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

文章目录
  1. 1. 马尔可夫过程
    1. 1.1. 马尔可夫决策过程简介
    2. 1.2. 马尔可夫性质
    3. 1.3. 状态转移矩阵
    4. 1.4. 马尔可夫过程
  2. 2. 马尔可夫奖励过程
    1. 2.1. 回报
    2. 2.2. 值函数
    3. 2.3. MRPs的贝尔曼方程
  3. 3. 马尔可夫决策过程
    1. 3.1. 策略
    2. 3.2. 值函数
    3. 3.3. 贝尔曼期望方程
    4. 3.4. 最优值函数
    5. 3.5. 最优策略
    6. 3.6. 贝尔曼最优方程
    7. 3.7. 贝尔曼最优方程的求解
  4. 4. MDP的扩展
  5. 5. 参考资料

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

本文将介绍用来对强化学习问题进行建模的马尔可夫决策过程(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

参考资料

分享到 评论