Research map / Reinforcement learning / MDPs and planning
Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces
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.
Establishes a corrected covering-number bound for safe linear-MDP RL under instantaneous hard constraints (via Objective-Constraint Decomposition in star-convex sets) and proposes NCS-LSVI, a two-phase algorithm with pure safe exploration for non-star-convex safe sets, achieving sublinear regret with zero safety violation.
Problem
Regret minimization in linear MDPs with instantaneous hard safety constraints where the feasible action set in feature space is star-convex or non-star-convex (e.g., collision avoidance), where covering-number arguments from unconstrained RL break down.
Approach
Shows that the value-function class under data-dependent safe sets needs a constraint-aware covering argument (Objective-Constraint Decomposition) for star-convex sets, and for non-star-convex sets under a Local Point Assumption uses an initial pure safe exploration phase to stabilize the estimated safe set so the covering number stays polynomial.
Key results
- NCS-LSVI achieves regret bound of order (1+1/tau) sqrt(log(1/tau) d^3 H^4 K) plus a pure-exploration term 1/(eps^2 iota^2) in non-star-convex settings, with safety maintained with high probability.
- Corrected covering-number result for star-convex case adds a sqrt(log(1/tau)) factor missing from prior work (SLUCB-QVI Theorem 1).
- In the merging simulation, regret is sublinear for K'=2000 pure exploration episodes and the lane-keeping constraint is never violated.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Objective–Constraint Decomposition (OCD) to bound the value-function covering number | Safe RL in star-convex linear MDPs · Star-convex linear MDP | regret upper bound: includes the missing \(\sqrt{\log\bigl(\tfrac{1}{\tau}\bigr)}\) factor | Mixed |
| Add a pure safe exploration phase before safe exploration-exploitation | NCS-LSVI · Non-star-convex linear MDP under the Local Point Assumption | regret | Helped |
| Remove the pure exploration phase (ablation) | NCS-LSVI · Non-star-convex linear MDP | value-function covering number: at least as large as the number of states | Hurt |
| Skip the pure exploration phase (set K' = 0) (ablation) | NCS-LSVI · Star-convex autonomous vehicle merging scenario | regret | No clear effect |
| Use K' = 2000 pure exploration episodes (ablation) | NCS-LSVI · Non-star-convex autonomous vehicle merging scenario | regret | Helped |
| Use the two-phase NCS-LSVI algorithm | Non-star-convex autonomous vehicle merging scenario · Autonomous vehicle merging scenario | safety constraint violations: never violates | Helped |
| Remove the collision avoidance module (ablation) | Autonomous vehicle merging simulation · Star-convex autonomous vehicle merging scenario | regret | No clear effect |
Surprising findings
- The covering number of the value-function class can be lower bounded by the number of states in non-star-convex safe sets, so unconstrained covering arguments fail.
- Prior star-convex regret analysis (SLUCB-QVI) is incorrect due to misapplied covering-number lemma from unconstrained RL.
Limitations
- Requires a known safe action per state and a Local Point Assumption with a hypersphere condition on the feature hyperplane.
- Experiments are small-scale (H=3, K=1000) with discretized action space and a single merging scenario.
- Analysis restricted to linear MDPs; deep RL extension left to future work.
Experimental setup
Datasets: simulated autonomous vehicle merging environment
Benchmarks: autonomous vehicle merging simulation
Metrics: regret constraint violation
Baselines: SLUCB-QVI
Builds on: SLUCB-QVI linear MDP (Jin et al.) safe linear bandits with star-convex sets LSVI-UCB
Closest papers by meaning
- Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration (AAAI 2024 · similarity 0.90)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.90)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.89)
- Safe and Efficient: A Primal-Dual Method for Offline Convex CMDPs under Partial Data Coverage (NeurIPS 2024 · similarity 0.88)
- Safe Reinforcement Learning using Finite-Horizon Gradient-based Estimation (ICML 2024 · similarity 0.87)
- Reward Penalties on Augmented States for Solving Richly Constrained RL Effectively (AAAI 2024 · similarity 0.87)
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.