Fugu-MT 論文翻訳(概要): Non-Stationary Dueling Bandits

論文の概要: Non-Stationary Dueling Bandits

arxiv url: http://arxiv.org/abs/2202.00935v1
Date: Wed, 2 Feb 2022 09:57:35 GMT
ステータス: 処理完了
システム内更新日: 2022-02-03 13:47:28.613145
Title: Non-Stationary Dueling Bandits
Title（参考訳）: 非定常デュエルバンド
Authors: Patrick Kolpaczki, Viktor Bengs, Eyke H\"ullermeier
Abstract要約: 我々は、非定常デュエルバンディット問題をK$アームで研究し、タイムホライズメント$T$は、固定セグメント$M$からなる。蓄積した後悔を最小限に抑えるため、学習者は各定常セグメントのコンドルチェットの勝者をできるだけ頻繁に選ぶ必要がある。我々は、M$やT$の知識を必要とせず、非定常ケースに対する後悔の意を示す。
参考スコア（独自算出の注目度）: 8.298716599039501
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the non-stationary dueling bandits problem with $K$ arms, where the time horizon $T$ consists of $M$ stationary segments, each of which is associated with its own preference matrix. The learner repeatedly selects a pair of arms and observes a binary preference between them as feedback. To minimize the accumulated regret, the learner needs to pick the Condorcet winner of each stationary segment as often as possible, despite preference matrices and segment lengths being unknown. We propose the $\mathrm{Beat\, the\, Winner\, Reset}$ algorithm and prove a bound on its expected binary weak regret in the stationary case, which tightens the bound of current state-of-art algorithms. We also show a regret bound for the non-stationary case, without requiring knowledge of $M$ or $T$. We further propose and analyze two meta-algorithms, $\mathrm{DETECT}$ for weak regret and $\mathrm{Monitored\, Dueling\, Bandits}$ for strong regret, both based on a detection-window approach that can incorporate any dueling bandit algorithm as a black-box algorithm. Finally, we prove a worst-case lower bound for expected weak regret in the non-stationary case.
Abstract（参考訳）: 我々は,非定常的決闘バンドイット問題をk$ armsで検討し,時間軸$t$ は,それぞれが独自の選好行列と関連づけられる固定セグメントから成り立っている。学習者は1対の腕を繰り返し選択し、それら間の二元選好をフィードバックとして観察する。蓄積した後悔を最小限に抑えるため、学習者は好みの行列やセグメントの長さが不明であるにもかかわらず、各定常セグメントのコンドルチェット勝者をできるだけ頻繁に選択する必要がある。我々は,現在最先端のアルゴリズムの限界を狭めるような定常の場合において,期待される2進不備の限界を証明し,$\mathrm{Beat\,the\,Winner\,Reset}$アルゴリズムを提案する。我々はまた、M$やT$の知識を必要とせずに、非定常ケースに対する後悔の意を示す。さらに,弱後悔のための$\mathrm{detect}$と強後悔のための$\mathrm{monitored\, dueling\, bandits}$という2つのメタアルゴリズムを提案し分析した。最後に,非定常の場合において,予想される弱い後悔に対して最悪のケースが低いことを証明した。

関連論文リスト

Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
本稿では,敵攻撃に対して頑健なマルチアームバンディットアルゴリズムについて検討する。我々は、攻撃予算の知識の有無に関わらず、このモデルの2つのケースを調査する。我々は、加法的あるいは乗法的な$C$依存項を持つ後悔境界を持つ2種類のアルゴリズムを考案する。
論文参考訳（メタデータ） (2024-08-16T17:41:35Z)
Adversarial Multi-dueling Bandits [0.4467766778351321]
対戦型多段バンディットにおける後悔の問題について紹介する。このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
論文参考訳（メタデータ） (2024-06-18T10:28:12Z)
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)
Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文参考訳（メタデータ） (2023-03-15T17:59:27Z)
Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文参考訳（メタデータ） (2022-05-26T15:55:44Z)
Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms [30.024167992890916]
そこで本研究では,学習者が200ドル(約1万2000円)の帯域幅のタスクに直面する決定について検討する。敵は各タスクの最適なアームを、M$アームのより小さな(しかし未知の)サブセットで選択することを制約される。境界は既知のもの(非定常的メタラーニング設定)、あるいは未知のもの(非定常的バンディット設定)である。
論文参考訳（メタデータ） (2022-02-25T22:28:01Z)
Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文参考訳（メタデータ） (2022-02-12T21:55:44Z)
A Regret bound for Non-stationary Multi-Armed Bandits with Fairness Constraints [7.716156977428555]
我々は,緩やかに変化する$k$-armed bandit問題を解くために,fair upper confidenceと呼ばれる新しいアルゴリズムとexploring fair-ucbeを提案する。非定常ケースにおけるアルゴリズムの性能は,その定常ケースに近づくとゼロになりがちであることを示す。
論文参考訳（メタデータ） (2020-12-24T18:12:01Z)
Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文参考訳（メタデータ） (2020-10-27T19:09:08Z)
Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-17T22:32:19Z)
Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-02-20T06:36:19Z)

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

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