Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures
Authors: Hamish Flynn
David Reeb
Melih Kandemir
Jan Peters
Venue: NeurIPS 2023 oral (2023)
Keywords: Linear bandits
confidence sequences
martingales
convex optimization
cumulative regret
regret analysis
TL;DR: Based on novel mixture martingales, we obtain tighter confidence bounds for linear bandits resulting in better algorithms with performance guarantees.

Abstract: We present improved algorithms with worst-case regret guarantees for the stochastic linear bandit problem. The widely used "optimism in the face of uncertainty" principle reduces a stochastic bandit problem to the construction of a confidence sequence for the unknown reward function. The performance of the resulting bandit algorithm depends on the size of the confidence sequence, with smaller confidence sets yielding better empirical performance and stronger regret guarantees. In this work, we use a novel tail bound for adaptive martingale mixtures to construct confidence sequences which are suitable for stochastic bandits. These confidence sequences allow for efficient action selection via convex programming. We prove that a linear bandit algorithm based on our confidence sequences is guaranteed to achieve competitive worst-case regret. We show that our confidence sequences are tighter than competitors, both empirically and theoretically. Finally, we demonstrate that our tighter confidence sequences give improved performance in several hyperparameter tuning tasks.

Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures
Hamish Flynn David Reeb', Melih Kandemir', Jan Peters
Bosch Center for Artificial Intelligence, Renningen, Germany
TTechnische Universität Darmstadt, Germany
3 University of Southern Denmark, Odense, Denmark
Deutsches Forschungszentrum für Künstliche Intelligenz (DFKI), Germany hamishttrobot-Leariing de, david. reeb@de david.reeb@de bosch. com, kandemir@imade adu.dk, jan. San.petersotu-de wawpsstttdddamaaat.t....m..
Abstract
We present improved algorithms with worst-case regret guarantees for the stochas- tic linear bandit problem. The widely used "optimism the face of uncertainty" principle reduces a stochastic bandit problem to the construction of a confidence sequence for the unknown reward function. The performance of the resulting bandit algorithm depends the size of the confidence sequence, with smaller confidence sets yielding better empirical performance and stronger regret guarantees. In this work,
novel tail bound for adaptive martingale mixtures to construct confidence sequences which are suitable for stochastic bandits. These confidence sequences allow for efficient action selection via convex programming. We prove that linear bandit algorithm based on our confidence sequences is guaranteed to achieve competitive worst-case regret. We show that confidence sequences tighter than competitors, both empirically and theoretically. Finally, we demon- strate that our tighter confidence sequences give improved performance in several hyperparameter tuning tasks.
Introduction
The stochastic linear bandit problem a sequential decision-makes problem where, in each round a learner chooses an action and then receives a stochastic reward for its choice of action. The expected value of each reward a linear function ((a,) 0" of a known feature vector ((a;) associated with the corresponding action, while 0" is unknown. The linear bandit problem has attracted great deal attention because
expressive enough to be a faithful model of many real-world decision-making problems, such news recommendation (Li et al. 2010) and dynamic pricing (Cohen et al. 2020), yet it is simple enough to make theoretical analysis tractable.
A popular way to design algorithms for linear bandits is to follow the principle of optimism in the face of uncertainty. This principle states that we should choose actions if the expected reward function is nice as plausibly possible. For linear bandits, the principle can be instantiated with confidence sequence Og, OI,... for the parameter vector 0* of the expected reward function. confidence sequence is sequence of subsets of the full parameter space θ which is built iteratively as data becomes available and is constructed such that with high probability over the observed data, 0" is contained in each confidence set O,, One can then run upper confidence bound (UCB) algorithm, which at round t chooses an action 0++1 by maximising the UCB maxase, {o(a) 0} with respect to
The popularity of UCB algorithms stems from the fact that they come with worst-case regret guaran- tees and often perform well in practice. However, the performance of UCB algorithm is intimately
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

CMM-UCB
AMMAUCB
OFUL
Figure 1: Tighter upper and lower confidence bounds via tail bounds for martingale mixtures. The upper and lower confidence bounds of CMM-UCB (left), AMM-UCB (middle), and OFUL (Abbasi- Yadkori et al. 2011) (right) for a test function linear in random Fourier features. The bounds from CMM-UCB and AMM-UCB are visibly closer to the true function (dashed line) than those of OFUL. The CMM-UCB confidence bounds are slightly tighter than the ones of AMM-UCB.
tied to the size of the confidence sets it uses. The smaller the subsets in the confidence sequence, the better the regret bound and, perhaps more importantly, the better the algorithm performs in practice.
In this work, we develop general-purpost tail bound for martingale mixtures, which can be used to construct confidence sequences. When specialise general results to the linear bandit problem, the maximisation problem to compute the UCB a convex program. We maximise the UCB over actions via gradient-based methods, and investigate two procedures for computing the UCB along with its gradient: (a) Convex Martingale Mixture UCB (CMM-UCB): We employ a convex solver for the UCB maximisation and calculate its gradients via differentiable convex optimisation (Agrawall et al. 2019); (b) Analytic Martingale Mixture UCB (AMM-UCB): We exploit weak Lagrangian duality obtain an analytic upper bound on the UCB, whose gradient can be computed in closed-form or via standard automatic differentiation procedures.
Fig. higghlights key observation: both of our UCBs are tighter than those used in the state-of-the-art OFUL algorithm (Abbasi- Yadkori et al. 2011 for stochastic linear bandits. We verify this claim We evaluate CMM-UCB, AMM-UCB, OFUL and
empirically in Sec. (eand prove it in App. C
various other linear bandit algorithms in several hyperparameter tuning problems (Sec. [8. We find that our tighter UCBs result linear bandit algorithms with better performance.
2 Related Work
Algorithms with regret guarantees have been developed for several variants of the stochastic linear bandit problem. Dani et al.) (2008), AAbassi AbbbasiYaadkori et al.) (2009) and Rusmevichientong & Tsitsiklis (2010) proposed algorithms for a linear bandit problem where the action set is fixed, possibly inhnite subset of finite dintee-dimnsionall vector space. Auer (002) and Chu et al. (011)) proposed algorithms for linear bandit problems where the action set has finite cardinality. but may change over time. Abbasi-Yaddkoi Yadkori al. (2011) proposed the OFUL algorithm for linear bandit problems with changing and possibly infinite action set, which is essentially the problem that investigate. We consider stochastic linear bandit problems where the reward function is a composition non-linear feature map and a linear function. This can be seen as restricted version of the stochastic kernelised bandit problem, where the kernel feature map is minteedimensionall Srinivas et al. (2010);
possibly
Valko al. (2013); Chowdhury & Gopalan 2017); Camilleri al. (2021) 1); Salgia et al. [2021 and Li Scarlett (2022) proposed algorithms with regret guarantees for various kernelised bandit problems.
In the bandit literature, confidence sets and confidence bounds constructed from online (e.g. non-i.i.d.)
observation points for unknown linear functions have been proposed by Dani al.) (2008) ; Rus mevichientong & Tsitsiklis (2010) and /Abbasi- Yadkori et al. (201T). Online confidence sets/bounds for unknown functions in separable Hilbert spaces and reproducing kernel Hilbert spaces (RKHSs) have been proposed by Srinivas et al. (2010); Abbasi- Yadkori (2012); Kirschner & Krause (rause|20018 and Durand et | (2088) Russo & Van Roy| (2013) derived online confidence sets unknown functions belonging to arbitrary function classes.

---

We use the term "mixture of martingales", or martingale mixture, to refer to a martingale of the form [.-r where (M) E N) collection of martingales indexed by the variable E V. Martingale mixtures can be traced back to (Darling & Robbins 1968 Robbins 1970). and have been used to construct confidence sequences since at least the work of (196)) Proofs of tail bounds for martingale mixtures typically use the method of mixtures, which was first used by Robbins & Siegmund (170)) and was later popularised by (de la Peña et al. (2004) 2009). Methods for martingale mixtures have seen renewed interest in the sequential testing literature (Howard et al.
2020, Kaufmann & Koolen 202T), Examples of confidence sequences for bandits that use martingale mixtures include the works of Abbasi- Yadkori al. (2011); Abbasi- Yadkori (2012); Kirschner & Krause (2018); Durand et al. 2018): Neiswanger & Ramdas (2021). Unlike in these examples, construct confidence sequences based on adaptive martingale mixtures (EuwP, (+)]it N), where the mixture distribution P. can be refined as more data is acquired at each time l.
3 Problem Statement and Background
We consider problem in which a learner plays a game over sequence of rounds, where T may not be known advance. In each round I, the learner observes an action set A, and must choose an action
a E A,, The learner then receives reward r ((x)) 0" + et. The feature map Φ A - IR is a known function that maps actions to d-dimensional feature vectors, where A = A,. 0 E Rd an unknown parameter with Euclidean norm bounded by some known > 0, i.e. 1 S B. 6,, C2,2...., Cr are conditionally zero-mean and C,, ...; CT are standard in the linear bandit literature, see e.g. (Abbasi- Yadkori et al. (001T)
Bub-Gaussiin noise variables. These assumptions on 0"
While our regret analysis applies to any action sets, our algorithms focus on the case where the action sets Ar are continuous subsets of RdA.
The goal of the learner is to choose a sequence of actions that maximises the total expected re- ward, which is equal to Σ Φ(a;) 0" after T rounds. We use cumulative regret, which is the difference between the total expected reward of the learner and the optimal strategy, to evaluate
the learner. For single round, we define the regret A(ae) s(at) 0 -(aa) TO', where
a- argmax {o(a) 0"). After I rounds, the cumulative regret AuT = Σ A(a.).
Confidence Sequences. For any level 5 E (0, 1]. a (1 - cocoodiiee sequence for the parameter vector 0* a sequence θ, O2.... of subsets of R.d, such that each O can be calculated using the data 011 ri...., dr and the sequence satisfies
Par.e..... (vt 2 1: 0" E 1-
A confidence sequence ,,, 2 is thus a sequence of data-dependent confidence sets such that with high probability over the random actions and rewards, 0" E O, holds for all / Z 1 simultaneously. We remark that the confidence sets O in this paper are random closed sets in the sense of Def. 1.1.1 of (Mochaaovv 2005). which implies that the event E O, is actually measurable for all Rd
4 UCB Algorithms for Linear Bandits
We describe here how to transform confidence sets for 0" into a UCB algorithm for the linear bandit problem. Such algorithms have appeared under various names, such as LinRel (Auer 2002). LinUCB et al. 2010) and OFUL (Abbasi-Yadkori et al. 201T). We refer to this meta algorithm as LinUCB, and give its pseudo-code in Algorithm| [ When with our confidence sets, we call this algorithm
CMM-UCB resp. AMM-UCB (see Sec. 6).
In each round t, the first step is to construct a confidence set θ, from the previous observations {(ax, rx) H If 0* E O2 with high probability, then for any action a,
UCBe, (a) := max( 0}
eee,
is upper confidence bound (UCB) on ((a)T T Taking minsee, in I yields the lower confidence bound LCB,, (a). Once a confidence set θ, has been constructed and the next action set A has been observed, the LinUCB algorithm chooses the action
0++1 argmaax {UCBe, (a))
(2)
aEAA+1
3

---

Algorithm 1: LinUCB
for f 0, 1......
Construct confidence set θ from {(ax, rk)]k=1
Observe next action set A
Play next action d++11 argmax (UCBe,
Observe next reward Tt+1
end
which maximises the UCB. The remaining challenge lies in the construction of the confidence sets.
5
Confidence Sequences from Martingale Mixtures
In this section, we develop specialise our general result to the stochastic linear bandit setting, described See. and construct confidence sequences for the parameter 0"
tail bound for adaptive martingale mixtures. We then
5.1 Ceneral-Purposs Tail Bound for Adaptive Martingale Mixtures
We consider a general setting in which random functions (Z₃ + Rlt E N), and a sequence of predictable random variables (Ar E N). For ft I. we define the conditional cumulant generating function ()e Ax) as
given filtration (Haft N), sequence of adapted
V (fe, xe) (E (cxp(>
where the expectation over (f) and > (although X non-random when conditioned on H1-1). We use the shorthand f. = (f1, f2. and ) = (2.,)2,...; Ax). Let
Mi(f. Av) = exx Σ ZeZx(f)
[MZ(()))- - =b((fe:uu)
(3)
Me(fa 2: Ax) is slight generalisation of the martingale used in App. B.1 of (Russo & Van Roy 2013). One can show that for any sequence (Salt E N), (Mrfr, At)lt E N) is a martingale and We will now construct an adaptive martingale mixture.
Bf A.)] = (App
We call a data-dependent sequence of probability distributions (Pylt E N) an adaptive sequence of mixture distributions if: (a) Pt is distribution over ft E IR'; (b) P. is measuuaas;,,, (c) the distributions are consistent in the sense that their marginals coincide, i.e. Pff Pt- 1)
: for all f. These conditions on the sequence of distributions ensure that the martingale mixture PP [M Ao]lE N) is fact a martingale. In App. A.I we verify this and show that 5- [M Xx)]] = 1. From here, we can use Ville's inequality for non-negative supermartingales (Ville 1939) to obtain our general-purpose tail bound.
Theorem 5.1 (Tail Bound for Adaptive Martingale Mixtures). For any (0, 1), any sequence of predictable random variables (Delt N), and any adaptive sequence of mixture distributions (P.lt E N), the following holds with probability at least
In P.
(M.(f(:)i))) < In(1/0) for all t 2 1.
We provide a proof of this result in App. upper bound on e'x A the statement of the theorem still holds.
A.2 Note that if each (fk 2a) in is replaced by an
Thm. 5. is closely related to the general- purppse anytime PAC-Bayes bound in Thm. 3.1 of (Chugg et al. 2023) The main difference is that our inequality holds for adaptive sequences of mixture distributions or priors. PAC-Bayes bounds with somewhat similar adaptive sequences of mixture
distributionnsprroors have recently been proposed by Haddouche & Guedj 2002 2023).

---

5.2 Confidence Sequences for Stochastic Linear Bandits
We now specialise Thm. 5.1 the stochastic linear bandit setting. For the filtration (H,]t N), we set He to be the o-algebra generated by (01, ri,.... (tt, Yt, ax+1). ). For reasons that will become clear, we choose ( = (fr )(a)) O je, Since ((ft) is linear in the noise variable et, &h (ft, xz) can be upper bounded using the aau-Gausiian property of et. We have
(t A,) = In (R [exp (Ar(Se p(a.) )et)) H(-1]) S X20 ((ar) /
(4)
With this upper bound on (de A.), Thm. 5.1 implies that, with probability at least -
(ux )(ax) To (r= <(ax)) 0² (Caf--((a=TT00)) S
Bx exp
Since (fa) is linear in fe, this integral has closed-form solution whenever the mixture distribution a Gaussian P. = [1,, T.). Although there is a closed-form solution for any predictable sequence (Xelt N) (see App. B. D. we choose d 1/02, which yields relatively simple convex quadratic
constraint for 0*, Collecting the feature vectors in 4 := [o(a]] (Maa))...,olo. M(a)] E Rexd and writing
the reward vector r, ==
we arrive at (see App. B.2
1+ (1+ -1 )z)
T, 02 +
1,,00- - rell2 S (44-1) r.)
(4--r) + + Inde
L
20
In
(5)
8'
This incquality has an attractive interpretation. At each step of the bandit process, the (unknown) ground-truth reward vector 4 0" lies within sphere around the observed reward vector Tr, with squared radius equal to the RHS of (5) One can think of the mean vector μ4 as a prediction of the reward vector rt. given the previous data d1, 7l,..... Gt-1, 1t-1,, 4g. The covariance matrix T. can be thought of as the uncertainty associated with the prediction f4, If f4, is good prediction of rı. then the quadratic "prediction error" term in (5) will be close to O, and we can afford to choose T, close to zero to minimise the log determinant term. In this situation, (5) can give a much tighter constraint than the naive bound la², especially when
a pessimistic upper bound on the true sub-Ga Gabb-aassiin parameter. This naive bound follows from the observation that || 00 rell2 = || where e (E1, Et). Combining the constraint in (5) with our assumption ||0" l|2 S B yields our confidence sequence for 0"
Corollary 5.2 (Martingale Mixture Confidence Sequence). For any adaptive sequence of mixture distributions P/ (4,,, T,), it holds with probability at least 1 - 8 that for all t '2 1 simultaneously. O" lies in the set
+. 0 Rd 11:00 - rell2 RMM. and |01 S B).
(6)
where we define RAM,, as the right-hand-sin of Eq. (5)
The boundaries of the constraints in (6) are both ellipsoids in Rdd which means that each θ is the intersection of (the interiors of) two ellipsoids.
Martingale Mixture UCB Algorithms
In this section, we describe our CMM-UCB and AMM-UCE algorithms, which are two different
implementations of LinUCB (Algorithm with confidence sequence from Corollary 5.2
6.1 UCB Computation and Optimisation
To run the LinUCB action selection rule with our confidence sequence, we need to be able to maximise UCB,, (a) with respect a. The value of the UCB at the action is the solution of
UCBe, (a) = max
(aa) 0
S.t. |2,00 relly < AMMA and
|01| < B.
(7)
OER"
5

---

This is convex optimisation problem, which can be efficiently solved via convex programming. If the action sets have finite cardinality, UCBe, (a) can be maximised by solving (7) for each a E A, and then comparing the solutions. If the action sets are continuous subsets g44, then exact maximisation of UCBa, (a) is (in general) infeasible. For example, when the feature map Φ is linear in a, UCBe, (-) the maximum over set of linear functions, which a convex function of (see Eq. (3.7) in Sec. 3.2.3 of [oyd & Vandenberghe (2004). Since maximisation of a convex function is (in general) NP-hard, exact maximisation of CBe, (a) is also (in general) NP-hard. For this reason, when the action sets are continuous subsets of IRd. (and is differentiable), approximately maximise UC (a) via gradient-base -hased local search.
6.2 Convex Martingale Mixture UCB
Our Convex Martingale Mixture UCB (CMM-UCB) algorithm is based computing using numerical convex (conic) solvers from the CVXPY library (Diamond & Boyd 2016 Agrawal et al. 2018). Note that (7) is already stated in conic form, which is favourable for conic solvers (Boyd & Vandenberghe/ 2004). Solving 7 numerically gives the tightest UCBs that can be obtained from confidence sequence. To compute the gradient of UCB,, (a) with respect to the action a, use recently developed methods for differentiating conic programs at their optimum (Agrawal et al.) 2019). which are implemented in the evxpylayers library.
6.3 Analytic Martingale Mixture UCB
Our Analytic Martingale Mixture UCB (AMM-UCB) algorithm uses an analytic upper bound on the solution of (7). The resulting analytic confidence bounds looser than the numerical confidence bounds used by CMM-UCB, but are cheaper to evaluate and maximise. Theorem6.1 states our upper bound on the solution of
Theorem 6.1 (Analytic UCB). For all a > O, we have
UCBa,(a) (a) = max {d(a) T 0} S b(a) T.,t + RAMMA /AMM.//la)) (0) d, + all o(a), (8)
where
0n,t (0) 4; aa)) DTTr.
+ R2 RAMMA RMIMA + aB - (0, t. aal 0.r,
In App. we derive this analytic UCB by partial optimisation of the Lagrangian dual function. Using strong duality, one show that the analytic UCB minimised with respect to is equal to UCBe, (a). Due to the closed-form expression of the analytic UCB in (8) its gradient with respect to can be computed using standard automatic differentiation packages.
6.4
Choosing the Mixture Distributions
Both of our algorithms require to choose mixture distributions P. -2,:N((pp (N,,,, T,). The mixture distributions play role similar to the priors used in the PAC-Bayes (Shawe- Taylor & Williamson McAllesteri 1998, Guedj] 2019: Alquier (02T) and luckiness [
1997
frame-
works. Our confidence sequences and regret bounds are valid for any sequence of adaptive mixture distributions, but (as seen in Eq. 55) if better/worse mixture distributions are chosen, then our confidence sequences will get smaller/bigger and our regret guarantees will get tighter/looser.
Here, describe some sensible choices for the mixture distributions. In order for a sequence of Gaussian mixture distributions (N(,,, T,) t E N) to be sequence of adaptive mixture distributions (as defined in S..tion(5.I). we require: (a) μt and T. can only depend on aj ....... ag and rı. ... rt-1; (b) the first t elements of μ, must be equal to 1 (c) the upper left t - 1 x t block of T must be T, 1 (d) T, must be positive bemi-)Jefinite These conditions are all satisfied if we use mean vector μ,, and covariance matrix T, of the form
a(a1. k(a1, 0z) k(az, a1)
k(a1, at)
k(az,
k(az, ai)
14 = [m(ma)) m(a))........)............. m(a.). T.
(9)
:
a(a),
k(ar,
a(a

---

where m : AA + IR is mean function and l A x A - IR is positive-definite kemne function. For the linear bandit problem. it natural to use a linear mean function m(a) Φ(a) 0, and linear kernel function kaa a') o(a) (oo(a') (where Eo symmetric and positive-definite) since the resulting mixture distribution assigns non-zero probability only to those vectors of function values f, that could have been generated by linear reward function. By direct computation, the Gaussian mixture distribution with this m and k and with μr and T3 as in (9), is P. = NN( D Do When 0u 0 and Eu 1, we recover what we call the standard mixture distributions Pt (0, 4, ).
Choosing T. = 2, Lo has the additional benefit that it allows for cheaper computation of the radius RMM, In App. F we show that one (only) has to compute the inverse and determinant of a d x d matrix instead of the inverse and determinant of the t x t matrix 1 + T T//o². Finally, we remark that the requirement that (N Tt]lt j N) is an adaptive sequence of mixture distributions allows for "more adaptive" choices of μa, and T,, In E.2 we describe and investigate method for updating b, and Te each round / based on previously observed actions and rewards.
E.2
Regret Bounds
In this section, we establish cumulative regret bounds for our CMM-UCB and AMM-UCB algorithms. First, we state a data-dependent regret bound that illustrates how the radius the analytic UCB from Sec. 6.33 influences the regret of both algorithms. Then, prove a data-independent regret bound which illustrates the worst-case growth rate of the cumulative regret, with explicit dependence on the feature vector dimension d and the number of rounds T. We begin by stating the assumptions (which are standard) under which our regret bounds hold.
Assumption 7.1 SSub-Gaussian noise). Let H, denote (the o-algebra generated by) (01, r....., az, r2, d.+1). Each noise variable is conditionally zero-mean and o-sub- which means
E (x [H-11 = 0, and AA IR, E [lexp(Ae,) (H,, S exp(X"o²/2) (xxx((/)))))))
Assumption 7.2 (Bounded parameter vector). For some 0, |0 S B.
Assumption 7.3 (Bounded feature vectors). For some 0, [|((a)) < L for all A.
Assumption 7.4 (Bounded expected reward). For some C 0, (()) 0* E C- for all a E A.
We remark that to run our algorithms and evaluate the data lata-dependent regret bound in Thm. 7.5 we only need know (upper bounds on) the sub-Gaussian parameter a and the norm bound B. Assumption 7.2 and Assumption 7.3 together imply that Assumption 7.4 must hold with C < L.B. We nevertheless state it as a separate assumption because this leaves open the possibility that a better (than LB) value for C' is known.
7.1 Data-Dependee Regret Bounds
Several authors DDan et al., 2008 Abbasi- Yadkori al. 2011 Russo & Van Roy 2013) have shown that the cumulative regret of UCB algorithm can be upper bounded by the sum of the widths of the confidence sets or confidence bounds that uses. The width of confidence set θ at the action is the difference between the corresponding UCB and the LCB at a (i.e., maxøee. (ø(() [)
mingge, (0(a) 0}). )) In App. CMM-UCB algorithm, then
D.I. we show that if a1 02 ....... ar are the actions selected by our
A((a)) max (p(ar) min (á(a:) BE
(10)
BEB,
This gives a data-dependent cumulative regret bound for CMM-UCB. AMM-UCB has a similar data-dependent cumulative regret bound. In App. D.I. show that if a1 a2,.... ... ar are the actions selected by our AMM-UCB algorithm, then
T
T AUCBe, (0t) ALCBe,,,a,
A(a)) Σ
(1))
1=1
7

---

where AUCBe, (a) is the sight-hand-sie of (8) and ALCBe, (a) is the equivalent analytic LCB. Since, the analytic UCB/LCB an upper/lower bound on the numerical UCB/LCB, the bound in Equation (1) also holds for the actions selected by CMM-UCB. By substituting in the expressions for the analytic UCB/I.Css, we obtain the following data-dependent cumulative regret bound for CMM-UCB and AMM-UCB.
Theorem 7.5. Suppose that assumptions 7.1 7.2 hold. For any adaptive sequence of mixture distributions P. = ( T.), any 8 E (0, 1), any > 0 and all T 1, with probability at least 1 8, the cumulative regret of both CMM-UCB and AMM-UCB is bounded by
AIT 2AAM.L11 00-1 + aal) p(ar).
A proof is given in App. D. This regret bound tells us that if we choose an adaptive sequence of mixture distributions P. N (H Tr), such that the radii RAMM, are small, then we can expect to have small cumulative regret.
7.2 Data-Independent Regret Bounds
We now state data-indepen intteinndeendent cumulative regret bound for the special case when the adaptive sequence of mixture distributions P. (0, cb, ), and a o²/c. These mixture distributions are scaled versions of the standard mixture distributions described in Sec. 6.4
Theorem 7.6. Suppose that assumptions 7.7 7.4 hold. for any O. the sequence of mixture
distributions is P. = (0,, D ), then for all a 2 with probability at least 8, the cumulative
regret of both CMM-UCB and AMM-U MCB (with o² /c) is bounded by
cL'T o2d
B²
1
cL?T o2d
AET 1 max
C, dl 1+
+222
dI'n 1+
vin
< ((dVTIn(T)).
Proof sketch. Choosing P. (O,,,,0,,,,, 2b, and a o²/c means that the two quadratic terms in RAMM: cancel out. We then find data-independent upper bound for the log det term. Following
is upper bounded using an elliptical potential lemma. The result is the data- lata-independent regret bound in the statement of the theorem.
Abbasi- Yadkori al. (2011). 1), the sum of the norms / á((a)) ( 9
a +
we give proof of this special case. In addition, we also treat more general case when the sequence mixture distributions P. N (1000000.o.. (b and a is any positive number. Using Eq. (5) with μ, = 2,0, and T. of fb, 2 one can interpret Oo as a guess for 0* and og as a guess for the distance between the reward vector r; and the prediction 2.00-
In App. D.2
Focusing the dependence d and T, this regret bound (and the more general one in App. D.2, at most Odd/TIn(T)), which matches OFUL and is minimax optimal up to the In(T) factor. If (upper bounds on) o², B, I. and C² are known, then we can evaluate this cumulative regret bound before running the algorithm.
8 Experiments
In all our experiments, we 5 0.01. When using our analytic UCBs (Thm. 6. we always choose o² Unless stated otherwise, we use the standard mixture distributions P. (00, Φ

---

Scaling With
Scaling With
10
ORUL
2.0
Figure 2: Average confidence bound width for different data set sizes T and feature dimensions d.
8.1 Upper and Lower Confidence Bounds
Compared Methods. We evaluate the following upper/lower confidence bounds: (a) CMM-UCB:
our numerical UCBs/LCBs from Sect. 6.2; (b) AMM-UCB: our analytic UCBs/LCBs from Thm. 6.1
(c) OFUL: the UCBs/LCBs used by the OFUL algorithm (Abbasi- Yadkori et al. 201T); ; (d) Bayes: a Bayesian credible interval constructed from the Bayesian posterior for linear regression with Gaussian prior and likelihood (see App. E. for details).
Experimental Setup. We conduct experiments on randomly generated linear functions the form f(x) (xx) 0", with inputs a IRdx and 0 RRd the latter drawn from standard Gaussian distribution and if necessary scaled down to ||0* || < 10 =; B. For the feature map Ø Rdx + Rd we use Random Fourier Features (ef. Algorithm of (Rahimi & Recht 2007)). We investigate the properties of upper and lower confidence bounds constructed from random data sets {(æ;, ye) ) where y/: = ( + tee (O,, o²) and o 0.1.
Jr-
0*
UCB/LCB Tightness. Fig. shows the data {(x;, yc) 9t) and the UCBs/LCBs of CMM-UCB, AMM-UCB and OFUL for randomly generated linear function with dx 1 and d 20. In this example, the confidence bounds of CMM-UCB are slightly tighter than those of AMM- UCB, which are considerably tighter than those of OFUL. Next, we investigate the tightness of confidence bounds for functions with higher dimensional inputs (dx 10), a range of data set sizes (T E {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000)) and range feature vector dimensions (d E (1, 5, 10, 20, 50, 100)). For each T and d, we sample a random feature map á and weight vector 0 of appropriate size. Then,
sample random training data ((z,, vt) )²=1 and random test points { 100 where Vg and x/ are drawn uniformly from the dx-dimeesional unit hypercube. Finally, we use the training data construct confidence bounds with each method and calculate the average width (UCB minus LCB) at the test points. Fig. shows the average width of the CMM-UCB, AMM-UCB and OFUL confidence bounds with: d 10 and varying T (left), and T 100 and varying d (right). We observe the same pattern at every and T: CMM-UCB produces the tightest confidence bounds followed by AMM-UCB and then OFUL.
Effect of the Mixture Distributions. Fig. in App. E. shows the confidence bounds of CMM- UCB and a Bayesian credible interval for different choices of the mixture distributions/prior Pt. For a well-specified prior, either uninformative or informative, the Bayesian credible interval is slightly tighter than the confidence bounds of CMM-UCB, For a misspecified prior, the confidence bounds of CMM-UCB become looser whereas the Bayesian credible interval becomes wrong (not containing the ground-truthe function). Here, misspecification refers solely to Bayesian prior misspecification. In Figs. 5] in App. E.2 we show that adaptive choices of the mixture distributions P. can lead to smaller confidence bounds and smaller cumulative regret in linear bandit problems.
8.2 Linear Bandits
Compared Methods. We compare: (a) CMM-UCB: cf. Sec. 6.2 (b) AMM-UCB: cf. Sec. 6.3 (c)
OFUL: the OFUL algorithm (Abbasi- AAbbasi-Yadkori et al. 2011 1) with regularisation parameter X a ²²:
(d) IDS: the frequentist Information Directed Sampling (IDS) algorithm (Kirschner & Krause 2018
specifically the DIDS-F version; (e) Freq-TS: Thompson Sampling with posterior covariance inflation (Agrawal & Goyal 2013), which we call Frequentist Thompson Sampling.

---

Table 1: Average test accuracy and maximum test accuracy of our UCB algorithms and OFUL, IDS and Freq-TSS in the SVM hyperparameter tuning problems after T 500 rounds (100 repetitions).
Raisin
Maternal
Banknotes
Mean Acc
Max Acc
Mean Acc
Max Acc
Mean Acc
Max Acc
CMM-UCB (Ours)
0,818 = 0.018
0.893 + 0.019
0.744 + 0.020
0.829
0.023
0.954 = 0.005
1,000 +: 0.000
AMM-UCB (Ours)
0,800 + 0.017
0.892 0.020
0.736 + 0.020
0.829
0.023
0.948 = 0.005
1.000 0.000
OFUL
0.764 0.019
0.891 0.019
0.722 0.019
0.827
0.022
0,929 = 0.006
1.000 0.000
IDS
0.706 = 0.048
0.891 + 0.020
0.714 0.019
0.827
0.024
0.926 = 0.007
1.000 + 0.000
Froq-TS
0.527 = 0.022
0.884 + 0.019
0.616 + 0.018
0.823
0.022
0.808 = 0.012
1,000 + 0.000
Raisin
Maternal
Bankmotes
0.75
0.55
Not. AC000000
0.65
9.70
0.83
3.90
0.02
0.6
0.70
Pre
0.50
0.65
0.15
0.00
102
250
103
4:00
102
230
100
4.00
100
230
100
4.00
Figure 3: The smoothed per-round expected reward (test accuracy) of our UCB algorithms compared with OFUL, IDS and Freq-TS in the SVM hyperparameter tuning experiments three datasets. Shown is the mean reward over 100 runs of each experiment, after Gaussian kernel smoothing.
Experimental Setup. We investigate whether our tighter upper confidence bounds translate to better UCB algorithms. We use each linear bandit algorithm to optimise the hyperparameters of kernel Support Vector Machine (SVM) for three classification data sets from the UCI Machine Learning Repository (Dua & Graff) 2017): Raisin (Cinar et al. 2020). Maternal (Ahmed et al. 2020). and Banknotes. The expected reward function fa( is the average test set accuracy of kerne SVM trained using an ARD RBF kernel with hyperparameters a = (C, with C the regularisation and y the length-scales. The observed reward is the validation set accuracy at ag. The feature map 6 is neural network layer with 20 outputs and random weights. We choose o = 0.05 for the sub-Gaussian parameter and B 10, i.c. we assume that (a) x ((a) " for some ||0 I|2 - 10.
Results. Fig- compares the average test accuracy (expected reward) obtained by each bandit algorithm for each data set and at each round = ...... 500. Our CMM-UCB and AMM-UCB methods outperform all other methods. From the reward curves of CMM-UCB, AMM-UCB and OFUL, we observe that CMM-UCB outperforms AMM-UUB, which outperforms OFUL. Therefore, we can conclude that our tighter confidence bounds (compared OFUL's) lead to UCB algorithms with improved performance.
Conclusion
In this paper, developed novel tail bound for adaptive martingale mixtures and showed that it can be used to construct tighter confidence sequences for linear bandits. We proved that our CMM-UCP and AMM-UCB algorithms match the worst-case cumulative regret of OFUL, and we found that our tighter confidence sequences allowed CMM-UCB and AMM-UCB to achieve greater average and maximum reward in several hyperparameter tuning problems.
limitation of our algorithms is that they assume a linear expected reward function, which may not always be realistic assumption for real-world bandit problems. Our ceneral-purpons tail bound in Thm. 5. already allows one to derive confidence sequences for non-linear reward functions by simply choosing (fi) (fe f" (a,))e, where f" is the non-linear reward function. In the case where f lies in a reproducing kernel Hilbert space, the corresponding UCB is still the solution of convex program. The main challenge in this setting is that the regret bound must now depend on quantities like the effective dimension or the maximum information gain of the kernel, since the dimension d of the feature vectors is d oo for interesting kernels.
We believe that further investigation into the degree to which adaptive mixture distributions can lead to improved performance and regret bounds (see App. E.2) is another exciting topic for future work.
10

---

References
Abbasi-Yadkori, Y. Online learning for linearly parametrized control problems. PhD thesis, Univer- sity of Alberta, 2012.
Abhasi- Yadkori, Y., Antos, A., and Szepesvári, C. Forced-exploration based algorithms for playing in stochastic linear bandits. In COLT Workshop on On-line Learning with Limited Feedback, volume 92, pp. 236, 2009.
Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Agrawal, A., Verschueren, R., Diamond, S., and Boyd. S. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019.
Agrawal, S. and Goyal, N. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pp. 127-135. PMLR, 2013.
Ahmed, M., Kashem, M. A., Rahman, M., and Khatun, S. Review and analysis of risk factor of maternal health in remote area using the internet of things (loT), In InECCE2019: Proceedings of the 5th International Conference on Electrical, Control & Computer Engineering, Kuantan, Pahang, Malaysia, 29th July 2019, pp. 357-365. Springer, 2020.
Alquier, P. User-friendly introduction to PAC-Bayes bounds, 2021. URL https:///axxii org abs abs/2110..111 11216
Auer, P. Using confidence bounds for exploitation-expllrrtion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
Boyd, S. and Vandenberghe, L. Convex optimization. Cambridge university press, 2004.
Camilleri, R., Jamieson, K., and Katz-Samuels, J. High-dimensional experimental design and kernel bandits. In International Conference on Machine Learning, pp. 1227-1237. PMLR, 2021.
Chowdhury, S. R. and Gopalan. A. On kernelized aulti-armed bandits. In International Conference Machine Learming, pp. 844-853. PMLR, 2017.
Chu, W., Li, L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-2 208-214. JMLR Workshop and Conference Proceedings, 2011.
Chugg. B., Wang. H., and Ramdas, A. A unified recipe for deriving (time- uniee- PAC-Bayes bounds. arXiv preprint arXiv:2302.0344 034222 2023.
Cinar, I., Koklu, M., and Tasdemir, Classification of raisin grains using machine vision and artificial intelligence methods. Gazi Mühendislik Bilimleri Dergisi, 6(3):200-209, 2020.
Cohen, M. C., Lobel, I., and Paes Leme, R. Feature-based dynamic pricing. Management Science, 66(11):4921-4943 2020.
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In COLT, pp. 356-366, 2008
Darling, D. and Robbins, H. Some further remarks on inequalities for sample sums. Proceedings of the National Academy of Sciences, 17554:1175-1182. 1968.
de la Peña, V. H., Klass, M. and Leung Lai, T. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. Annaly of Probability, 32:1902-1933, 2004.
de Peña, H., Lai, T. L., and Shao, Q.-M. Self-normalized processex: Limit theory and Statistical Applications. Springer, 2009.

---

Diamond, S. and Boyd, S. CVXPY: A Python-embedder modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Donsker, M. D. and Varadhan, S. S. Asymptotic evaluation of certain Markov process expectations for large time-ii. ii.. Communications on pure and applied Mathematics, 29(4):389-461, 1976.
Dua, D. and Graff, C. UCI machine learning repository, 2017. URL http:://rrrchiie.icc.. edu/ml
Durand, A., Maillard, O.-A., and Pineau, Streaming kernel regression with provably adaptive mean,
variance, and regularization. The Journal of Machine Learning Research, 19(1):650-666 683, 2018.
Grünwald, P. D. The minimum description length principle. MIT press, 2007.
Grünwald, D. The e-posterior. Philosophical Transactions of the Royal Society A, 381 (2247)) 20220146, 2023.
Guedj, B. A primer PAC-Bayesian learning. In Proceedings of the second congress of the French Mathematical Society, volume 33, 2019. httpttts::/ http:///aa.iiv....aaaa////////// wwwg/b/////.......///.
Haddouche, M. and Guedj, B. Online PAC-Bayes learning. In Advances in Neural Information Processing Systems, volume 35. pp. 25725-25735 Curran Associates, Inc., 2022.
Haddouche, M. and Guedj, B. PAC-Bayes generalisation bounds for heavy-tailed losses through supermartingales. Transactions on Machine Learning Research (TMLR), 2023. ISSN 2835-888 8856. doi: 10. 10.46550/ARXXV.21000005
URL http:tttts:::eereeeeeee http://www.......oo.oo///o//t/oo
Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17, 2020.
Kaufmann, E. and Koolen, W. M. Mixture martingales revisited with applications to sequential tests and confidence intervals. The Journal of Machine Learning Research, 22(1):1 1183, 2021.
Kirschner, J. and Krause, A. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pp. 358-384- PMLR, 2018.
Lai, T. L. On confidence sequences. The Annals of Statistics, pp. 265-280, 1976.
Li, L.,, Chu, W., Langford, J., and Schapire, R. F. A contextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Li, and Scarlett. J. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics, pp. 92-107. PMLR, 2022.
McAllester, D. A. Some PAC-Bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pp. 230-234, 1998.
Molchanov, S. Theory of random sets, volume 19. Springer, 2005.
Neiswanger, W. and Ramdas, A. Uncertainty quantification using martingales for misspecified Gaussian processes. In Algorithmic Learning Theory, pp. 963-982, PMLR, 2021.
Petersen, K. B., Pedersen, M. S., al. The matrix cookbook. Technical University of Denmark, 7 (15), 2008
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Robbins, H. Statistical methods related to the law the iterated logarithm. The Annals of Mathemat- ical Statistics, 1555:1397-1449, 1970.
Robbins, and Siegmund, Boundary crossing probabilities for the Wiener process and sample sums. The Annals of Mathematical Statistics, pp. 1410-1429, 1970.
12

---

Rusmevichientong, P. and Tsitsiklis, J. N. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-441, 411, 2010.
Russo, D. and Van Roy, B. Eluder dimension and the sample complexity optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Salgia, S., Vakili, S., and Zhao, Q- A domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance. Advances in Neural Information Processing Systems, 34: 28836 28837,28887, 2021.
Shawe-Taylor, J. and Williamson, R. C. A PAC analysis of Bayesian estimator, In Proceedings of the tenth anmual conference on Computational learning theory, pp. 2-9, 1997.
Sherman. J. and Morrison, W. J. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. The Annals of Mathematical Statistics, 21(1):124-277, 1950.
Srinivas, N., Krause, A., Kakade, S., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. International Conference on Machine Learning (ICML), 2010.
Valko, M., Korda, N., Munos, R., Flaounas, I., and Cristianini, N. Finite-Time Analysis of Kernelised Contextual Bandits. In Uncertainty in Artificial Intelligence, 2013.
Ville, J. Etude critique de notion de collectif. Bull. Amer. Math. Soc, 45:11): 1939.
13

---

A Proof of the General-Purpose Tail Bound for Adaptive Martingale Mixtures
A.1 Verifying Martingale Properties
First, we recall the definition of (M A, N) in Eq. (3). We are given a filtration (Hylt N). sequence of adapted random functions (7+ IR Rli E N), and sequence of predictable random variables (Aele E N).
filtration an increasing sequence of o-algebras Ho C Hi C H2 H..... Each ø-algebra He represents the information available time t. (Z, + Rt E N) being a sequence adapted (to the filtration (Helt E N)) functions means that, when conditioned on Hr. Ze is no longer random. (Ae]t N) being sequence predictable random variables means that, when conditioned Hi-1, X is no longer random.
For sequence of real numbers (fe : N), define
Milf., Ax) exp
AaZa(ff)) -
where (e(fe, is the conditional cumulant generating function
t (fe, In (B (f))))))
Lemma A.1. For any sequence of real numbers (Jelt E N), (M.(S Ar) N) is martingale and E[M((F f. Ac)] for all E N.
Proof. For l 1, we have
(IM
= E. (()) (1
= E|eep({12(((f)))94] (e0p)))))///e/(((((((///a// cxp(e)((f..A)))
Using the tower rule of conditional expectation, also have
E[Mi A:)] (f
Now, we verify the martingale property. For any / 2 2, we have
Σ AaZz(ff)) Sha (fas Me-1
E (M, H4-1
exp
AeZa(fe) - (b((fe Texp (Ne (.(fe. [H-11]
exp
exp
Ze( - -balkk Av))
1f-
Using the tower rule again, we have for any t 2 2
E[Ma(S,, Ax)] = [E A. H.. = Ef
Therefore, we have
EJM(f 1: A,) = -f -... EMM (f) =1.
14

---

Lemma A.2. For any adaptive sequence of mixture distributions (Pi N), DPP.-P[[M..ff. A,]][t N) is a martingale and EIE f [M A+)]l f all E N.
Proof. For any Ł 2 1, since Mffr. Xx) is non-negative and P. is Ha-1-measurable, Tonelli's theorem implies
A:) - [R[M > H4-1]]
The requirement that the distributions Pt, .2.... have coinciding marginals, i.e. P Pt-1(f means that for all 2 2
Bp S.M if (f A--1)] P A.-1)..
Using these two results, and the fact that (Mr(F,. At] E N) is a martingale for any sequence (filt E N), we now verify that the martingale mixture (B,, (M, Ar)][t N) is martingale with expected value 1. For t = 1, we have
[E, ( A.]HHH
~
-3 Pi [1]
1.
Using the tower rule before, this also means that E [Es [M1 1:: x1)]] 1. For any 2 we have
E (RR A:)]: = PR [E[ xx)(H+-11)
= =ES.rP [M (f 1--1::155 x11
= -Ee M 1f ;-10 x (f:-1)
Using the tower rule one more time, we have for any 2 2
[M A.)I] IIE|E,, (M. Ar) - (M- dr-I)]]
Therefore, have
E DES A+]]
A.)]] =
A.2 Proof of Theorem
To prove Thm. 5.1 we use Ville's inequality for non-negative supermartingales (Ville 1939). which can be thought of as a time-uniform version of Markov's inequality. Instead of the martingale property [[MM,HH,-11
M,-1. supermartingale satisfies E[M,|H,,-l. < Mr-1, which means that any martingale is also supermartingale. Therefore, Ville's inequality for non-negative supermartingales also holds for the non-negative martingale in Lemma A.2
Lemma A.3 (Ville's inequality for nog-negative supermartingales Ville 1939)). Ler (M.lt E N) be a non non-negative supermartingale with respect the filtration (Hife E N). which satisfies Mo
For any å E (0, 1), it holds with probability at least 6:
1: M₁ 2 1/65.
Proof of Thm. 5.1 We choose arbitrary 8 1). From Lemma A.2 for any adaptive se- quence of mixture distributions (P.lt N), (Er,p)) [MA(fr x,]][K E N) is a martingale and EIR [M At)]] 1. In addition, (Es,-r, [M (f(r X.]][e N) is clearly non-negative.
Therefore, using Lemma A.3 with probability at least
VI 2 1, ES [M Ax) < 1/8.
Taking the logarithm of both sides yields the statement of Thm. 5.1
15

---

B Closed-Form Gaussian Integration
Here, we calculate the integral in the inequality (see beginning of Sec. 5.2
E
exp
Aa(f -
-((x) )(ax) - a²
AE - o(ax) T
1
fo (r,N
2
(12)
First, we rearrange the integrand into a more convenient form. For every k, using 1': c(ax) 0- tek. we have
(Ø(ax)" 0- - -rk)² 2 (Jk- -rk)² = (Jx ((a)) 0 - =x,²
c (fk x(an) T022 2(fx (((x)) 00))ex
(((xx)(()ea) oz
2(1 x(ax) (0')(re ) (fk - x(ax) T
Therefore, have that
0²
Ap(fx o(ax) )(ax) (r)) (b(x-((a))) T0") 00²)
>Z o(ax) ( T0"12
2
A A (d(x)) T -rx)² rx)²
de (fr rk)²
1
(ds 0² 2b) ((ax) TO)
2
Equation 12 can now be re-written as
A (ø(as) 2
1
E (o
cxp
( 0 rr))²
(fk - -xx)²+ 2
2 (Ax - -f2 - {(xx)
Toy2
$ 8
(13)
In the special case where A = 1/0², we have d o2 O, which means that 5 xf
((ax) T disappears. In addition, (b(a)) T rk)2 does not depend fk. it can be moved outside the integral.
B.1 General At
Let Ar be the f t diagonal matrix with diagonal elements Å1 Ag...., the logarithm of both sides, rearranging terms and then writing everything in matrix notation, arrive at
......,,e de Starting from [3 taking
(0.00
-r)A.(F.0' -r)) S 21n(1/))
(14)
(5, (f,- - rr) (T)T - r.)++ + - T,0') (A,-o2 o²A,) (f, - 8,0%) 1)
21n
E (.
exp
The expected value inside the logarithm can be re-written
/ exp
( 1 (s. - m1) A)) TT (f. (1) 1 ( - Aclf. rr) (15)
del (Tl)
1 + 2 (f. T,0') (A, - -2A (f. 2, df. )af
We will calculate the integral by "completing the square", i.e. rewriting the exponent in the form
(f, b) A(f. b) c, recover the integral of Gaussian density function. For symmetric
matrix A, we have
1 (f.-
1
TTT(( A(f. b) +c= 1 IT AF. +b Af. 2
1 bJ Ab +c
A
2
16

---

We also have
1
(
2 (f: - m4) Ti (f: T
m²) = 2 Ti' f, - Mi TT f. 2 Ti Me
2
1
(f+ -
2
ri) Ac(f: - -r) = 2
Arf. + Arf. -- A
1 2 (S: 2,00)) (A, o² A²) (f. (.--.00) // -g) S: 0* 0, (A. - 0² (2)))) S.
1
+ 0 o/ (A: - o² A7) 2,0"
2
We now equate coefficients to find A. b and c. We find that A is
A=T, + to
Note that A is symmetric. We find that b is
b A T. +
- TT (A, oPAi)
TTT
Ab T7 14 + ArT - -A,, 0² 22A)) 200"
(T + 2²))) -1 "(T,' + Arr: (Ac (A 0,0%).
Finally, we find that c is
1
c= b Ab-
T 1
14 2 n. A.r + 0 :. - d²A7) (A2-d2A?) 0,0" 0².7
2 2 14
2
(Tr u4 + Arri - -A, - - 8,0') "TT²' + +o² -1 (TT pr + ArT - (A. - o²²2)) 0,00)
1
1 1. A,r, + 2
1 0 क. (Ai oZA))) 0,0"
2 24 T, 14
2"
Now, we can rewrite and calculate the integral in (15) as
exp(c)
-b) / exp (-) A(S, b) ds.
exp(c) del (A 1
(27))de((T))
v (2 dTt(
= exp(c)) det(A-t)
det(TT)
Substituting this into 14 we obtain the constraint
det(A )1 det(T,)
(0.0- - -r)) A, - r,) < -2nn
exp(e)
+ +21m(110)
-20 + In (det + (m166
- -(T77p + A.r: - - (M.-opA33 0,0') (T-2+0023) -1 (T7 14, + Arr - (A, (A,-o7 o2 0,0") u4, T p4 r. Arr: 0¹ T -T. (A. o² A²) :.0- + In (det(1 + 0² A(T.)) + (1/8))
Note that 0* appears on both the left-hand-side and right-hand-side of this inequality. However, when A, A²A² is the zero matrix (e.g. when d = 1/0²), all the 0" ddeeenddentt terms on the sidd disappear.
B.2 The Special Case A, 1/0²
Starting from 13 choosing de = 1/0", taking the logarithm of both sides and then rearranging terms, we arrive at
| -ral2 < -20 In
E (.NNTH.
exp
(-20 (S. (-22 r.) r.)
20
(0..-..))]] 20 ln(1))). (J. (r))
(16)
17

---

For any x covariance matrix T, let (T)) denote the normalising constant of a Gaussian distribution with covariance T, so
((T) (2 (T).
For any t-dimensional vectors a and μ., and any X t covariance matrix T, let p(æ) μu, T)) denote the density function of a Gaussian distribution with mean μ and covariance T, evaluated at æ. This means that
p(al T)
1 Z(T) exp
(-
(1) T (0)
will use the product of Gaussians trick from (Petersen et al. 2008) (Section 8.1.8, Equation 371), which states
p Σn pb E2) - p( E1 + E2)p(al Ec),
(17)
where
Ne = (Ei + Σ3 11 [E) 11 + Dz 12);
E. = + --²1)
We have that
1 (fi- (ri - (.) (ff
1
f (P,
exp
20
E S.NN(H,T.)
= -((d'1)
JR'
Z(o21)
.. T Eddds
=((o 1 02
1el(o²1)
exp - (m)) T
- + -re))
det + x21)
Substituting this into (16). the constraint becomes
10,0- -r:l2 s o² (2, r.) (TT + +01+ ((4) -ri)-20- 320- In (V del + +021)
det(o²1)
+ 20 In
= (m -m (1+ Tí (14 r1) + Inde
|+ Tr |
+ +20
5
C Computing Upper Confidence Bounds
First, we state and prove some useful lemmas.
Lemma C.1. For any a > 0
(0,0 (0.0-r)) (0:0-r:)) e- = (Φ. Tb a1) (0 -o..) ) RAMM.
(0-0.))
where REan, is the squared radius quantity from Cor. 5.2 and
0 ( p. + aa))
r.r.,
RAMMLE RAMM. aB² -r. r
r. t. (0. t. + +al) -1 T..r..
Proof. For any symmetric matrix A, we have
(0 - A(e b) + - T 2bT A0 + b Ab +
We also have
(2.0-r.) (
(2,0-r:)+a0 (2000-:)(0000-))))) 0- 2-RM - T (Φ, d. +al) 0 0r2r 2.0+r. r r -
18

---

We can now find A. b and e by equating coefficients. We find that
A $ t2 al,
which is symmetric matrix. We have
b A ri t2
Ab 1. rr
b (0, t2 +a1) -1
8, r1 -0a.t
Finally, we have
c RIIME aB2
+
rre r.
bT Ab
BAMMA aB + + p4 r1 or (0, 0. + +al) =
= -RAMM,
Therefore, we have shown that
(0.0-r,) ( +a:00-r)++0066 RaM.
=(0-0a,t) 1 (0, tb + aa) (0 (0-0a.)) R2 RAMM,
Lemma C.2. For any symmetric, positive-defiiite matrix A E Raxd, any vectors a, b E Rd any R > O, and any 1l
a 0 + 17 b) -TT b) -R²) a T A R
BERd
4n
Proof. Let
f(0) a o ((0 A( b) b
R²²
The gradient and Hessian of f are
0
00 (0) + A0 b):
00² (0) 2nAA
Since A is positive-definite and r7 solution 0" of ag (() = must be a maximiser of f(). There is unique solution, which is
8² f() is negative-definite for all 0 Rd. Therefore, any
0" = A - a.
2n
The maximum is
1 T A-1 1/R2.
1(0") = a
a
4nj
Lemma C.3. For any symmetric, positive-defmitt mairix A E Bdxd any vectors a, b E Rd, and any R 0,
{ TT TTA A n7R² 1-,2- bb RV a a
min ncO
4n
Proof. Let
g(n) = a Tb
a T A -1 T/R22
4n
19

---

The first and second derivatives of g are
d
1 A a R²,
d? dp2
1 2n1² a A a.
(()) drj
4xp
Since A is positive-definit, d dr g (7) = 0 must be minimiser of g(n). There is a unique (negative) solution, which is
d² g is positive for all v O. Therefore, any negative solution vf" of
1 --- A
7 =
2R
The minimum is
= = b + RV a A
C.1 Analytic UCBs
Here, we prove Theorem 6.1 which states that for all a > 0:
max {Ø(a) [o} I see,
+ RAMM. o(a)T (0) o, aa) Φ(a),
(18)
where
O., = (0, 0, + a1l) 8, rt:
R RMM.. aB² r,
r. re r, 4, (0, t. a1) -1 Φ, re.
O₂ is the confidence set at time t our confidence sequence from Cor. 5.2 and RMM, is the radius from Cor. 5.2 and Eq. (5). As well as proving this statement, we will also show that if θ has an interior point, then when the right-hand-side of (18) optimised with respect to a > 0, the inequality in (T8) becomes equality, i.e.
áaa) Oo,t + Rla (4T 2, + +al ola) (19) as0
max (o(a) min 0E8,
Proof of Thm. 6.1
We use weak Lagrangian duality to prove the upper bound and strong Lagrangian
duality to prove the second part. The convex optimisation problem maxøee, {Φ(() 0) can be stated
as
max
(aa)
s.t. (#,0 r.) ( rI) S R and θ B².
(20)
BER
Rewriting both constraints the form f(0) Σ 0, we can see that the Lagrangian for this problem is
L(O, m, 72) ((a) 0 m ( (T.0- r.) (T.0 r() R( 7/2 (oTe B²)
?h and 7/2 called the Lagrange multipliers. The Lagrange dual function (or just dual function) is g(m, 92)
max (T.(0, 7h, 72)
BERd
By weak duality, for any 71 72 S 0, the dual function is upper bound the solution of the primal problem in (20). i.e. for any Th. 72 I O
max (Ø(a) 0} g(m,))))
(21)
ece,
Alternatively, 21 can be verified by starting from the inequality d < L(O, mı 72) for all O E O,,7h < 0, and 7/2 < O. The challenge is to set the Lagrange multipliers such that the dual function has a closed-form expression while being as close as possible to its minimum value min 50 {9(12. n.)). We will now show that for any form solution, which is the right-hand-side of (18.. The Lagrangian, evaluated with the Lagrange multipliers 77 and am, is
0. minggo [g(n, an) has closed-
L(O, n1 om) = <(a) + (0..0- - -r) -8,0 re) a0 TT BAAM aB²)
20

---

Using Lemma C.1 the Lagrangian can be rewritten as
[(O, 7. om) <(a) (0- )..:) (0. a1) (0
-aa.)) (0-
RRAMs:)
Using Lemma C.2
the dual function evaluated 7) and an is
((()) T 0+ 17 (Oe 0a.e) (0, 21 + a1) (0 -o.)) RAMMI.)
g( am) max OER"
= ( a,t - 4n
δ(a)T (Ø. th + al) -1 o(a) - -n
Using Lemma C.3
have
1 Maaa) (2, 2, +al) 6(a) - -
min (g(n, om) = min 750
O(a) 0o,
6(a)
750
An
Φ(a) Ta, + RAMM. v(aT (0) 0 aal) v(a).
This concludes the proof of Theorem 6.1
To prove
we use strong duality. Clearly m2),. if we optimise the upper bound in (18)
mina >o minygo (g(1) an)) mi ( with respect to a, then we will recover the minimum the dual function. If strong duality holds, then the minimum of the dual function is equal to maXøge, {o(a) 0). Since maxøge. { {o(a) 0) is
convex optimisation problem, we can use Slater's condition to obtain a sufficient condition for strong duality hold. In particular, if O has an interior point, then strong duality holds, which means
max (o(a) 0) BEe,
min min {g(n, an))
a>0 v00
min a>0
((a) Da.t RAMM, p(a)T (0, t. + tal) o(a)}
One can follow the same steps, with few minor modifications, prove similar statement for lower confidence bounds. For all a >
min { To} Oo.: ó(a) (0. 4. + = s(a).
eee,
O, has an interior point, then
(o(a) max Φ(a) Oaa) ( (2) T, + +al) pla)).
min
OEO,
as0
C.2 OFUL VS AMM-UCB (and CMM-UCB)
We will now show that for any value of the parameter a, we can choose a sequence of Gaussian mixture distributions, such that the confidence bounds of AMM-UCB (and therefore also CMM-UCB) are always tighter than the confidence bounds of OFUL (Abbasi- Yadkori et al. 2011).
To do this, we will use the following lemma.
Lemma C.4. For any > 0, v E RC and M E RRtxd, we have
w JT- r M M TMM +1) MT = - (MMM*++ +1) v.
Proof. We start with the identity
M (MMM++7) (00-11--MM'1> +71) M.
21

---

By post-multiplying both sides with (M' M + +?1)²
-1
and pre-multiplying both sides with
(MM +71)
we obtain
(MM tx1) M = M (M
(22)
Now, using (2), have
TTo
0 M
M MMMME M M +
M w= u==voo vT - - (MM +11) MM3
= T (MM² +11) (MM² + +
oov o o + (MM ++1)²
= T 1 (MMT -1)
With r, and M D. we obtain
r, r: r, e (9, 4. + >1) -1 D. r. =r] L (000 + +1) re.
We will also use the fact that, due to the Weinstein Weinstein-Aronszajnn identity, for any 7 > 0 de d, + 1) = det(> + +1..
(23)
For any a (in (Abbasi- Yadkori et al. 2011), what we call a is called A), the OFUL UCB states that
S (o(a) Oa. + ROPUL. ola) 2, o(a),
where ROFUL, =0 1 In det (.0T00 De + (0)00++)) 21m(1/6) + VaB.
For any 0 and any 8 E (0, 1]. this statement holds with probability at least 1 - 6 for all t > 0 and all a E A. By comparison, our AMM-UCB holds uniformly over Z 0, all a E A and all 0 (i.e. we could optimise the AMM-UCB with respect in data-dependent manner, which would yield our CMM-UCB).
Notice that for any history 01. Q2 ..... and any > 0, the OFUL UCB is the same as our AMM-UCB, except that our AMM radius quantity RAMM, replaced with RoruL, The same is true for the LCBs of OFUL and AMM-UCB (with the same RoruL.)) so we will only focus on the UCBs. We will now show that for any history d1, 71, 02, r2, and any a > O, we can chose sequence of Gaussian mixture distributions such that AAMM, ROFUL, This means that the UCBs our CMM-UCB and AMM-UCB algorithms are never worse than the OFUL UCB.
Without loss of generality, suppose we choose a = o² for some > OFUL radius
0. With this choice, the
ROFUL. = a (Vin (e= 8. TT ob + 11) + 2m101 +
Vo
For any a > 0 and a Gaussian mixture distribution P. = N(4, T(), the squared AMM-UCB radius
RAMMA RhAM, + aB² r. TTTr + T, (0) 2. +al) DTTr.
-m,-0 rr)
[1
T:
Tí - (n) o del [1
) 20 In
Φ2
+ + -T, + r, T
p ob o. + a1)
TTTr. rt-
22

---

For AMM-UCB, we will use a = 0²/c and the scaled standard mixture distributions P. NO cD, foreach i. With these choices, and using Lemma C.4 and radius is
(3 the squared AMM-UCB
④ R RAMM, = 22000 +1) - rr + tr, Dr
D2 +
L Tt
(24)
In (del del T + +1)) + 20022 In
o²
+
0² In det (5 2ù 1)) + 2ln
1
B
i
Using the basic inequality va tbs va + for a, b 2 0, we have
RAMME = / In (det (f क. tb + +1)) + 2ln
1
B²
8
S a (v In (dot ( ( T. 11) + 21n
1
B
+
02
vC
= ROFUL
Therefore, the confidence bounds of AMM-UCB, with 0²/c and Pt NoO, cb, are never looser than the confidence bounds of OFUL with an arbitrary a o²/c. Since In (det (g2 T th + 1)) + 2n (?) and B² B²/c are strictly positive, there is actually a strict inequality. This means that the AMM-UCB (and CMM-UCB) confidence bounds are always strictly tighter than the OFUL confidence bounds.
Note that P. N(, cb, ) is not necessarily the best choice for the mixture distribution. With better choice of the mixture distribution, e.g. a mixture distribution that is chosen using some prior knowledge about the expected reward function and/or refined using previously observed rewards, RAMM, will smaller and the gap between AMM-UCB and OFUL will be greater.
D Cumulative Regret Bounds
In this section, prove the cumulative regret bounds stated in Section We prove the data- dependent regret bound in Thm. [7.5] We also prove the data-indepea inttiinneeendent regret bound in Thm. 7.6 and another data-indeppnndet regret bound, which holds for more general choices of the mixture distributions and the a parameter.
For convenience, we use some more compact notation in this section. For symmetric positive semi-definite matrix A and vector æ, let
2 A = Vx Ax.
Before presenting the proof of the main results, we state some useful lemmas.
Lemma D.1 (Donsker- Varadhan Change of Measure (Donsker & Varadhan 1976)). For any set X, any measurable function h X + R. and any probability distribution P P(X) (i.e. any distribution on X),, such that [x-p(ch(2)] < co, we have
sup E [h(x)] m
(KL(111))] = in
((a)))
(25)
QEP(Z)
By rearranging 25 have
inf QEP(X)
-In E [Mxx)] D
M(x))
(26)
a
xwP
23

---

Lemma D.2 (Determinant- Trace Inequality (Abaasi- Yadkori et al. 2011 )) If assumption 7.3 holds
(i.e. [|ø(a)]l2 & L), then for any y
In (det (70, tb + 1)) < dln (1 xtT2/dd
(27)
The Determinant-Trace Inequality in Lemma 10 of (Abbasi-Yadie al. 2011) is stated in the form det 0 4, + +1)
11/74
(28)
Since det (70, t2 + 1) = det (0, 4. + (1/7) / del ((1/7)1), the statement in 27 follows from (28).
Lemma D.3. For any and any oo 0, define E, (, Φ.
o/2 1)
We have
o² (,2)) o²d (.) S odd.
Proof. Since E, is positive-definite, its trace is positive. Now
1
(r("[,,EE,) = rr
th
0
0
00
02tr
(0's
02 8
1
+ og
11
+
22
1
/1
1
+
02
o
o²
1
= o tr(2;)
00
< o²dd
Lemma D.4. For any > 0 and any do > O, the matrix E, ( 2. 4, + o/f 1) satisfies
tr(E,) S 0
Proof. Let {x) denote the eigenvalues of D. Since T d, is positive semi-definite, its eigenvalues real and non-negative. From the definition of eigenvalues, one verify that the 2
cigenvalues E; are 15t 1= Using this, we have
o²
d
tr(E.) Σ
%
0
9
Lemma D.5. Let e, denote the vector containing the first noise variables (so r, 02," ce). For
any a > 0, we have
(0.0- - r.) ( - -r:) - -r. + r. ( 4, + a1) 10 r, < 11 < 11 (ooT)++)1--
+ 2a ||0" [1 1 cell (o)))))-)))--
24

---

Proof.
Using rı = =,,0" Ee, we have
(0,0" - r0) - -r)) = 4 =Ga, ct:
and
T Py + Tg Po 9, a1) 1 r1 - +a) (0,00 +
+ (0,0" Et) ( 2 + al all (0,0" +
c.a 20" 1 0 8. 0 0 क. ( o a1) - 1 00
20 8. (0 -
al
0
0. + + 4,
+ 6,
- 20 20 D.
20"
4. ( +al) Et
E 2 2, + al) a
c. c 200"
(0, 4, +all 1 c, + c. (0, v. aa1 -1, cr.
Using the Cauchy-Schward inequality, we have (0) p +
10
a11-112 2, Eel = (0)
00 Eol( )ctal)-1 oo
Therefore
2a0' (0, 1, +
s 2a 1a|1001 10 0 10
and
(0,0" T
(4,0' -r)) -r. 1r (0 4. + aa1) - 1T,r S STSSeT e, e c
1 e, 2
(0, --tal)-1
2a |00 [T)o
10
(1] +1t)))- (0)) +1ta1)
| call - +a1))
2a |00 (0TT
| c;
Theorem D.6 (Self-Norman Serfa-eorml Bound for Vector- Martingales (Theorem of (Abbasi-Yadkori
ct al. ))) Let (Hult 2 0) be a filtration. Let (e 2 1) be a real-valued stochastic process such that is Ha-meaaurable and e, is conditionally o-sub- Sub--Gaussian for some O. Let (o(a,))t 1) be an valuul stochastic process such that Φ(az) is H4-1----asa H4-1-measurable. For any 5 E (0. 1] and any O, with probability least
1 <a eellin +.+01)-1 S o²²nn In det (_ T. (0. +1)) + 202
VI. 2 0,
Lemma D.7. For any symmetric positive semi- matrix A with largest eigenvalue Ymaxo have
acc A
Tmax || ||2:|/2
Proof. Let (r and {oi)d= be the eigenvalues and eigenvectors of A. Since (v:}d_ form basis, there are constants 1d such that æ = Σd CUS, We have
| =
Gc2u, Au;
Σ
n u, v, S 7max
Σ
a. = Ymax ||
i=15=1
1,1=
Lemma D.8. For all 20. 0.
1
min(1, S In(2)
In(1 + x).
25

---

Proof. Since In(1 + 2)/ In( is monotonically increasing in we only need to prove that S In(1 + z (2) for all [0, 11. For any positive constant a, the function a In + x) is concave on the domain [0. 1.. Therefore, if x I aln(1 + x) at the end points
1, then x S (n(1 + x) for every x [0. 1]. At 0, we have In + x) for any a, which means we can choose the smallest such that 1 I a anIn11 + 1). By rearranging this inequality, we obtain
0 and
a 1/ l2)..
D.1 Deta-Dependent Regret Bound
First, we show that the cumulative regret of both of our algorithms can be upper bounded by the sum of the widths of the UCB/LCBs that they use. Let
UCBe, (a) max {o(a) 0}, and LCBa, min { 0-0,
oee,
In words, UCBe, (a) and LCBe, (a) are the upper and lower confidence bounds used by CMM-UCB (evaluated a). Similarly, let
AUCBe, (a) 0 + RAMM, [lo(a)) (o) octal)-1
ALCBe, (a) = o(a) d(a))o.,. RAMM, [l (o) 4etal)-1-
AUCBe, (a) and ALCBe, (a) are the analytic upper and lower confidence bounds used by AMM- UCB. Lemma D.9 shows that the cumulative regret of CMM-UCB and AMM-UCB can be upper bounded by the sum of the widths (UCB minus LCB) of the confidence bounds that they use.
Lemma D.9. Suppose the actions a,, a2.... are selected by the CMM-UCB algorithm. For any adaptive sequence of mixture distributions P. NN Tx) and any ô E (0, 1]. with probability at least 1
T S Aa))))
T
VT 2 I,
Σ UCB,, (a.) LCBe, (ar). 2=1
(29)
t=1
Suppose the actions 01, ....... are selected by the AMM-UCB algorithm. For any adaptive sequence of mixture distributions P. = N(,,, T)) and any 8 E (0, 1], with probability at least 1
T
Ya 0,T21,
E S Σ AUCBe,_, (at) -LLCB,,,
(30)
Proof. Using Cor. 5.2 (i.e. the fact that θ1, O2 ... is confidence sequence), for any adaptive sequence of mixture distributions P. = =N T:) and any E (0, 1]. with probability at least 1
Ya E 1,
I.Be, (a) S ((a) T 0 < UCBe,,(a).
Using Thm. 6.1 this implies
Va > 0,
(4) T < AUCBe,, (a).
Let a1, ....... be the actions selected by CMM-UCB, i.e. argmax,eAi (a)] Then, with probability at least
8, we have
Σ (ar)
(aa)) -(at)) T
T
UCBe, (a,) - ILCBe, (at)
1=1
UCB (a:) LCBB,,
26

---

Now, let d1, a2,,... be the actions selected by AMM-UCB, i.e. = oEgmax,EAA (a)] Then, with probability at least have
Σ (a,)
Σ
(0)) - (4)
T AUCBe, (4:) ALLCBe,,
t=1
Since Va > 0.a E A and t > 1, AUCBe, (a) 2 UCBe,_, (a) and ALCBe,,, (a) <
LCBe,.. (a), (29) implies that (30) also holds when a1, 02. ... the actions selected by CMM-
UCB.
Suppose a1, CMM-UCB or AMM-UCB. For any adaptive sequence of mixture distributions P. = NW T,) and any 8 (0, 1), with probability least 6
Proof of Theorem 7.3 We start by using Lemma D.9
.2.... ,1,a2,...
the actions selected by
T
Ya 0,
Σ
((a) S Σ AUCBa, (a.) ALCBe, (at).
Using the definitions of AUCBe, (at) and ALCBe, (ot). we have
T
Va 0,721,
Σ A(a)) S Σ (aAMM,,-Ill((aalll ---tta)-11-
D.2 Data-Independent Regret Bound
To establish data-independent regret bounds, we first prove data-independent upper bounds on the radius RAMM, and the norms [Io(a))l(( [ to1 Then, we take the data-dependent regret bound in Lemma D.9 and substitute in these bounds on the radius and the norms.
D.2.1 Bounding the Radius
Lemma D.10. If. for any O. the sequence of mixture distributions is P. -N(0,c,,,)) and a = 0² //. then
R2 RaMME S o'd (1+
ctl
O²B² + 2021n(1/6).
o2d +
(31)
Proof. In Equation 24 we already saw that for this choice of and the mixture distributions, have
( - T. + 1)) + B² + ln
MAM = o² In (det
To obtain data-inde data-independent upper bound on the radius, all that remains is to upper bound In (det (500 t + 1)) by data-independent quantity. Using Lemmal D.2 have
etL2 s dln (+
In det
T. + +1) T2
o²d
Therefore
RAMMA & dddIn (1+ otT,
o2d + O²
+ 200
27

---

Lemma D.11. If. for any dg E R' and any do 0, the sequence of mixture distributions is =. = 0, oi 1 for any d (0, 1] and any a with probability at least 1 for
all
o² 10" 0oll2 + din 1+ o²d + aB + 1000)m(1//))
toi
HAMM, <
0
+ o (1 tL² / (ad)) + 2/ 10 v dln (1+ + /ad)((d))))))))))))))))))))))) + 20 20
Proof.
In App. B.2 (see Equation 16). saw that the squared radius R&M, can be written as
RMM, = -20 In
exp (- 202 (f. 2f
-f: (t)
20 In(1/)).
f 1
(32)
Using the substitution D,0- = S.. (32 is equivalent to
exp (-2) 2
(0. (0:0-n) )))) 20 In(1/6). (33)
RAM. -20 In
E
(~
Using the Donsker- Varadhan change of measure inequality (specifically (26), the first term on the right-hand-side of (33) equal
inf E [ r:) (.) - r.)] + 20 2 BOo (0 (RP(
L
we evaluate this at any specific distribution Q, we obtain an upper bound on the infimum over Q. We choose Q N'00" E.), where E. = tb, Tb 1 1)- Combining everything so far,
have
R
S
E
[ - r.)) r:)T T - rr)] + 20 DKL(W(O", E.) oi1)) + 20 In(1/))
0~N(0- E.)
o² -0,00- - rri) (10,0" -r) + tr (b) +,E,)
tr((e)
of
0²d + σ² 0 - 00l12 + 2n
det det(E,
[Tel(1/oo))] + 20 In(1/8)
(34)
Using Lemma D.3 we have
tr (,E,) s odd.
Using Lemma D.4 we have
o² tr(EE) S odd.
Using Lemma D.2. we have
det(E,-) In det
( ( o²
o. + +1) s sdm
oft1?
In det((L/of)1)
1+
o2d
The bound on R2 REIMA in 34 becomes
0² RAMM. S (. -r))
ogLL2
0-
(1+
+ +2 +2021n(116))
odd
This means that
0²
odd (1+
(1+ + 20 (1(/0)
oitL?
R2 RAMMA -r: -r:) -r:) +
1 - 0011 001l +
o²d
+ aB² - r. +r き, (0. x, al)
क,7
(35)
28

---

Finally, using Lemma D.3 then Theorem D.6 and Lemma D.7_ and then Lemma D.2 for any 8 E (0, 1] and any 0, with probability least 1 6, for all t 2 0 simultaneously
(2,0" -ri)"(2,0) (2,0" - rr) r. + + D, (o) Φ2 + aal 2 r
< (TTeelli selling -ctad)-1 + 2xx 110 110
0.to1)-1 o 1 6: ((,00 (2t0))-1
+ (e[00+1)) + +20 In(1/0) 22v0 10 V in det - 2 2, +1)+ + +21n(1/0) s s in det
(1+t2)) ad )
(+
tL?
+ 20 2 dln det (1+ =+)d)) + 2m1m()))
s det
Substituting this into (35
we have
toi
HAMM, s 0
10 00l12 o
1 1+ o²d + ab + 10010()
+ o (1+ + 2/ v dl (1 (1+ (L3/ + 2021n(
D.2.2 Bounding the Sum Norms
We use the following upper bound on the sum of the squared norms.
Lemma D.12 (Lemma 11 of (Abbasi- Yadkori et al. 2011)). For any a > 0, we have
Σ min (1,11((()))) (oT (f
S
1 1n(2)
dln 1+ ad
TL2
In Lemma 11 of (Abbasi- Yadkori et al. improved constant by using Lemma D.8 instead of the looser bound min(1, S 21nn11 + x), for 2 0.
2011 12)) = 1.44 is replaced with 2. We achieve an
D.2.3 Regret Bounds
We now ready prove data-independent regret bounds.
we can also obtain the following data-dependent bound the per-round regret for actions selected by CMM-UCB AMM-UCB. For the mixture distributions P. = NNO,, (b, a = o² /c and any E (0, 1), with probability least 1
Proof of Theorem 7.6
Following the same steps as in the proof of Lemma D.9
Vt 2 1,
A (a+)) < 2 R || (o,, 01 1)-
(36)
From Assumption 7.4 (á(a) 0* E [[C, CJ), we have another bound on the per-round regret A(a:) < 2C.
(37)
The combination of 36) and 37 yields
(aa)) S min 2C, 2 11 (| 1(0T (-)-)
< 2 max(C, RAMM,--1) min(1, (((()))) oot.. ott
Starting with the Cauchy-Schwarz inequality, have
T
T
Σ A(ai) <
T
A(a.)2
(38)
T
max (C2, (PPPRAM min (1,11((a)))1 10 it ++g1-))
29

---

We will now use the upper bound on R AMM. from Lemma D.10 Let U AMM,-1 bound (i.e. the side of (T).. We have
denote this upper
T
T
Σ (at) &
4 max (RMM,))))))) min (1.
T
min (1,11((a)) +0 .)
2 max (C, (A,M,,).T-))
T
Finally, using the bound on the sum of norms in Lemma D.12, we have
2 Vin(2)
max (C.rr dln (1+ c(T - 1
B + 2ln
(
(1 (1+
cT
(ax) s
o2d
+
8
V dT
o²d
Now, state and prove cumulative regret bound that holds for more general choices of the mixture distributions and the parameter a.
Theorem D.13. Suppose that assumptions 7.4 hold. If. for any On E Rd and any on > 0, the sequence of mixture distributions is Pt N( Go, b. then for any ö E 10,1/2 and any > 0, with probubility at least 26, for all T simultaneously, the cumulative regret of CMM-UCB and AMM-UCB is bounded by
2 VIn
L2T O(dVTIn(T),
A 1:T S
max {C, UAMM.T-I] v di'n [1+- ad
where
0² 10" -011 2d2 (1 (T 1)
U2 UAMM.T-1 S Sdd+
+ +aB² + 40²1n(1/5)
(39)
00
o2d
(T 1)L²²
o22dn (1+ (T (T- 1)12)
+ o²din
1+
-2
2001m(118))
ad
ad
Proof. Following the proof of Theorem 7.6 we obtain (with high probability)
Σ A(a.) <
T
4max (Ca, RAMMA-.) min (1, (l((a))) (0_ )
1=1
This time, use the bound on the radius from Lemma D.11 Let UAMM.T-1 denote this bound on the radius (i.e. the square root the right-hand-side of (39). Also, note that this bound on the radius holds with probability at 8. Since - is monotonically increasing with T, we have
T
T
Σ ( < 2 max (C, UAMM.T))))
T
min (1.11o(a)lioz )
t=1
Finally, we use Lemma D.12 to obtain
T (aa)) < vIn
max {C, UAMM.- dT'In In (1+ (1+ L2T
Σ
ad
We used two inequalities that each hold with probability least 8. By union bound argument, the cumulative regret bound holds with probability at least 1 - 26.
30

---

E
Additional Experiments
In this section, we present the results some additional experiments which we investigate the effect of the mixture distributions (or priors) upper and lower confidence bounds.
E.1 The Effect of The Mixture Distributions
We investigate how our CMM-UCB upper and lower confidence bounds behave when provide an uninformative but well-specified mixture distribution/prior, an informative and well-specified mixture distribution/prior,, and misspecified mixture distribution/prior. Here misspecification refers to prior misspecification in a Bayesian sense. For reference, we compare the behaviour of our upper and lower confidence bounds with the upper and lower limits of Bayesian credible interval.
For fair comparison with CMM-UCB, we attempt to construct Bayesian credible interval that holds with high probability for all rounds 2 0. However, whilst the CMM-UCB confidence set holds with high probability over the random draw of the data 41, 71, 02, ......, the Bayesian credible interval holds with high probability over the random draw of 0 from prior (for fixed data a1, 71, 022 .....
For the Bayesian credible interval, we use Gaussian prior and assume 0- ~ NN Ep). We assume a Gaussian likelihood function, i.e. rewards are of the form Ti = <(ar) er, where ~ N(0, The Bayesian posterior for 0* is another Gaussian N N(H,, Σ.), where
14 E, Eg + J v.Tr))
E, =
(
02 $
o. + Σ
Using Bayes' rule, any round I, have 0 ~ ~N(, E.). Therefore
(H. - TT (m, 0*) (d),
where (d) is a chi- chi-squared distribution with degrees of freedom. Let Qa(-) be the quantile function of the chi-squared distribution with d degrees of freedom. With probability at least 1 d, (over the random draw of 0" from N Ex))
(n, - --) ) " (m, 0²) S Qa(1 5.).
(40)
68 Using a union bound argument, if 6, ( then 40)) holds with probability at least 6 for all 2 0. Therefore, 0" ~ (H,. Eu). then with high probability the following credible sets contain 0* for all t 2 0 simultaneously:
θ, 00 e Re (m TT) ( s SQa Qa (1 (1-1))))0++11110))111 1)
68
(1
The upper limit of the credible interval for this credible set (and the one use in Figure is
(o(a)=0) =d(a u. + voa(1 (t+ 1) ocê,
68
Vola) To
sup
We compute confidence bounds/credible intervals for a randomly generated linear function of the
form f(x) = ((x)) 0", with inputs x E and 0" E 20 the latter drawn from a standard Gaussian
distribution and if necessary scaled down to |@0" lg < 10 Random Fourier Features. We generate random data {( V1. M where y/ o(xx) 0" nik 7k (0, o²) and 0.1 (so the Gaussian likelihood is well-specified).
B. For the feature map d, we
31

---

CMM-UCB
Bayes
0.0
0.0
2.5
2.5
5.0
-5.0
-7.5
-7.5
-4
-2
2
-2
2.5
5.0
5.0
7.5
77.
5.0
5.0
2.5
2.5
-7.5
-7.5
-2
2
-2
2
Figure 4: The upper and lower confidence bounds of our CMM-UCB method (left) and Bayesian posterior credible intervals (right) with different choices of the prior. The top row uses the prior f, (O, Φ for CMM-UCB and 0" ~ (O, 1)) for Bayes. The middle row uses an informative prior: f. ( .,7 for CMM-UCB and 0 N'e0, 0..1)) for Bayes. The bottom row misspecified prior: f. N 0.0", 0,, for CMM-UCB and 0 A((0", 00.11) for Bayes.
Figure shows the CMM-UCB upper and lower confidence bounds (left) and the Bayesian credible intervals (right) with different choices of the prior. We use roughly equivalent priors for both methods. If the Bayesian credible interval uses the prior 0* NN Eo), then CMM-UCB uses the induced distribution over the function values 0,0", i.e. N(Q 2.E,
In the top and middle rows of Figure where the prior is sell-spe,ified, we observe that the CMM- UCB upper and lower confidence bounds are slightly looser than the Bayesian credible intervals. In the bottom row of Figure when the prior is misspecified, the CMM-UCB interval gets looser whereas the Bayesian credible interval becomes wrong. In summary, the Bayesian credible interval appears to be slightly tighter when the prior well-specified and least somewhat informative, but CMM-UCB is robust to "misspecified" mixture distributions.
32

---

E.2 Benefits of Adaptive Mixture Distributions
In this section, we investigate method for refining M4 and T, based on previously observed actions and rewards. Recall that μe and Ta must be chosen such that: (a) e and Te can only depend on d1..... a2 and r1, ......... ............ 1: (b) the first 1 elements pr must be equal to p4-13 (c) the upper left / x 1 - block of T' must be 1- (d) T2 must be positive (semi-)definite
As in Sec. 6.4 and k are any fixed mean and kernel functions. Each set using an adaptive kernel function h For /3 > 0, define
and column of T; is
(e d') = k(a, a') ke(a)' (K, + 31) (a));
where (a(a) [k(a, a1),................. ... k(a, ax)] and K, is the kernel matrix whose (i,j)th element is k(a;, aj). For Te, we choose
Kalai, a1) k1 (1 a1)
11 (a a2) k1 a2)
k 1 ae)
ky ka21 01)
T,
(41)
(ar; a1)
( a2)
k (at, as))
The 7th column and 7th row of this matrix depend only on only d1 ......... 0g. Our motivation for this kernel function is: (a) generalising the usual Bayesian Gaussian process (GP) posterior covariance, one can show that if the kernel function & is positive definite, then T; is positive semi-definite; (b) ke the Bayesian GP posterior covariance function (with Gaussian likelihood with variance 3). Each new element of μe is set by evaluating an adaptive mean function m4-1 at the latest action dg Define
m (a) m(a) (a) (K, + =1) (m, (m))
For Me, choose
14, [mo((i))
m1((2)) mi
me-1
(42)
The th element, ma=1 depends on only 41, 7...... ag so this a valid choice for μ4, Note that my is the Bayesian GP posterior mean function (again with Gaussian likelihood with variance (8).
We now compare the standard "non-adaptive" mixture distributions (with f4, and T, as (9) and an adaptive sequence of Gaussian mixture distributions (with J4, as in (42 and T, in 44)). With both sequences of mixture distributions, we use m(a) = and k(a, a') <(a) "a(aa. For the adaptive sequence of mixture distributions, we set 8 4
Non Adaptive
2
Figure 5: The upper and lower confidence bounds of CMM-UCB with the standard (non-adaptive) sequence Gaussian mixture distributions (purple) and adaptive sequence of Gaussian mixture distributions (red).
Figure shows upper and lower confidence bounds for a randomly generated linear function f(z) = ((x) where v E R. 0* R220 and & is a random Fourier feature map. this example, the adaptive sequence of mixture distributions leads to tighter upper and lower confidence bounds.
33

---

Accuracy Raward
100
00-
3.75
03
1.55
J08 IC:B
1.30 202
370 202 0.00
5.0
Figure 6: The radius RAMM, (left) and test accuracy (right) with the standard sequence of Gaussian mixture distributions (blue) and the adaptive sequence of Gaussian mixture distributions (orange). On the left, we plot the mean value of the radius RAMM. over 10 runs and show the mean one standard deviation in the shaded regions. On the right, we plot the mean reward over 10 runs and after Gaussian kernel smoothing.
Figure 6 shows the radius RAMM, (left) and test accuracy (right) for AMM-UCB in the SVM hyperparameter tuning problem with the Raisin data set (described in Sec. 88.2 We observe that AMM-UCB with the adaptive mixture distributions achieves slightly higher test accuracy.
In Sec. D.2.1 we saw that for standard sequence of mixture distributions, RAMM.T could be upper bounded by data-indeppndeet quantity of order O( ((Vdln(()). In Figure RAMM,T does appear to grow roughly logarithmically with I" when the mixture distributions are the standard choice. However, RAMM.T r appears be bounded by a constant when the mixture distributions are adaptive. If, when using adaptive mixture distributions, we could prove a data-independent bound on RAMM.T of order O(vd), then we would be able to improve data iata-independent cumulative regret bounds to (d (T))))) (rather than O(dVTIn(T)), This would be within Vln(T) factor of the lower bound (ddTT).
F Efficient Radius Computation
If we compute the squared radius RMM, using the expression in 5 then we have to compute the inverse and determinant the x matrix 1 + Te/o?. We will now show that for any mixture distribution of the form P. = ( & En + where Eg symmetric and positive-definite, we can re- ve-write the expression for R such that we instead need to compute the inverse and determinant of d x matrix. When P. N( D.EDDT)) ). the squared radius RAA., equal
R (M, (u,)-:)'
2 10 (1+-
(m, ro)+o² In (det [1
(1-21 o²
)) +20² In(1/)).
By using the Weinstein-Aronszne identity, and then doing some algebra, we have
det (1 (
0. = det 1
1/ 2 D. +
= det (Eo/o?) (0, + 0, +02
o²
o²
Using Lemma C.4 with y 02,0 2 p4, -i and M = 4.E 1/2 we have
(4--r() rz) [+ [1+ 02
t Eo
(H:- -r) = (H: - -r.) (H+: - r()
-(4, - T4,
2220 1/2 11//20 2,7 + x + +021) 21/2 // (m, rt)
=(14 TT) (m,, rt) - -14, - ri) Φ, 1// 1/2 //// ( t; + +o o²Io x212)
xd ". (m, -r))
(14 rz) TT)T(H rτ) -14, - -rt)² TT)TTT (t. t; + o - /, [/,, -rt)
34

---

The resulting expression for RMM, is rather cumbersome, but the upshot is that we now (only) need compute the inverse and determinant of the d matrix &, Φ, + o Since, we compute RAM.. at each round t, can update the inverse of D, Φ, + x² - imcrementally using the Sherman-Morison Morrison formula (Sherman & Morrison 1950). The determinant of o 4r + o can be updated incrementally using the relation
det ( @ + =0 = d + E ((())) ( + o - (a))),
which can be found in Eq. (6) in Lemma 11 of (Abbasi-
al. 2011). Additionally, recall /e for any c 0, the radius RAMM, of our that (see Eq. (24h) when P. = (O, o and a = o²/e analytic confidence bounds simplifies to
o²B²
AAMM. o² In (del
( :. 0. + 1)) g2
+ 2202n(116).
Note that the inverse (0) o, + (o2 still appears in the expression for AUCBe, (a) and in the incremental determinant update rule.
35


Reviews:
[{"review_id": "Aba4ORomw6", "reviewer": "Reviewer_qEDN", "summary": "This paper studies the stochastic linear bandits problem and proposes an improved algorithm with sub-linear regret guarantees. The improvement is achieved using a novel tail bound for adaptive martingale mixtures to construct tighter upper confidence bounds, which leads to a smaller regret than existing algorithms for linear bandits. The authors also verify the performance of the proposed algorithm via experiments on hyperparameter tuning tasks. ", "questions": "Please address the weakness raised in ***Weaknesses**. \n\nMinor comment:\n1. Line  303: FTS: Freq-TS\n\nI can change my score based on the authors' responses.", "limitations": "I have raised a few limitations of the paper in my response to the ***Weaknesses**. Since the paper is a theoretical contribution to linear bandits literature, I do not find any potential negative societal impact of this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "#### **The following are the strengths of the paper:**\n1. The performance of any upper confidence bound (UCB) based bandit algorithm depends on the tightness of the confidence bounds. This paper proposes a novel way (using the tail bound for adaptive martingale mixtures) to improve the upper confidence bound, leading to an improved UCB-based bandit algorithm with a smaller regret.\n\n2. The authors propose two novel methods for computing the confidence bounds: Convex Martingale Mixture UCB (CMM-UCB) and Analytic Martingale Mixture UCB (AMM-UCB). CMM-UCB uses a convex solver for the UCB maximization (gradient differentiable convex optimization), whereas AMM-UCB uses a weak Lagrangian duality to obtain an analytic UCB (gradient can be computed in closed-form or via standard automatic differentiation procedures). \n\n3. When the mixture distribution is a Gaussian distribution, the authors showed the sub-linear data dependent/ independent cumulative regret for CMM_UCB and AMM-UCB. The author also empirically validated the performance gain of the proposed methods over existing linear bandit algorithms. ", "weaknesses": "#### **The following are the weaknesses of the paper:**\n1. Assumption of mixture distribution having Gaussian distributions: The regret bounds stated in the paper hold only when the mixture distribution is Gaussian. It is unclear from the paper how practical this assumption is and what the consequences are (especially in analysis) if this assumption does not hold. \n\n2. Linearity assumption: Assuming a linear relationship between the reward and action's features (in high dimensional space using a known feature map) restricts the applications of proposed methods. Even though authors claim their tail bounds can be used to derive confidence sequences for non-linear reward functions, it is unclear what are the challenges of extending their work to non-linear reward functions (or kernelized bandits).\n\n\n3. Unexplained notations: Many notations are not properly defined in the paper. For examples: \\\ni. Line 145: What is $Z_t(f_t)$ connection with existing regret analysis (e.g., OFUL)? \\\nii. Line 149: How are the parameters ($\\boldsymbol{\\mu}_t, \\boldsymbol{T}_t$) of Gaussian distribution computed? \\\niii. In Theorem 7.5: what is the regret upper bound in terms of $T$? \\\niv. Line 234: How to set the value of $c$? \\\nv: Line 248: What is $\\sigma_0$ and how to set its value? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind and constructive comments.\n\nWe now address the reviewer's points under \"Weaknesses\":\n\n1. The reason for choosing Gaussian mixture distributions is that the expected value just above Eq. (5) can be calculated analytically when $P_t$ is a Gaussian, which is convenient for running the algorithm and for proving regret bounds. Restricting the mixture distributions to be Gaussian does not impose any assumptions on the ground truth reward function or the bandit problem. The mixture distributions can simply be thought of as hyperparameters of our bandit algorithm.  \n\n2. Our bandit algorithm applies to kernel bandits with minor modifications. The main challenge is in obtaining data-independent regret bounds analogous to the one in Thm. 7.6, since the feature dimension is $d=\\infty$ for interesting kernels.\n\n   In more detail, our confidence sequences in Corollary 5.2 can be immediately extended to non-linear reward functions $f^*$, simply by replacing $\\phi(a_t)^\\top\\theta^*$ with $f^*(a_t)$ in the definition of $Z_t(f_t)$. The result is a confidence set, as in Corollary 5.2, with a squared error constraint for non-linear functions $f$ and a suitable boundedness constraint $\\Vert f\\Vert\\leq B$. For kernel bandits, the corresponding UCB is still the solution of a convex program, so we can run our CMM-UCB and AMM-UCB algorithms in kernel bandit problems. While the data-dependent regret bound in Thm. 7.5 remains basically unaltered, the (derivation of the) data-independent regret bound in Thm. 7.6 must be modified. The main challenge is that the regret bound must now depend on quantities like the effective dimension or the maximum information gain of the kernel instead of the dimension $d$ of the feature vectors (which is $d=\\infty$ for interesting kernels).\n\n   We will explain this in more detail in the revised version of the paper.\n\n3. i. The random variables $Z_t(f_t)$ in our submission play a similar role to the random variables $Z_t$ in [Russo and Van Roy, App. B.1].\n\n   ii. A standard choice is $\\mu_t\\equiv 0$ and $T_t = \\Phi_t\\Phi_t^\\top$, which can be motivated by choosing $\\theta\\sim{\\mathcal N}(0,I)$ and then considering the distribution of the function values $\\Phi_t\\theta$. In general, $\\boldsymbol{\\mu}_t$ and $\\boldsymbol{T}_t$ can be freely chosen as long as the sequence of mixture distributions $(\\mathcal{N}(\\boldsymbol{\\mu}_t, \\boldsymbol{T}_t) |t \\in \\mathbb{N})$ satisfies the requirements for being a sequence of adaptive mixture distributions; see lines 126-130 for general mixture distributions and lines 812-816 for Gaussian mixture distributions. A particular adaptive choice of $\\mu_t$ and $T_t$ is examined in App. E.2 (i.e. such that the entries of $\\mu_t$ and $T_t$ depend on the previously observed rewards, namely they are predictors of the reward at the newly selected action), and shown to yield good results.\n\n   iii. The growth rate in $T$ of the regret bound in Thm. 7.5 is determined by the growth rate of the radius and the sum of norms. If we upper bound each of these terms by quantities with explicit dependence on $T$, then we arrive at the data-independent bound in Thm. 7.6. We can therefore say that the dependence on $T$ of the regret bound in Thm. 7.5 is no worse than that of the regret bound in Thm. 7.6 (i.e. no worse than $\\mathcal{O}(\\sqrt{T}\\ln(T))$).\n\n   iv. There are at least two good choices of $c$. In all of our experiments, we used $c = 1$, which is a simple choice that appears to work well. Alternatively, one can choose $c = B$. With this choice, the data-independent regret bound in Thm. 7.6. has improved dependence on the norm bound $B$ (roughly $\\mathcal{O}(\\sqrt{B})$ instead of $\\mathcal{O}(B)$).\n\n   v. One can think of the real number $\\sigma_0$ as a guess for the distance between the observed reward vector $\\boldsymbol{r}_t$ and the predictions $\\Phi_t\\boldsymbol{\\theta}_0$. Consider Eq. (5) with $\\boldsymbol{\\mu}_t = \\Phi_t\\boldsymbol{\\theta}_0$ and $\\boldsymbol{T}_t = \\sigma_0^2\\Phi_t\\Phi_t^{\\top}$. If the distance between $\\Phi_t\\boldsymbol{\\theta}_0$ and $\\boldsymbol{r}_t$ is close to 0, then we should choose $\\sigma_0$ to be close to 0, since both the quadratic and log determinant terms in Eq. (5) will then be close to 0. Alternatively, if the distance between $\\Phi_t\\boldsymbol{\\theta}_0$ and $\\boldsymbol{r}_t$ is large, we should choose a larger $\\sigma_0$ so that the quadratic term in (5) is not too large. We call $\\sigma_0$ a guess because it has to be chosen *before* observing $\\Phi_t\\boldsymbol{\\theta}_0$ and $\\boldsymbol{r}_t$.\n\nThank you for pointing out the typo on line 303.\n\nWe hope that the reviewer can now recommend acceptance of the paper.\n\n[Russo and Van Roy] Russo, D. and Van Roy, B., Eluder dimension and the sample complexity of optimistic exploration. *Advances in Neural Information Processing Systems*, 26. 2013.\n"}, {"review_id": "64vrqYrZn8", "reviewer": "Reviewer_Cd9x", "summary": "The paper considers the problem of stochastic linear contextual bandits, and proposes an improvement of the classic LinUCB / OFUL algorithmic template via a more sophisticated construction of the confidence sets for the hidden reward vector. The improvement comes from replacing the confidence ellipsoid used since the classic work of Abbasi-Yadkori et al. (based on the method of mixtures) with a tighter confidence set based on what the authors call \"adaptive martingale mixtures\". The authors eventually derive a confidence ellipsoid resembling the ones used by Russo and Van Roy, which enjoys the useful property of having a potentially data-dependent radius, and can also be turned into a confidence sequence very easily via an application of Ville's inequality. Using two different methods (an exact convex solver and an approximation of the optimal width), the authors then turn these confidence sets for theta into confidence bounds for the rewards of each action, and use the resulting bounds in a UCB scheme. The algorithms are then shown to outperform standard LinUCB in some simple experiments.", "questions": "See above.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is superbly written and presents a very interesting technique, improving one of the main building blocks of UCB algorithms that have been used for over a decade without any substantial changes. The proposed techniques make use of techniques that have recently gained popularity for mean estimation and proving PAC-Bayesian generalization bounds. The derivations up until the end of Section 5 are very neat and satisfying, and I believe that everyone interested in confidence ellipsoids and linear bandits should find them interesting.\n", "weaknesses": "The concrete approaches proposed in Section 6 are also nice but leave something to be desired. Perhaps it is my fault, but I have missed how one should choose the predictions mu_t and T_t. From what I understand, both approaches in Sections 6.1 and 6.2 should give valid results irrespective of the choice of these parameters, but I still wonder how the choice will impact the quality of the guarantees. The authors only suggest that choosing mu and T that \"are good predictors of the (stochastic) reward r\" will yield good results, but do not elaborate further. For instance, is setting mu_t as the least squares estimator and T_t as the Grammian a good idea? It feels somewhat unsatisfying to introduce all the possibilities for adaptivity and then simply set a constant lambda_t and go with the standard choice of mu and T... Also, the confidence set proposed in Section 6.2 doesn't seem all that different from the standard tail bound popularized by Abbasi-Yadkori et al. Accordingly, the regret bounds of Theorem 7.5 and 7.6 also take the same for as previous bounds, which is not unexpected given how the theorems are stated for rather generic choices of mu and T. I can see that the new bounds *could* be tighter, but at the moment the theory does not reflect this, which is somewhat disappointing.\n\nOne additional thing that I would like to comment on is the computational complexity of the resulting method. I understand that the UCB's obtained from the method are always convex in the feature representation of the actions (given how they are a maximum of linear functions). Thus, calculating the action with maximal UCB is a convex maximization problem, which is NP-hard in general. This is generally true for all UCB-like methods I can think of, so perhaps it is a bit odd to avoid discussing this question altogether in the paper and suggest that the gradient-based optimization scheme for finding the optimistic actions is a theoretically well-justified idea. (It is not, but I understand that it often still works in practice.) I think it would be nice to add a comment on this in order to not mislead more casual readers who may not be familiar with this computational difficulty.\n\nDespite all my criticism above, I am happy to support acceptance of this paper to the NeurIPS program. I am looking forward to future literature addressing the current limitations of the approach proposed in this otherwise very nice paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We are very happy to receive such an enthusiastic review!\n\nWe now address the reviewer's points under \"Weaknesses\":\n\n* *how one should choose the predictions mu_t and T_t ... I still wonder how the choice will impact the quality of the guarantees ... For instance, is setting mu_t as the least squares estimator and T_t as the Grammian a good idea? It feels somewhat unsatisfying to introduce all the possibilities for adaptivity and then simply set a constant lambda_t and go with the standard choice of mu and T ...*\n\n   The effects of $\\mu_t$ and $T_t$ on the tightness of the UCBs and the regret guarantees are determined by their effects on the squared radius $R_{\\mathrm{MM}, t}^2$, which is defined in Eq. (5). Based on Eq. (5), we can treat the mean vector $\\mu_t$ as a prediction of the reward vector $r_t$. The covariance matrix $T_t$ can be thought of as the uncertainty associated with this prediction. If the distance between $\\mu_t$ and $r_t$ is close to 0 (i.e. $\\mu_t$ is a good predictor of $r_t$), then the quadratic \"prediction error\" term in (5) will be close to 0, and we can afford to choose $T_t$ close to zero to minimize the log determinant term.\n\n   Unfortunately, we cannot simply choose $\\mu_t = r_t$, because then the mixture distributions would not satisfy the conditions in lines 812-816 (i.e. each component of $\\mu_t$ can only depend on the *preceding* rewards). Hence, we can think of the $k$th component of $\\mu_t$ a prediction/guess/bet for the $k$th reward.\n\n   We agree that it is exciting to consider more adaptive choices of $\\lambda_t$, $\\mu_t$ and $T_t$. In App. E.2, we investigate a generic method for setting $\\mu_t$ and $T_t$ based on previously observed actions and rewards; this results in somewhat lower regret in an experiment (Fig. 6 in App. E.2) and possibly better regret bounds. In App. B.1, we derive the radius $R_{\\mathrm{MM}, t}$ for more general choices of $\\lambda_t$. However, we don't analyze these choices of $\\lambda_t$, $\\mu_t$ and $T_t$ in the main paper because: (a) these choices make the resulting bandit algorithms very difficult to analyze theoretically; (b) we already struggled to fit everything into the 9 page limit. We view the analysis of more adaptive versions of our method as an exciting challenge to address in future work.\n\n* *Also, the confidence set proposed in Section 6.2 doesn't seem all that different from the standard tail bound popularized by Abbasi-Yadkori et al. Accordingly, the regret bounds of Theorem 7.5 and 7.6 also take the same for as previous bounds, which is not unexpected given how the theorems are stated for rather generic choices of mu and T. I can see that the new bounds could be tighter, but at the moment the theory does not reflect this, which is somewhat disappointing.*\n\n   In App. C.2, we compare our analytic UCBs (from Thm. 6.1) to the OFUL UCBs. We prove that for any value of the OFUL regularization parameter (similar to our $\\alpha$ parameter), there are valid (and simple) choices of $\\alpha$, $\\mu_t$ and $T_t$ (which are not necessarily the optimal choices) such that our analytic UCBs (and therefore also our convex-program UCBs from Eq. (6)) are always strictly tighter than the OFUL UCBs. Furthermore, there is hope that more the adaptive choices for $\\mu_t$ and $T_t$ described in App. E.2 could lead to regret bounds with an improved growth rate in $T$. See Fig. 6 in App. E.2 and the discussion below it for more.\n\n* *One additional thing that I would like to comment on is the computational complexity of the resulting method. ... This is generally true for all UCB-like methods I can think of, so perhaps it is a bit odd to avoid discussing this question altogether ... I think it would be nice to add a comment on this in order to not mislead more casual readers who may not be familiar with this computational difficulty.*\n\n   We fully agree with the reviewer on this point. We will add a comment on this in the revised paper."}, {"review_id": "jrkrvUrq0a", "reviewer": "Reviewer_uqhQ", "summary": "A very well written paper introducing a slightly different way of constructing confidence sets for $\\theta^\\star$ in the adaptive regression setting. The two main differences are that the paper bounds the norm of the observation noises $\\epsilon_t$ directly, rather than the projection of the noises that features in the standard bound. This is done by showing that the method of mixtures can be used with a suitably adapted sequence of mixing measures, and choosing that mixture appropriately. ", "questions": "I included some minor questions in the weaknesses section. I have no major questions for the authors.", "limitations": "Some aspects of the writing could be thought to overclaim, specifically when it comes to robustness to misspecification. I feel strongly that this ought to be addressed. But this is also easily fixable; I hope the authors do so.\n\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Paper is _very_ well written. Method introduced is neat and the perspective taken in deriving it will be of interest to other researchers in adaptive regression/design. ", "weaknesses": "I don't believe the paper has any significant weaknesses. One could argue that it has, perhaps, limited scope: but bandits and adaptive regression/design are very popular topics nowadays, and this is an interesting read for many people interested in those.\n\nOne issue I feel strongly about, but that can be easily addressed: you advertise that your confidence intervals are robust to misspecification (abstract, line 12). I was very disappointed to see, when I got to section 8.1 and particularly lines 282-289, that you mean misspecification to a prior in a Bayesian setting. The general setting of your work is frequentist, and in the frequentist setting, misspecification has a well understood meaning which, of course, does not coincide with that which you show. It is unclear that your method is any better in this respect than the standard concentration inequality used in OFUL (Yasin's original work); and indeed, that's a generous interpretation: it is generally accepted that bounds derived under frequentist assumptions work well in a misspecified Bayesian setting. Please remove this claim from your abstract.\n\nAnother issue is that your plots are unreadable when printed in grayscale (all lines look the same). I'm reviewing a grayscale printed version of this paper, so cannot asses empirical performance from plots. Fortunately for you, I also happen to care little for empirical results.\n\nI have some minor feedback, solely for the purpose of improving the manuscript:\n\n-High level: please reiterate in the introduction, e.g. on line 44, that your UCBs are tighter in an empirical sense; that you have not (to my understanding) shown them to be tighter in a theoretical sense. Your results are neat: by risking the perception that you might be overclaiming/misleading you'd be doing yourself a disservice. \n\n-High level: your method is highly related to the rather excellent paper \n\n-Line 65: the result you cite Chowdhury & Gopalan 2017 for is implied directly by theorem 4.1 in Yasin Abbasi-Yadkori's PhD thesis (2012); that the result of Chowdhury & Gopalan was novel is an error in the literature that ought not be propagated.\n\n-Lines 97-98, you state that $\\mathcal{H}_t$-measurability equates to 'can be calculated using the data available just after reward $r_t$ is revealed'. From the rest of the paper, I know that you know that this isn't true. It may seem like a nice simplifying explanation, but its misleading, and often inexperienced authors make a mess of things because they take that to be the definition. Indeed, in your setting, the event $\\{ \\theta^\\star \\in \\Theta_t\\}$ is $\\mathcal{H}_t$ measurable (assuming $\\Theta_t$ is a closed set, see next comment), since $\\theta^\\star$ is a constant and $\\Theta_t$ is a measurable random set. But $\\theta^\\star$ is explicitly unknown at the end of the $t$th iteration, and so the indicator of $\\theta^\\star \\in \\Theta_t$  _cannot_ be computed with the information available at that point. Please remove that statement, and if you feel the reader might need a primer on measurability, please include a reference to any standard measure/probability textbook.\n\n-Lines 95 to 100: you define what are effectively random sets with a certain property. One has to be careful around the definitions of random sets to ensure they behave in a way that one would expect. For example, we'd usually like that for a random set $A'$ subset of $A$, for any $a \\in A$, the event $\\{a \\in A'\\}$ is measurable. Your sets are closed and you work on a Polish space, so this is true; but I would point out that this is so (and indeed, you might run into trouble if the confidence sets were open). See Molchanov, Ilya: Theory of Random Sets. Springer London. 2017, 2nd edition. Proposition 1.1.2; that should be all you need.\n\n-Eq (5), I would point out that this is just the 2-norm of $\\epsilon_t$; this makes it much clearer, for example, where your naive bound of line 158 comes from.\n\n-On your assumptions 7.1-7.4: It seems to me that 7.2+7.3 together imply a bound of the form asked for in 7.4; is there a good reason you have a separate assumption 7.4? \n\nPS: I have not read the appendix. I am confident from the sketches in the main text that the result claimed goes through.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer very much for their careful and helpful comments!\n\nWe address the reviewer's points under \"Weaknesses\":\n\n* *One issue I feel strongly about, but that can be easily addressed: you advertise that your confidence intervals are robust to misspecification (abstract, line 12). ...*\n\n   We understand the reviewer's point, thank you for pointing this out. We will remove the claim about misspecification from the abstract, and in the main text of the paper we will clarify this term by writing \"Bayesian prior misspecification\". We hope that this makes clear that we make no claim about the frequentist notion of misspecification.\n\n* *Another issue is that your plots are unreadable when printed in grayscale (all lines look the same). ...*\n\n   We will use a more grayscale-friendly color scheme for the revised version of the paper.\n\n* *High level: please reiterate in the introduction, e.g. on line 44, that your UCBs are tighter in an empirical sense; that you have not (to my understanding) shown them to be tighter in a theoretical sense. ...*\n\n   Our UCBs are tighter in a theoretical sense. In App. C.2, we show that for any value of the OFUL regularization parameter (similar to our $\\alpha$ parameter), there are valid (and simple) choices of $\\alpha$, $\\mu_t$ and $T_t$ (which are not necessarily the optimal choices) such that our analytic UCBs (and therefore also our numerical UCBs) are always strictly tighter than the OFUL UCBs. We will add a pointer to App. C.2 in the paragraph on line 44.\n\n* *High level: your method is highly related to the rather excellent paper*\n\n   We would be curious to know which excellent paper the reviewer is referring to here, especially if we haven't cited it in our paper yet.\n\n* *Lines 97-98, ...*\n\n   We will replace our previous statement about $\\mathcal{H}_t$-measurability with: \"each $\\Theta_t$ can be calculated using the data $a_1, r_1, \\dots, a_t, r_t$.\"\n\n* *Lines 95 to 100: ...*\n\n   After this paragraph we will add the sentence: \"We remark that the confidence sets $\\Theta_t$ in this paper are random closed sets in the sense of [Molchanov, Def. 1.1.1], which implies that the event $\\theta\\in\\Theta_t$ is actually measurable for any $\\theta\\in\\mathbb{R}^d$.\"\n\n* *On your assumptions 7.1-7.4: It seems to me that 7.2+7.3 together imply a bound of the form asked for in 7.4; is there a good reason you have a separate assumption 7.4?*\n\n   We agree that 7.2 + 7.3 imply assumption 7.4 with $C = LB$. Our reasons for stating a separate assumption are: (a) this is in line with the conventions of other linear bandit analyses (e.g. [Lattimore and Szepesvári, Section 19.3]); (b) this leaves open the possibility that a better (than $LB$) value for $C$ is known.\n\nThe reviewer's other minor points under \"Weaknesses\" which we did not address above, we will directly fix in the paper as suggested.\n\n[Lattimore and Szepesvári] Lattimore, T. and Szepesvári, C., *Bandit algorithms.* Cambridge University Press. 2020.\n\n"}, {"review_id": "H6K8hCYmEp", "reviewer": "Reviewer_LyTZ", "summary": "This paper studies the stochastic linear bandits as introduced in Abbasi-Yadkori et al., 2011. Here, at each time step $t$, an action set $\\mathcal{A}_t$ is given. The learner then selects an action $a_t \\in \\mathcal{A}_t$, which maps to a feature vector $\\phi(a_t)$, and subsequently receives a reward $\\phi(a_t)^{\\mathsf{T}}\\pmb{\\theta}^*+\\epsilon_t$. The objective is to maximize the cumulative rewards over a designated time horizon $T$.\n\nThe main contributions of this paper can be summarized as:\n\n1. The authors propose a general approach based on the notion of Martingale Mixtures to create confidence sets. These are subsequently utilized in the meta LinUCB algorithm to derive the bandit algorithms. It is further demonstrated that such algorithms can be efficiently computed via convex optimization.\n\n2. The paper shows that such bandit algorithm derived from a suitable selection of mixture distributions $P_t$ attains the same worst-case regret as found in Abbasi-Yadkori et al., 2011.\n\n3. Evidence is presented to show that the algorithm derived in this paper outperforms the approach proposed in Abbasi-Yadkori et al., 2011 when applied to several real-world datasets.", "questions": "I'm curious, how would the present work compare to the general approach as in \"The Statistical Complexity of Interactive Decision Making\" by D. J. Foster, S. M. Kakade, J. Qian and A. Rakhlin.?", "limitations": "No issue with negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While I'm not thoroughly acquainted with the most recent literature on stochastic linear bandits, this paper appears to present compelling results. The idea of using mixture martingales to derive linear bandit algorithms is innovative and provides a general methodology for generating new algorithms. The authors supplement their theoretical contributions with empirical evidence showing that their algorithm outperforms those presented in previous literature, further strengthening their findings.", "weaknesses": "The downside of the paper lies in its inability to improve upon the theoretical worst-case bound as shown in Abbasi-Yadkori et al., 2011. The strength of this paper would be significantly enhanced if the authors could demonstrate that employing the methodology from their current work could theoretically offer improved bounds compared to previous results (or new results in novel settings).\n\nTypos:\n- Line 216,  $\\sum_{t=1}^T$ is missing\n- Line 696,  AUCB appeared twice", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and questions.\n\nWe respond to the reviewer's points:\n\n* *The downside of the paper lies in its inability to improve upon the theoretical worst-case bound as shown in Abbasi-Yadkori et al., 2011. The strength of this paper would be significantly enhanced if the authors could demonstrate that employing the methodology from their current work could theoretically offer improved bounds compared to previous results (or new results in novel settings).*\n\n   While our worst-case regret bound in Thm. 7.6 only matches the equivalent regret bound for the OFUL algorithm by Abassi-Yadkori et al., we can prove that our UCBs are tighter than the OFUL UCBs. In App. C.2, we show that for any value of the OFUL regularization parameter (similar to our $\\alpha$ parameter), there are valid (and simple) choices of $\\alpha$, $\\mu_t$ and $T_t$ (which are not necessarily the optimal choices) such that our analytic UCBs (and therefore also our numerical UCBs) are always strictly tighter than the OFUL UCBs.\n\n   We believe that there is potential to obtain worst-case regret bounds with improved dependence on $T$ using our methodology. In App. E.2, we investigate “more adaptive” choices for the mixture distributions, which depend on previously observed rewards. We observe that the radius quantity grows at a slower rate (in $T$) when using these more adaptive mixture distributions. This means that the data-dependent regret bound (in Thm. 7.5) also grows at a slower rate. In future work, we would like to search for improved data-independent bounds on the radius (which would give improved worst-case regret bounds).\n\n* *I'm curious, how would the present work compare to the general approach as in \"The Statistical Complexity of Interactive Decision Making\" by D. J. Foster, S. M. Kakade, J. Qian and A. Rakhlin.?*\n\n   The present work gives a new and improved way to *construct confidence sets* for bandits, which are turned into improved bandit algorithms with guarantees *via the UCB/LinUCB meta-algorithm* (Sec. 4). The cited work by Foster et al. turns *any online predictor* (with guarantees) into a bandit/RL algorithm (with guarantees) *via the E2D meta-algorithm*. While Foster et al. aim to establish a complexity measure for general interactive decision making, we focus on providing as tight as possible confidence statements for a given bandit task. There are many further differences between both works in the scope and in the techniques.\n\nThank you for pointing out the typos.\n\nWe hope that this addresses the reviewer's points. We are open to discussion."}]

Author rebuttal:

Meta-review: This paper proposes novel confidence bounds form martingale sequences motivated by UCB-type algorithms for contextual bandits, in the spirit of the seminal work of Abbasi-Yadkori et al. While the method also leverages mixing distributions to obtain any-time bounds via Ville’s inequality, these mixing distributions are potentially data-driven, opening the door to empirical Bayes type estimators. Even without these improved predictors, they demonstrate data-dependent and independent regret bounds using their new bounds, and demonstrate empirically that choosing data-dependent predictors can improve performance (in E.2). While regret for contextual bandits is the main motivation, the tools introduced in Abbasi-Yadkori et al have found very broad applications and this work is sure to expand this scope even further.
Decision: Accept (oral)