#
Reinforcement Learning RL就是一个supervised random walk，传统的random walk是按照固定的转移概率随便（采样）游走，RL就是在随机游走的每一步，都选择一个能使回报函数最大化的方向走，即选择一个当前状态下最好的action。而RL游走的这个网络，是由状态S为点集，动作A为边集，状态转移概率P为边权重的有向无环图（DAG）。状态转移概率P不是不变的，而是随着agent在这个网络中的步进，不断变得更加正确，符合现实世界的分布。这个DAG，就是一种混沌的网络状态。
-
状态集合S：S是一个状态集合，其中每一个元素都代表一个状态，在游戏的场景中，状态S就是某一时刻采集到的视觉信号。
-
动作集合A：A中包含所有合法操作。
-
状态转移概率P：P是一个概率的集合，一种每一项都表示着一个跳转的概率。
-
回报函数R：R是一个映射，跟状态转移概率P有点联系，R表示在当前状态s下，选择操作a，将会得到怎样的回报。回报不一定是即时回报。
经验式解释RL：连续决策的过程，相比于传统的机器学习中supervised learning有标注哪些是“好”的结果，RL是不给定标注的，而是给一个回报函数，这个回报函数决定当前状态得到什么样的结果。其数学本质是一个马尔科夫决策过程。最终的目的是决策过程中整体的回报函数期望最优。
回报函数有一些小小的tricky。 RL的过程是一个随机过程，每一步的选择是不确定的，而是在一个概率分布中采样出来的结果。因此，整个回报函数是一种沿时间轴进行的时序/路径积分。在RL中，回报函数的时序/路径积分中，每一步的回报都会乘上一个decay量，即回报随着游戏的进行逐渐衰减。本质是如何最快找到好的结果。
所谓策略，就是状态到动作的映射，目的就是找到一种最优策略，使得遵循这种策略进行的决策过程，使得到的全局回报最。
动态规划，Bellman公式可知，在一种序列求解的过程中，如果一个解的路径是最优路径，那么其中的每个分片都是当前的最佳路径。回报函数的最大化就服从Bellman公式，表示可以不断迭代求解问题。
RL的学习有两个方面，典型的EM算法的过程。价值函数，表示当前动作下的即时回报函数，是从状态s转移到之后，所能得到最大的期望价值。即时(immediate)回报函数，即从初始状态s触发，经过a动作的作用，走到这个状态获得的回报是多少。E步：一个函数，以当前状态s为参数，返回一个动作a，这个动作是一个概率分布，代表着在当前状态s下，转移到任意另外一个状态的概率是多少。M步：计算价值函数。
Reward是一次动作a得到的收益，Return是一序列reward的函数，这是两个目标，价值函数是状态的函数，预测在给定状态下agent能表现多好，衡量就是expected reward，在这点能看到的未来最大期望收益。
关键是泛化能力，在有限的状态-动作子集上获得的经验，如何扩展到全部的状态和动作上。使用动态规划这种"查找表"的方式，是有局限的，而且这个局限不仅仅是内存上的，Off-policy是指不需要一个policy查找表之类的，而是直接求最大化reward的那个action。
需要处理的状态，很多时候是连续的、复杂的、高维的。在玩游戏的案例中，状态画面的状态数目是非常恐怖的。 DL的分类如下：
- 第一个差别就是单层网络的不同，分为Auto-encoder和Restricted Boltzmann Machine；
- 第二就是深层架构之不同，如何安排深层架构，是直接堆叠，还是通过卷积神经网络？
- 第三就是最高两层分类/识别层的不同安排，不同的高两层安排代表了不同的学习形式，是生成模型，还是判别模型？
- 第四是不同的激活函数选择，常见的是sigmoid函数，但也有通过Rectified Linear Unit增强学习能力的，甚至还有convex函数的选择，如DSN。
初始化的时候需要设置DL和RL的起始参数，例如episode设置为零，初始化策略，以及初始化空的replay memory。
学习过程就是在一个个episode中进行探索。简单描述过程，累计4帧游戏画面（裁剪，白化）之后，算作当前状态。之后根据现有的策略，选择一个最大化全局回报动作。一次探索的结果存入replay memory。
接下来进行新的策略（模型）学习，首先从replay memory中采样几组探索结果，分别根据一阶的Bellman公式求解理论回报值，作为标注信息。之后使用标准信息来优化CNN，通过SGD进行优化。
不同的episode之前有一些变量是共用的，但是有一些需要置零，重新开始。神经网络是维持不变的，CNN就是随着样本数目，迭代数目不断增加，优化的越来越好。replay memory也是不变的，replay memory是一个资源池，也是传统意义上的数据。至于其他的，比如学到的policy，以及reward等都是需要重新开始的。
Q-function称为function approximator。动态规划方法，需要跟环境交互才能计算最优回报的。这个Q-function是为了完全避免计算最优回报的时候和环境交互。Q-learning是model-free的，RL过程在计算value function（即Q-function）的时候，不需要和环境进行交互。
k值，画面出k帧才判决一次。主要原因是DL编码出特征，找出策略的过程要的时间较长，流式处理系统目前大多无法满足实时判决。
RL是没有大量标准数据，RL每一次计算的时候是不知道一个具体的label来表明对错的，只能得到一个叫做标量回报的信号，这个信号通常是稀疏的，有噪声的和有延迟的。延迟，表明当前动作和回报之间的延迟，所以，agent在战术性游戏的效果好于战略性游戏。
IID（independently and identically distribute），数据分布独立性的假设。如果数据之间是有关联的，计算出来的模型就是有偏向的，但是RL中的数据通常是一个前后严重相依的序列。并且随着policy的学习，数据分布倾向于不同，严重影响回归器的使用。通过使用replay memory，存储过去一段时间内的“状态-动作-新状态-回报”序列，并进行随机采样以打破依赖，以及用过去的动作做平滑。
历史局限性也会制约agent的能力。历史局限性指在当前阶段只能看到游戏的一部分画面，无法掌握全局。从而产生一个问题，马太效应难以调和。强烈的正反馈的循环会昂agent迅速陷入局部最优解，通过replay memory会让更多的历史样本参与训练，从而冲淡马太效应影响。
RL应用Bellman公式，尅有快速得到最大未来回报的结果，这种情况下只针对当前最优路径这一单条路径的情况进行计算，不具备泛化能力。使用卷积神经网络作为自定义的function来模拟最大回报，之前的做法是，给我当前的策略、状态，以及动作的选择作为输入，通过动态规划计算出未来的回报。现在是给定这些输入，直接输送到神经网络中计算出未来的回报。
网络架构方面，输入是84×84×4的像素，第一层神经元是16个8×8的过滤器，第二层是32个4×4的过滤器，最后一层是与256个rectifier单元的全连接，输出层是与单一输出与下层的全连接的线性函数。DeepMind称这种与RL结合使用的卷积神经网络为Deep Q-Network。
传统的有监督学习过程中，评测是简单确定的，给定了测试集，就可以对现有模型给出一个评价。然而，RL的评测是很困难的。最自然的评测比如计算游戏的结果，或者几次游戏结果的均值，甚至是训练过程中周期性的分数统计。这种做法有很大的噪声，因为策略上权重的微小扰动可能造成策略扫过的状态大不相同。因此DeepMind选择了更加稳定的评价策略，即直接使用动作的价值函数，累加每一步操作agent可以得到的折扣回报。
复杂动力系统的预测困难来自三个方面，一是微观结构的易变性，稀疏性导致缺少显著的统计特征；二是复杂动力系统的混沌性，简单的微扰会带来巨大的变化；三是人类行为的因变性，导致数据分布改变影响预测模型。而不同的目的导向也导致了不同的不同的预测结果。
只不过此随机并非完全随机，而是某种程度上可预测的随机。根据状态的不同，动作的选择并不是一个均匀分布。RL正如现实世界的一个缩影，正是RL和DL对世界和人类高度的拟真性，RL和DL就像两位不懈的巨人，在人类认识自我，认识环境的道路上渐行渐远。