arXiv:2604.20024cs.LG2026-04

提出可复现的上置信界算法,显著降低随机多臂赌博机的可复现代价。

Replicable Bandits with UCB based Exploration

  • 基于乐观探索设计可复现的批量UCB算法,避免传统淘汰法缺陷。
  • 线性老虎机下首次实现ρ依赖最优的后悔上界,提升幅度达O(d/ρ)。
  • 适用于需要结果可复现的强化学习、推荐系统等实际场景。

研究基于上置信界(UCB)探索的随机多臂老虎机(MAB)与线性老虎机中的可复现算法。一个算法若在共享内部随机性但独立奖励实现下以至少1−ρ的概率产生相同动作序列,则称其为ρ-可复现。先前方法依赖淘汰机制,在无限动作的线性老虎机中需离散化,导致维度d和ρ的依赖关系次优。本文提出两种乐观替代方案:针对随机多臂老虎机,提出RepUCB,一种可复现的批处理UCB算法,其后悔界为O((K² log²T)/ρ² ∑_{a:Δ_a>0} (Δ_a + log(KT log T)/Δ_a));针对随机线性老虎机,首先引入RepRidge,一种满足置信保证和ρ-可复现性的可复现岭回归估计器,随后基于此构建RepLinUCB,其后悔界为~O((d + d³/ρ)√T),相比前人最优结果提升O(d/ρ)因子,首次实现大臂数下对ρ的最优依赖。最后将框架扩展至广义线性老虎机,提出RepGLM与RepGLMUCB。

原文摘要 · Abstract (English)

We study replicable algorithms for stochastic multi-armed bandits (MAB) and linear bandits with UCB (Upper Confidence Bound) based exploration. A bandit algorithm is $ρ$-replicable if two executions using shared internal randomness but independent reward realizations produce the same action sequence with probability at least $1-ρ$. Prior approaches to this problem are elimination-based and, in linear bandits with infinitely many actions, rely on discretization, leading to suboptimal dependence on the dimension $d$ and $ρ$. We develop optimistic alternatives for both settings. For stochastic multi-armed bandits, we propose RepUCB, a replicable batched UCB algorithm and show that it attains a regret $O\!\left(\frac{K^2\log^2 T}{ρ^2}\sum_{a:Δ_a>0}\left(Δ_a+\frac{\log(KT\log T)}{Δ_a}\right)\right)$. For stochastic linear bandits, we first introduce RepRidge, a replicable ridge regression estimator that satisfies both a confidence guarantee and a $ρ$-replicability guarantee. Beyond its role in our bandit algorithm, this may also be of independent interest in other statistical estimation settings. We then use RepRidge to design RepLinUCB, a replicable optimistic algorithm for stochastic linear bandits, and show that its regret is bounded by $\widetilde{O}\!\big(\big(d+\frac{d^3}ρ\big)\sqrt{T}\big)$. This improves the best prior regret guarantee by a factor of $O(d/ρ)$, showing that our optimistic algorithm can substantially reduce the price of replicability. This is the first linear-bandit algorithm with an optimal dependence on $ρ$ for large number of arms. Finally, we extend our framework to stochastic generalized linear bandits by developing RepGLM, a replicable penalized GLM estimator, and RepGLMUCB, a replicable optimistic algorithm for this setting.

多臂老虎机可复现性上置信界线性模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。