論文の概要: Batched Dueling Bandits
- arxiv url: http://arxiv.org/abs/2202.10660v1
- Date: Tue, 22 Feb 2022 04:02:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-24 03:19:30.728725
- Title: Batched Dueling Bandits
- Title（参考訳）: 一括デュエルバンディット
- Authors: Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan
- Abstract要約: そこで本研究では,2つの標準設定条件下で,K$アームのデュエルバンディット問題について検討した。
バッチ数と後悔数のトレードオフを円滑に行うアルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 13.69077222007053
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The $K$-armed dueling bandit problem, where the feedback is in the form of
noisy pairwise comparisons, has been widely studied. Previous works have only
focused on the sequential setting where the policy adapts after every
comparison. However, in many applications such as search ranking and
recommendation systems, it is preferable to perform comparisons in a limited
number of parallel batches. We study the batched $K$-armed dueling bandit
problem under two standard settings: (i) existence of a Condorcet winner, and
(ii) strong stochastic transitivity and stochastic triangle inequality. For
both settings, we obtain algorithms with a smooth trade-off between the number
of batches and regret. Our regret bounds match the best known sequential regret
bounds (up to poly-logarithmic factors), using only a logarithmic number of
batches. We complement our regret analysis with a nearly-matching lower bound.
Finally, we also validate our theoretical results via experiments on synthetic
and real data.
- Abstract（参考訳）: k$-armed dueling bandit問題(英語版)は、フィードバックがノイズの多い対数比較の形式である)は、広く研究されている。
これまでの作業は、各比較の後にポリシーが適応するシーケンシャルな設定にのみ焦点が当てられていた。
しかし,検索ランキングやレコメンデーションシステムといった多くのアプリケーションでは,限られた数の並列バッチで比較を行うことが望ましい。
我々は2つの標準設定の下で、k$-armed dueling bandit問題の研究を行った。
(i)condorcetの勝者の存在
(ii)強い確率的推移性と確率的三角不等式。
どちらの設定でも、バッチ数と後悔のトレードオフをスムーズに行うアルゴリズムを得る。
我々の後悔の限界は、最もよく知られた連続的な後悔の限界(多対数因子まで)に一致する。
我々は、ほぼ一致する下限で後悔の分析を補完する。
最後に, 合成データおよび実データを用いた実験により, 理論結果を検証した。
関連論文リスト
- Neural Dueling Bandits [58.90189511247936]
ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。
次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
論文 参考訳（メタデータ） (2024-07-24T09:23:22Z) - Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。
われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。
我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
論文 参考訳（メタデータ） (2024-04-09T04:45:18Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Dueling Bandits: From Two-dueling to Multi-dueling [40.4378338001229]
エージェントが複数の選択肢を同時に比較し、最適な腕を選択することで後悔を最小限に抑える、一般的なマルチダウリングバンディット問題について検討する。
この設定は従来の二段バンディット問題を一般化し、複数の選択肢に対する主観的なフィードバックを含む現実世界の多くのアプリケーションを見つける。
論文 参考訳（メタデータ） (2022-11-16T22:00:54Z) - An Asymptotically Optimal Batched Algorithm for the Dueling Bandit
Problem [13.69077222007053]
従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。
我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。
実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
論文 参考訳（メタデータ） (2022-09-25T00:23:55Z) - The Impact of Batch Learning in Stochastic Linear Bandits [7.3449418475577595]
本稿では,特定の期間にエージェントが応答のバッチを観察する,バッチ化バンドイットと呼ばれるバンディット問題の特殊な事例について考察する。
本研究の主な理論的結果は,バッチ学習の効果がオンライン行動の後悔に比例して測定できることを示唆している。
論文 参考訳（メタデータ） (2022-02-14T12:27:06Z) - Batched Neural Bandits [107.5072688105936]
BatchNeuralUCBはニューラルネットワークと楽観性を組み合わせ、探索と探索のトレードオフに対処する。
BatchNeuralUCBは、完全なシーケンシャルバージョンと同じ後悔を達成しつつ、ポリシー更新の数を大幅に減らしています。
論文 参考訳（メタデータ） (2021-02-25T17:36:44Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。