論文の概要: Regret Minimization in Stochastic Contextual Dueling Bandits
- arxiv url: http://arxiv.org/abs/2002.08583v2
- Date: Sun, 9 May 2021 00:21:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 06:41:27.331718
- Title: Regret Minimization in Stochastic Contextual Dueling Bandits
- Title（参考訳）: 確率的コンテクスト・デュエル・バンディットにおける後悔の最小化
- Authors: Aadirupa Saha and Aditya Gopalan
- Abstract要約: 我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 40.17224226373741
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of stochastic $K$-armed dueling bandit in the
contextual setting, where at each round the learner is presented with a context
set of $K$ items, each represented by a $d$-dimensional feature vector, and the
goal of the learner is to identify the best arm of each context sets. However,
unlike the classical contextual bandit setup, our framework only allows the
learner to receive item feedback in terms of their (noisy) pariwise
preferences--famously studied as dueling bandits which is practical interests
in various online decision making scenarios, e.g. recommender systems,
information retrieval, tournament ranking, where it is easier to elicit the
relative strength of the items instead of their absolute scores. However, to
the best of our knowledge this work is the first to consider the problem of
regret minimization of contextual dueling bandits for potentially infinite
decision spaces and gives provably optimal algorithms along with a matching
lower bound analysis. We present two algorithms for the setup with respective
regret guarantees $\tilde O(d\sqrt{T})$ and $\tilde O(\sqrt{dT \log K})$.
Subsequently we also show that $\Omega(\sqrt {dT})$ is actually the fundamental
performance limit for this problem, implying the optimality of our second
algorithm. However the analysis of our first algorithm is comparatively
simpler, and it is often shown to outperform the former empirically. Finally,
we corroborate all the theoretical results with suitable experiments.
- Abstract（参考訳）: 文脈設定における確率的$k$-armed dueling banditの問題を考察し、各ラウンドにおいて学習者には$k$アイテムのコンテキストセットが提示され、それぞれが$d$-dimensional feature vectorで表現され、学習者の目標は各コンテキストセットの最高のアームを特定することである。
しかし、従来の文脈的帯域設定とは異なり、我々のフレームワークでは、学習者がアイテムの相対的強度を絶対スコアではなく引き出すのが容易な、推薦システム、情報検索、トーナメントランキングなど、様々なオンライン意思決定シナリオにおいて実践的な関心を持つデュエル・バンディットとして、それぞれの(ノイズの多い)パーソナライズの観点からのみアイテムフィードバックを受け取ることができる。
しかしながら、我々の知る限りでは、この研究は、潜在的に無限な決定空間に対する文脈的デュエル・バンディットの後悔の最小化の問題を最初に考慮し、適切なアルゴリズムと一致する下限解析を与える。
提案するアルゴリズムは, それぞれ, $\tilde O(d\sqrt{T})$ と $\tilde O(\sqrt{dT \log K})$ である。
その後、$\Omega(\sqrt {dT})$がこの問題の基本的な性能限界であることを示し、2番目のアルゴリズムの最適性を示している。
しかし,第1のアルゴリズムの解析は比較的単純であり,前者よりも優れていることがしばしば示される。
最後に、すべての理論結果を適切な実験で照合します。
関連論文リスト
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - 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) - Contextual Bandits and Imitation Learning via Preference-Based Active
Queries [17.73844193143454]
本研究では,学習者が実行された行動報酬の直接的な知識を欠いている文脈的包帯と模倣学習の問題を考察する。
その代わり、学習者は各ラウンドのエキスパートに積極的に問い合わせて2つのアクションを比較し、ノイズの多い好みのフィードバックを受け取ることができる。
学習者の目的は、実行されたアクションに関連する後悔を最小限に抑えると同時に、専門家が行った比較クエリの数を最小化することである。
論文 参考訳（メタデータ） (2023-07-24T16:36:04Z) - Versatile Dueling Bandits: Best-of-both-World Analyses for Online
Learning from Preferences [28.79598714109439]
両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。
まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。
提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
論文 参考訳（メタデータ） (2022-02-14T13:37:23Z) - Stochastic Contextual Dueling Bandits under Linear Stochastic
Transitivity Models [25.336599480692122]
我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。
本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。
本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
論文 参考訳（メタデータ） (2022-02-09T17:44:19Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Multinomial Logit Contextual Bandits: Provable Optimality and
Practicality [15.533842336139063]
パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。
本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。
本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
論文 参考訳（メタデータ） (2021-03-25T15:42:25Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。