本篇博客记录强化学习中的数学模型——Markov决策过程(Markov Decision Process，MDP)

Markov决策过程模型

离散时间Markov决策过程

在离散时间智能体/环境接口中，智能体和环境交互的时刻为{0,1,2,3...}，在时刻t依次发生以下事件：

• 智能体观察S_t∈S的环境，得到观测O_t∈O，其中S是状态空间，表示状态取值的综合；O是观测空间，表示观测取值的集合
• 智能体根据观测决定做出动作A_t∈A，其中A是动作集合
• 环境根据智能体的动作，给予智能体奖励R_t+1∈R，并进入下一步的状态S_t+1∈S，其中R是奖励空间，表示奖励取值的集合

一个时间离散化的智能体/环境接口可以用这样的轨道表示：

S₀,O₀,A₀,R₁,S₁,O₁,A₁,R₂,S₂,O₂,A₂,R₃...

对于回合制的任务，可能会有一个终止状态S_终止，当达到终止状态时，回合结束，不再有任何观测或动作，回合制任务的轨道形式：

S₀,O₀,A₀,R₁,S₁,O₁,A₁,R₂,S₂,O₂,A₂,R₃...S_T=S_终止

其中T是达到终止状态的步数
在时间离散化的智能体/环境接口中，如果智能体可以完全观察到环境的状态，则称环境是完全可观测的，令O_t=S_t，完全可观测任务的轨道可以简化为：

S₀,A₀,R₁,S₁,A₁,R₂,S₂,A₂,R₃...S_T=S_终止

定义在时间t，从状态S_t=s和动作A_t=a跳转到下一状态S_t+1=s'和奖励R_t+1=r的概率为：

\[Pr[S_{t+1}=s',R_{t+1}=r|S_t=s,A_t=a] \]

这样的概率假设认为奖励R_t+1和下一状态S_t+1仅仅依赖于当前的状态S_t和动作A_t，而不依赖于更早的状态和动作，这样的性质称为Markov性
Markov性是Markov决策模型对状态的额外约束，要求状态必须含有可能对未来产生影响的所有过去信息

如果状态空间、动作空间A、奖励空间R都是元素个数有限的集合，这样的Markov决策过程称为有限Markov决策过程(Finite Markov Decision Process,Finite MDP)

环境与动力

Markov决策过程的环境由动力刻画
对于有限Markov决策过程，可以定义函数p:S * R * S * A->[0,1]为Markov决策过程的动力：

\[p(s',r|s,a)=Pr[S_{t+1}=s',R_{t+1}=r|S_t=s,A_t=a] \]

• 状态转移概率：

\[p(s'|s,a)=Pr[S_{t+1}=s'|S_t=s,A_t=a]=\sum_{r∈R}p(s',r|s,a),s∈S,a∈A,s'∈S \]

• 给定"状态-动作"的期望奖励：

\[r(s,a)=E[R_{t+1}|S_t=s,A_t=a]=\sum_{r∈R}r\sum_{s'∈S}p(s',r|s,a),s∈S,a∈A \]

• 给定"状态-动作-下一状态"的期望奖励

\[r(s,a,s')=E[R_{t+1}|S_t=s,A_t=a,S_{t+1}=s']=\sum_{r∈R}\frac{p(s',r|s,a)}{p(s'|s,a)},s∈S,a∈A,s'∈S \]

智能体与策略

智能体根据观测决定其行为，在Markov决策过程中，定义策略为从状态到动作的转移概率
对于有限Markov决策过程，其策略π:S*A->[0,1]可定义为：

\[π(a|s)=Pr[A_t=a|S_t=s],s∈S,a∈A \]

如果某个策略π对于任意的s∈S，均存在一个a∈A，使得：

\[π(a'|s)=0,a'≠a \]

这样的策略称为确定性策略，这个策略可简记为π:S->A

奖励、回报与价值函数

强化学习的核心概念是奖励，强化学习的目标是最大化长期奖励

对于回合制任务，假设某一回合在第T步达到终止状态，则从步骤t(t回报G_t可定义为未来奖励之和：

\[G_t=R_{t+1}+R_{t+2}+...+R_T \]

在上式中，t是一个确定性的变量，而回合的步数T是一个随机变量，因此在G_t的定义式中，不仅每一项是随机变量，而且含有的项数也是随机变量

对于连续性任务，因为连续性的任务没有终止时间，所以G_t会包括t时刻以后所有的奖励信息，可是如果对未来的奖励信息简单求和，则未来奖励信息的总和往往是无穷大，因此需要引入折扣的概念，重新定义回报：

\[G_t=R_{t+1}+γR_{t+2}+γ^2R_{t+3}+...=\sum_{τ=0}^{+∞}γ^τR_{t+τ+1} \]

其中折扣因子γ∈[0,1]，折扣因子决定了如何在最近的奖励和未来的奖励间进行折中：

• 未来τ步后得到的1单位奖励相当于现在得到的γ^τ单位奖励
• 若指定γ=0，智能体会只考虑眼前利益，完全无视长远利益，就相当于贪心算法的效果
• 若指定γ=1，智能体会认为当前的1单位奖励和未来的1单位奖励是一样重要的
  对于连续性任务，一般设定为γ∈(0,1)，此时如果未来每一步的奖励有界，则回报也是有界的

基于回报的定义，对于给定的策略π，可以定义以下价值函数：

• 状态价值函数：v_π(s)表示从状态s开始采用策略π的预期回报：

\[v_π(s)=E_π[G_t|S_t=s] \]

• 动作价值函数：q_π(s,a)表示在状态s采取动作a后，采用策略π的预期回报：

\[q_π(s,a)=E_π[G_t|S_t=s,A_t=a] \]

终止状态之后没有动作，故一般定义v_π(s_终止)=0,q_π(s_终止,a)=0

Bellman期望方程

策略评估：求解给定策略的价值函数，Bellman期望方程常用来进行策略评估

Bellman期望方程刻画了状态价值函数和动作价值函数的关系，方程由两部分组成：

• 用t时刻的动作价值函数表示t时刻的状态价值函数：

\[v_π(s)=\sum_aπ(a|s)q_π(s,a) \]

推导过程如下所示：

• 用t+1时刻的状态价值函数表示t时刻的动作价值函数

\[ q_\pi(s,a)=r(s,a)=\gamma\sum_{s'}p(s'|s,a)v_\pi(s') =\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')],s∈S,a∈A \]

推导过程如下所示：

对于上式，可以用代入法消除其中一种价值函数，得到下面两种结果：

• 用状态价值函数表示状态价值函数

\[v_\pi(s)=\sum_a\pi(a|s)[r(s,a)+\gamma\sum_{s'}p(s'|s,a)v_\pi(s')],s∈S \]

• 用动作价值函数表示动作价值函数

\[q_\pi(s,a)=\gamma\sum_{s',r}p(s',r|s,a)[r+\sum_{a'}\pi(a'|s')q_\pi(s',a')],s∈S,a∈A \]

最优策略及其性质

价值函数实际上给出了策略的一个偏序关系：对于两个策略π和π^'，如果对于任意s∈S，都v_π(s)≤v_π'(s)，则称策略π小于等于π'，记作π≤π'

最优策略和最优价值函数

对一个动力而言，总是存在一个策略π，使得所有的策略都小于等于这个策略，这是策略π称为最优策略，最优策略的价值函数称为最优价值函数，包括以下两种形式：

• 最优状态价值函数

\[v_*(s)=\max_{\pi}v_{\pi}(s),s∈S \]

• 最优动作价值函数

\[q_*(s,a)=\max_{\pi}q_{\pi}(s,a),s∈S,a∈A \]

对于一个动力，可能存在多个最优策略，而这些最优策略总是有相同的价值函数

Bellman最优方程

最优价值函数具有一个重要性质——Bellman最优方程，Bellman最优方程可以用于求解最优价值函数

最优函数的性质：

\[ \pi_*(a|s)=\left\{ \begin{aligned} 1, & a = arg,\max_{a'∈A}q_*(s,a') \\ 0, & 其他 \end{aligned} \right. \]

将最优函数的性质代入Bellman期望方程，即可得到Bellman最优方程：

• 用最优动作价值函数表示最优状态价值函数

\[v_*(s)=\max_{a∈A}q_*(s,a),s∈S \]

• 用最优状态价值函数表示最优动作价值函数

\[q_*(s,a)=\gamma\sum_{s',r}p(s',r|s,a)[r+\sum_{a'}\pi(a'|s')q_\pi(s',a')],s∈S,a∈A \]