論文の概要: UCB algorithms for multi-armed bandits: Precise regret and adaptive inference

• arxiv url: http://arxiv.org/abs/2412.06126v1
• Date: Mon, 09 Dec 2024 01:14:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-10 14:56:09.293676
• Title: UCB algorithms for multi-armed bandits: Precise regret and adaptive inference
• Title（参考訳）: マルチアームバンディットのためのUPBアルゴリズム:精密な後悔と適応推論
• Authors: Qiyang Han, Koulik Khamaru, Cun-Hui Zhang,
• Abstract要約: upper Confidence Bound (UCB) アルゴリズムは、$K$武器の盗聴問題に対して広く使われているシーケンシャルアルゴリズムのクラスである。 Lai-Robbins の後悔公式が真であることと、その部分最適性ギャップが$sigmasqrtKlog T/T$を超える場合に限ることを示す。 また、その最大後悔は対数係数によって最小後悔から逸脱し、従ってその厳密な最小最適性を負に設定することを示した。
• 参考スコア（独自算出の注目度）: 6.349503549199403
• License:
• Abstract: Upper Confidence Bound (UCB) algorithms are a widely-used class of sequential algorithms for the $K$-armed bandit problem. Despite extensive research over the past decades aimed at understanding their asymptotic and (near) minimax optimality properties, a precise understanding of their regret behavior remains elusive. This gap has not only hindered the evaluation of their actual algorithmic efficiency, but also limited further developments in statistical inference in sequential data collection. This paper bridges these two fundamental aspects--precise regret analysis and adaptive statistical inference--through a deterministic characterization of the number of arm pulls for an UCB index algorithm [Lai87, Agr95, ACBF02]. Our resulting precise regret formula not only accurately captures the actual behavior of the UCB algorithm for finite time horizons and individual problem instances, but also provides significant new insights into the regimes in which the existing theory remains informative. In particular, we show that the classical Lai-Robbins regret formula is exact if and only if the sub-optimality gaps exceed the order $\sigma\sqrt{K\log T/T}$. We also show that its maximal regret deviates from the minimax regret by a logarithmic factor, and therefore settling its strict minimax optimality in the negative. The deterministic characterization of the number of arm pulls for the UCB algorithm also has major implications in adaptive statistical inference. Building on the seminal work of [Lai82], we show that the UCB algorithm satisfies certain stability properties that lead to quantitative central limit theorems in two settings including the empirical means of unknown rewards in the bandit setting. These results have an important practical implication: conventional confidence sets designed for i.i.d. data remain valid even when data are collected sequentially.
• Abstract（参考訳）: upper Confidence Bound (UCB) アルゴリズムは、$K$武器の盗聴問題に対して広く使われているシーケンシャルアルゴリズムのクラスである。 過去数十年にわたる広範な研究は、その漸近的で(ほぼ)最小限の最適性の性質を理解することを目的としていたが、彼らの後悔行動の正確な理解はいまだに解明されていない。 このギャップは実際のアルゴリズム効率の評価を妨げるだけでなく、逐次データ収集における統計的推測のさらなる発展を妨げている。 本稿では,UCBインデックスアルゴリズムのアームプル数を決定論的に評価することにより,これら2つの基本的側面を補足する:高精度な後悔解析と適応的統計的推測- [Lai87, Agr95, ACBF02]。 得られた正確な後悔公式は, 有限時間地平線と個別問題事例に対する UCB アルゴリズムの実際の挙動を正確に把握するだけでなく, 既存の理論が有意義なままである状況に対して, 新たな洞察を与える。 特に、古典的なレイ・ロビンの後悔公式が真であることと、その部分最適性ギャップが位数$\sigma\sqrt{K\log T/T}$を超える場合に限ることを示す。 また、その最大後悔は対数係数によって最小後悔から逸脱し、従ってその厳密な最小最適性を負に設定することを示した。 UCBアルゴリズムのアームプル数の決定論的特徴は、適応的な統計的推論に大きな影響を及ぼす。 UCBアルゴリズムは, [Lai82] のセミナルな研究に基づいて, バンドイット設定における未知の報酬の実証的手段を含む2つの条件において, 定量的中心極限定理を導出する安定性特性を満たすことを示す。 これらの結果は重要な実用的意味を持つ: 従来の信頼セットは、データが逐次収集された場合でも、i.d.データ用に設計された信頼セットが有効である。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
  分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。 提案アルゴリズムの有効性と有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-04T16:49:29Z)
• Exact Asymptotics for Linear Quadratic Adaptive Control [6.287145010885044]
  最も単純な非帯域強化学習問題である線形二次制御(LQAC)について検討する。 ステップワイズ更新LQACアルゴリズムの残差,推定誤差,予測誤差の式を導出する。 安定系と不安定系のシミュレーションにおいて、我々の理論はアルゴリズムの有限サンプル挙動を著しくよく記述している。
  論文  参考訳（メタデータ） (2020-11-02T22:43:30Z)
• Bandit algorithms: Letting go of logarithmic regret for statistical robustness [0.0]
  我々は,多武器の盗賊設定における後悔について研究し,アルゴリズムによる後悔と統計的堅牢性の間に基本的なトレードオフを確立する。 対数的後悔を伴う帯域学習アルゴリズムは常に矛盾しており、一貫した学習アルゴリズムは常に超対数的後悔に苦しむことを示す。
  論文  参考訳（メタデータ） (2020-06-22T07:18:47Z)
• Interpretable Random Forests via Rule Extraction [0.0]
  本稿では,ルールの短時間かつ単純なリストの形式を取り入れた,安定なルール学習アルゴリズムであるSIRUSを紹介する。 当社のR/C++ソフトウェア実装サイラスは、CRANから入手可能です。
  論文  参考訳（メタデータ） (2020-04-29T08:13:35Z)
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits [3.8073142980733]
  実装が簡単かつ容易なアルゴリズムを提案する。 FP-UCBアルゴリズムは対数的後悔を実現する。 また、FP-UCBアルゴリズムの性能を広範囲な数値シミュレーションにより検証する。
  論文  参考訳（メタデータ） (2020-03-03T04:37:07Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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