論文の概要: Near-Optimal Regret for KL-Regularized Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2603.02155v1
• Date: Mon, 02 Mar 2026 18:17:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-03 19:50:57.026825
• Title: Near-Optimal Regret for KL-Regularized Multi-Armed Bandits
• Title（参考訳）: KL規則化マルチアーマッド帯域の準最適レグレット
• Authors: Kaixuan Ji, Qingyue Zhao, Heyang Zhao, Qiwei Di, Quanquan Gu,
• Abstract要約: KL正規化目標に対するオンライン学習の統計的効率について検討する。 我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
• 参考スコア（独自算出の注目度）: 54.77408659142336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent studies have shown that reinforcement learning with KL-regularized objectives can enjoy faster rates of convergence or logarithmic regret, in contrast to the classical $\sqrt{T}$-type regret in the unregularized setting. However, the statistical efficiency of online learning with respect to KL-regularized objectives remains far from completely characterized, even when specialized to multi-armed bandits (MABs). We address this problem for MABs via a sharp analysis of KL-UCB using a novel peeling argument, which yields a $\tilde{O}(ηK\log^2T)$ upper bound: the first high-probability regret bound with linear dependence on $K$. Here, $T$ is the time horizon, $K$ is the number of arms, $η^{-1}$ is the regularization intensity, and $\tilde{O}$ hides all logarithmic factors except those involving $\log T$. The near-tightness of our analysis is certified by the first non-constant lower bound $Ω(ηK \log T)$, which follows from subtle hard-instance constructions and a tailored decomposition of the Bayes prior. Moreover, in the low-regularization regime (i.e., large $η$), we show that the KL-regularized regret for MABs is $η$-independent and scales as $\tildeΘ(\sqrt{KT})$. Overall, our results provide a thorough understanding of KL-regularized MABs across all regimes of $η$ and yield nearly optimal bounds in terms of $K$, $η$, and $T$.
• Abstract（参考訳）: 近年の研究では、KL正規化目的による強化学習は、非正規化条件における古典的な$\sqrt{T}$-type後悔とは対照的に、収束率や対数後悔の速さを享受できることが示されている。 しかし、KL規則化された目的に対するオンライン学習の統計的効率は、マルチアーム・バンディット(MAB)に特化しても、完全に特徴付けられていない。 我々は, KL-UCB の急激な解析によりMAB のこの問題に対処し, K$ 上の線形依存に縛られた最初の高確率な再帰を$\tilde{O}(ηK\log^2T)$上界とする。 ここで、$T$は時間軸、$K$は武器の数、$η^{-1}$は正規化強度、$\tilde{O}$は$\log T$を含むものを除いて全ての対数要素を隠す。 我々の分析のほぼ高所性は、微妙なハード・インスタンス構造とベイズの事前の調整された分解から導かれる最初の非コンスタントな下界$Ω(ηK \log T)$によって証明される。 さらに、低正規化(すなわち大きな$η$)では、MABsに対するKL正規化後悔は$η$非依存であり、$\tilde'(\sqrt{KT})$としてスケールすることを示す。 全体として、我々の結果はKL規則化されたMABを$η$と$η$と$T$の全ての条件で完全に理解し、ほぼ最適な境界を$K$と$η$と$T$の条件で得られる。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• 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)
• Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
  我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。 逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。 我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
  論文  参考訳（メタデータ） (2023-11-02T03:41:58Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs [12.450760567361531]
  オンライン学習問題では,低分散の活用がパフォーマンス保証の厳密化に重要な役割を果たしている。 本研究は, 後悔の限界を著しく改善する新たな分析法を提案する。 我々の分析は、新しい楕円型ポテンシャル数補題に依存している。
  論文  参考訳（メタデータ） (2021-11-05T06:47:27Z)
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
  SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。 本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。 1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
  論文  参考訳（メタデータ） (2021-10-13T17:50:46Z)
• Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits [12.462608802359936]
  Zimmert and Seldin (2021) の Tsallis-INF アルゴリズムに対する後悔の境界を改善した。 特に、$C = Thetaleft(fracTlog Tlog T$)$の場合、$T$が時空である場合、乗算因子による改善を達成します。 また, time horizon 上の後悔の依存性を $log t$ から $log frac(k-1)t(sum_ineq i*frac1delta_ に改善する。
  論文  参考訳（メタデータ） (2021-03-23T12:26:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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