論文の概要: Optimal and Adaptive Non-Stationary Dueling Bandits Under a Generalized Borda Criterion
- arxiv url: http://arxiv.org/abs/2403.12950v1
- Date: Tue, 19 Mar 2024 17:50:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 13:04:26.687510
- Title: Optimal and Adaptive Non-Stationary Dueling Bandits Under a Generalized Borda Criterion
- Title(参考訳): 一般化ボルダ条件下での最適かつ適応的な非定常ダウリングバンド
- Authors: Joe Suk, Arpit Agarwal,
- Abstract要約: デュエル・バンディットでは、学習者は腕間の好みのフィードバックを受け取り、腕の後悔は勝者アームに対する過度な最適化によって定義される。
本研究では,最初の最適で適応的なボルダ動的後悔の上界を確立する。
驚くべきことに、非定常的なボルダデュエルバンディットに対する我々の技術は、コンドルセットの勝者設定内でも改善される。
- 参考スコア(独自算出の注目度): 11.770902693413401
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In dueling bandits, the learner receives preference feedback between arms, and the regret of an arm is defined in terms of its suboptimality to a winner arm. The more challenging and practically motivated non-stationary variant of dueling bandits, where preferences change over time, has been the focus of several recent works (Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023). The goal is to design algorithms without foreknowledge of the amount of change. The bulk of known results here studies the Condorcet winner setting, where an arm preferred over any other exists at all times. Yet, such a winner may not exist and, to contrast, the Borda version of this problem (which is always well-defined) has received little attention. In this work, we establish the first optimal and adaptive Borda dynamic regret upper bound, which highlights fundamental differences in the learnability of severe non-stationarity between Condorcet vs. Borda regret objectives in dueling bandits. Surprisingly, our techniques for non-stationary Borda dueling bandits also yield improved rates within the Condorcet winner setting, and reveal new preference models where tighter notions of non-stationarity are adaptively learnable. This is accomplished through a novel generalized Borda score framework which unites the Borda and Condorcet problems, thus allowing reduction of Condorcet regret to a Borda-like task. Such a generalization was not previously known and is likely to be of independent interest.
- Abstract(参考訳): デュエル・バンディットでは、学習者は腕間の好みのフィードバックを受け取り、腕の後悔は勝者アームに対する過度な最適化によって定義される。
より困難で実質的に動機づけられたデュエル・バンディットの非定常的な変種は、時代とともに好みが変わるが、近年のいくつかの作品(Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023)の焦点となっている。
目標は、変更の量を知ることなく、アルゴリズムを設計することだ。
ここでは、多くの既知の結果がコンドルチェットの勝者設定を研究しており、どの腕よりも好まれる腕は常に存在する。
しかし、そのような勝者は存在せず、対照的に、この問題のボルダ版(常によく定義されている)はほとんど注目されていない。
本研究では,コンドルチェットとボルダの過度な非定常性の学習性に基礎的な差異を生じさせる,最初の最適かつ適応的なボルダ動的後悔上限を確立する。
意外なことに、非定常なボルダデュエルブレイトに対する我々の手法は、コンドルセットの勝者設定における改善率をもたらし、非定常性のより厳密な概念が適応的に学習可能な新しい選好モデルを明らかにする。
これは、ボルダとコンドルチェの問題を統一する新しい一般化されたボルダスコアフレームワークによって達成され、これにより、ボルダのようなタスクに対するコンドルチェットの後悔を減らすことができる。
このような一般化は以前は知られておらず、独立した関心を持つ可能性が高い。
関連論文リスト
- Imprecise Multi-Armed Bandits [0.0]
そこで本研究では,各アームが,結果空間上の固定された未知の干潟と結びついている,新しいマルチアーム・バンディット・フレームワークを提案する。
次に、これらのクレダル集合によって定義される下述の前提に対応する後悔の概念を定義する。
論文 参考訳(メタデータ) (2024-05-09T10:58:40Z) - Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - Bandits Meet Mechanism Design to Combat Clickbait in Online
Recommendation [50.469872635246176]
我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。
このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
論文 参考訳(メタデータ) (2023-11-27T09:19:01Z) - Information-Gathering in Latent Bandits [79.6953033727455]
本稿では,潜伏バンドにおける情報収集手法を提案する。
我々は、各州に対するエージェントの信念から、最高の腕を選ぶことは、より高い後悔を引き起こすことを示した。
また,腕を慎重に選択することで,状態分布の推定精度が向上することを示した。
論文 参考訳(メタデータ) (2022-07-08T01:15:12Z) - Batched Dueling Bandits [13.69077222007053]
そこで本研究では,2つの標準設定条件下で,K$アームのデュエルバンディット問題について検討した。
バッチ数と後悔数のトレードオフを円滑に行うアルゴリズムを得る。
論文 参考訳(メタデータ) (2022-02-22T04:02:36Z) - 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) - Be Greedy in Multi-Armed Bandits [22.301793734117805]
グレディアルゴリズムは、各ラウンドで局所最適選択を行う、シーケンシャルな決定問題の最も単純なものである。
We provide a generic worst-case bound on the regret of the Greedy algorithm。
連続・無限・多武装バンディット問題において,ほぼ最適の最悪の後悔境界を検証できることを証明した。
論文 参考訳(メタデータ) (2021-01-04T16:47:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。