UCB による探索を用いた可複製バンディット

arXiv:2604.20024v1 Announce Type: new Abstract: 私たちは、UCB（Upper Confidence Bound）に基づく探索を用いた確率多重アームバンディット（MAB）と線形バンディットのための可複製アルゴリズムを研究します。バンディットアルゴリズムが ρ 可複製であるとは、共有内部ランダム性と独立した報酬実現を持つ 2 つの実行が、少なくとも 1−ρ の確率で同じ行動系列を生み出すことを意味します。既存の研究は主に除外ベースの手法に基づいており、無限個のアクションを持つ線形バンディットの文脈では、分断化に依存しており、次元 d と ρ に対して不十分な依存関係を持っています。私たちが開発した楽観的代替案はこれら 2 つの設定のいずれにも対応します。確率多重アームバンディットに対して、私たちは RepUCB という可複製のバッチ UCB アルゴリズムを提案し、それが O(K^2 log^2 T / ρ^2 ∑(a:Δa>0) (Δa + (log(KT log T) / Δa))) のレグレットを達成することを示しました。確率線形バンディットに対して、私たちはまず、確実性保証と ρ 可複製性保証の両方を満たす RepRidge という可複製の Ridge リgression 推定者を導入しました。この推定器とその保証は、私たちのバンディットアルゴリズムの役割を超えて、他の統計推定設定においても独立した興味を喚起する可能性があります。その後、私たちは RepRidge を利用して、確率線形バンディットのための可複製楽観的アルゴリズム RepLinUCB を設計し、そのレグレットが O~((d + d^3/ρ)√T) によって束縛されることを示しました。これは、以前の最も良いレグレット保証を O(d/ρ) の因子で改善し、楽観的アルゴリズムが可複製性の価格を著しく減少させ得ることを示しています。

arXiv:2604.20024v1 Announce Type: new Abstract: We study replicable algorithms for stochastic multi-armed bandits (MAB) and linear bandits with UCB (Upper Confidence Bound) based exploration. A bandit algorithm is $\rho$-replicable if two executions using shared internal randomness but independent reward realizations, produce the same action sequence with probability at least $1-\rho$. Prior work is primarily elimination-based and, in linear bandits with infinitely many actions, relies on discretization, leading to suboptimal dependence on the dimension $d$ and $\rho$. 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}{\rho^2}\sum_{a:\Delta_a>0}\left(\Delta_a+\frac{\log(KT\log T)}{\Delta_a}\right)\right)$. For stochastic linear bandits, we first introduce RepRidge, a replicable ridge regression estimator that satisfies both a confidence guarantee and a $\rho$-replicability guarantee. Beyond its role in our bandit algorithm, this estimator and its guarantees 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}{\rho}\big)\sqrt{T}\big)$. This improves the best prior regret guarantee by a factor of $O(d/\rho)$, showing that our optimistic algorithm can substantially reduce the price of replicability.