【强化学习】Markov Decision Processes

1.强化学习介绍

（1）典型的RL问题

强化学习（RL）问题可以通过下图描述

RL中的代理和环境：
代理在观察环境状态 $s_t$ 后决定采取哪些行动
环境基于代理采取的行动 $a_t$ ，从一个状态 $s_t$ 过渡到另一个状态 $s_{t+1}$ 并产生奖励 $R_{t+1}$

我们只能为代理设计动作选择算法（即策略），而不能控制环境的演变

（2）RL中的环境

环境决定状态 $S_t$ 的演化方式以及观察动作 $a_t$ 后发出的奖励数量

在数学上，环境由两个概率分布来描述，即

状态转换： $P[S_{t+1}=s'|S_t=s,A_t=a]$
回报： $P[R_{t+1}|S_t=s,A_t=a]$

根据代理是否知道分布，可以将RL分为两类：基于模型的RL和不基于模型的RL

（3）RL的策略

策略：观察环境状态s后确定采取的行动

在数学上，策略可以由条件概率分布表示： $\pi(a|s)=P(A=a|S=s)$ ，其中 $a\in{A},s\in{S}$

（4）RL的目标

找到一个策略 $\pi(a|s)$ ，使平均累积奖励 $E_{\pi}[R_{t+2}+\gamma R_{t+2}+\gamma^2R_{r+3} ... ]$ 最大，其中 $\gamma \in{[0,1]}$ 是折扣因子

（5）RL举例

问题描述：

(1) 状态：agent的位置

(2) 行动：North,East,South,West

(3) 回报：每步-1

每个状态学习的策略如下：

2.Markov决策过程

从数学上讲，所有RL问题都可以表述为MDP

（1）Markov过程

马尔可夫过程： 状态 $s\in S$ 根据转移概率 $P[s'|s]$ 顺序生成,如： $S_1,S_2,...,S_t,S_{t+1},...$

该序列具有Markov属性，这在数学上意味着: $P[S_{t+1}|S_1,...,S_t]=P[S_{t+1}|S_t]$

这表示，给定现在，未来就独立于过去。即，在当前状态下，所有历史信息都可以丢弃。

马尔可夫过程可以表示为元祖<S，P>，其中S是状态空间 ，P是状态转移矩阵 。其中

而 $p_{ss'}=P[s'|s]$

Markov过程举例

这样一个马尔科夫过程的状态转移矩阵为

而所有以 $C_1$ 为其实状态的策略为：

（2）Markov奖励过程

马尔可夫回报过程（MRP）：与每个状态的奖励相关联的马尔可夫过程： $S_1,R_2,S_2,R_3,...,S_t,R_{t+1},S_{t+1},R_{t+2},...$

MRP可以由四元组 $<S,P,R,\gamma>$ 表示。其中S是所有可能状态的集合，P是概率转移矩阵，R是给定状态s的回报函数 $P[R_{t+1}|S_t]$ ， $\gamma$ 是折扣因子 $\gamma \in [0,1]$

Markov回报过程

回报：是时间t之后的折扣后总奖励，即

$G_t=R_{t+1}+\gamma R_{t+1}+...={\sum_{k=0}^{+\infty}\gamma^k R_{t+k+1}}$

回报举例

以上图，在t=1时，可能回报 $G_1$ 是: $\gamma = \frac{1}{2}$

（在t=0时，状态s0为Class 1，t=1时，状态s1为Sleep）

折扣因子 $\gamma$ 的作用：

1）确保收敛

2）不确定性未完全体现

3）近期奖励比远期奖励更有价值

两种特殊情况

1） $\gamma = 0$ 表示代理仅关心即时奖励

2） $\gamma = 1$ 表示代认为所有未来状态的回报同样重要

（3）Markov决策过程

马尔可夫决策过程（MDP）：与每个状态的决策相关的MRP： $S_1,A_1,R_2,S_2,A_2,R_3,...,S_t,A_t,R_{t+1},S_{t+1},A_{t+1},R_{t+2},...$

MDP由五元组 $<S,A,P,R,\gamma>$ 表示。其中S是所有状态的集合，A是行为的集合，P是概率转移矩阵 $P^a_{ss'}=P[s_{t+1}=s'|s_t=s,A_t=a]$ ，R是给定状态s和行为a的回报函数 $P[R_{t+1}|S_t=s,A_t=a]$ ， $\gamma$ 是折扣因子。

MDP举例

策略

策略 $\pi$ 是给定状态的行为的条件分布： $\pi (a|s)=P[A_t=a|S_t=s]$

策略决定在不同状态采取哪种行动
政策仅取决于当前状态，与历史无关
策略是固定的（与时间无关）

给定一个MDP $<S,A,P,R,\gamma>$ 和一个策略 $\pi (\cdot)$ ,随机序列可以根据 $\pi (a|s)$ 、回报函数 $P[R_{t+1}|S_t=s,A_t=a]$ 和概率转移矩阵 $P^a_{ss'}$ 得出： $...S_{t-1},A_{t-1},R_t,S_t,A_t,R_{t+1},S_{t+1},A_{t+1},R_{t+2}...$