Regularized-OFU: an efficient algorithm for general contextual bandit with optimization oracles
Authors: Yichi Zhou
Shihong Song
Huishuai Zhang
Jun Zhu
Wei Chen
Tie-Yan Liu
Venue: ICLR 2022 Submitted (2022)

Abstract: In contextual bandit, one major challenge is to develop theoretically solid and empirically efficient  algorithms for general function classes. We present a novel algorithm called \emph{regularized optimism in face of uncertainty (ROFU)} for general contextual bandit problems. It exploits an optimization oracle to calculate the well-founded upper confidence bound (UCB).  Theoretically, for general function classes under very mild assumptions, it achieves a near-optimal regret bound $\Tilde{O}(\sqrt{T})$. Practically, one great advantage of ROFU is that the optimization oracle can be efficiently implemented with low computational cost. Thus, we can easily extend ROFU for  contextual bandits with deep neural networks as the function class, which outperforms strong baselines including the UCB and Thompson sampling variants. 

Under review as a conference paper at ICLR 2022
REGULARIZED-OFU: AN EFFICIENT ALGORITHM FOR GENERAL CONTEXTUAL BANDIT WITH OPTIMIZATION ORACLES
Anonymous authors Paper under double-blind review
ABSTRACT
In contextual bandit, one major challenge is develop theoretically solid and empirically efficient algorithms for general function classes. We present a novel algorithm called regularized optimism in face of uncertainty (ROFU) for general contextual bandit problems. It exploits an optimization oracle to calculate the well- founded upper confidence bound (UCB). Theoretically, for general function classes under very mild assumptions, it achieves a near-optimal regret bound Ö(VT). Practically, one great advantage of ROFU is that the optimization oracle can be efficiently implemented with low computational cost. Thus, we can casily extend ROFU for contextual bandits with deep neural networks the function class, which outperforms strong baselines including the UCB and Thompson sampling variants.
INTRODUCTION
Contextual bandit is basic sequential creision-making problem which is extensively studied and widely applied machine learning. At each time step in contextual bandit, agent should choose an action according to presented context, and will receive reward conditioned on the context and the selected action. The goal of the agent is to maximize its cumulative reward, which is equivalent to minimizing regret.
Algorithms for contextual bandit can be divided into two categories: agnostic algorithms and realizability-basee algorithms.. The agnostic algorithms, e.g., EXP4 (Auer et al., 2002b; McMahan & Streeter, 2009; Beygelzimer et al., 2011), provide worst-case optimal regret bounds for any function class and data. However, the time complexity of EXP4 is linear to the cardinality of the function class which is intractable for large function classes.
The realizability assumes that the reward is generated from underlying model, whose form is known but with some parameters to be determined. When the realizability is satisfied in real-world problem, the realizability- based algorithms usually perform much better than the agnostic algorithms. The most popular realizability-baat based algorithms are UCB (Auer et al., 2002a) which selects action according an upper confidence bound, and Thompson sampling (Thompson, 1933) which makes decisions according to samples from the posterior distribution. Both UCB and Thompson sampling achieve near-optimal regret bound for many function classes. However, the construction upper confidence bound and sampling from the posterior distribution are extremely computationally expensive for general function classes.
To overcome the computational barrier, there are line of works (Agarwal et al., 2014; Dudik et al., 2011; Foster & Rakhlin, 2020; Foster et al.. 2018) that reduce the decision decision-making problem to an optimization problem, and then exploit optimization oracles to accelerate computation. Nonetheless, the optimization oracle may not be feasible or efficient for general function classes. In face of the challenges above, when dealing with modern function classes, such deep neural networks, these theoretically solid algorithms either become computationally intractable or do not achieve low regret in practice.
Our paper also falls into this line of research. We propose a novel algorithm, called Regularized OFU (ROFU) which is developed upon the realizability assumption and optimization oracle. In ROFU,

---

Under review as a conference paper at ICLR 2022
measure the uncertainty of the reward function by regularizer, and then calculate the optimistic estimation by maximizing the reward function with the regularizer penalizing its uncertainty. To the end, give novel formulation of upper confidence bound for general function classes. Our algorithm achieves near-optimal regret bound under very mild assumptions, and can be efficiently solved by standard optimization oracles, such as gradient descent. Thus, our algorithm can be easily extended to deep neural networks in computationally efficient manner.
We summarize our contributions follows:
We propose a new UCB variant ROFU, which is designed for general function classes with provably near-optimal regret. ROFU computes UCB with optimization oracle which can be efficiently implemented for complex function classes including deep neural networks. Theoretically, for general function classes under very mild assumptions, we prove that ROFU
achieves a regret of O (V/Tlogg | which matches the lower bound up to a logarithm factor, where is the parameter space. As special case, we present regret bound for linear function class which the same to that in Sobbasi-Yadkori al., 2011).
Empirically, we evaluate ROFU on complex contextual bandits with deep neural network as the function class. We show that ROFU also provides efficient UCB estimation for popular DNN architectures including MLP and ResNet. Moreover, our algorithm enjoys smaller regret than strong baselines on real-world non-linear contextual bandit problems introduced by Riquelme al. (2018).
2 PRELIMINARY
We consider the contextual bandit problem (Bubeck & Cesa-Biancis 2012) with K actions.
Definition (Contextual bandit). Contextual bandit is sequential decision decision-muking problem where the agent has a set of actions At each time step t, the agent first observes a context In. then selects action a₂ E A based on the context. After taking the action, the agent receives reward
Realizability- algorithms are developed under the following assumption. Assumption (Realizability assumption). Er, == fo- (It, az) where fo- (Ie, 0e) is a function with unknown groundtruth parameters 0* @.
The agent aims to maximize its expected cumulative reward EiST for (Ii, ai) which is equiva- lent to minimizing the regret Ri = EtsT max,(Je (fo- (I,, a) - fo- (2t, at) under the realizability assumption. For convenience, let a; = arg max, fe- (IL, a).
METHOD
Algorithm Regularized Optimism in Face Uncertainty
1: Input: A reward function fe- with unknown 0", number of rounds T.
2: Du Q.
3: fort= 1, do
4: Observe Z+--
5: Va É A, compute
U(xe, a) Lin-U(xe, a)
Option for general function classes
OFU" (zt,a) a) =
Option II, improved version for linear functions (1)
6:
Take a; arg max A OFU (x,, a) and receive reward r. with Er, for (xt, at).
7: Let D. = D. U (TT, ar, r.)).
8: end for
In this section, we first formally present the optimization oracle and the algorithm. Then we discuss the intuition behind our method. Alter that we provide the theoretical justification of the algorithm,
2

---

Under review as a conference paper at ICLR 2022
showing it's near-optimal in terms of regret under very mild assumptions. Finally, give empirically efficient implementation of the algorithm relying on gradient descent. Proofs of our theoretical results can be found in Section 3.3 and Appendix.
Our algorithm is developed upon the following oracle.
Definition (Optimization oracle). Given dataset D == {(t,, av,, Te)) before round t, for 2t, we assume there an optimization oracle compute
U a) max [0( a) - 71,a (MSE((0 D) + =
(2)
where MSE(O; D) = Doi D(earre r)² and Mt., a > O are constants to be specified later. For convenience, let dr, = arg max fo( "t,, D) + a=|10112).
The availability of such optimization oracle is very mild assumption in practice. For example, we can exploit gradient-bant bassed algorithm to approximately solve Eq. (2) for differentiable functions.
As summarized in Alg. 1, our algorithm is as follows: in round 4, the agent invokes the optimization oracle to compute OFU (3²,, a) for each action. Then, the agent selects a, arg max, OFU (r+, a).
We now provide more insights into Alg. and the optimization oracle in Eq. (2). The key minimize regret is to trade-off exploration and exploitation (EE). In order to maximize cumulative reward, the agent exploits collected data to take the action with high estimated reward while it also explores the undiscovered areas to learn knowledge. Our method follows the Optimism in Face of Uncertainty (OFU) principle, which is widely verified to be effective in EE tradc-off. When facing uncertainty, OFU first optimistically guesses how good each action could be and then takes the action with highest guess.
Eq. (2) gives such optimistic guess by maximizing fo a) under the regularization of mean squared error. The intuition behind Eq. (2) is that: from the view of exploitation, if θr,e is parameter with small mean squared error, and fo., (Zz, a) is large. Then we can expect fe- (I2, a) is also large
as Or.a is close to 6* in general; from the view of exploration, if Ór,a increases the value of fa.. (#t, a) without significantly increasing MSE(0,, D), then the uncertainty the reward of (æe, a) would be large.
3.1 REGRET ANALYSIS
Besides the conciseness and clear intuitions, the algorithm also enjoys several theoretical advantages:
Theorem develops a O( O log [ regret under Assumption 2. The regret bound in Theorem matches the lower bound as presented in Theorem up to a logarithm factor, showing the algorithm is near-optimal.
Assumption 2. There exists constants C1, C2 > 0 and a function g : + R U (0), such that
Vx, a, 0, [fo a) - fo- (a, a)l E [cig(0), c2g(
Assumption 2 is very mild that includes many function classes. For example, if Vx, a, function hz (8) (2, a) fo- (Ir, a)l e -troonyy convex and ca-smooth, then Assumption is true.
Theorem (Regret for general functions with Option T). Under Assumption 2, if' a,,a,, fo (z, a) [1,, let Tt. = 801 with Option satisfies
and = O, then with probability at least 1 - 6, the regret of Alg. 1 [-1 T log
C2 T log
T
RT
C1
Theorem (Lower bound). For any 02 2 C1 > O, there is a function class {fo Looe that satisfies Assumption 1 and with some 9()). One can construct context sequence {ItheS such that the expected regret of all bandit algorithms is lower bounded by 21 (ooTTlog/e (0)).
3

---

Under review as a conference paper at ICLR 2022
It is obvious that when 02/c1 is large, the regret bound in Theorem is meaningless. However, fortunately, for linear functions, which the most interesting function class with 02/01 co, Alg. 1 achieves near optimal regret bound in Theorem 3 and 4, indicating boarder theoretical potentials to develop regret bound of Alg. for function classes beyond that in Assumption 2.
Theorem 3 (Regret for linear functions with Option T). If the function class is linear, i.e., fo(2, a) 0 (T, a), and @ {110] < vd). [|0(x, a)ll Vd. Then, applying Alg. with Option to discretized parameter space O which is an e-mesh. Let 1/T, a =
and 1ht = 33BBer,at ' where An = + Ever Qu òt =((z,,) a). O, = ii
m12 Br max 128d In é (n(tt/6)), ln(+² is the confidence width in (Dani et al., 2008), we have
with probability at least 1 26, the regret of Alg. with Option I satisfies
T
Ry S 8TT3TI Vd 32 dTT log Ö(dVT).
The e-mesh in Theorem 3 introduces addition regrel than standard LinUCB. More importantly, the calculation of T)t expensive. We can improve the performance on linear functions with Option which invokes the optimization oracle two times for each action per round.
We postpone the proof of Theorem 3 to Appendix. Theorem 4 (Regret for linear functions with Option I1). Let arg ming MSE D.) + /100)//\ and 0r, - arg maxg fI a) Thoa (MSE(O, D.) 110113). Let
Lin-U(xa, a) fa.. 1. (Ie, a) + v ( (Zt,
So. (It,
(4)
We have Lin-U(xt, a) is equivalent to upper confidence bound in LinUCB Abbasi-Yadkori Yadkori et al. (2011). Thus, setting 1/(2),a) to be the confidence width in (Abbasi-Yadken et al., 2011), we have with probability at least 1 - 6, the regret of Alg. I with Option 11 is
Ry Ö(dVT).
Proof. LinUCB (Abbasi-Yadkorii et al., 201 uses the following upper confidence bound for Φ(I;, a).
LinUCB(a,, a) = 10, + v Bidr,aA Pi... where A = I I+Eee & òi,a = o(I,, a), o: = o(Ie, az) and Be confidence width.
(5)
Then the proof is straightforward after observing that 0 A, Evsc DUTY and Ôe.a O2- + A, (r.aaa(// (2n,a) and, thus, (0r,a - 1)-1) Di.a 201
I Di Ar &r.a.
3.2 AN EMPIRICALLY EFFICIENT GRADIENT DESCENT- BASED OPTIMIZATION ORACLE
In order to apply Alg. 1, we have to efficiently solve or approximate Eq. (2). In this section, we consider the case that Eq. (2) is differentiable. Thus, naturally, one can use gradient descent methods to approximately solve Eq. (2). However, it is still not manageable to optimize from scratch for every (xt,a) We propose to optimize from 8 for (It,a).
More specifically, we approximately solve Eq. (2) by executing few steps of gradient ascent starting from 4-- That is, 0 0, + <Vo a) (0; D))le=d, with 0 == 0,-1. where is the step size. The above implementation summarized in Alg. 2.
Alg. 2 essentially performs a local search around 8--1- Indeed Alg. 2 brings extra benefit for the optimization by starting from 0,_1 in this case. This is because intuitively 0,-1 often gets closer to ((, a) when is larger. For example, in linear contextual bandits, ir, 0 2mr. A, Dt.as and
2nr A &e monotonically decreases becomes larger according to the definition of nt...
is easy to see that the time complexity of Alg. is (Mp) where p is the number of parameters. In Sec. 5, we can see that the regret of ROFU is low in practice with very small M.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 2 An efficient implementation estimate (11,, a)
1: Input: Dataset Di-1, ft-1 arg min, MSE(#; Dr-1) + || and context-action pair
Zt; a. Learning rate A and training steps M, hyperparameters vy and a.
2: Set (0 a) := 0
3: for 1,.,, .M do
4: (12, == 0, ( =Vo(fo(2), (MMSE(); + (= -- (())))))) where V
is an estimator of gradient.
5: end for
6: return 8as(6 (Iz, a).
3.3 PROOF OF THEOREM
Let start with some useful notations. For convenience, we abbreviate Tht T/t since Thta Na,'' Va, a' in Theorem Let 6,,0 arg max fo(2s, a) MME 0; D) denote the parameter used in Uxx, a), (,) = (Jo(I ae) rı)² (So- (Fe, a.) - rz)² and (o - (Jo(z,, dr) fo- (ze, a.)) 2. is casy that (0) (o) where the expectation is the randomness of the reward.
Lemma 2 presents consentration inequality of Σ Ai(0) which is derived from Lemma 1. Lemma (Freedman-type inequality, Theorem in (Beygelzimer et al., 201 1)). For any martingale Z, with Zel S R, with probability at least 5, for a (0, 1/R).
T Σ
Eale - 2)B|Z + Rlog 1/8
(6)
1ST
Lemma (Bounded differences).
With probability least 1 - 8, v0 0,
|
2 A.) + 16
X
2'5t
Proof. This lemma is essentially a restatement Lemma 4 in (Foster et al., 2018). Applying Lem martingale (f) (.(O)).T:: we have with probability at least 5/(
log (
(A) (0) s ale 2) Σ S
((EA(()) A.()))
a
1ST
S 4a(e 2) Σ (0) + log(()17/8)
t
The second inequality is because EEA, (0) A, ()) < 4EA, Setting a = 1/8 and rearrang- ing, with fact (0) and applying union bound, have with probability least 1 1-4 6
A T,0E0, Σ A.( + 16log
Σ A
Let at = arg max, for (Ie, a), according to the definition of ô. and the definition of ag we have
Sor (1 a.) 1):MSE(0*) Sō..; (1) MSE
fo (B),03) 7)M)E((r.a)) S Sō.., (xe, ac) T).SE((
5

---

Under review as a conference paper at ICLR 2022
Summing up the above two inequalities leads to
fo- (It ai) S fôn., (It, ar) T/ (MSE((0 D:) MSE(O"; D.)).
(8)
Now present the proof of Theorem 1.
Proof of Theorem 1. Assuming the events in Lemma 2 happen, we have
RT= =
Σ
So- (ai,, So- (2i,, at)
ET
Sir.c (Nie; (t)) (MSS((fraa; D₂) MSE(0"; D.)) - (xe,
O
Sin.c (ste ae)
-te((t - Σ
de (0 + 1// 1) log
p<a
167
10|
log
+ c29(0) m1:)9((03
t 1
16T
|
c
log
t
c
of
Σ
41
log
(t - 1) 1)
SSP
T
8
Tlog
8
The first line is the definition of regret; the second line is according to Eq. (8); the third line is by
cf(t-1)
Lemma 2; the fourth line is by Assumption 2; the second last line is by setting Th $ VV o log l
4 RELATED WORK
Optimism in face of uncertainty (OFU): Our algorithm is essentially a variant of OFU principle, which is a powerful framework to trade-off exploration and exploitation for bandit problems. As discussed in Section 3, OFU algorithms take actions according to an optimistic estimation over the reward. Most OFU algorithms optimistically estimates the reward by the best possible value over confidence set of the reward functions, i.e.,
OFUS (Ir, == max fo( a), BEO,
where θ, : (0: F(D > 8} and P(D the likelihood of D given 0. In many cases, the constraint can be replaced by MSE(0; D) < 5. For simple function classes such as multi-armed bandit and linear contextual bandit, SFU has closed-form solutions
However, for more complex tasks, OFU algorithms explicitly maintain a confidence set, c.g., see (Foster et al., 2018; Dudik et al., 2011). The cost of explicitly maintaining confidence set is extremely expensive for complex problems or function classes, such as deep neural networks. One alternative approach is consider the Lagrangian Multiplier method, i.e., solving ming max, [o( a) 1)MSE((; D). But this is still much slower than our optimization oracle in general.
Our results, theorem 1 and theorem suggest that we can effectively trade-off exploration and cxploitation while avoiding explicitly maintaining the confidence set.
'The computational cost of closed-form solutions can be expensive for high- digh--imensional problems when the function class linear.

---

Under review as a conference paper at ICLR 2022
ResNet20 bandtt
MLP bandit
ResNet20 bandit
MLP bardi
<-penty
C-geedy
ROFLIMeTTO
14410
ROFU/00:10 RIDFUIOIS
ROFUMM-10
0.2
ROFU/1--1
ROPUMM-1
Corfilence
0.14
Time stop
Timre stap
Time stop
Time stop
Figure I: Ablation study MLP and ResNet bandits. Notation: M 1/5/10 means that 1/5/10 10 gradient descent updates in Alg. 2.
Contextual bandit algorithms with optimization oracle: As mentioned in section 1, some contex- tual bandit algorithms invoke optimization oracles to accelerate computation. Agarwal et al. (2014); Dudik et (201 1) rely on cost-sensitive policy classification oracles and achieve an optimal regret of (og
where IT is the space of policies. This kind of oracles can be computational inef- ficient for complex function classes. And these algorithm call the optimization algorithm many times in each round to achieve a regret guarantee, e.g. Dudik et al. (2011) calls the optimization oracle for O(T5) times. Foster al. (2018) access regression oracle which is special case of Eq. (2) with ?) R +00. But Foster et al. (2018) calls the oracle for (log T) times for cach action in cach round. More importantly, they explicitly maintain subset of @ with MSE(6; D) < ming MSE(0% (0'; D) + And as discussed above, maintaining such confidence set is infeasible for complex function classes.
Algorithms for deep contextual bandit: We note that there attempts (Zhou al., 2020; Zhang et al., 2020) to extend the realizability-basee algorithms to deep neural networks. NeuralUCB (Zhou al., 2020) and Neural Thompson sampling (Zhang al., 2020) conduct experiments on multi- layer neural network with significantly simplified and approximate implementation to accelerate computation. The analyses do not apply to general function classes.
EXPERIMENT
We now empirically evaluate ROFU. We only present empirical results for Option as the empirical performances of Option II is slightly better than Option I. For simplicity. in all our experiments, we set 1/t,a = 1 and a = 1. More specifically, we train 0.- by minimizing MSE(6; Dz) with standard optimizer? and Ōr,a is trained to maximize fo(x,
DIMSE(0; D) using Alg, 2. And OFU" a) = fe._, (Ii, a) + Vie... (Ie, a) - fo._, (Iz, a) as in Option II.
5.1 ANALYSIS ON MLP AND RESNET BANDITS
The goal of this work is to develop contextual bandit algorithm which is efficient in trading off EE when reward is generated from a complex function while keeping low cost on computational resources. From Alg. 2, we can see that the time complexity of ROFU is determined by the training step M. To reduce computational cost, we evaluate ROFU when M is small in experiments. As suggested by the experimental results, setting M be relatively small value doesn't hurt the performance much.
To evaluate the performance of ROFU in Alg, complex tasks, we consider two contextual bandits with a DNN as the simulator. That is. r(æ;, a) is generated by DNN model. We consider two popular DNN architectures to generate rewards: 2-layer MLP and 20-layer ResNet with CNN blocks and Batch Normalization as in He et al. (2016). We summarize other information of the two tested bandits in Table. 1.
We train 6 with stochastic gradient descent starting from 0.-2 in all the experiments.
7

---

Under review as a conference paper at ICLR 2022
Bandit
Layer
Context Dim
Arms
NN Parameters
Context Distribution
Noise
MLP
10
10
Random
Gaussian
NV [0. 0.05)
ResNet
20
3 x 32 x 32
10
Trained on Cifar10
Uniform
(0,0.55
Table
Basic information about MLP and ResNet bandits.
fiendial
stalkog
covertype
ROTU
RDFU (ours)
ROFU (ours
RDFU Joars)
Oreadyy
Dree7y
Dreedy
Oreedy
Dospurt
Drsgut
Dreao
Despout
Nevralinee
Neandiu now
Nauna Lines
Bootern
Baotrin
200
Boananno
Panerho an
109
Time ktep
Time stap
Time stup
Time slop
RDFU
HOFU (sung)
RQFU
Sanwdy
Glaudy
Growdy
Dropout
Chopout
Dropect
Nouril Iroo
Nourol Iooo
Noxril
Dockeiop hp
Peramilviic
Paraeflun
1108
Time slop
Time stop
Timee slop
Figure 2: Evaluations on non-linear contextual bandits.
We use DNNs with larger size for training in Alg. 2. More specifically, for MLP-bandit, fo is chosen as 3-layer MLP and for ResNer20-banme for 16 times. We present the regret and confidence bonus in Fig. 1. From Fig. 1, we can see that (1) ROFU can achieve small regret on both tasks with a considerably small M even for very large DNN model; (2) The confidence bonus monotonically increases with M For each M, the confidence bonus converges to as expected. Moreover, while the regret seems sensitive to the value of M, the regrets of ROFU with M 5, 10 are much smaller than the case of M and e-greedy.
fo is chosen as ResNet32. Each experiment repeated
5.2 PERFORMANCE COMPARISON ON TEAL-WORLD DATASETS
To evaluate ROFU against powerful baselines, conduct experiments on contextual bandits which are created from real-world datascts, following the setting in Riquelme et al. (2018). For cxample, suppose that == { ot) hesT is K-classification dataset where x; is the feature vector and E [K] is the label. We create a contextual bandit problem as follows: at time step t < T, the agent observes context Ty, and then takes an action a, The agent receives high reward if it successfully predicts the label of x4. For non-classification dataset, can turn it into contextual bandit in similar ways. For the details of these bandits, please refer to Riquelme et al. (2018).
For baselines, consider NeuralUCB Zhou et al. (2020) and Thompson sampling variants from Riquelme et al. (2018). is noteworthy that we only evaluate the algorithms in Riquelme et al. (2018) 8) with relatively small regrets. We directly run the code provided by the authors. For ROFU, we fix M = 5 for all experiments. We tune other syper-parameters of ROFU on statlog and directly apply the hyperparameters on statlog to other datasets except mushroom. This is because the reward scale of mushroom is much larger than other datasets. For baselines, we directly use the best reported hyper-parameters.
8

---

Under review as a conference paper at ICLR 2022
We report the regret R E EiST r(z,, 4)) EiST r(E2, a4) where df arg m for (Zz, a) and 0' is the parameter trained by minimizing MSE the whole dataset. The results are presented in Fig. 2 and Table 2. We found that the regret of NeuralUCB is occasionally linear. This might be
because that NeuralUCB uses diagonal matrix approximate Z accelerate. Morcover, we can see that ROFU significantly outperforms these baselines in terms of regret.
Cavertype
Starlog
Financial
Mushroom
Dropout
L.7
1.51
1.34-0.14
1.00=0.09
1.14+0.18
1.64=0.77
3.50=0.60
2.21
Bootstrup
2.23:1.00
2.51:0.16
1.72-0.11
1.43:2.10
1.93+0.13
1.43=157
4.52-2.29
2.04
ParamNoise
2.30
2:2820023
1.59-0.14
1.3720.10
1.8020.00 20
3.8826.00
4.07=1.76
1.0620.32
NeuralLincar
1.82=0.09
3.24=u.47
1.70=o.18
1.46a0.12
1.84+0.19
1.25=o.11
2.25=0.35
1.00
Greedy
2.47+1.12
2.76+1.24
1.65=o.10
1.56+0.11
2.27+0.28
3.08=4.91
4.74-2.81
1.20==0.11
NeuralUCCB
14.6
1.
1.47=0.08
1.18=0.05
1.86:20.1
41.42:69.5
2.74=0.50
17.29+7.49
ROFU (ours)
1.05
1.00
1.00
1.17.000
1.00.2.14
1.00.0
1.0011.00
1.221037
Table The final regret of each algorithm. The regrets are normalized according to the algorithm with smallest regret.
CONCLUSION AND FUTURE WORK
In this work, we propose an OFU variant, called ROFU, which is designed for contextual bandit with general function classes. We show that the regret of ROFU is (near-)optimal under very mild assumptions. Moreover, we propose an efficient algorithm to approximately compute the upper confidence bound. Thus, ROFU is efficient in both computation and EE trade-off, which are empirically verified by our experimental results.
EE trade-off is fundamental problem that lies in the heart of sequential decision making. How- ever, the huge computational cost of (near-)optimal EE trade-off algorithms significantly limits the application, especially on complex domain. We hope method could inspire more algorithms to efficiently trade-off EE for sequential decision-making tasks beyond contextual bandit, such as deep reinforcement learning.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320, 2011.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Peter Auer, Nicolo Cesa- Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 2002a.
Peter Auer, Nicolo Gesa-Bianchi,
Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(())48-77, 2002b.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Sébastien Bubeck and Nicolo Desa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: 1204.521 2012.
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, 2011.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.

---

Under review as a conference paper at ICLR 2022
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. arXiv preprint arXiv: / 2369, 2011.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199-321111 PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference Machine Learning, pp. 1539-1544 1548. PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In The IEEE Conference on Computer Vision and Puttern Recognition (CVPR), June 2016.
H Brendan McMahan and Matthew Streeter. Tighter bounds for multi-armed bandits with expert advice. 2009.
Carlos Riquelme, George Tucker, and Jasper Snock. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. 2018.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:2010.00 00827, 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, 2020.
10


Reviews:
[{"review_id": "r2QqPSmF7H6", "reviewer": "Reviewer_xPt8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe paper conducts numerical experiments and shows that ROFU outperforms many popular baselines including the UCB and Thompson sampling variants when using deep neural networks as the function class. The experimental results are interesting.\n\nWeaknesses:\n- The paper claims that \"theoretically, for general function classes under very mild assumptions, ROFU achieves a near-optimal regret bound\" in the abstract, and highlights it as a main contribution throughout the paper. I find this claim misleading. The regret bound for general function classes is stated in Theorem 1, which relies on a super strong assumption — Assumption 2, for which the authors do not provide any concrete and practical function classes as examples. Importantly, Assumption 2 does not even hold for linear function classes. This makes the use of the term \"general contextual bandits\" (in the title and main body) very misleading — in fact, Assumption 2 is far more restrictive than the assumption of linear function classes, and I believe that this assumption can directly make exploration unnecessary (i.e., *the greedy algorithm can directly achieves the near-optimal $\\tilde{O}(\\sqrt{T})$ regret bound*). Since there is no exploration-exploitation trade-off under Assumption 2 at all, I don't feel that Theorem 1 can be viewed as a non-trivial result for \"general contextual bandits\".\n  - Let me explain why Assumption 2 is strong in more detail. Assumption 2 essentially says that, for arbitrary $x$ and $a$, $|f_{\\theta}(x,a)-f_{\\theta^*}(x,a)|=\\Theta(\\textrm{distance}(\\theta,\\theta^*))$. This means that the choice of actions $a_1,a_2,\\dots,a_t$ is not important for learning $\\theta^*$ at all, as any sequence of $(x_1,a_1),(x_2,a_2),\\dots,(x_t,a_t)$ always gives the same estimation rate of $\\textrm{distance}(\\theta,\\theta^*)$ by running least squares regression. Moreover, $\\textrm{distance}(\\theta,\\theta^*)$ can also directly control the regret bound. Therefore, it seems that even the greedy algorithm can achieve near-optimal regret under Assumption 2.\n  - Although the paper also has other theoretical results (Theorem 3 and Theorem 4) on the regret bounds for linear function classes, the fact that OFU-type algorithms can attain near-optimal regret for linear function classes is already well-known. Therefore, it is not clear what is the contribution of Theorem 3 and Theorem 4 .\n\n- Even if the authors can show Theorem 1 under much weaker assumptions on the function class, it is unclear to me whether the algorithm really has computational advantages over some existing algorithms based on the least squares oracle. Specifically, the optimization oracle assumed in the current paper (see Definition 2) seems to be strictly more restrictive than the least squares oracles used in [1,2,3]. It is also worth noting that [2] and [3] have already provided optimal and efficient algorithms for general stochastic contextual bandits using the least squares oracle (under no assumption on the function class and standard/weak assumptions on the action space). Therefore, even if the authors can extend Theorem 1 to a much more general setting, comparisons to existing literature [2,3] seem to be important.\n  - By the way, in Section 4, when the authors compare their result to [1], the authors say that \"[1] explicitly maintain a subset of $\\Theta$ ...\". To my knowledge, this statement is not correct — [1] does not explicitly maintain the subset, but designs a oracle-efficient algorithm to cleverly compute the confidence bounds (see Theorem 1 therein).\n\n- There are several unclear places in the paper. For example, the \"MSE\" appears in Definition 2 is not really defined in the main article. Also, in Algorithm 2, it is unclear to me how $\\tilde{\\Delta}$, the estimator of gradient, can be efficiently computed using the assumed optimization oracle.\n\nReferences:\n\n[1] Foster, D., Agarwal, A., Dudík, M., Luo, H. and Schapire, R., 2018, July. Practical contextual bandits with regression oracles. In International Conference on Machine Learning (pp. 1539-1548). PMLR.\n\n[2] Simchi-Levi, D. and Xu, Y., 2020. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Available at SSRN 3562765.\n\n[3] Xu, Y. and Zeevi, A., 2020. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07876.\n", "summary_of_the_paper": "The paper presents a contextual bandit algorithm called regularized optimism in the face of uncertainty (ROFU) which is designed for general function classes. The algorithm is claimed to achieve near-optimal regret \"for general functions under very mild assumptions\". However, I find this claim misleading. The optimization oracle considered in the paper also seems to be more restrictive than the least squares oracle considered in recent literature.\n\nThe paper also conducts numerical experiments to examine the empirical performance of the ROFU algorithm and compare it to several baselines. The performance of the ROFU algorithm seems promising. I feel that the experimental part of the paper is more solid and interesting than the theoretical part. ", "summary_of_the_review": "The experimental results of the paper may have potential. However, the existing theoretical results are relatively weak and overclaimed. The paper also fails to demonstrate its contributions compared with prior works. Therefore, I do not think that the paper can be accepted in its current form.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nVE8A2B49T_", "reviewer": "Reviewer_sNy5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Contextual bandit with general function classes is an interesting problem in machine learning. However, I think this paper still has some concerns.\n\n1. Thm 1 requires the parameter space $\\Theta$ to be a finite set. However, it is not clear in the paper how to deal with the finite parameter space. For example, the authors say max can be solved using a gradient-based algorithm (right after Definition 2), but don't show how to adjust the gradient-based algorithm to finite parameter space. \n\n2. I think the conclusion of Thm 3 should be $R_T\\leq \\tilde{O}(d\\sqrt{dT})$ because $\\beta_T=\\tilde{O}(d)$.\n\n3. When the authors claim Assumption 2 is mild (right after Assumption 2), they say if the h function is smooth. However, the absolute value function usually affects smoothness (by at least one point).\n\n4. What's the intuition of Option II? I suggest the authors provide more discussion on Option II and introduce the relationship between Option I and Option II.\n\n5. I'm confused with the proof of Thm 2. Thm 2 proves the lower bound by giving an instance of the linear function. However, as presented in the second line of page 4, the linear function doesn't satisfy assumption 2. Thus the given instance doesn't meet the condition of Thm 2. \n\n6. In section 5, the authors only present the results of Option II. However, I think it would be better to show the results of both Option I and Option II because Option I has regret bound for general functions. Also, I'm curious about whether Option II also has regret bound for general functions since the paper claims that Option II performs better than Option I.\n\n7. Some experimental results haven't converged.", "summary_of_the_paper": "This paper studies contextual bandits with general function classes. The authors propose Regularized OFU algorithm where the agent selects the action maximizing the OFU function in each round. The proposed methods achieves $O(\\sqrt{T\\log\\frac{|\\Theta|T}{\\delta}})$ regret for general functions under mild conditions and achieves $\\tilde{O}(d\\sqrt{T})$ regret for linear functions.", "summary_of_the_review": "I think the theoretical part is not very consistent with the motivation and the experiments. It is not very clear why to consider such two options and why the experiments only use option II but in non-linear case.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gTcuXHpdJy", "reviewer": "Reviewer_e8Nb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nI think the paper is tackling an important aspect of the contextual bandit problem, aiming for flexible function classes and efficient implementation. The idea of utilizing regression oracles has been proposed previously, but the authors focused on designing an algorithm that is efficiently implementable for practical usage.\n\nThe generalization of linear bandit is also nice and makes sense.\n\nWeaknesses:\nFirst, the authors argue that \"the availability of such optimization oracle [for solving Eq.(2)] is a very mild assumption in practice.\" In practice, there are algorithms to \"approximately\" solve Eq.(2). To exactly solve for possible non-convex function $f_\\theta$ is not mild. The regret analysis is based on exactly solve Eq.(2). If one allows for approximate solutions for the optimization problem that the paper presents, then it would be fair to allow for similar approximate solutions for the previous works that the authors criticize for not having tractable solutions.\n\nAnother drawback is the lack of comparisons with more recent work including  Foster & Rakhlin, (2020) and Simchi-Levi & Xu (2020). The authors mention Foster & Rakhlin, (2020) once in the introduction but do not directly compare with their algorithm and results despite the fact that it is also a regression oracle-based algorithm with flexible function classes. The paper does not mention Simchi-Levi & Xu (2020) at all, which uses a regression oracle under realizability assumption.\n\n#References\nSimchi-Levi, David, and Yunzong Xu. \"Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.\" Available at SSRN 3562765 (2020).\n", "summary_of_the_paper": "The paper proposes a UCB variant called Regularized-OFU (ROFU) with provably near-optimal regret. ROFU computes UCBs with an optimization oracle which, the authors claim, can be efficiently implemented for flexible function classes.\n\nThe paper provides a sublinear regret bound of $O(\\sqrt{T \\log \\frac{|\\Theta|T}{\\delta}})$ that matches the lower bound up to a logarithmic factor. The paper also provides experimental results to support their claims of efficient implementation.\n", "summary_of_the_review": "With the reasons above, I am leaning towards rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RhRh9gd_nuu", "reviewer": "Reviewer_aMkn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the biggest issue of this paper to me is Assumption 2. The authors keep saying that this assumption is \"very mild\", but they don't even give a concrete example that satisfy this condition. To me this is a very strong assumption. It means that if $\\theta$ is not optimal, $f_\\theta$ is strictly worse than the optimal value at every (x,a). Even the simplest case (linear function) I can think of does not satisfy this assumption. I think this assumption makes sense only if c1 is very very small, but it makes the regret bounds vacuous. \n\nThe theorem is also strange to me. Theorem 1 only shows the case when $\\alpha=0$. If so, why do we even need the regularization term in the algorithm? I didn't find any discussion in the experiments, either. \n\nAs for the algorithm design, I think it is reasonable and I appreciate its simplicity. However, I don't think authors do a sufficient literature review. The citations are relatively few. Although I cannot come up with any previous work that consider similar algorithms, I think the authors should compare more previous methods to support the novelty of their algorithm. For example, with some random search on the Internet, I found a paper \"Regularized Contextual Bandits\" by Fontaine et al. I am not saying the paper is comparable to this work but I think this is something the authors should clarify. Moreover, the survey should not only cover contextual bandits but discuss related fields such as reinforcement learning and online regression literatures.  \n", "summary_of_the_paper": "The authors present an algorithm called regularized optimism in face of uncertainty (ROFU) for general contextual bandit problems. It extends upper confidence bounds to general functions. When the optimization oracle can be efficiently solved, the algorithm can be efficiently implemented. Some theoretical regret bounds and experiments are provided.   ", "summary_of_the_review": "The strong assumption makes theoretical contributions of this paper incremental. The authors also didn't do enough literature survey to support the novelty of their algorithm. Therefore, I tend to recommend rejection.    ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the contextual bandit problem with general function classes and introduces a novel algorithm called regularized optimism in face of uncertainty (ROFU). Although this is an important and relevant problem, the theoretical contribution is rather weak due to the strong assumptions, which also results in a lack of consistency with the motivation and the empirical settings. Moreover, although experimental results suggest that the proposed ROFU method may have potential, the empirical contribution is unclear as the paper currently lacks a comparison with appropriate previous work. All these concerns were raised in the reviews, but unfortunately, none were addressed in the rebuttal phase.
Decision: Reject