# How to correctly evaluate the state value of this simple markov decision process?

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 ?

• 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) Sep 14, 2022 at 20:02
• 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. Sep 14, 2022 at 22:13
• 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. Sep 14, 2022 at 22:20
• 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. Sep 14, 2022 at 22:28

The issue is with your calculation of $$R_{a-b-a}$$: you're missing the +1 reward on the path from B to A.