論文の概要: Adversarial Combinatorial Semi-bandits with Graph Feedback
- arxiv url: http://arxiv.org/abs/2502.18826v2
- Date: Fri, 28 Feb 2025 00:20:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-03 13:43:10.234642
- Title: Adversarial Combinatorial Semi-bandits with Graph Feedback
- Title（参考訳）: グラフフィードバックを用いた逆アベレーティブ半帯域
- Authors: Yuxiao Wen,
- Abstract要約: 時間的地平線上での最適後悔は、$widetildeTheta(SsqrtT+sqrtalpha ST)$としてスケールする。
重要な技術的要素は、負の相関を持つランダム決定ベクトルを用いて凸化作用を実現することである。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: In combinatorial semi-bandits, a learner repeatedly selects from a combinatorial decision set of arms, receives the realized sum of rewards, and observes the rewards of the individual selected arms as feedback. In this paper, we extend this framework to include \emph{graph feedback}, where the learner observes the rewards of all neighboring arms of the selected arms in a feedback graph $G$. We establish that the optimal regret over a time horizon $T$ scales as $\widetilde{\Theta}(S\sqrt{T}+\sqrt{\alpha ST})$, where $S$ is the size of the combinatorial decisions and $\alpha$ is the independence number of $G$. This result interpolates between the known regrets $\widetilde\Theta(S\sqrt{T})$ under full information (i.e., $G$ is complete) and $\widetilde\Theta(\sqrt{KST})$ under the semi-bandit feedback (i.e., $G$ has only self-loops), where $K$ is the total number of arms. A key technical ingredient is to realize a convexified action using a random decision vector with negative correlations.
- Abstract（参考訳）: 組み合わせセミバンドにおいて、学習者は、組み合わせ決定セットから繰り返し選択し、実現された報酬の合計を受信し、個々の選択されたアームの報酬をフィードバックとして観察する。
本稿では,このフレームワークを,学習者が選択した腕のすべての腕の報酬をフィードバックグラフG$で観察する「emph{graph feedback}」を含むように拡張する。
時間的地平線上での最適後悔$T$は$\widetilde{\Theta}(S\sqrt{T}+\sqrt{\alpha ST})$とスケールし、$S$は組合せ決定のサイズであり、$\alpha$は$G$の独立数である。
この結果は、既知の後悔である$\widetilde\Theta(S\sqrt{T})$を完全な情報(すなわち、$G$は完全である)と$\widetilde\Theta(\sqrt{KST})$を半帯域フィードバック(すなわち、$G$は自己ループしか持たない)で補間する。
重要な技術的要素は、負の相関を持つランダム決定ベクトルを用いて凸化作用を実現することである。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。
その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
論文 参考訳（メタデータ） (2023-07-14T10:38:30Z) - Combinatorial Neural Bandits [10.463365653675694]
学習エージェントが各ラウンドでアームのサブセットを選択し、そのスコアに応じて選択したアームのフィードバックを受け取るというコンテキスト的盗聴問題を考える。
アルゴリズムを提案する: Combinatorial Neural UCB(textttCN-UCB)と Combinatorial Thompson Sampling(textttCN-TS$)。
論文 参考訳（メタデータ） (2023-05-31T23:27:58Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳（メタデータ） (2021-12-13T09:48:54Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - 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) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。