Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit

Authors: seok-jin  kim
min-hwan  oh
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:58:58

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.

Main paper: 
 introduction: 
 In the contextual multi-armed bandit problem [2, 6, 24, 25] , an agent uses revealed contextual information in each round to 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 to design a sequential arm-pulling strategy to maximize cumulative rewards, necessitating a balance between exploration and exploitation. Linear contextual bandits, where expected reward is modeled as a linear function of contextual information, serve as the fundamental framework for contextual bandits [1, 10, 26] . Various exploration strategies, including upper confidence bound (UCB) [1, 11] , Thompson sampling (TS) [3, 4] , and ϵ-greedy [19] are widely used and studied in the theoretical analysis for linear contextual bandits. However, exploration can often be challenging in 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 decisionmaking systems.A greedy policy, i.e., pure exploitation without exploration, selects arms greedily based on current problem parameter estimates. While a 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 a 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 to 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 in the contexts (or the features of arms) -so that even with exploration-free action selection, parameter estimation is effectively possible. However, distributions known in the existing literature to allow efficient greedy algorithms are mostly limited only to Gaussian and uniform distributions [8, 20, 30, 33] . Hence, the following research questions arise.Is it possible for a wider range of distributions to allow efficient learning for greedy algorithms?If so, how can we characterize such distributions?We answer the above questions affirmatively by proposing a general distributional condition that allows for a broad range of distributions to achieve provable efficiency of greedy linear bandit algorithms. In this work, we present a new Local Anti-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 we 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 significantly 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-logarithmic O(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) Gaussian-distributed contexts could only yield O( √ T ) regret for greedy algorithms for single-parameter linear contextual bandits [20, 30, 33] ; (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 O(poly log T ) regret. 1 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 has rigorously examined the scaling of the margin constant, rather than simply treating it as a 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 1 ) induce O(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 as UCB and TS, for linear contextual bandits lies in the estimation bounds. While UCB [1] and TS [4] analyses involve bounding the weighted estimation error of the parameter using selfnormalized martingales, the analysis of greedy algorithms relies on the ℓ 2 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 a broad class of context distributions, √ t-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 √ t-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-a result derived from our analysis rather than assumed explicitly.The main contributions of our paper are summarized as follows:• We propose a novel condition, called Local Anti-Concentration (LAC) condition, for a greedy linear contextual bandit algorithm to achieve provable efficiency. The newly proposed Raghavan et al. [30] Gaussian O(T3 ) † Single parameter• Under our proposed LAC condition, we prove that the cumulative expected regret for the greedy algorithm is bounded by O(poly log T ) (Theorem 1), the sharpest known bound for greedy algorithms in linear contextual bandits with a single parameter.• By leveraging the proposed condition, we can guarantee both (i) the growth of the minimum 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 not 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.• Various context distributions have been empirically shown to allow favorable performances of greey algorithms (see Appendix L). However, the distributions previously known in the literature that enable efficient greedy algorithms were primarily limited to Gaussian and uniform distributions. Our theoretical results offer a 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.Linear bandits and generalized linear bandits have been widely studied [1, 2, 4, 6, 10, 11, 18, 23, 27, 32] . Upper confidence bound (UCB) algorithms for the linear contextual bandit have been proposed and analyzed for their regret performance [1, 6, 10, 11, 32] . Thompson sampling [35] algorithms for linear contextual bandits have also been widely studied, with results demonstrating their effectiveness 2 Preliminaries 
notations: 
 We use ∥x∥ p to denote the ℓ p -norm of vector x ∈ R d . For a positive definite matrix A ∈ R d×d , we define ∥x∥ A = √ x ⊤ Ax. We use λ min (A) to denote the minimum eigenvalue of the positive definite matrix A. We denoteD d R := [-R, R] d and B d R := {x ∈ R d : ∥x∥ 2 ≤ R}. If d is clear, we just write B d R := B R and D d R := D R .We define [n] for a set [n] := {1, 2, . . . , n}. We write S d-1 for a d-dimensional unit sphere. We set ∥X∥ ψ1 = sup p≥1 {p -1 E 1/p |X| p },∥X∥ ψ2 = sup p≥1 {p -1 2 E 1/p |X| p } for a random variable X. If X is a d-dimensional random vector, then we write ∥X∥ ψ2 = sup ∥u∥2=1 ∥⟨u, X⟩∥ ψ2 , ∥X∥ ψ1 = sup ∥u∥2=1 ∥⟨u, X⟩∥ ψ1 . We use the notation O() or ≲ to hide constants, and O() to hide constants and logarithmic terms. We use the notation a ≍ b when a ≲ b and b ≲ a. We use c, c 1 , c 2 . . . for absolute constant, which may differ from line by line.We consider the linear contextual bandit problem with K arms (K ≥ 2), where in each round t = 1, 2, . . . , T , the set of context vectors X (t) = {X i (t) ∈ R d , i ∈ [K]} is drawn from some unknown distribution P X (t). Each arm's feature X i (t) ∈ X (t) for i ∈ [K] need not be independent of each other and can possibly be correlated. The agent then pulls an arm a(t) ∈ [K]. Each context vector X i (t) for i ∈ [K] is associated with stochastic reward Y i (t) ∈ R with mean X i (t) ⊤ θ ⋆ where θ ⋆ ∈ R d is a fixed, unknown parameter. For simplicty, we assume ∥θ ⋆ ∥ 2 ≤ 1. After pulling arm a(t), the agent receives a stochastic reward Y a(t) (t) as a bandit feedback: Y a(t) (t) = X a(t) (t) ⊤ θ ⋆ + η a(t) (t), where η a(t) (t) ∈ R is a zero mean noise. We assume that there is an increasing sequence of sigma fields {H t } such that each η at (t) is H t -measurable with E[η at (t)|H t-1 ] = 0. In our problem, H t is the sigma field generated by random variables of the arms chosen {a(1), ..., a(t)}, their context vectors {X a(1) (1), ..., X a(t) (t)}, and the corresponding rewards {Y a(1) (1), ..., Y a(t) (t)}. Also, η a(t) (t) is assumed to be conditionally σ-sub-Gaussian, i.e., for all λ ∈ R, E[e λη a(t) (t) | H t-1 ] ≤ exp λ 2 σ 2 /2 for σ ≥ 0. Observing context vector X (t), let a * (t) denote the optimal arm in round t, that is, a * (t) = arg max i∈[K] X i (t) ⊤ θ ⋆ . Then the instantaneous expected regret (reg(t)) and cumulative expected regret (Reg(T )) are defined respectively asReg(T ) := T t=1 reg(t) := T t=1 E X a ⋆ (t) (t) ⊤ θ ⋆ -X a(t) (t) ⊤ θ ⋆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 is to minimize the cumulative expected regret.D := [-R 1 , R 1 ] d . 3. Define D v := P[D, v]. 
generality of lac condition: 
 We show that the LAC condition is applicable to 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 a polynomial scale. Included in the LAC class are distributions such as Gaussian, exponential, uniform, Student's t, 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 B 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 a suitable framework for comparing regret when both the number of arms and the dimension are large.Proposition 1 Suppose the random variable X = (X 1 , X 2 ), where X 1 ∈ R n1 and X 2 ∈ R n2 , consists of two independent components. If X 1 and X 2 satisfy the LAC condition with functions λ 1 (•) and λ 2 (•), respectively, then X satisfies the LAC condition with λ(x) = max(λ 1 (x), λ 2 (x)).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 ℓ ∞ norm, the expression decomposes perfectly. Using this proposition, the LAC condition remains robust across dimensions if the coordinates are independent, making it dimension-free in such cases. Furthermore, this condition is very accessible because it can be readily computed for a given density function. For many well-known exponential families, the exponential component of the density often scales polynomially.We present a few examples of known distributions satisfying the LAC condition. We provide rigorous proofs for the examples in Appendix B.• Gaussian distribution: For X = (x 1 , . . . x n ) ∼ N (µ, Σ), when Σ is diagonal, it satisfies the LAC condition with L(x) = If each coordinate's density independently adheres to one of the aforementioned distributions, according to Proposition 1, they all share the same LAC function irrespective of the dimension.Consider the density f (x) with f (x) ∝ exp(-V (x)) for some differentiable function V (x). If ∇V (x) has polynomial growth, i.e., is bounded by a polynomial, then the density f (x) meets the LAC condition. This holds because f (x) = C exp(-V (x)), ∇ log f (x) = ∇ log exp(-V (x)) = -∇V (x). If ∇V (x) exhibits polynomial-scale growth, then the supremum norm confirms that the LAC condition is satisfied.This observation makes the LAC condition easily verifiable for exponential family distributions with density forms f X (x|θ) = h(x) exp[η(θ) • T (x) -A(θ)], where the exponential part T (x) has polynomial growth. In many exponential family cases, T (•) indeed exhibits polynomial growth. Proofs and further details can be found in Appendix B. 
statistical challenges of greedy linear contextual bandits: 
 In this section, we outline the key statistical challenges in analyzing greedy algorithms for linear contextual bandits: (i) ensuring the diversity of the adapted Gram matrix (Section 4.1) 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 ⊤ 1 (t), . . . X ⊤ K (t)) ∈ R dK of X (t), which combines context vectors X i (t) for i ∈ [K]. We define X ij (t) as the j-th coordinate of the context X i (t).The first key challenge lies in ensuring sufficient ℓ 2 -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 1, if the minimum eigenvalue of the adapted Gram matrix λ min (Σ(t)) increases linearly with the number of rounds t, we can obtain the high probability ℓ 2 error bound ∥ θtθ ⋆ ∥ 2 with a convergence rate of O(1/ √ t) using martingale concentration [13, 29] . In fact, the growth of λ min (Σ(t)) is a necessary condition to obtain √ t-consistency of the estimator.However, estimating the covariance of the selected contexts X a(t) (t) is relatively challenging, as its distribution differs significantly from the overall distribution (before selection) of X(t). 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 λ min (Σ(t)) can be ensured for a broader class of distributions and what characteristics such distributions would need to satisfy.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:∆(X(t)) := X a ⋆ (t) (t) ⊤ θ ⋆ -max i̸ =a ⋆ (t) X i (t) ⊤ θ ⋆ ,which is determined by the true parameter θ ⋆ . We aim to bound this suboptimality gap probabilistically, as described precisely in Challenge 2 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 linear contextual bandit with stochastic contexts [7, 19] . A high-level description of the role of the margin constant in the regret bound is provided in Appendix C.1, with a rigorous analysis in Appendix I.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 a priori; rather, we will demonstrate that they are satisfied in the stochastic context under the LAC condition.In this section, we formally define these challenges to 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 2 (Diversity Constant) For a linear contextual bandit with contexts X(t) and history H t-1 , the diversity constant λ ⋆ (t) is defined as the value satisfyingEQUATIONfor all t > 0, where a(t) denotes the arm selected by the algorithm in round t.Then, the first challenge is to ensure a positive diversity constant λ ⋆ (t) > 0, which involves sufficient eigenvalue growth of the adapted Gram matrix. We explore this further in Appendix E.1.Challenge 1 (Positive Diversity Constant) Our goal is to ensure λ ⋆ (t) > 0.Achieving a positive diversity constant is challenging, as it requires analyzing the behavior of a context selected by the greedy policy in a 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 a 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 C ∆ (t), which holds under the given history H t-1 and for any ε > 0,EQUATIONWe also refer to this constant C ∆ (t) as the margin constant.Note that Eq. ( 2) is a relaxed version of the margin condition presented in [5, 7, 8, 19] . The aforementioned literature explicitly assumes this condition to hold. However, we instead show that the suboptimality gap can be bounded without directly assuming it (Section 5.3.2). Rigorously, C ∆ (t) depends on T , as it is a function of T . However, we emphasize that our algorithm does not require prior knowledge of T ; this dependency is needed only for the analysis.v 1 := (D v ) K . 5. Then ∥C v 1 ∥ ∞ ≤ R 1 + 2 holds.< l a t e x i t s h a 1 _ b a s e 6 4 = " i hX k r S X p K N b Y X 0 T M l / l K b S 2 n l o U = " > A A A G M X i c j V T L b h M x F H W B Q C m v F n a w s Y i Q W I y q T F U B U j e V 2 k r s + h B t U m W i y u P c S a x 4 b M v 2 t I m m + Q K 2 8 C V 8 T X e I L T + B J z M h H a d I W E p 8 c 8 6 5 v g / f O F a c G d t q 3 a z c u / + g 8 f D R 6 u O 1 J 0 + f P X + x v v H y z M h M U z i l k k v d i Y k B z g S c W m Y 5 d J Q G k s Y c 2 v F o r + D b l 6 A N k + K L n S j o p W Q g W M I o s Q 4 6 P r x Y b 7 Y 2 W 7 O F l 4 2 w M p q o W k c X G 4 3 X U V / S L A V h K S f G d M O W s r 2 c a M s o h + l a l B l Q h I 7 I A L r O F C Q F 0 8 t n m U 7 x O 4 f 0 c S K 1 + w i L Z + h t j 5 y k x k z S 2 C l T Y o f G 5 w r w L q 6 b 2 e R T L 2 d C Z R Y E L Q M l G c d W 4 q J s 3 G c a q O U T X D t R E B u z e H p X l M D t R Y 4 m m K d U U 8 0 y D z A I 1 w h N L A Q 4 4 Z L Y A A 8 0 U U N G x w E e S Q t u S 8 k I K H D u r I x b p u V V g J n o u / Y l T B v n Y b K Y E l V c h 5 c I H y g D m W u 2 7 M M S J T W z w 7 Q O D 1 2 l W k N S R z l T J v O U z t V K y c 3 U a 4 c r B p L A 3 e M l L J 0 z r 8 w / C a S G t F D X e x t 7 I f 9 V 5 r g c j R q m t J R e d E W 0 G T H l Q A F X V K Y p E f 0 8 O p j m U X F b c Z w f T D 3 u Z M G d + N z + / o L c 9 0 k 3 n o 7 d i d z 1 2 b z 4 g a M d 7 G m K B k 1 q K k w 4 v 0 v Z m U d K 8 o 4 f 6 X z B n S 9 l s e A S n 2 s v u L b P j R f c 2 O f S B Z f 6 H I n N t B v 2 8 o h D Y q + b Y a T Z Y G i v P Z X J l J A 6 v a U s v 3 E z x J V H t V 3 k E R O J n f h x 7 J X 8 7 x O 2 f G c l e d F 1 q Y o / n d T F w O Y z b D l N 5 e t m W K m r h j a X 5 T z m h / O 5 v M V R K f q s p P f + m j W F m 1 L 3 z L q e H l X G m n t N Q / / t X D b O t j b D D 5 v b x 9 v N 3 e 3 q X V 1 F b 9 B b 9 B 6 F 6 C P a R Z / R E T p F F A H 6 i r 6 h 7 4 0 f j Z v G z 8 a v U n p v p f J 5 h W q r 8 f s P b X d D B Q = = < / l a t e x i t >O < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 P N K g n M Z 6 D e Q e p c Q N k v h i u G w + W 0 = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h F m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N N E 0 X 8 A W v o S v 6 Q 6 x 5 S f w J B P S c Y q E p c Q 3 5 5 z r + / C N Y 8 W o s c 3 m z d r 6 v f u 1 B w 8 3 H m 0 + f v L 0 2 f O t 7 R f n R m Y 6 g b N E M q n b M T H A q I A z S y 2 D t t J A e M y g F Q 8 P C r 4 1 A m 2 o F F / s R E G X k 7 6 g K U 2 I d d D J 6 H K r 3 m w 0 Z w u v G m F p 1 F G 5 j i + 3 a 6 + i n k w y D s I m j B j T C Z v K d n O i L U 0 Y T D e j z I A i y Z D 0 o e N M Q T i Y b j 7 L d I r f O q S H U 6 n d R 1 g 8 Q 2 9 7 5 I Q b M + G x U 3 J i B 8 b n C v A u r p P Z 9 G M 3 p 0 J l F k Q y D 5 R m D F u J i 7 J x j 2 p I L J v g y o m C 2 J j G 0 7 u i B G 4 v c j T B I q W K a p Z 5 g E G 4 R m h i I c A p k 8 Q G u K + J G t B k H O C h t O A 2 T o a Q A G P O y p i l W l 4 F m I q e a 1 9 K t X E e J o s T o o r r 8 B J h f W U g c 8 2 W P V i h p K Z 2 w K v w w F W q N a R V l F F l M k / p X K 2 U z E y 9 d r h i I A 3 c P Y 5 g 5 Z x F Z f 5 J I D X w Q l 3 t b e y F / F e Z 4 / l o V D C l p f S i K 6 L N k C o H C r h K J O d E 9 P L o a J p H x W 3 F c X 4 0 9 b j T J X f q c 4 e H S / L Q J 9 1 4 O n Y v c t d n 8 + I H j v a w p y k a N K m o M G H s L m V 7 E S n N 2 3 6 k i y V 3 s Z L F k k t 9 r r X k W j 4 3 X n J j n + N L j v s c i c 2 0 E 3 b z i E F q r + t h p G l / Y K 8 9 l c m U k J r f U s 6 / c T 3 E p U e 5 X e Y R F a m d + H H s l f z v E 3 Z 8 Z y V Z 0 X W p i j + d 1 M X A 5 j N s N U 3 l 6 2 b Y X F c O b S 7 n 8 5 h / X s z l L S 6 R o k f n 9 M F f s 6 J w U + q e W d f T 4 9 L Y d K 9 p 6 L + d q 8 b 5 T i N 8 3 9 g 9 2 a 3 v N 8 p 3 d Q O 9 R m / Q O x S i D 2 g f f U L H 6 A w l C N B X 9 A 1 9 r / 2 o 3 d R + 1 n 7 N p e t r p c 9 L V F m 1 3 3 8 A T f N D J g = = < / l a t e x i t > v < l a t e x i t s h a 1 _ b a s e 6 4 = " K k 3 O r + y l j z + b j d i 7 x s p X y 9 J P y y A = " > A A A G M 3 i c j V T L b h M x F H U L A 6 U 8 2 s I O N h Y R E o t R l a k q Q O q m U l O J H a X Q J l U m V B 7 H k 1 j x S 7 a n T T S d T 2 A L X 8 L H I H a I L f + A J 5 m Q j l M k L C W + O e d c 3 4 d v n C h G j W 0 2 v 6 + s 3 r o d 3 L m 7 d m / 9 / o O H j z Y 2 t x 6 f G p l p T E 6 w Z F J 3 E m Q I o 4 K c W G o Z 6 S h N E E 8 Y a S e j g 5 J v X x B t q B Q f 7 U S R H k c D Q V O K k X X Q h 9 a n i / P N R n O 7 O V 1 w 2 Y g q o w G q d X S + F T y N + x J n n A i L G T K m G z W V 7 e V I W 4 o Z K d b j z B C F 8 A g N S N e Z A n F i e v k 0 1 w K + c E g f p l K 7 j 7 B w i l 7 3 y B E 3 Z s I T p + T I D o 3 P l e B N X D e z 6 Z t e T o X K L B F 4 F i j N G L Q S l o X D P t U E W z a B t R M F s g l N i p u i h G 4 v c z T h P K W a a p p 5 C I l w j d D I k h C m T C I b w o F G a k j x O I Q j a Y n b O B o R T B h z V s Y s 1 f I y h F T 0 X f t S q o 3 z M F m C k S o v x E u E D Z Q h m W u 2 7 J M l S m p q h 7 w O D 1 2 l W p O 0 j j K q T O Y p n a u V k p n C a 4 c r h q S h u 8 c L s n T O v D L / J C I 1 4 a W 6 3 t v E C / m v M s e z 0 a h h S k v p R V d I m x F V D h T k E k v O k e j n 8 W G R x + V t J U l + W H j c 8 Y I 7 9 r l W a 0 G 2 f N K N p 2 P 3 Y n d 9 N i 9 / w H g P e p q y Q Z O a C i L G b l J 2 5 p H S v O N H O l t w Z 0 t Z L L j U 5 9 o L r u 1 z 4 w U 3 9 j m + 4 L j P o c Q U 3 a i X x 4 y k 9 q o R x Z o O h v b K U 5 l M C a n 5 N e X s G z Y i W H l U 2 3 k e U 5 H a i R / H X s r / P m H H d 1 a S l V 2 X q v z T S V 0 O b D 7 F l t N U v m 6 K z X T V 0 O Z y N o / 5 u / l c X u O w F H 0 6 o w / + m j W F m 1 L 3 0 L q e H l X G u n t N I / / t X D Z O d 7 a j V 9 u 7 7 3 c b + 7 v V u 7 o G n o H n 4 C W I w G u w D 9 6 C I 3 A C M B i A z + A L + B p 8 C 3 4 E P 4 N f M + n q S u X z B N R W 8 P s P T v l D 4 g = = < / l a t e x i t > D v < l a t e x i t s h a 1 _ b a s e 6 4 = " z i H R 1 p 5 G z y R Z V v j N D G M d y e 2 C 5 b o = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m S o C p G 4 q N Z X Y 0 V a 0 S Z W J K o 9 z J 7 H i s S 3 b 0 y a a 5 g v Y w p f w N d 0 h t v w E n m R C O k 6 R s J T 4 5 p x z f R + + c a w 4 M 7 b R u F l b v 3 e / 9 u D h x q P N x 0 + e P n u + t f 3 i z M h M U z i l k k v d i Y k B z g S c W m Y 5 d J Q G k s Y c 2 v H o o O D b l 6 A N k + K L n S j o p W Q g W M I o s Q 4 6 b l 1 s 1 R s 7 j d n C q 0 Z Y G n V U r q O L 7 d q r q C 9 p l o K w l B N j u m F D 2 V 5 O t G W U w 3 Q z y g w o Q k d k A F 1 n C p K C 6 e W z T K f 4 r U P 6 O J H a f Y T F M / S 2 R 0 5 S Y y Z p 7 J Q p s U P j c w V 4 F 9 f N b P K x l z O h M g u C z g M l G c d W 4 q J s 3 G c a q O U T X D l R E B u z e H p X l M D t R Y 4 m W K R U U c 0 y D z A I 1 w h N L A Q 4 4 Z L Y A A 8 0 U U N G x w E e S Q t u S 8 k I K H D u r I x b p u V V g J n o u / Y l T B v n Y b K Y E l V c h 5 c I H y g D m W u 2 7 M M K J T W z w 7 Q K D 1 2 l W k N S R T l T J v O U z t V K y cC E s h L f C f 6 / + A U i A m d W X S b 3 2 Q r M Q = " > A A A G N n i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y U S r a p M p E l W d y J z H x S 7 a n T T T N P 7 C F L + F X 2 L B D b P k E P J k J 6 T h F w l L i m 3 P O 9 X 3 4 x r F i 1 N h W 6 / v K 6 q 3 b j T t 3 1 + 6 t 3 3 / w 8 N H j j c 0 n p 0 Z m O o G T R D K p O z E x w K i A E 0 s t g 4 7 S Q H j M o B 2 P 9 g u + f Q H a U C k + 2 o m C H i c D Q V O a E O u g 0 8 g O w Z L z j W Z r q z V b e N k I K 6 O J q n V 0 v t l 4 F v V l k n E Q N m H E m G 7 Y U r a X E 2 1 p w m C 6 H m U G F E l G Z A B d Z w r C w f T y W b p T / N I h f Z x K 7 T 7 C 4 h l 6 3 S M n 3 J g J j 5 2 S E z s 0 P l e A N 3 H d z K Z v e z k V K r M g k j J Q m j F s J S 5 q x 3 2 q I b F s g m s n C m J j G k 9 v i h K 4 v c j R B P O U a q p Z 5 g E G 4 R q h i Y U A p 0 w S G + C B J m p I k 3 G A R 9 K C 2 z g Z Q Q K M O S t j l m p 5 G W A q + q 5 9 K d X G e Z g s T o g q 7 s R L h A 2 U g c w 1 W / Z h i Z K a 2 i G v w 0 N X q d a Q 1 l F G l c k 8 p X O 1 U j I z 9 d r h i o E 0 c P d 4 A U v n z C v z T w K p g R f q e m 9 j L + S / y h y X o 1 H D l J b S i 6 6 I N i O q H C j g M p G c E 9 H P o 8 N p H h W 3 F c f 5 4 d T j j h f c s c 8 d H C z I A 5 9 0 4 + n Y 3 c h d n 8 2 L H z j a x Z 6 m a N C k p s K E s Z u U n X m k N O / 4 k c 4 W 3 N l S F g s u 9 b n 2 g m v 7 3 H j B j X 2 O L z j u c y Q 2 0 2 7 Y y y M G q b 1 q h p G m g 6 G 9 8 l Q m U 0 J q f k 1 Z f u N m iC u P a j v P I y p S O / H j 2 E v 5 3 y d s + 8 5 K s q L r U h V / O q m L g c 1 n 2 H K a y t f N s F J X D W 0 u y 3 n M 3 8 / n 8 h q X S N G n J b 3 / 1 6 w p 3 J S 6 t 9 b 1 9 K g y 1 t 1 r G v p v 5 7 J x u r 0 V v t 7 a + b D T 3 N u p 3 t U 1 9 B y 9 Q K 9 Q i N 6 g P f Q O H a E T l K B P 6 D P 6 g r 4 2 v j V + N H 4 2 f p X S 1 Z X K 5 y m q r c b v P 6 d I R V o = < / l a t e x i t > ω < l a t e x i t s h a 1 _ b a s e 6 4 = " y g G I S C p s p 8 s 1 A v 8 E A c 6 d 0 D S 0 o B E = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w Z C a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t F 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H 2 x c b z d Z W a 7 b w s h F W R h N V 6 + h i s / E q 6 s s k 4 y B s w o g x 3 b C l b C 8 n 2 t K E w X Q 9 y g w o k o z I A L r O F I S D 6 e W z T K f 4 r U P 6 O J X a f Y T F M / S 2 R 0 6 4 M R M e O y U n d m h 8 r g D v 4 r q Z T T / 2 c i p U Z k E k Z a A 0 Y 9 h K X J S N + 1 R D Y t k E 1 0 4 U x M Y 0 n t 4 V J X B 7 k a M J 5 i n V V L P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I q w F T 0 X f t S q o 3 z M F m c E F V c h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z G b q t c M V A 2 n g 7 v E S l s 6 Z V + a f B F I D L 9 T 1 3 s Z e y H + V O S 5 H o 4 Y p L a U X X R F t R l Q 5 U M B V I j k n o p 9 H h 9 M 8 K m 4 r j v P D q c e d L L g T n z s 4 W J A H P u n G 0 7 G 7 k b s + m x c / c L S L P U 3 R o E l N h Q l j d y k 7 8 0 h p 3 v E j n S + 4 8 6 U s F l z q c + 0 F 1 / a 5 8 Y I b + x x f c N z n S G y m 3 b C X R w x S e 9 0 M I 0 0 H Q 3 v t q U y m h N T 8 l r L 8 x s 0 Q V x 7 V d p F H V K R 2 4 s e x V / K / T 9 j 2 n Z V k R d e l K v 5 0 U h c D m 8 + w 5 T S V r 5 t h p a 4 a 2 l y W 8 5 h / n s / l L S 6 R o k 9 L e v + v W V O 4 K X X P r O v p U W W s u 9 c 0 9 N / O Z e N s e y t 8 v 7 V z v N P c 2 6 n e 1 T X 0 G r 1 B 7 1 C I P q A 9 9 A k d o V O U I E B f 0 T f 0 v f G j c d P 4 2 f h V S l d X K p + X q L Y a v / 8 A x S 9 C 6 A = = < / l a tX ∈ C v 1 ] ≥ 1 2 .Proof First, we prove P[X ∈ D K ] ≥ 1 2 . If we prove that, since C v 1 ⊃ D K , we get the result. Using equation 16, we getP[X ∈ (D K ) c ] ≤ K i=1 P[X i ∈ D c ] ≤ K i=1 d j=1 P[|X ij | > R 1 ] ≤ dK × 1 2dK = 1 2 .In the second inequality, we use the Assumption 2 and sub-exponential context concentration results from Appendix I.2.Next, we define the truncated contextsW = X | {X ∈ C v 1 } := (W ⊤ 1 , . . . W ⊤ K ). Claim 5 The truncated contexts W = (W ⊤ 1 . . . W ⊤ K ) and W a satisfies E[v ⊤ X a X a v] ≥ 1 2 E[v ⊤ W a (W a ) ⊤ v].Note that a is defined asa = arg max i∈[K] X ⊤ i θ. Proof First, observe that E[v ⊤ X a X ⊤ a v] ≥ E[v ⊤ X a X ⊤ a v ∩ {X = W}] + E[v ⊤ X a X ⊤ a v ∩ {X ̸ = W}] ≥ E[v ⊤ X a X ⊤ a v ∩ {X = W}] ≥ E[v ⊤ W a W ⊤ a v | {X = W}]P[X = W] ≥ 1 2 E[v ⊤ W a W ⊤ a v]and then we only need to bound the diversity of the truncated contexts, W = (W ⊤ 1 , . . . W ⊤ K ).We need to check two conditions: The sections of supp(W i ) with direction v in [-1, 1] v should be the same and have a bounded decay rate √ dL(R 1 + 2). Since X satisfies LAC with functions L and ∥C 1 ∥ ∞ ≤ R 1 + 2 by the Lemma 12, it has a bounded decay rate of √ dL(R 1 + 2) by Lemma 3.The truncated contexts W have LAC with L(•) and∥ supp(W)∥ ∞ ≤ R 1 + 2.Proof By the observation of Appendix B.3 for the relation of the conditioning and LAC, it is clear that W has LAC with function L. Also, by the construction of C 1 and Lemma 11,∥ supp(W)∥ ∞ ≤ R 1 + 2 is true. Claim 7 For every i ∈ [K], supp(W i ) is identical for all i ∈ [K] and supp(W i ) ∩ [-1, 1] v has equal sections with direction v.Proof Since we set D v as the partial completion with direction v, it is straightforward.We already checked that our truncated contexts W fulfill the condition of the Proposition 2. Hence, we apply Proposition 2 and we get the bound,E[W a W ⊤ a ] ⪰ c d(A 1 + A 2 (R 1 + 2) α ) 2 I d . hence we get E[X a X ⊤ a ] ⪰ c d(A 1 + A 2 (R 1 + 2) α ) 2 I dfor some absolute constant c > 0.We aim to use the result of Proposition 3. We first consider the case ∥θ ⋆ ∥ 2 = 1, and for general case, using the same argument from Appendix E.4 and (10), we can adjust it. We first truncate our contextsX = (X ⊤ 1 . . . X ⊤ K ) to some region C 2 = D K , D ⊂ R d, with slight abusing of notations. We define the truncated contexts as W = (W ⊤ 1 , . . . W ⊤ K ). Note that the support of W i is D. To satisfy the conditions of Proposition 3, we want to make the sections with direction θ ⋆ of the support of W i the same.We construct the truncation set C 2 as follows. Firstly, setR 3 = c 0 x max (1 + log dK + 1 2 log T ) and R 2 = R 3 + 1. • Set D 1 := ([-R 2 , R 2 ]) d ⊂ R d . • Set D 2 := {x ∈ R d | -R 2 ≤ x ⊤ θ ⋆ ≤ R 2 } ⊂ R d • Set D 3 := D 1 ∩ D 2 . • Set D := C[D 3 , θ ⋆ ]. • The final truncation set is constructed by C 2 = D K .Claim 8 The supnorm of the truncation set satisfies ∥ supp(W)∥ ∞ = ∥D∥ ∞ ≤ 3R 2 and the W has bounded LAC with L(3R 2 ).Proof The LAC of W has the same function as the original, L(•) by Lemma 1. By Lemma 11, we easily see that ∥ supp(W)∥ ∞ ≤ 3R 2 since π θ ⋆ (D 2 ) is an interval with length 2R 2 . Since L(•) is an increasing function (by definition) and ∥ supp(W)∥ ∞ ≤ 3R 2 , W has a bounded LAC with L(3R 2 ).The region C 2 has equal sections with direction θ ⋆ and P[X ∈ C 2 ] ≥ 1 -1 √ T .Proof By the moment Assumption 2,P[|X ij | ≤ R 2 ] ≥ 1 - 1 2dK √T holds for all i, j and thereforeP[X ∈ D K 1 ] ≥ 1 -1 2 √ T holds. Next, by Assumption 2, we get P[X ∈ D K 2 ] ≥ 1 -1 2 √ T . Hence P[X ∈ D K 3 ] ≥ 1 -1 √ T and D ⊃ D 3 , we get P[X ∈ C 2 ] ≥ 1 -1 √ T .We truncate X into the high probability confidence region C 2 and define the truncated contexts as W = (W ⊤ 1 . . . W ⊤ K ) and play with W = (W ⊤ 1 , . . . W ⊤ K ) from now on. The following calculation shows that it is enough to bound the suboptimality gap of W.EQUATIONTherefore, if we find the constantEQUATIONwe finally can boundC ∆ ≤ C ′ ∆ . Lemma 13 The truncated contexts W = X | {X ∈ C 2 } meet the condition of Proposition 3 with H = R 2 + 1 and δ = 1 √ T . Proof Let D = cyl(B, θ ⋆ , R 2 ) for some set B ⊂ P θ ⋆ and define D ′ = cyl(B, θ ⋆ , R 2 -1). We can show that P[X ∈ D ′ ] ≥ 1 -1 √T with exactly same argument from Claim 9. Hence we can calculateP[W ∈ D ′ ] ≥ P[X ∈ D ′ ]/P[X ∈ D] ≥ 1 -1 F.3.3 Applying Proposition 3Finally, we aim to apply Proposition 3, which bounds the margin constant.Then, by Proposition 3, we can get the equation ( 13) holds forC ′ ∆ = 3 √ dL(R 2 ) = 3 √ d(A 1 + A 2 (3R 2 ) α ).Then, finally, we getC ∆ ≤ 3 √ d(A 1 + A 2 (3R 2 ) α ) = O( √ d).F.4 Proof of Theorem 1: Unbounded Contexts CaseWe combine the previous Proposition 9 and our result of Theorem 2 and 3. Then we getReg(T ) ≤ cC ∆ dx 2 max 1 λ ⋆ (log T ) 4 ≤ cC ∆ d 2.5 x 2 max (A 1 + A 2 (R 1 + 2) α ) 2 (A 1 + A 2 2 α R α 2 )(log T ) 4 ≤ O(d 2.5 ) holds.Now, we present our main result for bounded contexts.In the linear contextual bandit setting, ℓ 2 boundedness is widely used. However, for light-tailed distributions (such as Gaussian or exponential), the ℓ 2 norm is unbounded. Therefore, we divide our analysis into two cases: unbounded and bounded contexts. While our previous focus was on unbounded contexts, here we summarize and present the 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 R or a distribution with bounded density on the ball is used.1) Truncated contexts. Truncated contexts refer to cases where the context distribution is a truncated version of the original distribution. For example, truncated Gaussian and truncated exponential distributions fall into this category.2) Naturally bounded contexts. Naturally bounded contexts include uniform distributions on a ball or distributions with bounded density defined on the ball.Now, we present our result for the regret bound. The first case is when we receive the truncated contexts, generated by truncating the unbounded contexts to (B R ) K where B R is d-dimensional ball with radius R. For the ℓ 2 -bounded case, R may depend on the dimension d when we choose a large R, so we do not hide the R term in our main regret bound result. Corollary 1 and 2 gives the regret bound for truncated contexts. Corollary 3 gives the regret bound for naturally bounded contexts.Corollary 1 (Regret bound: truncated contexts) Let X(t) be unbounded contexts with the same condition as Theorem 1. For R ′ > 0 with P[X(t) ∈ (B R ′ ) K ] = p > 0, we receive truncated contexts X(t) | (B R ′ +r ) K for some r > 0 each round t ≥ 1. In this case, for R = R ′ + r, the regret of Algorithm 1 is bounded byReg(T ) ≤ O(d 2.5 R 2 L(R) 2 1 p ).when r ≍ R 1 .Example: truncated contexts. The next lemma states that the truncated contexts satisfy Condition 1 has parameters 1c ⋆ , p ⋆ ≍ 1. If contexts are generated by truncating from the original distribution and the truncated region is a positive probability region, then the parameters in Condition 1 c ⋆ , p ⋆ are well-defined and do not harm the regret bound when we choose a sufficiently large truncation set.Lemma 14 (Concentration parameters for truncated contexts) Suppose the unbounded contextsX ∈ R dK satisfy P[X ∈ (B R ′ ) K ] = p > 0,for some R ′ > 0. Then if we truncate eachX i to B R ′ +r for any r > 0, i ∈ [K], the truncated contexts X = (X ⊤ 1 , . . . X ⊤ K ) satisfy Condition 1 with p ⋆ = p, c ⋆ = R ′ R ′ +r .Proof Recall that we truncate X to(B R ′ +r ) K . If P[X ∈ (B R ′ ) K ] = p > 0 and truncate to B R ′ +r , P[max i∈[K] X ⊤ η ≤ R ′ ] = P[{max X ⊤ i η ≤ R ′ } ∩ {X ∈ (B R ′ +r ) K }] P[X ∈ (B R ′ +r ) K ] ≥ P[X ∈ (B R ′ ) K ] P[X ∈ (B R ′ +r ) K ] ≥ P[X ∈ (B R ′ ) K ] = p.Therefore, we can set p ⋆ = p and c ⋆ = R ′ R ′ +r .Example: Bounded Density Distributions The below lemma tells us that a uniform distribution or a bounded density distribution defined in the ball B R satisfies Condition 1 and presents the range of two parameters. Without loss of generality, we prove for distribution defined in unit ball, B 1 .Lemma 15 Consider a random vectorX i ∈ B 1 , i ∈ [K]with each X i 's density being upper bounded with cu ω d Here, ω d is a volume of d-dimensional unit ball B 1 , recalling that the density of the uniform distribution in the ball B 1 has density 1 ω d . When X 1 = • • • = X K (strongly correlated), then Condition 1 holds withp ⋆ = 1 2 , 1 -c ⋆ ≳ 1.When X 1 , . . . X K are independent (not correlated), we havep ⋆ = 1 2 , 1 -c ⋆ ≥ cK -2 d+1 .Proof We use the result of the below Claim 10.Correlated Case. For the caseX 1 = X 2 = . . . X K , the 1 2 -quantile of X ⊤ i η say c ⋆ satisfies 2(1 -c ⋆ ) ≥ ( 1 2c u ω d ω d-1)2 d+1by the Claim 10. Since (ω d ω d-1 ) 2 d+1 ≍ 1, we get 1 -c ⋆ ≳ 1.Independent Case. For the case X ⊤ 1 , . . . X ⊤ K are independent, for c ⋆ with2(1 -c ⋆ ) ≥ 1 -c 2 ⋆ = ( 1 Kc u ω d ω d-1 ) 2 d+1 ≍ K -2 d+1 satisfies P[X ⊤ i η ≤ c ⋆ R] ≤ 1 -1 K for all i ∈ [K]. Due to independence, we get p ⋆ = (1 -1 K ) K ≤ 1 2 .Claim 10 Consider random vector X ∈ R d defined in B 1 with density upper bounded by cu ω d . For any η ∈ S d-1 , let 1p quantile of X ⊤ η as α. We have2(1 -α) ≥ 1 -α 2 ≥ ( p c u ω d ω d-1 ) 2 d+1 .We prove that α with 1 -α 2 = ( p cu ω d ω d-1 ) 2 d+1 satisfies P[X ⊤ η ≥ α] ≤ p.Since the density of X ⊤ η = r satisfiesP[X ⊤ η = r] ≤ ω d-1 (1 -r 2 ) d-1 2 c u ω d hence P[X ⊤ η ≥ α] ≤ 1 α ω d-1 (1 -r 2 ) d-1 2 c u 1 ω d ≤ c u ω d-1 ω d (1 -α)(1 -α 2 ) d-1 2 ≤ c u ω d-1 ω d (1 -α 2 ) d+1 2 ≤ p G.Now, we present results related to two challenges for bounded contexts. Proof are presented in Appendix H.Proposition 4 (Diversity constant: naturally bounded contexts) Suppose X(t) is the random vector supported in (B R ) K , its density satisfies the LAC condition with constant function L(R) and has Condition 1 with p ⋆ , c ⋆ . Thenλ ⋆ (t) ≥ c p ⋆ d 1 (L(R) + 1 R(1-c⋆) ) 2for the absolute constant c > 0.Proposition 5 (Diversity constant: high-prob truncated contexts) Suppose X(t) ∈ R d×K satisfies LAC with L(•) and Assumption 2. Then we truncateX(t) to (B L ) K for some L ≥ c √ dx max (1 + log( dKxmax λ⋆)) and define this truncated contexts as X(t) = (X 1 (t) . . . X K (t)). Then, it has diversity constant (Challenge 1) with 1 2 λ ⋆ (t), where λ ⋆ (t) is a diversity constant of X(t).Proposition 6 (Suboptimality gap: truncated contexts) Let X(t) be a truncated random variable ofX(t) into (B R ) K with P[X ∈ (B R ) K ] ≥ 1 -δ for some δ > 0. Let C ∆ (t)is a margin constant of the contexts before truncation. Then margin constant of truncated contexts X(t), say C ∆ (t) satisfiesC ∆ (t) ≤ 1 1 -δ C ∆ (t).Proposition 7 (Suboptimality gap: naturally bounded contexts) For naturally bounded contexts X(t) with LAC function L(•), the margin constant is bounded asC ∆ (t) ≤ cK √ dL(R)for some absolute constant c > 0.Definition 16 (Linear section maps) We define the linear section maps between sections. For two sections of A, Sec(A, v, y) and Sec(A, v, y + h), we define linear section map Φ h y asΦ h y (•) : Sec(A, v, y) → Sec(A, v, y + h)which satisfies Φ h y (Sec(A, v, y)) ⊂ Sec(A, v, y + h) and Φ h y is a part of some projection map with center P .< l a t e x i t s h a 1 _ b a s e 6 4 = " E N y O 9 H G A q F N C T t U l n w 5 + W r k q 1 x A = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m S o C p G 4 q t Z X Y k V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w J B P S c Y q E p c Q 3 5 5 z r + / C N Y 8 W o s Y 3 G z d r 6 v f u 1 B w 8 3 H m 0 + f v L 0 2 f O t 7 R d n R m Y 6 g d N E M q k 7 M T H A q I B T S y 2 D j t J A e M y g H Y 8 O C r 5 9 C d p Q K b 7 Y i Y I e J w N B U 5 o Q 6 6 D j 1 s V W v b H T m C 2 8 a o S l U U f l a l 1 s 1 1 5 F f Z l k H I R N G D G m G z a U 7 e V E W 5 o w m G 5 G m Q F F k h E Z Q N e Z g n A w v X y W 6 R S / d U g f p 1 K 7 j 7 B 4 h t 7 2 y A k 3 Z s J j p + T E D o 3 P F e B d X D e z 6 c d e T o X K L I h k H i j N G L Y S F 2 X j P t W Q W D b B l R M F s T G N p 3 d F C d x e 5 G i C R U o V 1 S z z A I N w j d D E Q o B T J o k N 8 E A T N a T J O M A j a c F t n I w g A c a c l T F L t b w K M B V 9 1 7 6 U a u M 8 T B Y n R B X X 4 S X C B s p A 5 p o t + 7 B C S U 3 t k F f h o a t U a 0 i r K K P K Z J 7 S u V o p m Z l 6 7 X D F Q B q 4 e 7 y E l X M W l f k n g d T A C 3 W 1 t 7 E X 8 l 9 l j u e j U c G U l t K L r o g 2 I 6 o c K O A q k Z w T 0 c + j o 2 k e F b c V x / n R 1 O N O l t y J z x 0 e L s l D n 3 T j 6 d i 9 y F 2 f z Y s f O N r D n q Z o 0 K S i w o S x u 5 S d R a Q 0 7 / i R z p f c + U o W S y 7 1 u f a S a / v c e M m N f Y 4 v O e 5 z J D b T b t j L I w a p v a 6 H k a a D o b 3 2 V C Z T Q m p + S z n / x v U Q l x 7 l d p F H V K R 2 4 s e x V / K / T 9 j 1 n Z V k R d e l K v 5 0 U h c D m 8 + w 1 T S V r 5 t h c 1 0 5 t L m c z 2 P + e T G X t 7 h E i j 6 d 0 w d / z Y r C T a l 7 Z l 1 P W 6 W x 6 V 7 T 0 H 8 7 V 4 2 z 3 Z 3 w / U 7 z u F n f b 5 b v 6 g Z 6 j d 6 g d y h E H 9 A + + o R a 6 B Q l C N B X 9 A 1 9 r / 2 o 3 d R + 1 n 7 N p e t r p c 9 L V F m 1 3 3 8 A c 0 R D B g = = < / l a t e x i t > P < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 2 v 0 O 5 9 Z L R A T J b g u A T x 5 q a K R c E I = " > A A A G S 3 i c j V T N b h M x E H Y L g V L + W j g B F 4 s I q U i r K l t V g N R L U V u J G 6 X Q p l U 2 i r z O b G L F a 1 u 2 t 0 2 0 X f E 0 X O F J e A C e g x v i g D c / p O s U C U s b T + b 7 x j P + P J p Y c W Z s o / F j a f n G z d q t 2 y t 3 V u / e u / / g 4 d r 6 o x M j M 0 3 h m E o u 9 W l M D H A m 4 N g y y + F U a S B p z K E Z D / Z K v H k O 2 j A p P t m R g n Z K e o I l j B L r X J 2 1 J 5 F U o I m V W p A U 8 o 9 A i 4 2 3 w X k w e t l Z q z c 2 G + O F F 4 1 w a t T R d B 1 2 1 m t P o 6 6 k W Q r C U k 6 M a Y U N Z d s 5 0 Z Z R D s V q l B l Q h A 5 I D 1 r O L B O a d j 6 + Q 4 F f O E 8 X J 1 K 7 T 1 g 8 9 l 6 N y E l q z C i N H T M l t m 9 8 r H R e h 7 U y m 7 x p 5 0 y o z I K g k 0 R J x r G V u B Q E d 5 k G a v k I V 0 4 U x M Y s L q 7 L E r i 9 r N E E s 5 I q r H H l A Q b h h H D C Q o A T L o k N c E 8 T 1 W d 0 G O C B t O C 2 l A y A A u f O y r h l W l 4 E m I m u k y 9 h 2 r g I k 8 W U q P K h v E J 4 T x n I n N i y C w u Q 1 M z 2 0 6 q 7 7 2 6 q N S R V L 2 f K Z B 7 T h V o p u S k 8 O d x l I A n c O 5 7 D w j m z m / k n g d S Q l u y q t r G X 8 l / X H E 5 a o + J T W k o v u y L a D J h y T g E X V K Y p E d 0 8 O i j y q H y t O M 4 P C g 8 7 m m N H P r a / P w f 3 f d C 1 p 0 N 3 I v d 8 N i / / 4 G g H e 5 x S o F G F h Q n n 1 z F P Z 5 m S / N T P d D b H z h a q m G O J j z X n W N P H h n N s 6 G P p H E t 9 j M S m a I X t P O K Q 2 M t 6 G G n W 6 9 t L j 2 U y J a R O r z A n v 7 g e 4 m n E d O v k E R O J H f l 5 7 I X 8 7 x O 2 / G A l e a l 6 Z Z q N f Y t l K p 8 3 9 k 1 4 0 6 b N 5 a Q f 8 / e z v r y C U S m 6 b A L v / T U r D N e l b g A 7 T Q + n x q q b p q E / O x e N k 6 3 N 8 N X m 9 o f t + u 7 2 d K 6 u o G f o O d p A I X q N d t E 7 d I i O E U W f 0 R f 0 F X 2r f a / 9 r P 2 q / Z 5 Q l 5 e m M Y 9 R Z d 2 q / Q E c x 0 w t < / l a t e x i t > Sec(A, v, y) < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 r M B 2 t / B y 1 k d e y 7 a q 4v J a R + G j v k = " > A A A G T X i c j V R N b x M x E H U L o a V 8 t X C j F 4 s I q Y h V l a 0 q Q O q l q K 3 E j V J o k y o b R V 7 H m 1 j x l 2 x v m 2 i 7 B 3 4 N V / g l n P k h 3 B D C m 2 x I 1 y k S l j a e z H v j G T + P J l a M G t t o / F h a v n W 7 d m d l 9 e 7 a v f s P H j 5 a 3 3 h 8 Z m S q M T n F k k n d i p E h j A p y a q l l p K U 0 Q T x m p B k P D w q 8 e U G 0 o V J 8 s m N F O h z 1 B U 0 o R t a 5 u u u b k V R E I y u 1 Q J x k H w n O t 9 4 G F 8 H 4 5 e B F d 7 3 e 2 G 5 M F l w 0 w t K o g 3 I d d z d q T 6 O e x C k n w m K G j G m H D W U 7 G d K W Y k b y t S g 1 R C E 8 R H 3 S d m a R 0 n S y y S 1 y + N x 5 e j C R 2 n 3 C w o n 3 e k S G u D F j H j s m R 3 Z g f K x w 3 o S 1 U 5 u 8 6 W R U q N Q S g a e J k p R B K 2 E h C e x R T b B l Y 1 g 5 U S A b 0 z i / K U v g 9 q J G E 8 x K q r A m l Q e Q C C e E k 5 Y E M G E S 2 Q D 2 N V I D i k c B H E p L 3 M b R k G D C m L N S Z q m W l w G k o u f k S 6 g 2 L s K k M U a q e C q v E N Z X h q R O b N k j C 5 D U 1 A 5 4 1 T 1 w N 9 W a J F U v o 8 q k H t O F W i m Z y T 0 5 3 G V I E r h 3 v C A L 5 8 x u 5 p 9 E p C a 8 Y F e 1 j b 2 U / 7 r m a N o a F Z / S U n r Z F d J m S J V z C n K J J e d I 9 L L o K M + i 4 r X i O D v K P e x k j p 3 4 2 O H h H D z 0 Q d e e D t 2 L 3 P P Z r P g D o z 3 o c Q q B x h U W R I z d x G z N M i V Z y 8 9 0 P s f O F 6 q Y Y 4 m P N e d Y 0 8 d G c 2 z k Y 3 y O c R 9 D s c n b Y S e L G E n s V T 2 M N O 0 P 7 J X H M q k S U v N r z O k v r I e w j C i 3 b h Z R k d i x n 8 d e y v 8 + Y c c P V p I V q l f m 2 c S 3 W K b y e R P f l F c 2 b S a n / Z i 9 n / X l N Q x L 0 a N T + O C v W W G 4 L n U j 2 G l 6 X B p r b p q G / u x c N M 5 2 t s N X 2 7 s f d u v 7 u + V c X Q W b 4 B n Y A i F 4 D f b B O 3 A M T g E G n 8 E X 8 B V 8 q 3 2v / a z 9 q v 2 e U p e X y p g n o L L u r P w B 1 7 t M 1 A = = < / l a t e x i t > Sec(A, v, y + h) < l a t e x i t s h a 1 _ b a s e 6 4 = " S 3 M Y 0 A H n z 1 m H F g J w K b f K K m J h j 1 o = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w Z C a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t F 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H l x c b z d Z W a 7 b w s h F W R h N V 6 + h i s / E q 6 s s k 4 y B s w o g x 3 b C l b C 8 n 2 t K E w X Q 9 y g w o k o z I A L r O F I S D 6 e W z T K f 4 r U P 6 O J X a f Y T F M / S 2 R 0 6 4 M R M e O y U n d m h 8 r g D v 4 r q Z T T / 2 c i p U Z k E k Z a A 0 Y 9 h K X J S N + 1 R D Y t k E 1 0 4 U x M Y 0 n t 4 V J X B 7 k a M J 5 i n V V L P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I q w F T 0 X f t S q o 3 z M F m c E F V c h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z G b q t c M V A 2 n g 7 v E S l s 6 Z V + a f B F I D L 9 T 1 3 s Z e y H + V O S 5 H o 4 Y p L a U X X R F t R l Q 5 U M B V I j k n o pP q A 9 9 A k d o V O U I E B f 0 T f 0 v f G j c d P 4 2 f h V S l d X K p + X q L Y a v / 8 A T 8 F D L A = = < / l a t e x i t > v < l a t e x i t s h a 1 _ b a s e 6 4 = " L V b I E H n J h z x x l t z I M Y I Z y g j S v z g = " > A A A G O H i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y E S r a p M q E y O N 4 M l b 8 k u 1 p E 0 3 z E 2 z h S / g T d u w Q W 7 4 A T z J h O k 6 R s J T 4 5 p x z f R + + c a w Y N b b V + r 6 2 f u t 2 4 8 7 d j X u b 9 x 8 8 f P R 4 a / v J m Z G Z x u Q U S y Z 1 N 0 a G M C r I q a W W k a 7 S B P G Y k U 4 8 P i z 4 z g X R h k r x 0 U 4 V 6 X M 0 E j S h G F k H d a N 2 S g f T T + l g q 9 n a a c 0 X X D X C 0 m i C c r U H 2 4 1 n 0 V D i j B N h M U P G 9 M K W s v 0 c a U s x I 7 P N K D N E I T x G I 9 J z p k C c m H 4 + T 3 g G X z p k C B O p 3 U d Y O E e v e + S I G z P l s V N y Z F P j c w V 4 E 9 f L b P K 2 n 1 O h M k s E X g R K M g a t h E X 1 c E g 1 w Z Z N Y e 1 E g W x M 4 9 l N U Q K 3 F z m a Y J l S T T X P P I B E u E Z o Z E k A E y a R D e B I I 5 V S P A n g W F r i N o 7 G B B P G n J U x S 7 W 8 D C A V Q 9 e + h G r j P E w W Y 6 S K W / E S Y S N l S O a a L Y d k h Z K a 2 p T X 4 d R V q j V J 6 i i j y m S e 0 r l a K Z m Z e e 1 w x Z A k c P d 4 Q V b O W V b m n 0 S k J r x Q 1 3 s b e y H / V e Z k M R o 1 T G k p v e g K a T O m y o G C X G L J O R L D P D q e 5 V F x W 3 G c H 8 8 8 7 q T i T n z u 6 K g i j 3 z S j a d j 9 y N 3 f T Y v f s B o H 3 q a o k H T m g o i x m 5 S d p e R k r z r R z q v u P O V L C o u 8 b l O x X V 8 b l J x E 5 / j F c d 9 D s V m 1 g v 7 e c R I Y q + a Y a T p K L V X n s p k S k j N r y k X 3 7 A Z w t K j 3 A Z 5 R E V i p 3 4 c e y n / + 4 R d 3 1 l J V n R d q u J P J 3 U x s P k c W 0 1 T + b o 5 t t C V Q 5 v L xa Q r M X 0 K C o i + Q + k = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q 2 k r d 0 V a 0 S Z W J K s / k T m L F L 9 m e J t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w J B P S c Y q E p c Q 3 5 5 z r + / C N Y 8 W o s Y 3 G z c r q v f u 1 B w / X H q 0 / f v L 0 2 f O N z R f n R m Y 6 g b N E M q l b M T H A q I A z S y 2 D l t J A e M y g G Q / 2 C 7 5 5 B d p Q K b 7 Y s Y I O J z 1 B U 5 o Q 6 6 C T o 8 u N e m O r M V 1 4 2 Q h L o 4 7 K d X y 5 W X s V d W W S c R A 2 Y c S Y d t h Q t p M T b W n C Y L I e Z Q Y U S Q a k B 2 1 n C s L B d P J p p h P 8 1 i F d n E r t P s L i K X r b I y f c m D G P n Z I T 2 z c + V 4 B 3 c e 3 M p h 8 7 O R U q s y C S W a A 0 Y 9 h K X J S N u 1 R D Y t k Y V 0 4 U x M Y 0 n t w V J X B 7 k a M J 5 i l V V N P M A w z C N U I T C w F O m S Q 2 w D 1 N V J 8 m o w A P p A W 3 c T K A B B h z V s Y s 1 X I Y Y C q 6 r n 0 p 1 c Z 5 m C x O i C q u w 0 u E 9 Z S B z D V b d m G J k p r a P q / C f V e p 1 p B W U U a V y T y l c 7 V S M j P x 2 u G K g T R w 9 3 g F S + f M K / N P A q m B F + p q b 2 M v 5 L / K H M 1 G o 4 I p L a U X X R F t B l Q 5 U M A w k Z w T 0 c 2 j w 0 k e F b c V x / n h x O N O F 9 y p z x 0 c L M g D n 3 T j 6 d j d y F 2 f z Y s f O N r F n q Z o 0 L i i w o S x u 5 S t e a Q 0 b / m R L h b c x V I W C y 7 1 u e a C a / r c a M G N f I 4 v O O 5 z J D a T d t j J I w a p v a 6 H k a a 9 v r 3 2 V C Z T Q m p + S z n 7 x v U Q l x 7 l d p l H V K R 2 7 M e x Q /n f J 2 z 7 z k q y o u t S F X 8 6 q Y u B z a f Y c p r K 1 0 2 x m a 4 c 2 l z O 5 j H / P J / L W 1 w i R Z f O 6 P 2 / Z k X h p t Q 9 s 6 6 n x 6 W x 7 l 7 T 0 H 8 7 l 4 3 z 7 a 3 w / d b O y U 5 9 7 1 P 5 r q 6 h 1 + g N e o d C 9 A H t o S N 0 j M 5 Q g g B 9 R d / Q 9 9 q P 2 k 3 t Z + 3 X T L q 6 U v q 8 R J V V + / 0 H S R J D D A = = < / l a t e x i t > H Figure 12 : Illustration of linear section maps. Projection map of Sec(A, v, y) to P induce linear section map Sec(A, v, y) to Sec(A, v, y + h). Also we use H as the length between Sec(A, v, y) and P .Our subgoal is to bound the one-side decay rate of the section density, and we use linear section maps to bound them. Previously, we deal with expanding or equal sections, hence section maps directly gives the lower bound of density. However, for general linear section maps, they are no longer expanding sections due to boundaries. Assume the density f is defined in B R and it has a decay rate M . If f has LAC with function L(•), we already studied in Lemma 3 that it has decay rate with M = √ dL(R). We can set L(R) ≥ 10.Slope of linear section maps. We first bound the maximum length between Φ h y (x) and x. It is related to the slope of section maps, and we define s > 0 such that ∥Φ h y (x) -x∥ 2 ≤ sh for any x ∈ Sec(A, v, y). We call s as a slope of linear section map Φ h y (•).Volume element. We define | det(∇Φ h y (x))| := u y (h). This value is the same for any x ∈ Sec(A, v, y), since we use the linear section maps. Using that, we can calculate the lower bound of g(y + h) as the following:g(y + h) = Sec(A,v,y+h) f (x)dx ≥ Sec(A,v,y) f (Φ h y (x))| det(∇Φ h y (x))|dx ≥ Sec(A,v,y) f (x) exp(-M sh)u y (h)dx = exp(-M sh)u y (h)g(y).The third inequality is by using the Gronwall inequality, Lemma 22, using the decay rate is bounded by M and the length between x and Φ h y (x) is bounded by sh. This formula tell us that to bound the one-side decay rate of section density, there are two quantities: slope s and volume element u y (h).A way to bound u y (h). Lets define H as the intersection of two section Sec(A, v, y) and P . The volume element can be calculated asu y (h) = ( H -h H ) dholds since H-h H is the ratio of similarity. Then,g(y + h) g(y) ≥ exp(-M sh -(-d log( H -h H ))) When h ≤ H 2 , we have log( H-h H ) ≥ 1 -2h H , we have g(y + h) g(y) ≥ exp(-M sh - 2d H h)This implies that when we can find the linear section map Φ h y , we can bound the one-side decay rate of the section density by M s + 2d H .H.5 Linear Section Maps between Sliced Balls, S R (v, y)< l a t e x i t s h a 1 _ b a s e 6 4 = " E N y O 9 H G A q F N C T t U l n w 5 + W r k q 1 Lemma 16 (One-side decay rate of S R (v, y)) The projected density g(y) of sections S R (v, y) satisfiesx A = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m S o C p G 4 q t Z X Y k V a 0 S Z W J K s / k T m L F Lf O + 7 K X z / s J z f 7 1 f S k 9 Z P 7 A V O X F M = " > A A A G S X i c j V T L b h M x F H V b U k p 5 t b B A g o 1 F h F S k U Z S p K k D q p l J b i R 2 l 0 C Z V J o o 8 j i e x 4 p d s T 5 t o O l / D F r 6 E L + A z 2 C F W e J I J 6 T h F w l L i m 3 P O 9 X 3 4 x r F i 1 N h m 8 8 f K 6 t q d 2 v r d j X u b 9 x 8 8 f P R 4 a / v J u Z G p x u Q M S y Z 1 O 0 a G M C r I m a W W k b b S B P G Y k V Y 8 O i z 4 1 i X R h k r x 2 U 4 U 6 X I 0 E D S h G F k H 9 b a e R R z Z Y R x n n / L e 6 U 5 k h 8 S i A E 5 e 9 7 b q z U Z z u u C y E Z Z G H Z T r p L d d e x 7 1 J U 4 5 E R Y z Z E w n b C r b z Z C 2 F D O S b 0 a p I Q r h E R q Q j j M F 4 s R 0 s 2 k F O X z l k D 5 M p H Y f Y e E U v e m R I W 7 M h M d O W e R r f K 4 A b + M 6 q U 3 e d T M q V G q J w L N A S c q g l b B o B + x T T b B l E 1 g 5 U S A b 0 z i / L U r g 9 i J H E 8 x T q q i m m Q e Q C N c I j S w J Y M I k s g E c a K S G F I 8 D O J K W u I 2 j E c G E M W e l z F I t r w J I R d + 1 L 6 H a O A + T x h i p 4 p q 8 R N h A G Z K 6 Z s s + W a K k p n b I q / D Q V a o 1 S a o o o 8 q k n t K 5 W i m Z y b 1 2 u G J I E r h 7 v C R LG I f 1 l M f J T P T C 0 v U i Y o Y J H L K c o = " > A A A G S n i c j V T L b h M x F H V L U 0 p 5 t b B B s L G I k I o Y V Z m q A q R u K r W V 2 F E K b V J l o s j j e B I r f s n 2 t I m m w 9 e w h S / h B / g N d o g N n m R C O k 6 R s J T 4 5 p x z f R + + c a w Y N b b R + L G 0 f G u l t n p 7 7 c 7 6 3 X v 3 H z z c 2 H x 0 Z m S q M T n F k k n d i p E h j A p y a q l l p K U 0 Q T x m p B k P D w q + e U G 0 o V J 8 s m N F O h z 1 B U 0 o R t Z B 3 Y 0 n E U d 2 E M f Z x 7 x 7 s h X Z A b E o G L 8 a v O x u 1 B v b j c m C i 0 Z Y G n V Q r u P u Z u 1 p 1 J M 4 5 U R Y z J A x3 p K 5 2 q l Z C b 3 2 u G K I U n g 7 v G C L J w z q 8 w / i U h N e K G u 9 j b 2 Q v 6 r z N F 0 N C q Y 0 l J 6 0 R X S Z k i V A w W 5 x J J z J H p Z d J R n s 8 k + y j 3 u Z M 6 d + N z h 4 Z w 8 9 E k 3 n o 7 d i 9 z 1 2 a z 4 A a M 9 6 G m K B o 0 r K o g Y u 0 n Z m k V K s p Y f 6 X z O n S 9 k M e c S n 2 v O u a b P j e b c y O f 4 n O M + h 2 K T t 8 N O F j G S 2 K t 6 G G n a H 9 g r T 2 V S J a T m 1 5 T T b 1 g P Y e l R b t 0 s o i K x Y z + O v Z T / f c K O 7 6 w k K 7 o u V f G n k 7 o Y 2 G y C L a a p f N 0 E m + r K o c 3 k d B 6 z 9 7 O 5 v M Z h K X p 0 S h / 8 N S s K N 6 X u / XI R l T R s W 1 X u t T i C Y = " > A A A G M X i c j V T L b h M x F H W B Q C m v F n a w s Y i Q W I y q T F U B U j e V 2 kv Z y o i 2 j H K Z r U W Z A E T o i A + g 6 U 5 A U T C + f Z T r F 7 x z S x 4 n U 7 i M s n q G 3 P X K S G j N J Y 6 d M i R 0 a n y v A u 7 h u Z p N P v Z w J l V k Q t A y U Z B x b i Y u y c Z 9 p o J Z P c O 1 E Q W z M 4 u l d U Q K 3 F z m a Y J 5 S T T X L P M A g X C M 0 s R D g h E t i A z z Q R A 0 Z H Q d 4 J C 2 4 L S U j o M C 5 s z J u m Z Z X A W a i 7 9 q X M G 2 c h 8 l i S l R x H V 4 i f K A M Z K 7 Z s g 9 L l N T M D t M 6 P H S V a g 1 J H e V M m c x T O l c r J T d T r x 2 u G E g C d 4 + X s H T O v D L / J J A a 0 k J d 7 2 3 s h f x X m e N y N G q Y 0 l J 6 0 R X R Z s S U A w V c U Z m m R P T z 6 G C a R 8 V t xg(y ′ ) g(y) ≥ exp(-3 √ dL(R)(y ′ -y)) for any -1 √ d < y < y ′ < 1 √ d .Proof Set P as the similarity center of S R (v, y) and S R (v, y + h). We aim to apply arguments of Appendix H. 1 √ d , 1 √ d ] is bounded by 2 √ dL(R) + 2d H ≤ 2 √ dL(R) + 2d(y + h) R 2 -(y + h) 2 ≤ 3 √ dL(R).holds for all -1√ d ≤ y < y + h ≤ 1 √ d since L(R) ≥ 10.H.6 Linear Section Maps for Double Slicde balls, S R (θ, b, v, y)Goal. We investigate the one-sided decay rate of section densities with sections S R (θ, b, v, y) for fixed θ, v, b. For density f (x) defined in B R with LAC function L(•), we define section density of S R (θ, b, v, y) as g(y). We setM = 4 √ dL(R) + 16 √ d R 2 (1-c⋆) .We prove that the one-side decay rate at y ∈ [-1M , 1 M ] is bounded by M. Also we define some small angle τ 0 := sin -1 ( 1 MR ).H.6.1 Case v ⊥ θ.For this case, the sections S R (θ, b, v, y) are no longer expanding section when ⟨θ, v⟩ is close to π 2 . In that case, we can construct a linear section map, and the following figure illustrates the procedure. In each section S R (θ, b, v, y) and S R (θ, b, v, y + h), assume the highest coordinate with respect to direction θ as Q and Q h . Assume the directed half-line starting from connecting Q and connecting Q h and the hyperplane {x | x ⊤ θ = b} meets at some point P . Then we can set the intersection point P as the center of the projection map and we can construct linear section map using P . Please see the figure 14 for the intuitions.< l a t e x i t s h a 1 _ b a s e 6 4 = " C E s h L f C f 6 / + A U i A m d W X S b 3 2 Q r M Q = " > A A A G N n i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y U S r a p M p E l W d y J z H x S 7 a n T T T N P 7 C F L + F X 2 L B D b P k E P J k J 6 T h F w l L i m 3 P O 9 X 3 4 x r F i 1 N h W 6 / v K 6 q 3 b j T t 3 1 + 6 t 3 3 / w 8 N H j j c 0 n p 0 Z m O o G T R D K p O z E x w K i A E 0 s t g 4 7 S Q H j M o B 2 P 9 g u + f Q H a U C k + 2 o m C H i c D Q V O a E O u g 0 8 g O w Z L z j W Z r q z V b e N k I K 6 O J q n V 0 v t l 4 F v V l k n E Q N m H E m G 7 Y U r a X E 2 1 p w m C 6 H m U G F E l G Z A B d Z w r C w f T y W b p T / N I h f Z x K 7 T 7 C 4 h l 6 3 S M n 3 J g J j 5 2 S E z s 0 P l e A N 3 H d z K Z v e z k V K r M g k j J Q m j F s J S 5 q x 3 2 q I b F s g m s n C m J j G k 9 v i h K 4 v c j R B P O U a q p Z 5 g E G 4 R q h i Y U A p 0 w S G + C B J m p I k 3 G A R 9 K C 2 z g Z Q Q K M O S t j l m p 5 G W A q + q 5 9 K d X G e Z g s T o g q 7 s R L h A 2 U g c w 1 W / Z h i Z K a 2 i G v w 0 N X q d a Q 1 l F G l c k 8 p X O 1 U j I z 9 d r h i o E 0 c P d 4 A U v n z C v z T w K p g R f q e m 9 j L + S / y h y X o 1 H D l J b S i 6 6 I N i O q H C j g M p G c E 9 H P o 8 N p H h W 3 F c f 5 4 d T j j h f c s c 8 d H C z I A 5 9 0 4 + n Y 3 c h d n 8 2 L H z j a x Z 6 m a N C k p s K E s Z u U n X m k N O / 4 k c 4 W 3 N l S F g s u 9 b n 2 g m v 7 3 H j B j X 2 O L z j u c y Q 2 0 2 7 Y y y M G q b 1 q h p G m g 6 G 9 8 l Q m U 0 J q f k 1 Z f u N m i C u P a j v P I y p S O / H j 2 E v 5 3 y d s + 8 5 K s q L r U h V / O q m L g c 1 n 2 H K a y t f N s F J X D W 0 u y 3 n M 3 8 / n 8 h q X S N G n J b 3 / 1 6 w p 3 J S 6 t 9 b 1 9 K g y 1 t 1 r G v p v 5 7 J x u r 0 V v t 7 a + b D T 3 N u p 3 t U 1 9 B y 9 Q K 9 Q i N 6 g P f Q O H a E T l K B P 6 D P 6 g r 4 2 v j V + N H 4 2 f p X S 1 Z X K 5 y m q r c b v P 6 d I R V o = < / l a t e x i t > ✓ < l a t e x i t s h a 1 _ b a s e 6 4 = " S 3 M Y 0 A H n z 1 m H F g J w K b f K K m J h j 1 o = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w Z C a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t F 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H l x c b z d Z W a 7 b w s h F W R h N V 6 + h i s / E q 6 s s k 4 y B s w o g x 3 b C l b C 8 n 2 t K E w X Q 9 y g w o k o z I A L r O F I S D 6 e W z T K f 4 r U P 6 O J X a f Y T F M / S 2 R 0 6 4 M R M e O y U n d m h 8 r g D v 4 r q Z T T / 2 c i p U Z k E k Z a A 0 Y 9 h K X J S N + 1 R D Y t k E 1 0 4 U x M Y 0 n t 4 V J X B 7 k a M J 5 i n V V L P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I q w F T 0 X f t S q o 3 z M F m c E F V c h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z G b q t c M V A 2 n g 7 v E S l s 6 Z V + a f B F I D L 9 T 1 3 s Z e y H + V O S 5 H o 4 Y p L a U X X R F t R l Q 5 U M B V I j k n o p 9 H h 9 M 8 K m 4 r j v P D q c e d L L g T n z s 4 W J A H P u n G 0 7 G 7 k b s + m x c / c L S L P U 3 R o E l N h Q l j d y k 7 8 0 h p 3 v E j n S + 4 8 6 U s F l z q c + 0 F 1 / a 5 8 Y I b + x x f c N z n S G y m 3 b C X R w x S e 9 0 M I 0 0 H Q 3 v t q U y m h N T 8 l r L 8 x s 0 Q V x 7 V d p F H V K R 2 4 s e x V / K / T 9 j 2 n Z V k R d e l K v 5 0 U h c D m 8 + w 5 T S V r 5 t h p a 4 a 2 l y W 8 5 h / n s / l L S 6 R o k 9 L e v + v W V O 4 K X X P r O v p U W W s u 9 c 0 9 N / O Z e N s e y t 8 v 7 V z v N P c 2 6 n e 1 T X 0 G r 1 B 7 1 C I P q A 9 9 A k d o V O U I E B f 0 T f 0 v f G j c d P 4 2 f h V S l d X K p + X q L Y a v / 8 A T 8 F D L A = = < / l a t e x i t > v < l a t e x i t s h a 1 _ b a s e 6 4 = " M 3 E A G o 6 G 6 m K Q k u y z A b M Y H O Y 7 Z r E = " > A A A G T n i c j V T L b h M x F H U L K a W 8 U t g B C 4 s I q U i j K l N V g N R N p b Y S O 0 q h T a p M F H k m ni z M h M U z i l k k v d i Y k B z g S c W m Y 5 d J Q G k s Y c 2 v H o o O D b l 6 A N k + K L n S j o p W Q g W M I o s Q 4 6 b l 1 s 1 Z u N 5 m z h V S M s j T o q V + t i u / Y q 6 k u a p S A s 5 c S Y b t h U t p c T b R n l M N 2 M M g O K 0 B E Z Q N e Z g q R g e v k s 0 y l + 6 5 A + T q R 2 H 2 H x D L 3 t k Z P U m E k a O 2 V K 7 N D 4 X A H e x X U z m 3 z s 5 U y o z I K g 8 0 B J x r G V u C g b 9 5 k G a v k E V 0 4 U x M Y s n t 4 V J X B 7 k a M J F i l V V L P M A w z C N U I T C w F O u C Q 2 w A N N 1 J D R c Y B H 0 o L b U j I C C p w 7 K + O W a X k V Yc Q h s d f 1 M N J s M L T X n s p k S k i d 3 l L O v 3 E 9 x K V H u V 3 k E R O J n f h x 7 J X 8 7 x N 2 f G c l e d F 1 q Y o / n d T F w O Y z b D V N 5 e t m 2 F x X D m 0 u 5 / O Y f 1 7 M 5 S 2O S t F n c / r g r 1 l R u C l 1 z 6 z r a a s 0 N t 1 r G v p v 5 6 p x t t M I 3 z d 2 j 3 f r + 4 3 y X d 1 A r 9 E b 9 A 6 F 6 A P a R 5 9 Q C 5 0 i i g B 9 R d / Q 9 9 q P 2 k 3 t Z + 3 X X L q + V v q 8 R J V V + / 0 H c X Z D A A = = < / l a t e x i t > P < l a t e x i t s h a 1 _ b a s e 6 4 = " y 3 a 65 F h M T 8 5 Q 1 a Q r M X 0 K C o i + Q + k = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q 2 k r d 0 V a 0 S Z W J K s / k T m L F L 9 m e J t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w J B P S c Y q E p c Q 3 5 5 z r + / C N Y 8 W o s Y 3 G z c r q v f u 1 B w / X H q 0 / f v L 0 2 f O N z R f n R m Y 6 g b N E M q l b M T H A q I A z S y 2 D l t J A e M y g G Q / 2 C 7 5 5 B d p Q K b 7 Y s Y I O J z 1 B U 5 o Q 6 6 C T o 8 u N e m O r M V 1 4 2 Q h L o 4 7 K d X y 5 W X s V d W W S c R A 2 Y c S Y d t h Q t p M T b W n C Y L I e Z Q Y U S Q a k B 2 1 n C s L B d P J p p h P 8 1 i F d n E r t P s L i K X r b I y f c m D G P n Z I T 2 z c + V 4 B 3 c e 3 M p h 8 7 O R U q s y C S W a A 0 Y 9 h K X J S N u 1 R D Y t k Y V 0 4 U x M Y 0 n t w V J X B 7 k a M J 5 i l V V N P M A w z C N U I T C w F O m S Q 2 w D 1 N V J 8 m o w A P p A W 3 c T K A B B h z V s Y s 1 X I Y Y C q 6 r n 0 p 1 c Z 5 m C x O i C q u w 0 u E 9 Z S B z D V b d m G J k p r a P q / C f V e p 1 p B W U U a V y T y l c 7 V S M j P x 2 u G K g T R w 9 3 g F S + f M K / N P A q m B F + p q b 2 M v 5 L / K H M 1 G o 4 I p L a U X X R F t B l Q 5 U M A w k Z w T 0 c 2 j w 0 k e F b c V x / n h x O N O F 9 y p z x 0 c L M g D n 3 T j 6 d j d y F 2 f z Y s f O N r F n q Z o 0 L i i w o S x u 5 S t e a Q 0 b / m R L h b c x V I W C y 7 1 u e a C a / r c a M G N f I 4 v O O 5 z J D a T d t j J I w a p v a 6 H k a a 9 v r 3 2 V C Z T Q m p + S z n 7 x v U Q l x 7 l d p l H V K R 2 7 M e x Q / n f J 2 z 7 z k q y o u t S F X 8 6 q Y u B z a f Y c p r K 1 0 2 xm a 4 c 2 l z O 5 j H / P J / L W 1 w i R Z f O 6 P 2 / Z k X h p t Q 9 s 6 6 n x 6 W x 7 l 7 T 0 H 8 7 l 4 3 z 7 a 3 w / d b O y U 5 9 7 1 P 5 r q 6 h 1 + g N e o d C 9 A H t o S N 0 j M 5 Q g g B 9 R d / Q 9 9 q P 2 k 3 t Z + 3 X T L q 6 U v q 8 R J V V + / 0 H S R J D D A = = < / l a t e x i t > H < l a t e x i t s h a 1 _ b a s e 6 4 = " b I 9 + Y F p U W B S F P U G D L y n o b T y q z Q o = " > A A A G M n i c j V T L b h M x F H W B Q C m v F n a w s Y g Q L E Z V p q o A q Z t K b a X u K B V t U m W i y u N 4 E i t + y f a 0 i a b z B 2 z h S / g Z 2 C G 2 f A S e z I T p O E X C U u K b c 8 7 1 f f j G s W L U 2 E 7 n + 8 q t 2 3 d a d + + t 3 l 9 7 8 P D R 4 y f r G 0 9 P j U w 1 J i d Y M q l 7 M T K E U U F O L L W M 9 J Q m i M e M d O P J X s F 3 L 4 g 2 V I p P d q b I g K O R o A n F y D r o + P D 1 + X q 7 s 9 m Z L 7 h s h J X R B t U 6 O t 9 o P Y + G E q e c C I s Z M q Y f d p Q d Z E h b i h n J 1 6 L U E I X w B I 1 I 3 5 k C c W I G 2 T z V H L 5 y y B A m U r u P s H C O X v f I E D d m x m O n 5 M i O j c 8 V 4 E 1 c P 7 X J + 0 F G h U o t E b g M l K Q M W g m L u u G Q a o I t m 8 H G i Q L Z m M b 5 T V E C t x c 5 m m C R U k M 1 z z y A R L h G a G R J A B M m k Q 3 g S C M 1 p n g a w I m 0 x G 0 c T Q g m j D k r Z Z Z q e R l A K o a u f Q n V x n m Y N M Z I F f f h J c J G y p D U N V s O y R I l N b V j 3 o T H r l K t S d J E G V U m 9 Z T O 1 U r J T O 6 1 w x V D k s D d 4 w V Z O m d R m X 8 S k Z r w Q t 3 s b e y F / F e Z 0 3 I 0 G p j S U n r R F d J m Q p U D B b n E k n M k h l l 0 k G d R c V t x n B 3 k H n d c c 8 c + t 7 9 f k / s + 6 c b T s T u R u z 6 b F T 9 g t A M 9 T d G g W U M F E W M 3 K X u L S E n W 8 y O d 1 d z Z U h Y 1 l / h c t + a 6 P j e t u a n P 8 Z r j P o d i k / f D Q R Y x k t i r d h h p O h r b K 0 9 l U i W k 5 t e U 5 T d s h 7 D y q L b z L K I i s T M / j r 2 U / 3 3 C l u + s J C u 6 L l X x p 5 O 6 G N h s j i 2 n q X z d H C t 1 1 d B m s p z H 7 M N i L q 9 x W I o h L e m 9 vh f g J X g D Q v A O 7 I J D c A R O A A Y J + A y + g K + t b 6 0 f r Z + t X 6 X 0 1 k r l 8 w w 0 V u v 3 H 1 C b Q y 8 = < / l a t e x i t > H → < l a t e x i t s h a 1 _ b a s e 6 4 = " 1 M X d k D e n j d s t w r C i r l K x p u 7 C Z 0 c = " > A A A G T n i c j V T L b h M x F H U L K a U 8 2 s I O W F h E S E W M q k x V A V I 3 l d p K 7 C i F N q k y U e R x P I k V v 2 R 7 2 k T T 2 f A 1 b O F L 2 P I j 7 B B 4 k g n p O E X C U u K b c 8 7 1 f f j G s W L U 2 E b j x 9 L y r d u 1 l T u r d 9 f u 3 X / w c H 1 j 8 9 G Z k a n G 5 B R L J n U r R o Y w K s i p p Z a R l t I E 8 Z i R Z j w 8 K P j m B d G G S v H J j h X p c N Q X N K E Y W Q d 1 N 5 5 F H N l B H G c f 8 + 7 J V m Q H x K I g D i 6 C 8 a v B y + 5 G v b H d m C y 4 a I S l U Q f l O u 5 u 1 p 5 E P Y l T T o T F D B n T D h v K d j K k L c W M 5 G t R a o h C e I j 6 p O 1 M g T g x n W x S R g 5 f O K Q H E 6 n d R 1 g 4 Q a 9 7 Z I g b M + a x U x Z J G 5 8 r w J u 4 d m q T t 5 2 M C p V a I v A 0 U J I y a C U s e g J 7 V B N s 2 R h W T h T I x j T O b 4 o S u L 3 I 0 Q S z l C q q Se Y B J M I 1 Q i N L A p g w i W w A + x q p A c W j A A 6 l J W 7 j a E g w Y c x Z K b N U y 8 s A U t F z 7 U u o N s 7 D p D F G q r g r L x H W V 4 a k r t m y R x Y o q a k d 8 C o 8 c J V q T Z I q y q g y q a d 0 r l Z K Z n K v H a 4 Y k g T u H i / I w j m z y v y T i N S E F + p q b 2 M v 5 L / K H E V 1 f B U / A c b I E Q v A H 7 4 B 0 4 B q c A g 8 / g C / g K v t W + 1 3 7 W f t V + T 6 X L S 6 X P Y 1 B Z K 6 t / A D k F T O c = < / l a t e x i t > S R (ω, b, v, y + h) < l a t e x i t s h a 1 _ b a s e 6 4 = " i u k J Q p s q c + 9 b r o 7 U h b X t w V t / K q Y = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t F 0 v o A t f A l f 0 x 1 i y 0 / g S S a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t l 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H 8 c V G s 7 X V m i 6 8 b I S V 0 U T V O r r Y b L y K + j L J O A i b M G J M N 2 w p 2 8 u J t j R h U K x H m Q F F k h E Z Q N e Z g n A w v X y a a Y H f O q S P U 6 n d R 1 g 8 R W 9 7 5 I Q b M + G x U 3 J i h 8 b n S v A u r p v Z 9 G M v p 0 J l F k Q y C 5 R m D F u J y 7 J x n 2 p I L J v g 2 o m C 2 J j G x V 1 R A r e X O Z p g n l J N N c 0 8 w C B c I z S x E O C U S W I D P N B E D W k y D v B I W n A b J y N I g D F n Z c x S L a 8 C T E X f t S + l 2 j g P k 8 U J U e V 1 e I m w g T K Q u W b L P i x R U l M 7 5 H V 4 6 C r V G t I 6 y q g y m a d 0 r l Z K Z g q v H a 4 Y S A N 3 j 5 e w d M 6 8 M v 8 k k B p 4 q a 7 3 N v Z C / q v M 8 W w 0 a p j S U n r R F d F m R J U D B V w l k n M i + n l 0 W O R R e V t x n B 8 W H n e y 4 E 5 8 7 u B g Q R 7 4 p B t P x + 5 G 7 v p s X v 7 A 0 S 7 2 N G W D J j U V J o z d p e z M I 6 V 5 x 4 9 0 v u D O l 7 J Y c K n P t R d c 2 + f G C 2 7 s c 3 z B c Z 8 j s S m 6 Y S + P G K T 2 u h l G m g 6 G 9 t p T m U w J q f k t 5 e w b N 0 N c e V T b R R 5 R k d q J H 8 d e y f 8 + Y d t 3 V p K V X Z e q / N N J X Q 5 s P s W W 0 1 S + b o r N d N X Q 5 n I 2 j / n n + V zV p J L p N 2 n H 2 k j I = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S vT T / 2 c i p U Z k E k Z a A 0 Y 9 h K X J S N + 1 R D Y t k E 1 0 4 U x M Y 0 n t 4 V J X B 7 k a M J 5 i n V V L P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I q w F T 0 X f t S q o 3 z M F m c E F V c h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z G b q t c M V A 2 n g 7 v E S l s 6 Z V + a f B F I D L 9 T 1 3 s Z e y H + V O S 5 H o 4 Y p L a U X X R F t R l Q 5 U M B V I j k n o pProof Using similar argument, we do the fixed history arguments. Simply write X = (X 1 , . . . X K ) = X(t) | H t-1 and we first fix θ and consider the greedy policy a with estimator θ. We define λ ⋆ as a diversity constant of X. Also, we define L n := c 0 √ dx max (1 + log dK + n log γ) and set event B n := {X i ∈ B(0, L n ) for all i ∈ [K]}. We determine γ > 0 later. By Lemma 19, we have P[B n ] ≥ 1 -1 γ n . We apply the peeling technique to bound the truncated contexts.E[X a X ⊤ a ] = E[X a X ⊤ a ; B 1 ] + ∞ n=1 E[X a X ⊤ a ; B n+1 \ B n ]By setting α = c 0 √ dx max , β = 1 + log dK, observe that∞ n=1 E[X a X ⊤ a ; B n+1 \ B n ] ⪯ ∞ n=1 L 2 n+1 1 γ n I d ⪯ ∞ n=1 (α(β + n log γ)) 2 1 γ n I d ⪯ ∞ n=1 2α 2 (β 2 + n 2 log 2 γ) 1 γ n I d .If γ ≥ 3α 2 β 2 1 λ⋆ , we have∞ n=1 E[X a X ⊤ a ; B n+1 \ B n ] ⪯ 1 2 λ ⋆ I d .Using Theorem 2, we getλ ⋆ I d ≤ E[X a X ⊤ a ; B 1 ] + 1 2 λ ⋆ I d and hence E[X a X ⊤ a ; B 1 ] ≥ 1 2 λ ⋆ .Finally, we getE[X a X ⊤ a | B 1 ] ≥ 1 2 λ ⋆ .H.9 Proof of Proposition 6Define ∆(X) as the suboptimality gap of X and denote its density as f X (x), x ∈ (R d ) K . By the direct expectation, we getP[∆(X) ≤ ε] = ∆(X)≤ε f X (x)dx = {∆(X)≤ε}∩D f X (x) P[X ∈ D] dx ≤ ∆(X)≤ε f X (x) P[X ∈ D] dx ≤ 1 1 -δ P[∆(X) ≤ ε]holds.By conditioning H t-1 , we define fixed history contexts X = (X ⊤ 1 , . . . X ⊤ K ) similar to previous proofs in Appendix F. We decompose the probability of suboptimality gap asP[∆(X) ≤ ε] = K i=1 P[{∆(X) ≤ ε} ∩ Ω ⋆ i ] = K i=1 E P[{∆(X) ≤ ε} ∩ Ω ⋆ i | {X j = x j } j̸ =i ] = K i=1 E P[{max j̸ =i x ⊤ j θ ⋆ ≤ X ⊤ i θ ⋆ ≤ max j̸ =i x ⊤ j θ ⋆ + ε} | {X j = x j } j̸ =i ]the last equality holds by the definition of Ω ⋆ i . Next we aim to bound P[{maxj̸ =i x ⊤ j θ ⋆ ≤ X ⊤ i θ ⋆ ≤ max j̸ =i x ⊤ j θ ⋆ + ε} | {X j = x j } j̸ =i ]and for the same argument, we only need to bound the maximum density ofP[ X ⊤ i θ ⋆ = y | {X j = x j } j̸ =i ]. and it is enough to bound its one-side decay rate by Lemma 5. Since the conditional density of X i | {X j = x j } j̸ =i , say f 3 (•), has same LAC with constant function L(R), hence it has bounded decay rate by √ dL(R) by Lemma 3. Also the density P[ X ⊤ i θ ⋆ = y | {X j = x j } j̸ =i ] is a section density of f 3 of S R (θ ⋆ , y) for y ∈ [-R, R]. Then we can observe that at least one of the directions of θ ⋆ or -θ ⋆ , the sections S R (θ ⋆ , y) are expanding section in B R . Then by applying Lemma 8, we can bound the one-side decay rate of section density X ⊤ i θ ⋆ | {X j (t) = x j } j̸ =i by √ dL(R) and finally we can bound the maximum density by 3 √ dLR by using Lemma 5. Therefore, by the decomposition we did before, we finally getP[∆(X(t)) ≤ ε] ≤ i∈[K] 3 √ dL(R) ≤ 3K √ dL(R).We have λ ⋆ (t) ≥ c p d1 (L(R)+ 1 R(1-c⋆ ) ) 2 with 1 -c ⋆ = R ′r ≍ 1 by using Proposition 4 and Lemma 14. Hence we get λ ⋆ (t) ≥ c p dL(R) 2 := λ ⋆ . Also, using Proposition 6, we have the margin constant of truncated contexts C∆ is bounded by 1 1-p C ∆ , where C ∆ is defined in Theorem 3. We can see thatReg(T ) ≤ cσ 2 dR 2 C ∆ 1 λ ⋆ (log(T )) 2 ≤ O(d 2.5 R 2 L(R) 2 1 p )holds.If L ≥ √ dc 0 x max (3 + log dK), we can use the same proof of the Theorem 2. For the diversity constant of truncated contexts, it is lower bounded by 1 2 λ ⋆ (t) where λ ⋆ (t) is define in Theorem 2. Also, using Proposition 6, we have the margin constant of truncated contexts C∆ is bounded by 1 1-p C ∆ , where C ∆ is defined in Theorem 3. Combining these observations, we finally can apply Proposition 9 since truncated contexts are also has bounded ψ 1 -norm by x max , and get the wanted result.We can prove it directly by combining the results of Proposition 4 and Proposition 7. This can be obtained directly by combining the results and Proposition 8.We now present the results and proofs to obtain an exact regret bound after the two challenges are addressed. Recall that we define the (unexpected) regret as reg ′ (t) := X a ⋆ (t) (t) ⊤ θ ⋆ -X a(t) (t) ⊤ θ ⋆ and expected regret as reg(t) = E Ht-1,X(t) [reg ′ (t)]. We can achieve logarithmic regret bounds if the contexts meet Challenges 1 and 2.We first present our regret analysis for bounded contexts.Proposition 8 (Regret bound for bounded contexts) For bounded contexts as ∥X i (t)∥ 2 ≤ R, suppose that E[X a(t) X a(t) | H t-1 ] ⪰ λ ⋆ I and C ∆(X(t)) ≤ C ∆ for all t ∈ [T ] and H t-1 . Under the Assumption 1, expected regret of Algorithm 1 is bounded byReg(T ) ≤ cσ 2 R 2 dC ∆ 1 λ ⋆ (log T ) 2 = O(R 2 d C ∆ λ ⋆ ).Next, we present the regret bound result for unbounded contexts, under the satisfaction of two challenges. ).Firstly, set T 0 := c0 λ⋆ R(3 log T + log d). Before starting the proof, we define the good events which satisfy the sufficient concentration of the estimator θt .Definition 17 From now on, in this section, we define the event by E t .E t := {λ min (Σ(t)) ≥ λ ⋆ 4 t}Which is the event that the Gram matrix has a sufficient growth of the minimum eigenvalue. The event E t occurs with high probability according to Corollary 9.Corollary 4 For T 0 = 1 c1λ⋆ R(3 log T + log d), the following holds.P[ T τ =T0 E t ] ≥ 1 2TProof Using the Corollary 9, with probability 1 -1 2T 2 , event E t holds. By the union bound, we get the result.We define the event t τ =T0 E t := E t .Proof We prove it using the similar argument used in Kannan et al. [20] to bound the Gram matrix. We view contexts X i (t) given the history H t-1 as a mixture of X i (t) | B L and X i (t) | B c L . Consider there is an invisible coin toss c s for every time s ∈ [t], and if c s = 1 the contexts are drawn in X(t) | (B L ) K and if c s = 0, it is drawn from X(t) | (B c L ) K . By our choice of high-probability region radius L, for any c s , P[c s = 1] ≥ 1 -1 T 2 holds. Define Σ(t) as the Gram matrix of the contexts sampled from the truncated distribution for all 1 ≤ s ≤ t. For truncated contexts, the Proposition 5 tell us that it has diversity constant with 1 2 λ ⋆ under our choice of L. Then, the following holds by our independence assumption and Lemma 5: X a(τ ) (τ )η τ ) ≤ σ 2 log(T 2 det(Σ(t)) 1/2 ) Concentration 3. In the previous section, we prove that for any t ≥ T 1 ,P[Σ(t) ⪰ 1 8 λ ⋆ tholds with probability 1 -2 T 2 . Combining these three concentrations, we get the following result: with probability 1 -4 T 2 for any t ≥ T 1 , Second inequality holds since under the Concentration 3, Σ(t) ⪰ 1 2 (Σ(t) + I d ). Finally, we obtain the following concentration results. ℓ 2 .∥ θt -θ ⋆ ∥ Σ(t) = ( t τ =1 X a(τ ) (τ )η τ )Σ(t) -1 ( t τ =1 X a(τ ) (τ )η τ ) ≤ 2( t τ =1 X a(τ ) (τ )η τ )(Σ(t) + I d ) -1 ( t τ =1Corollary 7 (ℓ 2 concentration: unbounded contexts) For any t ≥ T 1 , we haveEQUATIONfor some absolute constant c with probability 1 -4 T 2 .We define event G t as the above inequality (17) holds and set G t = T t=T1 G t .Finally, we present a key analysis to bound the regret. Remark that we set T 1 := holds for some absolute constant c > 0.Proof Under any history contained in G t-1 , by using ( 16), with probability 1 -1 T 2 we have holds for some absolute constant c > 0. We define this event as K t . The the (unexpected) regret is bounded by reg ′ (t) ≤ 2e.We now bound the expected regret asE[reg ′ (t); G t-1 ] = E[reg ′ (t); G t-1 ∩ K t ] + E[reg ′ (t); G t-1 ∩ K c t ] ≤ 2eP[reg ′ (t) > 0; G t-1 ∩ K t ] + E[reg ′ (t); G t-1 ∩ K c t ] ≤ 2eP[∆(X(t)) ≤ 2e] + E[reg ′ (t); G t-1 ∩ K c t ] ≤ 6C ∆ e 2 + E[reg ′ (t); G t-1 ∩ K c t ].In the last inequality, we use definition of Challenge 2 and Lemma 7.Peeling technique for tail events. Next we bound the regret E[reg ′ (t) | G t-1 ∩ K c t ]. In the event G t-1 ∩ K c t , we do the peeling technique to bound the expected regret. Let L n = c 0 √ dx max (1 + log dK + n log γ) for n ≥ 1 where we determine γ > 0 later. Then, by results from Appendix I.2, we getP[max i∈[K] |X i (t) ⊤ θ ⋆ | ≥ L n ] ≤ i∈[K] P[|X i (t) ⊤ θ ⋆ | ≥ L n ] ≤ 1 γ n .We define the event V n as {max i∈[K] |X i (t) ⊤ θ ⋆ | ∈ [L n , L n+1 ]}. Then P[V n ] ≤ 1 γ n and E[reg ′ (t); V n ] ≤ 2L n+1 . Set α = c 0 √ dx max , β = 1 + log dK. The regret can be decomposed asE[reg ′ (t); G t-1 ∩ K c t ] ≤ E[reg ′ (t); G t-1 ∩ K c t ∩ V 1 ] + ∞ n=1 E[reg ′ (t); K c t ∩ (V n+1 \ V n )] ≤ 2L 1 P[G t-1 ∩ K c t ] + ∞ n=1 E[reg ′ (t); K c t ∩ (V n+1 \ V n )] ≤ 2L 1 1 T + 2 ∞ n=1 L n+1 1 γ n ≤ 2L 1 1 T + 2 ∞ n=1 α(β + n log γ) 1 γ n ≤ 3L 1 1T holds when γ > (αβ) 3 + T 2 . Now we set γ = (αβ) 3 + T 2 and we haveE[reg ′ (t); G t-1 ] ≤ cC ∆ (σx max √ d log T (t -1)λ ⋆ log KT ) 2 ≤ cσ 2 C ∆ dx 2 max 1 λ ⋆ (t -1) (log T ) 3 .Main proof of the Proposition 9 We apply the result of Proposition 21. We get Next we observe the E[reg ′ (t); G c t-1 ] and we can also bound this using the peeling technique. We define the same L n and V n in the previous Proposition 21E[reg ′ (t)] ≤ cC ∆ dx 2E[reg ′ (t); G c t-1 ] ≤ E[reg ′ (t); V 1 ∩ G c t-1 ] + ∞ n=1 E[reg ′ (t); (V n+1 \ V n ) ∩ G c t-1 ] ≤ 2L 1 P[V 1 ∩ G c t-1 ] + ∞ n=1 E[reg ′ (t); (V n+1 \ V n ) ∩ G c t-1 ] ≤ 2L 1 4 T + 2 ∞ n=1 L n+1 1 γ n ≤ c L 1 T .for some absolute constant c > 0. Then we getE[reg ′ (t)] ≤ cC ∆ dx 2 max 1 λ ⋆ (t -1) (log T ) 3and by summing up, we get the desired result directly. For t ≤ T 1 , just using peeling technique, we can see that E[reg(t)] ≤ cL 1 hence Reg(T 1 ) ≤ cL 1 T 1 ≤ cσ 2 C ∆ dx 2 max 1 λ⋆ (log T ) 4 .In this paper, we considered only context distributions with differentiable densities.• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors 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 of 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. 
regret analysis: 
 We present the main results of our paper. We prove that the regret of the greedy algorithm (Algorithm 1) for linear contextual bandits can be bounded at a logarithmic scale in the time horizon T , provided that the context distribution satisfies the LAC condition with a polynomial function λ.Assumption 1 (Independently distributed contexts) The context sets X (1), . . . , X (T ) are independently distributed across time.Discussion of Assumption 1. 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, 33] . In Assumption 1, 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 √ t-consistency of estimators also assumes independence of context sets [21, 22] . Note that under Assumption 1, context vectors within the same round are permitted to be dependent.We first provide detailed considerations on context boundedness. In the linear contextual bandit setting, ℓ 2 boundedness is commonly assumed. However, for light-tailed distributions (such as Gaussian or exponential), the ℓ 2 norm is unbounded. In such cases, a general approach in the statistical literature is to assume bounded ψ 1 or ψ 2 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 ℓ 2 norm of contexts is commonly assumed. In this paper, for bounded contexts, we consider both truncated contexts (e.g., truncated Gaussian, truncated Cauchy distributions) and naturally bounded contexts (e.g., uniform distribution). For unbounded contexts, we assume a bounded ψ 1 norm, which is a standard assumption for handling light-tailed distributions (e.g., as in [14, 17] , which assume bounded ψ 2 norms).Assumption 2 (Boundedness) For unbounded contexts, we assume ∥X i (t)∥ ψ1 ≤ x max . For bounded contexts, we assume∥X i (t)∥ 2 ≤ x max for all i ∈ [K], t ∈ [T ].The bounded context assumption is widely used in the literature [1, 7, 8, 21, 22, 28] . For unbounded contexts, our assumption of ψ 1 boundedness is notably weaker than the sub-Gaussianity (or ψ 2 ) assumption commonly used in statistical regression literature to handle random design covariates [14, 39] . If ℓ 2 boundedness holds, it automatically implies boundedness of the ψ 1 norm. However, as the analysis differs slightly depending on whether the support is restricted to a bounded ball or is unbounded, we address these cases separately.We first introduce our main result, the regret bound of the greedy algorithm under the LAC condition.Theorem 1 (Regret bound of LinGreedy) Suppose X(t) satisfy the LAC condition with polynomial function L and satisfy Assumptions 1 and 2 for all t, then the cumulative expected regret of LinGreedy (Algorithm 1) is bounded byReg(T ) ≤ O(poly log T ).Explicitly, for unbounded contexts, we haveReg(T ) ≤ O(d 2.5 ).For bounded contexts, refer to Appendix G for explicit results, as we consider several cases.Discussion of Theorem 1. Theorem 1 states that if the contexts are drawn from a distribution in the LAC class, the regret scales as O(poly log T ). While our primary objective is not solely to achieve the sharpest regret bounds, attaining poly-logarithmic regret is highly favorable. Our main goal is to demonstrate that a large class of context distributions satisfies the LAC condition. When they do, a simple greedy algorithm can suffice or even outperform exploration-based algorithms (see numerical experiments in Section 6). The worst-case dependence on d and K for bounded contexts is detailed in Appendix G, where dependencies remain at most polynomial in d and K. As these dependencies vary across distributions, refer to Appendix G for precise information. Proofs for unbounded contexts are provided in Appendix F, with a proof sketch in Appendix C. Proofs for bounded contexts are included in Appendix H. Theorem 1 is the first result to expand the class of admissible distributions for greedy bandit algorithms beyond Gaussian and uniform distributions. Our result demonstrates, for the first time, that distributions in 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.We first present our key results for addressing each of Challenges 1 and 2 stated in Section 4.3.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 Challenge 1. Theorem 2 is the analysis under the case of unbounded contexts, where contexts have full support. A similar result is presented in Appendix G for contexts with bounded or truncated support.Theorem 2 (Diversity constant for unbounded contexts) If unbounded contexts X(t) has the LAC condition with L(x) := A 1 + A 2 x α and satisfies Assumption 2 for all t,λ ⋆ (t) ≥ c 1 1 d • 1 (A 1 + A 2 (R 1 + 2) α ) 2 holds for R 1 := c 2 x max (log d + log K + 2). Here, c 1 , c 2 are absolute constants.Discussion of Theorem 2. Theorem 2 implies that λ ⋆ (t) ≥ Ω( 1 d ), hence ensuring the growth of the minimum eigenvalue of the adapted Gram matrix. In Appendix C.1, we discuss how 1 λ⋆(t) factors into the regret bounds. Note that α is generally small in many distributions. For example, for Gaussian distributions, α = 1, and for exponential distributions, α = 0.Next, we present our result addressing Challenge 2 by computing the suboptimality gap constant C ∆ (t), which satisfies the inequality in Eq.( 2) for every ε > 0. By combining this condition with the estimates for λ ⋆ (t), we can obtain an O(poly(log T )) regret bound in terms of T by applying the analysis techniques of linear contextual bandits with stochastic contexts [7, 8, 19] to our setting. Theorem 3 (Suboptimality gap for unbounded contexts) In the same setup as Theorem 2,C ∆ (t) ≤ c 3 √ d(A 1 + A 2 3 α R α 2 ) 1 ∥θ ⋆ ∥ 2 holds for R 2 = c 4 x max (1 + log K + log d + 1 2 log T ) + 1 and absolute constants c 3 , c 4 > 0.Discussion of Theorem 3. Note that the suboptimality gap constant C ∆ (t) is multiplied linearly in regret bounds [5, 7, 19] . For bounded contexts, we present a similar result in the Appendix G.We provide a high-level proof overview of Theorem 1 in Appendix C. Note that once Challenges 1 and 2 are satisfied, achieving logarithmic regret becomes straightforward, as detailed in Appendix I.The remaining task is to address these two challenges, with a particular focus on bounding the constants λ ⋆ (t) and C ∆ (t). A key implication of the LAC condition is that the density decays slowly at every point. Another useful property is that the LAC condition is preserved under conditioning, meaning that X(t) | {X(t) ∈ A} also satisfies the LAC condition with the same function for any set A ⊂ R K×d . This can be verified using the fact that log fX(t)|{X(t)∈A} (x) = log f X(t) (x) -log P[A],whereP[A] is a constant (see Appendix B.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 X a(t) (t) differs significantly from the distribution of the overall (pre-selected) contexts X(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 are provided in Appendix F. For results on bounded contexts, see Appendix G (and their proofs in Appendix H).In addition to achieving logarithmic regret, an independently valuable result is obtained: the ℓ 2consistency of the estimator θt . 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 1, we achieve∥ θt -θ ⋆ ∥ 2 ≤ O d √ twith high probability (see Corollaries 6 and 7) . This additional result may also facilitate analysis of sample complexity, such as PAC bounds. We define additional notation. For v ∈ R d , defineP v := {x | x ⊤ v = 0}. For S ⊂ R n , we define ∥S∥ ∞ := sup{∥x∥ ∞ , x ∈ S}. For the intervals I ⊂ R and v ∈ R d , define I v := {x | x ⊤ v ∈ I}. For instance, [-1, 1] v := {x | -1 ≤ x ⊤ v ≤ 1}.We define π V (•) as the projection to the subspace V . Also, in the appendix, we writeB R = B d R = {x ∈ R d | ∥x∥ 2 ≤R} with slight abuse of notations. For random variable X, we define supp(X) as the support of X. Recall that we define the expected regret in round t as reg(t) and we define unexpected regret as reg ′ (t). Also for Ω = i∈I E i for disjoint events E i , we use following notationsE [E[X | E i ]] := i∈I P[E i ]E[X | E i ].For event A, we define P[X; A], E[X; A] as P[X ∩ A] and E[X ∩ A] by following Durrett [15] 's notation.In this section we provide the omitted details of LAC and its properties.We first provide more details on the LAC of various distributions, presented in Section 3.2.Gaussian. For densityf (x) = C exp(-(x -µ) ⊤ V (x -µ)), x ∈ R n , where V = 1 2 Σ -1 , ∇ log f = 2V ⊤ (x -µ).First, when V is diagonal, after taking log and gradient, we get∥∇ log f (x)∥ ∞ ≤ 2λ max (V )∥x -µ∥ ∞ ≤ 2λ max (V )(∥x∥ ∞ + ∥µ∥ ∞ ). Since V = 1 2 Σ -1, we get the wanted results. For general V , we can see that∥∇ log f (x)∥ ∞ ≤ 2(max i ∥V i ∥ 1 )∥x -µ∥ ∞ where V i is i-th row of V .LAC of bounded support contexts. If the support of the contexts is bounded in the compact set, ∇ log f is bounded when it is continuous. Therefore, in this case, LAC can be a constant function. Also, if ∥x∥ 2 ≤ R, we have ∥∇ log f (x)∥ ∞ ≤ L(R) by monotonicity of L(•).LAC and context correlations.We claim that LAC L(•) function of random vector x = (x 1 , . . . x n ) related to the correlation structure of x i , x j , rather then dimension n itself. Consider f (x) ∝ exp(-V (x)). Then,∇ log f (x) = -∇V (x) and ∂ i log f (x) = -∂ i V (x) holds.Since L is defined in the sense of supremum norm, to investigate LAC function, the maximum value: max i ∥∂ i V (x)∥ ∞ is important. We claim that it is a dimension-free property, and the correlation structure is more important rather than dimension n itself. For instance, ifx = (x 1 , . . . x n ) is coordinate-wise independent, we have V (x) = V 1 (x 1 ) + V 2 (x 2 ) + • • • + V d (x n ). Hence ∥∇V (x)∥ ∞ = max i ∥V ′ i (x i)∥ ∞ and we can see it is dimension-free value.LAC with shifted mean distribution. Let the mean zero contexts X's density as f (x) with LAC fuction L(•). Then, the shifted contexts with mean µ has density g(x) = f (x + µ) and see that∥∇ log g(x)∥ ∞ = ∥∇ log f (x + µ)∥ ∞ ≤ L(∥x + µ∥ ∞ ) ≤ L(∥x∥ ∞ + ∥µ∥ ∞ ).Hence the density g(x) has LAC with function L ′ (x) = L(x + ∥µ| ∞ ) and when ∥µ∥ ∞ = O (1) , it has the same rate. Thus, LAC does not require that contexts be mean zero, and LAC can be defined for distributions with a general mean.If X = (X ⊤ 1 , X ⊤ 2 ) and X 1 , X 2 are independent, the f X , density of X can be decomposed as fX ((x 1 , x 2 )) = f X1 (x 1 )f X2 (x 2 ). Then, ∇ log f X ((x 1 , x 2 )) = ∇(log f X1 (x 1 ) + log f X2 (x 2 )) = (∇ x1 log f X1 (x 1 ), ∇ x2 log f X2 (x 2 ))holds, and when taking the supremum norm, we get∥∇ log f X ((x 1 , x 2 ))∥ ∞ = max ∥∇ x1 log f X1 (x 1 )∥ ∞ , ∥∇ x2 log f X2 (x 2 )∥ ∞ ≤ max L 1 (∥x 1 ∥ ∞ ), L 2 (∥x 2 ∥ ∞ ) ≤ max(L 1 (∥(x 1 , x 2 )∥ ∞ ), L 2 (∥(x 1 , x 2 )∥ ∞ )).By the definition of the LAC function, we finally obtain the desired result: f has LAC with the function L(x) = max(L 1 (x), L 2 (x)) for x ∈ R.First, we observe that the LAC condition is maintained under conditioning. Let the density ofX = (X ⊤ 1 , . . . X ⊤ K ) ∈ R dK be f (•). For event E := {X ∈ A} for A ⊂ R dK , the conditional density of X given event E is formulated as f |E (x) = f (x)P[E] ∈ R d for x ∈ R dK and the following holds:∇ log f |E (x) = ∇ log f (x) -∇P[E] = ∇ log f (x).It means X | E is also LAC with the same function, hence LAC is robust with conditioning. Especially, if event E has a form of E = {X i ∈ D and X j = x j for j ̸ = i} for some D ⊂ R d , we define the density ofX i | E as f i,E (x) = f (x1,...xi-1,x,xi+1,...x K ) P[E] for x ∈ R d . Then, ∇ x log f i,E (x) = ∇ x log f ((x 1 , . . . x i-1 , x, x i+1 , . . . x K )) -∇P[E] = ∇ x log f ((x 1 , . . . x i-1 , x, x i+1 , . . . x K ))holds. We have∥∇ x log f i,E (x)∥ ∞ ≤ L(∥(x 1 , . . . x i-1 , x, x i+1 , . . . x K )∥ ∞ )which tell us the conditional density also enjoys LAC property with L(•).We summarize above observations in the following lemma, using L(•) is non-decreasing function.Lemma 1 (LAC of conditional contexts) For random vector X = (X ⊤ 1 , . . . X ⊤ K ) ∈ R dK , let it's density has LAC with function L(•). Then for event E := {X ∈ A} for A ⊂ R dK with ∥A∥ ∞ ≤ R, the conditional random vector X | E has LAC with constant function L(R). Especially, if event E has a form of E = {X i ∈ D and X j = x j for j ̸ = i} for some D ⊂ R d with ∥D∥ ∞ ≤ R, conditional random vector X i | E has LAC with L(R).We introduce the property that can compute the LAC of truncated contexts. Truncating the contextsX i (t) to a d-dimensional ball B R ⊂ R d for every i ∈ [K] still satisfies the LAC with a constant, L(R).Lemma 2 (LAC with truncation) Suppose the density of contexts X ∈ R dK satisfies the LAC condition with the function L(•). Consider the case we truncate X into the region (B R ) K and define truncated contexts as X. Then X satisfy the LAC condition with constant function L(R).Proof The density of truncated contexts is calculated asf X (x) = f X (x) P[(B R ) K ]. Then, when taking the log and gradient, we get ∇ log f X (x) = ∇ log f X (x) holds. Since ∥x∥ 2 ≤ R for x ∈ (B R ) K , and L is defined by non-decreasing function, we get ∇ log f X (x) ≤ L(R).Next, we rigorously define the decay rate of a density. Definition 3 (Decay rate) For a density f (x), x ∈ R d , and for a set A ⊂ R d , we say it has decay rate M > 0 whenf (x 1 ) f (x 2 ) ≥ exp(-M |x 1 -x 2 |).for all x 1 , x 2 ∈ A.We next present lemma that the density with a bounded LAC function L has a bounded decay rate in every direction. This property is especially used to control the projected contexts in the whole paper.Lemma 3 (Decay rate and LAC) Suppose a density f is defined in a domain D ⊂ R d and satisfies the LAC condition with constant function L ∈ R. Then the decay rate of f in D is bounded by √ dL.Proof By using Cauchy-Schwarz inequality, we can bound the directional derivative for any v ∈ S d-1 as∂ v f (x) f (x) = v ⊤ ∇f (x) f (x) ≤ ∥v∥ 2 ∥ ∇f (x) f (x) ∥ 2 = ∥ ∇f (x) f (x) ∥ 2 ≤ √ d∥ ∇f (x) f (x) ∥ ∞ ≤ √ dL.Next, by applying Gronwall inequality Lemma 22, we getf (x + hv) f (x) ≥ exp(- √ dLh)for any x, x + hv ∈ D. Since h, v is arbitrary, we get the wanted result.For univariate function, we define one-side decay rate, which is weaker quantity then decay rate.Definition 4 (One-side decay rate) For univariate function g, we say it has one-side decay rate M in set A when for all y, y ′ ∈ A, y < y ′ g(y ′ ) g(y) ≥ exp(-M (y ′y)).Using these observations, we can see that the LAC condition gives the upper bound of the decay rate of density. For the one-dimensional case, for instance, for density with f (x) ∝ exp(-M x) has the decay rate M . Then we can bound the lower bound of variance as 1 M 2 scale and the maximum density is bounded by M . Since Challenge 1 is related to the variance lower bound and Challenge 2 is related to the maximum density (of suboptimality gap), we aim to investigate the decay rate of contexts density.We first present our key lemma, which gives relation between one-side decay rate and variance lower bound. In the following part, we present the rigorous relations between LAC, (one-side) decay rate, variance lower bound and maximum density. M for some M > 0. Suppose g(•) satisfiesg(y ′ ) g(y) ≥ exp(-M |y -y ′ |) for all y, y ′ ∈ I ∩ [-1 M , 1 M ], y < y ′ . Then we get E[Y 2 ] ≥ c 1 M 2 for some absolute constant c > 0.Proof Using Lemma 5, we get the density g is bounded by 3M in the interval [-1 2M , 1 2M ] ∩ I. By applying Lemma 6, we get the wanted result.If I ∩ [-1 M , 1 M ] = ∅ or I ∩ [-1 2M , 1 2M ] = ∅, it means that |Y | ≥ 12M almost surely and we get the result directly.Next, we present another key lemma that gives relation between one-side decay rate and maximum density.Lemma 5 (One-side decay rate leads maximum density) Suppose a real-valued random variable Y has density g and for y 0 ∈ R, [y 0 , y 0 + 1 2M ] ⊂ supp(Y ) for some M > 0. If g satisfies g(y0+h)g(y0) ≥ exp(-M h) holds for any 0 ≤ h < 1 2M , then g(y 0 ) ≤ 3M .Proof Since the integral of the density is 1, we get1 = y∈supp(g) g(y)dx ≥ g(y 0 ) y0+ 1 2M y0 g(y) g(y 0 ) dx ≥ g(y 0 ) y0+ 1 2M y0 exp(-M (y -y 0 ))dx ≥ g(y 0 ) 1 3M therefore g(y 0 ) ≤ 3M holds.Lemma 6 (Maximum density leads variance lower bound) Let Y be an univariate random variable and set A = supp(Y ). For an intervalI = [-1 3M , 1 3M ], if density of Y in I ∩ A is bounded by M , then we have E[Y 2 ] ≥ c 1 M 2 .Proof First, since the density is bounded by M ,P[Y ∈ A ∩ I] ≤ 2 3M × M = 2 3 .Therefore, with a probability greater than1 3 , Y ∈ A ∩ {|x| > 1 3M }. Therefore, E[Y 2 ] ≥ 1 3 ( 1 3M ) 2 = 1 27M 2 .In this section, we briefly outline the high-level proof of Theorem 1 for unbounded contexts. This section provides a summary and high-level sketch of proofs. The full proofs are presented in Appendix E and F. First, we explain the mechanism by which two challenges lead to a logarithmic regret bound, as related to the proof of Theorem 1. Next, we provide a proof sketch for the theorems concerning the two challenges: Theorem 2 and Theorem 3. For bounded contexts, the result statements are in Appendix G, and the proofs are in Appendix H. Since the proof for bounded contexts uses a similar approach to the unbounded case, we first provide a proof sketch of the unbounded results.In this section, we briefly present our proof sketch for the regret bounds. We describe how we can achieve logarithmic regret addressing the two challenges: Challenges 1 and 2.Addressing Challenge 1, we can obtain the O( 1 √ t ) rate ℓ 2 bound of the parameter θt and θ ⋆ by using the combination of the self-normalized concentration [1] and properties that Σ t ⪰ |X ⊤ a(t) ( θt-1 -θ ⋆ )| ≤ cx max √ d log T λ ⋆ × (t -1) , |X ⊤ a ⋆ (t) ( θt-1 -θ ⋆ )| ≤ cx max √ d log T λ ⋆ × (t -1)holds with high probability. Details are in Appendix I.1.However, this resolution in insufficient for the logarithmic regret, it can only makes O( √ T ) regret bound.Challenge 2: Towards logarithmic regret. Furthermore, addressing Challenge 2 (margin condition), we can get logarithmic expected regret upper bound. When the greedy policy select a(t), it means that X a(t) (t) ⊤ θt-1 ≥ X ⊤ a ⋆ (t) θt-1 and by the definition of the optimal arm,X a(t) (t) ⊤ θ ⋆ ≤ X ⊤ a ⋆ (t) θ ⋆ holds. Ensuring Challenge 1, we get reg ′ (t) := X a ⋆ (t) (t) ⊤ θ ⋆ -X a(t) (t) ⊤ θ ⋆ ≤ 2cx max √ d log T λ ⋆ × (t -1).Next, we define the event E as the event of X(t) with regret occurring as reg ′ (t) > 0. Under the event E, the suboptimality gap of X(t) satisfies∆(X(t)) ≤ reg ′ (t) ≤ 2cx max √ d log T λ ⋆ × (t -1)and by overcoming Challenge 2, we getP X(t) [reg ′ (t) > 0] ≤ C ∆ × 2cx max √ d log T λ ⋆ × (t -1) + 1 √ T ≤ 3cx max C ∆ √ d log T λ ⋆ × (t -1)By combining two things, we can bound the expected regret asE X(t) [reg ′ (t)] ≤ 3cx max C ∆ √ d log T λ ⋆ × (t -1) × 2cx max √ d log T λ ⋆ × (t -1) = 6c 2 x 2 max C ∆ d log T λ ⋆ × (t -1).This observation enable us to get logarithmic regret bound. Using this argument, our only remaining goal is bounding two constants in Challenge 1 and 2. We summarize our above observation in the following Lemma.Lemma 7 Assume that ∥X i (t)∥ 2 ≤ R for some R > 0 for all i ∈ [K]. Also assume that the estimator ∥ θt-1 -θ ⋆ ∥ ≤ A 1 √ t-1 holds for some constant A > 0. Then the (unexpected) regret in round t is bounded by reg ′ (t) ≤ 2AR 1 √ t-1 . Furthermore, under the margin condition (Challenge 2), we get E X(t) [reg ′ (t)] ≤ 6R 2 A 2 C ∆ 1 t-1 to hold.Using the above observation, we can get a logarithmic regret bound when ∥X i (t)∥ 2 is bounded. For bounded ∥X i (t)∥ ψ1 case, we use the peeling technique. Given the history H t-1 , θt-1θ ⋆ is a fixed vector, and using the results from Appendix I.2, we can bound |X i (t) ⊤ v|, v ∈ { θt-1θ ⋆ , θ ⋆ } with high probability. Hence we can do the similar arguments, and details are presented in Appendix I.Now, we summarize our proof strategy to prove diversity (Challenge 1) and suboptimality gap (Challenge 2). First, we consider the problem with fixed history setup, which do analysis under the given history H t-1 . We set history-conditioned contexts asX := X(t) | H t-1 and X = (X ⊤ 1 , . . . X ⊤ K ), X i ∈ R d .We describe more about this history fixing in the next Appendix E. Under the given event H t-1 , θt-1 is a deterministic value and no longer random. Thus, the policy a(t), conditioned on H t-1 , is a greedy policy with respect to θt-1 , making it deterministic as well. To address any θt-1 , we propose an analysis that applies to any θ ∈ R d . In Appendix E.1, we argue that it suffices to bound this variance for any fixed θ. Since we fix θ, which is the corresponding value of θt-1 under the given history H t-1 , we define the policy-selected arm a = arg max X ⊤ i θ. The main difficulty is that the property of the selected contexts X a for a = arg max X ⊤ i θ is difficult to analyze. Hence we do the conditioning to the event, which the policy selects a certain arm i. Also, recall that we defined ∆(X) := X ⊤ a ⋆ θ ⋆max i̸ =a ⋆ X ⊤ i θ ⋆ . Next, we introduce our two important goals to achieve two challenges.Goal 1. For any θ, v ∈ S d-1 and greedy policy w.r.t. θ, we aim find the lower bound ofE[vX a X ⊤ a v].Goal 2. For fixed θ ⋆ , our aim is to find the upper bound of C ∆ that satisfiesP[∆(X) ≤ ε] ≤ C ∆ ε + 1 √ T .It is straightforward that when we achieve Goal 1, then Challenge 1 can be achieved easily since Goal 1 is preparing for all greedy policy with θ.Before we do all the previous steps, we start by truncating our contexts X with high-probability regions. Since X i has bounded ψ 1 norm as x max , roughly speaking, there exists set D ⊂ R d with ∥D∥ ∞ = O(1) andP[X ∈ D K ] ≈ 1.We can view X as a mixture of X | {X ∈ D K } and X | {X ∈ (D K ) c } and with high probability, X is sampled from the distribution X | {X ∈ D K }. In this section (Appendix C), since we are providing proof sketch, so we just regard X is sampled from the distribution with bounded supportD K where ∥D∥ ∞ = O(1). At Appendix B.3, we observed that X | {X ∈ D K } also has LAC and since ∥D∥ ∞ = O(1), it has constant LAC with L(∥D∥ ∞ ) = L( O(1)) = O(1) since L is polynomial.So only for this section, we assume that X has bounded support D K and it has bounded constant LAC function L = O(1). For rigorous proof and justification, we provide them throughout Appendix E and Appendix F.Next, we start to bound the constants in two challenges. Before that, we present event deompositions for our analysis.Definition 5 (Event decomposition 1) We define the event {a = i} as Ω i and Ω i ({x j } j̸ =i ) := {a = i} ∩ {X j = x j for all j ̸ = i }.Pick and v ∈ S d-1 . We can decompose the variance term asE[v ⊤ X a X ⊤ a v] = E[E[v ⊤ X a X ⊤ a v | Ω i ]] = E[E[v ⊤ X i X ⊤ i v | Ω i ]] = E[E[v ⊤ X i X ⊤ i v | Ω i ({x j } j̸ =i )]].For notationsE[E[• | •]],please refer Appendix A. From now on, we aim to boundEQUATIONfor any i, {x j } j̸ =i . Hence we investigate the property of the conditional densityX i | Ω i ({x j } j̸ =i )and especially we are interested at density of projected conditional contextsEQUATIONWe define new event decompositions for bounding suboptimality gap. Under the fixed history, seta ⋆ := arg max i∈[K] X ⊤ i θ ⋆ .Definition 6 (Event decomposition 2) We define the event {a ⋆ = i} as Ω ⋆ i andΩ ⋆ i ({x j } j̸ =i ) := {a ⋆ = i} ∩ {X j = x j for all j ̸ = i }.Next, we aim to bound C ∆ , which is another key constant in the Challenge 2. Define the optimal arm a ⋆ = arg max X ⊤ i θ ⋆ and suboptimal arm a ′ = argmax i̸ =a ⋆ X ⊤ i θ ⋆ . By the definition, for any ε > 0, we have to calculateP[∆(X) ≤ ε] = P[X ⊤ a ⋆ θ ⋆ -X ⊤ a ′ θ ⋆ ≤ ε] = E[P[X ⊤ a ⋆ θ ⋆ -X ⊤ a ′ θ ⋆ ≤ ε | Ω ⋆ i ]] = E[P[X ⊤ a ⋆ θ ⋆ -X ⊤ a ′ θ ⋆ ≤ ε | Ω ⋆ i ({x j } j̸ =i )]] = E[P[X ⊤ i θ ⋆ -max j̸ =i x ⊤ j θ ⋆ ≤ ε | Ω ⋆ i ({x j } j̸ =i )]]then we aim to boundP[max j̸ =i x ⊤ j θ ⋆ ≤ X ⊤ i θ ⋆ ≤ max j̸ =i x ⊤ j θ ⋆ + ε | Ω ⋆ i ({x j } j̸ =i )]and hence we investigate the properties of the conditional densityEQUATIONIt is enough to bound the maximum density ofX ⊤ i θ ⋆ | Ω ⋆ i {x j } j̸ =i since if it is bounded by U , we can see that P[max j̸ =i x ⊤ j θ ⋆ ≤ X ⊤ i θ ⋆ ≤ max j̸ =i x ⊤ j θ ⋆ + ε | Ω ⋆ i ({x j } j̸ =i )] ≤ U εholds and we can set C ∆ = U .In the previous Appendix B. 3 and Lemma 1, we saw that LAC is preserved for conditioning. Our conditioned contexts for interest,X i | Ω i ({x j }) and X i | Ω ⋆ i ({x j }) is conditioning with events such as X i | {X j = x j for all j ̸ = i, X ⊤ i θ ≥ max j̸ =i x ⊤ j θ}, which meets condition of Lemma 1. Then we can apply Lemma 1 and we get that these two conditional densityX i | Ω i ({x j }), X i | Ω ⋆ i ({x j }) also have LAC with bounded constant function L.Lemma 4 tell us that bounded one-side decay rate of density guarantees the lower bound of the variance. Lemma 5 tell us the bounded one-side decay rate of density guarantee the maximum density.In summary, we need to find the lower bound of equation ( 4) and the maximum density of (5) . We present Lemma 4 and 5, which tell us that if we can bound the one-side decay rate, then we can bound variance of (4) and maximum density of (5) . By the property that LAC is preserved under conditioning, we can bound the decay rate ofX i | Ω i ({x j } j̸ =i ) and X i | Ω ⋆ i ({x j } j̸ =i ) by √ dL, bycombining Lemma 3 and LAC property of conditional contexts. However, our interests are projected contexts, defined asX ⊤ i v | Ω i ({x j } j̸ =i ) and X ⊤ i θ ⋆ | Ω ⋆ i ({x j } j̸ =i) which are projected contexts with some direction v and θ ⋆ . In the remaining part, we aim to bound the one-side decay rate of these projected random variables densities to apply Lemma 4 and 5.After the decomposition (by conditioning), we proceed with the following steps:Decomposition by conditioning → LAC of conditional densities → Bounding one-side decay rate of (4) and ( 5) → Bounding two key constants in two Challenges Using Lemma 4 and 5.Support of Conditional Densities. We first observe the support of the conditional densityX i | Ω i ({x j } j̸ =i ). By the definition of Ω i , the arm i should be optimal under the greedy policy θ in this event. Therefore, its support is restricted to{x ∈ D | x ⊤ θ ≥ max j̸ =i x ⊤ j θ}.Next, we consider the density of projected contexts,X ⊤ i v | Ω i ({x j } j̸ =i ). Since the support of X i | Ω i ({x j } j̸ =i ) is of the form {x ∈ D | x ⊤ θ ≥ max j̸ =i x ⊤j θ}, our projected density is an integrated form:P[X ⊤ i v = y | Ω i ({x j } j̸ =i )] = {x∈D|x ⊤ θ≥max j̸ =i x ⊤ j θ}∩{x|x ⊤ v=y} P[X i = x | Ω i ({x j } j̸ =i )] dx.Geometrically, this represents the total density at the intersection of the hyperplanes {x | x ⊤ v = y} and the set {x ∈ D | x ⊤ θ ≥ max j̸ =i x ⊤ j θ}. We refer to these as section densities, as they represent the total density of sections sliced by the hyperplane {x | x ⊤ v = y}. Further discussion is provided in Appendix D.X i | Ω i ({x j } j̸ =i has bounded decay rate √ dL = O( √ d),we prove that the projected densities also have bounded one-side decay rate of O( √ d). Lastly, by applying Lemma 4 and can prove the quantityE[v ⊤ X i X ⊤ i v | Ω i ({x j } j̸ =i )] ≥ c 1 dfor some c = O(1). Also, using Lemma 5, we can prove that the density of ( 5) has bounded density √ dL and we can prove thatC ∆ = O( √ d).In this section, we define sections and section densities and investigate their properties. Previously in Appendix C, we discussed decomposition by conditioning, and our interest became the properties of conditioned contexts, the form ofX i | Ω i ({x j } j̸ =i ) and X i | Ω ⋆ i ({x j } j̸ =i ).Our first goal is to bound the variance of projected contexts, such asX ⊤ i v | Ω i ({x j } j̸ =i ) for all v ∈ R d .To do that, we investigate the projected density ofX ⊤ i v = y | Ω i ({x j } j̸ =i ).To apply Lemma 4 and Lemma 5, we only need to bound the one-side decay rate of that projected density. We saw that its density is the total density of intersections with {x | x ⊤ θ ≥ max j̸ =i x ⊤ j θ} and hyperplane {x | x ⊤ v = y}. We can view it as sections sliced by hyperplanes, and we provide some theory related to sections and section densities.In the proof strategy (Appendix C), we aims to bound the one-side decay rate and maximum density of conditional density,X ⊤ i v | Ω i ({x j } j̸ =i ) and X ⊤ i θ ⋆ | Ω ⋆ i ({x j } j̸ =i ).Recall that we define one-side decay rate of univariate density g (Definition 4) at Appendix C as a constant M satisfying g(y ′ ) g(y)≥ exp(-M (y ′ -y))for all y < y ′ .As we discussed in Appendix C, we have to deal with section densities. If the support ofX i | Ω i ({x j } j̸ =i ) is A, then the density of X ⊤ i v | Ω i ({x j } j̸ =i ) becomes the total density in the sections A ∩ {x | x ⊤ v = y}. This argument also works for the X i | Ω ⋆ i ({x j } j̸ =i ) and X ⊤ i θ ⋆ | Ω ⋆ i ({x j } j̸ =i). We already discussed that LAC is maintained under the conditioning, especially the conditioning to event Ω i ({x j } j̸ =i ) and Ω ⋆ i ({x j } j̸ =i ) in the Lemma 1.Our remaining goal is to bound the one-side decay rate of section density. To build some general theory, we first define sections and section densities.Definition 7 (Sections) For the set A ⊂ R d and v ∈ S d-1 we define sections asSec(A, v, y) := A ∩ {x | x ⊤ v = y} for y ∈ R.This means that section is the intersection of region A and hyperplane {x ∈R d | x ⊤ v = y}.Definition 8 (Section density) We define the section density of the region A. Let f be the density defined in the region A ⊂ R d . Then we define g(y) is the section density of Sec(A, v, y) asg(y) = x∈Sec(A,v,y) f (x)dx. Remark 1 If the density of X ∈ R d is f , the section density corresponds to the density of X ⊤ v for v ∈ S d-1 .Next, we define the areas with special section structures: equal sections and expanding sections. First, we define equal sections, the area whose section with direction v is equal.Definition 9 (Equal sections) We define the set A have equal sections with v ∈ S d-1 when Sec(A, v, y) is the congruence of shapes for y > 0.Next, we define expanding sections, where the sections of A with direction v expand when y increases.We define the sections of A with direction v are expanding sections whenSec(A, v, y) + hv ⊂ Sec(A, v, y + h)for every h > 0. Technically, equal sections are included in expanding sections.< l a t e x i t s h a 1 _ b a s e 6 4 = " P P A a g 2Q 5 f Z E m f C + Y b H H x b q O / 4 D U = " > A A A G T X i c j V R N b x M x E H U L o a V 8 t X C j F 4 s I q Y h V l a 0 q Q O q l q K 3 E j V J o k y o b R V 7 H m 1 j x l 2 x v m 2 i 7 B 3 4 N V / g l n P k h 3 B D C m 2 x I 1 y k S l j a e z H v j G T + P J l a M G t t o / F h a v n W 7 d m d l 9 e 7 a v f s P H j 5 a 3 3 h 8 Z m S q M T n F k k n d i p E h j A p y a q l l p K U 0 Q T x m p B k P D w q 8 e U G 0 o V J 8 s m N F O h z 1 B U 0 o R t a 5 u u u b k V R E I y u 1 Q J x k H w n O t 9 4 G F 8 H 4 5 e B F d 7 3 e 2 G 5 M F l w 0 w t K o g 3 I d d z d q T 6 O e x C k n w m K G j G m H D W U 7 G d K W Y k b y t S g 1 R C E 8 R H 3 S d m a R 0 n S y y S 1 y + N x 5 e j C R 2 n 3 C w o n 3 e k S G u D F j H j s m R 3 Z g f K x w 3 o S 1 U 5 u 8 6 W R U q N Q S g a e J k p R B K 2 E h C e x R T b B l Y 1 g 5 U S A b 0 z i / K U v g 9 q J G E 8 x K q r A m l Q e Q C C e E k 5 Y E M G E S 2 Q D 2 N V I D i k c B H E p L 3 M b R k G D C m L N S Z q m W l w G k o u f k S 6 g 2 L s K k M U a q e C q v E N Z X h q R O b N k j C 5 D U 1 A 5 4 1 T 1 w N 9 W a J F U v o 8 q k H t O F W i m Z y T 0 5 3 G V I E r h 3 v C A L 5 8 x u 5 p 9 E p C a 8 Y F e 1 j b 2 U / 7 r m a N o a F Z / S U n r Z F d J m S J V z C n K J J e d I 9 L L o K M + i 4 r X i O D v K P e x k j p 3 4 2 O H h H D z 0 Q d e e D t 2 L 3 P P Z r P g D o z 3 o c Q q B x h U W R I z d x G z N M i V Z y 8 9 0 P s f O F 6 q Y Y 4 m P N e d Y 0 8 d G c 2 z k Y 3 y O c R 9 D s c n b Y S e L G E n s V T 2 M N O 0 P 7 J X H M q k S U v N r z O k v r I e w j C i 3 b h Z R k d i x n 8 d e y v 8 + Y c c P V p I V q l f m 2 c S 3 W K b y e R P f l F c 2 b S a n / Z i 9 n / X l N Q x L 0 a N T + O C v W W G 4 L n U j 2 G l 6 X B p r b p q G / u x c N M 5 2 t s N X 2 7 s f d u v 7 2 + V c X Q W b 4 B n Y A i F 4 D f b B O 3 A M T g E G n 8 E X 8 B V 8 q 3 2 v / a z 9 q v 2 e U p e X y p g n o L L u r P w B 1 e 1 M z g = = < / l a t e x i t > Sec(A, v, y + h) < l a t e x i t s h a 1 _ b a s e 6 4 = " J Y N R W 6 1 q w C d m K G n 6 D V 8 A J U j Y i d Q = " > A A A G S 3 i c j V T N b h M x E H Y L g V L + W j g B F 4 s I q U i r K F t V g N R L U V u J G 6 X Q J l U 2 i r y O N 7 H i P 9 n e N t F 2 x d N w h S f h A X g O b o g D 3 m R D u k 6 R s L T x Z L 5 v P O P P o 4 k V o 8 Y 2 m z 9 W V m / c r N 2 6 v X Z n / e 6 9 + w 8 e b m w + O j U y 1 Z i c Y M m k b s f I E E Y F O b H U M t J W m i A e M 9 K K R / s F 3 j o n 2 l A p P t m J I l 2 O B o I m F C P r X L 2 N J 5 F U R C M r t U C c Z B 8 J z r f e B u f B 5 G V v o 9 5 s N K c L L h t h a d R B u Y 5 6 m 7 W n U V / i l B N h M U P G d M K m s t 0 M a U s x I / l 6 l B q i E B 6 h A e k 4 s 0 h o u t n 0 D j l 8 4 T x 9 m E j t P m H h 1 H s 1 I k P c m A m P H Z M j O z Q + V j i v w z q p T d 5 0 M y p U a o n A s 0 R J y q C V s B A E 9 q k m 2 L I J r J w o k I 1 p n F + X J X B 7 U a M J 5 i V V W N P K A 0 i E E 8 I J S w K Y M I l s A A c a q S H F 4 w C O p C V u 4 2 h E M G H M W S m z V M u L A F L R d / I l V B s X Y d I Y I 1 U 8 l F c I G y h D U i e 2 7 J M l S G p q h 7 z q H r q b a k 2 S q p d R Z V K P 6 U K t l M z k n h z u M i Q J 3 D u e k 6 V z 5 j f z T y J S E 1 6 w q 9 r G X s p / X X M 8 a 4 2 K T 2 k p v e w K a T O i y j k F u c C S c y T 6 W X S Y Z 1 H x W n G c H e Y e d r z A j n 3 s 4 G A B H v i g a 0 + H 7 k b u + W x W / I H R L v Q 4 h U C T C g s i x q 5 j t u e Z k q z t Z z p b Y G d L V S y w x M d a C 6 z l Y + M F N v Y x v s C 4 j 6 H Y 5 J 2 w m 0 W M J P a y H k a a D o b 2 0 m O Z V A m p + R X m 7 B f W Q 1 h G l F s v i 6 h I 7 M T P Y y / k f 5 + w 7 Q c r y Q r V K 9 N s 6 l s u U / m 8 q W / G K 5 s 2 k 7 N + z N 7 P + / I K h q X o 0 x m 8 / 9 e s M F y X u g H s N D 0 q j X U 3 T U N / d i 4 b p 9 u N 8 F V j 5 8 N O f a 9 R z t U 1 8 A w 8 B 1 s g B K / B H n g H j s A J w O A z + A K + g m + 1 7 7 W f t V + 1 3 z P q 6 k o Z 8 x h U 1 q 3 a H x r 5 T C c = < / l a t e x i t > Sec(A, v, y) < l a t e x i t s h a 1 _ b a s e 6 4 = " a 0 k g B g y s l d n Q 3 V + 2 4 y P / r m u x M Z k = " > A A A G M X i c j V T L b h M x F H U L g V I e b W E H G 4 s I i c U o y l Q V I H V T 1 F Z i R 1 v R J l U m q j y T O 4 k V v 2 R 7 2 k T T f A F b + B K + p j v E l p / A k 0 x I x y k S l h L f n H O u 7 8 M 3 j h W j x j a b N y u r 9 + 7 X H j x c e 7 T + + M n T Z x u b W 8 / P j M x 0 A q e J Z F K 3 Y 2 K A U Q G n l l o G b a W B 8 J h B K x 7 u F 3 z r E r S h U n y x Y w V d T v q C p j Q h 1 k H H H y 8 2 6 8 1 G c 7 r w s h G W R h 2 V 6 + h i q / Y y 6 s k k 4 y B s w o g x n b C p b D c n 2 t K E w W Q 9 y g w o k g x J H z r O F I S D 6 e b T T C f 4 j U N 6 O J X a f Y T F U / S 2 R 0 6 4 M W M e O y U n d m B 8 r g D v 4 j q Z T T 9 0 c y p U Z k E k s 0 B p x r C V u C g b 9 6 i G x L I x r p w o i I 1 p P L k r S u D 2 I k c T z F O q q K a Z B x i E a 4 Q m F g K c M k l s g P u a q A F N R g E e S g t u 4 2 Q I C T D m r I x Z q u V V g K n o u f a l V B v n Y b I 4 I a q 4 D i 8 R 1 l c G M t d s 2 Y M l S m p q B 7 w K D 1 y l W k N a R R l V J v O U z t V K y c z E a 4 c r B t L A 3 e M l L J 0 z r 8 w / C a Q G X q i r v Y 2 9 k P 8 q c z Q b j Q q m t J R e d E W 0 G V L l Q A F X i e S c i F 4 e H U 7 y q L i t O M 4 P J x 5 3 s u B O f O 7 g Y E E e + K Q b T 8 f u R u 7 6 b F 7 8 w N E u 9 j R F g 8 Y V F S a M 3 a V s z y O l e d u P d L 7 g z p e y W H C p z 7 U W X M v n R g t u 5 H N 8 w X G f I 7 G Z d M J u H j F I 7 X U 9 j D T t D + y 1 p z K Z E l L z W 8 r Z N 6 6 H u P Q o t 4 s 8 o i K 1 Y z + O v Z L / f c K 2 7 6 w k K 7 o u V f G n k 7 o Y 2 H y K L a e p f N 0 U m + n K o c 3 l b B 7 z z / O 5 v M U l U v T o j N 7 / a 1 Y U b k r d M + t 6 e l Q a 6 + 4 1 D f 2 3 c 9 k 4 2 2 6 E 7 x o 7 x z v 1 v U b 5 r q 6 h V + g 1 e o t C 9 B 7 t o U / o C J 2 i B A H 6 i r 6 h 7 7 U f t Z v a z 9 q v m X R 1 p f R 5 g S q r 9 v s P G n N C 8 Q = = < / l a t e x i t > A < l a t e x i t s h a 1 _ b a s e 6 4 = " S 3 M Y 0 A H n z 1 m H F g J w K b f K K m J h j 1 o = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w Z C a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t F 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H l x c b z d Z W a 7 b w s h F W R h N V 6 + h i s / E q 6 s s k 4 y B s w o g x 3 b C l b C 8 n 2 t K E w X Q 9 y g w o k o z I A L r O F I S D 6 e W z T K f 4 r U P 6 O J X a f Y T F M / S 2 R 0 6 4 M R M e O y U n d m h 8 r g D v 4 r q Z T T / 2 c i p U Z k E k Z a A 0 Y 9 h K X J S N + 1 R D Y t k E 1 0 4 U x M Y 0 n t 4 V J X B 7 k a M J 5 i n V V L P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I q w F T 0 X f t S q o 3 z M F m c E F V c h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z G b q t c M V A 2 n g 7 v E S l s 6 Z V + a f B F I D L 9 T 1 3 s Z e y H + V O S 5 H o 4 Y p L a U X X R F t R l Q 5 U M B V I j k n o p 9 H h 9 M 8 K m 4 r j v P D q c e d L L g T n z s 4 W J A H P u n G 0 7 G 7 k b s + m x c / c L S L P U 3 R o E l N h Q l j d y k 7 8 0 h p 3 v E j n S + 4 8 6 U s F l z q c + 0 F 1 / a 5 8 Y I b + x x f c N z n S G y m 3 b C X R w x S e 9 0 M I 0 0 H Q 3 v t q U y m h N T 8 l r L 8 x s 0 Q V x 7 V d p F H V K R 2 4 s e x V / K / T 9 j 2 n Z V k R d e l K v 5 0 U h c D m 8 + w 5 T S V r 5 t h p a 4 a 2 l y W 8 5 h / n s / l L S 6 R o k 9 L e v + v W V O 4 K X X P r O v p U W W s u 9 c 0 9 N / O Z e N s e y t 8 v 7 V z v N P c 2 6 n e 1 T X 0 G r 1 B 7 1 C I P q A 9 9 A k d o V O U I E B f 0 T f 0 v f G j c d P 4 2 f h V S l d X K p + X q L Y a v / 8 A T 8 F D L A = = < / l a t e x i t > v Figure 2:Illustration of expanding section's example. The section with direction v is expanding when y increases: y to y + h.Recall that we define one-side decay rate of univariate density g (Definition 4) at Appendix C as a constant M satisfyingg(y ′ ) g(y) ≥ exp(-M (y ′ -y))for all y < y ′ . Then, how to bound the (one-side) decay rate of the section density? We present a technique to bound the (one-side) decay rate of section densities defined in equal and expanding sections.Lemma 8 (One-side decay rate: equal and expanding sections) For A ⊂ R d , v ∈ R d and y ∈ R, a density f has support A and has a bounded decay rate M . Assume that the sections of A with the direction v are expanding sections. We define the section density of Sec(A, v, y) as g(y) then we have for any y 1 < y 2 :g(y 1 ) g(y 2 ) ≥ exp(-M |y 1 -y 2 |).Proof Since the section is expanding with the direction v, we can observe for any h > 0,g(y + h) g(y) = Sec(A,v,y+h) f (x)dx Sec(A,v,y) f (x)dx ≥ Sec(A,v,y) f (x) exp(-M h)dx h Sec(A,v,y) f (x)dx ≥ exp(-M h).The second inequality holds since the section is expanding and using Lemma 3. Since equal sections are also expanding sections, we end the proof. This section aim to provide key propositions to prove Theorem 2 and Theorem 3. Our two challenges aim to boundEQUATIONWe define X(t) = (X 1 (t) ⊤ , . . . , X K (t) ⊤ ) ∈ R dK . Under the given event H t-1 , θt-1 is a deterministic value and no longer random.In the definition of the diversity constant, we recall that the expection is taken with respect to X(t) and history H t-1 . In round t, for any fixed history H t-1 , we perform the greedy policy with the estimator θt-1 . Hence, when the entire set of contextsX(t) = (X 1 (t) ⊤ , . . . , X K (t) ⊤ ) is revealed, a(t) is determined immediately given the history H t-1 .Then the exact statement is:"In round t, for any given historyH t-1 , E X(t) [X a(t) (t)X a(t) (t) ⊤ ] ⪰ λ ⋆ I dholds with some λ ⋆ > 0."In the proof, we proved a stronger statement:"For any greedy policy with any θ ∈ R d and selected arm a(t) with that policy,E X(t) X a(t) (t)X a(t) (t) ⊤ ⪰ λ ⋆ I d holds with some λ ⋆ > 0."We prove a stronger quantity (second argument), for any given parameterθ ∈ R d , define a θ (X(t)) := argmax i∈[K] X i (t) ⊤ θ and define λ ⋆ (t) := min ∥θ∥2=1 λ min E t [X a θ (X(t)) X ⊤ a θ (X(t))] . Since θt-1 can be arbitrary value, we prepare for all greedy policy w.r.t. θ ∈ S d-1 . Then the new defined λ ⋆ (t) satisfies equation (1) and we discuss this in Appendix E.Thus, the policy a(t), conditioned on H t-1 , is a greedy policy with respect to θt-1 , making it deterministic as well. To address any θt-1 , we propose an analysis that applies to any θ ∈ R d , aiming to bound the variance of the selected contexts. In Appendix E.1, we argue that it suffices to bound this variance for any fixed θ.min ∥θ∥2=1 λ min E[X a θ (X(t)) (t)X ⊤ a θ (X(t))(t) ] Note that a θ (X(t)) is defined as arg max i∈[K] X i (t) ⊤ θ. This quantity is equal to min ∥θ∥2=1,∥v∥2=1 E t |v ⊤ X a θ (X(t)) (t)| 2and we prove this lower bound for any θ and v. In summary, our aim is to prove that for any history H t-1 and θ, v, we aim to boundEQUATION)To bound the margin constant, our aim is to prepare for all θ ⋆ , since the true model parameter θ ⋆ also can be arbitrary.We aim to find a class of density F such that if X(t) ∈ F, then equation ( 7) is lower bounded for any θ, v. Similarly, we aim to find the class of density G, if X(t) ∈ G, then equation ( 6) can be upper bounded for any θ ⋆ ∈ R d .1. We first prove that for fixed θ, v, for densities with LAC and its support satisfies some geometric conditons, we can bound equation ( 7). 2. We also prove that for fixed θ ⋆ , for densities with LAC and its support satisfies some geometric conditions, we can bound equation ( 6). 3. Next, we prove that the densities with LAC and bounded ψ 1 norm, for any give θ, v we can truncate it with high probability region to the densities contained in class of 1. 4. Lastly, we prove that for the densities with LAC and bounded ψ 1 norm, for any given θ ⋆ we can truncate it with high probability region to the densities contained in class of 2.In this section, we provide the results of 1 and 2. And in the next Appendix F, we proceed to 3 and 4. Now, we build the theory with the assumptions that θ, v and H t-1 are fixed. We assume that random vectorsZ = (Z ⊤ 1 . . . Z ⊤ K ), Z i ∈ R d arise from some distribution with LAC L(•).The Z represents the history-conditioned contexts, but to build the general theory, we use the notation of Z.We fix arbitrary θ ∈ R d and define random index variablea = argmin i Z ⊤ i θ.We also fix v ∈ S d-1 and first aim to boundE[v ⊤ Z a Z ⊤ a v].We next define C ∆ as the margin constant of the Z with the parameter θ ⋆ which satisfiesP[∆(Z) ≤ ε] ≤ C ∆ ε + 1 √ T .where ∆(Z) is a suboptimality gap, defined similarly in Section 4.Our goal is to find the lower bound ofE[v ⊤ Z a Z ⊤ a v] for any v ∈ S d-1and from now on, we fix the arbitrary v ∈ S d-1 . Then, we aim to boundE[v ⊤ Z a Z ⊤ a v]for fixed θ and v. We define Ω i := {a = i}. Then, the whole probability space is decomposed as Ω = i∈[K] Ω i . Similar to previous decompositions, we decompose Ω i asEQUATIONWe already stated in Appendix B.3 that the conditional density Z | Ω i ({z j } j̸ =i ) also satisfies LAC and especially,Z i | Ω i ({z j } j̸ =i ) satisfies LAC type property with L(•) in R d .We now state and prove our one of the most important results in fixed history analysis. Recall that we define[-1, 1] v := {x | -1 ≤ x ⊤ v ≤ 1}.Proposition 2 (Fixed history diversity constant lower bound) The random vector Z= (Z ⊤ 1 . . . Z ⊤ K ), Z i ∈ R d satisfies the following conditions: 1. Z has LAC with L(•) and ∥ supp(Z)∥ ∞ ≤ R. 2. For all i ∈ [K], supp(Z i ) is identical for some subset A ⊂ R d . It means supp(Z) = A K for some A ⊂ R d . 3. The support A ∩ [-1, 1] v has equal sections with direction v.Then we have the following with some absolute constant c > 0:E[v ⊤ Z a Z ⊤ a v] ≥ c dL(R) 2 .Remark 2 For unbounded contexts X(t) in the original bandit problem, we truncate to some region C 1 with positive probability, and we make the truncated contexts satisfy the condition of the above proposition.Proof of Proposition 2 Since supp(Z) ≤ R, it has bounded decay rate √ dL(R) by Lemma 3. By the previous decomposition, we can seeΩ i = {zj } j̸ =i Ω i ({z j } j̸ =i )holds. By applying tower property, we getE[v ⊤ Z a Z ⊤ a v] = E E[Z a Z ⊤ a | Ω i ({z j } j̸ =i )] = E E[Z i Z ⊤ i | Ω i ({z j } j̸ =i )]and we are enough to bound the termEQUATIONfor every Ω i ({z j } j̸ =i ). Recall that we defined[-1, 1] v := {x | x ⊤ v ∈ [-1, 1]}.Then, we can decompose it again asE[v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i )] = E v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v } P Z i ∈ [-1, 1] v | Ω i ({z j } j̸ =i ) + E v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ ([-1, 1] v ) c } P Z i ∈ ([-1, 1] v ) c | Ω i ({z j } j̸ =i ) ≥ E v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v }].The last inequality holds sinceE v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ ([-1, 1] v ) c } ≥ 1 and E v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v } ≤ 1.From now on, we focus on the conditional density ofZ i | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v } and its projected density v ⊤ Z i | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v }. For simplicity, we set the conditional density of Z i | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v } as f 1 (•) and the projected density of v ⊤ Z i | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v } as g 1 (•).Using Lemma 1, the density f 1 (•) has LAC with constant function L(R) and it has bounded decay rate √ dL(R) by Lemma 3.[1] Investigating the support of f 1 and g 1 . First, we examine the support of f 1 . Since arm i is optimal with estimator θ, for all z in the support of f 1 should satisfy z ⊤ θ ≥ max j̸ =i z ⊤ j θ. Also, because -1 ≤ z ⊤ v ≤ 1 holds, then it is the intersection of these two areas. Lets defineA 1 := supp(Z i | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v }) = {z ∈ A | z ⊤ θ ≥ max j̸ =i z ⊤ j θ, -1 ≤ z ⊤ v ≤ 1}.Recall that A := supp(Z i ) is designed to have equal sections with direction v. Hence A ∩ [-1, 1] v has equal section with v. Therefore, we can see that support ofZ ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v } is interval by our design of A.[2] Bounding one-side decay rate of section density in [-1, 1]. We aim to apply Lemma 4 to bound the varianceE v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v }].It told us that it is enough to bound the one-side decay rate of the section density,g 1 (•) in the interval [-1 2 , 1 2 ].Claim 1 Then one of Sec(A 1 , v, y) or Sec(A 1 , -v, y) are expanding sections when y increases fory ∈ [-1, 1].Proof Choose one of v, -v that satisfies ⟨•, θ⟩ ≥ 0. We want to use the result of Lemma 10. Since [-1, 1] v has equal sections with direction v, by rotating the axis, we can make this satisfy the condition of Lemma 10. Then the result of the Lemma 10 tells that at least one direction of v, -v makes an expanding section. Please see Figure 5 for intuitions.< l a t e x i t s h a 1 _ b a s e 6 4 = " k V In this case, sections with direction +v is expanding! If a cylindrical set is cut by some hyperplane (which is A 1 ), at least one direction makes expanding sections.T j U x K H n g X e x W c d V U P l Q C r L t y I = " > A A A G T n i c j V R N b x M x E H U L g V K + W r g B B 4 s I q U i r K l t V g N R L U V u J G 6 X Q p l U 2 i r z O b G L F a 1 u 2 t 0 2 0 3 Q u / h i v 8 E q 7 8 E W 4 I v P k g X a d I W N p 4 M u + N Z / w 8 m l h x Z m y j 8 W N p + c b N 2 q 3 b K 3 d W 7 9 6 7 / + D h 2 v q j E y M z T e G Y S i 7 1 a U w M c C b g 2 D L L 4 V R p I G n M o R k P 9 k q 8 e Q 7 a M C k + 2 Z G C d k p 6 g i W M E u t c n b V n k V S g i Z V a k B T y j 0 C L j b e d M M D n w e h l Z 6 3 e 2 G y M F 1 4 0 w q l R R 9 N 1 2 F m v P Y m 6 k m Y p C E s 5 M a Y V N p R t 5 0 R b R j k U q 1 F m Q B E 6 I D 1 o O b P M a d r 5 + B o F f u E 8 X Z x I 7 T 5 h 8 d h 7 N S I n q T G j N H b M l N i + 8 b H S e R 3 W y m z y p p 0 z o T I L g k 4 S J R n H V u J S E 9 x l G q j l I 1 w 5 U R A b s 7 i 4 L k v g 9 r J G E 8 x K q r D G l Q c Y h B P C a Q s B T r g k N s A 9 T V S f 0 W G A B 9 K C 2 1 I y A A q c O y v j l m l 5 E W A m u k 6 + h G n j I k w W U 6 L K t / I K 4 T 1 l I H N i y y 4 s Q F I z 2 0 + r 7 r 6 7 q d a Q V L 2 c K Z N 5 T B d q p e S m 8 O R w l 4 E k c O 9 4 D g v n z G 7 m n w R S Q 1 q y q 9 r G X s p / X X M 4 a Y 2 K T 2 k p v e y K a D N g y j k F X F C Z p k R 0 8 + i g y K P y t e I 4 P y g 8 7 G i O H f n Y / v 4 c 3 P d B 1 5 4 O 3 Y n c 8 9 m 8 / I O j H e x x S o F G F R Y m n F / H P J 1 l S v J T P 9 P Z H D t b q G K O J T 7 W n G N N H x v O s a G P p X M s 9 T E S m 6 I V t v O I Q 2 I v 6 2 G k W a 9 v L z 2 W y Z S Q O r 3 C n P z i e o i n E d O t k 0 d M J H b k 5 7 E X 8 r 9 P 2 P K D l e S l 6 p W B N v Y t l q l 8 3 t g 3 4 U 2 b N p e T f s z f z / r y C k a l 6 L I J v P f X r D B c l 7 o Z 7 D Q 9 n B q r b p q G / u x c N E 6 2 N s N X m 9 s f t u u 7 2 9 O 5 u o K e o u d o A 4 X o N d p F 7 9 A h O k Y U f U Z f 0 F f 0 r f a 9 9 r P 2 q / Z 7 Q l 1 e m s Y 8 R p V 1 a + U P s o d M + w = = < / l a t e x i t > Sec(A 1 , v, y) < l a t e x i t s h a 1 _ b a s e 6 4 = " g / C H M j g 9 I H 2 o A n n / d Z K j A J T I 5 O c = " > A A A G M 3 i c j V T L b h M x F H U L A 6 U 8 2 s I O N h Y R E o t R l a k q Q O q m q K 3 E j l J o k y o T R R 7 H k 1 j x S 7 a n T T T N J 7 C F L + F j E D v E l n / A k 0 y Y j l M k L C W + O e d c 3 4 d v n C h G j W 0 2 v 6 + s 3 r o d 3 L m 7 d m / 9 / o O H j z Y 2 t x 6 f G Z l p T E 6 x Z F K 3 E 2 Q I o 4 K c W m o Z a S t N E E 8 Y a S W j g 4 J v X R B t q B S f 7 E S R L k c D Q V O K k X X Q x 7 e 9 q L f Z a G 4 3 Z w s u G 1 F p N E C 5 j n t b w d O 4 L 3 H G i b C Y I W M 6 U V P Z b o 6 0 p Z i R 6 X q c G a I Q H q E B 6 T h T I E 5 M N 5 / l O o U v H N K H q d T u I y y c o d c 9 c s S N m f D E K T m y Q + N z B X g T 1 8 l s + q a b U 6 E y S w S e B 0 o z B q 2 E R e G w T z X B l k 1 g 7 U S B b E K T 6 U 1 R Q r c X O Z p w k V J N N c s 8 h E S 4 R m h k S Q h T J p E N 4 U A j N a R 4 H M K R t M R t H I 0 I J o w 5 K 2 O W a n k Z Q i r 6 r n 0 p 1 c Z 5 m C z B S B U X 4 i X C B s q Q z D V b 9 s k S J T W 1 Q 1 6 H h 6 5 S r U l a R x l V J v O U z t V K y c z U a 4 c r h q S h u 8 c L s n T O o j L / J C I 1 4 Y W 6 3 t v E C / m v M s f z 0 a h h S k v p R V d I m x F V D h T k E k v O k e j n 8 d E 0 j 4 v b S p L 8 a O p x J x V 3 4 n O H h x V 5 6 J N u P B 2 7 F 7 v r s 3 n x A 8 Z 7 0 N M U D Z r U V B A x d p O y v Y i U 5 m 0 / 0 n n F n S 9 l U X G p z 7 U q r u V z 4 4 o b + x y v O O 5 z K D H T T t T N Y 0 Z S e 9 W I Y k 0 H Q 3 v l q U y m h N T 8 m n L + D R s R L D 3 K r Z f H V K R 2 4 s e x l / K / T 9 j x n Z V k R d e l K v 5 0 U h c D m 8 + w 5 T S V r 5 t h c 1 0 5 t L m c z 2 P + f j G X 1 z g s R Z / O 6 Y O / Z k 3 h p t Q 9 t K 6 n x 6 W x 7 l 7 T y H 8 7 l 4 2 z n e 3 o 1 f b u h 9 3 G / m 7 5 r q 6 B Z + A 5 e A k i 8 B r s g 3 f g G J w C D A b g M / g C v g b f g h / B z + D X X L q 6 U v o 8 A b U V / P 4 D s v t D m w = = < / l a t e x i t > A 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " S 3 M Y 0 A H n z 1 m H F g J w K b f K K m J h j 1 o = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w Z C a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t F 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H l x c b z d Z W a 7 b w s h F W R h N V 6 + h i s / E q 6 s s k 4 y B s w o g x 3 b C l b C 8 n 2 t K E w X Q 9 y g w o k o z I A L r O F I S D 6 e W z T K f 4 r U P 6 O J X a f Y T F M / S 2 R 0 6 4 M R M e O y U n d m h 8 r g D v 4 r q Z T T / 2 c i p U Z k E k Z a A 0 Y 9 h K X J S N + 1 R D Y t k E 1 0 4 U x M Y 0 n t 4 V J X B 7 k a M J 5 i n V V L P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I q w F T 0 X f t S q o 3 z M F m c E F V c h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z G b q t c M V A 2 n g 7 v E S l s 6 Z V + a f B F I D L 9 T 1 3 s Z e y H + V O S 5 H o 4 Y p L a U X X R F t R l Q 5 U M B V I j k n o p 9 H h 9 M 8 K m 4 r j v P D q c e d L L g T n z s 4 W J A H P u n G 0 7 G 7 k b s + m x c / c L S L P U 3 R o E l N h Q l j d y k 7 8 0 h p 3 v E j n S + 4 8 6 U s F l z q c + 0 F 1 / a 5 8 Y I b + x x f c N z n S G y m 3 b C X R w x S e 9 0 M I 0 0 H Q 3 v t q U y m h N T 8 l r L 8 x s 0 Q V x 7 V d p F H V K R 2 4 s e x V / K / T 9 j 2 n Z V k R d e l K v 5 0 U h c D m 8 + w 5 T S V r 5 t h p a 4 a 2 l y W 8 5 h / n s / l L S 6 R o k 9 L e v + v W V O 4 K X X P r O v p U W W s u 9 c 0 9 N / O Z e N s e y t 8 v 7 V z v N P c 2 6 n e 1 T X 0 G r 1 B 7 1 C I P q A 9 9 A k d o V O U I E B f 0 T f 0 v f G j c d P 4 2 f h V S l d X K p + X q L Y a v / 8 A T 8 F D L A = = < / l a t e x i t > v < l a t e x i t s h a 1 _ b a s e 6 4 = " C E s h L f C f 6 / + A U i A m d W X S b 3 2 Q r M Q = " > A A A G N n i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y U S r a p M p E l W d y J z H x S 7 a n T T T N P 7 C F L + F X 2 L B D b P k E P J k J 6 T h F w l L i m 3 P O 9 X 3 4 x r F i 1 N h W 6 / v K 6 q 3 b j T t 3 1 + 6 t 3 3 / w 8 N H j j c 0 n p 0 Z m O o G T R D K p O z E x w K i A E 0 s t g 4 7 S Q H j M o B 2 P 9 g u + f Q H a U C k + 2 o m C H i c D Q V O a E O u g 0 8 g O w Z L z j W Z r q z V b e N k I K 6 O J q n V 0 v t l 4 F v V l k n E Q N m H E m G 7 Y U r a X E 2 1 p w m C 6 H m U G F E l G Z A B d Z w r C w f T y W b p T / N I h f Z x K 7 T 7 C 4 h l 6 3 S M n 3 J g J j 5 2 S E z s 0 P l e A N 3 H d z K Z v e z k V K r M g k j J Q m j F s J S 5 q x 3 2 q I b F s g m s n C m J j G k 9 v i h K 4 v c j R B P O U a q p Z 5 g E G 4 R q h i Y U A p 0 w S G + C B J m p I k 3 G A R 9 K C 2 z g Z Q Q K M O S t j l m p 5 G W A q + q 5 9 K d X G e Z g s T o g q 7 s R L h A 2 U g c w 1 W / Z h i Z K a 2 i G v w 0 N X q d a Q 1 l F G l c k 8 p X O 1 U j I z 9 d r h i o E 0 c P d 4 A U v n z C v z T w K p g R f q e m 9 j L + S / y h y X o 1 H D l J b S i 6 6 I N i O q H C j g M p G c E 9 H P o 8 N p H h W 3 F c f 5 4 d T j j h f c s c 8 d H C z I A 5 9 0 4 + n Y 3 c h d n 8 2 L H z j a x Z 6 m a N C k p s K E s Z u U n X m k N O / 4 k c 4 W 3 N l S F g s u 9 b n 2 g m v 7 3 H j B j X 2 O L z j u c y Q 2 0 2 7 Y y y M G q b 1 q h p G m g 6 G 9 8 l Q m U 0 J q f k 1 Z f u N m i C u P a j v P I y p S O / H j 2 E v 5 3 y d s + 8 5 K s q L r U h V / O q m L g c 1 n 2 H K a y t f N s F J X D W 0 u y 3 n M 3 8 / n 8 h q X S N G n J b 3 / 1 6 w p 3 J S 6 t 9 b 1 9 K g y 1 t 1 r G v p v 5 7 J x u r 0 V v t 7 a + b D T 3 N u p 3 t U 1 9 B y 9 Q K 9 Q i N 6 g P f Q O H a E T l K B P 6 D P 6 g r 4 2 v j V + N H 4 2 f p X S 1 Z X K 5 y m q r c b v P 6 d I R V o = < / l a t e x i t > ω < l a t e x i t s h a 1 _ b a s e 6 4 = " X Y V 5 Z I 9 l / J I 2 A k c W P c T s V U e x 7 n Q = " > A A A G M n i c j V T L b h M x F H U L A 6 W 8 W t j B x i J C Y j F U m a o C p G 4 q t Z X Y U S r a p M p E l c f x J F b 8 k u 1 p E 0 3 z B 2 z h S / g Z 2 C G 2 f A S e z I T p O E X C U u K b c 8 7 1 f f j G i W L Ux v t F q b 7 X n C y 4 b U W W 0 Q L W O z j e D Z / F A 4 o w T Y T F D x v S i t r L 9 H G l L M S O z 9 T g z R C E 8 R k P S c 6 Z A n J h + P k 9 1 B l 8 6 Z A B T q d 1 H W D h H r 3 v k i B s z 5 Y l T c m R H x u c K 8 C a u l 9 n 0 X T + n Q m W W C F w G S j M G r Y R F 3 X B A N c G W T W H j R I F s Q p P Z T V F C t x c 5 m n C R U k M 1 z z y E R L h G a G R J C F M m k Q 3 h U C M 1 o n g S w r G 0 x G 0 c j Q k m j D k r Y 5 Z q e R l C K g a u f S n V x n m Y L M F I F f f h J c K G y p D M N V s O y B I l N b U j 3 o R H r l K t S d p E G V U m 8 5 T O 1 U r J z M x r h y u G p K G 7 x w u y d M 6 i M v 8 k I j X h h b r Z 2 8 Q L + a 8 y J + V o N D C l p f S i K 6 T N m C o H C n K J JThe result of Claim 1 tell us that we can apply Lemma 8 and finally we can bound the one-side decay rate of section density g 1 (•). Without loss of generality, Sec(A 1 , v, y) is expanding sections whan y increases. Then support ofZ ⊤ i v | Ω i ({z j } j̸ =i ) ∩ {Z i ∈ [-1, 1] v } is interval of form [c, 1] with some -1 < c < 1.Claim 2 One-side decay rate of the densitiesP[v ⊤ Z i = y | Ω i ({z j } j̸ =i ) ∩ [-1, 1] v ] is bounded by √ dL(R) in y ∈ [-1, 1] .Proof To bound the one-side decay rate, we aim to use Lemma 8. By the following Claim 1, without loss of generality, we can set sections with direction v as Sec(A, v, y) is expanding section. (Since variance of v ⊤ X is the same as (-v) ⊤ X, either case is fine) Then we can apply Lemma 8 and get the wanted result directly.[3] Bounding desired variance. We can see that the support of g 1 (•) is form of interval [c, 1] for some c < 1. Hence, by using the result of the previous Lemma 4, we conclude the varianceE[v ⊤ Z i Z ⊤ i v | Ω i ({z j } j̸ =i ) ∩ Z i ∈ [-1, 1] v ] ≥ c dL(R) 2for some absolute constant c > 0.We prove the Lemma 10 which is used in the proof. Proof To prove that they are expanding sections, we need to show that for any h > 0, x 0 + he n ∈ Sec(S ′ , e n , y + h) for any x 0 ∈ Sec(S ′ , e n , y). By the definition of sections, it is clear that x 0 + he n ∈ {x ∈ R d | x ⊤ e n = y + h}. Next, we need to show that x 0 + he n ∈ {x | x ⊤ θ ≥ b}. Since e ⊤ n θ ≥ 0 (x 0 + he n ) ⊤ θ ≥ x ⊤ 0 θ ≥ b holds. < l a t e x i t s h a 1 _ b a s e 6 4 = " M u O A M 2 l Q O i z / I u M I E o O 0 F I D Q u 7 k = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 R b a B G W i y j O 5 k 1 j x S 7 a n T T S d L 2 A L X 8 L X d I f Y 8 h N 4 k g n p O E X C U u K b c 8 7 1 f f j G s W L U 2 F b r e m X 1 z t 3 G v f t r D 9 Y f P n r 8 5 O n G 5 r M z I z O d w G k i m d S d m B h g V M C p p Z Z B R 2 k g P G b Q j k f 7 J d + + A G 2 o F J / t R E G P k 4 G g K U 2 I d d D x p / O N Z m u r N V 1 4 2 Q g r o 4 m q d X S + 2 X g R 9 W W S c R A 2 Y c S Y b t h S t p c T b W n C o F i P M g O K J C M y g K 4 z B e F g e v k 0 0 w K / d k g f p 1 K 7 j 7 B 4 i t 7 0 y A k 3 Z s J j p + T E D o 3 P l e B t X D e z 6 f t e T o X K L I h k F i j N G L Y S l 2 X j P t W Q W D b B t R M F s T G N i 9 u i B G 4 v c z T B P K W a a p p 5 g E G 4 R m h i I c A p k 8 Q G e K C J G t J k H O C R t O A 2 T k a Q A G P O y p i l W l 4 G m I q + a 1 9 K t X E e J o s T o s r r 8 B J h A 2 U g c 8 2 W f V i i p K Z 2 y O v w 0 F W q N a R 1 l F F l M k / p X K 2 U z B RC I 3 q E 9 9 A E d o V O U I E B f 0 T f 0 v f G j c d 3 4 2 f g 1 k 6 6 u V D 7 P U W 0 1 f v 8 B h K t D C Q = = < / l a t e x i t > S < l a t e x i t s h a 1 _ b a s e 6 4 = " O Y u X w y v 4 K B 9 y h T r R G u x E D K U v z t s = " > A A A G M n i c j V T L b h M x F H W B Q C m v F n a w s Y g Q L E Z V p q o A q Z t K b S V 2 l E K b V J m o 8 j i e x I p f s j 1 t o u n 8 A V v 4 E n 4 G d o g t H 4 E n M 2 ED i V N O h M U M G d M P O 8 o O M q Q t x Y z k a 1 F q i E J 4 g k a k 7 0 y B O D G D b J 5 q D l 8 4 Z A g T q d 1 H W D h H r 3 p k i B s z 4 7 F T c m T H x u c K 8 D q u n 9 r k 7 S C j Q q W W C F w G S l I G r Y R F 3 X B I N c G W z W D j R I F s T O P 8 u i i B 2 4 s c T b B I q a G a Z x 5 A I l w j N L I k g A m T y A Z w p J E a U z w N 4 E R a 4 j a O J g Q T x p y V M k u 1 v A g g F U P X v o R q 4 z x M G m O k i v v w E m E j Z U j q m i 2 H Z I m S m t o x b 8 J j V 6 n W J G m i j C q T e k r n a q V k J v f a 4 Y o h S e D u 8 Z w s n b O o z D + J S E 1 4 o W 7 2 N v Z C / q v M a T k a D U x p K b 3 o C m k z o c q B gL w C I X g D d s E 7 c A i O A Q Y J + A y + g K + t b 6 0 f r Z + t X 6 X 0 x k r l 8 w Q 0 V u v 3 H 5 B 1 Q z o = < / l a t e x i t > S → < l a t e x i t s h a 1 _ b a s e 6 4 = " C E s h L f C f 6 / + A U i A m d W X S b 3 2 Q r M Q = " > A A A G N n i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y U S r a p M p E l W d y J z H x S 7 a n T T T N P 7 C F L + F X 2 L B D b P k E P J k J 6 T h F w l L i m 3 P O 9 X 3 4 x r F i 1 N h W 6 / v K 6 q 3 b j T t 3 1 + 6 t 3 3 / w 8 N H j j c 0 n p 0 Z m O o G T R D K p O z E x w K i A E 0 s t g 4 7 S Q H j M o B 2 P 9 g u + f Q H a U C k + 2 o m C H i c D Q V O a E O u g 0 8 g O w Z L z j W Z r q z V b e N k I K 6 O J q n V 0 v t l 4 F v V l k n E Q N m H E m G 7 Y U r a X E 2 1 p w m C 6 H m U G F E l G Z A B d Z w r C w f T y W b p T / N I h f Z x K 7 T 7 C 4 h l 6 3 S M n 3 J g J j 5 2 S E z s 0 P l e A N 3 H d z K Z v e z k V K r M g k j J Q m j F s J S 5 q x 3 2 q I b F s g m s n C m J j G k 9 v i h K 4 v c j R B P O U a q p Z 5 g E G 4 R q h i Y U A p 0 w S G + C B J m p I k 3 G A R 9 K C 2 z g Z Q Q K M O S t j l m p 5 G W A q + q 5 9 K d X G e Z g s T o g q 7 s R L h A 2 U g c w 1 W / Z h i Z K a 2 i G v w 0 N X q d a Q 1 l F G l c k 8 p X O 1 U j I z 9 d r h i o E 0 c P d 4 A U v n z C v z T w K p g R f q e m 9 j L + S / y h y X o 1 H D l J b S i 6 6 I N i O q H C j g M p G c E 9 H P o 8 N p H h W 3 F c f 5 4 d T j j h f c s c 8 d H C z I A 5 9 0 4 + n Y 3 c h d n 8 2 L H z j a x Z 6 m a N C k p s K E s Z u U n X m k N O / 4 k c 4 W 3 N l S F g s u 9 b n 2 g m v 7 3 H j B j X 2 O L z j u c y Q 2 0 2 7 Y y y M G q b 1 q h p G m g 6 G 9 8 l Q m U 0 J q f k 1 Z f u N m i C u P a j v P I y p S O / H j 2 E v 5 3 y d s + 8 5 K s q L r U h V / O q m L g c 1 n 2 H K a y t f N s F J X D W 0 u y 3 n M 3 8 / n 8 h q X S N G n J b 3 / 1 6 w p 3 J S 6 t 9 b 1 9 K g y 1 t 1 r G v p v 5 7 J x u r 0 V v t 7 a + b D T 3 N u p 3 t U 1 9 B y 9 Q K 9 Q i N 6 g P f Q O H a E T l K B P 6 D P 6 g r 4 2 v j V + N H 4 2 f p X S 1 Z X K 5 y m q r c b v P 6 d I R V o = < / l a t e x i t > ω < l a t e x i t s h a 1 _ b a s e 6 4 = " Z g O 1 M n U d p Z 3 o G B h 9 x w / d 2 1 b K Z S U = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z V g R V v R J i g T V Z 7 J n cB s V 6 l B l Q J B m R A X S d K Q g H 0 8 u n m R b 4 t U P 6 O J X a f Y T F U / S m R 0 6 4 M R M e O y U n d m h 8 r g R v 4 7 q Z T d / 3 c i p U Z k E k s 0 B p x r C V u C w b 9 6 m G x L I J r p 0 o i I 1 p X N w W J X B 7 m a M J 5 i n V V N P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I y w F T 0 X f t S q o 3 z M F m c E F V e h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z K b w 2 u G K g T R w 9 3 g B S + f M K / N P A q m B l + p 6 b 2 M v 5 L / K H M 9 G o 4 Y p L a U X X R F t R l Q 5 U M B l I j k n o p 9 H h 0 U e l b c V x / l h 4 X E n C + 7 E 5 w 4 O F u S B T 7 r x d O x u 5 K 7 P 5 u U P H O 1 i T 1 M 2 a F J T Y c L Y b c r O P F K a d / x I X x b c l 6 U s F l z q c + 0 F 1 / a 5 8 Y I b + x x f c N z n S G y K b t j L I w a p v W q G k a a D o b 3 y V C Z T Q m p + Q z n 7 x s 0 Q V x 7 V d p 5 H V K R 24 s e x l / K / T 9 j 2 n Z V k Z d e l K v 9 0 U p c D m 0 + x 5 T S V r 5 t i M 1 0 1 t L m c z W P + a T 6 X N 7 h E i j 6 d 0 f t / z Z r C T a l 7 Z l 1 P j y p j 3 b 2 m o f 9 2 L h t n 2 1 v h 2 6 2 d 4 5 3 m 3 k 7 1 r q 6 h l + g V e o N C 9 A 7 t o Q / o C J 2 i B A H 6 i r 6 h 7 4 0 f j e v G z 8 a v m X R 1 p f J 5 j m q r 8 f s P S q l C / w = = < / l a t e x i t > I < l a t e x i t s h a 1 _ b a s e 6 4 = " W q 4 l P d 5 D 1 s 1 f Y 8 A 9 y G Z E 7 I o F U 0 I = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m S o C p G 4 q t Z X Y 0 V a k S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w J B P S c Y q E p c Q 3 5 5 z r + / C N Y 8 W o s Y 3 G z d r 6 v f u 1 B w 8 3 H m 0 + f v L 0 2 f O t 7 R d n R m Y 6 g V Y i m d S d m B h g V E D L U s u g o z Q Q H j N o x 6 O D g m 9 f g j Z U i i 9 2 o q D H y U D Q l C b E O u i k d b F V b + w 0 Z g u v G m F p 1 F G 5 j i + 2 a 6 + i v k w y D s I m j B j T D R v K 9 n K i L U 0 Y T D e j z I A i y Y g M o O t M Q T i Y X j 7 L d I r f O q S P U 6 n d R 1 g 8 Q 2 9 7 5 I Q b M + G x U 3 J i h 8 b n C v A u r p v Z 9 G M v p 0 J l F k Q y D 5 R m D F u J i 7 J x n 2 p I L J v g y o m C 2 J j G 0 7 u i B G 4 v c j T B I q W K a p Z 5 g E G 4 R m h i I c A p k 8 Q G e K C J G t J k H O C R t O A 2 T k a Q A G P O y p i l W l 4 F m I q + a 1 9 K t X E e J o s T o o r r 8 B J h A 2 U g c 8 2 W f V i h p K Z 2 y K v w 0 F W q N a R V l F F l M k / p X K 2 U z E y 9 d r h i I A 3 c P V 7 C y j m L y v y T Q G r g h b r a 2 9 g L + a 8 y x / P R q G B K S + l F V 0 S b E V U O F H C V S M 6 J 6 O f R 0 T S P i t u K 4 / x o 6 n G n S + 7 U 5 w 4 P l + S h T 7 r x d O x e 5 K 7 P 5 s U P H O 1 h T 1 M 0 a F J R Y c L Y X c r O I l K a d / x I 5 0 v u f C W L J Z f 6 X H v J t X 1 u v O T G P s eY = " > A A A G M 3 i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m S o C p G 4 q t Z X Y U Q p t U m W i y O P c S a x 4 b M v 2 t I m m + Q S 2 8 C V 8 D G K H 2 P I P e J I J 6 T h F w l L i m 3 P O 9 X 3 4 x r H i z N h G 4 / v a + q 3 b t T t 3 N + 5 t 3 n / w 8 N H j r e 0 n Z 0 Z m m s I p l V z q d k w M c C b g 1 D L L o a 0 0 k D T m 0 I p H B w X f u g B t m B S f 7 E R B N y U D w R J G i X X Q R + i J 3 l a 9 s d O Y L b x q h K V R R + U 6 7 m 3 X n k V 9 S b M U h K W c G N M J G 8 p 2 c 6 I t o x y m m 1 F m Q B E 6 I g P o O F O Q F E w 3 n + U 6 x S 8 d 0 s e J 1 O 4 j L J 6 h 1 z 1 y k h o z S W O n T I k d G p 8 r w J u 4 T m a T t 9 2 c C Z V Z E H Q e K M k 4 t h I X h e M + 0 0 A t n + D K i Y L Y m M X T m 6 I E b i 9 y N M E i p Y p q l n m A Q b h G a G I h w A m X x A Z 4 o I k a M j o O 8 E h a c F t K R k C B c 2 d l 3 D I t L w P M R N + 1 L 2 H a O A + T x Z S o 4 k K 8 R P h A G c h c s 2 U f V i i p m R 2 m V X j o K t U a k i r K m T K Z p 3 S u V k p u p l 4 7 X D G Q B O 4 e L 2 D l n E V l / k k g N a S F u t r b 2 A v 5 r z L H 8 9 G o Y E p L 6 U V X R J s R U w 4 U c E l l m h L R z 6 O j a R 4 V t x X H + dNext, we provide a fixed history analysis to bound margin constant of Challenge 2. In this section, we first bound the margin constant C ∆ by assuming ∥θEQUATIONEQUATIONholds. So from now on, we assume ∥θ ⋆ ∥ 2 = 1 and we adjust it later. Also, we highlight that we only need to bound C ∆ it for ε < 1 2 , since if ε > 1 2 , it holds with C ∆ = 2. Before we start, we define the cylindrical set, which is used in characterizing the support of densities.We define A ⊂ R d as a cylindrical region with direction v ∈ S d-1 and length H when A = {B + tv | -H ≤ t ≤ H} for some subset of the hyperplane B ⊂ {x | x ⊤ v = 0}. We write this set as cyl(B, v, H). Next, we prove that if the support of each context Z i is a cylindrical set, we can bound the margin constant. We state our key results for the bounding margin constant in the fixed history setup.Y 0 A H n z 1 m H F g J w K b f K K m J h j 1 o = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t E 0 X 8 A W v o S v 6 Q 6 x 5 S f w Z C a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t F 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H l x c b z d Z W a 7 b w s h F W R h N V 6 + h i s / E q 6 s s k 4 y B s w o g x 3 b C l b C 8 n 2 t K E w X Q 9 y g w o k o z I A L r O F I S D 6 e W z T K f 4 r U P 6 O J X a f Y T F M / S 2 R 0 6 4 M R M e O y U n d m h 8 r g D v 4 r q Z T T / 2 c i p U Z k E k Z a A 0 Y 9 h K X J S N + 1 R D Y t k E 1 0 4 U x M Y 0 n t 4 V J X B 7 k a M J 5 i n V V L P M A w z C N U I T C w F O m S Q 2 w A N N 1 J A m 4 w C P p A W 3 c T K C B B h z V s Y s 1 f I q w F T 0 X f t S q o 3 z M F m c E F V c h 5 c I G y g D m W u 2 7 M M S J T W 1 Q 1 6 H h 6 5 S r S G t o 4 w q k 3 l K 5 2 q l Z G b q t c M V A 2 n g 7 v E S l s 6 Z V + a f B F I D L 9 T 1 3 s Z e y H + V O S 5 H o 4 Y p L a U X X R F t R l Q 5 U M B V I j k n o p 9 H h 9 M 8 K m 4 r j v P D q c e d L L g T n z s 4 W J A H P u n G 0 7 G 7 k b s + m x c / c L S L P U 3 R o E l N h Q l j d y k 7 8 0 h p 3 v E j n S + 4 8 6 U s F l z q c + 0 F 1 / a 5 8 Y I b + x x f c N z n S G y m 3 b C X R w x S e 9 0 M I 0 0 H Q 3 v t q U y m h N T 8 l r L 8 x s 0 Q V x 7 V d p F H V K R 2 4 s e x V / K / T 9 j 2 n Z V k R d e l K v 5 0 U h c D m 8 + w 5 T S V r 5 t h p a 4 a 2 l y W 8 5 h / n s / l L S 6 R o k 9 L e v + v W V O 4 K X X P r O v p U W W s u 9 c 0 9 N / O Z e N s e y t 8 v 7 V z v N P c 2 6 n e 1 T X 0 G r 1 B 7 1 C I P q A 9 9 A k d o V O U I E B f 0 T f 0 v f G j c d P 4 2 f h V S l d X K p + X q L Y a v / 8 A T 8 F D L A = = < / l a t e x i t > v < l a t e x i t s h a 1 _ b a s e 6 4 = " v u B Q h b L i 3 x K K 2 6 k 2 I M H U x y p a y y I = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 6 K 2 k r s a C v a B G W i y j O 5 k 1 j x S 7 a n T T S d L 2 A L X 8 L X d I f Y 8 h N 4 k g n p O E X C U u K b c 8 7 1 f f j G s W L U 2 F b r e m X 1 z t 3 G v f t r D 9 Y f P n r 8 5 O n G 5 r M z I z O d w G k i m d S d m B h g V M C p p Z Z B R 2 k g P G b Q j k f 7 J d + + A G 2 o F J / t R E G P k 4 G g K U 2 I d d D x h / O N Z m u r N V 1 4 2 Q g r o 4 m q d X S + 2 X g R 9 W W S c R A 2 Y c S Y b t h S t p c T b W n C o F i P M g O K J C M y g K 4 z B e F g e v k 0 0 w K / d k g f p 1 K 7 j 7 B 4 i t 7 0 y A k 3 Z s J j p + T E D o 3 P l e B t X D e z 6 f t e T o X K L I h k F i j N G L Y S l 2 X j P t W Q W D b B t R M F s T G N i 9 u i B G 4 v c z T B P K W a a p p 5 g E G 4 R m h i I c A p k 8 Q G e K C J G t J k H O C R t O A 2 T k a Q A G P O y p i l W l 4 G m I q + a 1 9 K t X E e J o s T o s r r 8 B J h A 2 U g c 8 2 W f V i i p K Z 2 y O v w 0 F W q N a R 1 l F F l M k / p X K 2 U z B RC I 3 q E 9 9 B E d o V O U I E B f 0 T f 0 v f G j c d 3 4 2 f g 1 k 6 6 u V D 7 P U W 0 1 f v 8 B H E F C 9 w = = < / l a t e x i t > A < l a t e x i t s h a 1 _ b a s e 6 4 = " W C q N 4 N y G c U / V S 7 v 3 6 J p D I D b P F R 0 = " > A A A G M n i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z W 6 o 1 S 0 S Z W J K o / j S a z 4 J d v T J p r O H 7 C F L + F n Y I f Y 8 h F 4 M h O m 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y z u d 7 y u r d + 6 2 7 t 1 f e 7 D + 8 N H j J 0 8 3 N p + d G Z l q T E 6 x Z F L 3 Y m Q I o 4 K c W m o Z 6 S l N E I 8 Z 6 c a T / Y L v X h J t q B S f 7 E y R A U c j Q R O K k X X Q y f b R x U a 7 s 9 W Z L 7 h s h J X R B t U 6 v t h s v Y i G E q e c C I s Z M q Y f d p Q d Z E h b i h n J 1 6 P U E I X w B I 1 I 3 5 k C c W I G 2 T z V H L 5 2 y B A m U r u P s H C O 3 v T I E D d m x m O n 5 M i O j c 8 V 4 G 1 c P 7 X J + 0 F G h U o t E b g M l K Q M W g m L u u G Q a o I t m 8 H G i Q L Z m M b 5 b V E C t x c 5 m m C R U k M 1 z z y A R L h G a G R J A B M m k Q 3 g S C M 1 p n g a w I m 0 x G 0 c T Q g m j D k r Z Z Z q e R V A K o a u f Q n V x n m Y N M Z I F f f h J c J G y p D U N V s O y R I l N b V j 3 o T H r l K t S d J E G V U m 9 Z T O 1 U r J T O 6 1 w x V D k s D d 4 y V Z O m d R m X 8 S k Z r w Q t 3 s b e y F / F e Z 0 3 I 0 G p j S U n r R F d J m Q p U D B b n C k n M k h l l 0 m G d R c V t x n B 3 m H n d S c y c + d 3 B Q k w c + 6 c b T s b u R u z 6 b F T 9 g t A s 9 T d G g W U M F E W O 3 K X u L S E n W 8 y O d 1 9 z 5 U h Y 1 l / h c t + a 6 P j e t u a n P 8 Z r j P o d i k / f D Q R Y x k t j r d h h p O h r b a 0 9 l U i W k 5 j e U 5 T d s h 7 D y q L a L L K I i s T M / j r 2 S / 3 3 C t u + s J C u 6 L l X x p 5 O 6 G N h s j i 2 n q X z d H C t 1 1 d B m s p z H 7 M N i L m 9 w W I o h L e n 9 vZ f g F X g D Q v A O 7 I E j c A x O A Q Y J + A y + g K + t b 6 0 f r Z + t X 6 V 0 d a X y e Q 4 a q / X 7 D 5 B U Q z o = < / l a t e x i t > 2H < l a t e x i t s h a 1 _ b a s e 6 4 = " O j r 5 z y N G x 5 N M k m 0 P R K v Z u 2 p m z I Y = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q 2 k r s a C v a B G W i y j O 5 k 1 j x S 7 a n T T S d L 2 A L X 8 L X d I f Y 8 h N 4 k g n p O E X C U u K b c 8 7 1 f f j G s W L U 2 F b r e m X 1 z t 3 G v f t r D 9 Y f P n r 8 5 O n G 5 r M z I z O d w G k i m d S d m B h g V M C p p Z Z B R 2 k g P G b Q j k f 7 J d + + A G 2 o F J / t R E G P k 4 G g K U 2 I d d D x h / O N Z m u r N V 1 4 2 Q g r o 4 m q d X S + 2 X g R 9 W W S c R A 2 Y c S Y b t h S t p c T b W n C o F i P M g O K J C M y g K 4 z B e F g e v k 0 0 w K / d k g f p 1 K 7 j 7 B 4 i t 7 0 y A k 3 Z s J j p + T E D o 3 P l e B t X D e z 6 f t e T o X K L I h k F i j N G L Y S l 2 X j P t W Q W D b B t R M F s T G N i 9 u i B G 4 v c z T B P K W a a p p 5 g E G 4 R m h i I c A p k 8 Q G e K C J G t J k H O C R t O A 2 T k a Q A G P O y p i l W l 4 G m I q + a 1 9 K t X E e J o s T o s r r 8 B J h A 2 U g c 8 2 W f V i i p K Z 2 y O v w 0 F W q N a R 1 l F F l M k / p X K 2 U z B RProposition 3 (Fixed history margin constant bound) Assume that the random vector Z = (Z ⊤ 1 . . . Z ⊤ K ), Z i ∈ R d satisfies LAC with function L(•) and ∥ supp(Z)∥ ∞ ≤ R. Additionally, it satisfies following conditions:1. For all i ∈ [K], supp(Z i ) ⊂ R d is identical for some set A ⊂ R d . It means supp(Z) = A K . 2. For some H > 0, Z i 's support supp(Z i ) = A = cyl(B, θ ⋆ , H + 1) for all i ∈ [K] and P[Z ∈ (cyl(B, θ ⋆ , H)) K ] ≥ 1 -δ.Then we haveP[∆(Z) ≤ ε] ≤ 3 √ dL(R)ε + δ.Remark 3 For the original bandit problem with contexts X(t), we truncate to some high-probability region C 2 and set the truncated contexts to satisfy the conditions of the above proposition. We provide the analysis in the next Appendix F.< l a t e x i t s h a 1 _ b a s e 6 4 = " g W D d 6 Y A n w i z q Q L t v J d F c + 5 r S y x Y = " > A A A G O H i c j V T L b h M x F H W B Q C m v F n a w s Y i Q E B p V m a o C p G 4 q t Z X Y U Sv Z y o i 2 j H K Z r U W Z A E T o i A + g 6 U 5 A U T C + f J T z F L x z S x 4 n U 7 i M s n q F X P X K S G j N J Y 6 d M i R 0 a n y v A 6 7 h u Z p O 3 v Z w J l V k Q t A y U Z B x b i Y v q c Z 9 p o J Z P c O 1 E Q W z M 4 u l 1 U Q K 3 F z m a Y J 5 S T T X L P M A g X C M 0 s R D g h E t i A z z Q R A 0 Z H Q d 4 J C 2 4 L S U j o M C 5 s z J u m Z Y X A W a i 7 9 q X M G 2 c h 8 l i S l R x K 1 4 i f K A M Z K 7 Zt V V 9 A w 9 R y 9 R i N 6 g X f Q O H a J j R B F H n 9 E X 9 L X x r f G j 8 b P x q 5 T e W K l 8 n q D a a v z + A x O E R f Q = < / l a t e x i t > ✓ ⇤ < l a t e x i t s h a 1 _ b a s e 6 4 = " W C q N 4 N y G c U / V S 7 v 3 6 J p D I D b P F R 0 = " > A A A G M n i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z W 6 o 1 S 0 S Z W J K o / j S a z 4 J d v T J p r O H 7 C F L + F n Y I f Y 8 h F 4 M h O m 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y z u d 7 y u r d + 6 2 7 t 1 f e 7 D + 8 N H j J 0 8 3 N p + d G Z l q T E 6 x Z F L 3 Y m Q I o 4 K c W m o Z 6 S l N E I 8 Z 6 c a T / Y L v X h J t q B S f 7 E y R A U c j Q R O K k X X Q y f b R x U a 7 s 9 W Z L 7 h s h J X R B t U 6 v t h s v Y i G E q e c C I s Z M q Y f d p Q d Z E h b i h n J 1 6 P U E I X w B I 1 I 3 5 k C c W I G 2 T z V H L 5 2 y B A m U r u P s H C O 3 v T I E D d m x m O n 5 M i O j c 8 V 4 G 1 c P 7 X J + 0 F G h U o t E b g M l K Q M W g m L u u G Q a o I t m 8 H G i Q L Z m M b 5 b V E C t x c 5 m m C R U k M 1 z z y A R L h G a G R J A B M m k Q 3 g S C M 1 p n g a w I m 0 x G 0 c T Q g m j D k r Z Z Z q e R V A K o a u f Q n V x n m Y N M Z I F f f h J c J G y p D U N V s O y R I l N b V j 3 o T H r l K t S d J E G V U m 9 Z T O 1 U r J T O 6 1 w x V D k s D d 4 y V Z O m d R m X 8 S k Z r w Q t 3 s b e y F / F e Z 0 3 I 0 G p j S U n r R F d J m Q p U D B b n C k n M k h l l 0 m G d R c V t x n B 3 m H n d S c y c + d 3 B Q k w c + 6 c b T s b u R u z 6 b F T 9 g t A s 9 T d G g W U M F E W O 3 K X u L S E n W 8 y O d 1 9 z 5 U h Y 1 l / h c t + a 6 P j e t u a n P 8 Z r j P o d i k / f D Q R Y x k t j r d h h p O h r b a 0 9 l U i W k 5 j e U 5 T d s h 7 D y q L a L L K I i s T M / j r 2 S / 3 3 C t u + s J C u 6 L l X x p 5 O 6 G N h s j i 2 n q X z d H C tZ f g F X g D Q v A O 7 I E j c A x O A Q Y J + A y + g K + t b 6 0 f r Z + t X 6 V 0 d a X y e Q 4 a q / X 7 D 5 B U Q z o = < / l a t e x i t > 2H < l a t e x i t s h a 1 _ b a s e 6 4 = " D U Y z A x f r N G g p Q d g m R g W / + s s H M 1 4 = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t F 0 v o A t f A l f 0 x 1 i y 0 / g S S a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t l 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H 4 c V G s 7 X V m i 6 8 b I S V 0 U T V O r r Y b L y K + j L J O A i b M G J M N 2 w p 2 8 u J t j R h U K x H m Q F F k h E Z Q N e Z g n A w v X y a a Y H f O q S P U 6 n d R 1 g 8 R W 9 7 5 I Q b M + G x U 3 J i h 8 b n S v A u r p v Z 9 G M v p 0 J l F k Q y C 5 R m D F u J y 7 J x n 2 p I L J v g 2 o m C 2 J j G x V 1 R A r e X O Z p g n l J N N c 0 8 w C B c I z S x E O C U S W I D P N B E D W k y D v B I W n A b J y N I g D F n Z c x S L a 8 C T E X f t S + l 2 j g P k 8 U J U e V 1 e I m w g T K Q u W b L P i x R U l M 7 5 H V 4 6 C r V G t I 6 y q g y m a d 0 r l Z K Z g q v H a 4 Y S A N 3 j 5 e w d M 6 8 M v 8 k k B p 4 q a 7 3 N v Z C / q v M 8 W w 0 a p j S U n r R F d F m R J U D B V w l k n M i + n l 0 W O R R e V t x n B 8 W H n e y 4 E 5 8 7 u B g Q R 7 4 p B t P x + 5 G 7 v p s X v 7 A 0 S 7 2 N G W D J j U V J o z d p e z M I 6 V 5 x 4 9 0 v u D O l 7 J Y c K n P t R d c 2 + f G C 2 7 s c 3 z B c Z 8 j s S m 6 Y S + P G K T 2 u h l G m g 6 G 9 t p T m U w J q f k t 5 e w b N 0 N c e V T b R R 5 R k d q J H 8 d e y f 8 + Y d t 3 V p K V X Z e q / N N J X Q 5 s P s W W 0 1 S + b o r N d N X Q 5 n I 2 j / n n + V z e 4 h I p + n R G 7 / 8 1 a w o 3 p e 6 Z d T 0 9 q o x 1 9 5 q G / t u 5 b J x t b 4 X v t 3 a O d 5 p 7 O 9 W 7 u o Z e o z f o H Q r R B 7 S H P q E j d I o S B O g r + o a + N 3 4 0 b h o / G 7 9 m 0 t W V y u c l q q 3 G 7 z + / Y k L n < / l a t e x i t > 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " D U Y z A x f r N G g p Q d g m R g W / + s s H M 1 4 = " > A A A G M X i c j V T L b h M x F H U L g V J e L e x g Y x E h s R h V m a o C p G 4 q t Z X Y 0 V a 0 S Z W J K s / k T m L F L 9 m e N t F 0 v o A t f A l f 0 x 1 i y 0 / g S S a k 4 x Q J S 4 l v z j n X 9 + E b x 4 p R Y 1 u t m 5 X V e / c b D x 6 u P V p / / O T p s + c b m y / O j M x 0 A q e J Z F J 3 Y m K A U Q G n l l o G H a W B 8 J h B O x 7 t l 3 z 7 E r S h U n y x E w U 9 T g a C p j Q h 1 k H H 4 c V G s 7 X V m i 6 8 b I S V 0 U T V O r r Y b L y K + j L J O A i b M G J M N 2 w p 2 8 u J t j R h U K x H m Q F F k h E Z Q N e Z g n A w v X y a a Y H f O q S P U 6 n d R 1 g 8 R W 9 7 5 I Q b M + G x U 3 J i h 8 b n S v A u r p v Z 9 G M v p 0 J l F k Q y C 5 R m D F u J y 7 J x n 2 p I L J v g 2 o m C 2 J j G x V 1 R A r e X O Z p g n l J N N c 0 8 w C B c I z S x E O C U S W I D P N B E D W k y D v B I W n A b J y N I g D F n Z c x S L a 8 C T E X f t S + l 2 j g P k 8 U J U e V 1 e I m w g T K Q u W b L P i x R U l M 7 5 H V 4 6 C r V G t I 6 y q g y m a d 0 r l Z K Z g q v H a 4 Y S A N 3 j 5 e w d M 6 8 M v 8 k k B p 4 q a 7 3 N v Z C / q v M 8 W w 0 a p j S U n r R F d F m R J U D B V w l k n M i + n l 0 W O R R e V t x⊤ i θ ⋆ = U i for all i ∈ [K].With slight abusing of notations, we define optimal arm a ⋆ = arg max i Z ⊤ i θ ⋆ and suboptimal arm a ′ = arg max i̸ =a ⋆ Z ⊤ i θ ⋆ for the proof.[1] Decomposition by conditioning. We can bound the margin probability by conditioning, asP[U a ⋆ -U a ′ ≤ ε] = E[1(U a ⋆ -U a ′ ≤ ε)] = E[1(U a ⋆ -U a ′ ≤ ε) | U a ′ ≤ H]P[U a ′ ≤ H] + E[1(U a ⋆ -U a ′ ≤ ε) | U a ′ > H]P[U a ′ > H] ≤ E[1(U a ⋆ -U a ′ ≤ ε) | U a ′ ≤ H]P[U a ′ ≤ H] + δ (By the second condition of the proposition) ≤ E[1(U a ⋆ -U a ′ ≤ ε) | U a ′ ≤ H] + δ ≤ E E[1(U a ⋆ -U a ′ ≤ ε) | {U a ′ ≤ H} ∩ Ω ⋆ i ({z j } j̸ =i )] + δ ≤ E E[1(0 ≤ U i -max j̸ =i z ⊤ j θ ⋆ ≤ ε) | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j } j̸ =i )] + δ = E E[1(max j̸ =i z ⊤ j θ ⋆ ≤ Z ⊤ i θ ⋆ ≤ ε + max j̸ =i z ⊤ j θ ⋆ ) | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j } j̸ =i )] + δWe set the density ofZ i | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j } j̸ =i ) and Z ⊤ i θ ⋆ | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j } j̸ =i ) as f 2 and g 2 .[2] Support of f 2 (•), g 2 (•) and their geometry. We first examine the support of the conditional density f 2 , which is a density ofZ i = z | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j } j̸ =i ). Under the given Ω ⋆ i ({z j } j̸ =i ), we have z ⊤ θ ⋆ ≥ max j̸ =i z ⊤ j θ ⋆ by the definition of Ω ⋆ i ({z j } j̸ =i ), since arm i should be the optimal arm. When we write max j̸ =i z ⊤ j θ ⋆ = b with b ≤ H, the support of f 2 becomes{z ∈ A | z ⊤ θ ⋆ ≥ b}.Recall that A := supp(Z i ) and it has equal section with direction θ ⋆ . Using Lemma 1, the density f 2 (•) has LAC with constant function L(R) and it has bounded decay rate √ dL(R) by Lemma 3.[3] Bounding one-side decay rate.Next we aim to bound the one-side decay rate ofZ ⊤ i θ ⋆ = y | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j } j̸ =i ). Define the (conditional) density of Z ⊤ i θ ⋆ = y | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j }) as g 2 (y).Then, its support is restricted to the region {y | b ≤ y ≤ H + 1}.The one-side decay rate of the projected densityZ ⊤ i θ ⋆ = y | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j }) is bounded by √ dL(R) in the interval [b, b + 1 2 ].Proof First, we observe that the support ofZ i | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω ⋆ i ({z j }) is form of interval [b, H + 1]. This holds from the definition of Ω ⋆ i ({z j } and our design of A. Also this support has equal sections with direction θ ⋆ . This is straightforward from the condition that A is a cylindrical set with the direction θ ⋆ and intersection with {z ∈ R d | z ⊤ θ ⋆ ≥ b} also makes equal section with θ ⋆ . Since b ≤ H, we can apply Lemma 8 we get wanted result.3) Bounding maximum density by applying Corollary 5. Using the previous Lemma 5 and we can conclude that the maximum density is bounded by 3√ dL(R) in the interval [b, b + 1 2 ]. Finally, we get the wanted result:E[1(max j̸ =i z ⊤ j θ ⋆ ≤ Z i ≤ max j̸ =i z ⊤ j θ ⋆ + ε | {max j̸ =i z ⊤ j θ ⋆ ≤ H} ∩ Ω i ({z j })] ≤ 3 √ dL(R)ε for any ε < 1 2 .In this section, we prove our main theorems stated in Section 4.3.This section presents operations to construct truncation sets, which will be used in the proof of our main results. In the proof, we first truncate our contexts X ∈ R dK to a truncation set C = K i=1 D, where D ⊂ R d , 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 a set A and a vector v, we define the following process: the filling of 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 v. This procedure ensures that all sections of A along the direction v are equal. Recall that π S (A) denotes the projection of A onto the subspace S. If S is the subspace spanned by a vector v, we write π v (A), which is a subset of a straight line.For A ⊂ R d and v ∈ S d-1 , We define C[A, v] := π ⟨v⟩ ⊥ (A) + vπ v (A)After the completion, the section sliced by the normal hyperplane of v is the same.A ⊂ R d and v ∈ S d-1 , ∥P(A, v)∥ ∞ ≤ ∥A∥ ∞ + 2 holds.Proof For any y ∈ P(A, v), there is y ′ ∈ A such that y = y ′ + tv for |t| ≤ 2. Then, it is straightforward by taking the sup norm.Our goal is to proveE[X a θ (X(t)) (t)X a θ (X(t)) (t) ⊤ ] ≥ λ ⋆ (t) > 0for any t and θ. Then, we fix arbitrary history H t-1 and fix any θ ∈ S d . For simplicity, define(X ⊤ 1 . . . X ⊤ K ) as the conditioned random variable of (X 1 (t) ⊤ . . . X K (t) ⊤ ) | H t-1 .The condition of Theorem 2 means that X = (X ⊤ 1 . . . X ⊤ K ) satisfies boundedness Assumption 2 and LAC condition. Under conditioning the history H t-1 , we aim to apply the Proposition 2 for any θ and v. We also set a = arg max X ⊤ i θ and for any fixed v ∈ R d , ∥v∥ = 1, our goal is to calculate the lower bound ofE[v ⊤ X a X a v ⊤ ].We can view it as the fixed history random variable and we aim to use the arguments developed in Section E.To use Proposition 2, we first truncate our contexts (X ⊤ 1 , . . . X ⊤ K ) into some region C v 1 and then apply Proposition 2 to the truncated contexts. To meet the geometric conditions of Proposition 2, we do the truncation.We first define the truncation set rigorously.1. Define R 1 = c 0 x max (2 + log dK). 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Yes, we provide whole details in Appendix L.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: Yes, we 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: Yes, we include them in Introduction and Appendix K.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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).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 a single parameter with separate contexts, as is predominantly studied in the linear contextual bandit literature[1, 4,20,30,33]. WhileBastani 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 J that the Gibbs distribution does not satisfy the diversity condition when extended to cases with more than two arms.= 1 -1 √ Twhich means that it satisfies the condition of Proposition 3 with δ = 1 √ T .Further details on discrete contexts are in Appendix J.We used jupyter notebook to run the experiments. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: The paper addresses the problem of linear contextual bandits with randomly generated contexts from a distribution 
$f$. The goal is to determine under which conditions on $f$ a greedy algorithm (outlined in Algorithm 1) achieves reasonable regret.

By 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.
strength_weakness: strength_weakness: The only weakness I see is the lack of discussion about the optimality of the achieved regret concerning the parameters of interest, i.e., 
$d$ (dimension of the context), 
$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.
questions: 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.

2. 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)?

3. I would appreciate it if the authors addressed my question in the weaknesses section.
limitations: limitations: The authors adequately address the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The authors should provide (possibly not-to-far-fetched) distributions in which the LAC fails.
- 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$.


**(Minor) Typography suggestions**
- 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{..})
- The pseudocode in Algorithm 1 seems wrong...? the while loop should be an If-Else.
- In pg. 6, "Consider the desnity" -> "Consider the density"
- If accepted, the authors should include the full regret bound from Appendix B.3 in the main text.
questions: 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.
- 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)?
- 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.
- (minor) 



[1] https://proceedings.mlr.press/v206/banerjee23b.html
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. 89, 264: It’s unclear what the entries of this Gram matrix represent.

2. 24-25: It’s not explained why healthcare and clinical domains might find exploration infeasible or unethical.

3. 57: The specifications of margin condition are not explained.

4. 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. 

5. 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.

6. 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.

7. 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.

8. 490: There is a typo as these algorithms are stated as linTS and linUCB instead of LinTS and LinUCB.

9. 114: There is another typo: "unecessary" should be "unnecessary".

10. 352: Experiment results are not discussed extensively, making it hard to understand how the experiments support the claims.
questions: 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.

- 246: What do the authors mean by if two challenges are “satisfied”? Do you mean “overcome”?
limitations: limitations: - Technical contribution: The most significant proof, which is the proof that the given distributions satisfy the LAC condition, was left out.
paper_summary: paper_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. 

The 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.
strength_weakness: strength_weakness: Edit: after reading the rebuttal and discussing with other reviewers I decided to increase my score 
______________________________

In 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.

Then 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.

Overall, 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.
questions: 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.

* 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? 

* What is special about unbounded context that make it relevant to keep the distinction in the paper? 

* 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.

* Additional related question: what $\epsilon$ is used in the analysis?
limitations: limitations: Not applicable

Comments: title: Thank you
Thank you
Thank you
Thank you
Rebuttal acknowledgment
Answers to Reviewer's Questions
comment: Dear Reviewer Fhbd,
Thank you for your open-mindedness in recognizing our work and for the increased score. We will make sure to improve our writing, particularly in the appendix, for the final version.
Dear Reviewer PGWV,
Thank you for your open-mindedness in recognizing our work and for the increased score. We will make sure to improve our writing, particularly in the appendix, for the final version.
Thank you very much for your in-depth response. After reading it and discussing with other reviewers I acknowledge that 
* My concern about the setting is an opinion and should not be a motive for rejection.
* My technical questions are answered, thank you.

Furthermore, it seems that some reviewers have been able to check in detail the theoretical results, leading them to strongly support the paper. In that case, I am happy to increase my score and recommend acceptance. However, I still believe that some rewriting might be beneficial to improve the clarity of the final version of the paper.
Thank you for addressing my questions. While I haven't had the opportunity to thoroughly go over the entire referenced paper to verify the statement, it appears to be accurate. However, due to the need for improvements in the clarity and organization of your paper, I have adjusted my score to 5.
Reviewer qUQr, 

Thank you very much for your continued support and for recognizing the value of our work. We will definitely incorporate your feedback, along with the other reviewers' suggestions, to improve our presentation in the appendix (including adding a table of contents at the beginning of the appendix). If you have any questions in the meantime, please feel free to reach out to us!
Thanks for the detailed response, which have addressed all my questions. I will retain my score.

But, please do make sure to take the other reviewers' concerns and suggestions on the paper's organization, including
- table of contents (a suggestion of mine that I forgot to mention)
- significantly reorganizing Appendix so that the readers can easily locate the main proof.
- typos
- etc
We sincerely appreciate your feedback and your willingness to reassess your score. We are more than happy to provide the responses to your questions.

---
**[1]** It is a great question.
First, following the setup you mentioned, let $Z := X_{(1)} - X_{(2)}$.  
If the density of $Z$ is upper bounded by some constant $M$, then for any $\epsilon > 0$,

$$
\mathbb{P}[0 \leq Z \leq \epsilon] \leq M\epsilon
$$
holds. We emphasize again that $M$ is independent of the choice of $\epsilon$; it depends only on the context distribution and $K$.  In the proof of regret analysis, we choose an arbitrary $\epsilon$. Hence, we want this inequality to hold for all $\epsilon$.  
Then, for a fixed $K$, our next question becomes: "What is the upper bound of $M$?"

Our margin constant $C_\Delta$ is closely related to the maximum density by the above argument, and we bound the maximum density of the suboptimality gap of contexts throughout the paper.
(Our definition of Challenge 2 includes an additional term $\frac{1}{\sqrt{T}}$ due to some technical reasons, but it is weaker than the above inequality).

For a 1-dimensional uniform distribution, it is widely known that $M \asymp K$ (you can refer to any textbook on extreme value theory, such as [12]). However, for a $d$-dimensional uniform distribution within a ball, $M$ **decreases** rapidly as $d$ increases, which is a beneficial effect of high dimensionality. For details, please see Appendix I.8, where this matter is explicitly discussed.

For Gaussian or other light-tailed distributions, $M$ exhibits a logarithmic dependency on $K$. Some asymptotic results for $M$ with respect to $K$ are proven in [12], and we provide a non-asymptotic bound that maintains this logarithmic dependency.
This corresponds to the unbounded contexts case in our paper, and all of our results match the known asymptotic results.

Regarding the experiment you mentioned, the difference between order statistics $X_{(1)} - X_{(2)}$ (two extremes) is well-known, with its asymptotic distribution understood. As stated earlier, for the 1-dimensional uniform distribution, this difference is proportional to $K$, while for Gaussian or light-tailed distributions, it is proportional to $\log K$. For the $d$-dimensional uniform distribution, it necessarily depends on both $K$ and $d$, and decreases with $d$.
Given this solid theoretical foundation, we expect experimental results to align with these predictions. However, if you would like additional experimental results, we can provide them. We have also adjusted our approach to derive a non-asymptotic bound that applies to the bandit problem, and our results remain valid under this scenario.

---

**[2]**
The expection is taken only with respect to $\mathbf{X}(t)$.
At time $t$, for any fixed history $H_{t-1}$, we perform the greedy policy with the estimator $\hat{\theta}_{t-1}$.

Hence, when the entire set of contexts $\mathbf{X}(t) = (X_1(t), \dots, X_K(t))$ is revealed, $a(t)$ is determined immediately given the history $H_{t-1}$.
Then the exact statement is:

"At time $t$, for any history $H_{t-1}$,

$$
\mathbb{E} {\tiny{\mathbf{X}(t)}} [X_{a(t)}(t) X_{a(t)}(t)^\top] \succeq \lambda_\star I_d
$$

holds with some $\lambda_\star > 0$."

In the proof, we proved a stronger statement:

"For any greedy policy with any $\theta \in \mathbb{R}^d$,

$$\mathbb{E}{\tiny{\mathbf{X}(t)}} \left[X_{a(t)}(t) X_{a(t)}(t)^\top\right] \succeq \lambda_\star I_d$$

holds with some $\lambda_\star > 0$."

And yes, there should be a transpose sign. Thank you for pointing this out. Hope our answers provided clarification. If you have any questions, please let us know.
I would like to thank the authors for all their clarifications. I have a few clarifying questions before I reassess my score. 

1. Equation (3) suggests that the probability that the minimum sub-optimality gap is small is also small. Specifically, the probability that the gap falls below $\varepsilon$ is proportional to $\varepsilon$. The proportionality constant, $C_{\Delta}(t)$ has been further bounded in Theorem 3, and a growth rate of $O(\log K)$ has been established. I suspect that this is a weak bound. Here's a counterexample:

Assume $d=1$, and randomly sample $K$ points uniformly from $[0,1]$. The suboptimality gap would be proportional to the gap between the first and second order statistics $X_{(1)} - X_{(2)}$, where we have defined $X_{(1)} > X_{(2)} > \cdots X_{(K)}$. Now, as $K$ increases, I think the minimum gap should shrink (larger the number of contexts, lower the sub-optimality gap). Hence, for a large number of contexts, say $O(1/\varepsilon)$, the probability in (3) may no longer be small, thus, violating the LAC property. Is my understanding correct? To verify my hypothesis, I suggest the authors a simple simulation: Sample $K$ points between $[0,1]$ uniformly at random. In x axis, plot $K$, and in the y axis, plot $X_{(1)} - X_{(2)}$. The authors can use $K = 5$, $100$, $500$, $1000$.

2. Additionally, I have a clarification question. Is the expectation in the diversity constant equation (Equation 2) with respect to contexts $X(t)$, or both $X(t)$ and $a(t)$? Also, I believe the second $X_{a(t)}(t)$ should have a transpose sign.
Reviewer Lk9D, Thank you very much for recognizing the value of our work and for your support. If you have any questions in the meantime, please feel free to reach out to us!
We would like to express our sincere gratitude for taking the time to review our paper and for the opportunity to engage in this discussion. We encourage the reviewers to reflect on the following point: Tackling and improving a long-standing, critical open theoretical problem—where progress has previously been limited (with the community having previously recognized only Gaussian and Uniform distributions as effective for greedy algorithms)—holds significant value for both the bandit research community and the larger NeurIPS community.

- Identifying which context distributions enable greedy bandit algorithms to achieve a sublinear regret is a significant challenge, and the research community had not known much beyond Gaussian and Uniform.
- Constructing the common key characteristic of these distributions admissible for greedy algorithms marks an important milestone.
- Proving that the newly identified and characterized distributions actually allow for poly-logarithmic regret is a breakthrough that no previous work has achieved.
- Furthermore, we achieve this without assuming a margin condition—proving that these distributions naturally induce margins, which is a novel finding even for Gaussian distributions.

We strongly believe that contributions that this paper presents merit acknowledgment. We are confident that our research offers substantial value to the NeurIPS community. We remain open to making minor revisions to further clarify our contributions and to address any feedback or questions from the reviewers. If there are any additional comments or concerns, please do not hesitate to contact us. We truly appreciate the time and effort you have invested in reviewing our work.
I would like to thank the authors for the rebuttal. For now, I will maintain my current score. I plan to discuss the paper with the other reviewers and look forward to the author's discussions with them as well. I will update my score accordingly.
**[Q1]**
**No, your first sentence (premise) in the question is incorrect:** The LAC condition **does not "imply a mode of the context distribution in zero.""**

It seems there might be a misunderstanding of the LAC condition's properties. If you need any clarification, please feel free to let us know.

Regardless, if you are still interested in a shifted mean, it turns out that this is not an issue at all. Our regret bound still holds. For example, for the Gaussian with a shifted mean, please see Appendix C.1.


Here is a imple explanation. Let the mean zero contexts $\mathbf{X}(t)$'s density as $f(x)$ with LAC fuction ${L}(\cdot)$.
Then, the shifted contexts with mean $\mu$ has density $g(x) = f(x + \mathbf{\mu})$ and see that

\begin{align*}
 \lVert \nabla \log g(x) \rVert_{\infty} &= \lVert \nabla \log f(x + \mu) \rVert_{\infty} \\
 &\leq L( \lVert x + \mu\rVert_{\infty}) \\
 &\leq L( \lVert x \rVert_{\infty} +\lVert \mu\rVert_{\infty})
\end{align*}

Hence the density $g(x)$ has LAC with function $L'(x) = L (x + \lVert \mu \rVert_{\infty})$
and since $\lVert \mu\rVert_{\infty} = O(1)$, it has the same rate.

**[Q2]**
We believe **there is a misunderstanding in the comment here**. We do NOT assume i.i.d. of arms at all. We only assume the independence of the entire arm set over time (note there is a clear difference between i.i.d.-ness vs. independence only; independent of each arm vs. independence of the arm set!), and hence we allow that arms can even be dependent on each other in a given arm set. A rich body of linear contextual bandit studies assumes stochastic contexts and independence of the contexts (often even stronger i.i.d. contexts) over time [5, 8, 15, 16, 25, 28].

In particular, all of the relevant greedy contextual bandit literature assumed even i.i.d.-ness (often i.i.d. for each arm), which is stronger than our problem setting that only requires independence of the arm set (not each arm or i.i.d.). We emphasize again that $X_i(t), X_j(t)$ can be correlated for $i, j \in [K]$. Hence, we strongly believe that justification is provided in order for our work to be fairly evaluated (note again our problem setting is even weaker than the previous problem setting in greedy contextual bandits).

**[Q3]**
We are happy to address this question. The reason we present both bounded and unbounded contexts (particularly why we include analysis for unbounded context) is because previous works in greedy contextual bandits largely utilized unbounded noise (e.g., Gaussian) in feature setups. Hence, for fair comparisons with the existing results, we feel that it is fair to include unbounded cases [25, 28, 29].

There is also a technical reason to separately consider the two cases. Boundedness assumptions affect the regret bound differently. Hence, we would like to use appropriate soft boundedness of unbounded contexts. If we were to assume conventionally accepted $\ell_2$ boundedness for light-tail unbounded distributions, there could be a dimension dependency for the high-probability bound. Generally, it has a $\tilde{O}(\sqrt{d})$ bound which is often ignored but can be significant. However, since we assume $\psi_1$ or $\psi_2$ norm boundedness for unbounded contexts, it is dimension-free and we can get a tighter bound even in a more transparent manner.

**[Q4-5]**
Please see the answer to W2 part; we think it will help understand your questions in the proof sketch. We would be happy to answer any further questions.