第2章：多臂老虎机（Multi-armed Bandits）
一、导读
1.1 本章学习目标
第2章从最简单的强化学习问题——多臂老虎机（Multi-armed Bandit Problem）——入手，深入探讨强化学习中最核心的矛盾之一：探索与利用（Exploration vs. Exploitation）。多臂老虎机问题去除了状态转移的复杂性，只保留了一步决策的结构，使得我们可以集中研究"如何在不确定性中做出最优决策"这一根本问题。
本章的核心学习目标包括：
- 理解多臂老虎机问题的数学形式化：$k$ 个动作，每个动作对应一个未知的奖励分布，目标是最大化累积奖励
- 掌握 $\epsilon$-greedy 策略的原理和局限性：最简单的探索方法，但在理论上不是最优的
- 理解乐观初始化的作用：通过设置较高的初始估值来鼓励探索
- 掌握 UCB（Upper Confidence Bound）方法：基于不确定性驱动的探索策略，具有理论保证
- 理解梯度赌博机算法：直接学习动作概率的策略梯度方法
- 了解多臂老虎机在实际场景中的应用：临床试验、在线广告、推荐系统等
1.2 为什么本章如此重要
多臂老虎机问题虽然简单，但它蕴含了强化学习的核心挑战。在完整的强化学习问题中，智能体需要处理状态转移、延迟奖励等复杂因素，但探索与利用的矛盾始终存在。理解多臂老虎机的解法，是理解更复杂强化学习算法的基础。
此外，多臂老虎机问题在工业界有广泛应用。在线广告系统需要在展示已知高转化率的广告（利用）和尝试新广告（探索）之间权衡；临床试验需要在已知有效药物（利用）和测试新药（探索）之间权衡；推荐系统需要在推荐热门内容（利用）和推荐新内容（探索）之间权衡。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
如果你有一台 10 臂老虎机，每个臂的奖励分布不同但未知，你会如何选择？
$\epsilon$-greedy 策略的探索效率如何？它有什么根本性的缺陷？
为什么 UCB 方法能在探索和利用之间取得更好的平衡？它的理论保证是什么？
乐观初始化为什么能促进探索？它与 UCB 有什么异同？
梯度方法直接学习动作概率，与基于价值估计的方法有什么本质区别？
在什么场景下应该选择哪种探索策略？
二、核心概念详解
2.1 问题形式化
多臂老虎机问题定义如下：有 $k$ 个动作（臂），每个动作 $a$ 对应一个未知的奖励分布 $\mathcal{N}(\mu_a, \sigma^2)$。在每一步 $t$，智能体选择一个动作 $A_t$，获得奖励 $R_t \sim \mathcal{N}(\mu_{A_t}, \sigma^2)$。目标是最大化 $T$ 步的累积奖励：
$$\max \mathbb{E}\left[\sum_{t=1}^{T} R_t\right]$$
定义动作价值 $q_(a) = \mathbb{E}[R_t | A_t = a]$，最优动作是 $q_(a)$ 最大的动作。由于 $q_*(a)$ 未知，智能体需要通过采样来估计。
import numpy as np
class KArmedBandit:
def __init__(self, k=10, mean=0, std=1):
self.k = k
self.true_values = np.random.normal(mean, std, k)
self.best_action = np.argmax(self.true_values)
def pull(self, action):
return np.random.normal(self.true_values[action], 1)
def get_info(self):
return {
'true_values': self.true_values,
'best_action': self.best_action,
'best_value': self.true_values[self.best_action]
}
bandit = KArmedBandit(k=10)
info = bandit.get_info()
print(f"Best action: {info['best_action']}")
print(f"Best value: {info['best_value']:.3f}")
print(f"All values: {np.round(info['true_values'], 3)}")2.2 动作价值的估计
最直接的方法是维护每个动作的估计价值 $Q_t(a)$，使用增量更新公式：
$$Q_{t+1}(a) = Q_t(a) + \frac{1}{N_t(a)}(R_t - Q_t(a))$$
其中 $N_t(a)$ 是动作 $a$ 被选择的次数。这是样本均值的增量形式，当所有动作的奖励方差相同时，它是 $q_*(a)$ 的无偏估计。
class SampleAverageAgent:
def __init__(self, k=10, initial_Q=0):
self.k = k
self.Q = np.full(k, initial_Q, dtype=float)
self.N = np.zeros(k, dtype=int)
self.total_steps = 0
def select_action(self):
return np.argmax(self.Q)
def update(self, action, reward):
self.N[action] += 1
self.Q[action] += (reward - self.Q[action]) / self.N[action]
self.total_steps += 1
def evaluate_agent(agent, bandit, n_steps=1000):
rewards = []
optimal_actions = []
for _ in range(n_steps):
action = agent.select_action()
reward = bandit.pull(action)
agent.update(action, reward)
rewards.append(reward)
optimal_actions.append(
int(action == bandit.best_action)
)
return rewards, optimal_actions2.3 $\epsilon$-greedy 策略
最简单的探索策略是 $\epsilon$-greedy：以 $1-\epsilon$ 的概率选择当前估计价值最高的动作（利用），以 $\epsilon$ 的概率随机选择一个动作（探索）。
class EpsilonGreedyAgent:
def __init__(self, k=10, epsilon=0.1, initial_Q=0):
self.k = k
self.epsilon = epsilon
self.Q = np.full(k, initial_Q, dtype=float)
self.N = np.zeros(k, dtype=int)
def select_action(self):
if np.random.random() < self.epsilon:
return np.random.randint(self.k)
return np.argmax(self.Q)
def update(self, action, reward):
self.N[action] += 1
self.Q[action] += (reward - self.Q[action]) / self.N[action]$\epsilon$-greedy 的局限性：
盲目探索：随机探索时，可能选择价值远低于最优的动作，浪费大量资源
无法区分不确定性：对所有未充分探索的动作一视同仁，不考虑哪些动作更值得探索
渐近性能：即使所有动作的价值都已精确估计，仍以 $\epsilon$ 的概率选择次优动作
2.4 乐观初始化
通过设置较高的初始价值估计 $Q_1(a) = +5$（远高于真实值），可以自然地鼓励探索。初始阶段，所有动作的估计值都会下降，智能体会不断尝试不同的动作以找到真正的高价值动作。
class OptimisticInitialValuesAgent:
def __init__(self, k=10, initial_Q=5, alpha=0.1):
self.k = k
self.Q = np.full(k, initial_Q, dtype=float)
self.N = np.zeros(k, dtype=int)
self.alpha = alpha
def select_action(self):
return np.argmax(self.Q)
def update(self, action, reward):
self.N[action] += 1
self.Q[action] += self.alpha * (reward - self.Q[action])乐观初始化的优点是不需要额外的探索参数（如 $\epsilon$），探索行为自然地从乐观的初始值中涌现。但它也有局限：对于非平稳问题（奖励分布随时间变化），固定的步长 $\alpha$ 可能导致估计偏差。
2.5 UCB（Upper Confidence Bound）
UCB 方法基于一个优雅的直觉：在选择动作时，不仅考虑估计价值，还考虑估计的不确定性。不确定性越大的动作越值得探索。
$$A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]$$
其中 $c > 0$ 控制探索程度。第二项是不确定性度量：动作 $a$ 被选择次数越少、总步数越多，不确定性越大。
import math
class UCBAgent:
def __init__(self, k=10, c=2.0):
self.k = k
self.c = c
self.Q = np.zeros(k, dtype=float)
self.N = np.zeros(k, dtype=int)
self.t = 0
def select_action(self):
self.t += 1
for a in range(self.k):
if self.N[a] == 0:
return a
ucb_values = self.Q + self.c * np.sqrt(
math.log(self.t) / self.N
)
return np.argmax(ucb_values)
def update(self, action, reward):
self.N[action] += 1
self.Q[action] += (reward - self.Q[action]) / self.N[action]UCB 的理论保证： regret 上界为 $O(\sqrt{kT \ln T})$，这在理论上接近最优。但 UCB 在实际中也有局限：
难以处理高维状态空间：UCB 假设每个动作独立，不适用于有状态转移的完整 RL 问题
对非平稳问题效果不佳：$\ln t$ 项随时间单调增长，不适合奖励分布变化的场景
参数 $c$ 的选择：理论上 $c$ 有最优值，但实际中需要调参
2.6 梯度赌博机算法
与基于价值估计的方法不同，梯度方法直接学习动作的概率分布 $\pi_t(a)$。使用策略梯度的思想，根据奖励调整动作概率：
$$\pi_{t+1}(a) = \pi_t(a) \exp(\alpha \hat{A}_t \cdot \mathbf{1}_{A_t = a})$$
其中 $\hat{A}_t = R_t - \bar{R}_t$ 是基线化的奖励（减去平均奖励作为基线可以减少方差）。
class GradientBanditAgent:
def __init__(self, k=10, alpha=0.1, use_baseline=True):
self.k = k
self.alpha = alpha
self.use_baseline = use_baseline
self.H = np.zeros(k, dtype=float)
self.pi = np.ones(k, dtype=float) / k
self.avg_reward = 0
self.t = 0
def select_action(self):
return np.random.choice(self.k, p=self.pi)
def update(self, action, reward):
self.t += 1
self.avg_reward += (reward - self.avg_reward) / self.t
baseline = self.avg_reward if self.use_baseline else 0
advantage = reward - baseline
for a in range(self.k):
indicator = 1.0 if a == action else 0.0
self.H[a] += self.alpha * advantage * (indicator - self.pi[a])
exp_H = np.exp(self.H - np.max(self.H))
self.pi = exp_H / exp_H.sum()梯度方法的独特优势在于它直接优化目标函数（期望奖励），不需要维护价值估计。但它也有缺点：收敛速度可能较慢，且对步长参数敏感。
2.7 探索方法的比较
def run_comparison(k=10, n_steps=1000, n_runs=2000):
agents_config = [
('epsilon-greedy (0.01)', lambda: EpsilonGreedyAgent(k, 0.01)),
('epsilon-greedy (0.1)', lambda: EpsilonGreedyAgent(k, 0.1)),
('optimistic init', lambda: OptimisticInitialValuesAgent(k, 5, 0.1)),
('UCB (c=2)', lambda: UCBAgent(k, 2)),
('gradient bandit', lambda: GradientBanditAgent(k, 0.1)),
]
results = {}
for name, agent_factory in agents_config:
avg_rewards = np.zeros(n_steps)
pct_optimal = np.zeros(n_steps)
for _ in range(n_runs):
bandit = KArmedBandit(k)
agent = agent_factory()
for step in range(n_steps):
action = agent.select_action()
reward = bandit.pull(action)
agent.update(action, reward)
avg_rewards[step] += reward
pct_optimal[step] += int(
action == bandit.best_action
)
avg_rewards /= n_runs
pct_optimal /= n_runs
results[name] = {
'rewards': avg_rewards,
'optimal_pct': pct_optimal
}
return results
print("Running bandit comparison...")
results = run_comparison(n_steps=500, n_runs=500)
for name, data in results.items():
print(f"{name}: avg reward = {data['rewards'][-1]:.3f}, "
f"optimal = {data['optimal_pct'][-1]*100:.1f}%")三、实战案例
3.1 案例一：在线广告点击率优化
在线广告场景中，平台需要决定向用户展示哪个广告。每个广告的点击率（CTR）未知但相对稳定，这是一个典型的多臂老虎机问题。
class OnlineAdBandit:
def __init__(self, n_ads=5):
self.n_ads = n_ads
self.true_ctr = np.random.uniform(0.01, 0.1, n_ads)
def show_ad(self, ad_id):
clicked = np.random.random() < self.true_ctr[ad_id]
return 1.0 if clicked else 0.0
def simulate_ad_selection(n_ads=5, n_impressions=10000):
bandit = OnlineAdBandit(n_ads)
epsilon_agent = EpsilonGreedyAgent(n_ads, epsilon=0.1)
ucb_agent = UCBAgent(n_ads, c=1.0)
agents = {'epsilon-greedy': epsilon_agent, 'UCB': ucb_agent}
results = {name: {'revenue': 0, 'optimal': 0} for name in agents}
best_ad = np.argmax(bandit.true_ctr)
for step in range(n_impressions):
for name, agent in agents.items():
action = agent.select_action()
reward = bandit.show_ad(action)
agent.update(action, reward)
results[name]['revenue'] += reward
if action == best_ad:
results[name]['optimal'] += 1
print(f"True CTRs: {np.round(bandit.true_ctr, 4)}")
print(f"Best ad: {best_ad} (CTR={bandit.true_ctr[best_ad]:.4f})")
for name, data in results.items():
avg_rev = data['revenue'] / n_impressions
opt_pct = data['optimal'] / n_impressions * 100
print(f"{name}: avg revenue={avg_rev:.4f}, "
f"optimal selection={opt_pct:.1f}%")
simulate_ad_selection()3.2 案例二：临床试验中的自适应分配
在临床试验中，需要在已知有效药物（利用）和测试新药（探索）之间权衡。$\epsilon$-greedy 和 UCB 可以用于自适应地分配患者到不同治疗方案。
class ClinicalTrialBandit:
def __init__(self, n_treatments=4):
self.n_treatments = n_treatments
self.true_efficacy = np.random.uniform(0.3, 0.8, n_treatments)
def treat(self, treatment_id):
success = np.random.random() < self.true_efficacy[treatment_id]
return 1.0 if success else 0.0
def simulate_clinical_trial(n_treatments=4, n_patients=500):
bandit = ClinicalTrialBandit(n_treatments)
ucb_agent = UCBAgent(n_treatments, c=1.5)
treatment_counts = np.zeros(n_treatments, dtype=int)
total_success = 0
for patient in range(n_patients):
action = ucb_agent.select_action()
reward = bandit.treat(action)
ucb_agent.update(action, reward)
treatment_counts[action] += 1
total_success += reward
print(f"True efficacies: {np.round(bandit.true_efficacy, 3)}")
print(f"Patient assignments: {treatment_counts}")
print(f"Overall success rate: {total_success/n_patients:.3f}")
print(f"Best treatment received: "
f"{treatment_counts[np.argmax(bandit.true_efficacy)]}/{n_patients} "
f"({treatment_counts[np.argmax(bandit.true_efficacy)]/n_patients*100:.1f}%)")
simulate_clinical_trial()3.3 案例三：非平稳老虎机问题
在实际场景中，奖励分布可能随时间变化（非平稳问题）。此时，样本平均法会逐渐失去适应性，需要使用指数加权平均。
class NonStationaryBandit:
def __init__(self, k=10, drift=0.01):
self.k = k
self.drift = drift
self.true_values = np.zeros(k)
def pull(self, action):
self.true_values += np.random.normal(0, self.drift, self.k)
return np.random.normal(self.true_values[action], 1)
class ExponentialWeightAgent:
def __init__(self, k=10, alpha=0.1, epsilon=0.1):
self.k = k
self.alpha = alpha
self.epsilon = epsilon
self.Q = np.zeros(k)
def select_action(self):
if np.random.random() < self.epsilon:
return np.random.randint(self.k)
return np.argmax(self.Q)
def update(self, action, reward):
self.Q[action] += self.alpha * (reward - self.Q[action])
def test_nonstationary(alpha=0.1, epsilon=0.1, n_steps=10000):
bandit = NonStationaryBandit(k=10, drift=0.01)
agent = ExponentialWeightAgent(k=10, alpha=alpha, epsilon=epsilon)
rewards = []
for _ in range(n_steps):
action = agent.select_action()
reward = bandit.pull(action)
agent.update(action, reward)
rewards.append(reward)
avg_reward = np.mean(rewards[-1000:])
print(f"Non-stationary test: last 1000 avg reward = {avg_reward:.3f}")
test_nonstationary()四、本章小结
第2章通过多臂老虎机问题深入研究了探索与利用的困境，核心要点如下：
问题本质：多臂老虎机是最简化的强化学习问题，只有单步决策，核心挑战是在不确定性中选择最优动作。
$\epsilon$-greedy：最简单的探索方法，但存在盲目探索的缺陷。适用于简单场景或作为基线方法。
乐观初始化：通过设置较高的初始估值来自然鼓励探索，无需额外的探索参数。适用于稳态问题。
UCB 方法：基于不确定性驱动的探索，具有理论最优的 regret 上界。是当前最常用的探索策略之一。
梯度方法：直接学习动作概率分布，不需要价值估计。与策略梯度方法有深刻的联系。
非平稳问题：当奖励分布随时间变化时，需要使用指数加权平均等自适应方法。
这些探索策略的思想贯穿整个强化学习领域。在后续章节中，我们将看到 UCB 的思想如何被推广到有状态转移的 MDP 问题中，策略梯度的思想如何发展为完整的策略优化方法。
五、思考与练习
思考题
如果你有 100 个臂的老虎机，UCB 方法的计算复杂度是多少？如何优化？
在非平稳环境中，UCB 方法为什么不如 $\epsilon$-greedy + 指数加权平均？如何改进 UCB 以适应非平稳环境？
梯度赌博机算法中的基线（baseline）起什么作用？如果不使用基线会发生什么？
考虑一个推荐系统场景：用户的兴趣可能随时间变化，同时新用户和老用户的探索需求不同。如何设计一个适合这个场景的探索策略？
证明：对于 $k$ 臂老虎机，$\epsilon$-greedy 方法的渐近 regret 为 $\Theta(\epsilon \cdot \Delta \cdot T)$，其中 $\Delta$ 是最优动作与次优动作的价值差。
编程练习
实现 Thompson Sampling：Thompson Sampling 是另一种经典的探索策略。对每个动作维护奖励分布的后验，每次从后验中采样并选择最优。与 UCB 对比性能。
参数敏感性分析：对 $\epsilon$-greedy、UCB、梯度方法分别进行参数搜索，找出每种方法在不同问题设置下的最优参数。
设计一个非平稳老虎机：让每个臂的真实价值按照随机游走变化，测试不同方法（样本平均 vs 指数加权）的适应性。