論文の概要: Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback
- arxiv url: http://arxiv.org/abs/2305.16074v1
- Date: Thu, 25 May 2023 14:02:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 14:49:49.893380
- Title: Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback
- Title（参考訳）: 最大値インデクスフィードバックによる最大値リワード関数の組合せ帯域
- Authors: Yiliu Wang, Wei Chen, and Milan Vojnovi\'c
- Abstract要約: 本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
- 参考スコア（独自算出の注目度）: 9.771002043127728
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a combinatorial multi-armed bandit problem for maximum value
reward function under maximum value and index feedback. This is a new feedback
structure that lies in between commonly studied semi-bandit and full-bandit
feedback structures. We propose an algorithm and provide a regret bound for
problem instances with stochastic arm outcomes according to arbitrary
distributions with finite supports. The regret analysis rests on considering an
extended set of arms, associated with values and probabilities of arm outcomes,
and applying a smoothness condition. Our algorithm achieves a
$O((k/\Delta)\log(T))$ distribution-dependent and a $\tilde{O}(\sqrt{T})$
distribution-independent regret where $k$ is the number of arms selected in
each round, $\Delta$ is a distribution-dependent reward gap and $T$ is the
horizon time. Perhaps surprisingly, the regret bound is comparable to
previously-known bound under more informative semi-bandit feedback. We
demonstrate the effectiveness of our algorithm through experimental results.
- Abstract（参考訳）: 最大値とインデックスフィードバックの下での最大値報酬関数に対する組合せ多腕バンディット問題を考える。
これは、よく研究されている半帯域と完全帯域のフィードバック構造の間にある新しいフィードバック構造である。
有限サポートを持つ任意の分布に従って確率的アームアウトカムを持つ問題インスタンスに対して,アルゴリズムを提案し,後悔のバウンドを与える。
後悔の分析は、腕の成果の値と確率に関連する拡張されたアームセットを考慮し、滑らかな条件を適用している。
我々のアルゴリズムは、$O(((k/\Delta)\log(T))$ distribution-dependent and a $\tilde{O}(\sqrt{T})$ distribution-independent regret, $k$ is the number of arms in each round, $\Delta$ is a distribution-dependent reward gap, $T$ is the horizon time。
おそらく意外なことに、後悔の限界は、より情報的な半帯域フィードバックの下で、これまで知られていた境界に匹敵する。
実験により,本アルゴリズムの有効性を実証した。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-14T12:58:46Z) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳（メタデータ） (2021-10-05T18:02:10Z) - Continuous Time Bandits With Sampling Costs [17.412117389855222]
連続時間マルチアームバンディット問題 (CTMAB) を考えると, 学習者は任意の間隔で何回でもアームをサンプリングし, サンプルからランダムな報酬を得ることができる。
サンプリング周波数の関数として、大きな報酬を得ることとサンプリングコストをもたらすことにはトレードオフがある。
目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
論文 参考訳（メタデータ） (2021-07-12T10:00:35Z) - 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) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。