强化学习数学原理
上面的视频讲的很好。但为了更好的理解，你应该知道“为什么需要这些算法，各自解决了什么问题”。
作者不喜欢背公式(除了一些基础公式)，简单的可以轻松推导，复杂的记了但是用不到、很快就忘了。所以通过本文对知识点进行梳理，不带任何公式，只说明“它在干什么”，且不保证内容正确性。
知识线梳理
马尔科夫决策过程
你需要一个模型解决一些问题，于是想到了马尔科夫决策过程(MDP, Markov desicion process)。
它包含五个参数：(S, A, Pi, P, R)，分别表示状态、行为(行动)、策略、状态转移、奖励。
举个例子：
- 现在的状态是：存在A和B两个人，A骂了B、B很生气。
- 有两种行动可以选择：B忍气吞声或B打A一拳。
- B有50%概率忍气吞声、50%概率打A，这就是策略。
- B忍气吞声则A安然无恙；B打了A则A有40%概率受伤、30%死亡、30%安然无恙，这就是状态转移。
- B不动手则不加分；如果B打了A且A没死，则加10分；如果B把A打死了，则减50分，这就是奖励。
本文后续方法讲解，可能直接用“点/位置“代指“状态”，“走”代指采取行动。
此模型并非万能，比如它不会记录你是怎么走到当前位置的，但已经足够解决许多“小问题”。
状态值与行动值
如果从某个状态出发，最多N次行为后就会停下，那么我们可以计算出从此状态出发可能获得的最大奖励和、平均奖励和，这称为状态值(State Value)。注意每个状态可能有多种行为，所以也可以计算出采取指定行为后可能获得的最大奖励和、平均奖励和，称为行动值(Action Value)。
如果停不下来呢？可以加个折扣系数k(0<=k<=1)，最终奖励的计算改为”R1 + R2 * k + R3 * k^2 + …”，由于单步奖励R必然有最大值，参考等比数列知识，此最终奖励应当收敛，也能得到状态值和行动值。
贝尔曼公式
我们可以通过状态值和行动值衡量每个状态和行为的好坏了，但是如何计算它们呢？
可以想到 “状态值 = 一次行动的奖励 + 下一个状态值”，“行动值 = 指定行动的奖励 + 下一个状态值”。
采取什么行动是随机的，依据策略Pi，比如50%概率选行动1、50%概率选行动2。下一个状态也是随机的，依据状态转移参数P，比如采取行动1后有50%概率变为状态1、50%概率变为状态2。
如果我们计算的是期望值，就得到了贝尔曼公式(Bellman Equation)。如果计算的是最大值（人为指定策略，一直选最优行动，但状态转移依然随机），就得到了贝尔曼最优公式(Bellman Optimality Equation)。
值迭代与策略迭代
现在问题变难了，我们不知道模型的“策略”了！！我们需要通过剩下的四个参数（状态、行为、状态转移、回报）计算出一个策略，以及此策略下的状态值和行动值。
注意：我们需要求的不一定是最优策略，但下面以最优策略为例。
最优策略和最优状态值/行动值是等价的，因为采取最优策略就会得到最优状态值/行动值，每次都使用行动值最大的行动就得到了最优策略。
我们可以随机指定一个策略，计算出状态值。然后根据状态值更新策略，再用新策略更新状态值，反复迭代。注意每次我们都采取了更好的策略，所以状态值只会一直增加直到趋于稳定，策略自身也趋于稳定。
如初始指定(赋予随机值)的是策略，就是策略迭代；初始指定的是状态值，就是值迭代。
我们可以在单次迭代造成的差异足够小时停止，但这种算法每次迭代都要计算一遍差异。我们可以直接指定迭代的次数，这就是截断迭代。
蒙特卡洛方法
现在问题又变难了，我们连模型的“奖励”都不知道了。好消息是，我们知道几个特殊点的状态值。
由于不知道奖励参数，我们直接认为当前状态的状态值是下一个状态的k倍，k是折扣系数。这样我们一直往状态值增大的方向走，就能达到“终点”，也就是那几个已知状态值的点。
可以想到使用动态规范的方式，从“终点”向外扩散，即可推出所有点的状态值。
如果再特殊一点，虽然我们确实有“终点”，但是不知道“终点”在哪呢？那就可以使用记忆化搜索的方式，从一个点出发进行搜索(比如DFS/BFS)，达到一个终点后，在回溯时计算出路径上的状态值。这就是蒙特卡洛基本方法(MC Basic)。
注意由于搜索路径并非最优，我们得到的状态值也不一定是最优的，依然需要一个迭代优化的过程。
此方法有一个问题，我们只能得到那些路径上的状态值。如果有些状态距离出发点很远，即使多次随机搜索，也可能走不到或者很难被更新。如果我们要求从所有状态出发并进行搜索，就得到了 MC Exploring Starts 方法（可能翻译为“蒙特卡洛全探索”？），保证所有的状态都会被更新。
如果我们搜索时找到了已有状态值的点，是直接回溯还是继续搜索？上面提到了搜索路径并非最优，已有的记录值很可能需要迭代优化，直接回溯就相当于放弃了优化。继续搜索又可能造成浪费，因为它可能已经最优了（尤其在迭代的后期）！我们可以指定一个概率ε，每次有ε的概率继续搜索且方向随机，剩下1-ε的概率直接回溯。这就是 MC ε-Greedy 方法(可能翻译为“蒙特卡洛概率贪心”？)。
时序差分方法
蒙特卡洛方法有一个问题，我们必须一直搜索，直到找到有状态值的点。如果问题超级复杂，搜索一直搜不到怎么办？如果使用DFS这样的递归函数进行搜索，不就很容易栈溢出？
一个好方法是，我们按轮次迭代，每轮更新每个状态，每次更新只看后续k个状态值。
如果k为1，每次更新只看下一个状态。可以想象，第一轮迭代后，距离“终点”步数为1的点都被更新了；第二轮行动后，距离终点步数<=2的点都被更新了。这样一直循环到最后，也能获得正确的状态值。
如果k=1，称为Sarsa方法。如果k=n，称为n-step Sarsa方法。如果k=+∞，就是蒙特卡洛方法。
需要注意的是我们没有策略，如何根据下一个状态值更新当前状态值是不确定的。你可以使用上面提到的“策略/值”迭代生成策略，也可以直接取“最大状态值”进行更新。每次更新都取“最大状态值”，就称为 Q-Learning 算法。
注意“策略+值”循环迭代得到的“策略”往往是概率分布的形式，各种行为都有一定的概率。直接取最大值，相当于只进行最佳行为，只有一个行为的概率是1、其他行为的概率都为0。这两种算法有不同的用处。
策略梯度方法
注意到 Q-Learn 算法得到的是“最大状态值”，而我们需要的是最优策略。
通过最优状态值得到最优策略并不是O(1)复杂度的，因为我们需要遍历所有“行动”和可能的“下一个状态”，计算出“行动值”，然后挑选最大行动值。即使记录的是行动值，也需要遍历一遍才能得到最大行动值。
我们当然可以先计算状态值，最后通过状态值一次性计算出策略。但能不能直接在迭代时就使用策略而不是状态值呢？答案是可以的，这就是“策略梯度方法”。
策略梯度方法的核心思想是“直接通过优化策略来提升长期奖励的期望值”。
对称我们定义一个目标函数J，它的参数是策略，表示了当前策略下的的状态值的平均数。我们需要最优策略，就是要最大化状态值，也就是最大化目标函数J，就可以使用梯度上升方法。
这个目标函数的梯度是本节最复杂的内容，建议直接看数学原理的视频。
需要注意一点，此方法只记录策略而没有状态值和行动值。但是J计算的是平均状态值，计算梯度时需要用到行动值，只能使用类似蒙特卡洛方法进行搜索得到。
首先对于每个状态，我们根据策略随机指定一个行动，然后计算行动值，根据行动值和策略得到梯度进行梯度上升。
值函数近似
显然我们需要有一个数据结构记录我们得到的答案。
有多少个数据需要记录？状态值的数量等于状态的数量。如果你的游戏有“血量/攻击/防御/法力···”等参数，状态的数量将是它们可能性的乘积，这已经太太多了。如果状态存在连续值，则根本无法记录！！
一种巧妙的方式是，设计一个函数F拟合这些数据。假设函数参数是C，则每个具体的行动值都可以表示为Fc(i)，i指状态序号。我们需要得到正确的状态值，实际上就是需要找到一个合适的函数F和正确的参数C，我们称这种方法为“值函数拟合”。
值函数近似做的是“拟合当前的状态值”；而策略梯度方法却是主动调整状态值让它尽量大！
第一个问题是如何选择函数，可以使用一些复杂的线性/非线性函数，特点我们知道函数的形式，可以直接得到导数的方程。可你很难知道什么函数复杂到足够拟合你的模型，所以有更“懒”的方法，直接使用一个神经网络作为拟合函数，就变成了“深度强化学习”。
第二个问题是如何训练。如果状态值完全已知，那直接拟合就好了。如果只知道部分状态值，我们要求函数拟合这几个特殊点。然后使用时序差分方法，每次更新一个点，同时要求值函数拟合新的点。
最后的问题是如何拟合。又回到了熟悉的机器学习基础内容，我们将“值函数和真实值的差”作为损失函数，然后使用梯度下降或者反向传播方法。注意单点拟合类似随机梯度下降，我们最好一次性拟合较多的点，从而提高训练效率。
Actor-Critic方法
现在是时候将“值函数近似””和“策略梯度方法”方法结合起来了！！
之前提到，策略梯度算法的问题在于，梯度的计算需要行动值，但是基于策略的方法并没有存储行动值，只能使用蒙特卡洛方法搜索得到行动值。
现在我们将策略梯度与值函数结合，策略梯度方法将根据策略生成行为，值函数根据行为进行一次时序差分方法，同时生成行动值，策略梯度方法再使用此行动值进行梯度上升。二者循环迭代得到最终结果。
Actor指的就是策略梯度方法，它用于生成行为。而Critic指的是值函数近似，它用于评估行为的好坏。
算法的基本思路就这么简单，但实际应用中还有些技巧用于加速训练、降低方差，请自行观看视频。
学习这些内容需要多久？
如果你具有机器学习基础，直接看开头推荐的“强化学习的数学原理”视频，10小时的课时，两个晚上足以让你理解强化学习的基本思想。但是对于具体的数学公式和应用，则需要更多的实践。
希望看到这里的读者，不要像作者一样因为没学这“两个晚上的内容”，面试被挂······