論文の概要: A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs

• arxiv url: http://arxiv.org/abs/2305.08629v1
• Date: Mon, 15 May 2023 13:21:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-16 14:24:07.515850
• Title: A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs
• Title（参考訳）: 組合せ半バンド、線形バンド、mdpにおける非確率的遅延フィードバックの統一的解析
• Authors: Dirk van der Hoeven and Lukas Zierahn and Tal Lancewicki and Aviv Rosenberg and Nicol\'o Cesa-Bianchi
• Abstract要約: オンライン学習のためのFTRL(Follow The Regularized Leader)の新たな分析結果を得た。 我々の新しい後悔分解は、FTRLが正則化器のヘシアンに穏やかな仮定の下で複数のラウンドで安定であることを示している。
• 参考スコア（独自算出の注目度）: 18.199326045904996
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We derive a new analysis of Follow The Regularized Leader (FTRL) for online learning with delayed bandit feedback. By separating the cost of delayed feedback from that of bandit feedback, our analysis allows us to obtain new results in three important settings. On the one hand, we derive the first optimal (up to logarithmic factors) regret bounds for combinatorial semi-bandits with delay and adversarial Markov decision processes with delay (and known transition functions). On the other hand, we use our analysis to derive an efficient algorithm for linear bandits with delay achieving near-optimal regret bounds. Our novel regret decomposition shows that FTRL remains stable across multiple rounds under mild assumptions on the Hessian of the regularizer.
• Abstract（参考訳）: オンライン学習のためのFTRL(Follow The Regularized Leader)の新たな分析結果を得た。 遅延フィードバックのコストとバンディットフィードバックのコストを分離することで,3つの重要な設定で新たな結果を得ることができる。 一方、遅延のある組合せ半帯域に対する最初の最適(対数的要因まで)後悔境界を導出し、遅延(および既知の遷移関数)を持つ逆マルコフ決定過程を導出する。 一方,提案手法を用いて,線形帯域に対する効率の良いアルゴリズムを導出する。 我々の新しい後悔分解は、FTRLが正則化器のヘシアンに穏やかな仮定の下で複数のラウンドで安定であることを示している。

関連論文リスト

• 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)
• Non-stationary Delayed Combinatorial Semi-Bandit with Causally Related Rewards [7.0997346625024]
  我々は、因果関係の報酬で非定常かつ遅延半帯域問題を定式化する。 遅延したフィードバックから構造的依存関係を学習し、それを利用して意思決定を最適化する政策を開発する。 イタリアにおけるCovid-19の拡散に最も寄与する地域を検出するために, 合成および実世界のデータセットを用いて数値解析により評価を行った。
  論文  参考訳（メタデータ） (2023-07-18T09:22:33Z)
• Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback [39.12903814606534]
  本稿では,過度な(期待している)報酬と全帯域遅延フィードバックを伴うマルチアームバンドの問題について検討する。 遅延したフィードバックは過去のアクションからの報酬のコンポーネントで構成されており、サブコンポーネント間で未知の分割がある。 提案アルゴリズムは,合成匿名フィードバックの遅延により,他の全帯域アプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2023-03-23T18:38:33Z)
• A Reduction-based Framework for Sequential Decision Making with Delayed Feedback [53.79893086002961]
  汎用マルチエージェントシーケンシャル意思決定における遅延フィードバックについて検討する。 本稿では, 逐次的意思決定のためのマルチバッチアルゴリズムを, 即時フィードバックにより, サンプル効率のよいアルゴリズムに変換する, 新たなリダクションベースフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-02-03T01:16:09Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Nonstochastic Bandits and Experts with Arm-Dependent Delays [17.272515865592542]
  遅延が時間と腕に依存するような遅延環境で,非確率的な盗賊や専門家について検討する。 私たちの分析では、ドリフトに縛られた小説にヒンジを付け、1ラウンドのルックアヘッドを与えられた場合、アルゴリズムがどれだけの精度で実行できるかを測定しました。
  論文  参考訳（メタデータ） (2021-11-02T13:36:11Z)
• Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
  ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。 情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。 これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2021-05-25T10:08:41Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)

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

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