Calculating state value using bellman equation question:

Question

Consider a 4x4 grid world problem where the goal is to reach either the top left or bottom right corner. The agent can choose from four actions up,down,left,right which deterministically cause the corresponding state transitions, except that actions that would take the agent off the grid leave the state unchanged. We model this as an undiscounted,episodic task where the reward is -1 for all transitions. Suppose that the agent follows equi-probable random policy. Calculate the state values where * is placed.(Hint: Bellman expectation equation)

Grid(list of rows):

[

[  0,  *,-20,-22],

[-14,-18,-20,  *],

[   ,-20,-18,-14],

[-22,-20,   ,  0]

]

Should the * be initialized as 0 and then calculated using the equation?

Answer 1

Should the * be initialized as 0 and then calculated using the equation?

This would work if you repeated the calculation multiple times, and that would be similar to a solution method called value iteration. However, it is not what is intended here. Instead, if you expand the Bellman equation for $v_{\pi}(s)$ using your knowledge of existing values and the policy, you will get terms in your unknown on both sides (because one action in each case will stay in the same state) which you can resolve to directly find the value for the marked squares.

To work through this for the * on the top line, we can call the value $x$ and expand the Bellman equation as follows (working clockwise from "move up" action):

$$x = 0.25 * (-1 + x) + 0.25 * (-1 - 20) + 0.25 * (-1 - 18 ) + 0.25 * (-1 + 0)$$

$$3x = -1 - 21 - 19 -1$$

$$3x = -42$$

$$x = -14$$