Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
Authors: Jingfeng Wu
Vladimir Braverman
Lin Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: RL
multi-objective
sample complexity
unsupervised exploration

Abstract: In this paper we consider multi-objective reinforcement learning where the objectives are balanced using preferences. In practice, the preferences are often given in an adversarial manner, e.g., customers can be picky in many applications. We formalize this problem as an episodic learning problem on a Markov decision process, where transitions are unknown and a reward function is the inner product of a preference vector with pre-specified multi-objective reward functions. We consider two settings. In the online setting, the agent receives a (adversarial) preference every episode and proposes policies to interact with the environment. We provide a model-based algorithm that achieves a nearly minimax optimal regret bound $\widetilde{\mathcal{O}}\bigl(\sqrt{\min\{d,S\}\cdot H^2 SAK}\bigr)$, where $d$ is the number of objectives, $S$ is the number of states, $A$ is the number of actions, $H$ is the length of the horizon, and $K$ is the number of episodes. Furthermore, we consider preference-free exploration, i.e., the agent first interacts with the environment without specifying any preference and then is able to accommodate arbitrary preference vector up to $\epsilon$ error. Our proposed algorithm is provably efficient with a nearly optimal trajectory complexity $\widetilde{\mathcal{O}}\bigl({\min\{d,S\}\cdot H^3 SA}/{\epsilon^2}\bigr)$. This result partly resolves an open problem raised by \citet{jin2020reward}.

A ccommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
Jingfeng Wu Department of Computer Science Johns Hopkins University Baltimore, MD 21218 uuujf0jhu. edu
Vladimir Braverman
Department of Computer Science Johns Hopkins University
Baltimore, MD 21218 vovašcs. juu. edu
Lin F. Yang
Department of Electrical and Computer Engineering University of California, Los Angeles
Los Angeles, CA 90095 1 linyang@ee ucla.
Abstract
In this paper consider multi-objective reinforcement learning where the objec- tives are balanced using preferences. In practice, the preferences are often given in adversarial manner, e.g., customers be picky in many applications. We formalize this problem as an episodic learning problem on a Markov decision pro- cess, where transitions preference vector with pre-specified multi-objective reward functions. We consider settings. In the online setting, the agent receives (adversarial) preference every episode and proposes policies to interact with the environment. We provide model- based algorithm that achieves nearly minimax optimal regret bound ( //mm S} HASAK), where d is the number of objectives, S is the number of states, A is the number of actions, H is the length of the horizon, and K is the number of episodes. Furthermore, we consider preference- exploration, i.e., the agent first interacts with the environment without specifying any preference and then able to accommodate arbitrary preference vector up to error. Our proposed algorithm is provably efficient with nearly optimal trajectory complexity Ö (minfd, S} H SA/c)). This result partly resolves open problem raised by Jin et al. [2020].
unknown and reward function is the inner product of a
Introduction
In single-objective reinforcement learning (RL), sealar reward is pre-specified and agent leams a policy to maximize the long-term cumulative reward [Sutton and Barto, 2018]. However, in many real-world applications, need to optimize multiple objectives for the same (unknown) environment, even when these objectives are possibly contradicting [Roijers et al., 2013]. For example, in an autonomous driving application, each passenger may have different preference of driving styles: some of the passengers prefer a very steady riding experience while other passengers enjoy the fast acceleration of the car. Therefore. traditional single-objective RL approach may fail to be applied in such scenarios. One way to tackle this issue is the multi-objective reinforcement learning (MORL) [Roijers al., 2013, Yang et al., 2019, Natarajan and Tadepalli, 2005, Abels et al., 2018]
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

method, which models the multiple objectives by vectorized reward, and an additional preference vector to specify the relative importance of each objective. The agent of MORL needs to find policies to optimize the cumulative preference-weightee rewards.
If the preference vector is fixed drawn from fixed distribution, MORL is no more challenging than single-objective RL, as we can predict the objective to be optimized and apply (variants of) single-objective RL algorithms (e.g.. [Azar al., 2017]). However, more often in practice, the preference vector (under which the weighted objective needs to be optimized) is:
adversarially provided,
(ii) or even not available in the learning phase.
Once more taking the autonomous driving application example: (i) the intelligent system needs to adapt driving configurations to accommodate every customer, even though the next customer can have picky preference that is unpredictable; (ii) when the intelligent system is under development, the future customer cannot be known in advance, nonetheless, when the system is deployed, it has to be capable accommodate any potential customer who rides the car. Such MORL examples are common, to name a few beyond the autonomous driving one: medical treatment must take care of every patient even in very rare health conditions; an education system should accommodate every student according to his/her own characteristics; and emergency response systems have to be responsible in all extreme cases. Due to these exclusive challenges that have not appeared in single-objective RL, new sample-efficien algorithms for MORL need to be developed, as well as their theoretical grounds need to be established.
In this work, we study provable sample-efficiens algorithms for MORL that resolve the aforemen- tioned issues. Specifically, we consider MORL finite-horizon Markov decision process (MDP) with an unknown transition kernel, S states, A actions, H steps, and d reward functions that represent the d difference objectives. We investigate MORL problems in two paradigms: (i) online MORL (where the preferences are adversarially presented), and (ii) preference-fre exploration (where the preferences are not available in the learning/exploration phase). The two settings and our contributions are explained respectively in the following.
Setting (i): Online MORL. We first consider online learning problem to capture the challenge that preference vectors could be adversarially provided in MORL. In the beginning of each episode, the MORL agent is provided (potentially adversarially) with preference vector, and the agent interacts with the unknown environment to collect data and rewards (that is specified by the provided preference). The performance of algorithm is measured by the regret, i.e., the difference between the rewards collected by the agent and those would be collected by a theoretically optimal agent (who could use varying policies that adapt to the preferences). This setting generalizes the classical online single-objective RL problem [Azar et al., 2017] 7] (where d = 1).
Contribution (i). For online MORL, we provide provably efficient algorithm with regret upper bound Ō (v (i HASAK)! where K is the number of episodes for interacting with the en- vironment. Furthermore, we show an information -thoorethc lower bound Q / (d, S} H2SAK) for online MORI. These bounds together show that, ignoring logarithmic factors, algorithm resolves the online MORL. problems optimally.
Setting (ii): Preference-Free Exploration. We further consider an unsupervised MORL problem to capture the issue that preferences could be hard to obtain in the training phase. The MORL agent first interacts with the unknown environment in the absence of preference vectors; afterwards, the agent is required to use the collected data to compute near-optimal policies for an arbitrarily specified preference vector. The performance is measured by the sample complexity, i.e., the minimum amount of trajectories that an MORL agent needs to collect during exploration in order to be near-optimal during planning. This setting extends the recent proposed rewerd-free exploration problem [Jin et al., 2020] to MORI..
Contribution (ii). For preference- free exploration, we show that a simple variant of the proposed online algorithm can achieve nearly optimal sample complexity. In particular, the algorithm achieves a sample complexity upper bound Ô (min(d, S}- H SA/e) where is the tolerance of the planning error; and we also show a sample complexity lower bound, Mmmin(d, S} SAA") for any
We use Ō()) to hide (potential) poly loarihgaii factors in 0(-), Ö(n) == O(n log" n) for sufficiently large n and some absolute constant k 0.
2

---

algorithm. These bounds suggest that our algorithm is optimal in terms of d. S, A, up to logarithmic factors. is also worth noting that our results for preference-free exploration partly answer am open question raised by Jin et al. [2020]: reward-free RI. is easier when the unknown reward functions enjoy low-dimensional representations (as in MORL).
Paper Layout. The remaining paper is organized as follows: the preliminaries are summarized in Section 2; then in Section 3, we formally introduce the problem online MORL, our algorithm and its regret upper and lower bounds; then in Section 4, we turn to study the preference- free exploration problem in MORL, where we present an exploration algorithm with sample complexity analysis (with both upper bound and lower bound), and compare our results with existing results for related problems; finally, the related literature is reviewed in Section 5 and the paper is concluded by Section 6.
2
Preliminaries
We specify a finite-horizon Markov decision process (MDP) by a tuple of AS..A. S finite state set where |S]= - S. A finite action set where |A| = A. H is the length of the horizon. P.. I, a) is a stationary, unknown transition probability to new state for taking action at state I. r = (ri,.... } ). where Th : S x A - [0, 1] represents a d-dimensional vector rewards function that captures the d objectives?. W == w E [0, 1jd, ||l||| = }} specifies the set of all possible preference vectors', where each preference vector w E W induces a scalar reward function by" rh r=(::-)= = (w, rx( .)) for h = 1..... H. A policy is represented by each (-) maps a state to a distribution over the action set. Fixing a policy æ, we will consider the following generalized Q-value function and generalized value function:
{T1..... TH where
Q7 (1 = E E[E (w, T, (5 (1)) = x, an = =a] (x; = Q7 (2, Ta (2); w),
where zj (. 2z-1, and 0j (x)) for j h. Note that compared with the typical Q-value function (or the value function) used single-objective RL, here the generalized Q-value function (or the generalized value function) takes the preference vector as an additional input, besides the state-action pair. Fixing a preference w E W, the optimal policy under w is defined as T = arg.ax. max, (111 w). For simplicity, we denote
Q% (z. a; w) = 0 (2,,,w); (x; == Vi= (z; max Qh ax))
The following abbreviation is adopted for simplicity:
PV l,,,, VV, == EyesP (v;w),
and similar abbreviations will be adopted for variants of probability transition (e.g., the empirical transition probability) and variants of value function (e.g., the estimated value function). Finally, we remark that the following Bellman equations hold for the generalized Q-value functions
S (T. az w) = (w, (2 + PV.. I, : V (2; w)) (z):
(x, ([r,a;w)) = (w, r. a)) + PV z.a."
V (2; max, Q7 (zx a; w)
With the above preparations, we are ready to discuss our algorithms and theory for online MORL (Section 3) and free exploration (Section 4).
3 Online MORL
Problem Setups. The online setting captures the first difficulty in MORL, where the preference vectors can be adversarially provided to the MORL agent. Formally, the MORL agent interacts with
For the sake of presentation, we discuss bounded deterministic reward functions in this work. The techniques can be readily extended to stochastic reward settings.
'The condition that w E [0, 1] only assumed for convenience. Our results naturally generalize to preference vectors that are entry-wisely hounded by absolute constants.
'The linear scalarization method can be generalized. See more discussions in Section 3.2, Remark 2.
3

---

an unknown environment through Protocol I: at the beginning of the k-th episode, an adversary selects preference vector w and reveals the agent; then starting from fixed initial state" 21. the agent draws trajectory from the environment by recursively taking action and observing new state, and collects rewards from the trajectory, where the rewards are scalarized from the vector rewards by the given preference. The agent's goal is to find the policies that maximize the cumulative rewards. Its performance will be measured by the following regret: suppose the MORL agent has interacted with the environment through Protocol for K episodes, where the provided preferences are fu= JK j and the adopted policies are {x * 11 Jk-1 correspondingly, we consider the regret of the collected rewards (in expectation) competing with the theoretically maximum collected rewards (in expectation):
(egret(K) == Eken Vi1;; VT" ((1:w")
(1)
Clearly, the regret (1) is always non-negative, and a smaller regret implies a better online performance. We would like to highlight that the regret (1) allows the theoretically optimal agent to adopt varying policies that adapt to the preferences.
Protocol Environment Interaction Protocol
Require: MDP(S,, A, H, P, r, W) and online agent
1: agent observes (S, A, H,r, W)
2: for episode h 1,2, ...., K do
3: agent receives an initial state xx = 21, and a preference whth (from an adversary)
4: for step h = 1,2,.... ................. H do
5: agent chooses an action ax and collects reward (w* on (a at))
6: agent transits to a new state 2/t1 ~ PP( 1 a/)
7: end for
8: end for
Connections to Online Single-Objective RL.
The online regret minimization problems are well investigated in the context of single-objective RL (see, e.g., [Azar et al., 2017, Jin et al., 2018J). In both online objele-objective RL and our studied on- line MORL, it is typical to assume that the transition probability P is the only unknown information about the environment since estimating a stochastic reward is relatively easy (see, e.g., [Azar et al., 2017, Jin et al., 2018]). In particular, single-objective RL is a special case of MORL in the online setting, where the preference is fixed during the entire learning pro- cess (i.e., - : w for all k) therefore an online MORL algorithm naturally applies to single-objective RL. However, the reverse is not true as that in MORL
MO-UCBVI
002
Best stationary policy
300
total regrat
200
200
1365
2000
3050
1000
5953
number of episodes
Figure 1: A regret comparison of MO-UCBVI vs. the best-in-hindsight policy in simulated ran- dom multi-objectivv MDP. Note that the best-in- hindsight policy is the optimal policy for single- objective RL. The plots show that the best-in- hindsight policy will incur linear regret in online MORL, and the proposed MO-UCBVI achieves sub- linear regret as predicted by Theorem 1. See Ap- pendix A for details.
the preference vectors can change over time and are potentially adversarial.
Comparison with Single-Objective Stochastic and Adversarial Reward Setting. The essential difficulty of MORL is further reflected in the regret (I). Specifically, the regret (1) compares the perfor- mance of the agent's 's policies to sequence of optimal policy under each given preference, which could vary over time. However, in online single-ohjective RI, either with known/stochastic re- wards [Azar et al., 2017, Jin et al., 2018] or adversarial rewards [Rosenberg and Mansour, 2019, Jin et al., 2019], the benchmark policy is supposed to be fixed over time (the best policy in the hindsight). This difference suggests that online MORL could be more challenging than online single-objective RL, as harder performance measurement adopted. More specifically, when measured by regret
'Without loss of generality, we fix the initial state; otherwise we may as well consider an MDP with an external initial state with zero reward for all actions, and a transition Po(- @o, a) = PP(()) for all action a. This is equivalent setting by letting the horizon length H be H

---

(I), existing algorithms for regret when the sequence of preferences adversarially designed; contrast, we will show an MORL algorithm that experiences at most x O(v regret under any sequence of preferences. A numerical simulation of this issue is presented in Figure 1.
RL (e.g., [Azar et al., 2017]) easily suffer ((K)
3.1 A Sample-Efficient Online Algorithm
In this part we introduce algorithm for online MORL, called multi-objective upper confidence bound value iteration (MO-UCBVI). A simplified verison MO-UCBVI is presented as Algorithm 1, and more advanced version (Algorithm 4) can be found in Appendix B. Our algorithm is inspired by UCBVI [Azar et al., 2017] that achieves minimax regret bound in online single-objective RL.
Algorithm MO-UCBVI
initialize history 7
2: for episode k = 1, 1,2.... K do
3: (x, P (y I, Empi- Empi-Prob(H(
/ min (d.8) H², (=,aa,)
4: compute bonus 6t (z,
where log(HSAK/o) and i constant
5: receive preference w
6: {Qh (z, a; w + UCB-Q-Valuel (Pt w (*)
7: receive initial state 2 21
8:
for step / = 1, 2, do
9: take action of arg max. Q (2h a; wh), and obtain new state 2/+11
10: end for
update history H H ( a
12: end for
13: Function Empi-Pro
Require: history 7
15: for (x.0,y) E S
16:
(* = #((,,, E H* and (², := Ey (
17:
if N* a) > then
18:
P*(y x,a) = NN a, V)/N
19: else
20: P*(y Jr.a = 1/S
21: end if
22: end for
23: return N* (z, a) and 15t a)
24: Function UCB-Q NCB-Q-Value
25: Require: empirical transition P* preference w and bonus b* (xx a)
26: set V V++1 (x,w** 0
27: for step
H. 1,..., do
28: for (I,a) ES do
29: Qh w min {11, (w" rn(a, a)) (*, PAVE
30: Va; wh) max.EA (1
31: end for
32:
end for
33:
return (=
In Algorithm 1, the agent interacts with the environment according to Protocol 1, and use an optimistic policy to explore the unknown environment and collect rewards. The optimistic policy is a greedy policy with respect to an optimistic estimation to the value function, UCB-Q-Value (lines and 9). Specifically, UCB-Q-Value is constructed to maximize the cumulative reward, which is scalarized by the current preference, through dynamic programming over an empirical transition probability (line 24). The empirical transition probability is inferred from the data collected so far (lines 3 and
5

---

13), which might not be accurate if a state-action pair has not yet been visited for sufficient times. To mitigate this inaceuracy UCB-Q-Valus utilizes an extra exploration bonus (lines 4 and 29) so that: (i) 119-Q-Value never under-estimates the optimal true value function, for whatever preference vector (and with high probability); and (ii) the added bonus shrinks quickly enough (as the corresponding state-action pair continuously being visited) so that the over-estimation is under control. The overall consequence is that: MO-UCBVI explores the environment via a sequence of optimistic policies, in order to collect rewards under a sequence of adversarially provided preferences; since the policies are optimistic for any preference, the incurred regret would not exceed the total amount of added bonus; and since the bonus decays fast, their sum up would be sublinear (with respect to the number of episodes played). Therefore MO MU-UCBVI only suffers sublinear regret, even when the preferences are adversarially presented. The above intuition is formalized in the next part.
3.2 Theoretical Analysis
The next two theorems justify regret upper bounds for MO-UCBVI and a regret lower bound for online MORL problems, respectively.
Theorem (Regret bounds for MO-UCBVI), Suppose K is sufficiently large. Then for any sequence of the incoming preferences {w* JEz with probability at least
the regret (1) of X0-UCBVI (see Algorithm 1) satisfies
regret(K) s (0/miindd.55550 H3SAK log(HSAK//));
and the regrel (1) of Bernstein-variant KO- UC-UCBVI (see Algorithm 4 in Appendix B) satisfies
regret(K) S 50(v min S} H2SAK log" (HSK/(0))
Theorem (A regret lower bound for MORL). There exist some absolute constants c, Ko > O, such that for any K >> Ko. any MORL algorithm that runs K episodes, there is set of MOMDPs and sequence of (necessarily adversarially chosen) preferences vectors such that
E[regret(K]] 2 e- /mmi {d, S} H2SAK,
where the expectation is laken with respect to the randomness of choosing MOMDPs and the randomness of the algorithm for collecting dataset.
Remark When d = 1, MORL recovers the single-objective RL setting, and Theorem recovers existing nearly minimax regret bounds for single-objective RL [Azar et al., 2017, Zanette and Brunskill, 2019]. Moreover, the lower bound in Theorem implies that our upper bound in Theorem I is tight ignoring logarithm terms. Interestingly, the lower bound suggests MORL with d > 2 is truly harder than single objective RI. (corresponding adversarially chosen.
1) as the sequence of preferences can be
Remark 2. Theorem (as well as our other theorems) applies to general scalarization methods besides the linear one as adopted by Algorithm and many other MORL papers [Yang et al., 2019, Roijers et al., 2013, Natarajan and Tadepalli, 2005, Abels et al., 2018). In particular, our results apply to scalarization functions Fn () = (rr (::)); w) that are (1) deterministic, (2) Lipschitz continuous for w, and (3) bounded between j0, 1] (which can be relaxed). This will be clear from proofs in Appendix B, where we treat the potentially adversarially given preferences by a covering argument and union bound, and these techniques not dedicated to linear scalarization function and can be casily extended to more general cases.
The proof of Theorem leverages standard analysis procedures for single-objective RL [Azar et al., 2017, Zanette and Brunskill, 2019], and covering argument with an union bound to tackle the challenge of adversarial preferences. Th rigorous proof is included in Appendix B.
Specifying an adversarial process of providing preferences is the key challenge for proving Theorem 2. reduction techniques and utilize lower bound that we will show shortly
To handle this issue, for preference-fier exploration problems. We refer the readers to Theorem and Appendix E for more details.
4 Preference-Free Exploration
Preference-fiee exploration (PFE) captures the second difficulty in MORL: the preference vector might not be observable when the agent explores the environment. Specifically, PFE
Problem Setups.

---

consists of an exploration phase and planning phase. Similarly as in the online setting, the transition probability is hidden from the MORL agent. In the exploration phase, the agent interacts with the unknown environment to collect samples. however the agent has no information about the preference vectors at this point. Afterwards PFE switches to the planning phase, where the agent prohibited to obtain new data, and is required to compute near-optimal policy for any fiferrence-wiigheee reward functions, Since this task is no longer in an online fashion, we turn to measure the performance of a PFE algorithm by the minimum number of required trajectories (in the exploration phase) so that the algorithm can behave near-optimally in the planning phase. This is made formal as follows: a PFE algorithm is called (c, 6) -PCC (Probably Approximately Correct), if
P P( W, (=) (T w) 2-
where Tw is the policy outputted by the PFE algorithm for input preference w. then the sample complexity of a PFE algorithm is defined by the least amount of trajectories it needs to collect in the exploration phase for being (e, P-PAC in the planning phase.
Connections to Reward-Free Exploration. PFE problem is natural extension to the recent proposed reward-free exploration (RFE) problem [Jin et al., 2020, Kaufmann al., 2020, Wang et al., 2020, Ménard et al., 2020, Zhang et al., 2020b]. Both problems consist of an exploration phase and planning phase; the difference is in the planning phase: in RFE, the agent needs to be able to compute near-optimal policies for all reward functions, while in PFE, the agent only needs to achieve that for all preference-weighted reward functions, i.e., the reward functions that can represented as the inner product of d-dimensional preference vectors and the dddimensional vector rewards functions (i.e., the d objectives in MORL). A PFE problem reduces to a RFE problem if = S'A such that every reward function can be represented as preference-weighted reward function. However, if < SA, it is conjectured by Jin et al. [2020] that PFE can be solved with a much smaller sample complexity than RFF. Indeed, in the following part we show an algorithm that improves a ix O(5²) dependence for RFE to Ominndd S} S) dependence for PFE, in terms of sample complexity.
4.1 A Sample-Efficient Exploration Algorithm
We now present a simple variant of MO-UCBVI that is sample-efficient for PFE. The algorithm is called preference-free upper confidence bound exploration (PF-UCB), and is discussed separately as in the exploration phase (Algorithm 2) and in the planning phase (Algorithm 3) in below.
Algorithm 2 PF-UCB (Exploration)
1: initialize history H. 0
2: for episode k = 1, 1, 2...., K do
3: (²,x,a), 1 x, a) + Empi-Prob(?!
4: compute bonus c (x, (x,a) a) 2N'(2,a)
H²S
2b (1) a) for by a) defined in Algorithms 1 or
5: (2, (((rr,))][= a) + UCB -CB--QVaalee Value (f² w = 0,
6: receive initial state o = σ1
7:
for step h = 2, ... H do
8: take action a arg max 4x (at; a). and obtain a new state r/
9: end for
10: update history H² Hk- u ( of Wh
11: end for
Algorithm 2 presents our PFE algorithm in the exploration phase. Indeed, Algorithm 2 is modified MO-UCBVI (Algorithm 1) by setting the preference to be zero (Algorithm 2, line 5), and slightly enlarging the exploration bonus (Algorithm 2, line 4). The intention of an increased exploration bonus will be made clear later when we discuss the planning phase. With zero preference vector, the JCB-Q-Valme in Algorithm 2 will identify trajectory along which the cumulative bonus (instead of the cumulative rewards) maximized (with respect to the empirical transition probability). Also note that the bonus function (Algorithm 2, line 4) is negatively correlated with the number of visits to state-action pair. Hence the greedy policy with respect to the prro-erefeeence UCB-Q uCB-qe tends to visit the acttonactions pairs that are associated with large bonus, i.c., those that have been visited
7

---

Algorithm 3 PF-UCB (Planning)
Require: history HK preference vector w
1: for k = 1.2..... K do
2: (x, P (yllr, a) +- Empi-Prob
compute bonus 6% (x, := c. V N4(2,0) w,bb)
mini min(d.S) where i log(HSAK/0) and is constant
4: (Q)();;))E + UCB-Q-Valuel
5: infer greedy policy (x) = arg max, (2;
6: end for
7: return т drawn uniformly from [=*]
for less times. In sum, Algorithm explores the unknown environment "uniformly", without the guidance of preference vectors.
Then Algorithm shows our PFE algorithm in the planning phase. Given any preference vector, Algorithm 3 computes sequence of optimistically estimated value functions based on the data collected from the exploration phase, and then outputs a greedy policy with respect to a randomly drawn optimistic value estimation. Note that the bonus in Algorithm 3 is set the one in Algorithm 1, and recall that the bonus in Algorithm exploration phase guarantees that the regret in the planning phase never exceeds that in the exploration phase. On the other hand, based on Theorem for MO-UCBVI (Algorithm 1), we have already known that the exploration algorithm (Algorithm 2), a modified Algorithm 1, suffers at most Ó v K') regret, hence the planning algorithm (Algorithm 3) experiences most ((1VVK) error. The next part rigorously justifies these discussions.
an enlarged one. The relatively large bonus in the
4.2 Theoretic Analysis
We first provide Theorem 3 to justify the trajectory complexity of Algorithms and in the PFE setting: then we present Theorem that gives an information-theoretiic lower bound on the trajectory complexity for any PFE algorithm.
Theorem 3 (A trajectory complexity of PF-UCB). Suppose PF-UCB (Algorithm 2) for
0 is sufficiently small. Then for
(min (d, S} H& where log(HSA/(5c),.
episodes, PF-UCB (Algorithm 3) is (e.C.-PAC.
Theorem (A lower bound for PFE). There exist absolute constants c, En O, such that for any
0 < c < there exists a set of MOMDPs such that any PFE algorithm that is (c, O.1.PPACC on them, needs collect at least
K 2 Qmin {d, HTSSA/e)
trajectories in expectation (with respect to the randomness of choosing MOMDPs and the exploration algorithm).
Remark 3. According to Theorems and the trajectory complexity of PF-UCB is optimal for d, S, A, ignoring logarithmic factors, but is an H factor loose compared with the lower bound. This because the current Algorithm 2 utilizes a preference-indeee -inrreeedeenddeednntt Hoeffding type bonus since the preference vector is not available during exploration. We leave it as an open problem to further remove this gap about H.
Proof Sketch of Theorem 3. Theorem 3 is obtained in three procedures. (1) We first observe the ((ymin (d, S) H H*SAK) according to Theorem (2) Then
total regret incurred by Algorithm utilizing the enlarged exploration bonus, we show that in each episode, the planning error is at most constant times of the incurred exploration error. (3) Thus the averaged planning error at most Ō( ((Cmin (d, HA/AK) as claimed. A complete proof deferred to Appendix C.
Note that the second argument is motivated by [Zhang et al., 2020a, Wang et al., 2020]. However in their original paper, a brute-force union bound over all possible value functions are required obtain similar effect, due to the limitation of model-free algorithm [Zhang et al., 2020a] (see Appendix F

---

for more details) or linear function approximation [Wang et al., 2020]. This will cause loose, (SS) complexity in the obtained bound. Different from their approach, carefully manipulate a lower order term to avoid union bounding all value functions during the second argument. As a consequence we obtain a near-tight x (min S} .S dependence in the final bound. We believe this observation has broader application in the analysis of similar RI. problems.
(d,
Proof Sketch of Theorem 4, We next introduce the idea of constructing the hard instance that witnesses the lower bound in Theorem 4. A basic ingredient is the hard instance given by Jin et al. [2020]. However, this hard instance is invented for RFE, where the corresponding lower bound is K
A/c²). Note this lower bound cannot match the upper bound in Theorem 3 in terms of d and S. In order to develop a dedicated lower bound for PFE, we utilize Baanson-Lindenstruue Lemma [Johnson and Lindenstrauss, 1984] to refine the hard instance in [Jin al., 2020], and successfully reduce a factor S to min {d, S} in their lower bound, which gives the result in Theorem 4. We believe that the idea to refine RL hard instance by Johnson-LLiddenstrauss Lemma is of broader interests. A rigorous proof is deferred to Appendix D.
Application in Reward-Frid Free Exploration. By setting d = SA and allowing arbitrary reward functions, PFE problems reduce to RFE problems. Therefore as a side product, Theorem 3 implies the following results for RFE problems on stationary or non- non-stationary MDPs
Corollary 5. Suppose e is sufficiently small. Consider the reward-free exploration problems on stationary MDP. Suppose PF-UCB (Algorithm 2) is runfor
K = 52 where == log( (og(H)
episodes, then PF-UCB (Algorithm 3) is (c, PAC. Moreover, the MDP is non-stationary, the above bound will be revised to =
Remark 4. When applied to RFE, PF-UCB matches the rate shown in [Kaufmann et al., 2020] and improves an H factor compared with [Jin et al., 2020] (for both stationary and non-stationary MDPs), but is an H factor loose compared with the current best rates, [Ménard et al., 2020] (for non-stationary MDPs) and [Zhang et al., 2020b] (for stationary MDPs). However we highlight that our results are superior in the context of PFE, since PF-UCB adapts with the structure of the rewards. In specific, if rewards admit d-dimensional feature for d < S, PF-UCB only needs Ommin dd, S} S) samples, but the above methods must explore the whole environment with a high precision which consumes x (S?) samples.
Application in Task-Agnostic Exploration. PFE is also related to task-agnostic exploration (TAE) [Zhang et al., 2020a]: in PFE, the agent needs to plan for an arbitrary reward function from fixed and bounded d-dimensional space: and in TAE, the agent needs to plan for N fixed reward functions. Due to the nature of the problem setups, PFE algorithms (that do not exploit the given reward basis r during exploration, e.g., ours) and TAE algorithms can be easily applied to solve the other problem through a covering argument and union bound, and with a modification of min(d, S} ++ log(NN in the obtained trajectory complexity bounds. For TAE a non-stationary MDP, Zhang et al. [2020a] show an algorithm which takes Ölog(N) 1/SSA/e* episodes for TAE". In comparison, when applied to TAE on a non-stationary MDP, Theorem 3 implies PF-UCB only takes (log(NN) -H*SA/ee) episodes*, which improves [Zhang et al., 2020a].
"Our considered MDP is stationary as the transition probability P is fixed (across different steps). An MDP is called non-stationary, if the transition probability varies at different steps, ie., replacing IP by (PP) ) "This bound is copied from [Zhang et al., 2020a]. which is erroneously stated due to a technical issue in the proof of Lemma in their original paper. The issue can be fixed by covering argument and union bound on the value functions, but then the obtained bound should be Ö (log(NN) S2 A/e"). See Appendix F for details.
"The conversion holds as follows. First set d in our algorithm to yield algorithm for TAE with single agnostic task, where we have min(d, S} = Then one can extend this algorithm to TAE with agnostic tasks using a union bound to have the algorithm succeed simultaneously for all N tasks, which adds a log N multiplicative factor in the sample complexity bound. In this way, we obtain a TAE algorithm with sample complexity bound in Theorem 3 where min(d, S) is replaced with log N.

---

5 Related Works
MORL. MORL receives extensive attention from RL applications [Yang et al., 2019, Natarajan and Tadepalli, 2005, Mossalam et al., 2016, Abels et al., 2018, Roijers et al., 2013]. However, little theoretical results are known, especially terms of the sample efficiency and adversarial preference settings. A large amount of MORL works focus on identifying (a cover for) the policies belonging to the Pareto fromt [Yang et al., 2019, Roijers et al., 2013, Cheung. 2019], but the correspondence between a preference and an optimal policy is ignored. Hence they cannot "accommodate picky customers" as our algorithms do. To our knowledge, this paper initiates the theoretical study of the sample efficiency for MORL in the setting of adversarial preferences.
Adversarial MDP. Similarly to the online MORL problem studied in this paper, the adversarial
MDP problem [Neu et al., 2012, Rosenberg and Mansour, 2019, Jin et al., 2019] also allows the reward function to change adversarially over time. However, we study a totally different regret (see (I)). In the adversarial MDP problem, the regret is measured against fixed policy that is best in the hindsight; but in online MORL problem, we study a regret against a sequence of optimal policies with respect to the sequence of incoming preferences, i.e., our benchmark policy may vary over time. Therefore our regret bound for online MORL problems is orthogonal to those for adversarial MDP problems [Neu et al., 2012, Rosenberg and Mansour, 2019, Jin et al., 2019].
Constrained MDP. In the problem of the constrained MDP, d constraints are enforced to restrict the policy domain, and the agent aims to find policy that belongs to the domain and maximizes the cumulative rewards [Achiam et al., 2017, Efroni et al., 2020, El Chamie al., 2018, Fisac et al., 2018, Wachi and Sui, 2020, Garcia and Fernández, 2015, Brantley et al., 2020]. Constrained MDP related to MORL as when the constraints are soft, they can be formulated as "objectives" with negative weights. However, there is fundamental difference: constrained MDP aims to optimize only one (and known) objective, where in MORL studied in this paper, we aim to be able to find near optimal policies for any mreference-weighted objective (to accommodate picky customers).
Reward-Free Exploration. The proposed preference-free exploration problem generalizes the problems of reward-free exploration [Jin et al., 2020]. Compared with existing works for RFE [Jin al., 2020, Kaufmann al., 2020, Ménard et al., 2020, Zhang al., 2020b], our method has the advantage of adapting with rewards that admit tow-dimensions structure this partly answers an open question raised by Jin et al. [2020]. We also note that Wang et al. [2020] study RFE with linear function approximation the value functions; in contrast our setting can be interpreted as RFE with linear function approximation on the reward functions, which orthogonal to their setting.
6 Conclusion
In this paper we study provably sample- eeffcceet algorithms for multi-objectio reinforcement learning in both online and preference-free exploration settings. For both settings, sample-efficient algorithms are proposed and their sample complexity analysis is provided; moreover, two information -thhoretc lower bounds are proved justif'y the near-tightness of the proposed algorithms, respectively. Our results extend existing theory for single-objective RL. and reward-free exploration, and resolve an open question raised by Jin al. [2020].
Acknowledgement
This research supported in part by NSF CAREER grant 1652257, ONR Award N00014-18-1 2364, the Lifelong Learning Machines program from DARPA/MTO, and NSF HDR TRIPODS grant 1934979.
References
Axel Abels, Diederik M Roijers, Tom Lenaerts, Ann Nowé, and Denis Steckelmacher. Dynamic weights in multi-objective deep reinforcement learning. arXiv preprint arXiv: (809.00800077 201 8.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference Machine Learning, pages 22-31. PMLR, 2017.
10

---

Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR. org, 2017.
Kianté Brantley, Miroslav Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksan- drs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. arXiv preprini vrXiv:2006.0055, 2020.
Wang Chi Cheung. Exploration-exploiatie trade-off in reinforcement learning on online markov decision processes with global concave rewards. arXiv preprint arXiv: 1905.06466 2019.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. arXiv preprint arXiv:1703.07710 2017.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explotttion in constrained mdps. arXiv preprint 2003:20000002/88 2020.
Mahmoud EI Chamie, Yue Yu, Behçet Açıkmeşe, and Masahiro Ono. Controlled markov processes with safety state constraints. IEEE Transactions on Automatic Control, 64(3):1003-1018, 2018.
Jaime F Fisac, Anayo K Akametalu, Melanie N Zeilinger, Shahab Kaynama, Jeremy Gillula, and Claire Tomlin. A general safety framework for learning- control in uncertain robotic systems. IEEE Transactions on Automatic Control, 64(7):2737-2752 2018.
Javier Gareia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learming provably efficient? In Advances Neural Information Processing Systems, pages 4863-4873, 2018
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial mdps with bandit feedback and unknown transition, 2019.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. arXiv preprint arXiv:2002.02794 2020.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free ffre exploration. arXiv preprint arXiv:2006.00 06294, 2020.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. arXiv preprint arXiv:0907.3740, 2009.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. arXiv preprint arXiv:2077.13442 2020.
Hossam Mossalam, Yannis M Assael, Diederik M Roijers, and Shimon Whiteson. Multi-objective deep reinforcement learning. arXiv preprint arXiv: 1610.02707, 2016.
Sriraam Natarajan and Prasad Tadepalli. Dynamic preferences in multi-criteria reinforcement learning. In Proceedings of the 22nd international conference on Machine learning, pages 601-608 2005.
Gergely Neu, Andras Gyorgy, and Csaba Szepesvári. The adversarial stochastic shortest path problem with unknown transition probabilities. In Artificial Intelligence and Statistics, pages 805-813, 2012.
Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. survey of multi- objective sequential decision-making Journal of Artificial Intelligence Research, 48:67-113, 2013.
Aviv Rosenberg and Yishay Mansour. Online convex optimization adversarial markov decision processes. arXiv preprint 4rXiv:1905.07773, 2019.

---

Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. In International Conference on Machine Learning, pages 9797-9806. PMLR, 2020.
Ruosong Wang. Simon Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. arXiv preprint arXiv:2006.11274 2020.
Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi-objective reinforcement learning and policy adaptation. In Advances in Neural Information Processing Systems, pages 14610-14621, 2019.
Andrea Zanette and Emma Brunskill. Tighter -eepedeed regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration reinforcement learning, 2020a.
Zihan Zhang, Simon S Du, and Xiangyang Ji. Nearly minimax optimal reward-free reinforcement learning. arXiv preprint arXiv:2010.05900,, 2020b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
12

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "ZcR6FYxIG72", "reviewer": "Reviewer_5wS9", "summary": " This paper studies the multi-objective reinforcement learning (MORL) problem where the reward function is an inner product of two d-dimensional vectors, an objective vector and a preference vector. Two algorithms have been proposed for known and not known preference vectors. Both algorithms are proved to achieve sub-linear regrets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n1. The paper is well written and organized. The insights behind the main results are well presented.\n\n2. This paper extends the reward-free approach recently introduced in [1] to multi-objective reinforcement learning MDPs. \n\nWeaknesses\n\n1. The baseline in the numerical simulations is the single-objective RL, which seems unfair because the objective functions are different. How about comparing MO-UCBVI with a more related task-agnostic algorithm [2]? Because introducing the preference is similar to changing the reward functions for different objectives.\n\n2. Most of the theoretical analysis follows from the previous work. \n\n3. The authors state that there is a connection between MORL and soft constrained MDPs by setting the weights to be negative. I do not quite agree. The results are derived based on the assumption that all the preference weights are bounded between [0,1]. It is not clear whether the results hold when the weights are negative.\n\n[1]  Jin, Chi, et al. \"Reward-free exploration for reinforcement learning.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Zhang, Xuezhou, and Adish Singla. \"Task-agnostic exploration in reinforcement learning.\" arXiv preprint arXiv:2006.09497 (2020).\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "TYHlO2gDwXu", "reviewer": "Reviewer_jxvg", "summary": "This paper investigates multi-objective reinforcement learning (MORL) in the online setting and the so-called preference-free setting, where the preference vector is given by an adversary. It proposes a model-based algorithms for each setting under tabular episodic MDPs, respectively. Both algorithms are shown to attain nearly optimal regret or sample complexity bound.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "MORL is an interesting and important problem in RL, and being able to tackle adversarial preference in MORL is valuable. \nThe algorithm design appears to follow standard value iteration algorithms in the existing literature. The theory and their proof also adapts standard techniques. The min{d, S} factor in the regret and sample complexity bounds is tight, and it sheds light on the special structure of the MORL problem.\nI appreciate the discussion on the relationship between the MORL problem and other existing RL settings (adversarial, reward-free, task-agnostic etc.). The discussion brings much insight into the context of MORL.\nOverall I find the paper to be clear and easy to follow. \n\nSuggestion\n\nOn L183, Remark 2 mentions that Theorem 1 applies to general scalarization methods beyond the linear function. It would be great if the authors could mention one or two examples of such general scalarization methods, so as to make the argument more concrete. \n\nTypo\n\n- L101: display equation below, Q*_h(x,a;;w) has an redundant semicolon\n- L244: On other the hand => On the other hand\n\n***** Post-rebuttal ****\n\nI have read other reviewers' comments and authors' responses. I would like to maintain my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "QE8AcbfxVv5", "reviewer": "Reviewer_sCTs", "summary": "This work studies the multi-objective RL (MORL) with unknown transition, where the reward function\ncan be parameterized with d-dimensional preference vectors. In the beginning of each episode, an adversary selects\nthe weight vector and reveals it to the learner, the learner then selects corresponding policy and suffers\na regret comparing with the optimal policies with respect to the given preference vector. \n\nBesides this online MORL setting, the authors further study a preference-free exploration (PFE) setting where the learner manually separates the learning and planning phases and her performance is measured by the number of samples that are required to ensure PAC-bound. Then, the authors introduce a lower bound for PFE, which shows there is only an H factor loose. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Contribution (Strengths)\n\nThe authors design an algorithm based on UCBVI (Azar et al., 2017) and Bernstein-style confidence intervals, which achieves sqrt(min(d,S) H^2SAK) regret. This regret guarantee is not comparable with the existing results for adversarial or stochastic episodic MDPs as the preference is known at the beginning of episode. First, the MORL provides the preference at the beginning of each episode. Second, the regret of MORL compares with a sequence of optimal policies with respect to the given preference, instead of a fixed stationary policy. \n\nThis setting can be regarded as an extension of the tabular episodic stochastic MDP setting of Azar et al. (2017). Therefore, some parts of the proof is standard and similar to the previous works such as Zanette and Brunskill (2019) and Azar et al. (2017). However, the usage of a specific covering argument and union bound in Lemma 1 is novel and interesting, which leads to a tighter regret bound with min(d,S). \n\nThen, the authors show a lower bound for PFE based on J-L Lemma (Lemma 13) and the existing hard instance of Jin et al. (2020)., which leads to a lower bound for the online MORL setting and shows the optimality of the proposed algorithms. Though the techniques of Lemma 12-15 are not new, this lower bound is meaningful and inspiring. \n\n2. Weaknesses\n\nThe contributions are purely theoretical, as the algorithm may be difficult to implement. Most parts of the proof are quite standard and expected. \n\n3. Writing Issues\n\nline 305, \"Due\" -> \"Due to\"\n\nline 409， “Adish Singla, et al.\" seems wrong \n\nline 471, \"an covering\" -> \"a covering\" (also 473, 819)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is pure theoretical and does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "21"}, "extra_text": {}}, {"review_id": "PUUGzjlX4I", "reviewer": "Reviewer_Lo1z", "summary": "This paper tackles the reinforcement learning problem in a multi-objective and online setting. Two different cases are considered: (i) when preferences over the multiple objectives are given at the start of each episode and (ii) when preferences are unknown and the environment needs to be explored in preparation for any arbitrary preferences. For both cases, the paper proposes optimal solutions (up to logarithmic factors, and a factor of $H$ in the second case).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses an important problem: accommodating users with varying goals and preferences, which could be relevant for many domains. Authors give the example of autonomous driving, which also explains how exactly the two settings considered in the paper might arise in a practical application. Maybe one or two additional examples from other domains could make the motivation even stronger.\n\nDemonstrating how existing solutions for the single-objective case cannot be used in the multi-objective case when the preferences are designed adversarially (since they would suffer $O(K)$ regret) is important in motivating the need for a new algorithm like MO-UCBVI. In the current version, this demonstration is deferred to Appendix A, which does not have enough details to make a convincing argument. In particular, what \"the best-in-hindsight policy\" formally means and how preferences are \"designed adversarially\" in the experiment presented in Figure 1 needs to be explained. Considering the importance of this argument, authors might consider moving some of the discussion in Appendix A to the main paper. While I believe an empirical demonstration is sufficient for this paper, a future question might be to formally prove that single-objective solutions would indeed incur $O(K)$ regret.\n\nIn Remark 2 (line 183), it is mentioned that Theorem 1 can be extended to more general cases. Does this mean that any arbitrary deterministic function $f$ such that $r=f(\\mathbf{r};w)$ can be accommodated? If not, the necessary conditions should be given formally.\n\nTheorem 3 confirming the conjecture of Jin et al. (2020) is a nice result that makes the contributions of the paper stronger.\n\nCorollary 5 gives a regret bound for the case when the MDP is non-stationary. Is this true for any arbitrary forms of non-stationarity? If so, how is PF-UCB able to achieve this in the setting of reward-free exploration? Why does Theorem 3 not give a similar bound for non-stationary MDPs as well (i.e. why is PF-UCB *not* able to achieve the same thing in the setting of preference-free exploration)?\n\nWhile I understand the duality between preference-free and reward-free exploration quite easily, how preference-free exploration can be applied to the setting of task-agnostic exploration is not immediately clear to me (especially, why the regret bound would change from $\\min\\{d,S\\}$ to $\\log N$). Both the explanation in line 302 should be improved and a formal proof of the regret bound $\\tilde{O}(\\log N \\cdot H^4S A/\\epsilon^2)$ should be given (or an explanation of how the proof of Theorem 3 can be adapted to the setting of task-agnostic exploration).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "An important limitation that is mentioned by the authors is that the upper bound in Theorem 3 is not optimal with respect to $H$. As far as I understood, despite this limitation, their analysis in Theorem 3 still improves the existing bounds for the task-agnostic exploration setting in terms of dependence on $H$.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BihGRSmy_bt", "reviewer": "Reviewer_rfjR", "summary": "The authors propose to study an multi-objective RL in an online, episodic and tabular setting. In each episode, there is an adversarial chosen weight vector $w^k$  revealed to the agent, whose aim is to achieve a sublinear-time regret compared to an oracle who uses the optimal policy every episode. The authors propose the MO-UCBVI algorithm, which incorporate the adversarial chosen weight vectors with the learning approach by the classical UCBVI. Then the authors harness their framework on a recent proposed reward-free exploration problem, and they show that their algorithm's performance is superior to the state-of-the-art.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the paper uses technical tools from UCBVI, they involve a different definition of confident radius, by incorporating the factor $\\min\\{S, d\\}$. Moreover, the technical contributions to the regret upper and lower bounds in the two problem settings are quite concrete, and provide strict improvement over existing results. \n\nTwo improvement to the paper are:\n\n1) For MORL, when we specialize the multi-obj setting to the single objective setting, do we still recover the state of the art? (My understanding is that it is not, since there seem to be an extra \\sqrt{S}, and the authors should check on that) While I do not think it is a major shortcoming to the paper even in the case when the best possible regret bound is not recovered, it is still informative for the authors to know how it is positioned.\n\n2) The inclusion of numerical experiments would be informative, in particular it will shine light (empirically) on how the hardness of the problem depends on d.\n\nMoreover, the authors should also cite the following recent work, which involves a general concave reward function for the episodic RL (NeurIPS 2020):\n\nhttps://arxiv.org/pdf/2006.05051.pdf\n\nIn addition, the long version of (Cheung 2019) shows how concave reward function can model multi-objective optimization (in a different manner from the submission)\n\nhttps://arxiv.org/pdf/1905.06466.pdf\n\nOverall, I am happy with the paper's contributions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper looks at an interesting variant of Reinforcement/Online learning, where users arrive with different preferences over several criteria. The problem is therefore linked to multi-objective optimization. Preferences could have been modelled and tackled differently than by linear aggregation, but one must start somewhere.

The content of the paper, as well as its writing, justify its acceptance.  
Decision: Accept (Poster)