論文の概要: The Sample Complexity of Multiclass and Sparse Contextual Bandits

• arxiv url: http://arxiv.org/abs/2605.29645v1
• Date: Thu, 28 May 2026 09:12:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-30 02:45:56.098759
• Title: The Sample Complexity of Multiclass and Sparse Contextual Bandits
• Title（参考訳）: マルチクラス・スパース・コンテクストバンドのサンプル複雑度
• Authors: Liad Erez, Fan Chen, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran, Alexander Rakhlin,
• Abstract要約: 我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
• 参考スコア（独自算出の注目度）: 106.74652380822778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study contextual bandits in the stochastic i.i.d.\ setting, where a learner observes contexts drawn from an unknown distribution, selects actions from a finite set $A$, and aims to identify an approximately optimal policy from a given class based on bandit feedback. Motivated by bandit multiclass classification with zero-one rewards, we focus on the \emph{$s$-sparse} setting in which, for every context, the reward vector has $L_1$-norm at most $s \ll |A|$. Our main result is the design of algorithms that, with high probability, output an $ε$-optimal policy compared to policy class $Π$ using $\tilde{O} ((s/ε^2 + |A|/ε)\log |Π|/δ)$ samples. We extend this bound to general Natarajan classes and complement it with a matching lower bound (up to logarithmic factors), thereby closing a substantial gap left by prior work (Erez et al., 2024, 2025), which incurred an additional $Θ(|A|^9)$ dependence. We obtain these results via two complementary approaches. First, we analyze contextual bandits through the lens of contextual decision making with structured observations, designing an exploration-by-optimization algorithm whose sample complexity is governed by the \emph{decision-estimation coefficient} (DEC; Foster et al., 2021, 2022). We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate. Since this approach is largely information-theoretic and involves solving complex min-max optimization problems, we also develop a second, more specialized algorithmic method based on a low-variance exploration technique. This approach leads to concrete, tractable algorithms and naturally extends to contextual combinatorial semi-bandits, leading to improved sample complexity guarantees for bandit multiclass list classification.
• Abstract（参考訳）: そこでは,学習者が未知の分布から引き出された文脈を観察し,有限集合の$A$から行動を選択し,帯域幅フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを同定することを目的とした,確率的i.d.\セッティングの文脈的帯域幅について検討する。 任意の文脈において、報酬ベクトルは、ほとんどの$s \ll |A|$に対して$L_1$-norm を持つような \emph{$s$-sparse} 設定にフォーカスする。 我々の主な結果は、高い確率で、$\tilde{O} ((s/ε^2 + |A|/ε)\log |\|/δ)$サンプルを使用して、$ε$最適化ポリシーを$\tilde{O} ((s/ε^2 + |A|/ε)\log |\|/δ)$サンプルを用いて出力するアルゴリズムの設計である。 この境界を一般のナタラジャン類に拡張し、それと一致する下界(対数的因子まで)で補うことにより、事前の作業(Erez et al , 2024, 2025)によって残された実質的なギャップを閉じる。 これらの結果は2つの相補的なアプローチによって得られる。 まず、構造化された観測による文脈決定のレンズを用いて文脈的帯域幅を解析し、サンプルの複雑さを推定係数(DEC; Foster et al , 2021, 2022)で制御する探索・最適化アルゴリズムを設計する。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。 このアプローチは主に情報理論であり、複雑な min-max 最適化問題を解くことを伴うため、低分散探索技術に基づく第二のより専門的なアルゴリズム手法も開発する。 このアプローチは具体的かつトラクタブルなアルゴリズムにつながり、自然に文脈的組合せ半帯域に拡張され、バンディットのマルチクラスリスト分類におけるサンプル複雑性の保証が向上する。

関連論文リスト

• Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback [0.8287206589886881]
  本稿では,ロジスティック・コンテクスト・スレート・バンド問題について考察する。 選択したスレートに対して、ロジスティックモデルにより決定された単一のバイナリ報酬が観測される。 本稿では,Slate-GLM-OFUとSlate-GLM-TSの2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-16T07:19:02Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• 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)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。 提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-20T06:36:19Z)

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

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