强化学习前置知识

深度强化学习（Deep Reinforcement Learning）基础部分。

基本概念

一些数学基础

随机变量
概率密度函数
期望
随机抽样
蒙特卡洛（采样越多，越近似最优解；尽量找好的，但不保证是最好的。）

一些机器学习基础

线性模型
神经网络
反向传播和梯度下降

一些基础名词

马尔可夫决策过程

马尔科夫决策过程（Markov decision process, MDP）是对完全可观测的环境进行描述的，也就是说观测到的状态内容完整地决定了决策的需要的特征。几乎所有的强化学习问题都可以转化为MDP。

马尔科夫性

某一状态信息包含了所有相关的历史，只要当前状态可知，所有的历史信息都不再需要，当前状态就可以决定未来，则认为该状态具有马尔科夫性。

马尔科夫过程

马尔科夫过程 又叫马尔科夫链，它是一个无记忆的随机过程，可以用一个元组表示，其中S是有限数量的状态集，P是状态转移概率矩阵。

举例说明：学生马尔科夫链

如图：圆圈表示学生所处的状态，方格Sleep是一个终止状态，或者可以描述成自循环的状态，也就是Sleep状态的下一个状态100%的几率还是自己。箭头表示状态之间的转移，箭头上的数字表示当前转移的概率。

如：当学生处在第一节课（Class1）时，他/她有50%的几率会参加第2节课（Class2）；同时在也有50%的几率不在认真听课，进入到浏览facebook这个状态中。在浏览facebook这个状态时，他/她有90%的几率在下一时刻继续浏览，也有10%的几率返回到课堂内容上来。

以此类推，一个可能的学生马尔科夫链从状态Class1开始，最终结束于Sleep，其间的过程根据状态转化图可以有很多种可能性，这些都称为Sample Episodes。以下四个Episodes都是可能的：

C1 - C2 - C3 - Pass - Sleep
C1 - FB - FB - C1 - C2 - Sleep
C1 - C2 - C3 - Pub - C2 - C3 - Pass - Sleep
C1 - FB - FB - C1 - C2 - C3 - Pub - C1 - FB - FB - FB - C1 - C2 - C3 - Pub - C2 - Sleep

其状态转移矩阵如下图：

马尔科夫奖励过程

马尔科夫奖励过程在马尔科夫过程的基础上增加了奖励R和衰减系数*γ：

奖励函数R

S状态下的奖励是某一时刻(t)处在状态s下在下一个时刻(t+1)能获得的奖励期望 (当进入某个状态会获得相应的奖励)

$R_s = E[R_{t+1} | S_t = s]$

衰减系数 γ

也叫折扣未来奖励，其中γ∈ [0, 1]，引入衰减系数可以避免陷入无限循环，远期利益具有一定的不确定性，符合人类对于眼前利益的追求。

如图：（此图并没有特殊交代衰减系数值的大小）

收获 Return

收获 G_t 为在一个马尔科夫奖励链上从t时刻开始往后所有的奖励的有衰减的总和。

$G_t = R_{t+1} + γR_{t+2} + .... = \sum_{k=0} γ^k R_{t+k+1}$

其中衰减系数体现了未来的奖励在当前时刻的价值比例，在k+1时刻获得的奖励R在t时刻的体现出的价值是 [公式] ，γ接近0，则表明趋向于“近视”性评估；γ接近1则表明偏重考虑远期的利益。

状态价值函数 Sate Value Function

价值函数给出了某一状态或某一行为的长期价值。

一个马尔科夫奖励过程中某一状态的价值函数为从该状态开始的马尔可夫链收获的期望

$v(s) = E[G_t | S_t = s]$

用行为价值函数来描述某一状态下执行某一行为的价值，严格意义上说行为价值函数是“状态行为对”价值函数的简写。

举例说明收获和价值的计算

表中第二行对应各状态的即时奖励值

当γ= 1/2时，在t=1时刻) 状态( S_1 = C_1 ) 的收获分别为：

可以发现，收获是针对一个马尔科夫链中的某一个状态来说的。

当γ= 0时，上表描述的MRP中，各状态的即时奖励就与该状态的价值相同。

当γ≠ 0时，各状态的价值需要通过计算得到。

如γ分别为0, 0.9,和1三种情况下各状态的价值，如下图所示：

贝尔曼方程

在折扣未来奖励话题中，将t时刻的奖励函数R定义为

$R_t=r_t+γ(r_{t+1}+γ(r_{t+2}+...))=r_t+γR_{t+1}$

在价值函数话题中，将价值函数v(s)定义为

$v(s)=E[R_t|S_t=s]$

两个式子结合后，可以得到

$v(s)=E[r_t+γR_{t+1}|S_t=s] \\ =E[r_t+γv(S_{t+1})|S_t=s]$

上面这个公式就是贝尔曼方程的基本形态 - 它表明当前状态的奖励反馈由当前的奖励反馈和下一步的奖励反馈决定。

同时，它也表明价值函数是可以通过迭代来计算得出的。

但是贝尔曼方程有个问题，它的计算复杂度是O(n^3) ，因此直接求解仅适用于小规模的MRPs。大规模MRP的求解通常使用迭代法。

常用的迭代方法有：动态规划Dynamic Programming、蒙特卡洛评估Monte-Carlo evaluation、时序差分学习Temporal-Difference等。

动作价值函数 Action-Value function

由于每个状态之后有多种动作可以选择，每个动作之后的状态又不一样，实际情况中，我们更关心在某个状态下的不同动作的价值，这就是动作值函数Qπ(s,a)。

因为知道了某个状态下每个动作的价值，那么就可以选择价值最大的一个动作去执行了。

跟价值函数一样，动作值函数也是用奖励反馈来表示，但动作值函数的奖励反馈和价值函数的奖励反馈不一样：

动作值函数是执行完动作a_t之后得到的奖励反馈。

价值函数是多种动作对应的奖励反馈的期望值。

$Q^π(s,a)=E[r_{t+1}+λr_{t+2}+λ^2r_{t+3}+...|s,a] \\ =E_{s′}[r+λQ^π(s′,a′)|s,a]$

注：动作值函数加了π意味着在策略π下的动作价值，如果定义vπ(s)则表示在策略π下的价值函数。

最优动作值函数

最优动作值函数就是所有策略下的动作值函数的最大值。

$Q^∗(s,a)=max_π Q^π(s,a)$

因为最优的Q值必然为最大值，所以，等式右侧的Q值必然为使动作a′取最大的Q值。

由此可以引出基于贝尔曼方程的两种基本算法：

策略迭代（获取使 v(s) 最大的状态）
值迭代（获取使 Q(s,a) 最大的动作）

蒙特卡洛

蒙特卡洛 (Monte Carlo) 是一大类随机算法 (Randomized Algorithms）的总称，它们通过随机样本来估算真实值。

以近似π值为例

假设在[-1,1]随机生成x和y。所以我们生成了一些正方形区域的点。我们随机抽样n次。

由圆方程：

$x^2 + y^2 <= 1$

如果我们均匀随机抽样n个点，其中有m个点满足圆方程。

只有n够大，满足大数定理。那么我们可以认为

$m = \frac{πn}{4}$

做变化得：

$π = \frac{4m}{n}$

近似积分

近似期望

在强化学习中，我们会经常用到蒙特卡洛做期望的近似。

如果是均匀抽样，期望是定积分，所以可以用蒙特卡洛求定积分处理

但是做非均匀抽样可能比均匀抽样有更快的收敛

进一步推导：

$q_t = (1 − αt)· q_{t−1} + α_t · f(x_t)$

这个公式叫做Robbins-Monro 算法，其中 αn 称为学习步长或学习率。

参考：

https://blog.csdn.net/xg123321123/article/details/77504032

https://www.bilibili.com/video/BV1rv41167yx

https://github.com/wangshusen/DRL/blob/master/Notes_CN/DRL.pdf

https://mofanpy.com/tutorials/machine-learning/reinforcement-learning/intro-RL/

https://zhuanlan.zhihu.com/p/28084942