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.
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 : -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 ?
