马尔可夫决策过程

一个Agent包含3部分：

  1. 策略：action，是agent的behavior。目标
  2. 价值函数：评估。对未来做出估计，找到更好的策略
  3. 模型：agent对env的表示。根据模型做出计划。包含两部分：
    1. 转移概率
    2. reward函数

根据有无价值函数可以将方法分为：策略梯度方法，基于价值函数的方法，actor-critic

根据有无模型可以将方法分为：有模型和无模型

预测：评估策略的价值

控制：寻找最优策略

马尔可夫决策过程（MDP）的介绍

MDP假设环境状态完全可观测。但是部分可观测问题可以转换成为MDP问题来解决。

马尔可夫过程

马尔可夫是一个无记忆的随机序列。它的状态满足马尔可夫性质。马尔可夫过程可以表示为<S,P><S, P>. S为状态集合，P为转移概率。

马尔可夫奖励过程

马尔可夫奖励过程是带有reward的马尔可夫过程。可以表示为<S,P,R,γ><S, P, R, \gamma>:

  • S 有限状态集合
  • P 转移概率
  • RS=E[Rt+1∣St=s]R_S = E[R_{t + 1}|S_t = s]
  • γ\gamma 折扣因子

回报：return GtG_t 表示从时间t开始的的带有折扣的回报总和

Gt=Rt+1+γRt+2+γ2Rt+3+..=∑k=0∞γkRt+k+1G_t = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t +3} + .. = \sum\limits_{k = 0}^{\infty}\gamma^k R_{t + k + 1}

RtR_t 叫做实时回报。这里的回报只是计算了一条sample上的回报，因此没有E。

加入折扣因子的原因

  1. 防止陷入无限的循环当中
  2. 模型对于未来的预测有不确定性，因此用折扣因子表现这种不确定，而不是完全的相信这个模型
  3. 在比如金融的领域中，越早得到的钱有越高的价值
  4. 人和动物都对实时回报表现出更高的偏好，认知模式
  5. 如果状态没有环的话，也就是最终都可以终止，可以让γ=1\gamma = 1

价值函数

描述了如果从状态s开始，则期望的回报是多少：

v(s)=E[Gt∣St=s]v(s) = E[G_t|S_t = s]

计算的方式可以是S1=sS_1 = s, 采样多条，求平均从而获得期望的近似值。

贝尔曼方程

V(s)=E[Gt∣St=s]=E[Rt+1+γRt+2+γ2Rt+3...∣St=s]=E[Rt+1+γ(Rt+2+γRt+3+..)∣St=s]=E[Rt+1+γGt+1∣St=s]=E[Rt+1+γVt+1(St+1)∣St=s]\begin{equation} \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 (R_{t + 2} + \gamma R_{t + 3} + ..)|S_t = s]\\ &= E[R_{t + 1} + \gamma G_{t + 1}|S_t = s]\\ &= E[R_{t + 1} + \gamma V_{t + 1}(S_{t + 1})|S_t = s] \end{aligned} \end{equation}

将状态价值函数分解成及时回报和后继回报的组合形式。

进一步可以得到：

v(s)=Rt+1+γ∑s′∈SPss′v(s′)v(s) = R_{t + 1} + \gamma \sum\limits_{s' \in S}P_{ss'}v(s')

贝尔曼方程的矩阵形式

v=R+γPvv = R + \gamma P v

v这里是向量，表示每一个状态的状态价值。P是转移矩阵。R是每个转移对应的reward，也是矩阵。

理论上：v在这里可以直接求解，但是由于矩阵求逆的复杂度是O(N3)O(N^3)，因此不适合状态很多的情况。

v=(I−γP)−1Rv = (I - \gamma P)^{-1}R

马尔可夫决策过程

马尔可夫决策过程在马尔可夫奖励过程的基础上加入Action空间。也就是马尔可夫决策过程可以表示为<S,A,P,R,γ><S, A, P, R, \gamma>:

  • A 是行为空间

策略： 给定当前状态s，对于action的分布。

π(a∣s)=P[At=a∣St=s]\pi(a|s) = P[A_t = a|S_t = s]

目前假设策略都是稳定策略，也就是策略的选择和时间无关。

马尔可夫决策过程可以退化成马尔可夫奖励过程或者马尔可夫过程。

比如

Pss′π=∑a∈Aπ(a∣s)pss′aRsπ=∑a∈Aπ(a∣s)Rsa\begin{equation} \begin{aligned} P^{\pi}_{ss'} &= \sum\limits_{a \in A} \pi(a|s)p_{ss'}^a\\ R^{\pi}_{s} &= \sum\limits_{a \in A} \pi(a|s)R_s^a \end{aligned} \end{equation}

就退化成马尔可夫奖励过程<S,Pπ,Rπ,γ><S, P^{\pi}, R^{\pi}, \gamma>

由于马尔可夫决策过程中有了策略，而状态的价值和策略有关。因此状态价值函数更新为vπ(s)=Eπ[Gt∣St=s]v_{\pi}(s) = E_{\pi}[G_t|S_t = s]

又提出了行为价值函数qπ(s,a)=Eπ[Gt∣St=s,At=a]q_{\pi}(s, a) = E_{\pi}[G_t|S_t=s, A_t = a]

更新贝尔曼公式：

vπ(s)=E[Rt+1+γvπ(St+1)∣St=s]qπ(s,a)=E[Rt+1+γqπ(St+1,At+1)∣St=s,At=a]\begin{equation} \begin{aligned} v_{\pi}(s) &= E[R_{t + 1} + \gamma v_{\pi}(S_{t + 1})|S_t = s]\\ q_{\pi}(s, a) &= E[R_{t + 1} + \gamma q_{\pi}(S_{t + 1}, A_{t + 1})|S_t = s, A_t = a] \end{aligned} \end{equation}

q与v的关联：

由q获得v：

vπ(s)=∑a∈Aπ(a∣s)qπ(s,a)v_{\pi}(s) = \sum\limits_{a \in A}\pi(a|s)q_{\pi}(s, a)

由v获得q：利用bellman公式整理

qπ(s,a)=Rt+1+γ∑s′∈S∑a′∈Apss′aπ(a′∣s)qπ(a′,s′)=Rt+1+γ∑s′∈Spss′avπ(s′)\begin{equation} \begin{aligned} q_{\pi}(s, a) &= R_{t + 1} + \gamma \sum\limits_{s' \in S}\sum\limits_{a' \in A} p_{ss'}^{a}\pi(a'|s)q_{\pi}(a', s')\\ &= R_{t + 1} + \gamma \sum\limits_{s' \in S} p_{ss'}^a v_{\pi}(s') \end{aligned} \end{equation}

v告诉我们s这个状态有多好。

q告诉我们在s这个状态下的action有多好。

通过这两个公式，我们同样可以将v和下一个时刻的v联系起来，也可以将q和下一个时刻的q联系起来。

贝尔曼公式实际上在告诉我们，可以通过线性的方式得到v的结果，只是由于逆矩阵的运算慢，才需要其他的方式来计算，贝尔曼公式本身已经提供了一种计算方式。

最优价值函数

vπ∗(s)=max⁡πvπ(s)qπ∗(s,a)=max⁡πqπ(s,a)\begin{equation} \begin{aligned} v_{\pi}^*(s) &= \max \limits_{\pi}v_{\pi}(s)\\ q_{\pi}^*(s, a) &= \max \limits_{\pi}q_{\pi}(s, a) \end{aligned} \end{equation}

简单来说：

  • v的最优函数表示在当前状态下，通过选取不同的策略可能得到的最大价值是多少
  • q的最优函数表示在当前状态下，采取了action a之后，通过选取不同的策略可能得到的最大价值是多少。

而q的最优函数则已经给出了策略，因为在每一个状态下，我们能通过q*选择可以获得最大价值的action。

最优策略

最终目标是找到最优策略，那么首先定义策略的比较：

π≥π′ if vπ(s)≥vπ′(s),∀s\pi \ge \pi' \ if \ v_{\pi}(s) \ge v_{\pi'}(s), \forall s

最优策略可以通过q∗q^*来获得：

π∗(a∣s)={1if a=arg⁡max⁡a∈Aq∗(s,a)0otherwise\begin{equation} \begin{aligned} \pi^*(a|s) = \left\{ \begin{array}{lr} 1 & if\ a = \arg\max\limits_{a \in A} q^*(s, a)\\ 0 & otherwise \end{array} \right. \end{aligned} \end{equation}

贝尔曼最优化等式

当采取当前的最优策略时候，由于π\pi对于最大的q对应的action取1，因此：

v(s)=max⁡a∈Aq(s,a)v(s) = \max\limits_{a \in A} q(s, a)

而q根据v进行计算，也就是：

qπ(s,a)=Rt+1+γ∑s′∈Spss′avπ(s′)q_{\pi}(s, a) = R_{t + 1} + \gamma \sum\limits_{s' \in S} p_{ss'}^a v_{\pi}(s')

因为我们只会去采取action来保证获得最多的回报，而状态的价值函数不是我们能决定的。因此只找最大的action使得q函数值取最大。

可以证明满足贝尔曼最优化等式的策略是最优策略，因此寻找最优策略的过程，转化为求解贝尔曼等式的过程。

需要注意的是，由于公式中有最大化的操作，因此这个过程不是一个线性过程，不能直接求解，而是需要通过迭代更新求解。

求解贝尔曼最优化等式，从而找到最优策略的方式有很多种：（本身可以直接采用矩阵求逆的方法得到）

  • 值迭代
  • 策略迭代
  • Q-learning
  • Sarsa