强化学习：1. 策略梯度算法
用“起源”似乎有点不恰当，但是笔者希望在该系列文章中较为系统地学习“基于策略”的强化学习算法，不考虑“基于值”的强化学习算法。
问题陈述和符号定义
在马尔可夫决策过程中，有关键的五个要素是：状态空间、动作空间、奖励函数、转移函数和折扣因子。
- 状态空间：$\mathcal{S}$
- 动作空间：$\mathcal{A}$
- 奖励函数：$r(s_t, a_t)$
- 转移函数：$p(s_{t+1}, r_{t+1} | s_t, a_t)$
- 折扣因子：$\gamma$
在这个问题中，我们的目标是希望能够找到一个策略$\pi_\theta$，基于这个策略和初始状态分布，能够采样出奖励最大化的轨迹。我们记轨迹为$\tau = \{(s_t, a_t, r_t)\}^T_{t=0}$，其中$T$为轨迹的长度。
问题建模
策略梯度算法的建模目标非常直观，就是最大化策略$\pi_\theta$的期望奖励：
$$
max\ J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} [R(\tau)]
$$
策略梯度方法
这个最“直观”的优化目标显然对于梯度上升法来说是不可行的，因为这里面不存在关于$\theta$的表达式。我们进行改写：
$$
J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} [R(\tau)] \\ =
\sum_{\tau \sim \pi_\theta} P(\tau | \theta) \cdot R(\tau) \\
$$
此时对$\theta$求导，得到：
$$
\nabla J(\theta) = \sum_{\tau \sim \pi_\theta} P(\tau | \theta) \cdot \nabla \log P(\tau | \theta) \cdot R(\tau) \\ = \mathbb{E}_{\tau \sim \pi_\theta} [\nabla \log P(\tau | \theta) \cdot R(\tau)]
$$
根据MDP的性质，我们知道：
$$
P(\tau | \theta) = P(s_0) \prod_{t=0}^{T} P(s_{t+1} | s_t, a_t) \cdot \pi_\theta(a_t | s_t)
$$
所以：
$$
\nabla log P(\tau | \theta) = \nabla[ P(s_0) + \sum_{t=0}^{T} P(s_{t+1} | s_t, a_t) + \sum_{t=0}^{T} \log \pi_\theta(a_t | s_t) ] \\ = \nabla \sum_{t=0}^{T} \log \pi_\theta(a_t | s_t)
$$
所以$\nabla J(\theta)$可以改写为：
$$
\nabla J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} [\sum_{t=0}^{T} \nabla \log \pi_\theta(a_t | s_t) \underbrace{\sum_{k=t}^{T} \gamma^{k-t} r_k}_{G_t}]
$$
至此，可以使用蒙托卡洛方法来估计$\nabla J(\theta)$，实现梯度上升。
$$
\nabla J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=0}^{T} \nabla \log \pi_\theta(a_t | s_t) G_t
$$
问题
Q：为什么需要折扣因子？
如果$R(\tau)= \sum^{T}_{t=0} r_t$，那么当$T \rightarrow \infty$时，$R(\tau)$会无限大，这是发散的，会导致没有收敛的策略。因此，我们需要引入折扣因子$\gamma \in (0, 1)$，将奖励函数改写为：
$$
R(\tau) = \sum^{T}_{t=0} \gamma^t \cdot r_t \lt R_{max} \underbrace{\sum^{T}_{t=0} \gamma^t}_{几何级数} = R_{max} \frac{1}{1-\gamma}
$$
