RL-Ch2-马尔可夫决策过程

2020-10-22

RL-Ch2-马尔可夫决策过程

前情回顾

RL Agent的核心元素为model，value，policy。

课程大纲

Markov Chain–>Markov Reward Process–>Markov Decision Process
Policy evaluation in MDP
Policy iteration and value iteration

引入

上章图1的RL过程可转化为MDP，但是MDP下的环境是完全可观测的，很多时候环境不完全可观测时也可通过一些方法转化为MDP。

Markov性质

Markov Property指的是未来的状态只取决于当下的状态，而独立于过去的状态。

令历史状态序列为$h_t={S_1,S_2,…,S_t}$，若$S_t$满足Markov Property，则有如下式子成立
$$
P(S_{t+1}|S_t)=P(S_{t+1}|h_t)
$$

$$
P(S_{t+1}|S_t,a_t)=P(S_{t+1}|h_t,a_t)
$$

Markov Chain (S,P)

图1为状态转换图，图中包含有状态(State)和转移矩阵(Probability)。

图1 二维的Markov Chain

状态转移矩阵可写为
$$
P=[p(s_{t+1})=s|s_t=s]=\left[
\begin{matrix}
p(s_1|s_1)&…&p(s_N|s_1)\
p(s_1|s_2)&…&p(s_N|s_2)\
\vdots&\ddots&\vdots\
p(s_1|s_N)&…&p(s_N|s_N)
\end{matrix}
\right]
$$

状态转换图中的一个链条即为Markov Chain。

Markov Reward Process(MRP) (S,P,R,$\gamma$)

MRP=Markov Chain+Reward

Markov Chain包含State和transition Probability matrix，而Reward包含Reward function $R[s_t=s]=\mathbb{E}(r_t|s_t=s)$和折扣因子$\gamma$。

Horizon

Markov (Reward) Process分为有限步和无限步，其中记有限步中的序列的最大时间步数为Horizon。

Return

记从当前时间步t->Horizon的收益加权和为Reward，计算公式如下
$$
G_t=R_{t+1}+\gamma R_{t+2}+…+\gamma^{T-t-1}R_T
$$

状态价值$V_t(s)$

记对未来可能获得价值的当前表现，即状态s时当前时间步t的期望收益为状态价值$V_t(s)$。
$$
V_t(s)=\mathbb{E}(G_t|s_t=s)=\mathbb{E}(R_{t+1}+\gamma R_{t+2}+…+\gamma^{T-t-1}R_T|s_t=s)
$$
上式的矩阵形式为
$$
\left[
\begin{matrix}
V(s_1)\
V(s_2)\
\vdots\
V(s_N)
\end{matrix}
\right]
=\left[
\begin{matrix}
V(s_1)\
V(s_2)\
\vdots\
V(s_N)
\end{matrix}
\right]
+\gamma\left[
\begin{matrix}
p(s_1|s_1)&…&p(s_N|s_1)\
p(s_1|s_2)&…&p(s_N|s_2)\
\vdots&\ddots&\vdots\
p(s_1|s_N)&…&p(s_N|s_N)
\end{matrix}
\right]\left[
\begin{matrix}
V(s_1)\
V(s_2)\
\vdots\
V(s_N)
\end{matrix}
\right]
$$

即$V=R+\gamma PV$。

折扣因子$\gamma$的意义

避免环形MC产生无穷的奖励
体现不确定性：关注当前奖励而非未来
奖励若有实质价值，倾向于更快得到奖励
动物/人趋向于即时奖励
$\gamma=0$，即时奖励；$\gamma=1$，未来与当下奖励等同看待。(超参数)

例子

取下图做例子，记$s_1$的奖励为+5，$s_4$的奖励为+10，则R=[5,0,0,10]。取$\gamma=0.5$。

图2 一维的Markov Chain

则其中可能的两条Markov Chain的return的计算过程如下：

$s_1,s_2,s_3,s_4: return=5+0.50+0.250+0.125*10=6.25$

$s_1,s_2,s_2,s_1: return=5+0.50+0.250+0.125*0=5$

如何计算$V(s_1)$？

Method1：穷举所有$s_1$为起点的马氏链，取平均。

Method2：Bellman Equation：定义了状态之间的迭代关系
$$
V(s)=R(s)+\gamma\sum_{s’\in S}P(s’|s)V(s’)
$$

式(7)等号右边第一项为即时奖励，第二项为折减的下一时刻奖励。式(7)求解方法有如下两类：

Method2.1：分析法求解：$V=(I-\gamma P)^{-1}R$

涉及到矩阵求逆，计算复杂度为$O(N^3)$，所以仅适用于小问题规模MRP的求解

Method2.2：迭代法求解：适用于大问题规模MRP求解：

* 动态规划：不断迭代Bellman Equation产生最优解（Bootstripping）
* 蒙特卡洛法（Mento-Carlo）:不断选取多段轨迹，求轨迹的return和，然后取平均。（与Method1有区分）
* 时序差分学习（Temporal-Difference Learning）

练习

从$V(s)=\mathbb{E}[R_{t+1}+\gamma\mathbb(R_{t+2}+\gamma^2R_{t+3}+…)|s_t=s]$推导式(6)。

待解答。

Markov Decision Process(MDP) (S,A,P,R,$\gamma$)

相较于MRP多了个决策空间$A$，状态转移矩阵从$P=[p(s_{t+1})=s|s_t=s]$转变为$P=[p(s_{t+1})=s|s_t=s,a_t=a]$，reward function从$R[s_t=s]=\mathbb{E}(r_t|s_t=s)$转变为$R[s_t=s]=\mathbb{E}(r_t|s_t=s,a_t=a)$

Policy

每个状态s应采取什么样的a。分类可分为以下两类：

概率型：$\pi(a|s)=P(a_t=a|s_t=s)$
决定型：s直接决定a

假设：Policy是静态的，s决定a的分布，即$A_t \sim \pi(a|s)\quad for,any,t>0$

给定马尔可夫决策过程$(S,A,P,R,\gamma)$和策略$\pi$，其中的$S_1,S_2,\dots$为马尔科夫链$(S,P^{\pi})$，$S_1,R_1,S_2,R_2,\dots$则为马尔科夫奖励过程$(S,P^{\pi},R^\pi,\gamma)$。则有如下式子成立：

$$
P^\pi(s’|s)=\sum_{a\in A}\pi(a|s)P(s’|s,a)
$$

$$
R^\pi(s)=\sum_{a\in A}\pi(a|s)R(s,a)
$$
式(8)代表所有从状态s->s’的动作a的求和。

式(9)代表状态s所有可产生行为a的后果奖励求和。

MP/MRP vs. MDP

通过树状图区分MP/MRP与MDP。

图3 Markov (Reward/Decision) Process树状图

MP与MDP相比，就相当于自由滑行的船与有人工控制的船。

价值函数(value function)

在policy $\pi$下的状态s的期望收益，即
$$
V^\pi(s)=\mathbb{E}_\pi[G_t|s_t=s]
$$

行为价值函数(Action-value function)

在policy $\pi$下的状态s采取a的期望收益，即
$$
q^\pi(s,a)=\mathbb{E}_\pi[G_t|s_t=s,a_t=a]
$$

v-func和q-func之间的关系

$$
V^\pi(s)=\sum_{a\in A}\pi(a|s)q^\pi(s,a)
$$
相当于把a节点隐藏。过程中需要完成叶节点的合并。

Bellman Expectation Equation

$$
V^\pi(s)=\mathbb{E}[R_{t+1}+\gamma V^{\pi}(s_{t+1})|s_t=s]
$$

$$
q^\pi(s,a)=\mathbb{E}[R_{t+1}+\gamma q^{\pi}(s_{t+1},a_{t+1})|s_t=s,a_t=a]
$$

由图3可知，
$$
V^\pi(s)=\sum_{a\in A}\pi(a|s)q^\pi(s,a)
$$

$$
q^\pi(s,a)=R_{s}^a+\gamma \sum_{s’\in S}P(s’|s,a)V^\pi(s’)
$$

联立式(15)、(16)，可得

$$
V^\pi(s)=\sum_{a\in A}\pi(a|s)(R(s,a)+\gamma \sum_{s’\in S}P(s’|s,a)V^\pi(s’))
$$

$$
q^\pi(s,a)=R(s,a)+\gamma \sum_{s’\in S}P(s’|s,a)\sum_{a’\in A}\pi(a’|s’)q^\pi(s’,a’)
$$
式(17)、(18)中两个求和符号分别代表着两层树从叶节点到根节点的求和。其中式(17)的根节点为状态s，式(18)的根节点为动作a。

Policy Evaluation

估计当前策略$\pi$的价值$V^\pi(s)$。

选择好policy $\pi(s)$和折扣因子$\gamma$，则policy evaluation的值可由
$$
V_t^\pi(s)=R(s,\pi(s))+\gamma\sum_{s’\in S}P(s’|s,\pi(s))V_{t-1}^\pi(s’)
$$
通过迭代（t–>\inf）求出$V^\pi(s)$。

Decision in MDP

Prediction（评估策略）
- Input：MDP$(S,A,P,R,\gamma)$和策略$\pi$
- Output：Value Function $V^\pi$
Control（查找最佳策略）
- Input：MDP$(S,A,P,R,\gamma)$
- Output：最优$V^*$和最优$\pi$

通过动态规划求解Prediction & Control

动态规划

可以解决的问题：

问题可分解为最佳子结构
子结构求解后能递推得到最优解

MDP满足以上性质：

Bellman Equation可递归分解
价值函数可存储和再利用解

Policy Evaluation in MDP

算法：Synchronous backup

在第t轮迭代过程，式(19)不断收敛，$V_1^\pi–>V_2^\pi–>…–>V^\pi$

Bellman Expectation backup
$$
V_{t+1}(s)=\sum_{a\in A}\pi(a|s)(R(s,a)+\gamma\sum_{s’\in S}P(s’|s,a)V_t(s’))
$$

MRP形式(去掉a)，得到
$$
V_{t+1}(s)=R^\pi(s)+\gamma P^\pi(s’|s)V_t(s’)
$$

最优价值函数

满足$V^*(s)=\max_{\pi} V^\pi(s)$

，最优策略由最优价值函数反推，即$\pi^*(s)=arg\max_{\pi}V^\pi(s)$

我们称MDP被求解当且仅当最优价值函数被求出来，而必伴随最少一个最优策略。

一个最优价值函数可能伴随对各最优策略。

最优策略

特性：确定性、静态性（不依赖时间）、不唯一性。

如何寻找最优策略？

这是一个control问题，可通过最大化q函数来求取。
$$
\pi^(a|s)={ \begin{align}1,&\quad if,a=argmax_{a\in A}q^(s,a)\
0,& \quad otherwise\end{align}
$$

穷举：总可能策略有$|A|^{|S|}$
policy iteration
value iteration

Policy iteration

通过给定\pi计算v
通过Q函数greedy考虑V^\pi去改进\pi
- 通过给定\pi去计算q值：$q^{\pi_i}(s,a)=R(s,a)+\gamma\sum_{s’\in S}P(s’|s,a)V^{\pi_i}(s’)$
- 计算新策略：$\pi_{i+1}(s)=arg\max_{a}q^{\pi_i}(s,a)$

新策略取Q-table中在当前State轴的Action最大值集合为更好的$\pi$。

示意图如下：

如何证明以上所得的策略能得到最佳价值函数？

证明过程如下：

考虑确定性策略$a=\pi(s)$，策略改进后$\pi’(s)=arg \max_{a} q^\pi(s,a)$，

所以
$$
V^\pi(s)=q^\pi(s,a)\leq \max_{a\in A}q^\pi(s,a)=q^\pi(s,\pi’(s))
$$
同时考虑到
$$
q^\pi(s_t,a_t)=E_\pi[R_{t+1}+\gamma q^\pi(s_{t+1},a_{t+1})]
$$

因此
$$
\begin{align}
V^\pi(s)&\leq q^\pi(s,\pi’(s))=E_{\pi’}[R_{t+1}+\gamma V^\pi(s_{t+1})|s_t=s]\
&\leq E_{\pi’}[R_{t+1}+\gamma q^\pi(s_{t+1},\pi’(s_{t+1}))|s_t=s]\
&=E_{\pi’}[R_{t+1}+\gamma (R_{t+2}+\gamma q^\pi(s_{t+2},\pi’(s_{t+2})))|s_t=s]\
&= E_{\pi’}[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+… |s_t=s]\
&=V^{\pi’}(s)
\end{align}
$$

如果improvement结束，则
$$
q^\pi(s,\pi’(s))=\max_{a\in A}q^\pi(s,a)=q^\pi(s,\pi(s))=V^\pi(s)
$$
因此，Bellman最优方程的解得出
$$
V^\pi(s)=\max_{a\in A}q^\pi(s,a)\quad for,all,s\in S
$$

所以$\pi$为最优策略。

Value iteration

知道子问题的最优解($V^*(s’)$)，通过Bellman Optimal backup规则，不断迭代以至收敛：

$$
V(s)<–max_{a\in A}(R(s,a)+\gamma\sum_{s’\in S}P(s’|s,a)V(s’))
$$

Policy iteration vs. Value iteration

代码学习可参考港中大强化学习MDP代码
对比：
- Policy iter：policy evaluation与policy improvement交替进行，直至收敛。
- Value iter：寻找最佳的Value function（过程可认为是policy eval与policy impro的组合，在policy evaluation还没做完的时候就直接进行了policy improvement），从中提取出最佳policy。

总结

Prediction与Control在MDP中的解决

Problem	Bellman Equation	Algorithm
Prediction	Bellman Expectation Equation	Iterative Policy Evaluation
Control	Bellman Expectation Equation	Policy iteration
Control	Bellman Optimal Equation	Value iteration