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）方法。

在蒙特卡洛方法中，虽不需要事先知道模型，但是更新需要得到当前的采样结束后，才能对动作价值函数 $Q$ 更新，更新较慢，同时，蒙特卡洛方法的高方差也导致了整体的训练会出现不平稳的现象。在蒙特卡洛方法中，其更新公式为：

$$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 )$$

基于时序差分算法对上述的问题进行了优化，典型的算法如 Sarsa 算法。在 Sarsa 算法中，由于其基于时序差分算法，能充分利用每一步来更新动作价值函数，其更新公式为：

$$Q^{\pi }\left ( s_t,a_t \right ) \leftarrow Q^{\pi }\left ( s_t,a_t \right )+\alpha \left ( R_t+\gamma Q^{\pi }\left ( s',a' \right )- Q^{\pi }\left ( s_t,a_t \right ) \right )$$

由于每一步的更新都依赖当前的策略 $\pi$，故 Sarsa 算法也被称之为 on-policy 的算法。

2. Q-Learning 算法

在 Sarsa 算法中，学习的是策略 $\pi$ 下的动作价值函数 $Q^{\pi }\left ( s_t,a_t \right )$：

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

在其更新公式中，也能发现，每一步的更新都依赖于当前的策略 $\pi$。而 Q-Learning 算法则是学习最优的动作价值函数 $Q^{\ast }\left ( s,a \right )$，而最优的动作价值函数是所有策略里面的最优：

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

其表示的含义是在状态 $s$ 下，先执行动作 $a$，然后之后都采取最优策略时，能够获得的“最大期望回报”。由贝尔曼最优方程，有：

$$Q^{\ast }\left ( s,a \right )=r\left ( s,a \right )+\gamma \underset{s'}{\sum }P\left ( s'\mid s,a \right )\underset{a'}{max}Q^{\ast }\left ( s',a' \right )$$

由于 $r\left ( s,a \right )=\textbf{E}\left [ R\mid s, a \right ]=\underset{s'}{\sum }P\left ( s'\mid s,a \right )\cdot R$，对上式进行改写：

$$Q^{\ast }\left ( s,a \right )=\underset{s'}{\sum }P\left ( s'\mid s,a \right )\left [ R_t+\gamma \;\underset{a'}{max}Q^{\ast }\left ( s',a' \right ) \right ]$$

改成期望的形式：

$$Q^{\ast }\left ( s,a \right )=\textbf{E}\left [ R_t+\gamma \;\underset{a'}{max}Q^{\ast }\left ( s',a' \right ) \right ]$$

因此有了 Q-Learning 的更新公式：

$$Q^{\pi }\left ( s_t,a_t \right ) \leftarrow Q^{\pi }\left ( s_t,a_t \right )+\alpha \left ( R_t+\gamma \;\underset{a'}{max}Q^{\ast }\left ( s',a' \right )- Q^{\pi }\left ( s_t,a_t \right ) \right )$$

Q-Learning 算法的整个过程^[1]：

3. 算法实现

还是以 Frozen Lake^[2] 问题展开实验，实验环境如下：

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

import numpy as np
import gymnasium as gym

class QLearning:
    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

        # INFO: 设置超参数
        self.learning_rate = 0.01
        self.discount_rate = 0.95
        self.epsilon = 1.0
        self.max_epsilon = 1.0
        self.min_epsilon = 0.01
        self.decay_rate = 0.0005

        # 训练过程
        self.num_episodes = 500000
        self.max_steps = 1000
    
    def train(self):
        for episode in range(self.num_episodes):
            print(f"episode: {episode}")
            state, _ = self.env.reset()
            done = False

            for step in range(self.max_steps):
                # INFO: Epsilon-greedy 策略
                if np.random.uniform(0, 1) < self.epsilon:
                    action = env.action_space.sample()  # 探索
                else:
                    action = np.argmax(self.q_table[state, :])  # 利用
                
                new_state, reward, terminated, truncated, info = env.step(action)
                done = terminated or truncated # 更新 done 标志
                if done:
                    if reward == 0:  # 掉坑
                        reward = -1
                # 到终点 reward=1 保持
                else:
                    reward = -0.01

                # Q-table 更新
                self.q_table[state, action] = self.q_table[state, action] + self.learning_rate * \
                    (reward + self.discount_rate * np.max(self.q_table[new_state, :]) - self.q_table[state, action])

                state = new_state

                if done:
                    break

            # INFO: 更新 epsilon
            self.epsilon = self.min_epsilon + (self.max_epsilon - self.min_epsilon) * np.exp(-self.decay_rate * episode)
        return self.q_table

再写一段测试的代码，如下：

if __name__ == "__main__":
    # INFO: 创建环境
    env = gym.make('FrozenLake-v1', map_name="8x8", is_slippery=False)
    mc = QLearning(env)
    q_table = mc.train()
    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()

4. 总结

Sarsa 算法和 Q-Learning 算法都是基于时序差分的算法，不同的是在 Sarsa 算法中，其学习的目标是在策略 $\pi$ 下的动作价值函数 $Q^{\pi }\left ( s_t,a_t \right )$，这是一个与当前策略 $\pi$ 相关的目标，在策略评估和策略更新时都是基于策略 $\pi$，而在 Q-Learning 算法中，其学习的目标是最优的动作价值函数 $Q^{\ast }\left ( s,a \right )$，这个目标与策略无关，策略的评估和策略的更新不是同一个策略，因此 Q-Learning 算法也被称为 off-policy 算法。

参考文献

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

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