[人工智能]【机器学习】白板推导系列(三十四) ～ 强化学习之马尔科夫决策过程

【机器学习】白板推导系列(三十四) ～ 强化学习之马尔科夫决策过程

相关资料&参考资料：

【机器学习】白板推导系列(三十四) ～ 强化学习之马尔科夫决策过程_哔哩哔哩_bilibili

Sutton & Barto Book: Reinforcement Learning: An Introduction (incompleteideas.net)

datawhalechina/easy-rl: 强化学习中文教程，在线阅读地址：https://datawhalechina.github.io/easy-rl/

YJLAugus/Reinforcement-Learning-Notes: Reinforcement-Learning-Notes, start with MDP. (github.com)

背景介绍

Random Variable

随机变量：用大写字母代表随机变量，如$X$，$Y$。

$X$和$Y$之间相互独立，记作$X\perp Y$。

Stochastic Process

随机过程：研究的不在是单个的随机变量，而是一组随机变量。并且这一组随机变量之间存在着一种非常紧密的关系（不相互独立）。

符号表示：$\dots ,S_t,S_{t+1},S_{t+2},\dots$ ， { S t } t = 1 ∞ \lbrace S_t \rbrace ^\infty_{t=1} {St?}t=1∞?

Markov Chain/Process

马尔科夫链（马尔科夫过程）：一种特殊的随机过程，是具备马尔科夫属性（Markov Property）的随机过程。

下一个时刻仅依赖于当前时刻。

符号表示：$P(S_{t+1})\mid S_t,S_{t?1}...S_1)=P(S_{t+1}\mid S_t)$

State Space Model

状态空间模型：（HMM,Kalman Filterm Particle Filter），马尔可夫链 + 观测变量（Markov Chain + Obervation）。

挂测独立假设：观测变量跟当前状态有关，跟之前状态无关。

Markov Reward Process

（Markov Chain + Reward ）

Markov Decision Process

（Markov Reward Process + Action）

$\mathcal{S}:\text{state?set.}\to S_t$

$\mathcal{A}:\text{action?set.}?s\in \mathcal{S},\mathcal{A}(s)\to A_t$

$\mathcal{R}:\text{reward?set.},\to R_t.R_{t+1}$

如上图：$S_t$ 用来表示某一个时刻的状态。$A_{(s)}$ 表示在某一个状态时候的行为。从$S_t$状态经过 $A_t$ 到$S_{t+1}$状态，获得的奖励记作$R_{(t+1)}$。

动态特性

动态特性

Markov Chain: $\mathcal{S}$

MRP: $\mathcal{S},\mathcal{R}$

MDP: $\mathcal{S},\mathcal{R},\mathcal{A}(s),\mathcal{P}$

马尔可夫链只有一个量——状态。

描述其动态特性：状态转移矩阵

$?\begin{array}{ccc}{s}_1{s}_1& ...& s_1{s}_{10}\\ ?& ?& ?\\ s_{10}{s}_1& ...& s_{10}{s}_{10}\end{array}?$

在状态转移的过程中，对于下一个状态转移是有概率的，

动态特性： p ( s ′ , r ∣ s , a ) = ˙ P r { S t + 1 = s ′ , R t + 1 = r ∣ S t = s , A t = a } p(s',r\mid s,a) \dot{=} P_r\lbrace S_{t+1}=s',R_{t+1} = r \mid S_{t} =s,A_{t}=a \rbrace p(s′,r∣s,a)=˙Pr?{St+1?=s′,Rt+1?=r∣St?=s,At?=a}

状态转移函数（去掉了$r$）：$p(s^{\prime }\mid s,a)=\sum _{r\in R}p(s^{\prime }\mid s,a)$

reward的动态性：在 $s$ 和 $a$ 选定后，$r$ 也有可能是不同的，即 $r$ 也是随机变量。但是，大多数情况$r$随机性不怎么明显。

价值函数

策略（Policy）

符号表示：$\pi$

• 确定性策略: $a?\pi (s)$
• 随机性策略: $\pi (a\mid s)?P_r{A}_t=a|S_t=s$

回报

多个reward的加和

会引入一个折扣（discount）

$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2?+{\gamma }^{T?1}{R}_T=\sum _{i=0}{\gamma }^i{R}_{t+i+1},\gamma |in[0,1],T\to \infty$

但是这里的$G_t$仅代表了其中一系列确定的策略，但是策略会是一个随机性策略，所以这时候引入价值函数。

价值函数

在指定一个状态 $s$ ，采取一个随机策略$\pi$ ，然后加权平均，以上图为例，把9 个分叉($G_t$)加权平均。也就是期望 $E$。

$V_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$

$G_t$在$\pi$上的加权平均。

贝尔曼期望方程

贝尔曼期望方程

MDP：$\mathcal{S},\mathcal{A}(s),\mathcal{R},\mathcal{P}$
{ p ( s ′ , r ∣ s , a ) ? P r { S t + 1 = s ′ , R t + 1 = r ∣ S t = s , A t = a } \begin{cases} p(s',r\mid s,a) \triangleq P_r\lbrace S_{t+1}=s',R_{t+1} = r \mid S_{t} =s,A_{t}=a \rbrace \end{cases} {p(s′,r∣s,a)?Pr?{St+1?=s′,Rt+1?=r∣St?=s,At?=a}?

P o l i c y = { a ? π ( s ) , 确定性策略 π ( a ∣ s ) ? P r { A t = a ∣ S t = s } , 随机性策略 Policy = \begin{cases} a \triangleq \pi(s), & \text{确定性策略} \\ \pi(a\mid s) \triangleq P_r \lbrace A_t=a \mid S_t = s \rbrace, & \text{随机性策略} \end{cases} Policy={a?π(s),π(a∣s)?Pr?{At?=a∣St?=s},?确定性策略随机性策略?

$$\text{Value?Function}=\{\begin{array}{llc}{V}_{\pi }(s)& ?{\mathbb{E}}_{\pi }[G_t\mid S_t=t],& \text{状态价值函数}\\ q_{\pi }(s,a)& ?{\mathbb{E}}_{\pi }[G_t\mid S_t=s,A_t=a],& \text{状态动作价值函数}\end{array}$$

关系：

$$V_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)?q_{\pi }(s,a)\le q_{\pi }(s,a)$$

$$q_{\pi }(s,a)=\sum _{r,s^{\prime }}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

贝尔曼期望方程：

$$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

$$q_{\pi }(s,a)=\sum _{s^{\prime },r}(s^{\prime },r\mid s,a)[r+\gamma \sum _{a^{\prime }}\pi (a^{\prime }\mid s^{\prime })q_{\pi }(s^{\prime },a^{\prime })]$$

贝尔曼最优方程

贝尔曼最优方程

最优化价值函数：
$$?\begin{array}{l}{V}_{?}(s)?\underset{\pi }{\max }{V}_{\pi }(s)\\ q_{?}(s,a)?\underset{\pi }{\max }{q}_{\pi }(s,a)\end{array}$$
记
$${\pi }_{?}=\arg \underset{\pi }{\max }{V}_{\pi }(s)=\arg \underset{\pi }{\max }{q}_{\pi ?}(s,a)$$

$$V_{?}(s)=\underset{\pi }{\max }{V}_{\pi }(s)=V_{\pi ?}(s)$$

$$q_{?}(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a)=q_{\pi ?}(s,a)$$

关系：
$$V_{?}(s)=\underset{a}{\max }{q}_{?}(s,a)$$

$$q_{?}(s,a)=\sum _{s^{\prime },r}(s^{\prime },r\mid s,a)[r+\gamma V_{?}(s^{\prime })]$$

$$v_{?}(s)=\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

$$q_{?}(s,a)=\sum _{s^{\prime },r}(s^{\prime },r\mid s,a)[r+\gamma \underset{a^{\prime }}{\max }{q}_{?}(s^{\prime },a^{\prime })]$$