《Reinforcement Learning》 读书笔记 5：蒙特卡洛（Monte Carlo Methods）

《Reinforcement Learning: An Introduction》 读书笔记 - 目录

问题

前面两章都假设我们已知MDP的分布p(s′,r|s,a)$p(s^{\prime },r|s,a)$（model），但有时这一点难以做到（第2章的多臂老虎机问题是一个特殊的例子），或者说这种Markov假设可能是不合理的，那么我们只能从真实/模拟环境中去获取这些知识

• PS: 以下只考虑episodic task

一些概念

Monte Carlo（MC）

• 用样本分布代替总体分布，估计一些总体分布的参数
• 简单来说，就是假设想知道一些真实分布的一些信息，比如期望，或函数的期望，如果我们不知道真实分布的表达式，或者知道，但是很难推导求解，就需要模拟出一批样本，再做平均，虽然有误差，可只样本量足够大，根据大数定律还是收敛的

Importance Sampling

• 问题：假设我们要求分布f$f$下x$x$的期望，但是我们只是已知/或能模拟出另一个分布g$g$的情况，该怎么办？
• 方法：Ef(x)=∫xf(x)g(x)g(x)dx=Eg(f(x)g(x)x)${\mathbb{E}}_f(x)=\int \frac{xf(x)}{g(x)}g(x)dx={\mathbb{E}}_g(\frac{f(x)}{g(x)}x)$
  
  • 也就是说，只要求f(x)g(x)x$\frac{f(x)}{g(x)}x$在分布g$g$下的期望就可以了，这点可以用MC来做到
  • 这里，我们把ρ=f(x)g(x)$\rho =\frac{f(x)}{g(x)}$ 叫做importance-sampling ratio
    
    • f(x)$f(x)$和g(x)$g(x)$的表达式不一定要是已知的，只要知道比值就可以

on/off-policy

• on-policy
  
  • 直接评价或优化目标策略
  • 假设目标策略为π$\pi$，则通过model或观测/模拟直接计算其value function，或优化它
• off-policy
  
  • 两个策略
    
    • 行为策略(behavior policy) b$b$，已知或观察/模拟的策略
    • 目标策略(target policy) π$\pi$，待评估的策略
  • 目标：通过 b$b$ 评估/优化 π$\pi$
  • 当π=b$\pi =b$ 时，on/off policy一致

Monte Carlo Control

• 其实就是用MC方法替换了替换了原来的policy evaluation方法

MC估算value function（on-policy）

两种方法

• first-visit MC
  
  • 对于一个episode，只考虑第一次进入到某种state(-action)后的return
  • 各episode之间iid，相对误差→O(1/n−−−√)$\to O(\sqrt{1/n})$
  • 举例，计算vπ$v_{\pi }$
    
    
    • 注意：其中的内部循环t是倒序的（考虑第2章计算Gt$G_t$时的递推式），这里还可以加上折扣因子γ$\gamma$
• every-visit MC
  
  • 考虑episode中每次进入到state(-action)后的return
  • 虽然不独立，但是误差仍然→O(1/n−−−√)$\to O(\sqrt{1/n})$

action-value function

• 问题：如果采用某种确定性的策略，则可能会有很多state-action在模拟的过程不会碰到（exploitation only），导致样本量为0
• 两种思路
  
  • exploring start
    
    • 方法：在初始化episode的时候，随机一点，允许exploration
      
    • 缺点：麻烦，不能保证覆盖全面
  • ε$\epsilon$-greedy
    
    • ε$\epsilon$-soft：区别于确定性策略的绝对，要求所有π(a|s)≥ε|A(s)|$\pi (a|s)\ge \frac{\epsilon }{|\mathcal{A}(s)|}$
    • 方法：类似第2章中的方法
      
      • 以p=1−ε+ε|A(s)|$p=1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s)|}$采用原先确定性的action(exploitation)
      • 以p=ε|A(s)|$p=\frac{\epsilon }{|\mathcal{A}(s)|}$选取剩下的策略（exploration）
      • 
    • 优点：是所有ε$\epsilon$-soft策略中最优的

Importance Sampling 估算value function (off-policy)

state-value function

• 基本原理
  
  1. 策略π$\pi$的一个episode中的一个子序列t→T$t\to T$的概率
     
     Pπ(At,St+1,At+1,…,ST|St)=∏k=tT−1π(Ak+1|Sk)p(Sk+1|Sk,Ak+1)$$\begin{gathered} P_{\pi }(A_t,S_{t+1},A_{t+1},\dots ,S_T|S_t) \\ =\prod _{k=t}^{T-1}\pi (A_{k+1}|S_k)p(S_{k+1}|S_k,A_{k+1}) \end{gathered}$$
  2. 同理，对b$b$也是一样，那么
     
     ρt=∏T−1k=tπ(Ak+1|Sk)p(Sk+1|Sk,Ak+1)∏T−1k=tb(Ak+1|Sk)p(Sk+1|Sk,Ak+1)=∏T−1k=tπ(Ak+1|Sk)∏T−1k=tb(Ak+1|Sk)$${\rho }_t=\frac{\prod _{k=t}^{T-1}\pi (A_{k+1}|S_k)p(S_{k+1}|S_k,A_{k+1})}{\prod _{k=t}^{T-1}b(A_{k+1}|S_k)p(S_{k+1}|S_k,A_{k+1})}=\frac{\prod _{k=t}^{T-1}\pi (A_{k+1}|S_k)}{\prod _{k=t}^{T-1}b(A_{k+1}|S_k)}$$
     
     也就是说，只需要知道策略，与model无关
  3. vπ(St)=Eb[ρtGt|St]$v_{\pi }(S_t)={\mathbb{E}}_b[{\rho }_t{G}_t|S_t]$
• 两种方法
  
  • 简单平均(ordinary importance sampling)
    
    • V(s)=∑t∈T(s)ρtGt|T(s)|$V(s)=\frac{\sum _{t\in \mathcal{T}(s)}{\rho }_t{G}_t}{|\mathcal{T}(s)|}$
    • 根据上面的原理得到的 最直观的实现
    • 优点：无偏
    • 缺点：方差可能很大，甚至无限大
      
  • 加权平均(weighted importance sampling)(一般更优)
    
    • V(s)=∑t∈T(s)ρtGt∑t∈T(s)ρt$V(s)=\frac{\sum _{t\in \mathcal{T}(s)}{\rho }_t{G}_t}{\sum _{t\in \mathcal{T}(s)}{\rho }_t}$
    • 优点：方差较小
    • 缺点：有偏（考虑只有一个样本情况，即V(s)=Gt$V(s)=G_t$）（但是渐近无偏）
  • 说明
    
    • 这里把所有episode串联起来，所以t是全局唯一的（只是一种简单处理的表示方法）
    • T(s)$\mathcal{T}(s)$表示状态s被访问的t集合（取决于first-visist还是every-visit）
    • ρt${\rho }_t$表示从t到该episode的termination state之间的ratio
• 实现例子
  这里都用了weighted方法，并用了迭代式减少内存开销
  
  • 计算qπ$q_{\pi }$
    
    
    • 最后内循环中的退出条件，仅当π(At|St)=0$\pi (A_t|S_t)=0$时成立，即出现了b$b$中存在，但π$\pi$中不会存在的策略，因为是倒序迭代，所以继续往下是没有意义的（如果继续迭代下去，相当于把不可能存在的样本序列加进去）
  • control
    
    
    • 最后内循环中的退出条件理由基本同上，因为这里假设π$\pi$是确定性策略
      也就是说，π(At|St)=1$\pi (A_t|S_t)=1$ （Exercise 5.9）