PaperlayerView exact revision on arXiv

Source-linked AI summary

A General $\widetilde{\Omega}(\sqrt{T \gamma_T})$ Lower Bound for Kernel Bandits

Chenkai Ma, Jonathan Scarlett

arXiv:2610.11082v1stat.MLcs.ITcs.LGmath.IT

TL;DR

General-kernel minimax lower bounds were missing, leaving the scope of near-optimality for existing kernel-bandit upper bounds unclear. The paper derives a lower bound using effective dimension and finite approximation, then relates it to maximum information gain. The bound is logarithmically tight in general, with the logarithmic loss removable under a stated growth condition.

  • Problem

    Prior nearly matching minimax-regret lower bounds covered specific kernels, leaving open whether √(Tγ_T) characterizes regret for general kernels.

    Source: §1 · p. 1

  • Method

    The paper proves a lower bound through effective dimension on finite domains and extends it to compact domains using finite approximation.

    Source: §1 · pp. 1–2

  • Results

    The paper establishes an Ω(√(Tγ_T/log T)) lower bound for non-constant continuous positive-semidefinite kernels on compact domains, and the logarithmic factor is unavoidable in general.

    Source: §1 · p. 2

  • Takeaways & Limitations

    On [0, 1]^d, γ_T = Θ(T^α) for some α > 0 is a sufficient condition for an Ω(√(Tγ_T)) lower bound, and holds for the Matérn kernel among others.

    Source: §1 · p. 2

    For the squared exponential, rational-quadratic, and Dirichlet kernels, the paper's condition for removing the logarithmic factor fails, though this does not rule out such a bound by a different argument.

    Source: §4.1 · p. 10

Abstract

from arXiv · show

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain $\gamma_T$. In particular, the best existing upper bounds scale as $\sqrt{T\gamma_T}$ up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Mat\'ern. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general $\Omega(\sqrt{T\gamma_T/\log T})$ minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly $\Theta(\sqrt{T\gamma_T})$ (i.e., within constant factors) for the Mat\'ern-$\nu$ kernel with $\nu \in (0,2)$, $\gamma$-exponential kernel with $\gamma \in (0,2)$, and certain piecewise-polynomial kernels.

1 Introduction

Kernel-bandit regret is commonly analyzed through maximum information gain, but general-kernel minimax lower bounds have been missing. This paper uses effective dimension to establish general lower bounds and identifies when they match upper bounds or retain a logarithmic gap.

1.1 Setup

  • The setup is sequential optimization of an unknown bounded-RKHS-norm function with noisy observations, minimizing cumulative regret against the best action.The effective dimension is connected to regularized experimental design and counts feature directions above a threshold.Source: §1 · p. 1, §1.1 · pp. 2–3

1 Introduction

  • The motivating gap is that prior nearly matching lower bounds covered specific kernels, leaving unclear whether √(Tγ_T) characterizes minimax regret for general kernels.Existing general-kernel upper bounds scale as √(Tγ_T) up to logarithmic factors.Source: §1 · p. 1
  • The paper establishes an Ω(√(Tγ_T/log T)) minimax-regret lower bound for non-constant continuous positive-semidefinite kernels on compact domains.It first proves a lower bound using the effective dimension of a regularized D-optimal design, then extends the result to compact domains by finite approximation.Source: §1 · pp. 1–2
  • The logarithmic factor is unavoidable in general, while on [0, 1]^d a sufficient condition for an Ω(√(Tγ_T)) lower bound is γ_T = Θ(T^α) for some α > 0.The stated sufficient condition holds for the Matérn kernel, among others.Source: §1 · p. 2
  • Matching upper and lower bounds yield Θ(√(Tγ_T)) regret for the Matérn-ν kernel with ν ∈ (0, 2), γ-exponential kernels with γ ∈ (0, 2), and specified piecewise-polynomial kernels.For other kernels or general settings considered, a √log T or log T gap remains.Source: §1 · p. 2

1.2 Related Work

  • Related work supplies kernel-specific lower bounds and upper-bound analyses; sharp lower bounds were still absent for kernels including rational quadratic and one-dimensional Dirichlet.The paper uses effective dimension directly rather than identifying the RKHS with Hölder or Besov function spaces.Source: §1.2 · p. 4

2 The Finite Domain Setting

For finite domains, the paper states lower-bound results in terms of a regularized D-optimal design's effective dimension and develops hard-to-distinguish functions to prove them. A change-of-measure argument transfers regret under a zero-function model to the hard-function model.

2.1 Statement of Results

  • The finite-domain results are stated as a theorem and corollary under the setup's feature-separation quantity Δ_k.The supplied theorem statements identify the setup and Δ_k but do not expose the bound expressions.Source: §2.1 · p. 4

2.2 Proofs

  • The proof constructs hard functions from normalized feature vectors associated with the regularized D-optimal design, with each function maximized at its corresponding support point.For effective dimension d_T ≥ 4, the construction uses functions whose maximum value is of order σ√(d_T/T).Source: §2.2 · p. 5
  • A zero-function model makes the learner's actions independent of the randomly chosen hard function; bounded regret and KL divergence then support a change-of-measure transfer to the hard-function model.When d_T < 4, a separate construction uses two opposite functions based on maximally separated feature vectors.Source: §2.2 · pp. 5, 7

3 Extension to General Compact Domains

The paper extends its finite-domain argument to compact domains through a finite approximation that preserves maximum information gain. It then states compact-domain lower bounds and a high-probability version.

3 Extension to General Compact Domains

  • A finite approximation of a compact domain is used to extend the finite-domain lower-bound argument.The approximation is chosen so that its maximum information gain equals that of the original domain.Source: §3 · p. 7, §3.1 · p. 7

3.2 Main Results

  • The compact-domain theorem is stated for a finite approximation, and its dependence on that approximation is removed by converting effective dimension to maximum information gain.The resulting scaling is stated to match Corollary 1.Source: §3.2 · pp. 7–8
  • For every policy, there exists a function in the RKHS ball whose regret satisfies the Corollary 2 lower bound with probability at least 1/4.The paper places this high-probability statement in Appendix D.1.Source: §3.2 · p. 8

4 Refinements and Comparisons

The section compares information-gain-based regret bounds across kernel families, showing that the bounds match for some kernels while logarithmic gaps remain for others. It also identifies when the logarithmic factor can be removed and compares general and kernel-specific upper-bound refinements.

4 Refinements and Comparisons

  • The bounds match for Matérn kernels with ν ∈ (0, 2), γ-exponential kernels with γ ∈ (0, 2), and piecewise-polynomial kernels with q = 0, d ≥ 3 or q = 1; other listed kernels retain at most a √log T gap.Table 1 compares maximum-information-gain rates with minimax-regret upper and lower bounds.Source: §4 · p. 8, Table 1 · p. 9

4.1 When can the Log Factor be Removed?

  • On small finite domains, γ_T = Θ(log T), so an Ω(√(Tγ_T)) minimax lower bound is impossible in general and the logarithmic factor is unavoidable.The argument combines the finite-domain information-gain rate with a minimax-regret bound.Source: §4.1 · p. 9
  • When γ_T = Θ(T^α) for some α > 0 on [0, 1]^d, the stated sufficient condition yields matching Ω(√(Tγ_T)) regret lower bounds for the Matérn, γ-exponential, and piecewise-polynomial cases identified in Table 1.The paper verifies that these polynomial-growth information-gain rates satisfy Proposition 2's condition.Source: §4.1 · pp. 9–10

4.2 Comparison with Upper Bounds

  • Under a suitable Hölder condition on [0, 1]^d, the finite-domain upper bound extends to O(√(Tγ_T log T)) regret, and all six listed kernels satisfy the theorem's condition.For finite domains, the bound is within a log T factor of the general lower bound when |X| ≤ poly(T).Source: §4.2 · pp. 10–11
  • A sharper analysis of h(V, ρ) removes the log T factor for the squared exponential, rational-quadratic, and one-dimensional Dirichlet kernels.The corresponding bounds on max_V h(V, ρ) are O((log T/log log T)^d), O((log T)^d), and 2n + 1, respectively.Source: §4.2 · p. 11
  • For the Matérn, γ-exponential, and piecewise-polynomial settings named in Lemma 6, MOSS with careful discretization removes the log T factor and matches the lower bound at Θ(√(Tγ_T)).A √log T gap remains for the other kernel settings considered.Source: §4.2 · p. 11

5 Conclusion

The paper establishes a general minimax regret lower bound in terms of maximum information gain, with a logarithmic factor that is unavoidable in general but removable under a growth condition. Comparisons with upper bounds yield exact Θ(√(Tγ_T)) scaling for several kernel families; the appendix also discloses AI involvement and specifies the scope of the kernel definitions.

5 Conclusion

  • The paper proves an Ω(√(Tγ_T/log T)) lower bound for non-constant continuous positive-semidefinite kernels on compact subsets of R^d.The conclusion describes the resulting minimax scaling as √(Tγ_T) up to logarithmic factors in very high generality.Source: §5 · pp. 11–12
  • The logarithmic term cannot be removed in general, but can be removed on [0, 1]^d when γ_T = Θ(T^α) for some α > 0.Comparisons with suitable upper bounds establish exact Θ(√(Tγ_T)) minimax scaling for several kernels, while small gaps remain for others.Source: §5 · p. 12

AI Use Disclosure

  • The authors report using AI for theoretical development, proof outlining and proofreading, literature search, and technical kernel-rate work, with proofs checked line by line by the authors.They state that they take responsibility for the results and their correctness.Source: AI Use Disclosure · p. 12

A Definitions of Kernels

  • The kernel appendix considers six stationary kernels, with parameter restrictions including ν > 0 for Matérn and q ≥ 1 when d = 1, 2 for piecewise-polynomial kernels.It restricts the Dirichlet kernel to one dimension because it may fail to be positive semidefinite in higher dimensions, and excludes n = 0 because that gives a constant kernel.Source: A Definitions of Kernels · p. 14

B Technical Lemmas

The technical lemmas establish operator and feature-map facts used in the finite-domain analysis, connect Gram matrices and design operators, and verify continuity properties on compact domains. Together these results supply supporting steps for the paper's regret arguments.

B Technical Lemmas

  • For every distribution ν on a finite X, regularization makes M_ν + ρI_E positive definite, so its inverse is positive definite and satisfies the stated inverse-square operator inequality.The inequality is (M_ν + ρI_E)^−2 ⪯ ρ^−1(M_ν + ρI_E)^−1.Source: B Technical Lemmas · p. 15
  • The Gram matrix from T queried points and T times the empirical-design operator have the same positive eigenvalues, including multiplicities.This links the spectrum of the observations' Gram matrix to the design operator used in the analysis.Source: B Technical Lemmas · p. 16
  • The technical results also establish positivity of the effective dimension on finite domains and uniqueness of the regularized D-optimal design operator.The uniqueness claim is that any two such designs have the same M_ν operator.Source: B Technical Lemmas · p. 17
  • On a compact domain with a continuous kernel, the feature map and every bounded-RKHS-norm function are continuous.The proof bounds function differences by the RKHS norm bound times the distance between feature vectors.Source: B Technical Lemmas · p. 18

C Proofs of Theorem 1 and Corollary 1 (Finite Domains)

The finite-domain proof constructs hard functions and compares interaction histories under hard-function and zero-function models. It uses the effective dimension to organize the lower-bound argument, with a separate construction for the small-dimension case.

C Proofs of Theorem 1 and Corollary 1 (Finite Domains)

  • For the main construction, the proof compares the hard-function model with a zero-function model in which actions are independent of the randomly chosen hard function, then transfers a regret bound by change of measure.The proof bounds the KL divergence between the models and uses a change-of-measure argument.Source: C Proofs of Theorem 1 and Corollary 1… · p. 20
  • The effective dimension is related to maximum information gain through a bound whose regularization parameter is ρ = σ²/(B²T).The proof uses the relation between the empirical design operator and the Gram matrix of the queried points.Source: C Proofs of Theorem 1 and Corollary 1… · p. 21
  • When d_T ≥ 4, the proof uses the effective-dimension lower bound; when d_T < 4, it uses a separate two-function construction based on maximally separated feature vectors.Combining the cases proves Theorem 1.Source: C Proofs of Theorem 1 and Corollary 1… · pp. 20, 22

D Proofs of Theorem 2 and Corollary 2 (General Compact Domains)

For compact domains, the proof transfers the regret lower bound through an effective dimension, handling large and small dimensions separately. A finite subset can preserve the maximum information gain used in the argument.

D Proofs of Theorem 2 and Corollary 2 (General Compact Domains)

  • The compact-domain reduction chooses a finite X̃ that retains γT(X), allowing the finite-set argument to apply without changing the maximum information gain.It uses compactness to obtain a finite cover, then includes a maximizing tuple for γT(X).Source: D Proofs of Theorem 2 and Corollary 2… · p. 22
  • When dT(X̃) ≥ 4, the proof bounds regret using hard functions indexed by a random design and compares that model with interaction on the zero function.The policy’s actions are independent of the randomly chosen hard function in the zero-function model.Source: D Proofs of Theorem 2 and Corollary 2… · pp. 23–24
  • For dT ≥ 4, Lemma 27 applies directly; for dT < 4, under Section 3.1’s setup, a maximizing feature-vector pair is justified by Lemma 21, establishing Lemma 24 for compact X.Source: D Proofs of Theorem 2 and Corollary 2… · p. 25
  • Lemma 28 relates dT(X̃) to γT(X), completing the transfer from the effective-dimension bound to the information-gain bound.The displayed relation bounds dT using γT(X̃) and ρ, and Proposition 1 gives γT(X̃) = γT(X).Source: D Proofs of Theorem 2 and Corollary 2… · pp. 22, 24

D.1 High-Probability Lower Bound

The appendix gives a high-probability regret lower bound and develops supporting results on information gain, effective dimension, and upper bounds. It also derives sharp information-gain rates for the rational quadratic kernel.

D.1 High-Probability Lower Bound

  • With probability at least 1/4, every policy incurs the Corollary 2 lower-bound scale for some fixed f in Fk(B).The proof combines the dT ≥ 4 and 0 < dT < 4 cases.Source: §D.1 · pp. 25, 27

E.1 Deriving Sharp Rates for γT

  • For the rational quadratic kernel, γT = O((log T)^(d+1)) and γT = Ω((log T)^(d+1)).The proof obtains these rates by applying upper- and lower-bound results to its spectral density.Source: §E.1 · pp. 27, 29

E.2 Proof of Lemma 2 (Lower Bound Based on Information Difference)

  • The information-difference proof deletes points from a maximizing tuple and uses the resulting design to lower-bound dT(X̃) through γT − γm.The argument bounds the information difference by a sum involving dT(X̃), then combines that bound with the lower-bound result.Source: §E.2 · pp. 29–30

E.3 Proof of Proposition 2 (Sufficient Condition for Log Factor Removal)

  • When condition (37) holds, the proof combines it with Lemma 2 to establish the sufficient condition for removing the logarithmic factor.It takes T sufficiently large with T ≥ 2L and bounds the relevant sum by log(2L).Source: §E.3 · p. 31

E.4 Proof of Lemma 4 (Upper Bound on h(V, ρ)

  • The upper bound on h(V, ρ) is derived by greedily selecting points that maximize a regularized leverage quantity over V.The proof uses the empirical design from the selected points and telescopes the resulting bounds.Source: §E.4 · p. 31

E.5 Proof of Theorem 3 (General Upper Bound)

  • The general upper-bound proof rounds the compact domain to a finite grid, controls the approximation error, and applies RIPS to the grid.The constructed grid has approximation error at most B/T.Source: §E.5 · pp. 31–32

E.6 Proof that All Six Kernels Satisfy the H¨older Condition

The kernel-specific proofs establish Hölder-type control by reducing feature-map distances to bounds on k(0) − k(r). The resulting exponent choices vary across the kernels.

E.6 Proof that All Six Kernels Satisfy the H¨older Condition

  • The feature-map distance satisfies ||ϕ(x) − ϕ(y)||² = 2(k(0) − k(r)), reducing the condition to bounding the kernel difference by a power of r.For the γ-exponential kernel, the proof chooses α = γ/2.Source: §E.6 · p. 32
  • For the Matérn kernel, the integral representation and the bound 1 − exp(−u) ≤ u^α for 0 < α ≤ 1 support the required power bound.The proof permits 0 < α ≤ 1 with α < ν.Source: §E.6 · pp. 32–33
  • For the one-dimensional Dirichlet kernel, pairing terms with indices j and −j yields the bound needed to choose α = 1.The proof uses 1 − cos u ≤ u²/2 and the sum of squares through n.Source: §E.6 · p. 33

E.7 Proof of Lemma 5 (Sharper Upper Bounds; First Result)

The proof bounds h(V, ρ) using weighted Gram matrices and kernel approximations. It gives specific bounds for the rational quadratic and one-dimensional Dirichlet kernels.

E.7 Proof of Lemma 5 (Sharper Upper Bounds; First Result)

  • A kernel approximation with a low-rank component and controlled residual trace bounds h(V, ρ) through the rank and residual size.The proof applies this decomposition to the weighted Gram matrix and bounds its regularized trace.Source: §E.7 · pp. 33–34
  • For the rational quadratic kernel, maxV h(V, ρ) = O((log T)^d).The proof uses its analytic extension and an exponentially accurate approximation.Source: §E.7 · p. 34
  • For the one-dimensional Dirichlet kernel, maxV h(V, ρ) ≤ 2n + 1.Its kernel has rank at most 2n + 1.Source: §E.7 · p. 35

E.8 Proof of Lemma 6 (Sharper Upper Bounds; Second Result)

The proof bounds grid-interpolation error under polynomial spectral decay and applies MOSS; for the listed kernel families, the resulting regret rates match the scaling of √(Tγ_T) under stated parameter ranges.

E.8 Proof of Lemma 6 (Sharper Upper Bounds; Second Result)

  • For a kernel satisfying eq. (237), applying MOSS on ˜X gives the cited guarantee O(T^((s+d)/(2s+d))).Source: §E.8 · p. 37
  • For the Matérn kernel, ν∈(0,2) gives the corresponding regret rate, matching the scaling implied by γ_T=Θ(T^(d/(2ν+d))) (Janz et al., 2026, Corollary 7).The proof sets s=ν in the spectral-decay condition.Source: §E.8 · p. 37
  • For the γ-exponential kernel, γ∈(0,2) yields the corresponding regret rate, matching the scaling implied by γ_T=Θ(T^(d/(γ+d))) (Lee and Javidi, 2025, Proposition 1).Here the spectral-decay parameter is s=γ/2.Source: §E.8 · p. 37
  • For piecewise-polynomial kernels, s=q+1/2<2 restricts q to 0 or 1; Appendix A further requires q=0 with d≥3 or q=1 (Lee and Javidi, 2025, Proposition 1).The supplied rate passage gives γ_T=Θ(T^(d/(2q+1+d))) for these cases.Source: §E.8 · p. 37

F Upper Bound on the Maximum Information Gain

The section derives an upper bound on maximum information gain from an upper bound on minimax regret. Applied to the γ-exponential kernel, this recovers its stated information-gain rate, while a direct conversion can incur an extra log T factor.

F Upper Bound on the Maximum Information Gain

  • If minimax regret is bounded by U_t for every t≤T on a compact domain, Corollary 4 gives an upper bound on γ_T.The proof applies the regret bound across horizons and sums the resulting inequalities.Source: F Upper Bound on the Maximum… · p. 38
  • For the γ-exponential kernel, the section obtains γ_T=O(T^(d/(γ+d))), matching its Θ(T^(d/(γ+d))) rate.The example uses a minimax-regret upper bound of order T^((γ+2d)/(2γ+2d)).Source: F Upper Bound on the Maximum… · p. 38
  • The immediate conversion γ_T=O(U_T^2 log(T)/T) yields an extra log T factor over the matching rate.The alternative approach may help when information-gain upper bounds are unavailable or difficult to derive, provided minimax-regret upper bounds are available.Source: F Upper Bound on the Maximum… · p. 38
Loading 2610.11082v1…