Value Iteration

In the Gridworld example of the policy iteration section, you saw that you may not need to reach the optimal state value function $v_*(s)$ to obtain an optimal policy. The value function at iteration $k=3$ already gives the same policy as a far more accurate value function at large $k$. We could have stopped early, and taking the argument to the limit, we can question the need to start from a policy at all. Instead of letting the policy $\pi$ dictate which actions are selected, we select the actions that maximize the expected return: the immediate reward plus the discounted value of the successor state. We therefore do the improvement step in each iteration, computing the optimal value function without a policy. In this section we look at an algorithm called value iteration that does that. Value iteration. The basic principle behind value iteration is the principle that underlies dynamic programming, called the principle of optimality, as applied to policies. According to this principle an optimal policy can be divided into two components.

1. An optimal first action $a_*$.
2. An optimal policy from the successor state $s^\prime$.

More formally, for a discount factor $\gamma > 0$, a policy $\pi(a|s)$ achieves the optimal value from state $s$, $v_\pi(s) = v_*(s)$, if and only if it selects only optimal actions at $s$ and achieves the optimal value, $v_\pi(s^\prime) = v_*(s^\prime)$, from every successor state $s^\prime$ that it reaches from $s$ with positive probability. Effectively this principle allows us to decompose the problem into two sub-problems, one of them straightforward to determine, and to use the Bellman optimality equation, which provides the one-step backup induction at each iteration. $v_*(s) = \max_a \left( \mathcal R_s^a + \gamma \sum_{s^\prime \in \mathcal S} \mathcal{P}^a_{ss^\prime} v_*(s^\prime) \right)$ As an example, if I want to move optimally towards a location in the room, I can make an optimal first step and at that point follow the optimal policy, which I was magically given, towards the desired final location. Think of making that optimal first step by walking backwards from the goal state. We start at the end of the problem, where we know the final rewards, and work backwards to all the states that connect to it in our look-ahead tree. One-step look-ahead tree representation of the value iteration algorithm. The “start from the end” intuition behind the equation is usually applied with no consideration of whether we are at the end or not. We just do the backup inductive step for each state. In value iteration with synchronous backups, we start at $k=0$ from the value function $v_0(s)=0.0$, and at each iteration $k+1$, for all states $s \in \mathcal{S}$, we update $v_{k+1}(s)$ from $v_k(s)$. For a discounted problem with $0 \le \gamma < 1$ and bounded rewards, the update is a contraction, and the value function converges to $v_*$ from any starting point. With $\gamma = 1$ convergence needs further assumptions, for example an episodic problem in which every policy eventually reaches a terminal state; without them the values can grow without bound. The equation of value iteration is taken straight from the Bellman optimality equation, by turning the latter into an update rule called the Bellman update. $v_{k+1}(s) = \max_a \left( \mathcal R_s^a + \gamma \sum_{s^\prime \in \mathcal S} \mathcal{P}^a_{ss^\prime} v_k(s^\prime) \right)$ Value iteration can be written in vector form as $\mathbf v_{k+1} = \max_a \left( \mathcal R^a + \gamma \mathcal P^a \mathbf v_k \right)$ Notice that we are not building an explicit policy at every iteration, and the intermediate value functions may not correspond to a feasible policy.

​

Value Iteration in Gridworld Example

• To solve the non-linear equations for $v^{*}(s)$ we use an iterative approach.
• Steps:
  • Initialize estimates for the utilities of states with arbitrary values: $v(s) \leftarrow 0 \forall s \epsilon S$
  • Next use the iteration step below repeatedly. Since we are taking $\max$ we only need to consider states whose next states have a positive value.

$v_{k+1}(s) \leftarrow R(s) + \gamma \underset{a}{ \max} \left[ \sum_{s^{'}} P(s^{'}| s,a) v_k(s^{'}) \right] \forall s \epsilon S$

• Let us apply this to the maze example. Assume that $\gamma = 1$ for simplicity.

Initialize state value estimates.

• For the remaining states, the value is equal to the immediate reward in the first iteration.

States to consider - the only state that has as next state a positive value is shown.

​

Value Iteration (k=1)

$v_1(s_{33}) = R(s_{33}) + \gamma \max_a \left[\sum_{s^{'}} P(s^\prime| s_{33},a)v(s{'}) \right] \forall s \in S$ $v_1(s_{33}) = -0.04 + \max_a \left[ \sum_{s'} P(s'| s_{33},\uparrow) v_0(s'), \sum_{s'} P(s'| s_{33},\downarrow)v_0(s'), \sum_{s'} P(s'| s_{33},\rightarrow) v_0(s'), \sum_{s'} P(s'| s_{33}, \leftarrow)v_0(s') \right]$ $v_1(s_{33}) = -0.04 + \sum_{s^{'}} P(s^{'}| s_{33},\rightarrow) v_0(s^\prime)$ $v_1(s_{33}) = -0.04 + P(s_{43}|s_{33},\rightarrow)v(s_{43})+P(s_{33}|s_{33},\rightarrow)v(s_{33})+P(s_{32}|s_{33},\rightarrow)v_0(s_{32})$ $v_1(s_{33}) = -0.04 + 0.8 \times 1 + 0.1 \times 0 + 0.1 \times 0 = 0.76$

​

Value Iteration (k=2)

Initial value estimates for iteration 2 (A). States with next state positive value (B). $v_2(s_{33}) = -0.04 + P(s_{43}|s_{33},\rightarrow)v_1(s_{43})+P(s_{33}|s_{33},\rightarrow)v_1(s_{33}) +P(s_{32}|s_{33},\rightarrow)v_1(s_{32})$ $v_2(s_{33}) = -0.04 + 0.8 \times 1 + 0.1 \times 0.76 + 0.1 \times 0 = 0.836$ $v_2(s_{23}) = -0.04 + P(s_{33}|s_{23},\rightarrow)v_1(s_{23})+P(s_{23}|s_{23},\rightarrow)v_1(s_{23}) = -0.04 + 0.8 \times 0.76 = 0.568$ $v_2(s_{32}) = -0.04 + P(s_{33}|s_{32},\uparrow)v_1(s_{33})+P(s_{42}|s_{32},\uparrow)v_1(s_{42}) +P(s_{32}|s_{32},\uparrow)v_1(s_{32})$ $v_2(s_{32}) = -0.04 + 0.8 \times 0.76 + 0.1 \times -1 + 0.1 \times 0= 0.468$

​

Value Iteration (k=3)

Initial value estimates for iteration 3 (A). States with next state positive values (B) After many iterations, the value estimates converge to the optimal value function $v^*(s)$ and a policy $\pi^*$ can be derived from the value function using the following equation: $\pi^*(s) = \arg \max_a \left[ \sum_{s^{'}} P(s^{'}| s,a)v^*(s^{'}) \right]$ Optimal value function and optimal policy $\pi^*$ for the maze problem.

​

Value Iteration - Convergence

The rate of convergence depends mainly on the discount factor $\gamma$, and also on the maximum reward value. The policy that we get from coarse estimates is close to the optimal policy long before $v$ has converged. This means that after a reasonable number of iterations, we could extract the policy in a greedy fashion and use it to guide the agent’s actions. Convergence of value for the maze problem. For this problem, convergence is reached within 5 to 10 iterations. Key references: (Mansour & Singh, 2013; Tamar et al., 2016; Tamar et al., 2016)

​

References

• Mansour, Y., Singh, S. (2013). On the Complexity of Policy Iteration. arXiv [cs.AI].
• Tamar, A., Wu, Y., Thomas, G., Levine, S., Abbeel, P. (2016). Value Iteration Networks. arXiv [cs.AI].
• Tamar, A., Wu, Y., Thomas, G., Levine, S., Abbeel, P. (2016). Value Iteration Networks. arXiv [cs.AI].

---