2
$\begingroup$

I am watching the lecture by Abbeel on MDPs and Reinforcement Learning. The setup of the problem is the classic gridworld with optimal policy (and corresponding values of states) pictured below. enter image description here

The parameters of the problem here are: there is a 0.8 chance that you go to your chosen action and 0.1 chance you go to a direction perpendicular to it. For example, if you choose "right", then you have a 0.8 chance of going right and a 0.1 chance of going up, and another 0.1 chance of going down. If the action makes the agent 'bump' into the wall or 'leave' the world, then the agent stays in the same place.

My question is this: Since the problem above shows the optimal policy (having solved/demonstrated the solution via the Value Iteration algorithm), is it possible that I solve for the values of the states manually (analytically), knowing that the optimal policy is give above? I expected that if I setup the (system of) equations, I should be able to recover the values that are printed in the figure above.

I represented the states of the gridworld as follows. $X$ is just a place holder since it is a blocked state.

$\begin{array}{cccc} H & D & A & +1 \\ G &X & B & -1 \\ F & E & C & J \end{array}$

Knowing that $V^{\pi}(s) = \displaystyle\sum_{a} \pi(a|S) \displaystyle\sum_{s'} P(s'|s,a) [r_{t+1} + \gamma V^{\pi}(s')]$, $\gamma = 0.9$, there are no rewards awarded for every step except with entering the terminal states $+1$ and $-1$.

The actions are already deterministic at this point, so I set $\pi(a|s) = 1$. For simplicity of notation, I just wrote $A$ as the value of state $A$ in the following equations:

At state $A$: $A = 0.8[1+0] + 0.1[0.9A] + 0.1[0.9B]$. Meaning: 0.8 chance of going right, receiving a reward of 1, and the value of the terminal state is 0. 0.1 change of going up and therefore ending up in the same state $A$. Finally, 0.1 chance of going down, ending up in state $B$.

Another example: $H = 0.8[0.9D] + 0.1[0.9H] + 0.1[0.9G]$ Meaning: 0.8 chance to move right to D, 0.1 chance to bump the upper wall and stay in H, another 0.1 chance to move down the lower state G.

There are a total of 9 equations of this form. When I solved for the unknowns $A,B,\cdots,J$, why am I not getting the values placed here in this figure?

Edit: I found an error that made the values way above 1. The error is now fixed. The values are now below 1, which is good. But why am I not getting the values indicated in this figure?

Please give some insights.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

In the gridworld setting, you can replicate the lecture's results, by defining the reward function $R_t(s,a) = R(s)$, meaning that the reward function simply aggregates only on the current state and ignores the selected action and the next state, as well. With this modification, the state value of a terminal state always (after the 1st iteration) equals its reward (+1 or -1).

However, this is not very common in MDP implementations (e.g. in gym envs). I think that when this is the case, it should always be highlighted.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Another way to put this: The states in boxes with +1 and -1 reward for leaving them are not the terminal states. The terminal state occurs when taking any action from those states (which also grants the associated reward), and is not shown on the grid. How can you tell they are not terminal states? Because they have a non-zero value. Terminal states have 0 value by definition (because nothing happens after the agent enters them) $\endgroup$
    – Neil Slater
    Feb 19, 2022 at 1:58
  • $\begingroup$ Exactly. There is a little confusion on the definition of Q and V among books and lecture slides. $\endgroup$
    – ddaedalus
    Feb 19, 2022 at 13:23
  • $\begingroup$ @NeilSlater Yes! I found this out while performing the lengthy and tedious computation. I think this is something that should be said especially when you are learning MDP for the first time to avoid this grand confusion. $\endgroup$
    – cgo
    Feb 21, 2022 at 2:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .