How do we get the value of this state of an MDP, at time-step $h-2$, using dynamic programming?

Question

I am trying to understand the problem below, represented as an MDP with four states (PU, PF, RU, and RF) and two actions (AS).

Let's consider V(RF), the value of the state RF. At time-step $h$, V(RF) = 10. When we go to the previous time-step $h-1$, V(RF) increases to 19.

Why is the value of RF increasing backward, i.e. at time-step $h$, which is the last step, it's 10, but in $h-1$ it's 19?

Also, when I apply the Bellman equation, I am not getting the value of V(RF) at time-step $h-2$, which is 25.08, according to the table.

Below is my solution which I am applying on V(RF):

Lets suppose for RF, I know that
Vh (RF) = max {R(RF,A), R(RF,S)}
        = max ({10,10}
Vh (RF) = 10

    **for h-1**
    Vh-1 (RF) = max R(RF,act) + gamma E (summation state) P(State|RF,act) Vh(State)
              = max {10+0.9(1*0), 10+0.9(0.5(10)+0.5(10))}
              = max (10,19)

    **for h-2**
    Vh-2(RF) = max R(RF,act) + gamma E(summation state) P(State|RF,act) Vh(State h-1)
             = max {19+0.9(1*0), 19+0.9(0.5(10)+0.5(10))}
             = 28.0

So, in the above scenario, the reward is 0.9, but I am not sure how we get the third result in V(RF) as 25.08. Where are we using this last part Vh(State) from the equation?

Answer 1

Wow, that's a really confusing example, if I were you I would check out some other RL resources. I wouldn't consider h being the last step and h-1 being the previous step. In terms of steps of iterations of the dynamic programming algorithm, h is actually the first step, h-1 the next step and so on. Viewing it in these terms it makes sense that the Value of RF increases from 10 to 19, because after the first step of dynamic programming the state RF incorporates some of the value from RU.

Here is the correct calculation for h-2.

$$10 + 0.9(0.5\times19+0.5\times14.5) = 25.08$$

You are doing a couple of things incorrectly in your calculation:

• Firstly, you are mistakenly assigning the reward a value of 19. The reward should be 10. Note that the reward and Value are two different quantities. As we iterate through the dynamic programming algorithm, our current approximation of the values will change but reward will always remain the same (it is the number as indicated in the bubbles in the diagram). It just so happens that the Value and reward are equal on the first step (h).
• You are using the Values for states RU and RF (=10) from step h to calculate the values step h-2 which is incorrect. You should be using the values from step h-1 which are 14.5 and 19 respectively.

Using this understanding, the calculation for the next step h-3 would be (notice that I am now using values from step h-2).

$$10 + 0.9*(0.5*25.08+0.5*16.53) = 28.72$$