Contextual Online Decision Making with Infinite-Dimensional Functional Regression
Authors: Haichen Hu
Rui Ai
Stephen Bates
David Simchi-Levi
Venue: ICML 2025 poster (2025)
Keywords: Infinite-Dimensional Functional Regression
Contextual Decision-Making
Online learning
Bandits
Primary area: theory->online_learning_and_bandits
TL;DR: We propose a general framework to handle a wide range of sequential contextual decision-making problems, and proposed an efficient functional regression method combined with IGW policy to solve it.

Abstract: Contextual sequential decision-making is fundamental to machine learning, with applications in bandits, sequential hypothesis testing, and online risk control. These tasks often rely on statistical measures like expectation, variance, and quantiles. In this paper, we propose a universal algorithmic framework that learns the full underlying distribution, enabling a unified approach to all contextual online decision-making problems. The challenge lies in the uncountably infinite-dimensional regression, where existing contextual bandit algorithms all yield infinite regret. We innovatively propose an efficient infinite-dimensional functional regression oracle for contextual cumulative distribution functions (CDFs) and model every datum as a combination of context-dependent CDF basis functions. Our analysis reveals that the decay rate of the eigenvalue sequence of the design integral operator governs the regression error rate, and consequently, the utility regret rate. Specifically, when the eigenvalue sequence exhibits a polynomial decay of order $\frac{1}{\gamma}\ge 1$, the utility regret is bounded by $\tilde{O}( T^{\frac{3\gamma+2}{2(\gamma+2)}})$. The case that $\gamma=0$ can recover the existing optimal rate in contextual bandits literature with finite-dimensional regression and so as exponential decay. We also provide a numerical method to compute the eigenvalue sequence of integral operators, enabling the practical implementation of our framework.

Contextual Online Decision Making with Infinite-Dimensional Functional Regression
Haichen Hu
Rui Ai
Stephen Bates
David Simchi-Levi
Abstract
1. Introduction
Contextual sequential online experimentation has been over- whelmingly important for online platforms, healthcare com- panies, and other businesses (Tewari & Murphy, 2017; Saha et al., 2020; Beygelzimer et al., 2011; Avadhanula et al., 2022). A decision maker (DM) might face a wide range of tasks, and different tasks lead to various adaptive algo- rithm designs. For example, for maximizing the total reward, there are all kinds of contextual bandit algorithms (Chu al., 2011). For minimizing the total hypothesis testing error, have online hypothesis testing algorithms (Wei et al., 2007). To rectify a pre-trained machine learning model, many on- line calibration algorithms have been developed (Fasiolo et al., 2021).
Contextual sequential Docision-making is funda- mental to machine learning, with applications in bandits, sequential hypothesis testing, and online risk control. These tasks often rely on statistical measures like expectation, variance, and quantiles. In this paper, we propose a universal algorithmic framework that learns the full underlying distribu- tion, enabling a unified approach all contextual online decision-making problems. The challenge re-
lies in the uncountably gression, where existing contextual bandit algo- rithms all yield infinite regret. We innovatively propose an efficient dimente-dimensionall func- tional regression oracle for contextual cumulative distribution functions (CDFs) and model every da- as a combination of context-dependent CDF basis functions. Our analysis reveals that the de- cay rate of the eigenvalue sequence of the design integral operator governs the regression error rate, and consequently, the utility regret rate. Specif- ically, when the eigenvalue sequence exhibits a polynomial decay of order I 1, the utility re-
Some common structures appear be obscured behind these examples. At each round, the DM first receives some context, such past consumption records or symptoms in healthcare setting. Then, the DM chooses action apply according to this context and his objective. For example, in online hypothesis testing, the actions could be "reject" and "accept", while in contextual bandits, the action is to choose and pull an arm. Commonly, there is an underlying distribution Pz,a associated with every context x and action
a. The DM makes decisions based on the estimation of its various statistics. In the context of bandits, the primary statistic of interest is the expectation, whereas in risk control, attention is directed toward variance (Li et al., 2022; Füss et al., 2024). Please refer to Ayala-Romero et al. (2024); Bouneffouf (2016); Sun et al. (2016); Li et al. (2019); Han et (2021); Kong (2024) for more examples.
gret is bounded by ① (T The case that
Y = 0 can recover the existing optimal rate in con- textual bandits literature with finite-dimensional regression and so as exponential decay. We also provide a numerical method to compute the eigen- value sequence of integral operators, enabling the practical implementation of our framework.
The essential difficulty behind all these online decision- making examples is the uncertainty of the outcomes under different actions. In revenue management, the decision maker is not sure about the mean reward, while in financial portfolio management, he is mostly uncertain about both mean and variance (Gupta et al., 2021). Moreover, online quantile calibration, the key concern turns the unknown quantile function (Bastani et al., 2022).
'Center for Computational Science and Engineering, MIT, Cambridge, United States Depaarment of CEE, MIT, Cambridge, United States IInstitte for Data, Systems, and Society, MIT. Cam- bridge, United States *Department EECS, MIT, Cambridge, United States. Correspondence to: Haichen Hu <huhc mit.
Note that matter what kind of statistic we aim to know, as long as we learn the distribution Pr... the decision maker knows exactly how to make the decision. Therefore, it raises
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Contextual Online Decision Making with Infniit--iimensional Functional Regression
question:
2. Model setup and Operator Eigendecay
2.1. Model Setup
Is it possible consider more general (robust and adaptive) online decision-making setting based on infimite-dimensionall functional regression?
There are two main bodics of our framework, Functional Regression Model and Decision-Making Model. We first focus on the functional regression model.
Infinite-dimensional Functional-Regrrssion: Assume feature space X' and finite action space A X and action a, there
Specifically, we are looking for a general solution with infinit-diimessinall functional regression of cumulative dis- tribution functions (CDFs).
{a....., ax) For any context is an associated random variable Ya.- which takes values in some bounded Borel set S C R with m(S) 1, where m is some measure on the real line F. We assume Ya., has a cumulative distribution function F* (x, a, 8) satisfying the following Assumption 2.1 and Assumption 2.2.
Another motivation for considering dinnnie-adieniioalll models is the practical success of high-dimensional mod- els, such as AI products based on transformer architec- tures. Traditional minee-dimensional analysis fails to explain the strong performance of deep learning models. To fully address this challenge, our paper directly focuses on the infinite-dimensionall regression problem.
Assumption 2.1. We have access to a function family of CDF basis 4 = {ő(I, a, w, (), indexed by a com- pact set Ω C RR with d-dimensional Lebesgue measure v(2) = That is, given any x E X.a E A, w E Q 0 S (2, a, w. 8) S 1 is a CDF of some S valued random variable. For any x, a, there is an unknown non-negative coefficient function 0 e =L2(S,,)) v) such that
Roadmap: We present results in the following structure. In Section 1, we introduce our general sequential decision- making model with uninite-dimensionaa functional regres- sion. Then in Section 2.2, we introduce the mathematical concepts, tools, and assumptions in functional analysis and operator theory that are essential for our regression. In Section 3, we put forward an efficient algo- rithm to carry out the functional regression and establish its oracle inequality. We further present our sequential decision- making procedure (Algorithm 2) in Section 4 and prove its theoretical guarantee in theorem 4.1.
F* / 0 (w) a, w, s)du(w) s/
= (8 ()), ((),)((x,,.))))))))))))) a,,,))
We also set Sn 0 (w)) = 1 to ensure that F* s) is cumulative distribution function. For boundedness, we assume that |00 [0= S M for some constant M.
1.1. Related Works
The dimension of this functional regression problem is infi- nite, as the number of the functions in candidate model class I can be uncountably infinite, which makes solving this problem extremely hard. Modeling the basis model class & could be problem-driven; different tasks have different families. Generally, we use spline functions, trigonometric functions, truncated Gaussian mixtures, neural networks, and the Bernoulli random variable mixture to model the basis distribution family in different applications. Please see Zhang et al. (2022) for numerical details.
Our work is intimately related to the lines of work on con- textual bandits (Tewari & Murphy, 2017; Zhou et al., 2023; Zhou, 2015; Bouneffouf et al., 2020; Agarwal et al., 2014; Chu et al., 2011), operation learning (Mollenhauer et al., 2022; Kovachki et al., 2024; Adcock et al., 2024; Foster et al., 2018; Foster & Rakhlin, 2020) and functional gression (Morris, 2015; Ramsay& & Silverman, 2002; Zhang et al., 2022; Azizzadenesheli et al.; Yeh et al., 2023; Hou et al., 2023). Due to limited space, we discuss these and more related works in Appendix A.
Furthermore, we assume that the candidate model class t parametrized by the set Ω has Lipschiz-coontinitty with respect to E Ω. This assumption is common in learning theory (see Xu & Zeevi (2020)). Our goal in our functional regression model is to derive an accurate coefficient function estimation 0p.
Notation: For any measure space (B,B, n), we use (B, n) to denote the square-integrable function space which is also Hilbert space with inner product (..)) Jo (x))g())) (z))((())))))))))))))))))))))))) and norm [[ J). 0() and o()) stand for Bachmann Mochmannn-andau asymptotic notations up to constants. Meanwhile, Ô stands for the asymptotic notations up to logarithmic terms. For any E N, [n] de- notes the set [1,, and (t) denotes the indicator function {y < t}. Unless otherwise stated, when we write the eigenvalue sequence {A,}, is arranged in a decreasing order.
Assumption 2.2. 6lI, a, s) is Lo-Liscchitz continuous, (0 w, s) - (zz, a, r, s)1 - Tollw rllbo-
We now turn to our Decision-Making Model.
(S)) can be any finite number. Our m(S) assumption here just for notation convenience.
2

---

Contextual Online Decision Making with Infiiite-iimensional Functional Regression
Data D
reward distribution of arm a given context x. Consequently, T(F a, s)) is the mean reward of arm a given x, and we recover the contextual bandit problem.
Task T
We assume that the reward is bounded in interval S = [a, bj and illustrate that contextual bandits satisfy our model assumption in Section 2. Note that T(F) = xx)( and integrating by parts, we have that for any two CDFs Fi. F2.
Functional Regression
Decision Making Algorithm 2
Algorithm
Figure 1. Data D drives the functional regression and decision- making for statistical task T.
| Fi(s) F2(s)ds
(T(RR) ((F2))
To incorporate all the sequen- tial decision-making examples in framework, we assume that the objective of the decision-maker is relevant to the cu- mulative distribution function itself, rather than only some concrete statistics such as mean, variance, quantile and so on.
Decision-making Model:
- Fellea(s)
The inequality is by integrating by parts and Cauchy- Schwarz inequality. So contextual bandit satisfies Assump- tion 2.3 with constant L = (6 a)1/².
Example 2.5 (Sequential Hypothesis Testing (Naghshvar & Javidi, 2013)). M hypotheses {H,,... .Hr) are of in- terest, among which only one holds true. a, is to choose hypothesis H, to believe. For any true class H; and DM's judgment aj. there is a loss function ((H,,a3) az). The distri- bution associated with observation x and aj is the poste- rior distribution of the loss I with PMF denoted by F2,a; Fž,a, (IH,, a,)) P(H. [z. az). ((H,),aa)) ) is the poste- rior probability that H, is true given observation x and ag- T F + - Ss sdF(s) is the negative expectation func- tional, where the integral stands for the Lebesgue integral. From the deduction of Example 2.4, we know that sequential hypothesis testing satisfies Assumption 2.3.
To be specific, we assume that there is known utility func- tional T defined on function space (²(S,m)) m). At each round t, the context 24 is drawn i..d. from some unknown distri- bution Qx- Given any context if the DM applies action a, then one data point will be sampled and observed according to distribution function F* (x( a, 8), and the utility of action a under x is T(F* (ar a, s)). The goal of the decision maker to maximize the total utility in T rounds of interaction, i.e., max Ei=1 ((F"(1 s)).
Analogous to the bandit setting, the policy is map-
ping from the feature space X' to the action space prob- ability simplex A(A). Given any x. we denote a" (x) as the action that maximizes the utility, i.e., a"(x) = argmax, T(F (I,,u,)) s)). For any policy sequence (Te))= the performance measure is utility regret, which is the dif-
Example 2.6 (Mean- Variance (MV) bandits (Hu et al., 2022)). In multi-armed bandits (MAB), denote F; as the distribution of arm i. The mean-varianc, functional T F: + P. Fx) - (1 - p){ xxdF - (f (x)))) MV-MAB is about finding a policy that maximizes the total mean-variance Similar to Example 2.4, we illustrate that this example satisfies Assumption 2.3.
ference between the optimal policy x'" (x)- = (x)()) (.) and {T. [==)
Reg(f TT )Tm1)
T ((F ((P()))))))
(T(F)) T(F2)
Sp / sdFi - sdF2(s)
Assumption 2.3. The known functional T is L-Lipschitz continuous with respect to the norm ||- (S.m))
+(1 p)((- - a) //1 sdlFi (5) -1{ sd F2
Assumption 2.3 is essential since it ensures that an accurate estimation about the underlying distribution results in a good approximation of the corresponding utility functional value. Finally, we end this section with some practical applications and their corresponding utility functionals T and their Lipschitz constant T..
s (1- (1-p)(p--))))))))))00( p) a)) (6 (6-a)1/21155 - Fellea(S)-
Therefore, mean-variance bandits satisfy Assumption 2.3 with Lipschitz constant L = (p - (1 - p) a)) (b- a)2/2
It is intuitive that a good estimation of the underlying dis- tribution may result in good utility estimation. However, estimating the underlying CDF with an uncountable basis and arbitrary feature space is highly non-trivial. In Sec- tion 2.2, we would like to introduce some tools and as- sumptions from the functional analysis and operator theory community before we dive into our regression oracle. For
Example 2.4 (Contextual Bandits). Define the functional as T: F (x), which is known functional in terms of F. Given any context x, F* (x, a, s) is the conditional
$8, is the Dirac function of a, i.e. (x) only if x=a, otherwise, (z) =0 =0
3

---

Contextual Online Decision Making with Infinite-Dimensioonl Functional Regression
background knowledge of operator theory and functional analysis, please refer to some texthooks Conway (2000); Kubrusly (2011); Simon (2015).
where (C > (2(( 2...>> 0 and (C + 0. The eigenvalues and eigenfunctions play crucial role in our algorithm and analysis. Hence, we further examine them and state additional properties below. All proofs are deferred to Appendix C.
2.2. Operator Eigendecay
Recall that in Section 2.1, we invoke the infinite- dimensional online decision-making problem, which makes the ditteeddmeesionll linear algebra analysis invalid. There- fore, we turn to functional analysis and operator theory in infinit-diimensional spaces to handle our learning problem instead. One core object of the intersection regarding func- tional analysis and learning theory is the operator, which is intrinsically defined as mappings from infiitt-diimeniioaal spaces to a very powerful tool to study the properties of many oper- ators, especially Hilbert- Schhmit operators, is their eigen- value and eigenfunction sequences. Specifically, in this pa- per, we care about the decay rate of the eigenvalue sequence (eigendecay). which is the essential factor that determines our approximation accuracy (theorem 3.6) and utility regret bound (theorem 4.1). In this subsection, we present all the mathematical concepts, theorems, and assumptions regard- ing the eigendecay rate of several important operators which will be utilized in Section 3.
By Gohberg et al. (2012); Ferreira & Menegatto (2013), we call the Hilbert-Schhite integral operator _ traceable if E (c < co. For any traceable operator, we could analyze the decay rate of its eigenvalue sequence, and the eigenvalue decay rate of these integral operators has been well studied in functional analysis (Ferreira & Menegatto, 2013; Volkov, 2024; Levine, 2023; Carrijo & Jordão, 2020).
Specifically, for our integral operator L we observe the following properties.
spaces. In functional analysis,
Property 2.9. For any I, the integral operator 2 satis- fies
Ei (: = Sn Is o(I, a, w. dddm))ddu(()) s 1.
. anyany i, 3,' 0 such that (c S
(((=))==(t))
For many concrete integral operators, Property 2.9 could be further strengthened and the decay rate of the eigenvalue se- quence could be established. For example, one might show polynomial eigendecay and even exponential eigendecay (Carrijo Jordão, 2020). Intuitively, a larger eigenvalue implies that more 'information' is stored in the direction of the corresponding eigenfunction. Therefore, faster decaying of the eigenvalue sequence means that more 'information' is concentrated in several large eigenvalues and the corre- sponding eigenfunctions. In this paper, we use a single positive parameter 7 in Assumption 2.10 to describe the decay rate of the eigenvalue sequence and characterize this phenomenon, which is called 7-dominating eigendecay.
Definition 2.7. For any (w,r) E Ω2 x Q define the following linear integral operator, integral kernel, and mapping:
// [ (0)),,,, a,, a.))
n
Kea (w,r) + /
ar (0,,v) x 5 + R. (0,s) (0()) (12, a,),)
By Fubini's theorem, we have
Assumption 2.10 (7-dominating eigendecay). Denoting all the bounded linear operators on L2( v) as B(L v)), we assume that the set {L : x E X,a E A) C (SL v)) is convex and satisfies the existence of se- quence {T: } such that
Vu E f2 L (r)((0)w)= / (()) (())==((
In
ol w, s) t)dm(s).
Theorem 2.8. For any E X and E A, L is compact, linear, positive and self-adjoint Hilbert-Schmidt integral operator with |[ < 1.
for some < <<75 S and so 00, E 7/ so,
for Va, a, (C < S O+), Vk.
By the Riesz-Schauder theorem and the spectral decom- position theorem (Reed & Simon, 1978), if we denote (M(C))=a))) J==1 its eigenvalue sequence in decreasing or- der and (c,(())))) as the corresponding eigenfunctions, then it holds that
We name the sequence {m. 1 as "7-dominating sequence". Intuitively, Assumption 2.10 states that the decay rate of the eigenvalue sequence of any operator L in the integral operator set {C : I E X, a E A} could be "dominated" by some polynomially converging series. The rate parameter ty is a key factor in our analysis. In Section 3, we will prove that parameter y influences the error rate of the functional
(0) = Σ Ax(C (0, ((x.a)) e (C.0)
4

---

Contextual Online Decision Making with InfiiteeDiimensional Functional Regression
regression oracle and therefore determines our utility regret rate.
Definition 3.2. For any small number 0, the truncated integral operator Üre is defined as
Finally we remark that our assumption in Assumption 2.10 essentially claims that the eigenvalue sequence {Ax} J decays with a polynomial order in magnitude. It is quite common to assume polynomial or even exponential eigendecay rate of large matrix or neural network operators (Yeh et al., 2023; Vakili & Olkhovskaya, 2024; Goel Klivans, 2017:
No.
UD 0
(,((D) (0, (np) e'o
where ND. is the smallest number such that for Vi 2 ND.: + >;(U(D) < ne.
Agarwal & Gonen, 2018).
is some hyper-parameter which will be determined later. Since we arrange the eigenvalues in a decreasing order, we have that for Vi < N, (1(D)) 2 ns. Despite the fact that UD is not invertible, it is still possible to define its pseudo- inverse as follows.
3. F Functional Regression and Oracle Inequality
3.1. Functional Regression
Definition 3.3. The pseudo-inverse of the operator Ü'D defined
In Section 3.1, we provide method about how to esti- mate our coefficient function 0* (w)), given dataset D {(2), (y,8,) Here, Vj is sampled according to CDF F* (Z(.
ND.
(0, (0, E üb. : + Σ (.((D)
The intuition of functional regression oracle is to use the operator's spectral decomposition. In ordinary least squares regression min| - the normal matrix X X plays a crucial role (Goldberger, 1991). Here, we require an operator that behaves similarly.
We set E Ex n to conduct functional regression. With a bit of abuse of notation, we also use N denote ND.r, and abbreviate U,D.:..1p,. as Üh and Un.
After obtaining Üp and 7hz there are two remaining steps of our functional regression. The first step is to compute the following function:
Definition 3.1 (Design Integral Operator). For any given dataset D= = {(Ty, az })));"= whose [D] = n, we define the design integral operator Up as Vu Ω
0p ub (1.5 Mns (1)0(2) aj, w, w, 8 s)dm(s)
(D)
Σ
F (w)
1=1
The motivation for calculating it lies in its ability to solve the following least squares optimization problem presented in Theorem 3.4. Intuitively, for any data point (z,, a,). the un- derlying targeted distribution function is J (x;;,,, Ja (w))(z (z,, as w. s)dv(w). Normally, to learn the function 0* (w), we need to observe the whole function F" (zz, a,, 8) = Sa 0" (w))(I; a4, s,))dv(w) and solve an inverse problem to obtain 6*. However, due to our bandit feedback nature, we only have one sample ys from this distribution. Thus, considering the I,2 error between the real empirical counterpart ly, (t) and any candidate distri- bution function Sqz 0 ((W))(zz (Z4, a,, w, s) s)dv(w) for all n data points, we obtain the following loss function ((0, D) in The- orem 3.4.
n
Σ
(r
(w,r)(vr))
1=
Moreover, we denote the spectral decomposition of Up as EES )
Using Theorem 2.8, one could verify that Up is also linear, positive, self-adjoint and Hilbert-Schmidt integral operator. Therefore, we have (2(Up) + O, and Up is not invertible.
In finit-ddimenional regression, people often handle non- invertibility with regularization terms >| leading to an eтror that scales with the problem dimension. However, since our dimension is infinite, adding this regularization term is infeasible. Zhang et al. (2022) considers differ- ent data-driven regularization, but the term will scale with the cardinality |D| = n, thus it's inapplicable to obtain convergence results.
Theorem 3.4. We define the loss function 1(0 D) on dataset
D as
1(0 2 E1In [I,)(()) (1)) ((w))(o) a, w. ()dv(w)li I[ (s,))
Rather than regularization, we consider a truncation of the function series Σi A(UU))e' according to the eigen- value sequence {}:(M))}} Specifically, we define the trun- cated finite rank operator Ü.D.-
1=1
Then, OD solves the following optimization problem,
P):
min 0ESpan(es.r ,x..)) 1(0,D),
(1)
5

---

Contextual Online Decision Making with Infiiite-iimensional Functional Regression
where Span(X) ( denotes the linear subspace spanned by the vector group X.
given, whereas the second one is for the random design that { a:) ]== are sampled from some unknown joint distribution Q.
After obtaining 0D. in order to ensure that our estimated coefficient function satisfies Assumption 2.1, we project it onto the set C = {0= 2 0: Sn Odv = 1, 1,110]la?(0..) S ) in the following norm.
Theorem 3.6. Under Assumption 2.1 and Assumption 2.10, given dataset 'D = {(zz, "j, 85) and setting E"
n *ें then with probability at least 1 - 6, the estimated coefficient function OD from Algorithm I satisfies
Definition 3.5. We define the following norm for any posi- tive self-adjoint bounded linear operator Ut
110 - 1110 S EZf(n)
|00 - (8))
N₂ Loog(1 + x:((4))) + + 0
1
2
2 2log
Correspondingly, we define the projection Po onto set C under the norm Ilke
Theorem 3.6 provides theoretical guarantee about our regression error when the given D has cardinality [D] = n. Nevertheless, Theorem 3.6 cannot be directly used, as there exists an agnostic term Σnn log(1 + >x((()) related to the dataset D. The following important lemma gives us an upper bound of (n) which is independent of D.
PD(x) argmin l1y x upp
VEC
The second step is to project OD onto set C by Pp. i.e., 0p - PP((O)) This process yields our estimated coefficient function 0p. At the end of this section, we summarize the functional regression oracle FuncReg in Algorithm 1.
Lemma 3.7. For any dataset D { at ys y:)) whose DD] ni by choosing E = = 742 we have
Algorithm 1 Regression Oracle: FuncReg
Basis function family {ø(I, a, w, w)e dataset D = { at ye M= (T))p 0 < S11
Require:
(n() 1 2
2 2 σ
1 + >
N.-
log(1 + + + M
Define the integral operator
(n) & 2 log (1/5) + (2v so log(1 + + M) n
Ub(0)(w)
j=1
With Lemma 3.7, we derive the following corollary which is independent of D.
n
Σ
(w. j=1
Corollary 3.8. Under Assumption 2.1 and Assumption 2.10, given dataset D = {(z,, {z 9;)1, and setting E" n オサं then with probability at least 1 - 6, we have |00 1l S (n).
Compute the spectral decomposition Up" say
uD(0) Σ A (0))))
When the data points are sampled i.i.d. according to some distribution, we could further give an oracle inequality for random design. Taking into consideration, our oracle inequality for random design helps to bound the I error between the ground truth CDF and our estimated CDF.
Define s* n - and construct the truncated operator Up and its pseudo-inverse UhD according to Definition 3.2 and Definition 3.3.
Solve the optimization problem and obtain solution 0p. Compute the projection Op = (D(0))
We first state some mild assumptions in random design. Assumption 3.9. We assume that for any I, W,T, there exists a constant n > 0 such that K=*(ww,) r) = S ő(x a, w, 8) s)Ø(2, 0, ss)m(s) 2 21 > 0.
Return: Øp.
Assumption 3.9 plays a role in guaranteeing the integral operator will not map a function far from 0 L²( v) to some near-zero point, which is bit similar to the concept of proper mapping in convex analysis (Magaril-II' yaev & Tikhomirov, 2003). With Assumption 2.1, we know that
3.2. Oracle Inequality
In this section, we give two versions of oracle inequalities. The first one is for the fixed design that D is arbitrarily
Ω x is also compact in R2d Thus, we have A (t ft, ||. 2d
'We present conerete numerical method to compute eigenval- ues in Appendix
|1xc) S (2)2d for some number A, delayed to Lemma B.9.
6

---

Contextual Online Decision Making with InfiiiteDiimensional Functional Regression
We finally transfer the estimation error of Öp to the L error between cumulative distribution functions,
Theorem 4.1. Given some dataset D {( ag 11 3))
where (2z, i.d.d ~ Q, we define Fo a) & Ja ( a, w. s)dv(w) our estimated cumulative distribution function. For any 0 < 8 < 1, we have that with probability at least 1 ò.
100 1
(Op 0- ,UD (0D - (bb-0))
Σ T 0", ,, (oo- 1p--0 -0-))
T B (1) ((F
Σ / Ieals
X.ASS / (1/ (0D - 0+) (w))b(ss aj w. s s)du(())
1d To, 8/2, A. Es/22))
x (1/ (00 @0 -0) (r)a(I). ag s)du(r) dm((s)
where
C(d, Lo.,,o. 8/2. = (48
"
Σ [I)o()))),s) (2) - az, () ())p(m))))
+ (
Consequently, combining Theorem 3.6 with some concen- tration analysis and Lemma 3.7, we have the following theorem.
We use Ents(n) to denote Lo, ()) there- after. For any 2, a, we could view T(F a, 8)) as the unknown expected "reward" related to action given con- text x. Therefore, we transform our abstract sequential dccision-making problem into a stochastic contextual bandit problem. Although in our problem, at every round, we do not directly observe sample point from the "reward" dis- tribution, could still estimate it by functional regression FuncReg, yielding the desired reduction from the sequential decision-makee problem to a contextual bandit.
ajj "j.,;)}" D=) Theorem 3.10. Given some dataset 'D = ((1),
where Mi) i..d Q we define Fo(x,,, a) A Ja. ( a, w, (w) to be our estimated cumula- tive distribution function under 2, a. For any 0 < 8 < 1/2,
we have that with probability at least 1 25,
Begaain [I - (
Old, Lo, 8, (n))
We summarize our algorithm in Algorithm 2. For the al- gorithm structure, we first divide the whole rounds into several epochs and geometrically increase the length of ev- ery epoch so that the low-frequency oracle call property is automatically satisfied in Algorithm 2. At the beginning of every epoch m, we call our functional regression ora- cle FuncReg based on the i.i.d. data gathered from the last epoch to get an estimation θ... We then design our inverse gap weighting policy Tm based on O. and execute it throughout this epoch. By such a structure, we could ensure that the data generated throughout this epoch are i.i.d. so that we can use Theorem 3, 10 to bound the L estimation error, and therefore the utility regret.
n
where
C(d,, Lo, 8, A,
= =(1+ (Togg(lo(( + 2//og(11/ (10((1)))/1)
is some constant that does not influence the 2 error rate with respect to n.
4. Algorithm
We provide algorithm in Section 4 that incorporates our functional regression oracle to minimize the expected utility regret.
To be specific, we first impose epoch schedule Tm = 2 which means that the (m + 1)-th epoch is twice as long as the m-th epoch. Therefore, the statistical guarantee we get from epoch + 1 is stronger than that of epoch m.. As m scales, our estimation becomes more and more accurate. The Inverse Gap Weighting policy enables us to balance the exploration and exploitation trade-off to maintain a low re- gret just assuming access to an offline regression oracle with i.i.d. input data. We now provide the theoretical guarantee of our Algorithm
is computationally expensive to calculate eigenvalues and corresponding eigenfunctions of an integral operator. Hence, is desirable to develop algorithms with a low-frequency oracle call property. Inspired by Simchi-Levi & Xu (2021); Qian et al. (2024), design Inverse Gap Weighting policy in batched version possessing the low-frequency oracle call property.
follows.
Before delving into the specific algorithm, the following statement indicates that a well-bounded estimation error implies well-bounded decision-making error.
Theorem 4.2. For stochastic context setting. assuming that we can only call functional regression oracle [log(T)]
7

---

Contextual Online Decision Making with Infinite-iimensionnl Functional Regression
Algorithm 2 Stochastic Contextual Decision Making with Infinite Functional Regression
is closer and closer to the vT order, which matches the traditional optimal regret rate. If the eigenvalue sequence is decaying exponentially fast, then it is also decaying poly- nomially fast for any positive y > 0. Thus. by choosing
Require: Functional T, feature space X, action space A {a1 ... ;okk basis function family {ó(2, a, w, w)eee regression space (2(), v), range space of random variables (5, m)
? O, we conclude that the regret rate has order Ö (T)) for any exponentially decaying eigenvalue sequence. More- over, for lmnttedimennsion problems, could imagine that all the eigenvalues with an index larger than the dimension number are zero. So, we can also set 0 in Theorem 4.2 and recover the optimal regret rate ( up to some logarithmic factors.
Initialize epoch schedule Eo < EΙ < E2 <..
for m 1.2, do
Obtain On E v), from oracle FuncReg with dataset m = {Iir ae, ye) 2+1
py. FuncReg(Dmmi)..
On the other hand, if we have no prior knowledge about the order of the dominating sequence {T: but just know that it converges, sublinear regret OTTS/0), as shown in Corollary 4.3.
Define
exploration
parameter (for epoch 1, 51 = 1).
Sm
simply set it to 1 and still achieve
K
Ests/2m 3 (Tm Tm
for Round 1 = 5m-1 1...,,. S. do
Corollary 4.3. For the dominating sequence { we only have information that it converges without any knowl- 37+2
Observe Zt.
Compute the value of functional for every action
edge of the order 7, we can set y = 1 and get 2(++2) Therefore, we could obtain the following expected regret bound:
Um (a) - T( 0m u. Va A.
Lo, (1ob ( (M) +M) o (r log(logTT6))
[[[Re(T))
Define IGW... sm. policy:
1 K+ K+sm (Knsm(FFaee (an 11 Eafā, Pt (a)
for all a + am for om.
pe(a)=
In summary, our algorithm is adaptive and robust. It not only recovers the optimal regret rate in finite-dimensional problems and
Sample at ~ Pt and observe one data point from cumulative distribution function F (I(, dc,s).
problems with exponen- tial eigendecay but can still manage to achieve a sublinear regret with no prior information about the eigendecay rate as well. These properties demonstrate the versatility of our algorithm and its broad potential for application.
end for end for
We finish this section with remark that in the design of Al- gorithm 2, we do not involve any information about the total round number T. If we know T in advance, we could further have a more efficient epoch schedule that reduces the offline functional regression oracle call times from Olog T') to (log log T) (Simchi-Levi & Xu, 2021; Qian et al., 2024).
times, then with probability at least 1 - 8, the expected regret of Algorithm 2 after T rounds is at most
E[Reg(T)) SŌ(K, L, Lo, L, A, (1s) + +))1) o (Iog(log T18) (VT+TTAT
37+2
where ČAA, K, L, Lo. n) is some constant that is only relevant to the parameters in the bracket.
5. Conclusion and Discussion
In this paper, we establish general framework for stochastic contextual online decision decision-making with infinite- dimensional functional regression, which incorporates any application examples with Lipschitz continuous objective functionals. We study the relationship between the util- ity regret and the eigenvalue sequence decay of our de- sired integral operator. Compared with minee-dimensional linear bandits, this connection is new and crucial in func- tional regression with infinite dimensions. Furthermore, we design a computationally efficient algorithm to solve our sequential decision makiin problem based on a novel infiiitedimmeniional functional regression oracle.
As < 7 < the term VT dominated by T 20 and regret rate becomes
o (6 (18 1/2 + +) v1 T 13
(log(log T/6)))
where Ō= LCK Add,1)
From Theorem 4.2, we observe that the regret rate is deter- mined by the decay speed of the eigenvalue sequence and we present a numerical method to compute these sequences in Appendix F. Specifically, when ? Y O, our regret rate
8

---

Contextual Online Decision Making with Infinite-iimensionnl Functional Regression
Finally, would like discuss some interesting future research directions and leave these interesting questions as potential next steps.
lations for bounded operators. Chapman and Hall/CRC. 2001.
Avadhanula, V., Baki, O. A., Bastani, H.,, Bastani, O., Goe- men, C., Haimovich, D., Hwang, D., Karamshuk, D., Leeper, T.,, Ma, J., et al. Bandits for online calibration: An application to content moderation on social media platforms. arXiv preprint arXiv:221 2022.
Extension to adversarial contextual The epoch of Algorithm 2 designed for lower computation cost, through the low-frequency algorithm call property, of computing eigenvalues and eigenfunctions in our functional regression oracle FuncReg. We observe that the guarantee provided by our oracle in Theorem 3.6 inherently adapts to any dataset where the contexts are arbitrarily drawn. This raises a natural question: can we design an efficient online functional regression oracle (Foster & Rakhlin, 2020), built on Algorithm 1, to address adversarial contextual decision- making problems?
Ayala-Romese J. A., X. Risk-aware continuous control with neural contex- tual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20930-20938, 2024.
A., and Costa-Perez,
Azizzadenesheli, K., Lu, W., Makur, A., and Zhang, Q. Sparse contextual edf regression. Transactions on Ma- chine Learning Research.
22 Minimax lower bound: our paper, the utility regret rate
An interesting open question is whether this dependency " is optimal. is worth future exploration into the minimax lower bound of the utility regret with respect to the eigenvalue decay rate y
ÖT (())))
Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Practical adversarial multivalid confor- mal prediction. Advances in Neural Information Process- ing Systems, 35:29362-29373, 2022.
Extension to nonlinear functional regression: In our problem, the relationship between F (2;, a, s) and & {ō(I, a, w, {) wen is linear because of the linearity of inte- gration. One challenging problem is to extend our method- ology to some potential nonlinearity between Fx (I, a, 8) and our basis function family and design efficient decision- making algorithms.
Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, R. Contextual bandit algorithms with super- vised learning guarantees. In Proceedings of the Four- teenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Confer- ence Proceedings, 2011.
Bouneffouf, D. Contextual bandit algorithm for risk-aware recommender systems. In 2016 IEEE Congress on Evolu- tionary Computation (CEC), pp. 4667-4674. IEEE, 2016.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bouneffouf, D., Rish, I., and Aggarwal, C. Survey on appli- cations of multi- and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), pp. 1-8. IEEE, 2020.
References
Carrijo, A. and Jordão, T. Approximation tools and decay rates for eigenvalues of integral operators on general setting. Positivity, 24:761-777, 2020.
Adcock, B., Brugiapaglia, S., Dexter, N., and Moraga, S. Learning smooth functions in high dimensions: from sparse polynomials deep neural networks. arXiv preprint arXiv:2404.03761, 2024.
Chatelin, F. The spectral approximation of linear operators with applications to the computation of eigenelements of differential and integral operators. SIAM review, 23(4): 495-522, 1981.
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: fast and simple algo- rithm for contextual bandits. In International conference machine learning pp. 1638-16466 PMLR, 2014.
Chatelin, F. Spectral approximation of linear operators. SIAM, 2011.
Agarwal, N. and Gonen, A. Effective dimension of exp- concave optimization. arXiv preprint arXiv.1805.08268, 2018.
Chu, W., Li, L.,, Reyzin, L.,, and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-2042214 JMLR Workshop and Conference Proceedings, 2011.
Ahues, M., Largillier, A., and Limaye, B. Spectral compu-

---

Contextual Online Decision Making with Infinite-Dimensional Functional Regression
Conway, J. A course in operator theory. American Mathe- matical Sociery, 2000.
Hou, B., Sanjari, S., Dahlin, N., Bose, S., and Vaidya, U. Sparse learning of dynamical systems in rkhs: An operator-theoretic approach. In International Conference on Machine Learning, pp. 13325- 13352. PMLR, 2023.
Fasiolo, M., Wood, N., Zaffran, M., Nedellec, R., and Goude, Y. Fast calibrated additive quantile regression. Journal of the American Statistical Association, 116(535); 1412-1412, 2021.
Hu, H., Charpentier, A., Ghossoub, M., and Schied, A. Multiarmed bandits problem under the mean-variance setting, arXiv preprint arXiv:2212.09192 2022.
Ferreira, and Menegatto, V. Eigenvalue decay rates for positive integral operators. Annali di Matematica Pura ed Applicata, 192(6): 1025-10142 2013.
Kohn, W. Improvement rayleigh-ritz eigenfunctions.
SIAM Review, 14(3):399 419, 1972.
Foster, D. and Rakhlin, A. Beyond ucb: Optimal and ef- ficient contextual bandits with regression oracles. In International Conference Machine Learning, pp. 3199- 3210. PMLR. 2020.
Kong, Y. Peer expectation in robust forecast aggre-
gation: The possibiltyimpossibiity. arXiv preprint arXiv:2402.0600 2024.
Kostenko, A. Trace ideals with applications (lecture notes).
Foster, D., Agarwal, A., Dudík, M., Luo, H., and Schapire, R. Practical contextual bandits with regression oracles. In International Conference Machine Learning, pp- 1539-1548. PMLR, 2018
Kovachki, N. B., Lanthaler, S., and Stuart, A. M. Oper- ator learning: Algorithms and analysis. arXiv preprint arXh::2402.157/55 2024.
Füss, R., Glück, T., Koeppel, C., and Miebs, An averaging framework for minimum-variance portfolios: Optimal rules for combining portfolio weights. Swiss Finance Institute Research Paper, (24-10), 2024.
Kubrusly, C. S. Elements of operator theory. Springer, 2011.
Levine, M. On the decay rate of singular values of integral operators. PhD thesis, Master's s thesis, WORCESTER POLYTECHNIC INSTITUTE, 2023.
Giné, and Nickl, R. Mathematical foundations of infinite- dimensional statistical models. Cambridge university press, 2021.
Li, B., Wang, Q.. Yu, Y., Sun, M.-Z., Chen, L.-X., Xiang, Z.- I.., Zhao, F., Lv, Q.-C., and An, 7.-Y. A novel risk-control model for the online portfolio selection of high-frequency transactions. Knowledge-Bac -Bsee Systems, 240:108176 2022.
Gnaneshwar, N. A degenerate kernel method for eigenvalue problems of compact integral operators. Advances in Computational Mathematics, 27:339-354, 2007.
Goel, S. and Klivans, A. Figenvalue decay implies polynomial-time learnability for neural networks. Ad- vances in Neural Information Processing Systems, 30, 2017.
Li, S., Li, X., Wang. X., and Liu, J. Sequential hypothesis test with online ssage-constrained sensor selection. IEEE Transactions on information theory, 65(7):4392 4410, 2019.
Gohberg, I., Goldberg, S., and Krupnik, N. Traces and determinants of linear operators, volume 116. Birkhäuser, 2012.
Magaril-II' yaev, G. and Tikhomirov, V. Convex analysis: Theory and applications. Translations of Mathematical Monographs, 2003.
Goldherger, A. course econometrics. Harvard Univer- sity Press, 1991.
Mollenhauer, M., Mücke, N., and Sullivan, T. Learning linear operators: Infiniteddimensional regression well- behaved non- compcct inverse problem. arXiv preprint arXiv:221 122211.08880 100885, 2022.
Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. Online multivalid learning: Means, moments, and prediction intervals. arXiv preprint arXiv:2101.01739 2021.
Morris, J. S. Functional regression. Annual Review of Statistics and Its Application, 2(1):321-359, 2015.
Han, Q., Ruan, S., Kong, Y., Liu, A., Mohsin, F., and Xia, L. Truthful information elicitation from hybrid crowds. arXiv preprint arXiv:2107.1011 2021.
Naghshvar, M. and Javidi, T. Active sequential hypothesis testing. THE ANNALS of STATISTICS, pp. 2703-2738, 2013.
Hoeffding, W. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffd- ing, pp. 409 426, 1994.
Panigrahi, B. L. Galerkin methods for eigenvalue problem of an integral operator with logarithmic kernel. The Journal of Analysis, 25(2):235-255 2017.
10

---

Contextual Online Decision Making with Infniite-iimeniional Functional Regression
Qian, J., Hu, H., and Simchi-Levi, D. Offline oracle-efficient learning for contextual mdps via layerwise exploration- exploitation tradcoff. arXiv preprint arX1v:2405.17796 2024.
Wei, W., Suh, K., Wang, B., Gu, Y., Kurose, J., and Towsley, D. Passive online rogue access point detection using se- quential hypothesis testing with tep ack-pairs. In Proceed- ings of the 7th ACM SIGCOMM conference on Internet measurement, pp. 365-378, 2007.
Ramsay, J. O. and Silverman, B. W. funciin, analysis: methods and case studies. Springer, 2002.
functional data
Xu, Y. and Zeevi, A. Upper counterfactual confidence bounds: new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07877 2020.
Ray, S. S. and Sahu, P. Numerical methods for solving fredholm integral equations of second kind. In Abstract and Applied Analysis, volume 2013, pp. 426916. Wiley Online Library, 2013.
Ych, S.-Y., Chang, F.C.,, Yuch, C.-W, Wu, P.-.,, Bernac- chia, A., and Vakili, S. Sample complexity of kernel- based q-learning. In International Conference Arti- ficial Intelligence and Statistics, pp. 453 469.469, PMLR, 2023.
Reed, M. and Simon, B. IV: Analysis of Operators, volume 4. Elsevier, 1978.
Saha, A., Gaillard, P., and Valko, M. Improved sleeping bandits with stochastic action sets and adversarial rewards. In International Conference on Machine Learning, pp. 8357-8366. PMLR, 2020).
Zhang, Q.. Makur, A., and Azizzadenesheli, K. Functional linear regression of cumulative distribution functions. arXiv preprint arXiv:2205. 14545, 2022.
Zhou, L. A survey on contextual multi- bandits, arXiv preprint arXiv:1500 03326, 2015.
Shalev-Shwarzz, S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Zhou, T., Wang, Y., Yan, L.., and Tan, Y. Spoiled for choice?
personalized recommendation for healthcare decisions: A multiarmed bandit approach. Information Systems Research, ((()::493-1512, 2023.
Simchi-Levi, D. and Xu, Bypassing the monster: faster and simpler optimal algorithm for contextual bandits un- der realizability. Mathematics of Operations Research, 2021.
Simon, B. Trace ideals and their applications. Number 120.
American Mathematical Soc., 2005.
Simon, B. Operator theory, volume 4. American Mathe- matical Soc., 2015.
Sion, M. On general minimax theorems. 1958.
Sun, W. Dey, D., and Kapoor, A. Risk-aware algo- rithms for adversarial contextual bandits. arXiv preprint arXiv:1610.0511 2016.
Teschl, G. Mathematical methods in quantum mechanics, volume 157. American Mathematical Soc., 2014.
Tewari, A. and Murphy, Contextual bandits in mobile health. Mobile health: sen- sors, analytic methods, and applications, pp. 495-517, 2017.
From ads interventions:
Vakili, S. and Olkhovskaya, J. Kernelized reinforcement learning with order optimal regret bounds. Advances in Neural Information Processing Systems, 36, 2024.
Volkov, D. Optimal decay rates sobolev norms for singu- lar values of integral operators. Journal of Mathematical Analysis and Applications, 537(2): 2024.

---

Contextual Online Decision Making with Infinite-Dimensional Functional Regression
A. Related Works
Contextual Bandits Contextual bandits have been widely studied in both academia and industry, including applications such as recommendation systems (Tewari & Murphy. 2017) and healthcare (Zhou et al., 2023). Please refer to Zhou (2015); Bouneffouf et al. (2020) for comprehensive surveys. However, most theoretical results require assumptions about the dimensionalityy, such as the context having finite cardinality (Agarwal et al., 2014) the existence of low-dimensional representation, in linear contextual bandits (Chu et al., 2011), I). Our paper is the first to address the problem of contextual decision- decision-making making based on siinittedimensionall functional regression. We establish universal regret bounds for various tasks under eigenvalue decay assumptions and further derive general sublinear regrets without them.
Operator Learning. Operator learning (Mollenhauer et al., 2022; Kovachki al., 2024; Adcock et al., 2024) studies the case where the input and output are elements in Banach spaces such as some function spaces. However, in our paper, although the objective the distribution function, we are unable directly observe the function itself. Instead, we can only observe single data point sampled from this distribution. In other words, we do not have full feedback but only bandit feedback, which makes our problem much more difficult than general operator learning (Foster et al., 2018; Foster & Rakhlin, 2020).
Functional Regression. Functional data analysis focuses on analyzing data where each observation is a function defined over a continuous domain, typically sampled discretely from a population. Morris (2015); Ramsay Silverman (2002) provide comprehensive introductions to functional regression. One subdomain, Kernel learning. for example, learning in reproducing kernel Hilbert space (RKHS) has been hot topic in recent years (Yeh al., 2023; Hou al., 2023). Nonetheless, the problem we focus on is quite different from theirs, datasets in kernel learning contain input and output points lying in some kemeliiedd spaces, while we do not have access to data of required integral kernel L lying in an infiniteddimensional space (,2 v) directly. Zhang et al. (2022); Azizzadenesheli et al. studies functional regression for contextual CDFs in finite dimensions. For infinite dimensions, under some special conditions, Zhang et al. (2022) also proposes method based on some regularization term which scales with respect to the number of data points.
B. Useful Math Theorems
Theorem B.1 (Theorem 8.2 in Gohberg et al. (2012)). Let positive operator ((0)(w) = Sa adjoint. If the kernel K (w,r) is continuous and satisfies the Lipschitz condition.
be self-
(w, r1) K(w, r2) S Cl|ss2 s1||;
then
(2) < <0
ie., Ld is a trace class operator.
Theorem B.2 (Theorem 8.1 in Gohberg et al. (2012)). If a positive Hilbert-Schmidi integral operator U is associated with kernel KC(-.)). Then, if is traceable, it holds that tuu))= = K(xxx)dr < cc.
Theorem B.3 (Theorem 2.7 in Ferreira & Menegatto (2013)). Assume is Borel measure. Let K. be kernel in C(Ω x Q2) n (? x Q2 x v) possessing an integrable diagonal. Finally, assume L possesses a I,2 .N -coovvergennt spectral representation in the form
c(f)= = - ((C) f (Z,,v),
where {ei} is an orthonormal subset of T.2 (S, v) and the sequence (NxC)) is subxet of a circle sector from the origin of C with central angle less than n. Then, the following statements hold:
(i) There exists & E 10, 2T] and 1 > 0 such that
/
12

---

Contextual Online Decision Making with Infinite-iimensionall Functional Regression
,,, (ii) If the eigenvalues of L are arranged such that [Ax(C) ( = ..,, ,
(a((C) 5 (1 (1+
/ (e(c)K((,))))d((0))
(itt) OC,
(2 = o)n
(iv) The operator is trace-class.
Definition B.4 (Functional Determinants). For any traceable Hilbert-Schmidt integral operator 44, we define the following number as the functional determinants of U,
Eu - log(1 + A())))
Given dataset D, we will also use the terminology &p to denote Eup when it's clear from context. This number depicts the speed of growth of the eigenvalues of our integral operator. When the dimension is finite, one can show that the order ED log( [D]).
Theorem B.5 (Doob's Maximal Martingale Inequality). Suppose {Kktwzo is sub-martingale with X₃. 2 0 almost surely. Then for all a > O, we have,
E X
P max 1SiSk
X; 2 a) S
Lemma B.6. For any a, b, C. E IR, a > O, we have
[ exp {
ax²
+ but + c)
2m
(b2-40 4ac
122
dx
exp
2
8a
Proof of Lemma B.6. The proof is quite direct. By calculus, have
ax? + by +
2 b x
b
2
b2
4ac
x +
+
a a 2
2a
8a
Using the fact that Jg nT, by change of variable
V
[ + b , just plug it and we shall finish the proof.
Theorem B.7 Coorrnn-Fischhe minimax theorem in Teschl (2014)). Let A be compact, self-adjoint operator Hilbert space H. Its eigenvalues are listed in decreasing order
A1 2 22 ....2 ....
Let St C H denote a k-dimensional subspace. Then,
A = max
min
Ax)
8%. aESE.I|a|=!
Theorem B.8 (Sion's Minimax Theorem in Sion (1958)). Let X and y be convex sets in linear topological spaces, and assume X is compact. Let f : X x y - TR be such that i) f(x. -) is concave and upper semicontinuous over y for all x E X and (-)((y)) is convex and lower semicontinuous over X for all E y. Then,
inf sup f(z, v) sup inf f(z, v). yey =EX
zEX yEy
Lemma B.9 (Example 27.1 Shalev-Shward & Bavid (2014)). Suppose that A is compact set in R and set A ||a]], then (r, ||) 20/m
13

---

Contextual Online Decision Making with Infinite-Dimensional Functional Regression
C. Proofs in Section 2 Proof of Theorem 2.8. Recall that
(w)((;;)0()))) (0)(() 9
By definition, we have 0 Σ (C,)(, = (r, 1,
Sa (")" S
Thus, - is integral operator and it is compact. By Cauchy- SehuhhySShhwzz inequality, have
| (0) $ Salo (()) / () dr)dd()) & 1101L2((aM))
Also,
(0, (0, = 1 1/ s
( 2 0.
Therefore, Le positive operator with || S 1. By direct calculation, we have
| (w(w)
(0,06))))))
(w, (aattiir)))tt
52
(2(r)
(c (01),02).
So we finish the proof.
D. Proofs in Section 3
Proof of Theorem 3.4. We prove this theorem for general 0. We first show that Σÿ= Iu, (s) aj w, s)dm(s)
(2( v). We have
L/g55/ Ty (5)6(1)) ag, w. (d
Dy (s)) aj w. s)dm(s) (B S Σ1 1=1
g
S (V(( < 00.
Now we define
112 Ly (s)ō(z), ay, s)dm(s)
(u(w) 2 ub.
Because there are only finite terms in the summation by the definition of ub have
| (2(2)))) < o0.
Therefore, by the Sauchy-Schwarz inequality, we have
(o(w)o(z), w. s)dv(w))
n
10 (00(w))()))))) (du(ww
< (100l1<000m) )
<110011<<00.>>>
14

---

Contextual Online Decision Making with Infinite-Dimensional Functional Regression
Recall have m(5) oc and IT (+) < for any j E [n]] and S, which implies that
L(0o, D) < oo.
On the other hand, for any 0 E Span(ei ... ,N.)) we have
Σ3 / (Ls ((w))(( ag, u; us,, w,)))
a
L(6u + 0, L(6b, D)
dm((s)
j=1
+ > / (Lg ((w))()) as w, s)du(()) j=1
(Ss do (o(w))(rz) ag, s)dr(w) - Lv5(s) (s) dm((s)
We analyze this difference term by term. First, by algebra, it holds that
Σ Σ S s (J ((w)olz) oj, we s)du(()) (Js Oo (o(w))(z))) ag w, s)dv(w)) dm(s)
1=1
I ((w) I (o(r)
E ((0s), w, s))((,) a s)dm((s) du(w)de(r)
Σ "
((w) Σ
Ja j=1
=
Recall 0, 0 E Span(e1 ... ,NN)) so we have
(0, (0.ū
Second, by direct calculation, also have
(/,
Σ
(w))(1)) aj, w, s)dr(w)) Ius (s)dm(s)
1=1
- (ww)
Σ
/ Tu, (s)0(1g as, w, sydmn(s) du(uo
0,
Σ
Tu (s)00ll3,,,
Given the condition that 0 E Span(e: ). we have
N
In (s))
Σ
(0, e
Σ
Mg (3) s)mm(s))) e4
Moreover, by the definition of Co. we know that
(0.00..(0i))
Σ (0)
>;
1
Ly (5)0(I); ajr 3))dm(s)
X
No
Σ (0)
In, (5))(1z. s))m(ss)
1=1
15

---

Contextual Online Decision Making with InfmitteDiimensional Functional Regression
Thus,
Σ / j=1
((ow))lee))) dm((s 2
Li00 + L(0,)
Therefore, 8, = 0DD and we finish the proof.
Lemma D.1. Projection PD non-expansive, which implies that
[|Pp(z) - PD S ||x - =2luu Vz, E (S2,
Proof of Lemma D.I. By the fact that C is convex, we define the quadratic function h(u) = (111()))()))) + pay) 1 for any x E (S2, v),y E C. We expand to get,
h(4)= = (a The vertex of h22)) is
(lx-Po(<))la M(V-o())))
2p (c - - - - -pp(2) 1
n² (x Uppx)),l(l - -b(xx)) (V-PD(x)) (2)
Because Po(x)= = argminyec byy - x xllip we have 1¹ 0.. Thus,
- (b- - Pp(x))) s 0.
Again, we abbreviate A; (:(D)) and e; Ebp. By the spectral representation of Up. this is equivalent to
(x - Pa(x), (y PD(x),
(2)
This holds for all y E C, so we set = (2) Equation (2) to get
20 N (s Pp(x) (Po(a)-Po(s)ee)) so.
(3)
On the other hand, we switch x, in Equation (3) to get,
A ( (Po(z) -p((),)) $0.
(4)
Adding Equation (4) and Equation (3) to obtain
0
> (Po(s) - Pp(x), (Po(=) Pp(x), -Po())-Po())ee)) S A (2 (P)e))((()) -P((s))Po(()))e))
Σ
By Cauchy-Sehwand inequaaltti we have,
1/2
1/2
20
2
20
Σ
(Po(2) Pb(x), -Po())))))PPp
Σ
As (z (x-=),,)))
Σ
N (Po(2) (tp(())Pp(())cc))
Plugging this back, we get
1/2
Axe - 2,,)3
x
X; (Po())-Po(on) - (s 1/22
de
which is exactly [P)(2> Po(2)lle $ 5|1r =1120- So we finish the proof.
16

---

Contextual Online Decision Making with Infinite-Dimensionall Functional Regression
Proof of Theorem 3.6. In this section, we also first prove for general E, and then we replace by n रीड to obtain our result. For the ease of notation, use to denote (;(pp) and e, to denote ey. We first compute the difference
OD.= - 0"
aj, Lu (s)((1) aj, w, s)dm(s)
Σ 10 e
-
=ubbc
Uy (8)((1)) aj, w, s)dm(()
- Uber (Uo(10))
Σ
e4)
j=1
12N
Ls (s))(I)) ag, s)dm(()) s)dm(()- -f o 01 w, s)dm(()
Σ j=1
(0" es N2++11
E
(5)
We define
V (w) & / Le, (s)o(z,, w, s)dm(s) - S
Lo 0 (, w, s)dm(s),
W A Vj
We apply norm
||| on both sides of Equation (5) yielding
110p - 0"uluu $11u5, (Ww)lup +
Σ (0", es) eillup
12
=IIWallab. +11 Σ (0", eiluuo
12N+11
S <lWWalli,. + M
(6)
The equality due the definition of U. Hence, our analysis only needs to focus the first term ||W,lllg.. We Fu denote the o-algebra generated by all the data from (I), (1,31) v1) to (I', ake yk), and Foo is ((U=FR) correspondingly. By the definition of Vj, we take expectation with respect to Fイ-1 and obtain
B[V / (F))(1)) aj ()d(()))(2)) aj, s)dm(s) - 0 (r)ø(zz, a,, s)dv(r)((ax) ag. w, s)dm(s) 0.
Therefore, {V5),21 is martingale difference sequence and consequently, Wi = E Vú martingale. For any T,2 v), we define (a) A exp (a, W - [elll, }. Moreover, we define Mo(a) = for any a. We have the following Lemma D.2 that (M)x
non-negative supermartingale.
Lemma D.2. (Me(o)) is non-negative supermartingale.
Define ( = ( as an infinite sequence of i.i.d. standard Gaussian random variables. We use FS to denote the o(LI, (2. Define
N
B
A
Se
Because there only finite terms in the summation, it holds that
E [[] < co.
17

---

Contextual Online Decision Making with Infiiite-iimensional Functional Regression
Thus, have (),,)))((..))))) a.s. and (P,
Denoting Mr as (o) we now verify that this is also a non-negative supermartingale.
[ (3)
(B) Fi-
S (3)) FR Fe-i)]
(
-M
Furthermore, the integral of M, could be upper bounded by,
E M a = E[M,] = [[M+ = EBE
& (()))))) =1
Therefore, {M+) n2420 is non-negative supermartingale with uniform expectation upper bound. On the other hand, we can directly calculate Mn. We use w, denote (Wn, ei) for simplicity. Then, it holds that
21181100 }
1
N
N.
)
M.( exp exp (3, W.)
Xis? J.
exp
2 1=1
and
N: Σ
( exp Σ
1
DG2 ... 1 dCN.
M
WiCi
(2:97 + 97)
dei
JR
V2T
V2x
1=1
t=1
II
N:
(1g
exp
wiss
A + 1
52
1
dGo
2T
i=1
Then, by Lemma B.6, we have
w 2(1 Xz)
1
1
M,
exp
exp
Wa [Walltb.
II No (1 + A₂)
(1+
2 1/(nE))
Applying Theorem B.5, we derive
1
P
exp 2(11 + 1/(ne))
||inlle 2 So.
M (1 (1+A)
which implies that with probability 1 8,
1 N₂
| 2 1 + 1/(ne)) < 2(1
log( ()
2
log(1 (1 + 21)
2
i=1
Combined with Equation (6), it indicates that with probability 1 - 5,
N₂
00 - 1kkee s
2(1 + 1/(ne)) log( 5
+ 2
Σ 1=1
log(1 + Ar)
+ nnMM
Noting that projection mapping is non non-expansivve by Lemma D.I, we have
[(P,((D,)) PPD(0")lus
110p - 17 S 110 8" 111l
18

---

Contextual Online Decision Making with Infinite-Dimensionall Functional Regression
Finally, we conclude that
00 - -0 V
(1+ 1/ns)
1 2 2 g) 5 +
Σ i=1
log(1 Ai) + nnM..
We define
N2
(n) (n) -
V 2 5) Σ
log(1 1 + +x)) neM.
Setting == n -ीス and notice that ne
I 1, So finish the proof.
Proof of Lemma D.2. By definition, we know that Ma(a) is Fe-measurable. Consequently, it holds that
E Fi- M (a) =E exp fa, Vid // f.5 aa (a, ()
E eex fa, Vi 1F
=Ma-1(a)
exp 2 Ig Man,an (a, t) dm)
Since - Js Warnaa (a, ())m((s) S (a, V&) S Ss Vzzu,a, (a, ())mm(s). according to Hoeffding's lemma (Hoeffdingg 1994),
we have
2) )} exp E Texp fa, 1Fa-l] exp ( Ieree a (a, ())mm(ssss)
4
{ au (a, (a, t)) }
{2 J
Then we have
exp { Ig Vanan (a, dm))))))
E (a) M (a)
exp 2 Ss vnnan (a, 1)2 = Ma-1(a).
We finish the proof.
Proof of Lemma 3.7. For any Is fixed, by Theorem B.7, we have,
X (l(D)
max
min
(a, (f +... = (a))
max
min
(a,azs:))(a))
Su.dim (8y) o Ø=1
max
min
max
n (ax, L(xx)
|= (5.
Notice that for any Sg fixed, the set fa E Sx, Sx,1|a|| = 1} is both compact and convex. By Assumption 2.10, we also know that {L I E X,, a E A} is convex. We regard (a, L(a)) as a function of both a and L. Then, function f(a, L) (a, L(a)) linear L, and so fa, C) is continuous and concave L. the other hand, f(a, L) is the square of some norm || l|e and thus it is convex and continuous a. We apply Theorem B.8 to get
max min 3 www.ee/ew......e....
max
(a, L(a))
max (EC aeS..//a|== (()))
max
min
max
max 5..dm((5))=kosss..). oES..
min
(a, L(a))
The last inequality holds because we can swap the order of two supremums. Using Theorem B.7 once again, we have
max max a
min (a, ((a)) = LE(2"MIzEX
max \e(.).
19

---

Contextual Online Decision Making with Infinite-iimensional Functional Regression
Combining these parts together, it holds that
Au (l(D)) S
max (E(
Ax( S nT.
Thus, we have
N log(1 + (x(4d)
N
N
A
n77
=
log(1 [1 +
ns)
-
log(1 +
nE)
T18
TE
2=1
1=1
Because for A1 iiS Ne, it holds that
nE X S nT1s.
have
Ne
log(1 1
nT +
ne)=
=
Σ
N.
log( (1 + nT:)) S
Σ
N.
log(1 nT; 1-7g7
N.
log 1 +nt, - S
log(1 + e
N.
Tin
ne
87
87
87
1=1
1=1
i=1
1=1
which implies
N,
log(1 nn)
No
log(1 + (,((1))) S
Σ
Ex
Plugging Equation (7) back to the definition of (n), we have,
N. Σ
(n))
88
logg( 5)
log(1 (1 + A1))
meM
i=1
logg 1ogg)))
log(1 + +87n
Σ
No
To
+ MeM
8"
2 log( 1
+ log(1 + =
(
80
+ nsM.
87
Setting e" = x42, we get
(n) S V logg(1/)) + 2son 3h log(1 + n) + - M.
The RHS has nothing to do with D but the information [D] n. Therefore, we define En( 2 2log(1/5)2/2 + (2 (2/5olog(1+ + n) + M) n पनन By the fact that Va+ + Va Vb, we obtain,
E.. (n) Es(n) = llog(1/))//2 + (2V so log(1 + +n) + M) n t
Thus, finish the proof.
Proof of Theorem 3.10. Denoting (w,"(w,T) as Fwrr (x, a), we get function family indexed by Ω. G (I, a) (w, r) E Ω x Ω.). We first consider all the rational points in Ω Ω which forms countable subset (w 1 and induces countable subset of Go (9w,, r. (z, a) {= By Theorem 3.4.5 in Giné & Nickl (2021), have, for any 8 0,
logg(110)
P sup Iw, vo (z, a) (x, a)dQ) 2E
sup Eig (1),as) +
< 8.
X.A
71
20

---

logg(1)/) Contextual Online Decision Making with Infiiite-iimensional Functional Regression
By the density of rational numbers in real numbers and g is 2 -Lipscccc continuous in (ue, r), we know that
P sup (2, -
- - X.A Iw Iur 2 2B
sup -
(she, BEg j=1
+
2 2log(1/6)
S ó.
gEg
Now we try to bound the Rademacher complexity term E sup gEG 1 Ei= Es (,9u,((0,, an)
Recall that we have have.N (Vt, 22, ||-
ll - (4) I1gwi.r (a,, a) Iw (z, al - r1) - (w2, r2) 12) 100. Then,
N,,,, |1>0) 5 2 2d
Then, by Dudley's integral entropy bound and using 11916o 1, we have
12 Vn. /
24v
Ee sup gEg TE
Σ (i) S
v VlogW(u 11.0 Gjdy S
Vn Vlog(2Lo
For the simplicity of notation, we use ((((*)((;r)) r)) to denote Jx.a ő(x, a, w, s)Ø(1, a, r, s)dm(s)d and Qn (w)r) to denote its empirical counterpart. Combining all the parts above together, we have that with prob- ability at least 1 8,
sup Q(KT."(wrr) - On (1,))= 48 48 (log(2LA))) (w.r)
22 (2log(1/0) +
Vn
Vn
By Assumption 3.9, we get with probability at least - 8,
QuK r))
48 / (2
sup (wir)
1
Qn (Ka.aa a. (w,r))
n/n
nyn
Recalling that Up = Σブ= Sa Ka as (w, r dd s) ddv((), our bound in Corollary 3.8 yields with probability at least 1 5, the following bound holds that
100 - 8" llub I Es(n).
use 2t2 to denote the integral operator induced by kernel n fx,A SS Mxx, a, w, D) a, r, 1)dm()))02... and Up its empirical counterpart. Therefore, for any 0, we have that
(0) = =1 ((w) [ J Sx.ASs (()))() w, t)((, a,, a, ann.
n / (7)
(,24b()) = - ((w)
[EE, 0 ((r) w. s)o(Z, ay, (os ()d)(s)dr(()dd((r) 5=
= / (w)))()) (K(r)))))k
Combining these two equations and the concentration analysis above, we conclude that with probability at least 8,
(0,ur = n / (K)))
n
n (w))(()) { Q(K(wr))) } (n(K(( ())d()))))) (n((w(
48 dog (2 2 log( (1/0)
n [ /
n/n
48 dloogl2 2 log (1/5) n/n
(0, (0))
21

---

Contextual Online Decision Making with Infmitt-Diimessional Functional Regression
Replacing the general 0 by 0p 0" using Corollary 3.8, it holds that, with probability at least 26,
1/2 100 - 1l s (1+ 48 4 2/log(110))
)
(n().
On the other hand, by directly calculating 110p 0r 11.y we find that
110 0'1/20 (OD.s - 00, (00 -01)
=n /
JxAA ( (0D 0*) (w) / (0n-07 0r) ao
I IxaUs { (1/ @p 8*) (w))(z, a, tyduluo)) (N/ (op 07) (r)o(1, a, r,du(( dmlssddQ...
=nBz,a [IFo(r,, F (x, a, =)2
Assembling all these parts, we finally get the following inequality,
(1+ (48. + 22log(L/0))//) Es(n)
F (F
F
s
n
By Lemma 3.7, we know that
En(n) 2 2 2lg((166) (2 log(1 + +n) + M) noFz.
By denoting C(d, Lo. 6, A, as (1 (48 + 2 2lgg(1//)) we finish our proof.
E. Proofs in Section 4
Lemma E.1 (SSimchi-Levi & Xu, 2021)). Assume that we are given an offline regression oracle RegOff and i.i.d. data
D ((1), at (t, r:))== where E[rr/a,, a:] =
(1i, a.). With probability at least returns f X - TK such that
Ests(n) m
Ezga
for some number Est Then, define epoch schedule &m 2 and exploration parameter Sn = 1 K////////aaa (Em (Em-) For any t, let m(t) be the number of epochs that round lies in. For any T large enough, with probability at least the regret of Algorithm 2 after T rounds is at most
Esto/(2m²) 5m-22 2) (Sm Em-1)
VK Σ
5m-1
Em-2
Proof of Theorem 4.2. From our regression oracle, have that
Ests(n) LdO(d, Lo. 8/2, A, (2)
22

---

Contextual Online Decision Making with Infniite-iimensional Functional Regression
By applying Lemma E.1 and plugging in the choices that Sm 2m, get
(Tg
mT)
Est5/(2m2)(5mm1 - 5m-2)
0
VK
(5m 6m-1)) 0111
5m-1
5m-2
m=
m(T
E5s(4m3)(5mn) (5m- 6m-2) (6m - Em- +1
o
VKLY
Σ
VCd, Lo, 8/.8//m3, A, 1))
Vmm-1 fm-
m=2
m
2 2log(4m²² 10)2/2/ (2 s0 log(1 + 2m + M) (2m-2)
0
VKL
Σ
Lo, A,,)
2
+1
2m/2-1
m=2
(8)
By our epoch schedule, holds that m(T) & [log;(T)] (T)]. By Theorem 3.10, we know
192 (logg(/g2
C(d, Lo. 8/4m", = (1+ (48 /dlog(2L)) + +2 20gg(m42/0)) <
loggmm/
Thus,
Vdlog(2Lod)
Cid, Lo, 8/4m² A, 0o
Vlog(m/0)
17
Therefore, for Equation (8), we further have
Reg(T) so
LVdK log (2
/ /log(m/6)
mf()
(log(logT/))) + (Vso m==
Σ
(eii++++/,,+ log(1 + Io) + M)
26m-22
(5+2)
2m/2
LydK log(2
Denote the number
as Ō(K, Lo A.d,n). We have,
L LVdK log(2Lo.)
/log(m/8)
m(T)
(log(lo + (V log(1 + M)
26m-2) (x+z)
2m/2
11
m=
m(T)
m(T]
<Ō(K, I., To, A,d,n)O
log(log T/8)
2m/ (log log 1/2 Σ
Σ
Voolog( 11lg
Tog + M) 2 2(
(By 1am
m=
<Ō(K, To, A,d,1)
(log(log T/O)vT++ + (80² 1/2 + M) (log log T/8)T 3y42
SÖ(KL,, A.d, m) (1s0 1/2 + M) v1) o (og((ogTT/0)
3-+2
Proof of Theorem 4.1. By the L-Lipsehitz continuity of T, we have
Ex,a (T(Folt,a))) ((F Ex,a [o,,,a( Fx, (112
Then we apply Theorem 3.10 and replace 26 by in the claim of Theorem 3.10. Thus, with probability 1- 8.
Old, Lo. A, E/////2
[ [I, F (ar a, 8) ()
Combining these two inequalities together, we shall get our result.
23

---

Contextual Online Decision Making with Infinite-Dimensionall Functional Regression
F. Computation
Given the theorems and properties we have established, a natural and fundamental question arises: how can we numerically compute the eigenvalues and eigenfunctions of an fiinite-dimensionall operator? In fact, within the applied functional analysis community, there is a wide range of methods for numerically solving the cigenvalues and eigenfunctions of integral operators in infiniteddimensional spaces (for example, (1972); Ahues et al. (2001); Panigrahi (2017) for reference), including the Galerkin method, the Rayleigh-Ritz method, quadrature approximation methods and so on. In this section, we will briefly introduce one method based on degenerate kernels for calculating the eigenvalues and cigenfunctions as an illustration. Please see Gnaneshwar (2007) for full details.
Chatelin (2011); Ray & Sahu (2013); Chatelin (1981); Kohn
We assume that Ω = [0, 1] and an integral operator C' is defined as C(=][(s) = Jo k(s,, ())(())t. The basic idea of Algorithm 3 is to construct a finite-dimensional integral kernel kN, to approximate A: holding the property that the differences between their eigenvalues and eigenfunctions are small enough to be ignored. Therefore, to solve the eigenvalues and eigenfunctions for the kernel k; we can instead solve them for , which is fiitte-dimensional and can be readily transformed into a matrix eigenvalue problem.
We present the pseudo-code in Algorithm 3 and omit the theoretical approximation amalysis here. Please refer to Gnaneshwar (2007) for concrete theoretical guarantees.
Algorithm 3 Degenerate Kernel Method
Require: partition number n, kernel k(s, t), degree number and corresponding Legendre polynomials T,,(t) der
d' (f2 1)².
Partition [0. 1] into n intervals, 0 = Zo < < 22 < In-1 < In 1. Is = [ Zxl, h = max [Ts]. Set
[t( = 2 - + 1+h - Tk. -1 - 1
1-f
2
Define P, as the space of polynomials of degree 2 r - 1. Denote N₁. = nr.
Define piecewise polynomial space associated with P,
S% = {u: uu: [0, 1] R u/,, E Pr, s
Find the Gauss point set (zeros set) of (t) [0, 1), B, {y) ... yr).
Let A Uh (B,) twi, (x() 1 [r], [n]] and (zx be the Lagrange polynomials of degree 1 with
respect to y1 Ur such that (113) 8iz-
Define Pap(x) 15 (x))
x E [xp
0
otherwise.
Pjp (w)) òyoōpp, f, j E [r],k, p E [n]. Set t(k-1)r+5 = Wyk. 2(k- 1)r+) Pyk, for k [m]. Let S @ S% be the tensor product space of S%, with dimension N₁. = nr. Define degenerate kernel
Notice Pjp E Sy and
Na
Ni.
kN, (8,
k(ws, (1))
which induces degenerate kernel operator
No N₂ k(w, (s)))()
(x)( =
Σ
==
Solve the eigenvalue problem for the Nn-dimensional integral kernel kN2-
We now provide a method to solve the cigenvalue problem for the finite-dimensional kernel AN for completeness.
Solve eigenvalue problem for finite-dimensional kN.: Consider the following formula that
N N
A g(s)== = -
Σ k(w,, (1))
(9)
24

---

Contextual Online Decision Making with Infinite-Dimensionall Functional Regression
Here, À stands for the unknown eigenvalue and g is the corresponding eigenfunction. Define C A fo م k(wi, (y) i [Ni]. and c = (c1, "2 ,N,, is an unknown vector R. which we will
solve for. Then, can rewrite Equation (9)
(66) Σ (s)
(10)
Plugging Equation (10) back to the definition of c, it holds that
G = %
1
No
N (t)dt
N₁ N
ckk(wi wi) / 2))))xx(t)dt, i [Na,]
Σ
ko (wni, w))
Σ
ckZN
(11)
j=1A=1
which is equivalent to
N2. k(w, ((),) Σ
No.
Nº. No Caklui, w5) I/" 2z(()=x(()d{, i e [Nv]
A.G = / Σ
(1)x
(12)
Note that within the implementation Algorithm 3, both k(ws,w) wy) and (z(t), (t) are known to us. Besides, the right hand side of Equation (12) linear with respect
Define bu = En= k(w),w)) fo =, (t) (t)dt. Then, Equation (12) is equivalent to
ci
b11
b12
bINn D2N,
C1
C2
by1
b22
C2
:
:
:
CNr
ON,
bN, bN, N..
CNr
Equation (12) finally turns out to be matrix eigenvalue problem with unknown eigenvector (C1, (21,02 C2 CN,, ) and eigenvalue X. We could solve this matrix eigenvalue problem to acquire (CI, C2 ,CN,) and eigenvalue X. Eventually, we derive the eigenfunction associated with À for kernel kN, using Equation (10), i... g(s) Σm (s).
No
G. Auxiliary Results
Definition G.1 (Gohberg et al. (2012)). Let A compact operator in Hilbert space H and let A (A*A) Z (A 2 be the sequence of non-zero eigenvalues of A A. A" is the adjoint operator of A. Then the j singular value of A sy (A) defined as
sy( A (Ar(A"
Property G.2. For any self-adjoint positive Hilbert-Schmidt integral operator 4, it holds that
Xy(41) (y( for j.
Proof. We denote the integral kernel of 24 K. Because 14 is self-adjoint positive Hilbert-Schmin integral operator, then for V B.
u(0) Σ x:()) e0) e..
t=1
Therefore,
u(((F)) Σ x (0)
Because L1" = 44 we finish the proof.
25

---

Contextual Online Decision Making with Infinite-Dimensional Functional Regression
Theorem G.3 (Corollary 3.6 in Gohberg et al. (2012)). If A and B are compuct operalors on the Hilbert space H, then for any n,
"
11
Σ
8y
B)
8y 8)(A)
Σ (B)
5=1
Theorem G.4 (Corollary 4.2 Gohberg al. (2012)). Let and be compact operators on a Hilbert space H, then for any p and any k,
Σ (AB)) & Σ (B))
and
Σ
(AB) & Σ (B)))) j=1
Now we introduce the functional determinant of trace class operator. We notice here that the formal definition of functional determinant requires exterior product and tensorization of the Hilbert space H. Nonetheless, by Lidskii's 's Theorem (Simon, 2005), are able to achieve equivalent characterization of it, so we directly use this characterization definition for simplicity.
Definition G.5 (Theorem 3.4.7 in Kostenko). For any trace class operator A, the functional determinant det(L + zA) is defined as
det(/ + +A) & II + =A(A)), V2 E.
Theorem G.6 (Theorem 3.10 Simon (2005)). Suppose the integral operator A is defined as Af(x) = Jn K(x, f)) where Q is compact and ((x, y) is continuous on Q x Q. Then, it holds that
(r(A) / K(x,x)do.
In the meanwhile,
det(I + +A) = Σ
O'
m!!
1=
where
Om .a.a ... / (ot((K(2, | dxm, V m 2
We conventionally set ag 1.
Now we are ready to analyze the integral operator - and Up in our paper.
Lemma G.7. For any x; a, det(1 + L S e.
Proof of Lemma G.7. We apply Theorem G.6 to the operator L The associated integral kernel is k=t((w,)) Sg (1x, a, w. f)6(x, a, r, ft)m(t). Therefore, by Theorem G.6, we have
(K(wi, wy) w;))
Mox a, wr. dt
I ((z wi,t) w2, t)dt [o a, u2, 2)
Jo wi, (1,t)o(z, a, wm, t)dt I Mo a, we, 1)l( a, wms t)dl
f cla,a W2, M)( wi, ()dt
=
f Solz, a, wms t)) a, wT. t)dt
f Lo(z,a a, ums t)o(k, a, w2, t)dt
f wm. 2
This is symmetric matrix and
Σ (((KKus,,0; = Σ}
/ o( a, w., t)3 S m,
26

---

Contextual Online Decision Making with Infinite-iimensional Functional Regression
due to 0 S Φ < 1 and m(S) 1. Therefore, by the AM-GM inequality,
1/m
E
X,((K(u,, ((KKW,,,))), W S 1.
II ((((K(w; w)))
m
We find that
(et[(((w,, w;)) w;)); :1= = II X, (KK(( w;)) I 1.
2=1
Recalling v(22 = 1, we have that for V m 2 1, Omm S Sa ... So ldv(wrr) ... d.dumm) S Thus,
det (1 + Lz.a)
Om
1
Se
m!
m!!
i=0
i=0
27


Reviews:
[{"review_id": "tYaAFTI13E", "reviewer": "Reviewer_t1kP", "summary": "This paper studies the contextual bandits setting, in which it develops a novel method --- with broad applicability --- for making decisions whose utility is allowed to be any (square-integrable) function of entire (contextual) distributions associated to each arm/action. This flexible definition of rewards is in contrast to much of the literature, in which rewards are typically assumed to be a simple function of the arms' distributions, such as means, mean-variance etc. \n\nIn a nutshell, the proposed approach consists of two parts: (in each period,) the arms' distributions are estimated via an infinite-dimensional functional regression, followed by estimation of the best decisions to take based on the estimated distributions. The functional regression part crucially utilizes the following technique from operator theory: results/assumptions on the spectrum of the design integral operator are made, and the estimation is regularized by cutting off all terms in the eigendecomposition from some term onwards. The policy estimation part is more standard and utilizes an inverse gap weighting approach. The general bounds are then derived for the performance of both above described parts, and are stated as a function of the properties of the design integral operator's spectrum.\n\n#######\nUpdate after rebuttal:\n\nI have read the authors' response, which does mostly address my questions. I will keep my original score, as I still believe the paper is a thought-provoking and reasonably technically sophisticated contribution to the literature --- but it, however, suffers from issues such as its very suboptimal writing, as I have pointed out in this review and on which there seems to be a broad consensus among the other reviewers. I have also read the discussion with the other reviewers, and I believe the writing of this paper may have led to the ensuing lack of clarity over key assumptions of the paper, i.a. the eigendecay --- and as such, it is on the authors to better motivate and contextualize this assumption in future revisions, in particular making sure readers understand why/when this assumption can be nontrivial.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your remarks and questions. We would now like to answer your questions in order. \n\n**RE: Squared-Integrability**\nThank 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)]\nincluding 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$. \nOur assumption is an extension because the finite $2$-norm in infinite dimensional function space is square-integrability.\nGenerally speaking, assuming no prior knowledge about model class, you can still estimate using any model class.\nIn this circumstance, there will be two types of errors, the first type is **approximation\nerror** 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.\n\n**RE: $\\gamma$-intuition**\nWe explain the intuition of $\\gamma$ from the following:\nFirst, 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$, \nwhere $\\lbrace\\lambda_i\\rbrace_{i=1}^{\\infty}$ is eigenvalue sequence and we have $\\sum_{i=1}^{\\infty}\\lambda_i^{\\gamma}<s_0<\\infty$. \nWe 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.\n\nWe 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)].\n\n**RE:Examples**\nThanks 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, \n$|T(F_1)-T(F_2)|=|\\int_{S}sd(F_1(s)-F_2(s))|=|\\int_{S}F_1(s)-F_2(s)ds|,$\nThen by algebra,\n\n$\n|\\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)}.\n$\nThis indicates that the decision-mapping is Lipschitz continuous with respect to our $L_2$ metric.\n\n**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.\n\n**RE: Compare with [54, Zhang, Qian et al. (2022)]**\nIn [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)}})$.\n\nThank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.\n\n[47] Approximation tools and decay rates for eigenvalues of integral operators on a general setting\n\n[54] Functional linear regression of cumulative distribution functions\n\n[73] Conservative contextual linear bandits\n\n[74] A simple approach for non-stationary linear bandits\n\n[83] Generalized linear bandits with local differential privacy\n\n[84] Combinatorial bandits with linear constraints: Beyond knapsacks and fairness\n\n[85] Improved algorithms for linear stochastic bandits", "claims_and_evidence": "Yes, as the paper is theoretical in nature and all their claims are substantiated by (to the best of my checking) correct proofs.", "methods_and_evaluation_criteria": "N/A --- The proposed algorithm for contextual bandits, as well as the associated performance bounds, make sense for the setting. As a theory paper, there are no associated experiments or evaluation criteria.", "theoretical_claims": "Yes, I checked for correctness of the overall methodology and the broad-level correctness of the analyses, and am reasonably convinced that the results are substantially true (possibly up to minor unchecked details).", "experimental_designs_or_analyses": "N/A --- the paper is theoretical in nature.", "relation_to_broader_scientific_literature": "This paper can be viewed as a substantial generalization of many results in the literature on contextual online decision making. The main setting studied in the literature is that of mean-rewards (corresponding to vanilla contextual bandits), and there are also many more specialized settings that study risk-aware rewards (which allow for dependence on risk measures such as variance, quantiles, spectral measures etc.) as well as settings such as sequential hypothesis testing --- but due to various statistical and computational intractability concerns, most of the above settings typically don't permit the reward to be a general functional on the space of arms' distributions. \n\nThis paper, by contrast, makes rather generic assumptions on the distributions (such as that there is a functional basis with respect to which the distributional estimation is allowed to proceed, and that the reward is an appropriately integrable function of the distribution), and still manages to provide an algorithm that works in all such settings, with regret bounds that depend on the spectral properties of the design operator corresponding to each concrete instantiation of the setting at hand.", "essential_references_not_discussed": "The literature review is currently fairly sufficient for providing the necessary context for the contribution, but see below for a list of several works that I would like to see added discussion on.", "other_strengths_and_weaknesses": "1. A major strength of the work, as I alluded to above, is the generality of its proposed methodology and bounds. Through a streamlined infinite dimensional regression-based approach, it is able to capture rewards that can be diverse functionals of the arms' contextual distributions, rather than just e.g. arms' means. \n\n2. In addition, the theory developed in this paper is mathematically nontrivial and previously not particularly explored in the present setting. Therefore, the paper makes a sophisticated, and useful, methodological contribution to the area, starting from the ability to perform infinite-dimensional regression when that is required, and not least including the discovered connection relating regret bounds with spectral properties of setting-specific design operators.\n\n---------\n\nFor the weaknesses, I can mainly point out that I am not optimally happy with the clarity of the work's presentation. For such subject matter of potentially big relevance to the community, in my opinion the details of the approach are described in a fairly linear and dry fashion, which could be improved. In particular, certain technical details of import could be insightfully highlighted, including but not limited to:\n\n(a) What is the minimal restriction on the utility functional? If square-integrability were not assumed, would the entire approach break down or is there hope with weaker assumptions?\n\n(b) How is the dependence on \\gamma propagated from the regression guarantees to the regret guarantees? In other words, I'd like for an intuitive sketch of the regret dependence on gamma to be provided in the main part, rather than buried in the derivation in the appendix.\n\n(c) Several specific instantiations of the setting are presented early on, but none of them are \"worked out\" after the algorithm is presented --- meanwhile, it would really help the readers to highlight how the assumptions made on the decision mapping and on the distributions play out in specific settings such as mean, MV bandits and sequential hypothesis testing. \n\n(d) Notation is clunky at several points. E.g. one annoying bit is how the utility is often described as a functional of F(x, a, s) --- s here is confusing, instead much less controversial would be to e.g. index F by a, x as F_{x, a} and then simply write e.g. \\Tau(F_{x,a})", "other_comments_or_suggestions": "See above for presentational suggestions below. As for further feedback, I think that while the literature review is overall sufficient, but of particular interest would be:\n\n(1) an expanded discussion of the Zhang et al (2022) reference --- as far as managed to familiarize myself with it, it offers some infinite-dimensional regression guarantees, but the scaling is with the number of points and the assumptions differ. While this is briefly mentioned in the paper at the appropriate point, as well as in the appendix, but I would appreciate further details on that and on how the proposed new procedure manages to improve on that.\n\n(2) A deep paper in the online learning literature (not strictly the considered \"contextual bandits\" setting) by Foster et al (2018) (https://arxiv.org/pdf/1803.07617) appears to offer a useful complementary angle: how much estimation (i.e. what sufficient statistics) is actually required to achieve certain guarantees. In another angle on the estimation problem, another paper (https://openreview.net/pdf?id=tyqL1bPl0L), in a full feedback online learning setting, studies accurate/calibrated estimation of general functionals of distributions beyond mean-rewards but subject to the functionals being \"elicitable\". By contrast to these papers, the approach in the present manuscript is to just estimate the entire distribution and take the functional of the estimated CDF when that's possible. Discussing the difference in approaches and techniques to these references, as well as what the proposed infinite-dimensional approach could imply for these other settings, would, I think, meaningfully contribute to positioning the work in-context and pre-view its possible future applications.", "questions_for_authors": "My main gripes are with the presentation of the paper, so I would appreciate if the authors could address in their response my points above by providing some text/discussion of these points that could later be inserted in the manuscript. (My current positive evaluation of the paper already presumes that these will be addressed in the eventual camera-ready.)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ks2POO10QW", "reviewer": "Reviewer_aBVe", "summary": "The paper proposes a unified framework for contextual online decision-making using infinite-dimensional functional regression. It introduces an efficient regression oracle to estimate context-dependent CDFs, enabling sublinear regret across tasks. The authors establish a regret bound linked to the eigendecay rate and design an inverse gap weighting policy for efficient learning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind remarks and questions, and we would now like to answer your questions in order. \n\n**RE: Minimax bound**\nThank 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.\n\n**RE: Our new contribution**\nOur contribution lies in the following perspectives. We propose a unified\nframework 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. \nCombining this functional regression oracle with inverse-gap weighting policy from contextual bandits, we can design our efficient sequential decision-making algorithm.\n\nThe key theoretical contribution of our paper is that we provide a rigorous characterization of the\nrelationship 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.\n\nThank you again for your comments. We hope you find the response satisfactory. Please let us know if you have further questions.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "including contextual bandits, functional regression, operator learning, and decision-making under uncertainty", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "One weakness is in the minimax upper bound, since \\gamma>0, there is still a gap between their upper bound and \\sqrt{T} lower bound.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. What is the novelty of your algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dMRxWsDcRu", "reviewer": "Reviewer_dr26", "summary": "This paper proposes a general framework for contextual online decision-making problems. The unique challenge about the general setting lies in the estimation the ground-truth distribution $F^*$ which is a function itself, and learning the distribution becomes an infinite-dimensional functional regression problem. Under some assumptions, this paper reduces this problem to learning the leading basis CDFs from the decomposition of the ground-truth. An algorithm is proposed to adaptive collect data and make decisions on-the-fly, with an online estimation of the coefficient $\\theta$ given by the regression sub-routine.\n\n## update after rebuttal\n\nI appreciate the authors' response. My original concerns were partially resolved and I would increase the score. However, I still lean towards the reject side for the following reasons: \n\n(1) the justification of assumptions (i.e. basis family $\\Phi$) is not enough: from a purely theoretical perspective, it might be okay to omit details on $\\Phi$ despite that it might be impractical to implement. Your work is claimed to be a general framework that is capable of subsuming downstream practical applications (examples 2.4-2.6), to support this claim it's necessary to show a reasonable parameterization and implementation of $\\Phi$ tailored to each of the examples. Otherwise there will be a gap between your theory and application. A related issue is the lack of details on the examples. Concrete details on how these examples are written within your framework in a practical way should be included (at least in the appendix), your last response only included one example and it still lacks details on assumption 2.1.\n\n(2) the eigen-decay condition should be emphasized: I do appreciate your contribution and I didn't say the eigen-decay condition is not valid. However, it's a small subset of the whole infinite-dimensional functional regression problem class, and exhibits nice \"finite-effective-dimension\" like property that mitigates the core difficulty of infinite dimension. The current writing is a bit over-selling in my opinion, and I recommend reflecting the eigen-decay condition in your title.\n\nIn all, I believe the paper can be greatly improved with a thorough re-writing.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind questions, and we would now like to answer your questions in order.\n\n**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 \n$\\Phi= \\lbrace\\phi(x,a,w,s)\\rbrace_{w\\in\\Omega}$. \nThe 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. \n\nWith no prior knowledge about the model class, you can still estimate using any model class.\nIn this circumstance, there will be two types of errors, the first type is **approximation\nerror** 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.\n}\nFor 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 .\n\n**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.\n\n**RE: Assumption 2.10**\nThanks 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})$, \nand if we let $d$ go to $\\infty$, we incur an invalid regret bound. \n\nAssumption 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.\n\nRegarding 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$.\nAlso, 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.\n\nThe 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}\\}$. \n\n**RE: Technical Roadmap**\nWe will write a clear roadmap in the camera-ready version and improve the structure of our paper.\n\nPlease 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.", "claims_and_evidence": "No. I'm mainly concerned about the setting and assumptions. I feel more justification is required.\n\n(1) in assumption 2.1, it's assumed that we have access to a family of basis CDFs, whose (convex) span is guaranteed to contain the ground-truth $F^*$. How do we find such a family without the knowledge of $F^*$? And what kind of oracle access do we have to the family? I feel the family has to be explicitly parameterized by $w$, otherwise for a family with uncountable size, what is a reasonable way to store and access it? The general framework proposed is claimed to be able to subsume previously considered settings (examples 2.4-2.6). However, I feel the examples are not explained in enough details: i.e. what's the basis family $\\Phi$ in each of the example? And do they satisfy assumptions 2.1-2.3?\n\n(2) in assumption 2.10, it's assumed that the eigenvalues are decaying fast enough, dominated by a sequence $\\tau_k$. In my opinion, this is essentially a finite effective dimension assumption, which disenchants the \"magic\" of the infinite-dimensional functional regression storyline, which is the essential contribution of your work. The justification paragraph before assumption 2.10 is farfetched and not convincing (e.g. \"In the analysis of many machine learning algorithms\"). How are the listed references related to this work? Can you provide more direct justifications? In addition, can you explain more on the sequence $\\tau_k$ and why the two constraints make sense? For example, the constraint $\\tau_k=O(\\frac{1}{k})$ seems loose, because $\\tau_k=\\Theta(\\frac{1}{k})$ will contradict the first constraint.\n\nIn all, the technical setting and assumptions should not be casual. I would appreciate more justifications.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No, I'm not convinced by the problem setting and assumptions in the first place.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "It's related to both machine learning and operation research areas.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "I feel the writing is not clear enough: some formulas and math are not necessary for the main-text, please considering moving them to the appendix for more explanatory writing in the main-text. \n\nThe paper's organization is \"straight\", it lists the components one by one, and I get lost between the transitions of these components in the first pass of reading. Please consider adding a concise section explaining the main idea and technical roadmap before section 2.1.", "other_comments_or_suggestions": "NA.", "questions_for_authors": "See 'Claims And Evidence\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IHXNFmKqAW", "reviewer": "Reviewer_Zz7E", "summary": "This paper consider a contextual decision making problem where the context space is infinite but the decision set is finite. Such kind of formulation applies ,for example, in the contextual Multi-Armed Bandit model. The authors focuses on learning infinite CDF functions, that define the distribution over the decision making result. However, they do not consider the general case but rather have assumptions regarding the CDFs e.g., Lipshitz and $\\gamma$-eigendecay.  Beside the linear case, the authors do not mentioned standard distributions for them such assumption applies. The authors define a function-approximation oracle over the CDF function in class, and use it in a iterative-batch-based algorithm that looks identical to the one of Simchi-Levi and Xu 2020 for contextual bandits. They obtain a regret bound that depends on $\\gamma$.\n\n## update after rebuttal\nAfter the rebuttal, although my concerns were partially resulved, I am leaning towrds rejection of this paper for the following reasons:\n\n1. The writing requires a significet improvents; this issue seems to be raised by most of the reviewrs.\n\n2. I agree with the concerns raised by reviewer dr26 regarding assumptions 2.1 and 2.10. They should be justified.\n\n3. In my opinition, the results of this paper are limited to only a small set of function classes that can satiafy those assumptions and  the eigen-decay condition. This was also raised by reviewer dr26.\n\n4. The algorithm is an application of the well known Inverse Gap Weigthening (IGW) technique to the presented setting, hence the algorithmic novelty  is limited.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions. We answer your questions in order.\n\n**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:\n\n$L(\\hat{f}) \\leq L(f^*) + \\text{complexity penalty},$\n\nwhere $\\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. \n\n**Oracle Regret.**\nIn 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:\n\n$\\text{Reg}(T) = \\sum_{t=1}^{T} L_t(f_t) - \\min_{f \\in F} \\sum_{t=1}^{T} L_t(f)$\n\nwhere $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$.\n\nTherefore, oracle regret is not oracle inequality.\n\n**RE: oracle efficiency** Our adaptive algorithm solves uncountable-dimension functional optimization problems efficiently by adaptive approximation with good statistical guarantee.\nERM approach is intractable because it is practically impossible to optimize an infinite-dimensional functional optimization problem.\n\n**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. \n\n**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.\n\n$|\\phi(x,a,r,s)-\\phi(x,a,w,s)|\\le L_0||w-r||_{\\infty}.$\n\nThis assumption could be found in other papers, see arxiv.org/pdf/2007.07876, proceedings.mlr.press/v15/chu11a/chu11a.pdf. \n\nThe 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. \nIn finite dimensions, it assumes $\\theta^*\\in R^d$, $||\\theta^*||_2\\le S$.\n\nOur contribution is not about ** relaxing these conditions.** Instead, we propose a\n**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.\n\nOur theoretical contribution is that we provide **characterization of the\nrelationship 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.\n\n**RE: Pseudo regret** Pseudo-regret is trajectory-based and random; utility regret is its expected version which is common in literature.\n\n**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.\n\nTo 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\n\n$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.$\n\nThis divergence is a UCB.\nAt 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\n\n$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})$.\n\nThen 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. \nWe believe we have addressed your concerns and hope that you will consider raising the score accordingly.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Theoretical analysis of regret.", "theoretical_claims": "Read the text in the main paper - seems sound.", "experimental_designs_or_analyses": "The authors present \"utility-regret\" bound. \nI read the text in the main paper - seems sound.", "relation_to_broader_scientific_literature": "I do not see immediate implications beyond contextual MAB.", "essential_references_not_discussed": "Significant line of contextual RL literature is not discussed in the main paper: contextual MDPs, most of the works in contextual MAB (that has been vastly studied).", "other_strengths_and_weaknesses": "Strengths:\nInteresting research question.\n\nWeakness:\n1.The writing requires improvement: the order of things makes it hard to follow, very technical paper with significant lack of intuition behind it and insignificant comparison to related work.\n2 The actions comes from a finite set? How this result is different from other papers in CMAB literature that consider infinite context space? Why do not extend the result to infinite action space as well?\n3.See questions to the authors.", "other_comments_or_suggestions": "See questions and Weakness.", "questions_for_authors": "1. What is \" oracle inequality\" ? You mean oracle regret?\n\n2. Is the proposed oracle efficient? Highlight  the difference of it from the standard ERM oracle. Why this oracle is used instead of standard ERM?\n\n3. As far as I understand your approach, you established some kind of confidence bound around the distribution approximation. Is that correct?\n\n4. Foster and Rakhlin (2020) also considered in the second part of their work and infinite context space. Please compare yourself to their results.\n\n5. Since you assume both boundness and Lipchitzsness, the contribution is unclear to me. There are works (e.g., Modi et al. (2018)) that considers such settings. Please state your contribution clearly. \n\n6. What is the difference between \"utility-regret\" and the standard contextual pseudo regret?\n\n7. From the algorithm it seems that the actins space is finite, and only the context space is infinite. How does this improve over existing literature? For example, the work for Simchi-Levi and Xu (2021) can be easily extended to infinite context space using a dimension that capture the context-space complexity. Since you already have boundnesses and Lipschitzness assumption, the contribution is unclear to me given previous literature that can be applies to the more general case of infinite context space.\n\n8. Have you tried to consider also infinite action space? It seems the work of Zhu et al. (2022) cover both for bi-linear contextual bandits.\n\n[1] Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles, Foster and Rakhlin (2020).\n\n[2] Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability, Simchi-Levi and Xu (2021).\n\n[3] Contextual Bandits with Large Action Spaces: Made Practical, Zhu et al. (2022)\n\n[4] Markov Decision Processes with Continuous Side Information, Modi et al. (2018)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: This paper presents a general framework for contextual online decision-making by combining well-established techniques from statistics and the bandit literature. The proposed approach, based on infinite-dimensional functional regression and inverse gap weighting enables a unified approach to various contextual online decision-making problems. However, reviewers have raised several important concerns. Firstly, the clarity of the writing must be improved. Secondly, the practical application of the proposed method, especially the crucial aspect of selecting an appropriate basis family in real-world scenarios, may be difficult. Finally, the scope and applicability of the assumed eigendecay conditions warrant a more detailed discussion and analysis.
Decision: Accept (poster)