論文の概要: On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization

• arxiv url: http://arxiv.org/abs/2605.02141v1
• Date: Mon, 04 May 2026 01:46:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-05 20:33:50.102391
• Title: On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
• Title（参考訳）: KL正則化によるオフラインマルチArmed Banditの最適サンプル複素度について
• Authors: Kaixuan Ji, Qiwei Di, Heyang Zhao, Qingyue Zhao, Quanquan Gu,
• Abstract要約: Kullback-Leibler (KL) の正規化は、オフラインの意思決定で広く使われている。 大規模な正規化の下では$tildeO(SAC*/)$のサンプル複雑性を実現する。 また、よりシャープなサンプル複雑性の下界も提供し、これは正規化強度の全範囲にわたる上界と一致する。
• 参考スコア（独自算出の注目度）: 54.77408659142336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kullback-Leibler (KL) regularization is widely used in offline decision-making and offers several benefits, motivating recent work on the sample complexity of offline learning with respect to KL-regularized performance metrics. Nevertheless, the exact sample complexity of KL-regularized offline learning remains largely from fully characterized. In this paper, we study this question in the setting of multi-armed bandits (MABs). We provide a sharp analysis of KL-PCB (Zhao et al., 2026), showing that it achieves a sample complexity of $\tilde{O}(ηSAC^{π^*}/ε)$ under large regularization $η= \tilde{O}(ε^{-1})$, and a sample complexity of $\tildeΩ(SAC^{π^*}/ε^2)$ under small regularization $η= \tildeΩ(ε^{-1})$, where $η$ is the regularization parameter, $S$ is the number of contexts, $A$ is the number of arms, $C^{π^*}$ policy coverage coefficient at the optimal policy $π^*$, $ε$ is the desired sub-optimality, and $\tilde{O}$ and $\tildeΩ$ hide all poly-logarithmic factors. We further provide a pair of sharper sample complexity lower bounds, which matches the upper bounds over the entire range of regularization strengths. Overall, our results provide a nearly complete characterization of offline multi-armed bandits with KL regularization.
• Abstract（参考訳）: Kullback-Leibler(KL)正則化は、オフライン意思決定で広く使われており、いくつかの利点を提供している。 それでも、KL規則化されたオフライン学習の正確なサンプル複雑さは、ほとんど完全に特徴づけられるものではない。 本稿では,マルチアームバンディット(MAB)の設定において,この問題を考察する。 我々は KL-PCB (Zhao et al , 2026) の急激な解析を行い、KL-PCB (Zhao et al , 2026) の標本複雑性を$\tilde{O}(ηSAC^{π^*}/ε)$ の大正規化$η= \tilde{O}(ε^{-1})$ のサンプル複雑性と小正規化$η= \tildeΩ(SAC^{π^*}/ε^2)$ のサンプル複雑性を達成できることを示した。 さらに、よりシャープなサンプルの複雑さの低い境界が提供され、これは正規化強度の全範囲にわたる上限と一致する。 以上の結果から,KL正則化によるオフラインマルチアームバンディットのほぼ完全な特徴付けが得られた。

関連論文リスト

• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
  最短経路問題(SSP)問題において,$$-optimal Policy($-optimal Policy)を学習する際のサンプル複雑性について検討した。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。 驚くべきことに、$c_min = 0$のSSP問題はいつでも学習できない。
  論文  参考訳（メタデータ） (2026-04-17T14:47:52Z)
• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  KL正規化目標に対するオンライン学習の統計的効率について検討する。 我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
  論文  参考訳（メタデータ） (2026-03-02T18:17:33Z)
• 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)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
  未知の報酬$g(gamma, v)$が提案されたしきい値$gamma$と潜伏値$v$に依存する問題を示し、そのしきい値が未知の潜伏値よりも低い場合のみ$$を達成できる。 この問題は、オンラインオークションにおける予約価格の最適化、クラウドソーシングにおけるオンラインタスクの割り当て、雇用におけるリクルートバーの設定など、現実的なシナリオにおける幅広い応用がある。
  論文  参考訳（メタデータ） (2023-12-07T19:30:08Z)
• Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
  平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。 これは文学の下位境界に到達した最初のアルゴリズムと分析である。
  論文  参考訳（メタデータ） (2023-10-13T03:08:59Z)

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

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