論文の概要: Uniform-PAC Bounds for Reinforcement Learning with Linear Function
Approximation
- arxiv url: http://arxiv.org/abs/2106.11612v1
- Date: Tue, 22 Jun 2021 08:48:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 15:04:42.907629
- Title: Uniform-PAC Bounds for Reinforcement Learning with Linear Function
Approximation
- Title(参考訳): 線形関数近似を用いた強化学習のための一様PAC境界
- Authors: Jiafan He and Dongruo Zhou and Quanquan Gu
- Abstract要約: 線形関数近似を用いた強化学習について検討する。
既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。
我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
- 参考スコア(独自算出の注目度): 92.3161051419884
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study reinforcement learning (RL) with linear function approximation.
Existing algorithms for this problem only have high-probability regret and/or
Probably Approximately Correct (PAC) sample complexity guarantees, which cannot
guarantee the convergence to the optimal policy. In this paper, in order to
overcome the limitation of existing algorithms, we propose a new algorithm
called FLUTE, which enjoys uniform-PAC convergence to the optimal policy with
high probability. The uniform-PAC guarantee is the strongest possible guarantee
for reinforcement learning in the literature, which can directly imply both PAC
and high probability regret bounds, making our algorithm superior to all
existing algorithms with linear function approximation. At the core of our
algorithm is a novel minimax value function estimator and a multi-level
partition scheme to select the training samples from historical observations.
Both of these techniques are new and of independent interest.
- Abstract(参考訳): 線形関数近似による強化学習(rl)について検討した。
この問題に対する既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たず、最適ポリシーへの収束を保証できない。
本稿では,既存のアルゴリズムの限界を克服するために,高確率で最適方針への一様パック収束を享受するフルートと呼ばれる新しいアルゴリズムを提案する。
この一様PAC保証は,PACと高確率後悔境界の両方を直接的に示唆し,線形関数近似を持つ既存のアルゴリズムよりも優れたアルゴリズムを実現するため,文献中では最強の強化学習保証となる。
アルゴリズムの核となるのは,新しいミニマックス値関数推定器と,過去の観測からトレーニングサンプルを選択するマルチレベル分割スキームである。
これらの技術はどちらも新しく、独立した関心事である。
関連論文リスト
- A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees [28.974797385513263]
オンラインマルコフ制約決定過程(CMDP)に対する原始二重強化学習(RL)アルゴリズムについて検討する。
本稿では,一様に近似した正当性(Uniform-PAC)を保証し,最適ポリシへの収束,サブ線形後悔,任意の目標精度に対するサンプル複雑性を同時に確保する,新しいポリシー勾配PDアルゴリズムを提案する。
特に、これはオンラインCMDP問題に対する最初のUniform-PACアルゴリズムである。
論文 参考訳(メタデータ) (2024-01-31T12:23:24Z) - Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文 参考訳(メタデータ) (2023-10-22T12:37:25Z) - Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension [86.3584476711976]
一般関数クラスと有界エリューダを用いた非線形帯域幅とモデルベースエピソードRLのアルゴリズムを提案する。
達成された一様PACサンプルの複雑性は、最先端の後悔境界や、線形ケースに還元された場合のサンプルの複雑さを保証するという意味で厳密である。
論文 参考訳(メタデータ) (2023-05-15T05:07:45Z) - A relaxed proximal gradient descent algorithm for convergent
plug-and-play with proximal denoiser [6.2484576862659065]
本稿では,新しいコンバーゼントなPlug-and-fidelity Descent (Play)アルゴリズムを提案する。
このアルゴリズムは、より広い範囲の通常の凸化パラメータに収束し、画像のより正確な復元を可能にする。
論文 参考訳(メタデータ) (2023-01-31T16:11:47Z) - PAC-Bayesian Learning of Optimization Algorithms [6.624726878647541]
PAC-Bayes理論を学習最適化の設定に適用する。
証明可能な一般化保証(PAC-bounds)と高収束確率と高収束速度との間の明示的なトレードオフを持つ最適化アルゴリズムを学習する。
この結果は指数族に基づく一般の非有界損失関数に対してPAC-Bayes境界に依存する。
論文 参考訳(メタデータ) (2022-10-20T09:16:36Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-08-22T16:00:45Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。
ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。
そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-08T00:43:04Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。