在人工智能领域,时序决策是考虑了世界是动态变化的算法,可以认为是一种循序渐进的决策理论,较早的决策会影响较晚的可用选择。例如我们考虑一个推箱子到指定区域的问题,从初始状态(start state)到目标状态(goal state)的一系列动作(action)都会影响到达目标状态的,我们可以把这一过程扩展到策略的概念,即在某个时隙(time slot)中应该做何种动作,这样这一策略的概念为:基于决策理论对于待优化的目标函数最优值(optimality)的计算,策略将所有的状态映射到一个最优的动作。
在上述时序决策提出的问题中,马尔科夫决策过程就是一种正式的框架。在这个模型中,环境通过一组状态和动作进行建模,可以用来执行以控制系统的状态。通过这种方式来控制系统以最大化模型的性能指标。这里说明在这个模型中的基本定义:
Random Variable:随机变量是概率论的基础,可以认为该变量是动态随机变化的,在强化学习中,两个随机变量是相互独立的。举例来说“海水是咸的”是随机变量\(X\)的值,“井水是甜的”是随机变量\(Y\)的值,两者显然相互独立。
Stochastic Process:举例来说,在股市当中,\(t\)时刻股票价格\(S_t\),\(S_t\)是随着时间\(t\)动态变化的,在这一过程中\(S_1\)、\(S_2\)、\(S_3\)、\(S_4\)、……、\(S_t\)变化十分复杂,是一种随机过程,可表示为\(\sum_{i=1}^t{S_t}\)。
Markov Chain:马尔科夫链和马尔科夫过程(Markov Process)指的是同一种东西。即当前时刻的状态仅和上一状态有关,公式表示为:$$P[S_{t+1}|S_t]=P[S_{t+1}|S_1,\cdots,S_t]$$马尔科夫链示意图如下:

State Space Model:状态空间模型可以认为是马尔科夫链加上一个观察值,即表示为\(Markov Chain+Observation\)。包括HMM,Kalman Filter,Particle Filter模型。之所以有观测独立假设,是因为此模型中引入了隐变量。而某时刻观测变量只和此时刻隐变量之间有关系。
Markov Reward Process:马尔科夫回报即:\(Markov Chain+Reward\)。在转移到下一个状态时,会得到一个回报,可通过该回报来评价状态转移。
Markov Decison Process:马尔科夫决策过程即:\(Markov Chain+Reward+Action\)在当前状态可选择一类动作执行,然后通过Reward来评价决策是否合理。马尔科夫链可用下图表示:
MDP可由一个四元数组\(\{\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R}\}\)表示。
状态\(\mathcal{S}\):当状态空间的规模为N,环境集合S可以定义为有限集合\(\{s^1,\cdots,s^N\}\),即\(|S|=N\)。
动作\(\mathcal{A}\):动作集合mathcal{A}通过有限集合\(\{a^1,\cdots,a^N\}\)来定义。其中,动作空间的大小为K,即\(|A|=K\)。动作可以用于控制系统的状态,能够用于某一特定状态\(s\in{S}\)的动作集合表示为\(A(s)\),其中\(A(s)\subseteq{A}\)。
转换函数\(\mathcal{T}\):通过将动作\(a\in{A}\)应用于状态\(s\in{S}\),基于可能的转换集合的概率分布,学习系统能够完成从当前状态s到新状态\(s‘\in{S}\)的转换。
回报方程\(\mathcal{R}\):回报方程指在一个状态中的奖励,或在一个状态中完成一个动作后的奖励。
转换矩阵也就是转换函数,即转换集合的概率分布。假设系统一共有N状态,表示为\(\mathcal{S}=\{s_1,s_2,\cdots,s_t,\cdots,s_N\}\),那么从\(s_1\)转换到\(s_2\)的概率可表示为\(T(s_1,s_2)\),即转换矩阵可表示为:
考虑动作\(\mathcal{A}\)和回报\(\mathcal{R}\)一个转换概率可表示为:$$P=(s‘,r|s,a) \buildrel\Delta\over= P_r[S_{t+1}=s‘,R_{t+1}=r|S_t=s,A_t=a]$$动态特性由以上这个概率函数可以表现。需要注意的是回报r是一个随机变量,因此状态转移函数并不等于转换概率。因此,状态转移函数与转换概率关系为:
\begin{equation}
T(s,a,s‘)=P(s‘|s,a)=\sum_{r\in{R}}{P(s‘,r|s,a)}\tag{2}
\end{equation}其中\(0 \le T(s,a,s‘) \le 1\),并且\(\sum T(s,a,s‘)=1\)。
什么是策略?在给定的一个马尔科夫决策过程\(<\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R}>\)中,我们有状态集合\(\mathcal{S}\)以及行为集合\(\mathcal{A}\),那么在给定的一个状态\(s\)中我们要做何种行为\(a\)就叫策略,即表示为:\(\pi:\mathcal{S}\longrightarrow\mathcal{A}\)。策略分两种:
确定性策略:在确定了状态后,只执行特定的动作。注意这个状态跟时间没有关系。比如在状态\(s\)我们只执行动作\(a\),表示为:\(a\buildrel\Delta\over= \pi(s)\)。
随机性策略:在确定了状态后,有多种动作可供选择,并且每种动作按照一定概率分布。表示为:\(\pi(a|s) \buildrel\Delta\over= P_r\{A_t=a|S_t=s\}\)。
如何衡量一个策略的好坏呢?我们在状态\(S_t\)做出动作\(A_t\),只要使得获得的回报函数\(R_{t+1}=r\)最大就行。然而这只考虑到下一个状态回报,并没有考虑到全局,这种方法称为贪心算法。
我们知道,评价策略的好坏就是通过回报(奖励函数)来评判。事实上,马尔科夫决策过程学习的目标就是收集回报,尽可能的让回报最大。一个简单的最优准则就是优化回报\(G_t=R_{t+1}+R_{t+2}+\cdots+R_{T}\),如果我们考虑长期回报,但是根据接收时间的远近将在未来受到打折。打个比方讲,张三伤害了李四,李四在第一天是十分痛苦的,但是久而久之这种痛苦可能会逐渐减弱。因此这里引入阻尼系数\(\gamma\),\(0\le \gamma <1\)。这样回报表示为:
\begin{equation}
G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots+\gamma^{h-1} R_{t+h}=\sum_{i=0}\gamma^i{R_{t+i+1},\quad r\in[0,1)}\tag{3}
\end{equation}然而,回报只能对应马尔科夫决策过程中的其中一条路径。系统根据不同的动作及回报会有多种状态转移路径,如图所示:
根据上图,我们知道,此图例中可以看到一共有9种转移可能,可以记为\(G_t^1\)、\(G_t^2\)、\(\cdots\)、\(G_t^9\),并不是单独的一个\(G_t\)。所以,我们就可以用这个9个可能的平均值来表示最终的衡量标准。而实际中由于可能性很多,通常通过蒙特卡罗采样来求平均值得到最终的函数值,也就是价值函数:
\begin{equation}
V^{\pi}(s)=\mathbb{E}_\pi [G_t|S_t=s]\tag{4}
\end{equation}
价值函数可以分为两种:
状态价值函数:
有一个自变量。
状态—动作价值函数:
这里引入了动作,指在某种状态下确定一个动作。状态价值函数和动作价值函数关系可表示为:
\begin{equation}
\begin{split}
V^{\pi}(s)&=\pi(a_1|s)Q^\pi(s,a_1)+\pi(a_2|s)Q^\pi(s,a_2)+\pi(a_3|s)Q^\pi(s,a_3)+\cdots \
&=\sum\limits_{a\in \mathcal{A}(s)}^\infty \pi(a|s) Q_{\pi}(s,a)
\end{split}\tag{7}
\end{equation}通过式子\((7)\)我们知道\(V^{\pi}(s)\)是\(Q_{\pi}(s,a)\)的加权平均值,对式子\((5)\)展开:
\begin{equation}
\begin{split}
Q^{\pi}(s,a) &= \sum_{r,s‘}P(s‘,r|s,a)[\sum\limits_{k = 0}^\infty\gamma^kR^{t+k}|S_t=s] \
&= \sum_{r,s‘}P(s‘,r|s,a)[R_t+\gamma R_{t+1}+\gamma^2 R_{t+2}+\cdots|S_t=s] \
&= \sum_{r,s‘}P(s‘,r|s,a)[r+\gamma V^\pi (s‘)]
\end{split}\tag{8}
\end{equation}将式\((8)\)代入式\((7)\)得到状态价值的贝尔曼期望方程:
\begin{equation}
V^{\pi}(s) = \sum\limits_{a\in \mathcal{A}(s)}^\infty \pi(a|s)\sum_{r,s‘}P(s‘,r|s,a){r+\gamma V^\pi (s‘)}\tag{9}
\end{equation}将式\((7)\)代入式\((8)\)得到状态-动作的贝尔曼期望方程:
\begin{equation}
Q^{\pi}(s,a) = \sum_{r,s‘}P(s‘,r|s,a){r+\gamma \sum\limits_{a‘\in \mathcal{A}(s‘)}^\infty \pi(a‘|s‘) Q_{\pi}(s‘,a‘)}\tag{10}
\end{equation}
式\((9)\)、式\((10)\)为贝尔曼期望方程。对于式\((9)\),\(V_\pi\)是这组方程的唯一解,对于多个策略可以有相同的价值功能,但对于给定的策略\(\pi\),\(V_\pi\)是独一无二的。对于任何给定的马尔科夫决策过程的目标是找到一个最优策略,即获得最多的回报(奖励)策略。这意味着对所有状态\(s \in \mathcal{S}\)最大化式\((5)\)。最优策略表示为\(\pi ^*\),设定:
这个表达式称为贝尔曼最优方程,一个最优策略下的状态值必须等于在该状态下的最优行为回报。为了选择了最优状态的价值函数\(V_*\)的最优行为,可以有以下规则:
\begin{equation}
\pi ^*(s) = \arg\max_\pi V_\pi(s) = \arg\max_\pi Q_\pi(s,a)\tag{12}
\end{equation}
那么有:
这里注意等式左右两边的概念,左边\(V^*(s)\)是个泛概念,无论你什么策略,该值就是最优价值函数。右边\(V_{\pi ^*}(s)\)是指在最优策略情况下取得的奖励值。
我们讨论\(V_{\pi ^*}(s)\)和\(Q_{\pi ^*}(s,a)\)之间的关系。根据前面所述,V函数是Q函数的一个加权平均,那么得到:
现在\(\pi ^*\)是一个最优策略,如果\(V_{\pi ^*}(s) < \max_a Q_{\pi ^*}(s,a)\)则表示V函数并没有达到最大值,策略\(\pi ^*\)还有提高的空间,这与它是最优策略矛盾,因此有:
据此,我们建立最优策略中\(s,s‘\)之间的关系:
这就是贝尔曼最优方程。
这部分是强化学习的基础知识,也可以了解对时序决策、随机优化的一些基本概念。定义了马尔科夫决策过程的策略、价值函数以及最优准则,那么怎么求解最优策略,是最为核心的问题,之后我再给大家讲解一些方法。
原文:https://www.cnblogs.com/souluki/p/13460639.html