强化学习笔记（三）

二、经典强化学习

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{aligned} \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{aligned} $$
- 代入梯度更新公式：更新值=步长 × 预测误差 × 特征向量
  $$ \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) $$
- 表查找形式
  $$ \begin{aligned} \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} \end{aligned} $$
使用 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 S1,V{\pi}(S1)\rangle,\langle S_2,V{\pi}(S2)\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 S1,A_1,V{\pi}(S1)\rangle,\langle S_2,A_2,V{\pi}(S2)\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}$中保存$(st,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\mid 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\mid \, 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 算法（蒙特卡洛策略梯度）

通过采样轨迹来估计策略梯度
通过随机梯度上升法更新策略参数
使用回报$vt$作为$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. 执行动作$at$，观察奖励$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. 重复直到达到终止状态
兼容函数逼近定理
- 如果满足以下两个条件
  - 价值函数逼近器与策略兼容：$\nablawQ_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}\mid s,a\right] & =\mathbb{E}_{\pi_\theta}\left[r+\gamma V^{\pi_\theta}(s^{\prime})\mid 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)} $$
  其中：
  - $\deltat = 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}\mid s,a]=\mathbb{P}[s^{\prime}\mid s,a]\mathbb{P}[r^{\prime}\mid 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)$
- 选择当前的真实动作：$at=\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^{\prime}, A^{\prime}) - 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\mid 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 在整个学习过程中错失的最大累积奖励
  - $Lt=\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}\left[N_t(a)\right](V^*-Q(a)) \\ & =\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\mid \Delta_a>0}\Delta_i \\ & \epsilon_{t}=\min\left\{1,\frac{c\mid \mathcal{A}\mid }{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\mid \Delta_a>0}\frac{\Delta_a}{KL(\mathcal{R}^a\mid \mid \mathcal{R}^{a^*})} $$
- 在某些策略下，随着时间推移，探索的频率逐渐降低，而 Regret 损失的增长速率也可能与时间成对数关系
- 求和表示考虑所有次优动作（即那些与最优动作$a^{\star}$的奖励差$\Delta_a$的动作），这些动作的选择导致了 Regret 损失的产生
- $KL(\mathcal{R}^a\mid \mid \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{aligned} \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{aligned} $$
  - 取$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\mid \Delta_a>0}\Delta_a$
- 贝叶斯方法
  - 基本思想
    - 假设已知奖励$\mathcal{R}$的先验概率分布$p[\mathcal{R}]$
    - 然后计算在历史$hr=a_1,r_1,\cdots,a{t-1},r_{t-1}$下的后验概率分布$p[\mathcal{R}\mid 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}\mid 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}\mid \tilde{s},a)$
    - 信息奖励函数：$\mathcal{\tilde{R}}$
    - 折扣因子：$\gamma$
  - 这是一个无限 MDP 问题
- 如何解决信息状态空间的 MDP 问题
  - Model-Free 强化学习
  - 贝叶斯 Model-Based 强化学习
    - 贝叶斯适应强化学习
    - Gittins Indices