論文の概要: On Instability of Minimax Optimal Optimism-Based Bandit Algorithms

• arxiv url: http://arxiv.org/abs/2511.18750v1
• Date: Mon, 24 Nov 2025 04:23:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:25.016185
• Title: On Instability of Minimax Optimal Optimism-Based Bandit Algorithms
• Title（参考訳）: 最適最適化に基づく帯域幅アルゴリズムのミニマックス不安定性について
• Authors: Samya Praharaj, Koulik Khamaru,
• Abstract要約: マルチアーム・バンディット(MAB)アルゴリズムは適応的で非i.d.な性質のため困難である。 楽観主義原理に基づく広帯域アルゴリズムの安定性特性を解析する。 MOSS, Anytime-MOSS, Vanilla-MOSS, ADA-UCB, OC-UCB, KL-MOSS, KL-UCB-SWITCH, Anytime KL-UCB-SWITCH などのミニマックス最適UPB型アルゴリズムが不安定であることを示す。
• 参考スコア（独自算出の注目度）: 2.5782420501870296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Statistical inference from data generated by multi-armed bandit (MAB) algorithms is challenging due to their adaptive, non-i.i.d. nature. A classical manifestation is that sample averages of arm rewards under bandit sampling may fail to satisfy a central limit theorem. Lai and Wei's stability condition provides a sufficient, and essentially necessary criterion, for asymptotic normality in bandit problems. While the celebrated Upper Confidence Bound (UCB) algorithm satisfies this stability condition, it is not minimax optimal, raising the question of whether minimax optimality and statistical stability can be achieved simultaneously. In this paper, we analyze the stability properties of a broad class of bandit algorithms that are based on the optimism principle. We establish general structural conditions under which such algorithms violate the Lai-Wei stability criterion. As a consequence, we show that widely used minimax-optimal UCB-style algorithms, including MOSS, Anytime-MOSS, Vanilla-MOSS, ADA-UCB, OC-UCB, KL-MOSS, KL-UCB++, KL-UCB-SWITCH, and Anytime KL-UCB-SWITCH, are unstable. We further complement our theoretical results with numerical simulations demonstrating that, in all these cases, the sample means fail to exhibit asymptotic normality. Overall, our findings suggest a fundamental tension between stability and minimax optimal regret, raising the question of whether it is possible to design bandit algorithms that achieve both. Understanding whether such simultaneously stable and minimax optimal strategies exist remains an important open direction.
• Abstract（参考訳）: マルチアーム・バンディット(MAB)アルゴリズムによって生成されたデータからの統計的推測は、適応的で非i.d.な性質のため困難である。 古典的な表現は、バンドイットサンプリングの下での腕の報酬のサンプル平均は中心極限定理を満たさないかもしれないということである。 Lai と Wei の安定性条件は、バンドイト問題における漸近正規性に対する十分かつ本質的に必要な基準を提供する。 有望なアッパー信頼境界(UCB)アルゴリズムはこの安定性条件を満たすが、極小最適ではないため、極小最適性と統計的安定性を同時に達成できるかどうかという疑問が提起される。 本稿では,楽観主義原理に基づく広帯域アルゴリズムの安定性特性を解析する。 このようなアルゴリズムがレイ・ヴァイ安定基準に反する一般的な構造条件を確立する。 その結果、MOSS、Anytime-MOSS、Vanilla-MOSS、ADA-UCB、OC-UCB、KL-MOSS、KL-UCB++、KL-UCB-SWITCH、Anytime KL-UCB-SWITCHなどのミニマックス最適化UPBスタイルのアルゴリズムが不安定であることが判明した。 さらに、これらの場合、サンプルは漸近正規性を示すことができないことを示す数値シミュレーションで理論結果を補完する。 全体としては,安定性と最小限の後悔の間に根本的な緊張関係があることが示唆され,両者を両立させる帯域幅アルゴリズムを設計できるかどうかという疑問が提起された。 そのような安定かつ極小戦略が同時に存在するかどうかを理解することは、依然として重要な開方向である。

関連論文リスト

• EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
  The fixed-confidence best arm identification problem in the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion。
  論文  参考訳（メタデータ） (2025-10-06T11:49:56Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling [24.487235945761913]
  本研究では, 1-パラメータ指数分布系に属する報酬分布を持つ帯域幅$K$の帯域幅の問題について検討する。 本稿では,Asymptotic Optimality, Minimax Optimality with a $sqrtln (K)$ factor, Sub-UCB, and variance-adaptive worst-case regret boundなど,複数の最適条件を同時に達成できるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-20T09:12:16Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• UCB algorithms for multi-armed bandits: Precise regret and adaptive inference [6.349503549199403]
  upper Confidence Bound (UCB) アルゴリズムは、$K$武器の盗聴問題に対して広く使われているシーケンシャルアルゴリズムのクラスである。 Lai-Robbins の後悔公式が真であることと、その部分最適性ギャップが$sigmasqrtKlog T/T$を超える場合に限ることを示す。 また、その最大後悔は対数係数によって最小後悔から逸脱し、従ってその厳密な最小最適性を負に設定することを示した。
  論文  参考訳（メタデータ） (2024-12-09T01:14:02Z)
• Unified theory of upper confidence bound policies for bandit problems targeting total reward, maximal reward, and more [0.8287206589886879]
  上位信頼境界(UCB)ポリシは、古典的全逆バンディット問題に対する順序最適解として認識される。 以上の結果から,UCB政策は全回帰問題と最大帯域幅問題の両方において順序最適性を実現する。 改善の可能性が最も高い腕を引くことを目的としたPIUCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T03:39:33Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  本稿では,最小化問題と最小化問題の両方に対して,MC-SGMの包括的一般化解析を行う。 我々はスムーズかつ非スムーズなケースに対して最適な過剰人口リスク境界を確立する。 コンベックス・コンケーブ問題に対する最初期のほぼ最適な収束率を期待と高い確率で開発する。
  論文  参考訳（メタデータ） (2022-09-16T15:42:51Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。 提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。 我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
  論文  参考訳（メタデータ） (2020-11-05T08:04:34Z)

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

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