强化学习 2：马尔可夫决策过程（MDP）与贝尔曼方程（Bellman）

Autumn

分类：机器学习

发布时间 2021.12.03阅读数 5055 评论数 0

强化学习的基础模型就是马尔可夫决策过程（MDP），大部分强化学习问题都可以被转化为MDP问题。

参考资料

[1] gwave：马尔可夫决策过程MDP -- 强化学习基础（1）

[2] 叶强：《强化学习》第二讲马尔科夫决策过程

[3] 张楚珩：【强化学习入门 1】从零开始认识强化学习

[4] 华师数据学院·王嘉宁：强化学习（三）：有限马尔可夫决策与贝尔曼方程

[5] 野风同学：强化学习——马尔科夫决策过程和贝尔曼方程

1 马尔可夫性质（Markov property）

一个随机过程的未来状态的条件概率分布仅依赖于当前状态，与过去状态是条件独立的，那么此随机过程即具有马尔可夫性质。

2 马尔可夫链（Markov Chain, MC）/马尔可夫过程（Markov Process）

马尔可夫链的概念比较宽泛，有时候会认为它包括连续时间马尔可夫链（Continuous-Time MC, CTMC） ，与离散时间马尔可夫链（Discrete-Time MC, DTMC）。

但有时候认为它是具有马尔可夫性质且存在于离散的指数集和状态空间内的随机过程，而认为马尔可夫过程为适用于连续指数集的马尔可夫链。

不过对于马尔可夫链和马尔可夫过程的概念不用过于区分，视作一样的含义即可。

用元组 $<S,P>$ 表示，其中 $S$ 是有限数量的状态集， $P$ 是状态转移概率矩阵（n×n阶）。所谓状态转移矩阵就是描述了一个状态到另一个状态发生的概率，所以矩阵每一行元素之和为1。

3 马尔可夫回报过程（Markov Reward Process, MRP）

MRP就是带有价值的马尔可夫链，以元组 $<S,P,R,γ>$ 表示，其中 $R$ 是回报、 $γ$ 是衰减率。

4 马尔可夫决策过程（Markov Decision Process, MDP）

以元组 $<S,A,P,R,γ>$ 表示，其中 $A$ 是状态 $S$ 下的有限数量的动作集。

$P(s'|s,a)$ 表示在状态s下执行动作a后转移到状态 $s'$ 的概率。 $P^a_{ss'}=P(S_{t+1}=s'|S_t=s,A_t=a)\\$

$R(s',s,a)$ 表示在状态s下执行动作a后转移到状态 $s'$ 时取得的即时回报。 $R^a_{ss'}=E(R_{t+1}|S_t=s,A_t=a,S_{t+1}=s')\\$

5 贝尔曼方程（Bellman Equation）

5.1 状态价值函数的贝尔曼方程

$V_\pi(s)= \mathbb{E}_\pi(G_t|S_t=s) \\$ $=\sum_{a}Π(a|s)Q(s,a) \\$ $=\sum_{a}Π(a|s)\sum_{s'}P^a_{ss'}[R^a_{ss'}+γV_\pi(s')] \\$

第一行表示的是价值函数的定义;

第二行可知，状态价值就是在当前状态 $s$ 所有可能采取的动作 $a$ 得到的动作价值的期望;

第三行则表示当前状态 $s$ 的价值 $V_Π(s)$ 与下一个状态 $s'$ 的价值 $V_Π(s')$ 之间的递归关系。

图解：

从顶端状态开始，有 $Π(a|s)$ 概率选择其下的两个动作（黑点）,又有 $P^a_{ss'}$ 概率转移到下一个状态 $s'$ ，并获得回报 $R^a_{ss'}$ ， $γV_\pi(s')$ 则代表新状态 $s'$ 的回报。

5.2 动作价值函数的贝尔曼方程

$Q_Π(s,a)= \mathbb{E}_\pi(G_t|S_t=s,A_t=a) \\$ $=\sum_{s'}P^a_{ss'}[R^a_{ss'}+γV_\pi(s')] \\$ $=\sum_{s'}P^a_{ss'}[R^a_{ss'}+γ \sum_{s', a'}Π(a'|s')Q(s',a')] \\$

第一行表示动作价值的定义；

第二行指当前动作价值是经过状态转移之后得到局部收益 $R^a_{ss'}$ 和所处新的状态的状态价值折扣后和的期望，换句话说是描述状态动作二元组 $(s,a)$ 的价值与下一时刻 $s'$ 的价值之间的关系；

第三行则表示相邻两个时刻动作价值的递推关系式。

6 贝尔曼最优方程（Bellman Optimality Equation）

对于任意一个MDPs，总是存在一个最优的策略 $Π_*$ ，此时 $V_{\pi_* }(s)=V_* (s)$ 【从所有策略产生的状态价值函数中，选取使状态s价值最大的函数】， $Q_{\pi_* }(s,a)=Q_* (s,a)$ 【从所有策略产生的行为价值函数中，选取使状态行为对 $<s,a>$ 价值最大的函数】，贝尔曼最优方程如下：