蒙特卡洛方法
动态规划的局限
从以上可以看出动态规划具有一定的局限性：
- 必须已知状态转移概率 $p$
- 每次更新一个状态的价值需要遍历计算后续所有的状态价值，复杂度较高
因此，接下来引入蒙特卡罗方法解决策略评估和策略提升问题。
蒙特卡洛方法简介
- 蒙特卡洛是指一类随机算法的统称，核心思想是：用事件发生的“频率”来替代事件发生的“概率”-对无法准确知道的概率通过采样得到频率代替概率。
- 特点：
- 可通过随机采样获得近似结果
- 采样次数越多，估计结果越准确
- 强化学习中的蒙特卡洛：直接从采样的轨迹序列中学习，基于采样得到的轨迹，计算某个状态在多条轨迹下的平均价值，该值近似认为是该状态的价值。
1. 蒙特卡洛预测
- 轨迹序列中出现重复状态
首次访问MC：所有首次访问的回报的平均值估计。
每次访问MC：所有访问回报的平均值。
问题：确定性策略会使得一些状态永远无法访问到
例5.1 二十一点
游戏规则：
扑克牌点数之和不超过21的情况下越大越好，(J,Q,K)点数为10，A既可以看作1也可以看作11。 开局会给玩家和庄家(一张面朝上)发两张牌，此时直接获得21点（10+A）成为天和的玩家获胜，若庄家也是天和则平局； 若不是天和，则玩家可以主动要牌，直至停牌(主动停止)或者爆牌（>21）。爆牌则直接输掉比赛。 停牌，则轮到庄家行动，庄家一直要牌知道点数>=17则停牌，最后看双方点数谁更靠近21点 马尔可夫决策过程： 每一句为一个episode；胜负平奖励为1，-1，0；每局游戏进行中的收益为0，折扣为1； 每次去除的牌都会放回牌堆。若玩家有A且可视为11不爆牌，则当前A可用； 此时，这张牌总会被视为11，因为若取1则当前点数总和<=11，此时玩家可以直接要牌； 所以玩家的选座只依赖于三个变量：手牌总和(12-21),庄家显示的牌(A-10),是否有可用的A，共计200个状态。
练习5.1-5.2
5.1 1. 因为当前的策略是玩家直到点数>=20才停牌，那么也就意味着玩家采用的是相对激进的策略，也就导致了20和21两行的价值要比前面的部分要高；由于庄家执行的是点数>=17停牌，那么此时玩家有更高的概率取得游戏的胜利。 2. 左侧一列表示当前庄主展示了一张A，说明当前庄家能够有更多的选择，并有更大的概率获胜。 3. 上方图中A表示可用，那么也就意味着A既可以是1也可以是11，在相同条件下会比下方图有更大的概率获胜。 5.2
不会，因为在该游戏中，一个中episode不会有相同的状态。首次访问和每次访问也就没有区别。
2. 动作价值的蒙特卡洛估计
一般情况下，我们无法确定环境模型，即不知道状态s下动作a所产生的结果。这样一来，动作值函数$q(s,a)$的估计对于策略选择更加直接。
MC估计法
将访问考察对象改为状态-动作二元组，用同样的方法计算所有碰到的（或是第一次碰到的）状态-动作二元组价值函数的平均值作为其估计值。
确定性策略困境&解决
- 概率型策略：次数足够大就能保证一些状态被访问并更新
- 确定性策略：
- 一旦策略固定后只会转移到特定的状态-动作二元组上，此时也就意味着某些状态-动作二元组在当前策略下永远无法被访问到；
- 策略提升需要尽可能多的值函数，从而能够在每个状态的可用动作中选择。
解决办法：
- 试探性出发：每一个状态动作二元组都有一定的概率被选作一个幕的起始点。这个假设能够直接保证每个状态动作都能被访问到，但应用场景很受限制；
- ϵ贪心和UCB(随机策略)：在每次策略控制阶段，都设置一定概率进行随机选择。基于这一类的策略也被称为同轨策略；
- 重要度采样：重要度采样是一种在给定来自其他分布的样本条件下，估计某种分布的期望的通用方法。
练习5.3
3. 蒙特卡洛控制
蒙特卡洛估计解决控制问题，即近似最优的策略。
策略评估与改进的迭代过程：
策略改进方法：在当前价值函数上贪心选择动作，即$\pi(s) \doteq \arg\max_{a} q(s,a)$
基于试探性出发的蒙特卡洛
试探性出发能够解决部分状态动作二元组无法访问的问题，但其也存在另一个问题：一般而言，很多应用领域是不适合随机初始状态的，因此不能够适合所有场景。
练习5.4
2.4节中的内容：
相似改进蒙特卡洛估计：
$\begin{align}
Q_n(S_t,A_t)
&= \frac{1}{n} \sum_{i=1}^{n}G_i(S_t,A_t) \\
&= \frac{1}{n}(G_n(S_t,A_t) + \sum_{i=1}^{n-1}G_i(S_t,A_t))\\
&= \frac{1}{n}(G_n(S_t,A_t) + (n-1) \frac{1}{n-1}\sum_{i=1}^{n-1}G_i(S_t,A_t))\\
&= \frac{1}{n}(G_n(S_t,A_t) + (n-1)Q_{n-1}(S_t,A_t))\\
&= \frac{1}{n}(G_n(S_t,A_t) + nQ_{n-1}(S_t,A_t)- Q_{n-1}(S_t,A_t))\\
&= Q_{n-1}(S_t,A_t) + \frac{1}{n}(G_n(S_t,A_t)-Q_{n-1}(S_t,A_t))
\end{align}$
4. 没有试探性出发假设的蒙特卡洛控制
当某些情况下，很难满足试探性出发的假设，一般性的解决办法就是让智能体持续不断的选择所有可能的动作。同归策略和离轨策略能够保证这一点。
- 同轨策略（On-Policy）：
定义：用于生成采样数据序列的策略和用于实际决策的待评估和改进的策略相同。同轨策略也通常是一种“软性”策略，对于任意的状态与动作的选择概率虽然大于0，但是该策略会逐渐逼近一个确定性策略，如 $\epsilon$-贪心策略等；
- 离轨策略（Off-Policy）：
定义：用于评估或者改进的策略与生成采样的序列的策略是不同的，即生成的数据“离开”了待优化的策略所决策的序列轨迹。
ε-贪心软性策略
ε概率随机选择一个动作$a_t$
1-ε概率选择当前价值最高的动作$\arg\max_{a} Q(S_t,a)$
那么当前价值最高动作被选择的概率 $1 - \epsilon + \frac{\epsilon}{|A|}$
其他动作被选择的概率 $\frac{\epsilon}{|A|}$
软性策略证明
策略提升
收敛证明
5. 基于重要度采样的离轨策略
同轨策略： 不学习最优策略的动作值，而是学习一个接近最优而且仍能进行试探的策略的动作值，因此同轨策略实际只是一种妥协-特殊的离轨策略. 离轨策略：方差大，收敛慢-因为数据来自一个不同的策略
离轨策略的两个条件
离轨策略的主要内容是通过行动策略b去做试探性采样，基于这些采样数据改进目标策略 $\pi$.因此，有如下两个条件
- 目标策略 $\pi$下发生的动作都至少偶尔能在b下发生。即$任意\pi(a|s)>0 ，要求b(a|s)>0$(覆盖假设)
- 重要度采样建立两种不同分布之间的关系。 重要度采样指在给定某个来自其他分布的条件下，估计某种分布的期望值的方法。
重要度采样
- 不同策略的期望
$\begin{align} \mathbb{E}_{x \sim p(x)}[f(x)] &= \int p(x)f(x) dx \\ &= \int \frac{q(x)}{q(x)} p(x)f(x) dx \\ &= \int q(x) \frac{p(x)}{q(x)}f(x)dx \\ &= \mathbb{E}_{x \sim q(x)}[\frac{p(x)}{q(x)}f(x)] \end{align}$
- 重要度采样比
将重要度采样应用于离轨策略学习，对回报值根据其轨迹在目标策略与行动策略中出现的相对概率进行加权，这个相对概率也被称为重要度采样比。
重要度采样比只与两个策略和样本序列数据相关
- 行动策略期望->目标策略期望
- 普通重要度采样
$V(s) = \frac{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}G_t}{|\tau(s)|}$
- 加权重要度采样
$V(s) = \frac{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}G_t}{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}}$
两种重要度采样的不同
- 普通重要度采样
相当于给每一个回报加上了一个收益，从公式上来看普通重要度采样是一个无偏估计（对其求期望就是我们需要找的目标策略）。 然而实际中，由于两个策略生成完全相同的轨迹概率很小，因而就会导致权重变得极大或极小（方差较大），因此就需要非常长的轨迹才能够达到好的评估效果。 也就意味着当前的数据序列能够有效反应目标策略，但其估计值会离观测到的回报值很远。
- 加权重要度采样
则直接将每个时刻的回报权重改为 $\frac{\rho_{t:T(t)-1}}{\sum_{t \in \tau(s)} \rho_{t:T(t)-1}}$，此时权重就不会出现极大极小的情况，致使方差变得很小甚至可以收敛到0。 但相对的通过该公式计算期望得到的是行动策略 $v_b(s)$而不是 $v_{\pi}(s)$,因此此时这个估计又是有偏的。
例子5.5无穷方差
练习5.5-5.8
计算回报：$\sum_{t \in \tau(s)} \rho_{t:T(t)-1} = 10$ 只有一个状态： $\rho_{t:T(t)-1} = 1$ 所以当前采用的是同轨策略： 首次访问：$v_s = 10$,每次访问：$v_s = \frac{1}{10}(10+9+…+1) = 5.5$
- 5.6
- 5.7
因加权重要度采样是有偏估计，一开始需要部分的episode去减小偏置。特别是当重要度采样比较大的时候，此时偏移就会比较大。
针对每次访问型的平方期望
参考资料
书本链接
《强化学习 第2版》.pdf http://incompleteideas.net/book/RLbook2020.pdf https://rl.qiwihui.com/zh_CN/latest/partI/chapter5/monte_carlo_methods.html https://laddie132.github.io/Reinforcement-Learning-Notes/chapter/chapter5.html
参考讲解链接
https://blog.csdn.net/quiet_girl/article/details/105149631 https://zhuanlan.zhihu.com/p/296899775 https://blog.csdn.net/qq_36426650/article/details/105194140 https://blog.csdn.net/weixin_38886470/article/details/121473123 https://zhuanlan.zhihu.com/p/350276990 https://github.com/LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions
Latex 公式表
https://www.cnblogs.com/wuliytTaotao/p/9714070.html https://blog.csdn.net/xovee/article/details/107733398
代码链接
https://github.com/ShangtongZhang/reinforcement-learning-an-introduction https://github.com/PiperLiu/Reinforcement-Learning-practice-zh
增量式实现(Increment Implementation)
增量式蒙特卡洛方法
- 增量式多臂赌博机：对收益（Rewards）进行平均
- 增量式蒙特卡洛方法：对回报（returns）进行平均
- R ----> G
- 对于同轨策略（on-policy）的MC方法：多臂赌博机中用到的增量式方法可以完全移植到MC方法上。
- n对于离轨策略（off-policy）的MC方法:
- 普通重要度采样：先乘上重要度采样比$ρ_{t:T(t)-1}$进行缩放再取平均后适用。
- 加权重要度采样：需要一个不同的增量式算法？
加权重要度采样的离轨策略方法
- [ ] 假设一个回报序列$G_1, G_2,… ,G_(n-1)$，它们始于相同的状态，每一个回报对应一个随机权重$W_i$，估计到的状态价值函数$V_n$可以写为下式，且每得到一个回报都能进行及时的更新。
e.g., $W_i =ρ_{t_i:T(t_i )-1}$
- $V_n$的更新同时也需要对前n个回报对应的权值的累加合$C_n$进行更新，最终形式：在增量式的基础上考虑权重。（$C_0≐0 ， V_1$任意）
离轨MC预测算法（策略评估，估计$Q≈q_π$）
- n同样适用于同轨策略，其目标策略和行动策略相同， b=π，W=1。
- 目标策略，行动策略，增量式实现，回报计算，权重更新。
- 从回合的尾部开始学习。
离轨策略蒙特卡洛控制(Off-policy Monte Carlo Control)
离轨控制方法
- 同轨策略（on-policy）：使用某个策略进行控制的同时也对那个策略的价值进行评估。
- 离轨策略（off-policy）：
- 行动策略：用于生成行动数据。需要对所有可能的动作采样（软性）
- 目标策略：被评估和改善的策略。策略可以是确定性的（如贪心策略）
离轨策略MC控制算法
- 收敛的目标策略π*对应Q得到的贪心策略。
- Q是对$q_π$的估计。
- 行动策略软性：保证每一个(S,A)二元组都有无穷多次回报。
- 目标策略π为贪心策略，是一个确定性策略？
- 问题：假如回合很长？非贪心动作很多？导致学习速度慢。
折扣敏感的重要度采样(Discounting-aware Importance Sampling)
- 上述讨论：离轨方法将回报视为一个单一整体，需要为回报计算重要度采样的权重。
- 回报内部结构：是每个时刻的折后收益之和。
假设情况
- [ ] 一个有100步长的回合，折扣因子γ=0（模拟一种回合很长且折扣因子很小的情况）
- 0时刻的回报：$G_0=R_1$
- 0时刻的重要度采样比：
- 普通重要度采样情况下，0时刻的回报需要使用该时刻的重要度采样比来进行缩放。
- 实际上，只需要第一个因子来衡量，因为在这种情况下的首次收益决定了整个回合的回报，其余因子与回报相互独立且期望值为1，不会改变预期的更新，但这些余下的因子会极大地增加其方差（甚至无限大）。如何避免这种无关的方差？
方法一：折扣敏感的重要度采样
- 本质：把折扣γ∈[0,1)看作回合终止的概率（部分终止的程度）：γ：这一步不终止；1- γ：这一步终止。 $𝐺_0=(1−γ) 𝑅_1+(1−γ)γ(𝑅_1+𝑅_2)+(1−γ) γ^2 (𝑅_1+𝑅_2+𝑅_3)……$
- 平价部分回报（flat partial returns）：“平价”：没有折扣；“部分”：回报不会延续到终止，而是只延续到视界(horizon)h处
- 传统全回报$G_t$可以转化为平价部分回报的总和：
- 对于平价部分回报，使用一种类似截断的重要度采样比来缩放，$\hat{G}_{t:h}$只涉及到h为止的收益，因此只需要使用到h为止的概率值。
- 普通重要度采样估计器：
- 加权重要度采样估计器：
每次决策型重要度采样(Per-decision Importance Sampling)**
方法二：每次决策型重要度采样
- 离轨估计器中的分子求和计算的每一项也是一个求和式：随机重要度采样比随机收益
- 分析第一项：
- 只有第一个因子和最后的收益是相关的，所有其他比率均为期望值为1的独立随机变量：
- 独立随机变量乘积的期望 = 变量期望的乘积，将除了第一个因子的其他因子移出：
- 分析第k项：
- 每次决策性重要度采样最终形式：
- 每次决策型重要度采样：普通重要度采样估计器，使用$\hat{G}_{t}$来计算其相同的无偏期望，以减小估计器的方差
- 每次决策型重要度采样：加权重要度采样估计器，未知，已知的所有为其提出的估计器都不具备统计意义上的一致性，在数据无限时，不会收敛到真实值
