强化学习-马尔可夫决策过程

参考：

https://www.cnblogs.com/pinard/p/9426283.html

https://blog.csdn.net/liweibin1994/article/details/79079884

https://b23.tv/fOmHymj（推荐）

一、马尔可夫性

agent与environment的交互过程可以表示为一个序列：{S_0，A₀，R₁，S₁，A₁，R₂，S₂......}

马尔可夫性：下一个状态的产生只和上一个状态有关，而与更之前的状态无关。即$P\left( S_{t+1}|S_1,S_2,...,S_t \right) =P\left( S_{t+1}|S_t \right)$。这个条件虽然在某些问题上有些理想，

但是极大地简化了问题的复杂性。

二、关键概念

1、状态集：S，S_t表示t时刻的状态

2、动作集：A，A_t表示t时刻的动作

3、策略：$\pi$，$\pi\left(a|s\right)=P\left(A_t=a|S_t=s\right)$，针对某个状态既可以采取确定性的策略也可以采取随机策略

4、奖励：R，R_t表示在S_t-1时采取动作A_t-1后获得的奖励

5、长期回报：$G_t$，$G_t=R_{t+1}+\gamma R_{t+2}+\gamma ^2R_{t+3}+...$，表示S_t之后所有奖励的有衰减之和，其中$\gamma$表示衰减因子，$\gamma \in [0,1]$

6、状态价值函数：$v_\pi \left(s\right)=E_\pi \left(G_t|S_t=s\right)$

7、状态-动作价值函数：$q_\pi \left(s,a\right)=E_\pi \left(G_t|S_t=s,A_t=a\right)$

8、贝尔曼方程：

$
\begin{aligned}
    v_{\pi}\left( s \right) &=E_{\pi}\left( G_t|S_t=s \right)\\
    &=E_{\pi}\left( R_{t+1}+\gamma R_{t+2}+\gamma ^2R_{t+3}+...|S_t=s \right)\\
    &=E_{\pi}\left( R_{t+1}+\gamma \left( R_{t+2}+\gamma R_{t+3}+... \right)|S_t=s \right)\\
    &=E_{\pi}\left( R_{t+1}+\gamma G_{t+1} |S_t=s \right)\\
    &=E_{\pi}\left( R_{t+1}+\gamma v_{\pi}\left( S_{t+1} \right)|S_t=s \right)\\
\end{aligned}
$

根据下图来推导一些重要的公式：

（1）$v_{\pi}\left( s \right) =\sum_a{\pi \left( a|s \right) q_{\pi}\left( s,a \right)}$

（2）$v_{\pi}\left( s \right) =\sum_a{\pi \left( a|s \right) \sum_{s',r}{P}\left( s',r|s,a \right) \left( r+\gamma v_{\pi}\left( s' \right) \right)}$

（3）$q_{\pi}\left( s,a \right) =\sum_{s',r}{P}\left( s',r|s,a \right) \left( r+\gamma v_{\pi}\left( s' \right) \right) $

（4）$q_{\pi}\left( s,a \right) =\sum_{s',r}{P}\left( s',r|s,a \right) \left( r+\gamma \sum_{a'}{\pi \left( a'|s' \right) q_{\pi}\left( s',a' \right)} \right) $

9、最优价值函数

强化学习希望能够找到最好的策略$\pi_*$，使得$v_{\pi_*}\left( s \right)$不会比其他任何策略$\pi$的$v_{\pi}\left( s \right)$差，即$v_*(s)=\underset{\pi}{max}v_{\pi}\left( s \right)$，其中$s\in S$

同理，$q_*(s,a)=\underset{\pi}{max}q_{\pi}\left( s,a \right)$，其中$s\in S$，$a\in A$

10、最优策略

$
\pi _*\left( a|s \right) =\begin{cases}
    1\,\,\,if\,\,\underset{a}{max}q_*\left( s,a \right)\\
    0\,\,\,else\\
\end{cases}
$

此时:

（1）$v_*\left( s \right)=\underset{a}{max}q_*\left( s,a \right)$

（2）$v_*\left( s \right)=\underset{a}{max}\left( \sum_{s',r}{P(s',r|s,a)(r+\gamma v_*(s'))} \right)$

（3）$q_*\left( s,a \right)=\sum_{s',r}{P\left( s',r|s,a \right)\left( r+\gamma v_*(s') \right)}$

（4）$q_*\left( s,a \right)=\sum_{s',r}{P\left( s',r|s,a \right)\left( r+\gamma \underset{a'}{max}q_*(s',a') \right)}$