这篇文章主要是Book-Mathematical-Foundation-of-Reinforcement-Learning这本书的阅读笔记，简单总结一下重点和学到的东西。

配套课程在这里：【强化学习的数学原理】课程：从零开始到透彻理解（完结）_哔哩哔哩_bilibili

基础概念

Agent：受控的对象。

State：描述Agent的状态集合，比如位置、速度、方向等信息，使用$ \mathcal{S}=\left{s_1, \ldots, s_n\right} $表示。

Action：描述Agent拥有的动作集合，比如前进、后退、攻击等动作，使用$ \mathcal{A}=\left{a1, \ldots, a_n\right} $表示。不同的状态可以有不同的Action，比如$ \mathcal{A}\left(s_1\right)=\left{a_2, a_3, a_5\right} $表示在$ s{1} $状态下可以执行动作$ a{2},a{3},a_{5} $。

State Transition：在某个状态执行某个Action后，Agent的状态会发生转移。比如$ s1 \xrightarrow{a_2} s_2 $表示在状态$ s_1 $执行$ a{2} $后，状态转移到了$ s_{2} $。通常在数学上State Transition被描述为条件概率分布，比如上面的例子可以表示为$ p\left(s_1 \mid s_1, a_2\right) $。

Policy：定义为Agent在给定任意状态$ s $时可以执行$ a $的条件概率，使用数学语言描述为$ \pi(a|s) $。

Behavior Policy：产生数据（experience）用的Policy。

Target Policy：需要求取的最优Policy。

Off-Policy：指的是behavior Policy和target Policy不同的算法。

On-Policy：指的是behavior Policy和target Policy相同的算法。

Reward：在某个状态$ s $执行一个Action后，Agent需要获取一个反馈，这个反馈就是reward。reward定义为状态$ s $和动作$ a $的函数$ r(s,a) $。通常$ r(s,a) $也是一个条件概率分布。

Trajectory：一个Trajectory定义为给定Policy时的一个State-Action-Reward链。比如

$ s_1 \underset{r=0}{\stackrel{a_2} {\longrightarrow}}s_2 \underset{r=0}{\stackrel{a_3} {\longrightarrow}}s_5 \underset{r=0}{\stackrel{a_3} {\longrightarrow}}s_8 \underset{r=1}{\stackrel{a_2} {\longrightarrow}}s_9 $

表示一条Trajectory，Agent开始在$ s_1 $状态，采取$ a_2 $后进入状态$ s_2 $，获取的reward为$ 0 $，其他依次类推。

Experience ：经验，也就是监督学习里面的数据，在强化学习里面由一个或多个State-Action-Reward组成。

Return：表示一条Trajectory上所有reward的和。比如上面的轨迹的Return是$ 0 + 0 + 0 + 1 = 1 $，所以Return也被称为total rewards或者cumulative rewards。Return计算了一条Trajectory上所有reward的和，而Trajectory被Policy确定，因此Return可以用来衡量不同Policy间的好坏。

Return分为immediate reward 和future rewards。immediate reward是指采取Action后获取的第一个reward。比如上面Trajectory中$ s_1 \underset{r=0}{\stackrel{a_2} {\longrightarrow}}s_2 $ 获取的reward就是immediate reward。future rewards则是指离开初始状态获取的reward，比如上面Trajectory中的剩余部分。

Discounted Return：有时候Trajectory可能是无限长度，比如寻路任务中到达终点后如果继续留在重点一直给正的reward，那么这样计算的Return会得到$ \infin $。Discounted Return通过引入Discount rate$ \gamma \in(0,1) $来解决这个问题，Discounted Return定义如下：

$ \begin{aligned}\text { discounted return }&= r{0}+\gamma r{1}+\gamma^2 r{2}+\gamma^3 r{3}+\gamma^4 r{4}+\gamma^5 r{5}+\ldots \ &= \sum{n=0} \gamma^{n}r{n} = \gamma^3 \frac{1}{1-\gamma}\end{aligned} $

Episode：当Agent与环境交互训练时，从一个初始状态开始一直到终止状态的一系列状态、动作、和奖励的序列（Trajectory）。

Markov Decision Processes（MDPs）：MDP是在状态空间$ \mathcal{S} $、动作空间$ \mathcal{A}(s) $、和Reward空间$ \mathcal{R}(s,a) $上定义有状态转移$ p\left(s^{\prime} \mid s, a\right) $、Reward $ p(r \mid s, a) $、Policy $ \pi(a \mid s) $以及满足马尔科夫性质（下一状态只与当前状态有关）的决策过程。

State Values

考虑一个时间序列$ t=0,1,2, \ldots $，在时间$ t $时，Agent处于状态$ S{t} $，如果Agent遵从Policy $ \pi $采取Action为$ A{t} $时的下一个状态为$ S{t+1} $时获取的immediate reward为$ R{t+1} $，这个过程可以被表达为：

$ St \xrightarrow{A_t} S{t+1}, R_{t+1} $

其中$ St, S{t+1}, At, R{t+1} $均为随机变量。考虑一条State-Action-Reward Trajectory：

$ St \xrightarrow{A_t} S{t+1}, R{t+1} \xrightarrow{A{t+1}} S{t+2}, R{t+2} \xrightarrow{A{t+2}} S{t+3}, R_{t+3} \ldots $

这条Trajectory的Discounted return为：

$ Gt \doteq R{t+1}+\gamma R{t+2}+\gamma^2 R{t+3}+\ldots $

由于$ St, S{t+1}, At, R{t+1} $均为随机变量，则$ G_{t} $也是随机变量，所以为了获取它的值，我们需要对它求期望：

$ v_\pi(s) \doteq \mathbb{E}\left[G_t \mid S_t=s\right] $

这个值就被称为State Values。可以看到当轨迹确定时（Policy、State Transition、Reward都确定时），State Values等于Discounted Return；当轨迹不确定时，实际上State Values就是在在相同状态$ s $时对不同Trajectory的Discounted Return的期望。

贝尔曼方程

注意到：

$ \begin{equation} \begin{aligned} Gt & =R{t+1}+\gamma R{t+2}+\gamma^2 R{t+3}+\ldots \ & =R{t+1}+\gamma\left(R{t+2}+\gamma R{t+3}+\ldots\right) \ & =R{t+1}+\gamma G_{t+1} \end{aligned} \end{equation} $

则有：

$ \begin{equation} \begin{aligned} v\pi(s) & =\mathbb{E}\left[G_t \mid S_t=s\right] \ & =\mathbb{E}\left[R{t+1}+\gamma G{t+1} \mid S_t=s\right] \ & =\mathbb{E}\left[R{t+1} \mid St=s\right]+\gamma \mathbb{E}\left[G{t+1} \mid S_t=s\right] \end{aligned} \end{equation} $

上面式子中的第一项表示immediate rewards 的期望，展开有：

$ \begin{equation}\begin{aligned}\mathbb{E}\left[R{t+1} \mid S_t=s\right] & =\sum{a \in \mathcal{A}} \pi(a \mid s) \mathbb{E}\left[R{t+1} \mid S_t=s, A_t=a\right] \& =\sum{a \in \mathcal{A}} \pi(a \mid s) \sum_{r \in \mathcal{R}} p(r \mid s, a) r .\end{aligned}\end{equation} $

上面式子中的第二项表示的是Future Reward的期望，同样展开有：

$ \begin{equation}\begin{aligned}\mathbb{E}\left[G{t+1} \mid S_t=s\right] & =\sum{s^{\prime} \in \mathcal{S}} \mathbb{E}\left[G{t+1} \mid S_t=s, S{t+1}=s^{\prime}\right] p\left(s^{\prime} \mid s\right) \& =\sum{s^{\prime} \in \mathcal{S}} \mathbb{E}\left[G{t+1} \mid S{t+1}=s^{\prime}\right] p\left(s^{\prime} \mid s\right) \;\;\text{(马尔科夫决策过程，只有当前状态相关)} \& =\sum{s^{\prime} \in \mathcal{S}} v\pi\left(s^{\prime}\right) p\left(s^{\prime} \mid s\right) \& =\sum{s^{\prime} \in \mathcal{S}} v\pi\left(s^{\prime}\right) \sum{a \in \mathcal{A}} p\left(s^{\prime} \mid s, a\right) \pi(a \mid s)\end{aligned}\end{equation} $

将上面两项带入到原方程可以得到：

$ \begin{equation}\begin{aligned}v\pi(s) & =\mathbb{E}\left[R{t+1} \mid St=s\right]+\gamma \mathbb{E}\left[G{t+1} \mid St=s\right], \& =\underbrace{\sum{a \in \mathcal{A}} \pi(a \mid s) \sum{r \in \mathcal{R}} p(r \mid s, a) r}{\text {mean of immediate rewards }}+\underbrace{\gamma \sum{a \in \mathcal{A}} \pi(a \mid s) \sum{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\pi\left(s^{\prime}\right)}{\text {mean of future rewards }}, \& =\sum{a \in \mathcal{A}} \pi(a \mid s)\left[\sum{r \in \mathcal{R}} p(r \mid s, a) r+\gamma \sum{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\pi\left(s^{\prime}\right)\right], \quad \text { for all } s \in \mathcal{S} .\end{aligned}\end{equation} $

这个方程就被称为贝尔曼方程。表述了所有State Values之间的关系。其中$ v\pi(s) $和$ v\pi\left(s^{\prime}\right) $均未知，是需要计算的state values值。$ \pi(a \mid s) $是给定的Policy；$ p(r \mid s, a) $和$ p\left(s^{\prime} \mid s, a\right) $分别是Reward和State Transition，对应MDPs中的Model。

贝尔曼方程也可以写成矩阵向量形式：

$ \begin{equation}\begin{aligned} v\pi&=r\pi+\gamma P\pi v\pi \ r\pi(s) &\doteq \sum{a \in \mathcal{A}} \pi(a \mid s) \sum{r \in \mathcal{R}} p(r \mid s, a) r \ P{\pi} &= \left[P\pi\right]{i j}=p\pi\left(s_j \mid s_i\right) \in \mathbb{R}^{n \times n} \ v\pi&=\left[v\pi\left(s_1\right), \ldots, v\pi\left(sn\right)\right]^T \in \mathbb{R}^n \ r\pi&=\left[r\pi\left(s_1\right), \ldots, r\pi\left(s_n\right)\right]^T \in \mathbb{R}^n \end{aligned}\end{equation} $

下面是一个例子，放这里方便理解：

$ \begin{equation}\underbrace{\left[\begin{array}{l}v\pi\left(s_1\right) \v\pi\left(s2\right) \v\pi\left(s3\right) \v\pi\left(s4\right)\end{array}\right]}{v\pi}=\underbrace{\left[\begin{array}{l}r\pi\left(s1\right) \r\pi\left(s2\right) \r\pi\left(s3\right) \r\pi\left(s4\right)\end{array}\right]}{r\pi}+\gamma \underbrace{\left[\begin{array}{llll}p\pi\left(s1 \mid s_1\right) & p\pi\left(s2 \mid s_1\right) & p\pi\left(s3 \mid s_1\right) & p\pi\left(s4 \mid s_1\right) \p\pi\left(s1 \mid s_2\right) & p\pi\left(s2 \mid s_2\right) & p\pi\left(s3 \mid s_2\right) & p\pi\left(s4 \mid s_2\right) \p\pi\left(s1 \mid s_3\right) & p\pi\left(s2 \mid s_3\right) & p\pi\left(s3 \mid s_3\right) & p\pi\left(s4 \mid s_3\right) \p\pi\left(s1 \mid s_4\right) & p\pi\left(s2 \mid s_4\right) & p\pi\left(s3 \mid s_4\right) & p\pi\left(s4 \mid s_4\right)\end{array}\right]}{P\pi} \underbrace{\left[\begin{array}{l}v\pi\left(s1\right) \v\pi\left(s2\right) \v\pi\left(s3\right) \v\pi\left(s4\right)\end{array}\right]}{v_\pi} .\end{equation} $

贝尔曼方程可以通过$ v\pi=\left(I-\gamma P\pi\right)^{-1} r\pi $来得到闭式解，虽然$ \left(I-\gamma P\pi\right)^{-1} $一定可逆，但求逆的计算量在矩阵比较大时会非常大，所以经常使用迭代方式$ vk \rightarrow v\pi=\left(I-\gamma P\pi\right)^{-1} r\pi, \quad \text { as } k \rightarrow \infty $，来求贝尔曼方程的解。

通过解贝尔曼方程，我们可以得到给定Policy下的State Values，因此对于不同的Policy，可以计算不同Policy对应的State Values，这样不同的Policy就可以进行比较了。

Action Values

Action Values用于度量在某种State执行某种Action的Discounted Return的期望，使用数学语言描述如下：

$ \begin{equation}q_\pi(s, a) \doteq \mathbb{E}\left[G_t \mid S_t=s, A_t=a\right]\end{equation} $

需要注意的是Action Values依赖于State-Action对 $ (s,a) $而不单单是Action。Action Values和State Values的联系如下：

$ \begin{equation}\begin{aligned}\underbrace{\mathbb{E}\left[Gt \mid S_t=s\right]}{v\pi(s)}&=\sum{a \in \mathcal{A}} \underbrace{\mathbb{E}\left[Gt \mid S_t=s, A_t=a\right]}{q\pi(s, a)} \pi(a \mid s) \ v\pi(s)&=\sum{a \in \mathcal{A}} \pi(a \mid s) q\pi(s, a) \end{aligned}\end{equation} $

所以可以使用State Values来推导出Action Values的表达式：

$ \begin{equation}\begin{aligned}v\pi(s)&=\sum{a \in \mathcal{A}} \pi(a \mid s)\underbrace{\left[\sum{r \in \mathcal{R}} p(r \mid s, a) r+\gamma \sum{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\pi\left(s^{\prime}\right)\right]}{q{\pi(s,a)}} \ q\pi(s, a)&=\sum{r \in \mathcal{R}} p(r \mid s, a) r+\gamma \sum{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v_\pi\left(s^{\prime}\right) \end{aligned}\end{equation} $

根据上面的公式，贝尔曼方程也可以通过Action Values来表示：

$ \begin{equation}q\pi(s, a)=\sum{r \in \mathcal{R}} p(r \mid s, a) r+\gamma \sum{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) \sum{a^{\prime} \in \mathcal{A}\left(s^{\prime}\right)} \pi\left(a^{\prime} \mid s^{\prime}\right) q_\pi\left(s^{\prime}, a^{\prime}\right)\end{equation} $

它的矩阵向量形式如下：

$ \begin{equation}q\pi=\tilde{r}+\gamma P \Pi q\pi\end{equation} $

其中$ [\tilde{r}]{(s, a)}=\sum{r \in \mathcal{R}} p(r \mid s, a) r $，$ [P]{(s, a), s^{\prime}}=p\left(s^{\prime} \mid s, a\right) $，$ \Pi $是一个分块对角矩阵，每块是一个$ 1 \times|\mathcal{A}| $的向量：$ \Pi{s^{\prime},\left(s^{\prime}, a^{\prime}\right)}=\pi\left(a^{\prime} \mid s^{\prime}\right) $。

贝尔曼最优方程（BOE）

对于两个不同的Policy $ \pi{1} $和$ \pi{2} $，如果对所有的 $ s \in \mathcal{S} $，有$ v{\pi_1}(s) \geq v{\pi2}(s) $，那么就说$ \pi{1} $比$ \pi_{2} $好。如果一个Policy $ \pi^{\star} $比其他所有的Policy都好，那这个Policy $ \pi^{\star} $被称为最优Policy。

这个Policy可以用过解贝尔曼最优方程（Bellman optimality equation，BOE）来得到，贝尔曼最优方程如下：

$ \begin{equation}\begin{aligned}v(s) & =\max {\pi(s) \in \Pi(s)} \sum{a \in \mathcal{A}} \pi(a \mid s)\left(\sum{r \in \mathcal{R}} p(r \mid s, a) r+\gamma \sum{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right)\right) \& =\max {\pi(s) \in \Pi(s)} \sum{a \in \mathcal{A}} \pi(a \mid s) q(s, a),\end{aligned}\end{equation} $

其中$ \pi(s) $是在$ s $的Policy，$ \Pi(s) $是在$ s $所有可能得Policy。使用矩阵-向量表示有：

$ \begin{equation} \begin{aligned} v&=\max {\pi \in \Pi}\left(r\pi+\gamma P\pi v\right) \ \left[r\pi\right]s &\doteq \sum{a \in \mathcal{A}} \pi(a \mid s) \sum{r \in \mathcal{R}} p(r \mid s, a) r \ \left[P\pi\right]{s, s^{\prime}}&=p\left(s^{\prime} \mid s\right) \doteq \sum{a \in \mathcal{A}} \pi(a \mid s) p\left(s^{\prime} \mid s, a\right) \end{aligned} \end{equation} $

可以证明BOE一定有唯一解，且可以使用不动点迭代来求得解。这里略过证明方法，具体看书或者视频。

值迭代和策略迭代

值迭代

Policy Update

$ \begin{equation} \pi{k+1}=\arg \max \pi\left(r\pi+\gamma P\pi v_k\right) \end{equation} $

State Values $ v{k} $是固定的，通过解BOE得到一个新的策略$ \pi{k+1} $。

Values Update

$ \begin{equation}v{k+1}=r{\pi{k+1}}+\gamma P{\pi_{k+1}} v_k\end{equation} $

使用Policy Update得到的新策略，更新State Values。

策略迭代

Policy Evaluation

$ \begin{equation} \begin{aligned} v{\pi_k}&=r{\pik}+\gamma P{\pik} v{\pik} \ v{\pik}^{(j+1)}(s)&=\sum_a \pi_k(a \mid s)\left(\sum_r p(r \mid s, a) r+\gamma \sum{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v{\pi_k}^{(j)}\left(s^{\prime}\right)\right), \ &=\sum \pi(a \mid s) q{\pi_k}(s, a), \quad s \in \mathcal{S} \end{aligned} \end{equation} $

使用贝尔曼方程计算State Values，按照贝尔曼最优方程这节提到的方法迭代解算就可以了。

Policy Improvement

$ \begin{equation} \begin{aligned} \pi{k+1}&=\arg \max \pi\left(r\pi+\gamma P\pi v{\pi_k}\right) \pi{k+1}(s) \ &=\arg \max \pi \sum_a \pi(a \mid s)\left[\sum_r p(r \mid s, a) r+\gamma \sum{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v{\pi_k}\left(s^{\prime}\right)\right] \ & =\arg \max \pi \sum \pi(a \mid s) q_{\pi_k}(s, a), \quad s \in \mathcal{S} . \end{aligned} \end{equation} $

通过解BOE来计算提升后的Policy。

Truncated Policy Iteration

这种方法是值迭代和策略迭代的泛化方法，当该方法的Policy Evaluation中的迭代次数等于无穷大时，该方法变成Policy Iteration。当迭代次数等于1时，该方法退化为值迭代。

可以从图中看出，策略迭代的收敛速度更快一些，但是由于策略迭代的Policy Evaluation步骤需要无穷大次，所以实际上使用的是Truncated Policy Iteration，它的收敛速度仍然大于值迭代。

Monte Carlo Methods （MC Methods）

MC Base（最简单的蒙特卡洛方法）

值迭代和策略迭代都是已知模型（状态转移&Reward）推导出来的，蒙特卡洛方法则是未知模型（model-free）推导出来的。

为了求出最优的策略，要么需要知道模型，要么需要数据来估计，数据在强化学习里也被叫做经验（Experiences）:

$ \begin{equation} \mathbb{E}[X] \approx \bar{x}=\frac{1}{n} \sum{j=1}^n x_j \qquad x{j} \in X, \qquad \text{X 是未知的分布} \end{equation} $

回忆策略迭代分为Policy Evaluation和Policy Improvement两步，这两步实际都是通过计算Action Values来进一步计算得到的（参考公式17、公式18），Action Values计算的是在state $ s $时执行action $ a $时的discounted reward的期望，那么自然可以想到是否可以通过数据来估计Action Values来实现Model-Free，这就是蒙特卡洛方法的核心思想：

$ \begin{equation} \begin{aligned} q{\pi_k}(s, a) &=\mathbb{E}\left[G_t \mid S_t=s, A_t=a\right] \qquad \text{Action Value的原始定义} \ &\approx \frac{1}{n} \sum{i=1}^n g{\pi_k}^{(i)}(s, a) \qquad \qquad g{\pi_k}^{(i)}(s, a)\text{是每个episodes对discounted return的估计} \end{aligned} \end{equation} $

所以最简单的蒙特卡洛方法也分为两步：

1. 对每一个$ (s,a) $收集充分数量的Episode用于估计Action Values $ q_{\pi_k}(s,a) $。
2. 使用计算好的$ q_{\pi_k}(s,a) $和策略迭代一样进行Policy Improvement。

这个算法比较简单，但是样本利用效率太低，只用于抓核心思想。

MC Exploring Start

考虑由一个Policy生成的Trajectory：

$ \begin{equation}s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_4} s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \ldots\end{equation} $

对于其中出现的每一个state-action对$ (s,a) $称为一次visit。注意到最简单的蒙特卡洛方法只计算上面序列中$ (s_1,a_2) $的Action Value，在这个序列中诸如$ (s_2,a_4),(s_1,a_2) $的Action Value并没有被充分利用。MC Exploring Start的核心思想就是利用这些Action Values。

如果将这些state-action的Action Values值充分利用，这被称为every-visit strategy，而像最简单的蒙特卡洛方法中只计算$ (s_1,a_2) $的Action Value被称为first-visit strategy。

MC Exploring Start需要遵循exploring-starts condition：

从选取的State-Action对$ (s_0,a_0) $出发需要确保其他State-Action对$ (s_i,a_j) $都可达（一个Episode中的Trajectory足够长且能覆盖到所有的State-Action对）。这样我们就不需要从所有的state-action对出发一遍产生数据，而是充分利用一条Trajectory上的所有数据来计算了。

最终算法如下：

MC $ \epsilon $-Greedy

MC Exploring Start需要满足exploring-starts条件，注意到到现在为止我们使用的Policy都是确定性的（greedy策略），我们可以通过使用随机性的Policy实现exploring-starts条件，再次之前需要引入$ \epsilon $-greedy policies。

• $ \epsilon $-greedy policies

$ \epsilon $-greedy是指有更高的概率选择贪心Action，有同样的非零概率选择其他Action的策略，使用数学描述如下：

$ \begin{equation}\pi(a \mid s)= \begin{cases}1-\frac{\epsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1), & \text { for the greedy action, } \ \frac{\epsilon}{|\mathcal{A}(s)|}, & \text { for the other }|\mathcal{A}(s)|-1 \text { actions, }\end{cases} \qquad \epsilon \in [0,1]\end{equation} $

注意到当$ \epsilon = 0 $时，这个策略就变成了Greedy策略（取这个状态下action value最大的Action），当$ \epsilon = 1 $时，所有Action有同样的概率$ \frac{1}{|\mathcal{A}(s)|} $，且在$ \epsilon\in[0,1] $范围内，Greedy Action的概率一定大于其他Action的概率。

• 算法

为了实现MC $ \epsilon $-Greedy，只需要将Greedy Policy变为$ \epsilon $-greedy policies即可。

需要注意的是虽然没有了Exploring Start条件，但是还是需要运行多个Episode尽量让每个Action-Value都被visit比较好，否则算法可能没有收敛到最优解。

MC $ \epsilon $-Greedy利用$ \epsilon $来控制Exploration（探索）和exploitation（充分利用）。如果$ \epsilon $太大，则算法可能不能收敛到最优解，所以建议使用这个算法时，一开始设置的$ \epsilon $应该比较小，让算法可以充分探索尽量覆盖到所有的state-value对。随着迭代的增加在增加$ \epsilon $，让算法收敛到稳定的策略。

在使用时可以直接在每个state直接选择Greedy Action即可。

Stochastic Approximation（随机近似理论）

Mean Estimation问题

我们可以直接使用$ \mathbb{E}[X] \approx \bar{x} \doteq \frac{1}{n} \sum_{i=1}^n x_i $来计算所有的样本均值，但是这样计算均值需要我们一次拥有所有的样本，均值估计问题就是每次获取一个样本时，我们怎么样才能得到样本的均值？

算法很简单，如下所示：

$ \begin{equation} w{k+1} \doteq \frac{1}{k} \sum{i=1}^k x_i, \quad k=1,2, \ldots \end{equation} $

$ \begin{equation}wk=\frac{1}{k-1} \sum{i=1}^{k-1} x_i, \quad k=2,3, \ldots\end{equation} $

$ \begin{equation}w{k+1}=\frac{1}{k} \sum{i=1}^k xi=\frac{1}{k}\left(\sum{i=1}^{k-1} x_i+x_k\right)=\frac{1}{k}\left((k-1) w_k+x_k\right)=w_k-\frac{1}{k}\left(w_k-x_k\right)\end{equation} $

均值估计问题重要的原因是因为不管是ActionValue还是StateValue实际上都是求了期望，也就是均值估计，均值估计又是SGD的特例，SDG又是RM算法的特例，所以这章反复提及均值估计问题，后续可以使用SGD和RM算法来分析相关的问题。

Robbins-Monro（RM） 算法

RM算法是对未知表达式的函数$ g(w) $求根的一种算法，如下所示：

$ \begin{equation} \begin{aligned} \tilde{g}(w, \eta)&=g(w)+\eta \ w_{k+1}&=w_k-a_k \tilde{g}\left(w_k, \eta_k\right) \end{aligned} \end{equation} $

其中$ g(w) $是一个不知道表达式的函数，$ \eta $是观察噪声，$ a_k $是一个正系数，$ w_k $是第$ k $次的求根的估计值。

满足下面条件时RM算法一定会收敛，这里只记录结论，推导和分析看书上的6.2一节。

先看条件(c)，当观察噪声是独立同分布(i.i.d)时，这个式子一定满足，因为观察噪声一般都假设是i.i.d，所以这个条件恒成立，不怎么重要。

再看条件(a)，它要求函数$ g(w) $必须有界且单调递增。对于一个凸优化问题，这个条件也常常满足。

最后看条件(b)，它用于保证算法收敛且不管初始的猜测$ w_0 $离最优解$ w^{\star} $多远都能最终收敛，这个的分析看书上。

由条件（b）引出的问题是到底该选什么样的$ a_k $才能满足条件，答案是选择$ a_k=\frac{1}{k} $就是合适的。

需要注意的是在实际使用时$ ak $常常会选一个小的常数，这样条件（b）不满足（因为$ \sum{k=1}^{\infty} a_k^2=\infty $），但是算法在一些情况下仍然收敛，这个了解一下就行。

SGD是RM算法的一种特例，Mean Estimation问题又是SGD的一种特例，这章的主要目的是介绍一些强化学习中使用的理论，了解一下就好，用到了再翻。

Stochastic Gradient Descent （SGD）

试图解最优化问题：

$ \begin{equation}\min _w J(w)=\mathbb{E}[f(w, X)]\end{equation} $

直接使用梯度下降有：

$ \begin{equation}w_{k+1}=w_k-\alpha_k \nabla_w J\left(w_k\right)=w_k-\alpha_k \mathbb{E}\left[\nabla_w f\left(w_k, X\right)\right]\end{equation} $

问题出在计算$ \mathbb{E}\left[\nabla_w f\left(w_k, X\right)\right] $需要所有的样本，所以使用梯度$ \nabla_w f\left(w_k, X\right) $直接代替$ \mathbb{E}\left[\nabla_w f\left(w_k, X\right)\right] $，这就是随机梯度下降算法：

$ \begin{equation}w_{k+1}=w_k-\alpha_k \nabla_w f\left(w_k, x_k\right)\end{equation} $

这个算法之所以有效是因为可以证明$ \mathbb{E}\left[\etak\right]=\mathbb{E}\left[\nabla_w f\left(w_k, x_k\right)-\mathbb{E}\left[\nabla_w f(w, X)\right]\right]=\mathbb{E}{x_k}\left[\nabla_w f\left(w_k, x_k\right)\right]-\mathbb{E}_X\left[\nabla_w f(w, X)\right]=0 $，具体证明看书上这里只简单记录一下结果。

Temporal-Difference Methods

Temporal-Difference是一类算法，但是在这里专指TD算法这一种用于估计state Values的算法

TD算法

回忆贝尔曼方程，它可以写成如下形式：

$ \begin{equation} \begin{aligned} v\pi(s) & =\mathbb{E}\left[G_t \mid S_t=s\right] =\mathbb{E}\left[R{t+1}+\gamma G{t+1} \mid S_t=s\right] \ \mathbb{E}\left[G{t+1} \mid St=s\right]&=\sum_a \pi(a \mid s) \sum{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v\pi\left(s^{\prime}\right) =\mathbb{E}\left[v\pi\left(S{t+1}\right) \mid S_t=s\right] \ v\pi(s)&=\mathbb{E}\left[R{t+1}+\gamma v\pi\left(S_{t+1}\right) \mid S_t=s\right], \quad s \in \mathcal{S} \ \end{aligned} \end{equation} $

如果定义函数为：

$ \begin{equation} g\left(v\pi\left(s_t\right)\right) \doteq v\pi\left(st\right)-\mathbb{E}\left[R{t+1}+\gamma v\pi\left(S{t+1}\right) \mid S_t=s_t\right] \end{equation} $

那么公式（27）实际上等于$ g\left(v\pi\left(s_t\right)\right)=0 $。为了求$ v{\pi}(s_t) $，可以使用RM算法，最后就得到了如下解：

$ \begin{equation}\begin{aligned}v{t+1}\left(s_t\right) & =v_t\left(s_t\right)-\alpha_t\left(s_t\right) \tilde{g}\left(v_t\left(s_t\right)\right) \& =v_t\left(s_t\right)-\alpha_t\left(s_t\right)\left(v_t\left(s_t\right)-\left[r{t+1}+\gamma v\pi\left(s{t+1}\right)\right]\right)\end{aligned}\end{equation} $

注意到公式（29）右侧是$ v\pi\left(s{t+1}\right) $，原因是这里我们计算的是$ st $的State Values从而假设其他State Values都是已知的，如果将$ v\pi\left(s{t+1}\right) $替换成$ v\left(s{t+1}\right) $，那么我们就得到了TD 算法：

$ \begin{equation}\begin{aligned}v{t+1}\left(s_t\right) & =v_t\left(s_t\right)-\alpha_t\left(s_t\right)\left[v_t\left(s_t\right)-\left(r{t+1}+\gamma vt\left(s{t+1}\right)\right)\right] \v_{t+1}(s) & =v_t(s), \quad \text { for all } s \neq s_t\end{aligned}\end{equation} $

因为算法只计算$ st $的state Value，所以上式中的第二部分是trivial的，这里列出只用于补全。值得注意的是将$ v\pi\left(s{t+1}\right) $替换成$ v\left(s{t+1}\right) $算法是否还是可以收敛，答案是肯定的，但是这里略过证明，详细证明参考书上对应章节。

对公式（29）进一步分析：

$ \begin{equation} \begin{aligned} \bar{v}t &\doteq r{t+1}+\gamma vt\left(s{t+1}\right) \ \underbrace{v{t+1}\left(s_t\right)}{\text {new estimate }}&=\underbrace{vt\left(s_t\right)}{\text {current estimate }}-\alphat\left(s_t\right)[\overbrace{v_t\left(s_t\right)-(\underbrace{r{t+1}+\gamma vt\left(s{t+1}\right)}_{\text {TD target } \bar{v}_t})}^{\text {TD error } \delta_t}] \end{aligned} \end{equation} $

这个式子的意思是新的state value的估计值是通过当前state value的估计值加上修正来得到的，至于为什么后面一项是修正值，$ \bar{v}_t $为什么被称为TD target，可以参考书上7.1.2一节。对这个公式的理解非常重要，需要熟练掌握。

Sarsa算法

回忆从Action Values表示的贝尔曼方程，同TD算法，这个贝尔曼方程可以写成：

$ \begin{equation}q\pi(s, a)=\mathbb{E}\left[R+\gamma q\pi\left(S^{\prime}, A^{\prime}\right) \mid s, a\right]\end{equation} $

同样类似TD算法，我们也可以用RM算法得到对Action Values迭代方式的计算方法如下：

$ \begin{equation}\begin{aligned}q{t+1}\left(s_t, a_t\right) & =q_t\left(s_t, a_t\right)-\alpha_t\left(s_t, a_t\right)\left[q_t\left(s_t, a_t\right)-\left(r{t+1}+\gamma qt\left(s{t+1}, a{t+1}\right)\right)\right] \q{t+1}(s, a) & =q_t(s, a), \quad \text { for all }(s, a) \neq\left(s_t, a_t\right)\end{aligned}\end{equation} $

有了计算Action Values的方法，可以结合Policy Improvement（使用$ \epsilon $-Greedy）获得Sarsa算法：

Q-learning

与前面提到的Sarsa不同，Q-learning则是通过使用RM算法解贝尔曼最优得到的。证明见书上的7.4.1一节。直接列举Q-learning算法如下：

$ \begin{equation}\begin{aligned}q{t+1}\left(s_t, a_t\right) & =q_t\left(s_t, a_t\right)-\alpha_t\left(s_t, a_t\right)\left[q_t\left(s_t, a_t\right)-\left(r{t+1}+\gamma \max {a \in \mathcal{A}\left(s{t+1}\right)} qt\left(s{t+1}, a\right)\right)\right] \q_{t+1}(s, a) & =q_t(s, a), \quad \text { for all }(s, a) \neq\left(s_t, a_t\right),\end{aligned}\end{equation} $

Q-learning可以是on-policy，也可以是off-policy，这给了Q-learning可以使用神经网络的可能。

对比

所有的TD算法都可以写成如下形式，目前为止学到的算法本质上则只是求解贝尔曼方程或者贝尔曼最优方程的形式不同或者对TD target $ \bar{q}_{t} $的形式不同的差异：

$ \begin{equation}q_{t+1}\left(s_t, a_t\right)=q_t\left(s_t, a_t\right)-\alpha_t\left(s_t, a_t\right)\left[q_t\left(s_t, a_t\right)-\bar{q}_t\right],\end{equation} $

Sarsa、n-step Sarsa以及Monte Carlo都是on-policy，也就是说它们的behavior Policy和target Policy是相同的。

Value Function Approximation

回忆前面的章节，不管是State Values还是Action Values，我们都使用如下的表格来表示它：

但是在一些情况下，State值可能很多，甚至可能是连续的，使用表格来表示不太方便；同时在使用表格形式表示时，假如需要调整$ s_i $的State Value，那么我们需要查表找到表里$ s_i $的位置修改它，其他位置不会收到影响，这样的表示方法泛化性比较差。

所谓的Value Function Approximation就是将State Values或者Action Values使用函数来表示，因为函数对这些值的表示是一个拟合过程，所以被称为Value Function Approximation。

（既然是个值函数拟合过程，那么自然这些值很适合使用神经网络来表示）

使用TD Learning近似State Values

近似State Values是一个最小二乘问题：

$ \begin{equation}J(w)=\mathbb{E}\left[\left(v_\pi(S)-\hat{v}(S, w)\right)^2\right]\end{equation} $

其中$ v_{\pi}(S) $是真实的State Values函数，$ \hat{v}(S,w) $是其估计。为了最小化这个函数，我们有：

$ \begin{equation} \begin{aligned} w{k+1}&=w_k-\alpha_k \nabla_w J\left(w_k\right) \ \nabla_w J\left(w_k\right) & =\nabla_w \mathbb{E}\left[\left(v\pi(S)-\hat{v}\left(S, wk\right)\right)^2\right] \ & =\mathbb{E}\left[\nabla_w\left(v\pi(S)-\hat{v}\left(S, wk\right)\right)^2\right] \ & =2 \mathbb{E}\left[\left(v\pi(S)-\hat{v}\left(S, wk\right)\right)\left(-\nabla_w \hat{v}\left(S, w_k\right)\right)\right] \ & =-2 \mathbb{E}\left[\left(v\pi(S)-\hat{v}\left(S, wk\right)\right) \nabla_w \hat{v}\left(S, w_k\right)\right] \ \Longrightarrow w{k+1}&=wk+2 \alpha_k \mathbb{E}\left[\left(v\pi(S)-\hat{v}\left(S, w_k\right)\right) \nabla_w \hat{v}\left(S, w_k\right)\right] \end{aligned} \end{equation} $

不失一般性，可以把上面式子中的$ 2 $合并进$ \alpha_{k} $，并且使用随机梯度下降（SGD）有：

$ \begin{equation} w{t+1}=w_t+\alpha_t\left(v\pi\left(s_t\right)-\hat{v}\left(s_t, w_t\right)\right) \nabla_w \hat{v}\left(s_t, w_t\right) \end{equation} $

由于$ v_{\pi} $是真实的State Values，我们并不知道这个值，所以只能前面学过的Monte Carlo或者TD来估计，分别有：

$ \begin{equation} \begin{aligned} w{t+1}&=w_t+\alpha_t\left(g_t-\hat{v}\left(s_t, w_t\right)\right) \nabla_w \hat{v}\left(s_t, w_t\right) \qquad \text{(Monte Carlo Method)} \ w{t+1}&=wt+\alpha_t\left[r{t+1}+\gamma \hat{v}\left(s_{t+1}, w_t\right)-\hat{v}\left(s_t, w_t\right)\right] \nabla_w \hat{v}\left(s_t, w_t\right) \qquad \text{(TD Method)} \end{aligned} \end{equation} $

其中$ gt $是使用Monte Carlo对$ v{\pi}(st) $的近似，$ r{t+1}+\gamma \hat{v}\left(s_{t+1}, w_t\right) $是TD target。

这里面函数$ \hat{v}(s_t,w_t) $可以使用神经网络拟合，也可以直接使用线性函数代替，如果使用神经网络的话，输入是State $ s $，输出是State Value，输入多个样本拟合出来就可以了。问题是$ \nabla_w \hat{v}\left(s_t, w_t\right) $ 如果是神经网络怎么算？

使用Sarsa和Q-Learning近似Action Values

遵从同上面一节的最小二乘方法，只需要把State Values换成Action Values，就可以得到近似的Action Values：

$ \begin{equation}w{t+1}=w_t+\alpha_t\left[r{t+1}+\gamma \hat{q}\left(s{t+1}, a{t+1}, w_t\right)-\hat{q}\left(s_t, a_t, w_t\right)\right] \nabla_w \hat{q}\left(s_t, a_t, w_t\right)\end{equation} $

集合Sara算法，有：

同样对Q-Learning则有类似的结果：

$ \begin{equation}w{t+1}=w_t+\alpha_t\left[r{t+1}+\gamma \max {a \in \mathcal{A}\left(s{t+1}\right)} \hat{q}\left(s_{t+1}, a, w_t\right)-\hat{q}\left(s_t, a_t, w_t\right)\right] \nabla_w \hat{q}\left(s_t, a_t, w_t\right)\end{equation} $

Deep Q-Learning

Deep Q-Learning本质上也是值函数近似的一种，只不过使用的是神经网络来代替Action Values。

Experience Replay

经验回放是所有off-policy算法都会使用的技巧。在前面介绍的非深度强化学习的算法中，都是来一个Experience就立马被拿去做模型更新了，但是在深度学习中如果使用一个一个样本去更新很容易让网络变的不稳定而且效率比较低。另一个问题是在深度学习里的样本需要是独立同分布（i.i.d），但是显然多个连续的Experience不是独立的，经验回放便是用来解决这个问题。

所谓经验回放就是不立即使用得到的Experience，而是通过将Experience先缓存到Experience Buffer，然后网络每次从Experience Buffer里面随机取一些数据（Batched Experience）用于训练，这样每次迭代的样本就近似满足i.i.d的条件了。

算法细节

Q-Learning是通过使用RM算法解使用Action Values表示的贝尔曼最优方程得到的，Deep Q-Learning的优化目标就是与贝尔曼最优方程的平方误差：

$ \begin{equation}J=\mathbb{E}\left[\left(R+\gamma \max _{a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, w\right)-\hat{q}(S, A, w)\right)^2\right]\end{equation} $

为了最优化这个目标，我们使用随机梯度下降方法，需要注意的是不仅$ \hat{q}(S, A, w) $与$ w $有关，$ R +\max _{a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, w\right) $也与$ w $有关。所以目标目标函数的梯度如下：

$ \begin{equation}\nablaw J=-\mathbb{E}\left[\left(R+\gamma \nabla_w \max {a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, w_T\right)-\hat{q}(S, A, w)\right) \nabla_w \hat{q}(S, A, w)\right]\end{equation} $

在SGD下，我们关心的是$ \left(R+\gamma \nablaw \max {a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, wT\right)-\hat{q}(S, A, w)\right) \nabla_w \hat{q}(S, A, w) $，如果达到最优解，那么应该有$ R+\gamma \nabla_w \max {a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, wT\right)=\hat{q}(S, A, w) $，也就是说我们想让$ R+\gamma \nabla_w \max {a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, w_T\right)-\hat{q}(S, A, w) $最小化。

Deep Q-Learning的解决方法是使用两个网络，一个网络称为main network，输入是$ \left(s, a, r, s^{\prime}\right) $，输出是Action Values的估计$ \hat{q}\left(S, A, w\right) $；另一个网络是target network，输入是$ \left(s^{\prime},a\right) $，输出的是$ \max {a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, w\right) $，结合$ r $得到Q的期望值，$ r +\max {a \in \mathcal{A}\left(S^{\prime}\right)} \hat{q}\left(S^{\prime}, a, w\right) $；然后使用两个网络的输出计算Loss并更新main network，虽然每隔$ C $步将main network的参数复制到target network，如下图所示：

算法如下：

上面算法中模型更新不一定每个时间步都更新，可以隔一段时间再更新。

DQN只是使用网络计算出了Action Values，还是需要结合Policy Improvement使用Action Values来更新策略。

Policy Gradient Methods

上面提到的是将State Values和Action Values使用函数近似，这一章的目标是将Policy使用函数近似然后直接优化Policy。近似的Policy使用 $ \pi_\theta(a \mid s) = \pi(a \mid s, \theta) $表示，其中$ \theta $是参数。

想直接优化Policy的一个关键问题是如何定义最优的Policy，以前的方法都是通过值（State Values & Action Values）来定义，直接优化Policy后变成了优化某种度量（metric），

重要的是这种度量是什么？怎么使用这种度量得到最优Policy？以及怎样利用Experience来优化Policy？

Policy Gradient

目前常用的有两种度量：平均State Values $ \bar{v}{\pi} $和平均单步奖励 $ \bar{r}{\pi} $（average one-step reward ），他们有多种形式，如下：

这些Metric都与策略$ \pi $有关，而$ \pi $都是$ \theta $的函数，所以这些Metric也是$ \theta $的函数，不同的$ \theta $会得到不同的Metric值，所以我们可以通过优化这些metric来得到最优Policy。实际上这两种metric有如下关系：

$ \begin{equation} \bar{r}\pi=(1-\gamma) \bar{v}\pi, \qquad \gamma < 1 \end{equation} $

其中$ \gamma $是Discounted Rate。

为了找到最优的Policy，直接的想法就是优化这些metric，而对这些metric的优化自然的需要对它们进行求导，这个求导过程比较复杂，直接给出结论，不管是对平均State Values还是平均单步奖励，不管是不是考虑discounted return，最终梯度都可以总结为如下形式：

$ \begin{equation} \begin{aligned} \nabla\theta J(\theta)&=\sum \eta(s) \sum \nabla\theta \pi(a \mid s, \theta) q\pi(s, a) \ &=\mathbb{E}{S \sim \eta, A \sim \pi(S, \theta)}\left[\nabla\theta \ln \pi(A \mid S, \theta) q\pi(S, A)\right] \end{aligned} \end{equation} $

由于式子中存在$ \ln $函数，所以要求$ \pi(a|s,\theta) $对于所有的$ (s,a) $均大于0，这可以通过让$ \pi(a|s,\theta) $称为一个softmax functions来实现：

$ \begin{equation}\pi(a \mid s, \theta)=\frac{e^{h(s, a, \theta)}}{\sum_{a^{\prime} \in \mathcal{A}} e^{h\left(s, a^{\prime}, \theta\right)}}, \quad a \in \mathcal{A}\end{equation} $

其中$ h(s,a,\theta) $表示在状态$ s $时选择动作$ a $的偏好。需要注意的是$ \pi(a|s,\theta) $对于所有动作$ a $都有$ \pi(a|s,\theta) $，因此得到的Policy是随机的，这意味着Policy不直接产生在状态$ s $时的动作$ a $，而是根据概率分布随机生成一个动作$ a $。

REINFORCE（Monte Carlo Policy Gradient）

直接使用梯度下降可以得到参数$ \theta $的优化方法：

$ \begin{equation}\begin{aligned}\theta{t+1} & =\theta_t+\alpha \nabla\theta J\left(\thetat\right) \& =\theta_t+\alpha \mathbb{E}\left[\nabla\theta \ln \pi\left(A \mid S, \thetat\right) q\pi(S, A)\right]\end{aligned}\end{equation} $

进一步如果使用SGD可以得到：

$ \begin{equation}\theta{t+1}=\theta_t+\alpha \nabla\theta \ln \pi\left(a_t \mid s_t, \theta_t\right) q_t\left(s_t, a_t\right)\end{equation} $

其中$ q_t(s_t,a_t) $使用Monte Carlo生成即可，所以可以得到第一个直接求解最优策略的算法REINFORCE：

注意：这里$ \theta $是Policy的参数，更新$ \theta $就是更新Policy，所以说这是一个直接求取Policy的方法。

Actor-Critic Methods

QAC

从公式（51）可以看到，这个公式直接更新Policy的参数$ \theta $，同时也需要使用值估计方法得到的$ q_t\left(s_t, a_t\right) $，所以这个公式即牵扯到Policy，又牵扯到对值的估计。所谓的Actor-Critic就是指的这个过程，其中Actor表示基于某种策略来执行Action，Critic对应计算值估计来评价策略好坏。在REINFORCE中我们使用Monte Carlo来做值估计，如果使用TD来做值估计的话就形成了最简单的Actor-Critic算法，以下是使用Sarsa做值估计的Actor-Critic算法QAC：

其中$ w $是Action Values函数的参数。

A2C

A2C的本质就是在Policy Update时减去一个Baseline $ b(S) $，加这个Baseline的作用是减少近似的方差，常用的Baseline是State Value（State Values是Action Values的平均，所以用State Values做Baseline很合适）：

$ \begin{equation} \begin{gathered} X(S, A) \doteq \nabla\theta \ln \pi\left(A \mid S, \theta_t\right)\left[q\pi(S, A)-b(S)\right] \ \theta{t+1}=\theta_t+\alpha \mathbb{E}\left[\nabla\theta \ln \pi\left(A \mid S, \thetat\right)\left[q\pi(S, A)-v\pi(S)\right]\right] \ \doteq \theta_t+\alpha \mathbb{E}\left[\nabla\theta \ln \pi\left(A \mid S, \thetat\right) \delta\pi(S, A)\right] . \ \delta\pi(S, A) \doteq q\pi(S, A)-v_\pi(S) \end{gathered} \end{equation} $

使用SGD的版本则有：

$ \begin{equation}\begin{aligned}\theta{t+1} & =\theta_t+\alpha \nabla\theta \ln \pi\left(at \mid s_t, \theta_t\right)\left[q_t\left(s_t, a_t\right)-v_t\left(s_t\right)\right] \& =\theta_t+\alpha \nabla\theta \ln \pi\left(a_t \mid s_t, \theta_t\right) \delta_t\left(s_t, a_t\right),\end{aligned}\end{equation} $

其中$ q_t\left(s_t, a_t\right)-v_t\left(s_t\right) $被称为Advantage Function，叫这个名字的原因在于当$ q_t\left(s_t, a_t\right)-v_t\left(s_t\right) $时，表示的是$ q_t(s_t,a_t) $大于了在$ s_t $的所有Action Values的平均值（State Values是Action Values的平均），说明这个Action有优势。Advantage Function可以近似为：

$ \begin{equation}qt\left(s_t, a_t\right)-v_t\left(s_t\right) \approx r{t+1}+\gamma vt\left(s{t+1}\right)-v_t\left(s_t\right)\end{equation} $

所以A2C如下所示：

所以A2C的本质就是加了个Baseline，这个Baseline是经过一系列推导简化后的$ r{t+1}+\gamma v_t\left(s{t+1}\right)-v_t\left(s_t\right) $。

重要性采样

所谓重要性采样来源于一个问题：有一些样本$ x\sim X $通过分布$ p_1 $生成，但是能不能用这些样本去计算$ p_0 $的期望，答案是可以，有如下方程成立：

$ \begin{equation}\mathbb{E}{X \sim p_0}[X]=\sum{x \in \mathcal{X}} p0(x) x=\sum{x \in \mathcal{X}} p1(x) \underbrace{\frac{p_0(x)}{p_1(x)}}{f(x)} x=\mathbb{E}_{X \sim p_1}[f(X)]\end{equation} $

这样估计$ p0 $的分布问题就变成了对$ p_1 $分布的估计问题，只不过待估计的随机变量$ X $变成了$ f(X) $。这里需要澄清的一点是虽然这里需要知道的$ p_0(x) $只是样本点的概率，不是整个分布$ X $的概率，否则我们可以通过$ \mathbb{E}{X \sim p0}[X]=\sum{x \in \mathcal{X}} p_0(x) x $直接计算期望了。

Off-policy Actor-Critic

前面提到的Actor-Critic都是on-policy。如果要使用Off-Policy的Actor-Critic，也就是Behavior Policy和Target Policy不一致时，两个Policy遵从不同的分布，我们的目标便成了通过一个分布产生的样本估计另一个分布的期望问题，这就需要使用重要性采样。

基于上面的描述，我们重新描述我们的度量如下：

$ \begin{equation}J(\theta)=\sum{s \in \mathcal{S}} d\beta(s) v\pi(s)=\mathbb{E}{S \sim d\beta}\left[v\pi(S)\right]\end{equation} $

上面的式子表示Behavior Policy $ \beta $遵循$ d_{\beta}(s) $，求取的Target Policy是$ \pi $。上面式子使用的仍然是State Value的平均，但是Behavior Policy和Target Policy不同而已。可以得到它的梯度为：

$ \begin{equation}\nabla\theta J(\theta)=\mathbb{E}{S \sim \rho, A \sim \beta}[\underbrace{\frac{\pi(A \mid S, \theta)}{\beta(A \mid S)}}{\begin{array}{c}\text { importance } \\text { weight }\end{array}} \nabla\theta \ln \pi(A \mid S, \theta) q_\pi(S, A)]\end{equation} $

使用SGD可以进一步得到：

$ \begin{equation}\theta{t+1}=\theta_t+\alpha\theta \frac{\pi\left(at \mid s_t, \theta_t\right)}{\beta\left(a_t \mid s_t\right)} \nabla\theta \ln \pi\left(a_t \mid s_t, \theta_t\right)\left(q_t\left(s_t, a_t\right)-v_t\left(s_t\right)\right)\end{equation} $

在使用Advantage Function代替则有：

$ \begin{equation}\theta{t+1}=\theta_t+\alpha\theta \frac{\pi\left(at \mid s_t, \theta\right)}{\beta\left(a_t \mid s_t\right)} \nabla\theta \ln \pi\left(a_t \mid s_t, \theta\right) \delta_t\left(s_t, a_t\right)\end{equation} $

最终算法如下所示：

确定性Actor-Critic

确定性Actor-Critic指的是对每一个状态$ s $，策略生成的Action不再是概率分布，而是某个确定性的动作。这种Actor-Critic需要把所有的metric和其梯度按照确定性策略重新推导一遍，但是思路和随机Actor-Critic类似，所以不做过多记录，需要的时候在看书就好，这里只记录一个算法：

Reference

https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning

关于强化学习数学原理的一本书，作者是西湖大学的老师，在B站和YouTube上都有对应的课程视频，本文主要是参考这系列教程所做的笔记

【RL大家说】为什么说强化学习在近年不会被广泛应用，但还要继续研究呢？ - 深度强化学习实验室 (deeprlhub.com)

JoyRL

国人写的RL的书，主要专注实践以及和深度学习结合的使用

随笔

RL本身可以作为一种方法，能解决以下特征的问题：

1. 固定场景：状态空间不大，整个trajectory不长
2. 问题不复杂：没有太多层次化的任务目标，奖励好设计
3. 试错成本低：咋作都没事
4. 数据收集容易：百万千万级别的数据量，如果不能把数据收集做到小时级别，那整个任务的时间成本就不太能跟传统的监督相比
5. 目标单纯：容易被reward function量化，比如各种super-human的游戏。对于一些复杂的目标，比如几大公司都在强调拟人化，目前没有靠谱的解决方案

比较适合用在游戏AI上，其他领域都还有待发展。