論文の概要: Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

• arxiv url: http://arxiv.org/abs/2607.13686v1
• Date: Wed, 15 Jul 2026 10:28:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-16 16:39:12.744065
• Title: Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
• Title（参考訳）: 一般関数近似を用いた最適かつ効率的な組合せ半帯域
• Authors: Hao Qin, Chicheng Zhang,
• Abstract要約: ここで、SquareCB.Combは、$O(sqrtm A T log |mathcalF|)$、$A$は腕の数、$m$はアクションにおける腕の最大数、$T$は時間的地平線である。 実現可能な設定では、この境界はポリシー検索ベースのアルゴリズムによって達成された、最先端の後悔の保証と一致する。
• 参考スコア（独自算出の注目度）: 17.2911371867411
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the contextual combinatorial semi-bandit (CCSB) problem with general reward function approximation. At each round, the learner observes a context, selects a combinatorial action consisting of a subset of basic arms, and receives the reward of each selected arm; the goal is to maximize the cumulative reward over time. We propose SquareCB.Comb, a computationally efficient algorithm that, at each round, solves a convex optimization problem to sample a combinatorial action that balances exploration and exploitation. SquareCB.Comb scales to large arm sets and imposes no structural assumptions on the action set beyond a cardinality bound of $m$ on each combinatorial action. We prove that SquareCB.Comb achieves a minimax optimal regret bound of $O(\sqrt{m A T \log |\mathcal{F}|})$, where $A$ is the number of arms, $m$ is the maximum number of arms in a combinatorial action, $T$ is the time horizon, and $\mathcal{F}$ is the reward function class. In the realizable setting, this bound matches the state-of-the-art regret guarantees achieved by policy search-based algorithms in the more restricted slate recommendation settings, while simultaneously generalizing to arbitrary combinatorial action structures and general reward function approximation.
• Abstract（参考訳）: 本稿では,一般報酬関数近似を用いた文脈組合せ半帯域問題(CCSB)について検討する。 各ラウンドにおいて、学習者はコンテキストを観察し、基本アームのサブセットからなる組合せアクションを選択し、選択された各アームの報酬を受け取り、その目標は累積報酬を時間とともに最大化することである。 計算効率のよいSquareCB.Combを提案する。このアルゴリズムは各ラウンドで凸最適化問題を解き、探索と利用のバランスをとる組合せ作用をサンプリングする。 SquareCB.Comb は、大きなアームセットにスケールし、各組合せアクションに対して、濃度境界の$m$を越えて設定されたアクションに構造的な仮定を課さない。 ここでは、$A$ はアームの数、$m$ は組み合わせアクションにおけるアームの最大数、$T$ は時間地平線、$\mathcal{F}$ は報酬関数クラスである。 実現可能な設定では、このバウンダリは、より制限されたスレートレコメンデーション設定においてポリシーベースのアルゴリズムによって達成される、最先端の後悔の保証と一致し、同時に任意の組合せアクション構造と一般報酬関数近似に一般化する。

関連論文リスト

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  このモデルは、$M$armと$K$playで構成されている。 各アームには複数の能力があり、各ユニットの能力は報酬関数に関連付けられている。 複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。
  論文  参考訳（メタデータ） (2025-12-25T11:19:09Z)
• Multi-Play Combinatorial Semi-Bandit Problem [8.922365714546162]
  半帯域(CSB)問題において、プレイヤーはアクションセットからアクションを選択し、アクションに含まれるベースアームからのフィードバックを観察する。 マルチプレイ・セミバンド (MP-CSB) を提案し、プレイヤーは非負の整数アクションを選択し、各ラウンドで1つの腕から複数のフィードバックを観測できる。
  論文  参考訳（メタデータ） (2025-09-12T02:46:59Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes [8.919345630832366]
  本稿では,アクションセットと時間変化によるベースアームの可利用性に関するコンテキスト的帯域幅問題について考察する。 我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。 アルゴリズムを劇的に高速化するために,スパースGPを用いたO'CLOK-UCBの変種を提案する。
  論文  参考訳（メタデータ） (2021-10-05T18:02:10Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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