Pith. sign in

REVIEW 3 major objections 6 minor 84 references

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

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that one condition on the context distribution — no sharp log-density growth — makes an exploration-free greedy bandit algorithm achieve poly-logarithmic regret.

desk verdict Genuine step forward for greedy linear contextual bandits, but the abstract oversells untruncated heavy-tailed contexts; the real theorem needs psi1-boundedness, and for Cauchy the regret isn't even defined. read the letter →

arxiv 2411.12878 v2 pith:MK4CZJ2L submitted 2024-11-19 stat.ML cs.LG

Seok-Jin Kim , Min-hwan Oh This is my paper · ORCID
classification stat.MLcs.LG MSC 62L0568W27
keywords linearcontextualbanditsgreedyalgorithmexploration-freeLocalAnti-Concentrationlogarithmicregretmarginconditionstochasticcontexts
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Pure exploitation, with no deliberate exploration, is enough to learn optimally in linear contextual bandits, provided the context distribution's log-density does not change too sharply anywhere. The paper introduces the Local Anti-Concentration (LAC) condition — $\|\nabla \log f(x)\|_\infty$ bounded by a polynomial in $\|x\|_\infty$ — and proves that under it the greedy algorithm LinGreedy achieves cumulative expected regret $O(\mathrm{poly}\log T)$, with dimension dependence $\tilde{O}(d^{2.5})$ for unbounded contexts. This matters because exploration is often expensive, infeasible, or ethically fraught (healthcare is the recurring example), and previous efficiency guarantees for greedy bandits covered essentially only Gaussian and uniform contexts or required a separately assumed margin condition. Under LAC the two ingredients those earlier analyses assumed — growth of the selected-context Gram matrix's minimum eigenvalue and a probabilistic upper bound on the suboptimality gap — follow as theorems rather than assumptions. The LAC class contains Gaussian, exponential, uniform, Laplace, Cauchy, and Student's $t$ distributions and their truncated variants, the widest class of context distributions for which exploration-free bandits are known to be provably near-optimal.

What carries the argument

The Local Anti-Concentration (LAC) condition: a density $f$ satisfies it when $\|\nabla \log f(x)\|_\infty \le L(\|x\|_\infty)$ for a non-decreasing polynomial $L$, a uniform control on how fast the log-density slopes upward that rules out sharp local concentration while still allowing heavy tails. Its load-bearing property is that it bounds the one-sided decay rate of every one-dimensional projection of the conditional distributions the greedy policy induces, and it is preserved under conditioning with the same function $L$, so conditioning on the event that arm $i$ is chosen does not break the hypothesis. Three lemmas convert decay rates into the constants the regret proof needs: a bounded one-sided decay rate forces a variance lower bound (Lemma 4) and a maximum-density upper bound (Lemma 5), and for sets with equal or expanding hyperplane sections the section density inherits the same decay (Lemma 8). Truncation to high-probability regions extends the analysis to unbounded contexts, a separate section-geometry argument covers naturally bounded contexts, and a peeling concentration argument then sums the per-round bounds into the final poly-logarithmic regret.

What would settle it

Run LinGreedy with two arms and small dimension on contexts drawn from an untruncated Cauchy distribution out to $T = 10^6$: if the cumulative regret follows a power law in $T$ rather than a poly-logarithmic curve, the $\psi_1$ premise carries the theorem and the advertised Cauchy coverage holds only after truncation; if the regret stays poly-logarithmic, the theorem's tail assumption is stronger than necessary.

Watch

Extended reading notes

Core claim

The paper's central claim is that a single distributional condition simultaneously guarantees everything a greedy algorithm needs. Concretely: if the context distribution satisfies LAC with a polynomial $L$, Assumptions 1–2 hold (context sets independent across time; contexts bounded, or unbounded with bounded $\psi_1$ norm), then LinGreedy — an OLS-based algorithm that always pulls the arm maximizing estimated reward and never explores — has cumulative expected regret $\mathrm{Reg}(T) \le O(\mathrm{poly}\log T)$, and for unbounded contexts the bound reads $\tilde{O}(d^{2.5})$ with dependencies at most polynomial in $d$ and $K$ in the bounded case. The two constants that dominate greedy regret are derived, not assumed: the diversity constant $\lambda_\star(t) \ge \Omega(1/d)$ (Theorem 2) and the margin constant $C_\Delta(t) \le \tilde{O}(\sqrt{d})$ (Theorem 3), both following from LAC alone. The paper additionally states that the OLS estimator is $\sqrt{t}$-consistent, $\|\hat\theta_t - \theta^\star\|_2 \le \tilde{O}(d/\sqrt{t})$ with high probability, a property it notes that exploration-based UCB and Thompson sampling analyses do not generally provide.

Load-bearing premise

For unbounded contexts the proof rests on Assumption 2, which requires the context vectors to have a finite $\psi_1$ (sub-exponential) norm, so genuinely heavy-tailed laws such as untruncated Cauchy or Student's $t$ lie outside the theorem's formal scope and are covered only in truncated form.

Editorial extensions

If this is right

  • For every context distribution in the LAC class, a pure greedy policy matches the regret order of exploration-based algorithms, removing the exploration-exploitation trade-off in deployments where exploration is costly or unwelcome.
  • The margin (low-noise) condition that earlier greedy-bandit analyses assumed becomes a derived consequence with explicit constants $C_\Delta(t) \le \tilde{O}(\sqrt{d})$.
  • The OLS estimator under adaptively chosen greedy contexts is $\sqrt{t}$-consistent, which gives sample-complexity and PAC-type statements that standard UCB and Thompson sampling analyses do not deliver.
  • For bounded-support contexts the bound stays polynomial in $d$ and $K$ while remaining poly-logarithmic in $T$, so the guarantee does not silently degrade as the number of arms grows.
  • Gaussian, uniform, Laplace, exponential-family, and truncated heavy-tailed contexts (Cauchy, Student's $t$) are all certified, widening the provably admissible class well beyond the Gaussian and uniform pair.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • My inference: because LAC is stated through the density's log-gradient, its certified class is continuous contexts; extending it to discrete or categorical features will need a new anti-concentration notion, and the paper's own appendix observes that Gibbs-style discrete distributions fail the diversity condition once $K \ge 3$, so the extension is non-mechanical.
  • My inference: the $\psi_1$ tail assumption is load-bearing rather than bookkeeping, since untruncated heavy-tailed contexts formally fall outside Theorem 1; replacing it by a polynomial-moment condition with a growing truncation radius is a plausible route, at the cost of larger dimension constants.
  • My inference: the mechanism — LAC survives conditioning, so every deterministic policy-induced distribution keeps its decay-rate bound — should transfer to other settings where actions are greedy functions of an estimated parameter, such as generalized linear bandits or greedy policy search.
  • My inference: the paper predicts graceful degradation as the LAC function $L$ grows, but not beyond it; a bounded-support density with super-polynomial log-slope (e.g., $f \propto \exp(-\exp(x))$) sits outside the LAC class, and Theorem 2's diversity mechanism should measurably collapse there, a probe worth running.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper introduces a Local Anti-Concentration (LAC) condition, a bound on the ∞-norm of the log-density gradient, and claims that for context distributions satisfying LAC, the exploration-free LinGreedy algorithm for linear contextual bandits enjoys O(poly log T) expected regret. The proof strategy is modular: LAC is used to bound the decay rate of densities, which yields a lower bound on the diversity constant λ⋆(t) (Theorem 2) and an upper bound on the margin constant C∆(t) (Theorem 3); these two ingredients are then combined with a standard regret decomposition to obtain the main result (Theorem 1). The paper also claims that the LAC class includes Gaussian, exponential, uniform, Cauchy, and Student's t distributions, together with many exponential-family and truncated variants.

Significance. If the main theorem is correct, this is a valuable contribution: it replaces earlier Gaussian- or uniform-specific analyses of greedy contextual bandits with a general density condition, and it derives rather than assumes the diversity and margin constants. The appendix gives a detailed, modular proof with no fitted parameters, and the comparison with the earlier Gaussian √T bound of Kannan et al. provides a useful external anchor. The paper is also candid in places: Table 1 lists truncated Cauchy and truncated Student's t, and Appendix K records that Gibbs distributions fail the diversity condition for K ≥ 3. However, the abstract and Section 3.2 substantially overstate the scope of the regret theorem: the advertised untruncated heavy-tailed examples do not satisfy the assumptions under which the theorem is proved, and for untruncated Cauchy the paper's own regret definition is not even finite. The central derivation appears defensible under the stated assumptions, but the headline claims need to be narrowed and reworded.

major comments (3)
  1. [Abstract, Section 3.2, Table 1, Section 5.1] The abstract and Section 3.2 state that the LAC class includes Cauchy and Student's t distributions and that 'under our proposed LAC condition' the greedy algorithm achieves O(poly log T) regret. However, Theorem 1 is proved only under Assumptions 1 and 2, and for unbounded contexts Assumption 2 requires a finite ψ1 norm. For Cauchy and for Student's t with any finite degrees of freedom, the ψ1 norm is infinite: for Student's t with ν degrees of freedom, E|X|^p is infinite for p ≥ ν, so the supremum in the definition of the ψ1 norm diverges. The truncation argument in Appendix G.2.1 and Claim 4, which are load-bearing for Theorem 2, rely on the sub-exponential tail bound that follows from a finite ψ1 norm. Table 1 correctly lists truncated Cauchy and truncated Student's t, but the abstract and Section 3.2 do not qualify the examples. The paper should explicitly state that the regret theorem applies to the class 'LAC ∩ {bounded or ψ1-bounded contexts}' and that the heavy-tailed examples are covered only in truncated form.
  2. [Section 2.2, Abstract] For untruncated Cauchy contexts, the expected regret as defined in Section 2.2 is not finite. If θ* has a nonzero component and Xi is Cauchy, then E|Xi| is infinite, so E[Xi(t)⊤θ*] is undefined and the expression Reg(T) = Σ_t E[X_a*(t)⊤θ* − X_a(t)⊤θ*] is not a finite quantity for any algorithm. Consequently, the abstract's inclusion of untruncated Cauchy among the distributions for which logarithmic regret is proved is incompatible with the paper's own regret definition. This is not a minor technicality: it means that the advertised heavy-tailed examples cannot be repaired by a sharper proof within the same problem formulation. The authors should either state that untruncated heavy-tailed examples are outside the scope of the regret guarantee or define a modified (e.g., truncated or otherwise regularized) regret notion.
  3. [Section 5.2, Section 3] The phrase 'under our proposed LAC condition' is stronger than what is shown. Theorem 1 requires not just LAC but also Assumption 1 (independence of context sets across rounds) and Assumption 2 (boundedness or ψ1-boundedness). The LAC condition alone is not sufficient for the regret conclusion, and in fact a density can satisfy LAC while having infinite first moments, so the paper should not present LAC as the sole enabling assumption. The theorem should be phrased as a result for the class 'LAC ∩ {Assumptions 1 and 2}', and the introduction and abstract should avoid the implication that the LAC condition by itself characterizes the distributions for which exploration-free greedy learning is efficient.
minor comments (6)
  1. [Section 3.2] The exponential density is written as f_X(x) = (1/λ) exp(−λx), which is missing the normalizing factor λ; the derivative calculation is unaffected, but the displayed density is incorrect.
  2. [Table 1] The last row, 'PDF f ∝ exp(−π) with polynomially growing π', is ambiguous because π is also used as a constant elsewhere; it should be written with a function such as V(x) or π(x).
  3. [Discussion of Theorem 2, Section 5.3.1] The discussion states λ⋆(t) ≥ Ω(1/d), but the displayed bound is c/(d (A1 + A2(R1+2)^α)^2), and A2(R1+2)^α can grow like a power of log d for unbounded contexts. The Ω(1/d) statement should be qualified as holding up to factors depending on L(R1) or should be restated as Ω(1/(d L(R1)^2)).
  4. [Throughout] There are numerous typographical errors ('Univeristy', 'simplicty', 'greey', 'wide rage', 'Dicussions') and the phrase 'sharp poly-logarithmic regret' is not supported by a lower bound. A careful proofreading pass and a more conservative choice of 'sharp' are recommended.
  5. [Appendix K] The negative result for Gibbs distributions with K ≥ 3 is interesting and relevant to the paper's claimed scope; it appears only in a footnote and in the appendix, so it would be helpful to summarize this limitation in the main text when discussing the breadth of the LAC class.
  6. [Proof of Claim 1, Appendix F.3.1] The sentence 'Choose one of v, −v such that ⟨·, θ⟩ ≥ 0' is unclear notation; it should be written in terms of the sign of ⟨v, θ⟩ or ⟨−v, θ⟩.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1's regret bound is derived from the LAC condition and explicit assumptions, with λ* and C∆ derived rather than fitted.

full rationale

The derivation chain is self-contained. Definition 1 gives LAC as a polynomial bound on ||∇log f||∞. Theorem 2 lower-bounds the diversity constant λ*(t) by a function of the LAC growth constants A1, A2, α, the dimension d, and the ψ1 bound xmax; Theorem 3 upper-bounds the margin constant C∆(t) by a similar expression. No fitted parameters are renamed as predictions: both constants are proven bounds, and the final regret bound in Section G.4 substitutes these bounds into Proposition 9's self-normalized concentration analysis. The truncation and partial-completion constructions (G.2.1) are part of the proof and do not import the conclusion. The only self-citation (Oh et al. [28]) is used as a comparison of known results and is not load-bearing. The paper's advertised inclusion of untruncated Cauchy and Student's t conflicts with Assumption 2's ψ1-boundedness, but that is a correctness/scope concern outside the circularity definition. The central claim is therefore not circular.

Assumptions & free parameters 0 free parameters · 6 assumptions · 3 invented entities

The central derivation rests on (1) the LAC condition, a domain assumption about the context density; (2) Assumption 1 (independent contexts); (3) Assumption 2 (bounded ψ1 or ℓ2 norm); plus standard sub-Gaussian reward noise and standard concentration tools. The proof invokes internal geometric devices (set completion, partial completion, section densities) whose properties are proven in the appendix rather than assumed. No parameters are fitted to data: all constants are universal or determined by the distribution (A1, A2, α, xmax), and the truncation radii are explicit functions of xmax, d, K, T. The LAC condition is the authors' own definition, but it is verified by direct computation for concrete distributions and yields falsifiable regret predictions, so its introduction is not circular.

assumptions (6)
  • domain assumption Contexts admit a joint density f_X whose log-gradient is polynomially bounded (LAC, Definition 1).
    This is the paper's central sufficient condition; it drives the decay-rate bounds (Lemma 3) and hence both Theorems 2 and 3. It is verified for concrete distributions in Appendix C but is an assumption about the data-generating process.
  • domain assumption Assumption 1: context sets X(1),...,X(T) are independent across time (non-identically distributed allowed).
    Needed for the self-normalized/martingale concentration (Appendix J) and for the fixed-history analysis to treat X(t) as exogenous given H_{t-1}.
  • domain assumption Assumption 2: unbounded contexts satisfy bounded ψ1 norm xmax; bounded contexts satisfy ℓ2 norm at most xmax.
    Used to construct high-probability truncation sets (scales R1, R2), to apply ψ1 tail bounds, and to bound X_i^T v in the regret assembly (Appendix J.2). Excludes untruncated heavy-tailed laws such as Cauchy.
  • standard math Reward noise η_t is conditionally σ-sub-Gaussian.
    Standard bandit assumption; needed for the self-normalized concentration used in the ℓ2 estimation bound (Appendix J).
  • standard math Standard concentration tools: ψ1 tail bounds, matrix martingale inequalities (Tropp), self-normalized processes (de la Peña et al.).
    Invoked in Appendices N and J; standard results from the cited literature.
  • standard math Geometric section machinery (set completion C[A,v], partial completion P(A,v), section-density decay Lemmas 8, 10, 16, 17) is internally proven.
    Claims 1-3 and Lemmas 10, 16, 17 supply the section geometry that converts LAC decay rates into variance lower bounds and max-density bounds; no external geometric axiom beyond Euclidean geometry.
invented entities (3)
  • Local Anti-Concentration (LAC) condition / LAC class independent evidence
    purpose: A sufficient distributional condition (||∇ log f||∞ polynomially bounded) under which the exploration-free LinGreedy algorithm provably attains O(poly log T) regret; it substitutes for previously assumed diversity and margin conditions.
    The condition is directly checkable for any density (Appendix C computes it for Gaussian, Laplace, exponential, uniform, Cauchy, Student's t, and truncations), and it yields falsifiable quantitative predictions: bounded margin and diversity constants feed a (log T)^4 regret bound, partially validated by the experiments in Section 6.
  • Diversity constant λ⋆(t)
    purpose: Lower bound on the minimum eigenvalue of the Gram matrix of policy-selected contexts; positive λ⋆ answers Challenge 1 and yields √t estimator consistency.
    A proof-technical quantity defined in Definition 2; Theorem 2 bounds it below by c/(d L(·)^2). It has no physical or data referent outside the analysis.
  • Margin constant C∆(t)
    purpose: Coefficient in the probabilistic bound P[gap ≤ ε] ≤ ε C∆(t) + 1/√T (Challenge 2), used to convert estimator accuracy into log-regret terms.
    Defined in Section 4.3 (Eq. 2) and bounded in Theorem 3; previously the analogous margin condition was assumed in the literature, here it is derived. Proof device only.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit." pith.science (2026). https://pith.science/paper/MK4CZJ2L

@misc{pith2026241112878,
  author       = {Pith},
  title        = {Pith review of: Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MK4CZJ2L}},
  note         = {Machine review of arXiv:2411.12878}
}
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 $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.

Figures

Figures reproduced from arXiv: 2411.12878 by the authors.

Figure 1
Figure 1. The cumulative regret plots of the numerical experiments. The full results are available in [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Illustration of expanding section’s example. The section with direction [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗
Figure 3
Figure 3. Illustration of A1 and expanding sections of v or −v. A1 is the area above the green line. In this case, sections with direction +v are expanding! If a cylindrical set is cut by some hyperplane (which is A1), at least one direction makes expanding sections. 27 [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: Illustration of A1 and expanding sections of v or −v. A1 is the area above the green line. In this case, sections with direction +v are expanding. If a cylindrical set is cut by some hyperplane, at least one direction produces expanding sections. Claim 1 tells us that …
Figure 5
Figure 5. Figure 5: Illustration of S and expanding sections with direction en. Blue lines are sections Sec(S ′ , en, y). If a cylindrical-shaped set is sliced by some hyperplane, at least one direction forms expanding sections. F.4 Key Proposition for Suboptimality Gap Next, we provide a…
Figure 6
Figure 6. Figure 6: Illustration of a cylindrical region A. Next, we show that if the support of each context Zi is a cylindrical set, we can bound the margin constant. We state our key result on bounding the margin constant in the fixed-history setup. Proposition 3 (Key proposition: subo…
Figure 7
Figure 7. Figure 7: Illustration of supp(Zi). It has equal sections with θ ⋆ and ∥Zi∥∞ ≤ R. F.4.1 Proof of Proposition 3 Define Z ⊤ i θ ⋆ = Ui for all i ∈ [K]. With a slight abuse of notation, define the optimal arm a ⋆ = arg maxi Z ⊤ i θ ⋆ and the suboptimal arm a † = arg maxi̸=a⋆ Z ⊤ i …
Figure 8
Figure 8. Figure 8: Illustration of C(A, v). This is the operation of filling the area A in the v-direction. Then, all sections in the v-direction become equal. Lemma 11 Suppose a set A ∈ R d and a unit vector v satisfy πv(A) is an interval with length ℓ. Then, ∥C[A, v]∥∞ ≤ ∥A∥∞ + ℓ. Proo…
Figure 9
Figure 9. Figure 9: Illustration of P(A, v). 35 [PITH_FULL_IMAGE:figures/full_fig_p035_9.png]
Figure 10
Figure 10. Figure 10: Illustration of the set Dv . The red rectangle is D, and Dv is the union with the green boundary rectangle and D. We force the sections in the direction v within [−1, 1]v to be equal. Hence, we can apply the previous results from Proposition 2. Claim 4 For any X satis…
Figure 11
Figure 11. Figure 11: Illustrations of various sections in the ball [PITH_FULL_IMAGE:figures/full_fig_p045_11.png]
Figure 12
Figure 12. Figure 12: Illustration of a projection map. Remark 4 A projection map means a homothety toward some point P. 45 [PITH_FULL_IMAGE:figures/full_fig_p045_12.png]
Figure 13
Figure 13. Figure 13: Illustration of linear section maps. A projection map of [PITH_FULL_IMAGE:figures/full_fig_p046_13.png]
Figure 14
Figure 14. Figure 14: Illustration of the linear section map between two sections of the ball. The linear section [PITH_FULL_IMAGE:figures/full_fig_p047_14.png]
Figure 15
Figure 15. Figure 15: for the intuition. ✓ v SR(✓,b,v,y) P H H→ SR(ω,b,v,y + h) b Q Qh [PITH_FULL_IMAGE:figures/full_fig_p048_15.png]
Figure 16
Figure 16. Figure 16: For the case where θ and v do not form too large an angle, we first define a linear section map between S(θ, y) and S(θ, y + h). This section map can also be the linear section map between S(θ, b, v, y) and S(θ, b, v, y + h). Using this map, we can bound the one-side …
Figure 17
Figure 17. Figure 17: Results For d = 20, K = 20 0 200 400 600 800 1000 Round (t) 0 50 100 150 200 250 Cumulative Regret d=20, K=100, Guassian LinUCB LinTS LinGreedy 0 200 400 600 800 1000 Round (t) 0 100 200 300 400 500 Cumulative Regret d=20, K=100, Uniform LinUCB LinTS LinGreedy 0 200 4…
Figure 18
Figure 18. Figure 18: Results For d = 20, K = 100 3We used jupyter notebook to run the experiments. 60 [PITH_FULL_IMAGE:figures/full_fig_p060_18.png]
Figure 19
Figure 19. Figure 19: Results For d = 100, K = 20 N Technical Lemmas Lemma 22 (Gronwall Inequality) For g(y) ∈ R satisfies g ′ g (y) ≥ −M in [y, y + h], then g(y + h) g(y) ≥ exp(−Mh). Proof See classic PDE books like Evans [16]. N.1 Concentration Inequalities Lemma 23 (Matrix Chernoff : Ad…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

84 extracted references · 76 canonical work pages

  1. [1]

    Abbasi-Yadkori, Y ., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24

    2011

  2. [2]

    and Long, P

    Abe, N. and Long, P. M. (1999). Associative reinforcement learning using linear probabilistic concepts. In International Conference on Machine Learning, pages 3–11

    1999

  3. [3]

    and Lazaric, A

    Abeille, M. and Lazaric, A. (2017). Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176–184. PMLR

    2017

  4. [4]

    and Goyal, N

    Agrawal, S. and Goyal, N. (2013). Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127–135. PMLR

    2013

  5. [5]

    Ariu, K., Abe, K., and Proutière, A. (2022). Thresholded lasso bandit. InInternational Conference on Machine Learning, pages 878–928. PMLR

    work page 2022

  6. [6]

    Auer, P. (2002). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397–422

    work page 2002

  7. [7]

    and Bayati, M

    Bastani, H. and Bayati, M. (2020). Online decision making with high-dimensional covariates. Operations Research, 68(1):276–294

    work page 2020

  8. [8]

    Bastani, H., Bayati, M., and Khosravi, K. (2021). Mostly exploration-free algorithms for contextual bandits. Management Science, 67(3):1329–1349

    work page 2021

Show all 84 references
  1. [9]

    and Li, L

    Chapelle, O. and Li, L. (2011). An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249–2257

    2011

  2. [10]

    Chu, W., Li, L., Reyzin, L., and Schapire, R. E. (2011). Contextual bandits with linear payoff functions. Journal of Machine Learning Research

    2011

  3. [11]

    P., and Kakade, S

    Dani, V ., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference on Learning Theory, page 355–366

    2008

  4. [12]

    De Haan, L., Ferreira, A., and Ferreira, A. (2006). Extreme value theory: an introduction , volume 21. Springer

    2006

  5. [13]

    H., Klass, M

    de la Pena, V . H., Klass, M. J., and Leung Lai, T. (2004). Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws

    2004

  6. [14]

    and WANG, K

    DUAN, Y . and WANG, K. (2023). Adaptive and robust multi-task learning. The Annals of Statistics, 51(5):2015–2039

    2023

  7. [15]

    Durrett, R. (2019). Probability: theory and examples, volume 49. Cambridge university press

    2019

  8. [16]

    Evans, L. C. (2022). Partial differential equations, volume 19. American Mathematical Society

    2022

  9. [17]

    Fan, J., Wang, D., Wang, K., and Zhu, Z. (2019). Distributed estimation of principal eigenspaces. Annals of statistics, 47(6):3009

    2019

  10. [18]

    Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010). Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pages 586–594

    2010

  11. [19]

    and Zeevi, A

    Goldenshluger, A. and Zeevi, A. (2013). A linear response bandit problem. Stochastic Systems, 3(1):230–261

    2013

  12. [20]

    H., Roth, A., Waggoner, B., and Wu, Z

    Kannan, S., Morgenstern, J. H., Roth, A., Waggoner, B., and Wu, Z. S. (2018). A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. Advances in neural information processing systems, 31

    2018

  13. [21]

    and Paik, M

    Kim, G.-S. and Paik, M. C. (2019). Doubly-robust lasso bandit. In Advances in Neural Information Processing Systems, pages 5869–5879

    2019

  14. [22]

    Kim, W., Kim, G.-s., and Paik, M. C. (2021). Doubly robust thompson sampling for linear payoffs. In Advances in neural information processing systems. 11

    2021

  15. [23]

    Kveton, B., Zaheer, M., Szepesvari, C., Li, L., Ghavamzadeh, M., and Boutilier, C. (2020). Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 2066–2076

    2020

  16. [24]

    and Zhang, T

    Langford, J. and Zhang, T. (2007). The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96–1

    2007

  17. [25]

    and Szepesvári, C

    Lattimore, T. and Szepesvári, C. (2019). Bandit Algorithms. Cambridge University Press (preprint)

    2019

  18. [26]

    Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010). A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670. ACM

    2010

  19. [27]

    Li, L., Lu, Y ., and Zhou, D. (2017). Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071–2080

    2017

  20. [28]

    Oh, M.-H., Iyengar, G., and Zeevi, A. (2021). Sparsity-agnostic lasso bandit. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8271–8280. PMLR

    2021

  21. [29]

    H., Lai, T

    Peña, V . H., Lai, T. L., and Shao, Q.-M. (2009).Self-normalized processes: Limit theory and Statistical Applications. Springer

    2009

  22. [30]

    W., and Wu, Z

    Raghavan, M., Slivkins, A., Vaughan, J. W., and Wu, Z. S. (2023). Greedy algorithm almost dominates in smoothed contextual bandits. SIAM Journal on Computing, 52(2):487–524

    2023

  23. [31]

    V ., and Wu, Z

    Raghavan, M., Slivkins, A., Wortman, J. V ., and Wu, Z. S. (2018). The externalities of exploration and how data diversity helps exploitation. In Conference on Learning Theory, pages 1724–1738. PMLR

    2018

  24. [32]

    and Tsitsiklis, J

    Rusmevichientong, P. and Tsitsiklis, J. N. (2010). Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395–411

    2010

  25. [33]

    Sivakumar, V ., Wu, S., and Banerjee, A. (2020). Structured linear contextual bandits: A sharp and geometric smoothed analysis. In International Conference on Machine Learning , pages 9026–9035. PMLR

    2020

  26. [34]

    Sivakumar, V ., Zuo, S., and Banerjee, A. (2022). Smoothed adversarial linear contextual bandits with knapsacks. In International Conference on Machine Learning, pages 20253–20277. PMLR

    2022

  27. [35]

    Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285–294

    1933

  28. [36]

    Tropp, J. A. (2011). User-friendly tail bounds for matrix martingales. Technical report, CALIFORNIA INST OF TECH PASADENA

    2011

  29. [37]

    Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press

    2018

  30. [38]

    Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press

    2019

  31. [39]

    Wang, K. (2023). Pseudo-labeling for kernel ridge regression under covariate shift. arXiv preprint arXiv:2302.10160. 12 Appendix Contents 1 Introduction 1 1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Related Work . . . . . ....

    2023 arXiv

  32. [40]

    Event decomposition by conditioning

  33. [41]

    We know Xi | Ωi({xj}j̸=i) and Xi | Ω⋆ i ({xj}j̸=i) have a bounded decay rate √ dL = eO( √ d)

  34. [42]

    We aim to bound the decay rate of the projected densities X ⊤ i v | Ωi({xj}j̸=i) and X ⊤ i θ⋆ | Ω⋆ i ({xj}j̸=i)

  35. [43]

    PPAag2Q5fZEmfC+YbHHxbqO/4DU=

    If we are able to bound the decay rate of the above projected densities, we can bound the two key constants in the two challenges using Lemma 4 and Lemma 5. For step 3, the remaining important task is to bound the decay rate of the projected densities, which we address in Appe...

  36. [44]

    We first prove that for a fixed θ, v, for densities with LAC and supports satisfying certain geometric conditions, we can bound equation (9)

  37. [45]

    We also prove that for a fixed θ⋆, for densities with LAC and supports satisfying certain geometric conditions, we can bound equation (8)

  38. [46]

    Next, we prove that the densities with LAC and bounded ψ1 norm, for any given θ, v, can be truncated (with high probability) to densities contained in class 1

  39. [47]

    In this section, we provide the results of 1 and 2

    Lastly, we prove that for densities with LAC and bounded ψ1 norm, for any given θ⋆, we can truncate it (with high probability) to densities contained in class 2. In this section, we provide the results of 1 and 2. In the next Appendix G, we proceed to 3 and 4. Now, we build th...

  40. [48]

    Z has LAC with L(·) and ∥ supp(Z)∥∞ ≤ R

  41. [49]

    That is, supp(Z) = AK for some A ⊂ Rd

    For all i ∈ [K], supp(Zi) is identical for some subset A ⊂ Rd. That is, supp(Z) = AK for some A ⊂ Rd. 29

  42. [50]

    Then there exists an absolute constant c >0 such that E[v⊤ZaZ ⊤ a v] ≥ c dL(R)2

    The support A ∩ [−1, 1]v has equal sections with direction v. Then there exists an absolute constant c >0 such that E[v⊤ZaZ ⊤ a v] ≥ c dL(R)2 . Remark 2 For unbounded contexts X(t) in the original bandit problem, we truncate to some region C1 with positive probability and make...

  43. [51]

    First, we examine the support of f1

    Investigating the support of f1 and g1. First, we examine the support of f1. Since arm i is optimal with estimator θ, all z in the support of f1 must satisfy z⊤θ ≥ maxj̸=i z⊤ j θ. Also, because −1 ≤ z⊤v ≤ 1 holds, this support is the intersection of these two areas. Define A1 ...

  44. [52]

    kVTjUxKHngXexWcdVUPlQCrLtyI=

    Bounding one-side decay rate of section density in [−1, 1]. We aim to apply Lemma 4 to bound the variance E v⊤ZiZ ⊤ i v | Ωi({zj}j̸=i) ∩ {Zi ∈ [−1, 1]v} . It tells us that it is enough to bound the one-side decay rate of the section density g1(·) in the interval [−1/2, 1/2]. C...

  45. [53]

    MuOAM2lQOiz/IuMIEoO0FIDQu7k=

    Bounding the desired variance. We now see that the support of g1(·) has the form [c, 1] for some c <1. Hence, by Lemma 4, we conclude E[v⊤ZiZ ⊤ i v | Ωi({zj}j̸=i) ∩ {Zi ∈ [−1, 1]v}] ≥ c dL(R)2 for some absolute constant c >0. Below, we prove Lemma 10, which is used in the proo...

  46. [54]

    That is, supp(Z) = AK

    For all i ∈ [K], supp(Zi) ⊂ Rd is identical for some set A ⊂ Rd. That is, supp(Z) = AK

  47. [55]

    gWDd6YAnwizqQLtvJdFc+5rSyxY=

    For some H > 0, Zi’s support supp(Zi) = A = cyl(B, θ⋆, H+ 1) for all i ∈ [K], and P[Z ∈ (cyl(B, θ⋆, H))K] ≥ 1 − δ. Then P[∆(Z) ≤ ε] ≤ 3 √ dL(R)ε + δ. Remark 3 For the original bandit problem with contexts X(t), we truncate to a high-probability region C2 and set the truncated ...

  48. [56]

    Decomposition by conditioning. We can bound the margin probability by conditioning as P[Ua⋆ − Ua† ≤ ε] = E[1(Ua⋆ − Ua† ≤ ε)] = E[1(Ua⋆ − Ua† ≤ ε) | Ua† ≤ H]P[Ua† ≤ H] + E[1(Ua⋆ − Ua† ≤ ε) | Ua† > H]P[Ua† > H] ≤ E[1(Ua⋆ − Ua† ≤ ε) | Ua† ≤ H]P[Ua† ≤ H] + δ (By the second conditi...

  49. [57]

    We examine the support of the conditional density f2, which is Zi = z {max j̸=i z⊤ j θ⋆ ≤ H} ∩Ω⋆ i ({zj}j̸=i)

    Support of f2(·), g2(·) and their geometry. We examine the support of the conditional density f2, which is Zi = z {max j̸=i z⊤ j θ⋆ ≤ H} ∩Ω⋆ i ({zj}j̸=i). Under the event Ω⋆ i ({zj}j̸=i), we have z⊤θ⋆ ≥ maxj̸=i z⊤ j θ⋆ by the definition of Ω⋆ i ({zj}j̸=i). Since maxj̸=i z⊤ j θ...

  50. [58]

    Next, we aim to bound the one-side decay rate of Z ⊤ i θ⋆ = y | {maxj̸=i z⊤ j θ⋆ ≤ H} ∩Ω⋆ i ({zj})

    Bounding one-side decay rate. Next, we aim to bound the one-side decay rate of Z ⊤ i θ⋆ = y | {maxj̸=i z⊤ j θ⋆ ≤ H} ∩Ω⋆ i ({zj}). Define the (conditional) density of Z ⊤ i θ⋆ = y {max j̸=i z⊤ j θ⋆ ≤ H} ∩Ω⋆ i ({zj}) as g2(y). Its support is restricted to the region {y | b ≤ y ≤...

  51. [59]

    vuBQhbLi3xKK26k2IMHUxypayyI=

    Bounding maximum density of g2 by applying Corollary 5. From Lemma 5, the maximum density is bounded by 3 √ dL(R) in the interval [b, b+ 1 2 ]. Hence, E[1(max j̸=i z⊤ j θ⋆ ≤ Z ⊤ i θ⋆ ≤ max j̸=i z⊤ j θ⋆ + ε) | {max j̸=i z⊤ j θ⋆ ≤ H} ∩Ωi({zj})] ≤ 3 √ dL(R)ε for any ε <1 2. G Pro...

  52. [60]

    Define R1 = c0 xmax(2 + logdK)

  53. [61]

    Define D := [−R1, R1]d

  54. [62]

    Define Dv := P[D, v]

  55. [63]

    Set the truncation set Cv 1 := (Dv)K

  56. [64]

    ihXkrSXpKNbYX0TMl/lKbS2nloU=

    Then ∥Cv 1∥∞ ≤ R1 + 2 holds (by Lemma 12). 36 <latexit sha1_base64="ihXkrSXpKNbYX0TMl/lKbS2nloU=">AAAGMXicjVTLbhMxFHWBQCmvFnawsYiQWIyqTFUBUjeV2krs+hBtUmWiyuPcSax4bMv2tImm+QK28CV8TXeILT+BJzMhHadIWEp8c865vg/fOFacGdtq3azcu/+g8fDR6uO1J0+fPX+xvvHyzMhMUzilkkvdiYkBzgScWmY5dJQGksYc2vF...

  57. [65]

    Using (14), we get P[X ∈ (DK)c] ≤ KX i=1 P[Xi ∈ Dc] ≤ KX i=1 dX j=1 P[|Xij| > R1] ≤ dK × 1 2dK = 1 2

    Since Cv 1 ⊃ DK, it suffices to prove the latter. Using (14), we get P[X ∈ (DK)c] ≤ KX i=1 P[Xi ∈ Dc] ≤ KX i=1 dX j=1 P[|Xij| > R1] ≤ dK × 1 2dK = 1 2 . Define the truncated contexts W = X | {X ∈ Cv 1} := (W ⊤ 1 , . . . , W⊤ K ). Claim 5 The truncated contexts W satisfy E[v⊤Xa...

  58. [66]

    Truncated contexts refer to cases where the context distribution is truncated from the original distribution

    Truncated contexts. Truncated contexts refer to cases where the context distribution is truncated from the original distribution. Examples include truncated Gaussian and truncated exponential distributions

  59. [67]

    Naturally bounded contexts include uniform distributions on a ball or distributions with bounded density defined on the ball

    Naturally bounded contexts. Naturally bounded contexts include uniform distributions on a ball or distributions with bounded density defined on the ball. H.2 Regret Bounds for Bounded Contexts Next, we present our result for the regret bound. The first case is when we receive ...

  60. [68]

    When X1 = · · ·= XK (strongly correlated), Condition 1 holds with p⋆ = 1 2 , 1 − c⋆ ≳ 1

  61. [69]

    PeMgCxkv/6YLANh8LNF6+EPP03k=

    When X1, . . . , XK are independent (not correlated), we have p⋆ = 1 2 , 1 − c⋆ ≥ c K− 2 d+1 . Proof We use the result of Claim 10 below. Correlated Case. If X1 = X2 = · · ·= XK, then the 1 2-quantile c⋆ of X ⊤ i η satisfies 2(1 − c⋆) ≥ 1 2cu ωd ωd−1 2 d+1 . Since ωd ωd−1 2 d+...

  62. [70]

    Guidelines: • The answer NA means that the abstract and introduction do not include the claims made in the paper

    Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: Yes, we think our abstract and introduction well reflect the whole paper’s contributions. Guidelines: • The answer NA ...

  63. [71]

    Limitations

    Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We wrote it in Appendix L. Guidelines: • The answer NA means that the paper has no limitation while the answer No means that the paper has limitation...

  64. [72]

    Guidelines: • The answer NA means that the paper does not include theoretical results

    Theory Assumptions and Proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] 63 Justification: Yes, we state whole assumptions and provide rigorous proofs. Guidelines: • The answer NA ...

  65. [73]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experimental Result Reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and da...

  66. [74]

    Guidelines: • The answer NA means that paper does not include experiments requiring code

    Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material? 64 Answer: [Yes] Justification: We provide code in suppl...

  67. [75]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: Yes, we provide whole details...

  68. [76]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Yes, we provide whole details in Appendix M. Guide...

  69. [77]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experiments Compute Resources Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Yes, we provide whole d...

  70. [78]

    Guidelines: • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics

    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? Answer: [Yes] Justification: Yes, we checked. Guidelines: • The answer NA means that the authors have not re...

  71. [79]

    Guidelines: • The answer NA means that there is no societal impact of the work performed

    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 L. Guidelines: • The answer NA means that there is no s...

  72. [80]

    Guidelines: • The answer NA means that the paper poses no such risks

    Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Not relevant. G...

  73. [81]

    Guidelines: • The answer NA means that the paper does not use existing assets

    Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Not relevant. Gui...

  74. [82]

    Guidelines: • The answer NA means that the paper does not release new assets

    New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 67 Answer: [NA] Justification: Not relevant. Guidelines: • The answer NA means that the paper does not release new assets. • Researchers should c...

  75. [83]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Crowdsourcing and Research with Human Subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? A...

  76. [84]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.