打地鼠看似简单，一旦对手（地鼠出现的位置规律）是故意针对你的，问题就变了性质：你越打某个洞，地鼠越不来那个洞。这不是随机环境，而是对抗性环境（adversarial environment）。此时经典的 UCB、汤普森采样都会失效——它们假设奖励分布平稳；而 EXP3 算法专门为对抗性多臂老虎机设计，能在最坏情况下保证遗憾以 O(√(TK log K)) 增长。本文用 Java 实现一个 EXP3 驱动的打地鼠 AI。
一、为什么 UCB 会输给”会针对你”的地鼠
标准的随机多臂老虎机假设：每个摇臂的奖励服从固定分布。UCB 的策略是”乐观面对不确定性”——多试几次不确定的臂，就能估计出真实均值。
但打地鼠的现实是：玩家的行为会影响地鼠的分布。机器可以观察你的历史，然后专挑你不打的洞冒头。这时：
- 你越”专精”某个洞，该洞的出现概率越低；
- 你以为在利用已知优势，实际是在暴露策略；
- UCB 的”探索”在对抗性场景下会被对方当作空档利用。
对抗性模型的形式化：每轮 t = 1..T，环境（对手）在观察到你的历史后，选择每个臂的损失向量 ℓ_t ∈ [0,1]^K；然后你选择一个臂 i_t，承受损失 ℓ_t(i_t)。对手可以任意选择，包括针对你。
EXP3（Exponential-weight algorithm for Exploration and Exploitation）的核心思想：把每个臂的权重按指数更新，但更新时用重要性加权估计补偿”没有观测到的臂”。
二、EXP3 的三个关键步骤
2.1 概率分布：权重归一 + 显式探索
p_i = (1 - γ) * w_i / Σw + γ / K
(1-γ)部分是”利用”：按当前权重比例分配；γ/K部分是”探索”：每个臂至少被选中γ/K的概率。
γ 控制两者权衡，理论最优值 γ = min(1, sqrt(K log K / T))。注意是 γ/K 而不是给某个特定臂加量——均匀的保底探索是对抗场景下不被针对的关键。
2.2 损失估计：重要性加权
关键难点：你只观测到选中臂的损失，其他臂的损失未知。直接令未观测臂的估计损失为 0，会导致”没选过 = 显得很好”，从而过度利用。
EXP3 用无偏估计：
ℓ̂_i = ℓ_i / p_i 若 i = i_t（本轮被选中）
ℓ̂_i = 0 否则
期望上 E[ℓ̂_i] = ℓ_i（因为选中概率为 p_i）。代价是估计方差很大（1/p_i 可能很大），这需要 γ > 0 保证 p_i ≥ γ/K，从而给方差上界。
2.3 权重更新：指数衰减
w_i ← w_i * exp(-γ * ℓ̂_i / K)
乘以 -γ/K 是为了让学习率随 K 与 γ 调节。理论遗憾上界：
Regret(T) ≤ 2 * sqrt(T * K * log K)
这是 O(√T) 量级——与对手策略无关的最坏情况保证。
三、Java 实现
3.1 项目结构
whack-a-mole/
├── src/main/java/com/example/mole/
│ ├── Exp3Agent.java // EXP3 决策器
│ ├── MoleEnvironment.java // 对抗性地鼠模拟（含针对策略）
│ ├── AdversarialMole.java // 三种对手策略
│ └── Simulation.java // 主程序与遗憾统计
└── pom.xml
3.2 EXP3 核心类
package com.example.mole;
import java.util.*;
/**
* EXP3 对抗性多臂老虎机。
* 目标：在损失序列可能被对手针对的情况下，把累计遗憾控制在 O(sqrt(T*K*logK))。
*/
public class Exp3Agent {
private final int K; // 臂数量（打地鼠的洞位数）
private final double gamma; // 探索系数
private final double[] logW; // 用对数权重避免下溢：log w_i
private final Random rnd;
public Exp3Agent(int arms, double gamma, long seed) {
this.K = arms;
this.gamma = gamma;
this.logW = new double[arms]; // 初始 log(1) = 0
this.rnd = new Random(seed);
}
/** 根据理论最优公式自动设置 gamma */
public Exp3Agent(int arms, int horizon, long seed) {
this(arms, Math.min(1.0, Math.sqrt(arms * Math.log(arms) / horizon)), seed);
}
/** 计算当前的混合分布 p_i = (1-γ)*softmax(logW)_i + γ/K */
public double[] probabilities() {
double maxLog = Double.NEGATIVE_INFINITY;
for (double v : logW) if (v > maxLog) maxLog = v;
double sumExp = 0;
double[] soft = new double[K];
for (int i = 0; i < K; i++) {
soft[i] = Math.exp(logW[i] - maxLog); // 数值稳定
sumExp += soft[i];
}
double[] p = new double[K];
for (int i = 0; i < K; i++)
p[i] = (1.0 - gamma) * soft[i] / sumExp + gamma / K;
return p;
}
/** 按分布采样一个臂 */
public int sample() {
double[] p = probabilities();
double u = rnd.nextDouble();
double acc = 0;
for (int i = 0; i < K; i++) {
acc += p[i];
if (u < acc) return i;
}
return K - 1; // 数值误差兜底
}
/**
* 观测到损失后更新权重。
* @param arm 本轮选择的臂
* @param loss 观测到的损失，取值 [0,1]
*/
public void update(int arm, double loss) {
double[] p = probabilities(); // 注意：必须用"更新前"的概率
double pHat = Math.max(p[arm], 1e-12);
double estimatedLoss = loss / pHat; // 重要性加权的无偏估计
// 只更新被选中的臂：其余臂估计损失为 0，logW 不变
logW[arm] -= gamma * estimatedLoss / K;
// 数值保护：防止 logW 无限下溢
double floor = -50.0;
if (logW[arm] < floor) logW[arm] = floor;
}
public double getGamma() { return gamma; }
}
两个容易写错的地方：
update里必须用更新前的概率p。如果先更新权重再取概率，p_i会偏小，重要性加权系数错误，估计失去无偏性。- 用
logW而非w。exp(-γℓ̂/K)连乘 T 轮后，w会下溢到 0（double 最小约1e-308），而logW一直保持有限值。
3.3 三类对抗性地鼠
为了让实验结果有说服力，需要构造真正的对抗环境：
package com.example.mole;
import java.util.*;
/** 地鼠环境接口：给定历史，返回本轮各地洞的"损失"（1=有地鼠但没打中，0=没地鼠或打中） */
public interface MoleEnvironment {
double[] losses(int[] history, int round);
String name();
}
package com.example.mole;
import java.util.*;
public class AdversarialMole {
/** 策略一：均匀随机（基线，等价于随机老虎机） */
public static class Uniform implements MoleEnvironment {
private final int K;
private final Random rnd;
public Uniform(int k, long seed) { K = k; rnd = new Random(seed); }
public double[] losses(int[] history, int round) {
double[] l = new double[K];
int hit = rnd.nextInt(K);
Arrays.fill(l, 1.0);
l[hit] = 0.0; // 只有冒头的洞可以打中（损失 0）
return l;
}
public String name() { return "Uniform(随机)"; }
}
/** 策略二：反频率（专挑你最近最少打的洞冒头） */
public static class AntiFrequency implements MoleEnvironment {
private final int K;
private final int window;
public AntiFrequency(int k, int window) { K = k; this.window = window; }
public double[] losses(int[] history, int round) {
int[] freq = new int[K];
int from = Math.max(0, round - window);
for (int t = from; t < round; t++) freq[history[t]]++;
double[] l = new double[K];
// 出现频率越低，越容易被选中冒头（损失 0 的位置）
double[] score = new double[K];
double total = 0;
for (int i = 0; i < K; i++) { score[i] = 1.0 / (freq[i] + 1); total += score[i]; }
int best = 0; double bestS = -1;
for (int i = 0; i < K; i++) {
double s = score[i] / total;
if (s > bestS) { bestS = s; best = i; }
}
Arrays.fill(l, 1.0);
l[best] = 0.0;
return l;
}
public String name() { return "AntiFrequency(反频率)"; }
}
/** 策略三：最坏情况（永远挑损失最大的洞，即完全不给你打中的机会） */
public static class WorstCase implements MoleEnvironment {
private final int K;
private final Random rnd;
public WorstCase(int k, long seed) { K = k; rnd = new Random(seed); }
public double[] losses(int[] history, int round) {
double[] l = new double[K];
// 对手直接"报复"：你越常打的洞，损失越高（必定落空）
int[] freq = new int[K];
for (int t = 0; t < round; t++) freq[history[t]]++;
for (int i = 0; i < K; i++) l[i] = 1.0; // 全部为损失 1
int most = 0;
for (int i = 1; i < K; i++) if (freq[i] > freq[most]) most = i;
// 让最近的洞也可以被打中一点，避免完全不可学
if (rnd.nextDouble() < 0.25) l[rnd.nextInt(K)] = 0.0;
return l;
}
public String name() { return "WorstCase(最坏情况)"; }
}
}
四、遗憾（Regret）的度量与对照实验
遗憾定义为”你的累计损失”减去”事后最优固定臂的累计损失”：
R(T) = Σ_t ℓ_t(i_t) - min_i Σ_t ℓ_t(i)
理论保证：R(T) = O(√(TK log K))。要在实验中看到这个形状，需要把累计遗憾除以 √T，看它是否趋于常数。
package com.example.mole;
import java.util.*;
public class Simulation {
public static void main(String[] args) {
int K = 9; // 3×3 的洞位
int T = 20000;
long seed = 20261031L;
System.out.printf("%-28s %-14s %-14s %-10s%n",
"环境", "EXP3累计损失", "最优固定臂", "遗憾");
System.out.println("--------------------------------------------------------------");
runExperiment(new AdversarialMole.Uniform(K, seed), K, T, seed);
runExperiment(new AdversarialMole.AntiFrequency(K, 30), K, T, seed);
runExperiment(new AdversarialMole.WorstCase(K, seed), K, T, seed);
}
static void runExperiment(MoleEnvironment env, int K, int T, long seed) {
Exp3Agent agent = new Exp3Agent(K, T, seed);
int[] history = new int[T];
double[] lossesSeen = new double[K]; // 记录每轮各臂损失，用于算最优固定臂
double cumulativeLoss = 0;
// 先跑一遍收集全部损失序列（对抗环境依赖历史，需顺序推进）
for (int t = 0; t < T; t++) {
int arm = agent.sample();
history[t] = arm;
double[] l = env.losses(history, t);
for (int i = 0; i < K; i++) lossesSeen[i] += l[i] / T; // 平均值近似
cumulativeLoss += l[arm];
agent.update(arm, l[arm]);
}
// 事后最优固定臂：用平均损失最小者
double bestFixed = Double.MAX_VALUE;
for (int i = 0; i < K; i++) bestFixed = Math.min(bestFixed, lossesSeen[i]);
double regret = cumulativeLoss - bestFixed * T;
System.out.printf("%-28s %-14.1f %-14.1f %-10.1f%n",
env.name(), cumulativeLoss, bestFixed * T, regret);
System.out.printf(" 平均每轮遗憾 = %.4f, 遗憾/√T = %.3f%n",
regret / T, regret / Math.sqrt(T));
}
}
三行输出的对比会非常有信息量：
- Uniform 环境：EXP3 遗憾较小，因为环境确实近似随机，任何策略都不会太差；
- AntiFrequency 环境：随机策略会吃亏（专挑你不打的洞），EXP3 通过均匀保底探索仍然保持遗憾可控；
- WorstCase 环境：这里任何策略都会被针对，但 EXP3 的遗憾仍然是次线性的——这正是”最坏情况保证”的含义。
五、打地鼠的真实建模：把”洞”变成”时空臂”
上面的模型把 K 个洞当成 K 个固定臂。真实打地鼠里，地鼠是在时间和空间上同时出现的，因此更准确的建模是”时空臂”：
- 臂 =
(洞位, 时间窗口)； - 每轮只有一个或少数几个臂的损失为 0（地鼠出现的那一格与那个时间片）；
- 玩家的反应有延迟，超过窗口就落空。
这时可以直接把 EXP3 套上去，只需要把 K 换成 洞位数 × 时间片数。但 K 增大会让 γ 变小、学习变慢（γ ∝ √(log K / (T K))）。工程上的改进：
- 分层 EXP3：先选洞位（内层 EXP3），再选时间片（外层 EXP3），把
K的乘积变成和； - 上下文 EXP3：把”最近 N 轮的地鼠位置”作为上下文，为每个上下文维护一组权重（即 EXP3 的 contextual 变体）；
- 共享权重：空间上相邻的洞共享部分权重，利用地鼠出现的位置相关性。
/** 分层 EXP3：空间层 + 时间层，把臂数 O(K1*K2) 降为 O(K1+K2) */
public class HierarchicalExp3 {
private final Exp3Agent spatial; // 选洞位
private final Exp3Agent temporal; // 选时间片
private int lastPos, lastTime;
public HierarchicalExp3(int positions, int timeSlots, int horizon, long seed) {
spatial = new Exp3Agent(positions, horizon, seed);
temporal = new Exp3Agent(timeSlots, horizon, seed + 1);
}
/** 决策：先空间后时间（也可反过来，或按概率交替） */
public int[] decide() {
lastPos = spatial.sample();
lastTime = temporal.sample();
return new int[]{lastPos, lastTime};
}
/** 反馈：两层分别更新，各自只看自己的损失分量 */
public void update(double spatialLoss, double temporalLoss) {
spatial.update(lastPos, spatialLoss);
temporal.update(lastTime, temporalLoss);
}
}
分层带来的代价是”两层各自的损失”并不等于”联合损失”，因此遗憾界会乘以一个常数因子。但在臂数很大时，这种近似远比”直接堆乘积”更实用。
六、复杂度与数值稳定性
| 环节 | 复杂度 | 说明 |
|---|---|---|
probabilities |
O(K) |
每轮一次 softmax + 归一 |
sample |
O(K) |
线性扫描累积分布 |
update |
O(K) |
需重算概率，O(K) |
| 整体每轮 | O(K) |
K = 9 时几乎零开销 |
数值稳定性要点：
- softmax 前减去最大 logW：避免
exp上溢。 logW设下限（如-50）：防止长时间不选的臂权重塌陷到 0，失去探索可能。p_i设下限（如1e-12）：防止重要性加权系数1/p_i爆成Infinity。γ不能取 1：γ = 1时完全均匀随机，退化为无学习；γ → 0则方差爆炸。理论值γ = min(1, √(K log K / T))是渐进最优的折中。
七、和 UCB 的正面比较
写一个对照实验，用同一个对抗环境跑两种算法：
/** UCB1（假设平稳分布），用于展示其在对抗环境下的失效 */
public class Ucb1Agent {
private final int K;
private final int[] pulls;
private final double[] meanLoss;
private int round = 0;
public Ucb1Agent(int k) { K = k; pulls = new int[k]; meanLoss = new double[k]; }
public int sample() {
for (int i = 0; i < K; i++) if (pulls[i] == 0) return i; // 先各试一次
int best = 0;
double bestScore = -Double.MAX_VALUE;
for (int i = 0; i < K; i++) {
double score = meanLoss[i] - Math.sqrt(2 * Math.log(round) / pulls[i]);
if (score > bestScore) { bestScore = score; best = i; }
}
return best;
}
public void update(int arm, double loss) {
round++;
pulls[arm]++;
meanLoss[arm] += (loss - meanLoss[arm]) / pulls[arm];
}
}
在 AntiFrequency 环境下的典型结果：UCB1 会不断”锁定”某个刚被证明损失低的洞，对方立刻停止在那里冒头，导致 UCB1 反复落空；EXP3 因为始终保留 γ/K 的均匀探索，反而能持续命中。
这就是”对抗场景下，均匀保底探索比乐观估计更安全“的算法结论——它不依赖任何对手模型的假设。
