Sub-optimal Experts mitigate Ambiguity in Inverse Reinforcement Learning

It would be powerful to see it actually employed in a case study to see how such a technique would be used. Even outside of empirical evidence, it would aid in readability of the paper to see how the notations used in the theoretical sections are actually used in practice. To that end, even a case study with a toy example would go a long way.

We thank the Reviewer for raising this point. We have added an experiment to show how the presence of sub-optimal experts limit the feasible reward set in a tabular domain. We refer the reviewer to our reply to Reviewer 6BJu.

Finally, we agree with the Reviewer that an intuitive example can benefit the reader. Given the page limit, however, we preferred to give more space to an appropriate formalism to model the problem. We will make use of the additional page to insert an intuitive example on a 2D goal-based grid-world that shows how the presence of the sub-optimal experts shrinks the feasible reward set.

Examples 3.1,3.2,3.3. Maybe it's "easy to show", but can you please show where these come from?

We thank the reviewer for pointing this out, and we are sorry about this. We agree that the presentation would benefit from formal justifications. Below, the Reviewer can find proofs about these examples. We integrated them in the appendix in a revised version of the paper.

Proof of Example 3.1 Consider two MDPs \ R $\mathcal{M}\_1$ and $\mathcal{M}\_2$ that differs only in the transition function, namely $p_1$ and $p_2$. Suppose that $\pi\_{E\_1}$ and $\pi\_{E\_2}$ are optimal for $\mathcal{M}\_1$ and $\mathcal{M}\_2$ respectively. We are interested in upper-bounding $V\_{\mathcal{M}\_1 \cup r}^{\pi\_{E\_1}}(s) - V\_{\mathcal{M}\_1 \cup r}^{\pi\_{E\_2}}(s)$. Then, for any state $s$, we have that:

$$V\_{\mathcal{M}\_1 \cup r}^{\pi\_{E\_1}}(s) - V\_{\mathcal{M}\_1 \cup r}^{\pi\_{E\_2}}(s) \le V\_{\mathcal{M}\_1 \cup r}^{\pi\_{E\_1}}(s) - V\_{\mathcal{M}\_2 \cup r}^{\pi\_{E\_1}}(s) + V\_{\mathcal{M}\_2 \cup r}^{\pi\_{E\_2}}(s) - V\_{\mathcal{M}\_1 \cup r}^{\pi\_{E\_2}}(s)$$

(we have added and subtracted $V^{\pi\_{E\_1}}\_{\mathcal{M}\_2 \cup r}$, and then we have used $V^{\pi\_{E\_1}}\_{\mathcal{M}\_1 \cup r} \le V^{\pi\_{E\_2}}\_{\mathcal{M}\_2 \cup r}$ due to the optimality of $\pi\_{E\_2}$ in $\mathcal{M}\_2$). Then, focus on $V\_{\mathcal{M}\_1 \cup r}^{\pi\_{E\_1}}(s) - V\_{\mathcal{M}\_2 \cup r}^{\pi\_{E\_1}}(s)$ (an identical reasoning can be applied for the second difference). This can we written as $\gamma \sum\_a \pi\_{E\_1}(a|s) \sum\_{s'} p\_1(s'|s,a) (V^{\pi\_{E\_1}}_{\mathcal{M}\_1}(s') - V^{\pi\_{E\_1}}\_{\mathcal{M}\_2}(s')) + (p\_1(s'|s,a) - p\_2(s'|s,a))V^{\pi\_{E\_1}}\_{\mathcal{M}_2}(s')$

which, in turn, can be further bounded by:

$\frac{\gamma}{1-\gamma} ||p\_1 - p\_2 ||\_1 + \gamma \sum\_a \pi\_{E\_1}(a|s) \sum\_{s'} p\_1(s'|s,a) (V^{\pi\_{E\_1}}\_{\mathcal{M}\_1}(s') - V^{\pi\_{E\_1}}\_{\mathcal{M}\_2}(s'))$

Unrolling the summation to iterate the aforementioned argument, and using the fact that $\sum\_{t=0}^{+\infty} \gamma^t = \frac{1}{1-\gamma}$ concludes the proof.

Proof of Example 3.2 In this proof, we explicit the relationship of the value function $V$ with the discount factor $\gamma$ by writing $V^{\pi, \gamma}\_{\mathcal{M} \cup r}$. Then, we have that

$V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}, \gamma}(s) - V\_{\mathcal{M} \cup r}^{\pi\_{E\_2}, \gamma}(s) \le V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}, \gamma}(s) - V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}, \gamma'}(s) + V\_{\mathcal{M} \cup r}^{\pi\_{E\_2}, \gamma'}(s) - V\_{\mathcal{M} \cup r}^{\pi\_{E\_2}, \gamma}(s)$

(we have added and subtracted $V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}, \gamma'}(s)$, and then we have used $V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}, \gamma'}(s) \le V\_{\mathcal{M} \cup r}^{\pi\_{E\_2}, \gamma'}(s)$ due to the optimality of $\pi\_{E\_2}$ for the discount factor $\gamma'$).

At this point, focus on $V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}, \gamma}(s) - V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}, \gamma'}(s)$. Using the definition of the value function, together with the fact that rewards are bounded in $[0,1]$, we can rewrite this difference as $\mathbb{E}[\sum\_{t=0}^{+\infty} (\gamma^t - {\gamma'}^{t}) r(s\_t, a\_t)] \le \sum\_{t=0}^{+\infty} \gamma^t - {\gamma'}^{t} = \frac{\gamma - \gamma'}{(1-\gamma)(1-\gamma')}$. An identical argument holds for the second difference, thus concluding the proof.

Proof of Example 3.3

By using the definition of value function, we can rewrite $V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}}(s) - V\_{\mathcal{M} \cup r}^{\pi\_{E\_2}}(s)$ as $\sum\_{a} (\pi\_{E\_1}(a|s) - \pi\_{E\_2}(a|s) )r(s,a) + \gamma \sum\_{s'} p(s'|s,a) (V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}}(s') - V\_{\mathcal{M} \cup r}^{\pi\_{E\_2}}(s')))$. At this point, since rewards are bounded in $[0,1]$ and by the policy similarity assumption, we have that the difference in value functions can be upper bounded by $\epsilon + \gamma \sum\_{s'} p(s'|s,a) (V\_{\mathcal{M} \cup r}^{\pi\_{E\_1}}(s') - V\_{\mathcal{M} \cup r}^{\pi\_{E\_2}}(s'))$. Unrolling the summation to iterate the aforementioned argument, and using the fact that $\sum\_{t=0}^{+\infty} \gamma^t = \frac{1}{1-\gamma}$ concludes the proof.

Writing suggestions

We thank the Reviewer for the suggestions. In a revised version, we limit the use of word "Indeed" and we removed the use of "it's easy to see" and we replaced with formal justifications (see point above). On the use of the symbol $\pi$, we replaced the operator $\pi$ with $\bar{\pi}$ to distinguish it from the policy symbol $\pi$.

How can we utilize the feasible reward set in a real-world scenario?

We thank the Reviewer for raising this point. How to make the best use of the feasible reward set to learn a policy in RL is currently an open problem, even for the single-agent IRL formulation of the feasible reward set (see Section 8 in Metelli et al., ICML 2023).

Nevertheless, suppose that the algorithm has terminated, and, consequently, the estimated policies $\\{ \hat{\pi}\_{E\_i} \\}\_{i=1}^{n+1}$ and the empirical model $\hat{P}$ are available to the agent. At this point, given any $V$ and $\zeta$ that satisfies Eq. (4) and (5) for $\\{ \hat{\pi}\_{E\_i} \\}\_{i=1}^{n+1}$ and $\hat{P}$, let us write $\hat{r}\_{v,\zeta}$ for its corresponding reward function.

Now, suppose we are given a function $f: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ that evaluates the quality of a compatible reward function $\hat{r}\_{V, \zeta}$, i.e., $f(\hat{r}\_{V, \zeta})$, so that we are interested in learning a policy for the reward function that maximizes $f$. Then, we can search over the feasible reward set for the function that maximizes $f$. This problem is simply a constrained optimization problem, where the constraints are the ones on $V$ and $\zeta$ specified by the empirical versions Eq. (5) and (6) (i.e., $P$ is replaced with $\hat{P}$ and $\pi_{E_i}$ is replaced with $\hat{\pi}_{E_i}$). Since all these constraints are linear in $V$ and $\zeta$, the complexity of the optimization is entirely dominated by the complexity of evaluating the objective function $f$. If evaluating $f$ is computationally efficient, then, searching for a reward function that maximizes $f$ is computationally efficient.

Once the reward function that maximizes $f$ (or an approximation) is available, we can use it to train the RL agent. Notice that, in this sense, we can appreciate that this approach does not force us to select a criterion $f$ beforehand, and therefore, we might adopt the aforementioned strategy for several criteria (e.g., the max-margin approach of "Algorithms for inverse reinforcement learning", Ng and Russel, ICML 2000) and train several RL agents.

Finally, it has to be remarked that learning a policy in RL is not the only purpose of IRL. Another typical application is the interpretability of the behavior of the expert. In this sense, the feasible reward set approach offers broader perspectives w.r.t. standard IRL methods that adopt specific criteria to select a single reward function.

Can you provide more insights into determining the performance gap of sub-optimal policies?

Determining the performance gap $\xi_i$ for sub-optimal experts is a relevant issue. First of all, in the paper we have provided three scenarios (Examples 3.1-3.3) in which the values of $\xi_i$ can be computed, with no assumption of no knowledge of the (possible) reward function optimized by the expert policy. We remark that $\xi_i$ is to be intended as an upper bound of the degree of sub-optimality of expert $i$ and, for this reason, even a rought estimate (provided that it is an overestimate) is acceptable. Furthermore, the presence of a human domain expert is able to evaluate the sub-optimality of several agents, providing estimates of $\xi_i$, is a more realistic scenario than requesting the human expert to explicitly design a reward function.

Can you experimentally verify if sub-optimal experts can mitigate reward ambiguity?

We thank the Reviewer for raising this point. We have designed an experiment that aims at visualizing the reduction of the feasible reward set. We have considered as environment the forest management scenarios with $10$ states and $2$ actions that is available in the "pymdptoolbox" library. We considered a discount factor $\gamma = 0.9$. We have run policy iteration on this domain to recover a set of expert policies, and we have considered as $\xi_i$ the infinite norm between the value functions of the optimal policy and the sub-optimal ones computed using the true reward function.

To appreciate the reduction in the feasible set that is introduced by the sub-optimal experts, we have plotted the maximum value that $\zeta(s,a)$ can achieve according to the theoretical bound of Eq. (7) (notice, indeed, that this is way easier to visualize rather than an entire set of reward functions). For the sake of visualization, we have flattened the matrix that contained upper bounds on $\zeta$, and the reviewer can find the result in the right figure in the pdf that we attached to the general answer. As the Reviewer can notice, the presence of the sub-optimal experts can significantly limit the value of the advantage function in many state-action pairs (notice that the maximum value for $\zeta$ is given by $1 / (1-\gamma) \approx 10$; this theoretical threshold represents the upper-bound on $\zeta$ that was derived in Metelli et al., 2021 for the single-agent problem).

We have then run our algorithm for $20$ times using $\epsilon = 0.1$ and $\delta = 0.1$, and computed the again the theoretical upper bound on $\zeta(s,a)$. The reviewer can find the empirical value of the upper bounds on $\zeta$ in the left figure. We have reported only the empirical mean, as the $95\%$ confidence intervals are in the order of $1^{-5}$. As one can verify, the results are almost identical to the exact case.

We integrated this result in the appendix in a revised version of our manuscript.

The paper assumes access to a generative model of the experts' policies. However, in practical IRL a finite data set of precollected expert demonstrations is the norm

We thank the reviewer for raising this point. We agree with the reviewer that the generative model represents a limitation. Extending this work to remove the assumption on the generative model and working directly on a dataset of demonstrations is an intriguing avenue for future research. In this sense, one could draw inspiration from the recent paper "Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms", Lazzati et al., 2024, where the authors analyze solution concepts and algorithms for recovering the feasible reward set in the single-agent IRL setting.

Minor points

We thank the Reviewer for these notes.

We have inserted proofs for Example 3.1-3.3 in a revised version of the manuscript and also in this Rebuttal (see reply to Reviewer KsdM).

On Equation (5). Having fixed a sub-optimal expert $i$, Equation (5) represents a set of $S$ inequalities. This is visible in Equation (6) that makes explicit one of such inequalities having fixed $s'$ (the initial state of the occupancy measure). By varying $s'\in \mathcal{S}$, we obstain $S$ inequalities, and for this reason, the right hand side of Equation (5) is an $S$-dimensional vector.

On Equation (10). Yes, thanks for the typo. Equation (10) should be changed to a $\min_{i \in \{2, \dots n \}} \min_{(s,a): \pi_{E_i} > 0} \pi_{E_i}(s,a)$.

As pointed out, we would generally like the suboptimalities to be small and the $\xi$ to be large. However, these may be conflicting goals, given that we also want the suboptimal experts to deviate from $\pi_{E_1}$. Could this problem be mitigated by having experts that are more suboptimal (e.g. a completely uniform expert) but with lower and upper bounds on their suboptimality?

We thank the Reviewer for the interesting question. We agree that these may be conflicting goals, at least when no additional structure is enforced (consider, for example, a kernelized and continuous state-action space which has been discretized; here, taking similar but distinct actions leads to similar effects on the underlying MDP; in this case, the goals are not necessarly conflicting).

Nevertheless, as the Reviewer suggests, we agree that one way to mitigate this problem would be having experts with lower and upper bounds on their sub-optimality. In this case, the lower and upper bounds will delimit the set of reward functions with potentially more information, thus avoiding the "need" for "precise" experts with small sub-optimality gaps.

What if we were to drop the optimal expert ? Can we say anything about the feasible reward set in that setting?

We thank the Reviewer for raising the interesting question. If we drop the optimal expert, we are still be able to make use of this knowledge to reduce the feasible reward set. Consider a set of experts for which we know that $0 \le V^{E_1} - V^{E_i} \le \xi_i$ holds. Then, for each pair $(i,j) \in \{2, \dots, n+1 \}$, simple algebraic manipulations leads to the following inequalities: $V^{E_j} - V^{E_i} \le \xi_i$, which does not depend on the optimal policy $\pi_{E_1}$. As a remark, we note that, by considering only these inequalities (i.e., by neglecting the presence of $\pi_{E_1}$), one can still obtain sufficient conditions for describing the feasible reward set.

As an illustrative example, consider a simple bandit with two sub-optimal experts $i$ and $j$. Then, suppose that $\pi_{E_i}(a_i) = 1$ and $\pi_{E_j}(a_j) = 1$ for some actions $a_i, a_j$ such that $a_i \ne a_j$. Then, the previous set of equations leads to $r(a_j) - r(a_i) \le \xi_i$ and $r(a_i) - r(a_j) \le \xi_j$, thus introducing constraints on the values that the reward functions can assume in these actions.

The main weakness of the setting is that it assumes having access to a generative model for the optimal and sub-optimal experts during sampling and that there is a performance gap between the sub-optimal and optimal experts

We thank the Reviewer for raising this point. Extending this work to remove the assumption on the generative model and working directly on a dataset of demonstrations is an intriguing avenue for future research. In this sense, one could draw inspiration from the recent paper "Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms", Lazzati et al., 2024, where the authors analyze solution concepts and algorithms for recovering the feasible reward set in the single-agent IRL setting. Concerning the assumption of the performance gap, we take the chance to note that our formulation still generalizes existing theoretical works on IRL, which usually assume to have access to possibly multiple optimal experts (see, e.g., "Identifiability and generalizability from multiple experts in inverse reinforcement learning.", Rolland et al., NeurIPS 2022, or additional works that we discuss in Section 5).