A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning
Authors: Yunchang Yang
Tianhao Wu
Han Zhong
Evrard Garcelon
Matteo Pirotta
Alessandro Lazaric
Liwei Wang
Simon Shaolei Du
Venue: ICLR 2022 Poster (2022)
Keywords: bandits
lower bound
reinforcement learning theory

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.

Published as a conference paper at ICLR 2022
A REDUCTION-BASED FRAMEWORK FOR CONSERVA- TIVE BANDITS AND REINFORCEMENT LEARNING
Yunchang Yang"
Tianhao Wu"
Center for Data Science, Peking University yangyclpku. edw.eeeppkuuuuu...... cn
University of California, Berkeley
thw@berkeley.ck
Han Zhong"
Evrard Garcelon, Matteo Pirotta, Alessandro Lazaric Facebook Al Research (evrard, pirotta, lazaric @fb. cmm
Center for Data Sience, Peking University san pku edu.co cn
com
Liwei Wang
Simon S. Du University of Washington saduêcs Cestuuss.washineee.. wwwwington. edu
Key Laboratory of Machine Perception, MOE, School of Artificial Intelligence, Peking University International Center for Machine Learning Research, Peking University wanglw@e cis. pku. edu.cm
ABSTRACT
We study bandits and reinforcement learning (RL) subject to a conservative con- straint where the agent is asked to perform at least as well as a given baseline policy. This setting particular relevant in real-workh domains including digital marketing. healthcare, production, finance, etc. In this paper, we present a reduction-based framework for conservative bandits and RL, which our core technique is calculate the necessary and sufficient budget obtained from running the baseline policy. For lower bounds, 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 black-box reduction that turns certain lower bound in the nonconservative setting into a new lower bound the conserva- tive 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 new upper bound for conservative low-rank MDP.
INTRODUCTION
This paper studies online sequential decision making problems such as bandits and reinforcement learning (RL.) subject to conservative constraint. Specifically, the agent given reliable baseline policy that may not be optimal but still satisfactory. conservative bandits and RI., the agent is asked to perform nearly well (or better) the baseline policy at all time. This setting is natural formalization of many real-world problems such as digital marketing, healthcare, finance, etc. For strategies maximize profit while simultaneously
example, company may want explore 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 tractable approach keep the exploration not too aggressive. Solving these two problems simultancously 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 al., 2021) and tabular RL (Garcelon et al., 2020a). However, lower bound exists only for the multi-
"cqual contribution

---

Published as a conference paper at ICLR 2022
armed 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 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-specifes regret analysis and the conservative constraint. Furthermore, it 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.
1.1 OUR CONTRIBUTIONS
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 online sequential decision-makinn problems. The common theme underlying our framework is to calculate the necessary and sufficient budget required to enable non-conservative exploration. Such 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 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 (c.g., multi-armed bandits, linear bandits), our framework immediately turns a minimax lower bound of the con-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- aamed bandits that works on 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 well.
Upper Bounds. Our novel view of conservative exploration can also be used to derive high probability regret upper-bounds. When the suboptimality gap Ao and the expected return 140 of the baseline policy are known, we show that the regret in a wide variety of sequential optimal non-conservative algorithm specific the problem hand. In the more realistic (and challenging) scenario where Ao and μe 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.
algorithm (Alg. 1) attains minimax optimal problems, when associated to any minimax
In the MAB setting, we obtain regret upper- bound that matches 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.
1.2
MAIN DIFFICULTIES AND TECHNIQUE OVERVIEW
1.2.1
LOWER BOUNDS
The only lower bound for conservative exploration is by Wu et al. (2016) who followed approach in the bandit literature. They constructed class of hard environments and used an
a classical
2

---

Published as a conference paper at ICLR 2022
Setting
Lower Bound
Upper Bound
Multi-armed bandits
Ω (VAT +
AAg apolapo+AA)
Ô VAT
AAp topoo
( + app (Wu et al., 2016)
VAT aRO
(Wi et al., 2016) A (dvT + app 1o Agg
Linear
l adVT
d²
bandits
(oa +o0)
This work and (Kazerouni al., 2016; Garcelon et al., 20206)
Tabular
Ô VH'SAT
SAH An
augig (asig F δ (VHSSAT (Garcelon et al. 2020a)
MDPs
(VHSSAT
SAH An apo + Ao)
AA An
GMO + Ag)
Low Rank
A expotowo + Bo)
ō (V
d A ogg oop + An)
MDPs
Comparison of bounds for conservative decision-makinn making. Our contributions are reported in grey cells. We denote by T the number of rounds the agent plays (episodes in RL), the conservative level. Hi the expected return of the baseline policy'. Su the suboptimality gap of the baseline policy, A the number of actions (or arms), S the number of states and d the feature dimension. The upper bounds hold both in the case Dg and Mo are unknown since the lack of knowledge changes the regret only by a constant multiplicative factor (cf. Section 5).
Table 1:
information--teorrtie argument to prove the lower bound. Construction of hard environments is highly non-trivial because one needs 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 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, c.g., Chapter 24 of Lattimore & Szepesvári (2020) and Domingues et al. (2021).
will need new constructions of hard environments for different
In this paper, We use completely different approach. Our key insights are 1) relating the necessary budget to the regret lower bounds of non-conservative sequential pocision-making problems, and 2) obtaining sharp lower bounds in the conservative settings via maximizing a quadratic function (ef. Equation (6)). Comparing with the classical approach, our approach is simpler and more general: ours does not need groblem-specife constructions and can automatically transform any lower bound in a non-conservative problem to the corresponding conservative problem. See Section for details.
1.2.2 UPPER BOUNDS
Improvement over Wu et al. (2016) when Ag is known. When Ag is known, Wu et al. (2016) proposed 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 T-step exploration where T is the total number of rounds. Our main technical insight to obtain the tight regret bound is 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 Ag. When Ag is unknown, the paper by Wu et al. (2016), its follow-up papers (Kazerouni et al., 2016; Garcelon et al., 2020b; Zhang 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.
2 Although the lower hound in Wu et al. (2016) seems tighter, they require a condition ape- 2 0.9. Under
Agg
this condition, our lower bound the same as theirs. Thus ours more general. See Appendix E.
II (Garcelon et al., 2020a), the upper bound scales with rа min,gs po (=)20 ViTo(s) (with po 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 unique starting state hence r3- V
3

---

Published as a conference paper at ICLR 2022
The key difference and the most non-trivial part in different papers is how analyze To (the number of times of executing the baseline policy). Existing works upper bound To 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 problen-specific analyses, and in some settings, the analyses are not tight (e.g.. MAB and tabular RI.. Our analysis approach different from existing ones: we bound To via maximizing quadratic function that depends on the minimax regret bounds of non-conservative algorithms and the conservative constraint. See Section 5 for more details.
1.3 RELATED WORK
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
time-inhomogennouss MDP with S states, A actions and horizon H, the minimax regret lower bound is ( (Domingues et al., 2021), where T denotes the number of episodes. For any inmomonooooeessuss low-rank MDP with d-dimensional linear representation, the lower-bound is Q ( (T)) (Zhou et al., 2020, Remark 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 Ō(v D(vdHHTT)) H*T). while ELEANOR (Zanette al., 2020) improves (V
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 with exchangeable ac-
been considered in conservative exploration are combinatorial tions (Katariya al., 2019) and contextual combinatorial cascading bandits (Wang 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 al., 2021; Amani et al., 2021) and constrained RL (Altman, 1999; Efroni et al., 2020; Ding et al., 2020; 2021: Chen et al., 2020). 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 constraint on the expected utility value (value function with respect to another reward function). 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.
2 PRELIMINARIES
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 A(-) to represent the of all prob- ability distributions on a set. For n E N,. we denote [rx] = {1,2, 1,,,,...,u n... We use 0(-), O(),, to denote the big-O, big-Theta, big-Omega notations. We use ((-) to hide logarithmic factors. We denote A Σ (S)B if there exists a positive constant such that 2 (s)eB.
Tabular MDPs. A tabular finite-horizon time- time-inhomogeneouss MDP can be represent as a tuple M (S, H. {p H $1, { where S is the state space, .A is the action space, H is the length of each episode and 81 is the initial state. At each stage h, every state-action pair (s, a) is characterized by reward distribution with mean r. (s, a) and support in [0, rmaa]] and transition distribution Pa (-|s, a) over next states. We denote by S = [S] and A = |A]. A (randomized) policy IT is set of functions {TH : S + ((A)) For each stage h [H] and any state-action
4

---

Published as a conference paper at ICLR 2022
pair (s,a) E A, the value functions of a policy are defined as:
H
H
Qh
Σ LA=h
Th 18h = s, an = a, π
(9)
Σ
The The = 5, π
For each policy n, we define V V (s) 0 and Q7+ (s, = for all 8 E S,a a E A. There exists an optimal policy x" such that (5, 07 (s,a) max, (7, a) satisfy the optimal Bellman tp (5') and Vi max,ca(Q)(s.a)) Then the optimal policy is the greedy policy 7 arg A ()).
equations (%,s,, a) - r (s,
Low-Rank MDPs. We assume that S,A A are measurable spaces with possibly infinite number of elements. For algorithmic tractability, we shall restrict the attention to A being 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 (Low-rank MDP). An MDP (S,A, p,r) is a linear MDP with feature map Φ: : Sx A RR4, ifror any h [H], there exist unknown (signed) measures 14 (1h 1. 1h
(1)
(d)
over S and an unknown vector 0% Rd. such that for any (x, a) ES A, we have Pa( (x,a) - (1(x,, a), 1n))),, (2( = (0(2, a), On)
Without loss of generality, we assume [1 a)ll I 1 for all (x, a) max
8x A. and
S for all 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 i and stage h [H], there exists 0g E IRd such that Q7 (s, a) (0(s, a),
Connection between RL and Bandits. To have unified view, we can represent multi-armed bandit as a tabular MDP with S = 1, A actions, H = 1 and self-loop transitions in $1. In multi- armed bandits, consider only deterministic policies that II A. then (=1(s) = r(s1, 7 (($1)) and the optimal policy is simply x' = arg max.c.A r(a1, 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 (II = A) as (8)) = (81,a) a) = (Ø(s1; a), 01). The optimal policy x² is thus such that x' arg m a), We refer the reader to Appendix A for details.
3 GENERAL FRAMEWORK FOR CONSERVATIVE EXPLORATION
With the unified view provided in the previous section, we can consider a generic sequential decision- making problem & over T' N episodes. We consider the standard online interaction protocol where, at each episode & E [T]. the learning agent 인 selects a policy Te, observes and stores trajectory (s;, a; [H)) updates the policy and restart with the next episode. We evaluate the performance of the learner through the pseudo- Let V VIT(s) be the value function of policy π, then the regret is defined as:
T V V
RT (T 21)
In conservative exploration, the learner aims to minimize the regret while guaranteeing that, at any episode f, their expected performance is (nearly) above the one of a baseline policy no. Formally, given a possibly randomized baseline policy %o E II and conservative level E [0, 1J. the learner should satisfy w.h.p. that
Vt ST
v a2) t
(3)
5

---

Published as a conference paper at ICLR 2022
We assume that the value of conservative policy V is known to the agent. Such assumption can be seen in previous works such as Wu et al. (2016); Kazerouni al. (2016); Garcelon al. (2020b;a). This assumption is reasonable in practice because usually the baseline policy has been used for long time and is well-characterized, and its value can 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 al. (2016)), and we omit here for simplicity.
3.1 BUDGET OF A CONSERVATIVE ALGORITHM
Given the set of policies hee selected by a conservative algorithm M, we can divide the episodes into the set To = {t < T'
To and its complement T {t < T Te # To} = [I'] To. The set To denotes the episodes where the algorithm played an exploratory policy, i.c., had enough budget to satisfy condition (3) through a policy #i * zo- This sequence of non-baseline policies t heeT defines a new algorithm 21 that we refer as the non-conservative algorithm. However, the algorithm 21 is conservative therefore, for any 5 > 0 and E [T], we have with probability at least V (1 a) Hence, for any & E [7'] we have:
1 6 th
aV (Toel 2
Σ (1-a)V - IETO,
(4)
where To.: = To [t] and To. = Ty [t]. Taking maximum over t in Eq. (4), we have that with high probability the conservative algorithm 21 is such that
a N0 To
max
Σ (1-a)Voo V LET
The quantity on the right of the previous equation is exactly the amount of reward that the conservative algorithm 2 has to collect by playing the baseline policy. Hence this quantity acts as conservative budget B. The higher it is, the more 2 needs 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
extend this notion any (non necessarily conservative) algorithm.
Definition 1. For any T E N* set of episodes O C. [T] and arbitrary sequence of policies { heo. the budget of this sequence of policies is defined as:
(r (mehEo) = max (1-a) -V LEO
(5)
(EON
4 REGRET LOWER BOUND FOR CONSERVATIVE EXPLORATION
In this section, we leverage the framework introduced in Section 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 decision-making problem & over T steps, a conservative level a E [0, 11, a baseline policy ny, an algorithm and 5 E (0, 1). We assume that:
Lower-bound for non-conservative exploration. There exists a E E R_ and To E N such that for any algorithm N' there exists an environment (instance of () such that with probability at least
1 5, (T, X 2 TVT for T 2 To-
conservative, that say with probability at least 1 for any & T. Ei= V 2 =
21 is conservative. The algorithm
Then, there exists an environment (instance of problem B) and To E M such that with probability at least 1 and T > To:
RT F) Z max {EVT, aVao (o Ao)
where Ao V V is the sub-optimality gap of policy no-

---

Published as a conference paper at ICLR 2022
Theorem 1 provides 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 pocision-making problem, after sufficiently large number of episodes the conservative condition can 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 the role of the conservative budget B.
Proof Sketch. Let us consider a conservative algorithm a {Te f S T), which associated to a non-conservative algorithm X = { t To. with To and To the set of non-conservative and E
conservative episodes defined in Sec. 3. Now if E (Tal aV"o-(aVVo+Sao (i.e. the algorithm
plays mo too many times), then the regret caused by mo is at least (V
E
When E (ol <
(avo- consider the budget of To defined in Definition 1:
(Ac)
max E a)V V
max T5 (A.) (aV + Au)t, (6)
TETO
TET
k=
where E R
(Ac) (t) is the regret incurred by the rounds in TB Now if
R
(A.) 2 EvF,
we have Byg (Aa) Z av by taking maximum on the right handside of (6) (viewing RHS as a quadratic function of Vt). Therefore E (To)
Byg aV=o 2 ao and the regret also no
Ao smaller than aV RaV (aV +An) which completes the proof.
Example of Lower Bounds. For instance, in the multi-armed bandits. by leveraging the bouer-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 restriction that Ao 2 0.9. See Appendix E for details.
aoo+Ao
Corollary 1. For any K E N", E [0, No [0. 1]. 8 E (0, 1) and a conservative algorithm 21
then there exists μ E [0, such that Ei=1 Maz 2 (1 a) with high probability for any t < T.
Then, for T 2 aapo
VA ( 21 Z max VAT
AAg
The generality of Theorem allows us to derive lower-bounds for conservative exploration in many different problems, where the lower-bound was unknown. Table reports the lower-bound obtained through Theorem 1. Please refer Appendix B for lower-bounds for con-conservvttve exploration. In linear bandits, the lower bound we obtain matches the result in (Kazerouni et al., 2016; Garcelon 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 in low-rank MDPs, we obtain the first lower bound for this setting.
UPPER BOUNDS
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 Ao simple algorithm achieves a minimax regret, as preseribed 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-EXPORATE ALGORIIHM
Given a con-conservvtive algorithm 인1 the minimum amount of rewards needed play this non- conservative algorithm for T consecutive steps the budget defined in Def. 1. Indeed, we denote by ( I < T} the sequence of non-conservative policies executed by 2., then for any set O C [T] the budget can be rewritten as:
(r, ( 1 T})
max Σ LEO LEON
(1-a)Va a)v V
7

---

Published as a conference paper at ICLR 2022
Algorithm 1: Budget- Exportion
Input: A non-conservative algorithm 21, conservative policy cumulative reward V*a, conservative level: a E (0, baseline action gap: Ao = V - V and a constant C
Set B aV*o+Ao and To aV
C²
for t 1..... do
if < To then
Play To:
else
Play according to 2
end
end
(V* V -Ao + a a n [0]).
max IEO
LEON|I
Let's define Ron (ii) = EieonIa V V the regret over the time steps in O of the non- conservative algorithm X For most non-conservative algorithms with minimax regret bound, (2,, = O(Cyvlon [e]l) w.h.p., where C' E E is a problem-dependent quantity as in Theorem 1. For example, in multi-armed bandit C V for the UCB algorithm C VH3SA for the UCBVI- BF algorithm (Azar et al., 2017). This implies that the budget required by 21 is at least AotaV=
Therefore, the simple algorithm playing the baseline policy for the first To == O TaV
steps and then running the non-conservative algorithm 21 is conservative. We call such algorithm Budget-Exporation (see Alg. 1). This algorithm is conservative and minimax optimal. Indeed, can show (see Theorem 2) that the regret upper bound of bounds of Section 4. While knowing Ao in advance may be 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.
matches the lower
Theorem 2. Consider an algorithm X,, (0,1) and constant C E R. such that with probability at least 1 6, for any T 2 (2() < ÖCCVT). Then for any T 2 1, the regret of Budget-
C² Exporation is bounded with probability at least 5 by Õ(CVT (o
Instantiating Thm. 1 with 인 being the UCB algorithm (Lattimore & Szepesvári, 2020), then C = VA A&g and the regret of Exxogratonoo is bounded w.h.p. by Ö(VAT + (a ). that matches our novel lower bound introduced in Sec. 4. Similar results can be obtained for the other settings, 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, get C VH3SA and C Vd respectively using UCBVI-BF (Azar et al., 2017) and LSVI-UCB (Jin et al., 2020). Refer to Table for a complete comparison of the results.
5.2 THE LCBCE ALGORITHM
When Ag is unknown, we aim to use the same idea as Eudoeet-Epooatiin, that is to say to play a policy differrntt than the baseline one only 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 non-conservative algorithm 인 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 conservative regret bound.
Let's consider non-conservative algorithm र { l S T} able to construct a high probability lower bound on the set of selected policies. That for any time t < T' and E (0, 1). 인1 computes a sequence of real numbers (X5* (o)) such that with probability at least 1 - 8, for all k < t, X. (8) < V Using these lower bounds, we define proxy the budget for B7 (O, M) for
8

---

Published as a conference paper at ICLR 2022
Algorithm 2: Lower Confidence Bound for Conservative Exploration
Input: A non-conservative algorithm 2, d E (0, 1), lower confidence bounds AT VT conservative policy value V E (0,1)
Set B 00; Set t' =0; for 11.2.... T do
// the accumulated budget // the number of steps in which the agent acts as a
gives lower bound λ041 and a policy ßrt1:
Set A Σ * + X // lower bound of expected total reward
if (t' 1)V* < B then
Play ग. = To and set B = B + aV=;;
else
Play के = #1 and set t' = +
end
end
any subset O C [T) by
BT, (0,0)
Σ Ieon
(1- - (1-0))(o-\((00))
max 1EO
with (Ti)ge the sequence of policies computed by the non-conservative algorithm श. Then following from the definition of (X, (6))1S(, we have that with probability at least 1 that Br,s (0.*) 2 (r(O,2) 2). This shows that is possible to compute Br,s (0,2) without knowl- edge of the environment and the baseline parameters. The idea of our algorithm is now to play non-conservative policy at time only if the difference between the proxy to the budget of ğ and the reward accumulated by playing the baseline policy is negative. Formally, the condition is By, (8 U6, aV (I (Se)) where is the set of time step where non-conservative policy was deployed in episodes before t. As a result, the minimum budget that श requires to be conservative is max, Bi,5 (S. Ut, = max Eies, ((1 a)V= X, (6)). The algorithm, called Lower Confidence Bound for Conservative Exploration (LCBCE), is detailed in Alg. 2.
Next, we show the regret bound LCBCE. The proof is in Appendix D.
Theorem 3. Consider algorithm ब, (0,1) and constant C' E R such that with probability at
least 8, for any T 2 Rr (2) S Ö(CVT). If computes lower confidence bound such that Ei= (V** - X²²) - Õ(CVT) with probability at least 5, then for any T 2 1, the regret of LCBCE is bounded with probubility least 1 by Õ(CVT + av=o(aV +
C A0
In the MAB and tabular case, LCBCE paired with UCB achieves a better regret bound compared with previous papers(Garcelon Garcelon et al., 2020a; Wu et al., 2016). We also provide the first minimax optimal bound for the case of unknown baseline parameters. Finally, in low rank MDPs recover the same rate as in the case known baseline. See Table 1.
CONCLUSION
We present a unified framework for conservative exploration in sequential boeksinn-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. 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 dependent logarithmic bounds for conservative exploration. Another direction is to investigate model-free algorithms (e.g., Q-learning (Jin et al., 2018)) for conservative exploration.
can leverage this framework derive problem-

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
Liwei Wang was supported by National Key R&D Program of China Research Project of Zhejiang Lab (No. 2022RC0AN02), BJNSF (L172037), Project 2020BD006 supported by PKUBaidu Fund.
Exploratory
REFERENCES
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. NeurIPS, pp. 9252-9262, 2019.
Sanae Amani, Christos Thrampoulidis, and Lin F Yang. Safe reinforcement learning with linear function approximation. arXiv preprint arXiv:2
2021.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pp. 263-272. PMLR, 2017.
Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang. Efficient reinforcement learning in factored mdps with application to constrained rl. In International Conference on Learning Representations, 2020.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R. Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. In NeurIPS, 2020.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang. Zhaoran Wang, and Mihailo R. Jovanovic. Prov- ably efficient safe exploration via primal-dual policy optimization. In AISTATS, volume 130 of Proceedings of Machine Learning Research, pp. 3304-3312. PMLR, 2021.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic re- inforcement learning in finite mdps: Minimax lower bounds revisited. In ALT, volume 132 of Proceedings of Machine Learning Research, pp. 578-5988 PMLR, 2021.
Yihan Du, Siwei Wang, and Longbo Huang. one-size-fits-al solution conservative bandit. problems. CoRR, abs/2012.07333 2020.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explotaaiio in constrained mdps. CoRR, abs/2003.02189, 2020.
Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Conservative exploration in reinforcement learning. International Conference on Artificial Intelligence and Statistics, pp. 1431-1441. PMLR, 2020a.
Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Improved algorithms for conservative exploration in bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 3962-3969, 2020b.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Chi Jin, Zeyuan Allen-Zhu Sébastien Bubeck, and Michael I. Jordan. Is q-learning provably efficient? In NeurIPS, pp. 4868-4878, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Sumeet Katariya, Branislav Kveton, Zheng Wen, and Vamsi K. Potluru. Conservative exploration using interleaving. In AISTATS, volume 89 of Proceedings of Machine Learning Research, pp- PMLR, 2019.
Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi-Yadken and Benjamin Van Roy. Con- servative contextual linear bandits. arXiv preprint 1xXiv:6//.066 2016.
10

---

Published as a conference paper at ICLR 2022
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. UCB momentum q-learning: Correcting the bias without forgetting. CoRR, abs/2103.01312, 2021.
Aldo Pacchiano, Mohammad Ghavamzadch, Peter L. Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In AISTATS, volume 130 of Proceedings of Machine Learning Research, pp. 2827-2835. PMLR, 2021.
Steven E Shreve and Dimitri P Bertsekas. Alternative theoretical frameworks for finite horizon discrete-tine titrete--iieeaae stochastic optimal control. SIAM Journal on control and optimization, 16(6):953- 978, 1978.
Kun Wang, Canzhe Zhao, Shuai Li, and Shuo Shao. Conservative contextual combinatorial cascading bandit. CoRR, abs/2104.08615, 2021.
Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvári. Conservative bandits. In Interna- tional Conference on Machine Learning, pp. 1254-1262. PMLR, 2016.
Andrea Zanette and Emma Brunskill. Tighter problem- depeedent regret bounds in reinforcement learning without domain knowledge using value function bounds. In ICML, volume 97 of Proceed- ings of Machine Learning Research, pp. 7304-7312. PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In ICML, volume 119 of Proceedings Machine Learning Research, pp. 10978-10989. PMLR, 2020.
Xiaojin Zhang, Shuai Li, and Weiwen Liu. Contextual combinatorial conservative bandits. CoRR, abs/1911.11337, 2019.
Zihan Zhang, Xiangyang Ji, and Simon S Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. arXiv preprint WiXiv:2009.135000 2020a.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. In NeurlPS, 2020b.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvári. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. CoRR, abs/2012.085077, 2020.


Reviews:
[{"review_id": "rc9RVaiSfwI", "reviewer": "Reviewer_yivy", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths\n* The proposed algorithm LCBCE is a general framework which could be used to tackle many bandit and RL problems\n* For some of the problems (multi-armed bandits, linear bandits and tabular MDPs), a nearly optimal upper bound is obtained.\n* The paper is written well and the ideas are easy to understand.\n\nWeaknesses\n* Although the proposed framework seems very general, the main ideas of the paper come from the existing literatures. In the beginning, the authors propose a simple policy called Budget-Exploration which performs the baseline policy first to ensure that there is enough budget and then conducts the non-conservative policy for the remaining episodes of the game assuming that the gap between the optimal policy and the baseline policy ($\\Delta_0$) is known. A similar idea is already proposed in the BudgetFirst policy in Wu et al., 2016. Later, the authors extend the idea to the case when $\\Delta_0$ is unknown where they build an online estimate on the lower bound performance of the policy, which also shares a similar idea with Conservative UCB proposed in Wu et al., 2016. I find it difficult to believe the impact is significant except that the authors deploy the idea under a general problem setting.\n* No experiments are conducted to illustrate the empirical performance of the proposed algorithm.", "summary_of_the_paper": "This paper investigates bandits and reinforcement learning problems under the conservative setting where it is required that with high probability, the performance of the proposed policy is comparable to that of a baseline policy $\\pi_0$. An efficient framework LCBCE together with a lower bound are proposed which are able to be used to tackle the multi-armed bandit, linear bandit, tabular MDP and even low-rank MDP problems. ", "summary_of_the_review": "Although the authors propose a general framework to deal with multi-armed bandits and RL problems, it seems to me that the work is an extension of the existing work i.e., Wu et al., 2016 to a more general problem setting.  If I read the paper correctly, I did not see any new techniques developed to tackle this more general problem setting. \n\nDetailed comments:\n\n__Before section 2__, ... All these works focused on provide an upper-bound to the regret of a conservative algorithm...: provide -> providing\n\n__Notations__, ...there exists a constant $c$ such that $A \\geq (\\leq) cB$... : constant -> positive constant\n\n__After Assumption 1__, ... there exists $\\theta^{\\pi} \\in \\mathbb{R}^d$ such that $Q_h^{\\pi}(s, a) = \\langle \\phi(s, a), \\theta^{\\pi}_h \\rangle. $: $\\theta^{\\pi}$ -> $\\theta^{\\pi}_h$", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "P3r4Eyq8QxF", "reviewer": "Reviewer_wDiu", "summary": "", "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": "The paper is well-written in general and the contributions and the model are well-motivated. Numerical experiments that corroborate the theoretical guarantees of the paper are missing in the current version and I highly recommend to add some in the revision since the theoretical guarantees and algorithms seem to be incremental compared to the existing works.\n\nCould the authors provide a convincing argument about the non-incremental nature of the novelty.", "summary_of_the_paper": "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.", "summary_of_the_review": "The problem studied in this paper is interesting and I think it would interest the ICLR community. While the theoretical derivations heavily reliy on Kazerouni et al 2017 and Wu et al. 2016, the theoretical results are interesting. I have not checked all the proofs, but they seem sound and correct.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IWoVEUrtZ4C", "reviewer": "Reviewer_nbyJ", "summary": "", "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:**\n1. The paper is clearly written and easy to follow.\n2. The budget approach is simple and intuitive.\n3. The regret upper bounds are optimal (near-optimal for linear MDPs but this is the best one can hope for).\n4. The reduction approach provides lower bounds easily for many settings.\n\n**weaknesses:**\n1. The authors give too much credit to their MAB lower bound in my opinion. Notice that this lower bound is less tight than the previous one, and that it can be deduced from the previous lower bound and this paper's new upper bound. I think that the authors need to state this a little more accurately and focus on the lower bounds that they provide for the other settings (for which there were no previous lower bounds).\n2. Although there are no previous lower bounds for conservative linear bandits/tabular MDPs/linear MDPs, I think that the authors should discuss standard constructions. That is, if I take the construction of Wu et al. and embed it in linear bandit or MDP what would I get? Embedding MAB in MDP or linear bandit is common in sequential decision making problems and should be addressed in my opinion. Could the authors explain if this is not possible here or if it gives sub-optimal lower bounds? The derivation of lower bounds through the reduction is nice but it should be put in perspective against common approaches.\n3. The lower bound proof sketch is not clear at all in my opinion. I read the proof in the appendix and it was very clear so I encourage the authors to rewrite the proof sketch more closely to the way that it is written in the appendix (this is not a long proof).\n4. There is no proof sketch for Theorem 3. This is the most important theorem and there is no explanation regarding its proof. The way that the LCB is combined with the budget was very interesting to me, and I was very disappointed that the (short) proof from the appendix was not sketched at all.\n5. The authors mention safe RL and constrained MDP but do not explain what is the difference between them and conservative RL. These problems seem very related and I think a comparison or at least an explanation is in order.\n6. The authors claim that the concept of budget was already used in Wu et al., but that it is less general because it is for the UCB algorithm. Is it really less general or simply analyzed better in the current paper (since the reduction also uses confidence bounds I am guessing it will only work with optimistic algorithms)? I am wondering whether the budget approach is novel in this paper or does this paper just analyze it better (which is also a good contribution but should be stated accurately).\n7. The authors also mention budget in the context of the algorithms by Garcelon et al. and Kazerouni et al.. They say that their approach is different, but then just say that their budget is tighter. So is it really different or is the budget analyzed better in the current paper?", "summary_of_the_paper": "This paper studies online sequential decision making under a conservative constraint, i.e., the agent needs to perform at least as well as some baseline policy. The authors present algorithms based on a reduction from non-conservative MAB/linear bandits/tabular MDPs/linear MDPs, and prove minimax optimal (or near-optimal) upper and lower bounds on the regret.", "summary_of_the_review": "The paper studies an interesting question and presents a natural reduction-based approach that yields optimal upper and lower bounds. However, the relation to previous work is not described clearly, the proof sketches are either unclear or missing and the authors put their focus on a lower bound that is less tight than previous ones. Overall, while this paper has interesting contributions, it requires further revision before being published in my opinion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "AuAdtSFSxR", "reviewer": "Reviewer_g4nC", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper is well written. The studied problem is significant. The generality of the results are impressive.\n\nWhile the reviewer tends to accept the paper, the reviewers has some concerns.\n\n1/ No assumption is made on the baseline \\pi_0. However, Budget-Exploration plays \\pi_0 during a first period of time. What does happen if \\pi_0 plays only one sub-optimal arm? How can learn the non-conservative baseline ?\n\n2/ The proposed lower bound is not as tight the one in (Wu et al 2016): the right term is greater in (Wu et al 2016). However, Theorem 3 states that the regret upper bound of LCBCE reaches the proposed lower bound. Hence it violates the lower stated in (Wu et al 2016). Could you comment? (The reviewer does not understand the comment below Corollary 1).\n\n3/ The reviewer thinks that the comment on the comparison with (Wu et al 2016) above section 1.3 is not supported by the facts. In particular the reviewer does not get the sentence “our algorithm calculates how much budget the algorithm needs in advance, and therefore has a tighter regret bound”. First it only concerns Budget-Exploration. Second generally an algorithm that uses the seen data is better than an algorithm that does not use them.\n\n\nAFTER REBUTTAL\nThe authors have answered my concerns. I vote for acceptance.", "summary_of_the_paper": "This paper proposes a reduction-based framework for a large class of reinforcement learning algorithms, including bandits, linear bandits, tabular MDP and linear MDP.\nThe 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.\nThen, 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.\nThe 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.\n", "summary_of_the_review": "While the reviewer tends to accept the paper, the reviewers has some concerns.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary: The paper studies RL and bandits in the conservative setting where the performance of the new, learnt policy should never be significantly worse than that of a baseline. 

Discussions: The main concern of the reviewers was about novelty, and specifically what new techniques and ideas were brought in this work compared to (Wu et al. 2016) and (Garcelon et al 2020). The authors have addressed these concerns and updated their draft accordingly. The reviewers have now all reached a consensus and recommend to accept this work. 

Recommendation: Accept
Decision: Accept (Poster)