2
$\begingroup$

I am having a hard time to understand the value iteration derived from the Bellman equation:

$$V_{k=0}(s) = 0$$

$$\forall s : V_{k+1}(s) = \max_a \Bigr[ R(s,a) + \gamma \sum_{s'} P(s'|s, \pi(s)) V_k(s') \Bigr]$$

I am trying to understand this on a concrete example I have thought of: A maze and a rat in it:

                            +------------------+
                            | s2             s3|
                            +------+ s1 +------+
                                   |    |
                                   |  R |

There are only three states. $s_1$ is a T-junction with the possible actions, left and right. $s_2$ and $s_3$ is food and something else poision or so. Thus granting rewards $(2,0)$. Everything is determinstic and I would like to use a discounting of $\gamma = 0.5$

How would a concrete example look like:

Here are my thoughts:

  • $R(s,a)$ is the reward which would be granted immediately (isn't it?), so I guess for $s_1$ this would be $0$?
  • the sum $\sum_{s'}$ is the sum over the possible transition states, that would be $s_2$ and $s_3$?
  • the transition probability $P(s'|s, \pi(s))$ is not given, but maybe it's just $1/2$

When I try to write it down it does not seem to make a lot sense:

\begin{align} V_{k=1}(s_1) = 0 + 0.5 + (0.5 \cdot 0 + 0.5 \cdot 0) = 0 \end{align}

This would just become zero again, is that correct?

\begin{align} V_{k=1}(s_2) = 3 + 0.5 + (0.5 \cdot 0 + 0.5 \cdot 0) = 3 \end{align}

How would the $a$ be evaluated? Its the state of the rat and it should choose the one with the highest result, but what are possible $a$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Your example is a little weaker than it could be, because there don't really seem to be any actions, however, we can work with that; I'll preserve the $\max_a$ and $R(s,a)$ pieces of notation, although $a$ isn't operative in the example. I'm assuming that from state 1 there is a 50-50 chance of transitioning to either state 2 or state 3, and that the discount rate is also 50%, as per your example. I also assume the rewards $R(s,a)$ for being in states 1, 2, and 3 are 0, 2, and 0 respectively.

Value iteration iterates until the values converge. At the first iteration, as you have, $V_0(s) = 0 \space \forall s$.

At iteration 1:

$V_1(s=3) = \max_a\{R(3,a)\} = 0$ as state 3 is a terminal state, so no transitions.

$V_1(s=2) = \max_a\{R(2,a)\} = 2$ as state 2 is a terminal state, so no transitions.

$V_1(s=1) = \max_a\{R(1,a) + 0.5(0.5*V_0(s=2) + 0.5*V_0(s=3))\} = 0$

At iteration 2:

$V_2(s=3) = \max_a\{R(3,a)\} = 0$ as state 3 is a terminal state, so no transitions.

$V_2(s=2) = \max_a\{R(2,a)\} = 2$ as state 2 is a terminal state, so no transitions.

$V_2(s=1) = \max_a\{R(1,a) + 0.5(0.5*V_1(s=2) + 0.5*V_1(s=3))\} = 0.5$

At iteration 3:

$V_3(s=3) = \max_a\{R(3,a)\} = 0$ as state 3 is a terminal state, so no transitions.

$V_3(s=2) = \max_a\{R(2,a)\} = 2$ as state 2 is a terminal state, so no transitions.

$V_3(s=1) = \max_a\{R(1,a) + 0.5(0.5*V_2(s=2) + 0.5*V_2(s=3))\} = 0.5$

And we have convergence! All the $V_3(s) = V_2(s)$. In a more complex example, with actions included, $V_3(s) = V_2(s)$ implies that the actions selected at iteration 3 and at iteration 2 are either equal or equivalent in terms of value; having part of the algorithm be a fixed way of choosing between actions that are tied, in terms of expected value, reduces the implication to the actions being the same between iterations.

$\endgroup$
5
  • $\begingroup$ Thanks for the detailed explanation. A question right ahead for the transition probability. I chose the probability of $0.5$ just arbitrarily. But when it is said, all actions are deterministic doesn't that then mean the probability is chosen by the policy? For instance $1$ oder $0$ instead something in between. $\endgroup$
    – Mahoni
    Commented Jun 22, 2012 at 22:51
  • 1
    $\begingroup$ Nein, there are no actions at all, therefore no policy (to speak of), so the state transition probabilities are fixed. A more complex example might have two actions in state 1, call them $a$ and $b$, such that $R(1,a)=0$ and $R(1,b)=1$, which influence the transition probabilities: $P(1\to 2|a)=0.5$ and $P(1\to 2|b)=0.7$. (Basically action $b$ means you pay 1 unit to improve your chances of getting to state 2 from 50% to 70%.) Try setting that up and solving it using value iteration. $\endgroup$
    – jbowman
    Commented Jun 22, 2012 at 23:00
  • $\begingroup$ To clarify terminology: in dynamic programming (DP) terminology, an action is what you choose when you are in a state and you have a choice. Although it may seem that you are "acting" when you transition from one state to another, that's the English language usage of "action", not the DP usage. The DP term for that is "transitioning", and it occurs after you choose your action. $\endgroup$
    – jbowman
    Commented Jun 22, 2012 at 23:07
  • $\begingroup$ That was a mistake of mine, actually it says "Everything is deterministic" so not really referencing to the so called actions. I was just wondering, because since I haven't given any transition probabilities it seemed wrong to just assume one out of the blue. $\endgroup$
    – Mahoni
    Commented Jun 22, 2012 at 23:11
  • 1
    $\begingroup$ Ah, I see your point. Maybe the real problem description does have two actions, "left" and "right", and there are no transition probabilities, hence deterministic. In that case, all those $0.5*V_k(s=2)$ statements etc. should be changed to just $V_k(s=2)$ if you choose "left" and $V_k(s=3)$ if you choose "right", and the value $V_k(s=1)$ is the maximum over choosing "left" and "right". $\endgroup$
    – jbowman
    Commented Jun 22, 2012 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.