Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback
Authors: Simone Drago
Marco Mussi
Alberto Maria Metelli
Venue: ICML 2025 poster (2025)
Keywords: preference-based
sequential decision making
preference feedback
Primary area: theory->reinforcement_learning_and_planning

Abstract: The success of sequential decision-making approaches, such as *reinforcement learning* (RL), is closely tied to the availability of a reward feedback. However, designing a reward function that encodes the desired objective is a challenging task. In this work, we address a more realistic scenario: sequential decision making with preference feedback provided, for instance, by a human expert. We aim to build a theoretical basis linking *preferences*, (non-Markovian) *utilities*, and (Markovian) *rewards*, and we study the connections between them. First, we model preference feedback using a partial (pre)order over trajectories, enabling the presence of incomparabilities that are common when preferences are provided by humans but are surprisingly overlooked in existing works. Second, to provide a theoretical justification for a common practice, we investigate how a preference relation can be approximated by a multi-objective utility. We introduce a notion of preference-utility compatibility and analyze the computational complexity of this transformation, showing that constructing the minimum-dimensional utility is NP-hard. Third, we propose a novel concept of preference-based policy dominance that does not rely on utilities or rewards and discuss the computational complexity of assessing it. Fourth, we develop a computationally efficient algorithm to approximate a utility using (Markovian) rewards and quantify the error in terms of the suboptimality of the optimal policy induced by the approximating reward. This work aims to lay the foundation for a principled approach to sequential decision making from preference feedback, with promising potential applications in RL from human feedback.

Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback
Simone Drago' Marco Mussi Alberto Maria Metelli
Abstract
1. Introduction
The success of sequential decision -making ap- proaches, such as reinforcement learning (RI.), is closely tied to the availability of a reward feed- back. However, designing a reward function that encodes the desired objective is challenging task. In this work, we address more realistic scenario: sequential decision making with prefer- ence feedback provided, for instance, by human expert. We aim to build a theoretical basis link- ing preferences, mnon-Markovin (Markovian) rewards, and we study the connec- tions between them. First, we model preference feedback using a partial (pre)order over trajecto- ries, enabling the presence of incomparabilities that are common when preferences are provided by humans but are surprisingly overlooked in ex- isting works. Second, to provide a theoretical justification for a common practice, we investi- gate how a preference relation can be approxi- mated by a multi-objective utility. We introduce a notion of preference-utilit compatibility and ana- lyze the computational complexity of this transfor- mation, showing that constructing the minimum- dimensional utility is NP-hard. Third, we propose a novel concept of preference-baie based policy domi- nance that does not rely on utilities or rewards and discuss the computational complexity of assessing it. Fourth, develop computationally efficient algorithm approximate utility using (Marko- vian) rewards and quantify the eтror in terms of the suboptimality of the optimal policy induced by the approximating reward. This work aims to lay the foundation for a principled approach to sequential decision making from preference feed- back, with promising potential applications in RL from human feedback.
In the last decade, reinforcement learning (RL, Sutton & Barto, 2018) has demonstrated great success tackling sequential decision-making under uncertainty with no- table results in industrial plant control (Nian et al., 2020), robotics (Kober et al.. 2013), clinical trials (Coronato et al., 2020), autonomous driving (Kiran et al., 2021), videogames (Mnih et al., 2015), and, more recently, lan- guage models (Du et al., 2023), In RL, the learning process is guided by numerical feedback (i.e., reward function). The reward is often defined informally as "the most succinet description of a task" (Ng & Russell, 2000). More formally, the power of a reward function is apparent since it allows, under the Markovian property of the environment (Puter- man, 2014), to approach the learning problem with desirable computational (Papadimitriou & Tsitsiklis, 1987; Littman, 1995) and statistical (Azar al., 2012) properties.
utilities, and
Nevertheless, the limits of learning with reward are well known. In the common practice, the reward function is typically designed by system expert who leverages their domain knowledge to capture the intuitive notion of "solving the task". However, many real-world scenarios, crafting reward function that appropriately encodes the desired objective can be challenging. Indeed, rewards should go beyond merely capturing the desired behavior to enhance their generalizability, interpretability. and transferability to new environments (Ng & Russell, 2000). Defining a reward, often referred to as reward engineering (Dewey, 2014), is typically a trial-and-error process involving successive re- finements since the behavior learned by the agent can be highly sensitive misspecifications of the reward (Pan et al., 2022). As such, the choice of the reward function has crit- ical impact on the success of the agent in learning how to solve the task. Even accepting the availability of a reward function, the community has recently questioned whether a reward function is truly an appropriate mathematical tool to encode the notion of a goal. The debate dates back twenty years, when Sutton postulated that "all of what we mean by goals and purposes can be well thought of as maximization of the expected value of the cumulative sum of a received scalar signal (reward)" (Sutton, 2004). More recently, this hypothesis has been under investigation, although a defini-
'Politecnico di Milano, Milan, Italy. Correspondence to: Simone Drago cimmonn.drago@e polimi.tt>>
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
tive answer is currently lacking (Silver al., 2021; Glukhov, 2022; Vamplew al., 2023; Bowling al., 2023).
represent incomparabilities (i.e., situations where the human expert is unable compare certain pairs of trajectories). However, the definition of optimality, we will discuss later in the paper, may pose important computational lim- itations. On the other hand, (+i) and (iil) are based on a numerical signal and, for this reason, introduce a bias² and the need for multi-objective signals (Hayes et al., 2022) to model incomparabilities. The positive counterpart of using a numerical signal is that optimality notions (e.g.. Pareto optimality, Censor 1977) are well-defined. Neverthe- less, planning with general utilities (ii) is still intractable, whereas when using rewards (iii) coupled with the Markov property, the computation of the optimal policy can be done efficiently (Papadimitriou & Tsitsiklis, 1987).
Why not get rid of the reward? One solution is to ask a hu- man expert for feedback on the agent's 's behavior rather than requiring them to define a numerical reward function. The agent can then learn a behavior that aligns with the expert's preferences. In the literature, this paradigm is known as preference-based reinforcement learning (PbRL, Fürnkranz et al., 2012). Although PbRL dates back more than twenty years, it has received renewed attention from the community thanks to the rise of large language models (LLMs, Zhao et al., 2023a). Indeed, modern LLMs are (pre-)trained using large amounts of data collected by eliciting pairwise human preferences (Ramachandran et al., 2017; Radford, 2018). An established approach for leveraging human preferences is reinforcement learning from human feedback (RLHF, Chris- tiano et al., 2017; Stiennon et al., 2020; Bai et al., 2022; Ouyang et al., 2022), which consists of two steps: first, pref- erences over trajectories are used to learn a reward model, and then, RL is applied using the recovered reward func- tion. In addition to its remarkable empirical performance, RLHF has recently gained a theoretical understanding (Xu et al., 2020; Chen al., 2022: Saha et al., 2023; Zhan et al., 2024a;b). Nevertheless, these works are closely tied to the assumption of the existence of an underlying (hid- den) numerical signal (either a proper reward function or a utility defined over trajectories), of which the preferences expressed by the human are an indirect stochastic manifesta- tion.' More in general, estimating& a scalar numerical signal, like in RLHF, from preferences hinders the complexity of the human feedback such as the possible multi-objective nature of the human behavior (Hayes et al., 2022). Other approaches focus on learning the policy directly from pref- erences without going through a reward model (An et al., 2023; Zhao et al., 2023b; Rafailov et al., 2024; Azar et al., 2024). Despite the promising results, these approaches, sim- ilar to RLHF, are based on a probabilistic model of human preferences that the learned policy tries to replicate.
In this paper, we aim to take step toward the theoretical un- derstanding of sequential decision- making with preference feedback. Specifically, we seek to understand: (a) What can be learned when no assumptions are made beyond the
fact that the human provides preference feedback? This involves introducing and studying notions of dominance and optimality. (b) How can we approximate preferences with a utility, making the fewest assumptions? This requires defining a notion of compatibility between preference rela- tions and utilities (Evren & Ok, 2011) and studying whether constructing a compatible utility can be done efficiently. (c) How can we converl a utility to a reward function? This includes analyzing the level of approximation and the com- putational tractability of the conversion.
Unlike RLHF, we will make no assumptions about the exis- tence of underlying reward function the existence of a probabilistic model guiding the human preference- generation process. Our main goal is to establish theoret- ical basis to design, in future works, statistically efficient algorithms for learning with preference feedback.
Original Contributions. The contributions of the paper are summarized as follows:
In Section 3, we define three augmentations of the Markov decision process without rewards setting to include pref- erences, utilities and rewards.
Despite the wide variety of approaches, to the best of the authors' knowledge, there is still limited theoretical un- derstanding of the challenges and opportunities involved in learning from preference feedback. In the PbRL litera- ture (Wirth et al., 2017), an agent can roughly operate in three ways: (i) learn the policy directly from preferences, (ii) estimate surrogate utility (i.e., a non-Markovian re-
In Section 4, we define the notion of compatibility be- tween (partial) preorder that we use to represent prefer- ences and a mnulti-dimensional) utility function. We study the computational complexity of constructing compatible utilities. Moreover, we propose a heuristic to compute a compatible utility in polynomial time.
ward) defined over trajectories, or (iii) derive a (Markovian) reward function. Moving from (i) to (iii), we trade off rep- resentational power with tractability. On the one hand, (i) constitutes a more general approach where no numerical signal needs to be modeled, and as such, could inherently
In Section 5, we define the concepts of dominance and optimality for policies when only preferences are involved, discussing their computational properties, and deriving method to verify policy dominance w.r.t. preorder.
A classical assumption is that the probability of one trajectory heing preferred over another is proportional to some function of the difference in utility between the two (Saha et al., 2023).
Intuitively, with preferences, we can only say if trajectory is better than another; whereas with a utility or reward, we have to encode how much a trajectory is better than another.
2

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
In Section 6, we study the problem of jointly comput- ing (non-Markovian) compatible utility and its (Marko- vian) approximation induced by rewards and we provide a bound to the distance of the induced Pareto frontiers.
comparable). The width is the maximum cardinality of antichain width(=xx) max( :'= s.t. Vr.ye 2 = x || lyy). It is known that dim( (xxx) < width(=Sx) (Dilworth, 1987).
:
Related works are reported in Section 7 and omitted proofs can be found in Appendix A.
Component-wise Order. For real vectors vi we R we define the component-wise (or Pareto) partial order as v vs w= Vie [d]: : 1 E wt According to previous definition, we w~
2. Preliminaries
have vー w = Vie [d]] : U2 E wi A 3je [d]: Wyy
Sorting function. Let Ex be total order, a bijection whg || | we have i j + w= (i) <x Pz()). Ve (which is unique) sorts the elements of X according to the total order xxx Let f ': R and Ex be a total order, whenever clear from the context, we abbreviate f(i) = fiVe (i)).
In this section, we provide the background that will be employed in the following sections.
is sorting function if for every i, E [|
Notation. Given N with a abb, we define [a] := (I, and (a,a=
For CE R, we use the notation (e)+ == m0.)0,c). Given a finite set X. we denote as (x) the probability simplex over X, with P(x) its power set, and with | its cardinality. For a matrix A,
Markov Decision Process without Rewards. A finite- horizon Markov decision process without reward (MDP),, R, Abbeel & Ng, 2004) is tuple (S,A, H,P, p), where S and A are the finite ([S = and |A|==:A) state and ac- tion spaces, HEN is the horizon, p= ==(p))te(m defined for every he [H] as Ph:S A- (S)) is the transition model that for every state SE action AE stage he [/]]] and next state S provides the probability p,(''ls,a) to reach s' by playing action in state at stage h, and μu (SS) is the initial-state distribution such that p(s) pro- vides the probability that the interaction starts in 8. A tra- jectory of length he [[]] is T= (;) representing sequence of state-action pairs belonging to the set of tra- jectories Th S (S x A)* with cardinality [Ta] < (SA)². If the length is not specified, it is assumed to be h H (i.e., TH) The agent behavior is modeled with a history- dependent policy т (TT)) defined for every /e [H] as RTK T x S - ((A) that, for every trajectory TE TA-1 of length h h- 1, state sES, and action aE,,, provides the probability TA (a 7 s) to play action a after having observed trajectory 7 and state s. A policy is Markovian if depends on the current state only and, in such a case, we abbreviate with n (als). We denote with II the set of distory-dependee policies. A policy T II induces trajectory distribution:
we indicate with || its Frobenius norm and with La the identity matrix of order d.
(Pre)Order Relations. Let be set and xx X' x X' be (hinary) relation, if (x,,))Exx,, we use the notation x SXx y- A relation Xx is
preonder is: (i) reflexive (i.e., x Sxx 2) and (it) transitive (i.e., 2 S. y ^ Sx xx Sxxx 2). A (partial) order is a preorder that is (iii) antisymmetric (i.e., x y A - x= y). We write x x if x S y and not y/5x x. x and y are incomparable, and we denote it as x llxx g. if neither SxxV y nor y Sxx z; otherwise they are comparable. Moreover, x and y are equivalent if x y and v, and we denote it as z== y. =x is an equivalence relation that induces partial order over the quotient set X/=x,, i..., [x] S|x|/>> [v] i xxxx y. A (pre)order is total when every pair of distinct elements is comparable (i.e., ye X: xx V //xx), We sometimes denote total (pre)orders with the symbol Ex.
Linear Extensions, Order Dimension, and Width. Let SxE X x X be an order relation and ε X x X' be to- tal order, x is linear extension of 5x if xx (i.e., x x V) A set [xx.liee of total orders is a realizer of an order Sx if <x= <x=Nuetq Ex,a (which im- plies that all xx,= are linear extensions of xx). The order dimension (Dushnik & Miller, 1941; Trotter, 1992) of the order x is the least cardinality of a realizer of xxx, i.e., dim x m: : ((x realizer of sx}. If 2 is preorder, we define its dimension as the dimen- sion of the partial order induced over the quotient set, i.e., dim(sx):=dl : :iim (x/==))- It is known that for | |> 3, computing the order dimension is NP-hard (Yannakakis, 1982; Felsner et al., 2017). Furthermore, unless NP ZPP. there exists no polynomial-time algorithm ap- proximate the order dimension with factor of "() for every e>0 0 (Chalermsook et al., 2013), An antichain (resp. chain) is a subset of X' such that any two dis- tinct elements are incomparable (resp. all elements are
H II
de (+)))
Th (an Th- Sh)p (s. h=1
()),),)) (1)
where π. = lE [=] of trajectory T= (5,.
.1,01) denotes the prefix of length
3. Setting
In this section, we introduce three augmentations of MDP) R defined in terms of preference relations, utility function, and Markovian cumulative reward function.
Preference- based MDP. Let <T=Tx] T be a pre- order over trajectories T. We define a preference-based
3

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
Markov decision process (PbMDP) as the tuple = (S,A, (.,,,, obtained by pairing an MDP R with a preorder relation zt defining preferences over the trajec- tories.' The use of a preorder relation allows formalizing when a trajectory r' is preferred over т, i.e., TTT T'. but also accounting for both equivalent T T= and incompara- ble r I| trajectories with T; TT. We will introduce the optimality conditions for a PbMDP in Section 5.
4. Representing Preferences with Utilities
In this section, we show how preferences can be represented using utilities. We define the notion of compatibility be- tween preferences and (possibly multi-dimensional) utilities, starting with the simpler case of total preorders and, then, moving to partial preorders. We also discuss the computa- tional aspects of constructing compatible utility from a preorder. The content of this section will be necessary to define the notion of optimality presented in Section 5.
Utility-based MDP. Let N and u: T= be multi- dimensional utility function, i.e., function mapping tra- jectory T to a vector u(T)= (T),. Um (m)(T)) (T)) of m real numbers. A utility-based Markov decision process (UtilMDP) is defined as the tuple M- (SS.A, H.p. Ja. u) obtained by pairing an MDP)R R with a utility function u. Let Æ l1 be a policy, its expected utility is defined as:
The use of utilities to represent preferences dates back to (Von Neumann & Morgenstern, 1947), which shows that any rational agent defines their preferences in terms of an underlying utility function. Then, (Debreu, 1954) shows the existence of a scalar utility that represents total order. Subsequently, (Ok, 2002; Evren & Ok, 201 1) extend this result by proving the existence of a dimeniininn utility that represents a partial (pre)order relation.
J uT; Σ (T(())(()= TET
Let क., I' be two policies, we say that iT u- u-Pareto strictly dominates x' (resp. u-Pareto weakly dominates x²) if J (T; ( (x) (resp. J (T; 2 u(). We define the set of uu-Pareto optimal policies (i.e., the Pareto frontier) as the set of policies that are not u-Pareto strictly dom- inated by any other policy, i.e. II (u) = II:: -3n's e II s.t. J(z';u) u) > J [T;; u)). Given a utility u, the u-Pareto dominance induces partial preorder relation = IT x IT over the policy space, of which the set of Pareto optimal policies II (u) are the maximal elements. If m 1n=1,2 a u- optimal policy is any policy maximizing the expected utility, i.e., π= e "II* (u)= arg max, J (I;u).
Compatible Utilities. We start with the total preorder case. Definition 4.1 (Compatible Utility Total Preorder). Let T be a total preorder over T and let u:T w TR. be a scalar utility function. is compatible with <T for every T,T'E T it holds that T ET +> u(T)<u(T')
Thus, if T TTT (i.e., T' is strictly preferred over 7) then u(T) < u(7') and if 7= (i.e., T' and t are equivalent) then ((T)=u(F)) Utilities compatible with total preorders clearly exist and simplistic way to derive a compatible utility to order the trajectories according to T and map each one to real number, e.g., u(t (1)) i. Similarly, given a utility it is simple to derive the corresponding preorder by applying Definition 4.1. We now move to the partial preorder case, following (Ok, 2002, Equation 2).
(1)) = u(f)= (())==(()=)))))) [7]
Reward- based MDP. Let meN and let r= (F defined for every he he[H] as : A-R" be a multi- dimensional reward function, i.e., a function mapping ev- ery stage he [H]. state SE and action ae A to vector of m real numbers. A rreward-based Markov decision process (MDP) is de- fined as the tuple M=(S. (S, Hr, obtained by pairing an MDP,R R with a reward function r. It is always possible to define a utility from a reward by means of the trajectory return, defined for every T 7=($1 ($1,01...... SH. TTTT as:
ra(s,a)= (T,, "h..
Definition 4.2 (Compatible Utility - Partial Preorder). Let ST be a preorder over T and let u: T T with mEN be a multi- ciilli-dimessoonall utility. u is compatible with ZT for every T, T'ET it holds that t T <>
Some comments are in order. First, we note that, differently from Definition 4.1, we employ multi-dimensionn utilities made of m components. Second, we use the component- wise order of the utility to define the compatibility. Precisely, if i (i.e., 7' strictly preferred over r) then Vie [M]] <x(T)& and Aje [m]]: ]
11
Ur (T) = Σ rn (s).
(3)
Let IE be policy, its expected return is defined as J (T;z):= := u.) The concept of r-Pareto dominance, the set of P-rretoo optimal policies 11$ (r)), and, in the case of m=mm 1, the set of optimal policies (r), are defined as for the UtilMDP. by means of the return utility up It is well-known that in MDPs there always exist (Pareto) opti- mal policies which are Markovian (Puterman, 2014).
(r))).) If, instead, T= (i.e.. T and r' are equivalent), we set the utilities to the same value Vie [u())=)(([[==))))))]])])<))))[ ( =.(r). Finally, 7 I|T r' (i.e., and T' are incomparable) corresponds to the condi- tion Ji [ (=(rr> u)(()) ()(7)<
While deriving the preorder from the multi-dimensional utility can be done directly by applying Definition 4.2; dif- ferently from the total preorder case, the construction of a compatible utility from the preorder not straightforward
In agreement with the literature (Ok, 2002), we use preorders to represent the informal notion of "preference relation". "
4

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
T2
FG
77
74
1
F3
T7
T5
T1
22
T4
T3
T7
T5
T6
T4
T5
T6
T4
TI
T2
T3
T7
T4
T5
T6
T3
(h) minimum path cover [C: Nets--
(c) realizer (ET.))<11) constructed from the minimum path cover [C]]
(a) DAG G of ST.
Figure Example of a partial order on the set T (T...... 77) having width w - 3, a minimumn path cover, and a realizer.
The following result shows that the minimum value of m is the order dimension of the preorder.
the set of nodes corresponds to the set of trajectories T and the set of edges E is such that its reflexive and transitive closure is the partial order Zy. We now solve a minimum path cover (MPC) problem to obtain set of wo chains (i.e., paths in the graph) that covers all the trajectories (i.e., all the nodes). Caceres et al. (2022) proposes an algorithm that runs in of chains (i.e., sequence of nodes), we now derive realizer set << This is done by extending each chain C, with iE [w] to obtain the linear extension &T,; as follows: for every Ti, T2 T, if T1 and T3 are incomparable in <T (i.e., Ti |l 72) and C2, then 71 &T, 72- This procedure has cost of O (ITP). Overall, we compute a realizer of IT with cardinality w in at most ( + w²)), having observed that |E| a T (Kritikakis & Tollis, 2022). An example of this procedure is reported in Figure 1.
Theorem 4.1. Let T x T be a preorder over T. Then: (i) there exists a dim((=))ddmmnnsoon)) compatible utilit;; (ti) no m-dimensional compatible utilities with m < dim(sT) exist.
+ [ Letting [Ci] represent the set
The proof of the theorem follows from the application of Definitions 4.1 and 4.2 and from the definition of order di- mension. Clearly, one can define utilities with more than dim(< dimensions and, in any case, having fixed m, in- finitely many compatible utilities exist (e.g., by performing translations or rescaling with positive factors). We call min- imal a dim( ( -dimensional utility. The following result shows that computing minimal utilities hard.
Theorem 4.2. Let I be preorder over T. The construc- tion of a minimal utility u compatible with IT is NP-hard.
Given Definitions 4.1 and 4.2, every UtilMDP can be mapped exactly one PbMDP defined with the preorder IT unambiguously constructed from the utility u, while PbMDP can be mapped to multiple (infinitely many) UtiLMDPs with any utility u compatible with the preorder
The theorem follows from the NP-hardness of computing the order dimension. Due to the inapproximability results, it is not possible to compute in polynomial time compatible utilities with a number of dimensions 0(77)==<im(<>>) for <>> in the worst case (Chalermsook et al., 2013).
ST. This observation motivates the need for evaluating opti- mality and dominance directly w.r.t. the preference relation.
Compatible Utility Heuristic. We propose a method to construct multi-dimenssioal utility function u that is com- patible with < based dividing the problem into three phases: (i) we construct a realizer (< im (i.e., a set of linear extensions) of zT of size m (which need not be min- imal), then, (ii) we construct a scalar compatible utility for each T in the realizer set (which can be done in O(TT) time) for every ie [[m] finally, (iéi) we juxtapose the scalar utilities into m-dimensional utility (which can be done in (()) time).
5. Dominance and Optimality with Preferences
In this section, introduce the novel concepts of domi- nance and optimality for policies defined by means of the preorder ST. and we discuss their computational proper- ties. Similarly to UtilMDPs and MDPs, where (possibly multi lilliidiimesional) utilities or rewards are present, we aim to characterize the target when solving a PbMDP, i.e.. a notion of a non-dominated set of policies. However, unlike UtiLMDPs and MDPs, PbMDPs lack numerical signal.
We now introduce a tractable method for (i), i.e., to derive realizer of cardinality w:= = width( < given a partial order over trajectories.' 4 We start by observing that ST can be rep- resented as a direct acyclic graph (DAG) G = (T, (E), where
From now on, we only consider the case in which Σn is an order. Indeed, if < is a preorder, we can consider the order induced over the quotient T/ =y. observing that equivalent trajectories correspond to the same utility value.
"We consider only the case in which we have an order. Indced, if we have a preorder, we can consider the order induced over the quotient set by the equivalence relation =7, as for equivalent trajectories, we are foreed to set the same value of the utility.
Dominance for Total Orders. As discussed in Section
FFormally, E the cover relation induced by the partial order ST (Knuth, 2013).
5

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
for every order =., there exist infinitely many compatible utilities. However, the Pareto optimality of policy x e IT w.r.t. certain compatible utility u does not necessarily guarantee its Pareto optimality w.r.t. another compatible utility u', as shown in the following example.
Definition 5.1 requires testing the condition "for every com- patible utility" which is clearly infeasible. We can easily overcome this issue, as shown in the following result.
Theorem 5.1. Let T be a total order over T, and let T, T' EI be two policies. π &T-weakly dominates x' if and only if it holds that:
Example 1. This holds even for scalar utilities. Let T (T,,T2, Ta} and the total order ET be defined as:
Vn [1711: Σ (1))))
T3 T
(4)
(8)
Let [1=(,,,²) be the policy space with the correspond- ing trajectory distributions (0.5, 0. and -
Furthermore, π. ST-strictly dominates x' if and only if. in addition to the above, it holds that:
(0.8,0.0.2) Consider the utilities i = (4,2, 2)) and
U2 =2 both compatible with T.. We have:
An E [11I Σ
(9)
J - (((; 3, ( (2)) 2.8.
(5)
(6)
The proof is reported in Appendix A. To give an interpretation to the condition in Equation (8), con- sider the vectors (d. (ITI)) and d== (dz:(1)....,d'/ ((T)) of the trajectory probabilities sorted in non- non-increasing order (from the most preferred to the least preferred trajectory) according to the total order ÊT. Equation (8) prescribes that the vectors of the cumulative sums Cdn and Cd of the trajectory probabilities to sat- isfy Cd 2 Cd in the sense of the component- wise order, where C is a lower triangular matrix of all 1s. Thus, we have reduced the problem of assessing the dominance between policies (T' m) to the problem of assessing dominance be- tween real vectors (Cdyy =<' Cdz). An immediate intuitive consequence is that for the most preferred trajectory, we have d=(1) >> (1), and for the least preferred trajectory, we have dx ((T)) < d ((T() The computational complexity of verifying the condition of Equation (8) is O(T7)).
Thus, n' "n- u1-(Pureto) dominates π and π (p-(Prt) domi-
nates x/.
For this reason, we propose defining dominance between policies considering all compatible utilities. This ensures that if a policy x dominates another policy x' (in the sense detined below), then т Pareto dominates n w.r.t. all com- patible utilities. Let us begin with the case of total orders.
Definition 5.1 (Policy Dominance- Total Order). Let T be a total order over T, and let ,, Ell be two policies. π Et-stricty dominates n², denoted as nO <n v ifi for every utility u: T - RR compatible with ET, have:
J(Z')) (da -dr >0.
If the inequality holds with 3, we say that π E--wwekly dominates n', denoted as n' En n.
Dominance for Partial Orders.
Moving from total to partial orders, we directly generalize Definition 5.1 to the case of compatible muulii-dimensional) utilities.
Since we are considering total orders and, consequently, scalar utilities, require that π yields strictly better expected utility J(T;U) compared to that u() of x', evaluated under any compatible utility. Note that EnE 1l x II is a partial preorder over the space of policies II. Indeed, even if the order < is total, the induced preorder En can be partial, as illustrated below.
Definition 5.2 (Policy Dominance Partial Order). Let ST be an order over T, and let n IT be two policies. n -y-strictly dominates n², denoted as T² <nz if. for every utility u compatible with ΣT, it holds that:
Example 2. Let (T,, T3, T be a trajectory space. Consider the following total order Ty:
J(T;u) [ ;u) (dn - dr., u0,,,,2=000 > 0.
If the inequality holds with 2, we say that π we-kly dominates n², denoted as n' Snn.. n.
T4 <TT33TTT25 STT--
(7)
Let EII be two policies with trajectory distributions and d,, = (0.3,0.2,00 Now, let i1 (4,3,,1))))) and u2 = 11,,9,8.11 scalar utilities both compatible with T Thus, to determine whether N. dominates n², we need to verify if the condition of
Thus, we require that policy π u-Pareto dominates x' under any compatible utility u. As for the case of total orders. II x II represents partial preorder over the space of policies. The following result shows that Definition 5.2, i.e., dominance between policies w.r.t. a partial order <T, can be equivalently stated by requiring that dominance holds for all the linear extensions (i.c., total orders), according to Definition 5.1, for every realizer ( (57,,iie]m) of <T.
0.2, 0.1. be two
Definition 5.1 holds for both utilities: <d_- - dd - 0.2
and (dn - de,, u2) = 0.4. Thus, π does not dominate n' and vice versa (i.e., nt I| TT,, showing that en is partial.
6

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
Theorem 5.2. Let ST be partial order over T and let
Total Order Case. Consider total order T over [7] trajectories that can be represented by a scalar compatible utility u as in Definition 4.1. We can arbitrarily choose the values of uu()) so that for every [[7]] such that i j we have u(i) & w(j) - & where e> 0 represents the minimum utility gap between two trajectories. We want to find a reward vector re RRH which best represents the compatible utility vector. To this end, we jointly optimize the choice of utility and reward to minimize the error due to the limited expressive power of the reward w.r.t. the utility, by means of the following quadratic program (QP):
n, II be two policies. ι ST-weakly dominates nt if and only if. for every realizer (ET,a)etmm] with me IN of ST, it holds that:
Vie[m]] n' 2'E1TT,
where n' EIL σт (resp. T) denotes that π weakly (resp. strictly) ET doominntts x' (Definition 5.1) w.r. the i-th total order in the realizer of ST. Furthermore, a -T- strictly dominates x' if and only if. in addition the above,
it holds that:
]je[m]]
T' T'S1ITT.
(10)
1f =
min NE MERI PER
Thus, we have reduced the problem of assessing the dom- inance for partial orders to assessing the dominance of a number of total orders. By a simple application of Theo- rem 5.1, we can state the following equivalent condition.
s.t. u(V' (i+ 1)) & uu (i)) - E,, ViE - 1]
u(Ver ( u( (1))=1
Theorem 5.3. Let ΣT be partial order over T and let T' e II be two policies. π se-wllkly dominates nt if and only if. for every linear extension ET of ST, it holds that:
where BE (0, (1,11)/XXSAH X is binary matrix encoding, for every trajectory, which stages, states, and actions are in- volved in it (the order in which will influence only the order the elements in the reward vector). The constraints on u(1) and u([TT) just set the scale of the utilities and the ones proposed above are an arbitrary valid choice. We can casily climinate the vari- able r by observing that it is not involved in any con- straints, and solve the least- least-squares problem in closed form, obtaining r= BB) -1
AE I1T11: E(d=(vEr (V=, (1))) 0. (11)
design this matrix
π. St-Strictly dominates n' is and only if. in addition to the above, there exists a linear extension s'7 ST such that:
Ane Ine][ Σ (W=, (z) (1 (1)))
(12)
" "Buu? Thus, by defining A:- BT, the objective function becomes
Although it resembles Theorem 5.1 for total orders, Theo- rem 5.3 cannot be leveraged to derive an efficient algorithm. Indeed, trivial application would require to enumerate all linear extensions that, in the worst case, are !T!. We are currently unable to provide a polynomial-time algorithm to assess policy dominance for partial orders but we conjecture that the problem is computationally hard.
I - B ( B BT, Au Aul= = A Au, leading to a QP with [T] variables, a quadratic (convex) objective, and |T|+ + linear constraints, that can be solved using convenient convex optimization tools (Boyd & Vandenberghe, 2004).
Partial Order Case. The same rationale can be applied to partial orders > by considering a realizer ( and compatible m-dimensional utility u /7 (also switching the Euclidean norm with the Frobenious norm):
Optimality. We now define notion of optimality for policies in terms of the preference relation. Following the same ideas as for Pareto-optimal policies, we call policy optimal w.r.t. an order zn if there exists no other policy that strictly dominates it.
17* = min wER 7ixm
|Au 2
(13)
Definition 5.3 (Optimality). Let ST be a partial order over T. n* E II is =o-otiimal if it is not S--strictly dominated by any other policy. We denote the set of sp-ttiaall poli- cies as:
s.t. uz (1 1)) & &uy(Wer.) (1) - -c,
Vie [T - 1]. je [m]
uy uy(Ver, , ([T))) =0,
Yje [m]
uy(Ver, a (1)) 11))=1,
Vje [m]
II (TE) -3 π <'
Also in this case we are in the presence of a QP with m TT] variables and m([T] | 1) linear constraints.
6. From (Non-Markovian) Utility to Markovian Reward
'Formally. let T (s1,a1..... 811, aT)ETTTTTTTTT..TTT............ we have that B(r, (st,ar, ()) 1 for every le [H] and all other components of row T are equal to 0.
In this section, we study the problem of approximating a non-Markovian) compatible utility with a (Markovian) reward and discuss the approximation error.
'The choice of the set of all trajectories [T] makes B full rank.
thus ensuring that B admits an inverse.
7

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
When the partial order can be in- deed represented via Markovian rewards, then the QP pre- sented above returns value of the objective function n7* = 0, otherwise, it returns 17 > 0. In the opposite case, the Marko- vian reward yields an approximated utility û urr that will induce a certain set 11 (I*(())) S 11 of ü- fa-Pareto optimal policies, whereas u will yield another set II$ (u) S II of u- u--aareto op- timal policies. We now propose to evaluate the dissimilarity between the two sets of policies with the following index:
Approximation Error.
(i.e., the type of feedback consider in this work) is also referred to comparison feedback. Comparison feedback first appeared in the literature in terms of feedback over individual state-action pairs (Cheng et al., 201 I; Fürnkranz et al., 2012), and was later extended to reward learning tasks (Christiano et al., 2017; Ibarz et al., 2018).
Learning from Preferences. Our setting has connections with both PbRL and RLHF. Wirth al. (2017) propose the Markov decision process with preferences (MDPP) setting, aiming at unifying some of the existing PbRL results under common framework. MDPPs employ a stochastic prefer- ence generation process. Although this is a relevant scenario when learning a policy given a set of binary preferences, it deviates from the objective of studying the computational complexity of the problem, thus, motivating the need to define our PbMDPs where the preferences are deterministic. Moreover, MDPPs define preferences between trajectories in terms of the likelihood of them being generated by a given policy. This assumption, although sensible w.r.t. the goal of the authors, is stronger than what is required in this work that simply considers general preorders. Wirth et al. (2017) and Kaufmann al. (2023) survey several PbRL and RLHF approaches, ranging in methodology from direct pol- icy learning (Wilson et al., 2012; Rafailov et al., 2024), to learning a utility (Akrour et al., 2012), to learning reward function (Zucker et al., 2010; Christiano et al., 2017), all under the probabilistic preference assumption.
C(u, u) = max
sup inf AJ (TT, u),, (u) (1)
inf AJ+ ( ,,, {
sup (e)l (u)
where:
AJ+ = Σ (((Tu)))-(a.))) jE[m]
(14)
This index is designed to account only for performance losses when we move from a u-Pareto optimal policy û-Pareto optimal policy âे and does not allow for compen- sations when ी better optimizes some dimensions of w.r.t. the Pareto optimal policy л. The presence of the infimum ensures picking the policy @t in the Pareto frontier of â "clos- est" to π, while the supremum forces the worst-case choice of π. Analogous reasoning holds for the second argument of the max by reversing the roles of π and â. In the following theorem, we upper bound the performance loss due to the Markovian approximation.
Preference-Based Multi-Armed Bandits. Several multi- armed bandit (MAB, Lattimore & Szepesvári, 2020) set- tings share some aspects with PhRL.. For example, dueling bandits (DBs, Yue et al., 2012) are the preference-based version of MABs, and can be interpreted as the one-state version of PbRI.. DBs can allow for non-order relations among arms (see, e.g., Zoghi et al., 2015). Xu et al. (2020) employ a DB-based subroutine in their PbRL algorithm, and demonstrate the existence of MDPs with non-transitive preferences between trajectories, leading to the absence of unique optimal policy. This scenario, however, is out of the scope of this work, as removing the assumption of a (partial) preorder would change the basis of the analysis, with a notable loss of the properties presented in this paper. A different example is (Azar et al., 2024), in which the au- thors define the problem of learning from human feedback as an offline contextual bandit (Lu al., 2010) problem. We refer the interested reader (Busa-Feket) & Hüllermeier, 2014) for detailed survey of sefference-bssed learning in MABS.
Theorem 6.1. Let u, T "M be two m-dimensional utilities functions such that ||u Rill En Then, it holds that L(u, i & 2
It is worth noting that this result holds for arbitrary pairs of utilities, not necessarily derived with the QP presented above. We can trivially verify that in the case of total pre- order, the difference in performance is bounded by 2
7. Related Works
We summarize the relevant literature, focusing on feedback types, learning from preferences, and results on bandits.
Types of Feedback. PbRL and RLHF approaches have been studied combined with several types of feedback. Kaufmann et al. (2023) report and analyze several classes of feedback, presenting a trade-off in terms of how the complexity is distributed between the human expert (i.e., difficulty of pro- viding a feedback) and the agent (i.e., difficulty of learning given the feedback). In our framework, we consider only feedback over trajectories, the most common one, while allowing for non- Manrovaavianttyy in the implicit evaluation of the expert. Asking for a preference among a set of objects
8. Discussion and Conclusions
In this work, we defined the PbMDP setting, obtained by extending an MDP R with (partial) preorder over trajec- tories, and compared it with UtilMDPs and MDPs. We
8

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
defined the notion of utility-preférence compatibility and discussed the computational issues in constructing them. Then, we defined the concepts of policy dominance, ac- counting for the fact that the true underlying utility function is unknown. Finally, we discussed the need to move from utilities to Markovian rewards, providing a QP optimization problem to compute the reward values, and quantifying the approximation error.
An, G., Lee, J., Zuo, X., Kosaka, N., Kim, K.-M., and Song, H. O. Direct preference- policy optimization with- out reward modeling. Advances in Neural Information Processing Systems (NeurIPS), 36:70247-70266, 2023.
Azar, M. G., Munos, R., and Kappen, H. J. On the sample complexity of reinforcement learning with generative model. In Proceedings of the International Conference on Machine Learning (ICML), pp. 1707-1714, 2012.
The computational limitations presented in the paper suggest the need for less demanding notions of dominance when preferences are concerned. Furthermore, our work does not tackle the statistical complexity of learn- ing with preference feedback. Future works should address these issues. Specifically, it would be interesting to inves- tigate less demanding notions of dominance that consider, e.g., subset of all compatible utilitiie, and compare them with the one presented in this paper from the computational perspective. Moreover, in realistic scenarios, the preference relation is not given and should be learned from samples. Future studies could define methodologies to address both the preference elicitation problem (see, e.g., Wilde et al., 2018), and the uncertainty in the preference generation pro- cess. One such natural extension is to study the statistical complexity of a multi-objective problem in terms of (i) the uncertainty due to partial coverage of the preorder relation and (ii) the error due to the approximation.
Future Works.
Azar, M. G., Guo, Z. D., Piot, B., Munos, R., Rowland, M., Valko, M., and Calandricllo, D. A general theoretical paradigm to understand learning from human preferences. In Proceedings of the International Conference on Artifi- cial Intelligence and Statistics (AISTATS), pp. 4447-4455 PMLR, 2024.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., Das- Sarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. Training a helpful and harmless assistant with rein- forcement learning from human feedback, arXiv preprint arXiv:2204.0588 05562,, 2022.
Bowling, M., Martin, J. D., Abel, D., and Dabney, W. Set- tling the reward hypothesis. In Proceedings of the Inter- national Conference on Machine Learning (ICML), pp. 3003-3020. PMLR, 2023.
Boyd, S. and Vandenberghe, L. Convex optimization. Cam- bridge university press, 2004.
Impact Statement
Busa-Fekete, R. and Hüllermeier, E. A survey of preference- based online learning with bandit algorithms. In Algorith- mic Learning Theory (ALT), pp. 18-39. Springer, 2014.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Caceres, M., Cairo, M., Mumey, B., Rizzi, R., and Tomescu, A. I. Minimum path cover in parameterized linear time. arXiv preprint arXiv:2211.00 1.09559, 2022.
Acknowledgments
Censor, Y. Pareto optimality in multiobjective problems. Ap- plied Mathematics and Optimization, 4(1):41-59, 1977.
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 Research- Spoke 4- PE00000013 D53C22002388006.
Chalermsook, P., Lackhanukit, B., and Nanongkai, D. Graph products revisited: Tight approximation hardness of in- duced matching, poset dimension and more. In Proceed- ings of the ACM-SIAM symposium on Discrete algorithms (SODA), pp. 1557-1576. SIAM, 2013.
References
Abbeel, P. and Ng. A. Y. Apprenticeship learning via in- verse reinforcement learning. In Proceedings of the In- ternational Conference on Machine Learning (ICML), volume 69 of ACM International Conference Proceeding Series. ACM, 2004.
Chen, X., Zhong, H., Yang, Z.,, Wang, 7.,, and Wang, L. Kluman-in-the-loog Provably efficient preference-based reinforeement learning with general function approxima- tion. In Proceedings of the International Conference on Machine Learning (ICML), pp. 3773-3793. PMLR, 2022.
Cheng. W., Fürnkranz, J., Hüllermeier, E.,, and Park, S.HH. Preference-basee policy iteration: Leveraging preference learning for reinforcement learning. In Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pp. 312-327. Springer, 2011.
Akrour, R., Schoenauer, M., and Sebag, M. April: Active preference learning-basse based reinforcement learning. In Ma- chine Learning and Knowledge Discovery in Databases (ECML.PKDD). pp- 116-131. Springer, 2012.
9

---

Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback
Christiano, P. F,, Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems (NIPS), 30, 2017.
Ibarz, B., Leike, J., Pohlen, T., Irving, G., Legg, S., and Amodei, D. Reward learning from human preferences and demonstrations in atari. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
Coronato, A., Naeem, M., De Pietro, G., and Paragliola, G. Reinforcement learning for intelligent healthcare applica- tions: A survey. Artificial Intelligence in Medicine, 109: 101964, 2020.
Kaufmann, T., Weng, P., Bengs, V., and Hüllermeier, E. survey of reinforcement learning from human feedback. arXiv preprint 2tt.:2322..112922 2023.
Kiran, B. R., Sobh, I., Talpaert, V., Mannion, P., Sallab, A., Yogamani, S., and Pérez, P. Deep reinforcement learning for autonomous driving: A survey. IEEE Trans- actions Intelligent Transportation Systems (T-ITS), 23 (6):4909 4926, 2021.
Debreu, G. Representation of preference ordering by numerical function. Decision Processes, 3:159-165, 1954.
Dewey, D. Reinforcement learning and the reward engi- neering principle. In AAAI Spring Symposium Series, 2014.
Knuth, D. E. Art of Computer Programming, Volume 4, Fascicle The: Generating All Trees-History of Com- binatorial Generation. Addison Wesley Professional, 2013.
Dilworth, R. P. A decomposition theorem for partially or- dered sets. Classic papers in combinatorics, pp. 139-144, 1987.
Kober, J., Bagnell, A., and Peters, Reinforcement learning robotics: A survey. The International Journal of Robotics Research, 32(11) (0(1)):128-1277) 2013.
Du, Y., Watkins, O., Wang, Z., Colas, C., Darrell, T., Abbeel, P. Gupta, A., and Andreas, J. Guiding pretraining in reinforcement learning with large language models. In Proceedings of the International Conference on Machine Learning (ICML), pp. 8657-8677. PMLR, 2023.
Kritikakis, G. and Tollis, I. G. Fast and practical DAG decomposition with reachability applications. CoRR, abs/2212.03945, 2022.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Dushnik, B. and Miller, E. W. Partially ordered sets. Ameri- can Journal of Mathematics, 63(3):600-610, 1941.
Littman, M. L. On the complexity of solving markov de- cision problems. Proceedings of the International Con- ference on Uncertainty in Artificial Intelligence (UAI), 1995.
Evren, Ö. and Ok, A. On the multi-utility representa- tion of preference relations. Journal of Mathematical Economics, 47(4-5):554-563, 2011.
Felsner, S., Mustata, I., and Pergel, M. The complexity of the partial order dimension problem: Closing the gap. SIAM Journal on Discrete Mathematics 31(1); 172-189, 2017.
Lu, T., Pál, D., and Pál, M. Contextual multi-armed bandits. In Proceedings of the International Conference on Artifi- cial Intelligence and Statistics (AISTATS), pp. 482- JMLR, 2010
Fürkkranz, J., Hüllermeier, E.,, Cheng, W., and Park, S.- H. Preference based reinforcement learning: formal framework and policy iteration algorithm. Machine Learning, 89:123-11 126- 2012.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Ve- ness, J., Bellemare, M. G., Graves, A., Riedmiller, M. A., Fidjeland, A., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wier- stra, D., Legg, S., and Hassabis, D. Human-Level control through deep reinforcement learning. Nature, 518(7540): 929-533, 2015.
Glukhov, V. Reward is not enough: can we liberate ai from the reinforcement learning paradigm? arXiv preprint arXiv:2202.03192, 2022.
Ng, A. Y. and Russell, S. Algorithms for inverse rein- forcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pp. 663-670. Morgan Kaufmann, 2000.
Hayes, F., Radulescu, R., Bargiacchi, E., Källström, J., Macfarlane, M., Reymond, M., Verstracten, T., Zintgraf, L. M., Dazeley, R., Heintz, F., Howley, E., Irissappane, A. A., Mannion, P., Nowé, A., de Oliveira Ramos, G., Restelli, M., Vamplew, P., and Roijers, D. M. A practi- cal guide to multi-objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems (AAMAS), 36(1):26, 2022.
Nian, R., Liu, J., and Huang, B. A review on reinforcement learning: Introduction and applications industrial pro- cess control. Computers & Chemical Engineering, 139: 106886, 2020.
10

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
Ok, E. A. Utility representation of an incomplete preference relation. Journal of Economic Theory, 104(2):429 449, 2002.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Trotter, W. T. Combinatorics and partially ordered sets.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J.. Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P. F., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback. Advances in
Johns Hopkins University Press, 1992.
Vamplew, P., Smith, B. J., Källström, J., de Oliveira Ramos, G., Radulescu, R., Roijers, D. M., Hayes, C. F., Hentz, F., Mamnion, P., Libin, J. K., Dazeley, R., and Foale, Scalar reward not enough. pp. 839 841, 2023.
Neural Information Processing Systems (NeurIPS), 35: 17730-27744, 2022.
Von Neumann, J. and Morgenstem, O. Theory of games and economic behavior. Princeton University Press, 1947.
Pan, A., Bhatia, K., and Steinhardt, J. The effects of reward misspecification: Mapping and mitigating misaligned models. In International Conference on Learning Repre- sentations (ICLR), 2022.
Wilde, N., Kulić, D., and Smith, S. L.. Learning user pref- erences in robot motion planning through interaction. In IEEE International Conference on Robolics and Automa- tion (ICRA), pp. 619-626. IEEE, 2018.
Papadimitriou, C. H. and Tsitsiklis, N. The complexity of markov decision processes. Mathematics of Operations Research, 12 12(3):441-4555 1987.
Wilson, A., Fern, A., and Tadepalli, P. A bayesian approach for policy learning from trajectory preference queries. Ad- vances in Neural Information Processing Systems (NIPS), 25, 2012.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. A survey of preference-based reinforcement learning meth- ods. Journal of Machine Learning Research, 18(136): 1 1-46, 2017.
Radford, A. Improving language understanding by genera- tive pre-training. 2018.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. Direct preference optimiza- tion: Your language model is secretly reward model. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Xu, Y., Wang, R., Yang, L.,, Singh, A., and Dubrawski, Preference-based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems (NeurIPS), 1788-187944 2020.
Ramachandran, P., Liu, P. J., and Le, Q. V. Unsupervised pretraining for sequence to sequence learning. pp. 383- 391, 2017.
Yannakakis, M. The complexity of the partial order di- mension problem. SIAM Journal on Algebraic Discrete Methods, 3(3):351-358, 1982.
Saha, A., Pacchiano, A., and Lee, J. Dueling RL: reinforce- ment learning with trajectory preferences. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 206 of Proceedings of Machine Learning Research, pp. 6263-6289, PMLR, 2023.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538 1556, 2012.
Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. Provable offline preference-based reinforcement learning. In International Conference on Learning Representations, (ICLR), 2024a.
Silver, D., Singh, S., Precup, D., and Sutton, R. Reward is enough. Artificial Intelligence, 299:103535, 2021.
Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. Advances in Neural Information Processing Systems (NeurIPS), 33: 3008-3021, 2020.
Zhan, W., Uehara, M., Sun, W., and Lee, J. D. Provable poward-agnosti preference-based reinforcement learning. In International Conference on Learning Representations (ICLR), 2024b.
Zhao, W. X., Zhou, K., Li, J., Tang, T., Wang, X., Hou, Y., Min, Y., Zhang, B., Zhang, J., Dong. Z., Du, Y., Yang, C., Chen, Y., Chen, Z., Jiang, J., Ren, R., Li, Y., Tang, X., Liu, Z., Liu, P., Nie, J., and Wen, survey of large language models. CoRR, 2ttp/2333.1223 2023a.
Sutton, R. S. The reward hypothesis - incompletei- deas.net. http:://nccompltttett cs ualberta /atittaaaa/AAA/eeeaaaatttttttaa html, 2004.
net/rlai.

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
Zhao, Y., Joshi, R., Liu, T., Khalman, M., Saleh, M., and Liu, J. Slic-hf: Sequence likelihood calibration with human feedback. CoRR, abs/2305. 2023b.
Zoghi, M., Karnin, Z. S., Whiteson, S., and de Rijke, M. Copeland dueling bandits. In Advances in Neural Infor- mation Processing Systems (NIPS), pp. 307-315, 2015.
Zucker, M., Bagnell, J. A.. Atkeson, C. G., and Kuffner, An optimization approach to rough terrain locomo- tion. In JEEE International Conference on Robotics and Automation (ICRA), pp. 3589-3595. IEEE, 2010.
12

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
A. Omitted Proofs
Theorem 4.1. Let STETx T preorder over T. Then:
(i) there exists a dim(=Z)) -dimeessiinn compatible utility;
(it) no m-dimensional compatible utilities with m < <im(==) exist.
Proof. We limit the proof for the case in which we have an order. Indeed, if we have preorder, we can consider the order induced over the quotient set by the equivalence relation =7, as for equivalent trajectories we are forced to set the (aen(==)diimnestii
utility, Let D diiim=>>) for notational convenience. To this end, know that there exists set (ET, of D total orders such that ST= TT i.e, T Ty <> ViE [D] =', Since for total orders, compatible utilities exist, let us consider 7 R. compatible with ET, for every E [D] Let us now construct the D-dimensional utility u (UI....,up) We show that u compatible with the preorder =- Let T, 7 T, we have:
same value of the utility. Let us start with (i). We show the existence of a compatible
u(() ((T))su(T)) ViE [D] (T(T)
(15)
ViE [D] IT TT
(16)
< STT
(17)
where line (16) follows from the compatibilities of the scalar utilities u, with the corresponding εT, and line (17) follows from the construction of the partial preorder from the intersection of total preorders. For (ii), by contradiction, suppose there exists an m-dimensiooal compatible utility (u1...., mm)) with m < D. Let (,, be the set of m total orders induced by u1...., Mm: which is unique. We now show that IT n== T contradicting the definition of order dimension. Let T ET, we have:
u(T)
(18)
[m] un (T(T) ViE[mm] : T
(19)
(20)
where line (18) follows from the compatibility of the multi-dimensiee utility and line (20) follows from the compatibility of the scalar utilities.
Theorem 4.2. Let ST be a preorder over T. The construction of a minimal utility u compatible with ST is NP-hard.
Proof. We restrict to the case of orders. We reduce from the problem of deciding whether the order dimension of an order is > which known to be NP-hard (Yannakakis, 1982; Felsner et al., 2017).
Decision Problems.
ORDER DIMENSION (OD): given order = X' x X' and natural number &e YES if the order dimension is < k. MINIMAL UTILITY (MU): given an order < X' x X' and natural number ke N, YES if minimal compatible utility has dimensionality & k.
Reduction. We show that OD & MU (&p denotes Karp's reduction). The instance of MU is the same as for OD. trivial to show that the order dimension is & if and only if minimal compatible utility has dimensionality & k. n
Theorem 5.1. Let Ex be a total order over T, and let म, n' Illl be two policies. π Ey-weakly dominates if and only if holds that:
Vne [[1: Σ (44(0))
(8)
Furthermore, π. Et-strictly dominates T' if and only if. in addition to the above, it holds that:
3n' e [ Σ
(f)))
(9)
13

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
Proof. We prove the first statement, as the second one be proved analogously.
If. We start showing that:
a En
min II
Σ (dx())
=0
By contradiction, suppose the following condition to hold:
3n E [1 (1)(1)-d-1() d+)()) <0n ~0^
inf
(d> -dz, =0.
compatible with &
Define the utility function defined as:
M ifign* ffiin",
7(1)
for some M > We observe that 7 is compatible with T-- Then, we can write:
m
*
Σ
(i)
Σ (0) Σ d1)
i=
M
0,
where the last inequality holds under condition (i), which is absurd
Only if. Let us now prove that:
min Σ
(1)) = र'ÉnT.
(21)
The LHS of Equation (21) implies that, for every * E [[] it holds that:
(4)))))
(22)
and consequently, that the following holds as well:
Σ (i) <0,
(23)
f=
since, by definition of the policy occupancy, it holds that:
Σ (i))) -0.
(24)
Let be compatible utility function, and let me [[] be the index such that:
(u1)) 0 ifimm
(u1)) <0 im.
Then, we can rewrite:
Σ (d (4))
Σ
u(1) (d= - (0)
(()
14

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
m1
( u(m+1)
Σ
(i)
(25)
i=++1
where Equation (25) is obtained by applying the following reasoning. On the one hand, under Equation (22) and under the and by applying a chain reasoning, we can
compatibility of u, holds that demonstrate that:
Σ (1) (1) -
> uu (d+)))))))
Σ - (d)()))d=+())..
On the other hand, under Equation (23) and under the compatibility of it holds that u (47( -([T| -) (d=()7) dz (IT) 1)), and by applying similar chain reasoning as before, but in the opposite direction,
we get that:
(d.(1) - d+)(1)) 11
Σ
(d=(1) - dz)
i=++1
i=++1
Finally, by applying Equation (24) to Equation (25) we get that:
Σ (d. - (u(m) -u(m+ 1)) Σ (1))
where the last inequality holds under the compatibility of u, thus demonstrating the implication and concluding the proof.
Theorem 5.2. Let IT be a partial order over T and let n, I' be two policies. क =y-weakly dominates n' if and only if. for every realizer (e with meN of ST, holds that:
Vie[m]: n' EI,
where xt' E11,7 πt (resp. n' <11; denotes that x weakly (resp. strictly) Ser d-ominnnts (Definition 5.1) w.r.t the i-th total order the realizer of ST. Furthermore, स St-strictly dominates if and only if, in addition to the above, it holds that:
Bje [m]] n' n'S1.T..
(10)
Proof. We prove the statement for the weak dominance, since the statement for the strict dominance is analogous. We have:
n' 3n π
(26)
Yu compatible with ST: (
(27)
Y/ [TThhejm] realizer of < Vie [m]Vu, compatible with IT, J (T; [( u.) >
(28)
{{TTemmmm realizer of ST Vie [m] : $n,
(29)
where line (27) follows from Definition 4.2, line (28) follows from the fact that unique realizer of ST and from the component-wis wise order definition, and line (29) is obtained from Definition 4.2.
utility u determines
Theorem 5.3. Let ST be a partial order over T and let n, n' IT be two policies. æ Sy-weakly dominates n' if and only if. for every linear extension E of ST. it holds that:
Vne [ITII: E (V) (1))
(11)
SS-strictly dominates x' if and only if, in addition to the above, there exists linear extension E'y of ST such that:
3ne [[]]: Σ (dx (d, (1)) dn (1))
(12)
15

---

Towards Thcoretical Understanding of Sequential Decision Making with Preference Feedback
Proof. We prove the statement for the weak dominance, for the strict dominance analogous derivation holds. Recall that the set of all linear extensions of ST realizer of <t and that the union of all the realizes of < is such set. We have:
म' 31 T s.hffmm realizer of < Vie Vieemiimm] T En,T
(30)
Y T linear extension of <<:'' Sπ
(31)
b T linear extension of < Vn [[]]] > (4+())
(32)
where Equation (30) follows from Theorem 5.2, Equation (32) follows from Theorem 5.1.
Theorem 6.1. Let u, T: Rm be two m-dimensional utilities functions such that ||u uilB E)) Then, holds that C(u. u) <2/m"
Proof. Let π. fe II be two Pareto optimal policies w.r.t. and û, respectively. Let dz and dæ be the corresponding trajectory distributions. We consider matrices and à both in Rl7 constituted by a of m vectors (ug)je[m] and (ūz) je[m respectively. Then, for every component j [m]]. it holds:
JT, u() (uj. dz dz)
(Uj. dx dx) (u) (ūjjdd)
U ūشر új,daa + (ūj ug da> dj) +(ūg, dx da)
(A)
(B)
ū ugllæ + +ūj da dz)
(A)+(B)
where the inequality follows from the fact that both terms (A) and (B) can be bounded using Holder's inequality with || -|o and 111 and observing that || | = |d=ll =. Now, we apply the infimum:
inf Σ fEll [=[m]
(u dx - d
inf Rell*
(21 usllo + - -dz))
j+[m]
< 22 m u uFF
inf fEll*
Σ (aa - -d
(33)
( je[m]
< <2 u U
(34)
where line (33) follows from the application of Cauchy-Schwarze inequality after having observed that such ||- terms do not depend on â. and line (34) is due to the fact that the removed term is non-positive by definition of which is Pareto optimal w.r.t. â. Replicating the derivation by reversing the roles of and à leads to the result.
16


Reviews:
[{"review_id": "exqhAHjAGK", "reviewer": "Reviewer_g3qH", "summary": "This paper aims to build a theoretical basis linking the preference-based MDP, the utility-based MDP, and the reward-based MDP. Specifically, this paper formulates these three settings in Section 3, and discusses the connections between the preference-based MDP and the utility-based MDP in Section 4. In Section 5, this paper discusses the dominance and optimality with preferences; and finally, in Section 6, it discusses the relationship between the utility-based MDP and the reward-based MDP.", "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 the time spent reviewing our work. Below, our answers to the Reviewer's questions and concerns.\n\n> It seems that some parts of this paper are well-known results from the classical choice theory and existing work, such as Theorem 4.2. Might the authors clearly explain in the rebuttal what are the new results of this paper and what are the existing results?\n\nTo the best of our knowledge, **all the results presented in the paper are novel**. While we recognize that some of them, especially those presented in Section 4, can be obtained with non-complex arguments starting from existing ones, they have never been presented in the literature, as far as we know. Specifically, considering Theorem 4.2, while it is known that **computing the order-dimension is NP-hard** (Yannakakis, 1982), we claim that also **computing a minimal compatible utility is NP-hard**. This is proved with a simple, we recognize, but still novel, **reduction** to the problem of computing the order-dimension. We kindly ask the reviewer to provide references that already report any of the results we provide in this paper.\n\nWe refer the Reviewer also to the itemize in the answer below for further discussion.\n\n> My understanding is that this paper has discussed many different issues related to preference-based MDPS, utility-based MDPs, reward-based MDPs, as well as their connections. Several theorems have been developed; however, it seems that none of them is very hard to prove, and none of them is really counter-intuitive. This might reduce the significance of this paper.\n\nWe  honestly **disagree with the Reviewer on the fact that if a theorem is \"not very hard to prove\" or \"really counter-intuitive\" then this reduces its significance**. Beside being quite subjective notions, we wonder how many papers accepted at top-conferences (like ICML) really contain theorems that are \"very hard to prove\" and \"really counter-intuitive\". Just think to the bandit literature where the regret bound is often known before proving it (not counter-intuitive) and the proofs follow minor variations of techniques established by 20 years (not very hard to prove). Nevertheless, we report below two examples of theorems, in our opinion, that are either counter-intuitive or hard to prove:\n- Theorem 5.1: is *counter-intuitive* since it is not obvious that the condition of Definition 5.1, which involves an **existential quantification** over the compatible utilities (which are an infinite continuous set), can be verified by checking a finite number of inequalities.\n- Theorem 5.4: is *not simple to prove* since it involves a reduction to a non-standard NP-complete problem of **topological ordering in weighted DAG** (Gerbner et al., 2016) which requires a non-trivial construction. Furthermore, in the authors' opinion, the fact that checking policy dominance in a partial order is NP-complete is quite *counter-intuitive*.\n\nMoreover, there are results that are significant beyond this work. For example, Theorem 6.1 generalizes the **bisimulation lemmas** from the case of a scalar utility (or reward) to the case of multi-dimensional utilities. This requires defining a proper index to evaluate suboptimality on the Pareto frontier (function $\\mathcal{L}(\\boldsymbol{u},\\boldsymbol{\\widehat{u}})$).\n\n> In addition, from the perspective of writing, this paper is mathematically too heavy, and is not easy to read.\n\nWe thank the Reviewer for raising the point. We will make our best efforts to improve the redability of the paper, in particular for Sections 2 and 5, also leveraging the additional available page. We commit to improve it by lightening the notation (moving the not fundamental one to the appendix) and rewriting some parts which are less fluid.", "claims_and_evidence": "To the best of my knowledge, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "This paper does not have any experiment results.\n\nTo the best of my knowledge, the theoretical claims (theorems) in this paper seem to be correct.", "theoretical_claims": "I have checked the proofs in a high level. To the best of my knowledge, the proofs seem to be correct.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This paper has done a good job of literature review. However, I have some concerns about the novelty and significance of this paper, which I will list below.", "essential_references_not_discussed": "To the best of my knowledge, No.", "other_strengths_and_weaknesses": "I have some concerns about the novelty and significance of this paper. Specifically,\n\n1) It seems that some parts of this paper are well-known results from the classical choice theory and existing work, such as Theorem 4.2. Might the authors clearly explain in the rebuttal what are the new results of this paper and what are the existing results?\n\n2) My understanding is that this paper has discussed many different issues related to preference-based MDPS, utility-based MDPs, reward-based MDPs, as well as their connections. Several theorems have been developed; however, it seems that none of them is very hard to prove, and none of them is really counter-intuitive. This might reduce the significance of this paper.\n\nIn addition, from the perspective of writing, this paper is mathematically too heavy, and is not easy to read.", "other_comments_or_suggestions": "This paper has done a good job of literature review.", "questions_for_authors": "Please try to address the questions/weaknesses listed above.\n\n-----------------------------------------------\n\nI have read the authors' rebuttal, which has addressed some of the concerns listed above, especially the concerns about the novelties and technical contributions of this paper. I will increase my recommendation from 2 to 3.", "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": "YJ4UIiyy1c", "reviewer": "Reviewer_6i49", "summary": "The authors consider the setting of sequential decision-making problems in which only preferences over trajectories are provided, specifically partial (pre)orders. This allows for situations where comparisons of pairs of trajectories are not available (incomparabilities). After several definitions to precisely capture this setting, including the notion of utility-preference compatibility, the authors show how a multiobjective utility function can be constructed from the preorder and that constructing the utility function with the smallest dimensionality is NP-hard. Finally, the authors propose a quadratic program to approximate such a utility function with a reward function for an approximate MDP and provide a bound on the incurred error.", "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 the time spent reviewing our work, for understanding the relevance of the QP and of the error bound. Below, our answers to the Reviewer's questions.\n\n> As for inverse RL, I was surprised that the authors did not cite work that directly connects preference elicitation and inverse reinforcement learning.\n\nWe thank the Reviewer for raising this point. We have not included methods specific to the Inverse RL field in the related works of this paper due to the following reasoning:\n\n1. **IRL focuses on observing a behavior** that is assumed to be optimal and learning a reward function, whereas, according to our framework, we consider the case in which the **agent interacts with the environment, asking for preference feedback** to be used to estimate a reward and to improve its policy. For this reason, the two frameworks are different;\n2. Preference elicitation and IRL are related to the learning aspect of the problem, and, thus, to the statistical complexity of doing so, whereas, in this work, we focus on the different concepts of optimality and the computational complexity of estimating multi-dimensional utility and reward functions. In other words, we focus more on **computational complexity** rather than on **statistical complexity**. As we briefly discuss in the future works, one possible direction is to address learning with preference feedback when incomparabilities are possible. When tackling such a direction, it will then be necessary to compare with the literature of preference elicitation and IRL.\n\nHowever, we acknowledge that there exist works that combine both preference elicitation and IRL, such as (Rothkopf and Dimitrakakis, 2011). We added a discussion on this in the related works.\n\nRothkopf, C. A., and Dimitrakakis, C. Preference elicitation and inverse reinforcement learning. ECML-PKDD 2011.\n\n> Are there any problems and datasets that could be used to construct Markovian reward functions solving the quadratic program (eq. 13) and thereby provide a sense of the applicability of the present algorithm and the value of the error bound?\n\nIn principle, existing RL benchmarks could be adapted to accomodate the problem of solving the QP to estimate an approximated reward function. This can be done either by querying preference from real humans (see, e.g., Christiano et al., 2017) or by defining a synthetic expert (see, e.g., Akrour et al., 2012). One example of existing datasets which can be adapted to allow for incomparabilities are those based on the OpenAI Gym, which can be found in Minari (https://minari.farama.org/main/), from the Farama Foundation.\nRegarding LLMs, there exist datasets which, with the necessary adaptations, could be considered for what the Reviewer suggests. One such example is the *Preference Dissection* dataset (Li et al., 2024), which contains questions, pairs of answers, and features for each answer. Although the reported human preferences do not admit incomparabilities, synthetic preferences could be generated considering the answers and their features. An additional example is the *PKU-SafeRLHF* dataset (Ji et al., 2024), which contains questions and answers labelled in terms of harmfulness and correctness. Again, it would be necessary to generate synthetic preferences.\nIn conclusion, we believe that the definition of a standardized benchmark containing both standard RL tasks and language tasks, together with human-labelled datasets and synthetic parametric experts would be beneficial for the evaluation of future approaches to the problem of learning from preferences with incomparabilities.\n\nChristiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. NeurIPS 2017.\n\nAkrour, R., Schoenauer M., and Sebag M. April: Active preference learning-based reinforcement learning. ECML-PKDD 2012.\n\nLi, J., Zhou, F., Sun, S., Zhang, Y., Zhao, H., and Liu, P. Dissecting human and llm preferences. arXiv preprint arXiv:2402.11296, 2024.\n\nJi, J., Hong, D., Zhang, B., Chen, B., Dai, J., Zheng, B., Qiu, T., Li, B., and Yang, Y. PKU-SafeRLHF: Towards Multi-Level Safety Alignment for LLMs with Human Preference. arXiv preprint arXiv:2406.15513, 2024.", "claims_and_evidence": "I followed the proofs and could not find any mistakes but this is not my area of expertise.", "methods_and_evaluation_criteria": "There are no evaluations involving examples or simulations.", "theoretical_claims": "I followed the proofs and could not find any mistakes but this is not my area of expertise.", "experimental_designs_or_analyses": "No experiments were conducted.", "relation_to_broader_scientific_literature": "This is not my area of expertise, and I am not knowledgeable enough about preference-based RL and RL from human feedback. I was wondering about any potential canonical problems and datasets that could be used to construct Markovian reward functions solving the quadratic program (eq. 13) and thereby providing a sense of the applicability of the present algorithm and the value of the provided error bound.", "essential_references_not_discussed": "As for inverse RL, I was surprised that the authors did not cite work that directly connects preference elicitation and inverse reinforcement learning.", "other_strengths_and_weaknesses": "This is a theoretical paper that makes notions of utility-preference compatibility, policy dominance, and the connection between partial preorders on trajectories, utility functions, and reward functions in an approximate MDP precise, shows that establishing policy dominance in the very general case considered here is NP-hard, and provides a constructive algorithm for reward functions in an approximate MDP. This relates to preference-based RL and RL from human feedback. \n\nIt is difficult for me to assess how much of an advancement in the field this is, as I am not an expert in this area.", "other_comments_or_suggestions": "“in the realizer ofthe\"", "questions_for_authors": "Are there any problems and datasets that could be used to construct Markovian reward functions solving the quadratic program (eq. 13) and thereby provide a sense of the applicability of the present algorithm and the value of the error bound?", "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": "yDjbidjqjC", "reviewer": "Reviewer_xt7J", "summary": "This paper establishes a rigorous theoretical framework for sequential decision-making with preference feedback, where agents learn from comparative evaluations of trajectories rather than explicit reward signals. The authors make several key contributions:\n\n1. They model preference feedback using partial preorders between trajectories, enabling the formal characterization of incomparability phenomena that occur when trajectories cannot be meaningfully ranked.\n\n2. The research investigates systematic approaches to approximate preference relations using multi-objective utility functions.\n\n3. The authors develop a novel concept of preference-based policy dominance that operates independently of utility functions or rewards.\n\n4. They present an algorithm that efficiently approximates utilities using Markovian rewards, complete with quantifiable error bounds.\n\nTogether, these contributions create a principled framework connecting preferences, utilities, and Markovian rewards in sequential decision-making environments.", "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 the time spent reviewing our work and we appreciate the Reviewer's understanding of the relevance of the proposed framework. Below, our answers to the Reviewer's comments.\n\n> Some theoretical results largely follow or implied by existing known results (e.g., Theorem 4.2). While this work offers new insights for decision making with preference feedback, highlighting the technical novelty of the proof would further strengthen the paper.\n\nWhile we recognize that some of the results, especially those presented in Section 4, can be obtained with non-complex arguments starting from existing ones, **they have never been presented in the literature, as far as we know**. Concerning the **technical novelty**, we report below two examples of results we present that bring technical novelty:\n- Theorem 5.4: its proof involves a reduction to a non-standard NP-complete problem of **topological ordering in weighted DAG** (Gerbner et al., 2016) which requires a non-trivial construction.\n- Theorem 6.1: it **generalizes the bisimulation lemmas** from the case of a scalar utility (or reward) to the case of multi-dimensional utilities. This requires defining a proper index to evaluate suboptimality on the Pareto frontier, which is the function $\\mathcal{L}(\\boldsymbol{u},\\boldsymbol{\\widehat{u}})$.\n\nWe have rewritten the Original Contribution paragraph to better highlight these aspects.\n\n> While establishing a solid theoretical foundation, the paper places less emphasis on developing practical algorithms that could be immediately applied to real-world problems.  \n\n> The paper is purely theoretical, with no empirical evaluation to validate how well the proposed methods perform in practice compared to existing RLHF methods. This limitation is significant for such an application-driven area.\n\nWe take the liberty to answer both questions together since our choices are justified by a specific aim. Preference-based RL and/or RLHF is, as the Reviewer notes, \"such an application-driven area\". However, the understanding of the intimate properties of the preference relations is currently missing. This paper precisely aims to **make a step forward the understanding of the theoretical properties of preference relations** and its limitations (that are significant, as we show) from a computational perspective. This, in our view, represents a fundamental step to, for instance, avoid that practitioners attempt to address problems which turn out to be provably hard (e.g., checking policy dominance for partial orders). This is the reason why we decided not to (1) propose algorithms and (2) conduct an experimental validation. Clearly, building on our work, and aware of the computational limitations, future works should formalize real-world problems according to this setting, and design algorithms capable of solving them, under **certain assumptions**, to achieve convenient computational (and, subsequently, statistical) guarantees.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "This is a pure theory paper.", "theoretical_claims": "I have reviewed the high-level proof idea and did not find obvious issues.", "experimental_designs_or_analyses": "This paper contains no experiments.", "relation_to_broader_scientific_literature": "These results build upon previous work in theoretical computer science/game theory and provide new findings for RLHF.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths**\n- The paper establishes a comprehensive framework that connects preferences, utilities, and rewards in sequential decision-making, filling an important gap in the theoretical understanding of preference-based learning.\n- Unlike many existing approaches, the authors explicitly model preferences as partial preorders, allowing for incomparabilities that commonly occur with human preferences but are often overlooked in the literature.\n- The work provides valuable insights into the computational complexity of various transformations between preferences, utilities, and rewards, highlighting fundamental challenges in this domain.\n\n\n**Weaknesses**\n- Some theoretical results largely follow or implied by existing known results (e.g., Theorem 4.2). While this work offers new insights for decision making with preference feedback, highlighting the technical novelty of the proof would further strengthen the paper.\n- While establishing a solid theoretical foundation, the paper places less emphasis on developing practical algorithms that could be immediately applied to real-world problems.\n- The paper is purely theoretical, with no empirical evaluation to validate how well the proposed methods perform in practice compared to existing RLHF methods. This limitation is significant for such an application-driven area.\n\n---\n\nOverall, I appreciate the new theoretical framework developed by the authors and would advocate for acceptance.", "other_comments_or_suggestions": "na", "questions_for_authors": "na", "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": "fLZS2ujmGd", "reviewer": "Reviewer_dYAR", "summary": "This paper considers sequential decision making with preference feedback. The authors build a theoretical formulation linking preferences, utilities (i.e., non-Markovian rewards), and Markovian rewards, and then study the connections between them. First, the authors model preference feedback using a partial (pre)order over trajectories, which enables the presence of incomparabilities. Second, the authors study how a preference relation can be approximated by a multi-objective utility. They introduce a notion of preference-utility compatibility and analyze the computational complexity of this transformation, showing that constructing the minimum-dimensional utility is NP-hard. Third, the authors propose a new concept of preference-based policy dominance that does not rely on utilities or rewards, and analyze the computational complexity of assessing it. Fourth, the authors develop a computationally efficient algorithm to approximate a utility using (Markovian) rewards, and quantify the error in terms of the suboptimality of the optimal policy induced by the approximating reward. This paper aims to lay a foundation for sequential decision making from preference feedback, with promising potential applications in RL from human feedback.", "questions": "", "limitations": "", "rating": 2, "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 the time spent reviewing our paper. Below, our answers to the Reviewer's comments and concerns.\n\n> The writing and readability of this paper should be improved. This paper is hard to follow. The abstract is a bit long.\n\nWe thank the Reviewer for raising this point. We will make our best efforts to improve the readability of the paper, in particular for Sections 2 and 5, also leveraging the additional available page. We commit to improve it by lightening the notation (moving the not fundamental one to the appendix) and rewriting some parts which are less fluid.\n\n> This paper seems to be a pure theoretical work, which defines a MDP based on partial order and proves some of its properties. What is the motivation of the proposed MDP formulation based on partial order and utility? How can this MDP formulation relate and contribute to real-world applications, e.g., the RL with human feedback and LLM applications?\n\n> There is no new algorithm proposed, and there is no experiment. The contribution is purely theoretical, i.e., a new MDP formulation defined based on partial order and utility, which is limited.\n\nWe thank the Reviewer for raising the point. We believe that our theoretical formulation of preference-based MDP (especially with partial orders) is **strongly motivated by real-world applications**. We provide arguments for this statement below:\n\n1. In the real-world, a **preference feedback is a much more realistic feedback than both rewards (used in RL) and demonstrations (used in Inverse RL)**. Consider, for example, LLM applications: it is quite natural of a human to state which of two proposed answers they prefer, rather than trying to define a reward function for answer generation, or asking the human to demonstrate which answer they would want to receive.\n\n2. Furthermore, it is as realistic to consider that **a human might not be able to state a clear preference between any pair of proposed trajectories**. Regarding LLM applications, if we were to ask a human to state their preference between two answers, the human may  evaluate different aspects, e.g., the length, the clarity, the correctness, and the harmfulness of the answers. Thus, it is possible that the human may not be able to state a clear preference. This requires modeling **incomparabilities** among trajectories. One natural approach to address this need is to consider **partial order relations** among trajectories. Another example is the well-known problem of autonomous driving, where we want to balance terms of travel time and travel comfort. Clearly, these two objectives are in contrast, as reckless driving brings the passenger to the destination quicker but at the cost of their comfort, whereas a completely comfortable drive may take too much time to reach the destination. By considering a partial order relation over trajectories, we are able to capture the multi-dimensionality of such a problem. The preference-based MDP (PbMDP) framework we propose in this paper allows us to formally define these problems.  \n\n3. Finally, having motivated **why** we need a framework to generalize preferences to allows for incomparabilities, we ask **what** we are able to learn. Thus, we propose novel concepts of **dominance between policies**, and study the computational complexity of evaluating them. The NP-completeness results we propose constitute a computational barrier on **what** is possible to ask of a (practical) algorithm. Then, we study a way to approximate this problem, rendering it computationally tractable, at the cost of an approximation error.  \n\nWe will leverage the additional page to include a discussion on this point, as we recognize the importance of motivating a novel framework from real-world applications.", "claims_and_evidence": "The claims made in this paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense.", "theoretical_claims": "The theoretical results look reasonable, but I didn’t go through every proof.", "experimental_designs_or_analyses": "There is no experiment in this paper.", "relation_to_broader_scientific_literature": "This paper is relevant to the literature.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\n\n1. This paper proposes a theoretical formulation which links preferences, utilities (i.e., non-Markovian rewards), and Markovian rewards, and then study the connections between them.\n2. The authors model preference feedback using a partial (pre)order over trajectories and propose a new notion of preference-based policy dominance. In addition, the authors study the computational complexity of the transformation and assessment for the proposed notions in this preference-based and utility-based MDP formulation.\n\nWeaknesses:\n\n1. The writing and readability of this paper should be improved. This paper is hard to follow. The abstract is a bit long.\n2. This paper seems to be a pure theoretical work, which defines a MDP based on partial order and proves some of its properties. What is the motivation of the proposed MDP formulation based on partial order and utility? How can this MDP formulation relate and contribute to real-world applications, e.g., the RL with human feedback and LLM applications?\n3. There is no new algorithm proposed, and there is no experiment. The contribution is purely theoretical, i.e., a new MDP formulation defined based on partial order and utility, which is limited.", "other_comments_or_suggestions": "Please see the weaknesses above.", "questions_for_authors": "Please see the weaknesses above.", "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 provides a theoretical framing and analysis of problems that connect trajectory-based preferences, trajectory-based utilities, and Markov rewards. The work is largely theoretical, introducing several new notions and proving several complexity and approximation results. The overall contribution is framed as providing a foundation for sequential decision making from preference feedback. Overall, the reviewers appreciated the potential contributions of the paper, but raised several questions concerning the overall significance and surprise of the results, the lack of empirical evaluation (some of the results do avail themselves of such), and the fact that the paper, while using RLHF as one of its motivations, does not make anything other than superficial connections to that literature. The authors response (and other comments) were helpful, but did not fully alleviate the concerns of significance. Overall, this paper makes a reasonable contribution, but whether it meets the ICML bar is at issue.
Decision: Accept (poster)