(强化学习)- 马尔可夫过程

马尔科夫性

马尔可夫性指系统的下一个状态 $s_{t+1}$ 仅与当前状态 $s_t$ 有关,而与之前的状态无关。定义为 $P[s_{t+1}|s_t] = P[s_{t+1}|s_1,...,s_t]$。可以看出当前状态 $s_t$ 蕴含了历史信息。

马尔科夫过程

定义:马尔科夫过程是一个二元组 $(S,P)$ ,且满足:$S$ 是有限的状态集合,P 是条件转移概率。状态转移的概率矩阵为:

$$ P=
\left[
\begin{matrix}
P_{11} & \cdots & P_{1n} \\
\vdots & \vdots & \vdots \\
P_{n1} & \cdots & P_{nn} \\
\end{matrix}
\right]
$$

马尔可夫回报过程

马尔可夫回报过程(MRP)是带有回报和衰减系数$\gamma$的马尔可夫过程。

累积回报

给定的策略 $\pi$

$$G_t=R_{t+1}+\gamma R_{t+2}+\cdots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$$

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

值函数

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

$$v(s)=\mathbb{E}[G_t|S_t=s]$$

这里约定用状态——价值函数描述针对状态的价值;用状态——行为值函数来描述某一状态下执行某一行为的价值。

价值函数的推导

  • 贝尔曼方程 - MRP

$$
\begin{aligned}
& v(s)=\mathbb{E}[G_t|S_t=s]\\
& =\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots|S_t=s]\\
& =\mathbb{E}[R_{t+1}+\gamma(R_{t+2}+R_{t+3}+\cdots)|S_t=s]\\
& =\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\
& =\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})|S_t=s]
\end{aligned}
$$
最终得到针对 MRP 的贝尔曼方程:$$
\begin{equation}
v=\mathbb{E}_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]\\
\label{bellman_mrp}
\end{equation}
$$

导出最后一行时,将$G_{t+1}$变成了$v(S_{t+1})$是因为求回报的期望的期望(数值)。

如果用$s^{'}$表示s的下一个状态,也贝尔曼方程也可以写成:$$v(s)=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})|S_t=s]$$

贝尔曼方程的矩阵形式

$$
v=R+\gamma Rv
$$

贝尔曼方程是一个线性方程组,可以求解:

$$
\begin{aligned}
&v=R+\gamma Pv \\
&(I-\gamma P)=R \\
&v=(I-\gamma P)^{-1}R
\end{aligned}
$$

实际上,计算复杂度是$O(n^{3})$, n 是状态数量。因此直接求解仅适用于小规模的MRPs。大规模MRP的求解通常使用迭代法。常用的迭代方法有:

  • 动态规划Dynamic Programming
  • 蒙特卡洛评估Monte-Carlo evaluation
  • 时序差分学习Temporal-Difference

马尔科夫决策过程(Markov Decision Process)

相比 MRP,MDP 引入了行为集合 A

决策过程可以由元组 $(S,A,P,R,\gamma)$ 表示。

  • S 是有限的状态集
  • A 是有限的动作集
  • P 是状态转移概率矩阵。$P_{ss^{'}}^a = P[S_{t+1} = s^{'}|S_t = s, A_t = a]$
  • R 是回报函数,$R_s^a=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]$
  • $\gamma$ 是折扣因子,用来累计回报。范围是 [0,1]

策略

策略就是指状态到动作的映射,常用 $\pi$ 表示,它指给定状态 s,动作集上的一个分布:$\pi(a|s)=p[A_t=a|S_t=s]$。策略 $\pi$ 指定一个动作的概率。如果给出的策略 $\pi$ 是确定性的,那么策略 $\pi$ 在每个状态在每个状态指定的一个确定的动作。强化学习的目标就是找到最优的策略,最有就是得到的总回报最大。

当给定一个MDP: $M=(S, A, P, R, \gamma)$ 和一个策略$\pi$,那么状态序列$ S_{1},S_{2},\cdots$ 是一个马尔科夫过程 $(S,P^{\pi})$ ;同样,状态和奖励序列$ S_{1}, R_{2}, S_{2}, R_{3}, S_{3}, \cdots$ 是一个马尔科夫奖励过程 $(S, P^{\pi}, R^{\pi}, \gamma)$ ,并且在这个奖励过程中满足下面两个方程:

$$
P_{ss_{'}}^\pi=\sum_{a\in A}\pi(a|s)P_{ss_{'}^a}
$$

$$
R^\pi_s=\sum_{a\in A}\pi(a|s)R_s^a
$$

即当前状态s下执行某一指定策略得到的即时奖励是该策略下所有可能行为得到的奖励与该行为发生的概率的乘积的和。

基于策略$\pi$的价值函数

状态-价值函数

当采用策略 $\pi$,累积回报服从一个分布,累积回报在状态 s 的期望定义为状态-值函数:

$$v_{\pi}(s)=\mathbb{E}_\pi[\sum_{k=0}^\infty \gamma^k R_{t+k+1}|S_t=s]$$

学生的马尔可夫转移图:

黑色的实心圆圈表示的是两个状态之间的动作。

如图是状态值函数:

空心圆圈中的就是状态-值函数。每个状态转移的状态概率已经在线上标出。$v_\pi(s_1)=-2.3, v_\pi(s_2)=-1.3 \cdots, v_\pi(s_5)=0$

状态-行为值函数

$$q_\pi(s,a)=\mathbb{E}[\sum_{k=0}^\infty\gamma^kR_{t+k+1}|S_t=s,A_t=a]$$

贝尔曼期望方程

  • 与$\eqref{bellman_mrp}$不同的是,MDP 的状态-价值函数包含了$\pi$

$$
\begin{equation}
v_\pi=\mathbb{E}_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]
\end{equation}
$$

  • 状态-行为值函数

$$q_\pi(s,a)=\mathbb{E}_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})|S_t=s,A_t=a]$$

$v_\pi$ 与 $q_\pi(s,a)$的关系

空性圆圈表示状态,实心圆圈表示状态-行为对。状态-值函数与状态-行为值函数的关系:

$$
\begin{equation}
v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a)\\
\label{state_value_vpi}
\end{equation}
$$

同样 $q_\pi(s,a)$ 也可以连接其他的状态-值函数:

$$
\begin{equation}
q_\pi(s,a)=R_s^a+\gamma\sum_{s^{'}}P_{ss^{'}}^av_\pi(s^{'})\\
\label{state_value_q}
\end{equation}
$$

综合这$\eqref{state_value_vpi}$和$\eqref{state_value_q}$可以得到:

$$
\begin{equation}
v_\pi(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^av_\pi(s^{'}))\\
\label{state_value_final}
\end{equation}
$$

同理也可得:

$$
\begin{equation}
q_\pi(s,a)=R_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^a\sum_{a^{'}\in A}\pi(a^{'}|s^{'})q_\pi(s^{'},a^{'})\\
\label{state_action_final}
\end{equation}
$$

验证$\eqref{state_value_final}$得到的$v_\pi(s4)=7.39$ 基本上与已知的 7.4 相差无几。注意实心圆圈是状态-行为值函数,采取是$\pi(a|s)=0.5, \gamma=1$。

最优值函数

计算状态-值函数的目的是为了构建学习算法从数据中的得到最优策略。每个策略对应一个状态-值函数,最优策略对应的是最优状态-值函数。

  • 最优状态-值函数$v^*(s)=\max_\pi v_\pi(s)$
  • 最优状态-行为函数$q^*(s,a)=\max_\pi q_\pi(s,a)$

学生的 MDP 的最优状态-值函数:

首先看到状态$s_4$,根据$\eqref{optimal_state_value_bellman}$可以选择的动作以及得到的回报:

采取的动作 转移的状态 回报 状态-值函数
喝酒 实心圆圈 +1 $1+1\times(0.2\times6+0.4\times8+0.4\times10)=9.4$
学习 $s_5$ +10 $10+1\times0=10$

所以$v^*(s_4)=10$

同理,计算$s_3$。当选择动作睡觉(Sleep)的时候,$v(s_3)=0+1\times0=0$;选择动作学习(Study)的时候,$v(s_3)=-2+1\times(1\times10)=8$,之所以$P^a_{ss^{'}}=1$是因为我们已经明确转移的状态。

学生的 MDP 的最优状态-行为值函数

我们计算的重点是在弧上,根据$\eqref{optimal_state_action_bellman}$。根据$v_\pi$和$q(s,a)$的关系$\eqref{state_value_q}$:

动作 $q(s,a)$
从$s_4$到$s_5$的名为 study 的弧 $q^*(s_4,\textrm{study})=10+1\times(0.5\times0)=10$
以$s_4$为弧尾名为 pub 的弧 $q^*(s_4,\textrm{pub})=1+1\times(0.2\times6+0.4\times8+0.4\times10)=9.4$

这个与David Silver的图片中的8.4不一致

最优策略

当对于任何状态 s,遵循策略$\pi$的价值不小于遵循策略$\pi^{'}$的价值,则策略$\pi$优于策略$\pi^{'}$:

$$\pi\ge\pi^{'}\ \textrm{if}\ v_\pi(s)\ge v_{\pi^{'}}(s),\forall s$$

定理 对于任何MDP,下面几点成立:

  1. 存在一个最优策略,比任何其他策略更好或至少相等
  2. 所有的最优策略有相同的最优状态-值函数;
  3. 所有的最优策略具有相同的状态-行为价值函数。

寻找最优策略

$$
\pi_*(a|s) =
\left\{
\begin{array}{ll}
\displaystyle 1 & \textrm{if}\ a=\arg\max_{a\in A}q_*(s,a)\\
\displaystyle 0 & \textrm{otherwise}
\end{array}
\right.
$$

对于任何一个 MDP 问题,总存在一个确定性的最优策略;同时也知道最优状态——行为函数,则表明找到了最优策略。已知最优的状态-行为值函数,最优策略可以直接通过最大化$q_*(s,a)$确定。

贝尔曼最优方程

由公式$\eqref{state_value_final}$和$\eqref{state_action_final}$以及他们的推导过程分别得到最优状态-值函数和最优状态-行为值函数的贝尔曼方程:

$$
\begin{equation}
v^*(s)=\max_aR_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^av^*(s^{'})\\
\label{optimal_state_value_bellman}
\end{equation}
$$
$$
\begin{equation}
q^*(s,a)=R_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^a\max_{a^{'}}q^*(s^{'},a^{'})\\
\label{optimal_state_action_bellman}
\end{equation}
$$

贝尔曼最优方程在学生 MDP中的例子:

最优值函数明确了MDP的最优可能表现,当我们知道了最优值函数,也就知道了每个状态的最优值,这时便认为这个MDP获得了解决。

求解贝尔曼最优方程

  • 贝尔曼方程是非线性的(比如存在 max)
  • 通常来说,没有固定的解(No closed solution)
  • 有很多迭代方法可以解:
  1. Value Iteration
  2. Policy Iteration
  3. Q-learning
  4. Sarsa

参考