值迭代和策略迭代

值迭代 (Value Iteration) 和策略迭代 (Policy Iteration) 强化学习算法的两个经典类别。

值迭代

值迭代通常包括求最优价值函数和策略提取两部分。在每次迭代中，值迭代算法会通过某种方式更新状态价值函数 $V(s)$ 或状态动作价值函数 $Q(s,a)$，该价值函数可能是表格，也可能是函数近似器 (如神经网络) 。值迭代最终提取出的目标策略是基于最优价值函数的贪心策略，显然，一旦价值函数是最优的，那么贪心策略也是最优的。这里包含更多关于值迭代的内容。

值迭代所使用的行为策略和提取出来的目标策略可能不同，例如探索策略可能是 $ϵ$-贪心策略。详见行为策略与目标策略。

策略迭代

策略网络 $\pi (a|s;\theta )$ 由 $\theta$ 参数化，给出状态 $s$ 下采取动作 $a$ 的概率。如果动作空间是离散的，通常网络会将状态 $s$ 映射到一个向量，向量的每个元素对应一个动作的概率。

策略迭代 (策略梯度方法) 希望最大化以下目标:

$$J(\theta )={\mathbb{E}}_s[V_{\pi }(s)]$$

我们可以用梯度上升来更新策略参数 $\theta$:

$${\theta }_{\text{new}}\leftarrow {\theta }_{\text{now}}+\alpha {\nabla }_{\theta }J({\theta }_{\text{now}})$$

其中策略梯度 ${\nabla }_{\theta }J({\theta }_{\text{now}})\triangleq {\frac{\partial J(\theta )}{\partial \theta }|}_{\theta ={\theta }_{\text{now}}}$

这里包含更多关于策略迭代的内容。

策略梯度定理

策略梯度定理将策略梯度 ${\nabla }_{\theta }J(\theta )$ 表示为期望的形式:

$${\nabla }_{\theta }J(\theta )=\frac{1-{\gamma }^n}{1-\gamma }{\mathbb{E}}_{S\sim d(\cdot )}\left[{\mathbb{E}}_{A\sim {\pi }_{\theta }(\cdot |S;\theta )}\left[\frac{\partial \ln {\pi }_{\theta }(A|S;\theta )}{\partial \theta }\cdot Q_{{\pi }_{\theta }}(S,A)\right]\right]$$

其中

• $d(\cdot )$ 是马尔科夫链的稳态分布
• $\theta$ 是策略网络的参数
• $Q^{{\pi }_{\theta }}(s,A)$ 是状态动作价值函数

在实际使用中，系数 $\frac{1-{\gamma }^n}{1-\gamma }$ 无关紧要（被学习率吸收），而且我们通常省略 $d(\cdot )$，所以通常将策略梯度定理简写为:

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_S\left[{\mathbb{E}}_{A\sim {\pi }_{\theta }(\cdot |S;\theta )}\left[Q_{{\pi }_{\theta }}(S,A)\cdot {\nabla }_{\theta }\ln {\pi }_{\theta }(A|S;\theta )\right]\right]$$

近似策略梯度

尽管策略梯度定理给出了一个计算策略梯度的式子，但是解析求解该期望是不可能的，因为我们不知道 $d(\cdot )$ ，即使知道，使用求和或积分求期望也是不现实的。因此，我们通常使用采样的方法来估计策略梯度。

我们每次从环境中观察到一个状态 $s$，然后根据策略网络 ${\pi }_{\theta }$ 采样一个动作 $a\sim \pi (\cdot |s;\theta )$，然后计算随机梯度:

$$g(s,a;\theta )=Q_{{\pi }_{\theta }}(s,a)\cdot \frac{\partial \ln {\pi }_{\theta }(a|s;\theta )}{\partial \theta }$$

它是策略梯度 ${\nabla }_{\theta }J(\theta )$ 的一个无偏估计。我们可以使用这个梯度来更新策略参数 $\theta$:

$$\theta \leftarrow \theta +\beta \cdot g(s,a;\theta )$$

其中 $\beta$ 是学习率。

为了计算 $Q_{{\pi }_{\theta }}(s,a)$，我们通常有两类方法，其代表分别为 REINFORCE (用观测到的回报近似) 和 actor-critic (用神经网络近似)。

这两种方法都是其类型中的最简单算法，实践中往往效果不佳。它们需要配合 基线使用，或者你可以寻找更加先进的改进型。