强化学习笔记（三）

二、经典强化学习

2.6 函数逼近

2.6.1 函数逼近

• 基本思想

  • 通过建立表格来存储每个状态-动作对的价值是不现实的，难以应用于大规模强化学习问题或连续状态空间
  • 如何通过泛化，建立有效的方法

• 价值函数逼近

  • 能够从已经见到的状态泛化到未见状态

  • 通过MC或TD学习更新参数$\mathbf{w}$
    $$
    \begin{aligned}
    \hat{v}(s,\mathbf{w}) & \approx v_{\pi}(s) \
    \mathrm{or~}\hat{q}(s,a,\mathbf{w}) & \approx q_{\pi}(s,a)
    \end{aligned}
    $$

  • 函数逼近器有哪些？特征的线性组合、神经网络、决策树、最近邻、傅里叶/小波基

  • 可微函数逼近器有哪些？特征的线性组合、神经网络

  • 同时还需要能够训练非平稳、非独立同分布数据

2.6.2 增量方法

• 利用梯度下降法，找到局部最小值

  • $J(\mathbf{w})$是损失函数，要通过梯度下降法，最小化损失函数，以优化模型参数
    $$
    \begin{aligned}
    J(\mathbf{w}) &=\mathbb{E}\pi\left[(v_\pi(S)-\hat{v}(S,\mathbf{w}))^2\right]\
    \Delta \mathbf{w} & =-\frac{1}{2}\alpha\nabla{\mathbf{w}}J(\mathbf{w}) \
    & =\alpha\mathbb{E}_\pi\left[(v_\pi(S)-\hat{v}(S,\mathbf{w}))\nabla_\mathbf{w}\hat{v}(S,\mathbf{w})\right]\
    \end{aligned}
    $$
  • 其中，$\nabla_\mathbf{w}\hat{v}(S,\mathbf{w})$即表示模型对参数$\mathbb{w}$的梯度，表示模型参数变化时，预测值的变化量

• 随机梯度下降法采样梯度，收敛于全局最优值
  $$
  \Delta\mathbf{w}=\alpha(v_\pi(S)-\hat{v}(S,\mathbf{w}))\nabla_\mathbf{w}\hat{v}(S,\mathbf{w})
  $$

• 线性价值函数逼近

  • 使用特征向量表示状态
    $$
    x(S)=\begin{pmatrix}
    \mathbf{x}_1(S) \
    \vdots \
    \mathbf{x}_n(S)
    \end{pmatrix}
    $$

  • 代入梯度公式

  $$
  \begin{align}
  \hat{v}(S,\mathbf{w})&=\mathbf{x}(S)^\top\mathbf{w}=\displaystyle\sum_{j=1}^n\mathbf{x}_j(S)\mathbf{w}_j\
  J(\mathbf{w})&=\mathbb{E}_\pi\left[(v_\pi(S)-\mathbf{x}(S)^\top\mathbf{w})^2\right]\
  \end{align}
  $$

  • 代入梯度更新公式：更新值=步长×预测误差×特征向量
    $$
    \nabla_\mathbf{w}\hat{v}(S,\mathbf{w}) =\mathbf{x}(S)\
    \Delta \mathbf{w} =\alpha(v_\pi(S)-\hat{v}(S,\mathbf{w}))\mathbf{x}(S)
    $$

  • 表查找形式
    $$
    \mathbf{x}^{table}(S)=
    \begin{pmatrix}
    \mathbf{1}(S=s_1) \
    \vdots \
    \mathbf{1}(S=s_n)
    \end{pmatrix}\
    \hat{v}(S,\mathbf{w})=\mathbf{x}^{table}(S)\cdot
    \begin{pmatrix}
    \mathbf{w}_1 \
    \vdots \
    \mathbf{w}_n
    \end{pmatrix}
    $$

• 使用MC或TD作为对$v_{\pi}(s)$的估计

  • 对于MC，估计是$G_t$，收敛于局部最优​
  • 对于TD(0)，估计是TD目标，即$R_{t+1}+r\hat{v}(S_{t+1},w)$，收敛于全局最优
  • 对于前向TD($\lambda$)，估计是$\lambda$-回报$G_t^{\lambda}$​
  • 可以对$\langle S_1,V_{\pi}(S_1)\rangle,\langle S_2,V_{\pi}(S_2)\rangle,…,\langle S_T,V_{\pi}(S_T)\rangle$进行监督学习，来构造逼近函数
  • MC的价值函数逼近
  • TD学习的价值函数逼近

• 动作值函数的函数逼近

  • 目标：$\hat{q}(S,A,\mathbf{w})\approx q_{\pi}(S,A)$
  • 损失函数：$J(\mathbf{w})=\mathbb{E}_\pi\left[(q_\pi(S,A)-\hat{q}(S,A,\mathbf{w}))^2\right]$
  • 随机梯度下降：$\Delta\mathbf{w} = -\frac{1}{2}\alpha\nabla_{\mathbf{w}}J(\mathbf{w}) =\alpha(q_{\pi}(S,A)-\hat{q}(S,A,\mathbf{w}))\nabla_{\mathbf{w}}\hat{q}(S,A,\mathbf{w})$
  • 使用特征向量表示状态-动作
    $$
    \begin{aligned}
    \mathbf{x}(S,A)&=
    \begin{pmatrix}
    \mathbf{x}{1}(S,A) \
    \vdots \
    \mathbf{x}{n}(S,A)
    \end{pmatrix}\
    \hat{q}(S,A,\mathbf{w})&=\mathbf{x}(S,A)^\top\mathbf{w}=\sum_{j=1}^n\mathbf{x}_j(S,A)\mathbf{w}_j\
    \nabla_\mathbf{w}\hat{q}(S,A,\mathbf{w}) & =\mathbf{x}(S,A) \
    \Delta \mathbf{w} & =\alpha(q_\pi(S,A)-\hat{q}(S,A,\mathbf{w}))\mathbf{x}(S,A)
    \end{aligned}
    $$
  • 使用MC或TD作为对$q_{\pi}(S,A)$的估计
    • 对于MC，估计是$G_t$，收敛于局部最优
    • 对于TD(0)，估计是TD目标，即$R_{t+1}+\gamma\hat{q}(S_{t+1},A_{t+1},\mathbf{w})$，收敛于全局最优
    • 对于TD($\lambda$)，估计是$\lambda$-回报$q_t^{\lambda}$
    • 可以对$\langle S_1,A_1,V_{\pi}(S_1)\rangle,\langle S_2,A_2,V_{\pi}(S_2)\rangle,…,\langle S_T,A_T,V_{\pi}(S_T)\rangle$进行监督学习，来构造逼近函数

2.6.3 批量方法

• 基本思想

  • 梯度下降方法中数据被逐步处理（逐样本或小批量），每次更新仅依赖于当前样本或小批量样本，没有充分利用数据

• 最小二乘法找到的参数$\mathbf{w}$最小化平方和误差
  $$
  \begin{aligned}
  LS(\mathbf{w}) & =\displaystyle\sum_{t=1}^T(v_t^\pi-\hat{v}(s_t,\mathbf{w}))^2 \
  & =\mathbb{E}_{\mathcal{D}}\left[(v^{\pi}-\hat{v}(s,\mathbf{w}))^{2}\right]
  \end{aligned}
  $$

• 如何找到最小二乘解

  • 从经历中采样状态-值：$\langle s,v^{\pi}\rangle\sim \mathcal{D}$
  • 应用随机梯度下降更新：$\Delta\mathbf{w}=\alpha(v^\pi-\hat{v}(s,\mathbf{w}))\nabla_\mathbf{w}\hat{v}(s,\mathbf{w})$​
  • 收敛至最小二乘解：$\mathbf{w}^{\pi}=\arg\min_{\mathbf{w}} LS(\mathbf{w})$​

• DQN

  • 经验回放（Experience replay）
    • 将智能体的交互数据存储到一个回放缓冲区（Replay Buffer）中，并从中随机采样小批量数据来训练神经网络，而不是直接使用最新的数据
      • 在经验池$\mathcal{D}$中保存$(s_t,a_t,r_{t+1},s_{t+1})$
      • 从经验池中采样随机的小批量$(s,a,r,s^{\prime})$
  • 固定Q-学习目标网络
    • 引入一个目标网络（Target Network）来稳定目标值的计算
    • 主网络（Online Network）：实时更新，用来选择动作并估计 Q 值
    • 目标网络（Target Network）：延迟更新，提供相对稳定的目标 Q 值
  • 用主网络预测当前状态的Q值，即$q=Q(s,a;w_i)$
  • 用目标网络计算目标值$\hat{q}=r+\gamma\displaystyle\max_{a^\prime}Q_{target}(s^\prime,a^\prime;w_i^-)$
  • 计算两者之间的均方误差作为损失函数
    $$
    \mathcal{L}i(w_i)=\mathbb{E}{s,a,r,s^{\prime}\sim\mathcal{D}i}\left[\left(r+\gamma\displaystyle\max{a^{\prime}}Q(s^{\prime},a^{\prime};w_i^-)-Q(s,a;w_i)\right)^2\right]
    $$

• 线性最小二乘

  • 给定线性函数逼近$\hat{v}(S,\mathbf{w})=\mathbf{x}(S)^\top\mathbf{w}$
  • 当取$\min LS(\mathbb{w})$时，$E_{\mathcal{D}}[\Delta\mathbb{w}]=0$，即
    $$
    \begin{aligned}
    \mathbb{E}{\mathcal{D}}\left[\Delta\mathbf{w}\right] & =0 \
    \alpha\sum{t=1}^T\mathbf{x}(s_t)(v_t^\pi-\mathbf{x}(s_t)^\top\mathbf{w}) & =0 \
    \sum_{t=1}^T\mathbf{x}(s_t)v_t^\pi & =\sum_{t=1}^T\mathbf{x}(s_t)\mathbf{x}(s_t)^\top\mathbf{w} \
    \mathrm{w} & =\left(\sum_{t=1}^T\mathbf{x}(s_t)\mathbf{x}(s_t)^\top\right)^{-1}\sum_{t=1}^T\mathbf{x}(s_t)v_t^\pi
    \end{aligned}
    $$
  • 对于$N$维特征向量，时间复杂度为$O(N^3)$；采用增量方法（Shermann-Morrison）解决，时间复杂度为$O(N^2)$
  • 使用MC/TD估计$v_t^\pi$

• 最小二乘Q-Learning（LSTDQ）

  • 目标：线性逼近$\hat{Q}(s,a;\mathbf{w})=\mathbf{x}(s,a)^\top\mathbf{w}$
  • 损失函数：$LS(\mathbf{w})=\mathbb{E}_{\mathcal{D}}\left[(Q(s,a)-\hat{Q}(s,a;\mathbf{w}))^2\right]$
  • 计算$\mathcal{w}$
    $$
    \begin{aligned}
    \delta & =R_{t+1}+\gamma\hat{q}(S_{t+1},\pi(S_{t+1}),\mathbf{w})-\hat{q}(S_{t},A_{t},\mathbf{w}) \
    \Delta\mathbf{w} & =\alpha\delta\mathbf{x}(S_{t},A_{t})\
    0 & =\sum_{t=1}^{T}\alpha(R_{t+1}+\gamma\hat{q}(S_{t+1},\pi(S_{t+1}),\mathbf{w})-\hat{q}(S_{t},A_{t},\mathbf{w}))\mathbf{x}(S_{t},A_{t}) \
    \mathbf{w} & =\left(\sum_{t=1}^{T}\mathbf{x}(S_{t},A_{t})(\mathbf{x}(S_{t},A_{t})-\gamma\mathbf{x}(S_{t+1},\pi(S_{t+1})))^{\top}\right)^{-1}\sum_{t=1}^{T}\mathbf{x}(S_{t},A_{t})R_{t+1}
    \end{aligned}
    $$

• 最小二乘策略迭代（Least Squares Policy Iteration）

  function LSPI-TD(D, π₀)
      π′ ← π₀
      repeat
          π ← π′
          Q ← LSTDQ(π, D)  // 通过最小二乘 TD-Q 方法计算 Q 函数
          for all s ∈ S do
              π′(s) ← argmaxₐ Q(s, a)  // 策略改进
          end for
      until (π ≈ π′)  // 判断策略是否收敛
      return π
  end function

2.7 策略梯度

2.7.1 策略梯度方法

• 类似于函数逼近价值函数和动作值函数，可以直接对策略进行逼近，即$\pi_{\theta}(s,a)=\mathbb{P}[a|s,\theta]$
  • 基于价值的：学习价值函数，隐式的策略
  • 基于策略的：学习策略，没有价值函数
    • 更好的收敛性质，但是通常收敛到局部最优解
    • 在高维或连续动作空间中更有效
    • 可以学习随机策略
    • 评估策略通常不高效而且方差较大
  • Actor-Critic：学习价值函数和策略
• 策略目标函数：如何评估策略$\pi_{\theta}$的质量
  • 在Episodic环境中，使用起始状态
    $$
    J(\theta) = V^{\pi_{\theta}}(s_0) = \mathbb{E}{\pi{\theta}}[v_0]=\mathbb{E}{\pi{\theta}} \left[ \displaystyle\sum_{t=0}^{T-1} \gamma^t r_t ,\Big|, s_0 \right]
    $$
  • 在连续环境中，使用值函数的平均值
    $$
    J_{avV}(\theta)=\displaystyle\sum_sd^{\pi_\theta}(s)V^{\pi_\theta}(s)
    $$
  • 在连续环境中，使用每个时间步的平均奖励
    $$
    J_{avR}(\theta)=\displaystyle\sum_sd^{\pi_\theta}(s)\displaystyle\sum_a\pi_\theta(s,a)\mathcal{R}_s^a
    $$
  • 其中，$d^{\pi_\theta}(s)$是$\pi_\theta$的稳态概率分布
• 对策略目标函数$J(\theta)$使用梯度上升法
  • $\Delta\theta=\alpha\nabla_\theta J(\theta)$
  • 其中$\nabla_\theta J(\theta)$即为策略梯度
    $$
    \nabla_\theta J(\theta)=
    \begin{pmatrix}
    \frac{\partial J(\theta)}{\partial\theta_1} \
    \vdots \
    \frac{\partial J(\theta)}{\partial\theta_n}
    \end{pmatrix}
    $$
  • 通过有限差分计算梯度
    • 对于每个维度$k\in[1,n]$，估计目标函数的 k 阶偏导数
      $$
      \frac{\partial J(\theta)}{\partial\theta_k}\approx\frac{J(\theta+\epsilon\mathbf{u}_k)-J(\theta)}{\epsilon}
      $$
  • 策略梯度定理（Policy Gradient Theorem）
    • 似然比（Likelihood ratios）
      $$
      \begin{aligned}
      \nabla_\theta\pi_\theta(s,a) & =\pi_\theta(s,a)\frac{\nabla_\theta\pi_\theta(s,a)}{\pi_\theta(s,a)} \
      & =\pi_\theta(s,a)\nabla_\theta\log\pi_\theta(s,a)\
      \end{aligned}
      $$
    • Score函数即为$\nabla_\theta\log\pi_\theta(s,a)$
    • 对于任意可微策略和任意策略目标函数，策略梯度为
      $$
      \nabla_\theta J(\theta)=\mathbb{E}_{\pi_\theta}\left[\nabla_\theta\log\pi_\theta(s,a)Q^{\pi_\theta}(s,a)\right]
      $$

2.7.2 REINFORCE算法（蒙特卡洛策略梯度）

• 通过采样轨迹来估计策略梯度
• 通过随机梯度上升法更新策略参数
• 使用回报$v_t$作为$Q^{\pi_\theta}(s,a)$的无偏估计
  $$
  \Delta\theta_{t}= \alpha\nabla_\theta\log\pi_\theta(s_t,a_t)v_t
  $$

2.7.3 Actor-Critic算法

• 蒙特卡洛策略梯度存在高方差问题
• 使用Critic去估计动作值函数$Q^{\pi_\theta}(s,a)$，Actor根据Critic的估计更新策略
  • Critic更新动作值函数的参数$\mathbf{w}$，即$Q_{\mathbf{w}}(s,a)\approx Q^{\pi_\theta}(s,a)$
  • Actor更新策略的参数$\theta$，根据Critic建议的方向
• 遵循逼近策略梯度定理
  $$
  \begin{aligned}
  \nabla_\theta J(\theta)&\approx\mathbb{E}{\pi_\theta}\left[\nabla_\theta\log\pi_\theta(s,a)Q{\mathbf{w}}(s,a)\right]\
  \Delta\theta_t&=\alpha\nabla_\theta\log\pi_\theta(s_t,a_t)Q_{\mathbf{w}}(s_t,a_t)
  \end{aligned}
  $$
• 算法流程
  • Critic使用线性函数逼近器，即$Q_{\mathbf{w}}(s,a)=\mathbf{\phi}(s,a)^\top\mathbf{w}$，使用TD(0)逼近
  • 初始化策略参数$\theta$和动作值函数参数$\mathbf{w}$
  • 循环更新
    1. 从起始状态$s_0$开始
    2. 根据策略$\pi_\theta$选择动作$a_t$
    3. 执行动作$a_t$，观察奖励$r_{t+1}$和下一状态$s_{t+1}$
    4. 根据策略选择下一动作$a_{t+1}$
    5. 更新动作值函数
       $$
       \begin{aligned}
       \delta&=r_{t+1}+\gamma Q_{\mathbf{w}}(s_{t+1},a_{t+1})-Q_{\mathbf{w}}(s_t,a_t)\
       \mathbf{w}&\leftarrow\mathbf{w}+\beta\delta\mathbf{\phi}(s_t,a_t)
       \end{aligned}
       $$
    6. 更新策略
       $$
       \theta\leftarrow\theta+\alpha\nabla_\theta\log\pi_\theta(s_t,a_t)Q_{\mathbf{w}}(s_t,a_t)
       $$
    7. 将状态和动作更新为$s_{t+1}$和$a_{t+1}$
    8. 重复直到达到终止状态
• 兼容函数逼近定理
  • 如果满足以下两个条件
    • 价值函数逼近器与策略兼容：$\nabla_wQ_w(s,a)=\nabla_\theta\log\pi_\theta(s,a)$
    • 价值函数的参数$w$最小化均方误差：$\varepsilon=\mathbb{E}_{\pi_\theta}\left[(Q^{\pi_\theta}(s,a)-Q_w(s,a))^2\right]$
  • 那么策略梯度即为$\nabla_\theta J(\theta)=\mathbb{E}_{\pi_\theta}\left[\nabla_\theta\log\pi_\theta(s,a)\mathrm{~}Q_w(s,a)\right]$

2.7.4 优势函数

• 选择基线函数$B(s)$减少方差而不改变期望，即满足
  $$
  \begin{aligned}
  \mathbb{E}{\pi_\theta}\left[\nabla_\theta\log\pi_\theta(s,a)B(s)\right] & =\displaystyle\sum{s\in S}d^{\pi_\theta}(s)\displaystyle\sum_a\nabla_\theta\pi_\theta(s,a)B(s) \
  & =\displaystyle\sum_{s\in\mathcal{S}}d^{\pi_\theta}B(s)\nabla_\theta\displaystyle\sum_{a\in\mathcal{A}}\pi_\theta(s,a) \
  & =0
  \end{aligned}
  $$

• 可以选择状态值函数$B(s)=V^{\pi_\theta}(s)$，则有优势函数$A^{\pi_\theta}(s,a)$
  $$
  \begin{aligned}
  A^{\pi_\theta}(s,a) & =Q^{\pi_\theta}(s,a)-V^{\pi_\theta}(s) \
  \nabla_\theta J(\theta) & =\mathbb{E}_{\pi_\theta}\left[\nabla_\theta\log\pi_\theta(s,a)\right.A^{\pi_\theta}(s,a)]
  \end{aligned}
  $$

• 优势函数实际上表示着在状态$s$下，选取动作$a$相对于其他情况的优势

• 优势函数可以显著减少策略梯度的方差，从而Critic应该预估优势函数——采用两个函数逼近器和两个参数向量
  $$
  \begin{aligned}
  V_v(s) & \approx V^{\pi_\theta}(s) \
  Q_w(s,a) & \approx Q^{\pi_\theta}(s,a) \
  A(s,a) & =Q_w(s,a)-V_v(s)
  \end{aligned}
  $$

• TD误差$\delta^{\pi_\theta}$是优势函数的无偏估计
  $$
  \begin{aligned}
  \delta^{\pi_\theta}&=r+\gamma V^{\pi_\theta}(s^{\prime})-V^{\pi_\theta}(s)\
  \mathbb{E}{\pi_\theta}\left[\delta^{\pi_\theta}|s,a\right] & =\mathbb{E}{\pi_\theta}\left[r+\gamma V^{\pi_\theta}(s^{\prime})|s,a\right]-V^{\pi_\theta}(s) \
  & =Q^{\pi_\theta}(s,a)-V^{\pi_\theta}(s) \
  & =A^{\pi_\theta}(s,a)\
  \nabla_\theta J(\theta) & =\mathbb{E}_{\pi_\theta}\left[\nabla_\theta\log\pi_\theta(s,a)\right.\delta^{\pi_\theta}]
  \end{aligned}
  $$

• 在实际情况，可以使用估计TD误差$\delta_v=r+\gamma V_v(s^{\prime})-V_v(s)$​

• 优势函数（Advantage Function）

  • 定义：优势函数 $A_t$ 衡量当前动作 $a_t$ 相对于当前策略下平均动作的优势

  • 广义优势估计（Generalized Advantage Estimation, GAE）
    $$
    A_t^{\text{GAE}(\gamma, \lambda)} = \displaystyle\sum_{l=0}^{\infty} (\gamma \lambda)^l \delta_{t+l}
    $$
    或递推形式：
    $$
    A_t^{\text{GAE}(\gamma, \lambda)} = \delta_t + \gamma \lambda A_{t+1}^{\text{GAE}(\gamma, \lambda)}
    $$
    其中：

    • $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$：一步 TD 误差。
    • $\gamma$：折扣因子，控制未来奖励的重要性。
    • $\lambda$：平滑参数，控制 TD 误差的加权衰减。
    • $l$：从当前时间步 $t$ 开始累积 TD 误差的步数。

2.8 基于模型的强化学习

2.8.1 基于模型的强化学习

• 什么是基于模型的强化学习
  • 从经历中直接学习环境的模型
  • 通过规划来学习策略或价值函数
  • 缺点：累积近似误差
  • 价值/策略–采取动作–>经历–模型学习–>模型–规划–>价值/策略
• 什么是模型
  • 模型是一个MDP过程的表示$\mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R}\rangle$，以$\eta$参数化
  • 假设状态空间和动作空间是已知的，那么$\mathcal{M}=\langle\mathcal{P}_\eta,\mathcal{R}_\eta\rangle$
  • 其中$\mathcal{P}_\eta\approx\mathcal{P}$且$\mathcal{R}_\eta\approx\mathcal{R}$
  • 通常假设状态转移和奖励是条件独立的，即$\mathbb{P}[s^{\prime},r^{\prime}|s,a]=\mathbb{P}[s^{\prime}|s,a]\mathbb{P}[r^{\prime}|s,a]$
• 模型学习
  • 从经历中估计模型$\mathcal{M}_\eta$
  • 监督学习问题
    $$
    \begin{aligned}
    S_{1},A_{1} & \to R_{2},S_{2} \
    S_{2},A_{2} & \to R_{3},S_{3} \
    & \vdots \
    S_{T-1},A_{T-1} & \to R_{T},S_{T}
    \end{aligned}
    $$
  • 学习$s,a\rightarrow r$是一个回归问题
  • 学习$s,a\rightarrow s^{\prime}$是一个密度估计问题
  • 寻找参数$\eta$最小化经验损失
  • 基于模型的强化学习的效果受限于估计得到的模型，当模型是不正确的，规划过程会得到一个次优策略
  • 学习到模型后，采用规划方法来学习策略或价值函数
    • 动态规划
    • Sample-Based Planning：先从模型中采样，然后使用采样数据通过Model-Free方法进行学习

2.8.2 Dyna

• 结合学习和规划
  • 从真实经历中学习模型
  • 从真实和模拟经历中学习和规划策略/价值函数
• Dyna-Q算法
  • 初始化：Q值初始化为某个值（通常为零），并且模型也被初始化为空
  • 与环境交互：执行动作并观察环境的反馈（即状态转移和奖励），然后更新Q值并拟合模型
  • 规划（内部模拟）：使用当前的环境模型模拟一系列可能的状态转移和奖励，并通过这些模拟进行Q值更新
  • 重复：交替进行环境交互和规划，逐渐改进Q值

    initialize Q(s, a) arbitrarily
    initialize model (state, action, reward, next_state) arbitrarily
    
    for each episode:
        initialize state s
        while s is not terminal:
            choose action a using policy derived from Q (e.g., ε-greedy)
            take action a, observe reward r, and next state s'
            update Q(s, a) using Q-learning update rule
            update model with (s, a, r, s')
            
            # Perform planning step (simulate interactions)
            for i = 1 to N:
                randomly choose a state-action pair (s, a)
                get (r, s') from model
                update Q(s, a) using Q-learning update rule

• Dyna-Q+算法
  • 奖励修正
    • 在规划过程中，对于每个模拟的经验（状态、动作、奖励、下一个状态），Dyna-Q+ 会使用一个修正因子来调整奖励值；
    • 这个修正因子是通过比较模型预测的奖励和实际奖励的差异来计算的。具体来说，它会给奖励进行调整，使得模型可以更准确地反映环境的不稳定性。
    • $r^\prime==r+\alpha\cdot(r_{model}-r_{actual})$

      initialize Q(s, a) arbitrarily
      initialize model (state, action, reward, next_state) arbitrarily
      
      for each episode:
          initialize state s
          while s is not terminal:
              choose action a using policy derived from Q (e.g., ε-greedy)
              take action a, observe reward r, and next state s'
              update Q(s, a) using Q-learning update rule
              update model with (s, a, r, s')
              
              # Perform planning step (simulate interactions)
              for i = 1 to N:
                  randomly choose a state-action pair (s, a)
                  get (r_model, s') from model
                  # Apply reward correction
                  r' = r_model + α * (r_model - r_actual)
                  update Q(s, a) using Q-learning update rule with adjusted reward r'

2.8.3 基于模拟的搜索

• 基本思想
  • 不同于采样随机选择状态和动作，可以通过前向搜索算法通过前瞻选择最佳的动作
  • 以当前状态$s_t$为根节点，构造搜索树，无需解决整个MDP，而是只关注子MDP
• 前向搜索范式
  • 基于Sample-Based Planning
  • 使用模型从当前状态开始模拟若干个经历
    $$
    {s_t^k,A_t^k,R_{t+1}^k,…,S_T^k}_{k=1}^K\sim\mathcal{M}_\nu
    $$
  • 应用Model-Free强化学习去模拟经历
    • 蒙特卡洛控制–>蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）
    • SARSA–>时序差分树搜索（Temporal Difference Tree Search, TDTS）
• 简单的蒙特卡洛搜索
  • 从根节点$s_t$开始，对于每一个动作$a_t$
    • 基于固定的策略，模拟$K$次经历
    • 进行蒙特卡洛评估：$Q(s_{t},a)=\frac{1}{K}\displaystyle\sum_{k=1}^{K}G_{t}\xrightarrow{P}q_{\pi}(s_{t},a)$
  • 选择当前的真实动作：$a_t=\arg\displaystyle\max_{a\in\mathcal{A}} Q(s_t,a)$
• 蒙特卡洛树搜索
  • 动态评估状态，不像DP一样探索整个状态空间
  • 使用采样来打破维数诅咒
  • $Q(s,a)=\frac{1}{N(s,a)}\sum_{k=1}^{K}\sum_{u=t}^{T}\mathbf{1}(S_{u},A_{u}=s,a)G_{u}\overset{P}{\operatorname*{\operatorname*{\operatorname*{\to}}}}q_{\pi}(s,a)$
  • 选择-扩展-模拟-回溯更新策略
• TD树搜索
  1. 模拟从当前状态 $s_t$ 开始的 episodes
  2. 估计动作-价值函数 $Q(s, a)$
  3. 通过 Sarsa 更新动作-价值
     $$
     \Delta Q(S, A) = \alpha \left( R + \gamma Q(S’, A’) - Q(S, A) \right)
     $$
  4. 根据动作-价值函数 $Q(s, a)$ 选择动作
     • 例如：$\epsilon$-贪婪策略
  5. 可能使用函数逼近来表示 $Q(s, a)$
• Dyna-2
  • 长期记忆
    • 智能体从环境中通过真实交互获得的一般领域知识，即适用于所有或大部分 episodes 的知识
    • 通过时序差分（TD）学习更新
  • 短期记忆
    • 智能体从模拟经验中获得的特定局部知识，即仅适用于当前特定情境的知识
    • 通过TD 搜索更新；TD 搜索是模拟的经验更新过程，其中智能体使用它所学到的环境模型来生成虚拟的状态转移和奖励，然后基于这些模拟的经验进行更新
  • 价值函数是长期记忆和短期记忆的加权总和
    $$
    V(s) = V_{\text{long}}(s) + V_{\text{short}}(s)
    $$
  • 模拟经验通过模型生成，允许智能体进行规划而不依赖于与环境的每一步交互

2.9 探索与利用

2.9.1 探索与利用

• 探索与利用的权衡
  • 探索：尝试新的动作，获得更多信息，以发现更好的策略
    • 简单探索：探索随机动作，如$\epsilon$贪心，Softmax
    • 面对不确定性时保持乐观：评估不确定性，倾向于选择不确定性最高的状态/动作
    • 信息状态搜索：将Agent的信息作为其状态的一部分，动作选择过程结合了前瞻性搜索，关注通过探索获得的潜在信息如何帮助改进长期策略。
  • 利用：选择当前最好的动作，以获得最大的奖励
• Regret
  • 动作值：$Q(a)=\mathbb{E}[r|a]$
  • 最优价值：$V^{\star}=Q(a^{\star})=\max_{a\in\mathcal{A}}Q(a)$
  • Regret
    • 指在某个时间步$t$，Agent由于选择了次优动作而错失的最大累积奖励
    • $I_t=\mathbb{E}[V^{\star}-Q(a_t)]$
  • 累积Regret
    • Agent在整个学习过程中错失的最大累积奖励
    • $L_t=\mathbb{E}\left[\sum_{\tau=1}^tV^{\star}-Q(a_\tau)\right]$
    • 最大累积奖励=最小累积Regret
  • Regret的计算
    $$
    \begin{aligned}
    L_{t} & =\mathbb{E}\left[\sum_{\tau=1}^tV^*-Q(a_\tau)\right] \
    & =\sum_{a\in\mathcal{A}}\mathbb{E}\leftN_t(a)\right \
    & =\sum_{a\in\mathcal{A}}\mathbb{E}\left[N_t(a)\right]\Delta_a
    \end{aligned}
    $$
    • 其中$\Delta_a$表示动作$a$与最优动作$a^{\star}$之间的差异（Gap）
• 各种策略的Regret
  • 随机策略
    • 动作值函数：$\hat{Q}{t}(a)=\frac{1}{N{t}(a)}\sum_{t=1}^{T}r_{t}\mathbf{1}(a_{t}=a)$
    • 总是选择最优动作：$a_{t}^{}=\underset{a\in\mathcal{A}}{\operatorname{\operatorname*{\operatorname*{\operatorname*{argmax}}}}}\hat{Q}_{t}(a)$
    • 会陷入局部最优解–>线性总Regret
  • $\epsilon$-贪心策略
    • $\epsilon$保证最小Regret：$I_t\ge \frac{\epsilon}{\mathcal{A}}\displaystyle\sum_{a\in\mathcal{A}}\Delta_a$
    • 线性总Regret
  • 下降$\epsilon$-贪心策略
    • 考虑以下$\epsilon$序列
      $$
      \begin{aligned}
      & c>0 \
      & d=\min_{a|\Delta_a>0}\Delta_i \
      & \epsilon_{t}=\min\left{1,\frac{c|\mathcal{A}|}{d^2t}\right}
      \end{aligned}
      $$
    • 对数渐近总Regret
    • 然而，设置合适的$\epsilon$序列需要提前了解有关Gap的信息
    • 目标：对于任意问题，找到一个具有亚线性总Regret的算法
  • Softmax
  • Gaussian noise
• Regret的Lower Bound
  • 渐近总Regret大于某个时间步的对数值
    $$
    \lim_{t\to\infty}L_t\geq\log t\sum_{a|\Delta_a>0}\frac{\Delta_a}{KL(\mathcal{R}^a||\mathcal{R}^{a^*})}
    $$
  • 在某些策略下，随着时间推移，探索的频率逐渐降低，而Regret损失的增长速率也可能与时间成对数关系
  • 求和表示考虑所有次优动作（即那些与最优动作$a^{\star}$的奖励差$\Delta_a$的动作），这些动作的选择导致了Regret损失的产生
  • $KL(\mathcal{R}^a||\mathcal{R}^{a^{\star}})$表示动作$a$的奖励分布$\mathcal{R}^a$与最优动作$a^{\star}$的奖励分布$\mathcal{R}^{a^{\star}}$之间的Kullback-Leibler散度，衡量了选择次优动作时，与最优动作的奖励分布的差异大小
• 面对不确定性时保持乐观
  • Upper Confidence Bound（UCB）算法
    • 对于每个动作值，估计上置信界$\hat{U_t}(a)$，则$Q(a)\le \hat{Q_t}(a)+\hat{U_t}(a)$出现的可能性较大
    • 选择动作时，考虑动作的平均奖励和不确定性
    • 选择具有最大UCB值的动作：$a_t=\underset{a\in\mathcal{A}}{\operatorname*{\operatorname*{\mathrm{ar gmax}}}}\hat{Q}_t(a)+\hat{U}_t(a)$
    • UCB值的计算：$Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}$
    • 其中$Q_t(a)$是动作$a$的平均奖励，$N_t(a)$是动作$a$被选择的次数，$c$是一个探索参数
  • Hoeffding’s Inequality
    • 对于独立同分布的随机变量，其均值的估计值与真实均值之间的差异是以高概率收敛的
      $$
      \begin{align}
      \mathbb{P}\left[\mathbb{E}\left[X\right]>\overline{X}_t+u\right]&\leq e^{-2tu^2}\
      \mathbb{P}\left[Q(a)>\hat{Q}_t(a)+U_t(a)\right]&\leq e^{-2N_t(a)U_t(a)^2}=p\
      U_t(a) & =\sqrt{\frac{-\log p}{2N_t(a)}}
      \end{align}
      $$
    • 取$p=t^{-4}$，则$U_t(a)=\sqrt{\frac{2\log t}{N_t(a)}}$
  • UCB1
    • $a_t=\underset{a\in\mathcal{A}}{\operatorname*{\operatorname*{argmax}}}Q(a)+\sqrt{\frac{2\log t}{N_t(a)}}$
    • 对数渐进总Regret：$\displaystyle\lim_{t\to\infty}L_t\leq8\log t\displaystyle\sum_{a|\Delta_a>0}\Delta_a$
  • 贝叶斯方法
    • 基本思想
      • 假设已知奖励$\mathcal{R}$的先验概率分布$p[\mathcal{R}]$
      • 然后计算在历史$h_r=a_1,r_1,\cdots,a_{t-1},r_{t-1}$下的后验概率分布$p[\mathcal{R}|h_t]$
      • 利用后验概率指导探索
    • 贝叶斯UCB
    • 概率匹配
      • 选择动作$a$满足：$\pi(a\mid h_t)=\mathbb{P}\left[Q(a)>Q(a^{\prime}),\forall a^{\prime}\neq a\mid h_t\right]$
      • 将不确定性表示为概率分布，不确定的动作有更高的概率成为最大
    • Thompson Sampling算法
      • $\pi(a\mid h_t) =\mathbb{E}{\mathcal{R}|h_t}\left[\mathbf{1}(a=\operatorname*{argmax}{a\in\mathcal{A}}Q(a))\right]$
      • 从后验分布中采样一个奖励分布$\mathcal{R}$
      • 计算状态值函数$Q(a)=\mathbb{E}[\mathcal{R}a]$，选择最大的动作$a_t=\displaystyle\operatorname*{argmax}{a\in\mathcal{A}}Q(a)$
      • 更新后验分布
      • 重复以上步骤
• 信息状态搜索
  • 探索获得了信息，如何定量信息的价值，量化该信息能够带来多少长期价值
    • 获取信息后长期奖励-即时奖励
    • 如果我们知道信息的价值，我们就可以最佳地权衡探索和利用
  • 信息状态空间
    • 每一步均有其信息状态$\tilde{s}$：$\tilde{s}$是历史信息的统计，$\tilde{s}=f(h_t)$，总结目前积累的所有信息
    • 信息状态空间是一个MDP，即$\mathcal{M}= \langle \mathcal{\tilde{S}}, \mathcal{A}, \mathcal{\tilde{P}}, \mathcal{R}, \gamma \rangle$
      • 状态：信息状态$\tilde{s}$
      • 动作：选择动作$a$
      • 状态转移：$\mathcal{\tilde{P}}(\tilde{s}^{\prime}|\tilde{s},a)$
      • 信息奖励函数：$\mathcal{\tilde{R}}$
      • 折扣因子：$\gamma$
    • 这是一个无限MDP问题
  • 如何解决信息状态空间的MDP问题
    • Model-Free强化学习
    • 贝叶斯Model-Based强化学习
      • 贝叶斯适应强化学习
      • Gittins Indices