Year: 2021

Abstract:
We study bandits and reinforcement learning (RL) subject to a conservative constraint where the agent is asked to perform at least as well as a given baseline policy. This setting is particular relevant in real-world domains including digital marketing, healthcare, production, finance, etc. In this paper, we present a reduction-based framework for conservative bandits and RL, in which our core technique is to calculate the necessary and sufficient budget obtained from running the baseline policy. For lower bounds, we improve the existing lower bound for conservative multi-armed bandits and obtain new lower bounds for conservative linear bandits, tabular RL and low-rank MDP, through a black-box reduction that turns a certain lower bound in the nonconservative setting into a new lower bound in the conservative setting. For upper bounds, in multi-armed bandits, linear bandits and tabular RL, our new upper bounds tighten or match existing ones with significantly simpler analyses. We also obtain a new upper bound for conservative low-rank MDP.

heading: 1 INTRODUCTION
text: This paper studies online sequential decision making problems such as bandits and reinforcement learning (RL) subject to a conservative constraint. Specifically, the agent is given a reliable baseline policy that may not be optimal but still satisfactory. In conservative bandits and RL, the agent is asked to perform nearly as well (or better) as the baseline policy at all time. This setting is a natural formalization of many real-world problems such as digital marketing, healthcare, finance, etc. For example, a company may want to explore new strategies to maximize profit while simultaneously maintaining profit above a fixed baseline at any time, in order not to be bankrupted. See (Wu et al., 2016) for more discussions on the motivation of the conservative constraint.
Analogously to the non-conservative case, conservative bandit/RL problems also require us to balance exploration and exploitation carefully. Meanwhile, to ensure the obtained policies outperform the baseline policy, we need to provide a tractable approach to keep the exploration not too aggressive. Solving these two problems simultaneously is the key challenge in conservative bandits and RL.
Existing work proposed algorithms for different settings, including bandits (Wu et al., 2016; Kazerouni et al., 2016; Garcelon et al., 2020b; Katariya et al., 2019; Zhang et al., 2019; Du et al., 2020; Wang et al., 2021) and tabular RL (Garcelon et al., 2020a). However, lower bound exists only for the multiarmed bandit (MAB) setting (Wu et al., 2016), and there is no lower bound for other widely-adopted settings, such as linear bandits, tabular Markov Decision Process (MDP) and low-rank MDP. In Section 1.3, we provide a more detailed discussion of the related work.
For each of the different settings considered in the literature (i.e., multi-armed bandits, linear bandits, tabular MDPs), existing approaches rely on ad-hoc algorithm design and analysis of the trade-off between the setting-specific regret analysis and the conservative constraint. Furthermore, it is hard to argue about the optimality of the proposed algorithms because it would require clever constructions of the hard instances to prove the non-trivial regret lower bounds under the conservative constraint.

heading: 1.1 OUR CONTRIBUTIONS
text: In this paper, we address these limitations and make significant progress in studying the general problem of online sequential decision-making with conservative constraint. We propose a unified framework that is generally applicable to online sequential decision-making problems. The common
theme underlying our framework is to calculate the necessary and sufficient budget required to enable non-conservative exploration. Such a budget is obtained by running the baseline policy (cf. Section 3). With the new framework, we obtain a novel upper bound on tabular MDPs, which improves the previous result. And we prove a new upper bound on low-rank MDPs. Also, we derive the first lower bounds for linear bandits, tabular and low-rank MDPs, which shows that our upper bound is tight.
Lower Bounds. For any specific problem (e.g., multi-armed bandits, linear bandits), our framework immediately turns a minimax lower bound of the non-conservative setting to a non-trivial lower bound for the conservative case (cf. Section 4). We list some examples to showcase the power of our framework for lower bounds. Full results are given in Table 1.
• We derive a novel lower bound for multi-armed bandits that works on a wider range of parameters than the one derived in (Wu et al., 2016). In particular, our lower bound shows a more refined dependence on the value of the baseline policy. • We derive the first regret lower bound for conservative exploration in linear bandits, tabular MDPs and low-rank MDPs. These results allow to establish or disprove the optimality of the algorithms currently available in the literature.
We emphasize our technique for deriving lower bounds is simple and generic, so we believe it can be used to obtain lower bounds for other problems as well.
Upper Bounds. Our novel view of conservative exploration can also be used to derive high probability regret upper-bounds. When the suboptimality gap 0 and the expected return µ0 of the baseline policy are known, we show that the Budget-Exploration algorithm (Alg. 1) attains minimax optimal regret in a wide variety of sequential decision-making problems, when associated to any minimax optimal non-conservative algorithm specific to the problem at hand. In the more realistic (and challenging) scenario where 0 and µ0 are unknown, we show how to simply convert an entire class of algorithms with a sublinear non-conservative regret bound into a conservative algorithms with a sublinear regret bound. We obtain the following results, full details are given in Table 1.
• In the MAB setting, we obtain a regret upper-bound that matches our refined lower-bound, thus improving on existing analysis. In the linear bandit setting, we match existing bounds that are already minimax optimal. • In the RL setting, we provide two novel results. First, we provide the first minimax optimal result for tabular MDPs, improving over (Garcelon et al., 2020a). Second, we derive the first upper bound for conservative exploration in low-rank MDPs. Our bound matches the rate of existing non-conservative algorithms though it is not minimax optimal. How to achieve minimax optimality in low rank MDPs is an open question even in non-conservative exploration.
Again, our reduction technique is simple and generic, and can be used to obtain new results in previously unstudied settings, like we did for low-rank MDPs.

heading: 1.2 MAIN DIFFICULTIES AND TECHNIQUE OVERVIEW

heading: 1.2.1 LOWER BOUNDS
text: The only lower bound for conservative exploration is by Wu et al. (2016) who followed a classical approach in the bandit literature. They constructed a class of hard environments and used an information-theoretic argument to prove the lower bound. Construction of hard environments is highly non-trivial because one needs to incorporate the hardness from the conservative constraint. It is also non-trivial to generalize Wu et al. (2016)’s lower bound to other settings such as conservative linear bandits and RL because one will need new constructions of hard environments for different settings. We note that new constructions are needed even for non-conservative settings, because simply embedding the hard instances of MAB to other settings cannot give the tightest lower bounds. See, e.g., Chapter 24 of Lattimore & Szepesvári (2020) and Domingues et al. (2021).
In this paper, We use a completely different approach. Our key insights are 1) relating the necessary budget to the regret lower bounds of non-conservative sequential decision-making problems, and 2) obtaining sharp lower bounds in the conservative settings via maximizing a quadratic function (cf. Equation (6)). Comparing with the classical approach, our approach is simpler and more general: ours does not need problem-specific constructions and can automatically transform any lower bound in a non-conservative problem to the corresponding conservative problem. See Section 4 for details.

heading: 1.2.2 UPPER BOUNDS
text: Improvement over Wu et al. (2016) when 0 is known. When 0 is known, Wu et al. (2016) proposed an algorithm (BudgetFirst) which first plays the baseline policy for enough times and then plays an non-conservative MAB algorithm. However, their regret bound is not tight because their analysis on the required budget is loose: they accumulate enough budget to play T -step exploration where T is the total number of rounds. Our main technical insight to obtain the tight regret bound is a sharp analysis on the required budget: by relating the minimax regret upper bounds of UCB algorithms, we show the required budget can be independent of T . See Section 5 and F for details. Sharp upper bounds with unknown 0. When 0 is unknown, the paper by Wu et al. (2016), its follow-up papers (Kazerouni et al., 2016; Garcelon et al., 2020b; Zhang et al., 2019; Garcelon et al., 2020a), and our paper, all adopt the same algorithmic template: 1) build an online estimate on the lower bound performance of each possible exploration policy, and 2) based on the estimated lower bounds, choose an exploration policy or play the baseline policy.
The key difference and the most non-trivial part in different papers is how to analyze T0 (the number of times of executing the baseline policy). Exiting works upper bound T0 by relating it to the decision criterion for whether to choose the baseline policy or not. Since for different problem settings, the criteria have different forms, existing papers adopt different problem-specific analyses, and in some settings, the analyses are not tight (e.g., MAB and tabular RL). Our analysis approach is different from existing ones: we bound T0 via maximizing a quadratic function that depends on the minimax regret bounds of non-conservative algorithms and the conservative constraint. See Section 5 for more details.

heading: 1.3 RELATED WORK
text: Non-conservative exploration has been widely studied in bandits, and minimax optimal algorithms have been provided for the settings considered in this paper (e.g. Lattimore & Szepesvári, 2020). The exploration problem has been widely studied also in RL but minimax optimal algorithms have not been provided for all the settings. For any finite-horizon time-inhomogeneous MDP with S states, A actions and horizon H , the minimax regret lower bound is ⌦( p H3SAT ) (Domingues et al., 2021), where T denotes the number of episodes. For any time-inhomogeneous low-rank MDP with d-dimensional linear representation, the lower-bound is ⌦( p d2H3T ) (Zhou et al., 2020, Remark
2Although the lower bound in Wu et al. (2016) seems tighter, they require a condition 0 ↵µ0+ 0 0.9. Under this condition, our lower bound is the same as theirs. Thus ours is more general. See Appendix E.
3In (Garcelon et al., 2020a), the upper bound scales with rb = mins2S,⇢0(s)>0 V ⇡0 1 (s) (with ⇢0 the distribution of the starting state), the minimum of the baseline’s value function at the first step over the potential starting states.Here, we assume there is a unique starting state hence rb = V ⇡0 .
5.8). While several minimax optimal algorithms have been provided for tabular MDPs (e.g. Azar et al., 2017; Zanette & Brunskill, 2019; Zhang et al., 2020a;b; Ménard et al., 2021), the gap between upper bound and lower bound is still open in low-rank MDPs, where LSVI-UCB (Jin et al., 2020) attains a eO( p d3H4T ), while ELEANOR (Zanette et al., 2020) improves to eO( p d2H4T ).
In conservative exploration, previous works focus on designing specific conservative algorithms for different settings. This conservative scenario was studied in multi-armed bandits (Wu et al., 2016), contextual linear bandits (Kazerouni et al., 2016; Garcelon et al., 2020b), contextual combinatorial bandits (Zhang et al., 2019) and tabular MDPs (Garcelon et al., 2020a). All these works focused on providing an upper-bound to the regret of a conservative algorithm. Other problems that have been considered in conservative exploration are combinatorial semi-bandit with exchangeable actions (Katariya et al., 2019) and contextual combinatorial cascading bandits (Wang et al., 2021). Du et al. (2020) have recently considered conservative exploration with sample-path constraint.
Our work is also related to safe bandits/RL (Amani et al., 2019; Pacchiano et al., 2021; Amani et al., 2021) and constrained RL (Altman, 1999; Efroni et al., 2020; Ding et al., 2020; 2021). The setting of safe bandits/RL is different from conservative bandits/RL. Specifically, the safety constraint requires that the expected cost at each stage is below a certain threshold. This constraint is stage-wise, and is independent of the history. On the contrary, the conservative constraint requires that the total reward is not too small. For the constrained MDP, the goal is to maximize the expected reward value subject to a constraint on the expected utility value (value function with respect to another reward function). In conservative RL, however, the agnet aims to maximize the expected reward value subject to the constaint that the (same) reward value is not significantly worse that of the baseline policy.

heading: 2 PRELIMINARIES
text: The objective of this section is to provide a unified view of the settings considered in this paper, i.e., multi-armed bandits, linear bandits, tabular Markov Decision Processes (MDPs) and low-rank MDPs. We use the RL formalism which encompasses the bandit settings.
Notations. We begin by introducing some basic notation. We use (·) to represent the set of all probability distributions on a set. For n 2 N+, we denote [n] = {1, 2, . . . , n}. We use O(·),⇥(·),⌦(·) to denote the big-O, big-Theta, big-Omega notations. We use eO(·) to hide logarithmic factors. We denote A & (.)B if there exists a positive constant c such that A ()cB. Tabular MDPs. A tabular finite-horizon time-inhomogeneous MDP can be represent as a tuple M = (S,A, H, {ph}Hh=1, s1, {rh} H h=1), where S is the state space, A is the action space, H is the length of each episode and s1 is the initial state. At each stage h, every state-action pair (s, a) is characterized by a reward distribution with mean rh(s, a) and support in [0, rmax], and a transition distribution ph(·|s, a) over next states. We denote by S = |S| and A = |A|. A (randomized) policy ⇡ 2 ⇧ is a set of functions {⇡h : S 7! (A)}h2[H]. For each stage h 2 [H] and any state-action pair (s, a) 2 S ⇥A, the value functions of a policy ⇡ are defined as:
Q⇡h(s, a) = E " HX
h0=h
rh0 |sh = s, ah = a,⇡ # , V ⇡h (s) = E " HX
h0=h
rh0 |sh = s,⇡
# .
For each policy ⇡, we define V ⇡H+1(s) = 0 and Q ⇡ H+1(s, a) = 0 for all s 2 S, a 2 A. There exists an optimal policy ⇡? such that Q?h(s, a) = Q ⇡? h (s, a) = max⇡ Q ⇡ h(s, a) satisfy the optimal Bellman equations Q?h(s, a) = rh(s, a) + Es0⇠ph(s,a)[V ?h+1(s0)] and V ?h = maxa2A{Q?h(s, a)}. Then the optimal policy is the greedy policy ⇡?h(s) = argmaxa2A{Q ? h(s, a)}.
Low-Rank MDPs. We assume that S,A are measurable spaces with possibly infinite number of elements. For algorithmic tractability, we shall restrict the attention to A being a finite set with cardinality A. When the state space is large or uncountable, value functions cannot be represented in tabular form. A standard approach is to use a parametric representation. Here, we assume that transitions and rewards are linearly representable (Jin et al., 2020). Assumption 1 (Low-rank MDP). An MDP (S,A, H, p, r) is a linear MDP with a feature map : S⇥A ! Rd, if for any h 2 [H], there exist d unknown (signed) measures µh = ⇣ µ(1)h , . . . , µ (d) h ⌘
over S and an unknown vector ✓h 2 Rd, such that for any (x, a) 2 S ⇥A, we have Ph(· | x, a) = h (x, a),µh(·)i , rh(x, a) = h (x, a),✓hi . (1)
Without loss of generality, we assume k (x, a)k  1 for all (x, a) 2 S ⇥ A, and max {kµh(S)k , k✓hk}  p d for all h 2 [H].
Under certain technical conditions (e.g., Shreve & Bertsekas, 1978), all the properties of tabular MDPs extend to low-rank MDPs. In addition, the state-action value function of any policy ⇡ is linearly representable in low-rank MDPs. Formally, for any policy ⇡ and stage h 2 [H], there exists ✓⇡h 2 Rd such that Q⇡h(s, a) = h (s, a), ✓⇡hi. Connection between RL and Bandits. To have a unified view, we can represent a multi-armed bandit as a tabular MDP with S = 1, A actions, H = 1 and self-loop transitions in s1. In multiarmed bandits, we consider only deterministic policies so that ⇧ = A, then V ⇡(s1) = r(s1,⇡(s1)) and the optimal policy is simply ⇡? = argmaxa2A r(s1, a). Similarly, a linear bandit can be modeled through low-rank MDPs with H = 1. For generality, we allow the action space to be possibly uncounted and we define the value of a deterministic policy ⇡ = a (⇧ = A) as V ⇡1 (s1) = r1(s1, a) = h (s1, a), ✓1i. The optimal policy ⇡? is thus such that ⇡? = argmaxa2Ah (s1, a), ✓1i. We refer the reader to Appendix A for details.

heading: 3 GENERAL FRAMEWORK FOR CONSERVATIVE EXPLORATION
text: With the unified view provided in the previous section, we can consider a generic sequential decisionmaking problem P over T 2 N? episodes. We consider the standard online interaction protocol where, at each episode t 2 [T ], the learning agent A selects a policy ⇡t, observes and stores a trajectory (si, ai, ri)i2[H], updates the policy and restart with the next episode. We evaluate the performance of the learner through the pseudo-regret. Let V ⇡ = V ⇡1 (s1) be the value function of a policy ⇡, then the regret is defined as:
RT (P,A) = TX
t=1
V ? V ⇡t . (2)
In conservative exploration, the learner aims to minimize the regret while guaranteeing that, at any episode t, their expected performance is (nearly) above the one of a baseline policy ⇡0. Formally, given a possibly randomized baseline policy ⇡0 2 ⇧ and a conservative level ↵ 2 [0, 1], the learner should satisfy w.h.p. that
8t  T, tX
j=1
V ⇡j (1 ↵) t V ⇡0 . (3)
We assume that the value of conservative policy V ⇡0 is known to the agent. Such assumption can be seen in previous works such as Wu et al. (2016); Kazerouni et al. (2016); Garcelon et al. (2020b;a). This assumption is reasonable in practice because usually the baseline policy has been used for a long time and is well-characterized, and its value can be estimated using historical data. Even if we do not know the value of baseline policy, we can estimate it during the algorithm (e.g., Section 3.5 in Wu et al. (2016)), and we omit here for simplicity.

heading: 3.1 BUDGET OF A CONSERVATIVE ALGORITHM
text: Given the set of policies {⇡t}t2[T ] selected by a conservative algorithm A, we can divide the episodes into the set T0 = {t  T | ⇡t = ⇡0} and its complement T c0 = {t  T | ⇡t 6= ⇡0} = [T ] \ T0. The set T c0 denotes the episodes where the algorithm played an exploratory policy, i.e., it had enough budget to satisfy condition (3) through a policy ⇡l 6= ⇡0. This sequence of non-baseline policies {⇡t}t2T c0 defines a new algorithm eA, that we refer as the non-conservative algorithm. However, the algorithm A is conservative therefore, for any > 0 and t 2 [T ], we have with probability at least 1 that Pt l=1 V ⇡l (1 ↵)tV ⇡0 . Hence, for any t 2 [T ] we have:
↵V ⇡0 |T0,t| X
l2T c0,t
(1 ↵)V ⇡0 V ⇡l , (4)
where T0,t = T0 \ [t] and T c0,t = T c0 \ [t]. Taking maximum over t in Eq. (4), we have that with high probability the conservative algorithm A is such that
↵V ⇡0 |T0| max tT
X
l2T c0,t
(1 ↵)V ⇡0 V ⇡l
| {z } =B
.
The quantity on the right of the previous equation is exactly the amount of reward that the conservative algorithm A has to collect by playing the baseline policy. Hence this quantity acts as a conservative budget B. The higher it is, the more A needs to play the baseline policy to satisfy the conservative condition. In other words, it is the least amount of reward that an algorithm needs to not violate the conservative constraint. We now extend this notion to any (non necessarily conservative) algorithm. Definition 1. For any T 2 N?, set of episodes O ⇢ [T ] and arbitrary sequence of policies {⇡t}t2O, the budget of this sequence of policies is defined as:
BT (O, {⇡t}t2O) = max t2O
X
l2O\[t]
(1 ↵)V ⇡0 V ⇡l . (5)

heading: 4 REGRET LOWER BOUND FOR CONSERVATIVE EXPLORATION
text: In this section, we leverage the framework introduced in Section 3 to build lower bounds for several problems. Our result is based on the notion of budget defined in Section 3. This notion is used to build an algorithm whose regret is a lower bound for any conservative algorithm. Theorem 1 (Conservative Exploration Regret Lower Bound). Let’s consider a decision-making problem P over T steps, a conservative level ↵ 2 [0, 1], a baseline policy ⇡0, an algorithm A and 2 (0, 1). We assume that:
• Lower-bound for non-conservative exploration. There exists a ⇠ 2 R+ and T0 2 N such that for any algorithm A0 there exists an environment (instance of P) such that with probability at least 1 , RT (P,A0) ⇠ p T for T T0. • A is conservative. The algorithm A is conservative, that is to say with probability at least 1 for any t  T , Pt l=1 V ⇡l (1 ↵)tV ⇡0 .
Then, there exists an environment (instance of problem P) and T0 2 N such that with probability at least 1 and T T0:
RT (A,P) & max n ⇠ p T , ⇠2 0
↵V ⇡0(↵V ⇡0 + 0)
o .
where 0 = V ? V ⇡0 is the sub-optimality gap of policy ⇡0.
Theorem 1 provides a general framework deriving lower-bounds for conservative exploration and highlights the impact of the baseline policy on the regret. In particular, it shows that in any sequential decision-making problem, after a sufficiently large number of episodes the conservative condition can be verified and the baseline policy has no impact anymore on the learning process. The only requirement is the knowledge of a lower-bound for the non-conservative case. Before instantiating the result in specific settings, we provide an intuition about how this result is derived and what is the role of the conservative budget B.
Proof Sketch. Let us consider a conservative algorithm A = {⇡t | t  T}, which is associated to a non-conservative algorithm eA = {⇡t | t 2 T c0 } with T c0 and T0 the set of non-conservative and conservative episodes as defined in Sec. 3. Now if E |T0| ⇠ 2
↵V ⇡0 ·(↵V ⇡0+ 0) (i.e. the algorithm
plays ⇡0 too many times), then the regret caused by ⇡0 is at least ⇠ 2 0
↵V ⇡0 ·(↵V ⇡0+ 0) . When E |T0| <
⇠2
↵V ⇡0 ·(↵V ⇡0+ 0) , consider the budget of T0 defined in Definition 1:
BT c0 (Ac) = maxt2T c0 E
tX
k=1
[(1 ↵)V ⇡0 V ⇡ t
] = max t2T c0
E[RT c 0
A (Ac)(t)] (↵V ⇡0 + 0)t, (6)
where E h R
T c0 A (Ac) (t) i is the regret incurred by the rounds in T c0 . Now if E h R T c0 A (Ac) (t) i ⇠ p t,
we have BT c0 (Ac) & ⇠2 ↵V ⇡0+ 0 by taking maximum on the right handside of (6) (viewing RHS as a quadratic function of p t). Therefore E |T0| BT c0 (Ac) ↵V ⇡0 & ⇠2 ↵V ⇡0 ·(↵V ⇡0+ 0) and the regret is also no smaller than ⇠ 2 0
↵V ⇡0 ·(↵V ⇡0+ 0) , which completes the proof.
Example of Lower Bounds. For instance, in the multi-armed bandits, by leveraging the lower-bound in (Thm. 15.2 Lattimore & Szepesvári, 2020), we can obtain the following corollary of Theorem 1.
This result is more general than the lower bound in Wu et al. (2016) where they have a restriction that 0 ↵µ0+ 0 0.9. See Appendix E for details.
Corollary 1. For any K 2 N?, ↵ 2 [0, 1], µ0 2 [0, 1], 2 (0, 1) and a conservative algorithm A then there exists µ 2 [0, 1]K such that Pt l=1 µ⇡l (1 ↵)µ0t with high probability for any t  T . Then, for T A↵µ0·(↵µ0+ 0) + p A ↵µ0+ 0 , RT (µ,A) & max np AT, A 0↵µ0·(↵µ0+ 0) o .
The generality of Theorem 1 allows us to derive lower-bounds for conservative exploration in many different problems, where the lower-bound was unknown. Table 1 reports the lower-bound obtained through Theorem 1. Please refer to Appendix B for lower-bounds for non-conservative exploration. In linear bandits, the lower bound we obtain matches the result in (Kazerouni et al., 2016; Garcelon et al., 2020b), showing the optimality of their algorithms. In tabular MDPs, our result shows that the dependence on S,A and H of CUCBVI (Garcelon et al., 2020a) is not optimal. Finally, by instantiating Theorem 1 in low-rank MDPs, we obtain the first lower bound for this setting.

heading: 5 UPPER BOUNDS
text: In this section, we show how to leverage the framework of Sec. 3 to derive an algorithm for any conservative sequential decision-making problem. We first show that when knowing 0 a simple algorithm achieves a minimax regret, as prescribed by our lower bound of Sec. 4. Then, we show how to remove this knowledge without hurting the performance by combining our framework and the idea of lower confidence bound.
5.1 THE BUDGET-EXPORATION ALGORITHM
Given a non-conservative algorithm eA, the minimum amount of rewards needed to play this nonconservative algorithm for T consecutive steps is the budget defined in Def. 1. Indeed, if we denote by {⇡̃l | l  T} the sequence of non-conservative policies executed by eA, then for any set O ⇢ [T ] the budget can be rewritten as:
BT (O, {⇡̃l | l  T}) = max t2O
X
l2O\[t]
(1 ↵)V ⇡0 V ⇡l
= max t2O
X
l2O\[t]
⇣ V ? V ⇡l ( 0 + ↵V ⇡0) O \ [t] ⌘ .
Let’s define RO\[t](eA) := P l2O\[t] V ? V ⇡l the regret over the time steps in O of the nonconservative algorithm eA. For most non-conservative algorithms with minimax regret bound, R̃T (eA,O) = O(C p |O \ [t]|) w.h.p., where C 2 R is a problem-dependent quantity as in Theorem 1. For example, in multi-armed bandit C = p A for the UCB algorithm or C = p H3SA for the UCBVIBF algorithm (Azar et al., 2017). This implies that the budget required by eA is at least C 2
0+↵V ⇡0 .
Therefore, the simple algorithm playing the baseline policy for the first T0 := O( C 2
(↵V ⇡0+ 0)↵V ⇡0 )
steps and then running the non-conservative algorithm eA, is conservative. We call such algorithm Budget-Exporation (see Alg. 1). This algorithm is conservative and minimax optimal. Indeed, we can show (see Theorem 2) that the regret upper bound of Budget-Exporation matches the lower bounds of Section 4. While knowing 0 in advance may be a restrictive assumption, it is interesting that a two-stage algorithm structure (deploying a baseline policy and then a non-conservative policy) is enough to achieve minimax optimality.
Theorem 2. Consider an algorithm eA, 2 (0, 1) and constant C 2 R such that with probability at least 1 , for any T 1, RT (eA)  eO(C p T ). Then for any T 1, the regret of BudgetExporation is bounded with probability at least 1 by eO(C p T + C
2 0 ↵V ⇡0 (↵V ⇡0+ 0) ).
Instantiating Thm. 1 with eA being the UCB algorithm (Lattimore & Szepesvári, 2020), then C = p A and the regret of Budget-Exporation is bounded w.h.p. by eO( p AT + A 0↵V ⇡0 (↵µ0+ 0) ), that matches our novel lower bound introduced in Sec. 4. Similar results can be obtained for the other settings,
Algorithm 1: Budget-Exporation Input: A non-conservative algorithm eA, conservative policy cumulative reward V ⇡0 ,
conservative level: ↵ 2 (0, 1) ,baseline action gap: 0 = V ? V ⇡0 and a constant C 1 Set B = C 2
↵V ⇡0+ 0 and T0 = B↵V ⇡0 ;
2 for t = 1, . . . , T do 3 if t < T0 then 4 Play ⇡0; 5 else 6 Play according to Ã; 7 end 8 end
see Table 1. In linear bandit we consider LinUCB as the non-conservative algorithm, leading to C = d. Similarly, in tabular MDP and low-ran MDPs, we get C = p H3SA and C = p d3H4 respectively using UCBVI-BF (Azar et al., 2017) and LSVI-UCB (Jin et al., 2020). Refer to Table 1 for a complete comparison of the results.
5.2 THE LCBCE ALGORITHM
When 0 is unknown, we aim to use the same idea as Budget-Exporation, that is to say to play a policy different than the baseline one only if the budget is positive. To achieve this, we need to build an online estimate of the conservative budget which amounts to build a lower confidence bound (w.h.p.) on the value function of any policy ⇡. Therefore, assuming a non-conservative algorithm eA builds such confidence bounds, for example by estimate the MDP as done by Garcelon et al. (2020a), we show how our budget framework helps to derive a conservative regret bound.
Let’s consider a non-conservative algorithm eA = {⇡t | t  T} able to construct a high probability lower bound on the set of selected policies. That is, for any time t  T and 2 (0, 1), eA computes a sequence of real numbers ( ⇡kt ( ))kt such that with probability at least 1 , for all k  t, ⇡kt ( )  V
⇡k . Using these lower bounds, we can define a proxy to the budget for eBT, (O, eA) for any subset O ⇢ [T ] by
eBT, ⇣ O, eA ⌘ = max
t2O
X
l2O\[t]
(1 ↵)V ⇡0 ⇡lt ( ) , (7)
with (⇡l)l2O the sequence of policies computed by the non-conservative algorithm eA. Then following from the definition of ( ⇡lt ( ))lt, we have that with probability at least 1 that eBT, ⇣ O, eA ⌘ BT (O, eA). This shows that it is possible to compute eBT, ⇣ O, eA ⌘ without knowl-
edge of the environment and the baseline parameters. The idea of our algorithm is now to play a non-conservative policy ⇡t at time t only if the difference between the proxy to the budget of eA and the reward accumulated by playing the baseline policy is negative. Formally, the condition is eBt, ⇣ St [ t, eA ⌘  ↵V ⇡0(t 1 |St|) where St is the set of time step where a non-conservative
policy was deployed in episodes before t. As a result, the minimum budget that eA requires to be conservative is maxt eBt, ⇣ St [ t, eA ⌘ = maxt2[T ] P l2St (1 ↵)V ⇡0 ⇡lt ( ) . The algorithm, called Lower Confidence Bound for Conservative Exploration (LCBCE), is detailed in Alg. 2.
Next, we show the regret bound of LCBCE.
Theorem 3. Consider an algorithm eA, 2 (0, 1) and constant C 2 R such that with probability at least 1 , for any T 1, RT (eA)  eO(C
p T ). If eA computes lower confidence bound such thatPt
k=1 V ⇡k ⇡kt  eO(C
p T ) with probability at least 1 , then for any T 1, the regret of
LCBCE is bounded with probability at least 1 by eO(C p T + C 2 0 ↵V ⇡0 (↵V ⇡0+ 0) ).
In the MAB and tabular case, LCBCE paired with UCB achieves a better regret bound compared with previous papers(Garcelon et al., 2020a; Wu et al., 2016). We also provide the first minimax
Algorithm 2: Lower Confidence Bound for Conservative Exploration Input: A non-conservative algorithm eA, 2 (0, 1), lower confidence bounds ⇡kt  V ⇡k ,
conservative policy value V ⇡0 , ↵ 2 (0, 1) 1 Set B = 0 ; // the accumulated budget 2 Set t0 = 0 ; // the number of steps in which the agent acts as eA 3 for t = 1, 2, ..., T do 4 eA gives lower bound t0+1 and a policy ⇡̃t0+1; 5 Set = Pt0 k=1 ⇡k t0+1 + ⇡̃t0+1 t0+1 ; // lower bound of expected total reward 6 if (t0 + 1)↵V ⇡0 < B then 7 Play ⇡t = ⇡0 and set B = B + ↵V ⇡0 ; 8 else 9 Play ⇡t = ⇡̃t0+1 and set t0 = t0 + 1;
10 end 11 end
optimal bound for the case of unknown baseline parameters. Finally, in low rank MDPs we recover the same rate as in the case of known baseline. See Table 1.
Proof of Theorem 3. Given an LCB algorithm Ã, suppose it maintains a lower confidence bound ⇡kt ( )  V ⇡k with probability at least 1 that satisfies Pt k=1(V ⇡k ⇡kt )  Õ(C p t). Let St be the set of time step where a non-conservative policy was deployed in episodes before t. The additional budget needed by the algorithm can be written as:
B̃T (ST ,A) = max t2[T ]
X
l2St
[(1 ↵)V ⇡0 ⇡lt ( )]
= max t2[T ]
X
l2St
⇣ V ? V ⇡l + V ⇡l ⇡lt ( ) ⌘ ( 0 + ↵V ⇡0) St
 max t2[T ]
X
l2St
⇣ V ? V ⇡l ⌘ + Õ(C p |St|) ( 0 + ↵V ⇡0) St
= max t2[T ]
RSt(Ã) + Õ(C p |St|) ( 0 + ↵V ⇡0) St .
Note that RSt(Ã)  Õ(C p |St|), so the last line can be upper bounded by maxt2[T ] ⇣ Õ(C p |St|)
( 0 + ↵V ⇡0) St
⌘
. This is a quadratic function g(x) = Õ(Cx) ( 0 + ↵V ⇡0)x2 with variable
x = p |St|, and we have g(x)  Õ( C 2
0+↵V ⇡0 ) as a result. In other words, we show that with high
probability, LCBCE only need to accumulate B̃T (ST ,A)  Õ( C 2
0+↵V ⇡0 ). Since playing the baseline
policy yields ↵V ⇡0 budget, LCBCE plays the baseline policy for at most Õ( C 2
↵V ⇡0 ( 0+↵V ⇡0 ) ) times.
Hence, the total regret incurred can be written as:
RT (A) = RST
⇣ Ã ⌘ + Õ ✓ C2 0
↵V ⇡0( 0 + ↵V ⇡0)
◆  Õ ✓ C p T + C2 0
↵V ⇡0( 0 + ↵V ⇡0)
◆ .

heading: 6 CONCLUSION
text: We present a unified framework for conservative exploration in sequential decision-making problems. This framework can be leveraged to derive both minimax lower and upper bounds. In bandits, we provide novel lower bounds that highlighted the optimality of existing algorithms. In RL, we provide the first lower bound for tabular MDPs and a matching upper bounds, and the first analysis for low rank MDPs. An interesting question is whether one can leverage this framework to derive problemdependent logarithmic bounds for conservative exploration. Another direction is to investigate model-free algorithms (e.g., Q-learning (Jin et al., 2018)) for conservative exploration.

Review summaries:
This paper proposes a reduction-based framework for a large class of reinforcement learning algorithms, including bandits, linear bandits, tabular MDP and linear MDP. The authors notably propose a generic lower bound that holds for all the studied class of algorithms. The lower bound is built on the regret decomposition between the regret of the conservative baseline during the time when the budget is not reached, and the regret of a non-conservative algorithm that learns on the baseline. While the obtained lower in the bandit setting is not as tight as the one obtained in (Wu et al, 2016), this lower bound holds for a larger class of algorithms. Then, two generic algorithms are proposed for handling conservative reinforcement learning. Budget-Exploration consists in learning the non-conservative algorithm on the conservative baseline during a fixed period of time and then to play the non-conservative algorithm. The regret upper bound of Budget-Exploration matches the lower bound, but the knowledge of the baseline gap is need. The second algorithm LCBCE does not necessitate that the baseline gap be known. The idea of the algorithm is to compute an upper bound of the budget thanks to the lower bounds of rewards obtained by the non-conservative algorithm run on the baseline. The regret upper bound of LCBCE still matches the proposed lower bound. 

This paper studies bandits and RL settings subject to a conservative constraint where the agent has to perform at least as well as a given baseline policy. It improves the existing lower bound for conservative MAB, and as the main contribution, obtains new lower bounds for conservative linear bandits, tabular RL and low-rank MDP. It also provides new upper bounds matching existing ones with different analyses.