論文の概要: 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)の焦点となっている。 目標は、変更の量を知ることなく、アルゴリズムを設計することだ。 ここでは、多くの既知の結果がコンドルチェットの勝者設定を研究しており、どの腕よりも好まれる腕は常に存在する。 しかし、そのような勝者は存在せず、対照的に、この問題のボルダ版(常によく定義されている)はほとんど注目されていない。 本研究では,コンドルチェットとボルダの過度な非定常性の学習性に基礎的な差異を生じさせる,最初の最適かつ適応的なボルダ動的後悔上限を確立する。 意外なことに、非定常なボルダデュエルブレイトに対する我々の手法は、コンドルセットの勝者設定における改善率をもたらし、非定常性のより厳密な概念が適応的に学習可能な新しい選好モデルを明らかにする。 これは、ボルダとコンドルチェの問題を統一する新しい一般化されたボルダスコアフレームワークによって達成され、これにより、ボルダのようなタスクに対するコンドルチェットの後悔を減らすことができる。 このような一般化は以前は知られておらず、独立した関心を持つ可能性が高い。

関連論文リスト

• Adversarial Multi-dueling Bandits [0.4467766778351321]
  対戦型多段バンディットにおける後悔の問題について紹介する。 このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
  論文  参考訳（メタデータ） (2024-06-18T10:28:12Z)
• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation [50.469872635246176]
  我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。 このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
  論文  参考訳（メタデータ） (2023-11-27T09:19:01Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• The price of unfairness in linear bandits with biased feedback [62.25313751895011]
  線形帯域フィードバックによる逐次意思決定の問題点について検討する。 その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。 興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
  論文  参考訳（メタデータ） (2022-03-18T08:03:20Z)
• Bandit problems with fidelity rewards [7.154621689269006]
  フィデリティ・バンディット問題(英: fidelity bandits problem)とは、過去にプレイヤーがその腕に「ロヤル」したかによって、各腕の報酬がフィデリティ・報酬によって増強されるK$アームのバンディット問題の変種である。 忠誠ポイントモデルでは、余分な報酬の量は、これまで腕が演奏された回数に依存する。 サブスクリプションモデルでは、追加の報酬は腕の連続的な引き分けの数に依存する。
  論文  参考訳（メタデータ） (2021-11-25T11:09:43Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。