論文の概要: Adversarial Multi-dueling Bandits
- arxiv url: http://arxiv.org/abs/2406.12475v1
- Date: Tue, 18 Jun 2024 10:28:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-19 19:27:22.533115
- Title: Adversarial Multi-dueling Bandits
- Title（参考訳）: 対訳 マルチ・ダウリング・バンド
- Authors: Pratik Gajane,
- Abstract要約: 対戦型多段バンディットにおける後悔の問題について紹介する。
このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
- 参考スコア（独自算出の注目度）: 0.4467766778351321
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the problem of regret minimization in adversarial multi-dueling bandits. While adversarial preferences have been studied in dueling bandits, they have not been explored in multi-dueling bandits. In this setting, the learner is required to select $m \geq 2$ arms at each round and observes as feedback the identity of the most preferred arm which is based on an arbitrary preference matrix chosen obliviously. We introduce a novel algorithm, MiDEX (Multi Dueling EXP3), to learn from such preference feedback that is assumed to be generated from a pairwise-subset choice model. We prove that the expected cumulative $T$-round regret of MiDEX compared to a Borda-winner from a set of $K$ arms is upper bounded by $O((K \log K)^{1/3} T^{2/3})$. Moreover, we prove a lower bound of $\Omega(K^{1/3} T^{2/3})$ for the expected regret in this setting which demonstrates that our proposed algorithm is near-optimal.
- Abstract（参考訳）: 本稿では,敵対的マルチダウリング・バンディットにおける後悔の最小化の問題を紹介する。
デュエルバンディットでは敵の嗜好が研究されているが、マルチダウリングバンディットでは研究されていない。
この設定では、学習者は各ラウンドで$m \geq 2$ Armを選択し、選択された任意の選好行列に基づいて最も好まれるアームのアイデンティティをフィードバックとして観察する。
そこで我々は,ペアワイズ・サブセット選択モデルから生成されると考えられるような選好フィードバックから学習するために,新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
我々は、期待されるMiDEXの累積的な$T$ラウンド後悔を、K$アームの集合のボルダ・ウィンナーと比較すると、$O((K \log K)^{1/3} T^{2/3})$で上界であることを証明する。
さらに、提案アルゴリズムがほぼ最適であることを示すこの設定において、期待される後悔に対して、$\Omega(K^{1/3} T^{2/3})$の低い境界を証明した。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - Dueling Bandits: From Two-dueling to Multi-dueling [40.4378338001229]
エージェントが複数の選択肢を同時に比較し、最適な腕を選択することで後悔を最小限に抑える、一般的なマルチダウリングバンディット問題について検討する。
この設定は従来の二段バンディット問題を一般化し、複数の選択肢に対する主観的なフィードバックを含む現実世界の多くのアプリケーションを見つける。
論文 参考訳（メタデータ） (2022-11-16T22:00:54Z) - Non-Stationary Dueling Bandits [8.298716599039501]
我々は、非定常デュエルバンディット問題をK$アームで研究し、タイムホライズメント$T$は、固定セグメント$M$からなる。
蓄積した後悔を最小限に抑えるため、学習者は各定常セグメントのコンドルチェットの勝者をできるだけ頻繁に選ぶ必要がある。
我々は、M$やT$の知識を必要とせず、非定常ケースに対する後悔の意を示す。
論文 参考訳（メタデータ） (2022-02-02T09:57: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) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。