Best of Both Worlds Model Selection
Authors: Aldo Pacchiano
Christoph Dann
Claudio Gentile
Venue: NeurIPS 2022 Accept (2022)
Keywords: bandits
linear bandits
model selection
policy classes
best of both worlds
reinforcement learning
adversarial
stochastic

Abstract: We study the problem of model selection in bandit scenarios in the presence of nested policy classes, with the goal of obtaining simultaneous adversarial and stochastic (``best of both worlds") high-probability regret guarantees. Our approach requires that each base learner comes with a candidate regret bound that may or may not hold, while our meta algorithm plays each base learner according to a schedule that keeps the base learner's candidate regret bounds balanced until they are detected to violate their guarantees. We develop careful mis-specification tests specifically designed to blend the above model selection criterion with the ability to leverage the (potentially benign) nature of the environment. We recover the model selection guarantees of the CORRAL algorithm for adversarial environments, but with the additional benefit of achieving high probability regret bounds. More importantly, our model selection results also hold simultaneously in stochastic environments under gap assumptions. These are the first theoretical results that achieve best-of-both world (stochastic and adversarial) guarantees while performing model selection in contextual bandit scenarios.


Best of Both Worlds Model Selection
Aldo Pacchiano Microsoft Research, NYC apacchi cro@miirofo com
Christoph Dann Google, NYC cdann@cdann net
Claudio Gentile Google, NYC cgentile@google.coo
Abstract
We study the problem of model selection in bandit scenarios in the presence of nested policy classes, with the goal of obtaining simultaneous adversarial and stochastic ("best of both worlds") high-probabiiltyy regret guarantees. Our approach requires that each base learner comes with a candidate regret bound that may or may not hold, while our meta algorithm plays each base learner according to a schedule that keeps the base learner's 's candidate regret bounds balanced until they are detected to violate their guarantees. We develop careful mis miis-peciifiction tests specifically designed to blend the above model selection criterion with the ability to leverage the (potentially benign) nature of the environment. We recover the model selection guarantees the CORRAL [3] algorithm for adversarial environments, but with the additional benefit of achieving high probability regret bounds. More importantly, our model selection results also hold simultaneously in stochastic environments under gap assumptions. These are the first theoretical results that achieve best of both world (stochastic and adversarial) guarantees while performing model selection in contextual bandit scenarios.
Introduction
fundamental challenge in sequential decision-making is the ability of the learning agent adapt to the unknown properties of the environment they interact with. While adversarial environments may require some caution, would also like to leverage situations where more benign scenarios may be disclosed as result of this interaction.
In the literature multi- armed bandits, this adaptation capabilities has often taken two forms: 1. Best-of-both worlds guarantees, which were pioneered by [10] and subsequently studied by a number of authors [e.g., 29, 5, 28, 30, 33, 21]. Here, the goal is to design algorithms achieving both stochastic and adversarial environment guarantees simultaneously, without knowing the type of environment in advance. Similar in spirit is the stream of literature stochastic rewards with adversarial corruptions [23, 17, 34, 21, 31], where an adversary is assumed to corrupt the stochastic expected degrade gracefully with
rewards observed by the algorithm, and the regref guarantees the total amount of corruption, without knowing this amount in advance.
Model selection guarantees, which were initiated by [3], and subject since then intense investigations [e.g.. 15, 1, 27, 4. 16. 12, 8, 14, 22, 26, 13]. Here, we assume we have access to pool of M base bandit algorithms each operating, say, within different class of models or under different assumptions on the environment, and the aim is to design bandit meta- algooriht that learns to simulate the best base algorithm in hindsight, without knowing in advance which one will be best for the environment at hand. This approach has often been used in the literature to capture bandit model selection problems. In fact, a natural instantiation of this framework is when we have sequence of nested policy classes, and the goal is single out the best policy within this nested family, by paying as price only the complexity of the policy class the optimal policy falls into. In some sense, Item 2 is more general than Item 1, since one may attempt to achieve a hest-of-both-wea world performance by pooling a stochastic bandit algorithm with an adversarial bandit one, and expect the meta-algorithm on top of them to eventually learn to follow one of the two. Similarly, in the setting of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

stochastic rewards with adversarial corruptions, one can pool together stochastic algorithmss operating with increasing guessed levels of corruptions, and let the meta-algorithm learn single out the one corresponding to the true corruption level.
In this paper, we combine the two items above into bandit algorithm that exhibits both model selection and best-of-both worlds regret guarantees simultancously. Our framework encompasses in particular a well-known linear bandit model selection scenario, where the action set A is (finite but large) subset of IR for some maximal dimension dM > O, and we deal with hierarchy of possible dimensions d1 .... < dy. At time t, the learner plays an action a E A and receives as reward reward vector (adversarial setting),
either a, W;, where W, E Ra is an ad veersariall-generaaee or = w+ + white noise, where w E Rddar is a fixed but unknown reward vector (stochastic setting). Associated with dimensions d1 < .... < dı are nested family of policy classes IT, C C... TM, and M base algorithms A.,..., AM. where the i-th algorithm A, is a linear bandit algorithm that works under the assumption that only the first d, components of Wt (or w) are nonzero. Hence A; operates with dimension d; in that all policies π E II, are probability distributions which are projections over action set A, of the set of probability distributions in aas Here, A, is the projection of the mull-dimessional action set A onto its first d, dimensions. Notice that this implies that the policy classes are nested: II, S Il2... ... S MI. If only the first d,, dimensions (i. being unknown to the learner) of each W/ (adversarial setting) or w (stochastic setting) are nonzero, we design an algorithm whose regret bound scales as poly(d:,) VT in the adversarial case and, simultaneously,
as poly(dar) log if the environment happens to be stochastic. Specific consideration is given to the dependence on di.. We show through lower bounding argument that in the stochastic case a guarantee of the form dM log T that is, where dı replaces the more desirable factor d,,, is inevitable, A
if we want to insist on obtaining logT -lie result. Thus our bounds reflect the best achievable regret rates depending on dæ in the stochastic case and on poly(ds,) in the adversarial case.
In order to achieve these best-of-bothh sorf-booh-worddd results, one cannot easily rely on general corralling techniques, like the one contained in [3], since the granularity offered by adversarial aggregation algorithms is no better than VT. which is not adequate for stochastic settings; hence our choice towards the model selection technique known as regref balancing. Yet, even in this case, the literature does not provide off-the-shelf solutions: We first need to extend regret balancing from stochastic rewards [13, 26, 1] and corrupted stochastic rewards [31] to adversarial rewards. This involves adding extra actions to the action space at a given level of the hierarchy so as to enable the base learner operating at that level to compete with higher levels. This seems to be needed because in the adversarial case, base algorithms may even incur a negative regret, thus making it hard to compare the relative performance of algorithms operating at different levels during the regret balancing operations. Specific technical hurdles arise in the linear bandit case, where mis- suissppeciiiattin may cause low-level base learners to behave in maliciously erratic way. In this case, mis-specification tests have to be designed with care so as to ensure that base learners that are mis-specified but not yet eliminated incur manageable regret. At the same time, these tests should also detect soon as possible if the environment is stochastic through ad hoc regret balancing gap estimation procedures.
For our results to hold, some technical conditions are required on the base algorithms, like notion of (high probability) stability and notion of action space extendability, formally defined in Section 2. We show that these conditions are fulfilled by known algorithms, like an anytime variant of the GeometricHedge.P algorithm [7], and a high-probability variant of the EXP4 algorithm in [6].
Related work. Among the references we mentioned above, those which are most relevant to our work, as directly related to model selection and boot-ol-both-worddds guarantees are perhaps [4, 13, 21, 31]. In both [4] and [13], model selection regret guarantees for stochastic contextual bandits are given which take the form poly(d, (d,, J Yet, no combination of best-of- both worlds and model selection results are contained in those papers. Closer in spirit are [21] and [31].
In [21], the authors consider model selection problems on top of adversarially corrupted stochastic linear bandit problems, where the total level of corruption C is unknown in advance. It is worth stressing that this is a model selection problem which is substantially different (and actually easier, see Section& 4) than ours, as the selection applies to C' instead of the complexity term R(II.). In fact, the model selection procedure in [21] looks very different from ours, and can be roughly seen as
RReeent relevant papers, working with model mis-specification instead of reward corruption, include [27, 14).

---

robust version of doubling trick applied to C. Our algorithm is more general than theirs, as it applies settings beyond linear bandits, and the same is true of our best of both worlds procedures.
In [31], the authors also consider RI. settings, and more general forms of corruptions than [21]. Like ours, their model selection algorithm follows the idea of regret balancing and elimination of [I, 13]. Yet, importantly our work applies the fully adversarial setting with vT regret while the corruption-robust approach by [31] suffers a linear in 7 regret if the world is fully adversarial (C -(T)). To enable this sublinear regret, several important technical challenges needed to solved that are not present in the corruption setting. Most importantly, the corruption setting can, for the most part. be handled similar to the stochastic setting. For instance, since [31] measures regret always w.r.t. to the uncorrupted environment, by definition, no learner can achieve negative regret, which entails that setting does not require linking base learners as we do here see Section 2.
On the lower bound side, relevant papers include [32, 24), where the authors investigate the Pareto frontier of model selection for (contextual) stochastic bandits. It is shown in particular that regret upper bound of the form / d,,T T cannot be achieved. However, these papers do not explicitly cover gap-dependent regret guarantees. A more thorough discussion our contributions is postponed to Section 3, after introducing our main notation and assumptions.
2 Problem Setting and Assumptions
We start off by defining the adversarial scenario. An adversarial contextual bandit problem is a repeated game between a learner A and an environment B. We consider the general decision-making scenario where the learner has its disposal class of policies IIA made up functions т of the form : X - AA, where A denotes the set of probability distributions over A. At each round I, the interaction between and B is as follows:
1. Learner & selects a policy Ti IIA
2. Simultaneously, the environment B selects context 2; X' and reward function re
A x X' + [0, 1], and reveals x, to A
3. Learner A takes an action ae ~ ..( (.) and observes reward or = ry rr(at,
The regret Rega (T, II') of algorithm in rounds T C N against a policy class IT' is the difference between the learner's accumulated reward in T and the performance the best fixed policy from II':
Rega (Tgg(T,T) (T, xEIl'
max
[Eas [re(a, re((e,
EET
EeEd (a)ar))re(a me) denotes the expectation over the action drawn from the given policy æ which may itself be random quantity. For ease of notation, we will omit the comparator policy class when II' = II is the policy class of A and replace T by t when T= [1] :- (1...., l). Hence, Rega (t) is the regret of A against its own policy class up to round t.
where Euw=(re(a,
The stochastic scenario we consider is similar the above, except the way contexts 2, and reward values ri(a,, 2z) are generated. Specifically, B generates contexts Fa in an i.i.d. fashion according to a fixed (but arbitrary and unknown) distribution D over X' while the reward r (a,, 21) is such that for all fixed (a, x) E A x X, we have E[r; (a, =]] = r r(a, I), for some fixed function r(.,) :) in some known class of reward functions. In this case, we measure performance through pseudo-regret
PseudoRega (T, IT')
Σ max TETT'
EanDDar x)) E aamm [r(a,
EET
where Ez~DDava is the expectation over contexts and the action a ~ (-|2x) drawn from policy that may itself be a random quantity. We say an environment E is stochastic with gap A > if there is policy n, II such that
EgnD awe. [r(a,x)) Z
max Eew-Da (r(a, x)] + A. *EIl((=*)
notable example of the above the following linear bandit scenario. ("adversarial linear bandits"") the action space A is a subset of Rd, for some dimension d, the context J, is irrelevant and, upon playing action a, E A, the environment generates a reward which is linear function of the actions, T1 xx) r. ra(a)) a, Wi, where wi is chosen adversarially every round
the adversarial case
3

---

within some known class of d- d-dimensional vectors. In the stochastic case ("stochastic linear bandits") "), the only difference is that we simply have ry (a, 2x) rr((ar) a, w + c,. where w is a fixed and unknown vector in the class of d-dimensional vectors, and 6, is sub-Gaussian noise. Moreover, we have gap A if there is x'' E IT such that Ea [a [ max Rig
[a [ A.
Many algorithms A in the literature exist that enjoy regret bound against their policy class 11 holding in all environments IB satisfying certain conditions. If this regret bound holds, we say that A is adapted to this environment. Here, we allow algorithms to also compete against policy classes II' other than II,, and focus on algorithms that come with regret bounds of the following form.
Definition 1 (Adapted). We call A adapted to environment B and policy class 11' if. with probability least 6, the following bound holds simultaneously for all N.
Rega (1, IT') = ==
(((TTA) (
The term R(II,) is a (known) measure of complexity of the policy class 1Ig used by A.
Examples of algorithms satisfying Definition I include version of the Geometric Hedge algorithm in linear bandits [7] and the EXP4 algorithm [6] in contextual bandits with finite action sets that operates over policies mapping contexts to probability distributions over actions. We will discuss them in detail below. Before introducing the model selection questions addressed in this work, we present two stronger versions of the above definition, which we call probbbrrbybiiityy stability and extendability. These will be useful for model selection among multiple learners. As we will show with examples later, these stricter conditions can be established for several common settings under the same conditions for which adaptivity from Definition is guaranteed.
Additional conditions. The first condition, high-prebubillity stability (or h-stability) generalizes adaptivity to the case where A only observes certain noisy version of the reward. To state the condition formally, consider more general interaction protocol between A and the environment IB, where Step above is replaced by
3a. Let be Bernoulli(p) for fixed and known م (0, 1]. Learner A takes action a, ~ T (it) and observes an importance-sampler version of the reward 0r = b, ra(a).r.)
This encompasses the original protocol with p 1 as a special case. An algorithm is h-stable if maintains its regret guarantee up to a 1/ /p penalty in this more general interaction protocol: Definition 2 (h-stability). An algorithm & is high probability stable (h-stable) in environment B against policy class II' if it satisfies for any constans E (0, 1] a regret bound
Rega (t, II') = (t,,Ir)):) (RITA) In
that holds with probability at least - 8 simultaneously for all t N.
Note that A is adapted to B and IT' if it is h-stable for p 1. Compared to the notion of stability proposed in [3], the one in Definition 2 is more demanding, in that it requires the importance- weighted regret bound to hold with high probability, rather than in expectation. Since we aim for regret bounds in ad adversarial and stochastic settings, this stronger notion is natural.
The second condition, extendability, generalizes h-stability to environments with additional actions, as specified next. Let be the original environment with action set A and let A = AU aa,,,.,,, d% be the action set extended by k extra special actions a/ ab .h..................... ........,.. a/. Further, let II = (π AAA } be an extended version of the original policy set II = {T: : X + A that contains all policies of the original policy set and the single-action policies {a{} that always choose a certain special We further allow the environment on the extended action space A choose any values for rewards 2e(,),..), possibly depending on the entire history and all rewards ra(a, xx) assigned to other actions & a in that round. We denote the set of all such extended environments by (B, As). An algorithm A is now extendable we can run it with the extended policy set II and it competes well against II' and policies 1 {at} in all such extended environments.
action a/, i.e., IT 2 IT TUT (1 (af) 1 (a²) ...., 1 [a/
2 Here and throughout, the O-notation only hides absolute constants. Poliiies E 11 naturally extended from AA A, by assigning probability 0 to all special actions af.

---

Definition 3 (Extendability). Consider an algorithm A with policy set HI X AA in environment B. We call & k-extendable in against II' if there an extended policy set Th 2 IT U {1 {ai).- ... {aj] such that A equipped with the extended policy set TTg is h-stable against II U {1/) 1 {a } in all environments B E BBB, As) that extend B from action space A to action space A = AU Au.
One relevant example of h-stable and extendable algorithm working in the adversarial linear bandit scenario is an anytime variant of the Geometric Hedge algorithm from [7] with exploration ruled by John's 's ellipsoid (e.g.. [9]) see Appendix B. Another example is botb-brbbbbbiity variant of the EXP4 algorithm from [6], which operates with finite sets of policies.
2.1 Model selection and worl- regret
Our model selection for best-of-both worlds regret guarantees can be described as follows. We have nested family policy classes II; .... M. with (known) complexities R(III) S .... S R([Tas): A meta-learning algorithm M. has access to M base algorithms A1. AM algorithm A, operating with policy class II, These algorithms we sometimes refer to as base learners. Let i. be the smallest index of the base learner that competes against the largest policy class 11M in the following sense:
1 = min {i E [M] A, is (M - -)-exeendable and h-stable in IB against I1as)
The goal of model selection to devise meta- meta-algorithm M that has access to the base learners A1, ......; M, and which achieves with probability 1 - 5 a regret bound of the form*
Rega (t, 11M) = o (poly (M, ((I,, R(IM)) in 5)
holding for all f, whenever AM is h-stable and the environment is adversarial. Simultancously, IB stochastic with gap A, then must have
PseudoRegaa (t, l1M) = = (ooooo(MM R(TTas)
/ log 5)
A
Notice that the above requirement on the pseudo-regret in stochastic environments only requires dependence on R(IIM), instead of R(II,,). ). This is motivated by the fact that in stochastic environments with gap A it is generally impossible to obtain model selection guarantees of the form R(T,, logt sce Appendix A for proof of this claim.
3 Summary of Our Contributions and Discussion
Our contributions can be summarized as follows. (i) We introduce an algorithm, called Arbe (Algorithm 1), for high probability model selection. This is the first nigh-probability model selection result for adversarial contextual bandit algorithms. Arbe satisfies high probability guarantee as long as each of the base algorithms also satisfies one. Our algorithm takes inspiration from the balancing and elimination techniques [13], which have been designed for stochastic contextual bandit (and RL) scenarios. Yet, mentioned above, several technical hurdles had to be overcome in the algorithm's is design to make it usable with adversarial base learners. We believe the model R(I,,)
selection rates that our algorithm achieves are minimax optimal in their dependency Recall that, as shown by the lower bounds of [24], it is not possible to achieve a model selection rate scaling linearly with R(II,,) the best can hope for is quadratic dependence the setting of adversarial linear bandits this turns into a rate with a multiplier of the form d,, log(.A) instead of /d,, (og( 1). In particular, when |A| 9(24..) ) or |A| = co, this multiplier becomes d. In the simpler case of EXP4 base learners, this multiplier takes the form log(II,,) instead of Vlog(TT..)
RIII,)) In
(ii) We introduce the first algorithm for best-of-both wot---oot-woldds model selection. By leveraging the high- probability guarantees of Arbe, we develop the first best-of-both- worlds model selection algorithm
'Here, poly(a, b, c) is polynomial function of the three arguments separately. 'Despite we do not explicitly work out the details here, applying our results to the infinite arm case for adversarial linear bandits can be accomplished by standard covering argument at each dimension d, This turns factor log(A) into of the form d:, 'o.
5

---

Algorithm 1: Arbe 1,40 1,40 0) Adversarial Regret Balancing and Elimination
Input: initial time to. index s of smallest active base learner, failure probability
Initialize base learners A. Ast1...., AM with extended policy classes II,, II, IIM R(L,) 2 Set sampling probabilities P: Σ;-, R(n))= for all i {s...., M), and ps for i < for round 1 = fg + 1,40 + 2.... do Sample base learner index b, Categorical(p PPM) .PM)
Get context and compute af ~ xf{+|æz), the action each base learner A, proposes for 2t
Play action a, a (resolve linked actions necessary) and receive reward re (e( Update all base learners A; with reward
[b, - (ar.m))
P
Set
1
1 ( 13 (t)
(.(to)))= =0 (v
to In lnt
Int
CRew
=
+
(1)
Test for all ú, E (8,..., M) with i j:
1 to to In
(tu,,(tu;t)) CRew, f) D.(to, (too.)) R(IT.) test triggers for A; then restart algorithm by running Arbe(ô, i 1,t)
(2)
Pi
10
(Arbe-Gap Arbe-GapEEploiit Algorithm 2 + Algorithm 4) that retain model selection rates when the environment is adversarial, and obtain logarithmic rates when the environment is stochastic with a gap. The logarithmic gap-dependent rate of this algorithm exhibits optimal quadratic dependence w.r.t. the largest policy class R((TM) (see also Item (iii) below). Our algorithm is quite complex and requires couple of main innovations: First, careful design of a gap identification subroutine aimed at identifying candidate optimal policy and gap estimator (Arbe-Gap) and, second, very precise schedule of play for exploiting this knowledge and test its truthfulness (Arbe-Gar Arre--aaExxloity
(iii) As already mentioned, show via lower bound for stochastic environments that, in the presence of a gap. perfect model selection between multiple logarithmic rate learners is impossible. This can be found in Appendix A. A dependence on the complexity of the largest class R(I Ms) is inevitable, and this dependence must be quadratic. Our algorithms (Arbe-Gay Gape-aap + trbe-GapExploit achieve exactly this dependence when the environment is stochastic and has gap (Theorem 5).
4 Adversarial Model Selection Using Regret Balancing
We now introduce our algorithm for model selection in adversarial bandit problems with high- probability regret guarantees. The algorithm is shown in Algorithm 1, and follows the regret balancing principle. This principle has been applied successfully to model selection in bandit and RL problems with stochastic rewards [13, 26. 1] and with coruppted stochastic rewards [31]. Our work is the first to extend this approach to adversarial rewards.
Regret Balancing. In each round, we choose the index of a base learner by by sampling from categorical distribution with probabilities Pe: ... PM that remain fixed throughout the epoch. The policy of learner As, is then used to sample the action a, that is passed the environment. After receiving the reward rı (= xz), Algorithm updates each base learner As with Te (at, xx) importance- weighted by the probability that the learner was selected, i.e., 1(b,=5)re(00..)) Thus, we update all base learners. This is closer the Corral algorithm [3] than to the regret balancing approaches for the stochastic setting, which only update the selected learner Ab,-
Pi
If the probabilities are set to P: TIILY then after / rounds, each leamer A, is followed roughly pal times. To see why the regrets of all learners balanced if they are h-stable against II in this case, consider the following. Denote by reg, (a) [Eawer [Fe(a, xx)] (a xx)] the regret in round of
action where x¹ argmaaxeell. Σ Ea-a [r xx)] is the best policy after all rounds T' The

---

regret in rounds where A, was selected can be bounded using standard concentration arguments as
1 [b, = Σ 1 (b. = i) (ag) = Pi
T
T Ps (a:) & R(TT,) (VA.T)
(eg,(a))
(at)
Pt
where the final inequality holds because A, is h-stable. From the definition of p. we have R(IL))
EE R(T,)-=) - 1/2 S R(T,), which shows that the total regret in those rounds is bounded by Ö(R(İ.) Thus, if base learners are all h-stable, then the regret incurred by each of them is comparable the regret incurred by As, the learner with the smallest complexity RIII)).
Eliminating Base Learners. a learner A is not h-stable and may have linear regret, then the probabilistic schedule above which plays this learner roughly p, times yields linear regret. We therefore monitor the performance of each learner and terminate the epoch whenever a learner performs significantly worse than expected, and thus cannot be h-stable in the environment. To identify such cases, we compare estimates of the rewards of all pairs of base learners as follows. For
each learner A., (te t) in Equation is an unbiased estimate of the learners reward sequence CRew: 1) = Ei re(at, zig) (see the appendix for details about how these estimates are computed). Further, using confidence bounds Dt - (o) from Equation 1, we can constructs a confidence interval for CRew, t) as CRew: t) D2(t to), CRew, t) + D,(t to) If the confidence intervals for two learners with indices < j are more than the h-stable regret bound of apart, see Equation 2, then deem all learners with index up to not h-stable and restart the algorithm with a reduced set of base learners.
This kind of elimination condition has already been used in stochastic environments [27, 13, 31], but it requires substantially more care in an adversarial setting. In settings with stochastic rewards (even with corruption, c.g., [31]), no learner can achieve rewards that are significantly higher than the optimal policy. In contrast, in the adversarial setting, it is possible to have negative regret against any fixed policy. Thus, if we were to use the elimination condition in Equation 2 with our base learners as is, then we may eliminate an h-stable base learner i when another base learner j has negative regret against the best fixed policy प.. This could in turn lead to undesirable regret in subsequent epochs when only learners with R(II, >> R(II,) are left.
Linking Base Learner Performances. To address this issue, link the performance of base learners. Instead of instantiating each learner A; with its original policy set HI; we apply it to an extended problem with M - additional actions āري1, .i+2:...,ūū âMs and an extended policy set IT, that includes all original policies, along with policies that only choose one of the additional actions ā, that is TI 2 U (1 (ā++1)... .... (āar) }}. Whenever base learner A.; chooses one of the additional actions ā, then the action proposed by A is followed. Essentially, running each base learner with choose to follow the actions proposed by any learner with higher index in the hierarchy. The benefit of linking base learners this way is that each base learner now not only competes against the best fixed policy in their set, but also against all learners above them in the hierarchy. Thus, if A, is stable and extendable (see Definition 3), then it satisfies regret bound of the form
such an extended action set allows
B Banny (re(a, - Eaway (re(a, [op]]]=O(((R)
=Ō (R(IL)))
t f- to
Pi
against any learner Ag with > i. As a result, since the LHS of Equation 3 is approximately CRew (to. t) - CRew, (to. t) + (st.,. + Dy t), the test in Equation 2 cannot trigger for such Ad, and only base learners that are not h-stable or extendable can be eliminated.
In Appendix C, we show that our regret balancing algorithm achieves the following regret bound: Theorem 4. Consider a run of Algorithm 1 with Arbe( 1,0) and M base algoritlmss with 1 S R(T < .... S R((TM) where πT, is the extended version of policy class II, with (M - i) additional actions. Then with probability at least poly (M)8 the regret Reg(t, Ias) for all rounds t 2 i, is bounded by
We here naturally extend the domain of linked actions re(ās, 2e) re(a), xz) for all i E [M].
7

---

((Ri))) Vi, M R(lL,, ) R(iL))
y i ti
where i, the smallest index of the base algorithm that is h-stable.
In most settings, the complexity R(TT;.) VM and the first term dominates. This regret recovers m(ii))
the expected regret guarantees of Corral [2] when used with learning rates that do not require bounds. To the best of our knowledge, Theorem the first high-probabilityy regret bound for adversarial model selection. To illustrate our result, consider to common problem of model selection with nested model classes of dimensions d: = 2' for i [M,] discussed in the introduction. We can use GeometricHedge.. as base learners which are h-stable and extendable if adapted (see Appendix B) and the complexity of extended policy classes R(II.) R(II,) + MM - S d; + .M is not much larger than those of the original policy classes. Arbe with such base learners achieves a regret bound of order (df vt) up factors of M and log-factoo fag-factors which are typically small.
knowledge of i, but as stronger high-probabile
5 Adversarial Model Selection with Best of Both Worlds Guarantees
In this section, we present our algorithm for adversarial model selection that preserves a logarithmic regret guarantee in case it interacts with a stochastic environment with gap A > O. In order to achieve such a best-of-both--won both-worlds guarantee, we will combine our adversarial regret balancing technique with the algorithmic strategy of Bubeck and Slivkins [11]. The main result for our algorithm is:
Theorem 5. Consider a run of Algorithm 2 with inputs to = O, arbitrary policy policy मे E II and M base learners . ..3. Then with probability least poly( M),, the following two conditions hold for all 2 M simultaneously. In any adversarial or stochastic environment B, the regret is bounded as
((MM-M))) + R(T,)) R(II)
Via R(TT,.) + in) 1m)
Reg(t, (T)==Q
If B is stochastic and there a unique policy with gap A 0, then the pseudo-regret bounded as,
R((Iw)
In(t) In R(U, ) PR(N,))
M2i
PseudoRega (t, 11y)= = o
In²
A
R(ī))² A
A6
(5)
The algorithm has the same regret bound as Arbe up to a VIn factor. However, in addition, also maintains poly-logarithmic pseudo-regret if the environment is stochastic and the best policy exhibits a positive gap. Our pseudo-regret bound depends polynomially on R(ITxr in contrast to the R(II,) dependency for the adversarial regret rate. This may seem undesirable but, as mentioned in Section 2.1, model selection in stochastic environments with poly( [RII,, In ([II)))))) lmit)
A regret is impossible (see Appendix A), let alone while maintaining a sest-of-both-worfee guarantee with vT regret in adversarial environments. Hence, our algorithm achieves the best kind of guarantee we can hope for, up to improvements in the order of polynomial dependencies.
Our algorithm proceeds in two distinct phases. The first, Arbe-Gap shown Algorithm 2 designed to identify suitable candidate for the optimal policy and to estimate its gap. If such a policy that performs significantly better than any other policy emerges, the algorithm enters the second phase, Gapeloii which hones in on this policy by playing it most of the time while monitoring its regret in case the environment turns out to be adversarial after all (in which case we simply run Arbe). We now describe both phases.
5.1 First Phase: Candidate Policy Identification and Gap Estimation
This goal this phase is to always maintain the desired adversarial model selection regret guarantee and simultaneously identify the gap between the best policy and the rest if one exists. To achieve the first goal, we employ the regret balancing and elimination technique of Arbe, see Lines 3-11 of Algorithm 2 which are virtually identical to Algorithm 1.

---

To do so, regret rate overall and each policy but x* will incur on average at least a regret of A per round. Hence, in order maintain that regret, Arbe- Gap must select "' in the majority of all rounds when violating the Algorithm 2: Arbe-Gap(o,,, n, (As)
Input:
failure probability 6, timestep tu, focus policy म. number of (re)starts n, learners (Ai))
Set I[ = MM ) and AM- as a copy of AM with policy class MI
Initialize base learners Ag; As+1,-.. AM+1 with extended policy classes II,, I1 ................................ MT
m( for all (8....; M 1}, and p. for i < Set sampling probabilities Pj Σ5 A(I;)
5 for round = to + 1, + 2.... do Sample base learner index b Categorical(
.PM)
Get context 24 and compute at (-(r) the action each base learner A; proposes for 2t.
Play action ae = a (resolve linked actions necessary) and receive reward rr(a vx) Update all base learners AS with reward ((b==))r((ae,as)
Equation holds between A. A, for & I j Pi
10
M then restart algorithm by running Sibe-Gapte 0, R, (A++1, AMM)
// Gap Test: AM better than AM+1??
Set W(tu, () (V In mit-ro) + In nlatt-ce2
(V pxrit-oo
R(U
12
CRew Set Å, (fo.)) - -CRww ((toa)) W(to. 8)
13
1-10 if (W((o, S A. ? then
Run cape-GapExploit (Appendix D) with inputs 6, tu t, AM. क and A A. Run Arbe with inputs s.
15
16
// New Candidate Policy Test
17
31 if a policy π E HI \ { has been selected in more than
4 of all 2 rounds then restart algorithm by running Arbe- Sabe-Gap(da. 8, t, n, n + 1, (A.)
18
For the second goal, determining the gap, Arbe- Gap maintains a candidate स E 1l for the optimal policy and estimates its gap as follows. The learner hierarchy A....., Am is augmented at the top with additional learner AM+1 operating
the policy class 11 = 1l \ { Since A identical to As except that does not have access to म. we can obtain gap estimate for by monitoring the difference in reward estimates CRew M+1 M+1 and CRew M of A and AM. In fact, S, in Line 13 lower confidence bound on the difference between the best policies in II and Il \ { and thus, the gap of We test at every round whether A exceeds its confidence width 2Woto. t). If this test triggers then स must have positive gap A of order W W(to, t) and further, A, must be a multiplicative estimate of A, that is, A < A 23, The latter holds, because A + 2W t) an upper-confidence bound on A and the test condition implies 23, 2 Â, 2W 2W(to.3 t) 2 A. Since in this case, we have determined that से is optimal with a gap of order A, we can move on to the second phase Arbe- Gapploitt discussed later.
Assume the candidate policy î is indeed optimal and exhibits positive gap A. Since A concentrates around A at a rate of W(tg, t) ~ poly(Rar(Hlx)) the condition of the gap test in Line 14 must Vt-lo trigger after at most - tu S poly(Rar((aar)) rounds. Finally, since Arbe-Gap always maintains the (ttiiii,.ttt (oly( /t- to adversarial regret rate, the total pseudo-regret incurred until the test triggers is
A
of order poly ( leading to the second term in the bound in Equation 5.
With the techniques above, we can reliably detect a positive gap if the candidate policy â exhibits one. It remains to identify a suitable candidate से of the optimal policy x² in stochastic environments. the following two observations: Arbe- Gap maintains poly / adversarial
t w( (oly( ))
Otherwise the regret grows l(tA)

---

adversarial rate. To leverage this observation and identify suitable candidate policy म. Line 17 of Algorithm 2 always checks whether there policy other than the current candidate policy that has been selected in at least 3/4 of all rounds." If so, the algorithm is restarted with this policy as candidate म. One can show that there are at most (In 1) restarts due to candidate policy switches, only increasing the adversarial regret rate of Arbe-Gap by a factor of O D(VInt) compared to Arbe's. s. Our candidate policy selection approach is similar to that by Wei et al. [31] for the corrupted reward setting but they require each adapted base learner to achieve logarithmic regret rate in the first place. Instead, approach only requires adversarial regret rate from the base learner.
5.2 Second Phase: Exploitation
Since each base learner only needs to satisfy a VT regret rate even in stochastic environments, generally cannot hope to recover logarithmic pseudo-regret by only selecting among them. For logarithmic pseudo-regret, we need to ensure that the given policy क with gap estimate A is played sufficiently often. However, we also need to monitor its regret against all other policies in case the environments turns out to be adversarial. If at any point, fails to maintain a gap of order A, we can conclude that the environment is adversarial. Then Grae-Gap returns and we simply play an instance of Arbe (Line 16 of Algorithm 2).
We will present a brief summary of the main intuition behind our exploitation phase approach here and defer a longer discussion and the detailed pseudo-code to Appendix D. In each round, we play policy से with probability approximately
poly( and with the remaining probability A
))ly(R(Har)) a version of base learner AM with policy class HI \ (+).
If the environment is indeed stochastic, then मे = x* does not incur any pseudo-regret and the total regret in other t' ss t. (oly(R([Ix))) x polyt ([lls) rounds can be bounded as t' A + Rega, (t',Ily.
A
(+)) R poly(R([x<)) It)... The first term is the regret of the best policy in 1L \ (n] and the second term is the regret of AM against that policy. Since AM is h-stable on 11 \ {.. its regret against that policy is at most poly(R(II,) )) Vt and we get the desired pseudo-regret.
To ensure good regret in the adversarial case, we need to detect quickly enough when fे does not exhibit a performance gap anymore and fall back a fully adversarial algorithm. Similar to A, in the first phase, we use lower confidence bound on the average performance gap and continuously test whether falls below S. This simple approach would give /t adversarial regret but may exhibit a poly( R[( )) dependency. Fortunately, we can avoid this dependency and retain the desired model selection regret rates by extending the intuition above to also test an upper bound on the gap. For details, see Appendix D.
6 Conclusions
We have described and analyzed novel model selection scheme for bandit algorithms that benefits from best-of- best-of-bothh-ee both- worlds high probability regret guarantees. Though not restricted linear bandits, our machinery can be specifically applied to adversarial/stochastic linear bandit tasks, where model selection performed on the unknown dimensionality of the linear reward function. This has required extending the regret balancing technique of model selection from stochastic to adversarial rewards and very careful handling of the associated mis-specifiiatiinn tests. The hase learners aggregated by our meta-algorithh case, along with regret stability and action space extendability properties which we have shown are satisfied by (variants of) known algorithm in the bandits literature.
have to satisfy an anytime high probability regret guarantee in the adversarial
Our best-of-both world model selection regret guarantees cannot in general be improved, specifically in stochastic environments with gaps, where it is generally impossible to obtain log t-like model selection bounds that only depend on the complexity of II, On the other hand, it would be nice to see in Theorem 5 better polynomial dependence on M and R( Also, it might be possible to adapt Arbe- Gap to work with adversarially corrupted stochastic rewards while doing model selection on the complexity of the models. We leave this as a future research direction.
"Due to linking learners, there is slight ambiguity in defining the selected policy per round. We here determine the selected policy as the policy chosen by the learner that eventually picked at after resolving linked actions.
10

---

References
[1] Y. Abbasi- Abdkoii-addkor, A. Pacchiano, and M. Phan. Regret balancing for bandit and rl model selection. arXiv preprint 0044:9000.05491, 2020.
[2] A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire. Corralling band of bandit algorithms. arXiv preprint arXiv: 1612.06661 2016.
[3] A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
[4] R. Arora, T. V. Marinov, and M. Mohri. Corralling stochastic bandit algorithms. arXiv preprint arXiv:2006.0990 09255, 2020.
[5] P. Auer and C.-K. Chiang. An algorithm with nearly optimal pscudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory, 2016.
[6] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal Computing, 32(1), 2003.
[7] Bartlett, V. Dani, Hayes, S. Kakade, A. Rakhlin, and A. Tewari. High-probabiliyy regret bounds for bandit online linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory-COLT 2008, pages 335-342. Omnipress, 2008.
[8] A. F. Bibaut, A. Chambaz, and M. J. van der Laan. Rate-adaptive model selection over a collection of black-box contextual bandit algorithms. arXiv preprint arXiv:2006.03665 2020.
[9] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint 1204.5:204..722 2012.
[10] S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference Learning Theory, 2012.
[11] S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pages 42-1. JMLR Workshop and Conference Proceedings, 2012.
[12] N. Chatterji, V. Muthukumar, and P. Bartlett, Osom: A simultaneously optimal algorithm for multi-armed and linear contextual bandits. In International Conference on Arlificial Intelligence and Statistics, pages 1854, 2020.
[13] A. Cutkosky, C. Dann, A. Das, C. Gentile, A. Pacchiano, and M. Purohit. Dynamic balancing for model selection in bandits and rl. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2276-2285, PMLR, 2021.
[14] D. Foster, C. Gentile, M. Mohri, and J. Zimmert. Adapting to misspecification in contextual bandits. In Advances in Neural Information Processing Systems, 2020.
[15] D. Foster, A. Krishnamurthy, and H. Luo. Model selection for contextual bandits. In Advances in Neural Information Processing Systems, pages 14741-14752, 2019.
[16] A. Ghosh, A. Sankararaman, and K. Ramchandran. Problem- complextt adaptive model selection for stochastic linear bandits. arXiv preprint arXiv:2006.02612 2020.
[17] A. Gupta, T. Koren, and K. Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, 2019.
[18] S. R. Howard, A. Ramdas, J. Mc Auliffe, and J. Sekhon. Uniform, nonparametric, non- asymptotic confidence sequences. arXiv preprint arXiv: 2018.
[19] S. Howard, Ramdas, McAuliffe, and Sekhon. Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317, 202.
[20] T. Lattimore and C. Szepesvári. Bandit algorithms. preprint, page 28, 2018.

---

[21] C. Lee, H. Luo, W. Chen Yu, M. Zhang, and X. Zhang. Achieving near instance-optimaling and minimax-optiman in stochastic and adversarial linear bandits simultaneously. Proceedings of the 38th International Conference Machine Learning, ICMI,, volume 139 of Proceedings of Machine Learning Research, pages 6142-6151. PMLR, 2021.
[22] Lee, A. Pacchiano, V. Muthukumar, W. Kong, and Brunskill. Online model selection for reinforcement learning with function approximation. In International Conference Artificial Intelligence and Statistics, pages 3340-3348. PMLR, 2021.
[23] Lykouris, V. Mirrokni, and Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposiun Theory of Computing, 2018.
[24] T. Marinov and J. Zimmert. The pareto frontier of model selection for general contextual bandits. In Neurips, 2021.
[25] G. Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. arXiv preprini /50600037 2015.
[26] A. Pacchiano, C. Dann, C. Gentile, and P. Bartlett. Regret bound balancing and elimination for model selection in bandits and rl. arXiv preprint arXiv:2012. 13045, 2020.
[27] A. Pacchiano, M. Phan, Y. Abbasi Yadkori, A. Rao, J. Zimmert, Lattimore, and C. Szepesvari. Model selection in contextual stochastic bandit problems. arXiv preprint arXiv:2003.01704, 2020.
[28] Y. Seldin and G. Lugosi. An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory, 2017.
[29] Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning. 2014.
[30] C.-Y. Wei and Luo. More adaptive algorithms for adversarial bandits. In Conference Learning Theory, 2018.
[31] C.-Y. Wei, C. Dann, and J. Zimmert. A model selection approach for corruption robust reinforcement learning. arXiv preprint arXiv:2 10.03580, 2021.
[32] Y. Zhu and R. Nowak. Pareto optimal model selection in linear bandits, 2021.
[33] Zimmert and Y. Seldin. An optimal algorithm for stochastic and adversarial bandits. In 22nd International Conference on Artificial Intelligence and Statistics, 2019.
[34] J. Zimmert and Y. Seldin. Tsallis-inf: inf: An optimal algorithm for stochastic and adversarial bandits. Mach. Learn. Res, pages 22:28-1, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work is of purely theoretical nature, and are not aware of any potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See in particular the definitions and desiderata in Section 2.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are provided
in the appendix.
12

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "OgH7pH71lOo", "reviewer": "Reviewer_1K6U", "summary": "This work considers model selection from a set of contextual bandit algorithms with nested policy classes. Each of these base learners has a known regret guarantee, that may or may not hold. The environment may be either stochastic with a reward gap or adversarial, and a best-of-both-worlds high-probability bound is provided for the proposed meta-algorithm. On each round this meta-algorithm chooses a base learner with probability that depends on their known bounds. It then performs mis-specification tests and eliminates the learners that violate their regret bounds. Additionally, it performs a test to reliably detect the stochastic environment and switch to exploitation mode in this case. An important building block is extension of the policy class of each of the base learners to include special actions that delegate the decision to another base learner (with a larger policy class). This allows the elimination test to work in the adversarial environment. In the case that the environment is known to be adversarial, the algorithm can run without the stochastic detection test, in which case it achieves a tighter bound. This bound is a high-probability version of the one known from prior art.", "questions": "Can you provide an example of contextual base algorithms (that actually use the context) that are suitable for this framework?", "limitations": "The assumptions are clearly stated. A lower bound for stochastic case is provided.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality** To the best of my knowledge, this is the first work to provide best-of-both-worlds guarantees for bandit model selection. It extends the idea of regret balancing to the adversarial environment by modification of the base learners and carefully designed tests.\n\n**Quality** The proofs are provided in the appendix, but I did not verify their soundness. The proof sketches in the main paper seem reasonable. The dependence of the stochastic case bound on the complexity of the largest policy class is justified by proving a lower bound.\n\n**Clarity** This work is highly theoretical, and therefore it is not surprising that it is not easy to understand. However, some improvements to the clarity and the organization would be helpful. For example, the detailed example in lines 46-65 is too technical to be part of the introduction, and is better suited for section 2. Subsection 2.1 feels out of scope for section 2. The extension of the policy space and linking of the base learner performances need more explanation. For example, before the definition of extendability, linking of the learners can be mentioned to explain how the extendability will be used by the meta-algorithm.\n\n**Significance** Demonstration of best-of-both-worlds bounds is important for the understanding of the underlying relations between different settings and eventually designing practical algorithms that can optimally exploit the properties of the environment. On the other hand, switching between operation modes based on tests is intuitively less generic than a framework that tunes its parameters continuously. \n\nSome more discussion on future directions would help to realize the significance of this work. Can it be potentially generalized to other partial information settings? Can some additional assumptions improve the stochastic regret bound?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8cCx6wAYwFs", "reviewer": "Reviewer_Bk6N", "summary": "The authors study the best-of-both-worlds guarantees for model selection in linear bandits. The paper proposes a novel algorithm called Arbe, which achieves the first high probability regret bound for adversarial model selection. In addition, the paper proposes a two-stage algorithm called Arbe-Gap, which achieves best-of-both-worlds high probability regret bounds.", "questions": "1. Can the proposed algorithms be extended to the infinite arm setting? If not, what is the main difficulty?\n2. Does Arbe-Gap work for the stochastic rewards with adversarial corruptions?", "limitations": "Since the paper does not provide any empirical comparisons, it is still unknown whether the proposed algorithms are practical.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The writing is mostly clear.\n2. The best-of-both-worlds guarantees for model selection is an interesting and important problem.\n3. The proposed algorithms are novel. It is the first algorithm that achieves high probability best-of-both-worlds regret bounds for linear bandits with nested model classes.\n\nWeakness:\n\n1. Both stochastic and adversarial regret bounds are suboptimal with respect to the dimension of the reward vectors.\n2. The paper does not contain numerical experiments for the proposed algorithms.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7jxB9Q8FxXN", "reviewer": "Reviewer_FmBH", "summary": "This work studies the problem of model selection with bandit feedback in the presence of a sequence of policy classes, in other words, a monotonically increasing sequence of sets of polices. The goal is to achieve the \"best of both worlds\" high-probability guarantee between the stochastic world and the adversarial world, in other words, ensuring $polylog(T)$ regret for stochastic setting and $\\sqrt{T}$ regret for the adversarial setting. It follows similar ideas of Lee et al. (2021) and Wei et al. (2021) and applies the idea of regret balancing technique discussed in Cutkosky et al. (2021) to design the algorithm Arbe for model selection. To achieve this, the authors extend the techniques to adversarial rewards: they have a few necessary constraints on the algorithms, and enhance the test for mis-specification. ", "questions": "1. The idea is very similar to the pervious work of Lee et al. (2021) and Wei et al. (2021). I wonder if the authors could emphasize the specific adjustment they made to achieve the best of both worlds guarantee in this setting and what's the specific difficulty this new problem has. \n\n2. Would like to confirm that line 6 of Arbe-GapExploit means that the whole algorithm would only deal with \"adversarial\" setting and would not go to ArbeGapExploit phase anymore. \n\n3. Can we extend this approach to achieve results in an intermediate setting (e.g., corruption setting)? ", "limitations": "None. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work provides the first algorithm which achieves the best of both worlds high-probability guarantees for model selection within (linear) bandit scenarios. The problem is well-defined and very general (for h-stability and extendability). The techniques which are further improved from the previous work of Lee et al. (2021) and Wei et al. (2021) following the idea of regret balancing are very interesting, and may be applied in solving other problems. \n\nOverall, this work does not have any other specific weakness. The paper is clearly written and easy to understand. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept