Learning Utilities from Demonstrations in Markov Decision Processes

We are glad that the Reviewer appreciated the novelty of the model presented, the significance of the theoretical and empirical results provided, and also acknowledged that the paper is well-written and overall clear. Below, we report answers to the Reviewer's comments.

Weaknesses

Most importantly, I'm not yet convinced that explicitly learning risk-sensitive utility functions is necessary. Playing the devil's advocate here, I'd argue that a reward function is able to capture risk appetite by extending the state space (as noted by the authors themselves in footnote 3). In said footnote, you argue that we shouldn't alter the state representation, because we couldn't transfer the reward function to new environments. This is quite unconvincing in my opinion, because, after all, we get to design the state space (usually), and any similar environments that we would like to transfer the reward function to could also have, say, a feature that refers to the money we currently have in our pocket. I think that it is quite standard to alter a state representation this way (e.g., think about maze environments where the agent has to pick up a key first in order to go through a door). Thus, Example 3.1 may be too simple an example to highlight why we should model some problems as utility learning instead of IRL. I do hope that this prompts the authors to make a stronger case for the necessity of utility learning.

We thank the Reviewer for the important question, that allows us to clarify a crucial point of the paper. Specifically, if we re-model the MDP by including the reward into the state to make the optimal policy Markovian, then we might incur in interpretability and transferability issues. To better explain this, let us make a simple example.

Consider a driving setting, where the state is the location of the car (name of the road and position inside the road), the actions permit to change the current road (only when the car is close to another road, otherwise no effect), and at every stage/timestep the position of the car advances on the current road depending on the amount of traffic in the road, which is random and modelled through the transition model of the environment.

Consider now an expert agent that aims to reach a certain goal location $s_g$ in the minimum time/number of stages possible, and that is risk-averse, in the sense that it prefers roads that always have little traffic, even though they are, on average, slower, to roads that are usually faster but sometimes have peaks of traffic that make them very very slow (since the traffic is random, there is no sequence of roads that is always better than others, but it is a matter of chance).

In our model (Eq. (1)), we can represent the expert through the reward function $r^E$ that is $0$ in the goal location $s_g$, and $-1$ otherwise. In this manner, the faster a trajectory reaches $s_g$, the larger the cumulative reward. Next, we can choose the utility function $U^E$ to be some concave function in order to achieve the risk-aversion property [1], i.e., to make sure that the expert prefers, intuitively, roads with "smaller variance" of traffic. We remark that our model permits to capture the preferences of the expert in a very simple yet expressive manner. In fact, as shown in this example, $r^E$ and $U^E$ can be easily designed, and their meaning is easily interpretable. However, this does not hold if we include past rewards in the state.

In the model with an extended state space, the behavior of the expert is represented through a single reward $\overline{r}^E$ (defined on the expanded state space) instead of the pair reward-utility $r^E,U^E$. The intuition is that, to contain all the information present in $r^E,U^E$, the new reward $\overline{r}^E$ will be "messy". As such, designing it is also more complex. For instance, choosing $\overline{r}^E$ to be $-t$ in the (expanded) state made of the goal location $s_g$ and of $t$ timesteps, and $0$ elsewhere, represents a risk-neutral agent that aims to reach $s_g$ as soon as possible, but it does not capture the risk-aversion of the expert. To make $\overline{r}^E$ model the risk-aversion, we must take it to be a concave function of $-t$, making it more difficult to be interpreted.

Some comments:

• The first three experiments analyze the performance when we increase the size of the state-action space. Note that the number of gradient iterations necessary to achieve a certain level of performance is not affected by an increment of $S,A$, as already shown in our Theorem 5.2. Nevertheless, larger $S,A$ require more execution time, because of the value iteration subroutine, that has a computational complexity that grows with $S,A$.
• The last two experiments analyze what happens when we consider demonstrations in multiple ($N=5$ and $N=20$) environments. We note that, as expected, the number of iterations required to find a utility with small (non)compatibility increases with $N$: after $T=70$ iterations, we have $\overline{\mathcal{C}}(U_T)=0.07$ for $N=1$ (see Section 6), $\overline{\mathcal{C}}(U_T)=0.14$ for $N=5$, $\overline{\mathcal{C}}(U_T)=0.20$ for $N=20$. This result is expected from the theoretical guarantees of Theorem 5.2, and also from the intuition. In addition, we observe that the best learning rate when $N$ increases (we found $\alpha=1$) is much smaller than $\alpha=100$ used for the experiments with $N=1$. Again, this result is expected (we mentioned it in the paper), since now we aim to find a utility that has to satisfy more constraints (more environments), and, thus, there are less utilities with small (non)compatibility. Intuitively, "finding" them is more difficult, and we cannot make large gradient steps as when $N=1$.

We hope that the Reviewer finds these experiments satisfactory; we will include them in the final version of the paper. Please do not hesitate to contact us for any further explanations.

In the experiments, you should include how the participants were recruited (e.g., lab members or others). This may somewhat limit the validity and integrity of the experiments, but this is a fairly minor point of concern to me.

Thank you for pointing out. The participants to the experiments are lab members. As such, they have the competences necessary to understand effectively the questions asked to them. We will add this point to the paper.

Questions

Are there any alternatives to enlarging the state space to compute the optimal policy in RS-MDPs?

As far as we know, there are not other approaches in literature. Moreover, we believe that no alternative can even be devised, for the following, intuitive, reason. [1] have proved that the non-Markovianity of the optimal policy is limited to the cumulative reward up to now. Thus, in the most general case, the optimal policy $\pi^*$ is a function of the current state and stage, and of the amount of reward accumulated so far: $\pi^*: \mathcal{S}\times[H]\times\mathcal{Y}\to\mathcal{A}$, where $\mathcal{Y}$ is the set of possible cumulative reward values (see definition in the paper). Thus, intuitively, since $\pi^*$ has domain $\mathcal{S}\times[H]\times\mathcal{Y}$, then we need to assign a value (action) to all the triples $(s,h,y)$. Since $\mathcal{S}\times\mathcal{Y}$ coincides with the enlarged state space, then in the worst case this approach is necessary.

Right before and in Section 5, you refer to the situation where you get demonstrations in multiple environments as the "setting with multiple demonstrations". This could be interpreted as observing the several trajectories in the same environment (instead of trajectories in different environments). I think it woul be better to consistently refer to this as learning from demonstrations in multiple environments. There is also related work in IRL that has referred to this as such and studied learning from multiple environments: Identifiability and Generalizability from Multiple Experts in IRL, Environment Design for IRL.

We thank the Reviewer for the suggestion. We agree that the expression "learning from demonstrations in multiple environments" is more suitable to the considered problem setting, given the analogies with the mentioned papers. Our simplified expression "setting with multiple demonstrations" can be misleading. We will fix this in the final version.

We thank the Reviewer for recognizing the importance of our results on the partial identifiability of the expert's utility, and for appreciating our theoretical and empirical analysis of the proposed algorithms. Below, we answer to the Reviewer's comments and questions.

Weaknesses

The theorems on identifiability and compatibility of utility function seem to be more like a mathematical game.

We remark that, although we derived them in illustrative problems, our results on the partial identifiability of the expert's utility establish the barriers of the Utility Learning (UL) problem. Specifically, Propositions 4.1-4.3, 4.5, demonstrate that UL cannot be used for predicting, imitating, or "assessing" the behavior of the expert when we are given demonstrations in a single environment. Instead, Proposition 4.6 proves that the availability of demonstrations in multiple environments permits successfully apply UL in applications. We also remark that the criticality of the identifiability issue in the connected IRL problem setting has been highlighted even in the seminal papers [1,2]. Since then, many crucial results on the identifiability properties of the setting have appeared [3,4,5,6,7,8,9,10].

In particular, I cannot think of any practical example for which Proposition 4.6 will hold.

We agree with the Reviewer that, since Proposition 4.6 requires the knowledge of the expert's policy in an infinite amount of different MDPs, then it cannot hold in practice. However, its importance is to show that observing expert demonstrations in more than a single environment permits to reduce the unidentifiability of the expert's utility, i.e., it permits to compute more accurate estimates. Observe that, under additional regularity assumptions, it would be possible to obtain accurate estimates of the expert's utility even with a finite number of environments. Note also that there exist analogous results in IRL, like [3,4,8,9].

Proposition 4.6 basically says that demonstrations in multiple MDP environments have exactly the same utility function. However, I don't think that can be true in general. Utility functions, which represent risk attitudes, will change in different environments, even for the same agent.

We remark that the risk attitude of a person does not change across different environments when the underlying reward function is the same. Consider the following two examples where reward is represented by "life" and "money", respectively.

1. A person who does not drive fast because she is worried for her life (she is very risk-averse with her life), then, reasonably, will not play dangerous sports, like skydiving, for the same reason. Namely, she exhibits the same risk-averse behavior with life in both the environments.
2. A person who loves gambling (risk-lover for money), is less likely to buy optional insurances than a person who hates gambling.

Since the utility function represents the risk attitude of a person, and the risk attitude does not change across different environments, then also the utility function does not change.

We also mention that the problem setting in which demonstrations in multiple MDP environments have exactly the same reward function (a different kind of "utility function") is very common in the IRL literature [3,4,6,7,8,9,10].

For example, the same person might have different risk attitudes when gambling with different amount of money.

We remark that different "risk behaviors" associated with the same person gambling with different amount of money can be indeed represented using the same utility function. This is well-known in choice theory [11,12].

To make a simple example, consider a person who loves making small bets (e.g., <10€) on football matches (i.e., who is risk-lover for small amounts of money), but who would never gamble more than 10€ (i.e., she is risk-averse for larger amounts of money). Clearly, this person has a risk attitude that exhibits love for risking small amounts of money, and aversion for risking larger amounts of money. Nevertheless, she has one risk attitude for money, that is easily captured by a single utility function, that is convex before 10€ and concave afterwards.

If the Reviewer has additional questions or doubts, please feel free to ask.

Also, could you conduct additional experiments varying the number of demonstrations from 1 to N, and report how this affects the method’s performance?

As requested by the Reviewer, we have conducted two additional experiments on simulated data, one with $N=5$ environments, and the other with $N=20$ environments. For each experiment, we have first randomly generated $N$ MDPs. Then, in order to consider reasonable expert's policies that (almost) satisfy the assumption that they are generated by the same utility function, we have computed, in each environment, the optimal policy for the same utility function, that we took to be convex for small returns, and concave for large returns, i.e., it is S-shaped as the most popular (and realistic) utility functions considered in behavioral economics [12]. We have additionally injected some noise on these policies to make them more realistic.

We have executed TRACTOR-UL on these two problem instances for $T=70$ iterations to compare with the performance reported in Section 6 for $N=1$. We have set $\overline{U}_0$ (the initial utility) to be the linear utility, and $K=10000$ and $L=10$ as in the experiments in the paper. In both the simulations, we have used a learning rate of $\alpha=1$, smaller than that used with $N=1$ (this choice is explained in the paper, and is motivated later on). Below we report the truncated (non)compatibility values of the utilities extracted by the algorithm as a function of the number of iterations.

For $N=5$:

For $N=20$:

Some comments:

• The best learning rate found is $\alpha=1$, much smaller than $\alpha=100$ used for the experiments with $N=1$. The reason is that, since now we aim to find a utility that has to satisfy more constraints (i.e., the feasible set is smaller), then there are less utilities with small (non)compatibility. Therefore, intuitively, "finding" them is more difficult, and we cannot make large gradient steps as when $N=1$. Note that we already mention this fact in the paper.
• The number of iterations required to find a utility with small (non)compatibility increases with $N$, as expected. After $T=70$ iterations, we have $\overline{\mathcal{C}}(U_T)=0.07$ for $N=1$ (see Experiment 2), $\overline{\mathcal{C}}(U_T)=0.14$ for $N=5$, $\overline{\mathcal{C}}(U_T)=0.20$ for $N=20$. This result is expected from the theoretical guarantees of Theorem 5.2, and also from the intuition.

We will include these results in the final version of the paper. If the Reviewer desires additional details or insights on these experiments, please feel free to ask.

We are glad that the Reviewer appreciated the significance of the considered problem setting, as a powerful extension of IRL when interacting with risk-sensitive agents. Below, we report answers to the Reviewer's comments.

Weaknesses

While the paper extends utility-based approaches to MDPs, the core contributions, such as incorporating risk attitudes in utility functions and the algorithms for UL, rely heavily on prior work in IRL and risk-sensitive models. This might limit the novelty of the proposed approach. Maybe highlight the technical novelty in main text can help.

We remark that the paper brings several novel contributions that do not simply rely on prior work in IRL. We summarize them in the following:

1. We are the first researchers that recognize the importance of non-Markovian policies in modelling the behavior of (human) agents in presence of stochasticity/risk in MDPs for inverse problems. We provide an intuitive justification in Example 3.1 and a proof-of-concept empirical demonstration in Experiment 1 (see Section 6), where we show that, in a toy MDP, the majority of the participants to the study exhibit a non-Markovian behavior.
2. We present the first model of (human) behavior in MDPs that complies with non-Markovian policies (see Eq. (1)), and we show its superior empirical validity (in a small-scale study) over "Markovian" models in Section 6, Experiment 1. No author in the IRL literature has analyzed either this or another model compliant with non-Markovian policies. Indeed, most of the authors focus on a Boltzmann rationality model [1,2], that considers Markovian policies. In addition, we remark that even Eq. (1) in itself represents a novel contribution as a formulation of the inverse problem. In fact, we use it for modelling the behavior of (boundedly rational) agents (inverse problem), while works like [3,4] adopt it for constructing rational agents (control problem), i.e., for prescribing how an "intelligent" agent should behave in face of stochasticity/risk. The difference is subtle but clear, because it leads to two very different problem settings and algorithmic solutions.
3. We prove the first results that characterize the properties of this original setting when it comes to applications like predicting, imitating, or "assessing" behavior (see Propositions 4.1-4.3, 4.5 and 4.6). Note that these results, as well as their proofs, are novel, and they demonstrate an interesting non-trivial connection with IRL.
4. We propose to extend two IRL algorithms because of the connection with IRL proved in Section 4. However, the extension demands technical effort to integrate algorithmic solutions from distributional RL [5], risk-sensitive control [4], and IRL [6,7], which are needed to face the challenges highlighted in Section 5.1. Inter alia, we refine the analysis in [4] using the Bernstein's inequality to improve the sample complexity rate.
5. We provide a proof-of-concept empirical analysis of the proposed algorithms and model in a toy environment with real-world data.

We will make the contributions clearer in the paper.

The assumptions made to guarantee compatibility under finite data might not hold in more complex settings. I hope the author can provide comprehensive discussion on this issue and some intuition on possible relaxation.

We are unsure about which assumptions the Reviewer is referring to. Anyway, as mentioned also in Section 6, when the horizon $H$ becomes very large, assuming that the observed human expert plays an optimal risk-sensitive policy $\pi^E$, i.e., a policy that satisfies Eq. (1) exactly, might be too demanding. Indeed, due to bounded rationality, people are often not able to "look too many steps into the future" [8], and, thus, they may demonstrate a suboptimal policy. For this reason, we have left to future works (see lines 531-532) to analyze what are the maximum values of the horizon $H$ that make our model realistic. Nevertheless, we remark that the optimality assumption is standard in IRL for all the values of the horizon. E.g., [9] assumes the expert to be optimal in an MDP, while [10] assumes the expert to be optimal in an entropy-regularized MDP. Analogously, in this paper, we assume the expert to be optimal in a risk-sensitive MDP.

We are glad that the Reviewer found the problem setting both interesting and important for the IRL community, and also that the Reviewer appreciated the analysis of the partial identifiability of the expert's utility. We provide detailed replies to their questions/comments below.

Weaknesses:

I felt the notation used in this paper might be unnecessarily complicated, which makes it more difficult to read. The paper starting from section 4 could also be more organized.

We agree with the Reviewer that the mathematical notation adopted might appear rather cumbersome and complicated at first sight. However, we remark that it is necessary to avoid losing formality or even clarity. Every symbol introduced in the main paper is necessary to convey some important concept. An intuitive justification for the "strong" notation is that we have to integrate three different formalisms: IRL, risk-sensitive RL, and distributional RL [1].

If the Reviewer has any suggestions for improving the organization of the paper from Section 4 on, we would greatly appreciate your feedback.

I did not understand why the authors require a "deterministic reward function" (line 97), does this exclude any settings where the reward has noise? This seems to directly contradict the motivating example the authors present in Example 3.1 where the reward is noisy.

We remark that Example 3.1 does not require a noisy/stochastic reward function. Indeed, the stochasticity of the transition model suffices to obtain the lotteries over returns described in the example, even with a deterministic reward function. Simply, add two next states, one with a deterministic reward of $0$€ and the other with $200$€, after playing $a_{\text{risky}}$, and make them reachable with probability $1/2$ from it (i.e., make the transition model stochastic).

We have decided to avoid considering stochastic rewards for the sake of simplicity, since it would complicate the notation further without adding much value to the paper. Indeed, observe that extending the results of the paper and also the algorithms to the setting with a stochastic reward function is trivial. In particular, the proofs of Propositions 4.1-4.3, 4.5, 4.6, would still hold, and algorithms CATY-UL and TRACTOR-UL can be easily extended to such setting by adding a line of code for computing the empirical estimate (i.e., sample mean) of the reward function at each state-action pair of the space, and then by replacing the current usage of the deterministic reward value with such estimate. Next, the proofs of Theorems 5.1 and 5.2 could be adjusted by simply adding a term that quantifies the estimation error of the stochastic reward, and then by bounding it using the Hoeffding's inequality.

I was not convinced of the practical application of this problem framing and approach. When would one have access to agent demonstrations in multiple MDP environments, for each agent, in a practical application?

In literature, there is plenty of papers that analyze the setting in which an agent provides demonstrations of behavior in multiple environments. Just to mention a few: [2,3,4,5,6,7,8]. To give some toy examples, you can think of an expert agent who demonstrates the task of driving safely on multiple cars (that have different dynamics), or on multiple roads (each road with its own traffic distribution), or a table tennis player that demonstrates how to play against multiple adversaries.