强化学习基础#
本文从有限马尔可夫决策过程出发，依次介绍回报、价值函数与贝尔曼方程，并进一步梳理基于模型的动态规划方法和无模型强化学习方法，形成从策略评估到最优控制的完整理论框架。
马尔可夫决策过程#
有限马尔可夫决策过程（Markov Decision Process, MDP）可表示为五元组
$$ \mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma), $$其中，$\mathcal{S}$ 和 $\mathcal{A}$ 分别为状态空间和动作空间，$P$ 为状态转移概率，$R$ 为期望即时奖励，$\gamma\in[0,1]$ 为折扣因子；持续任务通常取 $\gamma<1$：
$$ \begin{aligned} P(s'\mid s,a) &=\Pr(S_{t+1}=s'\mid S_t=s,A_t=a),\\ R(s,a) &=\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a]. \end{aligned} $$马尔可夫性意味着：给定当前状态和动作后，下一时刻的分布与更早的交互历史无关，即
$$ \Pr(S_{t+1}\mid S_t,A_t) =\Pr(S_{t+1}\mid S_t,A_t,S_{t-1},A_{t-1},\ldots). $$在有限时域任务中，智能体在状态 $S_k$ 根据策略选择动作 $A_k$，环境随后产生奖励 $R_{k+1}$ 并转移到状态 $S_{k+1}$，直至到达终止状态 $S_T$：
马尔可夫策略仅以当前状态为条件。一个有效的随机策略必须对每个状态给出合法的动作概率分布：
$$ \pi(a\mid s)\ge 0,\qquad \sum_{a\in\mathcal{A}(s)}\pi(a\mid s)=1, \qquad \forall s\in\mathcal{S}. $$确定性策略是其特例，此时每个状态只选择一个动作，可写为 $A_k=\pi(S_k)$。
对于在时刻 $T$ 终止的回合，时刻 $t$ 的折扣回报为
$$ \begin{aligned} G_t &=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-t-1}R_T\\ &=\sum_{k=0}^{T-t-1}\gamma^kR_{t+k+1}. \end{aligned} $$强化学习的目标是选择策略 $\pi(a\mid s)$，使期望累积回报最大。给定策略 $\pi$，状态价值函数定义为
$$ V_\pi(s) =\mathbb{E}_\pi[G_t\mid S_t=s]. $$状态—动作价值函数定义为
$$ Q_\pi(s,a) =\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]. $$贝尔曼方程#
利用回报的递推结构，将状态价值函数逐步展开：
$$ \begin{aligned} V_\pi(s) &=\mathbb{E}_\pi[G_t\mid S_t=s]\\ &=\mathbb{E}_\pi[ R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots \mid S_t=s]\\ &=\mathbb{E}_\pi[ R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\cdots) \mid S_t=s]\\ &=\mathbb{E}_\pi[ R_{t+1}+\gamma G_{t+1} \mid S_t=s]\\ &=\mathbb{E}_\pi[ R_{t+1}+\gamma V_\pi(S_{t+1}) \mid S_t=s]\\ &=\sum_{a\in\mathcal{A}}\pi(a\mid s) \mathbb{E}_\pi[ R_{t+1}+\gamma V_\pi(S_{t+1}) \mid S_t=s,A_t=a]\\ &=\sum_{a\in\mathcal{A}}\pi(a\mid s) \left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V_\pi(s') \right]. \end{aligned} $$因此，最后一行即为状态价值函数的贝尔曼期望方程。同理，状态—动作价值函数可逐步展开为
$$ \begin{aligned} Q_\pi(s,a) &=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]\\ &=\mathbb{E}_\pi[ R_{t+1}+\gamma G_{t+1} \mid S_t=s,A_t=a]\\ &=\mathbb{E}_\pi[ R_{t+1}+\gamma V_\pi(S_{t+1}) \mid S_t=s,A_t=a]\\ &=R(s,a)+\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V_\pi(s')\\ &=R(s,a)+\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,a) \sum_{a'\in\mathcal{A}} \pi(a'\mid s')Q_\pi(s',a'). \end{aligned} $$为了求解最优策略，对动作价值取最大值，得到状态价值函数的贝尔曼最优方程：
$$ \begin{aligned} V_*(s) &=\max_{a\in\mathcal{A}}Q_*(s,a)\\ &=\max_{a\in\mathcal{A}} \left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V_*(s') \right]. \end{aligned} $$同理，最优状态—动作价值函数满足
$$ \begin{aligned} Q_*(s,a) &=R(s,a)+\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V_*(s')\\ &=R(s,a)+\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,a) \max_{a'\in\mathcal{A}}Q_*(s',a'). \end{aligned} $$基于模型的动态规划#
当环境的状态转移概率与奖励函数已知时，可以使用动态规划直接求解贝尔曼方程。策略迭代与价值迭代是两种典型方法。
策略迭代#
在环境模型 $P$ 和 $R$ 已知的情况下，为求解上述贝尔曼最优方程，可以采用动态规划中的策略迭代算法。该算法交替执行策略评估与策略改进：策略评估求解当前策略 $\pi_k$ 的价值函数 $V_{\pi_k}$，策略改进则据此构造贪心策略 $\pi_{k+1}$。当策略不再变化时，算法收敛到最优策略：
策略评估可通过迭代贝尔曼期望备份实现：
$$ V_{j+1}(s) \leftarrow R(s,\pi_k(s)) +\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,\pi_k(s))V_j(s'). $$随后进行策略改进：
$$ \pi_{k+1}(s) \in\arg\max_{a\in\mathcal{A}} \left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V_{\pi_k}(s') \right]. $$完整过程如下。
$$ {\small \begin{array}{rll} \hline & \textbf{Algorithm: Policy Iteration} & \\[2pt] \hline & \textbf{Require:}\ \theta>0 & \text{（策略评估的收敛阈值）}\\ & \textbf{Ensure:}\ \pi\approx\pi_*,\;V\approx V_* & \\[2pt] 1: & \text{任意初始化 }V(s)\in\mathbb{R},\; \pi(s)\in\mathcal{A},\ \forall s\in\mathcal{S} & \\[2pt] 2: & \textbf{repeat} & \\[2pt] 3: & \quad\textbf{repeat} & \triangleright\ \text{Policy Evaluation}\\ 4: & \qquad \Delta\leftarrow 0 & \\ 5: & \qquad \textbf{for each }s\in\mathcal{S}\textbf{ do} & \\ 6: & \qquad\quad v\leftarrow V(s) & \\ 7: & \qquad\quad V(s)\leftarrow R(s,\pi(s)) +\gamma\displaystyle\sum_{s'\in\mathcal{S}} P(s'\mid s,\pi(s))V(s') & \\ 8: & \qquad\quad \Delta\leftarrow\max\!\left(\Delta,\lvert v-V(s)\rvert\right) & \\ 9: & \qquad \textbf{end for} & \\ 10: & \quad\textbf{until }\Delta<\theta & \\[2pt] 11: & \quad \mathrm{stable}\leftarrow\mathrm{true} & \triangleright\ \text{Policy Improvement}\\ 12: & \quad \textbf{for each }s\in\mathcal{S}\textbf{ do} & \\ 13: & \qquad a_{\mathrm{old}}\leftarrow\pi(s) & \\ 14: & \qquad \pi(s)\leftarrow\displaystyle\arg\max_{a\in\mathcal{A}} \left[ R(s,a)+\gamma\displaystyle\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V(s') \right] & \\ 15: & \qquad \textbf{if }a_{\mathrm{old}}\ne\pi(s)\textbf{ then} & \\ 16: & \qquad\quad \mathrm{stable}\leftarrow\mathrm{false} & \\ 17: & \qquad \textbf{end if} & \\ 18: & \quad \textbf{end for} & \\ 19: & \textbf{until }\mathrm{stable} & \\[2pt] 20: & \textbf{return }V,\pi & \\ \hline \end{array} } $$价值迭代#
策略迭代显式地交替执行策略评估与策略改进；价值迭代则将两者合并为一次贝尔曼最优备份，是广义策略迭代的一种特殊形式。由前述贝尔曼最优方程可直接得到价值迭代的自举更新：
$$ V_{k+1}(s)=\max_{a\in\mathcal{A}}\left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}}P(s'\mid s,a)V_k(s') \right]. $$反复应用该更新直至价值函数收敛，即可得到最优价值函数 $V_*$；随后对 $V_*$ 进行贪心策略提取，得到最优策略 $\pi_*$。完整算法如下：
$$ {\small \begin{array}{rll} \hline & \textbf{Algorithm: Value Iteration} & \\[2pt] \hline & \textbf{Require:}\ \theta>0 & \text{（收敛阈值）}\\ & \textbf{Ensure:}\ \pi\approx\pi_*,\;V\approx V_* & \\[2pt] 1: & \text{任意初始化 }V(s)\in\mathbb{R},\ \forall s\in\mathcal{S} & \\[2pt] 2: & \textbf{repeat} & \\ 3: & \quad \Delta\leftarrow 0 & \\ 4: & \quad \textbf{for each }s\in\mathcal{S}\textbf{ do} & \\ 5: & \qquad v\leftarrow V(s) & \\ 6: & \qquad V(s)\leftarrow\displaystyle\max_{a\in\mathcal{A}} \left[ R(s,a)+\gamma\displaystyle\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V(s') \right] & \\ 7: & \qquad \Delta\leftarrow\max\!\left(\Delta,\lvert v-V(s)\rvert\right) & \\ 8: & \quad \textbf{end for} & \\ 9: & \textbf{until }\Delta<\theta & \\[2pt] 10: & \textbf{for each }s\in\mathcal{S}\textbf{ do} & \\ 11: & \quad \pi(s)\leftarrow\displaystyle\arg\max_{a\in\mathcal{A}} \left[ R(s,a)+\gamma\displaystyle\sum_{s'\in\mathcal{S}} P(s'\mid s,a)V(s') \right] & \\ 12: & \textbf{end for} & \\ 13: & \textbf{return }V,\pi & \\ \hline \end{array} } $$无模型预测#
策略迭代和价值迭代均依赖完整的环境模型，包括状态转移概率 $P(s'\mid s,a)$ 与奖励函数 $R(s,a)$，而这些信息在实际问题中通常难以直接获得。无模型预测（model-free prediction）不显式构建环境模型，而是利用交互样本估计给定策略的价值函数。下面介绍蒙特卡洛方法（Monte Carlo, MC）和时序差分学习（Temporal-Difference Learning, TD）。
Monte Carlo Method#
蒙特卡洛预测在策略 $\pi$ 下采样多个完整 episode。每当状态 $s$ 在轨迹中出现时，计算从该时刻开始的回报 $G_t$；Every-visit MC 保留状态的每一次访问，并用这些回报的样本均值估计 $V_\pi(s)$。其算法如下：
$$ {\small \begin{array}{rll} \hline & \textbf{Algorithm: Every-visit Monte Carlo Prediction} & \\[2pt] \hline & \textbf{Require:}\ \pi & \text{（待评估策略）}\\ & \textbf{Ensure:}\ V_\pi & \text{（策略 }\pi\text{ 的价值函数）}\\[2pt] 1: & \mathrm{Returns}(s)\leftarrow 0,\quad \forall s\in\mathcal{S} & \\ 2: & \mathrm{Visits}(s)\leftarrow 0,\quad \forall s\in\mathcal{S} & \\[2pt] 3: & \textbf{for each episode do} & \\ 4: & \quad \text{使用策略 }\pi\text{ 生成一条轨迹：} S_0,A_0,R_1,S_1,A_1,R_2,\ldots,S_{T-1},A_{T-1},R_T & \\ 5: & \quad G\leftarrow 0 & \\ 6: & \quad \textbf{for }t=T-1,T-2,\ldots,0\textbf{ do} & \\ 7: & \qquad G\leftarrow\gamma G+R_{t+1} & \\ 8: & \qquad \mathrm{Returns}(S_t)\leftarrow\mathrm{Returns}(S_t)+G & \\ 9: & \qquad \mathrm{Visits}(S_t)\leftarrow\mathrm{Visits}(S_t)+1 & \\ 10: & \quad \textbf{end for} & \\ 11: & \textbf{end for} & \\[2pt] 12: & V_\pi(s)\leftarrow \displaystyle\frac{\mathrm{Returns}(s)}{\mathrm{Visits}(s)}, \quad \forall s:\mathrm{Visits}(s)>0 & \\ 13: & \textbf{return }V_\pi & \\ \hline \end{array} } $$Temporal-Difference Learning#
蒙特卡洛方法需要等待 episode 结束后才能获得完整回报，通常用于 episodic MDP，且回报估计的方差较高。TD 学习通过自举（bootstrapping）构造单步目标，可以在每次状态转移后立即更新价值函数，也适用于 continuing MDP。最基本的 TD 方法是 TD(0)：
$$ V_{\pi}(s_t) =V_{\pi}(s_t)+\alpha\left( \overbrace{ \underbrace{r_{t+1}+\gamma V_{\pi}(s_{t+1})}_{\text{TD Target}} -V_{\pi}(s_t) }^{\text{TD Error}} \right) $$其中，终止状态的价值按约定取 $0$。完整算法如下：
$$ {\small \begin{array}{rll} \hline & \textbf{Algorithm: Tabular TD(0)} & \\[2pt] \hline & \textbf{Require:}\ \pi & \text{（待评估策略）}\\ & \phantom{\textbf{Require:}}\ \alpha\in(0,1] & \text{（步长）}\\ & \phantom{\textbf{Require:}}\ \gamma\in[0,1] & \text{（折扣因子）}\\ & \textbf{Ensure:}\ V_\pi & \text{（策略 }\pi\text{ 的价值函数）}\\[2pt] 1: & \text{任意初始化 }V_\pi(s)\in\mathbb{R},\quad \forall s\in\mathcal{S} & \\ 2: & \textbf{for each episode do} & \\ 3: & \quad \text{初始化起始状态 }s & \\ 4: & \quad \textbf{while }s\text{ 非终止且未超过最大步数 do} & \\ 5: & \qquad a\sim\pi(\cdot\mid s) & \\ 6: & \qquad \text{执行动作 }a\text{，观测下一状态 }s'\text{ 和奖励 }r & \\ 7: & \qquad \delta\leftarrow r+\gamma V_\pi(s')-V_\pi(s) & \\ 8: & \qquad V_\pi(s)\leftarrow V_\pi(s)+\alpha\delta & \\ 9: & \qquad s\leftarrow s' & \\ 10: & \quad \textbf{end while} & \\ 11: & \textbf{end for} & \\ 12: & \textbf{return }V_\pi & \\ \hline \end{array} } $$无模型控制#
无模型预测只能估计给定策略的价值函数，不能直接改进策略。无模型控制（model-free control）将 TD 价值估计与策略改进结合起来，在未知环境模型的条件下学习动作价值函数，并由此构造近似最优策略。下面介绍 Q-learning 和 Sarsa 两种经典 TD 控制算法。
Q-learning#
Q-learning 的 TD target 使用下一状态上的最大动作价值：
$$ r_{t+1}+\gamma\max_{a'\in\mathcal{A}}Q(s_{t+1},a'). $$因此，TD error 为
$$ \delta_t=r_{t+1}+\gamma\max_{a'\in\mathcal{A}}Q(s_{t+1},a')-Q(s_t,a_t). $$对应的 Q-learning 更新为
$$ Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha\delta_t. $$Q-learning 使用 $\epsilon$-greedy 行为策略与环境交互，但更新目标对应贪心目标策略，因此属于 off-policy 方法。在充分探索并满足适当步长条件时，表格型 Q-learning 可收敛到 $Q_*$。终止状态的后继动作价值按约定取 $0$。完整算法如下：
$$ {\small \begin{array}{rll} \hline & \textbf{Algorithm: Q-learning} & \\[2pt] \hline & \textbf{Require:}\ \alpha\in(0,1] & \text{（步长）}\\ & \phantom{\textbf{Require:}}\ \epsilon\in(0,1) & \text{（随机探索概率）}\\ & \phantom{\textbf{Require:}}\ \gamma\in[0,1] & \text{（折扣因子）}\\ & \textbf{Ensure:}\ Q\approx Q_* & \text{（最优动作价值函数）}\\[2pt] 1: & \text{任意初始化 }Q(s,a),\quad \forall s\in\mathcal{S},\ a\in\mathcal{A} & \\ 2: & \textbf{for each episode do} & \\ 3: & \quad \text{初始化状态 }s & \\ 4: & \quad \textbf{while }s\text{ 非终止且未超过最大步数 do} & \\ 5: & \qquad \text{根据 }Q\text{ 导出的 }\epsilon\text{-greedy策略选择动作 }a & \\ 6: & \qquad \text{执行动作 }a\text{，观测下一状态 }s'\text{ 和奖励 }r & \\ 7: & \qquad \delta\leftarrow r+\gamma\displaystyle\max_{a'\in\mathcal{A}}Q(s',a')-Q(s,a) & \\ 8: & \qquad Q(s,a)\leftarrow Q(s,a)+\alpha\delta & \\ 9: & \qquad s\leftarrow s' & \\ 10: & \quad \textbf{end while} & \\ 11: & \textbf{end for} & \\ 12: & \textbf{return }Q & \\ \hline \end{array} } $$Sarsa#
Sarsa 的 TD target 使用当前策略在下一状态实际选出的动作 $a_{t+1}$：
$$ r_{t+1}+\gamma Q(s_{t+1},a_{t+1}). $$因此，TD error 为
$$ \delta_t=r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t). $$对应的 Sarsa 更新为
$$ Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha\delta_t. $$Sarsa 的行为动作与更新目标均来自当前 $\epsilon$-greedy 策略，因此属于 on-policy 方法。其名称来源于一次更新使用的五元组 $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$。固定 $\epsilon$ 时，Sarsa 评估并改进当前 $\epsilon$-greedy 策略；若探索逐渐衰减且满足 GLIE 条件，则可收敛到最优动作价值函数。终止状态的后继动作价值按约定取 $0$。完整算法如下：
$$ {\small \begin{array}{rll} \hline & \textbf{Algorithm: SARSA} & \\[2pt] \hline & \textbf{Require:}\ \alpha\in(0,1] & \text{（步长）}\\ & \phantom{\textbf{Require:}}\ \epsilon\in(0,1) & \text{（随机探索概率）}\\ & \phantom{\textbf{Require:}}\ \gamma\in[0,1] & \text{（折扣因子）}\\ & \textbf{Ensure:}\ Q\approx Q_\pi & \text{（当前策略的动作价值函数）}\\[2pt] 1: & \text{任意初始化 }Q(s,a),\quad \forall s\in\mathcal{S},\ a\in\mathcal{A} & \\ 2: & \textbf{for each episode do} & \\ 3: & \quad \text{初始化状态 }s & \\ 4: & \quad \text{根据 }Q\text{ 导出的 }\epsilon\text{-greedy策略选择动作 }a & \\ 5: & \quad \textbf{while }s\text{ 非终止且未超过最大步数 do} & \\ 6: & \qquad \text{执行动作 }a\text{，观测下一状态 }s'\text{ 和奖励 }r & \\ 7: & \qquad \text{根据 }Q\text{ 导出的 }\epsilon\text{-greedy策略选择动作 }a' & \\ 8: & \qquad \delta\leftarrow r+\gamma Q(s',a')-Q(s,a) & \\ 9: & \qquad Q(s,a)\leftarrow Q(s,a)+\alpha\delta & \\ 10: & \qquad s\leftarrow s',\quad a\leftarrow a' & \\ 11: & \quad \textbf{end while} & \\ 12: & \textbf{end for} & \\ 13: & \textbf{return }Q & \\ \hline \end{array} } $$Q-learning 与 Sarsa 的核心差别仅在 TD target：前者使用下一状态的最大动作价值，后者使用当前策略实际选择的下一动作价值。因而，Q-learning 学习贪心目标策略，而 Sarsa 会将探索行为的后果纳入价值更新。