# Provably Efficient Model-Free Constrained RL with Linear Function Approximation

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 41 references that are in the map.
- First posted on arXiv 23 Jun 2022.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [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)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (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)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Reinforcement Learning with Dynamic Boltzmann Softmax Updates](https://mlsanity.com/paper/1903.05926/) (2019)
- [Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions](https://mlsanity.com/paper/2010.11450/) (2020)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)

## Built on by (most cited first, 30 of 31)

- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Long-Term Fairness with Unknown Dynamics](https://mlsanity.com/paper/2304.09362/) (2023)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [Refining Minimax Regret for Unsupervised Environment Design](https://mlsanity.com/paper/2402.12284/) (2024)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL](https://mlsanity.com/paper/2206.14057/) (2022)
- [A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learning](https://mlsanity.com/paper/2306.07818/) (2023)
- [Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces](https://mlsanity.com/paper/2502.18655/) (2025)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees](https://mlsanity.com/paper/2505.19238/) (2025)
- [An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints](https://mlsanity.com/paper/2505.21841/) (2025)
- [Online Nonstochastic Control with Adversarial and Static Constraints](https://mlsanity.com/paper/2302.02426/) (2023)
- [Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraints](https://mlsanity.com/paper/2306.06265/) (2023)
- [Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees](https://mlsanity.com/paper/2508.05441/) (2025)
- [Provable Reset-free Reinforcement Learning by No-Regret Reduction](https://mlsanity.com/paper/2301.02389/) (2023)
- [Flipping-based Policy for Chance-Constrained Markov Decision Processes](https://mlsanity.com/paper/2410.06474/) (2024)
- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation](https://mlsanity.com/paper/2211.15792/) (2022)
- [Anytime-Competitive Reinforcement Learning with Policy Prior](https://mlsanity.com/paper/2311.01568/) (2023)
- [Out-of-Distribution-Aware Electric Vehicle Charging](https://mlsanity.com/paper/2311.05941/) (2023)
- [Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs](https://mlsanity.com/paper/2309.15395/) (2023)
- [Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints](https://mlsanity.com/paper/2310.00962/) (2023)
- [Scrutinize What We Ignore: Reining In Task Representation Shift Of Context-Based Offline Meta Reinforcement Learning](https://mlsanity.com/paper/2405.12001/) (2024)
- [Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Exploration](https://mlsanity.com/paper/2603.18326/) (2026)
- [Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPs](https://mlsanity.com/paper/2604.02727/) (2026)
- [Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guarantees](https://mlsanity.com/paper/2604.14243/) (2026)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)

## Abstract (arXiv)

We study the constrained reinforcement learning problem, in which an agent aims to maximize the expected cumulative reward subject to a constraint on the expected total value of a utility function. In contrast to existing model-based approaches or model-free methods accompanied with a `simulator', we aim to develop the first model-free, simulator-free algorithm that achieves a sublinear regret and a sublinear constraint violation even in large-scale systems. To this end, we consider the episodic constrained Markov decision processes with linear function approximation, where the transition dynamics and the reward function can be represented as a linear function of some known feature mapping. We show that tildeO(√d3H3T) regret and tildeO(√d3H3T) constraint violation bounds can be achieved, where d is the dimension of the feature mapping, H is the length of the episode, and T is the total number of steps. Our bounds are attained without explicitly estimating the unknown transition model or requiring a simulator, and they depend on the state space only through the dimension of the feature mapping. Hence our bounds hold even when the number of states goes to infinity. Our main results are achieved via novel adaptations of the standard LSVI-UCB algorithms. In particular, we first introduce primal-dual optimization into the LSVI-UCB algorithm to balance between regret and constraint violation. More importantly, we replace the standard greedy selection with respect to the state-action function in LSVI-UCB with a soft-max policy. This turns out to be key in establishing uniform concentration for the constrained case via its approximation-smoothness trade-off. We also show that one can achieve an even zero constraint violation while still maintaining the same order with respect to T.