RL-MonteCarlo
蒙特卡罗方法
入门
动态规划需要完整的环境模型且计算量大，而蒙特卡洛方法不需要环境模型，且适用于大规模问题。它只适用于 Episodic 回合任务，即任务有明确的结束点，如玩一局游戏。且只在回合结束后更新价值函数。
采样策略
MC 方法通过 经验数据（Estimated value function）来计算价值，有两种策略：
假设在同一个 episode 中，我们经历了状态：
$$
S_1, S_2, S_2, S_1
$$
First-visit MC：每个状态在一个回合中 首次 出现时，它的回报被记录以用于估计
也就是只会记录 $s_1$ 的第一次访问（第一步），这种策略适用于大部分任务，它减少了计算量，但可能浪费一些有用的信息。
Every-visit MC：每个状态在一个回合中 所有访问 该状态的回报都被记录以用于估计
则会在第一步和第四步都记录 $s_1$ 的回报，它利用所有数据，会更快的收敛到正确的估计函数，但可能导致过度计算。
经验采样
之前我们提到代理会产生一种叫 Trajectory 轨迹的数据，表示为
$$
(s_t, a_t, r_t, s_{t+1}), \cdots
$$
- $s_t$：状态
- $a_t$：动作
- $r_t$：回报
- $s_{t+1}$：下一个状态
这个过程也被称之为 episode 回合，是代理在环境中的一次完整尝试。经验采样利用这些数据，不需要知道环境的规则，代理通过多次交互摸索出最佳策略，记录经验并不断优化，且一定需要足够的探索。
Bootstrap
自举是指利用已有的估值来更新当前估计。公式
$$
V(S_t) \leftarrow E_{\pi} [R_{t+1} + \gamma V(S_{t+1})]
$$
就体现了 DP 中的自举，它利用了下一个状态的估值来更新当前状态的估值。而 MC 方法不使用自举，它通过对实际经历的样本回报进行平均来估计状态的价值。这种特性使得 MC 方法对环境的依赖程度更低，它不需要知道状态之间的转移关系和其他估值。公式
$$
V(S_{t}) \leftarrow V(S_{t}) + \alpha (G_{t} - V(S_{t}))
$$
- $\alpha$：学习率，越大对新样本越重视
- $G_t$：是从 t 开始到一个 episode 结束的回报总和
- $V(S_t)$：表示当前状态的估计值
- $G_t - V(S_t)$：表示当前估计值与实际回报的误差
通过学习率来控制调整的幅度，然后将调整值加到估计值上，得到新的估计值。
21 点游戏
21 点的规则是使得手牌总和尽可能接近 21，但是不能超过21。
- 玩家先行动，可以选择 Hit 要牌或者 Stick 停牌
- 庄家根据固定规则行动，如果手牌总和小于 17，就要牌，否则停牌
- 2 到 10 的牌面值为其点数，J、Q、K 的点数为 10，A 的点数为 1 或 11（如果 11 会爆牌就取 1）
游戏可以描述为 MDP：
- 状态：玩家的手牌和庄家的明牌
- 动作：Hit 或 Stick
- 奖励：游戏结束时的奖励，赢了为 1，输了为 -1，平局为 0
- 折扣因子：$\gamma = 1$
- 无限张牌，每张牌被抽到的概率是相等的
MC 方法在 21 点游戏中，First 与 Every 的效果一致，因为不会回到曾经的状态。从实验结果发现，当玩家手牌总和较大（20，21）时，State Value 跃升，此时玩家通常选择 Stick，胜率较高。如果有可用的 A，则胜率更高，因为可以灵活选择 1 或 11，降低 Bust 的概率。
MC 策略
通过采样回合来估计状态价值，但是有一个重要问题：许多 状态-动作 对可能永远不被访问，如果策略是确定性的，即始终选择当前最优策略，则某些 Q 值无法估计。所以我们提供了两种解决方案：
- Exploring Starts：让每个回合都从随机的状态和动作开始，但在实际环境中我们可能无法随意选择回合的起点。
- Stochastic Policy：使策略变得随机，以高概率选择当前最优动作，有概率选择其他动作，可以使用 soft policy（任何状态下每个动作都有概率被选中，如 $\epsilon$-greedy）。
MC 只能近似最优策略，它使用广义策略迭代进行收敛，但它理论上要求无限多的回合来保证最终收敛，但现实中不可能，我们可以使用 Funciton Approximation 来近似价值函数。在实际应用中，我们通常不会等待策略评估完全收敛再进行策略改进（Incomplete Policy Evaluation），而是在有误差的情况下就开始改进策略，比如只迭代了一次评估，就开始改进策略，会导致优化过程不稳定。
On / Off-Policy
强化学习的核心 Dilemma 就是很难平衡 Exploration 和 Exploitation，我们有两种解决方案：
在线策略，只有一个策略，evaluating 和 improving 都是对同一个函数进行的，它可能不能充分探索环境中的所有情况，而且收敛较慢。
而离线策略引入了两个不同的策略，分为 Behavior Policy 和 Target Policy，它们不相同。行为策略通常是一个探索性策略（如 $\epsilon$-greedy），而目标策略是我们希望收敛到最优的贪心策略。这样，行为策略可以利用不同来源的数据，而目标策略可以更快收敛到最优解。但很明显，这个方法计算量大。有一段很长的证明过程，证明了新策略的性能不会低于原策略。
$\epsilon$-soft 是一个泛化概念，只要满足所有动作都有非零的选择概率，就是 $\epsilon$-soft 策略。$\epsilon$-greedy 是 $\epsilon$-soft 的特例，它以 1 - $\epsilon$ 的概率选择最优，以 $\epsilon$ 的概率随机选择任意动作。
重要性采样
为了解决目标策略 $\pi$ 和行为策略 $b$ 不一致的问题，我们引入了 Importance Sampling，它是一种加权采样方法，调整行为策略的采样数据，使其符合目标策略的分布。公式：
$$
\rho = \frac{\pi(A|S)}{b(A|S)}
$$
这就是对于 单步 的重要性采样比率，我们同时计算同一个动作在两个策略下的概率，然后取比值。
这个比率衡量了目标策略选择动作 A 的概率，与行为策略选择动作 A 的概率之比。假设我们要计算如下期望：
$$
E_{\pi} [f(s, a)] = \sum_{a} \pi(a|s) f(s, a)
$$
由于我们的数据是从 $b$ 采样的，所以我们直接将 $\rho$ 乘到期望公式上即可：
$$
E_{\pi} [f(s, a)] = \sum_{a} b(a|s) f(s, a) \rho
$$
在 Off-Policy 的 MC 中，假设我们有一个 episode：
$$
S_0, A_0, R_1, \cdots, S_T
$$
我们希望计算此 episode 在 $\pi$ 的回报：
$$
G_t^{\pi} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-t-1} R_T
$$
但是我们只有从 $b$ 采样的数据，所以我们需要使用重要性采样：
$$
G_t^{\pi} = G_t \cdot \rho_t
$$
其中：
$$
\rho_t = \prod_{k=t}^{T} \frac{\pi(A_k|S_k)}{b(A_k|S_k)}
$$
使用此累计比率就可以调整整个 episode 的回报。
采样方式
在实际应用中，我们有两种采样方式：
- Ordinary Importance Sampling：直接计算比率，Unbiased，但方差较大，适用于数据量大的情况
$$
V_{\pi}(s) = \frac{1}{N} \sum_{i=1}^{N} \rho_i G_i
$$
- Weighted Importance Sampling：归一化比率，确保所有 Episode 的比率总和为 1，Biased，但方差较小，稳定性好，适用于稳定性要求高或者数据量小的情况
$$
V_{\pi}(s) = \frac{\sum_{i=1}^{N} \rho_i G_i}{\sum_{i=1}^{N} \rho_i}
$$
RL-MonteCarlo