Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration

AI summary

Overview

Research area: Constrained Reinforcement Learning (CRL) and safe exploration, specifically the study of estimation bias in cost value functions.

Technical level: Advanced. The paper assumes familiarity with CMDPs, trust-region policy optimization (CPO), primal-dual Lagrangian methods, Bellman updates, and pseudo-count-based exploration bonuses.

Scope: The paper identifies underestimation bias in cost value functions as a driver of constraint violations in CRL, and proposes a memory-driven intrinsic cost mechanism (MICE) that corrects this bias while controlling the amount of bias introduced, supported by convergence and constraint-violation bounds and experiments on Safety Gym and Safety MuJoCo.

What This Paper Is About

Constrained RL agents must maximize reward while keeping cumulative cost below a threshold, but existing algorithms (CPO, PID Lagrangian, CUP, Saute, Simmer) frequently violate constraints during training. The authors argue the root cause is that cost value functions are systematically underestimated — because cost updates use a minimization operator over noisy estimates, the zero-mean-noise assumption breaks and high-cost states look deceptively safe. The goal is to shape cost estimation so that harmful underestimation in high-cost regions is corrected, without making the agent so conservative that it loses performance.

Key Contributions

1. Flashbulb Memory mechanism. A memory module stores previously explored unsafe states (states with positive extrinsic cost), letting the agent identify high-cost regions. Each state is embedded into a lower-dimensional latent space via a random projection layer implemented with a Gaussian random matrix, justified by the Johnson–Lindenstrauss lemma to approximately preserve relative Euclidean distances.

2. Extrinsic-intrinsic cost value update with bias correction. The intrinsic cost is defined as a pseudo-count of the current state visiting high-cost regions in memory, computed from the sum of kernel similarities over the k-nearest neighbors of the state embedding. This intrinsic cost is added to the extrinsic cost target with an intrinsic factor β, and an adaptive bias correction mechanism adjusts the target based on the estimated bias from the previous update.

3. Theoretical analysis. The authors prove an extrinsic-intrinsic constraint bound (Theorem 4.3), a worst-case constraint violation bound for the MICE update (Theorem 4.4) that they state is tighter than CPO's, and convergence of the extrinsic-intrinsic cost value function to the optimal value with probability 1 (Theorem 4.5) under standard stochastic-approximation conditions.

4. Practical algorithms and experiments. MICE-CPO and MICE-PIDLag are derived from the trust-region optimization objective, with code released at https://github.com/ShiqingGao/MICE.

Main Findings

• Underestimation is empirically confirmed. Comparing estimated cost values against true values (computed by averaging cumulative discounted costs over 1,000 episodes under the current policy), both the primal method CPO and the primal-dual method PID Lagrangian consistently and significantly underestimate cost value across environments during training.

• MICE reduces constraint violations while preserving performance. In Safety Gym (four navigation tasks: Goal and Circle, with Point and Car agents) and Safety MuJoCo (four tasks), MICE maintains superior or similar returns to baselines while substantially lowering constraint violations. In the Goal1 navigation tasks with multiple hazards, MICE improves policy performance while maintaining constraint satisfaction.

• Zero constraint violations in Safety MuJoCo. MICE consistently maintains zero constraint violations throughout training with convergence speed comparable to or faster than baselines, matching the constraint satisfaction of Saute and SimmerPID while surpassing them in policy performance. In HalfCheetahVelocity, PIDLag exceeds the constraint threshold, so its higher return than MICE does not indicate a better policy.

• Estimation bias is corrected, not just shifted. MICE's estimated cost values are significantly higher than the baselines', and the residual estimation bias approaches zero, indicating the balancing factor β effectively corrects bias. The extrinsic-intrinsic cost value function gradually converges to the true value, consistent with Theorem 4.5.

• Simply adding a constant penalty does not work. In an ablation where the intrinsic cost is replaced by fixed constants (3, 5, 15), policy performance decreases. Constraint violations are more frequent with constant 5 than with constant 3, showing that adding a larger value to the cost estimate does not necessarily reduce violations. MICE achieves the best performance, indicating the intrinsic cost does not achieve safety merely by introducing conservatism.

• Robustness to constraint thresholds. Sensitivity experiments in SafetyPointGoal1-v0 with thresholds 0, 15, and 25 show MICE adapting to varying requirements: at threshold 15 it balances performance and constraint satisfaction, and under the strict threshold of 0 it enforces compliance.

• Random projection layer is useful. The ablation on the random projection layer shows it significantly reduces computational complexity without degrading policy performance or increasing constraint violations.

• KNN sensitivity. Increasing the number of nearest neighbors k enhances policy safety but also raises computational overhead; the authors set k = 10 uniformly across all environments.

Methodology in Plain English

The authors begin from a known quirk of value-based learning: when you take a minimum over noisy estimates, the noise no longer averages out and you systematically underestimate. In RL this is normally a problem with maximization and Q-values (the classic overestimation problem that Double Q-learning and TD3 address), but in constrained RL the cost critic uses a minimization and therefore drifts below the true cost. An agent that thinks dangerous states are cheap will walk into them.

Their fix is a memory of bad experiences. Whenever the agent encounters a state with positive cost, that state is stored in a "flashbulb memory," named after the human tendency to vividly recall dangerous events. States are compressed into a lower-dimensional embedding so that comparison is cheap. When the agent is in a new state, it compares that state's embedding against the stored unsafe states; the more similar it is to remembered danger, the higher a bonus cost it receives. This bonus is called the intrinsic cost, and it acts like a pseudo-count of visits to high-cost regions, following the same idea as count-based exploration bonuses but used in the opposite direction — to discourage rather than encourage.

The intrinsic cost is added to the ordinary, environment-provided extrinsic cost in the Bellman target, which pushes the cost estimate upward in risky regions. Because upward pressure could become excessive overestimation, they add a correction term: the target is adjusted based on how far the previous estimate was from the true value, and a balancing factor β is derived (Proposition 4.1) that increases when the estimate is too low and decreases when it is too high. Since the true optimal value is unknown in practice, it is approximated by the cumulative discounted cost of trajectories sampled by the current policy.

Memory is only useful if it describes the policy currently being trained, so the whole objective is wrapped in a trust region: the updated policy is constrained by a KL-divergence bound to stay near the policy that generated the stored unsafe samples. The resulting constrained optimization problem is solved in two ways, giving MICE-CPO and MICE-PIDLag.

Experiments run for 10^7 training time steps with a maximum trajectory length of 1000 steps, using 6 random seeds per method, with results reported as mean and variance.

Why This Matters

Impact on research. The paper reframes constraint violations in CRL as an estimation-bias problem rather than purely a policy-optimization problem, and connects two normally separate literatures: estimation-bias control in RL (Double Q-learning, TD3, Maxmin Q-learning, Balanced Q-learning) and intrinsic-reward exploration (NGU, count-based bonuses). It also reverses the usual direction of intrinsic signals — intrinsic rewards encourage exploration, whereas intrinsic costs here discourage it. The theoretical results give a worst-case constraint violation bound and a convergence guarantee, which most bias-control heuristics lack.

Real-world applications.

• Robotics: training manipulators or mobile robots where the "cost" represents collisions, joint-limit violations, or damage to hardware.
• Autonomous driving: learning driving policies where cost corresponds to lane departures, near-misses, or hard braking events, and where violations during training are unacceptable even in simulation-to-real transfer.
• Industrial control and power systems: operating policies that must keep temperature, pressure, or voltage within hard limits.
• Healthcare and resource allocation: sequential decision policies where safety constraints (dosage limits, budget ceilings) must hold during the learning phase, not just at convergence.

Industry relevance. Systems that must be trained in simulation before deployment (robotics, autonomous vehicles, energy management) suffer whenever the training policy violates constraints, because violations translate into unsafe rollouts, wasted simulator budget, or failed safety certification. A method that keeps constraint violations near zero throughout training, while matching baseline returns, directly reduces the cost and risk of the training pipeline — and the released code lowers the barrier to trying it. It also reduces the need to trade task performance for conservatism, which is the usual practical compromise.

Future Directions

• Scaling to more complex tasks. The authors state that extended experiments on more complex tasks are in the appendix; how MICE behaves as state dimensionality and hazard density grow is a natural open question, particularly given that the random projection layer is justified by approximate distance preservation.

• Memory management over long horizons. The memory has a dynamically adjusted capacity and stores unsafe samples from the previous iteration to stay aligned with the current policy. How to size and refresh this memory in non-stationary or very long-horizon tasks is unresolved.

• Tuning the intrinsic factor and k. The balancing factor β is derived theoretically but depends on estimating the optimal value Q*, which is approximated empirically. The paper notes that larger k improves safety at higher computational cost and fixes k = 10 across all environments; principled, adaptive choices of k and β remain open.

• Extension beyond the two solver variants. MICE is instantiated as MICE-CPO and MICE-PIDLag. Whether the extrinsic-intrinsic cost function can be plugged into other primal or primal-dual CRL algorithms, and how the constraint bound behaves there, is untested.

• Bias control in the reward critic. The paper focuses on the cost critic's underestimation. Whether reward-side overestimation interacts with the intrinsic-cost correction, and whether bias should be controlled jointly across both critics, is not addressed.

Target Audience

Researchers and graduate students working on safe RL, constrained MDPs, or trust-region policy optimization who already understand actor-critic methods and Lagrangian duality. It is also relevant to applied researchers and engineers in robotics, autonomous driving, and industrial control who need training-time constraint satisfaction rather than only asymptotic feasibility, and who want to understand why their constrained RL agents violate constraints mid-training. Readers without a background in CMDPs, Bellman operators, and KL-divergence trust regions will find the methodology and theoretical sections difficult, though the core intuition — agents underestimate danger, so give them a memory of past danger — is accessible to a general machine learning audience.

Authors’ abstract

Constrained Reinforcement Learning (CRL) aims to maximize cumulative rewards while satisfying constraints. However, existing CRL algorithms often encounter significant constraint violations during training, limiting their applicability in safety-critical scenarios. In this paper, we identify the underestimation of the cost value function as a key factor contributing to these violations. To address this issue, we propose the Memory-driven Intrinsic Cost Estimation (MICE) method, which introduces intrinsic costs to mitigate underestimation and control bias to promote safer exploration. Inspired by flashbulb memory, where humans vividly recall dangerous experiences to avoid risks, MICE constructs a memory module that stores previously explored unsafe states to identify high-cost regions. The intrinsic cost is formulated as the pseudo-count of the current state visiting these risk regions. Furthermore, we propose an extrinsic-intrinsic cost value function that incorporates intrinsic costs and adopts a bias correction strategy. Using this function, we formulate an optimization objective within the trust region, along with corresponding optimization methods. Theoretically, we provide convergence guarantees for the proposed cost value function and establish the worst-case constraint violation for the MICE update. Extensive experiments demonstrate that MICE significantly reduces constraint violations while preserving policy performance comparable to baselines.