Manifold-Aware Information Gain and Lower Bounds for Gaussian-Process Bandits on Riemannian Quotient Spaces

Abstract

We prove a regret lower bound for Gaussian-process bandits on a smooth compact Riemannian manifold $\M$ of dimension $d$ with intrinsic Matérn-$\nu$ kernel ($\nu >d/2$) that exposes how the geometry of the arm space enters the constant. For any algorithm and time horizon $T$ exceeding an explicit threshold, the worst-case expected regret over the RKHS-ball $\|f\|_{\Hil_{k_ν}}\!\le\!B$ satisfies \begin{multline*} \E[R_T(f)]\;\ge\;c_*(d,ν)\,B^{d/(2ν+d)}\,σ_n^{2ν/(2ν+d)} \\ \cdot\,\vol_g(\M)^{ν/(2ν+d)}\,T^{(ν+d)/(2ν+d)}(\log T)^{ν/(2ν+d)}. \end{multline*} The exponent matches the Vakili--Khezeli--Picheny upper bound \cite{vakili2021information}; the $\vol_g(\M)^{ν/(2ν+d)}$ factor is, to our knowledge, the first explicit volume-dependent geometric constant in a manifold GP-bandit lower bound. We extend the analysis in five directions: (i)~a companion Assouad-style proof gives a different lower bound with a strictly smaller $T$-exponent $(2\nu +3d)/(4(\nu +d))$ but with a polylog factor of the form $1/(\log \log T{)}^{(2\nu +d)/(4(\nu +d))}$, sharpening the $(\log T{)}^{\nu /(2\nu +d)}$ Fano polylog of Theorem~\ref{thm:main}; (ii)~we prove a $|G{|}^{1/2}$ upper bound on the regret of an extrinsic-kernel GP-UCB algorithm on a quotient space $\M=\Mt/G$, plus a bracketing theorem (Theorem~\ref{thm:gauge-bracket}); the precise constant is conjectured to take the modulated form $(1+(|G|-1)h(\rinj/κ))^{1/2}$ (Conjecture~\ref{conj:gauge-modulated}), validated numerically on $\SO(3)$; (iii)~we write the leading constant $c_{\ast }(d,\nu )$ out fully; (iv)~we extract a curvature dependence $1+O(K\eps_T^2)$ via Bishop--Gromov; (v)~we transfer the bound to the Bayesian regret framework via the Yang--Barron / Castillo et al.\ Bayesian-Fano transfer.

arXiv commentIt will be submitted to IEEE Transactions on Information Theory