深入了解马尔科夫决策过程(Markov Decision Process)
深入了解马尔科夫决策过程(Markov Decision Process)
马尔科夫决策过程(Markov Decision Process)
马尔科夫决策过程(Markov Decision Process, MDP)是时序决策(Sequential Decision Making, SDM)事实上的标准方法。时序决策里的许多工作，都可以看成是马尔科夫决策过程的实例。
人工智能里的规划(planning)的概念(指从起始状态到目标状态的一系列动作)已经扩展到了策略的概念：基于决策理论对于待优化目标函数最优值的计算，策略将所有的时序状态映射到一个我们期望的最优动作。
策略的一些限定条件
策略通过以下方式将状态映射到动作上：
- 操作者的动作对规划产生确定性的预期结果。
- 动作的预期结果取决于有关概率性的结果和对目标的贡献(credit)的理论期望。
马尔科夫决策过程的优点
- 允许在线的解决方案：通过模拟实验(simulated trials)逐步地学习最优策略。
- 允许依据计算资源实现近似解决方案。 （在计算资源充足的条件下，给出最优解的方案；反之，则也能给出能让人接受的最优解的近似解）
- 允许对决策理论的策略质量和学习效果进行数值化度量。
形式化描述马尔科夫决策过程
(下面的概念涉及到形式化，博主的导师是研究形式化方法的。)
强化学习问题的元素可以通过马尔科夫决策过程来形式化地描述。马尔科夫决策过程可以看做是有限自动机(finite automata)的随机化扩展，或者看作引入了动作(action)和奖励(rewards)的马尔科夫过程(Markov Process)。
马尔科夫决策过程
定义
马尔科夫决策过程是一个由4个元素构成的四元组<S,A,T,R><S,A,T,R><S,A,T,R>。其中，SSS是一个包含所有动作的有限集合，TTT是一个定义为S×A×S→[0,1]S\times A \times S \rightarrow[0,1]S×A×S→[0,1]的转换函数，RRR是一个定义为R:S×A×S→RR:S\times A \times S \rightarrow\mathbb{R}R:S×A×S→R的奖励函数。
马尔科夫决策过程包括状态(State)、动作(Action)、转换函数(Transition)、奖励函数(reward function)等，在下面所有形式化描述，×\times×表示笛卡尔积。
- 状态S，有限集合{s1,s2,...,sN}\{s^1,s^2,...,s^N\}{s1,s2,...,sN}，即∣S∣=N|S|=N∣S∣=N。对于建模的问题来说，状态是所有信息中唯一的特征。
- 动作A，有限集合{a1,a2,...,aN}\{a^1,a^2,...,a^N\}{a1,a2,...,aN}，即∣A∣=N|A|=N∣A∣=N。能够用于某个状态s∈Ss \in Ss∈S的集合表示为A(s)A(s)A(s)，其中A(s)⊆AA(s) \subseteq AA(s)⊆A。先决条件函数(precondition funcion):S×A→{true,false}: S\times A\rightarrow\{true, false\}:S×A→{true,false}可以表达动作a∈Aa\in Aa∈A能否运用在状态s∈Ss\in Ss∈S。
- 转换函数T，可以通过如下方式定义：S×A×S→[0,1]S\times A \times S \rightarrow[0,1]S×A×S→[0,1]，即它是从(S,A,S)(S,A,S)(S,A,S)三元组映射到一个概率的函数，其概率表示为T(s,a,s′)T(s, a, s^{'})T(s,a,s′)，表示，从状态sss转换到状态s′s{'}s′的概率，其值需要满足0≤T(s,a,s′)≤10\leq T(s, a, s^{'})\leq 10≤T(s,a,s′)≤1且∑s∈s′T(s,a,s′)=1\sum_{s\in s^{'}}T(s, a, s^{'})=1∑s∈s′T(s,a,s′)=1，即概率必须满足实际，否则无意义。 我们可以定义离散的全局时钟t=1,2,3...t=1,2,3...t=1,2,3...，然后使用sts_tst表示在时间t的状态。 如果一个系统的动作不依赖于之前的动作和历史状态，而仅仅取决于当前状态，那么该系统具有马尔科夫特性，即P(st+1∣st,at,st−1,at−1,...)=P(st+1∣st,at)=T(st,at,st+1)P(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},...)=P(s_{t+1}|s_t,a_t)=T(s_t,a_t,s_{t+1})P(st+1∣st,at,st−1,at−1,...)=P(st+1∣st,at)=T(st,at,st+1) 马尔科夫决策过程的核心思想是当前状态s提供了足够的信息来做最优决策，而之前的状态和动作是不重要的。换一种表述方法是，下一个状态的概率分布和同一个状态下当前动作的概率分布是相同的。
- 奖励函数R，可以定义为R:S→RR:S\rightarrow\mathbb{R}R:S→R，从状态中直接获取奖励；或者R:S×A→RR:S\times A\rightarrow\mathbb{R}R:S×A→R，在某状态执行某动作获得奖励；或者R:S×A×S→RR:S\times A \times S \rightarrow\mathbb{R}R:S×A×S→R，执行某个状态转换获得奖励。最后一种定义方式可以非常方便的应用于无模型算法(model free algorithm)，因此是广泛使用的定义方式。 奖励函数是马尔科夫决策过程最重要的部分，因为奖励隐式地定义了学习的目标(goal)。奖励函数给予了系统(即MDP)的前进方向。通常情况下，奖励函是也将非零的奖励分配给非目标的状态，这可以理解为为学习定义的子目标。
转换函数TTT和奖励函数RRR一起定义了马尔科夫决策过程的模型。马尔科夫决策过程经常被描绘成一个状态转换图，图的结点对应状态，有向边对应状态的转换。
马尔科夫决策过程可以建模几种不同类型的系统：
周期性任务有周期长度(episode of length)的概念，在这个概念中，学习的目标是将代理(agent)从开始状态转换到目标状态。对于每一个状态来说，初始状态分布I:S→[0,1]I: S\rightarrow[0,1]I:S→[0,1]，给出了当前系统在此状态下开始的概率。根据所执行的动作，从一个状态s开始，系统通过一系列的状态前进。在周期性任务中，有一个特定的子集G⊆SG\subseteq SG⊆S，这个子集表示过程结束时的目标状态区域，该区域通常包含一些特定的奖励。
此外，任务还可以进一步分为以下类型：
- 有限的固定范围的任务：任务的每个阶段包含固定数目的步骤。
- 未定义范围的任务：任务的每一个阶段都可以终止，但是阶段的长度可以是任意的。
- 无限范围的任务：无限任务包含无限的步骤，学习系统永不停止，通常被称为一个持续任务。
周期任务可以通过吸收状态(absorbing states)或者终止状态(terminal states)来建模。这是指每一个动作所处的状态都可以变换到一个概率为1，奖励为0的相同状态，即吸收状态。它可以被形式化的表示为：T(s,a,s′)=1T(s, a, s^{'})=1T(s,a,s′)=1和R(s,a,s′)R(s, a, s^{'})R(s,a,s′)=0。进入一个吸收状态时，进程将在一个新的启动状态下重新设置或者重新启动。周期性任务加上吸收状态，可以以这种方式用连续任务相同的框架优雅地进行模拟。
策略
给定一个MDP<S,A,T,R>MDP<S,A,T,R>MDP<S,A,T,R>，策略是一个可计算的函数，它为每一个状态s∈Ss\in Ss∈S和每一个动作a∈Aa\in Aa∈A提供输出。形式化地，一个确定性策略π\piπ是一个被定义为π:S→A\pi: S\rightarrow Aπ:S→A的函数，也可以定义一个随机性策略π:S×A→[0,1]\pi: S\times A \rightarrow [0,1]π:S×A→[0,1]，使得π(s,a)≥0\pi(s,a)\geq0π(s,a)≥0并且∑a∈Aπ(s,a)≥0\sum_{a\in A}\pi(s,a)\geq0∑a∈Aπ(s,a)≥0。
马尔科夫决策过程的应用方法如下： 首先，从初始状态分布III产生一个起始状态s0s_0s0。然后，策略建议的动作a0=π(s0)a_0=\pi (s_0)a0=π(s0)，而这个动作将被执行。基于状态转换函数TTT和奖励函数RRR，转换到状态s1s_1s1，那么概率为T(s0,a0,s1)T(s_0,a_0,s_1)T(s0,a0,s1)且奖励r0=R(s0,a0,s1)r_0=R(s_0,a_0,s_1)r0=R(s0,a0,s1)将被接收。重复这个过程，产生以下状态和动作: s0,a0,r0,s1,a1,r1,s2,a2,r2...s_0,a_0,r_0,s_1,a_1,r_1,s_2,a_2,r_2...s0,a0,r0,s1,a1,r1,s2,a2,r2...如果任务是周期性的，这个过程将结束在状态sgoals_{goal}sgoal，并从初始状态分布III中产生一个新的状态后重新启动。如果继续执行，该序列的状态可以无限期执行。 策略是代理(agent)的一部分，而代理(agent)的目的是控制环境，而环境是用马尔科夫决策过程建模的。一个固定的策略是在马尔科夫决策过程中推导出一个静态转换，而这个静态转换能够转换成马尔科夫系统<S′,T′><S^{'},T^{'}><S′,T′>，它满足如下条件：当π(s)=a\pi (s)=aπ(s)=a时，S′=SS^{'}=SS′=S和T′(s,s′)=T(s,a,s′)T^{'}(s,s^{'})=T(s,a,s^{'})T′(s,s′)=T(s,a,s′)。
最优准则和折扣
前面的两个小节我们定义了环境(MDP)，代理(agent)(控制元件，或策略)。在讨论最优算法之前，首先要界定什么是最优模型。有两种方式看到最优性：
- 代理(agent)实际在优化什么方面，它的目标是什么？
- 如何通过最优的方式优化目标。 第一个方面与奖励收集(gathering reward)有关；第二个方面与算法的效率和最优性有关。
马尔科夫决策过程中学习的目标是收集奖励。如果agent只关心即时奖励，一个简单的最优准则是优化E[rt]E[r_t]E[rt]。
有限时域(finite horizon)模型选取一个有限的长度为h的有限时域，并声明agent将优化该有限时域内的预期奖励。 E[∑t=0hrt](有限时域)E[\sum_{t=0}^{h}r_t] (有限时域)E[t=0∑hrt](有限时域) 这可以通过两种方法来实现：
- agent在第一步采取h步优化行为，在这之后采取(h-1)步优化行为，以此类推。
- agent始终采取h步最优行为，这称为滚动时域控制(receding-horizon control)。 有限时域模型的问题在于(最优)选择的时域长度h不总是已知的。
无限时域模型中，将考虑长期奖励，但是根据接收时间的远近将在时间较远时对接收到的奖励打折扣。为了实现这个，引入一个折扣因子γ\gammaγ，其中0≤γ<10 \leq \gamma < 10≤γ<1。 E[∑t=0∞γtrt](无限时域)E[\sum_{t=0}^{\infty}\gamma^tr_t](无限时域)E[t=0∑∞γtrt](无限时域) 在打折扣的条件下，后面接收到的奖励折扣的力度会比前面的大(即后面的奖励会小于前面的，越往后奖励越小)。除此之外，折扣因子确保即使时域是无限的情况下，获得奖励的总和也是有限的。在阶段性任务(有限的任务范围)中，不需要折扣因子，或者我们可以把折扣因子γ\gammaγ设置为1。如果设置折扣因子为0，则agent被称为是近视的，它只关心即时回报。折扣因子可以有多种解释方式：如利率，存活到下一步的概率，或者限定(奖励的)总和是有限的等等。
平均奖励模型中，我们最大化的是长期平均回报。这有时被称作增益优化策略，在取极限，折扣因子γ\gammaγ等于1时，无限时域模型等价于平均奖励模型。 limh→+∞E1h∑t=0hrt(平均奖励)\lim_{h\rightarrow+\infty}E\frac{1}{h}\sum^h_{t=0}r_t(平均奖励)h→+∞limEh1t=0∑hrt(平均奖励) 这种模型一个棘手的问题是，我们不能区分两个策略在起始阶段获得奖励的多少，这种初期奖励差异将会隐藏在长期平均水平之间。该问题可以使用偏置优化模型来解决，该模型的长期平均水平仍然是最优的，如果策略获得最初额外的奖励则该模型是首选。
第二种模型与最一般的学习过程的最优性相关。
价值函数和贝尔曼方程
价值函数，是一种连接最优准则和策略的方法。大多数针对MDP的学习算法通过学习价值函数来计算出最优策略。
一个价值函数表示在一个特定的状态(或是在该状态采取的某一动作的条件)下对一个agent好的程度的的估计。好的程度的概念由最优准则来表达。价值函数被特定的策略所定义。
在策略π\piπ下的状态SSS的值，表示为Vπ(s)V^{\pi}(s)Vπ(s)，代表收益的期望。无限的时域贴现模型(the infinite-horizon, discounted model)，可以用下面的式子表示： Vπ(s)=Eπ{∑k=0∞γkrt+k∣st=s}(1.1)V^{\pi}(s)=E_{\pi}\{\sum_{k=0}^{\infty}\gamma^kr_{t+k}|s_t=s\} (1.1)Vπ(s)=Eπ{k=0∑∞γkrt+k∣st=s}(1.1)
一个类似的状态-动作价值函数可以定义为Q:S×A→RQ: S \times A \rightarrow \mathbb{R}Q:S×A→R，即从状态s出发，采取动作a，此后遵循策略π\piπ的收益的期望。 Qπ(s,a)=Eπ{∑k=0∞γkrt+k∣st=s,at=a}(1.2)Q^{\pi}(s,a)=E_{\pi}\{\sum_{k=0}^{\infty}\gamma^kr_{t+k}|s_t=s,a_t=a\}(1.2)Qπ(s,a)=Eπ{k=0∑∞γkrt+k∣st=s,at=a}(1.2)
价值函数的一个基本属性是这些函数满足一定的递归性，因此可以根据贝尔曼方程递归地定义： Vπ(s)=Eπ{rt+γrt+γ2rt+...∣st=t}=Eπ{rt+γVπ(st+1)∣st=t}=∑s′T(s,π(s),s′)(R(s,a,s′)+γVπ(s′))(1.3)V^{\pi}(s)=E_{\pi}\{r_t+\gamma r_t+\gamma^2 r_t+...|s_t=t\}\\ =E_{\pi}\{r_t+\gamma V^{\pi}(s_{t+1)}|s_t=t\}\\ =\sum_{s'}T(s,\pi(s),s')(R(s,a,s')+\gamma V^{\pi}(s')) (1.3)Vπ(s)=Eπ{rt+γrt+γ2rt+...∣st=t}=Eπ{rt+γVπ(st+1)∣st=t}=s′∑T(s,π(s),s′)(R(s,a,s′)+γVπ(s′))(1.3) 以上的公式表示状态的期望值是定义在即时奖励和可能的随后被转换概率加权的状态值以及一个额外的折扣因子的条件下。VπV^{\pi}Vπ是这组方程的唯一解。需要强调的是，多个策略可以有相同的价值功能，但只要给定一个策略π\piπ，VπV^{\pi}Vπ就是独一无二的。
任何一个给定的马尔科夫决策过程，其目标均为找到一个最优策略，即获得最多的奖励的策略。这意味着对所有状态s∈Ss\in Ss∈S最大化公式(1.1)的价值函数。最优策略表示为π∗\pi^*π∗，并对所有的策略π\piπ，都满足Vπ∗≥VπV^{\pi^*}\geq V^{\pi}Vπ∗≥Vπ。
可以证明最优解决方案V∗=Vπ∗V^{*} = V^{\pi^*}V∗=Vπ∗满足如下方程： V∗(s)=maxa∈A∑s′∈ST(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))(1.4)V^{*}(s)=\max_{a\in A}\sum_{s'\in S}T(s,\pi(s),s')(R(s,a,s')+\gamma V^{\pi^*}(s'))(1.4)V∗(s)=a∈Amaxs′∈S∑T(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))(1.4) 上面这个方程被称作贝尔曼最优方程，一个最优策略下的状态值必须等于在该状态下的最优行为的预期回报。为了选择最优状态的价值函数V∗V^*V∗的最优行为，可以应用如下规则: π∗(s)=argmaxa∈A∑s′∈ST(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))(1.5)\pi^*(s)=\arg\max_{a\in A}\sum_{s'\in S}T(s,\pi(s),s')(R(s,a,s')+\gamma V^{\pi^*}(s'))(1.5)π∗(s)=arga∈Amaxs′∈S∑T(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))(1.5) 这种策略其实就是贪心策略，表示为πgreedy(V)\pi_{greedy}(V)πgreedy(V)，因为它贪婪的选择了价值函数V∗V^*V∗的最优行为。
类似的最优状态-动作值(optimal state-action value)可以计算为： Q∗(s,a)=∑s′T(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))(1.6)Q^*(s,a)=\sum_{s'}T(s,\pi(s),s')(R(s,a,s')+\gamma V^{\pi^*}(s'))(1.6)Q∗(s,a)=s′∑T(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))(1.6)
Q函数(即最优状态动作函数，博主补充)是非常有用的，他们在不同的选择之间使用不需要的转换函数就可以进行加权求和。不需要前向推导步骤来计算一个状态下的最优动作。这是为什么在无模型的方法中，如果TTT和RRR是未知的，学习的不是VVV函数，而是QQQ函数。
Q∗Q^*Q∗和V∗V^*V∗之间的关系是由一下公式确定的： Q∗(s,a)=∑s′∈ST(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))V∗(s)=maxaQ∗(s,a)(1.7)Q^*(s,a)=\sum_{s'\in S}T(s,\pi(s),s')(R(s,a,s')+\gamma V^{\pi^*}(s'))\\ V^*(s)=\max_aQ^*(s,a) (1.7)Q∗(s,a)=s′∈S∑T(s,π(s),s′)(R(s,a,s′)+γVπ∗(s′))V∗(s)=amaxQ∗(s,a)(1.7)
类似于公式(1.5)，现在最优行为可以简单地计算为： π∗(s)=argmaxaQ∗(s,a)(1.8)\pi^*(s)=\arg\max_aQ^*(s,a)(1.8)π∗(s)=argamaxQ∗(s,a)(1.8)
这也就是说，最优行为是基于可能产生的下一个状态所采取的行动，其有最高的预期效用。类似于公式(1.5)，可以在QQQ上定义一个贪婪策略πgreedy(Q)\pi_{greedy}(Q)πgreedy(Q)，与πgreedy(Q)\pi_{greedy}(Q)πgreedy(Q)不同的是，它(无模型的方法)不需要参考马尔科夫决策模型，有Q函数就够了。
参考文献
Reinforcement learning-State of Art，2012