———— 但远山长，云山乱，晓山青。

强化学习 (Reinforcement Learning)

本章开始讨论强化学习 (reinforcement learning) 和适应性控制 (adaptive control) 的一些知识。强化学习是一种区别于监督学习和非监督学习的机器学习算法，在一些涉及到控制的场景，尤其是机器人控制系统上，应用较为广泛。在监督学习算法中，模型通过训练学习会使一个输入数据的输出逐渐接近真实标签 (label)  ，这类算法要求训练数据  有一个明确定义的标签，即我们拿到这个输入数据后，希望得到一个什么样的结果。然而对于序列性的决策和控制问题，并不适合预先制定好数据集和标签再调用监督算法。控制系统都很强调闭环思路，而大部分监督学习算法都只是一个开环系统，不能构成反馈，这样控制效果肯定是不佳的。强化学习就通过一个奖励函数 (reward function) 来形成这样一个反馈控制效果。

强化学习的奖励函数用来告诉模型什么时候的输出是好的，什么时候是不好的。例如如果想要控制一个机器人向前走，当机器人系统的输出使其向前运动时，通过奖励函数告诉机器人做得好下次继续，当机器人后退时就告诉它不能这样做要求改正，直到其继续向前走，形成一种奖惩机制，于是强化学习的任务就是解决如何选择正确的动作才能使系统获得最大的奖励。

强化学习已经成功应用于直升机飞行，多足机器人行走，手机网络路由，市场策略选择，工厂控制，高效网页检索等场景，下面将从马尔科夫决策过程 (Markov decision processes) 开始介绍强化学习。

1. 马尔科夫决策过程 (Markov Decision Processes)

一个马尔科夫决策过程由一个五元组  组成，其中

•  是一个状态集合，比如一个直升机自主飞行时，  就可能是直升机所有可能出现的方位。
•  是动作集合，例如操纵直升机摇杆的所有方向。
•  是状态转移概率，对于任意状态和动作  ，  表示在状态  时采取动作  转移到下一状态的空间概率分布。
•  被称为折扣因子 (discount factor)。
•  被称为奖励函数 (reward function)，表示在一系列状态和动作下算法给予的奖励，有时奖励函数也可以只与状态有关。

马尔科夫决策动态过程如下：从初始状态  开始，采取动作  ，马尔科夫决策过程的状态会随机转移至  ，其中  ，然后采取另一个动作  ，转移至状态  ，依次类推，马尔科夫决策过程就可以表示为

遍历全序列状态  和动作  后，全部奖励为

如果只考虑状态对奖励函数的贡献，全部奖励就可以写作

强化学习的目标就是找到一组动作来最大化奖励

在时间步  会以因子  对奖励进行折扣，因此为了使期望收益最大化，我们应当尽可能早的累积正奖励，推迟负收益。例如在经济学应用中，奖励函数  可以看做是一段时间总的金钱收益，  存在的意义就是自然状态下货币贬值。

策略 (policy) 是指将状态  映射到动作  的函数  ，在状态  时，我们执行策略  得到动作  ，定义一个策略  的值函数

 即为从状态  开始，执行策略  选择动作所积累的折扣奖励函数的期望。

给定一个策略  其值函数满足贝尔曼等式 (Bellman equations)：

这表示从状态  起折扣奖励的期望总和为两部分，第一是位于状态  时的奖励  ，第二是未来的折扣奖励期望总和，也可以写作  ，这也是从状态  开始的折扣奖励期望总和，其中  服从分布  ，这也是在状态  执行策略  后的状态分布。

贝尔曼等式可以用于求解  ，尤其是，在一个有限状态的马尔科夫决策过程中，可以对每个状态  写出  （其中总的状态数  ），这给出包含  个变量的  个线性方程，则可以求解出每个状态的  。

定义最优值函数为

这在所有可能的策略中能获得折扣奖励的最大期望，关于最优值函数的贝尔曼等式为

这与公式 (6) 的含义大致相同。定义策略  如下：

策略  给出动作  使得公式 (8) 收益最大化。

对于任意策略  和状态  ，都有

这表示采用最优策略  可以获得最大收益  ，其中  表示针对所有状态  的最优策略，也就是无论马尔科夫决策过程的初始状态是什么，使用策略  总能获得最大收益。

2. 值迭代和策略迭代 (Value Iteration and Policy Iteration)

这部分会给出解决有限状态马尔科夫决策过程的两种算法，并且我们假设已知状态转移概率  和奖励函数  。

第一种算法是值迭代 (value iteration) 算法，对于每个状态  ，初始化  ，然后更新

这种算法可以被看做不断重复更新公式 (8) 的估计值函数。关于更新算法的内循环也有两种方式，第一种方式是对于每一步状态  计算一次新的值函数  ，并且将新值用于替换旧值，这种方式也称为同步 (synchronous) 更新；另一种异步 (asynchronous) 的方式是按某种顺序遍历状态，一次更新一个值。不论哪种方式，最后值函数  都将收敛于最优值  。

除了值迭代的方式，另外还有一种策略迭代 (policy iteration) 的方法。策略迭代算法的流程是随机初始化策略  ，然后按照以下方式更新

该内循环算法不断计算当前策略的值函数，然后使用当前值函数更新策略，更新的策略是关于值函数的贪婪 (greedy) 策略。内循环第一步值函数的求解方式如前，为含有  个变量的线性方程组。一般对于较小的马尔科夫决策过程，策略迭代更快，迭代次数较少；而对于较大状态空间，求解  相对较难，通常使用值迭代。

3. 马尔科夫决策过程模型学习

上述讨论都是在转移概率和奖励函数已知的条件下，然而在很多实际问题中，这些条件都是未知的，但是我们可以根据现有训练数据进行估计，而在马尔科夫决策过程中，  都是已知的。假设我们从实验中得到这样一个马尔科夫过程。

其中  表示实验  在时间  的状态，对应的动作为  ，每个过程都是有限的，在运行到某个时间点后就会停止。于是我们就能用极大似然估计法求出状态转移概率

如果比例是  ，即在状态  从未采取过动作  ，那我们就用  替代  ，这表示在所有可能的状态空间上是一个均匀分布。在实际操作中，有一种更高效的方式，就是将新的数据直接在旧数据上累加计算转移概率。

在学习出模型的状态转移概率等参数后，就可以用值迭代或策略迭代求解，找出最佳策略，将模型学习和值迭代结合在一起，就可以求解未知概率转移矩阵的马尔科夫决策过程的学习，先随机初始化策略  ，然后重复执行：将  执行多次得到实验数据，然后将数据累加更新得到状态转移概率  ，基于估计的状态转移概率和奖励函数应用值迭代算法，得到一个新的  的估计，再更新  为关于  的贪婪策略。

在采用值迭代的算法内循环时，如果每次都初始化  为上一次值迭代中求解的值，这样就能加快收敛。