笔记

• 强化学习基于值函数的学习方法。
• 最重要的是SARSA、Q学习、DQN。但是这些都依赖于前面的动态规划和蒙特卡罗方法。

值函数的学习方法

摘要

1. 穷举所有策略选择最好策略（没用）
2. 迭代优化策略，根据策略的值函数去优化策略 （重点）
3. 动态规划（已知状态转移概率$p(s^{\prime }\mid s,a)$和奖励函数$r(s,a,s^{\prime })$）
4. 蒙特卡罗方法（不知模型），先采一些样本，再优化
5. 时序差分学习算法：SARAS和Q学习
6. 深度Q网络

值函数策略学习方法

值函数（$V^{\pi }(s)$、$Q^{\pi }(s,a)$ ）用来对策略$\pi (a\mid s)$进行评估。

1. 穷举策略法 （无用）

• 如果策略有限，可以对所有策略进行评估，选出最优策略

$$\mathrm{\forall }s,{\pi }^{\ast }=\arg \underset{\pi }{max}{V}^{\pi }(s)$$

• 缺点：实际策略空间$|\mathcal{A}{|}^{|\mathcal{S}|}$非常大，根本无法搜索。

2. 迭代优化策略法 (重点)

• 核心步骤

  • 随机初始化一个策略
  • 计算该策略的值函数：动态规划、 蒙特卡罗 等方法
  • 根据值函数来设置新的策略

• 例子

  • 给一个初始策略$\pi (a\mid s)$，根据$Q^{\pi }(s,a)$去不断迭代去优化，直到收敛。
  • 得到新策略函数${\pi }^{\prime }(a\mid s)$（确定性策略）
  • 新策略的值函数会不断变大：$Q^{{\pi }^{\prime }}(s,\hat{a})\ge Q^{\pi }(s,\hat{a})$

$${\pi }^{\prime }(a\mid s)=\{\begin{array}{lll}& 1& a=\arg \underset{\hat{a}}{max}{Q}^{\pi }(s,\hat{a})\\ & 0& \text{others}\end{array}$$

动态规划算法

总体思想

动态规划算法

1. 动态规划思想

• 已知环境模型：状态转移概率$p(s\prime \mid s,a)$ 和奖励$r(s,a,s\prime )$
• 迭代计算值函数：通过贝尔曼或贝尔曼最优方程，先算$V(s)$，再算$Q(s,a)$
• 通过值函数来优化策略：一般为优化为固定策略$\pi (s)=a$

2. 两种方法

• 策略迭代算法

  • 有策略，均等初始化策略， 贝尔曼方程迭代计算V函数(均值)
  • 再计算Q函数，依Q更新策略

• 值迭代算法

  • 无策略，直接优化V函数，均0初始化V函数，贝尔曼最优方程迭代计算V函数(最大a)
  • 直到V函数收敛，再计算Q函数，依Q更新策略

3. 缺点

• 要求模型已知：$p(s\prime \mid s,a)$、 $r(s,a,s\prime )$
• 效率太低：状态动作数量太多时，无法计算，如棋盘361个位置、每位置3种状态，则棋盘状态有$3^{361}$个，无法计算
  • 可以通过神经网络来近似计算值函数

策略迭代算法

策略迭代算法

核心思想

• 显式维护和更新策略，通过策略评估和策略改进 2个步骤来完成1次更新。
• 给定策略$\pi$(初始随机)，
  • 使用贝尔曼方程(所有a求期望)来算出该策略下各状态的价值函数 $V^{\pi }(s)$
  • 再算出 $Q^{\pi }(s,a)$ 来更新策略

关键步骤

• 均等概率初始化策略$\pi (a|s)$

$$\mathrm{\forall }s,\mathrm{\forall }a,\pi (a\mid s)=\frac{1}{|\mathcal{A}|}$$

• 使用贝尔曼方程迭代计算该策略各状态s的价值函数 $V^{\pi }(s)$，所有a求均值

$$\mathrm{\forall }s,V^{\pi }(s)=E_{a\sim \pi (a\mid s)}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })]=E_{a\sim \pi (a\mid s)}[Q(s,a)]$$

• 利用$V^{\pi }(s)$ 计算 $Q^{\pi }(s,a)$函数

$$Q^{\pi }(s,a)=E_{s^{\prime }\sim p(s^{\prime }|s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$

• 根据$Q^{\pi }(s,a)$更新策略$\pi (s)=a$，选择最好的动作a，更新为固定策略，最终输出策略$\pi$

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

价值迭代算法

值迭代算法

核心思想

• 无需策略，通过贝尔曼最优方程，直接迭代更新$V(s)$ 直到其收敛，收敛后再算$Q(s,a)$和$\pi$
• 收敛时的值函数就是最优值函数，对应的策略 $\pi$ 是最优的策略

$$V^{\ast }(s)=\underset{a}{max}{Q}^{\ast }(s,a)$$

关键步骤

• 均0初始化值$V(s)$函数

$$\mathrm{\forall }s\in S,V(s)=0$$

• 无需策略，使用贝尔曼最优方程迭代计算$V(s)$，直到其收敛。
• 每次迭代，选择最大化当前价值的动作

$$\mathrm{\forall }s\in S,V^{\ast }(s)=\underset{a}{max}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]=\underset{a}{max}[Q(s,a)]$$

• 收敛后，利用值$V^{\pi }(s)$ 计算 $Q^{\pi }(s,a)$函数

$$Q^{\pi }(s,a)=E_{s^{\prime }\sim p(s^{\prime }|s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$

• 最后，根据$Q^{\pi }(s,a)$更新策略$\pi (s)=a$，选择最好动作a, 最终输出策略$\pi$

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

蒙特卡罗采样方法

模型无关的强化学习

参考文章

• 蒙特卡洛方法

采样学习方法

蒙特卡洛采样学习方法

1. 背景

• 智能体和环境交互采集一些样本，根据样本期望来估计Q函数，求解最优策略
• 模型未知，不知$p(s^{\prime }|s,a)、r(s,a,s^{\prime })$ ， 通过采样来计算$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({\tau }_i)$$

2. 方法步骤

• 从状态$s$,动作$a$ 开始随机游走探索环境， 采集N个样本/轨迹，得到轨迹总回报

$$\begin{array}{ll}\mathrm{轨}\mathrm{迹}:& {\tau }^{(1)},{\tau }^{(2)},\cdots ,{\tau }^{(N)}\\ \mathrm{回}\mathrm{报}：& G({\tau }^{(1)}),G({\tau }^{(2)}),\cdots ,G({\tau }^{(N)})\end{array}$$

• 利用轨迹总回报去估计 $Q^{\pi }(s,a)$

$$\begin{array}{l}{Q}^{\pi }(s,a)\approx {\hat{Q}}^{\pi }(s,a)=\frac{1}{N}\sum _{i=1}^{N}G({\tau }^{(i)})\end{array}$$

• 也可增量计算，不用每次计算平均值。

$$Q_N^{\pi }(s,a)=Q_{N-1}^{\pi }(s,a)+\alpha \cdot \underset{\mathrm{增}\mathrm{量}}{\underbrace{(G({\tau }^{(N)})-Q_{N-1}^{\pi }(s,a))}}$$

• 基于 $Q^{\pi }(s,a)$ 改进策略 $\pi (a|s)$， $ϵ$ 贪心法 鼓励探索和利用。
• 在新策略下，再去采集样本、估计Q、改进策略，直到收敛

3. 缺点

• 依赖每条轨迹的真实回报 $G(\tau )$，需每个轨迹完成以后(回合结束)，才能算出真实回报，再利用回报去更新价值函数。
• 在回合结束之前，价值函数的估计不会发生改变，学习效率较低，不适用于长序列任务。

增量计算Q回报

增量计算Q(s,a), TD算法

背景

• 需拿到所有轨迹的回报后平均，才能算出Q值，效率低。原始公式

$$Q^{\pi }(s,a)\approx {\hat{Q}}^{\pi }(s,a)=\frac{1}{N}\sum _{i=1}^{N}G({\tau }^{(i)})$$

增接迭代计算回报(Q值)

• 第N次后的平均(Q值) = 第N-1次后的平均(Q值) + 第N次的1个增量

$$Q_N^{\pi }(s,a)=Q_{N-1}^{\pi }(s,a)+\alpha \cdot (\underset{\mathrm{当}\mathrm{前}\mathrm{真}\mathrm{实}\mathrm{回}\mathrm{报}}{\underbrace{G({\tau }^N)}}-\underset{\mathrm{当}\mathrm{前}\mathrm{预}\mathrm{测}\mathrm{回}\mathrm{报}}{\underbrace{Q_{N-1}^{\pi }(s,a)}})$$

• 增量(蒙特卡洛误差) = 轨迹真实回报 - 期望回报

$$\delta =G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a)$$

• 具体推导过程

$$\begin{array}{rl}{\hat{Q}}_N^{\pi }(s,a)& =\frac{1}{N}\sum _{i=1}^{N}G({\tau }^{(i)})\\ & =\frac{1}{N}(G({\tau }^{(N)})+\sum _{i=1}^{N-1}G({\tau }^{(i)}))\\ & =\frac{1}{N}(G({\tau }^{(N)})+(N-1){\hat{Q}}_{N-1}^{\pi }(s,a))\\ & ={\hat{Q}}_{N-1}^{\pi }(s,a)+\frac{1}{N}\cdot (G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a))\\ & =\underset{\mathrm{前}N-1\mathrm{次}\mathrm{的}\mathrm{预}\mathrm{测}\mathrm{回}\mathrm{报}}{\underbrace{{\hat{Q}}_{N-1}^{\pi }(s,a)}}+\alpha \cdot \underset{\mathrm{第}N\mathrm{次}\mathrm{的}\mathrm{增}\mathrm{量}}{\underbrace{(G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a))}}\end{array}$$

• 符号定义
  • $Q_{N-1}^{\pi }(s,a)$：N-1次实验(轨迹)后的Q函数值
  • $Q_N^{\pi }(s,a)$：N次实验(轨迹)后的Q函数值
  • $G({\tau }^{(i)})$ ：第i条轨迹/第i次实验的真实回报

优点

• 每采样一个新轨迹${\tau }_{s,a}$，就可以更新${\hat{Q}}^{\pi }(s,a)$
• 无需拿到所有轨迹的回报后才计算Q值，而为增量迭代计算

利用和探索

利用探索

1. 利用和探索

• 试验轨迹应覆盖所有状态和动作，以找到更好的策略
• 采用 $ϵ$贪心法 👏，少数情况下随机选择动作，鼓励对环境进行探索

$${\pi }^{ϵ}(s)=\{\begin{array}{llll}& \pi (s)={\text{argmax}}_a{Q}^{\pi }(s,a),& \text{依概率 }1-ϵ& \text{(利用)}\\ & a\prime ,& \text{依概率 }ϵ& \text{(探索)}\end{array}$$

• 如用纯贪心法 ，则没有探索，只对环境进行利用
  • 每次试验得到的轨迹是一样的
  • 只能算出$Q^{\pi }(s,\pi (s))$ ，无法计算出$Q^{\pi }(s,a\prime )$，即无法计算出其它动作$a\prime$的Q函数

2. 同策略和异策略

• 同策略(on-policy) (普通MC)

  • 环境交互的行为(采样)策略，和评估价值的目标(改进)策略，相同，都是${\pi }^{ϵ}(s)$。

• 异策略(off-policy)

  • 采样策略是${\pi }^{ϵ}(s)$， 优化的目标策略是$\pi$，采样和改进策略不同。

• 我们希望：行为策略能尽可能探索环境，目标策略直接利用已有经验选取最佳策略。

3. 重要性采样

• 思想：通过在一个分布上采样，来估计另一个分布下的期望值。

• RL：

  • 用策略$\mu$ 生成数据，来估计策略$\pi$的价值函数，实现off-policy
  • 为每个$\mu$的轨迹回报，赋予重要性采样权重，弥补矫正2个策略的差异
  • 从而实现用一个策略的数据来估计另一个策略的价值函数
  $$E_{\tau \sim p_{\pi }(\tau )}[G(\tau )]\approx \frac{1}{N}\sum _{i=1}^N\frac{p_{\pi }({\tau }_i)}{p_{\mu }({\tau }_i)}\cdot G({\tau }_i)$$

• $w_i=\frac{p_{\pi }({\tau }_i)}{p_{\mu }({\tau }_i)}$： 重要性采样权重

时序差分学习算法

总体思想

TD 摘要

1. 时序差分学习=蒙特卡罗+动态规划，无需知道完整轨迹就能对策略进行评估。
2. 蒙特卡罗增量计算价值函数： ${\hat{Q}}^{\pi }(s,a)={\hat{Q}}^{\pi }(s,a)+\alpha \cdot (G({\tau }_{s,a,s^{\prime },a^{\prime }})-{\hat{Q}}^{\pi }(s^{\prime },a^{\prime }))$
3. 贝尔曼估计轨迹回报：$G({\tau }_{s,a,s^{\prime },a^{\prime }})=r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}^{\pi }(s^{\prime },a^{\prime })$

背景

• 动态规划：效率低，状态动作数量多，难以计算
• 蒙特卡罗：效率低，需拿到完整轨迹才能对策略进行评估和更新
• 时序差分(TD)
  • 对蒙特卡罗的改进，引入动态规划来提高效率
  • 模拟一段轨迹，每行动一步或几步，就利用贝尔曼方程来评估行动前状态的价值

TD 整体思想

时序差分学习（temporal-difference learning）结合了动态规划和 蒙特卡罗方法。

1. 改进蒙特卡罗 增量计算${\hat{Q}}_N^{\pi }(s,a)$

• 第N次后的Q值 = 第N-1次后的Q值 + 1个增量
• 增量是第N条轨迹实际回报和预测回报的误差， $\alpha$是一个较小的权值

$${\hat{Q}}_N^{\pi }(s,a)={\hat{Q}}_{N-1}^{\pi }(s,a)+\alpha \cdot \underset{\mathrm{增}\mathrm{量}}{\underbrace{(G({\tau }^{(N)})-{\hat{Q}}_{N-1}^{\pi }(s,a))}}$$

• 依赖：每条轨迹的真实回报 $G(\tau )$

2. 利用贝尔曼估计轨迹回报$G({\tau }^{(N)})$

• 无需完整轨迹，利用⭐Q函数贝尔曼方程动态规划，来估计完整轨迹回报 $G(\tau ),Q(s,a)$
• 从$s,a$开始，采样下一步状态动作$(s^{\prime },a^{\prime })$ 并得到奖励$r(s,a,s^{\prime })$，即可估计轨迹回报

$$\begin{array}{ll}G({\tau }_{s,a,s^{\prime },a^{\prime }})& =r(s,a,s^{\prime })+\gamma \cdot G({\tau }_{s_0=s^{\prime },a_0=a^{\prime }})\\ & \approx r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}^{\pi }(s^{\prime },a^{\prime })\end{array}$$

• ⭐用当前${\hat{Q}}_{N-1}^{\pi }(s^{\prime },a^{\prime })$，去估计当前轨迹未来$(s^{\prime },a^{\prime })$ 的总回报 $G({\tau }_{1:T}^{(N)})$ ‼️

3. 总结

• 贝尔曼估计总回报（马尔可夫性，动态规划）

$$G(\tau )\leftarrow r(s,a,s^{\prime })+\gamma \cdot Q(s^{\prime },a^{\prime })$$

• 增量更新值函数（蒙特卡罗）

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (G(\tau )-Q(s,a))$$$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (\underset{\mathrm{实}\mathrm{际}\mathrm{值}}{\underbrace{r+\gamma \cdot Q(s^{\prime },a^{\prime })}}-\underset{\mathrm{预}\mathrm{期}\mathrm{值}}{\underbrace{Q(s,a)}})$$$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a)$$

两种算法和比较

1. 两种算法

• SARSA：同策略。采样动作$a^{\prime }={\pi }^{ϵ}(s^{\prime })$和值函数更新$Q(s^{\prime },a^{\prime })$，都关于同一个策略${\pi }^{ϵ}$
• Q学习：直接选择最大的值函数$\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$更新，更新的Q是关于策略$\pi$的。

2. 蒙特卡罗方法和时序差分方法比较

• 蒙特卡罗方法：需完整路径才能知道总回报，不依赖马尔可夫性质
• 时序差分学习：只需一步就能知道总回报，依赖于马尔可夫性质

SARSA算法

摘要

1. 当前$s,a$， 奖励$r(s,a,s^{\prime })$， 新的$s^{\prime },a^{\prime }$， 优化$Q(s,a)$
2. 贝尔曼估计实际奖励$G(\tau )$：$r+\gamma \cdot Q(s^{\prime },a^{\prime })$
3. 增量计算Q：$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot Q(s^{\prime },a^{\prime })-Q(s,a))$
4. 更新策略$\pi (s)$ ：$\pi (s)=\arg \underset{a\in \mathcal{A}}{max}Q(s,a)$
5. SARAS：优化所有$Q(s,a)$直到收敛。对每一个$s,a$，每一步状态转移，计算Q，直到s为终止状态

State Action Reward State Action

SARASState Action Reward State Action，一种同策略的时序差分学习算法。

1. 核心思想

• 蒙特卡罗增量计算Q函数，其中轨迹回报 用贝尔曼估计来计算⭐

• 不断优化Q函数，减少实际值和预期值的差距，通过下面3项来更新${\hat{Q}}^{\pi }(s,a)$

  • 当前状态动作：$s,a$

  • 奖励：$r(s,a,s^{\prime })$

  • 下一步状态动作：$s^{\prime },a^{\prime }$

2. 核心推导

• 增量计算价值函数 ${\hat{Q}}^{\pi }(s,a)$

$${\hat{Q}}^{\pi }(s,a)={\hat{Q}}^{\pi }(s,a)+\alpha \cdot (G({\tau }_{s,a,s^{\prime },a^{\prime }})-{\hat{Q}}^{\pi }(s^{\prime },a^{\prime }))$$

• 贝尔曼方程估计轨迹回报 $G({\tau }^{(N)})$

$$\begin{array}{l}G({\tau }_{s,a,s^{\prime },a^{\prime }})=r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}^{\pi }(s^{\prime },a^{\prime })\end{array}$$

• 得到最终Q函数更新方程 ⭐

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

• 本质：蒙特卡罗增量计算Q函数，其中轨迹回报 用贝尔曼估计来计算⭐

$${\hat{Q}}^{\pi }(s,a)={\hat{Q}}^{\pi }(s,a)+\alpha \cdot (\underset{\mathrm{实}\mathrm{际}\mathrm{值},\mathrm{贝}\mathrm{尔}\mathrm{曼}\mathrm{估}\mathrm{计}}{\underbrace{r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}^{\pi }(s^{\prime },a^{\prime })}}-\underset{\mathrm{预}\mathrm{期}\mathrm{值}}{\underbrace{{\hat{Q}}^{\pi }(s^{\prime },a^{\prime })}})$$

3. SARSA 算法步骤

• 随机初始化策略$\pi (s)$，不断迭代直到$Q(s,a)$收敛，进行以下迭代
• 确定初始状态动作$s,a$，不断执行以下流程，直到$s$为终止态
  • 执行动作$a$：得到奖励$r$ 和新状态$s^{\prime }$
  • 在新状态$s^{\prime }$：依概率选择新动作$a^{\prime }={\pi }^{ϵ}(s^{\prime })$
  • 更新Q函数：${\hat{Q}}^{\pi }(s,a)={\hat{Q}}^{\pi }(s,a)+\alpha \cdot (r(s,a,s^{\prime })+\gamma \cdot {\hat{Q}}^{\pi }(s^{\prime },a^{\prime })-{\hat{Q}}^{\pi }(s^{\prime },a^{\prime }))$
  • 更新策略$\pi$：$Q(s,a)={\text{argmax}}_{a}Q(s,a)$
  • 状态前进：$s\leftarrow s^{\prime },a\leftarrow a^{\prime }$

Q学习算法

Q学习

核心思想

• 整体和SARAS类似，区别：
  • 不通过${\pi }^{ϵ}$来选下一步动作a，而是直接选择最优的Q函数
  • 更新后的Q函数是关于$\pi$的，而非${\pi }^{ϵ}$，是一种异策略的TD算法

核心推导

• Q函数推导公式
  • 直接选择最大的Q函数，不用依概率选择a对应的Q

$${\hat{Q}}^{\pi }(s,a)={\hat{Q}}^{\pi }(s,a)+\alpha \cdot (r(s,a,s^{\prime })+\gamma \cdot \underset{a^{\prime }}{max}{\hat{Q}}^{\pi }(s^{\prime },a^{\prime })-{\hat{Q}}^{\pi }(s^{\prime },a^{\prime }))$$

核心流程

• 在状态$s$，选择动作$a={\pi }^{ϵ}(s)$
• 执行动作$a$：得到奖励$r$ 和新状态$s^{\prime }$
• 在新状态$s^{\prime }$：不依概率选择新动作 ，而是直接选择最优的Q函数
• s状态前进 $s\leftarrow s^{\prime }$，直到s为终止态

DQN 算法

Q网络

Q 网络

1. 背景

• 在连续的状态动作空间里计算值函数$Q(s,a)$，

2. 核心思想

• 使用神经网络参数$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})$来近似逼近值函数$Q(s,a)$
• $\mathbf{s}\mathbf{,}\mathbf{a}$ 是 状态动作$s,a$的向量表示。

$$Q_{\varphi }(\mathbf{s},\mathbf{a})\approx Q^{\pi }(s,a)$$$$Q_{\varphi }(\mathbf{s})=\left[\begin{array}{c}{Q}_{\varphi }(\mathbf{s},{\mathbf{a}}_1)\\ ⋮\\ Q_{\varphi }(\mathbf{s},{\mathbf{a}}_m)\end{array}\right]\approx \left[\begin{array}{c}{Q}^{\pi }(s,a_1)\\ ⋮\\ Q^{\pi }(s,a_1)\end{array}\right]$$

• 若是蒙特卡罗方法，参数逼近平均总回报

$$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})\approx {\hat{Q}}^{\pi }(s,a)=\frac{1}{N}\sum _{n=1}^{N}G({\tau }^{(n)})$$

• 若是SARAS算法，参数逼近贝尔曼方程估计的轨迹回报

$$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})\approx E_{s^{\prime },a^{\prime }}[r(s,a,s^{\prime })+\gamma \cdot Q_{\varphi }({\mathbf{s}}^{\prime },{\mathbf{a}}^{\prime })]$$

• 若是Q学习算法，参数逼近贝尔曼最优方程估计的轨迹回报

$$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})\approx E_{s^{\prime }}[r(s,a,s^{\prime })+\gamma \cdot \underset{a^{\prime }}{max}{Q}_{\varphi }({\mathbf{s}}^{\prime },{\mathbf{a}}^{\prime })]$$

3. Q网络的目标函数(以Q学习为例)

• 以Q学习为例，采用SGD来优化，目标函数如下：

$$L(s,a,s^{\prime };\varphi )={(\underset{\mathrm{实}\mathrm{际}\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r+\gamma \cdot \underset{a^{\prime }}{max}{Q}_{\varphi }({\mathbf{s}}^{\prime },{\mathbf{a}}^{\prime })}}-\underset{\text{网络值}}{\underbrace{Q_{\varphi }(\mathbf{s},\mathbf{a})}})}^2$$$$J(\theta )=\frac{1}{2m}\sum _{i=1}^m{(\underset{\text{实际目标值}}{\underbrace{y^{(i)}}}-\underset{\mathrm{网}\mathrm{络}\mathrm{值}}{\underbrace{f_{\theta }({\mathbf{x}}^{(i)})}})}^2$$

DQN

DQN

1. 背景

• Q网络存在2个问题
  • 实际目标值不稳定：参数学习的目标依赖于参数本身。label本身也包含参数
  • 样本之间有很强的相关性

2. DQN(Deep Q Networks)

• 两个方法
  • 目标网络冻结：在一个时间段内，固定目标中的参数
  • 经验回放：
    • 构建经验池(最近经历的数据)来去除相关性
    • 训练时，随机从经验池中抽取样本来代替当前样本进行训练，打破和相邻样本的相似性，避免局部最优
    • 类似于监督学习，先收集样本，再在样本上训练

3. DQN的训练过程

• 初始化经验池 $\mathcal{D}$、容量为N，Q网络参数$\varphi$，目标Q网络参数$\hat{\varphi }=\varphi$

• 初始化$s$，执行以下流程，直到$s$为终止态；目标是让$\mathrm{\forall }s,\mathrm{\forall }a,Q_{\varphi }(\mathbf{s},\mathbf{a})$都收敛，

• 采样动作状态加入经验池

  • 在状态$s$，选择执行动作$a={\pi }^{ϵ}(s)$，得到奖励$r$、新环境状态$s^{\prime }$
  • 把$(s,a,r,s^{\prime })$ 加入经验池$\mathcal{D}$

• 从$\mathcal{D}$中采样一条数据，$(ss,aa,rr,s{s}^{\prime })$。 （去除样本相关性）

• 计算实际目标值$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})$（解决目标值不稳定的问题）

$$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})=\{\begin{array}{lll}& rr,& s{s}^{\prime }\mathrm{为}\mathrm{终}\mathrm{态}\\ & rr+\gamma \cdot \underset{{\mathbf{a}}^{\prime }}{max}{Q}_{\hat{\varphi }}({\mathbf{ss}}^{\prime },{\mathbf{a}}^{\prime }),& \mathrm{其}\mathrm{它}\end{array}$$

• 再计算损失函数，梯度下降法去训练Q网络

$$J(\varphi )={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-y)}^2={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa}))}^2$$

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

• 更新目标Q网络的参数 每隔C步更新：$\hat{\varphi }\leftarrow \varphi$

总结

策略迭代

已知模型。利用贝尔曼方程（算均值）迭代计算出$V(s)$，再算出$Q(s,a)$。选择最好的动作$a$去优化策略$\pi (s)$。

$$\mathrm{\forall }s,V^{\pi }(s)=E_{a\sim \pi (a\mid s)}{E}_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$$$\mathrm{\forall }s,\pi (s)=\arg \underset{a}{max}Q(s,a)$$

值迭代

已知模型。利用贝尔曼最优方程迭代算出$V(s)$，再算出$Q(s,a)$。选择最好的动作$a$去优化策略$\pi (s)$。

$$\mathrm{\forall }s\in S,V^{\ast }(s)=\underset{a}{max}{E}_{s^{\prime }\sim p(s^{\prime }\mid s,a)}[r(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$$$$Q^{\pi }(s,a)=E_{s\prime \sim p(s\prime \mid s,a)}[r(s,a,s\prime )+\gamma V^{\pi }(s\prime )]$$$$\mathrm{\forall }s,\pi (s)=\arg \underset{a}{max}Q(s,a)$$

蒙特卡罗

未知模型。从$(s,a)$随机游走，采集N个样本。使用所有轨迹回报平均值近似估计$Q(s,a)$ ，再去改进策略。重复，直至收敛。

$$Q^{\pi }(s,a)\approx {\hat{Q}}^{\pi }(s,a)=\frac{1}{N}\sum _{n=1}^{N}G({\tau }^{(n)})$$

时序差分算法

无需知道完整轨迹就能对策略进行评估。

时序差分学习=动态规划-贝尔曼估计$G(\tau )$ + 蒙特卡罗采样-增量计算$Q(s,a)$

贝尔曼估计轨迹总回报$G(\tau )$

$$G(\tau )\leftarrow r(s,a,s^{\prime })+\gamma \cdot Q(s^{\prime },a^{\prime })$$

增量计算$Q(s,a)$

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (\underset{\mathrm{实}\mathrm{际}\mathrm{值}}{\underbrace{r+\gamma \cdot Q(s^{\prime },a^{\prime })}}-\underset{\mathrm{预}\mathrm{期}\mathrm{值}}{\underbrace{Q(s,a)}})$$

SARSA

同策略的时序差分算法，是Q学习的改进。

1、当前状态$s$，当前动作$a$ （初始时选择$a={\pi }^{ϵ}(s)$，后续是更新得到的）

2、执行动作$a$，得到新状态$s^{\prime }$，得到奖励$r(s,a,s^{\prime })$

4、依概率选择新动作$a={\pi }^{ϵ}(s^{\prime })$，新状态新动作的值函数：$Q(s^{\prime },a^{\prime })$

5、更新Q函数

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

6、更新状态和动作：$s=s^{\prime },a=a^{\prime }$

Q学习

1、当前状态$s$，选择当前动作$a={\pi }^{ϵ}(s)$

2、执行动作$a$、得到新状态$s^{\prime }$和奖励 $r(s,a,s^{\prime })$

3、不依概率选择新动作，而是直接选择最大的值函数$\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$

4、更新Q函数

$$Q(s,a)\leftarrow Q(s,a)+\alpha \cdot (r+\gamma \cdot \underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })-Q(s,a))$$

5、更新状态：$s=s^{\prime }$

Q网络

使用神经网络$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})$去近似值函数$Q(s,a)$。两个问题：实际目标值不稳定；样本之间具有强相关性。

$$L(s,a,s^{\prime };\varphi )={(\underset{\mathrm{实}\mathrm{际}\mathrm{目}\mathrm{标}\mathrm{值}}{\underbrace{r+\gamma \cdot \underset{a^{\prime }}{max}{Q}_{\varphi }({\mathbf{s}}^{\prime },{\mathbf{a}}^{\prime })}}-\underset{\text{网络值}}{\underbrace{Q_{\varphi }(\mathbf{s},\mathbf{a})}})}^2$$

DQN

深度Q网络：

• 目标网络冻结-稳定目标值。$Q_{\varphi }(\mathbf{s}\mathbf{,}\mathbf{a})$训练网络，$Q_{\hat{\varphi }}(\mathbf{s}\mathbf{,}\mathbf{a})$目标值网络。定期更新参数$\hat{\varphi }\leftarrow \varphi$
• 经验池的经验回放-去除样本相关性- 每次采集一条数据放入经验池，再从经验池取数据进行训练。

生成新数据加入经验池

1、状态$s$， 选择动作$a={\pi }^{ϵ}(s)$

2、执行动作$a$， 得到$r$和$s^{\prime }$

3、$(s,a,r,s^{\prime })$ 加入经验池$\mathcal{D}$

采经验池中采样一条数据计算

1、从$\mathcal{D}$中采样一条数据，$(ss,aa,rr,s{s}^{\prime })$。 （去除样本相关性）

2、计算实际目标值$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})$。 （解决目标值不稳定的问题）

$$Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa})=\{\begin{array}{lll}& rr,& s{s}^{\prime }\mathrm{为}\mathrm{终}\mathrm{态}\\ & rr+\gamma \cdot \underset{{\mathbf{a}}^{\prime }}{max}{Q}_{\hat{\varphi }}({\mathbf{ss}}^{\prime },{\mathbf{a}}^{\prime }),& \mathrm{其}\mathrm{它}\end{array}$$

3、损失函数如下，梯度下降法去训练Q网络

$$J(\varphi )={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-y)}^2={(Q_{\varphi }(\mathbf{ss},\mathbf{aa})-Q_{\hat{\psi }}(\mathbf{ss}\mathbf{,}\mathbf{aa}))}^2$$

状态前进

$s\leftarrow s^{\prime }$

更新目标Q网络的参数

每隔C步更新：$\hat{\varphi }\leftarrow \varphi$