MC Basic

Monte-Carlo Basic

Convert policy iteration to be model-free

Policy iteration has two steps:

$$\{\begin{array}{ll}\text{Policy evaluation:}& v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}\\ \text{Policy improvement:}& {\pi }_{k+1}=\arg {\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_{{\pi }_k})\end{array}$$

See the elementwise form of the policy improvement step:

$$\begin{array}{rl}{\pi }_{k+1}(s)& =\arg \underset{\pi }{\max }\sum _a\pi (a|s)\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{{\pi }_k}(s^{\prime })\right]\\ & =\arg \underset{\pi }{\max }\sum _a\pi (a|s)q_{{\pi }_k}(s,a),s\in \mathcal{S}\end{array}$$

为什么我们这里不太关注policy evaluation而是policy improvement

我们策略迭代都是围绕策略展开的，希望得到下一个策略之前我们最关心的也就是q的值，而对于policy evaluation，我们在policy iteration中是通过iterative form去解第一条式子得到$v_{{\pi }_k}$的值从而进行下一步的policy improvement的计算的，本质而言我们最后还是要进行q值的计算，所以不妨在policy evaluation阶段我们就直接进行Q值的采样、平均估计（MC method），这也正是可以避免用到环境模型，而是直接进行蒙特卡洛采样估计。

• expression 1: requires the model $$q_{{\pi }_k}(s,a)=\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{{\pi }_k}(s^{\prime })$$
• expression 2: model-free $$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$$ obtain $q$ based on data (samples of experiences)

MC Basic替代环境模型的core idea

when model is unavailable, we can use data(samples, experience)

• starting from $(s,a)$, following policy ${\pi }_k$, generate an episode
• the return of this episode is $g(s,a)$, which is a sample of $G_t$ (suggest that $G_t$ is a random variable)
• suppose we have a set of episodes $\{g^{(i)}(s,a)\}$, then we can estimate $q_{{\pi }_k}(s,a)$ by averaging the returns $$q_{{\pi }_k}(s,a)\approx \frac{1}{N}\sum _{i=1}^N{g}^{(i)}(s,a)$$ where $N$ is the number of episodes

Algorithm

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{MC Basic (Model-Free Policy Iteration)}\\ & \text{Input: }\text{Number of episodes }M\text{ per state-action pair }(s,a)\\ & \text{Initialization: }\text{Initial policy }{\pi }_0.\\ & \text{For }k=0,1,2,\dots :\\ & \text{Policy Evaluation:}\\ & \text{For each state }s\in \mathcal{S}:\\ & \text{For each action }a\in \mathcal{A}(s):\\ & \text{Collect }M\text{ episodes starting from }(s,a)\text{, following }{\pi }_k\\ & q_k(s,a)\leftarrow \frac{1}{M}\sum _{m=1}^M{G}^{(m)}(s,a)\text{(Average return)}\\ & \text{Policy Improvement:}\\ & \text{For each state }s\in \mathcal{S}:\\ & a_k^{\ast }(s)\leftarrow \arg \underset{a\in \mathcal{A}(s)}{\max }{q}_k(s,a)\text{(Greedy action)}\\ & {\pi }_{k+1}(a|s)\leftarrow \{\begin{array}{ll}1& \text{if }a=a_k^{\ast }(s)\\ 0& \text{otherwise}\end{array}\text{(Policy update)}\end{array}}$$

or we can combine the policy evaluation and policy improvement steps into one:

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{MC Basic (Model-Free Policy Iteration)}\\ & \text{Input: }\text{Number of episodes }M\text{ per state-action pair }(s,a)\\ & \text{Initialization: }\text{Initial policy }{\pi }_0.\\ & \text{For }k=0,1,2,\dots :\\ & \text{For each state }s\in \mathcal{S}:\\ & \text{For each action }a\in \mathcal{A}(s):\\ & \text{Collect }M\text{ episodes starting from }(s,a)\text{, following }{\pi }_k\\ & q_k(s,a)\leftarrow \frac{1}{M}\sum _{m=1}^M{G}^{(m)}(s,a)\text{(Average return)}\\ & a_k^{\ast }(s)\leftarrow \arg \underset{a\in \mathcal{A}(s)}{\max }{q}_k(s,a)\text{(Greedy action)}\\ & {\pi }_{k+1}(a|s)\leftarrow \{\begin{array}{ll}1& \text{if }a=a_k^{\ast }(s)\\ 0& \text{otherwise}\end{array}\text{(Policy update)}\end{array}}$$

Notes

• MC Basic is a varient of policy iteration
• model-free build on model-based policy iteration, neccessary to understand policy iteration
• why MC Basic estimate action valuses instead of state values?
  • state values cannot improve policy directly
  • when models are unavailable, we should directly estimate action values
• policy iteration is convergent ⇒ MC Basic is convergent
• episode should be sufficiently long, not have to be infinitely long

赵老师对大家学习的一个想法

MC Basic在其它地方看不到，原因就是这是赵老师起的名字，在学习的时候应该把最最核心的想法和其它让它看起来更加复杂的这样一些东西给剥离开来。

Later

• MC Basic is useful to reveal the core idea, but not practical due to its low efficiency

next⇒Use data more efficiently