Continuum-armed bandit on the general metric space. Unfortunately, generalizing this approach to that setting would be highly nontrivial, as polynomial and trigonometric features are not even defined on arbitrary metric spaces. On the other side, the main competitor of this algorithm, UCB-meta-algorithm, suffers the same issue, also because the concept of "differentiability" itself cannot be trivially defined.

Computational performance in multidimensional space. Please see the common answer about computational complexity.

Does the algorithm work without knowing the value of $T$? Please see the common answer about adaptivity.

For the presentation of Algorithm 1, why don't the authors specify how to discretize the arm space directly there? In fact, discretization is unavoidable for all the algorithms considered in the state of the art, the only exception being Zooming, which without discretization is NP-Hard. Therefore, to grant a fair comparison, we preferred not to specify the discretization to show in Table 1 how the performance of every algorithm depends on the number of its elements. Indeed, it is true that in the general case, a uniform $T^{-1/2}-$cover would be the best choice, but also emphasizing the dependence on the cardinality $k$ of a general discretization is important.

Use of OB-LinUCB rather than OB-PE in the experiments We made this choice based on the principle that, usually, algorithms that optimize the worst-case regret are not the best option in practice. Coherently with this choice, we have compared our algorithm not with BPE, which achieves the best regret in kernelized bandits, but with IGP-UCB, which is well-known to have superior performance in practice regardless of the worse regret bound. Still, since also the practical performance of OB-PE is an interesting question, we are going to perform the experiments with this algorithm and upload them in a new version of the paper before the end of the discussion period.

Discretization in the experiments As the reviewer has understood, we discretize the interval [0,1] evenly with $\sqrt T$ arms. Unfortunately, OB-LinUCB is not endowed with a regret bound for this setting, and it is only shown as the most natural algorithm that can be built with orthogonal function representation.

Some experiments one high-dim space (e.g. $[0,1]^2$) will make your experiments more reliable. I am concerned on the computational issue of the algorithm since the number of arms and dimension may explode exponentially. First point: Being the algorithm valid for $d>1$, it is indeed a good idea to add an experiment in case of a bi-dimensional environment. We will do it and upload it in a new version of the paper before the end of the discussion period. Unfortunately, it will not be possible to include also the baselines used in the current experiment, as their running time is too high, and we cannot have the results in time. Second point: See the common answer about computational complexity.

We thank the reviewer for their comments and have hope to have addressed all their questions.

Adaptivity for unknown $T$ and how to choose $N$ without $s$. See the common answer about adaptivity.

Choice of $N$ in the experiments. Keeping the values of $N$ in the experiments disconnected from theory was a deliberate choice to show that the requirement to know the differentiability of the reward function exists only in theory. In fact, having chosen a fixed value of $N$ for functions with very different levels of regularity suggests that this parameter can be chosen in a totally empirical way and tuned very easily.

Computational complexity dependence on $N$. This question is linked to the theme of computational complexity, therefore, we suggest the reviewer to also see the "Computational complexity" section in the answer to all reviewers. In short, the computational complexity scales as $N^{3d}$, which means $\widetilde N^3$, where $\widetilde N$ is the number of features. This is unavoilable while using algorithms for linear bandits, as inversion of a design matrix is necessary. Still, note that the algorithm chooses $N$ in a way that $N^{d}\le T$, so that the full computational complexity does not explode.

In Figures 1 (b) and 2 (b), why do Fourier UCB and Legendre UCB perform worse when they use only even functions and the true reward function is even? We thank the reviewer for noticing this subtle phenomenon. The reason stays in the true reward function: as it is a polynomial of degree 4, including in the feature map even polynomials of higher degree is as useless as including odd functions. In fact, as high-frequencies are more prone to overfitting the noise, the effect of including these features may be even worse than adding other useless components, as in this example.

We thank the reviewer for their comments and insightful observations and hope to have addressed all their questions.

Adaptivity on $s$. See common answer about adaptivity.

Assuming square-integrable derivative in practice. The setting of stochastic bandits has achieved relevant success in the field of pricing. In this area, bandit algorithms are used to optimize a function of the price $p$ given by $f(p):=p d(p)$ where $d(p)$ is an unknown function known as "demand curve", which is non-increasing in $p$ (ref. "Pricing the long tail by explainable product aggregation and monotonic bandits" by Mussi et al.). Of course, the differentiability of $f(\cdot)$ corresponds to the one of $d(\cdot)$, the demand curve, and since this function is decreasing and bounded in $[0,1]$, its derivative cannot be "too large too often". This can be formulated by asking that its derivative is square-integrable.

Infinitely differentiable functions. We agree with the reviewer that, being $\mathcal C^\infty$ included in $\mathcal C^s$ for every $s>0$, the algorithm from Liu et al., 2021 can achieve regret of order $\mathcal O(T^{1/2+\beta})$ for every $\beta > 0$ when the function is infinitely differentiable. The point is that UCB-Meta-Algorithm has to choose a number of features that depends on $\beta$ and diverges for $\beta \to 0$ (that algorithm relies on dividing the actions space in hypercubes and running a linear bandit algorithm in each hypercube. We refer to the number of features used by each of these linear bandits). Conversely, our algorithm uses fewer features the higher the value of $s$, and in particular, for $s=+\infty$, it can achieve regret of order $\sqrt T$ using the lowest number of features. This strange phenomenon makes the two algorithms complementary, with UCB-Meta-Algorithm being more suitable for large $d$ and small $s$, and our one for $d=1$ or $s=+\infty$.

Use of OB-LinUCB in the experiments. We made this choice based on the principle that, usually, algorithms that optimize the worst-case regret are not the best option in practice, where simplicity works much better. Coherently with this choice, we have compared our algorithm not with BPE, which achieves the best regret in kernelized bandits, but with IGP-UCB, which is well-known to have superior performance in practice regardless of the worse regret bound. In the end, if ever one of our algorithms has a hope to be used in practical scenarios, this is probably OB-LinUCB, which is the most natural marriage between a Linear Bandit algorithm and the orthogonal function representations. Still, we will implement OB-PE and let the reviewer have its result by the deadline of the discussion period.

Dependence of the regret bounds of OB-PE on the Lipschitz constant $L$. Thanks for the question, which opens up some reflections we hadn't considered. Our regret bound is roughly of order $R_T \le \mathcal O\left (\sqrt{N^d T}+LN^{d/2}N^{-s}T\right ),$ where $L$ is the Lipschitz constant of the $s-1$ derivative. With the optimal choice $N=L^{1/s}T^{1/2s}$ we get, in the regime $d<2s$ where we have regret guarantees, $R_T \le \mathcal O\left (L^{d/(2s)}T^{(2s+d)/(4s)}\right ),$ meaning that the dependence is $L^{d/(2s)}$ (which of course becomes vacuous for $d>2s$, when also the regret is unbounded).

Assumptions of Theorem 4. The different type of assumption reflects the difference in the type of analysis behind the result. In fact, given that the theory of Legendre polynomials has so far been developed only in one dimension, it is not possible to use it in the general case, and the argument used there does not make assumptions on the $(s+1)$-th derivative. This is linked to the reason why our analysis is sub-optimal for $d>1$.

We thank the reviewer for their comments and for identifying some typos in our paper. We hope we have addressed all of their concerns.

Paper organization The theory behind our algorithm is highly nontrivial for someone with a background different than mathematics. Therefore, we have decided to keep in the main paper the parts that are essential for comprehending the paper and leave the more advanced and subtle discussions in the appendix.

Novelty We acknowledge the reviewer's observation that our analysis relies heavily on theorems already established in the field of functional analysis. However, we disagree with the notion that this diminishes the novelty of our work. On the contrary, given that existing literature predominantly employs Kernel methods or focuses on finding a cover for the arm space, the utilization of a theory previously unexplored in this context should be regarded as a valuable contribution. Recent research in bandits on Reproducing Kernel Hilbert Spaces (RKHS) has revealed that performance guarantees are intricately tied to the decay properties of the eigenvalues of the kernel. In our study, we demonstrate (refer also to appendix E.2) that the same holds true for general continuous armed bandits. This suggests that, even if certain results in our paper fall short of optimality, the methods formulated here could be applied to extend many findings from the extensive RKHS theory to this specific setting.

Computational advantages where the d/s value to become significantly large See the common answer about computational complexity.

Adaptivity for values of $s$ and $T$ See the common answer about adaptivity.

Input requirement in this paper compared to existing research All the related papers, like ours, assume knowledge of both the time horizon $T$ and the order $s$ of differentiability. In particular, the four works on Bayesian optimization also presume working in a Reproducing Kernel Hilbert Space (RKHS) with a known kernel. Since the knowledge of the kernel directly determines the order of smoothness of the functions considered in the RKHS, their requirement is notably more stringent than ours.

We thank the reviewer for their comments and hope to have addressed all their questions.

We have incorporated the experiments suggested by the reviewers into the paper. The results of these experiments are available in the appendix, F.4. Specifically, we have added experiments with OB-PE on the environments of the paper, as well as an experiment in dimension 2.