Learning Utilities from Demonstrations in Markov Decision Processes
Authors: Filippo Lazzati
Alberto Maria Metelli
Venue: ICML 2025 poster (2025)
Keywords: Inverse Reinforcement Learning
Risk
Imitation Learning
Theory
Primary area: reinforcement_learning->inverse
TL;DR: We study a variant of IRL where we aim to learn the risk attitude of an agent from non-Markovian demonstrations of behavior.

Abstract: Although it is well-known that humans commonly engage in *risk-sensitive* behaviors in the presence of stochasticity, most Inverse Reinforcement Learning (IRL) models assume a *risk-neutral* agent. As such, beyond $(i)$ introducing model misspecification, $(ii)$ they do not permit direct inference of the risk attitude of the observed agent, which can be useful in many applications. In this paper, we propose a novel model of behavior to cope with these issues. By allowing for risk sensitivity, our model alleviates $(i)$, and by explicitly representing risk attitudes through (learnable) *utility* functions, it solves $(ii)$. Then, we characterize the partial identifiability of an agent’s utility under the new model and note that demonstrations from multiple environments mitigate the problem. We devise two provably-efficient algorithms for learning utilities in a finite-data regime, and we conclude with some proof-of-concept experiments to validate *both* our model and our algorithms.

Learning Utilities from Demonstrations in Markov Decision Processes
Filippo Lazzati
Alberto Maria Metelli
vides the most popular and powerful models of the behav- ior of the observed agent, named "expert". IRL models Although it is well-known that humans com- monly engage in risk-sensitive behaviors in the presence of stochasticity, most Inverse Rein- forcement Learning (IRL) models assume risk- neutral agent. As such, beyond (i) introducing model misspecification, (ii) they do not permit direct inference of the risk attitude of the ob- served agent, which can be useful in many ap- plications. In this paper, we propose a novel model of behavior to cope with these issues. By allowing for risk sensitivity, our model allevi- ates (i), and by explicitly representing risk at- titudes through (learnable) utility functions, it solves (ii). Then, we characterize the partial identifiability of an agent's 's utility under the new model and note that demonstrations from multi- ple environments mitigate the problem. We de- vise two provably-effciient algorithms for learn- ing utilities in a finite-data regime, and we con- clude with some proof-of-comee conccptept experiments to validate both our model and our algorithms.
Abstract
assume the existence of a reward function that rationalizes the expert's behavior and differ from each other based on the specific assumption of how the expert behaves based on the given reward. For instance, Ng & Russell (2000) considers the expert as playing an optimal policy, Poiani et al. (2024) considers an e-optimal policy, Malik et al. (2021) considers optimal policy satisfying some con- straints, Ziebart (2010); Fu et al. (2017) assume that the ex- pert plays actions proportionally to their (soft) Q-functions and Ramachandran & Amir (2007) assumes this probabil- ity to depend on the optimal advantage function.
These IRL models represent the expert as risk-neutral agent, i.e., an agent interested in maximizing the expected return. However, there many scenarios in which ratio- nal agents and humans adopt risk-sensitive strategies in the presence of stochasticity, like finance (Föllmer & Schied, 2016), revenue management (Barz, 2007), driving (Bern- hard et al., 2019), and many other choice problems (Kah- neman & Tversky, 1979; Kreps, 1988). In these settings, agents are not only interested in the expected return, but in its full distribution (Bellemare et al., 2023). Thus, IRL models incur in misspecification, that can crucially affect the descriptive, predictive, and normative power of the in- ferred reward function (Skalse & Abate, 2024).
1. Introduction
The ultimate goal of Artificial Intelligence (AI) is to con- struct artificial rational autonomous agents (Russell & Norvig, 2010). Such agents will interact with each other and with human beings to achieve the tasks that we assign to them. In this vision, crucial feature is being able to cor- rectly model the observed behavior of other agents. This allows variety of applications: descriptive, to understand
In this context, in addition to misspecification, another is- sue of IRL models is that they do not explicitly represent the risk attitude of the expert, which is only indirectly cap- tured by the reward function. We desire two different rep- resentations for the task of the expert (through reward) and for its risk artitude (e.g., through a utility function), analogously to what is done in Inverse Constrained Rein- forcement Learning (ICRL) (Malik et al., 2021). Here, the behavior of the expert is described by two parameters, re- ward for modelling the task, and a cost for modelling the constraints. In this way, the reward is more easily inter- pretable since it does not have to capture both the task and the constraints, and, also, we can use the learned cost for performing new tasks safely (Kim et al., 2023). For these reasons, we were able to directly learn the risk attitude of the expert separately from its reward function, then we could more easily understand its intent and anticipate its choices in new, unseen, scenarios (Kreps, 1988).
the intent of the observed agent (Russell, 1998). predictive, to anticipate the behavior of the observed agent (potentially in new scenarios) (Arora & Doshi, 2021), and normative, to imitate the observed agent because they are behaving in the "right way" (Osa et al., 2018).
Nowadays, Inverse Reinforcement Learning (IRL) pro-
'Politecnico Milano, Milan, Italy. Correspondence to: Fil- ippo Lazzati callipo.lazzati pol
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning Utilities from Demonstrations in MDPs
Contributions. In this paper, we introduce new risk- sensitive model of behavior that encodes the risk attitude of an agent with a utility function. Thanks to this model, we will show that it is possible to overcome the limitations mentioned above. Our main contributions are:
g(w) == En (Sw, ag)). With abuse of notation, we denote by IP p.r,- the probability distribution over trajec- tories of any length induced by in M (we omit so for simplicity), and by Ep.r,- the expectation w.r.t P P....-- We define the return distribution 1pp-r E A [0.H) of policy x as opp-ri = -Eeel: g(w)=y - p.r,, (w) for all y E [00 H... The set of possible returns at h E [ + 1] is 9h :- {y [0, h - |] 3E E 3T : g(w) = y A p. (w) > 0}, and g = git We remark that g% has finite car- dinality for all h. The performance of policy π is given by J (p, == Ep.c E Th rh(S,; an)], and note that J (p, -G--p---G) We define the optimal perfor- mance (p,r) == max, (T r),, and the optimal pol- icy as x* arg max, J (p,r).
We present a new simple yet powerful model of behavior in Markov Decision Processes (MDPs) that rationalizes non-Markovian demonstrations (Section 3).
We formulate Utility Learning (UI.) as the problem of in- ferring the risk attitude of an agent under the new model of behavior, we characterise the partial identifiability of its utility, and we show that demonstrations in multiple environments alleviate the issue (Section 4).
We introduce CATY-UL and TRACTOR-UL, two novel algorithms for solving the UL problem with finite data in a provably-efficien manner (Section 5).
Risk-Sensitive Markov Decision Processes (RS- MDPs). A Risk-Sensitive Markov Decision Process (RS- MDP) (Wu & Xu, 2023) is pair Mr == (M, U), where
We conclude with proof-of-concept experiments that serve as an empirical validation of both the proposed model and the presented algorithms. (Section 6).
M = (S. H, Su. p. r) is an MDP, and U 1 is a utility function in set 1 == {U" [0, H] - [0, ((()
The proof' of all results are reported in Appendix C-E.
0, O,U"(H) = H ^ U' is strictly-increasing and continuous). Differently from Wu & Xu (2023), w.l.o.g.. our utilities satisfy U(H) = H to settle the scale. The interaction with My is the same as with M, and the notation described earlier still applies, except for the perfor- mance of policies. The performance of policy æ is (=(Upp,r) = [ [U( J ("; Banapin [U] We define the optimal performance as J+(U:P,r) == max, J P=; r),,, the optimal policy as T* E arg max, (U. and the set of optimal policies for My as (U).
2. Preliminaries
The main paper's notation is below. Additional notation for the supplemental is in Appendix B.
(s an))], and note that
Notation. For any N E N, we write [N] =- (1..... "i....,,y:
Given set X. we denote by A the probability simplex on
X. Given compact X c Rdd y E Rd, we define IIx (v) arg min ge |Vv z=l2- A real-valued function f : R - IR is L-Lipschitz if, for all æ, y E R. we have [f(z) - f(vl < L|x-- - y)- ʃ is increasing if, for all x < E IR, it holds f(z) < fyy). and it is prictly-increasingg if f(x) < fly) The probability distribution that puts all its mass on 2 e IR denoted by 6- and is called the Dirac delta. We represent distributions on finite support mixtures of Dirac deltas.
Enlarged state space approach. In MDPs, there al- ways exists a Markovian optimal policy (Puterman, 1994), but in RS-MDPs this does not hold. The enlarged state space approach (Wu & Xu, 2023) is method, proposed by Bäuerle & Rieder (2014), to compute an optimal policy in RS-MDP. Given RS-MDP My= (S, H, SO,,,, we construct the enlarged state space MDP e[My] = (S', ,A, A,, (so. 0), p. with a different state space S' S x g at every h.! For every h [M]] and as, Gh AA, the reward function is Vn (s, y. a)= = UUy+UU(((ssss as) a) (h= = H}, while the dynamies p assigns to the next state (s',g'))8 G the probabil- ity: (s(s', v/)s,,.a)===p (s)==ssss|ss 1)y = yy (s. a)). In words, the state space is enlarged with a component that keeps track of the cumulative reward in the original RS- MDP, and the reward r, bounded in [0. H]. provides the utility of the accumulated reward the end of the episode. A Markovian policy va { for E[Mou] is a se- quence of mappings th S x 9% A. Being MDP,
Markoy Decision Processes (MDPs). A tabular episodic Markov Decision Process (MDP) (Puterman, 1994) is a tu- ple M = A, H, 80, P, r), where S and A are the finite state (S == {S] and action (A == [Al) spaces, H/ is the time horizon, Su S is the initial state, p ::5. S x A x [H] - A is the transition model, and r S x X [+] - [0, 1] is the deterministic reward function. The interaction of an agent with M generates trajectories. Let S2 := (S x A)"~1 x S be the set of state-action trajectories of length h for all e [H + 1]. and Ω == Q4+1- A deterministic non- Markovian policy π = (TT)ee[M) is a sequence of fune- tions Th : Qr - A that, given the history up to stage h, i.c., w (s1,a)..... ai....,. Sh-1, 1h-1, sp)) E lh. prescribes an action. A Markovian policy quence of functions Ty S A that depend on the cur- rent state only. We use g bhe(2....H+.) S2 [0, H] to denote the return of a (partial) trajectory w E Ωr. i.e.,
(Ta)ne[r) is se-
AAttaall, Bäuerle & Rieder (2014) use state space S x Rgo, while Wu & Xu (2023) use S x [h- 1h1
1] for all h E [H]. Instead, we consider sets S (9 }., to capture the minimal size required.
2

---

Learning Utilities from Demonstrations in MDPs
d,, 0E
0.5
81
150C
Orinky r = 0E
start
80
= 0.5
82
0E
Ovate F DE
02, r = 1000E
83
500
Figure 1. The MDP considered in Example 3.1.
we adopt for e[Mu] the same notation presented earlier for MDPs, by replacing p,r, x with p, p. Let a be the optimal Markovian policy for e[Mc]. Then, Theo- rem 3.1 of Bäuerle & Rieder (2014) shows that the (non- Markovian) policy x², defined for all h e (2...., ....., H) and well, as o. (w) = (sk. Ewe[h-1j Tw (sw,,r))) and (f()) u (s),)), is optimal for My.
In short, demonstrations of behavior from risk-sensitive agents in MDPs are likely to be collected by non- Markovian policies, whose dependency on the past history is restricted to the amount of reward collected so far. How- ever, none of the existing IRL. models of behavior (see Sec- tions I and 7) contemplate non Markovian policies, and, thus, they result in misspecification.
Inverse Reinforcement Learning (IRL). In IRL we are given demonstrations of behavior from the expert's policy and the goal is to recover the reward of the expert _ (Russell, 1998). As explained in Section a model of be- havior describes how the expert's policy TF is generated from E A model suffers from partial identifiabiliyy if the knowledge of Th does not permit to recover F (almost) uniquely (Cao et al., 2021; Metelli et al., 2021).
For these reasons, we introduce new model of behavior that contemplates non-Markovian policies. Given demon- strations from the expert's policy T= in an environment (S, A, HI so. p), we assume the existence of a reward func- tion 5 and a utility function U E il such that:
75, and
x eargmaaxEppp p.r"
UE
[ r R (9n())))))) (1)
Miscellaneous. For L > O, we write Ht == {U e 11 U is L-Lipschitz). For any finite set X' = [0. H] we define 1 x = [UE (3 V=zx:U(x)==U( and _ = IU E x BB E Me, VEE U(x) = (x)).
i.e., we model the expert as an optimal agent in RS-MDP. The reward E aims to capture the task of the expert, while the utility U represents its risk attitude. Intuitively, if p deterministic, then the trajectories with the largest returns under B are preferred. However, in presence of stochas- ticity, the utility E associates weights to the returns of the trajectories to represent their true "values" for the ex- pert. If U is linear, then arg max, ( =")" = arg max, (p, rF) and the expert values each trajectory by its return under T i.e. it is risk-neutral. However, if U is convex (resp. concave), then the expert amplifies (resp. attenuates) the desirability of high-return trajecto- ries, so that it will accept even more (resp. less) variance to play them. In this case, U represents risk-seeking (resp. risk-averse) expert (Kreps, 1988; Bäuerle & Rieder, 2014).
We will denote by My some RS-MDPs with U T..
3. A New Model of Behavior
We aim to devise realistic model of behavior for humans and rational agents in MDPs that complies with their sensi- tivity to risk. In fact, due to the stochasticity of the environ- ment, they are likely to behave in a risk-sensitive manner. Our insight is that risk-sensitivity in MDPs gives rise to non-Markovian policies for both rational agents (see Belle- mare et al. (2023)) and humans:
There are many arguments that support this model:
Example 3.1. In the MDP of Fig. 1, we expect most people to decide what action to play in state s depending on the amount of reward earned so far, since, intuitively, it makes more sense take the risky action arisky, that sometimes gives a large return (150E) but sometimes gives nothing (OE), when we are guaranteed to have at least 1000 in our wallet (i.e., we have reached from 02), while it may be better to take the safe action aufe, that gives 50 for sure, if we reached s with no reward (ie., from a1). This kind of behavior is known as "decreasing" " risk-aversion. (Prat,, 1964; Kreps, 1988; Wakker, 2010).
1. it generalizes the IRL model of Ng & Russell (2000), that we get if the expert is risk-neutral (UE is linear);
2. it is justified by the famous expected utility theory (von Neumann & Morgenstern 1947), as can interpret each policy π as a choice that induces a lottery ppr" a over the set of prizes (i.e., returns) g
'Re-modelling the MDP including the sum of the past rewards into the state would make the demonstrated policy Markovian, but, as explained in Appendix C.I, it would create various issues like state space with a size exponential the horizon.
3

---

Learning Utilities from Demonstrations in MDPs
3. it contemplates the existence of non-Markovian policies that depend only on the cumulative reward so far (see Bäuerle& & Rieder (2014));
Eq. (1) in M for some unknown U the goal of Utility Learning (UL.) is to find UE..
Does the knowledge of π E and M suffice to uniquely iden- tity U Analogously to IRL (Cao et al., 2021) and ICRL (Kim et al., 2023), the answer is negative, as shown in the following example (details in Appendix D).
4. the corresponding planning problem enjoys practical tractability (Wu & Xu, 2023);
5. U can be learned efficiently, as we show in Section 5, If U is linear, Eq. (1) ad- mits a Markovian optimal policy (Puterman, 1994). Oth- erwise, the more U deviates from linearity, the more non- Markovian policies may outperform Markovian policies:
Some considerations.
Example 4.1. Consider the MDP M in Fig. 2 (left), where (0,00))0000.)) Let the expert's 's pol-
H = (1) icy _ prescribe a1 in 8o. Then, all the utility functions Ue 1l that take on values in the blue region of Fig. 2 (mid- dle) for returns 1,G 1.5, make xB optimal in My-
Proposition 3.1. There exists a RS-MDP in which the dif- ference between the optimal performance and the perfor- mance of the best Markovian policy is 0.5.
Simply put, in UI., the only information available on the unknown utility UE is that it belongs to Il and it makes n E an optimal policy in the corresponding RS-MDP. Since Example 4.1 shows that, in general, there is a set of utili- ties U E Il satisfying this condition, we realize that U is partially identifiable. Analogously to Metelli et al. (2021; 2023), we call such set the feasible set of utilities "compat- ible" with Th in M:
Next, note that, in absence of stochasticity, U plays no role, and Eq. (1) traces back to risk-neutral behavior, as desired:
then Proposition 3.2. If P is deterministic, p, ()) = arg max, 7 J (T
arg max, B ip,
We remark that, by complying with non-Markovian poli- cies, our model of behavior suffers from less misspecifica- tion than common IRL models. Moreover, by using U., it permits to learn a succinet and transferrable representation of the risk attitude of the expert, as we shall see later.
Up = E EI J
(2)
Applications. If we knew the risk attitude of the expert, i.e., its utility U in our model, then we could use it for applications like (i) predicting the behavior of the expert in a new environment, (fi) imitating the expert, or (fii) as- sessing how valuable certain behavior is from the view- point of the expert. UL represents an appealing problem setting for learning U from demonstrations of behavior. However, due to partial identifiability, no learning algo- rithm can recover UE, but, at best, it can find an arbi- trary utility in the feasible set Mp.no... Is this ambiguity tolerated by the applications (i), (ii), and (iii) above? In other words, we are interested in understanding whether all the utilities contained into Upr can be used in place of the true U without incurring in large errors.* 4 Unfor- tunately, the following propositions answer negatively for all (i), (ii). and (tit). Nevertheless, Proposition 4.5 shows that the availability of expert demonstrations from multiple environments is a possible mitigation for the issue.
4. Utility Learning
In this and in the following sections, we focus on the prob- lem of learning the utility U of the expert under the as- sumption that behaves as in Eq. (1). Here, we assume that the expert's ss policy x and the dynamics 8o. P are known, while in Section 5 we will estimate them from finite data.
Problem definition and partial identifiability. Given demonstrations collected by a policy x satisfying Eq. (I), three different learning problems arise:
1. given __ learn U.:,
2. given E learn E 3. learn both E and U.E.
Problem 3 is the most interesting and challenging, because makes the least assumptions, while Problem 2, i.e IRL, has been extensively studied in literature when U is lin- ear (Ng& & Russell, 2000). In this paper, in analogy to ICRL (Malik et al., 2021) where the goal is to learn the constraints when E is known, we focus on Problem 1 because it has relevant applications per se (see later in this section) and because represents a significant step toward solving Prob- lem 3. Thus, we will consider F to be given and denote it with r for simplicity. Let us formalize Problem 1:
Let us begin with (t). We say that utility U permits to pre- dict the behavior of an agent with utility U in a new MDP M' if U and F induce in M' the same optimal policies. The next two propositions show that if the transition model or the reward function of M' differ from those of the orig- inal MDP M, then there are utilities in the feasible set that get wrong in predicting the behavior of the agent with UE:
Proposition 4.1. There exist two MDPs M (S, A, H. 80, P. r), M' = (S, H. s/ r), with p + pl,
Definition 4.1 (Utility Learning (UL)). Let M = (S. A, H. So. p. be an MDP and Th a (potentially non- Markovian) policy. Under the assumption that T satisfies
'In Appendix D we provide more explicit expression. *Skalse al. (2023) conduct an analogous study for IRI..
4

---

Learning Utilities from Demonstrations in MDPs
((1.5)
0
r-0
0
0.4
41
0.5
005
80
02
0.8
0
((L)
0
G
83
2
0.5
15
Figure 2. (Left) MDP of Example 4.1. (Middle) its feasible set with sample utility U", (Right) plot of U' with linear interpolation.
for which there exist a policy _ and a pair of utilities U1.U2e E a such that I1 (Uii) (U2)) O. Proposition 4.2. There exist two MDPs M = (S. A. H, Su. p.r), M' A,, H.s. So. p.).), with r # r'.
is done in IRL (Amin & Singh, 2016; Cao al., 2021) and ICRL (Kim et al., 2023). Formally, extend the UL problem of Definition 4.1 to set of MDPs {M'), with M = (S" H, s r')) and policies { by assuming that there exists a single utility U for which Eq. (I) is satisfied for all i, i... such that T is opti- mal for My for all In this extended problem setting, the feasible set will be the intersection of all the feasible sets xx,. The following result proves that demon- strations in multiple environments is possible solution to the partial identifiability problem.
for which there exist a policy TE and a pair of utilities U1.U2 e a such that IT* (U)) IT; (U2) 0.
Consider now (it). We say that a utility U permits to im- itate the behavior of an agent with utility U if optimiz- ing U provides policies with a large expected utility w.r.t. U.E The reason behind this definition that, differently from IRL, we wish to imitate also the risk attitude of the observed agent. However, UL does not always allow to perform meaningful imitations:
Proposition 4.5. Let S,A,H be any state space, action space, and horizon, satisfying 2 22, and let UE be any utlity. If. for any possible dynamics so.P and reward т, we are given the set of all the deter- ministic optimal policies of the corresponding RS-MDP then we can uniquely identify UE.
Proposition 4.3. There exists an MDP M (S. A, H, So. p.r) and a policy TE for which there are utilities U1,U2 E Uprrr such that, for any e > O smaller than some universal constant, there exists policy ne such that (+UUp, J= = and
(UU::, - J= > 1.
5. Online UL with Generative Model
Concerning (iéi), we say that U and U assess behavior in a similar way if, given any policy, they provide close values of performance. The intuition is that the expert values policies based on their alignment with its risk at- titude E w.r.t. its task r. Formally, we want U such that J" (U:p.r) is small (Zhao et al., 2024). Nonetheless, not all the utilities in the feasible set are close to each other w.r.t. dall
In this section, we present two provably-efficient algo- rithms for solving the UL problem in a finite-data regime.
5.1. Problem Setting
dill (UE, (UU,U)== max [U' pp.
We consider a finite-data version of the UL prob- lem with demonstrations in multiple environments pre- sented in Section 4. We let (M*) with M (S) A', H, s p', r²)). be the N MDPs with shared hori- zon H in which an expert with utility U e l provides demonstrations of behavior. Specifically, for each MDP M' the expert provides us with a batch dataset D {(5] az sg...., S/ a/n s 1) of Eii trajecto- ries collected by executing a policy E. which is opti- mal for the RS- RS-MDP My Morcover, for every M', we let St ,', HI, sb, r' be known, and we consider access to generative sampling model (Azar et al., 2013) for the transition model p', which allows
Proposition 4.4. There exists an MDP M (S. A, H, So. p,r) and a policy TE for which there exists a pair of utilities U1, U2 E Up such that gull (U1,
1.
Propositions 4.1-4.4 tell that demonstrations of behay- ior in single MDP do not provide enough information on UE for applications (i), (ii). and (itz).5 Thus, we might hope that expert demonstrations in multiple environ- ments can help in mitigating this issue, similarly to what
collect sample s' p (-1s,a) from any triple s, a, h at our choice. In
Actuallyy for (ii) only, we can try to learn T. directly without passing through S. as behavioral cloning (Osa et al., 2018).
Forr simplicity, we let H be shared.
5

---

Learning Utilities from Demonstrations in MDPs
short, we assume access offline data for the expert and to online data for the environments, is common in the IRL. literature (Ho& & Ermon, 2016).
Algorithm 1 CATY-UL
Input: data (D J. threshold A, utility U, discrctization ea, dy-
namies {0"):
// Discretis ize U:
Due to partial identifiability, the feasible set N. M. Ti. might contain multiple utilities. Thus, we will develop two different algorithms, one that aims to classify utilities as
U(y) U()) for all y yey 2 for i = 1, 1,2,..., .N do
// Estimate J (U:p',
inside or outside the feasible set n "p''""r........ (CATY-UL, Section 5.3), and the other that aims to compute single utility contained into it (TRACTOR-UL, Section 5.4). In- tuitively, CATY-UL and TRACTOR-UL together permit to fully characterize the feasible set, by, respectively, learning a classification boundary and representative item. Never- theless, note that, because of finite data, we will be able to provide guarantees only for a relaxation of the feasible set Us 2 n. M.ipirri,.. for some A 0:
3
1 R < ERD(D! .r)
JEi(U)) - Eeey of (o)(())
1/ Estimate J (UU:''rr"
(U), + PLANNI BAAANIIGGU,,,,
5
// Estimate Cp,, (UU) - (U) -U)) (U) end
class
True if Eialn] (U) A else False
Return class
us = U E Σ B. R.I (U) [N[
& 4).
(3)
explode even for small H. Thus, we adopt a categori- cal representation for return distributions (Bellemare et al., 2023), that, roughly speaking, aims to approximate a dis- tribution [o. H] with distribution on y'= H. For- mally, given any Me A [0 with finite support, its cate- gorical representation (roje(1) is the distribution in Q:= {ge {gE [4] Exetq 4 Φy (vj are the items of y) obtained through the categorical projection operator Projc (Rowland et al., 2018), reported in Eq. (8)-(9) in Appendix B.
where Cyi, (U) quantifies the (non)compatibility of utility U with demonstrations from n in M¹ (Lazzati et al., 2024a; 2025):
a == J=U: J (U:p',r)
(4)
Intuitively, Ua enlarges the feasible set by accepting utili- ties that make the policies x at most A-suboptimal. Note
that, for A = 0, we have UA = n Up sf..
Optimal policies in RS-MDPs. To compute an optimal policy in RS-MDP My with dynamics p and reward r, the enlarged state space approach of Bäuerle & Rieder (2014) presented in Section 2 requires the computation of an optimal policy in the MDP e[Mu]. whose state space is S x G.."" Yh. Unfortunately, we suffer again from an expo- nential dependence on the horizon 1 (o(S") causes any exact representation of the state space and of the optimal policy of MDP E[Mu] to explode. To avoid this issue, we adopt the discretization approach of Wu & Xu (2023), which, in short, amounts to approximate sets Gh." with 3% by simply replacing reward r with the dis- cretized version F, defined as: Fr, a) == Ig[ra (s, a)l for all 8, a, h. Crucially, since Fn (8. a) E R, then the sum of h rewards belongs to V4+1- In this manner, the sets of partial returns satisfy g S Yn S y for all h. thus, the state space of the enlarged MDP has now a cardinality at most Sd & (SHH/co). which is no longer exponential in the horizon. In the following, we will denote by F the discretized version of reward y for all i E [N].
5.2. Challenges and Solution
To develop practical algorithms, some dimensionality challenges must be addressed. In this section, we explain how we will face them. In short, our solution permits to work with tractable approximations whose complexity is controlled by a discretization parameter 6o > 0. First, we need some notation. We use symbol 2%, to denote an co- discretization of the real-valued interval [0, h I].,iee, we
that
set Vi, == {0, 60. .e. [(h- 1o/ Vh E [H + l]. Moreover, we introduce ad-hoc symbols R, for the dis- cretization of intervals [o, 1] and [o, H]. namely, we let
R. := V/2 y ;= Vn+1- We also set d := | = (H/
Working with continuous utilitics. Utilities in 1l are de- fined over the real-valued interval [0, H]. making them in- compatible with the finite precision of computers. For this reason, we will consider discretized utilities. Formally, we will approximate any U E 1l with a d-dimensional vector T e -==I' such that Uly) Uly) Vy e y
5.3. CATY-UL (CompaTibility for Utility Learning)
Return distributions. In MDPs with dynamics p and re- ward r, return distributions 77 are supported on the set of possible returns = H]. However, in general, the size of this set grows exponentially in the horizon (S)))) causing any exact representation of ') to
The goal of CATY-UL (Algorithm 1) is to classify input utilities U e 1 based on whether they belong to set Us or
not for some A > O. We implement using two differ- ent subroutines (Lazzati et al., 2024a; 2025). First, Algo-
6

---

Learning Utilities from Demonstrations in MDPs
rithm 3 (reported in Appendix E for its simplicity) actively explores the N environments M uniformly, by collecting r' samples from each transition model p', and uses these samples to construct estimates p¹. Next, Algorithm 1 uses these estimates along with the expert's data D to classify any input utility U E Ll w.r.t. Un To perform the classi- fication, based on Eq. (3), CATY-UL computes estimates (U) 2 Cpi.ri,ne. (U)) for all i E [[V], and, then, it out- puts whether EME[N] (U) & A (see Line 8). To compute (U)), driven by Eq. (4), CATY-UL computes two sepa- rate estimates (U) J (U:p', r') (Lines 3-4) and (U) + JU; r*) (Line 5), and then combines them (Line 6). Specifically, the ERD (Estimate Return Distribu- tion) subroutine (Algorithm 5) permits to construct an es- timate sF of the categorical projection (roje in ( of the expert's 's return distribution 17p "ri,, from dataset DE. which is used at Line 4 to compute (U). Instead, quantity (U) is calculated at Line 5 as the optimal per- formance in the RS-MDP (S* A', H, s p¹, Fe. U,, which is computed through value iteration (Puterman, 1994) in the corresponding enlarged state space MDP using the PLANNING subroutine (Algorithm 4). CATY-UL enjoys the following guarantee for L-Lipschitz input utilities:
Algorithm 2 TRACTOR-UL
Input: data (D.),, ). parameters T, K, a, Us, discretization eu,
dynamics (p'} k.
7 < ED. R .r') for [N]
10
1 11 for t 0.1,.... 1 do
// Compute distributions (f8)e do 05 < PLANNING(U i.))) D - ROLLOUT ( " (v) < EoED 1 - y). Vy Ey
12
for i = 1, ...,. NN
14
15
end
// Update Uc+1:
St - E [ (fi - fP.i)
U1+1 I (U, agi)
end
20 Ô
7 ET-LU. U.
-
21 Return
functions. TRACTOR-UL (Algorithm 2) is a more "prac- tical" UL algorithm, in that aims to compute a util- ity function contained into the feasible set U, ,". As CATY-UL, it comprises an initial exploration phase (Algorithm 3), that collects r' samples to compute esti- mates Ø of the transition models p², and an extraction phase (Algorithm 2), where these estimates and the ex- pert's data DE, are used to compute utility (almost) in the feasible set. Specifically, since the utilities U in the feasible set satisfy Cr. (U) 0, TRACTOR-UL aims to find a minimum of function Σ, Cp.,rr,..... over the set Lz So, starting from an initial d-dimensional utility Uo E I, TRACTOR-UL computes sequence U UI....,UT UT by performing online projected gradient de- scent" (Orabona, 2023) in the space of discretized L- Lipschitz utilities Hg, where the gradient g. is computed at Line 17, and the update is carried out at Line 18. With infinite data, the gradient 9r at iteration would be En(p''s or aa 2. -pp''r', .f where o. *.4 is any optimal pol- icy in RS-MDP Mi, in which U, e IG is any util- ity satisfying Ur(y) Uz(y) for all y y. In our case, TRACTOR-UL. uses GF. computed at Line 10 in the same way as in CATY-UL, to approximate 17a pp'r"" 5is and it uses î. computed at Lines 13-15, to approximate sy8 x'' #.1 by estimating 7p ," a*t where 2, is the op- timal policy for the RS-MDP (S AA',, """, short, Line 13 computes policy म. through the enlarged state space approach, which is subsequently played in MDP (S' .'', H. S. ,²) (ROLLOUT subroutine, Algorithm 6, Line 14) to construct a dataset D of K trajectories that is used at Line 15 to compute n/. TRACTOR-UE enjoys the following guarantee:
Theorem 5.1. Let L 0, e, E 1). and let U s U1 be the set of utilities to classify. For all e [N], in case 14| = 1, let the number of samples satisfy:
N2212 E. 3 22
N 5)
r' 3
log SAHNL dE
log
22
Otherwise, if > 1, let the number of samples satisfy:
122 log dc (s log SAHN)) ))
HNL.
RA > δ
(5)
NASAH 2
Then, setting 6o = =2/((2H w.p. at least 1 for any A & O, CATY-UL correctly classifies all the U E U lying inside Ua-e or outside Us+e.
Roughly speaking, this theorem says that, for a number of samples independent of A, CATY-UL correctly recognizes all the utilities in Mss S Us and outside Us 2 Us as, respectively, inside and outside set U/s Intuitively, the Lipschitzianity assumption is necessary for approximating functions U E U with vectors in II. We remark that, if [4] = 1, then oCS queries to the generative model suffice. Otherwise, we require 82 samples.
In
5.4. TRACTOR-UL (eXTRACTOR for Utility Learning)
For simplicity of presentation, we introduce some notation. For any L > 0, let П, = and let 1f, Ly, II 2, Us be the analogous of, respectively, 1t, S1, II Ily, Us, but con- taining increasing functions instead of incresiin
This approach is based on (Syed & Schapire, 2007; Schlag- inhaufen & Kamgarpour, 2024).
7

---

Learning Utilities from Demonstrations in MDPs
Theorem 5.2. Let L O, e, E (0,1), and U Ly Assume that the projection operator II is implemented exactly. Let the number of samples satisfy Eq. (5). There exist values of 60, a, Uo (see Appendix E.5) such that, run ULACTOR-UL for a number of gradient iterations:
coupooopaaiiiiigg ((0,)
a=0.01
0.3
Q=5.5
a= 5
100
T ((N)))
0.2
1000
10000
then. w.p. at least - 6, any utility U E 11 such that U(v) Ü(y) Vy y belongs to u.
0.1
In other words, with high probability, TRACTOR-UL is guaranteed to find E, (U)) & 6, i.e., U is close to the feasible set. Note that we consider increasing utilities 1t, instead of strictly-inen iicereiiincre Mg to guarantee the closedness of the set onto which we project. Observe also that assuming that H. can be implemented exactly simplifies the theoretical analysis, but, in practice, we are satisfied with approxima- tions that can be computed efficiently since set I2 is made of O 2 /c)) linear constraints (Appendix E.
20
40
50
70
Iteration L
utility U with small
Figure 3. Simulations of TRACTOR-UE UL with various step sizes a. The shaded regions are the standard deviation over 5 seeds.
best step size for using TRACTOR-UL to compute a utility representative of the behavior of participant 10 is 100. Intuitively, this is explained by the presence of large num- ber of utilities in the feasible set (since we are considering demonstrations in a single environment N = 1), and by the projection step onto I, that results in small changes of utility even with large steps (see Appendix F.2.2). Next, we have run TRACTOR-UL on simulated data to analyze its performance on larger MDPs (increment of S, A) and with multiple environments (increment of N). We found that the number of gradient iterations necessary to achieve certain level of (non)compatibility is affected by the in- crement of N, but not of S, A, as predicted by Theorem 5.2. However, note that larger S, A require more execution time, because of the value iteration subroutine. Moreover, we observed that, when N 1, the best step size a can be much smaller than set contains less utilities now, thus, we need more accurate (smaller) gradient steps to find them. More details on this experiment in Appendix F.2.3.
6. Numerical Simulations
In this section, we present proof-of-concept experiments using data collected from lab members to provide empir- ical evidence to support both our model and algorithms.
The data. We asked to 15 participants to describe the ac- tions they would play in an MDP with horizon = 5 (see Appendix F), at varying of the state, the stage, and the cu- mulative reward collected. The reward has a monetary in- terpretation. To answer the questions, the participants have been provided with complete information about the MDP.
Experiment Validation of the model. Our model of behavior, presented in Fq. (1), is the first IRI. model that contemplates non-Markovian policies. To understand if this new model is more suitable than existing IRL mod- els describe human behavior in MDPs, count how many participants the study exhibited non-Markovian behavior. Intuitively, the more non-Markovianity, the bet- ter our model. What we found is that 10 participants out of 15 demonstrated a Mar-vvrkovi policy even in this very small environment, providing consistent evidence on the importance of our new model. See Appendix F.3 for additional analysis of our model on this data.
100. Intuitively, the feasible
7. Related Work
In risk-sensitive IRI. (Majumdar et al., 2017), the leamnrr is either provided with the reward of the expert and it must infer some parameters representing its risk attitude, or the learner must infer both the reward and the risk attitude from demonstrations of behavior (Singh et al., 2018; Chen et al., 2019; Ratliff Mazumdar, 2020; Cheng et al., 2023; Cao et al., 2024). However, these works consider problem set- tings and models of behavior fairly different from ours. Specifically, Majumdar al. (2017); Singh al. (2018); Chen et al. (2019) focus on the so-called "prepare-react model", which is a model of environment less expressive than an MDP. Instead, Ratliff & Mazumdar (2020); Cheng et al. (2023); Cao et al. (2024) consider models behav- ior which the expert's policy is Markovian. More on the
Experiment 2 Validation of TRACTOR-UL. To under- stand how TRACTOR-UL. performs in practice, we have run it on both the real-world data described earlier and on simulated data. Crucially, the executions on the partici- pants' data reveal that, irrespective of the initial utility U. adopted, the algorithm converges much faster using large values of step size a. For instance, as shown in Fig. 3, the
"hhe data collected not personal.
8

---

Learning Utilities from Demonstrations in MDPs
related works in Appendix A.
learning with generative model. Machine Learning, 91 (3):325-349, 2013.
8. Conclusion
Barz, C. Risk-Averse Capacity Control in Revenue Man- agement. Springer, 2007.
In this paper, we proposed a novel rwsk- model of be- havior that rationalizes non-Markovian policies in MDPs,
Bellemare, M. G., Dabney, W. and Rowland, M. Distribu- tional Reinforcement Learning. MIT Press, 2023.
and we presented two provably-efficiet algorithms for learning the risk attitude an agent from demonstrations. Interesting directions for future works include extending algorithms to high-dimensional settings, studying the problem of learning both and (/ from demonstrations, and exploring new methods to alleviate the partial identifiabil- ity.
Bernhard, J., Pollok, S., and Knoll, A. Addressing in- herent uncertainty: Risk-sensitive behavior generation for automated driving using distributional reinforcement learning. IEEE Intelligent Vehicles Symposium (IV), pp- 2148-2155, 2019.
Bäuerle, N. and Rieder, U. More risk-sensitive markov de- cision processes. Mathematics of Operations Research, 39(1):105-120) 2014.
Acknowledgements
AI4REALNET has received funding from European Union's Horizon Europe Research and Innovation pro- gramme under the Grant Agreement No 101119522 Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting au- thority can be held responsible for them.
Cao. H., Cohen, S., and Szpruch, L. Identifiability in in- verse reinforcement learning. In Advances in Neural In- formation Processing Systems 34 (NeurIPS), pp. 12362- 12373, 2021.
Cao, H., Wu, Z., and Xu, R. Inference of utilities and time preference in sequential decision-making, 2024.
Funded by the European Union Next Generation EU within the project NRPP M4C2, Investment 1.,3 DD. 341 15 march 2022 FAIR Future Artificial Intelligence Re- search- Spoke 4 PF00000013 D53C22002380006.
Chajewska, U.. Koller, D., and Ormoneit, D. Learning an agent's utility function by observing behavior. In Inter- national Conference on Machine Learning 18 (ICML), pp. 35 42, 2001.
Impact Statement
Chen, R., Wang, W., Zhao, Z., and Zhao, D. Active learning for risk-sensitive inverse reinforcement learn- ing, 2019,
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Cheng, Z., Coache, A., and Jaimungal, Eliciting risk aversion with inverse reinforcement learning via interac- tive questioning, 2023.
References
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Re- inforcement Learning: Theory and Algorithms. 2021. URL httph:tp////// http:////thhheryoooeko httpr///ooooo.tt.u....... io/.
Fu, J., Luo, K., and Levine, S. Learning robust rewards with adversarial inverse reinforcement learning. In In- ternational Conference on Learning Representations (ICLR), 2017.
Amin, K. and Singh, S. Towards resolving unidentifiability in inverse reinforcement learning, 2016.
Föllmer, H. and Schied, A. Stochastic Finance: An Intro- duction in Discrete Time. De Gruyter, 2016.
Arora, S. and Doshi, P. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:10351 2021.
Ho, J. and Ermon, S. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems 29 (NeurIPS), 2016.
Artzner, P., Delbaen, F., Eber, J., and Heath, D. Coherent measures of risk. Mathematical Finance, 93))2033-228 1999.
Jonsson, A., Kaufmann, E.. Menard, P., Dar- wiche Domingues, O., Leurent, E., and Valko, M. Planning in markov decision processes with gap- dependent sample complexity. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 1253-1263, 2020.
Azar, M. G., Munos, R., and Kappen, H. Minimax PAC bounds on the sample complexity of reinforcement

---

Learning Utilities from Demonstrations in MDPs
Kahneman, D. and Tversky, A. Prospect theory: An anal- ysis of decision under risk. Econometrica, 47(2):263- 291, 1979.
Poiani, R., Curti, G., Metelli, A. M., and Restelli, M. In- verse reinforcement learning with sub-optimal experts, 2024.
Kim, K., Swamy, G., Liu, Z., Zhao, D., Choudhury, S., and
Pratt, J. W. Risk aversion in the small and in the large. Econometrica, 32:122-136, 1964.
Wu, S. Z. Learning shared safety constraints from multi- task demonstrations. In Advances in Neural Information Processing Systems 36 (NeurlPS), pp. pp- 5808-5826, 2023.
Puterman, M. L. Markov Decision Processes: Discrete
Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
Kreps, D. M. Notes On The Theory Of Choice. Westview Press, 1988.
Ramachandran, D. and Amir, E. Bayesian inverse rein- forcement learning. In International Joint Conference on Artifical Intelligence 20 (ICCAI), pp. 2586-2591, 2007.
Lazzati, F., Mutti, M., and Metelli, A. M. How does in- verse scale to large state spaces? provably efficient approach. In Advances in Neural Information Process- 2024a.
ing Systems 37 (NeurIPS), pp.
Ratliff, L. J. and Mazumdar, E. Inverse risk-sensitive re- inforcement learning. IEEE Transactions on Automatic Control,
Lazzati, F., Mutti, M., and Metelli, A. M. Offline inverse rl: New solution concepts and provably efficient algo- rithms. In International Conference on Machine Learn- ing 41 (ICML), 2024b.
2020.
Rockafellar, R. T. and Uryasev, S. Optimization of condi- tional value-at risk. Journal of Risk, 3:21-41, 2000.
Lazzati, F. Mutti, M., and Metelli, A. Reward compatibil- ity: A framework for inverse rl, 2025.
Rowland, M. Bellemare, M., Dabney, W., Munos, R., and Teh, Y. W. An analysis of categorical distributional re- inforcement learning. In International Conference on Artificial Intelligence and Statistics 21 (AISTATS), vol- ume 84, pp. 29-37, 2018
Lei, B. Learning influence diagram utility function by ob- serving behavior. In Advanced Multimedia and Ubiqui- tous Engineering 14 (MUE), pp. 164-168, 2020.
Rowland, M., Wenliang, L. K., Munos, R., Lyle, C., Tang, Y., and Dabney, W. cear-minimax-optinne distributional reinforcement learning with generative model, 2024.
Majumdar, A., Singh, S., Mandlekar, A., and Pavone, M. Risk Disk-sensitive inverse reinforcement learning via coher- risk models. In Robotics: Science and Systems 13
(RSS), 2017.
Russell, S. Learning agents for uncertain environments (extended abstract). In Proceedings of the Eleventh An- nual Conference on Computational Learning Theory 11 (COLT), pp. 101-103, 1998.
Malik, S., Anwar, U., Aghasi, A., and Ahmed, A. In- verse constrained reinforcement learning. In Interna- tional Conference on Machine Learning 38 (ICML), vol- ume 139, pp. 7390-7399, 2021.
Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach. Prentice Hall, 3 edition, 2010.
Metelli, A. M., Ramponi, G., Concetti, A., and Restelli, M. Provably efficient learning of transferable rewards. In International Conference on Machine Learning 38 (ICML), volume 139, pp. 7665-7676, 2021.
Schlaginhaufen, A. and Kangarpour, M. Towards the transferability of rewards recovered via regularized in- verse reinforcement learning, 2024.
Metelli, A. M., Lazzati, F., and Restelli, M. Towards theo- retical understanding of inverse reinforcement learning. In International Conference on Machine Learning 40 (ICML), pp. 24555-24591, 2023.
Shah, R., Gundotra, N., Abbeel, P., and Dragan, A. On the feasibility of learning, rather than assuming, human biases for reward inference. In International Conference on Machine Learning 36 (ICML), volume 97, pp. 5670- 5679, 2019.
Ng. A. Y. and Russell, S. J. Algorithms for inverse rein- forcement learning. In International Conference on Ma- chine Learning 17 (ICML 2000), pp. 663-670, 2000.
Shukla, N., He, Y., Chen, F., and Zhu, S.-C. Learning human utility from video demonstrations for deductive planning in robotics. In Conference on Robot Learning 1 (CoRL), volume 78, pp. 448-457, 2017.
Orabona, F. A modern introduction to online learning, 2023.
Osa. T., Pajarinen, J., Neumann, G., Bagnell, J. A., Abbeel, P.. and Peters, J. An algorithmic perspective on imitation learning. Foundations and Trends@ in Robotics, 7(1-2): 1-179, 2018.
Singh, S., Lacotte, J., Majumdar, A., and Pavone, M. Risk- sensitive inverse reinforcement learning via semi- and parameert methods. The International Journal of Robotics Research, 37(13-14):1113-1777 2018
10

---

Learning Utilities from Demonstrations in MDPs
Skalse, and Abate, A. Quantifying the sensitivity of in- verse reinforcement learning to misspecification. In In- ternational Conference on Learning Representations 12 (ICLR), 2024.
Skalse, M. V., Farrugia-Roberts, M., Russell, S., Abate, A., and Gleave, A. Invariance in policy optimisation and partial identifiability in reward learning. In Inter- national Conference on Machine Learning 40 (ICML), volume 202, pp. 32033-32058, 2023.
Syed, U. and Schapire, R. E. A game-theoretic approach to apprenticeship learning. In Advances in Neural Infor- mation Processing System 20 (NeurIPS), 2007.
Villani, C. Optimal Transport: Old and New. Springer
Berlin, Heidelberg, 2008.
von Neumann, J. and Morgenstern, O. Theory of Games and Economic Behavior. Princeton University Press, 1947.
Wakker, P. P. Prospect Theory: For Risk and Ambiguity. Cambridge University Press, 2010.
Wu, Z. and Xu, R. Risk-sensitive markov decision process and learning under general utility functions, 2023.
Xiong, C., Shukla, N., Xiong, W., and Zhu, S.-C. Robot learning with a spatial, temporal, and causal and-or graph. In IEEE International Conference on Robotics and Automation 33 (ICRA), pp. 2144-2151, 2016.
Zhao, L.., Wang, M., and Bai, ment learning harder than standard reinforcement Iearn- ing? In International Conference Machine Learning 41 (ICML), 2024.
inverse reinforce-
Ziebart, B. D. Modeling purposeful adaptive behavior with the principle of maximum causal entropy, 2010.

---

Learning Utilities from Demonstrations in MDPs
A. More on Related Work
We describe here more in detail the most relevant related works. First, we describe IRL papers with risk, i.e., those works that consider MDPs, and try to learn either the reward function or the utility or both. Next, we analyze the works that aim learn the risk attitude (i.e., a utility function) from demonstrations of behavior (potentially in problems other than MDPs). Finally, we present other connected works.
Inverse Reinforcement Learning with risk. Majumdar et al. (2017) introduces the risk-sensitive IRL problem in deci- sion problems different from MDPs. The authors analyze two settings, one in which the expert takes single decision, and one in which there are multiple decisions in sequence. They model the expert a risk-aware secision-makingg agent acting according to coherent risk metric (Artzner et al., 1999), and they consider both the case in which the reward function is known, and they try to learn the risk attitude (coherent risk metric) of the expert, and the case in which the reward is unknown, and they aim to estimate both the risk attitude and the reward function. Nevertheless, the authors analyze a model of environment, called prepare-react model, rather different from an MDP, since, simply put, it can be seen as an MDP in which the stochasticity is shared by all the state-action pairs at each stage h E [H]] Moreover, they consider Markovian policies. Singh al. (2018) generalizes the work of Majumdar et al. (2017). Specifically, the biggest improvement is to consider nested optimization stages. However, the model of the environment is still rather different from an MDP. We mention also the work of Chen et al. (2019) who extend Majumdar et al. (2017) by devising active learning framework to improve the efficiency of their learning algorithms.
Another important work is that of Ratliff & Mazumdar (2020), who study the risk-sensitive IRL problem in MDPs, by proposing a parametric model of behavior for the expert based on prospect theory (Kahneman & Tversky. 1979), and they devise a gradient-basee IRL algorithm that minimizes a loss function defined on the observed behavior. This work differs from ours in that it assumes that the expert plays actions based softmax distribution, i.e., using Markovian policy.
Cheng et al. (2023) proposes model of behavior in MDPs using the conditional value-at-risk (Rockafellar & Uryasev, 2000) instead of a utility function (von Neumann & Morgenstern, 1947). Moreover, differently from ours, their model does not contemplate non-Markovian policies. Similarly to us, they analyze the partial identifiability of the parameters representing the risk attitude from demonstrations in a single environment, and propose a strategy for designing the envi- ronments which collecting additional demonstrations in order to reduce the partial identifiability.
We shall mention also the recent pre-print of Cao al. (2024) that proposes a novel stochastic control framework in continuous time that includes two utility functions and a generic discounting scheme under a time-varying rate. Assuming to know both the utilities and the discounting scheme, the authors show that, through state augmentation, the control problem is well-posed. In addition, the authors provide sufficient conditions for the identification of both the utilities and the discounting scheme given demonstrations of behavior. We note that there are crucial differences between this work and ours. First, the author model the expert as solving an optimization problem in which the utility function is applied to the per stage reward, instead we apply the utility to the entire return (see Eq. (1)). Next, they model the expert using Markovian policies.
Learning utilitics from demonstrations. Chajewska et al. (2001) considers an approach similar to IRL Ng & Russell (2000). Their goal is not to perform active preference elicitation, but, similarly to us, to use demonstrations to infer preferences. Specifically, they aim to learn utilities in sequential decision-making problems from demonstrations. However, they model the problems through decision trees, which are different from MDPs, and this represents the main difference between their work and ours. Indeed, decision trees are simpler since there is no notion of reward function at intermediate states. In this manner, they are able to devise (backward induction) algorithms to learn utilities in decision trees through linear constraints similar to those devised by Ng & Russell (2000) in IRL. It is interesting to notice that they adopt a Bayesian approach to extract a single utility from the feasible set constructed, and not an heuristic like that of Ng & Russell (2000). They assume a prior p(u) over the true utility function u, and approximate the posterior w.r.t the feasible set of utilities 24 using Markov Chain Monte Carlo (MCMC).
Shukla et al. (2017) faces the problem of learning human utilities from (video) demonstrations, with the aim of generating meaningful tasks based on the learned utilities. However, differently from us, they consider the stochastic context-free And-Or graph (STC-AOG) framework (Xiong et al., 2016), instead of MDPs.
Lei (2020) considers the problem of learning utilities from demonstrations similarly to Chajewska et al. (2001), but with the difference of considering influence diagrams instead of decision trees. Since any influence diagram can be expanded
12

---

Learning Utilities from Demonstrations in MDPs
into a decision tree, authors adopt strategy similar to Chajewska et al. (2001).
Others. Shah al. (2019) aims learn the behavioral model of the expert from demonstrations. However, they do not consider specific model like (i.e., Eq. (I)), but use differentiable planner (neural network) to learn the planner. In principle, they can fit any behavioral model (also risk-sentitive models) given the huge expressive power of neural networks. However, their approach requires a lot of demonstrations, even across multiple MDPs. Moreover, this approach does not permit to learn a utility function as a simple, interpretable, and transferrable representation of the risk attitude of the expert.
B. Additional Notation
In this appendix, we introduce additional notation that will be used in other appendices.
Miscellaneous. For any probability distribution y E AB, we denote its cumulative density function by F.. Let v e A be a probability distribution on I;; then, for any y [0, 1J. we define the generalized inverse F (3) as:
Fラ (v) = inf (F)()) 3 y). X
ReR
We define the I-Wasserstein distance wi
[0, coJ between two probability distributions 1 as:
wi (v, :- (v) (y)ldy
(6)
In addition, we define the Cramér distance lo A A - [0, co] between two probability distributions 2, as:
(2 = (S (Fr(v) - Fa(w))
We will notation:
= Ex Exxql(xXxXXX - -xx+lXX]"], V Xx-Q x [X]
to denote the variance of a random variable X Q distributed as Q. Given two random variables X ~ Q1, ~ Q2 we denote their covariance as:
Covx-Q.Y-Q,X;Y1 = Cor.oarrooAA11--xaaarlll--------
- -Ey-
We define the categorical projection operator Proje (mentioned in Section 5), that projects onto set y {yı V2. ........ ya (the items of y are ordered: y1 & 1/2 ... ya. with yı 0, 1/2 60, 1/3 2eo...., Dd [H/eoJoo), based Rowland
et al. (2018). For single Dirac measures on an arbitrary y IR, we write:
8ys
if y & 91
Proje(5,)) ==
gi y Ui
Ui+1 2 0aer
if < y & Vet1;
(8)
2
8ys
if y > Dd
and we extend it affinely to finite mixtures of M Dirac distributions, so that:
Proje Σ gide,)
Σ gf ()Poojc(82,)
(9)
jE[M]
for some set of real values [2ybeeM and weights {9:bşe[M1-
Value functions. Given an MDP M = (S.A, H, so, r) and a policy т,, we define the V- and Q-functions of policy
in MDP M at every h) S A [H] respectively QT,(s, (s, a.p,r) r) = Ep... at) = s, an = a]. We define the optimal V- and functions as V (s:p,r) = sup, V. (s:p,r r) and (s, =- sup, Q (8, a.
(s) = Ep.,, 1E Te(si, a,)]s, = s] and
13

---

Learning Utilities from Demonstrations in MDPs
For MDPs with enlarged state space, e-g., (IS x Vihn, A, H, (so, 0), p. t), and a policy (1h dn for all h [H] and (s, y, a) E x V/8 x A we denote the V- and Q-functions respectively as V2, yi p. t) = Ep. 1 (5 ye, at)]s = s, yhh y) and Q (s. r) := Ep.r. [-i Fe(st, yt. 0r)lsh s, yh y,a,, a]. We denote the optimal V- and Q-functions as V (s. y: p. r) == s V (s. y: p. and Q7 y, a: a. == a (s. o.
Observe that the notation just introduced will be extended in straightforward manner MDPs (MDPs with enlarged state space) that have estimated transition model (f), and/or discretized reward function F (t).
C. Additional Results and Proofs for Section 3
In Appendix C.I, we explain why including the past rewards into the state is not satisfactory, in Appendix C.2 we provide an observation on Eq. (1), while in Appendix C.3 we provide the missing proofs for Section 3.
C.1. Drawbacks of Re-modelling the MDP
Re-modelling the MDP including the sum of the past rewards into the state would make the demonstrated policy Markovian, and so, in principle, it would allow to apply the existing IRL models meaningfully. However, since in IRL the reward function is unknown, to adopt this trick one should include into the state representation the entire sequence of past state- action pairs, causing the size of the new state space to explode, and also causing the reward function to become non- Markovian w.r.t. the original state space. If instead the reward function was known, and one just wanted to apply one of the risk-sensitive IRL models of behavior presented in Section 7 to learn the (parameters of the) risk attitude, then re-modelling the MDP would still cause the size of the new state space to explode in tabular MDPs, since, in general, there is a number of cumulative reward values that is exponential in the horizon. Moreover, it is not clear why the considered model of behavior, that was designed for the original state space (not including the past rewards), should be realistic in the new state space.
C.2. An Observation on the Model
If we restrict the optimization problem in Eq. (1) to Markovian policies, we note that non-stationarity (i.e., the dependence of the policy on the stage h) and stochasticity (i.e., if the policy prescribes a lottery over actions instead of a single action) can improve the performance w.r.t. Markovian stationary deterministic policies even in stationary environments. Intuitively, the reason is that they permit to consider larger ranges of return distributions w.r.t Markovian stationary deterministic policies.
Proposition C.1.
There exists a RS-MDP with stationary transition model and reward in which the best Markovian policy is non-stationaay, and the best stationary Markovian policy is stochastic.
C.3. Proofs for Section 3
Proposition 3.1. There exists a RS-MDP in which the difference between the optimal performance and the performance of the best Markovian policy is 0.5.
Proof. For reasons that will be clear later, let us define symbol x x 2.6 as the solution of x
x²
0.11 = 1.
3.00
Consider the RS-MDP My (S, H, so r. U) in Fig. 4, where S {Simis $1, 82, 83, S4, 85, 85,88) 86). A (21. Smits transition model p such that:
H 4, 30
Pi P1(s1|imntt a) p1($2|smit, a) = 1/2 Va E A, (2(53 a) = P2(53| a) = Va E A,
Pa Pa(sa|sa, a1) = x/3.99, pa(s5 88, a1) = 1 - x/ pr/3/99.pa(ssllss 02) = 1,
reward function r defined as:
ri (sinti a) = 0 Va E A,
r2(81, a) = 1 Va E A,
r2(82, Va E A,
14

---

Learning Utilities from Demonstrations in MDPs
$4
2/3.99
2/3 330
1/2
start
Smit
01:
==
1/2
02
$2
0.5
96
Figure 4. MDP for the proof of Proposition 3.1.
(3(83, a) Va E A,
(54, a) Va E A,
(56, a) 0 Va E A,
(5 a) = 0.5 Va A,
and utility function U 11 that satisfies:
x 0.1
if y 0.5 if y = 1
U(y)
V x
if = 1.5
3.99
if
Note that this entails that:
3.99 U(2) U(1) U(..))
(10)
Note also that the support of the return function of this (RS-)MDP gr = (0,0.5,
0,5, 1.5.2
For a [o, 1]. let Th be the generic Markovian policy that plays action 01 in 83 w.p. a (the actions played in other states not relevant). Then, its expected utility is:
J (U:p.r) 2
1
U(2) + (1- x
(U)) +1 (1-a))((1.5)
3.99
3.99
+
I
U(1) + (1
(((0) + - a)U(0.5))
2
3.99
3.99
())
U(2) + U(1) + - (1
aU) + U(O.5))
2 3.99
( U (1.5) + U(0.5)
where (1) we have used that U(0) and at (2) we have used Eq. (10).
Thus, all Markovian policies n have the same performance. Let us consider the mar-Morkovi policy म that, in state 83, plays action w.p. 1 if 83 is reached with cumulative reward 1, and it plays action w.p. 1 if 83 is reached with cumulative reward 0. Then, its performance is:
J=UUpp,r) 1 T U(2)
(2) + (1
3.99 3.9 (0)) + (0.5).
3.99
The difference in performance between the optimal performance and that of a is:
(U: _=" (U:p,r) ("Upp,r)) F J= (U:p.r)
15

---

Learning Utilities from Demonstrations in MDPs
0.5
$1
$1
0.5
r=1
start
Smil
Smil
41
1/3
41
1/3
2/3
2/3
r= 0
83
83
Figure MDP for the proof of Proposition C.I.
1 T
U(2) + (1
((1) +
1 + U(0.5)
((1.5) + U(.5))
2
3.99
3.99
2
1 T
((2) + (1
UU( - U(15))
3.99
3.99
x²2
+ 3.99
0.1
x²
0.1
3.99
(4) 0.5,
where (3) have replaced the values of utility, and at (4) we have used the definition of sc
Proposition 3.2. p is deterministic, then arg max, JJ (U arg max, J (p,
Proof. If p is deterministic, then the optimal policy in Eq. (1) is the policy that deterministically plays the trajectory with largest value of (g(w)) (g(w) denotes the return of under reward rF) Since, by hypothesis, U Il, then it is strictly increasing, thus such trajectory coincides with the trajectory with largest return.
Proposition C.1. There exists a RS-MDP with stationary transition model and reward in which the best Markovian policy is non-slationury, and the best stationary Markovian policy is stochastic.
Proof. Consider the stationary RS-MDP My So, depicted in Fig. 5, where S {Stiits $1, $2, $3). A [a), H 4, Sinis stationary transition model (we omit subscript because of stationarity) such that:
p(82 (iniit a1) = 1 p(8a/sinii Sinits a1) = 1/3,
p(s) [8init; a2) = 1,
pl Smal (s, a) Vss E (81, $2, s3). Va A.
reward function defined as:
T(innts a) = 0 Va E A,
r(s1, a) = 0.5 Va E A.
r(s2, a) 1 Vae A.
r(83, a) Va A,
16

---

Learning Utilities from Demonstrations in MDPs
and utility function U Il that satisfies:
0.15
if 0.5
0.2
y =
U(v)
1.8
y 1.5
2 if
Let 7 denote the general non-stationary policy that plays action ai at stage I w.p. [0. IJ. and plays action at stage 2 w.p. B [0, 1]. The performance of policy n can be written as:
Jm (U:p.r) a 3 ((2) (
(0() + (1-33) + 2 L
+ a) ( ( 3 + +(1 (1-3)U(1)
o8 10)) + 1
13
U(1)
2
U(1.5) 1 U(0.5)
3
2
+ (a 8)
U((5)
+ U(.5)) -U(1] U(1
2
13
18
1
aB
5
+a B)
[5
+ 10 5 +
9
45
15
8
08
T0
(a+
+ B)
+)+
To show that the best Markovian policy is non-stationary in this example, we show that the performance of non-stationary policy 0.1 better than the performance of all possible Markovian policies. The performance n. is:
J (U:p,r)
10 + 0.3.
Instead, the generic stationary policy is a and has performance:
(U:p,r) = - -aa + 3 5'
1
The value of [O, 1] that maximizes this objective is:
d 5 (U:p,r)
16
1
de
9
80
from which we get:
j 3/ (U:p.r)
169
0.22,
800
which is smaller than 0.3 J (U:p, r). This concludes the proof of the first part of the proposition.
For the second part, simply observe that, in the problem instance considered, we just obtained that the best Markovian stationary policy plays action a₁ w.p. 9/80, i... it is stochastic.
D. Additional Results and Proofs for Section 4
In this appendix, we provide a more explicit formulation for the feasible utility set (Appendix D.I), we present a property of the distance اill (Appendix D.2), and then we provide the proofs of all the results presented in Section 4 (Appendix D.3).
D.I. A more Explicit Formulation for the Feasible Set
For any policy т. we denote by SP...T the set of all (s, h, y) state-stage-cumulatie reward triples which are covered with non-zero probability by policy æ in the considered MRS-)MDP.
Thanks to this definition, we can rewrite the feasible set as follows:
17

---

Learning Utilities from Demonstrations in MDPs
Proposition D.I. Let M (S, A, H, so:Po p,r) be MDP, and let Th be the expert policy. Then, the feasible utility set Uprar contains all and only the utility functions that make the actions played by the expert policy optimal at all the (s, y) E Sp.r.".. Formally:
V) SP Vaa Up Up (
Qu(s.u. (s. v).p.) Q*".,,
where we used the notation introduced in Appendix B.
Proof Sketch. Based on Theorem 3.1 of Bäuerle & Rieder (2014) (or Theorem 1 of Wu & Xu (2023)), we have that utility U E I belongs to the feasible set it makes the expert policy optimal even in the enlarged state space MDP (note that is possible to define policy s for the enlarged MDP because we are considering policies æ whose non-Markovianity lies only in the cumulative reward up to now). Therefore, the result follows thanks to proof analogous to that of Lemma in Lazzati et al. (2024b), since we are simply considering a common MDP with two variables per state.
D.2. A Property الهl
We note that closeness under the max norm (restricted to a certain domain) implies closeness under d=ll: Proposition D.2. Consider an arbitrary MDP with transition model p and reward function Then, for any pair of utilities U2 S. it holds that delt (U1, U2) & maxceGe. [Ui(G) ((2)))
Proof. For the sake of simplicity, we denote the infinity norm and the 1-norm w.r.t. set G as: | max [[G)) and [[f]] == Egego- [f(]). In addition, overload notation and use symbols U1, U2 to denote the vectors in [0, H G containing, respectively, the values assigned by utility functions U1, U2 to points in set GPIT, Then, we can write:
dell (U1, = sup
J= JF - (U2;))))))
nell
sup
Ea-ypo [Ui(G)] - Ea- (U2
xell
sup Ea-ypem [Ui(G) U2(G)]
well
(1)
sup | [U(() (2)]]
sup EG U1( U2(G))
U1
Uzlbo.
where at (1) we upper bound by considering the set of all possible distributions over set GP instead of just those induced by some policies in the considered MDP, at (2) we apply triangle inequality, and at (3) we have used the fact that || ||2 and || lo are dual norms.
D.3. Proofs for Section 4
Example 4.1. Consider the MDP M in Fig. 2 (left), where 2,r1 1,,r) - 0.5. Let the expert's 's policy = prescribe a1 in 8p- Then, all the utility functions UE that take on values in the blue region of Fig. 2 (middle) for returns G= 1- 1.5, make x F optimal in Mu.
Proof. A utility U E 1l makes _H optimal for My if playing a is better than playing az: J= (U: = 0.10(2) + 0.5U (1.5) + (1) > (..5( + (1) Thus, all the utilities e II that assign to = 1, G = 1.5 any of the values coloured in blue in Fig. (middle), satisfy this condition.
so. p.r), M' (S, H. sp. su.p'. p,rr), with # p'. which there exist a policy TO E and pair of utilities U1, U2 up such that TT , n [ = 0.
Proposition 4.1. There exist two MDPs M = (S, so:
18

---

Learning Utilities from Demonstrations in MDPs
G1 42
1/4
01 02
1/4
80.25
start
Sinit
02
4/2
80.75
(11 02
1/2
01, 02
Figure MDP proof Proposition 4.1.
Proof. We will prove the guarantee stated in the proposition using two different pairs of MDPs: One that that satisfies ge'r GP.,r i.e. for which the support of the return function coincides, and the other that does not. Let us begin with the former.
Consider simple MDP M (S,A, H, Smits p, r) with five states S {Simits So. $0.25 $0.75; 81), two actions A (2), horizon H 2, initial state Sinit, transition model such that:
1/4 if 80
1/4 if $0.25
pi (8' Sinit; a1)
1/4
if 80.75
1/4 if s' $1
1/2 if s' = 80.25
p1(8'18imi az)
1/2 if 8' = 80.75
and reward function r that assigns Tı ( (iitts a1) = ri r (smit 02) = 0, and:
0
if s So (a v= 02)
0.25
s = 80.25 ^ (a 01 a 02)
(2(
0.75
s $0.75 ^ (a 01 v a2)
if 8
(a va=
Note that the support of the return function GP.r = {0, 0.25, 0.75, 1). We are given an expert's policy T that preseribes action d1 stage in state Sinis and arbitrary actions in other states (the specific action is relevant). The MDP M represented in Figure 6.
Now, show that utilities U1, U2 1. defined in points of the support Gp. (and connected in arbitrary continuous strictly-increasing manner between these points):
0
if G
0
if G
0.01
if G 0.25
0.01
if G 0.25
(G)
U2(G)
0.02
G 0.75
0.99
G 0.75
1.99
G
1.99
if G
belong to the feasible set 24 5, and, when transferred new MDP M' (S, A, H, Binits p/ r),, with transition model o p defined as:
S-iisis a1) Px Simit, 01);
19

---

Learning Utilities from Demonstrations in MDPs
(1 (iiits 02)
0.7
if
80
0.3
if $1
impose different optimal policies, i... utility U2 keeps making action a1 optimal from state Sinit even in M' while Uj makes action 02 optimal. This proves the thesis of the proposition.
Let us begin by showing that U1, U2 E Up belong the feasible set of M with policy x². Let ग be the policy that plays action in state Sinit- Then, the distribution of returns induced by policies n and are (we represent values only at points in G = {0, 0.25,0...... 0.75, 13):
ip 1//4
1p.. [0,1/2,1/2,0]
Thus, policy x is optimal under some utility U and only if the values assigned by U to points in GP {0, 0.25, 0.75, 13 (denoted, respectively, by U!, ,U",, U3, U4) satisfy:
UT -))) - [/4 - 1/4,-11/4,1/4,////91 = U U2 - + U > 0,
U3
where we have overloaded the notation and denoted with U = [U -U',U2,00 U3,
UU, UUP both the utility and the vector of values
assigned points in Ga. By imposing normalization constraints (U(0) (2) 2), we get U 0, and by imposing also the monotonicity constraints, we get that utility U is in the feasible set Upr,, if and only if:
T > u2 U3
0 02 <
Clearly, both utilities U1, U2 satisfy these constraints, thus they belong to the feasible set Up p. Now, concerning problem M', the performances of T क w.r.t. utilities U1, U2 are:
(U:p',r)
4 [i(0) + (0.255) + (1.75) + (1( 2.02/4 = 0.505, 4
4
F(ULd( (07 013 - 0.3 x 1.99 0.597,
J= (Un:1'r) r) 4 [0) + 4 (0.25)) + (0.75) + (i(1) 2.99/4 0.7475,
4
J" r)) (0) (1) 0.3 1.99 0.597.
Clearly, Js (Un:',r) < r)) but J J (U2;p',r) > (U2; r),, thus we conclude that the set of policies induced by utilities U1, U2 in M' do not intersect, since they start from Sina with different actions IT p', (U,) / (U2) 0. This concludes the proof with an example that satisfies GP'rr GP.r.
If want an example that does not satisfy Gp'." GP. then M', but using Tı (Sint a2) = 0.001. In this manner, we see that gar = {0, 0.25, 0. 0.251, 0.75, 0.751, 1}, and gr'ir (0, 0.001, 0.25, 0.75, 1, 1.0013. which are different. By choosing Ui, U3 as:
consider exactly the same example with M and
0
if G 0
0
if G 0
0.001
if G = 0.001
0.001
if G = 0.001
0.01
if G 0.25
0.01
if 0.25
0.011
if G 0.251
0.011
if 0.251
UG(G)
0.02
if = 0.75
0.99
if 0.75
0.021
if 0.751
0.991
if 0.751
1.99
Gf = 1
1.99
if = 1
1.991
if 1.001
1.991
if G 1.001
it can be shown that U1, U/ belong to the (new) feasible set of M, and that induce different policies in M'. This concludes the proof.
20

---

Learning Utilities from Demonstrations in MDPs
1 42
81
start
Sinit
Ø1, 42
02
0.9
82
0.1
Figure 7. MDP for the proof Proposition 4.2.
Proposition 4.2. There exist two MDPs M = (8, A, H, 80, P. r), M' = (S, H. 80. p. r'),,, with r', which there exist a policy n E and pair of utilitiies U1, U2 Up,r= such that (U1) n ( = (}.
Proof. Similarly the proof of Proposition 4.1, provide examples, with ga.n' gP.,, and the other with goo # *g* Let us begin with the former.
Consider simple MDP M (S. A, H, Smit: P, r) with three states S {Simit, 81, 82), two actions A {0i, 02), horizon H1 2, initial state Sinit, transition model such that:
1/2 if 8 81
(1(8' Sinits a1)
1/2 s $2
0.9 if 81
P1(s' Sinit 02)
0.1 if $2
and reward function r that assigns ry (sinit; a1) = 0, ri (Sint: 02) = 0.5, and:
0 if $1 (a a1 02)
r2(s, a)
1 if s 82 A (a a=
a2)
Note that the support of the return function is GP (0, 0.5, 1, 1.5). We given expert's policy E that prescribes action d stage I in state Sinits and arbitrary actions in other states (the specific action is not relevant). The MDP M is represented in Figure 7.
Now, we show that the utilities U1, U2 E S, defined in points the support GP as (and connected arbitrary continuous strictly-increasing manner between these points):
G =
0
if =
0.1
if 0.5
0.1
if 0.5
U1(G)
(2(G)
0.9
ifG =1
0.8
ifG =1
1.5
ifG 1.5
1.5
if = 1.5
belong to the feasible set 24, 5, and, when transferred to the new MDP M' (S, A, H, Sinits P, r²), with reward function * r defined as:
r (Simit; a1)
0.5,
(Siit, 02) 0,
1
if = (a= 02)
( a)
0 if 82
a a2)
impose different optimal policies, i.e., utility U2 keeps making action optimal from state Smit even in M', while U1 makes action optimal. This will demonstrate the thesis of the proposition.
Let us begin by showing that U1, U2 E Up.r.== belong to the feasible set of M with policy - F Let ग be the policy that plays action 02 in state Siit- Then, the distribution of returns induced by policies म. and æ are (we represent values only
21

---

Learning Utilities from Demonstrations in MDPs
points in GP.r 1.15)
uprr. 8
(0.5,0,0.5,0) OJT
00,09,,,0.111.
Thus, policy x is optimal under some utility U if and only if the values assigned by U to points in GP {0, (0,0.5, 1, 1.5)
(denoted, respectively, by U², ,U,,U" U4) satisfy:
UT UTipirs P).. [0.5, 0.9, 0.5, 0.1]U 0.50 - 0.90 0.50 - 0.10 > 0,
where we have overloaded the notation and denoted with = [U', U both the utility and the vector of values assigned to points in GP. By imposing normalization constraints (U(0) = 0, (2) = 2), we get ( = 0, and by imposing also the monotonicity constraints, we get that utility U in the feasible set p. if and only if:
U² 50 30-- 0 ~
Clearly, both utilities U1, U2 satisfy these constraints, thus they belong to the feasible set 2 P.r.R. Now, concerning problem M', the performances of TT क w.r.t. utilities U1, U2 are:
JR (UBDDTT') = (U1(0) (0.5 + 0U1(1) + (.551 1.6/2 0.8,
(UU;)))))) 00) + 0U; + 0.903 (1.() 0.9 0.9 0.81, Js (UZDrT') OU>(0) 0.502 0U2(1) + 0.55 1.6/2 0.8,
(UUZPTT) - 0.1U5(0) + (0.5) + 0.9U2(1) (U.(155) 0.9 x 0.8 0.72.
Clearly, J (UI:.r) J(U::,,r"), but J (U2:p.r) JUUUpp, r"), thus we conclude that the set of policies induced by utilities U1, U2 in M' do not intersect, since they start from Sinit with different actions I1 (U,)(())) II p.r. (U2) () This concludes the proof with an example that satisfies Gr. = GP.".
we want an example that does not satisfy GP. = gPV, then we can consider exactly the same example with M and M', but using ri (Simi, a2) 0.001. In this manner, we see that Gar (0,0.5, 1, 1.5), and gv'"" r {0.001, 0.5, 1.001, 1.5), which are different. Nevertheless, by choosing Ui, U/2
0
if G
0
if
0.001
if G 0.001
0.001
if 0.001
0.1
G = 0.5
0.1
if = 0.5
(G)
GG
0.9
ifG
0.8
if G
0.901
if 1.001
0.801
if 1.001
1.5
if = 1.5
1.5
if 1.5
it can be shown that U1, U/2 still belong to the feasible set of A (the constraints are the same), and that induce different policies M'. This concludes the proof.
Proposition 4.3. There exists an MDP M = (S,A, so. r) and a policy F for which there are utilities U1, U2 Up.ra. such that, for any c 3 O smaller than some universal constant, there exists policy ne such that J (U:ppr)
J (U1:p.r) and J (U2.p. J (U2:p.r) 1.
Proof. Consider simple MDP M (S H. Sint p. with four states S {smit: $1, 82, 83). three actions A
(a1, 02 a3), horizon H 2, initial state Sinits transition model p such that:
(82l Sinit; a1) 1,
Pr (81 |iinis a3)
0.91
if =
Pi (8' Sinits a2)
0.09
if 83
22

---

Learning Utilities from Demonstrations in MDPs
d1 02
81
a3
a
41 02: dg
start
Sinit
$2
v.91
02
41. 02.
0.09
Figure MDP proof Proposition 4.3.
and reward function r that assigns rı (Sinits a1) = ri (Siiit: Q2) = T1 (iiit 03) = 0, and:
0 if s = A (a
02 03)
r2(5,a)
0.5 if 82 A (a 01 a 02 03)
if 5 53 (a a1 02 (3)
Note that the support of the return function GaD {0, 0.5, 1}. We are given an expert's policy πF that prescribes action a1 stage in state Sinit, and arbitrary actions in other states (the specific action relevant). The MDP M represented in Figure 8.
Now, we show that the utilities U1, U2 It defined in points of the support Gp. as (and connected in arbitrary continuous strictly-increasing manner between these points):
0
if G 0
0
if
U1(
0.1
if 0.5,
U2(G)
1.099
if = 0.5
0.1/0.09
if G =
1.1
if =
belong to the feasible E. and that, for any E E [0,0.1] there exists a policy π for which holds both that (UU;p, (UU:p,
and J* J (UU;;p
First, let us show that both U1, U2 belong to the feasible utility set. Let L ,,, be the policies that play, respectively, action a1, 03 in state Sinit (note that π = T.). Then, their performances for arbitrary utility U are:
J (U:p,r) U(0.5),
J" (U:p.r) 0.09U(1) + 0.91U = 0.09U((),
J= (U:p,r) = U(0)= = 0,
where we have used the normalization condition. Replacing U with U1. get JUUUp, J= (Uiipr)) = (Ujip,)) = 0.1 > J= (Un;p,)) = 0. Instead, replacing with U2. we get (* = J (UZiP.T) 1.099 > _² 1= (U2:P, 0.09 x 1.1 - fr (Uz:p,r)= = 0. Therefore, both U1, U2 E Upr.a.
Now, for any a e [o, 1] let us denote by та the policy that, at state Smmt plays action dg w.p. a, and action 02 w.p. 1 1 a. We show that, for any E [0.0.1], policy T./0.1 eoptimal for utility U1. and its suboptimality is at least under utility U2. For any E [0, 1], the expected utilities of policy aa under Un and U2 are:
=T (U1:..)) (1 a) x 0.09 UT (1) (1 (1-a) a) 0.1,
(T (1 a) x 0.09 (2(1) (1 (1-a) 0.099,
from which we derive that the suboptimalities of such policy under U1 and U2 are:
- (U-rp))))) = 0.1 (1 a) 0.1 = 0. 0.1o,
- -T 1.099 (1 a) 0.099 + 0.099a.
23

---

Learning Utilities from Demonstrations in MDPs
41 02
81
d1
start
Sinit
4g.
41 02 dg
$2
Figure 9. MDP for the proof of Proposition 4.4.
Thus, for any e 0.1,, policy T//0.1 is c-optimll for utility U1. but it is at least 1-suboptimal for utility U2.
The intuition is that utilities U/ and U2 assess in completely different manners the policies that play action 02 although they both describe policy T as optimal. This concludes the proof.
Proposition 4.4. There exists an MDP M = (S, s..p.) and a policy nº for which there exists a pair of utilities U1. U2 E Up such that der (U1, U2) =
Proof. Consider a simple MDP M (S, H, Smitt p. r) with three states S = {iiitt $1, 82), three actions A 2, initial state Simits transition model p such that:
{a1, 02 az), horizon
(1181/Smma a1) 1, pr (82 Sinit, 02) pi (1 Sinits 02) 1,
and reward function that assigns T1 (Sinits a1) = ri (Sinit 02) = O, ri ( a2) and:
0 if
(a v
03)
r2(
1 if s = $2 A (a = a1 va - 02 03)
Note that the support of the return function is Gp. {0, 1, We are given an expert's policy T that prescribes action ag at stage in state Sinits and arbitrary actions in the other states (the specific action is not relevant). The MDP M is represented in Figure 9.
Consider two utilities U1, U2 that take on the following values in GP::;
if G
GG)
0.1
ifG = 1,
if
ifG =
U2(G)=
1.1
ifG
2
if
is immediate that both utilities belong to the feasible set Upr.E. Nevertheless, if we denote by रे the policy that plays action d2 in state Siits we see that (U;;)) 0.1, while J (U2:;, 1.1, so that the difference
Proposition 4.5. Let S,A,H H be any state space, action space, and horizon, satisfying S and let U eil be any utility. If. for any possible dynamics 80.p and reward r, we are given the set of all the deterministic optimal policies of the corresponding RS-MDP S.A.HH,so.p.o U.., F), then we can uniquely identify U.F.
Proof. We provide a constructive proof that shows which values of so, p. sufficient to choose for recovering U exactly. The construction is articulated into two parts. First, we aim to recover the value of U recover the utility for all other possible values of return. The intuition is that construct Standard Gamble (SG) between two policies over the entire horizon (Wakker, 2010).
B (1), i.e., for G 1; next,
To infer U (1), we use the so, p, values that provide the MDP described in Figure 10.
We consider a single initial state Smit- From here, action a₁ (and all actions other than 01 and 02) brings deterministically to state s7. while action 02 brings to state sg w.p. q (to choose, for some q [0, 1]), and state 8 w.p. q. From
24

---

Learning Utilities from Demonstrations in MDPs
h
h
2
h
3
h
H
$7
3
H
Q1
start
Sinit
2
3
22
022
$3
3
$3
H
Figure 10. MDP for the proof of Proposition 4.5.
state s², for any i E [3]. all actions bring deterministically to state s² and on, up to state s. We will call the trajectory (Sinit, 87 2 s ,....,,,.. #f) .f } the 7th trajectory for all i E [3]. and we will write G(i) to denote the sum of rewards along such trajectory. To infer the value (1), we select a reward r' S A x [M] the first trajectory, return G(2) to the second trajectory, and return G(3) H to the third trajectory (this is possible because H > 2). By selecting, successively, all the values of q E [0. 1], we are asking to the expert to play either action 01 or action 02 from the initial state Sma (we denote policies n², , =², respectively, the policies that play actions 01, 02 in 8ma). Since are assuming that the expert will demonstrate all the possible deterministic optimal policies, there exists a value [o, 1] for which the expert demonstrates both policies IT' and x². Indeed, the expected utilities of policies ' 2² for arbitrary value of are (we write p(q) the generic transition model):
[0, 1] that provides return G(1) 1.5 to
J UB (1.5), (10)++11100) ( (H) + (1- (1-9) B = qH + (1 (1),
and since U is strictly-inereasing, we have (1) < (1.5) < ( H, thus there must exist y' that permits to write E (1.5) as a convex combination of the other two. This allows us to write:
U (1.5) = H (1 (1-9') (1).
(11)
Next, we select reward ," that provides returns G(1) 1, G(2) = 0.5, G(3) = 1.5. Thus, there must exist a q" [0, 1]
for which the expert demonstrates both policies - and 2², allowing us to write:
(1) U (1.5) + (1- (
(12)
Finally, we can repeat the same step with third reward "M that provides returns G(1) 0.5, G(2) = 0, G(3) = 1, and for some q"" e [0, we obtain:
B = ( B
(13)
By putting together Eq. (11), Eq. (12), and Eq. (13), we can retrieve U (1):
(L.5) (1= (= = (11 (B(00)) (1)
+
Now that we know (1), infer the utility for all the returns G (1, H) by choosing reward that provides returns G(1) G. G(2) 1, G(3) H. because for some q [0. 1] the expert will play both policies x! and 7?, which allows us to write:
T
9H B)
25

---

Learning Utilities from Demonstrations in MDPs
and to retrieve (T). Similarly, for all G (0, 1), select reward that provides returns G(1) G, G(2) 0, G(3) 1, and for some
e [0, 1] we can write:
U -
and retrieve U (G).
This concludes the proof. As final remark, we stress that the initial step for inferring (1) cannot dropped because there is reward S A [M] [0, 1] that provides returns G(2) 0 and G(3) H, because both the first and second trajectories pass through action d2 in state Smit-
E. Additional Results and Proofs for Section 5
This appendix is divided in parts. First, we show the complexity of implementing operator Il (Appendix E.1). In Appendix E.2, we provide the pseudocode, along with a description, of algorithms EXP LORE, PLANNING, ERD, and ROLLOUT. In Appendix E.3 we analyze the time and space complexities CATY-UL and TRACTOR-URE Appendix E,4, we provide the proof Theorem 5.1. In Appendix E.5, we provide the proof of Theorem 5.2.
E.1. Projecting onto the Set of Discretized Utilities
Let us use the square brackets explicitly as:
] to denote the components of vectors. Then, note that set I, can be represented more
I = =
Up Uli 1] Vie [d - 1]
A Vi.j [d]] s.t. j | UDI Mú - i)eo}-
(14)
Notice that set dr is closed and convex, since defined by linear constraints only. The amount of constraints scales as ocd2.
We remark that in Theorem 5.2 we assume availability of oracle for computing the projection exactly. In practice, can use any quadratic programming solver to approximate the projection.
E.2. Missing Algorithms and Sub-routines
EXPLORE In Algorithm 3, report the pseudo-code implementing subroutine EXPLORE, Simply put, adopt uniform-sampling strategy, i.e., we collect [r/(SAH) samples from each S [H] triple, that we use to compute the empirical estimate of the transition model. We return such estimate.
PLANNING The PLANNING sub-routine (Algorithm 4) takes in input a utility U, an environment index i, and a transition 2,,7,U) U). Notice that My * .Myys for aspects. First, it uses the input transition model p p²: next, it consider the discretized reward 5² * r²; finally, has input utility U * F.
model p. that uses construct the RS-MDP My (8 AA', HI, s (6,,,7",
PLANNING outputs two items. The optimal performance J*UU:p. rt) for RS-MDP Mu. and the optimal policy ** (vb)), n. for the enlarged state space MDP e[Mur. However, it should be remarked that, instead of computing optimal policy 8 for e[Mu] only at pairs (s,y) E x GP. for all h E [H], 2 PLNNINNG computes the optimal policy 3* at all pairs (8, y) E Vi, for all E [H] (note that 9 V.).
The algorithm implemented in PLANNING for computing both (U(Upp,r") and s is value iteration. The difference from common implementations of value iterations lies in the presence of an additional variable in the state. A similar pseudocode is provided in Algorithm I of Wu & Xu (2023).
ERD (Estimate the Return Distribution) The ERD sub-routine (Algorithm 5) takes in input a dataset D = (we)) of state-action trajectories wj E Ω and reward function r, and computes an estimate of the return distribution w.r.t.
26

---

Learning Utilities from Demonstrations in MDPs
Algorithm EXPLORE
Input: samples budget 7
[T/(S
for i (1, N) do
// Initialize the transition model estimate:
())) for all hs, E x [4] 8
// Collect samples:
for as, E S x [H] do
26
for E (1,2..... m) do
pt sample from (+),,a)
27
{) - [)
28
29
end
30
end
31
[,,[-s, a) - (-)(ss,))/n
end
33
Return (7)
Algorithm 4 PLANNING
Input: utility U, environment index transition model p
// Initialize the Q and value function at the last stage: for (s,9) E St V' do
34
35
for a A do
36
(n(s,y,a) + Uly + (s)
37
end
38
VH(s. v)
max QH (s, y. aЕλ
39
(n arg max (1( aEA'
/* Keep just one action +/
end
// Backward induction:
41
for h = H 1....,2. 2, do
42
for (8, E St x V%. do
43
for a A do
44
Qn (8, y. a)
Eg -ps Vn+ils'.y (8))))
45
end
46
Vi((,8) max (n a) aeA
47
(n(s.y) arg max (,) AEA
/* Keep just one action +/
48
end
49
end
// Return optimal performance and policy:
Return (s 0),
For every trajectory Wy e DE, ERD computes the return G, of wj based on the input reward (Line 55). In the next lines, ERD simply computes the categorical projection of the mixture of Dirac deltas:
Projec (>
1
where the categorical projection operator Proje is defined Eq. (8).
ROLLOUT ROLLOUT (Algorithm 6) takes in input a Markovian policy v/ a transition model p. a reward r, an environment index and a number of trajectories K, to construct the MDP M == (S",At 4 H, sb.p.1)) obtained from MDP M by
27

---

Learning Utilities from Demonstrations in MDPs
Algorithm 5 ERD Estimate the Return Distribution
Input: datasct D reward r
// Initialize î:
for y e 3 do
77y) - 53 end
52
// Loop over all trajectorics in D for w E D do
54
// Compute return of (si, 01.... 8H, an, 8841):
- E En- (a an)
55
// Update cstimate î
G & 0 then
57
f](0) - ()(
58
end
59
else if G 1. lea then
- # (oo) lco +
end
62
63
max veG? y
64
- minyey 223
65
Í(L) - Í(L) + U-T
G-G
?(U)= - ?(U) + G-L
66
U-L
67
end
end
Normal ize:
69
7
70
Return ?
replacing the dynamics and reward pi, r with the input p,
ROLLOUT collects K trajectories by playing policy vb in M for K times, computes the return G of each trajectory, and then returns a dataset DD containing these K returns. In other words, with abuse of notation, we say that the outputted dataset kejk obtained by collecting K samples G2 from distribution sp......
E.3. Time and Space Complexities
The time and space complexities of the subroutines are:
EXP LORE: time O(Nr) for collecting samples from the N environments; space -0 for storing the estimates of the transition model of the environments.
ERD: time = 0 ( H//)) for computing the return of each trajectory demontrated by the expert and initializing
estimate of the return distribution; space o (H)) to store estimate of the return distribution.
PLANNING: time = =($ for doing backward induction in the enlarged discretized MDP; space
(sAHH//c)) to store Q-function in the enlarged discretized MDP.
ROLLOUT: time O (KH) for simulating K trajectories long H; space = O(K) for storing the returns of the K trajectories.
Using these complexities, we derive the complexities of CATY-UL and TRACTOR-UL as:
CATY-UL: time = O(NT + MN (HT + AA1122/ /c0 ) for calling EXPLORE once and then both ERD and
PLANNING MN times, where M denotes the number of input utilities which CATY-UL is applied; space
28

---

Learning Utilities from Demonstrations in MDPs
Algorithm ROLLOUT
Input: policy tb. transition model p. reward r, environment index number trajectories K 71
() // Loop over the number of tra tratoroisssss for _E (1,2...... K]do do
for sb y
/ y keeps track of the accumulated reward x/
73
to H
74
a - (n,
75
y + an)
76
8 where o' ~ Ph (-1s,a)
77
end
D {0)
79
end
Return D
( SAHN + SAHf2/0)) where the dominant terms are for storing a transition model in EXPLORE and a Q-function in PLANNING.
TRACTOR-UL: time ONN NT++ NH, + T AH + NKH + Qtime)) )) for calling EXPLORE once, ERD AHf
N times, both PLANNING and ROLLOUT TN times, and executing T times the Fuclidean projection onto IL using optimization solver (Qrime represents this term); space O H/Hoco + SAH3/co + K + Qspace) for storing the N estimates of return distributions, for calling PLANNING and ROLLOUT, and for executing some optimization solver for Euclidean projection (Qspace represents this term).
Observe that the time and space complexities of the proposed algorithms are polynomial in the amount of data (r, r in the number of environments (N), and in the size of the environments (S, A, H).. Moreover, both CATY-UL and TRACTOR-UL. have time complexities that grow linearly in the number of runs (resp. M and T), and note that the complexity of TRACTOR-UL grows linearly also in the number of simulated trajectories (K) and in the complexity of the optimiza- tion solver used for the Euclidean projection (Qrime). Observe that the complexities depend on 1/co, where co 0 the discretization parameter.
From theoretical perspective, if we want that, with probability at least 1 8, the outputs of CATY-UL and TRACTOR-UL are c-accurate, then, under the assumption that the output of the optimization solver adopted for the Euclidean pro-
jection is exact, Theorems 5.1 and 5.2 show that it suffices to take c - ((2/(HN3)) F o Ö( log log }).
K & Ö N2 log !)). for obtaining a time and space complexity for the algorithms that grow polynomially in S, A, H. N. 1 e log 3, Quiee Qspace.
c² & Ö S (s + log :)) T & 0 N
E.4. Analysis of CATY-UL
Theorem 5.1. Let L 0, d (0, 1), and let U S Mr be the set of utilities classify. For all i [N] in case [2|| 1. let the number of samples satisfy:
8 N2 0(N2I log ) + δ
N
SAUNL log bc
2
Otherwise, U > let the number of samples satisfy:
INL log de
e
(5)
Ö( N2SAH
SAHN
(s+ sog
log
Then, setting to 2 e/(T2HT2N2) w.p. at least 1 for any > 0, CATY-UL correctly classifies all the U E U lying inside Us- outside Us+e-
Proof. Observe that the classification carried out by CATY-UL complies with the statement the theorem as long as we
29

---

8 N Learning Utilities from Demonstrations in MDPs
can demonstrate that:
IP (7
sup Uell
Σ N
C (t, Σ M
(UU E
2 1 8
where IP (L. represents the joint probability distribution induced by the exploration phase of CATY-UL and the exccution of each π F, in the corresponding M'
We can rewrite this expression as:
Σ (p' 1s|
Σ {(U)
& sup Σ (p -())
sup Veld
Veld
[c[N]
(I)
sup
Ueld
where at (1) we have upper bounded the maximum of a sum with the sum of the maxima. This shows that we can obtain the result as long as we can demonstrate that, for all i E [N]] it holds that:
sup Vell
pr - (U) -U)- &
)>
C 2
(15)
the statement of the theorem would then follow from union bound. Therefore, let us omit the index for simplicity, and let us try obtain the bound in Eq. (15). We can write:
sup B s (U) - ē(U))= = sup Uel
(U:p.r) 1
Vell
(2)
J
- + sup
sup Ueet
Ueu
sup
E
[U(G)] E [U(G]
Uell Gompina
E
[U + sup -U Bell
<
sup Uell Gom
E
[U(G))
E
[U(G)
(p
+ sup Uell
E
[U - E [U]]]]
sup (U:p,)))) - Veld
(5)
E f: is L-Lipschitz G-ypern
sup
[f(G)]
[f(G]]
G-Prij (
+ sup Uell
[U(G]]
[U(]]]
G-Pmic ()) 8
G
(U: - j*((i)
+ sup Uell
(6)
wi P.r, Proje(ppenat) ))
sup Ueul (
E
[U(G]] - E [UG]]]
G
- [.(),
sup well
where (2) have applied triangle inequality, (3) the definition of J (U:p, r),, and that of [E( (Line 4 of CATY-UL), and we have added and subtracted a term, where operator Proje is defined in Eq. (8). We remark that distribution p.na" I
may have a support that grows exponentially H. while both GE and (ppin"") are supported on
30

---

Learning Utilities from Demonstrations in MDPs
V. Note that ff and (n are different distributions, since the former is the projection on y of estimate of pp..... At (4), we apply triangle inequality, at (5) we use the hypothesis that all utilities are L-Lipschitz U = L,,, and notice that Ug is a subset of all L-Lipschitz functions f : [0, H] - [0, H]. and at (6) we apply the duality formula for the I-Wasserstein distance w1 (see Eq. (6.3) in Chapter of Villani (2008)).
Concerning the case [u] 1, we apply, for all i [N]] Lemma E.3 with probability 6/(2N) and accuracy e/(3N), and Lemma E.5 with probability 6/(2N) and accuracy c/(3)), while we bound the 1-Wasserstein distance through Lemma E.1, to obtain, through an application of the union bound, that:
P
sup Uell
Σ [[[M]
ppt pi E (U) Σ
(M
i[[N]
NLV/2He + c/3 + NH + t/33 > =1
as long as, for all e [N]
N2 log 0
B. δ
22
SHH
SAHN
log
62
deo
By setting 72HL2N3, we obtain that:
2
NL / + NHL 6 72LN c/3.
By putting this bound into the bound on T¹ we get the result.
When /f is arbitrary subset of M1, apply, for all e [N]] Lemma E.4 with probability 8/(2N) and accuracy c/(3N), and Lemma E.13 with probability 6/(2.N and accuracy e/(3N), while we bound the 1-Wasserstein distance through Lemma 1.1, to obtain, through an application of the union bound, that:
Σ [[[N]
Cpi M. (U) - Σ
P (
sup Uel
[E[
NL 2HE + e/3 + NH + +e/3) > =1
as long as, for all ie [N]:
N2113 HN Deo
E δ
log
::c
+/ Ö SHS (S log
SAHN
8
Again, by setting 60 N2, obtain that:
2
2
NI 2HE 2H + NH 6 72LN 8/3
By putting this bound into the bounds on T i and T', we get the result.
1. LEMMAS ON THE EXPERT'S S RETURN DISTRIBUTION
Lemma E.1. Let the projection operator Proje be defined as in Eq. (8), over set y with discretization Then, for all i E [N], it holds that:
Wi (1pp se E. PPojjc(1 ('aa")))))) & 2HH
31

---

Learning Utilities from Demonstrations in MDPs
Proof. For the sake of simplicity, we omit index i e [M], but the following derivation can be applied to all the N demon- strations.
By applying Lemma 5.2 of Rowland et al. (2024), replacing term 1/(1 -7) with horizon H, we get:
wi "nppirs"" Proje(1p )) & V (ne Proje( ))
Similarly the proof of Proposition 3 of Rowland et al. (2018), write:
Byprisrr Prrojc
=
(1)
(F Papinee Evy)
= (v))) dy
H
(2)
(F (pmmeii (v) Pro k()))) (v)) (dy
Us+1
(3)
(pperoa (V) F Proje (y))
c=[d-11
H1
(F Fpprns(() Projec( (y)
9511
Σ
(F (pmennt (v) (r (11) + t
je[d-1] 11 M/
Uiti
(F (Foe.rs (V(+2) - F Eppinot (y))) + co
V/
Σ
- Wi+1-1;1(6 (epiiin (15+1) F pe E (1,)) co
je(d
60
Σ
(F
Eppornt (V5+1) - F Epp.nn 5 (1;))² + co
]c[d-1]
Σ
(F gpmin (15+1) - F Pmperne (u;)) + 60
ED
je[d-1]
(8)
Eo Ep (yd) F Empinnt (31))² Eo
(F
200,
where at (1) we have applied the definition of 82 distance (Eq. (7)), at (2) we recognize that the two distribu- tions 1pp.r.= (T are defined on [0, HJ. at (3) we use the additivity property of the integral, using notation y = {0, cu. 2c...... |H/c (c],, (cu), d |V| |H/col + 1, 91 = 0.32 y22 == co. V/s == 2c....., Dd |H/colco. (nota- tion introduced in Section 5). At (4) we upper bound $ (F ( (z) - (op (v)) < SH dy = H ya = H -oo/colco cc(H//o
/col) < co since the difference of cumulative distribution functions bounded by 1. At (5), thanks the definition of the projection operator Proje (Eq. (8)), we notice that, for y [y, 11+1]. it holds that "n (v) E [ .. (uj), F ...... (1)- thus we can upper bound the integrand through the maximum, constant, difference of cumulative distribution functions. At (6) we use the definition of set V, i.c., an co-coveingg of the [o, H interval, at (7) we use the Cauchy-Schie Schwarz's inequality (x,,)) EE,,,) for x.j > O, and noticed that the summands are always non-negative, at (8) we apply telescoping argument.
The result follows by taking the square root of both sides.
Lemma E.2. Let i E [N], and let f E H be an arbitrary d-dimensional vector. Denote by G1, Gz..., Gre. iid. up of E. the random variables representing the returns of the TB, trajectories inside dataset DE.., Let B, be the random output of Algorithum 5 that depends on the random variables G1, G,E...,,G.... Then, it holds that:
[
= E P (ypt (.,... [f()]]
B Gr..Gr GRR, oe Ri
E By-gr
32

---

Learning Utilities from Demonstrations in MDPs
Proof. We omit index for simplicity, but the proof can be carried out for all i e [M] independently. To prove the statement, use the notation described in Appendix E.2 for the Dirac delta, to provide explicit representation of both the distribution (n F and the "random" distribution n"
We consider distribution up:.,. supported on 2 == {21, 22, ................................ : = L0, HJ, while distributions (rojc( ). ) are supported on set y' = (3/1, ................................ Va) = [0, H].
W.r.t. distribution (Toje(1p we can write:
Proje Proje(np = Proje
Σ nprro E (2a)0a))
ke M 1y m (rojc(o))
(
ke [M]
(2)
Pir.
(zx) (0 1/2k & v13 + 80a 12k > yal
ke [
Σ
Vj+1 2k 85 + 2k y) 60sts) 112x E (15, (o1l1)+)1))
yj+1 - Yj
1/+1 - yj
je[ 1]
= =ōy1
Σ
np 1 (#x)
2k 1(zx E well) 112x < v1 + y2 -
kM[M
y22
Σ
Σ Tppirt
(2x) y/5+1 2k 1|2x E (v 11+
Mj+1 y/
d-2.....dd-)
ke[ad
2k Vj 1
1(2k (U)-1.
y: y--
6 ga
Σ mpnnn Me[M]
(2x) (1(2x (1/22
> yal
2k yd-1 ( (ya-1, vall)
yd yd-1
where at (1) we have applied the extension in Eq. (9) of the projection operator Proje to finite mixtures of Dirac distribu- tions, and at (2) we have applied its definition (Eq. (8)).
Concerning distribution n², based on Algorithm 5, we can write:
6gg
Σ
(I(Ge & vn +
V2- G₁ [ (v1, (ul.)2l)) )
T
y2 y1
tel
Σ
yi
yj+1 Gi 1(G E (1111)+1))
E
Ui+1 y!
1E 1-1)
1]
G. リ
11 (Gr E (リj (uj-1.
V1
8 8ya
[1[G, > yal + G. G.-yaa -d-y 1 e (Ma-1, (ud)).)))))
Σ
Dd 1d-1
[e[r=]
Now, if we take the expectation of the random vector क. w.r.t. ppnn. we get:
E E Gr... wemprinet
8y E
Σ
(IIG, < vni++ V2 -2- G e (2))
-B B...Caa....eepppp Geeppine
[e[=a]
1/-91
G2
Σ
1 IG: E 1113
E
Vj+1
jE(2
LEI[T "I
G2 y
1 (G E (u5-1,
y/1 リ
33

---

Learning Utilities from Demonstrations in MDPs
Oyd E
G. Md-1 1|G, E (ua=1,
Σ
[1 > ya) +
[5|r5]
yd yd-1
1
8yg
[IG & vn)
V/2 G
[ E (21,
1/2
b0 [bt+1 G
Σ
1 (yi, Us+1l)
9j+1 yj
Vj
1|G e (yj-1, vil))
4/-1
+ 6yg
11G > yal + Yd yd-1
yd-1
IG E (yd- 1. Mal))
py
Σ
ppiris (zx) 1 11 $ v1
V/ 112x (3/1, 8211
ke[l]
1/2
1/
Σ
Ou Σ apona (2x)
[oj+1 "h 1fz (3/ V[++1}
Yj+1
yi
jE (2.......
ke[l]
11zx (U9-1.
5/ Uj-1
+ 6ys
Σ
24 - ya-1 pir (Ex) (1)6 yd) +
(2x E (ul-),
Vd-1
kE[M]
Proje (1) p.r.a
where (3) the fact that G1, G2...., G, independent and identically distributed, at (4) apply the linearity of the expectation, we notice that 6n does not depend on G for all E [d]] and we notice that, for any y e y it holds that Ba-mpnn R ( & v]] = vp 1 (G & y) EkE[M] 172 (zx) 1l (zk- & y), where we have abused notation by writing apoir (G & y) to mean the probability, under distribution 1p--. that event {G & v) happens. Moreover, similarly, we notice that, for any y 3/ y, it holds that B. |G. 1(G [v. ExE[M] zumpora (zx)1 v.. (5) simply recognize Projc(np using the previous expression.
This concludes the proof because the equality of the Dirac delta representations means that the expectations of any function w.r.t. these two distributions coincide.
Lemma E.3. Let i [N] and let 5 E (). If = 1, then, with probability at least 1 - 8, we have:
sup Uell
E
[U(G]]
E <c,
[U(G]]
G-REE
as long
2 log
E
where e is some positive constant.
Proof. Let be the only function inside U. Let us omit index for simplicity. Then, we can write:
E
[(G)]
E
[[G]]]
(
E
[UGG]]
E Grie
[
G-Proj (pp.a
G~GE
pper.a
(2)
log
cH
where at (1) we have applicd Lemma E.2, and at (2) we have applied the Hoeffding's inequality noticing that function bounded [0, MT, and denoting with e some positive constant.
34

---

Learning Utilities from Demonstrations in MDPs
By imposing:
log 2
cH &
and solving w.r.t 7", we get the result.
Lemma E.4. ie [N] and let e, ò (0, 1). Then, with probability least 8, we have:
sup Uell
[U(G]]
[UG
G-Pmie (mp' wepiie ee a E(i)
G-REE
as long as:
H
H
log
co
dco
Proof. Again, let us omit index for simplicity. First, for all possible functions U, we denote by U Iz the function Ig that takes on the values that the function assigns to the points of set set This permits us write:
sup Uau
E G-GE
[U(G]
[TG]]]
(m
sup Teil,
E G-GF
[TG
[G]]]
G-Pmic (1p...))))
sup
E G~
[U[G]]
EE
[U]
G-Proje ( pp.na
sup
E
[TGG]]
E Gm
[TG
Uejo.
G~+E
where at (1) we upper bound by considering all the possible vectors [0, HJJ, and at (2) we apply Lemma F.2.
Now, similarly the proof of Lemma 7.2 in Agarwal et al. (2021), we construct an e'-covering of set [o, HJ call it No. with Weel (1+ + 2//e'/e' such that, for all f [0, H] there exists f' We for which |[ f'll & é'. By applying union bound over all f' Nrr and Lemma E.3, we have that, with probability at least 6, for all f Ne,, it holds that:
d 211+2HVa
[f) -
E G~
[f
& cHH
(16)
G~
F
Next, for any fe E [0, HJd, denote its closest points (in 2-norm) from No. as f" Then, we have:
E
[f(G]] E
E GripE
[[]]]]]
G~i
E [[(]]]
E
E G~
[[G)
+
E
[M]]-- E E
Grie
mirr e
Gr
[()
E
[f
Grae
Gnie
[f(G) f')
E G~Gg
[f(G) [f(G)- [(]]
G~ie
2(1 2(1+2H
(4)
d dog
cH
E 2e
dlog
F 8
CH
35

---

Learning Utilities from Demonstrations in MDPs
where at (3) we apply triangle inequality, at (4) we apply the result in Eq. (16), and the fact that, by definition of c' covering |/ - 1 & e' entails that [l'v)) f(v')l E for all y E V) at (5) we set e' 1/7 and we simplify.
The result follows by upper bounding d H/ee + 1, and then by setting:
Hr H log Dea EaT
e" HHA
c,
(17)
and solving w.r.t 7", and noticing that for all R greater than some constant, we can get rid of the logarithmic terms in
E.4.2. LEMMAS ON THE OPTIMAL PERFORMANCE FOR SINGLE UTILITY
In this section, we will omit index i E [N] since the following derivations can be carried out for each i.
We denote the arbitrary MDP in {M*) as M = (S, H. 80 p)r, and its analogous with discretized reward 7, defined at all (s, a, h) E S x A x [H] as ra(s, a) == [T,[r a)). as M == (S, A, H. 80, r). We denote the analogous MDPs with empirical transition model p as M (S,A, H, 90 P. r) and M == (S,A, H. 80. r.
Given any utility U E Mr, we denote the corresponding RS-MDPs, respectively, as My, My, My. Concerning the discretized RS-MDPs My and My, we denote the corresponding enlarged state space MDPs, respectively, as e[Mc]] (ISx x Dn: A, H. (so. 0), p, t) and [[Mc]] ((S ),,,, H, (sg. 0), P. r), where we decided to define such enlarged state space MDPs using the state space {8 x Vahh considered by Algorithm (PLANNING) instead of, respectively, {S x "h hn and (S x g..F), Ja. Thus, the transition models P and p. from any E [H] and (s,y, a) E SS x Vn x A, assign to the next state (5'.y) E &S* x Va+1 the probability: p y, a) == pn (s Is, 1) = y + Fn a}} and y + Ta,s. a)}. Moreover, the reward function r, in any [H] and (s. y, a) S 8%2 A, is t. (8. 0f h H, and ta y, a) Uyy + (s, a)) if h H.
(s(s', s/s......... a) (s
We will make extensive use of notation for and Q- functions introduced in Appendix B.
We are now ready to proceed with the analysis. In general, the analysis shares similarities to that of Theorem 3 of Wu & Xu (2023), but we use results also from Azar et al. (2013) to obtain tighter bounds.
Lemma E.5. Let 8 E (0,1). 1). For any fixed L-Lipschitz utility function Mr, it suffices to execute CATY-UL with:
SAH
SAH
3
log
2
8cp
to obtain ( & HL + e w.p. 1-8. 6.
Proof. For an arbitrary utility U E ريg we can write:
- -*(U:p))) - (M()))
22
- ()p -+(())
2 [J*(U:p.)) - J r)) (p, (²((
HLee +
- r ((,
HLo + |V (Su. 0: - (st 0:
HLo
max hellW]
(*, p, - Q2(s, p.
(5)
Hé,
where (1) add and subtract the optimal expected utility in the enlarged MDP e|Mu] considered by Algorithm 4, but with the true transition model p. At (2) we apply triangle inequality, at (3) we recognize that the estimate j=(U) used
36

---

Learning Utilities from Demonstrations in MDPs
in CATY-UL and outputted by PLANNING (Algorithm 4) is the optimal expected utility for the discretized problem with estimated dynamics p, at (4) use Proposition 3 of Wu & Xu (2023), since U is I--Lipschitz, and at (5) apply Lemma E.6 to bound the distance between Q-functions.
By setting:
H log 4SAHd
log
168
3/4
log 165
cH2
71
6c/3
6t/3
<c/3
and solving w.r.t.
d 11 log 4BAHd
11 2 c H813 log
2 c Ha log 199AHe
Taking the largest bound, we get:
H log 16SAHA
n1 20 C
for some positive constant c. Since d & H/E0 + 1, we can write:
SAH log
e'SAH
2
for some positive constants c", where we used that T SAHn.
The proof of the following lemma is organized in many lemmas, and is based on the proof of Theorem I of Azar et al. (2013). Lemma E.6. For any e (0. 1). we have:
a (x. - a; <
max
w.p. at least where d' is defined as:
H log
4SAHd
log
16SAHd
3/4
log 168AHd
+ cH2
cH3
for some positive constant c.
Proof. We upper bound one side, and then the other. For all the he (s, E e 3h x A, it holds that:
H
E
Σ
Σ
(s an) - (oor))/vettte (s (..1:p.
P.c.p
k==h
8h
s, Uh = y. ah = a
H
Ci V (-l an (W Mee Me r)]
+ b2
P.r.U
Uh
= V. On =
37

---

Learning Utilities from Demonstrations in MDPs
H Ww LV (s', 9M+11 r)]
E
5, 3/h y,
P.r.y
b2
C1 v H +
Hb2
72
113 log 4SAHY
log
168 168 ANY
3/4
log 16SANY
H
c "H
72
72
where at (1) we have applied Lemma E.7, at (2) we have applied Lemma E.10 with 6/2 of probability, at (3) we have applied Lemma E.
The proof for the other side of inequality is completely analogous, and holds w.p. 8/2. The result follows through the application of union bound.
Lemma E.7. For any tuple h [H], (8, E Sxx x Vn A, it holds that:
H
ΣΣ
-
E
B
W'=
(pr(s)lsww an) (s ((r))s) V ( U..+
8n = 8, 4n = a
ΣΣ
(h(s, Q7(s,v,
E
pr.
(pn - (d (wx) (. 8n 8, = 4n = 0
where v/² x are the optimal policies respectively in problems t and p.r.
Proof. For any h E [H]. (8, a) 3n A. we can write:
o (s.y, of (s.8.
< o (s. (...,.ppr) - 2 (s.v.a;f..)
(, +
Σ
Pa(s', (.
(Exs))
- (In(s,8,,)) +
Σ
Σ
Pn(s (.s., (d..:/
(
Σ
Σ
Σ
(pa(s'.v/ss.,..))
P 0/ a) v.0 (s',
Σ
Pa(8', v. a) (i (8', p/: 1 (5''66))))
+
38

---

Learning Utilities from Demonstrations in MDPs
E
((l = =
- ( +N(s,)) = 3/3) / (/..)
Σ
a) (Vitza (itt2(ol.//:pp.. p': u
+
(+' (1)
(5)
Σ
Ph (5'(s,))
Dn (1) Σ 11y+7)(8,0) (s'.
Σ
(..'..0lss, a) ( V v/pp.t) (s)
+
(
Σ (pn(5'1s,a) (1,6) - in (s'1ss,
(1) V (6., vN (n(s.a);p.t)
E'ES
+
Σ
Pa(s
Vi v/: (
= Σ (o(()1ssa)) - (s'1 a)) V (8, .y (tt (s(.)):pp
SES
Σ Dn(s'.8/1s,3.4
(E (0%+1 (............... (...iss../)...... r) -ht v/, Whe v' (5..(.../):..))))
where at (1) we have used that &* is the optimal policy in P, and thus 0% (p, < O8" (s, p.. At (2) we apply the Bellman equation, at (3) we add and subtract the expected under p optimal value function under p. at (4) we use the definition of transition model p. p. at (5) we split the summations, at (6) we recognize that the indicator function takes on value 1 only when y + (T.ss, a) = y/. Finally, we unfold the recursion to obtain the result.
Concerning the second equation, for any E [M], v.) E ES Vn A, we can write:
Q% (s. v)
2h (s. - Qn (s,
(n + Σ
(1n())).a) +
Σ
Pald'. bal.vulan
(8)
Σ
Σ
(
Σ
= Σ
- (po(6,blls...0)pppcC a) v (s'.
+ Σ
pa(d'. a) (Viti v/..)) (
Σ
(pal6(s..000l)++assss)) =
-0i(6"),,))1( = v') 1
39

---

Learning Utilities from Demonstrations in MDPs
Σ
Pn(s',B/ss y. a) ( ( v (
+
(5) (s..0)S kitt
= Σ (p - - Σ + =
SEE
Du(s'.J/ls.y..)) a) Vh (ttp///////pp/)) (s' (1
Σ
Σ
- 1+ ()(,,)):)
S'ES
Σ
Pa(d', (V ( (.
(9)
Σ (pnlslls,)) (s'ls,,, a)) ( ( Fa(s,))pp.)
S'ES
Σ
+
(
(0it2 (5', v. Ph (d..) - Q (S.. 16.
where at (7) we have applied the Bellman equation, at (8) we have added and subtracted term, and at (9) we have used that vr A+1 (8', p) = Q (s', 3/, 1h p)) > Qh (s', y/, (s', y p. r), since w (s', y²) is the optimal action under p, v, and so, it cannot be worse than action ( 1.66..l v/). By unfolding the recursion, we obtain the result.
Lemma E.8. For any ô E (0, w.p. at least 1 --,, 5, it holds that:
log AdA
(s. V/ (s.1: & cHP2
max (s.
log
A 8
Vi (s, cH2
max (-
where e is some positive constant.
Proof. First, we observe that, for any [H]] (s. e S Vh. by following passages similar to those in the proof of Lemma E.7:
(s. - V (s)):
=10% ((...)(( - 10"0x"""0 (.....((
Σ 11
- -(u(s...
Σ
Σ
Σ
Pa V.
(e (W))es8)aa11
Σ
(#' (
Σ
(pa(s v. v (s, PA v, Vni (8.11/p))))
40

---

Learning Utilities from Demonstrations in MDPs
Σ
Pn(s', alls,/ls,u v. v)) (V v'',,/ - (s',
(pa(d'ls, (s)))) - Pn(s')s, (. Vi y o S'ES
Σ
Σ
Pa Vl (. (Vitz (1/2///////pp.)) v (d..
11
Σ
Σ
- Dn-(d'low, (((sswaa))) i (h:,,)+1:p,,)
E
p.r.))*
e'eS
8/
8, 1/h = y/
H
Σ
Σ
(d'ss, anc) - P ax) Vs' yh -1,+1:p,))
E
p.t,
W/=h
8/2 = s, 1/h = 1/
where at (1) we have brought the absolute value inside the expectation.
Similarly, for the other term, for any h [M] (s, E E x Vn, we can write:
Vy r) Vi (s. (s.
1n (s, Vi (s,
m a;p,)) aeA
maxa (s.
asA
(3)
Qh *
(s..,)pp))) Q (s.
& max aEd
= max anA
In y, a) +
Σ
pn(s', p
- (s, +
Σ
Σ
Pa(s', D
max aEA
(v' (e'ss)
Σ
Σ M'SSS
Σ
(pals'.''ss - Pn 1s'.' 1's,,,,,,,,, a1) (s
max aEA
Σ
(1(6,1/18,8 (v (
+
Σ
v
Σ
pa(s',//o,,,0)) ( - vi
(s (81:4")Sxxxt++
Σ

---

Learning Utilities from Demonstrations in MDPs
Σ
llss, ( (t'. Vit ( vd'.
(sf ())))))))))
H
Σ s'eS
(no((s'sss, and ( (s'lsw, an)) V (6', we+1ip.))
E
8.c,1
h/ w/=h
Sh. =
where (2) have applied the Bellman optimality equation, at (3) we have upper bounded the difference of maxima with the maximum of the difference, (4) we denote the maximal action by a, and we apply triangle inequality; at (5) have unfolded the recursion and called y the resulting policy.
Now, for some e E (0, 1), let us denote by & the event defined as:
= 4h E [H], y. 5. 34h A
Σ
- a) Vati(s', (s' F {
E'ES
We can write:
PPEE) IP 3h E [H], (8, ES Vn A:
Σ
- - (itt::))))
Σ
he[ (
Σ
V ( -fn((,
=)()))))p.)))=))
Σ
2e 22ne2
de -2nc2
where (6) we have applied a union bound over all tuples h [H], (s, E S Vh A, and at (7) we have applied
Hoeffding's inequality, by recalling that we collect samples (see Algorithm 3) for any (s, a, h) S A [H] triple, and that vector V ( (s, a): p, t) bounded by [0, H] is independent of the randomness in pr (-Is, a). It should be
remarked that our collection of samples depends only on S x A x [H], and not on Vn; such term enters the expression only through the union bound, because we have to apply Hoeffding's inequality for all the value functions considered, which are as many as [) Note that we use Di++1 since is the largest [)% among h [ 1].
This probability is at most 8 if:
28 log
AS
-2ne? H2
< 5
H1
8
2n
By plugging into the previous expressions, we obtain that, w.p. 1 8:
(s.y:p.r))
(s)
Σ
Σ S
(pro
D an)) Vitt1os (8', +1p,);
E
P.c.
42

---

Learning Utilities from Demonstrations in MDPs
M/
log
25 AHA
E
H
6
= 3/h
P.r.
2n
log
2
112
2n
and also:
VV (8,
(8,
Σ
Σ
(o'sss - ( (s'1s0r, and) Vo Me++;p.t)
<
E
P.
s'eS
8h.
Vhh
log 25AHd 6
<
E
H
yh =
2n
P.E.V
log 25AHd
H
2n
This concludes the proof.
Lemma E.9. For any (0, 1). w.p. at least 6, it holds that, for all h [H] (s. E S Vn x A:
Ve-pa(le, [ ( ra(s
V Ve--pattb.
bb,
V (0 &
(1l,,))
V Vv [V Fn (s r)] b1.
where bj is defined as:
(108
log
4SAHY
1/4
log
45AHY n
b, = cH
+ d H
n
for some positive constants e,
Proof. In the following, we will use y as a label for y + Fs(s a). We begin with the first expression. We can write, for any E (s, Dr, A:
Va (1, V (s', T.p. r)]
V Va (1) V (s' J. (h (s. r)
VV-ppa Vi+ TTP. V (s.T..p)))
+ V. (V p.
Σ
VAi
43

---

Learning Utilities from Demonstrations in MDPs
[( (u E'ES
Pa(s (1l SE
V , po
Σ
(i
xEES
Ph Ph 18 (a 2
SEE
Pn(s' V (... 1 + +V.~pa(laa) (5, [T:
Σ EE
+ V V
1 (s', (s', (s:.
+2Cov 1 (S', V (8. D. t).,,
V v/)
Σ 8'ES
(n((slss,a) a) - - a) V 1''i(s'':::) r.
e'ES
(6. '
SES
W (s.
+ V ( p.
+ VV (s', p.
+ (
r.
V (s', [.)))
V N)-p((191 1 (1. 1/2
Σ -)) (s'
EES
[[ ( ?
SES
Σ (1(6 ' S
Vi U:,,) V (s,,y:p.r)]
a' V
+V V. WV (s', J. r)]
where at (1) we have used the common formula for the variance -[X]= E[ at (2) we have decomposed the variance of sum as V[X + YJ= = V[X]= + V[Y]+ + 2Cov| yJ. at (3) we have applied Cauchy-Schwar's inequality to bound the covariance with the product of the variances |Cov[X, Y1 & /V[[xVVTY]
Next, observe that:
V "e-ma a.) V Vi t.P,)) - Vi (=..
44) E Eg (11e,))) [VV++1( (8', y:p.t) (s ( (.: =
44

---

Learning Utilities from Demonstrations in MDPs
Eg (
vu
4+1 (s', ".
(5)
< E Bx (6' 33 r) - ( y. e))
(6)
<
[1(V (s V: r) W (s U:P 100
| U. r) V ( yi &))
where at (4) we have used V[X] = E[x E[X]². (5) we recognize that the second term is square, thus always positive, and we remove it, and at (6) we have upper bounded the expected value, an average, through the infinity norm.
Thanks to this expression, we can continue to upper bound the previous term as:
(1 V (5', r)p
( (s,a) - ba( Vitral'' (s...)
3'ES
S'ES
Σ (s'. '1 SES
( Vi (s v: r)llx
v (Ve-patlaa) (..
Σ ( - - (it SES
-I(E -
Σ + fn'l's
a)) [
(5 (d.
SES
+ [IVE V (1 r)
SES
[( Σ (pm(5')s, -n -.16:::0000m1111110000011111111
s'es
(pn(s'|s,a) ()) (
S'ES
+ [cI2
4SAHd log
8
Verpaale (s', J. P. c)] 2
n
- - (s.
SE
+ 2H
- v.p..)
F'S
log 1SAHd
(H22
+
n
(10)
Σ
- -fn()),,,) Vii
S
45

---

Learning Utilities from Demonstrations in MDPs
4SAHd log 5
+ 2cH2
log 4SAHd 6
+ cH1
V - (1s,a) MV (8', Ir P. F)]]]]
(II)
log 4SAHd
log 4SAHA
& ccH2
+2cH2
1SAHA log 6
+
cH2
V (- 15', T: P.P. r)]
log 1SAHd 6
3cH²
4SAHd log 6
cH2
+ V V (a V h+i (8', us P. ri]
where at (7) we have applied the common formula x² - probability 8' = 8/2, and noticing that, for how the discretized MDP is constructed, we have that y V. at (9) we have upper bounded the second term with the absolute value and recognized that the value function does not exceed H and the sum of probabilities no greater than 2; at (10) we recognize that, in the proof Lemma E.8, we had already bounded that term, thus, under the event & which holds w.p. 5/2, we have that bound: at (11) we have applied Hoeffding's inequality all tuples h E [H] (s. y, a) E S Vn x with probability 8/(2SAAd)). and noticed that the square of the value function does not exceed 112
y) + y), at (8) we have applied Lemma E,8 using
Observe that the previous formula holds for all h E [M] v, 8 x 3h x A w.p. 1- 8 (by summing the two 8/2 through a union bound). By taking the square root of both sides, we obtain:
o' /pppp (x-p(-11..) VV
h+1 (s', (ss.v:PP.) v.)
log ASAHA 5
log 4SAHd
< 3cH22
+ CH2
P) 1/2
V ( h4i (s', Ms P. r)]
(12)
log ASAHY
log 4SAHY
+ cH2
à
=bb
V. pa(taa) V . T. t)]
V. - Vint (s', D. S, r) + b,
where at (12) we have used the fact that Va + & va + Vb.
To prove the second formula, the passages are basically the same, the only difference that, at passage (1), we sum and subtract 4 (s', 37 t) instead of h/+1 (8', T7: p, t), and that at passage (8) apply the other expression in Lemma E.8. This concludes the proof.
Lemma E. For any 8 (0, 1), define:
2SAHd
= log
log 8SAHd
log
8SAHd 5
by == cH
e 2
46

---

Learning Utilities from Demonstrations in MDPs
for some positive constants C, d. Then, w.p. least 8, we have, for all h [H], (s,,,a) E 8x Pn x A:
Σ e'E8
(p Da(s'ls, Vi+ 7
a aV ( h4 h+1 (s', (s,
&
V
+ b2.
n
Σ e'ES
Da - V h+ Fh (..
r
c V V- dm
62.
n
for some positive constants ce".
Proof. Again, we will write y instead of y Fr,ss a) for simplicity, For all h (s. S Vh A, we can write:
Σ
Ph (8'18, (/) (n( V (s'.
S'ES
24 5' s' LV h+1 D', log ASAHd
2H log 25AHd
n
3n
2 log 28AHd
(VVo-pactta V M.P.P... RJ] + bi)
2H log
28AHd
n
3n
c1 V
h+1 (S'.T.P,.))
log
88 ASAH 6
1/4
H1
log SSAHA
C1 2
c.d H C1
+ c"
C1 V (..00) Vhit
(s',
J: r)
r)
log
85AHd 8
3/4
+ C" H log SSAHd 5
<c
c' H'H
where at (1) we have applied the Bernstein's 's inequality using 6/(2SHHd) as probability for all h [H] S x yn x A, and at (2) we have applied Lemma E.9 with 8/2 of probability, and a union bound to guarantee the event to hold w.p. 1 - 8, at (3) we use the definition of c == log 8
2SAHd and denoted by c, c," c some positive constants.
For the other expression, an analogous derivation can be carried out. In particular, we use the other side of the Bernstein's inequality, and the other expression in Lemma F.9.
Lemma E.11. For any h = [H], (s, a) e S Yn x A and deterministic policy v.. let Ex (8, y, a) be defined as:
(8, = E
uw(ss anc - (x, a; 1 = 8,9h = y. ag a Σ
p.r.o
Then, function Σ satisfies the Bellman equation, i.e., for any h E (s,,,)) x Yi x A and deterministic policy th:
(), = =V V (11,)) h+1 (s' ,
+
E s1-pa(-)).a)
E h+ 1 ( (,, th th (s(s
Proof. For all h E [H] vs, E S 2hh x A and deterministic policy di we can write (we denote a' = Wh+1(s', Ta(8, a)) and y y Fs(s a) for notational simplicity, and we remark that is not a random variable):
(3, =
(sr Whs, awr) (8, Σ
8, 2h y. on a
P.r.sh N
47

---

Learning Utilitics from Demonstrations in MDPs
H (ww Ber, an) 18 D..)
E
E
of p' (-l,s,
Pir,sh
(Q% (s, p.
Qh h+1 (
y. pp
y. 8h+1 = o
8/ = 8, Un
a, yh
H
R
E
Σ
The (swe, yv,, an) - Q (5', (d....'....ppp.
(-1sn
pit,
-=+++1
- (Q (+, a; a; t) - (,, - (d..
8ht1 = 8' 1hhh1 T
H
E s'-ph,(-ss,a
E
Σ
The yw., ax) - -f..
pit,v
h1=
|/h+1 = =s',8h++1 T
(QX -) - "',i''',,,'''p..
2
E
of s'mph (1s,a)
Σ
Uh' aw) 1h+1 (s', a' p..) 8h41 5 11++111 y
P.c.0
M=h+1
-0
[0f(s...apptt-<(((ss va(s,v.a) "5.'.p''
s s-pa (1s,a)
s'>pk( (-18,a]
Σ
(1o,,,9,,an)) (6', (6',,,'''s 1841 81,
p.r.o W=
(.. - vn(s,8,a)) -n - ( d')
+
E Pa (1),,a)
VV VVrnpt (4
IV 1 (s..)))))
E (s', J. (s + V (1 V (s', U)P,t)],
E o 8' P.p.-lle (1),,)
at (1) we add and subtract term, at (2) we bring out the non-random reward received at h, at (3) we compute the square and use the linearity of expectation, at (4) we use the fact that Ep.c.v Σø= (ww, Bhr, ax) - Qh (s', T. a.:' 8h+1
s'} Q (s', D. a. +%+ (s', T. d': p. 0 because of linearity of expectation.
Lemma E. Let up be any policy, and let p be any transition model associated to an arbitrary inner dynamics p. Then, for all h [H], (8, y. a) Yn A, it holds that:
V Ve (8',
(S. 9141:p,t) 8h 8. y, Un a HVH H
P.T.V
Proof. For all h [H] (8 E 8 Vn x A. we can write (note that this derivation independent of p. P. so we might
48

---

Learning Utilities from Demonstrations in MDPs
use even P. f in the proof):
H
V pp (ww. [V WW
W M. r)]l sh. s, yh y.
p.t.t
H
E
H
V - (1ow))
VV N41 (8', 11 8/ = 8, yh = y, On = a
P.
H
E
V Par (1bbnriw VWh (,',,''',,,, M/+1:P r)]l 8h = 8, Uh = y, ab = a
p.r,
h--h
H
E
E s// yrr,aw) Bx- + (s', th++1 i yw++1))
p.t,
1/2
y/ ah a
8h
8, 8,
H1
V H
E
En (sw, yhe aw) - Σd + +1, a1++1] 8h. = 8, yh
= y, ag =
A
H
E
2 (ohs yh, an) - 2141180411 U1T+,,, 88 8, Uh = ah = a
p.r,sh
H V
2% (8.
15)
H² H
H
where at (1) we have applied the Sauchy-Schwarz's inequality, at (2) we have applied Jensen's inequality, at (3) we have applied Lemma E.11, at (4) we have used telescoping, and at (5) we have bounded [x & H² for all h [A], (8, y, a) e x yn x A.
E.4.3. LEMMAS ON THE OPTIMAL PERFORMANCE FOR MULTIPLE UTILITIES
To prove the following results, we will make use of the notation introduced in the previous section. Lemma E.13. Lei e, 8 E (0, It suffices to execute CATY-UL with:
T = Ö SAH$
(S + log
SAH 5
2
to obtain suptrest, (((U:,))-++(()) < HLep + w.p. 1- 6.
-
Proof. Similarly to the proof of Lemma E.13, can write:
sup (J*(Upp.r) J+((I)
Ueilz
-
- -+((()
sup
Ueitz.
& sup
- (
sup (p. r) St(U))
Veiti.
Dell.
sup [JM(Upp,r)- - (p, +
sup (p, J((
Uellz
Ueilz
& HToo + sup - (p)
-
Uell..
49

---

Learning Utilities from Demonstrations in MDPs
2
SAH
HTao + H22
log n
(S- 1) log (e(1 + +n/(5- 111)
< Heo t
where at (1) we have applied the formula in Lemma E. 14. By enforcing such quantity to be smaller than e, we get:
SAH
2
log
+ (S - 1) log (e(1 + n/(S- - 11)) <
6
2 log (e(1 n/(S 1]))
2 1og SAH
+ (S - 11) &
V
4
SAH
+ (S ( 1)) log (e(1 + n/(S - 1)))
n >
log
8
By summing over all (s,a,h) E S x xx x [H]] and by applying Lemma J.3 of Lazzati et al. (2024b), we obtain that:
SAH (SHH Iog 5 + 8))
T SAHn 3 ò
Lemma E.14. For any 8 (0, (0,1),for for all utility functions U E Mg at the same time, we have:
SAH
-N & H2 log 8
+ (S - log (e(1 n/(5 -1)))
w.p. at least 1 1 8.
Proof. Let us denote by& E the event defined as:
Vn :
N, vh ()) S Vn A:
nKL (KL & log + (S 1) log (e(1 + n/(5 111}
SAH
We can write:
P(E P in E N, 3h (s, Sx Vn. x A:
SAH
(s (lp.a log 8
+ (S log (c(1 n/(S - 1)))
@ P In N. ((s. [
SAH
()s > log 8
+ -S- (1-1))oo (c(1 n/(S - 11))
Σ
P Bnn (Il
(
SAH
(S - 1) log (e(1 + +n((S ())()((1))))
log
Σ
SAH
(
8,
50

---

Learning Utilities from Demonstrations in MDPs
where (1) realize that there no dependence on variable y, thus we can drop it," (2) we have applied union bound over all triples (s, a, h) 8 A [H] and at (3) we have applied Proposition of Jonsson et al. (2020).
Next, for all utilities U M, at the same time, for all the tuples h E [[] (s. v) E S x Vn. we can write:
[V (s. t) - (s.
Σ
Σ
(sr(s' (sw, Pe (s aw) (5'1ss, V W Me++ip,,
P,R,1
h/- h
SiES
a
8h
8, Vb
y. an
(5)
H
11
E
Ipw Ipw (-1ss,, awd (oai--Pnee -Nr(-1sw, ax) s/ 8.81 y,
P.F.V
W=h
(6) H
E
v (pw (-1sw.
8h = s. y/ y. on
1/ -==h
SAH
H
E
log
+ (S 1) (e(1 + n/(S 1)))
P.r.v
Rh=h
8h 9,
y: On a
H12
2 V
log 8
SAH
+ (S 1) log (e(1+ n/(S 1))))
where at (4) we apply the formula derived in the proof of Lemma E.8 and triangle inequality, (5) we have upper bounded with the 1-norm, defined | == Σz [f()), (6) we have applied Pinsker's inequality, at (7) assume that concentration event E holds.
We remark that the guarantee provided by this theorem holds not only for L-Lipschitz utilities, but for all functions with the same dimensionality (since it is a bound in 1-norm).
E.5. Analysis of TRACTOR-UL
Theorem 5.2. Let L > O, e E (0,1), and U E bh Assume that the projection operator 1I, is implemented exactly.
Let the number of samples satisfy Eq. (5). There exist values of co, K, a, Uo (see Appendix E.5) such that, if we run TRACTOR-UL for a number of gradient iterations:
T T2O(N=HA1)/)))
then, w.p. at least 1 1- 5, any utility Mr such that Uty) = (v) Vy y belongs to Ud.
Proof. The proof draws inspiration from those of Syed & Schapire (2007) and Schlaginhaufen & Kamgarpour (2024). Given any distribution y) supported on V, and given any two utilities U My U E b1 (where U is a function [0, H] and U is vector })), we will abuse notation and write both UT and U n, with obvious meaning.
Moreover, for L > 0, we define operator Ey I, - 24h.. (where 2 denotes the power set of set X) that, given vector T e Ir, returns the set (T) = {U dt Vy e y: U(v) = (v)}.
First of all, we observe that the guarantee provided by the theorem follows directly by the following expression:
IP M MA
sup (E) ME[M
E. Cp < > 1- 8,
'Therefore, differently from the event for a single utility, now there is no dependence on d in the bound. Intuitively, d appeared in the case of a single utility because we had to apply Hoeffding's 's inequality d times, because we had, potentially, d different value functions (as many as the states). Since now we provide the bound for all the possible value functions (1-norm bound), then the dependence d disappears.
51

---

SAHN 5 Learning Utilities from Demonstrations in MDPs
where PM',, .M. denotes the joint probability distribution obtained by the N MDPs (M',,
Let us denote by Ō = U Ut) the output of TRACTOR-UL. Note that i E Lye We can write:
sup Σ (0), ie[N]
( sup Σ - J= (U: UEC,,(U) [E[
sup Σ
+a1
(U) sc[M]
(
sup (eCn(U) Ne[N]
Σ
max
U n (TG +
nEDI
-nn + c1
sup
max neD: t=0
T
(To)
[
(T-1EEZ(UT--))
max U. - - nED:
U + +
sup
T
L
[N[
W3
Th nE. )
min +
T :it (iB
+ + +
DELL
N
t=0 M
2HN H/co
Σ T
T sBp)) + + +2t
DEL
vT
[N[
W
(Tt s)B.i) - + - ( +a+eta
N
W3
Σ
mi Bu - + 201 + 62 +3
[
Σ
Σ
UB
,p (pp +26, + E2 +3
pp'ir'
N
40
(1)
2el + e2 + E3 64,
where at (1) we apply the definition of (non)compatibility, at (2) we first upper bound the supremum of sum with the sum
H log NH. E.i
of the supremum, and then we apply Lemma 1.15 w.p. 6/3, and denote 61 := 2 + Σ cHA
Beg cg7 E,
at (3)
ic[N]
denote by Dj the set of possible return distributions in enviromment i, (4) we the definition of Ú, and realize that all functions U (Ū) can be constructed based on T functions Un E (U,) UT-1 E CT(UT-1). At (5) we upper bound the maximum of the sum with the sum of maxima, and exchange the two summations, and we add and subtract the dot product between the (discretized) utility U, and the estimate of the return distribution computed at Line 15; moreover, we bring the sup inside the summation. At (6) we upper bound the supremum of the sum with the sum of the supremum, and
we apply Lemma 16 w.p. 8/3, defining <2 == eNH2 V 1 log
+ (S 1) log (e(1 + n/(S (/(s-1))) 1))) H +
CHNN log NT
and we add and subtract term, at (7) we apply Theorem H.2 from Schlaginhaufen & Kamgarpour (2024)
since set H is closed and convex, where D := max ex ITU 1'122 vd 2H / H HH/co
52

---

Learning Utilities from Demonstrations in MDPs
(recall that consider increasing and not strietly-increasing utilities). 10 and maxueL, V EiENND U T" 1 [N Tit f < IN I + |1 2N G (because ni and ff are probability distributions), with learning rate = D/(GGT) = H 222-2/(2NVT) =
VT), at (8) we upper bound the minimum over utilities with a specific choice of utility, U², and we add and subtract a term; note that U E را corresponds to the expert's utility U it, (by hypothesis), i.e., for all y E V Th (v) U (y). Note that, by hypothesis, U makes all the expert policies optimal, i.., vi E [M] op ,',="". = sup, TT .².,,, At (9) we note that, under the good event of Lemma E.15, we can provide an upper bound using the term Lemma E.15 (since U E 42)); in addition, we sum and subtract a term that depends on some policy Tj. whose existence guaranteed by Lemma E.17, which we apply the next step. At (10) we apply Lemma E.17 w.p. 8/3, and we define as c the upper bound times N. Finally, (11) we use the hypothesis that utility E makes the expert policy optimal in all environments.
We want that 2e, + E2 + Eg 64 E. We can rewrite the sum as:
2e1 + + 63 + 64
3
LN + HNVH
= (2NLV 2HE +
VEOT
H log NH
log NT
d Σ HN
BED ET
+ CNNHA
K
NH d
(
1
log
SAHN 8
+ (S - 1) log (e(1 + n/(S - (1)))
n
By imposing each term smaller than c/5, find that it suffices that
60
8ON-
N
T 3
caE2
7 EK Ō
HHN log
Sen
H* loR NHL
NEL
Vie [N]
ege
K δ
N log
NT
No H2 log 22
22
r' δ
N²SAH
(5 log
SAHN
[ie
where we have used that 7 = SAHn for all e [N], and also used Lemma J.3 of Lazzati et al. (2024b).
The statement of the theorem follows through the application a union bound.
Lemma E.15. Let ō (0, 1). Then, it holds that, w.p. at least - 5:
H log N.
sup Σ DELL NN
UTgBI - _ F (U:p'rr) &
Σ cH [E[N]
+
where c is some positive constant.
Proof. We can make the same derivation as in the proof of Theorem 5.1 to upper bound the objective with the sum of two terms, which can then be bounded using Lemma E.1 and the expression (Eq. (17)) obtained in the proof of Lemma E.4 w.p. 6/N:
sup Σ Uest, iE[N
UTTES J _
(U:D,))))))
< L
Σ
(1p2 B. Proje (1pe (e
xe Ke[N]
The maximum is attained by discretized utilities D, T that assign, respectively, U(y) and T (v) y e 3 VM va).
53

---

Learning Utilities from Demonstrations in MDPs
+
sup [ U' D'e(o, G- G-Proje mi
R
1 [G)]
E GaRei
U
(G)
H log 81r dea EO
Σ cHV ie[N]
<
The result follows through the application of the union bound.
Lemma E.16. Let ò e (0, 1). With probability at least 1 - for all tE (0.1....., - - for all i [N], it holds that:
max Uln Ul & clf? V ( log nED;
SAHN
+ (S - 1) log (e(1 n/(S nn1+ -1)))
sup (U,)
log NT
+ HLc + H
K
where c, d are some positive constants.
Proof. We use the notation in Section 5. In particular, let policy a, be the optimal policy in the RS-MDP M = AS, H, sh: P i,,,)).
Jst --U))))))U,;))
where the last passage holds trivially for all U, E (U,) (because there is no evaluation of utility outside )).
Thus, for all E {0, ,,..,, T 13, we have:
sup max U. n - U. (T. nED;
- F3) U. ,p
sup (U,)
1 LL clt2 V
(log
log 5
SAHN
+ +(S - 1) log (e(1+ nn(S S 1)))
+ U7
M
(3)
1 /
(log log SAHN
HTeo cHP²
+(S -S- 1) log (e(1 + nn((S 1)))
5
log NT
+ c H
5
K
where at (1) we have applied the triangle inequality, and realized that in the second term there is no dependence on the value of utility outside of V; moreover, we have used that J (Ut; p', (D= U. r' by definition of policy #; At (2) we apply Lemma 13 (our J (U:: ".r"" r') has the same meaning of J (U) in the lemma, and we upper bound suPu,ee, with supvess)) ) w.p. 6/(2N)," !! and we keep the confidence bound explicit, and we upper bound d & H/eo + 1, and at (3) we observe that πi is the empirical estimate of distribution 178* xr ... (see Line 15) obtained through the sampling of K sample returns G1, G2...., GK iid. 17 #* Indeed, note that the policy G computed at Line 13 and optimal for e[M, = ((5) Vih,, A', H, $6. e)), provides policy म, through the formula in Section 2, thus Line 14 is actually simulating AM in MDP M.. Therefore, we can apply Hoeffding's inequality (e.g., see Lemma E.3) w.p. 8/(2TN).
We remark that, in doing so, we can still apply Proposition 3 of Wu & Xu (2023) inside the proof of Lemma E. even though we consider increasing utilities instead of strictly-iccreasinng utilities; indeed, it is trivial to observe that the proof of Proposition 3 of Wu & Xu (2023) does not depend on such property.
12eee Section 2 for the meaning of f$ and ri: we use Vi, for the state space instead the sets of partial returns (G mi "),
order to obtain policy v2. suppporedd on the entire 0% space, and make it compliant with Algorithm
54

---

Learning Utilities from Demonstrations in MDPs
The result follows through the application of the union bound.
We remark that in one case use probability 6/(2.V (without T') while in the other use 6/(2NNT) (with T', because in the former we provide a guarantee for all possible utilities w.r.t. the optimal performance, thus all the T steps are already included: instead, in the latter, we provide guarantee for single utility and for single policy at a specific t E (O..... T 1), thus we have to compute a union bound with T.
Lemma E.17. Let ō E (0,1) With probability at least 1 - 8, for all e [M] and L E (0,..., T - 1}, under the good event in Lemma E. 16, there exists a policy ni such that:
log NT
U T
U U.
B of < LHeo/2 + cHA
K
1
SAHN
e 12 V
log
+ (S log (e(1 n/(S 1)))
where c, d are positive constants.
Proof. First, simply observe that 9/ is the empirical estimate (see Line 15) of 17 """"""""" thus, similarly the proof of Lemma 1.16, for all i E [N] and LE 1........ T - 1}. we can apply Hoeffding's inequality w.p. 8/(2TN):
NT log 8
TB.T 1/ - 17 10'
&
cH
K
Now, we compare distributions 17 sr a' and 1ppl a Through straightforward passages, we can write:
110 F' as. - -pp .ppt
=|JRt (."; j (U" r')
Σ
pi(s'1sh को.
S'ES
(s':1
s'eS
Σ
(1 (1/6//16. (.) (.l1) 2(166 1 (6::),)))
SES
(s' 3t1 (d(p))))) V:a (5):p,,7))
e'eS
Σ (ph((o'low,anc)) - Phe (f/(w)/ v
E
8,1
81 8
H (-Iss,, -hh (-1s am)l 81 $6)
.H
E
E
2KL( P (-Isw, aw))
81
sú
where the last passage we applied the Pinsker's inequality. Note that the previous derivation was possible as long as policy -/' is defined over all the possible pairs state cumulative reward (s, y) e Sy for all h e [H]. Since we construct through policy c obtained Line 13, i.e., over the entire enlarged state space {S x )r then policy **. satsifies
55

---

Learning Utilities from Demonstrations in MDPs
such property. Now, in the proof of Lemma 1. we used Lemma E.14, in which event bounds the KL-divergence between transition models. Therefore, under the application of Lemma E.16, it holds that:
U ( "p
H2
2 V
log
SAHN 5
+ (S - 1) log (e(1 + n/(5 1)))
where n is the number of samples takes each (s, a, h)) S x A [M] in the [N] MDP. Therefore, we can finally write:
U B. o1 U Bi 1pp rt' x -U 1 10 5t
t U T p
U.T 1p2 Fr 17 up (
+ E.T 1p ,
1p
pp
+ U
E. (nt 188 F :1
())
UBB
(ppt.
+ cHA
NT log
b K
2
SAHN
+ +cH2,
V
log 8
+ +(S - 1) (e(1 + n/(S 1
NT log
LHEa/2 2 + =cHA
o K
2 + H V
SAHN
log
+ (S - 1) log (e(1 + n/(S -1)))
8
where (1) have used the bounds derived earlier, and at (2) we have applied Lemma E. noticing that we choose policy x' wish, and using that l & 6o/2.
Lemma E.18. Let Mi (S, H. so. r,) and M2 (S,A, So: p2)2) be two MDPs with deterministic rewards that differ only in the reward function r² + 12, and assume that, for all (8, h) E S x A [H], it holds that (1, a) rf, a)l & k. for some & 2 O. Let x² be an arbitrary (potentially con-Markovian) policy that induces, in M1. the distribution over returns up xx Then, there exists a policy n²2 that induces in M2 the distribution u s² such that:
E E (I [U(G)] - G [U(G] & Lilk.
sup Ueit,
Proof. A non-Markovian policy like n², in its most general form, prescribes actions at stages h [H] depending on the sequence of state-action-reward (s1, 01, T1, $2, d2, T2..... -h: Ph-11;7h-11 5%) received so far. Since, by hypothesis, the reward functions are deterministic (see also Section 2), then it is clear that the information contained in the rewards re- ceived so far (fr1, r2. 1) is already contained in the state-action pairs received ($1, 01, $2 .g..... Sh-1, (k)1, (#2, 02), and so on). This means that, for
(indeed, for deterministic reward r1, we have that /1 = ri (81, a1). any non-Markovian policy in the MDP Mj, since it coincides with M2 except for the deterministic reward function, is possible to construct a policy x² that induces the same distribution over state-action trajectories, i.e., for any state-action trajectory (81, 01, 82, 022 ..., 8H 0H-1- H HH 8 HH+1) Ω it holds TP p.rt ar (w) IP (w)))
Therefore, we can write:
sup Ueil,
E B [U[G)] - = [U(]]]]
(1) sup Ueil,
x (w)U
Σ r)((sa))
welt
(K,
Σ weft
IP x (w)
Σ r((s,a))
(s.a,))ew
56

---

Learning Utilities from Demonstrations in MDPs
sup U
Σ WEs?
(w) P pir x
Σ
r
(s,,,))ew
Σ wes
P Ppr xn (w)U
Σ
ri((,,a)
(s,,h))ew
Σ wel
P p.r x (w) (w)
Σ
rh(o, -U
Σ al()
sup Ueil,
(e,a,))ew
(s,a,N)ew
Par's x (W)
Σ ((B,a))-Us
Σ
r)(s,a))
sup
Uell, wel
(s,0,))ew
(s,a,A)Ew
(4)
P p.r mz (w)
Σ
(rh(s,a) - r((s,a)))
wEft
(x,a,h)ew
P p.r. pt (W)L wef
Σ
Σ
-((s,a)-r((s,00)
(J.0,)Jew
(6)
P pp ml (w)L
k
wEf
(s,0,))ew
LHk,
where at (1) use the fact that the expected utility w.r.t the distribution over returns can be computed using the probability distribution over state-action trajectories (since the rewards are deterministic), at (2) we use that policy x² is constructed exactly to match the distribution over state-action trajectories, at (3) we apply triangle inequality, at (4) we use the fact that all utilities U E Lr are I--Lipschitz, i.e., for all x, y E [o, H]: (U(x) - Ut) & L|x - yl. at (5) we apply again the triangle inequality, and at (6) we use the hypothesis that r! y² are close to each other by parameter k.
F. Experimental Details
In this appendix, we collect additional information about the experiments described in Section 6. Appendix F.1 presents formally the MDP used for the collection of the data along with the questions posed to the participants. Appendix F.2 contains additional details on Experiment 2. Finally, Appendix F.3 presents an additional experiment conducted on the collected data.
F.. Data Description
Below, we describe the data collected.
F.1.1. CONSIDERED MDP
The 15 participants analyzed in the study have been provided with complete access to the MDP in Figure 11, which we will denote by M. In other words, the participants know the transition model and the reward function of M everywhere.
Intuitively, states L (Low), M (Medium), H (High), and T (Top), represent 4 "levels" so that the received reward increases when playing actions in "higher" states instead of "lower" states. Formally, MDP M (S,A, H, so, P, has four states S = {L, M, H, T), and three actions for each state A = {ao. a_, The horizon is H = 5, i.c., the agent has to take 5 actions. The initial state is &g M. The transition model p is stationary, i.e., does not depend on the stage E [H]- Specifically, p is depicted in Table 1. The intuition is that action ag keeps the agent in the same state deterministically. while action a+ tries to bring the agent to the higher state with probability 1/3, and action a sometimes make the agent "fall down" the lower state with probability 1/5.
The reward function r S A x [H] R is deterministic, stationary, and depends only the state-action pair played. The specific values are depicted in Table 2. Note that we have written the reward values as numbers in [OC, 1000E), to provide a monetary interpretation. Nevertheless, we will rescale the interval to [0, 1] during the analysis for normalization. Observe that the same actions played in "higher" states (e.g., H or T) provide higher rewards than when played in "lower" states (c.g., L or M). Moreover, notice that action a+, which is the only action that tries to increase the state, does not provide reward at all, while the risky action a_, which sometimes decreases the state, always provides double the reward
57

---

Learning Utilities from Demonstrations in MDPs
h =
3
==
L
L
L
L
start
M
M
M
M
M
H
H
H
H
T
T
T
T
Figure 11. The MDP used for data collection.
M
H
T
(I,
0
0
(L,44)
2/3
1/3
0
(I,
0
0
(M)
1
aM,
2/3
1/3
0
(M,a)
1/5
4/5
0
(H)
0
(H,
0
2/3
1/3
(H
1/5
4/5
0
(T,
0
0
(T,a4)
0
(T,a
1/5
4/5
Table The transition model p of MDP M.
than "default" action ag-
H
00
30C
100C
500C
00
30
0E
a_
00
60C
200C
1000E
Table 2. The reward function of MDP M.
F.1.2. INTUITION BEHIND AGENTS BEHAVIOR
The reward is interpreted as money. Playing MDP M involves trade-off between playing action a4, which gives money but potentially allows to collect more money in the future (by reaching "higher" states), and action a., which provides the greatest amount of money immediately, but potentially reduces the amount of money which can be carned in the future. Action ag, being deterministie, provides a reference point, so that deterministically playing action ag for all the H stages gives to the agent 30 = 150E. Thus, playing actions a+, a_ other than ag means that the agent accepts some risk to try increase earnings.
58

---

Learning Utilities from Demonstrations in MDPs
1.1.3. QUESTIONS ASKED THE PARTICIPANTS
We remark that the participants have enough background knowledge understand the MDP described. To each participant, ask which action in (ag. a,, a_} it would play if in certain state stage h, with cumulative reward up to now y. for many different values of triples (s, h, v) S x [H] [OE, 5000E). Specifically, the values of triples s, h, y considered
are:
1,E)
(M)),0)
(M,),30E)
(M, 2, 60E)
2,E))
[M,3,00 0E)
(M,3,306
(M,3,606)
(M,3,2006)
(H,3, (E)
3,,3,306)
(H,3, (00E)
(H, 2000))
(T, 3,0)
(M, (, 4,00)
(M, 4, 30E))
(M, 4, 60E)
(M, 4, 90E)
(M, 4, 1200)
(M, 4, 180C)
(M, 3,30)))
(M, 4, 400C)
(H,4,0C)
(H,4,30C)
(H, 4, 60E)
(H, 4, 100
(H, 4, 1300)
2004)
(H,4,3006
(H, 4, 1000
(T, (T,4,0E)
(T, 4, 60E).
From state L, we assume all participants always play action 0+ since it is the only rational strategy. Moreover, from stage 5, we assume that all participants always play action a since, again, it is the only rational strategy.
In all other possible combinations of values of s, h, y. we "interpolate" by considering the action recommended by the participant in the closest y' y. in the same 8, h.
F.1.4. THE RETURN DISTRIBUTION OF THE PARTICIPANTS' POLICIES
We now present the return distribution of the policies prescribed by the participants. Specifically, we have simulated 10000 times the policies of the participants, and we have computed the empirical estimate of their return distributions. Such values are reported in Figures 12, 13, 14, 15, and 16, where we use notation 17, to denote the return distribution of participant i, with E [[5].
0.35
0.35
Probability n(G)
0.20
0.30
0.30
0.25
0.25
0.15
Probability
0.20
Probabilitg
0.20
0.10
0.15
0.15
0.10
0.10
0.05
0.05
0.05
0.00
0
Return G
Return G
Return G
Figure 12. Plot of "n .. and v/a
0.40
0.35
Probabiityy n(G)
0.35
0.30
Probability g(G)
n
0.30
0.25
0.25
Tobability
0.20
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0
0
2
Return G
Return G
Return G
Figure 13. Plot of th ng. and n
F.2. Details Experiment 2
Experiment 2 is made two parts, the first in which we execute TRACTOR-UL on the MDP (and data) adopted also in Experiment 1, and the other where we use simulated data. We describe here the former, while we present the latter more detail in Appendix F.2.3.
59

---

Learning Utilities from Demonstrations in MDPs
Probability A[G)
0.4
f
Probability g(G)
0.4
n
0.40
0.35
0.3
0.3
0.25
0.2
0.20
0.1
0.1
0.10
0.05
0.0
0.0
0.00
0
0
3
0
Return
Return G
Return G
Figure 14. Plot of nyF 78 and na.
0.35
Probabliity glG
0.30
nio
0.35
nta
0.30
niW
0.255
0.30
0.225
0.20
tobabliityooo
Probability
0.20
0.20
0.15
0.15
0.15
0.10
0.10
0.10
0.05
0.05
0.00
0.00
0.00
Return G
Return G
Return G
Pigure 15. Plot of vho Mii and viz-
0.35
Probability ((G)
0.30
1/3
Probability n(
0.4
nia
Probability [6
0.30
nf
0.25
0.3
0.25
0.20
0.20
0.15
0.2
0.15
0.10
0.10
0.1
0.05
0.05
0.00
0.0
0.00
0
1
0
Return
Return G
Return
Figure 16. Plot of mis, Mia. and vfs-
We consider the policy of the 10th participant (chosen arbitrarily) the survey, and we execute TRACTOR-UL multiple times with varying values of the input parameters, specifically: we always use K =10000 trajectories for estimating the return distribution of the 10th participant's policy, and the return distribution of the optimal policies computed along the way; we make 5 runs with each combination of parameters with different seeds. We execute for T' = 70 iterations using Lipschitz constant L = 10, which means that we consider only utilities U E II, satisfying (G) - U(G') & 10|G - G') for all G, G' e [0. 5] (the horizon 5). As initial utility Uo. we try Ungt Usquares and Unnear (see Appendix F.3), and as learning rates we try 0.01, 0.5, 5, 100, 1000, 10000.
The experiment has been conducted in some hours personal computer with processor AMD Ryzen 5 5500U with Radeon Graphics (2.10 GHz), with 8,00 GB of RAM.
We note that the choice of Uo is rather irrelevant for the shape of the extracted i, but it matters for its "location", as shown in Fig. 17.
To view the sequence of utilities extracted by TRACTOR-UL during the run, see Appendix F.2.1, while Appendix F.2.2 explain better why the best learning rate large.
F.2.1. THE SEQUENCE OF UTILITIES EXTRACTED BY TRACTOR-UL ON THE COLLECTED DATA
We now present some plots representing the sequence of utilities extracted by TRACTOR-UL. during its execution. Specif- ically, we consider initial utility Uo = U Usquare. and we use learning rates E [0.01, 0.5, 5, 100, 1000, 10000]. We plot the sequence of utilities considered by TRACTOR-UB during its execution in Figures 18, 19, and 20, where we adopt notation that U, denotes the utility extracted at iteration t, and the number in the legend represents the (non))copaatiiiliyy of that utility. We consider again participant 10.
60

---

Learning Utilities from Demonstrations in MDPs
Uspt
Usquere Unrast
Utiliyy U(G)
Figure 17. Utilities computed by TRACTOR-UU UL starting with the Uo in the legend (a 100).
We observe that, for smaller learning rates (e.g., a E [0.01, 0.), the utilities as well as the (non)compatibilities) do not change much (Figure 18 and Figure 19 left), while for larger learning rates, we obtain more consistent changes (Figure 19 left and Figure 20).
Clearly, larger learning rates require less iterations achieve small values of (non)compatibillttis, Nevertheless, too large values (e.g., 10000) are outperformed by intermediate values (e.g., 100).
Ug, 0.66
Uy, 0.26
Uzs. 0.25
Uze 0.2
Use, 0.17
0,25
0.16
Usitty U[G)
2
0
Return G
Return G
Figure 18. (Left) a = 0.01. (Right) = 0.5.
Ub,
Ug. 0.17
Us. 0.12
Ut. 0.16
Ug, 0.082
U,
Us.
Utility UIG)
Utilityy
1
Return
Return G
Figure 19. (Left) 5. (Right) 100.
61

---

Learning Utilities from Demonstrations in MDPs
Us. 0.26
Us. 0.26
U..
4
Ug. 0.12
U2. 0.18
Up. 0.086
U4. 0.14
Utility U(G)
Utility
Return G
Return G
Figure (Left) a 1000. (Right) a 10000.
F.2.2. AN EXPLANATION FOR LARGE LEARNING RATE
As mentioned in the main paper, there two reasons why large learning rate is required: (i) the feasible set is large and contains utilities that lie the boundaries of set Hg 13 causing larger step sizes to converge sooner; the projection onto Hr results in minimal changes of utility even with very large steps.
Now, we show visually that the projection update represented by operator Hl crucially neglects small variations in the (non-projected) utilities, requiring us to increase the step size.
Thus, the intuition is that we need a large learning rate because the projection step neglects small variations. To show this, we take as initial utility Uo Usm. two return distributions n/ ,/8,, where 1/ coincides with the distribution of an optimal policy for Usq, and T7 is the return distribution of the policy played by participant 10. These distributions are plotted in Figure 21 left, and their difference is plotted in Figure 21 right. In particular, we that the two distributions are rather different, with the expert's distribution 17 that is more rvsreeverse, in that it provides higher probability returns around G 0.5, while the optimal distribution V is more risk-lover, in that it assigns some probability to higher returns G > 1, but suffering from also high probability to small returns G & 0.3.
0.35
Difference ná (G))GG (fG
0.2
Probability n(G)
0.1
0.20
0.15
0.10
-0.2
0.05
Return
Return G
Figure 21. (Left) Plot of nh and th (Right) Plot of mp
We aim to perform the TRACTOR-UL update rule:
T U. - U-U0--(1p" - 1)
with some learning rate a, and then to perform the projection:
U 11 UT)
BN forces utilities be increasing, i.c., with constraints U(G1) & U(G2) UGG = U(2)) YG, & G2, G1, G2 E [1,3]. thus, represents boundary.
VG & G2. The plateau in Fig. 17 (right) indicates that
62

---

Learning Utilities from Demonstrations in MDPs
We execute the update with the following values of steps size: {0.01, 0.5,5, 5, 100, 1000, 10000), and plot the corresponding updated utilities Un and U in Figures 22, 23, and 24.
U;
U:
U
Utilty U(G)
Utility
Return
Figure 22, (Left) a 0.01. (Right) a 0.5.
U3
U
Utiliy UIG)
Utility
Return
Figure 23. (Left)) (Right) a 100.
Utilty VIG)
17
Return
Return G
Figure (Left) a 1000. (Right) a 10000.
As we can see from Figures 22, 23, and 24, the update Un Un obtained with step sizes < are rather neglectable, so that the return distribution of the new optimal policy 77 for U, still coincides with the previous one ne and the gradient the next step the same. For a we begin to notice some changes. See Figure 25.
Instead, with larger gradients, we observe non-neglectable change in utility, which provides consistent change in the return distribution for 100, and a huge change for a E [1000, 10000) (see Figure 26).
Since neglectable changes in both the utility and the optimal return distribution (obtained with small learning rates) mean that we have to update the utility many times along the same direction, then the update is equivalent to performing a single update in that direction with huge step size. This justifies the use of large learning rates.
63

---

Learning Utilities from Demonstrations in MDPs
ni.00.011
0.35
0.30
ng.am0.55
Probability ((o)
0.25
Probability (1
0.25
0.20
0.15
0.10
0.10
Return G
Return G
Figure 25. (Left) Comparison of the return distributions ni obtained with a = 0.01 and a = 0.5, with no (Right) Comparison of the return distribution 'n¹ obtained with vjñ
0.35
fi 10.0000
n.aam nam1000 n: 10-00000
Probability (())
Probability ((G]
0.20
0.15
0.10
Figure 26. (Left) Comparison of the return distribution n/ obtained with 100, with no (Right) Comparison of the return distribu- tions of obtained with 1000 and 10000, with n6-
F,2.3. ANALYSIS ON SIMULATED DATA
We have executed TRACTOR-UL on MDPs generated at random. Below (Figures 27-29), we report the truncated (non)compatibility values of utilities extracted by the algorithm as a function of the number of iterations, the five different experiments conducted. For the experiments, we executed for T 70 gradient iterations, with parameters K 10000 and 7. 10, in the first part of the experiment. We found that the best learning rate is 1.
To comply with the assumption that there exists utility function for which the expert's policy is (almost) optimal, we compute, in each environment, the optimal policy for an S-shaped utility function that is convex for small returns, and concave for large returns, and then we inject some noise.
0.40
conpoompaiiilty 2(0g)
0.35
Coonloomaabilltyyy 2(00)
0.35
0.30
0.25
0.20
0.20
Iteration
Iteration t
Figure 27. (Left) Simulation with 5 = 20 and A 5. (Right) Simulation with S = 100 and A = 10.
64

---

Learning Utilities from Demonstrations in MDPs
0.35
[Nonicompatbblity 2(0,)
0.40
[Nonicompatbllln) 7(0,)
0.35
0.30
0.25
0.25
0.20
0.20
Iteration
Iteration
Figure (Left) Simulation with S 1000 and 20. (Right) Simulation N
0.50
compatibiiiyt 2(00
0.40
0.35
0.30
0.20
2
Iteration
Figure 29. Simulation with 20.
E.3. Additional Experiment
We conducted additional experiment using the collected data to understand which utility is representative of all the participants' behaviors under the model of Eq. (I).
The utilities considered for comparison are: Usqit Usquare. Uninaars and Usa- The first three can be formally defined as: Usin(G) := v5G, Usquare (G) G² /5, (in)ar(G) G, and they are depicted in Figure 30, Instead, utility UsG differs from each participant and is defined in the next section.
F. STANDARD GAMBLE DATA
Utility UsG corresponds to the utility of each participant as fitted using the standard gamble method (Wakker, 2010).
Standard Gamble (SG). The Standard Gamble (SG) method (e-g., see Section 2.5 of (Wakker, 2010)) is common
method for inferring the von Geumann-Morgensteee (vNM) utility function of agent. Observe Figure 32. In a SG, the agent has to decide between two options: sure option (e.g., = 30E), in which the prize is obtained with probability 1, and lottery between two prizes (e.g., 5000 0E), in which the best prize (5000E) received with probability For any value of z, the agent has to answer what is the probability p that, from his perspective, makes the two options (i.c., æ for sure, or the lottery) indifferent.
Given the probability p. we have that the utility U of the agent for x is:
U(x) = p- (5000) + (1 - p) U(0) =
since, by normalization conditions, we have (7))) and (5000))
65

---

Learning Utilities from Demonstrations in MDPs
U(G) vVG
U(G) x
U(G)
Utility U(G)
Return
Pigure 30. A plot of utilities Ung: U Usqane, Utieear-
Utility U(6)
2ethoper:
2ethopen:
patioper:
nethoper:
pathopen:
patloppe::
puticipe::
Return
Figure The SG utilities the participants.
P
5000
O
Figure 32. The SG used for data collection.
Our SG. We have asked the 15 participants to the study to answer some SG questions, which allows us to fit a vNM utility function UsG for each of them. Specifically, we have asked to answer different SG questions, which the x value Figure 32 has been replaced by:
10E, 30E, 50E, 100E, 300E, 500E, 1000 2000
Next, we linearly interpolate the computed utilities, obtaining the functions in Figure 31.
It should be remarked that this model considers single decisions (i.e., H 1), while in MDPs there is sequence of decisions to be taken over time, specifically over certain time horizon H.
F.3.2, RESULTS
To measure the fitness of a utility U to the data (policy x) fairly, we consider a relative notion of (non)compatibility (we
omit p,7 r for simplicity): C2 (U) == (J*(U) - (FU))//J** Intuitively, č₁ (U) measures the quality π as perceived by the demonstrating agent, U was true utility function.
66

---

Learning Utilities from Demonstrations in MDPs
2
3
4
5
10
11
12
13
14
15
mean
U Jineer
39
58
56
16
28
Uug
16
28
8
1
3
16
11
30
25
6
8
11
28
13::10
U uqquee
70
86
88
28
45
UsG
39
76
11
0
5
28
20
34
10
2
21
17
51
22+-21
Table 3. Values of C, of various utilities with the demonstrations of the participants in percentage.
We execute CATY-UL (without exploration) for the 15 participants comparing the IRL. risk- utility Unnear with "baselines": A risk-averse Usn (concave) and a risk-lover Uqquare (convex) utilities, and the utility Usa fitted through the SG method (see Appendix F for details). We report the (non)compatibilttis in percentage in Table 3, where we have used colors to highlight the best and worst values for each participant (the last column contains the average over the participants),
Some observations are in order. First, this data shows that Unnear (i.e., IRL) is overcome by Usqn- which reduces (-(-) from 28% to 13% on the average the participants. Next, note that Usn outperforms the UsG of each participant. This is due to both the bounded rationality humans, who can not apply the
1 utility Usa to H > problems, and the fact that Uun probably "overfits" the simple MDP considered, but might generalize worse than UsG new environments. Finally, observe that all the utilities compatible with policies 4 and 11, providing empirical evidence the partial identifiability of the expert's utility from single demonstrations.
The experiment has been conducted on the same personal computer as experiment 2, in less than one hour.
The experiment has been conducted collecting 10000 trajectories to estimate the return distribution of each participant's policy, and 10000 trajectories for estimating the return distribution of the optimal policy, which has been computed exactly through value iteration. We have executed 5 simulations with different seeds, and the relative (non)compatibility values written Table are the average over the 5 simulations.
For the experiment, used the true transition model, and remark that the reward function considered, when discretized, coincides with itself, i.e., we did not incur in estimation error of the transition model nor in approximation error for the discretization.
Purrther analysis should be carried out this, we leave future works.
67


Reviews:
[{"review_id": "21VYn3aFTA", "reviewer": "Reviewer_HXF4", "summary": "The paper considers a specific type of risk-sensitive MDPs where the risk sensitivity is captured via a continuous, strictly increasing utility function. Given a set of optimal expert demonstrations and the expert reward, the aim is to recover the expert's utility function. The authors first provide a few impossibility results, showing that similar to the IRL, the utility learning problem is ill-posed in general. However, they show that if given access to all deterministic optimal policies under any transition kernel, we could identify the expert's utility function. Motivated by this observation, they provide two algorithms for learning from expert data collected in multiple environments: CATY-UL, a classification-based method to check the approximate compatibility of a given utility, and TRACTOR-UL, a more practical algorithm that outputs a single candidate utility, much like traditional IRL methods. Finally, the applicability of TRACTOR-UL is showcased on a tabular toy problem.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> 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.\n\nWe 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.\n\nAlso, 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.\n\n> 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.\n\nWe 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.\n\n> Typos: in line 197, 281, 381: contained into -> contained in\n\nWe thank the Reviewer for pointing out, we have fixed them.\n\n> 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?\n\nAnswering 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.\n\nConsider 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:\n$$\nr_h(s,a)=V_h(s)-\\sum\\limits_{s'\\in\\mathcal{S}}p_h(s'|s,a)\nV_{h+1}(s')+1\\\\{\\pi_h^E(s)=a\\\\}A_h(s,a).\\qquad (1)\n$$\nThus, 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:\n\n$$\n\\widehat{r}\\_h(s,a)=\\widehat{V}\\_h(s)-\\sum\\limits\\_{s'\\in\\mathcal{S}}\\widehat{p}\\_h(s'|s,a) \\widehat{V}\\_{h+1}(s')+1\\\\{\\widehat{\\pi}\\_h^E(s)=a\\\\}\\widehat{A}\\_h(s,a),\n$$\n\nthen it is possible to bound the Hausdorff distance in max norm by the 1-norm of the transition models:\n$$\n\\mathcal{H}(\\mathcal{R},\\widehat{\\mathcal{R}})\\le \\max_{s,a,h}\\\\|\\widehat{p}\\_h(\\cdot|s,a)-p_h(\\cdot|s,a)\\\\|_1, \n$$\n\nas 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.\n\nTo 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.\n\n[1] Ratliff, L. J. and Mazumdar, E. Inverse risk-sensitive reinforcement learning.\n\n[2] Metelli, A. M., Ramponi, G., Concetti, A., and Restelli, M. Provably efficient learning of transferable rewards.\n\n[3] Lindner, D., Krause, A., and Ramponi, G. Active exploration for inverse reinforcement learning.\n\n[4] Metelli, A. M., Lazzati, F., and Restelli, M. Towards theoretical understanding of inverse reinforcement learning.\n\n[5] Zhao, L., Wang, M., and Bai, Y. Is inverse reinforcement learning harder than standard reinforcement learning?", "claims_and_evidence": "Generally, the claims are clear, and complete proofs are provided in the appendix.", "methods_and_evaluation_criteria": "The problem definition, the algorithms, and the theoretical results are clearly presented and consistent.", "theoretical_claims": "I reviewed the proofs of Proposition 4.5 and Theorem 5.2, and they seemed to be sound.", "experimental_designs_or_analyses": "The experimental validation is limited to a toy problem, which may have limited practical relevance. Nevertheless, the results are well-documented, and the authors considered human expert data.", "relation_to_broader_scientific_literature": "While IRL in the risk-neutral setting has been addressed extensively, and some risk-sensitive approaches exist, the specific setting of identifying the utility given the reward seems to be novel.", "essential_references_not_discussed": "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.\n\n- Majumdar, Anirudha, et al. \"Risk-sensitive Inverse Reinforcement Learning via Coherent Risk Models.\" Robotics: science and systems. Vol. 16. 2017.\n- Chow, Yinlam. Risk-sensitive and data-driven sequential decision making. Diss. Stanford University, 2017.", "other_strengths_and_weaknesses": "Strengths: \n- The paper introduces an interesting problem setting by focusing on learning the utility function for a known reward.\n- The theoretical contribution providing both identifiability results and convergence guarantees is solid.\n\nWeaknesses: \n- 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.", "other_comments_or_suggestions": "Typos: in line 197, 281, 381: contained into -> contained in", "questions_for_authors": "When learning from a single environment, Theorem 5.2 basically guarantees that for the recovered utility, the expert is $\\varepsilon$ optimal. Is it possible to also say something in terms of Hausdorff distance to the set of feasible utilities?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wpp0poPS2B", "reviewer": "Reviewer_ZJB5", "summary": "The paper introduces a new risk-sensitive model for inverse reinforcement learning  in MDPs, explicitly accounting for the non-Markovian policies induced by risk-sensitive utility functions. The main contributions include formulating the Utility Learning problem to learn an agent's risk attitude, characterizing its partial identifiability, and proposing two algorithms, CATY-UL and TRACTOR-UL, for efficient utility learning from finite demonstrations. The authors validate their methods through theoretical analysis and proof-of-concept experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> On the comparison with literature.\n\nWe 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.\n\n> On the empirical validation.\n\nThe 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.\n\nIn 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.\n\n> On the notation.\n\nWe 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.\n\n> On the computational complexity.\n\nFor the subroutines:\n\n- EXPLORE: *time* = $\\mathcal{O}(N\\tau)$; *space* = $\\mathcal{O}(SAHN)$.\n- ERD: *time* = $\\mathcal{O}(H\\tau^E+H/\\epsilon_0)$; *space* = $\\mathcal{O}(H/\\epsilon_0)$.\n- PLANNING: *time* = $\\mathcal{O}(S^2AH^2/\\epsilon_0)$; *space* = $\\mathcal{O}(SAH^2/\\epsilon_0)$.\n- ROLLOUT: *time* = $\\mathcal{O}(KH)$; *space* = $\\mathcal{O}(K)$.\n\nThus:\n- **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)$.\n- **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.\n\nNote 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.\n\nWe 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.\n\nWe will add all these considerations to the paper.\n\n>  On the multi-environment utility identifiability.\n\nThis 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:\n- 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.\n- 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.\n\nFor 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.", "claims_and_evidence": "The paper provides strong theoretical justifications for its claims, with formal propositions  showing the limitations of identifiability in the single-environment setting. The propositions supporting the value of multi-environment data (Proposition 4.5) are correct but somewhat weak, as they confirm possibility rather than providing explicit complexity or a lower bound on the number of required environments.", "methods_and_evaluation_criteria": "The methods and evaluation criteria chosen (partial identifiability, regret, and compatibility metrics) make sense and are relevant to the problem of learning risk-sensitive utilities. The paper provides both bounds on the feasibility of learned utilities and empirical validations.", "theoretical_claims": "The theoretical claims, particularly the identifiability results  and regret bounds for algorithms, appear sound. I also checked the correctness of Proposition 4.1, Proposition 4.2, and Theorem 5.1; no issues were identified in the proofs. However, the complexity of the augmented state space approach is not well analyzed.", "experimental_designs_or_analyses": "The experimental results offers simple proof-of-concept demonstrations with real human data, validating the non-Markovian nature of human decision-making. However, the experiments are preliminary and somewhat limited in scope, particularly lacking evaluation in larger-scale or varied environments.", "relation_to_broader_scientific_literature": "The paper situates itself within inverse reinforcement learning and risk-sensitive MDP literature, highlighting how it generalizes previous IRL models (Ng & Russell, 2000) and connects to expected utility theory. However, the authors should more explicitly discuss connections to the broader literature on risk-sensitive MDPs, including Expected Risk Measure (ERM) MDPs and Conditional Value-at-Risk (CVaR) MDPs, which are not sufficiently discussed. Some references related to Maximum Entropy IRL (Ziebart, 2010) seems to be missing as well.", "essential_references_not_discussed": "Essential references related to risk-sensitive MDPs, particularly Online Risk-sensitive MDP, including ERM and CVaR-based, were not fully cited or adequately discussed. Incorporating such references would improve clarity and contextualize this work further within the broader risk-sensitive reinforcement learning literature. To name a few\n\nOnline ERM-MDP\n- Fei, Y., Yang, Z., Chen, Y., Wang, Z., and Xie, Q. Risk-sensitive reinforcement learning: near-optimal risksample tradeoff in regret. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.\n- Fei, Y., Yang, Z., Chen, Y., and Wang, Z. Exponential bellman equation and improved regret bounds for risksensitive reinforcement learning. Advances in neural information processing systems, 34:20436–20446, 2021.\n- Liang, H., & Luo, Z. Q. (2024). Bridging distributional and risk-sensitive reinforcement learning with provable regret bounds. Journal of Machine Learning Research, 25(221), 1-56.\n\nOnline CVaR-MDP\n- Bastani, O., Ma, J. Y., Shen, E., & Xu, W. (2022). Regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 35, 36259-36269.\n- Wang, K., Kallus, N., and Sun, W. Near-minimax-optimal risk-sensitive reinforcement learning with cvar. In International Conference on Machine Learning, pp. 3586435907. PMLR, 2023.\n- Wang, K., Liang, D., Kallus, N., and Sun, W. Risk-sensitive rl with optimized certainty equivalents via reduction to standard rl. arXiv preprint arXiv:2403.06323, 2024.", "other_strengths_and_weaknesses": "Strengths:\n- Novel problem formulation clearly motivated by real-world risk-sensitive behaviors.\n- Strong theoretical contributions on identifiability.\n- Clear, well-written manuscript.\n\nWeaknesses:\n- Limited empirical validation; experiments are preliminary and conducted only in simple settings.\n- Ambiguity in demonstrating the complexity and requirements for multi-environment utility identifiability.\n- Missing key discussions and comparisons with related risk-sensitive formulations (ERM, CVaR).", "other_comments_or_suggestions": "- Clarify and simplify Section 2’s notation, as some elements appear dense and are not essential for the main text.\n- More clearly state computational complexity and practical scalability concerns.", "questions_for_authors": "Please see the above concerns/weakness. In addition\n- Proposition 4.5 currently states only the possibility of unique identifiability. Can you provide insight into how many environments typically might be required for practical identifiability?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RFXwzJUopm", "reviewer": "Reviewer_mjRi", "summary": "This paper introduces a framework for learning utility functions from expert demonstrations inMDPs, where the utility function captures the agent’s risk sensitivity. As the utility may not be identifiable in a single environment, the authors consider learning from demonstrations in multiple environments. The paper proposes two methods and provide sample complexity guarantees for both. Finally, the authors conduct experiments on toy environment (both with real-world participants and simulated).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> On the experiments conducted.\n\nThe 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.\n\nIn 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.\n\n> On the participants to the experiments.\n\nThe 15 participants are **lab members**, as mentioned at the beginning of Section 6 (line 399). We will highlight this fact in the paper.\n\n> On the absence of baselines.\n\nConcerning **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.\n\nThe 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.\n\n> On the dependence on $H$.\n\nWe 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.\n\n> On the notation.\n\nWe 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.\n\n[1] Andrew Y. Ng and Stuart J. Russell. Algorithms for inverse reinforcement learning.\n\n[2] Brian D. Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy\n\n[3] Deepak Ramachandran and Eyal Amir. Bayesian Inverse Reinforcement Learning.\n\n[4] Lillian J. Ratliff and Eric Mazumdar. Inverse risk-sensitive reinforcement learning.\n\n[5] Sumeet Singh, Jonathan Lacotte, Anirudha Majumdar, and Marco Pavone. Risk-sensitive inverse reinforcement learning via semi- and non-parametric methods.\n\n[6] Haoyang Cao, Zhengqi Wu, and Renyuan Xu. Inference of utilities and time preference in sequential decision-making.", "claims_and_evidence": "The claims made in the submission are sufficiently supported.", "methods_and_evaluation_criteria": "The conducted experiments are in very small toy environments which seem inspired by simple financial decision-making situations. As a result, the experiments are not fully convincing, but still make sense for the motivation of learning risk-sensitive utility functions.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "I skimmed through the additional experimental details in Appendix F. The experimental design with the participants makes sense, though, it is not clear who the 15 participants are or whether these participants are representative/unbiased.   \n\nOne concern is the lack of baselines. The authors do not compare against existing methods in their experiments.", "relation_to_broader_scientific_literature": "This paper differentiates itself by explicitly modeling the risk attidude of individuals, whereas most prior work on IRL assumes risk-neutral experts (i.e., individuals). It is closely related to the literature on risk-senstive IRL (Majumdar et al. (2017), Singh et al. (2018), Chen et al. (2019), Ratliff & Mazumdar (2020), Cheng et al. (2023)) and primarily differs from the existing work in that it does not assume that the expert is Markovian.", "essential_references_not_discussed": "As far as I can tell, related work is appropriately addressed by the authors.", "other_strengths_and_weaknesses": "### Strengths \n1. The problem of learning risk-sensitive utility functions is well-motivated and addresses an important limitation of traditional IRL, which typically assumes risk-neutral behavior.\n2. The paper answers several fundamental questions about the problem setup, including the identifiability of utility functions. \n\n\n### Weaknesses \n1. The experiments lack comparisons to baselines from existing work on risk-sensitive IRL or utility learning. Could you please clarify whether existing methods are unsuitable for direct comparison or are there other reasons for having no baselines? \n2. The experiments are conducted on small toy environments, making it unclear how well the proposed methods scale and whether they can be applied in practice. Additionally, the dependence on the horizon $H$ appears to be a bottleneck and could potentially limiting the practicality of the approach in problems with longer horizons.", "other_comments_or_suggestions": "1. Even though the paper is overall well-written, it is still quite tedious to parse due to the sometimes seemingly exessive use of notation. It is nearly impossible to keep track of everything and you might want to consider finding ways to reduce the notational burden for the sake of the reader.", "questions_for_authors": "See above.\n\n\n**Post-Rebuttal Update**\n\nI maintain my original score and I am still in favor acceptance.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BXaBuTEQBd", "reviewer": "Reviewer_4S8c", "summary": "This paper considers learning a utility function from demonstration using inverse reinforcement learning and risk sensitive RL. The reward function is assumed to be known. The utility function mapping cumulative rewards to a scalar value is to be inferred. The authors proof the partial identifiability of utility function and improved identifiability with multiple environments. Two algorithms are proposed: 1) CATY-UL is used to classify whether a utility function lies in the compatibility set (i.e., compatible with observed behavior), 2) TRACTOR-UL is used to find a utility function that lies in the compatibility set. Practical implementation uses a discretization based approach for policy evaluation and utility representation and update. Experiments on real and simulated data show TRACTOR-UL's ability to find compatible utility functions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> 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.\n\nYes. 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.\n\n> Did the authors demonstrate improved identifiability with more environments, i.e., larger N? Sorry if I missed it but it was hard to find.\n\nFrom 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.\n\nFrom 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.\n\nNevertheless, 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.\n\n> 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.\n\nWe 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.\n\n> On line 18 in algorithm 2, what does the $\\Pi$ symbol mean? Is it a policy or a projection operator?\n\nYes, $\\Pi_{\\overline{\\underline{\\mathfrak{U}}}_L}$ denotes the Euclidean projection onto set $\\overline{\\underline{\\mathfrak{U}}}_L$, as defined on line 083.", "claims_and_evidence": "This paper proposes a method to learn utility functions from demonstration. The results demonstrate the claimed capability.", "methods_and_evaluation_criteria": "The proposal to focus on learning utility with known reward in line 201 makes sense. The definition of compatibility in (3) makes sense and is the main driver of the algorithms. Learning from multiple environments to improve identifiability makes sense.", "theoretical_claims": "I checked the counter examples used to proof partial identification, i.e., proposition 4.1-4.5. I briefly checked the derivations of the sample complexity bounds, i.e., theorem 5.1.", "experimental_designs_or_analyses": "The experimental design is sound, as the main focus is showing the ability to search compatible utility functions.\n\nA few questions:\n* 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. \n* Did the authors demonstrate improved identifiability with more environments, i.e., larger N? Sorry if I missed it but it was hard to find.", "relation_to_broader_scientific_literature": "This paper address the problem of model risk-sensitivity in inverse RL. Prior work has mainly focused on average return criteria, ignoring the full return distribution. This paper addresses the gap.", "essential_references_not_discussed": "I am not aware of essential references being missed.", "other_strengths_and_weaknesses": "**Weakness**\n* 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.", "other_comments_or_suggestions": "NA", "questions_for_authors": "* On line 18 in algorithm 2, what does the $\\Pi$ symbol mean? Is it a policy or a projection operator?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers learning utilities from demonstrations for risk-sensitive agents. A utility function is introduced that transforms rewards/returns of a trajectory to a real-valued utility for the agent. When this function is linear, classical inverse reinforcement learning methods result. When the function is nonlinear, risk-sensitivity is introduced. The paper specifically focuses on learning this utility function given the reward function is known/given. Identifiability is characterized for this task, and this characterization is used to guide the development of two algorithms: CATY-UL and TRACTOR-UL and provide convergence guarantees. The approach is evaluated on a simple tabular MDP.

This paper provides a good formulation and perspective for learning risk-sensitivity, and provides strong theoretical analysis. The empiricial demonstrations are weaker and it is not clear that the approach will be applicable to practical problems of much larger scale.

I dislike the title. It makes sense based on the authors' perspective, but would seem to imply learning both r^E and U^E without additional qualification: e.g., "Learning Risk-Sensitive Utilities from Demonstrations and Rewards in Markov Decision Processes" might be more appropriate.

Overall, I concur with the reviewers that this is a solid theoretical paper with a useful perspective and recommend acceptance.
Decision: Accept (poster)