Conservative Contextual Bandits: Beyond Linear Representations
Authors: Rohan Deb
Mohammad Ghavamzadeh
Arindam Banerjee
Venue: ICLR 2025 Poster (2025)
Keywords: Contextual Bandits
Safety
Neural Bandits
Constrained Bandits
Primary area: reinforcement learning
TL;DR: Algorithms for safe exploration in Conservative Contextual Bandits, ensuring performance stays within a safe range of a baseline policy for general non-linear costs.

Abstract: Conservative Contextual Bandits (CCBs) address safety in sequential decision making by requiring that an agent's policy, along with minimizing regret, also satisfies a safety constraint: the performance is not worse than a baseline policy (e.g., the policy that the company has in production) by more than $(1+\alpha)$ factor. 
Prior work developed UCB-style
algorithms for this problem in the multi-armed (Wu et al., 2016)  and contextual
linear (Kazerouni et al., 2017) settings.
However, in practice the cost of the arms
is often a non-linear function, and therefore existing UCB algorithms are ineffective in such settings. 
In this paper, we consider CCBs beyond the linear case and develop two algorithms $\mathtt{C\text{-}SquareCB}$ and $\mathtt{C\text{-}FastCB}$, using Inverse Gap Weighting (IGW) based exploration and an online regression oracle. 
We show that the safety constraint is satisfied in high probability and that the regret for $\mathtt{C\text{-}SquareCB}$ is sub-linear in horizon $T$, while the the regret for $\mathtt{C\text{-}FastCB}$ is first-order and is sub-linear in $L^*$, the cumulative loss of the optimal policy. 
Subsequently, we use a neural network for function approximation and online gradient descent as the regression oracle to provide $\tilde{\mathcal{O}}\big(\sqrt{KT} + K/\alpha\big) $ and $\tilde{\mathcal{O}}\big(\sqrt{KL^*} + K (1 + 1/\alpha)\big)$ regret bounds respectively. 
Finally, we demonstrate the efficacy of our algorithms on real world data, and show that they significantly outperform the existing baseline while maintaining the performance guarantee.

Published as a conference paper at ICLR 2025
CONSERVATIVE CONTEXTUAL BANDITS: BEYOND LINEAR REPRESENTATIONS
Rohan Deb University of Illinois Tribana-Champal rd228 11 linoiii....... edu
Mohammad Ghavamzadeh
Arindam Banerjee
Amazon AGI
University of Illinois
ghavamza aaaamaaaammaa @ama zon, com
Urbana-Champaign a arindambl llliniiiiss edu
ABSTRACT
Conservative Contextual Bandits (CCBs) address safety in sequential decision making by requiring that an agent's policy, along with minimizing regret, also satisfies a safety constraint: the performance not worse than baseline policy (c.g., the policy that the company has in production) by more than (1 + a) factor. Prior work developed UCB-style algorithms for this problem in the multi-an aamtid (Wu al., 2016) and contextual linear (Kazerouni al., 2017) settings. However, in practice the cost of the arms is often a non-linear function, and therefore existing UCB algorithms are ineffective in such settings. In this paper, we consider CCBs beyond the linear case and develop two algorithms C-SquareCB and C-FastCB, using Inverse Gap Weighting (IGW) based exploration and an online regression oracle. We show that the safety constraint is satisfied with high probability and that the regret for E-SquareCB is sub-linear in horizon T. while the regret for C- C-FastCB is first-order and is sub-linear in 7.", the cumulative loss of the optimal policy. Subsequently, we use neural network for function approximation and online gradient descent as the regression oracle to provide (V + K/aa) and Ō(VKL* + K + 1/a)) regret bounds respectively. Finally, we demonstrate the efficacy of our algorithms real world data, and show that they significantly outperform the existing baseline while maintaining the performance guarantee.
INTRODUCTION
Contextual bandits provide a framework to make sequential decisions over time by actively interacting with the environment. In each time step, the learner observes K context vectors associated with corresponding arms, selects an arm based on the history of interaction and observes the corresponding noise corrupted cost' of playing that arm. The objective of the learner minimize the cumulative sum of costs over the entire horizon of length T', or equivalently to minimize the regret. Although lot of progress had been made in the multi-armed (Auer al., 2002; Agrawal & Goyal, 2012: Bubeck et al., 2012; Bubeck & Slivkins, 2012) and linear formulation (Chu et al., 201 I; Abbasi- Yadkori et al., 2011: Agrawal & Goyal, 2013), until recently solutions for the general non-linear cost function did not exist. A series of work on neural contextual bandits (Zahavy & Mannor, 2020; Zhou et al., 2020; Zhang et al., 2021) have provided algorithms and guarantees for general non-linear cost functions, paving the way for practical use of bandit algorithms in real-world problems. Distinct from the previous set of works, Foster & Rakhlin (2020) and Foster & Krishnamurthy (2021) developed general reductions from the bandit problem to online regression using the Inverse Gap Weighting (IGW) idea (Abe & Long, 1999; Abe et al., 2003). This reduction works for general cost functions and uses only mild realizability assumption (see Assumption 1).
In addition to non non-linear cost functions, safety another crucial consideration that significantly enhances the practical use of these algorithms in real-world. In this work, we consider specific notion of safety called safety with respect to a baseline (Kazerouni et al., 2017). Algorithms that are safe, meaning is assured to perform at least as well as an established (possibly already deployed) baseline, are more likely to be used in practice. While existing online algorithms for bandits are expected to eventually identify an optimal or high- performrf policy, their performance during the
Wee use the cost formulation instead of the more common reward formulation in this paper.

---

Published as a conference paper at ICLR 2025
initial learning phase can be unpredictable and often unsafe. To ensure safety in such algorithms, it is important to regulate their exploration, by making them more conservative. This is done by making sure that the cumulative cost of the algorithm at any stage is not worse than that of the baseline by more than a (1 + a:) factor (cf. Definition 2.2). Such a conservative bandit formulation has been studied in the multi-armed setting (Wu et al., 2016) and the contextual linear setting (Kazerouni et al., 2017; Garcelon et al., 2020), but algorithms and regret guarantees for the general case do not exist.
Existing conservative bandit algorithms in Wu et al. (2016); Kazerouni et al. (2017); Garcelon et al. (2020) have considered standard multi-armed bandits and linear contextual bandits, using a suitable variant of the popular Upper Confidence Bound (UCB) approach. In this work, we are interested in Conservative Contextual Bandits (CCBs) beyond the linear case. One simple and lazy way to extend the analysis to general non-linear functions would be to modify the Neural UCB algorithm (Zhou et al., 2020), and extend the regret analysis to the conservative setup. However, recent work (Deb et al., 2024a) has shown that the regret bound for Neural UCB in Zhou al. (2020) (and Neural Thompson Sampling Zhang et al. (2021)) that depends on the efective dimension d, is (T) in the worst case even with an oblivious adversary. This also extends to any modification for the conservative case, and therefore we avoid this approach.
In this paper, we consider CCBs with general functions and make the following contributions, First, as our main contribution, under the assumption of an online regression oracle for such general functions, we propose CCB algorithms utilizing such regression oracle and doing exploration using inverse gap weighting (IGW) (Abe & Long, 1999; Foster & Rakhlin, 2020; Foster & Krishnamurthy, 2021). The regret of our proposed algorithms, respectively based on squared loss and KL-loss regression (Sections 3 and 4), can be expressed in terms of the regret of the corresponding regression oracle, while ensuring that the conservative performance guarantee not violated with high probability. Our analysis differs substantially from the standard UCB based analysis, since our algorithms do not maintain high confidence sets around the true cost functions, which is challenging for general functions. Our analysis also differs from the standard IGW analysis as the proposed CCB algorithms have to guarantee the safety constraint by a careful balance between actions chosen based on IGW exploration and using the baseline algorithm. Second, we instantiate the proposed CCB algorithms by using online neural regression, leverage Ollg T) regret for neural regression with both square-loss and KL-loss, and provide regret bounds for CCBs with neural networks (Section 5). A more detailed description of existing works leading up to the current work can be found in Appendix A.
Next summarize our specific technical contributions below:
1. Reduction using Squared loss: We provide an algorithm for conservative bandits for general cost functions using an oracle for online regression with squared loss (see Algorithm 1). We subsequently prove O(VKT KT Regsa (T) K Regsa (a) regret bound, where Regag (T) is the regret of online regression with squared loss, and also ensure that the performance constraint is satisfied in high probability (see Theorem 3.1).
2. Reduction using KL loss: Next, we provide an algorithm using oracle for online regression with KI. loss (see Algorithm 2) and prove a O( KT, log(I.*) Regar. (T) + K Rega. (7) (1 regret bound. Here, Regu, (T') is the regret of online regression with KL loss and L is the cumulative cost of the optimal policy, while ensuring that the performance constraint is satisfied in high probability (see Theorem 4.... This is a first order regret bound and is data-dependent in the sense that it scales with the cumulative cost of the best policy L", instead of the horizon length T.
3. Regret Bounds using Neural Networks: We instantiate the online regression oracle with Online Gradient Descent (OGD) and the function approximator with a -erward neural network to give an end-to-end regret bound of (V KT log(T) + K log(T)/a) (a) for Algorithm (Theorem 5.1) and (VKLL log(L*) log(T) + K log T + K log(T)/a) for Algorithm 2 (Theorem 5.2).
4. Experiments: Finally, we compare our proposed algorithms with existing baselines for conserva- tive bandits and show that our algorithms consistently perform better (see Section 6).
2 PROBLEM FORMULATION
We consider a contextual bandit problem where a learner needs to make sequential decisions over T time steps. At any round E [T], the learner observes the context for K arms X, = et al. (201 4); Simchi-Levi & Xu (2020); Ban al. (2022) where the contexts are chosen i.i.d. from
Contextual Bandits:
C Rd, where the contexts can be chosen adversarially unlike in Agarwal
2

---

Published as a conference paper at ICLR 2025
fixed distribution. The learner chooses arm a [K] and then the associated cost of the arm yt,a, E [0, 1] is observed. We make the following assumption on the cost.
Assumption 1 (Realizability). The conditional expectation of Ut, given Xt,a is given by some h E H. where H is the function class such that h : R² + [0, 11, ie., Elyr,olxeaa = li(xt,a). Further, the context vectors satisfy [|xt,al| S 1, 1. E (T), E [K].
Definition 2.1 (Regret). The learner's goal is to minimize the regret, defined as the expected difference between the cumulative cost of the algorithm and that of the optimal policy:
T
T
Regeo (T) = -E - (yt... - -V.a;) - ()(x).a))) - -h(x1,;))
-w.a:)]-E
1=1
1=1
where of aargiin (( minimizes the expected cost in round The subscript CB stands for Contextual Bandits and subsequently differentiates it from the regret of online regression.
Conservative Contextual Bandits:
There exists a baseline policy Te that at each round t, selects
action b, [] and receives the expected cost hxx,,,,)) ). This baseline policy is to be interpreted the default or status quo policy that the company follows and knows to provide a reasonable performance. However, the company wants improve the policy but the same time not incur high cost while trying to do so. Thus, it insists on the following performance constraint on any algorithm:
Definition 2.2 (Performance Constraint). At each round t. the cumulative loss of the agent's 's policy should remain below (1 + a)) times the cumulative loss of the baseline policy for some a > 0, i.e.,
(1++) (1+++)/nnee h(x,s..)) , Vt E (1.....T))
(2)
The parameter a >> O controls how conservative the agent has to be with respect to the baseline policy. When a very small, the cumulative loss by the agent's 's policy cannot be very large in comparison to baseline cumulative loss and as is increased the agent can take larger risks to explore more. We assume that the expected costs of the actions taken by the baseline policy, 1 (x(x,,))) ), are known. This is reasonable assumption as argued in Kazerouni et al. (2017); Garcelon et al. (2020), since we usually have access to a large amount of data generated by the baseline policy as this is the default strategy of the company. We can also relax this to the assumption that we have un- un-biased estimate of the baseline cost and modify our algorithms slightly (see Appendix E).
Next, we make the following assumption on the baseline gap and the costs of the baseline actions. Assumption 2 (Baseline Gap and Cost Bounds). Let Ar., := h(xx,,,)) h (xxt,a;) be the baseline gap. There exist 0 < A < Db and yt
< yhu such that for all t [2'] we have
A < D be < A.. and yt S bt < yh.
The assumption ensures minimum level of performance by the baseline action and is standard in conservative bandits. Assumption 3 in both Kazerouni et al. 2017 and Garcelon et al. (2020) are exactly as Assumption 2 in this work, while the regret bound provided in Theorem of Wu et al. (2016) implicitly depends on similar quantities.
REDUCTION TO ONLINE REGRESSION WITH SQUARED LOSS
In this section, we develop an algorithm for Conservative Bandits with general output functions by reducing it to a black-box online regression oracle with squared loss. In Section 5, we instantiate the oracle by online gradient descent and give end-to-end regret guarantees. Before proceeding to the algorithm, we briefly describe the online regression formulation below. For more detailed treatment, see Hazan (2021): Shalev-Shwartz (2012); Bubeck (2011).
Online Regression with Squared Loss: We assume access an oracle Sq-Alg that takes as input all data points until time t - 1, D
{(Xi,,,> Vi.a,) 1 < i < t t- 1} and makes the prediction Ột., = Sq Alg(D:-1, Xt,a) in [0, 1] for input Xt,a at time t. We further make the following assumption on the regret incurred by the oracle Sq-Alg:
Assumption 3 (Online Regression Regret for Squared Loss). The regret of the online regression
oracle Alg g is bounded by Regsa (T') 2 1, i.e.
T
Σ Lug (fr, a),
inf Σ gEN
Log (x(X),,))) V1,,e) S Regs
where the squared loss is given by Eng (ng(Dr, V),,,) = (Dr,ar - vt.a.)
3

---

Published as a conference paper at ICLR 2025
Algorithm I Conservative SquareCB (C- S-Suuuuere)
1: Input:
2:
Exploration parameter "Yt
3: Initialize: Su 0, and let mo = 0, my | [T]
4: for t 1,..., do
5: Receive contexts x,.1...., x and compute Dr,ks Ak E [K] using Sq Alg
6: Let 2 = argmin Dt,a, and compute aE[K]
Pr. K + (ili De,=,) Wk E [K] {z))
Pt. 1
Σ
Pro
aftss
7: Sample 0e Pt
8:
if the safety condition in (4) is satisfied then
9:
Play the IGW action Gr ag and observe output Vt.o.
10:
Set S. = S Ut, S S
11:
Set Di = Di-1 U {(xi,a,) v),,,)) and update the oracle Sq Alg
12:
else
Play d; b, and observe output ((x1,b))
14:
Set S. S S - Ul, Det1 Dr
We refer to our algorithm as C-SquareCB, whose pseudo-code is reported Algorithm 1. At high level, C-SquareCB does the following: 1) It samples an action from the IGW distribution using the outputs of the oracle Sq-Alg. 2) It then verifies if certain safety condition is met, 3) If yes, it then plays the sampled action, otherwise turns conservative and plays the baseline action. We use S, S [T] and its complement S S [T] to denote the subsets containing the time-steps until round t when the IGW and baseline actions were played, respectively. We denote the cardinality of these sets by m. [S,] and = |
At every round the agent receives K contexts Xt,1,-.., Xt, and estimates the cost for every arm at.a using the online regression oracle (line 5). It then finds the arm with the lowest estimate 2, (see line 6) and computes the Inverse Gap Weighted (IGW) distribution using the estimate gaps dt, Ut... and the exploration parameter "/t. Next it samples candidate action å, in line 7 and verifies safety condition in line 7 (corresponding to (2)) by checking the following inequality holds:
Σ Σ
Piaaiaa + Σ h(xi,b,) + 16 m Regsg (m,-1) + log( (4/8)
Ur,a. +
IESK-InE[K]
VEST
(C)
(A)
(B)
(1+aa) Σ h(x,,0.)
(4)
Here, term (A) sums up the expected costs of the regression oracle for rounds when the IGW action was played and the cost of the current IGW action ā, under consideration. Term (B) simply sums up the baseline costs for all the rounds when the baseline action was played. To ensure that the performance constraint (2) is not violated, in our proof show that (see proof of Lemma
(A)
Σ (E)
M(Xi,a;)) > -16 m (Rege + log(4/8)).
Observe that now term (C') compensates for the above gap and immediately implies that the constraint in (2) satisfied. Note that an easy way to ensure that (2) holds would be replace (A) with the observed costs Dt,a, and use
to bound Eies.,, (Vi.a; 1(xx;,a)) )). However this approach does not let us control the number of times the baseline action is played by the algorithm, which crucial to bound the final regret (see Step 2 in the proof of Theorem 3.1). the safety condition in (4) is satisfied, then the IGW action a; à, is played and the output Vt,a, is observed in line 9. The current time step is added to S, and the current input-output pair (x, Vt,a,) is added to the online regression dataset D, (lines 10 and 11). Otherwise play the baseline action b, in
4

---

Published as a conference paper at ICLR 2025
line 13, observe the true output h(xx,,;) and add the current time step to Si in line 14. We now state the main theoretical result of this section that bounds the regret of C-SquareCB (Algorithm 1) along with satisfying the performance constraint in (2) in high probability.
Theorem 3.1 (Regret Bound for C-SquareCB), Suppose Assumptions 1,2 and hold. With probability at least -,, C- SquareCB (Algorithm 1) with Tt. = / (Regs((Rr + 1og(86-1)) satisfies the performance constraint in (2) and has the following regret bound:
K (Regsq (T) 1og(88-11))
Regca (T) 0
KT
(Regsa (T) vlog(88-1)
(5)
ay (Ar + azy)
Remark 3.1 (Term interpretations), Term I and IT in (5) correspond to the regret of playing the IGW and baseline actions, respectively. Note that term // grows with Regsq (T), unlike the linear case where the second term is independent of the horizon I' (see Theorem 5 in Kazerouni et al. 2017). However, in Section 5, when we instantiate the oracle with OGD and the function approximator with neural network, (T)) only contributes log T factor to the regret to the second term.
Remark 3.2 (Infinite actions). The regret in (5) scales with the number actions K, and thus, holds for finite number of actions. In case of infinite actions, a straightforward extension of our results following the analysis of Theorem in Foster et al. (2020) will lead to regret that scales with the dimension of the action space instead of K.
Proof of Theorem 3.1 The proof the theorem follows along the following steps. We report the proof of the intermediate lemmas in Appendix B.
1. Regret Decomposition: We begin by decomposing the regret in (1) into two parts following Kaze- rouni et al. (2017): the regret accumulated by playing the IGW and baseline actions, terms / and II in the regret bound (5), respectively.
Lemma 3.1. Let Assumptions I and 2 hold. Then, the regret defined in (1) can be bounded as + nT
Regce (T)
-
(EST
where the set ST consists of the rounds until the horizon T when C- SquarrCB played IGW action and nt = SSy. is the number of times until T where a baseline action was played.
2. Upper Bound on nt : The safety condition in (4) determines how many times the baseline action played. In what follows, we use m, == |St] and == max [1 S t S T a, b,), i.c. the last time step at which C- SquareCB played an action according to the baseline strategy.
(a) The following lemma upper-bounds nr in terms of m, and Lemma 3.2. Suppose Assumption 1,2 and holds. Then, with probability 1 - 5/4 the number of times the baseline action is played by C-SquareCB is bounded as
nT < agt
(m,-1 + 1)(Ar + ag))
+ 64V / (T) + (log(86-1))
(b) Note that the second term in (7) grows M and the first term decreases linearly in m. and therefore, one can find the maximum and further bound ny as in the following lemma. Lemma 3.3. Suppose Assumption 1,2 and holds. Then, with probability 1 - 5/4 the number of times the baseline action is played by C-SquareCB is bounded as follows:
(Regsq (T) log(88-1)
RTT SO
agy( ( + axyt)
3. Bounding the Final Regret: The first term in (6) can be bounded along the lines of the analysis in (Foster& & Rakhlin, 2020). Note that Dr only contains the onput-output pairs at time steps when the IGW action was picked, i.c., all t E Sr, and therefore, using mr = |Sr]. (3) reduces to
Σ (Dr., - Vr,,,) inf Σ (g(X4,0.) - vt,a,) Regsg(mr)
(9)
gEH 1EST
BEST
5

---

Published as a conference paper at ICLR 2025
However, unlike Foster & Rakhlin (2020), need an a time varying exploration parameter " that depends on the size of St for all t E [T] in order to bound nr in Step 2. The next lemma bounds the regret of the first term in (6) with an such adaptive %
Lemma 3,4. Suppose Assumptions I and 3 hold. Then, for 8 > 0 and a =
v K (Reesl/ (T)) log(40 with probability 1 - 8/4, C- C-SquareCB guarantees
Σ REST
(((xLa)))) h(xx,0))) - (o Kmg Regs + v KKm log(88
(10)
Note that my S T. Combining (6), (8), and (10), and taking a union bound over the high probability events shows that the regret bound in (5) holds with probability 1 1- 5/22.
4. Performance Constraint: Finally the following lemma shows that the condition in Line 7 of C- C-SquareCB ensures that the performance constraint in (2) is satisfied.
Lemma 3.5. Let Assumptions 1, 2 and 3 hold. Then, for > and "It /K|S. (Regag
1og(88-1)), with probability 1 - 8/2, C- C-SquareCB satisfies the per- formance constraint in (2).
Taking union bound with the high probability regret bound in Step 3, we have that with probability 1 - 6, C-SquareCB simultancously satisfies the performance constraint in (2) and the regret upper-bound in (5), which concludes the proof.
Remark 3.3 (Bounding baseline regret). The analysis in Foster & Rakhlin (2020) does not have a safety condition and therefore our analysis bounding nr (the number of times the baseline action is played) in Step 2 and the performance constraint satisfaction in Step 4 of proof of Theorem 3.1 are original contributions. One of the important parts of the analysis involves bounding nt, the number of times the baseline actions are played. In the linear case (Kazerouni et al., 2017), the analysis crucially uses the upper and lower confidence bounds for the parameter estimates. For general function classes it is difficult to maintain such confidence bounds around estimates, and further the estimates from the regression oracle ft.., do not provide any such guarantees. Therefore our analysis crucially relates Wy to squared loss and through that gives reduction to online regression.
Remark 3.4 (Time dependent Exploration). The analysis from Foster & Rakhlin (2020) cannot be directly used bound the regret for the time steps when the IGW actions were picked (term in (5)). This is because we need to carefully choose a time dependent exploration parameter "/, to simultaneously ensure that term I is /T while ensuring that ny is small. In the process, we extend the analysis in Foster & Rakhlin (2020) to deme-dependent " and bound the regret I.
FIRST ORDER REGRET BOUND WITH LOG LOSS
In this section, we use an oracle with KL loss, KL KL-Alg, and provide a reduction from the conservative contextual bandit (CCB) problem to online regression. The objective of this reduction is to provide a.first order data dependent regret bound, i.e., bound that scales with L Eta (t),,, where (t) = h(x(,a;) is the cost of the optimal action at time t. Note that L < T, since h(x) E [o, 1] for all x, but in practice may have L" < T.
Online Regression with KL Loss: We assume access to an oracle KL Alg that takes as input all data points until time - 1, DD = {(xx,a Vi.a;) < i & t [1-1] 1} and makes the prediction ÿt,a KL- KL-Alg(D) Alg(D,-11 xt.a) in [0. 1] for input Xt,a at time t. We further make the following assumption on the regret incurred by the oracle KL-Alg:
Assumption 4 (Online Regression Regret for KL Loss), The regret of the online regression oracle KL- A-l is bounded by Regxi (T) 2 i.e.,
T
T
Σ LKL (OL Ve,o.) inf Σ gCM 1=1
LKL (g((x,a))) ve,a.) S Regia (T),
(11)
where the KL loss is given by lxl v) = y (1g((1))))) + (1 - y) log(1/(1 -)).
"ee Appendix A for more details on Data Dependent Bounds

---

Published as a conference paper at ICLR 2025
Algorithm 2 Conservative FastCB (C- FastCB)
1: Input:
2:
Exploration parameter ">+
3: Initialize: Sn =
4: for lil,=,..... do
5: Receive contexts ......... K and compute Dt,k, vk E [K] using KL- Alg
6: Let 2 = argmin 0r,8 and compute kE[R]
Pt.k
Dt.z
vk [K] {at)
Pt. =
E
Piaa
Kt, + (Be, - )1,2,)
afta
7:
Sample āe Pt
8:
if
0t,
Σ Σ [ESL-I
Piabiaa +
Σ M(xi,b,)
16 m4 Rega (7) $ h(xi,b.)
SES!11
then
9:
Play ar = āt and observe output yt,a;
10:
Set S₁ S Ut, Sf Si-1
11:
Set D. = D U ((xt,a)) [t,a,)} and update the oracle KL-Alg
12:
else
13:
Play a = b, and observe output h(x(,b,)
14:
Set S, St-1, Si = S Ut, Di+1 De
We refer to the resulting algorithm C-FastCB, It follows the same structure as C- S-uuureBB (Algorithm 1) and is summarized in Algorithm 2. We now state the main theory of this section that bounds the regret of C-FastCB along with satisfying the performance constraint in high probability.
Theorem 4.1 (Regret Bound for C-FastCB). Let Assumptions 1, 2 and 4 hold. With probability 1-6, 6, C C-FastCB (Algorithm 2) with N chosen in (71 (ya-Schedule), satisfies the performance constraint in (2) and has the following bound on the expected regret (expectation is the action distributions):
Reggs (T)] (VKLL-log(L)) RegEl (T)
K RRegxa log
(ev ( (VVKRoBu(T)))
(12)
(g)(Ar + aat)
A: + anj
Remark 4.1 (First Order Regret). Note that the regret in (12) depends on vL* instead of VT,
where I = Et= (i()) is the cumulative loss of the optimal policy and depends on the complexity of the bandit instance, I < T, thus improving the performance of the learner. Such data dependent regret is referred to as a first-order regret (Agarwal et al., 2017a; Foster & Krishnamurthy, 2021).
Remark 4.2 (Challenges). We face similar set of challenges as in Theorem 5.1 in trying bound nr, and our analysis relates my to the KL loss using the sampling strategy and reduces it to online regression with KL loss. We face additional challenge. In Foster & Krishnamurthy (2021), the exploration parameter "/ is set to fixed value 7 max( / LL" /KKL"/RReaaa /3Regku (T)), 10K). In analysis we need a time dependent ?t to ensure that we can bound the regret contributed by both the IGW and baseline actions (cf. decomposition in (6)). However, unlike in Algorithm
crucially need to set Y/t in an episodic manner to ensure that the final regret does not have a VT dependence. By having log(L") episodes and keeping 7 constant within an episode, we derive our final regret in (12), in which term / has only additional Vlog(L") factor. A more detailed description of the exact choice of y along with the episodic analysis has been pushed to Appendix C, for clarity.
Proof of Theorem 4.1. The proof broadly follows the same sequence of steps as in the proof of Theorem 3.1, and owing to limited space, has been reported in Appendix C.
7

---

Published as a conference paper at ICLR 2025
5 NEURAL CONSERVATIVE BANDITS
In this section, we instantiate the online regression oracles Sq-Alg (Algorithm 1) and KL-AI, Alg (Algorithm 2) by (projected) Online Gradient Descent (OGD), and use feed-forward neural networks for function approximation. The setup closely follows the one in Deb et al. (2024a), which we restate it here for completeness. We consider a ferd-forward neural network whose output is given by
f(0;; x)) := m 1/ Ø(m
(0mmm///p 1/, (1) o(... 6(m= 1/, (x) ).))),
(13)
where T. is the number of hidden layers and m the width of the network. Further, (1 Rmxd and with [w][[]]] E Rmxx for all E { Lij are layer-wise weight matrices, and Ve E R is the last layer vector. Similar to Du et al. (2019); Banerjee et al. (2023), we consider (point-wise) smooth and Lipschitz activation function ((-). We define 0₂ TR?, where 8, (vec(W;(")) ..... vec(W: v vT)T, as the vector of all parameters in the network, and make the following assumption on the initialization of the network (Liu et al., 2020; Banerjee al., 2023).
Assumption 5. We initialize Og with wo.s NN for E [4], where ou 2(1+
(1)
0,
Ving v2m
and Vo a random unit vector with ||voll2 1.
Next, define the Neural Tangent Kernel (NTK) matrix (Jacot et al., 2018) at O as Kutk (0) [(V f(O; Xt), V f(0; x)] E RTTxT, and make the following assumption on this matrix which is common in the deep learning literature (Du et al., 2019; Arora al., 2019; Cao & Gu, 2019). Note that our NTK is defined for a specific sequence of x 's where X2 depends on the choice of arms played, and our assumption on the NTK matrix is for all sequences, which is equivalent to the assumption for the (TK x TK) NTK matrix as in Zhou et al. (2020); Zhang et al. (2021).
Assumption 6. The mutrix Kntk (0p) is positive definite, ie., Kntk(Oo) ž Ao for some An > 0.
The assumption can be ensured if no two context vectors overlap. Note that this assumption is used by all existing regret bounds for neural bandits (see Assumption 4.2 Zhou et al. 2020, Assumption 3.4 in Zhang et al. 2021, Assumptio 5.1 in Ban et al. 2022 and Assumption 5 in Deb et al. 2024a). The choice of the width of the network m depends on Ao and is similar to the width requirements in Zhou et al. (2020) and Zhang et al. (2021).
We define a perturbed network as Deb et al. (2024a) as follows:
F
(0. 0n) egee
f(0,, x,, = f(0;; xx) ) + cp
(14)
j=1 m!/-
where {e,},=1 |= are standard basis vectors, E = (s epp"" is an i..dd random Rademacher vector, i.., P(E, = +1) = P(ey = 11) = 1/2, and cp is the perturbation constant. As in Deb et al. (2024a), we use an ensemble of S O Olog T' random networks as follows:
f(5) (o: (0:x,,
1 S
Σ
ea);,
(15)
==1
where each e, is Rademacher vector. We projected OGD the loss function
C ye, ((00)
> lsq (ve. ((0:x., (.)):
(16)
which with the projection operator
II (0) = arginf - 0|12 gives us the following update:
B
0+t = II (0. m v V
(S)
(t F((0 xt, e.) e.))
(17)
We now prove a regret bound for C-SquareCB with feed forward neural networks (neural E-SquareCB) and OGD regression oracle.
8

---

Published as a conference paper at ICLR 2025
covertype
fashion
MagicTeleecope
CB
CB
SquareCB
FasICB LinUCB
FasiCB
LinUCB
2.0
C LinUCB
FastCB
Regrot
Regrot
Regret
9.5
0.5
1000
2000
3000
4000
5000
1000
2000 Rounds
3000
4000
5000
1030
2000
3300
4000
5000
Rounds
Rounds
mushroom
3.0
SquareCB
Square CB
SquareCB
2.6
FastCH
FastCB LinU/B
C C-F C-astCCB
2.0
LinUCB
LinUCB
Regret
Regret
1.6
1.0
0.5
1000
2000
3000
4000
5000
1000
2000
4000
5000
1000
2000
4000
5000
Rounds
Rounds
Rounds
Figure 1: Comparison of cumulative regret of C-SquareCB and C-FastCB with the baseline C-LinUCB on openml datasets (averaged over 10 runs).
Theorem 5.1 (Regret bound for Neural C-SquareCB). We instantiate Sq-Alg Alg with the predictor Gt.a. = f(5) (0;x,,
x,, el e from (15) and update the parameters using OGD in (17). Under Assump- lions 1,2, 5 and with "tt in Theorem 5.1, step-size sequence {m,), width m, perturbation constant Cp, and projection ball B, with high probability (1 (6)), the performance constraint in (2) is satisfied by C-SquareCB and the regret given by
Regas (T) s {OVVTTooTT +
K Kllog T log
+
ayı( ayı)
Next, for the first-order bound, we use the following ensembled network as the predictor:
(f(s) (0; x1, g (1::7))
1 Σ a (f((:x,,
(18)
where f(0; Xx, Ex) is defined in (14) and ((.) is the sigmoid function. Our theorem provides a first-order regret bound for C- C-FastCB when coupled with feed-forward networks and OGD.
Theorem 5.2 (Regret bound for Neural C-FastCB). We instantiate Sq-Alg with the predictor xt,e (1::S)) from (15) and update the parameters using OGD in (17). Under As- sumptions 1,2, 5 and 6 with i/ chosen as in (7:-Schedule), step-size sequence {nt), width m. perturbation constant Cp. and projection ball B, with probability (1 -(()), the performance
Út.a, = f(8) (0; xt,
constraint (2) is satisfied by C-FastCB and the expected regret given by
Regca (T) S 0 (VKT. KT. log log T + log T
K log
ay A + az))
EXPERIMENTS
We evaluate our algorithms C-SquareCB and C-FastCB and compare the regret bounds with the existing baseline- Conservative Linear UCB (C-LinUCB) (Kazerouni et al., 2017). The algorithm estimates the parameter associated with the cost function using least squares regression and uses existing results on high probability confidence bounds around the estimate (Abbasi- Yadkori et al., 2011) to up safety condition. When the safety condition is satisfied, it plays actions according to Linear UCB (Chu et al., 2011: 1; Abbasi- Yadkori et al., 201 1), otherwise switches to the baseline action. We tune the ridge parameter in (0.001, 0.005, 0.01, 0.05, 0.1).

---

Published as a conference paper at ICLR 2025
covertyoe
CThlescops
Sqaaarc Farca
D-FweDk
SouncC
Fanca
Fani2
Spaniii
C-
0.04
2.95
1.10
3.02
0.04
0.95
0.21
0.04
1.1
0.02
0.04
3.55
9.25
Figure 2: Comparison of Percentage of Constraints violated by C-SquareCB and C-FastCB with their vanilla non conservative versions on openml datasets (averaged over 100 runs).
We use the evaluation setting for bandit algorithms developed in Bietti et al. (2021) and subsequently used in Zhou et al. (2020); Zhang et al. (2021); Ban et al. (2022); Deb et al. (2024a). We consider series of multiclass classification problems from the openml.org platform. We transform each d- dimensional input into K different context vectors of dimension dK, where K is the number of classes as follows: X,, = (x,, O, O, ................................ .0)", X (0, X2, O.... O)?)...... ,,....,y.K'
(0,0.... 0, x,x,) The K vectors correspond to the K different action choices in the bandit problem. We assign a cost of all the context vectors associated with the incorrect classes, and cost of 0.01 the correct class, Note that when an action corresponding to an incorrect class is selected, the learner does not learn the identity of the action with the lowest cost. For each of the datasets, we fix one action as the baseline action, and the baseline policy corresponds to always choosing this pre-defined action.
C-SquareCB and C-FastCB use a two layer neural network with ReLU activation and width 100. We update the network parameter every 10-th round and do grid search over step sizes {0.01, 0.005, }.
In C-SquareCB we set {10, 20, 50, 100, 200, 500, 1000). For C-FastCE, since the optimal loss I, not known in ad- vance, the exploration parameter is treated as a parpee--rramtter in our experiments. We set % =Y and tune it in {10, 20, 50, 100, 200, 500, 1000}. Deb et al. (2024a) tune for different choices of the perturbation constant (see Appendix F in Deb et al. (2024a)) and show that the unperturbed version perform almost as good as the perturbed ones, and are computationally more efficient. We saw a similar behavior in experiments and report the final plots for only the unperturbed networks.
c log(8-1) and tune in
We compare the cumulative regret of the algorithms in Figure 1. Note that C-SquareCB and C- F-FastCB consistently show sub-linear trend in regret and beat the existing benchmark, with C-FastCB performing better in some of the datasets, owing to it's first order order regret guarantee. We also compare it with another heuristic choice, where we substitute Σ L; by the sum of the observed losses until time t - 1, i..., Σ L, choose Yts and note that it produces good results in the majority of environments (See Figure in Appendix F). We also compare the performance of the algorithms for various choices of width of the network (see Appendix F).
Finally, we compare the percentage of constraints violated by our algorithms C-SquareCB and C-FastCB compared to their vanilla counterparts that does not use any safety condition in Figure 2. Our algorithms maintain the performance constraint while minimizing the regret.
CONCLUSION
In this paper, we developed two new algorithms, C- C-SquareCB and C-FastCB, for the problem of Conservative Contextual Bandits with general non-linear cost functions. Our algorithms use Inverse Gap Weighting (IGW) for exploration and rely on an online regression oracle for prediction. We provided regret guarantees for both algorithms, showing that C- S-uuareBB achieves sub-linear regret in T, while C- C-FastCB achieves first-order regret in terms of the cumulative loss of the optimal policy L We also extended our approach by using neural networks for function approximation and provide end-to-end regret bounds. Finally, through experiments on real-world data, we showed that our methods outperform existing baseline while maintaining safety guarantee. Adapting our methods to other safe bandit frameworks such the stage-wise setting (Moradipari al., 2019; Amani et al., 2019) and to the more general reinforcement learning framework following Foster et al. (2023b) and Foster al. (2023a) is left for future work.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Naoki Abe and Philip M Long- Associative reinforcement learning using linear probabilistic concepts. In ICML, pp. 3-11. Citeseer, 1999.
Naoki Abe, Alan W Biermann, and Philip M Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263-293, 2003.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Alekh Agarwal, Sarah Bird, Markus Cozowicz, Luong Hoang, John Langford, Stephen Lee, Jiaji Li, Dan Melamed, Gal Oshri, Oswaldo Ribas, Siddhartha Sen, and Alex Slivkins. A multiworld testing decision service. ArXiv, abs/1606 100.0666,,,,,6, 2016. URL https: /apii.pp...// eeemanticscool aar.
org/Corpus ID: 18 770075
Alekh Agarwal, Akshay Krishnamurthy, John Langford, Haipeng Luo, and Schapire Robert E. Open problem: First-order regret bounds for contextual bandits. Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 4-7, PMLR, 07-10 Jul 2017a. URL https: /ttppp::/ppooeeo /pppceedingegsss mlr. press/v655 agarwal17a, html.
Alekh Agarwal, Akshay Krishnamurthy, John Langford, Haipeng Luo, and Schapire Robert E. Open problem: First-order regret bounds for contextual bandits. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 4-7. PMLR, 07-10 Jul 2017b. URL https: /ttpp/peoecegg.....//////. .ww..n.......................... mlr.. press/v6 agarwall76 html.
Shipra Agrawal and Nikhil R. Devanur. Linear contextual bandits with knapsacks. In Proceedings of the 30th International Conference Neural Information Processing Systems, NIPS' 16, pp. 3458-3461 Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Shie Mannor, Nathan Srebro, and Robert Williamson (eds.), Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 39. 19.1-3,. Edinburgh, Scotland, 25-27 Jun 2012. PMLR. URL https: ppwcoedeeeeeeeeoeeooooooccoeeeee nngs. mlr. salrspress.. pwtpsss2sseeeeeeeeee...p.....oee
v23 agrawa 12. html.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pp. 127-135. PMLR, 2013.
Zeyuan Allen-Zhu, Sebastien Bubeck, and Yuanzhi Li. Make the minority great again: First-order regret bound for contextual bandits. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 186-194. PMLR, 10-15 Jul 2018. URL https: /ttp:://pprceeee pproceed ngs. m1 alr.ppres/v80/. allllllll en- wh11hh0000 8l. html.
Zeyuan Allen-Zhu Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In H. Wallach, H. Larochelle, Beygelzimer, d'Alché Buce Fox, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: httpttttt/t/tteseeettette http://///coceeeeeeeeeeee neurips cc secpppperr__eeeeeeeeeeeeeeeeeeee lellepppppe 2019 9/ // e 9 8a 8 bab.ddfeeeee wttpd/eeeee115442ee2222223220 www.a3aaaaaappppppppp
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019.
11

---

Published as a conference paper at ICLR 2025
Peter Auer, Nicolò Cesa-Bianche Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed ban- dit problem. Mach. Learn., 47(2-3):235-22 3)222226,,, may 2002. ISSN 0885-6125. doi: 10.1023/A: 1013689704352. URL hitps: / /doiiiiooo/ooooo/.ooo /ttp://..r......../////1./111130
10.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In 2013 IEEE 54th Anmual Symposium on Foundations of Computer Science. IEEE, oct 2013. doi: 10.1 20t//foocs.211..333 URL https:ttt///o...
htops://doi... htt.//doi..o wtw.dio.rggoooooooooooo.oooooo.t
11 110982F focs. 2013.30.
Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. EE-net: Exploization-explortiio neural networks in contextual bandits. In International Conference on Learning Representations, 2022.
URL hwtps:tpp//... http:///ppnneeeeeeeeeeeeeeeseeee htt.rieewwee/ooourttt. forum? dedd__ch3viillh
Arindam Banerjee, Pedro Cisneros- Asneros-Vellare, Libin Zhu, and Misha Belkin. Restricted strong con- vexity of deep learning models with smooth activations. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https: http:////pprrreeeeeomo net forum?id=
PINRbk 7h01.
Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. Journal of Machine Learning Research, 22(133):1-49, 2021. URL http: hattt::/jmlr..tm wwwpoo/pppppppp///.oo/oooo/// 863.
html.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial ban- dits. Conference on Learning Theory, pp. 42-1. JMLR Workshop and Conference Proceedings, 2012.
Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
Sébastien Bubeck.
Introduction to online optimization, December 2011.
URL
https: /wwp://wwww././// wwwp::/w..coooo..ooomoo
ontroducttionn-ollne---- www.////ennnseeeeercceceecccecee
Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning parameterized deep relu networks. In AAAI Conference on Artificial Intelligence, 2019.
Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice, 2006a. URL https: http///axxvvvv/// httg///r///////aaaaaaaaaaa
629.
Nicolo Cesa- Bisa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice, 2006b. URL https: www.iiovorrrooooooo. aabrg//b/////// http://ahhha/e 00000/00066666 629.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
Rohan Deb, Yikun Ban, Shiliang Zuo, Jingrui He, and Arindam Banerjee. Contextual bandits with online neural regression. In The Twelfth International Conference on Learning Representations, 2024a. URL puttpps://i http:///pppeeeeeeeeeee
net/ /att/forune
Rohan Deb, Aadirupa Saha, and Arindam Banerjee. Think before you duel: Understanding complexi- ties of preference learning under constrained resources. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 Proceedings of Machine Learning Research, pp. 3546-4554, PMLR, 02-04 May 2024b. URL https: httttts::/ppoceeeeee http///pcceeeedneecece/ ml prwss v2232 4ab24a.httl.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-1685. PMLR, 2019.
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty- Seventh Conference on Uncertainty in Artificial Intelligence, UAI'11, 11, pp. (69-178, Arlington, Virginia, USA, 2011. AUAI Press. ISBN 9780974903972.
12

---

Published as a conference paper at ICLR 2025
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Cu- lotta (eds.), Advances in Neural Information Processing Systems, volume 23. Curran Asso- ciates, Inc., 2010. URL. httpss/ /ttp:::://////ceeeeoeeooooe neurips www.iiisscppppppeeeeeeeeeeeeeeee cc/paper_ Filee//pp esspe/rr////// http://e//22655o0eee0eea11aaaaaa
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199-3210. PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1539-1548. PMLR, 10-15 Jul 2018. URL https: pettps://proceeeee /ppc:///eccceeegg......
Salr.press v80 www./r/steee.ee.e.eoeoeeeaaaaaee ptrpes//oo/oooteeeaaaaaaatt
Dylan J Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34, 2021.
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting misspecification in contextual bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 11478-1144 1489. Curran Asso- ciates, Inc., 2020. URL httpttppp://ppoppeeeteeteee 2020/ f feleeeelllee 20t0:///AAA222000000406666611010
neuri cc cappaer fi files/ les/paper/
Dylan J. Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimation coefficient. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 3969-4043, PMLR, 12-15 Jul 2023a. URL https: https///pocoeeddeegee mll.. press/v195 htt//oostee3333 html.
Dylan Foster, Noah Golowich, Jian Qian, Alexander Rakhlin, and Ayush Sekhari. Model- free reinforcement learning with the decision-estimation coefficient. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 20080-20117. Curran Associates, Inc., 2023b. URL https: ptoppedioeeennnseeeeeeeee. neurips cc/paper files/ pttees//pppp//2255 hale/3fcc0f884775B 7c6dbo4 5ed1 38b1 fde Paper- Cwwferanneeeeeeeoeoooooo .ddf.
Yoav Freund. Open problem: Second order regret bounds based on scaling time. In Vitaly Feld- man, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1651-1654, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https: httppsss///cceee//ppe/e mlr. press/
Dress/v49/1 449 freundl html.
Yoav Freund and Robert E Schapire. A decision-theoretic generalization on-line learning and ap- plication to boosting, Journal of Computer and System Sciences, 55(1):119-139, 1997. ISSN 0022- 0000. doi: com/
URL https: www.w/www....ooo....wo.... sciencccrree.....
Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses, 2014.
URL /ictps://aziiv. .og. /adss/4422 2044.
Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Improved algorithms for conservative exploration in bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):3962-300 3969, Apr. 2020. doi: wt..0///aai..3444.5.... https://ojs aaai. org/ index. php/ AAAI http///atteeeeeeeeeeeeeee
URL
Yuxuan Han, Jialin Zeng, Yang Wang, Yang Xiang, and Jiheng Zhang. Optimal contextual bandits with knapsacks under realizability via regression oracles. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent (eds.), Proceedings of The 26th International Conference on Artifi- cial Intelligence and Statisfies, volume 206 of Proceedings of Machine Learning Research, pp.
13

---

Published as a conference paper at ICLR 2025
5011-5035. PMLR, 25-27 Apr 2023. URL UtL.tttpss//pproceddns........sp han2 3b. html.
Elad Hazan. Introduction to online convex optimization, 2021.
Nicole Immorlica, Karthik Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. J. ACM, 69(6), nov 2022. ISSN 0004-5411, doi: 10.1145/3557045. URL https: //t::///do//////oo /ttggg/0..... 1145/ 1145.35574153555 3557045.
Shinji Ito, Shuichi Hirahara, Tasuku Soma, and Yuichi Yoshida. Tight first- and second-order regret bounds for adversarial linear bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2028- 2038. Curran Associates, Inc., 2020. URL http:::: httptttt////p/roedednng http://ceee.inn.......eeeeeeeeee neurips cttccc//pppeeeee.. paper_ files https//ppppp//2////peee
Paper pdf.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi Yadkori, and Benjamin Van Roy. Conservative contextual linear bandits. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: https://proceedii file/bde 62 det.aaaddd11811110011111
neurips wwtpaper_ffteeeeeeeeeee poperrrfless_ee httpppppppr//// 42d- www.paapppppp..
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2071-2080. PMLR, 06-11 Aug 2017. URL https: http://proeeeesceee/ee/e/csss.se wwt.mmlt....m....mmmmmmmm 1i17c.html
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel constant. Advances in Neural Information Processing Systems, 33: 15954-15964, 2020.
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 326003266 Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 17855606
Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Safe linear thompson sampling. ArXiv, abs/1911.02156 2019. URL https://///// /api. semanticsccoleee
org/CorpusID: 207794176.
Aldo Pacchiano. Second order bounds for contextual bandits with function approximation, 2024.
URL httpt::t///at /arssii///iviv.// org/ abs abs/2409 16197.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An em- pirical comparison of bayesian deep networks for thompson sampling. In International Confer- ence on Learning Representations, 2018. URL httpp:://pppeeeeeeeeeeeeeeeeeeee
net / forum?id
SyYe6k-CW.
Shai Shalev-Shward Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012. ISSN 1935-8237. doi: 10.1561/2200000118 URL http::/dse doi 100g/11.000 . 1561 /22000000
David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. ArXiv, abs/2003. 12699, 2020.
Vidyashankar Sivakumar, Shiliang Zuo, and Arindam Banerjee. Smoothed adversarial linear contex- tual bandits with knapsacks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 20253-20277 20277. PMLR, 17- 23 Jul 2022. URL https:ttppt... http://prooceeee ngs ml press / v1 62. va kuma r22a html.
14

---

Published as a conference paper at ICLR 2025
Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J. Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression, 2023.
Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvari. Conservative bandits. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd Interna- tional Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Re- search, pp. 1254 1262, New York, New York, USA, 20-22 Jun 2016. PMLR. URL https: //proceedings... mlr press / v48 wwwl 6.166... html.
Tom Zahavy and Shie Mannor. Neural linear bandits: Overcoming catastrophic forgetting through likelihood matching, 2020. URL https: /tpp/reeeeeeeeeeeeeeeeeeeeeeeeee /
net/ forum 7id=riliiii weiidddrrddahaiie gzchEKvH.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference Learning Representation (ICLR), 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 1 11492-11502 11502. PMLR, 2020.
15

---

Published as a conference paper at ICLR 2025
A RELATED WORKS
Contextual Bandits. The study of bandit algorithms, especially in the contextual bandit setting, has seen significant development over the years. Initial works on linear bandits, such as those by Abe et al. (2003), Chu et al. (2011), and Abbasi- Yadkori et al. (2011), 1), laid the foundation for exploration strategies with provable regret bounds. These works primarily leveraged linear models, achieving near-optimal performance in various settings. Agrawal & Goyal (2012) provided regret guarantee for the Thompson sampling algorithm in the multi-armed case and later extended it to the linear setting with provable guarantees (Agrawal & Goyal, 2013). The success of linear bandits naturally led to their extension to more complex settings, particularly nonlinear models. Generalized linear bandits (GLBs) explored by Filippi et al. (2010) and Li et al. (2017) introduced non-linearity through a link function, while preserving& a linear dependence on the context.
Contextual Bandits beyond linearity. More recently, the rise of deep learning has led to interest in neural models for contextual bandits. Early attempts to incorporate neural networks into the bandit framework relied on using deep neural networks (DNNs) as feature extractors, with linear model learned on top of the last hidden layer of the DNN (Lu & Van Roy, 2017; Zahavy & Mannor, 2020; Riquelme et al., 2018). Although these methods demonstrated empirical success, they lacked theoretical regret guarantees. The NeuralUCB (Zhou et al., 2020) algorithm combined neural networks with extended to Thompson Sampling in the work of Zhang et al. (2021), with both methods drawing on neural tangent kernels (NTKs) (Jacot et al., 2018; Allen-Zhu et al., 2019) and the notion of effective dimension d. However rcently Deb et al. (2024a) showed that these bounds are ((T) in the worst case even with an oblivious adversary. These methods also suffer from the computational complexity of inverting large matrices at each step of the algorithm remained a limitation, as the inversion scales with the number of neural network parameters. In response, Ban et al. (2022) introduced novel approach that achieved regret bounds independent of the effective dimension d, though this method required specific distributional assumptions on the context.
exploration, and provided regret guarantees. This approach was further
Agnostic Contextual Bandits. Concurrently, agnostic algorithms for bandit problems were also studied starting from Dudik et al. (201 1); Agarwal et al. (2014). Foster et al. (2018) provided an approach leverage an offline weighted least squares regression oracle and demonstrated that this approach performs well compared to other existing contextual bandit algorithms. However, despite its success, the algorithm was theoretically sub-optimal, potentially incurring high regret in the worst case. Subsequently (Foster & Rakhlin, 2020) adapted the inverse gap weighting idea from Abe & Long (1999); Abe al. (2003) related the bandit regret to the regret of online regression with square loss, while Foster & Krishnamurthy (2021) modified (Foster & Rakhlin, 2020), with binary Kullback-Leibhen
(KL) loss and a re- weighted inverse gap weighting scheme to provide a first-order regret bound. Further, Simchi-Levi & Xu (2020) showed that an offline regression oracle with Olog 7') calls can also be used to derive optimal regret gurantees for the general realizable case. This improves ove the O(T) calls by Foster & Krishnamurthy (2021) and (Foster & Rakhlin, 2020) and also relaxes the assumption to offline oracles instcad of online, however it needs to make a strong assumption about the contexts- they are drawn i.i.d. from fixed distribution.
Constrained Bandits. Bandit problems under constraints have also been studied extensively. The Bandits with Knapsacks problem looks cumulative reward maximization under budget constraints (Badanidiyuru et al., 2013; Agrawal & Devanur, 2016; Immorlica et al., 2022; Sivakumar et al., 2022; Deb et al., 2024b). The general cost function case as in this work has been studied in Slivkins et al. (2023); Han et al. (2023) and provided sub-linear regret bounds using the Inverse gap weighting idea from Abe & Long (1999): Foster & Rakhlin (2020); Foster & Krishnamurthy (2021). In the stage- wise constraint setup, each arm generates both reward and cost signals from unknown distributions. The objective is to maximize cumulative rewards while ensuring the expected cost stays below a threshold at each round. Amani et al. (2019) and Moradipari et al. (2019) investigated this setting in the context of linear bandits, developing and evaluating explore-exploit algorithm and a Thompson sampling algorithm respectively. The setup in this work. conservative bandity was introduced in Wu et al. (2016) and subsequently studied in the linear setting Kazerouni et al. (2017); Garcelon et al. (2020), and all existing methods use modified version of UCB. To the best of our knowledge neither a Thompson Sampling version has been studied, nor an oracle based approach for the general function case.
16

---

Published as a conference paper at ICLR 2025
Data Dependent Regret Bounds. Adaptive algorithms can often perform better if the environment it is operating in is comparatively easier. A data dependent regret bound tries to capture such a phenomena. In first-order regret bounds, the regret scales as in L. = Σi= la the cumulative loss/cost of the optimal policy. It has rich history, with Freund Schapire (1997) proving the first such bound for the full information setting (or the classical expert setting) using Exponential Weights algorithm. For the K- K-armed bandit setting (with no contexts), first order bounds were provided in
Agarwal et al. (2016). For the adversarial setting Agarwal et al. (2017b) provided O(L. bound and subsequently also posed an open problem COLT *Can first-order regret bounds be developed for contextual bandits ?'. Allen-Zhu et al. (201 8) responded by providing first order bound with an inefficient algorithm, and subsequently Foster Krishnamurthy (2021) provided an algorithm with a reduction to online regression that was both efficient and provided a first order regret.
Cesa-Bianchi et al. (2006a) first posed the question of whether further improvements could be achieved by deriving second-order (variance-like) bounds on the regret for the full information setting. They provided two choices for second order bounds, one that depends on Σ lra; (variance across time) and another that depends on EksK Pt.c lx,1)² (variance across actions), where & = - Pt. and Pk. is the probability with which expert l: is chosen in round t. For more detailed discussion of second order bounds we refer the reader to Ito et al. (2020); Gaillard et al. (2014); Freund 2); Ito et al. (2020); Cesa-Bianchi et al. (2006b); Pacchiano (2024).
B PROOF OF REGRET BOUND FOR C-SquareCB
Lemma 3.1. Let Assumptions / and 2 hold. Then, the regret defined in (1) can be bounded as
Regcs (T) S Σ (((xt,,))) l((xaa;) + TT
(6)
LEST
where the set ST consists of the rounds until the horizon when C-SquareCB played an IGW action and no- = |S4 is the number of times until T where baseline action was played.
Proof. The decomposition follows as in Proposition 2 in (Kazerouni et al., 2017), and we reproduce the proof here for completeness. Recall that ST = {t E [T] a = b,} is the set of time steps when the baseline action was chosen and St {t [T] a āe) is the set of time steps when the SquareCB action was played. Then, we can decompose the regret as follows:
Regca (T)
Σ h(x(,a)) Σ h(x(aa)
(0)
(h(xt,a)) -h(x),o;) + Σ
(N(x)o)) - -h-hhhee h(xx,;))
ME
rESS
(b)
Σ
(1(xt,a)) ((xxo;)) + Σ Alr
LEST
LES;
Σ
(((x),a)) n(xe,a)) + n Dr.
1EST
where (a) follows because US [T], (b) follows by the definition of AG, -h(xe,,)) h(xx, (x)) and (c) follows by Assumption 2.
Lemma 3.2. Suppose Assumption 1,2 and 3 holds. Then, with probability 1 6/4 4 the number of times the baseline action is played by C-SqqareCB is bounded as
nT < azy
(m,-1 + () + -ay)
+ +44 K (m,-1 + +1)(1 Regso + vlog(8-11) }
17

---

Published as a conference paper at ICLR 2025
Proof. Let T be the last round at which the algorithm plays the conservative action, i.e.
max I t S Taa b.).
Recall that my [ and n4 S By the definition of т, we have that round
ar
Σ Piabia
Σ
h(x(,b,) + 16 mr-1
Regsa (T) + log(2/6)
iES!
> (1+ a
h(x,,,,).
Therefore, we may write
((xi,,))
E
Σ Pioolia + trāā
Σ
(h(x);))) + l(xx.,))))
==1
iES--1
+ 16 m+-1
Regsa (T) + 1oog(/00)
Σ
E Piaatiia +r.a. E
E Prah(xx,a;)
EES [0E[K]
iES,
InE(k]
Σ
Σ
Pxial(Xi,a;) + Σ
Prahl(xra
iES, Lac
aE[K]
Σ Priah((x,a;)
Σ
(h(x)),b)) h(xx,
aE(K]
iES--1
+ 16 mr-1 Regga (T) + log(2/6)
Σ (h(xi,a)) - ((xx,,,)) + (h(x+,a;) h(x(.b)))
1ES,-1
Σ
Psá (Dh. ((xx,7))) +
Σ
Pr, (Br,a -((x),))))
(19)
iES,-1 [E[K]
KE[K]
111
16 m Regsa (T) + -log(2/0)
First consider term T. Using Assumption we have that A 11 h((xxa;)) -((x)))) Ao. Also recall that m | Combining these we have:
Σ
(h(x),a;) h(xx,,,) + (h(x+,a;) - h(xx,b.)) < -( 1)4
1ES.-1
Next consider term IT. Adding and subtracting h(xx,a), obtain
Σ Σ
Pi.a 0r. - h(xxaa))
Σ
Σ
Pi.a (N(xs,a) n(xx,,;)
KES,
[ K]
iES,
[E[K]
I1(a)
+
Pi,a @i.a h(xx,a))
KES. 1
I7(b)
18

---

Published as a conference paper at ICLR 2025
Consider term I[).). Using Lemma 3 in Foster & Rakhlin (2020) we have
Σ
Pi. h(xi,a) h(xi,;)) 7i (ūia - M(xia))
K
%
oE[K]
Now summing for all E S we have
Σ E Pio ((xxaa) 1(xi,;))
7i (Via - Mixia))
S Σ
K
4
BESt-1 [E[K]
IEST-1
Using this, we can bound term (T)a) follows:
Σ
Σ Pi.o (h(x(,a) h(xx,o)) 5
2K
Σ
Σ
Ji Pi.e (dia h(xx,o))²
K
4
iES, [E[K]
iES,
iES, [
Now recall that 7 / (K)s:l/2Reggs, (7) 16 log (og(88011 (86-1)) and therefore plugging this back in the above equation we get
Σ
Σ
Pio (h(xi,)) h(xx,,;)
2K 7
+ Σ
Σ
Ye Proaair. - h(xxa))²
4
iES,-1 [E[K]
IES--1
iES,
KE|K]
2Regsq (T) + 16 16log(88-1
-2K
Σ
K|S:
1ES,-1
1 Σ
K|S
Σ
Pi,a (araiia h(xi,a))
4
(2Regaq (T) 16 (1((8-11))
SES
aE[K]
(a)
m,
I 2/
K ((2Rogsg (T) + 16 16log(80 86 1))
Vi
+ 4 2Rega (T) 16log(80-)
1
Km Km,-1
Σ
Σ
Pi,a (Di, h(xx,a))²
iES.-1 aE[K]
Km,-1
In (a), we used the fact that 7/ depends on |S and that max 7/
rES,
2egga (T) + 16 log(85-1)
Now note that the C-SquareCB actions are only played for i ST and therefore invoking Assump- tion 3, we can use Lemma 2 in Foster & Rakhlin (2020) to show that with probability 1 - 5/4
Σ
Σ
Pi.o (Via h(xx,a))) < 2Regeq + 16 log((8)11)
LEST-1 [E[K]
Further note that
Σ Vi
1
22
Therefore term (T(a) can bounded as
Σ Σ
Pi.a (1(x),,)) l((x)aa))
VES, KE(K]
$ / Km,- (Regag (T) + +log(88-)))
1
Km
(Regs)(m,-1) + 16log(85" 1og(88-1))
4V 2Regsa (T) + 16 16l0g(85-)
< 17 117/Kmm
(v /Regsq (T) + / Vlog(86-1)
where we have used the fact (ega((m,-1) (T).
19

---

Published as a conference paper at ICLR 2025
Now consider term (b). Suppose Ep: be the expectation with respect to Pi,a- Then, may write
Σ
Σ
Pi.o (((x.a)) Di.))
Σ
Ep
(h(xiaa) - Vi.aa) -Di.))
(EST-1RE|K]
iESt-1
Σ iES.-1
Ep, V (h(xia)) Diaa)
(a)
Epg (h(xiaa) Di,a)
VES,
In
m
Σ
Σ
Piaa (a(xh,a)a)) Di.a)
SES,
aE(K]
where (a) follows by Jensen and (b) follows by Cauchy Schwartz. Again, using Lemma in Foster & Rakhlin (2020), with probability 1 0/4, we have
Σ
Σ
Pi,a (M(xi,)) - Dia)) s ///m
16 (ogg(86-1))
$ES--1 aE[K]
Finally consider term III. Since 0 S h(xr,a): Fi.a may write
Σ
Pr. (Urāū - l(xx,a))) 2.
ac[K]
Combining all the bounds, for K 2 2 and Regsg (T) 2 1, with probability 1 8822, have
((x...)) S ( 1)4, + 64v K (mm--i +1) (
/Regsq (T) + vlog(80-1)).
(20)
Now, using the fact that + +1 = т, and Assumption 2, we have S h(x(b;)) S yh, Vi E [2]] Therefore,
M(x,,.)) 2 a (m,-1 + n, + 1) Vt-
Combining this with (20), with probability 1 - -5/2, we obtain
an.-1391 S -m + 1)( ay: 64v K (m,-1 + 1) [Regsq(T) + /log(88-1)
-m + 1) A + om)) 64 K (m--1 + (Regaa(T) + vlog(86-1)
Finally, using nr = n, 74 1, with probability 1- 8/2, we have
(m,-1 + 1)(A + am)) + 64V (m--1 +1] (1) [Regsg(T) log(20-1)
nor
Lemma 3.3. Suppose Assumption 1,2 and 3 holds. Then, with probability 1 8/ the number of times the baseline action is played by C- C-SquareCB is bounded as follows:
K (Regs, (T) + log(86 (85 (86--18)
11 < 50
(8)
oy A + oy
Proof. Let us define
Q(m+-1)= - -mm7-1 1)(A: + oz)) + 64VK KoVKK//maa (m
+11] (veegs (T)
1ogg(2-1)
20

---

Published as a conference paper at ICLR 2025
Note that we have
Q(m+-1) -cm + c=ym: f(m)
where
A + ar 20,
64vK
(Regsq(T) + 1og(2001) (21--))) 2 0,
m 11- +
Setting (mm)) = O, and solving we get m
Now note that f is concave and that f"(m") < 0
4c9
and therefore,
2
c2
Q(m+-1) S f(m) & f((mm)
+
4c1
2c1
4ci
<[Regga (T) + (Pg(26-1))
0
D + axy
Finally noting that no S n + +1s (m 1 completes the proof.
azy
Lemma 3.4. Suppose Assumptions 1 and hold. Then, for
0 and Vt
v S (Regsa (T) + 1og((0-1))) with probability 1- 8/4, C C-SquareCB guarantees
Σ 1EST
((xx,a)) 11xxxxx1) 1(xx,o)) s s0(v KmrrRegsg(TT (T) + v Kmr log(88
(10)
Proof. Using Lemma 3 from Foster & Rakhlin (2020) for any i E [K] we have
Σ Pi.o
M(xx,a) h(xi,a;) Y' (ūi, M(xi,o))
K
%
KE(K]
Now summing for all E ST have
ΣΣ Pia h(xi,)) 1(xi,o))
24 (Di.a -((xia))
K
iEST RE[K] Using this get the following bound:
4
EEST
78
Σ
Σ Pi.o (h(x).a;) h(xx,a)) 5
2K
Vk 4 Pi,a (Br. h(xx,,))²
Y
FEST [E[K]
iEST
VEST
KE|K]
Now recall that %/ (K(Sil//RBBs (T) + 16 log 88 1)) and therefore plugging this back in the above equation we get:
Σ
Σ
Pia (h(x),a;) ((x(aa) 5
2K
+
Σ
Vi Pr.a(ora n(xx,a))
4
iEST aE(K]
FEST
iESt aE[K]
Regsy (T) + 16 16log(80 (88-1)
2K
K|S,
EEST
1
K|S,
Σ
Pio (Dria - 1(xxaa))
4 S
(Regag (T) + 16 (20-1)) aE(K]
(4)
mT 1
< 2/
K
(Reegs + 16 180 (8)-
1
KmT
+
Σ
Σ
Pi.a (Di.a h(xx,a))
4
Regsq (T') + 16 log (86-1)
SeSt aE(K]
21

---

Published as a conference paper at ICLR 2025
K KmT
In (a) we used the fact that 7/ depends on |S:] and that max "i =
Regsg (T) + 16 (8g (86-1) Now
sES;
note that the C-SquareCB actions only played for i E Sr and therefore invoking Assumption we can use Lemma from (Foster Rakhlin, 2020) to show that with probability - 6/4
Σ
Σ
Ps.a (Br.a h(xx,a)) I 2Regsq (mr) + 16 log(86
iEST [E(K]
Further note that
Σ
1
I m// Therefore term (T(a) can be bounded as follows
Σ
Σ
Piaa (M(x)a;)) - 1((xia)
iESy aE[K]
V (Regsgg) (T) + 16 (6log(88-1)
1 + VV 2Regsq (T) + 16 1og
Kmr
2Regag (mTT + 16 16log(80
17 KmT
(Regsa (T) + 1lg(88-1))
(21)
where we have used the fact Regaq(mi) (mT) S Regsq(T)) (T).
Now modify the proof of Lemma 2 of Foster & Rakhlin (2020) to take the sum over i Sr instead of E [T] to ensure that with probability 5/4
h(Xs,,0.) h(x(,a;)) S
Σ
Σ Pia (h(xia;)) h(xx,)) + v 22m log( 88 1).
RE
iEST [E(K]
Combining with (21) and noting that Regsa (T') 2 1 get with probability 1 8//4
E1(xaa)) h(xx,a;) 3 KmT (VRega((T) vlog(80-1)
SEST
which completes the proof.
Lemma 3.5. Let Assumptions 1, 2 and 3 hold. Then, for ô and Y + 1og(80-1]], with probability 1 8/2, C-SquareCB satisfies the perfor- mance constraint in (2).
/
Proof. For f if the condition in line holds then â = 01 and we have that with probability
Ú1.01 16 (m/ + 1)(1 + log s (1 + ())(x)),)))
Noting that 101.0, h(x,,,,)) < 2 and therefore with probability
M(x(,.)) E (1 + (x)
Further, if the condition in line 8 doesn't hold, then
b, and therefore
h(xx,.,) I (1 + a ())xx,,))).
showing that the performance constraint in Definition 2.2 is satisfied. Now assume that the constraint holds for - and now consider E [T]. Note that
Σ Σ iES.-1 KE|K]
PiaBiaa h(xi,a))
Σ iEST-1 aE[K]
Σ
Pi.aDiaa
Σ
Σ Praal(xi,))
iES.
dE|K]
Σ
Σ
Piah((x;aa - h h(xx,a))
iES KE(K)
22

---

Published as a conference paper at ICLR 2025
Consider term I. We handle it as in the proof of Lemma 3.2 as follows: Suppose Ep, be the expectation with respect to Pi,a- Then
Σ 1E8 KE(K]
Σ
Pi, (b(xi,)) Dea)
Σ
Rps (h(xiaa - -vaa
1ES
Ep, (h(xia) - Di.a)
IES:
Σ iES
Eps (h((2),)) - (1,a)
IN
Σ
Σ Pio (h(xiaa) vi.))
M
[E
where (a) follows by Jensen and (b) follows by (Foster Rakhlin, 2020) with probability
Cauchy Schwartz. Again using Lemma 2 from
6
2
ΣEn Pi, (h(xx.,)) Diaa)
m (2Regsq(m) + 16 (olo(20-1))
(22)
iE8 aE(K]
Next, consider term II. Consider the following filtration
F (X1,e 0i, Vi,a.) X sist- (K])
Note that E [h( F =
Σ aE(K]
Pt, and therefore using Azuma-Hoeflding we have
8
that with probability
Σ
Σ
Piaal(xi,a) h(xiaa)) S mr- log
2
(23)
iES,-1 aE(K]
Combing (22) and (23) and taking union bound have with probability 1 8
Σ
Σ
Pi,aûi,a M(xi,a))
< 8V m Regsq(m+-1) + log((/))
iESt-1 aE[K]
Further lūr,ā. 1((x,aa)) < 2, and therefore with probability 1 8
fr. + Σ Σ
Piadia h(xx,a,) - h(x).a))) s 16 m4-1 [eggs)(m-)) + log(2/5)
iES, 115--1cEH [
(24)
Now line of Algorithm holds at time step t, then we have
Ut. Σ
Σ Piaadra +
Σ h(xx,,)) 16 m Regsq(m)-1) + log (2/())))
1 VESE
(1 Σ
M(x,,,))
1=1
and therefore invoking (24), we have with probability 1 -
M(xx,a))+ + Σ h(xia:)+ +
Σ M(xx,))) 5 S (1+a)
h(x,,b))
SES RESE
23

---

Published as a conference paper at ICLR 2025
Now note that for all i St-1, a; âi for all i S a, b, and using St-1 U -]. and the fact that the condition in line is satisfied we have with probability 1-
h(xt,o))
Σ h(x),a)) S (1 1E(C-1]
satisfying the performance condition in Definition 2.2.
Next we consider the case when the condition in line 8 does not hold. Invoking the fact that the performance constraint holds until time 1, we have with probability 1 à
Σ h(xi.o.)) S (1 ④
h(xi,b.)
Adding (xx,,,,) on both sides of the above equation we get
b( ((xi,))) h(xx,)))) + (1 a) Σ h(xx,b))-
Noting that when condition in line 8 does not hold at step t, then by and that > 0, we have with probability
h(Xi.a:) S (1 + a Σ h(xi,,,;;
satisfying the performance constraint Definition 2.2 for step t. Using mathematical induction we conclude that the performance constraint holds for all t E [2'. completing the proof.
C PROOF OF REGRET BOUND FOR C- FastCB
Proof of Theorem 4.1. The proof of the theorem follows along the following steps, and the proof of the intermediate lemmas can be found at the end of this proof.
1. Regret Decomposition: The regret decomposition follows using Lemma 3.1 in the proof of Theorem 3.1.
Lemma 3.1. Let Assumptions 1 and 2 hold. Then, the regret defined in (1) can be bounded as
Regca (T) - Σ
(h(x)a))- h(xxa;)) + Br
(6)
YEST
where the set ST consists of the rounds until the horizon T when C-SquareCB played an IGW action and nr |St the number of times until T where a baseline action was played.
Upper Bound on nr The condition Line determines how many times the baseline action played. Suppose m, |S,| and 7 m1 S L T: = br). i.e., the last time step at which C-FastCB played an action according to baseline strategy.
Before we proceed and give bound on ny, the number of times the baseline action is played by Algorithm 2, we specify how the exploration factor 7/ is chosen. Unlike in Foster Krishnamurthy (2021) where " = = max( / KL (3RegıL (T)), 10K), for all i E [K], we need to choose a time dependent 7 to ensure that control both ny and the regret by playing the con-conservative actions. However using a different 7; at every step does not lead to a first-order regret bound for the first term in (6). Therefore
7 in episodic manner, where % remains in
24

---

Published as a conference paper at ICLR 2025
episode. More specifically choose 7/8 follows:
70 = 1, 1, 1 =
for i ST
L; = -i + h(xxt,o))
if L; > 21)-11
? 21
(% SS-Shhheulle
else
?i 7i-1
Kt
7/ max
10K,
Regxu (T)
(a) The following lemma upper-bounds nr in terms of my Eies, (i), the cumulative cost in the set S,-1, and the KL loss Regxa (T), using the above schedule for " Lemma C.1. Suppose Assumption 1.2, 4 holds. Then, the number of times the baseline action is played by C-FastCB is bounded as
1T 5
(mr- + + 1)(A; + aag1)
03
+ 60
KRegm (T) log
Σ h(xi,;))
Σ h(xi,az) + +1
(25)
iES.-1
iEST-1
(b) Now note that since L (i( E 10,
Σ L"(1) my-1- Therefore the second term in 1ES,-1
(25) grows as V /m,-1 log m,-1 and that the first term decreases linearly in m,-1, and therefore one can further bound Pr in the following lemma.
Lemma C.2. Suppose Assumption Assumption 1,2, holds. Then the number of times the baseline action is played by C- SqqareeB is bounded as follows:
KRegu, log
eev (e (VKRegu(TT)
nT S
(26)
ayi(Ai agg)
A + agji
3. Bounding the Final Regret: We next move to bounding the first term in (6), with the schedule of it as described in Step-2. Note that Dr only contains the input-output pairs at time steps when the IGW action was picked, i.e., all & E Sy, and therefore, (11) reduces to
(ur, Vt.o,)
inf Σ ExL. (g((,, gEH
Vt...) Vt.a. S Regx(())
(27)
LEST
LEST
The next lemma bounds the regret of the first term in (6) with an adaptive n
Lemma C.3. Suppose Assumptions and hold. Then t chosen as in (7a-Schedule), we have
Σ (1(xx,a)) 1(xxaa)) s0 o KRegga (T) log (I's,) T.S
(28)
IEST
where L', = Σtesp 1((x,a;) is the cumulative cost of the optimal policy in the subset ST.
Note that L', < L and therefore combining (6), (26), and (28), the regret bound in (12) holds.
Performance Constraint: Finally the following lemma shows that the condition in Line 7 of C SquarreB ensures that the Performance Constraint in (2) is satisfied.
25

---

Published as a conference paper at ICLR 2025
Lemma C.4. Suppose Assumptions and 4 hold. Then for d >> O with "s chosen according ()--Shheulle), with probability 1 6, C-FastCB satisfies the performance constraint in (2).
Combining all four steps, C-FastCB simultaneously satisfies the performance constraint in (2)
with probability 1 - 6 and the regret upper-bound bound in (12), which concludes the proof.
Lemma C.I. Suppose Assumption 1,2, 4 holds. Then, the number of times the baseline action
played by C-FastCB is bounded as
1
nT 0/
(m,-1+ + + ag))
}
+ 60
Regg (T) log
Σ
h(xra;)
Σ
h(x;;a;) +1
(25)
iES,
iES,
Proof. Let T be the last round at which the algorithm plays the conservative action, i.e.,
T max S L = be).
Recall that m, = =[ and n2 = ( By the definition of r, we have that at round
Úr.a, + Σ Σ
Pia +
Σ
h(xx,,,) + 16 m, Rega (T)
iESK-10E[K]
iESS
> (1+ h(xa,b)-
Therefore, we may write
((x..b.)
Σ
Σ
Piaaiaa + fr.. - Σ (h(xa,,)) + 1(xx..o))
iES, [0E[K]
iES,
Σ
Σ Pi.aßiaa + Úr.a,
Σ (xa
IESt IESK-10[[K]
iES,-1aE(K]
Σ
Σ Praal(xia;;) + Σ (x
(EST-1aE(K]
dE[K]
Σ Pr.al((x,,a))
Σ
(h(xi,b)) + 1(xx..))))
aE[K]
VES--1
16 (egg
Σ (h(xi,a;) - h(xx,,,)) + (h(x),;;) h(xx,v)))
iES
Σ
Σ
Pio Traa ((xxaa)) + E
Pra (Br,ār h((xr,))))
(29)
iES, dE|K]
aE[K]
16 m, [RogaL (T) log(2/8)
First consider term /. Using Assumption we have that D h((x),a)) -1(xx,))) Dr. Also recall that my 1S,-1/- Combining these we have:
Σ (h(x),a;) h(xx,b,)) + (h(x+a;)) - 1(xx.b.)) < -0m--1++11 +1)
1EST-1
26

---

Published as a conference paper at ICLR 2025
Next consider term II. Adding and subtracting hxxxs,a), we obtain
Σ
Σ [
Piaa (Bia h((x)a)))
Σ
Σ
Pi.a (((xs,)) h(xxs,a))
KES,
iES,
[
[1(a)
Σ
E
Piaa (Dia h((xea))
iES.-1 [E(K)
11(b)
Using the AM-GM inequality bound term [I) follows:
1 (0r. - h(xx,a)) + (Di,a ((xx,,;)) )}
Σ Σ
Piaa (Bi.a h(x1,a;) ))
Σ
Σ Pi.a
43
Di.a + h h(xi,a))
iES--1 aE(K]
iESt-1 [E[K]
for any 1. Using Lemma 5 in (Foster & Krishnamurthy, 2021) have
(Úr.a h((x,,;))))
Σ Σ Pi 33 Σ (xx, +
Σ
Piaa Úh.a h(xx,a))
iES.-1 [E[K]
aE[K]
aE(K]
Therefore we have the following bound on term [I(b):
(Ui.a h(xi.o;) ))2
Σ Pi,a Dia (Biaa
Mxxn;;) ))
S
Σ
Σ
Piah + 23
Σ
Σ
Pia
Dia + h(xi,a))
iES.-1 [E(K]
LEST-1 aE[K]
iES,-1 aE[K]
Using Proposition 5 from Foster & Krishnamurthy (2021) we have
(Di,a 11(xi,;))) ))²
2,3 VES,-1
Σ Σ
Pi.a Úi, + h(xi,a;) S 4,3Rega (T)
and therefore,
Σ
Σ Pi,a (Din: M(xi,;;)
5 Σ
Σ
Pi (xxa((xi,a;) 4,3Regu (T)
iES, aE(K)
iES, 1 (
Σ h(xxaa)) + 4,Reggx (T)
3
iES
Choosing 3 = EiEs,-, h(xr,a;)
Regaa (T) we have
Σ Σ
Pi,a (Brie h(xxaa)) s
h(xi,a; Regka (T)
(30)
EES,-1
1ES
Next consider term [T))). We use the per round regret guarantee (Theorem 4) from Foster & Krishnamurthy (2021) as follows:
5K
(iia h(xx,,,))²
Σ Pi,a (N(xi,a.) l((xx,;;)) (E[R]
Σ
Pi,ai(Xi,,s)
+ 776
Σ
Pi,a Dia + ((xi,a;)
%
aE(K]
aE(K]
(31)
Adding and subtracting hxxx,,;) we get
Σ Pi.a (h(xs,a;) - h(xx)o))) < Σ [E[K]
5K
5K Pr,ch(xi,o))
Σ (h.a(((),,a)) h(x),a;))
7
7
aE[K]
dE|K]
(Dra h(x),a,))
+ 7m
Σ aE[A]
Pi,a Dia + h(Xi,a))
27

---

Published as a conference paper at ICLR 2025
and therefore
5K
Σ Pi,a (h(x),a)) h((x,a;))
5k
Σ
Praa((xi,a)) 7%
Σ aEIK]
(Ui,a 11 1xxxi,,))) ))2
7
Pi.a
Di.a 11(x3,as)
aE|K]
ØE|K]
Using 7/ 2 10K we have
Σ Pr.a
((()s,a))) h(x),a))
10K
Σ
proh((xiaz) + 14%
Σ
(Ui.a
h(xx..))2
%
Pi.a
Di. + h (xxx,o)))
[E[K]
[E[K]
ae(K]
(32)
Recall that we set the exploration factor y/ follows:
To- = 1,700 1 =0
for i ST
L = L + hx(,,,))
if L > 27/-
7) 211111
else
7) 7):-1
KrJ Regxt (T)
N max 10K,
V
Note that according the above schedule of %i there are E log
Σ
Li episodes, that
iES.-1
we denote by (e(S+11), E [E], Tee and = T)e is constant for all i E (e(S+-1) with the following guarantee
Σ h(x;,a;) 1e 2
Σ h(xi,a;)
(33)
iST 1)
iET.
Therefore summing up the inequality in (32) for E S,-1 get
10K
Σ
Σ
Pia (h(xitas) h(x;,a;) 5
Σ aE|K]
Pi.a Pi,ah(Xi,at)
4E(K]
iES.-1
(Us.a h(xx,a))) ))2
Σ
14%
Σ
Piae
Di.a + h(x,,a))
iES,
KE[K]
(a)
10K
Σ Piaal(Xi,a;)
%
iST.(S,
aE(K)
(Ui. h(xx,,.))
14( max 71) IES,
Σ
Σ
Pia Di.a + ((x,,a))
iES, aE[K]
E
10K
Σ
Σ Pina((Xia;)
Ne
iET.(S, a)
Pia (ii. h(xx,,.)) ))2
14( max 71) 1ES.-1
Σ
Σ
Úi. + hxx,,a))
JES. [E(K]
(c)
E
10K
Regat. (T')
l((x;a;)
EiET.(S.-1) h(xi,a;)
iET 1) Pia (ih. h(x,,a,))
14( max 7))
Σ Σ
1ES,-1
Di.o + h(xi,a))
1.ST-10E(16
28

---

Published as a conference paper at ICLR 2025
where (a) follows by changing the sum in i S.-1 to Σ (IET. and noting that 5- 7/8 2 Ti for all i E Sy-1. Next (b) follows because 7 constant within an episode [E]. Finally (c) follows by our choice of % from (7a-Schedule) and the property in (38).
Therefore we have
(d)
RegkL (T)
E Σ Pi,a (b(xt.a)) l(xxxa)))
10K,
Σ
1((x(,a)
EiETT(S,_ ((xx,a))
iES--1 aE[K]
(ET.(ST-1)
Eies, l(xi,a)))
(Ui,a h 1xxi,a))) 1)2
+ 14 K
Regal (T)
Piaa Vi.a + h(xi,as)
VES aE[K]
10 Σ
KRegxL(T
Σ
h(xi,a;)
(ET,(S--1)
Eies, l((i,ar))
+ 141 K
RegKL (m+-1)
RegEl (T')
E Σ
10 ERegn (T)
Σ
h(x;;a)
e=1 iETx(S--1)
+ 14
K
Σ
h(x1,a,- Regaa (m7-1),
VES.-1
where (d) again follows by choice of 7, and (38), (e) follows by Proposition 5 of Foster & Krishnamurthy (2021) and (S) follows by Cauchy-Schwasd inequality. Finally we arrive at the following bound
Σ KES.
Σ [E[K]
Pi. (h(xi.as) - h(xia;))
s 25
KRegæ (Tg
Σ
h(xi,a;)
Σ h(xi,a;)
(34)
IEST-1
iES--1
and combining with (30) we have the following bound on term 11:
Σ Pia (ira n(xxta))) S 30
K (T)
log log
Σ M(xiaa))
Σ h(xi,;;
VES. KE(K]
iEST-1
iESt-1
Now consider term ITT. Since h(siaa) Dia 1 have that
Úr. Pr.ah((F,a;) = Σ Σ
Pr.a (Ur,a, - 1((x,,;))) $2
WE[K]
aE[K]
Combining all the bounds get for K 2 and Regku (T') 2 1 we have
h(x),b,) S -(m7-1 + 1)
+ 30
KRegka (T) log
Σ
h(xx,a;)
Σ
h(xi,a; +1
(35)
iEST-1
iES.-1
Now, note that m +n- +1 T, and using Assumption 2 we have yn I ((x..))) 2h. Vi e [7]. Therefore
h(x;,,)) ) 2 a (m,-1 + n + 1) m1.
29

---

Published as a conference paper at ICLR 2025
Combining with (35) and noting that ny n4 Ry-1 1 we have
1 (m,-1 + 1) + az)
ur 1 oxy1
+
KRegat log
Σ iEST-1
M(xeaa))
Σ (ESt-1
Mxxaa;)
+1 +1}
Lemma C.2. Suppose Assumption Assumption 1,2, 4 holds. Then the number of times the baseline action played by C- SquareCB is bounded as follows:
KRegkt(T) (T') log
eev KRegg (T)
nr o
(26)
(xi(Ar + aay)
A + aays
Proof.
Note that we have from Lemma C.1 and using the fact that h(-) E [0, we
1
Nt S
(m + 1)(Ar + ozn)
0/
60
K KRegm (T) log
Σ
hxxi,a;)
Σ
h(xi,az) +1
iES--1
iESt-1
<
(m,-1 + 1)(4, az)) 60 KRegkL log (m,-1) 1
03
We define ((m) + m/mlog(m) C2 where
A + azl 2 0,
62
60
K Rega. (T);
m +1
Next observe that for m 2 3, we have -m + m (m) Lemma 8 from Kazerouni et al. (2017) conclude that
C2 S -m + /mmlo m c2. Now we
16c3
20ge
-m C1 + moggomm C2 <
log
9c1
Regxg (T)
evv KRegkt
log
Ai + atl
Ai 0zi
which completes the proof.
Lemma C.3. Suppose Assumptions 1 and 4 hold. Then " chosen as in (ys -chhuueddle),, we have
(h(x),a)) h(xx,a;)) s o o (T) log (L's, L's
(28)
LEST
where D', Exesp l(xx,a;) is the cumulative cost of the optimal policy in the subset ST.
Proof. The proof follows along similar lines as term I[(a) in the proof of Lemma C.I and is provided here for completeness. We use the per round regret guarantee (Theorem 4) from Foster &
30

---

Published as a conference paper at ICLR 2025
Krishnamurthy (2021) follows:
Σ Pi,a (((xs,a)) 1(xx,a;) a
-
5k
Σ aE|K]
(x,ah(xs,aa) + 7%8
Σ
Pia Di,o + 1(3),,))
(ūia 1(xx,,,))) ))
%
aE(K]
(36)
Adding and subtracting h((x,,;)) we get
Σ Pi,a (b(x),a;) h(x(,0:)) -
5K
Σ
Pi.e (x
+
5K
Σ
Pi,a (h((2))))))) h(x(.o)))
aE[A]
Vi
WE[K]
7
DE(K]
(Dia
h(xxi,,,)) ))2
+ 7% Σ
Pi.a
Viaa + h(xi,a))
RE(R]
and therefore
(1
5K
Σ RE[K]
Pia (((x),a)) h(xi,;))
5 Σ
5K
Pi,ah(xi,o + 7% Σ
(Di,a 1(xx,, ))²
Ti
7i
Pi,o
Via + h1 h(xxi,a))
RE[R]
aE[R]
Using %/ 2 10K we have
Σ Piça (((xi,a)) h(xi,;))
10K
Σ
Prall(Xia;) + 147
Σ
Piaa Di.a + h(xi,,a))
(Di,a -(xi,a)))
%
aE[K]
aE[R]
ac(K]
(37)
Using the schedule of % from (7-Schheulee) there are E log
Σ L
episodes, that we
VEST
denote by TT(Sr), e E [E], = and Te is constant for all i E TT((S)) with the following guarantee
Σ
h(x),
ne 2
Σ h(x),;)
(38)
(ST)
(ET.(ST)
Now summing for i E ST as in the proof of Lemma C.1 (cf. equation (34)) obtain
Σ
Σ
Piaa (h(xias)) - h(xi,a))
VEST [E(K]
$ 25,
KRegm (T) log
Σ h(xx,a;)
Σ h(xi,a;
LiEST
iEST
2 KRegu (T) log (L's)) L's,
where Lis = Exes, M(xe,a;) Define the following filtration
F,-1 = o (xs,or āi, 31 a. Xt, siiist E
[K])
Note that E [x(x,,a)) [F(11]= Σ
(x,ah((e,a) and therefore
dE[K]
E
(((Xe..))) - h(x(,;;)
Σ
Σ
Pia (h(xi,a.) h(xiaa))
LEST
SEST dE[K]
which completes the proof.
Lemma 3.5. Let Assumptions 1, 2 and 3 hold. Then, for 5 and
+ log(86 with probability 1 - 6/2, C-SquareCB satisfies the perfor- mance constraint in (2).
31

---

Published as a conference paper at ICLR 2025
Proof. Fort if the condition in line holds then 0₃ 01 and we have that with probability 1 1 6
V1.0; / /m + 1)(1 log(1/6)) - (1 + a))(x.))))))
Noting that 10,00 h(xx,a)) )1 S 2 and therefore with probability -
M(xi,,)) - (1 + (x),(x),))))
Further, if the condition in line 8 doesn't 't hold, then h(x(,,,) S (1 + (>)x(x1)))).
b, and therefore
showing that the performance constraint in Definition 2.2 is satisfied. Now assume that the constraint holds for and now consider E [T]. Note that
Σ
Σ
Pioliaa - h(x(,a))
Σ iES aE[K]
E
PiaDiia- - Σ Σ
Pi.h((xia)
iESt-1 [E[K]
iES RE[K]
Σ iES.-1 aE(K]
Piah((xaa) 1(x(,a))
Consider term I. We handle it as in the proof of Lemma C.1 follows: Using the AM-GM inequality,
48 (Dr.a - 1((x,,;))) + (Úr.a h(xx;,a;) ))²
Σ Σ
Pi,a (iaa - 1(xx,a;)) =
Σ
Ps,a
Ú1.a 1(xi,a))
iES; 1 [E[K]
iES;
[E[K]
for any @ >> 1. Using Lemma 5 in (Foster & Krishnamurthy, 2021) we have
(Di,a -((xi ))
Σ
Pi,aiiaa < 3
Σ (x.al(xiaz)) +
Σ
Pi.a Dia + h(xi,a;)
iE S [E[K]
aE[K]
aE(K]
Therefore have the following bound term II(b):
Σ
Σ
Pi,o ( h(xx,a;) S
1 Σ
Σ
Pi,a((x,,;) 28
Σ
Σ
Pi.a
(0i.a - h(xi,a;) ))²
Úi,a h(x;,a;)
VES, WE|K]
VES, dE[K]
Ve iES, aE|K]
Using Proposition from Foster & Krishnamurthy (2021) we have
(Wi,a - 11 M(x; ))²
28
Σ
Σ
Piáa Di.a + 1 l(xx,,;)) S 4,3Rgga (T)
SES, 1 [E[K]
and therefore,
Σ
Σ Pi,a (Dia; h(xi,;; ))
5 Σ Σ Pi,ah((x,,a)) + 4.9Regku (T)
iESt-1 [E(K)
VES.-10E/E
h(xi,a;)) + 4,
3 VES.11
Eies, h(Xia;;
Choosing 3
RegKL (T) we have
Σ Σ Piaa (Dri: - m(xia;)) 54
Σ
h(xi,a; Regaa (T)
VES. [E[K]
iES
Using the fact that 1(-)) < 1 we have
Σ
Σ Pi.a (i.a h(xx,et) < 4, my Regmuu (T)
32

---

Published as a conference paper at ICLR 2025
Next, consider term II. Consider the following filtration
Fi-1 =
(Xi,ar ae Vi, Xt,ai sist-1,ae
Note that E [h(x4,āe))
(x)) and therefore using Azuma-Hocffding have aE[K]
that with probability 1-8
Σ Σ (x,,(()),,)) h(xx,a)) s 3 log :ESt-1 KE|K]
(39)
Combining (22) and (39) and taking union bound we have with probability -
Σ
Σ
Pi,ali,a h(xx,a.) - 8/ m+-1 (m,-)) + log(2/6)
iES. [E[K]]
Further 10r,a. h(x1,aa) S 2. and therefore with probability
Gr.ā, + Σ Σ
PiaDiaa h(x(,,)) -((e,a)) [E[R]
S 16 m--1 (R) + log(2/6)
VESi VESI-1
(40)
Now line 8 of Algorithm 2 holds at time step i, then we have
ūi.a. + Σ Σ
Piaadiaa +
Σ
h(x1,))) + 16 m Rega (m)-1) + (og((/))
iES, [
iES:
(1+ a)) Σ h(x(,b,)
and therefore invoking (40), we have with probability 1-8
a(x,,a))
+
Σ h(xia,)) +
Σ RES
h(xx,o,) S (1
Σ h(xibb))
iES,
Now note that for all i E S,-1, a, = āg for all Si a, = b, and using S US = 11. and the fact that the condition in line 8 is satisfied we have with probability 1-
h(Xt,aa)
((xi,.)) S 5 (a) kE(t-1]
Mxxx)))
satisfying the performance condition in Definition 2.2.
Next we consider the case when the condition in line 8 does not hold. Invoking the fact that the performance constraint holds until time
1, we have with probability 1 -
Σ h(xx..,) 5 (1+a))
Σ (xx,,,,)
Adding h(x4,6,) both sides of the above equation get
h(x(,b)) Σ h(xx,a)) h(xx,,))))))))))))))))(())) + (1
Σ
h(x,,b.)-
[=1
1=1
Noting that when condition line does not hold at step t, then d, = b, and that a > 0, we have with probability
Σ h(xx,a)))
(1 51
Σ h(x,,,)))
i=1
satisfying the performance constraint in Definition 2.2 for step t. Using mathematical induction conclude that the performance constraint holds for all t E [T], completing the proof.
33

---

Published as a conference paper at ICLR 2025
D PROOF FOR REGRET BOUNDS FOR NEURAL CONSERVATIVE BANDITS
Theorem 5.1 (Regret bound for Neural C-SquareCB). We instantiate Sq-Alg Alg with the predictor Ut,,, = =((5) (8;x,,
X1, ell:5)) from (15) and update the parameters using OGD in (17). Under Assump-
tions 1,2, and with "It as Theorem 5. step-size sequence ( width m, perturbation constant Cp. and projection ball B, with high probubility (1 (o)), the performance constraint in (2) is satisfied by C-SquareCB and the regret given by
Regas (T) S o NOOVKloog KTTlog + (T660(165-1)) +
K (log T + log(160
(gr(Ai agr)
Proof. We set the width of the network m max (O(T*), ((#TT) and the projection set B BBrob (fn). the layer-wise Frobenius ball around the initialization Og with radii p, Pi which is defined as
BErob (6o) = {0 e R": v)c(W())) vee Ill S p, [L]. volla S p1}.
(41)
PiPi
We set p and P1 according to Theorem 3.2 Deb al. (2024a), and the perturbation constant Cp = O(VA), where is the Lipschitz parameter the loss. Now, invoking Theorem 3.2 in Deb et al. (2024a) we get with probability -0(6) over the randomness of initialization and {e) the regret of projected OGD with loss c($) (y., [i(0; X1; E.) )==)) for online regression with squared loss is bounded by Oloo T) i.e.,
T
Eig(Urra Mr.ar)
inf gEH
Σ
(r, S Olog T)
Therefore with probability 1 0()) Assumption is satisfied with Regsa I O(log
Before proceeding further note that Foster & Rakhlin (2020) invokes Assumption-3 (Assumption 2a in Foster Rakhlin (2020)) for all sequences. In the proof of Lemma 2 in Foster & Rakhlin (2020), Appendix B, using this assumption, the authors conclude that SqAlg guarantees that with probability
T inf gEH
Σ Cug Vr,a,)
(x((x(x))))) Br.a)) S Ollo T'
In our analysis this would hold in high probability, i.e., with probability 1 1-0 O()) (this randomness over the initialization and the perturbation the network). Subsequently we invoke Freedman's Inequality (Lemma in Foster & Rakhlin (2020)) that holds with probability (1 5) and take union bound of both the high probability events to conclude that with probability (1 + (()))
T
ΣΣ 1=1 aEA
Pr.a (De(Ie, oz) (2,, a:)) 2Regs (T) + 16 log(0 (-)
Note that the the 1 8 high probability event is with respect the randomness of the arm algorithm. Thereafter the analysis follows as in Foster Rakhlin (2020). Therefore for any sequence of contexts and costs, regret bound holds in high probability over the randomness of initialization and the perturbation of the network and the randomness of the arm choices.
Invoking Theorem 3.1 get with with probability 1 5/2
Regca (T) o (O(VVK KTTllgg + / KT log(168-)) K Klog T log(165-1))
ayi(Ar + az)
Taking a union bound over all the high probability events, we have with probability - (6) over all the randomness in the Algorithm the performance constraint in (2) is satisfied and,
Regce (T) =0(VKT
(VKTT( (Regea (T) + Vlog(160-1)) +
K (Regs, (T) + log(166-1)
ayi(Ar + aay)
34

---

Published as a conference paper at ICLR 2025
Theorem 5.2 (Regret bound for Neural C-FastCB). We instantiate Al-Alg with the predictor 9t.a, = f(8) (0; Xt, xt, e(::)) from (15) and update the parameters using OGD in (17). Under As- sumptions 1,2, 4, 5 and 6 with ti chosen as in (y-Sccheulee), step-size sequence {Te), width m, perturbation constant Cp. and projection ball B, with probability (1 (6)), the performance constraint in (2) is satisfied by C-FastCB and the expected regret is given by
EE Regca (T) S 0 KT* log 1," log T + K log T
K log T
ayr ( + ayj
Proof. As in the previous Theorem, we set the width of the network m max (( and the projection set B = B (fo). the layer-wise Frobenius ball around the initialization 8g with radii P. pI which is defined
BErch P.p. (0o) = {0 R² vec(W(() vec( )l2 S p, [4]. voll2 s p1}.
(42)
We set and according to Theorem 3.3 Deb et al. (2024a), and the perturbation constant
Cp = O(VA), where À is the Lipschitz parameter the loss. Now, invoking Theorem 3.3 in Deb et al. (2024a) we get with probability 1 (6) over the randomness of initialization and { the regret of projected OGD with loss 2(4 (ye. (f,0;xx,,,)] e.)] for online regression with KI. loss bounded by (log T) i.e.,
T
(KL (Dt, vr)
inf gER
Σ
(KL (o(x),))))))))) V), S (llog
Therefore with probability 1 O()), Assumption satisfied with Regsę S O(log
Before proceeding further note that Foster & Krishnamurthy (2021) invokes Assumption-3 (Assumption 2 in Foster & Krishnamurthy (2021)) for all sequences. the proof of Theorem in Foster & Krishnamurthy (2021), J using this assumption, the authors conclude that E[Reg (T) s ( where Reg (T) is the conditional expectation of of the KI. regret with respect to Fi-1 ((xi,,, J, S t 1). In our case Regxı(1) < Ollog 7)) holds with probability 1 1-O and we need to provide an expected bound. Now note that Regxz(T) S T, for all sequences therefore setting (6) = 1/T we get that
E| (T) z (llg(())) +1 +== -0lgg(
Thereafter the analysis follows as in Foster & Krishnamurthy (2021). Now invoking Theorem 4.1
E Rega (T) S 5 (VKKT VKT. log log + log T
K log
ayr(Ar + aqj))
Taking a union bound over all the high probability events, we have with probability 1 ((8) over over the randomness of initialization and {E} the expected regret bounded by
Regcs (T) -
Regeg (T) + log(160-1)) + (Regs, (T) + log(168-1) 1))
ayi(Ar + ozj)
while simultancously with probability O()) over all the randomness in the Algorithm the performance constraint in (2) is satisfied.
E UNKNOWN BASELINE COSTS
In this section relax the the assumption of knowing the true baseline cost values to having noisy observation for the baseline cost ft,b, More formally, consider the following filtration
F (Xi,as ai y1, ), Xt, 1 1 [K]
Then we assume that
E El [r-1] (( AA (T)
35

---

Published as a conference paper at ICLR 2025
We slightly modify our algorithms to retain the same regret bound and performance constraint guarantees. Consider C-SquareCB (Algorithm 1) and replace the safety condition in (4) by the following more stringent condition:
ar + Σ Σ
PiaDia + 16 me-1 [Regsg (m== + log log(4/6)
[ESL-IBE[K]
16
a ammin Σ
yb,b, 5/ (mL- + 1)
m 191
iESt-LUe
16
Yi,b, - b// (m--1++1) (11-1+1)1m +1)
1ES:-1Ur
16
+ a max
yibb
5 nt-1 In
n4
(43)
LES
The next theorem shows that our modified algorithm satisfies the same regret bound in Theorem 5.1 while satisfying the performance constraint.
Theorem E.1 (Regret for C- C-SquareCB with unknown baseline cost). Suppose Assumptions 1,2 and 3 hold. With probability at least
C-SquareCB (Algorithu with the safety condition (4)
replaced by (43) satisfies the performance constraint in (2) and has the following regret bound:
Regce (T) = (VKT**
Regs, (T) + Vlog(86-1)) +
K (Reegsq 1og(88--)) 1))
(44)
a²v
We first start by showing that the modified safety condition (43) ensures that with high probability the performance constraint in (2) is satisfied.
Proof Theorem E.
Lemma E.2. Let Assumptions 1, 2 and 3 hold. Then, for 8 > 0 and % K
+ 1log(88 with probability - 5/2, c SquareCB satisfies the per- formance constraint (2).
Proof of Lemma E.2. We start with our safety condition in (4) for the known baseline case and show that it satisfied with high probability whenever the new safety condition in (43) is satisfied, i.e., the new condition is strictly more conservative than the previous one. Recall that from (4) we have
Úr,āe Σ ΣΣPE Pi.aiita + Σ h(x(,6,) + 16 m
Regsq log (4(()
[GE]KK
(ES,
(A)
(B)
(C)
5 a
,(x;,,))
i=1l
Now moving term (B) to the other side we have that the above condition is equivalent
Ur. Σ Σ Pr.ehr.a + 16 m
Regoy((m- log(4/6)
VESt-I0E[K]
< <
M(x(b,)) Σ M(xi,b))
SES,11
= =1+aa Σ
h(xx,b)) +a Σ
h(x(b))
iESt-1Ut
iESE
36

---

Published as a conference paper at ICLR 2025
where have used the fact that [t] St-1 U U Ut. We can further write the above condition as:
ar + Σ Σ
Piaaiia 16 m4-1
Regss(me-1) + log(4/6) -
Σ h(x1,6,)
IES: [ESKKK
RESI-1U0
Σ 1ESt-1Ut
((xx,b)) + Σ
h(x(,,,))
(45)
iEST
Now note that [F--1,,,FF.1] Mxx,,,), 1I E [T]. Therefore X, yt.b, -(xx,,,)) is martingale difference sequence and since X2 E [-1,2] we use Azuma-Hocfiding to ensure that for any and all I' >
Mr. M(xxsba)) s 2xxp
-62
P
18T
Therefore with probability 1 8/8
Σ
1i. h(xe,,)) 1(xA,,))s (m--1 + 1)
16
8
and, with probability 1 55/8
16 1(xx,,))) // ne-1 In
8
iESE_1
Further Σ ((Xt,b,) 2 13:13hh and Σ h(xe,b.)) 2
(ma-1 1)y; therefore with
SESE
1ES
probability - --8/8 we have the following lower bound for the rhs of (45):
Σ k(xi,,)) +a Σ
h(x(,)))
Σ
Ytdde - 5// (m²-1 + 1) Im
16
iES--1
BESE
RES.-IUr
(
166
+ max
Σ
Vi.b
5 14-1 In
72-1881
JESE
Next, with probability 1 - 6/8 we have the following upper bound on the lhs of (45)
at + Σ Σ
Pioaita + 16 m (m: + lloglo//)))
Σ
1(xi))))
IES, [0E[K]
iES?
S0 Σ
Σ
Pi.adia + 16 m Regsq(()-1) log loggl//////) (4/))
1ES,_10E[K]
16 +1
min Σ
Vi.h
5// (m--1+1)
1) m 13/1
(ES
37

---

Published as a conference paper at ICLR 2025
Therefore if the following condition holds
01, + E
Σ
Piobiaa + 16/ m=-1 (mg + log(4/6) (4/6)
yi,b, - (m/ 1) In (
16
min Σ
mm 19
iE
16
Yi,b, /v (m ( 11)mn
8
iES; 1ut
16
max
Σ 1ES
Dt.de 51 n4-1 In
8
-mc-1311
then with probability 1- 6/4
Gr,a, + ΣΣ Piabiaa + Σ
h(x1,0,) + 16 m4-1
Regss(me-1) log
log (40))
iES;
(1 (1+a) h(x(,)))
Now we invoke Lemma with ō substituted by 8/4 and take a union bound with the above high probability even to conclude that with probability 1 - 8/2 C- SqqareCB (Algorithm 1) with the safety condition (43) satisfies the performance constraint in (2).
Next show that the regret of the modified C-SquareCB algorithm satisfies the same regret bound. Note that the regret decomposition in (6) and the bound on term / in (10) still hold. Therefore objective to complete the proof of the Theorem is to bound ny in Step-2 of the proof of Theorem 5. The following Lemma bounds ny, the number of times the baseline action is played with the modified safety condition in (43).
Lemma E.3. Suppose Assumption 1,2 and hold. Then, with probability - 8/4 the number of times the baseline action is played by C-SquareCB with the safety condition (43) is bounded as follows:
K (Regss (T) log(86 - -1)
00
(46)
orj) ( + oz))
Proof. Let 7 be the last round which the algorithm plays the conservative action, i.e.,
max <t T b.).
38

---

Published as a conference paper at ICLR 2025
Recall that my =
|Se] and ny |. By the definition of т, we have that at round
0t, +
Σ
Σ
PioBia + 161 m
log (4/6)
[ESt-10E|K]
16
- a min
Σ Yi.h - / (m--1 + 1) In
my 1311
iES
16 8
Yb,be - sv (m,-1++ 1)11
iES; 1ut
16 Yidbe - 5 he- In
Σ
+ a max
The 13/t
FEST
Re-arranging we can write the above condition as follows:
Σ Σ PiaBiaa / (mmmm-1+1)))))) 1)
16
a71--191 S Ótäār
VEEK-K
(17 + log(4/6) a(m + 1)m + 16 My-1
Hereafter following the analysis in the proof of Lemma 3.2 we show that with probability 1 - 6/2
an, -m + 1)ay 64v K (mm,- - Regsa (T) + v /log(166-1)
-- 1)ay 64v (m,-1 + 1) [Regaq (T) v /log(165-1)
Now using the analysis in the proof of Lemma 3.3 with m c otf C2
64 K (Regsq(T) (T) /log((16-1)) with probability 1 - 5/4 we can bound bound as follows:
K (Regs, (T') 1og(20-
nT 0O
a²yp
To complete the proof of Theorem E.1 we combine Lemma E.2 and Lemma E.3 with Lemma 3.4.
Next consider C-FastCB (Algorithm 2) and replace the safety condition by the following more stringent condition:
Σ
Σ
PiaDiaa 16ym, 1iVmu--eegu((
16 m, 13/1
-amin
Yi,b, 5/ (m/mm---- + 1)
(5)
iES
16
Yt.b, - 5// (m--1 + 1)
iES
( 16
+ a max
Σ
Vi.b 5, n In
ne 13/1
(47)
SEST
Then have the following regret bound for C-FastCB.
39

---

Published as a conference paper at ICLR 2025
Theorem E.4 (Regret Bound for C-FastCB for unknown baseline). Let Assumpttins 1, 2 and hold. With probability 1- 8, C-FastCB (Algorithm 2) with n/s chosen in (% -i-Schedulle,, and with the modified safety condition in (47) satisfies the performance constraint in (2) and has the following bound on the expected regre! (expectation is for the action distributions):
E Regga (T)) = =0
(OVVII VKIrlog(LT)) ReguL (T)
K Keegu (T)
(EV (VKReBm((T))
log
(48)
y²yf
Q²
Proof. The proof follows along the same lines as proof of Theorem E.1. By upper bounding and lower bounding the safety condition probability the safety condition in Algorithm 2 is satisfied.
show that when (47) is satisfied then with high
Further the additional terms in (47) be handled exactly in proof of Lemma E.3 and combining with the proof of Lemma C.2 we complete the proof.
F ADDITIONAL EXPERIMENTAL DETAILS
F.1 EXPLORATION PARAMETER %/2
Since the optimal loss L is not known in advance, the exploration parameter % is treated hyper-parameter in our experiments. A heuristic choice to substitute Et= L3 by the sum of the observed losses until time - 1, i.e., Σ T. to choose "Y-- Note that at time 1, >>=1 L, is known to the user. The other choice is treat "/2 as single parameter y and tune it for different values. In our experiments we tune y in {10, 20, 50, 100, 200, 500, 1000]. We plot the corresponding cumulative regret for all these choices in Figure and we note that the heuristic choice of Σ Lı produces good results in the majority of environments.
40

---

Published as a conference paper at ICLR 2025
covertype
mushroom
3.5
1-
20
3.0
y= 00
2.0
==
2.5
200
Regret
600
Regret
2.0
y=
y1
1.5
== K
1.0
V1 100
200
1.0
0.5
y: 500
VI
0.5
VI
0.0
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Rounds
Rounds
fashion
1.6
Y
2.5
50
1.2
W 100
2.0
y=
Regret
20
Regret
550
1.5
V: 50
0.8
W
y=
1.0
200
Vi - 500
0.4
0.5
==
0.0
0.0
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Rounds
Rounds
Plants
shuttle
162
Y =110
2.0
50
h =100
1.5
200
Regret
= 10
Regret
500
== 50
1.5
W 1000
1.0
==
Σ 4
y-
1.0
- 500
0.5
== 1000
0.5
C-2
0.0
0.0
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Rounds
Rounds
Figure 3: Comparison cumulative regret of C-FastCB with various choices of the exploration parameter "/ openml datasets (averaged over 5 runs).
F.2 DEPENDENCE ON THE NETWORK WIDTH
For Theorem 5.1 and 5.2 we use one specific instance an online regression oracle, namely Online Gradient Descent with overparameterized neural networks. Note that the width requirements in the theorem statements are sufficient conditions, but not necessary. Therefore to address concerns about practicality of the algorithms, algorithms for different choices of the width of the network. Figure and Figure 5 shows that for practical purposes, fixed width networks suffice for both Algorithm and 2.
provide additional evidence here that shows the performance of the
41

---

Published as a conference paper at ICLR 2025
coverlype
Magic leloopocpp
1,2
1.0
-0
60 20
50
0.8
50
0.8
100
Ragrett
0.6
0.6
1000
m0 1000
0.4
m0 1000
0.2
0.0
1000
2000
3000
4000
5030
1000
2000
3000
4000
5000
1000
2000
3300
4000
5000
Rounds
Rounds
Rounds
mushroom
Plants
shutlic
2.0
20
1.5
m= 50
m0 50
m= 100
200
Regiel
Regmtt
1.5
mm
200
100
m
500
1000
0.5
0.0
0.0
Figure Comparison of cumulative regret of C- C--qqareeB with various choices of the network width m on openml datasets (averaged over 5 runs).
covertype
fashion
MegicTelescope
1,2
10
1.75
m-
1.0
1.50
0.8
m-
100
1-100
60
2.0
0.6
500
200
1.00
Regret
1.5
m=
1030
m=
0.4
100
0.2
0.25
0.0
0.00
0.0
= 1000
4000
Rounds
Rounds
Rounds
mushroom
Piants
shuttle
2.0
m
10
2.0
60 20
50
1.5
10
Regnet
1:000
m0
100
in 50
1000
m 100
m- 100
200
0.5
1000
1000
2000
3000
4000
5000
1000
2000
3000
4200
0000
0
1000
2000
3300
4000
5000
Rounds
Rounds
Rounds
Figure 5: Comparison of cumulative regret of C- C-FastCB with various choices of the network width m on openml datasets (averaged over 5 runs).
42


Reviews:
[{"review_id": "e2S2dk6IxJ", "reviewer": "Reviewer_2J6i", "summary": "This authors consider Conservative Contextual Bandits with general value function class and develop two algorithms C-SquareCB and C-FastCB, using Inverse Gap Weighting and online regression oracles. They show that the safety constraint is satisfied with high probability (the performance is not worse than a baseline policy by more than $(1+\\alpha)$ factor). They also show the regret for C-SquareCB is $\\tilde O(\\sqrt{KT}+K/\\alpha)$ and the regret for C-FastCB is $\\tilde O(\\sqrt{KL^*}+K/\\alpha)$, where $L^*$ is the cumulative loss of the optimal\npolicy. The efficacy of the proposed algorithms is validated on real-world data.", "questions": "Some clarification questions apart from the concern in Weaknesses:\n\n- Data-dependent bound\n  - When $L^*=O(1)$, it seems the regret bound becomes $\\tilde O(\\ln T)$. Is there any instance-dependent metric (similar to the mean gap in the stochastic MAB setting) hiding in the constant term?\n  - $\\gamma_t$ seems to be requiring the knowledge of not only $L^*$ but also each component that sums up to $L^*$. Would that be too strong?\n\n- Experiments\n  - Can you provide more details on how you set $\\delta$ and tune hyperparameters? How do you run C-FastCB if the optimal cost is not known?\n\n- Typos:\n  - Algorithm 2 Line 8: Is there a term related with $\\sqrt{\\log\\delta^{-1}}$ missing?\n  - Line 836 missing a sqrt term consisting of $m_{\\tau-1}$ and $\\texttt{Reg}$.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written and mostly easy to follow, with proof roadmap and intuition moderately provided.\n- The provided solution nicely connects safe conservative bandits and contextual bandits with general functions class.\n- Analysis is sound and rigorous. Numerical experiment is convincing.", "weaknesses": "As a paper that combines two established sub-fields in bandits, it is a bit unclear the novelty in algorithmic design and theoretical analysis. I would like to see authors provide and emphasize more detailed discussions if possible. In particular, what is your technical/methodological contribution compared to Kazerouni et al. (2017), Foster & Rakhlin (2020), Foster & Krishnamurthy (2021)? What are the challenges of adapting/extending their tools? From what I understand, the novelty appears in: a delicate safety criterion and a time-varying exploration schedule. The authors can add more if necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OZ7OEJacdu", "reviewer": "Reviewer_BHSm", "summary": "The paper studies the conservative contextual bandit problem, where the goal is to minimize the regret as in classical contextual bandit problems and, with high probability, be competitive against a baseline policy. Importantly, the cost functions are not assumed to be linear in the contexts. This extends previous study of conservative bandit problems beyond the multi-armed setting and the contextual linear setting. \n\nThe two proposed algorithms, C-SquareCB and C-FastCB, combine the inverse gap weighting based exploration and online regression oracles (e.g. function approximation using neural network+ gradient descent), and achieve regret which is sublinear in the horizon T or sublinear in the optimal loss L*, while being (1+alpha)-competitive against the baseline with high probability. Experiments using real world data show that C-SquareCB and C-FastCB have smaller regret compared to algorithms for contextual linear bandit problems, and are more competitive against the baselines.", "questions": "In Definition 2.2, line 124, alpha is chosen to be <1. I’m wondering if this is just a simplifying assumption, or there is difficulty in extending the results of this paper to settings where alpha>=1? \n\nIn line 160, what is H in the ``inf’’?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well written, with clearly presented problem formulations, algorithms and results. The setup considered fills in the gap of current conservative bandit literature, and the proposed algorithms have provably sublinear (in T or L*) regret while being (1+alpha) competitive against the baseline. Experiments further demonstrate their superior performance as compared to algorithms designed for conservative linear contextual bandits and for classical settings without baselines.", "weaknesses": "The proofs/assumptions may lack rigor. In particular, the proofs cite results in other works without carefully checking the assumptions under which those results hold. For instance, in line 914-915, lemma 2 in Foster & Rakhlin (2020) is invoked. If my understanding is correct, that lemma requires Assumption 3 to hold for all possible sequences. Nevertheless, in line 1736-1737, Assumption 3 is only proved to hold with high probability. \n\nOne contribution of the work is to use neural network for function approximation to deal with the non-linearity in the cost functions. However, to achieve the stated performance as in Theorem 5.2, the width (and thus the number of parameters) of the neural network is Omega(poly(T)), which might be too large for long-horizon problems, making the algorithms less practical. \n\nThe paper could benefit from more detailed discussion on the significance of the regret bounds in Theorem 3.1 and Theorem 4.1. In particular, it appears that for any algorithm which has regret upper bounded by alpha * y_l * t, under Assumption 2, equation (2) is automatically satisfied. Some discussions on the range of parameters might help the readers better understand the significance of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PoJ5KEmWI0", "reviewer": "Reviewer_wAuW", "summary": "This paper proposes algorithms for the conservative contextual bandit problem under a non-linear reward model.  The proposed algorithms apply IGW exploration based on an online regression oracle, enabling the selection of either an exploratory or a conservative policy based on a safety condition.  The proposed algorithms achieve sub-linear regret with respect to the total time step $T$, and its performance is supported by numerical experiments.", "questions": "1. In Algorithm 1, if the safety condition is not met, the baseline policy ($b_t$) is used, and its noiseless cost $h(x_{t,b_t})$ is observed. However, this data is not used in the oracle. Since the baseline policy provides high-quality data with zero noise, why is it not utilized? Would using this data yield a better estimator? Additionally, in the linear cost case (Kazerouni et al., 2017), a noisy reward is observed for actions chosen by the baseline policy (e.g., $y_{t,b_t}$). What would happen if, in this paper’s setting, the algorithm observed $y_{t,b_t}$ instead of $h(x_{t,b_t})$?\n\n2. The algorithm introduced in Section 4 is referred to as having a “first-order regret bound.” Why is it called “first-order”? How would second-order and third-order bounds be defined?\n\n3. When defining the Neural Tangent Kernel (NTK) matrix, is $x_t$ the feature chosen by the algorithm at time $t$? If so, it seems unclear how the NTK can be defined given that the chosen features are unknown prior to starting the algorithm. It may be better to define the NTK matrix based on the context of all actions at all times, as in Zhou et al. (2020). Additionally, the regret bounds in Theorems 5.1 and 5.2 are independent on $\\lambda_0$. Why is this assumption necessary, and does it not affect the regret bound?\n\n4. Most literature on Neural Tangent Kernel-based neural bandits shows a dependency of regret on the effective dimension of the NTK. In contrast, the proposed paper presents a dependency on $K$ instead of the effective dimension. Could you explain what enables this distinction?\n\n5. In the Neural Conservative Bandit, the activation function in the first-order bound changed from a smooth & Lipschitz function $\\phi$ to a sigmoid function $\\sigma$. What are the differences between $\\phi$ and $\\sigma$?\n\n6. There do not appear to be terms related to the perturbation constant or the number of ensemble $S$ in the regret bound. Do these quantities not affect the regret? Additionally, how are these hyperparameters chosen in the experiments, and how do they impact performance?\n\n---\n\n**[Typo]**\n\n- line 295: “Line 7” should be “Line 8.”", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed algorithm introduces the first conservative contextual bandit algorithm for a general reward model by adapting the assumption of access to a regression oracle and leveraging the IGW algorithm, which previously applied only to linear reward models. The authors also present regret analysis for the algorithm. Although I was unable to rigorously verify all proofs, the results appear consistent, achieving a regret bound comparable to that of the linear case.  \n- The methodology is illustrated with examples using an online gradient descent regression oracle and feed-forward neural networks. Real-world data experiments further support the algorithm’s performance.", "weaknesses": "1. This paper introduces multiple algorithms and theoretical results for the conservative contextual bandit problem with a general non-linear cost function. Consequently, much of the main content is focused on the operation of the algorithms, assumptions required for the theoretical results, and descriptions of the outcomes, with limited discussion of the technical challenges arising from handling non-linear cost functions in CCB and how these challenges were addressed. It seems that Algorithm 1 and Algorithm 2 are almost identical aside from the use of different regression oracles. Moreover, if, as the authors state, Algorithm 2 has a tighter regret guarantee than Algorithm 1, it may be beneficial to focus more on Algorithm 2, detailing the challenges and technical novelties associated with it.\n\n2. The main theorem statements lack completeness. For example, in the statement of Theorem 3.1, there is no indication of how to set the input parameter $\\gamma$ for the algorithm to achieve the stated regret bound. Similarly, Theorem 5.1 could benefit from more precise language rather than vague expressions like “appropriate choice of parameter”. Additionally, based on my understanding, the exploration parameter $\\gamma_i$ in Algorithm 2 appears to depend on $\\eta_i$ (line 1218). However, $\\eta_i$ in turn depends on $L_i^*$, which is the true cost value of the optimal action and unknown to the agent. Further clarification is needed on how $\\gamma_i$ is determined.\n\n3. The description for experiment reproducibility is lacking. Additional information, such as how the hyperparameters for each algorithm are set, would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)