Category: ICT-Information and Communication Technology

前面的相关文章，介绍了基于价值函数的强化学习算法（MDP和Q-Learning），在强化学习中，除了基于值函数的方法，还有一支非常经典的方法，那就是基于策略（policy-based）的方法。这篇文章将向大家介绍相关的算法思想，不正确或需要修正的地方欢迎大家批评指正。 在前面介绍的Q-Learning算法中，会采用一定的随机策略去选择action（epsilon greedy），一开始会让Agent更偏向于探索Explore，并不是哪一个Action带来的Value最大就执行该Action，选择Action时具有一定的随机性，目的是为了覆盖更多的Action，尝试每一种可能性。等训练很多轮以后各种State下的各种Action基本尝试完以后，我们这时候会大幅降低探索的比例，尽量让Agent更偏向于利用Exploit，哪一个Action返回的Value最大，就选择哪一个Action。 在策略梯度中，Agent一般称为Actor，策略pi通常用一个神经网络来表示，一般神经网络的输出为动作的概率（如softmax）。智能体会自动的探索不同的状态和trajectory(通过随机采样的机制进行实现。如一个policy在某种状态下输出action1的概率为60%，输出action2的概率为40%，则智能体自然而然会更多采样到action1，但也会常采样到action2)。policy gradient还有”No more perceptual aliasing”和”Effective in high-dimensional action spaces“这样的优势， 从初始状态出发，到任务的结束，被称为一个完整的episode（剧集）。这样，一个有T个时刻的eposide，Actor不断与环境交互，形成如下的序列τ： 具体的公式推导可以参考引文1，最后的梯度求解公式如下： 关于其公式的推导可以参考引文1，这里就不做赘述。需要说明和强调的是 对代码有几处说明一下：1、loss为负值，求最小，即为正值最大化，2，采用了Mento Carlo采样的思想，每次训练数据基于一个episode，从开始状态直至完成done；3、当前的某个时刻的R为从当前到最后状态r的一个折扣和，具体可以参考链接7中的实现。 实验中用到了GYM，强化学习算法工具包，可以提供强化学习算法的模拟环境，从而为测试和验证强化学习算法提供了方便。 References

在之前的关于马尔可夫决策过程的相关文章中，价值函数一般是某一状态下后续执行行为序列（特定策略）所获得的价值期望。价值函数可以是状态价值函数或动作价值函数，状态价值函数通常用V(s)来表示，而动作价值函数一般用Q(s,a)来表示，其含义为在特定状态下采取动作a来表示后续的价值期望。其表示更加灵活（因为只有状态的价值函数是针对特定策略的，而Q函数多了a这个维度表达能力就更强了），在许多强化学习算法中，特别是基于动作的方法（如Q-learning和Deep Q-Networks），Q函数是中心概念。 下面是Q-learning算法的基本思路解释： Q-learning的Q值更新规则通常使用了贝尔曼方程的近似形式，即将当前状态的Q值更新为当前奖励加上未来最大Q值的折扣后的值。这样可以不断地迭代更新Q值，逐步逼近最优的Q函数，从而学习到最优的策略。Q-learning的算法流程伪代码如下图所示。 对上述公式的解释如下： 一般情况下，可以设置为LMS loss：其中error为下面的表达式。 其中，在实际训练中，为了保持训练网络的稳定性，在训练过程中用到了两个网络，具体的过程可以参考引文3。 Q-learning的深度学习版本为DQN，原理基本差不多，不过Q函数不再以表格来表示，而是用神经网络的结构来表示，这样可以建模状态数很多的情况。 References

马尔可夫决策过程是强化学习的基本的算法，一些强化学习的概念知识点都在马尔可夫决策过程中有体现。强化学习是决策智能实现的一大类算法的统称，在游戏，智能辅助决策等场景下也有很多成功的应用。 马尔可夫性是概率论里边的一种特性，描述系统当前的状态概率只与上一个状态有关，而与之前的状态无关（或者说由于上一个状态的存在，之前的状态不会直接影响到当前状态）。用公式表示为： 马尔可夫决策过程是对具有离散状态的环境下的决策行为序列进行优化的建模方法。在马尔可夫决策过程中，问题被建模为一个包含以下要素的数学结构： 我们通常称的策略（policy)指的是当前系统环境处于s的情况下，采取某种行为a去执行，这种根据状态去执行特定的行为称为策略，一个策略下的价值函数（value function）定义为： 其中s为起始状态，pi为策略，因为在状态s下执行策略pi后下一个状态是概率分布，因此上述公式是期望值。价值函数更有价值的公式为下面的贝尔曼方程。其为一种递归定义： 上述公式的最右边可以理解为在当前状态为s的情况下执行策略pi后到达状态s’（满足上述的转移概率）后的价值函数，因为是满足概率分布，所以在不同s‘下求得价值函数的期望值即为结果。最优价值函数即为获取价值最大的策略。这里只关心其贝尔曼方程的表达（因为其方便用程序来实现，后面链接会有相关示例代码去进一步加深理解）。 通过上述的价值函数和最优价值函数的递归定义，我们就可以通过迭代算法去找到最优价值函数，并同时能找到其对应的最优策略。这里介绍两种迭代算法来找出最优的策略，第一种为policy iteration，第二种为value iteration。policy iteration首先通过迭代算法找出最优价值函数，然后通过迭代找出最优策略，而value iteration则是直接在迭代找出最优价值函数的过程中同时将最优策略的逻辑一并耦合在一起。 在这里有一个简单的演示示例，为一行五个格子对应五个状态，可以想象成一个五个格子的魔方，只有一个方块，其余为空格，方块可以向左或向右移动，目标是移动到中间的格子上。我们怎么去通过上述的迭代方法找出最优策略（在每一个状态下执行向左或向右行为为最优？）在这里需要注意几个关键的变量的定义，状态，当前状态价值以及状态转移矩阵。可以参考代码链接及里边的代码注解。 ai/samples/RL/MDP at master · kindlytree/ai (github.com)。 上述MDP的最优策略是在状态当前价值和状态转移矩阵已知的情况下的最优策略求解，实际过程中这些并不是已知的。这里也简要介绍一下MDP在状态转移矩阵未知情况下的求解方法，其也是基于迭代贪婪的思想，从一个随机的策略开始，然后逐步迭代找到更好的策略，在每一个中间策略迭代的开始，要做一些self play，积累一些数据，然后通过value iteration去找到更好的策略，流程伪代码如下所示：