马尔科夫性 – 马尔可夫进程 – 马尔可夫奖赏进程 – 马尔可夫决议计划进程

概述

马尔可夫决议计划进程（Markov Decision Processes, MDPs）是对强化学习问题的数学描述。

  • 要求环境是全观测的。y + ] G O C t U 4

马尔可夫性

“e p y k 只要知道现在，将来和过去是条件独立的，能够抛去过去一切的信息。”

界说：假如在t时刻的状况S_t满意下式，则这个3 M q & O a ^ J状况被称为马尔科夫状况，即该状况满意马尔科夫性

P[S_{t+1}|S_{t}] = P[S_{t+1}|S_1, ..., S_t]

注：

  • 状况} ` IS_t包含了一切历史相关信息，即之前的信息都能够} 7 o m在该状况上体现出来f O 8 w : – n（S_t能够替代一切之前的状况）
  • 所以要求环境是全观测$ k @ ]的，(假如是部分观测的话，状况信息有缺失)。
  • 是否满意马4 m : 0 ( m e尔可夫性与状况的界说休戚相关

比如：

  • 下棋
  • 俄罗斯方块

有了马尔可夫状况之后：

  • 能够界说状况搬运矩阵
  • 疏忽时刻的影响，只关心当时时刻

注： 状况是否满意马尔可夫性，与$ w G 1 ! M & . 9状况的界说休戚相关。

状况搬运矩阵

状况搬运概 # ] { @ 9 q率

状况搬运概率指从一个马尔可夫状况 s 跳转到后继状况 (successor state) s′ 的概率。是关于当时状况的条件概} Y A 8 2 h O率散布。

mathcal{P} _ {ss^{'}} = {P} [S_{t+1} = s^{'} | S_t = s]

状况搬运矩阵

若状况是离散的（有限个）：

  • 一切# $ ( u | ) M V的状况组成行R 3 0 s j
  • 一切后继状况组成列，

得到状况搬运矩阵

mathcal{P} = begin{bmatrix} mathcal{P} _ {11} & ... & mathcal{P} _ {1n} \ ... & ... & ... \ mathcal{P} _ {n1} & ... & mathcal{P} _ {nn} \ end{bmatrix}
  • n为状况个数
  • 每行元素相加为1

状况搬运函数

若**状况数量过多，或许无穷大（接连状况）**的，适合用本节最上式的函数方t : 8 D y式表明。

mathcal{P} _ {ss^{'}} = {P} [S_{t+1} = s^{'} | S_t = s]
  • 此刻，int_{s'}mathcal{P}(s'|s)=1

马尔可夫进k @ N T A 5 d程

界说

一个马尔可夫进程A ; 3 m d v e & (Markov process, MP) 是一个无记忆7 % y { b n j H M的随机进程，即一些马尔可夫状况的r S N Q v序列。

马尔可夫进程可由一个二元组来界说 < S,mathcal{P} >

  • S：代表状况调集
  • mathcal{P}：代表状况搬运矩阵

一般5 # v } ]假6 k P定mathcal{P}是存在且稳定的
当mathcal{P}不稳守/ H e ;时，采用在线学习、快速学习等办法

马尔可夫进程的比如

强化学习总结 02-马尔可夫决策过程
  • 马尔可夫进程中的停止状况有2种：
    • 时刻停止
    • 状况停止

片段（Episode）

界说： 强化学习中，从初始状况 S_1 到停止状况 S_T 的序列进程。

S_1, S_2, ..., S_T

马尔可夫奖赏进程

界说

在马尔可夫进程的基础上，在搬运联系中赋予不同的奖赏值，即得到马尔可夫奖赏进程。

马尔可夫奖赏 (Markov Reward ProK 4 & s Hcess, MRP) 进程由一个四元组组成 ⟨S, mathcal{P}, mathcal{R}, ⟩

  • S：状况调集
  • mathcal{P}：状况搬运} c t矩阵
  • mathcal{R}：奖赏函数， mathcal{R}(s) 描述o c Q + ,了在状况 s 的奖赏，mathcal{R}(s) = E [mathcal{R}_{t+1}|S_t = s]
  • ：衰减因子

回报值

  • 奖赏值1 L 5 i n l：对一个状况的点评
  • 回报值：对一个片段的点评

回报值（return G_t）是从时刻t处开端的累积衰减奖赏

G_t = R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + ...

MRPsh 4 o p中的值函数

为什么要值函数？
回报值是一个片段的结果，存在很大的样本偏差
回报值的角标是 t，值函数关注的是状况 s

一个 MRP 的值函数如下界说

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

这儿的值函数针对的是状况 s，所以称为状况值函数，又称 V 函数

MRPs中的贝尔曼方程（重点）

begin{aligned}v(s)&={E}[G_t|S_t=s] \ &={E}[ R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + ... | S_t=s] \ &={E}[ R_{t+1} + gamma G_{t+1} | S_t=s ] \ &={E}[ R_{t+1} + gamma v(S_{t+1}) | S_t=s ]end{aligned}

当时状况的值函数包含两部分：

  • 第一项：瞬时奖赏 R_{t+1}
  • 第二项：后继状况的值函数乘衰减系数 gamma v(S_{t+1})

由于后继状况可能有多个，因而假如已知搬运矩阵 P，那么

begin{aligned} v(s) &= {E} [R_{t+1} + v(S_{t+1}) | S_t = s] \ &= {E} [R_{t+1} | S_t = s] + {E}[v(S_{t+1})|S_t = s] \ &= mathcal{R}(s) + ∑mathcal{P}_{ss^′}v(s^′)end{aligned}

矩阵-向量方式为：

v = mathcal{R} + gamma mathcal{P} v
强化学习总结 02-马尔可夫决策过程

本质上是一个线性方程，能够直接解：

强化学习总结 02-马尔可夫决策过程

直接求解只适用于小型MRPs：

  • 计算复杂度O(n^3)
  • 要求已知 mathcal{P}

马尔可夫决议计划进程

MP 和 MRP 中，我们都是作为调查者，去调查其中的状况搬运现象，去计算回报值| Y [ [ 1 }。关于一个 RL 问题，我们更希望去改变状况搬运的N ( _ d d V V流程，去最大化回报值。因而，在 MRP 中引入决议计划，得到马尔可夫决议计划进程（Markov Decision Processes, MDPs）

界说

一个马尔可夫决议计划进程 (MDPs) 由一个五元组构成 ⟨S, mathcal{A}, mathcal{P}, mathcal{R}, ⟩

  • mathcal{A} ： 动作的调集
  • mathcal{P} ： 状况搬运矩阵
mathcal{P}_{ss^{'}}^{a} = {P}[ S_{t+1}=s' | S_t=s, A_{t}=a]
  • mathcal{R}(s,a)：奖赏函数， 表明在状况s做动作a的奖赏。mathcal{R}(s, a) = E [mathcal{R}_{t+1}|S_t = s, A_{t}=a]

战a z X略

在 MDP U s 中，一个战略 (Policy) 是在给定状况下的动作的概率散布

pi(a | s) = {P}[ A_t = a | S_t = s ]
强化学习总结 02-马尔可夫决策过程
  • 战略是时刻稳定的，只与s有关，与时刻t无关
  • 是RL问题的终6 v i d s 3 2 $极目标
  • 假如散布是 one-hot 的，那2 [ l T M J | T /么为确定性战略，否则为随机战略
强化学习总结 02-马尔可夫决策过程

MDPs与MRPs之间的联系

假如MDP问题给定战略pi，则会退化成MRP问题。

MDPs中的值函数

  1. 状况值函数（V函数）

    • 界说：从状况s开端，$ V Q运用战略pi得到的希望回报值
    v_{pi}(s) = {E}_pi[G_t|S_t = s]

  2. 状况动作值函数（Q函数）

    • 界说：MDPs 中的状况动作值函数是从状况 s 开端，执行动作 a， 然后运用战略 得到的希望回报值

      动作a不一定来自于战略 pi，实际上是做完动作 a之后，才遵从战略 pi 进行动作选择

    q_{pi}(s, a) = {E}_pi[ G_t | S_t = s, A_t = a ]

贝尔曼希E C s E 6 , |望方程

和 MRP 相似U K A E w ! @， MDPs 中的值函数也能分解成瞬时奖赏和后继状况的值函数两部分

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