論文の概要: Borda Regret Minimization for Generalized Linear Dueling Bandits

• arxiv url: http://arxiv.org/abs/2303.08816v2
• Date: Mon, 25 Sep 2023 18:01:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-27 18:05:42.612046
• Title: Borda Regret Minimization for Generalized Linear Dueling Bandits
• Title（参考訳）: 一般化線形デュリングバンディットに対するボルダ後悔最小化
• Authors: Yue Wu and Tao Jin and Hao Lou and Farzad Farnoud and Quanquan Gu
• Abstract要約: 本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
• 参考スコア（独自算出の注目度）: 65.09919504862496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dueling bandits are widely used to model preferential feedback prevalent in many applications such as recommendation systems and ranking. In this paper, we study the Borda regret minimization problem for dueling bandits, which aims to identify the item with the highest Borda score while minimizing the cumulative regret. We propose a rich class of generalized linear dueling bandit models, which cover many existing models. We first prove a regret lower bound of order $\Omega(d^{2/3} T^{2/3})$ for the Borda regret minimization problem, where $d$ is the dimension of contextual vectors and $T$ is the time horizon. To attain this lower bound, we propose an explore-then-commit type algorithm for the stochastic setting, which has a nearly matching regret upper bound $\tilde{O}(d^{2/3} T^{2/3})$. We also propose an EXP3-type algorithm for the adversarial linear setting, where the underlying model parameter can change at each round. Our algorithm achieves an $\tilde{O}(d^{2/3} T^{2/3})$ regret, which is also optimal. Empirical evaluations on both synthetic data and a simulated real-world environment are conducted to corroborate our theoretical analysis.
• Abstract（参考訳）: デュエルバンディットは、レコメンデーションシステムやランキングなど、多くのアプリケーションで一般的な優先的なフィードバックをモデル化するために広く使用されている。 本稿では,ボルダの残忍度を最小化しつつ,最も高いボルダスコアの項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 まず、ボルダの後悔最小化問題に対して、次数$\Omega(d^{2/3} T^{2/3})$の後悔の低い境界を証明し、$d$は文脈ベクトルの次元、$T$は時間地平線である。 この下限を達成するために、確率的設定のためのexplore-then-commit型アルゴリズムを提案し、ほぼ一致する上限$\tilde{o}(d^{2/3} t^{2/3})$を持つ。 また,各ラウンド毎にモデルパラメータを変更可能な逆線形設定のためのEXP3型アルゴリズムを提案する。 我々のアルゴリズムは、$\tilde{O}(d^{2/3} T^{2/3})$ regretを達成し、これも最適である。 合成データとシミュレーション実環境の両方に関する実証的な評価を行い, 理論的解析を裏付ける。

関連論文リスト

• Adversarial Multi-dueling Bandits [0.4467766778351321]
  対戦型多段バンディットにおける後悔の問題について紹介する。 このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
  論文  参考訳（メタデータ） (2024-06-18T10:28:12Z)
• Linear bandits with polylogarithmic minimax regret [8.97780713904412]
  本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。 我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
  論文  参考訳（メタデータ） (2024-02-19T10:56:47Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• 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)
• Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game [9.933208900617174]
  我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。 NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。 モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-03-11T13:45:42Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
  低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。 低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-04T15:30:14Z)

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

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