Provably Efficient Exploration in Inverse Constrained Reinforcement Learning

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.

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.

A1. Thank you for raising this concern. The 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.

---

Q2. Testing on additional continuous or larger-scale benchmarks could strengthen claims of broader applicability.

A2. Thank 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.

However, 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.

---

Q3. When the minimum cost advantage (...) becomes small, the sample complexity can be indefinitely large. Maybe add an assumption?

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.

---

Q4. RL solver needs its own sample complexity. This part is missing in the sample complexity.

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).

To highlight this point, we have revised the relevant paragraph in the manuscript accordingly.

---

Q5. The reviewer shares some important insights into PCSE from a Bayesian perspective in Relation To Broader Scientific Literature.

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.

---

Q6. I don't think linear MDPs for future research are particularly interesting, as linear MDPs are almost never practical.

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.

---

References

[1] Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep 32 (2019): 96.

[2] Towards theoretical understanding of inverse reinforcement learning. ICML, 2023.

[3] Is inverse reinforcement learning harder than standard reinforcement learning? ICML, 2024.

[4] Offline inverse RL: New solution concepts and provably efficient algorithms. ICML, 2024.

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.

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.

A1. Thank you for raising this concern. We argue that the improvement in PCSE's convergence is significant from several key perspectives.

First, 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. In 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.

Second, 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.

Finally, 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).

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.

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)?

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.

For 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.

For 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.

---

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?

A2. Thank you for this suggestion. We have revised Assumption 4.3 to highlight all these assumptions explicitly.

Next, 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.

For (b), could the reviewer explain what is DAgger in part (b)?

---

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?

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.

---

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).

A4. Thank you for this advice. We beg to differ that we parametrically define the feasible cost set in Lemma 4.5 as $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.

---

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?

A5. Thanks for your valuable feedback. We have revised the paper accordingly. The details are not presented here due to 5000 rebuttal character limit.

---

References

[1] Simplifying constraint inference with inverse reinforcement learning. NeurIPS, 2024.

[2] Your learned constraint is secretly a backward reachable tube. arXiv:2501.15618.

[3] Learning shared safety constraints from multi-task demonstrations. NeurIPS, 2023.

[4] Agnostic system identification for model-based reinforcement learning. ICML, 2012.

[5] The virtues of laziness in model-based RL: a unified objective and algorithms. ICML, 2023.

[6] Hybrid inverse reinforcement learning. ICML, 2024.