Reinforcement Learning - MC

Model-Free RL Algorithm

emm，名字看起来很玄乎，但是实际上就是基于统计学的做法

 

 

1. Monte-Carlo Basics

本部分以 Reinforcement Learning - Value / Policy Iteration 中的 Policy Iteration 为基础介绍 Monte-Carlo Method 的基本原理

注意：后文提到的 Model-Free Policy Iteration 网上大概是搜不到的，因为压根就不值得用

 

 

1.1 Review: 大数定理

• Sampling Distribution

  a set of $n$$n$ Random Variables $X_1,X_2,...,X_n$$X_1,X_2,...,X_n$ drawn independently & identically from a common distribution $X$$X$

• Mean of Sampling Distribution

  $$\overline{X}=\frac{1}{n}\sum _{i=1}^n{X}_i$$

  那么依据 Law of Large Numbers，当 $n\to \mathrm{\infty }$$n\to\infin$ 时，采样分布之均值将收敛于 Expectation

  $$\begin{array}{rl}\mathbb{E}[\overline{X}]& =\mathbb{E}[X]\\ \text{Var}[\overline{X}]& =\frac{1}{n}\text{Var}[X]\end{array}$$

 

 

1.2 无模型 Policy Iteration

用 Monte-Carlo Estimation 的方式将 Policy Iteration 改成 Model Free 的版本

基本的 Policy Iteration 算法

1. Step 1 - Policy Evaluation (PE)

   Find State Value $v_{{\pi }_k}$$v_{\pi_k}$ given Policy ${\pi }_k$$\pi_k$

   $$v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}$$

2. Step 2 - Policy Improvement (PI)

   Plug in derived $v_{{\pi }_k}$$v_{\pi_k}$, solve for improved policy ${\pi }_{k+1}$$\pi_{k+1}$

   $${\pi }_{k+1}=\arg \underset{\pi }{max}[r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}]$$

算法中与 Environment Model 强相关的部分是 ${\pi }_{k+1}$$\pi_{k+1}$，也就是 Step 2，以 Elementwise Form 表达

为什么强相关的是 ${\pi }_{k+1}$$\pi_{k+1}$ 而非 ${\pi }_k$$\pi_k$？

1. ${\pi }_k$$\pi_k$ 在算法的第一轮 Iteration 中，来自直接给定的 Initial Guess ${\pi }_0$$\pi_0$

2. 在第二轮及以后的 Iteration 中，${\pi }_k$$\pi_k$ 则直接来自于上一轮 Iteration 得到的 ${\pi }_{k+1}$$\pi_{k+1}$

包含 Environment Model 的核心组件为 Action Value $q_{{\pi }_k}(s_t,a_t)$$q_{\pi_k}(s_t,a_t)$，它有两种表达方式

要让 Policy Iteration 变得 Model-Free，那就得抛弃 Elementwise Form，直接通过 Mean Estimation 获取 Action Value

这种估计 Action Value 的方法，其名曰 Monte-Carlo Estimation

 

1.2.1 Monte-Carlo Estimation

1. 已知 ${\pi }_k$$\pi_k$

2. 对于一组 $(s,a)$$(s,a)$，依据 ${\pi }_k$$\pi_k$ 找到所有可能的 Episode 的 Return，$g_{{\pi }_k}(s,a)$$g_{\pi_k}(s,a)$

   $g_{{\pi }_k}(s,a)$$g_{\pi_k}(s,a)$ 是对 $G_t$$G_t$ 的采样，采样机制如下

   1. 对于 State $s$$s$ 的每个 Action $a_i$$a_i$ 都要采样 $q_{{\pi }_k}(s,a_i)$$q_{\pi_k}(s,a_i)$，这样才能比较 Action Value 以选择 Optimal Policy

      并非只采样当前 Policy 规定下，在 State $s$$s$ 时必须或可能采取的某些 Action

   2. 到了一组 $(s,a_i)$$(s,a_i)$ 的下一个 State 时才开始完全按照 Policy 走

   3. 所以，如果

      • Policy AND Environment Model All Deterministic $⟶$$\longrightarrow$ 一组 $(s,a_i)$$(s,a_i)$ 只可能产生一个 Episode

      • Policy OR Environment Model Not Deterministic $⟶$$\longrightarrow$ 一组 $(s,a_i)$$(s,a_i)$ 可能产生多个 Episode

3. 假设该组 $(s,a)$$(s,a)$ 收集了 $N$$N$ 个 Return，$\{g_{{\pi }_k}^{(i)}(s,a)\}$$\{g_{\pi_k}^{(i)}(s,a)\}$ with $i=1,2,...,N$$i = 1,2,...,N$，则该组 $(s,a)$$(s,a)$ Action Value 为

   $$\begin{array}{rl}{q}_{{\pi }_k}(s,a)& =\mathbb{E}[G_t|S_t=s,A_t=a]\\ \\ & =\frac{1}{N}\sum _{i=1}^N{g}_{{\pi }_k}^{(i)}(s,a)\end{array}$$

"没 model 的时候得有 Data，没 Data 的时候得有 Model"

顺带一提，Data 在概率论里叫 Sample，在 RL 里叫 Experience

 

1.2.2 Pseudo Code

与 Policy Iteration 差别不大，不过现在只涉及 Action Value 的问题了

所以直接放弃原本 PE 中求 State Value 的内容，替换为穷举 Episode 直接估计 Action Value

因为这种算法是基于 Policy Iteration 的，所以只要 Episode 的数量够多，Convergence is guaranteed

然而这种算法效率极低，并不实用

 

1.2.3 Example

在下图的场景中

• 黄色的 $s_2$$s_2$ 为禁区，蓝色的 $s_4$$s_4$ 为目的地

• Reward 设置

  • $r_{forbid}=r_{bound}=-1$$r_{forbid} = r_{bound} = -1$

  • $r_{target}=1$$r_{target} = 1$

• Discount Rate 设置 $\gamma =0.9$$\gamma = 0.9$

• Action Space 设置 $a_1,a_2,a_3,a_4,a_5=$$a_1,a_2,a_3,a_4,a_5 =$ 上, 右, 下, 左, 不动

• 绿色标识为 Initial Guess Policy ${\pi }_0$$\pi_0$

• Policy & Environment Models Deterministic

现在演算 Monte-Carlo Policy Iteration

• At $k=0$$k=0$ - Policy Evaluation

  一共 9 个 State，每个 State 的 Action Space 中有 5 个动作，所以一共需要计算 $9\times 5=45$$9\times5 = 45$ Episodes

  此处只演示 State $s_1$$s_1$ 的 5 个 Episode

  $$\begin{array}{rl}(s_1,a_1)\text{ Episode:}& s_1\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }\cdots \\ & q_{{\pi }_0}(s_1,a_1)=-1+\gamma (-1)+{\gamma }^2(-1)+\cdots \\ \\ (s_1,a_2)\text{ Episode:}& s_1\stackrel{a_2}{\to }{s}_2\stackrel{a_3}{\to }{s}_5\stackrel{a_3}{\to }\cdots \\ & q_{{\pi }_0}(s_1,a_2)=0+\gamma (0)+{\gamma }^2(0)+{\gamma }^3(1)+{\gamma }^4(1)+\cdots \\ \\ (s_1,a_3)\text{ Episode:}& s_1\stackrel{a_3}{\to }{s}_4\stackrel{a_2}{\to }{s}_5\stackrel{a_3}{\to }\cdots \\ & q_{{\pi }_0}(s_1,a_3)=0+\gamma (0)+{\gamma }^2(0)+{\gamma }^3(1)+{\gamma }^4(1)+\cdots \\ \\ (s_1,a_4)\text{ Episode:}& s_1\stackrel{a_4}{\to }{s}_1\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }\cdots \\ & q_{{\pi }_0}(s_1,a_4)=-1+\gamma (-1)+{\gamma }^2(-1)+\cdots \\ \\ (s_1,a_5)\text{ Episode:}& s_1\stackrel{a_5}{\to }{s}_1\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }\cdots \\ & q_{{\pi }_0}(s_1,a_5)=0+\gamma (-1)+{\gamma }^2(-1)+\cdots \end{array}$$

• At $k=0$$k=0$ - Policy Improvement

  肉眼观察可见最大的 Action Value 为

  $$(s_1,a_2)=(s_1,a_3)$$

  所以可以在 Policy ${\pi }_1$$\pi_1$ 中做如下改进

  $${\pi }_1(a_2|s_1)=1\text{or}{\pi }_1(a_3|s_1)=1$$

 

 

 

2. Monte-Carlo Exploring Starts

这个是真算法了

 

2.1 Data Efficiency

在 1.2.2 中有言道：MCPolicyIteration 效率极低——这是在说它的 Data Efficiency 很低

一个 Episode 中有很多 Sub-Episode，复用能省略重复探索的时间，然而 MCPolicyIteration 并没有没有用，就很糟糕（

如上图红框所示，Episode 中的一个 State-Action Pair 被称为 Visit，有如下几种类型

• Initial-Start Visit Method

  MCPolicyIteration 使用 Data 的方式

  每个 Episode 的检索都是完全独立的，内部的 Sub-Episode 不会被复用，非常笨拙

  

• First Visit Method

  同一个 Episode 中遇到

  • 不同的 Visit，开一个 Sub-Episode 复用

  • 同一个 Visit，不会被当成 Sub-Episode 复用

  

• Every Visit Method

  同一个 Episode 中只要遇到 Visit 就开一个 Sub-Episode 复用

  

 

 

2.2 Policy Update Efficiency

一共就两种方式

• Method 1

  收集从一个 State-Action Pair 出发的所有 Episode 的 Return，得到 Expectation，然后估计 Action Value

• Method 2

  用单一一个 Episode 的 Return 直接估计 Action Value，improve policy episode-by-episode

  有点 Stochastic Gradient Descent 的感觉，不精确，很狂野，但实际效果不错

 

 

2.3 Pseudo Code

算法名称叫 Monte-Carlo Exploring Start (Every Visit Method 版)

Exploring Start 的意思是，确保每对 $(s_i,a_j)$$(s_i,a_j)$ 都能被探索到

因为当前的方法无法确保每对 $(s_i,a_j)$$(s_i,a_j)$ 都能在从别的 State-Action Pair 出发的 Episode 中被 Visit 到

即，无法 guarantee 一定有机会被复用

这个算法印证了为什么说 “动态规划是从后往前规划的“

 

 

 

3. Monte-Carlo $ϵ$$\epsilon$-Greedy

如果你嫌 Monte-Carlo Exploring Starts 的 "Exploring Starts" 条件麻烦

那就可以用这个基于 Soft Policy 的算法，让 Policy 从 Deterministic 变得 Stochastic

• Soft Policy = Probability to take any Action is Positive

本算法使用的 Soft Policy 叫 $ϵ$$\epsilon$-Greedy

 

 

3.1 $ϵ$$\epsilon$-Greedy Policy

where

• $ϵ\in [0,1]$$\epsilon \in [0,1]$

• $|\mathcal{A}(s_t)|⟶$$\abs{\mathcal{A}(s_t)}\longrightarrow$ Number of Actions for $s_t$$s_t$

特性如下

• Greedy Action 的概率 $\ge$$\geq$ Other Actions 的概率

• 可以调节 "Exploration" 与 "Exploitation" 的平衡

  • 完全 Exploitation $⟶ϵ=0$$\longrightarrow\epsilon = 0$

    此时是纯 Exploitation，和一般的 Greedy Policy 没有区别

    看起来比较 “短视”

    $$\begin{array}{rl}1-ϵ\cdot \frac{|\mathcal{A}(s_t)|-1}{|\mathcal{A}(s_t)|}& =1\\ ϵ\cdot \frac{1}{|\mathcal{A}(s_t)|}& =0\end{array}$$

  • 完全 Exploration $⟶ϵ=1$$\longrightarrow\epsilon = 1$

    此时 Greedy Action 与 Other Actions 概率相等，显然更加 "Exploration"

    看起来比较 “远视”，但不如说是完全不带判断的 “盲视”

    $$\begin{array}{rl}1-ϵ\cdot \frac{|\mathcal{A}(s_t)|-1}{|\mathcal{A}(s_t)|}& =\frac{1}{|\mathcal{A}(s_t)|}\\ ϵ\cdot \frac{1}{|\mathcal{A}(s_t)|}& =\frac{1}{|\mathcal{A}(s_t)|}\end{array}$$

  • 二者的平衡 $⟶0<ϵ<1$$\longrightarrow 0<\epsilon<1$

与纯粹的 Greedy Policy 相比，$ϵ$$\epsilon$-Greedy Policy 能有更强的探索性，以此完全摆脱 Exploring Starts

但缺点是牺牲了 Optimality

(see 3.3.1, 3.3.2)

• [ ! WARNING ! ]

  $ϵ$$\epsilon$ 取值不能太大！！！

  你可以一开始取比较大的值，然后慢慢衰减到 $ϵ=0$$\epsilon = 0$，但是不能一直取太大的值！！！

  (see 3.3.1, 3.3.2)

 

 

3.2 Pseudo Code

well，只需要把 2.3 的 Exploring Start 的 Pseudo Code 中 Policy Improvement 的部分改为

哦 $ϵ$$\epsilon$ 需要放到 parameter list 里

（真的有人会忘记这种事吗？蠢爆了好吧，但我觉得还是提醒一下吧）

 

 

3.3 Examples & Properties

3.3.1 Exploration & Exploitation

 

3.3.2 Optimality

给定一个固定的 Policy，代入不同取值的 $ϵ$$\epsilon$ 后得到的 Policy 和 State Value

虽然所有其他 Policy 都能与 Greedy 状态下（$ϵ=0$$\epsilon = 0$）的 Policy 保持一致，即概率最大的动作是一致的

但是 State Value 的变化说明，更大的 $ϵ$$\epsilon$ 会导致Policy 的 Optimality 会下降

当 $ϵ=0.5$$\epsilon=0.5$ 的时候，Target 的 State Value 已经是负数了

原因在于 Target 附近全是 Forbidden Area，而探索性的提升会让处于 Target 位置的 Agent 有更高的概率踩到 Forbidden Area

 

3.3.3 Consistency

在不同 $ϵ$$\epsilon$ 取值下获得的对应 $ϵ$$\epsilon$-Greedy Policy

$ϵ$$\epsilon$ 取值越大，与 Greedy 状态下（$ϵ=0$$\epsilon = 0$）的 Policy 的差距就越大，$ϵ=0.5$$\epsilon = 0.5$ 的时候已经完全崩坏了