論文の概要: Non-Stationary Dueling Bandits Under a Weighted Borda Criterion
- arxiv url: http://arxiv.org/abs/2403.12950v2
- Date: Sat, 28 Sep 2024 15:05:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-01 22:01:26.160766
- Title: Non-Stationary Dueling Bandits Under a Weighted Borda Criterion
- Title(参考訳): 太いボルダ条件下での非定常デュエルバンド
- Authors: Joe Suk, Arpit Agarwal,
- Abstract要約: 本稿では,BordaとCondorcetの両問題を一般化した新しい$textitweighted Borda score$ frameworkを紹介する。
また、ボルダ問題とコンドルセット問題の両方を一般化する新しい$textitweighted Borda score$ frameworkを導入する。
- 参考スコア(独自算出の注目度): 11.770902693413401
- License:
- Abstract: In $K$-armed dueling bandits, the learner receives preference feedback between arms, and the regret of an arm is defined in terms of its suboptimality to a $\textit{winner}$ arm. The $\textit{non-stationary}$ variant of the problem, motivated by concerns of changing user preferences, has received recent interest (Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023). The goal here is to design algorithms with low {\em dynamic regret}, ideally without foreknowledge of the amount of change. The notion of regret here is tied to a notion of winner arm, most typically taken to be a so-called Condorcet winner or a Borda winner. However, the aforementioned results mostly focus on the Condorcet winner. In comparison, the Borda version of this problem has received less attention which is the focus of this work. We establish the first optimal and adaptive dynamic regret upper bound $\tilde{O}(\tilde{L}^{1/3} K^{1/3} T^{2/3} )$, where $\tilde{L}$ is the unknown number of significant Borda winner switches. We also introduce a novel $\textit{weighted Borda score}$ framework which generalizes both the Borda and Condorcet problems. This framework surprisingly allows a Borda-style regret analysis of the Condorcet problem and establishes improved bounds over the theoretical state-of-art in regimes with a large number of arms or many spurious changes in Condorcet winner. Such a generalization was not known and could be of independent interest.
- Abstract(参考訳): K$の武器を持つデュエルバンドでは、学習者はアーム間の好みのフィードバックを受け取り、アームの後悔は$\textit{winner}$のアームに最適化される。
この問題の$\textit{non-stationary}$ variantは、ユーザの好みを変えるという懸念から動機付けられ、近年の関心を集めている(Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023)。
ここでのゴールは、変化の量を知ることなく理想的に、低レベルの動的後悔を伴うアルゴリズムを設計することである。
ここでの後悔の概念は勝者の腕の概念と結びついており、典型的にはコンドルチェットの勝者かボルダの勝者と呼ばれる。
しかし、上記の結果はCondorcetの勝者に主に焦点が当てられている。
対照的に、この問題のボルダ版は、この研究の焦点である注意を減らしている。
最初に最適で適応的な動的後悔の上界 $\tilde{O}(\tilde{L}^{1/3} K^{1/3} T^{2/3} )$ を確立する。
また、ボルダ問題とコンドルセット問題の両方を一般化する新しい$\textit{weighted Borda score}$ frameworkを導入する。
この枠組みは、驚くほどにボルダ式のコンドルセット問題を後悔して分析することができ、多数の腕を持つ体制や多くのコンドルセット勝者の急激な変化を持つ体制において、理論上の最先端性に対する改善された境界を確立する。
そのような一般化は知られておらず、独立した関心を持つことができた。
関連論文リスト
- Neural Dueling Bandits [58.90189511247936]
ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。
次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
論文 参考訳(メタデータ) (2024-07-24T09:23:22Z) - Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals [28.94461817548213]
条件付き良性環境と任意の環境下での学習性能におけるトレードオフの可能性について,上界と下界の整合性を証明した。
この問題を線形バンディット設定に還元することで、最初に因果バンディットのインスタンス依存境界を求める。
論文 参考訳(メタデータ) (2024-07-01T04:12:15Z) - Multi-Player Approaches for Dueling Bandits [58.442742345319225]
Follow Your Leaderのブラックボックスアプローチの直接的な使用は、この設定の低いバウンダリと一致することを示す。
また,Condorcet-Winnerレコメンデーションプロトコルを用いて,メッセージパッシングによる完全分散アプローチも分析する。
論文 参考訳(メタデータ) (2024-05-25T10:25:48Z) - Imprecise Multi-Armed Bandits [0.0]
そこで本研究では,各アームが,結果空間上の固定された未知の干潟と結びついている,新しいマルチアーム・バンディット・フレームワークを提案する。
次に、これらのクレダル集合によって定義される下述の前提に対応する後悔の概念を定義する。
論文 参考訳(メタデータ) (2024-05-09T10:58:40Z) - Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility [12.05174711411919]
両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。
まず,1対1設定のための既存のアルゴリズムをこのより一般的な設定に拡張し,プレイヤー最適後悔に対するほぼ最適境界を実現することを示す。
本稿では,アダプティブ・サーベイ・then-deferred (AETDA) アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-01-03T03:45:35Z) - Information-Gathering in Latent Bandits [79.6953033727455]
本稿では,潜伏バンドにおける情報収集手法を提案する。
我々は、各州に対するエージェントの信念から、最高の腕を選ぶことは、より高い後悔を引き起こすことを示した。
また,腕を慎重に選択することで,状態分布の推定精度が向上することを示した。
論文 参考訳(メタデータ) (2022-07-08T01:15:12Z) - 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) - Bridging Adversarial and Nonstationary Multi-armed Bandit [10.3206415401832]
2つの定式化は、典型的には時間変化の報酬分布を扱うために用いられる: 逆の帯域幅と非定常帯域幅である。
この2つを特別なケースとしてスムーズにブリッジする統一的な定式化を提供する。
一致した下界で最適な後悔を達成するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-01-05T14:18:14Z) - Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳(メタデータ) (2020-06-22T16:06:25Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-23T19:52:44Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳(メタデータ) (2020-02-13T08:53:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。