Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
Year: 2021

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 Õ (√ min{d, S} ·H2SAK ) , 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 error. Our proposed algorithm is provably efficient with a nearly optimal trajectory complexity Õ ( min{d, S} ·HSA/ 2 ) . This result partly resolves an open problem raised by Jin et al. [2020].

text: min{d, S} ·H2SAK ) , 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 error. Our proposed algorithm is provably efficient with a nearly optimal trajectory complexity Õ ( min{d, S} ·H3SA/ 2 ) . This result partly resolves an open problem raised by Jin et al. [2020].

heading: 1 Introduction
text: In single-objective reinforcement learning (RL), a scalar reward is pre-specified and an agent learns a policy to maximize the long-term cumulative reward [Sutton and Barto, 2018]. However, in many real-world applications, we 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 a 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 et al., 2013, Yang et al., 2019, Natarajan and Tadepalli, 2005, Abels et al., 2018]
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
method, which models the multiple objectives by a 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-weighted rewards.
If the preference vector is fixed or drawn from a 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 et al., 2017]). However, more often in practice, the preference vector (under which the weighted objective needs to be optimized) is:
(i) adversarially provided, (ii) or even not available in the learning phase.
Once more taking the autonomous driving application as 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 to 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-efficient algorithms for MORL need to be developed, as well as their theoretical grounds need to be established.
In this work, we study provable sample-efficient algorithms for MORL that resolve the aforementioned issues. Specifically, we consider MORL on a 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-free 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 an 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 a 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 an 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] (where d = 1).
Contribution (i). For online MORL, we provide a provably efficient algorithm with a regret upper bound Õ (√ min{d, S} ·H2SAK ) 1, where K is the number of episodes for interacting with the en-
vironment. Furthermore, we show an information-theoretic lower bound Ω (√ min{d, S} ·H2SAK ) for online MORL. These bounds together show that, ignoring logarithmic factors, our 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 reward-free exploration problem [Jin et al., 2020] to MORL.
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 Õ ( min{d, S} ·H3SA/ 2 ) where is the tolerance of the planning
error; and we also show a sample complexity lower bound, Ω ( min{d, S} ·H2SA/ 2 ) , for any
1We use Õ(·) to hide (potential) polylogarithmic factors in O(·), i.e., Õ(n) := O(n logk n) for sufficiently large n and some absolute constant k > 0.
algorithm. These bounds suggest that our algorithm is optimal in terms of d, S, A, up to logarithmic factors. It is also worth noting that our results for preference-free exploration partly answer an open question raised by Jin et al. [2020]: reward-free RL 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 of 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.

heading: 2 Preliminaries
text: We specify a finite-horizon Markov decision process (MDP) by a tuple of (S,A, H,P, r,W). S is a finite state set where |S| = S. A is a finite action set where |A| = A. H is the length of the horizon. P(· | x, a) is a stationary, unknown transition probability to a new state for taking action a at state x. r = {r1, . . . , rH}, where rh : S ×A → [0, 1]d represents a d-dimensional vector rewards function that captures the d objectives2. W := { w ∈ [0, 1]d, ‖w‖1 = 1 } specifies the set of all possible preference vectors3, where each preference vector w ∈ W induces a scalar reward function by4 rh(·, ·) = 〈w, rh(·, ·)〉 for h = 1, . . . ,H . A policy is represented by π := {π1, . . . , πH}, where each πh(·) 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:
Qπh(x, a;w) := E [∑H j=h〈w, rj(xj , aj)〉 ∣∣xh = x, ah = a], V πh (x;w) := Qπh(x, πh(x);w),
where xj ∼ P (· | xj−1, aj−1) and aj ∼ πj(xj) for j > h. Note that compared with the typical Q-value function (or the value function) used in 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 ∈ W , the optimal policy under w is defined as π∗w := arg maxπ V π 1 (x1;w). For simplicity, we denote
Q∗h(x, a;w) := Q π∗w h (x, a;w), V ∗ h (x;w) := V π∗w h (x;w) = maxa Q∗h(x, a;w).
The following abbreviation is adopted for simplicity: PV πh |x,a,w := ∑ y∈SP(y|x, a)V πh (y;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{ Qπh(x, a;w) = 〈w, rh(x, a)〉+ PV πh+1 ∣∣ x,a,w ,
V πh (x;w) = Q π h(x, πh(x);w);
{ Q∗h(x, a;w) = 〈w, rh(x, a)〉+ PV ∗h+1 ∣∣ x,a,w ,
V ∗h (x;w) = maxaQ ∗ h(x, a;w).
With the above preparations, we are ready to discuss our algorithms and theory for online MORL (Section 3) and preference-free exploration (Section 4).

heading: 3 Online MORL
text: 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
2For the sake of presentation, we discuss bounded deterministic reward functions in this work. The techniques can be readily extended to stochastic reward settings.
3The condition that w ∈ [0, 1]d is only assumed for convenience. Our results naturally generalize to preference vectors that are entry-wisely bounded by absolute constants.
4The linear scalarization method can be generalized. See more discussions in Section 3.2, Remark 2.
an unknown environment through Protocol 1: at the beginning of the k-th episode, an adversary selects a preference vector wk and reveals it to the agent; then starting from a fixed initial state5 x1, the agent draws a trajectory from the environment by recursively taking an action and observing a 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 1 for K episodes, where the provided preferences are {wk}Kk=1 and the adopted policies are {πk}Kk=1 correspondingly, we consider the regret of the collected rewards (in expectation) competing with the theoretically maximum collected rewards (in expectation):
regret(K) := ∑K k=1V ∗ 1 (x1;w
k)− V πk1 (x1;wk). (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 1 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 k = 1, 2, . . . ,K do 3: agent receives an initial state xk1 = x1, and a preference w
k (from an adversary) 4: for step h = 1, 2, . . . ,H do 5: agent chooses an action akh, and collects reward 〈wk, rh(xkh, akh)〉 6: agent transits to a new state xkh+1 ∼ P(· | xkh, akh) 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., 2018]). In both online single-objective RL and our studied online 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 process (i.e., wk := 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 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 (1). Specifically, the regret (1) compares the perfor-
mance of the agent’s policies to a sequence of optimal policy under each given preference, which could vary over time. However, in online single-objective RL, either with known/stochastic rewards [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 a harder performance measurement is adopted. More specifically, when measured by regret
5Without loss of generality, we fix the initial state; otherwise we may as well consider an MDP with an external initial state x0 with zero reward for all actions, and a transition P0(· | x0, a) = P0(·) for all action a. This is equivalent to our setting by letting the horizon length H be H + 1.
(1), existing algorithms for single-objective RL (e.g., [Azar et al., 2017]) easily suffer a ∝ Θ(K) regret when the sequence of preferences is adversarially designed; in contrast, we will show an MORL algorithm that experiences at most ∝ Õ( √ K) regret under any sequence of preferences. A numerical simulation of this issue is presented in Figure 1.

heading: 3.1 A Sample-Efficient Online Algorithm
text: In this part we introduce an algorithm for online MORL, called multi-objective upper confidence bound value iteration (MO-UCBVI). A simplified verison of MO-UCBVI is presented as Algorithm 1, and a 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 1 MO-UCBVI 1: initialize historyH0 = ∅ 2: for episode k = 1, 2, . . . ,K do 3: Nk(x, a), P̂k(y | x, a)← Empi-Prob(Hk−1) 4: compute bonus bk(x, a) := c · √ min{d,S}H2ι Nk(x,a) , where ι = log(HSAK/δ) and c is a constant
5: receive a preference wk
6: {Qkh(x, a;wk)}Hh=1 ← UCB-Q-Value(P̂k, wk, bk) 7: receive initial state xk1 = x1 8: for step h = 1, 2, . . . ,H do 9: take action akh = arg maxaQ k h(x k h, a;w
k), and obtain a new state xkh+1 10: end for 11: update historyHk = Hk−1 ∪ {xkh, akh}Hh=1 12: end for
13: Function Empi-Prob 14: Require: historyHk−1 15: for (x, a, y) ∈ S ×A× S do 16: Nk(x, a, y) := #{(x, a, y) ∈ Hk−1}, and Nk(x, a) := ∑ y N k(x, a, y) 17: if Nk(x, a) > 0 then 18: P̂k(y | x, a) = Nk(x, a, y)/Nk(x, a) 19: else 20: P̂k(y | x, a) = 1/S 21: end if 22: end for 23: return Nk(x, a) and P̂k(y | x, a)
24: Function UCB-Q-Value 25: Require: empirical transition P̂k, preference wk, and bonus bk(x, a) 26: set V kH+1(x;w
k) = 0 27: for step h = H,H − 1, . . . , 1 do 28: for (x, a) ∈ S ×A do 29: Qkh(x, a;w k) = min { H, 〈wk, rh(x, a)〉+ bk(x, a) + P̂khV kh+1 ∣∣ x,a,wk
} 30: V kh (x;w k) = maxa∈AQ k h(x, a;w
k) 31: end for 32: end for 33: return { Qkh(x, a;w k) }H h=1
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 6 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
13), which might not be accurate if a state-action pair has not yet been visited for sufficient times. To mitigate this inaccuracy, UCB-Q-Value utilizes an extra exploration bonus (lines 4 and 29) so that: (i) UCB-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-UCBVI only suffers a sublinear regret, even when the preferences are adversarially presented. The above intuition is formalized in the next part.

heading: 3.2 Theoretical Analysis
text: The next two theorems justify regret upper bounds for MO-UCBVI and a regret lower bound for online MORL problems, respectively. Theorem 1 (Regret bounds for MO-UCBVI). Suppose K is sufficiently large. Then for any sequence of the incoming preferences {wk}Kk=1, with probability at least 1− δ: • the regret (1) of MO-UCBVI (see Algorithm 1) satisfies
regret(K) ≤ O (√ min{d, S} ·H3SAK log(HSAK/δ) ) ;
• and the regret (1) of a Bernstein-variant MO-UCBVI (see Algorithm 4 in Appendix B) satisfies regret(K) ≤ O (√ min{d, S} ·H2SAK log2(HSAK/δ) ) .
Theorem 2 (A regret lower bound for MORL). There exist some absolute constants c,K0 > 0, such that for any K > K0, any MORL algorithm that runs K episodes, there is a set of MOMDPs and a sequence of (necessarily adversarially chosen) preferences vectors such that
E[regret(K)] ≥ c · √
min {d, S} ·H2SAK, where the expectation is taken with respect to the randomness of choosing MOMDPs and the randomness of the algorithm for collecting dataset. Remark 1. When d = 1, MORL recovers the single-objective RL setting, and Theorem 1 recovers existing nearly minimax regret bounds for single-objective RL [Azar et al., 2017, Zanette and Brunskill, 2019]. Moreover, the lower bound in Theorem 2 implies that our upper bound in Theorem 1 is tight ignoring logarithm terms. Interestingly, the lower bound suggests MORL with d > 2 is truly harder than single objective RL (corresponding to d = 1) as the sequence of preferences can be adversarially chosen. Remark 2. Theorem 1 (as well as our other theorems) applies to general scalarization methods besides the linear one as adopted by Algorithm 1 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 rh(·, ·) = f(rh(·, ·);w) that are (1) deterministic, (2) Lipschitz continuous for w, and (3) bounded between [0, 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 are not dedicated to linear scalarization function and can be easily extended to more general cases.
The proof of Theorem 1 leverages standard analysis procedures for single-objective RL [Azar et al., 2017, Zanette and Brunskill, 2019], and a 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. To handle this issue, we use reduction techniques and utilize a lower bound that we will show shortly for preference-free exploration problems. We refer the readers to Theorem 4 and Appendix E for more details.

heading: 4 Preference-Free Exploration
text: Problem Setups. Preference-free exploration (PFE) captures the second difficulty in MORL: the preference vector might not be observable when the agent explores the environment. Specifically, PFE
consists of an exploration phase and a 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 is prohibited to obtain new data, and is required to compute near-optimal policy for any preference-weighted 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 ( , δ)-PAC (Probably Approximately Correct), if
P { ∀w ∈ W, V ∗1 (x1;w)− V πw 1 (x1;w) ≤ } ≥ 1− δ,
where πw 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 ( , δ)-PAC in the planning phase.
Connections to Reward-Free Exploration. PFE problem is a natural extension to the recent proposed reward-free exploration (RFE) problem [Jin et al., 2020, Kaufmann et al., 2020, Wang et al., 2020, Ménard et al., 2020, Zhang et al., 2020b]. Both problems consist of an exploration phase and a 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 be represented as the inner product of a d-dimensional preference vectors and the d-dimensional vector rewards functions (i.e., the d objectives in MORL). A PFE problem reduces to a RFE problem if d = SA such that every reward function can be represented as a preference-weighted reward function. However, if d SA, it is conjectured by Jin et al. [2020] that PFE can be solved with a much smaller sample complexity than RFE. Indeed, in the following part we show an algorithm that improves a ∝ Õ(S2) dependence for RFE to ∝ Õ(min{d, S} · S) dependence for PFE, in terms of sample complexity.

heading: 4.1 A Sample-Efficient Exploration Algorithm
text: 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 historyH0 = ∅ 2: for episode k = 1, 2, . . . ,K do 3: Nk(x, a), P̂k(y | x, a)← Empi-Prob(Hk−1) 4: compute bonus ck(x, a) := H
2S 2Nk(x,a) + 2bk(x, a) for bk(x, a) defined in Algorithms 1 or 3
5: {Qkh(x, a)}Hh=1 ← UCB-Q-Value(P̂k, w = 0, ck) 6: receive initial state xk1 = x1 7: for step h = 1, 2, . . . ,H do 8: take action akh = arg maxaQ k h(x k h, a), and obtain a new state x k h+1
9: end for 10: update historyHk = Hk−1 ∪ {xkh, akh}Hh=1 11: end for
Algorithm 2 presents our PFE algorithm in the exploration phase. Indeed, Algorithm 2 is a 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 a zero preference vector, the UCB-Q-Value in Algorithm 2 will identify a trajectory along which the cumulative bonus (instead of the cumulative rewards) is 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 a state-action pair. Hence the greedy policy with respect to the zero-preference UCB-Q-Value tends to visit the state-actions pairs that are associated with large bonus, i.e., those that have been visited
Algorithm 3 PF-UCB (Planning) Require: historyHK , preference vector w
1: for k = 1, 2, . . . ,K do 2: Nk(x, a), P̂k(y|x, a)← Empi-Prob(Hk−1) 3: compute bonus bk(x, a) := c · √ min{d,S}H2ι Nk(x,a) where ι = log(HSAK/δ) and c is a constant
4: {Qkh(·, ·;w)}Hh=1 ← UCB-Q-Value(P̂k, w, bk) 5: infer greedy policy πkh(x) = arg maxaQ k h(x, a;w) 6: end for 7: return π drawn uniformly from {πk}Kk=1
for less times. In sum, Algorithm 2 explores the unknown environment “uniformly”, without the guidance of preference vectors.
Then Algorithm 3 shows our PFE algorithm in the planning phase. Given any preference vector, Algorithm 3 computes a 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 as the one in Algorithm 1, and recall that the bonus in Algorithm 2 is an enlarged one. The relatively large bonus in the exploration phase guarantees that the regret in the planning phase never exceeds that in the exploration phase. On the other hand, based on Theorem 1 for MO-UCBVI (Algorithm 1), we have already known that the exploration algorithm (Algorithm 2), a modified Algorithm 1, suffers at most Õ( √ K) regret, hence the planning algorithm (Algorithm 3) experiences at most Õ(1/ √ K) error. The next part rigorously justifies these discussions.

heading: 4.2 Theoretic Analysis
text: We first provide Theorem 3 to justify the trajectory complexity of Algorithms 2 and 3 in the PFE setting; then we present Theorem 4 that gives an information-theoretic lower bound on the trajectory complexity for any PFE algorithm. Theorem 3 (A trajectory complexity of PF-UCB). Suppose > 0 is sufficiently small. Then for PF-UCB (Algorithm 2) run for
K = O ( min{d, S} ·H3SAι/ 2 ) , where ι := log(HSA/(δ )),
episodes, PF-UCB (Algorithm 3) is ( , δ)-PAC.
Theorem 4 (A lower bound for PFE). There exist absolute constants c, 0 > 0, such that for any 0 < < 0, there exists a set of MOMDPs such that any PFE algorithm that is ( , 0.1)-PAC on them, it needs to collect at least
K ≥ Ω ( min {d, S} ·H2SA/ 2 ) trajectories in expectation (with respect to the randomness of choosing MOMDPs and the exploration algorithm).
Remark 3. According to Theorems 3 and 4, 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 is because the current Algorithm 2 utilizes a preference-independent, 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 total regret incurred by Algorithm 2 is Õ (√ min {d, S}H3SAK ) according to Theorem 1. (2) Then 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 is at most Õ (√ min {d, S}H3SA/K ) as claimed. A complete proof is 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 to 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 a loose, ∝ Õ(S2) complexity in the obtained bound. Different from their approach, we 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 ∝ Õ(min{d, S} · S) dependence in the final bound. We believe this observation has broader application in the analysis of similar RL problems.
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 ≥ Ω ( H2S2A/ 2 ) . 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 Johnson–Lindenstrauss Lemma [Johnson and Lindenstrauss, 1984] to refine the hard instance in [Jin et 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–Lindenstrauss Lemma is of broader interests. A rigorous proof is deferred to Appendix D.
Application in Reward-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-stationary MDPs6:
Corollary 5. Suppose > 0 is sufficiently small. Consider the reward-free exploration problems on a stationary MDP. Suppose PF-UCB (Algorithm 2) is run for
K = O ( H3S2Aι/ 2 ) , where ι := log(HSA/(δ )),
episodes, then PF-UCB (Algorithm 3) is ( , δ)-PAC. Moreover, if the MDP is non-stationary, the above bound will be revised to K = O ( H4S2Aι/ 2 ) .
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 anH 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 a d-dimensional feature for d < S, PF-UCB only needs ∝ Õ(min{d, S} · S) samples, but the above methods must explore the whole environment with a high precision which consumes ∝ Õ(S2) 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 a 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 a union bound, and with a modification of min{d, S} ↔ log(N) in the obtained trajectory complexity bounds. For TAE on a non-stationary MDP, Zhang et al. [2020a] show an algorithm which takes Õ ( log(N) ·H5SA/ 2 ) episodes for TAE7. In comparison, when applied to TAE on a non-stationary MDP, Theorem 3 implies PF-UCB only takes Õ ( log(N) ·H4SA/ 2 ) episodes8, which improves [Zhang et al., 2020a].
6Our 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, i.e., replacing P by {Ph}Hh=1.
7This bound is copied from [Zhang et al., 2020a], which is erroneously stated due to a technical issue in the proof of Lemma 2 in their original paper. The issue can be fixed by a covering argument and union bound on the value functions, but then the obtained bound should be Õ ( log(N)H5S2A/ 2 ) . See Appendix F for details.
8The conversion holds as follows. First set d = 1 in our algorithm to yield an algorithm for TAE with a single agnostic task, where we have min{d, S} = 1. Then one can extend this algorithm to TAE with N agnostic tasks using a union bound to have the algorithm succeed simultaneously for all N tasks, which adds a logN multiplicative factor in the sample complexity bound. In this way, we obtain a TAE algorithm with a sample complexity bound in Theorem 3 where min{d, S} is replaced with logN .

heading: 5 Related Works
text: 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 in 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 front [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 (1)). In the adversarial MDP problem, the regret is measured against a 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 a policy that belongs to the domain and maximizes the cumulative rewards [Achiam et al., 2017, Efroni et al., 2020, El Chamie et al., 2018, Fisac et al., 2018, Wachi and Sui, 2020, Garcıa and Fernández, 2015, Brantley et al., 2020]. Constrained MDP is related to MORL as when the constraints are soft, they can be formulated as “objectives” with negative weights. However, there is a 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 preference-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 et al., 2020, Kaufmann et al., 2020, Ménard et al., 2020, Zhang et al., 2020b], our method has the advantage of adapting with rewards that admit low-dimensional 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 on the value functions; in contrast our setting can be interpreted as RFE with linear function approximation on the reward functions, which is orthogonal to their setting.

heading: 6 Conclusion
text: In this paper we study provably sample-efficient algorithms for multi-objective 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-theoretic lower bounds are proved to justify 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 et al. [2020].

heading: Acknowledgement
text: This research was supported in part by NSF CAREER grant 1652257, ONR Award N00014-18-12364, the Lifelong Learning Machines program from DARPA/MTO, and NSF HDR TRIPODS grant 1934979.

Review summaries:
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.  

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.

 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.

This work studies the multi-objective RL (MORL) with unknown transition, where the reward function can be parameterized with d-dimensional preference vectors. In the beginning of each episode, an adversary selects the weight vector and reveals it to the learner, the learner then selects corresponding policy and suffers a regret comparing with the optimal policies with respect to the given preference vector.   Besides 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. 

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).