Learning Utilities from Demonstrations in Markov Decision Processes

We thank the Reviewer for recognizing the validity of our proposal, specifically of learning a utility with known reward and to use demonstrations from multiple environments to reduce identifiability issues. Below, we answer to the Reviewer's comments and questions.

Is the purpose of including human data only to show that human data is not Markovian? Numerical experiment could have been conducted completely in simulation.

Yes. Since one of the main contributions of the paper is to present the first model of human behavior that complies with non-Markovian policies in MDPs (see Eq. (1)), then, we have included human data to provide some empirical evidence on the claim that human behavior is inherently non-Markovian. This is precisely the goal of Experiment 1.

Did the authors demonstrate improved identifiability with more environments, i.e., larger N? Sorry if I missed it but it was hard to find.

From the theoretical viewpoint, our Proposition 4.5 demonstrates that the feasible set of utilities $\mathcal{U}$ reduces its size as demonstrations from multiple environments are observed, up to the limit in which it contains only the expert's utility $\mathcal{U}=\{U^E\}$. Simply put, a policy in an environment represents a constraint in the set of utilities $\mathfrak{U}$, thus, adding more environments we are adding more constraints, and the feasible set $\mathcal{U}$, i.e., the intersection of these subsets, reduces its size.

From an empirical perspective, as mentioned in Experiment 2, we have observed that, increasing the number of environments $N$, the empirically-best step size reduces, which may be a symptom that the feasible set $\mathcal{U}$ is smaller, and, thus, we have to be more "precise" for spotting it inside the set of all utilities $\mathfrak{U}$. Anyway, note that Theorem 5.2 holds with a choice of step size $\alpha$ that decreases with $N$ (see line 2728), thus, our previous conjecture may be wrong.

Nevertheless, we remark that an increment of $N$ does not necessary improve the identifiability of the expert's utility $U^E$, although it cannot worsen it, and, thus, this complicates the analysis of the relationship between $N$ and the identifiability of $U^E$. Indeed, intuitively, identifying $U^E$ using demonstrations from $N+M$ environments is "easier" than using only $N$ environments as long as the additional $M$ environments provide constraints that do not already appear in the first $N$ environments. For this reason, analyzing how the identifiability of $U^E$ improves as $N$ increases is not immediate from a technical perspective. Thus, we leave it for future works.

This paper is quite difficult to read, perhaps due to a lot of notations. Ultimately the results and algorithms are pretty straightforward. I think the authors could present it in a much easier way.

We agree with the Reviewer that the algorithms and the results in Section 5 could be presented using a simpler notation. However, note that the additional notation is necessary for providing a sketch of the proofs of Theorems 5.1 and 5.2 in the main paper. We will try to adjust this trade-off by moving the notation not strictly necessary to the appendix, in order to improve the clarity and the readability of the paper.

On line 18 in algorithm 2, what does the $\Pi$ symbol mean? Is it a policy or a projection operator?

Yes, $\Pi_{\overline{\underline{\mathfrak{U}}}_L}$ denotes the Euclidean projection onto set $\overline{\underline{\mathfrak{U}}}_L$, as defined on line 083.

We are glad that the Reviewer appreciated the novelty and the significance of the problem setting introduced, and that the Reviewer recognized the solidity of the theoretical results presented. Below, we report answers to the Reviewer's comments.

The authors stress the ability of their approach to induce non-Markovian behavior. The claim on line 409 that this is the first IRL model to induce non-Markovian behavior is too strong. Majumdar et al. (2017) already address IRL with coherent risk measures such as CVaR, which leads to non-Markovian policies (Chow, 2017). Moreover, most risk measures, except for ERM, EVaR, and time-consistent ones [Chow, Theorem 1.3.8], inherently yield non-Markovian policies.

We agree with the Reviewer that the claim on line 409 is imprecise, and we will change it to "... the first IRL model that contemplates non-Markovian policies in MDPs". Indeed, as we explain in Section 7, Majumdar et al. (2017) consider the much simpler "prepare-react model" as environment intead of an MDP.

Also, we note that, even though most risk measures yield non-Markovian policies, there is no IRL algorithm for MDPs in the literature that models the expert's policy as the result of the optimization of a risk measure, and, as such, as non-Markovian. Indeed, as mentioned in Section 7 and explained in Appendix A, works like [1] model the expert's policy as Boltzmann rational, i.e., as stochastic Markovian.

The paper is quite notation-heavy, which can make it difficult to follow. If you can reduce the density of math symbols in the main text, that could significantly improve the overall readability.

We agree with the Reviewer that the main text is notationally dense. We will try to simplify some passages to improve the readability in the final version of the paper, moving the notation not strictly necessary in the main paper to the appendix.

Typos: in line 197, 281, 381: contained into -> contained in

We thank the Reviewer for pointing out, we have fixed them.

When learning from a single environment, Theorem 5.2 basically guarantees that for the recovered utility, the expert is optimal. Is it possible to also say something in terms of Hausdorff distance to the set of feasible utilities?

Answering to this question is not trivial. The reason is that, for the feasible utility set, it is not immediate to find an explicit representation for the feasible utility set $\mathcal{U}$ that permits to construct an estimator $\widehat{\mathcal{U}}$ for which it is simple to carry out a sample complexity analysis.

Consider the sample complexity analysis conducted for the estimation of the feasible reward set [2,3,4,5]. In [2,3], it is proved that each reward $r$ in the feasible reward set $\mathcal{R}$ can be parameterized as a function of the optimal value $V_h$ and advantage $A_h$ functions as:

Thus, using as estimator for $\mathcal{R}$ the set $\widehat{\mathcal{R}}$ where each reward $\widehat{r}\in\widehat{\mathcal{R}}$ can be parametrized as a function of the optimal value $\widehat{V}_h$ and advantage $\widehat{A}_h$ functions in the estimated MDP as:

then it is possible to bound the Hausdorff distance in max norm by the 1-norm of the transition models:

as long as $\widehat{\pi}^E=\pi^E$ with high probability (see also [4,5]). Then, the analysis follows rather directly by applying standard concentration inequalities.

To adapt this analysis to sets of utilities, we require a simple representation of the feasible utility set $\mathcal{U}$ analogous to that in (1). However, it is not immediate to us how to obtain it, since utilities are objects rather different from reward functions. Nevertheless, studying the feasible utility sets and the problem of learning them is an interesting future research direction.

[1] Ratliff, L. J. and Mazumdar, E. Inverse risk-sensitive reinforcement learning.

[2] Metelli, A. M., Ramponi, G., Concetti, A., and Restelli, M. Provably efficient learning of transferable rewards.

[3] Lindner, D., Krause, A., and Ramponi, G. Active exploration for inverse reinforcement learning.

[4] Metelli, A. M., Lazzati, F., and Restelli, M. Towards theoretical understanding of inverse reinforcement learning.

[5] Zhao, L., Wang, M., and Bai, Y. Is inverse reinforcement learning harder than standard reinforcement learning?

We thank the Reviewer for recognizing the novelty of the proposed problem formulation, and the strength of our theoretical contributions on the identifiability problem of utilities. Below, we answer to the Reviewer's comments and questions.

On the comparison with literature.

We thank the Reviewer for the references. We will incorporate a discussion on both ERM-MDPs and CVaR-MDPs in the paper. Although the primary focus of our work is the inverse problem, we agree with the Reviewer that including a discussion on algorithms for solving the forward problem can improve the quality and clarity of the paper.

On the empirical validation.

The ultimate goal of the paper is to introduce a new problem setting, and to characterize its properties and challenges (e.g., identifiability issues). The presentation of CATY-UL and TRACTOR-UL serves the main objective of demonstrating that, from a theoretical viewpoint, the UL problem can be solved efficiently even in the worst case, which is not obvious given the non-Markovianity of the expert's policy. This result paves the way to more practical UL algorithms, whose development would be "risky" in absence of theoretical guarantees of polynomial sample and computational complexity (see Theorems 5.1, 5.2). For these reasons, we believe that, although interesting, an extensive empirical validation of the proposed algorithms that goes beyond the simple tabular settings considered in Section 6 has limited relevance for the scope of this work.

In brief, we stress that, since the paper is the first to consider this problem setting and since it already provides significant contributions, then we conducted only illustrative experiments in the tabular setting. The development of more complex and practical algorithms able to scale should be conducted in future works.

On the notation.

We agree with the Reviewer that part of the notation introduced in Section 2 is rather cumbersome and marginal for conveying the main ideas of the paper. However, it is necessary for providing a sketch of the proofs of Theorems 5.1 and 5.2 in the main paper. We will try to adjust this trade-off by moving the notation not strictly necessary to the appendix, in order to improve the clarity and the readability of the paper.

On the computational complexity.

For the subroutines:

• EXPLORE: time = $\mathcal{O}(N\tau)$; space = $\mathcal{O}(SAHN)$.
• ERD: time = $\mathcal{O}(H\tau^E+H/\epsilon_0)$; space = $\mathcal{O}(H/\epsilon_0)$.
• PLANNING: time = $\mathcal{O}(S^2AH^2/\epsilon_0)$; space = $\mathcal{O}(SAH^2/\epsilon_0)$.
• ROLLOUT: time = $\mathcal{O}(KH)$; space = $\mathcal{O}(K)$.

Thus:

• CATY-UL: time = $\mathcal{O}(N\tau+MN(H\tau^E+S^2AH^2/\epsilon_0))$, where $M$ denotes the number of input utilities to which CATY-UL is applied; space = $\mathcal{O}(SAHN+SAH^2/\epsilon_0)$.
• TRACTOR-UL: time = $\mathcal{O}(N\tau+NH\tau^E+T(NS^2AH^2/\epsilon_0+NKH+Q_{time}))$, where $Q_{time}$ represents the number of iterations of the optimization solver adopted for the Euclidean projection; space = $\mathcal{O}(NH/\epsilon_0+SAH^2/\epsilon_0+K+Q_{space})$, where $Q_{space}$ is the space used for the projection.

Note that these complexities are polynomial in all the quantities of interest $S,A,H$, $N,$ $\frac{1}{\epsilon}$, $\log\frac{1}{\delta},Q_{time},Q_{space}$, and this holds even if we replace $\epsilon_0,\tau^E,\tau,T,K$ with the values that provide the theoretical guarantees in Theorems 5.1, 5.2.

We remark that the assumption made in Theorem 5.2 that the Euclidean projection is exact is made just for simplifying the theoretical analysis, but it is not necessary. If the Reviewer desires details on the proof, we can provide them.

We will add all these considerations to the paper.

On the multi-environment utility identifiability.

This is an interesting point. Intuitively, it is not trivial to compute a minimum number of environments $N\ge\overline{N}$ that suffices for the "practical" identifiability of the expert's utility $U^E$, for two reasons:

• It depends on how much "informative" are the observed $N$ environments. For instance, if the $N$ environments provide similar constraints in the space of utilities $\mathfrak{U}$, then identifying $U^E$ remains difficult.
• Depending on what we want to do with the expert's utility $U^E$ once that we have recovered it, we might be satisfied with less accurate estimates. For instance, if we want to recover $U^E$ for transferring it to a difficult environment, then, intuitively, we need a very good estimate $\widehat{U}\approx U^E$, because the target environment is difficult, and so we expect $N$ to be large; instead, if the goal is to do planning in a simple environment, then we can tolerate $N$ to be small.

For these reasons, analyzing how the identifiability of $U^E$ improves as $N$ increases is not immediate from a technical perspective and we leave it for future works.

We are glad that the Reviewer appreciated the significance of the problem setting considered and the analysis conducted. Below, we report answers to the Reviewer's comments.

On the experiments conducted.

The ultimate goal of the paper is to introduce a new problem setting, and to characterize its properties and challenges (e.g., identifiability issues). The presentation of algorithms CATY-UL and TRACTOR-UL serves the main objective of demonstrating that, from a theoretical viewpoint, the utility learning problem can be solved efficiently even in the worst case, which is not obvious given the non-Markovianity of the expert's policy. This result paves the way to more practical utility learning algorithms, whose development would be "risky" in absence of theoretical guarantees of polynomial sample and computational complexity (e.g., see Theorems 5.1, 5.2). For these reasons, we believe that, although interesting and important in order to comprehensively corroborate the proposed model and algorithms, an extensive empirical validation that goes beyond the simple tabular settings considered in Section 6 has limited relevance for the scope of this work.

In brief, we stress that since the paper is the first to consider this problem setting and since it already provides significant contributions, we conducted only illustrative experiments in the tabular setting. The development of more complex and practical algorithms able to scale should be conducted in future works.

On the participants to the experiments.

The 15 participants are lab members, as mentioned at the beginning of Section 6 (line 399). We will highlight this fact in the paper.

On the absence of baselines.

Concerning Experiment 1, the objective is to understand which model of human behavior is the most appropriate. Since the main novel feature of the model of behavior that we propose in the paper (see Eq. (1)) is the non-Markovianity of the expert's policy, then, in the experiment, we compare with the baseline represented by the Markovian policy.

The goal of Experiment 2 is to test the efficiency of TRACTOR-UL at recovering a utility function under the newly-proposed UL problem setting. Since no IRL algorithm in literature, neither the common ones like [1,2,3] nor the risk-sensitive ones like [4,5,6], aims to learn a utility function of this kind, then comparing the efficiency with which existing (risk-sensitive) IRL algorithms converge to their learning targets with the efficiency with which TRACTOR-UL converges to a utility function would not be much meaningful.

On the dependence on $H$.

We agree with the Reviewer that the dependence on $H^4$ and $\frac{1}{\epsilon^4}$ in the theoretical guarantee of Theorem 5.2, although being polynomial, can be prohibitive in problems with very long horizons for which we require accurate estimates. However, note that this guarantee holds in the worst case and using the discretization approach that, while offering the advantage of simplifying the theoretical analysis of the algorithm, might be less efficient in practice than other methods, e.g., estimating the utility of the expert through function approximation and some fixed set of basis functions. We leave this interesting direction to future works.

On the notation.

We agree with the Reviewer that part of the notation introduced for instance in Section 2 and Section 5 is rather cumbersome and marginal for conveying the main ideas of the paper. However, it is necessary for providing a sketch of the proofs of Theorems 5.1 and 5.2 in the main paper. We will try to adjust this trade-off by moving the notation not strictly necessary to the appendix, in order to improve the clarity and the readability of the paper.

[1] Andrew Y. Ng and Stuart J. Russell. Algorithms for inverse reinforcement learning.

[2] Brian D. Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy

[3] Deepak Ramachandran and Eyal Amir. Bayesian Inverse Reinforcement Learning.

[4] Lillian J. Ratliff and Eric Mazumdar. Inverse risk-sensitive reinforcement learning.

[5] Sumeet Singh, Jonathan Lacotte, Anirudha Majumdar, and Marco Pavone. Risk-sensitive inverse reinforcement learning via semi- and non-parametric methods.

[6] Haoyang Cao, Zhengqi Wu, and Renyuan Xu. Inference of utilities and time preference in sequential decision-making.