Infrequent Exploration in Linear Bandits
Authors: Harin Lee
Min-hwan Oh
Venue: NeurIPS 2025 poster ()
Keywords: linear bandits
greedy selection
Primary area: theory

Abstract: We study the problem of infrequent exploration in linear bandits, addressing a significant yet overlooked gap between fully adaptive exploratory methods (e.g., UCB and Thompson Sampling), which explore potentially at every time step, and purely greedy approaches, which require stringent diversity assumptions to succeed. Continuous exploration can be impractical or unethical in safety-critical or costly domains, while purely greedy strategies typically fail without adequate contextual diversity. To bridge these extremes, we introduce a simple and practical framework, INFEX, explicitly designed for infrequent exploration. INFEX executes a base exploratory policy according to a given schedule while predominantly choosing greedy actions in between. Despite its simplicity, our theoretical analysis demonstrates that INFEX achieves instance-dependent regret matching standard provably efficient algorithms, provided the exploration frequency exceeds a logarithmic threshold. Additionally, INFEX is a general, modular framework that allows seamless integration of any fully adaptive exploration method, enabling wide applicability and ease of adoption. By restricting intensive exploratory computations to infrequent intervals, our approach can also enhance computational efficiency. Empirical evaluations confirm our theoretical findings, showing state-of-the-art regret performance and runtime improvements over existing methods.

Infrequent Exploration in Linear Bandits
Harin Lee
Min-hwan Oh Scoul National University Seoul, South Korea minoh@snu. ac
University of Washington Seattle, WA, USA leeharin@cs washington. edu
Abstract
We study the problem of infrequent exploration in linear bandits, addressing significant yet overlooked gap between fully adaptive exploratory methods (e.g.. UCB and Thompson Sampling), which explore potentially every time step, and purely greedy approaches, which require stringent diversity assumptions to succeed. Continuous exploration or costly domains, while purely greedy strategies typically fail without adequate contextual diversity. To bridge these extremes, we introduce simple and practical framework, INFEX, explicitly designed for infrequent exploration. INFEX exe- cutes a base exploratory policy according given schedule while predominantly choosing greedy actions in between. Despite its simplicity, our theoretical analysis demonstrates that INFEX achieves instance-depender regret matching standard provably efficient algorithms, provided the exploration frequency exceeds a loga- rithmic threshold. Additionally, INFEX is general, modular framework that allows seamless integration of any fully adaptive exploration method, enabling wide appli- cability and ease of adoption. By restricting intensive exploratory computations to infrequent intervals, our approach can also enhance computational efficiency. Empirical evaluations confirm our theoretical findings, showing state-of-the-an regret performance and runtime improvements over existing methods.
be impractical or unethical in safety-critical
Introduction
The multi-armed bandit (MAB) problem [Lattimore and Szepesvárj 2020 dilemma sequential decision- making under uncertainty: at each time step, an agent must select an action (or arm) and receives feedback only from the chosen action, without observing the outcomes of alternative choices. Linear bandits generalize this problem by assuming that rewards follow linear structure with respect to known arm features [Abe and Long 1999 Auer 2002 Dani et al.
captures fundamental
2008). modeling diverse real-world scenarios such as clinical trials, recommendation systems, and adaptive pricing, where simultaneous learning and optimization are critical.
central challenge in bandit settings is balancing exploration-aaqqiiingg new information about existing knowledge to maximize immediate rewards.
uncertain arms-with
Classical algorithms, including Upper Confidence Bound (UCB) [Auer al., 2002 Abbasi- Yadkori
et al. 2011] and Thompson Sampling (TS) [Thompson] 1933 Agrawal and Goyal (2012), resolve
this tension by exploring systematically at every time step. These methods provide robust theoretical guarantees and strong empirical performance, forming the backbone of the MAB literature.
However, persistent exploration
be costly, risky, ethically problematic in certain domains. For example, in healthcare or safety-critical settings, consistently experimenting with potentially suboptimal actions might lead to adverse or unacceptable outcomes. Consequently, is often desirable to minimize exploration, performing it only when absolutely necessary. A straightforward alternative the purely greedy policy, which consistently selects the currently estimated optimal arm, offering simplicity and reduced risk by avoiding unnecessary experimentation.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Recent literature has studied conditions under which greedy algorithms achieve near- near-optimal per- formance in linear contextual bandits (Kannan et al. 2018 Sivakumar al. 2020 Bastani et al.) 2021 Raghavan et al. 2023 Kim and Ohl 2024). Crucially, these favorable theoretical guarantees of the greedy policy rely on strong distributional assumptions, such as sufficient diversity observed contexts, which naturally facilitates exploration. However, these guarantees fail to hold even in the standard linear bandit settings with fixed arm features, where the greedy approach typically incurs linear regret due insufficient exploration and inadequate information acquisition (e.g., Example 1 in Jedor et al. (02TT).
Thus, we are left with two extremes: at one extreme, greedy policies can succeed under strong diversity conditions (and may otherwise fail); at the other extreme, exploratory methods such as UCB or TS explicitly balance exploration and exploitation at every time step. Surprisingly, there is a substantial gap between these extremes. Specifically, the literature lacks rigorous studies on the impact of infrequent exploration regret in linear bandit problems
This raises fundamental open questions:
1. In order to achieve netr-optimal performance (c.g., logarithmic regret), are we forced to explore at every time step, or infrequent exploration suffice?
2. Can we devise an analytical framework to rigorously analyze methods with infrequent exploration, given that existing techniques may not directly apply?
3. How does the frequency of exploration affect regret performance?
4. Can infrequent exploration methods also demonstrate practical advantages beyond theoreti- cal considerations?
Answering these questions not only provides fundamental theoretical insights but also has significant practical implications, particularly in domains where frequent exploration carries substantial cost or risk. Moreover, even when exploration risks are low, thoroughly investigating these questions may still yield meaningful practical benefits, as exploration typically entails additional computational cost.
In this work, we rigorously address this critical gap by introducing novel and practical framework. INFEX (Infrequent Exploration), designed explicitly for infrequent exploration in linear bandits. Given base exploratory policy Alg, our algorithm executes Alg according a given schedule while predominantly making greedy action selections between these scheduled explorations. This hybrid approach naturally interpolates between fully exploratory and purely greedy strategies, offering fine- grained control over the exploration-exploittiio trade-off. Notably, our approach is computationally efficient, which is particularly valuable large-scale or real-time applications.
Our main contributions are summarized as follows:
Our proposed framework INFEX is general and easily adoptable. It can seamlessly in- corporate any (fully adaptive) linear bandit algorithm as the base policy, enabling broad applicability and straightforward integration into existing bandit implementations.
We analyze the regret of INFEX within the linear bandit framework. We show that de- spite interleaving greedy actions-ve which individually could incur linear regret in naive analysis-on our algorithm achieves
mustance--dpendern regret matching that of LinUCB (or OFUL) [Abbasi- Yadkori et al. 201T]. provided the total number of exploratory time steps exceeds the order of log T. This result demonstrates that the asymptotic regret behavior remains unaffected by the infrequency of exploration. Furthermore, we complement the result by showing that the log T threshold is necessary (see Theorem
We construct new analytical framework for infrequent exploration that establishes regret bounds for INFEX with arbitrary exploration schedules. Using this framework, we propose multiple exemplary exploration schedules and their resulting regret bounds. The main distinction of our analysis comes from the observation that the estimation error of the optimal arm directly affects the regret, and we show that this error decreases as the number of optimal selections increases.
'hiiee approaches such as the classic e-greedy method which introduces occasional stochastic explo- ration and Explore-Thae Chen-Commit (ETC) algorithms which perform an initial exploration phase followed by pure exploitation are known to achieve suboptimal regret rates, in this work, we study whether infrequent exploration be near-optimal.

---

Furthermore, we derive new instance-dependent regret bound for LinTS [Agrawal and Goyal 2013 Abeille and Lazaric 2017]. This new theoretical insight may independently interest the broader bandit research community.
By limiting computationally intensive exploratory updates (e.g., posterior sampling or confidence set computations) to infrequent intervals, our algorithm significantly reduces runtime complexity compared to traditional approaches.
Empirical results, provided in Section 5 substantiate our theoretical findings by demonstrat- ing that, for suitable exploration schedules, INFEX outperforms both purely greedy and fully exploratory baselines in cumulative regret and computational efficiency.
1.1 Related Work
Full adaptive exploratory policies. Classical bandit algorithms, such as Upper Confidence Bound (UCB) et al., 2002 /Abbasi- Yadkori et al.] 2011] and Thompson Sampling (Thompsnn
1933
systematically balance exploration and exploitation at every time step. These approaches provide robust theoretical guarantees, including optimal logarithmic or sublinear regret bounds, and have been widely studied due to their effectiveness and simplicity. However, it remains an open question whether continuous exploration at every step is necessary or if infrequent exploration could suffice without compromising performance.
Agrawal and Goyal 2012]. 2012)]
Greedy policies. Recently, significant research has investigated conditions under which purely greedy algorithms achieve near-optimal performance, particularly within contextual bandit frame- works. Studies by Basttni et al. [2021), Kannan et al. [2018), Sivakumar et al. [2020], Oh et al. [2021],
Raghavan al. 22023]. Kim and Oh 2024 have shown that greedy policies can implicitly benefit from exploration when strong distributional assumptions, such as sufficient contextual diversity, are satisfied. For instance, Kannan al. [018], [Sivakumar al.) [2000, Raghavan et al. 2023) assume that the context vectors are perturbed by multivariate Gaussian distribution at each time step, forcing the context distribution to be diverse. Kim and Oh (2024) study more general class of distributions under which greedy policies achieve polylogarithmic regret. While these findings identify specific scenarios favoring greedy methods, they leave unresolved how one should approach less ideal settings-such as linear bandit problems with fixed arm features lacking contextual diver- sity or stochastic variation, precisely the scenario addressed our paper. In such standard lincar bandit settings, purely greedy policies typically incur linear regret due to insufficient information gathering [Jedor et al. 2021], highlighting the necessity of explicit exploration.
Randdomizedlscheedueee forced exploration. To incorporate explicit exploration in simple man- ner, e-greedy algorithms randomly explore arms with a small probability at each step [Lattimore and Szepesvári 2020 Tirinzoni et al. 2022]. While intuitive and computationally efficient, e-greedy policies are theoretically known to incur suboptimal regret. Another approach, forced-sampling [Gold]
enshluger and Zeevi, 2013 Bastani and Bayati] 2020 Lee et al., 2023], involves exploration at predetermined intervals. For instance, Goldenshluger and Zeevi [2013] demonstrate that scheduled forced-sampling combined with greedy exploitation can achieve polylogarithmic regret under fa- vorable context distributions.
Cegiorre-Ten-Conne
(ETC) methods represent another scheduled
exploration approach [aagffrr and Zhang 2007| Abbasi-Yadkori et al. 2009 Garivier et al. 2016
Perchet et al. 2016 Hao et al. (020). separating exploration and exploitation into distinct phases. ETC algorithms initially perform extensive exploration to identify promising actions, after which they commit exclusively to exploiting the best-identified arm. Despite their simplicity and intuitive appeal, ETC methods typically result in suboptimal regret compared fully adaptive exploration strategies such as UCB and TS.
Infrequent exploration. To the best of our knowledge, approaches combining greedy exploitation with infrequent exploration have received limited attention, particularly in linear bandit contexts. One related work by Jin et al. (2023) studies multi-arma bandits without features and proposes hybrid method that randomly chooses between Thompson Sampling and greedy selections. Their results highlight the potential theoretical benefits of strategically interleaving exploration and exploitation. Nevertheless, extending this hybridization concept rigorously to linear bandits and establishing near-optimal regret guarantees remains an important open question.
3

---

Despite extensive research on adaptive exploration methods, greedy algorithms, and scheduled exploration, significant gaps remain in understanding how exploration frequency affects regret linear bandits. Key questions include: Is continuous exploration necessary for near-optimal performance, and can infrequent exploration achieve similar guarantees? Current analytical frameworks primarily address frequent exploration, highlighting the need for rigorous approaches tailored specifically to infrequent exploration scenarios.
2 Problem Setting
We consider the stochastic linear bandit problem. The agent is presented with finite arm set X' Bd with X = K, where I the d-dimensional unit ball. At each time step t 1, 2..... the agent selects an arm X; E X' and receives real-valued reward Y, X; l + ?, where 0* Rd is an unknown parameter vector and nh is zero-mean o-subGaussian noise We assume that |0 S S, and that this bound is known to the agent, where || ||2 denotes the & norm. The optimal arm the arm with the highest expected reward and is denoted by == argmax, x 8*, We assume that is unique for simplicity.
2
A linear bandit algorithm Alg is that (possibly randomly) selects X, based the history X1, Y1, Yi...., X, X,, Y-11- The cumulative regret RAig (7) of an algorithm Alg over T time steps is defined as follows:
RAig (T)
The goal of the agent is to minimize the cumulative regret. We primarily focus on instance-dependent regret, meaning that we study the growth of (T')(T) for fixed problem instance (X, O*)
3 Algorithmic Framework: INFEX
INFEX is versatile and broadly applicable algorithmic framework designed for linear bandits and explicitly controls the frequency of exploration. The framework takes as input a base exploratory algorithm Alg and predetermined exploration schedule Te (i.e., set of time-step indices). At each time step in Te, INFEX executes the exploratory algorithm Alg, while at all other steps it acts greedily based on the ridge estimator. We denote the resulting hybrid algorithm INFEX Alg, T.).
One notable advantage of INFEX is its generic design, enabling seamless integration of virtually any linear bandit algorithm as the exploratory component. This flexibility facilitates straightforward adaptation to various application domains and existing algorithmic frameworks. Furthermore, by clearly separating exploration and exploitation phases, INFEX achieves computational efficiency by limiting the frequency of computationally intensive exploratory procedures.
The pseudocode describing the procedure is provided in Algorithm [
Remark (Substituting the ridge estimator.). The only properties of the ridge estimator used in analysis the boundedness of the online squared-loss regret, Σt= (x, 0. X, 07)² (dd log" T), and the fact that the estimation error |x: Ó, - x T decreases proportionally to v/ when there are samples of in the data. Therefore, any estimator that satisfies similar properties may be used place of the ridge estimator.
Theoretical Analysis
4.1 Notations and Definitions
Define reg, := T X,T 8" to the instantaneous regret time step t. The main quantity that measures instance's difficulty is the minimum gap, defined as xx O* maxxex') x. 0*. It represents the smallest possible non-zero instantaneous regret.
21p satisfies Bsexp(sn:) X1, Yi, X.] S exp(s20² o2262222)))))0 /2) for all R.

---

Algorithm INFEX Alg, Te): INFrequent EXploration
1: Input: Base algorithm Alg, exploration schedule Te N
2: Initialize 1/6-+ = la
3: for t = 1, 2, .... do
4: i Te then
5: Choose X, according Alg and observe Y;
6: else
7:
Compute ridge estimator Ū:-1 Choose X, = argmax 0, and observe Y
8:
9:
end if
10: Update V = 1/-1 + X.X,
end for
For two positive functions (xx and g(z),, write f(x) (g(x)) if there exists constant C
such that f()) & Cg(x) + C' for all z. When is a positive real number and lim f(z) 0, we write f(x (()x)). In our analysis, we treat d, T, K, and A as variables, and regard all other quantities such as a and as constants.
g(x)
We say an algorithm Alg attains (high-probabilig instance-dependent polylogarithmic regret if (T) = O d" n To) for some constants a, b, 2 0 with probability at least 1 1 Note that our analysis holds for an arbitrary failure probability å E (0, 1]. For simplicity, we will mainly focus the common choice 8 1/". Such high-probability bounds that hold with probability at least 1 - 1/T immediately imply comparable expected-regret bounds.
Let f(t) = TTe n (1,2, . | be the number of time steps at which Alg is executed by INFEX( Alg, Ta) up to time step f. Hence, f(t) is the frequency of exploratory steps up to time Let f (n) == ming! N: f(t) 2 n be the time step which Alg is executed for the rethh time. One particular exploration schedule of interest is the periodic schedule that executes Alg at a fixed interval. For positive integer m, let mN == {m, 2m, 3m, . denote the set of positive multiples of m. Then, the exploration schedule that executes Alg every m time steps corresponds to Te = mN, and the resulting algorithm is denoted INFEX(AL mN).
Let Nop (T) == E'n 1xx" X2) denote the number of times the optimal arm is selected up to time step T. We define a; == log det Vg the analysis of many linear bandit algorithms [Abbasi- Yadkori al. 2011]. []. For simplicity, we let
Vi and (5( == a va, + 2 log(1/)) S, which are key quantities
3 = (1/TT) for all
4.2
Main Results
In this section, we analyze the regret bound INFEX(AAE Te).
Theorem (Regret of INFEX). Let Alg be a linear bandit algorithm that attains polylogarithmic regret, specifically RAg = O ( da a, c 2 0. Let Te C be the set of exploratory time steps and f(t) == TTe n 21,2.... ... tt} be the number of exploratory time steps up time step t. Assume that f(t) w(log t) as
Ao log T) with probability at least 1 1/T for some constants
Then,
with probability at least 2/T, the regret of INFEX(Alg, Te) is bounded as
(INEEX(AA.TT.(T)) S RAlE (J(T)) Geome f) G(T),
where Geonsl (TAlg: f) is independent of T, TAIg N is constant determined by Alg satisfying d
TAlg 0 J log 4), and
T (
d [log loglollogT
log d
G(T) -
A
Bounds on Geons (TAlg. f) for some functions are provided Table 7
5

---

Table 1: Example bounds on (To f) for various functions f. Epoch length refers to the length between two consecutive executions of the base algorithm.
Example of f())
Description
Goonst (TAle: 5)
t/m
Epoch length is constant m
O (miTAIs + mnd log" me)
A)
t/(logt))
Epoch length increases by (logt)*
O (TAIR log" TAIK + 3 log
log2tr d)
t" (r 1))
Epoch length increases by fh-r
O
TAls "./
log2/r r/rr d 1/r gh/r
3)
(logt" (r b 1)
Epoch length increases exponentially
( (((((A3)))
Discussion of Theorem 1 In the regret bound of Theorem 1 only the terms Raig (J()) and O (1 (log T + dl log log 7 7) depend on T. The first term corresponds to the regret of the base algorithm Alg. The second term bounds the additional regret incurred by the interleaved greedy selections, and it matches the instance-dependent bound of LinUCB [Abbasi- [Abbasi-Yadkorr We emphasize that these terms do not increase as the number of explorations decreases; in fact, the first term decreases. Therefore, choosing sparse exploration schedule does not worsen the asymptotic regret of INFEX(Alg, Te). as long as satisfies the condition f(t) = w(log t). The trade-off from reduced exploration only appears in the constant term. Geons (TAlg( f) is the cumulative regret incurred by the greedy selections for some initial time steps, where greedy selections do not have strong guarantees. As shown in Table [] an excessively small number of explorations may result in exponential growth of the constant term with respect to d/ A, which may significantly degrade the algorithm's 's finite-time performance. Meanwhile, exploration with constant periods logarithmically growing epochs increases Geona (Tolg f) only by constant or a logarithmic factor. For finite T, the least amount of exploration required to ensure that Goonst (TAlg: f) does not exceed the order of G(T) is determined by the relative magnitudes of d, T, and A. While it may be possible to allocate a minimal amount of exploration if all of these quantities are known, A is typically unknown to the agent, making it challenging to determine the optimal schedule. In practice, we suggest that periodic or logarithmically growing epochs would be efficient. However, is very important to note that, even without knowing these quantities, INFEX achieves the same order of the regret compared to the vanilla fully adaptive exploration methods. In Section 5 we demonstrate through numerical simulations that exploration with fixed period of 5 to 100, so that 80% to 99% of the actions are greedy, yields favorable performance in terms of both regret and computational efficiency.
al. 1011]
Obtaining minimax bound. We mainly focus on the instance-dependen bounds in this paper to show how the exploration schedule affects the regret for a fixed instance. Meanwhile, providing the worst-case minimax regret bounds for infrequent exploration would also be an interesting problem. While the asymptotic behavior of the instance-dependent bounds achieves the same order of polylogarithmic regret as long as the exploration number satisfies w w(og t), we conjecture that this threshold would be too small to achieve the optimal O(VT) minimax guarantees. Finding the optimal infrequent exploration strategy and trade-offs for the minimax regret bound would be an interesting open problem.
As an instantiation of INFEX, we can choose Alg LinUCB Abbasi- Yadkori et al. 2011 or Alg LinTS (Abeille and Lazaric 2017), which are representative linear bandit algorithms. To show that Theorem I applics to both algorithms, we present their instance-dependent polylogarithmic regret bounds. To the best of our knowledge, the instance-dependent bound for LinTS is explicitly shown for the first time. The proof of Theorem [
is deferred to Appendix B
Theorem 2. LinTS (Abeille and Lazaric 2017 achieves the following instance-dependen bound with probability at least 1 d:
mminfdog log dT 8 A
log KT) (ar log 1)²²
RTints(T)= 0
where at = 0 min dlog log T d log T + d log 1)

---

Furthermore, Theorem 5 in Abbasi- Yadkori et al. [2011] states that the regret of LinUCB is ReinUce (T)) a / with the same bound on or as Theorem 2 Then, combined with the result of Theorem 1 we obtain the regret bounds for specific base algorithms. We show some example regret bounds for INFEX when Alg is LinUCB or LinTS with varying exploration schedule in Table 2 It demonstrates that the regret of INFEX, instantiated with LinUCB or LinTS, matches the regret bounds of the corresponding algorithms without infrequent exploration, up to factors independent of T'
Table 2:
Example regret bounds of INFEX(Alg, Te) with specific instantiations of Alg and S().. Each column shows the regret corresponding to each base algorithm. The final regret bound the sum of the regret shown in the base regret row and the constant regret shown in the row with the corresponding exploration schedule.
Regret bound of INFEX(Alg, Te))
Frequency of exploration
Alg LinUCB
Alg LinTS
[(1) = L (base)
o x (log doo log T)²)
(dlog T) (log T + d log log T)
f(t) t/m
0
((m
d +
I
I
d
log?
o
Az
d log²
d I
+
md
log d
I
[(1) 1/(lo())
o
d²
log
2+r
2)
o
d
log
3+r
27
[(1) 1
o
d
dl log
2
o
d 3 d
log
]
log
7 (+++)
lox $) +
f(t) = (log t)r
Computational complexity. The computational time complexity of a single greedy selection is Old + dK): using the Therman-Morrison formula [Sherman and Morrison 1950], one maintain Vi in Odd)) time per step, so updating 0, also takes (dd) time, and the remaining (dd) is required to find the arm with the highest estimated reward. The computational complexity of LinUCB (dd d2 K") per time step, where the additional (d K) term required to compute the upper confidence bound of rewards x 0 + -el|==ly,-> for all x E X. The computational complexity of
LinTS is (d + dK), where the additional Old)) term corresponds to sampling parameter 0r from multivariate Gaussian distribution. Both algorithms have strictly greater computational complexity than performing a greedy selection, meaning that replacing them with greedy selections reduces the total computational cost.
4.3 Necessity of t(ogtt Exploration.
We provide a lower-bound result that implies the condition f(t) = (logt) is necessary to obtain polylogarithmie regret bound that holds for any T. Specifically, we show that if f(t = w(oog t)
log does not exist is above zero, then there exists does not hold, that is, either the limit lim, J(T) a problem instance such that the regret of INFEX scales almost linearly in T using the standard information-theoretie
method.
Theorem 3. Let Alg be an arbitrary policy and Te C be a set of natural numbers. If [(1) + w(og l), then for urbitrary constant e E (0, 1), there exists problem instance (X, 0²) and constant ef >> 0 that depends on and e such that
E (RIFEE(AAA T.) (T)] 2 e(J.E)rZ=
for infinitely many T E.
We note that this result applies predetermined exploration schedules, and the w(og () threshold might not be necessary when the exploration schedule is adaptive to the observations.
The proof of Theorem 3 is presented in Appendix A.4
7

---

4.4 Sketch of Proof
In this subsection, we provide a sketch of the proof of Theorem Throughout this subsection, we work under the high-probability event that RAi (T) is polylogarithmic in T and the event of Lemma that ensures the concentration of 8g toward 6".
We first explain how TAlg is chosen. Assuming that Alg is independently run, TAlg defined as the time step such that for all T 2 TAlg- at least quarter of the selections made by Alg are optimal, that is, the optimal arm chosen in at least //4 / of the T time steps. The existence and order of TAlg are guaranteed by the following lemma:
Lemma 1. Suppose a linear bandit algorithm Alg' attains a polylogarithmic regret bound of RAig' (T) O ( T) for some constants a, a,b,e e 2 O. Then, there exists TAig' E N such that for all T 2 T at least a quarter of the selections made by Alg are optimal. Furthermore, TAlg" O AT log". 2)
We mainly focus on the sum of regret incurred after the time step (TAgg. that is, after Alg executed for TAlg times. For t, T E N. let ((T, == {t N 7 + < T. Teh. which denotes the set of time steps with greedy selections between + and T, inclusively. Let LIEG(T.T) reg, be the cumulative regret incurred at the time steps in I(,, In the remainder of this section, we show that R RIFEEx(Ale.T. (f-1) + 71, T') has the polylogarith- mic bound stated in Theorem for some constant TI.
RC INIEIIAA (T,
The following lemma shows that the regret of greedy selections related the number of optimal selections.
Lemma 2. For any T, T.Te E N with T T. holds that
40- 3
BL 1 N Nop (t 1)
RC R. (T,
Σ
A
(EG(r,T)
The intuition behind this lemma that the estimator 0, becomes more accurate in estimating x² 8 as the optimal arm x" is selected more often. The conclusion of the lemma implies that if (t)(()) increases linearly in f, then the additional regret caused by the greedy selections remains polylogarithiic in T. By the choice of TAlg at least quarter of the selections made by Alg are optimal for all t 2 frrffl(rn (FAIg), implying that Nop (t) 2 ft). This fact leads to the following regret bound:
Lemma 3. Let TAlg be defined as in Theorem
Then, for any T > f (TAIg) it holds that
4aT 8
8
B
R RiIEENNN T-)
(T (TN)), T) s
Σ
A
A
f(t)
LEG(S ( (T)
Furthermore, this bound is sublinear in T when f(t = wlog
We further improve this bound by observing that the quantity Nop (t) must grow linearly with i for sufficiently large f as we now have a sublinear bound on RISFEX(Ale,T T.). Using this fact, we obtain the following stronger regret bound.
Proposition 1. There exists a constant T1 E that depends on A, TAlg. and the function f. is independent T,, and satisfies
7
RG RINFEX(ALE (TAIK), (TAIK) +T1) <
ATI
16
and
Alg, (I TT, 5 4uT 32
16,3% log
RG
A
for all T> f T1.
Note that 88 ((Tr)) so we have derived a bound of Oar +lo T) with some additional constant amount. The proof is completed by providing an appropriate bound on or. We apply the
following lemma, which is derived from the proof of Theorem 5 in Abbasi- Yadkori al. [011]
8

---

Lemma 4. the data X1. X2... Xx is collected through a linear bandit algorithm Alg', then
RAgg 1+ (d - 1)
or S log (1 7) + (d- (03-1)11. lo
Consequently, if Alg' attains potylogarithmic regret, then
d
aT = O log T + log log T + log
A
The detailed proof of Theorem is presented in Appendix A
Remark 2. The analysis of Theorem requires positivity of the minimum gap A and a fixed optimal arm. Therefore, the analysis holds long the two conditions satisfied, even for infinite and time-varying arm sets, although it does not fully generalize to the linear contextual bandit setting with arbitrary arm sets. For detailed discussion on the possibility of extending the analysis to time-narying arm sets, refer to Appendix E
Numerical Experiments
To complement our theoretical analysis, we conduct numerical simulations empirically investigate the behavior and practical benefits of INFEX. Our main objectives are to (i) assess whether infrequent exploration strategies maintain strong regret performance compared to fully adaptive methods, (ii) evaluate computational efficiency improvements due to reduced exploration frequency, and (iii) demonstrate the general applicability and robustness of our proposed framework across different base exploratory algorithms and exploration schedules.
We select Alg LinUCB and Alg LinTS as the base algorithms for exploration and use exploration schedule Te = mN := {mn n E N}. meaning Alg executes every m steps. Specifically, examine three choices of 99% greedy selections, respectively. For benchmarking, we also compare our framework against other policies: the purely greedy policy, single-parameter version of OLSBandit (Goldenshluger and Zeevi 2013), and an e-greedy approach with s =t 1/33
5, 20, and
100, corresponding
80%, 95%. and
We randomly generate problem instances for given and K follows. We construct the arm set A' by sampling K arms i.i.d. from a multivariate Gaussian distribution AoO,, 2d Ia) and rescaling each vector have a norm at most when exceeds We sample 0* uniformly from the unit sphere in Rd. The random reward is given either +1 or - 1, with its expectation being X, 0". We repeat the process for 20 randomly generated instances and report the mean and standard deviation of the cumulative regret over T = 10000 time steps for each algorithm.
Figure shows the total regret and computation time of each algorithm. Interestingly, we observe that certain exploration schedules improve the total regret. Especially for Alg LinTS, all values of m 5, 20, 100 reduce the regret significantly. The performance of Alg = LinUCB is also improved when m = J. These configurations outperform both the base algorithm and the purely greedy policy, exhibiting strong practicality. We also observe a reduction of computational time for any value of m.
OLSBandit inefficient because it spends most of the time steps, specifically at least (2d log T) steps, forced sampling. While e-greedy appears to show decent performance, note that the choice E 1/3 implies a regret lower bound of (2(32/3) and it is its best bound, precluding the possibility of achieving polylogarithmic regret.
Refer to Appendix for additional experiments with different dimensions d and experiment details.
6 Conclusion
We propose INFEX, a simple yet practical framework that mainly performs greedy selections while exploring according to a given schedule. Our theoretical analysis reveals that INFEX attains polylogarithmic regret bound, whose growth rate with respect to remains independent of the exploration schedule, provided that the exploration frequency exceeds the order of log T. Empirical results further illustrate the strengths of INFEX, showing that judiciously timed exploration not only maintains robust theoretical performance guarantees but also delivers practical improvements in

---

Experiment 10, 10000
LinUCB
LinTS
Greedy
INFEXILinUCB, 5N)
INFEX(LinTS, SNI
OLSBandit
INFEXILİnUCB, 20N)
INFEX(LinTS, 20N)
r-Greedy
INFEXILinUCB, 100N)
INFEX(LinTS, 100N)
Total Regret (K 10)
Computation Time (K 10)
Computation Timels)
2500
1.5
Total Regret
2000
1500
500
Total Regret (K 100)
Computation Time (K 100)
3500
Computation Timels)
3000
Total Regret
2500
2000
1.0
1500
1000
0.5
Total Regret (K 1000)
Computation Time (K 1000)
Computation Time(s)
Tocal Regret
3000
2000
2-
1000
Figure 1: Comparison total regret (left) and computation time (right) when 10, 10000, and K 10 (top), K 100 (middle), and K 1000 (bottom).
terms of both regret and computational efficiency. While this work focuses specifically on linear bandit settings, we believe the framework and results serve as foundation for broader exploration strategies, potentially enabling similar performance benefits in more complex and general function approximation scenarios. An exciting avenue for future research lies extending our framework to accommodate these generalizations, further enhancing its applicability and impact.
10

---

Acknowledgements
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR071883 and RS-2023-002226633 by Institute of Information & communications Technology Planning Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS- RS-2025-022633544) and by AI-Bio Research Grant through Seoul National University.
References
Yasin Abbasi- Yadkori, András Antos, and Csaba Szepesvári. Forced-exploration based algorithms for playing in stochastic linear bandits. In COLT Workshop on On-line Learning with Limited Feedback, volume 92, page 236, 2009.
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24:2312-2320, 2011.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In International Conference on Machine Learning, pages 3-11, 1999.
Mare Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Proceedings the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pages 176-184 PMLR, PMLR, 2017.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In International conference on machine learning, pages 127-135. PMLR, 2013.
Peter Auer. Using confidence bounds for exploitationneexlloaaion trade-offs. Journal of Machine Learning Research, (3Nov):397-422. 2002.
Peter Auer, Nicolo Cesa-Biances and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-2555 2002.
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-22) 2944, 2020.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-Fi algorithms for contextual bandits. Management Science, 67(3):132--1349) 2021.
Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wahhschheiniicckettthheeeee und verwandte Gebiete, 47:119-137. 1979.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. In 2 Annual Conference on Learning Theory, number 101, pages 355-366, 2008
Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-commit strategies. Ad- vances Neural Information Processing Systems, 29, 2016
Alexander Goldenshluger and Assaf Zeevi. A linear response bandit problem. Stochastic Systems, (1):230-261, 2013.
Osama A Hanna, Lin Yang, and Christina Fragouli. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. The Thirty Sixth Annual Conference on Learning Theory, pages 1791-1821. PMLR, 2023.
Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 13:15-3110773, 2020.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference learning theory, pages 9-1. JMLR Workshop and Conference Proceedings, 2012.
11

---

Matthieu Jedor, Jonathan Louëdec, and Vianney Perchet. Be greedy in multi- armed bandits. arXiv preprint arXiv:2101.01086, 2021.
Tianyuan Jin, Xianglin Yang, Xiaokui Xiao, and Pan Xu. Thompson sampling with less exploration fast and optimal. In International Conference Machine Learning, pages 15239-15261. PMLR, 2023.
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. Advances in neural information processing systems, 31, 2018.
Scok-Jin Kim and Min-hwan Oh. Local anti-comcentraation class: Logarithmic regret for greedy linear contextual bandit. Advances in Neural Information Processing Systems, 37:77525-77592, 2024.
John Langford and Tong Zhang- The spoch-greeds algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Harin Lee, Tachyun Hwang, and Min hwan Oh. Lasso bandit with compatibiliity condition optimal arm. In The Thirteenth International Conference on Learning Representations, 2025.
Min-hwan Oh, Garud Iyengar, and Assaf Zeevi Sparsity-annostic lasso bandit. In International Conference on Machine Learning, pages 8271-8280. PMLR, 2021.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. 2016.
Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. Greedy algorithm almost dominates smoothed contextual bandits. SIAM Journal on Computing, 52(2): 487-524, 2023.
Jack Sherman and Winifred Morrison. Adjustment of inverse matrix corresponding to change in one element of given matrix. The Annals of Mathematical Statistics, 21(1):124-127, 1950.
Vidyashankar Sivakumar, Steven Wu, and Arindam Banerjee. Structured linear contextual bandits: A sharp and geometric smoothed analysis. In International Conference Machine Learning, pages 9026-9035. PMLR, 2020.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-22) 294, 1933.
Andrea Tirinzoni, Mattco Papini, Ahmed Touati, Alessandro Lazaric, and Matteo Pirotta. Scalable representation learning in linear contextual bandits with constant regret guarantees. Advances in Neural Information Processing Systems, 35:2307-2319, 2022.
Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgle- ichungen (mit einer anwendung auf die theorie der bohlraunstrahlungg. Mathematische Annalen, 71(4):441445 4799, 1912.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification: The abstract and introduction (Section bution and scope.
I
accurately reflect the paper's contri-
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitation of the work is discussed Appendix B
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: The full set of assumptions is presented in Section The complete proofs of the theoretical results is provided the Appendix with sketch the proof provided in Section 4.4
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide code for experiments with random seed that produces the results in the paper.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
14

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We submit experiment code as supplemental material, which reproduces the experiment results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guidees/oodeStmii wtt.eeeuuiiisisooooiooooooo for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https htc//public/guudees/Ccddee
ssi sisionnnicc for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experiment setting and details are accurately and sufficiently described in Section 5 and Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
The experiment results presented with 1-standard deviation error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Information on the computer resources is provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and the research conducted in the paper conform, in every respect, with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datatsss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standare components.
Please refer to our LLM policy lattps://neurip:: /ttp:///scccc.cfeeeeeee///////// for what should or should be described.
19

---

A Proof of Theorem 1
In this section, we provide detailed proof of Theorem [ We supplement the proof by proving Proposition in Appendix A.2 and verifying the bounds of (TAle f) listed in Table in Appendix In Appendix A.4 we prove Theorem 3 Proofs of technical lemmas are provided in Appendix Throughout the proof, denote To := =f''(TAN for simplicity.
A.1 Proof of Theorem 1
Proof of Theorem |
TAlg is the way described Lemma with Alg' Alg, and the lemma
guarantees that TAlg = O log" 2). Tn is the constant defined Proposition
The total regret is decomposed into four parts, described in Eq. (I
(I & Rau((((T) + 28 + R RIFEEX T.) (To TO +T))
R RNFEXX(A (To T).
(I)
The first term is the sum of the regret incurred by Alg. Since Alg is executed (T) times, this regret bounded by (T))) The second part is the sum of the regret incurred by the greedy selections during the first time steps. Since the maximum possible regret per time step is 25, we bound T. Lastly, among the time steps that
the sum by 2S Note that this quantity is independent perform greedy selections, R R (AFEX(A)g.T..) (To, To TI) is the sum of the regret incurred during the time steps between To + and To + 71, inclusively, and RG R SINPEX(Alg,TA. (To + T) is the sum of the regret incurred during the time steps between To + + and T, inclusively. By Proposition
I we have R INFEX (To, To =1)= I 16 ATi and R INFEX T.) (TO + TI,
Olar(ar log T)) Denoting Geonst == 2STo 16
7 ATi, we obtain that
orr arr + log
RAi(([(T)) (T) S
Geonst +
(2)
A = Rf Goust + (d T)2
(
where we use Lemma 10 for the last equality. Eq. (3) shows that INFEX(Alg, T.)) achieves poly- logarithmic regret bound added by T-iidependent constant. We improve the bound on ar using Lemma 4 and the derived regret bound. The growth rate of the logarithm of the cumulative regret log Geons). Applying this fact Lemma 4
log(1 RISFEX(AAg, T.) (T)) Ollog( $ log
obtain that
( [og T+ dlog log + d dlog A
d
oT = o
+ dllog Gooost
Plugging this bound into Eq. (2) we obtain that
RI (T) S (AE(((()) + G.oost
1 A
[logT Io + dog log T + dllog A + d log Goonst )
+ +0
RAlg (F()) + Goonst + + (0( d log Geonse)
+ +
(
L A
log + d log log T dlog
(4)
where the last equality holds since (a + b)22 < 2a² + 212 for all a, b E R. Therefore, there exists a constant Geons f) = Goonst + O (dlog (cons))
and a function G(T) in 2)
20

---

1/4 (log T dllo log T dlog 2) ))² such that
(I RAIg (J()) + Geona (TAlg: f) + G(T).
In Appendix A.3 we summarize how Goonst TAlg f) is determined and provide its example bounds listed in T
A.2 Proof of Proposition
1
Proof of Proposition By the sublinearity stated in Lemma on d, A, Algs and f such that for all 2 T1
there exists constant that depends
4
32
8
Σ TEG(TO.T)
B 7 M(()
S A(T A(T-m) To),
(5)
A
A
16
The first part of the proposition trivial by the choice of Ti. Now, we prove the second part. Fix T > To + TI. While Lemma 3 only considers the optimal selections by Alg, we improve this result by showing that the number of optimal selections grows linearly in and combining it with Lemma 2 Specifically, we show that (T) 2 (T (o)- We consider two cases. First, suppose Alg is executed at more than half the time steps between To + 1 and T, that is, (Te (To + 1. , ,. 2 {(T TO). Then, f(Z) 2 { To). Since at least quarter of the
selections made by Alg are optimal after time step = To. holds that
1
Nope(T) (T) 7 ((T) 8 (T -T-ro) TO).
Now, we suppose the opposite. Consider the case where Alg is executed at fewer than half of the time steps between = To + and T. Then, 1(T - TO) I (G TT). bound the number of suboptimal selections during the time steps in ((To, T) follows:
Σ (ED(T..T)
A1 # x3} < RG
LNEEX (TO.
40 32
8
Σ
+
A
f(l)
(E9(T..T)
7
A(T TO)
16
7
A (((TO,T)))
where the first inequality uses that the non-zero instantaneous regret is at least A, the second inequality applies Lemma 3] the third inequality follows from Eq. (5). and the last inequality uses that -o) < (G T... Therefore, we conclude that the number of suboptimal selections at time steps in ( T) is most (T T)]. It follows that the number of optimal selections among the same of time steps is least $ (T(. T Since at least quarter of the exploratory selections are optimal, we have
Nop (T))
9(To, T) 1 ((T)
8
1( T)l (5(T) -TAle)
8 (T - -T),
where the last equality comes from that [G(To, T) and S(T) TAlg are the numbers of greedy
selections and exploratory selections during time steps = Tn + 1,...,
.....,7 T respectively and hence
their sum is T To. We have proved that NNpx (T) $ (T 7o) for both cases. Plugging this bound
21

---

into Lemma 2 we conclude that
2
Σ
32
2
Σ
S
A
1 Nop1 (t
1)
A
[t To)
TE
1E
16
Σ
A
t - TO
TE ,
16
T
1
dr
to
To
16,3 (log
[T
Tv)
log T1)
A
16,3 log
A
where the first inequality holds since 1 + Nap 1) (t TO) (t (t- To), the second
inequality uses that 9, is increasing, and the third inequality upper bounds the summation by integral since 1 (f(z - To) is decreasing t. The proof is completed by plugging this bound into Lemma
4a 3
RG T. + T) S
Σ
A
Nopi(t 1)
LED T1.7"
4 32
16,34 log
A
A.3 Bounds on Geonst ( (TAlg: f)
In this subsection, provide bounds (coms((Algg, f)- The steps of determining Gevnal (TAlg: in the proofs of Theorem can be summarized as follows. First, take TI such that for all T 2 7i holds that
4
92
8
B
7 A(T To),
<
A
A
f(t)
16
TT)(TO.T)
which exists by Lemma
3 Then, define Geonst = 2STo + 16 AT, Lastly, take Geonsi f)
Goonst + O (d log Geonst P). The value of To f-1 (FAlg) determined once f and TAlg are determined. remains to provide an upper bound for т1. We define additional constants whose bounds are easier to obtain. Let T1.1 E be the least time step such that T1,1 2 To and for all T 2 + T1,1, it holds that
4aT 02
AT.
A
Since ar,, .3 Oo T), infer that 71,1 max To: O(( 5 log 1)3) O(Tu + + log 22)).
Define 7122 E N to be the least time step such that for all T 2 To + T1,, it holds that
8
Σ
BZ
A(T-
1
f(I)
(E
The scale of F1,2 depends on [()). Putting together, we obtain that T 2 to + max(nuam it holds that
4am
32
8
32
<
AT
+
A(T T0)
f(t)
16
4
TT)
3
A(T -T)
7
A(T TO).
16
22

---

where we use T - 2TT for the second inequality, which is implied by T' 2 T0+ 2 2To. Since Ti is the least value that satisfies the property above, we have 7i max T1,1 -1,2)- Then, we obtain
that Goonst ( + ATI, + d² log² A) Additionally, note that for some universal constant C' > 0, A
d² log" x I for all x 2 A (dlog 2)² Therefore, we have & log Olx + log 1)
we have A
implies that
G const + o 0AA (dlog Gemma))) Gouns + +o (
de log²
+
A
A
=0 TO + ATI +
de log²
d A
Combining with Eq. 44) in the proof of Theorem
1 we obtain that
RIMFEX(AAE.TT(T)) (T) I (fag(((()) + +
d? - To Ar22
d A
log²
A
log T + d log T + dlog d A
+
A
RAle (S(T)) O + (A.2)
d A
+o
A log T + log log T + d log
where in the last equality, the O log )) term in the second term is absorbed into the last O(3 (log T + dlooglo log T + dloo 2) term. Therefore, there exists Grons (FAll( f) and GTT) such that Goons ( (TAlg: f) = O (To + 2TI2), G(T) = =0 (log T + d log log T + d log d 2 and RINPEX(AL (T) S RAig(f(T) + Goona (TAlg. f) + G(T).
remains to bound To and 71,2. Let C3 > 0 be a constant independent of d, A, and that satisfies 3 S Cog + T) for all T, which exists by Lemma 10 Let Tí,2 be the least time step such that for all T ,í.2. it holds that
32C log(1 (1 + 27')
max ((), ST.
(6)
A
We show that 7ı2 max T
For all T to max -(,2). it holds that
8
32
8,3
T
A
f(t)
A
f(t)
(E
(=
8 T-
max
8C3d log(1 + T)
T-ro
A
max (S(1).}}
8C 8Codlog(1 + 2(T To))
A
max (S(1), 13
A(T A(T- -0);
4
where the first inequality holds since 3; is increasing, the second inequality uses that f(t) is increasing
and [() 2 for 2 To + 1, the third inequality holds by the definition Cp, and the fourth inequality is due to T > 27o. and the last inequality holds by the definition of Tí.2. Therefore, we deduce that T122 max To, Tí. Then, we have that Goons (TAlg: f) O(To + ATI2) O(To + A
23

---

For some example functions f. we provide bounds on Coonst (FAlg: f) by providing bounds on and Ti.2. We write f(t) (t)) for a function g(t) when there exist constants C₁, C2 > 0 such that f(0 C1g(t) C2 for all N.
Example 1. Suppose f(t) [t/m| for some m N. This corresponds to executing Alg with fixed period m. We have (m) = mn, so TO = mTAlg. We now establish a bound on 71, that satisfies Eq. (6). We have
S m
Σ
m
max (((),
t
t=
S m(1 + log T).
Using elementary analysis,
show that after some time step O md 32Cgmdd (1 + log T) log(1 2T) < 'T' for all T 2 T, hence مi,2 = O
log" md)), holds that
A
md
md log" A holds. Combining
A
A
the bounds on and T(,2. we obtain
md
2 mdd
Gonnst (TAlg: J) = ITTAI
log
A
A
Example 2. Suppose f(t) = ((tg((lggt))) for some constant r 2 O. Then, (n) On n)"). Also, we have
T 1
T
(log (log1)") 1)"
Σ 0
max [f(t,
1=1
=0 (log
T12 is the first time step such that O( (log Tyr+2) < T for all T 2 Tí.2 and derive that
1. = -0 22 (log d )+2)) Therefore, we conclude that
d
Geona (TAlg: 1) = TAle (log TAIg)* + A
log
A
Example 3. Let f(t) = (2(tt) ) for some constant r E (0, 1). Then, f (n)(n) = O(n!/r), We have
T
max (J(1).) 5
= -T(T)))
For constant C 0, CT log < T' is equivalent to for all T' > with O((C' log 1r). Therefore, we have that for Tí.2 O(( d log holds that O 2z Tllrlolg T) S 7 for all T 2 -(.2. Therefore, we conclude that
T, and this incquality holds
d 2r)/,,,
( Alg
1
dlog d 37) A
Geons(TAlg:1 f)
A
2
Example Let f(t) {)(logt)") for some constant
Then, f f' -(0tt)) We have
max f(t),
(log t)
T (log T)
Then, Ti.2 must satisfy Ao Ty
T' for some constant C > or equivalently, Cd < (log?)--1 We that T/,2 cxp (O((d/ 22)1//-1111111 Therefore, conclude that
Car
Geons! coons((TAlg (TAlg. exp (0 (TAIS) + exp (o (0(()A))==)
24

---

A.4 Proof of Theorem 3
Proof of Theorem 3 For simplicity, we write π == INFEX(Alg, Te). We analyze the performance of under two linear bandit instances. Let A > 0 be fixed constant whose value is chosen later. We define the arm set as X = {er, Ou). where e1 E I the first standard basis vector and 0g E R is the zero vector. This instance can be viewed as the one-armed bandit setting since the agent is aware that the second arm has reward 0. The true parameter vectors are defined as 01 (-A, 0,....O) 0) and 82 (A, 0, ..... 0). In the first instance, (KK, 01), the expected reward of the first arm is A, while the second arm yields a reward of O. Thus, the second arm is the optimal arm. Conversely, in the second instance, (X, 02). the first arm yields an expected reward of A and the optimal arm. We assume that i.i.d. unit Gaussian noise is added to the observed reward.
Fix T E N. Let N1(T) and (T') be the number of times the first and second arms are selected up to time T. respectively. We define P1 to be the probability distribution over the trajectory induced by policy и interacting with instance (X,, 01) for T time steps, and define P22 similarly for the second
instance (X.02).
Let (x.) be the KL-diieegeece between two probability measures. By Lemma 15.1 in Lattimore and Szepesvári 2020], we have that
DKL. (TP, = 4 4
Let = (T) < T//2} the event that the first arm selected less than T/2 times. By
Lemma 12
we obtain that
(A(A) - P2(49) 2 exp(-Dxx(P1,)))
2
Under the first instance, we have R2
R2(T) (T) = (N) Using Markov's ' incquality, we obtain
that E, [T)] 2 (N2(T) 2 +)- (N) < F = FPP (A), which implies that E, [R~ (T) 2 2 (A). Using a similar argument, we also derive that Eg RR (T)) 2 P21).
Combining everything, we conclude that
AT
En [R) + R2 (2
N (
(((A)++2(4
2
AT
>
(DK(-DDL (P1,
AT
(7)
Now, we show that E2 [N1 increases too slowly when f(t) * w(og t). First, we show that the expected number of greedy selections of the first arm under the first instance is at most a constant. Let Ai (T) be the empirical mean of the first arm after T time steps. The greedy selection chooses the first arm only if úú (T)= 2 O. We bound the expected number of the averages of a Gaussian random walk exceeding A by the following lemma, whose proof is provided in Appendix C.5)
Lemma 5. Let Z1, Z2...... be sequence of i.i.d. samples of the unit Gaussian distribution and S, -'= Ze be its partial sum. Then, for any constant e >> 0, the expected number of indices n. such that Sn/n exceeds e is at most 22, that is, E 1 2 cHl < 2
For (T) 2 0 to hold, the average of the noises added to the random rewards of the first arm must be greater than A. Using Lemma we infer that
E Σ
= 1(x
< 2A²
Therefore, the expected number of suboptimal greedy selections is at most A..
Therefore, we have (T)) < 2 + J(T) since there are at most 2 suboptimal greedy selections and /(T) exploratory selections. By [(() & w(og l), there exists a constant C > 0 and infinitely many T E N such that ((T) S Coog T. We conclude that for infinitely many T, we have E[N, (T)) < _ + C' Colog T. Plugging this bound into Eq. 77) we obtain that for infinitely many
25

---

Algorithm 2 Linear Thompson Sampling
1: Input: Sampling distribution D
2: Initialize 1/-
3: for 2, ...,, do
4: Compute ridge estimator - X,Y,
V,
5: Sample 7/- DS
6: Compute perturbed parameter 0g = f + 3c-1 v 1/22
7: Choose X; = argınaxzex x. 0r and observe Y
8: Update = V/-1 X.X!
9:
end for
T' E N. it holds that
AT
1
E, [x)R,( (2(R.(())
2
4
exp
-4A²
2A
+ Clogg)
7
p1-1a 1220
2
It implies that either E, [R, (T)) Eg (T) exceeds A T1-4000 The proof is completed by taking& = vE/4C and c(f. Sea
Remark 3. In the proof of Theorem we show that E, [N))] S 2 + Cog 7) and
E, [R, (T)] = [NN so INFEX attains polylogarithmic regret for the first instance. Therefore, we can conclude that the instance that INFEX incurs almost linear regret is the second instance (X, 02).
B Instance-Dependent Regret Analysis of Linear Thompson Sampling
In this section, we provide an instance mestance-dependent polylogarithmic regret bound of LinTS (Agrawal and Goyal 2013 Abeille and Lazaric [2017]. For completeness, we present the algorithm in Algo- rithm where we use the version by Abeille and Lazaric [2017].
The input of the algorithm, TS is distribution over R.d We pose two conditions on the sampling distribution in Abeille and Lazaric (0017.
1. (anti concenroncetttiion) There exists a positive probability p such that for any u E Rd with 1,
PryDii (u 2 2p.
2. (concentration) There exists positive constants c, such that for all E Rd with ||lle = 1 and 8 E (0, 1).
(IuTT s V Velog c' d' ( )21 2-1-
P PIIDII
The first condition comes directly from Abeille and Lazaric 2017 We slightly strengthen the second condition to derive a tighter bound when log K < d. The original condition in Abeille and Lazaric (017)] poses that IP PT (117 2 < odd log(ccd//)) 2 1 8. Our strengthened condition implies the original condition by taking be the vectors of the standard basis and taking the union bound. The strengthened condition holds for all the distributions discussed in Abeille and Lazaric (017 including the multivariate Gaussian distribution and spherical distribution.
Now, assuming that the conditions are true, we prove Theorem
Proof of Theorem Let 7 := (,)5) min /ed (2 / (2eg((2'(72/0)) Our choice of " slightly differs from Abeille and Lazaric 2017]] : they choose be the first term in the minimum
26

---

instead of taking the minimum over the two values. We show that their analysis still applies even with this refined value of n/- Suppose " /clog22 By the concentration condition on DJS for any E RR, it holds that
Pt-1 (3e- (0) mh) <
21
21
Taking the union bound over x E X, we obtain
2 Pi-1 Vx E X, xx x (B- |r
= P Yx E N (3 (B S ~
2 1
21
This probabilistic inequality the only property "t must satisfy the analysis of Abeille and Lazaric [207)), therefore the results in their paper hold for this refined value of 7:.
We first decompose the instantaneous regret of LinTS as follows:
reg. = x== TT 0" -X, l"
xTTTT 0r x 0
X, 01-1 X
R2
Following the proof of Abeille and Lazaric 2017], we obtain that 12 47s E,-1
| and
RRLS I [,(6)]| By the definition of the minimum gap A, we have either reg, 0 or
reg, 24, which implies that reg, S reg? Therefore, we derive the following bound on reg,-
reg, V rege
[RTS + RRISJ2
A
2(12S)2 2
2(PRRLS)2
A
2
16
2 |
S
Bx_1
+ +..00)91xx011
A
p
2
1672
||X,1R B.(()) 11x0)
<
Ez-1 p²
A
where the second inequality uses that (a + 6)2 < 20² + 26² for all b E R, and the last inequality is due to Jensen's inequality. We bound ΣT= Em-11/x,111 using the following lemma that provides lower bound for sum of nonnegative random variables. Its proof is provided in Appendix C.6
Lemma Lei {x be sequence of real-valued random variables adapted to a filtration (- Suppose 0 < X, < for all t. For any (0, the following inequality holds for all n e with probability at least 1 8:
1 5
Σ EXx F--i 2 Σ
X, + 2 2log
[=1
Applying Lemma 6 on [||x||1 v= t. we derive that with probability least 1 8, it holds that
1 g + +2 X 1
Σ E, | 1ー
< 2
t
27

---

for all T E N. Therefore, the cumulative regret of LinTS is bounded as follows:
2
16
RLiNTS (T)
1
E1-1
|
A
pz
1=1
2
3211
+ (r(())
Σ |xell
32 1 8
log
A
p2
p2
4 A
132
16 1 aT + log
+ +r(
p²
p²
8
where the third inequality applies Lemma 11
Finally, plugging in (T O(ar + log ( and
ff (mminddlog oT 8 log KT o Har + log 3)) proves the theorem.
C Proofs of Technical Lemmas
In this section, we provide proofs of Lemmas 7o
C.1 Proof of Lemma
Proof of Lemma
7
Take TAlg' to be the least positive integer that satisfies
Cdd
log o TT
s AT
A
4
log T
for all T TAlg', which exists since lim
0. Elementary analysis shows that TAig'
T-00 T
d" O( 16+1 log" 2). Let (T) be the number of suboptimal selections made by Alg' up to time step T. Since a suboptimal selection incurs at least A regret, we have A (T) S RAig' (T). It implies that for any T' 2 TAlg', we have A (T) < $ AT, or equivalently, Nop((T) 2 4., which proves the lemma.
C.2 Proof of Lemma 2
In this subsection, we prove Lemma To do we show that the estimation error of the optimal reward x= T 8 scales with
where we need the following technical lemma. Its proof is VNaa(t)"
deferred to Appendix C.7
Lemma 7, We have that for all E N,
||x0 ||00|1 ll2- 5 1 Nop
Now, we prove Lemma
Proof of Lemma
The instantaneous regret of greedy selection can be bounded as follows:
reg, = T 0+ X, 0r TT 0² T 0 + X, - X, 0r
T (or (0--0, -0--1) + X2 (d.-1 - 0r)
(II="Ivz: llv
||00
+ || ) 110 -.
$ 3 (10*"|1__] + ||
where the first inequality uses that xx 0 S X, OT when X, chosen greedily, the second inequality is due to the Sauchy-Schwand incquality, and the last inequality comes from Lemmal 9
28

---

By the definition of the minimum gap A, we have either reg, = 0 or reg, > A, which implies that
reg, < reg2 Then, we obtain that
A
regg
reg, S
A
B
(|0*"|y
[|xollv
A
2
(100||
|
+
||
where the last inequality uses that (a + b)2 < 2(a² + 12) for any a, E IR. Taking the sum of instantaneous regret for E G(T, T), we proceed as follows:
(T.
Σ reg,
1E9(T,T)
2
||2-1|, V, +
+1IXal 1
A
(EA(T.T)
2
| v=1 +
Σ (EG(TTT)
(EG(T,T)
4ar
Σ
B
B0-111="11
(EG(T.T)
4aT PT
Σ
1+ (1-
tEG(T.T)
where the third inequality is due to Lemma and the last inequality applies Lemma 7
C.3 Proof of Lemma 3
Proof of Lemma 3. By the choice of TAlg. at least a quarter of the selections by Alg are optimal when
f(1) 2 TAlg. or equivalently, & Z (TAlg)))) It implies that (tpe(t) f)()). Then, holds that
Nop 1) 2 1 f((t 1) N 1 + (f(t) 1) N 1 ft). Plugging this bound into Lemma 2
we conclude that
40m 37
32_1
RINFEX(ANG, (TAlE: 7) (T-
Σ
A
1 Nopu (t
1)
tEG(F (((Au)))
4a 32
8
Σ
37_11
A
A
f(t)
LEG(J ((TA)).T
40. 32
8
Σ
33
A
f(1)
(EG(S-
Now, we show that this quantity is sublinear in T. By Lemma 10 we have at, 87 = Od T), 8a
so 4ayy is sublinear in T. By ((t) w(log() and B Od T",, have lim T(0)
which implies that EiEoy (.T)).T) T(J
is sublinear in T.
29

---

C.4 Proof of Lemma 4
Proof of Lemma
We decompose Vi as follows:
Vr = la + X,X,
t
la Σ
1(x =xx==x000 xxxx
+ Σ -xxx+xxxxx
Ia + Nop (T)="" TT
Σ 1
A B,
where we define A = 11 + Nop (T)x"* and B : Σ 1(x, + + +x,,, The eigenvalues of A are 1 + [op(TT]|==>>>
1,... 12, 1. Let bi 2 b2 2- ... ba be the eigenvalues of B. Finally, let 21 2 U2 2 ... 2 ti be the eigenvalues of Vr. By Lemma 13 we have
S (1 + [Top((")] (12) + b1
and
2 S (2 + bi-1 1+ 6
for
2....,d. Let N (T) == T Nop (T) be the number of suboptimal arm selections up to time T. Then, we have bj S ir(B) < Naub (7), so we infer that
01 S (1 + Nopt ||x" [12] + bi
Nopr (T)) 112 Nou (T) SI+T.
and
II 2 I 11 (1 + b;-1)
d-1
Σ Lima (1 + bi
d 1
1 + Ir( Lr(B)
d-1
1 Naub (T)
d-1
d
where the second inequality is the AM-GM inequality. Then, have det Vr
QT = log det Vo
log Us
1+ < log(1 + T) (d 1) (1+ Nuu((T)
(d (d-1)
Since a suboptimal selection incurs at least A regret, we have that AN (T') S RAIs (T'), or equivalently, Nswb(T) < A RAg (T). Plugging in this bound completes the proof.
C.5 Proof of Lemma
Proof of Lemma 5 Let ((-) be the cumulative density function of the standard Gaussian distribution. Since the distribution of S,/n follows the Gaussian distribution with mean 0 and variance 1/n, we have P( S.
2 c) =1 (n). Then, we have that
Sn 2
Σ
Sn
20]|
E
71
Σ
(1
((cVT)))
30

---

Since 1 - (c is a decreasing function with respect to n, we can upper bound the summation by an integral and conclude as follows:
((ovn)) -
$(cV1) di
5/4
dx dt
ovi V2T
00
dt da
2t
1
c
dr
22T
0
2n
where the first equality plugs the probability density function of the Gaussian distribution and the second equality interchanges the order of the integral, which is justified by Fubini's theorem since the integrand is continuous and positive.
C.6 Proof of Lemma
Proof of Lemma 6 For simplicity, denote E[- Fr-1] by E,-
= By e" 1 + 7 for all r S 0,
have that
Ex 1 (e
X1 S E E--1 X; x21
E, [X,] - [X7]
[x,]
$ e (X,)
where the second inequality uses that X, 2 and X? S X, when X, s 1 and the last
inequality holds since 1 1+ ex for all x E E. Then, M, exp (E (-X, + 1 is supermartingale. By Ville's maximal inequality, we have that P(3n E M, 2 ()) S 6. Taking the logarithm and rearranging the terms leads to the following conclusion:
1 + + 2 8 88.
Bn N: Σ E. EE-X2 2
Xx
C.7 Proof of Lemma
We prove Lemma 7 by proving the following more general lemma.
Lemma 8. For X, > 0 and x E IRd, let V be symmetric matrix with V > Ala + +nax T. Then,
| 5 N
Proof. It sufficient to consider the case V Ala + nax T only since || S | | In this case, we have
Vx = Ax + nzr
(> + n
Multiply x TV on the left to both sides and obtain
||~||
(A n
||
|
By reordering the terms, obtain that
| 13 A +
n
n=|
X+n n
completing the proof.
31

---

D Auxiliary Lemmas
Recall that ar = log det Vr and (T( = / + + 2og22llggg111 (1/6) + S. det
Lemma 9 (Theorem 2 in Abbasi- Yadkori al.
2011]).
With probability least
00- 0elly. S B,()) holds for all
Lemma 10 (Lemma 10 in Abbasi- Yadkori et
201 It holds that or I <dlog(1 + 7))
Lemma 11 (Lemma 11 in Abbasi- Yadkori al. 2011
For any sequence of X1..... X2 with
, X, B for all t ,,..., T, we have E(=
S 20r-
Lemma 12 (Bretagnolle-Hubee Huber inequality [Bretagnolle and Huber 1979. Theorem 14.2 in Lattimore and Szepesvári (2200). ) Let P and Q be two probability measures the same measurable space F). Let D PP, Q log dE dIP be the Kullback- divergence between IP and Q Then, aq for any event A E F, it holds that
P(A) + Q(19)))))))) 2 ( Q))-
Lemma 13 (Weyl's inequality [Weyl 1912). ). For Hermitian matrix A E Cddd, let \1 2 ... . (A) be its eigenvalues sorted from from large to small. For two Hermitian matrices A, B E Cddd and any S i.j S d with + 1 holds that
B)) +
E Extension to Time- Features
In this section, we discuss the possibility of relaxing the assumption of requiring a finite and fixed arm
Previous literature on greedy bandit algorithms [Bastani et al. 2021 Kannan et al. 2018 Sivaku mar et al. 2020 Raghavan et al., 2023 Kim and Oh 2024] has established the effectiveness of purely greedy selections under certain favorable context distributions, specifically when features drawn i.idd from distributions with suitable diversity conditions. Under such conditions, the regret contributions from the base exploratory algorithm and greedy selections can be analyzed separately. Moreover, since analysis primarily assumes fixed optimal arm x=, the theoretical results provided in Theorem [ reedily extend to contexts where the optimal arm remains invariant.
However, an important and open challenge remains: extending the performance guarantees of INFEX to scenarios involving dynamically varying optimal arms. Addressing these more general cases non- trivial, as our current analysis relies on the property that estimation errors of x= 0* diminish when the optimal arm is selected frequently. This property becomes less straightforward to guarantec when the optimal arm itself is random tarmevarying. Notably, pointwise guarantees for linear regression with random design require additional distributional assumptions [Hsu et al.) 2012), suggesting that bounding the estimation error of random optimal arm without assumptions may be infeasible.
Meanwhile, Hanna al. 2023) propose reduction technique that enables linear bandit algorithms to address linear contextual bandit problems when the arm set is sampled i.i.d. from a fixed distribution. Their results, however, focus on worst-case O -typee regret, which is suboptimal in our context where
polylogarithmie regret is desired. Additionally, while greedy selection chooses the same arm irrespective of this reduction, the parameter update involves mismatch: the observed reward Y, from the selected arm X, is attributed to a potentially different predetermined vector X Despite these challenges, the approach by Hanna al. (2023) underscores the feasibility of adapting linear bandit methods to contextual scenarios, suggesting promising directions for extending results in future work.
32

---

Additional Experiments
We provide additional experimental results for different values of d omitted in Section Except for the difference in the ambient dimension d. the generation of the problem instances and the algorithms identical to those described in Section Figure presents the result when d 20 and Figure presents the result when d = 40. We observe the same trends as in the case where d = 10. Even for larger d, INFEX consistently demonstrates efficiency both regret and computational time.
All hyperparameters the algorithms are set to their theoretical values. Both LinUCB and LinTS det
require the confidence radius 8,. We explicitly compute the value of log det Vo using rank-one update [Abbasi- Yadkori et al. 2011] instead of using its upper bound d dolog T, so that the base algorithms achieve the regret bounds of Theorem 5 in Abbasi Yadkori et al. [201T] and Theorem 2 We expect that the regret reduction achieved by INFEX would have been even more significant if the base algorithm had used crude upper bound for the confidence radius.
The experiments are conducted on computing cluster with twenty Intel(R) Xeon(R) Silver 4214R CPUs, and three of them are used for the experiments. The total runtime of the entire experiment is approximately one hour.
33

---

Experiment 10000
LinUCB
LinTS
Greedy
INFEX(LinUCB, 5N)
INFEX(LinTS, SNI INFEX(LInTS, 20N)
OLSBandit
INFEXILInUCB, 20N)
e-Greedy
INFEXILinUCB, 100N)
INFEX(LiNTS, 100N)
Total Regret 10)
Computation Time (K 10)
2.5
2500
Computation Timels)
Total Regret
2000
1.5
1500
1000
500
0.0
Total Regret (K 100)
Computation Time (K 100)
4000
Computation Timets)
Total Regret
3000
1.5
2000
1.0
1000
0.5
Total Regret (K 1000)
Computation Time (K 1000)
50
Computation Time(s)
Total Regret
4000
30
2000
20
1000
10
Figure 2: Comparison of total regret (left) and computation time (right) when 20, 10000,
and K 10 (top), K 100 (middle), and K 1000 (bottom).
34

---

Experiment T 10000
LinUCB
LinTS
Greedy
INFEX(LinUCB, 5N)
INFEX(LinTS, SNI
OLSBandit
INFEXILInUCB, 20N)
INFEX(LINTS, 20N)
e-Greedy
INFEXILinUCB, 100N)
INFEX(LiNTS, 10ON)
Total Regret 10)
Computation Time (K 10)
Computation Timels)
Total Regret
1500
1000
2-
500
Total Regret (K 100)
Computation Time (K 100)
3000
Computation Timels)
2500
20
Total Regret
1500
1000
500
Total Regret (K 1000)
Computation Time (K 1000)
120
4000
100
Computation Time(s)
3000
Total Regret
80
40
1000
20
Figure 3: Comparison of total regret (left) and computation time (right) when 40, 10000,
and K 10 (top), K 100 (middle), and K 1000 (bottom).
35


Reviews:
[{"review_id": "8IfkPySXuH", "reviewer": "Reviewer_386q", "summary": "This paper studies the theoretical regret guarantees of infrequent exploration in linear bandits. Specifically, this work proposes INFEX, which interleaves greedy actions and the use of an adaptive exploratory policy, and establishes that INFEX achieves a polylogarithmic instance-dependent regret bound under the condition that number of exploration steps is at least $\\omega(\\log t)$. As a result, this work fills the gap between the fully exploratory methods and the purely greedy method in linear bandits. Moreover, the paper complements the regret analysis with numerical simulations, showing that INFEX can attain strong empirical regrets while achieving less computation time compared to the two base linear bandit algorithms LinUCB and LinTS.", "questions": "1. This paper assumes that the arm set is finite and fixed, but the more common setting in the (generalized) linear bandit literature is that the arm set can be arbitrary or time-varying. Can the authors comment on whether these assumptions are indeed needed or the results can be readily extended to the more standard linear bandit settings?\n\n2. While I can see that this work mainly focuses on instance-dependent regret bounds, I wonder if the infrequent exploration can possibly hurt the minimax regret bound. Can the authors comment on this?\n\n3. From the numerical results in Figure 1, it appears that INFEX typically has higher standard deviation in regret as the exploration budget gets smaller. This can be an undesired property in practice as the regrets in different trials can vary quite significantly.", "limitations": "The work does not describe any potential limitations in the main paper.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The proposed INFEX is a generic and conceptually simple infrequent exploration method that nicely bridges the gap between the various existing adaptive exploratory bandit algorithms and the purely greedy policy. This offers interesting new insights into the linear stochastic bandit problems.\n- The proposed INFEX achieves an instance-dependent regret bound for any linear bandit algorithm with polylogarithmic regret (under some mild exploration condition). The results accordingly gives a new instance-dependent regret bound for LinTS, which can be of independent interest to the bandit community.\n- One empirical benefit of using INFEX is that under some base bandit algorithms (such as LinTS and LinUCB), the infrequent exploration mechanism can reduce the overall computation time required while still achieving similar scaling of regret.\n- Overall, the writing is very clear, and the proof sketch nicely highlights the important steps of the regret analysis, which makes the paper easier to read.\n\nWeaknesses\n\n- While I can appreciate the contribution regarding the algorithm and the established regret bounds, I do find INFEX somewhat not that easy to use in practice. Specifically, as shown in Theorem 1 and Table 1, the choice of exploration schedule can significantly affect the $G_{const}$, which depends on multiple problem-dependent and algorithm-dependent parameters. These parameters are typically unknown and hence make it difficult to optimize the trade-off between $G_{const}$ and the other regret terms. Therefore, in practice, it is hard to choose a proper exploration schedule and the resulting $f(t)$ a priori.\nOne quite possible scenario is that infrequent exploration can incur a much higher regret by using infrequent exploration despite that the computation time can be somewhat reduced. Without addressing the above issues with the choice of exploration schedule, I find the algorithm not as promising as claimed despite that theoretically this is an interesting contribution.\n\n- While I can see that this work mainly focuses on instance-dependent regret bounds, I wonder if the infrequent exploration can possibly hurt the minimax regret bound. For example, suppose we use LinUCB and consider the degenerate case where each arm $i$ is a one-hot vector with the $i$-th element being one and $\\theta$ is $K$-dimensional with the $i$-th entry being the mean reward of arm $i$, then intuitively, if the resulting exploration budget is only as small as $f(t)=\\log^m t$ with $m>1$ (which still satisfies the condition in Theorem 1), then the minimax regret can be linear in $T$. With that said, I believe that this work can be strengthened if a discussion on the resulting minimax regrets can be provided as well. \n\n- Another concern is that this paper assumes that the arm set is finite and fixed, but the more common setting in the (generalized) linear bandit literature is that the arm set can be arbitrary (e.g., OFUL [Abbasi-Yadkori et al., 2011] and LinTS [Abeille and Lazaric, 2017]) or time-varying (e.g., LinUCB [Li et al., 2010] and UCB-GLM [Li et al., 2017]). It is not immediately clear to me whether the regret bounds in Theorems 1-2 can be directly extended to the more standard linear bandit settings.", "was_revised": true, "final_justification": "This paper studies the theoretical regret guarantees of infrequent exploration in linear bandits. The contributions are mainly two-fold: (1) This work proposes INFEX, which interleaves greedy actions and the use of an adaptive exploratory policy (2) This work establishes that INFEX achieves a polylogarithmic instance-dependent regret bound under the condition that number of exploration steps is at least $\\omega(\\log t)$.\n\nIn my initial review, the main concerns are: (1) INFEX can be not that easily applicable in practice due to the need for choosing a proper exploration schedule. (2) While INFEX still achieves polylogarithmic instance-dependent regret bound, the infrequent exploration can possibly hurt the minimax regret bound, especially when the exploration budget is small (e.g., polylogarithmic in $T$). (3) This paper assumes that the arm set is finite and fixed, and this differs from the (generalized) linear bandit literature where the arm set can be arbitrary or time-varying.\n\nThrough the multi-round discussions during rebuttal, the authors addressed the concerns (1) and (3) and also offered helpful remarks on the minimax regret bound. Overall I am happy to see this paper accepted if these improvements and discussions can be incorporated into the final version.", "rebuttal": "We appreciate the reviewer’s time and effort in evaluating our paper and providing valuable feedback.\nWe are grateful for the recognition of our contributions and the detailed comments.\nBelow, we address each of the comments and questions in detail.\n\n---\n\n**[W1] (On the choice of exploration schedule)**\n\nWe are more than happy to have the opportunity to clarify this point.\n\nFirst of all, we would like to clarify that our main focus is not specifying the ``proper'' exploration schedule or frequency per se. \nAs stated in the Introduction, there are many practical scenarios in which the possible amount of exploration is already constrained due to logistical reasons such as costs, risks, and ethical considerations.\nIn such cases, one does not even have the freedom to choose $f(t)$.\nOur main contribution lies in showing that even in such scenarios, one can achieve polylogarithmic regret as long as the exploration budget is super-logarithmic in $t$, complemented by showing that such a condition is necessary in Theorem 3 in Appendix A.4.\n\nOn the other hand, there may be cases where there is no constraint on the amount of exploration, and it is true that our paper does not suggest speicific exploration schedule in this case.\nYet, theoretical bounds are still greatly meaningful in that they provide the principled ground on how often the exploration algorithm should be executed in order to achieve polylogarithmic regret.\nIn addition, the numerical experiments show that the performance of $\\texttt{INFEX}$ is not sensitive to the choice of $f(t)$.\nThe simulated exploration schedule significantly varies from at least 100 total exploratory time steps to at most 2000 total exploratory time steps, and most configurations show superior performance compared to their base algorithms and the pure greedy policy.\nBeing able to be combined with any base algorithm without additional computational or implementational burden, we confidently claim that our method IS easy to use in practice.\nFor example, it is better to use TS with, say, a few steps intervals mixed with greedy action (rather than running TS at every time step), and the exact specification of $f(t)$ is not even needed to achieve a favorable practical performance.\nOverall, our proposed method and its theoretical results carry meaningful implications and impact on practical use.\n\n\n**[W2/Q2] (Minimax regret)**\n\nProviding the worst-case minimax regret bound for $\\texttt{INFEX}$ would indeed be an interesting problem, however it is beyond the scope of our paper, and we believe that not providing it should not be considered as a weakness.\nThe main reason we focus on instance-dependent bounds is to show how the regret changes depending on the exploration schedule for a fixed instance.\nFurthermore, minimax bounds might be too conservative for practical purposes, as they only focus on the worst-case regret and guarantee nothing more about the other instances which are more likely to be encountered in practice.\nAs to the question of whether infrequent exploration can hurt the minimax bound, although we cannot provide theoretical guarantees or counterexamples at the moment, we agree that overly insufficient exploration is likely to lead to higher worst-case minimax bounds.\nHowever, we speculate that it will be sublinear in $T$ for some (or all) exploration schedules considered in this paper given that the instance-dependent bounds are polylogarithmic.\n\n\n**[W3/Q1] (Fixed and finite arm set)**\n\nWe are glad to have the opportunity to discuss this point.\n\nWe first clarify that Theorem 2 only requires the positivity of the minimum gap $\\Delta$ and can be applied to arbitrary, time-varying arm sets. Finiteness is only assumed to naturally induce the definition of $\\Delta$, so as long as $\\Delta$ is well-defined and positive, the finiteness of the arm set is not required.\nThis applies to Theorem 1 as well.\n\nAs for the requirement of a fixed arm set in Theorem 1, there are some possible generalizations.\nFirst, our analysis only requires the optimal arm to be fixed across time, rather than the entire arm set.\nThe conditions for Theorem 1 are exactly the same as those for Theorem 5 in Abbasi-Yadkori et al. [2011] (although not explicitly mentioned, the proof requires -- and only requires -- the optimal arm to be fixed).\nIn addition, we note that, counterintuitively, the greedy policy performs worse with fixed arm sets than with time-varying arm sets.\nUnder certain diversity assumptions on the context distribution, the varying arm sets automatically offer exploration even if the agent acts greedily [Kannan et al., 2018, Sivakumar et al., 2020, Bastani et al., 2021, Raghavan et al., 2023, Kim and Oh, 2024], allowing the pure greedy policy to achieve small regret.\nIn this case, $\\texttt{INFEX}$ naturally inherits the guarantees provided by the cited works in their respective settings.\nOn the other hand, there are examples with fixed arm sets where the greedy policy fails (Example 1 in Jedor et al. [2021]) and insufficient exploration fails (Theorem 3 in Appendix A.4).\nTherefore, it should be surprising that $\\texttt{INFEX}$ achieves polylogarithmic regret even when the arm set is fixed, despite performing greedy selections at most of the time steps.\n\nYet, we admit that the setting where $\\texttt{INFEX}$ is guaranteed to work well is not fully general, and generalizing Theorem 1 even further seems challenging for now. Please refer to Appendix E for more discussion on the possibility of extending the analysis to the time-varying arm sets.\n\n**[Q3] (Higher standard deviation)**\n\nSince the greedy policy has a high standard deviation, we believe it is natural that more greedy selections lead to a higher standard deviation.\nHowever, our simulations demonstrate that even when the greedy policy is deployed at most of the time steps, for instance, 99\\% of the time steps, the standard deviations of the regret are significantly smaller than the one by the purely greedy policy, being roughly 50\\% instead of 99\\%, which should be considered as a strength of $\\texttt{INFEX}$.\nWhile we agree that high standard deviation may be undesired in practice, we do not find the observed values to be critically high in the experiment.\nAdditionally, we hope that having a higher standard deviation does not obscure the fact that $\\texttt{INFEX}$ achieves small average regret, which is highly desired in practice."}, {"review_id": "OfacoEFv1E", "reviewer": "Reviewer_oBP9", "summary": "This paper proposes INFEX, a general framework for linear contextual bandits that performs infrequent exploration. It aims to bridge the gap between: \n- \"Fully\" exploratory algorithms like UCB or Thompson Sampling, which explore continuously but may be ethically problematic in practice; and \n- greedy algorithms, which completely avoids exploration but require strong assumptions (e.g., persistent feature diversity) to achieve good regret.\n\nTheir algo, INFEX, maintains a predefined exploration schedule, running a base exploratory algorithm (e.g., LinUCB) at these rounds, and acting greedily in other rounds. The main result shows that INFEX achieves instance-dependent regret bounds matching standard algorithms, as long as the exploration schedule is superlog.", "questions": "see above", "limitations": "see above", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- Clarity and simplicity: The algorithm is intuitive, easy to implement, and compatible with many existing base algorithms.\n- Clean results: The paper proves that logarithmically infrequent exploration suffices to maintain optimal performance in the linear bandit setting. \n- Practical motivation: The framework is well-motivated for domains like healthcare or safety-critical systems, where constant exploration may be infeasible.\n- Good writing: Overall, the paper is easier to read and better organized than many others.\n\n**Weaknesses.** The authors repeatedly state that previous works require “strong distributional assumptions,” particularly for greedy policies. However, it is not clearly explained what these assumptions are, why they are necessary for greedy algorithms, and why INFEX avoids them. A more explicit comparison (ideally with counterexamples or illustrations) would greatly strengthen the paper. \n\nIn particular, what are the “bad cases” that INFEX handles well? It would be illuminating to show specific examples where greedy fails but INFEX succeeds — this would clarify the paper’s practical impact.", "was_revised": true, "final_justification": "I will maintain my initial evaluation.", "rebuttal": "We sincerely thank the reviewer for the positive evaluation and thoughtful comments.\nWe deeply appreciate your recognition of our contributions.\n\nWe are more than happy to elaborate further on this question by the reviewer.\n\nIn the linear contextual bandit setting, the \"strong distributional assumptions\" required for the greedy policy to work well [Kannan et al., 2018, Sivakumar et al., 2020, Bastani et al., 2021, Raghavan et al., 2023, Kim and Oh, 2024] refer to the assumptions that the context distribution of the arms is sufficiently diverse to allow the greedy policy to automatically explore and achieve small regret.\nWhile the greedy policy does not explore explicitly, varying the arm set at each time step can lead it to select arms in diverse directions, possibly spanning the full $R^d$ space, and thus gain information.\nThe cited works formalize the conditions under which the greedy policy benefits from such diversity and achieves low regret.\n\nSpecifically,\n\n- Kannan et al. [2018], Sivakumar et al. [2020], and Raghavan et al. [2023] assume that the context vectors are perturbed by a multivariate Gaussian distribution at each time step, forcing the context distribution to be diverse.\n- Bastani et al. [2021] directly assume covariate diversity (Assumption 3 in their paper), assuming a positive minimum eigenvalue of the covariate matrix of the selected feature vector, which guarantees linear increase of the minimum eigenvalue of the empirical covariate matrix.\n- Kim and Oh. [2024] propose a more general condition on the context distribution under which the greedy policy achieves polylogarithmic regret.\n\nHowever, all of these assumptions rely on the arm set being randomly changed over time.\nNone of these analyses apply when the arm set is fixed across time steps.\nIn fact, it is not the matter of the analysis as there are counterexamples with fixed arm sets where the greedy policy fails (Example 1 in Jedor et al. (2021)) and insufficient exploration fails (Theorem 3 in Appendix A.4).\nTherefore, the \"bad cases\" that $\\texttt{INFEX}$ handles well are those with fixed arm sets, achieving polylogarithmic regret even in such settings.\nWe will add more details about this point in the final version of the paper."}, {"review_id": "CfRbsiXfTF", "reviewer": "Reviewer_NfJs", "summary": "This paper studies the problem that lies in the intersection between fully adaptive algorithms that explore at every step and greedy algorithms that do not explore. In particular, the authors are interested in whether infrequent exploration can achieve near-optimal regret while reducing exploration costs and computational burden. To address this, they propose a new general algorithm, INFEX, that allows a base algorithm as an input and decides a schedule for which the algorithm explores or commits. The authors show regret bounds for their algorithm and show that these bounds match with the bounds of fully adaptive algorithms asymptotically. The authors also show numerical experiments that compare the empirical performance of INFEX with fully adaptive and greedy algorithms.", "questions": "- In Theorem 1, you provide a regret bound that holds \"with high probability\", which is a bit unusual since high probability statements often occur in best-arm identification instead of regret. Is this a probability 1 statement? If it is with probability 1-delta, where can I see the dependence of delta in the statement of Theorem 1?\n- Also in Theorem 1, can you describe intuitively what the constants a,b, and c are, and in which scenarios they would be large?\n- Can you explain intuitively why inefficient exploration for the instance you constructed in the numerical experiment has a benefit? I'm a bit surprised that for this instance, INFEX even beats LinUCB which is fully adaptive. I would imagine infrequent exploration gives benefits mostly computationally, but not necessarily a better regret bound. \n- Also, it would be good to understand why no exploration, e.g. LinTS, performs so poorly here. \n- Does INFEX work in settings with budget constraints? I was thinking whether you could frame some objectives for which the number of exploration is limited due to e.g. resources or time, so we have to do infrequent exploration here. Could the authors provide some intuition on whether their algorithm will or will not work in this case, or they are different settings?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n- In terms of clarity, the writing is very clear with sections and subsection titles, also the authors stated contributions very clearly. \n- In terms of quality, the proposed framework is quite general, in the sense that we can plug in a lot of existing algorithms. \n- The numerical experiments and visualizations are clear, and the authors compare their algorithms with various benchmarks. \n\nWeaknesses: \n- In terms of significance, the motivation could be discussed further, especially in terms of practical use. The authors mentioned this in their last open question, \"Can infrequent exploration methods also demonstrate practical advantages beyond theoretical considerations?\", but I'm not sure if the authors fully answered it in this paper.", "was_revised": true, "final_justification": "The authors' detailed and clear responses addressed my concerns. I will keep my score.", "rebuttal": "We appreciate the reviewer’s time and effort in evaluating our paper and providing valuable feedback.\nWe sincerely thank the reviewer for the supportive and constructive comments.\nBelow, we address each of the comments and questions in detail.\n\n---\n\n**[W] (Practical use)**\n\nWe are more than happy to have the opportunity to clarify this point.\n\nFirst of all, we would like to emphasize that there are many practical scenarios in which the possible amount of exploration is constrained due to logistical reasons such as costs, risks, and ethical considerations, as described in the Introduction.\nOur main contribution lies in showing that even in such scenarios, one can achieve polylogarithmic regret as long as the exploration budget is super-logarithmic in $t$, complemented by showing that such a condition is necessary in Theorem 3 in Appendix A.4.\nBeing able to be combined with any base algorithm without additional computational or implementational burden, we confidently claim that our method IS practical.  \nIn addition, the performance of $\\texttt{INFEX}$ is not only limited to theoretical growth orders, but also has empirical superiority as shown through numerical simulations.\nThe experiments further show that the performance of $\\texttt{INFEX}$ is not sensitive to the choice of $f(t)$, showing superior performance in most configurations.\nAssuming one uses, for example, TS for practical purposes, the experiment shows that it is better to use TS with, say, a few steps intervals mixed with greedy action, rather than running TS at every time step, where a wide range of exploration schedules (from one out of five to one out of one hundred time steps) generally improves performance.\n\nOverall, our proposed method and its theoretical results carry meaningful implication and impact on practical use.\n\n\n**[Q1] (\"With high probability\")**\n\nAs mentioned in Section 4.1, \"with high probability\" means with probability $1 - \\delta$ in this paper, and the shown bounds correspond to the case where $\\delta = 1 / T$, (or more precisely, the bounds are invariant up to constant factors when $\\delta$ is regarded as a constant or when $\\delta$ decreases polynomially in $1/T$).\n$\\log \\frac{1}{\\delta}$ factors can be recovered by replacing some of the $\\log T$ factors with $\\log \\frac{T}{\\delta}$ factor.\nWe omitted the dependence on $\\delta$ since explicitly writing it out only leads to unnecessarily complicated bounds without providing much additional information; for example, the order of $G(T)$ becomes $\\frac{1}{\\Delta}(\\log \\frac{T}{\\delta} + d \\log \\log T + d \\log \\frac{d}{\\Delta})(\\log T + d \\log \\log T + d \\log \\frac{d}{\\Delta})$ instead of $\\frac{1}{\\Delta}(\\log T + d \\log \\log T + d \\log \\frac{d}{\\Delta})^2$.\nNote that $\\texttt{INFEX}$ does not require the value of $\\delta$ for its execution, unless required by the base algorithm, which gives us the freedom to choose $\\delta = 1/ T$.\nIf the expression causes confusion, we will replace the phrase with another one in the final version.\n\n\n**[Q2] (Constants $a, b,$ and $c$)**\n\nThe constants $a, b,$ and $c$ quantify the regret performance of the base algorithm, $\\texttt{Alg}$.\nThey would be large when $\\texttt{Alg}$ is an inefficient algorithm.\nFor $\\texttt{LinUCB}$, we have $a = 2, b = 1$, and $c = 2$ (Theorem 5 in Abbasi-Yadkori et al. (2011)).\nFor $\\texttt{LinTS}$, we have $a = 3, b = 1$, and $c = 3$ (Theorem 2).\n\n**[Q3] (Empirical superiority)**\n\nWe conjecture that $\\texttt{INFEX}$ empirically reduces the regret by avoiding unnecessary exploration.\nOnce the estimator becomes accurate enough to distinguish the optimal arm, a greedy selection would incur less instantaneous regret than exploratory ones.\nIndeed, LinUCB explores fully adaptively, but is based on the worst-case confidence bounds.\nEven when the estimator correctly identifies the optimal arm, LinUCB conservatively chooses other arms as long as they have a certain amount of probabilities of being optimal in the worst cases.\nWe believe $\\texttt{INFEX}$ benefits when such \"worst cases\" do not occur, allowing it to successfully exploit the optimal arm for most time steps.\n\n**[Q4] (Performance of LinTS)**\n\nLinTS theoretically requires a $\\sqrt{d}$-factor inflation in its perturbation, which results in a multiplicative $\\sqrt{d}$ factor in its minimax regret [Agrawal and Goyal, 2013, Abeille and Lazaric, 2017], and a $d$ factor in its instance dependent regret (Theorem 2), compared to LinUCB.\nSince larger perturbation in LinTS corresponds to excessive exploration, this additional factor is reflected in the empirical results as well.\nWe believe that $\\texttt{INFEX}$ significantly improves the performance of LinTS in the numerical simulation since it naturally limits excessive exploration.\n\n\n**[Q5] (Budget constraints)**\n\nWe thank the reviewer for this question, and we would like to further highlight the significance of our paper.\n\nYes, our work can be directly applied in such settings.\nThe exploration budget -- or even more generally, the whole exploration schedule -- may be given by external sources, and we do not assume that the agent has the freedom to adjust it.\nOur algorithm and theoretical results remain perfectly valid even in such cases, where we  only require the exploration budget $f(t)$ to be superlogarithmic in $t$.\nWe also show that this condition is necessary in Theorem 3 in Appendix A.4, showing that if the allowed exploration budget does not exceed the logarithmic barrier, then there exists an instance where no algorithm succeeds.\nIn the budget-constrained setting, this lower bound could be of independent interest."}, {"review_id": "GKTiYlZRuu", "reviewer": "Reviewer_yhSE", "summary": "This paper provides a generic algorithmic template for infrequent exploration in stochastic linear bandits. It provides a simple meta algorithm that attains near-optimal regret, with a near-optimal regret bound. The algorithm can at most tolerate $w(\\frac{\\log t}{t})$ frequence exploration, in the asymptotic regime when $d$ is treated as a constant.", "questions": "See Strengths And Weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** the result is novel and technically elegant. It uses a simple meta algorithm by reduction to black-box linear bandit algorithms. The regret bound is also generic and reflects trade-offs between factors.\n\n**Weakness:** the statement of the main theorem should clarify that $f(t)=w(\\log t)$ for any $t$, otherwise it would lead to a pathological interpretation.\n\nIt would be beneficial to have a more detailed, quantitative discussion on the trade-off between regret and exploration, mainly on the effect of $G(T)$. For example, one question in my mind is that when (how large $T$ grows in $d$) frequent exploration is for free, for different choices of $f(t)$ from the table.", "was_revised": true, "final_justification": "I've read the author's response, which addressed my question, and I will maintain my score.", "rebuttal": "We sincerely thank the reviewer for the positive evaluation and thoughtful comments.\nWe have carefully considered each point and provide our detailed responses below.\n\n---\n\n\n**[W1] (f(t) = w(log t) *for all t*)**\n\nAs defined in Section 4.1, we only require the asymptotic growth condition $f(t) = \\omega(\\log t)$ as $t \\rightarrow \\infty$, not for every $t$.\nThis condition is weaker than requiring the growth condition to hold for all $t$.\nWe will add \"as $t \\rightarrow \\infty$\" in the final version for clarity.\nFurther, Theorem 3 in Appendix A.4 shows that $f(t) = \\omega(\\log t)$ is a necessary condition.\nGiven these points, we believe this should be considered a strength rather than a weakness.\n\n\n**[W2] (Trade-off between regret and exploration)**\n\nWe would like to clarify that in Theorem 1, $G(T)$ is unaffected by the exploration schedule.\nAs long as the number of executions of the base algorithm is super-logarithmic in $t$, the asymptotic regret of $\\texttt{INFEX}$ remains the same, regardless of the exploration schedule.\nTherefore, there is no trade-off between exploration and $G(T)$, which we believe is one of the most interesting findings of the theorem.\n$G_{\\text{const}}$, which is the $T$-independent regret term incurred by the additional greedy selections, is affected by the exploration schedule, and its dependence on some example $f(t)$ is shown in Table 1.\nA more specific derivation can be found in Appendix A.3.  \nWhile infrequent exploration is not free in general in terms of non-asymptotic regret, if the reviewer is curious about the exact closed-form expression of the relationship between $T$ and $d$ where the $T$-dependent terms dominate the constant terms, it is slightly tricky to state it as it also depends on the performance of the base algorithm.\nInstead, we provide the total regret when the base algorithm $\\texttt{Alg}$ is LinUCB or LinTS for the examples of $f(t)$ in Table 1, where we omit the $\\mathcal{O}(\\cdot)$ symbol for simplicity.\n\n\n| $\\texttt{Alg}$ | $f(t)$ | Total regret |\n|------|---|---|\n|$\\texttt{LinUCB}$ | $t / m$   | $\\frac{1}{\\Delta}(\\log T + d \\log \\log T)^2 + (m + \\frac{d}{\\Delta})\\frac{d}{\\Delta} \\log^2 \\frac{d}{\\Delta}$|\n|$\\texttt{LinUCB}$ | $t / (\\log t)^r$ | $\\frac{1}{\\Delta}(\\log T + d \\log \\log T)^2 + \\frac{d^2}{\\Delta^2}\\log^{2+r} \\frac{d}{\\Delta}$|\n|$\\texttt{LinUCB}$ | $t^r$ $(r \\in (0, 1])$ | $\\frac{1}{\\Delta}(\\log T + d \\log \\log T)^2 + (\\frac{d}{\\Delta}\\log \\frac{d}{\\Delta})^{\\frac{2}{r}}$|\n|$\\texttt{LinUCB}$ | $(\\log t)^r$ $(r > 1)$ | $\\frac{1}{\\Delta}(\\log T + d \\log \\log T)^2 + \\exp( (\\frac{d}{\\Delta}\\log \\frac{d}{\\Delta})^{\\frac{2}{r}} ) + \\Delta \\exp ( (\\frac{d}{\\Delta^2})^{\\frac{1}{r-1}} )$|\n|$\\texttt{LinTS}$ | $t / m$   | $\\frac{1}{\\Delta}(d \\log \\frac{dT}{m})(\\log T + d \\log \\log T)^2 + \\frac{d^3}{\\Delta^2} \\log^3 \\frac{d}{\\Delta} + \\frac{md}{\\Delta} \\log^2 \\frac{d}{\\Delta}$|\n|$\\texttt{LinTS}$ | $t / (\\log t)^r$ | $\\frac{1}{\\Delta}(d \\log dT)(\\log T + d \\log \\log T)^2 + \\frac{d^3}{\\Delta^2}\\log^{3+r} \\frac{d}{\\Delta}$|\n|$\\texttt{LinTS}$ | $t^r$ $(r \\in (0, 1])$ | $\\frac{1}{\\Delta}(d \\log dT)(\\log T + d \\log \\log T)^2 + (\\frac{d^{\\frac{3}{r}}}{\\Delta^{\\frac{2}{r}}}\\log^{\\frac{3}{r}} \\frac{d}{\\Delta})$|\n|$\\texttt{LinTS}$ | $(\\log t)^r$ $(r > 1)$ | $\\frac{1}{\\Delta}(d \\log (d\\log T) )(\\log T + d \\log \\log T)^2 + \\exp( \\frac{d^{\\frac{3}{r}}}{\\Delta^{\\frac{2}{r}}}\\log^{\\frac{3}{r}} \\frac{d}{\\Delta} ) + \\Delta \\exp ( (\\frac{d}{\\Delta^2})^{\\frac{1}{r-1}} )$|"}]

Author rebuttal:

Meta-review: The paper studies the problem of infrequent exploration in linear bandits. Specifically, the authors analyze whether infrequent exploration can achieve near-optimal regret while reducing both exploration costs and computational burden. They propose a new general algorithm, INFEX, which takes a base algorithm as input and determines a schedule for when the algorithm should explore versus commit. The authors derive regret upper bounds for INFEX, showing that these match the bounds obtained by fully adaptive algorithms. Numerical experiments further support the theoretical findings.

The paper’s contributions were unanimously acknowledged, and reviewers particularly appreciated the generality and elegance of the results. A few interesting points were raised during the rebuttal phase that should be incorporated into the camera-ready version of the paper—most notably, the discussions with reviewers 386q and yhSE.
Decision: Accept (poster)