論文の概要: When Can We Track Significant Preference Shifts in Dueling Bandits?
- arxiv url: http://arxiv.org/abs/2302.06595v1
- Date: Mon, 13 Feb 2023 18:49:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 14:16:32.894742
- Title: When Can We Track Significant Preference Shifts in Dueling Bandits?
- Title(参考訳): デュエルバンドにおける有意な選好変化をいつ追跡できるのか?
- Authors: Joe Suk and Arpit Agarwal
- Abstract要約: 本稿では,最近の重要なシフトの概念(Suk and Kpotufe, 2022)を考察し,$O(sqrtKtildeLT)$ dynamic regretを用いて,デュエル問題に対する適応アルゴリズムを設計できるかどうかを問う。
まず、よく研究されたCondorcetとSSTの好み分布のクラスの下で、$O(sqrtKtildeLT)$ dynamic regretで任意のアルゴリズムを制御できない結果を与える。
- 参考スコア(独自算出の注目度): 8.490310884703458
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The $K$-armed dueling bandits problem, where the feedback is in the form of
noisy pairwise preferences, has been widely studied due its applications in
information retrieval, recommendation systems, etc. Motivated by concerns that
user preferences/tastes can evolve over time, we consider the problem of
dueling bandits with distribution shifts. Specifically, we study the recent
notion of significant shifts (Suk and Kpotufe, 2022), and ask whether one can
design an adaptive algorithm for the dueling problem with
$O(\sqrt{K\tilde{L}T})$ dynamic regret, where $\tilde{L}$ is the (unknown)
number of significant shifts in preferences. We show that the answer to this
question depends on the properties of underlying preference distributions.
Firstly, we give an impossibility result that rules out any algorithm with
$O(\sqrt{K\tilde{L}T})$ dynamic regret under the well-studied Condorcet and SST
classes of preference distributions. Secondly, we show that $\text{SST} \cap
\text{STI}$ is the largest amongst popular classes of preference distributions
where it is possible to design such an algorithm. Overall, our results provides
an almost complete resolution of the above question for the hierarchy of
distribution classes.
- Abstract(参考訳): k$-armed dueling bandits問題(英語版)は、フィードバックがうるさいペアワイズ選好の形式であり、情報検索やレコメンデーションシステムなどに応用されているため、広く研究されている。
ユーザの好みや味が時間とともに進化するのではないかという懸念から,分布シフトに伴う帯域幅の重複の問題を考える。
具体的には、最近の有意なシフトの概念(Suk and Kpotufe, 2022)を考察し、$O(\sqrt{K\tilde{L}T})$ dynamic regret, ここで$\tilde{L}$は(未知の)好みの重要なシフトの数である。
この質問に対する答えは、基礎となる選好分布の性質に依存することを示す。
まず、よく研究されたCondorcetとSSTの選好分布のクラスの下で、$O(\sqrt{K\tilde{L}T})$ dynamic regret で任意のアルゴリズムを規定する不可能な結果を与える。
第二に、$\text{SST} \cap \text{STI}$は、そのようなアルゴリズムを設計することが可能な、選好分布の一般的なクラスの中で最大であることを示す。
全体として、我々の結果は、分布クラス階層に対する上記の問題に対するほぼ完全な解決を提供する。
関連論文リスト
- 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) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳(メタデータ) (2022-11-28T08:40:12Z) - Modeling Attrition in Recommender Systems with Departing Bandits [84.85560764274399]
政策に依存した地平線を捉えた新しいマルチアームバンディット構成を提案する。
まず、全てのユーザが同じタイプを共有しているケースに対処し、最近の UCB ベースのアルゴリズムが最適であることを実証する。
次に、ユーザが2つのタイプに分けられる、より困難なケースを前進させます。
論文 参考訳(メタデータ) (2022-03-25T02:30:54Z) - Stochastic Contextual Dueling Bandits under Linear Stochastic
Transitivity Models [25.336599480692122]
我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。
本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。
本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
論文 参考訳(メタデータ) (2022-02-09T17:44:19Z) - Tracking Most Severe Arm Changes in Bandits [12.29762518277676]
我々は、$tildeO(sqrtT)ll tildeO(sqrtLT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll
論文 参考訳(メタデータ) (2021-12-27T18:59:05Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-20T04:29:18Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳(メタデータ) (2020-10-27T19:09:08Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-20T06:36:19Z) - Improved Optimistic Algorithms for Logistic Bandits [16.140301473601454]
そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。
我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
論文 参考訳(メタデータ) (2020-02-18T12:52:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。