論文の概要: Delayed Feedback in Generalised Linear Bandits Revisited
- arxiv url: http://arxiv.org/abs/2207.10786v4
- Date: Tue, 11 Apr 2023 11:52:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-12 19:16:32.025810
- 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(参考訳): 確率的一般化線形帯域は、逐次決定問題に対するよく理解されたモデルであり、多くのアルゴリズムは即時フィードバックの下でほぼ最適の後悔を保証する。
しかし、即時報酬の厳格な要求は、報酬がほとんど常に遅れている多くの現実世界のアプリケーションでは未完成である。
一般化線形バンディットにおける遅延報酬現象を理論的に検討した。
遅延フィードバックに対する楽観的なアルゴリズムの自然な適応は、遅延に対するペナルティが地平線から独立であるような後悔境界を達成することを示す。
この結果は、最もよく知られた後悔境界が地平線にしたがって遅延ペナルティが増大する既存の作業を大幅に改善する。
シミュレーションデータを用いた実験により理論的結果を検証する。
関連論文リスト
- Stochastic Approximation with Delayed Updates: Finite-Time Rates under
Markovian Sampling [76.72850243028888]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳(メタデータ) (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) - An Improved Best-of-both-worlds Algorithm for Bandits with Delayed
Feedback [28.095384245873113]
本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。
アルゴリズムとその後悔の限界は、遅延や最大遅延よりも、卓越した観測の回数に基づいている。
論文 参考訳(メタデータ) (2023-08-21T12:17:40Z) - A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial
Semi-Bandits, Linear Bandits, and MDPs [18.199326045904996]
オンライン学習のためのFTRL(Follow The Regularized Leader)の新たな分析結果を得た。
我々の新しい後悔分解は、FTRLが正則化器のヘシアンに穏やかな仮定の下で複数のラウンドで安定であることを示している。
論文 参考訳(メタデータ) (2023-05-15T13:21:50Z) - 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) - Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
オンライン凸最適化の問題点を未知の遅延で検討する。
まず、OGDの遅延変形を強凸関数に拡張する。
我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
論文 参考訳(メタデータ) (2021-03-21T10:16:15Z) - Stochastic bandits with arm-dependent delays [102.63128271054741]
我々は、単純なUCBベースのアルゴリズムであるPatentBanditsを提案する。
問題に依存しない境界も問題に依存しない境界も、性能の低い境界も提供します。
論文 参考訳(メタデータ) (2020-06-18T12:13:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。