Q-Learning 算法

Q-Learning 是强化学习中最经典、最重要的算法之一，由 Watkins 于 1989 年提出。它是第一个被证明能够收敛到最优策略的离线策略算法，为后来的深度强化学习奠定了基础。理解 Q-Learning 对于掌握整个强化学习领域至关重要。

算法思想

核心理念

Q-Learning 的核心思想非常直观：如果我们能够估计每个状态-动作对的价值（即 Q 值），那么最优策略就是简单地选择 Q 值最大的动作。问题在于，我们如何估计这些 Q 值？

Q-Learning 给出的答案是：通过不断尝试和观察，逐步修正我们对 Q 值的估计。每次执行一个动作后，我们观察得到的奖励和下一状态，然后用这些信息来更新当前状态-动作对的 Q 值估计。

在线策略 vs 离线策略

理解 Q-Learning 需要先理解两个重要概念：

在线策略（On-Policy）：学习和行为使用同一个策略。智能体根据当前策略选择动作，然后用这些动作的经验来更新策略。

离线策略（Off-Policy）：学习和行为使用不同的策略。智能体可以用任意策略（如随机探索）收集经验，然后学习最优策略的价值。

Q-Learning 是离线策略算法，这意味着：

• 它可以学习最优策略，而不管智能体实际执行的是什么策略
• 它可以利用历史数据（经验回放）进行学习
• 它具有更好的样本效率

Q-Learning 算法详解

算法形式化

Q-Learning 的更新公式如下：

$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_t + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t) \right]$

其中：

• $Q(s_t, a_t)$ 是当前对状态-动作对价值的估计
• $\alpha \in (0, 1]$ 是学习率，控制更新幅度
• $r_t$ 是即时奖励
• $\gamma$ 是折扣因子
• $\max_a Q(s_{t+1}, a)$ 是下一状态的最大 Q 值

更新公式的解读

让我们深入理解这个更新公式：

TD 目标（TD Target）： $y_t = r_t + \gamma \max_a Q(s_{t+1}, a)$

TD 目标是对 $Q(s_t, a_t)$ 的一个新估计。它由两部分组成：

1. 即时奖励 $r_t$：执行动作后立即获得的反馈
2. 折扣后的最大未来价值 $\gamma \max_a Q(s_{t+1}, a)$：假设从下一状态开始采取最优行动所能获得的价值

TD 误差（TD Error）： $\delta_t = r_t + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t)$

TD 误差反映了当前估计与新观测之间的差距。如果 TD 误差为正，说明我们低估了这个状态-动作对的价值；如果为负，说明我们高估了。

更新规则： $Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \delta_t$

更新规则将 Q 值向 TD 目标方向移动，移动幅度由学习率 $\alpha$ 控制。

为什么使用 max？

Q-Learning 使用 $\max_a Q(s_{t+1}, a)$ 而不是 $Q(s_{t+1}, a_{t+1})$，这是它能够学习最优策略的关键。

考虑贝尔曼最优方程： $Q^*(s, a) = \mathbb{E}\left[r + \gamma \max_{a'} Q^*(s', a')\right]$

这个方程告诉我们，最优 Q 值满足：执行动作后的期望回报等于即时奖励加上折扣后的最优未来价值。Q-Learning 的更新正是对这个方程的逐步逼近。

与 SARSA 的关键区别：

SARSA 使用实际选择的下一个动作 $a_{t+1}$ 来更新： $Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)]$

这意味着 SARSA 学习的是当前策略的价值，而不是最优策略的价值。如果策略包含探索行为（如 ε-greedy），SARSA 会考虑这些探索动作的影响，学到的策略会更保守。而 Q-Learning 忽略探索行为，总是假设未来会选择最优动作，因此学习的是理论最优策略。

为什么使用 max？

Q-Learning 使用 $\max_a Q(s_{t+1}, a)$ 而不是 $Q(s_{t+1}, a_{t+1})$，这是它能够学习最优策略的关键。

考虑贝尔曼最优方程： $Q^*(s, a) = \mathbb{E}\left[r + \gamma \max_{a'} Q^*(s', a')\right]$

这个方程告诉我们，最优 Q 值满足：执行动作后的期望回报等于即时奖励加上折扣后的最优未来价值。Q-Learning 的更新正是对这个方程的逐步逼近。

算法伪代码

初始化 Q(s, a) 为任意值（终止状态 Q = 0）
对于每个回合：
    初始化状态 s
    对于每一步：
        使用策略从 s 选择动作 a（如 ε-greedy）
        执行动作 a，观察 r 和 s'
        Q(s, a) ← Q(s, a) + α[r + γ max_a' Q(s', a') - Q(s, a)]
        s ← s'
    直到 s 是终止状态

Python 实现

import numpy as np
from collections import defaultdict

class QLearning:
    def __init__(self, n_actions, learning_rate=0.1, discount_factor=0.99,
                 epsilon=0.1):
        self.n_actions = n_actions
        self.lr = learning_rate
        self.gamma = discount_factor
        self.epsilon = epsilon
        self.q_table = defaultdict(lambda: np.zeros(n_actions))
    
    def get_action(self, state):
        if np.random.random() < self.epsilon:
            return np.random.randint(self.n_actions)
        else:
            return np.argmax(self.q_table[state])
    
    def update(self, state, action, reward, next_state, done):
        current_q = self.q_table[state][action]
        
        if done:
            target = reward
        else:
            target = reward + self.gamma * np.max(self.q_table[next_state])
        
        td_error = target - current_q
        self.q_table[state][action] += self.lr * td_error
        
        return td_error
    
    def get_policy(self):
        policy = {}
        for state in self.q_table:
            policy[state] = np.argmax(self.q_table[state])
        return policy

def train_qlearning(env, agent, n_episodes=1000, max_steps=100):
    episode_rewards = []
    episode_lengths = []
    
    for episode in range(n_episodes):
        state = env.reset()
        total_reward = 0
        
        for step in range(max_steps):
            action = agent.get_action(state)
            next_state, reward, done, _ = env.step(action)
            
            agent.update(state, action, reward, next_state, done)
            
            state = next_state
            total_reward += reward
            
            if done:
                break
        
        episode_rewards.append(total_reward)
        episode_lengths.append(step + 1)
    
    return episode_rewards, episode_lengths

探索策略

Q-Learning 需要探索来发现好的状态-动作对。常用的探索策略有：

ε-Greedy 策略

以概率 ε 随机选择动作，以概率 1-ε 选择当前最优动作。

def epsilon_greedy(q_values, epsilon, n_actions):
    if np.random.random() < epsilon:
        return np.random.randint(n_actions)
    else:
        return np.argmax(q_values)

ε 的选择：

• 固定 ε：简单但可能收敛慢
• 衰减 ε：开始时高探索，后期高利用

class DecayEpsilonGreedy:
    def __init__(self, epsilon_start=1.0, epsilon_end=0.01, decay_steps=10000):
        self.epsilon_start = epsilon_start
        self.epsilon_end = epsilon_end
        self.decay_steps = decay_steps
        self.step = 0
    
    def get_epsilon(self):
        epsilon = self.epsilon_end + (self.epsilon_start - self.epsilon_end) * \
                  np.exp(-self.step / self.decay_steps)
        self.step += 1
        return epsilon
    
    def get_action(self, q_values, n_actions):
        epsilon = self.get_epsilon()
        if np.random.random() < epsilon:
            return np.random.randint(n_actions)
        return np.argmax(q_values)

UCB（Upper Confidence Bound）

UCB 根据不确定性进行探索，对访问次数少的动作给予更高的探索奖励。

$a_t = \arg\max_a \left[ Q(s, a) + c \sqrt{\frac{\ln t}{N(s,a)}} \right]$

其中 $N(s,a)$ 是状态-动作对的访问次数，$t$ 是总步数。

class UCBExploration:
    def __init__(self, n_actions, c=1.0):
        self.n_actions = n_actions
        self.c = c
        self.counts = defaultdict(lambda: np.zeros(n_actions))
        self.q_values = defaultdict(lambda: np.zeros(n_actions))
        self.total_steps = 0
    
    def get_action(self, state):
        self.total_steps += 1
        
        for a in range(self.n_actions):
            if self.counts[state][a] == 0:
                return a
        
        ucb_values = self.q_values[state] + \
                     self.c * np.sqrt(np.log(self.total_steps) / self.counts[state])
        
        return np.argmax(ucb_values)
    
    def update(self, state, action, reward):
        self.counts[state][action] += 1
        n = self.counts[state][action]
        q = self.q_values[state][action]
        self.q_values[state][action] = q + (reward - q) / n

玻尔兹曼探索

根据 Q 值的 softmax 分布选择动作。

$P(a|s) = \frac{\exp(Q(s,a)/\tau)}{\sum_{a'} \exp(Q(s,a')/\tau)}$

其中 $\tau$ 是温度参数，控制探索程度。

def boltzmann_exploration(q_values, temperature=1.0):
    scaled_q = q_values / temperature
    exp_q = np.exp(scaled_q - np.max(scaled_q))
    probs = exp_q / np.sum(exp_q)
    return np.random.choice(len(q_values), p=probs)

收敛性分析

收敛条件

Q-Learning 在以下条件下保证收敛到最优 Q 值：

1. 所有状态-动作对被无限次访问：需要足够的探索

2. 学习率满足 Robbins-Monro 条件： $\sum_t \alpha_t = \infty, \quad \sum_t \alpha_t^2 < \infty$

   常用选择：$\alpha_t = 1/(t+1)$ 或 $\alpha_t = 1/N(s,a)$

3. 折扣因子 $\gamma < 1$：确保回报有界

收敛证明思路

Q-Learning 的收敛性可以通过随机逼近理论证明。核心思想是：

1. 定义 Q-Learning 更新的算子 $T$： $(TQ)(s,a) = \mathbb{E}[r + \gamma \max_{a'} Q(s', a')]$

2. 证明 $T$ 是压缩映射： $||TQ_1 - TQ_2||_\infty \leq \gamma ||Q_1 - Q_2||_\infty$

3. 由压缩映射原理，$T$ 有唯一不动点 $Q^*$

4. Q-Learning 是随机版本的值迭代，在满足条件下收敛到 $Q^*$

收敛速度

Q-Learning 的收敛速度受以下因素影响：

因素	影响	建议
学习率	太大震荡，太小收敛慢	使用衰减学习率
探索策略	探索不足导致次优	使用适当的探索策略
奖励尺度	影响学习稳定性	归一化奖励
折扣因子	影响长期规划	根据任务选择

示例：悬崖行走

让我们用 Q-Learning 解决经典的悬崖行走问题：

import numpy as np
import matplotlib.pyplot as plt

class CliffWalkingEnv:
    def __init__(self, height=4, width=12):
        self.height = height
        self.width = width
        self.start = (height - 1, 0)
        self.goal = (height - 1, width - 1)
        self.cliff = [(height - 1, i) for i in range(1, width - 1)]
        self.actions = ['up', 'right', 'down', 'left']
        self.action_effects = {
            'up': (-1, 0), 'right': (0, 1),
            'down': (1, 0), 'left': (0, -1)
        }
    
    def reset(self):
        self.state = self.start
        return self.state
    
    def step(self, action):
        effect = self.action_effects[self.actions[action]]
        new_row = max(0, min(self.height - 1, self.state[0] + effect[0]))
        new_col = max(0, min(self.width - 1, self.state[1] + effect[1]))
        self.state = (new_row, new_col)
        
        if self.state in self.cliff:
            return self.start, -100, True
        elif self.state == self.goal:
            return self.state, 0, True
        else:
            return self.state, -1, False
    
    def render(self):
        grid = [['.' for _ in range(self.width)] for _ in range(self.height)]
        for c in self.cliff:
            grid[c[0]][c[1]] = 'C'
        grid[self.start[0]][self.start[1]] = 'S'
        grid[self.goal[0]][self.goal[1]] = 'G'
        grid[self.state[0]][self.state[1]] = 'P'
        
        for row in grid:
            print(' '.join(row))
        print()

env = CliffWalkingEnv()
agent = QLearning(n_actions=4, learning_rate=0.5, discount_factor=0.99, epsilon=0.1)

n_episodes = 500
episode_rewards = []

for episode in range(n_episodes):
    state = env.reset()
    total_reward = 0
    done = False
    
    while not done:
        action = agent.get_action(state)
        next_state, reward, done = env.step(action)
        agent.update(state, action, reward, next_state, done)
        state = next_state
        total_reward += reward
    
    episode_rewards.append(total_reward)

plt.figure(figsize=(10, 5))
plt.plot(episode_rewards)
plt.xlabel('Episode')
plt.ylabel('Total Reward')
plt.title('Q-Learning on Cliff Walking')
plt.show()

print("学到的策略：")
policy = agent.get_policy()
for row in range(env.height):
    for col in range(env.width):
        state = (row, col)
        if state in env.cliff:
            print('C', end=' ')
        elif state == env.goal:
            print('G', end=' ')
        elif state in policy:
            action = policy[state]
            arrows = ['↑', '→', '↓', '←']
            print(arrows[action], end=' ')
        else:
            print('.', end=' ')
    print()

Q-Learning vs SARSA

Q-Learning 和 SARSA 是两种经典的表格型算法，它们的主要区别在于更新公式：

SARSA 更新

$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \right]$

SARSA 使用实际采取的下一个动作 $a_{t+1}$ 来更新 Q 值。

关键区别

特性	Q-Learning	SARSA
类型	离线策略	在线策略
更新目标	$\max_a Q(s', a)$	$Q(s', a')$
学习目标	最优策略价值	当前策略价值
探索影响	不受探索策略影响	受探索策略影响
收敛性	收敛到最优	收敛到当前策略

悬崖行走对比

在悬崖行走任务中，两种算法表现出明显不同的行为：

• Q-Learning：学习最优路径（沿着悬崖边缘走），但在执行时可能因为探索而掉入悬崖
• SARSA：学习更安全的路径（远离悬崖），因为它考虑了探索带来的风险

实际应用场景选择

理解两种算法的适用场景对实践非常重要：

选择 Q-Learning 的场景：

1. 离线学习：当有大量历史数据可用时，Q-Learning 可以充分利用这些数据
2. 仿真环境：在可以安全探索的仿真环境中，Q-Learning 能学到最优策略
3. 需要最优性能：当目标是找到理论最优策略时，Q-Learning 更合适
4. 经验回放：结合经验回放机制，Q-Learning 可以高效利用数据

选择 SARSA 的场景：

1. 在线学习：当智能体需要边学习边执行策略时，SARSA 更安全
2. 高风险环境：当探索失败代价很高时（如机器人控制、自动驾驶）
3. 策略评估：当需要评估特定策略的价值时
4. 稳定性要求：当需要稳定、可预测的行为时

一个具体例子：

假设你在训练一个机器人行走。如果是在仿真环境中训练，Q-Learning 是更好的选择，因为机器人可以安全地摔倒和尝试极端动作。但如果是在真实机器人上进行在线学习，SARSA 可能更合适，因为它会学习更保守的策略，避免机器人损坏。

def compare_qlearning_sarsa(env_class, n_episodes=500):
    qlearning_rewards = []
    sarsa_rewards = []
    
    q_agent = QLearning(n_actions=4, learning_rate=0.5, epsilon=0.1)
    sarsa_agent = SARSAAgent(n_actions=4, learning_rate=0.5, epsilon=0.1)
    
    for _ in range(n_episodes):
        env = env_class()
        qlearning_rewards.append(run_episode_qlearning(env, q_agent))
        
        env = env_class()
        sarsa_rewards.append(run_episode_sarsa(env, sarsa_agent))
    
    return qlearning_rewards, sarsa_rewards

qlearning_rewards, sarsa_rewards = compare_qlearning_sarsa(CliffWalkingEnv)

plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.plot(qlearning_rewards, label='Q-Learning')
plt.plot(sarsa_rewards, label='SARSA')
plt.xlabel('Episode')
plt.ylabel('Total Reward')
plt.legend()
plt.title('Learning Curves')

plt.subplot(1, 2, 2)
plt.bar(['Q-Learning', 'SARSA'], 
        [np.mean(qlearning_rewards[-50:]), np.mean(sarsa_rewards[-50:])])
plt.ylabel('Average Reward (last 50 episodes)')
plt.title('Final Performance')
plt.show()

Q-Learning 的局限性

维度灾难

Q-Learning 需要存储每个状态-动作对的 Q 值，当状态空间很大时，这变得不可行。

解决方案：使用函数近似（如神经网络），这就是 DQN 的思想。

最大化偏差

Q-Learning 使用 max 操作，会导致过高估计 Q 值。

原因：假设 Q 值估计有噪声，$\max_a Q(s,a)$ 倾向于选择被高估的动作。

解决方案：Double Q-Learning

class DoubleQLearning:
    def __init__(self, n_actions, learning_rate=0.1, discount_factor=0.99, epsilon=0.1):
        self.n_actions = n_actions
        self.lr = learning_rate
        self.gamma = discount_factor
        self.epsilon = epsilon
        self.q1 = defaultdict(lambda: np.zeros(n_actions))
        self.q2 = defaultdict(lambda: np.zeros(n_actions))
    
    def get_action(self, state):
        if np.random.random() < self.epsilon:
            return np.random.randint(self.n_actions)
        return np.argmax(self.q1[state] + self.q2[state])
    
    def update(self, state, action, reward, next_state, done):
        if np.random.random() < 0.5:
            best_next_action = np.argmax(self.q1[next_state])
            target = reward + self.gamma * self.q2[next_state][best_next_action] * (1 - done)
            self.q1[state][action] += self.lr * (target - self.q1[state][action])
        else:
            best_next_action = np.argmax(self.q2[next_state])
            target = reward + self.gamma * self.q1[next_state][best_next_action] * (1 - done)
            self.q2[state][action] += self.lr * (target - self.q2[state][action])

稀疏奖励问题

当奖励稀疏时，Q-Learning 很难学习到有价值的信息。

解决方案：

• 奖励塑形（Reward Shaping）
• 好奇心驱动探索
• HER（Hindsight Experience Replay）

实用技巧

学习率调度

class AdaptiveLearningRate:
    def __init__(self, initial_lr=0.5, min_lr=0.01, decay_rate=0.99):
        self.lr = initial_lr
        self.min_lr = min_lr
        self.decay_rate = decay_rate
    
    def get_lr(self):
        return self.lr
    
    def decay(self):
        self.lr = max(self.min_lr, self.lr * self.decay_rate)
    
    def update_by_visit(self, n_visits):
        self.lr = 1.0 / (n_visits + 1)

经验回放

虽然 Q-Learning 本身不需要经验回放，但使用经验回放可以提高样本效率：

class ReplayBuffer:
    def __init__(self, capacity=10000):
        self.buffer = []
        self.capacity = capacity
    
    def push(self, state, action, reward, next_state, done):
        if len(self.buffer) >= self.capacity:
            self.buffer.pop(0)
        self.buffer.append((state, action, reward, next_state, done))
    
    def sample(self, batch_size):
        indices = np.random.choice(len(self.buffer), batch_size, replace=False)
        return [self.buffer[i] for i in indices]

乐观初始化

将 Q 值初始化为较高的值，鼓励探索：

class OptimisticQLearning(QLearning):
    def __init__(self, n_actions, initial_value=10.0, **kwargs):
        super().__init__(n_actions, **kwargs)
        self.initial_value = initial_value
        self.q_table = defaultdict(lambda: np.ones(n_actions) * initial_value)

小结

Q-Learning 是强化学习的基石算法：

• 核心思想：通过 TD 学习估计最优动作价值函数
• 更新公式：$Q(s,a) \leftarrow Q(s,a) + \alpha[r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$
• 离线策略：可以学习最优策略，不受探索策略影响
• 收敛保证：在适当条件下收敛到最优 Q 值
• 局限性：维度灾难、最大化偏差、稀疏奖励

Q-Learning 为深度强化学习（DQN）奠定了基础。下一章将介绍 DQN，它将 Q-Learning 与深度神经网络结合，解决了高维状态空间的问题。

参考文献

1. Watkins, C. J., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3), 279-292.
2. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
3. Even-Dar, E., & Mansour, Y. (2003). Learning rates for Q-learning. Journal of Machine Learning Research, 5, 1-25.