主题：马尔可夫决策过程、动态规划、无模型值函数估计（蒙特卡洛 / 时序差分）

---

一、强化学习基础与马尔可夫决策过程

1. 强化学习核心要素

• 智能体与环境：智能体通过试错交互，在每个时间步观察状态、执行动作、获得奖励，目标是最大化累积折扣奖励。
• 策略 (Policy) $\pi (a|s)$：状态到动作的映射，可以是确定性 $a=\pi (s)$ 或随机性 $\pi (a|s)=P(A_t=a\mid S_t=s)$。
• 奖励 (Reward) $R(s,a)$：即时标量信号，定义任务目标。
• 价值函数 (Value Function)：长期累积奖励的期望，评价状态或动作的“好坏”。
  • 状态价值：$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[{\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}\mid S_t=s\right]$
  • 动作价值：$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[{\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}\mid S_t=s,A_t=a\right]$
• 模型 (Model)：状态转移概率 $P_{s{s}^{\prime }}^a=P(S_{t+1}=s^{\prime }\mid S_t=s,A_t=a)$ 和奖励函数，用于规划。

2. 马尔可夫决策过程 (MDP)

MDP 形式化描述完全可观测的随机序贯决策问题，满足马尔可夫性：未来只依赖于当前状态和动作。

• 五元组：$(S,A,P,R,\gamma )$

  • $S$：状态空间（有限或无限）
  • $A$：动作空间
  • $P_{s{s}^{\prime }}^a$：状态转移概率
  • $R(s,a)$：期望即时奖励
  • $\gamma \in [0,1]$：折扣因子

• Bellman 期望方程（对于策略 $\pi$）：
  $$V^{\pi }(s)=\sum _a\pi (a|s)\left[R(s,a)+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^a{V}^{\pi }(s^{\prime })\right]$$
  $$Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^a\sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })$$

3. 最优价值函数与 Bellman 最优方程

• 最优状态价值 $V^{\ast }(s)={\max }_{\pi }{V}^{\pi }(s)$，最优动作价值 $Q^{\ast }(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$。
• Bellman 最优方程：
  $$V^{\ast }(s)=\underset{a}{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })\right]$$
  $$Q^{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^a\underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })$$
• 最优策略：${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)$。

---

二、动态规划：基于模型的值函数求解

当 MDP 模型（$P$ 和 $R$）已知时，可以用动态规划求解最优值函数和策略。

1. 策略迭代 (Policy Iteration)

1. 策略评估：迭代计算当前策略 $\pi$ 的价值函数，直到收敛。
   $$V_{k+1}(s)=\sum _a\pi (a|s)\left[R(s,a)+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^a{V}_k(s^{\prime })\right]$$
2. 策略改进：贪心更新策略 ${\pi }^{\prime }(s)=\arg {\max }_a{\sum }_{s^{\prime }}{P}_{s{s}^{\prime }}^{a}V(s^{\prime })$。
3. 重复直到策略不再变化。

特点：收敛快（通常少次迭代），但每次策略评估需要完整求解线性方程组或多次迭代，计算开销较大。

2. 价值迭代 (Value Iteration)

直接使用 Bellman 最优方程进行更新，无需显式维护策略：
$$V_{k+1}(s)=\underset{a}{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }}{P}_{s{s}^{\prime }}^a{V}_k(s^{\prime })\right]$$
特点：每轮更新同时改进价值与隐含策略，适用于大规模状态空间；收敛至 $V^{\ast }$。

方法	更新方式	优点	缺点
策略迭代	评估+改进交替	迭代次数少	评估步骤计算昂贵
价值迭代	直接最优贝尔曼更新	实现简单，效率高	需足够多轮达到最优

---

三、无模型值函数估计

当 MDP 模型未知时，只能从经验片段（episodes）中学习。常用方法：蒙特卡洛 (MC) 和时序差分 (TD)。

1. 蒙特卡洛方法 (MC)

核心思想：通过采样完整片段，用实际累积回报 $G_t$ 的均值估计价值函数。只适用于幕式任务（有终止状态）。

• 累积回报：$G_t=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{T-1}{R}_T$
• 更新规则（每次访问）：
  $$V(S_t)\leftarrow V(S_t)+\alpha (G_t-V(S_t)),\text{或增量平均}V(S_t)\leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t))$$

特点：

• 无偏估计：$G_t$ 是 $V^{\pi }(s)$ 的无偏估计。
• 高方差：依赖于多步随机动作、状态转移和奖励。
• 限制：必须等片段结束才能更新；不适用于持续任务。

2. 时序差分学习 (TD)

核心思想：结合采样与自举 (bootstrapping)，用当前估计的后续状态价值更新当前价值。

• TD(0) 更新：
  $$V(S_t)\leftarrow V(S_t)+\alpha \left[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\right]$$
  其中 $R_{t+1}+\gamma V(S_{t+1})$ 称为 TD目标，${\delta }_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ 为 TD误差。

特点：

• 在线学习：每一步都可更新，无需等待片段结束。
• 有偏估计：TD目标依赖当前估计 $V(S_{t+1})$，引入偏差，但方差低（仅依赖单步随机性）。
• 适用于持续任务和片段任务，实际中通常比 MC 更高效。

3. MC vs TD：详细对比

维度	蒙特卡洛 (MC)	时序差分 (TD)
更新依据	完整回报 $G_t$	单步奖励 + 下一状态价值估计
偏差 / 方差	无偏，高方差	有偏，低方差
自举 (Bootstrapping)	无	有（依赖当前估计）
收敛性（表格）	收敛到真值，对初值不敏感	收敛到真值，对初值略敏感
更新时机	片段结束后	每一步后
适用环境	片段任务	片段/持续任务

4. 驾车回家的例子

• MC：必须完整到家后才能重新估计各路段耗时。
• TD：每经过一个路段，立即根据新情况更新剩余时间预测，更灵活。

---

四、重要性采样与离策略评估

离策略学习：从行为策略 $\mu$ 产生的数据中评估目标策略 $\pi$（$\pi \ne \mu$）。

• 重要性采样比率：
  $${\rho }_{t:T-1}=\prod _{k=t}^{T-1}\frac{\pi (a_k|s_k)}{\mu (a_k|s_k)}$$
• MC 重要性采样：用加权回报 $G_t^{\pi /\mu }={\rho }_{t:T-1}{G}_t$ 进行更新。
  • 缺点：方差极大，易不稳定。
• TD 重要性采样：仅需一步比率校正：
  $$V(s_t)\leftarrow V(s_t)+\alpha \left(\frac{\pi (a_t|s_t)}{\mu (a_t|s_t)}(r_{t+1}+\gamma V(s_{t+1}))-V(s_t)\right)$$
  • 优点：方差更低，更实用。

---

五、n步TD与统一视角

n步TD是MC和TD(0)的折中，定义n步回报：
$$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}V(S_{t+n})$$
更新规则：
$$V(S_t)\leftarrow V(S_t)+\alpha \left(G_t^{(n)}-V(S_t)\right)$$

• $n=1$：TD(0)
• $n\to \infty$：MC

---

六、探索与利用 (Exploration vs Exploitation)

强化学习中的基本权衡：

• 利用 (Exploitation)：根据当前知识选择最优动作。
• 探索 (Exploration)：尝试新动作以获取更多信息，可能发现更优策略。

常用探索策略：

• ε-greedy：以 $1-\epsilon$ 概率贪心，$\epsilon$ 概率随机均匀选择。
• 乐观初始化：初始价值估计偏高，鼓励未充分访问的状态。
• UCB (Upper Confidence Bound)：基于不确定性度量。

多臂老虎机 (Multi-Armed Bandit) 作为无状态RL实例：

• 目标：最小化累积遗憾 (Regret)
• 理论上最优 regret 为 $O(\log T)$
• ε-衰减可达到次线性 regret

---

七、方法选择指南与实用建议

场景	推荐方法
已知 MDP 模型，小规模状态空间	动态规划（策略迭代/价值迭代）
无模型，片段任务，可接受高方差	蒙特卡洛 (MC)
无模型，在线/持续任务，方差敏感	时序差分 (TD)
离策略评估/控制	重要性采样 + TD（如 Q-learning）

主流深度强化学习（后续课程）基于 TD 和函数近似（神经网络），如 DQN、DDPG、PPO 等。

---

八、关键公式速查表

名称	公式
Bellman 期望方程	$V^{\pi }(s)={\sum }_a\pi (a|s)\left[R(s,a)+\gamma {\sum }_{s^{\prime }}{P}_{s{s}^{\prime }}^a{V}^{\pi }(s^{\prime })\right]$
Bellman 最优方程	$V^{\ast }(s)={\max }_a\left[R(s,a)+\gamma {\sum }_{s^{\prime }}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })\right]$
蒙特卡洛更新	$V(S_t)\leftarrow V(S_t)+\alpha (G_t-V(S_t))$
TD(0) 更新	$V(S_t)\leftarrow V(S_t)+\alpha (R_{t+1}+\gamma V(S_{t+1})-V(S_t))$
n步回报	$G_t^{(n)}={\sum }_{i=1}^n{\gamma }^{i-1}{R}_{t+i}+{\gamma }^{n}V(S_{t+n})$
重要性采样比率	${\rho }_{t:T-1}={\prod }_{k=t}^{T-1}\frac{\pi (a_k|s_k)}{\mu (a_k|s_k)}$