論文の概要: A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays
- arxiv url: http://arxiv.org/abs/2308.10675v2
- Date: Mon, 27 May 2024 19:30:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-30 04:36:37.221729
- Title: A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays
- Title（参考訳）: 過度遅延に対するロバスト性を有する遅延フィードバックをもつ帯域幅に対するBest-of-both-worldsアルゴリズム
- Authors: Saeed Masoudian, Julian Zimmert, Yevgeny Seldin,
- Abstract要約: 本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。
我々のアルゴリズムは任意の過剰な遅延を許容し、$T$をオーダーすることができる。
- 参考スコア（独自算出の注目度）: 24.998122268199797
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new best-of-both-worlds algorithm for bandits with variably delayed feedback. In contrast to prior work, which required prior knowledge of the maximal delay $d_{\mathrm{max}}$ and had a linear dependence of the regret on it, our algorithm can tolerate arbitrary excessive delays up to order $T$ (where $T$ is the time horizon). The algorithm is based on three technical innovations, which may all be of independent interest: (1) We introduce the first implicit exploration scheme that works in best-of-both-worlds setting. (2) We introduce the first control of distribution drift that does not rely on boundedness of delays. The control is based on the implicit exploration scheme and adaptive skipping of observations with excessive delays. (3) We introduce a procedure relating standard regret with drifted regret that does not rely on boundedness of delays. At the conceptual level, we demonstrate that complexity of best-of-both-worlds bandits with delayed feedback is characterized by the amount of information missing at the time of decision making (measured by the number of outstanding observations) rather than the time that the information is missing (measured by the delays).
- Abstract（参考訳）: 本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。
事前の作業とは対照的に、最大遅延$d_{\mathrm{max}}$の事前知識が必要であり、後悔の線形依存性があったため、我々のアルゴリズムは任意の過剰遅延を許容して$T$(ここでは$T$は時間水平線である)をオーダーすることができる。
アルゴリズムは3つの技術革新に基づいており、それらはすべて独立した関心を持つかもしれない: 1) 世界の最高の環境で機能する最初の暗黙の探究スキームを導入する。
2) 遅延の有界性に依存しない分布ドリフトの第一制御を導入する。
この制御は、暗黙の探索スキームと過度な遅延を伴う観測の適応的なスキップに基づいている。
(3) 遅れの有界性に依存しない, ゆるやかな後悔を伴う標準後悔に関する手続きを導入する。
概念レベルでは、情報の欠落(遅延による測定)よりも、意思決定時に欠落する情報量(見事な観測回数によって測定される)が特徴的である。
関連論文リスト
- Biased Dueling Bandits with Stochastic Delayed Feedback [6.167074802065416]
遅延を伴う状況に対処するアルゴリズムを2つ提案する。
完全遅延分布情報を必要とする第1のアルゴリズムは,遅延のない場合の遅延帯域問題に対する最適後悔境界を達成できる。
第2のアルゴリズムは、分布が不明な状況に最適化されるが、遅延の期待値のみが利用可能である。
論文 参考訳（メタデータ） (2024-08-26T19:49:12Z) - Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文 参考訳（メタデータ） (2024-02-14T13:08:26Z) - Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit
Feedback [39.12903814606534]
本稿では,過度な(期待している)報酬と全帯域遅延フィードバックを伴うマルチアームバンドの問題について検討する。
遅延したフィードバックは過去のアクションからの報酬のコンポーネントで構成されており、サブコンポーネント間で未知の分割がある。
提案アルゴリズムは,合成匿名フィードバックの遅延により,他の全帯域アプローチより優れていることを示す。
論文 参考訳（メタデータ） (2023-03-23T18:38:33Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - Delayed Feedback in Generalised Linear Bandits Revisited [5.349852254138085]
一般化線形包帯における遅延報酬の現象を理論的に研究する。
遅延フィードバックに対する楽観的なアルゴリズムの自然な適応は、遅延に対するペナルティが地平線から独立であるような後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2022-07-21T23:35:01Z) - Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When
Partial Feedback Counts [53.579515853222986]
時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。
この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。
本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:56:59Z) - Nonstochastic Bandits and Experts with Arm-Dependent Delays [17.272515865592542]
遅延が時間と腕に依存するような遅延環境で,非確率的な盗賊や専門家について検討する。
私たちの分析では、ドリフトに縛られた小説にヒンジを付け、1ラウンドのルックアヘッドを与えられた場合、アルゴリズムがどれだけの精度で実行できるかを測定しました。
論文 参考訳（メタデータ） (2021-11-02T13:36:11Z) - Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions [54.25616645675032]
アルゴリズムが受信したフィードバックにランダムな遅延を伴うマルチアーマッド・バンドイット(MAB)問題について検討する。
報酬非依存の遅延設定は、報酬非依存の遅延設定と、報酬非依存の遅延設定に依存する可能性がある。
私たちの主な貢献は、それぞれの設定でほぼ最適に後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2021-06-04T12:26:06Z) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳（メタデータ） (2020-10-12T20:53:52Z) - Stochastic bandits with arm-dependent delays [102.63128271054741]
我々は、単純なUCBベースのアルゴリズムであるPatentBanditsを提案する。
問題に依存しない境界も問題に依存しない境界も、性能の低い境界も提供します。
論文 参考訳（メタデータ） (2020-06-18T12:13:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。