5分钟读懂强化学习之Q-learning
强化学习的难点，在于其引入了时间这个维度，不管是有监督还是无监督学习，都是能获得即使反馈，但到了强化学习中，反馈来的没那么及时。在周志华的《机器学习》中，举过一个种西瓜的例子。种瓜有很多步骤，例如选种，浇水，施肥，除草，杀虫这么多操作之后最终才能收获西瓜。但是，我们只有等到西瓜收获之后，才知道种的瓜好不好，也就是说，我们在种瓜过程中执行的某个操作时，并不能立即获得这个操作能不能获得好瓜，仅能得到一个当前的反馈，比如瓜苗看起来更健壮了。因此我们就需要多次种瓜，不断摸索，才能总结一个好的种瓜策略。
为了应对时间带来的不确定性，就需要一个框架来量化时间的流逝对我们关心奖励有怎样的影响。按照最简单的线性模型，我们首先确认要引入那些特征，首先是前一个时间的得分，其次是新发生的事件对奖励的影响，由于我们对未来的奖励看的不如现在的重要，因此可以引入折线率，折现率越高，说明我们越处于游戏的早期，对未来的关注也越多，这道理就如同我们在年轻时更要做长久的规划。同时在更新策略时，也会有快慢之分，将其称为学习率。由此得出了时间差分学习(Temporal Difference)，简称TD方法的更新公式：
该公式描述了给定一个策略，该怎么去更新下一个时刻的估值函数，其中的V代表估值函数，下一个时刻的估值乘以折现率，再减去当前的差值，代表了一个策略的间接影响，可以看成是战略决策，再加上下一个时刻能立即获得的奖励，就是智能体（agent）应该关注的策略的影响，最后对此乘以学习率，用来控制随机性的影响，既要避免由于学习率过低导致的智能体学的太慢，也要避免学习率过高导致智能体矫枉过正。
由于在当下，你并不知道下一时刻的估值函数，所以你要做的是对其有一个尽可能准确的估算，这个估算被称为Q value，对应的算法称为Q-learning。如果你是用神经网络得出对未来value的估算的，那你使用的算法框架就从强化学习变为了深度强化学习。
下面是一个具体的例子，将一个结冰的湖看成是一个4×4的方格，每个格子可以是起始块（S），目标块（G）、冻结块（F）或者危险块（H），目标是通过上下左右的移动，找出能最快从起始块到目标块的最短路径来，同时避免走到危险块上，（走到危险块就意味着游戏结束）为了引入随机性的影响，还可以假设有风吹过，会随机的让你向一个方向漂移。
左图是每个位置对应的Q value的表，最初都是0，一开始的策略就是随机生成的，假定第一步是向左，那根据上文公式，假定学习率是0.1，折现率是0.5，而每走一步，会带来-0.4的奖励，那么（1.2）的Q value就是 0 + 0.1 ×[ -0.4 + 0.5× (0)-0] = -0.04，为了简化问题，此处这里没有假设湖面有风。
假设之后又接着往右走了一步，用类似的方法更新（1，3）的Q value了，得到（1.3）的Q value还为-0.04
等到了下个时刻，骰子告诉我们要往左走，此时就需要更新（1，2）的Q-value，计算式为：V(s) = 0 +0.1× [ -0.4 + 0.5× (-0.04)-0) ]
从这里，智能体就能学到先向右在向左不是一个好的策略，会浪费时间，依次类推，不断根据之前的状态更新左边的Q table，直到目标达成或游戏结束。这就是TD learning的基本步骤，通过多次的实验，智能体掌握了在不同位置下，相应的策略的估值分，从而解决了将较远的未来映射到当下的对不同策略的激励这个强化学习的核心问题。
根据是否亲自尝试不同的策略，Q learning可以分为在线和离线俩者，用学下棋来举例，前者是AI通过自己和人类选手下棋或者自我对弈来提升，而后者AI不操作只观察他人下棋的棋谱，下面看看再离线（off-line）的Q learning中，Q value更新的公式又有了怎样的改变。
和之前的公式对比，最大的不同是未来的Q值是所有行动/策略对应的未来Q值中最大的那一个，这代表着模型根据已有的知识，选择了局部最优的那个行动，通过不断的优化Q table，使得这样一个只考虑一步的最简单型启发规则，也能学到全局相对较优的策略。
还是冰湖的案例，假设在训练的循环中，当前智能体已经学会了在（3，2）这个点上，向左和向右走对应的估值，此时模型要做的是去判定利用当前的知识，还是去探索未知策略的影响，探索是为了发现环境的更多信息，而当探索进行到了一定的程度，就需要根据已知信息去最大化奖励值，在Q learning中，通过一个0-1的参数来用随机性调控探索和开发的权衡。
假设骰子告诉智能体应该选择探索，因此选择了向下走，左图代表的之前智能体的Q-table，现在要做的是根据公式，更新（3，2）这里的Q value，由于向下走的Q-value最低，假定学习率是0.1，折现率是1，那么（3，2）这个点向下走这个策略的更新后的Q value就是：
Q( (3,2) down) = Q( (3,2) down ) + 0.1× ( 0.4 + 1 × max [Q( (4,2) action) ]- Q( (3,2), down））
Q( (3,2), down) = 0.6 + 0.1× ( 0.4 + 1 × max [0.2, 0.4, 0.6] – 0.6)=0.64
而在在线的Q learning算法下（称为State-Action-Reward-State-Action ，简称SARSA），Q table的更新公式变为了
此处不同的是没有了max，由于是智能体在亲自参与，这里也就没法像离线时那样，选择一个最优的策略。不管是在线还是离线，在训练的时候需要做经验回放，即存储当前训练的状态到记忆体中，等下一次训练时再调用。
以上就是强化学习中最基础的Q learning，上诉的例子中不存在随机性，要引入随机性，可以需要通过蒙特卡罗的方法，来进行采样，同时引入对弈树，对其进行翦枝，这就是alpha zero的精髓。了解了Q learning的步骤，可以分析强化学习适用的领域所满足的假设，例如必须有能够清晰定义，事先已知且有限的策略，但现实生活中，真正重要的选择都是无限游戏，有无数种可能的选项，有前人根本不曾想到的选项，因此说强化学习不等价于强AI，只是通向强AI的一条必要选项。
不同于人类的学习，是首先对坏境建模，之后再根据模型找到合适的启发式规则，Q learning框架是模型无关的，不管是什么样的问题，Q learning做的都是去更新状态对应的估值表，不管问题本身具有什么样的特点。和人类思维的另一个不同是Q learning中没有因果关系，学到的Q table只是反映了奖励和策略之间的相关性，而人类的学习则是受着因果关系指引的。关于这个话题，可以参考让神经网络变得透明-因果推理对机器学习的八项助力，其中有详细的论述。
更多阅读
Jianye2019-04-09 19:16:47
文章里面核心概念错误，q learning和sarsa区别在于off policy和on pilicy，而不是在线online和离线offline。
Guo2021-10-26 04:11:05
非常好的文章
Bo2019-04-09 12:29:23
撰文者用的五笔输入法
作者
不是啊
Michael Chen2019-04-08 21:15:25
好像很有学问的样子。