Research map / Reinforcement learning / MDPs and planning
Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs
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 Confident-NPG-CMDP, a primal-dual natural policy gradient planner with off-policy evaluation in the local-access model that achieves polynomial sample complexity for CMDPs under q_pi-realizability.
Problem
Efficient planning in constrained MDPs with large or infinite state spaces under q_pi-realizable linear function approximation, where value functions of all policies are linearly representable but transitions are not assumed linear.
Approach
Combines a primal-dual scheme (Lagrangian with mirror descent on the dual) with a natural policy gradient (softmax) update, and reuses historical rollouts through per-trajectory importance-sampled off-policy evaluation with interval-based data collection, building on CAPI-QPI-Plan's core-set construction under the local-access model to reach eps^-3 query complexity.
Key results
- Achieves Õ(poly(d) ε^-3) query complexity for finding an epsilon-optimal CMDP policy under q_pi-realizability with local access, the first polynomial result in this setting.
- Theorem 1 gives Õ(ε^-3 ζ^-3 d^2 (1-γ)^-11) queries for relaxed feasibility; Theorem 2 gives Õ(ε^-3 ζ^-6 (1-γ)^-14 d^2) for strict feasibility.
- Under misspecification omega, suboptimality and constraint violation are Õ(omega)+epsilon with the same sample complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use natural policy gradient with softmax policy structure and off-policy estimation instead of directly applying CAPI-QPI-Plan | CMDP planning with qπ-realizability · qπ-realizable CMDP, local access | sample complexity: \tilde O(\epsilon^{-4}) -> \tilde O(\epsilon^{-3}) | Helped |
| Use periodic data collection and reuse data for off-policy policy updates | Confident-NPG-CMDP · qπ-realizable CMDP, local access | sample complexity: \tilde{O}(\epsilon^{-3}) | Helped |
| Require strict feasibility rather than relaxed feasibility | Confident-NPG-CMDP · qπ-realizable CMDP, local access | local-access queries: \tilde O(\epsilon^{-3} \zeta^{-3} d^2 (1-\gamma)^{-11}) -> \tilde O(\epsilon^{-3} \zeta^{-6}(1-\gamma)^{-14} d^2 ) | Hurt |
Limitations
- Requires knowledge of the Slater constant zeta (estimated separately per Remark 3).
- Strict feasibility requires extra assumptions on misspecification error omega and higher sample complexity (zeta^-6).
Experimental setup
Metrics: sample complexity (queries to local-access model) suboptimality constraint violation
Baselines: CAPI-QPI-Plan
Builds on: CAPI-QPI-Plan Confident-NPG Lagrangian primal-dual method for CMDPs
Closest papers by meaning
- Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees (NeurIPS 2025 · similarity 0.90)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.89)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.89)
- Sample-Efficient Constrained Reinforcement Learning with General Parameterization (NeurIPS 2024 · similarity 0.89)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.89)
- Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 2025 · similarity 0.89)
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.