REVIEW 6 cited by
Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
As an important type of reinforcement learning algorithms, actor-critic (AC) and natural actor-critic (NAC) algorithms are often executed in two ways for finding optimal policies. In the first nested-loop design, actor's one update of policy is followed by an entire loop of critic's updates of the value function, and the finite-sample analysis of such AC and NAC algorithms have been recently well established. The second two time-scale design, in which actor and critic update simultaneously but with different learning rates, has much fewer tuning parameters than the nested-loop design and is hence substantially easier to implement. Although two time-scale AC and NAC have been shown to converge in the literature, the finite-sample convergence rate has not been established. In this paper, we provide the first such non-asymptotic convergence rate for two time-scale AC and NAC under Markovian sampling and with actor having general policy class approximation. We show that two time-scale AC requires the overall sample complexity at the order of $\mathcal{O}(\epsilon^{-2.5}\log^3(\epsilon^{-1}))$ to attain an $\epsilon$-accurate stationary point, and two time-scale NAC requires the overall sample complexity at the order of $\mathcal{O}(\epsilon^{-4}\log^2(\epsilon^{-1}))$ to attain an $\epsilon$-accurate global optimal point. We develop novel techniques for bounding the bias error of the actor due to dynamically changing Markovian sampling and for analyzing the convergence rate of the linear critic with dynamically changing base functions and transition kernel.
Forward citations
Cited by 6 Pith papers
-
Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
For average-reward MDPs with total-variation uncertainty, the minimax sample complexity is SA/epsilon^2 times min{H0,Hsigma}, with an extra SA sigma Hsigma^2/epsilon^2 term in the low-tolerance regime, and the paper p...
-
On the Policy Convergence of Policy Mirror Descent Methods
Unregularized PMD with any constant step size converges to a limiting optimal policy for general decomposable Legendre mirror maps, with behavior governed by differentiability of ψ at 0 and 1.
-
SHAP-Guided Kernel Actor-Critic for Explainable Reinforcement Learning
RSA2C is a kernel-based actor-critic that uses RKHS-SHAP state attributions from its value critic to reweight the policy kernel and advantage targets, with a claimed global non-asymptotic convergence bound under pertu...
-
Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning
Claims the first O(1/T) global optimality guarantee for deep neural actor-critic methods in decentralized multi-agent reinforcement learning, but the central proof conflates Q-function TD errors with advantage functions.
-
Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulator
Single-sample single-timescale actor-critic provably finds the global optimum of linear quadratic regulation on continuous state-action space with O(ε^-2) sample complexity.
-
Decoupled Functional Central Limit Theorems for Two-Time-Scale Stochastic Approximation
Rescaled fast and slow iterates of two-time-scale stochastic approximation converge weakly to decoupled Ornstein-Uhlenbeck processes, with coupling entering only through the coefficient matrices.
Discussion (0). Continue with ORCID to comment.