Pessimism for Offline Linear Contextual Bandits using $\ell_p$ Confidence Sets
Authors: Gene Li
Cong Ma
Nathan Srebro
Venue: NeurIPS 2022 Accept (2022)
Keywords: offline reinforcement learning
pessimism
linear contextual bandits

Abstract: We present a family $\{\widehat{\pi}_p\}_{p\ge 1}$ of pessimistic learning rules for offline learning of linear contextual bandits, relying on confidence sets with respect to different $\ell_p$ norms, where $\widehat{\pi}_2$ corresponds to Bellman-consistent pessimism (BCP), while $\widehat{\pi}_\infty$ is a novel generalization of lower confidence bound (LCB) to the linear setting.  We show that the novel $\widehat{\pi}_\infty$ learning rule is, in a sense, adaptively optimal, as it achieves the minimax performance (up to log factors) against all $\ell_q$-constrained problems, and as such it strictly dominates all other predictors in the family, including $\widehat{\pi}_2$.

This leads Pessimism for Offline Linear Contextual Bandits using lp Confidence Sets
Gene Li Toyota Technological Institute at Chicago gene@tt edu
Cong Ma Department of Statisties University of Chicago congm@uchicager edu
Nathan Srebro Toyota Technological Institute at Chicago nat @t c edu
Abstract
We present family {#ppp21 of pessimistic learning rules for offline learning of linear contextual bandits, relying on confidence sets with respect to different Ep norms, where π22 corresponds to Bellman-consister pessimism (BCP), while 7 is novel generalization of lower confidence bound (LCB) to the linear setting. We show that the novel oo learning rule is, in sense, adaptively optimal, the minimax performance (up to log factors) against all b ey-oostraieee problems, and such it strictly dominates all other predictors in the family, including #2.
achieves
Introduction
Offline (or batch) reinforcement learning (RL) [17 18 seeks to learn good policy from fixed historical data without active interactions with the environment. This offline paradigm has been widely adopted in applications including dialog generation [00, autonomous driving 43 and robotic control 16]. etc.
When the offline dataset has insufficient coverage over the state and action spaces, planning via nominal estimates either the value function or the model may perform poorly-a phenomenon that is observed even in simple two-armed bandit [24). This challenge motivates the adoption of the pessimism principle for solving offline RL. In essence, the pessimism principle discounts policies that are less represented//uppported in the offline dataset, and hence is pessimistic/conservaiie in outputting a policy. Built on this common principle, a diverse collection of pessimistic learning rules
have been proposed in theory and practice [II 24 36 37 45 46 9 [5] 34 14 21 42).
us to the following natural question:
Which pessimistic learning rule should one use for solving offline RL problems?
In this paper, address the question in the setting of offline linear contextual bandits, in which the expected reward-as function of the state-action pair-is linear with respect to a known feature mapping that maps state-action pairs sense of previously proposed learning rules for offline RL, and understand which learning rule is "optimal" in a statistical sense. We present a general family p of pessimistic learning rules based on the construction of l, confidence sets for the unknown linear parameter. We advocate for 7.o. a fox learning rule for offline linear contextual bandits, which we call Pessimism via Uniform Norm Confidence (for short, (UNCY)PUNT directly extends the lower confidence bound algorithm proposed the tabular contextual bandit setting
fiite-dimensional vectors. Our goal to make
(24). We show that PUNC (1) achieves suboptimality guarantee that dominates other मे (up to log factors, which we ignore throughout the introduction). and (2) has an alaptive minimax optimality property that unique among the family (7p)p21. In particular, we argue that PUNC dominates prior learning rules which are based on & pessimism (e.g.,
and which cannot attain adaptive minimax optimality.
Throuughou the paper, we use T. and PUNC interchangeably.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

We begin by introducing the problem of offline learning in linear contextual bandits. Let S and A be the state space and the action space, respectively. Let Φ x A - I2d known feature mapping. In the offline setting, we observe dataset D = [(si, di, r;)) j=1 where the covariates {(si, a:) ) are fixed and the rewards are drawn independently according to r. ~ R(s,, (z),, where R(s, a) the reward distribution associated with the pair (s.a). a). We assume that R(s, a) is I-subgaussian for every (s, a) with mean reward r(s, a)= == E E[R(s, a)). Furthermore, we assume that the expected reward linear in the sense that for every (s, a) pair, r(s, a) a(s,a) 8* TT for some unknown parameter Roadmap. We first introduce broad class of pessimistic learning rules in Section 3 The con- struction of these pessimistic learning rules relies on the observation that any confidence set of the linear reward function automatically induces pessimistic value estimate, and hence pessimistic learning rule. As concrete examples, for each p 2 1, one can design Tp. an lp learning rule, by constructing such confidence set using the lp distance metric. We show in Section 3.3 that 72 recovers the Bellman-consistent pessimism (BCP) learning rule [37], proposed for offline RL with general function approximation; meanwhile, fo generalizes the lower confidence bound (LCB) learning rule, proposed for offline tabular RL, to the linear setting.
Once we have cast pessimistic estimation in this framework, we can study the performance guarantees of the family p22. Employing a notion of pessimism-vari -iaiiiiiit (Definition [ allows us to easily to derive upper bounds on suboptimality for each .. in terms of the dual lg norm (where 1/p-1/6 1/q = 1); see Theorem
T For p = 2, the upper bound improves over that provided contextual bandits. For contextual bandits. A key observation regarding the upper bound is that the suboptimality guarantee of xx dominates all other Rp in the general linear setting. This partially showcases the advantage of using PUNC.
the paper (37 for linear
oc, the upper bound matches that proved in the paper 24 for tabular
To further investigate the advantage of PUNC over other 7p (for E [1, xc)) we consider the fundamental statistical limits of the offline linear contextual bandit problem in Section Inspired by both the upper bounds we prove and prior work [45] 24 40), we consider a sequence of norm- constrained classes of contextual bandit instances indexed by the Eg norm (q 2 1). We prove that each 7p is minimax rate-optimal within the dual norrm constrained contextual bandit class; see Theorem 2 However, Theorem delivers an even stronger message: PUNC is adaptively minimax optimal in the sense that it simu himulianeuusly achieves optimality for all fy-norm constrained classes, as illustrated by Figure [ We also demonstrate that such adaptivity is unique to PUNC as other values of p (e.g.. p 2) cannot achieve simultaneous optimality. Instead, T, is only adaptively optimal for normm constrained classes where q 2 p/ (p- - 1); see Theorem
In summary, our main contributions are the following:
We introduce novel learning rule, PUNC, for solving the offline linear contextual bandit problem, whose performance guarantee dominates those of all other 7p. for finite (Theorem D..
We show minimax lower bounds over norm-constrained classes of contextual bandit instances, which show that each 7p is optimal over the dual Eg class, up to log factors in the dimension (Theorem 2)
We demonstrate that PUNC satisfies the adaptive minimax optimality property (Section 4.2) and show that this property is unique to PUNC by proving a separation result against any other 7ip (Theorem 3 and see also Figure
2 Problem setup
vector 0+ E Rd.
Let π: : S > A be a deterministic policy. Fixing a (known) test distribution p E A(S), we define the value of the policy π (with respect to p)
V(T) = Es-p [r(s, π (s)) Es-p Ts))
(1)
Correspondingly, we define the optimal policy π
I (s) = arg max r(s,a) arg max o(s, a)T@ TO,, 0+, for each E S. a
(2)
The goal of offline learning in linear contextual bandits is to design a learning rule which takes as input dataset D and outputs a policy ãे that maximizes the value (T): this paper we abuse notation and also denote the learning rule f. We measure the suboptimality of स using V(x*) ) (().

---

3 Offline learning with pessimism
The pessimism principle has recently gained much attention in offline RI theory and practice. At high level, pessimistic learning rules first construct data data-dependent estimate ((T) of the true value function (T) that is pessimistic, i.c., (TT) I (TT) for all æ. Then, the learning rule proceeds to select the policy that maximizes this pessimistic value function, i.e.,
= arg max (TT).
(3)
Elll
Here, IT C A is some policy class that contains the optimal policy n². To why this choice of policy makes sense, let us decompose the suboptimality of मे as follows:
V(x*) ( (V(**) - ((*)) + (V(m*) - V()) (V()) -(R)):
(4)
The middle term is non-positive by definition of 7. Due to the pessimistic property of V. also have V( ( z O, which yields the suboptimality upper bound
V(T*) - V(+) s ((TT'-((TTT)
(5)
Consequently, under the selection rule (3) a tight pessimistic value function V induces policy with small suboptimality.
3.1 Achieving pessimism by building confidence sets
As general strategy, one can construct the pessimistic value estimator V by building confidence sets for the linear parameter 0" Let C IRd be confidence set that contains the true parameter 0*, We can define the corresponding pessimistic value estimator
((T) == inl Ex=plo(s, (s))
(6)
dE
and its associated policy learning rule Te == arg max (TT) Here for simplicity we take IT to be the class of all deterministic policies.
In essence, the confidence set θ captures the amount of uncertainty we have about the ground truth 0* Once è is determined, we construct the value estimate ((T) via the worst-case value of x among all plausible linear parameters 0 in the confidence set @ is immediate to see that under the assumption 0* O one has V (m) S (T)) for all æ. In other words, the value estimator V is indeed pessimistic. As result,
apply the general upper bound (5) to obtain
V(=*) (ffe) & V(=*) - ((T*) = sup Ex-plø(s, (s)) T(0* - -0),
where the identity follows from the definition (6. Clearly, the "smaller" the confidence set. the smaller the bound suboptimality. An extreme case is when θ contains the singleton f*, which yields zero suboptimality. However, since only noisy rewards are observed, we cannot hope to construct such good confidence set. Given the uncertainty about the rewards, confidence set has to be "large" enough in order to guarantee that 0* E O with decent probability.
Below we present general definition called pessimism-validing that involves both the size of the confidence set and also its confidence level, both of which allow us bound the suboptimality the pessimistic learning rule ee. Let ||- be any norm over Ed that will be used to measure the size of the confidence set θ Let ò E (0, be the failure probability. We have the following definition.
Definition 1. We say the confidence set @ is (3, 8) pessimism-valit under the norm ||||| if with probability at least 6, the following two properties hold: (1) 8 e θ; (2) supsee ||@* - 01 < B.
A (8, 8) pessimism-valid confidence set @ automatically induces a pessimistic learning rule सe with bounded suboptimality, as shown in the following proposition.
Proposition 1. Suppose that is (3, 5) pessimism- valid under the norm I|-I|- Then with probability least 8, the pessimistic learning rule सe obeys
V(x*) - V < 3
(0(s, x<))
supp
where I1.1l. is the dual norm of ||-1|.
3

---

Proposition 1 simply follows from the upper bound 7 the definition of pessimism-valine and the definition of the dual norm.
3.2 Building b confidence sets
In this section, we instantiate the general strategy introduced above for achieving pessimism by
constructing an Ep confidence around the true parameter 0* for some p 2 1. Such constructions using lp norms include the aforementioned BCP and LCB learning rules (as well as other recently proposed learning rules) as special cases. As we will see, setting up the notion of ressimism-validiee allows us to easily bound the suboptimality of the induced policy learning rules.
Let us denote the data matrix @ E Rnxd where the i-th row of ④ is given by ((s;, a.) We also be the
define the observed reward vector r (ri....., TT)T E IR. Let Ools == () ordinary least-squares estimate for the true parameter 0* Throughout the paper, we assume that the az sample "covariance" matrix Ed = - (()),,;)d(s; a.) L
invertible. (The results in the paper can be modified to accomodate the scenario when Ep is not invertible by considering
n
regularized quantities Ep + AI for some À > 0.) We then consider the confidence sets of the form:
8 A E F2 - Bos) s /B/2]
where > 0 is width parameter. In other words, the set O₂ contains all the O's that close to the OLS estimate fots in f, distance after the linear transformation r;1/² Since Bots is a faithful approximation of the truth 0*, expect that 0 lies in this confidence set O, with an appropriate choice of B. This is indeed true, as the following lemma shows.
Lemma 1. Fix any (0, 1). Set the width parameter 3=6 d2/1 8log(d/5) Then the confidence set Op is (3, 5) pessimism-vale valid with respect to the norm ||0|| == |ED
1//22m1 ullp-
See Appendix B.I for the proof of this lemma.
Combining Lemma I and Proposition D [immediately yields the following performance guarantee for the pessimistic learning rule constructed using 6₂ (which for notational brevity we denote as Rp))
Theorem 1. For any p 2 1, with probability at least 1 d, we have
V(T*) - ((r S d/p/
8 8log(d/5)
|> 1/2 10-1/2Emn Baup (0,0, x (6)))l,
n
where q is the solution 1/p + 1/9 =
Several remarks regarding Theorem I are order. First, the performance upper bound has a natural scaling w.r.t. the sample size n, i.e., V(TT) ((Tp)) S VI/n. In addition, Theorem provides a family of upper bounds for each specific choice of p 2 1. Lastly, from an upper bound perspective, the Too learning rule (which we call PUNC) dominates all the other E [1, oo), since for any v E Id
and E [1, oo), the inequality ||w||| < d ||u||, holds. This partially showcases the benefits of using PUNC over the alternatives. Later in Section we will see a stronger motivation from the perspective of the lower bound-for using PUNC, in which we show that PUNC is adaptively minimax optimal. We also remark that the max-min form for कi has an equivalent max-on max-only formulation, which will be helpful for proofs and comparisons to other algorithms:
Esep (o(s, [((s) [())]] 0os- o | (Ms (0).)
Tp = arg max TEIT
3.3 Connections to prior pessimistic learning rules
Now we present several connections to existing methods used for offline linear contextual bandits.
Connection between ीH and Bellman-consistent pessimism. Xie et al. 37 proposed the idea of Bellmaa--onsistent pessimism (BCP) for solving offline reinforcement learning with general function approximation. When specialized to linear contextual bandits, the BCP learning rule first forms

---

version space that includes all possible linear reward functions with small lz prediction error on the observed datasets, Then, BCP defines each policy's pessimistic value as the smallest value the policy can achieve in the version space. Finally, BCP returns the policy that has the highest pessimistic value. fact, BCP exactly matches the learning rule क22 proposed herein. To see this, suffices to note that the empirical estimate of the Bellman error (cf. Equation (3.1) in the paper (37]) in the linear contextual bandit case is given by
(0(ss; ao) ri)²
inf BER
a Σ (d(si; a:) --;; - -00t))))))
=1>=///00
0st)
Therefore a parameter having small Bellman error is equivalent having a small distance to the OLS estimate. Xie et al. (37 prove that BCP enjoys the guarantee (up to log factors) of theoretical guarantee / vd/n.
vd/n E, || 2(,, T [s)) which is loose compared
"" (s))) as a consequence of Jensen's 's inequality and the convexity of the f norm.
Similar ideas using the &g confidence set also appear in recent paper by Zanette al. 45 ; their actor-critic algorithm, PACLE, can be interpreted as providing a computationally efficient way to solve म2
Connection between PUNC and lower confidence bound for tabular contextual bandits. We now discuss how the LCB learning rule for the tabular setting is specialization of PUNC. The tabular contextual bandit setting a special case of the linear setting with the feature mapping (ss, a.) Csa (the canonical basis vector indexed by (s, a)). For notational convenience, define = S). A = Al, F(s, a) to be the empirical average reward, and (s,s, a) to be the number times the pair (s.a) is seen in the dataset.
Rashidinejad et al.
24 present the following lower confidence bound (LCB) learning rule:
(s) = arg max F(s, a) - 8 (og(SA/0)
for each
(10)
n(s,a)
aEA
In essence, the quantity a(s
((s,0) acts as a lower confidence bound for the true mean reward r(s, a). In every state, LCB picks the action that maximizes this lower confidence bound. It is easy to verify that LCB (TO) exactly corresponds to PUNC (with proper choices of ()); one just needs and q 1.
(Sg(5
to check the max-only formulation in Equation with
In establishing performance guarantees for LCB, Rashidinejad et al. (24] assume that the covariates {(s;, a:) }i are drawn i.i.d. from a behavior distribution E (S x A) (as opposed to our fixed design setting). Nevertheless, it is straightforward translate our results this random design case by using Chernoff bounds.
Corollary 1. In the tabular setting, with probability at least - 6, the learning rule Too with + given by Equation
(8) achieves the suboptimality:
log(S (SA/AAA))
p(s)
V(TT) - V(Tx)) S
p(s क ++)))))))
as long as ni 2 log(S/8) (min, (s))))
Corollary is proved in Appendix B.2
Compared to the upper bound in the paper 24 Corollary I is more fine-grained, or "problem- dependent", as the suboptimality bound depends on the interaction between the specific behavior distribution μ and test distribution In contrast, Rashidinejad et al. (24) consider the class of tabular instances with bounded single-police concentrability coefficient.
Definition 2. The single-poles concentrabilliy coefficient is defined as C* = supses (s))
m(s)
Corollary readily recovers the performance guarantee for LCB of Õ(V5C*/m) established the paper 24 which is optimal in the regime where C* > 2.
Whilee we focus on the statistical properties of the familly { } in this work, we believe that the actor-critic approach developed by Zanette al. 45 can be extended to yield tractable algorithms for general p 1.
5

---

Connection to pessimistic value iteration. We give another example of how to interpret pessimistic learning rules using the idea of confidence set construction. Consider the pessimistic value iteration (PEVI) learning rule proposed by Jin et al. [1I. PEVI directly extends Equation (TO) to the linear setting:
PPEvI(S) == arg max ((5, - 1/2 (s,a)
3. 8.115
(11)
aEA
where the right hand side still acts as a lower confidence bound for the true mean reward r(s, a). PEVT bears striking resemblance with the max-only formulation ? (with p = g 2), with the key difference that the max-only formulation "averaged" over the test distribution p. while PEVI
directly discounts every (s, a) pair. PEVI does not immediately fit into our confidence set framework. However, if we modify the minimization over confidence sets to minimization over functionals 0:8 Rd, then we can rewrite PEVI
#PEVI == arg max inf Bemplo(s, (ss))) *ET
OEG
where + = {s ((s)
| (0(s) (0(s) 0ots) 12 3, for all s]
In other words, PEVI enlarges the Eg confidence set by separately picking pessimistic parameter ((s) for each state E S. Jin al.
| prove the guarantee (up log factors) of / dd///
(5, x (s))ll2 which loose due to the extra factor of and the interchanging of the expectation and the norm. However, their guarantee holds for all test distributions-as opposed to a fixed test distribution p. This is consequence of being pessimistic for every state 8.
Exep || 1/2 ((s,
4 Which learning rule should one use?
Having introduced a general strategy for building pessimistic learning rules by constructing ép confidence sets, is natural ask which Ωp one should use. To enable such comparisons, we investigate the statistical limits of offline linear contextual bandits over constrained sets of problem instances.
4.1 Minimax lower bound for constrained instances
For any feature mapping & :: S x A + R4, sample size n E N. and two quantities g E [1, oo), A > we define set of linear contextual bandit (CB) instance as follows:
(B₂(A)== (p. (si, a.)) 0* RR)
" lo(s, = (+)]] SA, R is I-subgaussian
The set (A, includes all the linear contextual bandit instances such that a sort of "complexity measure" " Cg == / (0(s, n* (s))]ll, is at most A. Our motivation to consider the rate of estimation in the CB family CB, (A) are two-fold. First, in view of Theorem I the family (B,(A) admits a good learning rule, specifically म. with t/p+ 1/q = 1, since for every Q E CB,(A), w.p. at least 1 5,
V V Vo S de /log/ /loo(d/o)//
(12)
where Vi denotes the optimal value in instance Q and VT( denotes the value of policy in instance Q. Thus, it is natural to view e. as a certain complexity measure for offline learning in linear contextual bandits. Second, prior work 45 24 40 has proven various types of lower bounds on offline learning using either the &2 quantity C2 or the & quantity C, We will elaborate more on this point later.
Now we are ready to present the minimax lower bounds for these families of CB instances.
Theorem 2. For every d 2 2, there exists feature mapping & such that the following lower bound holds. For any p.q 2 such that 1/p + 1/q = 1, as long as A 2 v8. d /9/1/2 and n 2 d we have
inf sup (A)
E V
V2(
d A/n-A,
For brevity, omit the dependence on & and in the notation (B,(A).

---

where с >> 0 is some universal constant. Furthermore, when 30,q 1, the lower bound holds for the extended range of 2 2.
The proof can be found Appendix C It relies on a reduction to bound for the minimax regret of the multi-armed bandit problem.
We note that Theorem 2 also consists of a family of lower bounds for each l, norm constrained CB class. By comparing the lower bound in Theorem with the upper bound (12) obtained by Tp. we see that for the eg norm constrained class (A), the learning rule H. with 1/p + 1/g is minimax rate-optimal, up to a log d factor. For instance, over the & class (A), the minimax rate of estimation is @ /d/n A),, while over the & class CB₁ (A), the rate is given by θ(vI/n A).
On a technical front, it would be interesting to extend Theorem to the entire range of A Z 0. is unclear whether the same minimax rate of (dd //n A) holds when A (dd'/n11/3) whether we can achieve faster rates in the small A regime. In the tabular setting, Rashidinejad et al. [24] recently showed that LCB achieves fast 1/n rates when the single policy concentrability coefficient small; similar results might hold in the linear setting. Several limitations prevent us from extending the range of A in Theorem 2 Appendix C.I provides more technical details.
4.2 Adaptive minimax optimality of PUNC
We point out even stronger message delivered in Theorem 2 PUNC is adaptively minimax optimal for solving the offline linear contextual bandit problem. This is illustrated in Figure [ where we plot the sample complexity required in order to achieve constant suboptimality (say, 0.01) for various (Bp/(p-1) (A). (For sake of illustration, it is more convenient to work with p rather than on the ur-axis.)
As indicated by the red line, Theorem 2 shows that every learning rule must incur sample complexity at least Q(d2/pA) A?). Likewise, we can also follow the discussion after Theorem to see that the per-
formance upper bound of no is ddt/p, V log(d/a) C,
Es perferranoe (1hm. 1-Thm
d-A-
for all p.q 2 1.1/p 1/g 1. Thus, PUNC at- tains the green line in Figure []] that is, PUNC is simultareously minimax rate-optimal for all nn-orrm constrained classes (A), up log d factor From worst-case perspective, one should always pre- fer using PUNC given unknown CB instance.
performance (1hm.
oc Figure 1: Sample complexity of से (for var- ious p) over different CBp/(p-1)( (A) classes. The red line corresponds the minimax lower bound, Other lines correspond to different val- ues of and show the number of samples required to ensure SuPQECB
2
this adaptive optimality property unique to PUNC among the family { we consider? Below, we answer this question in the positive by presenting a separation result.
B
( < 0.01. The blue and green lines cor- respond to ीे2 and To respectively. Two pur- ple lines correspond to ी. for some P (1,2) and ğ E (2, oo). PUNC attains minimax op- timality over every class, while other केे do not.
Theorem 3 (Informal). Fix any p 2 For suffi- ciently large n, d, there exists contextual bandit instance Q E CB₁ (A) with A = /8d, such that with probability at least 1/4, Rp has suboptimality least (yd / A).
Since PUNC attains suboptimality of O(1/// A) over the class (A), Theorem shows that every other Ω is suboptimal over the class (B)(..
A formal statement of Theorem 3 and its proof can be found in Appendix D The key intuition in the proof that the Ep confidence sets capture a notion of error that is "averaged" over directions, while the fox confidence sets separately estimate the error in each direction. In the hard instance we construct, only one direction determines the difficulty of the offline learning problem, so n. is worse
We did not investigate when the log d factor in Theorem can be removed, so for example, it is possible that ft beats 7oo over (Ba(A) by factor of vlog d.
7

---

10
10
100
Sabcatimelity
10
S.bootinallts
80
6
10-2
10-
60
(b)
40
1010
0-10
20
10
10
10
10
10-4
10
10f Number Samples
10
10a
10
10a
Number of Semples
Number Samples
(a) Random rotation
(b) Basis-aligned
(c) E and & complexities
Figure 2: Comparing the performance the plug-in rule, T2. and 35 on linear contextual
bandit instances with d 100, averaged over 100 trials, with 90% confidence intervals. (a) Φ; ~ NO QDQ") ) and 0r = Qenn, where Q is a random rotation matrix and D is a diagonal matrix with entries Da = :===////0 1. (b) Φi (0, D) and 0 e2n- (c) computed average val- ues for C and vd x C2 The quantity C2 is identical in both plots (a) and (b). For (a), e v C2. while for (b), E < vd x E2.
by factor of d There is nothing special about the choice A 8d, and our construction works for any A 2 (Vvd); pick it to enable comparison with Theorem
For sake of discussion, consider 72.. Theorem
shows that क2 attains the rate:
d/r log(d/8) dlogd//8) |25 //2 Eemp (T(s n (6))
1 Exup (0(s, x (s)
when g 2 2,
V(**) - ((22)
n
when q E [1.
n
Together, Theorem 2 and 3 provide the message that both cases in the upper bound are tight (up to log factors). In the range p E [1.2] (or 2 2). Theorem shows that l2 attains the minimax optimal rate (up to log factors) over (Bp/(p-1)(A) i.e., adaptively minimax optimal here. This explains the curved part of the blue line in Figure D On the other hand, Theorem 3 shows that 7o cannot obtain the minimax rate over CB (A). Instead, म2 may require 22(d A?) samples in order to achieve constant suboptimality. Since for any p. the set CBp/(e-1)(A) 2 CB₁ (A), we know that ît2 may require l(d A?) samples for any CB,, ( (A)) Thus, the second case is tight when p 2 2 (or q E [1. 2)), explaining the flat part of the blue line in Figure In general, for any finite the learning rule ni will be adaptively optimal for CB CBp/(r-1) 1) (A) only in the range p E [1, pl. and afterwards the sample complexity will "flatten out", as illustrated by the purple lines in Figure I
Experimental Evidence. order to further validate this claim, we provide experimental evidence which shows that ßo does not adapt to "easy" CB instances. In Figure 2 linear contextual bandit in which there is a single state and the feature set is Bd, thus the policy learning problem is equivalent to finding a vector æ E gd-1 that maximizes
we consider simple offline
V(T) = A We vary the offline dataset distribution and the hidden parameter 0*. When f is basis-aligned, we have vd x Ez when 8* is not basis- the two quantities are on the same order.
e,
4.3 Comparisons with prior lower bounds
There exist several lower bound results for offline reinforcement learning in the literature. In this section, we compare our lower bounds (cf. Theorem 2 with the prior bounds and highlight several improvements offered by our results.
Comparison to lower bounds w.r.t. a single A. Our lower bounds are stronger than those provided in the papers [1 45), which hold for specific choices of y q 2 and single fixed A. Take Theorem 2 of Zanette et al. 45 for example. Zanette et al. proved that the minimax rate of estimation over CB₂ = d) is given by d3/2 / Such a lower bound fails to uncover the fundamental scaling on the complexity A F Theorem 4.7 of Jin et al. [IT) shows result in similar spirit; their construction essentially shows a minimax lower bound of 1 over (B²(A) when = O(1). Furthermore, their
'For instance, their result does not preclude the possibility that the correct lower bound over CBz(A) takes expression, say, d' 96.5,
-9.55 A 100 /nn.
8

---

Wond-eese
indannos onisaid
CB V25
Wordsrwe Instances
coincdd
CB v
Insianes churacterization loowe
Figure 3: Illustaating the relationship between single policy concentrability and boundedness of G1. Left: When C* = 2, the quantity Ci always provides a tighter characterization the problem difficulty, and the worst-case instances coincide. R: When C 1, the quantity En does not provide a tight characterization in general.
lower bound loose by factor of Vd since they reduce two-point hypothesis testing problem. In contrast, our lower bound holds for nested families of CB instances with varying complexities A, which better showcases that the norm quantity an intrinsic measure of difficulty for offline learning.
Connections with single-policy concentrability. Our lower bound shares a similar flavor as that established in the paper (24), with the key difference lying in the class of CB instances under consid- eration: Rashidinejad et al. [24] consider the contextual bandit instances CBcone (C*) with bounded single-policy concentrability coefficient C** (cf. Definition 2, while we consider the instances with bounded complexity C, These two quantities are intimately related, and we illustrate the relationship
in Figure As we have alluded in Section
3.3 one has the inclusion
CBoone (C*) C CB, (VSC')
When C* 2 2. the minimax rate of estimation over CBeone exactly matches that over CB, (BI(VCC*) which implies that the hard instances for CBrone (C*) are also the hard instances in CB , (v However, this no longer holds when C* E [1, 2). Take C* = as an example. Rashidinejad et al. show that the optimal rate over CBeone (C* 1) S/n, while Theorem 2 indicates that the optimal rate over CB, = vS) is vS/n. There no contradiction, since the hard instances we construct for (v3)) satisfy C 2 2. This shows that when C < 2, we "lose something" by working with the larger CB, (v class, as we are no longer able to achieve the fast rates possible over CBeone(C*)
On the flip side, the quantity e can give tighter suboptimality guarantees than the C* bound for a given instance. Consider the tabular instance where p Unif(S) and n(1, (1)) 1/83, while u(s, (s)) 1/S for all 8 2 2. This instance has C* S², implying guarantee of 83/2 / /n, while C (V)S), implying better guarantee of vS/n.
4.4
A better complexity measure?
Our results lend support to the claim that we should always use PUNC, since it is simultancously minimax rate-optimal over all the l, norm-constrained contextual bandit classes. Furthermore, the & quantity E can be thought of as a "complexity measure" that dominates other bg 'ccoplexity measures" C2 for q > To this, consider the following thought experiment. Suppose before solving the linear contextual bandit problem, an oracle told us that the instance satisfies C.y I A. The results herein show that we do not lose anything by assuming that the instance satisfies the weaker condition e < d! /P/AA AA using PUNC will give the optimal rate of d' d//9// ////////AA A.
However this is certainly not the complete answer to guiding question of "which pessimistic learning rule should one use for offline linear contextual bandits?"" One piece of evidence comes from the comparison with the single policy concentrability assumption: in the regime where C' E [1, 2). we do "lose something" when we assume the instance satisfies the weaker condition C₁ S SSO Below discuss another drawback associated with using C₁ as the complexity measure.
Rotation ambiguity. One drawback of the complexity E (as well as the learning rule PUNC) lies in the fact that it is not rotation invariant. (In fact, C2 is the only rotational invariant complexity!)

---

To see this, let U E R be fixed rotation matrix. Suppose that the features are rotated from @ to Uò which yields a different complexity (U) 1 Es-p [Ø(s, -= (s))]l where 2d is defined using the old feature mapping. Since the & norm is not rotation invariant, the e (U') varies for differing choices of U, by up to Vd factor. Thus, we cannot claim that any "complexity measure" (U) dominates others. A naive attempt to modify the & set to be rotationally invariant by taking a minimization over U also fails; observe that:
O2, that is, we recover Ā2. A similar equivalence holds if we take the max inside the confidence set; we will recover the confidence set with an extra factor of vd.
O ==
{0 0 Rdd inf U
U (0 -Baw) s =
Poz) S
Instance-dependent optimality? Arguably, the strongest possible support for PUNC would be an instance-dependent lower bound which shows that for every specific linear contextual bandit instance, the performance achieved by PUNC not improvable. Instance-dependent optimality results have been shown for related problems such policy evaluation [3 12] and optimal value estimation [I3] in tabular MDPs; the recent work [7] also employs the local minimax method for online bandit and RL problems. For offline bandits, the paper [36] shows how a particular definition of instance optimality cannot be achieved by any algorithm. Establishing instance-dependent guarantees for offiine learning is important direction for future research.
Recent work 440] establishes the local minimax rate for offline learning terms of the complexity E for tabular contextual bandits. However, the theorem seems incorrect; provide counterexample Appendix to demonstrate-vis explicit construction-that the complexity C₁ cannot characterize the local minimax risk for two-armed bandit instance. The key observation is that the reduction used in the proof of the paper [40] from offline policy learning to optimal value estimation is invalid; if the gap in rewards for different actions is large, offline policy learning is fundamentally casier than optimal value estimation. This in turn allows us to break the claimed parametric 1/ / rate.
Conclusion
In this paper, we introduce family p2 of pessimistic learning rules that include number of prior works as special cases for the problem of offline learning in linear contextual bandits. We prove upper bounds for each learning rule Ωt and show matching minimax lower bounds over appropriately defined constrained instance classes. Our results highlight the benefits of using PUNC, the 7o learning rule: namely (I) the guarantee for PUNC dominates all others; (2) PUNC is the sole learning rule with an adaptive minimax property. In particular, our results demonstrate that prior learning rules based on & pessimism can be suboptimal (by factor of vd).
Below list several interesting directions for future investigation.
Extending MDPs. The MDP setting is more difficult due to the long horizon and transition dynamics. Extending the results of this paper to the MDP setting is an interesting future direction. One possible approach is to modify the PACLE algorithm [45] to solve for any Ep learning rule.
Gap-dependent bounds. In online RL, there wealth of results which adapt to easy instances which are characterized by gap structure in the rewards, see, e.g., c 32). Obtaining tight gap-dependent bounds for the offline setting is an interesting direction for future work.
Offfine RL with general function approximation. In this paper, we focus on offline RL with linear function approximation. What is the right extension of these l, learning rules to general function approximation? While मं has the natural interpretation of defining version space with small squared prediction error, no such interpretation exists for PUNC. It would be interesting to establish an analog for PUNC for general function classes.
Acknowledgments and Disclosure of Funding
This work is supported by funding from the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL..
10

---

References
[1] Léon Bottou, Jonas Peters, Joaquin Quiñonero-Camee Candela, Denis X Charles, D Max Chickering. Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
[2] Jinglin Chen and Nan Jiang. Information-theoree theoretic considerations in batch reinforcement learning. arXiv preprint arXiv:/905.0 003600 2019.
[3] Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizability: the power gaps. arXiv preprint arXiv:2203. 2022.
[4] Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alckh Agarwal. Adversarially trained actor critic for offline reinforcement learning. arXiv preprint arXiv:2202.02446, 2022.
[5] Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. arXiv preprint arXiv:2103. 2021.
[6] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective. arXiv preprint arXiv:2010.03104 2020.
[7] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.134495 2021.
[8] Dylan J Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline rein- forcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919, 2021.
[9] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pages 2052-2062. PMLR, 2019.
[10] Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv: /ttl::/9900000000 997700056,, 2019.
[11] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference on Machine Learning, pages 5084-5096. PMIR, 2021.
[12] Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin Wainwright, and Michael I Jordan.
Is temporal difference learning optimal? an instance-dependen analysis. arXiv preprint arXiv:2003.07337 2020.
[13] Koulik Khamaru, Eric Xia, Martin J Wainwright, and Michael I Jordan. Instance-opiimality in optimal value estimation: Adaptivity via variance-reduced q-learning. arXiv preprint arXiv:2106. /4352, 2021.
[14] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL: Masel-based offline reinforcement learning. arXiv preprint arXiv:2005.05951,, 2020.
[15] Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy Q-learning via bootstrapping error reduction. arXiv preprint arXiv:1906.000 00949, 2019.
[16] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33: 1179-1191, 2020.
[17] Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
[18] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020. 2020.
11

---

[19] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of mooeel-based offline reinforcement learning. arXiv preprint arXiv:2204.05275. 2022.
[20] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[21] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202. 2020.
[22] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
[23] Ashwin Pananjady and Martin J Wainwright. Instance-dependers -boudds for policy eval- uation in tabular reinforcement learning. IEEE Transactions on Information Theory, 67(1): 566-585, 2020.
[24] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint UrXiv:2103.1202/ 2021.
[25] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint arXiv:2202.13890 2022.
[26] Max Simchowitz and Dylan Foster. Naive exploration is optimal for online lqr. In International Conference on Machine Learning, pages 8937-8948. PMLR, 2020.
[27] Alex Strehl, John Langford, Sham Kakade, and Lihong Li. Learning from logged implicit exploration data. arXiv preprint arXiv: 2010.
[28] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, pages 814-823. PMLR, 2015.
[29] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. advances in neural information processing systems, 28, 2015.
[30] Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint urXiv:2107.06226 2021.
[31] Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprint arXiv:2110004652, 2021.
[32] Andrew Wagenmaker and Kevin Jamieson. Instance-deppndent near-optimal policy identifica- tion in linear mdps via online experiment design. arXiv preprint arXiv:2207.02575. 2022.
[33] Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.1 1895, 2020.
[34] Yifan Wu. George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint 1111v.111, 2019.
[35] Yihong Wu. Lecture notes on: informatiion-theoreiic methods for high-dimensional statistics. 2020.
[36] Chenjun Xiao, Yifan Wu, Jincheng Mei, Bo Dai, Tor Lattimore, Lihong Li, Csaba Szepes- vari, and Dale Schuurmans. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning, pages 11362-11371 PMLR, 2021.
[37] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. arXiv preprint 2021.
12

---

[38] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34, 2021.
[39] Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-learnig. arXiv preprint arXiv:2203.07368, 2022.
[40] Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. arXiv preprint arXiv:2 2021.
[41] Ming Yin, Yaqi Duan, Mengdi Wang. and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv: 058044 2022.
[42] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model-based offline policy optimization. arXiv preprint arXiv:2005. 13239, 2020.
[43] Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of au- tonomous driving: Common practices and emerging technologies. IEEE Access, 8:58443-58469, 2020.
[44] Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. In International Conference on Machine Learning, pages 12287-12297. PMLR, 2021.
[45] Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. arXiv preprint (rxXi:2108.08812 2021.
[46] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D Lee. Offline reinforcement learning with realizability and single-policy concentrability, arXiv preprint 22XXiv2202.0405 2022.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical work which does not have immediate societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We describe the few dozen lines of code. (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
experiment we ran in sufficient detail; can be replicated
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Experiments were ran on a laptop.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "lCMhu4FgAAO", "reviewer": "Reviewer_oqs5", "summary": "This paper proposes a family of offline pessimistic learning algorithms for linear contextual bandit based on $\\ell_p (p\\geq 1)$ confidence sets (called $\\widehat{\\pi}_p$). Among them, the algorithm based on $\\ell_\\infty$ confidence set (called $\\widehat{\\pi}_\\infty$) has the smallest suboptimality gap. Furthermore, it also proves lower bounds for classes of linear contextual bandit problems indexed by $q\\in[1, \\infty]$ and shows that $\\widehat{\\pi}_\\infty$ is minimax optimal for all classes of problems.", "questions": "- It looks peculiar that the requirement for $\\Lambda$ in lower bound becomes purely numeric when $p=\\infty$. Is there any intuition for this?", "limitations": "Yes, the limitations are adequately discussed, especially the regime where the proposed lower bounds are applicable.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThe claim that $\\widehat{\\pi}_\\infty$ is adaptively minimax optimal is appreciated and considered to be highly novel. Meanwhile, this paper also provides thorough discussion and comparison between $\\widehat{\\pi}_\\infty$ and previous methods, showing non-trivial advantage of $\\widehat{\\pi}_\\infty$. Furthermore, to support its claim, this paper also proposes a novel lower bound and complexity measure for linear contextual bandit problems.\n\nThe writing of the paper is also in a good logic flow.\n\n### Weaknesses\n\nMinor issues:\n- It may be better to have a separate section for conclusion to summarize what has been discussed before.\n- It may be better to give a sketch or core idea of the hard instance construction for proving the lower bounds.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cG7mVIKAtzA", "reviewer": "Reviewer_aDkY", "summary": "This paper proposed a new confidence set estimation approach for linear contextual bandits based on the pessimistic principal. The optimality gap is derived using the dual norm techniques. The authors are able to show that the l_p confidence set attains the optimal rate when p=infinity. Furthermore, the paper showed that using p=infinity also achieves the adaptive minimax optimality. Experiments on synthetic dataset demonstrate the confidence set derived in this paper is valid and using l_infinity norm indeed outperforms the other candidates.", "questions": "(1) How to justify that the paper has significant contributions to the linear contextual bandit community?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1). This paper provided a suite of methods for deriving valid confidence set in the linear contextual bandit scenario. Furthermore, the paper suggested that using l_p norm with p=infinity gives the best suboptimality guarantee. The theoretical results are interesting, which I believe will facilitate future research in offline linear contextual bandits.\n\n(2). The pessimism principle is well-motivated in the beginning of the paper, and it is very clear why pessimism would work in the offline linear contextual bandit scenario through equation (7).\n\n(3). The related works are thoroughly discussed. Two important prior works, the LCB and BCP, are special instantiations of the general confidence set derived in this paper. Therefore, this paper can be viewed as an extension of prior research to the broadest setting.\n\nWeaknesses:\n\n(1). I am a bit skeptical of the contribution of this paper. In particular, the paper basically unified the prior works on LCB and BCP and provided a generic approach for confidence set estimation. The paper also suggested that when p=infinity, the confidence set estimation and the error rate attains the optimum. However, again as the paper pointed out, LCB is an instantiation of the generic approach when p=infinity, thus is already optimal. Therefore, the contribution of this paper is mostly about a general framework to unify previous methods.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Qwvf2RbLiq_", "reviewer": "Reviewer_9CB2", "summary": "The paper studies batch (offline) learning in linear contextual bandits (with a realizability assumption that the expected reward of a context and an action is a linear function of their feature mapping given to the learner). \n\nThey analyze a class of pessimistic learning rules indexed by different l_p norms. For each learning rule, the learning rule is to (1) build a confidence set of the true parameter under l_p norm; (2) pessimistically select the policy that maximizes a lower confidence bound on the expected reward constructed using the confidence set. \n\nThey provide near-optimality analysis of the learning rules and show that the learning rule with l_{\\infty} norm enjoys the best performance guarantee under their analysis. \n\nThe show that each learning rule under a norm is minimax optimal under the specific norm, within a norm-constrained class of contextual bandit instances (instances that are \"easy\" to learn). \n\nThey show that the learning rule under l_{\\infty} nrom is minimax optimal under all norms, while the other learning rules are not. \n\n\n", "questions": "See weaknesses. ", "limitations": "I did not find limitations and potential negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-written and easy to follow. \n\nThey provide instance-dependent and minimax optimality analysis of learning rules under different norms. \n\nThe discussion about the connections to prior works is interesting. \n\nWeaknesses:\n\n1. The proposed learning rules seem to have already been discussed in many existing offline RL literature, as also mentioned by the authors. The methodological contribution seems limited. \n\n2. It would be great if the authors discuss and compare with prior works on offline learning in contextual bandit literature (e.g. [1,2,3] and their follow-ups). \n\n3. The paper lacks empirical evaluation. And I doubt its real-world applicability. In particular, the theoretical analysis of the proposed learning rule relies heavily on a realizability assumption, which might not hold in most of the real-world problems. Also, the minimax optimality analysis is within some benign class of instances, which might not hold in real-world applications. It would be great if the paper shows some empirical evidence that the proposed learning is better compared with other rules and existing works [1,2,3]. \n\n\nSome minor issues:\nwhy in eq (6) we use \\min (instead of \\inf) and in eq (7) we use \\sup? \n\n[1] Dudík, Miroslav, John Langford, and Lihong Li. \"Doubly robust policy evaluation and learning.\" ICML (2011)\n[2] Bottou, Léon, et al. \"Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising.\" Journal of Machine Learning Research 14.11 (2013).\n[3] Swaminathan, Adith, and Thorsten Joachims. \"Counterfactual risk minimization: Learning from logged bandit feedback.\" International Conference on Machine Learning. PMLR, 2015.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6prQjRVcK7E", "reviewer": "Reviewer_hhtZ", "summary": "This paper focuses on offline learning for linear contextual bandits and provides a novel family of pessimistic learning rules that generalizes over the Bellman--consistent pessimism and lower confidence bound strategies. The statistical guarantees established here for this new family of learning rules are proven to be minimax optimal, as the authors also show a lower bound. Last is demonstrated the adaptive minimax optimality property of one of the new learning rules - the extension of the lower confidence bound strategy - with empirical experiments corroborating the theoretical findings.", "questions": "- Could this work be extended to RL?\n- The definition of the policies of interest are only explicitly made in Equation (9), while they should be explicitly defined before Theorem 1.\n- Could the confidence set in Equation (8) and Lemma 1 incorporate more instance-dependent terms in order to get tighter results?\n", "limitations": "The theoretical limitations are adequately addressed. The authors state that the potential negative societal impacts of their work is N/A due to its theoretical nature. It might still be valuable to mention what could go wrong if the suggested algorithms were actually deployed. \n", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Presentation: the problem is well introduced and the main results are clearly presented\n- Impact: this paper provides a minimax optimal solution to the problem of offline linear contextual bandits. This new family of learning rules generalizes well-known approaches.\n- The paper is technically sound.\n- The experiments seem to nicely support the theoretical findings\n\nWeakness: No instance dependent results. It seems like the instance dependent literature for linear is growing (even for RL, see [1,2]) and it would have been to see a result of that form \n\n[1] Zanette, A., Kochenderfer, M. J., and Brunskill, E. Almost horizon-free structure-aware best policy identification with a generative model. \n[2] Wagenmaker, A., Simchowitz, M., and Jamieson, K. Beyond no regret: Instance-dependent pac reinforcement learning\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept