Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Authors: Bo Yue
Jian Li
Guiliang Liu
Venue: ICML 2025 poster (2025)
Keywords: Inverse Constrained Reinforcement Learning
Exploration Algorithm
Sample Efficiency
Primary area: reinforcement_learning->inverse
TL;DR: This paper introduces a strategically efficient exploration framework for Inverse Constrained Reinforcement Learning problems with theoretically tractable sample complexity.

Abstract: Optimizing objective functions subject to constraints is fundamental in many real-world applications. However, these constraints are often not readily defined and must be inferred from expert agent behaviors, a problem known as Inverse Constraint Inference. Inverse Constrained Reinforcement Learning (ICRL) is a common solver for recovering feasible constraints in complex environments, relying on training samples collected from interactive environments. However, the efficacy and efficiency of current sampling strategies remain unclear. We propose a strategic exploration framework for sampling with guaranteed efficiency to bridge this gap. By defining the feasible cost set for ICRL problems, we analyze how estimation errors in transition dynamics and the expert policy influence the feasibility of inferred constraints. Based on this analysis, we introduce two exploratory algorithms to achieve efficient constraint inference via 1) dynamically reducing the bounded aggregate error of cost estimations or 2) strategically constraining the exploration policy around plausibly optimal ones. Both algorithms are theoretically grounded with tractable sample complexity, and their performance is validated empirically across various environments.

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Bo Yue Jian Li
Guiliang Liu"
Abstract
sistently guarantee safe control is challenging. which is further exacerbated when the ground-truth constraint is time- varying and context-dependent
Optimizing objective functions subject to con- straints is fundamental in many real-world ap- plications. However, these constraints are often not readily defined and must be inferred from ex- pert agent behaviors, a problem known as Inverse Constraint Inference. Inverse Constrained Rein- forcement Learning (ICRL) is a common solver for recovering feasible constraints in complex en- vironments, relying on training samples collected from interactive environments. However, the effi- cacy and efficiency of current sampling strategies remain unclear. We propose strategic explo- ration framework for sampling with guaranteed efficiency to bridge this gap. By defining the fea- sible cost set for ICRL problems, we analyze how estimation errors in transition dynamics and the expert policy influence the feasibility of inferred constraints. Based on this analysis, introduce two exploratory algorithms to achieve efficient constraint inference via 1) dynamically reducing the bounded aggregate error of cost estimations or 2) strategically constraining the exploration policy around plausibly optimal ones. Both algorithms are theoretically grounded with tractable sample complexity, and their performance is validated empirically across various environments.
Instead of utilizing a pre-defined constraint, an alterna- tive approach, Inverse Constrained Reinforcement Learning (ICRL) (Malik et al., 2021; Liu et al., 2025), seeks to learn constraint signals from the demonstrations of expert agents and imitate their behaviors by adhering the inferred con- straints. ICRL effectively incorporates expert experience into the online CRL paradigm and thus better explains how expert agents optimize cumulative rewards under their em- pirical constraints. Under this framework, existing ICRL algorithms often assume the presence a known dynamic model (Scobee & Sastry, 2020; McPherson et al., 2021), or generative transition model that responds to queries for any state-action pair (Papadimitriou al., 2023; Liu et al., 2023). However, this setting has a considerable gap with real-works scenarios where such global transition models are often unavailable or even vareingy In such cases, agents have to physically navigate to new states to learn about transition dynamics through exploration.
To mitigate the gap, some recent studies (Malik et al., 2021; Baert et al., 2023) explicitly maximized the policy entropy throughout the learning process, yielding soft-optimal pol- icy representations that favor less-selected actions. However, this strategy often induces overly conservative constraints that forbid any behavior not present in the expert demon- strations. Moreover, such an uncertainty-drie ignores the potential estimation errors in dynamic models and expert policies. To date, a thcoretical framework is still lacking to demonstrate how well such exploration ap- proaches facilitate the accurate estimation of constraints.
exploration
1. Introduction
Constrained Reinforcement Learning (CRL) tackles sequen- tial decision-makinn problems with safety constraints and has achieved considerable success in various safety-critical applications (Gu al., 2022). However, in many real-world environments, such as robot control (García & Shafie, 2020; Thomas et al., 2021) and autonomous driving (Krasowski et al., 2020), specifying the exact constraint that can con-
This paper introduces a strategic exploration framework for sampling to solve ICRL problems with guaranteed effi- ciency. Recognizing the inherent challenge of pinpointing the exact constraint that expert agents adhere in their demonstrations (Ng et al., 2000), the objective of our frame- work is to recover a sei feasible construints, rather than to specify unique constraint with pre-defined heuristics or re- strictions. This approach has the advantage of analyzing the intrinsic sample complexity of ICRL problems only, without being obfuscated by other factors (Lazzati et al., 2024b). By representing constraints with reward advantages, we bound
CCoreesoonding Author 'School of Data Science, The Chi- nese University of Hong Kong, Shenzhen "Stony Brook Uni- versity, New York. Correspondence to: Guiliang Liu <liuguil- iang ciee@cuhk.edu.cn..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
estimation errors for feasible cost functions to the discrep- ancy between estimated and ground-truth ones regarding dynamics and the expert policy. Based on this quantifiable measure of estimation errors, a tractable upper bound for sample complexity can be derived.
simplify inverse constraint inference to a variant of IRL by jointly identifying the cost function and Lagrange parame- ters, which are assumed to form convex cone. Kim et al. (2024) generalized the IRL framework to infer tight safety constraints from multi-task expert demonstrations, offer- ing both performance and constraint satisfaction guarantees. Building on this work, Qadri et al. (2025) revealed that in- verse constraint inference recovers a dynamic-conie cendticccoddiiooned and failure-inevitalle constraint set, rather than the origi- nal ground-truth constraint set. Another line of research in classical ICRI, algorithms updated the cost functions by maximizing the likelihood of generating the expert dataset under the maximum (causal) entropy framework (Scobee & Sastry, 2020). This method has been scaled to both dis- crete (McPherson et al., 2021) and continuous state-action spaces (Malik et al., 2021; Baert et al., 2023; Liu et al., 2023; Qiao et al., 2023; Xu & Liu, 2024a;b; Zhao et al., 2025). To improve training efficiency, recent studies combined ICRL with bi-level optimization techniques (Liu & Zhu, 2022;
Under our framework, we design two strategic exploration algorithms for solving ICRL problems: 1) Bounded Error Aggregate Reduction (BEAR) algorithm, which guides the exploration policy minimize the upper bound of cost esti- mation errors, and 2) a Policy-Constrained Strategic Explo- ration (PCSE) algorithm, which reduces the estimation eπrоr by selecting an exploration policy from a set of candidate policies. This collection of policies is rigorously established to encompass the optimal policy, thereby promising to ac- celerate the training process significantly. We provide rigorous sample complexity analysis for both algorithms, furnishing deeper insights into their training efficiency.
To empirically study how well our method captures the accurate constraint, we conduct evaluations under different environments. The experimental results show that PCSE significantly outperforms other exploration strategies and applies continuous environments.
Gaurav et al., 2023). However, neither have these ICRL methods investigated exploration strategies based on estima- tion errors nor conducted theoretical studies on the sample efficiency of their algorithms.
2. Related Work
3. Preliminaries
This section reviews the previous works that are most closely related to ours. Appendix B provides further discussions.
Notation. Let X' and Y be two sets. y represents the set of functions f X' - y. Let A denote the set of probability measures over X. Let A denote the set of functions: y - A* We define the vector infinity norm as ||a|| x max;/a; [a:] and the matrix infinity norm as || max, E, |Aijl. We define min (x) to re- turn the minimum positive value of f over X. The complete notation is reported in Appendix A.
Exploration in Inverse Reinforcement Learning (IRL). Compared with the exploration strategies in RL for forward control (Amin et al., 2021; Ladosz et al., 2022), the ploration algorithms in IRL have relatively limited studies. Balakrishnan et al. (2020) utilized Bayesian optimization to identify multiple IRI. solutions by efficiently exploring the reward function space. To learn a transferable reward function, Metelli et al. (2021) introduced an active sampling methodology that targets the most informative regions with generative model to facilitate effective approximations of the transition model and the expert policy. A subsequent research (Lindner et al., 2022) expanded this concept to finite-horizon MDPs with non-stationary policies, crafting innovative strategies to accelerate the exploration process. To better quantify the precision of recovered feasible re- wards, Metelli et al. (2023) recently provided a lower bound on the sample complexity for estimating the feasible reward set in the fiite-horizoo setting with a generative model. However, these methods study only reward functions under a regular MDP without considering the safety of control or the constraints in the environment.
Constrained Markov Decision Process (CMDP). We model the environment as a stationary CMDP M u (S, A, Pr, r, c, No, 7), where S and A are the finite state and action spaces, with each cardinality denoted as 5=18| and A AA| P7('' (8, a) E A S..A defines the transition distribution; E [0, Rmax J and c E [0, Cmax) de- note the reward and cost functions; e defines the threshold (budget) of the constraint; Po E A denotes the initial state distribution; 7 E [0, 1) is the discount factor. M denotes the CMDP without knowing the cost (i.e., CMDP' (c). The agent's behavior is modeled by a policy π E Ag. Iuu denotes the set of all optimal policies for CMDP MUc. The expert policy x= is optimal in the sense that x maximizes the rewards while adhering to constraints, i.e., i E IljMue Let f E RS and g E R.S.A. X.A.A, we slightly abuse Py and æ as operators: (PT a) = -Eves Ps(''|s, P (s' and (s) = E measure as (s) (1 7) Eee 7 7'P (sr 8, a, a) where pT denotes the probability at (8, a) at timestep No
Inverse Constrained Reinforcement Learning (ICRL). Inverse Constraint Learning (ICL) extended the IRL paradigm account for safety issues. This line of research encompasses several notable works. Hugessen et al. (2024)
(a)s)) a). We define the occupancy
2

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
I under the policy π and the initial distribution Ho. We fo- cus on discrete finite state-action space within infinite planning horizon in this work.
higher rewards than the expert policy (shorter path in Fig- ure 1, left), the underlying constraints must be violated, and we can detect unsafe state-action pairs by examining these infeasible trajectories; 2) if policy achieves the same or lower rewards than the expert policy (equal or longer path in Figure 1, middle & right), this suggests an absence of notable constraint-violating actions, implying that the under- lying constraints may or may not be violated. To effectively prevent overfitting and mitigate the combinatorial explosion of the constraint space, ICRL focuses on identifying the minimal set of constraints necessary to explain expert be- haviors (Scobee & Sastry, 2020). In this sense, only the first insight is utilized to expand the cost set.
Constrained Reinforcement Learning (CRL). Within a CMDP, CRL learns a policy æ that maximizes the dis- counted cumulative rewards subject to a known constraint:
8
arg max 7
E T.P
Σ
s.t. E 7.
Σ 2'c(se, s,
where 0 indicates hard constraint and e >> represents soft constraint since e is non-negative.
Lemma 4.1. Suppose the expert policy T. of a CMDP M U e is known, and the current state is 8. Let (x)) de- note the set containing all expert actions at state s, i.e. 2 (s) = {a E A | (als)) > 0}. Then, at least one of the following two conditions must be satisfied: 1) the cost function satisfies E. - r'c((1, ai)
Value and advantage functions. We distinguish two cases where the first superscript or specifies the actual rewards or costs evaluated and the subscript M or MUe the environment. We denote the reward action-value function as Q71 (s, = Er, 1E== 2'r(s;, a=)]=0 = 8,00 = a] and the reward advantage function as (s,
2) Va' E A(2 AM R (s, S.O
QM (s,a) a)- - VM" (s), where the reward state-value func-
Intuitively, if there is some unused constraint budget and a better action, there must exist chance for policy improve- ment, which violates the optimality of the expert policy, The above lemma shows that cumulative costs of the expert policy must reach the threshold, i.e., use all the budget, if there exists a non-expert action yielding greater rewards than the expert policy (the first condition must be satisfied if the second condition is not satisfied). Thus, enforcing that any higher-reward action incurs greater costs than the expert policy suffices to establish a constraint-violatio condition.
Likewise, note the cost action-value function as C (Muu(() a) =
tion VM" (s)
de-
Ex 1 r'c(s,, 0s) = s, ao = al and the cost state-
value function as (s) = E. (x
4. Learning Feasible Constraints
This section formally defines the feasible cost set and inves- tigates how estimation errors of the inferred cost functions can be bounded by imperfections in the estimates of both transition dynamics and the expert policy.
Let Q. = [(s, a) QMu (s, a) Vate (s) > 0} denote the set of state-action pairs with higher costs than the expert, given cost function c. In scenarios with hard constraints, it simplifies to: Q. = {(s, a))c(s), a) > 0}. We formally formulate the ICRL problem (Malik et al., 2021) as follows.
Definition 4.2. An ICRL problem is a pair 2 #F) A cost function c E [0, Cmax] is feasible for q if π is an optimal policy for the CMDP M U c. i.c., - E 11"Mue Let Fup = f E Muuee denote general set of feasible cost functions. ICRL problem seeks to recover the minimal set of feasible cost functions for P. named feasible cost set that satisfies Cp {c"lc" = arg min [2o]]-
Start
Start
Figure 1. Trajectories of the expert policy (black) and exploratory policies (red and bluc) in a Gridworld. The constraint (gray) is observable. On the left, exploratory policies reach the goal in shorter paths and thus have larger rewards. In the middle, the rewards of exploratory policies are equal to the rewards of the expert policy. Their trajectories can either overlap with the con- straint (red) or simply mismatch the expert's (blue). On the right, exploratory policies result in longer paths that gain fewer rewards.
We have defined the Q-function for non-expert actions. However, for stochastic expert actions under soft constraints, we only know that E.--, (Q Mu a')] = V ve.r* (s) 2 O. To determine the exact value of the Q-function for expert actions, the following assumption is required.
4.1. Feasible Costs in CMDP
Assumption 4.3. (i) The expert policy F is optimal want rewards among all safe policies;
Since the expert policy maximizes rewards within certain constraints, two key insights emerge 1) if a policy achieves
(ii) The expert policy E is deterministic for soft constraints.
3

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Based on these findings, we establish the feasible cost set.
expert decision at state 8. We further denote (s) EaEA nf((s,)) a). We define four cumulative counts from iteration 1 to l as N,,(s,,ss) = E²= ny(s, s') and Ne a) = ركز (5(,,a), (E( -j (s, a) and [ = ΣE= (s). Eventually, the transition model and the expert policy for a state-action pair at it- eration are estimated as:
Lemma 4.4. (Feasible Cost Set Implicit). Under Assump- tion 4.3, e is a feasible cost function for an ICRL problem B. i.e., c C Czp if and only if V(s, a) E x A:
(i) 1 > ie., (8, follows the expert policy:
Q E
Vinue (5) = 0.
(3)
Pro(d1o, a) = No(s,a,s') (s,
N a)
(ii) If (als) = and AM (s, > 0, ie, (s, vio-
T (als))
(7)
NE (s)
lates the constraint:
Vuic - vene(() (s) >0. 0.
where x = =m)
(4)
4.3. Error Propagation
(iii) If (als) = 0 and AM (s,a) S i.e. (s, is in the non-critee non-critical region:
Building on the above estimations and the definition of cost functions, we obtain a set of estimated feasible cost functions. Next, we investigate the estimation error for the feasible cost function and analyze its underlying sources.
Q ( ()) - Muee (8)50 S.
(5)
Lemma 4.5. (Feasible Cost Set Explicit). Under Assump- tion 4.3, c. is feasible cost function for an ICRL problem B. if and only if there exists Ç E B500 and V E _
Lemma 4.6. (Error Propagation). Let & xM and Fb = FM be two ICRL problems where M (MPPT) U UT. For any c E Cpp satisfying c = A C (E - PT)ee and e [0, Cmux) SSA, there exists C Cap and ē E [0, Cmax] SXA, V(8,a) ES x A:
c c= A (E
(6)
where E : R$ + BSSA is the expansion operator that satisfies (F.)(s, a) = f()). Furthermore, || (+)(s))ss &
2(x(s, a) +X)
Ic- (s. I (x(s, a) + +x)/Cmma where x= =
(8)
Ciax 77 7) and IK = Cinax/ maxx (s.a) A
a x(s and
Intuitively, the first term in (6) penalizes constraint-violatingg actions that deviate from the expert's policy yet achieve higher rewards (i.e., A E M as) 0). This penalty ensures these actions violate the constraint in (2). The second term ve E R can be interpreted as cost-shaping operator that plays the role of translating the Q-function values by a fixed quantity. By utilizing the Bellman equation, we obtain
= (0).0)>
(s. AMM" Am
- M
((s,u).
x(s, a) is the distance at (s, between the ground-truth cost function and a pseudo-estimated cost function with the same { and VG, but does not necessarily fall into [0, mmax]. The first part of x(s, a) reflects the estimation error of the transition model, while the second part depends on the esti- mation error of the advantage function, which can be further decomposed as follows:
that (s) 0 for hard constraints and (*()) V (s) for soft constraints. Proofs of the above and the following theoretical results can be found in Appendix C.
Lemma 4.7. Let Φ = =M, and 9 (M, be two ICRL problems. Then, we have
4.2. Estimating Transition Dynamics and Expert Policy
Recall that our primary objective is to minimize the estima- tion errors of feasible cost functions. To obtain this error, we first introduce how we estimate the transition dynamics and the expert policy. We consider a model- setting where the agent strategically explores the environment to learn the transition dynamics and the expert policy. We record the returns from querying a state-action pair (s, a) by observing a next state s' ~ P(-|s, a), and the preferences of expert agents a ~ (+(ss) in each visited state. At iteration k, we denote by (s, a, s') the number of times we observe the transition tuple (s, a, s'). We further denote mg,s, a) = -Eves (s, a, s'). At iteration k we denote by n
A A M
(9)
27
-P) M
7(1 7(1+)) 1 1-7
( (x- VM v
1 1-
To relate these error sources to the sample size, we derive confidence intervals for the transition model and expert policy using the Hoeffding inequality (see Lemma C.5). We show that the true transition model and expert policy lie within these intervals with high probability. Based on these results, we derive an upper bound on the estimation errors of feasible cost functions and prove that this upper bound is guaranteed with high probability as follows:
F (s.a) a) the number of times we observe action a as
4

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Lemma 4.8. Let 8 E (0,1), 1), with probability at least 6, for any pair of cost functions e E Cip and Tk Cap. at iteration k, we have
Unlike most existing ICRL works (Papadimitriou al., 2023; Liu al., 2022a; Yue et al., 2025) that rely on generative model for sample collection, our exploration strategy must determine which states need more frequent visits and how to traverse to them from the initial state. We propose a Bounded Error Aggregate Reduction algorithm (BEAR, Section 5.1) and Policy-Constrained Strategic Exploration algorithm (PCSE, Section 5.2) for solving ICRL problems in Algorithm 1.
[e(s, a) - (s a)l S Cn(s,a)=
(10)
20
(e(s,a)
+ max (0,0)
(((a,)) 2 (s,0)
2N2 (s,0)
min
Cmax
a 1+
Umax
(V
2N (s,a)
(2lo,a)
+ max (s,a)
(e(o,a) 2N2 (s,a)
7Cmax Binox (3+ / maxt
A +(1-7))
Algorithm 1 BEAR and PCSE for ICRL in an unknown environment
where
and
(1-7)²
4 (8, log 36SSANNN (s.a))*
Input: significance ō (0, 1), target accuracy e, maxi- mum number of samples per iteration Amaxi
Intuitively, as the sample size grows, Cs (s, a) decreases, progressively reducing the estimation errors of feasible cost functions towards zero. However, this error does not nec- essarily need be infinitesimal for the estimated feasible cost functions to sufficiently explain the expert's behavior. Next, we define Probably Approximately Correct (PAC) optimality criterion for the estimated cost. The estimated feasible set Cj. is considered "close" to the exact feasible set Cap, if for every cost function e E Cz., there exists one estimated cost function è E Cg. such that their O-functions diverge within E, and vice versa.
Initialize k + 0, c --qi
while E > E do
Solve RL. problem defined by Mc to obtain the ex-
ploration policy us:
Solve optimization problem in (15) to obtain the explo- ration policy ıк:
Explore with Ty for nhe episodes; For each episode, collect 1mmax samples from S x A:
Update accuracy EX-1
max C++1 a)/(a (1))/(117)) Update accuracy EK-1 = 11 (ISXA - -2PTx)- Update T and Pri+i in (7); k 4- ki +
Definition 4.9. (Optimality Criterion). Let Cp be the ex- act feasible set and C33 be the feasible set recovered after observing 2 0 samples collected in the source M and R. We say that an algorithm for ICRL is (2,8,n)-comme ncoccrrectt if with probability at least 1 - 6, it holds that:
end while
M a) QuiLa a)/
inf sup EcC Mul
S e, Ve E Cpp, 5.1. Exploration via Reducing Bounded Errors
To fulfill the optimality criterion in Definition 4.9, we begin by relating it to the cost estimation error.
inf sup eECp a ETE x Muu
Q (Mu a)- Q a)
Se, Vo E Cpp
Lemma 5.1. Let en =1Q Quiie Mue. (s,a)) define the optimality error of state-action pair (s, a) at iter- ation lo for x² E &T'Mue We upper bound it as follows:
where x² is an optimal policy in MUJ and #* is an optimal policy in MUM U.
The criterion ensures estimation errors of feasible cost func- tions do not compromise the optimality of the expert policy. The first condition ensures completeness, requiring the re- covered feasible cost set to track every true cost function. The second condition guarantees that there exists a true cost function close to every recovered cost function. This pre- vents the recovery of an excessively large feasible set that would overly prioritize completeness.
[ a; π l|o S 11 (IsxA-
(11)
We show in the lemma below that the exploration algorithm converges (satisfies Definition 4.9) at iteration & if either one of the following statements is satisfied:
Lemma 5.2. Let Cqs be the ground-truth feasible set and
Cz. be the recovered feasible set after k iterations. The conditions of Definition 4.9 are satisfied if either of the following statements are satisfied:
5. Efficient Exploration for ICRL
In this section, we introduce two algorithms for efficient exploration, addressing the challenge of collecting high- quality samples through interactions with the environment, thereby increasing the accuracy of our cost set estimations.
max Cx a) Se; (8.0)
(12)
(2)
T max max mn (TSXA 7PPT) -Cal Se, (13) well &
5

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
)
5.2. Exploration via Constraining Candidate Policies
n TiMua CEC'p
ntt =
n CEC
I
Muua
The above exploration strategy has limitations, aims to minimize uncertainty across all policies, whereas it could be more effective by focusing reducing uncertainty only for potentially optimal policies. To address this, we propose PCSE for ICRL in Algorithm (highlighted in purple). At each iteration, we intentionally restrict the search to policies that yield a value function close to the estimated optimal one regarding both rewards and costs. This allows us to focus solely on plausibly optimal policies, and we formulate the optimization problem follows:
Based on (12), we introduce BEAR in Algorithm 1 (high- lighted in teal), which derives the k-th iteration exploration policy Ty. by solving the RL problem where the reward func- tion = Cx- In practice, any RL solver can be applied to determine the exploration policy. Next, analyze the sample complexity of BEAR.
Sample Complexity. Due to stochasticity in the environ- mental dynamics, we employ pseudo-counts to calculate the number of visitations to state-action pairs during traver- sal induced by the exploration policy. Let (s, also), h E [maa be the probability of state-action pair (s, a) reached in the h-th step following policy Fı IIMe, starting in We can compute it recursively
Ek+1 sup
1o (ISXA P
(15)
MoEA
mEll
S.t.
HIg n III
state sg-
I1
T sup MoE
uD (ve,
MAUes - -Va
Mauae) S dextee
(s, also) == ([
-vna)) T. (((yrr - 2 Nla
I
π inf HOEAS
h+1 (s, also) = Σ (r(as)) (m Th
Mr
where R2 2=RRax (1-?)²
[| PPT-Po + (1-nss ||(TT~ 77)
Definition 5.3. (Pseudo-counts). We introduce the pseudo- counts of visiting a specific state-action pair (s, a) after k iterations as:
The rationale in I can be attributed to two aspects: 1) Hgg constrains exploration policies visit states within an addi- tional cost budget, thereby ensuring resilience to estimation error when searching for optimal policies; 2) IT states that exploration policies should focus on states with potentially higher cumulative rewards, where possible constraints lie. As the estimation error decreases, the gap (i.c., Rg) also diminishes, eventually converging to zero, which ensures the optimality of constrained policies. We have shown in Appendix C. that optimal policies in basic environments are captured by llg.
k (s.o))))
Nx(8, = 40
Similar to (7), we define N a) = max(0, (s, a)}. The following lemma provides an upper bound on the actual error in terms of the error induced by pseudo-counts.
Lemma 5.4. With probability at least 1 - 6/2, as, S x A x [maax] x N+, we have:
To solve the optimization problem (15), we express its La- grangian objective as A(p
min { {o)
(s,aa)
)
(s,
Cmax (ov 2N (s,a)²
(14)
No. (s,
(D CK+1) X2 22 (1--))(V7 + RR) (03u:r)) Mr
where Ex (8) log(365 (N, and à max(a, ).
+ (1(1-))(VV) Maue, + 4eR - 22) + (03n (pin:())
Subsequently, we derive the sample complexity of BEAR:
where X = [11, A2)" records two Lagrangian multipliers.
Theorem 5.5. (Sample Complexity of BEAR). If Algo- rithm BEAR terminates at iteration K with the updated accuracy K, then with probability at least - 5, it fulfills Definition 4.9 with a number of samples upper bounded by
The dual problem of (15) can be defined as
min max L(pM A). PM A20
(16)
To solve this dual problem, we assume that Slater's condi- tion is fulfilled, and we follow the two-timescale stochastic approximation (Borkar & Konda, 1997; Konda Tsitsiklis, 1999). The following two gradient steps alternated until convergence.
n E ( (2(2Cmaax -EReaxxEKKK -Ex(1-7))
(1 (1- 7E C2
max
The above theorem has taken into account the sample com- plexity of the RL phase. In fact, further improvements can be made to enhance the algorithm's performance.
PMM = PMM, - -ag a.(TT A+) + Wk),
6

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
AR+1 d + by AR) ) U&),
Gridworld-1
Gridworid-22
Grsdworld-3
Grsdwurid-
where coefficients dg < bg. satistying Ex as = -b oo, Eo < Do and Σ b < oc; WA and Us are two zero-mean noise sequences. Under this condition, the con- vergence is guaranteed in the limit (Borkar, 2009). At each iteration k; the exploration policy is calculated as: [T(aas) = ( aa/ Ea (s.a)
0
0
Figure 2. Four different Gridworld environments with white, red. and black markers indicating the starting, target, and constraint locations, respectively.
Sample Complexity. The convergence condition for PCSE for ICRL. given by (13), determines its sample complexity. To present this result, we additionally define the cost advan- +. (s), in which ē E arg ceC max(s.))ESx |c(s, a) cx (s,a)l the cost function in the true feasible cost set Cap closest to the estimated cost function čg (s, a) at iteration K.
tage function as A (8, = Q (s MLE
Mus
Experiment Settings. The evaluation metrics include: 1) discounted cumulative rewards, which measure the opti- mality of the learned policy; 2) discounted cumulative costs, which assess the safety of the learned policy; and 3) Weighted Generalized Intersection over Union (WGloU) (refer to Appendix D.2 for details), which robustly evaluates the similarity between inferred cost functions and ground- truth cost functions.
Theorem 5.6. (Sample Complexity of PCSE). If Algoritium PCSE terminates at iteration K with accuracy к and the accuracy of previous iteration is s K-1, then with probability at least 1 - 8, it fulfills Desinition 4.9 with the number of samples upper bounded by
n S Ô min+ {ō
0 (2C -Ex(1-2))
Comparison Methods. We compare BEAR and PCSE with four other exploration strategies: random exploration, e-gredyy exploration, maximum-entropy exploration, and upper confidence bound exploration.
(1 - 7)88 C2 max
0² (6)x--1+
min(s,a) (A (8)
2
Mua
6.1. Evaluation under Discrete Environments
The first term matches the sample complexity of the BEAR strategy since the convergence of BEAR is stricter than PCSE, i.e. (13) is always satisfied if (12) is satisfied. As a result, the sample complexity of BEAR constitutes lower bound for that of PCSE. The second term depends the ratio (65x-1 + <)/Ex and the minimum cost advantage On one side, the ratio depends on both Timax and ne. If the two values are high, the ratio is high because the accuracy reduces faster from itcration K K-1to to K with more collected samples. Otherwise, the ratio is small because the accuracy remain similar between two iterations. A smaller 6, namely a tighter constraint, benefits the sample efficiency. On the other side, the cost shows that the larger the
Figure 2 illustrates four discrete environments, each charac- terized by distinct constraints. The expert policy is trained under ground-truth constraints, while two ICRL algorithms and four baselines operate without knowledge of these con- straints. These environments stochastie, with the envi- ronment executing randomly sampled action with proba- bility 0.05. Figure 3 and 5 (in Appendix) demonstrate the training process of three metrics for six exploration strategies in four Gridworld environments, along with the performance of expert policy (represented by the grey line). It can be shown that the performance of the optimal policy in M Uē gradually converges to the performance of the op- timal policy in MUc. Also, we find that PCSE (represented by the red curve) converges the fastest among the six explo- ration strategies. In Gridworld-2 and Gridworld-4, WGIoU converges to a degree of similarity less than (ground-truth) This because some of the ground-truth constraints in non-critical regions, and ICRL infers the minimal set of con- straints required to explain expert behavior. We demonstrate constraint learning processes of six exploration strategies for four Gridworlds in Appendix Figure 7, 8, 9, and 10, respectively. These learned constraints are recovered as vis- iting these states leads to higher cumulative rewards, while other unrecovered constraints do not impact the optimality of expert hehaviors.
function min(...) A MUE
advantage function min A "Mua suboptimality gap, the easier to infer the constraint.
6. Empirical Evaluation
We empirically compare our algorithms against other meth- ods in both discrete and continuous environments, where the agent navigates from a starting location to a target location (receiving positive reward) while satisfying the constraints. Our implementation of code for discrete environments is adapted from (Liu et al., 2023), and for continuous environ- ments, it adapted from (Lazcano et al., 2024).
7

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Fritworid4
kanden
Pandain
0,75
ICAn
1.00
ECAn
0.50
Disounte Comulstie
PCSC
kipar
14
PCBC
kxpar
0.64
0.050
0.62
2.00
0.00
-2021
120
0..0
-0.05%
350
0.62
neeittoon
Iterationn
Ite Iterattoon
Iteratiion
Random DEAR cocceity
Randam RCAR
0.5
REAR
Rander
Random
ZCAR
Dicountes Comuishie
1.5
Rapirt
0.3
0.5
1.0
0.2
0.4
022
0.0
-0/2
150
362
75
100
125
X50
135
300
125
150
202
25
170
175
Iteration
Roration
Itoration
itoration
0.5
WGou
2.0
0.5-
0.5-
20MR cinnsyy
2CAR
-0.5
22MR
-0.
DCAR greeds
-18
-10
01
1.6
76
25
55
36
106 Keradon
125
15
10s
235
25
150 Iteration
12%
15
10%
230
25
95
1:0 iteration
13%
255
Iteration
Figure 3. Training curves of discounted cumulative rewards (top), discounted cumulative costs (middle), and WGIoU (bottom) for four exploration strategies in four Gridworld environments, respectively.
6.2. Evaluation under Continuous Environments
fectiveness of our method, we perform empirical evaluations in various environments.
Figure 4 (leftmost) shows the Point Maze environment, where the green agent has a continuous state space. The agent's goal is to reach the red ball inside the maze with pink walls. The environment is stochastic due to the noises im- posed on the observed states. Figure 4 (middle left) demon- strates the inferred constraints (represented by blue dots) obtained through PCSE, with the center of the entire maze at (0, 0). Figure 4 (middle right and rightmost) reports the discounted cumulative rewards and costs during training.
Limitations and Future Work. As is also pressing chal- lenge in the field, our method faces the limitation of strug- gling to scale to problems with large or continuous state spaces. This is due to the fact that our sample complexity is directly dependent on the size the state space, and real- world problems often involve large or continuous spaces. Several future research directions warrant attention. First, extending the analysis to finite-horizon settings and deriv- ing lower bounds for sample complexities would provide more comprehensive understanding of the performance limits. Second, investigating the transferability of feasible constraints across different environments would be valuable in determining the generalizability of our approach. Addi- tionally, relaxing the assumption that the expert policy is safe and reward optimal, either to a safe expert policy (not necessarily optimal) offline expert demonstrations. would be an interesting direction for future work. We believe it is also valuable to investigate how the sub-optimality of expert agents influences inverse constraint inference and transferability. Finally, is also intriguing the hypothesis space of admissible constraint functions can be restricted in the first place, leading to more practical, scalable, and efficient constraint inference.
For all the experiments discussed above, please check Ap- pendix D and E for more experimental details.
7. Conclusions
Summary. This paper introduces a strategically efficient exploration framework for ICRL problems. We conduct the- oretical analysis to investigate the inffuence of estimation rors in expert policy and environmental dynamics the timation of feasible constraints. Building upon this, we pro- pose two exploration algorithms, namely BEAR algorithm and PCSE. BEAR explores the environment to minimize the aggregated bounded error cost estimations. Moreover, PCSE algorithm goes a step further by constraining the ex- ploration policies plausibly optimal ones, thus enhancing the overall sample efficiency. We provide tractable sample complexity analyses for both algorithms. To validate the ef-
8

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Infened Lumsirantts
Point More
Paint Maze
Gouudd mi rocntier
KCSE BEAA
PCSE BEAA
Decounted comuustive Resmants
Ca egrnedy
Discoutted Cum weualtttree Costs
eognedy
Mox-entmoy
Hex-mnmroy
924
2.4
t2
300
Beeshion
Figure 4. Point Maze environment (leftmost), inferred constraints (middle left), discounted cumulative rewards (middle right) and discounted cumulative costs (rightmost).
8. Discussions
One critical issue is the exploration challenge where algo- rithms need to specify where and how to explore at each iteration. Another key difficulty is the estimation of the ground-truth expert policy, which is hard to obtain in an online setting. potential solution involves extracting the expert policy from offline datasets of expert demonstrations. However, these datasets often contain mix of optimal and sub-optimal demonstrations, leading to sub-optimal expert policies. Addressing this issue could involve i) treating the dataset as noisy and applying robust learning algorithms designed to handle noisy demonstrations or ii) combining offline demonstrations with online fine-tuning, where fea- sible, refine the learned policy. Finally, the scalability of learning in continuous spaces is frequeetly hindered by the curse of dimensionality. Dimensionality reduction tech- niques can mitigate this challenge by simplifying state and action representations while retaining the features essential for effective policy learning.
Set-recovery Framework. In contrast to prior ICRL meth- ods, our set-recovery framework defers the commitment to specific constraints until a later stage, thereby exposing the fundamental complexity of inverse constraint inference. Building on this perspective, we characterize two distinct modes of constraint selection for the downstream optimiza- tion procedure on a novel task. For hard constraints, all feasible constraints in the set equivalent for novel task, the cost function value does not matter (c(s, a) and c(s, a) = 2 both prohibit (s, a.). Thus, any feasible constraint can be selected for transfer. For soft constraints, feasible constraints in the set differ for a novel task. The value of each cost function matters due to task differences in dynamics and rewards. Therefore, the generalizable learned constraints should come from the intersection of feasible sets from old and novel tasks. The selection criterion should depend on differences in dynamics and rewards.
Affine Space Perspective. Linear algebraic analyses pro- vide a more rigorous and inherent framework for this set- recovery approach, making them valuable for investigat- ing ICRL theories. For instance, by defining subspace u im(E- Pr), the cost functions within a feasible cost set become equivalent on the quotient space S /u. Furthermore, we can measure the distance between the re- covered and expert costs within this quotient space.
A Akknowledgments
This work is supported in part by Shenzhen Fundamen- tal Research Program (General Program) under grant JCYJ202308071 111711142000 Guangdong-Shenziie Joint Re- search Fund under grant 2023A1515110617, Guangdong Basic and Applied Basic Research Foundation under grant 2024A1515012100 and Guangdong Provincial Key Labora- tory of Mathematical Foundations for Artificial Intelligence 2203B12120100000
Scaling to Practical Environments. Sample complex- ity analysis has primarily focused on discrete Mate-action spaces (Agarwal al., 2019). Existing algorithms for learn ing feasible sets (Metelli et al., 2023; Zhao al., 2023; Lazzati et al., 2024a) struggle to scale effectively to prob- lems with large or continuous state spaces. This limitation arises because their sample complexity depends directly on the size the state space, and real-world problems fre- quently involve large or continuous spaces. Scaling feasible set learning to practical problems with large state spaces re- mains pressing challenge in the field (Lazzati al., 2024b).
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. We do not see any direct negative consequences of our work.
9

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
References
Hugessen, A., Wiltzer, H., and Berseth, G. Simplifying constraint inference with inverse reinforcement learning. In The Thirty-eighth Annual Conference Neural Infor- mation Processing Systems (NeurlPS), 2024.
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Rein- forcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA. USA, Tech. Rep, 32, 2019.
Jin, C.. Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is Q-learning provably efficient? Advances in neural infor- mation processing systems (NeurIPS), 31, 2018.
Amin, S., Gomrokchi, M., Satija, H., van Hoof, H., and Pre- cup, D. A survey of exploration methods in reinforcement learning. CoRR, abs/2199.001577 2021.
Jin, C., Liu, Q., and Miryoosefi, S. Bellman eluder di- mension: New rich classes of RL problems, and sample- efficient algorithms. Advances in Neural Information Processing Systems (NeurIPS), 34:13406-13418, 2021.
Baert, M., Mazzaglia, P., Leroux, S., and Simoens, P. Max- imum causal entropy inverse constrained reinforcement learning. Machine Learning, 2023.
Balakrishnan, S., Nguyen, Q. P., Low, B. K. H., and Soh,
Kalagarla, K. C., Jain, R., and Nuzzo, P. A sample-effiiient algorithm for episodic finite-horizon MDP with con- straints. In Proceedings of the AAAI Conference on Artifi- cial Intelligence, volume 35, pp. 8030-8037, 2021..
H. Efficient exploration of reward functions in inverse reinforcement learning via bayesian optimization. In Neural Information Processing Systems (NeurIPS), 2020.
Bellemare, M. G., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. Unifying count-based explo- ration and intrinsic motivation. In Proceedings of the International Conference on Neural Information Process- ing Systems (NeurIPS), pp. 1479-1487, 2016.
Kaufmann, E.,, Ménard, P., Domingues, D., Jonsson, A., Leurent, E., and Valko, M. Adaptive reward-free exploration. In Algorithmic Learning Theory, pp. 865- 891. PMLR, 2021.
Kim, D. and Oh, S. Efficient off aff-policy safe reinforcement learning using trust region conditional value at risk. IEEE Robotics and Automation Letters (RAL), 733)76444-7511, 2022.
Borkar, V. S. Stochastic Approximation: A Dynamical Systems Viewpoint, volume 48. Springer, 2009.
Borkar, V. S. and Konda, V. R. The Actor-Critic Algorithm as Multi Time--Saeeeee Stochastic Approximation. Sadhana, 22(4):525-55 1997.
Kim, K., Swamy, G., Liu, Z., Zhao, D., Choudhury, S., and
Wu, S. Z. Learning shared safety constraints from multi- task demonstrations. Advances in Neural Information Prucessing Systems (NeurIPS), 36, 2024.
Chan, A. J. and der Schaar, M. Scalable bayesian in- verse reinforcement learning. In International Conference on Learning Representations (ICLR). OpenReview.net, 2021.
Konda, V. and Tsitsiklis, Actor-critic algorithms. In Advances Neural Information Processing Systems (NeurIPS), volume 12, 1999.
Chou, G., Berenson, D., and Ozay, N. Learning constraints from demonstrations. In Workshop on the Algorithmic Foundations of Robotics, WAFR 2018, volume 14, pp. 228-26 245. Springer, 2018
Krasowski, H., Wang, X., and Althoff, M. Safe reinforce- ment learning for autonomous lane changing using set- based prediction. In 23rd IEEE International Conference Intelligent Transportation Systems (ITSC), pp. 1-7. IEFE, 2020.
García, J. and Shafie, D. Teaching a humanoid robot to walk faster through safe reinforcement learning. Engineering Applications of Artificial Intelligence, 88, 2020.
Ladosz, P., Weng, L., Kim, M., and Oh, H. Exploration in deep reinforcement learning: A survey, Inf. Fusion, 85: 1-22, 2022.
Gaurav, A., Rezaee, K., Liu, G., and Poupart, P. Learning soft constraints from constrained expert demonstrations. In International Conference on Learning Representations (ICLR), 2023.
Lazcano, R., Andreas, K., Tai, J. J., Lee, S. R., and Terry, J. Gymnasium robotics, 2024. URL http:///gtthu..cooooo www.///////aaaaaaa Foama--ounnatiion Gymnas um Robotics. Lummaasi-RRoboiico..
Gu, S., Yang, L., Du, Y., Chen, G., Walter, F., Wang, J., Yang. Y., and Knoll, A. C. A review of safe reinforcement learning: Methods, theory and applications. IEEE Trans. Pattern Anal. Mach. Intell. (TPAMI), abs/2205.10330, 2022.
Lazzati, F. and Metelli, A. M. Learning utilities from demon- strations in Markov Decision Processes. arXiv preprint arXiv:2409. 17355, 2024.
10

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Lazzati, F., Mutti, M., and Metelli, A. M. Offline inverse RL: New solution concepts and provably efficient algorithms. In Forty-first International Conference on Machine Learn- ing (ICML), 2024a.
Luo, Y., Liu, G., Duan, H., Schulte, O., and Poupart, P. Dis- tributional reinforcement learning with monotonic splines. In International Conference on Learning Representations (ICLR), 2022.
Lazzati, F., Mutti, M., and Metelli, A. M. How does in- verse RI. scale to large state spaces? A provably efficient approach. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2024b.
Malik, S., Anwar, U., Aghasi, A., and Ahmed, A. Inverse constrained reinforcement learning. In International Con- ference on Machine Learning (ICML), pp. 7390-7399, 2021.
McPherson, D. I.., Stocking, K. C., and Sastry, S. S. Max- imum likelihood constraint inference from stochastic demonstrations. In IEEE Conference on Control Technol- ogy and Applications, (CCTA), pp. 1208-1213, 2021.
Lindner, D., Krause, A., and Ramponi, G. Active explo- ration for inverse reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 35: 5843-5853, 2022.
Metelli, A. M., Ramponi, G., Concetti, A., and Restelli, M.
Lindner, D., Chen, X., Tschiatschek, S.,, Hofmann, K., and Krause, A. Learning safety constraints from demonstra- tions with unknown rewards. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2396. PMLR, 2024.
Provably efficient learning of transferable rewards. In International Conference on Machine Learning (ICML), pp. 1665-7676.1 PMLR, 2021.
Metelli, A. M. Lazzati, F., and Restelli, M. Towards theoret- ical understanding of inverse reinforcement learning. In International Conference on Machine Learning (ICML), volume 202, pp. 24555 245911. PMLR, 2023.
Liu, G., Luo, Y., Schulte, O., and Poupart, Uncertainty- aware reinforcement learning for risk-sensitive player evaluation in sports game. In Neural Information Pro- cessing Systems (NeurIPS), 2022a.
Miryoosefi, S. and Jin, C. A simple reward-free approach to constrained reinforcement learning. In International Conference on Machine Learning (ICML), pp. 15666- 15698. PMLR, 2022.
Liu, G., Luo, Y., Gaurav, A., Rezaee, K., and Poupart. P. Benchmarking constraint inference in inverse reinforce- ment learning. In International Conference on Learning Representations (ICLR), 2023.
Moskovitz, T., O' O'Donoguue, B., Veeriah, V., Flennerhag, S., Singh, S., and Zahavy, T. Reload: Reinforcement learning with optimistic ascent-descent for last-iterate convergence in constrained mdps. In International Conference on Machine Learning (ICML), pp. 35303-253333 PMLR, 2023.
Liu, G., Xu, S., Liu, S., Gaurav, A., Subramanian, S. G., and Poupart, P. A survey of inverse constrained rein- forcement learning: Definitions, progress and challenges. Transactions on Machine Learning Reseurch (TMLR), 2025.
Ng, A. Y., Russell, S., et al. Algorithms for inverse reinforce- ment learning. In International Conference on Machine Learning (ICML), volume 1, pp. 2, 2000.
Liu, S. and Zhu, M. Distributed inverse constrained rein- forcement learning for multi-agent systems. In Neural Information Processing Systems (NeurIPS), 2022.
Papadimitriou, D., Anwar, U., and Brown, D. Bayesian methods for constraint inference in reinforcement learn- ing. Transactions on Machine Learning Research (TMLR), 2023.
Liu, S. and Zhu, M. Meta inverse constrained reinforce- ment learning: Convergence guarantee and generaliza- tion analysis. In The Twelfth International Conference on Learning Representations (CCM),,023.
Qadri, M., Swamy, G., Francis, J., Kaess, M., and Bajesy, A. Your learned constraint is secretly backward reachable tube. arXiv preprint axXiv:2501.15618 2025.
Liu, Z., Zhang, Y., Fu, Z., Yang, Z., and Wang, Z. Learning from demonstration: Provably efficient adversarial policy imitation with linear function approximation. In Inter- national Conference on Machine Learning (ICML), pp. 14094-14138. PMLR, 2022b.
Qiao, G., Liu, G., Poupart, P., and Xu, Z. Multi-modal in- verse constrained reinforcement learning from a mixture of demonstrations. In Neural Information Processing Systems (NeurIPS), 2023.
Liu, Z., Lu, M., Xiong, W., Zhong, H., Hu, H., Zhang, S., Zheng, S., Yang, Z. and Wang, Z. Maximize to explore: One objective function fusing estimation, planning, and exploration. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Ramachandran, D. and Amir, E. Bayesian inverse reinforce- ment learning. In International Joint Conferences on Artificial Intelligence (ICCAI), volume 7, pp. 258.558-177 2586-2591, 2007.

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Rezatofighi, H., Tsoi, N., Gwak, J., Sadeghian, A., Reid, I,, and Savarese, S. Generalized intersection union: A metric and loss for bounding box regression. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 658-666, 2019.
theoretical perspective. In International Conference on Machine Learning (ICML., 2023.
Zhao, R., Xu, S., Yue, B., and Liu, G. Toward exploratory inverse constraint inference with generative diffusion ver- ifiers. In The Thirteenth International Conference on Learning Representations (ICLR), 2025.
Scobee, D. R. R. and Sastry, S. S. Maximum likelihood constraint inference for inverse reinforcement learning. In International Conference on Learning Representations (ICLR), 2020.
Simonelli, A., Bulo, S. R., Porzi, L., López-Antequera, M., and Kontschieder, P. Disentangling monocular 3D object detection. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 1991-1999, 2019.
Skalse, J. and Abate, A. Misspecification in inverse rein- forcement learning. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 37, pp. 15136- 23143,202.
Skalse, J. and Abate, A. Quantifying the sensitivity of inverse reinforcement learning to misspecification. Inter- national Conference on Learning Representations (ICLR), 2024.
Szepesvári, C. Constrained MDPs and the reward hypothe- sis, 2021.
Thomas, G., Luo. Y., and Ma, T. Safe reinforcement learn- ing by imagining the near future. In Neural Information Processing Systems (NeurIPS), pp. 11859-13869, 2021.
Wachi, A., Sui, Y., Yue, Y., and Ono, M. Safe exploration and optimization of constrained mdps using gaussian processes. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Xu, S. and Liu, G. Robust inverse constrained reinforce- ment learning under model misspecification. Forty-first International Conference on Machine Learning (ICML), 2024a.
Xu, S. and Liu, G. Uncertainty-awee aware constraint inference in inverse constrained reinforcement learning. In Interna- tional Conference on Learning Representations (ICLR), 2024b.
Yue, B., Wang, S., Gaurav, A., Li, J., Poupart, P., and Liu, G. Understanding constraint inference in safety-crit criticall inverse reinforcement learning. In The Thirteenth Interna- tional Conference on Learning Representations (ICLR), 2025.
Zhao, L., Wang, M., and Bai, inverse reinforcement learning harder than standard reinforcement learning?
12

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Appendix
Table of Contents
Notation and Symbols
14
Extra Related Works
14
C Proofs of Theoretical Results in the Main Paper
15
C.I Proof of Lemma 4.1
15
C.2 Proof of Lemma 4.4
16
C33 Proof of Lemma 4.5..
17
C.4 Proof of Lemma 4.6...
18
C.5 Proof of Lemma 4.7
19
C.6 Proof of Lemma 4.8
21
C.7 Proof of Lemma 5.1
23
C.8 Proof of Lemma 5.2
24
C.9 Uniform Sampling Strategy for ICRL with a Generative Model
25
C.10 Proof of Lemma 5.4
................................
27
C.11 Proof of Theorem 5.5
28
C.12 Theoretical Results on Policy-Constrained Strategic Exploration (PCSE)
29
C.13 Proof of Theorem 5.6
33
C.14 Optimization Problem and the Two- Twmeeimsceaee Stochastic Approximation
34
Experimental Details
36
D.1 Discrete Environment
36
D.2 Weighted Generalized Intersection over Union (WGIoU)
36
D.3 Continuous Environment
37
More Experimental Results
38
E.1 Gridworld Environments
38
E.2 Point Maze Environment
38
13

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
A. Notation and Symbols
In Table I, we report the explicit definition of notation and symbols applied in our paper.
Table I. Overview of notation and symbols
Symbol
Name
Signature
M
CMDP without knowing the cost (CMDP) (c)
(S, A, P,, (S,A, P,
MUc
CMDP
S A
State space
Action space
Pr
Transition dynamics
AS
SxA
so
Initial state
S
Policy
n F
Expert policy
r
Reward function
10. R Rimax
SxA
c
Cost function
[0, max
SXA
Threshold of constraint or budget
RS
Vi
Reward state-value function for of in M Reward action-value funetion for of in M Reward advantage function for r of π in M
RS
Q
RSxA
A a
RSxA
M
Cost state-value function for c of ı in M U Cost action-value function for e of x in MUc Ground-trun feasible cost set Recovered feasible cost set State action pair visitation frequencies Occupancy measure of π in M
RS
Mue
Q Mue
RSxA
Cp
/
Cpp
A (8, a|so)
AAA
PM
ASA
Target accuracy
IR+
8
Significancy
(0, 1)
ne
Number of exploration episodes
N+
E
Expansion operator
R - RSXA
IsxA
Identity matrix on S x A
Is
Identity matrix on S
[a]
Set that contains integers from 0 to a
{0, 1, a). E
B. Extra Related Works
Sample Efficiency. Sample-efficient algorithms have been explored across various RL directions, yielding significant advancements. To find the minimal structural assumptions that empower sample-efficient learning, (Jin et al., 2021) introduced the Bellman Eluder (BE) dimension and proposed sample-efficient algorithm for problems with low BE dimension. (Liu et al., 2024) introduced sample-efficient RL framework called Maximize to Explore, which reduces the computational cost and enhances compatibility. In the field of imitation learning, (Liu et al., 2022b) addressed both online and offline settings, proposing optimistic and pessimistic generative adversarial policy imitation algorithms with tractable regret bounds. In the realm of model-free RL., (Jin et al., 2018) developed a Q-learning algorithm with upper confidence bound exploration, achieving a regret bound of /T in episodic MDPs. (Wachi et al., 2018) modeled state safety values using Gaussian Process and proposed a more efficient approach to balance the trade-off between exploring the safety function, exploring the reward function, and exploiting knowledge to maximize rewards. In the context of (CRL), (Miryoosefi & Jin, 2022) bridged reward-fire frreeeeffeeeee RL and CRL, providing sharp sample complexity results for CRL in tabular MDPs. Focusing on episodic finite-horizon Constrained MDPs (CMDPs), (Kalagarla et al., 2021) established probably approximately correct guarantee on the number of episodes required to find a near-optimal policy, with a lincar dependence on the state and action spaces and a quadratic dependence on the time horizon. From a meta-learning perspective, (Liu & Zhu, 2023) framed the problem of learning an expert's 's reward function and constraints from a few demonstrations as bi-level optimization, introducing a provably efficient algorithm to learn meta-prior over reward functions and constraints. In terms of sample
14

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
efficiency in IRL, (Lazzati al., 2024a) redefines offline IRL by introducing the feasible reward set to address limited data coverage, proposing approaches ensure inclusion monotonicity through pessimism. (Lazzati & Metelli, 2024) extends IRL to Utility Learning, introducing framework for capturing agents' risk attitudes via utility functions. (Lazzati et al., 2024b) tackles scalability in online IRL by introducing reward compatibility and a Saate-space-nndeeeddee Linear MDPs, bridging IRI. and reward-free exploration. For misspecification in IRI., (Skalse & Abate, 2023) provides a framework and tools to evaluate the robustness of standard IRL models (e.g., optimality, Boltzmann rationality) to misspecification, ensuring reliable inferences from real-world data. (Skalse & Abate, 2024) quantifies IRL's sensitivity to behavioral model inaccuracies, showing that even small misspecifications can result in significant errors in inferred reward functions.
algorithm for
Constraint Inference. Constraint learning in reinforcement learning has advanced significantly to address safety require- ments and extend application scenarios. Chou et al. (2018) introduced a method to infer shared constraints across tasks using safe and unsafe trajectories, leveraging hit-and-run sampling and integer programming with theoretical guarantees. Kim & Oh (2022) proposed a sample-efficient RL method with CVaR constraints that addresses distributional shift via surrogate functions and trust-region constraints, achieving high returns and safety in complex tasks. To ensure stable convergence, Moskovitz et al. (2023) developed ReLOAD, which guarantees last-iterate convergence and overcomes limitations of gradient-based methods in CRL. For scenarios with unknown rewards and dynamics, Lindner al. (2024) introduced CMDP method that constructs a convex safe set from safe demonstrations, enabling task transferability and outperforming IRL-based approaches. Kim et al. (2024) extended IRL. framework to infer tighter safety constraints from diverse expert demonstrations, addressing the ill-posed nature of constraint learning and enhancing multi-task generalization. These prior works either require multiple demonstrations across diverse environments or rely on additional settings to ensure the uniqueness of the recovered constraints. In contrast, our approach infers a feasible cost set encompassing all cost functions consistent with the provided demonstrations, eliminating reliance on additional information to address the inherent ill- ill-posedness of inverse problems.
Bayesian IRL. In Bayesian IRI., posterior sampling over reward functions serves as foundational mechanism to guide policy inference (Ramachandran & Amir, 2007). In contrast, PCSE shifts the focus from reward estimation to constraint- based reasoning by leveraging a structured policy set to guide exploration. Additionally, Balakrishnan et al. (2020) employed Bayesian optimization to facilitate active exploration of reward functions in IRL. PCSE extends this idea to the ICRL setting by actively exploring constraint structures rather than rewards, and crucially, it removes reliance on generative models. This design directly addresses scalability limitations highlighted by (Chan & van der Schaar, 2021). where traditional Bayesian IRL methods relying on Markov Chain Monte Carlo (MCMC) sampling exhibited poor scalability in high-dimensional state spaces.
C. Proofs of Theoretical Results in the Main Paper
In this section, we provide detailed proofs of theoretical results the main paper.
C.1. Proof of Lemma 4.1
Proof. If neither case happens, i.e., Ep Pr Ei 7'c(se, ai) < c and 3 a' E A that satisfies both a' & 2
and Ana R M (8,a') > O, we can always construct a new policy, which only differs from the expert policy T in state
0 a a-=a a'
s. as n' <a(sss =
(1 1, a~ There must 3 f e (0,1) that uses some (or all) of the leftover budget T = e
Eee rc((s,,))) ai) while having a larger cumulative reward, which makes π F not an optimal policy. This makes a contradiction.
E E Pr
The existence of such 0 can be proved as follows. By recursively using the Bellman Equation, we can obtain
Eno VMue [5o) a(Pr. B 7, + ( F 7. c) Ey [Q af. of)].
(17)
where coefficients 2 0, B > 0. B can not equal to 0, since state s has to be visited with at least some probability, Otherwise, we do not need to explain (s). Note that if Qua a') < E,e Q a afi] T' is a strictly better policy than the expert policy for any 0 E (0, 1] (larger rewards with equal or less costs). This clearly makes a contradiction. Hence,
15

---

must be satisfied. On one hand, if e is feasible, (NTC((s a) > (s On the other hand, any cost function E [0, (maxx that satisfies Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
we focus on Quee(s, > E,
In this case, we can always obtain a 0 > 0, by letting
x, .7,)) & Buo [Vauee (8o)] a Th .2.
_
[s + AQ (11 -1-8) -0)
(18)
where 7' T0, denotes the leftover budget after applying x/. By subtracting Eq. (17) from Eq. (18), we have A QMuu(s, a') > E, (.))
(19)
Quat B(PT, B 7. (uuc(,, Exz Me [di]]
1Q
With this analysis, if A as, > 0 which indicates 2) of Lemma 4.1 is not satisfied 1) must be satisfied,
(Moo(s,))) > Ey"" QNuuo aF) Viuue (s) suffices to let Byo,"" 2'c(s, > with x" only dif- fers from Th state where N" (s) d', which is constraint- condition.
C.2. Proof of Lemma 4.4
Proof. In this proof, distinguish two cases according to Assumption 4.3. In the first case, the constraint (2) is hard, i..., c O.
(i) By definition of expert policy n², we have (s) = O. On one hand, c is feasible, vox. = E, Q 0.
Also, since c E [0, Caaaamaxxxx SSA,, Qar"" 2 0. As a result, Q = va* On the other hand, any e [0, Cmax] S that satisfies M = V makes _ an optimal policy under this condition.
(ii) By definition of expert policy Th, we have Mur O. On one hand, since AM (s, a) > O, if c is feasible,
Mye (s, a) 0, otherwise F5 is not optimal. On the other hand, any cost function [0, Cmaax] SS ] that satisfies
(s,aa a) > 0 Viuue (s) ensures action violates the constraint, and makes Th optimal policy under this condition.
8
R (iii) By definition of expert policy E, we have VALLe = 0. On one hand, since A (8,4) s O, any c E [0, Cmax S ensures the expert's optimality. However, in terms of the minimal set Cpp in Definition 4.2, c(s. = and
VMLL (s). On the other hand, any c(s,a) E [0, Cimax SxA that satisfies Qu a) Vea ensures F an optimal policy under this condition.
(s
a)
In the second case, the constraint in (2) is soft, i.e., > O, and the expert policy is deterministic.
(i) Since the expert policy F is deterministic, we have (u a) = VaLi (s). On one hand, is feasible, Q a) =
veaf Mu. (s). On the other hand, any c E [0, Cmax] SxA that satisfies (M a) = vcx (s) makes E an optimal policy under this condition.
Veri 8 (s) suffices to let (ii In this case, since A (s,a) > 0, situation 2) of Lemma 4.1 is not satisfied. As a result, 1) of Lemma 4.1
E "Ho,T",1" Pr Ere 7'((s1, ai)
(s, > Vortf( ensures action violates the constraint, and makes T an optimal policy under this condition. E (iii On one hand, since A (s < 0, any relationship between Q (s.a) and Verie (s) ensures the expert's ss optimality, However, in terms of the minimal set Cyp in Definition 4.2, Q (8,a) a) S Voru (s). On the other hand, S
ensures F an optimal policy under this condition. any c C [0, Cmaxx] Sxx that satisfies Q < V
16

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
C.3. Proof of Lemma 4.5
Lemma C.I. Let Φ (M, x) be an ICRL problem. Q-function satisfies the condition of Lemma 4.4 if and only if there exist Ç A and V 2200 such that:
Qiuvc = A -V; M
(20)
where the expansion operator E satisfies (Ef)(s, = f(s).
Here, the term Ç ensures 1) (when A' E > 0) the constraint condition in (2) is violated at (s,a) pairs that achieve larger rewards than the expert policy, and 2) (when M I 0) only necessary cost functions are captured by feasible cost set Cg..
"
Proof. We prove both the 'if" and 'nnly if" sides.
To demonstrate the "if" side, can easily see that all the Q-functions of the form (Muo(s, a) A' (()
(V*(s) satisfies the conditions of Lemma 4.4 in the following:
1) Let s E S and a E A such that x (als) > O, then we have (Mu a) = (s) = (s). This is the condition (i)
in Lemma 4.4. Note that (s)) = (M) (8) holds true for the following two cases since each state 8 E S has an expert policy such that 7 (als) > 0.
2) Let E S and a E A such that (alss) and Q'M (s,a) > VA (s), then we have () AM (s, +
AlM (s,a)((s, (s) (s) This is the case (ii) in Lemma 4.4.
3) L E and a E A such that (als)) = 0 and Qu (s,a) I M (s), then we have (Mue(s, = =A as,a){+ (*(s) = AM (s,s)ss a) + (s) I (s). This is the case (iii) in Lemma 4.4.
To demonstrate the "only if" side, suppose that Vinve satisfies conditions of Lemma 4.4, we take Vo(s) = Viuu((s since we are proving the existence of Ve RR..
1) In the critical region and follows the expert policy, where QM (s. = -VM (s), 0((s, = Qiiee - EVEue = O. Hence, there definitely exists ((s, a) > O.
(1), AtT (s,a)((s, Qiue 2) In the constraint-violating region with more rewards, where Qia (s,0) > VTT" (5), EVjue > 0. Hence, there definitely exists a(s,a) > 0.
3) In the non-critical region with fewer rewards, where Qix"" E (s,a) S VM AM (s.a)((s,a) = Qiie - EVV S
0. Hence, there definitely exists Ç(s, a) > 0.
Final proof of Lemma 4.5
Proof. Recall that Quuve (ISXA- - PP and based on Lemma C.I, we can show that:
c= (ISXA- - -PPT ) (Ar" <+ ++V)
A (+ FVV - 7Ppm" A - - EVO
Since B A M = Os and E = Is.
B A C + (E 18--PP (E-+
We now bound the infinity norm of ( and V First, from Eq. (20), we know that EV*(s) (iuu(ss Hence, intuitively
(s)llo < Cunss Second, from Eq. (6), c(s, a) = AM (s,a)((s, a) + (E- - (P)))s)) 1) When A (s, a) > 0,
1-7
since for every (s,a) > O, ((s, a) should satisfy the existence of cost function in [0, Cmax] Sxd ((s,a) (c(s,a)
(E- (s)) (s, /nuxx/ maxt (s,n) A (s, 2) When A (s, 0, ((s,a) (-c(s, + (E +
(s)) 5 (s,a)). Since (E (s)) = c(s, a) S Cmax. < < /max/ ( max(s.a)
A M (s,a)). 3)
When A = 0, we define ((s, a) 0. To combine all the three conditions, ||/ Cnax/ maxt (s.a)
Ar
17

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
C.4. Proof of Lemma 4.6 Proof. From Lemma 4.5, V(s, E x A, we can express the cost functions belonging to Cap as:
c(s,a) AM
& ((s, a) + -EBB-PPPV
Regarding R and Pr, we can express the estimated cost function belonging Cp as:
as a) A ((s. (F (F-
What we need to do first is to provide specific choice of { and V under which 7 [0, Cmax]Sxx, We construct
a(. a)
- Mn ((s. a) + (E - -PP))
We now define the absolute difference between ((s a) and c(s, a) as
x(s.a)= [ā(s, c(s,a) = (PT - (PT-PP)) (s. (s.0)+|AM² AM -Ar M ((s,a),
x=
max
x(s,a).
(A.0)ExxA
V(s,a) ES x A, since a(s,a) E [0, mmax] and ((8,4) c(s, a) E [-x, xw. have: as,a) = c(s,a) (c(s, a) ds, E 1-x Cmax + +x]
(21)
Therefore, there is always a state-action pair (s', a') such that
min (6 (s.a))=(s''..) A M (x.A)ESxA
(E-
To obtain č(s, a) E [0, maxx], we distinguish two cases: 1) a') < 0 and 2) 2(s 2 0.
Case one: o(s',a') <
By subtracting 7(8 n') from all ((8, a), have
E(s, a) = Ō(s a) ē(s',a') a')
AT M
((s, + (B) (s))) -A 5(8', - (E (B-
=
M
An
ds)
A M
((s,a)
M
((s',a')
+ - (VF-)))(V((ssd)) (3(5' -
A (s,a)
M
2 0
Also, note that V(s,a) E S x A, we have:
त(5 d') 0, a) C(s a) - 0(5' ,0's,a') [2ss, a)l + (((5'''')) S Cmax + x(s, + x
Hence, v(s,a) ES x A, (( a) E [0, Ciax + x(x, a) + x]. Because we are looking for the existence of à E Cp satisfying Z [0, Cmax] SxA, we can now provide a specific choice of and P under which 2 E [0, Cmax] S |x
((s',a") M Ans (d'aa)
((),a)
A
(s.a)
ε(8,a) ((() - VV(''sa') (s, 1 (x(s, a) + C (0(s 1 (x(s, a) x)/Cmaxx Cmax
{(s,a)= 1+ (x(s, + X)/x
(22)
We then quantify the estimation error between ö(s, a) and a(s
a(s,a)
le(s, a) - -(s a)) = a(s,a) 1+ (x( x) max
18

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
1 (x(s,a) a) + x)/Cmax [|((s, a) - a(s,a])++++00 ((x(s,)) +
[I(ss,a)C((saa)
+x)
1+ (x(s, a) x)/Cmax
I+ (x(s a) + x)/Cmux max - a)l
- -
[(s, - E(s, ((x(s, + x) O0Cmmx))e(ss)))
x(s,a) + X ((x(s,
1 (x(5, a) + x)/Cmax
2x(s, + 22
1+ (x(s 0) + x)/Cmax
Case Two: a(s',d') 0:
Note that (s) E x A. we have:
2(,",a))00, 0,,(s,,)) = -7 S {(ssa) I Cmax + x(s, a)
(23)
Hence, V(s,a) E 8 A, a(s, a) E 00 max + x(s,, a)}. Because we are looking for the existence of Cj satisfying E [0, Cmax] SxA, Sxx, we can now provide a specific choice of { and V under which E E [0, Cmax] SXA:
a(s,a) Č(s.a)= 1 1+ x(s, am/Cmax
(s)
ā(s,a)
(3(sa))= 1+ 1+ x(s, a(saa)= 1+ x(s, 0)/Cmxx
(24)
We then quantify the estimation error between (s, a) and c(s.a)
Ō(s,a)
[c(s,a) a(s,a) ((s,a) 1+ ()5,a)/CCml
a +
1 (ss,a))Cmma
x) + (x(s, /max)
1 x(8, a) Cmax
2x(s,a)
I+ ((s.a)/CCm..
2x a) + 2X
< 1+ (x(s. a) + x)/Cmax
(25)
Combine the upper bound of the estimation eтror for cost functions in both cases, we finally derive:
2x(s, a) + 2x
2(x(s, a) +x)
[c(s, a) - 2(s,a) a)l 1 (x(8,a) + x)/Cmax 1+ (x(8, a) + x)/Cmax
C.5. Proof of Lemma 4.7
Lemma C.2. (Simulation Lemma for action-value function.) Let M (S, PT. (.r,,) and M (S,A, Pr, be two MDPs. Let स A be policy. The following equality holds element-wiss
-" -M- -1
Q Q²- -
(26)
Proof. The proof can be shown as follows:
(IsxA - -PpxA)-Pp))
(ISXA -
= =ISxA - (IsxAA- (ISXA - -PPp) - - -
19

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
- (P - - PT) M
5 M
V
Lemma C.3. (Simullation Lemma for state-value function.) Let M = M Pr,r, and M (S.A, rr, be two MDPs. Let E Aड be a policy. The following equality holds element-wise:
VM* V
71s P V=) M
(27)
M
Proof. The proof can be shown as follows:
M V
= (Is PTPT) r (1s- (Is - 7 PT)
M
M
(Is PT)
PTPTT
(Is -TPP)) 7 PT) M
M
-Is PTPT) P 9 V=.
= - -PPPT - PT)
Lemma C.4. (Policy Mismatch Lemma.) Let M= ( PT,r, 7) be an MDP. Let n, E D be two policies. The
following equality holds element-wise:
7Is - VT M
M
Proof. The proof can be shown as follows:
V M
(Is -TPP) (1s - (Is -
(Ts - -1 - T M
(Is - -T - 7. PT VM
= r(1s - -7
Final proof of Lemma 4.7
Proof. By utilizing the triangular inequality of norms, we can obtain:
A r.
Σ<
AT R
Ara R
+
1.m R M
A
M
M
M
M
M
1.11
<
27
(PT - PT) /
+
7(1 71)
1-7
vr."
M
(28)
where the second inequality is derived by the following two parts.
Part I.
Let's consider the first part.
AT
(
( - ²7 - L.VVVV (VV -V*#*)
M
M
(4))
(QME - -maat)
M ) + E (/ - -IARE)
M
(10)
7 |LSKA - - -Pr) +
(Is - 1
- PT
MM
M
(kv)
=1((SxAA - 11
(Pr - P
P M
+ 111s - 7 p7) 00 | 1oc (Pr- PT)VnRE
M
M
(0)
27
(pr, VT)
1-7
M
20

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
exploits the definition of the advantage function.
(ii) applies the triangular inequality.
(iii) applies the simulation Lemma for action-value function in Lemma C.2 (a variant of (Agarwal et al., 2019, Lemma
2.2)) and the simulation Lemma for state-value function in Lemma C.3.
(iv) exploits Holder's inequality and the theorem of matrix infinity norm inequalities that ||AB oo S || [/
(v) exploits the fact that [I(5xx - S 1 l1(Is - S - and || S 1.
Part II. Let's consider the second part:
A
- Ar
Q M
224) - B (VM
-vn
M
M
M
(PTVM* -PTV -E(V ((VM*** VM )M
M
(8)
PT (VM - -VM*") )
+ E (VM - -VM -V
((0)
(1+7) E (virr* -VM)
(0)
5 7(1 +7) (1s- - - PT) -7)-1(( ( - PT V
M
x)(1+))
s11 - - F PT)
(T F. - > PT V
( 71
( - - )
PT 1 8
1-7
applies the Bellman equation -
(ii) applies the triangular inequality.
(iii) holds since || < 1.
(iv) applies the policy mismatch Lemma for state-value function in Lemma C.4.
(v) exploits the fact [hat]]([s - 7 Pr) loc S +
C.6. Proof of Lemma 4.8
Lemma C.5. (Good Event). Let E (0, 1), define the good event &g as the event at iteration such that the following inequalities hold simultaneously for all (s,a) a) E S x A and l 2 1:
Rmax
Ex(s, a)
(PTx -P)
(s) <
Mr
2N (s,a) (,,))
(PT - -P-Paa (8,a) 5
Rmax
(u(s, a) (N, (s,a)
7
(TT PT PTV 5
)
(s,a) <
Rmax r
(x(s,a)
2N (s)
(#F n ~7)P7 P
o Mr
(s,0) 5
Rmax
(s(
2N (s,
21

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
max
(x a)
(Pr - Pri)Vo (8,a) - 1 V
2 (s,
(Pr - PT
(s, 5
Crax
(s)
2 (s, a))
where Vn@ Vna", vc and VE are defined in Lemma 4.6 and Lemma 4.7. Lx (s, = (3 Then, Mj
Pr(Ex) 2 1 -
Proof. We show that each statement does not hold with probability less than 6/6. Let us denote 8 (s.a) (8, =
Cmaxx 1-7
Eu(s.a) and B (s,
Cmax 1-7 2m
(o.o)) Consider the second to last inequality. The probability that it does not
2N (s,a)
hold is:
Pr 3k 2 1,) ES A: (PT- - (P (0,a) B (xt( (s.a)
Σ (..a)
Pr
3k 21 :: (Pr - Pr-PPaa (s, > S (xt(eay(ss (8.a)
m 0: (Pr - -P (8, > (s,a)
Pr
(s,a)
Σ
Pr (P -Ta) (s, (s,a)>Ba
(3,a)
-2(3% (s, Rm²
2exp
Cuus I-7
Σ
exp ( (-)+(s,a)
m (s,a)
28
Σ
36SA(m )2
(s,a)
5 (1
8
(29)
18
6
(a) and (c) use union-bound inequalities over (s, a) and m.
(b) assumes that we visit state-action pair (s, a) for times and only focus on these m times that the transition model is updated.
(d) applies the Hoeffding's inequality and > S Cuaxx/ / (1 10-)) 7) in Lemma 4.6. The factor m² in the numerator results from dividing by 1/m average over samples, and the factor in the denominator results from the sum over m in the denominator of Hoeffding's 's bound.
Similarly, we have 11.2 N (s.a) (s. (s.)
Rmax
(e(s.)) (N.() and 21.22 a) Reax
(2(a,) 2m
for Lemma's first and second, third
T-y
1-7
and fourth inequalities, respectively. Lemma's last inequality employs 33
(s,a) (s,a) and 8 (s, a) again. A union bound
over the six probabilities results in Pr(E)) S (6/6 + 5/6 + 8/6 8/6 8/6 1 8.
5/6) = Thus, Pr(Ex) = 1 -r((&)) Z
Final proof of Lemma 4.8
22

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Proof.
(a) x(s,u) S (PT - PF)V +
AM -A AM
M 6
2 Rmax + 7)5(1, 0) -Cmax -17)
Ex (x, a)
(1-
2N (s,
7 |mmax (3 + 701151100 + +Cmax (1ax(119))
(x(s, a)
(1-
2N (s,a)
mmax Rinux (3 + t max (0,0) 11
+ (1 - 7)
(x(5sa) (,,
(30)
(1-
a)s,aa 2N (8,
(31)
7mmxx
Bmmax (3+7)/ muxtna) I [+(1-))
where, for concision, we denote
(1-7)²
(a) uses Lemma 4.6 and the triangular inequality.
(b) uses Lemma 4.7 and Lemma C.5.
(c) uses Lemma results of O0 in Lemma 4.5
2(x(e.0)+)) From Lemma 4.6, since T+(x(sa))x) increases monotonically with x(s,a) + X. we have
(V
2(x(s,a) +x) 1+ (x(8, a) + x)/Cmax
20
Pa(a,a) 122 (s(a)
mI8X (x.))SxA
2N (s.0)
(a(a.)
(o(s,a) - (x(
(32)
1 + o/ o/Cmax
(12N, 2N,, (o.a)
(e(a.a)
+
(s,a)ESxA
max
2N, (s,a)
Ex(a,))
Also, note that
[e(s,a) (s, < (x( s Cmax
(33)
Thus, the following formula holds true,
(c(8,a) (xx(8, S Ca(s, (
ES
(34)
20
(e(e,)) +
tale.a) 2N, (s.a)
(1 2N (s,a)
(s,a)SSxA
(s) = min
Cmax
(35)
(1/ fx(s,a)
1 + a /Cmux
(V
(Nt(s,a)
+ max (s,a)ESxA
V
fx(s.a) 2N (s.a)
C.7. Proof of Lemma 5.1
Proof.
(0) S [[xxxA "PTx*)
2nlllss (IsAA -PTT) loo
(36)
(a) follows Lemma C.6 (treat π 77" and ē = 2x).
(b) follows Lemma 4.8.
23

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
C.8. Proof of Lemma 5.2
Lemma C.6. For every given policy n, the first inequality below holds element-wise. For every optimal policies n²" E 11 Mue and R E T. of CMDPss M U.c. and M U respectively, the second inequality below holds.
Mue
Q - -Qiiaa $
(15xA-
((Px) (---2) 2
max a (
12000
-Q
-
-1-11
1
|c 8.
20
-
Proof. We can show that:
(a] (ISXA- - -PTTT (IsXA PPT
(IsXA
(37)
(a) results from the matrix representation of Bellman equation, i.e., Q (ISXA- -PTx)
By definition of infinity norm, we have
QMuu Quuual 1 - -
(38)
Further, we derive the error upper bound of the action-value function by that of cost.
1 la
( (IsXA - -PPTx) ---1 all 20 |c- 2l
( (IsxA - -ppxx)
(d)
1
||c -o0
1 g q
(b) uses Eq. (37)
(c) exploits the theorem of matrix infinity norn inequalities that |BBlo I >0||BbB0|B||
(d) results from - ll S +
Final proof of Lemma 5.2
Proof. For statement (1),
inf B x ETT
sup
2ii a) 2uem (so, a)
inf
sup r
11 - Dun QMaaa (s, a)lx
2, EC
(a)
1
inf
I 1- [c((s, (s)
max (s,a)ESXA
Ca(s,a) Se,
sup cECy Rg el R Saguez
inf
(90 a) MUEU (3o, a)
< inf
sup
[1 - e Sung (s)
cECy
Rgell
1
inf eECy
||((s, a) a))
1 -
24

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
max Cx(s, e,
7 (s.a)ESxA
where steps (a) and (c) use Lemma C.6, and steps (b) and (d) use Lemma 4.8. For statement (2),
(e) inf max - Gell
inf sup 8g E/ 3g Mel
1Q0- QMMa (50, a)
8,EC v. Hell!
max
- (Ppx)---PT)1000
sell
5
max max
"M((1AA - 7PTx) ) Se
eell' MoEaS
(eit (Muu(s), -MMA (50, a)
inf sup cECp R R M,ua,
inf max 11l1xx-7PPTm) 2/c Exl
EEC Tell
max [TsxA PPPx)
sell
max max |nd (1sxAA77rx)) - P Se
well woE
where steps (e) and (g) use Eq. (37) and the fact that each cost function in the feasible cost set must ensure the feasibility of expert policy, steps (f) and (h) use Lemma 4.8.
C.9. Uniform Sampling Strategy for ICRL with a Generative Model
In this part, we additionally consider the problem setting where the agent does not employ any exploration strategy to acquire desired information but utilizes a uniform sampling strategy to query a generative model. The problem setting is based on the following assumption, which stronger than the assumption the main paper. Assumption C.7. The agent have access the generative model of M:
More specifically, the agent can always query a generative model about a state-action pair (s, a) to receive a next state ~ (-|ss,a a) and about a state s to receive an expert action a ~ π (-[s). We first present Alg. 2 for uniform sampling strategy with the generative model and study the sample complexity of this algorithm in Theorem C.9.
Algorithm 2 Uniform Sampling Strategy for ICRL
Input: significance E (0, 1). target accuracy e, maximum number of samples per iteration Temax Initialize k +- 0, Eo 1-y
while E > do
Collect SA samples from each (s,a) E S x A
Update accuracy Ex+1
I- max
Cx+1(s, (xA
Update #5 (als) and (s'lss)'ss, (7) k + +1
end while
Lemma C.8. (Metelli al., 2021, Lemma B.8). Let a, b 2 0 such that 2ayb Then, the inequality 2 a alog(bx?) is satisfied for all 2 -2aW 24vb) where W-1 is the secondary component of the Lambert W function. Moreover, -2aW-1 -2aW-1(- (-a--1---/b 220/b) 4a l)g
Theorem C.9. (Sample Complexity of Uniform Sampling Strategy). If Algorithm stops at iteration K with accuracy EK- then with probability at least 6, it fulfills Definition 4.9 with a number of samples upper bounded by,
SSSA
(39)
(1-
25

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
yCmax (Mmae(3+7)) max
1AM 1-(1-7)
where o
and Ô notation suppresses logarithmic terms.
(1-7)²
Proof. We start from Lemma 5.2. We further bound:
20
Ex(s,a)
+ max
(3,0)) 2N (s,0)
max Cx(s,a)=
1 max
min
2N (s,a)
(s,a)
Cmax
1 - (s,0)ExxA
1-7 (s.a)ESxA
(x(s,a) 2NE (a,a)
(x(,a) 2N (s.a)
1+ Umax
max (5.0)
4a max (8,0)
(e(o,))
2N (8,0)
min
Cmaxx
1+
2a maxx
(x(s,a) (s,a)
Guax
(9,a)
(s,a)
Bu(s',a") 2N (s',a")
40
(a) 1
min
Cmax
(40)
20 1+
Eu(s'a()) 2N (s',at)
Cmax
V
where step (a) supposes at state-action pair (s', a'), o
fa(s'aa))
felstaa) (N'
2N
max (d',a')
V
After K iterations, based on uniform sampling strategy, know that Nx for any (s,a) E x A. To terminate iteration K, suffices to enforce every (s,a) S A::
(alstaa)
4a
1
2N (s',a")
-KK
7
Pu(s"aa")
Cmax V
(s
Ex(s', .²)
Cmax (1 - -7)
V
2N (8',a))
4Cmax 28 (1 7)
*Cmax (3+xl3+7)// maxto.a)
AM (+(1-))
By
we have
(1-7)2
7max Rmaxx + /)/ max max (s,0)
M (1
(x(5',a')
Cmaxe
(1 11-71 7)3
V 2N (8',a')
40max 22 (1 7)
NK(ss, 272 - Ex(1 (1 - -7) Rmaxx (3 + 7 maxt (0.) AA 1 (1--)) ea(s',a')
(1 - 7
From Lemma C.8, we derive
(s'
4-2 4~2 - -Ex(1 (xx(1-2))2 RRmax (3 + 7)/ maxt (0,0) 1 |+(1 (1)- 2
(1 7
(1 - (1-7)0E7
W-1
4722(Cmax 7))2 Rmax (3+x)))++)))))))))
maxt (5,0) IA |+ (1(1-))
36SA
8- 822 - -x((1- 7)) (Bmax (3 + 7 maxt (s.a) AA (1 - 7)) 2
<
- 26
26

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
422 Ex 7))? Rmax + / max (s,a) I (1 7))
36SA
log
(1-7)66
8
y 1-CCma-EEKll - -x(1--)) Rmuux + 7)/ max (8.0)
(a.0) |AM + (1--7)) (1 -7)
(20 -Ex(_ Rmaxx (3 + /)/ max (s.0) IAM 1 (1- )
(41)
(1 (1
By summing n = E(aa)ESxA E we obtain the upper bound.
a),
(20 - -8x - 7))² Rmaxx (3 + 7)/ max (x.a) I + (1 7)) SA
(s.0)
(42)
(1 (1 7
7mmax (3 maxt e (+(1-))
Since
have
(1-7)²
0 Q2 max -x -A
n S Ō
(43)
( C2 max
Regarding the sample complexity in the RI. phase, since the reward function is known, according to Corollary 2.7 in Section 2.3.1 from the book 'Riinforemment Learning: Theory and Algorithms' (Agarwal al., 2019), the sample complexity of obtaining E-optimal policy is O(SA/(1 -7) which is dominated by the sample complexity in Theorem 5.5. Note that also contains 1/(1 7). As result, Eq. (43) still holds true after including the sample complexity of the RL phase.
C.10. Proof of Lemma 5.4
Proof. This result generalizes (Kaufmann al., 2021, Lemma 7) setting. We define event Gent
{ vk Vk N", ((s.a) e S A: Nu
1 } Na(s,a)
2SA log 8
)
}
geut
(44)
We calculate the probability of the complement of event geut
P ((gent))
2SA
IN
Σ
Na(sa) Na((s,)) - log
(s.A)ESXA
&
22AA
Σ
P
IKEN: Σ Σ 1 (()) ) = (s,a))
5 Σ
Σ Σ
(o (s, log
2 5p
8
(
h=1
1m1
1=1 im
Σ
2SA =
(45)
2'
SA.
(a) results from union bound over (s, a).
(b) results from Definition 5.3.
(c) results from (Kaufmann et al., 2021, Lemma 9).
27

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
As result, have with probability least 1 6/2:
1 a)(s,,) 2 N Pont (6),
(46)
2
where Pent (6) = log (2SA/6).
The following proof is adapted from Lemma B.18 in (Lindner et al., 2022). Distinguish two cases. First, let Sent (6) S as) Then (x(5, a) 2 Nx (5,ss)) a), and
ax(8,a) 2N (s,a) Cmaxx Sa (
(x(
log(36S (s, (s,a))2/6)
min-
=OV 2N (s
2N (s,
( (8, (8)))/4)//))
(8,(s,a) a) No (s)
a
(47)
N (s
where we use that log(365.Ar2 /8)/x is non-increasing for > ev 365A For the second case, let Bent (6) > (s, a). Then,
where e is Euler's number.
(x(s,a) a) 2N (s, a)
(0) S Cmaxx (s,
4lx(s, a) No (s, ()
min- V
Cimxx
S Cmax Omax V
(48)
where we use (s a) = log (36SA(N; a)) = (o))(0) + log (18(N (s, (8,a))}) 2 Bont (d). By combining the two cases, we obtain
2N (s, Craxx } max(o, V2C (2Cmmx)
a))
(5,
(8, a) N (s, a)
min
Vo
N (s,
=ō
(49)
where we denote 5 = max V2Cmax).
C.11. Proof of Theorem 5.5
Proof. We assume BEAR exploration strategy terminates after K iterations, then
2a
fu(s.a)
+ max (5.0)
(u(o,a)
maxCx (a)
2N (x,a)
2N (s,a)
min
Cmax
1 1-y y (s.4)
1-7 (s.
fa(s.a)
(a(sa))
+ max (s.a)
Cmax
2N, (s,a)
2N 2N (s.a)
[s,a)
(x,(s,a)
2ō
+ max (4,0]
(a,a)
N (a,a)
min
Cmax
Y (s,a)ESxA
(x.().a) (7()).)
(x.0) Nē(3,0)
+ Umas
max (5,a)
20x(c',a')
48
8 (el,aa)))
(c)
min
C.axx
7
28x(s',a')
1+ Cmna
where step (a) follows Lemma 4.8, step (b) results from Lemma 5.4 and step (c) assumes at state-action pair (s', a') (s'
(x.().)) Hence, obtain, (8.0) Nā(s,a)
(²)
max
4ø
EK
(50)
7
1
Cmax
28

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
δ 2xx((')a)) 8 4Cmax 2= 1 1- 1 (s','aa') 1-7( (
Cmax K
21og(365 ( /a)))/6))
Thus,
()) 802
Ex (N
(1 - -)) C
From Lemma C.8, we have
(+ 1602(2C Ex(1 - -7))
- (1))22 O2 max
8
W-1
(1 (1- miax
160 (2C (2C max -E 7))
36SA
32202(2Cmon max Ex - -)))
max - -x 320²(2C
36SAA
log
(1 5 C22 Cuaxx
(1 3) C2 max
8
02 02 max ex(11-))1
(51)
(1 2 Cmaax
By summing over n = Σ E. (8, a), we obtain the upper bound.
S δ (02 max -Ex(1 7))
(52)
(1 7)5 f C Cmax
where ē = ma 2.
Regarding the sample complexity in the RL phase, since the reward function is known, according to Corollary 2.7 in Section 2.3.1 from the book Reinforeement Learning: Theory and Algorithms' (Agarwal et al., 2019), the sample complexity of obtaining e-optimal policy is O(SA) A/(1 se?, which is dominated by the sample complexity in Theorem 5.5. Note than also contains 1/(1 - 7)) As result, Eq. (43) still holds true after including the sample complexity of the RL phase. O
C.12. Theoretical Results on Policy-Constrained Strategic Exploration (PCSE)
Definition C.10. We define the optimal policy w.r.t. cost, reward, and safety as follows:
The cost minimization policy: л.* = arg min B|E, 7 a:)
The reward maximization policy: T arg max B , (t(s at)].
The optimal safe policy: n" = arg mellaa ET
where Ilaase {T :E: 70c(s,, ar)l s [e}
Accordingly, we can have the following relations:
E (Ve (su) < Euo [Ve==' (sv) I Eyo [Vax (su)] + where the equality normally holds that Ve,0" (su) 0.
Eno[Vaa (so) < Eng [V" (so)).
Let's define the following symbols:
Eg 4 -(->))
Ex suppoEasxa 1 (IsxA
CC
E max cg
29

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
We construct of plausibly optimal policies
11g 11 1
1 π E Ag: sup Po (Vaa - Vae
S 4Ek 26
MUG
MUU
MoEA
IT
π E AS
inf HoEAS
10
( V
2 R
M
where R4 2r.amax [PT - Polloc 7ffimax (1-7)"
lloo.
(1-7)²
Lemma C.11. (T" propagation). Under the good event Ek, if 7% E T then n²" E ITg
Proof. Given E Cz,, we can show:
sup 1 MOEA8
(pen' MUEL
Ven Musi
sup A
n T (vex' MUU.
-ver'
+ Ven MUc
VG* Mue
(53)
Mue
sup 16 T
[E +
Ve+ MUe
-VGx MUEN
MoEAS
(86)
< 28 + 2e,
which demonstrates that n² E IIg
holds since
Vex -ve Mue S (1s - 9T p7) -1 x" (0 - cl
MuG
S (Is 7xx PT)
-1 1 Ck:
where
The first inequality follows (Metelli et al., 2021, Lemma B.2) (treat P6. = - and r = c)).
The second inequality is due to the good event definition in Lemma C.5.
As result:
M0 HOEAS
sup
T. ( Muaa
-VG7*) M.Jo
Ex < max E Ek
(54)
rel
(ii) holds since
VGx"
Ve.
V8x*
MUc
MUR
Mue
MUEL
I V0,8 MUe
Ve
+
MUG
min V
min Va.
+e
Mue
MUG
min
yea
min
Ve, MuRe
+
<'Ell 1-1
Mue
=en
xEll
max
Var
M.
Mue
+ 2E,
where
The first incquality utilizes E,,, [VG="' (5o) +e> Eno |VG= (so))
- The second inequality utilizes Vc, E.g [V=="* (so)) s Ego! ( (so)] < Eno assumption that n. 7े E ITg-)-
(VoT" + e for e
and the
30

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
The third inequality results from Lemma C.12.
By following the inequality (54), we have:
max sup Tells -- na EgE
14
(Ver MuR
Ve.
+ 2e 8k + 2e MUOe
Lemma C.12.
max f(x) max S max(f(x) g(x))
min f(x) min g(z)) S max (fx) g(x))
Proof. For the first incquality, suppose 1ι = arg max fz) and x2 = arg max g(z), then we have,
max f(x) max g(x) = (m) - g(x2) S f()1) - g(ml) max( g(x))
For the second inequality, suppose 23 = arg min (x) and x4 = arg min (2), then we have,
min f(x min g(x) f(23) - g(x)) S fx1) g(an) s max(f(x) - -g(x))
1 and & & HT then is suboptimal for some cost Ee Riy for Lemma C.13. Under the good event &s, if a & all K 2
Proof. Let's consider the following decomposition:
(
VSS Muex
Vor+ MUea
VSs
MUGe
MUGz
Vog MUGa
Ves
+ Vas MUG.
-VORE MUG. + +VOR8"
- -eaa
MUGe
MUG
MUGN
(8)
4Ek + Vas
V MUe
MUG
(184)
2c
which indicates that cannot be optimal for k' k.
(i) holds since V S
GAW MuRy
VS.* Muey
MURN
(ii) holds by following (Metelli al., 2021, Lemma B.5) (treat Pkr )
#x and respectively, while Fi. T and
sup M6 HOEA
(pott MUG
VeAk" MUG
S 20 #K < 2
sup wá (vss MUGi
Veg MUSzy
$ 265 255 < 2
PoE
(iii holds since according to the definition of 11g. and considering our assumption that & 1Is we have:
sup 5
140
T Vog MiFa
> 45 + 2e
31

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Lemma C.14. e -ा- then for every & 0, it holds that n², k E T.
Proof. We prove the result by induction on k. For k 0, for every policy & E As. we have supreeas 16 (ver
MuRa MUR) s S 45a I 46g + c. Thus, Hi contains all the policies, i.e., n1 Ag. and in particular x: : Ti 11j. Suppose that for every S K' the statement holds, we aim prove that the statement also holds for k. Let k' = k- 1, from the inductive hypothesis we have that n², #7 - Then, from Lemma C.11, it holds that x² E -. If *+4 E Iy. the proof is finished. If +++1 $ [Tg. we prove by contradiction. Let 1 S j S A be the iteration such that 7f - and + NI. Note that this assumption always holds, since Tī contains all policies. Recalling the inductive hypothesis, we have that #j E - Thus, from Lemma C.13, it must be that 7b.1 is suboptimal for all j' in particular for j' = k + 1. which brings about a contradiction.
Lemma C.15. It holds that x² EIT where:
} where
11. x D
inf
Mb (yn - 2 Ri
MDE
(M
27 Ryamax
Rumax
R2 (1 7)2
(1 7)3 [( - =70 IPT pol
Proof. We should show if n MT we will have VM* VM=
VVL M
V
V
VEL
VM VM" + VM VMM" + VM Vr,
M
M
M
(8,81,501)
27 Rmxx
PT lo + 7/mmxx
S
(1 (1- |1(T= 8z 1ox + VM V/="
= Ri
+ VM
VM
Since inf moss mo!
Vn M
V
Rg. it must hold that inf posss mā (Vir VM" 2
M
To show (i), we first follow the simulation Lemma for the value function:
V
प... - xPr - PT)VM
M
=
Then we derive an upper bound for the difference between these state-values as follows:
v
v. M
S
7
| | - -PT) oloc
1
Rmmxx
| | -PT-P)ll
7)2
? Rmax
<
7)2 |P - -P
(ii) holds due to the policy mismatch Lemma C.4:
VA
V M
= (Ts -1--~ P -7* PT
Then we derive an upper bound for the difference between these state-values as follows:
v M
||(TT= - -T 1ox0
M
R Rmax
[1 7²') PT 1loc
(1 7)2
7 Bmax
<
(T - -
(1 7)3
32

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
(iii) holds due to the derivation (i):
V
VA
?Rmax 21- Pl Prl M
Since we can guarantee VM 2 V. know 'T" the feasible cost set, the exploration policy should follow the that visits states with larger cumulative rewards.
{T[VM 2 VMD: }. Subsequently, according our Lemma 4.4, find
Lemma C.16. Under the good event Ex, let ē arg min max lc(s, 0) (x, a) I 1lg and n' E 11k-1 then sup MOEAS Mó
(vem MUE
Ve,* Mua
S 6ε사 e..
Proof.
sup HoEAS
1
(vea Mue
Var Mua
sup HOEAS
Mo
(Vei MuE
ven Mua
sup HOEAS
1
(ver Mua
Ve+ Mua.
sup
MD (ver (Via
Ves MU8
MoEds
(a)
(6)
< (Ex) + (AE +e) + (Ek)
68* +6
where
(vex VSa
) S c S Ek.
(a) holds due to sup mn
Mua
MUG
(b) results from sup a 10
Var MuR
Vaa Mua.)
S 48 since llg-
(c) follows Eq. (54), recalling the definition of ē
C.13. Proof of Theorem 5.6
Proof. Suppose we have derived value of Nx(ss a) so that for all (s, E S x A (the rationale is discussed later), it holds that:
(s( min { (oV (x,
(x)
(k (z)
min E. EAA A (s,a')E) MUA
Cmax
S
(55)
- +
From Lemma C.8, we obtain
26 K- + +c)((((0,)))
No (8, = (mina'Ed A (s, a. 22
MUE
402 e)2
(min EAAAAAAA A Mus Mu (s,a'))EEE
8
W-1
(mina'eA 1 (8, () 222
402 + 6)2
3654
MUA
802 + e)2
402 | + e)2
365 A
log
(min, c.+ (s, a 222
(minw'eA c, (s, a 2E
Mua
Mua
0 02 + c)2
=ō
(56)
(minw'ed A cit MuE
(s, a al))))))))))) 22
33

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Summing over n E(sa)eSAA N (s, since the convergence of BEAR is stricter than PCSE, i.e., (13) is always satisfied if (12) is satisfied, the sample complexity of BEAR constitutes lower bound for that of PCSE. Recall the sample complexity of BEAR exploration strategy in Theorem 5.5, we obtain
S ① min {ō {0(=(2
(20 max -Ex(1-2)) (1 23 Cax
[66K-1 (
})
(57)
(min( (x.a) A c.
(5, a))3
MUE
Next, we explain the rationale for the assumption in Eq. (55). We have for every E II
(4)
[|x 0, ,,
S
7/4 (Is - - (TppT)-T(C
(6) yEk I (Ls -TTPP) (T
(-AcH
(MA)) Mud)
6 +
6sk-1 + (VMué
NEK
T
Va+ Muă)
S EK:
(58)
(a) follows the matrix from the Bellman equation for the value function.
(b) is based on the assumption in Eq. (55).
(c) follows (Metelli al., 2021, Lemma B.3), where treat - and note that Vi Mu(-E)
-VV
MUEE (xu((-)
O
Taa and AT Mu((EE = - Muue
(d) results from Lemma C.16 and y < 1.
C.14. Optimization Problem and the Two-Timescale Stochastic Approximation
We now formulate the optimization problem.
Ek+1 = sup
s.t. IIg I
II
(59)
Ag
sup Ho (Vo.
Vee MuGn
40x + 2c
MuG.
PoE
I
A
inf mEAS
Po Vri
V M
2 Rip
where R₁ Run PT (1-7)²
Prllec ooo + Taanys I( - )oo..
Recall that the discounted normalized occupancy measure is defined by
( Σ
y u (st = =s = a),
(60)
where the normalizer (1 71) makes Plu (8, a) probability measure, i.e., E(s,,)
1.
The promised relationship between reward value function and occupancy measure is as follows:
(1 - ソ) (a) (1
Byn, Pr
Σ 2'r(st;
=11 -
T No
(st
8,0, = a)r(s: 8, a)
t=0
(s.a)
34

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
pr. No (st = 0, aa) [r(s) = a, = a))
(s,a)
t=
(P)
(61)
where step (a) follows the definition of the reward state-value function, and step (b) exchanges the order of two summations.
Similarly, concerming the cost function, the relationship between the cost value function and (the same) occupancy measure as follows:
(1-7)VM =(1 - B,
cs(s,, a+)
1=0
(1 7)
p.d po
(st s, a, = a)c(s s, 0t = aa)
(8,a)
Σ
(1 7)
M Ho
(st = 0 a)
[c(s: =, aa]
(x,0)
t=0
():,.c..
(62)
For simplicity, denote the occupancy measure vector PMM vector z. As result, the optimization problem (59) can be recast as a linear program.
min
- Cx+1)
s.t. -(1-7)(Ve) MuE. + 4Ex + 26) + (x, Gx) S 0
(63)
(1 (1-
M + Rs) (c,,) 0
To solve this linear program, we introduce the Lagrangian function and calculate its saddle points by solving the dual problem. The Lagrangian of this primal problem is defined as:
A(x,A) (x, Cx-) +1 (-(1 (-(1-2)(Ve) (V
MUG. + + 2c) + (z,, (x)
+2 >2((11 71 (V
+ Rig) (t,
(64)
M
where À = [2] is a nonnegative real vector, composed of so-called Lagrangian multipliers. The dual problem is defined as:
min max L(x, A).
(65)
A20
To solve this dual problem, we follow a gradient-bact based approach known as the two-timescale stochastic approximation (Szepesvári, 2021). At time step k the following updates are conducted,
xx+1 Ik = aa (TK, Ax) + Wt),
(66)
Ax+1 - = bb (Ik, Ax) + Uk).
(67)
where the two coefficients a < by. satisfying Eσ az = Eb = xc, Σ a < 0o and Σ b < co. Under this condition, the convergence is guaranteed in the limit. As an option, we can set 0 c/k: by c/ 0/t0.5+*, with e being a constant and < K 0.5. WE and UR are two zero-mean noise sequences. The two gradients are:
AT( = -C++1 + A1 - A22T,
(68)
AR(I = [L (IRI Aa)
[ -1--7)(ve (VVG + + 2c) + (x, E6) MUe
(69)
(Ig Ax)
(VV +He) (z,r) M
At each time step k the exploration policy can be calculated as,
TA (als) = (1 a)
(70)
Σ. 2x (8,a)
35

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
D. Experimental Details
We ran experiments on desktop computer with (R) Core(TM) i5- 1--14 and NVIDIA GeForce RTX 2080 Ti.
D.1. Discrete Environment
More details about Gridworld. In this paper, we create a map with dimensions of 7 x 7 units and define four distinct settings, as illustrated in Figure 2. We use two coordinates to represent the location, where the first coordinate corresponds to the vertical axis, and the second coordinate corresponds the horizontal axis. The agent aims to navigate from starting location to a target location while avoiding the given constraints. The agent starts in the lower left cell (0, 0), and it has & actions that correspond to 8 adjacent directions, including four cardinal directions (up, down, left, right) well as the four diagonal directions (upper-left, lower-left, upper-right, lower-right). The reward and target locations are the same, which is located in the upper right cell (6, 6) for the first, second, and fourth Gridworld environment or located in the upper left cell (6, 0) for the third Gridworld environment. If the agent takes an action, then with probability 0.05 this action fails, and the agent moves in any viable random direction (including the direction this action leads to) with uniform probabilities. The reward the reward state cell is 1, while all other cells have O reward. The cost in a constraint location is also 1. The game continues until a maximum time step of 50 is reached.
Comparison Methods. The upper confidence bound exploration strategy is derived from the UCB algorithm, which selects an action with the highest upper bound. The maximum-entie entropy given previous choices of actions. The random strategy uniformly randomly selects a viable action on a state s. The c-greedy strategy selects an action based on the c-greedy algorithm, balancing exploration and exploitation with the exploration parameter e = 1/Vk.
strategy selects an action on a state with the maximum
More details about Figure 3. In Figure 3. we plot the mean and 68% confidence interval (I-sigma error bar) computed with 5 random seeds (123456, 123, 1234, 36, 34) and exploration episodes n, 1. The six exploration strategies compared in Figure 3 include: upper confidence bound, maximum -entumopueen.......om random, BEAR, e-greedy, and PCSE. Mcanwhile, utilize the running score to make the training process more resilient to environmental stochasticity: running_score = 0.2* + running_scome + 0.8 * iteration_rewal
(or seprrationccosss (Luo et al., 2022).
D.2. Weighted Generalized Intersection over Union (WGIoU)
In this section, we present the methodology for designing the metric that assesses the similarity between the estimated and ground-truth cost functions, which we refer to as WGIoU, We commence our discussion by explaining IoU, followed by GloU, and ultimately introduce the novel concept of WGIoU for ICRL.
Intersection Over Union (loU) score a commonly used metric in the field of object detection, which measures how similar two sets are. The IoU score is bounded in [0, 1] (0 being no overlap between two sets and 1 being complete overlap). Suppose there sets X and Y.
IoU IxnY XUY
Note that IoU equals to zero for all two sets with no overlap, which a rough metric and incurs the problem of vanishing gradients. To further measure the difference between two sets with no overlap, Signed loU (SloU) (Simonelli al., 2019) and Generalized IoU (GIoU) (Rezatofighi et al., 2019) are proposed. Both SloU and GloU are bounded in [-1, However. rectangular bounding box, which is not the case for the cost function. By contrast, GloU is not
SIoU is constrained limited to rectangular boxes. Thus, GloU is more suitable for comparing the distance between the estimated cost function and the ground-truth cost function.
GloU LoU (XU)
IZ
where set Z is the minimal enclosing convex set that contains both X and Y. Taking cost function into account, the difference between & the estimated cost function at iteration i and the ground-truth cost function is calculated as,
|c n Ck GloU
[ee ((UU)) Ic + Exl
c U Ck
36

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
where Eg @ e denotes the enclosing convex matrix of c and Cg-
Note that the estimated cost function é could have different values, but GIoU only reflects spatial relationship and is unable to represent weight features. To accommodate our settings, weighted GloU (WGIoU) is proposed, where we measure the distance between a weighted estimated cost function and a uniformly valued (or weighted) ground-trudh cost function. WGloU is also bounded in [-1,1] 1]. To calculate WGIoU, first, remap the cost function to ({0) U [1, [1o+) +oo)))x4
(s,
(s.a)= min (z,))ExxA Cs a) min ((s,)))
(71)
d(saa)
c² (s. a) min ( Ce a), min (A,)ssxx d(s,a)
(72)
where min ( returns the minimum positive value of C or c over all (s, a) pairs. Note that must exceed 0 at certain (s, a). Otherwise, the cost function is zero, indicating an absence of constraint anywhere. Also note that if Cg is zero, let ck as 0 and c* (s, a) c(s, a) (e//mmmaa)s.ss...... ( c(s, a). Besides the two trivial situations, the above two equations (71 and 72) can be applied naturally.
Then, WGIoU is defined as:
WGIoU (1, max c², (x,))))) + +c- o 1
(l = 0}.
where 1 denotes the vector with appropriate length whose elements are all 1s. The rationale here can be understood by distinguishing two cases. For the first case, there is overlap between é₁ and so the second term in WGIoU is 0. For the first term, for some (s, a). 1) if both o (s, a) 2 and c* (s, 2 1, WGIoU approaches 1; 2) if either 6x (s. a) = 0 or c*( (s, a) = O, WGIoU approaches O. For the second case, so there is no overlap between T and (s, a). the first term in WGIoU is 0. The second term is always below 0 and approaches - if the estimated and ground-truth cost functions contain large values.
D.3. Continuous Environment
Density model. Recall that in Definition 5.3, the concept of pseudo-counts is introduced to analyze the uncertainty of the transition dynamics without generative model. Here, we abuse the concept of pseudo-counts for generalizing count-based exploration algorithms to the non-tabular settings (Bellemare al., 2016). Let p be a density model on a finite space X, and pr( the probability assigned by the model to after being trained on a sequence of states 21,--. ... .y....,,n--- Assume px (x) >> 0 for all æ, The recoding probability p'n (x) is then the probability the model would assign to if it was trained on that same one more time. We call p learning-positive if p', (z) 2 (x) for all Z1...., In, E X. A learning poahiing--oitiveeeeee p implies we define the pseudo-couml as N., = (rr) n., where n is the total
(z. 2 0 for all x E X. For learning-positionn count.The pseudo-count generalizes the usual state visitation count function (z), also called the empirical count function or simply empirical count, which equals the number of occurrences of a state in the sequence.
Methods. We first train Deep Q Network (DQN) in advance that stores the Q values of the constrained Point Maze environment. This DQN induces the expert policy at any given state. We also train a density model that accounts for calculating the pseudo-count of any given state-action pairs. The agent then collects samples from unconstrained Point Maze environment where it could violate constraints. For algorithm BEAR, Proximal Policy Optimization (PPO) is utilized to obtain the exploration policy T&. For algorithm PCSE, we rank 8 permissible actions for the exploration policy. The action that has a high estimated cost or high reward is assigned with more probability to choose from. After the rollout of this exploration policy, the density model and accuracy are updated for the selection of the next exploration policy. Multiple rounds of iterations are conducted until the target accuracy is achieved.
Point Maze. In this environment, we create a map of 5m 5m, where the area of each cell is Im x 1m. The center of the map is the original point, i.e. (0, 0). The constraint is initially set at the cell centered at (). The agent is 2-DoF ball, force-actuated in the cartesian directions x and y. The reward obtained by the agent depends on where the agent reaches a target goal in a closed maze. The ball is considered to have reached the goal if the Euclidean distance between the ball and the goal is smaller than 0.5m. The reward in the reward state cell is 1, while all other cells have a reward. The cost in a constraint location is also 1. The game terminates when a maximum time step of 500 reached. The state space dimension
37

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
continuous and consists of 4 dimensions (two the and y coordinates of the agent and two the linear velocity in the and y direction). The action space is discrete, and each state, there & permissible actions (8 directions add linear force), similar to the action space of the Gridworld environment. The environment has certain degree of stochasticity because there is sampled noise from uniform distribution to the cell's (z, y) coordinates.
E. More Experimental Results
E.1. Gridworld Environments
Figure 7, 8, and 10 show the constraint learning process of six exploration strategies in four Gridworld environments, i.e., Gridwworld-1, 2, and 4. Note that in Figure 8 (Gridworld-2) and Figure 10 (Gridworld-4), only fraction of ground-truth constraint is learned. This is attributed to ICRL's emphasis on identifying the minimum set of constraints necessary to explain expert behavior. Venturing into unidentified part of ground-truth constraints will not yield any advantages for cumulative rewards.
Gridwenldk
Dritworid-22
Do slwordd-3
stworid-4
0.325
Diccoutte Cumusttve
DLAA
<greedy
0.100
GLKA
2.02
0.005
0.000
1.50
206
-2.00
1in
35x
50
1itn
156
35c
160
350
X52
Stwastion
Ieeraton
Blemitoon
Iterition
Cotts
UCB
ULB
UCB
122
UCB
1.0
PCSE
PCSE Sigiort
PCSc
0.5
PCSE
Copert
Cipert
0.8
0.8
-0.3
-0.2
200
1.5
206
25
30
150
125
350
175
2000
350
175
201
8
35
1.50
1.0
2.5
0.5
W000
0.0
-25-
Nacerites
Nacer3e51
Nacertray
Nacernsy
-1.0
Ground 1ram
Greandtrmm
Greanstrm
150
150
356
201
150
Bleration
Iteralien
Figure Training curves of discounted cumulative rewards (top), costs (middle), and WGIoU (bottom) two other exploration strategies in four Gridworld environments.
E.2. Point Maze Environment
Figure shows the constraint learning process of PCSE in the Point Maze environment.
38

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Iteration-22 20
Iteration-5 550
Fround-truth constraint
Ground truth constraint
2
Inferred constralnt
Inferred constralitt
-1
-1
X
Iteration-100
Iteration-200
constraint Infermed constraint
2
Infereed constraint
2-
-1
-2
-2
X
Iteration
Iteration 1000
Ground-truth constraint
Giruund-trrss constraint
Inferred constraint
Inferred constraint
1-
1
0
-2
-2
-2
1
-2
D
2
Figure 6. Constraint learning performance of PCSE for ICRL in the Point Maze environment.
39

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
teratian-20
0.8
Iteretion-25
Iteretion35s
Peralian-50
teretion-100
12.5
Itretiin-2000
12.5
10.0
10.0
10.0
7.
7.5
7.
0.4
0.4
5.0
5.0
02
0.2
2.5
2.5
2.5
2.5
0
5
0.0
0
3
0.0
0.0
5
0.0
0
4
5
0.00
0.0
Reration-20
Iteretion
heration-35
Peration-53
12.5
keretion-100
12.5
Iteration
10.0
10.0
10.0
1.5
7.5
2-
1.0
5.0
0
5
0.0
01
2
5
0.0
0.0
0.0
Itoration22 20
Iteration-25 25
Reration-38
35
Beratian-50
2orotion-000
12.5
Beration-200
12.5
10.0
10.0
10
4
10.0
7.5
3
2-
5.0
5.0
2.5
Beracion-20
0.10
Baratin-25
0.10
Earation355
0.30
5
Peratian-50
1.25
Beration-100
10.0
Beratien-200
10.0
0.05
4
1.00
0.00
0.00
2
5.0
5.0
0.50
0.25
2.5
2.5
Beeatiir terahlor-20
Iteration-25
Benetion-35 -35
10
Peration-50
Terwiion-100 100
Beratien-200
5
10
2
terwclon:20
Peration-25
Beretion-35
0.10
Peration-50
1.25
Reretion-100
10.0
Iterstion-200
10
0.05
0.05
7.5
0.75
Ool
0.00
0.00
0.50
-0.0
-0.0t
-0.00
-011
0
-0.10
-0.10
0.00
3
4
5
0.0
2
3
Figure 7. Constraint learning performance six exploration strategies for ICRL in Gridworld-1. PCSE (Ist row), BEAR strategy (2nd row), e-greedy exploration strategy (3rd row), maximum-entropy exploration strategy (4th row), random exploration strategy (5th row), upper confidence bound exploration strategy (bottom row).
40

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
Rer Peratlon220
Iteretion-25
Peretien-35
Per Peration-50
teration-100
Iteration-200
Coot
0
5
6
01
3
2
3
5
4
5
2eration-20
Iteretion
Ierrtion
Beration-50
Ceratton-233
Iteration
0.8
10.0
2-
0.4
1.0
5.0
10
Conl
0.2
0.5
2.5
0.0
0.0
0.0
0.0
Poration-20
-00
Iteration255
Reration-33
Reratian-50
Eeration-100
Iteration 200
3
Coot
2
Baracion-20
0.10
Baratin-25
0.10
Ierattion33
12.5
Foratlan-50
Peration-100 100
Ierationn200
10.0
15
7.5
7,5
Cosl
0.00
5.0
5.0
5.0
2.5
2.5
Bee teration-20
12.5
Iteretion-25
12.5
Iterttion355
12.5
Beration-S0
15
terwtion-100
Ieratiinn200
10.0
10.0
10.0
5
Cosl
2.5
0
0
0.0
0.0
terwclon:20
Peration-25
Beretion-35
0.10
terwiion:5
teration-100
Itersticn-200
0.05
0.05
0.05
Coot
0.00
0.00
0.00
-0.0
-0.0t
-0.00
-0.05
2
0
0
5
2
-011
-0.10
-0.10
-.11
Figure 8. Constraint learning performance six exploration strategies for ICRL in Gridworld-2, PCSE (Ist row), BEAR strategy (2nd row), e-greedy exploration strategy (3rd row), maximum-entropy exploration strategy (4th row), random exploration strategy (5th row), upper confidence bound exploration strategy (bottom row).

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
teration-20
1.5
Iteretion22 25
Peretien-35
Per Peration-50
teration-100
Iteraticn-200
1.0
Cool
0.5
0
5
0.0
0
3
0.0
2
5
6
0
5
Reration-20
Iteretion
herabinn33
atian-no
teration-100
Iteration
2.0
2.0
Coll
2-
1.0
1.0
5
0.0
0.0
Boratiar-20
Iteration225
Beration
Reratian-50
keration-100
Iteration
12.5
12.5
12.5
10.0
10.0
10.0
3
3
Cort
2-
5.0
5.0
5.0
2
2
2.5
2,5
2.5
Beracion-20
0.10
Baratio-25
0.10
Earation:55
0.10
Beratian-50
Feration-100
Ieratiinn200
5
0.05
4
0.00
0.00
3
Cosl
beratior-20
Ieeration225
Benation-35 35
Per Beration-50
terwtion-100
Iteration-200
5
10
Cosi
terwclon:20
Peration-25
Beretion-35
0.10
Per Peretion-50
terwtion-100
Iterstion-200
0.05
0.05
Cool
0.00
0.00
-0.0
-0.0t
-0.00
-011
0
-0.10
-0.10
5
6
5
2
3
Figure 9. Constraint learning performance six exploration strategies for ICRL in Gridworld-3, PCSE (Ist row), BEAR strategy (2nd row), e-greedy exploration strategy (3rd row), maximum-entropy exploration strategy (4th row), random exploration strategy (5th row), upper confidence bound exploration strategy (bottom row).
42

---

Provably Efficient Exploration in Inverse Constrained Reinforcement Learning
tee abtor-2o
Iteretion-25
Heertion-35
6
Per Zeration-50
teration-100
Iteration-200
10.0
75
2
Cool
2.5
0
5
00
3
0.0
0.0
5
6
5
Reration-20
Iteration
Iteration
10
Peration-50
Peration-100
Iteration
G
2-
Rorattor-20
Iteration.22
12.5
Iteration
12.5
Reratton-50 50
20
heration-100
Itoration 200
10.0
10.0
15
4
7.5
75
10
Cook
2-
5.0
5.0
2.5
2.5
Beracion-20
0.10
Baratio-25
0.10
Earation355
0.30
Beratian-50
Feration-100 100
Berafionn200
5
0.05
Cosl
0.00
0.00
teratior-20
Iteration-25
Renation-35 355
Bee Zeration-50
terwtion-100
Ieeratien-200
Cost
0
terwclon:20
Peration-25
Berelion335
0.10
Per seretton-30
teration-100
Iteration-200
0.05
0.05
Cool
0.00
0.00
-0.0
-0.0t
-0.00
0
5
5
2
3
-0.1
-0.10
-0.10
Figure 10. Constraint learning performance six exploration strategies for ICRI. Gridworld-4. PCSE (Ist row), BEAR strategy (2nd row), e-greedy exploration strategy (3rd row), maximum-entropy exploration strategy (4th row), random exploration strategy (5th row), upper confidence bound exploration strategy (bottom row).
43


Reviews:
[{"review_id": "v9WdUxFfNs", "reviewer": "Reviewer_SXpM", "summary": "The authors propose a pair of elegant exploration methods for a variant of the inverse constrained RL problem where one wants to recover the entire set of feasible constraints and provide corresponding sample complexity benefits.\n\n\n## Update After Rebuttal\nThe authors added in a discussion of some of the points of confusion I originally had to the paper. I already factored this into my evaluation of the paper, and hence maintain my score", "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": "Dear Reviewer SXpM, we sincerely value your time and effort in evaluating our work. We appreciate your recognition and have prepared comprehensive responses and clarifications to address each point you raised. We hope these responses can resolve your concerns.\n\n>*Q1. Prior work in ICRL recovers a single constraint ... When faced with a novel task, it is trivial to figure out which constraint to enforce. This is much less true for set-recovery approaches. Could you comment on this fact or how you would select within the set (potentially reducing the complexity of the overall estimation problem)?*\n\n**A1.** Thank you for raising this concern. Compared to prior ICRL works, the set-recovery approach delays selecting specific constraints, enabling analysis of the intrinsic complexity in inverse constraint inference (ICI) problems. Next, we identify two cases of constraint selection when faced with a novel task.\n\nFor hard constraints, all constraints in the set are equivalent for a novel task, as the cost function value does not matter ($c(s,a)=1$ and $c(s,a)=2$ both prohibit $(s,a)$). Thus, any feasible constraint can be selected. \n\nFor soft constraints, constraints in the set differ for a novel task. The value of each cost function matters due to task differences in dynamics and rewards. Therefore, a generalizable learned constraint should come from the intersection of feasible sets from old and novel tasks. The selection criterion should depend on differences in dynamics and rewards. As a result, visits to some states are no longer necessary given novel task specifications.\n\n---\n>*Q2. There are several assumptions made in this paper that are fairly unusual in the literature ... Could you (a) call these out more explicitly / contrast them with the assumptions in [3] and (b) explain why I wouldn't want to analysis closer to that of DAgger if I can freely query the expert?*\n\n**A2.** Thank you for this suggestion. We have revised Assumption 4.3 to highlight all these assumptions explicitly. \n\nNext, we distinguish two key differences. First, unlike [3], which assumes the expert policy is safe but not necessarily optimal, we assume it is both safe and optimal. Aligning with a suboptimal safe policy might degrade reward performance, as it might exclude constraints that ensure the safety of a safe-optimal policy since a safe optimal policy makes the best use of constraint tolerance while suboptimal safe policies might not. Second, we adopt an online setting for flexibility and real-time adaptation, while [3] adopts an offline setting. We acknowledge that offline setting is an intriguing research direction for ICRL.\n\nFor (b), could the reviewer explain what is DAgger in part (b)? \n\n---\n>*Q3. At heart, RL / CRL solves a linear program. IRL / ICRL solves the inverse of these problems. Does this perspective provide any insights into your results?*\n\n**A3.** Thank you for this advice. In essence, ICRL alternates between updating an imitating policy with CRL and learning constraints via ICI until the imitation policy reproduces expert demonstrations. In our setting, the estimation of the expert policy and dynamics reproduces expert demonstrations, while constraints are inferred through subsequent updates of advantage functions.\n\n---\n>*Q4. Prior work commonly assumes access to a parametric class of functions to avoid \"too expressive\" constraints that forbid an unnecessarily wide set of expert behavior. Is it possible to adapt your work to this more practical setting (with the current results being a special case with the full set of constraints)? It would be interesting if this would provide tighter sample complexity guarantees (which I suspect it does).*\n\n**A4.** Thank you for this advice. We beg to differ that we parametrically define the feasible cost set in Lemma 4.5 as\n$c=A^{r,\\pi^E}_ {\\mathcal{M}}\\zeta+(E-\\gamma P_{\\tau})V^c$, where $\\zeta$ and $V^c$ can alter. In addition, we avoid \"too expressive\" constraints by not penalizing $(s,a)$ with fewer rewards than the expert in case (iii) in Lemma 4.4.\n\n---\n>*Q5. 1) Discuss [1,2,3] and reword the last paragraph in Sec.2. 2) Repeat the message of 'constraining candidate policies' in PCSE. 3) Mention the drawbacks of entropy regularization in ICRL in the 3rd paragraph. 4) Can [4-6] adapt to ICRL settings?*\n\n**A5.** Thanks for your valuable feedback. We have revised the paper accordingly. The details are not presented here due to 5000 rebuttal character limit.\n\n---\n**References**\n\n[1] Simplifying constraint inference with inverse reinforcement learning. NeurIPS, 2024.\n\n[2] Your learned constraint is secretly a backward reachable tube. arXiv:2501.15618.\n\n[3] Learning shared safety constraints from multi-task demonstrations. NeurIPS, 2023.\n\n[4] Agnostic system identification for model-based reinforcement learning. ICML, 2012.\n\n[5] The virtues of laziness in model-based RL: a unified objective and algorithms. ICML, 2023.\n\n[6] Hybrid inverse reinforcement learning. ICML, 2024.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "There is fairly limited experimental evaluations -- I think it would be relatively easy to run more thorough experiments.", "theoretical_claims": "I read all the theorems and skimmed the proofs -- nothing seemed egregiously wrong to me.", "experimental_designs_or_analyses": "Yes, they seemed correct but limited.", "relation_to_broader_scientific_literature": "Essentially, the authors considered a setting (ICRL) that has received much study before but provided an interesting pair of exploration strategies to solve the problem with tighter sample complexity guarantees than prior approaches.", "essential_references_not_discussed": "Could you add in a discussion of https://openreview.net/forum?id=T5Cerv7PT2 and https://arxiv.org/abs/2501.15618 in the paper? Also, there definitely has been prior work on sample complexity in ICRL (e.g. https://arxiv.org/abs/2309.00711), so I would reword the last paragraph in Sec. 2.", "other_strengths_and_weaknesses": "- I appreciated the clarity of the justification for the second algorithm's sample complexity benefits over the first (restricting the set of policies consider to only those that could be optimal). It would be good to perhaps repeat this message at other parts of the paper as I thought it was particularly interesting upon reflection.", "other_comments_or_suggestions": "- One of the key issues with entropy regularization in ICRL is that it frequently leads to the recovery of constraints that forbid *all* behavior the expert didn't take (as the learner visits all reachable states with nonzero probability). It might be good to mention this in your third paragraph.\n\n- The experiments here are extremely limited. While I don't think it is required, it would of course make things a stronger paper to see if some of these methods could be adapted to more high-dimensional settings, perhaps using open source code like https://github.com/konwook/mticl.", "questions_for_authors": "1. Most (if not all) of the prior work you cite in ICRL recovers a single constraint, rather than a set of feasible constraints. Then, when faced with a novel task, it is trivial to figure out which constraint to enforce. This is much less true for set-recovery approaches. Could you comment on this fact or how you would select within the set (potentially reducing the complexity of the overall estimation problem)?\n\n2. There are several assumptions made in this paper that are fairly unusual in the literature, including a deterministic expert, a known constraint tolerance, the expert actually being the constraint-saturating policy, and if I'm reading it correctly, the ability to query the expert (rather than a fixed set of demonstrations). Could you (a) call these out more explicitly / contrast them with the assumptions in work like that of https://arxiv.org/abs/2309.00711 (who also derive some elementary sample complexity results) and (b) explain why I wouldn't want to analysis closer to that of DAgger if I can freely query the expert? The usual justification for the latter is transferring the constraint to new tasks (as otherwise you could directly replay the observed action frequencies and get strong sample complexity guarantees as the expert is assumed to be the optimal safe policy), but I'm not quite sure how to make that argument in this constraint set recovery setting.\n\n3. At heart, RL / CRL are solving a linear program. IRL / ICRL can be seen as solving the inverse of these problems. Could you comment on whether this perspective provides any insights on your results?\n\n4. In prior work, it is common to assume access to a parametric class of functions to avoid \"too expressive\" constraints that forbid an unnecessarily wide set of expert behavior. Is it possible to adapt your work to this more practical setting (with the current results being a special case with the full set of constraints)? It would be interesting if this would provide tighter sample complexity guarantees (which I suspect it does).\n\n5. This is a bit of a vague question but your analysis bears some similarity to the standard simulation lemma analysis. However, when you have access to an expert, the analysis in https://arxiv.org/abs/1203.1007 and more modern variants like https://arxiv.org/abs/2303.00694 or  https://arxiv.org/abs/2402.08848 are known to provide stronger guarantees. I'd be curious to know if this is also true in the ICRL setting.", "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": "qI2MFscoKJ", "reviewer": "Reviewer_fGXy", "summary": "The paper presents a new exploration approach for inverse constrained reinforcement learning (ICRL). in ICRL, the goal is to identify (safety) constraints and a well-performing policy from expert demonstrations resp. an interactive environment. The paper proposes a theoretically motivated way for efficient exploration, i.e. sampling strategies, to learn a good and robust policy.\nThe proposed method is introduced, formalized and discussed; experiments on several environments are performed to compare the performance against baseline techniques.", "questions": "", "limitations": "", "rating": 3, "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": "Dear Reviewer fGXy, we sincerely appreciate your valuable and constructive comments. We have carefully considered your comments and hope the following responses address your concerns satisfactorily.\n\n> *Q1. ...PCSE (red line) converges much faster and is therefore better than the baselines, but this is not really apparent from Figure 3.  ... is the improvement statistically significant over the other techniques? From the plots, it appears as if all techniques perform more or less the same without major differences, but maybe this is an artifact of the presentation and not the results themselves.*\n\n**A1.** Thank you for raising this concern. We argue that the improvement in PCSE's convergence is significant from several key perspectives.\n\nFirst, since ICRL recovers safety constraints, both cumulative rewards (top row) and WGIoU (bottom row) are considered valid only after the corresponding cumulative costs of an exploration strategy converge to those of the expert policy. As shown in the middle row of Figure 3, which illustrates the discounted cumulative costs, PCSE (red line) converges faster to the costs of the expert policy (grey line) compared to other baselines. \nIn Gridworld 1 and Gridworld 3, the WGIoU score (bottom row) of PCSE further confirms this convergence, which measures the similarity between the recovered and ground-truth constraints. In Gridworld 2 and Gridworld 4, the discounted cumulative rewards (top row) of PCSE further support this convergence. \n\nSecond, we present quantitative visualization results in Figures 7, 8, 9, and 10 in the Appendix from page 39 to 42. We do not include them in the main part due to page limit. These figures depict the learned constraints at selected iterations, further demonstrating that PCSE learns feasible constraints faster than the other exploration methods across the four gridworld environments. \n\nFinally, we provide experimental results for comparison of PCSE and two additional baselines, max entropy and upper confidence bound, in Figure 5 in the Appendix (page 37).", "claims_and_evidence": "- The methods are supported by a theoretical foundation\n- BEAR and PCSE and claimed to be more efficient than other baselines, which is maybe supported, but not clear (see comments on experiments below).", "methods_and_evaluation_criteria": "The selection of discrete and continuous environments are good and sufficiently representative. One can always wish for more, of course, e.g. mujoco with safety constraints or safety-gymnasium, but the selected ones are okay to proof the point of the experiments IMHO.", "theoretical_claims": "The argumentation and motivation for the theoretical claims appear sound, but I have not checked them in detail.", "experimental_designs_or_analyses": "BEAR and PCSE are evaluated both in multiple discrete and continuous environments and against an expert policy with groundtruth data and four baseline exploration approaches.\nThe execution and design of the experiments is reasonable and sufficiently broad.\nThe presentation of the results is, however, a bit strange and mostly done through Figure 3 and a textual interpretation.\nIt is stated that PCSE (red line) converges much faster and is therefore better than the baselines, but this is not really apparent from the Figure itself. I would have preferred a more thorough evaluation, e.g., is the improvement statistically significant over the other techniques? From the plots it appears as if all techniques perform more or less the same without major differences, but maybe this is an artifact of the presentation and not the results themselves.\n\nEdit after rebuttal: The authors addressed my concerns in their rebuttal and pointed to supplementary information.", "relation_to_broader_scientific_literature": "references to existing works are given and seem reasonable, however I can't say whether they are complete.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I'm glad to see the effort towards provably efficient exploration. Any sound + justified foundation of (inverse) RL is a great step forward.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "This is not my area and I'm not familiar with the state of the art and prior works.", "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": "pEttZz82xY", "reviewer": "Reviewer_p7jo", "summary": "This paper tackles ICRL, adding safety constraints in addition to classical IRL. \nIt claims to stand out by handling unknown environments, unlike many recent ICRL studies that assume known conditions.\nThe paper focuses on balancing expert imitation with exploration in Inverse Constrained Reinforcement Learning (ICRL), introducing efficient strategies for learning constraints. In particular, the paper's main contribution is a strategic exploration framework with two algorithms: Bounded Error Aggregate Reduction (BEAR) and Policy-Constrained Strategic Exploration (PCSE), both backed by theoretical guarantees. \n\nBoth BEAR and PCSE are supported by rigorous theoretical analyses, providing tractable upper bounds on sample complexity. The paper uses tools like the Hoeffding inequality to derive these bounds, ensuring that the algorithms achieve Probably Approximately Correct (PAC) optimality.\n\nThe sample complexity analysis is a significant contribution, as it quantifies the number of samples needed for accurate constraint inference, addressing a gap in previous ICRL literature where such guarantees were often absent or limited to specific settings.", "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": "Dear Reviewer p7jo, we sincerely appreciate your constructive feedback and thank you for recognizing the significance of our work. We have carefully considered your suggestions and hope the following response can address your concerns.\n\n> *Q1. Empirical results ..., showing PCSE outperforming baselines ... in terms of rewards, costs, and constraint similarity. One issue is that those baseline algorithms are general-purpose algorithms.*\n\n**A1.** Thank you for raising this concern. \nThe four baselines we selected—random, $\\varepsilon$-greedy, upper confidence bound, and max-entropy—are well-established and effective exploration methods in RL. In our setting, the exploration strategy prioritizes states requiring frequent visits to improve constraint estimation. Our approach, which takes into account the estimation of unknown dynamics and the expert policy via exploration, is underexplored in ICRL literature. Prior ICRL works typically assume a maximum entropy framework, and we include it as a baseline in our experiments for Gridworld and PointMaze.\n\n---\n> *Q2. Testing on additional continuous or larger-scale benchmarks could strengthen claims of broader applicability.*\n\n**A2.** \nThank you for this advice. We have a relevant discussion in Appendix F. We acknowledge that additional experiments on larger-scale continuous benchmarks could offer deeper insights into the practical challenges and opportunities associated with inferring and transferring constraint information. Such experiments would ultimately help guide the development of more robust and scalable algorithms for ICI.\n\nHowever, it is important to note that sample complexity analysis primarily focuses on discrete state-action spaces [1]. Extending these analyses to continuous spaces presents a significant challenge in the field. Existing algorithms for learning feasible sets [2, 3, 4] struggle when scaling to problems involving large or continuous state spaces. This difficulty arises because their sample complexity is directly tied to the state space size, posing a substantial limitation, particularly since real-world problems often involve large or continuous domains. Continuous environments typically require the use of function approximation techniques, additional assumptions (such as smoothness or linearity), and more sophisticated exploration strategies. Moreover, generalizability remains a key concern, as continuous domains are infinite and depend heavily on effectively approximating value functions, policies, and constraints. We plan to address the development of a scalable approach for sample complexity analysis in future work.\n\n---\n> *Q3. When the minimum cost advantage (...) becomes small, the sample complexity can be indefinitely large. Maybe add an assumption?*\n\n**A3.** Thank you for your valuable feedback. We agree with the reviewer that adding such an assumption is more rigorous. We additionally assume $\\min_{(s,a)}A^{c,\\ast}_{\\widehat{\\mathcal{M}}\\cup\\tilde{c}}(s,a)\\geq\\psi>0$, and replace this advantage with $\\psi$ in the sample complexity of Theorem 5.6 accordingly. The manuscript has also been revised.\n\n---\n> *Q4. RL solver needs its own sample complexity. This part is missing in the sample complexity.*\n\n**A4.** Thank you for raising this concern. We have considered the sample complexity of the RL phase in the overall sample complexity for BEAR and PCSE. This can be verified in lines 304-306 (left column) in the main paper and lines 1511-1514 in the proof for Theorem 5.5 in the Appendix (page 28). \n\nTo highlight this point, we have revised the relevant paragraph in the manuscript accordingly.\n\n---\n> *Q5. The reviewer shares some important insights into PCSE from a Bayesian perspective in Relation To Broader Scientific Literature.*\n\n**A5.** Thank you for your valuable feedback. We appreciate the reviewer’s justification of PCSE from a Bayesian perspective. We value this insight and have included these relevant studies in the related work section. The details are not presented here due to 5000 character limit.\n\n---\n> *Q6. I don't think linear MDPs for future research are particularly interesting, as linear MDPs are almost never practical.*\n\n**A6.** Thank you for this suggestion. The key assumption in a linear MDP is that both the dynamics and rewards are linear with respect to underlying features of the state and action space. We agree with the reviewer that this assumption is strong and, as a result, may not be very practical in real-world scenarios. In response, we have revised the relevant section of the manuscript in Appendix F.\n\n---\n**References**\n\n[1] Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep 32 (2019): 96.\n\n[2] Towards theoretical understanding of inverse reinforcement learning. ICML, 2023.\n\n[3] Is inverse reinforcement learning harder than standard reinforcement learning? ICML, 2024.\n\n[4] Offline inverse RL: New solution concepts and provably efficient algorithms. ICML, 2024.", "claims_and_evidence": "The primary claim is that the proposed BEAR and PCSE algorithms achieve efficient constraint inference in ICRL with unknown dynamics.\n\nThis is theoretically backed by rigorous sample complexity analyses (e.g., Theorems 5.5 and 5.6) using tools like Hoeffding’s inequality, demonstrating PAC optimality with high probability.\n\nEmpirical results in Gridworld and Point Maze environments further corroborate this, showing PCSE outperforming baselines like maximum-entropy and ε-greedy in terms of rewards, costs, and constraint similarity. One issue is that those baseline algorithms are general-purpose algorithms. Another issue is that the environments are too simple. However, the theoretical claim mitigates this crude empirical result issue.", "methods_and_evaluation_criteria": "The two algorithms—Bounded Error Aggregate Reduction (BEAR) and Policy-Constrained Strategic Exploration (PCSE)—are thoughtfully designed to address the challenge of efficient exploration without relying on generative models, a common limitation in prior ICRL work. BEAR minimizes cost estimation errors across all state-action pairs, while PCSE focuses exploration on plausibly optimal policies, leveraging a constrained optimization approach (Section 5.2).\n\nThe use of a Probably Approximately Correct (PAC) optimality criterion (Definition 4.9) to evaluate the closeness of inferred constraints to the true feasible set is a rigorous and appropriate metric.\n\nEvaluation is conducted using benchmark datasets—Gridworld for discrete settings and Point Maze for continuous environments—which are standard in RL research and reasonable choices for testing ICRL. Gridworld (7x7 grid, Section D.1) offers a controlled, interpretable environment to assess exploration strategies, while Point Maze (5m x 5m, Section D.3) introduces continuous state spaces and stochasticity, reflecting real-world complexity.\n\nTesting on additional continuous or larger-scale benchmarks could strengthen claims of broader applicability.", "theoretical_claims": "* When the minimum cost advantage (the smallest difference in cost between the optimal action and any other action across all state-action pairs in the constrained Markov Decision Process (CMDP)) becomes small, the sample complexity can be indefinitely large. Maybe add an assumption?\n* RL solver needs its own sample complexity. This part is missing in the sample complexity.", "experimental_designs_or_analyses": "* Point Maze has a 4D continuous state space (x, y coordinates plus velocities), which is a step up from Gridworld’s discrete 2D grid. However, the environment is still relatively simple—a flat 5m x 5m square with a single constraint at (-1,0) and a goal within 0.5m. This lacks the intricate obstacles, walls, or multi-goal complexity of typical maze benchmarks (e.g., OpenAI Gym’s Maze environments), limiting its ability to test navigation in truly continuous, cluttered spaces.", "relation_to_broader_scientific_literature": "PCSE’s restriction to a candidate policy set extends ideas from Bayesian IRL’s posterior sampling (Ramachandran and Amir, 2007), where a distribution over reward functions guides policy inference. However, PCSE focuses on constraints and leverages a structured policy set, akin to constrained policy optimization in Achiam et al. (2017). Unlike Liu et al. (2023), who apply bi-level optimization in ICRL without strategic exploration, PCSE’s targeted policy constraint offers a novel efficiency boost.\n\nPCSE’s selective exploration aligns with active sampling in Balakrishnan et al. (2020), who use Bayesian optimization to explore reward functions in IRL. The paper advances this by applying it to constraints in ICRL and eliminating generative model reliance, addressing scalability issues noted in Chan and van der Schaar (2021, \"Scalable Bayesian Inverse Reinforcement Learning\"), where BIRL struggles with large state spaces due to MCMC sampling demands.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The work is significant for advancing ICRL in safety-critical domains where constraints are paramount but ill-defined. The theoretical sample complexity bounds (Theorems 5.5 and 5.6) fill a gap in ICRL literature. While not an application-driven ML paper per se, its focus on unknown dynamics and minimal constraint sets aligns with real-world use cases where expert data is available but environmental models are not.\n\nDespite overall clarity, the omission of the effect of RL solver’s sample complexity in Theorem 5.5 (Section 5.1) on the overall sample complexity is glossed over, potentially confusing readers expecting a full efficiency analysis.", "other_comments_or_suggestions": "I don't think the Linear MDPs for future research is a particularly an interesting idea, as Linear MDPs are almost never practical.", "questions_for_authors": "How do you think about the effect of sample complexity of RL solver on the overall sample complexity?", "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 three reviewers recommended the acceptance of paper and appreciated the authors' responses to their questions and concerns. The theoretical contributions are novel and interesting, and the proposed algorithms show advance our current approaches to Inverse Constrained Reinforcement Learning (ICRL). For a paper with a strong theoretical focus, the empirical evaluation is adequate but could benefit from being more comprehensive overall. Based on the above, I recommend accepting the paper. 
To improve the paper, the authors should explicitly state and discuss the strong assumptions made in the theoretical analysis (as already indicated in the rebuttal). Additionally, they should incorporate a more detailed discussion on the implications of these assumptions and potential directions for relaxing them in future work.
Decision: Accept (poster)