論文の概要: Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and
Ranking Application
- arxiv url: http://arxiv.org/abs/2307.14549v1
- Date: Thu, 27 Jul 2023 00:11:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-28 16:18:39.092062
- Title: Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and
Ranking Application
- Title(参考訳): 複数の遊びを伴う対向型睡眠バンディット問題:アルゴリズムとランキング応用
- Authors: Jianjun Yuan and Wei Lee Woon and Ludovik Coba
- Abstract要約: 本稿では,オンラインレコメンデーションシステムのコンテキストにおいて,複数のプレイの問題で睡眠帯域を効率的に解決するアルゴリズムを提案する。
提案アルゴリズムは、単腕選択のための睡眠帯域幅アルゴリズムを拡張し、$bigO(kN2sqrtTlog T)$で理論的性能を達成することを保証している。
- 参考スコア(独自算出の注目度): 7.0717496233701365
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper presents an efficient algorithm to solve the sleeping bandit with
multiple plays problem in the context of an online recommendation system. The
problem involves bounded, adversarial loss and unknown i.i.d. distributions for
arm availability. The proposed algorithm extends the sleeping bandit algorithm
for single arm selection and is guaranteed to achieve theoretical performance
with regret upper bounded by $\bigO(kN^2\sqrt{T\log T})$, where $k$ is the
number of arms selected per time step, $N$ is the total number of arms, and $T$
is the time horizon.
- Abstract(参考訳): 本稿では,オンラインレコメンデーションシステムにおいて,複数のプレイの問題で睡眠帯域を効率的に解決するアルゴリズムを提案する。
問題は、有界で対向的な損失と、腕の可用性のための未知のi.d.分布である。
提案アルゴリズムは、単腕選択のための睡眠帯域アルゴリズムを拡張し、$\bigO(kN^2\sqrt{T\log T})$の残差上限を持つ理論的性能を保証し、$k$は時間ステップ毎に選択されたアームの数、$N$は腕の総数、$T$は時間軸である。
関連論文リスト
- Contextual Bandits with Arm Request Costs and Delays [19.263086804406786]
本稿では,時間的遅延と関連するコストを伴って,新たなアームセットを要求できるコンテキスト的バンディット問題の拡張を提案する。
この設定では、学習者は、各選択が1つの時間単位を取るように、決定セットから複数のアームを選択することができる。
我々は、武器を効果的に選択し、新しい武器を要求する適切な時間を決定するアルゴリズムを設計し、彼らの後悔を最小限に抑える。
論文 参考訳(メタデータ) (2024-10-17T00:44:50Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳(メタデータ) (2024-09-08T12:19:12Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - An Asymptotically Optimal Batched Algorithm for the Dueling Bandit
Problem [13.69077222007053]
従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。
我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。
実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
論文 参考訳(メタデータ) (2022-09-25T00:23:55Z) - 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) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳(メタデータ) (2021-02-15T19:10:52Z) - 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) - DART: aDaptive Accept RejecT for non-linear top-K subset identification [34.68931784199599]
我々は、各ステップでN$アームからK$を選択するという盗賊問題を考える。
本稿では,各アームのフィードバックや報酬関数の線形性を必要としない新しいアルゴリズムを提案する。
我々のアルゴリズムであるaDaptive Accept RejecT (DART)は、良好な腕を逐次見つけ、信頼境界に基づいて悪い腕を除去する。
論文 参考訳(メタデータ) (2020-11-16T02:10:06Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。