强化学习的数学原理 · Chap5

[TOC]

https://www.bilibili.com/video/BV1sd4y167NS

Model

model-based：概率模型已知
model-free：概率模型未知

抛硬币模型：

model-based: 基于0.5的概率直接把期望、分布全部都算出来

model-free: 重复采样多次，以样本均值作为期望

MC Basic

最简单的基于蒙特卡洛的强化学习算法

本质上是转化Policy Iteration为Model-Free

其中Policy Iteration中的一步：

$$ \pi_{k+1}=\arg \max_\pi \sum_a \pi(a|s){\color{red}q_{\pi_k}(s,a)}, \quad s\in \mathcal{S} $$

其中这一步的action value可以表示为：

$$ \begin{split} q_{\pi_k}(s,a) &=\sum_{r}p(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_{\pi_k}(s') \\ &= \mathbb{E}\left[ G_t \mid S_t = s, A_t = a\right] \end{split} $$

第一个公式是依赖于模型$p$的，而第二个公式就可以通过采样去近似

基于状态$s$采取动作$a$，依据策略$\pi_k$，生成一个episode，记return为$g(s,a)$

则我们可以将$g(s,a)$看作一个$G_t$的采样

因此我们大量重复采样，得到序列$\left { g^{(j)}(s,a)\right }$

则可以近似：

$$ q_{\pi_k}(s,a) = \mathbb{E}\left [ G_t\mid S_t = s,A_t = a \right] \approx\frac{1}{N}\sum_jg^{(j)}(s,a) $$

没有模型的时候，你最好有数据（统计学叫Sample，强化学习叫Experience）

因此整个算法的流程：

从$\pi_0$出发，迭代到$k$

Step1：Policy Evaluation
- 本质上就是希望得到所有的$q$
- 对每一个$(s,a)$对，生成大量的episodes
- 计算均值，作为$q_{\pi_k}(s,a)$
Step2：Policy Improvement
- 贪心策略：$\pi_{k+1}$基于最大的$q$去选择
- 这里和model-based是一样的

因此我们可以直接通过这个方法得到$\pi$，而不是state value

但是算法效率比较差后续有优化

甚至这个算法也只是一个idea 没有具体的名字

是作者取的

Eposide Length是重要的、需要够长：采样的步数太短，会导致均值不够准确

MC Exploring Starts

MC Basic的数据采样效率非常低

需要对每一个$(s,a)$对进行大量采样

$$ s_1,a_1 \to s_2,a_5 \to {\color{red}s_1,a_2} \to s_2,a_3 \to a_5,a_1 \to ... $$

在MC Basic中，这一条episode只会用来计算最开始的$s_1,a_1$的action value

但其实中间的$s,a$对是可以当成一次采样的

我们可以从两个角度开始优化：

复用：我们希望一整条episode都能被利用，有两个方法
- First Visit：只采样每个episode中每个$(s,a)$第一次出现
  - 样本独立
- Every Visit：每次出现$(s,a)$都当成一次采样
  - 样本更多，但是相关性会变强
即时更新
- Basic：跑完所有的episode，统一做一次Policy Improvement
- 但可以用单个 episode的return来立即更新action value
  - 本质上可以看作是Truncated Policy Improvement

算法流程：

初始化策略$\pi_0$

“Exploring starts” 意思是：所有 (s, a) 都有可能成为 episode 的起点。

随机选择一个起点$s_0,a_0$——Exploring Starts
- 需要保证所有的状态都是非0的概率能作为起点
按照当前策略$\pi$生成一个episode
反向更新（相当于后缀和，方便计算return）
- 每个$s,a$会维护一个列表
- First Visit：如果当前$s,a$对是$(s_0,a_0,s_1,a_1,s_2,a_2,…)$中没有出现过的（第一次出现）
  - 将当前的return加入到对应列表
  - 计算列表中的均值，更新$q(s,a)$
  - 根据$q$实时更新$\pi$

MC Epsilon Greedy

但现实中Exploring Starts难以实现，有时候我们很难自由选择一个起点开始采样

你总不能每次采样一个起点，就搬动机器人过去一次吧

前两个算法之所以要对不同的$s,a$做采样，本质原因是：

$$ \pi(a|s) = \begin{cases} 1 & \text{ if } a=a^*(s) \\ 0 & \text{ if } a\neq a^*(s) \end{cases} $$

我们的策略是greedy的，因此会导致从真实起点出发，非常多的状态无法被覆盖到

因此无法针对单一起点做反复采样

所以我们可以考虑引入一点随机性：

$$ \pi(a|s) = \begin{cases} 1-\frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1) & \text{ for the greedy action }\\ \frac{\varepsilon}{|\mathcal{A}(s)|} & \text{ for the other }|\mathcal{A}(s)|-1 \text{ actions} \end{cases} \\ \text{where } \varepsilon \in [0,1] \text{ and } |\mathcal{A}(s)| \text{ is the number of actions.} $$

假设有5个action，其中greedy action是$a_0$，定义$\varepsilon=0.2$

action	$a_0$	$a_1$	$a_2$	$a_3$	$a_4$
probability	0.84	0.04	0.04	0.04	0.04

同时，我们可以保证任意时刻greedy action的概率都是最大的

$\varepsilon=1$时，所有action概率相同

$$ 1-\frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1)=1-\varepsilon + \frac{\varepsilon}{|\mathcal{A}(s)|} \geq \frac{\varepsilon}{|\mathcal{A}(s)|} $$

算法维持了一个平衡：

探索性：越大的$\varepsilon$带来越强的探索性，只要episode足够长，就能探索所有状态
最优性：越大的$\varepsilon$带来的策略自然是更差的，因为每一步走向greedy的概率变低了

可以动态调整，一开始大，逐渐变小

算法流程：

去掉了Exploring Starts的条件：需要保证所有的状态都是非0的概率能作为起点
修改策略更新的分布

$$ \pi(a|s) = \begin{cases} 1-\frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1) & a=a^*(s)\\ \frac{\varepsilon}{|\mathcal{A}(s)|} & a\neq a^*(s) \end{cases} \\ $$

其他都是和前文算法一致