Research map / Reinforcement learning / MDPs and planning
Sample-Efficient Constrained Reinforcement Learning with General Parameterization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PD-ANPG, a primal-dual natural policy gradient for general-parameterized CMDPs that uses accelerated SGD (momentum) in the inner loop to estimate the NPG, achieving O~((1-γ)^-7 ε^-2) sample complexity.
Problem
Sample complexity of constrained reinforcement learning (CMDPs) with general (non-tabular) policy parameterization; prior best for general parameterization was O~(ε^-4) (or ε^-6 for NPG-PD), far from the Ω(ε^-2) lower bound.
Approach
Replace the SGD inner loop in primal-dual NPG with accelerated SGD (momentum plus tail averaging) and show the first-order error term is the bias of the NPG estimator, which decays exponentially in inner-loop length, letting the inner loop be O(log) and yielding ε^-2 sample complexity.
Key results
- PD-ANPG achieves O~((1-γ)^-7 ε^-2) sample complexity for general parameterized CMDPs, improving the prior O~((1-γ)^-8 ε^-4) by a factor of O((1-γ)^-1 ε^-2).
- The result matches the ε^-2 dependence of the stated Ω((1-γ)^-5 ε^-2) lower bound in ε.
- Inner loop length H = O(log ε^-1) and outer loop K = O((1-γ)^-6 ε^-2) suffice for objective and constraint violation of order ε.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use accelerated stochastic gradient descent (ASGD) in the natural policy gradient inner loop instead of SGD | PD-ANPG for general-parameterized CMDPs · General-parameterized CMDP | sample complexity: \tilde{\mathcal{O}}((1-\gamma)^{-8}\epsilon^{-4}) -> \tilde{\mathcal{O}}((1-\gamma)^{-7}\epsilon^{-2}) | Helped |
| choose the dual learning rate \zeta smaller | PD-ANPG · CMDP objective and constraint violation | convergence rate | Mixed |
Surprising findings
- Decreasing the dual learning rate ζ improves objective convergence but worsens constraint violation, so ζ must be balanced (set to λmax(1-γ)/sqrt(K)).
Limitations
- Results depend on assumptions such as bounded and smooth log-policy gradients, Fisher non-degeneracy, and compatible function approximation error ε_bias that cannot be made zero for incomplete policy classes.
- Analysis is theoretical with no experiments reported.
- Assumes countable state space and finite action space for simplicity.
Experimental setup
Metrics: sample complexity global optimality gap constraint violation
Baselines: PMD-PD PD-NAC NPG-PD CRPO C-NPG-PDA
Builds on: primal-dual natural policy gradient accelerated stochastic gradient descent CRPO NPG-PD
Closest papers by meaning
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.91)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.90)
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.90)
- Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs (NeurIPS 2024 · similarity 0.89)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.89)
- A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.