强化学习(二):马尔可夫决策过程


在上一篇文章 强化学习(一):强化学习简介 中, 我们介绍了强化学习的一些基本概念.

本文将介绍用来对强化学习问题进行建模的马尔可夫决策过程(Markov Decision Processes, MDPs).

马尔可夫过程

马尔可夫决策过程简介

马尔可夫决策过程(Markov Decision Processes, MDPs)形式上用来描述强化学习中的环境.

其中,环境是完全可观测的(fully observable),即当前状态可以完全表征过程.

几乎所有的强化学习问题都能用MDPs来描述:

  • 最优控制问题可以描述成连续MDPs;
  • 部分观测环境可以转化成MDPs;
  • 赌博机问题是只有一个状态的MDPs.

马尔可夫性质

马尔科夫性质

马尔科夫性质(Markov Property)表明: 未来只与现在有关,而与过去无关.


状态转移矩阵

对于一个马尔可夫状态$S$及其后继状态$S’$,其状态转移概率由下式定义:

状态转移矩阵(State Transition Matrix)$\mathcal{P}$定义了从所有状态$S$转移到所有后继状态$S’$的概率.

其中,$n$为状态个数,且矩阵的每行和为1.


马尔可夫过程

马尔可夫过程(Markov Process)是一个无记忆的随机过程(memoryless random process).

即,随机状态$S_1, S_2, \dots$序列具有马尔可夫性质.

马尔可夫过程(或马尔可夫链)是一个二元组$<\mathcal{S}, \mathcal{P}>$

  • $\mathcal{S}$: (有限)状态集
  • $\mathcal{P}$: 状态转移概率矩阵, $\mathcal { P } _ { s s ^ { \prime } } = \mathbb { P } \left[ S _ { t + 1 } = s ^ { \prime } | S _ { t } = s \right]$

Example: Student Markov Chain

圆圈代表状态, 箭头代表状态之间的转移, 数值代表转移概率.

状态转移矩阵$\mathcal{P}$如下:


马尔可夫奖励过程

马尔可夫奖励过程(Markov Reward Process, MRP)带有奖励的马尔可夫链.

马尔可夫奖励过程是一个四元组<$\mathcal{S}$, $\mathcal{P}$, $\mathcal{R}$, $\mathcal{\gamma}$>

  • $\mathcal{S}$: (有限)状态集
  • $\mathcal{P}$: 状态转移概率矩阵, $\mathcal { P } _ { s s ^ { \prime } } = \mathbb { P } \left[ S _ { t + 1 } = s ^ { \prime } | S _ { t } = s \right]$
  • $\mathcal{R}$: 奖励函数, $\mathcal { R } _ { s } = \mathbb { E } \left[ R _ { t + 1 } | S _ { t } = s \right]$
  • $\gamma$: 折扣因子, $\gamma \in [ 0,1 ]$

Example: Student MRP

回报

回报(Return) $G_t$ 是从时间 $t$ 开始的总折扣奖励.

  • 折扣因子 $\gamma \in [ 0,1 ]$ 表示未来的奖励在当前的价值. 由于未来的奖励充满不确定性, 因此需要乘上折扣因子;
  • $\gamma$ 接近 $0$ 表明更注重当前的奖励(myopic);
  • $\gamma$ 接近 $1$ 表明更具有远见(far-sighted).

值函数

值函数(Value Function) $v(s)$ 表示一个状态 $s$ 的长期价值(long-term value).

一个马尔可夫奖励过程(MRP)的状态值函数 $v(s)$是从状态 $s$ 开始的期望回报.


MRPs的贝尔曼方程

值函数可以被分解为两部分:

  • 立即奖励 $R_{t+1}$
  • 后继状态的折扣价值 $\gamma v(S_{t+1})$

上式表明, $t$ 时刻的状态 $S_t$ 和 $t+1$ 时刻的状态 $S_{t+1}$ 的值函数之间满足递推关系.

该递推式也称为贝尔曼方程(Bellman Equation).

Bellman Equation for MRPs

如果已知概率转移矩阵 $\mathcal{P}$, 则可将公式\eqref{eq:mrp-bellman-equation}变形为:

例子:

Example: Bellman Equation for Student MRP

贝尔曼方程的矩阵形式:

可将公式\eqref{eq:mrp-bellman-equation-2}改写为矩阵形式:

其中, $v$ 为一个列向量, 向量的元素为每个状态的值函数.

观测贝尔曼方程的矩阵形式, 可知其为线性方程, 可直接求解如下.

计算复杂度为: $\mathcal{O}(n^3)$. 因此, 只适合直接求解小规模的MRP问题.

对于大规模的MRP问题, 通常采取以下的迭代方法:

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

马尔可夫决策过程

马尔可夫决策过程(Markov Decision Process, MDP)带有决策的马尔可夫奖励过程.

马尔可夫决策过程是一个五元组<$\mathcal{S}$, $\mathcal{A}$, $\mathcal{P}$, $\mathcal{R}$, $\mathcal{\gamma}$>

  • $\mathcal{S}$: 有限的状态集
  • $\mathcal{A}$: 有限的动作集
  • $\mathcal{P}$: 状态转移概率矩阵, $\mathcal { P } _ { s s ^ { \prime } } ^ {a}= \mathbb { P } \left[ S _ { t + 1 } = s ^ { \prime } | S _ { t } = s, A _ { t } = a \right]$
  • $\mathcal{R}$: 奖励函数, $\mathcal { R } _ { s } ^ {a} = \mathbb { E } \left[ R _ { t + 1 } | S _ { t } = s, A _ { t } = a \right]$
  • $\gamma$: 折扣因子, $\gamma \in [ 0,1 ]$

例子:

Example: Student MDP


策略

策略(Policy) $\pi$ 是给定状态的动作分布.

  • 策略完全决定智能体的行为;
  • MDP策略值依赖于当前状态(无关历史);
  • 策略是固定的(与时间无关). $A _ { t } \sim \pi ( \cdot | S _ { t } ) , \forall t > 0$

给定一个马尔可夫决策过程 $M = <\mathcal{S},\mathcal{A}, \mathcal{P}, \mathcal{R}, \mathcal{\gamma}>$ 和 一个策略 $\pi$, 其可以转化为马尔可夫过程马尔可夫奖励过程.

  • 状态序列 $S_1, S_2, \dots$ 是马尔科夫决策过程 $<\mathcal{S}, \mathcal{P}^{\pi}>$.

  • 状态和奖励序列 $S_1, R_2, S_2, \dots$ 是马尔科夫奖励过程 $<\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma>$.

其中,


值函数

值函数(Value Function)可分为状态值函数(state-value function)动作值函数(action-value function).

MDP的状态值函数 $v_{\pi}(s)$ 是从状态 $s$ 开始, 然后按照策略 $\pi$ 决策所获得的期望回报.

MDP的动作值函数 $q_{\pi}(s, a)$ 是从状态 $s$ 开始, 采取动作 $a$, 然后按照策略 $\pi$ 决策所获得的期望回报.


贝尔曼期望方程

状态值函数可以被分解为两部分, 立即奖励 + 后继状态的折扣价值.

动作值函数也可以类似地分解.


上图中, 空心圆圈代表状态, 实心圆圈代表动作.

在已知策略 $\pi$ 的情况下, 状态值函数 $v_{\pi}(s)$ 可以用动作值函数 $q_{\pi}(s, a)$ 进行表示:


同理, 动作值函数 $q_{\pi}(s, a)$ 也可以用状态值函数 $v_{\pi}(s)$ 进行表示:


状态值函数的贝尔曼期望方程:

将公式\eqref{eq:mdp-action-value-function}代入公式\eqref{eq:mdp-state-value-function}中, 可得状态值函数的贝尔曼期望方程:


动作值函数的贝尔曼期望方程:

将公式\eqref{eq:mdp-state-value-function}代入公式\eqref{eq:mdp-action-value-function}中, 可得动作值函数的贝尔曼期望方程:


例子:

状态值函数的贝尔曼期望方程示例


贝尔曼期望方程的矩阵形式:

可直接求解:


最优值函数

最优状态值函数(optimal state-value function) $v_{*}(s)$ 是所有策略中最大的值函数.

最优动作值函数(optimal action-value function) $q_{*}(s, a)$ 是所有策略中最大的动作值函数.

  • 最优值函数代表了MDP的最好性能.
  • 当得知最优值函数时, MDP可被认为”已解决”.

例子:

Student MDP中的最优状态值函数


例子:

Student MDP中的最优动作值函数

注: 根据公式\eqref{eq:mdp-state-value-function}, Pub动作的最优值应为 $q_{*} = +1 + (0.2 \times 6 + 0.4 \times 8 + 0.4 \times 10) = 9.4$.


最优策略

首先定义策略之间的偏序关系, 使得策略之间可以进行比较:

对于任意的MDP来说:

  • 存在一个最优策略 $\pi_{*}$, 使得 $\pi_{*} \geq \pi, \forall \pi$
  • 所有的最优策略都能取得最优值函数 $v_{\pi_{*}}(s) = v_{*}(s)$
  • 所有的最优策略都能取得最优动作值函数 $q_{\pi_{*}}(s, a) = q_{*}(s, a)$

寻找最优策略

一个最优策略可以通过最大化所有的 $q_{*}(s, a)$ 得到:

  • 对于任意的MDP, 总存在确定的最优策略
  • 如果我们知道 $q_{*}(s, a)$, 则可以立即得到最优策略

例子:

Student MDP的最优策略

图中红色弧线表示每个状态的最优决策.


贝尔曼最优方程

$v_{*}$可以通过贝尔曼最优方程递归得到:

与公式\eqref{eq:mdp-state-value-function}的贝尔曼期望方程进行比较, 此时不再取均值, 而是取最大值.


$q_{*}$与公式\eqref{eq:mdp-action-value-function}类似:


状态值函数的贝尔曼最优方程

将公式\eqref{eq:action-bellman-optimal-equation}代入公式\eqref{eq:state-bellman-optimal-equation}可得 $v_{*}$ 的贝尔曼最优方程:


动作值函数的贝尔曼最优方程

将公式\eqref{eq:state-bellman-optimal-equation}代入公式\eqref{eq:action-bellman-optimal-equation}可得 $q_{*}$ 的贝尔曼最优方程:


例子:

Student MDP贝尔曼最优方程


贝尔曼最优方程的求解

贝尔曼最优方程不是线性的(因为有取$max$操作), 因此没有封闭解(Closed-form solution).

通常采用迭代求解方法:

  • 值迭代(Value Iteration)
  • 策略迭代(Policy Iteration)
  • Q-Learning
  • Sarsa

MDP的扩展

  • 无穷和连续的MDPs
  • 部分可观测的MDPs
  • 不折扣, 平均奖励MDPs

参考资料