論文の概要: Combinatorial Pure Exploration of Dueling Bandit
- arxiv url: http://arxiv.org/abs/2006.12772v1
- Date: Tue, 23 Jun 2020 05:36:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 22:34:54.979977
- Title: Combinatorial Pure Exploration of Dueling Bandit
- Title（参考訳）: デューリングバンドの組合せ純粋探索
- Authors: Wei Chen, Yihan Du, Longbo Huang, Haoyu Zhao
- Abstract要約: デュエルバンディット(CPE-DB)の純粋探索に関する研究
各ラウンドで2人の候補者のデュエルを1つのポジションでサンプリングし、誰がデュエルで勝つかを観察する。
CPE-DBは、マルチアーム・バンディット(CPE-MAB)問題に対する本来の純粋探索をデュエル・バンディット・セッティングに適応させるものである。
- 参考スコア（独自算出の注目度）: 35.102653686701444
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study combinatorial pure exploration for dueling bandits
(CPE-DB): we have multiple candidates for multiple positions as modeled by a
bipartite graph, and in each round we sample a duel of two candidates on one
position and observe who wins in the duel, with the goal of finding the best
candidate-position matching with high probability after multiple rounds of
samples. CPE-DB is an adaptation of the original combinatorial pure exploration
for multi-armed bandit (CPE-MAB) problem to the dueling bandit setting.
We consider both the Borda winner and the Condorcet winner cases. For Borda
winner, we establish a reduction of the problem to the original CPE-MAB setting
and design PAC and exact algorithms that achieve both the sample complexity
similar to that in the CPE-MAB setting (which is nearly optimal for a subclass
of problems) and polynomial running time per round.
For Condorcet winner, we first design a fully polynomial time approximation
scheme (FPTAS) for the offline problem of finding the Condorcet winner with
known winning probabilities, and then use the FPTAS as an oracle to design a
novel pure exploration algorithm ${\sf CAR}$-${\sf Cond}$ with sample
complexity analysis. ${\sf CAR}$-${\sf Cond}$ is the first algorithm with
polynomial running time per round for identifying the Condorcet winner in
CPE-DB.
- Abstract（参考訳）: 本稿では,2部グラフでモデル化された複数の位置の候補を複数有し,各ラウンドにおいて1つの位置において2人の候補の決闘をサンプリングし,決闘の勝者を観察し,複数のラウンドの後に高い確率で一致した最良候補位置を求めることを目的とする。
CPE-DBは、マルチアームバンディット(CPE-MAB)問題に対する元の組合せ純粋探索の適応である。
Bordaの勝者とCondorcetの勝者の双方について検討する。
ボルダの受賞者については、元のcpe-mab設定と設計pacと、cpe-mab設定(問題のサブクラスにほぼ最適である)と1ラウンドあたりの多項式実行時間とのようなサンプルの複雑さを両立する厳密なアルゴリズムに問題を還元する。
コンドルセットの勝者にとって、まず、勝利確率が既知のコンドルセットの勝者を見つけるというオフライン問題に対する完全多項式時間近似スキーム(FPTAS)を設計し、次にFPTASを用いて新しい純粋探索アルゴリズムである${\sf CAR}$-${\sf Cond}$をサンプル複雑性解析で設計する。
${\sf CAR}$-${\sf Cond}$は、CPE-DBにおけるCondorcetの勝者を特定するために、1ラウンドあたりの多項式実行時間を持つ最初のアルゴリズムである。
関連論文リスト
- Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。
われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。
我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
論文 参考訳（メタデータ） (2024-04-09T04:45:18Z) - Identifying Copeland Winners in Dueling Bandits with Indifferences [12.96903983663382]
本研究は,3次フィードバックを伴うデュエルバンディット問題において,コペランドの勝者を識別するタスクについて考察する。
我々は,Copeland の勝者を固定誤差確率で求める学習アルゴリズムに対して,サンプルの複雑性を低くする。
我々は,この下界とほぼ一致し,優れた経験的性能を示すサンプル複雑性を持つアルゴリズムPOCOWISTAを提案する。
論文 参考訳（メタデータ） (2023-10-01T17:59:27Z) - Thompson Sampling for Real-Valued Combinatorial Pure Exploration of
Multi-Armed Bandit [65.268245109828]
本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。
一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これは,アクションセットのサイズが指数関数的に$d$で大きい場合でも動作可能な,最初のアルゴリズムである。
論文 参考訳（メタデータ） (2023-08-20T11:56:02Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Dueling Bandits: From Two-dueling to Multi-dueling [40.4378338001229]
エージェントが複数の選択肢を同時に比較し、最適な腕を選択することで後悔を最小限に抑える、一般的なマルチダウリングバンディット問題について検討する。
この設定は従来の二段バンディット問題を一般化し、複数の選択肢に対する主観的なフィードバックを含む現実世界の多くのアプリケーションを見つける。
論文 参考訳（メタデータ） (2022-11-16T22:00:54Z) - Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
シュルツ法(schulze method)と呼ばれる,有名な単勝投票ルールの計算的側面について検討した。
私たちの論文は、計算社会的選択の分野に微細な複雑さをもたらす最初のものです。
論文 参考訳（メタデータ） (2021-03-05T22:27:36Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳（メタデータ） (2020-02-03T04:58:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。