論文の概要: Dueling Bandits with Adversarial Sleeping
- arxiv url: http://arxiv.org/abs/2107.02274v1
- Date: Mon, 5 Jul 2021 21:14:04 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-08 06:40:57.287214
- Title: Dueling Bandits with Adversarial Sleeping
- Title(参考訳): 逆行性睡眠を伴うデュエルバンド
- Authors: Aadirupa Saha, Pierre Gaillard
- Abstract要約: 好みと敵意の相反するバンドレットを睡眠させるという問題を紹介した。
目標は、各ラウンドで最高のアイテムを識別できる最適なノンレグレットポリシーを見つけることです。
- 参考スコア(独自算出の注目度): 26.308541799686505
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce the problem of sleeping dueling bandits with stochastic
preferences and adversarial availabilities (DB-SPAA). In almost all dueling
bandit applications, the decision space often changes over time; eg, retail
store management, online shopping, restaurant recommendation, search engine
optimization, etc. Surprisingly, this `sleeping aspect' of dueling bandits has
never been studied in the literature. Like dueling bandits, the goal is to
compete with the best arm by sequentially querying the preference feedback of
item pairs. The non-triviality however results due to the non-stationary item
spaces that allow any arbitrary subsets items to go unavailable every round.
The goal is to find an optimal `no-regret' policy that can identify the best
available item at each round, as opposed to the standard `fixed best-arm regret
objective' of dueling bandits. We first derive an instance-specific lower bound
for DB-SPAA $\Omega( \sum_{i =1}^{K-1}\sum_{j=i+1}^K \frac{\log
T}{\Delta(i,j)})$, where $K$ is the number of items and $\Delta(i,j)$ is the
gap between items $i$ and $j$. This indicates that the sleeping problem with
preference feedback is inherently more difficult than that for classical
multi-armed bandits (MAB). We then propose two algorithms, with near optimal
regret guarantees. Our results are corroborated empirically.
- Abstract(参考訳): 本稿では,確率的嗜好とDB-SPAA (Adversarial Availability) による睡眠デュエルバンドの問題点を紹介する。
例えば、小売店の管理、オンラインショッピング、レストランのレコメンデーション、検索エンジンの最適化などだ。
驚くべきことに、このデュエル・バンディットの「眠る側面」は文献で研究されていない。
デュエルバンドと同様に、ゴールはアイテムペアの好みのフィードバックを逐次クエリすることで、ベストアームと競合することである。
しかし、非自明性は任意の部分集合アイテムをラウンド毎に利用できないような非定常アイテム空間によって生じる。
目標は、各ラウンドで最高のアイテムを識別できる最適な"no-regret"ポリシーを見つけることであり、デュエルのバンドの標準的な"fixed best-arm regret objective"とは対照的である。
まず、DB-SPAA $\Omega( \sum_{i = 1}^{K-1}\sum_{j=i+1}^K \frac{\log T}{\Delta(i,j)})$に対してインスタンス固有の下限を導出します。
これは、従来のマルチアームバンディット(MAB)よりも、好みフィードバックによる睡眠問題は本質的に困難であることを示している。
次に,最善の後悔を保証できる2つのアルゴリズムを提案する。
我々の結果は実証的に裏付けられている。
関連論文リスト
- Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and
Ranking Application [7.0717496233701365]
本稿では,オンラインレコメンデーションシステムのコンテキストにおいて,複数のプレイの問題で睡眠帯域を効率的に解決するアルゴリズムを提案する。
提案アルゴリズムは、単腕選択のための睡眠帯域幅アルゴリズムを拡張し、$bigO(kN2sqrtTlog T)$で理論的性能を達成することを保証している。
論文 参考訳(メタデータ) (2023-07-27T00:11:59Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Dueling Bandits: From Two-dueling to Multi-dueling [40.4378338001229]
エージェントが複数の選択肢を同時に比較し、最適な腕を選択することで後悔を最小限に抑える、一般的なマルチダウリングバンディット問題について検討する。
この設定は従来の二段バンディット問題を一般化し、複数の選択肢に対する主観的なフィードバックを含む現実世界の多くのアプリケーションを見つける。
論文 参考訳(メタデータ) (2022-11-16T22:00:54Z) - 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) - 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) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳(メタデータ) (2020-10-27T19:09:08Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z) - Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial
Rewards [59.559028338399855]
我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。
本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-14T00:41:26Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。