免模型

免模型试错探索，环境信息未知，没有概率可言，熊何时出现做什么，一切都未知。

RL可以应用在完全未知随机的环境，像人类一样，通过尝试不同的路来学习，慢慢了解哪个状态动作会更好。

免模型预测

蒙特卡洛方法

思想

蒙特卡洛思想

核心思想

• 通过多次采样来估计期望值的方法
• 和环境实际交互获取经验(样本/轨迹)，通过所有经验的平均回报来估计价值函数
• 由于环境存在未知性，需要做探索-利用平衡，$ϵ$ 贪婪策略做平衡。

特点

• 不依赖：模型(状态转移/奖励函数)；不依赖：动态规划自举方法
• 基础MC是on-policy的，可通过 重要性采样 变成off-policy。

缺点

• 只适用于有终止状态的马尔可夫决策过程 (MC方法通用问题)
• 依赖每个轨迹的真实回报$G_t$

具体做法

• 给定策略$\pi$，从状态s开始，智能体和环境交互，采样多条轨迹
• 计算每条轨迹的真实回报$G_t$，用所有轨迹的平均回报来估计价值函数

$$\begin{array}{ll}{V}_{\pi }(s)& =E_{\tau \sim \pi }[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots \mid s_t=s]\\ & =E_{\tau \sim \pi }[G_t\mid s_t=s]\\ & \approx \frac{1}{N}\sum _{i=1}^N{G}_t({\tau }_i)\end{array}$$

• 如果估计Q函数，从状态s开始，强制执行动作a，再进行采样即可。

$$Q_{\pi }(s,a)\approx E_{\tau \sim p(\tau )}[G(\tau )\mid {\tau }_{s_0}=s,{\tau }_{a_0}=a]\approx \frac{1}{N}\sum _{i=1}^N{G}_t({\tau }_i)$$

• 有了Q，做贪婪策略，就能做策略改进了。

$${\pi }^{\prime }(s)=\arg \underset{a}{max}{Q}_{\pi }(s,a)$$

经验均值估计价值函数

价值函数估计(经验均值)

• 每回合，若在时间t状态s被访问，则更新总访问数和总回报
  • 总访问数： $N(s)=N(s)+1$
  • 总回报：$S(s)=S(s)+G_t$
• 通过回报平均，来估计状态s的价值：$V(s)=S(s)/N(s)$
• 缺点：需拿到所有的轨迹的回报后，才能求平均、更新价值函数

增量更新

增量更新

核心思想

• 做增量计算：新估计值 = 旧估计值 + 学习率 * (目标值 - 旧估计值)，

$$V_{new}(s_t)=V_{old}(s_t)+\alpha \cdot (\underset{\mathrm{目}\mathrm{标}\mathrm{值}-\mathrm{估}\mathrm{计}\mathrm{值}}{\underbrace{G_t-V_{old}(s_t)}})$$$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{MC\mathrm{误}\mathrm{差}}{\underbrace{G_t-V(s_t)}})$$$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \cdot (G_t-Q(s_t,a_t))$$

• 蒙特卡洛误差
  • 误差项= 轨迹真实回报 - 期望回报，希望估计回报逼近真实回报
  • 如果$\delta >0$，说明估计值偏低；如果$\delta <0$，说明估计值偏高，需要调整。

$$\delta =G_t-V(s_t)$$

• 学习率$\alpha$

  • 如果较大(接近1)，更新比较激进，大幅朝着新回报值$G_t$靠拢

  • 如果较小，更新会比较保守。

优点

• 不用保存所有样本数据，每采样一个新轨迹，就可以更新价值函数，做到回合级更新
• 只更新轨迹上的所有状态，和轨迹无关的不用更新
• 节省资源

缺点

• 需等一个完整回合结束后，才能算出每个状态的真实收益，利用收益去更新价值函数。
• 不适用于持续性任务、步骤很长的回合制任务。

对比动态规划自举更新

• 用上一时刻的V来更新当前时刻的V (贝尔曼期望备份)

$$V_{k+1}(s)=\sum _{a\in A}\pi (a\mid s)(R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_k(s^{\prime }))$$

MC vs DP

MC vs DP

环境模型

• DP：需已知环境模型(状态转移概率和奖励函数)
• MC：无需完整环境模型，只需通过环境交互来收集经验即可

策略更新

• DP：使用自举，通过贝尔曼方程迭代更新。
  • 用价值函数估计值来更新价值函数，用策略评估值来更新策略。
• MC：使用采样，通过轨迹回报来更新策略。

更新方式

• DP：全局更新，需更新所有可能状态和动作。
• MC：局部更新，只更新轨迹上的状态。通过一个经验的回报，就能做更新。

计算量

• DP：计算量大。需计算所有可能的动作和状态，空间很大时，难以计算，非常慢。
• MC：计算量小，只需更新轨迹上的状态动作即可。

适用场景

• DP：状态空间小、模型已知
• MC：状态空间大、模型未知

收敛性

• DP：保证收敛到最优解
• MC：可能需要更多迭代次数才能收敛，受到样本随机性影响。

动态规划需更新所有状态来求期望：

蒙特卡洛只更新轨迹线上的状态：

时序差分方法

一步时序差分

时序差分方法

背景

• MC需采样整个回合才能更新，TD只需采样1步就可以更新价值函数。
• 单步采样
  • 可以快速适应环境变化。
  • 但只考虑一步的未来，导致自举方法是一种有偏估计。

核心思想

• 使用MC采样 + DP自举 估计 轨迹回报。

  • 用V函数的自举估计值来代替MC中的真实轨迹回报$G_t$

• 无需等待轨迹结束，在每一步都可更新价值函数

一步时序差分TD(0)

• 采样1步$r_{t+1}$，自举估计出轨迹回报作为目标值，来更新价值函数
  • 自举：用1个估计值，来更新另1个估计值

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{\mathrm{时}\mathrm{序}\mathrm{差}\mathrm{分}\mathrm{目}\mathrm{标}，\mathrm{采}\mathrm{样}1\mathrm{步}}{\underbrace{r_{t+1}+\gamma V(s_{t+1})}}-\underset{\mathrm{估}\mathrm{计}\mathrm{值}}{\underbrace{V(s_t)}})$$

• 类比 增量MC

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{\mathrm{完}\mathrm{全}\mathrm{采}\mathrm{样}}{\underbrace{G_t}}-V(s_t))$$

TD目标和TDError

TD目标和TDError

TD目标 (采样1步+自举估计回报)

• 采样1步：走1步后得到的实际奖励$r_{t+1}$
• 自举估计：用上一轮的$V(s_{t+1})$来估计当前轮的$V(s_t)$
  • 用之前的估计来估计$V(s_{t+1})$

$$G_t\approx V_{\mathrm{目}\mathrm{标}\mathrm{值}}(s_t)\approx r_{t+1}+\gamma \cdot V(s_{t+1})$$

TD error

• 实际走一步看到的回报 $r_{t+1}+\gamma V(s_{t+1})$ 和 先前对当前状态的预测 $V(s_t)$的差距。
  • ${\delta }_t>0$：说明实际情况比预想的要好。
  • 学习$V(s_t)$来逼近 时序差分目标/真实回报
  • $\gamma$：平衡短期奖励和长期奖励，通常在0.95-0.99之间。

$${\delta }_t=r_{t+1}+\gamma V(s_{t+1})-V(s_t)$$

• 类比MC Error

$${\delta }_t=G_t-V(s_t)$$

• TD Error 在A2C中的应用：估计优势函数

TD&MC 方差和偏差

TD 的方差和偏差

TD （近视眼/有偏估计）

• 自举1步，只能看到下1步。可能不准确（偏差大），但比较稳定（方差小）。
• 用下一步状态估计值$V(s_{t+1})$来更新当前状态估计值$V(s_t)$，TD目标本身就是不准确的，这就导致了偏差
• 但TD只依赖下一个状态，每次更新变动比较小，因此方差小

MC （远视眼/无偏估计）

• 完全采样，看到整个回合。所以比较准确（偏差小），但经常出现波动（方差大）。
• MC用实际真实回报，所以是无偏的；
• 但需等待整个回合结束，回报是多个随机事件叠加结果，因此MC更新目标波动大，即方差比较大。

TDError 优势偏差方差问题

为什么 TD Error 估计优势 是有偏的

0. 优势函数公式

$$A_{\pi }(s_t,a_t)={\delta }_t=\underset{TD\mathrm{误}\mathrm{差}}{\underbrace{r_{t+1}+\gamma V_{\pi }(s_{t+1})-V_{\pi }(s_t)}}$$

1. TD Error 有偏估计 问题分析

• 如果$V_{\pi }(s_t)$是无偏的，能准确估计出状态价值
  • 那么TD Error 也是无偏的，能准确估计出优势。
• 但没有如果，现实 $V_{\pi }(s_t)$ 往往很难估计出状态价值
  • $V_{\pi }(s)$ 发生偏差时，无论采样多少次，都无法估算真正的优势函数
  • TDError 一定是有偏的，从而引发系统性偏差。

2. TD Error 高偏差 解决办法

• $V_{\pi }(s)$ 价值函数估计不准，就少信赖它。
• 采样多步回报，多信赖依靠采样实际奖励 $r_t、r_{t+1}、r_{t+2},\cdots$。

3. n步TD 高方差 问题分析

• 由于随机策略及环境转移等内容，所以$r_t、r_{t+1}、r_{t+2},\cdots$是 随机变量。
• n步采样、相比之前单步采样，方差更大。

$$Var(r_t+r_{t+1}+r_{t+2}+\cdots )>Var(r_t)$$

4. n步 TD 高方差 解决方法

• 既不完全信任价值函数估计 $V_{\pi }$，又不完全信任采样结果 $r_t、r_{t+1}、r_{t+2},\cdots$。
• 在单步TD 和 完全MC采样 之间做平衡。
• GAE 算法、TD(λ) 算法

TD(λ) / λ-return算法

• 重温强化学习之无模型学习方法：TD(lambda)
• 从强化学习和最优化视角理解资格迹-TD(λ)
• 从对偶视角看强化学习离线λ回报和在线λ回报的关系
• GAE 笔记

指数移动加权平均

• 指数移动加权平均在梯度下降法中的应用
• 指数加权平均

指数移动加权平均

• $v_t$：到第t天的平均值，${\theta }_t$：第t天的温度值，$\beta =0.9$ 是衰减系数

$$v_t=\beta \cdot v_{t-1}+(1-\beta )\cdot {\theta }_t$$$$\begin{array}{ll}& v_0=0\\ & v_1=\beta v_0+(1-\beta ){\theta }_1\\ & v_2=\beta v_1+(1-\beta ){\theta }_2=\beta \underset{v_1}{\underbrace{(\beta v_0+(1-\beta ){\theta }_1)}}+(1-\beta ){\theta }_2\\ & v_3=\beta v_2+(1-\beta ){\theta }_3=\beta \underset{v_2}{\underbrace{(\beta (\beta v_0+(1-\beta ){\theta }_1)+(1-\beta ){\theta }_2)}}+(1-\beta ){\theta }_3\end{array}$$

• 指数加权平均：作为原数据的估计值，可以抚平短期波动，起到平滑作用
• 离当前越近，权值越大；离当前越远，权值越小（指数递减），也有一定权值

$$v_{100}=0.1(0.9{)}^0\cdot {\theta }_{100}+0.1(0.9{)}^1\cdot {\theta }_{99}+0.1(0.9{)}^2\cdot {\theta }_{98}+0.1(0.9{)}^3\cdot {\theta }_{97}+\cdots$$$$v_k=\sum _{i=1}^k(1-\beta )\cdot {\beta }^{k-i}\cdot {\theta }_i=(1-\beta )\sum _{i=1}^k{\beta }^{k-i}\cdot {\theta }_i$$

红色的数据比蓝色的原数据更加平滑，少了很多噪音，并且刻画了原数据的趋势。

在梯度下降法中的应用

• 纵轴方向，平均过程中正负摆动相互抵消，平均值接近于零，摆动变小，学习放慢。
• 横轴方向，因为所有的微分都指向横轴方向，因此平均值仍然较大，向最小值运动更快了。
• 在抵达最小值的路上减少了摆动，加快了训练速度。

n步回报

n步时序差分

背景

• 1步TD：高偏差、低方差。MC：低偏差、高方差。
• 在 单步采样 和 MC 回合采样之间，做折中。

核心思想

• 往前采样n步，再更新，不局限于1步，也不必等到回合结束👍。

  • 比如往前走2步，得到2步的回报，再使用自举来更新价值。
  • 考虑时刻$t\to t+n$的回报。

• 时序差分目标

  • $G_{t:t+n}$：时刻$t$到时刻$t+n$的n步回报。
  • $V(s_{t+n})$：在时刻$t+n$的价值估计。

$$\begin{array}{lll}n=1& \mathrm{TD}(0)& G_{t:t+1}=r_{t+1}+\gamma \cdot V(s_{t+1})\\ n=2& \mathrm{TD}(1)& G_{t:t+2}=r_{t+1}+\gamma \cdot r_{t+2}+{\gamma }^2\cdot V(s_{t+2})\\ & & ⋮\\ n=n& \mathrm{TD}(\mathrm{n})& G_{t:t+n}=r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^{n-1}{r}_{t+n-1}+{\gamma }^{n}V(s_{t+n})\\ & & ⋮\\ n=\mathrm{\infty }& \mathrm{MC}& G_{t:t+\mathrm{\infty }}=r_{t+1}+\gamma \cdot r_{t+2}+{\gamma }^2\cdot r_{t+2}+\cdots +{\gamma }^{T-t-1}\cdot r_T\end{array}$$

• 增量式参数更新

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (G_{t:t+n}-V(s_t))$$$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{n\mathrm{步}TD,\mathrm{采}\mathrm{样}n\mathrm{步},1\mathrm{个}n\mathrm{步}\mathrm{回}\mathrm{报}}{\underbrace{r_{t+1}+\gamma \cdot r_{t+2}+\cdots +{\gamma }^n\cdot V(s_{t+n})}}-V(s_t))$$

n的选择

• 如果固定n
  • n较小，学习速度快，但可能不准确，但方差小
  • n较大，学习速度慢，但可能更准确，但方差大
• 不同的任务可能需要不同的n值
  • 有些状态需要长远回报，有些状态需要较短回报

λ 回报

多个n步估计加权平均

• TD(λ) 多个n步回报加权平均
• GAE 多个n步优势估计加权平均

λ 回报算法

问题背景

• TD 高偏差、低方差；MC 高方差、低偏差。
• n步回报，n难以确定；若固定n，所有状态都使用相同步长的回报，不够灵活。

$$G_{t:t+n}=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots +{\gamma }^{n-1}{r}_{t+n}+{\gamma }^{n}V(s_{t+n})$$

λ回报公式

• λ回报

  • 对多个n步回报估计，做λ权重加权平均，权重衰减，平衡方差和偏差
  • 共有多个n步估计量，步数从1到$\mathrm{\infty }$

• 定义

$$G_t^{\lambda }=(1-\lambda )[{\lambda }^0\cdot G_{t:t+1}+{\lambda }^1\cdot G_{t:t+2}+{\lambda }^2\cdot G_{t:t+3}+{\lambda }^3\cdot G_{t:t+2}+\cdots ]$$

• 推导过程 (分离终止项推导见下文)

$$\begin{array}{ll}{G}_t^{\lambda }& =(1-\lambda )[{\lambda }^0\cdot G_{t:t+1}+{\lambda }^1\cdot G_{t:t+2}+{\lambda }^2\cdot G_{t:t+3}+{\lambda }^3\cdot G_{t:t+2}+\cdots ]\\ & =(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_{t:t+n}\\ & =(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+\underset{\mathrm{分}\mathrm{离}\mathrm{终}\mathrm{止}\mathrm{项}}{\underbrace{{\lambda }^{T-t-1}\cdot G_t}}\end{array}$$

• 推导结果

$$\begin{array}{ll}{G}_t^{\lambda }& =(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_{t:t+n}\end{array}$$$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+{\lambda }^{T-t-1}\cdot G_t$$$$G_t^{\lambda }=\underset{\mathrm{回}\mathrm{合}\mathrm{内}\mathrm{的}n\mathrm{步}\mathrm{回}\mathrm{报}\mathrm{加}\mathrm{权}\mathrm{平}\mathrm{均}}{\underbrace{(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}}}+\underset{n\ge T-t\mathrm{后}\mathrm{面}\mathrm{的}\mathrm{等}\mathrm{效}\mathrm{合}\mathrm{并}\mathrm{项}}{\underbrace{{\lambda }^{T-t-1}\cdot G_t}}$$

参数更新

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (G_t^{\lambda }-V(s_t))$$$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{\lambda \mathrm{回}\mathrm{报}，\mathrm{多}\mathrm{个}n\mathrm{步}\mathrm{回}\mathrm{报},\mathrm{做}\mathrm{平}\mathrm{均}}{\underbrace{(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_{t:t+n}}}-V(s_t))$$

权重的理解

权重 ${\lambda }^{n-1}$ 和 系数$1-\lambda$

• ${\lambda }^{n-1}$：估计量 $G_{t:t+n}$的加权/衰减权重
  • n越大，$G_{t:t+n}$衰减越高

为何需要乘以$1-\lambda$ ？

• 需要保证加权权重为1

• 仅看权重，权重为等比数列 ${\lambda }^0+{\lambda }^1+{\lambda }^3+\cdots {\lambda }^n+\cdots$

  • 等比数列求和公式：$s_n=\frac{a_1(1-q^n)}{1-q}$，首项为$a_1$、比为$q$。

• 权重求和：

  • $\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}=\frac{1-{\lambda }^n}{1-\lambda }$。$|\lambda |<1$ 时，$\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}=\frac{1}{1-\lambda }$
  • 如果不乘$1-\lambda$：权重和为$\frac{1}{1-\lambda }$
  • 如果乘以$1-\lambda$，权重和为1

统一理解

• $(1-\lambda )\cdot {\lambda }^{n-1}$统称为权重、归一化权重，权重和为1。对所有n步回报加权平均。

$$(1-\lambda )\cdot \sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}=(1-\lambda )\cdot \frac{1}{1-\lambda }=1$$

分离终止项的推导

背景

• 无限求和公式 不适用于有限回合。

• 回合在时间T结束 $V(s_T)=0$，时间T以后不再有状态、没有回报。

• 当$t+n\ge T$，即$n>T-t-1$时，回合已经结束，无法通过无限公式计算$G_{t:t+n}$

  • 因为无法获取$r_T,r_{T+1},\cdots$, $s_{T+1},s_{T+2},\cdots$, 无法计算$V(s_{t+n})$
  • 但后面的所有即时奖励回报都为0。
  $$G_{t:t+n}=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots +{\gamma }^{n-1}{r}_{t+n}+{\gamma }^{n}V(s_{t+n})$$

• 意味着，$n\ge T-t$时，$G_{t:t+n}$ 就等同于完整的MC回报 $G_t$

$$G_{t:t+n}=\underset{G_t}{\underbrace{r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots +{\gamma }^{T-t-1}{r}_{T-1}}}+\underset{\mathrm{没}\mathrm{有}\mathrm{奖}\mathrm{励},\mathrm{全}\mathrm{为}0}{\underbrace{{\gamma }^{T-t}{r}_T+\cdots }}=G_t$$$$G_{t:t+n}=G_t,\mathrm{当}n\ge T-t\mathrm{时}$$

分离终止项 ${\lambda }^{T-t-1}\cdot G_t$

• 作用：把无限求和公式分成2部分

$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+{\lambda }^{T-t-1}\cdot G_t$$

• 第1部分：从开始时间t到回合结束时间T之间的所有n步回报

  $$(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}$$

• 第2部分：$n+t$超出结束时间$T$ 后的n步回报平均值，详见下文公式推导过程

  $${\lambda }^{T-t-1}\cdot G_t$$
  • ${\lambda }^{T-t-1}$：推导出来后面的权重
  • $G_t$：推导出来后面的回报求和内容

推导过程

• 推导过程

$$\begin{array}{ll}{G}_t^{\lambda }& =(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+(1-\lambda )\sum _{n=T-t}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_{t:t+n}\\ & =(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+(1-\lambda )\sum _{n=T-t}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_t\\ & =(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+(1-\lambda )G_t\underset{\mathrm{等}\mathrm{比}\mathrm{数}\mathrm{列}\mathrm{求}\mathrm{和}}{\underbrace{\sum _{n=T-t}^{\mathrm{\infty }}{\lambda }^{n-1}}}\\ & =(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+(1-\lambda )G_t\cdot \frac{{\lambda }^{T-t-1}}{1-\lambda }\\ & =(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+{\lambda }^{T-t-1}\cdot G_t\end{array}$$

• 推导结果

$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+{\lambda }^{T-t-1}\cdot G_t$$$$G_t^{\lambda }=\underset{\mathrm{回}\mathrm{合}\mathrm{内}\mathrm{的}n\mathrm{步}\mathrm{回}\mathrm{报}\mathrm{加}\mathrm{权}\mathrm{平}\mathrm{均}}{\underbrace{(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}}}+\underset{n\ge T-t\mathrm{后}\mathrm{面}\mathrm{的}\mathrm{等}\mathrm{效}\mathrm{合}\mathrm{并}\mathrm{项}}{\underbrace{{\lambda }^{T-t-1}\cdot G_t}}$$

TD(λ) 、TD(0)和TD(1)

TD(0)和TD(1)

TD(λ)

• λ 越小：趋近于单步TD，偏差越大，方差越小
• λ 越大：趋近于MC，偏差越小，方差越大

$$G_t^{\lambda }=(1-\lambda )[{\lambda }^0\cdot G_{t:t+1}+{\lambda }^1\cdot G_{t:t+2}+{\lambda }^2\cdot G_{t:t+3}+{\lambda }^3\cdot G_{t:t+2}+\cdots ]$$$$\begin{array}{ll}{G}_t^{\lambda }& =(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_{t:t+n}\end{array}$$$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+{\lambda }^{T-t-1}\cdot G_t$$

TD(0)

• $\lambda =0$，完全衰减，退化为单步TD回报。

$$G_t^0=(1-0)[1\cdot G_{t:t+1}+0\cdot G_{t:t+2}+0\cdot G_{t:t+3}+\cdots ]=G_{t:t+1}$$

TD(1)

• $\lambda =1$，完全不衰减， 退化为完整MC回报
• ${\lambda }^{n-1}=1$会导致无穷级数发散，不能直接通过$(1-\lambda )=0$ 去乘积计算
• 需用分离终止项公式

$$G_t^1=(1-1)\sum _{n=1}^{T-t-1}{1}^{n-1}\cdot G_{t:t+n}+1^{T-t-1}\cdot G_t=G_t$$

TD(λ) 价值函数更新

TD(λ) 价值函数更新

直接使用λ回报替换TD目标来更新Q函数 (表格法)

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \cdot (G_t^{\lambda }-Q(s_t,a_t))$$

函数参数法

• 用神经网络来近似价值函数，权重为$w$

$$w\leftarrow w+\alpha \cdot (G_t^{\lambda }-Q_w(s_t,a_t))\cdot {\mathrm{\nabla }}_w{Q}_w(s_t,a_t)$$

• ${\mathrm{\nabla }}_w{Q}_w(s_t,a_t)$：价值函数对权重$w$的梯度。

资格迹

资格迹

背景

• 在实际运算中，$\lambda$回报需存储所有历史信息。工程复杂、内存消耗高、不适合在线学习决策等。
• 引入资格迹(Eligibility Traces)，高效计算λ回报的一种技巧。

资格迹

• 资格迹作用
  • 记录了过去回合中，哪些状态被访问过，以及对学习结果影响程度。
  • λ回报的复杂计算 变成 更简单、增量式的更新方式，避免大量重复计算
• $z_t$表示t时刻的资格迹，一个加权的价值函数梯度和。
• $\gamma$是折扣因子，$\lambda$控制资格迹的衰减速度。

$$z_t(s,a)=\{\begin{array}{ll}\gamma \lambda \cdot z_{t-1}(s,a)+{\mathrm{\nabla }}_w{Q}_w(s_t,a_t)& \mathrm{i}\mathrm{f}(\mathrm{s},\mathrm{a})=({\mathrm{s}}_{\mathrm{t}},{\mathrm{a}}_{\mathrm{t}})\\ \gamma \lambda \cdot z_{t-1}(s,a)& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}$$$$z_t=\lambda \gamma \cdot z_{t-1}+{\mathrm{\nabla }}_w{Q}_w(s_t,a_t)$$

• 当状态被访问时，资格迹会增加。早期访问过的状态，资格迹按$\gamma \lambda$衰减。

使用资格迹

• 按照如下公式更新价值函数。只需计算TD误差和资格迹，无需计算复杂的$\lambda$回报。

$$w_{t+1}=w_t+\alpha \cdot {\delta }_t\cdot z_t$$

• Sara(λ)

$${\delta }_t=r_t+\gamma \cdot Q_w(s_{t+1},a_{t+1})-Q_w(s_t,a_t)$$

• Q-Learning(λ)

$${\delta }_t=r_t+\gamma \cdot \underset{a}{max}{Q}_w(s_{t+1},a_{t+1})-Q_w(s_t,a_t)$$

MC vs TD vs n步TD vs TD(λ)

核心公式对比

MC vs TD vs n步TD vs TD(λ)

MC 采样

• V函数 更新

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{\mathrm{完}\mathrm{全}\mathrm{采}\mathrm{样}}{\underbrace{G_t}}-V(s_t))$$

• MC Error

$$\delta =G_t-V(s_t)$$

单步TD

• V函数 更新

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{\mathrm{时}\mathrm{序}\mathrm{差}\mathrm{分}\mathrm{目}\mathrm{标}，\mathrm{采}\mathrm{样}1\mathrm{步}}{\underbrace{r_{t+1}+\gamma V(s_{t+1})}}-\underset{\mathrm{估}\mathrm{计}\mathrm{值}}{\underbrace{V(s_t)}})$$

• TD Error

$$\delta =r_{t+1}+\gamma V(s_{t+1})-V(s_t)$$

n步 TD

• $G_{t:t+n}$ 定义

$$G_{t:t+n}=r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^{n-1}{r}_{t+n-1}+{\gamma }^{n}V(s_{t+n})$$

• V函数 更新

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (G_{t:t+n}-V(s_t))$$$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{n\mathrm{步}TD,\mathrm{采}\mathrm{样}n\mathrm{步},1\mathrm{个}n\mathrm{步}\mathrm{回}\mathrm{报}}{\underbrace{r_{t+1}+\gamma \cdot r_{t+2}+\cdots +{\gamma }^n\cdot V(s_{t+n})}}-V(s_t))$$

• TD Error$$\delta =G_{t:t+n}-V(s_t)$$

$$\delta =r_{t+1}+\gamma \cdot r_{t+2}+\cdots +{\gamma }^n\cdot V(s_{t+n})-V(s_t)$$

TD(λ)

• $G_t^{\lambda }$ 定义

$$G_t^{\lambda }=(1-\lambda )[{\lambda }^0\cdot G_{t:t+1}+{\lambda }^1\cdot G_{t:t+2}+{\lambda }^2\cdot G_{t:t+3}+{\lambda }^3\cdot G_{t:t+2}+\cdots ]$$$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}\cdot G_{t:t+n}+{\lambda }^{T-t-1}\cdot G_t$$

• V函数 更新

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (G_t^{\lambda }-V(s_t))$$$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (\underset{\lambda \mathrm{回}\mathrm{报}，\mathrm{多}\mathrm{个}n\mathrm{步}\mathrm{回}\mathrm{报},\mathrm{做}\mathrm{平}\mathrm{均}}{\underbrace{(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_{t:t+n}}}-V(s_t))$$

• TD Error

$$\delta =G_t^{\lambda }-V(s_t)$$$$\delta =(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}\cdot G_{t:t+n}-V(s_t)$$

概念对比

时序差分 vs 蒙特卡洛 vs 动态规划

时序差分

• 可以在线学习，每走一步就能更新；在知道结果之前就能学习，更快速灵活
• 可以从不完整序列学习，可以在连续环境下进行学习
• 利用了马尔科夫性质
• 更新时使用了自举(更新时使用了估计)，一部分采样，一部分自举。
  • 以采样方式得到不完整序列，估计某状态后可能的奖励，不断采样持续更新价值
• TD方法在每个时刻都可以更新价值函数，是一种高偏差、低方差的方法
• TD 有偏估计，可能无法准确预测未来收益，在延迟激励情况下，需很长时间才能把奖励传播到之前的状态，存在信用分配问题。

蒙特卡洛

• 不能在线学习，必须游戏结束时才能更新
• 只能从完整序列进行学习，只能在有终止的情况下进行学习
• 没有假设环境具有马尔科夫性质
• 没有使用自举
• 高方差 (预测值的变化范围、离散程度)
• MC方法需要用整个episode的经验去估计价值函数，是一种低偏差、高方差的方法。

动态规划

• 有模型预测方法
• 使用了自举

自举采样对比

时序差分对比蒙特卡罗

动态规划备份：直接计算期望

$$V(s_t)\leftarrow E_{\pi }[r_{t+1}+\gamma V(s_{t+1})]$$

蒙特卡洛备份：采样一条支路计算，更新这条路径上的所有状态

$$V(s_t)\leftarrow V(s_t)+\alpha \cdot (G_{i,t}-V(s_t))$$

时序差分备份：采样+自举，从当前状态开始走几步，关注局部步骤

时序差分：需要广度，就变成动态规划；需要深度，就变成蒙特卡洛。

免模型控制

免模型控制是指不需要知道环境模型，进行寻找最优策略输出最有价值。Q-Learning和SARSA都是基于时序差分的算法。

广义策略迭代

狭义策略迭代

狭义策略迭代算法

定义

• 有模型控制，通过策略评估和策略改进，不断迭代直到值函数收敛。

• 通过环境信息（奖励函数、状态转移概率），来计算价值函数

$$\begin{array}{ll}{V}_{{\pi }_{k+1}}(s)& =\sum _{a\in A}\pi (a\mid s)\cdot (R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_{{\pi }_k}(s^{\prime }))\end{array}$$$$Q_{{\pi }_{k+1}}(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_{{\pi }_k}(s^{\prime })$$

缺点

• 依赖奖励函数和状态转移概率；免模型时，无法估计

广义策略迭代

广义策略迭代算法

定义

• 免模型控制，引入蒙特卡洛和时序差分，进行策略迭代
• 策略评估：用蒙特卡洛探索采样多个轨迹，平均轨迹价值，来估计Q函数

$$Q_{\pi }(s,a)\approx E_{\tau \sim p(\tau )}[G(\tau )\mid {\tau }_{s_0}=s,{\tau }_{a_0}=a]\approx \frac{1}{N}\sum _{i=1}^{N}G({\tau }_i)$$

• 策略改进：直接选择最大的Q函数

$$\pi (s)=\arg \underset{a}{max}Q(s,a)$$

探索策略

探索和利用

探索的意义

• 一直基于某种思路工作，可能会比较好，但也可能会走偏
• 换一种思路也许就会豁然开朗
• 守旧不一定是坏事，不能过度好奇心

贪心策略

$ϵ$贪心策略

• 为了保证足够的探索，以$ϵ$概率随机选择一个动作
• $ϵ$按时间步递减，如0.1 -> 0.01
  • 开始时不确定哪个动作较好，花较多时间进行探索
  • 后期逐渐稳定，减少探索，降低$ϵ$

$${\pi }^{ϵ}(s)=\{\begin{array}{llll}& \pi (s)=\arg \underset{a}{max}{Q}^{\pi }(s,a),& \text{依概率 }1-ϵ& \text{(利用, 守旧派)}\\ & \mathrm{随}\mathrm{机}\mathrm{选}\mathrm{动}\mathrm{作}a\prime ,& \text{依概率 }ϵ& \text{(探索, 好奇心)}\end{array}$$

玻尔兹曼探索策略

定义

• 对$Q(s,a)$，$a$ 被选中的概率和$e^{Q(s,a)/T}$有关
• T为温度系数
  • T很大，等概率选择；T很小，Q值更大的动作容易选中；T趋于0，只选择最优动作。

$$\pi (a\mid s)=\frac{e^{Q(s,a)/T}}{\sum _{a^{\prime }\in A}{e}^{Q(s,a^{\prime })/T}}$$

同策略异策略

行为策略 vs 目标策略

目标策略和行为策略

行为/探索/采样策略

• 探索环境的策略，采集很多轨迹经验，给行为策略进行学习
• 像前线的战士，希望充分探索环境，访问所有可能的状态和动作。
• 如：策略评估，探索环境，采样估计Q函数

目标/学习/改进策略

• 通过经验稿子进行学习的策略，不用和环境进行交互
• 像后方的军师，尽可能利用已有的经验。
• 如：策略改进，更新策略

同策略 vs 异策略

同策略 vs 异策略

同策略/On-Policy

• 定义
  • 行为/采样/探索策略 和 学习/改进/目标策略 相同。
  • 使用同一策略来搜集样本，通过样本学习并更新原策略。
• 优点
  • 稳定，可以保证学习到的策略收敛到最优策略
  • 较好解决连续动作空间问题
• 缺点
  • 样本利用效率低
    • 仅能用来更新当前策略，不能更新其他策略

异策略/Off-Policy

• 定义
  • 行为/采样/探索策略 $\mu$ 和 学习/改进/目标策略 $\pi$ 不同。
  • 使用行为策略探索到的经验轨迹，来优化目标策略。
    • 如从经验回放或历史数据中学习。
  • $\mu$可是随机策略，但采取 $ϵ$贪心 使其不至于完全随机，是基于Q表格逐渐改进的。
• 优点
  • 学习效率高：旧策略的采样经验可多次利用，节省资源
  • 利用通过行为策略探索来学到最佳策略
    • 行为策略可采用 $ϵ$贪心算法，更加大胆，有可能探索到最佳策略
    • 目标策略仍使用普通贪心算法，根据行为策略经验来采用最佳策略
  • 可以学习其他智能体的动作
• 缺点
  • 需分布比较接近，避免偏差，避免训练不稳定

SARSA：同策略TD

Sarsa 核心思想

Sarsa 核心思想

核心思想

• 用时序差分方法来估计Q函数，更新Q表格后就可更新策略
• 用下一步$Q(s_{t+1},a_{t+1})$值，来更新当前步$Q(s_t,a_t)$值，不断强化每一个Q值

$$Q_{\pi }(s_t,a_t)\leftarrow Q_{\pi }(s_t,a_t)+\alpha \cdot (\underset{TD\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r_{t+1}+\gamma \cdot Q_{\pi }(s_{t+1},a_{t+1})}}-\underset{\mathrm{当}\mathrm{前}\mathrm{值}}{\underbrace{Q_{\pi }(s_t,a_t)}})$$$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a))$$

Sarsa 算法流程

主要流程

• 随机初始化$\pi (s)$，不断迭代直到$Q(s,a)$收敛，进行以下迭代

• 确定初始状态$s$，依策略选择动作$a={\pi }^{ϵ}(s)$，重复以下流程，直到$s$为终止态

  • 环境交互采样 $s,a,r,s^{\prime },a^{\prime }$

    • 执行动作$a$，得奖励$r$、新状态$s^{\prime }$
    • 在新状态$s^{\prime }$，依策略选择动作$a^{\prime }={\pi }^{ϵ}(s^{\prime })$

  • 策略评估 / Q函数估计

    • $Q(s,a)=Q(s,a)+\alpha (r+\gamma Q(s^{\prime },a^{\prime })-Q(s,a))$

  • 策略改进 / 更新策略 $\pi$

    • $\pi (s)=\arg \underset{a}{max}Q(s,a)$

  • 状态动作前进：$s\leftarrow s^{\prime },a\leftarrow a^{\prime }$

n步Sarsa

n步时序差分

单步时序差分

• 自举1步，用下一步$Q(s_{t+1},a_{t+1})$值，来更新当前步$Q(s_t,a_t)$值$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \cdot (\underset{TD\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r_{t+1}+\gamma \cdot Q(s_{t+1},a_{t+1})}}-\underset{\mathrm{当}\mathrm{前}\mathrm{值}}{\underbrace{Q(s_t,a_t)}})$$

n步时序差分

• 自举n步，一次性考虑$n$步回报

$$\begin{array}{lll}n=1& \mathrm{Sarsa}(0)& Q_{t:t+1}=r_{t+1}+\gamma \cdot Q(s_{t+1},a_{t+1})\\ n=2& \mathrm{Sarsa}(1)& G_{t:t+2}=r_{t+1}+\gamma \cdot r_{t+2}+{\gamma }^2\cdot Q(s_{t+2},a_{t+2})\\ & & ⋮\\ n=n& \mathrm{Sarsa}(\mathrm{n})& Q_{t:t+n}=r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^{n}Q(s_{t+n},a_{t+n})\\ & & ⋮\\ n=\mathrm{\infty }& \mathrm{MC}& Q_{t:\mathrm{\infty }}=r_{t+1}+\gamma \cdot r_{t+2}+{\gamma }^2\cdot r_{t+2}+\cdots +{\gamma }^{T-t-1}\cdot r_T\end{array}$$

• n步回报$Q_t^n$

$$Q_t^n=r_{t+1}+\gamma \cdot r_{t+2}+\cdots +{\gamma }^n\cdot Q(s_{t+n},a_{t+n})$$

Sarsa(λ)

Sarsa(λ)

核心思想

• 模仿TD(λ)使用多个n步回报，引入资格衰减参数λ，对多个$Q_t^n$进行加权平均

$$Q_t^{\lambda }=(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}{Q}_t^n$$

• Sarsa($\lambda$)的更新策略

$$Q(s,a)\leftarrow Q(s_t,a_t)+\alpha \cdot (Q_t^{\lambda }-Q(s,a))$$

Q学习：异策略TD

核心思想

Q学习 核心思想

核心思想

• 同Sarsa一样，利用TD自举来估计Q函数，更新Q表格后可更新策略。

• 但学习策略和行为策略不一样，是一种异策略算法

• 学习策略

  • 估计Q函数时，采取下一时刻Q值最大的动作 $a^{\prime }=\underset{a^{\prime }}{max}Q(s_{t+1},a^{\prime })$
  • $a^{\prime }\ne a_{t+1}$ ，$a^{\prime }$ 不来自行为策略，并非下一步真正执行的动作$a_{t+1}$
  • 学习策略动作$a^{\prime }$和行为策略动作$a_{t+1}$不一样

• TD目标值：$r_{t+1}+\gamma \underset{a^{\prime }}{max}Q(s_{t+1},a^{\prime })$， 自举1步，更新Q函数

$$Q(s_t,a_t)=Q(s_t,a_t)+\alpha (\underset{TD\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r_{t+1}+\gamma \underset{a^{\prime }}{max}Q(s_{t+1},a^{\prime })}}-\underset{\mathrm{当}\mathrm{前}\mathrm{值}}{\underbrace{Q(s_t,a_t)}})$$

• 对比：Sarsa学习策略使用的动作$a_{t+1}$来自于行为策略采样的动作$a_{t+1}$，二者相同

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \cdot (\underset{TD\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r_{t+1}+\gamma \cdot Q(s_{t+1},a_{t+1})}}-\underset{\mathrm{当}\mathrm{前}\mathrm{值}}{\underbrace{Q(s_t,a_t)}})$$

算法流程

Q学习 算法流程

• 初始化策略$\pi$，执行以下迭代，直到所有$Q(s,a)$收敛

• 初始化$s$，执行以下迭代，直到$s$为终止态

  • 环境交互采样/探索策略

    • 依策略选择动作 $a={\pi }^{ϵ}(s)$
    • 执行动作$a$，得即时奖励$r$、新状态$s^{\prime }$

  • Q函数估计/学习策略

    • 与sarsa不同，不使用探索策略采样的、下一步真正执行的 动作$a_{t+1}$

    • 而是直接选择 最大Q值对应的动作 $a^{\prime }=\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$ 用来估计Q。

      • $a^{\prime }\ne a_{t+1}$ ，$a^{\prime }$ 不来自探索策略，并非下一步真正执行的动作
      $$Q(s,a)=Q(s,a)+\alpha (r+\gamma \underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })-Q(s,a))$$

  • 仅状态前进 $s\leftarrow s^{\prime }$

• 策略更新，输出策略$\pi$

$$\pi (s)=\arg \underset{a\in A}{max}Q(s,a)$$

伪代码

训练流程代码：多个回合

• agent采样动作：agent.sample_action(state)
• 环境交互：env.step(action)
• 样本放入经验池：agent.meomory.push(xxx)
• agent更新策略：agent.update(xxx)

for i_ep in range(train_eps): # 遍历每个回合
    # 重置环境，获取初始状态
    state = env.reset()  # 重置环境,即开始新的回合
    while True: # 对于比较复杂的游戏可以设置每回合最大的步长，例如while ep_step<100，即最大步长为100。
        # 智能体根据策略采样动作
        action = agent.sample_action(state)  # 根据算法采样一个动作
        # 与环境进行一次交互，得到下一个状态和奖励
        next_state, reward, terminated, _ = env.step(action)  # 智能体将样本记录到经验池中
        agent.memory.push(state, action, reward, next_state, terminated) 
        # 智能体更新策略
        agent.update(state, action, reward, next_state, terminated)  
        # 更新状态
        state = next_state  
        # 如果终止则本回合结束
        if terminated:
            break

Agent类：

• 采样动作：$ϵ$贪心法，指数衰减
• 预测动作：直接根据Q_table选择最大值即可
• 策略更新：更新Q_table，

class Agent:
    def __init__():
    		self.Q_table  = defaultdict(lambda: np.zeros(n_actions))

    def sample_action(self, state):
        ''' 采样动作，训练时用
        '''
        self.sample_count += 1
        # epsilon是会递减的，这里选择指数递减
        self.epsilon = self.epsilon_end + (self.epsilon_start - self.epsilon_end) * math.exp(- self.sample_count / self.epsilon_decay) 
        # e-greedy 策略
        if np.random.uniform(0, 1) > self.epsilon:
            action = np.argmax(self.Q_table[str(state)]) # 选择Q(s,a)最大对应的动作
        else:
            action = np.random.choice(self.n_actions) # 随机选择动作
        return action
    
    def predict_action(self,state):
        ''' 预测或选择动作，测试时用
        '''
        action = np.argmax(self.Q_table[str(state)])
        return action
    
    def update(self, state, action, reward, next_state, terminated):
      	''' 更新Q_table即可
      	'''
        Q_predict = self.Q_table[str(state)][action] 
        if terminated: # 终止状态
            Q_target = reward  
        else:
            # TD目标计算，reward + 直接Q max值，而非给定下一时刻真正执行的动作的Q值
            Q_target = reward + self.gamma * np.max(self.Q_table[str(next_state)]) 
        self.Q_table[str(state)][action] += self.lr * (Q_target - Q_predict)
        return

Sarsa vs Q-Learning

Sarsa vs Q-Learning

Sarsa

• 同策略算法
• 自己的策略采样轨迹，并用$Q_{\pi }(s_{t+1},a_{t+1})$来更新$Q_{\pi }(s_t,a_t)$

Q-Learning

• 异策略算法
• 不需要知道下一步实际执行哪个动作，更新Q时默认选择Q值最大的动作
• 不用知道下一步实际$a_{t+1}$，就能更新$Q(s_t,a_t)$
• Q学习不担心受探索的影响，比Sarsa更大胆