Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback
Authors: Han Shao
Lee Cohen
Avrim Blum
Yishay Mansour
Aadirupa Saha
Matthew Walter
Venue: NeurIPS 2023 poster (2023)
Keywords: preference learning
algorithms
linear model
Markov decision processes
learning theory
multi-objective decision making
preference elicitation
TL;DR: Preference learning approach for multi-objective decision making - algorithms and theoretical guarantees

Abstract: In this work, we propose a multi-objective decision making framework that accommodates different user preferences over objectives, where preferences are learned via policy comparisons. Our model consists of a known Markov decision process with a vector-valued reward function, with each user having an unknown preference vector that expresses the relative importance of each objective. The goal is to efficiently compute a near-optimal policy for a given user. We consider two user feedback models. We first address the case where a user is provided with two policies and returns their preferred policy as feedback. We then move to a different user feedback model, where a user is instead provided with two small weighted sets of representative trajectories and selects the preferred one. In both cases, we suggest an algorithm that finds a nearly optimal policy for the user using a number of comparison queries that scales quasilinearly in the number of objectives.

Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback
Han Shao
Lee Cohen TTIC
Avrim Blum TTIC avrimêttic. edu
TTIC
han@ttic.edi edu
leecohencs@gaillcc com
Yishay Mansour
Aadirupa Saha TTIC aadirupa@ttic.edu
Matthew R. Walter TTIC mwalterSttic.en edu
Tel Aviv University and Google Research mansour, wisshyygmaaaallal......aa com
Abstract
In this work, we propose multi-objective decision making framework that accom- modates different user preferences over objectives, where preferences are learned via policy comparisons. Our model consists of known Markov decision process with a vector-valued reward function, with each user having an unknown prefer- ence vector that expresses the relative importance of each objective. The goal is to efficiently compute a near-optimal policy for a given user. We consider two feedback models. We first address the case where user is provided with policies and returns their preferred policy as feedback. We then move to different user feedback model, where user is instead provided with two small weighted sets of representative trajectories and selects the preferred one. In both cases, we suggest algorithm that finds nearly optimal policy for the user using number of comparison queries that scales quasilinearly in the number of objectives.
Introduction
Many real-world decision making problems involve optimizing over multiple objectives. For example, when designing an investment portfolio, one's investment strategy requires trading off maximizing expected gain with minimizing risk. When using Google Maps for navigation, people concerned about various factors such as the worst and average estimated arrival time, traffic conditions, road sur- face conditions (e.g., whether or it paved), and the scenery along the way. As the advancement of technology gives rise to personalized machine learning (McAuley, 2022), in this paper, we design efficient algorithms for personalized multi-objective decision making.
While prior works have concentrated on approximating the Pareto- Pareto-optimal solution set' (see Hayes al. (2022) and Roijers al. (2013) for surveys), aim to find the optimal personalized policy for user that reflects their unknown preferences over & objectives. Since the preferences are unknown, we need elicit users' preferences by requesting feedhack selected policies. The problem of eliciting preferences has been studied in Wang et al. (2022) using strong query model that provides stochastic feedback on the quality of single policy. In contrast, work focuses query model, comparison queries, which query the user's preference over two selected policies, e.g.. 'do you prefer policy which minimizes average estimated arrival time policy which minimizes the number of turns?'. Our goal is to find the optimal personalized policy using as few queries as possible.
natural and intuitive
The Pareto optimal solution contains optimal personalized policy for every possible user preference.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To the best of our knowledge, we are the first to provide algorithms with theoretical guarantees for specific personalized multi-objective recision-making via policy comparisons.
Similar to prior works on multi-objective decision making, we model the problem using a finite- horizon Markov decision process (MDP) with a k-dimensional reward vector, where each entry is non-negative scalar reward representative of one of the k objectives. To account for user preferences, we assume that user is characterized by a (hidden) k-dimensional preference vector with non- negative entries, and that the personalized reward of the user for each state-action is the inner product between this preference vector and the reward vector (for this state-action pair). We also distinguish between the k- k-dimensional value of a policy, which is the expected cumulative reward when selecting actions according to the policy, and the personalized value of a policy, which is the scalar expected cumulative personalized reward when selecting actions according to this policy. The MDP is known to the agent and the goal is to learn an optimal policy for the personalized reward function (henceforth, the optimal personalized policy) of a user via policy comparative feedback.
Comparative feedback. If people could clearly define their preferences over objectives (e.g.. "my preference vector has 3 for the scenery objective, 2 for the traffic objective, and 1 for the road surface objective"), the problem would be easy-one would simply use the personalized reward function as a scalar reward function and solve for the corresponding policy. In particular, a similar problem with noisy feedback regarding the value of single multi-objectiv policy (as mapping from states to actions) has been studied in Wang et al. (2022). As this type of fine-graing grained preference feedback difficult for users to define, especially in environments where sequential decisions are made, we restrict the agent to rely solely on comparative feedback. Comparative feedback is widely used in practice. For example, ChatGPT asks users to compare two responses to improve its performance. This approach is more intuitive for users compared to asking for numerical scores of ChatGPT responses.
Indeed, as knowledge of the user's preference vector is sufficient to solve for their optimal person- alized policy, the challenge is to learn a user's preference vector using minimal number of easily interpretable queries. We therefore concentrate on comparison queries. The question is then what exactly compare? Comparing state-action pairs might not be a good option for the aforementioned tasks-wher is the meaning of two single steps in route? Comparing single trajectories (c.g.. routes in Google Maps) would not be ideal either. Consider for example two policies: one randomly generates either (personalized) GOOD or (personalized) BAD trajectories while the other consistently generates (personalized) MEDIOCRE trajectories. By solely comparing single trajectories without considering sets of trajectories, we cannot discern the user's preference regarding the two policies.
Interpretable policy representation. Since we are interested in learning preferences via policy comparison queries, we also suggest an alternative, more interpretable representation of a policy. Namely, we design an algorithm that given an explicit policy representation (as a mapping from states to distributions over actions), returns weighted set of trajectories of size at most k + 1, such that its expected return is identical to the value of the policy.? 2 It immediately follows from our formalization that for any user, the personalized return of the weighted trajectory set and the personalized value of the policy are also identical.
In this work, we focus on answering two questions:
(1) How to find the optimal personalized policy by querying as few policy comparisons as possible? (2) How can we find a more interpretable representation of policies efficiently?
Contributions. In Section 2, we formalize the problem of eliciting user preferences and finding the optimal personalized policy via comparative feedback. As an alternative to an explicit policy representation, we propose a weighted trajectory set as a more interpretable representation. In Section 3, we provide an efficient algorithm for finding approximate optimal personalized policy, where the policies are given by their formal representations, thus answering (1). In Section 4, we design two efficient algorithms that find the weighted trajectory set representation of policy. Combined with the algorithm in Section 3, we have an algorithm for finding an approximate optimal personalized policy when policies are represented by weighted trajectory sets, thus answering (2).
Related Work. Multi-objective decision making has gained significant attention in recent years (see Roijers et al. (2013); Hayes et al. (2022) for surveys). Prior research has explored various approaches,
AA return of a trajectory is the cumulative reward obtained in the trajectory. The expectation in the expected return of a weighted trajectory set is over the weights.
2

---

such as assuming linear preferences or Bayesian Settings, or finding an approximated Pareto frontier. However, incorporating comparison feedback (as was done for Multi-arm bandits or active learning. e.g., Bengs et al. (2021) and Kane et al. (2017)) allows us a more comprehensive and systematic approach to handling different types of user preferences and provides (nearly) optimal personalized decision-making outcomes. We refer the reader to Appendix A for additional related work.
Problem Setup
Sequential decision model. We consider a Markov decision process (MDP) known' to the agent represented by tuple (S, A, so. P. R. H), with finite state and action sets, S and A. respectively, an initial state 8o E S, and finite horizon H E N. For example, in the Google Maps example a state is an intersection and actions are turns. The transition function P : S x A H Simplex maps state-action pairs into a state probability distribution. To model multiple objectives, the reward function R : S x A + [o, 1] maps every state-action pair to a k-dimensional reward vector, where each component corresponds
one of the objectíves (e.g., road surface condition, worst and average estimated arrival time). The return of a trajectory T = (80, 8H- 811) is given by (T)) E R(st,a)). ae).
A policy π is mapping from states distribution over actions. We denote the set of policies by II. The value of a policy म, denoted by V", is the expected cumulative reward obtained by executing the policy π starting from the initial state, Su- Put differently, the value of π is V
(=(ss)= =0 E R(S,, ((s)) E [0, H!},, where S, is the random state at time step t when executing æ, and the expectation is over the randomness of P and æ. Note that V = E, [+(r)] where 7 = (Su, π (su), . (SH Sh) is a random trajectory generated by executing æ
We assume the existence of a "do nothing" action on E A. available only from the initial state 8o. that has zero reward for each objective R(5o, un)
and keeps the system in the initial state, i.e., P(#o 80, (g) = (e.g., this action corresponds to not commuting or refusing to play in a chess game.)*. We also define the (deterministic) "do nothing" policy To that always selects action ao and has a value of V = O. From a mathematical perspective, the assumption of "do nothing" ensures that 0 belongs to the value vector space {VT|T π E 11), which is precisely what we need.
1l2 S vTH for every policy и. For convenience, we denote Cv = Vkel. We denote by d < the rank of the space spanned by all the value vectors obtained by 11, i.e., d == rank
Since the rewards are bounded between [0, 1]. have that 1 S ||V*
I1})).
Linear preferences. To incorporate personalized preferences over objectives, we assume each user is characterized by an unknown k-dimensional preference vector w" E R with a bounded norm 1 1< ||w")] 11, I C. for some (unknown) C. 2 1. We avoid assuming that C.u to accommodate for general linear rewards. Note that the magnitude of w" does not change the personalized optimal policy but affects the "indistinguishabilit"" in the feedback model. By not normalizing ||w" 1l2 = 1, we allow users to have varying levels of discernment. This preference vector encodes preferences over the multiple objectives and as a result, determines the user preferences over policies.
Formally, for a user characterized by w", the personalized value of policy π is (w", V*) E We denote by π- := arg ,ax, (w*, V*) and v² := (w", (w",V"") the optimal personalized policy and its corresponding optimal personalized value for a user who is characterized by w". We remark that the "do nothing" policy To (that always selects action an) has a value of V/8 = 0, which implies a personalized value of (w", V=a 0 for every w For any two policies πi and ne, the user characterized by w" prefers over 22 if (w", V /=a) > O. Our goal is to find the optimal personalized policy for given user using as few interactions with them as possible.
Comparative feedback. Given two policies T2, the user returns ग. > 72 when- ever (w- V V=2) > e; otherwise, the user returns "indistinguishable" (i.e., whenever (ww,, Vxi V=> < c). Here e > 0 measures the precision of the comparative feedback and
II the MDP is unknown, can approximate the MDP and apply the results of this work in the approximated MDP. More discussion included in Appendix 5.
"We remark that the "do nothing" action require domain-spectnn knowledge, for example in the Google maps example the "do nothing" will be to stay put and in the ChatGPT example the "do nothing" is answer nothing.
3

---

is small usually. The agent can query the user about their policy preferences using two different types of policy representations:
1. Explicit policy representation of m: An explicit representation of policy as mapping, π : - Simplex
2. Weighted trajectory set representation of A k-sized set of trajectory-weight pairs {(i, Ta 7,)); 1: for some Λ < k + such that (i) the weights pI.....PA. Px are non-negative and sum to 1; (ii) every trajectory in the set is in the support" of the policy π.; and (iii) the expected return of these trajectories according to the weights is identical to the value of æ, i.e., V* = 1 (T;( Such comparison could be practical for humans. E.g., in the context of Google Maps, when the goal is to get from home to the airport, taking specific route takes 40 minutes 90% of the time, but it can take 3 hours in case of an accident (which happens w.p. 10%) vs. taking the subway which always has a duration of 1 hour.
In both cases, the feedback is identical and depends the hidden precision parameter As result, the value of c will affect the number of queries and how close the value of the resulting personalized let the agent decide in advance
policy is to the optimal personalized value. Alternatively, maximal number of queries, which will affect the optimality of the returned policy.
Technical Challenges. In Section 3, we find an approximate optimal policy by O !) queries. To achieve this, we approach the problem in two steps. Firstly, we identify a set of linearly independent policy values, and then we estimate the preference vector w" using linear program that incorporates comparative feedback. The estimation error of wt usually depends on the condition number of the linear program. Therefore, the main challenge we face is how to search for linear independent policy values that lead to a small condition number and providing guarantee for this estimate.
In Section 4, we focus on how to design efficient algorithms to find the weighted trajectory set representation of a policy. Initially, we employ the well-known Carathéodory's 's theorem, which yields an inefficient algorithm with a potentially exponential running time of |.s H Our main challenge lies in developing an efficient algorithm with running time of (poly H [S] [A)). The approach based on Carathéodory's 's theorem treats the return of trajectories as independent k-dimensional vectors, neglecting the fact that they are all generated from the same MDP. To overcome this challenge, leverage the inherent structure of MDPs.
3 Learning from Explicit Policies
In this section, we consider the case where the interaction with user is based on explicit policy comparison queries. We design an algorithm that outputs a policy being nearly optimal for this user. For multiple different users, we only need to run part of the algorithm again and again. For brevity, we relegate all proofs to the appendix.
If the user's preference vector w" (up to positive scaling) is given, then one can compute the optimal policy and its personalized value efficiently, c.g., using the Finite Horizon Value Iteration algorithm. In our work, w" is unknown and we interact with the user to learn w through comparative feedback. Due to the structure model that is limited to meaningful feedback only when the compared policy values differ at least c, the exact value of w² cannot be recovered. We proceed by providing high-level description of our ideas of how to estimate w".
(1) Basis policies: We find policies TI,..., TT, and their respective values, V*i ..... VT E [0, H & such that their values are linearly independent and that together they span the entire space of value vectors. These policies will not necessarily be personalized optimal for the current user, and instead serve only as building blocks to estimate the preference vector, w=. In Section 3.1 we describe an algorithm that finds set of basis policies for any given MDP.
(2) Basis ratios: For the basis policies, denote by a; >> 0 the ratio between the personalized value of a benchmark policy, T2, to the personalized value of T i.e.,
Vi E [d - 1] a4 (w", V*L (w", V=L1).
'we require the trajectories in this set to be in the support of the policy, avoid trajectories that do not make sense, such as trajectories that "teleport" between different unconnected states (e.g.. commuting at mph in Manhattan in one state and then at 40 mph New Orleans for the subsequent state). Recall that d E k is the rank of the space spanned by all the value vectors obtained by all policies.

---

We will estimate â; of a; for all E [d- 1] using comparison queries. A detailed algorithm for estimating these ratios appears in Section 3.2. For intuition, if we obtain exact ratios ā a, for every i [d 1). then we can compute the vector w | as follows. Consider the d 1 equations and d - 1 variables in Eq (1). Since d is the maximum number of value vectors that are linearly independent, and V .... V*a form a basis, adding the equation ||m||| = yields d independent equations with d variables, which allows us to solve for w². The details of computing an estimate of w" are described in Section 3.3.
3.1 Finding a Basis of Policies
In order to efficiently find d policies with d linearly independent value vectors that span the space of value vectors, one might think that selecting the l policies that each optimizes one of the k objectives will suffice. However, this might fail-in Appendix N. we show an instance which these & value vectors are linearly dependent even though there exist & policies whose values span space of rank k.
Moreover, our goal is to find not just any basis of policies, but basis of policies such that (1) the personalized value of the benchmark policy (w", V will be large (and hence the estimation error of ratio ag |ā: as|. will be small), and (2) that the linear program generated by this basis of policies and the basis ratios will produce good estimate of w".
Choice of TI Besides linear independence of values, another challenge is find a basis of policies to contain a benchmark policy, Ti (where the index is wlog) with a relatively large personalized value, (w", V**), so that ū; 's error is small (e.g., in the extreme case where (w", V O, we will not be able to estimate o:)).
For any Rt we use x" denote policy that maximizes the scalar reward (w, R). i.c..
π "
arg max (w., VT).
well
and by vt = (w, V*") to denote the corresponding personalized value. Let e1.....,e, ex denote the standard basis. To find I with large personalized value (w", V= we find policies Th that maximize the j-th objective for every j= L,..., k and then query the user to compare them until we find a x with (approximately) a maximal personalized value among them. This policy will be our benchmark policy, T.. The details are described in lines 1-6 of Algorithm 1.
Choice of T2...., T.. After finding Ti, next search the remaining d - polices T Fa sequentially (lines 8-13 of Algorithm 1). For i= 2...... d, we find a direction u; such that (i) the vector u, orthogonal to the space of cur- rent value vectors span VT!,.. ...., (=--1), 1. and (ii) there exists policy ग, such that V* has significant component in the direction of u, Condition (i) is used guarantee that the policy T; has a value vector linearly independent of span (V*I,... V 1). Condition (ii) is used to cope with the error caused by inaccurate ap- proximation of the ratios â. Intuitively, when I0,V - V* l|2 < 6, the angle between ā, V V and a; V=L / could be very large, which results in an inaccurate esti- mate of w" in the direction of a; VT V For example, if 7 e1 and V e1 1 "; ce; for i = 2...., k, then Tı n. are "indis- tinguishable" and the estimate ratio ā;-1 can be 1. Then the estimate of wn by solving linear equations in Eq (1) is (1, O........ 0), which could be far from the true w² Finding u, 's in which policy values have large component can help with this problem.
Algorithm 1 Identification of Basis Policies
1: initialize n² + R
2: for 2..... k do
3: compare π and T
4: 7 > _e" then n0' + T
5: end for
prot || la
6: Ti
+ T and U1
2..... k do 8: arbitrarily pick an orthonormal basis,
7: for i = 2 ................................
Pl, Pk+ 1- for
span (V": --
9: Jmax
arg maxxjelk-1-- 1- max(|ues|, P,/0pp()).
10:
if max (JuPbmox) , Pomax Pamax]] 1) > 0 then
11:
T4 + T Pomax if Potoax
> 10 Premax |;
otherwise Th Pimmax
Ui fo-txo Pimax
12: else
13:
return (TI, ..), (u1, .2....)
14: end if
15:
end for
Algorithm provides a more detailed description of this procedure. Note that if there are n different users, we will run Algorithm I at most & times instead of n times. The reason is that Algorithm
5

---

1 only utilizes preference comparisons while searching for (lines 1-6), and not for .2...., (which contributes the k2 factor in computational complexity). As there are at most is candidates for иi namely nh, ,.... T* we execute lines 1-6 of Algorithm I for rounds and lines 8-13 for only & rounds.
3.2 Computation of Basis Ratios
As we have mentioned before, comparing basis policies alone does not allow for the exact computation of the a; ratios as comparing TT nT can only reveal which is better but not how much. To this end. we will use the "do nothing" policy to approximate every ratio O; up to some additive error [o;; odl using binary search over the parameter ã₂ E [0, C.) for some C. 2 (to be determined later) and comparison queries of policy #1+1 with policy 0, + (1 ã: To if o; Σ 1 (or comparing #1 and a. T++1 + (1 _ Aoo instead if à; > 1). Notice that the personalized value of बे + (1-60 (1-ā,) is identical to the personalized value of тT multiplied by ā We stop once â, is such that the user returns "indistinguishable" Once stop, the two policies have roughly the same personalized value,
if a 1, āa a, (w", V (w", V*H+1) c if 1, (w", v
1 ā,
(w" VTulyy Sc. (3)
Eq (1) combined with the above inequality implies that |ā ail (w", V=L) I Cae. Thus, the approximation error of each ratio is bounded by |ā; oul S (wry. To make the procedure
Cot
will terminate, need set C. 2 (a0 Vo since a; 's must lie in the interval [0, (w V Upon stopping binary search once Eq (3) holds, it takes at most (d (w" Vm) /e)) comparison queries to estimate all the a, ss.
Due to the carefully picked in Algorithm 1, we can upper bound upper bound for jā arl by selecting C. 2k:
1² (wu V013 by 2k and derive an
=² 26 Lemma 1. When <
we have v² (w.,V=I) I 2k, and Tā; asl S
for every E [d] 4k 3'
In what follows we set C. 2k: The pseudo code of the above process of estimating as'' is is deferred to Algorithm 3 in Appendix C.
3.3 Preference Approximation and Personalized Policy
We move on present algorithm that estimates w" and calculates a nearly optimal personalized policy. Given the n;'s 's returned by Algorithm I and the â 's returned by Algorithm 3, consider a matrix Ā E dx with 1st row T and the ith row (ā;-1 V V=:)T for every i 2,...,d dd Let w be "" solution Ar C1. We will show that @ is good estimate of w/ (V") and that n is nearly
optimal personalized policy. In particular, when is small, we have (wē, VT) (w', VTy (eb)) for every policy т. Putting this together, we derive the following theorem.
Theorem 1. Consider the algorithm of computing À and any solution w to Ax e and outputting the policy π. = arg max (w. V*), which is the optimal personalized policy for preference vector
@. Then the output policy Th satisfying that v² - -Kw", (W=,V=') V=*) S ((V++1) d+ ct)
using
( (og()/()) comparison queries.
Computation Complexity We remark that Algorithm solves Eq (2) for the optimal policy in scalar reward MDP at most O(k2) ) times. Using, c.g., Finite Horizon Value iteration to solve for the optimal policy takes O(H ||| [A) steps. However, while the time complexity takes to return the optimal policy for single user is O(k2 |||//||1 ||| + & log(( ))) considering n different users rather than one results in overall time complexity of O( +
+ nı lo)(
Proof Technique. The standard technique typically starts by deriving an upper bound on || w* l| and then uses this bound to upper bound sup, (ūē VT (w", VT)l as Cy || w" w"ll.. However,
We write ā. + (1 @T) to indicate that is used with probability ā. and that mo is used with probability 1 ā..

---

this method fails to achieve a non vacuous bound in case there are two basis policies that are close to each other. For instance, consider the returned basis policy values: V (1, 0). V (1. 1. 0). and V* = (1, 0, 17) for some 1) > O. When 7) is extremely small, the estimate i becomes highly inaccurate the direction of (0, 0, 1), leading to large || - -== Il.- Even in such cases, we can still obtain a non-vacuous guarantee since the selection of V*a (line 11 of Algorithm 1) implies that no policy in II exhibits a larger component in the direction of (0, 0, 1) than TT.
Proof Sketch, The analysis of Theorem 1 has two parts. First, as mentioned in Sec 3.1, when I|o, V* ||| < c. the error of Øi+1 can lead to inaccurate estimate of w" in direction a; o;V* - - 1. Thus, we consider another estimate of w" based only on some Ts+1 's with a relatively large llo, V 1 In particular, for any > 0, let dg := m (o0"
That is say, for = 2, ,,...,de da. the policy Ty satisfies (ui; V* > ô and for any policy n, we have (Ud++1, VT) S 8. Then, for any policy and any unit vector & span ....., V* we have (E, S Vkō. This is because round ds + we pick an orthonormal basis pl,...: Pk-ds of span(V*), ...... VT (line in Algorithm 1) and pick Uds+1 to be the one in which there exists policy with the largest component as described in line 9. Hence, Kpj, V=Y S å for all j E [k dg]- Then, we have VT) = Σド=1 da (E) (pj, VT) S VRō by Cauchy-Schwand inequality. Let A(6) E Rdda be the sub-matrin comprised of the first dg rows of A. Then we consider an alternative estimate (6) arg min g:i0))= ||=/||2- the minimum norm solution of to
A()) e1. We upper
bound sup, | (wl)) V*) (w', | in Lemma 2 and sup, (w, V*) (018), V= in Lemma 3. Then we done with the proof of Theorem 1.
Lemma 2. If |0:: asl S ca and a; S Car all i E [d - for every 8 2 ACå Cvds eá. we have (wlo), vT) - (w', vTy S 00- C.ctd 1. 11
Vko |w''l (w'lll2), ( all x, where w' = VVi)"
Since we only remove the rows in A corresponding to u, 'ss in the subspace where no policy's 's value has large component, w and ()()) are close in terms of sup, (ūt, Vo) (ail1) v*yl-
Lemma 3. If T0; -asl S ta and S Ca for all i [d 1]. for every policy a and every
8 2 C. G. 84
we have |w V - -01)) V & O((Vk + 1)d Cae(f)), where cl
+ vkō ||''l2 is the upper bound in Lemma 2.
Note that the result in Theorem I has factor of 6 which is exponential in d. Usually, we consider
the case where 1 = (1) is small and thus ba = ((1) is small. We get rid of the exponential dependence on d by applying ((() to estimate w directly, which requires us to set the value of beforehand. The following theorem follows directly by assigning the optimal value for ò in Lemma 2.
Theorem 2. Consider the algorithm of computing À and any solution wi(6) to A(0) e1 for
5 = - and outputting the policy x 2000 arg max (ū0(0) V*). Then the policy n. _(
satisfies that v² - -(w", V st6)
Notice that the algorithm in Theorem needs to set the hyperparameter 5 beforehand while don't It have to set any hyperparameter in Theorem 1. The improper value of å could degrade the performance of the algorithm. But we can approximately estimate by binary searching 7) E [0, 1] and comparing π against the scaled version of itself (1 7) until we find an such that the user cannot distinguish between Ii and (1 m) Then we can obtain an estimate of and use the estimate to set the hyperparameter.
We remark that though we think of l small number, it is unclear whether the dependency in T'eeorems and 2 is optimal. The tight dependency on is left as an open problem. We briefly discuss potential direction improve this bound in Appendix I.
4 Learning from Weighted Trajectory Set Representation
In the last section, we represented policies using their explicit form as state-action mappings. However, such representation could be challenging for users to interpret. For example, how safe is car
7

---

described by a list of [] states and actions such as "turning left"? In this section, we design algorithms that return a more interpretable policy representation weighted trajectory set.
Recall the definition in Section 2, a weighted trajectory set is small set of trajectories from the support of the policy and corresponding weights, with the property that the expected return of the trajectories in the set (according to the weights) is exactly the value of the policy (henceforth, the exact value property). $ As these sets preserve all the information regarding the multi-objective values of policies, they can be used as policy representations in policy comparison queries of Algorithm 3 without compromising on feedback quality. Thus, using these representations obtain the same optimality guarantees regarding the returned policy in Section 3 (but would require extra computation time to calculate the sets).
There are two key observations on which the algorithms in this section are based:
(1) Each policy induces distribution over trajectories. Let 7d (r) denote the probability that trajectory 7 is sampled when selecting actions according to æ. The expected return of all trajectories under q² is identical to the value of the policy, i..., V = =E+ q" (T)) In particular, the value of a policy is a convex combination of the returns of the trajectories in its support. However, we avoid using this convex combination to represent policy since the number of trajectories in the support of a policy could be exponential in the number of states and actions.
(2) The existence of a small weighted trajectory set is implied by Carathéodory's 's theorem. Namely, since the value of a policy is in particular convex combination of the returns of the trajectories in its support, Carathéodory's 's theorem implies that there exist k + 1 trajectories in the support of the policy and weights for them such that a convex combination of their returns is the value of the policy. Such (A: + si-si set will be the output of our algorithms.
We can apply the idea behind Carathéodory's theorem proof to compress trajectories as follows. For any (k: + 2)-ize set of k-dimensional vectors {uI...., ( for any convex combination of them μ == 2 P,M4, we can always find (k + )-ssieed subset such that μ can be represented as the convex combination of the subset by solving a linear equation. Given an input of a probability distribution p over set of k-dimensional vectors, M, we pick k + 2 vectors from M, reduce at least one of them through the above procedure. We repeat this step until we are left with at most k + 1 vectors. We refer to this algorithm as C4 (Compress Convex Combination using Carathéodory's theorem). The pseudocode is described in Algorithm 4, which is deferred to Appendix J due to space limit. The construction of the algorithm implies the following lemma immediately.
Lemma 4. Given set of k-dimensional vectors M c R and a distribution p over M. C4(M.p) outputs M' C M with [M|| S k ++ 1 and distribution q E Simplex M' satisfying that Eyig [4] Eusp [p] in time O(M 1.3).
So now we know how to compress a set of trajectories to the desired size. The main challenge is how to do it efficiently (in time Opoly H |S| (A))). Namely, since the set of all trajectory returns from the support of the policy could be of size (((S)"), Instead, we will only use C4 as a subroutine when the number of trajectories is small.
" ). using
input C4 Algorithm is inefficient.
We propose two efficient approaches for finding weighted trajectory representations. Both approaches take advantage of the property that all trajectories are generated from the same policy on the same MDP. First, we start with a small set of trajectories of length of 1, expand them, compress them, and repeat until we get the set of trajectory lengths of H. The other is based on the construction of a layer graph where policy corresponds to flow in this graph and show that finding representative trajectories is equivalent to flow decomposition.
In the next subsection, we will describe the expanding and compressing approach and defer the flow decomposition based approach to Appendix due to space considerations. We remark that the flow dccomposition approach has a running time of O(H2 | + 1 S(² (see appendix for
WWithout asking for the exact value property, one could simply return a sample of Olog k/ k/())) trajectories from the policy and uniform weights. With high probability, the expected return of every objective is e'afar from its expected value. The problem that this set does not necessarily capture rare events. For example, if the probability of a crash for any car is between (c')* and (c')², depending on the policy, users that only care about safety (i.e., no crashes) are unlikely to observe any "unsafe" trajectories at all, in which case we would miss valuable feedback.
8

---

details), which underperforms the expanding and compressing approach (see Theorem 3) whenever |S) + [S| w(*+ + xJS).. For presentation purposes, the following, we only consider the deterministic policies. Our techniques can be easily extended to random policies.'
Expanding and Compressing Approach.
The basic idea to find k + 1 trajectories length to represent V first and then increase the length of the trajectories without increasing the number of trajectories. For policy オ, let VT h)
(=0 R(S,, (S.)) be the value of æ with initial state So and time horizon h. Since we study the representation for fixed policy и in this section, we slightly abuse the notation and represent trajectory by 7" (8, 01......... 8H)- We denote the state of trajectory T at time & as of = st. For trajectory prefix T = (s, 81......... 8h.) of i with initial state s and I subsequent states, the return of 7 is ((()) R(s, (s)) Σx=1,
Es,=s
Ee=
t=1 R(st, (st)). Let J() be the expected return of trajectories (of length H) with the prefix being T, i.e.
1-1
J(7) :- = 2 (1 h).
For any E S, let a denote the trajectory of appending s to r. We can solve (* h) for all s E S, E [H] by dynamic programming in time OkH [ Specifically, according to definition, have V (s, R(s, a (s)) and
(T h
VT
R(s, Σ P() s'ES
Thus, we can represent V by
V" =R(30, (so)) + >
- Psss P (s0)))
SES
SES
By applying C4, we can find a set of representative trajectories of length 1, F() C {((0 s)(s E S}.
with |F(]| < ls + and weights 3(1) E Simplex (())
such that
Σ (T) FEFG
(5)
Supposing that we are given a set of trajectories F()) length with weights 3(0) such that V EEerro (T), we can first increase the length of trajectories by through Eq (4) and obtain a subset of (7 o 8/7 E F(0), E S). in which the trajectories are of length t - 1. Specifically, we have
V"
(6)
TEP())
Then we would like to compress the above convex combination through C4 as we want to keep track of at most h + trajectories of length + due to the computing time. More formally, let JPc
{J(T o 8)]7 7 E p((), E S} be the set of expected returns and PFte,300 E Simplex p(t) with ppo (T o s) = ((t) (T) (ss)) be the weights appearing in Eq (6). Here Pru gte defines distribution over J pto) with the probability of drawing J(T o being p (T) Then can apply C4 over (Prt,,Prte Prtc, (.ss))s))) and compress the representative trajectories (7 s/T E P()), 8 S). We start with trajectories of length and repeat the process of expanding and compressing until we get trajectories of length H. The details are described Algorithm 2.
"In Section 3, we consider special type random policy that mixed strategy a deterministic policy (the output from an algorithm that solves for the optimal policy for an MDP with scalar reward) with the "do nothing" policy. For this specific random policy, we can find weighted trajectory representations for both policies and then apply Algorithm 4 to compress the representation.

---

Algorithm 2 Expanding and compressing trajectories
I: compute (s h) for all 8, h [M] by dynamic programming according to Eq (4)
2: p(o) {())) and (so) =1
do 4: JFC t {J(T ( F(t) E 8} and po o.s) 3thh (T) (T$])) ( for
3: fort= =0, =......
// expanding step 5: (J(+)), g(t+l)) t CA(J and F(++)) + [T] E J(+1) compressing
TE p ,088 ES
step
6: end for
7: output F(H)
and ((H)
Theorem 3. Algorithm 2 outputs F(H) and g(H) satisfying that |F()|
+
and
Ererun (3H (T) V* in time O(K H 8 kH (
The proof of Theorem 3 follows immediately from the construction of the algorithm. According to Eq (5), we have V = -Errro E(a) (T) Then can show that the output of Algorithm 2 is valid weighted trajectory set by induction on the length of representative trajectories. C4 guarantees that F(0| I k + for all -....., H. and thus, we only keep track of most k trajectories at each step and achieve the computation guarantee in the theorem. Combined with Theorem 1, we derive the following Corollary.
Corollary 1. Running the algorithm in Theorem with weighted trajectory set representation returned by Algorithm 2 gives us the same guarantee that of Theorem I in time (1 (ke H [S] + H |S|3) log( (
5 Discussion
In this paper, we designed efficient algorithms for learning users' preferences over multiple objectives from comparative feedback. The efficiency is expressed in both the running time and number of queries (both polynomial in H, [S], [A|, and logarithmic in 1/c). The learned preferences of a user can then be used to reduce the problem of finding personalized optimal policy for this user to (finite horizon) single scalar reward MDP, a problem with a known efficient solution. As we have focused minimizing the policy comparison queries, our algorithms based on polynomial time pre-pree pre-processing calculations that save valuable comparison time for users.
The results in Section 3 are of independent interest and can be applied to a more general learning setting, where for some unknown linear parameter w", given a set of points and access to comparison queries of any two points, the goal is to learn arg max (w", E.g., in personalized recommendations for coffee beans in terms of the coffee profile described by the coffee suppliers (body, aroma, crema, roast level....,, while users could fail to describe their optimal coffee beans profile, adopting the methodology in Section 3 can retrieve the ideal coffee beans for a user using comparisons (where the mixing with "do nothing" is done by diluting the coffee with water and the optimal coffee for a given profile is the one closest to it).
When moving from the explicit representation of policies as mappings from states to actions to more natural policy representation as a weighted trajectory set, we then obtained the same optimality guar- antees in terms of the number of queries. While there could be other forms of policy representations (e.g., a small subset common states), one advantage of our weighted trajectory set representation that it captures the essence of the policy multi-objective value in clear manner via ((k) trajectories and weights. The algorithms provided in Scction 4 are standalone and could also be independent interest for explainable RL (Alharin et al., 2020). For example, to exemplify the multi-objective performance of generic robotic vacuum cleaners (this is beneficial we only have e.g., 3 of them we can apply the algorithms in Section 4 to generate weighted trajectory set representations and compare them directly without going through the algorithm in Section 3.).
An interesting direction for future work is to relax the assumption that the MDP is known in advance. One direct way is to first learn the model (in model-based RL). then apply our algorithms in the learned MDP. The sub-optimality of the returned policy will then depend on both the estimation error of the model and the error introduced by our algorithms (which depends on the parameters in the leamned model).
10

---

Acknowledgements
This work was supported in part by the National Science Foundation under grants CCF-2212968 and ECCS-22 16899 and by the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003. The views expressed this work do not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred. Approved for public release; distribution is unlimited.
This project was supported in part by funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement number 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for Al and Data Science (TAD), the Eric and Wendy Schmidt Fund, and the Yandex Initiative for Machine Learning at Tel Aviv University.
We would like thank all anonymous reviewers, especially Reviewer Gnoo, for their constructive comments,
References
Ailon, N. (2012). An active learning algorithm for ranking from pairwise preferences with almost optimal query complexity. Journal of Machine Learning Research, 13(1):137-164
Ailon, N., Karnin, Z. S., and Joachims, T. (2014). Reducing dueling bandits to cardinal bandits. In ICML, volume 32, pages 856-864.
Akrour, R., Schoenauer, M., and Sebag, M. (2012). APRIL: Active preference learning- -baed reinforcement learning. Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 116-131.
Alharin, A., Doan, T.-N., and Sartipi, M. (2020). Reinforcement learning interpretation methods: survey, IEEE Access, 8:171058-171077.
Balcan, M., Blum, A., and Vempala, S. (2015). Efficient representations for lifelong learning and autoencoding. In Proceedingy of the Annual Conference on Learning Theory (COLT), pages 191-210.
Balcan, M.-F., Vitercik, E., and White, C. (2016). Learning combinatorial functions from pairwise comparisons. In Proceedings of the Annual Conference on Learning Theory (COLT).
Barrett, L. and Narayanan, S. (2008). Learning all optimal policies with multiple criteria. In Proceedings of the International Conference on Machine Learning (ICML), pages 41-47.
Bengs, V., Busa-Fekete, R., El Mesaoudi-Pant Paul, A., and Hüllermeier, E. (2021). Preference-based online learning with dueling bandits: A survey. Mach. Learn. Res.
Bhatia, K., Pananjady, A., Bartlett P., Dragan, A., and Wainwright, M. J. (2020). Preference learning along multiple criteria: A game-theoretic perspective. In Advances Neural Information Processing Systems (NeurIPS), pages 7413-7424.
Biyik, E. and Sadigh, D. (2018). Batch active preference-based learning of reward functions. In Proceedings of the Conference Robot Learning (CoRI.), pages 519-528.
Blum, A. and Shao, H. (2020), Online learning with primary and secondary losses. Advances in Neural Information Processing Systems, 33:20427-20436.
Chatterjee, K. (2007). Markov decision processes with multiple long-run average objectives. In Pro- ceedings of the International Conference Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 473-484,
Chatterjee, K., Majumdar, R., and Henzinger, T. A. (2006). Markov decision processes with multiple objectives. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 325-336.

---

Chen, X., Ghadirzadeh, A., Björkman. M., and Jensfelt, P. (2019). Meta-learning for multi- multi-objective reinforcement learning. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 977-983.
Cheng, W., Fürnkranz, J., Hüllermeier, E.,, and Park, S.-H. (2011). Preference-basee policy iteration: Leveraging preference learning for reinforcement learning. In Proceedings of the Joint European Conference Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 312-327.
Cheung. W. C. (2019). Regret minimization for reinforcement learning with vectorial feedback and complex objectives. In Advances in Neural Information Processing Systems (NeurIPS).
Christiano, F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. (2017). Deep reinforce- ment learning from human preferences. In Advances in Neural Information Processing Systems (NeurIPS).
Doumpos, M. and Zopounidis, C. (2007). Regularized estimation for preference disaggregation in multiple criteria decision making. Computational Optimization and Applications, 38(1):61-80.
Fürnkranz, J., Hüllermeier, E., Cheng, W., and Park, S.-H. (2012). Preference-based reinforcement learning: A formal framework and policy iteration algorithm. Machine Learning, 1931):123-156.
Hayes, C. F., Radulescu, R., Bargiacchi, E., Källström, J.. Macfarlane, M., Reymond, M., Verstracten, T., Zintgraf, I.. 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. (2022). A practical guide to multi-objective reinforcement learning and planning. Autonomous Agents and Multi-Agens Systems.
Ibarz, B., Leike, J., Pohlen, T., Irving, G., Legg, S., and Amodei, D. (2018). Reward learning from human preferences and demonstrations in Atari. In Advances in Neural Information Processing Systems (NeurIPS).
Jain, A., Sharma, S., Joachims, T., and Saxena, A. (2015). Learning preferences for manipulation tasks from online coactive feedback. International Journal of Robotics Research, 34(10):1296 17199-111....
Jamieson, K. G. and Nowak, R. (2011). Active ranking using pairwise comparisons. Advances in neural information processing systems, 24.
Kane, D. M., Lovett, S., Moran, S., and Zhang, J. (2017). Active classification with comparison queries. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 355-366. IEEE.
Knox, W. B., TlaggisKKsssele S., Booth, S., Niekum, S., Stone, P., and Allievi, A. (2022). Models of human preference for learning reward functions. arXiv preprint vrXiv:2206.0223)
Lee, K., Smith, L., and Abbeel, P. (2021). PEBBLE: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training. arXiv preprint arXiv:2106.0509)
Mannor, S., Perchet, V., and Stoltz, G. (2014), Approachability unknown games: Online learning
meets multi-objective optimization. In Conference on Learning Theory, pages 339-355. PMLR.
Mannor, S. and Shimkin, N. (2001). The steering approach for multi-criteria reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS).
Mannor, S. and Shimkin, N. (2004). A geometric approach to multi-criterion reinforcement learning. Journal of Machine Learning Research, 5:325-360.
Marinescu, R., Razak, A., and Wilson, N. (2017). Multi-objective influence diagrams with possibly optimal policies. Proceedings of the AAAI Conference on Artificial Intelligence.
McAuley, J. (2022). Personalized Machine Learning. Cambridge University Press. in press.
Pacchiano, A., Saha, A., and Lee, J. (2022). Dueling RL: reinforcement learning with trajectory preferences.
12

---

Ren, W., Liu, J., and Shroff, N. B. (2018). PAC ranking from pairwise and listwise queries: Lower bounds and upper bounds. arXiv preprint arXiv:1806.0297)
Roijers, D. M., Vamplew, P., Whiteson, S., and Dazeley, R. (2013). A survey of multi-objective sequential decision-making. Journal of Artificial Intelligence Research, 48:67-113.
Rothkopf, C. A. and Dimitrakakis, C. (2011). Preference elicitation and inverse reinforcement learning. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 34 48.
Sadigh, D., Dragan, A. D., Sastry, S., and Seshia, A. (2017). Active preference-basee learning of reward functions. In Proceedings of Robotics: Science and Systems (RSS).
Saha, A. and Gopalan, A. (2018). Battle of bandits. In Uncertainty in Artificial Intelligence.
Saha, A. and Gopalan, A. (2019). PAC Battling Bandits in the Plackett-Luce Model. In Algorithmic Learning Theory, pages 700-737.
Saha, A., Koren, T., and Mansour, Y. (2021). Dueling convex optimization. International Conference Machine Learning, pages 9245-9252 PMLR.
Sui, Y., Zhuang, V., Burdick, J., and Yue, Y. (2017). Multi-dueling bandits with dependent arms, In Conference on Uncertainty in Artificial Intelligence, 1AI'17.
Sui, Y., Zoghi, M., Hofmann, K., and Yue, Y. (2018). Advancements in dueling bandits. In IJCAI, pages 5502-5510.
Wang, N., Wang, H., Karimzadehgan, M., Kveton, B., and Boutilier, C. (2022). Imo" Interactive multi-objective off-polic, optimization. In Proceedings of the Thirty-Firsl International Joint Conference on Artificial intelligence, IJCAI-22.
Wilson, A., Fern, A., and Tadepalli, P. (2012). A Bayesian approach for policy learning from trajectory preference queries. In Advances in Neural Information Processing Systems (NeurIPS).
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, (2017a). A survey of preference-based reinforcement learning methods. J. Mach. Learn. Res.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. (2017b). A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136):
Wirth, C., Fürnkranz, J., and Neumann, G. (2016). Model-free preference-based reinforcement learning. In Pruceedings of the National Conference on Artificial Intelligence (AAAI).
Yona, G., Moran, S., Elidan, G., and Globerson, A. (2022). Active learning with label comparisons. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI).
Zoghi, M., Whiteson, S., Munos, R., Rijke, M. d., et al. (2014). Relative upper confidence bound for the k-armed dueling bandit problem. JMLR Workshop and Conference Proceedings, number 32, pages 10-18. JMLR.
13

---

A Related Work
Multi-objective sequential decision making There is a long history of work on multi-objective sequential decision making (Roijers et al., 2013), with one key focus being the realization of efficient algorithms for approximating the Pareto front (Chatteerjee et al., 2006; Chatterjee, 2007; Marinescu et al., 2017). Instead of finding a possibly optimal policy, we concentrate on specific user preferences and find a policy that is optimal for that specific user. Just like the ideal car for one person could be a Chevrolet Spark (small) and for another, it is Ford Ranger (a truck).
In the context of multi-objective RL (Hayes et al., 2022), the goal can be formulated as one of learning policy for which the average return vector belongs to target set (hence the term "multi-criteria" RL), which existing work has treated as a stochastic game (Mannor and Shimkin, 2001, 2004). Other works seek to maximize (in expectation) a scalar version of the reward that may correspond to weighted sum of the multiple objectives (Barrett and Narayanan, 2008; Chen et al., 2019) as we consider here, a nonlinear function of the objectives (Cheung, 2019). Multi-objective online learning has also been studied, see (Mannor et al., 2014; Blum and Shao, 2020) for example.
The parameters that define this scalarization function (e.g., the relative objective weights) are often unknown and vary with the task setting or user. In this case, preference learning (Wirth et al., 2017a) is commonly used to elicit the value of these parameters. Doumpos and Zopounidis (2007) describe an approach to eliciting a user's relative weighting in the context of multi-objective decision- -aaiing... Bhatia et al. (2020) learn preferences over multiple objectives from pairwise queries using game- theoretic approach to identify optimal randomized policies. In the context of RL. involving both scalar and vector-valued objectives, user preference queries provide demonstrations, which may be difficult for people to provide (e.g.. in the case of robots with high ofgrees-offfreedom) or explicit reward specifications (Cheng al., 2011; Rothkopf and Dimitrakakis, 2011: Akrour et al., 2012; Wilson et al., 2012; Fürnkranz et al., 2012: Jain et al., 2015; Wirth et al., 2016; Christiano et al., 2017: Wirth al., 2017b; Ibarz et al., 2018; Lee et al., 2021). These works typically assume that noisy human preferences over a pair of trajectories are correlated with the difference in their utilities (i.e.. the reward acts as a latent term predictive of preference). Many contemporary methods estimate the latent reward by minimizing the cross-entropy loss between the reward-based predictions and the human-proon human-provided provided preferences (i.e., finding the reward that maximizes the likelihood of the observed preferences) (Christiano et al., 2017: Ibarz et al., 2018; Lee et al., 2021; Knox et al., 2022; Pacchiano et al., 2022).
alternative learning from
Wilson et al. (2012) describe a Bayesian approach to policy learning whereby they query a user for their preference between a pair of trajectories and use these preferences maintain posterior distribution over the latent policy parameters. The task of choosing the most informative queries challenging due the continuous space of trajectories, and is generally NP-hard (Ailon, 2012). Instead, they assume access to distribution over trajectories that accounts for their fcasibility and relevance to the target policy, and they describe two heuristic approaches to selecting trajectory queries based on this distribution. Finally, Sadigh et al. (2017) describe an approach to active preference- based learning in continuous state and action spaces. Integral to their work is the ability to synthesize dynamically feasible trajectory queries. Biyik and Sadigh (2018) extend this approach to the batch query setting.
Comparative feedback in other problems Comparative feedback has been studied in other problems in learning theory, e.g., combinatorial functions (Balcan al., 2016). One closely related problem is active ranking/learning using pairwise comparisons (Jamieson and Nowak, 2011; Kane et al., 2017; Saha et al., 2021; Yona et al., 2022). These works usually consider given finite sample of points. Kane et al. (2017) implies a lower bound of the number of comparisons is linear in the cardinality of the set even if the points satisfy the linear structural constraint as we assume in this work. In our work, the points are value vectors generated by running different policies under the same MDP and thus have a specific structure. Besides, we allow comparison of policies not in the policy set. Thus, we are able to obtain the query complexity sublinear in the number of policies. Another related problem using comparative/preference feedback is dueling bandits that aim to learn through pairwise feedback (Ailon et al., 2014; Zoghi et al., 2014) (see also Bengs et al. (2021); Sui et al. (2018) for surveys), or more generally any subsetwise feedback (Sui et al., 2017: Saha and Gopalan, 2018 2019; Ren et al., 2018). However, unlike ducling bandits, we consider noiseless comparative feedback.
14

---

B Proof of Lemmal
Lemma 1. When S o² 26
we have 1''
(w' S 2k, and - asl 4k for every E [d].
Proof. We first show that, according to our algorithm (lines 1-6 of Algorithm 1), the returned T satisfies that
(w", V
max ve [A]
w", V
This can be proved by induction over k. the base case of k = 2, it's easy to see that the returned Ti satisfies the above inequality. Suppose the above inequality holds for any k S n 1 and prove that it will also hold for k = n. After running the algorithm over j = ......k 1 (line 2), the returned policy we- satisfies that
(w",, va
)
( (w*, pari) -E.
max vE[k-1]
Then there are two cases,
If wn', Vo (w", V4rk 6, will return mi n and also, (w", Vacky (wr, pani) - for all E [k.].
If (w",, Vare) (we vark c, then will return xx and it satisfies (w", va maxiel (w", pasi -e.
As T is the optimal personalized policy when the user's preference vector is e,, we have that
k
o² = (w=, V"
w. V"
e S w ( (v*
pr
S w
where the last inequality holds because the entries of V exists i [k] such that (w", V V= (w", V fu².
and wt are non-negative. Therefore, there
Then we have
(w", V=l)= > max (w", ya 2 -
2h: 1²
iE(k]
when n" 25 By rearranging terms, we have
5- [== < 2k.
By setting C. = 2k, we have [ā, agl (w", V < Cae 2ke and thus, 10,
asl 5 4k3c
C Pseudo Code of Computation of the Basis Ratios
The pscudo code of searching a, 's is described in Algorithm 3.
15

---

Algorithm 3 Computation of Basis Ratios
input: (VT, V*2) and Co
2: for = 1,... 1.....d-- do
3: let 0, h 2C, and ã₁ Ca
4: while True do
5:
if a. then
6:
compare and Ti+1 + (1 To: if 1 Ti+1 + (1 a.
nm then h <- ōs.
a.
if Lf 0; - Lt. 2
Rit1 + (1 a. no then Ci āi x
1uh
2
7: else
8:
compare T++1 and ā (1 ā mo if ā; + (1 ā.
no >
ai+ then h + ā.
ã; - 4th if ā. (1 ā=)=o x क11 then < 0ü 0g 2
L+h
9: end if
10: if "indistinguishable"" is returned then
11: break
12: end if
13: end while
14:
end for
15:
output: (G....,ūdd-1
D Proof of Theorem
Theorem 1. Consider the algorithm of computing À and any solution w to Au = e1 and oulpuiling
the policy nhh arg max (w, V*), which is the optimal personalized policy for preference vector
w. Then the output policy x" satisfying that o- - -ww,, "u*,V==) S O ((V++1)
d+ cb using
(kloog(k log(k/()) comparison queries.
Proof. Theorem I follows by setting ca = 1k2g and Ca = 2k as shown in Lemma I and combining y the results of Lemma 2 and 3 with the triangle inequality.
Specifically, for any policy n, we have
(w, VT) (w', VL) < (0, VT) - (000), vT) + (0000) vm) (w', VTy
Co Co
11 11:ca vko (1ww(l2))
<o((vk+ + 1)o-di Ca,
(7)
82
11w'112
||
so((Vk + do |
+ +8))
0²6²
Since ||w0|| = (w= v and (w= V=l 2 ns 26
from Lemma 1, we derive
v¹ (w", v==)) =w",, v (( w'' - vT())T))
Gi.k' lw''l2e
x (w., |in) (00, (0/) - @,, v= + O((Vk 1)d- 1/
0=0² + 8))
(w', / (vT + 1)d- || 12 G+ |1''l22 Gtualluelle
8)
v=82
C# ||0 |10 11
(Vh + 1ed- ||00||
+ 5) 2x282
-o ||w 1|2 ( 1) et
The first inequality follows from
(w, v=*) - (w', 5* (w', v=+)
(w'', Vxs
16

---

+ va vor)) ( ) )
and applying (7) twice- once for I and once for π" The last inquality follows by setting d Ci le pa2
E Proof of Lemma 2
Lemma 2. If [ā; asl ca and a; for all [d 11. every 8 Jvac we have
(wolo, v²) - (w', VTl S O C. d w I V 11'll2)) for all n, where w'
10
[wo (a1)"
To prove Lemma 2, we will first define a matrix, A (
Given the output (VTi,, V=a) of Algorithm 1, we have rank rank(span((VT)) ....., VTds })) ds.
Let bi..... bd-ds be set of orthonormal vectors that are orthogonal to span (ea,, ,..., V and together with V*,,. ..... V*d form basis for span( ( ((V*) | E II)).
We define ((flll) E Rddk as the matrix of replacing the last d dg rows of with ....... ba-do iee.
V (a,V=L - V=2)
(full)
(ads Vii V
bT
b
T
Observation
We have that span(A((ull) = span( (V E lI}} and rank(A =
Lemma S. For all w E R& satisfying Alfull) = =n, we have ww V w' V* S vio |w''l for all ı.
We then show that there exists w I&* satisfying Allll) e, such that (6)) V V is small for all π E II.
Lemma 6. If lā, - asl S Ea and a; S Co all E [d - 1}, for every 2 40 Cyd eà there
exists w E & satisfying Atill) e1 (7) v V S 00 C. w for all
We now derive Lemma 2 using the above two lemmas.
Proof of Lemma 2. Let be defined in Lemma Then for any policy æ. we have
()))) V - w'. V" < (1()) V
w V + ww V - w/ V
C. Ct | 1 + Vkō (
<o(
82
by applying Lemma 5 and 6.
Proofs of Lemma 5 and Lemma
Lemma 5. For all w E & satisfying Allill = es, we have ww Va -a- w. .V S Vi8 1
all n.
17

---

Proof of Lemma 5. Since (pan(A("l)) Span E IT),, for every policy x, the value vector can be represented a linear combination of row vectors of A(ful), ie., there exists (a1,...,aa) Ga) E Rd s.t.
V
a A
A a.
(8)
i=1
Now, for any unit vector E span(b)...... bd-d,). we have (V*, ,) vk6.
The reason is that at each round dg + 1, we pick an orthonormal basis fl,..., Pk-da of span(V*) ,..., (=ea)) ) (line 8 in Algorithm 1) and pick uds+I to be one which there ex- ists policy with the largest component described in line 9. Hence, Kpj, V*) 8 for all j E [k da).
follows from Cauchy-Schwarz inequality that (E, V*) ΣE (5,ps) (pj, V*) S vko.
Combining with the observation that by....: ba-ds are pairwise orthogonal and that each of them is orthogonal to span( V* V ) we have
V
asbi-ds
S
of Vio
1=d++1
i=d++1
i=ds+1
which implies that
Σ s Vko. i=ds+1
(9)
Since w' satisfies Aw' C1, we have
A w' (1, 0,, .., 0, (b1, w')..... ..... (ba- do w'))-
For any w E & satisfying u = es consider ã = w + S (bi, w²) bi. Then we have
A ã w'
Thus, applying (8) twice, we get
w v TT A ( a = nT A = w' V=.
Hence,
ww V w/ V = =|w- V - T Va
(a)
a w)
A
(full)
(0)
Σ a; (bi-da; w²)
1 Σ af
v
1d
||
imds+1
i=d++1
where Eq (a) follows from (8), inequality (b) from Cauchy-Schward and inequality (c) from applying (9).
Lemma 6. If - aul & Ea and a; S Ca for all E [d - for every 82 4C² Cydded there
exists w E & satisfying Alill) e (7) v* V 0 Ca | for all
Before proving Lemma 6, we introduce some notations and claim.
For any x, R let ((z, v) denotes the angle between and y.
For any subspace U c R* let 0xx U) = minyeu ((r y)-
For any two subspaces U c TR we define O(U,U') as 0(U,0")
maxxeu minyeur ((z, v).
18

---

For any matrix M, let M; denote the i-th row vector of M, Mej denote the submatrix of M composed of rows i, I.... J. and M, denote the submatrix composed all rows j 2 i.
Let span(M) denote the span of the rows of M.
Recall that E Rddx is defined as
VaiT (ōi V V=aaT
(ād-1V= - -V
which is the approximation of matrix A Rd defined by true values of a; i..,
V
(01V=1-V') - V=a)T
A
(aa- VTa)T
We denote by A = Ar.da A() A1.ds E BRdas the sub-matrices comprised of the first dž rows of Á and A respectively.
Claim 1. fā ail S en and as S C. for all i [d - for every 8 4C Cydsee ed. we have
(A. span A(. S Kead
(10)
and
A(span ( span(A (A S ne
(11)
4C.C3 Cassa 6
where
Me...
To prove the above claim,
the following lemma by Balcan al. (2015).
Lemma 7 (Lemma 3 of Balcan et al. (2015)). Let Uj = spaanE and Ūú = span({i: E.)
Let Cocey Tnew 2 0 and Cace S now (101), and assume that (E,, Ú,.1) 2 Tnew for i = ......... and that (E,, S Euce for I....,L. 0(U,, Ū1) < 21 Cace
Then,
Inew
Proof of Claim 1. For all 2 < < ds, we have that
0( ((7 Sppan (6) 12)-1)) 20 (A (8)
span (1))
1(o 2 sin(0(A(
spann( ((12-1))
7100 (b)
(a)
8
8
(
((8))
a.
V VTl (C, + 1)Cy
where Ineq (a) holds is orthogonal to span A 1 according to line 8 of Algorithm
and Ineq (b) holds due to A u: -IV= Uzl > 8. The last inequality holds due to
V ~, | + Villl < (C., + 1)Cv.
Similarly, also have
((4
(8)
span ( 2 (Ca 1)CV
We continue by decomposing V the direction of y and the direction perpendicular to V For convince, we denote e == V
v!!l = 2 |.
y
Vi+ == V - v!! and 1e' = | 11
19

---

Then we have
8(4 1(01 = - 0
- V V - = = v -V,+ 2 V V -V:)).
,
If (a;-1 V - V (03-1V=1- V 2 ie., / V v and a;- Vil are in the same direction, then
/i-1V V V.
Oi- V
Vi
arctan
arctan
1/3
a V V
a4 v V
2
(12)
27
1
2
27
Ea Cv
(13)
8
where Ineq (12) follows from the fact that the derivative of arctan is at most 1, i.e. lima-+x aretan a e-arttan a-
2 arrctan
Ox
1+22 I 1.
Inequality (13) holds since ws 2 (V* uz) 2 6.
If directions, then we have - Voa vi!l + 0 V/ v.ll1, = 11 0 V
V 1onn-vll1 v!!l < 0, i.c. â, V v and a4-1V/= -v! are in the opposite
112 z
<a ||V* ll2- Similarly, we have
ai- V v
ai V V!
(())
arctan
2
+ arctan
of
0,
2
V=
Vi
a V V.!
2
2
11
Ca Cv
By applying Lemma 7 with Cece Cv Nne (Cu-1jov (G),E) (A141, (and (E:. E.)
(A411,A44)) we have that when 8 10t +1)+Crd ca.
2ds + 1)C = 1e..6
((span(A))) spann (A{) <
82
and
0 (span ( (L()) span This completes the proof of Claim 1 since C. 1.
(pssn(AA (1o1 < Me..5
U
Proof of Lemma 6. Recall that ( arg min A00 |0||| is the minimum norm solution to (()) x ej.
Thus, (7) bi) for all i [d dz).
Let A Ads-1 be any orthonormal basis of span (A)
20

---

We construct vector satisfying u e1 by removing @(6)'s component in span(A2. (A2.) and rescaling.
Formally.
(1)(0) X1) Xj 1 V*1 ( i=1 (T)l), Xi) Xx)
w(6) d -1 -i=1
w =
(14)
direct to verify that A w = V w = 1 and A, w = for 2,...,ds. dg. As a result, A (6) ej.
Combining with the fact that ( has zero component in b, for E [d-da], we have A = e1
According to Claim 1, we have
((span(A (A span(A2 )) S 7e..5-
Thus, there exist unit vectors N A..... A 1 E Espan (Ag.)) such that 0(),, Ad) S Tea.s Since A (()) = c1, we have (0) X; = 0 for all = ,,....dd - 1, and therefore,
(6) X = (6)) (A, x.) 1 (0))) || Ne..ō
This implies that for any policy x.
ds
V
(x(6))
<|VV* l2 dds ((())
ne.,ó S Cv Ov /ds [((6] ne..
Denote by 7
V
-i=1
d (wl() A.) Ac), which is greater than Cy
[ ||2 n..8.
We have that
1 (8)
V
w V
I 111) v"
(6))
V
+
1
w())
V w V
1-
1-9
> 21 112
Cv
+
1
ds-1
Σ (w(6)
Ai)d. V
?
1 1-7
? ||100000
112
Cv
+ Cvvdss ||00000011 Te..8
1-7
1 1-y
= 2(CV ||000/|
+ +1)0v / vdo | Nea.5
(15)
where the last equality holds when Cv Cvd ( ||2 nc,. S 1 2'
Now we show that || [
|| I C¹ [|'ll, for some constant C².
Since (6) is the minimum norm solution to 1 e₁, we will construct another solution to A e₁ denoted by wp in simillar manner to the construction in Eq (14), and show that [|@oll2 < C ||w||||
Let E....., ......,,d---1 be any orthonormal basis of span( A
We construct a wo s.t. A = ei by removing the component of w/ in span (A()) and rescaling. Specifically, let
w w/ ΣiET
das (w' (.) &
(16)
1 (V=I, (E do (w', Ex) Ex)
Since ((0) = ei, it directly follows that (Ai, 000 = (V=1, (o) = and that (A., wo = 0 for i .,............................ ds. i.c., A(d) 2o e1-
21

---

Since Claim implies that O(span(A) (A2.) spanspann. (A (appp(2))))
S Ne there exist unit vectors
E..... Eds- E span(A (A such that ((E;, 51) S 6-
As w' has zero component in span(A2. w/ should have a small component in span( (pan)AA)))) ) In partieular,
(w/, = ( 10', |. E.) s || 7ka.8
which implies that
dg 1
(w' ,Ei) E1
S do 11l Te..
2
Hence
ds
(w' E.) Ei)
s sCv Iw'll2 Te..5 Te..5.
As result, |10ll22 S 2/2 ||w'll2 when Cv
|| Deard S j. which is true when ea is small
enough.
According to Lemma 1, Ea < 1h Eo + 0 as - O.
Thus, we have | 112 < || Wollz S || 1l2 and ds [ 112 Ne.. S 1/2
Combined with Eq (15), get
(11) v - w V o ((Cv ||''l1 1)Cv ds ||l Mca.s)
40, I..CRrdee into the above equation, we have
Since Cy ||20|2 2 ((VL,, w'Yl 1, by taking Ten.5
3 Ca Ca di I 12
()6) V w V =0
82
which completes the proof.
G Proof of Lemma 3
Lemma 3. If la: asl s ca and a S Ca for all i [d 1), for every policy a and every
8 2 Cv we have |w V - ( V I O((Vk + doCalf)) where c(
cacta2llu 8 II + Vho ||''ll is the upper bound in Lemma 2.
Proof. Given the output (V=1,, ..... V= of Algorithm 1, we have rank(span((V*; ...., Vilag })) dg.
For i do + I,...,d. d. let vi be the normalized vector of V=='s projection into span(V=i... ...., v with || 1.
Then we have that sVan ,..., va, 1, 1/) = span(V" V=L and that {dyli = ds 1...., d) are orthonormal.
For every policy v, the value vector can be represented as a linear combination of Â Ads i.., tha ie., there exists unique a (a1..... aa) E Rd s.t. V Ede a, + Ei a.h.
Since th orthogonal to w for j o and 1/s are orthogonal to span Ai...., Adg). ) we have a, (V", v1) for i 2 ds + 1.
22

---

This implies that
ds
d
(wi, VX) - -66010)
Σ
ai
((
@
A.)
- -(ult A4i)
+
Σ
a (w, vi)
==1
i=d++1
(0)
+
Σ
20(0) 2//s)
i=d++1
(c)
Since A = A(0) = el, we have term (a) = 0.
We move on to bound term (c).
Note that the vectors { da d ........ d) are orthogonal span ( ..... v and that together with y* ,..,, 4dd they form a basis for span( ( ([V E 11}).
Thus, we can let 0ū in the proof of Lemma 2 be vitdd.
In addition, all the properties of {bylé E [d d&]} also apply to (v/li do + 1, ...... d} well.
Hence, similarly to Eq (9),
Σ at S vko.
i=ds+1
Consequentially, we can bound term (c) is by
3 Voo ||0'l2
(c) s Vo (5)
2
since | 1| - 3 |/oe|, when Cr / ds ||l 112 Ten.55 I 1
3 as discussed in the proof of Lemma 6.
2
Now all is left is to bound term (b).
We cannot bound term (b) in the same way as that of term (c) because ||00| is guaranteed to be bounded by ||w' ||wll22-
For = ds + L,..., d, we define
= ( Wi A:)l
For any i,j = ds + 1,....d d the is perpendicular to V thus (M%.Ab)) 1( Qy-1 - v= = 1(ti, ). Especially, we have
4 4= < A, = K V=l)
Let A! = A. Ej=dst +1 (Ar. v3) U denote A,'s projection into span(A, Ai..., Ads).
Since A; has zero component in direction v for j i, we have A! = A:- - Ej +1 ( (Ar 1s W3.
Then, have
0 = 0. A, =
1o A! + t. Σ
(Ar, 1o ソ/
の A!
(V (5)
j=d++1
j=
where the first equation holds due to Aσ = ej.
By rearranging terms, have
(V (1) (6, (.) = w. A!
Σ (VTT,
(17)
j=d++1
23

---

Recall that at iteration j of Algorithm 1, in line 8 we pick an orthonormal basis Pl..... Pk+1-s of span( V ..... / )) Since u is in span(V*1, ..... ) according to the definition of Vi ((V", ا5yا is no greater then the norm of V*''s projection into span(V*; ..... ,..,,,,,,......................, V=
Therefore, have
(d) pi31 S Vb max max
( (v .ii) ( ( pi)
IVV 45y1 S Vi max lelk+1-jl
((V,,
le(k+1-j
Vk: (V 1 VV
Vkej.
(18)
where inequality (d) holds because π is the optimal personalized policy with respect to the preference
vector pt, and Equation (e) holds due to the definition of uj (line 9 of Algorithm 1). Inequality (I)
holds since (V*), 15y) is the norm of 'ra's projection in span ..... -- and uy belongs to )
span(V** (
By taking absolute value on both sides of Eq (17), we have
4 (ū,
1 x!
wby) (ū, 1y)
1 2!
Vi f=d++1
Σ
s (( (19)
j=d++1
We now bound
@ A
follows.
w A.
( A!
(20)
1 (A,
Σ
(Ai 13) v55)
(0( A
(21)
j=d++1
()) A + (6) (A;
-A:: - Ai) -Ai)
lw' A, + (m) w') A
(1( (A; A.) (x)
S 0 + (C. + 1) sup (T)(0) w²) 4 + Cv
60
2
I ())
for constant C' > 0.
Eq (20) holds because A A ()) e, and A! belongs to (A()) Eq (21) holds
because (6) is the minimum norm solution to A x = e1, which implies that ((6) 2b = 0. The last inequality follows by applying Lemma 2.
We will bound 6 (w,, whail by induction on i = ds + 1,...,d. d.
In the base case of i = ds + 1,
cds+1 1 (10, w'det2)l S @ - S c))
Then, by induction through Eq (19), we have for i = ds + 2.... d
(ū,, vi)l S (VT 1-- CC.
Similar to the deviation of Eq (18), we pick an orthonormal basis Pl.... PK+1-i of Vpan(V*i xi - line 8 of Algorithm 1, then have that, for any policy n
KV= v.)l < Vk max (V=, e S VKRV ui)l S V ((V=, ,bxi) = Vke. 1E|+1-1
Then have that term (b) is bounded by
(b)
Σ
(V",
1/i (00, vhi)
< Σ
KVV", ا-)ه 1( vt)l
+=ds+1
i=d++1
24

---

Svk Σ (1 vi)l S (Vk + +))a
== +1
Hence we have that for any policy
(10, V=) - ( ( v=) S (V + 22Vō6|
H Proof of Theorem
Theorem 2. Consider the algorithm of computing A and any solution T66) to A6), - el for
5 ks and outputting the policy x =
arg ma ( (o((), V*). Then the policy π. =
satisfies that V² -w",, V x(6))
S (
Proof of Theorem 2. As shown in Lemma 1, set C. 2k and have ca
4k²e
We have
||''||
[w" li
VV and showed that (w", V=l 2 y' 2%
in the proof of Lemma 1.
By applying Lemma and setting ő ( wn2
11ae $
we have
0* - (wur, (w', Vx0lo))
-w0,, vmy ((u', (o. -
w/, )amalo))
(wo,, V ( (mn1o) v
(066) Vanlesy
C. h 1 112 1)3) (b) u=
O(V ||w0112
C ||00) 11
(12c)))) )t
=0(Vk ||w0|l2
I Dependency on
In this section, we would like to discuss a potential way of improving the dependency on c in Theorems 1 and 2.
Consider toy example where the returned three basis policies are गi with V = (1, 0), ma with **2 = 1,, and ITy with 1r (1, -n) for some > 0 and w" (1, (2, w3) for some
W2, W3g
The estimated ratio âj lies in [1 + we + u3 1 + w2 + ws + E), and a2 lies in [1 + 1 - 17W3
1 + 1w22 1ju3 + E]. Suppose that â + w2 + wa E and 22 mw2 17W3 + E.
By solving
1
0
W2 + W3 +
-1
-1
1
0
77 we can derive T w2 + [1 ) and Th3 wa + 5(1 )
1722 7wg + c
The quantity measuring sub-optimality
care about is sup, ( - (w", VT),, which is upper bounded by Cv || - " ||2- But the &g distance between and wn depends on the condition number of Ā, which is large when is small. To obtain non-vacuous upper bound in Section 3, we introduce another estimate (5) based on the truncated version of Á and then upper bound (6(6) w" ||| and
sup- (() VT) (1))), VT) separately.
However, it is unclear if sup,, k V*) - (w= V* depends on the condition number of Å. Due to the construction of Algorithm 1, we can obtain some extra information about the set of all policy values.
25

---

First, since we find T2 before must be no greater than 1. According to the algorithm, V is the optimal policy when the preference vector is U2 (see line 11 of Algorithm for the definition of u2) and V*3 is the optimal policy when the preference vector is
(0. 1, -1). Note that the angle between u2 and V is no greater than degrees according to the definition of u2- Then the values of all policies can only lie in the small box B {Ir E R | a|
I (m2. V=2)1, [ug 2| I
(u3, |]. is direct to check that for any E B. (w x) (w" 2) < (1+ 22).. This example illustrates that even when the condition number of is large, sup, ( V*) - (w", V*)l can be small. It is unclear if this holds in general. Applying this additional information sup, ((), V*) - (w", | directly instead of through bounding Cv || w w²l12 is a possible way of improving the term es.
upper bound
Description of C4 and Proof of Lemma 4
Algorithm C4: Compress Convex Combination using Carathéodory' 's theorem
1: input a set of k-dimensional vectors M C R and a distribution p E Simplex" M
2: while [M A + 1 do
3: arbitrarily pick k + 2 vectors f11,... Pk++ from M
4: solve for x E k s.t. D 2344 1) = O, where denote the vector of appending 1
to fu
5: in < arg ma p(u))
6: if rio < 0 then t -
p(uto) and Vi E [k: + 2]. p(u)) + p(u)) - ya
7: 7 2io
8: remove 14, with p(u) = 0 from M
9: end while
10: output M and
Lemma 4. Given a set of k-dimensional vectors M C R and a distribution p over M, C4(M, outputs M' M with M'| S k and distribution 9 Simplex satisfying that Eywg [M]] Byep [n] in time O([M) 1.3).
Proof. The proof is similar to the proof of Carathéodory's 's theorem. Given the vectors Pi..... 44-2 picked in line of Algorithm 4 and their probability masses p(n)), we solve R s.t. the algorithm.
Ek+2 (:4 o 1)
Note that there exists a non-zero solution of because {1r o 1/2 E [A: + 2}} are linearly dependent.
Besides, z satisfies hd+2 z; 0.
Therefore.
4+2
d42
Σ (p(us) yx;) Σ p(u).
For all i, x4 < 0. p(p) - -o, 2 as 7 > 0; if x4 then 3y
p(r)) S
aro plrio)
y and thus
p(u) Yo4 2 0.
Hence, after one iteration, the updated is still probability over M (i.e., p(u) 2 0 for all μ E M and ENEMP(M) = 1). Besides, dd+ (p(μ4) - 7m:)m4 = Σ p(u)) - 7 Σi x,44 = Edt7 p(44)44
Therefore, after one iteration, the expected value Ey<p [u] is unchanged.
When we finally output (M', q), we have that is distribution over M and that Epnn [n]] Eppo [n]].
Due to line 6 the algorithm, we know that Ti 0. Hence p(u),) - p(u4,)
p(utaa
Win 0.
2i0
We remove at least one vector Hig from M and will run for at most [M| iterations.
26

---

Finally, solving x' takes O(k2) time and thus, Algorithm 4 takes ({
time in total.
K Flow Decomposition Based Approach
We first introduce algorithm based on the idea of flow decomposition.
E) with H + 2 pairwise disjoint layers (0), ..... ( where every layer t < H contains a set of vertices labeled by the (possibly duplicated) states reachable the corresponding time step f, i.e., {s E S] Pr(S, = s|So = 80) 0).
For that, we construct layer graph G ((L U (..
Let us denote by 50 the vertex in (*) labeled by state s.
Layer L (H++1) = {-' ( contains only an artificial vertex, Z+ (1+1) labeled by an artificial state *, (++1) by edge (H+1) by one
For t O,.... H. 1, for every x! ((),, zs (++1) L(++1), connect (t) and zz
labeled by (s, x¹) if P(s'|s, π (s)) > 0. Every vertex de (H) in layer H connected to x. edge, which is labeled by (8, k).
We denote by Et)) the edges between (()) and ((+1), Note that every trajectory (50, , 88) corresponds to single path (arie Daa Fag ;
F. (H+1)) of length H + 2 from 2:10) to x:! (H+1))
.....,
This is one-to-one mapping and in the following, we use path and trajectory interchangeably.
The policy corresponds to (Ireu (0) (H+1)) )-flow -flow with flow value 1 in the graph G. In particular, the flow is defined follows.
When the layer is clear from the context, we actually refer to vertex xy by saying vertex s.
Fort t O..... 1, for any edge S') E E(1, f E + be defined as
((8,8))=
Σ (T)
(22)
where q" (T) the probability of being sampled.
For any edge (8,*) E(H), let J(s *) = Ee ((s,,)). It is direct to check that the function f is well-defined flow. We can therefore compute by dynamic programming.
For all (5o, 8) E E("), we have [(00 8) P(s|so, ((o)) and for (8,8") E E(O,
f(s,8')
Σ
f(s",s).
(23)
Now are ready to present algorithm by decomposing in Algorithm 5.
Each iteration Algorithm will zero out at least one edge and thus, the algorithm will stop within E) rounds.
Algorithm 5 Flow decomposition based approach
1: initialize Q <- 0.
2: calculate f(e) for all edge e E E by dynamic programming according to Eq (23)
3: while Je E E s.t. f(e) do
4: pick a path (50, ,,,..., ,H, +) E L()) x 1() x... [(H+1) s.t. [(8,, 8141) 1) 0
5: f - f(e)
6: (= f(e) + f(e) - fr for in
7: end while
8: output
Theorem 4. Algorithm 5 outputs Q satisfying that E4
f. = V in time O(H²² S
27

---

The core idea of the proof is that for any edge (s E E(O, the flow on ss. captures the probability of s St+1 = s' and thus, the value the policy V is linear in (f(e)le E}.
The output Q has at most [ number of weighted paths (trajectories). We can further compress the representation through C4, which takes Q(Q) R.) time.
Corollary 2. Executing Algorithm 5 with the output Q first and then running C4 over ((+(T), fr (T, E Q} returns a (k + 1)-sized weighted trajectory representation in time O(H2 | + H s(²).
We remark that the running time of this flow decomposition approach underperforms that of the expanding and compressing approach (see Theorem 3) whenever S + |S] = w(k* + k()).
L Proof of Theorem 4
Theorem 4. Algorithm oulputs Q satisfying that (1 = V time O(H² S)²).
Proof. Correctness: The function f defined by Eq (22) is a well-defined flow since for all t 1...., H. for all s E ((),, we have that
E
f(s,s')
E
E (-( E (T)
(E
TIS
Σ
f(s",s)
In the following, first show that Algorithm 5 will terminate with f(e) f all E.
First, after each iteration, f is still feasible (z=()),,((++))))- -.((++)))-foow feasible flow with the total flow
out-of z(0) reduced by fr. Besides, for edge with f(e) > 0 at the beginning, we have f(e) 2 0 throughout the algorithm because we never reduce f(ee by an amount greater than f(e).
Then, since is a (z:(),, ..(+1)))-flo and f(e) 2 0 for all E E, line 4 of Algorithm 5.
always find path in
Otherwise, the set of vertices reachable from (0) through edges with positive flow does not contain (H+1) and the flow out of this set equals the total flow out-of (()), But since other vertices not reachable, there is no flow out of this set, which is contradiction.
In line 6, there exists at least one edge such that f(e) 0 is reduced to O. Hence, the algorithm will run for at most [E| iterations and terminate with f(e) = 0 for all E.
Thus we have that for any ss) E(t), ff(ss')) Eo..))EE0(E fr.
Then we have
v = Σ9(())()) ΣT( -
Σ
R(s m(7))
H-1
(T)
Σ R(s,x(s))
Σ
(T)
(8,))
((s,T()))f(ss5')
1=
(5)))))
Σ
Σ R(s,x(s))
Σ
fr
L= (L)))))
(1
28

---

H-1 fi(
E (Td+)EQ
5 ((5{,
Σ (T).
(T.-))EQ
Computational complexity: Solving f takes O(E)) time. The algorithm will run for ((
iterations and each iteration takes ((H) time. Since | =[[S] H), the total running time of Algorithm is ((S) HF... C4 will take O [E]) time.
M Proof of Theorem 3
Theorem 3. Algorithm 2 outputs F(B) and g(m) satisfying that |F(D]
and
EreFin (T)) v* in time O H S + kH (S|?)
Proof. Correctness: C4 guarantees that [ E +
We will prove ΣtEron (()) V by induction
1, 1,...,, H.
Recall that for any trajectory T of length h, J(F) + H1 - ht) was defined as the expected return of trajectories (of length H) with the prefix being т.
In addition, recall that JP (J(r o 8){7 F()), 8 8) and g00) was defined by letting 300 (sssss
(T P For the base case, we have that at =
V R(s0, (+o)) + Σ ((o))) -1) ((s))) o ((50) o ()) 08)
1)
Σ Prim
so0 s00
Σ
(T)
TEFO)
Suppose that V E holds at time 1, then we prove the statement holds time + 1.
V== Σ (+)((( Σ (T)))((++++ t))
T'EO
MEFi
Σ ((0 ((())+ Σ P(s T(s) [R(s] m( )) (" ti)
((E
SES
Σ
Σ
309 (T)PP)))) ((x (0(7') R(sT ( )) V H H-
r'e SES
Σ r'EPOO sES
Σ
(H) ; (8( os) ( -
300
Σ
Σ Pri,,
(r)s))((7'os)
T'EP()) SES
Σ g(++)
TEFUH))
By induction, the statement holds at H by induction, i.e., V Ererim B Ereriny (()))
Computational complexity: Solving (s for all S, e [M]] takes time O(Hl ( In each round, we need to call C4 for < (k + 1) [S] vectors, which takes O(k-1 (S]) time. Thus, we need Olk' и [S] + kH ) time in total.
29

---

Example of maximizing individual objective
Observation 2. Assume there exist k 2 policies that together assemble linear independent value vectors. Consider the k different policies Ti...., " that each nł maximizes the objective i [R]] Then, their respective value vectors .i...., VE are not necessarily linearly independent. Moreover, to any 2 1. We will show an example where there are different value vectors, where of them are obtained by the k = 3 policies that maximize the 3 objectives and have linear dependence.
if ........ Vi are linearly depended it does not mean that k. linearly independent value vectors do not exists.
Proof. For simplicity, we show an example with a horizon of H = 1 but the results could be extended
Consider an MDP with single state (also known as Multi-arm Bandit) with actions with de- terministic reward vectors (which are also the expected values of the 4 possible policies in this case):
((1) = 8
85/12 r(2) = r(3) =
7.083
1 2
25/6 6
~
4.167
r(4) =
35/112
2.9167
Denote the fixed policy that always selects action a. Clearly, policy n' maximizes the first objective, policy x² the third, and policy x² the second (x+ do not maximize any objective). However,
r(3 linearly depends on r1) and r(2)
5
r(1) + r(2) = =r(3).
6
12
addition, r(4) linearly independent in r(1), r(2): Assume not. Then, there exists $1, E R s.t.:
831 + 82
1
B1 r(- 32.
4 + 28g
=
r(4).
281 + 382
2
Hence, the first equattion imply |32 1 8/3, and 43
2 16,3 3, hence
and B2 5 Assigning in the third equation yields
+ 2 which contradiction.
30


Reviews:
[{"review_id": "0bVZBdhIIh", "reviewer": "Reviewer_wfQV", "summary": "This paper proposes a method for multi-objective RL considering two user feedback models and thereby the first algorithms with theoretical guarantees for personalized MO decision making via policy comparison.  ", "questions": "You state that the method learns a user's preference vector using minimal number of queries, and C4 is used when the number is small, but discussion of what is small in the number of trajectories or minimal for queries?\n\nCould you give an intuitive example of how are the easily interpretable queries presented to the user.\n\nWhat are the limitations of the method?  ", "limitations": "Not really addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper prpoposes an interesting method for finding a personalized optimal policy for MORL problems reflecting users' unknown preferences over the objectives. It is very well written and scienitifically sound, motivates the work well. Method is presented clearly and carefully. The novelty and significance of the method are well presented.   ", "weaknesses": "The paper lacks conclusions and discusssion about limitations completely and thereby its utility is left a bit open.  The paper also emphasizes that it is important to present the obtained trajectories in an easy format to the user, but does not give any examples how this would be achieved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the informative review. We address the reviewer’s questions below. \n\n> The paper lacks conclusions and discussion about limitations.\n\nAs mentioned in our general response, we have deferred discussion to Appendix A due to space limitations. For the final version of the paper, we will move the discussion into the main paper.\n\n> Examples on how to present the obtained trajectories in an easy format to the user.\n\nIn the Google maps example (lines 16, 56, 300), each trajectory is a route. In the ChatGPT example (line 50), each trajectory is some text generated by a ChatGPT session with a different history. We will make sure to explain this in the final version of the paper. \n\n> What is small in the number of trajectories or minimal for queries or minimal for queries?\n\nBy “small” we mean polynomial in $|S|, |A|, H$.\nAs mentioned in lines 335-338, our goal is to compress a set of trajectories to the desired size in time $O(poly(H |S| |A|)))$ while the running time of C4 is linear in the size of the input trajectories (stated in Lemma 4), which can be $\\Omega(|S|^H)$. Hence, we adopt C4 as a subroutine when the number of trajectories is small. Thus, “small” here refers to $poly(H |S| |A|)$.\n\nRegarding ‘minimal’, a clear lower bound on the query complexity is $\\Omega(k+\\log(1/\\epsilon))$ queries. Our upper bound comes close to it with $O(k\\log(k/\\epsilon)$ queries.\n\n>Limitations of the method.\n\nWe have included some discussions of limitations in Appendix A (which we will move to the main paper).\n"}, {"review_id": "HnimijHgsW", "reviewer": "Reviewer_Gnoo", "summary": "_**Edit:** I have read the authors' rebuttal, and they have addressed all the concerns raised in my review._\n\nThe paper considers the problem of multi-objective reinforcement learning, when there is an unknown linear preference over the objectives, and approximate preference comparisons can be performed. The goal is to find an optimal policy (according to the true preference) while minimizing the number of comparisons.\n\nThe main task is identifying the unknown preference, which the paper shows how to do using Algorithm 1, Algorithm 3, and Theorem 1. Once the preference is (approximately) identified, Theorem 1 shows that solving the RL problem for this approximate preference returns a policy that is competitive with the optimal policy for the true preference.\n\nAdditionally, the paper also considers how preference comparisons could be implemented. One option is to ask the user to compare two policies directly, which might be hard to do. Because of this, the paper considers the case when the user can compare trajectories from two policies, which might be more interpretable to the user. To this end, the paper shows how to efficiently find a small (O(k)) weighted set of trajectories such that their weighted values are equal to the value of the policy (Algorithm 2).", "questions": "- Proof of Lemma 1: in the first inequality, shouldn't it be possible to reduce $k \\epsilon$ to $\\epsilon$? This would make Lemma 1 applicable to when $\\epsilon \\le v^\\*/(2k)$ rather than $v^*/(2k^2)$.\n- Is it possible to approximately estimate $\\epsilon$ by comparing $\\pi^1$ against a scaled version of itself (similar to the binary search in Algorithm 3)? If $\\hat{\\epsilon} \\approx \\epsilon$ can be estimated this way, can Theorem 2 be used with $\\delta = k^{5/3} \\hat{\\epsilon}^{1/3}$, avoiding the problem of having to guess the hyperparameter $\\delta$?\n- Have you considered the case when the user can compare policy value vectors? In this case, we can query with “artificial” values directly (e.g. basis vectors), requiring no interaction with the MDP at all. Perhaps this makes the problem too simple?\n- The preference identification procedure can be extended to general, non-tabular RL case. Is the same true for efficiently finding weighted trajectory sets?", "limitations": "The paper requires that preferences are linear, which is a fairly strong assumption. However, it is a good first step.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The procedure for identification of linear preference is not limited to just RL and can be used in a wider setting, making it of general interest.\n- Algorithm 1 adapts to $d \\le k$, which could be helpful in cases when there are many redundant objectives.\n- The weighted trajectory set representation of a policy is novel, interpretable, and possibly of wider interest.", "weaknesses": "- Line 220: “we only need to run Algorithm 1 once for all users”. This seems to be incorrect, as Algorithm 1 uses preference comparisons which depend on the user. This means the leading factor in the bound on line 256 should change from $(k^2+n)$ to $n (k^2 + 1)$.\n- The paper assumes the existence of a “do nothing” action, which might require a modified MDP. While this appears straightforward, it seems to me it requires domain-specific knowledge in order to modify it such that the “do nothing” policy has minimal value (which is the true requirement). E.g. in the chess example, perhaps refusing to play is considered a draw, which is better than a loss. Thus, a “do nothing” action would need to somehow always lose.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful and detailed review. We especially appreciate the kind comments about the novelty of our main contributions and their broader implications. Your suggestions are very helpful and we will execute them in the camera ready version. We address the reviewer’s questions below:\n\n> On  “we only need to run Algorithm 1 once for all users”.\n\nWe thank the reviewer for pointing this out. The reviewer is correct that the sentence ”we only need to run Algorithm 1 once for all users” was imprecise. We intended to say that we don’t have to fully run Algorithm 1 for $n$ times. In fact, when there are $n$ different users, we will run Algorithm 1 at most $k$ times instead of $n$ times. The reason is that Algorithm 1 only utilizes preference comparisons while searching for $\\pi_1$ (lines 1-6), and not for $\\pi_2, \\ldots, \\pi_k$ (which contributes to the $k^2$ factor in computational complexity). As there are at most $k$ candidates of $\\pi_1$, namely $\\pi^{e_1}, \\ldots, \\pi^{e_k}$, we execute lines 1-6 of Algorithm 1 for $n$ rounds and lines 7-15 for only $k$ rounds. Consequently, we need to update the leading factor of our computational complexity bound from $(k^2+n)$ to $(k^3+n)$.\n\n> “do nothing” action seems to require domain-specific knowledge in order to modify it such that the “do nothing” policy has minimal value (which is the true requirement). \n\nThis is correct and we'll be sure to explain this in the final version of the paper, we thank you for that.\n\n> On the proof of Lemma 1: in the first inequality, shouldn't it be possible to reduce $k\\epsilon$ to $\\epsilon$?\n\nWe agree with the reviewer that we are able to reduce $k\\epsilon$ to $\\epsilon$ if we compare every pair of $\\pi^{e_i}$ and $\\pi^{e_j}$. However, our prime focus is on minimizing the number of queries and this will increase the number of queries (used for searching $\\pi_1$) from $k$ to $k^2$. Hence, it is a trade off between the number of queries and accuracy. We'll be sure to address that in the final version of the paper.\n\n> Is it possible to approximately estimate $\\epsilon$ by comparing $\\pi_1$ against a scaled version of itself (similar to the binary search in Algorithm 3) to avoid guessing the hyperparameter $\\delta$?\n\nThis is an interesting observation! We agree with the reviewer that it seems correct to estimate $\\epsilon$ in this way. We will add it right after Theorem 2.\n\n> On direct value vector comparisons. Perhaps this makes the problem too simple?\n\nYes, if that would have been the case the problem would be very simple. However, it does not necessarily align with our motivation, where the goal is to compare realistic policies.\n\n>  Extension of weighted trajectory sets to general, non-tabular RL case.\n\nOur current techniques rely on a finite set of space. Generalizing them to a large environment would require a different technique. It could be a very interesting direction for future work.\n\n> On linear preference assumption.\n\nWe want to address that linearity is a standard assumption behind many works in multi-objective decision making and multi-objective RL.\n"}, {"review_id": "YbpgawE9hQ", "reviewer": "Reviewer_5457", "summary": "The paper provides a multi-objective decision-making framework to learn approximate optimal personalized policies by eliciting user preferences via comparative queries. The authors characterize theoretically two feedback models, explicit queries and weights queries sets, and derive sound algorithms with proven upper bounds on the learning complexity. ", "questions": "- If we consider human-decision making, do you think the two proposed feedback models are realistically usable by humans or do you think they might work well with agents, for example, in cooperative AI settings?", "limitations": "The authors adequately address all the limitations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To the best of my knowledge, the proposed algorithms and theoretical analysis are novel and interesting. Eliciting multi-objective user preferences over policies has a tremendous impact on many (real-world) settings in which decision-making systems aid humans in daily tasks. The paper is well-written. All the theoretical assumptions, results and algorithms are well-motivated and clearly described. I checked the proofs (and skimmed through the appendix), but a more rigorous analysis would require more time. ", "weaknesses": "In my opinion, I can see two main areas of improvement (1) extending the algorithm to noisy feedback from the users and (2) providing some empirical evidence about the effectiveness of the proposed algorithms.\n\nLastly, the paper is dense with information, but it ends abruptly. I would have enjoyed a paragraph either summarizing the main findings or expanding the current research to consider its potential practical impact (e.g., challenges in implementation).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the informative review. \n\n> On noisy feedback model and abrupt ending of the paper.\n\nWe have addressed these questions in the general response. Please refer to the general response for details.\n\n> Empirical evidence\n\nThis work is purely theoretical and our focus is on theoretical analysis.\n\n> Do you think the two proposed feedback models are realistically usable by humans or do you think they might work well with agents, for example, in cooperative AI settings?\n\nIndeed, openAI trained ChatGPT (and it is still training it) using human feedback regarding comparative queries. As mentioned in the response to Reviewer wfQV’s question on “Examples on how to present the obtained trajectories in an easy format to the user”, in the ChatGPT example (line 50), each trajectory is some text generated by a ChatGPT session with a different history.\n"}, {"review_id": "EvYRy4Etwn", "reviewer": "Reviewer_pTmr", "summary": "The paper presents a novel approach to elicit the unknown linear weights used to aggregate multi-objective valuations in sequential decision-making problems. The authors first consider comparative queries where a user can compare policies (instead of trajectories as in previous work). They investigate then the case where a policy can be replaced and approximated by a set of weighted trajectories.", "questions": "1) In footnote 1, why do the authors mention \"nearly\"? I think under the assumptions they make, optimal policies for every possible user preferences are in the set of Pareto optimal solutions.\n\n2) Are there situations where comparing sets of weighted trajectories would be practical for humans?\n\n3) Why do you not assume that the weight vector w^* is normalized since dividing by a positive value doesn't change the preferences over policies?\n\n4) Can the proposed technique be adapted if there is noise in the user's comparisons?\n\nSome minor issues:\n- line 107: V(\\pi) -> V^\\pi\n- line 128: In line 96, policies are introduced as stochastic, which seems to contradict with the explicit policy representation.\n- line 259: vacuous -> non-vacuous?", "limitations": "Not applicable, this is a theoretical paper.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "The paper investigates a novel approach for preference elicitation in multi-objective problems.\n\nThe authors obtain upper-bounds on the number of queries needed to obtain a near optimal policy for a given user.\n\nThe approach scales well with the number of users.", "weaknesses": "I think the obtained results are mostly of theoretical interest, because the type of considered queries is not very practical, in my opinion. Directly comparing policies is naturally usually not possible for humans, which motivates the second case investigated in this paper. However, even comparing two sets of weighted trajectories would be very hard for humans. \n\nIt is not clear if the proposed approach based on geometric and algebraic results can work in presence of noisy feedback from the user, which is a more realistic setting.\n\nThe writing, while reasonably clear, seems to be a bit rushed. Notably, the paper ends abruptly, without any conclusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the informative review. We address reviewer’s questions in the following and will incorporate the suggestions in the final version.\n\n> The type of considered queries is not very practical. Directly comparing policies is naturally usually not possible for humans, which motivates the second case investigated in this paper. However, even comparing two sets of weighted trajectories would be very hard for humans. Are there situations where comparing sets of weighted trajectories would be practical for humans?\n \n> [question #2] “Are there situations where comparing sets of weighted trajectories would be practical for humans?”\n\nConsider a casino with slot machines in which someone puts some money (e.g., a dollar) and receives money with some probability (e.g., $0$ w.p. 91% vs. $10$ w.p, 9%). Describing each game policy using a weighted set can be very practical. The same goes for investment strategy. \nNotice that the weights express probabilities or variance of the outcome.\nAnother example is driving. E.g., when the goal is to get from home to the airport, taking a specific route takes 40 minutes 90% of the time, but it can take 3 hours in case of an accident (which happens w.p. 10%) vs. taking the subway which always has a duration of 1 hour. \n\n\n> On noisy feedback model and abrupt ending of the paper.\n\nWe have addressed these in the general response. Please refer to the general response for details.\n\n> In footnote 1, why do the authors mention \"nearly\"?\n\nThat is correct, we will definitely remove the word ‘nearly’.\n\n> Why do you not assume that the weight vector $w^*$ is normalized since dividing by a positive value doesn't change the preferences over policies?\n\nIn terms of personalized optimal policy, you are correct that normalizing does not change the personalized optimal policy. However, the magnitude affects the “indistinguishability’’ in the feedback model. By not normalizing $w^*$, we allow users to have varying levels of discernment. For instance, consider two policies with values $(\\epsilon, 1)$ and $(0,1)$, respectively. For a user with preference vector $w^* = (1,1)$, they cannot differentiate between $(\\epsilon, 1)$ and $(0,1)$ and will respond with \"indistinguishable\" when queried to compare these two policies. On the other hand, for a user with preference vector $w^* = (2,2)$, they can distinguish between $(\\epsilon, 1)$ and $(0,1)$ and will indicate a preference for the former policy.\n\n> On minor comments\n\nThank you for pointing out the typos. For explicit policy representation, it should be corrected from a mapping from $S$ to $A$ to a mapping from $S$ to the simplex over $A$. We will fix the typos in the final version."}, {"review_id": "3dtoF5DdCW", "reviewer": "Reviewer_BDkG", "summary": "The paper presents a multi-objective decision making framework that accommodates different user preferences over multiple objectives. Furthermore, the framework facilitates learning these preferences via policy comparisons. The underlying model is assumed to be a finite horizon Markov decision process, while the user preference relation is assumed to be a linear combination of objective values. The preference relation is subsequently learned using user feedback taking two forms: policy comparison, and the comparison of two small sets of representative trajectories, respectively. The paper then suggests an algorithm for finding near-optimal policies using a number of comparison queries that scales quasi-linearly with the number of objectives.\n", "questions": "No specific questions.\n", "limitations": "I found the paper closely related to previous work by (Marinescu et al, 2017) which also looks at multi-objective decision making in the case of influence diagram models (which are actually more general than finite-horizon MDPs) and an unknown linear preference relation between objectives. The goal however, is slightly different, in that it is concerned with finding possibly optimal policies (which are optimal under at least one instantiation of the preference vector).\n\n(Marinescu et al, 2017) Marinescu, R., Razak, A. and Wilson, N. 'Multi-Objective Influence Diagrams with Possibly Optimal Policies', Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, California, USA, 4 – 9 February, pp. 3783 - 3789.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper addresses an important problem in decision making under uncertainty with multiple objectives which has a wide range of potential applications. \n", "weaknesses": "However, the paper has several shortcomings. First, the presentation lacks a small running example and therefore it is quite difficult to follow the technical details of the proposed approach. Second, I was surprised by the abrupt ending of the paper (with Theorem 3) without any follow-up or discussion. It gives the impression that the submission was rushed right before the deadline which is kinda disappointing. Third, the paper lacks any empirical evidence of the proposed approach and therefore we don't have any idea whether the approach is practical or not. For example, if the MDP has a very complex state (and/or action) space, how would one best represent and present the trajectories to the user to elicit feedback. While it seems straightforward in a toy-like setting, I don't think the preference elicitation scheme based on trajectories is actually practical in a real setting.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the informative review. We will address some of your comments below:\n\n> A small running example.\n\nWe will extend our usage of the Google maps example (lines 16, 56, 300) through the paper to improve the paper's readability. Thank you for your suggestion.\n\n\n> On abrupt ending of the paper.\n\nWe have addressed this in the general response. Please refer to the general response for details.\n\n> Third, the paper lacks any empirical evidence of the proposed approach and therefore we don't have any idea whether the approach is practical or not. For example, if the MDP has a very complex state (and/or action) space, how would one best represent and present the trajectories to the user to elicit feedback. While it seems straightforward in a toy-like setting, I don't think the preference elicitation scheme based on trajectories is actually practical in a real setting.\n\nWe agree that in cases where the state representation is complex, the task is challenging, but this challenge is a result of either the complexity of the system or a non-efficient design of the MDP that describes the environment (and it is not due to our solution). Preference elicitation scheme based on trajectories is actually quite practical. For example, openAI using them (where each trajectory is a chatGPT response). We will address this in the final version of the paper!   \n\n> On the reference (Marinescu et al, 2017)\n\nThank you for the reference. While we were not familiar with this work, in both the Introduction (lines 21- “While prior works have concentrated on approximating the Pareto-optimal solution set”, 81- “ Prior research has explored various approaches, such as assuming linear preferences or Bayesian Settings, or finding an approximated Pareto frontier”) and in the (additional) related work section (App B), we did describe some works with similar approaches  to that of (Marinescu et al, 2017). Namely, the approach of finding policies in the pareto front. As the reviewer said, our goal is different. Instead of finding a possibly optimal policy, we concentrate on specific user preferences and find a policy that is optimal for that specific user. Just like the ideal car for one person could be a Chevrolet Spark (small) and for another, it is a Ford Ranger (a truck). We promise to cite the work of (Marinescu et al, 2017) as well in the final version of the paper! \n"}]

Author rebuttal:
We would like to thank the reviewers for their valuable and informative reviews! Here we address some common questions.

> Response on abrupt ending of the paper

Due to space limitations, we have deferred the discussion section to Appendix A, where we discuss the results obtained in this work and open problems. We briefly indicated the deferral of the discussion to the appendix immediately after the related work section (line 87) due to space limitations. We will add the discussion section back to the end of the main paper in the final version.

> Response on noisy feedback model to Reviewer 5457 and Reviewer pTmr

Noisy feedback models would be an interesting future direction. If we consider the simplistic noisy model where the feedback is flipped with some fixed probability $\eta< 0.5$, then we can simply repeat each specific query for $1/(0.5-\eta)^2$ times to obtain the true feedback with high probability. Subsequently, the techniques outlined in this paper could be applied. More complex noise models are interesting for future work.

> Response on lack of empirical evidence to Reviewer 5457 and Reviewer BDkG

We would like to address that this work is purely theoretical and our focus is on theoretical analysis.

> Response on running examples to Reviewer wfQV and Reviewer BDkG

We will extend our usage of the Google maps example (lines 16, 56, 300) through the paper to improve the paper's readability. Thank you for your suggestion.

If we misunderstood any of the questions, we would be happy to clarify any further information during the discussion period. Overall, your feedback is valuable, and we appreciate the opportunity to enhance the paper's coherence and readability!


Meta-review: This paper considers a multi-objective RL framework that can model different user preferences over objectives, where these preferences are learned via policy comparisons. The paper proposes algorithms to learn the near-optimal policy for two kinds of feedback and characterizes their query complexity. 

The reviewers tend to agree that the paper is well-written, and its contributions merit acceptance. I agree and recommend the acceptance of this paper. Please incorporate the reviewer's comments in the final version of the paper. In particular, addressing the following concerns will help strengthen the current version of the paper:
- Add the discussion in Appendix A to the main paper. 
-  Expand on the Google Maps running example, and better justify the proposed feedback model using more examples (response to Rev. 5457, Rev. pTmr)
- Update the leading factor of our computational complexity of Alg 1, update the proof of Lemma 1, and add the discussion about the better approximation of $\epsilon$ (response to Rev. Gnoo)
- Include the reference (Marinescu et al, 2017) in the paper.
Decision: Accept (poster)