迷雾探险3 | 强化学习入门
看完《迷雾探险2》的深度学习入门，又发现了一些不错的文章：
通俗易懂的深度学习发展介绍：从最基本的神经网络算法（单个神经元模型的提出，到两层和三层的简单神经网络，到BP算法，到深度神经网络CNN）讲到增强学习
增强学习系列之（一）：增强学习介绍：从动态规划算法和PageRank算法（和增强学习很像）讲到增强学习算法。
增强学习系列之（二）：实现一个简单的增强学习的例子：Q-Learning算法+epsilon_greedy策略+tensorflow训练神经网络==>Deep Q Learning
增强学习系列之（三）：实现一个打砖块的游戏：在openai的gym里面，针对breakout这款游戏的v3版本，实现AI打游戏。
强化学习的定义和通俗理解
1.定义
假定一个智能体(agent),在一个未知的环境中(当前状态state)，采取了一个行动(action),然后收获了一个回报(return)，并进入了下一个状态。最终目的是求解一个策略让 agent的回报最大化。
RL系统的概念图.png
增强学习当中经常用到的术语：
- agent，是指训练当中的个体，就是我们训练的算法和参数的集合
- environment，是指agent所处的环境
- episode，是指一个完整的训练的阶段。从一次训练开始，到这次训练成功或者失败结束，是一个episode
- step，是指一个episode当中的操作，每采取一次操作，就是一个step
- state，是指agent在每个时刻所面临的状态
- action，是指采取的那个操作究竟是什么
- value，是指在这个时刻，我所能采取的各个动作，所具有的价值
2. 强化学习最基础的解法：MPD（马尔可夫决策过程）
一个马尔可夫决策过程由五元组组成：M = (S, A, Psa, γ, R)
- S：表示状态集（states）
- A：表示一系列动作（actions）
- Psa：表示状态转移概率。表示的是在当前s ∈ S状态下，经过a ∈ A作用后，会转移到的其他状态的概率分布情况。比如，在状态s下执行动作a，转移到s'的概率可以表示为p(s'|s,a)。
- γ：（dicount factor）：表示阻尼系数[0,1)
- R：S x A → R，表示回报函数（reward function）
如果回报r是根据状态s和动作a得到的，则MDP还可以表示成下图：
3. 值函数
上面我们给出了MDP的定义，作为一个智能体（agent），当它在决定下一步应该走什么时，最简单的方式就是看下Reward函数的值是多少，即比较走不同动作的回报，从而做出决定。但是就像下棋的时候，我们每走一步都会向后考虑，所谓“走一步看三步”，所以这里我们只看一步即一次Reward函数是不够的，这就引出了值函数（Value Function）也叫折算累积回报（discounted cumulative reward）
3.1 状态值函数（state value function）
当我们遵循某个策略π，我们将值函数定义如下，对于状态序列中的每下一个状态，我们都设置一个衰减系数γ：
我们将上面的式子写作递推的样子如下：
另外当策略π，在状态s时，我们可以确定唯一的动作a，但是s经过动作a会进入哪个状态是不唯一的，比如同样是掷骰子操作，可能得到的状态有6种，那么利用Bellman等式我们便可以得到下面的公式：
再根据我们最初增强学习的目的，我们便可以得出，求V的目的就是想找到一个当前状态s下，最优的行动策略π，表示如下：
通俗的讲就是说，我需要判断一下当前的这个状态的价值是多少，从而让我可以选择最大化价值的那个状态来进行操作。当前状态的价值，就是之后的状态的价值的叠加，只不过越往后，噪声越大，就需要让他们的权重减小。而后面的所有状态的价值和，又可以写成下一个状态的价值。当前状态的reward我们是可以直接获得的，所以我们只需要计算下一个状态的权值函数就可以了
3.2 动作值函数（action value function）
上面我们的值函数的只与状态s有关，如果与状态s和动作a都有关，便称为动作值函数，即所谓的Q函数，如下：
从上式我们可以看出，我们不仅仅依赖状态s和策略π，并且还依赖于动作a。
关于MDP的求解主要分为值迭代和策略迭代，分别站在不同的角度对MDP进行求解，这里我们不在赘述，网上有很多相关资料。下面我们简单阐述下动作值函数的值迭代求解方式，即所谓的Q-learning
4. Q-learning
Q学习的基本迭代公式如下：
从公式中我们也可以看出它是一种值迭代方式，因为我们每次更新的是Q函数的值，而非策略。简单起见，整理一个简单的例子加以说明。
详细的分析可以参考：Q-learning的一个极简的例子
假设我们有这样一个房间：
我们的目的是训练一个机器人，使得它在图中的任意一个房间都能够到达房间外。
并得到reward矩阵，那么机器人走到这个房间之后，就知道了，它需要走到相邻的房间，才能走到最后的目标房间，所以相邻的房间也被赋予了权重。 ：
通过迭代，初始点也就有了权重。这个时候机器人就很省心了，只要向当前节点周围分值最高的点走过去就可以了。通过一下过程的迭代我们最终得出了我们的结果Q矩阵
可以看出，我们的机器人现在无论在哪个房间，都可以利用我们的Q矩阵顺利的走到屋外。
总结一下上面这个例子：增强学习的特征，就是从现有的状态出发，不断的优化自己的策略
5. 基于NEXT算法的马里奥AI游戏机器人
- NEXT算法（增强拓扑的进化神经网络，Evolving Neural Networks through Augmenting Topologies）它不仅会训练和修改网络的权值，同时会修改网络的拓扑结构，包括新增节点和删除节点等操作。
NEAT算法几个核心的概念是：
- 基因：网络中的连接
- 基因组：基因的集合
- 物种：一批具有相似性基因组的集合
- Fitness：有点类似于增强学习中的reward函数
- generation：进行一组训练的基因组集合，每一代训练结束后，会根据fitness淘汰基因组，并且通过无性繁殖和有性繁殖来新增新的基因组
- 基因变异：发生在新生成基因组的过程中，可能会出现改变网络的权重，增加突出连接或者神经元，也有可能禁用突触或者启用突触
利用NEAT算法实现马里奥的只能通关的基本思想便是，利用上面NEAT算法的基本观点，从游戏内存中获取实时的游戏数据，判断马里奥是否死忙、计算Fitness值、判断马里奥是否通关等，从而将这些作为神经网络的输入，最后输出对马里奥的操作，包括上下左右跳跃等操作，如下图：
大多数该算法实现马里奥的智能通关都依赖于模拟器，运用lua语言编写相应脚本，获取游戏数据并操作马里奥，真实例子见NeuroEvolution with MarI/O。
马里奥实现效果图
6. 基于Deep Reinforcement Learning的马里奥AI实现
NEAT算法是相对提出较早的算法，在2013年大名鼎鼎的DeepMind提出了一种深度增强学习的算法，该算法主要结合了CNN和Q-Learning两种算法，DeepMind的研究人员将该算法应用在Atari游戏机中的多种小游戏中进行AI通关。
其基本算法核心便是我们之前介绍的CNN和增强学习的Q-Learning，游戏智能通关的基本流程如下图：
利用CNN来识别游戏总马里奥的状态，并利用增强学习算法做出动作选择，然后根据新的返回状态和历史状态来计算reward函数从而反馈给Q函数进行迭代，不断的训练直到游戏能够通关。研究人员在训练了一个游戏后，将相同的参数用在别的游戏中发现也是适用的，说明该算法具有一定的普遍性。下图反映了一个学习的过程
而同样的方法，将DRL应用在马里奥上，github上有一个开源的实现方式：aleju/mario-ai，其最终的实现效果图如下：
在CNN识别过程中，每4帧图像，才会进行一次CNN识别，这是识别速率的问题，图中曲线反映了直接回报函数和简介回报函数。
7. 增强学习常用策略：
-
蒙特卡洛方法：暴力遍历所有episode
简单而言，蒙特卡洛方法就是对这个策略所有可能的结果求平均。我们向前走了以后，再做一个action，根据这个式子，直到episode结束，求出收益的和，就是向前走这个动作的一个采样。我们再不断地在这个状态采样，然后来求平均。等到采样变得非常非常多的时候，我们的统计值就接近期望值了。所以蒙特卡洛方法是一个非常暴力，非常直观的方法。 -
动态规划方法：在有向无环图结构的问题中可用
这个其实就类似于我们在开篇的那个例子里面提到的。我们要确定向前走的这个动作的收益，那么就需要将它所有的子问题先全都计算完，然后取最大值，就是它的收益了。这个方法的好处就是效率高，遍历一遍就可以了；而缺点也很明显，需要子结构问题是一个有向无环图。 -
Temporal Difference（时间差分）
（1）时间差分，简称TD，是对蒙特卡洛方法的一种简化，也是在实际中应用最多的一种算法。
（2）同样是要计算向前走的这个行为的价值的期望值，那么它就等于向前走了到达的那个状态的reward，加上它再转移到后继状态的期望值。有人会说这不就递归下去就是遍历了吗？不是，我们就观测前面一个状态，剩下的价值我们不去真的计算了，而是用神经网络来估算。这样我们不需要计算就可以得到它的价值了。这就是TD算法里面最简单的TD(0)算法。
8. 结合神经网络的增强学习——DQN
结合神经网络来对state和reward进行估算：很神奇的居然能收敛。
（1）可以把神经网络当成一个黑盒，输入是一个状态，输出是这个状态的价值。
（2）整个系统在运作过程中，通过现有的策略，产生了一些数据，获得的这些数据，在计算Reward值的时候会有所修正。然后我们用修正的值和状态，作为神经网络进行输入，再进行训练。最后的结果显示，这样做是可以收敛的，牛逼啊！
结合神经网络的增强学习
- 一个有意思的问题：使用神经网络来预测value，怎么评估神经网络预测的对不对呢，换个问法，如何决定下一个步骤的value，一个非常简单的策略是epsilon-greedy。
- 简单介绍一下epsilon-greedy，我们设置一个阈值,epsilon-boundary，比如说初始值是0.8，意思就是我们现在选择action的时候，80%的可能性是随机地从动作集中选择一个动作，20%的可能性是通过神经网络计算每个动作的收益，然后选最大的那一个。但是随着学习过程推进，我们的epsilon-boundary要越来越低，随机选择的次数要越来越少，到最后几乎不做随机的选择。
- 另外一个问题：如何跟神经网络相结合，可以看这篇博文的DNQ ：Q值神经网络化，讲述了如何用一个深度神经网络来表示一个近似输出reward的function。神经网络的训练是一个最优化问题，最优化一个损失函数loss function，也就是标签和网络输出的偏差，目标是让损失函数最小化。利用Q-Learning算法为Q网络提供标签的样本。然后通过反向传播使用梯度下降的方法来更新神经网络的参数。整个算法的流程差不多就是：首先反复随机action试验，然后存储数据。接下来数据存到一定程度，就每次随机采用数据，进行梯度下降！
9. 不同于DQN的Policy Gradient
-
概念：策略网络Policy Network：就是一个神经网络，输入是状态，输出直接就是动作（不是Q值）。a = π(s, θ) 或者概率Pa = π(a|s, θ)
-
为什么：我们已经知道DQN是一个基于价值value的方法。换句话说就是通过计算每一个状态动作的价值，然后选择价值最大的动作执行。这是一种间接的做法。那么，更直接的做法是什么？【能不能直接更新策略网络Policy Network呢？】
-
概率输出的问题。对于DQN来说，本质上是一个接近于确定性输出的算法。至多就是采用ε-greedy（ε-贪心）进行探索。但是有很多时候，在某一个特定状态下，很多动作的选择可能都是可以的。比如说我有20块钱去买饭。那么不管我买的是蛋炒饭还是土豆肉片盖码饭，结果都是一样的填饱肚子。因此，采用输出概率会更通用一些。而DQN并不能输出动作的概率，所以采用Policy Network是一个更好的办法。
-
目标函数。对于策略网络，目标函数其实是比较容易给定的，就是所有带衰减reward的累加期望
-
构造一个损失函数如下：
-
如何理解Policy Gradient的损失函数：对于AlphaGo而言，f(s,a)就是最后的结果。也就是一盘棋中，如果这盘棋赢了，那么这盘棋下的每一步都是认为是好的，如果输了，那么都认为是不好的。好的f(s,a)就是1，不好的就-1。所以在这里，如果a被认为是好的，那么目标就是最大化这个好的动作的概率，反之亦然。
10. 结合DQN和Policy Gradient的Actor Critic
- 一句话总结AC：结合了 Policy Gradient (Actor) 和 Function Approximation (Critic) 的方法. Actor 基于概率选行为, Critic 基于 Actor 的行为评判行为的得分, Actor 根据 Critic 的评分修改选行为的概率.
- 优势: 可以进行单步更新, 比传统的 Policy Gradient 要快（回合结束更新）.
- 劣势: 取决于 Critic 的价值判断, 但是 Critic 难收敛, 再加上 Actor 的更新, 就更难收敛. 为了解决收敛问题, Google Deepmind 提出了 Actor Critic 升级版 Deep Deterministic Policy Gradient. 后者融合了 DQN 的优势, 解决了收敛难的问题.
-
简单点说：Actor 在运用 Policy Gradient 的方法进行 Gradient ascent 的时候, 由 Critic 来告诉他, 这次的 Gradient ascent 是不是一次正确的 ascent, 如果这次的得分不好, 那么就不要 ascent 那么多.
11.DDPG（Deep Deterministic Policy Gradient）
-
一句话总结：Google DeepMind 提出的一种使用 Actor Critic 结构, 但是输出的不是行为的概率, 而是具体的行为, 用于连续动作 (continuous action) 的预测. DDPG 结合了之前获得成功的 DQN 结构（让计算机学会玩游戏）, 提高了 Actor Critic （让 Policy gradient 单步更新）的稳定性和收敛性.
- 基于策略 Policy 的神经网络+基于价值 Value 的神经网络：
a. Policy Gradient
（1）估计网络：输出实时动作，供actor在显示中实行，
（2）现实网络：用来实时更新价值网络系统的（action+state）
b. Value-Based
（1）现实网络：拿着动作实现网络的（action+state）加以分析
（2）估计网络：拿着真实的actor动作作为输入 - 在实际运用中, DDPG 的这种做法的确带来了更有效的学习过程.
12. A3C（Asynchronous Advantage Actor-Critic）
- 背景：目前的计算机多半是有双核, 4核, 甚至 6核, 8核. 一般的学习方法, 我们只能让机器人在一个核上面玩耍. 但是如果使用 A3C 的方法, 我们可以给他们安排去不同的核, 并行运算. 实验结果就是, 这样的计算方式往往比传统的方式快上好多倍.
- 一句话概括A3C：Google DeepMind 提出的一种解决 Actor-Critic 不收敛问题的算法. 它会创建多个并行的环境, 让多个拥有副结构的 agent 同时在这些并行环境上更新主结构中的参数. 并行中的 agent 们互不干扰, 而主结构的参数更新受到副结构提交更新的不连续性干扰, 所以更新的相关性被降低, 收敛性提高.
9-12节来源：强化学习入门简单实例 DQN
