Reinforcement Learning, Bellman Update

Policy Iteration

Intuition: build a policy, then build value function, and then build a better policy, and rinse and repeat until the optimal policy.

Policy iteration is the process of alternating between 2 things:

1. Policy Evaluation With fixed current policy $\pi$, find values with simplified Bellman expectation backups (iterate until values converge)

$v_{i+1}^{\pi }(s)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\lambda v_i^{\pi }(s^{\prime })]$ Other Notation from CS287 $V_{i+1}^{{\pi }_k}(s)={\sum }_{s^{\prime }}T(s,\pi (s),s^{\prime })[R(s,{\pi }_k(s),s^{\prime })+\gamma V_i^{\ast }(s^{\prime })]$

• Notice that the above is extremely similar, instead of using the $T(s,a,s^{\prime })$ in Value Iteration we can use $T(s,\pi (s),s^{\prime })$ to evaluate a particular policy.
• We are not taking the max because we don’t have a choice, the policy $\pi$ decides the action $a=\pi (s)$

2. Policy Improvement With fixed utilities, find the best action according to one-step lookahead. You basically override the action for the very first action.

• Improve the policy by acting greedily with respect to $v_{\pi }$ (Policy Improvement) ${\pi }^{\prime }=\text{greedy}(v_{\pi })$ ${\pi }^{\prime }(s)=\underset{a\in A}{\mathrm{argmax}}{q}_{\pi }(s,a)$ ${\pi }_{k+1}(s)={\text{argmax}}_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma v_k(s^{\prime }))$

How does acting epsilon greedy actually result in policy improvement??

Acting ε-greedy with respect to Q(s, a) leads to policy improvement because the greedy part exploits the best-known action, and the ε-randomness ensures exploration that lets us discover even better actions. Over time, this exploration refines Q(s, a), and thus, the greedy part improves too.

umm, but like wouldn’t that refine the Q negatively too?? Exploration can lead to bad actions. See proof below

Alternative notation from CS287: ${\pi }_{k+1}(s)={\text{argmax}}_a{\sum }_{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{{\pi }_k}(s^{\prime })]$ Repeat steps 1 and 2 until the policy converges, i.e. ${\pi }_k(s)={\pi }_{k+1}(s)$

Policy iteration always converges to the optimal policy ${\pi }_{\ast }$. In terms of comparing with Value Iteration, this is a lot longer it seems, because we need to figure calculate the value function for a particular policy, and then come up with a new policy.

Note

The example below is done with action-value functions, whereas the textbook uses state-value functions. It’s essentially the same thing, but in Model-Free Control, we always use q-values, and model-free are where the more interesting problems are.

Proof (IMPORTANT)

We essentially act greedily with respect to the action-value functions, doing a Bellman Optimality Backup.

https://www.tuananhle.co.uk/notes/policy-improvement-theorem.html

This improves the value from any state $s$ over one step, $q_{\pi }(s,{\pi }^{\prime }(s))\ge q_{\pi }(s,\pi (s))$ It therefore improves the value function, $v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$

Related

• Value Iteration