文章强化学习基础：基本概念和动态规划中介绍了如何使用动态规划解决强化学习的问题，但是使用动态规划的前提是已知马尔科夫决策过程(MDP)的所有信息，而不需要从与环境的交互中逐渐学习，这在大部分实际应用中是不可能的，因此本文介绍两种在实际应用中经常使用的解决强化学习问题的方法。
蒙特卡洛
该方法模拟随机抽样的思想来解决强化学习中的求解期望值（例如v_{\pi}）的问题，多用在Episodic Task中，下方左图说明了如何使用蒙特卡洛计算v_{\pi}(s)，下方右图说明了如何计算q_{\pi}(s,a)。以计算v_{\pi}为例，需要注意的是蒙特卡洛方法有两种常见形式：
- first-visit MC：仅计算状态s在一个episode中首次出现时的G_t
- every-visit MC：计算状态s在一个episode中每次出现时的G_t
本文仅介绍了first-visit MC，将下图中的if语句去掉即为every-visit MC：
使用蒙特卡洛进行策略迭代时可利用公式\large \bar{X}_{k}=\frac{\large \sum_{i=1}^{k} x_{i}}{\large k}=\bar{X}_{k-1}+\frac{\large 1}{\large k}\left(x_{k}-\bar{X}_{k-1}\right)具体过程见下方左图，需要注意的是在策略迭代过程中使用了\epsilon-greedy方法来尽可能探索不同的状态：
- Exploitation：按照概率1-\epsilon，选取贪心策略\pi(s)=\arg \max _{a \in \mathcal{A}(s)} Q(s, a)
- Exploration：按照概率\epsilon，选取完全随机策略\pi(a \mid s)=1/|\mathcal{A}(s)|
下方右图将左图中的\frac{1}{N(S_t, A_t)}替换为了一个常数\alpha，这样做的目的是赋予由较新的策略得到的G_t更大的权重，减少由旧策略得到的G_t的权重。
时序差分
相对于蒙特卡洛通过\sum_{k=t+1}^T \gamma^{k-t-1}R_{k}计算G_t，时序差分的主要区别是使用公式R_{t+1}+\gamma Q(S_{t+1},A_{t+1})来估计G_t。这样做的优点是不需要将整个episode模拟完，仅需要一步模拟就可以对策略进行更新，相比于蒙特卡洛有更小的方差和更快的收敛速度，下图表示使用时序差分计算q^*(s,a)的具体步骤：
本文上述方法均属于on-policy method，即智能体和环境进行交互时使用的策略\mu（behaviour policy）和需要提升的策略\pi（target policy）是相同的，下图表示一个off-policy method，即智能体和环境进行交互时使用的策略不同于需要提升的策略，容易看出\begin{cases}\mu=\epsilon\text{-greedy}(Q),\space\space A\sim\mu(\cdot |S^{\prime}) \\ \pi(S^{\prime})=\underset{a}{\operatorname{argmax}}\space Q(S^{\prime},a)\end{cases}该算法称为Q-learning：
