马尔可夫决策过程（MDP）

目录
智能体与环境
马尔科夫决策过程

1. 智能体与环境
   强化学习问题不同于传统机器学习问题，它是一种在交互的过程中学习并实现目标的问题。这里把具有学习能力和决策能力的程序或系统称之为Agent（代理，智能体）；与之交互的对象统称为环境（Environment）。交互过程如下图所示：

chapter1-pic02-agent-envs-interaction
chapter1-pic02-agent-envs-interaction

智能体与环境的交互通常是在离散的“时间步长”（discrete time steps）中进行的，t=0,1,2,⋯。 在时刻t，智能体会针对当前环境状态St，执行一个动作At，在下一时刻t+1, 环境在动作At的作用下会产生新的状态St+1。同时智能体也会接收到一个回报Rt+1。持续地交互过程中，Agent与Environment会产生大量的数据。智能体中的算法利用产生的数据调整自身的动作策略，再与环境交互，产生新的数据，并利用新的数据进一步优化自身策略。经过循环往复，智能体最终学习到相应任务整体收益最大化对应的最优策略。

在每一步中，智能体都要完成从状态到选择每个可能动作的映射。这个映射过程称为智能体的决策（policy，用符号πt表示）。那么πt(At=a|St=s)表示状态为St=s时选择制定动态At=a的概率。

强化学习解决的是在交互过程中以目标为导向的学习问题，目标就是长期收益最大化。无论学习的场景是什么、目标是什么，以目标为导向的行为学习问题都可以归纳为3个主要的“信号”（signal）：

Action（动作）：智能体的选择集合；
State（状态）：智能体从环境接收到的信息，涉及到信息表示／描述问题；
Reward（奖赏）：智能体获得的奖赏。决定了优化目标和长期收益。
无数学者们经过几十年不断的努力和探索，提出了一套可以解决大部分强化学习问题的框架，这个框架就是马尔可夫决策过程（Markov Decision Process, 简称MDP）. 下面我们循序渐进地介绍MDP过程。

在开始讲MDP之前，我们先花点时间看下强化学习与传统的监督学习、无监督学习问题在算法建模、数据方面的差异：

强化学习与传统机器学习

传统机器学习假设算法本身与环境无影响，强化学习破除了这一限制，考虑到了算法对于环境的影响，这使得强化学习特别适合解决多回合博弈or顺序决策问题（sequential decision making）。

在强化学习中，数据是在运行过程中自主收集。这解决了机器学习中常见的训练数据难于获取的问题。强化学习的算法具有自主学习能力，这就是强化学习在机器人领域里面使用比较广泛的原因。但是要注意到的是，通常强化学习的速度限制并不是来自于算法的训练，而是来自于环境给予反馈的延时。

2. 马尔科夫决策过程
   MDP依赖一些基本概念，比如状态、随机过程、马尔可夫性、马尔可夫过程等等这些到底是什么意思。我们先梳理下这部分知识：

马尔可夫性：所谓马尔可夫性是指系统的下一个状态st+1仅与当前状态st有关，而与以前的状态无关。

定义：状态st是马尔可夫的，当且仅当 p(st+1|st)=p(st+1|st,st−1,⋯,s1)。

从定义中可以看到，当前状态st其实蕴含了所有相关的历史信息s1,⋯,st。 马尔可夫性描述的是每个状态的性质，但真正有用的是如何描述一个状态序列。数学中用来描述随机变量序列的学科叫随机过程（本科数学系or研究生数学课程）。所谓随机过程就是指随机变量序列。

如果随机变量序列中的每个状态都满足马尔可夫性，那么该随机过程称为马尔可夫随机过程。

马尔可夫过程

定义：马尔可夫过程用一个二元组(S,P)表示，且满足：S是有限状态集合，P是状态转移概率集合。对应的状态转移概率矩阵为：

P=⎡⎣⎢⎢⎢⎢⎢P11 ⋮ Pn1 ⋯⋱⋯P1n⋮Pnn⎤⎦⎥⎥⎥⎥⎥
下面用一个例子来直观地理解。

//TODO 待补充

以上状态序列称为马尔可夫链。当给定状态转移概率时，从某个状态出发存在多条马尔可夫链。

马尔可夫决策过程

对于智能体（可以是机器人）而言，马尔可夫过程不足以描述其特点，因为他们都是通过动作与环境进行交互，并从环境中获得奖励，而马尔可夫过程不存在动作和奖励。那么，将动作（策略）和奖励（回报）考虑在内的马尔可夫过程称为马尔可夫决策过程。

马尔可夫决策过程可以用四元组(S,A,P,R)描述，其中：S为有限的状态集合，A为有限的动作集合，P为状态转移概率集合，R为回报函数。与马尔可夫过程不同的是，马尔可夫决策过程的状态转移概率是包含动作的，即：Pass′=P(St+1=s′|St=s,At=a).

强化学习的目标是给定一个马尔可夫决策过程，寻找最优策略。策略即是状态到动作的映射，这里用符号π表示，它是指给定状态s时，动作在动作集合中的分布。即：π(a|s)=p(At=a|St=s)。

可以看到，策略的定义是用条件概率分布给出的。策略π在每个状态s指定一个动作概率。可以想象，如果给出的策略π是确定性的，那么策略π在每个状态s指定一个确定的动作。

符合MDP过程强化学习问题的优化目标是什么？寻找最优策略。并且在给定策略下，可以评估状态或状态－动作对的值函数。

累积回报

前面提到，智能体的目标是最大化长期受到的累积回报（cumulative reward）。如何定义累计回报呢？如果在时间t时刻之后，智能体接受到的回报序列表示成Rt+1,Rt+2,⋯,RT. 那么，我们寻求的是最大化期望回报（expected return），这里用Gt表示特定的回报序列函数。回报的表示方法之一是将回报累加，即：

Gt=Rt+1+Rt+2+⋯+RT
考虑到实际场景，在计算累积回报时都会引入一个折扣因子（用γ表示)。智能体尝试选择一个动作使得未来的折扣回报累积最大化。特别的，智能体会在时刻t选择动作At能最大化期望折扣回报（expected discounted return）。即：

Gt=Rt+1+γRt+2+γ2Rt+3+⋯+γT−tRt+k+1=∑k=0T−t−1γkRt+k+1
上式包括T=∞或者γ=1的可能（但是两者不能同时满足）。 由于策略π是随机的，所以累积回报也是随机的。为了评价状态s的价值，我们需要定义一个确定量来描述状态s的价值，很自然的想法是利用累积回报来衡量状态s的价值。然而，累积回报Gt是个随机变量，不是一个确定值，因此无法进行描述。但是累积回报的期望是个确定值，可以作为状态值函数的定义。

值函数

几乎所有的强化学习算法都涉及到评估值函数(状态值函数或者状态-动作值函数)，因为在强化学习中知识是存储在值函数中的。值函数用来评估智能体在给定状态或状态－动作对下表现的会有“多好”。这里的“多好”用累积回报的期望来衡量。因此，我们可以说：值函数=累积回报的期望，最优值函数是我们的寻找目标。

所谓深度强化学习是利用深度神经网络来逼近值函数的一类强化学习方法。AlphaGo Zero使用了华人科学家何凯明等人提出的深度残差网络（ResNet）进行深度学习。

这里用π表示策略，即状态到动作的映射。用π(a|s)表示当状态为s时，采取动作a的概率(条件概率分布)。在策略π下状态s的值函数(状态值函数)用vπ(s)表示。对于MDP过程，vπ(s)形式化表示为：

vπ(s)=Eπ[Gt|St=s]=Eπ[∑k=0∞γkRt+k+1∣∣St=s]
这里Eπ[⋅]表示在策略π下状态s的期望值（最终状态的函数值总是为0）。我们称vπ为策略π对应的状态值函数（state-value function）。

定义：所有策略中对应的最大状态值函数称为最优状态值函数，表示为v∗(s)=maxπvπ(s).

类似的，在策略π下，状态为s时动作a对应值函数 我们称之为状态动作值函数（action-value function），用qπ(s,a)表示为：

qπ(s,a)=Eπ[Gt|St=s,At=a]=Eπ[∑k=0∞γkRt+k+1∣∣St=s,At=a]
定义：所有策略中对应的最大状态动作值函数称为最优状态动作值函数，表示为q∗(s,a)=maxπqπ(s,a).

计算值函数的目的就是为了构建学习算法从数据中学到最优策略。策略与值函数一一对应，最优策略对应最优值函数。

贝尔曼方程

贝尔曼方程建立了当前状态值函数vπ(St)与下一状态值函数vπ(St+1)之间的关系，使得值函数可以被分解成子问题求解。以状态值函数为例：

vπ(s) =Eπ[Gt|St=s]=Eπ[Rt+1+γ(Rt+2+γRt+3+⋯)|St=s]=Eπ[Rt+1+γGt+1|St=s]=Eπ[Rt+1+γvπ(St+1)|St=s]
可以看到，值函数可以被拆成两部分：立即奖赏Rt+1和下一状态折扣后的值函数γvπ(St+1)。

类似的，状态动作值函数也满足贝尔曼方程，即：

qπ(s,a)=Eπ[Rt+1+γqπ(St+1,At+1)|St=s,At=a]
状态值函数与状态动作值函数的关系：

vπ(s) qπ(s,a)=∑a∈Aπ(a|s)⋅qπ(s,a)=R(s,a)+γ∑s′∈SP(s′|s,a)vπ(s′)
因此，我们进一步可以得到：

vπ(s) qπ(s,a)=∑a∈Aπ(a|s)(R(s,a)+γ∑s′∈SP(s′|s,a)vπ(s′))=R(s,a)+γ∑s′∈SP(s′|s,a)∑a′∈Aπ(a′|s′)⋅qπ(s′,a′)
这里π(a|s)表示状态s对应不同的策略（动作集合的子集），R(s,a)表示状态s下执行动作a得到的立即奖赏；P(s′|s,a)表示执行动作a后下一步的状态概率。

分别记最优策略π∗对应的状态值函数和状态动作值函数为v__(s)和q__(s,a)，它们之间的关系满足：v∗(s)=maxaq∗(s,a)。因此，状态值函数对应的贝尔曼最优方程为：

v∗(s)=maxa(R(s,a)+γ∑s′∈SP(s′|s,a)v∗(s′))
状态动作值函数对应的贝尔曼最优方程为：

q∗(s,a)=R(s,a)+γ∑s′∈SP(s′|s,a)maxa′∈Aq∗(s′,a′)
最优策略（Optimal Policy）

先看最优策略的定义：如果策略π是最优的，当且仅当对于任意的状态s, 均存在策略π对应的值函数大于等于其它策略的值函数。用公式表示为：π≥π′,ifvπ(s)≥vπ′(s),∀s.

所以很重要的一个结论：我们构造&&优化值函数，本质上是得到最优的策略。因为值函数最优与策略最优 在这里是等价的。

对于任意的马尔科夫决策过程，以下条件均成立：

最优策略π∗均不差于所有其他的策略，形式化表示：π∗≥π,∀π;
所有的最优策略均对应着最优状态值函数，形式化表示：v_{\pi__}(s) = v__(s);
所有的最优策略均对应着最优状态动作值函数，形式化表示：q_{\pi__}(s,a) = q__(s,a);
以上3条就是策略最优定理。最优策略满足公式（状态值函数对应的贝尔曼最优方程），最优策略可以通过最大化动作状态值函数贝尔曼最优方程来求解。即：

π∗(a|s)=⎧⎩⎨⎪⎪1,if a = argmaxa∈Aq∗(s,a) 0,otherwise.
这里系统地梳理下强化学习中关键概念之间的关系，即累积回报、状态值函数、最优策略等。

强化学习是解决交互过程中、以目标为导向的序列学习问题的一类机器学习算法。 这里的目标即为最大化累积回报，而累积回报受过程中的策略π影响，策略π是随机变量，所以累积回报也是一个随机变量。

强化学习希望通过一个确定的函数－价值函数－能描述最大化的累积回报。因此就用了累积回报的期望来描述价值函数。 根据策略最优定理：价值函数最优所对应的策略即为最优策略，即最优策略的选择可以根据价值函数的最大值来确定。

那么，强化学习求解问题最后就转化为如果获得最优的价值函数（状态值函数or状态动作值函数）.

转载于http://www.52caml.com/reinforcement-learning/chapter3-markov-decision-process/