# Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPs

arXiv: https://arxiv.org/abs/2406.18529 · HTML: https://mlsanity.com/paper/2406.18529/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 21 of its 37 references that are in the map.
- First posted on arXiv 26 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 21 of 21)

- [Safe RLHF: Safe Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2310.12773/) (2023)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [A Primal-Dual Approach to Constrained Markov Decision Processes](https://mlsanity.com/paper/2101.10895/) (2021)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization](https://mlsanity.com/paper/2003.01303/) (2020)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function](https://mlsanity.com/paper/2102.02049/) (2021)
- [Towards Painless Policy Optimization for Constrained MDPs](https://mlsanity.com/paper/2204.05176/) (2022)
- [Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPs](https://mlsanity.com/paper/2210.15755/) (2022)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)

## Built on by (most cited first, 5 of 5)

- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Constrained Meta Reinforcement Learning with Provable Test-Time Safety](https://mlsanity.com/paper/2601.21845/) (2026)
- [Near-Optimal Sample Complexity for Online Constrained MDPs](https://mlsanity.com/paper/2602.15076/) (2026)
- [Mirror descent actor-critic methods for entropy regularised MDPs in general spaces: stability and convergence](https://mlsanity.com/paper/2602.10838/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)

## Abstract (arXiv)

The constrained Markov decision process (CMDP) framework emerges as an important reinforcement learning approach for imposing safety or other critical objectives while maximizing cumulative reward. However, the current understanding of how to learn efficiently in a CMDP environment with a potentially infinite number of states remains under investigation, particularly when function approximation is applied to the value functions. In this paper, we address the learning problem given linear function approximation with qπ-realizability, where the value functions of all policies are linearly representable with a known feature map, a setting known to be more general and challenging than other linear settings. Utilizing a local-access model, we propose a novel primal-dual algorithm that, after tildeO(poly(d) ε-3) queries, outputs with high probability a policy that strictly satisfies the constraints while nearly optimizing the value with respect to a reward function. Here, d is the feature dimension and ε > 0 is a given error. The algorithm relies on a carefully crafted off-policy evaluation procedure to evaluate the policy using historical data, which informs policy updates through policy gradients and conserves samples. To our knowledge, this is the first result achieving polynomial sample complexity for CMDP in the qπ-realizable setting.