强化学习是机器学习的一个重要分支，可以解决连续决策的问题。
一个强化学习问题，主要包含三个概念，环境状态,行动,奖励, 强化学习的目标就是获得最多的累计奖励。它已有很多应用，比如控制机器人，无人驾驶，商品定价，库存管理，玩游戏，例如AlphaGo。
基本的强化学习模型包括：
- 环境状态的集合 S;
- 动作的集合 A;
- 在状态之间转换的规则；
- 规定转换后“即时奖励”的规则；
- 描述主体能够观察到什么的规则。
规则通常是随机的。主体通常可以观察即时奖励和最后一次转换。在许多模型中，主体被假设为可以观察现有的环境状态，这种情况称为“完全可观测”（full observability），反之则称为“部分可观测”（partial observability）。有时，主体被允许的动作是有限的（例如，你使用的钱不能多于你所拥有的）。
应用举例（AlphaGo）：
例如在围棋这个游戏中，环境状态指的是已经出现的某个局势，行动指在某个位置落子，奖励是指当前这步棋获得的目数，最终的目标就是在结束时总目数超过对手，它是以最终结果为目标，而不是只看当下某个行动带来的利益。
强化学习不像无监督学习那样完全没有学习目标，也不像监督学习那样有非常明确的目标，他的目标一般是变化的不明确的。在围棋游戏中19×19的棋盘带来了3^361种状态，这是无法通过暴力搜索来战胜人类的，所以就需要给计算机抽象思维的能力。AlphaGo 主要使用了快速走子，策略网络，估值网络，和蒙特卡洛搜索树等技术。
深度强化学习模型本质上也是神经网络，主要分为策略网络和估值网络。强化学习中最重要的两类方法, Policy-based , Value-based。第一种是直接预测在某个环境状态下应该采取的行动，第二种是预测在某个环境状态下所有行动的期望价值，然后通过选择 Q 值最高的行动执行策略。
策略网络，即建立一个神经网络模型，它可以通过观察环境状态，直接预测出目前最应该执行的策略（policy），执行这个策略可以获得最大的期望收益（包括现在的和未来的reward）。和之前的任务不同，在强化学习中可能没有绝对正确的学习目标，样本的feature和label也不是一一对应。我们的学习目标是期望价值，即当前获得的reward和未来潜在的可获取的reward。所以在策略网络中不只是使用当前的reward作为label，而是使用Discounted Future Reward，即把所有未来奖励依次乘以衰减系数γ。这里的衰减系数是一个略小于但接近1的数，防止没有损耗地积累导致Reward目标发散，同时也代表了对未来奖励的不确定性的估计。
Policy
对于Action的选择被模型为一个map，也称为policy：
这个policy map提供了在状态s下，选取每个Action的概率，
State-value function
Value function V_π(s)定义成在状态s下预期的返回值，即s_0=s,并且随着策略π，严格的讲，value function是评价在给定一个状态好坏的值。
V_\pi(s) =E(R)=E(\sum_{t=0}^{\infty }\gamma ^tr_t|s_0=s)
这里随机变量R表示了return，并且被定义成将来的收益：
R=\sum_{t=0}^{\infty }\gamma ^tr_t
r_t是步step t的reward奖励，\gamma \subseteq [0,1] 是折扣率discount-rate.
该算法必须找到一个具有最大预期收益的策略。从MDP理论可知，在不损失一般性的情况下，搜索可以限于所谓的固定策略集。如果策略返回的动作分布仅取决于访问的最后一个状态（来自观察agent的历史），那此时策略是固定的。搜索可以进一步限制于确定性的固定策略（deterministic stationary policies）。确定性固定策略确定性地基于当前状态选择动作。因为任何这样的策略都可以通过从状态集到动作集的映射来标识，所以这些策略可以通过这样的映射来标识，而不会失去通用性。
它可以通过观察环境状态，直接预测出目前最应该执行的策略（Policy），执行这个策略可以获得最大的期望收益（包括现在的和未来的Reward）。与普通的监督学习不同，在强化学习中，可能没有绝对正确的学习目标，样本的feature不再和label一一对应。对某一个特定的环境状态，我们并不知道它对应的最好的Action是什么，只知道当前Action获得的Reward还有试验后获得的未来的Reward。我们需要让强化学习模型通过试验样本自己学习什么才是某个环境状态下比较好的Action，而不是告诉模型什么才是比较好的Action，因为我们也不知道正确的答案（即样本没有绝对正确的label，只有估算出的label）。我们的学习目标是期望价值，即当前获得的Reward，加上未来潜在的可获取的reward。为了更好地让策略网络理解未来的、潜在的Reward，策略网络不只是使用当前的Reward作为label，而是使用Discounted Future Reward，即把所有未来奖励依次乘以衰减系数γ。这里的衰减系数一般是一个略小于但接近1的数，防止没有损耗地积累导致Reward目标发散，同时也代表了对未来奖励的不确定性的估计。
使用被称为Policy Gradients的方法来训练策略网络。Policy Gradients指的是模型通过学习Action在Environment中获得的反馈，使用梯度更新模型参数的过程。在训练过程中，模型会接触到好Action及它们带来的高期望价值，和差Action及它们带来的低期望价值，因此通过对这些样本的学习，我们的模型会逐渐增加选择好Action的概率，并降低选择坏Action的概率，这样就逐渐完成了我们对策略的学习。和Q-Learning或估值网络不同，策略网络学习的不是某个Action对应的期望价值Q，而是直接学习在当前环境应该采取的策略，比如选择每个Action的概率（如果是有限个可选Action，好的Action应该对应较大概率，反之亦然），或者输出某个Action的具体数值（如果Action不是离散值，而是连续值）。因此策略网络是一种End-to-End（端对端）的方法，可以直接产生最终的策略。
Policy Based的方法相比于Value-Based，有更好的收敛性（通常可以保证收敛到局部最优，且不会发散），对高维或者连续值的Action非常高效（训练和输出结果都更高效），同时能学习出带有随机性的策略。例如，在石头剪刀布的游戏中，任何有规律的策略都会被别人学习到并且被针对，因此完全随机的策略反而可以立于不败之地（起码不会输给别的策略）。在这种情况下，可以利用策略网络学到随机出剪刀、石头、布的策略（三个Action的概率相等）。
描述
Q-learning是Watkins在1989年引入的。在1992年，Watkins和Dayan提出了一个收敛证明。在1994年，Tsitsiklis给出了更详细的数学证明，而Bertsekas和Tsitsiklis在他们1996年的《Neuro-Dynamic Programming》书中给出了这一证据。
沃特金斯Watkins的博士论文题目是“学习延迟奖励”(Learning from delayed rewards)。在1981年的，一个名为“延迟强化学习”Delayed reinforcement learning”的系统被一个名为“交叉适应阵列”(Crossbar Adaptive Array，CAA)的系统所解决。最初发表于1982年。所提出的CAA体系结构的记忆矩阵W(a,s)与Q-learning的q表相同。体系结构在强化学习中引入了“状态评估”一词。
“二次强化secondary reinforcemen” 一词是从动物学习理论中借鉴来的，通过反向传播来模拟状态值:结果情境的状态值v(s)被反向传播到之前遇到的情况。在 a crossbar fashion，CAA通过水平的方式计算出垂直和动作的状态值。演示图显示延迟强化学习包含状态(理想的、不受欢迎的和中立的状态)，这些状态是由状态评估函数计算的。这种学习系统在1997年被认为是q学习算法的先驱。
SARSA 是一种学习马尔可夫决策过程策略 (MDP) 的算法，用于机器学习的强化学习领域。它是由Rummery和Niranjan在 (1994)一个名为“Modified Connectionist Q-Learning”(MCQ-L)的技术注释中提出的。富萨顿(Rich Sutton)提出的另一个名字Sarsa，只是作为一个脚注被提及。1998年，Wiering认为一些对Watkin的Q-learning的优化可以应用于SARSA。
Van Hasselt很喜欢处理Over-Estimate问题，他先搞出一个Double Q-learning [van Hasselt 2010]，发表于NIPS，六年后设计出深度学习版本的Double DQN[van Hasselt 2016a]。
2013年，DeepMind在NIPS发表了Playing atari with deep reinforcement learning论文，论文中主体利用深度学习网络（CNNs）直接从高维度的感应器输入（sensory inputs）提取有效特征，然后利用Q-Learning学习主体的最优策略。这种结合深度学习的Q学习方法被称为深度Q学习（DQL）。
Deep Q-learning： 通过谷歌DeepMind(名为“深度强化学习”或“deep Q-learning”)，Q-learning在深度学习上的应用，在专家人类层次的Atari 2600游戏中获得了成功。初步结果于2014年公布。该系统使用了一个深度卷积神经网络，该神经网络使用分层结构的卷积滤波器来模拟接受域的效果。当一个非线性函数逼近器(如神经网络)用来表示q时，强化学习是不稳定或发散的。
一直以来，相比起国际象棋，计算机要在围棋方面胜过人类的难度更大，因为围棋有着更大的分支因子（branching factor）使得使用传统的AI方法（如alpha-beta修剪，树遍历和启发式搜索）变得非常困难。 1997年，IBM公司的计算机程序Deep Blue在比赛中击败了国际象棋世界冠军Garry Kasparov。在此后的近20年时间里，使用人工智能技术的最强大的Go程序仅仅达到了业余5段围棋选手级别，且在无让子的情况下仍然无法击败专业的Go棋手。2012年，运行在四台个人计算机集群上的软件程序Zen分别以让5子和让4子的情况下两次击败了日本9段选手武宫正树（Masaki Takemiya）。2013年，计算机程序Crazy Stone在让4子的情况下击败了日本9段棋手石田芳夫（Yoshio Ishida）。
据DeepMind公司介绍，AlphaGo研究项目始于2014年，目的是为了测试一个使用深度学习的神经网络如何在Go上竞争。 AlphaGo比以前的Go程序有了显着的改进，在与其他可用围棋程序（包括Crazy Stone和Zen）的500场比赛中，在单台计算机上运行的AlphaGo赢得了除一个之外的所有胜利，而运行在多台计算机上的AlphaGo赢得了与其他Go程序对战的所有500场比赛，在与单台计算机上运行的AlphaGo比赛中赢下了77％的对阵。 2015年10月的分布式版本使用了1,202个CPU和176个GPU，当时它以5: 0的比分击败了欧洲围棋冠军樊麾先生（职业2段选手），轰动一时。这是计算机围棋程序第一次在全局棋盘（19 x 19）且无让子的情况下击败了人类职业棋手。2016年3月，通过自我对弈进行练习的加强版AlphaGo在比赛中以4: 1击败了世界围棋冠军李世石，成为第一个在无让子情况下击败围棋职业九段棋手的计算机程序，载入史册。赛后，AlphaGo被韩国棋院授予名誉职业九段的称号。2016年12月至2017年1月，再度升级的AlphaGo在未公开真实身份的情况下，以Master名义在网上和中韩日台等一流职业棋手过招，取得了60战全胜的佳绩。2017年5月的乌镇围棋峰会上，进阶版的AlphaGo以3: 0的比分击败了当时世界第一围棋手柯洁。进阶版的AlphaGo相比起李世石版本，运算资源消耗更少，赛后，中国围棋协会授予AlphaGo职业围棋九段的称号。AlphaGo 主要使用了快速走子，策略网络，估值网络，和蒙特卡洛搜索树等技术。
2017年10月，DeepMind发布最新强化版的AlphaGo Zero，这是一个无需用到人类专业棋谱的版本，比之前的版本都强大。通过自我对弈，AlphaGo Zero经过三天的学习就超越了AlphaGo Lee版本的水平，21天后达到AlphaGo Maseter的实力，40天内超越之前所有版本。2017年12月，DeepMind发布AlphaZero论文，进阶版的AlphaZero算法将围棋领域扩展到国际象棋、日本象棋领域，且无需人类专业知识就能击败各自领域的世界冠军
【出处：机器之心-AlphaGo - Yufeng Xiong 】
comparison of reinforcement learning algorithms
以下是对上面的加强学习的算法对算法的模型，策略类型，行动空间，状态空间以及operator的总结和比较：
| Algorithm | Description | Model | Policy | Action Space | State Space | Operator |
|---|---|---|---|---|---|---|
| Monte Carlo | Every visit to Monte Carlo | Model-Free | Off-policy | Discrete | Discrete | Sample-means |
| Q-learning | State–action–reward–state | Model-Free | Off-policy | Discrete | Discrete | Q-value |
| SARSA | State–action–reward–state–action | Model-Free | On-policy | Discrete | Discrete | Q-value |
| Q-Learning-Lambda | State–action–reward–state with eligibility traces | Model-Free | Off-policy | Discrete | Discrete | Q-value |
| SARSA - Lambda | State–action–reward–state–action with eligibility traces | Model-Free | On-policy | Discrete | Discrete | Q-value |
| DQN | Deep Q Network | Model-Free | Off-policy | Discrete | Continuous | Q-value |
| DDPG | Deep Deterministic Policy Gradient | Model-Free | Off-policy | Continuous | Continuous | Q-value |
| A3C | Asynchronous Actor-Critic Algorithm | Model-Free | Off-policy | Continuous | Continuous | Q-value |
| NAF | Q-Learning with Normalized Advantage Functions | Model-Free | Off-policy | Continuous | Continuous | Advantage |
| TRPO | Trust Region Policy Optimization | Model-Free | On-policy | Continuous | Continuous | Advantage |
| PPO | Proximal Policy Optimization | Model-Free | On-policy | Continuous | Continuous | Advantage |
【出处：https://en.wikipedia.org/wiki/Reinforcement_learning 】
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1992 | Watkins, C. J., & Dayan, P.提出Q学习 | Watkins, C. J., & Dayan, P. (1992). Q-learning. Machine learning, 8(3-4), 279-292. |
| 1994 | Rummery, G. A., & Niranjan, M.提到sarsa算法 | Rummery, G. A., & Niranjan, M. (1994). On-line Q-learning using connectionist systems (Vol. 37). University of Cambridge, Department of Engineering. |
| 1994 | Tsitsiklis, J. N给出了更详细的数学证明 | Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine learning, 16(3), 185-202. |
| 2016 | Van Hasselt, H., Guez, A.使用双Q-learning的深度强化学习 | Van Hasselt, H., Guez, A., & Silver, D. (2016, February). Deep Reinforcement Learning with Double Q-Learning. In AAAI (Vol. 16, pp. 2094-2100). |
3. 发展分析
瓶颈
深度强化学习堪忧的采样效率；奖励函数设计困难；最合理的奖励也不能避免局部最优；Deep RL起作用时，它可能只是过度适应环境中的怪异模式；Deep RL起作用时，它可能只是过度适应环境中的怪异模式；Deep RL的落地应用艰难等问题都阻碍了深度强化学习的发展。
未来发展方向
- 添加更多的learning signal。稀疏奖励很难学习，因为我们无法获得足够已知的有帮助的信息；
- 基于模型的学习可以释放样本效率。原则上来说，一个好模型可以解决一系列问题，就像AlphaGo一样，也许加入基于模型的方法值得一试；
- 像参数微调一样使用强化学习。第一篇AlphaGo论文从监督学习开始，然后在其上进行RL微调。这是一个很好的方法，因为它可以让我们使用一种速度更快但功能更少的方法来加速初始学习；
- 奖励是可以学习的。如果奖励设计如此困难，也许我们能让系统自己学习设置奖励，现在模仿学习和反强化学习都有不错的发展，也许这个思路也行得通；
- 用迁移学习帮助提高效率。迁移学习意味着我们能用以前积累的任务知识来学习新知识，这绝对是一个发展趋势
Contributor: Ruiying Cai