論文の概要: Bandit Allocational Instability

• arxiv url: http://arxiv.org/abs/2602.07472v1
• Date: Sat, 07 Feb 2026 10:09:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.640124
• Title: Bandit Allocational Instability
• Title（参考訳）: Bandit Allocational Instaability
• Authors: Yilun Chen, Jiaqi Lu,
• Abstract要約: マルチアームバンディット(MAB)アルゴリズムは、競合するアーム間でプルを割り当てる。 これは、学習の強化されたプラットフォーム操作や帯域後統計的推測のような近代的な応用において特に有害である。 我々は、アームのプル数において最大(オーバーアーム)標準偏差であるアロケーション可変性と呼ばれるMABアルゴリズムの新たな性能指標を提案する。
• 参考スコア（独自算出の注目度）: 11.667122717858172
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When multi-armed bandit (MAB) algorithms allocate pulls among competing arms, the resulting allocation can exhibit huge variation. This is particularly harmful in modern applications such as learning-enhanced platform operations and post-bandit statistical inference. Thus motivated, we introduce a new performance metric of MAB algorithms termed allocation variability, which is the largest (over arms) standard deviation of an arm's number of pulls. We establish a fundamental trade-off between allocation variability and regret, the canonical performance metric of reward maximization. In particular, for any algorithm, the worst-case regret $R_T$ and worst-case allocation variability $S_T$ must satisfy $R_T \cdot S_T=Ω(T^{\frac{3}{2}})$ as $T\rightarrow\infty$, as long as $R_T=o(T)$. This indicates that any minimax regret-optimal algorithm must incur worst-case allocation variability $Θ(T)$, the largest possible scale; while any algorithm with sublinear worst-case regret must necessarily incur ${S}_T= ω(\sqrt{T})$. We further show that this lower bound is essentially tight, and that any point on the Pareto frontier $R_T \cdot S_T=\tildeΘ(T^{3/2})$ can be achieved by a simple tunable algorithm UCB-f, a generalization of the classic UCB1. Finally, we discuss implications for platform operations and for statistical inference, when bandit algorithms are used. As a byproduct of our result, we resolve an open question of Praharaj and Khamaru (2025).
• Abstract（参考訳）: マルチアーム・バンディット(MAB)アルゴリズムが競合するアーム間でプルを割り当てる場合、結果として得られるアロケーションは大きなばらつきを示す。 これは、学習の強化されたプラットフォーム操作や帯域後統計的推測のような近代的な応用において特に有害である。 そこで本研究では,腕のプル数の標準偏差として最大(オーバーアーム)であるアロケーション可変性と呼ばれるMABアルゴリズムの新たな性能指標を提案する。 我々は、アロケーションの変動性と後悔の基本的なトレードオフ、すなわち報酬の最大化の標準的なパフォーマンス指標を確立する。 特に、どんなアルゴリズムでも、最悪の場合、$R_T$と$S_T$は$R_T \cdot S_T=Ω(T^{\frac{3}{2}})$を$T\rightarrow\infty$とし、$R_T=o(T)$で満たさなければならない。 このことは、任意のミニマックスの後悔-最適アルゴリズムは、最も大きな可能なスケールである最低ケースの割り当て変数を$(T)$でなければならないことを示し、一方、最小ケースの後悔を持つアルゴリズムは、必ずしも${S}_T= ω(\sqrt{T})$でなければならない。 さらに、この下界は本質的に厳密であり、古典的 UCB1 の一般化である単純なチューナブルアルゴリズム UCB-f によってパレートフロンティア $R_T \cdot S_T=\tilde (T^{3/2})$ 上の任意の点が達成可能であることを示す。 最後に,バンディットアルゴリズムを用いた場合のプラットフォーム操作や統計的推論への影響について考察する。 結果の副産物として、プラハラジとハマル(2025年)の公然と疑問を解く。

関連論文リスト

• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。