Q-Learning 算法

Q-Learning 是强化学习中最经典、最重要的算法之一。它是一种无模型的时序差分学习方法，能够通过与环境的交互直接学习最优策略，而不需要环境的转移概率模型。

Q-Learning 的核心思想

Q-Learning 的核心思想非常直观：通过不断尝试，学习每个状态-动作对的价值（Q值），然后根据 Q 值选择最优动作。

为什么叫 Q-Learning？

Q 代表 Quality（质量），Q(s,a) 表示在状态 s 执行动作 a 的"质量"或"价值"。Q-Learning 的目标就是学习一个最优的 Q 函数 $Q^*(s,a)$，使得智能体能够做出最优决策。

Q-Learning 的特点

• 无模型：不需要知道环境的转移概率和奖励函数
• 离线策略：可以从任意策略产生的经验中学习最优策略
• 时序差分：结合了蒙特卡洛和动态规划的优点
• 收敛保证：在满足一定条件下保证收敛到最优策略

Q 值更新公式

Q-Learning 的核心是 Q 值的更新公式：

$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$

其中：

• $\alpha$ 是学习率，控制更新的步长
• $r$ 是即时奖励
• $\gamma$ 是折扣因子
• $\max_{a'} Q(s',a')$ 是下一状态的最大 Q 值

理解更新公式

让我们深入理解这个公式的含义：

1. 当前估计：$Q(s,a)$ 是对状态-动作价值的当前估计
2. 目标值：$r + \gamma \max_{a'} Q(s',a')$ 是基于实际经验的目标值
   • $r$ 是实际获得的即时奖励
   • $\max_{a'} Q(s',a')$ 是对下一状态最优价值的估计
3. 时序差分误差：$\delta = r + \gamma \max_{a'} Q(s',a') - Q(s,a)$
   • 表示目标值与当前估计的差距
4. 更新：用时序差分误差修正当前估计

与贝尔曼方程的关系

Q-Learning 的更新公式直接来自贝尔曼最优方程：

$Q^*(s,a) = \mathbb{E}[r + \gamma \max_{a'} Q^*(s',a')]$

Q-Learning 通过采样来估计期望值，而不是精确计算。

Q-Learning 算法流程

算法伪代码

初始化 Q(s,a) 为任意值（通常为 0）
对于每个回合：
    初始化状态 s
    对于每个时间步：
        使用策略（如 ε-贪婪）选择动作 a
        执行动作 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

class QLearning:
    def __init__(self, num_states, num_actions, learning_rate=0.1, 
                 discount_factor=0.99, epsilon=0.1):
        self.num_states = num_states
        self.num_actions = num_actions
        self.lr = learning_rate
        self.gamma = discount_factor
        self.epsilon = epsilon
        self.q_table = np.zeros((num_states, num_actions))
    
    def select_action(self, state):
        if np.random.random() < self.epsilon:
            return np.random.randint(self.num_actions)
        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
    
    def train(self, env, num_episodes=1000):
        rewards_history = []
        
        for episode in range(num_episodes):
            state = env.reset()
            total_reward = 0
            done = False
            
            while not done:
                action = self.select_action(state)
                next_state, reward, done, _ = env.step(action)
                self.update(state, action, reward, next_state, done)
                state = next_state
                total_reward += reward
            
            rewards_history.append(total_reward)
        
        return rewards_history

探索与利用

Q-Learning 需要在探索新策略和利用已知好策略之间取得平衡。

ε-贪婪策略

最常用的平衡方法是 ε-贪婪策略：

• 以概率 ε 随机选择动作（探索）
• 以概率 1-ε 选择当前最优动作（利用）

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

ε 衰减策略

随着学习的进行，逐渐减小 ε：

class EpsilonDecay:
    def __init__(self, start=1.0, end=0.01, decay=0.995):
        self.epsilon = start
        self.end = end
        self.decay = decay
    
    def get_epsilon(self):
        epsilon = self.epsilon
        self.epsilon = max(self.end, self.epsilon * self.decay)
        return epsilon

其他探索策略

UCB（Upper Confidence Bound）：

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

其中 $n$ 是状态访问次数，$n_a$ 是动作选择次数。

Boltzmann 探索：

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

其中 $\tau$ 是温度参数。

示例：悬崖行走

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

import numpy as np
import matplotlib.pyplot as plt

class CliffWalking:
    def __init__(self, width=12, height=4):
        self.width = width
        self.height = height
        self.start = (height - 1, 0)
        self.goal = (height - 1, width - 1)
        self.cliff = [(height - 1, i) for i in range(1, width - 1)]
        self.state = self.start
        
    def reset(self):
        self.state = self.start
        return self._state_to_idx(self.state)
    
    def _state_to_idx(self, state):
        return state[0] * self.width + state[1]
    
    def step(self, action):
        row, col = self.state
        
        if action == 0:    # 上
            row = max(0, row - 1)
        elif action == 1:  # 下
            row = min(self.height - 1, row + 1)
        elif action == 2:  # 左
            col = max(0, col - 1)
        elif action == 3:  # 右
            col = min(self.width - 1, col + 1)
        
        self.state = (row, col)
        
        if self.state in self.cliff:
            return self.reset(), -100, True
        elif self.state == self.goal:
            return self._state_to_idx(self.state), -1, True
        else:
            return self._state_to_idx(self.state), -1, False

env = CliffWalking()
agent = QLearning(
    num_states=env.width * env.height,
    num_actions=4,
    learning_rate=0.5,
    discount_factor=0.99,
    epsilon=0.1
)

rewards = agent.train(env, num_episodes=500)

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

Q-Learning 的收敛性

收敛条件

Q-Learning 在以下条件下保证收敛：

1. 所有状态-动作对被无限次访问
2. 学习率满足 Robbins-Monro 条件：
   • $\sum_{t=0}^{\infty} \alpha_t = \infty$
   • $\sum_{t=0}^{\infty} \alpha_t^2 < \infty$

学习率的选择

常用的学习率设置：

def get_learning_rate(episode, min_lr=0.01):
    return max(min_lr, 1.0 / (1 + episode * 0.01))

Q-Learning 的局限性

表格型方法的限制

Q-Learning 使用表格存储 Q 值，这在以下情况下会遇到问题：

1. 状态空间大：表格大小随状态数线性增长
2. 连续状态空间：无法用表格表示无限状态
3. 泛化能力弱：无法利用状态之间的相似性

解决方案

深度 Q 网络（DQN）使用神经网络来近似 Q 函数，解决了上述问题。下一章将详细介绍 DQN。

Q-Learning vs SARSA

SARSA 是另一种时序差分算法，与 Q-Learning 的主要区别：

特性	Q-Learning	SARSA
类型	离线策略	在线策略
更新目标	$\max_{a'} Q(s',a')$	$Q(s',a')$
学习策略	最优策略	当前策略
风险行为	可能学到危险策略	更保守

Q-Learning 的更新：

$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$

SARSA 的更新：

$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s',a') - Q(s,a)]$

完整示例：CartPole

import gymnasium as gym
import numpy as np

class CartPoleQLearning:
    def __init__(self, num_bins=10):
        self.env = gym.make('CartPole-v1')
        self.num_bins = num_bins
        
        self.state_bins = [
            np.linspace(-4.8, 4.8, num_bins),
            np.linspace(-4, 4, num_bins),
            np.linspace(-0.418, 0.418, num_bins),
            np.linspace(-4, 4, num_bins),
        ]
        
        self.num_states = num_bins ** 4
        self.num_actions = 2
        self.q_table = np.zeros((self.num_states, self.num_actions))
        
    def discretize(self, state):
        indices = []
        for i, val in enumerate(state):
            idx = np.digitize(val, self.state_bins[i]) - 1
            idx = max(0, min(idx, self.num_bins - 1))
            indices.append(idx)
        return sum(idx * (self.num_bins ** i) for i, idx in enumerate(indices))
    
    def train(self, num_episodes=5000, lr=0.1, gamma=0.99, 
              epsilon_start=1.0, epsilon_end=0.01, epsilon_decay=0.995):
        epsilon = epsilon_start
        rewards = []
        
        for episode in range(num_episodes):
            state, _ = self.env.reset()
            state = self.discretize(state)
            total_reward = 0
            done = False
            
            while not done:
                if np.random.random() < epsilon:
                    action = self.env.action_space.sample()
                else:
                    action = np.argmax(self.q_table[state])
                
                next_state, reward, terminated, truncated, _ = self.env.step(action)
                done = terminated or truncated
                next_state = self.discretize(next_state)
                
                best_next = np.max(self.q_table[next_state])
                td_target = reward + gamma * best_next * (1 - done)
                td_error = td_target - self.q_table[state, action]
                self.q_table[state, action] += lr * td_error
                
                state = next_state
                total_reward += reward
            
            rewards.append(total_reward)
            epsilon = max(epsilon_end, epsilon * epsilon_decay)
            
            if (episode + 1) % 100 == 0:
                avg_reward = np.mean(rewards[-100:])
                print(f"Episode {episode + 1}, Avg Reward: {avg_reward:.2f}, Epsilon: {epsilon:.3f}")
        
        return rewards

agent = CartPoleQLearning()
rewards = agent.train()

小结

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

• 核心思想：通过交互学习状态-动作价值函数
• 更新公式：$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$
• 特点：无模型、离线策略、时序差分
• 探索策略：ε-贪婪、ε 衰减、UCB、Boltzmann
• 局限性：表格型方法无法处理大规模或连续状态空间

Q-Learning 为深度强化学习奠定了基础。下一章将介绍 SARSA 算法，然后进入深度 Q 网络（DQN）的学习。