对抗性组合多臂老虎机Adversarial Combinatorial Bandits是强化学习里一个挺有意思的领域它处理的是那种“环境可能故意跟你作对”的决策问题。标题里这个“Adversarial $m$-Set Bandits”就是其中一类你可以把它想象成你面前有N台老虎机但每次你只能同时拉动其中m台一个组合而且每台机器的回报不是随机的而是由一个“对手”在背后根据你的历史选择来恶意设定的。你的目标是在这种最坏的情况下找到一个策略让长期的总损失尽可能接近理论上最优策略的损失也就是实现“接近最优”的后悔值上界。这篇文章要聊的就是一个针对这类问题的高效且接近最优的算法。如果你在做在线广告投放选择一组广告展示、网络路由选择一组路径或者资源分配并且需要考虑最坏情况下的性能保障那这个主题就值得一看。它的核心价值在于在对抗性环境下它能在计算效率和理论性能保证之间取得一个很好的平衡——算法跑得快同时后悔值增长得慢。很多人一看到“对抗性”、“组合优化”就觉得头大算法肯定复杂得没法用。其实不然这篇文章要拆解的这个算法思路其核心是清晰且可实现的。我会带你从问题定义开始一步步理解为什么常规方法不行这个算法是怎么绕开复杂度的墙的以及你如果想自己实现或者验证该从哪里入手关键参数怎么调结果怎么才算跑对了。1. 先搞清楚“对抗性m-Set老虎机”到底在解决什么问题在开始看算法之前我们必须把问题场景框死否则后面所有的讨论都会飘在空中。这不是一个纯理论的游戏它有很直观的现实对应物。1.1 场景还原当你的对手会学习并针对你想象你是一个网站运营者每天有N个广告位对应N台“老虎机”但一屏只能展示m个广告每次拉动m台机器。每次用户访问你选一组m个广告展示出去。如果环境是“随机的”Stochastic Bandits那么每个广告被点击的概率是固定的只是你不知道而已你可以通过试探来学习这个概率。但在“对抗性”Adversarial设定下规则变了。存在一个虚拟的“对手”它会在每一轮开始前观察你过去所有选择了哪些广告组合然后为每一个广告位注意是每一个分配一个损失比如0表示用户点击了1表示没点击。这个损失是专门为了让你这轮选任何组合都难受而设定的。你的目标不是击败这个对手因为它全知全能且恶意而是在它的恶意干扰下让你的长期累计损失不要比那个“每次都选理论上当期最优组合”的上帝策略差太多。这个“差多少”就是后悔值Regret。我们设计算法就是为了让这个后悔值随着游戏轮数T的增长增长速度尽可能慢比如是 $O(\sqrt{T})$ 而不是 $O(T)$。1.2 为什么这个问题难组合爆炸与计算效率难点立刻出现了组合空间巨大从N个里面选m个组合数是指数级的$C_N^m$。你不可能为每一个可能的组合都维护一个独立的概率分布或权重那内存和计算都受不了。对抗性环境你不能用那些依赖“平稳性假设”的算法比如UCB因为对手的损失分配可以任意变化甚至针对你的策略。所以一个“高效且接近最优”的算法必须同时做到两件事理论保证在最坏对抗情况下后悔值上界要接近已知的理论下限比如 $\tilde{O}(\sqrt{mT \log N})$ 这个量级。计算高效每次做决策从指数级组合中选一个的时间复杂度要低最好是多项式级别比如 $O(N)$ 或 $O(N \log N)$而不是 $O(C_N^m)$。很多早期算法只能满足其一要么理论最优但算不动要么算得快但理论保证弱。我们今天要讨论的这类算法目标就是鱼与熊掌兼得。2. 算法核心思想如何绕过组合爆炸直接处理所有组合行不通所以必须找“捷径”。目前主流的高效对抗性组合老虎机算法如COMBAND、FTRL with John‘s exploration等其核心思想可以概括为以下几步这也是理解本文“Efficient Near-Optimal Algorithm”的关键2.1 从组合空间降维到基元空间算法并不直接在 $m$-Set 组合的维度上操作。相反它维护一个在N个基元即单个臂/广告位上的概率分布。记作一个向量 $p \in \mathbb{R}^N$$p_i$ 表示在某种采样规则下第 $i$ 个基元被“考虑”的概率。每次决策时算法不是直接选一个组合而是根据这个概率分布 $p$通过一种特定的随机采样规则生成一个大小为 $m$ 的组合 $S$。最经典的采样规则就是独立的伯努利采样对每个基元 $i$以概率 $\tilde{p}_i$$p_i$ 的一个调整版本独立地决定是否将其放入集合 $S$。这样$S$ 的期望大小就是 $\sum \tilde{p}_i$我们可以通过调整 $\tilde{p}$ 使其期望等于 $m$。为什么这样做是高效的因为我们需要存储和更新的对象是长度为 $N$ 的向量 $p$而不是大小为 $C_N^m$ 的组合权重表。空间复杂度从指数级降到了线性级 $O(N)$。2.2 处理反馈从组合损失到基元损失估计当你选择了组合 $S$ 并观察到组合中每个基元的损失 $l_i$对手设定的后你只能看到 $S$ 里成员的损失。为了更新概率分布 $p$你需要为每一个基元 $i$无论是否在 $S$ 中构造一个无偏的损失估计量$\hat{l}_i$。这是对抗性老虎机的标准技术称为重要性采样Importance Sampling [ \hat{l}_i \frac{l_i \cdot \mathbb{I}(i \in S)}{P(i \in S)} ] 其中 $P(i \in S)$ 是基元 $i$ 被选入组合 $S$ 的概率这个概率可以从采样规则和概率向量 $p$ 计算出来。关键点这个估计量 $\hat{l}_i$ 的期望值等于真实的损失 $l_i$且对于未观察到的基元$i \notin S$其估计值可能为0但期望是正确的。这就把组合部分观测的反馈转化成了全基元空间的无偏估计信号。2.3 更新策略在线学习算法的应用现在我们有了所有基元的无偏损失估计向量 $\hat{l}$。接下来就可以使用任何高效的在线凸优化Online Convex Optimization算法来更新概率分布 $p$。最常用的就是Follow-The-Regularized-Leader (FTRL)或Online Mirror Descent (OMD)。以 FTRL 为例在每一轮 $t$我们求解如下优化问题来更新 $p_{t1}$ [ p_{t1} \arg\min_{p \in \mathcal{P}} \left( \eta \sum_{s1}^{t} \hat{l}_s^\top p R(p) \right) ] 其中$\hat{l}_s$ 是历史上第 $s$ 轮的损失估计向量。$\eta 0$ 是学习率一个至关重要的超参数。$R(p)$ 是正则项如负熵正则化用于控制 $p$ 的探索程度使其不要过于集中在某几个基元上。$\mathcal{P}$ 是 $p$ 的可行域通常要求 $p$ 是一个概率单纯形上的点并且隐含了期望组合大小为 $m$ 的约束。这一步是计算效率的另一个关键对于负熵正则化这个优化问题有闭式解类似于指数权重更新更新 $p$ 的时间复杂度是 $O(N)$。2.4 整合起来算法的高层伪代码流程基于以上思想一个典型的算法框架如下初始化设置学习率 η 正则化参数初始化概率向量 p_1 (例如均匀分布)。 For 轮数 t 1 to T: 1. 根据当前概率向量 p_t通过特定的采样规则如调整后的独立伯努利采样生成一个大小为 m 的组合 S_t。 2. 将组合 S_t 作为行动提交并观察到组合内每个基元 i ∈ S_t 的损失 l_{t,i}。 3. 为所有基元 i 1,...,N 构造无偏损失估计量 如果 i ∈ S_t: \hat{l}_{t,i} l_{t,i} / P_t(i ∈ S_t) 如果 i ∉ S_t: \hat{l}_{t,i} 0 4. 使用在线学习算法如 FTRL和损失估计向量 \hat{l}_t 来更新概率向量 p_{t1} UpdateRule(p_t, \hat{l}_t, η) 5. t t 1这个框架就是许多“高效接近最优”算法的骨架。不同算法的创新点可能在于采样规则如何从 $p$ 精确地生成期望大小为 $m$ 的集合独立伯努利采样可能使集合大小波动有些算法会使用更复杂的依赖采样如“骰子”机制来保证大小严格为 $m$。正则化与可行域 $\mathcal{P}$ 的设计这直接影响探索效率和理论后悔界。学习率 $\eta$ 的调度通常是随时间衰减的如 $\eta_t \propto 1/\sqrt{t}$其具体形式影响后悔界的常数项。3. 实现与实测环境、步骤与关键参数理解了思想我们来看看如果要自己复现或验证这类算法需要准备什么步骤如何以及哪里最容易出错。3.1 实验环境与数据准备1. 编程环境语言Python 是最佳选择因为有丰富的科学计算库NumPy, SciPy。算法中涉及大量的向量和矩阵运算。核心库numpy用于数值计算scipy.optimize可能用于求解某些约束优化问题如果不用闭式解matplotlib用于绘制后悔值曲线。2. 问题实例生成模拟对手你不能等一个真实的恶意对手必须自己模拟。这是测试算法的关键。损失生成方式你需要一个函数在每一轮 $t$根据算法历史动作 $S_1, ..., S_{t-1}$生成本轮损失向量 $l_t \in [0,1]^N$。最简单的对抗性模式有oblivious adversary损失序列是预先确定的与你的选择无关。这是最简单的测试。adaptive adversary损失可以依赖于你过去的行动。一个经典的强对抗策略是让算法历史中选择频率高的基元在本轮产生高损失。这能有效测试算法的鲁棒性。基线策略为了计算后悔值你需要知道每一轮的“最优固定组合”。对于 oblivious adversary你可以通过枚举如果N不大或整数规划求解。对于 adaptive adversary最优固定组合的定义更复杂通常与“上帝视角”的基准比较。3. 超参数配置准备一个配置文件或字典来管理超参数这是调优的起点。config { N: 100, # 基元总数 m: 10, # 每轮选择的组合大小 T: 10000, # 总轮数 eta_schedule: 1/sqrt_t, # 学习率调度方式如 constant, 1/sqrt_t eta0: 0.1, # 初始学习率需要精细调节 regularizer: negative_entropy, # 正则化类型 sampling: independent_bernoulli, # 采样规则 seed: 42, # 随机种子保证结果可复现 }3.2 核心实现步骤拆解我们以实现一个基于独立伯努利采样和FTRL的版本为例。步骤1初始化概率向量pimport numpy as np N, m config[N], config[m] p np.ones(N) / N # 初始均匀分布 cumulative_loss_est np.zeros(N) # 用于FTRL累计估计损失步骤2采样函数实现这是第一个关键点。我们需要根据p生成一个期望大小为m的集合。简单独立采样可能导致集合大小不等于m。一个常用技巧是计算一个缩放因子c使得c * p的和等于m但每个分量不能超过1。def sample_set(p, m): 根据概率向量p采样一个期望大小为m的集合S。 使用独立的、调整后的伯努利采样。 # 计算缩放因子c使得 sum(min(c * p_i, 1)) m # 可以通过排序和线性搜索求解c这里简化使用二分查找 sorted_p np.sort(p) # ... 二分查找求解c的代码 ... c find_scaling_factor(sorted_p, m) adjusted_probs np.minimum(c * p, 1.0) # 独立伯努利采样 S np.where(np.random.rand(N) adjusted_probs)[0] # 注意S的大小可能在m附近波动严格等于m需要更复杂的采样器如“骰子”法 return S, adjusted_probs步骤3损失估计def estimate_losses(S, observed_losses, selection_probs): S: 本轮选择的集合包含基元索引 observed_losses: 字典或数组记录S中基元的真实损失 selection_probs: 每个基元被选中的概率 adjusted_probs[i] l_hat np.zeros(N) for i in S: l_hat[i] observed_losses[i] / selection_probs[i] # 不在S中的基元估计损失为0 return l_hat步骤4FTRL更新负熵正则化负熵正则化 $R(p) \sum_i p_i \log p_i$ 下的FTRL有漂亮的闭式解——指数权重更新。def ftrl_update(cumulative_loss_est, eta): 使用指数权重更新规则。 cumulative_loss_est: 累计估计损失向量 (sum of l_hat) eta: 当前学习率 # 计算指数权重 weights np.exp(-eta * cumulative_loss_est) # 归一化得到新的概率分布 p_new weights / np.sum(weights) return p_new步骤5主循环与后悔值计算regret 0 cumulative_loss_algorithm 0 # 假设我们有一个函数 best_fixed_combo_loss(t) 能返回第t轮最优固定组合的损失 best_fixed_cumulative_loss 0 for t in range(1, config[T]1): # 1. 采样 S_t, selection_probs sample_set(p, config[m]) # 2. 从“对手”获得损失调用模拟函数 loss_vector_t adversary.generate_loss(t, history) # history包含过去的S # 只取选中元素的损失 observed_losses {i: loss_vector_t[i] for i in S_t} loss_t sum(observed_losses.values()) cumulative_loss_algorithm loss_t # 3. 计算最优固定组合在本轮的损失并累计 loss_best_t best_fixed_combo_loss(t) best_fixed_cumulative_loss loss_best_t # 4. 计算即时后悔并累计 regret cumulative_loss_algorithm - best_fixed_cumulative_loss # 5. 估计损失 l_hat_t estimate_losses(S_t, observed_losses, selection_probs) # 6. 更新累计估计损失 cumulative_loss_est l_hat_t # 7. 更新学习率 (例如 eta eta0 / sqrt(t)) eta_t config[eta0] / np.sqrt(t) # 8. 更新概率分布 p ftrl_update(cumulative_loss_est, eta_t) # 9. 记录历史可选 history.append(S_t)3.3 关键参数调优与结果验证1. 学习率eta0这是最重要的超参数。它控制着算法探索与利用的权衡。理论值通常理论分析会给出一个形式如 $\eta \propto \sqrt{\frac{\log N}{m T}}$。你可以用这个作为起点。调优方法在固定的对抗性损失序列如一个随机生成的序列上运行不同eta0的算法绘制累计后悔值随时间变化的曲线。好的eta0应该使曲线最终后悔值较低。上升过程平滑没有剧烈震荡。在总轮数T内能收敛到一个稳定的斜率。过大/过小的表现eta0太大算法反应“过敏”权重更新剧烈概率分布p波动大可能导致后悔值曲线震荡剧烈长期性能不稳定。eta0太小算法学习太慢探索不足可能长时间陷在次优组合里后悔值线性增长的时间段很长。2. 采样规则的稳定性独立伯努利采样可能导致|S_t|不等于m。虽然期望是m但方差可能影响理论边界和实际性能。验证在调试时打印或记录每轮len(S_t)的值观察其分布。如果波动过大比如经常出现m-3或m3可能需要实现更精确的采样器。替代方案实现一个“条件泊松采样”或使用“骰子法Dice”采样器它们能保证每次恰好选择m个元素同时满足每个元素被选中的边际概率与adjusted_probs成比例。这会增加实现复杂度但更符合理论假设。3. 结果验证怎么知道你的实现是对的后悔值曲线这是黄金标准。在 oblivious adversary损失序列固定下你的算法累计后悔值曲线应该低于随机选择策略这是底线。呈现次线性增长即随着T增大曲线的斜率应该逐渐变平。如果是线性增长一条陡直的斜线说明算法没在学习。与理论缩放律吻合在双对数坐标图log-log plot上后悔值关于T的曲线斜率应接近 0.5对应 $O(\sqrt{T})$ 增长。你可以用np.polyfit(np.log(t_range), np.log(regret_history), 1)来拟合斜率。概率向量p的演化观察p是否逐渐将质量集中到损失较低的基元上。在简单的对抗模式下例如始终给某几个固定臂高损失p应该学会避开这些臂。与基线算法对比实现一个简单的算法作为基线例如Exp3算法虽然它是针对单个臂的但可以将其视为每个组合是一个“超级臂”的朴素版本计算昂贵但易于实现用于小规模验证。你的高效算法在后悔值上应该与Exp3的趋势一致但运行时间快几个数量级。4. 常见问题、排查与进阶思考即使理解了原理实现和调试过程中也一定会遇到问题。下面是一些典型的坑和排查思路。4.1 数值不稳定与下溢/上溢问题现象概率向量p出现NaN或inf或者权重计算时得到全0。根本原因指数权重更新weights np.exp(-eta * cumulative_loss_est)中指数部分可能非常大负的很大或正的很大导致下溢接近0或上溢无穷大。解决方案对数域计算这是标准做法。我们计算log_weights -eta * cumulative_loss_est然后减去最大值进行数值稳定化。def ftrl_update_stable(cumulative_loss_est, eta): log_weights -eta * cumulative_loss_est max_log np.max(log_weights) # 减去最大值防止指数爆炸 weights np.exp(log_weights - max_log) p_new weights / np.sum(weights) return p_new损失归一化确保输入的损失估计量l_hat不要过大。理论上对抗性损失在[0,1]区间但l_hat可能因为除以很小的selection_probs而变得很大。如果出现这种情况检查采样概率是否过低或者考虑对l_hat进行裁剪clipping。4.2 后悔值不收敛或线性增长问题现象运行很多轮后后悔值曲线仍然是一条斜率明显的直线。排查顺序检查损失估计的无偏性这是算法正确性的核心。写一个测试固定一个概率向量p和损失向量l重复采样很多次计算l_hat的平均值。这个平均值应该非常接近真实的l。如果偏差很大你的采样概率selection_probs计算有误。检查学习率eta0可能太大了。过大的学习率导致策略震荡无法收敛到好的分布。尝试将eta0减小一个数量级例如从0.1调到0.01再观察。检查对手是否太强你模拟的adaptive adversary可能过于强大以至于任何在线算法都无法获得次线性后悔。尝试先切换到简单的oblivious adversary如随机生成损失序列进行测试。如果在这种简单环境下后悔值都不收敛那肯定是算法实现问题。检查“最优固定组合”的计算后悔值是相对于最优固定组合的。如果你计算best_fixed_combo_loss有误例如在 adaptive 设定下用了错误的标准后悔值就会失真。对于 oblivious 对手确保你计算的确实是全局最优组合可以通过枚举验证。4.3 采样组合大小严重偏离 m问题现象len(S_t)经常远小于或远大于m。影响这违反了算法的核心假设期望大小为m可能导致损失估计方差增大性能下降。解决方案精确求解缩放因子c在sample_set函数中确保求解sum(min(c*p, 1)) m的算法是精确的。二分查找是一个可靠的方法。实现更严格的采样器如果调整概率后adjusted_probs中仍有大量接近0或1的值独立采样仍可能波动大。考虑实现一个Conditional Poisson Sampling或使用Sampling Without Replacement的库如numpy.random.choice带replaceFalse和p参数但这要求p本身的和为m且每个元素不大于1这又需要不同的概率转换方法。这是一个实现上的进阶挑战。4.4 扩展到更大规模与生产考量本文讨论的算法框架是高效的$O(N)$ 每轮但当N达到百万甚至千万级别时即使是 $O(N)$ 的更新也可能成为瓶颈。稀疏更新在l_hat中只有被选中的m个基元有非零值。因此更新cumulative_loss_est和计算新的p时可以只操作这m个元素及其相关部分。对于指数权重更新这需要一些技巧因为归一化涉及所有N个元素的和。一种方法是维护权重总和并增量更新。分布式/并行化采样和损失估计可以并行。FTRL更新中的指数运算和求和也可以并行化。学习率自动调整理论上的学习率调度依赖于总轮数T但在实际在线环境中T可能未知。可以采用自适应学习率方法如 AdaGrad 风格根据历史梯度损失估计的幅度来调整。与上下文信息结合这就是 Contextual Combinatorial Bandits。每个回合还会有一个特征向量上下文。算法需要将概率分布p与上下文关联起来通常通过一个线性模型或神经网络来参数化。这大大增加了复杂度但实用性更强。这个算法框架的价值在于它提供了一个坚实的地基。它证明了在对抗性组合选择这个难题上我们确实可以设计出既快又好的策略。当你真正动手实现它并看到那条代表后悔值的曲线从线性挣扎变为优雅的次线性增长时你就能切实感受到在线学习理论中这种简洁而强大设计的美感。对于工程落地我的建议是先用小规模N如20和简单对手验证所有环节的正确性特别是损失估计的无偏性和学习率的影响。确保这个核心引擎运转无误后再去挑战规模扩展和更复杂的采样规则。