18-Iteration.md

tags	comments	dg-publish
notes cs188	true	true

note

Value Iteration

Considering finite horizons, The time-limited value for a state s with a time-limit of k timesteps is denoted $U_k(s)$,

Value iteration is a dynamic programming algorithm that uses an iteratively longer time limit to compute time-limited values until convergence¹ , operating as follows:

1. $\mathrm{\forall }s\in S$, initialze $U_0(s)=0$, since no actions can be taken to acquire rewards.
2. repear the following update rule until convergence (B is called the Bellman operator):

$$\mathrm{\forall }s\in S,U_{k+1}(s)\leftarrow \underset{a}{max}\sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma U_k(s^{\prime })](or{U}_{k+1}\leftarrow B{U}_k)$$

When convergence is reached, the Bellman equation will hold for every state: $\mathrm{\forall }s\in S,U_{k+1}(s)=U_k(s)=U^{\ast }(s)$.

Q-value Iteration

Q-value iteration is a dynamic programming algorithm that computes time-limited Q-values. It is described in the following equation: $Q_{k+1}(s,a)\leftarrow \sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{max}{Q}_k(s^{\prime },a^{\prime })]$.

Policy Iteration

policy extraction

$$\forall s\in S,:\boldsymbol{\pi}^{}(s)=\underset{a}{\operatorname{\operatorname*{\operatorname*{argmax}}}}Q^{}(s,a)=\underset{a}{\operatorname{\operatorname*{\arg\max}}}\sum_{{s^{\prime}}}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\boldsymbol{\gamma}U^{*}(s^{\prime})]$$

policy evaluation

For a policy π, policy evaluation means computing $U^{\pi }(s)$ for all states s, where $U^{\pi }(s)$ is expected utility of starting in state s when following π :

$$U^{\mathit{\pi }}(s)=\sum _{s^{\prime }}T(s,\mathit{\pi }(s),s^{\prime })[R(s,\mathit{\pi }(s),s^{\prime })+\mathit{\gamma }{U}^{\mathit{\pi }}(s^{\prime })]$$

policy improvement

Once we’ve evaluated the current policy, use policy improvement to generate a better policy.

Define the policy at iteration i of policy iteration as ${\pi }_i$ , we have

$$U_{k+1}^{{\boldsymbol{\pi}{i}}}(s)\leftarrow\sum{{s^{\prime}}}T(s,\boldsymbol{\pi}{i}(s),s^{\prime})[R(s,\boldsymbol{\pi}{i}(s),s^{\prime})+\boldsymbol{\gamma}U_{k}^{{\boldsymbol{\pi}_{i}}}(s^{\prime})]$$

finally improve policy with:

$$\boldsymbol{\pi}{i+1}(s)=\underset a{\operatorname*{argmax}}\sum{s^{\prime}}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\boldsymbol{\gamma}U^{\pi_i}(s^{\prime})]$$

summary

link

• cs188-sp24-note18

Footnotes

1. convergence means that $\forall s \in S, U_{k+1}(s) = U_{k}(s)$. ↩