論文の概要: From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards

• arxiv url: http://arxiv.org/abs/2502.09257v3
• Date: Sun, 26 Oct 2025 12:38:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 17:41:21.395949
• Title: From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
• Title（参考訳）: 文脈結合型半帯域からバンドリスト分類へ:スパース・リワードによるサンプル複雑度の改善
• Authors: Liad Erez, Tomer Koren,
• Abstract要約: 我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
• 参考スコア（独自算出の注目度）: 26.147671458980117
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of contextual combinatorial semi-bandits, where input contexts are mapped into subsets of size $m$ of a collection of $K$ possible actions. In each round, the learner observes the realized reward of the predicted actions. Motivated by prototypical applications of contextual bandits, we focus on the $s$-sparse regime where we assume that the sum of rewards is bounded by some value $s\ll K$. For example, in recommendation systems the number of products purchased by any customer is significantly smaller than the total number of available products. Our main result is for the $(\epsilon,\delta)$-PAC variant of the problem for which we design an algorithm that returns an $\epsilon$-optimal policy with high probability using a sample complexity of $\tilde{O}((poly(K/m)+sm/\epsilon^2) \log(|\Pi|/\delta))$ where $\Pi$ is the underlying (finite) class and $s$ is the sparsity parameter. This bound improves upon known bounds for combinatorial semi-bandits whenever $s\ll K$, and in the regime where $s=O(1)$, the leading terms in our bound match the corresponding full-information rates, implying that bandit feedback essentially comes at no cost. Our algorithm is also computationally efficient given access to an ERM oracle for $\Pi$. Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen as a special case with binary reward vectors. In the special case of single-label classification corresponding to $s=m=1$, we prove an $O((K^7+1/\epsilon^2)\log(|H|/\delta))$ sample complexity bound, which improves upon recent results in this scenario. Additionally, we consider the regret minimization setting where data can be generated adversarially, and establish a regret bound of $\tilde O(|\Pi|+\sqrt{smT\log |\Pi|})$, extending the result of Erez et al. (2024) who consider the simpler single label classification setting.
• Abstract（参考訳）: 入力コンテキストを$m$のサブセットにマッピングし,可能なアクションの集合を$K$とする,文脈組合せ半帯域問題について検討する。 各ラウンドにおいて、学習者は予測された行動の実際の報酬を観察する。 文脈的包帯の原型的応用によって動機づけられた我々は、報酬の和がある値$s\ll K$で束縛されていると仮定する$s$スパース体制に焦点を当てる。 例えば、レコメンデーションシステムでは、顧客によって購入される商品の数は、利用可能な製品の総数よりも大幅に少ない。 我々の主な成果は、$(\epsilon,\delta)$-PAC 変種で、$\tilde{O}((poly(K/m)+sm/\epsilon^2) \log(|\Pi|/\delta))$$\Pi$は基礎となる(有限)クラスであり、$s$はスパーシパラメータである。 このバウンダリは、$s\ll K$ と $s=O(1)$ のときの組合せ半バンドの既知のバウンダリと、我々のバウンダリの先頭項が対応する全情報率と一致するような状況において改善され、バンドリットのフィードバックは本質的にコストがかからないことを意味する。 また,ERMオラクルへのアクセスを$\Pi$で行うことにより,計算効率も向上する。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。 単ラベル分類が$s=m=1$に対応する特別な場合、$O((K^7+1/\epsilon^2)\log(|H|/\delta))$サンプル複雑性境界を証明し、このシナリオにおける最近の結果を改善する。 さらに、データを逆向きに生成できる後悔の最小化設定を考慮し、より単純な単一ラベル分類設定を考えるErez et al (2024)の結果を拡張して、$\tilde O(|\Pi|+\sqrt{smT\log |\Pi|})$の後悔の限界を確立する。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
  本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。 この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
  論文  参考訳（メタデータ） (2023-02-07T10:39:44Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• Semi-supervised Active Regression [21.51757844385258]
  本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。 学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
  論文  参考訳（メタデータ） (2021-06-12T03:28:43Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• A Multiclass Classification Approach to Label Ranking [2.6905021039717987]
  マルチクラスの分類において、目標は、$mathcalY=1,; ldots,; K $ with $Kgeq 3$で値を値するランダムラベル$Y$の予測方法を学ぶことである。 本稿では,多クラス分類と後続確率推定の中間点である,この統計的学習問題の解析に焦点をあてる。
  論文  参考訳（メタデータ） (2020-02-21T17:12:43Z)

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

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