The Pareto Frontier of model selection for general Contextual Bandits
Authors: Teodor Vanislavov Marinov
Julian Zimmert
Venue: NeurIPS 2021 Poster (2021)
Keywords: Contextual bandits
Pareto frontier

Abstract: Recent progress in model selection raises the question of the fundamental limits of these techniques. Under specific scrutiny has been model selection for general contextual bandits with nested policy classes, resulting in a COLT2020 open problem. It asks whether it is possible to obtain simultaneously the optimal single algorithm guarantees over all policies in a nested sequence of policy classes, or if otherwise this is possible for a trade-off  $\alpha\in[\frac{1}{2},1)$ between complexity term and time: $\ln(|\Pi_m|)^{1-\alpha}T^\alpha$. 
We give a disappointing answer to this question. Even in the purely stochastic regime, the desired results are unobtainable. We present a Pareto frontier of up to logarithmic factors matching upper and lower bounds, thereby proving that an increase in the complexity term $\ln(|\Pi_m|)$ independent of $T$ is unavoidable for general policy classes.
As a side result, we also resolve a COLT2016 open problem concerning second-order bounds in full-information games.

The Pareto Frontier of model selection for general Contextual Bandits
Teodor Marinov* Google Research tvmarinov@google..o com
Julian Zimmert Google Research
zimmert@google. com
Abstract
Recent progress in model selection raises the question of the fundamental limits of these techniques. Under specific scrutiny has been model selection for general contextual bandits with nested policy classes, resulting in COLT2220 open problem. asks whether possible to obtain simultaneously the optimal single algorithm guarantees over all policies in nested sequence of policy classes, if otherwise this is possible for a trade-off a E 1 1) between complexity term and time: In In (I 1= We give a disappointing answer to this question. Even in the purely stochastic regime, the desired results unobtainable. We present a Pareto frontier of up to logarithmic factors matching upper and lower bounds, thereby proving that increase in the complexity term In( independent of T is unavoidable for general policy classes. As a side result, we also resolve COLT2016 open problem concerning second-order bounds in full-information games.
Introduction
Contextual multi-armed bandits fundamental problem in online learning [Auer al., 2002, Langford and Zhang, 2007, Chu et al., 2011, Abbasi- Yadkori et al., 2011]. The contextual bandit problem proceeds as repeated game between learner and an adversary. At every round of the game the adversary prepares pair of a context and a loss over an action space, the learner observes the context and selects action from the action space and then observes only the loss of the selected action. The goal of the learner is to minimize their cumulative loss. The performance measure, known regret, is the difference between the learner's cumulative loss and the smallest loss of fixed policy, belonging to an apriori determined policy class, mapping contexts to actions. Given single contextual bandit instance with finite sized policy class, the well-known Exp4 algorithm [Auer al., 2002] achieves the optimal regret bound of O the complexity of the policy class, therefore a learner might want to leverage "guesses" about the optimal policy. Given policy classes II, .... C Ha,, learner would ideally suffer regret scaling only with the complexity of II,,, the smallest policy class containing the optimal policy x". While these kind results are obtainable in full-information games, in which the learner gets to observe the loss for all actions, they are impossible for multi-armed bandits [Lattimore, 2015]. In some aspects, contextual bandits are an intermediate setting between full-information and multi-armed bandits and it is unknown if model selection is possible. Foster et al. [2020b] stated model selection in contextual bandits as a relevant open problem in COLT2020. Any positive result for model selection in contextual bandits would imply general way to treat multi-armed bandits with switching baseline. Furthermore any negative result is conjectured to implicate negative results on another unresolved open problem second order bounds for full-information games [Freund, 2016).
(( KT [I]). Regret guarantees degrade with
In this paper, we give fairly complete answer the questions above.
Author was at Johns Hopkins University during part of this work.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

P.I. We provide a Pareto frontier of upper bounds for model selection in contextual bandits with finite sized policy classes.
P.2 We present matching lower bounds that shows that our upper bounds are tight, thereby resolve the motivating open problems [Foster et al., 2020b].
P.3 We present a novel impossibility result for adapting to the number of switch points under adaptive adversaries [Besbes et al., 2014].
P.4 We negatively resolve an open problem on second order bounds for full-information [Freund, 2016].
Related work. A problem closely related to contextual bandits with finite policy classes are linear contextual bandits. Model selection in linear contextual bandit problems has recently received significant attention, however none of these resuls transfer to the finite policy case. In the linear bandits problem the m-th policy class is subset of Rdm and the losses (,)(),,, т E mm are linear, that is (,,)(z) (8m: 6m (a,, π (z))) + 5. Here @m X' A + Rdm is feature embedding mapping from context-action pairs into Rd Ç is mean-zero nau-Gaussian noise with variance proxy equal to one and Om E TT is an unknown parameter.
Foster et al. [2019] assume the contexts are also drawn from unknown distribution
I ~ 'D and propose an algorithm which does not incur more than Ó (i+T)))) ) where 73 is the smallest eigenvalue of the covariance matrix of feature embeddings Σ EznD M EneA (1, ())M((1 a)" Pacchiano et al. [2020b] propose a different approach based on the corralling algorithm of Agarwal et al. [2017] which enjoys Odd. vT) regret bound for finite action sets and Ö vT) bound for arbitrary action sets A. Later, Pacchiano et al. [2020a] design an algorithm which enjoys gap- sup-dependent guarantee under the assumption that all of the miss-specified models have regret R,(t) 2 At, Vt E [T]. Under such an assumption, the authors recover a regret bounds of the order Ödd,- V + AA) for arbitrary action sets. Cutkosky et al. [2020] also manage to recover the (d2- VT) and Odd.. vT) bounds for the model selection problems through their corralling algorithm. Ghosh et al. [2021] propose an algorithm which enjoys Ô di in the finite arm setting, where 7 = min (00m= 10m- entry of 6m. Their algorithm also enjoys a similar guarantee for arbitrary action sets with vdm-TT TT replaced by dmm VT. Zhu and Nowak [2021] show that it is impossible achieve the desired regret guarantees of / Vd T without additional assumptions by showing a result similar to the one of Lattimore [2015]. The work of Lattimore [2015] states that in the stochastic
7 + Vnn-T
0} is the smallest, in absolute value,
bandit problem it is impossible to achieve regret to a fixed arm, without suffering at least K /VT regret to different arm.
Chatterji et al. [2020] study the problem of selecting between an algorithm for the linear contextual bandit problem and the simple stochastic multi-armed bandit problem, that is they aim achieve simultaneously a regret guarantee which is instance-dependent optimal for the stochastic multi-armed bandit problem and optimal for the finite arm stochastic linear bandit problem. The proposed results only hold under additional assumptions. More generally, the study of the corralling problem, in which we are presented with multiple bandit algorithms and would like perform as well the best one, was initiated by Agarwal et al. [2017]. Other works which fall into the corralling framework are that of Foster et al. [2020a] who study the speciffee linear contextual bandit problem, that is the observed losses are linear up to some unknown e miss- spiecisssciiiininnnn and the work of Arora et al. [2021] who study the corralling problem for multi- stochastic bandit algorithms.
Our work also shows an impossibility result for the stochastic bandit problem with non-stationary re- wards. Auer [2002] first investigates the problem under the assumption that there are L distributional changes throughout the game and gives an algorithm with a ((VKLT) dynamic regret² bound, under the assumption that L is known. Auer et al. [2019] achieves similar regret guarantees without assum- ing that the number if switches (or changes) of the distribution is known. A different measurement of switches the total variation of changes in distribution V/ = D [E[{]] I]l Multiple
works give dynamic regret bounds of the order ((V) (hiding dependence on the size of the policy class) when Vr is known, including for extensions of the multi-armed bandit problem like
In dynamic regret the comparator is the best action for the current distribution.

---

General CB
Upper bound
Lower bound
adaptive adversary
(maxx C
VMKT)
Q(max {C,
1m
KT
e
ln(K]
oblivious
(maxx C
VMKT)
1l [[
JvT)
e
adversary
stochastic
S-switch
Upper bound
Lower bound M(max[C, T (VKT))
adaptive
O(max[C, {(KT)
adversary
oblivious
O(VSKT + 7
Q(VSKT)
adversary
stochastic
O(VSKT)
((VSKT)
Table I: Overview of our results. Our novel contributions are in bold; lower bounds only hold if the expressions are not exceeding O(T). The stochastic/oblivious lower bounds hold only for proper algorithms.
contextual bandits and linear contextual bandits [Besbes et al., 2014, Luo et al., 2018, Besbes et al., 2015, Wei al., 2017]. Cheung al. [2019], Zhao et al. [2020] further show algorithms which enjoy (hiding dependence on dimensionality) for
a parameter free regret bound the order O(V))//7 the linear bandits problem. The lower bound in Table might seem to contradict such results. In Section 5.1 we carefully explain why this is not the case.
Finally, our lower bounds apply the problem of devising algorithm which simultaneously enjoys a second order bound over any fraction of experts. Basa-Bianchi et al. [2007] first investigate the problem of second order bounds for the experts problem, in which the proposed algorithm maintains a distribution Pr over the set K experts, during every round the game. The experts are assumed
to have stochastic losses 4, and the work shows an algorithm with Ö ΣTT Vi-p, [ log K) regret guarantee. Chaudhuri et al. [2009], Chernov and Vovk [2010], Luo and Schapire [2015], Koolen and Van Erven [2015] study a different experts problem in which the comparator class for the regret changes from the best expert in hindsight to the uniform distribution over the best [eK] experts for an arbitrary positive e. The above works propose algorithms which achieve a Ö(VT log(1/c)) regret bound for all simultaneously. Freund [2016] asks if there exists an algorithm which enjoys both guarantees at the same time, that does there exist an algorithm with
regret bound Ö(V Et Vinn [Cr,]] log(1/e)) which holds simultaneously for all positive
Notation.
For any N E N, [N] denotes the set {1,..., N). Ô notation hides holy-logarithmic factors in the horizon T and the number of arms K but not in the size of the policy classes [T
Problem setting
We consider the contextual bandit problem with general policy classes of finite size. There are K arms and nested policy classes (m ) m=1 where policy æ E Im, ग X - [K] is mapping from an arbitrary context space A' into the set of K arms. The game is played for 7 rounds and at any time f,, the agent observes context 24 E X, selects arm A, E [K] and observes the loss 4,,,, from an otherwise unobserved loss vector & [K]. We measure algorithm's 's performance in terms of pseudo-regret, which is the expected cumulative regret the player against following a fixed policy in hindsight
T Σ
Reg max E
le b
Environments. We distinguish between stochastic environments and oblivious or adaptive adver- saries. In stochastic environments, there unknown distribution Px, Q such that 2, ~ Px and

---

4 ~ Q(112)) are i.d. samples. In the adversarial regime, the distributions can change over time, i.c. It Px.1. Q.(- When the choices are fixed the beginning of the game, the adversary called oblivious, while an adaptive adversary can chose Px,t: Q based on all observations up to time 1.
Often the soocasttic-dveersane hybrid problem has been studied with adversarially chosen context but stochastic losses. In our work, all upper bounds hold in the stronger notion where both the losses and the contexts are adaptive, while the lower bounds hold for the weaker notion where only the contexts are adaptive.
Open problem [Foster et al., 2020b]. The regret upper bounds for all regimes introduced above for fixed policy class II of finite size are of the order ((vIn((II)) KT) and can be achieved by the Exp4 algorithm [Auer et al., 2002]. The question asked by Foster et al. [2020b]: For a nested
sequence of policies IT, TT2 .... M., there universal [ 1) such that regret bound of
Reg(T, mm = PolyLog(K, (, M) D'=077)
(1)
obtainable for all E [M] simultaneously?
W.l.o.g. we can assume that M OIn In(()))) (In(T)). Otherwise we take subset of policy classes that includes M and where two consequent policy classes at least square in size. Due to nestedness, any guarantees on this subset of models imply up to constants same bounds on the full set.
S-switch A motivating example for studying nested policy classes is the S-switch problem. The context is simply It e [T] and the set of policies given by
T-1 Σ lime F m+t1 S
Iss
the set of policies that changes its action not more than S many times. Any positive result for contextual bandits with finite sized policy classes would provide algorithms that adapt to the number of switch points, since In |w]s| = OSS). To make clear what problem we are considering, we are using Regsw ST) to denote the regret in the switching problem.
Next, we define the class of proper algorithms which choose their policy at every time step indepen- dently of context 2₁. Restricting our attention to such algorithms greatly reduces the technicalities for lower bound proofs in the non-aue -daptivee regimes. The lower bound for this class of algorithms also at the core of the argument for adaptive (improper) algorithms in stochastic environments.
Definition 1. We call an algorithu proper, if at any time t, the algorithm follows follows the recommendation of policy ni E IIM and if the choice of is by the algorithm, is independent of the context Zt.
Example. EXP4 is proper.
The properness assumption intuitively allows us to reduce the model selection problem to a bandit-like problem in the space of all policies M. We give more details in Section 4.2 and Appendix B.3.
3 Upper bounds
In this section, generalize the Hedged-FTRL algorithm [Foster al., 2020a] to obtain upper bound for model selection over a large collection of /T regret algorithms.
Theorem 1. For any C > O, tune Hledged-FRRI over selection of M instances of EXP4 operating on policy classes II.... Iss, such that the following regret bound holds uniformly over all m [M]
Reg IIm) = (max { In [11m
v V

---

Hedged-FTRL. (a, R) -hedgge FTRL, intro- duced in Foster et al. [2020a], is a type of Follow the Regularized Leader (FTRL) algorithm which used as corralling algorithm [Agarwal et al., 2017]. At every round i, the algorithm chooses to play one of M base algorithms (Base)) Base algorithm i is selected with probability He.s, where Or E AM-1 is a distribution over base algorithms determined by the FTRL rule qe = arg minges (q, L where L E R4 is the sum of the loss vectors (ew, /..A./9..M. ). F F
Input: a; R, Top, (op, (Base:)
for 1...., T do
Get M, U,M,, from Top Let BasEM, play the next round and receive A,
Play A, and observe C, Update Base with A.gr/ Update Top with (M, Et)
if 9++1 would violate Eq. (2) then Bias losses by b, to ensure Eq. (2).
Bi) + F(g)/7.
end
AM-1 + I is the end potential induced by the a-Tssllis entropy, 1 is a step size determined by the problem parameters and B, is special bias term which we now explain. Define Pt.m = min (m. min J..m. and initialize Bo,m p. Rm. Here Pt is a vector which tracks the variance of the loss estimators, R is a vector with regret upper bounds for the base algorithms, and S < 91 is threshold depending on the base algorithms. At any time f, after selecting base algorithm M, to play the current action, the top (corralling) algorithm observes its loss and gives as feedback an important weighted loss to the selected base, Mr. Whenever the base played at round / would satisfy Pt+1,M, > Mr the loss fed to the top algorithm adjusted with a bias br such that the cumulative biases track the quantity Pi+1,m Rm. This has been shown to be always possible [Foster et al., 2020a]. The condition for adjusting the biases reads
s=1.
Algorithm 1: Hedged FTRL
Vm E [M] Bo.m
bm.m
1. Rmm.
The condition in Equation 2 is motivated in a similar way to the stability condition in the work of Agar- wal et al. [2017]. Algorithm constructs an unbiased estimator for the loss vector, CM, 4, (4..//9. / and updates each base algorithm accordingly. A similar update is present in the CORRAL algo- rithm Agarwal et al. [2017] which each of the base learners also receives an importance weighted loss. The regret of the base learners is assumed to scale with the variance of the importance weighted losses. This assumption is natural and in practice holds for all bandit or expert algorithms. The scaling of the regret, however, must be appropriately bounded as Agarwal et al. [2017] show, otherwise no corralling or model selection guarantces are possible. Formally, the following stability property is required. If an algorithm B enjoys regret bound R under environment V with loss sequence (4:) then the algorithm is (a,, R)-stable if it enjoys a regret bound of the order [p R under the environ- ment V of importance weighted losses (fe)T-, where Pmax is the maximum variance of the T losses and the expectation taken with respect to any randomness in B. Essentially all bandit and expert algorithms used in practice are (a, Rttbbbl with a S 1/2, e.g., Exp4 is (1/2, v KT In( ([T])))stabll) stable. The bias terms in Algorithm 1 intuitively cancel the additional variance introduced by the importance weighted losses and this why we require the biases to satisfy Equation
Theorem 2. Given collection of base algorithms (Bm))M M= which are (1/2, v T T that is
Vm E [M] :: Regimp (T, B,,) S B[/PTml CnTT,
and any C 2 0, then the regret of (1/2, R, 3e-hddged Tsallis-Inf with Rm = VEmT, Bm = 1 M max(1, (1, e..
e² satisfies simultaneous regret of
Vm E [M] Reg(T, Bm) < 2 max {e, Cm (m) Tee BVTT + V2MT.
The analysis follows closely the proof of Foster al. [2020a] and is postponed to Appendix A.
Theorem recovers the bounds of Pacchiano et al. [2020b] for model selection in linear bandits, but holds in more general settings including adaptive adversaries in both contexts and losses. It neither requires nestedness of the policies nor that the policies operate on the same action or context space.
Proof of Theorem 1. The EXP4 algorithm initialized with policy class Im satisfies the condition of Theorem with e.. = O(n [m,,)), as shown in Agarwal et al. [2017]. Hence Theorem is direct corollary of Theorem 2.
D
5

---

Lower bounds
We present lower bounds that match the upper bounds from Section 3 up to logarithmic factors, thereby proving tight Pareto frontier of worst-case regret guarantees in model selection for contextual bandits.
In the first part of this section, we consider a special instance of S-switch with adaptive adversary. The proof technique based on Pinsker's inequality is folklore and leads to the following theorem.
Theorem 3. For any K 3. sufficiently large T, and any algorithm with regret guarantee
Regsw (T, 1) = O(EVKT).
there exists for any number of switches S = (2((2) stochastic bandil problem such that
( (KK.TT)):
Regsw (T, 8) = (T
min
This bound holds even when the agent is informed about the number of switches up time
Since this bound holds even when the agent is informed about when a switch occurs, can restrict the policy class to policies that only switch arms whenever the agent informed about a switch in the environment. This as contextual bandit problem with context X' = [S + 1] and [Ts [
[T policies. Hence Theorem 3 implies lower bound of Reg(T, IIş) = Ω min CIn(K) vKT,T))
In the second part of the section, we consider the stochastic regime. Our lower bound construction non-standard and relies on bounding the total variation between problem instances directly without the use of Pinsker's inequality.
Theorem 4. There exist policy classes II, C II2 with [2 = (2((2), such that if the regret of proper algorithm is upper bounded in any environment by
Reg(T, , [T) = O(EVT).
then there exists an environment such that
Reg(T, (T2) = S2 (maax
=1(max
In [TTa] VT)
E,
e
These theorems directly provide negative answers [Foster al., 2020b].
Corollary 1. There is a E [ 1) that satisfies the regret guarantee of open problem for any algorithm in the adaptive adversarial regime or any proper algorithm in the stochastic case.
Proof. By Theorems 3 and 4, for any
there exists K 3, M 2, Ih 1, [Tp
((ex)(TT)) Assume that Reg(T, I CT = C-T-- where Cr = PolyLog(T). Hence by Theorem 3 and Theorem 4 there exist environments where
Reg(T, (
(CTTa-3 vT) = ( (T)
T
Finally, disprove the open problem in the stochastic case for any algorithm.
Theorem 5. No algorithm (proper or improper) can satisfy the requirements of open problem (1) for all stochastic environments.
We present the high level proof ideas the following subsections and the detailed proof Ap- pendix B.
In Foster et al. [2020b] open problem 2, they ask about model based contextual bandit with realizability. Our lower bound is providing an instance of that.

---

4.1 Adaptive adversary: S-switch(A) Problem
We present the adaptive environment in which model selection fails and the proof Theorem 3.
The adversary switches the reward distribution up to many times, thereby segmenting the time into S + phases (I...., ................................ Ti T1 + L..... T2. ..... Ts:... ..). We denote I, [S + 1] the counter of phases and assume the agent given this information. For each phase 22 E [S]. the adversary selects
an optimal arm (a:) uniformly at random among the first K arms. If S S, the losses i..dd Bernoulli random variables with means
0
for E [K - 1 {az,}
E
E
A
for az for i K
In phase S + 1, all losses are 0 until the end of the game. The adversary decides on the switching points based on an adaptive strategy. switch from phase 8 < + to + oceurs when the player has played Nmax special case of S-switch problem, alternatively contextual bandit problem with [[Ts| K policies.
K-1 times an arm in [K 1] in phase s. We can see this problem either as
1922
The lower bound proof for S-switch( A) relies the following Lemma, which is proven in Ap- pendix
Lemma 1. Let agent interact with K 12 2 2 armed bandit problem with centered Bernoulli losses and randomized best arm of gap A < 8/3 for an adaptive number of time steps N. If the
probability of N Nmax = on the event N 2 Nmax is lower bounded by
K-L7 is at least
2. then the regret after Nmax time-steps conditioned
A N
Reg
max
Informally, this Lemma says that conditioned on transitioning from phase to phase s + 1, the agent has suffered regret Q P(AN Nmax) against arm K during phase
Informal proof of Theorem 3. The adversary's strategy is designed in a way such that at each phase E [S] it only allows the player's strategy to interact with the environment just enough times to discover the best action a. Then new phase begins to prevent the player from exploiting knowledge of a- This ensures by Lemma that the player suffers regret at least ((ANmax) during each completed phase. If an agent proceeds finding o for all phases E [S]. then the regret against the non-switching baseline is Regsw (T, 1) O(Á N.ax 5). By the assumption
the maximum regret of Regsw (T, 1) and an appropriate choice Nmax and A, we can ensure that the agent must fail to discover all at with constant probability, thus incurs regret least Regsw (T' S) Q (() against the optimal S-switch baseline. Tuning A and N max yield the desired theorem. The formal argument with explicit choice of A found in Appendix B.
4.2 Stochastic lower bound
We now present the stochastic environment used for the impossibility results in Theorems and 5. There are à: + environments ( with II, = {mii E [b: U {0}} policies and II, = {mo)- In all environments, we have K = 3 and mo always chooses action 3, while (T;){= are playing an action from (1,2) uniformly at random. (In other words, the context is X' = {1, (1,2]* with or sampled uniformly random and Txx)) 2F..)
In each environment, the losses of actions (1,2) at any time step satisfy f,, = l2 which are conditioned on I; independent Bernoulli random variables, with mean
1 and Vi [A] Es, (e.m)
Ex, [4,1] Es, 2
(1-A).
Action 3 gives constant loss of 1 A in all environments.
Let us unwrap these definitions. Playing either action or action which we call revealing actions, yields full- inllmannormttion of all random variables at time t due to the dependence of l,, 1 l,2 and
7

---

the non ra--oonddmess of f,,, On the other hand, playing action 3 allows only to observe 2,, which has the same distribution in all environments, hence there is no information gained all.
We know from full-information lower bounds that for optimal tuning of the gap, one suffers M VIn(k)T) regret in the policy class ll2, due to the difficulty of identifying the optimal arm. For smaller regret in policy class II, one needs confirm or reject the hypothesis & faster than it takes to identify the optimal arm. Existing techniques do not answer the question whether this is possible, and our main contribution of this section to show that the hardness of rejecting Eg is of the same order as identifying the exact environment.
For the remaining section, it will be useful to consider reparametrization of the random variables. Let 2, E {0. 1}* be the losses incurred by the policies (T; mT))/=n 2,, = (.:) We can easily see that 2, together with F2,1 is sufficient to uniquely determine E, and x4- Furthermore, 2n is always vector of independent Bernoulli random variables, which are independent of ø ". In environments (E.) the i-th component is a biased Bernoulli, while all other components have mean J. In Eo. no component is biased. As before, 2r,1 does not provide any information since its distribution conditioned on 2t is identical in all environments (see Lemma 4 in Appendix B for formal proof).
Under this reparameterization and ignoring non-informative bits of randomness, the problem of distinguishing Eg from {E now looks as follows. For time steps t = 1,... T. decide whether to play revealing action and observe 2 (potentially by taking it into account). Use observed (Zr,))== to distinguish between the environments. Proper algorithms simplify the problem even further, because selecting Tr, independently of xe implies that the decision of observing = is also independent of ze (any policy except To allows to observe 2, under any context). Hence for proper algorithms, we can reason directly about how many samples 2; are required to distinguish between environments. This problem bears similarity the property testing of dictator functions [Balcan et al., 2012] and sparse linear regression [Ingster et al., 2010 however, there is no clear way to apply such results our setting.
The following lemma shows the difficulty of testing for hypothesis Eg-
Lemma 2.
Let A < 1. k 2 22 + 1, N S 1n(k-1) and A 2 J.- If the algorithm chooses whether to reveal zt independently of xi and if the total times 2t is revealed bounded by N a.s. then for any measurable event F. it holds that
20
17
1
min P.. (E) PPE (E) [E
Vk
The proof of Lemma 2 is deferred to Appendix B.3. The high level idea is to directly bound the TV between min Pe, and PP over the space of outcomes of (zt, > by utilizing Berry-Essen's inequality instead of going through Pinsker's inequality. This step is key to achieve a dependence on k in the bound.
For readers familiar with lower bound proofs for bandits and full-information, this Lemma should not come at huge surprise. For a T Troound full-information game, it tells us that we can bias single arm up A= I2( In(k)/T), without this being detectable. This directly recovers the well known lower bound of AT 12( (2V/in (I) for full-information via the argument used for bandit lower bounds. However, this result goes beyond what is known in the literature. We not only show that one cannot reliably detect the biased arm, but that one cannot even reliably detect whether any biased arm is present at all. This property is the key to showing the lower bound of Theorem 4.
Informal proof of Theorem 4. Under enviromment Eg, observing z, for n time-steps incurs a regret of Rege, (1) Q (An).. Using the assumption the regret Regg, (T, II1) and Markov inequality, we obtain an upper bound N on the expected number of observations, which holds with probability 2. We can construct an algorithm A that never observes more than N samples, by following algorithm A until it played N times revealing action and then commits policy To (action 3). Since the algorithm A is proper, we can define Z = (2,,) as the observed z's during time т, where the algorithm plays revealing action. For the revealed information generated by A, tune the
'We want to emphasize that 2t is only independent 2t.1, not independent of the full vector 2t. $ 'The setting of [Ingster et al.. 2010] is different from our setting as they consider an asymptotic regime where both feature sparsity and dimensionality of the problem go to infinity, while for us the sparsity is fixed one.
8

---

remaining parameters such that the conditions of Lemma 2 are satisfied. Let E be the event that A
plays exactly N times a revealing action (i.e. A plays at least N time the revealing action), then E
happens with probability - (I(1) under min Pe, (.). Thus, there exists an environment E [A] such that A plays less than V times an action in {1, 2} with constant probability, which incurs regret
of Regg, (T, = ((AT). The theorem follows from tuning A and N, which is done formally in Appendix B.
Improper algorithms. Even though we are not able to extend the lower bound proof uniformly over all values C and & to improper algorithms, we can still show that no algorithm (proper or improper) can solve the open problem (1) for stochastic environments.
The key the following generalization of Lemma 2, which proven in the appendix.
Lemma 3. Let A S J. k 2 e0 +1, S
| and A 2 J. If the total number of times 2 is revealed is bounded by N a.s. then for any measurable event holds that
177N
min Pe, (B) iE[A]
Vk
This holds even if the agent can take all contexts (z+){=z and previous observations into account when deciding whether to pick revealing action at any time-step.
Informal proof of Theorem 5. The proof is analogous to Theorem 4, however use Lemma 3 to bound the difference in probability of E under & and & The key is to find a tuning such that the RHS of Lemma 3 does not exceed }. Note that this is of order exp(O(I(TT)N)
()In(k))) Let A = ((). then the requirement on Regg, (T, 111) yields N ( Setting k = O ((exp(I for any e E (0, 1 - a), then it follows immediately that the RHS in Lemma 3 goes to 0 for T + co. Following the same arguments as Theorem 4, there exists a sufficiently large T up from which there always exists an environment (E)) such that the regret is linear in T, thereby contradicting the open problem. The formal proof is deferred Appendix B
Implications
The relevance of open problem Eq. (1) has been motivated by its potential implications for other problems such as the S-switch bandit problem and an unresolved COLT2016 open problem on improved second order bounds for full-information. Our negative result for Eq. (1) indeed lead the expected insights.
5.1 S-switch
Our lower bound in the adaptive regime shows that adapting to the number of switches is hopeless if the timing of the switch points is not independent of the players actions. Any algorithm adaptive to the number of switches the regime with oblivious adversary must break in the adaptive case, which rules out bandit over bandit approaches based on importance sampling [Agarwal et al., 2017]. The successful algorithm proposed in Cheung et al. [2019] is using a bandit over bandit approach without importance sampling. Nonetheless, all components have adaptive adversarial guarantees. The algorithm splits the time horizon into equal intervals of length L. It initializes EXP3 with In(2") arms, corresponding to grid of learning rates. For each epoch, the EXP3 top algorithm samples an arm and starts a freshly initialized instance of EXP3.S using the learning rate corresponding to the selected arm. This instance is run over the full epoch of length L. collects the accumulated losses Leum = DL_ l of the algorithm and feeds the loss Lsum/L L to the EXP3 top algorithm.
If all algorithms in the protocol enjoy guarantees against adaptive adversaries, why do bandit over bandit break against adaptive adversaries? Adaptive adversaries are assumed to pick the losses E independent of the choice of arm A₁ of the agent at round t. In the bandit over bandit protocol, the loss of the arm of the top algorithm dependents on the losses that the selected base suffers in the epoch. An adaptive adversary can adapt the losses in the epoch based on the actions of the base algorithm, that means the loss f, not chosen independent of the action A,, Hence the protocol broken and the adaptive adversarial regret bounds do not hold.

---

5.2 Second order bounds for full information.
In an unresolved COLT2016 open problem. Freund [2016] asks if it possible to ensure a regret bound of order
Reg. Ô
Σ
V Vinn /C In(
against the best proportion of policies simultancously for E. We go even step further and show that the lower bound construction from Section 4.2 directly provides negative answer for any < 1 to the looser bound
(1
T Σ (Vinpileell Ta) In(
Reg. =
(4)
Theorem 6. algorithm satisfying Eq. (4r a < implies the existence of a proper algorithm that violates the lower bound for the counter example in the proof of Theorem 4.
Theorem 6 has the following interpretation. For any fixed a [0, 1), there no algorithm which enjoys a regret upper bound as in Equation 3 for all problem instances s.t. Σ/= (Vinpe (l,))) = not hope for polynomial improvement, in terms of time horizon, over the existing bound of Ö( D(yT(in (ln())))) The detailed proof is found in Appendix B. The high level idea is to initialize the full-information algorithm satisfying Eq. (4) with sufficient number of copies of the baseline policy To and feed importance weighted losses of the experts (i.e. policies) that algorithm.
@(7%). This implies
As mention in Section the a is obtainable. Our reduction relates the adaptation variance to the model selection problem. As in Eq. (1), a the trade-off hetween time and complexity. merely allows recover the trivial O(T) bound for model selection, and hence does not lead to a contradiction.
An algorithm satisfying Eq. (4) with
Conclusion
We derived the Pareto Frontier of minimax regret for model selection in Contextual bandits. Our results have resolved several open problems [Foster et al., 2020b, Freund, 2016].
Acknowledgments and Disclosure of Funding
We like thank Haipeng Luo and Yoav Freund for discussions about our lower bound proofs. We thank Tor Lattimore for pointing us to the technicalities required for bounding the total variation of improper algorithms.
References
Yasin Abbasi-Yadkon Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320, 2011.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. 2017.
Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Corralling stochastic bandit algo- rithms. In International Conference on Artificial Intelligence and Statistics, pages 21 21-2221. PMLR, 2021.
Peter Auer.
Using confidence bounds for exploitationnexxlloaiiin trade-offss Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1), 2002.
10

---

Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pages 158.15.. PMLR, 2019.
Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active property testing. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 21-30. IEEE, 2012.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic culti-arrmd--aane problem with non- stationary rewards. Advances neural information processing systems, 27:199-2000 2014.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 63(5):1227-1248 2015.
Esseen Carl-Gustav. On the liapunoff limit of error in the theory of probability. Arkiv for matematik, astronomi och fysik, A: 1-19, 1942.
Nicolo Cesa-Bianche Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice. Machine Learning, 66(2)3211335, 2007.
Niladri Chatterji, Vidya Muthukumar, and Peter Bartlett. Osom: A simultaneously optimal algorithm for multi armed and linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages 1844-1854, PMLR, 2020.
Kamalika Chaudhuri, Yoav Freund, and Daniel Hsu. A parameter-free hedging algorithm. arXiv preprint S.Kiv:090332851,, 2009.
Alexey Chernov and Vladimir Vovk. Prediction with advice of unknown number of experts. arXiv preprint arXiv: 0475, 2010.
Wang Chi Cheung, David Simchi-Levi, and Ruíhao Zhu. Learning to optimize under non-stationariiy, In The 22nd International Conference Artificial Intelligence and Statistics, pages 1079-1087. PMLR, 2019.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings, 2011.
Ashok Cutkosky, Abhimanyu Das, and Manish Purohit. Upper confidence bounds for combining stochastic bandits. arXiv preprint 13Xiv:2012..3115, 2020.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits.
arXiv preprint arXiv: 1906.0051, 2019.
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33, 2020a.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Open problem: Model selection for
contextual bandits. In Conference on Learning Theory, pages 3842-3846. PMLR, 2020b.
Yoav Freund. Open problem: Second order regret bounds based on scaling time. In Conference Learning Theory, pages 1651-1654. PMLR, 2016.
Avishek Ghosh, Abishek Sankararaman, and Ramchandran Kannan. Problem-complexity adaptive model selection for stochastic linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 1396-1404. PMLR, 2021.
Yuri I Ingster, Alexandre B Tsybakov, and Nicolas Verzelen. Detection boundary in sparse regression. Electronic Journal of Statistics, 4: 1:446615526, 2010.
Wouter M Koolen and Tim Van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Learning Theory, pages 1155-1175. PMLR, 2015,
John Langford and Tong Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96-1, 2007.

---

Tor Lattimore. The pareto regret frontier for bandits. arXiv preprint arXiv:1511.00048 2015.
Haipeng Luo and Robert E Schapire. Achieving all with no parameters: Adaptive normalhedge. arXiv preprint arXiv: 1502.0534, 2015.
Haipeng Luo, Chen- Yu Wei, Alckh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pages 1739-1776. PMLR, 2018.
Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett. Regret bound balancing and elimination for model selection in bandits and rl. arXiv preprint arXiv:2012. 13045,, 2020a.
Aldo Pacchiano, My Phan, Yasin Abbasi- Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and
Csaba Szepesvari. Model selection in contextual stochastic bandit problems. arXiv preprint arXiv:2003.01704, 2020b.
Ilya Tyurin. New estimates of the convergence rate in the Iyapunov theorem. arXiv preprint arXiv:0912.0726, 2009.
Chen-Y Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Tracking the best expert in non-stationary stochastic environments. arXiv preprint arXiv: arXiv:1712.00578. 2017.
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 746-755. PMLR, 2020.
Yinglun Zhu and Robert Nowak. Pareto optimal model selection linear bandits. arXiv preprint arXiv:2/02.06593, 2021.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1 2021.
12


Reviews:
[{"review_id": "T_Otjl-3UlN", "reviewer": "Reviewer_d1Ft", "summary": "This paper studies the model selection problem in contextual bandits. Lower bounds for the model selection problem, the switching rewards problem, and the second-order bound in the full-information game are provided, which resolve several open problems.", "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": "Lower bounds established in this paper resolve several open problems, i.e., impossible results for model selection under bandit feedback, impossible results for adapting to the number of switches in an adversarial setting, and the second-order bound for an \\epsilon portion of experts in the full information setting. I believe these results are important to the community. Although I didn't carefully check the proofs, the theoretical results stated in the paper make sense to me.\n\nOne minor drawback is that the lower bound for the stochastic setting is with respect to proper algorithms (Definition 1). However, the statements made by the authors (line 276-290) is compelling to me.\n\n====after rebuttal====\n\nI will keep my score at 8. However, I would like to see the clarification questions raised by Reviewer tzvm to be addressed in the next version of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As discussed in the checklist section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "CIgHzvweAMf", "reviewer": "Reviewer_KX4F", "summary": "This paper studies the model selection for contextual bandits. It approaches two open problems. One is a COLT2020 open problem of Foster et al, which askes if there exists a constant such that a regret bound (1) holds for all m \\in [0,M] simultaneously for a nested sequence of a finite set of policies m = 1, ..., M . The other one is a COLT2016 open problem of Freund asking if there is an algorithm for the online full feedback problem with adversarial losses that achieves \\sqrt{V_T logK} regret, where V_T is the cumulative variance across experts. The main claim of the paper is negative answers on both open problems. ", "questions": "", "limitations": "", "rating": 5, "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": "Before discussing the paper's results and methods, my main caution is that the paper is not written so that the ideas can be directly understood from the text. First of all, it feels that a solid block of definitions is missed before page 5. For example, on page 5, the Algorithm 1 and variables in the text appear suddenly and are not defined later in the paper, and there is no reference to other papers where it could be found. \n\n\nRegarding the stated results, looking at the proof of Theorem 5, I do not get where the loss estimate comes from, especially since no loss estimate is required in a full information setting. \n\nI put my Confidence score 3 as I don't get many claims in the paper because there is no definition for many variables. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "3ma5UEikBox", "reviewer": "Reviewer_tzvm", "summary": "The paper studies a COLT 2020 open problem on model selection for contextual bandits (Foster et al. 2020b). The paper presents strong lower bounds which are claimed to hold for all algorithms in the adaptive adversarial regime and hold for \"proper\" algorithms in the stochastic regime. If the lower bounds are true, then they would lead to the following consequences:\n1.  The paper resolves the open problem of Foster et al. (2020b) by providing a negative answer. \n2.  As a byproduct, the paper resolves a COLT 2016 open problem on second-order bounds for full-information online learning (Freund 2016).\n\nFor the model selection problem, the paper also provides a matching upper bound, thus gives a complete characterization of the pareto frontier of model selection for contextual bandits. The paper also discusses the implications to the $S$-switch non-stationary bandit problem.", "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": "========== After rebuttal\n\nI have read the authors' reparametrization argument in their response, which seems like a clever way to simplify the outcome space, and seems to address my major concern. After adding this argument, the lower bound proof implicitly utilizes the component-wise independence of $x_t$ in a substantial way, which seems to be crucial. While I may check more details later, I believe that the proof makes sense (after adding the non-obvious reparametrization argument which was completely missing in the original version). I thus believe that the paper makes significant contribution to the literature and would like to change my score. While I strongly recommend acceptance based on the theoretical contribution, I hope that the authors can add the missing arguments to the main text and spend time improving the presentation, as the original submission is very difficult to understand.\n\n========== Original review\n\nThe paper considers a challenging problem; if the claimed results are true, then the paper would definitely be a breakthrough in this field. I carefully read the paper, and spent lots of time verifying the results. I have a mixed feeling on this paper. On the one hand, the paper seems to contain several interesting and potentially important ideas. On the other hand, I have a major concern on the soundness of a main (and in my opinion the most important) result; see the \"major concern\" part for details. As a result, I cannot give a good score. However, if the author can convince me that there is no issue, then I would definitely be happy to give a high score.\n\nBy the way, the writing of the current paper is not good: there are many typos and the main technical ideas are somehow hard to follow (although I am familiar with the problem of model selection for contextual bandits, I had to figure out and fill in lots of details on my own). Regardless of whether this paper can be accepted, I hope that there can be a significant improvement on writing if there is a next version.\n\n----- Major concern\n\nIn my opinion, the stochastic lower bound in Section 4.3 is the most important result of this paper. While other results including the upper bounds in Section 3 and the adaptive adversarial lower bound in Section 4.1 are also interesting, they are not as exciting as the stochastic lower bound (the upper bounds are obtained by applying and modifying existing techniques, while the adaptive adversarial lower bound is more restrictive compared with the stochastic lower bound). Therefore, I paid the most attention to the stochastic lower bound.\n\nWhile requiring a \"proper\" algorithm is definitely not a weak condition (as it precludes many interesting algorithms like the $\\epsilon$-greedy algorithm), this is not a problem for me as a lower bound for proper algorithms is already sufficient to imply a strong lower bound for Freund's COLT 2016 problem. I would thus be willing to give the paper a high score as long as Theorem 4 is correct.\n\nMy major concern is that the current version of Lemma 2 is not sufficient to support Theorem 4. In particular, since the proof of Lemma 2 implicitly assumes that the considered event is defined on the space of $Nk$ Bernoulli random variables (see line 501) which is the space of all loss vectors, the event $E$ appearing in the statement of Lemma 2 can only be an event completely determined by the realizations of loss vectors (otherwise $E$ would be non-measurable). As a result, $E$ cannot be an algorithm-dependent event in general, as an algorithm can make decisions based on not only the observed losses but also the *observed contexts* --- while the author does assume a “proper” algorithm, being proper only means that the algorithm cannot use $x_t$ to decide $\\pi_t$ (by the way, there are also some issues with the current definition of being \"proper\"; see the \"other concerns\" section), but does not mean that the algorithm cannot use $x_1,\\dots,x_{t-1}$ to decide $\\pi_t$. As a result, the current proof of Theorem 4 seems to be problematic --- since the event $E$ defined in the proof of Theorem 4 is algorithm-dependent (which means that the event depends on the *realizations of contexts*), it is not a measurable event required by Lemma 2, so Lemma 2 does not tell anything about $E$. In other words, since the current proof of Lemma 2 crucially relies on the fact that $E$ only depends on the *realizations of loss vectors*, it seems to me that the author did not really prove a lower bound for all \"proper algorithms\", but proved a much weaker lower bound which only holds for all \"algorithms that cannot observe contexts at all\" --- this makes the actually proved lower bound not interesting as almost all reasonable contextual bandit algorithms rely on the use of context information (otherwise the problem is not \"contextual\" and is more similar to semi-bandits or bandits with many arms). I also spent quite some time thinking about the current main technique used to prove Lemma 2 (i.e., the Berry-Essen-based argument), and find it difficult to extend to the \"normal\" case where the algorithm can use the information of contexts. In particular, since Berry-Essen only holds for *independent* random variables, the current proof technique critically relies on the fact that \"at time $t$, the loss observed by policy $\\pi_1$ and the loss observed by policy $\\pi_2$ is independent\". However, if the algorithm can observe $x_t$, then this independence does not hold conditional on the observation of $x_t$ --- while being proper might suggest that the algorithm would not use $x_t$ to decide the policy used in round $t$, the algorithm can always use the information of $x_t$ and $\\ell_{t,A_t}$ at round $t+1$, so the current technique based on independence might be insufficient to address the challenge.\n\nI make two additional comments. First, if the author cannot address the issue that I state above, then the claim that Freund's COLT 2016 open problem is solved by the paper is false. Note that the algorithm constructed by the author in Appendix B.2 does use the realization of historical contexts to decide the policy used at round $t+1$ (see line 526), so this algorithm does not violate the actual lower bound that the author is able to prove in Theorem 4. Second, while I might misunderstand something, I feel the current proof of the lower bound extremely hard to follow, as the author does not really clearly specify the probability spaces when trying to prove \"change of measure\"-type results --- in my opinion, any rigorous proof should be clear about key definitions, and the current writing of the proof requires significant improvement.\n\n----- Other concerns\n1. Definition 1: The current definition of a \"proper\" algorithm is a little problematic. The author should add a restriction that $\\pi_t\\in\\Pi_M$ to ensure that this definition is meaningful; otherwise, any algorithm can satisfy this definition --- if $\\pi_t$ is arbitrary, then any algorithm can be thought as a procedure which sequentially selects $\\pi_t$ independent of $x_t$.\n2. Line 526: The author should try to avoid using $x_{t,i}$ as a notation for the realized loss, as $x_t$ also stands for a context.\n3. Lines 503-503: $(1-\\Delta)$ is a typo and should be changed to $(1+\\Delta)$.\n4. Line 517: Since the author is trying to bound the distance between the measures induced by ${\\mathcal{E}_0}$ and ${\\mathcal{E}_1}$, the current TV distance must be a typo (as it involves $\\mathcal{E}_1$ and $\\mathcal{E}_2$). Also, it should not be TV distance. There must be some constraints as specified in the earlier parts of the proof.\n5. Line 518: there is a typo on the place where $\\Delta^2$ appears.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have specified my concerns above, which may make the current version of the paper fail to obtain the claimed results. That being said, if the author can convince that there is no issue in the current version, then I would be very willing to give a high score.\n\nBy the way, I spent some time thinking about the construction for the stochastic lower bound, and cannot come up with a model selection algorithm which overcomes this hard instance. While I think that the current proof techniques may be not sufficient to lead to the desired result, I feel that the author is in fact in the right direction of constructing hard instances, and it is possible that this instance indeed leads to the desired lower bound (with more advanced proof techniques).", "review_text": "", "extra_scores": {"ethical_concerns": "This paper is theoretical in nature and I do not foresee any immediate societal impacts.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "14"}, "extra_text": {}}, {"review_id": "1NDOPchWMm", "reviewer": "Reviewer_9QgL", "summary": "The paper considers a model selection problem in contextual bandits, and resolve a few open questions regarding the achievable regret bounds. For finite sized policy classes, a Pareto frontier of upper bounds for model selection is provided. With an additional assumption of the algorithms being proper, matching lower bounds are provided as well. The paper also considers the case of adaptive adversarial problems, and discuss the challenges involved. \n\nThe paper is well written with clear context and literature overview. While the algorithmic contribution is incremental, the proof techniques for the lower bounds are interesting and add value to the literature.     ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The related literature section can be improved by including the definitions and intuition behind the symbols used in regret expressions. \n\nAlso, it would be useful to include the precise statements of the open problems in introduction, and what are the challenges involved. And why is it important to address them. \n\nQuestions:\n1. Does the policy class include situations where the optimal policy can outperform a policy that plays the optimal fixed arm? \n2. In case of adversarial switching, what is the the optimal oracle policy in the regret?  \n3. Suppose there is a known underlying structure that dictates the switching, can this help in relaxing the use of proper algorithms to reduce the technicalities for lower bound proofs? \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " While a motivation for the work is to resolve open problems proposed previously, it would be helpful to give an example application and illustrate the challenges and contribution.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies model selection in contextual bandits (and related problems) and the main result is a lower bound showing that "proper" algorithms cannot obtain the model selection guarantee conjecture in [FKL20]. A consequence is that the second order bound conjecture by Freund in a COLT open problem is not achievable. 

The result is very interesting and after a careful reading along with discussions with the reviewers, we believe it is correct. It is clearly a very important result and represents significant progress in our understanding of online learning and bandit problems. As such the reviewers and I agree the paper should be accepted. 

However, the paper was very hard to read, particularly regarding the proof of the lower bounds. My thoughts/suggestions here:
- I do not think the calculations for wrapping up the proof are very illuminating, e.g., paragraph block labeled "Proof of theorem 3" and "proof of theorem 4." I would prefer to see these replaced with a more qualitative/conceptual explanation of what is going on in the proof. Obviously the calculations should be included in the appendix, but I feel something more conceptual might be helpful to convince a reader.  
- I found it helpful to think about what an algorithm might do to convince myself. For example, for Theorem 3 the algorithm basically has two options: (1) it can choose to play only arm i=K or (2) it can essentially explore uniformly in arms [K-1] for N_max rounds. In the former case, the environment will not switch, which is a contradiction of the algorithm's guarantee, while in (2) it incurs a lot of regret due to Lemma 1. Then you can do the calculation showing how you set \Delta to ensure that both of these cases work out to "confirm" the theorem. This is not a proof but I think provides more intuition than the calculations provided at present. 

For the stochastic lower bound I think it is worth highlighting the following steps (this is also how I understand the proof):
- A proper learner means that there is no "cherry-picking" on contexts, so the statistical lower bound is a "passive learning" lower bound
- The construction is set up so that the lower bound part is essentially full information. In particular the algorithm always knows the loss for action 3 and the realized losses for actions 1 and 2 are coupled so that when you "explore" you are in a full information setting. 
- Thus we can reduce to "standard" full-information passive learning problems. The flavor of such problem is closely related to work on "estimating learnability" [1] or "tolerant testing" [2].  This is a very clever reduction and highlights the role of the proper learning assumption. 
- The specific learning problem being reduced to is essentially the problem of "estimating sparsity" in linear regression (see also the part on learning dictators in [2]), in particular where the sparsity is just 1. In fact I think Lemma 2 is very similar to Theorem 4.5 in [3] (although that theorem/paper is also quite hard to read). It would be great to mention this, so that readers who know this work (or who trust that result) can quickly convince themselves that your result is correct. 
- Actually the results in [3] demonstrate something quite interesting that I think would be worth pointing out here. If I understand it correctly, their results show that a slightly different construction does not completely work for the model selection lower bound. Suppose that the means are given as in your construction, but rather than Bernoulli noise, the noise is Gaussian. Then the statistic \frac{1}{n} \sum_i (\ell_{i,1} - 1/2)^2 actually provides a better testing sample complexity bound than the lower bound in Lemma 2. The key here is that the variances under both hypothesis are the same, so the difference in mean can be detected by looking at the second moment. On the other hand, the Bernoulli construction is closer to the "unknown variance" setting in [3] where the mean difference is washed out by changing the variance. (You can see that in [3] the complexity of the "known variance" and "unknown variance" problems are actually different.) 
- This is more or less how I convinced myself that the proof is correct. 

At a high level, I think it would be great to re-write the lower bound section to capture the following two properties: (1) some hand-wavy way to convince an expert that the result is likely correct, without them having to read the technical details (e.g., by citing related results and maybe following the recipe above), and (2) some intuition based more on algorithmic considerations which I think are easier for readers to understand conceptually.

Finally, regarding proper vs improper algorithms. The reviewer raised a concern here on the actual definition but additionally there are many contextual bandit algorithms that are formally improper (e.g., mixing uniform exploration makes an algorithm improper). Additionally, maybe you can use the lower bound argument on active tolerant testing of dictators in [2] to actually get a lower bound against improper algorithms? Otherwise I think it is fine to conjecture this, but I might slightly tone down the claims about solving the open problems in [FKL20]. If I understand it correctly, the present paper formally resolves Open Problem 1 (and 1a, 1b) in [FKL20] but does not formally resolve open problem 2 due to the proper/improper learning issue. I am aware of some some folklore constructions that critically rely on cherry-picking/active learning/improperness to obtain model selection guarantees in some special cases, so I personally would be more hesitant to make these claims. 

In addition to my suggestions, I hope the authors incorporate feedback from the reviewers, who I know spent quite a lot of time studying the paper and understanding the details. 

References:
1. Kong, Valiant. Estimating learnability in the sublinear data regime. https://arxiv.org/abs/1805.01626
2. Balcan, Blais, Blum, Yang. Active tolerant testing. http://www.cs.cmu.edu/~ninamf/papers/active-testing.pdf
3. Ingster, Tsybakov, Verzelen. Detection boundary in sparse regression. https://arxiv.org/abs/1009.1706
Please also follow references to find the related papers to these. I know there are others. 

Decision: Accept (Poster)