Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit
Authors: Seok-Jin Kim
Min-hwan Oh
Venue: NeurIPS 2024 poster (2024)
Keywords: contextual bandit
greedy algorithm
exploration-exploitation
sequential decision-making
bandit algorithms
Primary area: bandits

Abstract: We study the performance guarantees of exploration-free greedy algorithms for the linear contextual bandit problem. 
We introduce a novel condition, named the \textit{Local Anti-Concentration} (LAC) condition, which enables a greedy bandit algorithm to achieve provable efficiency. 
We show that the LAC condition is satisfied by a broad class of distributions, including Gaussian, exponential, uniform, Cauchy, and Student's~$t$ distributions, along with other exponential family distributions and their truncated variants. 
This significantly expands the class of distributions under which greedy algorithms can perform efficiently. 
Under our proposed LAC condition, we prove that the cumulative expected regret of the greedy algorithm for the linear contextual bandit is bounded by $\mathcal{O}(\operatorname{poly} \log T)$. 
Our results establish the widest range of distributions known to date that allow a sublinear regret bound for greedy algorithms, further achieving a sharp poly-logarithmic regret.

Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit
Seok-Jin Kim
Min-hwan Oh Scoul National Univeristy Scoul, South Korea minohêsnu. ac. kr
Columbia University
New York, NY, USA
seok-j jink kim@coluubiin edu
Abstract
We study the performance guarantees of exploration-fiee greedy algorithms for the linear contextual bandit problem. We introduce a novel condition, named the Local Anti-Concentio Concentration (LAC) condition, which enables a greedy bandit algorithm to achieve provable efficiency. We show that the LAC condition is satisfied by a broad class of distributions, including Gaussian, exponential, uniform, Cauchy, and Student's s / distributions, along with other exponential family distributions and their truncated variants. This significantly expands the class of distributions under which greedy algorithms can perform efficiently. Under our proposed LAC condition, we prove that the cumulative expected regret of the greedy algorithm for the linear contextual bandit is bounded by (poly log 2"). Our results establish the widest range of distributions known date that allow sublinear regret bound for greedy algorithms, further achieving a sharp loly-logarithmic regret.
Introduction
In the contextual multi-armed bandit problem 2 information in each round decide which arm to pull, receiving a reward corresponding to the pulled arm. The stochastic version of this problem observes rewards as random samples, with their expectation tied to the arm's contextual information. The agent's goal is design sequential arm-puliing strategy to maximize cumulative rewards, necessitating balance between exploration and exploitation. Linear contextual bandits, where expected reward modeled as linear function of contextual information, serve as the fundamental framework for contextual bandits [1] [T)] 26)..
6 24 25
an agent uses revealed contextual
Various exploration strategies, including upper confidence bound (UCB) [ Thompson sampling (TS) 3 and e-greedy [19] are widely used and studied in the theoretical analysis for linear contextual bandits. However, exploration can often be challenging practice, possibly leading to
over-exploration and performance deterioration. Some domains may find exploration infeasible or even unethical, and it may appear unfair in applications such as healthcare and clinical domains. Furthermore, exploration strategies tend to add complexity for algorithm designers and decision- making systems.
A greedy policy, i.e., pure exploitation without exploration, selects arms greedily based on current problem parameter estimates. While greedy policy's ' effectiveness cannot be guaranteed in general since it may fail to find optimality in the worst case, the possibility of its favorable performances in certain scenarios has been of interest both practically and theoretically. Therefore, understanding when greedy policy can perform effectively, i.e., when exploration is not needed, is a fundamental research question. Recently, a simple greedy policy has been proved achieve near-optimal regret bounds for linear contextual bandit problems under some stochastic conditions of contexts [8] 20 30 33 34).
Such efficient learning is possible if the greedy policy can benefit from suitable diversity the contexts (or the features of arms)
that even with exploration-free action selection, parameter estimation is
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

effectively possible. However, distributions known in the existing literature to allow efficient greedy algorithms are mostly limited only to Gaussian and uniform distributions 8 following research questions arise.
20
30 33 Hence, the
Is possible for a wider range of distributions allow efficient learning for greedy algorithms? If so, how can we characterize such distributions?
We answer the above questions affirmatively by proposing general distributional condition that allows for a broad range of distributions to achieve provable efficiency of greedy linear bandit algo- rithms. In this work, we present new Local Anti- cati-Concentration (LAC) condition for distributions that encompasses a wider range of context distributions compared to the previous findings. We demonstrate that the class of distributions that satisfy LAC, which denote as LAC class, include Gaussian, exponential, Cauchy, Student's t, and uniform distributions, as well as other exponential family distributions and their truncated variants. This study provides the first evidence that greedy algorithms can perform efficiently beyond Gaussian and uniform distributions. Our findings signifi- cantly expand the class of admissible distributions that are suitable for greedy algorithms for linear contextual bandits.
Our proposed LAC condition not only broadens the class of permissible distributions for greedy bandit algorithms but also facilitates a sharper regret guarantee, achieving a poly- voly-logarithmic (poly log T) regret for greedy algorithms. Our regret analysis constitutes a distinct improvement over the previously known results for greedy linear contextual bandit algorithms. The existing results are primarily categorized into two folds: (i) -iittiib-d contexts could only yield O regret for greedy algorithms for
linear contextual bandits (20] 30 [3]; (ii) Context diversity (e.g.. Assumption 3 in [8] alone was previously regarded as not sufficient to derive a poly-logarithmic regret but additionally assuming a margin condition (e.g., Assumption 2 in (8) can achieve (poly log T) regret In either case, there are limited prior results about context diversity beyond Gaussian and uniform distributions. As for the margin condition, to the best of our knowledge, no prior work in greedy contextual bandits has rigorously derived the scaling of the margin constant, rather than simply treating it as universal constant. To this end, we establish that Gaussian and uniform distributions as well as all of the common distributions that satisfy the LAC condition (see Table I induce (poly log T) regret without having to additionally assume a margin condition.
The key difference between the analysis of greedy algorithms and that of exploration based algorithms, such UCB and TS, for linear contextual bandits lies in the estimation bounds. While UCB (I] and TS analyses involve bounding the weighted estimation error of the parameter using self- normalized martingales, the analysis of greedy algorithms relies on the f2 estimation bound in all directions. Ensuring this estimation consistency is more challenging, especially when actions are chosen adaptively, resulting in non-i.i.d. data.
In this work, we prove that for broad class of context distributions, Vi-consistency of the estimator can be guaranteed, enabling poly-logarithmic regret for greedy algorithms. Our newly proposed class of context distributions represents the largest known class from which VE-consistency of the estimator can be derived, even with adaptively chosen (non-i.i.d.) contexts. To establish this consistency, we derive two key technical results. First, we show that the minimum eigenvalue of the Gram matrix increases sufficiently under the LAC condition. Additionally, we demonstrate that under this condition, the suboptimality gap can be bounded probabilistically- result derived from our analysis rather than assumed explicitly.
1.1 Contributions
The main contributions of our paper are summarized as follows:
We propose novel condition, called Local Anti- Concentratiiin (LAC) condition, for a greedy linear contextual bandit algorithm to achieve provable efficiency. The newly proposed
'It is important to note that the problem setting of Bastani et al. 8 (multiple parameters with shared context) differs from our setting, which involves single parameter with separate contexts, predominantly studied the linear contextual bandit literature | 20 50 33]. While Bastani et al. [8] demonstrated the diversity condition and the existence of a margin for Gaussian, uniform, and Gibbs distributions in the two-armed case within multi parameter settings, we show in Appendix K that the Gibbs distribution does not satisfy the diversity condition when extended to cases with more than two arms.

---

Table Comparisons of Greedy Linear Contextual Bandit Studies
Results
Paper
Context Distribution
Regret Bound
Problem Setting
Kannan et al. 20
Gaussian
((VT)
Single parameter
Sivakumar et al.
33
Gaussian
((VT)
Single parameter
Raghavan et al. 30
Gaussian
Ö(T3)f
Single parameter
Gaussian Uniform
Bastani et al. 8
Oppoly log T)
Multiple parameters
Gaussian
Uniform
Laplace
Truncated exponential
This work
Oppoly
Single parameter
Truncated Student's
Truncated Cauchy
PDF f о exp(-r) with
polynomially growing
The regret bound Raghavan al. 3D shown the Bayesian regret, which a weaker notion of regret than the frequennist regret that we consider in our work.
$
The problem setting of Bastani et al. g is mullti-arramter linear contextual bandit, where a context vector is shared across the arms, but each arm has separate parameter. Bastani et al. show that Gaussian and uniform distributions satisfy their covariate diversity condition (Assumption in (8) and margin condition.
the two-armed case (K' = 2), they also show that Gibbs distribution satisfies those conditions. However, we show in Appendix that Gibbs distribution fails to satisfy the conditions for the multi-armed cases with K 2 3.
LAC condition is satisfied by wide rage of common distributions, including Gaussian, exponential, Cauchy, Student's and uniform distributions, and many common distributions, well their truncated variants. This significantly expands the class of admissible distributions that are suitable for greedy algorithms and is, to our best knowledge, by far the largest class of distributions that induces efficient learning for greedy algorithms.
Under our proposed LAC condition, we prove that the cumulative expected regret for the greedy algorithm is bounded by (poly log T) (Theorem T. the sharpest known bound for greedy algorithms linear contextual bandits with a single parameter.
By leveraging the proposed condition, eigenvalue of the Gram matrix and (ii) a probabilistically bounded suboptimality gap. These two steps are key technical components for analyzing greedy bandit algorithms and were explicitly assumed in existing literature [8] to achieve poly-logarithmic regret. Notably, we do assume these steps; instead, we prove that distributions satisfying the LAC condition inherently induce these two technical results (Theorems 2 and 3 which may be of independent interest.
guarantee both (i) the growth of the minimum
Various context distributions have been empirically shown allow favorable performances of greey algorithms (see Appendix M). However, the distributions previously known in the literature that enable efficient greedy algorithms were primarily limited Gaussian and uniform distributions. Our theoretical results offer significant step toward bridging this gap between theory and practice, providing insights into why greedy algorithms can be effective under a wide range of distributions.
1.2 Related Work
Linear contextual bandits and generalized linear bandits have been widely studied [
6
Upper confidence bound (UCB) algorithms for the linear contextual bandit have been proposed and analyzed for their regret performance [ TO 11, 32]. Thompson sampling (35] algorithms for linear contextual bandits have also been widely studied, with results demonstrating
18
23
27 32

---

their effectiveness both theoretically and empirically 3 91 While UCB [ and Thompson sampling [ 4 analyses rely on bounding the weighted estimation error of the parameter using self-normalipe martingales, the analysis of greedy bandit algorithms depends on the l2 estimation bound in all directions. Ensuring this estimation consistency more challenging, especially in adaptive action settings where data are not i.i.d.
20 30 33 have shown that a greedy algorithm can achieve near-optimal regret performance for linear contextual bandit problems under stochastic contexts by providing sufficient conditions under which the greedy algorithm can be efficient. These conditions typically focus on the diversity of the context distribution, ensuring that the greedy policy benefits from sufficient context diversity for effective parameter estimation even without exploratory actions.
Recent studies 8
However, the existing literature has mainly limited itself to Gaussian g 20
30 33 and uniform g
distributions, leaving open questions about broader applicability. Specifically, it unclear if other distributions could also support efficient greedy algorithms and what fundamental characteristics these distributions should have enable consistent parameter estimation without exploration. Our work addresses this gap by identifying broader conditions under which diverse distributions can effectively support greedy algorithms linear contextual bandits.
2 Preliminaries
2.1 Notations
We use || to denote the E--norm of vector Rd. For positive definite matrix A idd we define ||^||_ = Vx Az. We use Amin(A) to denote the minimum eigenvalue of the positive definite matrix A. We denote D == [-R, Rj and B == {ar E R | S R}. If d is clear, we just write By := BR and D == DR- We define [n] for a set [n] =- .1, n). We write g for d-dimensional unit sphere. We set
........
| sup,21 {o P.III
supp21 {p / X for random variable X. If X is d-dimensional random vector, then we write || = (u, 11 || = supp|a|; (u, ll We use the notation O() S S to hide constants, and O() to hide constants and logarithmic terms. We use the notation a = b when a $ b and b S We use G, 02.00.... for absolute constant, which may differ from line by line.
2.2 Linear Contextual Bandits with Stochastic Contexts
We consider the linear contextual bandit problem with arms (K 2 2). where in each round
t = 1,2..... .T the set of context vectors X(t) (Xi(t) E Rd, E [K]] is drawn from some unknown distribution (t). Each arm's 's feature (1) E (1) for E [K] need not independent of each other and can possibly be correlated. The agent then pulls an arm a(l) [K]. Each context vector (t) for E [K] is associated with stochastic reward (t) E IR with mean (t) 6* where l* e Rd a fixed, unknown parameter. For simplicty, we assume |@*112 S 1. After pulling arm a(t), the agent receives a stochastic reward Ya(1) (t) bandit feedback: Ya(e) (1) = Xa(o (t)
Maat)) (t), where mean noise. We assume that there is increasing sequence of sigma fields (He) such that each na. (t) is H.-measurable with B/no, (t) [1 0. In our problem, H; is the sigma field generated by random variables of the arms chosen (a.1))...,a(f their context vectors (t)}. and the corresponding rewards
(t) R is
(Xa(1> (.,, Xa(t)) assumed to be conditionally o-sub-Gaussian, i.e., for all E R. A (+) H4-1] S exp(X2 20² 2 /2) for 2 0. Observing context vector (t). let (t) denote the optimal arm in round t, that is. a" (t) arg [ Xx(t)T6 f* Then the instantaneous expected regret (reg(t)) and cunulative expected regret (Reg(?? (T)) are defined respectively
(((e))))t). Also, Ma(t) (t) is
T'
Reg ()) = reg(1) = Σ E [Xa (a(
which are respectively the instantaneous and cumulative differences between the optimal expected reward and the expected reward of the pulled arms. The expectation is taken with respect to the stochasticity of history, containing randomness of contexts. The goal of the agent to minimize the cumulative expected regret.

---

In this section, introduce sufficient condition for efficient greedy contextual bandits. This condition is general and encompasses a wide range of common distributions, including Gaussian, exponential, uniform, Cauchy, and Student's distributions, as well as their truncated variants. To the best of our knowledge, this is the most extensive class of distributions considered in the greedy which has primarily focused on Gaussian, uniform 2.3 LinGreedy: Exploration-Free Algorithm for Linear Contextual Bandits
In this work, we focus on identifying sufficient conditions that enable exploration- greedy algorithms to efficiently learn the optimal policy. Specifically, we analyze greedy algorithm for linear contextual bandits, which we refer to as LinGreedy (Algorithm []. The LinGreedy algorithm selects arms greedily based on the OLS estimator, without any exploratory actions.
Algorithm LinGreedy: Greedy Linear Contextual Bandit
Initialize Σ() 0- Ia, 6(0) = 0, 0o E R4 for L [T] do while Amiu (E(( 1)) do
Choose ((t) arg m K (t(t) 6u and observe reward Ya(t)-
Update b(t) = b(t - 1) + Xa(t) (t))a(1) and [tt = E(t - 1) + Xa(e) (tte((t)
end while
Choose a(t) arg maxG[[]] (t) 0 and observe reward Y Ya(t)-
Update b(t) = b(1 - 1) + (1) and Σ() = E(( - 1) + X Xa(t) (1)
Update 02 E0))-)b(().
end for
Description of Algorithm 1 The algorithm performs greedy action in each round based on estimated rewards. In the initial rounds, when the Gram matrix Σ({) is not yet invertible, parameter estimation is deferred, and the algorithm selects actions based on an initial parameter 0g. Once the Gram matrix becomes invertible- algorithm computes an OLS estimator and performs greedy action based on the estimated parameter in each subsequent round. This algorithm is exploration-fiee In the following sections, we present novel and more general condition that enables efficient learning for greedy algorithms.
can be shown with high probability after sufficient time, the
3 Local Anti-Concentration Class
contextual bandit literature S 20 28 30 31 33
distributions, and their truncated variants.
Our proposed condition centers the rate of the log density of stochastic contexts, concept term Local Anti Concentration (LAC). We now formally introduce the novel LAC class.
Definition (Local anti-Concentration (LAC)) A density function fx of random variable X E R. is said to satisfy the Local Anti-Comcentration (LAC) condition with a non-decreasing polynomial L. if
Vog f'x (x) S (((1=)))))
for all R". We refer to L as the LAC function of X. We denote the class of distributions that satisfy this LAC condition as the Local Anti- Concentration class.
3.1 Intuition of LAC Condition
The LAC condition implies that a density is not overly concentrated at any given point, leading to gradual decay in density across all directions- the term local anti-concentration. A geometric interpretation of the LAC condition and a rigorous definition of this decay rate are provided in Appendix [D] Section 3.2 demonstrates that the LAC condition applies to broad range of common distributions. To the best of our knowledge, very few distributions have been previously shown to support efficient performance guarantees for greedy algorithms. However, we prove that the LAC condition holds for a wide range of distributions, including a variety of exponential families. Note that can be constant when contexts have bounded support (see Appendix C). the following sections, further explore the characteristics of the LAC condition.
5

---

3.2 Generality of LAC Condition
We show that the LAC condition is applicable various distributions, significantly expanding the class of admissible distributions for greedy linear contextual bandits. The LAC condition is satisfied when the exponential component in the exponential family has polynomial scale. Included in the LAC class are distributions such as Gaussian, exponential, uniform, Student's I, and Cauchy distributions, along with their truncated variants.
The following proposition demonstrates that the LAC function does not directly depend on the dimension of X. We further discuss in Appendix that the LAC condition is more closely related to the correlation structure of X rather than its dimensionality. Therefore, we suggest that the LAC condition provides suitable framework for comparing regret when both the number of arms and the dimension are large.
Proposition 1 Suppose the random variable X X2), where X1 E RT and X2 E R2 consists of two independent components. If X2 and X2 satisfy the LAC condition with functions (.).) and C-).), respectively, then X satisfies the LAC condition with [(x) max Ci (z), (z))))
This holds because, when we take the logarithm of the density, the independent coordinates decompose as the sum of each density. Upon taking the gradient and evaluating the fox norm, the expression decomposes perfectly. Using this proposition, the LAC condition remains robust across dimensions the coordinates are independent, making it dimension-free free in such cases. Furthermore, this condition very accessible because it can be readily computed for given density function. For many well-known exponential families, the exponential component of the density often scales polynomially.
Examples of Distributions with LAC Condition
We present a few examples of known distributions satisfying the LAC condition. We provide rigorous proof's for the examples in Appendix C
Gaussian distribution:
For a Gaussian random variable X = (Z....., ~ N (p. Σ), if
Σ is diagonal, it satisfics the LAC condition with L(x) Xmmi (E) (1|==11o |||||| For the
general (non-diagonal) case of Σ, see Appendix C
The exponential distribution's density fx(x) = exp( - Ax) satisfies the LAC condition with constant function L(x) A.
Exponential distribution:
The uniform distribution has constant density and satisfies the LAC condition with a constant function [xx) = 1.
Uniform distribution:
Student's i-distribution: The I-dimensional Student's t-distribution has density fx fx(x)
r(
-1+) )) (v+1)/2 and satisfies the LAC condition with L(x) for some
V/z
V dependent constant e2 > O.
Laplace distribution:
The Laplace distribution has density [*x) 25 exp( [ and
satisfies the LAC condition with L(x) c for some constant c 0.
If each coordinate's density independently adheres to one of the aforementioned distributions, according to Proposition] T they all share the same LAC function irrespective of the dimension.
Consider the density (z)) with f(x) cxp(-V(x:) for some differentiable function V(x). If (V(x) has polynomial growth, i.e., is bounded by a polynomial, then the density fzx meets the
LAC condition. This holds because f(z) C exp(-V(()) log fxx) V log exp(-V(x))
- (v).. If (x exhibits polynomial-scale growth, then the supremum norm confirms that the
LAC condition satisfied.
This observation makes the LAC condition easily verifiable for exponential family distributions with density forms fx (z|0) h(z) exp|n)(0)- -(()) - A(0)). where the exponential part T(z) has polynomial growth. In many exponential family cases, T(-) indeed exhibits polynomial growth. Proofs and further details can be found in Appendix C
4 Statistical Challenges of Greedy Linear Contextual Bandits
In this section, we outline the key statistical challenges analyzing greedy algorithms for linear contextual bandits: (i) ensuring the diversity of the adapted Gram matrix (Section and (ii)

---

bounding the suboptimality gap to achieve logarithmic regret (Section 4.2). For ease of exposition, we use the vectorized context expression X(t) (x, (t).... .............. X (t)) R of (t). which combines context vectors (1))) for i E [K]. We define (() the j-th coordinate of the context (1))).
4.1 Diversity of Adapted Gram Matrix
The first key challenge lies in ensuring sufficient fz-concentration of the estimator. This requires sufficient eigenvalue growth of the Gram matrix, constructed from the policy-selected contexts. For the OLS estimator used in Algorithm I if the minimum eigenvalue of the adapted Gram matrix Amin (2(()) increases linearly with the number of rounds t, we can obtain the high probability l error bound [|0, 0* 2| with a convergence rate of O(1/Vl) using martingale concentration [3 29
In fact, the growth of Amia (t) is necessary condition to obtain Vł-consistency of the estimator.
However, estimating the covariance of the selected contexts Xx(t) (t) is relatively challenging, as its distribution differs significantly from the overall distribution (before selection) of ( Some studies have investigated the statistical properties of selected contexts (20, 28;; however, the known results are limited to specific distributions, such as arm-independent Gaussian and uniform distributions. Therefore, it remains an open question whether the growth of Amin (E)) can ensured for broader class of distributions and what characteristics such distributions would need to satisfy.
4.2 Bounding Suboptimality Gap: Road to Logarithmic Regret
The next challenge that we face particularly in order to achieve logarithmic regret is to bound the suboptimality gap. We first denote the suboptimality gap as the difference between the optimal expected reward and the second highest expected reward:
(() = Xax (t)
max Xx(t)
(Fe
which is determined by the true parameter 0- We aim to bound this suboptimality gap probabilisti-
cally, as described precisely in Challenge of Section 4.3
When this challenge is resolved, along with the growth of the minimum eigenvalue of the adapted Gram matrix discussed in Section 4.1] we can achieve logarithmic expected regret using analysis techniques for lincar contextual bandit with stochastic contexts 7 [9]. A high-level description of the role of the margin constant the regret bound is provided in Appendix D.I with a rigorous analysis in Appendix
4.3 Formal Statements of Two Key Challenges
As mentioned above, we encounter two primary challenges: ensuring the diversity of the chosen contexts (i.e., the growth of the minimum eigenvalue of the Gram matrix of the selected contexts) and bounding the suboptimality gap. Importantly, we do not assume these conditions to hold priori; rather, we will demonstrate that they are satisfied the stochastic context under the LAC condition. In this section, we formally define these challenges be addressed.
Before delving into the formal statements for each of the two challenges, we first define the concept of the diversity constant, which depends on the minimum eigenvalue of the adapted Gram matrix.
Definition (Diversity Constant) For a linear contextual bandit with contexts X(t) and history H4-1, the diversity constant X, (t) is defined as the value satisfying
E (t)
(H-11 >
(t)
for all t > O, where a(t) denotes the arm selected by the algorithm in round t.
Then, the first challenge is ensure positive diversity constant A. 0, which involves sufficient eigenvalue growth of the adapted Gram matrix. We explore this further in Appendix E.
Challenge 1 (Positive Diversity Constant) Our goal is to ensure X, (t) 0.
7

---

Achieving a positive diversity constant is challenging, as it requires analyzing the behavior of context selected by the greedy policy specific direction rather than relying on the overall context distribution. In Section 5.3.1 we demonstrate that the minimum eigenvalue of the Gram matrix grows sufficiently, thereby ensuring positive diversity constant.
We now formally state our second challenge of bounding the suboptimality gap.
Challenge 2 (Probabilistic Suboptimality Gap) We aim to bound the constant Ca which holds under the given history H4-1 and for any > 0,
1
TP (A(((()) se] S (cCa(t)+
VT
We also refer to this constant Ca (t) as the margin constant.
Note that Eq. 2 is a relaxed version of the margin condition presented in g 19]. The aforementioned literature explicitly assumes this condition hold. However, we instead show that the suboptimality gap can be bounded without directly assuming it (Section 5.3.2). Rigorously, Ca depends on T, as it is function T'. However, emphasize that our algorithm does not require prior knowledge of T;; this dependency needed only for the analysis.
Regret Analysis
We present the main results of our paper. We prove that the regret of the greedy algorithm (Algo- rithm I for linear contextual bandits can be bounded a logarithmic scale in the time horizon T, provided that the context distribution satisfies the LAC condition with a polynomial function L.
Assumption (Independently distributed contexts) The context sets X(I), (T)) are inde- pendently distributed across time.
Discussion of Assumption To the best of our knowledge, all analyses of greedy linear contextual bandits assume the independence and identical distribution (i.i.d)) of context sets [8] 20 28 333. J In
Assumption[] [] we only require context sets to be independent; they may be non-identically distributed. Additionally, much of the literature on linear contextual bandits that investigates Vt-consistency of estimators also assumes independence of context sets (21 Note that under Assumption context vectors within the same round are permitted to be dependent.
5.1
Considerations for Context Boundedness
We first provide detailed considerations context boundedness. In the linear contextual bandit setting, f2 boundedness is commonly assumed. However, for light-tailed distributions (such as Gaussian or exponential), the l norm is unbounded. In such cases, general approach in the statistical literature is to assume bounded t or t2 norms [14] 17 37 38 Therefore, we divide our analysis into cases of bounded and unbounded contexts.
Bounded Contexts vs. Unbounded Contexts. In linear contextual bandit studies, boundedness of the & norm of contexts is commonly assumed. In this paper, for bounded contexts, consider both truncated contexts (e.g.. truncated Gaussian, truncated Cauchy distributions) and naturally bounded contexts (e.g., uniform distribution). For unbounded contexts, assume bounded t/1 norm, which a standard assumption for handling light-tailed distributions (e.g., as in 14, which assume bounded 1/2 norms).
Assumption (Boundedness) For unbounded contexts, we assume (t)()) S Fmax- For bounded contexts, assume [t)ll) S. Tmax for all [K], E [T].
The bounded context assumption is widely used in the literature [ 21 22 28 For unbounded contexts, our assumption of t/ boundedness is notably weaker than the sub- Sobb-Gausiiatty (or (hz) assumption commonly used in statistical regression literature to handle random design covariates [44 (9] If & boundedness holds, it automatically implies boundedness of the 1i norm. However, as the analysis differs slightly depending on whether the support restricted to bounded ball or is unbounded, address these cases separately.
Discussion of Assumption

---

5.2 Regret Bound of LinGreedy for LAC Distribution
We first introduce our main result, the regret bound of the greedy algorithm under the LAC condition.
Theorem (Regret bound of LinGreedy) Suppose ((t) satisfies the LAC condition with the poly- nomial function C and also satisfiex Assumptions I and for all Then, the cumulative expected
regret of LinGreedy (Algorithm) 7 is bounded by
Reg(T") S Oppoly log
where O concerns only the dependency on T. Considering the dependency on d and for unbounded contexts, have
Reg(T) S {O(225)
For bounded contexts, refer to Appendix H for explicit results, as we consider several cases.
Discussion of Theorem 1 Theorem I states that if the contexts are drawn from a distribution in the LAC class, the regret scales as (poly T"). While our primary objective is not solely to achieve the sharpest regret bounds, attaining
regret is highly favorable. Our main goal is to demonstrate that large class of context distributions satisfies the LAC condition. When they do, simple greedy algorithm can suffice or even outperform exploration-
algorithms (see numerical experiments in Section(6). The worst-case dependence on and K for bounded contexts is detailed Appendix [H] where dependencies remain at most polynomial and As these dependencies vary across distributions, refer to Appendix for precise information. Proofs for unbounded contexts are provided in Appendix G. with proof sketch Appendix Proofs for bounded contexts are included in Appendix! !
Theorem M the first result expand the class of admissible distributions for greedy bandit algo- rithms beyond Gaussian and uniform distributions. Our result demonstrates, for the first time, that distributions the LAC class inherently exhibit margin behavior, achieving sharp poly-logarithmic regret without requiring an additional margin assumption. This finding is of independent interest beyond the analysis of greedy bandit algorithms.
5.3
Proof Sketch of Theorem I
We first present our key results for addressing each of Challenges I [and] 2 ssttted in Section 4.3
5.3.1 Ensuring the Positive Diversity Constant
In this section, we present our key result for estimating lower bounds on the diversity constant for densities that satisfy the LAC condition, therefore addressing [Chlllenee I] Theorem 2 the analysis under the case of unbounded contexts, where contexts have full support. A similar result presented in Appendix H for contexts with bounded or truncated support.
Theorem (Diversity constant for unbounded contexts) unboundde contexts X(t) has the LAC condition with ((x) == A₁ + Aza and satisfies Assumption 2 for all t,
X1 2 2 (AI A2(R + 2)
holds for R1 = C2x (log d + log K + 2). Here, C1, 02 are absolute constants.
Discussion of Theorem Theorem 2 implies that A. (t) 9()). hence ensuring the growth of the minimum eigenvalue of the adapted Gram matrix. In Appendix D.1 discuss how 1 the regret bounds. Note that generally small in many distribttions. For example, for Gaussian distributions, a = 1, and for exponential distributions, a = 0.
(,) factors into
5.3.2 Bounding Suboptimality Gap
Next, we present our result addressing Challenge 2 by computing the suboptimality gap constant Cl()), which satisfies the inequality in Eq. for every > O. By combining this condition with the estimates for X_ (!), we can obtain an O (po T)) regret bound terms of T by applying the
analysis techniques of linear contextual bandits with stochastic contexts 7 g [9 our setting.

---

Theorem (Suboptimality gap for unbounded contexts) In the same setup as Theorem
C2(t)
Ca(t) S ScVida + A23" R2)
10-12
holds for Rg mC (1 + log K + log + 1 log T) + and absolute constants C3, Cq > 0.
Discussion of Theorem Note that the suboptimality gap constant Ca is multiplied linearly in regret bounds 5 For bounded contexts, we present a similar result in the Appendix H
5.3.3 Proof Intuitions
We provide a high-level proof overview of Theorem in Appendix [
Note that once Challenges and 2 are satisfied, achieving logarithmic regret becomes straightforward, as detailed in Appendix
The remaining task to address these challenges, with particular focus on bounding the constants X. (1) and Ca (t). A key implication of the LAC condition is that the density decays slowly every point. Another useful property that the LAC condition preserved under conditioning. meaning that ((() (t) E A} also satisfies the LAC condition with the same function for any set C R&xd This can be verified using the fact that log where P[[] is a constant (see Appendix
(x) = log (x(1) (x) log [[A],
C.3 for details).
The main challenge of analyzing the statistical concentration in greedy linear contextual bandits lies in the fact that the distribution of selected contexts Xa()) (t) differs significantly from the distribution of the overall (pre-selected) contexts (t). The preservation of LAC under conditioning ensures that LAC still holds when conditioning on the event of selecting arm i, enabling our analysis.
The full proofs for unbounded contexts provided in Appendix + see Appendix H (and their proofs in Appendix [].
For results bounded contexts,
5.4 VCCoonsisty of Estimator
In addition achieving logarithmic regret, independently valuable result is obtained: the f-- consistency of the estimator 0, This is a property that even typical sublinear-regret algorithms. such as UCB and TS, do not generally guarantee. Under the same setup as Theorem we achieve with high probability (see Corollaries 6 and 7). This additional result may also facilitate analysis of sample complexity, such as PAC bounds.
||d: 0" 12 < δ
6 Experiments
To validate our theoretical findings numerically, we conducted experiments using various context distributions: Gaussian, Laplace, uniform, and truncated Cauchy distributions. We compared the performance of LinGreedy with the LinUCB and LinTSS algorithms. The results showed that LinGreedy exhibited significantly superior regret performance compared the other exploration- based algorithms, achieving logarithmic scale of regret. Detailed experimental results provided in Appendix M
d=20, 20 Uniform
K=100, Laplace
d-20., K=20, Truncaled Cauchy
402
303
300
LinGrescy
253
150
303
Cumulative
202
Cumutaaive
200
Cumutative
353
232
302
300
202
52
203
400
820
1020
200
400
820
1000
200
400
620
1200
Round (1)
Round
(9)
Rounn
(1)
Figure 1: The cumulative regret plots of the numerical experiments. The full results are available in Appendix M
10

---

Acknowledgements
This work was supported by the National Research Foundation of Korea(NRRF grant funded by the Korea MoVernmen((MSIT) (No. 3022RICICI00685) 2022R1A42 14450035579, and RS- RS-2023-000222633 and by AI-Bio Research Grant through Scoul National University. The authors thank H. Choi for helpful discussions.
References
[1] Abbasi-Yadkand Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
[2] Abe, N. and Long, P. M. (1999). Associative reinforcement learning using linear probabilistic concepts. In International Conference on Machine Learning, pages 3-11.
[3] Abeille, M. and Lazaric, A. (2017). Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR.
[4] Agrawal, and Goyal, N. (2013). Thompson sampling for contextual bandits with linear payoff's In International conference on machine learning, pages 127-135. PMLR.
[5] Ariu, K., Abe, K., and Proutière, A. (2022). Thresholded lasso bandit. In International Conference Machine Learning, pages 878 778-992..77 PMLR.
[6] Auer, P. (2002). Using confidence bounds for exploitation-exploaaiie trade-offs. Journal of Machine Learning Research, 3NNov):397-422
[7] Bastani, H. and Bayati, M. (2020). Online decision making with high-dimensional covariates. Operations Research, 68( 68(1)277.
[8] Bastani, H., Bayati, M., and Khosravi, K. (2021). Mostly exploration-free algorithms for contextual bandits. Management Science, 6323)1132-
[9] Chapelle, O. and Li, L. (2011). An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249-2257.
[10] Chu, W., Li, L., Reyzin, L., and Schapire, R. E. (2011). Contextual bandits with linear payoff functions. Journal of Muchine Learning Research.
[11] Dani, V., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. In Proceedings of the 2 st Annual Conference on Learning Theory, page 355-366.
[12] De Haan, L., Ferreira, A., and Ferreira, A. (2006). Extreme value theory: an introduction, volume 21. Springer.
[13] de la Pena, V. H., Klass, M. J., and Leung Lai, T. (2004). Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws.
[14] DUAN, Y. and WANG, K. (2023). Adaptive and robust multi-task learning. The Annals of Statistics, 5115)2005--
[15] Durrett, R. (2019). Probability: theory and examples, volume 49. Cambridge university press. [16] Evans, L. C. (2022). Partial differential equations, volume 19. American Mathematical Society, [17] J.n, Wang, D., Wang, K., and Zhu, Z.. (2019). Distributed estimation of principal eigenspaces. Annals of statistics, 47(6):3009.
[18) Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010). Parametric bandits: The generalized linear case. In Advances Neural Information Processing Systems, pages 586-594.
[19] Goldenshluger, A. and Zeevi, A. (2013). A linear response bandit problem. Stochastic Systems, 3 3(1:2300-261
[20] Kannan, S., Morgenstern, J. H., Roth, A., Waggoner, B., and Wu, 7. S. (2018). smoothed analysis of the greedy algorithm for the linear contextual bandit problem. Advances in neural information processing systems, 31.
[21] Kim, G.-S. and Paik, M. C. (2019). Doubly-robust lasso bandit. In Advances in Neural Information Processing Systems, pages 5869-5879.
[22] Kim, W., Kim, G.-s., and Paik, M. C. (2021). Doubly robust thompson sampling for linear payoffss In Advances in neural information processing systems.

---

[23] Kveton, B., Zaheer, M., Szepesvari, C., Li, L.. Ghavamzadeh, M., and Boutilier, C. (2020). Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 2076.
[24] Langford, J. and Zhang, T. (2007). The spoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96-1.
[25] Lattimore, T. and Szepesvári, C. (2019). Bandit Algorithms. Cambridge University Press (preprint).
[26] Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010). contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670. ACM.
[27] Li, L.,, Lu, Y., and Zhou, D. (2017). Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080.
[28] Oh, M.-H., Iyengar, G., and Zeevi, A. (2021).
lasso bandit. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference Machine Learning, volume 139 Proceedings of Machine Learning Research, pages 8271-8280. PMLR.
[29] Peña, H., Lai, T. I.., and Shao, Q.-M. (2009). Self-normalized processes: Limit theory and Statistical Applications. Springer.
[30] Raghavan, M., Slivkins, A., Vaughan, J. W., and Wu, Z. S. (2023). Greedy algorithm almost dominates in smoothed contextual bandits. SIAM Journal on Computing. 52(2):487-524.
[31] Raghavan, M., Slivkins, A., Wortman, J. V., and Wu, Z. S. (2018). The externalities of exploration and how data diversity helps exploitation. In Conference on Learning Theory, pages 1724-1738. PMLR.
[32] Rusmevichientong, P. and Tsitsiklis, J. N. (2010). Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411
[33] Sivakumar, V.. Wu, S., and Banerjee, (2020). Structured linear contextual bandits: sharp and geometric smoothed analysis. In International Conference on Machine Learning, pages 9026-9035. PMLR.
[34] Sivakumar, V., Zuo, S., and Banerjee, A. (2022). Smoothed adversarial linear contextual bandits with knapsacks. In International Conference on Machine Learning, pages 20253-20277 PMLR.
[35] Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):255-294.
[36] Tropp, J. A. (2011). User-friendly tail bounds for matrix martingales. Technical report, CALIFORNIA INST OF TECH PASADENA.
[37] Vershynin, R. (2018), 8). High-dimensional probability: An introduction with applications in data
science, volume 47. Cambridge university press.
[38] Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press
[39] Wang, K. (2023). Pseudo-labeling for kernel ridge regression under covariate shift. arXiv preprint arXiv:2302. 10160.
12

---

Appendix
Contents
1
Introduction
1.1
Contributions
Related Work
2
Preliminaries
Notations
2.2
Linear Contextual Bandits with Stochastic Contexts
2.3
LinGreedy: Exploration-Free Algorithm for Linear Contextual Bandits
3
I Local Anti-Concentration Class
Intuition of LAC Condition
3.2
Generality of LAC Condition
Statistical Challenges of Greedy Linear Contextual Bandits
Diversity of Adapted Gram Matrix
Bounding Suboptimality Gap: Road to Logarithmic Regret
4.3
Formal Statements of Two Key Challenges
5
Regret Analysis
Considerations for Context Boundedness)
5.2
Regret Bound of LinGreedy for LAC Distribution
5.3
Proof Sketch of Theorem
5.3.1
Ensuring the Positive Diversity Constant
5.3.2
Bounding Suboptimality Gap
5,3.3
Proof Intuitions
10
5.4
Vi-Consistency Estimator
10
6
Experiments
10
Additional Notations
16
8*
Dependency of Suboptimality Gap
16
More Details of LAC: Distributions, Conditioning, Truncation
16
LAC of Various Distributions
16
Proof of Proposition]
17
LAC and Conditioning
18
LAC and Truncation
18
LAC and Decay Rate of Density
19
13

---

D
High-Level Proof of Theorem (Unbounded Contexts)
21
D.I
Regret Analysis: Overcoming Two Challenges
21
D.2
Tackling Two Challenges and Fixed History Arguments
22
D.3
Starting with Truncation
23
D.4
Event Decompositions
23
D.5
Conditional Contexts are Still in LAC Class
24
D.6
Remaining Goal: Bounding Decay Rate of Projected Contexts
24
Sections, Section Densities and Decay Rate
25
Motivation
25
Sections and Section Densities
26
Decay Rate of Section Density
27
F
Two Key Propositions in Fixed Histories (Unbounded Contexts)
28
Details for Diversity Constant (Challenge
28
F22
The Setup of Fixed History Analysis
29
Key Proposition for Diversity Constant
29
F33.1
Proof of Proposition
30
F.4
Key Proposition for Suboptimality Gap
32
F4.1 Proof of Proposition
Proofs of Results for Unbounded Contexts
34
G.I
Constructing Truncation Sets
34
G.2
Proof of Theorem 2
................................
36
G.2.1
Constructing Truncation Sets
36
G.2.2
Properties of Truncated Contexts W
37
G.2.3
Applying Proposition 2
38
G.3
Proof of Theorem
38
G.3.1
Constructing Truncation Sets
38
G.3.2
Truncation with a High-Probabbiliyy Region
39
G.3.3
Applying Proposition
39
G.4
Proof of Theoreml 1| Unbounded Contexts Case
39
H
Results for Bounded Contexts
40
Two Cases of Bounded Contexts
40
H.2 Regret Bounds for Bounded Contexts
40
3 Concentration Parameters for Bounded Contexts
Results for Two Challenges: Bounded Contexts
43
Proofs of Results for Bounded Contexts
44
Fixed History Arguments
44
14

---

I2
Sections of the Ball
44
L33
Linear Section Maps
45
One-side Decay Rate of Linear Section Maps
46
1.S
Linear Section Maps between Sliced Balls. UR
47
1.6
Linear Section Maps for Double Sliced Balls, Sp (, 6,
48
L.6.1
Case 1 A.
48
1.6.2
Case To S
1.00
49
1.6.3
Case 0 S (u,
49
1.7
Proof of Proposition
50
L8
Proof of Proposition
1.9
Proof of Proposition
51
1.10
Proof of Proposition
52
Proof of Corollary
52
1.12
Proof of Corollary
52
I.13
Proof of Corollary
53
J
Analysis After Challenges anddd 2 are Satisfied
53
J.1
Proof of Proposition
53
J.2
Concentration of Sub Sub-exponential Contexts
................................
55
J.3
Proof of Proposition
................................
55
L3.1
Gram Matrix Concentration
55
13.2
Good Events
56
J.3.3
Bounding Regret by the Peeling Technique
57
K
Discussion on Diserete-Supported Contexts
59
Dicussions, Limitations and Further Ideas
59
M Numerical Experiments
59
Technical Lemmas
61
Concentration Inequalities
15

---

A
Additional Notations
We define additional notation. For e E R define
P. {xr x T - 0}.
For S C R", define
| := sup 120/o00 a E S}.
For the intervals I C R and E Rd, define
Ig = fo VE
1}. We define TV (-) the projection onto the subspace V. Also, in the appendix, we write B = B {a E Rd ||||| I RJ with slight abuse of notation. For a random variable X, we define (Xp) as the support of X. Recall that we define the expected regret in round reg(t) and the unexpected regret as reg' (t), Also, for & Uier Eg with disjoint events Es, we use the following notation
For instance, 1= (
E [
Bi]l
PLE,EI E.].
For an event A, we define P(X; A] and E[X; A] as P[x n A] and X n A), respectively, following Durrett [15] notation.
B 10 Dependency of Suboptimality Gap
Throughout the proof, first bound the margin constant C's by assuming | 1. If we obtain CA for ||0112 = 1, then in the general case where | ||2 = K, observe that
X (nn
X,(1)
(t) max (t) (f0
To T
=
max (f0
(3)
R
K
Cs
1
+
K VT
holds. Therefore, from now on, we assume ||0* ditionally, we highlight that we only need to bound CA for < 1 since for = > 1 it holds that CA
1| and adjust for the general case later. Ad-
2,
C More Details of LAC: Distributions, Conditioning, Truncation
In this section, we provide the omitted details of LAC and its properties.
C.1 LAC of Various Distributions
We first provide more details on the LAC of various distributions, as presented Section 3.2
LAC of Gaussian contexts. For density f(x) CCeepp (-(x 4) VV n)), E R", where V Eー
Vog f = TV (x - 1)). First, when V is diagonal, after taking the log and gradient, we get
| log [x)]l S 2A (V) plllo S 2dmax (V) (||r + [1
Since V = 2 1 we obtain the desired results. For general V, we can see that
log f( s $2 [ || mlloo:
where V is the i-th row of V.
16

---

LAC of bounded support contexts. If the support of the contexts is bounded within compact set, v log.f f is bounded provided is continuous. Therefore, in this case, LAC can be constant function. Additionally, if ||0||2 I R, we have
V f(x)lll & ((R)
by the monotonicity of L(-).
LAC and context correlations. We claim that the LAC function L()) of a random vector x = (Zi ,x) is related the correlation structure of 24, Ty rather than the dimension itself. Consider f(x) o exp(-V(xr) Then,
V log f(x) = - (x)
and
0, log f(x) = (v)
hold. Since L is defined in the sense of the supremum norm, to investigate the LAC function, the maximum value max; |8, (==))loo is important. We claim that it is dimension-free property, and the correlation structure is more important than the dimension itself. For instance, if x (.1...., Fn)
coordinate-ve independent, we have (xx (1()z) + (2(22) +... (x,). Hence,
[V)x)) max (x:))
and we can see it is dimension-free value.
LAC with shifted mean distribution. Let the mean-zero contexts have density f(x) with LAC function L(.). Then, the shifted contexts with mean y have density g(x) f(x + 1). and we observe that
V log ((x))l> V log//e [(x + p)llxo
- L (||xr + mol
2 [1|=||<< + ||]l|=0)
Hence, the density ((x) has LAC with function L'(x) L(x + [|Ho and when || = O()) has the same rate. Thus, LAC does not require contexts be mean-zero and can be defined for distributions with general mean.
C.2 Proof of Proposition
I
X and X1, X2 are independent, the density fx of X can be decomposed as fx((21,22)) fx
Then,
Voog fx (egff((11, x2)) = V(log (x1) log fx, (x2)) = (Vz, log (I1), Va, log fx, (x2))
holds, and taking the supremum norm, we get
V log fx
max V|, log Jx, (1)))>>>))) || Vag log Sx, (222)1
< max
(2(1=2)loo)
< (Ix( Le (
where the third inequality holds by the monotonicity of Z(.). By the definition of the LAC function, finally obtain the desired result: / has LAC with the function L(x) max(Ci (I), La(x)) for g E R.
17

---

C.3 LAC and Conditioning
First, we observe that the LAC condition is preserved under conditioning.
Let the density of X (XI ,..k) E Rd be f(-). For the event
X A} where A Ra the conditional density of X given E is formulated
as fxx())
f(x)
E IRd for x E RaKk
P
Then, the following holds:
v log (x) = V log f(x) - VIP = V log f(x).
This means X E also satisfies the LAC condition with the same function, hence LAC is robust under conditioning.
Especially, if the event E has the form E = (X; D and X, = xz for j # i} for some D C Rd
we define the density of X; E as
f( I1- 21+1 TK)
f(,(())
for x E Rd.
P[E]
Then,
v log fx) = v log f (z),... 21-1, 2,41: xx) VP(E)
log f (#1,..., I,-1, I1+1..... FK)
holds. We have
log (x) S C (I( 24-1, 2, Ti+l. KK oloo
which indicates that the conditional density also satisfies the LAC property with L(-).
We summarize the above observations in the following lemma, noting that C(.) is non non-decreasing function.
Lemma (LAC of conditional contexts) For random vector X = -XT -XI E BdK let its density satisfy the LAC condition with function L(.). Then, for any event E (X A} where C TRoK and || A| R, the conditional random vector X F, satisfies the LAC condition with the constant function L(R). Specifically, if E has the form E. = (X: E D and X, =I for # i} for some D C Ra with || D1 S R, then the conditional random vector X; E satisfies the LAC condition with L(R).
C.4 LAC and Truncation
We introduce the property that can compute the LAC of truncated contexts. Truncating the contexts (t) to d-dimensional ball Bn IRd for every i [K] still satisfies the LAC condition with constant function, L(R).
Lemma (LAC with truncation) Suppose the density of contexts E RdK satisfies the LAC condition with the function L(.). Consider the case truncate X into the region (Bx)* K and define truncated contexts as X. Then, X satisfies the LAC condition with constant function L(R).
Proof The density of truncated contexts is calculated as
fx(x)
(x (x)
[P [
Then, when taking the log and gradient, we get
V log (x(x)= = V log (x).
Since ||x|| < for x E (BB)), and L is defined by a non-decreasing function, we get
log (x())= s C(R).
18

---

C.5 LAC and Decay Rate of Density
Next, we rigorously define the decay rate density.
Definition 3 (Decay rate) For a density f(x), IRd, and for set A C R., we say it has decay rate M > 0 if
f(x1) (112)
2 exp(-Mizz x2l) -22))
for all 21,22 E A.
We next present lemma that states a density with bounded LAC function C has bounded decay rate in every direction. This property is especially useful throughout the paper.
Lemma 3 (Decay rate and LAC) Suppose density is defined domain D C R.d. and satisfies the LAC condition with constant function L. Then, the decay rate of f in D is bounded by vdC.
Proof By using the Cauchy-Schward inequality, we can bound the directional derivative for any E Sd-1 as
0xf(x) f(x)
Vf(x))
v
f(x)
Vf(x)
< ||u1/2
f(x)
V fx)
f(x)
V fz)
/ Vdl
1000
f(x)
I vdc.
Next, by applying the Gronwall inequality (Lemma we obtain
f(x + hv)
exp(-Vdch)
f())
for any x, + hv E D. Since and are arbitrary, we achieve the desired result.
For univariate function, we define one-sided decay rate, which is weaker condition than the standard decay rate.
g. function say it has one-sided decay Definition 4 (One-sided decay rate) For univariate function rate M on set for all y, of e with y < <
g(v))
exp(-MM(') (M g(v)
Using these observations, we rate of the density. For example, in the one-dimensional case, a density with fx) x exp(-Mx) has decay rate M. We can then bound the lower bound of the variance as n and the maximum density bounded by M. Since Challenge is related to the variance lower bound and Challenge 2 is related to the maximum density (of the suboptimality gap), we aim to investigate the decay rate of the contexts' density.
that the LAC condition provides an upper bound on the decay
We first present our key lemma, which provides a relationship between the one-sided decay rate and the variance lower bound. the following parts, we present the rigorous relationships between LAC. (one-sided) decay rate, variance lower bound, and maximum density.
19

---

Lemma 4 (One-sided decay rate and variance lower bound) Consider the density g(-) of ran- dom variable R with support I [a.8 where >> M for some M >> Suppose g satisfies
g(v/)
exp( exp(-MMy v
gly)
for all v.v Eenl- Mr. #1 with < y' Then, we have
E 1
M
for some absolute constant
Proof Using Lemma we find that the density is bounded by 3M in the interval By applying Lemma we obtain the desired result.
[- 2M 2n7
T..
Next, we present another key lemma that provides relationship between the one-sided decay rate and the maximum density.
Lemma (One-sided decay rate leads maximum density) Suppose a real-valued random vari- able Y has density g and for yo E IR, [yo, yo 2Ml C supp(Y) for some M >> O. If satisfies
g(yo + h) 2 exp(-Mh)
(
for any 0 S h < 2M then g(ya) S 3M.
Proof Since the integral of the density is 1, we have
sv)dd
(Esupp(g)
Nut 257
9(v) dy
(36) )
g(3n)
y0
Not vht
2 g(yo)
exp(-Me yo))dy
ya
((0o)
M exp( exp(ex((p -M - -b0))
M 1eexp -xep (-11) 1
((16)
2
2 ((0))
3M
Therefore,
g(v0) S 3M.
Lemma (Maximum density leads to variance lower bound) Let be a univariate random vari- able with support A = supp(Y)). For an interval I bounded by M, then we have
3M 3M if the density of Y in O A is
B
1/2
If I n A = 0. above inequality still holds.
20

---

Proof First, since the density is bounded by M,
2
2
P|Y An
x M
3M
3
Therefore, with probability greater than
3 YE
AYEAnnH {|
1
Thus,
3M
2
1
E E|
3
3M
27M
If / 0 A = means that | 2 3M
almost surely, hence we get the wanted result.
D High-Level Proof of Theorem 1 (Unbounded Contexts)
In this section, we briefly outline the high-level proof of Theorem foor unbounded contexts, This overview provides summary and high-level sketch of the proofs, with full details presented in Appendices and
We begin by explaining how overcoming the two primary challenges (discussed in Section 4 leads to logarithmic regret bound in the proof of Theorem [ Next, we provide sketch of the proofs for the two key theorems: Theorem 2 for lower-bounding the diversity constant and Theorem for upper-bounding the suboptimality gap.
For bounded contexts, the result statements are given in Appendix H and the full proofs are in Appendix[] Since the proof for bounded contexts follows similar approach that of unbounded contexts, we start with a proof sketch for the unbounded case.
D.1 Regret Analysis: Overcoming Two Challenges
In this section, we briefly present our proof sketch for the regret bounds. We describe how we can achieve logarithmic regret by addressing the two challenges: Challenges T [add
Addressing Challenge we can obtain the O rate & bound of the parameter O, and 0* by
using the combination of self-normalized concentration [ and properties that Σ, ž _ holds with high probability (by using Corollary 9.. The details are in Appendix | Hence, by tackling Challenge ||0, 0- S L'dlog holds with high probability. The following part describes how Vx.t
can acheev logarithmic regret by addressing Challenge 2 First, simply assume the contexts are bounded, such as [|Xx(t)ll2 S Tmax- Later, in our main proof, we also modify it to the relaxed condition (t)ll S Fmaxx
Challenge 1: Vt-rate l2 concentration. Ensuring the first Challenge can lead the E statistical resolution of the estimator. Hence, we can get
Volgg
(xT))) (0.-1 - 0¹)l & cæ
Vx. (1 1)
vdlog
IXT a' (0.-1 - cæmax VA. x (t-1)
holds with high probability. Details are in Appendix [.]
However, this resolution is insufficient for logarithmic regret; it can only achieve O(VT) regret bound.
Challenge 2: Towards logarithmic regret. Furthermore, addressing Challenge 2 (margin condi- tion), we can obtain a logarithmic expected regret upper bound. When the greedy policy selects a(f). it means that
Xa(t) (t) 10 2 XT 0
21

---

and by the definition of the optimal arm,
(1( 00 S x (1)
holds. Ensuring Challenge 1 we get reg' (t) (t) Xt(t) 22x
v vdlog' T
Vd. (t-1)
Next, define the event E as the event where reg'(t) (t) > 0. Under the event E, the suboptimality gap of (() satisfies
Vdlog
AX X²-
max jza
X 0 2CTmax
Vxa (1-1)
and by overcoming Challenge
we get
v vdlog?
1
Pxeg|reg's (t) > 0] S Cs x 2ax
Vx+ (t 1) VT
VllogT
S 3cx Cs
Vd. x (1-1)
By combining these results, we can bound the expected regret as
VdlogT
dllog
[x(t)(reg S 3ax Co
X 2CT
VA, (t-
Vd, x (t-1)
dlogg T
= x max
Cs
A. x 1)
This observation enables us to achieve logarithmic regret bound. Using this argument, our only remaining goal to bound the two constants Challenges [ and 2 We summarize our above observations in the following lemma.
Lemma Assume that [t)ll S R for some R 0 for all E [K]. Also assume that the estimator [10-11 - 01 S VT-I
1 holds for some constant A >>> 0. Then the (unexpected) regret in
round t is bounded by reg'(t) (t) I 2AR A.. Furthermore, under the margin condition (Challengel) 2
we have (x(n)(rog((t) < 6R2 A
Using the above observation, we can achieve logarithmic regret bound when (() is bounded. For the where (t)ll,,, is bounded, use the peeling technique. Given the history He-1-
0 #* is a fixed vector, and using the results from Appendix J.2 we can bound (t) Th/l, u/, {0:-1 - 0*,60 0*} with high probability. Hence, we can apply similar arguments, and details are presented in Appendix
D.2 Tackling Two Challenges and Fixed History Arguments
Now, we summarize our proof strategy prove diversity (Challenge I and suboptimality gap (Challenge 2). First, we consider the problem with fixed history setup, which involves analysis under the given history H4-1. We set history-conditiones contexts as X == X(t) H and X (X, ..... Xx), where X, E Rdd. We describe more about this history fixing in the next appendix F Under the given event H4-1, d is a deterministic value and no longer random. Thus, the policy (t), conditioned on H4-1, is a greedy policy with respect to d making it deterministic as well. To address any 0.-1. we propose an analysis that applies to any 0 E Rd. In Appendix F. we argue that suffices to bound the variance selected contexts the greedy policy with respect to any fixed Since we fix which corresponds to the value of 0,-1 under the given history H,-1- we define the pelecy-selected arm arg max X, 0. To address Challenge [ our first goal is to find the lower bound of E[..X.). Next, recall that we defined A == x maxifa X 0* and we aim to bound this suboptimality gap. Next, we introduce our two important goals to achieve the two challenges.
22

---

Goal 1.
For any 0, E gd-1 and a greedy policy with respect to 8, we aim to find the lower bound
of
E/c X Xaxxux v/.
Goal 2.
For fixed 0*, our aim is to find the upper bound of Co that satisfies
1
PlA(X) S - Cas +
VT
is straightforward that when we achieve Goal 1, then Challenge can be achieved easily since Goal I prepares for all greedy policies with 0.
D.3 Starting with Truncation
Before we tackle the two above goals, we start by truncating our contexts X to high-probability regions. Since X₃ has bounded f/1 norm max: roughly speaking, there exists set D C R with || 01) and
P E D 1.
We view X as mixture of X {X D and X (X E (DK)o) and with high probability, X is sampled from the distribution X providing a proof sketch, we simply regard X sampled from the distribution with bounded support
[X E DK). J. In this section (Appendix D since we are
DK where || Ó(). In Appendix C.3 we observed that X (X DK} also has LAC,
and since || = (1), it has a constant LAC with (II) = (()(1)) = ((1) since C is polynomial.
Therefore, for this section only, we assume that X bounded support D and has bounded constant LAC function = ((). For a rigorous proof and justification, we provide them throughout Appendix [ and Appendix G
D.4 Event Decompositions
Next, we start to bound the constants in the two challenges. Before that, we present event decomposi- tions for our analysis.
Definition 5 (Event decomposition 1) We define the event {a i Q and Pu(tzzlivi) == (a -)= {X, = x for all j ii.
Pick any v e Sd-1 We can decompose the variance term as
Elu X X. u] = E
E E
X
St]]]
E
2i]]
IE
E
X,X;
v (((a)bo4)]]
For notations E [E [. -I], please refer to Appendix
A
From now on, we aim to bound
E E X
(5)
for any i, (zg Hence, we investigate the property of the conditional density
X, (2 b1)))
and especially we are interested in the density of projected conditional contexts
x v (((xz)izz))
(6)
We define new event decompositions for bounding the suboptimality gap. Under the fixed history, set a' = arg maxie[K] X, 0'.
23

---

Definition 6 (Event decomposition 2) We define the event {a* = if as 225 and 22, (1 == {a" 2} n (X, 2 for all; j + i}.
Next, aim to bound Ca. which is another key constant in Challenge Define the optimal arm a' = arg max X 8* and the suboptimal arm a' arg maxiza" X, 0- By definition, for any > 0, have to calculate
PlA(X) S $) = P 0" 0 [
= =E X 0r Xx Se |
= E [x 0" 0 Se (((())))0]]
= E P P.pxi 12 0- max x 0¹ sel ((((((1))))))
Then, we aim to bound
P max Jマ
2. 0 S X, 0" < max 0r + (1((s))))))))
f*1
and hence we investigate the properties of the conditional density
XTO o ((;)))))))
(7)
It is sufficient bound the maximum density of x, Ar 22 ((1))) since if it is bounded by U. we can see that
PP
m 0r S X. 0r S max x. 0 + 27 ((x, (z)))
$ Ue
jfi
jFi
holds, and we can set CA U.
D.5 Conditional Contexts are Still in LAC Class
In the previous Appendix C.3 and Lemma 1 conditioned contexts of interest, X; 22 (1,)) and X, 22 ((x;)) }), involve conditioning on events
that LAC is preserved under conditioning. Our
such as X; (X, 2; for all j * i, x, 0 2 max, 23 8). which meet the conditions of Lemmal Then, apply Lemma] [ and conclude that these two conditional densities
X, ((x,))))) X, 2 ((x,))
also have LAC with bounded constant function C.
D.6 Remaining Goal: Bounding Decay Rate of Projected Contexts
Lemma tellss that bounded one-sided decay rate of density guarantees lower bound on the variance. LemmaB5tell us that bounded one-sided decay rate of a density guarantees a bound on the maximum density.
In summary, we need to find the lower bound of equation (6) and the maximum density 7 We present Lemma 7 and 5] which tells us that if we can bound the one-sided decay rate, then we can bound the variance (6) and the maximum density 7 By the property that LAC is preserved under conditioning, we can bound the decay rate of X; (1xx,)) and X; 97 ({a, Ji by VdCC. by combining Lemma 3 and the LAC property of conditional contexts. However, our interests are projected contexts, defined as
XJu Ra((as)i)))
and
XTO (
These are projected contexts with some direction v and 0* In the remaining part, we aim to bound the one-sided decay rate of these projected random variables' densities to apply Lemma 4 and Lemma 5
24

---

Support of conditional densities. We first observe the support of the conditional density X; 0 O.((x))zzz). By the definition of Q2 the arm should be optimal under the greedy policy 0 this event. Therefore, its support is restricted to {a E T 2 maxz+1 xz 0)
Next, we consider the density of projected contexts, XTv (,((1)))7+)) Since the support of X; (((fz)141) is of the form {ar E D xx max mj f), our projected density is an integrated form:
P P v - [((((=))))))
PP [X; = x 12 (((t)))))) dr.
[[=EDl="0maxxxtu 02maxzzr 0)((alaTeer T
Geometrically, this represents the total density at the intersection of the hyperplane {x x u= y} and the set {I E D 2 0 2 max 2, 0). We refer to these section densities, as they represent the total density of sections sliced by the hyperplane {x x v)- Further discussion is provided in Appendix
Conclusion. Later in Appendix F and Appendix G since X, 14 (4((aa)) has bounded decay rate vdL Ö(vd), we prove that the projected densities also have a bounded one-sided decay rate of (Vd). Lastly, by applying Lemma we can prove the quantity
E T X,XTT ((((=))1=)) 2
for some (1). Also, using Lemma VdC and we can prove that Ca O(v To summarize, we proceed with the following steps:
5 can prove that the density of 7 has bounded density
1. Event decomposition by conditioning.
2. We know X, (4((1z)))+) and X; ((1)))))+ have bounded decay rate vdL. (Vd)).
3. We aim to bound the decay rate of the projected densities X,Tv u [24(<1)) and x7 0*
2 ((r,)
4. If we are able to bound the decay rate of the above projected densitics, we can bound the two key constants in the two challenges using Lemma 4 and Lemma
For step 3, the remaining important task is to bound the decay rate of the projected densities, which we uddress in Appendix E Appendix F and Appendix G
E Sections, Section Densities and Decay Rate
In this section, define sections and section densities and investigate their properties. Previously in Appendix [ we discussed decomposition by conditioning, and our interest became the properties of conditioned contexts, the form of X; (2((2,) (1a))ae)) and X; ((2gg) Our first goal is to bound the variance of projected contexts, such X,"v (2((Hay)st) for all Rdd. To do that, investigate the projected density of X,T v y P4((21 }+4)). To apply Lemma 4 and Lemma 5 only need to bound the one-sided decay rate that projected density. We saw that its density is the total density of intersections with (a To 0 2 maxjşi x. 0} and hyperplane { x v)- We can view it as sections sliced by hyperplanes, and we provide some theory related to sections and section densities.
E.1 Motivation
In the proof strategy (Appendix)) DD. we aim to bound the one-sided decay rate and maximum density
of projected conditional density, X, (a((zz)aass) and X, 0* (1 hjms). Recall that we define one-sided decay rate of univariate density y (Definition at Appendix D as constant M
satisfying
g(v)) g(y) 2 exp(-M - v))
25

---

for all y < y'.
Then, how bound the (one-sided) decay rate of section density? We present technique bound the (one-sided) decay rate of section densities defined equal and expanding sections.
E.2 Sections and Section Densities
Our remaining goal is to bound the one-sided decay rate of section density. To build some general theory, we first define sections and section densities explicitly.
Definition (Sections) For the set A C Rd and E gd-1, we define sections
Sec v, = An (x x===yy v)
for y E R.
This means that section is the intersection of region A and hyperplane {o E IRd xx y).
Definition 8 (Section density) We define the section density of the region A. Let f be the density defined in the region A C RRd Then we define gly) as the section density of Sec( (A, v, y) as
gly) = -I
f(x) dx.
Remark If the density of X Rd is f, the section density corresponds to the density of X v for E S6-1
Next, we define the areas with special section structures: equal sections and expanding sections. First, define equal sections, the whose section with direction equal.
Definition 9 (Equal sections) We define the set A to have equal sections with E gd-1 when Sec(A, A, u. y) is congruent in shape for y > O.
Next, we define expanding sections, where the sections of A with direction expand when y increases.
Definition 10 (Expanding sections) We define the sections of A with direction as expanding sections when
Sec(A, y) + ho C Sec( A, y,y + h) for every 0. Technically, equal sections are included expanding sections.
A
Sec A, v)
Sec(A, v. + h)
Figure Illustration of expanding section's 's example. The section with direction is expanding when increases: to + h.
26

---

E.3
Decay Rate of Section Density
Recall that we define the one-sided decay rate of univariate density (Definition 4 at Appendix D as constant M satisfying
g(y'
g 2 exp(-MM - y))
for all y < y'-
Then, how bound the (one-sided) decay rate of section density? We present technique bound the (one-sided) decay rate of section densities defined in equal and expanding sections.
Lemma (One-sided decay rate: equal and expanding sections) For A C Rd R and y R. a density I has support A and has bounded decay rate M. Assume that the sections of A with direction v are expanding sections. We define the section density of Sec( A, U, y) as g(y), then have for any < y/2
gly)) g112 2 exp(-MMyy -22)).
Proof Since the section is expanding with the direction e, we can observe for any h > O,
gly h)
Jsec(A.u.vt)) f(x) dr
g(v)
[sec(A.e.) f(x) dr
Ssec(A Mh) dr
Mh)
h (Soce( (xx dr
2 eep(--Mh)
The second inequality holds since the section is expanding and using Lemma 3 Since equal sections are also expanding sections, we end the proof.
Lemma (Maximum density: equal and expanding sections) The density f(.)) has support A C
Rd and has a bounded decay rate M. Furthermore, sections with direction are expanding sections and define the section density SSc(A, y) g(y). If the support of g()) contains an interval [a, b).
then ( & 3M for y E [a, 1-
Proof This can be obtained directly by applying the result of the previous Lemma and Lemma
A
See( (1,(A1,
10
Figure 3: Illustration of A₁ and expanding sections of v or -u. A₁ is the area above the green line. In this case, sections with direction to are expanding! If cylindrical is cut by some hyperplane (which is A)). at least one direction makes expanding sections.
27

---

Two Key Propositions in Fixed Histories (Unbounded Contexts)
This section aims to provide key propositions to prove Theorem and Theorem Our two challenges aim to bound
E[ ((xo()(()aaco(
and
P(A(((1)) s|.
(8)
We define X()) (X) istic value and is no longer random.
Xx(()T) R Under the given event He-1, Pe- determin-
F1 Details for Diversity Constant (Challenge 1
In the definition of the diversity constant, we recall that the expectation is taken with respect to X(t) and the history H4-1. In round t, for any fixed history H4-1, perform the greedy policy with the estimator 0 Hence, when the entire set of contexts X(t) Xx Xx()) a(t) is determined immediately, given the history H Then the exact statement is:
is revealed,
"In round t, for any given history H4-1.
E (at) A.Ia
holds with some A > 0."
In the proof, we proved stronger statement:
"For any greedy policy with any 0 E Fd and selected arm a(t) with that policy,
Ex(:) (t)) A.
holds with some X > 0."
We prove stronger quantity (second argument). For any given parameter Rd. define ag (X(t)) (x (t) and define
(t) min Amin 1101==1
X (10
Since 8.-1 can be arbitrary value, prepare for all greedy policies w.r.t. 0 E gdt-1, Then the newly defined (() satisfies equation (T. and we discuss this in Appendix
Thus, the policy a(t), conditioned on H4-1, is a greedy policy with respect to Q.-1, making deterministic as well. To address any θ we propose an analysis that applies to any E R aiming to bound the variance of the selected contexts. Appendix F. this variance for any fixed 0.
we argue that suffices to bound
min 101|==1
Amin (X)) (x())
Note that oo (X(()) is defined arg [ (t) f. This quantity is equal to
min ||||=||||=|
Eg ||0 (x)(
and we prove this lower bound for any and v. In summary, our aim is to prove that for any history H4-1 and f,, v, we can bound
E I X. (t))
To bound the margin constant, our aim to prepare for all 0* since the true model parameter 0* can also be arbitrary. For simplicity, when contexts are clear, we write (X) (when we fix 0).
28

---

F.2 The Setup of Fixed History Analysis
We aim find a class of densities F such that if X(t) F. then equation lower bounded for any 0, u. Similarly, we aim to find a class of densities G, such that if (() E g. then equation ( can be upper bounded for any 0* E IR.d
1. We first prove that for a fixed 0, e, for densities with LAC and supports satisfying certain geometric conditions, we can bound equation (
2. We also prove that for a fixed 0", for densities with LAC and supports satisfying certain geometric conditions,
bound equation (8)
3. Next, we prove that the densities with LAC and bounded t/ norm, for any given 0, can truncated (with high probability) to densities contained class 1.
4. Lastly, prove that for densities with LAC and bounded 1/1 norm, for any given 0*, can truncate (with high probability) to densities contained in class
In this section, we provide the results of and the next Appendix G we proceed to and 4.
Now, we build the theory with the assumptions that 0, and H are fixed. We assume that random vectors Z (Zg'' ... 2x),, where Z, F. arise from some distribution with LAC L(-). We fix an arbitrary 0 E Rd and define the random index variable
argmin Z, 0.
We also fix E gd-1 and first aim to bound B[y Z,, Z v). Our goal is to find the lower bound of Elu² Zu 2 u] for any v gd-1, from now on, we fix an arbitrary E gd-1, We then aim to bound
Ely Zo 2,Ju)
for fixed 0 and Proposition 2 below shows that when the support of Z satisfies certain geometric conditions, Elu T Z, 2g v] can be effectively bounded.
We next define CA as the margin constant of Z with the parameter 0r, which satisfies
P(A s c| CAE +
VT
where A(Z) is a suboptimality gap, defined similarly in Section Proposition 3 below shows
that when the support of Z satisfies certain geometric conditions, margin constant of Z can be effectively bounded.
Same previous definitions, define the event
Ω2 = {a {a= =i
and
((((s))))) == -a= i) {2 = 2 for all j # i).
Simiarly, define and
22 = fa- = =i}
((z)))iz)) = (a = i) n [2 = žj for all j # i}.
F.3 Key Proposition for Diversity Constant
Recall that we define [-1,1], = (- -11-1 < 1) for any E Rdd
Proposition 2 (Key proposition for diversity constant) The random vector Z (2 ... 2b).
Z, E Rdd, satisfies the following conditions:
1. Z has LAC with L(-) and supp(Z)]] < R.
2. For all i E [K] supp(Z.) is identical for some subset A C Rd. That is, supp(Z) A for
some A C Rd
29

---

3. The support An [-1, 1/ has equal sections with direction
Then there exists an absolute constant e such that
Biu T ZaZa d.(R))²
Remark 2 For unbounded contexts X(t) in the original bandit problem, we truncate to some region C with positive probability and make the truncated contexts satisfy the condition of the above proposition.
F.3.1 Proof of Proposition
Since sZpp < R, it has bounded decay rate vdc(R) by Lemma decomposition, we see
By the established event
Ω U 2e((=))ivi),
(2y)a
and by applying the tower property, we get
Biu Za
Z [(((())+++11
= E
[(((z))ixee]]
Hence, we only need to bound
E Z 0 [
(10)
for every 22 (,((2))44)) Recall that we defined
[-1,1], = for x E [-1,1]]. Then we
decompose it
E/e 2,2, v ((((4))44)
=E
B 2,2Tu
(4 (1-1,1))) | (i((2))a)z))
2 E Z,ZTu (((1))54 n [Z, E[-1,1]]]]
The last inequality holds because El E 222 (+((=1))))) n (2 E [-1,1]],] 1.
Z:Z,v (a((2))444) n 12, ([-1,1],) 2 and
From now on, we focus on the conditional density of 2, (1(2)))) n [-1, and its projected density T Z ((((2 n {Z, E [-1, 1].}. For simplicity, we set the conditional density of Z, (12g)44 n (Z E [[1, as (-) and the projected density of v Z, (11gg)144)) n {2 e [-1, as (-). Using Lemma I the density fi(-) has LAC with constant
function C(R). and it has bounded decay rate VaC(R) by Lemma
[1] Investigating the support fi and 9i- First, we examine the support of fI. Since arm i is optimal with estimator 0, all in the support of fi must satisfy z =T ( 2 max 2j 9. Also, because
-1 S To S holds, this support the intersection these two areas. Define
4 = supp / 24 (4((=)))))) (2+ [-1, (= E A 2 = 2 max 2, 0, -1 S x S 1).
J#1
Recall that = supp(Z,) (Z;) is designed have equal sections with direction Hence A n [- 1] has equal sections with Therefore, the support of Z (2(((z}))z)) n {Z, E [-1, is interval by our design of A.
[2] Bounding one-side decay rate of section density in [-1, We aim to apply Lemma 4 to bound the variance E 2,2, Pa(L=j)yvs) n (2+ E [-1, []1,1].)]. It tells us that it is enough to bound the one-side decay rate of the section density gi (.) in the interval 1/2/
Claim One Seo( A1, v,y) or Sec(A1, -U, y) consists of expanding sections when y increases for y [-1, 1].
30

---

Proof of Claim 1 Choose one of v, o such that (..0) 2 0. We want to use the result of Lemma 10
Since [-1.1], 1, has equal sections with direction v, by rotating the axis, we can satisfy the condition of Lemma T0 Then Lemma 10 implies that at least one direction among or - yields expanding sections. See Figure 5 for intuition.
A1
Sec(A1,0)
1.
Figure 4: Illustration of A₃ and expanding sections of v or v. A1 is the area above the green line. In this case, sections with direction +u are expanding. If cylindrical set is cut by some hyperplane, at least direction produces expanding sections.
Claim [tells us that we can apply Lemma 8 and thus bound the one-side decay rate of the section density (-). Without loss of generality, assume Sec( A1, v, v) is expanding when increases. Then
the support of 2, u Q4(1zzhi4)) n (2, E 1],} is an interval of the form [c, 1] with some -1 <<<<l.
Claim The one-side decay rate P( Z; = (1((()/)))) 1].] bounded by VaL(R)
for y E [-..1].
Proof of Claim To bound the one-side decay rate, we apply Lemma 8 By Claim without loss of generality, sections with direction i.e., Sec(A, v, form an expanding section. By Lemma g we obtain the desired result.
[3] Bounding the desired variance. We now that the support of (-()) has the form [c, for some с < 1. Hence, by Lemma 4 we conclude
Blv T 2, e
|-1,1,1111111111 dC(R)²
for some absolute constant >
Below, we prove Lemma 10 which is used in the proof.
Lemma 10 Consider the (cylindrical- set S = U x I for C RRd11 and an interval I C R.
For E Rd with 0 en and any b R define the set S' = Sn {a To b}. Then yields expanding sections with direction en-
Proof To prove that they are expanding sections, need to show that for any h 0, + hen Sec(S", On y + h) for any Ho E Sec(S", En, y). By the definition of sections, clearly 2o + hen {o Rd x T en = y h}. Next, we must show my + he, E {z x 2 b}. Since e >
(0o + hen) To 2 z 0 b
holds.
31

---

S
St
Gn
U
Figure 5: Illustration of S and expanding sections with direction en. Blue lines are sections Sec(S', , Cn. v). If a cylindrical-shaped set is sliced by some hyperplane, at least one direction forms expanding sections.
E.4 Key Proposition for Suboptimality Gap
Next, we provide a fixed-history analysis to bound the margin constant of Challenge 2 Before we start, we define the cylindrical set used to characterize the support of densities.
Definition 11 (Cylindrical region) We define A C Rdd as a cylindrical region with direction v E gd-1 and length 2H if
A [B + to 11 sts H}}
for some subset C (x T = 0}. We denote this set by cyl(B, v, H).
A
2H
B
Figure 6: Illustration of a cylindrical region A.
Next, we show that the support of each context Z; is cylindrical set, we can bound the margin constant. We state our key result on bounding the margin constant in the fixed- exed-history setup.
Proposition 3 (Key proposition: suboptimality gap) Assume that the random vector Z (Z) ... ZT), Zz Rd. satisfies LAC with function L()) and ||spp(Z))loc S R. Additionally, suppose satisfies the following conditions:
32

---

1. For all i E [K], supp(Z,) C R$ is identical for some set A C R That is, supp(Z) = =A*
2. For some H > 0, Z support supp(Z:) A cy H 1) for all i [K] and PP E (cyl(B,0* H)) ] ò.
Then
P(A(Z) <e) 3v)C(R) 6.
Remark For the original bandit problem with contexts X(t), we truncate to a high-probability region C2 and set the truncated contexts satisfy the conditions of the above proposition. We provide the analysis in the next Appendix
2H
0+
Figure Illustration of (upp(Z.). has equal sections with 0 and || s R.
F.41 Proof of Proposition
Define 2,T0 0* = Us for all i E [K]. With a slight abuse of notation, define the optimal arm a" a== arg max; Z; 8* and the suboptimal arm = arg maxişa* Z, l-
[1] Decomposition by conditioning. We can bound the margin probability by conditioning
P(U.- Uat Se]
E[I(U.. - Uat _e)
E[[(Ua- Ua <) U, S H S H E U2 U.) HP H]
[[[ - U, S E) U. S HHPUU + (By the second condition of the proposition)
[U. Ua S e) U0 H
E E[ U. S 8) (U,t $ H) ( +
< E E[ - U max 2 0r <
(max 2j 0r HH) +
jfi
E E (max jF1
2, < 2, 0r < - max 2J 0*) {max 2J S (12 +
set density Z, {maxx 23 < H} n ((aaaaa))))) and 2 T. (maxzzi 2J.0 S
H} n n22 ((2))+ss) as fa and 92.
Our goal is to bound the maximum density of g2, which is a density of
2 0*
{max 23 0 < H1 11 jfi
33

---

[2] Support of fa(-), 92(-) and their geometry. We examine the support of the conditional density fz. which is
Z = (max 2j 0- < H) (( J# Under the event (12g))))))) we have 2 2 max 2j 6* by the definition of (1zz}]))z)))
Since m 23 0" = b S H, the support of becomes
{= E A =T 2 b). Recall : (2,) and it has equal sections with direction 0". Using Lemmal 1 f2(-) has LAC with (R),, and it has bounded decay rate VdC(R) by Lemma
:
[3] Bounding one-side decay rate. Next, we aim to bound the one-side decay rate of 2, 0 = y { 2] 0* < H) 22 ((zz)). Define the (conditional) density of
z 0r =
{max =j 0r - H) n (1z5)) J
as (2)) Its support is restricted to the region {y y H
Claim 3 The one-side decay rate of
z 0r y {max 2 TJ000 0 < H} (22)())))) j7t
is bounded by VdC(R) in the interval [b, b+bbb 4.
Proof of Claim First, we observe that the support of
jfi Z; {max 2, 0" S H1 (17
is an interval [b, H 1]. This follows from the definition of S2 ((zzh) and our design of A. Moreover, this support has equal sections with direction l*, Since b S H, Lemma 8 applies. yielding the desired result.
3) Bounding maximum density of 92 by applying Corollary 5
From Lemma 5
the maximum
density is bounded by 3v /d)(R in the interval [b, + }.. Hence.
E (max =3.0 0r S Z 0 S max 2 0+ + +e) {max 2, 0r S ((z))))))))))))) <vac(()) ンデ
j#i
jfi
for any < 3
G Proofs of Results for Unbounded Contexts
In this section, we prove our main theorems stated in Section 4.3 We aim to apply the key propositions, Proposition and 3 To apply them, we first truncate our contexts an appropriate region to fulfill the conditions of the propositions. First, we present ways to construct a truncation set, which is used
prove Theorems 2 and] After that, we prove the two Theorems and 3 by applying Proposition and
G.1 Constructing Truncation Sets
This section presents operations to construct truncation sets that will be used in the proof of our main results. In the proof, we first truncate contexts X e gak to truncation set C II D, where D C Rd, and work with the truncated contexts. If the supremum norm of the set is bounded, by combining it with LAC, we can bound the decay rate of the truncated contexts.
First, we define the directional completion of v. For set A and a vector u we define the process of filling A in the direction of v. This process expands A so that its cross-section remains the same when cut by a hyperplane orthogonal to This procedure ensures that all sections of A along the direction are equal. Recall that s denotes the projection of A onto the subspace S. If S the subspace spanned by a vector write n, (A), which is subset of straight line.
34

---

Definition 12 (Set completion) For A C R and v gd-1, we define
C'A, u] == ( (A) + (T).
After this completion, the section sliced by the normal hyperplane of is the same.
C[A, v]
Figure 8: Illustration of C(A,v). This is the operation of filling the area A in the v-direction. Then, all sections in the o-direction become equal.
Lemma 11 Suppose set A Rd and a unit vector v satisfy (A( an interval with length &. Then,
|C[A,, & || + l.
Proof For all E C[A, v). there exists q E A and some h with |/| < such that p = q + lv. Hence,
|lp|lc & ||allo + | S ||Al|oo + l.
Next, we define partial completion, which makes the section with direction v in the region of C(A, v) [-1, 1] equal.
Definition 13 (Partial completion) For a A Rd and unit vector Rd define
P(A,v) == clan for |x: ul S 11),0UAA
Recall that (-).) is projection onto the direction v.
P(A,0)
A
Figure 9: Illustration of P(A, v).
35

---

P(A,t) u) has the same section with the direction e within the region [-1, 1/.. Equivalently,
== in P(A, x TT uu
for every # U2 1-1.1]. The partial completion operator has bounded supremum norm, as shown in the following lemma.
Lemma 12 (Sup norm bound of P(A,u) u)) For any A C Ie and E S
(P I ||A|| +2
holds.
Proof For any y E v)), there is s/ A such that y 1/ + tu for some |t| S 2. Hence,
lo/l s 11///>> + l1telloo S || +
G.2 Proof of Theorem
Our goal is to prove
(1) (.)
for any í and 0. Fix an arbitrary history H4-1 and any 0 E Sd. For simplicity, define (XT ....,.,77 as the conditioned random variable of (X)(t)T, ..... Xx [t) 74-1- Under the history He-1, we aim to apply Proposition for any and v. We also set a = arg max X 0. For any fixed E Red with ||||| 1, goal is to calculate the lower bound of
N..,XK
E/v X,X v).
We view it a fixed history random variable, and aim arguments developed in Section F
To use Proposition 2 we first truncate our contexts (x.....,,X) x into some region CJ, then apply Proposition 2 to the truncated contexts. To satisfy the geometric conditions of Proposition 2 we construct the truncation as follows.
G.2.1 Constructing Truncation Sets
We define the truncation set as follows:
1. Define R1 = Co Fiax (2 + log dk).
2. Define D [- R1 Rd
3. Define D := P(D, v).
4. Set the truncation set C == K
5. Then Cf < Rg + 2 holds (by Lemma 12
36

---

D
8
0/Oc
D
Figure 10: Illssrationn of the set D The red rectangle is D, and D is the union with the green boundary rectangle and D. We force the sections the direction v within [-1, 1]g be equal. Hence, we can apply the previous results from Proposition 2
Claim 4 For any X satisfying Assumption
2
P
CiJ 2
Proof First, we show P[X E D 2 1.2 Since CT
D
suffices to prove the latter. Using 14).
get
K
K d Σ
P|X P S
Σ
P(x
S
P
R.
dK x 2dK 2
1= ==
Define the truncated contexts W = X [X CT) = (W....., WT).
Claim The truncated contexts W satisfy
Elu Xa [.
Elv T Wa TWW
2
Proof Recall arg max X,7 8. Note that
J X w] 2 B(u X X u (x= + X v [[(x)]]
Since [(X < 1, and P = W| N }. we get
Blu X.X.Tu oj 2 I X,X, v [[==]]] 2 W.W, v x = P.P.X- = W|
> Elu T W.W, o).
2
Hence, we only need to bound the diversity of the truncated contexts W = (WTT WT).
G.2.2 Properties Truncated Contexts W
We need to check two conditions: (i) The sections of su,)(W.) in the direction within [-1, 1], are the same for all i. (ii) W has a bounded decay rate v C(R + 2).
Since X satisfies LAC with functions and ||C 5 Rı + 2, it follows from Lemma that X has bounded decay rate of / Vd. +).
37

---

Claim The truncated contexts W have LAC with [(-), and supp Wa)p |lc I R1 +
Proof By Appendix C.3
conditioning on the event {X E Cij preserves LAC with the same
function Also, by construction of Cj and Lemma 11 supp(W)) xc R1
Claim For every E [K], the support supp(W;) is identical for all i, and supp(W;) n [-11, 1] has equal sections in the v-direction.
Proof Since we D the partial completion of with direction v, the sections in [-1, 1 become equal by construction.
G.2.3 Applying Proposition
2
We have verified that our truncated contexts W satisfy the conditions of Proposition? 2 Hence, by Proposition 2 for some absolute constant > 0,
d
B[Wa W. d(Ai + A2 + 2)
Combining with Claim we get
x d (A1 + A2 + 2)m)²
for some absolute constant 0 and it ends proof.
G.3 Proof Theorem
We now use the result of Proposition First consider the case ||0*1/ 1. For the general case, can adjust via the argument in Appendix
Truncate our contexts X = (XT ...x)) to some region Cy = DK where D C Rd, with slight abuse of notation. Define the truncated contexts as W (WT ..... W Note that the support of W; is D. To satisfy the conditions of Proposition want the sections of supp(W;) in the direction 0* to be the same.
xx)
G.3.1 Constructing Truncation Sets
construct the truncation set C2 as follows. First, set R3 = Go Fmax (1 + log dK + 1 log T) and R₂ R3 1.
Set Dj = ([- R² C Rdd.
Set D2 = {x E Rd -R2 S x To R2) CRd
Set D3 = D- D2-
Set D = C(D3, 0*).
The final truncation set is C2 = D
Claim 8 The sup norm of the truncation set satisfies D|] S 3R2 Also, W has bounded LAC with L(3R2).
Proof By Lemma the LAC of W is the same as the original, Z(-). By Lemma 11 ||] S 3Ra
since wy- (D2) is an interval with length 2R2 Since L(-) is increasing and | 5 3R2, W has bounded LAC with C(3R2).
Claim The region C2 has equal sections in the direction 6* and P E C2) 2
38

---

Proof By Assumption
i[ I Ral 2 1
holds for all i,j.
Hence,
2dk 2d .T P E D 2
P[X E D 2
2VT By the same assumption,
Thus,
2
P[X E DJ! 2 1 VT Since D D3,
VT
G.3.2 Truncation with High-Probability Region
We truncate X into the high-probability region C2 and define the truncated contexts W (WT,.... ) We then work with W.
The following calculation shows that it suffices to bound the suboptimality gap of W:
[ ((x)
[ [(())s dx / ((x) dx
PP (AA(X] S =|
$ ( Jc. [(A())s) dx + P Co.
= P|X E Cal
f(x)
4ACKSS)
dx + VT
C2
P.X E C2.
P|X& E C2)P(A(W) Sel
VT
sel+ SE) S P/A(W)
(11)
VT
Therefore, if we find the constant C% satisfying
P[A(W) Sel S CAE,
(12)
we get Cs S C.2
Lemma 13 The truncated contexts W X (X E C2) meet the condition of Proposition 3 with
H R2 + 1 and
VT
Proof Let D cy 0* Ra) for set B C Po., and define D' cyl(B, 0* R2 1). By
similar argument to Claim P e DJ 2 1
1 Hence,
VT
P D' n X C2ll
P|X E D'
P[W D'J
VT
P E C2
Thus, the condition of Proposition
is satisfied with 8 V
G.3.3 Applying Proposition
By Proposition
we can ensure that 212 holds for
Ca =33 3
+ + A2(3R2)
Hence,
CA < 3vd (AI + A2(3)))) = Ö(Vo).
G.4 Proof Theoreem [ Unbounded Contexts Case
Combining Proposition g with results from Theorems
2 and
get
(Tg(T) S cC's d. max
X (log T
By substituting our bounds on CA and Xr, we have
Reg(T) < cC's 2 2 (Ai + Ag(Ri +2)
A 2 R3) (logT)* - Ō(8.).
39

---

H
Results for Bounded Contexts
Now, we present our main result for bounded contexts.
H.1
Two Cases of Bounded Contexts
In the linear contextual bandit setting, lg boundedness is widely used. However, for light-tailed distributions (such as Gaussian or exponential), the & norm is unbounded. Therefore, we divide analysis into two cases: unbounded and bounded contexts. While our previous focus unbounded contexts, here we summarize and present results for bounded contexts.
We classify the analysis into two cases: the first is for truncated contexts, and the second is for naturally bounded contexts, which include cases where the uniform distribution on the ball B z or distribution with bounded density on the ball.
1) Truncated contexts. Truncated contexts refer to cases where the context distribution is truncated from the original distribution. Examples include truncated Gaussian and truncated exponential distributions.
2) Naturally bounded contexts. Naturally bounded contexts include uniform distributions on ball or distributions with bounded density defined on the ball.
H.2 Regret Bounds for Bounded Contexts
Next, we present our result for the regret bound. The first case is when we receive truncated contexts, generated by truncating unbounded contexts to (BR))* where B is d-dimensional ball of radius R. For the bo-uudde case, may depend on the dimension when we choose large R. so we do not hide the R term in main regret bound. Corollary I and 2 gives the regret bound for truncated contexts. Corollary 3 gives the regret bound for naturally bounded contexts.
Corollary (Regret bound: truncated contexts) Ler X(t) be unbounded contexts with the same condition Theorem For R' > 0 with (t) (B ) = O, we receive truncated contexts
X(I) (B Br) ) for some r > each round 2 1. In this case, for R = R' + r, the regret of
Algorithm 7 is bounded by
Reg(T) S " C(R)) (
when x R'.
Corollary (Regret bound: high-prob truncated contexts) Let X(t) be unbounded contexts with the same condition Theorem [ We receive truncated contexts X(t) (Bz)* for L Z Vdxmax log d + log K) each round In this case, the regret of Algorithm bounded by
Reg(T) Ō(d25).
Discussion. For Corollary 1 when receive truncated light-tailed distributions (e.g.. Gaussian, exponential, Laplace), this theorem states that they enjoy a logarithmic regret bound. has poly(log 7)) regret bound for 7 and depends on R. the truncation radius. Corollary 2 states that when we choose a sufficiently large truncation radius, the bound becomes radius-free free, matching the unbounded case (Theorem D. Proofs for these corollaries presented in Appendix!] [
Next, we introduce the regret bound results for naturally bounded contexts. Here, new parameters c. and are introduced, along with Condition [] This condition will be discussed in Appendix HH.] where we clarify that both uniform distributions and bounded-density distributions satisfy We will provide detailed explanations and state the range of c., for several distributions, including the uniform distribution.
Corollary (Regret bound: naturally bounded contexts) Let naturally bounded contexts X(I) RB satisfy the LAC condition with function L(-) and Condition 1 holds with concentration
40

---

parameters each round t. Under Assumption and
the regret of Algorithm 7 is bounded by
Reg(T) S OkKK c1-
Discussion. Corollary applies to the uniform distribution and any distribution with bounded density on the ball. It also covers the truncation of heavy-tailes distributions. For Corollary 3 the polynomial dependency K is due to boundedness, and it matches the asymptotic result of the uniform distribution studied in 12] when = 1. Combining with Lemma 15 for a uniform
distribution or bounded density distribution in the ball, we have Reg(T) O(K at (2.5). For Condition T and parameters c, and p., we deeply discuss it in the following part. Proofs for these corollaries presented in Appendix M
Comparison with known results. For truncated contexts, to the best of our knowledge, there are no known results for greedy bandits. For naturally bounded contexts, Oh et al. [28] studied the case of a uniform distribution on the sphere, where each context X, for arm is independent across arms, and they only considered the case K S d. Their work assumes the minimum eigenvalue of the context covariance matrix is constant; however, for a uniform distribution, scales as 2 Taking when K d. When K S d, our result has the bound (d2-5 -111 for the uniform distribution. Moreover, for the multi murtt-p shared context setup, Bastani and Bayati 77. Bastani et al. 8 studied the uniform context case, and their worst-case regret bound O(K4d*) considering that the minimum eigenvalue the context covariance scales as In conclusion, our result is the sharpest among known previous results.
this into account, their regret bound is (
H.3 Concentration Parameters for Bounded Contexts
We introduce condition that defines two concentration parameters measuring sufficient con- centration for bounded contexts. We will show that truncated contexts satisfy this condition, as do naturally bounded contexts with bounded density. This condition does need be assumed for truncated contexts, as it is automatically satisfied.
Condition 1 (Concentration parameters for bounded contexts) For the random vectors (con- texts) X (X, ... E RdK where Xi E RB there exist < c, 1 and 0 < p. 1 such that for every 7 with ||1||2 1,
P max x c 2 P. [i(k]]
We call Pr, C. the concentration parameters.
Discussion. Two parameters, c. and p., must exist if X random. Below, we discuss - c, and P. x for truncated contexts truncated into the positive-probability region. Additionally, we show that a uniform distribution within the ball, as well as any distribution within the ball with bounded density, satisfies this condition, and explicitly calculate the range of these two parameters. For our regret bound, we have dependence on (1-0.)²
Example: truncated contexts. The next lemma states that truncated contexts satisfy Condition T with 1 C. x 1. If contexts are generated by truncating the original distribution into positive- probability region, then the parameters in Condition [ c,, P., are well-defined and do not harm the regret bound when we choose sufficiently large truncation set.
Lemma 14 (Concentration parameters for truncated contexts) Suppose the unbounded contexts X E BdK satisfy
P (BRr) = =p> 0,
for some Re > 0. Then, if we truncate each X; F for any 0, [K], the truncated contexts X XX ...., X satisfy Condition with p. P,C. W+
R'
41

---

Proof
Recall that we truncate X to (BR++)* If E (Bx) 0 and we truncate to
Br'+r
P[(max X R (Br++r)*)
max X, S R¹ kE|K]
P P (B
IP X (BRi) )
P X E [B
P E (Brr)
p.
Therefore, we can set P. = and = R'+r
N²
Example: Bounded Density Distributions The lemma below tells us that uniform distribution or a bounded density distribution on BR satisfies Condition and provides the range of the two parameters. Without loss of generality, we prove it for distribution defined on the unit ball 13.
i E [K], each with density upper-bounded by wa Here, wa is the volume of the d-dimensional unit ball B1. (Recall that the density of the uniform distribution in By is .
Lemma 15 Consider a random vector X, E B
aad
1. When X1 =.. XK (strongly correlated), Condition Tholds with
1
P.
1 1-c,
2'
2. When XI,..., Xx are independent (not correlated), we have
1
1 1 c, 2 ee' 22.
2'
Proof We use the result of Claim 10 below.
Correlated Case.
X = X2 Xx. then the 2 -quantile e, of X,T, satisfies
1 Wd a
2(1 c.) 2
2c Wa-1
- x 1, it follows that (
Since
Wa
1- 2 1.
Independent Case.
X XT are independent, then for a certain e, with
-(1 Wa atr
2(1 c.) 2 2 = Ke Wa-1
K aiI,
we have P n S R <
1 K for all i [K]. By independence, P+ = (1 1 s 1
Claim 10 Consider random vector X Rdd defined in B, with density upper-bounded by Sz. For we
any E Sd-1 let the (1 p)-quantile of X be a. Then
21-a) a) 2 1 - a² 2
Wd
a41
Cu Wd-1
Proof We show that a with 1 - a² = (P #d T
satisfies
wa-1
P
a) p.
42

---

Since the density of X 1 17
satisfies
P[XT== n= - wa-1(1 2 +
Wd
we have
P[X n 2 al
Wd-1 - -p²)==² -
1 dr
Cu
wd
S Wd-1 (1 - [1) (1 a d
Wd
Wd-1 (1 a² ) =
S Cu
Wd
S p.
H.4 Results for Two Challenges: Bounded Contexts
Now, we present results related to two challenges for bounded contexts. Proofs are provided in Appendix
Proposition 4 (Diversity constant: naturally bounded contexts) Suppose X(I) is random vec- tor supported in (BR)*, its density satisfies the LAC condition with constant function CRR), and Condition 7 with Pa, C, holds. Then
p- (C(R) R[I-o.)
xx(1)
for some absolute constant 0.
Proposition 5 (Diversity constant: high-prob truncated contexts) Suppose X(t) Raxk sat- isfies LAC with L(.) and Assumption 2 Then we truncate X(t) to (Br)* for some L 2 dv (1 + log (Kggss)) )) and define these trancuted contexts as X(I) = (X)..)...., x())).
Then X(t) has a diversity constant (Challengel) with 1 (t), where (t) is the diversity constant of X(t).
Proposition 6 (Suboptimality gap: truncated contexts) Let X(t) be a truncated random variable of X(t) into (BR)* with P[X (BB))] 2 1 8 for some 8 > O. Let Cs(t) (t) be the margin constant of the contexts before Irancation. Then the margin constant of truncated contexts X(I), denoted by (t))), satisfies
1 C&(() < T-8 Ca(1).
Proposition 7 (Suboptimality gap: naturally bounded contexts) For naturally bounded contexts (() with LAC function L()), the margin constant bounded by
Ca(t) S cKVaL(R)
for some absolute constant >> 0.
Discussion of Proposition 7 It has a linear factor in K, which can worsen the regret bound compared to LinUCB and LinTS when the number of arms K is large. Nevertheless, this factor arises in the logarithmic regret bound, which is still advantageous compared to algorithms that achieve O(VT) regret when T > K. Also, if every X²(1) follows a uniform distribution independently, then extreme value theory 112 implies there should be dependence on K. Hence, our result matches the lower bound for the uniform distribution, which indicates it cannot be improved.
43

---

I Proofs of Results for Bounded Contexts
We provide proofs for Appendix H For simplicity, we assume R 2 1. Using the observation of Appendix C.1 any density defined in Bx with LAC 2()) has a bounded decay rate vdc(R) by combining Lemma
L.1 Fixed History Arguments
We fix again the time step t and the history H4-1 and derive the fixed history results for the diversity and suboptimality gap. We use the same fixed history arguments in Appendix F We the history- conditioned contexts as X :- X(1) Hz-1. and X = (XI ..... Xk),X: X₁ E lk. To address any greedy policy with respect 0,
propose analysis that applies to any greedy policy with an arbitrary E Rd. In Appendix F.1| we already argued that it suffices to bound this variance for any fixed 0. Since we fix 6, which is the corresponding value of 0,-1 under the given history H4-1+ define the policy-selected arm arg max X, 0. Following the previous definitions, define the event Ω == {a = i and Q2(12 his) = {a- i) (X, = for all j # i}. Similarly, define ? = (a* =1 and s2 ((a))14)) = (a* =1 Xx Iy for all + a}.
Event decomposition and conditional density. We first define = max X, 0. Similar to the unbounded contexts, we decompose our diversity as
E X
= Pib < R.
X.X b.c.R.R
+Pb P C/ x
ス p. E X b R.
2 p. 1 X v (b R) n (2
Therefore, our next interest is the projected contexts, defined as
XTo | (a(tzglsa)) {b R.
Let us define this projected context's density as g(-). We first investigate the support of the conditional random vector,
x, (.(() Sc.)
and define its density g(-). The projected context's density g is the integration of f within the section {o E BR To b} n {a BR xx y}. Hence, the density of X,T (b c. section density of (ir BR 0 b} with direction v.
I.2 Sections of the Ball
Next, aim bound the one-side decay rate of the section density in the ball. Unlike the previous sections, the sections corresponding to ((,((z) 1945) no longer make expanding sections due to the boundary of Bg. To deal with sections for bounded contexts, define several sections of the ball.
Definition 14 (Sliced ball) We define the sliced ball S y) as
SR(C,v) = for E BR x v 5).
Also define the double sliced ball
SR b, v, = far E B y. x b).
44

---

SR(0,,b u,
8R(0,b)
0
Figure 11: Illustrations of various sections in the ball Bg. The red line is (n b, v, and the green line is ())
For bounded contexts, we need to bound the one-side decay rate of the section density, where the sections are sliced balls. Recall that we set 6 = maxj x² 0. We aim to obtain the lower bound of
x (.((=,444) (b = R]
(13)
for any (2,((,) )ix)), b. Observe that the support of T X, = y) 14(12 n (b S c, Rt is the section of double sliced ball, (, b, v, y). Here, we aim bound the one-side decay rate of these section densities to apply Lemma
1.3 Linear Section Maps
To deal with varying sections, we define linear section maps, and using linear section maps, we can bound the one-side decay rate of the section densities. We first define projection map, a projection to the center of similarity.
Definition 15 (Projection map) We define the projection map between A C Rd and P E Rd as map Tb A + P, which is an affine point projection with the center of similarity at P. Furthermore, call P the projection point.
A
P
Figure 12: Illustration of projection map.
Remark 4 A projection map means homothety toward some point P.
45

---

Definition 16 (Linear section maps) We define linear section maps between sections. For two sections of Sec(A, v, y) and Sec(A, v, y + h), we define the linear section map b as
(.) Sec( (A, v. + S.
which satisfies b (Sec(A (A, v,y)) Sec A, v, ft) and b is part of some projection map with center P.
S,
Sec A, v, h)
Φh
P
H
Figure 13: Illustration of linear section maps. A projection map of Sec(A, v, ) to P inducess a linear section map (ec(A,e y) to Sec u h). We also H the length between See( A, v, and P.
L.4 One-side Decay Rate of Linear Section Maps
Our subgoal is to bound the one-side decay rate the section density, and linear section maps to achieve this. Previously, we dealt with expanding or equal sections; hence section maps directly gave the lower bound of the density. However, for general linear section maps, they are no longer expanding sections due to boundaries. Assume the density f is defined in B and it has decay rate M. If f has LAC with function ((-), we already studied in Lemma that it has decay rate with M = VdC(R). We can set L(R)= 2 10.
Slope linear section maps. We first bound the maximum length between (x) and It related to the slope of the section maps, and we define >> such that
(x)
x112 I s
for any Sec(A, v) We call the slope of the linear section map (.)
(h).. This value is the same for any Sec(A, v. v). since we use linear section maps. Using that, we can calculate the lower bound of gly + h) as follows:
Volume element. We define (et((V4)))))
I SscCAA..
gly hh)
f(x) dæ
(s (x) det (v)
Sec(A,r,g) f(x) exp( M h)) uy (h) dx
exp(- - -M 8 h) u. (h) 9(v).
46

---

The third inequality uses the Gronwall inequality, Lemma 22, applying that the decay rate is bounded by M and the length between a and () is bounded by s This formula tells us that to bound the one-side decay rate of the section density, there are two quantities: slope and volume element My (h).
A way to bound uy (h). Let us define H as the distance between Sec(A, v, and P. The volume element can be calculated
H - h d
uy
H
since
H- is the ratio of similarity. Then, H
g + h)
2 exp (
1-Msh- [- d log
H h
-
11)
g(v)
H
H. When h S 2. have log
H
2 1
2h
H'
g + h)
(- Msh
2d
2d1 h)
exp
glv)
This implics that when can find the linear section map t can bound the one-side decay rate of the section density by Ms +
1,5 Linear Section Maps between Sliced Balls, Sneve, y)
Sn(0, v)
SR(0. + h)
Figure 14: Illustration of the linear section map between two sections of the ball. The linear section map is constructed with the center P.
Lemma 16 (One-side decay rate of &R(U.V) v)) The projected density g(y) of sections SR(V, v) sat- isfies
g(v') g
2 1ap(-3VaC(R)) (y' -y)
for any
3/2 < < 3/
vi
Proof Let v/ = y + h E |-
Set P as the similarity center of Sæ(v, y) and Sæ(ve, y + h).
We aim to apply the arguments of Appendix I.4 Using this P. we can form section maps $ First, the slope of Φhh is bounded by &
S 2 for 1yv S V The volume element of t
12 (ytayz
47

---

can be interpreted as the ratio of similarity. Let H be the distance of P and Sg(v, v).. Note that
H z R² (x+h)² 4th and hence 2 2h holds. By applying the result in Appendix I.4 its one-side decay rate in Va va is bounded by
2v)[(R)+ + 2d
2d (y + h) H I 2vdc(R) - R (y h)2 S 3v)c(R).
This holds for all
vd S y < y + v since ((R) 10.
1.6 Linear Section Maps for Double Sliced Balls, (R v,
Goal. We investigate the one-sided decay rate of section densities with sections Sg(0, b, v, y) for fixed 0, u, b. For density fx) defined in R with LAC function L(.), we define the section density
of R (0, b, v, as g(y). We M 4vd ((R) R=(--.)) We prove that the one-side decay rate of g y
16v/d
M M. is bounded by M. Also, we define small angle To sin (MR).
I66.1 Case v 1 6.
For this case, the sections (f, b, y) are no longer expanding sections when (0, v) is close to 2. In that case, we can construct linear section map, and the following figure illustrates the procedure. In each section S 6, v, 2) and (0, b, v, + h), assume the highest coordinate with respect to direction 0 is Q and Qn. Assume the directed half-line starting from connecting Q to Qn and the hyperplane {xr the center of the projection map and we can construct the linear section map using P. Please see Figure 13 the intuition.
0 = by meets at some point P. Then we can set the intersection point P as
Sn(0,b, v,0,),
Sp(0,b,,,y+
Q
b
H
0
v
H'
Figure 15: Illustration of section maps between SR(0, v, v, and (R b, v. + h)). We connect two points Q and Qn. Let P be the intersection with {x x TT = b). Then, using P, we can set the section maps between (6, b, v. y) and SR(0, b, U. y + h).
Lemma 17 (One-side decay rate of double sliced ball) Suppose b aR for some 1. v I 6, suppose we construct a linear section map by the sliced balls between Sy b, v) and
Sn b, u. + h) for aR the way described above, By setting M 2/d C(R) + R²(1-a)
svd
the one-side decay rate of the section density g(-) in the interval M by
h M is bounded
g + h) g(v)
> exp(-M (Mp0-M10 h).
48

---

Proof We aim to estimate and H to apply the arguments in Appendix 1.4 To bound 8, we can easily see that $ (y=- I
since related to the slope of the tangent line at y h.
To bound H, with some elementary calculations, we have
Rº y² c.R
- H'x
v R2 - y2
for
R² (y + h)2
H'
y + h
H' is defined Figure 15
Then we see
d
4+H h
V R2 y²
d
H
R² (y h12
VR² R2 122 o.R
2 2dy
<
1 1 R2 122
for any y.y h E [-
M. M. Then,
1.
2d
8dy
2vā[(R)
S 2v)
S M.
H
(2
The remaining part is proved by the argument from Appendix
L6.2 Case TO S <(v, S
In this case, we define 8' = using and 0'. For new sections, (0', b, y), we can make section maps as described in Lemma 17 We can see that these section maps also become section maps between (n, b, v, y). By using Lemma 17 for with 1 --c. and O', u, we have
0 0-v(0 0) ( TT) 0)1|2 and we aim define section maps between ( b, v, y)
g + h) (
2 exp(-MM)
holding for M 2(R + ==(1-.)) and any M <y<yth< M
16
I.6.3 Case 0 < (vv, < T0
In this case, the natural section map between Sn(v, y) and Sz(u, y h) for any M <y<ツth< M can be an expanding section map for y, y decay rate of the section density is bounded by
M M. We already proved that the one-side
g + h) g(v)
2 exp(-MM)
using Lemma 16
49

---

un, 1))
bn(0,b,,,))
[x 0 2 07
8R(U +h)
Sg(v,v)
Figure 16: For the case where 0 and v do not form too large angle, we first define linear section map between S(0, y) and S(0, y + h). This section map can also be the linear section map between S(0, b, v. v) and S(f, b, v, h). Using this map, bound the one-side decay rate of section densities of S(A, b, v, y) by Lemma 16
1.7 Proof of Proposition
We first fix 0 and e with the same argument in the proof of Theorem 2 For fixed history contexts
x= X xx) and fixed and v, define as the second largest value of (X 0, 0,..., N....,,K xx 0). By
Condition 1 first bound
Bi T XaX = Pib & c.
R
EEU X bb.. P/b > e. E| X,X b R.
2 p. E
X X bb c.
2 E
{b [b
2 E
E
X:X
(b
Then, we aim to bound
X,X,T ( ((((
Further observe the density of
XTu y Ai(lssbzi) n (bsccll R..
is a section density of sections (n, b, v,
Case 1: - To - <(0, S z. By applying results from Appendix 1.6
I.6 and Lemma we have
1
E X,XTT (b < c. 2
M
Case 2: 0 ((0,u) = To-
By applying results from Appendix L6 and Lemma we have
1
Ely XXXTU (b cR n2, 2
M
Case 3: 1(0,r) 2 5.
When we replace e with - it falls into Case or
50

---

L8 Proof of Proposition 5
Proof Using a similar argument, we use the fixed history arguments. Write (XI..... xx) ((t) H4-1 and we first fix 0 and consider the greedy policy with estimator 8. We define X. as diversity constant of X. Also, we define In eo (1 + log dK + n and set the event B, = {X; E (0, Ln) for all i E [K]}. We determine Y > 0 later. By Lemma 19 we have P[B,]] ym We apply the peeling technique bound the truncated contexts:
E x
= x BiJ+ Σ
B|XxX B \ Bal.
n=1
By setting Co Vd Fmaxx 3 -1- 1++ log dk, observe that
x[xaxa T But1 Bn] 3
I ym Ia
? Ia
[a(3+ 1o(3+nlu 1
ym
==1
00
1
2a 2 (33 n² $llo"* 7) gm la
y 2 3d x, we have
1 x B.t1 \ B,] 1 B,l
\₂ la.
Using Theorem
we get
1
Ia S E[X,X,, B,] +
h Ias
2
and hence
1
B Bi] 2
\₂ Ia.
2
Finally, we get
X B > >.
1.9 Proof of Proposition 6
Define ( as the suboptimality gap of X and denote its density as fx(x), x E (Rd)K, By direct expectation, we get
P ((A(X) SE /
fx(x) do
fx(x) dr
|AIX)SSIND
P E D
fx(x)
dx
(A(X)Sc)
P[X E D
<
1 1-8 P(A(X) S s]].
which holds.
51

---

I.10
Proof of Proposition 7
By conditioning on H define fixed history contexts X (X7 ..... xx). similar previous
proofs in Appendix G
We decompose the probability of the suboptimality gap
K
P (X)
S
Σ se)
E ( (x, xz [
Σ E [[ 27 S xX.0 S max o or + 8) {x, = 3. m
j#1
J#i
the last equality holds by the definition of Q2 Next, we aim bound
P [[[max=] 0r S x 0 S max z 0 + + {x, = xz) 23}1+1]
571
j
Similarly, we only need to bound the maximum density of
{X, = Iz | and it enough to bound its one-side decay rate by Lemma 5
P P 0-
Since the conditional density of
X, (X, Ø; )
say f.).), , has the same LAC with constant function L R), thus has a bounded decay rate ((R) by Lemma Also, the density F[X, 0" = y/ {X, xy } is a section density of S R y) for y E R. R). Then we observe that in least one of the directions of #* or - the sections Sn(0* are expanding sections in Rz. By applying Lemma g we can bound the one-side decay rate of the section density X, 8r (t) æ; Jiąi by vd and finally can bound the maximum density by 3 (()) using Lemma Therefore, by the decomposition above, we finally
get
P(A(X(t)) SEjS Σ 3V)
HE|K]
< 3K VR)(
L11 Proof of Corollary
[
We have (t) 2 c 2
with c, by using Proposition and Lemma 14
(C(R)+ at al-a.) p
Hence, we get X, (4) 2 TE(Ry=
X,. Also, using Proposition 6 we have the margin constant of
truncated contexts Co bounded by
1 Ca. where CA is defined in Theorem We can see that
I-p
Reg(T) S co² d Cs X
(log(T))²
( 25 R2 C(R) )
holds.
I.12 Proof of Corollary 2
L 2 Vi Xmax (3 + dK), we can use same proof as in Theorem 2 For the diversity constant of truncated contexts, it is lower bounded by 2 (²), where (x) is defined in Theorem Also, using Proposition 6 have the margin constant of truncated contexts Co bounded by 1 Ca. 1-p where CA is defined in Theorem Combining these observations, can finally apply Proposition since truncated contexts also have bounded -nor by Fmaxx and we get the desired result.
52

---

I.13 Proof of Corollary 3
can prove it directly by combining the results Proposition and Proposition obtained directly by combining those results with Proposition 8
This can be
J Analysis After Challenges 1 and 2 are Satisfied
We now present the results and proofs to obtain an exact regret bound after the two challenges are addressed. Recall that define the (unexpected) regret reg' (t) (a (t) (t) Xa(o) (t) (t)Te and the expected regret reg(t) X()) (reg' (t)). We can achieve logarithmic regret bounds the contexts meet Challenges and
We first present our regret analysis for bounded contexts.
Proposition 8 (Regret analysis: bounded contexts) For bounded contexts where [|xx(1)]l2 S R. suppose that B (aatt)XXa(t (HH-1) = X and Ca(xit) I Ca for all t [T] and H4-1- Under Assumption 7 the expected regret of Algorithm iis bounded by
Reg (T) < co RR (log Ō Co CA).
X
Next, we present the regret bound result for unbounded contexts, under the satisfaction of the two challenges.
Proposition 9 (Regret analysis: unbounded contexts) For unbounded contexts where [t)l())ll S Imax. suppose that E (at) Xate) H4-1] > A,I and CΔ(X(T) S Ca for all t [T] and He-1- Under Assumption the expected regret of Algorithm is bounded by
Reg(T) S co D max dCs X,
(logT)*= = Ö max X
J.1 Proof Proposition g
Firstly, set To A,A Rog + log d) for the constant ei defined in Corollary
9 Before starting
the proof, we define the good events that satisfy the sufficient concentration of the estimator O,.
Definition 17 From now on, in this section, define the event E, by
E, = (mmin (E(1) X 1).
This is the event that the Gram matrix has sufficiently large minimum eigenvalue. The event Fg holds with high probability according Corollary
Corollary For 2 To. the following holds:
1 FgJ
2T
Proof Using Corollary 9 with probability 1 272. E, holds.
Definition 18 (Self-normalized bound OLS estimator) Next, we define the event F, as
F {100 - 0x < /d (T(1 +(+)) + +1}.
which satisfies the self-normalized concentration of the estimator.
53

---

Lemma 18 (Concentration of OLS Estimator) For any t >
4 X T
Pl n Ed 2
holds.
Proof Under E,, we have (t) = A,tta. Then the concentration of the OLS estimator satisfies
[10 0* (x(()) = (z))) (a(t)(T)n+))
T=1
(x()) (5tt) + Ia)
(T(r)(T)
2
(aG)(T))))((1)) La)
(a(r)(T)n.))
To bound I, we use Lemma 24 from Abbasi- Yadkori et al. [ and obtain the desired result.
Next, we introduce an important lemma used to obtain the concentration of the minimum eigenvalue of the Gram matrix. We define G; := Ni= E, n Fy.
Corollary 5 (Good events) For the event G, defined above, for any To S STS
1 T
P P 2 1
holds.
Proof Straightforward from the previous observations.
Then, under the event G2 we have the following corollary by the definition of event Eg and Fú: Corollary (&z concentration: bounded contexts) For any t 2 To. under the event Gt. we have
||0. 1- S ca Vd T
A,t
for some absolute constant > 0.
Proof of the Proposition. We are now ready to prove Proposition 8 First, for time 2 To. the history H is contained in G with probability
J. The expectation reg' (t) is calculated with respect to the randomness of the whole history H.- and the distribution of contexts X(t). We
observe the following for (d) 4a / ddoog + T2
E(reg' (t)] EH,., [x(0 (reg' /reg' (t) H.-1l]
Ex(0) (reg'(t) (t) G.- [P R
112
< <GCA)(d)²
(1. -1], + R (by Lemma R²
+ T $ <6Ca>(d)² 11-1)
By summing these inequalities until T, obtain the desired result.
54

---

J.2
Concentration of Sub-exponential Contexts
We now provide regret analysis for unbounded contexts. To do that, we first provide some known facts for sub-exponential vectors. Under [ssumption (t) has & norm with mmax- Using a result from Wainwright [38). for any v E gd-1, there exists an absolute constant co > such that
(t) v| > co (1 + u)] I exp(-u)
(14)
holds for all u > If we set v = E = (0, 0, 1,..,.0) 0). then we get the concentration for each coordinate,
X (+) max (1 + u)] & exp(-u)
First, investigate the concentration of the & norm of the contexts.
Lemma 19 (High probability & bound of the contexts) Suppose the contexts X(t) satisfy As-
sumption 2 then
max (x(t)l22 cu daxa (1 + log(dK)) 8)) [
holds with probability at least 6.
Proof For any v E gd-1, we know
P(IX:(()Tol 2 co (1+ + [w] S exp(-11
by the result from Appendix J.2 Then, we get
P there exists E [K] such that ||x(())l2 > Vd Vd-xmax (1 log(dk
6D
Tmax (1 + log(dK |1)]
Xis(t)) > co
1=1 j=1
< dK dK 5.
J.3 Proof of Proposition 9
We now prove Proposition Gram matrix for unbounded contexts. Next, we define several nigh-probability good events. Finally, we bound the regret using the peeling technique.
9 It consists of three steps. First, we investigate the concentration of the
J.3.1 Gram Matrix Concentration
For bounded contexts, we can apply Lemma 23 and Corollary 9 to ensure the linear growth of the Gram matrix. However, for unbounded contexts, we cannot apply Lemma 23 directly since it requires l boundedness. We apply the same technique used in Kannan contexts, which are not bounded. They use a truncation technique to guarantee the growth of the Gram matrix: interpret similar arguments here. In this section, we set our truncation radius L = ev dx [1+3 log dKT and define Ti
20) who also deal with Gaussian
the mixture of truncated contexts and large Eg norm contexts. We apply
X.
2 x
(2 log + logd).
Lemma 20 For any t 2 Ti. the following holds with probability 1 72:
Σ(1) 7 Aal.
8
Proof We prove using a similar argument to Kannan al. 20 to bound the Gram matrix. We view Xt) given the history H,-1 mixture of Xxtt) IB, and Xt()) B Consider invisible
55

---

coin toss C, for every time s [t) and if = 1. the contexts are drawn in ((t) (BL) = 0, they are drawn from (() (Bi) R. By our choice of bigh-probability region radius L, for any cs+ Plc, = 1] 2
12. Define Et) as the Gram matrix of the contexts sampled from the truncated distribution for all I < t. For truncated contexts, Proposition 3
tells that it has diversity constant dd, under our choice of L. Then, by our independence assumption and Lemma
1 x.
P(Amin (E(1))
X.
F(c for some i [4] [P[ mmii (I())
T xT exp(-c1 A.1
1
2L
Hence, if we choose / 2 Tı, we get the desired result.
Recall that L = da (1 + 3 log (KT ))
J.3.2 Good Events
We present 4 concentrations and define good events that satisfy the concentrations.
Concentration 1. For any t 2 1, with probability 1 - Ix,(t)ll2 S L holds for all i [K]. Then, under that event,
TL2
det(E(t)) (1 d
and
TL? d
log (ectet((())) (E(()) S d dllog(1
Concentration 2.
For any 1 T, with probability 1 7t. using Lemma
24
we get
(T)))))))) Ta) (a(o)())H)) s (22llo((Tdde(((())
Concentration 3.
In the previous section, we showed that for any t 2 Ti.
Σ(() z Xe
holds with probability -.
Combining these three concentrations, we get the following result: with probability A for any
t 2 Ti,
||0, - (((())) =
Xa(r(()),)E(())-- Xa(r)(T)
$ 2 Σ
Xa(e) (E())
-1 2( (T())(T)
r=1
2 log (Td(eedd)((((())1))
20
log (o(((((( log T
d
s 2
log(1 + TT2) + log T
2
I c dlog
The second inequality holds since, under Concentration 3, Σ(I) 2 (EE()) + Ia). We finally obtain the following l fzconcenttottion result:
56

---

Corollary 7 (&2 concentration: unbounded contexts) For any t 2 Tí, we have
1
[|0, - -0-12 I ca
d
Vx,t
for some absolute constant with probubility
T
We define event G, as the event in which Corollary holds and set G, U²=r, G+.
Finally, we present a key analysis to hound the regret. Recall that we set Ti = 1 Loogd (1 - 2 log T).
X.
Corollary 8 (Good events) For the event G2 defined above, for any Ti STST.
4 T
P[G 2 1
holds.
Proof Straightforward by the previous arguments.
J.3.3 Bounding Regret by the Peeling Technique
Lemma For 2 Tı, under the good event Gt-1, and if (1))lls S Tmax then
CA 773
Ex(e)/reg (4) < cd x max (I - 1)
holds for some absolute constant >> 0.
Proof Under any history contained in G.-1, by using (14. with probability 1- T we have
Volog T
max IX:(1) K
(0001 -001 < cax v(t 1)1.
(1 + log KT): =
for some absolute constant e > 0. We define this event as Kr. Then, the (unexpected) regret is bounded by
reg' (1) S 2e.
We now bound the expected regret:
E(reg' G (t): G G (t); G 0 K?]
< 2e 2 PP reg (t) > 0; G.-1 K,] + E[reg' (f); G O K[]
2e Ae (t) < 2e] 1Eree (f); G n K.]
6C E|reg (f); G. 0 K.
In the last inequality, we use the definition of Challenge 2 and Lemma
Peeling technique for tail events. Next, we bound E[ree' (t) GG- using the peeling technique.
Let Ln co de (1- log dK log 7) for 1, where will determine later. Then, by results from Appendix
P max
(1(1) 0 Tmn] S Σ
P[X
KE[K]
7
(E[K]
57

---

We define the event Va as {max [X,(t) T01 E Lntil) Then P[V.] < 1 and Elreg' (1); Vo] S 2m. Set a co di 3 = 1 + log dK. The regret can be decomposed as
E(reg' (t); G n K3] S E[reg' (t); G St-nnkjnvi
Elreg (t); KY (Va+1 \ V.)]
2 2L 1 nK1]
Elreg' (t); n (Vn+1 V.)]
n=1
211 T
+
Ln+1 7
n=
1
8
1
< 2L, T
+
((3 n log
7
1
< 3L T
when y 2 (a:3)3 +22.
Now set y = (aB)* + T2. Then we have
E[reg'(1): G,-1 S cC' (Calaomaxx VdlogT log(
S Cad'C
(log 7)3.
V(t 1),,
max d. - 1)
Main proof of Proposition 9
We apply the result of Lemma 21 For t 2 T1, we get
E(reg' (1)) dC max d. (. 1) (log 7) + Eree'' (1); G
S cCAdx max -1 (log 7) + Wiree (t); G
Next, we examine E[reg' (4); 1 We also bound this using the peeling technique. We define the same Top and Vn in the previous Lemma
E(reg' (t): G s (1); +
Eireg' (t); (Vu+1 \ V.) n G
< 2L,F n G
Σ
Bfreg (t): (Vo+1
1
2L T
+2
L Li+11 7
n=1
L <
T
for some absolute constant > Thus,
1
Elreg' (f) S dx max X, (t 1)
(log 3
By summing up, we get the desired result. For /. < Tı, using peeling technique shows [E(re(()) S cla. Hence
1
Reg(Ti) s cLiTi S Co max X, (log T)
Then we can get wanted result easily.
58

---

K Discussion on Discrete-Supported Contexts
In this paper, we considered only context distributions with differentiable densities.
Sinale-Parameter Linear Contextual Bandits. To the best of our knowledge, no study has addressed the greedy algorithm for linear contextual bandits with discrete-supported stochastic contexts.
Multiple-Parameter Linear Contextual Bandits. For multi parameter linear contextual bandits, Bastani et al. [8] proved that the Gibbs distribution, which has discrete support, satisfies the mar- gin condition and their diversity condition, achieving logarithmic regret for the greedy algorithm. However, their proof applies only to the two-arm case.
We assert that, for the K Karreed multi parameterr linear contextual bandit with K > 3, Gibbs distribution can fail under the greedy policy, For example, the two-dimensional Gibbs distribution has support points (1,1), (1, (1, 3 = (1, 32 (1,-1), (-1,1), the diversity assumption of Bastani et al. [ is violated.
However, if three parameters are given as
We further claim that for parameee linear contextual bandits, the effectiveness of discrete- supported contextual bandits with an arbitrary number of arms K has not yet been thoroughly studied.
L Dicussions, Limitations and Further Ideas
Since our LAC class primarily includes differentiable densities, examining the performance of the greedy bandit with discrete valued contexts would be valuable future direction. For discrete valued contexts, the only existing result by Bastani et al. [8] establishes performance for Gibbs distribution in a 2-arm (shared-context) bandit, but this generally fails when 2 3 and also it differs somewhat from our setup. In our setup, linear contextual bandit, no results are currently known for discrete contexts. Given that Bastani et al. g studied a shared contexts setup, our work represents the largest class of distributions for which the greedy bandit shows efficient performance in the linear contextual bandit problem.
To derive the concentration of minimum eigenvalue, the boundedness of contexts (random variables) is required. However, for heavy tail contexts, the upper bound of the contexts' norm can be large, so it leads to poor concentration. Dealing with non-truncated heavy tail contexts can be another interesting problem.
M Numerical Experiments
We conducted numerical experiments evaluate the performance of the greedy algorithm and compare it with existing bandit algorithms, LinUCB from Abbasi- Yadkori et al. [ and LinTS from Agrawal and Goyal
44. We conducted experiments for three cases with varying parameters: d = 20, K = 20, T' < 1000, d = 100, K = 20, < 1000, and d = 20, K = 100, T' < 1000, and five different distributions of contexts: Uniform in ball, truncated Student's t, Laplace, Gaussian, and exponential. The experiments were repeated 10 times for each case, and the deviation was also displayed on the graph.
We note that the results were obtained as vd times larger than the actual size because of the absence of dimensional correction. For the uniform distribution, used (B. Vd)). The Laplace contexts were generated by independently sampling each component of Laplace distribution with parameters μ. b,b 1. The Gaussian context was created so that each element of the feature vectors was drawn from a multivariate Gaussian distribution with a covariance matrix V with V2, = and Vi 0.7 for any + j. The truncated Cauchy contexts were generated by independently sampling each component from truncated Cauchy with loc 0, scale 1 and truncation range 5,5,5] 5].
In most cases, the greedy algorithm produced the best results. Our theory predicted polynomial scale dependency on dimension for the regret of the greedy algorithm, and the experimental results
Further details discrete contexts in Appendix K
59

---

confirmed good performance even with an increased dimension. This discrepancy is due to the fact that we considered the worst case. The experimental results for the three cases are listed.
d=20,
400
LinUCa
LinUCR
Regret
LinGreedy
300
LinGreedy
100
150
50
50
200
800
1000
800
1000
d'=00. K=20, Laplace
d'=00. Km20, Truncated Cauchy
350
LinUcB
LinUCB
300
LinTS
LinTS
LinGreedy
LinGreedy
250
200
150
100
50
0
0-
0
200
400
600
800
1000
0
200
400
600
800
1000
Round
Round
Figure 17: Results For d = 20, K 20
d=200, K=100, Guassian
d0 K- 100, Uniform
LinUca
500
LinUca
250
LinT's
LinT5
LinGreedy
400
LinGreedy
200
100
0
0-
0
200
400
600
800
1000
0
200
400
600
800
1000
Round
Round
d=20,, 100, Laplace
d-20, K=100, Truncated Cauchy
LinUCB LinTS
LinUCB LinTS
400
LinGreedy
LinGreedy
300
300
Cumulative
200
0-
0-
200
400
600
800
1000
200
400
600
800
1000
Round it)
Round it)
Figure 18: Results For d = 20, K
100
We used jupyter notebook the experiments.
60

---

d--100, 2-20, Guassian
d-100. K-20, Uniform
LinTS
800
LinTS
400
LinGready
LinGready
600
Curulative
200
400
200
0-
0
200
400
600
800
1000
0
200
400
600
800
1000
Round (t)
Round (t)
K-20, Laplace
d-100, K=20, Truncated Cauchy
LinUCB
1000
LinUCB
1000
LinGreedy
000
LinGreedy
000
600
200
1000
Round
Round
Figure Results For d 100, K 20
N
Technical Lemmas
Lemma 22 (Gronwall Inequality) For g(v) TR satisfies
g' ((()) 2 -M in [v.y + h), then
g + h)
exp(- exp(-Mh).
9(v)
Proof See classic PDE books like Evans [16].
N.1 Concentration Inequalities
Lemma 23 (Matrix Chernoff Adapted Sequence from (36)) Consider a finite adapted sequence
} with filtration (Fihezo of positive-semi definite matrices with dimension d, and suppose that
Amax (Xx) < R almost surely.
Define the finite series
Y === Xx and W = Σ k
E Xx
b
For all 2 0
e-
u/R
P (mmin (Y) (1-8)pp and Amin (W) 2 m} d.
for 8 [0,1]
(1 8)1-8
Corollary 9 (Eigenvalue Growth of Adaptive Gram Matrix) If Amin (EX, He-1)) 2 No, then with probability dexp(-ec
|Xill2
Tmax and
Fmax
Ao
Amin
X,X, 2
i=1
holds for some absolute constant C1-
61

---

Proof Put d = 3 i /1 Aot, R = Fmax at the Lemma 23
Lemma 24 (Theorem 1 from 11) Let (Fttz be filtrationn Let {Tt) be real-valued stochas-
tic process such that qi is Fe-messurable and q is conditionally R-sub-Gaussian for some z Le.
(12R²
EEER E E Am Fi-1 S exp
2
Let {Xt]e=1 be an -vauud stochastic process such that X₂ is Fi- fe-i-mbasuralle. Assume that V is d d positive definite matrix. For any 2 define
V.=V+ Σ X,X! S, Σ NxN.-
Then, for any 8 > O, with probability at least 1 8. for all t 2 0,
det (V.) 1/2 det ( (V)
| S 2R log
Lemma 25 (Lemma 10 from 1 Suppose X1, X2...., X, E Rdd and any st 1x,12
L. Let V. = AT + >==1 X, X,X, for some À > 0. Then,
det (V,) +
62

---

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]
Yes, we think our abstract and introduction well reflect the whole paper's contributions.
Justification:
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 not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We wrote in Appendix L
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]
63

---

Justification:
Yes, we state whole assumptions and provide rigorous proofs.
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 referenced in 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 to provide short proof sketch 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 be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We fully provide informations about experiments in Appendix M
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is 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 is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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 all 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 clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, 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 to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
64

---

Answer: [Yes]
Justification:
We provide code in supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc) public//uides//odeeuuiie www.lbiiissooooooooooioo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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:
/ //ipps.cc/pblli/guideee Saaelee//ooSSeebisssceeeee
for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: Yes, we provide whole details in Appendix M
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, we provide whole details in Appendix M
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, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
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).
should be clear whether the error bar is the standard deviation the standard error of the mean.
65

---

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 enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, provide whole details in Appendix M
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 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 or failed experiments that didn't make 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 httppp/s//uuuusss..ppooocchhhhaa
Answer: [Yes]
Justification: Yes, checked.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, include them in Introduction and Appendix L
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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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
66

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as 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 or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not relevant.
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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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: Not relevant.
Guidelines:
The answer NA means that the paper does not 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 is used and, if 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 (c.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 the package should be provided. For popular datasets, paperswitthode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
67

---

Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part 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 an anonymized URL or include an 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: Not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, 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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not relevant.
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 expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
68


Reviews:
[{"review_id": "hWlPAGokV0", "reviewer": "Reviewer_Lk9D", "summary": "The paper addresses the problem of linear contextual bandits with randomly generated contexts from a distribution \n$f$. The goal is to determine under which conditions on $f$ a greedy algorithm (outlined in Algorithm 1) achieves reasonable regret.\n\nBy introducing the notion of Local Anti-Concentration (LAC) in Definition 1, the authors demonstrate that if $f$ satisfies the LAC condition, then the greedy algorithm achieves poly-logarithmic regret. The LAC condition encompasses a wide range of distributions, such as Gaussian, uniform, Laplace, and Student’s t-distribution, making the results of the paper general and applicable across several frameworks.", "questions": "1. I would like to know the authors' thoughts on the necessity of the LAC condition. While the paper's focus is on showing that the LAC condition is sufficient, I am curious if there are significant distributions that do not satisfy the LAC condition but for which the greedy approach still achieves poly-logarithmic regret.\n\n2. In line 269, the authors mention, \"Eq.(3) is a relaxed version of the margin condition\" and \"The aforementioned existing literature explicitly assumes the condition to hold.\" Does this mean that the margin condition imposed in previous works can be dropped and relaxed to provide a bound on Eq.(3)?\n\n3. I would appreciate it if the authors addressed my question in the weaknesses section.", "limitations": "The authors adequately address the limitations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and addresses a very interesting problem. It makes a significant contribution by covering a large family of distributions for the contexts and demonstrating that, for this wide range, a greedy algorithm can achieve poly-logarithmic regret. The main results, Theorems 3 and 4, are noteworthy and can be of independent interest.", "weaknesses": "The only weakness I see is the lack of discussion about the optimality of the achieved regret concerning the parameters of interest, i.e., \n$d$ (dimension of the context), \n$K$ (number of arms), and $\\alpha$ (the parameter associated to the LAC condition). While the authors addressed this by stating, \"Our focus here is not solely on attaining the sharpest regret bounds, although achieving poly-logarithmic regret is highly favorable,\" it would have been beneficial to discuss this matter in more detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for recognizing the value of our results. We appreciate your feedback and are happy to provide our responses to your comments.\n\n---\n**[W1]**\nIn order to validate optimality of contextual bandit algorithms under stochasticity, we need to derive proper lower bounds. However, existing studies ([7, 8, 5, 15]) that have examined poly-logarithmic regret under margin conditions (similar to our paper) have not discussed lower bounds or optimality either. \nOne caveat is that since the greedy algorithm is not adaptive, the dimensionality and $K$ dependence can vary depending on context distributions. In such cases, deriving distribution-dependent lower bounds would be meaningful to determine optimality. However, we conjecture that such an analysis would be quite challenging. \nNonetheless, it would be an interesting future direction to provide a lower bound under the margin condition, not just for greedy bandit algorithms but for linear contextual bandits in general.\n\n---\n**[Q1]**\nIn short, to our best knowledge, the distributions that satisfy LAC are currently the only ones proven to be admissible for greedy algorithms! Typical cases where LAC is not satisfied include: \n\n1. Fixed or discrete context distributions.\n2. Low rank or nearly low rank contexts.\n\nIn case 1, it is known that the greedy algorithm fails for fixed contexts. In case 2, it is known that logarithmic regret is impossible [25]. \nAdditionally, for distributions with double exponential density (e.g., Gumbel distribution), LAC is not satisfied. However, with slight modifications, it might be possible to show a sublinear regret bound, but we are unsure how tight the bound can be (we do not know whether poly-logarithmic regret would be possible). It is very important to note that our work significantly expands what has been known to be admissible for greedy algorithms.\n\n---\n**[Q2]**\nPrevious literature **assumes** the existence of a constant satisfying the margin condition and regards it as a **fixed** constant. However, we **derive** the upper bound of the margin constant from the LAC density. \n\nWe emphasize again that we **do not assume** the existence of the margin constant. For example, many previous studies [7, 8, 5, 15] assume that there exists $C_\\Delta$ satisfying:\n$$ \\mathbb{P}[X_{a^\\star}(t)^\\top \\theta^\\star - \\max_{i \\neq a^\\star} X_{i}(t)^\\top \\theta^\\star \\leq \\varepsilon] \\leq C_\\Delta \\varepsilon. $$\nWith this margin assumption, one can achieve logarithmic regret. However, our paper calculates and estimates the margin constant $C_\\Delta$ from scratch, only assuming the densities of contexts are LAC.\n\nAlso, note that if the above holds, then our equation of the margin condition (equation (3)) holds directly. Hence, our version of the margin condition is weaker. More importantly, we **do not even impose such an assumption** to start with! Instead, we prove that distributions in LAC automatically satisfy the margin condition which is a significant contribution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DYe06as5qn", "reviewer": "Reviewer_qUQr", "summary": "The paper proposes a novel condition for context distribution, called *Local Anti-Concentration (LAC)*. Under LAC, the authors prove the regret of greedy algorithms for stochastic contextual linear bandits is $\\mathcal{O}(\\mathrm{poly} \\log T)$, without additional margin assumption. The efficacy of the greedy approach for various distributions is validated numerically as well.", "questions": "- Is LAC necessary for the polylog(T) regret of the greedy algorithm, or at least close to it? In other words, if the distribution is not LAC, does greedy always fail? I would be curious to see the numerical performance of greedy algorithms for distributions that are not LAC.\n- Does this work for generalized linear bandits as well? How about generally structured bandits (although this seems quite unlikely) and kernelized linear bandits (this, I have no idea)?\n- There was an interesting paper [1] in which, for linear bandits with a rich (continuous) action set, sublinear regret *implies* a lower bound on the minimum eigenvalue of the design matrix. Of course, in this case, the margin doesn't make sense, and there is a $\\Omega(d\\sqrt{T})$ regret lower bound, but as this paper and [1] are conceptually similar (to my eyes), would the greedy algorithm achieve $O(d\\sqrt{T})$ regret? Even if not, it would also be nice to include some discussions regarding this in the paper.\n- (minor) \n\n\n\n[1] https://proceedings.mlr.press/v206/banerjee23b.html", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Clearly, very well-written\n- Clear-cut contributions that significantly improve greedy algorithms for contextual linear bandits, including a provably larger class of context distributions that can achieve $\\mathcal{O}(\\mathrm{poly} \\log T)$ regret without additional margin condition and other technical contributions.\n- Numerical verification", "weaknesses": "- The authors should provide (possibly not-to-far-fetched) distributions in which the LAC fails.\n- The initial parameter $\\theta_0$ is mentioned briefly but not much discussed. What is the dependency of the regret on $\\theta_0$? How was $\\theta_0$ chosen for the experiments? In practice, should one choose $\\theta_0$ randomly, or is it okay to fix it? I feel this plays an important role, as the initial \"exploration\" (til the diversity becomes positive) heavily depends on $\\theta_0$.\n\n\n**(Minor) Typography suggestions**\n- Some of the sentences in Section 1.2 overlap with those in the paragraph above Section 1.1. I think it would be more appropriate if Section 1.2 is absorbed into the beginning of Section 1, and Section 1.1 becomes a paragraph (\\paragraph{..})\n- The pseudocode in Algorithm 1 seems wrong...? the while loop should be an If-Else.\n- In pg. 6, \"Consider the desnity\" -> \"Consider the density\"\n- If accepted, the authors should include the full regret bound from Appendix B.3 in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for recognizing the value of our results. We appreciate your feedback and are happy to provide our responses to your comments.\n\n\n---\n**[W1]**\nWe are happy to address your comment and assure you that this should not be considered a weakness. Context distributions with discrete support, particularly fixed contexts, do not satisfy the LAC condition. However, for such distributions, the greedy algorithm fails (i.e., the greedy algorithms can incur linear regret) in the worst case. To the best of our knowledge, the LAC condition is the most inclusive condition for greedy algorithms to succeed. This is a crucial finding!\n\nFor further details, please read Appendix M, which contains a detailed discussion on this matter. We would be more than happy to elaborate on this. More details are also discussed in the answer to **[Q1]**.\n\n---\n**[W2]**\nOur algorithm and regret bound are valid regardless of the choice of $\\theta_0$ as long as it is bounded (and we have the freedom to choose a parameter with an adequate bound). Note that we can show that the minimum eigenvalue of the gram matrix selected by the greedy policy increases linearly with time for any $\\theta_0$. Hence, we can derive the same regret bound. We will include this discussion in the revision.\n\n---\n**[Q1]**\nLAC is a sufficient condition, not a necessary condition. However, we do not know of any distributions (yet) that do not satisfy LAC but allow poly-logarithmic regret for greedy algorithms. There are good examples of distributions that are not LAC where greedy algorithms fail (or cannot achieve poly-logarithmic regret).\n\nFirstly, it is well known that the greedy algorithm can fail in the worst case when contexts are fixed. Another example where LAC does not hold is a context distribution supported in a low-rank space. In this case as well, it is known that logarithmic regret is impossible [25], and we are not aware of the success of the greedy algorithm to the best of our knowledge. It is very important to note that our work significantly expands what has been known to be admissible for greedy algorithms. LAC is the most general condition currently known to allow greedy algorithms to achieve poly-logarithmic regret.\n\n---\n**[Q2]**\nYes, our analysis extends to the GLM bandit as well for regular link functions as long as the link function has a bounded first derivative, which is commonly assumed in GLM bandit literature [14, 23]. As long as the concentration of the estimator is controlled by the gram matrix, most of the analysis is similar.\n\nIn the case of the kernelized bandit, it can be expressed in the form of a linear contextual bandit through the RKHS formulation. However, it usually assumes eigenvalue decay, so the minimum eigenvalue can become arbitrarily small. Hence, it might be difficult to apply the same analysis but would be an interesting future direction. So far, we have not even known what was possible for linear contextual bandits. Extension to other parametric bandits or kernelized bandits would be interesting.\n\n---\n**[Q3]**\nWe appreciate your pointer to this related work. While the paper shares some common points of addressing the minimum eigenvalue of the gram matrix, our analysis significantly differs in that one of the key ingredients of our analysis is ensuring that the minimum eigenvalue of the gram matrix increases linearly (whereas in theirs it isn't). Furthermore, ensuring the margin condition from scratch is a key step that is not addressed in the reference you provided. However, analyzing the (though not logarithmic but some sublinear) performance of the greedy algorithm within the setup of the referred paper would be an interesting direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "us9aDsgfy6", "reviewer": "Reviewer_PGWV", "summary": "This paper aims to expand the range of distributions that can be used efficiently in exploration-free greedy linear contextualized bandits. For this purpose, a new condition called Local-Anti Concentration is introduced. It is claimed that different distributions from the exponential family satisfy this property and they do not require the margin property to achieve $O(poly logT)$ regret.", "questions": "- 352: LinTS and LinUCB algorithms are show in the Figures in the Experiments Section. However, it is unclear what these algorithms are. Were they designed by the authors or are they the work of other researchers? In 1444, they are stated as existing bandit algorithms. If so, please provide the appropriate references.\n\n- 246: What do the authors mean by if two challenges are “satisfied”? Do you mean “overcome”?", "limitations": "- Technical contribution: The most significant proof, which is the proof that the given distributions satisfy the LAC condition, was left out.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "For the Gaussian, the authors show that LAC condition holds. Hence, they show an improvement in the regret without assuming any margin condition.", "weaknesses": "1. 89, 264: It’s unclear what the entries of this Gram matrix represent.\n\n2. 24-25: It’s not explained why healthcare and clinical domains might find exploration infeasible or unethical.\n\n3. 57: The specifications of margin condition are not explained.\n\n4. Even though there are experiments in the paper, in the guideline the answer to the question 5 is marked as N/A. It's unclear whether the code belongs to the authors or another researcher and hence, the answer. If the code belongs to the authors, the answer should have been YES or NO. \n\n5. Lines 63 to 67 are repeated word for word in 106 to 109, except for the addition of the word \"bandit\". Please delete one of these sections.\n\n6. 120: It is not clear on what D and B are supposed to be. The authors can add the word \"sets\" to be more clear.\n\n7. 526-540: Appendix C.1 is not written extensively; the proof is provided only for the Gaussian distribution.  This is the main contribution of the paper as stated in 91-92 and used in different places such as 311. Without the proof, it’s unclear how well the rest of the statements for the distributions hold.\n\n8. 490: There is a typo as these algorithms are stated as linTS and linUCB instead of LinTS and LinUCB.\n\n9. 114: There is another typo: \"unecessary\" should be \"unnecessary\".\n\n10. 352: Experiment results are not discussed extensively, making it hard to understand how the experiments support the claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and for the opportunity to discuss our work with you. Most of your feedback appears to be clarifications and suggestions for stylistic edits or minor typos, which we appreciate. However, none of your comments seem critical enough to warrant a rating of \"Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility, and/or incompletely addressed ethical considerations.\"\n\nHence, we sincerely ask for a re-evaluation of our work. We strongly believe that the significance and impact of our results are very high, significantly expanding what had previously been known and doing so at a very timely moment. And, please let us know If you have any remaining questions.\n\n---\n**[W1]** The definition of the Gram matrix is $\\Sigma(t):=\\sum_{s=1}^t X_{a(s)}(s)X_{a(s)}(s)^\\top$ and is stated in Algorithm 1. Readers of the linear bandit literature are familiar with this term, but we will provide the formal definition of the Gram matrix earlier in the text.\n\n**[W2]** In healthcare, if a healthcare provider treats a patient with what appears to be sub-optimal (non-greedy) just for the purpose of exploration to learn the effect of a new treatment (not for the benefit of the particular patient being treated), it would be clearly unethical or often not feasible in actual healthcare practices (beyond clinical trials). This aspect has been discussed in various previous literature, including [8].\n\n**[W3]** The exact definition of the margin condition is stated in Challenge 2 (line 266).\n\n**[W7]** (LAC examples)\nFirst, we prove results in line 195. For exponential, Laplace, and Student's t, we prove results for 1-dimensional distribution. However, using Proposition 1, we can extend this to multi-dimensional contexts.\n\n* Exponential: $\\nabla \\log f(x) = -\\lambda $ and hence $| \\nabla \\log f(x) | \\leq \\lambda$.\n* Uniform: $\\nabla \\log f(\\mathbf{x}) = \\mathbf{0}$ and hence $||\\nabla \\log f(\\mathbf{x}) ||_\\infty \\leq 1$. (multi-dimensional)\n* Laplace: $f(x) = \\frac{1}{2 b} \\exp \\left(-\\frac{|x-\\mu|}{b}\\right)$ and then $|\\nabla \\log f ({x})| = |\\frac{1}{b}|$.\n* Student's t: $f(x)= \\Gamma\\big(\\frac{\\nu+1}{2}\\big) / \\sqrt{\\nu \\pi} \\Gamma\\big(\\frac{\\nu}{2}\\big) \\cdot \\big(1+\\frac{x^{2}}{\\nu}\\big)^{-(\\nu+1)/2}$ then $|\\nabla \\log f(x)|=|\\nabla \\frac{\\nu +1}{2}\\log(1 + \\frac{x^2}{\\nu})| = \\frac{(\\nu+1)x}{\\nu + x^2}\\leq C(\\nu)$ for some constant $C(\\nu)>0$.\n\n**[W10]** Our experiment demonstrates that a greedy algorithm clearly outperforms other widely used algorithms (LinUCB and LinTS) that balance exploration and exploitation for common distributions. It appears that for those distributions, any type of exploration is unnecessary -- greedy algorithms suffice, which is the main assertion of this paper. Due to space constraints, the discussion is provided in Appendix N.\n\n**[W4-6, 8-9]** Thank you for pointing out typos and stylistic suggestions. We will incorporate the appropriate edits suggested by the reviewer.\n\n---\n**[Q1]** LinUCB and LinTS are the most widely used linear contextual bandit algorithms. The LinUCB algorithm follows the paper by Abbasi-Yadkori et al. (2011), and the LinTS algorithm follows the paper by Agrawal and Goyal (2013) to conduct the experiments.\n\n**[Q2]** We mean that if the two challenges regarding the context distribution are satisfied, i.e., if two key constants exist, logarithmic regret can be achieved.\nHowever, to get the exact upper bound, rather than proving existence of the constant bounding the two constant is essential, and we discuss this throughout the whole paper.\n\n**[Details for two challenges and regret]**\nThe following part breifly describe how to challenges can make logartihmic regret.\n\n*Challenge 1: $\\sqrt{t}$-rate $\\ell_2$ concentration*\n\nFirst Challenge can lead the $\\ell_2$ statistical resolution of the estimator.\nUnder the Challenge 1, we can get\n$$\n|X_{a(t)}^\\top (\\hat{\\theta}_{t-1} -\\theta^\\star)| \\leq c x_{\\max} \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_{\\star} t}}, \\quad\n|X_{a^\\star(t)}^\\top (\\hat{\\theta}_{t-1}-\\theta^\\star)| \\leq c x_{\\max} \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_{\\star} t}}\n$$\nholds with high probability.\nHere, $c = \\tilde{O}(1)$ constant.\n\nHowever, this resolution in insufficient for the logarithmic regret, it can only get $O(\\sqrt{T})$ regret bound.\n\n*Challenge 2: Logarithmic regret*\n\nBut with the help of the Challenge 2 (margin condition), we can get logarithmic expected regret upper bound.\n\nWhen the greedy policy select $a(t)$, it means that\n\\begin{align*}\nX_{a(t)}(t)^\\top \\hat{\\theta}_{t-1}  \\geq X_{a^\\star(t)}^\\top \\hat{\\theta}_{t-1}\n\\end{align*}\nand by the definition of the optimal arm,\n\\begin{align*}\nX_{a(t)}(t)^\\top \\theta^\\star \\leq X_{a^\\star(t)}^\\top \\theta^\\star\n\\end{align*}\nholds.\n\nUnder the Challenge 1, we get\n\\begin{align*}\n\\operatorname{reg}'(t):= X_{a^\\star(t)}(t)^\\top \\theta^\\star-  X_{a(t)}(t)^\\top \\theta^\\star \\leq 2cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}.\n\\end{align*}\n\nNext, we define the event $E$ as the event of $\\mathbf{X}(t)$ with regret occurring as $\\operatorname{reg}'(t) > 0$.\nUnder the event $E$, the suboptimality gap of $\\mathbf{X}(t)$ satisfies\n\n\\begin{align*}\n\\Delta(\\mathbf{X}(t)) \\leq   \\operatorname{reg}'(t) \\leq 2cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}\n\\end{align*}\nand by the Challenge 2, we get\n\\begin{align*}\n\\mathbb{P}[\\operatorname{reg}'(t) >0] \\leq 2c x_{\\max}C_{\\Delta}  \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}} +  \\frac{1}{\\sqrt{T}} \\leq 3cx_{\\max}C_{\\Delta} \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}\n\\end{align*}\nBy combining two things, we can bound the expected regret as\n\\begin{align*}\n\\operatorname{reg}(t) &= \\mathbf{E}[\\operatorname{reg}'(t)] \\leq 3cx_{\\max}C_{\\Delta}  \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}} \\times 2cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}\\\\\n&= 6c^2x_{\\max}^2 C_{\\Delta} \\frac{d}{\\lambda_\\star t}.\n\\end{align*}\n\nUsing this argument, our only remainning goal is bounding two constants in Challenge 1 and 2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZpzVL6l6xG", "reviewer": "Reviewer_Fhbd", "summary": "This paper analyzes a Greedy bandit algorithm, in the context of a linear bandit problem where (1) a regression parameter is unknown and fixed for the experiment and (2) the $K$ arms from which the decision-maker can choose are sampled at the beginning of each step $t$, from a fixed context distribution. Recent works have shown that in similar problems exploration is not necessary, and greedy algorithms are sufficient to achieve satisfying theoretical guarantees. This observation is interesting because (1) some standard methods like UCB can be costly in linear bandits, and (2) in some settings exploration might be controversial, since it might imply not acting optimally with the knowledge at hand with consequences on living subjects. \n\nThe authors first propose a generic condition on the context distributions, called the LAC condition, under which they analyze Greedy. They then describe the two main statistical challenges needed for the analysis, before presenting poly-logarithmic regret guarantees under bounded context distributions. Finally, they showcase experiments that validate their approach, advocating for the use of Greedy to tackle the linear bandit problem that they consider.", "questions": "* The LAC condition implies a mode of the context distribution in zero, and some flatness around $0$. I am wondering how instrumental is this property to guarantee the implicit exploration of Greedy and the not-too-small sub-optimality gap. For instance, with a Gaussian in mind, do the guarantees generalize if we assume the existence of a mode and shift the condition to be on the norm of $x-a$ for some vector $a$? The adaptation does not seem direct to me because sampling around $0$ facilitate that diverse directions are sampled, making the gap emerge.\n\n* Could you be provide some justification of the settings, i.e. some applications where it would make sense to assume that $K$ arms are drawn i.i.d from a context distribution at each time step, with independence between steps? \n\n* What is special about unbounded context that make it relevant to keep the distinction in the paper? \n\n* The dependency in $t$ in challenge 2 looks fishy to me: I don’t see why the probability bound should depend on $T$ (or 1): the probability only depends on the context distribution and K, so the bound should only depends on $\\epsilon$. Furthermore, by independence the same bound should hold for all $t$. Am I missing something? In addition, assuming the result is true, how is the $1/\\sqrt{T}$ shaved off in the analysis? Because I would assume that the regret analysis would consist in multiplying the error by $T$ under the case the event does not hold.\n\n* Additional related question: what $\\epsilon$ is used in the analysis?", "limitations": "Not applicable", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "First, for the reasons mentioned in previous paragraph, I believe that Greedy algorithms work in some learning settings and understanding their properties is an interesting research question. It is true that, with the development of powerful tools like optimism or Thompson Sampling, we tend to jump on these methods to tackle every bandit problem without necessarily questioning whether their exploration mechanism is necessary or not. Hence, this line of work is in my opinion interesting to recall that simple methods should be tried first before moving to those more elaborate tools.\n\nThen, the authors put a lot of efforts in describing and providing intuitions on the two statistical challenges posed by their problem, namely the positivity of the eigenvalues of the design matrix (i.e. the implicit exploration of greedy), and the fact that randomly sampling contexts guarantee relatively large sub-optimality gaps at each time step. These two challenges are the key ingredients to derive the poly-logarithmic regret guarantees for the greedy algorithm proposed by the authors. Furthermore, the LAC condition is well-described and rather intuitive.", "weaknesses": "Edit: after reading the rebuttal and discussing with other reviewers I decided to increase my score \n______________________________\n\nIn my opinion, the first weakness is the setting itself. Other works in the literature seem to tackle two settings: the one presented in the paper, and another one which actually seems to be the main setting of the other works, in which the arms are fixed but the regression parameter is sampled at each round. This second setting looks more natural to me: the arms are fixed but their performance vary according to external environmental factors, eventually making each of them optimal in some context. I can see the applications of this setting, but I cannot see the applications of the setting presented in the paper.\n\nThen I believe that, although the main paper is not very technical, the presentation makes it difficult to grasp the main technical insights of the analysis. Many arguments are discussed but not properly sketched, and it is hard to precisely correlate the two « challenges » with the actual regret analysis. I decided to check the proof of the regret bound in appendix, and then things got even worse: the appendix is so badly organized that it requires at least 4 screens to check any single results, due to no clear proof scheme and various technical results spread everywhere. Overall, after considerable efforts I did not succeed in understanding precisely how each result is used in the regret analysis. I would suggest the authors to re-organize the paper by properly writing the regret analysis, and along the analysis pointing out how the main technical results are used, that would themselves be properly proved in dedicated sections. In appendix their should not be proof sketches but rigorous proofs, and discussions about intuitions should be clearly separated from the proofs. Furthermore, the unbounded context case seems to be tackled in an extremely complicated way. I do not get the point of this, it does not even seem important in the main paper, maybe tackling the bounded case only would be sufficient and remove some confusion. Second, I do not get why the authors do not eventually use the proof for bounded context with $x_{max}=O(polylog(T))$, which is eventually true with high probability with light-tailed contexts.\n\nOverall, it seems to me that the paper requires significant re-writing to (1) make the proofs rigorous and easy to check (or even just that an expert non-author reader might be able to check them), (2) clarify the contributions by focusing on precise interesting cases,  (3) more precisely linking the « challenges » with the regret analysis. Furthermore, the setting appears as artificial in the current version of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank the reviewer for taking the time to review our paper and for the comments. However, we believe there is a fundamental disagreement between the reviewer's comments and the focus of our study. We hope to remedy this through open-minded discussion. We strongly believe and remain very confident that our work presents significant values and very important results that advance the existing knowledge about greedy algorithms in contextual bandits.\n\n---\n**[W1]**\nWith all due respect, we are very concerned that the reviewer does not even agree with the stochastic context setting and suggests a new setting (the reviewer thinks it \"looks more natural\") where features are fixed but the parameter is sampled. Then, this leads to the reviewer's conclusion that our contribution should be somehow discounted, which we believe is an unfair evaluation.\n\nThis is problematic because **all of the existing greedy contextual bandit literature so far has been proposed under stochastic contexts, focusing on how such stochasticity in context allows for greedy algorithms to achieve sub-linear regret** [8, 16, 25, 28]. In fact, the previous literature focused only on very few distributions (e.g., Gaussian and uniform), as we state in the paper, which our work significantly expand and even achieve much smaller regret.\n\nSuch a comment not only **rejects the entire literature on greedy contextual bandits** but also **raises concerns about whether our work can be adequately evaluated compared to the existing results** if the problem setting itself is disregarded. \nOur work significantly expand the set of context distributions admissible for greedy bandit algorithms, which has been an open question among many researchers.\n\nThere is a rich history of contextual bandits with stochastic contexts even beyond the greedy bandit literature [5, 8, 15, 16, 25, 28]. We hope for a fair re-evaluation based on the established and widely accepted problem setting compared to the relevant literature within the field. \nPlease do not take this personally; we ask that the reviewer put themselves in the authors' shoes and consider whether there is any meaningful feedback to be gained from a comment that discredits the problem itself and disregards the entire history of research on greedy contextual bandits (and somehow hope that the authors' hard work can evaluated fairly). This is the main problem setting that all relevant literature has been working on. We respectfully but strongly dispute this point.\n\n---\n**[W2]** \nFirstly, we strongly disagree with the reviewer's statement that \"the main paper is not very technical.\" We are unsure how our results and analysis could be perceived as \"not very technical\" to begin with. While we appreciate the feedback on improving the presentation in the appendix and will incorporate appropriate edits, we feel that the assertion that our paper is \"not very technical\" is unfounded. Throughout our paper, we present rigorous analysis and stronger results than what has previously been known in the literature.\n\nDespite the disagreement, we are more than happy to provide a proof sketch—some details are already presented in Appendix D, but here, we will present more thorough arguments. We first demonstrate how our two challenges can lead to logarithmic regret.\n\n*Challenge 1: $\\sqrt{t}$-rate $\\ell_2$ concentration*\n\nFirst Challenge can lead the $\\ell_2$ statistical resolution of the estimator.\nUnder the Challenge 1, we can get\n\\begin{align*}\n|X_{a(t)}^\\top (\\hat{\\theta}_{t-1} -\\theta^\\star)| \\leq cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}, \\quad\n|X_{a^\\star(t)}^\\top (\\hat{\\theta}_{t-1} -\\theta^\\star)| \\leq cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}\n\\end{align*}\nholds with high probability.\nHere, $c = \\tilde{O}(1)$ constant.\n\nHowever, this resolution in insufficient for the logarithmic regret, it can only get $O(\\sqrt{T})$ regret bound.\n\n*Challenge 2: Logarithmic regret*\n\nBut with the help of the Challenge 2 (margin condition), we can get logarithmic expected regret upper bound.\nWhen the greedy policy select $a(t)$, it means that\n\\begin{align*}\nX_{a(t)}(t)^\\top \\hat{\\theta}_{t-1}  \\geq X_{a^\\star(t)}^\\top \\hat{\\theta}_{t-1}\n\\end{align*}\nand by the definition of the optimal arm,\n\\begin{align*}\nX_{a(t)}(t)^\\top \\theta^\\star \\leq X_{a^\\star(t)}^\\top \\theta^\\star\n\\end{align*}\nholds.\nUnder the Challenge 1, we get\n\\begin{align*}\n\\operatorname{reg}'(t):= X_{a^\\star(t)}(t)^\\top \\theta^\\star-  X_{a(t)}(t)^\\top \\theta^\\star \\leq 2cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}.\n\\end{align*}\n\nNext, we define the event $E$ as the event of $\\mathbf{X}(t)$ with regret occurring as $\\operatorname{reg}'(t) > 0$.\nUnder the event $E$, the suboptimality gap of $\\mathbf{X}(t)$ satisfies\n\\begin{align*}\n\\Delta(\\mathbf{X}(t)) \\leq   \\operatorname{reg}'(t) \\leq 2cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}\n\\end{align*}\nand by the Challenge 2, we get\n\\begin{align*}\n\\mathbb{P}[\\operatorname{reg}'(t) >0] \\leq 2c x_{\\max}C_{\\Delta}  \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}} +  \\frac{1}{\\sqrt{T}} \\leq 3cx_{\\max}C_{\\Delta} \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}\n\\end{align*}\nBy combining two things, we can bound the expected regret as\n\\begin{align*}\n\\operatorname{reg}(t) &= \\mathbf{E}[\\operatorname{reg}'(t)] \\leq 3cx_{\\max}C_{\\Delta}  \\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}} \\times 2cx_{\\max}\\frac{\\sqrt{d}}{\\sqrt{ \\lambda_\\star t}}\\\\\n&= 6c^2x_{\\max}^2 C_{\\Delta} \\frac{d}{\\lambda_\\star t}.\n\\end{align*}\n\nUsing this argument, our only remainning goal is bounding two constants in Challenge 1 and 2.\n\n**[Bounded and unbounded contexts]**\nPlease see the [Q3] parts.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The fact that the greedy algorithm works well in practice when the contexts have regularity has been an interesting topic of research. Obtaining polylog(T) regret bounds for greedy algorithms in the past have relied on strong assumptions such as the margin condition. The authors did an excellent job in relaxing these assumptions. The newly introduced assumption has been specialized to various examples. I believe these altogether are great contributions towards fully understanding the role of context distribution in linear bandits, which has not been satisfactory in the contemporary literature.

Meanwhile, I recommend that the authors improve clarity and organization of the paper (in particular appendix) so that readers can appreciate the results and gain insight without checking all the details and the proofs.
Decision: Accept (poster)