One Sweep Then Greedy

A two-state MDP, $\gamma = 0.9$ , all transitions deterministic.

state	action	reward	next state
$s_1$	$a$	1	$s_1$
$s_1$	$c$	0	$s_2$
$s_2$	$b$	0	$s_1$
$s_2$	$d$	2	$s_2$

The current policy $\pi$ takes $a$ in $s_1$ and $b$ in $s_2$ . Policy evaluation is run to convergence, then one policy improvement step is taken.

Which action does the improved policy take in $s_2$ ?

Neither can be chosen yet: improvement is only valid once $v_\pi$ has been recomputed under the new policy.

$d$ , because $q_\pi(s_2,d) = 10.1$ beats $q_\pi(s_2,b) = 9$ .

$b$ , because $b$ moves to $s_1$ , which is the higher-valued state under $v_\pi$ .

It is a tie at 10, so the policy is already greedy and iteration stops here.