引言
在多臂老虎机（Multi-Armed Bandit）问题中，玩家面临多个拉杆（手臂），每个手臂有不同的中奖概率，但事先未知。玩家的目标是在有限次数内最大化累计奖励。这一问题与钓鱼场景高度契合：不同的钓点如同不同的手臂，鱼群密度未知，钓手需要决定在每个钓点停留多久才能最大化渔获。
汤普森采样（Thompson Sampling）是一种基于贝叶斯思想的经典算法，通过维护每个手臂奖励概率的后验分布，并根据采样结果进行决策，在探索与利用之间取得良好平衡。本文将用Java实现钓鱼场景下的多臂老虎机问题，并详细讲解汤普森采样算法的核心原理。
问题建模
钓鱼场景抽象
假设有N个钓点，每个钓点的上鱼概率 $\theta_i$ 服从Beta先验分布 $\text{Beta}(1, 1)$（即均匀分布）。每次在钓点i垂钓，结果服从伯努利分布：钓到鱼（奖励1）的概率为 $\theta_i$，未钓到（奖励0）的概率为 $1 – \theta_i$。
Beta分布更新
Beta分布是伯努利分布的共轭先验。若先验为 $\text{Beta}(\alpha, \beta)$，观察到a次成功和b次失败后，后验更新为：
$$\text{Beta}(\alpha + a, \beta + b)$$
汤普森采样每次从各钓点后验分布中随机采样一个值，选择采样值最大的钓点进行垂钓。
Java实现
核心类设计
import java.util.*;
/**
* 钓点模型，维护Beta分布参数
*/
class FishingSpot {
private final String name;
private double alpha; // 成功次数 + 1
private double beta; // 失败次数 + 1
private int totalTrials;
private int totalSuccesses;
public FishingSpot(String name) {
this.name = name;
// Beta(1,1) 均匀先验
this.alpha = 1.0;
this.beta = 1.0;
this.totalTrials = 0;
this.totalSuccesses = 0;
}
/**
* 从Beta分布中采样（使用Gamma分布生成）
* Beta(a,b) = Gamma(a,1) / (Gamma(a,1) + Gamma(b,1))
*/
public double sample(Random random) {
double x = sampleGamma(random, alpha, 1.0);
double y = sampleGamma(random, beta, 1.0);
return x / (x + y);
}
/**
* Gamma分布采样（Marsaglia-Tsang方法）
*/
private double sampleGamma(Random random, double shape, double scale) {
if (shape < 1.0) {
// 使用形状小于1的变换
double u = random.nextDouble();
return sampleGamma(random, shape + 1.0, scale) * Math.pow(u, 1.0 / shape);
}
double d = shape - 1.0 / 3.0;
double c = 1.0 / Math.sqrt(9.0 * d);
while (true) {
double x = random.nextGaussian();
double v = 1.0 + c * x;
if (v <= 0.0) continue;
v = v * v * v;
double u = random.nextDouble();
if (u < 1.0 - 0.0331 * x * x * x * x) {
return d * v * scale;
}
if (Math.log(u) < 0.5 * x * x + d * (1.0 - v + Math.log(v))) {
return d * v * scale;
}
}
}
/**
* 更新后验分布
* @param success 是否钓到鱼
*/
public void update(boolean success) {
totalTrials++;
if (success) {
alpha++;
totalSuccesses++;
} else {
beta++;
}
}
public String getName() { return name; }
public double getAlpha() { return alpha; }
public double getBeta() { return beta; }
public int getTotalTrials() { return totalTrials; }
public int getTotalSuccesses() { return totalSuccesses; }
/**
* 获取当前估计的钓到鱼概率（后验均值）
*/
public double getEstimatedProbability() {
return alpha / (alpha + beta);
}
@Override
public String toString() {
return String.format("%s: Beta(%.1f, %.1f), 估计概率=%.3f, 试验=%d, 成功=%d",
name, alpha, beta, getEstimatedProbability(), totalTrials, totalSuccesses);
}
}
/**
* 汤普森采样钓鱼策略
*/
class ThompsonSamplingFishing {
private final List<FishingSpot> spots;
private final Random random;
public ThompsonSamplingFishing(List<FishingSpot> spots) {
this.spots = spots;
this.random = new Random(42); // 固定种子便于复现
}
/**
* 选择下一个钓点：从每个钓点的后验分布采样，选择最大值
*/
public FishingSpot selectSpot() {
FishingSpot bestSpot = null;
double bestSample = -1.0;
for (FishingSpot spot : spots) {
double sample = spot.sample(random);
if (sample > bestSample) {
bestSample = sample;
bestSpot = spot;
}
}
return bestSpot;
}
/**
* 执行一轮垂钓
* @param spot 选中的钓点
* @param trueProbability 该钓点的真实上鱼概率
* @return 是否钓到鱼
*/
public boolean fish(FishingSpot spot, double trueProbability) {
boolean success = random.nextDouble() < trueProbability;
spot.update(success);
return success;
}
/**
* 运行完整模拟
* @param trueProbabilities 各钓点的真实概率
* @param totalRounds 总垂钓轮数
*/
public void runSimulation(double[] trueProbabilities, int totalRounds) {
System.out.println("=== 汤普森采样钓鱼模拟 ===");
System.out.println("钓点真实概率: " + Arrays.toString(trueProbabilities));
System.out.println();
int totalReward = 0;
int[] spotTrials = new int[spots.size()];
int[] spotRewards = new int[spots.size()];
for (int round = 1; round <= totalRounds; round++) {
FishingSpot spot = selectSpot();
int spotIndex = spots.indexOf(spot);
boolean success = fish(spot, trueProbabilities[spotIndex]);
spotTrials[spotIndex]++;
if (success) {
spotRewards[spotIndex]++;
totalReward++;
}
// 每100轮输出一次状态
if (round % 100 == 0) {
System.out.printf("第 %d 轮，累计渔获: %d%n", round, totalReward);
}
}
System.out.println("\n=== 最终结果 ===");
for (int i = 0; i < spots.size(); i++) {
System.out.printf("%s: 试验 %d 次, 成功 %d 次, 实际成功率 %.3f%n",
spots.get(i).getName(), spotTrials[i], spotRewards[i],
spotTrials[i] > 0 ? (double) spotRewards[i] / spotTrials[i] : 0);
}
System.out.printf("总渔获: %d / %d (理论最优: %.1f)%n",
totalReward, totalRounds,
totalRounds * Arrays.stream(trueProbabilities).max().orElse(0));
// 计算遗憾（Regret）
double optimalReward = totalRounds * Arrays.stream(trueProbabilities).max().orElse(0);
System.out.printf("累计遗憾: %.1f%n", optimalReward - totalReward);
}
}
/**
* 对比算法：epsilon-贪心策略
*/
class EpsilonGreedyFishing {
private final List<FishingSpot> spots;
private final double epsilon;
private final Random random;
public EpsilonGreedyFishing(List<FishingSpot> spots, double epsilon) {
this.spots = spots;
this.epsilon = epsilon;
this.random = new Random(42);
}
public FishingSpot selectSpot() {
if (random.nextDouble() < epsilon) {
// 探索：随机选择
return spots.get(random.nextInt(spots.size()));
} else {
// 利用：选择当前估计概率最高的
FishingSpot best = spots.get(0);
double bestProb = best.getEstimatedProbability();
for (int i = 1; i < spots.size(); i++) {
double p = spots.get(i).getEstimatedProbability();
if (p > bestProb) {
bestProb = p;
best = spots.get(i);
}
}
return best;
}
}
public boolean fish(FishingSpot spot, double trueProbability) {
boolean success = random.nextDouble() < trueProbability;
spot.update(success);
return success;
}
}
/**
* 主程序入口
*/
public class FishingBanditDemo {
public static void main(String[] args) {
// 创建5个钓点，真实上鱼概率不同
List<FishingSpot> spots = Arrays.asList(
new FishingSpot("A-浅水湾"),
new FishingSpot("B-深水潭"),
new FishingSpot("C-芦苇荡"),
new FishingSpot("D-石桥下"),
new FishingSpot("E-回水湾")
);
// 各钓点的真实上鱼概率
double[] trueProbabilities = {0.15, 0.35, 0.25, 0.10, 0.40};
// 汤普森采样
ThompsonSamplingFishing ts = new ThompsonSamplingFishing(spots);
ts.runSimulation(trueProbabilities, 2000);
System.out.println("\n=== 各钓点后验分布 ===");
for (FishingSpot spot : spots) {
System.out.println(spot);
}
}
}
算法分析
时间复杂度
每轮决策需要为K个钓点各进行一次Beta分布采样。Gamma采样是O(1)的，因此每轮时间复杂度为 O(K)，其中K为钓点数量。
空间复杂度
每个钓点维护两个双精度浮点数（α和β），总空间复杂度为 O(K)。
遗憾界
汤普森采样的累计遗憾（Cumulative Regret）在伯努利奖励下满足：
$$R_T = O\left(\sum_{i \neq i^*} \frac{\ln T}{\Delta_i}\right)$$
其中 $i^$ 是最优钓点，$\Delta_i = \theta_{i^} – \theta_i$ 为次优臂的差距。这一界在常数因子意义下是最优的。
扩展思考
- 非平稳环境：若鱼群密度随时间变化，可引入指数衰减因子，使近期观测权重更高。
- 上下文信息：结合天气、水温等上下文变量，可使用上下文老虎机（Contextual Bandit）或LinUCB算法。
- 并发垂钓：多钓手场景可扩展为分布式老虎机问题，需考虑通信成本与协调策略。
总结
汤普森采样通过贝叶斯后验分布自然地平衡了探索与利用，在钓鱼这一经典场景中展现出优雅的决策能力。相比epsilon-贪心等频率学派方法，汤普森采样具有更好的理论保证和实际表现，是处理不确定性决策问题的有力工具。
