The Pareto Frontier of model selection for general Contextual Bandits
Year: 2021

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 ↵ 2 [ 2 , 1) between complexity term and time: ln(|⇧m|) ↵T↵. 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(|⇧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.

heading: 1 Introduction
text: Contextual multi-armed bandits are a fundamental problem in online learning [Auer et al., 2002, Langford and Zhang, 2007, Chu et al., 2011, Abbasi-Yadkori et al., 2011]. The contextual bandit problem proceeds as a repeated game between a learner and an adversary. At every round of the game the adversary prepares a pair of a context and a loss over an action space, the learner observes the context and selects an 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 as regret, is the difference between the learner’s cumulative loss and the smallest loss of a fixed policy, belonging to an apriori determined policy class, mapping contexts to actions. Given a single contextual bandit instance with finite sized policy class, the well-known Exp4 algorithm [Auer et al., 2002] achieves the optimal regret bound of O( p KT ln(|⇧|). Regret guarantees degrade with the complexity of the policy class, therefore a a learner might want to leverage “guesses” about the optimal policy. Given policy classes ⇧1 ⇢ · · · ⇢ ⇧M , a learner would ideally suffer regret scaling only with the complexity of ⇧m⇤ , the smallest policy class containing the optimal policy ⇡⇤. While these kind of 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 a general way to treat multi-armed bandits with a switching baseline. Furthermore any negative result is conjectured to implicate negative results on another unresolved open problem on second order bounds for full-information games [Freund, 2016].
In this paper, we give a fairly complete answer to the questions above. ⇤Author was at Johns Hopkins University during part of this work.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
P.1 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 a subset of Rdm and the losses `t,⇡(x),⇡ 2 ⇧m are linear, that is `t,⇡(x) = h✓m, m(x,⇡(x))i+ ⇠. Here m : X ⇥A ! Rdm is a feature embedding mapping from context-action pairs into Rdm , ⇠ is mean-zero sub-Gaussian noise with variance proxy equal to one and ✓m 2 Rdm is an unknown parameter. Foster et al. [2019] assume the contexts are also drawn from an unknown distribution x ⇠ D and propose an algorithm which does not incur more than Õ( 1 3 (i ⇤ T )2/3(Mdi⇤)1/3), where 3 is the smallest eigenvalue of the covariance matrix of feature embeddings ⌃ = Ex⇠D ⇥ 1 M P a2A M (x, a) M (x, a)
>⇤. Pacchiano et al. [2020b] propose a different approach based on the corralling algorithm of Agarwal et al. [2017] which enjoys a Õ(di⇤ p T ) regret bound for finite action sets and Õ(d2i⇤ p T ) bound for arbitrary action sets A. Later, Pacchiano et al. [2020a] design an algorithm which enjoys a gap-dependent guarantee under the assumption that all of the miss-specified models have regret Ri(t) t, 8t 2 [T ]. Under such an assumption, the authors recover a regret bounds of the order Õ(di⇤ p T + d4i⇤/ ) for arbitrary action sets. Cutkosky et al. [2020] also manage to recover the O(di⇤ p T ) and O(d2i⇤ p T ) bounds for the model selection problems through their
corralling algorithm. Ghosh et al. [2021] propose an algorithm which enjoys Õ ⇣ d2M 4.65 + p dm⇤T ⌘
in the finite arm setting, where = min{|✓m⇤,i| : |✓m⇤,i| > 0} is the smallest, in absolute value, entry of ✓m⇤ . Their algorithm also enjoys a similar guarantee for arbitrary action sets with p dm⇤T replaced by dm⇤ p T . Zhu and Nowak [2021] show that it is impossible to achieve the desired regret guarantees of p dm⇤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 multi-armed bandit problem it is impossible to achieve p T regret to a fixed arm, without suffering at least K p T regret to a 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 to 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 to perform as well as 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 miss-specified linear contextual bandit problem, that is the observed losses are linear up to some unknown ✏ miss-specification, and the work of Arora et al. [2021] who study the corralling problem for multi-armed stochastic bandit algorithms.
Our work also shows an impossibility result for the stochastic bandit problem with non-stationary rewards. Auer [2002] first investigates the problem under the assumption that there are L distributional changes throughout the game and gives an algorithm with a Õ( p KLT ) dynamic regret2 bound, under the assumption that L is known. Auer et al. [2019] achieves similar regret guarantees without assuming that the number if switches (or changes) of the distribution is known. A different measurement of switches is the total variation of changes in distribution VT = PT t=2 kE[`t] E[`t 1]k1. Multiple works give dynamic regret bounds of the order Õ(V 1/3T T 2/3) (hiding dependence on the size of the policy class) when VT is known, including for extensions of the multi-armed bandit problem like
2In dynamic regret the comparator is the best action for the current distribution.
contextual bandits and linear contextual bandits [Besbes et al., 2014, Luo et al., 2018, Besbes et al., 2015, Wei et al., 2017]. Cheung et al. [2019], Zhao et al. [2020] further show algorithms which enjoy a parameter free regret bound of the order Õ(V 1/4T T
3/4) (hiding dependence on dimensionality) for the linear bandits problem. The lower bound in Table 1 might seem to contradict such results. In Section 5.1 we carefully explain why this is not the case.
Finally, our lower bounds apply to the problem of devising an algorithm which simultaneously enjoys a second order bound over any fraction of experts. Cesa-Bianchi et al. [2007] first investigate the problem of second order bounds for the experts problem, in which the proposed algorithm maintains a distribution pt over the set of K experts, during every round of the game. The experts are assumed
to have stochastic losses `t and the work shows an algorithm with Õ( qPT
t=1 Vi⇠pt [`t,i] logK) 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 b✏Kc experts for an arbitrary positive ✏. The above works propose algorithms which achieve a Õ( p T log(1/✏)) regret bound for all ✏ simultaneously. Freund [2016] asks if there exists an algorithm which enjoys both guarantees at the same time, that is, does there exist an algorithm with regret bound Õ( qPT
t=1 Vi⇠pt [`t,i] log(1/✏)) which holds simultaneously for all positive ✏.
Notation. For any N 2 N, [N ] denotes the set {1, . . . , N}. Õ notation hides poly-logarithmic factors in the horizon T and the number of arms K but not in the size of the policy classes |⇧m|.

heading: 2 Problem setting
text: We consider the contextual bandit problem with general policy classes of finite size. There are K arms and nested policy classes (⇧m)Mm=1, where a policy ⇡ 2 ⇧m,⇡ : X ! [K] is a mapping from an arbitrary context space X into the set of K arms. The game is played for T rounds and at any time t, the agent observes a context xt 2 X , selects arm At 2 [K] and observes the loss `t,At from an otherwise unobserved loss vector `t 2 [K]. We measure an algorithm’s performance in terms of pseudo-regret, which is the expected cumulative regret of the player against following a fixed policy in hindsight
Reg(T,⇧) = max ⇡2⇧
E " TX
t=1
`t,At `t,⇡(xt)
# .
Environments. We distinguish between stochastic environments and oblivious or adaptive adversaries. In stochastic environments, there are unknown distribution PX , Q such that xt ⇠ PX and
`t ⇠ Q(·|xt) are i.i.d. samples. In the adversarial regime, the distributions can change over time, i.e. xt ⇠ PX ,t, `t ⇠ Qt(·|xt). When the choices are fixed at the beginning of the game, the adversary is called oblivious, while an adaptive adversary can chose PX ,t, Qt based on all observations up to time t 1.
Often the stochastic-adversarial 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 a fixed policy class ⇧ of finite size are of the order Õ( p ln(|⇧|)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 ⇧1 ⇢ ⇧2 ⇢ · · · ⇢ ⇧M , is there a universal ↵ 2 [ 12 , 1) such that a regret bound of
Reg(T,⇧m) = PolyLog(K,M)Õ ln(|⇧m|)
1 ↵ T ↵
(1)
is obtainable for all m 2 [M ] simultaneously?
W.l.o.g. we can assume that M = O(ln ln(|⇧M |)) = O(ln(T )). Otherwise we take a 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 the 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 xt = t 2 [T ] and the set of policies is given by
⇧S =
( ⇡ T 1X
t=1
I{⇡t 6= ⇡t+1}  S ) ,
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 ln |⇧S | = Õ(S). To make clear what problem we are considering, we are using RegSW (T, S) to denote the regret in the switching problem.
Next, we define the class of proper algorithms which choose their policy at every time step t independently of context xt. Restricting our attention to such algorithms greatly reduces the technicalities for lower bound proofs in the non-adaptive regimes. The lower bound for this class of algorithms is also at the core of the argument for adaptive (improper) algorithms in stochastic environments. Definition 1. We call an algorithm proper, if at any time t, the algorithm follows the recommendation of a policy ⇡it 2 ⇧M , and if the choice of it by the algorithm, is independent of the context xt.
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.

heading: 3 Upper bounds
text: In this section, we generalize the Hedged-FTRL algorithm [Foster et al., 2020a] to obtain an upper bound for model selection over a large collection of p T regret algorithms.
Theorem 1. For any C > 0, we can tune Hedged-FTRL over a selection of M instances of EXP4 operating on policy classes ⇧1, . . .⇧M , such that the following regret bound holds uniformly over all m 2 [M ]
Reg(T,⇧m) = Õ
✓ max ⇢ C, ln |⇧m|
C
p
MKT ◆ .
Input: ↵, R, , T op, (Basei)Mi=1 for t = 1, . . . , T do
Get Mt, qt,Mt from Top Let BaseMt play the next round and receive At Play At and observe `t,At Update BaseMt with `t,At/qt,Mt Update Top with (Mt, `t) if qt+1 would violate Eq. (2) then
Bias losses by bt to ensure Eq. (2). end
end Algorithm 1: Hedged FTRL
Hedged-FTRL. (↵, R)-hedged FTRL, introduced in Foster et al. [2020a], is a type of Follow the Regularized Leader (FTRL) algorithm which is used as a corralling algorithm [Agarwal et al., 2017]. At every round t, the algorithm chooses to play one of M base algorithms (Basei)Mi=1. Base algorithm i is selected with probability qt,i, where qt 2 M 1 is a distribution over base algorithms determined by the FTRL rule qt = argminq2 M 1hq, Lt Bti + F (q)/⌘, where Lt 2 RM+ is the sum of the loss vectors (eMs`s,As/qs,Ms) t 1 s=1, F : M 1 ! R is the potential induced by the ↵-Tsallis entropy, ⌘ is a step size determined by the problem parameters and Bt is a special bias term which we now explain. Define ⇢ 1t,m = min{ m,mins2[t] qs,m}, and initialize B0,m = ⇢↵1,mRm. Here ⇢t is a vector which tracks the variance of the loss estimators, R is a vector with regret upper bounds for the base algorithms, and  q1 is a threshold depending on the base algorithms. At any time t, after selecting base algorithm Mt to play the current action, the top (corralling) algorithm observes its loss and gives as feedback an important weighted loss to the selected base, Mt. Whenever the base played at round t would satisfy ⇢t+1,Mt > ⇢t,Mt , the loss fed to the top algorithm is adjusted with a bias bt,Mt , such that the cumulative biases track the quantity ⇢↵t+1,mRm. This has been shown to be always possible [Foster et al., 2020a]. The condition for adjusting the biases reads
8m 2 [M ] : B0,m + tX
s=1
bs,m = ⇢ ↵ t+1,mRm . (2)
The condition in Equation 2 is motivated in a similar way to the stability condition in the work of Agarwal et al. [2017]. Algorithm 1 constructs an unbiased estimator for the loss vector, eMt`t,At/qt,Mt , and updates each base algorithm accordingly. A similar update is present in the CORRAL algorithm Agarwal et al. [2017] in 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 guarantees are possible. Formally, the following stability property is required. If an algorithm B enjoys a regret bound R under environment V with loss sequence (`t)Tt=1, then the algorithm is (↵, R)-stable if it enjoys a regret bound of the order E[⇢↵max]R under the environment V 0 of importance weighted losses (ˆ̀t)Tt=1, where ⇢max is the maximum variance of the T losses and the expectation is taken with respect to any randomness in B. Essentially all bandit and expert algorithms used in practice are (↵, R)-stable with ↵  1/2, e.g., Exp4 is (1/2, p KT ln(|⇧|))-stable. The bias terms in Algorithm 1 intuitively cancel the additional variance introduced by the importance weighted losses and this is why we require the biases to satisfy Equation 2. Theorem 2. Given a collection of base algorithms (Bm)Mm=1 which are (1/2, p CmT )-stable, that is
8m 2 [M ] : RegImp(T,Bm)  E[ p ⇢Tm] p CmT ,
and any C 0, then the regret of (1/2, R, )-hedged Tsallis-Inf with Rm = p CmT , m =
1 M max{1,
C2 Cm } satisfies a simultaneous regret of
8m 2 [M ] : Reg(T,Bm)  2max
⇢ C,
Cm C p MT + p 2MT .
The analysis follows closely the proof of Foster et al. [2020a] and is postponed to Appendix A.
Theorem 2 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 ⇧m satisfies the condition of Theorem 2 with Cm = O(ln |⇧m|), as shown in Agarwal et al. [2017]. Hence Theorem 1 is a direct corollary of Theorem 2.

heading: 4 Lower bounds
text: We present lower bounds that match the upper bounds from Section 3 up to logarithmic factors, thereby proving a 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(C p KT ) ,
there exists for any number of switches S = ⌦(C2) a stochastic bandit problem such that
RegSW (T, S) = ⌦
✓ min ⇢ S
C
p
KT, T ◆ .
This bound holds even when the agent is informed about the number of switches up to time t.
Since this bound holds even when the agent is informed about when a switch occurs, we can restrict the policy class to policies that only switch arms whenever the agent is informed about a switch in the environment. This as a contextual bandit problem with context X = [S + 1] and |⇧S | = ⇥(KS) policies. Hence Theorem 3 implies a lower bound of Reg(T,⇧S) = ⌦ ⇣ min n ln |⇧S | C ln(K) p KT, T o⌘ . In the second part of the section, we consider the stochastic regime. Our lower bound construction is 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 ⇧1 ⇢ ⇧2 3 with |⇧2| = ⌦(C2), such that if the regret of a proper algorithm is upper bounded in any environment by
Reg(T,⇧1) = O(C p T ) ,
then there exists an environment such that
Reg(T,⇧2) = ⌦
✓ max ⇢ C, ln |⇧2|
C
p
T ◆ .
These theorems directly provide negative answers to [Foster et al., 2020b]. Corollary 1. There is no ↵ 2 [ 12 , 1) that satisfies the regret guarantee of open problem (1) for any algorithm in the adaptive adversarial regime or any proper algorithm in the stochastic case.
Proof. By Theorems 3 and 4, for any ↵ > 0 there exists K = 3, M = 2, |⇧1| = 1, |⇧2| = ⇥(exp(T↵)). Assume that Reg(T,⇧1)  CTT↵ = CTT↵ 1 2 p T , where CT = PolyLog(T ). Hence by Theorem 3 and Theorem 4 there exist environments where
Reg(T,⇧2) = ⌦
✓ T ↵
CTT ↵ 12
p
T ◆ = ⌦̃ (T ) .
Finally, we 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 in the following subsections and the detailed proof in Appendix B.
3In 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( ) Problem
We present the adaptive environment in which model selection fails and the proof of Theorem 3.
The adversary switches the reward distribution up to S many times, thereby segmenting the time into S + 1 phases (1, . . . , ⌧1, ⌧1 + 1, . . . , ⌧2, . . . , ⌧S , . . . T ). We denote xt 2 [S + 1] as the counter of phases and assume the agent is given this information. For each phase xt 2 [S], the adversary selects an optimal arm (a⇤s)Ss=1 uniformly at random among the first K 1 arms. If xt  S, the losses are i.i.d. Bernoulli random variables with means
E[`t,i] = 1
2
8 <
: 0 for i 2 [K 1] \ {a⇤xt} for i = a⇤xt 7 8 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. A switch from phase s < S + 1 to s+ 1 occurs when the player has played Nmax = d K 1192 2 e times an arm in [K 1] in phase s. We can see this problem either as a special case of S-switch problem, or alternatively as a contextual bandit problem with |⇧S | = KS+1 policies.
The lower bound proof for S-switch( ) relies on the following Lemma, which is proven in Appendix B. Lemma 1. Let an agent interact with a K 1 2 armed bandit problem with centered Bernoulli losses and randomized best arm of gap  1
8 p 3 for an adaptive number of time steps N . If the probability of N Nmax = d K 1192 2 e is at least 1 2 , then the regret after Nmax time-steps conditioned on the event N Nmax is lower bounded by
Reg
4 Nmax .
Informally, this Lemma says that conditioned on transitioning from phase s to phase s+ 1, the agent has suffered regret ⌦( Nmax) against arm K during phase s.
Informal proof of Theorem 3. The adversary’s strategy is designed in a way such that at each phase s 2 [S] it only allows the player’s strategy to interact with the environment just enough times to discover the best action a⇤s . Then a new phase begins to prevent the player from exploiting knowledge of a⇤s . This ensures by Lemma 1 that the player suffers regret at least ⌦( Nmax) during each completed phase. If an agent proceeds finding a⇤s for all phases s 2 [S], then the regret against the non-switching baseline is RegSW (T, 1) = O( Nmax S). By the assumption on the maximum regret of RegSW (T, 1) and an appropriate choice of Nmax and , we can ensure that the agent must fail to discover all a⇤s with constant probability, thus incurs regret at least RegSW (T, S) = ⌦( T ) against the optimal S-switch baseline. Tuning and Nmax yield the desired theorem. The formal argument with explicit choice of is found in Appendix B.

heading: 4.2 Stochastic lower bound
text: We now present the stochastic environment used for the impossibility results in Theorems 4 and 5.
There are k + 1 environments (Ei)ki=0 with ⇧2 = {⇡i|i 2 [k] [ {0}} policies and ⇧1 = {⇡0}. In all environments, we have K = 3 and ⇡0 always chooses action 3, while (⇡i)ki=1 are playing an action from {1, 2} uniformly at random. (In other words, the context is X = {1, 2}k with xt sampled uniformly at random and ⇡i(x) = xi.)
In each environment, the losses of actions {1, 2} at any time step satisfy `t,1 = 1 `t,2, which are conditioned on xt independent Bernoulli random variables, with mean
EE0 [`t,1] = EE0 [`t,2] = 1
2 and 8i 2 [k] : EEi [`t,⇡i(xt)] =
1 2 (1 ) .
Action 3 gives a constant loss of 12 1 4 in all environments.
Let us unwrap these definitions. Playing either action 1 or action 2, which we call revealing actions, yields full-information of all random variables at time t due to the dependence of `t,1 = 1 `t,2 and
the non-randomness of `t,3. On the other hand, playing action 3 allows only to observe xt, which has the same distribution in all environments, hence there is no information gained at all.
We know from full-information lower bounds that for optimal tuning of the gap, one suffers ⌦( p ln(k)T ) regret in the policy class ⇧2, due to the difficulty of identifying the optimal arm. For a smaller regret in policy class ⇧1, one needs to confirm or reject the hypothesis E0 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 is to show that the hardness of rejecting E0 is of the same order as identifying the exact environment.
For the remaining section, it will be useful to consider a reparametrization of the random variables. Let zt 2 {0, 1}k be the losses incurred by the policies (⇡i)ki=1: zt,i = `t,⇡i(xt). We can easily see that zt together with xt,1 is sufficient to uniquely determine `t and xt. Furthermore, zt is always a vector of independent Bernoulli random variables, which are independent of xt,14. In environments (Ei)ki=1, the i-th component is a biased Bernoulli, while all other components have mean 1 2 . In E0, no component is biased. As before, xt,1 does not provide any information since its distribution conditioned on zt is identical in all environments (see Lemma 4 in Appendix B for a formal proof).
Under this reparameterization and ignoring non-informative bits of randomness, the problem of distinguishing E0 from {Ei}ki=1 now looks as follows. For time steps t = 1, . . . , T , decide whether to play a revealing action and observe zt (potentially by taking xt into account). Use observed (z⌧n) N n=1 to distinguish between the environments. Proper algorithms simplify the problem even further, because selecting ⇡it independently of xt implies that the decision of observing zt is also independent of xt (any policy except ⇡0 allows to observe zt under any context). Hence for proper algorithms, we can reason directly about how many samples zt are required to distinguish between environments. This problem bears similarity to the property testing of dictator functions [Balcan et al., 2012] and sparse linear regression [Ingster et al., 2010]5, however, there is no clear way to apply such results to our setting.
The following lemma shows the difficulty of testing for hypothesis E0.
Lemma 2. Let  14 , k e 20 + 1, N  b ln(k 1)20 2 c and 2 N
1 2 . If the algorithm chooses
whether to reveal zt independently of xt and if the total times zt is revealed is bounded by N a.s. then for any measurable event E it holds that
min i2[k]
PEi(E) PE0(E)  17
4 p k 1
 1
4 .
The proof of Lemma 2 is deferred to Appendix B.3. The high level idea is to directly bound the TV between mini2[k] PEi and PE0 over the space of outcomes of (ztn)Nn=1 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 a huge surprise. For a T -round full-information game, it tells us that we can bias a single arm up to = ⌦( p ln(k)/T ), without this being detectable. This directly recovers the well known lower bound of T = ⌦( p ln(k)T ) 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 environment E0, observing zt for n time-steps incurs a regret of RegE0(T,⇧1) = ⌦( n). Using the assumption on the regret RegE0(T,⇧1) and Markov inequality, we obtain an upper bound N on the expected number of observations, which holds with probability 12 . We can construct an algorithm A that never observes more than N samples, by following algorithm A until it played N times a revealing action and then commits to policy ⇡0 (action 3). Since the algorithm A is proper, we can define Z = (z⌧i)Ni=1 as the observed z’s during time ⌧i where the algorithm plays a revealing action. For the revealed information generated by A, we tune the
4We want to emphasize that zt is only independent of xt,1, not independent of the full vector xt. 5The 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 to one.
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 1 ⌦(1) under mini2[k] PEi(E). Thus, there exists an environment i 2 [k] such that A plays less than N times an action in {1, 2} with constant probability, which incurs regret of RegEi(T,⇧2) = ⌦( T ). The theorem follows from tuning 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 k to improper algorithms, we can still show that no algorithm (proper or improper) can solve the open problem (1) for stochastic environments.
The key is the following generalization of Lemma 2, which is proven in the appendix.
Lemma 3. Let  14 , k e 20 + 1, N  b ln(k 1)20 2 c and 2 N
1 2 . If the total number of times zt
is revealed is bounded by N a.s. then for any measurable event E it holds that
min i2[k]
PEi(E) PE0(E)  17TN
4 p k 1 .
This holds even if the agent can take all contexts (xt)Tt=1 and previous observations into account when deciding whether to pick a revealing action at any time-step.
Informal proof of Theorem 5. The proof is analogous to Theorem 4, however we use Lemma 3 to bound the difference in probability of E under E0 and Ei. The key is to find a tuning such that the RHS of Lemma 3 does not exceed 14 . Note that this is of order exp(O(ln(T )N) ⌦(ln(k))). Let = ⇥(1), then the requirement on RegE0(T,⇧1) yields N = O(T
↵). Setting k = ⇥(exp(T↵+✏)) for any ✏ 2 (0, 1 ↵), then it follows immediately that the RHS in Lemma 3 goes to 0 for T ! 1. Following the same arguments as in Theorem 4, there exists a sufficiently large T up from which there always exists an environment (Ei)i2[k] such that the regret is linear in T , thereby contradicting the open problem. The formal proof is deferred to Appendix B

heading: 5 Implications
text: 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 to the expected insights.

heading: 5.1 S-switch
text: 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 in 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 ln(T ) arms, corresponding to a 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. It collects the accumulated losses Lsum = PL t=1 `t of the algorithm and feeds the loss Lsum/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 `t independent of the choice of arm At 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 `t is not chosen independent of the action At. Hence the protocol is broken and the adaptive adversarial regret bounds do not hold.

heading: 5.2 Second order bounds for full information.
text: In an unresolved COLT2016 open problem, Freund [2016] asks if it is possible to ensure a regret bound of order
Reg" = Õ
0
@
vuut TX
t=1
Vi⇠pt [`t,i] ln( 1
" )
1
A , (3)
against the best " proportion of policies simultaneously for all ". We go even a step further and show that the lower bound construction from Section 4.2 directly provides a negative answer for any ↵ < 1 to the looser bound
Reg" = Õ
0
@
vuut TX
t=1
(Vi⇠pt [`t,i] + T↵) ln( 1
" )
1
A . (4)
Theorem 6. An algorithm satisfying Eq. (4) for ↵ < 1 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 ↵ 2 [0, 1), there is no algorithm which enjoys a regret upper bound as in Equation 3 for all problem instances s.t. PT t=1 (Vi⇠pt [`t,i]) = ⇥(T↵). This implies we can not hope for a polynomial improvement, in terms of time horizon, over the existing bound of Õ( p T ln(1/✏)). The detailed proof is found in Appendix B. The high level idea is to initialize the full-information algorithm satisfying Eq. (4) with a sufficient number of copies of the baseline policy ⇡0 and to feed importance weighted losses of the experts (i.e. policies) to that algorithm.
As we mention in Section 1, the case ↵ = 1 is obtainable. Our reduction relates the adaptation to variance to the model selection problem. As in Eq. (1), ↵ is the trade-off between time and complexity. An algorithm satisfying Eq. (4) with ↵ = 1 merely allows to recover the trivial O(T ) bound for model selection, and hence does not lead to a contradiction.

heading: 6 Conclusion
text: 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 to 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.

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

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: 1.  The paper resolves the open problem of Foster et al. (2020b) by providing a negative answer.  2.  As a byproduct, the paper resolves a COLT 2016 open problem on second-order bounds for full-information online learning (Freund 2016).  For 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.

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