1. 多臂老虎机问题概述
多臂老虎机问题是强化学习中最经典的探索-利用困境(exploration-exploitation dilemma)的数学模型。想象你走进一个赌场，面前有K台老虎机（在学术文献中通常称为"臂"），每台老虎机的奖励概率分布不同但未知。你的目标是通过有限的尝试次数，最大化累计奖励。
这个问题看似简单，却蕴含着强化学习的核心思想：如何在获取信息（探索）和利用已知信息（利用）之间找到最佳平衡。太注重探索会导致频繁尝试低回报选项，太注重利用则可能错过未发现的更优选择。
2. ε-贪婪算法及其改进
2.1 基础ε-贪婪算法回顾
在基础ε-贪婪算法中，我们以ε的概率随机选择一个臂（探索），以1-ε的概率选择当前估计奖励最高的臂（利用）。这种策略简单直接，但存在明显缺陷：无论进行了多少次尝试，探索概率ε始终保持不变。
python复制class EpsilonGreedy(Solver):
def __init__(self, bandit, epsilon=0.01):
super(EpsilonGreedy, self).__init__(bandit)
self.epsilon = epsilon
def run_one_step(self):
if np.random.random() < self.epsilon: # 探索
k = np.random.randint(0, self.bandit.K)
else: # 利用
k = np.argmax(self.estimates)
r = self.bandit.step(k)
self.estimates[k] += 1./(self.counts[k]+1)*(r-self.estimates[k])
return k
2.2 ε衰减贪婪算法实现
ε衰减贪婪算法是对基础版本的重要改进，它让探索概率ε随着尝试次数增加而逐渐降低。这种调整基于一个直观认知：随着我们对各臂奖励估计越来越准确，探索的必要性应该相应减少。
python复制class DecayingEpsilonGreedy(Solver):
def __init__(self, bandit, init_prob=1.0):
super(DecayingEpsilonGreedy, self).__init__(bandit)
self.estimates = np.array([init_prob] * self.bandit.K)
self.total_count = 0 # 总尝试次数计数器
def run_one_step(self):
self.total_count += 1
if np.random.random() < 1 / self.total_count: # ε=1/t
k = np.random.randint(0, self.bandit.K) # 探索
else:
k = np.argmax(self.estimates) # 利用
r = self.bandit.step(k)
self.estimates[k] += 1./(self.counts[k]+1)*(r-self.estimates[k])
return k
2.2.1 算法特点分析
- 动态调整的探索率：ε从初始的1（100%探索）逐渐降低，最终趋近于0
- 理论保证：当ε=1/t时，算法满足次线性遗憾增长（regret grows sublinearly）
- 实践表现：在静态环境中表现优异，但在非静态（奖励分布会变化）环境中可能表现不佳
实际应用提示：在真实场景中，可以尝试ε=min(1,c/t)的形式，其中c是可调参数，控制初始探索强度。
2.3 性能对比实验
为了直观比较两种策略，我们进行5000次拉杆实验：
python复制# 初始化10臂老虎机
bandit = Bandit(10)
# 创建两种策略
greedy = EpsilonGreedy(bandit, epsilon=0.01)
decaying = DecayingEpsilonGreedy(bandit)
# 运行实验
greedy.run(5000)
decaying.run(5000)
# 绘制结果
plot_results([greedy, decaying], ["ε-Greedy(ε=0.01)", "Decaying ε-Greedy"])
实验结果分析：
- 初期（前100次尝试）：ε衰减策略探索更积极，懊悔增长较快
- 中期（100-1000次）：ε衰减策略开始显现优势
- 后期（1000次后）：ε衰减策略懊悔几乎不再增长，而固定ε策略仍保持线性增长趋势
3. 上置信界(UCB)算法
3.1 算法原理
UCB算法采用完全不同的思路，它不依赖随机探索，而是为每个臂计算一个上置信界(Upper Confidence Bound)，然后选择UCB值最大的臂。UCB值的计算公式：
UCB = 当前平均奖励 + c × √(lnN/n)
其中：
- N是总尝试次数
- n是该臂被尝试次数
- c是探索系数（通常设为1）
python复制class UCB(Solver):
def __init__(self, bandit, coef=1.0, init_prob=1.0):
super(UCB, self).__init__(bandit)
self.total_count = 0
self.coef = coef # 探索系数
self.estimates = np.array([init_prob] * self.bandit.K)
def run_one_step(self):
self.total_count += 1
# 计算UCB值
ucb = self.estimates + self.coef * np.sqrt(
np.log(self.total_count) / (2 * (self.counts + 1)))
k = np.argmax(ucb) # 选择UCB最大的臂
r = self.bandit.step(k)
self.estimates[k] += 1./(self.counts[k]+1)*(r-self.estimates[k])
return k
3.2 UCB算法优势
- 确定性选择：不依赖随机数，每次选择都有明确依据
- 智能探索：自动平衡探索和利用，对尝试次数少的臂给予更多机会
- 理论保证：在有限时间内达到对数级遗憾增长
3.3 参数选择建议
-
探索系数c：控制探索强度
- c越大，算法越倾向于探索
- 理论最优值为√2，实践中常用1
- 在非静态环境中可能需要更大值
-
初始估计值init_prob：
- 乐观初始值（如1.0）有助于早期探索
- 在已知先验信息时可设为更合理值
4. 汤普森采样算法
4.1 贝叶斯思想的应用
汤普森采样采用贝叶斯方法，为每个臂的奖励概率维护一个概率分布（通常使用Beta分布）。每次选择时，先从这些分布中采样得到各臂的奖励概率估计，然后选择采样值最大的臂。
python复制class ThompsonSampling(Solver):
def __init__(self, bandit):
super(ThompsonSampling, self).__init__(bandit)
self._a = np.ones(self.bandit.K) # 成功次数+1
self._b = np.ones(self.bandit.K) # 失败次数+1
def run_one_step(self):
# 从Beta分布采样
samples = np.random.beta(self._a, self._b)
k = np.argmax(samples) # 选择采样值最大的臂
r = self.bandit.step(k)
# 更新分布参数
self._a[k] += r
self._b[k] += (1 - r)
return k
4.2 算法特点
- 自然平衡探索利用：尝试次数少的臂方差大，偶尔会被采样到高值
- 适应性强：特别适合非静态环境和上下文老虎机
- 计算效率高：相比UCB需要更少的计算资源
4.3 实际应用技巧
-
先验知识利用：
- 如果有领域知识，可以设置非均匀先验（而非α=β=1）
- 例如，已知某臂大概率表现好，可设α=5,β=1
-
非静态环境适应：
- 可以引入遗忘因子，逐渐减小旧数据的影响
- 例如：self._a = 0.9*self._a + r
5. 算法比较与选择指南
5.1 性能对比
| 算法 | 探索方式 | 理论遗憾界 | 计算复杂度 | 适用场景 |
|---|---|---|---|---|
| ε-贪婪 | 随机探索 | O(logT) | 低 | 简单环境，快速实现 |
| ε衰减 | 动态随机探索 | O(logT) | 低 | 静态环境 |
| UCB | 确定性选择 | O(√T) | 中 | 需要理论保证的场景 |
| 汤普森采样 | 概率采样 | O(logT) | 低 | 非静态环境，贝叶斯模型 |
5.2 选择建议
- 简单快速实现：ε-贪婪或ε衰减
- 理论保证重要：UCB算法
- 非静态环境：汤普森采样
- 上下文信息可用：通常结合汤普森采样
5.3 实际应用注意事项
-
参数调优：
- ε-贪婪的ε值
- UCB的探索系数c
- 汤普森采样的先验分布
-
非静态环境检测：
- 监控各臂表现变化
- 考虑滑动窗口或衰减因子
-
计算资源考虑：
- UCB需要计算平方根和对数
- 汤普森采样需要随机数生成
6. 进阶话题与扩展
6.1 非静态环境处理
在实际应用中，老虎机的奖励分布可能随时间变化。常用应对方法：
- 滑动窗口：只考虑最近N次尝试的结果
- 衰减因子：给旧数据赋予较小权重
- 变化检测：监控奖励变化，检测到变化时重置学习
6.2 上下文老虎机
当选择可以基于额外信息（上下文）时，问题扩展为上下文老虎机。常用解决方案：
- LinUCB：线性模型+UCB
- 神经汤普森采样：用神经网络近似奖励分布
6.3 分布式老虎机
在多智能体系统中，需要考虑：
- 信息共享机制
- 通信成本与探索效率的平衡
- 对抗性环境下的安全探索
在实际项目中，我通常会先实现一个简单的ε-贪婪或汤普森采样作为基线，然后根据具体需求逐步升级到更复杂的算法。记住，没有放之四海而皆准的最佳算法，关键是根据问题特性和约束条件做出合适选择。