論文の概要: Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem

• arxiv url: http://arxiv.org/abs/2512.18409v1
• Date: Sat, 20 Dec 2025 16:11:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-23 18:54:32.322659
• Title: Why Most Optimism Bandit Algorithms Have the Same Regret Analysis: A Simple Unifying Theorem
• Title（参考訳）: 楽観主義のバンディットアルゴリズムがなぜ同じレギュレット分析をするのか:単純な統一理論
• Authors: Vikram Krishnamurthy,
• Abstract要約: UCB, UCB-V, linear UCB, and finite-arm GP-UCBなどの楽観主義に基づく帯域幅アルゴリズムは、表面的な違いにもかかわらず本質的に同じ構造であることを示す証明を用いて対数的後悔を実現する。 本報告はこれらの分析の背景にある最小の成分を分離する: 推定器上の1つの高確率濃度条件の後、半径崩壊と楽観主義による偏差を記述した2つの短い決定論的補題から対数的後悔が続く。 この枠組みはこれらの古典的アルゴリズムの統一的で最小に近い証明をもたらし、多くの現代のバンディット変種に自然に拡張する。
• 参考スコア（独自算出の注目度）: 15.493230983626281
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several optimism-based stochastic bandit algorithms -- including UCB, UCB-V, linear UCB, and finite-arm GP-UCB -- achieve logarithmic regret using proofs that, despite superficial differences, follow essentially the same structure. This note isolates the minimal ingredients behind these analyses: a single high-probability concentration condition on the estimators, after which logarithmic regret follows from two short deterministic lemmas describing radius collapse and optimism-forced deviations. The framework yields unified, near-minimal proofs for these classical algorithms and extends naturally to many contemporary bandit variants.
• Abstract（参考訳）: UCB, UCB-V, linear UCB, and finite-arm GP-UCBなど、楽観主義に基づく確率的帯域幅アルゴリズムは、表面的な違いにもかかわらず、本質的に同じ構造に従うという証明を用いて対数的後悔を実現する。 本報告はこれらの分析の背景にある最小の成分を分離する: 推定器上の1つの高確率濃度条件の後、半径崩壊と楽観主義による偏差を記述した2つの短い決定論的補題から対数的後悔が続く。 この枠組みはこれらの古典的アルゴリズムの統一的で最小に近い証明をもたらし、多くの現代のバンディット変種に自然に拡張する。

関連論文リスト

• Q-Learning with Fine-Grained Gap-Dependent Regret [13.370933509246568]
  既存のモデルフリーアルゴリズムは、最小限の最悪の後悔を実現するが、そのギャップ依存境界はいまだに粗いままであり、最適以下のギャップの構造を完全に捉えることができない。 UCBベースと非UCBベースの両方のアルゴリズムに対して、きめ細かいギャップ依存的後悔境界を確立する。
  論文  参考訳（メタデータ） (2025-10-08T05:02:16Z)
• 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)
• 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)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Non-Asymptotic Analysis of a UCB-based Top Two Algorithm [4.18804572788063]
  バンディット識別のためのトップ2サンプリングルールは、2つの候補アームの中から次のアームを選択する方法である。 提案するUCBベースのトップ2は,非漸近的保証と競合経験性能を同時に享受する。
  論文  参考訳（メタデータ） (2022-10-11T13:21:59Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms [8.099977107670918]
  アッパー信頼境界 (UCB) は楽観的なMABアルゴリズムである。 本稿では,UCBのアームサンプリング動作に関する新しい知見を提供する。 また、UPBの下でのMAB問題のプロセスレベルの特徴付けも提供する。
  論文  参考訳（メタデータ） (2021-06-03T20:52:26Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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