3. Value Iteration

Solving the MDP

We wish to find an optimal policy (${\pi }^{\ast }$) for the problem that is:

• complete: covers all states
• optional: gives the best action for state $s$
• stationary: actions dependent only on current state
• proper: guaranteed to reach terminal state

Our policy should yield an expected utility for a given state following a policy $U^{\pi }(s)$

$$U^{\pi }(s)=E\left[\begin{array}{c}{\sum }_{t=0}^{\infty }{\gamma }^{t}R(St)\end{array}\right]$$

Consider ${\pi }^{\ast }(s)$ for the problem as $U^{\pi }(s)$: it is the expected sum of discounted rewards if the agent is running the optimal policy.

Hence we now have two ways of acknowledging rewards in the problem space:

• $R(s)$: the short-term reward when reaching a given state
• $U(s)$: the long-term reward of passing through $s$ on the way to the goal

Meaning that our optimal solution is selecting the action with best expected utility:

$${\pi }^{\ast }(s)=\underset{a\in A(s)}{\mathrm{argmax}}\sum _{s^{\prime }}P(s^{\prime }|s,a)U(s^{\prime })$$

$R(s)=-0.04$	$U(s)\to R(s)=-0.04,\gamma =1$

Calculating Optimal Policy

We need to calculate the utility of each state so we can derive the optimal action. Utility calculation considers all discounted rewards over time, but future rewards are derived from states with other utility values. Hence we can calculate a utility as the immediate reward plus the expected utility of the successor, assuming optimal action selection.

Bellman Equation

The Bellman equation:

$$U(s)=R(s)+\gamma \underset{a\in A(s)}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)U(s^{\prime })$$Link to original

For the example given prior, take for example we want to know the value of $U(1,1)$:

$$U(1,1)=-0.04+\gamma \cdot \underset{a\in A(1,1)}{\max }\{\begin{array}{l}0.8U(1,2)+0.1U(2,1)+0.1U(1,1)\\ 0.9U(1,1)+0.1U(1,2)\\ 0.9U(1,1)+0.1U(2,1)\\ 0.8U(2,1)+0.1U(1,2)+0.1U(1,1)\end{array}$$

Value Iteration Algorithm

To create the value iteration algorithm, we use the Bellman update equation:

$$U_{i+1}(s)=R(s)+\gamma \underset{a\in A(s)}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)U(s^{\prime })$$

We initialise $U(s)=0\forall s\in S$ then update $U(s)$ for all states in the problem. As time $t\to \infty$, the utility values will reach an equilibrium and stabilise.

Value Iteration Psuedocode