論文の概要: A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants

• arxiv url: http://arxiv.org/abs/2102.01567v4
• Date: Mon, 4 Sep 2023 20:15:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 12:33:06.617327
• Title: A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Title（参考訳）: 非同期Q-LearningとTD-Learningの有限サンプル保証に対するリアプノフ理論
• Authors: Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam
• Abstract要約: 本稿では,値に基づく非同期RLアルゴリズムのクラスに対する有限サンプル収束保証について検討する枠組みを開発する。 副産物として、偏差トレードオフ、すなわちRLにおけるブートストラップの効率に関する理論的知見を提供する。
• 参考スコア（独自算出の注目度）: 39.28675942566465
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper develops an unified framework to study finite-sample convergence guarantees of a large class of value-based asynchronous reinforcement learning (RL) algorithms. We do this by first reformulating the RL algorithms as \textit{Markovian Stochastic Approximation} (SA) algorithms to solve fixed-point equations. We then develop a Lyapunov analysis and derive mean-square error bounds on the convergence of the Markovian SA. Based on this result, we establish finite-sample mean-square convergence bounds for asynchronous RL algorithms such as $Q$-learning, $n$-step TD, TD$(\lambda)$, and off-policy TD algorithms including V-trace. As a by-product, by analyzing the convergence bounds of $n$-step TD and TD$(\lambda)$, we provide theoretical insights into the bias-variance trade-off, i.e., efficiency of bootstrapping in RL. This was first posed as an open problem in (Sutton, 1999).
• Abstract（参考訳）: 本稿では,大規模な値ベース非同期強化学習(RL)アルゴリズムの有限サンプル収束を保証する統一フレームワークを開発する。 固定点方程式を解くために、まず RL アルゴリズムを \textit{Markovian Stochastic Approximation} (SA) アルゴリズムとして再構成する。 次に、リアプノフ解析を開発し、マルコフSAの収束に基づく平均二乗誤差境界を導出する。 この結果に基づいて,Q$-learning,$n$-step TD,TD$(\lambda)$,V-traceを含む非政治的TDアルゴリズムなどの非同期RLアルゴリズムに対して,有限サンプル平均二乗収束境界を確立する。 副産物として、$n$-step TD と TD$(\lambda)$ の収束境界を解析することにより、バイアス分散トレードオフ、すなわち RL におけるブートストラップの効率に関する理論的洞察を提供する。 これは最初に開問題として提起された(Sutton, 1999)。

関連論文リスト

• Finite Time Analysis of Temporal Difference Learning for Mean-Variance in a Discounted MDP [1.0923877073891446]
  割引報酬マルコフ決定プロセスにおける分散政策評価の問題点を考察する。 本稿では,線形関数近似(LFA)を用いた時間差分型学習アルゴリズムについて述べる。 平均二乗の意味で(i) を保持する有限標本境界と、(ii) テールイテレート平均化を用いる場合の高い確率を導出する。
  論文  参考訳（メタデータ） (2024-06-12T05:49:53Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。 本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
  論文  参考訳（メタデータ） (2023-08-17T08:34:58Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation [10.159501412046508]
  マルコフ決定過程(MDP)におけるモデルベース強化学習(RL)について検討する。 我々は,多項ロジスティックモデルにより状態遷移が与えられるMPPに対して,証明可能な効率のよいRLアルゴリズムを確立する。 我々の知る限りでは、証明可能な保証付き多項ロジスティック関数近似を用いたモデルベースRLアルゴリズムとしてはこれが初めてである。
  論文  参考訳（メタデータ） (2022-12-27T16:25:09Z)
• Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods [6.7546872379126155]
  一般的なアプローチは、架空の割引係数を導入し、近似に定常ポリシーを使用することである。 本稿では,これらのアルゴリズムを解析する第一歩を踏み出す。 どちらのアルゴリズムにも非漸近収束保証が確立されている。
  論文  参考訳（メタデータ） (2021-09-13T23:36:38Z)
• Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
  分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。 提案アルゴリズムの有効性と有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-04T16:49:29Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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