論文の概要: Delayed Feedback in Generalised Linear Bandits Revisited
- arxiv url: http://arxiv.org/abs/2207.10786v3
- Date: Thu, 6 Apr 2023 14:05:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 18:13:24.214752
- Title: Delayed Feedback in Generalised Linear Bandits Revisited
- Title(参考訳): 一般化線形バンディットの再訪における遅延フィードバック
- Authors: Benjamin Howson, Ciara Pike-Burke, Sarah Filippi
- Abstract要約: 一般化線形包帯における遅延報酬の現象を理論的に研究する。
遅延フィードバックに対する楽観的なアルゴリズムの自然な適応は、遅延に対するペナルティが地平線から独立であるような後悔境界を達成することを示す。
- 参考スコア(独自算出の注目度): 5.349852254138085
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The stochastic generalised linear bandit is a well-understood model for
sequential decision-making problems, with many algorithms achieving
near-optimal regret guarantees under immediate feedback. However, the stringent
requirement for immediate rewards is unmet in many real-world applications
where the reward is almost always delayed. We study the phenomenon of delayed
rewards in generalised linear bandits in a theoretical manner. We show that a
natural adaptation of an optimistic algorithm to the delayed feedback achieves
a regret bound where the penalty for the delays is independent of the horizon.
This result significantly improves upon existing work, where the best known
regret bound has the delay penalty increasing with the horizon. We verify our
theoretical results through experiments on simulated data.
- Abstract(参考訳): 確率的一般化線形帯域は、逐次決定問題に対するよく理解されたモデルであり、多くのアルゴリズムは即時フィードバックの下でほぼ最適の後悔を保証する。
しかし、即時報酬の厳格な要求は、報酬がほとんど常に遅れている多くの現実世界のアプリケーションでは未完成である。
一般化線形バンディットにおける遅延報酬現象を理論的に検討した。
遅延フィードバックに対する楽観的なアルゴリズムの自然な適応は、遅延に対するペナルティが地平線から独立であるような後悔境界を達成することを示す。
この結果は、最もよく知られた後悔境界が地平線にしたがって遅延ペナルティが増大する既存の作業を大幅に改善する。
シミュレーションデータを用いた実験により理論的結果を検証する。
関連論文リスト
- Biased Dueling Bandits with Stochastic Delayed Feedback [6.167074802065416]
遅延を伴う状況に対処するアルゴリズムを2つ提案する。
完全遅延分布情報を必要とする第1のアルゴリズムは,遅延のない場合の遅延帯域問題に対する最適後悔境界を達成できる。
第2のアルゴリズムは、分布が不明な状況に最適化されるが、遅延の期待値のみが利用可能である。
論文 参考訳(メタデータ) (2024-08-26T19:49:12Z) - Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays [25.757803459592104]
本研究では,有益性制約下での非制限フィードバック遅延を用いた半帯域問題について検討する。
これはクラウドソーシングやオンライン広告などのアプリケーションによって動機付けられており、即時フィードバックはすぐには利用できない。
我々は,その利点に基づいて,制限のないフィードバック遅延の下で腕を選択するための新しいバンディットアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-07-22T07:36:27Z) - Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳(メタデータ) (2024-02-19T03:08:02Z) - Posterior Sampling with Delayed Feedback for Reinforcement Learning with
Linear Function Approximation [62.969796245827006]
Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。
我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。
遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
論文 参考訳(メタデータ) (2023-10-29T06:12:43Z) - A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays [24.998122268199797]
本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。
我々のアルゴリズムは任意の過剰な遅延を許容し、$T$をオーダーすることができる。
論文 参考訳(メタデータ) (2023-08-21T12:17:40Z) - Multi-Armed Bandits with Generalized Temporally-Partitioned Rewards [0.4194295877935867]
現実のアプリケーションでは、決定に関するフィードバックが遅れて、異なる遅延で観察される部分的な報酬によって到着する場合がある。
本稿では,時間分割報酬を一般化したマルチアームバンディット(multi-armed bandits)と呼ばれる新しい問題定式化を提案する。
検討した問題に対する一様に効率的なアルゴリズムの性能の低い境界を導出する。
論文 参考訳(メタデータ) (2023-03-01T16:22:22Z) - Reward Imputation with Sketching for Contextual Batched Bandits [48.80803376405073]
コンテキストバッチバンドイット(Contextual batched bandit、CBB)は、各エピソードの最後に環境から報酬のバッチを観測する設定である。
CBBの既存のアプローチは、実行されていないアクションの報酬を無視し、フィードバック情報の未利用につながることが多い。
本研究では,未観測の報酬をスケッチを用いて完遂するSketched Policy Updating with Imputed Rewards (SPUIR)を提案する。
論文 参考訳(メタデータ) (2022-10-13T04:26:06Z) - 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) - Stochastic bandits with arm-dependent delays [102.63128271054741]
我々は、単純なUCBベースのアルゴリズムであるPatentBanditsを提案する。
問題に依存しない境界も問題に依存しない境界も、性能の低い境界も提供します。
論文 参考訳(メタデータ) (2020-06-18T12:13:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。