1. value-based

前面也介绍到了，在强化学习中，学习的目标是要找到一个策略 $\pi ^\ast$，使得总体回报的期望最高。这里的回报就是状态价值函数 $V^{\pi}\left ( s \right )$和动作价值函数 $Q^{\pi}\left ( s,a \right )$。而基于值的方法并不直接对策略 $\pi$ 建模，而是先学习并优化价值函数，然后基于价值函数来推导出最优策略：

$$\pi ^\ast \left ( s \right )=\underset{a}{argmax}\;Q^\ast\left ( s,a \right )$$

以上便是 value-based 强化学习的核心思想。

基于值的方法主要有三大类，分别为：动态规划、蒙特卡洛方法和时序差分算法。在动态规划方法中，我们需要知道转移矩阵 $P$ 和奖励函数 $r$，这两个参数就构成了模型，因此动态规划也划分到基于模型（model-based）方法。

但是对于实际生活中的问题来说，绝大部分情况下是不知道模型的，那么，是否存在不需要使用模型的方法，也就是 model-free 的方法。答案是存在，蒙特卡洛方法便是其中的一个。本篇中介绍的是基于蒙特卡洛的方法。

2. 蒙特卡洛方法

蒙特卡洛方法（Monte-Carlo method）是一种基于采样估计的方法，完全不需要事先知道模型，而是通过让智能体与环境交互，收集到完整的回合（episode）的样本，然后用该回合的实际回报的平均值估计价值函数。

我们已知动作价值函数的表达式为：

$$Q^{\pi }\left ( s_t,a_t \right )=\textbf{E}_{\tau \sim \pi}\left [ G_t\mid s_t=s,a_t=a \right ]$$

只需要采样到足够多的轨迹，便可以对上述的期望展开：

$$Q^{\pi }\left ( s_t,a_t \right ) \approx \frac{1}{N_{\left ( s_t,a_t \right )}} \sum _{i=1}^{N_{\left ( s_t,a_t \right )}} G_t^{\left ( i \right )}$$

其中，$N_{\left ( s_t,a_t \right )}$ 表示在策略 $\pi$ 下，状态-动作对 $\left ( s_t,a_t \right )$ 被访问的次数。$G_t^{\left ( i \right )}$ 表示的第 $i$ 次在状态-动作对 $\left ( s_t,a_t \right )$ 出现后得到的回报，而从回报的定义来看，回报是价值的累积。

上述的计算方法，最大的问题是为了计算最终的均值，需要存储所有历史的 $G_t^{\left ( i \right )}$，在实际的实现过程中，可以使用增量的方式：

$$Q^{\pi }\left ( s_t,a_t \right ) \leftarrow Q^{\pi }\left ( s_t,a_t \right )+\frac{1}{N_{\left ( s_t,a_t \right )}}\left ( G- Q^{\pi }\left ( s_t,a_t \right ) \right )$$

初次看到这个增量公式，可能并不清楚是怎么推导出来的，实际上是从上面的期望展开，首先，假设前 $n-1$ 次的平均为：

$$Q_{n-1}=\frac{1}{n-1}\sum _{i=1}^{n-1}G^{\left ( i \right )}$$

现在有第 $n$ 个样本 $G_n$，此时计算新的均值：

$$Q_{n}=\frac{1}{n}\sum _{i=1}^{n}G^{\left ( i \right )}$$

拆分开后，得到：

$$\begin{align*} Q_{n} &= \frac{1}{n}\left ( \sum _{i=1}^{n-1}G^{\left ( i \right )}+G_n \right )\\ &= \frac{1}{n}\left ( \left ( n-1 \right )Q_{n-1}+G_n \right )\\ &= \frac{n-1}{n}Q_{n-1}+\frac{1}{n}G_n\\ &= Q_{n-1}+\frac{1}{n}\left ( G_n-Q_{n-1} \right ) \end{align*}$$

在这里，如果状态-动作对 $\left ( s_t,a_t \right )$ 被多次访问，根据统计的不同，分为 first-visit 和 every-visit。first-visit 表示的是只记录第一次，而 every-visit 表示的是每一次都会被记录。在这里以 every-visit 为例，还是以 Frozen Lake^[2] 问题展开实验，实验环境如下：

2.1. every-visit

构建 MonteCarlo 类，并写出完整的代码，如下：

import numpy as np
import gymnasium as gym

class MonteCarlo:
    def __init__(self, env):
        self.env = env # 环境
        self.state_size = env.observation_space.n # 状态空间大小
        self.action_size = env.action_space.n # 动作空间大小
        self.q_table = np.random.uniform(low=0, high=0.01, size=(self.state_size, self.action_size)) # Q-table

        self.episodes = 50000
        self.gamma = 0.99

        # INFO: 用于控制探索的机率
        self.epsilon = 1.0
        self.min_epsilon = 0.05

        # INFO: 记录访问次数
        self.returns_count = np.zeros_like(self.q_table, dtype=np.float64)
    
    def __update_q_every_visit(self, trajectorty):
        G = 0
        # INFO: 反向计算 return
        for state, action, reward in reversed(trajectorty):
            G = reward + self.gamma * G
            self.returns_count[state, action] += 1
            count = self.returns_count[state, action]

            q = self.q_table[state, action]
            self.q_table[state, action] += (G - q) / count

    def train(self, first_visit=True):
        for episode in range(self.episodes):
            # INFO: 采样完整的轨迹
            trajectory = []
            state, _ = self.env.reset()
            for _ in range(1000):  # 限制最大步长
                # INFO: 选择下一步的行为
                action = np.argmax(self.q_table[state, :]) # 贪婪选择当前最优
                if np.random.rand() < self.epsilon: # 增加随机探索
                    action = self.env.action_space.sample()
                next_state, reward, terminated, truncated, _ = self.env.step(action)
                done = terminated or truncated

                # INFO: 设置奖励
                if done:
                    if reward == 0: # 掉落到洞中，增加惩罚
                        reward = -1
                else:
                    reward = -0.01

                # INFO: 记录完整的轨迹
                trajectory.append((state, action, reward))
                state = next_state

                if done:
                    break
            
            # INFO: 根据生成的轨迹，更新 Q-table
            # if first_visit:
            #     self.__update_q_first_visit(trajectory)
            # else:
            self.__update_q_every_visit(trajectory)

            # INFO: GLIE epsilon 衰减（不会变成0）
            self.epsilon = max(self.min_epsilon, self.epsilon * 0.99995)

            if episode % 1000 == 0:
                print(f"Episode {episode}, epsilon={self.epsilon:.3f}")

        print("Training finished.")
        return self.q_table

写下测试的代码：

if __name__ == "__main__":
    # INFO: 创建环境
    env = gym.make('FrozenLake-v1', map_name="8x8", is_slippery=False)
    mc = MonteCarlo(env)
    q_table = mc.train(False)
    env.close()

    # INFO: 测试
    env_test = gym.make('FrozenLake-v1', map_name="8x8", is_slippery=False, render_mode='human')
    print("测试环境初始化完成")
    state, _ = env_test.reset()
    done = False
    step = 0
    while not done:
        action = np.argmax(q_table[state, :])
        state, reward, terminated, truncated, _ = env_test.step(action)
        done = terminated or truncated
        print(f"step={step}, action={action}, state={state}, reward={reward}")
        step += 1
    print("Test finished.")
    env_test.close()

2.2. first-visit

every-visit 中每一次的状态-动作对 $\left ( s_t,a_t \right )$ 都会被记录，还有另一种 first-visit，只记录第一次的状态-动作对 $\left ( s_t,a_t \right )$，强化学习教材里 Reinforcement Learning: An Introduction^[3] 通常采用最后一次，这里也是沿着这个计算方法，得到下面的更新方式：

def __update_q_first_visit(self, trajectory):
    G = 0
    visited = set()

    # INFO: 反向计算 return
    for state, action, reward in reversed(trajectory):
        G = reward + self.gamma * G

        if (state, action) not in visited:
            visited.add((state, action))

            self.returns_count[state, action] += 1
            count = self.returns_count[state, action]

            q = self.q_table[state, action]
            self.q_table[state, action] += (G - q) / count

3. 总结

在蒙特卡洛方法中，已经不需要事先知道模型，通过让智能体与环境的交互，收集到完整的轨迹样本，从而估计出均值。但是通过上面的实验来看，高方差也导致了学习的不问东，同时，每次更新都需要得到轨迹结束，计算量较大。

参考文献

[1] https://datawhalechina.github.io/easy-rl/#/chapter3/chapter3?id=_33-%e5%85%8d%e6%a8%a1%e5%9e%8b%e9%a2%84%e6%b5%8b

[2] https://gymnasium.farama.org/environments/toy_text/frozen_lake/

[3] http://incompleteideas.net/book/RLbook2020.pdf