马尔可夫决策过程

Posted on

马尔可夫决策过程

1. 马尔可夫决策过程

  • Markov Decision Process:MDP；
  • 常用于建模序列化决策过程；
  • 行为不仅获得即时奖励，还能改变状态，从而影响长期奖励；
  • 学习状态到行为的映射——策略（多臂赌博机学习\(q_*(a)\)，MDP学习\(q_*(s,a)\)或\(v_*(s)\)）；

2. 要素

智能体和环境按照离散的时间步进行交互：

形式化记号：

  • 智能体在时间步\(t\)所处的状态记为\(S_t \in S\)；
  • 智能体在时间步\(t\)所采取的行为记为\(A_t \in A(s)\)；
  • 采取行为\(A_t\)后智能体转到状态\(S_{t+1}\)，并获得奖励\(R_{t+1} \in R\)；
  • 马尔科夫决策过程产生的序列记为 \[S_0, A_0, R_1, S_1, A_1,R_2, \cdots\]

3. 建模

模型：

\[p(s', r|s, a) \doteq Pr\{S_t=s', R_t=r|S_{t-1}=s,A_{t-1}=a\}\]

这里\(p: S \times R \times S \times A \to [0,1]\)满足 \[\sum_{s' \in S} \sum_{r \in R} p(s',r|s,a)=1, \quad \text{for all} \quad s \in S, \quad a \in A(s)\]

常见推导：

（1）状态转移概率： \[p(s'|s,a) \doteq Pr\{S_t=s'|S_{t-1}=s,A_{t-1}=a\} = \sum_{r \in R} p(s',r|s,a)\]

(2) “状态-行为”对的期望奖励： \[r(s,a) \doteq E[R_t|S_{t-1}=s,A_{t-1}=a] = \sum_{r \in R} r \sum_{s' \in S} p(s',r|s,a)\]

(3) "状态-行为-下一状态"的奖励： \[r(s,a,s') \doteq E[R_t|S_{t-1} = s, A_{t-1}=a, S_t = s'] = \sum_{r \in R} r \frac{p(s',r|s,a)}{p(s'|s,a)}\]

示例：

4. 奖励

4.1. 奖励假设

目标和奖励：

  • 目标：长期或最终的；
  • 奖励：即时奖励；

奖励假设（reward hypothesis）：That all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of received scalar signal(called reward).

设置奖励：奖励是我们与智能体进行交互的途径。

4.2. 奖励设置

设置奖励是希望智能体能达到期望的目标：

  • 围棋：奖励需要能够实现赢棋这一目标（吃子多少？占领棋盘中心？）；
  • 迷宫：目标是尽快走出迷宫，可设置每走一步，奖励-1；
  • 垃圾回收机器人：目标是在尽可能少的人工干预的情况下回收尽可能多的垃圾，奖励可设置为回收一个垃圾奖励+1，人工干预一次奖励-3。

4.3. 累计奖励

累计奖励（回报return）： \[G_t \doteq R_{t+1} + R_{t+2} + \cdots + R_T\] 其中\(T\)表示最后一步，对应的状态被称为终止态。

  • 具有终止态的马尔可夫决策过程被称为“多幕式”任务；
  • 没有终止态的任务称为连续式任务，其累计奖励记为 \[G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\] 其中\(0 \leqslant \gamma \leqslant 1\)表示折扣率。

4.4. 累计奖励的递推公式

递推公式： \[\begin{align} G_t & \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \nonumber \\ &= R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \cdots) \nonumber \\ &= R_{t+1} + \gamma G_{t+1} \nonumber \end{align}\]

求和公式： \[G_t \doteq \sum_{k=t+1}^T \gamma^{k-t-1} R_k\]

注意：\(\gamma=1\)和\(T=\infty\)不能同时出现。

5. 策略和状态估值函数

策略：

  • 状态到行为的映射；
  • 随机式策略：\(\pi(a|s)\)；
  • 确定式策略：\(a = \pi(s)\)；

给定策略\(\pi\)，状态估值函数（state-value function）定义为 \[v_{\pi}(s) \doteq E_{\pi}[G_t|S_t=s] = E_{\pi} \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t=s \right], \quad \text{for all} \quad s \in S\]

给定策略\(\pi\)，行为估值函数（action-value function）定义为 \[q_{\pi}(s,a) \doteq E_{\pi} [G_t | S_t=s,A_t=a] = E_{\pi} \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg|S_t=s,A_t=a \right]\]

6. 贝尔曼方程

状态估值函数的贝尔曼方程： \[\begin{align} v_{\pi}(s) & \doteq E_{\pi} [G_t|S_t=s] \nonumber \\ &= E_{\pi} [R_{t+1} + \gamma G_{t+1} | S_t=s] \nonumber \\ &= \sum_a \pi(a|s) \sum_{s'} \sum_r p(s',r|s,a) \Big[ r+\gamma E_{\pi}[G_{t+1}|S_{t+1}=s'] \Big] \nonumber \\ &= \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \Big[ r + \gamma v_{\pi}(s') \Big], \quad \text{for all} \quad s \in S \nonumber \end{align}\]

Tip:Bellman equation expresses a relationship between the value of a state and the values of its successor states.

贝尔曼方程的作用——贝尔曼方程定义了状态估值函数的依赖关系：

  • 给定策略下，每个状态的估值视为一个变量；
  • 所有状态（假如有\(n\)个）的估值根据贝尔曼方程形成一个具有\(n\)个方程和\(n\)个变量的线性方程组；
  • 求解该方程组即可得到该策略下每个状态的估值。

示例：Gridworld

7. 最优策略

状态估值函数定义了策略中间上的一个偏序：给定两个策略\(\pi\)和\(\pi'\)，如果对于所有状态\(s\)，都有\(v_{\pi}(s) \geqslant v_{\pi'}(s)\)，则可以说\(\pi \geqslant \pi'\)。

最优策略：

  • 最优策略\(\pi_*\)对应于如下状态估值函数： \[v_*(s) \doteq \max_{\pi} v_{\pi} (s)\]
  • 最优策略可以有多个，所对应的状态估值函数都一样；
  • 最优策略对应的行为估值函数： \[q_*(s,a) \doteq \max_{\pi} q_{\pi} (s,a)\]

7.1. 贝尔曼最优性方程

1. 状态估值函数的贝尔曼最优性方程： \[\begin{align} v_*(s) &= \max_{a \in A(s)} q_{\pi_*}(s,a) \nonumber \\ &= \max_a E_{\pi_*} [G_t | S_t=s, A_t=a] \nonumber \\ &= \max_a E_{\pi_*} [R_{t+1} + \gamma G_{t+1} | S_t = s, A_t=a] \nonumber \\ &= \max_a E[R_{t+1} + \gamma v_*(S_{t+1})|S_t=s,A_t=a] \nonumber \\ &= \max_a \sum_{s',r} p(s',r|s,a) [r + \gamma v_*(s')] \nonumber \end{align}\]

2. 行为估值函数的贝尔曼最优性方程： \[\begin{align} q_*(s,a) &= E \bigg[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1},a') \Big| S_t=s,A_t=a \bigg] \nonumber \\ &= \sum_{s',r} p(s',r|s,a) [r+\gamma v_*(s')] \nonumber \end{align}\]

7.2. 寻找最优策略

基于状态估值函数的贝尔曼最优性方程：

  1. 第一步：求解状态估值函数的贝尔曼最优性方程得到最优策略对应的状态估值函数；
  2. 第二步：根据状态估值函数的贝尔曼最优性方程，进行一步搜索找到每个状态下的最优性行为：
    • 注意：最优策略可以存在多个；
    • 贝尔曼最优性方程的优势，可以采用贪心局部搜索即可得到全局最优解。

基于行为估值函数的贝尔曼最优性方程：

  • 直接得到最优策略。

示例：Gridworld

7.3. 寻找最优策略小结

求解贝尔曼最优性方程寻找最优策略的局限性：

  • 需要知道环境模型\(p(s',r|s,a)\)；
  • 需要高昂的计算代价和内存（存放估值函数）；
  • 依赖于马尔可夫性。

实际应用中寻找最优策略的方法：

  • 动态规划方法
  • 蒙特卡洛方法
  • 时序差分方法
  • 参数化方法