論文の概要: Delayed Feedback in Generalised Linear Bandits Revisited
- arxiv url: http://arxiv.org/abs/2207.10786v2
- Date: Mon, 25 Jul 2022 11:07:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-26 11:27:42.103035
- Title: Delayed Feedback in Generalised Linear Bandits Revisited
- Title(参考訳): 一般化線形バンディットの再訪における遅延フィードバック
- Authors: Benjamin Howson, Ciara Pike-Burke, Sarah Filippi
- Abstract要約: 動作の選択と報酬の受け取りの遅延を導入することにより,遅延報酬現象を理論的に研究する。
そこで本研究では,遅延分布の事前知識を不要にすることで,楽観的な原理に基づくアルゴリズムが既存の手法を改良することを示す。
これはまた、$ widetilde O(sqrtdTsqrtd + mathbbE[tau]$ から $widetilde O(dsqrtT + d3/2mathbbE
- 参考スコア(独自算出の注目度): 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, in many real
world settings, the requirement that the reward is observed immediately is not
applicable. In this setting, standard algorithms are no longer theoretically
understood. We study the phenomenon of delayed rewards in a theoretical manner
by introducing a delay between selecting an action and receiving the reward.
Subsequently, we show that an algorithm based on the optimistic principle
improves on existing approaches for this setting by eliminating the need for
prior knowledge of the delay distribution and relaxing assumptions on the
decision set and the delays. This also leads to improving the regret guarantees
from $ \widetilde O(\sqrt{dT}\sqrt{d + \mathbb{E}[\tau]})$ to $ \widetilde
O(d\sqrt{T} + d^{3/2}\mathbb{E}[\tau])$, where $\mathbb{E}[\tau]$ denotes the
expected delay, $d$ is the dimension and $T$ the time horizon and we have
suppressed logarithmic terms. We verify our theoretical results through
experiments on simulated data.
- Abstract(参考訳): 確率的一般化線形帯域は、逐次決定問題に対するよく理解されたモデルであり、多くのアルゴリズムは即時フィードバックの下でほぼ最適の後悔を保証する。
しかし、現実世界の多くの場面では、即座に報奨を受けるという要件は適用されない。
この設定では、標準アルゴリズムはもはや理論的に理解されていない。
本研究は,行動の選択と報酬の受信の遅延を理論的に導入することにより,報酬の遅れ現象を理論的に検討する。
提案手法では,遅延分布の事前知識を排除し,決定セットと遅延に関する仮定を緩和することにより,楽観的な原理に基づくアルゴリズムが既存のアプローチを改善することを示す。
これはまた、$ \widetilde o(\sqrt{dt}\sqrt{d + \mathbb{e}[\tau]})$ to $ \widetilde o(d\sqrt{t} + d^{3/2}\mathbb{e}[\tau])$ ここで$\mathbb{e}[\tau]$は期待の遅延を表し、$d$は時間軸の次元であり、$t$は時間軸である。
シミュレーションデータを用いた実験により理論的結果を検証する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。