马尔可夫决策过程

背景

强化学习的最根本目的是在agent和环境的交互中最大化累计奖励。而多数情况下，环境状态并不是完全可观测的，无数学者经过探索，提出了一套可以解决绝大多数强化学习问题的框架，即马尔可夫决策过程（Markov Decision Process, MDP）。

• 马尔可夫性（Markov Property）
  在之前学习HMM也关注了这个重要的性质，即当前的状态只与前一个状态有关：

  $$P(s_{t+1}|s_t)=P(s_{t+1}|s_t,s_{t-1},\ldots,s_1)$$

• 马尔可夫过程（Markov Process）
  若过程中的每个状态都具有马尔科夫性，则这个过程具备马尔可夫性。具备了马尔科夫性的随机过程称为马尔可夫过程 （Markov Process），又称马尔可夫链 （Markov Chain）。马尔可夫由一个二元组决定$(S,P)$，$S$代表状态序列，$P$代表状态转移概率。

• 马尔可夫奖励过程（Markov Reward Process, MRP）
  马尔可夫奖励过程就是在马尔可夫过程的状态转移时加入了奖励（reward），由一个四元元组表示$(S,P,R,\gamma)$，其中$R$是奖励函数：$R_s=E[R_{t+1}|S_t=s]$，$\gamma$是折扣因子（discount factor）。现实中，往往我们的在一个状态下的动作带来的结果并不仅仅是即时的，而是会对未来若干个状态造成影响的。例如我们在高考结束后填报志愿，影响的不仅仅是我们去到了哪所大学，未来的所有状态所带来的奖励都与这个动作有关系，但是这种关系会随着时间的推移慢慢减弱，因此我们在MRP中定义一个概念累计回报（return）:

  $$G_t=R_{t+1}+\gamma R_{t+2}+\gamma ^2 R_{t+3}+\ldots+\gamma ^{T-1} R_T$$

  $\gamma$取值越接近1，代表“眼光”越长远，取值越接近0，代表越关注当下。
  由于回报是基于一个具体的状态序列的变量，而给定一个$S$和$P$后，实际的状态序列可能不同，这也造成从一个固定状态展开的回报不同，这时我们定义价值（value），状态的价值是该状态回报的期望：

  $$v(s)=E(G_t|St=s)$$

  改写上式：
  

继续化简可以得到：

$$v(s)=R_s+\gamma\sum_{s^\prime \in S}P_{ss^\prime}v(s^\prime)$$

上式称为马尔可夫奖励过程中的贝尔曼方程（Bellman Equation），它表示一个状态的价值由该状态的即时奖励以及后续状态价值按概率分布求和按一定的衰减比例联合组成。

---

马尔科夫决策过程

马尔可夫决策过程（Markov Dicision Process, MDP）就是在马尔可夫奖励过程中加入行为（action），可以由一个五元元组来表示$(S,P,R,A,\gamma)$，$A$是行为的有限集合，这时$P$和$R$表示的条件概率中条件都要加上$A=a$（即在特定状态下的动作）。在MDP中，奖励和状态转移概率均与行为直接相关，行为的选择是完全由人来决定的，但也只是唯一的一部分可以人为决定的，在做出行为后，状态的转移依旧满足一个概率分布。agent在给定状态下从行为集中选取一个行为的依据称为策略（policy）：

$$\pi=P(A_t=a|S_t=s)$$

对于不同的状态，个体依据同一个策略也可能产生不同的行为；对于同一个状态，个体依据相同的策略也可能产生不同的行为。策略描述的是个体的行为产生的机制，是不随状态变化而变化的，被认为是静态的。

价值函数

• 状态价值函数（State-Value Function）

  $$v_\pi (s)=E(G_t|S_t=s)$$

  指在MDP下，从当前状态s开始，遵循策略$\pi$所获得的回报的期望。

• 动作状态价值函数（Action-Value Function）

  $$q_\pi(s,a)=E(G_t|S_t=s,A_t=a)$$

  指在MDP下，遵循策略$\pi$，从当前状态s开始做出某一行为a，所得到的回报的期望。

在一个状态下可以选择不同的行为：

状态价值函数和行为状态价值函数之间的关系如下：

$$v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a)$$

同时，一个行为也有概率转到不同的状态：

行为状态价值函数与状态价值函数的关系：

$$q_\pi (s,a)=R_s^a+\gamma \sum_{s^\prime \in S}P_{ss^\prime}v_\pi(s^\prime)$$

将上述两式结合，就构成了贝尔曼期望方程（Bellman Expectation Equation）：

$$v_\pi(s)=\sum_{a\in A}\pi(a|s)[R_s^a+\gamma \sum_{s^\prime \in S}P_{ss^\prime}v_\pi(s^\prime)]$$ $$q_\pi(s,a)=R_s^a+\gamma\sum_{s^\prime\in S}P_{ss^\prime}\sum_{a^\prime \in A}\pi(a^\prime|s^\prime)q_\pi(s^\prime,a^\prime)$$

最优价值函数

为了寻找一种最佳的策略，即在任意状态下的价值都比其他策略的该状态下的价值大，我们引入了最优价值函数和最优策略。

• 最优状态价值函数（Optimal State-Value Function）：

  $$v_*(s)= \max\limits_{\pi}v_\pi(s)$$

• 最优行为状态价值函数（Optimal Action-Value Function）:

  $$q_*(s,a)=\max\limits_\pi q_\pi(s,a)$$

存在如下的结论：对于任何马尔科夫决策过程，存在一个最优策略，优于或至少不差于所有其它策略。最优策略可以通过最大化最优行为价值函数$q_*(s,a)$来获得：

这就是说最优策略在面对每一个状态时将总是选择能够带来最大最优行为价值的行为，即一旦确定$q_*(s,a)$就确定了最优策略。
一个状态的最优价值是该状态下所有行为对应的最优行为价值的最大值：

$$v_*(s)=\max\limits_a q_*(s,a)$$

同时，一个行为的即时奖励和后续的状态并不由人为决定，因此在状态$s$选择行为$a$的最优行为价值将不能使用最大化来表示（因为我们无法知道具体转移到了哪个状态）。一个行为的最优价值由两部分组成，一部分是执行该行为后环境给予的确定的即时奖励，另一部分则由所有后续可能状态的最优状态价值按发生概率求和乘以衰减系数得到：

$$q_*(s,a)=R_s^a+\gamma \sum_\limits{s^\prime \in S}P_{ss^\prime}^av_*(s^\prime)$$

总结来看，某状态的最优价值等同于该状态下所有的行为价值中最大者，某一行为的最优行为价值可以由该行为可能进入的所有后续状态的最优状态价值来计算得到。
将上述两式联立，可得贝尔曼最优方程（Bellman Optimality Equation）：

$$v_*(s)=\max\limits_a(R_s^a+\gamma \sum_\limits{s^\prime \in S}P_{ss^\prime}^av_*(s^\prime))$$ $$q_*(s,a)=R_s^a+\gamma \sum_\limits{s^\prime \in S}P_{ss^\prime}^a\max_\limits a q_*(s^\prime,a^\prime)$$

---

参考资料

1. DavidSilver深度强化学习算法第二讲
2. 《深入浅出强化学习：原理入门》