Answers.Body: <p>The issue is with your calculation of <span class="math-container">$R_{a-b-a}$</span>: you're missing the +1 reward on the path from B to A.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-16T17:06:54.283Z
Answers.LastActivityDate: 2022-09-16T17:06:54.283Z
Answers.UserDisplayName: Raphael Lopez Kaufman
Body: <p>For some contexts, I'm working on a c# library for reinforcement learning. I implemented two methods to evaluate a state value function, namely the TD(0) method and the Monte Carlo first visit method.</p>
  <p>To test my code, I ran it with a simple, but not trivial markov decision process, described in the image below.</p>
  <p><a href="https://i.sstatic.net/HQa9b.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/HQa9b.jpg" alt="enter image description here" /></a></p>
  <p>In the picture, you have, in green the rewards, and in red the probabilities of transition. E is a terminal state.</p>
  <p>We have two possible actions in state A, either going to C, so let's call it AtoC, or going to B or D, let's call it AtoBorD. The policy we evaluate choose randomly with a 50/50 chance between those two actions when in state A. The policy is implicit for the rest of the states since only one choice is possible.</p>
  <p>That's for the context, now my issue is the following. <strong>How to properly compute the state value of A ?</strong> I tested both my numerical methods, and they both gave a value very close to -8.6, however, when I compute it myself I find -8.93. I first thought it was an issue with the algorithms but since they both give the same answer, my computation must be the issue.</p>
  <p>So here's what I did, I'd be grateful if you find where I did wrong.
  Going back to the definition, the state value of A is the total expected return when following a given policy :</p>
  <p><span class="math-container">$$ \mathbb{E}_\pi(G_t|S_t = A)$$</span></p>
  <p>With <span class="math-container">$G_t$</span> the total return of an episode from state <span class="math-container">$S_t = A$</span> and <span class="math-container">$\pi$</span> the policy.</p>
  <p>I'll use the following notation for the rest of this demonstration :</p>
  <p><span class="math-container">$p_{a-c-d-e}$</span> is the probability of following the path A-C-D-E.</p>
  <p><span class="math-container">$R_{a-c-d-e}$</span> is the reward from following the path A-C-D-E.</p>
  <p>Going back to the very definition of the expectation :</p>
  <p>The set of outcomes for our random variable <span class="math-container">$G_t$</span> is infinite, since there's the A-B loop in the Markov process.</p>
  <p>The potential values of <span class="math-container">$G_t$</span> are :</p>
  <ul>
  <li><span class="math-container">$R_{a-c-d-e}$</span></li>
  <li><span class="math-container">$R_{a-d-e}$</span></li>
  <li><span class="math-container">$R_{a-b-a-c-d-e}$</span></li>
  <li><span class="math-container">$R_{a-b-a-d-e}$</span></li>
  <li><span class="math-container">$R_{a-b-...-a-b-a-c-d-e}$</span></li>
  <li><span class="math-container">$R_{a-b-...-a-b-a-d-e}$</span></li>
  <li>...</li>
  </ul>
  <p>First we note that the average reward <span class="math-container">$R_{a-b-a}$</span> is equal to <span class="math-container">$-5 \times 0.2-3 \times 0.8= -1.8$</span>.</p>
  <p>When looping N times through state A and B, we then expect that <span class="math-container">$R_{a-b-...-a-b-a} = N R_{a-b-a} = -1.8 N$</span> (with B appearing N times).</p>
  <p>We also have <span class="math-container">$R_{a-c-d-e}=-10$</span> and <span class="math-container">$R_{a-d-e}=-5$</span>.</p>
  <p>Taking an arbitrary number of <em>a-b</em> sequences (a-b-a-b-..-a-b) and then adding either <em>a-c-d-e</em> or <em>a-d-e</em> is enough to describe all possible path in this Markov process.</p>
  <p>We also note that state transitions are independent of each other, so for example :</p>
  <p><span class="math-container">$$p_{a-b-a-b-a-c-d-e} =  p_{a-b-a} p_{a-b-a} p_{a-c-d-e} = p_{a-b-a}^2 p_{a-c-d-e}$$</span></p>
  <p><strong>Using all of these, we can explicitly write the expected total return from state A :</strong></p>
  <p><span class="math-container">$$ \mathbb{E}[G_t|S_t=A] =  p_{a-d-e} R_{a-d-e} + p_{a-c-d-e} R_{a-c-d-e} + \sum_{N=1}^\infty p_{a-b-a}^N  p_{a-c-d-e} (N R_{a-b-a} + R_{a-c-d-e}) + \sum_{N=1}^\infty p_{a-b-a}^N  p_{a-d-e} (N R_{a-b-a} + R_{a-d-e})  $$</span></p>
  <p>Replacing the terms with their numerical values :
  Remind that we are following a policy that choose equiprobably between two actions,going to C or going to D or B. Then,</p>
  <ul>
  <li><span class="math-container">$p_{a-c-d-e} = 0.5$</span> since it depends purely on the policy choice.</li>
  <li><span class="math-container">$p_{a-b-a} = 0.5 \times (0.4+0.1) = 0.25$</span> since it depends on the action chosen and on the dynamic of the system.</li>
  <li><span class="math-container">$p_{a-d-e} = 0.5 \times 0.5 =0.25$</span>, same as <span class="math-container">$p_{a-b-a}$</span>.</li>
  </ul>
  <p>The reward are already given further up.</p>
  <p><span class="math-container">$$ \mathbb{E}[G_t|S_t=A] = -0.25 \times 5 - 0.5 \times 10 + \sum_{N=1}^\infty 0.25^N  \times 0.5 \times (-1.8 N - 10) + \sum_{N=1}^\infty 0.25^N  \times 0.25 \times (-1.8 N  - 5) $$</span></p>
  <p>At this point, I got help from wolfram alpha, <a href="https://www.wolframalpha.com/input?i=-0.25%20*5%20-%200.5%20*%2010%20%2B%20sum%200.25%5En%20*%200.25%20*%20%28-1.8n-5%29%2C%20n%3D1%20to%20infinity%20%2B%20sum%200.25%5En%20*%200.5%20*%20%28-1.8n-10%29%2C%20n%3D1%20to%20infinity" rel="nofollow noreferrer">this gave me the following result</a> : -8.93.</p>
  <p>Sadly, both my implementations disagree with me, but what bugs me is that the values are quite close, since they find -8.6.</p>
  <p><strong>Do you see anything wrong with my computation ?</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-14T20:02:24.980Z
Comments.Text: Isn't there a slight mistake in the probabilities of the actions from state A? I read that $P(A\rightarrow C) = 1$ and then that $P(A\rightarrow B) = 0.5$ and $P(A\rightarrow D) = 0.5$. But these probabilities should sum to 1. Another thing I don't understand is when you say that $R_{a-b-a} = -5 \times 0.2 -3 \times 0.8$. Reading the graph, depending on the path you take, the reward is either $-5 + 1$ with probability 0.1 (the left arrow from A to B) or $-1 + 1$ with probability 0.4 (the right arrow from A to B)
Comments.UserDisplayName: Raphael Lopez Kaufman
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-14T22:13:33.950Z
Comments.Text: Thank you for your answer ! regarding the probabilities in red, it's the probabilities *given* the choice of an action. If you choose the arrow leading to C, there's a probability equal to one that you'll end up in state C. If you choose the other arrow, then there's a probability equal to 0.5 that you end up in B and 0.5 in D.
Comments.UserDisplayName: nathan raynal
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-14T22:20:02.903Z
Comments.Text: Regarding the reward for $R_{a-b-a}$ I messed it up big time. Thank you for pointing it. The probabilities are correct here (0.2 and 0.8) because it's also conditional probabilities knowing that the path is a-b-a. but the reward should be $R_{a−b−a}=−4×0.2−0×0.8.$. I forgot the +1 reward from B to A. I'm going to correct it and test it.
Comments.UserDisplayName: nathan raynal
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-14T22:28:59.433Z
Comments.Text: So I tried by changing the value of $R_{a-b-a}$ from -1.8 to -0.8 and it worked ! Thank you for pointing it out, it's really helpful. If you want to put that this reward was the issue I'll gladly accept your answer.
Comments.UserDisplayName: nathan raynal
Tags: <reinforcement-learning><markov-decision-process><expectation>
Title: How to correctly evaluate the state value of this simple markov decision process?
UserDisplayName: nathan raynal
ThreadText: # How to correctly evaluate the state value of this simple markov decision process?
  
  (Asked by: username_0 on 2022-09-14)
  
  For some contexts, I'm working on a c# library for reinforcement learning. I implemented two methods to evaluate a state value function, namely the TD(0) method and the Monte Carlo first visit method.
  
  To test my code, I ran it with a simple, but not trivial markov decision process, described in the image below.
  
  [![enter image description here](https://i.sstatic.net/HQa9b.jpg)](https://i.sstatic.net/HQa9b.jpg)
  
  In the picture, you have, in green the rewards, and in red the probabilities of transition. E is a terminal state.
  
  We have two possible actions in state A, either going to C, so let's call it AtoC, or going to B or D, let's call it AtoBorD. The policy we evaluate choose randomly with a 50/50 chance between those two actions when in state A. The policy is implicit for the rest of the states since only one choice is possible.
  
  That's for the context, now my issue is the following. **How to properly compute the state value of A ?** I tested both my numerical methods, and they both gave a value very close to -8.6, however, when I compute it myself I find -8.93. I first thought it was an issue with the algorithms but since they both give the same answer, my computation must be the issue.
  
  So here's what I did, I'd be grateful if you find where I did wrong.
  Going back to the definition, the state value of A is the total expected return when following a given policy :
  
  $$ \mathbb{E}\_\pi(G\_t|S\_t = A)$$
  
  With $G\_t$ the total return of an episode from state $S\_t = A$ and $\pi$ the policy.
  
  I'll use the following notation for the rest of this demonstration :
  
  $p\_{a-c-d-e}$ is the probability of following the path A-C-D-E.
  
  $R\_{a-c-d-e}$ is the reward from following the path A-C-D-E.
  
  Going back to the very definition of the expectation :
  
  The set of outcomes for our random variable $G\_t$ is infinite, since there's the A-B loop in the Markov process.
  
  The potential values of $G\_t$ are :
  
  * $R\_{a-c-d-e}$
  * $R\_{a-d-e}$
  * $R\_{a-b-a-c-d-e}$
  * $R\_{a-b-a-d-e}$
  * $R\_{a-b-...-a-b-a-c-d-e}$
  * $R\_{a-b-...-a-b-a-d-e}$
  * ...
  
  First we note that the average reward $R\_{a-b-a}$ is equal to $-5 \times 0.2-3 \times 0.8= -1.8$.
  
  When looping N times through state A and B, we then expect that $R\_{a-b-...-a-b-a} = N R\_{a-b-a} = -1.8 N$ (with B appearing N times).
  
  We also have $R\_{a-c-d-e}=-10$ and $R\_{a-d-e}=-5$.
  
  Taking an arbitrary number of *a-b* sequences (a-b-a-b-..-a-b) and then adding either *a-c-d-e* or *a-d-e* is enough to describe all possible path in this Markov process.
  
  We also note that state transitions are independent of each other, so for example :
  
  $$p\_{a-b-a-b-a-c-d-e} = p\_{a-b-a} p\_{a-b-a} p\_{a-c-d-e} = p\_{a-b-a}^2 p\_{a-c-d-e}$$
  
  **Using all of these, we can explicitly write the expected total return from state A :**
  
  $$ \mathbb{E}[G\_t|S\_t=A] = p\_{a-d-e} R\_{a-d-e} + p\_{a-c-d-e} R\_{a-c-d-e} + \sum\_{N=1}^\infty p\_{a-b-a}^N p\_{a-c-d-e} (N R\_{a-b-a} + R\_{a-c-d-e}) + \sum\_{N=1}^\infty p\_{a-b-a}^N p\_{a-d-e} (N R\_{a-b-a} + R\_{a-d-e}) $$
  
  Replacing the terms with their numerical values :
  Remind that we are following a policy that choose equiprobably between two actions,going to C or going to D or B. Then,
  
  * $p\_{a-c-d-e} = 0.5$ since it depends purely on the policy choice.
  * $p\_{a-b-a} = 0.5 \times (0.4+0.1) = 0.25$ since it depends on the action chosen and on the dynamic of the system.
  * $p\_{a-d-e} = 0.5 \times 0.5 =0.25$, same as $p\_{a-b-a}$.
  
  The reward are already given further up.
  
  $$ \mathbb{E}[G\_t|S\_t=A] = -0.25 \times 5 - 0.5 \times 10 + \sum\_{N=1}^\infty 0.25^N \times 0.5 \times (-1.8 N - 10) + \sum\_{N=1}^\infty 0.25^N \times 0.25 \times (-1.8 N - 5) $$
  
  At this point, I got help from wolfram alpha, [this gave me the following result](https://www.wolframalpha.com/input?i=-0.25%20*5%20-%200.5%20*%2010%20%2B%20sum%200.25%5En%20*%200.25%20*%20%28-1.8n-5%29%2C%20n%3D1%20to%20infinity%20%2B%20sum%200.25%5En%20*%200.5%20*%20%28-1.8n-10%29%2C%20n%3D1%20to%20infinity) : -8.93.
  
  Sadly, both my implementations disagree with me, but what bugs me is that the values are quite close, since they find -8.6.
  
  **Do you see anything wrong with my computation ?**
  
  **Tags:** reinforcement-learning, markov-decision-process, expectation
  
  > **Comments:**
  > **username_1**: Isn't there a slight mistake in the probabilities of the actions from state A? I read that $P(A\rightarrow C) = 1$ and then that $P(A\rightarrow B) = 0.5$ and $P(A\rightarrow D) = 0.5$. But these probabilities should sum to 1. Another thing I don't understand is when you say that $R_{a-b-a} = -5 \times 0.2 -3 \times 0.8$. Reading the graph, depending on the path you take, the reward is either $-5 + 1$ with probability 0.1 (the left arrow from A to B) or $-1 + 1$ with probability 0.4 (the right arrow from A to B)  
  > **username_0**: Thank you for your answer ! regarding the probabilities in red, it's the probabilities *given* the choice of an action. If you choose the arrow leading to C, there's a probability equal to one that you'll end up in state C. If you choose the other arrow, then there's a probability equal to 0.5 that you end up in B and 0.5 in D.  
  > **username_0**: Regarding the reward for $R_{a-b-a}$ I messed it up big time. Thank you for pointing it. The probabilities are correct here (0.2 and 0.8) because it's also conditional probabilities knowing that the path is a-b-a. but the reward should be $R_{a−b−a}=−4×0.2−0×0.8.$. I forgot the +1 reward from B to A. I'm going to correct it and test it.  
  > **username_0**: So I tried by changing the value of $R_{a-b-a}$ from -1.8 to -0.8 and it worked ! Thank you for pointing it out, it's really helpful. If you want to put that this reward was the issue I'll gladly accept your answer.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-09-16. Score: 2 | Accepted answer
  
  The issue is with your calculation of $R\_{a-b-a}$: you're missing the +1 reward on the path from B to A.
  
  
  ---
  
  