本文主要针对查找表的强化学习方法（表格型方法），讨论表格型方法是什么，他的常见类型和使用的场景，常见的算法，这三个类型给具有一定基础知识的读者介绍表格方法。

主要参考李宏毅的蘑菇书，在线阅读链接。
感谢王琦等人编写的网站，一切以他们为准，笔者夹杂了自己理解。
王琦，杨毅远，江季，Easy RL：强化学习教程，人民邮电出版社，https://github.com/datawhalechina/easy-rl, 2022.

复习一下上一篇，就是马尔科夫是什么，还有马尔科夫决策过程，强化学习的目的就是为了获取更好地策略。
策略最简单的表示是查找表（look-up table），即表格型策略（tabular policy）。使用查找表的强化学习方法称为表格型方法（tabular method），如蒙特卡洛、Q学习和Sarsa（后续会提到）。

表格型方法是什么

说表格型方法就得先提免模型和有模型是什么。

免模型和有模型

强化学习是一个与时间相关的序列决策的问题。马尔科夫决策过程实际就是一条序列逐步的决策，将每次可以选择几种动作分对应的岔路，再将可能导致的结果再分对应岔路，形成树结构。如下图。

有模型就是啥都知道，即这是一个确定的环境，马尔科夫决策过程是可知的，比较容易得到最优策略。

无模型（也被称为免模型）就是有一些未知数，也就是环境是未知的。 因为现实世界好多都是未知的，只可通过观测进行摸石头过河。

处在未知的环境里，也就是这一系列的决策的概率函数和奖励函数是未知的，这就是有模型与免模型的最大的区别。

免模型强化学习方法没有获取环境的状态转移和奖励函数，而是让智能体与环境进行交互，采集大量的轨迹数据，智能体从轨迹中获取信息来改进策略，从而获得更多的奖励。

至此，就可以开始说两种情况对应的表格是什么样的了：

有模型预测：Q表格

Q 表格是一张已经训练好的表格，这张表格就像是便可全是。通过查看这本手册，我们就知道在房钱环境状态下，什么动作的价值会高一点。 这张表格里面 Q 函数的意义就是我们选择了某个动作后，最后能不能达到最高的奖赏，就需要我们去计算在某个状态下选择某个动作，后续能够获得多少总奖励。

如果可以预估未来的总奖励的大小，我们就知道在当前的状态下选择哪个动作价值更高。我们选择某个动作是因为这样未来可以获得的价值会更高。所以强化学习的目标导向性很强，环境给出的奖励是非常重要的反馈，它根据环境的奖励来做选择。

免模型预测：蒙特卡洛法

蒙特卡洛法就是掷骰子，主要通过采样得到很多次的结果，根据这个结果得到近似的概率。具体为：

特卡洛方法是基于采样的方法，给定策略 π，我们让智能体与环境进行交互，可以得到很多轨迹。每个轨迹都有对应的回报：
$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\dots$$
求出所有轨迹的回报的平均值，就可以知道某一个策略对应状态的价值，即
$$V_{\pi }(s)={\mathbb{E}}_{\tau \sim \pi }\left[G_t\mid s_t=s\right]$$
具体在网站上分析很详细，主要思想是逐步进行更新。

蒙特卡洛方法相比动态规划方法是有一些优势的。首先，蒙特卡洛方法适用于环境未知的情况，而动态规划是有模型的方法。

蒙特卡洛方法只需要更新一条轨迹的状态，而动态规划方法需要更新所有的状态。状态数量很多的时候（比如100万个、200万个），我们使用动态规划方法进行迭代，速度是非常慢的。这也是基于采样的蒙特卡洛方法相对于动态规划方法的优势。

注意蒙特卡洛法是将一个策略所有的走完才进行更新。

时序差分法

这个是样例

时序差分是介于蒙特卡洛和动态规划之间的方法，它是免模型的，不需要马尔可夫决策过程的转移矩阵和奖励函数。 此外，时序差分方法可以从不完整的回合中学习，并且结合了自举的思想。

时序差分方法的目的是对于某个给定的策略 π，在线（online）地算出它的价值函数 ，即一步一步地（step-by-step）算。 最简单的算法是一步时序差分（one-step TD），即TD(0)。每往前走一步，就做一步自举，用得到的估计回报（estimated return） 来更新上一时刻的值 。

对比一下蒙特卡洛方法和时序差分方法。在蒙特卡洛方法里面，奖励G是实际得到的值（可以看成目标），因为它已经把一条轨迹跑完了，可以算出每个状态实际的回报。时序差分不等轨迹结束，往前走一步，就可以更新价值函数。 如下图所示，时序差分方法只执行一步，状态的值就更新。蒙特卡洛方法全部执行完之后，到了终止状态之后，再更新它的值。

进一步比较时序差分方法和蒙特卡洛方法。

1. 时序差分方法可以在线学习（online learning），每走一步就可以更新，效率高。蒙特卡洛方法必须等游戏结束时才可以学习。
2. 时序差分方法可以从不完整序列上进行学习。蒙特卡洛方法只能从完整的序列上进行学习。
3. 时序差分方法可以在连续的环境下（没有终止）进行学习。蒙特卡洛方法只能在有终止的情况下学习。
4. 时序差分方法利用了马尔可夫性质，在马尔可夫环境下有更高的学习效率。蒙特卡洛方法没有假设环境具有马尔可夫性质，利用采样的价值来估计某个状态的价值，在不是马尔可夫的环境下更加有效。

自举和采样是什么

自举是指更新时使用了估计。蒙特卡洛方法没有使用自举，因为它根据实际的回报进行更新。 动态规划方法和时序差分方法使用了自举。

采样是指更新时通过采样得到一个期望。 蒙特卡洛方法是纯采样的方法。 动态规划方法没有使用采样，它是直接用贝尔曼期望方程来更新状态价值的。 时序差分方法使用了采样。时序差分目标由两部分组成，一部分是采样，一部分是自举。

总结

这里只是阐述了理解，并没有涉及很深，原文给出了以下总结，有需求最好过一下。