强化学习基础与Q-Learning

今年打 Kaggle 比赛用了 DeepSeek-Math-7B-RL 模型，学习时把 Claude 3.5 Sonnet 当作老师，这两个模型强大的原因都离不开 RL。隐约感觉这个领域的技术很强很美于是准备接触一下，奈何功底不扎实不好，看不懂 OpenAI Spinning Up，于是选择了 HuggingFace DeepRL 这样的入门课浅尝。

导论#

强化学习的理念是，智能体（AI）通过与环境互动（通过试错）并获得奖励（正面或负面）作为执行动作的反馈，从而从环境中学习。

Pasted image 20240923005651

Agent 从环境中获取第一帧，接收到 state $S_0$ ，基于 $S_0$ ，Agent 采取 action $A_0$ （比如向右走），环境进入新一帧（new state $S_1$ ），环境给予 agent 一定 reward $R_1$ （比如没有死亡 +1 正奖励）

Agent 的目标是 最大化 其累积奖励，称为预期回报。

奖励假设：强化学习的核心思想#

强化学习基于奖励假设，即所有目标都可以描述为预期回报的最大化（预期累积奖励）。在强化学习中，为了获得最佳行为，我们的目标是学会采取那些最大化预期累积奖励的行动。

Tasks 分两类#

Episodic: Has a starting point and an ending point. （游戏关卡）
Continuous: Has a starting point but no ending point. （自驾）

State 和 Observation 之间有何区别？#

State 是对世界状态的完整描述（不存在隐藏信息），如象棋棋盘
Observation 是对状态的部分描述，如马里奥游戏镜头

Policy-based Methods#

在此方法中，策略是直接学习的。
将为每个状态映射到该状态下最佳对应的动作，或该状态下可能动作集的概率分布。

Value-based Methods#

不是训练一个策略，而是训练一个价值函数，该函数将每个状态映射到处于该状态的预期价值。
Pasted image 20240925220141

探索 / 利用的权衡#

在强化学习中，我们需要平衡探索环境的程度与利用已知环境信息的程度。

Pasted image 20240924233504

何来深度？#

引入了深度神经网络来解决强化学习问题

Pasted image 20240923223626

实践举例 - HUGGY#

建议直接用 colab 玩，在 WSL2 中跑的话需要做一步 virtual display 设置：

import os
os.environ['PYVIRTUALDISPLAY_DISPLAYFD'] = '0'

from pyvirtualdisplay import Display
display = Display(visible=0, size=(1400, 900))
display.start()

Pasted image 20240924234251

State Space#

要训练 Huggy 去捡起我们扔出的棍子。这意味着它需要正确地朝棍子移动。

我们提供的环境信息：

目标（棍）位置
它与目标之间的相对位置
它双腿的朝向。

根据所有这些信息，Huggy 可以利用它的Policy来决定下一步采取什么行动以实现他的目标。

Action Space#

即 Huggy 可以执行的动作

Pasted image 20240924234309

关节电机驱动 Huggy 的腿部。

因此为了达到目标，Huggy 需要学会如何正确旋转每条腿的关节电机来移动。

reward function#

因此我们的奖励函数：

方向奖励：奖励接近目标。
达成目标奖励：我们奖励 Huggy 达成目标。
时间惩罚：每次行动时给予的固定时间惩罚，迫使尽快到达棍子。
旋转惩罚：惩罚过多旋转且过快的转动。

Q-Learning 简介#

value-based

v_{\pi}(s) = \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \,|\, S_t = s \right]

从状态 s 开始，我们按照策略 $\pi$ 行动。
我们会累积未来的奖励，但越远的奖励被折扣因子 $\gamma$ 减少其影响。
值函数计算的是从当前状态开始，整个未来的 “回报” 期望值。

the goal of an RL agent is to have an optimal policy π*

Value 和 Policy 的关系#

找到最优的值函数就可以导出最优的策略

\pi^*(s) = \arg \max_{a} Q^*(s, a)

$\pi^*(s)$ ：表示最优策略，在状态 $s$ 时应该采取的最佳行动。
$Q^*(s, a)$ ：表示state - action 值函数，它代表在状态 $s$ 下选择动作 $a$ 时，未来所有可能的折扣回报的期望值。
$\arg \max_{a}$ ：表示选择能使 $Q^*(s, a)$ 最大的动作 $a$ 。即找到使得预期回报最大化的动作。

这个公式的核心观点是，如果我们有了一个最优的 $Q^*(s, a)$ 函数，那么我们就可以通过选择能够最大化 $Q^*(s, a)$ 的动作来确定最优策略 $\pi^*(s)$ 。也就是说，最优策略是在每个状态 $s$ 下，选择使得未来期望回报最大的动作 $a$ 。

两种 Value Based Methods#

想象老鼠在迷宫里寻找奶酪的场景：

状态价值函数 相当于老鼠在某个位置（状态）时的心情预期：“如果我从这里开始按照我的策略行动，我有多大机会找到奶酪？”
动作价值函数 则更进一步：“如果我从这里出发，并且选择向右移动，我的成功概率是多少？” 动作价值函数帮助老鼠评估在每个状态下执行不同动作的效果，从而更有针对性地选择行动方向。

1. 状态价值函数（State Value Function）#

状态价值函数 $V_\pi(s)$ 评估在特定策略 $\pi$ 下，从给定状态 $s$ 出发，期望获得的累计奖励。换句话说，它衡量的是 “如果我现在处于状态 $s$ ，并遵循策略 $\pi$ ，那么我的长期收益会是多少”。

V_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]

$V_\pi(s)$ ：状态 $s$ 的价值，即从 $s$ 出发，遵循策略 $\pi$ 所能期望得到的累积回报。
$G_t$ ：从时间步 $t$ 开始的累积奖励，通常表示为 $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$ ，其中 $\gamma$ 是折扣因子。
$\mathbb{E}_\pi[\cdot]$ ：表示在策略 $\pi$ 下的期望。

假设我们有一个迷宫，老鼠从某个位置（状态 $s$ ）开始，遵循某种策略来寻找奶酪。状态价值函数可以告诉我们：如果老鼠从当前位置开始，它期望可以多快找到奶酪。

Screenshot 2024-09-30 at 20.30.51

上图的例子中，每个方格的数值表示某个状态的价值。如状态 $s$ 的值是 $-6$ ，意味着老鼠从这里开始期望的累积奖励较差（可能因为距离奶酪远），而越接近奶酪的状态（如值为 $-2$ ）则有较好的预期回报。

2. 动作价值函数（Action Value Function）#

动作价值函数 $Q_\pi(s, a)$ 评估在特定策略 $\pi$ 下，从给定状态 $s$ 采取动作 $a$ 后，期望获得的累计奖励。它不仅仅考虑状态的价值，还评估从该状态出发，选择某个特定动作 $a$ 后的预期收益。

Q_\pi(s, a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a]

$Q_\pi(s, a)$ ：状态 - 动作对 $(s, a)$ 的价值，即从状态 $s$ 选择动作 $a$ 并遵循策略 $\pi$ 所能期望得到的累积回报。
与状态价值函数不同，动作价值函数评估从状态 $s$ 开始执行特定动作 $a$ 的长期回报。

Screenshot 2024-10-01 at 00.43.07

还是以上述的迷宫为例，假设老鼠现在在状态 $s$ ，可以选择四个方向（上、下、左、右）来寻找奶酪。动作价值函数 $Q_\pi(s, a)$ 可以告诉我们老鼠选择每个方向后会有什么期望回报。例如，从某状态 $s$ 向右移动的价值可能比向左移动的价值高，因为向右移动会更快接近奶酪。

区别总结#

状态价值函数 $V_\pi(s)$ 只考虑在某一状态下，按照策略执行未来动作的累计期望回报。它不关注具体采取了哪个动作。
动作价值函数 $Q_\pi(s, a)$ 则更加精细，它不仅考虑从某一状态开始的回报，还关注在该状态下执行特定动作后的期望回报。

贝尔曼方程#

还是前面的例子，老鼠从状态 $St$ 开始，每走一步得到的奖励是 -1：

V(St) = (-1) + (-1) + (-1) + (-1) + (-1) + (-1) = -6

这表示老鼠从状态 $St$ 开始到达终点的累积回报是 -6。

V(St+1) = (-1) + (-1) + (-1) + (-1) + (-1) = -5

像上面这样直接计算每个状态的累积回报显然是一个高成本的过程，因为我们需要考虑每个可能的路径及其奖励，同时还有大量重复计算项。贝尔曼方程为我们提供了一种更简洁的递归方法来解决这个问题。

贝尔曼方程的核心思想是：我们可以把一个状态的价值表示为该状态的即时奖励加上未来状态价值的折扣和。公式如下：

V_\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma V_\pi(S_{t+1}) | S_t = s]

这样就不需要从头计算每个状态的累积回报，而是递归地将即时奖励和下一个状态的价值相加。

让我们回到之前的例子。如果我们已经知道状态 $St+1$ 的价值是 -5，那么状态 $St$ 的价值可以通过贝尔曼方程递归计算得到：

V(St) = R_{t+1} + \gamma V(St+1)

如果不进行折扣（即 $\gamma = 1$ ），并且知道 $V(St+1) = -5$ ，即时奖励 $R_{t+1} = -1$ ，那么：

Screenshot 2024-10-01 at 01.02.43

这与我们之前直接计算的结果一致。

折扣因子 $\gamma$ 的作用#

贝尔曼方程中的折扣因子 $\gamma$ 决定了我们对未来奖励的重视程度。

如果 $\gamma$ 很低（例如 0.1 或 0），那么我们几乎完全忽略未来奖励，关注的是当前的即时回报。
如果 $\gamma = 1$ ，我们考虑未来所有的奖励，未来的每一步与当前同样重要。
如果 $\gamma$ 过大（比如百万），它实际上失去了物理意义，因为未来的价值会被无限夸大，这在实际应用中是不合理的。

蒙特卡洛方法与时序差分学习#

Monte Carlo 和 Temporal Difference Learning 是两种不同的训练价值函数或策略函数的策略，它们都利用经验来解决强化学习问题。

Monte Carlo: 在回合结束时学习#

蒙特卡洛方法（Monte Carlo Approach） 是一种通过反复采样来估计状态或状态 - 动作对价值的方法。在这个方法中，我们会在每一集结束后，根据该集的完整经验来更新价值函数。下面将通过一个具体的例子来详细说明蒙特卡洛方法的工作原理。

记录状态、动作、奖励、以及下一个状态：
- 每当智能体进行一个动作，它会记录当时的状态、采取的动作、所获得的奖励，以及它转移到的下一个状态。
计算总的回报 $G_t$ ：
- 智能体将累积该集中的所有奖励，计算总的回报 $G_t$ ，用以评估当前策略的表现。
更新价值函数 $V(s)$ ：
- 更新某个状态 $s$ 的价值估计，公式如下：
  $V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)]$

其中：

$\alpha$ 是学习率，表示更新步长。
$G_t$ 是实际获得的总回报。
$V(S_t)$ 是当前对状态 $S_t$ 的价值估计。

更新后，智能体会以新的状态价值函数开始下一集，并通过多次游戏不断学习、改进其策略。

还是以同样地场景为例：

假设在游戏一开始，老鼠对每个状态的价值都是 0（即 $V(S) = 0$ ）。
学习率 $\alpha = 0.1$ ，且我们不进行折扣（即 $\gamma = 1$ ）。
老鼠在探索过程中获得了一系列奖励，假设累积回报 $G_0 = 3$ 。

Pasted image 20241001011239

算法流程：

回报 $G_0 = 3$ 。
更新状态价值 $V(S_0)$ ：
$V(S_0) = V(S_0) + \alpha [G_0 - V(S_0)]$
带入已知值：
$V(S_0) = 0 + 0.1 \times (3 - 0) = 0.3$

通过这集的更新，老鼠对状态 $S_0$ 的价值估计变为了 0.3。

时序差分学习：在每一步学习#

相比于蒙特卡洛方法，时序差分学习（Temporal Difference Learning，TD 学习） 不需要等到一整集结束后再更新，而是基于一步的经验来逐步调整。更新的依据是从当前状态 $S_t$ 出发，观察到的即时奖励 $R_{t+1}$ 和下一个状态 $S_{t+1}$ 的估计价值。

公式如下：

V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]

其中：

$\alpha$ 是学习率。
$R_{t+1}$ 是即时奖励。
$\gamma$ 是折扣因子，控制未来奖励的权重。

这个更新方式叫做自举法（Bootstrapping），因为它部分基于已有的价值估计（即 $V(S_{t+1})$ ）来进行更新，而不是完整的样本 $G_t$ 。

继续我们的老鼠找奶酪：

初始化价值函数：一开始，我们假设每个状态的价值都为 0。
智能体进行探索：老鼠从某个状态 $S_0$ 开始，随机选择一个动作，假设老鼠向左移动并吃到了奶酪。此时它获得了即时奖励 $R_{t+1} = 1$ 。
计算 TD 目标：
TD 目标是即时奖励加上下一个状态的折扣值：

$TD_{Target} = R_{t+1} + \gamma V(S_{t+1})$

在这个例子中，假设下一个状态的价值 $V(S_1) = 0$ 且 $\gamma = 1$ ，那么：

$TD_{Target} = 1 + 1 \times 0 = 1$
更新价值函数：
使用 TD 目标更新状态 $S_0$ 的价值：

$V(S_0) = V(S_0) + \alpha [TD_{Target} - V(S_0)]$

代入值：

$V(S_0) = 0 + 0.1 \times (1 - 0) = 0.1$

这样，老鼠在每一步后都会更新当前状态的价值。随着老鼠不断地与环境交互，价值函数会逐步反映各个状态的真实价值。

对比总结：从偏差与方差的角度#

蒙特卡洛方法：等待整个回合结束后，通过计算累计回报来更新价值函数。它使用的是真实的回报值 $G_t$ 。由于是基于一整集的经验来更新价值函数，因此它能提供比较准确的价值估计，尤其适合在没有明确的模型或转移概率情况下使用。

\text{Monte Carlo:} \quad V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)]

- **无偏性**：蒙特卡洛方法直接从实际经验中获得完整回报，因此是无偏的，即估计的期望值和真实期望值相符。 
- **高方差**：由于计算的是整个回合的回报，涉及多步的状态转移和奖励，导致估计的方差较高。
- MC 方法不会受到偏差的影响。方差高但无偏，适合全局经验的评估。

时序差分学习：在每一步之后及时更新价值函数，可以在没有完整回报的情况下学习，使用的是估计的回报，即 $R_{t+1} + \gamma V(S_{t+1})$ 来替代 $G_t$ 。

\text{TD Learning:} \quad V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]

- **有偏性**：TD 方法使用的是自举，即初始值通常是任意的，并不一定准确，导致初期存在偏差，但随着更多真实经验的累积，偏差会逐渐减小。 偏差的存在可能导致严重问题，特别是在使用 off-policy + 函数逼近器（如神经网络）时再加上 bias 时，往往会收敛失败。Sutton 和 Barto 提出的 **“deadly triad”** 指的正是这种情况。
- **低方差**：因为只涉及单步的状态转移和奖励，其方差相对较低。
- 方差低但有偏，初期估计不准，但适合实时更新。

Q-Learning 相关术语#

Q-Learning 是一种off-policy 的 value-based 方法，采用 TD 方法来训练其动作价值函数：Q 函数。Q 这一字母代表 “Quality”，即在该状态下该行动的价值。

Screenshot 2024-10-01 at 17.47.52

给定一个状态和动作，Q 函数输出一个 state-action value（也称为 Q value）

这里再回顾一下 Value 和 Reward 之间的区别：

术语	解释
状态的价值	预期累积奖励，即智能体从某个状态开始并依据策略行动时，期望获得的总奖励。
奖励	在某个状态下执行一个动作后，从环境中获得的即时反馈。

在内部，我们的 Q 函数由一个 Q Table 编码，该表中的每个单元格对应一个状态 - 动作对值。可以将这个 Q Table 视为 Q 函数的记忆（Cheat Sheet）

Pasted image 20241001182112

可以看到初始状态和向上移动的 state-action value 为 0

因此当训练完成后会得到一个最优的 Q 函数，这意味着我们拥有了一个最优的 Q Table，相当于就拥有了一个最优策略，因为我们可以通过 Q Table 得知在每个状态下采取的最佳行动。

\pi^*(s) = \arg \max_a Q^*(s, a)

算法流程#

好恐怖的 pseudocode：

Pasted image 20241001193949

Step 1: 初始化 Q 表#

为每个 state-action pair 初始化 Q 表。大多数情况下用 0 进行初始化。
Screenshot 2024-10-01 at 19.47.59

def initialize_q_table(state_space, action_space):
	Qtable = np.zeros((state_space, action_space))
	return Qtable

Step 2：用 ε- 贪心策略选择一个 action#

ε- 贪心策略是一种在探索 / 利用之间 trade-off 的策略。通过逐渐减少探索的概率，agent 在学习的初期倾向于探索新动作，而在后期则更加依赖已学得的知识来选择最佳动作。

以概率 $1 - \epsilon$ ：选择当前 Q-table 中 Q 值最高的动作（利用）。
以概率 $\epsilon$ ：随机选择一个动作（探索）。

Screenshot 2024-10-01 at 19.49.27

初始阶段：当 $\epsilon = 1.0$ 时，agent 完全进行探索，即随机选择动作。
训练过程：随着训练的进行， $\epsilon$ 逐渐减小（如指数衰减），agent 越来越多地选择当前估计最优的动作，即进行利用。

Pasted image 20241001200750

def greedy_policy(Qtable, state):
    # 利用：选择具有最高状态-动作值的动作
    # 经典的 Q-learning 操作：查询 Q 表，获取当前状态下奖励最高的动作。
    # 简单、直接，就是纯粹的“利用”。
    action = np.argmax(Qtable[state][:])  # np.argmax 找到最大值的索引。
    return action

def epsilon_greedy_policy(Qtable, state, epsilon):
    random_num = random.uniform(0,1) # 随机数
    
    # 如果随机数 > epsilon --> 利用
    # 这是关键：在 1 - epsilon 的概率下，我们选择利用，
    # 贪婪地选择 Q 表中最好的动作。
    if random_num > epsilon:
        # 在给定状态下，选择最高值的动作
        action = greedy_policy(Qtable, state)
    
    # 否则 --> 探索
    # 如果随机数小于 epsilon，智能体会进行探索，
    # 随机选择一个动作，尝试新的可能。
    else:
        action = env.action_space.sample()  # 探索：选择一个随机动作。
    
    return action

Step 3：执行动作 $A_t$ ，获得奖励 $R_{t+1}$ 并进入下一状态 $S_{t+1}$ #

在 Q-learning 中，这一步是算法的核心。当 agent 执行动作 $A_t$ 时，它会从环境中得到反馈（奖励 $R_{t+1}$ ），并且转移到新的状态 $S_{t+1}$ 。此时，agent 不仅需要考虑当前获得的即时奖励，还需要评估未来的潜在回报。

这就引出了 Q-learning 的更新公式。

Step 4：更新 $Q(S_t, A_t)$ #

Q-learning 使用一个非常重要的更新规则，即在前面时序差分学习中见过的自举：

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t) \right]

$Q(S_t, A_t)$ 是我们当前对状态 - 动作对的估计值。
$R_{t+1}$ 是 agent 在执行动作 $A_t$ 后获得的即时奖励。
$\max_a Q(S_{t+1}, a)$ 是在下一状态 $S_{t+1}$ 中，基于当前策略选择最优动作的 Q 值。
$\alpha$ 是学习率，它决定了我们更新 Q 值的速度。
$\gamma$ 是折扣因子，用来平衡即时奖励和未来奖励的权重。

通过这种方式，Q-learning 的每一步更新都会根据下一状态的最优 Q 值进行调整。

def train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable):
  # 外部训练循环：执行 n_training_episodes 次的学习
  for episode in tqdm(range(n_training_episodes)):
    # epsilon 衰减：随着训练的进行，epsilon 会逐渐减少，减少探索的概率，增加利用
    epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode)

    # 每轮开始时，重置环境，获得初始状态
    state, info = env.reset()
    step = 0
    terminated = False
    truncated = False
    # 每一轮，智能体会和环境交互，最多执行 max_steps 步
    for step in range(max_steps):
      # 使用 epsilon greedy 策略选择动作
      action = epsilon_greedy_policy(Qtable, state, epsilon)
      # 执行动作，并观察新状态、新奖励
      new_state, reward, terminated, truncated, info = env.step(action)

      # 更新 Q 值：
      # Q(s,a) = Q(s,a) + 学习率 * (奖励 + 折扣因子 * max(Q(s',a')) - Q(s,a))
      Qtable[state][action] = Qtable[state][action] + learning_rate * (reward + gamma * np.max(Qtable[new_state]) - Qtable[state][action])
      # 如果智能体在当前状态结束了（成功或失败），停止此轮训练
      if terminated or truncated:
        break

      # 将智能体的下一个状态设置为新的状态
      state = new_state
  return Qtable

Screenshot 2024-10-02 at 00.38.10

Off-policy vs On-policy#

现在，让我们讨论策略的两种类型 ——Off-policy 和 On-policy。

从策略学习的角度来看，二者的关键区别在于：

On-policy：学习的是当前正在执行的策略，agent 实际的行为与学习的策略一致。
Off-policy：学习的是不同于当前执行的策略，即使 agent 执行的是探索策略，更新时依然基于最优策略。

Off-policy (异策略)#

Off-policy 对于执行动作（acting policy）和更新 Q 值（updating policy）使用两种不同的策略。在前面我们介绍的 Q-learning 中，agent 使用 epsilon-greedy 策略进行动作选择（acting policy），但在更新 Q 值时，使用贪心策略（greedy policy）找到最优动作。

例如，在更新 Q 值时，agent 会选择下一个状态中最优的动作 $a$ ，即：

\gamma \max_a Q(S_{t+1}, a)

这意味着，即使我们当前策略是 epsilon-greedy，也总是使用贪心策略更新 Q 值，从而加快收敛速度。这也是 Q-learning 被称为 Off-policy 算法的原因。

On-policy (同策略)#

而 On-policy 则要求同一个策略同时用于执行动作和更新 Q 值。例如，在 SARSA 算法中，更新时选择的动作也是基于当前策略，而不是贪心策略。这意味着 agent 始终使用 epsilon-greedy 策略选择和更新动作，导致学习过程更贴近实际执行策略。

用一个例子来理解：

SARSA（On-policy）：假设 agent 现在在一个状态 $S_t$ ，它选择了一个动作 $A_t$ ，接着进入了新状态 $S_{t+1}$ ，并选择了新的动作 $A_{t+1}$ 。SARSA 用 $A_{t+1}$ （基于当前 epsilon-greedy 策略选择的动作）来更新 Q 值。
Q-learning（Off-policy）：在同样的情况下，Q-learning 也是从 $S_t$ 选择动作 $A_t$ ，进入状态 $S_{t+1}$ 。但在更新 Q 值时，它并不管在 $S_{t+1}$ 实际上选择了哪个动作 $A_{t+1}$ ，而是用 $S_{t+1}$ 中所有动作的最大 Q 值（即最优策略）来更新 Q 值。

Let's Dive Deeper!#

如果只是像 “Frozen Lake” 这样的小游戏，建立一个 Q 表显然可以在较短的时间内得到优秀的 Q 函数。

但当环境变为《Doom》这样拥有庞大状态空间（数百万种不同状态）的游戏或现实模拟器，此时创建和更新 Q 表的效率将十分低下。

这就是为什么现在要引入深度 Q 学习，使用一个神经网络来近似给定状态下每个动作的不同 Q 值。