机器学习之——强化学习中的免模型学习

强化学习解决的是在环境中做序列决策的问题。在现实场景中，环境的状态转移、奖赏函数、乃至环境总的状态数往往都是很难获知的，如果强化学习算法不依赖于环境模型，则称为“免模型学习”（model-free learning）。

蒙特卡洛强化学习

由于无法得到环境的模型，因此一个直接的想法就是对环境进行采样。为了估计状态-动作值函数Q，采用策略π进行一系列决策，然后得到一系列奖赏，据此计算每个状态-动作对的Q值。反复进行采样，即可以得到Q的准确估计。

但这样有个问题，就是策略π不能是确定性的策略，因为这样每次采样都会得到同样的序列。因此要使用ε-贪心法，即以ε的概率随机选择动作，以1-ε的概率采用确定性动作π。

仅能估计Q值还不够，还要能够更新策略π，这样才能得到越来越好的策略。与有模型学习类似，可以在每轮迭代时，使用当前Q值计算最优动作，作为策略π，而这可以在数学上证明是比之前的策略更优的。

通过上面过程得到的最终策略是一个ε-贪心策略，即估计Q值和最终输出的策略是同一个策略，这也称为“同策略”（on-policy）方法。

还可以让估计Q值和最终输出的策略不同，这也称为“异策略”（off-policy），这可以通过“重要性采样”的方法实现，本文不做深入介绍。

时序差分学习

上面所述的算法，要求每次采样要是完整的一个序列，例如围棋，每次采样需要下完一盘棋。这样做效率是比较低的。

事实上，可以每一步棋都更新一次Q值，即增量式的更新，这就是时序差分学习的思想。

将同策略的蒙特卡洛强化学习修改为增量式，就得到了SARSA算法。

将异策略的蒙特卡洛强化学习修改为增量式，就得到了Q-Learning算法。

这两个算法的伪代码如下

SARSA和Q-Learning算法