Research map / Reinforcement learning / MDPs and planning
Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
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 OPSE-LCMDP, a computationally efficient linear CMDP algorithm achieving O~(sqrt(K)) regret with episode-wise zero constraint violation, using a safe-policy deployment trigger and softmax-based optimistic-pessimistic exploration with bisection over a Lagrange-like weight.
Problem
Safe RL in finite-horizon linear constrained MDPs requiring zero constraint violation in every episode while achieving sublinear regret with polynomial computation independent of state-space size.
Approach
Deploy a known strictly safe policy only when the agent is unconfident about its safety (logarithmically many times), and implement optimism for reward and pessimism for utility via a composite entropy-regularized softmax policy whose trade-off parameter lambda is found by bisection search, yielding zero episode-wise violation without LP over states.
Key results
- Achieves O~(sqrt(K)) regret with zero episode-wise violation in linear CMDPs; regret bound O~(H^2 sqrt(d^3 K) + d^3 H^4 xi^-2 + H^4 xi^-1 sqrt(d^5 K)).
- Number of safe-policy deployments bounded by O~(d^3 H^4 xi^-2 ln(KH/delta)).
- Computational cost polynomial in A, H, d, versus exponential K^H cost of prior linear CMDP method with violation regret; experiments show zero violation while the prior linear method shows positive violation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OPSE-LCMDP with pessimistic constraint estimates and the safe-policy deployment rule | Linear CMDP exploration · Linear CMDP | constraint violation | Helped |
| Use OPSE-LCMDP instead of the prior linear CMDP algorithm | Linear CMDP exploration · Linear CMDP | constraint safety | Helped |
| Use bisection search over the softmax policy parameter | OPSE-LCMDP · Linear CMDP | computational cost | Helped |
| Remove the constraint | OPSE-LCMDP regret analysis · Linear MDP without constraints | regret | Helped |
Surprising findings
- The xi^-1 dependence in the leading regret term is shared by all existing safe RL works and remains unresolved, while the bound matches LSVI-UCB regret when constraints are removed.
Limitations
- Single-constraint setting only; extending bisection over lambda to multiple constraints is non-trivial.
- Initial state assumed fixed; adversarial initial states left open.
- Regret has an extra xi^-1 factor and dH^2 deterioration relative to unconstrained bound; tightness unclear.
Experimental setup
Benchmarks: simulated linear CMDP environments
Metrics: regret constraint violation regret
Baselines: DOPE prior linear CMDP algorithm with violation regret (exponential computation)
Builds on: LSVI-UCB OPLB (optimistic-pessimistic linear bandit) DOPE softmax policy for linear CMDPs
Closest papers by meaning
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.91)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.90)
- Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.90)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.90)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.89)
- Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs (NeurIPS 2024 · 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.