Research map / Reinforcement learning / Policy gradient and actor-critic
Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration
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 LSVI-AE, a least-squares value iteration algorithm for linear MDPs with instantaneous hard constraints that uses adaptive penalty-based optimization and double optimism, achieving sqrt(d^3H^4K) regret and optimal-in-K hard violation without known safe actions.
Problem
Safe RL in episodic MDPs with instantaneous hard constraints (unsafe actions must be avoided at every step), where the agent has no prior knowledge of safe actions or safe graphs and cost functions may be linear or in an RKHS.
Approach
Selects actions by maximizing optimistic Q minus an adaptive penalty on the rectified optimistic cost estimate, with the penalty floored at a growing lower bound (eta_k = k), and learns both Q and cost optimistically (double optimism), encouraging aggressive early exploration rather than conservative safe exploration.
Key results
- LSVI-AE achieves regret O~(sqrt(d^3H^4K)) and hard violation O~(H sqrt(dK)) for linear costs, and O(H gamma_K sqrt(K)) for RKHS costs.
- A lower bound of Omega(Hd sqrt(HK)) on regret and Omega(sqrt(HK)) on violation is proved, showing optimal K-dependence.
- On Frozen Lake, LSVI-AE matches the unconstrained LSVI reward while substantially reducing constraint cost; LSVI-Primal fails to reach zero hard violation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LSVI-AE instead of unconstrained LSVI | Frozen Lake · Frozen Lake | cost return | Helped |
| use LSVI-AE instead of unconstrained LSVI | Frozen Lake · Frozen Lake | reward | No clear effect |
| use LSVI-Primal instead of LSVI-AE | Frozen Lake · Frozen Lake | reward | Hurt |
| use LSVI-Primal instead of unconstrained LSVI | Frozen Lake · Frozen Lake | cost return | Helped |
Surprising findings
- Aggressive early exploration of potentially unsafe actions is argued to be necessary when no safe actions are known, in contrast to conservative safe-exploration methods.
- The standard primal-dual (virtual queue) approach fails to achieve hard instantaneous constraint satisfaction in the simulation, though it reduces cost relative to unconstrained LSVI.
Limitations
- The lower-bound and dependence on d and H are not matched without the rare-switching technique, which is only mentioned rather than applied.
- Hard violation is unavoidable at the start since the agent must explore from scratch; the violation bound depends on estimation error terms.
- Experiments are limited to a small tabular Frozen Lake environment with one-hot features.
Experimental setup
Datasets: Frozen Lake (10x10 grid, simulated)
Benchmarks: Frozen Lake
Metrics: moving average reward cumulative hard constraint violation cost
Baselines: LSVI LSVI-Primal SLUCB-QVI LSVI-NEW
Builds on: LSVI-UCB GP-LCB SLUCB-QVI LSVI-NEW primal-dual / drift-plus-penalty
Closest papers by meaning
- A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints (ICML 2023 · similarity 0.94)
- Provably Safe Reinforcement Learning with Step-wise Violation Constraints (NeurIPS 2023 · similarity 0.92)
- Sampling-Based Safe Reinforcement Learning (NeurIPS 2026 · similarity 0.92)
- Long-Term Safe Reinforcement Learning with Binary Feedback (AAAI 2024 · similarity 0.91)
- Reward Penalties on Augmented States for Solving Richly Constrained RL Effectively (AAAI 2024 · similarity 0.91)
- Safe Reinforcement Learning using Finite-Horizon Gradient-based Estimation (ICML 2024 · similarity 0.91)
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.