論文の概要: Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2610.39457v1
• Date: Thu, 29 Oct 2026 06:28:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.468315
• Title: Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits
• Title（参考訳）: マルチアーマッドバンドにおけるミニマックス・最適1次・ベスト・オブ・ボトムワールドレギュレットの同時達成
• Abstract要約: 我々は、多武装の盗賊における一級・一級・一級の後悔の保証について研究する。 我々のアルゴリズムは、最小極最適最悪の後悔と損失依存項が$mathcalO(sqrtK Lstarlog T)$である一階保証を組み合わせる。 我々は,同一のアルゴリズムが,一意のベストアームを持つi.d.損失に対して$mathcalO(sqrtK Lstar)$ regretを伴って,ベスト・オブ・ボスの保証を達成することを示す。
• 参考スコア（独自算出の注目度）: 13.08870048693199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study first-order and best-of-both-worlds regret guarantees in multi-armed bandits. Pogodin and Lattimore (2019) proposed an algorithm that combines minimax-optimal worst-case regret with a first-order guarantee whose loss-dependent term is $\mathcal{O}(\sqrt{K L^\star}\log T)$, where $T$ denotes the horizon, $L^\star$ denotes the smallest expected cumulative loss among fixed arms, and $K$ denotes the number of arms. However, a logarithmic gap remains between this loss-dependent term and the optimal first-order scale. In this paper, we remove this logarithmic factor by proposing an efficient and parameter-free algorithm that achieves the minimax optimal first-order regret guarantee $\mathcal{O}(\sqrt{K L^\star})$. Technically, our algorithm is built upon FTRL with a Tsallis entropy regularizer (Zimmert and Seldin,2021), with a learning rate adapted to the learner's cumulative loss and a sampling distribution determined by a scalar fixed point. This construction controls the combined estimation and stability cost in terms of the learner's loss. Moreover, we show that the same algorithm achieves a best-of-both-worlds guarantee, with $\mathcal{O}(\sum_{i\ne i^\star}\frac{\log T}{Δ_i})$ regret for i.i.d. losses with a unique best arm $i^\star$, where $Δ_i$ denotes the suboptimality gap of arm $i$.
• Abstract（参考訳）: 我々は、多武装の盗賊における一級・一級・一級の後悔の保証について研究する。 Pogodin and Lattimore (2019) は、最小極最適最悪の後悔と損失依存項が $\mathcal{O}(\sqrt{K L^\star}\log T)$ である一階保証とを組み合わせたアルゴリズムを提案した。 しかし、この損失依存項と最適一階スケールの間には対数的ギャップが残っている。 本稿では、この対数係数を、最小極大の1次後悔保証($\mathcal{O}(\sqrt{K L^\star})$)を実現する、効率的かつパラメータフリーなアルゴリズムの提案により除去する。 技術的には、このアルゴリズムは、学習者の累積損失に適応する学習率とスカラー固定点で決定されるサンプリング分布と、Tsallis entropy regularizer (Zimmert and Seldin,2021)を用いてFTRL上に構築されている。 この構成は、学習者の損失の観点から、推定と安定性の複合コストを制御する。 さらに、同一のアルゴリズムは、$\mathcal{O}(\sum_{i\ne i^\star}\frac {\log T}{Δ_i})$ regret for i.d. loss with a unique best arm $i^\star$。

関連論文リスト

• Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity [54.77408659142336]
  我々は,複数の最適な腕を持つマルチアーム・バンディット(MAB)について検討し,実際的な意思決定問題の多くが複数の正解を許容しているという事実に動機づけられた。 たとえば$tildeOBig(fracK-AsqrtKAsqrtT Big)$ minimax regret, where $T$ is the total number of interaction and $tilde O(cdot)$ drops all constant and logarithmic factors。
  論文  参考訳（メタデータ） (2026-09-29T23:33:10Z)
• Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? [11.223878908981725]
  1/2$-Tsallis-INFは、標準的なFTRLアルゴリズムである。 盗賊の対数的擬似回帰を達成しつつ、敵の盗賊の最小限の後悔を保ちながら達成する。 これは自然な疑問を提起する:同じアルゴリズムは、追加の探索なしに、最高の腕を確実に特定できるのか?
  論文  参考訳（メタデータ） (2026-08-15T18:38:36Z)
• Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs [8.923988278588768]
  無限水平マルコフ決定過程(MDP)におけるオンライン強化学習は、そのエピソード的学習よりも理論上、アルゴリズム上は発展していない。 本研究では、古典的平均逆後悔と$$-regretという2つの無限水平目的に対する欠点に対処する。 両設定に適用可能な単一トラクタブルなUPBスタイルのアルゴリズムを開発し、このアルゴリズムは、最初の最適分散依存後悔保証を実現する。
  論文  参考訳（メタデータ） (2026-03-25T04:34:19Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)

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

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