Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization
Authors: Sanath Kumar Krishnamurthy
Ruohan Zhan
Susan Athey
Emma Brunskill
Venue: NeurIPS 2023 poster (2023)
Keywords: Contextual Bandits; Adaptive Experimentation; Simple Regret; Reinforcement Learning
TL;DR: Flexible contextual bandit algorithms for simple and cumulative regret

Abstract: In many applications, e.g. in healthcare and e-commerce, the goal of a contextual bandit may be to learn an optimal treatment assignment policy at the end of the experiment. That is, to minimize simple regret. However, this objective remains understudied. We propose a new family of computationally efficient bandit algorithms for the stochastic contextual bandit setting, where a tuning parameter determines the weight placed on cumulative regret minimization (where we establish near-optimal minimax guarantees) versus simple regret minimization (where we establish state-of-the-art guarantees). Our algorithms work with any function class, are robust to model misspecification, and can be used in continuous arm settings. This flexibility comes from constructing and relying on “conformal arm sets" (CASs). CASs provide a set of arms for every context, encompassing the context-specific optimal arm with a certain probability across the context distribution. Our positive results on simple and cumulative regret guarantees are contrasted with a negative result, which shows that no algorithm can achieve instance-dependent simple regret guarantees while simultaneously achieving minimax optimal cumulative regret guarantees.

Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization
Sanath Kumar Krishnamurthy Management Science and Engineering
Ruohan Zhan
Industrial Engineering and Decision Analytics Hong Kong University of Science and Technology
Stanford University sanathsk@stanf ord. edu
rhzhan@ust. hk
Susan Athey
Emma Brunskill
Graduate School Business Stanford University athey@stanfor ord edu
Computer Science Department
Stanford University ebrunêcs.c stanf edu
Abstract
In many applications, e.g. in healthcare and e-commerce, the goal of a contextual bandit may be to learn optimal treatment assignment policy the end of the experiment. That is, to minimize simple regret. However, this objective remains understudied. We propose a family of computationally efficient bandit al- gorithms for the stochastic contextual bandit setting, where a tuning parameter determines the weight placed on cumulative regret minimization (where we estab- lish near-optimal minimax guarantees) versus simple regret minimization (where we establish state-of-the-art guarantees). Our algorithms work with any function class, are robust to model misspecification, and can be used in continuous arm set- tings. This flexibility comes from constructing and relying on "conformal arm sets" (CASs). CASs provide a set of arms for every context, encompassing the context- specific optimal arm with a certain probability across the context distribution. Our positive results on simple and cumulative regret guarantees are contrasted with a negative result, which shows that no algorithm can achieve instance-dee dependen sim- ple regret guarantees while simultaneously achieving minimax optimal cumulative regret guarantees.
Introduction
Learning and deploying personalized treatment assignment policies is crucial across domains such as healthcare and e-commerce [29, 25]. Traditional randomized control trials (RCTs), while foun- dational for policy learning [4. 7], can be inefficient and costly [30]. This motivates the study of adaptive sequential experimentation algorithms for the stochastic contextual bandit (CB) settings. The algorithm interacts with finite sequence of users drawn stochastically from fixed but unknown distribution. At each round, the algorithm receives a contexí (a user's feature vector), selects an action, and gets a corresponding reward. At the end of this adaptive experiment, the algorithm outputs learned policy (mapping between contexts and actions).
Our algorithms are designed with the dual objectives of minimizing simple regret and cumulative regret. Simple regret quantifies the difference between the expected rewards achieved by the optimal policy and the policy learned at the conclusion of the experimental process. In contrast, cumulative regret encapsulates the summation of differences between the expected rewards generated by the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

optimal policy and the exploration policies employed at each sequential round of decision- decision-making. ! Although there are many settings where simple regret is an important consideration, the majority of research in the contextual bandit field has focused on the minimization of cumulative regret. To the best of our knowledge, there is no general computationally efficient algorithm for pure exploration objectives like simple regret minimization in the contextual bandit setting. Further, there has been relatively little work so far into algorithms that explore the trade-off between multiple objectives like cumulative regret and simple regret (though see [3, 9, 37J for studies that address this empirically or juxtapose minimizing cumulative regret with estimating treatment effects or arm parameters). Our work seeks to address these gaps. We show that there is a trade-off between simple and cumulative regret minimization (formalized later in a lower-bound result). To navigate this trade-off, we proposes new algorithm called Risk Adjusted Proportional Response (RAPR) with a tuning parameter w E [1, K], which governs the weight placed on the two objectives." 2 The algorithm is general- purposs (in that it can address any user-specified reward and policy classes), ensures near-optimal guarantees, and is also computationally efficient.
Types of guarantees. In our analysis, we consider two different types of bounds on simple and cumulative regret, worst-case and instance-dependent guarantees. Here instance-dependent guarantees refer to bounds that surpass worst-case rates by exploiting instances with large gaps between the conditional expected rewards of the optimal and sub-optimal arms. Recent work by [11] has shown that it is not possible for contextual algorithms to have instance-dependent guarantees on cumulative regret (without suffering an exponential dependence on model class complexity); ; the authors instead develop algorithms that achieve minimax optimal (worst case optimal) cumulative regret guaranteess (with square-root dependence on model class complexity). [26] developed the first general-purpon contextual bandit algorithm for pure exploration, and their algorithm achieved instance- dependeen guarantees. They also show that instance -eeennddd best policy identification guarantees must come the cost of worse than minimax optimal cumulative regret (discussed in detail later). We show a similar lower bound on cumulative regret for algorithms that achieve better instance-dependent simple regret guarantees, and propose the first family of algorithms that flexibly navigate such trade-offs.
Overview of our guarantees. The simple regret guarantees of RAPR are never worse than the minimax optimal rates (Theorem 2). Depending the instance, RAPR achieves simple regret guarantees that are up to O(1/ vw) times smaller compared to minimax optimal rates (Theorem 2). This improvement factor of O(1/ /w) over minimax optimal rates is asymptotically achieved for instances where realizability holds (the reward model class is well specified) and the gap between the best and second best arm in terms of conditional expected reward is at least A > 0 at every context (best-case instance in Theorem 2). RAPR provides these instance-dependent guarantees without the knowledge of any instance information. Unfortunately, the corresponding cumulative regret for the above instances is a factor of O(vw) times larger compared to minimax optimal rates (Theorem 1). The cumulative regret guarantees of our algorithm only degrade relative to the minimax optimal rate if the instance allows for better simple regret guarantees. Our lower bound (Theorem 3) considers the instances described above with A 0.24 (the gap between best and second best arm in terms of conditional expected reward). Theorem 3 shows that, for any algorithm that bounds the simple regret on these instances to 0(1/ /W) of the minimax optimal rates, its cumulative regret will be at least 12( (W) times the minimax optimal rates. RAPR thus achieves a near-optimal trade-off between guarantees on simple vs cumulative regrets when T is large enough. The trade-off contrasts with non-contextual bandits, where successive elimination ensures improved (compared to minimax) instance-dependent guarantees for both simple and cumulative regret [10, 35].
Types of CB algorithms. Contextual bandit algorithms broadly fall into two categories: regression- free and regression- based. Regression frresssooonneeeeeeeee algorithms create an explicit policy distribution, randomly choosing policy for decision decision-making at any time-step [2, 5, 8, 26]. While these algorithms provide worst-case cumulative regret guarantees [2, 5, 8] or instance- -deendded PAC guarantees for policy learning [26] without additional assumptions, they can be computationally intensive [11]: they require solving and storing the output of ((poly(T)) cost-sensitive classification (CSC) problems [21] at every epoch (or update step). In contrast, regression-basee algorithms [e.g., 1, 11, 34] construct a
'Our formal definition of simple regret compares against the best policy in our policy class, while our cumulative regret definition compares against the global optimal policy (induced by the true conditional expected reward model). The reason for this discrepancy is because we use a regression based approach (due to computational considerations) for constructing our exploration policies. 2 KK' is the number of arms for the finite arm setting.
2

---

conditional arm distribution using regression estimates of the expected reward, allowing for methods that need only solve (1) regression or CSC problems at every epoch (or update step). Traditionally. these algorithms relied on realizability assumptions for optimal regret guarantees, but recent advances allow for misspecified reward model classes [6, 12, 22]. We develop regression- based algorithms and do not assume realizability. RAPR is the first general-purpon regression-based algorithm with attractive pure exploration (simple regret) guarantees.
Overview of our algorithm. We now describe the RAPR algorithm in more detail. We first define a surrogate objective for simple regret, the optimal cover, which inversely proportional to the probability that the bandit exploration policy chooses the arm recommended by the unknown optimal policy. The optimal cover bounds the variance of evaluating the unknown optimal policy under our exploration policy. This surrogate objective can be minimized by appropriately designing our exploration policy/action selection kernels. To maintain the attractive computational properties of regression-based algorithms, RAPR does not construct an explicit distribution over policies as that distribution would have large support and would be computationally and memory intensive to maintain. Instead, the goal of minimizing the optimal cover is attained by directly constructing a distribution over arms for each arriving context. This in turn builds on a novel general-purpon uncertainty quantification at each context. Much of the existing literature constructs confidence intervals with point-wise guarantees, but existing approaches to constructing them rely on assumptions like linear realizability. For general function classes, these intervals may be too wide and are often computationally expensive to construct. To overcome this issue, we develop Conformal Arm Sets (CASs), which are set of potentially optimal arms at each context. This uncertainty quantification is regression-basee baased and computationally efficient to construct; it's general-purpont and shrinks at "fast rates" (with square-root dependency these sets come with some risk of not containing the arm recommended by the optimal policy at every context. Nevertheless, we can use this uncertainty quantification to construct a distribution over arms at each context that helps us minimize the optimal cover by balancing the benefits and risks of relying on these CASs. The unavoidable trade-off between our simple and cumulative regret guarantees an artifact of these risky sets. Beyond allowing us to trade off simple and cumulative regret guarantees, the flexibility of the approach also helps us extend to continuous arm settings and allows us to handle model misspecification.
expected squared error bounds for regression). Unfortunately,
Other Related Work. Our work connects to the literature on pure exploration, extensively studied in
MAB settings (see overview in [24]). [10, 15) study elimination- based algorithms for fixed confidence
best-arm identification (BAT). [19, 32] study variants of Thompson Sampling with optimal asymptotic designs for BAI [18] propose sequential halving for fixed budget BAI Our algorithm provides fixed confidence simple regret guarantees and can be seen as generalization of successive elimination [10] to the contextual bandit setting. The key technical difference is that it is often impossible to construct sub sub-gaussian confidence intervals on conditional expected rewards. The uncertainty quantification we use is similar to the notion of conformal prediction (see [36] for detailed exposition). Until recently, pure exploration had been nearly unstudied in contextual bandits. [38] provide static exploration algorithm that achieves the minimax lower bound on sample complexity for linear contextual bandits. [26] then provided the first algorithm with instance-dependent (c. 8)PPAC guarantees for contextual bandits. This algorithm is regression-free (adapts techniques from (2)) and requires a sufficiently large dataset of offline contexts as input. Hence, unfortunately. it inherits high memory and runtime requirements [See 11, for a more detailed discussion]. However, these costs come with the benefit that their notion of instance dependence leverages structure not only in the true conditional expected reward (as in Theorem 2) but also in the policy class (similar to policy disagreement coefficient [13]). They also prove a negative result, showing that it is not possible for an algorithm to have instance-dependent (0, PPC guarantees and achieve minimax optimal cumulative regret guarantees. Our hardness result is similar but complementary to their result, for we show a similar result for simple regret (rather than their (0, PPC sample complexity). 3 Our work also recovers some cumulative regret guarantees for the continuous arm case [27, 40], with new guarantees on simple regret and robustness to misspecification. Note that our restriction to "slightly randomized" policies for the continuous arm case results in regret bounds with respect to a "slightly randomized" (smooth) benchmark [see 40, for smooth regret].
'In (c, 5) PAC sample complexity results, given an input o), the objective to minimize the number of samples needed in order to output an c-optimal policy with probability at least - (a "fix accuracy, compute budget" setting). In contrast, in our simple regret case, we consider how to minimize the error e as the number of samples increases.
3

---

1.1 Stochastic Contextual Bandits
We consider the stochastic contextual bandit setting, with context space X. (compact) arm space A. and fixed but unknown distribution D over contexts and arm rewards. Dx refers to the marginal distribution over contexts, and T signifies the number of rounds or sample size. At each time t E [T]+ the environment draws a context zez and a reward vector r E j0, 1 from D; the learner chooses an arm a, and observes a reward ri (ax). To streamline notation for discrete and continuous arm spaces, we consider finite measure space (A, Σ, 11) over the set of arms, with K shorthand for (u(A). For case of exposition, we focus on the finite/discrete arm setting. Here A = [K] and p is the count measure, and (xS) = |S] for any S C A. A (deterministic) policy т maps contexts to singleton arm sets 2, == {ala E AJo. With some abuse of notation, we also let ι refer to the kernel given by x(a[2)) [a <(x)). An action selection kernel (randomized policy) p : A x X - [0, 1] is probability kernel that describes a distribution p(-|z) over arms at every context x. We let D(p) be the induced distribution over X' x A x [0, 1], where sampling (z, a, a,)( D(p) is equivalent to sampling (z. r) ~ D and then sampling a ~ p(-|x).
A reward model f maps X x A to [0. 11, with ((r,a) == ED [a) a x:| denoting the true conditional expected reward model. Our algorithm works with a reward model class F and a policy class 11. For given model f and an action selection kernel p. we denote the expected instantaneous reward of p with f as Ry (p). We write Ry. (p) as R(p) to simplify notation when no confusion arises. The optimal policy associated with reward function is defined as xT²
Ry(p):= = E
E [f(x,a)) and y E arg max RT( D~Dx amp(-1a)
x
The policy y induced by f E F is assumed to be within policy class II without loss of generality." For any S S A, with some abuse of notation, we let f(x, S) = laes fxz a a)dp(a)/p(()), Note that Ty(x) E arg maxses, f(x, for all x. The regret of a policy π with respect to f is the difference between the optimal value and the actual value of æ,, denoted as (TT == Ry(Ta) (TT. Finally, we let n* denote the optimal policy in the class II and let Regn(-) denote the regret with respect to T That is, n- E arg max R(T) and (egn(T) == R(T*)= R(x).
Objectives. Contextual bandit algorithms adaptively construct action sampling kernels (exploration policies) (P:heetr) used to collect data over the rounds. At the end of the adaptive experiment, the adaptively collected data is used to learn policy á IT. We study two main objectives measure quality of these outputs: [Objective 1] Cumulative regret minimization. Cumulative regret (CRegr) is given by CRegr == rr= Reg,.. (Pt). It compares the cumulative expected reward obtained during the experiment with the expected reward of the policy (TT induced by the true conditional expected reward (f*). We seek to minimize cumulative regret which is equivalent to maximizing cumulative expected reward during the experiment. [Objective 2] Simple regret minimization. Simple regret is given by (f). It compares the expected reward of the learnt policy â E Il against the value of the optimal policy in the class II. We seek to minimize simple regret which is equivalent to maximizing expected reward of the policy learnt at the end of the experiment. To understand the kind of exploration kernels (fp, he(()) that help with policy learning, we now identify a surrogate objective for simple regret (called optimal cover) that is in terms of the kernels used for exploration.
Definition 1 (Cover). Given a kernel and a policy x, we define the cover of policy π under the kernel p to be,
<(a|=)
V(p, :=
E
(1)
a~ a-Dx
[p(a|x)
Additionally, for any pair kernels (p, q). we let (p, q) =- Ez Dx Bx.DDr.ngtill www.or/glllllllll/laaaaoo Finally, we use the term optimal cover kernel p to refer to V(p, T*).
The cover measures the quality of data collected under the action selection kernel p for evaluating a given policy π and bounds the variance of commonly used unbiased estimators for policy value
"For any n E N+, we use notation [m] to denote the set {l,..., m
$ 'Here Σ is a o-algebra over A and μ is a bounded set function from E to the real line.
'The introduction of E1 is to allow for easy generalization to the continuous arm setting.
7 'subject to any tie-breaking rule.
NNote that lI may contain policies that not induced by models in the class F.

---

[e.g., 2, 14, 39]. In particular, the cover under optimal policy / ET= Vip,, T) can be treated as surrogate objective for simple regret minimization (proven in Appendix E.2), which particularly instructional in designing our algorithm to minimize simple regret.
Extending notation to continuous arms. In the continuous deterministic policies can be infeasible without extra assumptions [28]. Thus, we focus on "slightly randomized" policies by generalizing 21 be the arm sets with measure one (2) := {S E 21p(S) 1J). The granularity of these sets can be adjusted by scaling the finite measure which also affects the value of K (u(A). We then continue defining policies be maps from X' Σ, and II is class of such policies. We overload notation and define the induced kernel as x (aa22) [aa E T())), which is valid definition since J [a (z))dpp(aa) = (x)( = 1. All the remaining definitions, including Ry Ry(x), ;;; n* and (p, x), relied on these induced kernels and continue hold. While there are some measure theoretic issues that remain to be discussed, we defer these details to Appendix A.
setting, evaluating arbitrary
Uniform sampling. Our algorithm frequently selects an arm uniformly from a constructed set of arms. In the context of set S A, uniform sampling refers to selecting arm from the distribution {(a) := I(a E S)/ (SS). This constitutes a probability measure since its integral over A equals 1. In the discrete arm setting, uniform sampling from set S A implies selecting an arm according to the distribution (a E S)/\S|
1.2 Oracle Assumptions
Our algorithm relies on two sub-routines. For generality, we abstract away these sub-routines by stating them as oracle assumptions, for which we describe two oracles, EstOracle and EvalOracle, in Assumptions 1 and 2 respectively. The EstOracle sub-routine is for estimating conditional expected reward models (Assumption 1), and the EvalOracle sub-routine is for estimating policy values (Assumption 2) according to the true and estimated reward models.
These sub-routine tasks are supervised learning problems. Hence, the average errors for the corre- sponding tasks can be bounded in terms of the number of samples (n) and a confidence parameter (8'). The oracle assumptions specify the estimation rates. We let Ç x [0, 1] - [0, 1] denote the estimation rate for these oracles. For simplicity, we assume that they share the same rate and that {(n, 8') scales polynomially in 1/n and log(1/6"). order to simplify the analysis, we also require {(n/3, /3/ 8' /n²)) be non-increasing in n." We now formally describe these oracle assumptions, starting with EstOracle.
Assumption (Estimation Oracle). We assume access to reward model estimation oracle (EstOracle) that takes as input an action selection kernel p. and n independently and identically drawn samples from the distribution D(p). The oracle then outputs an estimated model f E F Fscch that for any 8' E (0, 1), the following holds with probability least 88:
E
EE ampp(-12)
a)),,))))- B E(n,8')
Where B 2 0 is a fixed but unknown constant that may depend on the model class F and distribution D. but is independent of the action selection kernel p.
In Assumption 1, the parameter B measures the bias of model class F; under realizability, B equals The function & characterizes the estimation variance, which decreases with increasing sample size. As long the variance term (which shrinks as we gather more data) is larger than the fixed unknown bias (B), we have from Assumption that the expected squared error for the estimated reward model is bounded by 26. We use this bound on expected squared error to further bound how accurately the estimated reward model evaluates policies in the class (Lemma 6). However, since B is unknown, we need test to detect when this policy evaluation bounds starts failing (which can only happen after the variance term gets dominated by the unknown bias term). To construct this test,
Note that our restriction to "slightly randomized" policies for the continuous arm case results in regret bounds with respect to a "slightly randomized" (smooth) benchmark. Hence for the continuous arm case, our cumulative regret bounds translate smooth regret bounds from [40] with K 1/h. Where h is the measure of smoothness in smooth regret (a leading objective for this setting).
Thhis ensures that ε... defined in Lemma is non non-increasing in m for any epoch schedule with increasing epoch lengths.
5

---

our algorithm relies on EvalOracle, which provides consistent independent policy value estimates and helps compare them with policy value estimates with respect to the estimated reward model.
Assumption 2 (Evaluation Oracle). We assume access an oracle (EvalOracle) that takes input an action selection kernel p. n independently and identiallly drawn samples from the distribution D(p), a set of models {gili E [m]] F, and another action selection kernel q- The oracle then outputs a policy evaluation estimator R of true policy value, and a set of m policy evaluation estimators { (gg: E [m]]} that estimate policy value with respect to the models gi 92..... 9m respectively. Such that for any 8' E (0,1), the following conditions simultaneously hold with probability least (m + 1)6':
[f((z)) R(=)] S / (p, a (), 8) + (mm. for all E ITU {ạ).
[Ry(T) (y)) 22 8') for all E II {a} and for all f E {gili E [m]].
When and IT are finite, one can construct oracles such that Assumptions 1 and hold with {(n, 8') (log(maxx([F] (1)) ( One example of such a construction is given by using empirical squared loss minimization for EstOracle, using inverse propensity scores (IPS) for estimating R(x)) in EvalOracle, and using the empirical average for estimating Ry (Tr) in EvalOracle. The guarantees of these assumptions can be derived using Bernstein's 's inequality and union bounding. When F has bounded by [17, 16]. one can construct oracles such that Assumptions I and 2 hold with {(n, 8¹) O(d (anK/KKK)))
pseudo-dimension [20] bounded by d and II has the Natarajan-dimen
2 Algorithm
Algorithm 1 w Risk Adjusted Proportional Response (w-RAPR)
input: Trf parameter w E [1, K], proportional response threshold 9iax = 1/2, and confidence parameter 8 (used in definition of {m).
1: Let pı (a) .) = 1/)(AA) = 1 K, f = 0, 01 = 3K, t = 3, and safe
True.
2: for epoch
1,2,... do
3:
2Tm-11-
Doubling epochs.
4: safe then
5: for round t = Tm-1 + 1,.... Tm do
6:
Observe context Øt, sample a₂ pm (-12,), and observe ra()). end for
7:
8:
Let S. denote the data collected in epoch m.
9:
We split S., into three equally sized sets Sm,,, Sm, and Sm,3- Let fm-1
EstOracle(pms Sm, 1). and let Cm+1 be given by Definition 2.
11:
Let Mm+1 be the solution to (5) and let am+1 == 3K 1mm+1-
D Sm,2 is used here.
12:
Now let Pm+1 be given by (4).
Let Rmt11 {R (Rmtf.fl E [m + 1]} <- EvalOracle(pm, Sm,3, ffile E [m + 1]}, Pm+1).
14:
(2) does not hold. then
15:
vř, safe m, False
end
17:
else
18:
for round = Tm-1 + I...., Ti do
19:
Observe context 2t, sample aę Pm (-12z)), and observe ra.)..
20:
end for
21:
Let S., denote the data collected in epoch
22:
Let Rmti, (R (R E [m]] EvalOracle Smy (ilki [mm]]. pm))-
end if
24:
end for
At a high level, our algorithm operates in two modes, indicated by a Boolean variable "safe". During mode one (safe True), where estimated reward models are sufficiently accurate evaluating policies in the class II, we use our estimated models to update our action selection kernel used
Where the estimated reward models pass the misspecification test.

---

during exploration. During mode two (safe = False), where the condition for mode one no longer holds, we stop updating the action selection kernel used for exploration. Operationally our algorithm runs in epochs/batches indexed by m. Epoch m begins at round 1 Tm-1 + and ends at L = Tm- and we use mtt) to denote the epoch index containing round t. We let mn denote the critical epoch, at the end of which our algorithm changes mode (with "safe" being updated from "True" to "False"); we refer to rn as the algorithmic safe epoch. For all rounds in epoch m S m, our algorithm samples action using the action selection kerne pm defined later in (4). For m > m,, our algorithm samples action using pri -the action selection kernel used in the algorithmic safe epoch mic
We now describe the critical components of our algorithm. These include (i) data splitinng and using oracle sub-routines: (ii) misspecification tests, which we use identify the safe-mode switching epoch m,; and (iii) conformal arm sets, which presents a new form of uncertainty quantification that critical in constructing Pm++1 at the end of each epoch m E [mi)]. Finally, we use these components to describe our final algorithm.
Data splitting and oracle sub-routines. Consider an epoch m E [m.. Let Sm denote the set of samples collected in this epoch: Sm = {(T,, Qz, Qe, (t())) E [1m-1;Tm]] Tm Our algorithm splits S. into three equally-sized subsets: 1,, Sm,2 2 and Sm,3. Algorithm I outlines using these subsets and the oracles (described in Section 1.2) to estimate reward models and evaluate policies. Based on Assumptions and 2, we bound the errors for these estimates in terms of Em+1 25((Tm 3m 5/ (/66mm)), where d is specified confidence parameter. As we will see later, our algorithm relies on these bounds to test for misspecification and construct action selection kernels.
Misspecification test. We first discuss the need for our misspecification test. Note that Assumption 1 flexible and allows our reward model class FF to be misspecified. In particular, the squared error of our reward model estimate may depend on an unknown bias term B. To account for this unknown B. it is useful to center our analysis around the safe epoch m == arg max(m 2 1| 2 2B,. which denotes the last epoch where variance dominates bias. We show that for any epoch m E [m*]. the estimated reward model fm+1 is "sufficiently accurate" at evaluating the expected reward of any policy in II [pm+1). This property is critical in ensuring that the constructed action selection kernel Pm+11 has low exploration regret Reg,- (Pm++) and small optimal cover (V (pm+1, TT")) Since B and m are unknown, we need to test whether the estimated reward model is sufficiently accurate at evaluating these policies. When the test fails, the algorithm sets the variable "safe" to False and stops updating the action selection kernel used for exploration. The core idea for this test comes from [23] although its application simple regret minimization is new, and the form of our test differs bit. We now state our misspecification test (2). At the end of each epoch m. the test is passed if (2) holds:
R Rm+ (TT A 1 1. (T)
R 1R firz (T) Rmm+2TT) - V0mmmmt
Σ
max (p }
40m2 v /am -
mEmmm
< v amEm+1 1.1 L
(2)
where On empirically bounds V(pm,T") the optimal cover for the action selection kernel used in epoch m (see (49)). The first term in (2) measures how well the estimated reward model f evaluates the policy π, and the second term accounts for under-explored policies (policies that have high regret under the reward model f. would be less explored in epoch m).
Conformal arm sets. We proceed to introduce the notion of conformal arm sets (CASs), based on which we construct the action selection kernels employed by our algorithms. At the beginning of each epoch m. we construct CASs, denoted as {Cin (zr, O) X,C [0, 1]]; here Ç controls the probability with which the set Cm contains the optimal arm. The construction of these sets rely on the models ff....,,fu estimated from data up to epoch m 1, as defined below.
Definition 2 (Conformal Arm Sets). Consider Ç E (0, 1). At epoch m, for context z, the arm set (m, () is given by (3).
Cm (,, == =m (x) (mm,))) (=((x,))= = n Öm I, 2m
(I,
mm[m]
(3)
Cx,(x,5)== = {a am (x)) (x)
20 am 1Em
Vmn E [m].5' e (0, 1).
5'
7

---

Similar to conformal prediction (CP) [36, 331, CASs have marginal coverage guarantees. We show that with high probability, we have '" (x) lies in Cm () with probability at least - Ç over the context distribution. That is, Pra-Dxx ( (x) E [2, ()) > - C with boghhprobbbility (see Appendix E. However, there is also a key technical difference. While CP provides coverage guarantees for the conditional random outcome, CASs provide coverage guarantees for ==(x²) which is not a random variable given the context x. Hence, intervals estimated by CP need to be wide enough to account for conditional outcome noise, whereas CASs do not. CASs also have several advantages compared to pointwise confidence intervals used in UCB algorithms. First, CASs are computationally easier to construct. Second, CAS widths have a polynomial dependency on model class complexity, whereas pointwise intervals may have an exponential dependence for some function classes [see lower bound examples in 13]. Third, pointwise intervals require realizability, whereas the guarantees of CASs hold even without realizability (as long as the misspecifiication test in (2) holds). However, it's important remember that these benefits of CASs come with the risk of only covering T (ar) marginally over the context distribution - that is, these sets may not contain ' (I) at all x.
Risk Adjusted Proportional Response Algorithm. We now describe the design of our algorithm, which is summarized in Algorithm I. The algorithm depends on the following input parameters: E [1, K] which controls the trade-off between simple and cumulative regret, the proportional response threshold 9max = 1/2, and confidence parameter 5. The algorithm also computes 7m (risk adjustment parameter for Pm+1),, Qm+1 (empirical bound optimal cover for pm++)), and Am+1() (.) (empirical bound on average CAS size). At the end of every epoch m E [m]], we construct the action selection kernel pm++1 given by (4).
Pm+1 (a|x)) (1 - -muxx Ma E Cm+11I, Puaxx + J. ( I/a E (2, 3/mmmm/mmm
dg.
Ju (Cm+1 1 (Ir, Prnax / mm++))
(a (2r, B/mm+1))
(4)
At any context x, sampling arm a from Pm+11 (+|z) is equivalent to the following. Sample /3 uniformly from [0, 1]. then sample arm uniformly from the set Cm+1 (ar, min /)mmm++) A small B results in larger CAS and a higher probability of containing the optimal arm for the sampled context. However, uniformly sampling an arm from a larger CAS also implies lower probability on every arm in the set. Sampling/ 3 uniformly allows us to respond proportionately to the risk of not sampling the optimal arm while enjoying the benefits of smaller CASs. We refer to this as the Proportional Response Principle.
Similarly note that, larger adjjstmntt parameter 7m encourages reliance on less risky albeit larger CASs. We want to choose 7m+11 to tightly bound the the optimal cover (surrogate for simple regret), subject to cumulative regret constrains imposed by the trade-off parameter w. To do this, we first let Am+1 (1) be high- probabiitbb empirical upper bound on Ez=Dx ln(CCm- (I,, Bunsx/ m) Hence, using (49), we can upper bound the optimal cover (V (pm++, 7)))) by Am 11 + Dmc+1
K
1-Bmax
Our choice of 7m++1 approximately minimizes this upper bound on the optimal cover, by choosing
the largest feasible 77 E [Am,, V /WK/am] such that Am+1(1) (1) K (see (5)). Note that this choice of
"
Mm+1 balances the risk of small 17 (large K) with the benefits of small Am+1 (1)) (small Am+1(1)
I-Smax
Am+1(1)= == min 1+ |Sm.2l tE8...2
1
Σ
M(Cmtt (z. Punax
+
K² In(88) Sm.2 (m + 1)2/8) K
2|Sm.2l
77
ns WK
K
7m+11 + max
Ims max
17
n 11mm221..7
V
Am (1)
S
n
am
(5) With Mm+1 chosen, the action selection kernel Pm++1 is decided. Now let am+1 33//mm41 /mm41. which is a high-probability empirical upper bound on (((m+1, We then use am-1 at the end of epoch m + 1 to construct CASs, compute the risk-adjustment parameter, and test for misspecification.
Computation. We have (log(TT) epochs. At the end of any epoch m. E [m we solve three optimization problems. The first is for estimating fm+1, which often reduces to empirical squared loss minimization and is computationally tractable for several function classes F. The second is for computing the aaj-sadjutteent parameter in (5) which can be solved via binary search. The third is for the misspecification test (2), which can be solved via two calls to a cost-sensitive classification (CSC) solver (don't need this when assuming realizability, further if we only care about cumulative
8

---

regret, sufficient to use the simpler test in [22]). Finally, to learn policy ग at the end of T rounds, we need solve (8) using CSC solver (under realizability we can set = " fm Hence, overall, w-RAPR makes exponentially fewer calls to solvers compared to regression-free algorithms like [26].
Main Results
Our algorichn//nnaysiiiresslss hold for both the discrete and continuous arm cases. As discussed before, minimizing optimal cover helps us ensure improved simple regret guarantees. Hence Om E [1, [.3 (the high-probability empirical upper bound on the optimal cover V (pm: x²)) will play crititcal role thoughout this results section. We start with stating our cumulative regret bounds.
Theorem 1. Suppose Assumptions and 2 hold. Then with probability - 6, w-RAPR ataiins the following cumulative regret guarantee. Here Em+1 E((Tmm -mm-1m33 6/ (16m²) for all m.
CRegT 2
Σ
am(()- amm())
K
KKB + KEm(t)
(6a)
V
ama(t)
1-
T
VWKBT + E
VWKemees
(6b)
IMIT+
Where we use Ô hide terms logarithmic in T, K, E(T,
We start with discussing (6b). The first part VW comes from the bias of the regression oracle with model class F and will vanish under the realizability assumption. The second part Eizn+ V /WKE((t) when setting w = 1, recovers near-optimal (upto logarithmic factors) minimax cumulative regret guarantees for common model classes, demonstrated by the following examples.
We consider w-RAPR with appropriate oracles in the following cases and let B denote the corresponding bias terms. When F and II are finite, CRegr S O(VwKBT BT + /u log (I,, (T))))))))) with probability at least - 6. When F has finite pseudo di- mension d, II has a finite Natarajan dimension d, and A is finite, CRegr Ö(vWKBT V MrKKTllo(TK//S with probability at least 5. Note that under realizability (B = 0), RAPR achieves near-optimal minimax cumulative guarantees.
Corollary 1.
In (6a), we observe that the multiplicative vw cost to cumulative regret is only incurred if the empirical bound on optimal cover (0'm E [1,3K]) can get small. That is, our cumulative regret bounds degrade only if our algorithm better bounds the optimal cover and thus ensures better simple regret guarantees. We now provide instance dependent simple regret guarantees for our algorithm.
Theorem 2. Suppose Assumptions I and hold. For some (A, A, A) E [0, x (0, 1] x [1, K]. consider instances where for X fraction of contexts at most A arms are A optimal (i.e. (7) holds).
PR-Dx (u(fa E A: ft -
(z, s A}) < A
2 1-
Let m' min(m, m(T)) 1. Let the learned policy ft be given by (8) (equivalent variance penalized policy optimization).
R R (T R Rm(T),a (TT)
1 2V Om EmiTT)
t E arg max (m
(8)
sEll
40m² / / 1mm
me(m'
Then with probability
8, w-RAPR has the following simple regret bound when samples.
Regn (f) S 5
(ameSmitt
<o (
(mer) min
K,A+KX+ K3/2w1122
K w A
V Emin(mm (aaiimm.m(T----) (1) [loga (K)]
For large once our bounds optimal cover can't be significantly improved, we have amit) (amtt)/mm((t)11 O(1). Hence for large T. our cumulative regret is a factor of /K/a /K/am(t)+1 larger than the near optimal minimax guarantees. As we will see in Theorem this multiplicative factor is unavoidable.

---

Under (7), we can only argue that the expected (over context distribution) measure of A optimal arms is most (1 A)A + Kλ O(A+ + KX). Hence for large T. the best we can hope for is instance-dependaat simple regret guarantees that shrink/improve over minimax guarantees by factor of (A KX)/K) )) We show that this is guaranteed by Theorem 2. Suppose w K, FF has a finite pseudo dimension bounded by d, and II has a finite Natarajan dimension bounded by d. The simple regret guarantee of Theorem reduces to (minn(( /Kd/T, v(A + KXjd/T + (K/vA) /d/T VB+d/T)) When the reward model estimation bias B is small enough, the term (K/VA) / B + d/T) is dominated by the remaining terms for large T. Hence, in this case, we get a simple regret bound of Ö(V(A+ + KX)d/T) for large T. As promised, this improves upon the minimax guarantees by a factor of (Av(++ KA)/K).
Note that Theorem 1 guarantees are better for w closer to 1 whereas Theorem 2 guarantees are better for w closer to K. Hence these theorems show a tradeoff between the cumulative and simple regret guarantees for w- --R.PR. Theorem 3 shows that improving upon minimax simple regret guarantees for instances satisfying (7) may come at the unavoidable cost of worse than minimax optimal cumulative regret guarantees. This contrasts with non-contextual bandits, where successive elimination ensures improved (compared to minimax) gap-dependent guarantees for both simple and cumulative regret. Given parameters K, F,T E N and o oo). There exists context space X and function class F C (X' x A + 1]) with K actions such that | S F and the following lower bound on cumulative regret holds:
Theorem 3.
T Σ 1=1
2 2
(
K VKTllog VV F
inf sup E AE DED D
- (rr((((a))
Here (ai,...ary aT) denotes the actions selected by an algorithm A. DD denotes the set of environments such that I F and (7) hold with (A, A) = 0, II denotes policies induced by F. 2 a denotes the set of CB algorithums that run for T rounds and output a learned policy with a simple regret guarantee of Volog F/T for any instance in D with confidence at least 0.95, i.e. L (A: P(Reg(#A) S Volog F/T) 2 0.95 for any instance in D}. Finally, (1(-) hides factors logarithmic in K and T.
Near optimal trade-off of RAPR. Note that the environments constructed in Theorem 3 satisfy f e F with max([F], ) < F and also satisfy (7) with (A, X, A) = (1, 0, 0.24). With appropriate ora- cles, Assumptions and 2 are satisfied with B (i.e. m² oo) and E(n, 8') (log(F/88)) //n). Hence for large enough T, w-RAPR achieves a simple regret bound of (V(((//a log F/T) with probability at least 0.95 and thus is a member of V. for some 6 = ((Kww) Theorem 3 lower bounds the cumulative regret of such algorithms by 22( / KKoV/KTlog F) = ((W WWKWWKK /KT log F). Up to logarithmic factors, this matches the cumulative regret upper bound for w- RARR Re-emphasizing that the trade-off observed in Theorems 1 and 2 is near optimal for large T.
Simulations. To demonstrate the computational tractability of our approach, we ran simulation on setting within a IR. conntext space, eight arms, linear models, and an exploration horizon of 5000. Our algorithms ran in less than 9 seconds on simple/cumulative regret. See Appendix E.4 for details.
Macbook M1 Pro. We also compare with other baselines
Conclusion. We develop Risk Adjusted Proportional Response (RAPR), a computationally efficient regression-bant based contextual bandit algorithm. It is the first contextual bandit algorithm capable of trading-off worst-case cumulative regret guarantees with instance-dependent simple regret guarantees. The versatility of our algorithm allows for general reward models, handles misspecification, extends to finite and continuous arm settings, and allows us to choose the trade-off between simple and cumulative regret guarantees. The key ideas underlying RAPR are conformal arm sets (CASs) to quantify uncertainty, proportional response principle for cumulative regret minimization, optimal cover as surrogate for simple regret, and risk adjustment for better bounds on the optimal cover. 13 Limitations. A limitation of our approach is that we do not utilize the structure of the policy class being explored. Further refining CASs with other forms of uncertainty quantification that leverage such structure can lead to significant improvements, and potentially avoid trade-offss between simple/cumulative regret when policy class structure allows for it.
U.S.A. and S.K.K. are grateful for the support provided by Golub Capital Social Impact Lab and the ONR grant N00014- 19- 1-2468. E.B. is grateful for the support of NSF grant 2112926.
10

---

References
[1] Yasin Abbasi- Yadkori, Abbasi-Yadkor, In Advances in Neural Information Processing Systems, pages 2312-2320. 2011.
Dávid Pâl, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits.
[2] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638 1646, 2014.
[3] Susan Athey, Undral Byambadalai, Vitor Hadad, Sanath Kumar Krishnamurthy, Weiwen Leung, and Joseph Jay Williams. Contextual bandits in survey experiment on charitable giving: Within-cxperiment outcomes versus policy learning. arXiv preprint arXiv:2211.12004 2022.
[4] Abhijit Vinayak Banerjee, Esther Duñlo, and Michael Kremer. The influence of randomized controlled trials on development economics research and on development policy. The state of Economics, the state of the world, pages 082-488, 2016.
[5] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19 19-26, 2011.
[6] Aldo Gael Carranza, Sanath Kumar Krishnamurthy, and Susan Athey. Flexible and efficient contextual bandits with heterogenenus treatment effect oracles. In International Conference on Artificial Intelligence and Statistics, pages 7190-7212. PMLR, 2023.
[7] Jishnu Das, Abhijit Chowdhury, Reshmaan Hussam, and Abhijit Banerjee. The impact of training informal health care providers in india: A randomized controlled trial. Science, 354(6308) 2016.
[8] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal leamingg for contextual bandits. In Proceedings of the Sevenh-Seventh Conference on Uncertainty in Artificial Intelligence, UAT111, 1, page 169-178, Arlington, Virginia, USA, 2011. AUAT
Press.
[9] Akram Erraqabi, Alessandro Lazaric, Michal Valko, Emma Brunskill, and Yun-En Liu. Trading off rewards and errors multi-armed bandits. In Artificial Intelligence and Statistics, pages 709-717. PMLR, 2017.
[10] Eyal Even-Dar, Shie Mannor, Yishay Mansour. and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning reseurch, 7(6), 2006.
[11] Dylan Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression oracles. In International Conference Machine Learning, pages
PMLR, 2020.
[12] Dylan Foster, Claudio Gentile, Mchryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33, 2020.
[13] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement- perspective. arXiv preprint axXiv:2010.03/04, 2020.
[14] Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence inter- vals for policy evaluation in adaptive experiments. Proceedings of the national academy of sciences. (18(15)c201440021 2021.
[15] Avinatan Hassidim, Ron Kupfer, and Yaron Singer. An optimal elimination algorithm for learning best arm. Advances in Neural Information Processing Systems, 13:10788-10798, 2020.
[16] Ying Jin. Upper bounds on the natarajan dimensions of some function classes. arXiv preprint D.Xiv22209.001155 2022.
[17] Ying Jin, Zhimei Ren, Zhuoran Yang, and Zhaoran Wang. Policy learning" without" ovthout"overlap: Pessimism and generalized empirical bernstein's 's inequality. arXiv preprint arXiv:2212.09900, 2022.
[18] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-122 1246. PMLR, 2013.
[19] Maximilian Kasy and Anja Sautmann. Adaptive treatment assignment in experiments for policy choice. Econometrica, 89(1):113 132, 2021.
11

---

[20] Vladimir Koltchinskii, Orucle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d' Eté de Probabilités de Saint-Flour XXXVIII-2006 volume 2033. Springer Science & Business Media, 2011.
[21] Akshay Krishnamurthy. Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, pages 1915- 1924. PMLR, 2017.
[22] Sanath Kumar Krishnamurthy, Vitor Hadad, and Susan Athey, Adapting to misspecification contextual bandits with oftline regression oracles. In International Conference on Machine Learning, pages 5805- 5814. PMLR, 2021.
[23] Sanath Kumar Krishnamurthy, Adrienne Propp, and Susan Athey. Towards costless model selection in contextual bandits: A bias-variance perspective. arXiv preprint arXiv:2/06.0644 2023.
[24] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[25] Lihong Li, Wei Chu, John Langford, and Robert Schapire. contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670 670. ACM, 2010.
[26] Zhaoqi Li. Lillian Ratliff, Kevin G Jamieson, Lalit Jain, et al. castance-optimal pac algorithms for contextual bandits. Advances in Neural Information Processing Systems. 35:37590-37603, 2022.
[27] Maryam Majzoubi, Chicheng Zhang, Rajan Chari, Akshay Krishnamurthy, John Langford, and Aleksandrs Slivkins. Efficient contextual bandits with continuous actions. Advances in Neural Information Processing Systems,
2020.
[28] Wenlong Mou, Peng Ding, Martin Wainwright, and Peter L Bartlett. Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency, arXiv preprint arXiv:2301.062 2023.
[29] Susan A Murphy. Optimal dynamic treatment regimes. Journal of the Royal Statistical Society: Series (Statistical Methodology), 65(2):331-355 2003.
[30] Molly Westor,, Alexander Coppock, and Donald P Green. Adaptive experimental design: Prospects and applications political science. American Journal of Political Science, 65(4):826 844, 2021.
[31] Maxim Raginsky and Alexander Rakhlin. Lower bounds for passive and active learning. Advances in Neural Information Processing Systems, 24, 2011.
[32] Daniel Russo. Simple bayesian algorithmss for best arm identification. In Conference Learning Theory. pages 1417-1418. PMLR, 2016.
[33] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008
[34] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Available at SSRN, 2020.
[35] Aleksandrs Slivkins al. Introduction multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1-286, 2019.
[36] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorishmic learning in random world. Springer Science Business Media, 2005.
[37] Jiayu Yao, Emma Brunskill, Weiwei Pan, Susan Murphy, and Finale Doshi-Veles Power constrained bandits. In Machine Learning for Healtheare Conference, pages 209-259. PMIRR 2021.
[38] Andrea Zanette, Kefan Dong, Jonathan N Lee, and Emma Brunskill. Design of experiments for stochastic contextual linear bandits. Advances in Neural Information Processing Systems, 34:22720-22731, 2021.
[39] Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2125-2135, 2021.
[40] Vinglun Zhu and Paul Mineiro. Contextual bandits with smooth regret: Efficient learning continuous action spaces. In International Conference on Machine Learning, pages 27574-27590. PMLR, 2022.
12


Reviews:
[{"review_id": "wBUJusbGoc", "reviewer": "Reviewer_VVeg", "summary": "This paper provides a computational efficient algorithm for contextual bandit that is capable of trading off between near-optimal minimax cumulative regret guarantees and instance-dependent simple regret guarantees. Additionally, It handles model misspecification, works in the continuous arm setting, and provides a lower bound that shows there is always a trade off in achieving simple regret and the cumulative regret.", "questions": "- I request the authors to elaborate further on the optimality of the achieved trade-off between simple regret and cumulative regret. Additionally, I am curious to understand how the provided lower bound sheds light on this trade-off and its implications in the context of the paper's contributions.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- A significant contribution in achieving a trade-off between simple regret and cumulative regret.\n\n- One advantage of the algorithm is that it is regression based which makes it computationally efficient, while it does not rely on the realizability assumption, as it can adapt to model misspecification.\n", "weaknesses": "The weaknesses mainly lie in the paper's poor writing and presentation, as well as in the insufficiently conducted simulations, detailed as bellow.\n\n- The motivation in the introduction lacks conviction and the main story is postponed to the related work section.\n\n- The introduction lacks a clear image of the achieved bounds and the bounds of related works, which could have been presented together in a single table along with all limitations.\n\n- in Section Preliminaries, the notations are listed in the footnote, which make it difficult for readers to follow the setup. In general, the flow in this section is confusing and needs improvement. Moreover, the authors used $\\Pi$ and $\\mathcal{F}$ in the \"objectives\" subsection without defining them before in the problem setup. Also definition of \"CB algorithm\" is missing.\n\n- Lack of clarity regarding the specific location in the appendix for referenced proofs and details.\n\n- Algorithm section is tedious with numerous links to various definitions, making it challenging to follow the flow. Besides that, the provided intuition is not sufficient for a non-expert reader to understand the complex formulas used for variables such as $\\lambda$, $\\eta$, and $\\alpha$. This can hinder comprehension for readers. Moreover, line 15 of algorithm $\\omega$-RAPR seems to be incorrect.\n\n- There are many arXiv papers listed in the references, whereas for most of them there are already the published version in some journal or conference.\n\n- The simulation part is extremely brief and lacks comparison to existing baselines, as well as an illustration of the results.\n\nI believe the paper requires a major revision due to various identified weaknesses.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding theoretical guarantees and optimality of the achieved trade-off:** The algorithm RAPR comes with a tuning parameter $\\omega\\in[1,K]$. This tuning parameter helps us trade-off guarantees on simple and cumulative regret. We discuss our theoretical results and recap the optimality of our trade-off. \n- The simple regret guarantees of RAPR are never worse than the minimax optimal rates (Theorem 2). Depending on the instance, RAPR achieves simple regret guarantees that are up to $O(1/\\sqrt{\\omega})$ times smaller compared to minimax optimal rates (Theorem 2). This improvement factor of $O(1/\\sqrt{\\omega})$ over minimax optimal rates is asymptotically achieved for instances where realizability holds and where the gap between the best and second best arm in terms of conditional expected reward is at least $\\Delta>0$ at every context (best-case instance in Theorem 2). RAPR achieves these instance-dependent guarantees without being provided any instance information as input to the algorithm. \n- Unfortunately, the corresponding cumulative regret for the above instances is a factor of $O(\\sqrt{\\omega})$ times larger compared to minimax optimal rates (Theorem 1). The cumulative regret guarantees of our algorithm only degrade relative to the minimax optimal rate if the instance allows for better simple regret guarantees.\n- Our lower bound (Theorem 3) considers the instances described above with $\\Delta=0.24$ (the gap between the best and second best arm in terms of conditional expected reward). Theorem 3 shows that (by setting $\\alpha=\\Theta(K/\\omega)$ in the Theorem statement) if an algorithm bounds simple regret on these instances by $O(1/\\sqrt{\\omega})$ times minimax optimal rates, the cumulative regret is lower bounded by $\\Omega(\\sqrt{\\omega})$ times minimax optimal rates. Note that RAPR achieves this trade-off when the number of rounds $T$ is large enough. Hence in this sense, our algorithm achieves the optimal trade-off between guarantees on simple vs cumulative regret when $T$ is large enough.\n\n**Regarding simulations:** We are adding plots comparing with other baselines and showing the balance between the objectives. See the joint response above.\n\n**A new outline on the intro::** We thank the reviewer for their valuable feedback on the introduction. Reflecting on this, we have decided to rewrite the introduction with the following outline:\n- We study the stochastic contextual bandit setting and consider two goals. Define/motivate simple regret and cumulative regret. This paper proposes a new algorithm, RAPR, that has a tuning parameter $\\omega\\in[1, K]$ that governs the weight placed on the two objectives. Discuss the theoretical guarantees of RAPR and optimality of achieved trade-off (detailed earlier).\n- Define regression-based approaches and discuss computational benefits of regression-based approaches over the algorithm proposed in [1]. State that RAPR is the first general-purpose (works with any user-specified reward/policy class) regression-based algorithm with attractive simple regret guarantees.\n- We next describe the RAPR algorithm in more detail. (We will include similar intuition for the algorithms section)\n  - We first define a surrogate objective for simple regret, the optimal cover, which is inversely proportional to the probability that the (unknown) optimal policy is used by the bandit. The optimal cover bounds the variance of evaluating the unknown optimal policy under our exploration policy. This surrogate objective can be minimized by appropriately designing our exploration policy/action selection kernels.\n  - Since RAPR is regression-based, we cannot construct an explicit distribution over policies as that distribution would have a large support and would be computationally and memory intensive to maintain. We need to be able to minimize the optimal cover by directly constructing a distribution over arms for each arriving context.\n  - To reason about how well we explore the unknown optimal policy, having a general purpose uncertainty quantification at each context would be helpful. Much of the existing literature constructs  UCB-style confidence intervals, but existing approaches to constructing them rely on assumptions like linear realizability. For general function classes, these intervals may be too wide and are often computationally expensive to construct. \n  - To overcome this issue, we develop conformal arm sets (CASs), which are a set of potentially optimal arms at each context. This uncertainty quantification is regression-based and computationally easy to construct, is general-purpose, and shrinks at ``fast rates” (with square-root dependency on expected squared error bounds for regression). Unfortunately, these sets come with some risk of not containing the arm recommended by the optimal policy at every context. Nevertheless, we can use this uncertainty quantification to construct a distribution over arms at each context that helps us minimize the optimal cover by balancing the benefits and risks of relying on these CASs. The unavoidable trade-off between our simple and cumulative regret guarantees is an artifact of these risky sets.\n  - Beyond allowing us to trade off simple and cumulative regret guarantees, the flexibility of the approach also helps us extend to the continuous arm setting and allows us to handle model misspecification.\n- We then briefly discuss other related work that is outside the scope of this ``main story\".\n\n**Other writing comments:** We will fix the issue regarding our reference containing old arXiv papers. We have improved the intuition provided in the algorithms section and will give our variables intuitive names to help with the flow. We will add proper references to the specific locations in the appendix. We will also improve the flow and readability of the preliminaries. \n\n[1] Zhaoqi Li, Lillian Ratliff, Houssam Nassif, and Kevin Jamieson. Instance-optimal PAC Algorithms for Contextual Bandits "}, {"review_id": "SYjJRiFq8w", "reviewer": "Reviewer_X2Xo", "summary": "This paper focus on the continues objective between simple regret minmization (SRM) and cumulative regret minimization (CRM) in contextual bandits, and propose an algorithm that can be either optimal in SRM, or optimal in CRM. Meanwhile, a new uncertainty quantification is propsed. Numerical simulations validate the efficacy.", "questions": "See weaknesses above.", "limitations": "\\", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": " - Novelty: the paper focus on the objective between best arm identification (BAI) and regret minimization (RM), which is rarely studied but of great practical significance, as most works focus on either RM or BAI.\n- Technical contribution: the conformal arm set as a new type of confidence bound is new, and is of independent interests beyond the topic.\n- The results are strong, as a single algorithm can optimally change from one objective to another is not easy. It's also valuable for multi-objective related topics.", "weaknesses": "- The geometic covering in the algorithm (doubling the epochs) is common in RM, however, when it comes to simple regret minimization, there might be the case that only limited round $T$ is given, and thus requires an any-time algorithm.\n\n- $\\beta_{max}$ as the threshold of $\\beta$ constrains that $\\beta$ can not be too big, and restrains the smallest possible CAS. I'm confused with the counter-intuitive parameter, as for the objective of BAI, CAS should be as small as possible eventually. Why do we need the trucation threshold and why it's selected as $1/4$ should be explained.\n\n- Though it is mentioned that the optimal cover can be seen as the surrogate objective for BAI, it is mainly used to estimate arbitrary policy $\\pi$, while how it can be optimized to achieve a better $\\pi$ is not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging remarks.\n\n**Regarding doubling epochs:** We thank the reviewer for raising this point and will discuss doubling epochs as a limitation of our algorithm. To clarify, our algorithm does not assume a fixed given $T$. If we pause exploration in the middle of an epoch, then the simple regret guarantees in Theorem 2 depend on the data collected in the previous epoch. Hence while doubling epochs lead to larger constants in our simple/cumulative regret guarantees (Note the previous epoch contains at least one-fourth of the total number of samples), our algorithm is still anytime. That is, doubling epochs makes our algorithm less adaptive, leading to worse constants in our theoretical bounds. This is an artifact of us using offline oracles (requiring large batches of i.i.d. data). While needing only offline oracles improves the generality of our algorithm, using online oracles would help us avoid the need to use doubling epochs and would make our algorithm more adaptive. Developing better-optimized algorithms for the fixed budget setting could be an interesting direction for future research.\n\n**Clarifying the role of the optimal cover:** We apologize we did not make this clearer. As briefly discussed in the paper, optimal cover is a surrogate objective for simple regret. We approximately minimize an upper bound on the optimal cover when choosing $\\eta_{m+1}$ (See eq 5 at line 270.). This step is critical to the simple regret guarantees of Theorem 2.\n- Eq 49 (line 635-636) shows that the optimal cover $V(p_{m+1},\\pi^*)$ is upper bounded by $\\frac{E_{x\\sim D_X}[|C_{m+1}(x,\\beta_{\\max}/\\eta_{m+1})|]}{1-\\beta_{\\max}}+\\frac{K}{\\eta_{m+1}}$.\n- Empirically, this quantity is further upper bounded by  $\\frac{\\lambda_{m+1}(\\eta_{m+1})}{1-\\beta_{\\max}}+\\frac{K}{\\eta_{m+1}}$. \n- We approximately minimize this objective by selecting $\\eta_{m+1}$ to be the largest $\\eta$ that satisfies $\\lambda_{m+1}(\\eta)\\leq K/\\eta$ (subject to constraints needed to achieve the desired cumulative regret). Since $\\lambda_{m+1}(\\eta)$ is non-decreasing with $\\eta$, we can show that $\\eta_{m+1}$ approximately optimizes the above objective.\n- The proof of Theorem 2 (see section C) critically relies on the fact that our algorithm ensures the optimal cover is well-bounded.\n- We will expand on this in the paper.\n\n**Regarding the need for thresholding with $\\beta_{\\max}$:** We apologize we did not make this clearer. For simple regret minimization, two factors are of primary concern: (a) the size of the CAS we use and (b) does the set contain the optimal arm. Thresholding helps with (b). \n- When the optimal arm lies in $C_m(x,\\beta_{\\max}/\\eta_m)$, thresholding ensures the optimal arm is sampled with probability at least $(1-\\beta_{\\max})/|C_m(x,\\beta_{\\max}/\\eta_m)|$ (See eq 14 in the proof of lemma 3 in section B.2.). Without thresholding, this probability may be smaller since the optimal arm may not lie in smaller sets ($C_m(x,\\beta/\\eta_m)$ with $\\beta>\\beta_{\\max}$). If the threshold parameter is too close to one, the numerator term ($1-\\beta_{\\max}$) in the above bound would be trivial. \n- Hence, in our analysis, thresholding helps lock in the benefits of $E[|C_m(x,\\beta_{\\max}/\\eta_m)|]$ being small (see proof of Lemma 3) by avoiding the risk of the optimal arm not lying in smaller sets. \n- The numerator term of $1-\\beta_{\\max}$ appears due to selecting $\\beta$ proportionally. Eq 13 in the proof of Lemma 3 shows that selecting $\\beta$ proportionally helps bound the probability of sampling the optimal arm when the optimal arm does not lie in $C_m(x,\\beta_{\\max}/\\eta_m)$.\n- Our analysis can be made to work with $\\beta_{\\max}$ set to be any constant that is not too close to zero or one. The current heuristic choice of $1/4$ can be further optimized in our analysis. It may be that thresholding with $\\beta_{\\max}$ is an artifact of our analysis and can be avoided with other proof techniques.\n- We will expand our discussion of this in the paper."}, {"review_id": "vSKt2grGX7", "reviewer": "Reviewer_FhEq", "summary": "This paper studies contextual bandits and develops a flexible algorithm that can be adapted to both cumulative regret minimization and simple regret minimization. New techniques are developed to analyze the proposed algorithm, e.g., constructing the conformal arm sets. The authors also prove a negative result stating that one cannot simultaneously achieve optimal simple regret and cumulative regret.", "questions": "See the weaknesses part.", "limitations": "As stated on Page 9.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a novel algorithm called RAPR, which utilizes two computational subroutines, an estimation subroutione and an evaluation subroutine. The RAPR algorithm takes a hyperparameter as input, which can be tuned to adapt to either cumulative regret minimization or simple regret minimization. This result seems quite interesting to me. The authors also complement the theoretical upper bound with a lower bound stating that one cannot simultaneously achieve optimal cumulative regret bound and simple regret bound.", "weaknesses": "I have questions regarding some wording used in the paper. More specifically:\n1. The paper claims that they develop a new computationally efficient algorithm. However, it seems that the proposed algorithm is not entirely efficient under model misspecification since a cost-sensitive classification (CSC) subroutine is used in this case. It is known that CSC oracle can be NP-hard to implement even in simple cases.\n2. The paper claims instance-dependent guarantees for simple regret minimization. However, it seems that the guarantees stated in Theorem 2 have a worst-case flavor, compared to instance-dependent results stated in Li et al, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding claims of computational efficiency:** We thank the reviewer for raising this point and apologize for the confusion. The term “computationally efficient” is indeed ambiguous. In the revised version, we will be more precise in our explanation by emphasizing that we only make $O(1)$ oracle calls at the end of every epoch and do not need cost-sensitive classification (CSC) under realizability. Below is a detailed explanation: \n- As discussed in lines 280-281, we don't need CSC if we assume realizability or only focus on the cumulative regret objective. \n- To the best of our knowledge, under model misspecification, the computational challenge of solving problems like CSC is unavoidable in the policy learning literature (e.g. [2], see discussion in Section 2). Even policy learning under RCT (randomized control trials) data requires a CSC solver in settings without realizability assumptions. Despite CSC being NP-hard, several heuristic CSC solvers (e.g., vowpalwabbit) and exact brute-force solvers (e.g., policytree) have been developed.\n- Noting this, papers that propose regression-free algorithms (e.g., [1]) claim computational efficiency by arguing that they only make polynomially many calls to such CSC solvers at every epoch (under doubling epochs). However, as the epochs get large, the number of CSC problems they need to solve and outputs they need to save grows to be impractically large.\n- In contrast, we only make two calls to CSC solvers at the end of every epoch. While this is a computationally expensive step, our approach represents a sizable improvement in terms of computational efficiency over prior work. The improvement is sizable enough to make our algorithm sufficiently computationally tractable/efficient to be implemented (even under model misspecification). \n\n**Regarding the instance-dependence claim:** Thank you for allowing us to clarify why the guarantees in Theorem 2 are instance dependent. \n- Our regression-based approach exploits the gap between optimal and sub-optimal arms under the true conditional expected reward model $f^*$. Most prior literature on instance-dependent guarantees (e.g., [3], see Section 5.2) attempts to use similar gaps between arms under the true reward model.\n- Eq 8 (see line 306 in Thm 2) considers instances where for at least $1-\\lambda$ fraction of contexts from the context distribution, the instance has at most $A$ arms that are $\\Delta$-optimal. Notably, while RAPR does not need these parameters as input, the guarantees of Theorem 2 surpass  minimax guarantees by leveraging these instance-dependent parameters. \n- There is a worst-case component $\\sqrt{Kd/T}$ in our simple regret bound in Theorem 2. The reason for this is that the RAPR’s upper bound on simple regret highly relies on the size of the conformal arm set. By design, the set’s size is at most $K$ but can be smaller than $K$ when using RAPR in instances that are characterized in Theorem 2.\n- [1] propose a regression-free algorithm. Their upper bound is stated in terms of the value of a min-max optimization problem which makes our guarantees hard to compare. Both our bounds seem similar with regard to utilizing gaps between optimal and sub-optimal arms under $f^*$. Nevertheless, the value of the optimization problem in their upper bound can further exploit structure in the explored policy class. We will better emphasize this point as a limitation of our regression-based approach in the revised version.\n\n\n[1] Zhaoqi Li, Lillian Ratliff, Houssam Nassif, and Kevin Jamieson. Instance-optimal PAC Algorithms for Contextual Bandits. Advances in neural information processing systems. 2022.  \n\n[2] Wang, Lequn, Akshay Krishnamurthy, and Aleksandrs Slivkins. \"Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits.\" arXiv preprint arXiv:2306.07923 (2023).\n\n[3] Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. \"Improved algorithms for linear stochastic bandits.\" Advances in neural information processing systems 24 (2011)."}, {"review_id": "XJ8WlIrJYW", "reviewer": "Reviewer_G9eA", "summary": "The paper proposes a novel contextual bandit algorithm that balances cumulative and simple regret guarantees using a surrogate objective and optimal cover. By constructing the conformal arms sets (CASs) which improve the coverage guarantees for the optimal policy, the algorithm efficiently finds the policy that minimizes simple regret while balancing with the cumulative regret. Cumulative and simple regret upper bounds are considered in the case when the model can be misspecified and the hardness result shows that the trade-off between simple and cumulative regret is unavoidable.", "questions": "Q1. My main concern is in Theorem 3. The assumption in Theorem 3 implies a positive gap between the optimal and the second-best arm (e.g., Section 5.2 in [1] ) which enables the algorithm to attain zero simple regrets after $O(\\log T)$ exploration rounds and thus logarithmic cumulative regret bound. Does this result contradict Theorem 3?\n\nQ2. I couldn't understand the sentence \"it (the algorithm) does not utilize the structure of the policy class being explored\" in line 349. Could you elaborate more on this?\n\nQ3. In line 109, the integral in $f(x,S)=\\int_{a} f(x,a) d\\mu(a) / \\mu(S)$ ranges over $S$? Should it be $f(x,S)=\\int_{S} f(x,a) d\\mu(a) / \\mu(S)$?\n\n\n[1] Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. \"Improved algorithms for linear stochastic bandits.\" Advances in neural information processing systems 24 (2011).", "limitations": "Yes. This work is mostly theoretical and the negative societal impact of the work is unseen.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides a theoretical analysis of the balance and trade-off between cumulative and simple regrets, which are not considered in the previous literature. The definition of cover and conformal arm sets is new and paves the way to characterize simple regret minimization. Generalizing regret bounds to the case when the model can be misspecified extends the currently existing literature.", "weaknesses": "W1. More discussions on theoretical results are required. Specifically, (a) the role of the action selection kernel q in Assumption 2, (b) what happens when $\\min_{(x,a)\\in\\mathcal{X}\\times\\mathcal{A}} p(a|x)=0$in Assumption 2 (line 180), (c) how the bias $B$ is multiplied to $\\sqrt{1/T}$ term rather than $O(1)$, (d) examples of the setting that satisfies the assumptions in Theorem 3.\n\nW2. The experiment section does not include the balance of cumulative regret and simple regret, which is the key part of the paper. More diverse settings are required to evaluate the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: The results in [1] do not contradict Theorem 3. We will make this clear in our discussion. The log(T) cumulative regret guarantee in [1] relies on the linear realizability assumption, while our framework here addresses more general model classes where the instance-dependent cumulative regret bounds are impossible to obtain unless the bound depends exponentially on the policy class complexity, as pointed out in [2]. We provide a detailed explanation below.\n- Our lower bound in Theorem 3 indeed considers environments with a positive gap between the optimal and the second-best arm at every context. Under linear realizability, [1] develops an algorithm with gap-dependent cumulative regret guarantees, implying strong simple regret guarantees. While the environments we consider in Theorem 3 satisfy realizability, the model class $\\mathcal{F}$ we construct is not linear. Hence, this is not a contradiction.\n- It is worth noting that linear realizability is a strong structural condition that facilitates the design and analysis of some optimistic algorithms. For a general function class $\\mathcal{F}$, even under realizability, [2] show a lower bound of $\\Omega(|\\mathcal{F}|/\\Delta)$ on cumulative regret. Since this lower bound is much larger than $O(\\log|\\mathcal{F}|/\\Delta)$, in a reasonably strong sense, meaningful gap-dependent cumulative regret bounds are impossible in general. This also implies that gap-dependent simple regret guarantees can not be achieved as a byproduct of gap-dependent cumulative regret guarantees. Theorem 3 strengthens this observation by showing that cumulative regret guarantees get worse than minimax rates when attempting to attain gap-dependent simple regret bounds. \n\n[1] Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. \"Improved algorithms for linear stochastic bandits.\" Advances in neural information processing systems 24 (2011).\n\n[2] Dylan J Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. International Conference on Machine Learning (ICML), 2020.\n\nQ2: Beyond policy class complexity, our algorithm does not leverage any additional structure in the policy class we want to explore. For example, consider the class of policies that recommend the same arm at every context ($\\{\\pi|\\pi(x)=\\pi(x’),\\forall x,x’\\}$). Consider an arm with a high-expected reward for some sub-population of the context distribution but a low estimated average reward (under the context and reward distribution). This arm need not be considered for further exploration at any context. However, CASs do not leverage such structure and will continue accounting for cases where this arm may perform well for some sub-population. Ideally, we should use information regarding the explored policy class to reduce the size of CASs we rely on. If it were feasible in terms of memory/compute, we would ideally maintain a set of potentially optimal policies and then restrict our exploration at any context to arms that correspond to one of the policies in this set. \n\nQ3: You are right, it should be $f(x,S):=\\int_{a\\in S}f(x,a)d\\mu(a)/\\mu(S)$. \n\nW1 [More discussions on theoretical results]: We thank the reviewer for pointing out our limitations on the exposition, and we will address all these points in the updated paper. \n- (a)  [the role of ... kernel q in Assumption 2,] In assumption 2, the action selection kernel q is an input to the evaluation oracle. The oracle adds q to the set of policies it evaluates. Evaluating a single extra kernel does not significantly increase the statistical complexity of evaluating these policies. Our algorithm adds the action selection kernel for the next epoch ($p_{m+1}$) as this additional input to the evaluation oracle. Evaluating $p_{m+1}$ helps us verify that our reward model class's bias did not negatively affect the construction of $p_{m+1}$. \n- (b)[ what happens … Assumption 2 (line 180),]  We will clarify in Assumption 2 that we treat $1/0$ as $\\infty$. Hence, if $\\min_{(x,a)\\in\\mathcal{X}\\times\\mathcal{A}}p(a|x)=0$, then the evaluation guarantees of Assumption 2 are trivial. Assumption 2 specifies the requirements of the evaluation sub-routine we use. The weaker these requirements are, the easier they are to satisfy. The reason we let the bounds in Assumption 2 depend on $1/\\min_{(x, a)\\in\\mathcal{X}\\times\\mathcal{A}}p(a|x)$ is to (i) allow usage of policy evaluation methods like inverse propensity scores that average random variables with inverse propensity terms, and (ii) allow for confidence bounds that require these random variables be bounded.\n- (c) [how the bias is multiplied] In the definition of simple regret (line 118), we compare the learned policy with the best policy in the class $\\Pi$. Note that $\\Pi$ may not contain the universal optimal policy $\\pi_{f^*}$ induced by the ground truth reward model $f^*$. Hence the bound in Theorem 2 can go to zero asymptotically and does not depend on the bias of the policy class. Theorem 2 depends on the bias of the reward model class $B$ because our exploration relies on the estimated reward model. However, this bias can only reduce the benefits of our adaptive exploration.\nIn contrast, our definition of cumulative regret (line 123) compares our action selection kernels used for exploration against the universal optimal policy $\\pi_{f^*}$. Hence Theorem 1 has a $O(\\sqrt{\\omega KB}T)$ term. We work with different definitions of cumulative and simple regret because we use a regression-based approach that tries to estimate $f^*$ for exploration; however, we use cost-sensitive classification for learning the final policy. It is worth noting that there is no difference in our definitions if we assume realizability.\n- (d) [examples ... Theorem 3] The proof of Theorem 3 explicitly constructs environments that satisfy the conditions of Theorem 3 and demonstrate the tradeoff. \n\nW2: We are adding plots showing balance between the objectives. See joint response above."}]

Author rebuttal:
We thank all the reviewers for their valuable feedback.

**Regarding feedback on simulations:** We ran an additional simulation to compare our algorithm (RAPR) against other baselines and to better understand the balance between the two objectives we study. On a randomly generated linearly realizable data-generating process (DGP) with eight arms, two-dimensional context, and an exploration horizon of $40000$ rounds; we simulate LinUCB, BootstrapLinTS (linear thompson sampling), RCT (uniformly sampling arms), and $\omega$-RAPR with $\omega\in \{1,8\}$. 
- Since we are comparing against algorithms based on linear realizability, we used linear realizability to further refine the size of CASs used in our implementation. Note that tightening the uncertainty quantification we rely on does not break our theoretical guarantees. For the other algorithms, we use vowpalwabbit implementations.
- We provide a scatter plot showing (i) the value of the learned policy for each algorithm (as a proxy for simple regret of learned policy) and (ii) the value of the last exploration policy used by each algorithm (as a proxy for regret incurred during exploration). We compare policy values to make it easier to see the trade-off. The current plot averages over results from 10 simulation runs.
  - The ordering for the value of the learned policy is $8$-RAPR > $1$-RAPR > RCT > LinUCB > BootstrapLinTS.
  - The ordering for the value of the last exploration policy is LinUCB > $1$-RAPR > $8$-RAPR > BootstrapLinTS > RCT. As one might expect, cumulative rewards also have the same ordering.
  - Hence we see some trade-off between the two objectives (less stark than Theorem 3 since we restrict attention to the linear case). 
  - We also see that the algorithmic techniques introduced in this paper can help practitioners achieve better policy learning guarantees. However, algorithms like LinUCB can outperform RAPR on cumulative reward.
  - Finally, we note that each simulation run of RAPR took about 40 seconds on an M1 Macbook Pro laptop. Demonstrating the computational efficacy of our approach.
- Data-generating process (DGP): Contexts are 2 dimensional, and number of arms is 8. The DGP was randomly generated and satisfies linear realizability. At every round, each feature of the context is sampled from $[0,0.5]$. The final reward is the average of a uniform noise term sampled from [0,1], a linear reward, and an arm-specific reward. The linear reward parameters for each arm are sampled from a uniform distribution and are normalized to have an L1 norm of 1. The arm-specific rewards for each arm are sampled uniformly from [0,0.5].


Meta-review: This paper studies the contextual bandit problem under model misspecification and with access to regression oracles.
The proposed algorithm can be instantiated with a tradeoff parameter that interpolates between optimizing the cumulative regret or the last-iterate simple regret. For the second objective, it is the first optimal contextual bandit algorithm that is efficient under the regression oracle assumption.

The reviewers generally agree that this is a solid work and it is a clear accept. 

The reason why this is not above a poster is that it is well known, see Bandit algorithms (Lattimore and Szepesvari, Chapter 33) that there is an unavoidable trade-off between cumulative regret and simple regret in bandits. The lower bound presented here is folklore knowledge for me (at least for K-armed bandits). The reason why the literature studies the settings in isolation, is because 1) the trade-off curve does not contain too many surprising insights, 2) nor is it especially hard to obtain a point on the trade-off curve.
Decision: Accept (poster)