Calculating state value using bellman equation 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?

• Welcome to AI Stack Exchange. This is definitely solvable, but it would help if you could clarify what you mean by "the equation". We can either confirm your suggestion is correct, or show you what's wrong with it, but we cannot do either unless you show which equation you mean. There are multiple Bellman equations, so if that's what you mean, identify which one(s) you were considering using Commented Sep 12, 2023 at 11:34
• @NeilSlater I should have mentioned the equation. I have edited the post and added the equation now. I had this question in one of my tests and so I had copied it as it is. Even the missing values were copied as they were in question so I copied them in the same way . Commented Sep 12, 2023 at 13:28
• OK, so you don't need the missing values to do the calculation. They were clearly removed because they are in symmetrical positions to the *, so you could correctly assume the problem is symmetrical and simply copy them :-) Commented Sep 12, 2023 at 13:59

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$$