强化学习笔记（2）-- 马尔科夫决策过程

作者: ColleenKuang | 来源:发表于2019-02-14 18:00 被阅读56次

1.马尔科夫过程

Markov decision processes formally describe an environment for reinforcement learning, where the environment is fully ovservable.

大部分的RL问题都能用MDPs来描述

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

1.1 马尔科夫性质（Markov Property）

"The future is independent of the past given the present".

下个状态只与当前状态有关，跟更前面的状态无关。
定义：

如果在t时刻的状态 $S_t$ 满足如下灯饰，那么这个状态被称为马尔科夫状态，或者说该状态满足马尔科夫性
A state $S_t$ is Markov if and only if
$\mathbb{P}[S_{t+1} | S_t] = \mathbb{P}[S_{t+1} | S_1,...,S_t]$

状态 $S_t$ 包含了所有历史相关信息，所以无需再去了解之前的 $S_1,...,S_{t-1}$
数学上可以认为，当前状态是将来的充分统计量
所以，这里要求环境全观测
举例：
下棋时，只用关心当前局面（直接解残局，不需要）
打俄罗斯方块时，只用关心当前屏幕

有了马尔科夫状态之后，我们可以

定义状态转移矩阵
忽略时间的影响
PS：马尔科夫性和状态的定义息息相关

1.2状态转移矩阵(State Transition Matrix)

状态转移概率只从一个马尔科夫状态s跳转到后继状态s'的概率
For a Markov state s and successor states', the state transition probability is defined by
$\mathcal{P}_{ss'} = \mathbb{P}[S_{t+1} = s' | S_t = s]$

所有的状态组成行，所有的后继状态(successor)组成列，我们就可以得到状态转移矩阵
$\left[ \begin{matrix} P_{11} & \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\ P_{n1} & \cdots & P_{nn} \\ \end{matrix} \right]$

n表示状态的个数
每行元素相加等于1

当然如果状态太多，或者是无穷大（连续状态）时，更适合用状态转移函数，
$P(s'|s) = \mathbb{P}[S_{t+1} = s' | S_t = s]$

此时， $\int_{s'}P(s'|s) = 1$ 或 $\sum_{s'}P(s'|s) = 1$

重要的事情说三遍：
转移矩阵在MDP中被认为是环境的一部分！！！
转移矩阵在MDP中被认为是环境的一部分！！！
转移矩阵在MDP中被认为是环境的一部分！！！

1.3 马尔科夫过程

A Markov Process(or Markov Chain) is a memoryless random process, i.e. a sequence of random state $S_1$ , $S_2$ ,... with the Markov property
马尔科夫过程可以由一个二元组来定义 $<S, P>$
$S$ 代表了状态的集合
$P$ 描述了状态转移矩阵

$P_{ss'} = \mathbb{P}[S_{t+1} = s' | S_t = s]$

我们有时候并一定知道 $P$ 的具体值，但是通常我们假设 $P$ 存在且稳定(即，从 $s$ 转移到 $s'$ 的概率任何时候都是一样的)

PS：当 $P$ 不稳定时，不稳定环境，在线学习，快速学习

Student Markov Chain Transition Matrix

椭圆：普通状态
有向线：从这个状态跳转到另一个状态的概率
方块：表示终止状态

1.4 片段(episode)

定义

episode = one a sequence of states, actions and rewards, which ends with terminal state
强化学习中，从初始状态 $S_1$ 到最终状态的序列过程，被称为一个片段(episode)
$S_1,S_2,..,S_T$

如果一个任务总以终止状态结束，那么这个任务被称为片段任务(episodic task).
如果一个任务没有终止状态，会被无线执行下去，则被称为连续性任务(continuing task).
episodes example

2.马尔科夫奖励过程(Markov reward process)

A Markov reward process is a Markov chain with values.
马尔可夫过程主要描述的是状态之间的转移关系，在这个转移关系上赋予不同的奖励值即得到了马尔可夫奖励过程。

马尔科夫奖励过程有一个四元组组成 $<\mathcal{S},\mathcal{P},\mathcal{R},\gamma>$
$\mathcal{S}$ 代表了状态的集合
$\mathcal{P}$ 描述了状态转移矩阵
$\mathcal{R}$ 表示奖励函数， $R(s)$ 描述了在状态 $s$ 的奖励.
$\mathcal{R}(s) = \mathbb{E}[R_{t+1} | S_t = s]$
$\gamma \in [0,1]，表示衰减因子$

敲黑板！！
注意区别 $\mathcal{R}\text{和}R\text{的区别}$ ：
$R$ :在t+1时刻，所获得的随机变量的值
$\mathcal{R}$ :一个函数

Student MRP

2.1 回报值

奖励值：对每一个状态的评价
回报值：对每一个片段的评价

定义
回报值(return $G_t$ )是从时间 $t$ 处开始的累计衰减奖励
对于片段任务：
$G_t = R_{t+1} + \gamma*R_{t+2} + ... + \gamma^{T-t-1}*R_{T} = \sum^{T-t-1}_{k=0} \gamma^k*R_{t+k+1}$
对于连续性任务:
$G_t = R_{t+1} + \gamma*R_{t+2} + ... = \sum^{\infty}_{k=0} \gamma^k*R_{t+k+1}$

2.2 再聊片段

可以这么理解，终止状态等价于自身转移概率为1，奖励为0的一个状态。
因此，我们可以能够将片段性任务和连续性任务进行统一表达

2.4.1MRP中的贝尔曼方程（Bellman Equation）

值函数的表达式可以分解成两部分：

瞬时奖励(immediate reward) $R_{t+1}$
后继状态 $S_{t+1}$ 的值函数乘上一个衰减系数
下面是推导过程：
$\begin{equation} \begin{aligned} v(s) &= \mathbb{E}[G_t|S_t = s]\\ &= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... |S_t = s]\\&= \mathbb{E}[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + ... )|S_t = s] \\&=\mathbb{E}[R_{t+1} + \gamma G_{t+1} | S_t = s] \\&\text{求和的期望等价于求期望的和}\\&R_{t+1} \text{的期望仍是} R_{t+1} \\&G_{t+1}\text{的期望就是}v(S_{t+1})\\&= \mathbb{E}[R_{t+1} + \gamma v(S_{t+1})|S_t = s] \end{aligned} \end{equation}$
体现了 $v(s)$ 与 $v(S_{t+1})$ 之间的迭代关系

2.4.2 解贝尔曼方程

矩阵-向量形式表达贝尔曼方程
$v = \mathcal{R} + \gamma \mathcal{P}v$
假设状态集合为 $\mathcal{S} = {s_1,s_2,...,s_n}$ ，那么
$\left[\begin{matrix} v(s_1) \\ \vdots \\ v(s_n)\end{matrix}\right] = \left[\begin{matrix} \mathcal{R}(s_1) \\ \vdots \\ \mathcal{R}(s_n)\end{matrix}\right] + \gamma\left[ \begin{matrix} P_{11} & \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\ P_{n1} & \cdots & P_{nn} \\ \end{matrix} \right] \left[\begin{matrix} v(s_1) \\ \vdots \\ v(s_n)\end{matrix}\right]$

贝尔曼方程本质上是一个线性方程，可以直接解
$\begin{equation} \begin{aligned} v &= \mathcal{R} + \gamma \mathcal{P}v \\ (I - \gamma \mathcal{P})v &= \mathcal{R} \\v &=(I - \gamma \mathcal{P})^{-1} \mathcal{R} \end{aligned} \end{equation}$

Computational complexity is $O(n^3)$ for n states.
State Transition Matrix $\mathcal{P}$ is required.
Direct solution only possible for small MRPs.
There are many iterative methods for large MRPs, e.g:
1. Dynamic programming
2. Monte-Carlo evaluation
3. Temporal-Difference learning

3.马尔科夫决策过程

我们把动作(Action)引入到MRPs中，就得到了马尔可夫决策过程（Markov Decision Processes, MDPs）

一个马尔科夫决策过程(MDPs)由一个五元组构成 $<\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma>$
$\mathcal{S}$ 代表了状态的集合
$\mathcal{A}$ 代表了动作的集合
$\mathcal{P}$ 描述了状态转移矩阵 $\mathcal{P}^a_{ss'} = \mathbb{P}[\mathcal{S}_{t+1} = s' | S_t = s, A_t = a]$
$\mathcal{R}$ 表示奖励函数， $\mathcal{R}(s,a)$ 描述了在状态s做动作a的奖励 $\mathcal{R}(s,a) = \mathbb{E}[\mathcal{R}_{t+1} | \mathcal{S}_t = s, \mathcal{A}_t = a]$
$\gamma \in [0,1]，表示衰减因子$

3.1 策略(Policy)

A policy $\pi$ is a distribution over actions given states. 在MDPs中，一个策略 $\pi$ 是在给定状态下得动作的概率分布
$\pi(a|s) = \mathbb{P}[A_t = a | S_t = s]$

策略是对智能体行为的全部描述(智能体能够控制的是策略)
MDPs中的策略是基于马尔科夫状态的（而不是基于历史）
策略是时间稳定的，只与s有关，与时间t无关
策略的概率分布输出都是独热的(one-hot)，那么成为确定性策略，否则即为随机策略

3.2 MDPs和MRPs之间的关系

对于一个MDP问题 $<\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma>$ ，如果给定了策略 $\pi$ , MDP将会退化成MRP $<\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma>$
此时，
$\mathcal{P}^{\pi} = \sum_{a \in \mathcal{A}} \pi(a|s)\mathcal{P}^a_{ss'}$
$\mathcal{R}^{\pi}_s = \sum_{a \in \mathcal{A}} \pi(a|s)\mathcal{R}^a_{s}$

3.3 值函数

在MDPs问题中，由于动作的引入，值函数分为了两种：

状态值函数（V函数）
状态动作值函数（Q函数）

V函数
MDPs中的状态值函数是从状态s开始，使用策略 $\pi$ 得到的期望回报值
$v_{\pi}(s)=\mathbb{E}_{\pi}[G_t | S_t = s]$

Q函数
MDPs中的状态动作值函数是从状态s开始，执行动作a，然后使用策略 $\pi$ 得到的期望回报值
$q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$

Q函数中，之所以强调“然后”的意思是，在状态s下，智能体的动作a是随机选择的（不一定按策略来），之后的动作才是按策略来做选择。

MDPs中，任何不说明策略 $\pi$ 的情况下，讨论值函数都是在耍流氓！

3.4 贝尔曼方程

和MRP相似，MDPs中的值函数也能分解成瞬时奖励和后继状态的值函数两部分
状态值函数
$v_{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s]$
状态动作值函数
$q_{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]$

其中空心节点代表了state，实心点代表了state-action pair，从根节点

Q转V

这个本质上是全概率

V转Q

贝尔曼期望方程-V函数

贝尔曼期望方程-Q函数
贝尔曼方程矩阵形式
MDPs 下的贝尔曼期望方程和 MRP 的形式相同

最优v函数转最优q函数

最优q函数转最优v函数

同样根据上面的两个图，我们可以推导出：

贝尔曼最优方程——V函数

贝尔曼最优方程——Q函数

贝尔曼最优方程本质上就是利用了 $\pi_{*}$ 的特点，将其期望的算子转化成了max
在贝尔曼期望方程中， $\pi$ 是已知的，而在贝尔曼最有方程， $\pi_{*}$ 是未知的
解贝尔曼期望方程的过程即对应了评价，解贝尔曼最优方程的过程即对应了优化

贝尔曼最优方程是非线性的，一般很难有闭式的解(closed-form solution)，可以使用迭代优化的方法去解：

Value Iteration
Policy Iteration
Q-learning
Sarsa
...

4.MDPs的拓展

4.1 无穷或连续 MDPs

动作空间或状态空间无限可数
动作空间或状态空无限不可数（连续）
时间连续

4.2 部分可观测 MDPs（Partially observable MDPs, POMDPs)

此时观测不等于状态 $O_t \neq S_t$
POMDPs由七元组 $<\mathcal{S}, \mathcal{A}, \mathcal{O}, \mathcal{P}, \mathcal{R}, \mathcal{Z}, \gamma>$
\mathcal{Z} 是观测函数
$\mathcal{Z}^{a}_{s'o} = \mathbb{P} [O_{t+1} = o | S_{t+1} = s', A_{t} = a]$
观测不满足马尔可夫性，因此也不满足贝尔曼方程
状态未知，隐马尔科夫过程
又是对于POMDPs，最优的策略是随机性

4.3 无衰减 MDPs

用于各态经历（平稳随机过程的一种特性）马尔科夫决策过程
存在独立于状态的平均奖上 $p*{\pi}$
求值函数时，需要减去该平均奖赏，否则有可能奖赏爆炸