論文の概要: 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$は時間軸である。 シミュレーションデータを用いた実験により理論的結果を検証する。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。