强化学习笔记（2）-马尔科夫决策过程和动态规划

马尔科夫决策过程

在强化学习中，环境的是由马尔科夫决策过程表述的，当前的状态(state)可以完整地刻画决策过程。马尔科夫过程是一个无记忆地随机过程，在强化学习中表现为一串具有马尔科夫性质的随机状态序列$S_1, S_2, \cdots$

David Silver在课程中用了一个学生在课堂上的行为例子来解释马尔科夫决策过程，如下图所示。

图中的圆圈表示学生在课堂上可能处于的状态，箭头代表学生在每一个状态上可能所采取的行为，箭头旁的数字是转移概率。那么，agent在对这个环境进行观察或者学习的时候会进行采样，将环境中的每一个可能发生的过程采样成一个个Episodes，由于马尔科夫过程是离散的，所以Episode也由离散的采样状态序列构成。

对于这样的一个模型，状态知道了，行为知道了，而状态的转移概率可以看成当前个体的策略，那么，为了预测当前的策略到底好不好，agent需要对每一个状态进行遵循当前策略的奖励评估（也就是上一讲中的Prediction）。知道了当前策略所能带来的奖励，agent才能进一步地更新策略去或者最优策略（也就是上一讲地Control）。

Silver的课程中，奖励分为实时奖励（Reward）和长期奖励（Return）。

Reward function的数学定义如上图所示，它不是实时奖励，而是当t时刻处于某个状态所预测到的下一步能得到的实时奖励的数学期望，而学生到达某个状态所能获得的实时奖励如下图红色数字所示。按照这个定义，学生课堂行为模型中的reward function可以轻易的计算出来。

至于return，它的数学定义如下。return是个体处在某个状态到完成整个过程所能获得所有奖励总和。

可以注意到，公式中实时奖励的前面会有一个折扣因子。折扣因子的存在出于多方面的考虑，主要是因为没有一个完美的模型，未来越远，获得的奖励越不确定，并且要是个体一直处在在一个循环的状态，没有折扣因子，return将会无穷大。

确定了奖励信号，agent需要使用state value function来评估在当前策略下每个状态的好坏，介绍了return之后，state value function可以写成如下的表示形式：

$v(s) = \mathbb{E}[G_t|S_t=s]=\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})|S_t=s]$

以上是强化学习中将环境当作一个马尔科夫过程所需要的元素定义，通过Bellman方程，可以用矩阵的形式轻易的解出state value function的值。但是，这样计算的复杂度与状态个数的三次方成正比，对付小型的模型还好，遇上稍大一点的模型就要换种方法求解。目前有三种主要的迭代算法可以用来解决这个模型，分别是Dynamic Programming, Monte-Carlo evaluation 和 Temporal-Difference learning.

另外需要介绍的一个概念是Action-value function $q_\pi(s,a)$，它表示的是从状态s开始，遵循策略$\pi$，采取行为a后所获得的长期奖励的期望值，定义如下：

$q_\pi(s,a)=\mathbb{E}_\pi[G_t|S_t=s, A_t = a]$

Action-value function是对state value function的一个补充，在后面可以知道，这两个函数非常重要。

强化学习中的动态规划

动态规划是一种针对具有最优子结构和重叠子问题两个特性的最优化问题的解决方案。用简单的话来说，最优子结构的意思就是该问题的最优解所是由对应子问题的最优解得到的；重叠子问题即一个问题可以化分为一层一层的树状子问题，并且下层子问题的解在求解上层子问题的时候可以缓存起来重复使用。比如，马尔科夫决策过程中，state value function的求解问题可以用如下的树状图来表示，它满足最优子结构和重叠子问题的两个特性，利用Bellman方程可以进行迭代递归求解。

可以将下一个状态的state value function看成是当前状态state value function的子问题，那么状态s的函数值就可以由s的后续状态$s'$的函数值计算出来，这样每一个状态的state value function就只要被计算一次，并存储好，以后计算前面的状态函数值需要用到的时候直接调用就行。这就是动态规划的意义所在，

动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

明白了动态规划算法在强化学习中的应用，那么下面就基于这种方法来大致讲解一遍强化学习的过程，解释一下强化学习是怎样来获取最优策略的。

整个过程可以由上图表示，在学习算法的一开始，我们可以使用一个均匀分布的策略作为初始策略，接着，agent根据这个初始策略使用动态规划求解state value function或者action-value function，或者每一个状态的value function值之后，我们可以根据这些值进行策略更新。怎么更新策略呢，或者说，怎么让策略变得更好呢？有很多种方案，最简单的一个就是贪婪的思想，也就是将能让下一步状态的value function值最大的action的选取概率取最大，其余的舍弃。这样更新全部状态就得到了一个更好的策略。但是，经过一次更新往往是达不到最优策略的，必须经过再一次的评估、更新、评估、更新…，最终收敛为最优策略和最优value function。

我们来看一个例子，这是一个小游戏，名字叫做Grid world。

在棋盘上有16个格子，玩家要做的就是从棋盘上的任意一个格子中找到一条到达左上角或者右下角灰色格子的最短路线。我们设定状态为每一个格子的位置，灰色格子为最终状态，agent每走一步获得的实时奖励为-1，处于最终状态的时候会一直停留在该状态，实时奖励为0，agent遵循的行为策略是：向上下左右四个方向走出一步的概率均匀分布。

根据Bellman方程进行动态规划求解的过程和结果如下图所示：

评估时，第k+1次迭代的value function的值是根据第k次的值计算出来的，因为由重叠子问题的性质，使用动态规划在这个问题中的求解复杂度要比不使用动态规划小很多。最后当$k=\infty$时，value function的值收敛，根据此时的值利用贪婪的思想可以将策略一步更新为最优策略。

另外需要注意的是，当$k=3$的时候策略就可以一步更新为最优策略了，说明有的时候value function不必达到收敛为常数的情况，当收敛的范围控制在一定的程度之内也是可以接受的。这对于一些难以彻底收敛的问题来说是有益处的。

The end.

---

• ← Previous Post
• Next Post →