Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits
Authors: Yuwei Luo
Mohsen Bayati
Venue: ICLR 2025 Poster (2025)
Keywords: Linear bandit
Thompson sampling
Greedy
Data-driven exploration
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: This paper is motivated by recent research in the $d$-dimensional stochastic linear bandit literature, which has revealed an unsettling discrepancy: algorithms like Thompson sampling and Greedy demonstrate promising empirical performance, yet this contrasts with their pessimistic theoretical regret bounds. The challenge arises from the fact that while these algorithms may perform poorly in certain problem instances, they generally excel in typical instances. To address this, we propose a new data-driven technique that tracks the geometric properties of the uncertainty ellipsoid around the main problem parameter. This methodology enables us to formulate a data-driven frequentist regret bound, which incorporates the geometric information, for a broad class of base algorithms, including Greedy, OFUL, and Thompson sampling. This result allows us to identify and ``course-correct" problem instances in which the base algorithms perform poorly. The course-corrected algorithms achieve the minimax optimal regret of order $\tilde{\mathcal{O}}(d\sqrt{T})$ for a $T$-period decision-making scenario, effectively maintaining the desirable attributes of the base algorithms, including their empirical efficacy. We present simulation results to validate our findings using synthetic and real data.

Published as a conference paper at ICLR 2025
GEOMETRY-AWARE APPROACHES FOR BALANCING PERFORMANCE AND THEORETICAL GUARANTEES IN LINEAR BANDITS
Yuwei Luo, Mohsen Bayati
Graduate School of Business, Stanford University {yuweiluo, bayata (ruue
ABSTRACT
This paper is motivated by recent research in the d-dimensional stochastic linear bandit literature, which has revealed an unsettling discrepancy: algorithms like Thompson sampling and Greedy demonstrate promising empirical performance. yet this contrasts with their pessimistic theoretical regret bounds. The challenge arises from the fact that while these algorithms may perform poorly certain problem instances, they generally excel in typical instances. To address this, we propose a new data-driven technique that tracks the geometric properties the uncertainty ellipsoid around the main problem parameter. This methodology ables us to formulate a data-driven frequentist regret bound, which incorporates the geometric information, for broad class of base algorithms, including Greedy, OFUL,, and Thompson sampling. This result allows us to identify and "course- correct" problem instances in which the base algorithms perform poorly. The course-corrected algorithms achieve the minimax optimal regret of order ((d/T) for 7-period decision-making scenario, effectively maintaining the desirable at- tributes of the base algorithms,, including their empirical efficacy. We present simulation results to validate our findings using synthetic and real data.
INTRODUCTION
Multi-armed bandits (MABs) provide a framework for studying the inttorattio-explotattiii trade- off in sequential decision-making, where a decision- maker selects actions and observes uncertain rewards. This extends to contextual bandits with features
covariates, as shown in numerous applications (Langford & Zhang 2008 Li et al., 2010 Tewari & Murphy) 2017; Zhou et al. 2020]] Villar et al. 2015; Bastani & Bayati 2020 Cohen et al.) 2020). This paper focuses on a well- studied class of models that captures both MABs and contextual bandits special cases while being amenable to theoretical analysis: the stochastic linear bandit (LB) problem. In this model, the problem parameter 0* represents an unknown vector in Rdd while the actions, also vectors in Rdd yield noisy rewards with a mean equal to the inner product of 0* and the chosen action. The objective of policy is to maximize the cumulative reward based on the observed data up to the decision time. The policy's 's performance is measured by the cumulative regret, which quantifies the difference between the total expected rewards achieved by the policy and the maximum achievable expected reward.
Achieving this objective necessitates striking balance between exploration and exploitation. In the context of LB, this entails selecting actions that aid in estimating the true parameter 6* accurately while obtaining optimal rewards. Various algorithms based on the optimism principle have been developed to address this challenge, wherein the optimal action is chosen based on the upper con- fidence bound (UCB) (Lai & Robbins 1985] Auer 2002, Dani et al. 2008 Rusmevichientong & Tsitsiklis 2010). Another popular strategy Thompson sampling (TS), a Bayesian heuristic intro- duced by Thompson (1933) that employs randomization to select actions according to the posterior distribution of reward functions. Additionally, the Greedy policy that selects the myopically best action is shown to be effective in contextual bandits (Kannan et al. 2018 Raghavan et al. 2018
Hao et al. 2020 Bastani et al. 2021)

---

Published as a conference paper at ICLR 2025
In the linear bandit setting, two regret types are considered. Bayesian regret treats parameter 0* as a random variable with a prior distribution, averaging regret over noise, algorithm randomness, and parameter randomness, measuring expected performance across parameter realizations. Russo & Van Roy 2014)) and Dong & Van Roy (0018) establish an (dvVT) upper bound for the Bayesian regret of the Thompson Sampling (TS) heuristic, referred to as LinT'S, matching the minimax opti- mal bound by Dani et al. (2008). Here, O denotes asymptotic order up to polylogarithmic factors. Frequentist regret assumes fixed unknown parameter 8*, averaging only over noise and algorithm randomness. The OFUL algorithm (Abbasi- Yadkori et al. 2011) achieves an optimal (dvTT) frequentist regret bound. However, TS-Fireq, a frequentist LinTS variant with inflated posterior vari- ance, only achieves (d))TT) (Agrawal & Goyal 2013 Abeille et al. 2017). suboptimal by factor vd. Hamidi & Bayati (220a)) confirms this inflation is necessary and LinTS's frequentist regret cannot be improved. The Greedy algorithm lacks theoretical guarantees for linear bandit problems [Lattiore & Szepesvari 2017). suggesting both LinTS and Greedy may perform suboptimally.
Despite the theoretical gaps, LinTS demonstrates strong empirical performance (Russo al. 2018 suggesting posterior distribution inflation may be unnecessary in most scenarios. Similarly, the Greedy algorithm performs well in typical cases (Bietti al.] [202T). While optimism- based al- gorithms are computationally expensive (generally NP-hard (Dani et al. 2008: Russo & Van Roy] 2014 Agrawal, 2019)), LinTS and Greedy maintain computational efficiency. This disparity be- Tween theoretical, computational, and empirical performance prompts two questions: Can we iden- tify problematic instances for LinTS and Greedy in a data-driven way and apply -ourreecorrectton" to ensure competitive frequentist regret bounds? Can this be achieved while preserving their empir- ical performance and computational efficiency? In this paper, we provide positive answers both questions. Specifically, we make the following contributions.
1. We develop a real- tall-tmmegee geometric analysis technique for the d- d-dimensional confidence ellipsoid surrounding 0* This method is crucial for maximizing the use of historical data, advancing be- yond methods that capture only limited information from the confidence ellipsoid, such as a single numerical value. Consequently, this facilitates more precise "course-correction".
2. We introduce a comprehensive family of algorithms, termed POFUL (encompassing OFUL, LinTS, TS-Freq and Greedy specific instances), and derive general, data-driven frequentist regret bound for them. This bound is efficiently computable using data observed from previous decision epochs.
3. We introduce course-correcte variants of LinTS and Greedy that achieve minimax optimal fre- quentist regret. These adaptations maintain most of the desirable characteristies of the original algorithms.
1.1 OTHER RELATED LITERATURE
Our work is closely related to three main research streams: methodological foundations of lin- ear bandits, bandit algorithms utilizing spectral properties, and data-driven exploration techniques. While these works share some similarities with our approach, we highlight the key differences and the unique aspects of our methodology.
From a methodological perspective, our regret analysis builds upon the foundations laid by Abbasi- Yadkori et al. 1). Agrawal & Goyal (2013), and Abeille et al. (2017). However, a key distin- guishing factor is that our approach does not rely on optimistic samples, which is departure from previous methods. This means that the algorithms we study do not always choose actions that are expected to perform better than the true optimal action. By allowing non-optimistic samples, we avoid the need to inflate the posterior distribution, a requirement in the works of Agrawal & Goyal (013)) and Abeille et al. (2017).
Our use of spectral information in bandit algorithms bears some resemblance to the study of Spec- tral Bandits (Valko et al., 2014 Kocák et al., 2014 Kocák et al. 2020 Kocák & Garivier 2020). These works represent arm rewards smooth functions to improve algorithmic performance and obtain regret guarantees independent of the number of ac- tions. In contrast, our approach exploits the spectral properties of the action covariance matrix, which is distinct from graph spectral analysis. Moreover, our research tackles the broader context of stochastic linear bandits without assuming any low-rank structure.
graph, leveraging low-rank structures
2

---

Published as a conference paper at ICLR 2025
Our work also shares conceptual similarities with research on exploration strategies (Russo & Van Roy] 2016 Kirschner & Krause, 2018) and data-driven exploration reduction (Bastani et al, methodology and data uti- lization differ significantly. For instance, [Bastani et al. 202T)) focuses on the minimum eigenvalue of the covariance matrix, a single-parameter summary of the observed data, while/Hamin & Bayati (222bb) uses information from one-dimensional reward confidence intervals. The work of Hamidi & Bayati (2020a) is more closely related ours, as it employs spectral information to improve the performance of Thompson Sampling in linear bandits. They use single summary statistic called the thinness coefficient decide whether to inflate the posterior. In contrast, our approach leverages the full geometric details of the d-dimensional confidence ellipsoid, harnessing richer geometric information.
2021 Pacchiano et al. 2020; Hamidi & Bayati 22200a b). However,
SETUP AND PRELIMINARIES
Notations. We use || to denote the Euclidean 2-norm. For symmetric positive definite matrix A and vector r of proper dimension, we let ||=]|A == Vx Az be the weighted 2-norm (or the A-norm). We let .) denote the inner product in Euclidean space such that (ær, y) = x.' y. For d-dimensional matrix V, we let (V) 2 X2 2
\d(V) be the eigenvalues of V arranged
in decreasing order. We let Ba denote the unit ball in Rd, and Sa- (x R ||a||| 1] denote
.., the (-) notation to suppress problem-dependent constants, and the (-)) notation further suppresses polylog factors.
the unit hypersphere in IRd, For an interger N 2 1, we let [N] denote the set {1, 2,..,, N). We use
Problem formulation and assumptions. We consider the stochastic linear bandit problem. Let 0* Rd be a fixed but unknown parameter. At each time [2'. a policy selects action 3; from a set of action X C. Rd according to the past observations and receives a reward = (ax, 0*) + et, where E, is mean-zero noise with distribution specified in Assumption 3 below. We measure the performance of with the cumulative expected regret R(T) = ΣT (2t, 0*) 0*), where ry is the best action at time t, i.c., 27 arg max (x, 8r) Let Fi be o-algebra generated by the history (I1, f1,- ......,..................... Ft, r²)) and the prior knowledge, Fo. Therefore, (Fi)e20 forms a filteration such that each Fr encodes all the information up to the end of period t.
We make the following assumptions that are standard in the relevant literature. Assumption 1 (Bounded parameter). The unknown parameter 0* is bounded ||0+1| S S, where > 0 known.
Assumption 2 (Bounded action sets). The action sets {X1 are uniformly bounded and closed subsets of Rd, such that || I X, for all x E Xe and all t e [T]. where Xi's are known and sup121 {X,}
Assumption 3 (Subgaussian reward noise). The noise sequence {Er)121 is conditionally mean- zero and R-subgaussian, where R is known. Formally, for all real valued X, E [F]] I exp RX2R2 /2). This condition implies that E Fc] = for all t 1.
2.1 REGULARIZED LEAST SQUARE AND CONFIDENCE ELLIPSOID
In this subsection, we review the useful frequentist tools developed by Abbasi- Yadkori et al. (2011) for estimating the unknown parameter 6* in linear bandit (LB) problems.
Consider an arbitrary sequence of actions (II,..., xz) and their corresponding rewards (r1..... r
In LB problems, the parameter 0" is typically estimated using the regularized least squares (RLS)
estimator. Let Aveg be a fixed regularization parameter. The sample covariance matrix Vn and the
RLS estimate θ, are defined follows:
V = Xrog Ia
0,
V.
T.
(1)
The following proposition from Abbasi- Yadkori et al. 2011 establishes that the RLS estimate 0, concentrates around the true parameter (/* with high probability.
3

---

Published as a conference paper at ICLR 2025
Proposition 1 (Theorem in Abbasi- Yadkori al. (2011) ). Let å E (0.1) 1) be fixed confidence level. Then, with probability at least 1 1- 8, holds for all R that
110 - vv,, S pm, 11, -0>1 S |
BRLS 1,6,
where the confidence bound BRLS defined as
RV 2og(oogm log(Ang + 1)d/2 4/2 8-1 VnngS.
(2)
Proposition 1 Jenalles to construct the following sequence of confidence ellipsoids.
Definition 1. Fix E (0, 1). We define the RLS confidence ellipsoid as
gRL3 Am6
E R 110 -Oell S B
The next proposition, known the elliptical potential lemma, plays central role in bounding the regret. This proposition provides the key element in the work of Abbasi-Yadkori et al.) (201 showing that the cumulative prediction error incurred by the action sequence used to estimate 0" is small.
Proposition 2 (Lemma 11 in Abbasi- Yadkori al. (011)). If Amw 1, for arbitrary sequence del(V.-1)
Ufi....,44h it holds that E | vally.-> S log det
I 2d log(1 + x
3 POFUL ALGORITTMM
In this section, we introduce POFUL (Pivot OFUL), a generalized framework of OFUL. This frame- work enables a unified analysis of frequentist regret for common algorithms.
At a high level, POFUL is designed to encompass the exploration mechanism OFUI. and LinTS. POFUL takes input sequence of inflation parameters (4))T(T), feasible (randomized) pivots (Or)ertr and optimism parameters (Tehe(T)) The inflation parameters are used to construct confi- dence ellipsoids that contain {0. (ee) with high probability. This formalized the next defini- tion.
Definition 2. Fix E 10,1) and 8' = 8/2T. Given the inflation parameters {4herr we call random variables (fehretr) feasible pivots for all [T], P0ù EPVT FFl 2 8', where we define the "pivot ellipsoid" as EPVT
Amm
L, = (0 Rd 0 0.llv, S t,6,
At each time I, POFUL. chooses the action that maximizes the optimistic reward
BRLS ARLS arg max (x, 0,) + Tell=lly.-1 "'a A'
xe
as shown in a pseudocode representation in Algorithm and illustrated in Figure la
Recall OFUL encourages exploration by introducing the uncertainty term Ti 1 reward, while LinTS explores through random sampling within the confidence ellipsoid. We let
B 7,8",Am, Aus in the
CPVT and maximize the optimistic POFUL select arbitrary pivot (which can be random) from &,,6' Amp
reward to encompass arbitrary exploration mechanisms within PPTT
We demonstrate that POFUL encompasses OFUL, LinTS, TS-Freq, and Greedy as special cases, as illustrated in Figure lb
Example (OFUL). For stochastic linear bandit problems, OFUL chooses actions by solving the optimization problem maXzeX, (I, 0,) + |æI|y | 13,18 >e.' Therefore, OFUL is specially case of POFUL where 4 0, Tt and 02 Or the center of the confidence ellipsoid, for all (T].
Before describing how TS can be derived as instance of POFUL., we introduce definition.
Definition 3. Let E (0, 1). We define DSA(6) as a distribution satisfying F,-DDS(() ||l//| s 1]
1 5.
4

---

Published as a conference paper at ICLR 2025
Algorithm POFUL
Require: T, 8, Argg (uheem. { telr
Initialize V/ - Arogla. 01 + 0, 8' + 6/27
fo I..... do
Sample feasible pivot 0. with respect 4 according Definition
24 f- arg max,ex, (ar, 0e) Ti rel1= 1 A,0
RRLS
Observe reward Tt TT
Ve+1 V42 + Fyph
B.t11 + V El T.T...
end for
Example 2 (TS), Linear Thompson Sampling (LinTS) algorithm is a generic randomized algorithu that samples from distribution constructed from the RIS estimate each step. time LinTS samples as 02 - 02 + +
Pt.8" v,-1/21p, where 8' = 6/2T, 9 is inflation parameter controlling the scale the sampling range, and Tt is random sample from a normalized sampling distribution (8'( that concentrates with high probability. Lin''S is special case of POFUL where 4 1, 0 and 0, 0, L t,5'
1 gRLS
The Setting = Ö(1) corresponds to the original LinTS algorithm, while setting = O O(vd) corresponds to the frequentist variant of LinTS studied in Agrawal Goyal (2013); Abeelle et (2017), namely TS-Freq. This means TS- TS-Freq inflates the posterior by a factor of order vd.
RRLS
Vr 1/2 V/-
Example 3 (Greedy). Greedy is special case of POFUL with 4 = Th =0, 0. =0=
0c. Vl.
4 FREQUENTIST REGRET ANALYSIS POFUL
In this section, we present the frequentist regret analysis of POFUL algorithms. Details of the proofs deferred to the longer version of the paper Luo & Bayati (023). We first introduce high-probability concentration events.
Definition 4. Fix 8 1) and 8' = 8/2TT. We define 3PVT = Pi, 1,3.t.. ''in'' A. = (V5S St:
JRLS
|00 lIv. S 3. } A. = (Vs t 100 dellv. I SP. Amg
and Ae == A. A
Proposition 3. Under Assumptions 7 and we have IP [Ar] 2 1- 8.
4.1 AN DATA-DRIVEN REGRET BOUND FOR POFUL
the following, we condition on the event AT which holds with probability 8. The following proposition bounds the instantaneous regret of POFUL.
POFUL
M
1996
(6.
-8
x)
(x
OPUT.
(6,
( (
Groody
Parameter space: R
Reward space:
(b)
Figure I: (a) POFUL algorithms illustration for general 4; and 7;. (b) Special cases: OFUL (4 = 0,
1). TS (7: 0), and Greedy (4 T 0).
5

---

Published as a conference paper at ICLR 2025
Proposition 4. Suppose 8
CRLS A,. Aas
and 0s E 21,8' it holds that
GRLS 0- (Tt, ) S (1 ++)l=;; ll llv, P1,8' Ang (1 + + rc) re)l(Talll; 11,00 Ang
Note that this upper bound is different from what's used in the potimism-basehe methods (Abbasi- Yadkori et al. 2011 Agrawal & Goyal 2013: Abeille et al. 2017). we reproduce their upper bound and discuss the relationship of our method and theirs in the longer version of the paper Luo & Bayati (2023).
On the right-hand side of equation 4 since the oracle optimal action sequence (xj he(r is unknown to the algorithm and is different from the action sequence { hejoy played by POFUL, one cannot apply Proposition to bound the summation Σi= |
| and get an upperbound of the regret.
To address this, the key point to connect ( and (xt (#) with V -norm. This motivates the following definition.
Definition 5. For each t 2 1, let He and ot respectively denote the action chosen by POFUL and the optimal action. We define the uncertainty ratio at time as ar ||2 1/1iaall, We also define the (instantaneous) regret proxy at time L as jet == 01e(1 4-4-44100 1-4-7711 T.) - 1
7
Note that (z 8*) S || GRLS Awg holds with high probability, we have that || essen- tially determines the length of the confidence interval of the reward (x, 07). Hence, at serves as the ratio of uncertainty degrees of the reward obtained by the optimal action 27 and the chosen action Tz.
The intuition behind the definition for μ4 is constructing regret upper bound similar to that of OFUL. Specifically, Proposition 4 indicates (xz, 0*) (Te, 6*) S He Te - 1B 1,0 Aws and we can check that the instantaneous regret of OFUL satisfies (zž. 6*) (T 0*) S 21l B Auy this sense, μ4 is a proxy of the instantancous regret incurred by POFUL at time t. Morcover, OFUL can be regarded as POFUL algorithm whose (4 is fixed 2, and we could extend the definition of ag to OFUL by solving μ ar + 4 Tτ) + 1 + 4 + Tr and set a = for all t [2] for OFUL (recall that in OFUL,
RLS
RRLS In
0 and т for all E [T]).
The following Theorem connects {1r herr and R(T). It provides an oracle but general frequentist regret upper bound for all POFUL algorithmss.
Theorem (Oracle frequentist regret bound for POFUL). Fix 8 E (0, 1) and let 8' 8 8/2T. Under Assumptions 7 and with probability - 8, POFUL. achieves a regret of
T
R(T) < 2d Σ
log
1+
RLS 3 Am Am
(S)
Areg
We call Theorem 1 an oracle regret bound as {ueltett for general POFUL depends on the unknown system parameter 0" In general, they cannot be calculated by the decision-maker Nevertheless, note that 4s and Tt are chosen by the decision-maker when we have computable upper bounds {ā, he(r) for {ar het]). using μ² < 22, 72 2 221 + +4(1++++)) +.)2 we could calculate upper bounds for {ur hE as well. Consequently, Theorem [ instantly turns into data-driver regret bound for POFUL and could be utilized later for course correction, which will be the aim of the next section. When we additionally know that 1 + 4
Remark 1.
is non-negative, we would use the equality μt = (1(1 + 4 1E--7) Te) + + 4t + Ti directly for the bound.
Remark the Discussion section Abeille et al. (2017). the authors introduce a concept similar to the reciprocal of our at, They suggest that the necessity of proving LinTS samples are optimistic
could be bypassed if for some > 0 LinTS samples o, such that ||2 (e:) (ly) all2* (0t)lv
with constant probability, where x² (0t) and x" (0t) represent the optimal actions corresponding to 9, and 0. respectively. They pose this as an open question regarding the possibility of relaxing the requirement of inflating the posterior. in the following section, provide positive answer this question by studying the reciprocal of their a using geometric arguments. This investigation offers an explanation for the empirical success of LinT'S without the need for posterior inflation.

---

Published as a conference paper at ICLR 2025
5 A DATA-DRIVEN APPROACH
In this section, present the main contribution of this work which provides data-driven approach to calibrating POFUL. Note that 6 and т are parameters of POFUL that can be controlled by decision-maker, the essential point is find computable, non-trivial upper bound &r for the uncertainty ratio at,, which turns into an upper bound fig for the regret proxy μr that's deeply related the frequentist regret of POFUL.
We focus on scenarios where TS-Freq, as well as Greedy standard algorithms still lacking theoretical regret guarantees. Below, we construct upper bounds {āe (r) for the continuous-action scenario. Bounds for discrete-action scenarios appear in the longer version of the paper [uo & Bayati (2023).
0 for all E [2]. These include LinTS and variants such as
5.1 CONTINUOUS ACTION SPACE
Our strategy capitalizes geometric insights related the properties of the confidence ellipsoids, providing upper bounds that can be computed efficiently. For the sake of better illustration, we consider X; S for all [2] for this scenario, where Sa-1 { E H || 1} is the unit hypersphere in Rd. This a standard example of continuous action space, and the same as the setting considered in Abeille al. (2017). We remark that for this specific setting, the problem still hard. This because we don't have a closed- foosed-form solution for the set of potentially optimal actions.
In this setting, the optimal action x (1) = arg max,ex, (r. 0) takes the form 2 (0) 0/||@||- To upper bound ag consider respectively the smallest and largest value of [|)] for in the confidence ellipsoids of 0, namely, 1,8', Dea t, Specifically, we have
eRLS and gPVr
SuPPEERLe
| (0)lvv,
a S ....Ang .ang
(6)
infogePvT
As is illustrated in Figure 2 the set of potentially optimal actions C. is the projection of the confi- dence ellipsoid & onto S It's hard to get closed-form expression for C, so we cannot directly calculate the range of V, norm of actions in C,. Nevertheless, when POFUL has implemented suf- ficient exploration so that & is small enough, C, concentrates accordingly to small cap on St-1- Therefore, it is possible to estimate the range of the Vę-norm by employing geometric reasoning. Subsequently, this estimated range will be utilized to ascertain the range of the V--
andectes
(a)
(b)
Illustration of potentially optimal actions set C. in R², (a): C₁ is Ey's projection onto S (b): As more data is collected, & shrinks (colors show exploration levels). Potentially optimal actions point in similar directions, determining their V--ormm This suggests their Vi-orm range could be estimated geometrically.
Figure 2:
The main theorem derives upper bound for az based on this idea.
Theorem 2. Suppose X; = Sa-1 for all i. E [7]. Define = @11 (3RLS 2 ( +
GRLS PC6 A... (>a(V.)) M. -10.11/3// (100,11, / (8PVT (rn }2). Let l E [d] be the integer that satisfies

---

Published as a conference paper at ICLR 2025
(v) E M, S X++1 Define Pi,
1. Ans and
(V) + (V)) m (VV))
if 1110ollv 2 PI,8
4
Na (V)),
if Vileellv.
BRIS Pi
(Ve'(V)++ Xxt1 M (v)))
if 0elll 2 B8.6'
1
A (Vi),
if 11 < BPVI
Then for all t E (T). conditioned on Ag Ar, it holds for all 8 S that 02 S a. == ///V..
To better understand what Theorem 2 implies, we discuss some special cases and provide empirical validations for them in the longer version of the paper Luo & Bayati (2023).
6 A META-ALGORITHM FOR
This section demonstrates how the data-driven regret bound can enhance standard bandit algorithms. We propose meta-algorithm that creates course-corrected variants of base algorithms, achieving minimax-optimal frequentist regret guarantees while preserving most original characteristics, in- cluding computational efficiency and typically low regret.
We take LinTS as an example of the base algorithm, and propose the algorithm Linear Thompson Sampling with Maximum Regret (Proxy) (TS-MR). The idea is to measure the performance of LinTS using be and avoid bad LinTS actions by switching to OFUL actions. Specifically, at each time t, TS-MR calculates the upper bound ea and compares it with preset threshold μ.. If jae μ4, LinTS might be problematic and TS-MR takes an OFUL action to ensure a low instantaneous regret; if The S μ. TS-MR takes the LinTS action. We remark that setting 4 0 for all / [T) yields the corresponding Greedy-MP algorithm. The pseudocode is presented in the longer version of the paper Luo & Bayati| (2023).
Remark 3. Computing The primarily requires SVD decomposition of the sample covariance matrix g=1 IzZ, updated via rank-one matrices, its SVD can be efficiently updated (Gandhi & Rajgor 2017,, preventing computational bottlenecks.
Vi Since V, Are + E
By design, course-corrected algorithms ensure that μ4 max 2} for all t E [T]. Substituting this upper bound into Theorem establishes that these algorithms achieve optimal frequentist regret, up to constant factor.
Corollary 1. TS-MR and Greedy-MR achieve frequentist regret of (m, 2)dTT).
In high-risk settings where LinTS and Greedy may fail, a small μ ensures TS-MR and Greedy- MR select more OFUL actions, promoting sufficient exploration. Conversely, low-risk settings where the original algorithms perform well, large µ favors TS and greedy actions, minimizing unnecessary exploration and reducing computational cost. In the longer version of the paper Luo & Bayati (2023), we show how impacts the fraction of OFUL actions in TS-MR and Greedy-MR and their performance. Results indicate that course-corrected algorithms maintain robustness across range of moderate μ values, suggesting that the precise selection of μ is unlikely to present significant practical concern.
7 SIMULATIONS
We aim to compare TS-MR, Greedy-MR, and key baseline algorithms, via simulation.
7.1 SYNTHETIC DATASETS
We conduct simulations on three representative synthetic examples. We average simulation results over 100 independent runs for each of the examples. The results are shown in Figure
8

---

Published as a conference paper at ICLR 2025
Example 1. Stochastic linear bandit with uniformly and independently distributed actions. We fix d = 50, and sample 8* Unif({e E | = =10)) on a sphere with fixed norm. At each time t, generate 100 ii.d. random actions sampled from Unif(Sx-1) to form X. This is basic example of standard stochastic linear bandit problems without any extra structure. We set the threshold μ for TS-MR and Greedy-MR. TS- TS-Freq shows pessimistic regret due to the inflation of the posterior, while other algorithms in general perform well.
Example 2. Contextual bandits embedded in the linear bandit problem (Abbasi-Yadie 2013). We fix = 50, and sample 0 ~ Unif( E |00 = 70)). At each time i, we first generate random vector uı (0, Is) and let Ft,i E R be the vector whose i-th block of size 5 is a copy of uy, and other components are O. Then X2 = (za,stig(10) is an action set of size 10, sharing the same feature u in different blocks. This problem equivalent
10-armed contextual bandit, We set μ 12 for TS-MR and Greedy-MR, In this setting, Greedy performs suboptimally due to lack of exploration for some arms. Nevertheless, Greedy-MR outperforms both Greedy and OFUL by adaptively choosing OFUL actions only when it detects large regret proxy ft..
Example 3. Prior mean mismatch (Hamidi & Bayati, 2020a). This is an example in which LinTS is shown to incur linear Bayesian regret. We sample 8 (mm133s Isa) and fix the action
set Xr = f0, Za, I for all t E [T]. where = - e:/ /3d, 2n = Eie v shown in Hamidi Bayati (202aa) that, when LinTS takes a wrong prior mean as input, it has a large probability to choose 22 = O, conditioned on _
E e/v3d. 3d.
Note that choosing the zero action brings no information update to LinTS, it suffers linear Bayesian regret when trying to escape from the zero action. We let m = 10 and set d = 10, so the problem is a 30-dimensional linear bandit. We set μ = 12 for TS-MR and Greedy-MR. We see both LinTS and Greedy incur linear regrets expected, while TS-MR and Greedy-MR, switch to OFUL adaptively to tackle this hard problem and achieve sublinear regret.
30000
Cooetyy
LX175
20090
Cendirvee
8000
GHUL
A3099
600
4000
AC000
4000
2000
1.3
2iice
1550
350g
(a) example 1
(b) example 2
(c) example 3
7S-4I
75-48 Gready 41
Preddo SToRU Axtoor C
Gready M1
0.20
8.00
1000
1200
2000
2000
250
430
Thme
(d) example 1
(c) example 2
(f) example 3
Figure 3: Simulation results on synthetic data. (a) - (c): Cumulative regret of TS-MR and Greedy- MR versus baseline algorithms. Shaded regions show +2 SE of mean regret. (d) -(f): Fraction of OFUL actions in TS-MR and Greedy-MR.
7.2 REAL-WORLD DATASETS
We explore the performance of standard POFUL algorithms and the proposed TS-MR and Greedy- MR algorithms on real-world datasets. We use three classification datasets from OPENML Car- diotocography. Japanese Vowels, and Segment, representing healthcare, pattern recognition, and computer vision domains. Following Bietti et al.] (202I): [astani et al. (02T), we convert these classification tasks contextual bandit problems and embed them into linear bandit problems in

---

Published as a conference paper at ICLR 2025
Example 2, Section 7.1 Each class becomes an action where the decision makerr receives binary reward (1 for correct classification, 0 otherwise) plus Gaussian noise.
We plot the cumulative regret (averaged over 100 runs) for all algorithms. Figure shows that for all real-world datasets: OFUL and TS-Freq perform poorly due to their conservative exploration; LinTS and Greedy are achieving empirical success even though they don't have theoretical guarantees; TS-MR and Greedy-MR retain the desirable empirical performance of LinTS and Greedy, while enjoying the minimax optimal frequentist regret bound.
Drocela
1200
Gaeely-M
1200
Oaentyy
Carsentive Bogrrt
1000
1000
T5
Curuanvve
DTU.
OFLL
DPLL
430
230
200
3400
200
3023
400
1853
Thme
(a) Cardiotocography dataset
(b) Japanese Vowels dataset
(c) Segment dataset
10
73-41
Prodbon orogg Katve
84
2.4
402
1400
1.00
200
1200
Thme
(d) Cardiotocography datasel
(e) Japanese Vowels dataset
(l) Segment dataset
Figure 4: Simulation results real-world datasets. (c): Cumulative regret of all algorithms.
Shaded regions show the 22 SE the mean regret. (d) - (f): Fraction OFUL actions of TS-MR and Greedy-MR.
Remark 4. Simulation results in Figures and ssow OFUL actions are primarily used in the early stages. This indicates: (1) Greedy-MR and TS-MR implement OFUL actions only when necessary, maintaining low OFULfractionn throughout most of the time horizon, substantially reducing com- putational cost; and (2) limited course-correcter exploration at the beginning efficiently remedies TS and Greedy in problematic instances.
CONCLUSION
In this work, we propose a data-driven framework analyze the frequentist regret of POFUL, a fam- ily of algorithms that includes OFUL, LinTS, TS TS-Freq, and Greedy as special cases. Our approach allows the computation tation, which subsequently informs the course-correction of the algorithm. Our technique conducts a novel real-time geometric analysis the d-dimensional confidence ellipsoid to fully leverage the historical information and might be of independent interest. As applications, and Greedy-MR algorithms that enjoy provable minimax optimal frequentist regret and demon- strate their ability to adaptively switch OFUL when necessary in hard problems where LinTS and Greedy fail. We hope this work provides a steady step towards bridging the gap between theoretical guarantees and empirical performance of bandit algorithms such LinTS and Greedy.
data-driven frequentist regret bound for POFUL during implemen-
propose TS-MR
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Yasin Yadkoi. Online learning for linearly parametrized control problems. 2013.
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp.
2011.
Mare Abeille, Alessandro Lazaric, et al. Linear thompson sampling revisited. Electronic Journal of Statistics, 11(2)551555517,, 2017.
Shipra Agrawal. Recent Advances in Multiarmed Bandits for Sequential Decision Making, chapter 7, pp. 188. 2019. doi: stg//oo/abs/// 10.
2019.0204. URL.tttps:/ppussnn ine. informs. 2019.. 0204
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff'.. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Con- ference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 127 Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL httts:://proceeeeeeeee mlr. pttps/////////gaaaaa3 html
Peter Auer. Using confidence bounds for exploitation-explorrtion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-294, 2020. doi: 10.1287/0pre.2019.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-free algorithms for contextual bandits. Management Science, 1299)112-- 2021. doi:
Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. Journal of Ma- chine Learning Research, 22(133):1 -9, 2021. URL http: jml:://mmmrr.rr wwwpll/.or//ppppppr.
863.863.htl
Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature- dynamic pricing. Management Science, 66( 11:533-55,2,, 2020, doi: 10.1287/mms.22119.444 URL Utthttps:: httptttstsss....o/ orgg 10. 10l.1227/maa mt1.9/mmnc...1......
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In COLT, 2008.
Shi Dong and Benjamin Van Roy. An information-theeortiec analysis for thompson sampling with many actions. In Advances in Neural Information Processing Systems, pp. 4157-4165, 2018.
Rainik Gandhi and Amoli Rajgor. Updating singular value decomposition for rank one matrix per- turbation. arxiv preprint 1707.0777.0866 2017.
Nima Hamidi and Mohsen Bayati. On frequentist regret of linear thompson sampling, 2020a.
Nima Hamidi and Mohsen Bayati. A general theory of the stochastic linear bandit and its applica- tions. arXiv preprint arXiv:2002.05152. 2020b.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit, 2020.
Sampath Kannan, Jamie H Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Advances in Neural Information Processing Systems, pp. 2227-2236. 2018.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with het- eroscedastic noise. In Proc. International Conference on Learning Theory (COLT), July 2018.
Tomášs Kocák, Rémi Munos, Branislay Kveton, Shipra Agrawal, and Michal Valko. Spectral bandits. J. Mach. Learn. Res., 21(1), jan 2020. ISSN 1532-4435.
Tomáš Koeák and Aurélien Garivier. Best arm identification in spectral bandits, 2020.

---

Published as a conference paper at ICLR 2025
Tomáš Kocák, Michal Valko, Rémi Munos, and Shipra Agrawal. Spectral Thompson Sampling. 28(1), 2014. doi: 122.1609aaai..2281.9000 [aL/attps://oss.o aaai. orq/ iidex.dexx.. php/ BAA//articcll//ew///000
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules, Advances in applied mathematics, 6(1):4-22, 1985.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In C. Platt, Koller, Singer, and S. T. Roweis (eds.), Advances in Neural Information Processing Systems 20, pp. 817-824. Curran Associates, Inc., 2008.
Tor Lattimore and Csaba Szepesvari. The end of optimism? asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pp. 728-737. PMLR, 2017.
Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pp. 661-670. ACM, 2010.
Yuwei Luo and Mohsen Bayati. Geometry-awarr approaches for balancing performance and theo- retical guarantees in linear bandits. arXiv preprint arXiv:2306. 14872, 2023.
Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett. Regret Bound Balancing and Elimination for Model Selection in Bandits and RL. arXiv e-prints, art arX:v:2012.13045, December 2020. doi: (0.48350/arX...20222.33.
Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. The extemnalitiss of exploration and how data diversity helps exploitation, 2018.
Paat Rusmevichientong and John Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411, 2010.
Daniel Russo and Benjamin Van Roy. Learning optimize via posterior sampling. Mathematics of Operations Research, 39(4))1221-122)) 2014. doi: 10.12877/moo.22144.0666
Daniel Russo and Benjamin Van Roy. An information-theorrtiic analysis of thompson sampling. The Journal of Machine Learning Research, 17(1):2442-2477 2016.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Fowndations and Trends in Machine Learning, 11(1):1-96, 2018. URL
http::/dx.coo doi www.oogg/.0...o... 1ew. /2200000720000
Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health, pp. 495-5112 517. Springer, 2017.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285222 294, 1933.
Michal Valko, Remi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph functions. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 46-54, Bejing, China, 22-24 Jun 2014. PMLR. URL lattps://proceediinng .mlr. stress/322vvakko44 html
Sofía S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
Wenbin Zhou, Lihong Li, and Quanquan Gu. survey on contextual multi-armed bandits. arXiv preprint arXiv:2004.13/1 33/36, 2020.
12


Reviews:
[{"review_id": "iQEzqh6mOr", "reviewer": "Reviewer_5WZb", "summary": "This paper studied the classical linear bandit problem. It proposed the POFUL algorithm which can be specified to be LinTS, LinUCB and greedy algorithms with different parameters respectively. It analyzed its regret and evaluated its performance with numerical experiments. This paper also considered the continuous action space and the instances with proxy.\n\n\n======\n\nAfter rebuttal: I prefer to keep the score.", "questions": "Please refer to the *Questions* section.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provided a more general algorithm for regret minimization in linear bandits and another aspect to understand the efficient algorithms.\n1. The numerical experiments are well designed as different types of bandit examples are considered.", "weaknesses": "1. The author(s) may consider to place the comparison among Theorem 1 and results from existing papers in the main paper. The comparison is not clear at first glance. \n1. Sections 6 and 7 indicate that a preset threshold $\\mu$ can clearly reduce the regret and Remark 3 discussed the choice of $\\mu$. However, I wonder under which types of real-life scenarios we can know $\\mu$ and what is the choice of $\\mu$ in simulations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RKdgljW5UF", "reviewer": "Reviewer_jV72", "summary": "This paper studies the $d$-dimensional stochastic linear bandit setting. It builds on several previous works, mostly on\n- the analysis from Abbasi-Yadkori et al. (2011) where they proposed an algorithm \"Optimism in the Face of Uncertainty  Linear Bandit Algorithm\" (OFUL) for which they derived a frequentist regret bound in $\\tilde{O}(d\\sqrt{T})$;\n- the work from Agrawal \\& Goyal (2013) and Abeille et al. (2017) that studied the frequentist variant of LinTS, referred to as TS-Freq, and showed that its frequenist regret is upper bounded in $\\tilde{O}(d^{3/2}\\sqrt{T})$. The extra factor $d^{1/2}$ has latter confirmed to be necessary by Hamidi \\& Bayati (2020);\n- the works from Russo \\& Van Roy (2014) and Dong \\& Van Roy (2018), who studied the Bayesian regret of the Thompson Sampling algorithm, referred to as LinTS and proved that it is upper bounded in $\\tilde{O}(d\\sqrt{T})$.\n\nBased on the last points regarding LinTS, the authors conclude that the algorithm performs well in most problem instances but suffers in unfavorable, unlikely settings. Their idea is then to propose a modified \"course-corrected\" version of LinTS and Greedy algorithms, that can switch to selecting OFUL actions under a criteria based on a geometric analysis the $d$-dimensional confidence ellipsoid. The resulting algorithms are called respectively \"Linear\nThompson Sampling with Maximum Regret (Proxy)\" (TS-MR) and Greedy-MR. Both algorithms retain the theoretical guarantees of OFUL algorithm while presenting some computational and performance advantages from the LinTS and Greedy method.", "questions": "Here is a list of suggestions for the authors. \n- A first suggestion is to include a proof of Corollary 1, if possible, in the main part of the paper. \n- A second suggestion is to include the pseudocode of the proposed methods TS-MR and Greedy-MR in the paper's main text.\n- Another suggestion concerns the experiments. The authors should provide enough material and explanations so that it is possible to replicate and verify the results of the simulations. We suggest the authors to share the code they used to generate the simulations, as well as to include more details about the experiments in the Appendix: \n  - the pseudocode and parameters used for the TS-Freq algorithm\n  - the pseudocode and parameters used for the OFUL algorithm\n  - the pseudocode and parameters used for the Greedy algorithm\n  - the values of the parameters ($\\delta$, $\\iota_t$, $\\lambda$) for the TS-MR algorithm as well as explanations regarding the distribution $\\mathcal{D}^{SA}(\\delta')$.\n    The authors should also include references and explanations regarding \"the standard approach in the literature that converts classification tasks to contextual bandit problems\". Note that there is a typo on line 500 as there is no Example 2 in Section 6.\n    Ideally, the authors should also perform experiences to illustrate the tuning of the parameter $\\mu$ and its influence on the performance of the algorithm and include comparisons to algorithms that are not part of the proposed method, such as UCB. \n- The authors should also improve the readability of the Figures in the main body of the paper as the font size is too small. They should also provide explanations in Figures 3 (b) and (C) regarding what seems to be confidence intervals.  \n- There are some notations throughout the paper that are either not defined or used before they were defined: \n  - the notations $\\lambda_1,\\ldots,\\lambda_d$ and $\\lambda_2^{-\\frac{1}{2}}(V_t)$ used in Theorem 2 but are not defined. There is also some confusion with both the notation $\\lambda$ being used as a regularization parameter. We note that both the notation $\\lambda_d$ and $\\lambda_d(V_t)$ are present in the paper. It is not clear if it refers to the same quantity.\n  - there seems to be a typo on line 423 in Theorem 2, as the indexes $k$ and $k+1$ are used but do not refer to anything. The authors should bring clarification.\n  - the function $x^\\star_t(\\theta)$ is used on line 351 but only defined on line 383. \n  - the notation $\\equiv$ is used but not defined. \n  - the notation $\\mathcal{S}_{d-1}$ is used but not defined. It is unclear whether it refers to the $d$-dimensional unit sphere or a sphere of radius $S$ centered on the origin.\n  - the notation $\\beta^{RLS}_t(\\delta)$ hides the dependency on the parameter $\\lambda$.\n  - it is not explained how $\\hat{\\mu}_t$ relates to $\\hat{\\alpha}_t$ on line 364.\n- Other suggestions include: \n   - avoiding abbreviations such as \"we'll\" on line 368 and prefer the full expression\n   - citing reference on line 370 to explain the \"large regret proxies and computational inefficiencies seen in OFUL when determining the action\".\n   - it is unclear from Example 2 how to set the variables $\\iota^{TS}$ such that POFUL matches LinTS. \n   - Assumption 3 could be renamed to \"Subgaussian reward noise.\"\n   - rephrase line 390, \"As is illustrated on Figure 2.\" as this phrase lacks a subject and is therefore not a proper sentence. \n   - correct the typo on line 1048: \"We ser $\\mu$\".", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strength of the paper is to propose a modification of the LinTS and Greedy algorithms, two well studied algorithms for solving $d$-dimensional stochastic linear bandit problems. The modification is based on the work from Abbasi-Yadkori et al. (2011) and their algorithm \"Optimism in the Face of Uncertainty  Linear Bandit Algorithm\" (OFUL) which enjoys frequentist regret bound in $\\tilde{O}(d\\sqrt{T})$. The authors resulting algorithms \"Linear\nThompson Sampling with Maximum Regret (Proxy)\" (TS-MR) and Greedy-MR, can both switch from their respective methods to OFUL algorithm under some criteria. The authors derive frequentist regret bound in $\\tilde{O}(d\\sqrt{T})$ for both algorithms and illustrate their performance under some numerical experiments.", "weaknesses": "Although the main ideas of the paper are interesting, there are a few points that could be improved, such as listed below.\n\n- The main weakness concerns the reproducibility of the experiments. The authors provide few explanations regarding the experiment setup in the paper and no information regarding the algorithm's parameters and implementation. They did not provide their code, and the details they give in the Appendix are not sufficient to reproduce the same experiments. Therefore, it was impossible to assess the soundness of the simulation results. \n- A second weakness concerns the experimental comparison. The authors should have included experiments assessing the influence of the algorithm parameter $\\mu$ on the performance. They authors mention that they \"aim to compare TS-MR, Greedy-MR, and key baseline algorithms, via simulation\" but the key baseline algorithm they compared their method with are the very same algorithm their method is based upon. It would have been for the authors to include a comparison with a different algorithm such as UCB. \n- Another point of improvement concerns the figures in the paper. First, the font size in all figures in the paper is too small to read on a printed version of the paper. Second, some figures lack explanations such as Figure 3 that seems to show confidence interval for the regret of Greedy algorithm and LinTS algorithm without any explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u5RLhnNNbf", "reviewer": "Reviewer_NV26", "summary": "This paper addresses a significant challenge in stochastic linear bandits, where empirically effective algorithms like Thompson Sampling and Greedy algorithms demonstrate unsatisfying theoretical regret bounds. The author closes this gap by proposing a data-driven approach where problematic instances of LinTS and Greedy are identified, and \"course-correction\" is applied to those instances. The regret incurred by the new algorithm matches the minimax optimal regret of order $O(d\\sqrt{T})$.", "questions": "1. Line 310: \"On the right-hand side of equation 4...one cannot apply Proposition 2...\" Could you explain why? Proposition 2 applies to an \"arbitrary\" sequence, so it seems general enough to be applied here. \n2. Line 266: why $\\tilde{x}_t=x^*_t$ leads to $\\hat{\\alpha}_t$ no less than 1? If $\\hat{\\alpha}_t$ is no less than 1, shouldn't the inequality in line 367 go the other way?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well written. It follows a logical structure, progressing smoothly from one section to another. \n2. Diagrams, such as those illustrating the POFUL algorithm and confidence ellipsoid geometry, help clarify complex ideas, making abstract concepts more tangible. Examples that walk through different algorithms further enhance understanding.\n3. The question considered is important. The proposed framework, POFUL, for linear bandit algorithms is novel, supporting OFUL, LinTS, TS-Freq, and Greedy as special cases.\n4. The proposed course-correction idea is novel. It adapts LinTS and Greedy algorithms, making them maintain the desirable empirical performance while achieving minimax-optimal frequentist regret.", "weaknesses": "1. The method involves setting hyper-parameter $\\mu$ (also inflation and optimism parameters) for the course-corrected algorithm. How it is chosen in the experiments is not discussed. More insights into how these parameters influence the outcome or suggestions for selecting optimal values would strengthen the practical utility of the method.\n2. Empirically, TS-MR appears to perform similar to the better one of LinTS and OFUL in most cases when the balancing parameter is carefully chosen. While this result aligns with intuition, the paper lacks a discussion of the specific situations in which TS-MR could significantly outperform both LinTS and OFUL.\n3. The proposed method involves calculating $\\hat{\\mu}_t$ each round, which can be can be computationally demanding. This could limit the scalability of the proposed method, especially in applications where the dimension $d$ or the number of actions $T$ is large. It may benefit from a discussion of strategies to mitigate computational costs in such scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lTFPrkRyOE", "reviewer": "Reviewer_fHh6", "summary": "This paper considers the classic stochastic linear bandit problem. Motivated by that the LinTS-freq and Greedy algorithm show great empirical performances but does have minimax optimal regret guarantee, this paper wants to bridge the gap between theoretical guarantees and empirical performance. The paper first proposes a general POFUL algorithm framework which can include LinTS-freq, OFUL, Greedy as special cases and provide a regret bound. Inspired by the analysis, the paper then proposes a Course-Correction version for LinTS-freq and Greedy (TS-MR and Greedy-MR). By adaptively balance the action selection of the original algorithm and OFUL, the paper shows that the proposed algorithm achieves the minimax optimal regret while preserving the original empirical advantage. The better performances of the proposed algorithms are verified through both synthetic and real-world data sets.", "questions": "Please see the last part.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper proposes a general algorithmic framework POFUL that includes classic OFUL, TS, and Greedy as special cases, and provides frequentist regret analysis for this general framework.\n2.\tThe paper introduces the concept of regret proxy, which connects the variance of the optimal arm/selected arms with the regret. Inspired by this, the paper proposes Course-Correction for standard LinTS and Greedy algorithm. The variants combine the empirical advantage of the original algorithms and the theoretical advantage of achieving minimax optimality of OFUL algorithm.  \n3.\tExtensive experiments on both synthetic and real-world datasets are conducted to compare the empirical performances of the classic OFUL/TS/Greedy and the proposed TS-MS and Greedy-MS, which demonstrates consistent advantage over baselines.", "weaknesses": "1.\tIn Line 102, the paper says that “derive a general, instance-dependent frequentist regret bound”. Usually ‘instance-dependent’ in bandit literature means that the regret depends on the sub-optimality gap. Here there may be some confusions. \n2.\tGenerally speaking, the proposed TS-MR and Greedy-MR can be regarded as a combination of traditional TS/Greedy with OFUL. The algorithm adaptively determines which action to follow based on the value of $\\hat{\\mu}$. Such combination preserves the minimax optimality. However, since the algorithm still needs to compute the OFUL solution, the computational advantage may be limited. Can authors discuss in the experiments what percentage of rounds need to be replaced with OFUL?\n3.\tSome writing suggestions:\na)\tIn Section 4.1, the definition of $\\tilde{x}_t$ and $x_t^*$ should be moved before the Proposition 4. \nb)\tIn Appendix C, the $\\leq$ in Line 872 should be $\\geq$, the $\\in$ in Line 882 should be $\\notin$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7F5xwr5SHO", "reviewer": "Reviewer_HMrA", "summary": "The paper studies algorithms for stochastic linear bandits. Specifically, it has been established that frequentist algorithms may not match the optimal minimax rate in O(d\\sqrt{T}) but in practice, “hard” problems are rare and algorithms behave better than what theory predicts. This paper proposes a data-dependent switching strategy that adaptively switches between different “types” of linear bandit algorithms depending on the problem at stake. The switch is made thanks to a threshold that must be tuned. \n\nBeyond this concrete algorithmic contribution, the paper revisit the analysis of linear bandit algorithms and sheds a new light on the problem with a very clear discussion that would be highly valuable to this literature. I recommend accepting this submission to ICLR.\n\nUPDATE: I have changed my score to 8 to also take into account the few remarks raised by the other reviewers and a couple of minor second thoughts I had. However, I still believe this is a clear paper with an original proposal, which I recommend to accept.", "questions": "I don't have specific questions that would be useful for me to assess this work further.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* Many significant contributions. Concretely, the paper 1/proposes a new way to analyse bandit algorithms that admits all SOTA methods as special cases, 2/ proposes a novel algorithm with an “oracle” regret bound (Th 2) that depends on a problem-dependent quantity, and 3/ shows how to estimate and exploit this quantity for a fully adaptive algorithm, 4/ tests this algorithm on simulated but important examples and on real datasets. \n* Well written. The paper is very clear and I only have minor comment further below. \n* Impactful. I believe such analysis may have an impact on RL algorithms in Linear MDPs.", "weaknesses": "I am honestly not sure what to point out. I was a bit confused by the discussion of \\cX \\equiv \\cS^{d-1} because the notation of the sphere is not defined and I had missed the discussion  on considering only algorithms for which \\tau_t=0. But I am not sure what to recommend to make it clearer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)