論文の概要: Posterior Sampling with Delayed Feedback for Reinforcement Learning with
Linear Function Approximation
- arxiv url: http://arxiv.org/abs/2310.18919v2
- Date: Sat, 4 Nov 2023 01:38:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-07 19:47:44.775499
- Title: Posterior Sampling with Delayed Feedback for Reinforcement Learning with
Linear Function Approximation
- Title（参考訳）: リニア関数近似による強化学習のための遅延フィードバックによる後方サンプリング
- Authors: Nikki Lijing Kuang, Ming Yin, Mengdi Wang, Yu-Xiang Wang, Yi-An Ma
- Abstract要約: Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。
我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。
遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
- 参考スコア（独自算出の注目度）: 62.969796245827006
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent studies in reinforcement learning (RL) have made significant progress
by leveraging function approximation to alleviate the sample complexity hurdle
for better performance. Despite the success, existing provably efficient
algorithms typically rely on the accessibility of immediate feedback upon
taking actions. The failure to account for the impact of delay in observations
can significantly degrade the performance of real-world systems due to the
regret blow-up. In this work, we tackle the challenge of delayed feedback in RL
with linear function approximation by employing posterior sampling, which has
been shown to empirically outperform the popular UCB algorithms in a wide range
of regimes. We first introduce Delayed-PSVI, an optimistic value-based
algorithm that effectively explores the value function space via noise
perturbation with posterior sampling. We provide the first analysis for
posterior sampling algorithms with delayed feedback in RL and show our
algorithm achieves $\widetilde{O}(\sqrt{d^3H^3 T} + d^2H^2 E[\tau])$ worst-case
regret in the presence of unknown stochastic delays. Here $E[\tau]$ is the
expected delay. To further improve its computational efficiency and to expand
its applicability in high-dimensional RL problems, we incorporate a
gradient-based approximate sampling scheme via Langevin dynamics for
Delayed-LPSVI, which maintains the same order-optimal regret guarantee with
$\widetilde{O}(dHK)$ computational cost. Empirical evaluations are performed to
demonstrate the statistical and computational efficacy of our algorithms.
- Abstract（参考訳）: 強化学習(RL)の最近の研究は、関数近似を利用して、より優れたパフォーマンスのためにサンプル複雑性ハードルを緩和することで、大きな進歩を遂げている。
成功にもかかわらず、既存の効率的アルゴリズムは通常、行動を取る際の即時フィードバックのアクセシビリティに依存している。
観測における遅延の影響を考慮できないことは、後悔の爆発によって現実世界のシステムの性能を著しく低下させる可能性がある。
本研究では, 線形関数近似を用いたRLにおける遅延フィードバックの課題に対して, 後方サンプリングを用いることで, 幅広い状況において, 一般的な UCB アルゴリズムを実証的に上回っていることを示す。
Delayed-PSVIは楽観的な値に基づくアルゴリズムで、後続サンプリングによる雑音摂動による値関数空間を効果的に探索する。
RLの遅延フィードバックによる後方サンプリングアルゴリズムの最初の解析を行い,我々のアルゴリズムが未知の確率遅延の存在下での最悪の後悔を$\widetilde{O}(\sqrt{d^3H^3T} + d^2H^2E[\tau])で達成したことを示す。
ここで$E[\tau]$が期待の遅延です。
計算効率をさらに向上し,高次元RL問題に適用可能性を高めるために,遅延LPSVIのランゲヴィン力学を用いた勾配に基づく近似サンプリングスキームを導入し,計算コストを$\widetilde{O}(dHK)$で同じオーダー最適後悔保証を維持する。
アルゴリズムの統計的および計算的有効性を示すために経験的評価を行う。
関連論文リスト
- Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations [12.696136981847438]
ほぼ並列化されたイテレーション (OptEx) で高速化された一階最適化を導入する。
OptExは、並列コンピューティングを活用して、その反復的ボトルネックを軽減することで、FOOの効率を高める最初のフレームワークである。
我々は、カーネル化された勾配推定の信頼性とSGDベースのOpsExの複雑さを理論的に保証する。
論文 参考訳（メタデータ） (2024-02-18T02:19:02Z) - High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。
我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。
本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-19T15:29:32Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Revisiting State Augmentation methods for Reinforcement Learning with
Stochastic Delays [10.484851004093919]
本稿では,遅延を伴うマルコフ決定過程(MDP)の概念を正式に述べる。
遅延MDPは、コスト構造が大幅に単純化された(遅延なしで)等価な標準MDPに変換可能であることを示す。
この等価性を利用して、モデルフリーな遅延分解RLフレームワークを導出し、このフレームワーク上に構築された単純なRLアルゴリズムでさえ、動作や観測の遅延を伴う環境におけるほぼ最適報酬を達成することを示す。
論文 参考訳（メタデータ） (2021-08-17T10:45:55Z) - Non-asymptotic estimates for TUSLA algorithm for non-convex learning
with applications to neural networks with ReLU activation function [3.5044892799305956]
Lovas et alで導入された未調整Langevinアルゴリズム(TUSLA)の非漸近解析を行う。
特に、Wassersteinstein-1-2におけるTUSLAアルゴリズムの非漸近誤差境界を確立する。
TUSLAアルゴリズムは最適解に急速に収束することを示す。
論文 参考訳（メタデータ） (2021-07-19T07:13:02Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳（メタデータ） (2021-04-09T14:50:59Z) - Stochastic Gradient Langevin with Delayed Gradients [29.6870062491741]
本研究では,計算に用いた遅延勾配情報による誤差が測定値の収束率に有意な影響を及ぼさないことを示す。
計算に用いた遅延勾配情報による誤差は, 測定値の収束率に有意な影響を与えず, ウォールクロック時間における高速化の可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-12T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。