如何从理论上解决一个已知的MDP：通过动态规划来评估一个给定的策略，并且得到最优价值函数，根据最优价值函数来确定最优策略；也可以直接进行不基于任何策略的状态价值迭代得到最优价值函数和最优策略。

那么解决一个可以被认为是MDP、但却不掌握MDP具体细节的问题，也就是如何直接从Agent与环境的交互来得到一个估计的最优价值函数和最优策略？

这部分内容分为两部分：

• 第一部分聚焦于策略评估，也就是预测，直白的说就是在给定的策略同时不清楚MDP细节的情况下，估计Agent会得到怎样的最终奖励。包括【蒙特卡洛强化学习】、【时序差强化学习】和【介于两者之间的λ时序差分强化学习】。
• 第二部分聚焦于策略提升，也就是控制，找出最优策略，最大化智能体的奖励。
  【 补充：预测与控制、策略评估、策略提升的概念】

参考资料

[1] 叶强：《强化学习》第四讲 不基于模型的预测

[2] 华师数据学院·王嘉宁：强化学习（五）：蒙特卡洛采样方法

[3] 时雨：强化学习5：蒙特卡罗方法

[4] 叶强：《强化学习》第五讲 不基于模型的控制

目录

• 概念
• 蒙特卡洛策略评估
• 目标
• 数学描述
• 分类
• 增量计算/累积更新平均值

• 蒙特卡洛策略提升
• 目标
• 基于试探性出发的MC策略提升
• 基于同轨策略on-policy的MC策略提升
• 基于离轨策略off-policy的MC策略提升

1 概念

蒙特卡洛强化学习指在不清楚MDP状态转移及即时奖励的情况下，直接从经历完整的Episode来学习状态价值，通常情况下某状态的价值等于在多个Episode中以该状态算得到的所有回报的平均值。

当Agent运行越久，观测到越来越多的回报时，其平均值就会慢慢收敛到状态的期望价值，也就是。

当一个状态在Episode内出现多次，该状态的收获有不同的计算方法，下文会讲到。

延续GPI的思想，蒙特卡洛方法也是【策略评估（预测）】和【策略提升（控制）】之间的相互迭代。

蒙特卡洛强化学习的特点：

• 基于无模型
• 必须是一系列完整的Episode（从某个状态开始到终止状态）

2 蒙特卡洛策略评估

2.1 目标

在策略评估阶段，首先给定一个初始化固定的策略，目标便是从一系列的完整Episode经历中学习得到该策略下的状态价值函数，也就是预测某状态的状态价值函数。

2.2 数学描述

基于特定策略的一个Episode信息可以表示为如下的一个序列：

 时刻状态  的收益：

T为终止时刻。

2.3 分类

而对于某一个Episode，存在一些状态它们会被访问若干次，这在动态规划中是不会出现的，但对于随机采样的序列是很大概率出现的。

当一个状态在Episode内出现多次，该状态的收获有不同的计算方法。因此我们将蒙特卡洛策略评估划分为两种：

• 首次访问型（First-visit）：只统计每个状态首次被访问时的状态价值。
  在给定一个策略，使用一系列完整Episode评估某一个状态s时，对于每一个Episode，仅当该状态第一次出现时列入计算。
• 每次访问型（Every-visit）：统计每个状态所有被访问后产生的状态价值。

一般来说，常用首次访问型方法，因为其可以比较快速的收敛，而对于每次访问型，因为同一个状态不同时间点不一定是独立的，虽然实验显示也会收敛，但速度会比较慢。

2.4 增量计算/累积更新平均值

在计算状态价值时，如果要预先存储所有数据，最后再求均值，会浪费存储空间，增加计算压力。为了提高效率，可以更新计算方法如下：

可以引入参数  ： 

3 蒙特卡洛策略提升

3.1 目标

MC方法会遇到的一个棘手的问题是，有许多的状态动作不会被访问，比如说当Agent遵循一个确定性策略时，在每一次遇到一个状态时，Agent都会选择一个动作，对于当前状态下的其他可选动作将不会有机会进行回报值平均，这也就限制了对其他动作的评估，进而影响Agent的选择能力。

所以在MC方法中我们要加入一定的探索机制，主要有几种解决策略：① 试探性出发；② 同轨策略on-policy；④离轨策略off-policy。

3.2 基于试探性出发的MC策略提升

首先，初始化相关变量，然后无限次循环每一个采样序列，采样序列的初始部分的（状态-动作）二元组都有一定概率被选中，其次从后向前依次累计各个状态的价值，并使用增量方法计算动作价值函数的期望值。这里依然也是基于首次访问型。

试探性出发能够解决部分状态动作二元组无法访问的问题，但其也存在另一个问题：一般而言，很多应用领域是不适合随机初始状态的，因此不能够适合所有场景。

3.3 基于同轨策略on-policy的MC策略提升

采样策略与目标优化策略一致时，我们称之为同轨策略，此方法也被叫做软策略（soft policy），例如ε-贪心算法。

具体来说，就是个体已有一个策略，并且遵循这个策略进行采样，或者说采取一系列该策略下产生的行为，根据这一系列行为得到的回报，更新状态函数，最后根据该更新的价值函数来优化策略得到较优的策略。由于要优化的策略就是当前遵循的策略。

基于ε-贪心算法的同归策略蒙特卡洛提升算法如下：

3.4 基于离轨策略off-policy的MC策略提升

采样策略与目标优化策略不一致时，我们称之为离轨策略。

具体来说，就是虽然个体有一个自己的策略【目标策略】，但是个体并不针对这个策略进行采样，而是基于另一个策略【行动策略】进行采样，这另一个策略可以是先前学习到的策略，也可以是人类的策略等一些较为优化成熟的策略，通过观察基于这类策略的行为，或者说通过对这类策略进行采样，得到这类策略下的各种行为，继而得到一些回报，然后更新价值函数，即在自己的策略形成的价值函数的基础上观察别的策略产生的行为，以此达到学习的目的。这种学习方式类似于“站在别人的肩膀上可以看得更远”。

需要满足的条件：

• 目标策略下发生的动作都至少偶尔能在下发生，即。
• 重要度采样建立两种不同分布之间的关系。

3.4.1 重要度采样（importance sampling）

重要度采样指在给定某个来自其他分布的条件下，估计某种分布的期望值的方法。

两篇文章讲解很好：时雨：重要性采样（Importance Sampling） 以及 时雨：强化学习5：蒙特卡罗方法

(待完善)