REINFORCE 算法 | Codeboy's Blog

形式陈述

先取有限状态、有限动作和有界奖励，固定整数时域 $T\ge1$ 、 $0\le\gamma\le1$ 。初始分布与环境不依赖参数，策略在所考虑邻域连续可微且具有固定支持；一次轨迹或一批轨迹采样期间冻结 $\theta$ ，完成后才更新。设轨迹目标为

J(\theta)=\mathbb E_{\pi_\theta}\left[\sum_{t=0}^{T-1}\gamma^tR_{t+1}\right],

并定义从 $t$ 起重新计时的回报 $G_t=\sum_{k=0}^{T-t-1}\gamma^kR_{t+k+1}$ 。似然比推导结合因果性给

\nabla J(\theta)= \mathbb E\left[ \sum_{t=0}^{T-1}\gamma^t \nabla_\theta\log\pi_\theta(A_t\mid S_t)G_t \right].

REINFORCE 因而在一个或一批完整回合后，以

\widehat g= \sum_{t=0}^{T-1}\gamma^t \nabla_\theta\log\pi_\theta(A_t\mid S_t) [G_t-b_t(S_t)]

更新 $\theta\leftarrow\theta+\alpha\widehat g$ 。外层 $\gamma^t$ 对应从初始状态定义的折扣目标；若采用不同的状态加权目标，公式也会改变，不能一面省略该因子一面仍声称估计上式的梯度。

这是策略梯度恒等式的有限时域蒙特卡洛版本： $G_t$ 在给定 $(S_t,A_t)$ 时，是从时刻 $t$ 继续到 $T$ 的动作值 $q_{\pi,t}^{(T)}(S_t,A_t)$ 的无偏样本。这个值一般依赖剩余时间；把时间并入状态，才能沿用一个状态值符号。基线 $b_t$ 可以依赖状态、时间和动作抽样前的历史，甚至由另一个参数化模型估计；只要条件于这些信息时不依赖本次 $A_t$ ，且更新中不把基线自身的导数混入 policy loss，score 的条件均值为零，梯度估计便不引入偏差。

推导从轨迹密度开始。环境动力学不含 $\theta$ 时，

\nabla_\theta\log p_\theta(\tau) =\sum_t\nabla_\theta\log\pi_\theta(A_t\mid S_t).

把它乘上总折扣回报并取期望得到似然比梯度。对时刻 $t$ 的 score，动作发生前的奖励在条件期望中与该动作无关，其贡献为零；只留下从 $t$ 开始的 reward-to-go，并把原始时间折扣拆成 $\gamma^tG_t$ 。这一步因果消项说明了为何公式不应让后期动作为早期奖励负责。

实现时从 $G_T=0$ 反向递推 $G_t=R_{t+1}+\gamma G_{t+1}$ ，全部 reward-to-go 只需 $O(T)$ 算术操作。若参数维数为 $d$ ，每步 score 梯度与基线求值代价分别为 $C_{\mathrm{grad}}$ 、 $C_b$ ，整回合汇总耗时 $O(T(1+C_{\mathrm{grad}}+C_b+d))$ ，另计轨迹采样；保存轨迹并在冻结的 $\theta$ 处重算梯度，可用 $O(T+d)$ 存储外加模型求值工作空间，若缓存所有 $d$ 维 score 则需 $O(Td)$ 。

直觉

算法把一次随机行动的“责任”写成它的 log-probability 梯度，再用后来实际得到的回报决定奖励还是惩罚。回报高的轨迹会提高其中动作的概率，回报低的轨迹会压低它们。因为等到结局才结账，信号无须自举模型，却可能非常嘈杂。

基线像按状态设定的及格线：只奖励高于该状态通常水平的动作。所有动作都减去同一个数不会改变平均梯度方向，因为动作概率总和恒为一；但它能去掉与动作选择无关的共同回报波动。

REINFORCE：完整轨迹上各动作的对数概率梯度按后续回报加权后汇总 — 整回合的蒙特卡洛策略梯度

图中蓝框展示 $G_t\nabla\log\pi_t$ 这个因子；汇总时还要按底部公式乘以原始时刻的 $\gamma^t$ ，例如第二个蓝框对总梯度的贡献带一个 $\gamma$ 。

例子与边界

一回合只有一个状态和一次动作。动作 1 奖励 $3$ ，动作 0 奖励 $1$ ； $p=\pi_\theta(1)=\sigma(\theta)$ ，score 分别为 $1-p$ 和 $-p$ 。取基线 $b=1$ ，单样本梯度为：抽到动作 1 时 $2(1-p)$ ，抽到动作 0 时为零。其期望是

p\,2(1-p)=2p(1-p).

直接计算 $J=3p+1(1-p)=1+2p$ ，也有 $\mathrm dJ/\mathrm d\theta=2p(1-p)$ 。基线改变了两类样本各自贡献，却没有改变均值；若用本次观测到的奖励拟合这个唯一状态的常数基线，取 $b=R_1$ ，每次 $G_0-b$ 都变成零，估计梯度恒为零，却与上述非零真梯度矛盾。虽然拟合后的模型输入只含状态，它的训练数据已经包含本次动作的后果；动作无关性必须针对采样前的信息检验。

若把固定 $T$ 换成随机终止时刻，需固定不直接依赖参数的终止机制，并另外验证轨迹密度求导的可积支配与回报矩条件；仅有几乎必然终止还不足以保证上述无偏恒等式。

REINFORCE 的主要边界是方差和样本效率。长回合中，早期动作乘上许多与它无关的随机奖励；稀有高回报事件会制造重尾估计。截断未结束回合会产生偏差，除非加入正确续值或随机截断校正。离策略轨迹还需重要性权重，乘积权重可能进一步放大方差。

推论与应用

reward-to-go 利用因果性去掉期望贡献为零的早期奖励项，保持梯度期望不变；整个梯度和的方差还取决于各项协方差，需要结合环境与策略计算。把基线训练成 $v_\pi(S_t)$ ，括号成为优势的蒙特卡洛估计；若进一步用一步 TD 误差代替完整 $G_t-v_\pi(S_t)$ ，便进入actor–critic，以自举目标实现在线更新。

当轨迹由另一行为策略生成时，先要解决离策略评价的前缀换测度问题。价值评价与策略梯度是不同目标，不能只给梯度式乘上一个未经推导的单步权重；同样，删去零均值项也不自动证明整个和的普遍方差排序。

实践中通常对多条轨迹求平均、标准化优势并加入熵奖励。轨迹平均保持目标不变；批内标准化和熵项会改变有限样本估计或优化目标，应在理论陈述中单独标明，而不是统称为“方差降低且无偏”。

参考资料

Ronald J. Williams, “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning,” Machine Learning 8, 1992, pp. 229–256.
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Sec. 13.3.
Peter W. Glynn, “Likelihood Ratio Gradient Estimation for Stochastic Systems,” Communications of the ACM 33(10), 1990, pp. 75–84.

形式陈述 ​

反向链接

形式陈述