How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach

Summary

The paper studies IRL in linear MDPs. The authors first demonstrate that the feasible reward set cannot be efficiently learned in large state and action spaces. To address this challenge, they propose a new IRL framework called reward compatibility, where the goal is to learn a classifier that determines whether the expert is approximately optimal for a given reward. Using CATY-IRL, they also introduce a new sample-efficient algorithm for this task, which first explores the MDP via reward-free exploration (RFE) and then evaluates whether a given reward is compatible with the expert's demonstrations. Furthermore, for the tabular setting, they provide a tight minimax lower bound and show that a similar bound also improves on existing lower bounds for RFE. Lastly, the authors propose a novel problem setting of objective-free exploration, which generalizes RFE to arbitrary tasks of interest.

Strengths

The paper provides a good and original contribution to the challenging problem of IRL in large state-action spaces. In my opinion, its strengths are: 1. Technical quality: The authors use elegant notation and carefully introduce all symbols. Moreover, clear proofs for all results are provided in the appendix. 2. Sample complexity bounds: The sample complexity of CATY-IRL is thoroughly analyzed for tabular MDPs, tabular MDPs with linear rewards, and linear MDPs. Additionally, a tight minimax lower bound for the tabular setting is given. This lower bound is particularly appreciated, as lower bounds are still rare in the IRL literature. 3. Originality: After proving that identifying the feasible reward set is intractable, the authors introduce the novel problem setting of checking for reward compatibility and provide a sample efficient algorithm for it.

Weaknesses

1. Motivation: While original, the motivation for learning a reward compatibility classifier is not entirely clear to me. I would expect the authors to better explain its usefulness and potential applications. 2. Writing: The paper is not easy to understand on the first read. There are many propositions and theorems, but more emphasis on motivation and intuition building would be beneficial. For instance, a simple example for Proposition 3.1 could help build geometric intuition. 3. Related work: The authors introduce reward non-compatibility as a novel metric for IRL. However, minimizing the suboptimality of the expert is a core idea behind many imitation learning and IRL algorithms, such as GAIL and others. Of course, in the unregularized setting minimizing the suboptimality would lead to trivial solutions. However, I would expect a discussion about similarities and differences to min-max IL/IRL in the main part of the paper. 4. Computational complexity: The authors claim that their algorithm is also computationally efficient, but I couldn't find a discussion about this. 5. This is a minor point, but in line 103 you use but don't introduce the notation $Y^X$ for the set of functions mapping from $X$ to $Y$. Moreover, slightly inconsistently the set of functions from $X$ to $\Delta^Y$ is denoted as $\Delta_X^Y$. Why don't you change the notation to $\Delta_Y^X$?

Questions

How would you apply your algorithm to a real world IRL problem? What is the computational complexity of the classification step?

Rating

7

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

I think the practical limitations should be discussed more extensively.

Summary

This paper finds that the feasible reward set cannot be efficiently learned even under linear MDPs. Therefore, the paper proposes a new notion called "reward compatibility" that generalizes the notion of "feasible set" and thereby casts IRL as a classification problem. The paper proposes an algorithm to solve this new classification problem and theoretically show that the sample complexity of the proposed algorithms is independent of state cardinality for linear MDPs.

Strengths

1. This paper proposes a new notion called "reward compatibility" and novelly formulates IRL as a classification problem based on the notion. 2. This paper is theoretically solid, which is also the biggest strength of the paper.

Weaknesses

1. The paper title is a little bit exaggerating. The title is "scale IRL to large state spaces", while what the paper does is to scale one specific kind of IRL, i.e., learning the feasible reward set, to large state spaces. In fact, many other kinds of IRL algorithms can work quite efficiently in continuous state spaces without the linear MDP assumption. For example, maximum likelihood IRL [1] is sample efficient where only one sample is needed for each reward update. I think what the authors mean here is that learning the feasible reward set is difficult in large state space, however, learning feasible reward set is only a kind of IRL, but does not represent all IRL methods. I suggest that the authors change the general terminology "IRL" to some more specific terminologies, given that some other kinds of IRL methods can already scale to large state spaces. 2. The paper uses the terminology "online IRL" to represent IRL that needs to interact with the environment. The paper also adds a footnote to explain this notion. I know that this is to contrast offline IRL. However, it is still confusing because online IRL is already defined in literature [2,3,4], i.e., the IRL setting where the demonstrated trajectories are revealed sequentially. Therefore, I highly suggest the authors to use another terminology to avoid confusion. 3. In example 4.1, the authors mention that the reward function with smaller $\bar{C}(r)$ is more compatible. This can be questionable. For example, suppose $r_2=2 r_1$, then $\bar{C}(r_2)>\bar{C}(r_1)$ if they are both positive. However, can we say that $r_1$ is more compatible than $r_2$? The MDPs are equivalent if we multiply the reward by a constant. Then intuitively, $r_1$ and $r_2$ should be same compatible right? 4. Lack of empirical evaluation. [1] Maximum-likelihood inverse reinforcement learning with finite-time guarantees [2] First-person activity forecasting with online inverse reinforcement learning [3] Online inverse reinforcement learning under occlusion [4] Learning multi-agent behaviors from distributed and streaming demonstrations

Questions

Please see weaknesses.

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

3

Limitations

The limitation is discussed in Section 7.

Summary

Even under the strong assumption implicit in Linear MDPs, the learning of the set of rewards that make the expert’s policy optimal doesn’t scale well. This improves somewhat, if additionally a notion of compatibility of rewards is introduced, because in this way and under these conditions the IRL problem can be seen as a classification task. In this context a number of theoretical results are possible minimax optimality of a thus formulated IRL algorithm, complexity bounds and some contribution to the complexity theory of reward-free exploration.

Strengths

Outsourcing some of related work to the appendix seems a good idea here, as the proper introduction is still readable and interesting. However, it may have been an alternative option to move the “original contributions” to the appendix as these are already mentioned in the abstract and in --- the paper. The paper aims at much, and although it delivers, but could be more focused and concise.

Weaknesses

“How to” is not really addressed, “How to Scale Inverse RL to Large State Spaces?” should be “How does Inverse RL Scale to Large State Spaces?” The separation of exploration and classification phases may not appear to be a problem at this level of abstraction, but practically this can be a forbidding features of an algorithm. The approach uses a restrictive problem setting, while it could be preferable to attempt to discover any compositional structure or any latent low-dimensional manifolds, as would be the present in any practical problem if the problem can be treated at all at larger scales. No simulation included, although it should be easy provide some illustration, in particular for any worst-case results. Objective-free exploration need more study to receive the attention that it is claimed to deserve, but the current definition probably needs to be more precise. Here (as in most contributions to this conference) the use of display equations is dearly missed. Couldn’t the amount of ink be used to measure the length of the papers? The use of color in the manuscript could be more systematic, if it is encouraged at all. There is too much material in the paper. It may be tempting to publish a systematic study at a conference to reach some visibility, but it creates an imbalance among the contribution and may bias future submission.

Questions

Would objective-free exploration be independent on the linear MDP assumption? Is it needed at all in the present paper? Can you compare to other IRL algorithms?

Rating

8

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

Practical application is limited, but this is outside the scope of this very impressive paper.

Summary

This paper shows that finding the feasible reward set in IRL needs to sample $\Omega(S)$ number of samples, even when the MDP possesses a linear structure. To enable more efficient scaling with $S$, the authors propose another task in IRL called rewards compatibility: deciding whether $\pi^{E}$ is $\epsilon$-optimal under a given reward $r$. They further use reward-free algorithms to solve such tasks and propose a matching lower bound. As a byproduct, the lower bound also improves the existing lower bounds in tabular reward-free RL.

Strengths

The theoretical analysis is solid. In particular, the lower bounds for feasible reward set learning and reward compatibility are novel and significant as they quantify the hardness of these two tasks in IRL.

Weaknesses

1. The reward compatibility framework is not that interesting in my opinion because it requires you to input a reward function, which indeed makes IRL a standard RL problem given that reward. More specifically, the reward compatibility framework is just policy optimization and evaluation of $\pi^E$ under a given reward $r$, which has been studied sufficiently before. 2. The algorithms that the authors propose are also just the existing algorithms in standard RL, so there is no novelty in the algorithm design.

Questions

The lower bound in Theorem 3.2 characterizes the difficulty of identifying the exact feasible reward set. However, in many cases we just want to learn a feasible reward with some desirable properties instead of the whole set. For this setting will the lower bound still hold?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

None.