强化学习理论基础

强化学习理论基础

1、贝尔曼方程 & 贝尔曼期望方程

（1）Bellman方程

在MRP中，为了衡量一个状态未来得期望回报，引入了价值函数$v(s)$的概念，其计算方式为：
$$\begin{gathered} v(s)=E[G_t|S_t=s] \\ =E[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...|S_t=s] \\ =E[R_{t+1}+\gamma (R_{t+2}+R_{t+3}+...)|S_t=s] \\ =E[R_{t+1}+\gamma v_{(}{S}_{t+1}=s^{\prime })|S_t=s] \\ =R_{t+1}+\sum _{s^{\prime }\in S}P(S_{t+1}=s^{\prime }|S_t=s)v(s^{\prime }) \end{gathered}$$
Bellman方程这里并没有涉及策略的概念。

（2）Bellman期望方程

Bellman期望方程在MDP中引入的，这时有策略的概念，Bellman期望方程包括价值函数的期望方程的行为价值函数的期望方程，Bellman期望方程的获得可以从两个角度来看：
角度一：从Bellman方程看角度看，就是将策略的概率引入，类似的可以得到：
$$v_{\pi }(s)=R_s^a+\gamma \sum _{a\in A}\pi (a|s)\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })$$
$$Q_{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q(s^{\prime },a^{\prime })$$

角度二：利用行为价值函数，过程为：
a、引入行为价值函数$$Q_{\pi }(s,a)$$
b、得到价值函数与行为价值函数之间的关系：
$$v_{\pi }(s)=\sum _{a\in A}\pi (s,a)Q_{\pi }(s,a)$$
c、推导行为价值函数的递推式子：
$$\begin{gathered} Q_{\pi }(s,a)=E[G_t|S_t=s,A_t=a] \\ =R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime }) \end{gathered}$$
d、b与c互相带入就得到Bellman期望方程：
价值函数的Bellman期望方程：
$$v_{\pi }(s)=\sum _{a\in A}\pi (s,a)(R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime }))$$
行为价值函数的Bellman期望方程：
$$Q_{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q_{\pi }(a^{\prime }.s^{\prime })$$

过程来看，行为价值函数的引入似乎是为了推导出价值函数的Bellman期望方程，但是在后续的相关算法中其回发挥很大的作用。

2、贝尔曼最优方程

最优价值函数：$$v_{\ast }(s)=\underset{\pi }{\arg }max{v}_{\pi }(s)foranystates$$
最优行为价值函数：$$Q_{\ast }(s,a)=\underset{\pi }{\arg }max{Q}_{\pi }(s,a)foranystate-actionpairs$$
确定型最优策略：
π ∗ ( a ∣ s ) = { 1 , i f    a = a r g a m a x Q ∗ ( s , a ) 0 , e l s e \pi_*(a|s)=\left\{

$$\begin{array}{l}1,if~~a=\underset{a}{arg}maxQ_*(s,a)\\0,else \end{array}$$ \right. π∗​(a∣s)={ 1,if  a=aarg​maxQ∗​(s,a)0,else​
则对于最优策略下的价值函数：
$$\begin{gathered} v_{\ast }(s)=\underset{\pi }{\arg }max{v}_{\pi }(s) \\ =\underset{\pi }{\arg }max\sum _{a\in A}\pi (s,a)Q_{\pi }(s,a) \\ =\underset{\pi }{\arg }max{Q}_{\pi }(s,a) \\ =Q_{\ast }(s,a) \end{gathered}$$
即在确定型最优策略下，价值函数与行为价值函数的值相同，此时，价值函数与行为价值函数的Bellman期望方程形式相同，称为Bellman最优方程：
$$v_{\ast }(s)=\underset{a\in A}{\max }{R}_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })$$
$$Q_{\ast }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\underset{a^{\prime }\in A}{\max }{Q}_{\ast }(s^{\prime },a^{\prime })$$

因此，根据Bellman最优方程，获得最优策略的方法为：
求解Bellman最优方程，最优策略${\pi }_{\ast }$:
$${\pi }_{\ast }(s)=\underset{a}{\max }{R}_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })$$
$${\pi }_{\ast }(s)=\underset{a}{\max }{Q}_{\ast }(s,a)$$
从上面的式子可以看出，如果求得行为价值函数，那么就可以比较快得到最优策略，所以很多时候都是直接求解行为价值函数得到最优策略。
很多时候强化学习都是形式化为MDP，因此求解强化学习问题其实就是求解Bellman最优方程。

3、预测与控制

MDP中涉及的两类基本的问题是控制和预测，控制即找到最优策略，预测即评估当前给定策略的好坏。
控制即求解Bellman最优方程，Bellman最优方程中有非线性的算子max，所以Bellman方程并不是线性方程。
预测问题即求解Bellman期望方程，其是线性方程，有解析解，但是只适用于小规模问题。
预测和控制问题根据是否知道模型分为基于模型的预测（控制）以及无模型的预测（控制）。
基于模型至少要知道下列两个条件：
（1）$$R_s^a=E[R_{t+1}|S_t=s,A_t=a]$$
（2）$$P_{s{s}^{\prime }}^a=P[S_{t+1}=s^{\prime }|S_t=s,A_t=a]$$

（1）预测问题：求解Bellman期望方程

预测问题就求解Bellman期望方程：
$$v_{\pi }(s)=\sum _{a\in A}\pi (a|s)(R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime }))$$

基于模型的预测

基于模型的预测也就是知道了下面两个条件：
（1）$$R_s^a$$
（2）$$P_{s{s}^{\prime }}^a$$

解线性方程

因为知道了Bellman期望方程的所有条件，并且Bellman期望方程是线性的，所以可以直接得到其解析解。
首先：（1）$$R_s^{\pi }=\sum _{a\in A}\pi (a|s)R_s^a$$
（2）$$P_{s{s}^{\prime }}^{\pi }=\sum _{a\in A}\pi (a|s)P_{s{s}^{\prime }}^a$$
那么Bellman期望方程就可以写为：
$$V_{\pi }=R_{\pi }+\gamma P_{\pi }{V}_{\pi }\Rightarrow V_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{R}_{\pi }$$
缺点：
（1）矩阵求逆，复杂度为$O(S^3)$，计算量大
（2）当矩阵洗漱的时候结果不一定准确
但是Bellman期望方程满足动态规划的条件：
（1）原问题包含子问题
（2）子问题重复出现
因此使用动态规划的方法求解Bellman方程，动态规划的本质就是迭代进行。

动态规划

（1）初始化一个价值函数$V_1$
（2）进行迭代：
$$V_{l+1}(s)=\sum _{a\in A}\pi (a|s)(R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_l(s))$$
收敛道真实函数$V_{\pi }$

收敛性证明：
Bellman期望算子${\tau }^{\pi }(v)=R^{\pi }+\gamma P^{\pi }v$
$$\begin{gathered} |{\tau }^{\pi }(u)-{\tau }^{\pi }(v)|\le ||{\tau }^{\pi }(u)-{\tau }^{\pi }(v)|{|}_{\infty } \\ =||R^{\pi }+\gamma P^{\pi }u-R^{\pi }-\gamma P^{\pi }v|{|}_{\infty } \\ =||\gamma P^{\pi }(u-v)|{|}_{\infty } \\ \le ||\gamma P^{\pi }||u-v|{|}_{\infty }|{|}_{\infty } \\ \le \gamma ||u-v|{|}_{\infty } \end{gathered}$$
当$\gamma <1$时Bellman期望算子是收缩的，那么经过迭代会收敛到真实的$V_{\pi }$。（$\gamma =1$时的收敛证明用其他方法，参考PPT lecture3的15页）

无模型的预测

动态规划求解预测问题的局限：对模型的依赖
（1）要么是MDP问题的模型已知
（2）要么智能体对环境建模
很多情况下是不知道模型的，所以需要找到不基于模型的方法。

蒙特卡洛方法（MC）

MC是从价值函数的本质定义出发，即$$V(s)=E[G_t]$$使用观测轨迹的回报的均值估计回报的期望。

1、MC的特点：

（1）无模型：不需要MDP的奖励函数和状态转移概率
（2）根据完整的轨迹：无自举

2、MC的基本思想：

使用观测的均值回报代替回报的期望，即价值函数

3、MC的要求：

所有的轨迹都能到达终止状态或者轨迹足够长。

4、MC方法的过程：

（1）初始版本：
a、评估状态s，在一次轨迹中首次经过s时：$$N(s)=N(s)+1$$
$$S(s)=S(s)+G_t$$（这里需要$G_t$，只有完整轨迹之后才可以得到，这也就是为什么MC需要完整的轨迹)

b、估计价值函数为$$V(s)=\frac{S(s)}{N(s)}$$
总结：需要完整的轨迹，使用回报的均值估计回报的期望
（2）改进之增量版本
$$\begin{gathered} S(s)=\frac{{\sum }_{i=1}^N{G}_{t(i)}}{N(s)} \\ =\frac{1}{N(s)}(G_{t(N)}+\sum _{i=1}^{N-1}{G}_{t(i)}) \\ =\frac{1}{N(s)}(G_{t(N)}+(N(s)-1)V(s)) \\ =V(s)+\frac{1}{N(s)}(G_t-V(s)) \end{gathered}$$
随着采样轨迹数量的增加，$N(s)\to 0$，那么学习的后期，观测量对结果的影响不大，但是如果环境时动态的、不断变化的，更希望时能够随时跟踪当前不断变化的均值：使用固定的学习率$\alpha$
$$V(s)=V(s)+\alpha (G_t-V(s))$$

时间差分

价值函数的另一个定义是Bellmman期望方程：$$V_{\pi }(s)=E[R_{t+1}+\gamma V_{\pi }(S_{t+11})]$$

1、TD特点

（1）根据非完整的轨迹学习，借助自举法
（2）根据一个猜测值更新另一个猜测值

2、TD的本质思想

类似MC，使用回报的均值估计期望，最后更新变为在当前基础上加上学习率$\ast$差值。所以类似的，TD是根据Bellman方程进行估计，也有期望，那么类似MC，也是使用到了差值，在当前的基础上+学习率$\ast$差值，差值的获得根据Bellman方程。
当前已经有一个猜测值，期望减少和真实值之间的误差，由猜测值得到的值作为其对真实值更精确的估计。

3、TD算法

时间差分，根据考虑的时间步数的不同，可以分为$TD(0)$和$TD(\lambda )$算法。
这里的TD算法是进行预测，如果是进行估计那就是叫（Srasa,sarsa(lambda))

TD(0)

1、算法过程

（1）给定策略$\pi ，初始状态分布D，V(S)=0,\alpha ,t=0$
（2）如果$S_t=S_{terminal}$或者$s_t$没有初始化，那么初始化：$$S_t\sim D$$
（3）采样动作：$$a_t\sim \pi$$
执行$a_t$观测得到$R_{t+1}$和$S_{t+1}$.
（4）根据$$(S_t,R_{t+1},S_{t+1})$$更新：$$\begin{gathered} V(S_t)=V(S_t)+\alpha (R_{t+1}+\gamma V(S_{t+1})-V(S_t)) \\ t=t+1 \end{gathered}$$
回到（2）。

PS：TD目标：$$R_{t+1}+\gamma V(s_{t+1})$$
TD误差：$${\delta }_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$$

2、$\alpha$的选取

（1）$\alpha$小，学习慢，曲线平滑
（2）$\alpha$大，学习快，震荡明显，且可能越过真实值，一直震荡

TD($\lambda$)

1、n步回报

MC是无穷步回报，TD是一步回报，将两者结合，在TD学习中增加回报的计算步数。
$$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+{\gamma }^{(n-1)}{R}_{t+n}+{\gamma }^{n}v(S_{t+n})$$
n步回报时间差分学习：
$$v(S_t)=v(S_t)+\alpha (G_t^{(n)}-v(S_t))$$

TD与n步回报误差比较：
（1）TD（一步回报误差），使用一步期望估计价值函数，即代替回报的期望：$$\begin{gathered} max|E[G_t^{(1)}]-v_{\pi }(s_t)|=max|R_{t+1}+\gamma v_{\pi }(s_{t+1})-v(s_t)| \\ =max|R_{t+1}+\gamma v(s_{t+1})-(R_{t+1}+\gamma v_{\pi }(s_{t+1}))| \\ \le \gamma ||v-v_{\pi }|{|}_{\infty } \end{gathered}$$
（2）n步回报:
$$max|E[G_t^{(n)}]-v_{\pi }(s_t)|\le {\gamma }^n||v-v_{\pi }|{|}_{\infty }$$

使用机器学习中的方差-偏差分析：
（1）n大，价值估计准确性高，偏差小，但是随着采样数据的增加，方差大
（2）n小，价值估计准确性低，偏差大，但是采样数据少，方差小

那么n应该怎样取值？
均值化n步回报

2、$\lambda$回报

将所有n步回报整合在一起，系数为$(1-\lambda )\lambda$:$$无穷步轨迹：G_t^{(\lambda )}=(1-\lambda )\sum _{n=1}^{\infty }{\lambda }^{n-1}{G}_t^{(n)}$$
$$轨迹在T终止：G_t^{(\lambda )}=(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}{G}_t^{(n)}+{\lambda }^{(T-t+1)}{G}_t$$

3、前向$TD(\lambda )$

$$v(S_t)=v(S_t)+\alpha (G_t^{(\lambda )}-v(S_t))$$

好处：之前n步回报的缺点是方差增大，但是这里随着n的增加，其权重不断减小，因此既利用了长步数估计的精度，又降低了高方差的影响。

前向：对每个访问的状态，都是从其开始往前看所有未来的奖励，并结合这些奖励来更新价值函数。
特点：
（1）更新价值函数向$\lambda$-回报逼近
（2）需要未来时刻的观测计算$G_t^{(\lambda )}$
（3）与MC一样要求完整的轨迹
（4）离线学习

4、资格迹

反映了被观测的次数和频率，结合了历史和现在
E t ( s ) = { γ λ E t − 1 , s t ≠ s γ λ E t − 1 + 1 , s t = s E_t(s)=\left\{

$$\begin{array}{l}\gamma \lambda E_{t-1},s_t\neq s\\\gamma\lambda E_ {t-1}+1,s_t=s \end{array}$$ \right. Et​(s)={ γλEt−1​,st​​=sγλEt−1​+1,st​=s​

5、后向$TD(\lambda )$

使用TD估计价值函数，误差由过程中的状态共同导致，资格迹表征了每个状态对误差的贡献，如何权分误差：使用资格迹。
（1）、任意初始化$V(s)$
（2）、每个episode重复（3）（4）
（3）、E(S)=0
（4）、对episode的每一步：
a、$a\sim \pi$，执行动作 观测奖励r和下一个状态s’
b、$\delta =r+\gamma v(s^{\prime })-v(s),E(s)=E(s)+1$
c、对所有的状态分摊误差：$V(S)=V(S)+\alpha \delta E(S)$
$$E(S)=\gamma \lambda E(S)$$
d、$s\leftarrow s^{\prime }$
问题：误差的求解是根据当前步得到的，但是更新的时候是将误差平坦到所有的状态，这时候需要对所有的状态更新，那么需要知道所有的状态，对于连续状态的问题涉及的状态是无穷的，这个问题的本质就是状态空间太大，状态空间太大的问题将通过价值函数逼近器的方法解决。
这里仍然是无模型的，无模型指的是不知道动作奖励函数和转移概率，并不是不知道所有的状态，注意区分。

6、前向和后向$TD(\lambda )$

定理：当使用离线更新时，后向和前向$TD(\lambda )$在同一轨迹上的更新量时相同的：
$$\begin{gathered} \sum _{t=0}^T\Delta V_t^{TD}(S)=\sum _{t=0}^T\Delta V_{t=0}^{\lambda }(s_t)I(S=s_t)任意的s\in S \\ \Delta V_t^{TD}(S)=\alpha {\delta }_t{E}_t(S) \\ \Delta V_t^{\lambda }(s_t)=\alpha (G_t^{\lambda }-V_t(s_t)) \end{gathered}$$
向前：轨迹中每遇到一次进行一次更新
向后：每一步都进行一次更新

前向$TD(\lambda )$，每遇到一次进行更新，那么一次更新为：
$$\begin{gathered} \frac{1}{\alpha }\Delta V_t^{\lambda }(s_t)=G_t^{\lambda }-V_t(s_t) \\ =-V_t(s_t)+(1-\lambda )\sum _{n=1}^{T-t-1}{\lambda }^{n-1}{G}_t^{(n)}+{\lambda }^{T-t-1}{G}_t \\ =-V_t(s_t)+(1-\lambda ){\lambda }^0(R_{t+1}+\gamma V_t(s_{t+1}) \\ +(1-\lambda ){\lambda }^1(R_{t+1}+\gamma R_{t+2}+{\gamma }^2{V}_t(s_{t+2}) \\ +(1-\lambda ){\lambda }^2(R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+{\gamma }^3{V}_t(s_{t+3}) \\ +........ \\ =-V_t(s_t)+R_{t+1}+\gamma \lambda R_{t+2}+(\gamma \lambda {)}^2{R}_{t+3}+....+ \\ +(1-\lambda ){\lambda }^0\gamma V_t(s_{t+1})+(1-\lambda ){\lambda }^1{\gamma }^2{V}_t(s_{t+2})+.... \\ =-V_t(s_t)+R_{t+1}+\gamma \lambda R_{t+2}+(\gamma \lambda {)}^2{R}_{t+3}+....+ \\ (\gamma \lambda {)}^0(V_t(s_{t+1})-\gamma \lambda V_t(s_{t+1})+(\gamma \lambda {)}^1(V_t(s_{t+2})-\gamma \lambda V_t(s_{t+2}))+... \\ =(\gamma \lambda {)}^0(R_{t+1}+V_t(s_{t+1})-\gamma \lambda V_t(s_{t+1}))+ \\ (\gamma \lambda {)}^1(R_{t+2}+V_t(s_{t+2})-\gamma \lambda V_t(s_{t+2}))+.... \\ =\sum _{k=t}^T(\gamma \lambda {)}^{(k-t)}{\delta }_k \end{gathered}$$
则：
$$\sum _{t=0}^T\Delta V_t^{\lambda }(s_t)I(s=s_t)=\sum _{t=0}^T\alpha I(s=s_t)\sum _{k=t}^T(\gamma \lambda {)}^{k-t}{\delta }_k$$

后向$TD(\lambda )$，每一步都要进行一次更新：
首先，完整轨迹上的资格迹等于：
$$E_t(s)=\sum _{k=0}^t(\gamma \lambda {)}^{t-k}I(s_k=s)，即k时第一次出现$$
那么后向的更新量：
$$\begin{gathered} \sum _{t=0}^T\Delta V_t^{TD}(s)=\sum _{t=0}^T\alpha {\delta }_t\sum _{k=0}^t(\gamma \lambda {)}^{t-k}I(s_k=s) \\ =\sum _{t=0}^T\alpha \sum _{k=t}^T(\gamma \lambda {)}^{t-k}{\delta }_{k}I(s_k=s) \\ =\sum _{t=0}^T\alpha I(s_t=s)\sum _{k=t}^T(\gamma \lambda {)}^{t-k}{\delta }_k \\ （首次出现有了资格迹之后才在之后的每一步都进行更新） \end{gathered}$$

因此，离线的时候前向和后向是等价的。
总结：

前向提供理论依据
后向给出算法实现
在离线更新时两者等价
但实际应用时往往使用在线的后向$TD(\lambda )$：在线学习、每一时刻更新、可以适用轨迹中的一小段，非完整轨迹

7、TD(0) & MC & TD($\lambda$)

使用后向的角度进行关系寻找：

$\lambda =0$

资格迹： E t ( s ) = { 0 , S t ≠ s 1 , S t = s E_t(s)=\left\{

$$\begin{array}{l}0,S_t\neq s\\1,S_t=s\end{array}$$ \right. Et​(s)={ 0,St​​=s1,St​=s​
更新量： $$\Delta V_t^{TD}(s)=\{\begin{array}{l}0,S_t\ne s\\ \alpha {\delta }_t,S_t=s\end{array}$$
等同于TD(0): $$v(s_t)\leftarrow v(s_t)+\alpha {\delta }_t$$

$\lambda =1$

资格迹的累积：$$\begin{gathered} E_t(s)={\sum }_{k=t}^T(\gamma \lambda {)}^{t-k}={\sum }_{t=k}^T{\gamma }^{t-k}即当 \\ t=k \\ 的时候第一次遇到该状态，此后的每一步才对误差进行摊分 \end{gathered}$$
那么假设离散更新，在整条轨迹上的更新量：$$\begin{gathered} \Delta V_t^{TD}(s)=\alpha \sum _{t=k}^T{\delta }_k(\gamma {)}^{t-k} \\ =\alpha {\delta }_k+\gamma {\delta }_{k+1}+...+{\gamma }^{T-k}{\delta }_T \\ =\alpha [(R_{k+1}+\gamma V_t(s_{k+1})-V_t(s_k))+ \\ \gamma (R_{k+2}+\gamma V_t(s_{k+2})-V_t(s_{k+1}))+... \\ +{\gamma }^{T-k}(R_{T+1}+0-V_T(s_T))] \\ =\alpha (R_{k+1}+\gamma R_{k+2}+...+{\gamma }^{T-k}{R}_T-V_t(s_k)) \\ =\alpha (G_k-V_t(s_k)) \end{gathered}$$

所以离线TD(1)方法在同一个轨迹对某一状态的累计更新量等于该状态的MC更新。
但是实际上往往使用在线TD(1)方法，这是因为：
在线，增量式，学习效率高，对于MC要求整条轨迹结束后再更新。

总结与比较

1、MC & TD(0)

MC（采样）：
（1）需要完整的轨迹

（2）零偏差，高方差

（3）好的收敛性，即使是使用逼近器也能保证收敛

（4）与价值函数初始值无关

（5）原理简单，使用方便

（6）MC对应最小二乘，没有利用马尔可夫性，不需要直到后续的状态，在非马尔可夫环境下同样有效

TD(0)（自举）：
（1）不需要完整的轨迹，单步更新

（2）有偏差，低方差

（3）TD(0)能够收敛，但是与逼近器结合后没有收敛保证

（4）受价值函数初始值影响

（5）TD收敛结果对应最大似然马尔可夫模型，利用了马尔可夫性，需要直到后续状态，在马尔可夫环境下更加有效

2、 MC/TD/DP

自举

更新时包含一个猜测量：TD,DP

采样

使用采样的数据计算期望：TD,MC

（2）控制问题：求解Bellman最优方程

基于模型的控制

控制问题求解的是Bellman最优方程：
$$V_{\ast }(s)=\underset{a}{\max }(R_s^a+\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime }))$$
Bellman最优方程是非线性方程，不能直接求解，但是其仍有动态规划的特点，因此也采用迭代的方式求解。
同样的，基于模型的控制我们仍然直到下面两个条件：
（1）$$R_s^a$$
（2）$$P_{s{s}^{\prime }}^a$$
基于模型的控制有两种方法：价值迭代和策略迭代

价值迭代

（1）、初始化一个函数$V_1$
（2）、根据已知的价值函数$V_k$更新一个新的函数：
$$\begin{gathered} v_{k+1}(s)=\underset{a}{\max }(R_s^a+\gamma \sum _{s^{\prime }\in A}{P}_{s{s}^{\prime }}^a{v}_k(s)) \\ k=k+1 \end{gathered}$$
（3）、重复（2）直到收敛或者误差达到一定的范围
收敛性证明：
首先定义价值迭代算子$$\tau (v)=\underset{a}{\max }(R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}v)$$
$$\begin{gathered} |[\tau (u)](s)-[\tau (v)](s)|\le ||[\tau (u)](s)-[\tau (v)](s)|{|}_{\infty } \\ =||[\underset{a}{\max }{R}_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}u(s^{\prime })]-[\underset{a}{\max }{R}_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}v(s^{\prime })]|{|}_{\infty } \\ \le \underset{a}{\max }||\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a(u(s^{\prime })-v(s^{\prime }))|{|}_{\infty } \\ \le \gamma ||u(s^{\prime })-v(s^{\prime })|{|}_{\infty } \end{gathered}$$
因此，当$\gamma <1$的时候价值迭代算子$\tau$就是收缩算子，则：
$$\begin{gathered} ||v_{k+1}(s)-v_{\ast }(s)|{|}_{\infty }=||[\tau (v_{k+1})](s)-[\tau (v_{\ast })](s)|{|}_{\infty } \\ \le \gamma ||v_k(s^{\prime })-v_{\ast }(s^{\prime })|{|}_{\infty } \\ \le {\gamma }^k||v_1(s^{\prime })-u_{\ast }(s^{\prime })|{|}_{\infty } \\ k\to \infty ,v_k\to v_{\ast } \end{gathered}$$
$\gamma =1$的收敛性证明见PPT lecture3 page15

策略迭代

（1）给定一个初始策略${\pi }_1,k=1$
（2）策略评估：对当前的策略使用Bellman期望方程计算价值函数：
$$v_{\pi k}(s)=\sum _{a\in A}\pi (a|s)(R_s^a+\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi k}(s^{\prime }))$$
（3）策略提升：根据计算得到的价值函数进行贪心策略提升：
$$\begin{gathered} {\pi }_{k+1}(s)=\underset{a}{\max }(R_s^a+\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi k}(s^{\prime })) \\ k=k+1 \end{gathered}$$
（4）收敛则停止，或者达到一定的精度停止。

收敛性证明：
注意点：上述的策略提升的时候，只是进行了一步提升，先证明不断一步提升可以收敛到最优策略。
a、考虑确定性策略$s=\pi (s)$
b、从已知的策略进行贪心提升（一步提升）：
$$\begin{gathered} {\pi }^{\prime }(s)=\underset{a}{\max }(R_s^a+\sum _{s^{\prime }\in A}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })) \\ =\underset{a}{\max }{Q}_{\pi }(s,a) \end{gathered}$$
c、上述过程提升了s的一步期望：
$$\begin{gathered} Q_{\pi }(s,{\pi }^{\prime })=\underset{a}{\max }{Q}_{\pi }(s,a) \\ \ge Q_{\pi }(s,\pi (s))=v_{\pi }(s) \end{gathered}$$
d、$$\begin{gathered} v_{\pi }(s)\le Q_{\pi }(s_t,{\pi }^{\prime }(s_t)) \\ =E[R_{t+1}+\gamma v_{\pi }(s_{t+1})|a_t={\pi }^{\prime }(s_t),a_k=\pi (s_k),k>t] \\ =R(s_t,{\pi }^{\prime }(s_t))+\gamma \sum _{s_{t+1}}{P}_{s_t{s}_{t+1}}^{{\pi }^{\prime }}{v}_{\pi }(s_{t+1}) \\ \le R(s_t,{\pi }^{\prime }(s_t))+\gamma \sum _{s_{t+1}}{P}_{s_t{s}_{t+1}}^{{\pi }^{\prime }}(R(s_{t+1},{\pi }^{\prime }(s_{t+1}))+ \\ \gamma \sum _{s_{t+2}}{P}_{s_{t+1}{s}_{t+2}}^{{\pi }^{\prime }}{v}_{\pi }(s_{t+2})) \\ \le ... \\ \le E[R_{t+1}+\gamma R_{t+2}+...|a_k={\pi }^{\prime }(s_k),k\ge t] \\ =v_{{\pi }^{\prime }}(s_t) \end{gathered}$$
e、即提升了策略价值函数，这里讨论的是确定性策略，对随机性策略仍然成立。不断提升，最终收敛到价值函数值最大的$v_{\ast }$
f、$${\pi }_{\infty }(s)=\underset{a}{\max }(R_s^a+\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{{\pi }_{\infty }}(s^{\prime }))$$
满足Bellman最优方程，所以：
$$v_{\pi \infty }=v_{\ast },{\pi }_{\infty }={\pi }_{\ast }$$

总结

（1）价值迭代基于Bellman最优方程，策略迭代即使用了Bellman最优方程（策略提升），也使用了Bellman期望方程（策略评估）。
（2）价值迭代收敛之后得到最优策略，但是中间过程不产生策略；
策略迭代每次迭代开始时给定一个策略，结束时产生一个新的策略。
（3）价值迭代涉及赋值操作，计算量小，$O(|S{|}^2|A|)$
策略迭代矩阵求逆为$O(|S{|}^3)$，策略提升的代价为$O(|S{|}^2|A|)$
（4）价值迭代通常迭代次数多
策略迭代通常迭代次数少

无模型的控制

控制即找到最优的策略，价值迭代需要基于模型的信息，所以从策略迭代的方法入手，看是否能在无模型的条件下解决控制问题。
策略迭代分为策略评估和策略提升。
策略评估即求解Bellman期望方程，即可以使用无模型的预测方法：MC和TD进行策略评估。
策略提升即求解Bellman最优方程，仍然需要模型的信息，基于行为价值函数的策略提升是无模型的：
$${\pi }^{\prime }(s)=arg\underset{a}{\max }Q(s,a)$$
问题：
单纯使用贪心策略，可能会导致陷入局部最优，因此要进行探索。
（1）在线学习需要具有探索性的策略
（2）保证获得尽可能全面的模型观测数据
最简单的探索策略：$ϵ-greedy$
π ( s ) = ϵ − g r e e d y ( Q ) ( s ) = { a r g m a x a Q ( s , a )   w i t h   p r o b a b i l i t y   ϵ / m + 1 − ϵ r a n d o m   a   w i t h   p r o b a b i l i t y   ϵ / m \pi(s)=\epsilon-greedy(Q)(s)\\=\left\{

$$\begin{array}{l}arg\underset{a}{max}Q(s,a)~with~probability~\epsilon/m+1-\epsilon\\random~a~with~probability~\epsilon/m\end{array}$$ \right. π(s)=ϵ−greedy(Q)(s)={ argamax​Q(s,a) with probability ϵ/m+1−ϵrandom a with probability ϵ/m​

1、MC+行为-价值函数提升

（1）单轨迹评估策略

MC对一个策略的价值评估需要多条轨迹，能否每次策略评估的时候只使用一条轨迹：
GLIE（无限探索下的极限贪心）：当对状态行为对访问无数多次的时候，其会收敛到贪心策略。
当MC中的贪心探索的概率随着训练次数的增加趋近0，那么相当于已经对问题的状态有了比较全的探索，即访问了无数次，所以满足了GLIE，会收敛到贪心策略。
所以MC策略控制中要求探索的概率随着探索次数的增加趋近0

（2）MC控制学习

a、初始化$Q(S,A),N(S,A)=0,ϵ=1,k=1$
b、${\pi }_k=ϵ-greedy(Q)$
c、使用${\pi }_k$得到第k个轨迹，时间为0到T，t=0,1,2,…T:
如果$(s_t,a_t)$是轨迹上首次访问，那么计算（策略评估）：
$$\begin{gathered} 得到G_t \\ N(s_t,a_t)+=1 \\ Q(s_t,a_t)=Q(s_t,a_t)+\frac{1}{N(s_t,a_t)}(G_t-Q(s_t,a_t)) \end{gathered}$$
d、$$\begin{gathered} k=k+1,ϵ=\frac{1}{k} \\ {\pi }_k=ϵ-greedy(Q) \end{gathered}$$（策略提升）

3、定理

GLIE MC控制是收敛到最优动作-价值函数的。

但是实际算法运行的时候，$ϵ$更多使用的是一个固定的常值，保证新观测的数据对更新的有效性：时间差分+策略提升。

2、TD+行为-价值函数提升

to be continued

转载：https://blog.csdn.net/qq_43326818/article/details/116708279