Proof insight. Our regret bound, at its core, relies on a set of concentration inequalities, and analyzing the regret in a global high probability good event for which the empirical means are close to the true means. Combined with 1, we show in 5 that the maximizing set \(\mathcal{X}^\star\) always remains in the active sets \(\mathcal{A}^t\). We then leverage our hypothesis on the oracle 2 as well as standard techniques to bound how many times a point \(a \in S_k\) can be queried during phase \(k\), depending on its sub-optimality \(\Delta(a)\) to obtain the regret bounds above. The full proof of [lemma:first32regret32bounds] and the detailed steps to obtain the bounds are in 6. ◻

Proof insight. The key element in this proof comes from the link between packing numbers and our integral of the gap-function. As in [31], [32], by using 3, we can provide such a bound by using a peeling argument over the level sets of \(f\) and upper bounding volume integrals with packing numbers at scale \(r\) times the volume of the corresponding \(\ell_\infty\) balls of radius \(r\). This bound is formally provided in 9 in the appendix. The full proof is provided in 6.1. ◻

Proof sketch. This sketch provides the main insight into how the exponents in the regret appear from the computations. For a complete exposition of the proof steps, see 6.4.

For a worst-case instance with zooming dimension \(d_z\) and maximizer dimension \(d^\star\), the covering numbers satisfy \(\mathcal{M} \left ( \mathcal{X}_r\setminus \mathcal{X}_{r/2} , r \right ) = \Omega(r^{-d_z})\) and \(\mathcal{M} \left ( \mathcal{X}^\star, r \right ) = \Omega(r^{- d^\star})\).

The sampling-budget relation from Lemma [lemma:first32regret32bounds] bounds the last completed phase \(k_T\) by yielding \(T \geq \Omega(2^{k_T(d^\star+2)})\). Concurrently, the standard zooming analysis of the sampling budget implies \(T \ge \Omega(2^{k_T(d_z+2)})\), as the number of pulls in phase \(k_T\) scales as \(2^{2k_T}\mathcal{M}(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}_{2^{-(k_T-1)}}, 2^{-k_T}) \ge \Omega(2^{k_T(d_z+2)})\). Combining these gives \(2^{k_T (\max(d_z, d^\star) + 2)} \le \tilde{\mathcal{O}}(T)\), which implies \(2^{k_T} \le \tilde{\mathcal{O}}\!\left(T^{\frac{1}{\max(d_z, d^\star) + 2}}\right)\).

We then decompose the truncated integral upper bound of [theorem:instance32dependant32integral32regret32bounds] into a sum over the dyadic gap scales \(\mathcal{X}_{2^{-k}}\setminus \mathcal{X}_{2^{-(k+1)}}\) for \(k \le k_T\). Bounding the volume of each annulus using its corresponding covering number gives: \[\begin{align} R_T &\le C \log(T) \left( \sum_{k=0}^{k_T} \frac{\mathcal{M} \left ( \mathcal{X}_{2^{-k}}\setminus \mathcal{X}_{2^{-(k+1)}}, 2^{-k} \right )}{2^{-k}} + \frac{\mathcal{M} \left ( \mathcal{X}_{2^{-(k_T+1)}} \setminus \mathcal{X}^\star, 2^{-(k_T+1)} \right )}{2^{-k_T}} \right) \\ &\le \tilde{\mathcal{O}} \left( \sum_{k=0}^{k_T} 2^{k(d_z+1)} + 2^{k_T(d_z+1)} \right) = \tilde{\mathcal{O}}\!\left(2^{k_T(d_z+1)}\right). \end{align}\] Plugging in the bound on \(2^{k_T}\) yields \(R_T \le \tilde{\mathcal{O}}\!\left(T^{\frac{d_z+1}{\max(d_z, d^\star)+2}}\right)\). ◻

Proof insight. Here, we detail the main insights from the proof. The main idea is to characterize the covering number of \(\mathcal{X}_r\) at scale \(r\).

To that end, we first focus on \(\mathcal{X} \setminus \mathcal{X}^\star \supset \cup_{k\geq 1} \mathcal{X}_{r/2^{k-1}} \setminus \mathcal{X}_{r/2^k}\). The doubling properties of covering numbers in \(\mathbb{R}^d\) ensure that \(\mathcal{M} \left (\mathcal{X}_r \setminus \mathcal{X}^\star , r \right ) \leq \mathcal{O} \left( r^{-d_z} \right)\). It is now sufficient to consider any point \(y \in \mathcal{X}^\star\). We can use our assumptions that \(\mathcal{X}^\star\) is connected and \(\exists r \geq 0, \mathcal{B}(\mathcal{X}^\star,r) \subset \mathcal{X}\) to show that the affine hull of \(\mathcal{X}_r\setminus \mathcal{X}^\star\) contains \(\mathcal{X}^\star\).

Then, starting from an optimal covering of \(\mathcal{X}_r \setminus \mathcal{X}^\star\) at scale \(r\), we construct a valid covering of this affine hull by adding points along the segments between each covering point and \(y\) (adding at most \(\mathcal{O}(1/r)\) points per segment). Since this yields a covering of \(\mathcal{X}^\star\) at scale \(r\), its size is bounded below by \(\mathcal{M}(\mathcal{X}^\star, r)\). Therefore, we obtain \(\mathcal{M}(\mathcal{X}^\star, r) \le \mathcal{O}(1/r) \cdot \mathcal{M}(\mathcal{X}_r \setminus \mathcal{X}^\star, r)\), which implies \(\mathcal{O}(r^{-d^\star}) \le \mathcal{O}(r^{-(d_z+1)})\) and directly yields the bound \(d_z+1 \geq d^\star\).

The full proof of 2 is deferred to 6.4. ◻

Proof sketch. The proof of [thm:full-info-instance] leverages the same ideas as those of [theorem:instance32dependant32integral32regret32bounds]. Yet, it is more straightforward: in the full-information case, there is no need to use pointwise estimates of \(f\), which allows us to directly sample from \(\mathcal{A}_t\), making the link with integral-type bounds straightforward. The full proof is detailed in 8.2. ◻

Proof sketch. The bound is obtained by evaluating both terms of [thm:full-info-instance] over the instance geometry. As in 1, by using the definition of \(d_z\) and \(d^\star\) we can lower bound \(\text{vol}(\mathcal{X}_{r})\) by \(c' r^{d-\max \left ( d_z,d^\star\right )}\). We can then directly bound the second term of the regret bound by \(\tilde{\mathcal{O}} \left ( T^{\frac{1+ d_z-\max\left ( d_z,d^\star \right )}{2}}\right )\). For the first term, cutting the integral in dyadic annuli \(\mathcal{X}_{2^{-j}} \setminus \mathcal{X}_{2^{-(j+1)}}\), and then bounding the volume of each annulus by its covering number via the zooming dimension allows us to get \(\tilde{\mathcal{O}} \left ( T^{\frac{1+ d_z-\max\left ( d_z,d^\star \right )}{2}}\right )\). ◻

Proof. For each fixed \(\ell\ge 1\), conditional sub-Gaussianity and Hoeffding’s inequality yield \[\ifthenelse{ \equal{}{} } {\mathbb{P} } {\mathbb{P} \left ( \right )} \!\Big(\big|\widehat\mu_{k,\ell}(a)-f(a)\big|>\sqrt{\tfrac{2}{\ell}\log(1/\delta_\ell)}\Big)\;\le\;\delta_\ell.\] Choose \(\delta_\ell:=\frac{6\delta}{\pi^2\ell^2}\) so that \(\sum_{\ell\ge 1}\delta_\ell=\delta\). With this choice, the deviation threshold equals \(u(\ell,\delta)\). A union bound over \(\ell\ge 1\) gives the claim. ◻

Proof. Applying Lemma 3 to each \(a\in S_k\) with confidence level \(\delta_k/n_k\), and then doing a union bound provides the desired result. ◻

Proof. Fix \(\ell\ge 1\) and suppose \(a\in A_\ell\). Let \(m_\ell\in\arg\max_{j\in A_\ell}\widehat\mu_{k,\ell}(j)\). On \(\mathcal{E}\) we have \(\widehat\mu_{k,\ell}(a)\ge f(a)-u_{k,\ell}\ge f^\star-r_k-u_{k,\ell}\). Also for any \(j\in A_\ell\), \(\widehat\mu_{k,\ell}(j)\le f(j)+u_{k,\ell}\le f^\star+u_{k,\ell}\), so \(\max_{j\in A_\ell}\widehat\mu_{k,\ell}(j)-u_{k,\ell}\le f^\star\). Therefore \[\widehat\mu_{k,\ell}(a)+u_{k,\ell} \;\ge\;f^\star-r_k \;\ge\;\max_{j\in A_\ell}\widehat\mu_{k,\ell}(j)-u_{k,\ell}-r_k,\] so \(a\) satisfies the retention condition and belongs to \(A_{\ell+1}\). By induction over \(\ell\), \(a\) is never eliminated and thus is in \(\widehat S_k\). ◻

Proof. We prove the above statement by induction on \(k\). For \(k=1\), the statement is trivially true as \(\mathcal{A}_1=\mathcal{X}\).

Let \(1 \leq k < k_T\), and assume \(\mathcal{X}^\star\subseteq \mathcal{A}_k\).

Let \(x^\star\in\mathcal{X}^\star\). By the oracle covering property (Assumption 2), there exists \(a\in S_k\subseteq\mathcal{A}_k\) such that \(\|a-x^\star\|_\infty\le \frac{r_k}{L}\).

The Lipschitzness of \(f\) (Assumption 1) then yields, \[f(a)\;\ge\;f(x^\star)-L \|a-x^\star\|_\infty\;\ge\;f^\star-r_k,\] By definition of \(\Delta\), we obtain \(\Delta(a)\le r_k.\)

Lemma 5 then implies that \(a\) survives, i.e. \(a\in\widehat S_k\). Therefore, since \(x^\star\in B_\infty(a,r_k/L)\subseteq \mathcal{A}_{k+1}\), we have \(x^\star \in \mathcal{A}_{k+1}\).

Since \(x^\star\) was arbitrary, \(\mathcal{X}^\star\subseteq \mathcal{A}_{k+1}\) which concludes the proof. ◻

Proof. By Lemma 6, \(\mathcal{X}^\star\subseteq \mathcal{A}_k\). Hence there exists \((x^\star,z) \in \mathcal{X}^\star\times S_k\) such that \(\|x^\star-z\|_\infty \leq \frac{r_k}{L}\), which by Lipschitzness of \(f\) implies \(\Delta(z) \leq r_k\).

Let \(x^{\mathrm{best}}\in\arg\max_{z\in S_k} f(z)\). By the above statement, we have \(\Delta(x^{\mathrm{best}})\le r_k\).

For any \(x\in\mathcal{A}_{k+1}\), by definition of \(\mathcal{A}_{k+1}\) there exists \(y\in \widehat S_k\) such that \(\|x-y\|_\infty\le \frac{r_k}{L}\). By Lipschitzness of \(f\), \[\Delta(x)=f^\star-f(x)\;\le\;f^\star-f(y)+L \|x-y\|_\infty\;=\;\Delta(y)+r_k.\]

Therefore, at the final phase \(\ell_k\) we have \(u_{k,\ell_k}\le r_k/4\). Since \(y\in\widehat S_k=A_{\ell_k}\), it was not eliminated, so the conservative rule implies \[\widehat\mu_{k,\ell_k}(y)+u_{k,\ell_k} \;\ge\; \max_{j\in A_{\ell_k}}\widehat\mu_{k,\ell_k}(j)-u_{k,\ell_k}-r_k \;\ge\; \widehat\mu_{k,\ell_k}(x^{\mathrm{best}})-u_{k,\ell_k}-r_k,\] where the last step uses \(x^{\mathrm{best}}\in A_{\ell_k}\) (it is never eliminated because \(\Delta(x^{\mathrm{best}})\le r_k\), by Lemma 5).

On \(\mathcal{E}\) we have \(\widehat\mu_{k,\ell_k}(y)\le f(y)+u_{k,\ell_k}\) and \(\widehat\mu_{k,\ell_k}(x^{\mathrm{best}})\ge f(x^{\mathrm{best}})-u_{k,\ell_k}\), hence \[f(y)+2u_{k,\ell_k}\;\ge\;f(x^{\mathrm{best}})-2u_{k,\ell_k}-r_k \quad\Rightarrow\quad f(y)\;\ge\;f(x^{\mathrm{best}})-4u_{k,\ell_k}-r_k.\] Thus \[\Delta(y)=f^\star-f(y) \;\le\;(f^\star-f(x^{\mathrm{best}})) + 4u_{k,\ell_k}+r_k \;\le\;r_k + 4(r_k/4) + r_k\;=\;3r_k.\] Plugging into \(\Delta(x)\le \Delta(y)+r_k\) yields \(\Delta(x)\le 4r_k\). ◻

Proof. Fix phase \(k\). Algorithm 2 plays each point \(a \in S_k\) at most once per round; let \(\ell_k\) be the last round of phase \(k\), therefore for all \(a \in S_k\), \(N_k(a) \leq \ell_k\).

Since the phase ends at the first \(\ell_k\) such that \(u_{k,\ell_k}\le r_k/4\), we can obtain a bound on \(N_k(a)\).

Solving \(u_{k,\ell}\le r_k/4\) yields \[\ell_k \;\le\;c\,r_k^{-2}\log\!\Big(\frac{|S_k|}{\delta_k}\Big)\] for a universal \(c\) (the extra \(\log(\ell)\) term is absorbed into the constant by standard bounds).

Thus \(N_k(a)\le \ell_k\le c\,\log(|S_k|/\delta_k)/r_k^2\).

For all \(a \in S_k\) such that \(\Delta(a)\le 3 r_k\), the above inequality matches the claim up to a constant factor.

Case \(\Delta(a) > 3 r_k\)
Let \(b\in\arg\max_{z\in S_k} f(z)\). As in the proof of Lemma 7, by oracle covering \(\Delta(b)\le r_k\) and by Lemma 5, \(b\) is never eliminated, so for any \(\ell\), \(b\in A_\ell\).

Let us denote by \(\tau\) the first round at which \[\Delta(a) > 2 r_k + 4 u_{k,\tau}.\] By conditioning on \(\mathcal{E}\), we ensure that at round \(\tau\) we have \[\widehat\mu_{k,\tau}(a) \le f(a) + u_{k,\tau}\] and \[\widehat\mu_{k,\tau}(b) \ge f(b) - u_{k,\tau}.\] Since \(f(b) - f(a) = \Delta(a) - \Delta(b) \ge \Delta(a) - r_k\), our condition \(\Delta(a) > 2 r_k + 4 u_{k,\tau}\) implies: \[f(b) - f(a) > r_k + 4 u_{k,\tau}.\] Combining these, we obtain: \[\widehat\mu_{k,\tau}(a) + u_{k,\tau} \le f(a) + 2 u_{k,\tau} < f(b) - 2 u_{k,\tau} - r_k \le \widehat\mu_{k,\tau}(b) - u_{k,\tau} - r_k.\] This triggers the elimination rule of Algorithm 2, meaning \(a\) is eliminated at round \(\tau\). Thus \(N_k(a) \le \tau\).

Solving for \(\tau\) such that \(u_{k,\tau} < \frac{\Delta(a) - 2r_k}{4}\), and using \(\Delta(a) > 6 r_k\) (which yields \(\Delta(a) - 2r_k > \frac{2}{3} \Delta(a)\)), we obtain: \[\tau\;\le\;c'\,\frac{\log(|S_k|/\delta_k)}{\Delta(a)^2},\] and since here \(\max\{\Delta(a),r_k\}=\Delta(a)\), this is the desired bound. ◻

Proof. The expected cumulative regret is defined as \(R_T = \mathbb{E}[\sum_{t=1}^T (f^\star - f(x_t))]\). We decompose this expectation over the global good event \(\mathcal{E}\) and its complement \(\mathcal{E}^c\): \[\label{eq:32expectation32decomposition} R_T \;\le\; \mathbb{E}\left[\sum_{t=1}^T \Delta(x_t)\,\mathbf{1}_{\mathcal{E}}\right] + \mathbb{P}(\mathcal{E}^c) T \max_{x \in \mathcal{X}} \Delta(x).\tag{2}\] By the union bound, \(\mathbb{P}(\mathcal{E}^c) \le \delta = T^{-3}\). Under Assumption 1, the suboptimality gap is bounded by \(\max_{x \in \mathcal{X}} \Delta(x) \le L \operatorname{diam}_\infty(\mathcal{X}) \le L\) (with our normalization \(L=1\)). Therefore, the failure term is bounded by \(L/T^2 \le o(1)\), which is a negligible constant that can be absorbed into the final term.

We now bound the cumulative pseudo-regret on the good event \(\mathcal{E}\). Algorithm 1 works in multiple phases, each having its own level of approximation of \(f\). Let \(k_T\) be the active phase index containing the horizon \(T\), so that \(s_{k_T-1} < T \le s_{k_T}\). The total pseudo-regret incurred on \(\mathcal{E}\) satisfies: \[\label{eq:32sum32phase32based32regret} \sum_{t=1}^T \Delta(x_t) \;\le\; \sum_{k=1}^{k_T} R_k,\tag{3}\] where \(R_k\) is the regret incurred if phase \(k\) is run to completion (for the last, incomplete phase \(k_T\), the actual number of pulls of any arm \(a\) is bounded by \(N_{k_T}(a)\), so this bound holds conservatively).

Fix a phase index \(k \leq k_T\), we can decompose the regret based on how many times each point in \(S_k\) is played during phase \(k\) as follows : \[\label{eq32:32regret32phase32k4432count32points} R_k\;=\;\sum_{a\in S_k} N_k(a)\Delta(a).\tag{4}\]

Combining 4 with Lemma 8 yields \[\label{eq32:32temporary32instance32delta} R_k \;\le\; c_0\log\!\Big(\frac{|S_k|}{\delta_k}\Big) \sum_{a\in S_k}\frac{\Delta(a)}{\max\{\Delta(a),r_k\}^2}.\tag{5}\]

To account more tightly for the fact that within \(S_k\), \(\Delta(a)\) can still vary a lot, we define the following subsets of \(S_k\), based on the values of \(\Delta\): \(S_k^{l} := S_k \cap (\mathcal{X}_{r_l}\setminus \mathcal{X}_{r_{l+1}})\) . We can thus rewrite 5 \[\label{eq:32temporary32instance32delta322} R_k \leq c_0 \log \left ( \frac{|S_k|}{\delta_k} \right ) \sum_{k' \geq \max \left (1,k-3 \right )} \sum_{a\in S_k^{k'}} \frac{\Delta(a)}{\max\{\Delta(a),r_k\}^2}\tag{6}\] Note that it is sufficient to take the sum starting at \(\max \left (1,k-3 \right )\) by 7.

We can now upper-bound the values of \(\frac{\Delta(a)}{\max\{\Delta(a),r_k\}^2}\) and get: \[\begin{align} \label{eq:temporary32instance32delta323} R_k &\leq 4c_0 \log \left ( \frac{|S_k|}{\delta_k} \right ) \left [ \sum_{k'=\max(1,k-3)}^k \frac{\left |S_k^{k'}\right |}{r_{k}} + \sum_{k'=k+1}^{k_T} \frac{r_{k'} \left |S_k^{k'}\right |}{r_{k}^2} + \frac{r_{k_T+1} |S_k \cap \mathcal{X}_{r_{k_T+1}}|}{r_{k}^2} \right] \end{align}\tag{7}\]

In order to bound \(\left |S_k^{k'}\right |\), we use Assumption 2 on our oracle. Indeed, remember that as an output of our oracle, \(S_k\) is \((c_{\mathrm{sep}}r_k)\)-separated. Hence for any \(\mathcal{Y}\subseteq\mathcal{X}\), \[|S_k\cap\mathcal{Y}| \;\le\; \mathcal{N}(\mathcal{Y},c_{\mathrm{sep}}r_k) \;\le\; C_{\mathrm{double}} \mathcal{N}(\mathcal{Y},r_k),\] where the last inequality follows from the doubling property of \(\mathbb{R}^d\) (since \(c_{\mathrm{sep}}r_k\le r_k\)). Applying this to \(S_k^{k'}\) gives \(\left |S_k^{k'}\right |\le \mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_k)\).

We combine the same bounding techniques with the definition of \(\mathcal{X}_{r_{k'}}\) and the fact that \(r_k=2^{-k}\) on the second and third terms of the inequality to get: \[\label{eq32:32complicated32but32necessary} \begin{align} R_k \leq 4c_0 \log \left ( \frac{|S_k|}{\delta_k} \right ) \Bigg[ &\sum_{k'=\max(1,k-3)}^k \frac{\mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_k)}{r_{k}} + \sum_{k'=k+1}^{k_T} \frac{\mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_k)}{2^{k'-k} r_{k}} \\ &\qquad + 4\, \mathcal{N}\left( \mathcal{X}_{r_{k_T+1}}, r_k \right ) \frac{r_{k_T+1}}{r_{k}^2} \Bigg] \end{align}\tag{8}\]

To prepare for summing the \(R_k\), we compute the following \[\begin{align} &\sum_{k=1}^{k_T} \sum_{k'=\max(1,k-3)}^k \frac{\mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_k)}{r_{k}} +\sum_{k=1}^{k_T} \sum_{k'=k+1}^{k_T} \frac{\mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_k)}{2^{k'-k} r_{k}} \\ & \leq \sum_{k'=1}^{k_T} \sum_{k=k'}^{\min(k_T,k'+2)} \frac{\mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_k)}{r_{k}} + \sum_{k=1}^{k_T}\sum_{k'=k+1}^{k_T} \frac{\mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_k)}{2^{k'-k} r_{k}} \tag{9} \addtocounter{equation}{1}\\ & \leq(1 + 2^{d+1}C_d + 4^{d+1} C_d) \sum_{k'=1}^{k_T} \frac{\mathcal{N}(\mathcal{X}_{r_{k'}}\setminus \mathcal{X}_{r_{k'+1}},r_{k'})}{r_{k'}} \tag{10} \addtocounter{equation}{1}\end{align}\]

We used, to get from 9 to 10 , the fact that \(\mathbb{R}^d\) is a doubling space of dimension \(d\) and \(C_d\) is the doubling constant of \(\mathbb{R}^d\) (as in [34] 10.13 Doubling spaces)Using the above bound and 8 , we can now go back to 3 and sum over all phases \(k \le k_T\) to get \[\begin{align} \sum_{k=1}^{k_T} R_k &\leq \log \left ( \frac{\max_k |S_k|}{\min_k \delta_k} \right ) \Bigg[ c_1\sum_{k=1}^{k_T} \frac{\mathcal{N}(\mathcal{X}_{r_{k}}\setminus \mathcal{X}_{r_{k+1}},r_{k})}{r_{k}} \notag \\ &\qquad\qquad + c_2 \sum_{k=1}^{k_T} \mathcal{N}\left( \mathcal{X}_{r_{k_T+1}}, r_k \right ) \frac{r_{k_T+1}}{r_{k}^2} \Bigg] \\ &\leq \log \left ( \frac{\max_k |S_k|}{\min_k \delta_k} \right ) \Bigg[ c_1 \sum_{k=1}^{k_T} 2^k\mathcal{N}(\mathcal{X}_{2^{-k}}\setminus \mathcal{X}_{2^{-(k+1)}},2^{-k}) \notag \\ &\qquad\qquad + c_2 2^{-(k_T+1)} \sum_{k=1}^{k_T} 2^{2k} \mathcal{N}\left( \mathcal{X}_{2^{-(k_T+1)}}, 2^{-k} \right ) \Bigg] \\ &\leq \log \left ( \frac{k_T^2 \pi^2 T}{6 \delta} \right ) \Bigg[ c_1 \sum_{k=1}^{k_T} 2^k\mathcal{N}(\mathcal{X}_{2^{-k}}\setminus \mathcal{X}_{2^{-(k+1)}},2^{-k}) \notag \\ &\qquad\qquad + c_2 2^{-(k_T+1)} \sum_{k=1}^{k_T} 2^{2k} \mathcal{N}\left( \mathcal{X}_{2^{-(k_T+1)}}, 2^{-k} \right ) \Bigg] \label{eq32:32the32second32term32of32regret} \end{align}\tag{11}\]

where \(c_1=8c_0(1+2^{d+1} C_d + 4^{d+1} C_d)\) and \(c_2=16c_0\). This concludes the regret part of the proof.

Let us now characterize \(k_T\). Our first two equations describe two facts: the sum of the durations of all completed phases up to \(k_T-1\) is at most \(T\), and each phase duration is the sum of the number of times each point in \(S_k\) was pulled in that phase. \[\begin{align} & s_{k_T-1} = \sum_{k=1}^{k_T-1} \tau_k \le T \le \sum_{k=1}^{k_T} \tau_k = s_{k_T} \tag{12} \\ \forall k\le k_T\;,\;& \tau_k = \sum_{a \in S_k} N_k(a) \tag{13} \end{align}\]

We provide below a first, simple approach that allows us to get an upper bound on \(k_T\), which does not depend on the geometry of \(\mathcal{X}^\star\) or on the level sets \(\mathcal{X}_{r}\).

By 5, at phase \(k\), \(\mathcal{X}^\star \subseteq \mathcal{A}_k\) and by Assumption 2 and because \(f\) is \(L\)-Lipschitz, we know that at least one point of \(S_k\), that we denote \(x_k^{best}\), is such that \(\Delta(x_k^{best}) \leq r_k\). By Lemma 5 this point is never eliminated in the phase, hence \(N_k(x_k^{best}) \ge \ell_k\) where \(\ell_k\) is the final round of phase \(k\). By 2, \(\ell_k\) is the smallest integer \(i\) such that: \[u_{k,i}\le r_k/4\]

We therefore have \(\ell_k \ge \lceil \frac{32c \log (\frac{T}{\delta})}{r_k^2} \rceil\) hence \[\ell_k \ge 2^{2k} c'\log\left ( \frac{T}{\delta} \right )\]

When \(k_T \ge 2\), phase \(k_T-1\) is fully completed. Since phase lengths get exponentially longer as \(k\) grows, it is enough (up to constants) to consider only this last finished phase: \[\begin{align} 2^{2(k_T-2)} \le \ell_{k_T-1} \le N_{k_T-1}(x_{k_T-1}^{best}) \le \tau_{k_T-1} \le T \\ k_T \le 2 + \frac{1}{2} \log_2 (T) \end{align}\]

In order to obtain a more precise bound, one should focus on refining the bound \(N_k(x_k^{best}) \le \tau_k\) and account for the fact that the number of points which are guaranteed to not be eliminated during phase \(k\) is at least \(c_{\mathrm{sep}} \mathcal{M} \left ( \mathcal{X}_{r_{k+1}}, r_k/L \right )\). The above argument can then be applied to each of these points as it was to \(x_k^{best}\), which yields the desired bound linking \(k_T\) and \(T\): \[T \ge \tau_{k_T-1} \ge C_3 2^{2(k_T-2)} \mathcal{M} \left ( \mathcal{X}_{r_{k_T}}, 2^{-(k_T-1)}/L \right ) \log \left ( \frac{T}{\delta} \right )\] where \(C_3 = c_{\mathrm{sep}}c'\). Since \(\mathcal{X}^\star \subseteq \mathcal{X}_{r_{k_T}}\) and by monotonicity of the covering number with respect to the radius, we naturally deduce the bound presented in Lemma [lemma:first32regret32bounds]. ◻

Proof. Recall that by definition, \(\forall x \in \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}, 2^{-k} \geq \Delta(x) \geq 2^{-(k+1)}\). \[\begin{align} \int_{\mathcal{X}_{2^{-l}} \setminus \mathcal{X}_{2^{-k_T}}} \frac{1}{\left ( \Delta(x) \right )^{d+1}} dx & \geq \sum_{k=l}^{k_T-1} \int_{\mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}} \frac{1}{\left ( \Delta(x) \right )^{d+1}} dx \\ & \geq \sum_{k=l}^{k_T-1} \frac{1}{2^{-(d+1)(k+1)}} \int_{\mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}} dx \\ & \geq \frac{1}{2^{3d}} \sum_{k=l+1}^{k_T-1} 2^{(d+1)(k+1)} \int_{\mathcal{X}_{2^{-(k-1)}} \setminus \mathcal{X}_{2^{-(k+2)}}} dx \\ & \geq \frac{1}{2^{3d}} \sum_{k=l+1}^{k_T-1} 2^{(d+1)(k+1)} vol (\mathcal{X}_{2^{-(k-1)}} \setminus \mathcal{X}_{2^{-(k+2)}}) \end{align}\]

We can then bound, for \(k\geq l\), \(vol(\mathcal{X}_{2^{-(k-1)}} \setminus \mathcal{X}_{2^{-(k+2)}} )\), as follows. Let \((x_i)_{i \in \mathcal{N} \left ( \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}} , 2^{-(k+2)}/L \right )}\) be a packing for \(\mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}\). By definition, these points are at distance at least \(2^{-(k+2)}/L\) from one another, so the balls \(B_\infty\left (x_i,2^{-(k+3)}/L \right )\) are disjoint. Furthermore, since \(f\) is \(L\)-Lipschitz, for all \(x_i\), we know that for any point \(y \in B_\infty(x_i, \frac{2^{-(k+3)}}{L})\) we have \(2^{-(k+1)} - 2^{-(k+3)} \leq \Delta(y)\leq 2^{-k} + 2^{-(k+3)}\), which ensures that they belong to \(\mathcal{X}_{2^{-(k-1)}} \setminus \mathcal{X}_{2^{-(k+2)}}\). Hence we can write: \[vol(\mathcal{X}_{2^{-(k-1)}} \setminus \mathcal{X}_{2^{-(k+2)}} ) \geq \sum_{(x_i)_{i \in \mathcal{N} \left ( \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}} , 2^{-(k+2)}/L \right )}} vol \left (B_\infty\left (x_i,\frac{2^{-(k+3)}}{L} \right ) \cap \mathcal{X} \right ).\]

This then yields the following inequality and allows us to use 4 :

\[\begin{align} \int_{\mathcal{X}_{2^{-l}} \setminus \mathcal{X}_{2^{-k_T}}} \frac{1}{\left ( \Delta(x) \right )^{d+1}} dx & \geq \frac{1}{2^{3d}} \sum_{k=l+1}^{k_T-1} 2^{(d+1)(k+1)} \mathcal{N} \left ( \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}} , \frac{2^{-(k+2)}}{L} \right ) \notag \\ &\qquad\qquad \times vol \left ( B_\infty\left(0,\frac{2^{-(k+3)}}{L}\right )\right ) \\ & \geq \frac{v_1 \gamma }{2^{4d+d} L^d} \sum_{k=l+1}^{k_T-1} 2^{(k+1)} \mathcal{N} \left ( \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}} , \frac{2^{-(k+1)}}{L} \right ) \end{align}\]

The missing term \(k=l\) is nonnegative and can be absorbed into the constant \(C\), which yields the stated sum from \(k=l\). Here \(v_1 := vol\left(B_\infty(0,1)\right )\), and we used monotonicity of packing numbers with respect to the radius. This concludes the proof. ◻

Proof. Fix \(\delta=T^{-3}\) and take \(\delta_k=6\delta/(\pi^2k^2)\) so that \(\sum_k\delta_k\le\delta\). Condition on the global good event from Appendix 6.

By Lemma [lemma:first32regret32bounds], there exists a constant \(C>0\) such that \[\label{eq:thm1-start} \begin{align} R_T\;\le\;C\log(T)\Bigg[ &\sum_{k=1}^{k_T}2^k\,\mathcal{N}\bigl(\mathcal{X}_{2^{-k}}\setminus\mathcal{X}_{2^{-(k+1)}},2^{-k}/L\bigr) \\ &\quad + 2^{-(k_T+1)}\sum_{k=1}^{k_T}2^{2k}\,\mathcal{N}\bigl(\mathcal{X}_{2^{-(k_T+1)}}\setminus\mathcal{X}^\star,2^{-k}/L\bigr) \Bigg]. \end{align}\tag{14}\]

While the two terms are complementary, we work on them separately for simplicity.

6.2.0.1 First term (up to phase \(k_T-1\)).

Assumption 4 allows us to apply Lemma 9, yielding \[\label{eq:thm1-first-term} \sum_{k=1}^{k_T-1}2^k\,\mathcal{N}\bigl(\mathcal{X}_{2^{-k}}\setminus\mathcal{X}_{2^{-(k+1)}},2^{-k}/L\bigr) \;\le\;C\int_{\mathcal{X}\setminus\mathcal{X}_{2^{-k_T}}}\frac{1}{\Delta(x)^{d+1}}\,dx.\tag{15}\]

6.2.0.2 Terminal annulus and near-optimal term.

The terminal annulus term corresponding to \(k=k_T\) in the first sum of 14 is: \[2^{k_T}\,\mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}_{2^{-(k_T+1)}}, 2^{-k_T}/L\bigr).\] Since \(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}_{2^{-(k_T+1)}} \subseteq \mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star\), the monotonicity of the packing number implies: \[2^{k_T}\,\mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}_{2^{-(k_T+1)}}, 2^{-k_T}/L\bigr) \;\le\; 2^{k_T}\,\mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star, 2^{-k_T}/L\bigr).\] For the second term in 14 (the near-optimal term), we can use the monotonicity of packing numbers to upper bound it as follows: \[\begin{align} 2^{-(k_T+1)}\sum_{k=1}^{k_T}2^{2k}\,\mathcal{N}\bigl(\mathcal{X}_{2^{-(k_T+1)}}\setminus\mathcal{X}^\star,2^{-k}/L\bigr) & \leq 2^{-k_T}\sum_{k=1}^{k_T}2^{2k}\,\mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star,2^{-k}/L\bigr) \\ & \leq \frac{4}{3}\,2^{-k_T} 2^{2k_T}\mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star,2^{-k_T}/L\bigr) \\ & = \frac{4}{3}\,2^{k_T} \mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star,2^{-k_T}/L\bigr). \label{eq32true32for32reg32second32sum} \end{align}\tag{16}\] Therefore, both the terminal annulus term \(k=k_T\) and the near-optimal term are upper bounded (up to constant factors) by \(2^{k_T} \mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star,2^{-k_T}/L\bigr)\).

As in the proof of 9, we use the volumetric condition in 4 to relate this packing number to the volume integral over the near-optimal region. Indeed, let \((x_i)_{i \in \mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star, 2^{-k_T}/L\bigr)}\) be a maximal packing of \(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star\) at scale \(2^{-k_T}/L\). The disjoint balls \(B_\infty(x_i, 2^{-(k_T+3)}/L)\) are all contained within \(\mathcal{X}_{2^{-(k_T-1)}} \setminus \mathcal{X}^\star\). Summing their volumes and applying 4 yields: \[\label{eq:32link32integ32and32sum32rest} \int_{\mathcal{X}_{2^{-k_T}} \setminus \mathcal{X}^\star} \frac{dx}{\left (2^{-k_T}\right )^{d+1}} \geq \frac{v_1 \gamma}{2^{4d+d} L^d} 2^{k_T}\mathcal{N}\bigl(\mathcal{X}_{2^{-k_T}}\setminus\mathcal{X}^\star,2^{-k_T}/L\bigr).\tag{17}\]

Combining 17 , 16 , and the terminal annulus bound, we can sum them with the first term’s integral bound 15 to obtain: \[R_T \leq \log(T)\left[ C_1 \int_{\mathcal{X}\setminus\mathcal{X}_{2^{-k_T}}}\frac{1}{\Delta(x)^{d+1}}\,dx + C_2 \int_{\mathcal{X}_{2^{-k_T}} \setminus \mathcal{X}^\star} \frac{dx}{\left (2^{-k_T}\right )^{d+1}} \right]\] where \(C_2\) is a constant depending on \(L, d, v_1, \gamma\). This allows us to write overall: \[R_T \leq C_3\log(T) \int_{\mathcal{X} \setminus \mathcal{X}^\star} \frac{dx}{\max\left(\Delta(x), 2^{-k_T} \right )^{d+1}}\] ◻

Proof. To ease the notations, we denote \(N_k\) the set corresponding to the packing number \(\mathcal{N} \left ( \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}, 2^{-k}\right )\) (if multiple such sets exist, we require \(N_k\) be one of these sets). We also use the following notation : \(N_k^l := \{x \in N_k | 2^{l} \leq \frac{\text{vol} \left ( B \left ( x,2^{-k} \right ) \cap \mathcal{X} \right )}{v_1 2^{-dk}} < 2^{l+1} \}\).

\[\begin{align} \sum_{k=1}^{k_T} 2^{k} \mathcal{N} \left ( \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}, 2^{-k}\right )& \leq \sum_{k=1}^{k_T} 2^{k} \sum{x \in N_k} \frac{\text{vol}\left( B(x,2^{-k}) \cap \mathcal{X} \right)}{\text{vol}\left( B(x,2^{-k}) \cap \mathcal{X} \right)} \\ & \leq \sum_{k=1}^{k_T} 2^{k} \sum_{l\geq 0} \sum_{x \in N_k^l} \frac{\text{vol}\left( B(x,2^{-k}) \cap \mathcal{X} \right)}{v_1 2^{-dk} 2^{l}} \\ & \leq \sum_{k=1}^{k_T} 2^{k} \sum_{l\geq 0} \sum_{x \in N_k^l} \frac{\text{vol}\left( B(x,2^{-k}) \cap \mathcal{X} \right)}{v_1 \Delta(x)^d 2^{l}}\\ & \leq \sum_{k=1}^{k_T} \sum_{l\geq 0} \sum_{x \in N_k^l} \frac{\text{vol}\left( B(x,\Delta(x)/2) \cap \mathcal{X} \right)}{v_1 \Delta(x)^{d+1} 2^{l}}\\ \end{align}\]

To match the above term we define \(l_{\Delta}(x):= \sup \{ l \in \mathbb{R}^+ | \frac{ vol\left( B(x,\Delta(x)/2) \cap \mathcal{X} \right)}{v_1 \Delta(x)^{d} 2^l} \geq 1 \} \cup \{ \infty \}\). Notice \(l_{\Delta}(x) = \log_2 \left ( \frac{ vol\left( B(x,\Delta(x)/2) \cap \mathcal{X} \right)}{v_1 \Delta(x)^{d}} \right ).\)

Given this, we can define directly \(d_{\Delta}(x):= \inf \{ d>0 | \frac{ vol\left( B(x,\Delta(x)/2) \cap \mathcal{X} \right)}{v_1 \Delta(x)^{d}} \leq 1 \}\). By 5, we have \(d_{\Delta}(x) = \frac{\log \left ( vol(B(x,\Delta(x)/2) \cap \mathcal{X}) \right )-\log(v_1)}{\log (\Delta(x))}\).

With this definition, we can do the following computations, let \(y \in B(x,\Delta(x)/2) \cap \mathcal{X}\). Notice that, since \(f\) is Lipschitz, \(\Delta(y) \leq \frac{3\Delta(x)}{2}\). Therefore, we have that \(B(y, \Delta(y)/12) \subseteq B(x,\Delta(x)/2)\). These combined with the definition of \(d_{\Delta}(y)\), gives us, for all \(y \in B(x,\Delta(x)/2) \cap \mathcal{X}\): \[\frac{vol (B(x,\Delta(x)/2) \cap \mathcal{X})}{vol(B(x,\Delta(x)/2) \cap \mathcal{X})} \leq \frac{vol(B(x,\Delta(x)/2) \cap \mathcal{X})}{vol(B(y,\Delta(y)/12) \cap \mathcal{X})}\]

By using the definition of \(d_{\Delta}(y)\), we have \[\begin{align} \frac{vol (B(x,\Delta(x)/2) \cap \mathcal{X})}{vol(B(x,\Delta(x)/2) \cap \mathcal{X})} & \leq \frac{vol (B(x,\Delta(x)/2) \cap \mathcal{X})}{v_1 \frac{\Delta}{3}(y)^{d_{\frac{\Delta}{3}}(y)}} \\ & \leq \frac{3}{v_1} \int_{B(x,\Delta(x)/2) \cap \mathcal{X}} \frac{dy}{\Delta(y)^{d_{\frac{\Delta}{3}}(y)}} \end{align}\]

And obtain by summing \[\begin{align} \sum_{k=1}^{k_T} 2^{k} \mathcal{N} \left ( \mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}, 2^{-k}\right ) & \leq \sum_{k=1}^{k_T} \int_{\mathcal{X}_{2^{-k}} \setminus \mathcal{X}_{2^{-(k+1)}}} \frac{dy}{\Delta(y)^{d_{\Delta(y)/8}+1}} \\ & \leq \frac{8}{v_1} \int_{\mathcal{X} \setminus \mathcal{X}_{2^{-(k_T+1)}}} \frac{dy}{\Delta(y)^{d_{\Delta(y)/8}+1}} \end{align}\]

Where we use the fact that points from the packing define disjoint ball of radius \(2^{-k}\).

Outside of this proof, we redefine \(d_{\Delta}(x)\) to be \(d_{\frac{\Delta}{8}}(x)\) for convenience. ◻

Proof. We leverage existing results from [26], restated in 10, which yield the following lower bound on the regret incurred by any algorithm.

We assume an \(a_0\)-consistent algorithm. We take \[a_0=\frac{d+1}{d+2},\qquad \Delta_T:=T^{-(1-a_0)}=T^{-\frac{1}{d+2}}.\] This choice of \(a_0\) is the correct one; indeed the family of algorithms for which we want to control the minimum amount of regret on each specific instance \((\mathcal{X},f)\) are algorithms that already exhibit the worst-case regret bounds. We know from the literature [13] that the worst-case regret bound in the Lipschitz bandit setting is \(\tilde{\Theta} \left ( T^{\frac{d+1}{d+2}} \right )\). We set \(k_T := \lfloor \log_2 (T) / (d+2) \rfloor\) such that, up to multiplicative constants, \(2^{(d+2)k_T}\asymp T\).

We apply 3 with \(\Delta=\Delta_T\) and define \[\mathcal{Z}_j:=\{x\in\mathcal{X}:2^j\Delta_T\le \Delta(x)<2^{j+1}\Delta_T\},\qquad m_j:=\mathcal{N}(\mathcal{Z}_j,c\,2^j\Delta_T/L).\] The lower bound gives \[\label{eq:lb-deltaT} \ifthenelse{ \equal{R_T}{} } {\mathbb{E}} {\mathbb{E} \left [ R_T \right ] } \;\ge\;c\sum_{j\ge 0}\frac{m_j}{2^{j+2}\Delta_T}.\tag{18}\]

We reindex by \(k=k_T-j-1\). Since \(k_T=\lfloor \log_2(T)/(d+2) \rfloor\) and \(\Delta_T=T^{-1/(d+2)}\), we have \(2^{-(k_T+1)}<\Delta_T\le 2^{-k_T}\), hence \[2^{-(k+2)}<2^j\Delta_T\le 2^{-(k+1)},\qquad 2^{-(k+1)}<2^{j+1}\Delta_T\le 2^{-k}.\] Hence \(\mathcal{X}_{2^{-k}}\setminus\mathcal{X}_{2^{-(k+1)}} \subseteq \mathcal{Z}_{j-1} \cup \mathcal{Z}_j \cup \mathcal{Z}_{j+1}\) and by subadditivity and monotonicity of packing numbers, \[m_{j-1} + m_j + m_{j+1} \;\ge\;\mathcal{N}(\mathcal{X}_{2^{-k}}\setminus\mathcal{X}_{2^{-(k+1)}},c'\,2^{-k}/L).\] Moreover \(2^{j+2}\Delta_T\le 2^{-(k-1)}\), so \(1/(2^{j+2}\Delta_T)\ge 2^{k-1}\). Summing over adjacent indices and adjusting the constant factor yields \[\label{eq:lb-sum-outer} \ifthenelse{ \equal{R_T}{} } {\mathbb{E}} {\mathbb{E} \left [ R_T \right ] } \;\ge\;c\sum_{k=1}^{k_T}2^{k}\,\mathcal{N}(\mathcal{X}_{2^{-k}}\setminus\mathcal{X}_{2^{-(k+1)}},c'\,2^{-k}/L).\tag{19}\]

For each \(k\), let \(A_k:=\mathcal{X}_{2^{-k}}\setminus\mathcal{X}_{2^{-(k+1)}}\) and \(r_k:=c'2^{-k}/L\). Since a maximal \(r_k\)-packing covers \(A_k\), \[\mathcal{N}(A_k,r_k)\;\ge\;\frac{\mathrm{vol}(A_k)}{v_1 r_k^d}\;\ge\;c\,2^{kd}\,\mathrm{vol}(A_k).\] On \(A_k\) we have \(\Delta(x)\ge 2^{-(k+1)}\), hence \[2^{k}\mathcal{N}(A_k,r_k)\;\ge\;c\,2^{(d+1)k}\,\mathrm{vol}(A_k)\;\ge\;c\,2^{-(d+1)}\int_{A_k}\frac{dx}{\Delta(x)^{d+1}}.\] Summing over \(k\le k_T\) gives the first integral term \[R_T\;\ge\;c' \int_{\mathcal{X}\setminus\mathcal{X}_{2^{-k_T}}}\frac{dx}{\Delta(x)^{d+1}}.\] ◻

Proof of Lemma 2. Let \(d_z\) and \(d^\star\) be the zooming dimension and optimal dimension of the instance \((\mathcal{X},f)\). By definition of the zooming dimension, for all \(r>0\), we have \(\mathcal{M}(\mathcal{X}_r \setminus \mathcal{X}^\star, r) \le \mathcal{O}(r^{-d_z})\). Let \(y \in \mathcal{X}^\star\). Since \(\mathcal{X}^\star\) is connected and there exists \(r_0 > 0\) such that \(\mathcal{B}(\mathcal{X}^\star, r_0) \subset \mathcal{X}\), the affine hull of \(\mathcal{X}_r \setminus \mathcal{X}^\star\) contains \(\mathcal{X}^\star\).

For any small \(r>0\), let \(\mathbf{O}\) be an optimal \(r\)-covering of \(\mathcal{X}_r \setminus \mathcal{X}^\star\). We construct a valid covering of \(\mathcal{X}^\star\) at scale \(r\) by adding points along the segments between each covering point in \(\mathbf{O}\) and \(y\). Since the maximum distance is bounded, this requires adding at most \(\mathcal{O}(1/r)\) points per segment. This new set of points covers \(\mathcal{X}^\star\) at scale \(r\), so its size is bounded below by the minimal covering number \(\mathcal{M}(\mathcal{X}^\star, r)\). Thus, we have: \[\mathcal{M}(\mathcal{X}^\star, r) \le \mathcal{O}(1/r) \cdot \mathcal{M}(\mathcal{X}_r \setminus \mathcal{X}^\star, r)\] Substituting the dimension bounds gives \(r^{-d^\star} \le \mathcal{O}(r^{-(d_z+1)})\). For this to hold as \(r \to 0\), we must have \(d^\star \le d_z + 1\). ◻

Proof. For any fixed time step \(t \ge 1\), let \(\delta_t = \frac{6 \delta}{\pi^2 t^2}\), so that \(\sum_{t=1}^{T} \delta_t \leq \delta\). By the union bound over all \(t \ge 1\), if we establish that for each \(t\), uniform concentration holds with probability at least \(1 - \delta_t\), then concentration holds uniformly over all \(t \ge 1\) with probability at least \(1 - \delta\).

Fix \(t \ge 1\). Let \(\epsilon > 0\) be a resolution scale to be chosen later, and let \(S_\epsilon\) be an \(\epsilon\)-net of \(\mathcal{X}\) with respect to the \(\ell_\infty\) norm. Since \(\mathcal{X} \subset [0, 1]^d\), we can construct such a net with cardinality \(|S_\epsilon| \le \lceil 1/\epsilon \rceil^d\).

For any fixed \(y \in S_\epsilon\), the random variables \(f_k(y)\) are i.i.d., bounded in \([0, 1]\), and have expectation \(f(y)\). By Hoeffding’s inequality, for any \(u > 0\): \[\mathbb{P}\left( |\hat{f}_t(y) - f(y)| > u \right) \le 2 \exp(-2 t u^2).\] Applying a union bound over all \(y \in S_\epsilon\), we have with probability at least \(1-\delta_t\): \[\label{eq:net95concentration} \max_{y \in S_\epsilon} |\hat{f}_t(y) - f(y)| \le \sqrt{\frac{\log(2|S_\epsilon|/\delta_t)}{2t}} \le \sqrt{\frac{d \log(1/\epsilon + 1) + \log(2/\delta_t)}{2t}}.\tag{20}\]

We now extend this concentration to the entire continuous space \(\mathcal{X}\). For any arbitrary \(x \in \mathcal{X}\), let \(y(x) \in S_\epsilon\) be its closest point in the net, such that \(\|x - y(x)\|_\infty \le \epsilon\). Since each \(f_k\) is \(L\)-Lipschitz, the empirical average \(\hat{f}_t\) is also \(L\)-Lipschitz. Similarly, the expected function \(f\) is \(L\)-Lipschitz. We can thus bound the error at \(x\) using the triangle inequality: \[\begin{align} |\hat{f}_t(x) - f(x)| &\le |\hat{f}_t(x) - \hat{f}_t(y(x))| + |\hat{f}_t(y(x)) - f(y(x))| + |f(y(x)) - f(x)| \\ &\le L \|x - y(x)\|_\infty + |\hat{f}_t(y(x)) - f(y(x))| + L \|x - y(x)\|_\infty \\ &\le 2L\epsilon + \max_{y \in S_\epsilon} |\hat{f}_t(y) - f(y)|. \end{align}\]

Conditioning on the high-probability event of Equation 20 , we obtain: \[\sup_{x \in \mathcal{X}} |\hat{f}_t(x) - f(x)| \le 2L\epsilon + \sqrt{\frac{d \log(1/\epsilon + 1) + \log(2/\delta_t)}{2t}}.\] To minimize this upper bound, we match the uncertainty level with the radius of the net by choosing \(\epsilon = \frac{1}{L\sqrt{t}}\). Substituting this choice yields: \[\sup_{x \in \mathcal{X}} |\hat{f}_t(x) - f(x)| \le \frac{2}{\sqrt{t}} + \sqrt{\frac{d \log(L\sqrt{t} + 1) + \log(2/\delta_t)}{2t}} \le \frac{1}{4} \epsilon_t,\] where we set \(\epsilon_t = 2L \sqrt{\frac{2d \log(t L) + \log(1/\delta_t)}{t}}\). This concludes the proof. ◻

Proof. Let \(\mathcal{E}\) be the uniform concentration event from Lemma 11, which holds with probability at least \(1-\delta\). On the complement event \(\mathcal{E}^c\), we bound the regret crudely by \(T \max \Delta \le T\). Since \(\delta = T^{-3}\), this failure term contributes at most \(1/T^2 \le o(1)\), which is negligible and can be accounted for by a constant term in the regret. We now conduct the proof conditioning on \(\mathcal{E}\).

Recall that at each round \(t \ge 2\), the algorithm chooses \(x_t\) uniformly from the active set \(\mathcal{A}_t\) defined using the information available up to round \(t-1\): \[\mathcal{A}_t := \{ x \in \mathcal{X} \mid \hat{f}_{t-1}(x) \ge \max \hat{f}_{t-1} - \epsilon_{t-1} \}.\] At \(t=1\), we set \(\mathcal{A}_1 = \mathcal{X}\). The expected regret is bounded as: \[\begin{align} \label{eq:regret95expert95base} R_T &\le C_{ini} + \sum_{t=2}^T \mathbb{E}[f^\star - f(x_t) \mid \mathcal{F}_{t-1}] \notag \\ &\le C_{ini} + \sum_{t=2}^T \frac{1}{\text{vol}(\mathcal{A}_t)} \int_{\mathcal{A}_t \setminus \mathcal{X}^\star} \Delta(a) da. \end{align}\tag{21}\]

Under the concentration event \(\mathcal{E}\), the empirical means satisfy \(\sup_{x} |\hat{f}_{t-1}(x) - f(x)| \le \frac{1}{4} \epsilon_{t-1}\) for all \(t \ge 2\). This allows us to establish the two following properties: For any \(x \in \mathcal{X}_{\epsilon_{t-1}/2}\) (i.e., \(\Delta(x) \le \epsilon_{t-1}/2\)), we have: \[\hat{f}_{t-1}(x) \ge f(x) - \frac{1}{4}\epsilon_{t-1} \ge f^\star - \Delta(x) - \frac{1}{4}\epsilon_{t-1} \ge f^\star - \frac{3}{4}\epsilon_{t-1} \ge \max \hat{f}_{t-1} - \epsilon_{t-1}.\] To see why the last inequality holds, note that under the concentration event \(\mathcal{E}\), we have \(\hat{f}_{t-1}(y) \le f(y) + \frac{1}{4}\epsilon_{t-1} \le f^\star + \frac{1}{4}\epsilon_{t-1}\) for all \(y \in \mathcal{X}\), which implies \(\max \hat{f}_{t-1} \le f^\star + \frac{1}{4}\epsilon_{t-1}\) (or equivalently \(f^\star \ge \max \hat{f}_{t-1} - \frac{1}{4}\epsilon_{t-1}\)). This implies \(\mathcal{X}_{\epsilon_{t-1}/2} \subseteq \mathcal{A}_t\), and thus \(\text{vol}(\mathcal{A}_t) \ge \text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})\). Conversely, for any \(x \in \mathcal{A}_t\), we have: \[f(x) \ge \hat{f}_{t-1}(x) - \frac{1}{4}\epsilon_{t-1} \ge \max \hat{f}_{t-1} - \frac{5}{4}\epsilon_{t-1} \ge \hat{f}_{t-1}(x^\star) - \frac{5}{4}\epsilon_{t-1} \ge f^\star - \frac{3}{2}\epsilon_{t-1},\] which implies \(\Delta(x) \le 2\epsilon_{t-1}\). Thus, \(\mathcal{A}_t \subseteq \mathcal{X}_{2\epsilon_{t-1}}\).

Substituting back into 21 , we obtain: \[\label{eq:expert95deterministic95sum} R_T \;\le\; 1 + \sum_{t=2}^T \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \int_{\mathcal{X}_{2\epsilon_{t-1}} \setminus \mathcal{X}^\star} \Delta(a) da.\tag{22}\]

To evaluate this sum, we partition the domain \(\mathcal{X}_{2\epsilon_1} \setminus \mathcal{X}^\star\) into time-based regions \(\mathcal{X}_{2\epsilon_{t'-1}} \setminus \mathcal{X}_{2\epsilon_{t'}}\) for \(t' \ge 2\), and a residual region \(\mathcal{X}_{2\epsilon_T} \setminus \mathcal{X}^\star\).

The sum of integrals in 22 can be rewritten by exchanging the order of summation: \[\begin{align} \sum_{t=2}^T \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \int_{\mathcal{X}_{2\epsilon_{t-1}} \setminus \mathcal{X}^\star} \Delta(a) da &= \sum_{t=2}^T \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \left( \sum_{t'=t}^T \int_{\mathcal{X}_{2\epsilon_{t'-1}} \setminus \mathcal{X}_{2\epsilon_{t'}}} \Delta(a) da + \int_{ \mathcal{X}_{2\epsilon_{T}} \setminus \mathcal{X}^\star} \Delta(a) da \right) \\ &= \sum_{t'=2}^{T} \int_{\mathcal{X}_{2\epsilon_{t'-1}} \setminus \mathcal{X}_{2\epsilon_{t'}}} \Delta(a) \left( \sum_{t=2}^{t'} \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \right) da + \int_{ \mathcal{X}_{2\epsilon_{T}} \setminus \mathcal{X}^\star} \Delta(a) \left( \sum_{t=2}^T \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \right) da. \end{align}\]

For any \(a \in \mathcal{X}_{2\epsilon_{t'-1}} \setminus \mathcal{X}_{2\epsilon_{t'}}\), we know that \(2\epsilon_{t'} < \Delta(a) \le 2\epsilon_{t'-1}\). Therefore, for any \(t \le t'\), we have \(\epsilon_{t-1} \ge \epsilon_{t'-1} \ge \Delta(a)/2\), which implies \(\epsilon_{t-1}/2 \ge \Delta(a)/4\). By the monotonicity of the level sets, we have \(\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2}) \ge \text{vol}(\mathcal{X}_{\Delta(a)/4})\).

Moreover, from the definition of \(\epsilon_{t'} = \tilde{\Theta}((t')^{-1/2})\), the condition \(2\epsilon_{t'} < \Delta(a)\) implies that \(t' \le C_0 \frac{\log T}{\Delta(a)^2}\) for some constant \(C_0 > 0\). The inner sum over \(t\) is therefore bounded by: \[\sum_{t=2}^{t'} \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \;\le\; \frac{t'}{\text{vol}(\mathcal{X}_{\Delta(a)/4})} \;\le\; C_0 \frac{\log T}{\Delta(a)^2 \text{vol}(\mathcal{X}_{\Delta(a)/4})}.\]

Multiplying by \(\Delta(a)\) and integrating over each region \(\mathcal{X}_{2\epsilon_{t'-1}} \setminus \mathcal{X}_{2\epsilon_{t'}}\), we obtain for the first part of the sum: \[\int_{\mathcal{X}_{2\epsilon_{t'-1}} \setminus \mathcal{X}_{2\epsilon_{t'}}} \Delta(a) \left( \sum_{t=2}^{t'} \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \right) da \;\le\; C_0 \log T \int_{\mathcal{X}_{2\epsilon_{t'-1}} \setminus \mathcal{X}_{2\epsilon_{t'}}} \frac{1}{\Delta(a) \text{vol}(\mathcal{X}_{\Delta(a)/4})} da.\]

Summing this bound over all \(t'\) from \(2\) to \(T\) yields the integral bound over the resolved region: \[C_1 \log T \int_{\mathcal{X}_{2\epsilon_1} \setminus \mathcal{X}_{2\epsilon_T}} \frac{dx}{\Delta(x) \text{vol}(\mathcal{X}_{\Delta(x)/4})} \;\le\; C_1 \log T \int_{\mathcal{X} \setminus \mathcal{X}_{2\epsilon_T}} \frac{dx}{\Delta(x) \text{vol}(\mathcal{X}_{\Delta(x)/4})}.\] Note that the volumes \(\text{vol}(\mathcal{X}_{\Delta(x)/4})\) and \(\text{vol}(\mathcal{X}_{\Delta(x)/2})\) are equivalent up to constant factors under standard scaling assumptions on the level sets, and this constant is absorbed by \(C_1\).

For the residual region \(\mathcal{X}_{2\epsilon_T} \setminus \mathcal{X}^\star\), which corresponds to the second part of the sum, we can rewrite it back as: \[\int_{ \mathcal{X}_{2\epsilon_{T}} \setminus \mathcal{X}^\star} \Delta(a) \left( \sum_{t=2}^T \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \right) da = \sum_{t=2}^T \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_{t-1}/2})} \int_{\mathcal{X}_{2\epsilon_T} \setminus \mathcal{X}^\star} \Delta(a) da.\]

Combining these two bounds yields the stated regret guarantee of Theorem [thm:full-info-instance]. ◻

Proof. Let \(M = \max(d_z, d^\star)\). The instance-dependent regret bound of Theorem [thm:full-info-instance] can be decomposed into two main components, \(R_T \le \mathcal{O}(\log T) (I_1 + I_2)\), where \[\begin{align} I_1 &= \int_{\mathcal{X} \setminus \mathcal{X}_{\epsilon_T}} \frac{1}{\Delta(x) \text{vol}(\mathcal{X}_{\Delta(x)/2})} dx, \\ I_2 &= \sum_{t=1}^T \frac{1}{\text{vol}(\mathcal{X}_{\epsilon_t})} \int_{\mathcal{X}_{\epsilon_T}} \Delta(x) dx. \end{align}\] Recall from the proof of Theorem [thm:full-info-instance] that \(\epsilon_t = \tilde{\Theta}(t^{-1/2})\).

8.3.0.1 Geometric volume bounds.

By the definition of the zooming dimension \(d_z\), the maximum number of disjoint \(\ell_\infty\)-balls of radius \(r\) that can be packed in the region \(\mathcal{X}_{2r} \setminus \mathcal{X}_r\) is bounded by \(c_z r^{-d_z}\) for some constant \(c_z > 0\). Since the action space \(\mathcal{X}\) is embedded in \(\mathbb{R}^d\), the volume of each such \(\ell_\infty\)-ball of radius \(r\) is \((2r)^d \propto r^d\). Because these balls are mutually disjoint, the volume of their union is simply the sum of their individual volumes. Consequently, we can upper bound the volume of the annulus by the number of balls multiplied by their volume: \[\text{vol}(\mathcal{X}_{2r} \setminus \mathcal{X}_r) \le c_z r^{-d_z} \cdot (2r)^d = C_z r^{d - d_z},\] for some constant \(C_z > 0\). Applying the exact same reasoning to the near-optimal dimension \(d^\star\), we obtain an analogous bound for the near-optimal region: \(\text{vol}(\mathcal{X}_r) \le C_\star r^{d - d^\star}\). By summing the volumes of dyadic annuli geometrically, we also naturally have \(\text{vol}(\mathcal{X}_r) \le C_z' r^{d - d_z}\).

We can similarly derive a volume lower bound. Because \(d_z\) is the smallest exponent characterizing the packing number of the annuli, and \(d^\star\) is the smallest exponent characterizing the near-optimal region, the packing number of \(\mathcal{X}_r\) requires at least \(\Omega(r^{-M})\) balls of radius \(r\), where \(M = \max(d_z, d^\star)\). This directly implies a lower bound on the volume of \(\mathcal{X}_r\): \[\text{vol}(\mathcal{X}_r) \ge c_1 r^{d - M},\] for some universal constant \(c_1 > 0\) independent of \(T\).

8.3.0.2 Bounding the first term (Peeling argument).

We decompose the domain of integration \(\mathcal{X} \setminus \mathcal{X}_{\epsilon_T}\) into disjoint dyadic annuli. Let \(J = \lceil \log_2(1/\epsilon_T) \rceil\). We define the annuli as \(A_j = \mathcal{X}_{2^{-j+1}} \setminus \mathcal{X}_{2^{-j}}\) for \(j = 1, \dots, J\). For any \(x \in A_j\), we have \(\Delta(x) \in (2^{-j}, 2^{-j+1}]\). In particular, \(\Delta(x) > 2^{-j}\), which allows us to lower bound the volume of the inner optimal set using our established lower bound: \[\text{vol}(\mathcal{X}_{\Delta(x)/2}) \ge \text{vol}(\mathcal{X}_{2^{-(j+1)}}) \ge c_1 2^{-(j+1)(d-M)}.\] Substituting this, along with the volume upper bound \(\text{vol}(A_j) \le C_z 2^{-j(d-d_z)}\), into the integral over \(A_j\), we obtain: \[\begin{align} \int_{A_j} \frac{1}{\Delta(x) \text{vol}(\mathcal{X}_{\Delta(x)/2})} dx &\le \frac{\text{vol}(A_j)}{2^{-j} \cdot c_1 2^{-(j+1)(d-M)}} \\ &\le \frac{C_z 2^{-j(d-d_z)}}{c_1 2^{-M - j(1+d-M)}} \\ &= C' 2^{j(1 + d_z - M)}. \end{align}\] Summing this bound over all annuli \(j=1, \dots, J\), we have: \[I_1 \le C' \sum_{j=1}^J 2^{j(1 + d_z - M)} \le C'' 2^{J \max(0, 1 + d_z - M)}.\] Since \(2^J \approx \epsilon_T^{-1} = \tilde{\mathcal{O}}(T^{1/2})\), we have \(I_1 = \tilde{\mathcal{O}}\left(T^{\frac{1 + d_z - M}{2}}\right)\). Note that by Lemma 2, we naturally have \(M \le d_z + 1\), meaning \(1 + d_z - M \ge 0\), and thus the exponent is non-negative.

8.3.0.3 Bounding the residual term.

For the second term \(I_2\), we upper bound the inner integral by the maximum suboptimality gap in \(\mathcal{X}_{\epsilon_T}\) multiplied by its volume: \[\int_{\mathcal{X}_{\epsilon_T}} \Delta(x) dx \le \epsilon_T \text{vol}(\mathcal{X}_{\epsilon_T}) \le C_z' \epsilon_T^{1 + d - d_z}.\] For the sum over time steps, we use the volume lower bound \(\text{vol}(\mathcal{X}_{\epsilon_t}) \ge c_1 \epsilon_t^{d-M}\). Plugging these bounds into \(I_2\) yields: \[\begin{align} I_2 &\le C_z' \epsilon_T^{1 + d - d_z} \sum_{t=1}^T \frac{1}{c_1 \epsilon_t^{d-M}} \\ &= \mathcal{O}\left( \epsilon_T^{1 + d - d_z} \right) \sum_{t=1}^T \mathcal{O}\left( \epsilon_t^{-(d-M)} \right) \\ &= \tilde{\mathcal{O}}\left( T^{-\frac{1 + d - d_z}{2}} \right) \sum_{t=1}^T \tilde{\mathcal{O}}\left( t^{\frac{d-M}{2}} \right) \\ &= \tilde{\mathcal{O}}\left( T^{-\frac{1 + d - d_z}{2}} \cdot T^{1 + \frac{d-M}{2}} \right) \\ &= \tilde{\mathcal{O}}\left( T^{\frac{2 - 1 - d + d_z + d - M}{2}} \right) \\ &= \tilde{\mathcal{O}}\left( T^{\frac{1 + d_z - M}{2}} \right). \end{align}\]

8.3.0.4 Conclusion.

Combining the bounds for \(I_1\) and \(I_2\), and recalling that \(M = \max(d_z, d^\star)\), we conclude that the total regret is bounded by: \[R_T \le \tilde{\mathcal{O}}\left( T^{\frac{1 + d_z - \max(d_z, d^\star)}{2}} \right),\] which rigorously completes the proof. ◻

Proof. We argue exactly as in Lemma 6, replacing ordinary coverings by forward coverings. Let \(x^\star\in\mathcal{X}^\star\cap\mathcal{A}_k\). By construction of \(S_k\), there exists \(a\in S_k\) such that \(x^\star\in B_\infty^+(a,r_k/L) \cap \mathcal{A}_k\). Hence \(a\preceq x^\star\) and \(\|x^\star-a\|_\infty\le r_k/L\). 6 then gives \[f^\star-f(a)\;=\;f(x^\star)-f(a)\;\le\;L\|x^\star-a\|_\infty\;\le\;r_k,\] so \(\Delta(a)\le r_k\). By Lemma 5, the point \(a\) is never eliminated and therefore belongs to \(\widehat S_k\). Since \(x^\star\in B_\infty^+(a,r_k/L) \cap \mathcal{A}_k\), it also belongs to \(\mathcal{A}_{k+1}\). This proves the claim. ◻

Proof. The proof of Lemma 8 only uses the existence, in each phase, of at least one benchmark point \(b\in S_k\) satisfying \(\Delta(b)\le r_k\) and surviving until the end of the phase. Proposition 1 provides exactly such a point in the one-sided setting. Once this benchmark point is available, the elimination argument for any arm \(a\in S_k\) is unchanged. The bound therefore follows verbatim. ◻

Proof. Let \(x^\star\in\mathcal{X}^\star\). Since \(S\) is a forward cover of \(\mathcal{X}\) at scale \(r_\Delta\), there exists \(a\in S\) such that \(x^\star\in B_\infty^+(a,r_\Delta) \cap \mathcal{X}\). Hence \(a\preceq x^\star\) and \(\|x^\star-a\|_\infty\le r_\Delta\). By 6, \[\Delta(a)\;=\;f^\star-f(a)\;\le\;L\|x^\star-a\|_\infty\;\le\;Lr_\Delta\;=\;\frac{\Delta_f}{4}.\] By definition of \(\Delta_f\), every suboptimal point has gap at least \(\Delta_f\). Therefore \(a\) cannot be suboptimal, and thus \(a\in\mathcal{X}^\star\). This proves that \(S\cap\mathcal{X}^\star\neq\emptyset\).

The second statement is then immediate from standard finite-armed bandit theory: once the action set is reduced to the finite set \(S\), any gap-dependent algorithm such as UCB satisfies a regret bound of order \(\sum_{a\in S\setminus\mathcal{X}^\star}(\log T)/\Delta(a)\) in expectation; see, e.g., [15]. Since \(\Delta(a)\ge \Delta_f\) for every \(a\in S\setminus\mathcal{X}^\star\), the displayed upper bound follows. ◻