强化学习之 免模型学习（model-free based learning）
------ 蒙特卡罗强化学习 与 时序查分学习
------ 部分节选自周志华老师的教材《机器学习》
由于现实世界当中，很难获得环境的转移概率，奖赏函数等等，甚至很难知道有多少个状态。倘若学习算法是不依赖于环境建模，则称为“免模型学习（model-free learning）”，这比有模型学习要难得多。
1. 蒙特卡罗强化学习：
在免模型学习的情况下，策略迭代算法会遇到几个问题：
首先，是策略无法评估，因为无法做全概率展开。此时 只能通过在环境中执行相应的动作观察得到的奖赏和转移的状态、一种直接的策略评估代替方法就是“采样”，然后求平均累积奖赏，作为期望累积奖赏的近似，这称为“蒙特卡罗强化学习”。
第二，就是策略迭代算法估计的是 状态值函数（state value function） V，而最终的策略是通过 状态动作值函数（state-action value function） Q 来获得。模型已知时，有很简单的从 V 到 Q 的转换方法，而模型未知 则会出现困难。所以我们将估计对象从 V 转为 Q，即：估计每一对 “状态-动作”的值函数。
总而言之，就是在模型未知的时候，我们从初始状态出发，使用某种策略进行采样，执行该策略 T 步并获得轨迹：
$x_0, a_0, r_1, x_1, a_1, r_2, ... , x_{T-1}, a_{T-1}, r_{T-1}, x_T$
然后，记录轨迹中每一个 状态-动作对 的奖赏之和，作为该 状态-动作对 的一次累积奖赏采样值。多次采样得到多条轨迹，对其求平均 作为状态-动作值函数的估计。
此外，为了得到较好的奖赏，仅仅依靠某一个策略进行采样是不充分的，需要额外的采用其他策略来进行探索，类似于 K-摇臂赌博机，以一定的概率随机的选择一个动作执行，然后以 另一个概率 从当前的动作集合中进行选择 奖赏最大的动作，进行执行。
在策略评估完毕后，同样要进行策略改进，这里由于“被评估”和“被改进”的是同一个策略，因此称为“on-policy（同策略）”蒙特卡洛强化学习算法。
此处需要注意的是：我们将确定性的策略 $\pi$ 称为“原始策略”，而原始策略上使用贪心算法之后的策略记为：$\epsilon-贪心$。
2. 时序差分学习（TD）：
与基于 策略迭代 和 值迭代的算法相比，蒙特卡洛算法需要采样完成一个轨迹之后，才能进行值估计（value estimation），这样看，就感觉蒙特卡洛速度很慢啊！据说主要原因在于 蒙特卡洛没有充分的利用强化学习任务的 MDP 结构。但是， TD 充分利用了 “MC”和 动态规划的思想，做到了更加高效率的免模型学习。
MC 的本质是通过多次采样后计算平均 作为期望累积奖赏的近似。但是由于是 一个轨迹采样完成后 才对各个 状态-动作对进行更新，所以是属于“批处理”的方式，那么怎么将其改成 online版本的呢？从而实现 增量的更新？
众所周知 Online版本的算法与 批处理很大的不同在于， online可以实现 一个一个的递增的更新，那么此处就有：
不妨假设在 第 t 次采样的时候，已经估计出 值函数 Q(s, a)，则在第 t + 1 次采样的时候，就有：
$Q_{t+1}^{\pi} (x, a) = Q_{t}^{\pi} (x, a) + \frac{1}{t+1}(r_{t+1} - Q^{\pi}_t (x, a)) $
3. 策略评估 与 策略改进：
策略评估是为了检查当前策略是否是最优策略，若不是最优策略，需要对当前策略进行改进。
当模型已知的时候，对任意策略都可以估计出该策略可以带来的 期望累积奖励。
此处有两个估计函数，即：state-action value function Q(s, a) 以及 state value function V(s)：
state value function V(s) 是从状态 s 出发，按照某策略，所能够得到的累积奖励；
state-action value function Q(s, a) 是从状态 s 出发，执行动作 a 之后，再使用当前策略，所能够得到的累积奖赏。
利用这两个 value function 就可以对策略进行测试 或者讲是评估，那么，如果并非最优策略，那么如何对其进行改进呢？
迭代的求解最优值函数 就可以得到最大化的累积奖赏。
最优贝尔曼等式（Bellman Equation）解释了非最优策略的改进方式：
将策略选择的动作 改变为 当前最优的动作。
4. 策略迭代 与 值迭代：
所谓策略迭代 也就是将策略评估 和 策略改进 组合起来使用，即首先进行策略评估，然后进行策略改进，在评估，再改进，直到达到最优策略。
那么，什么是 值迭代呢？
由于 策略改进 和 值函数的改进是一致的，因此 可以将策略改进 看做是 值函数的改善。所以，值迭代其实就是以更新 值函数的形式 对策略进行改善，这也就是值迭代的定义。
