Two Sweeps Of Value Iteration

A three-state MDP with $\gamma = 0.9$ . State $G$ is terminal with $v(G) = 0$ forever. All transitions are deterministic.

state	action	reward	next state
$s_1$	right	0	$s_2$
$s_1$	stay	0.5	$s_1$
$s_2$	right	10	$G$
$s_2$	left	0	$s_1$

Run synchronous value iteration, $v_{k+1}(s) = \max_a \left[ r(s,a) + \gamma, v_k(s') \right]$ , from $v_0 = 0$ everywhere. Give $v_2$ and the greedy action in $s_1$ after each sweep.

$v_2(s_1) = 10$ , $v_2(s_2) = 10$ ; both states reach the goal, so both inherit its reward of 10.

$v_2(s_1) = 9$ , $v_2(s_2) = 10$ ; the greedy action in $s_1$ is stay after sweep 1 and right after sweep 2.

$v_2(s_1) = 9$ , $v_2(s_2) = 10$ ; the greedy action in $s_1$ is right after both sweeps, since each sweep already maximises over actions.

$v_2(s_1) = 0.95$ , $v_2(s_2) = 10$ ; each sweep evaluates the action the current greedy policy selects, and in $s_1$ that action is stay.