Contextual Online Decision Making with Infinite-Dimensional Functional Regression

Thank you for your questions. We answer your questions in order.

RE:oracle ineq Oracle inequality provides an upper bound on the performance of the learning algorithm compared to an ideal benchmark ("oracle"), the best function in a reference class. A typical form is:

$L(\hat{f}) \leq L(f^*) + \text{complexity penalty},$

where $\hat{f}$ is the output of algorithm, $f^*$ is the best-in-class function, and $L(\cdot)$ denotes the loss. The additional term represents the complexity penalty.

Oracle Regret. In contrast, oracle regret is a concept from online learning. It measures the cumulative performance gap between the learner and the best fixed decision in hindsight:

$\text{Reg}(T) = \sum_{t=1}^{T} L_t(f_t) - \min_{f \in F} \sum_{t=1}^{T} L_t(f)$

where $f_t$ is the learner's decision, and $L_t$ is the loss function at time $t$. Oracle regret measures dynamic performance; sublinear regret means average vanishes as $T \to \infty$.

Therefore, oracle regret is not oracle inequality.

RE: oracle efficiency Our adaptive algorithm solves uncountable-dimension functional optimization problems efficiently by adaptive approximation with good statistical guarantee. ERM approach is intractable because it is practically impossible to optimize an infinite-dimensional functional optimization problem.

RE: confidence bound For confidence bound, please refer to Thm 3.6. This constructs a function confidence bound. For arxiv.org/abs/2002.04926, they assume access to abstract online oracle and is neither practical nor valid in our problem. Also, it only cares about mean reward setting, which is just a subclass of problems that we can handle.

RE: Boundness and Lipschitzness are both common assumptions in online learning. A lot of function classes are Lipschitz. All linear functions are Lipschitz; neural networks are Lipschitz (www.mit.edu/~rakhlin/courses/mathstat/rakhlin_mathstat_sp22.pdf). Our Lipschitz condition concerns parameter distance $||w - r||$ in the family.

$|\phi(x,a,r,s)-\phi(x,a,w,s)|\le L_0||w-r||_{\infty}.$

This assumption could be found in other papers, see arxiv.org/pdf/2007.07876, proceedings.mlr.press/v15/chu11a/chu11a.pdf.

The boundness assumption is common in online learning; see https://proceedings.neurips.cc/paper/2011/file/e1d5be1c7f2f456670de3d53c7b54f4a-Paper.pdf , arxiv.org/abs/1611.06426, arxiv.org/pdf/2106.03365, https://openreview.net/forum?id=F5TbbyTgbC. In finite dimensions, it assumes $\theta^*\in R^d$, $||\theta^*||_2\le S$.

Our contribution is not about ** relaxing these conditions.** Instead, we propose a framework for contextual online decision-making capable of a wide range of tasks, including bandits, online hypothesis testing, and risk-aware bandits. We design efficient regression oracle for infinite-dimensional functional regression. By spectral decomposition and eigenvalue truncation, we solve an infinite-dimensional function optimization problem efficiently by adaptive approximation. Combined with inverse-gap weighting, this oracle yields our algorithm.

Our theoretical contribution is that we provide characterization of the relationship between regret and the eigendecay rate of the operator by single parameter $\gamma$. This is the first regret bound for infinite-dimensional decision-making via eigendecay.

RE: Pseudo regret Pseudo-regret is trajectory-based and random; utility regret is its expected version which is common in literature.

RE: context and action space Our paper could handle arbitrary context space. We study finite action space purely for simplicity. arxiv.org/abs/2207.05836 can handle infinite action space because its reward model has a special structure.

To extend to infinite action space, we change the algorithm to a UCB-type algorithm to handle it, see arxiv.org/pdf/2007.07876. We define the following action divergence $V_x(a||\lbrace a_i\rbrace_{i=1}^{n})$ such that

$V_x(a||\lbrace a_i\rbrace_{i=1}^{n})\ge \sup_{\theta}\Big\lbrace\frac{|T(\langle\theta(\cdot),\phi(x,a,\cdot,\cdot)\rangle)-T(\langle\theta^*(\cdot), \phi(x,a,\cdot,\cdot)\rangle)|^2}{\sum_{i=1}^{n}(T(\langle\theta(\cdot), \phi(x,a_i,\cdot,\cdot)\rangle)-T(\langle\theta^*(\cdot), \phi(x,a_i,\cdot,\cdot)\rangle))^2}\Big\rbrace.$

This divergence is a UCB. At any round $t$, receiving context $x_t$, for $i=d_x+1,\cdots,t$, where $d_x$ is some parameter, we pretend all previous actions were applied at context $x_t$ and simulate the counterfactual action sequence by solving

$a_{ti} \in argmax_{a \in A} T(\langle \hat\theta_i,\phi(x_t,a)\rangle) + \beta_i V_{x_t}(a || [a_{tj}]_{j=1}^{i-1})$.

Then we apply $a_{tt}$. This algorithm can handle infinite action space with counterfactual action divergence. We will add this discussion to the camera-ready version. We believe we have addressed your concerns and hope that you will consider raising the score accordingly.

Thank you for your kind questions, and we would now like to answer your questions in order.

RE: Model Assumption 2.1 Thank you for your question. In machine learning, it is a common assumption to assume that the underlying true model lies in some known model class. This assumption is usually called the realizability assumption, and we follow this protocol. See arxiv.org/abs/2107.02237, arxiv.org/abs/2410.12713 ,arxiv.org/abs/2002.04926 . Thus, we assume that there is a basis CDF family $\Phi= \lbrace\phi(x,a,w,s)\rbrace_{w\in\Omega}$. The true distribution function is of the form $F^*(x,a,s)=\int_{\Omega}\theta^*(w)\phi(x,a,w,s)d\nu(w)$. As for the estimation oracle, this is our key contribution. Generally, estimating the true $\theta^*(w)$ is an infinite-dimensional functional optimization problem and is impossible to solve. However, by spectral decomposition in functional analysis and eigenvalue decomposition, we successfully developed an efficient estimation oracle.

With no prior knowledge about the model class, you can still estimate using any model class. In this circumstance, there will be two types of errors, the first type is approximation error induced by potential model misspecification. This is unavoidable because the assumption about the underlying true model is wrong. The second type is estimation error, which can be reduced by designing more delicate algorithms. In this paper, we assume a well-specified model class and focus on reducing the estimation error. In practice, considering storage space and computation, we can choose a moderate neural network class as model candidates. In this case, we will suffer from approximation error, and our paper provides a theoretical bound on the estimation error. By balancing computation and performance—where a larger network reduces approximation error but requires more resources—our work offers theoretical insights for practical applications. } For the storage and of such a distribution family, we can first view $\Phi$ just as a function of $x,a,w,s$. We could use a neural network to store and learn such nonlinear functions. For example, see arxiv.org/abs/2110.03177, arxiv.org/abs/2306.00242 , arxiv.org/abs/2305.03784 .

RE: Basis Family $\Phi$ Modeling the basis function family could be problem-driven, different tasks have different families. Generally, we use spline functions, trigonometric functions, truncated Gaussian mixtures, and the Bernoulli random variable mixture to model the basis distribution family in different applications. Please see arxiv.org/abs/2205.14545 for numerical details.

RE: Assumption 2.10 Thanks for your question. First, the eigendecay rate assumption is not a finite effective dimension assumption. The infinite dimension setting actually makes the traditional regret bound of online learning invalid. For example, in linear bandit papers with dimension $d$, often the optimal regret rate after $T$ rounds is $\mathcal{O}(\sqrt{dT})$, and if we let $d$ go to $\infty$, we incur an invalid regret bound.

Assumption 2.10 is a polynomial eigendecay assumption, which is common in many machine learning subfields such as kernel learning, deep neural network analysis arxiv.org/abs/2305.02657, and neural network learnability analysis arxiv.org/abs/1708.03708. Some even assumed an exponential eigendecay rate. We use a polynomial eigendecay rate to characterize the estimation error of our functional regression oracle. Our assumption is mild in comparison.

Regarding the question about $O(1/k)$ and $\Theta(1/k)$, we give a counterexample that a finite sum doesn't imply $O(1/k)$. For example, the series $a_i=\frac{1}{i^{2}}$ for $i\neq 2^{2j},\ j=1,2,\cdots$, and $a_i=\frac{1}{\sqrt{i}},\ i=2^{2j},\ j=1,2,\cdots$. Also, please see Prop 2.9 before jumping into Assumption 2.10. In Prop 2.9, we first prove that the sum of the eigenvalues is finite. Mathematically, this is called trace-class, so it is impossible that $\lambda_k=\Theta(1/k)$ as the sum would be infinite, which violates Prop 2.9.

The first line of 2.10 is that decay rate of sequence $\{\tau_k\}$ is strictly faster than $1/k$. For the second line, the first inequality says that the eigenvalue sequence of the operator could be dominated by $\{\tau_k\}$, which cannot be induced by the first line. The second inequality is a restatement of the third point in Prop 2.9, saying that the eigenvalues are dominated by the $\{\frac{1}{k}\}$.

RE: Technical Roadmap We will write a clear roadmap in the camera-ready version and improve the structure of our paper.

Please feel free to discuss with us any further questions. We hope our rebuttal has clarified the reviewer’s confusion and respectfully hope that the reviewer would consider re-evaluating the merit of our work accordingly.

Thank you for your kind remarks and questions, and we would now like to answer your questions in order.

RE: Minimax bound Thank you for your question. In the conclusion part, we actually point out that investigating the minimax lower bound of the regret with respect to the eigendecay rate is an important open question. Historically, people focus on finite-dimension cases and avoid discussing infinite-dimension cases. Our work directly extends the existing finite-dimensional problem to infinite dimension and we believe the eigendecay rate is an efficient tool to describe the learnability of infinite-dimensional models. Our conjecture is that we might be optimal. Nonetheless, it is out of the scope of this paper and is an important future direction.

RE: Our new contribution Our contribution lies in the following perspectives. We propose a unified framework for contextual online decision-making capable of addressing a wide range of tasks, including contextual bandits, online hypothesis testing, and risk-aware bandits. We design an efficient regression oracle for infinite-dimensional functional regression. By applying spectral decomposition and eigenvalue truncation, we solve an infinite-dimensional function optimization problem efficiently with adaptive approximation. Combining this functional regression oracle with inverse-gap weighting policy from contextual bandits, we can design our efficient sequential decision-making algorithm.

The key theoretical contribution of our paper is that we provide a rigorous characterization of the relationship between regret and the eigendecay rate of the operator, depicted by a single parameter $\gamma$. This is, to the best of our knowledge, the first result that characterizes the regret of infinite-dimensional general sequential decision-making by the eigendecay rate of the operator.

Thank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.

Thank you for your remarks and questions. We would now like to answer your questions in order.

RE: Squared-Integrability Thank you very much for your question! We point out that in many online learning settings such as finite-dimensional linear bandits [85, Abbasi-Yadkori, Yasin et al. (2011)] including non-stationary bandits [74, Zhao, Peng et al. (2020)], conservative bandits [73, Kazerouni, Abbas et al. (2017)], combinatorial bandits, [84, Liu, Qingsong et al. (2022)], differential privacy bandits [83, Han, Yuxuan et al. (2021)] square-integrability is always assumed. In these problems, square-integrability is presented as finite $2$-norm assumption $\theta^*\in R^d$, $||\theta^*||_2\le S$ for some $S$. Our assumption is an extension because the finite $2$-norm in infinite dimensional function space is square-integrability. Generally speaking, assuming no prior knowledge about model class, you can still estimate using any model class. In this circumstance, there will be two types of errors, the first type is approximation error induced by potential model misspecification. This is unavoidable and there is no way to reduce because the assumption about the underlying model is wrong. The second type is estimation error, this can be reduced by designing more delicate algorithms. In practice, you can use deep learning and neural network with strong expressive power to approximate the underlying function to reduce approximation error. In this paper, we assume well-specified model class and focus on reducing the estimation error.

RE: $\gamma$-intuition We explain the intuition of $\gamma$ from the following: First, the value of eigenvalue reflects the information in that direction, and larger eigenvalue means more information. Our $\gamma-$ eigendecay condition says $U_{D}=\sum_{i=1}^{\infty}\lambda_ie_i$, where $\lbrace\lambda_i\rbrace_{i=1}^{\infty}$ is eigenvalue sequence and we have $\sum_{i=1}^{\infty}\lambda_i^{\gamma}<s_0<\infty$. We design an adaptive truncation method based on the decay rate of eigenvalues to solve an infinite-dimensional problem. We achieve a utility regret rate of $\mathcal{O}(T^{\frac{3\gamma+2}{2(\gamma+2)}})$ for our algorithm. For small $\gamma$, the eigenvalue sequence $\{\lambda_i\}$ is decaying fast enough, so the information of this operator is concentrated in the first several largest eigenvalues. Therefore, our finite-dimensional eigenvalue truncation preserves most of the information stored in the original operator. So our regret $\mathcal{O}(T^{\frac{3\gamma+2}{2(\gamma+2)}})$ will be very good. If we assume no prior knowledge about the eigendecay rate instead, just use the trace-class property and set $\gamma=1$ also leads to a sublinear $O(T^{5/6})$ regret.

We finally remark that under mild conditions, polynomial eigendecay for integral operator could be rigorously proved and assumption 2.10 is satisfied. See Thm 4 in [47, Carrijo, Angelina O et al. (2020)].

RE:Examples Thanks for the question. We illustrate the mean as an example here. MV bandits and other applications could be derived similarly. For mean, functional $T$ is $T(F)=\int_{S}sdF(s)$. Then, $|T(F_1)-T(F_2)|=|\int_{S}sd(F_1(s)-F_2(s))|=|\int_{S}F_1(s)-F_2(s)ds|,$ Then by algebra,

$|\int_{S}F_1(s)-F_2(s)ds|\le \int_{S}|F_1(s)-F_2(s)|ds\le m(S)^{1/2}(\int_{S}|F_1(s)-F_2(s)|^2ds)^{1/2}=m(S)^{1/2}||F_1-F_2||_{L^2(S)}.$ This indicates that the decision-mapping is Lipschitz continuous with respect to our $L_2$ metric.

RE: Notation We use $F(x,a,s)$ to denote a distribution to show that we want to emphasize that the distribution is related to context action pair $x,a$. We will polish accordingly in the camera-ready version.

RE: Compare with [54, Zhang, Qian et al. (2022)] In [54, Zhang, Qian et al. (2022)], they use a regularizer which scales with the number of the sample points. The main difference is that in terms of the estimator in [54, Zhang, Qian et al. (2022)], they just used the fact that the sum of the eigenvalues of the operator is finite without the eigendecay rate characterization. We describe the behavior of the eigenvalue sequence in a more meticulous way and discover that the scaling regularizer is no longer needed. Instead, we can use the decay parameter $\gamma$ to depict the regret $O(T^{\frac{3\gamma+2}{2(\gamma+2)}})$.

Thank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.

[47] Approximation tools and decay rates for eigenvalues of integral operators on a general setting

[54] Functional linear regression of cumulative distribution functions

[73] Conservative contextual linear bandits

[74] A simple approach for non-stationary linear bandits

[83] Generalized linear bandits with local differential privacy

[84] Combinatorial bandits with linear constraints: Beyond knapsacks and fairness

[85] Improved algorithms for linear stochastic bandits