Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Authors: Shiqing Gao
Jiaxin Ding
Luoyi Fu
Xinbing Wang
Venue: ICML 2025 oral (2025)
Keywords: constrained RL
safe exploration
underestimation
intrinsic cost
Primary area: reinforcement_learning

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.

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Shiqing Gao
Jiaxin Ding'
Luoyi Fu'
Xinbing Wang'
Abstract
with safety requirements (Stooke et al., 2020; Xu al., 2021; Yang et al., 2022; Gao et al., 2024), such as robotics (Tang et al., 2024) and autonomous driving (Zhang et al., 2024), by integrating constraints into Reinforcement Learn- ing (RL) policy optimization. However, existing CRL meth- ods often exhibit persistent constraint violations during pol- iey training (Sootla al., 2022a;b), undermining their relia- bility in real-world deployments.
Constrained Reinforcement Learning (CRL) aims to maximize cumulative rewards while satisfy- ing constraints. However, existing CRL algo- rithms often encounter significant constraint vi- olations during training, limiting their applica- bility in safety-critical scenarios. In this paper. we identify the underestimation of the cost value function as a key factor contributing to these vi- olations. To address this issue. we propose the Memory-driven Intrinsic Cost Estimation (MICE) method, which introduces intrinsic costs to miti- gate underestimation and control bias to promote safer exploration. Inspired by flashbulb memory, where humans vividly recall dangerous experi- ences to avoid risks, MICE constructs a mem- ory module that stores previously explored unsafe states to identify high-cost regions. The intrinsic cost is formulated as the pseudo-count of the cur- rent state visiting these risk regions. Furthermore, we propose an extrinsic-intrins cost value func- tion 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 opti- mization methods. Theoretically, provide con- vergence guarantees for the proposed cost value function and establish the worst-case constraint violation for the MICE update. Extensive exper- iments demonstrate that MICE significantly re- duces constraint violations while preserving pol- icy performance comparable to baselines.
A key factor driving constraint violations is the underestima- tion of the cost value. In CRI,, unsafe high-cost regions pose the risk of constraint violations, prompting policy updates to reduce the cost value. However, the inherent noise in function approximation disrupts the zero-mean assumption under minimization objective (Thrun & Schwartz, 2014), resulting in cost underestimation. Consequently, high-cost states may appear deceptively safe, enticing the agent to ex- plore them for potentially high rewards. This underestima- tion leads to frequent constraint violations during training, even when an optimal safe policy theoretically exists.
Although biases in cost estimation are generally undesir- able, they not inherently detrimental and can enhance policy learning and exploration in certain scenarios (Lan et al., 2020; Karimpanal et al., 2023). Underestimation gen- erally encourages exploration, while overestimation tends to discourage exploration. Specifically, in high-cost regions, overestimation can help prevent unsafe exploration to re- duce risks, whereas underestimation may induce excessive exploration of unsafe states. Therefore, the key challenge to shape cost estimation to mitigate harmful underestimation in high-cost regions while ensuring safe exploration without being overly conservative.
To address this challenge, we propose the Memory-driven Intrinsic Cost Estimation (MICE) algorithm, integrating ex- trinsic and intrinsic cost value updates to mitigate underesti- mation while exploiting controlled bias for safer exploration. Inspired by flashbulb memory (Conway, 2013), where hu- mans vividly recall significant experiences to avoid risks, we equip agents with a flashbulb memory module that stores previously explored unsafe states, enabling the identification of high-cost regions. The intrinsic cost is derived from the flashbulb memory, formulated as the pseudo-count (Badia et al., 2020) of the current state visiting high-cost regions in
1. Introduction
Constrained Reinforcement Learning (CRL) has become powerful framework for addressing makision tasks
'Shanghai Jiao Tong University, Shanghai, China. Correspon- dence to: Jiaxin Ding <jiaxinding @ edu.c'..d
Proceedings of the nrnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
memory. Then we introduce an extrinsic-intrinsic cost value update that mitigates underestimation by augmenting ex- trinsic cost estimates in high-cost regions, with a balancing factor to correct excessive bias. Further, we propose an op- timization objective within the trust region, ensuring align- ment between the updated policy and the policy generating the flashbulb memory samples. We also provide correspond- ing solution methods for this objective. Theoretically, we establish constraint bound for the extrinsic-intrinss cost value function and provide a worst-case constraint violation under the MICE update, ensuring minimal constraint viola- tions during training. Additionally, we prove convergence guarantees for the proposed cost value function. Extensive experiments demonstrate that MICE significantly reduces constraint violations while ensuring robust policy perfor- mance. Our contributions are summarized as follows:
ever, both primal and primal-dual methods often encounter significant constraint violations during training, primarily due to the underestimation of cost value. To address this, we propose a memory-driver drivvn intrinsic cost to correct under- estimation with a convergence guarantee, ensuring minimal constraint violations while maintaining performance.
Overestimation in RL. Overestimation in RL has been extensively studied. Double Q-learning (Hasselt, 2010) and Double DQN ( (Van Hasselt et al., 2016) reduce bias by us- ing separate target value functions, avoiding maximization- induced errors. However, in actor-critic frameworks, the slow-changing policy keeps current and target values close, failing to fully eliminate maximization bias. TD3 (Fuji- moto et al., 2018) addresses this by using pair of critics and selecting the minimum value. AdaEE (Wang et al., 2021) employs an ensemble-based method, adjusting the ensemble size based on Q-value approximation error to mitigate overestimation. Notably, overestimation and un- derestimation biases can be beneficial in certain scenarios. Methods like Maxmin Q-learning (Lan al., 2020) and Balanced Q-learning (Karimpanal et al., 2023) focus on controlling estimation bias to enhance learning. In this pa- per, we demonstrate that underestimation of the cost value causes constraint violations during training and introduce the intrinsic cost to mitigate underestimation, controlling bias for safer exploration.
We introduce a novel Flashbulb Memory mechanism that records high-cost regions, enabling the derivation of an intrinsic cost to effectively mitigate the prevalent underestimation in these regions.
We propose Extrinsic-Intrinsic Cost Value Update that incorporates the intrinsic cost estimate and applies a bias correction strategy, ensuring more robust cost estimation and safer exploration in high-cost regions.
We provide a theoretical analysis with convergence guarantees and constraint violation bounds, along with practical optimization methods that demonstrate signif- icant improvements in constraint satisfaction and pol- icy performance through extensive experiments. The code for this paper is available https: //github. com/ Shi Sthiginngao/MMi.
Intrinsic reward. Intrinsic rewards in RL are typically used to enhance exploration, falling into two categories: en- couraging exploration of novel states (Zhang et al., 2021; Seo et al., 2021), and reducing prediction errors or uncer- tainties improve environmental understanding (Sharma et al., 2019; Laskin al., 2022). Count-based methods (Strehl & Littman, 2008; Badia et al., 2020) use state visit counts as bonus rewards to encourage the exploration of new states. (Lipton et al., 2016) indicates that agents tend to periodically revisit states under new policies after forgetting them, introducing an intrinsic fear model to prevent periodic catastrophes. In CRL, ROSARL (Tasse al., 2023) inter- prets constraints as intrinsic rewards, optimizing policies by assigning minimal penalties to unsafe states. This paper introduces intrinsic costs to enhance safer exploration, par- ticularly when extrinsic costs are underestimated. Memory- driven intrinsic costs provide anticipatory signals, guiding policy updates to avoid revisiting high-cost regions.
2. Related Work
CRL methods. CRL optimization methods can be classi- fied into primal-dual and primal approaches. Primal-dual methods (Ding et al., 2021; Ying et al., 2024) convert con- strained problems into unconstrained ones via dual variables. NPG-PD (Ding et al., 2020) guarantees global convergence with sublinear rates. PID Lagrangian (Stooke et al., 2020) introduces proportional and differential control to mitigate cost overshoot and oscillations. However, primal-dual ap- proaches are sensitive to initial parameters, limiting their application (Zhang et al., 2022). In contrast, primal methods directly optimize constrained problems in the primal space (Zhang et al., 2020; Yu et al., 2022; Gao et al., 2024). CPO (Achiam et al., 2017) enforces performance and constraint violation bounds within a trust region. PCPO ( (Yang et al., 2020) alternates between reward improvement and policy projection into feasible regions. CUP (Yang et al., 2022) provides generalized theoretical guarantees using the gener- alized advantage estimator (Schulman et al., 2015). How-
3. Preliminary
CRL can be modeled as Constrained Markov decision process (CMDP), denoted by a tuple (S, A, R, C, C,P.A P.P. r), where S is the state space, A is the action space, R S x A + RR is the reward function, P: S x A + [0, 1] is the transition probability function, p is the initial state distri-
2

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
bution, and 7 E (0,1) cost function C S x A - R maps state-action pairs to extrinsic costs c,, which are task-specific costs provided by the environment. The intrinsic cost is denoted as c', and d denotes the constraints threshold.
1) is the discount factor. The extrinsic
Qc(s, a)], where is the step size. Assuming that value estimates contain zero-mean noise c, consistent under- estimation bias is induced by minimizing the noisy value estimate Qc a') + c. The zero-mean property of noise is disrupted after minimization, resulting in the minimized value estimate being generally smaller than the true mini- mum (Thrun & Schwartz, 2014):
Starting from an initial state so sampled from the initial state distribution p. the agent perceives the state st from the envi- ronment at each time step t, selects an action a according to the policy π. S - A, receives the reward r2 (s, dt) and extrinsic cost of, and transfers to the next state 11+1 based on P(st+1|se 1s,, az). The set of all stationary policies is denoted as II. The discounted future state visitation dis- tribution is defined as ds)(s) == (1 7) Ei= P(s, = s| The value function for a policy π is (s) == B 2 R(sr, [s) sg = s}. and action-value function is (s) == E, 1E=0 R(s,, as) s, du a].
E. [min Qc(s' ,a)) + S min Qc(s', a')
(2)
Such noise is inherent in function approximation methods (Fujimoto et al., 2018).
In actor-critic-based CRL methods, the policy learns from value estimation provided by the approximate reward critic and cost critic. When constraints are violated, the policy is updated with a policy gradient that minimizes the expected cost value estimate: arg minxen,, "es-d=,a-n [Qa(s, a)}. where II, represents the policy set parameterized by B. Denote the true cost value function as Q2 a) and the approximate cost value function as Qc(s, a). Updated from the current policy (-10)) with deterministic policy gradient, let i be the policy derived from the true cost value (s, a), and the policy derived from the approx- imate cost value Qc a). According to TD3 (Fujimoto et al., 2018), when the approximation introduces bias such that E[Qc(s, (s))] S EiQa(s, ((s)]] due to unavoidable noise in the function approximation, then the cost value is underestimated under the updated policy ň within suffi- ciently small step size:
The advantage function measures the advantage of action over the mean value: A8 == (s. VV
The cost value function (s), cost action value function (Z,s,, a) and cost advantage function (5, a) in CMDP can be obtained as in MDP by replacing the reward r with the cost c. The expected discounted return Jπ(T)= := E EE== R(s,, ae)], and the expected cumulative dis- counted cost Jc( := Ea IEt= 7 CC(s, at)]. where T= 7($so, $1, 01,'" :) .) is the trajectory under æ.
The CRL aims to find an optimal policy by maximizing the expected discounted return over the set of feasible policies Te = { e II: JJ(T)) S d):
arg (RT) TEll
s.t. Jc(x) d
Elêc(s, (s))) (s
4. Methodology
To validate the presence of underestimation bias, pare the estimated cost value for various states against their corresponding true values in both the primal method CPO (Achiam et al., 2017) and the primal-dual method PID La- grangian (Stooke et al., 2020). The true values are computed by averaging the cumulative discounted costs over 1, 000 episodes under the current policy. Results in Figure 2 show that cost value functions in different CRL methods con- sistently and significantly underestimated across various environments during training.
In this section, we introduce the MICE algorithm. We first present the underestimation in the CRL cost value fune- tion. Then we introduce the flashbulb memory mechanism for recording high-cost regions, and derive the intrinsic cost to correct underestimation. Finally, we propose an extrinsic-intrinsic update formulation for MICE and a new optimization objective with its solutions.
4.1. Underestimate Bias in Cost Value Function
Compared to overestimation in RL, underestimation in CRL can have more detrimental impacts, as directly leads to unsafe actions that violate constraints. When the cost critic underestimates the true cost, actions with high rewards but violating constraints mistakenly perceived safe, caus- ing these unsafe actions to be selected. Then these actions are propagated through the Bellman equation, accumulat- ing bias and generating increasingly unsafe policies. This explains the frequent constraint violations observed during training in various CRL. methods.
Overestimation in RL arises from the tendency of the value function update to greedily select high value actions, result- ing in estimates exceeding the optimal value (Fujimoto et al., 2018). Conversely, the cost value function in CRL exhibits underestimation, particularly during constraint violations, due to the inherent tendency to minimize costs.
In methods like Q-learning, the cost value function is updated using a greedy strategy during constraint viola- tions: Qc(8. a) < Qc(s, () + afc+ + mina' Qc(s', (o')
3

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
record high-cust regions
trust region
true value Q
Hazards
Flashbulb Memory
k-nearest neighbors
Goal
High-cost region
M: (=""(s
N
high-cost region
mitigate underestimation in high-cost regions
c
pseudo-coum for St
QC
balancing factor B
St
HD
Critic
f(++
t Actor
environment
Random Projection f
B
Memory-driven Intrinsic Cost
MICE Policy Optimization
Figure I: Structure of MICE. Underestimation cost value in high-cost regions causes constraint violations. The Flashbulb Memory records high-cost regions by storing previously explored unsafe states. The intrinsic cost computed through the pseudo-count of the current state's visit high-cost regions in memory. The trust region ensures the alignment of the stored high-cost regions with the current policy. The extrinsic-intrines cost critic mitigates underestimation in high-cost regions.
Underastimaton in Seree-Ca
Uscersed medtess 1abep-oottieee--0
matrix (Zhu et al., 2020). By the Johnson Lindenstrauss lemma (Johnson et al., 1984), this mapping approximately maintains relative Fuclidean distances the original space. The memory, with dynamically adjusted capacity, stores unsafe samples collected by the policy from the previous iteration. By mirroring the human tendency to prioritize recent high-risk experiences, this design ensures that the memory remains aligned with the current policy.
CPO
CPO
Figure 2: Underestimation bias across environments. The x- axis is time steps, the y-axis is the cost value estimate minus the true value, and the dashed line is the zero deviation.
The intrinsic cost с' is derived from the flashbulb mem- ory. By comparing the current state 8N with states stored in memory, smaller differences indicate higher similar- ity to prior unsafe experiences, signaling an increased risk of constraint violations and resulting in higher in- trinsic cost c/. Denote the flashbulb memory M (J(*)"),... ","")),, where *!" is the i-th unsafe state. Inspired by pereticalll-justiffie exploration methods that convert state- action counts into bonus rewards (Strehl & Littman, 2008), the intrinsic cost of at time is generated by comparing the current embedding state f(()) with those in memory M:
4.2. Intrinsic Cost Generated from Flashbulb Memory
Risk awareness enables humans to identify potential dan- gers and adopt conservative behaviors to ensure safety. Hu- mans are impressed by previous risky experiences, which vividly recalled to avoid danger in similar scenarios. However, CRL agents with underestimated critics often fail to recognize the consequences of unsafe actions, lead- ing to constraint violations. Inspired by human cognitive mechanisms, we introduce a memory-driven intrinsic cost mechanism to enhance the agent's 's risk awareness. This in- trinsic cost discourages repeated visits to unsafe states while promoting safer exploration.
df
Σ {(I(s)).((F)) STONN
(4)
Drawing inspiration from NGU (Badia et al., 2020), the sum of the similarities, computed using a kernel function K, is used to represent the pseudo-count of the current state s, visiting high-cost regions in memory. This sum is approximated by the k-nearest neighbors N₂. of f(x) in M. The kernel function is:
We construct flashbulb memory M to record high-cost regions by storing unsafe states " with positive extrinsic costs. To reduce dimensionality while approximately pre- serving inter-sample distances, each state is embedded into a divee--imensional latent space f()) using a random projection layer f. implemented with Gaussian random
E
K K(I, v) [( y) +
(5)

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
where / is the Euclidean distance, and & is a small constant for numerical stability (set to 10-3 following NGU). To preserve training stability, the intrinsic cost is normalized. A larger visit count for indicates a higher probability that it resides in a high-cost region, thus resulting in a greater intrinsic cost.
excessive underestimation. Conversely, when On Q- 0, QT.,. is adjusted downward, introducing negative bias to address excessive overestimation. Then we derive the balancing intrinsic factor & to control the estimation bias.
Proposition 4.1. For a transition (8, a, c ce, 8') in a CMDP, where the n-th update of the extrinsic-intrins cost value Qn corresponds to the n-th update target Qr,, the modified target for the (n + 1)-th update is Qr,,12' the balancing intrinsic factor 3 for the (n + 1)-th update is given by:
4.3. Safety Policy Optimization with the Intrinsic Cost
The standard cost value function Qo(8, a) in CRL is up- dated using only extrinsic costs c Qc(s,a) = (1 a) a)Qc(s, a) + afcf + (Qo(s, d'))). To mitigate un- derestimation, we propose an cutrinsic-intrinsie cost value function @ (s,a),, a), which incorporates memory-driven in- trinsic costs cf and task-driven extrinsic costs cft:
B' -maa (B (B))
d>0
(8)
where 6n Qn Q" is the n-th update estimation bias, E (0, 1) is the saacouut,factoo
The derivation process is provided in Appendix B.2.
0 2 (8, a) (1 (11 (s.a)
(6)
The direction of the update depends solely on 6.-- When En < O, indicating underestimation of Qn. 8' is increased to raise the intrinsic cost and mitigate underestimation. When en > O, indicating overestimation of Qn. 3 is decreased, reducing the intrinsic cost to mitigate overestimation. The discount factor is used to ensure the convergence of the value function, with the convergence analysis in Theorem 4.5. By leveraging the estimated bias from the previous update, we iteratively refine the intrinsic factor to control the estimated bias of the current value function.
+ +a(c + Bc' + tEx 10 a'))
where is the step size, is the intrinsic factor. Starting from the same initialization, ( 2 Qc(s, a) for the same state-action pair, as the target QT = cº + Bc + (s',
7LE (s', a')] for QE' incorporates the intrinsic cost, resulting in a larger target compared to the standard cost estimate. By augmenting the agent's 's memory, the extrinsic- intrinsic target cost value increases the cost estimate, effec- tively mitigating underestimation in high-cost regions.
In practical implementation, since the optimal value Q' is unknown, we approximate it by computing the cumulative discounted cost along trajectories sampled by the current policy, following (Wang et al., 2021; Fujimoto et al., 2018).
Overestimation and underestimation biases in cost value are not inherently detrimental, their impact depends on the current state (Lan et al., 2020), with detailed analysis in Appendix B.I. Generally, underestimation bias encourages exploration, while overestimation bias tends to discourage exploration. In high-cost regions with a high risk of con- straint violation, overestimation bias can be beneficial by discouraging unsafe exploration, while underestimation bias may lead to over-exploration of these unsafe regions.
Based on the extrinsic-intrinsic cost value function, the cumulative discounted extrinsic-intrinsie cost is defined as:
JØ =- : ETTE Σ FC az)
(9)
In this work, flashbulb memory is employed to identify previously explored high-cost regions, with intrinsic cost quantifying the pseudo-coum of the current state visiting these regions. Higher intrinsic costs signal greater likeli- hood of entering a high-cost region, potentially introducing overestimation to discourage unsafe explorations. Addition- ally, the propagation of overestimation through cost value updates is limited, as the policy tends to avoid actions with large cost estimates (Fujimoto et al., 2018).
where (st, a.) = of + Bee is the extrinsic-intrinsic cost function. The extrinsic-intrinsic advantage function in MICE is defined as: A (5. = E. + +>Voss)) (o(s)]. To minimize constraint violations, we replace the standard constraint Jc with the extrinsic-intrinse constraint J& in the optimization objective. To facilitate optimization, we give the difference in expectation constraint between ixtrinsic-intrinsic J (xr') extrinsic Je(x).
Lemma 4.2. Given arbitrary two policies and n', the difference in expectation constraint of extrinsic-intrnsic J (x') and extrinsic Jc(x) is expressed as:
To avoid excessive estimate bias, we propose an adaptive bias correction mechanism. The target for the (n 1)-th update Qraf1 is modified as:
80
J - -c'))Jc(m)) = Er/tr
Σ
2d A'AA A A ar/T))
(10)
Q = Qr...
-
(7)
1=0
where Q" is the optimal value, Qn is the estimate at the n-th update. When Qn - Q' < 0, the modified target Qr,,, adjusted upward, introducing positive bias to mitigate
where AET (sc: azlz)) = ICF + Bct + (V8
V (s))). The expectation is over trajectories T, with E indicating that actions are sampled from n¹ to generate T.
5

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
proof is provided in Appendix B.3.
two policies results in larger upper bound on the constraint gap. This theorem supports the optimization objective 12 within the trust region in MICE.
According to Equation 10, present the optimization ob- jective of MICE:
By mitigating the underestimation, the MICE algorithm sig- nificantly reduces constraint violations during the learning process. We further establish a theoretical upper bound on the constraint violation for the updated policy within the MICE optimization framework:
Th+1- = arg max Regnd" awx [A (8, a)] xello
s.t. (T((T)) 1 Bondt ann [AO (s, a|Txa]] S d
(11)
To ensure that the unsafe states stored in memory remain rel- evant to the updated policy n, we further propose a surrogate objective within the trust region:
Theorem 4.4 (MICE Update Worst-Case Constraint Vio- lation). Suppose The Th+1 are related by the optimization objective 12. upper bound the constraint of the up- dated policy th+1 is:
Th+1 = arg max Es -0- R (s, a)] TElle
Jo( sd- V20icO Tut1
(14)
s.l. Jo(Tx) + 1-7 B Band a~
aan (A (8, m/m) s d,
(1 (1-
[(=[(Ta) &
where 6O Tk-1 == max, [ [A (s, a)], and I
(12) where (+) Bandrx B [+])(s]])))s and DR is the KL divergence. 4p > is the trust region size, and the set { II. (TT]] (k) S }p} defines the trust region.
E, Erjree1 1 1 Bcl].
A proof is provided in Appendix B.4.
Theorem 4.4 demonstrates that our method achieves a tighter upper bound on constraint violation compared to CPO, guar- anteeing that the updated policy in MICE has lower proba- bility of exceeding the constraint threshold.
The trust region constrains the updated policy æ to remain close to the previously sampled policy тR- This alignment preserves the relevance of unsafe states stored in memory, ensuring that the identified high-cost regions adequately cover the sampling space of the updated policy æ. Conse- quently, the intrinsic cost more accurately reflects the risk of the updated policy visiting these high-cost regions, ef- fectively mitigating underestimation and promoting safer exploration in unsafe regions.
Based on similar assumptions as in TD3 and Double Q- learning, we give convergence guarantees of the extrinsic- intrinsic cost value function.
Theorem 4.5 (Convergence Analysis). Given following conditions:
To solve the optimization objective 12, we propose the MICE-CPO and MICE-PIDLag optimization methods, as detailed in Appendix A.
Each state-action pair is sampled an infinite number of times.
2. The MDP is finite.
4.4. Theoretical Analysis
3. 7 E (0,1).
Theoretically, we establish an upper bound on the difference in the expected extrinsic-intrinsic constraint between arbitrary policies.
4. Q values are stored in a lookup table.
5. Q receives an infinite number of updates.
Theorem 4.3 (Extrinsic-intrinscc Constraint Bounds). For arbitrary two policies x'' and x, the following bound for the expected extrinsic-intrines constraint holds:
6. The learning rates satisfy ar(s, a) E, cc. E,(ar(s,)) a))² oo with proba- bility 1, ar(s,a) (s, & (8,, dr).
[0,1] 1),
Je (x') - (T)
EI Drv(T(1())
7. Varla + Bcl] < Vs,
E Bxnd 'ana'
AE (s, +
1- D
(13)
The extrinsic-intrinsic QE! will converge to the optimal Q7: with probability 1.
where EE! = max, Eawr' [AE' (s, a|T]]] the TV.
divergence Drv (~'l (1/2) E. nt (als) (als))]
The proof is in Appendix B.5.
The proof is provided in Appendix B.4.
Theorem 4.5 ensures that MICE converges to the optimal solution, which guarantees policy performance while satis- fying constraints.
The upper bound in Theorem 4.3 is associated with the TV divergence between and x'_ larger divergence between
6

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
SaledyCa Goaf1-40
SaketCarrCrdee-.00
Safio
20
103m
0.2
06
0.2
0.4
0.2
06
10
1e7
Salidy Car Gool1-40
20
107
107
MICE CUP
PIDLag
Saute
Simmer
Figure 3: Comparison of MICE to baselines on Safety Gym. The x-axis the total number of training steps, the y-axis is the average return constraint. The solid line is the mean and the shaded area is the standard deviation. The dashed line is the constraint threshold which is 25.
5. Experiment
Performance and Constraint. Figure 3 presents the learn- ing curves for MICE and baselines in Safety Gym. The first row shows the cumulative discounted reward during training, and the second row is the cumulative discounted cost, with the black dashed line indicating the cost thresh- old. The results indicate that MICE significantly reduces constraint violations while maintaining superior similar policy performance to baselines. Notably, in the Goall nav- igation tasks with multiple hazards, MICE enhances policy performance while maintaining constraint satisfaction, as its intrinsic cost provides predictive signals to avoid haz- ards and encourage safe exploration. In Safety MuJoCo, as shown in Figure MICE consistently maintains zero constraint violations throughout training, with convergence speed comparable to or faster than baselines. MICE matches the constraint satisfaction levels of Saute and SimmerPID, which emphasize zero constraint violations, while surpass- ing them in policy performance. In HalfCheetah Veloccit PIDLag exceeds the constraint threshold, thus its higher return compared to MICE does not indicate better pol- icy. Extended experiments covering more complex tasks are provided in Appendix C.3.2. The results demonstrate that MICE continues to achieve superior constraint satisfac- tion while maintaining policy performance in these more challenging scenarios.
The experiments address the following questions: 1) Does MICE reduce constraint violations while maintaining policy performance compared to baselines? 2) Does the intrin- sic cost component effectively mitigate underestimation? Basclines include the primal-dual PID Lagrangian method (Stooke et al., 2020), the primal CUP method (Yang al., 2022), and state augmentation methods Saute (Sootla al., 2022a) and Simmer (Sootla et al., 2022b) focusing on zero constraint violations. Results for additional basclines are provided in the Appendix C.
We implemented both MICE-CPO and MICE-PIDLag, with optimization details provided in Appendix A. All experi- ments followed uniform conditions to ensure fairness and reproducibility, with a total of 10" training time steps and maximum trajectory length of 1000 steps. To reduce ran- domness, 6 random seeds were used for each method, and the results are presented as mean and variance. The algo- rithm process is provided in Appendix C.I, and additional experiments are presented in Appendix C.3.
Environments Description. Experiments were conducted across four navigation tasks in Safety Gym (Ji et al., 2023) and four MuJoCo physical simulator tasks (Todorov et al., 2012), as detailed in Appendix C.4. All tasks aim to max- imize expected reward (higher is better) while satisfying constraints (below threshold). In Safety Gym, we train Point and Car agents on navigation tasks, including the Goal task (navigate to a goal while avoiding hazards) and the Circle task (go around a circle's 's center without crossing boundaries). In Safety MuJoCo, agents are rewarded for running along a straight path with a velocity limit for safety.
Estimation Bias in MICE. To validate the effectiveness of the intrinsic cost MICE for mitigating estimation bias, compare the difference between estimated and true cost values across MICE and baselines. True values are com- puted as the average cumulative discounted cost over 1, 000 episodes under the current policy. Figure 5 shows that the estimated values in MICE are significantly higher than those of the baselines, indicating that the intrinsic cost effectively
7

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
3000
0X00
5000
1006
1000
5000
1000
2000
1000
0.5
244
0.2
6.6
0.5
0.2
06
10
Suflotykut//dookyy-44
Sulktyhumano dVllocity-
Solutyhoopee httphhoppp//V/llll--aa
117
147
MICE CUP
PIDLag Saute
Simmer
Figure 4: Comparison of MICE to baselines on Safety MuJoCo. The x-axis is the total number of training steps, the y-axis the average return constraint. The solid line is the mean and the shaded area is the standard deviation. The dashed line in the cost plot is the constraint threshold which is 25.
Exieeade FadieefartGGoee-od
Extimaaee Pain 1i
Extirade Bivs Coall
SafeeyCa
MCF
MB:F
690
RBB AM
Catractin Ente
Eatrutan Ener
PELLag MICE
20
MIZE
-10
0.2
0.9
005
022
0.9
100
1.4
08
08
02
0.4
0.5
Figure 5: Validation experiments of mitigating underestimation with MICE. The y-axis is the cost value estimate minus the true value, and the dashed line is the zero deviation.
mitigates underestimation. Meanwhile, the estimation bias in MICE approaches zero, confirming that the balancing factor B in MICE can effectively correct estimation bias. Furthermore, the extrinsic-intrinsic cost value function in MICE gradually converges to the true value, supporting the convergence analysis in Theorem 4.5. Additionally, we com- pare the TD3-based cost value function with that of MICE in mitigating constraint bias, showing that the intrinsic cost component in MICE more accurately mitigates underestima- tion, resulting in improved constraint satisfaction and policy performance, as detailed in Appendix C.3.3.
introducing conservatism. Instead, it is derived from the count of visits to high-regions stored in memory, effectively mitigating underestimation in high-regions and promoting safer exploration. Our method is theoretically and empir- ically proven converge to the optimal value, while the constant-based approach lacks such guarantees, leading to suboptimal policy performance. Additionally, we perform an ablation study on the random projection layer in MICE to validate its effectiveness. The results show that it signifi- cantly reduces computational complexity without degrading policy performance or increasing constraint violations, as detailed in Appendix C.3.4.
Ablation Study of Intrinsic Cost. To verify that memory- driven intrinsic cost enhances policy learning, we conduct an ablation study where the intrinsic cost in MICE is re- placed by fixed constants (3, 5, 15). Figure 6a and 6b show that introducing fixed constants results in decreased pol- more
Robustness to Constraint Thresholds. Sensitivity analy- sis experiments are conducted in SafetyPointGoall-v0 with thresholds of 0, 15, and 25, as illustrated in Figure 6c and 6d. The results show that MICE adapts effectively to vary- ing constraint requirements. With a threshold of 15, MICE achieves a balance between performance and constraint sat- isfaction. Under the strict threshold of O, MICE enforces compliance, ensuring the policy adheres to constraints.
icy performance. Notably, constraint violations frequent with constant 5 compared to 3, indicating that simply adding a larger value to the cost estimate does not necessarily reduce constraint violations. MICE achieves the best performance, demonstrating that the intrinsic cost in MICE does not merely ensure constraint satisfaction by
8

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
oMation Sulocyo
Ablation SalkyPoinnEaattIC
Limit Sensibiity in SutiogaainBoaatt00
Limit Sensibity Safoey Parnt
15
1806
0.2
04
05
10
D44 055
10
0.6
hor
(c) Return of Sensitivity Figure 6: (a) Ablation study of extrinsic-intrinsi cost value in MICE, comparing MICE with variants that remove the intrinsic cost and add fixed constants to the cost value function. (c) Robustness of MICE to different cost thresholds
(a) Return of Ablation
(b) Constraint of Ablation
(d) Constraint of Sensitivity
Safedy Car G0a81-40
SaletyCarCrdee--00
SalioyFainBBoltt-0000
20
1000
13
0.2
04
0.2
06
10
0.2
0.4
0.2
06
10
Salety Gool1-40
CaletyCarCeeeeteee Cirdle-vV
SulddyFairtGodd 1-10
20.5
Caretess
31.2
7:5
107
Figure 7: Sensitivity analysis of MICE algorithm for the number of nearest neighbors & in KNN, showing that increasing A enhances the safety of the policy but also raises computational overhead. We uniformly set l 10 across all environments to balance safety, performance, and computational efficiency.
Sensitivity Analysis of Hyperparameters. To evaluate the sensitivity of the number of nearest neighbors k in KNN, we varied & across multiple environments and analyzed its impact, as shown in Figure 7. The results indicate that in- creasing enhances policy safety by incorporating more unsafe states from memory, but also raises computational overhead. Conversely, smaller k may result in insufficient leveraging of unsafe state information, potentially leading to higher constraint violations. In this paper, we uniformly set k = 10 across all environments to balance safety, perfor- mance, and computational efficiency.
algorithm. Extensive experimental results demonstrate that MICE effectively reduces constraint violations while main- taining robust policy performance.
The MICE framework exhibits strong applicability across diverse tasks. For example, the criterion for adding states to the flashbulb memory can be flexibly adjusted. In our experiments, we adopt a rule based whether the extrinsic cost of a state is greater than zero, where extrinsic costs are directly provided by the environment without noise. How- ever, in real-world applications, extrinsic costs may be noisy and may not accurately reflect the true cost of a given state. A practical alternative is to employ the expected cumula- tive cost as the criterion for memory inclusion: state is stored if its expected cumulative cost exceeds predefined threshold. By aggregating information across multiple fu- ture timesteps, this approach effectively mitigates the influ- ence of individual outlier values. Additionally, in domains such as autonomous driving, the expense of sampling unsafe states is prohibitively high. In these scenarios, the memory can be constructed using offline datasets to ensure safety and feasibility, with techniques such importance resampling employed to correct for potential distributional shifts.
6. Discussion and Conclusion
This paper addresses important challenge in CRL, the underestimation of the cost value, which significantly con- tributes to constraint violations. To mitigate this issue, we propose the MICE algorithm, which incorporates an extrinsic-intrinsic cost value update mechanism inspired by human cognitive processes. MICE enhances the cost esti- mates of high-cost regions, encouraging safer exploration. Theoretically, we provide an upper bound on constraint vio- lations and establish convergence guarantees of the MICE

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Acknowledgment
Ji, J., Zhang, B., Zhou, J., Pan, X., Huang, W., Sun, R., Geng, Y., Zhong, Y., Dai, J., and Yang. Y. Safety gymna- sium: A unified safe reinforcement learning benchmark. Advances in Neural Information Processing Systems, 36, 2023.
This work was supported by NSF China under Grant No. T2421002, 62202299, 62020106005, 62061 146002.
Impact Statement
Johnson, W. B., Lindenstrauss, J., et al. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
This paper presents work whose goal is to advance the field of Reinforcement Learning. By introducing the MICE algo- rithm, we substantially enhance safety during RL training. In real-world applications, MICE can facilitate safer and more efficient deployment of RL in domains such large language models, autonomous driving, and robotics, ulti- mately advancing the field of Machine Learning. There are potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Karimpanal, T. G., Le, H., Abdolshah, M., Rana, S., Gupta, S., Tran, T,, and Venkatesh, S. Balanced q-learning: Combining the influence of optimistic and pessimistic targets. Artificial Intelligence, 325:104021, 2023.
Lan, Q. Pan, Y., Fyshe, A., and White, M. Maxmin q- learning: Controlling the estimation bias of q-learning. arXiv preprint arXiv:2002.0644 2020.
References
Laskin, M., Liu, H., Peng, X. B., Yarats, D., Rajeswaran, A., and Abbeel, P. Unsupervised reinforcement learning with contrastive intrinsic control. Advances in Neural Information Processing Systems, 35:34478-34491, 2022.
Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy optimization. In International conference on ma- chine learning, pp. 22-31, 2017.
Badia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., et al. Never give up: Learning directed exploration strategies. arXiv preprint arXiv:2002.06038, 2020.
Lipton, Z. C., Arizzadeneshelii K., Kumar, A., Li, L., Gao, J., and Deng, L. Combating reinforcement learn- ing's 's sisyphean curse with intrinsic fear. arXiv preprint arXiv: 1.11211111, 2016.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. Openai gym. arXiv preprint 1606.: 5100 2016.
Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. High- figh-ddmeessionl continuous control using generalized advantage estimation. arXiv preprint arXiv: 506.500663. 2015.
Conway, M. Flashbulb memories. Psychology Press, 2013.
Seo, Y., Chen, L., Shin, J., Lee, H., Abbeel, P., and Lee, K. State entropy maximization with random encoders for efficient exploration. In International Conference on Machine Learning, pp. 9443-9454, PMLR, 2021.
Ding, D., Zhang, K., Basar, T., and Jovanovic, Natu- ral policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Informa- tion Processing Systems, 33:8378 8390, 2020.
Sharma, A., Gu, S., Levine, S., Kumar, V., and Hausman, K. Dynamics- aware unsupervised discovery of skills. arXiv preprint 1rXiv:1907.0166 2019.
Ding, D., Wei, X., Yang. Z., Wang, Z., and Jovanovic, M. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pp. 3304 3312, 2021.
Sootla, A., Cowen-Rivers, A. I., Jafferjee, T., Wang, Z.. Mguni, D. H., Wang, J., and Ammar, H. Sauté rl: Almost surely safe reinforcement learning using state augmenta- tion. In International Conference on Machine Learning, pp. 20423-20443, PMLR, 2022a.
Fujimoto, S., Hoof, H., and Meger, D. Addressing function approximation error in actor-critic methods. In Interna- tional conference on machine learning. pp. 1587-1596. PMLR, 2018.
Gao, S., Ding, J., Fu, L., Wang, X., and Zhou, C. Exterior penalty policy optimization with penalty metric network under constraints. In Proceedings of the Thirty-Thin International Joint Conference on Artificial Intelligence, pp. 4007-4015, 2024.
Sootla, A., Cowen- A. I., Wang, J., and Ammar, H. B. Effects of safety state augmentation on safe exploration. arXiv preprint arXiv: 220.0:200000665. 2022b.
Stooke, A., Achiam, J., and Abbeel, P. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference on Machine Learning, pp. 9133- 9143, 2020.
Hasselt, H. Double g-leamiig. Advances in neural informa- tion processing systems, 23, 2010.
10

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Strehl, A. L. and Littman, M. L. An analysis of model- based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309- 1331, 2008.
Zhang, L.,, Shen, L.,, Yang, L.., Chen, S., Yuan, B., Wang, X., and Tao, D. Penalized proximal policy optimiza- tion for safe reinforcement learning. arXiv preprint arXiv:2205. 2022.
Tang, C., Abbatematteo, B., Hu, J., Chandra, R., Martín- Martín, R., and Stone, P. Deep reinforcement learning for robotics: A survey of real-world successes. Annual Review of Control, Robotics, and Autonomous Systems, 8, 2024.
Zhang, T., Rashidinejad, P., Jiao, J., Tian, Y., Gonzalez, J. E.,, and Russell, S. Made: Exploration via maximizing deviation from explored regions. Advances in Neural Information Processing Systems, 34:9663- 9680, 2021.
Zhang, Y., Vuong, Q., and Ross, K. First order constrained optimization in policy space. Advances Neural Infor- mation Processing Systems, 33:15338-1523 2020.
Tasse, G. N., Love, T., Nemecek, M., James, S., and Ros- man, B. Rosarl: Reward-only safe reinforcement learning. arXiv preprint arXiv:2306.00033. 2023.
Zhang, Z., Liu, Q. Li, Y., Lin, K., and Li, L. Safe rein- forcement learning in autonomous driving with epistemic uncertainty estimation. IEEE Transactions on Intelligent Transportation Systems, 2024.
Thrun, S. and Schwartz, A. Issues in using function approx- imation for reinforcement learning. Proceedings of the 1993 connectionist models summer school, pp. 255-263 Psychology Press, 2014.
Zhu, G., Lin, Z., Yang. G., and Zhang, C. Episodic rein- forcement learning with associative memory. 2020.
Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ inter- national conference on intelligent robots and systems, pp. 5026-5033, 2012.
Van Hasselt, H., Guez, A., and Silver, D. Deep reinforce- ment learning with double q-learning. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Wang, H., Lin, S., and Zhang. J. Adaptive ensemble q- learning: Minimizing estimation bias via error feedback. Advances in neural information processing systems, 34: 24778-24790, 2021.
Xu, T., Liang, Y., and Lan, G. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, 11480-11491. PMLR, 2021.
Yang, L., Ji, J., Dai, J., Zhang, L., Zhou, B., Li, P., Yang, Y., and Pan, G. Constrained update projection approach safe policy optimization. Advances in Neural Information Processing Systems, 35:9111-99 1-9124,, 2022.
Yang, T.-Y., Rosca, J., Narasimhan, K., and Ramadge, P. J. Projection- based constrained policy optimization. arXiv preprint arXiv:2010.03152 2020.
Ying, D., Zhang, Y. Ding, Y., Koppel, A., and Lavaei, Scalable primal-dual actor-critic method for safe multi- agent with general utilitics. Advances in Neural Infor- mation Processing Systems, 36, 2024.
Yu, H., Xu, W., and Zhang, H. Towards safe reinforce- ment learning with safety editor policy. arXiv preprint arXiv:2201. 12427, 2022.

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Notations
d
intrinsic cost
c
extrinsic cost
R
reward function
P
transition probability function
initial state distribution
y
discount factor
the policy
dm
the discounted future state visitation distribution
trajectory
a)
advantage function
JR
the expected discount return
Je
the expected discount cost return
d
cost threshold the set of feasible policies action cost value function cost value function cost advantage function
Ilc
a
()(s)
a))
step size
M
flashbulb memory
unsafe state
Random Projection
intrinsic factor
estimation bias
Q
extrinsic-intrinsic cost value function
Qr
extrinsic-intrinsic update target
Qn
extrinsic-intrinsic n-th update
J
cumulative discount extrinsie-intrinicc cost
E
extrinsic-intrinsic cost function
A
extrinsic-intrinsie cost advantage function
8
extrinsic-intrinsic TD-error trust region size
k
the number of nearest neighbors in KNN
12

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
A. Safety Policy Optimization in MICE
The CRL aims to find an optimal policy by maximizing the expected discount return over the set feasible policies He f II ( S d]:
arg max TEll
(15)
s.t. Jc(x) S
The following equation briefly gives the performance difference of arbitrary two policies, which represents the expected return of another policy n' in terms of the advantage function over æ:
1
JR(TT) - JR(T) =
E Eanan aan (s)
(16)
This implies that iterative updates to the policy, x =s)) arg max, ( a), lead to performance improvement until convergence the optimal solution.
According to the performance difference equation (16), CRL is defined as a constrained optimization problem:
Mk+1 arg Bg a [A] (8, a)] HEllo
(17)
s.l. Jo(TN) + Be ana (A (s, [s,
where policy æ 11g parameterized with parameters 0, and Ty represents the current policy, In this paper, define the cumulative discount Attrinsccinttrnsie cost
(T) : B (st,
(18)
where C=F((s, = F. 3c the extrinsic-intrinsie cost function. The extrinsic-intrinsic advantage function MICE defined
A = Ec + Be + >Vo(s' Ve(+)]
(19)
To reduce constraint violations, we replace Jc with the extrinsic-intrinsé constraint J in the optimization objective. We give the optimization objective of MICE based on the extrinsic-intrinsic cost value estimate and Lemma 1:
Th+11 = arg max Exodd xEllo
Eawdd .ar (A (s.
(20)
1 s.t. Jo(Tx) + 1-7 Ennar amx A (8, (())) < d
where policy E 11e is parameterized with parameters 0, and represents the current policy. We propose optimization methods, MICE-CPO and MICE-PI MICE-PIDLag, based on CPO and PID Lagrangian respectively, to solve the optimization objective 20.
A.1. MICE-CPO
The complex dependency of state visitation distribution d= (s) on unknown policy makes objective 20 difficult to optimize directly. To address this, this paper uses samples generated by the current policy to approximate the original problem locally. We seck to solve the following optimization problem in the trust region:
Th+1 = arg max Esnd aawa LA (s, a)]
FElls
s.t. (T(TT)
E Es aas LA (s, a|Tx)]
(21)
1 1-
(( <
13

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
where Hg is the policy parameterized by parameter 0, ( [T)) Bewar [ (F]((T))) DEL is the KL divergence and 4p > 0 is the trust region size. The set (Ir To D (x) (p)
is the trust region.
In the MICE-CPO method, we approximate the reward objective and cost constraints with first-order expansion and approximate the KL-divergence constraint with second-order expansion. The local approximation to equation 21 is:
B = arg max g T (0 8k)
s.t. c+ (oc ( T 0x) 00
(22)
1
2 (0 0 ( 0k) 4
Fl denotes the gradient of extrinsic-intrinsie constraint where g denotes the gradient of the reward objective in equation 21, 9C in equation 21, Jc(T:) d, H is the Hessian of the Kl.ddivegeecc. When the constraint is satisfied, we can get the analytical solution with the primal-dual method. The solution to the primal problem is:
0" 0"
+ A 11
ET 9C
v²)
(23)
where À and v are the Lagrangian multipliers of the KL-divergence term and the constraint term in the Lagrangian function, respectively. X", v² are the solutions to the dual problem:
A - "
V³ max (0,
(24)
1
uc
ifAc > u
X arg max
27
(25)
X
8 + Xxp)
othhewisee,
where = u 9 H v= (
When the constraint is violated, we use the conjugate gradient method to decrease the constraint value:
2
0- =0
H
9C
(26)
(9C
90
A.2. MICE-PIDLag
In the MICE-PIDLag method, we write the CRL problem 20 as the first-order dynamical system:
0x+1 02 + n-g Auge')
3/ JO(TK) + 1- Egna' ann [A (s, a/mTx)
(27)
A h(yo, ... ...
where 1j the step size of the update, is the gradient of reward objective in equation 20 and ge denotes the gradient of extrinsic-intrinsic constraint equation 20. denotes the control function. À is the Lagrangian multiplier for the equation 20. We provide the updated formulas for the Lagrangian multiplier MICE-PIDLag:
A - (Kr + K,T + Kp0)+
(28)
where (+)+ = max(0, J. and:
1
A (Jo(TT)) + 1 B amm [AE (s, a[m]] d),
+ (T+ A)+,
0 (JO(TH) +
(T 1-7 - E Band amt LA - 1- Esndd am LAg (8, al/=a-1))
1
(29)
1
1 (Bends aaun anm [AE (s, mx)] - Ex anm [AE (s, 2 (
( (s,a)))
Kr, Kr, and KD are the coefficients of the respective control terms. The initial value of the integral term is 0.
14

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
B. Theoretical Proof
B.1. Estimation Bias Lemma
Lemma B.1. a finite MDP for a given state-action pair (8, a), the difference between the optimal cost value function (7(s,0) a) and the cost value estimate Q Q (s,a) after (m n)-th update given by:
- (.
(c, (s
- (a1-)))(n-m-(l-- in-m-
(30)
where Q (s,a) is the estimate of the value function at the n-th update, a is the step size, and In (n(,,a) a) = c + Bc +
IQ (s', a')] (c(s,a) a) is the target difference.
Proof. We use induction method to proof this lemma B.1.
Base Case: m
Substituting 1 in lemma B.I, get:
Qc(s, a) QC =1 -11-a(((6((s0))))) Qc,((s at,(s,a)
(31)
According to the update equation of the extrinsic-intrinsic cost value function in MICE, get:
Q (8, a) aiQ (s) a(c 3e t. (s,, ,')])
(32)
= (1 2. (s, + a(tn(s, a) + (c()sa))
which is equivalent to equation 31.
Induction Step: ks
Assuming lemma B.1 is true for k which is:
Qe(s, - (0,+x(s (a))))))(( (x,
E (1 a) (n4n-
(33)
Now need to prove that it holds for k 1. According to the cost value update equation in MICE, get:
O (s, (1 (1-)) 2) a) a(c + 3d + 19 = (1- a) + t((tn+a(ss Qc(, (c(ss)))
(34)
Then we can get:
ac(s,a) - (s, = (1 a)(Q?(s, - 1o - atn+x(s,
(35)
Substituting the equation 33, we get:
Vc(s, a)
EJ (s,4))
-(1 a) (1 (=) (s, Σ (1 a)* i- ((,
atath(s,a)
(36)
k+1
=(1 - ( QEL
Σ
a)
which satisfies the equation when m lemma B.1.
15

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Lemma B.1 indicates that when 1 and Q (s, a) is random initial value for the cost value function, in stochastic high value region of the state-action space, likely that (c(s, a) ( a) (Karimpanal et al., 2023). In this case, overestimation of our extrinsic-intrinsic cost value function can effectively reduce the estimation bias, whereas underestimation in the traditional value function further increases the estimation bias.
B.2. Balancing Intrinsic Factor
Proposition B.2. For transition (s, a, c ,') in a CMDP, where the n-th update of the extrinsic-intrinsit cost value Qn corresponds the n-th update target QT the modified target for the (n 1 update is Qra,y'' the balancing intrinsic factor 3' for the (n + 1)-th update is given by:
B' = (1"xx("" (3n aGx)
ct
) d00
(37)
where =Qn- Q" is the n-th update estimation bias, 7 E (0,1) is the discount factor.
To avoid excessive estimate bias, we propose an adaptive mechanism for bias correction. The target for the (n+ + 1)-th update QT is modified as:
TT., = QT.+: - a(Qn -
(38)
where Q* is the optimal value, Qn the n-th update estimate. When Qn - Q < O, the modified target 2 is adjusted upward, introducing positive bias to mitigate excessive underestimation. Conversely, when Qn Q" > 0, Q is adjusted downward, introducing negative bias to address excessive overestimation. (Karimpanal et al., 2023).
Denote 6n- = Qn Q* as estimation bias of the n-th update.
@r., = QT aQQn Q²))
(39)
QT QEn
The ideal estimation bias for the ideal (n + 1)-th update target can be denoted as:
cu+1 = QT. - Q"
(40)
According to equation 39, the ideal estimation bias for the (n + 1)-th target can be expressed as:
c QT atn Q"
(41)
where:
QT. c F: + Bacd + 1Q (8,
(42)
The we get the ideal estimation bias of the (n + 1)-th update, with the current value of balancing factor 3
= = cF B 1 arn Q"
(43)
We define the ideal balancing factor P141 as 3r:
6 Q QQ"
(44)
+ 12 "'','')) Q*
According to equation 43 and equation 44, we get the ideal factor 3r:
3' = 3n cl
acn
c' > 0
(45)
16

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
To ensure the non-negativity of intrinsic cost, clip the balancing factor:
aC cf 00, d'>0
8' max (3n
(46)
Based on the convergence analysis of the traditional value function (Van Hasselt al., 2016; Fujimoto et al., 2018), gradually converges the optimal value, causing the estimation bias approach zero. To ensure the convergence of the extrinsic-intrinsic cost value function, we incorporate the discount factor to the balancing factor:
8' max
(EE c. ),0), df
(47)
We provide the convergence guarantee in Theorem 4.5.
B.3. Constraint Difference Lemma
Lemma B.3. Given arbitrary two policies n and n², the difference expectation constraint of extrinsiccintrrnssic J (x²) and extrinsic (T) can be expressed as:
JE'(TT) (-') JC(T) B77T'
Σ xt AC' (st, (()T)
(48)
where AC (st, 0r|=T) = E 1ef + 3et + (V((++)) (s))) The expectation is taken over trajectories and E7/r' indicates that actions are sampled from to generate T.
Proof. The expectations in J (T') and (T) can be expanded as:
JE' = ErAXY
r' ll + Bc(])
(49)
JC(T) = ErAN Σ
Beo~p (5(())
1=0
J EI (x')
Jc(T)
=Brj='
1' (cf + +Bct)
(V
1=
=Byls'
r2 (cf + +c() - (80)
1=
-Ey
7 (c + -Be + ()(+)) - VZ (80)
(50)
-E,
(8())) + + Bd + (8( (8() gof + 7/30 +VV[(s) (() +...]
Exjt
Σ 7' (c +Bd (V8 V8((s))
00
-EA/='
A (st, म| (5))
Here the term A ET (st, r' (s)) denotes that the advantage value function A is over n, the action is selected according to
x'
17

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
The second equation above holds because that
r VV (80)]
= sond' a (v)()
(51)
=E somp [VE
The initial state So in V depends solely on the initial state distribution p. allowing the expectation over 7|m' to be expressed as an expectation over 50
The third equation in equation 50 holds by adding Va while subtracting V2. The fourth equation expands the cumulative sum over time steps The final equation follows from the definition of A
B.4. Constraint Bounds
Theorem B.4 (Extrinsic-intrinsic Constraint Bounds). For arbitrary two policies xe' and n, the following bound for the expected extrinsic-intrinsic constraint holds:
JC ET (T)) S
1 Eswdd aaaa' Bann'
AC (s,
ET D (T [T)]s]
(52)
1-7
1 1-7
El = max, Eaws (AE (s, al the VV-divergence Dry (1/2) E. (r((ass) ( (a|s)) where a"
Proof. Define the state visit probability for time step as (s) P(st s| denote the transition matrix as P=(8'(s)
((s( a), get Pz PxPt-1 Ptp. The discounted future state distribution d d=((s) satisfies:
00
(8) (1 7)
7
P((s s/T)
1=0
= (1 7)
Σ
(s)((s)
1=
(53)
= (1 7)
PPPP
00
= (1 - 7) Σ P>p'''p
t=
- 7) -
where p the initial state distribution, is the identity matrix. Multiply both sides by (I ?P>), we get
(1- (1-7Pa)d (1-7)p
(54)
For cost value function Vs(s) with polices and n. we get the following according to equation 54:
(1 - (1-7) E (o())) Band aor.s - E (Ve(s)]
-11 - 7) / dop())Vo(s)+ + / ds Sda I (1dd - f dsdd [ds((s)Vo(s) (s)Vo(s)
/ ds(1 ())() + (s) - / (s)
(55)
/ dss( PPP (s) dsd dsdd (s))
=0
18

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
The third equation above holds according to equation 54. Then we get:
(1 - (VCp))))(((()) + anr. -B -Bavdr(Vo(s))
(56)
The definition of discount total extrinsic-intrinsic cost is:
(T) (T)(T) 1 Bad B p (C (s, s')]
1
(57)
By combining this with equation 56, we get the discount total extrinsic-intrinsic cost equation:
1 - (T) Ec-ol(())) + -
Exnay Band" www.sstpppppptp (s, 7Vo(8) Vo(s)]
(58)
where the first term on the right side is the estimate of the policy constraint. and the second term on the right side is the average extrinsic-intrinscc TD-error of the approximator. The extrinsic-intrissic TD-error is: 85' a, 8') C (s, a, s') +Voo(s' - (s).). According to the equation 58, the expectation extrinsic-intrinsic constraint difference of any two policies is:
El (C'() (x') 1 Eowddr on ( as,a, 8')l
Eg af
E8 (s, a, a'ss))))
(59)
To simplify the representation, we denote (s) = Baa (85/ (s,0, The first term of the right side in equation 59 can be represented as:
lo0 (s, 6')] doct' /dar' f do' Abg (8,,,,)),
E By ardt s' 1881
= (dF'' (8x1) (d 3x + (dtt" d" ,z)
(60)
the second equation holds by adding d while subtracting d= According to the Hölder's incquality, for any p, a [L, oo] satisfy 1 = 1, we set p 1 and and get:
(d d" 3w S I|d= - dd 1110@rlo
(61)
According to the definition in this theorem, we have 1 lloc = c and ||dd' - -d = 2Drv (dd). According to Lemma 3 in CPO, we have:
27
||d= d d=
Es
(62)
?
By the importance sampling, we get:
n²'
(d 85/)
1" d= 3z)
(63)
The second term of the right side in equation 59 can be represented as:
Eand" st 18 (8, a, 8')] = dodd / daa / as' (oppp1eE.,a... 88,0,8)
(64)
(dd 8z)
Then we get the final result by combining the above equations:
19

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
v 1
π d", 5m) 22DrV (dt ( (dd,,,, ,8,)
(²)-
7
1
πT' () d5) (d ((0T)
(65)
aaw, ( --111 (s, (,,,,'') 1),8'(s,,,
2
E D Drv (n'((>1|
+
27 F1
Bandd away
Al Ac (s, + Drv
1-7
Theorem B.5 (MICE Update Worst-Case Constraint Violation). Suppose Th, Th+1 are related by the optimization objective 21, an upper bound on the constraint of the updated policy Tx++1 is:
6 T11 Jo( S S d I+
(66)
(1 7)2
where EC Mi++ = max, [Ba-ay (A7 (s, u)]l, and I = Er
Dt 3/
Proof. According to Corollary CPO (Achiam et al., 2017),
1 - - Jo(TT) s 1- Benddt
27 Te+1
A (s)
1-7 Drv(
(67)
As The 1 are related by objective 21, we get
Je(Tk) 1-7 Band k a (s,
(68)
which is:
JC(TT) +
1- Bond"H, awtriile + 3d
- s
1
JC(Tx) + 1 1-7
E (oNTEt 14T (s) + 1- B Bandd awtt [Bc|| $ d
(69)
1
Je(Tx) + Eand ano |4 (s, < d
According to Pinsker's inequality, for arbitrary distributions p. the TV-divergence and KL-divergence related by:
Drv(pll)) 1 PKI(Pllg)
(70)
2
According to Jensen's inequality, get:
Exware
<
Exnarx [DKI
(71)
5
2
Then get the final result:
22 mi+1
Jo(Tn-1) 5d-1+ Jd-1
(72)
(1 7)
20

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
B.5. Convergence Analysis
Based on the same assumptions as in TD3 and Double Q-learning, we give convergence guarantees the extrinsic-intrrnsscc cost value function in MICE.
Lemma B.6. Consider a stochastic process (Sts De Ft), where Se, D.s Pr X - R satisfy the equation:
(++1(T+) = (1 ((x=)))Ar(aa) + (((x))
(73)
where It E X ani 1= 0, ... Lel Pt. be sequence of increasing o-fields such that Co and Do are Po-measurable and St. D and Fi-1 are P-mmeasurable = 1,2,-.. Assume that the following holds:
1. The set X is finite.
2. (((m)) E [0, 1), (()) = x., Ex(G(()))) < co with probability I and Vx + xz [((x) = 0.
3. B[F[ 1 x A, 1oo toe where & [0, 1) and ot converges to 0 with probability 1.
4. Var(F.( P.) & K(1 + K A. 1b,)), where K is some constant.
where
oooc denotes the maximum norm. Then A, converges with probability
We use the Lemma B.6 prove the convergence our approach with similar condition in Q-learning.
Theorem B.7 (Convergence Analysis). Given the following conditions:
1. Each state-action pair is sampled an infinite number of times.
2. The MDP is finite.
3. r 1).
4. Qc values are stored in a lookup table.
5. Qc receives an infinite number of updates.
6. The learning rates satisfy (s(s,a) [0. 11, E. a) xo, (x(a(s, < with probability I and (s, a) 0.
v(s, a) # as).
7. Varlcf + Bef] < oo, Vs
The extrinsic-intrinsic Qe will converge to the optimal value function Qo with probability 1.
Theorem B.7 ensures that our method converges to the optimal solution.
Proof. We apply Lemma B.6 prove Theorem B.7. Denote the variables in Lemma B.6 with P. [QE) So, do, Ou, cF. $1, St, ),), X S= A. G au. Define A.(st, Q (s), Q7 az), F,
of -Be + +2QEl (8111, d(41) at).
Condition of the lemma B.6 holds by condition 2 of the theorem B.7. Condition of the lemma B.6 holds as the theorem condition with & = at The condition of lemma B.6 holds as a consequence of the condition the theorem.
So we need to show that the lemma condition on the expected contraction of F, holds.
The extrinsic-intrinsi Q-learning equation in our paper is:
Q (s, = (1 - a)Q5 (s, a) a + Be' + +. (s',a'))
(74)
21

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
We have:
(5t, ax) QQ1++
(8t, a+) -
=(1 an a (st, + aul + 3c/ + (
($411, a(+1)) - (c(st,)))
(75)
=(1 (1 (Q (s,, Qc(ss, + aule + Bet 700 ((+))
a(t1) (c(ss,
=(1 an) P.P.
For the F6, we can write as:
F((s), ac) =c + B/ 7 (041,, Q" (st,
(76)
=F (s,, ar) + Be,
where F/ (st, a,) = c + + (8:+1, 9x+1) Q6 (s,, at) is the value of F; in normal value function. According to the convergence analysis in value function, we get E Pdl S 7 A ol.e. Then condition 3 of lemma 2 holds of converges with probability 1.
The intrinsic cost is normalized and the discount factor term y" is included in the balancing factor, where y (0, 1). So 3et converges to 0 with probability 1, which then shows condition 3 of lemma B.6 is satisfied. So the Q (st, ae) converges to (*(,,
C. Experiment
C.1. Algorithm Process
We provide the code for MICE-CPO and MICE-PIDLag in http::////.ttuu...ooo/ssgiigg/// com description of our method is shown in Algorithm 1.
A formal
Algorithm MICE: Memory-driven Intrinsic Cost Estimation
Input: Initialize policy network To, value networks Vi and V flashbulb memory M. Set the hyperparameter.
Output: The optimal policy parameter 0.
1: for epoch k,0,,, do
2: Sample under the current policy Te.-
3: Update flashbulb memory M.
4: Output the intrinsic cost c
5: Process the trajectories to C-returns, calculate extrinsic-intrinsic advantage functions A with va and by GAE method.
6: for K iterations do
7: Update value networks ViR V.
8: Update policy network no.
9: if N Ej=, (Te |s,] > yp then
10: Break.
11: end if
12: end for
13:
end for
Return: Policy parameters 0x+1-
C.2. Complexity Analysis
The Time complexity of MICE is O(M - N), where M represents the size of the flashbulb memory, and N denotes the number of samples processed during training. For the state of each sample in the training, we compute the distance between the embedding generated by the random projection layer and the contents the memory in order to retrieve the k-nearest neighbors.
22

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
C.3. Additional Experiments
We conducted comparative experiments against additional baselines. Additionally, we designed ablation study to verify the effect of different components in MICE.
C.3.1. BASELINES
The MICE approach can be extended to other CRL algorithms based on actor-critic architectures. We compare MICE-CPO and MICE-PIDLag with their corresponding baselines, CPO and PIDLag, across multiple environments to validate the improvements offered by our approach. The results are shown in Figure 8 and Figure 9, which indicates that our MICE approach effectively improves constraint satisfaction over the respective original approaches while maintaining the same or even better level of policy performance. is crucial to note that in SafetyCarGoall CPO exceeds the constraint threshold, so its higher return compared to MICE- does not indicate better policy. A direct comparison of the returns of CPO and MICE-CPO is not meaningful. A similar phenomenon occurs in Safety Ant when evaluating MICEPID and PIDLag.
Here, we provide an additional introduction to the baseline methods employed in the main text. CUP (Yang et al., 2022) is a projection approach that provides generalized theoretical guarantees for surrogate functions with a generalized advantage estimator (Schulman et al., 2015), effectively reducing variance while maintaining acceptable bias. State augmentation methods aim to achieve constraint satisfaction with probability one. Saute RL (Sootla et al., 2022a) eliminates safety constraints by expanding them into the state space and reshaping the objective. Specifically, the residual safety budget is treated as new state to quantify the risk of violating the constraint. Simmer (Sootla et al., 2022h) extends the state space with state encapsulating the safety information. This safe state is initialized with safety budget, and the value of the safe state can be used as a distance measure to the unsafe region. Simmer reduces safety constraint violations by scheduling the initial safety budget.
SrtttyCrrrrdb1100
FIDLag CatayCarroal
19C2
VICE
1422
0.2
0.4
10
02
0.4
09
1.0
0.2
06
10
02
00
68
SaletyCae Conde
Sufely CareeyCo
Sultt/hantCideeee
MicE:
vice
Figure 8: Comparison of MICE and their respective baseline approaches on Safety Gym. The x-axis is the total number of training steps, the y-axis is the average return or constraint. The solid line is the mean and the shaded area is the standard deviation. The dashed line in the cost plot is the constraint threshold which is 25.
C.3.2. COMPLEX TASKS
We conducted additional experiments comparing MICE with CPO in the SafetyCarButton and SafetyPointBution 1-v0 environments. These tasks are more complex, requiring agents to navigate to a target button and correctly press it while avoiding Gremlins and Hazards. Results presented in Figure 10 show that MICE achieves superior constraint satisfaction while maintaining policy performance comparable to CPO.
C.3.3. COMPARED TO TD3-BASED COST VALUE FUNCTION
TD3 is a reinforcement learning method designed to mitigate the overestimation bias in the reward value function, which uses the minimum output from two separately-leamnel action-value networks during policy updates. Similarly, TD3 can
23

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
1730
5000
1900
1500
100
1000
500
PCA+a
CPC
1BC5
ROL
0
DFO
VICE
MICE
1300
DPO
110403
MICE
CPO
0.6
24
0.4
10
0.2
10
022
Suloty-talChhoo http://aaaahhhhchc////ol/ely/ee
Solicty Huu www.aaamannddddeooooo oddit
35
CPC
VICE
PiDLigg
3
Figure 9: Comparison of MICE and their respective baseline approaches on Safety MuJoCo. The x-axis is the total number of training steps, the y-axis is the average return or constraint. The solid line is the mean and the shaded area is the standard deviation. The dashed line in the cost plot is the constraint threshold which is 25.
SuletyCarautent-00
SuletCCaButentt.0
Suldty-cchnB.aantt--
SaketyPoinButtrtt--0
MBCE
Senenn 45
DF3
72
CPQ
Figure 10: Comparison of MICE with CPO in more complex environments. MICE achieves better constraint satisfaction while maintaining policy performance comparable CPO.
serve as a baseline for addressing underestimation bias in cost by using the maximum output from two separately-learned cost value networks. We conducted experiments compare the cost value estimation bias between the TD3 cost value function and MICE with the PIDLag optimization method in SafetyPointGoall and SafetyCarGoall-vo/ shown in Figure 11, and the performance results are shown in Figure 12.
The results show that TD3 mitigates underestimation bias in cost value estimation, but it cannot fully eliminate it. This limitation arises from the inherent slow adaptation of neural networks, which results in a residual correlation between the value networks, thus preventing TD3 from completely eliminating the underestimation bias. In contrast, MICE eliminates this bias more accurately with the memory-driven intrinsic cost, resulting in significantly improved constraint satisfaction. The intrinsic cost in MICE enhances policy learning by enabling safer exploration, thereby improving performance while maintaining constraint compliance.
Additionally, compared to the TD3 cost value function, the flashbulb memory structures in MICE help address the catastrophic forgetting issue in neural networks (Lipton et al., 2016), where agents may forget previously encountered states and revisit them under new policies. This mechanism generates intrinsic cost signals that guide the agent away from previously explored dangerous states, effectively preventing repeated encounters with the same hazards.
C.3.4. ABLATION STUDY ON RANDOM PROJECTION LAYER
In this paper, a random projection layer is used to compress states before applying KNN. Specifically, states are projected from their original dimension to a lower embedding dimension using a Gaussian random matrix of shape (n, m). This reduces the computational complexity of KNN from O(Mn) to ((M)), where M is the number of stored states. According to the Johnson- Lindsst-Lindesstauuss lemma (Johnson et al., 1984), random projection approximately preserves Euclidean distances in the original space.
We further conducted ablation experiments on random projection, as shown in Figure 13, which confirm that using random
24

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Estimate Bias SafetyCarGoal1-v0
Estimate Bias in SafetyPointGoal1-v0
MICE
10
MICE
PIDLag
TD3PID
10
TD3PID
PIDLag
Estimation Error
Estimation Error
5
5
-5
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
1.0
1e7
1e7
Figure 11: Comparison experiment about Estimation Error of MICE to TD3PID. The y-axis is the cost value estimate minus the true value, and the dashed line is the zero deviation. MICE achieves more accurate mitigation of estimation bias compared to TD3
1127,g
VICE
M622
120010
103P10
15
0.
04
06
0.1
0.2
04 0.
044
1.0
0.2
0.6
1.0
02
00
64
(a) Return
(b) Constraint
(c) Return
(d) Constraint
Figure 12: Comparison of MICE, TD3PID and PIDLag. The x-axis the total number of training steps, the y-axis the average return constraint. The solid line the mean and the shaded area is the standard deviation. The dashed line in the cost plot is the constraint threshold which is 25.
projection in MICE does not reduce policy performance or increase constraint violations, while substantially reducing training time.
In our work, relative similarity between states is important than absolute scalar distances. In implementation, both extrinsic and intrinsic costs normalized to ensure training stability. This normalization alters absolute distance values but preserves similarities between states, which is key to maintaining meaningful guidance for intrinsic cost computation and policy learning. The ablation results show that random projection effectively preserves this relative similarity, thus maintaining the performance of MICE.
C.4. Environments
C.4.1. SAFETY GYM
Figure 14 shows the environments in the Safety Gym (Ji et al., 2023). Safety Gym is the standard API for safe reinforcement learning. The agent perceives the world through the sensors of the robots and interacts with the environment via its actuators Safety Gym. this work, we consider two agents, Point and Car, and two tasks, Goal and Circle.
The Point is simple robot constrained two-dimensional plane. is equipped with actuators, one for rotation and another for forward/backward movement. It has small square in front of it, making it easier to visually determine the orientation of the robot. The action space in Point consists of two dimensions ranging from -1 to 1, and the observation space consists of twelve dimensions ranging from negative infinity to positive infinity.
The Car more complex robot that moves in three-dimensional space and has two independently driven parallel wheels and freely rotating rear wheel. For this robot, both steering and forward/backwwar movement require coordination between the two drive wheels. The action space of Car includes two dimensions with a range from -I to 1, while the observation
25

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
Goaf1-10
SaktyCarrCrdee--0
Ablliin FredorPraccioo
20
MIZ2
Adlliing Paedorrrggeeen
stng Ra-deerhsppcho
Amaiing Randveergpolnnn
MCC
MBC
0.2
10
Salltty Car Gool 1-10
Salcty Car CirdletvV
Fannttool 1-40
Figure 13: Ablation study of random projection layer in MICE algorithm. Utilizing random projection MICE does not degrade policy performance or increase constraint violations.
(a) SafetyPointGoall-v00
(b) SafetyCarGoall-v0
(c) SafetyPoinCirclee-v00
(d) SafetyCarCirelel-v0
Figure 14: Environments in Safety Gym.
space consists of 24 dimensions with a range from negative infinity to positive infinity.
The agent is required to navigate towards the location of the goal. Upon successfully reaching the goal, the goal location is randomly reset to new position while maintaining the remaining layout unchanged. The rewards in the task of Goal are composed of two components: reward distance and reward goal. In terms of reward distance, when the agent is closer to the Goal it gets a positive value of reward, and getting farther will cause a negative reward. Regarding the reward goal, each time the agent successfully reaches the Goal, it receives a positive reward value denoting the completion of the goal. In SafetyGoall, the Agent needs navigate the Goal's location while circumventing Hazards. The environment consists of 8 Hazards positioned throughout the scene randomly.
Goal:
Agent required to navigate around the center of the circle area while avoiding going outside the boundaries. The optimal path is along the outermost circumference of the circle, where the agent can maximize its speed. The faster the agent travels, the higher the reward it accumulates. The episode automatically ends if the duration exceeds 500 time steps. When out of the boundary, the agent gets activated cost.
Circle:
C.4.2. SAFETY MuJoCo
The agent in Safety MuJoCo is provided by OpenAl Gym (Brockman et al., 2016), and it is trained to move along a straight line while constrained with a velocity limit. Figure 15 illustrates the different environments.
26

---

Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration
(a) Veloocit
(b) SaferyHallCheetaaWeeeae
(c) SaletyHumanoodVVllccity
(d) SafetyHopper
Figure 13: Environments in Safety MuloCo.
C.5. HyperParameters
experiments are implemented in Pytorch 2.0.0 and CUDA 11.3 and performed on Ubuntu 20.04.2 LTS with a single GPU (GeForce RTX 3090). The hyperparameters are summarized Table 1.
Parameter
Saute
Simmer
CUP
CPO
PIDLag
MICE-CPO
MICE-PIDLag
hidden layers
2
2
2
2
hidden sizes
64
64
64
64
64
64
64
activation
lanh
lanh
lanh
lanh
Lanh
Lanh
lanh
actor learning rate
3e
3e 4
3e 4
3e 4
36 4
3e 4
3e
critic learning rate
3e
3e 4
3e
4
3e 4
3e 4
3e 4
3e -
batch size
64
64
64
64
64
64
trust region bound
1e
1e
16
le 2
1e
discount factor gamma
0.99
0.99
0.99
0.99
0.99
0.99
0.99
GAE gamma
0.95
0.95
0.95
0.95
0.95
0.95
0.95
normalization coefficient
1e
1e 3
1e 3
1e
1e - 3
lE 3
1e 1 3
clip ratio
0.2
0.2
0.2
N/A
0.2
N/A
0.2
conjugate gradient damping
N/A
N/A
N/A
0.1
N/A
0.1
N/A
initial lagrangian multiplier
N/A
N/A
1e -0-3
3
N/A
16-3
N/A
1e-3 3
lambda learning rate
N/A
N/A
0.035
N/A
0.035
N/A
0.035
Table Hyperparameters
27


Reviews:
[{"review_id": "HEu4Apah5q", "reviewer": "Reviewer_9DRS", "summary": "The paper tackles a important issue in CRL: the underestimation bias in the cost value function, arising from the functio approximation error, which often results in unsafe exploration and frequent constraint violations. The paper proposes the MICE algorithm to address this issue. It uses a flashbulb memory mechanism to store unsafe states and then compute an intrinsic cost based on the pseudo-count of state visits to high-risk regions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's positive and insightful comments. The following are the detailed responses to the points raised by Reviewer 9DRS.\n\n>The assumptions (e.g., finite MDP, extensive sampling) might restrict practical applicability in more complex or continuous environments.\n\n**Response:**\nWe thank the reviewer’s valuable comment. \nTo address this concern, we conducted additional experiments comparing MICE with CPO in SafetyCarButton1-v0 and SafetyPointButton1-v0 environments. These tasks are more complex, requiring agents to navigate to a target button and correctly press it while avoiding Gremlins and Hazards. Results presented in Figure 1 (<https://anonymous.4open.science/r/7532-6C07/experiments1.pdf>) show that MICE achieves superior constraint satisfaction while maintaining policy performance comparable to CPO.  \n\nFurthermore, we acknowledge potential limitations where direct environmental sampling is infeasible. To address this, offline data can be leveraged to construct memory, thus enhancing MICE’s applicability in these special cases.\n\n\n\n\n>I suggest the authors provide a hyperparameter sensitivity experiment on $N_k$ in KNN.\n\n**Response:**\nWe appreciate the reviewer’s valuable suggestion.\nTo address this, we conducted hyperparameter sensitivity experiments for $N_k$ across multiple environments and analyzed the impact, as shown in Figure 2 in (<https://anonymous.4open.science/r/7532-6C07/experiments1.pdf>). \nThe results show that increasing $N_k$ enhances the safety of the policy, as it considers more unsafe states in memory, but also raises computational overhead. Conversely, a smaller $N_k$ may lead to insufficient leveraging of unsafe state information, potentially leading to higher constraint. In this paper, we selected $N_k = 10$ uniformly across all environments to balance safety, performance, and computational efficiency.\n\n\n\n>Please provide the detailed implementation specifics of the random projection layer.\n\n**Response:**\nWe appreciate the reviewer's valuable comment regarding the details of random projection. \n\nOur random projection layer is implemented using a Gaussian random matrix with shape $(n, m)$, projecting states from the original dimension $n$ to a lower embedding dimension $m$. According to the Johnson-Lindenstrauss lemma [1], this approach approximately preserves relative Euclidean distances in the original space, which is proven valid by prior KNN-based methods [2][3].\n\nIn our work, this dimensionality reduction effectively decreases the computational complexity of KNN from $O(N n)$ to $O(N m)$, where $N$ is the number of states in memory. Specifically, in SafetyPointGoal1, the state dimension is reduced from 60 to 8. \n\nFurthermore, we conducted ablation experiment on random projection. As demonstrated in Figure 3 (<https://anonymous.4open.science/r/7532-6C07/experiments1.pdf>), utilizing random projection in MICE does not degrade policy performance or increase constraint violations, while effectively reducing training time. \n\n\n\n>The flashbulb memory only stores states with extrinsic cost greater than zero. However, the states with outlier extrinsic costs may not store in the memory and therefore might not be adequately corrected by the intrinsic cost mechanism. How does the paper handle these cases?\n\n**Response:** \nWe appreciate the reviewer’s insightful question. \nIn our tasks, the extrinsic cost is derived by the environment based on the agent's and obstacles' coordinates, providing unbiased real data without outliers. \nUnderestimation primarily occurs due to constraint minimization during optimization, which disrupts the zero-mean property of noise, especially in regions with higher extrinsic costs. Therefore, current memory mechanism adequately captures these underestimated states in our tasks.\n\nHowever, we fully agree with the reviewer that in other special tasks, where extrinsic costs may be biased, outlier states could arise. To handle such cases, alternative criteria for adding new states into memory could be applied. \nOne possible strategy is using the expected subsequent costs as the criterion for adding states into memory: a state would be stored if its expected future cost exceeds a threshold. This approach effectively mitigates the impact of individual outliers by considering multiple future states collectively.\n\n[1] Johnson, W. B., Lindenstrauss, J., et al. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics,\n26(189-206):1, 1984.\n\n[2] Hu, H., Ye, J., Zhu, G., Ren, Z., and Zhang, C. Generalizable episodic memory for deep reinforcement learning. In\nInternational Conference on Machine Learning, pp. 4380–4390. PMLR, 2021.\n\n[3] Zhu, G., Lin, Z., Yang, G., and Zhang, C. Episodic reinforcement learning with associative memory. In International\nConference on Learning Representations.", "claims_and_evidence": "The paper provides convergence proofs, worst-case constraint violation bounds, and other theoretical results that support its claims regarding bias correction and safe exploration.", "methods_and_evaluation_criteria": "The proposed methods are well-aligned with the underestimation challenge inherent in  CRL.", "theoretical_claims": "I reviewed the proofs.", "experimental_designs_or_analyses": "The claim that the intrinsic cost mechanism alleviates underestimation without overly conservative behavior is supported by both theoretical analysis (via the adaptive balancing factor) and experimental results. However, the evidence might be less convincing if one considers potential sensitivity to hyperparameters or the handling of outlier states not captured by the flashbulb memory.\n\nThe use of KNN with random projection is theoretically motivated to reduce computation. However, the experiments do not extensively report on implementation details, computational overhead, or scalability issues, which might be relevant for real-world applications or more complex simulations.", "relation_to_broader_scientific_literature": "The paper integrates and extends ideas from CRL, intrinsic motivation, and memory-based exploration. By combining these concepts, it provides a theoretically grounded and empirically validated framework", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "1. The idea of using a flashbulb memory to derive an intrinsic cost is innovative and draws an interesting parallel with human risk perception.\n2. The paper provides solid theoretical underpinnings including convergence analysis and constraint violation bounds. However, the assumptions (e.g., finite MDP, extensive sampling) might restrict practical applicability in more complex or continuous environments.", "other_comments_or_suggestions": "1. Typically, for the KNN part, the choice of N_k is crucial. If N_k is too small, the count might be noisy; if it’s too large, it may smooth out important local variations. This parameter may require careful tuning depending on the environment. I suggest the authors to provide a hyperparamter sensitivity experiment on it.\n\n2. Please provide the detailed architectural design, hyperparameter settings, or the exact implementation specifics of the random projection layer.", "questions_for_authors": "I have a concern regarding the flashbulb memory mechanism described in the paper. The flashbulb memory stores only states where the extrinsic cost is greater than zero. This raises the issue that samples truly suffering from underestimation—possibly due to function approximation errors—may not be captured if they do not exhibit extrinsic cost > 0 or if they are outliers. Such outlier states are potentially more prone to underestimation, yet they may not fall within the types of states stored in the memory and therefore might not be adequately corrected by the intrinsic cost mechanism. Has the paper addressed this issue, and if so, what strategies are proposed to handle these cases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pSF3b2iTQt", "reviewer": "Reviewer_rbBW", "summary": "The paper proposed MICE, which introduces the concept of intrinsic cost to combat the issue of underestimation bias in cost-value function present in many safe RL algorithms. The paper discusses their flashbulb memory design, which attaches additional intrinsic cost to previously visited risk regions, and shows that this reduces underestimation bias in safe RL. Theoretically, the paper provided theoretical bound on the constraint violation and convergence guarantee.\n\n----- Score raised to 4: Accept after rebuttal -----", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's positive and insightful comments. The following are the detailed responses to the points raised by Reviewer rbBW.\n\n\n>The paper might benefit from investigating how this embedding function interact with the effect of KNN choice.\n\n**Response:**\nWe appreciate the reviewer’s valuable comment regarding investigating the embedding function and KNN choice.\n\nIn our paper, we utilize a random projection method as the embedding function to compress states before applying KNN. Specifically, states are projected from their original dimension $n$ to a lower embedding dimension $m$ using a Gaussian random matrix of shape $(n, m)$. This significantly reduces the computational complexity of KNN from $O(N n)$ to $O(N m)$, where $N$ is the number of states in memory. Prior studies [1][2] have validated the effectiveness of random projection in similar KNN-based methods.\n\nWe further conducted ablation experiments of random projection (Figure 1, <https://anonymous.4open.science/r/7532-6C07/experiments2.pdf>), which confirm that using random projection in MICE does not reduce policy performance or increase constraint violations, while substantially reducing training time.\n\nAdditionally, we examined the sensitivity of $N_k$ selection in KNN across multiple environments (Figure2, <https://anonymous.4open.science/r/7532-6C07/experiments2.pdf>). Results show that a larger  $N_k$ enhances policy safety by considering more unsafe states, but it increases computational overhead. Conversely, a smaller $N_k$ may not fully utilize memory information, potentially leading to higher constraint. To balance safety, performance, and efficiency, we set $N_k = 10$ in MICE for all tasks.\n\nWe appreciate the reviewer’s constructive comments and hope that these analyses provide further clarity.\n\n\n>The baseline comparison with CPO (in Appendix C.3.1) should be moved to the main paper. I'd think that expanding to more tasks might verify that MICE is reliably safer than CPO.\n\n**Response:**\nWe appreciate the reviewer’s valuable comments. \nFollowing your advice, we will move the comparison between MICE and CPO from Appendix to the main text for improved clarity.  \n\nTo further verify the safety advantages of MICE, we conducted additional experiments in a broader set of environments. The results in Figure 3 (<https://anonymous.4open.science/r/7532-6C07/experiments2.pdf>) demonstrate that MICE consistently achieves superior constraint satisfaction across all tasks, while CPO exhibits significant constraint violations.  \n\nAdditionally, to provide a more intuitive quantitative comparison, we present the difference in constraint violation rates between CPO and MICE during training. The results in Table 1 (<https://anonymous.4open.science/r/7532-6C07/experiments2.pdf>) show that CPO consistently exceeds MICE in violation rates in all environments, with an average violation rate 34.4\\% higher than MICE. This further confirms the safety advantages of MICE.  \n\n\n>The authors might want to consider expanding to other tasks to check how the discount rate of 0.99 behaves and comparing with PPO-Lagrangian and PID-Lagrangian.\n\n**Response:**\nWe appreciate the reviewer’s valuable comment regarding the behaviour of discount factor 0.99 in more tasks and its comparison with PPO-Lagrangian and PID-Lagrangian.\nTo address this, we evaluated MICE with a discount factor of 0.99 on additional tasks and compared its performance against PPO-Lagrangian and PID-Lagrangian. As shown in Figure 4 (<https://anonymous.4open.science/r/7532-6C07/experiments2.pdf>), MICE consistently achieves strong constraint satisfaction while maintaining superior policy performance. In contrast, PPO-Lagrangian and PID-Lagrangian exhibit significant oscillations in constraint during training.\n\nIn our experiments, we used the consistent discount factors across all methods.\n\n\n[1] Hu, H., Ye, J., Zhu, G., Ren, Z., and Zhang, C. Generalizable episodic memory for deep reinforcement learning. In\nInternational Conference on Machine Learning, pp. 4380–4390. PMLR, 2021.\n\n[2] Zhu, G., Lin, Z., Yang, G., and Zhang, C. Episodic reinforcement learning with associative memory. In International\nConference on Learning Representations.", "claims_and_evidence": "Most of the claims in the paper are well supported by theory and experiment. The only doubt I have is that: \n\n1. To compute the similarity between newly encountered state and the state in the memory, the paper proposed a kernel function which is approximated using k-nearest neighbors. KNN, as a non-parametric model, is known to suffer from curse of dimensionality. This might cause difficulty for MICE to handle very high-dimensional state representation. The embedding function $f()$ would be key in this regard. The paper might benefit from investigating how this embedding function interact with the effect of KNN choice.", "methods_and_evaluation_criteria": "The baselines chosen are well suited for this problem. I'd also highlight that MICE is extended based on CPO, thus the baseline comparison with CPO (in Appendix C.3.1) should be moved to the main paper. I do note that CPO and MICE performance are very close, and MICE is relatively safe in some domains (Hopper, PointGoal1).", "theoretical_claims": "The theoretical claim is well supported, I do have to highlight I did not do step-by-step check on the detailed proof in the Appendix.", "experimental_designs_or_analyses": "1. In the 8 chosen tasks, MICE's performance seems rather close to CPO although it's relatively safer in two domains. I'd think that expanding to more tasks might verify that MICE is reliably safer than CPO.  \n\n2. In the sensitivity analysis (Appendix C.3.2) of discount factor, the oft-used default of 0.99 seems to produce a policy which oscillates around the constraint threshold 25. This behavior seems largely similar to other constrained RL algorithm (e.g. PPO-Lagrangian, PID-Lagrangian). The authors might want to consider expanding to other tasks to check how the discount rate of 0.99 behaves.", "relation_to_broader_scientific_literature": "This is quite relevant to the safe RL literature where cost-value underestimation might be present.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "1. Is discount rate of 0.99 used across all baselines for the main result?", "questions_for_authors": "Please refer to earlier sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pxmxG3X5uK", "reviewer": "Reviewer_kehG", "summary": "This paper presents Memory-driven Intrinsic Cost Estimation (MICE), an algorithm for reducing constraint violations in constrained RL throughout training, rather than just at the end of training. It does this using a memory buffer that stores a representation previously seen constraint-violating states, which are compared to new states to form an intrinsic reward term to reduce value function over-estimation leading to repeated visitation of constraint violating states.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's positive and insightful comments. The followings are detailed responses to the points raised by Reviewer kehG.\n\n\n>When using a random network to project into latent space, my understanding is that distance in random latent space is mostly a \"these two states are or are not similar\" thing, rather than having use as a scalar quantity. As MICE uses a k-NN distance in this space, it makes me wonder if the numerical value matters or if it's just a matter of being moderately distant from previously sampled datapoints. Could the intrinsic rewards be quantized, and would that affect performance? I don't think this is critical to answer but the use of a random latent space seems at odds with the idea of specific distances mattering.\n\n**Response:**\nWe appreciate the reviewer’s insightful comments regarding the use of random projection in state comparisons.  \n\nIn our experiments, random projection is implemented using a Gaussian random matrix of shape $(n, m)$, which projects states from the original dimension $n$ to a lower dimension $m$. According to the Johnson-Lindenstrauss lemma [1], random projection approximately preserves Euclidean distances in the original space, which is proven to be valid in similar KNN-based methods in prior works [2][3].  \n\nAdditionally, we fully agree with the reviewer that relative similarity between states is more important than absolute scalar distance. In our implementation, both extrinsic and intrinsic costs are normalized to ensure training stability. This normalization alters absolute distance values but preserves similarities between states, which is key to maintaining meaningful guidance for intrinsic cost computation and policy learning.  \n\nTo further assess the impact of random projection, we conducted an additional ablation study on it. The results in Figure 1 (<https://anonymous.4open.science/r/7532-6C07/experiments3.pdf>) demonstrate that using random projection does not degrade policy performance or increase constraint violations, further supporting the idea that state similarity is likely more critical than absolute numerical values.  \n\nWe appreciate the reviewer’s constructive questions and hope these additional experiments and clarifications address the concern.\n\n\n>The paper title at the top of each page is not correct.\n\n**Response:**\nWe sincerely appreciate the reviewer’s careful review. We will correct this typo in the revised manuscript.\n\n\n[1] Johnson, W. B., Lindenstrauss, J., et al. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics,\n26(189-206):1, 1984.\n\n[2] Hu, H., Ye, J., Zhu, G., Ren, Z., and Zhang, C. Generalizable episodic memory for deep reinforcement learning. In\nInternational Conference on Machine Learning, pp. 4380–4390. PMLR, 2021.\n\n[3] Zhu, G., Lin, Z., Yang, G., and Zhang, C. Episodic reinforcement learning with associative memory. In International\nConference on Learning Representations.", "claims_and_evidence": "The claims of the paper seem to be well-supported by the theoretical and experimental evidence provided.", "methods_and_evaluation_criteria": "The proposed methods and evaluation seems reasonable for the problem.", "theoretical_claims": "I did not check the proofs, but the theorem claims seem reasonable", "experimental_designs_or_analyses": "The experimental design seems reasonable, the estimation bias and ablation experiments test specific claims the paper makes about why the proposed method works.", "relation_to_broader_scientific_literature": "This work seems significant in that reducing the frequency of constraint violations during constrained RL training is valuable for enabling CRL to be used for many tasks which require training where constraint violations have a real cost (for example, training a robot policy on a real robot). To my knowledge, prior work on CRL hasn't attempted to address during-training violations and has mostly focused on the state of the policy after training. That this work also improves the training process in general and finds a better solution is a worthwhile contribution as well.", "essential_references_not_discussed": "Conservative Q Learning and similar methods have been used for offline RL with success, while the goal and method are different the general concept of conservative value estimation to ensure good behavior is shared, it might be worth mentioning in the discussion of related work on overestimation in RL.", "other_strengths_and_weaknesses": "Overall, I liked this paper. The problem being addressed is significant and to my knowledge novel. The proposed method makes intuitive sense, and is theoretically justified, with sufficient experimental validation on standard benchmarks to demonstrate efficacy.\n\nIf there's one weakness to highlight, it's that I wonder about the use of a random network projection for the memory state comparison (I've got a question below along those lines), but overall I think this is a solid paper that is ready for acceptance.", "other_comments_or_suggestions": "The paper title at the top of each page is not correct", "questions_for_authors": "When using a random network to project into latent space, my understanding is that distance in random latent space is mostly a \"these two states are or are not similar\" thing, rather than having use as a scalar quantity. As MICE uses a k-NN distance in this space, it makes me wonder if the numerical value matters or if it's just a matter of being moderately distant from previously sampled datapoints. Could the intrinsic rewards be quantized, and would that affect performance? I don't think this is critical to answer but the use of a random latent space seems at odds with the idea of specific distances mattering.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers agreed that the work addresses an important problem that is understudied in the area of constrained reinforcement learning. Reviewers recognize that the proposed method is novel and that the theoretical claims are largely convincing. Reviewer 9DRS reviewed the proofs, but noted that some assumptions may affect the generality of some claims.
The rebuttal acknowledged the reviewer’s thoughtful feedback and provided detailed answers and clarifications, which sufficiently addressed the raised concerns.
I have no hesitation to strongly recommend this work for acceptance.
Decision: Accept (oral)