Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning?

We thank the reviewer for the valuable feedback on our paper. We respond to the specific questions as follows.

At times, the language and writing was a bit informal and sometimes confusing to interpret.

We appreciate the reviewer for bringing up this question. We have made extensive revisions and polished Appendix C significantly in the latest version. We have addressed the issues you mentioned, and you can review the latest version. For example, regarding "our method that considers is greater than theirs", detailed explanations are provided in the discussion above Lemma C.1 in the most recent version. Concerning "metric can't capture transitions", comprehensive explanations can be found in the discussion above Proposition C.4 in the latest version.

I would urge the authors to rewrite their comparison with prior work in Appendix C, focusing on cases where one subsumes the other, and giving concrete examples when your algorithm(s) can achieve guarantees while previous algorithms cannot. What is currently lacking is a distinction in the writing between (1) comparing the quantities $d^{\pi}$ and $d^{\sf all}$ themselves to prior work; (2) comparing guarantees that your algorithms can achieve to guarantees that algorithms from prior work can achieve.

Thank you very much for your suggestions. We have made substantial revisions in the latest version of Appendix C as per your requests (see Appendix C in the latest version).

(minor) weakness: the upper/lower bounds seem to be loose. In particular, it would be good if the authors commented on the fact that the lower bound has a min{S,A} term - where does this come from? can it be improved? In general, the regime that we care about is when S≥A, so the fact that the rate is only sharp when S≤A is not very meaningful.

About $\textrm{min}\\{S,A\\}$ factor: Regarding $\mathrm{min}\\{S,A\\}$ term, the introduction of $\textrm{min}\\{S,A\\}$ is introduced as follows. In constructing hard instances, there is a step where we need to ensure $\mathbb{P}_h ( s_i| s_i,a_i)=1$ for $i\leq \textrm{min}\\{S,A\\}$. This particular step is crucial for our proof. Exploring ways to improve the lower bound on $\textrm{min}\\{S, A\\}$ could be a promising avenue for future research. We believe our results are still meaningful, and the condition $S < O(A)$ also holds significance. Regarding the lower bound in the online setting, we have made improvements (Theorem G.2), improving the original $\mathcal{O}(H^2SA\textrm{min}\\{S,A\\})$ to $\mathcal{O}(H^3SA\textrm{min}\\{S,A\\})$. Although it does not exactly match the upper bound, it has been significantly tightened. We appreciate the reviewer for bringing up this question.

About $H$ factor: Regarding the lower bound in the online setting, we have made improvements (Theorem G.2), improving the original $\mathcal{O}(H^2SA\textrm{min}\\{S,A\\})$ to $\mathcal{O}(H^3SA\textrm{min}\\{S,A\\})$. Although it does not exactly match the upper bound, it has been significantly tightened. We appreciate the reviewer for bringing up this question. As for the lower bound in the offline setting, even though we employed the same MDP construction as in proving the lower bound in the online setting, we did not fully exploit the property of our MDP construction, where transitions are different for each h, because of the construction of the behavior policy. This results in our lower bound having a dependence on $H$ of $\mathcal{O}(H^2)$. How to prove a tighter lower bound for the $H$-factor would be a highly intriguing avenue for future research.

I'm a bit confused about the discussion of the Hausdorff metric used by Metelli et al. The quantity that they propose seems to be some notion of diameter. I'm not sure why it should go to zero as you collect more samples, as even when $\mathcal{R}=\widehat{\mathcal{R}}$ the quantity doesn't seem like it should be zero since the set of possible rewards could be large. But your results imply that an upper bound on this quantity goes to zero, so what am I missing here?

If we understood correctly, the reviewer is asking why the Hausdorff metric appears to be a kind of diameter for sets and why it tends to zero? The Hausdorff metric $D^{\sf H}$ (see Section C.2) is indeed a measure of distance between sets, not a diameter. For instance, when two sets are equal, the Hausdorff metric becomes zero. And so the upper bound goes to zero.

While the definition of the metric seems mathematically well defined, it seems a bit weird: to define the reward mapping, you need a value and advantage function (V,A) (e.g., Eq. 3.2). However, inside the definition of the metric, you define a new value function of a particular policy and reward function (e.g., in Eq. 3.1). How do these two value functions relate?

$(V, A) \in \mathcal{V} \times \mathcal{A}$ represents a set of parameters, not a value function. Each pair $(V, A)$ determines a solution to an IRL problem (Lemma 2.2). Let $r^\theta = \mathscr{R}(V, A)$, where $\mathscr{R}$ is a reward mapping induced by an IRL problem $(\mathcal{M}, \pi^E)$. The connection between the parameter $\theta = (V, A)$ and the value function defined in Eq. 3.1 on Page 3 is as follows: $V^{\pi^E}_h(s; r^\theta) = V_h(s)$ and $A^{\pi^E}_h(s, a; r^\theta)=A_h(s,a)$.

Many typos throughout, especially in the appendix.

We thank the reviewer for this feedback. We have addressed and corrected the majority of the typos as suggested.

We thank the reviewer for the valuable feedback on our paper. We respond to the specific questions as follows.

... the title of this paper is a little confusing.

Our paper's title “Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning?” aims to convey that we can apply standard RL techniques to address IRL problems, including techniques such as pessimism and some exploring strategies. I apologize for any confusion. In the latest version, we provide the framework for our IRL algorithms in Section E.4. Here, we give a condition (Condition E.4) that is sufficient to do IRL. Then, we illustrate that pessimism can fulfill Condition E.4. We appreciate the reviewer for bringing up this question.

We thank the reviewer for the valuable feedback on our paper. We respond to the specific questions as follows.

The main paper writing needs to be improved...

We sincerely apologize for the confusion caused by writing issues. Thank you very much for pointing out the concrete writing issues, and we have corrected most of them in the latest version.

The current work stops at reward learning, that is, the IRL problem. But without the extra RL step using the learned reward, is an incomplete story… Yes, one can just do planning with the learned reward and learned transition model, but equipping it with traditional model-based guarantees is important for making connections with other relevant works. Model-based guarantee will be unsatisfactory since [1] gives results for general function approximation.

Regarding the use of learned rewards, in fact, we do have guarantees for the performance of performing RL algorithms with the learned rewards. I apologize for any confusion; our previous versions did not emphasize this part. In the latest version, we specifically discuss guarantees for performing RL algorithms with learned rewards (see Section C.4 and Corollary I.6, I.7 in the latest version). We appreciate the reviewer for bringing up this question.

[1] introduces an algorithm for imitation learning under function approximation, analyzing numerous concrete examples such as discrete MDPs, linear models, and GP models. However, our paper focuses on Inverse Reinforcement Learning (IRL) within the tabular setting. Regarding “Yes, one can just do planning with the learned reward and learned transition model, but equipping it with traditional model-based guarantees is important for making connections with other relevant works. Model-based guarantee will be unsatisfactory since [1] gives results for general function approximation.”, we may not have fully understood your meaning. Could you please provide further clarification or explanation?

My score reflects the fact that the generative model setting (samples from every state-action pairs ≈ uniform concentrability) in Lindner et al. (2023), is equipped with pessimism and optimism terms to account for partial concentrability using the usual techniques in offline RL (Rashidinejad, et al. 2021) and thereafter.

While the algorithm in Lindner et al. (2023) also incorporates pessimism, we emphasize a fundamental difference in the purpose of pessimism between Lindner et al. (2023) and our work. In Lindner et al. (2023), the $E^h_k(s,a)$ defined in Eq (FBI) serves as an uncertainty measure, and the algorithm minimizes this $E^h_k(s,a)$ at each step to determine the sampling strategy (see Section 6.1 in Lindner et al. (2023)). On the other hand, our introduction of pessimism aims to impose a high penalty on state-action pairs that are rarely visited. This is done to ensure that the recovered rewards satisfy the monotonicity condition: $\widehat{\mathscr{R}}_h(s,a)\leq \mathscr{R}^\star_h(s,a)$. This condition is crucial for obtaining guarantees in performing RL algorithms with learned rewards, as detailed in our latest version (see Proposition C.6 and Section E.4).

[1] Jonathan D. Chang, Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, Wen Sun. Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage, NeurIPS 2021.

We thank the reviewer for the valuable feedback on our paper. We respond to the specific questions as follows.

Why do you use $d^\pi$ (Definition 3.1) as a (pre)metric between reward functions?

• Unlike generative models, in the offline setting, there are unreachable state-action pairs. We cannot expect the recovered rewards to be very close to the ground truth reward for every state-action pair. As a result, in the offline setting, many classical metrics such as $L_{\infty}$ distance between rewards cannot be employed. Therefore, considering the use of policy and value function to define is a very natural choice.

• $d^\pi$ (Definition 3.1) can provide guarantees for performing RL algorithms or doing transfer learning with learned rewards (see Section C.2 and I.3).

...This is not a metric, and therefore the problem that you highlight in Lemma C.4 for the Hausdorff distance between sets sussists also for your (pre)metric $D^\pi_{\Theta}$ (Definition 3.2)...It might be that the proposed (pre)metric $D^\pi_{\Theta}$is zero even if the reward sets do not coincide.

We first clarify that Lemma C.4 (Lemma C.3 in the latest version) is intended to compare the Hausdorff metric and mapping-based metric, rather than metrics between rewards. The reason for “the proposed (pre)metric $D^\pi_{\Theta}$is zero even if the reward sets do not coincide” is due to the selection of metric between rewards: $d^{\pi}$ (it is easy to see that $d^\pi(r,r')=0$ does not imply $r=r'$). Lemma C.4 (Lemma C.3 in the latest version) aims to demonstrate that $D^{\mathsf{M}}$ is strictly stronger than $D^{\mathsf{H}}$ for some $d$, but lacks a discussion of the mapping-based metric in the first version. Therefore, we have modified Lemma C.4 (Lemma C.3 in the latest version) to include a discussion of both the Hausdorff metric and the mapping-based metric (See Lemma C.3 in in the latest version).

What is the rationale behind choosing the (pre)metric in Definition 3.1?... It does not seem to me that the (pre)metric in Definition 3.1 guarantees anything on how close the performance of the trained RL agent with the learned reward.In "Towards Theoretical Understanding of Inverse Reinforcement Learning" the authors focus on the actual distance between reward functions, not induced value functions. Can the author elaborate?

Regarding the rationale behind choosing the (pre)metric in Definition 3.1 and why we do not use the actual distance between reward functions, please refer to the answer to “ Why do you use $d^\pi$ (Definition 3.1) as a (pre)metric between reward functions?”.

Regarding the lack of guarantees for the performance of the trained RL agent with the learned reward, in fact, we do have guarantees for the performance of the trained RL agent with the learned rewards. We apologize for any confusion; our previous versions did not emphasize this part. In the latest version, we specifically discuss guarantees for performing RL algorithms with learned rewards (see Section C.4 and Corollary I.6, I.7). We appreciate the reviewer for bringing up this question.

Why do your lower bounds not depend on $1-\delta$?

We apologize for any confusion caused. We failed to clarify that our lower bounds also hold for small $\delta$, such as $\delta \leq 1/3$ in the first version. This error has been corrected in our latest version. We appreciate the reviewer for bringing up this question. We believe that our results hold true when $\delta$ is very small, and thus, they are highly meaningful.

How did you manage in the proof of the upper bound the fact that rewards defined as in the ground truth reward mapping are not bounded in $[−1,+1]$ even though the parameters $(V,A)\in\mathcal{V}\times \mathcal{A}$?

Although the reward is not bounded within $[-1, 1]$, we emphasize that $\mathcal{V}\times \mathcal{A}$ is bounded (see the Definition of $\mathcal{V}\times \mathcal{A}$ on page 4). Specifically when $(V,A)\in \mathcal{V}\times \mathcal{A})$, we have $|V_h|_{\infty},|A_h|_{\infty}\leq H-h+1$, which is sufficient for our proof (see the proof of Theorem 4.2).

The lower bounds do not match the upper bounds, especially for what concerns the dependence on the horizon H. What is the reason for this gap?

Regarding the lower bound in the online setting, we have made improvements (Theorem G.2), improving the original $\mathcal{O}(H^2SA\textrm{min}\\{S,A\\})$ to $\mathcal{O}(H^3SA\textrm{min}\\{S,A\\})$. Although it does not exactly match the upper bound, it has been significantly tightened. We appreciate the reviewer for bringing up this question.

As for the lower bound in the offline setting, even though we employed the same MDP construction as in proving the lower bound in the online setting, we did not fully exploit the property of our MDP construction, where transitions are different for each h, because of the construction of the behavior policy. This results in our lower bound having a dependence on $H$ of $\mathcal{O}(H^2)$. How to prove a tighter lower bound for the $H$-factor would be a highly intriguing avenue for future research.

Regarding the $\mathrm{min}\\{S,A\\}$ term, the $\textrm{min}\\{S,A\\}$ factor is introduced as follows. In constructing hard instances, there is a step where we need to ensure $\mathbb{P}_h ( s_i| s_i,a_i)=1$ for $i\leq \textrm{min}\\{S,A\\}$. This particular step is crucial for our proof. Exploring ways to improve the lower bound on $\textrm{min}\\{S, A\\}$ could be a promising avenue for future research. We believe our results are still meaningful, and the condition $S < O(A)$ also holds significance.

‘The proof of the second part of Lemma C.1, although easy, is missing;’ and ‘the proof of Proposition C.2 is missing;’

Thank you for pointing these out. We have added the proofs in Section C.5.

In Section 1, Introduction, when listing the contributions, the authors state that this work contributes at "providing an answer to the longstanding non-uniqueness issue in IRL". This statement is factually false. Indeed, the authors investigate IRL as the reconstruction of the feasible reward set (and this formulation is not introduced in the paper), providing novel analysis for the offline and online (with forward model);

We appreciate the reviewer's feedback. We want to emphasize that, to the best of our knowledge, we are the first to consider IRL using reward mapping instead of just feasible sets. Additionally, we introduce a mapping-based performance metric to address the no-uniqueness problem. We believe our approach differs from previous work (see Section C).

the title has nothing to do with the paper; the paper concerns a sample complexity analysis in the IRL setting, stop. Nothing in the paper gives novel results on whether IRL is harder than RL, so the title must be changed;

Our paper's title “Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning?” aims to convey that we can apply standard RL techniques to address IRL problems, including techniques such as pessimism and some exploring strategies. I apologize for any confusion. In the latest version, we provide the framework for our IRL algorithms in Section E.4. Here, we give a condition (Condition E.4) that is sufficient to do IRL. Then, we illustrate that pessimism can fulfill Condition E.4. We appreciate the reviewer for bringing up this question.

About symbols and typos.

We appreciate this suggestion. We have addressed the modifications related to symbols and typos as suggested in the latest version.

We thank the reviewer for the additional questions. We respond to them as follows.

[On the use of $d^\pi$] … looking at Section C.2, only with $d^{\rm all}$ it is possible to have guarantees when performing RL. It doesn't seem that for the offline setting the authors are able to provide guaranteed w.r.t. . This makes the argument in favor of $d^\pi$ quite weak in my opinion.

We apologize we gave the wrong pointer there, it should be Proposition C.6 in Section C.4.

There we show that, a small $d^\pi$ where $\pi$ is any $\bar\epsilon$ near-optimal policy, combined with monotonicity of the recovered reward ($\hat{r}\le r$ pointwise), ensures an RL guarantee with $\hat{r}$. So $d^\pi$ plus this additional monotonicity condition indeed gives an RL guarantee. Further, our RLP algorithm also guarantees monotonicity (see the blue text in Theorem 4.2, bottom of Page 7) along with the $D^{\pi}$ guarantee. We believe this justifies the $d^\pi$ metric as well as our offline results.

[On the dependence on $\delta$] …proper use of $\tilde{O}(\cdot)$ should not hide the polynomial dependence on $\log(1/\delta)$... This spots an important lack of tightness since the lower bound does not diverge to infinity when $\delta\to 0$.

For our upper bounds, we were indeed using $\tilde{O}(\cdot)$ to suppress $\log(1/\delta)$ and the other polylog factors, as we explained in each occurrence of it in the upper bounds.

For our lower bounds, indeed, the statements are only for $\delta=1/3$ (which then implies the same statement for all $\delta\le 1/3$) for which $\log(1/\delta)$ is a constant. We have slightly tweaked the statements to clarify this, but we agree with the reviewer that this is looser than what we want.

Upon initial inspection, we believe it is possible to improve our lower bounds to have an additional $\log(1/\delta)$ factor, by using the inequality $1-{\rm TV}\ge \frac{1}{2}e^{-\rm KL}\ge \delta$ whenever ${\rm KL}\le \log(1/(2\delta))$ instead of Pinsker’s inequality, and arguing that $n\le O(\log(1/\delta))$ (times the other factors) will result in ${\rm KL}\le \log(1/(2\delta))$ (as KL scales linearly in the sample size $n$ due to its additivity). However, we need to go through the full argument more carefully. We will include this in our final version if it works out.

[Pessimism] By re-reading the paper, I realized that the use of pessimism in the reward function has a quite strange effect compared to pessimism in standard off-line RL. Here, pessimism is directly applied to the reward function (eq. 4.4) but it does not seem to have a significant role in the ability to achieve the desired results… if the role of pessimism is so marginal in the paper (as I suspect at this point) and if without using it, it is possible to derive the same results, this is an important concern to report. I would really appreciate it if the authors could say whether without pessimism they can obtain (apart from constants) the same results.

We agree that for reward estimation ($d^\pi$ or $d^{\rm all}$ guarantee) alone, a simple empirical mean estimator is enough, as the reviewer pointed out.

However, pessimism additionally ensures (entrywise) monotonicity of the learned reward (cf. blue text in Theorem 4.2). The role of this monotonicity is in downstream RL (Proposition C.6, Thm/Corollaries I.4->I.7), where monotonicity is required for the learned policy (from the recovered reward) to have guarantees.

This is fully aligned with the use of pessimism in standard offline RL (as per the reviewer’s question), where the monotonicity of the rewards ($\hat{r}\le r$ pointwise) is crucial for achieving learning guarantees under single-policy concentrability only instead of all-policy concentrability. For example, in offline bandits, we need to rule out seldom-chosen bad arms (not covered by the optimal policy) that happen to have a large empirical reward by a big negative bonus.

If the reviewer agrees with this, we then also believe this kind of parallellization to standard offline RL gives some justification to our title. As an example, we gave a more modular argument in Section E.4 on how pessimism implies IRL ($d^\pi$ bound + monotonicity) in a black-box fashion. (Looking back, we probably should have structured the main results using this, where we first show pessimism implies IRL black-box by this argument, then reduce to standard pessimistic offline RL algorithms to achieve the pessimism. We will think about whether we can restructure our paper along this direction in its next version).

---

We appreciate again the reviewer's prompt response to our rebuttal, and would be happy to answer additional questions before the rebuttal period ends.

Dear AC,

Thank you for your question and pointing out the work [1]. The algorithm in [1] utilizes an MDP solver to solve an MDP where the reward is the indicator of the expert policy, followed by imitation learning. It is important to note that the algorithm in [1] is limited to imitation learning and cannot learn rewards. In contrast, our algorithm not only enables imitation learning (using an MDP solver to solve the MDP with the rewards learned by our algorithms RLP and RLE) (see Section C.4) but also provides performance guarantees for using the learned rewards to perform RL in different environments via transfer learning (see Corollary I.6, I.7), a feature not achievable by the imitation Algorithm in [1].