論文の概要: An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem

• arxiv url: http://arxiv.org/abs/2209.12108v1
• Date: Sun, 25 Sep 2022 00:23:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-27 14:45:44.793469
• Title: An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem
• Title（参考訳）: ダリング帯域問題に対する漸近的最適バッチアルゴリズム
• Authors: Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan
• Abstract要約: 従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。 我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。 実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
• 参考スコア（独自算出の注目度）: 13.69077222007053
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the $K$-armed dueling bandit problem, a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the $\textit{fully adaptive}$ setting, where the algorithm can make updates after every comparison. The "batched" dueling bandit problem is motivated by large-scale applications like web search ranking and recommendation systems, where performing sequential updates may be infeasible. In this work, we ask: $\textit{is there a solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for $K$-armed dueling bandits?}$ We answer this in the affirmative $\textit{under the Condorcet condition}$, a standard setting of the $K$-armed dueling bandit problem. We obtain asymptotic regret of $O(K^2\log^2(K)) + O(K\log(T))$ in $O(\log(T))$ rounds, where $T$ is the time horizon. Our regret bounds nearly match the best regret bounds known in the fully sequential setting under the Condorcet condition. Finally, in computational experiments over a variety of real-world datasets, we observe that our algorithm using $O(\log(T))$ rounds achieves almost the same performance as fully sequential algorithms (that use $T$ rounds).
• Abstract（参考訳）: 対数比較の形でフィードバックが得られる従来のマルチアーム付きバンディット問題の変種であるk$-armed dueling bandit問題について検討した。 従来の学習アルゴリズムは$\textit{fully Adaptive}$設定に重点を置いており、アルゴリズムは比較毎に更新を行うことができる。 は、web検索ランキングやレコメンデーションシステムのような大規模アプリケーションによって動機付けられており、シーケンシャルな更新の実行は不可能かもしれない。 この作業では、$\textit{?$k$-armed dueling banditsの最高のシーケンシャルアルゴリズムの漸近的な後悔の限界にマッチする、いくつかの適応ラウンドを使用するソリューションがありますか? これは、$K$の武装デュエルバンディット問題の標準設定である$\textit{under the Condorcet condition}$で答える。 asymptotic regret of $o(k^2\log^2(k)) + o(k\log(t))$ in $o(\log(t))$ rounds, ここで$t$は時間軸である。 私たちの後悔は、コンドルセット条件の下で完全に連続した設定で知られている最高の後悔の境界にほぼ一致する。 最後に、様々な実世界のデータセットに対する計算実験において、$o(\log(t))$ roundsを使用するアルゴリズムは、完全なシーケンシャルアルゴリズム($t$ roundsを使用する)とほとんど同じ性能を達成することを観察する。

関連論文リスト

• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• 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)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• No Regrets for Learning the Prior in Bandits [30.478188057004175]
  $tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。 $tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
  論文  参考訳（メタデータ） (2021-07-13T15:51:32Z)
• 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)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)
• Blocking Bandits [33.14975454724348]
  我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。 全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。 我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2019-07-27T20:42:01Z)

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

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