Follow-ups Also Matter: Improving Contextual Bandits via Post-serving Contexts
Authors: Chaoqi Wang
Ziyu Ye
Zhe Feng
Ashwinkumar Badanidiyuru
Haifeng Xu
Venue: NeurIPS 2023 spotlight (2023)
Keywords: linear stochastic bandits
online learning
partial information
contextual bandits
TL;DR: This study presents a new algorithm that improves the contextual bandit problem by using post-serving context, demonstrating superior performance on various data sets.

Abstract: Standard contextual bandit problem assumes that all the relevant contexts are observed before the algorithm chooses an arm. This modeling paradigm, while useful, often falls short when dealing with problems in which additional valuable contexts can be observed after arm selection. For example, content recommendation platforms like Youtube, Instagram, Tiktok receive much additional features about a user's reward after the user clicks a content (e.g., how long the user stayed, what is the user's watch speed, etc.). To improve online learning efficiency in these applications,  we  study a novel contextual bandit problem with post-serving contexts and design a new algorithm, poLinUCB,  that achieves tight regret under standard assumptions. Core to our technical proof is a robustified and generalized version of the well-known Elliptical Potential Lemma (EPL), which can accommodate  noise in data. Such robustification is necessary for tackling our problem, though we believe it could also be of general interest.
Extensive empirical tests on both synthetic and real-world datasets  demonstrate the significant benefit of utilitzing post-serving contexts as well as the superior performance of  our   algorithm over the state-of-the-art approaches.

Follow-ups Also Matter: Improving Contextual
Bandits via Post-serving Contexts
Chaoqi Wang'
Ziyu Ye! Zhe Feng²
Ashwinkumar Badanidiyuru' Google Research²
Haifeng Xu'
University of Chicago!
Google
{chaoqi, ziyuye, haifengru)@uchiccan edu
{zhef, ashvinkumarbv/@gogllee com
Abstract
Standard contextual bandit problem assumes that all the relevant contexts observed before the algorithm chooses an arm. This modeling paradigm, while useful, often falls short when dealing with problems in which valuable additional context can be observed after arm selection. For example, content recommenda- tion platforms like Youtube, Instagram, Tiktok also observe valuable follow-up information pertinent to the user's 's reward after recommendation (c.g., how long the user stayed, what is the user's watch speed, etc.). To improve online learning efficiency in these applications, we study novel contextual bandit problem with post-serving contexts and design a new algorithm, poLinUCB, that achieves tight regret under standard assumptions. Core to our technical proof is robustified and generalized version of the well-known Elliptical Potential Lemma (EPL), which can accommodate noise in data. Such robustification is necessary for tackling our problem, and we believe it could also be of general interest. Extensive empirical tests on both synthetic and real-world datasets demonstrate the significant benefit of utilizing post-serving contexts as well as the superior performance our algorithm over the state-of-le the-hrt-r approaches.
1 Introduction
Contextual bandits represent fundamental mathematical model that is employed across a variety of applications, such as personalized recommendations (Li al., 2010; Wu et al., 2016) and online advertising (Schwartz et al., 2017; Nuara et al., 2018). In their conventional setup, at each round f, a learner observes the context ær selects an arm a, E A, and subsequently, observes associated reward Ti,a0- Despite being basic and influential framework, it may not always capture the learner
complexity of real-world scenarios (Wang et al., 2016; Yang et al., 2020). Specifically, often observes valuable follow-up information pertinent to the payoff post arm selection (henceforth, the sertise context). Standard contextual bandits framework that neglects such post-serving contexts may result in significantly suboptimal performance due to model misspecification.
Consider an algorithm designed to recommend educational resources user by utilizing the user's partially completed coursework, interests, and proficiency pre-serving context (exemplified in platforms such Coursera). After completing the recommendation, the system can refine the user's profile by incorporating many post-serving context features such as course completion status, how much time spent on different educational resources, performances, etc. This transition naturally delineates mapping from user attributes (i.e., the pre-serving context) to user's learning experiences and outcomes (i.c., the post-serving context). is not difficult to see that similar scenarios happen in many other recommender system applications. For instance, in e-commerce platforms (c.g.. Amazon, Etsy or any retailing website), the system will first recommend products based on the user's profile information, purchasing pattern and browsing history, etc.; post recommendations, the system can
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

then update these information by integrating post-serving contexts such as this recent purchase behaviour and product reviews. Similarly, media content recommendation platforms like Youtube, Instagram and Tiktok, also observe many post-serving features (e.g., how long the user stayed) that can refine the system's 8 estimation about users' interaction behavior as well as the rewards.
A common salient point in all the aforementioned scenarios is that the post-serving context are prevalent in many recommender systems; moreover, despite being unseen during the recommenda- tion/serving phase, they can be estimated from the pre-serving context given enough past data. More formaly, we assume that there exists a learnable mapping (-(+)) Rd, + Rd, that maps pre-serving feature Rd to the expectation of the post-serving feature E Rd= i.e., E[z|a) / (ar).
Unsurprisingly, and as we will also show, integrating the estimation of such post-serving features can significantly help to enhance the performance of contextual bandits. However, most of the existing contextual bandit algorithmss e.g., (Auer, 2002; Li ct al., 2010; Chu et al., 201 I; Agarwal et al., 2014; Tewari and Murphy, 2017), are not designed to accommodate the situations with post-serving contexts. We observe that directly applying these algorithms by ignoring post-serving contexts may lead to linear regret, whereas simple modification of these algorithms will also be sub-optimal. To address these shortcomings, this work introduces a novel algorithm, poLinUCB. Our algorithm leverages historical data to simultancously estimate reward parameters and the functional mapping from the pre- to post-serving contexts so to optimize arm selection and achieves sublinear regret. En route to analyzing our algorithm, also developed new technique tools that may be of independent interest.
Main Contributions.
First, we introduce new family of contextual linear bandit problems. In this framework, the decision-making process can effectively integrate post-serving contexts, premised on the assumption that the expectation of post-serving context as a function of the pre-serving context can be gradually learned from historical data. This new model allows us to develop more effective learning algorithms in many natural applications with post-serving contexts.
Second, to study this new model, we developed a robustified and generalized version of the well-regarded elliptical potential lemma (EPL) in order to accommodate random noise in the post-serving contexts. While this generalized EPL is an instrumental tool in our algorithmic study, we believe it is also of independent interest due to the broad applicability of EPL in online learning.
Third, building upon the generalized EPL, we design new algorithm PoLinUCB and prove that it enjoys a regret bound Ö(T1-a + d, v TK), where T denotes the time horizon and a E [0, 1/2] is the learning speed of the pre- to post-context mapping function ø* (-), whereas d, = dz + dz and K denote the parameter dimension and number of arms. When d'))) easy to learn, e.g.. a = 1/2, the regret bound becomes ÖVVTd, + du (TK) and is tight. For general functions o (-) that satisfy a S 1/2, this regret bound degrades gracefully as the function becomes more difficult learn, i.e., as a decreases.
Lastly, we empirically validate our proposed algorithm through thorough numerical experi- ments on both simulated benchmarks and real-world datasets. The results demonstrate that our algorithm surpasses existing state-of-the-art solutions. Furthermore, they highlight the tangible benefits of incorporating the functional relationship between pre- and post-serving contexts into the model, thereby affirming the effectiveness our modeling.
2 Related Works
Contextual bandits. The literature on linear (contextual) bandits is extensive, with rich body of works (Abe al., 2003; Auer, 2002; Dani al., 2008; Rusmevichientong and Tsitsiklis, 2010; Lu et al., 2010; Filippi et al., 2010; Li et al., 2010; Chu et al., 2011; Abbasi-Yadkori et al., 2011; Li et al., 2017; Jun al., 2017). One of the leading design paradigm to employ upper confidence bounds as a means of balancing exploration and exploitation, leading to the attainment of minimax optimal regret bounds. The derivation of these regret bounds principally hinges on the utilization of confidence ellipsoids and the elliptical potential lemma. Almost all these works assume that the contextual information governing the payoff is fully observable. In contrast, our work focuses on scenarios where the context is not completely observable during arm selection, thereby presenting new challenges in addressing partially available information.

---

Contextual bandits with partial information. Contextual bandits with partial information has been relatively limited in the literature. Initial progress in this area was made by Wang et al. (2016), who studied settings with hidden contexts. In their setup there is some context (the post-serving context in our model) that can never by observed by the learner, whereas in our setup the learner can observe post-serving context but only after pulling the arm. Under the assumption that if the parameter initialization is extremely close to the true optimal parameter, then they develop sub-linear regret algorithm. Our algorithm does not need such strong assumption on parameter initialization. Moreover, we show that their approach may perform poorly in our setup, Subsequent research by Qi al. (2018); Yang et al. (2020); Park and Faradonbeh (2021); Yang and Ren (2021); Zhu and Kveton (2022) investigated scenarios with noisy or unobservable contexts. In these studies, the learning algorithm was designed to predict context information online through context history analysis, or selectively request context data from an external expert. Our work, on the other hand, introduces a novel problem setting that separates contexts into pre-serving and post-serving categories, enabling the exploration of a wide range of problems with varying learnability. Additionally, we also need to employ new techniques for analyzing our problem get near-optimal regret bound.
Generalizations of the elliptical potential lemma (EPL). The EPL, introduced in the seminal work ofLai and Wei (1982), is arguably cornerstone in analyzing how fast stochastic uncertainty decreases with the observations of new sampled directions. Initially being employed in the analysis of stochastic linear regression, the EPL has since been extensively utilized in stochastic linear bandit problems (Auer, 2002; Dani et al., 2008; Chu et al., 2011; Abbasi-Yadkori et al., 2011; Li et al., 2019; Zhou al., 2020; Wang al., 2022). Researchers have also proposed various generalizations of the EPL to accommodate diverse assumptions and problems. For example, Carpentier et al. (2020) extended the EPL by allowing for the use of the X, Pnoomm as opposed to the traditional x,- normm I| x term,
Meanwhile, Hamidi and Bayati (2022) investigated a generalized form of the 1 A [l{();)
which was inspired by the pursuit of variance reduction in non-Gaussie linear regression models. However, existing (generalized) EPLs are inadequate for the analysis of our new problem setup. Towards that end, we develop a new generalization of the EPI. in this work to accommodate noisy feature vectors.
3 Linear Bandits with Post-Serving Contexts
Basic setup. We hereby delineate a basic setup of linear contextual bandits within the scope of the partial information setting, whereas multiple generalizations of our framework can be found in Section 6. This setting involves finite and discrete action space, represented as A = [K]. Departing from the classic contextual bandit setup, the context in our model is bifurcated into two distinct components: the pre-serving context, denoted as E Rdz,, and the post-serving context, signified as E Rd= When it is clear from context, we sometimes refer to pre-serving context simply as context as in classic setup, but always retain the post-serving context notion to emphasize its difference. We will denote X, Σ._ Z + AI and Z, = >1 ===1 _22," + XI. For the sake of brevity, employ u = (z, z) to symbolize the stacked vector of x and z, with dy = d. + d2 and ullp S Lu- The pre-serving context is available during arm selection, while the post-serving context is disclosed post the arm selection. For each arm a E A, the payoff, ra (z, 2), is delineated as follows:
Ta (x. 2) x 0 + z 3% +
where 0; and 3 represent the parameters associated with the arm, unknown to the learner, whereas is a random noise sampled from an -suu--uuussssss distribution. We use ||>||p to denote the p-norm
of a vector æ. and ||~||| A == v Ax is the matrix norm. For convenience, we assume |0] < 1 and || 2 < 1 for all a E A. Additionally, we posit that the norm of the pre-serving and post-serving contexts satisfies ||æ||| < L,z and || | 2 S I.z, respectively, and max SuPo,DEA (0; 0g. .x.) < and maX suPa,bEA (g) Br, 21) < 1, same as in (Lattimore and Szepesvári, 2020).
3.1 Problem Settings and Assumptions.
The learning process proceeds as follows at each time step / = 1,2,....77
1. The learner observes the context Z,-
2. An arm ag E [K] is selected by the learner.
3

---

3. The learner observes the realized reward Ft,a, and the post-serving context, 2;-
Without incorporating the post-serving context, one may incur linear regret as result of model misspecification, as illustrated in the following observation. To see this, consider a setup with two arms, ai and d2, and context x E IR drawn uniformly from the set {-3, -1, 1] with d (x) x². The reward functions for the arms are noiseless and determined as ray (1) = x + x²/2 and Taz (a: - x² =2/2. It can be observed that raj (a) Taz (2) when x: (-3,1) and ray (x) < Taz(2) (z) when z = -1. Any linear bandit algorithm that solely dependent on the context (ignoring
(x)) will inevitably suffer from linear regret, since it is impossible to have linear function (i.e..
r(x) = 0r) that satisfies the above two inequalities simultancously.
Observation 1. There exists linear bandit environments in which any online algorithm without using post-serving context information will have ((T) regret.
Therefore, it is imperative that an effective learning algorithm must leverage the post-serving context, denoted as 2,- As one might anticipate, in the absence of any relationship between 2; and 2;, it would be unfeasible to extrapolate any information regarding 2; while deciding which arm pull, point at which only æe is known. Consequently, it is reasonable to hypothesize a correlation between 2, and xt. This relationship is codified in the subsequent learnability assumption.
Specifically, we make the following natural assumption - there exists an algorithm that can learn the mean of the post-serving context Et, conditioned on æ,, Our analysis will be general enough to accommodate different convergence rates of the learning algorithm, as one would naturally expect, the corresponding regret will degrade as this learning algorithm's 's convergence rate becomes worse. More specifically, we posit that, given the context xy, the post-serving context x, is generated as'
post-serving context generation process: 2 = 6² (aze) + 6t, i.e., (xx) = [[2]ar]-
Here, E; is zero-mean noise vector in Rd, and Φ= Rd, - Rd= can be viewed the post-serving context generating function, which is unknown to the learner. However, we assume 6² is learnable in the following sense.
Assumption 1 (Generalized learnability of d¹). There exists an algorithm that, given pairs of examples {(x zz)) with arbitrarily chosen F. 'ss, outputs an estimated function of o" : Rda -> the following holds with probability least 1 6,
Rd= such that for any x E Rd=,, the
= x)(()) - S Co (1=113+-)) -log (t/8),
where a E 1/2) and Co is some universal constant.
The aforementioned assumption encompasses a wide range of learning scenarios, each with different rates of convergence. Generally, the value of a is directly proportional to the speed of learning; the larger the value of a, the quicker the learning rate. Later, we will demonstrate that the regret of our algorithm is proportional to O(T)~a), exhibiting graceful degradation as decreases. The ensuing proposition demonstrates that for linear functions, a = 1/2. This represents the best learning rate that can be accommodatedf. In this scenario, the regret of our algorithm is O(VT), aligning with the situation devoid of post-serving contexts (Li al., 2010; Abbasi-Yadkorf
al., 2011).
Observation 2. Suppose o(-) is linear function, i.e., Φ(x) = + T x for some t E Rdz xds, then of = = [|==|xx,- log (t/8)).
This observation follows from the following inequalities (())(z)) (x)))
क5.
कb Tell S
= O[|x==] x-- log (!)), where the last equation is due to the confidence ellipsoid bound (Abbasi- Yadkori et al., 2011). We refer curious readers to Appendix D.2 for a discussion on other more challenging d6-) functions with possibly worse learning rates
- 1' -axx_==/xxxx ||,|||,-
'We remark that an alternative view of this reward generation is to treat it function of æ as follows: (x()) 0: + 6² (x) 8 + noise. Our algorithm can be viewed as a two-phase learning of this structured function, i.e., using (ac,, 2x) learn 6' that is shared among all arms and then using learned & to estimate each arm a's reward parameters. This more effectively utilizes data than approaches that directly learns the ra (a) function, as shown in our later experimental section (c.g., see Figure 1).
"To be precise, our analysis regret bound since the regret is already 2 VT), even with knowledge of z. This would only further complicate notation, and therefore, such situations not explicitly examined in this paper.
extend to instances where a > 1/2. However. this would not enhance the

---

3.2 Warm-up: Why Natural Attempts May Be Inadequate?
Given the learnability assumption of ø², one natural idea for solving the above problem is to estimate 6", and then run the standard LinUCB algorithm to estimate (f.: B.)) together by treating (æ,, (2x)) as the true contexts. Indeed, this is the approach adopted by Wang et al. (2016) for addressing similar problem of missing contexts žz, except that they used a different mnsurprised-leaningg-oe approach to estimate the context 2, due not being able observing any data about 2t. Given the estimation of 6, their algorithm - which we term it as LinUCB (Ø) - iteratively carries out the steps below at each iteration t (see Algorithm for additional details): 1) Estimation of the context-generating function (-)- from historical data; 2) Solve of the following regularized least square problem for each arm a E A, with regularization coefficient 2 0:
Ee - Σ
(re.a x, 02 -
+ + (110 B.)) (18.11))
(I)
+E|1;a,=a
Under the assumption that the initialized parameters in their estimations are very close to the global optimum, Wang et al. (2016) were able to show the ((VT) regret of this algorithm. However, it turns out that this algorithm will fail to yield an satisfying regret bound without their strong assumption on very close parameter initialization, because the errors arising from ?(-) will significantly enlarge the confidence set of &2 and Ba.² Thus after removing their initialization assumption, the best possible regret bound we possibly achieve is of order Ö(T3/4), as illustrated in the subsequent proposition.
(0)). The regret of LinUCB-(@) in Algorithm 2 is upper bounded with probability at least 6, by carefully setting the regular- ization coefficient X = ( log (T/6)) in Equation I.
Proposition 1 (Regret of LinUCB-(0))
by Ô (Tl-add di + T1-a/2 / K [d++
Since E [0, 1/2]. the best possible regret upper bound above O(T%/1), which is considerably inferior to the sought-after regret bound of ((vT) Such deficiency of LinUCB-(o) is further observed in all experiments in Section 7 well. These motivate our following design of new online learning algorithm to address the challenge of post-serving context, during which we also developed new technical tool which may be of independent interest the research community.
4 A Robustified and Generalized Elliptical Potential Lemma
turns out that solving the learning problem above requires some novel designs; core to these novelties is robustified and generalized version of the well-known elliptical potential lemma (EPL), which may be of independent interest. This widely used lemma states a fact about a sequence of vectors æ1,'" FT E Rd Intuitively, it captures the rate of the sum of additional information contained in each 2;, relative to its predecessors 21. ".. 2t-1- Formally,
Lemma (Original Elliptical Potential Lemma). Suppose (1) Xo E [Rdxd is any positive definite
matrix; (2) ; PTT E Rd is any sequence of vectors; and (3) X, Xo + Et=ı a.a.. Then the following inequality holds
Σ EIA S 2
det Xr det. Xo
where a A min(a, b) is the min among a, D.
To address our new contextual bandit setup with post-serving contexts, it turns that we will need to robustify and generlaize the above lemma to accommodate noises in D; vectors and slower learning rates. Specifically, we present the following variant of the EPL lemma.
'Specifically, Wang et al. (2016) assume that the initial estimation of ((-) is already very close to (*(-) such that the error arising from o(-) diminishes exponentially fast due to the local convergence property of alternating least squares algorithm (Uschmajew, 2012). This strong assumption avoids significant expansion of the confidence sets, but is less realistic in applications do not impose such assumption.
5

---

Lemma 1 (Generalized Elliptical Potential Lemma). Suppose (1) Xo E B.xd is any positive definite matrix; (2) BI......2 Pr R is a sequence of vectors with bounded l2 norm max, | ll & Lg: (3)
ET: E RR is a sequence of independent (not necessarily identical) bounded zero-mean noises 77 = for any l; and (4) Xx is defined as follows:
satisfying maxt ||= S L, and [[(ErE]]
X, = X1 +
Σ (a, + (z, + c.) E Raxd
E(,,
s=1
Then, for any p E (0, 11, the following inequality holds with probability at least - 8.
Σ [IA )" 2 log"
(det.x..)
XT. det X.
8L2 =x)²² o7
log 32dL2 + Lxn)²
(2)
80
Note that the second term is independent of time horizon T and only depends on the setup parameters. Generally, this can be treated as constant. Before describing main proof idea of the lemma, we make a few remarks regarding Lemma to highlight the significance of these generalizations.
1. The original Elliptical Potential Lemma (EPL) corresponds to the specific case of p 1, while Lemma is applicable for any p E 00, 1]. Notably, the (1 - p) rate in the T term of Inequality 2 is tight for every p. In fact, this rate is tight even for æ; = 1 E R, Vi and Xo 1 E R since, under these conditions, || X
1/t and, consequently,
Σ. ( 1==))) = Ein, to, yielding a rate of 71-P. This additional flexibility gained by allowing a general E [] (with the original EPL corresponding to p = 1) helps us to accommodate slower convergence rates when learning the mean context from observed noisy contexts, as formalized in Assumption 1.
2. A crucial distinction between Lemma and the original EPL. lies in the definition of the noisy data matrix X, in Equation 1, which permits noise. However, the measured context vector 2, does not have noise. This is beneficial in scenarios where a learner observes noisy contexts but seeks to establish an upper bound on the prediction error based on the underlying norse-free context or the mean context. Such situations are not rare in real applications; our problem of contextual bandits with post-serving contexts is precisely one of such case while choosing an arm, we can estimate the mean post-serving context conditioned on the observable pre-serving context but are only able to observe the noisy realization of post-serving contexts after acting.
3. Other generalized variants of the EPL have been recently proposed and found be useful in different contexts. For instance, Carpentier et al. (2020) extends the EPL to allow for the X, P' --norm, as opposed to the x, -norm, while Hamidi and Bayati (2022) explores a generalized form of the 1 A ||<p(x:))) ( x;= term, which is motivated by variance reduction in ann-Gaussian linear regression models. Nevertheless, to the best of our knowledge, our generalized version is novel and has not been identified in prior works.
Proof Sketche of Lemma I. The formal proof of this lemma is involved and deferred to Appendix B. At a high level, our proof follows procedure for proving the original EPL. However, to accommodate the noises in the data matrix, we have introduce new matrix concentration tools to the original (primarily algebraic) proof, and also identify the right conditions for the argument to go through. A key lemma to our proof is high probability bound regarding the constructed noisy data matrix X, (Lemma in Appendix B. 1) that we derive based on Bernstein's 's Inequality for matrices under spectral norm (Tropp et al., 2015). We prove that, under mild assumptions on the noise, || || ب S || x
with high probability for any t. Next, we have to apply the union bound and this lemma to show that the above matrix inequality holds for every 2 with high probability. Unfortunately, this turns out to not be true because when f is very small (e.g.. t = 1). the above inequality cannot hold with high probability. Therefore, we have to use the union bound in a carefully tailored way by excluding all I's that are smaller than a certain threshold (chosen optimally by solving certain inequalities) and handling these terms with small / separately (which is the reason of the second (logg(1)) term in Inequality 2). Finally, we refine the analysis of sthe standard EPL by allowing the exponent p in

---

Algorithm poLinUCB (Linear UCB with post-serving contexts)
1: for I= O, ,,...,,7 do
2: Receive the pre-serving context at
3: Compute the optimistic parameters by maximizing the UCB objective
T
cc. (x(()))) wt)
Lt ((x+t)
arg max
Wa.
(e. x mm X (10
4: Play the arm a, and receive the realized post-serving context as and the real-valued reward
It + 7)-
Vr,az
w
Zt
5: Compute Wt.a using Equation 3 for each a E A.
6: Compute the estimated post-serving context generating function ee(-) using ERM.
7: Update confidence sets C2 (W.r.) and C (0te m:)) for each a based on Equations 6 and
8:
end for
(1 | | 1 )² and derive upper bound the sum Σ (1 (1 )a with high probability.
These together yeilds robustified and generalized version of EPL as Lemma
No Regret Learning in Linear Bandits with Post-Serving Contexts
5.1 The Main Algorithm
In the ensuing section, we introduce our algorithm, PoLinUCB, designed to enhance linear contextual bandit learning through the incorporation of post-serving contexts and address the issue arose from the algorithm introduced Section 3.2. The corresponding pseudo-code is delineated Algorithm 1. Unlike the traditional LinUCB algorithm, which solely learns and sustains confidence sets for parameters (i.e.. 3r and 0, for each a), our algorithm also sinultaneously manages the same for the post-serving context generating function, Ø(-). Below, we expound on our methodology for parameter learning and confidence set construction.
Parameter learning. During each iteration f, we fit the function 2.(-) and the parameters (Gr. laEA and (Br.a)aEAA. To fit (-(.), resort to the conventional empirical risk minimization (ERM) framework. As for JaEA and (aE,) we solve the following least squared problem for each arm a,
3.) = Σ =E)
(re.a 0_0. = T.))²² + > (I10,112 112 + 11..112).
For convenience, we use w and u to denote (0,3) and (x, 2) respectively. The closed-form solutions
to Or.a and Br.a for each arm E A are
00o0 Braa
Li. =
A where A.o AI + Σ u.u. T and
b
Us.
(4)
s:a,=a
8:0,=a
Confidence set construction. At itteration i, we construct the confidence set for (x())) by
C, (ā..2:) = f Rd (( = s
(5)
Similarly, we can construct the confidence set for the parameters Bū,n for each arm a E A by
C, (wir,a
w Rd. w|w Wr A.. S S4,aa
(6)
where G.a = -2 R, du log (1 + Tue (a) further define 6. == A G.a- By the assumption and Lemma 3, have the followings hold with probability at least 1 for each of the following events,
and n²(a) = Σ. 1aa = a). Additionally,
(x,) E C, (5e,
and w* E EC, (w)a.)
7

---

5.2 Regret Analysis
In the forthcoming section, we establish the regret bound. Our proof predicated upon the conven- tional proof of LinUCB (Li al., 2010) in conjunction with robust elliptical potential lemma. The pseudo-regret (Audibert et al., 2009) within this partial contextual bandit problem is defined as,
Rx (eg
Σ (Fe,at Trt,a))
(8)
which we reload the notation of reward by ignoring the noise,
Tt,a = ( a2a) + (9 o² (x+)) and 07 = arg max (0) v2) + (B ( (x:)))
(9)
aeA
crucial to note that our definition of the optimal action, at, in Eq. depends on o (xt) as opposed to 2, This dependency ensures more pragmatic benchmark, as otherwise, the noise present in would invariably lead to linear regret, regardless of the algorithm implemented. In the ensuing section, we present our principal theoretical outcomes, which provide an upper bound on the regret of our PoLinUCB algorithm.
Theorem (Regret of poLinUCB).
The regret of poLinUCB in Algorithmm I upper bounded by Ô TI-ad di d, d.VTK) with probability at least 1 8, if ((logg(166))
The first term in the bound implicated by learning the function o* (+)... Conversely, the second term resembles the one derived in conventional contextual linear bandits, with the exception that our dependency on du linear. This linear dependency direct consequence of our generalized robust elliptical potential lemma. The proof is deferred in Appendix B.2.
Generalizations
So far have focused basic linear bandit setup with post-serving features. Our results and analysis can be casily generalized to other variants of linear bandits, including those with feature mappings, and below we highlight some of these generalizations. They use similar idoos, up to some technical modifications; we thus defer all their formal proof' to Appendix B.3.
6.1 Generalization Action-Dependent Contexts
Our basic setup in Section 3 has single context at any time step t. This can be generalized to action-dependent contexts settings as studied in previous works (e.g., Li et al. (2010)). That is, during each iteration indexed by f, the learning algorithm observes a context øt,a for each individual arm action of pulling arm dr, corresponding post-serving context æt.a, is
E A. Upon executing subsequently revealed. Notwithstanding. the post-serving context for all alternative arms remains unobserved. The entire procedure is the same as that Section 3.
In extending this framework, we persist in our assumption that for cach arm E AA, there exists specific function (.) IRd, + Rd. that generates the post-serving context z upon receiving x associated with arm E A. The primary deviation from our preliminary setup lies in the fact that we now require the function o% (-) be learned for each arm independently. The reward generated as
Tt,a, = (0;, Vt,o,) ) + (Bi, Zt,a.) + Tt.
The following proposition shows our regret bound for this action- dependent context case. Its proof largely draws upon the proof idea of Theorem and also relies the generalized EPL Lemma 1. Proposition 2. The regret of poLinUCB in Algorithm 1 for action-dependent contexts is upper bounded by 5 (T'-"d" "K + d.vTK) with probability at least 1 - 5 if (llog(1/8))
The main difference with the bound Theorem is the additional v K appeared in the first term, which is caused by learning multiple (:(+) functions with e A.

---

3655
((x) - w/ +
1.0
d(x) W sin(k)
2.0 166
4(x) - W'x+D
Cunuistive Regret
0.8
1.5
1.0
0.5
1000
2000 Time steps
3000
4000
5000
0.0
200
400
600
800
1000
0.0
200
400
500
800
1000
Time steps
Time steps
only)
(6)
polnnUC tours)
Figure I: Cumulative Regret in three synthetic environments. Comparisons of different algorithms in terms of cumulative regret across the three synthetic environments. Our proposed pol poLinUCB (ours) consistently outperforms other strategies (except for LinUCB which has access the post-serving context during arm selection), showcasing its effectiveness in utilizing post-serving contexts. The shaded area denotes the standard error computed using 10 different random seeds.
6.2 Generalization to Linear Stochastic Bandits
Another variant of linear bandits is the linear stochastic bandits setup (see, c.g., (Abbasi- Yadkori al., 2011)). This model allows infinitely many arms, which consists decision set D₁ R at time t, and the learner picks an action E Dj. This setup naturally generalizes to our problem with post-serving contexts. That is, iteration f, the learner selects an arm 2; E Dr first, receives reward Te. and then observe the post-serving feature conditioned æt. Similarly, we assume existence of a mapping ("xx,) = E [2 [.,] that satisfies the Assumption Consequently, the realized reward is generated as follows where 0" 3²* are unknown parameters:
Tt. (a,, 0*) + (Ze, 33r) Tl--
Therefore, the learner needs to estimate the linear parameters Ô and 3, as well as the function (-)). We obtain the following proposition for the this setup.
Proposition 3. The regret of PoLinUCB in Algorithm for the above setting is upper bounded by Ö T de + du duvT) with probability at least 1 - ifT = ((log(1/))).
Generalization to Linear Bandits with Feature Mappings
Finally, we briefly remark that while we have so far assumed that the arm parameters are directly linear in the context Ft, Zt, just like classic linear bandits our analysis can be easily generalized to accommodate feature mapping π (xx) and n (2x)
x= (Φ(x:) + 8x). Specifically, if the reward generation process is Ta (0 π x (xt)) + (B: - (z))) + Th instead, then we can simply view E; = x" (xx and E = π (2+) as the new features, with ((xx)) = E., (Ø(xx) + c4).. By working with ,e, E,, S. we shall obtain the same guarantees as Theorem 1.
Experiments
This section presents comprehensive evaluation of our proposed PoLinUCB algorithm both synthetic and real-world data, demonstrating its effectiveness in incorporating follow-up information and outperforming the LinUCB(O) variant. More empirical results can be found in Appendix D.
7.1 Synthetic Data with Ground Truth Models
Evaluation Setup. We adopt three different synthetic environments that representative of range of mappings from the pre-serving context to the post-serving context: polynomial, periodicical and linear functions. The pre-serving contexts are sampled from uniform noise the range [-10, 10]d,, and Gaussian noise is employed for both the post-serving contexts and the rewards. In each environment, the dimensions of the pre-serving context (d.) and the post-serving context (d.) are of 100 and 5, respectively with 10 arms (K). The evaluation spans T = 1000 or 5000 time steps, and each experiment repeated with 10 different seeds. The cumulative regret for each policy in each environment is then calculated to provide a compararison.
Results and Discussion. Our experimental results, which are presented graphically in Figures provide strong evidence of the superiority of our proposed poLinUCB algorithm. Across all setups,

---

observe that the LinUCB (r and 2) strategy, which has access to the post-serving context during arm selection, consistently delivers the best performance, thus serving as the upper bound for comparison. On the other hand, the Random policy, which does not exploit any environment information, performs the worst, serving as the lower bound. Our proposed poL.nUCB (ours) outperforms all the other strategies, including the LinUCB (Φ) variant, in all three setups, showcasing its effectiveness in adaptively handling various mappings from the pre-serving context to the post-serving context. Importantly, poLinUCB delivers significantly superior performance to LinUCB (z only), which operates solely based on the pre-serving context.
7.2 Real World Data without Ground Truth
Evaluation Setup. The evaluation was conducted on real-world dataset, MovieLens (Harper and Konstan, 2015), where the task is to recommend movies (arms) to a incoming user (context). Following Yao et al. (2023), we first map both movies and users to 32-dimensional real vectors using neural network trained for predicting the rating. Initially, K = 5 movies were randomly sampled to serve as our arms and were held fixed throughout the experiment. The user feature vectors were divided into two parts serving as the pre-serving context (dg 25) and the post-serving context (dz = 7)). We fit the function (()) using a two-layer neural network with 64 hidden units and ReLU activation. The network was trained using the Adam optimizer with a learning rate of 1c-3. At each iteration, we randomly sampled a user from the dataset and exposed only the pre-serving context to our algorithm. The reward was computed as the dot product of the user's feature vector and the selected movie's 's feature vector and was revealed post the movie selection. The evaluation spanned T 500 iterations and repeated with 10 seeds.
MovieLens
500
Results and Discussion. The experimental results, pre- sented in Figure 2, demonstrate the effectiveness of our proposed algorithm. The overall pattern is similar to it ob- served in our synthetic experiments. Our proposed policy consistently outperforms the other strategies (except for Lin- UCB with both pre-serving and post-serving features). Sig- nificantly, our algorithm yields superior performance com- pared policies operating solely on the pre-serving context, thereby demonstrating its effectiveness in leveraging the post-serving information.
Random
Cumulativv Regret
LinUCB (x only)
LinUCB (x and 21
300
LinUCe (5)
poLinIICa (ours)
100
100
300
400
Time steps
Figure 2: Results MovieLens.
8 Conclusions and Limitations
Conlusions. In this work, we have introduced novel contextual bandit framework that incorporates post-serving contexts, thereby widening the range of complex real-world challenges it can address. By leveraging historical data, our proposed algorithm, PoLinUCB, estimates the functional mapping from pre-serving to post-serving contexts, Ieading to improved online learning efficiency. For the purpose of theoretical analysis, the elliptical potential lemma has been expanded to manage noise within post-serving contexts, a development which may have wider applicability beyond this particular framework. Extensive empirical tests on synthetic and real- world datasets have demonstrated the significant benefits of utilizing post-serving contexts and the superior performance of our algorithm compared to state-of -tate-of-the-ar the-art approaches.
Limitations. Our theoretical analysis hinges on a crucial assumption that the function d' d²(-) is learnable, which may not always be satisfied. This is particularly a concern when the post-serving contexts may hold additional information that cannot be deduced from the pre-serving context, irrespective of the amount of data collected. In such scenarios, the function mapping from the pre- serving context to the post-serving context may be much more difficult to Iearn, or even not learnable. Consequently, a linear regret may be inevitable due to model misspecification. However, from practical point of view, our empirical findings from the real-world MovieLens dataset demonstrate that modeling the functional relationship between the pre-serving and post-serving contexts still significantly enhance the learning efficiency. We hope our approaches can inform the design of practical algorithms that more effectively utilizes post-serving data in recommendations.
Acknowledgement. This work supported by an NSF Award CCF-2303372, an Army Research Office Award W91 1NF-13N--3-10000 100030, and Office of Naval Research Award N00014-23-1-2802.
10

---

References
Yasin Yadkor,, Dávid Päl, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Naoki Abe, Alan W Biermann, and Philip M Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37:263-293, 2003.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-exploorttion tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876-1902. 2009.
Peter Auer. Using confidence bounds for exploitation-exxllraaton trade-offs. Journal of Machine Learning Research, 3(Nov):397-42) 2002.
Alexandra Carpentier, Claire Vernade, and Yasin Abbasi- Yadkori. The elliptical potential lemma revisited. arXiv preprint arXiv:2010. 10102200000012,, 2020.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings, 2011.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010.
Nima Hamidi and Mohsen Bayati. The elliptical potential lemma for general distributions with application to linear thompson sampling. Operations Research, 2022.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (ftis) 5(4):1-19, 2015.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
Tze Leung Lai and Ching Zong Wei. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics, 10(1): 154-166, 1982.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bande approach to personalized news article recommendation. In Proceedings the 19th international conference World wide web, pages 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173-2174. PMLR, 2019.
Tyler Lu, Dávid Pál, and Martin Pál. Contextual multi-armed bandits. In Proceedings the the Thirteenth
international conference on Artificial Intelligence and Statistics, pages 485 JMLR Workshop and Conference Proceedings, 2010.
Alessandro Nuara, Francesco Trovo, Nicola Gatti, and Marcello Restelli. A combinatorial-bandit algorithm for the online joint bid/budget optimization of pay-per-elick advertising campaigns. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
11

---

Hongju Park and Mohamad Kazem Shirani Faradonbeh. Analysis of thompson sampling for partially observable contextual multi-armes bandits. IEEE Control Systems Letters, 6:2150-2155, 2021.
Yi Qi, Qingyun Wu, Hongning Wang, Jie Tang, and Maosong Sun. Bandit learning with implicit
feedback. Advances in Neural Information Processing Systems, 31, 2018.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411,, 2010.
Eric M Schwartz, Eric Bradlow, and Peter Fader. Customer acquisition via display advertising
using multi-armed bandit experiments. Marketing Science, 36(4):500-52,, 2017.
Ambuj Tewari and Susan Murphy. From ads to interventions: Contextual bandits in mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, pages 495-517, 2017.
Ryan Tibshirani. Nonparametric regression (and classification). 2017.
Joel A Tropp et al. An introduction to matrix concentration incqualities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
André Uschmajew. Local convergence of the alternating least squares algorithm for canonical tensor approximation. SIAM Journal on Matrix Analysis and Applications, 33(2):639-652, 2012.
Huazheng Wang, Qingyum Wu, and Hongning Wang. Learning hidden features for contextual bandits. In Proceedings of the 25th ACM international on conference on information and knowledge management, pages 1633-1642, 2016.
Huazheng Wang, Haifeng Xu, and Hongning Wang. When are linear stochastic bandits attackable? In International Conference on Machine Learning, pages 23254-23273, PMLR, 2022.
Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in collaborative environment. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 529 529-538, 2016.
Jianyi Yang and Shaolei Ren. Robust bandit learning with imperfect context. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10594-10602, 2021.
Shangdong Yang, Hao Wang. Chenyu Zhang, and Yang Gao. Contextual bandits with hidden features to online recommendation via sparse interactions. IEEE Intelligent Systems, 35(5):62-72, 2020.
Yun Yang and David B Dunson. Bayesian manifold regression. 2016.
Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. How bad is top- recommendation under competing content creators? International Conference Machine Learning, 2023.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
Rong Zhu and Branislav Kveton. Robust contextual linear bandits. arXiv preprint arXiv:2210.14483, 2022.
12

---

A Algorithm and Regret Analysis of LinUCB(
We present the details of the algorithm described in Section 3.2 and the proof of the regret bound.
A.1 Main Algorithm
We consider solving the following regularized least squared problem for estimating (Or, and (BraJaEA for each arm a:
Parameter learning.
(.0.. - Σ (raa- x 00 -1. (0.) + A (110, 11.
(10)
sin,mo
where À 2 0 penalty factors ensuring the uniqueness of minimizers 0i,a and 3r.a.
In the same convention, we use w to denote (0, (). and u to denote (z, (x) The closed-form solutions for G., and Br,a in this least squared problem then become:
0 0r,a
Wta
A br.a1
3r
where we reload the notations of Ar, and bia.
A A
Σ u.u.
and
bi,a
Σ Ta.a Ug
(11)
Confidence construction. At iteration we construct the confidence set for क. (ax) by
C, (or 2.) = f = Rd (o ( S og
(12)
The construction of the confidence set for wi will be different, as we using the predicted value (.) for linear regression. Consider the following.
Ar,
(
Braa
[0:
=
c,
3
Φ (Ixz)
1)
Σ
((0(z))) Bi
- -z.
(2x))
x.
=a
sta, =aa
Σ ns
Dg (xx
0 A
B
810, =00 =
4
Therefore, the confidence set will be enlarged due to the error introduced by Z.(.). the below, we derive the confidence set. To build the confidence set, we need to bound
iuita wi, lA.
0r.a
0
+ 2
3r
Since both (e =1= and {n ) are i.i.d sub-Gaussian random variables, respectively, we use the nelf-normalized inequality to bound the corresponding terms, i.c., the followings hold with probability at least 1 22.
det det(Arr,))4 det det(AA)
L
||ūta - wiaalA <
2(L2 + R2)) log
Σ
5/t
+
+2VA
5/2
VÁ
1 + L2/11
Lu
<
2(L2 + R2) log
+
Σ
8/t
+ 225
8/2
VA
d=1
13

---

Algorithm 2 LinUCB-(Q) (Linear UCB adapted from Wang et al. (2016) with post-serving contexts; The differences with Algorithm are highlighted in blue color)
1: for 0, ...., do
2: Receive the pre-serving context Et
3: Compute the optimistic parameters by maximizing the UCB objective
Lc. ox (3xe) wix)
arg max (o.g...)E(K)xC,. ($1-1 ai XC (80 1,.)
6(x+))
Wa-
4: Play the arm a, and receive the realized post-serving context as 2t and the real-valued reward
Dt
Tr,az
wa, Th-
5: Compute the estimated post-serving context generating function (e(-) using ERM.
6: Compute ir by solving Equation 10 for each a.
7: Update confidence sets C₂ (w.r.)) and C,(0r. æt) for each based on Equations 12 and 5.
8:
end for
Therefore, the confidence set
(,a(wraa) {w E Rd || @iaallae. Straa:
(13)
where Gr.a V 22 + R2) ((1 + (()()(//))/((//2) + Tu (Ein / + 2VT. In comparison the original confidence set, there one additional term due the generalization error introduced from (-). In the next section, we will provide a regret analysis, which following from the proof of LinUCB (Li et al., 2010). We simply have the following
T
RT (reat rt,a.)
A
i., - 0o, Ba. Ba.
(T)(2x))
10 (axt)
3a.
+
(xxz)
Zt
A
Ar-1.s
T
o (ax)) |
Ban
+ 267,a
I
Et
(xx))
AT
Σ (xx.) o+ (2x 2|
2
|A
2
T
Bo.
+ +267
~ (xxx))
Ai
T.
(SC 20 log2n
det Xe det Xo
log?
T
+ 2K (g log
1+
TL3
Adu
In the next, we expand the term G
2
5 1 + R2) log
1+ TL3/A
Tu
ET e3/2
+
2V
8/2
1 TTT/A/A
3L2
T Σ
5 6(L2 + R²) log
+
5/T
+ 12A
8/2
X
4=/
14

---

In the next, we bound the second term in the above equation under the learnability assumption 1,
T Σ c
det XT det Xo
T
167 20x log
log²
Therefore, naively choosing the value of will lead to a linear regret due to the term 78/2-a equation. To minimize the upper bound, choose the value of À to be
dct X₃ (dct det Xo
T
A = T log"
log 8
Then, we can bound Ç by
1 + TL
det
Xx
T
G 5
+ R2) log
48L,T72-100
log
6/2
det Xo
By plugging it in and following the simplication in the proof of Theorem 1, we can get the regret is upper bounded by
δ (T
T1-0/2 TT Kdd+a)
The above result summarized the following proposition.
Proposition 1 (Regret of LinUCB-(0)). The regret of LinUCB-(0) in Algorithm 2 is upper bounded
di by Ō d + TTl-l//22 Kd,+t with probability at least 6, by carefully setting the regular-
ization coefficient X = (Ln log (T/6)) in Equation I.
B Missing Proofs
B.1 Missing Proofs in the Generalized Elliptical Potential Lemma
Lemma (Generalized Elliptical Potential Lemma), Suppose (1) Xo Rdddd any positive definite matrix; (2) æ1,.... 2T Rd is sequence of vectors with bounded 2a norm max, | & T.z (3) El....,ET ET E IRd is sequence of independent (not necessarily identical) bounded zero-mean noises satisfying max, ||=x|| < L, and [[E,,e]] b of for any l; and (4) X, is defined follows:
x X1
E(,, + (xx, To Rdxd
Then, for any p E [0, 1), the following inequality holds with probability at least - 8,
L ( 2"p log"
det X det Xo +
8L3(L.
o² log
L.)) 33dLL (L. + L.x)²
(2)
dot
Proof. Our proof follows the high level idea for proving the original EPI. However, to accommodate the noises in the data matrix, have introduce matrix concentration tools to the original (primarily algebraic) proof, and also identify the right conditions for the argument to go through. A key lemma our proof is the following high probability bound regarding the noisy data matrix:
Let æi,..., T..,.TTTTTT FT E Rd be a fixed sequence of vectors, and Ei. ET Rd are independent random variables satisfying max, ||æell2 & Lzz, max; |all2 & Lo and Elcec b IoI. Then the -To²
Lemma 2.
following hold with probability at least 1 - exp (L,
I
T
Σ
a + E2) + Tx) x
Tx
15

---

The Proof of Lemma 2 employs the Bernstein's 's Inequality for matrices (Tropp et al., 2015), which is technical; for ease of presentation, we defer its proof of Appendix B.1. By Lemma we have that, too
for every t [T), the following inequality holds with probability at least 1 - 2d exp (L.
X, Xo + Σ (ss + E2) + +.E) Xo + Σ
Lz = X1,
am
under which we have
x x+ S
[2++1 x
To prove our Lemma I, we need to apply union bound to guarantee the above hold simultancously for every 2 1 with high probability. Unfortunatcly, this turns out to not be true because when t is very small (c.g., = 1), the above incquality cannot hold with high probability. Therefore, to obtain high-probability guarantee by the union bound, we will have to exclude these small t's and apply the union bound for only the events from some t' E [T], as follows
E TT, P P
|00
2 1 2 l1 x
T-1
-00?
2 1
Σ
2dexp
(812(Le )2
(=P-1
20
t (812(T. + )2
21 2 Σ
2dexp
(=f-11
exp ( (I' - 1)o (8T. +zz)))
= 1 - 2d
1 - exp (81.81 + [2z)
16L2 + Lz)²
2 1 - 2d x exp (- (L' 1)o (8L + (z)))) x
where the last inequality uses the fact that of / (L2 + (z) s (o./ S and 1 x 2 x/2 for any x E [0, 1). By solving the following inequality,
16L2 -.,)²
exp ( (1 10o + bz))))
o7
2nd
we have,
2 1+ SL. + 12
32dL? + Lx)² )2
of log
do!
Let To denote the ceiling of the sight-hand-side of the above term. Therefore, we have the following hold with high probability at least 1 - 6:
1A E 2 xx-1 ) 11)+ Σ (I | )=
1=To
< <To - 1)+ Σ
(I || )
T=To
T
S (To 1)+
Σ T=T.
(I^ | (x==:))))
In the next, going bound the second term in the above equation, whose proof can be adapted from the proof of the original elliptical potential lemma. Using the fact that for any 2 E [0, +o0],
A 21 + 2). we get
T
T
Σ La (Icc.
)²=
p
Σ
22 (1 + ||2 13x;,,
16

---

Additionally, by definition, we have
X, x - 2 = x i-1 (I+Xi11 xx a x 112) x
This implies the following relationship between the determinant,
( 2 X, (2) det X, det (Xx-1) det (I x
Since the only eigenvalues of matrix of the form yy" 1 1+ |///22 and 1, we have
log [1 | (
log det X; log det X
By taking the power p for both sides and taking the sum, we have
T (log (1+ ||x: ||
T
Σ
Σ
(log det X, log det X(-1)².
Since E [0, 1]. the function g(x) xx is concave function. Thus, we have
P
det Xr det Xo
(log det X, log det XI-1)*
log det X, - log det X(-1)
log"
T
TD
Therefore, we can conclude that
T E (1E
det XT det Xo
By combining the above results, have the following hold with probability least 8:
Σ 11
))
Soo To 1 Σ I || [x
S To + 2PT log
det XT det Xo
Invoking
To 8L2 + Lx)²
32dL + L )2)
log
of
80
we obtained the desired inequality with probability at least
1
LA M x, +
det Xx det Xo
8L2(L, + L2) log
32dL2 + L
S 2PT
of
80
Lemma 2. Let FT, .... ET E Rd be fixed sequence of vectors, and .I...., E are independent random variables satisfying max, ||æe||2 I Lzz max, ||ll2 S Lo and Elcee, > o². Then the following hold with probability least 1 - 2d exp
Too
5L:(L.th.)
I
T
Σ
a + +xx
+ + x
Σ x1
Proof. We will analyze the term-wise difference, denoted
S, (æ., <x) + TT) x,,0, e 2.E; + tETE]
(14)
Moreover, since E(e,] = for any t E [T]. the expectation of S, (over randomness of noise) can be lower bounded
S = E( + E. + E(gcC] E(c,c,1 b T²I.
17

---

Since ||æ,|la I L and 1e I Le, we know that S, क (2L. Lz + L with probability 1. Thus S, uniformly upper bounded under the spectral-none denoted by || ||, or formally
| S 21 + E.
Consider the "centered" matrix sum Z7 Σi= S. - F(GG)) with mean 0. Since the spectral-
norm of St is upper bounded by 2L, Lo + L2. its variance V(S)) - || |S.S |l is upper bounded by (2 + -2)². Thus, the variance of Zr equals the variance of sum Σ/m S, which is then upper bounded by T(2 + r.2)a. By the Bernstein's Inequality
random matrices (Tropp et al., 2015), we have the following high probability upper bound for the spectral norm of Zr:
-12/2
Zrll 2 4 < 2d exp
(15)
v(Zr) + (2 + L2)2/3)
Since Zr a symmetric matrix, its spectral norm upper bounds the absolute value of any eigenvalue. Thus can lower bound the smallest eigenvalues follows:
T
P ||| Zrll
P
Amia
Σ S, Elere,
s-1
1=1
T
P
Amiu
Σ
S 0:1
-
[=1
T Σ S:
P
Amin
< <To?
where the second inequality is due to two facts: (1) A > B implies (Ain(A) 2 Amin (B) where
= ET= St - and B [T S - E(e,e]]) and (2) the event Amin S - thus is included within the event Amin (B) S -t. Consequently, we have
-12/2 s 2d 2d (((ZT) (2L.Lz 12)013)
P Amin
Es
Ss TTo
or equivalently,
-22/2
Amin
Σs: S:
2 To²
21 2
((ZT) + (2 + L2)//3)
1=1
By choosing the value of v = To?, we get
P Amiu
Σ S 2 0
-T
1 2dexp
v(Zr) + (2 - L2)ToO/33)
-T"00/22
2 2dexp
T(2T. + +.222 (2 Tog 12)To?/3
Using the fact that a. S Le, we can further simplify the above equation by
-To! 882(LL + La)
P
Amin
Σ St
0 1 1-22exxp
18

---

B.2 Missing Proofs in the Regret Analysis
Theorem 1 (Regret of poLinUCB). The regret of poLinUCB in Algorithm I is upper bounded by Ô aT--dd du (KVT with probability at least 1 8, if ((log(1/6)).
Proof. In the next, we prove the regret bound. For each time step f, the immediate regret
A rt,o; Pr,at
3t
0a;
d1
0 (xr4)
Ba; B
On. 0%
(00(2z)) 80 (2)))
Ør (xt
Ba Pag
0
21
0a, 0z
20 (2x4)
(0((x1))
Ba, Br,
(o)()t) 50 (2x)), Bos
<10 2t
On. 0z
(
Ba, - B
(b)
2 (00 - 0zxz)|
+
at
On, 0%
Φ (20))
Bar B
(2) (x(x))) 20 xxxx)) ||.
2t (xx:)
0., 0
+
x-
Bo. - 3
Ac-1.0
where the inequality (a) due to the definition of UCB, and (b) and (c) are obtained using the Cauchy-Schwarz inequality. Therefore, the cumulative regret can be further upper bounded by
T T
R
A
S
A
t=1
(Tl(2x)) x² (ax)
| +
x2 |1)m)()))))
i.. 0a,
(2xa))
Ba, - Ba.
A 11
T
Bo.
1
+ +
St
2
x) (x:t)
AT 2,me
T Σ
(xx))
||
|
|2
+ 2Ç}
[I^]]
2
(x:)
AZ
In the next, we bound each term separately, Firstly, we have the following hold with probability at least 1 by using the union bound.
T
Σ [e( - (xx))
|
|| <8
c/ (
In the next, to bound the remaining term, we use the result from Lemma 1. We first group the sums based the arm,
En
-
E
Vn
Et (2x))
(mx))
(16)
1=1
AT-L. tE
ATLL.
By denoting ny (a) as the number of times that arm a is pulled, we can divide the arms into two groups
Go = fa E A:: ( = ((log(1/8) and g = A No
19

---

Then, we can further decompose the r.h.s term of Equation 16 based on if the corresponding arm is in Gn or GT. Then, by applying Lemma we have the following holds, with probability at least 8.
Σ am
E
zt (2,,)
A
2
]
Σ
IA
Σ
Σ
1
E1
0* (x))
(0'
aEGo tE(T)aamma
A,
OE
Ne(T].n,ma
AT-1.a
T
SKL + 12x)
32K d, [2 + L8)
<2Kd, log
1
log
Ad
o²
80
where the last inequality due Lemma and apply the union bound the K arms. To bound the remainder term, since E [0, 1/2], by the learnability assumption as stated in Assumption and Lemma we have
T
2
<
T
(111001(221) C
20
log²
tT
1=1
T
$ 40 22 log
2a
log²
det Xo
8
TL / + A
(T'
$ 4C 2a Len log 20
log²
8
Therefore, the total regret bound is bounded by the following term with probability at least 25,
(T. (SCoTI-2a log
det Xx det Xo
log"
T
KCJ
dh log
1
TLL
48L: ob
log
192Kd.LALL
Ada
do?
By hiding the logarithmic terms, we can further simplify it to be
Tl da + dh VTK)
B.3 Missing Proofs in Generalizations
Proposition 2. The regret of poLinUCB in Algorithm for action-dependent contexts upper bounded by δ (r & V + d dTK with probability least 5 if = (llo((1)))
Proof. Our proof follows from the proof of Theorem 1. The immediate regret at each time step / is
A Ft,a; Tt,as
(17)
Recall that the definition of az
af = arg max 0 Tr,a) + (3 (2
(18)
aEA
To bound the immediate regret, have
A, (0;; Ft.at) + (3;; 0 (2),, )) (0 Dr,a,) (gt Hz, (2r,,,)))) By the definition of UCB, further have
(19)
A < (t... Vt,aa) (Br.ar Ti (xt,a))) (0: Dr,ae) (Bi &2, (Iir,))):
(20)
By rearranging the terms, we get
A < (0..r 0; Vt,ao) + (3r,, Bá, ot, (z)),))) )) + (Bras Pt.a. (II dū, (zt,a.))
(21)
20

---

Bounding the first term 1 is the same the proof in Theorem 1, while bounding the second term now have K such functions of (2(+) for A to learn. By denoting the error for each estimate of (-)-) at iteration as eL,a- Therefore, the contribution from the second term to the total regret can be bounded by
2 will be slightly different,
6/t (tas)
Σ
E
1/8) eta
(22)
del XT det Xo
T ④
S 4KC log
log*
(23)
Hence, by following the remaining steps in the proof of Theorem can conclude that the regret is upper bounded by
Ō de VK + du (TK)
(24)
where the only difference is the additional VK appeared in the first term.
Proposition 3. The regret of poLinUCB in Algorithm for the above setting is upper bounded by δ T du du (TT with probability at least ifT 12(log(1/8)).
Proof. This proof also follows from the proof of Theorem 1. The immediate regret at each time step
t
A = Ti,2] Ti,x,
(25)
Recall that the definition of 2j,
x = arg max (0", x)) + (x)))
(26)
To bound the immediate regret, have
A, (0 xt) , (x;)) (0* x.) (0* (xxx))
(27)
By the definition of UCB, further have
A, S (0,, xi) (Ge, (x,))) (0" xx)) - (B", o (xx)).
(28)
By rearranging the terms, get
A < 0 0" xx) + (B: B o² (xt)) + (Be, (((1)) - (xx))
(29)
Since we only need to single 0r, B and x²( (.). We thus have the following bound for the total regret,
δ T - du + do dovT))
(30)
C Technical Lemmas
Lemma 3 (Confidence Ellipsoid, based on Theorem 2 of (Abbasi-Yadkori Yadkori et al., 2011)), Let wn E Rdd Vo = AI, X O. For any L 2 0, lei uI,... Ur E Rd, define It = (ur, w-) ) + 1tt where Gaussian and assume that ||w*||2 S Lww let V. = Vo + Et= corresponding regularised least-square estimator: Then, for any 8 > 0 and t 0, with probability at least 1 8, w" lies in the set:
Ii is Ruyssub-Gaussian
== u.u, and w, be the
det (V.) det( 11/2
C. Rd :112; wllv, S VALw + Boy 2
(31)
21

---

Furthermore, for all t 2 1, |u S Lu, then any 8 > 0 and 2 0, with probability at least
1 6, w" lies the set:
1 1
C = w E RR |1eb wllv S VAlw + Ray dlog
(32)
Lemma (Bernstein's Inequality for Matrices, Theorem 6.1.1 of (Tropp et al., 2015)). Let Xi.... X,, E Rdi xd2 be independent and centered random matrices. Assume that for each i E [n]. X, is uniformly bounded, that is:
[X and
(33)
where ||
denotes the spectral-norm distance here. Introduce the sum
Z - X
(34)
and let (Z) denote the matrix variance statistics of the sum Z:
v(Z) = max
{IlE [ZZ]
11, IEE 2 2
||}
(35)
Σ x
Σ X
x
max
(36)
where the asterisk" denotes the conjugate transpose operation. Then, for every e 2 O, we have,
222/2
P P(1Z (d)++ d2) exp (v())+ + BB/33
(d1
(37)
22

---

Comparison Convergence Rates
10
Convergence
10-4-
Liner jo- 0.307
Hilder (5 05.d 31:7 77
-5
23 3
10
Number
Figure 3: Comparison of convergence under different & functions (c.g., linear and those in Holder space).
10
#al W
#00 W alhoo
Ui-E (6)
poú-UCC (curs)
25
(ISIC and
LInICC enyy
Curulaaion avvv Regret
0.6
Li-Uca igt
Cumulative
porricc bust
2.5
only
0.6
1030
2000
.000
4000
5000
200
410
603
600
1003
Time steps
Time steps
Figure 4: Comparison under the setup where the reward's dependency on the post-serving context
noiseless.
D
Additional Results and Discussions
D.1 Additional Experiments
We further investigate the case where the true reward is ( (2)), For this case, the reward's dependency the post-serving context noiseless. The results are presented in Figure 4. We observe that the algorithm adapted from Wang et al. (2016) still performs worse than our method, though the gap seems become smaller.
D.2 Additional Discussions Assumption
Our regret amalysis accommodate different values of a in Assumption 1. The rate of 1/VT (when a = 0.5) is a commonly observed rate for many classical machine learning algorithms, including linear regression, logistic regression, and SVM with linear kernel. This rate is rooted in the law of large numbers and the central limit theorem. For smaller a values, the generalization error will converge more slowly than 1/VT, indicating that the learning problem becomes increasingly difficult. In the extreme case when 0, ø² function cannot be learned accurately, thus will inevitably suffer linear regret (simply due to model misspecification)
For standard linear functions, However, we intentionally made assumption to be more general in order to accommodate other much more complex ways of estimating the & functions such manifold regression (see, e.g., Yang and Dunson (2016)), non-parametric ways like k-nearest-neighhor to estimate phi, or to estimate complex non-smooth function (e.g.. functions in Holder spaces). For example, when á is function in Holder space H()., then the learning rate is 7 (225/(2+4)) which is generally slower than 7-0.5 and depends on 3 as well as the data dimension d (see, e.g., the note of Tibshirani (2017)). visual illustration be found in Figure 3.
0.5 and our regret bound in such situations is tight w.r.t.
23


Reviews:
[{"review_id": "dqguX8diux", "reviewer": "Reviewer_3eSw", "summary": "This work considered a novel contextual bandit problem with post-serving contexts and designed a new algorithm, poLinUCB. With a generalized version of Elliptical Potential Lemma (EPL), they provided tight regret under standard assumptions. Empirically, they showed on synthetic and real-world datasets, the proposed algorithms outperformed LinUCB with different types of contexts. ", "questions": "- Can you provide a detailed discussion of how Assumption 1 will be realised when phi is not a linear function: how alpha will change, how regret bound would be? \n- Can you test in synthetic experiments for more types phi functions, to verify the discussion above? \n- would the form the phi function influence the parameter learning in Eq. (3)? \n- what if phi function depends on contexts? e.g. for different users, different types of contexts can be observed before and after serving, and those contexts can have different relationships. ", "limitations": "As mentioned by the authors in the appendix, this work heavily relies on Assumption 1 and the relationship between pre- and post-serving contexts. In practice, those assumptions may not hold. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written and organised. Easy to read and well-defined notation. \n- The proposed new setting of contextual bandits is valid, interesting and well-motivated. The analysis of natural attempts fails provided good support evidence for the new proposed algorithm. \n- A generalised elliptical potential lemma (EPL) is proposed and well-explained. Can be an independent interest. \n- A regret bound is provided with parameters introduced in assumptions, with a clear description that how the parameter can be realised for the proposed algorithm. \n- The generalisations to action-dependent contexts, Linear Stochastic Bandits and Linear Bandits with Feature Mappings are interesting and useful extensions of the proposed setting. \n- Comparison to related algorithms in empirical is provided on both synthetic and real-world datasets. ", "weaknesses": "The regret analysis replies to Assumption 1 -- Generalised learnability of phi^ast, and the regret bound depends on the value of alpha. It is not clear when phi is not a linear function, how alpha will change. For example, when alpha approaches 0, the regret bound will approach linear regret. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the thoughtful comments! Below please find our detailed responses to the questions below.\n\n\n\n**Re: weakness 1, Q1 \\& Q2** Our regret analysis can accomodate different values of $\\alpha$ in Assumption 1, which we would view it as a strength rather than weakness. The rate of $1/\\sqrt{T}$ (when $\\alpha=0.5$) is a commonly observed rate for many classical machine learning algorithms, including linear regression, logistic regression, and SVM with a linear kernel. This rate is rooted in the law of large numbers and the central limit theorem. For smaller $\\alpha$ values, the generalization error will converge more slowly than $1/\\sqrt{T}$, indicating that the learning problem becomes increasingly difficult. In the extreme case when $\\alpha = 0$,  $\\phi^\\star$ function cannot be learned accurately, thus we will inevitably suffer a linear regret (simply due to model misspecification). \n\nFor standard linear functions, $\\alpha = 0.5$ and our regret bound in such situations is tight w.r.t. $\\alpha$. However, we intentiaonally made assumption 1 to be more general in order to accomodate other much more complex ways of estimating the $\\phi$ functions such as manifold regression (see, e.g., Yang \\& Dunson, 2016.), non-parametric ways like k-nearest-neighbors to estimate phi, or to estimate complex non-smooth function (e.g., functions in Holder spaces). For example, when $\\phi$ is a function in Holder space $H(\\beta)$, then the learning rate is $T^{-2\\beta/(2\\beta + d)}$, which is generally slower than $T^{-0.5}$ and depends on $\\beta$ as well as the data dimension $d$ (see, e.g., the note of [Tibshirani and Wasserman, 19] below). The reviewer can also find a visual illustration in the Figure (1) of our uploaded PDF.\n\nYang, Yun, and David B. Dunson. \"Bayesian manifold regression.\" (2016): 876-905.\n\nTibshirani, Ryan and Larry Wasserman. \"Nonparametric Regression\", Statistical Machine Learning, Spring 2019 \n\n**Re: Q3** The Eq. (3) is independent of $\\phi$. Therefore, $\\phi$ willl not affect the parameter learning in Eq. (3). \n\n**Re: Q4** This is a great question. For this setup, it's equivalent to say $\\phi^x(x) = \\theta(x) * x$, i.e., the function $\\phi$ depends on $x$. If $\\theta(x)$ is an arbitrary function, then the problem is clearly not learnable. If the composited function $\\phi^x(x) = \\theta(x) * x$ satisfies our learnability Assumption 1, we can view $\\phi^x(x)$ as the new $\\phi’(x)$, and our Theory still applies. We’ve studied a similar problem as one generalization in section 5.1, where the context generating function $\\phi$ depends on the arm we selected. As a consequence, this will introduce an additional $\\sqrt{K}$ in the first term of the regret bound in Theorem 1.\n\nThank you once again for your time and thoughtful feedback. If there are any further concerns or questions, please kindly let us know. Thank you!\n\n"}, {"review_id": "7Jlx1FFku1", "reviewer": "Reviewer_uygu", "summary": "This paper introduces and analyzes the problem of contextual multi-armed bandits with post-serving contexts, where additional reward-relevant information is revealed after the the algorithm makes its choice. It divides the traditional context into a pre-serving context which is known the the algorithm at decision-time and a post-serving context which revealed later, but for which the algorithm can learn to produce an accurate estimate of its mean based on the pre-serving context. It then shows that the standard elliptical potential lemma needs updating in order to handle this case, and provides an alternative version. The paper then provides a novel algorithm which estimates the post-serving context in order to use in the new EPL, and proves its regret rate. Finally the paper performs experiments validating the performance of the poLinUCB algorithm.", "questions": "1) Could you spell out an example of the setting in more detail? The paper does a good job of explaining situations where there is a post-serving context, but isn't that explicit about what the reward function is where the reward is revealed immediately after the decision but the post-serving context is clearly helpful for predicting performance\n2) Could you say a bit more about why poLinUCB outperforms LinUCB even when $\\phi$ is a linear function? If $z = Ax$, then $r = \\theta x + \\beta z = \\theta x + \\beta Ax = (\\theta + \\beta A)x$, and it is equivalent to a slightly different linear contextual bandits problem.", "limitations": "The authors did not discuss the limitations of this work. While they would be similar to the limitations of normal bandit problems, adding the post-serving context could plausibly be more impactful than (for instance) a 20% performance improvement on a standard bandit problem. In particular, it seems plausible that the post-serving context could allow one to use more complex reward functions, which could be good or bad.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1) Makes a novel contribution to a more general version of the elliptical potential lemma which is well-motivated by their chosen application problem\n2) Introduces a novel but useful-seeming problem setting where additional reward-relevant information is revealed after the algorithm's decision\n3) Experiments clearly demonstrate the performance improvements benefits of their new algorithm, which nearly matches the performance of LinUCB which ", "weaknesses": "1) The paper doesn't have a conclusion section\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for the insightful comments! Please find our detailed responses to the questions below.\n\n**Re: weakness 1 \\& limitations** We apologize for missing the conclusion and limitation section in the main paper.  Due to space constraints, we had to move the conclusions and limitations to Appendix A.1 (see supplementary material). We tried to prioritize the more technical contributions in the main body. Based on our knowledge, if the paper gets accepted, there will be one extra page and we will move the conclusion and limitation section back to the main paper. \n\n**Re: Q1** Thanks for the great question. For example, for youtube recommendation, the pre-serving context $x$ could be a feature vector that summarizes the user's profile, along with their purchase and browsing history. The 'arm' might be the available youtube videos, and the post-serving feature $z$ could be an embedding extracted from the user’s watching behavior, including speed-up or speed-down, liked or not liked, watching time and its review contents (if any).\n\n**Re: Q2**  Yes, you are correct! If the context-generating function is linear, LinUCB should ultimately achieve no-regret as well. However, poLinUCB may have an advantage in the initial stages, as it can utilize the additional information encoded by the (x, z) pairs. Specifically, for poLinUCB, it simultaneously learns the matrix $A$ (if $z = A x$), and $\\theta$ and $\\beta$, which can leverage the data more efficiently. This advantage is also observed in Figure 1 (in the main paper), when $\\phi$ is linear, the regret of LinUCB tends to flatten as the number of time steps increases. However, this pattern isn't observed in the other two cases.\n\nThank you again for your valuable time and consideration. Should you have any additional concerns or questions, kindly let us know. Thank you!\n"}, {"review_id": "qieTMr1l15", "reviewer": "Reviewer_BiVL", "summary": "The paper proposes a novel contextual bandit problem with post-serving contexts and introduces a new algorithm, poLinUCB, that achieves tight regret under standard assumptions. The authors demonstrate the effectiveness of their approach through both synthetic and real-world experiments, showing that poLinUCB consistently outperforms other strategies in leveraging post-serving information. Overall, the paper makes contributions to the field of online learning and contextual bandits.", "questions": "- Could the authors provide more details on the choice of hyperparameters and the sensitivity of the proposed algorithm to their values?\n- Could the authors provide more insights into the practical implications and potential impact of the proposed approach? \n- How does the proposed algorithm handle noisy or incomplete post-serving context information, and what are the limitations of the approach in such scenarios?\n", "limitations": "See comments above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- Introduces a new contextual bandit problem with post-serving contexts and proposes a novel algorithm, poLinUCB, that achieves tight regret under standard assumptions.\n- Demonstrates the effectiveness of the proposed approach through both synthetic and real-world experiments.\n- Makes significant contributions to the field of online learning and contextual bandits, and has the potential to improve efficiency in a wide range of applications.", "weaknesses": "- The paper does not seem to be fully finished. There is no conclusion section. \n- The paper could benefit from a more thorough discussion of the limitations and assumptions of the proposed approach, particularly in the context of real-world applications.\n- The experimental evaluation is limited. It could be expanded to include more datasets and scenarios.\n- The paper could provide more details on the implementation and computational complexity of the proposed algorithm.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks to the reviewer for the thoughtful observations and comments! Our detailed responses to the questions can be found below.\n\n\n**Re: weakness 1 \\& 2** We apologize for missing the conclusion and limitation section in the main paper.  Due to space constraints, we had to move the conclusions and limitations to Appendix A.1 (see supplementary material). We tried to prioritize the more technical contributions in the main body. Based on our knowledge, if the paper gets accepted, there will be one extra page and we will move the conclusion and limitation section back to the main paper.  The potential limitation of our work hinges on the assumption that the function $\\phi^\\star$ is learnable, a condition that may not always be possible. However, we do observe that modeling the function mapping from x to z will boost the performance on a real world dataset, MovieLens.\n\n**Re: weakness 3**  Thank you for the constructive feedback. We acknowledge the importance of comprehensive experimental evaluations in strengthening the validity of the research findings. Our selection of datasets and scenarios was aimed at presenting an initial exploration of the effectiveness of the proposed methodology in a new problem setup, while balancing feasibility and computational constraints. That being said, we certainly agree that a more extensive set of experiments, including a wider range of datasets and scenarios, may help to provide more insights. It could also validate our method across diverse contexts, understand its limits better, and optimize it to function efficiently in varied settings.\n\n\n**Re: weakness 4** We’ve included the details about the experiments in the experimental section. To promote reproducibility, we will surely release the code for reproducing all the figures in our paper.\n\n\n**Re: Q1** For the coefficient of the variance term in UCB, we performed a grid search using the values {0.01, 0.1, 1}. As for the Adam optimizer, we didn't adjust the learning rate, instead choosing the default value which already demonstrates satisfactory performance.\n\n**Re: Q2**  At its core, our approach aims to enhance the efficiency and effectiveness of decision-making processes in dynamic environments, which is relevant in numerous practical domains. In the realm of e-commerce, for instance, our method could be utilized to enhance product recommendations by better modeling user responses based on their past interactions and newly posted reviews. This can lead to improved customer satisfaction and potentially increased revenue. Similarly, in the field of healthcare, our approach could be used to optimize personalized treatment plans, where the \"post-serving context\" could be patient responses to previous treatments. This could potentially lead to more effective treatment strategies and improved patient outcomes. In the broader realm of machine learning, our approach introduces a new problem setup on the exploration-exploitation trade-off, by incorporating post-decision information into the learning process. This could stimulate the development of new learning algorithms with improved performance.\n\n**Re Q3**  Our algorithm can handle the noisy post-serving context information. Our generalized elliptical potential lemma is developed to address the technical challenge in analyzing the regret under noisy post-serving context information.  However, it's important to note that significantly incomplete information might affect the effectiveness of the algorithm, as is common for almost all  machine learning models. Further research will be required to understand and optimize the performance under such conditions.\n\n\nOnce again, we appreciate your time and constructive feedback. If further questions or concerns arise, please don't hesitate to reach out. Thank you!\n"}, {"review_id": "a3wv0MglJ5", "reviewer": "Reviewer_8bhs", "summary": "This paper looks into contextual bandits in the scenario where only partial context is provided to the learner for making decisions. Specifically, this paper comes up with an environment setting where the full context consists of pre and post components which are revealed to the learner before and after she finalizes the action to take. Given the true reward is tied to the full context, the algorithm should include a post-context inferring step to get low regret. For the linear case, this paper proposes a low regret algorithm poLinUCB for this pre-post contextual bandit setting. The performance of poLinUCB is proved with theorems and evaluated by simulations, where a smaller regret rate is shown in contrast to other method/baselines.", "questions": "- What I’m not sure of is whether the problem setting is of good value to study, hopefully the author will respond with more evidence that may justify the problem setting.  \n- Is the dependency on $d_u = d_x +d_z $able to further optimize, given $z_t$ is predictable by $x_t$, the effective dimension of this problem maybe smaller than $d_u$.", "limitations": "Identified Limitations are listed in Weakness and Questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Both the theorem and simulation show in agreement that poLinUCB outperforms counter-method (Wang et al.) and baselines that are mentioned in the paper. \n2. The theorem and its consequential sharper regret rate in $T$ compared to Wang et al. is built upon the generalized EPL, which may be considered as a new tool for other independent interests that take the uncertainties of context into account.", "weaknesses": "**Soundness of the problem setup** Though the math content from problem formulation to algorithm to theorems are sound, it’s of independent evaluation that whether the setup at the first place is worth studying, put in other words, does the reward model (under line 107) cover/match any real-world problem. For me, some major drawbacks are: \n- it’s unlikely in reality that z_t will be fully revealed to learner \n- the learnability assumption fails when z_t is not fully determined by x_t, which is what usually happens in the hidden contextual setting where the hidden part is influenced by multiple factors, including but not limited to the revealed part x_t.\n- given this setting where z_t is fully predictable by x_t, then isn’t kernel/neural bandit already a good solution for this problem? \n\n**Method proposed is pretty similar to existing one** It’s in doubt that the outperformance is gained because poLinUCB has any essential algorithmic improvement than that of Wang at el. **or the formance gain is a only matter of new problem setting**. Wang at el. is not designed for the specific problem setting brought up by this work. \n- I can see that the original algorithm by Wang at el will suffer larger regret under your reward setup where true reward has component $<z_t, \\beta_a^*>$. Since $z_t$’s from previous rounds are accessible to learner, the most accurate way for estimating \\beta^* is certainly to utilize $z_t $rather than $\\hat \\phi (x_t)$ in loss. poLinUCB is more like an alternation of exsisting method as on adapting it to a new problem.\n- But what if  true reward turns to have $<\\phi^*(x_t), \\beta_a^*>$, which is like a twin problem setup of this paper’s, then maybe Wang at el. will outperforms poLinUCB given $z_t$ is a noisy sample of $\\phi^*(x_t)$ thus casts extra error into $\\hat \\beta_a$, while  $\\hat \\phi (x)$ is ERM, which should have some noise reduction effect strengthened as $t$ goes up. Upper bound of regret in Wang at el. is inferior doesn’t necessarily mean the algorithm is less optimal, the performance may be underestimated by an upper bound that is not tight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for the comprehensive and valuable comments! Below, you'll find our in-depth responses to the questions raised.\n\n\n**Re: weakness 1 & 2**  The reviewer is correct that there may be other hidden factors (both pre-serving or post-serving) that affect the reward. In this work, we are just trying to capture such post-serving signals as much as we can, by modeling it as the post-serving contexts that are observable. We do not mean to claim that we are able to capture everything post-serving, neither can any previous works. This is also why our reward model – like most standard bandit models – also has a noise term, which is designed to capture remaining unobservable signals. Our experiments show that even utilizing those observable post-serving features, it already is useful for reducing the regret.\n\n**Re: weakness 3**  To a certain degree, the reviewer's proposal is correct. However, for neural bandits, relying solely on the mapping from the pre-serving context x to the reward r may not be as efficient as our method, which exploits the structure of the reward function, i.e., $r = \\theta * x + \\beta * \\phi(x)$. We’ve observed that the linUCB performs worse than poLinUCB as linUCB doesn’t exploit this structure, though ultimately it will achieve no-regret. In general, leveraging this intrinsic structure will enhance generalization and make the learning process more efficient.\n\nAdditionally, on the computational side, the kernel method necessitates the inversion of the covariance matrix, which comes with a computational cost that is cubic in the dimension. In addition, calculating the NTK is also a costly process. For instance, the computation of the convolutional neural tangent kernel (CNTK) involves $\\Omega(d^4\\cdot n^2)$ operations (Arora et al., 2019), where $d$ is the dimension, and $n$ is the number of data points.\n\n[Reference] Arora, Sanjeev, et al. \"On exact computation with an infinitely wide neural net.\" Advances in Neural Information Processing Systems 32 (2019).\n\n**Re: weakness 4**  We believe poLinUCB has essential algorithmic improvement over Wang at el. In fact, our first attempt in solving our problem is a natural adaptation of the algorithm of Wang et al. 2016 (LinUCB ($\\hat{\\phi}$)). Note that LinUCB ($\\hat{\\phi}$) is not exactly the same as the algorithm of Wang et al. 2016, but a natural adaptation of their idea to our setup (i.e., estimating post-serving context first, and then use the post-serving context estimation to estimate linear parameters), which is why we think it is a suitable algorithm for our setup. We tried to prove that this algorithm has small regret, which we did not succeed (our later experiments does show that its regret is not good). This is the motivation for us to design the poLinUCB algorithm.\n\n**Re: weakness 5\\&6**  Your understanding is intuitively correct for the first point. Additionally, we did experiments follow the setup you mentioned. Please see the Figure (2) in the uploaded PDF (as a response to all reviewers). We observe that the algorithm adapted from Want et al., 2016, (LinUCB ($\\hat{\\phi}$)) still performs worse than our method, though the gap seems become smaller.\n\n**Re: Q1** The potential significance of our problem setting lies in the exploration of using pre-serving context to predict post-serving context within the contextual bandits framework. Unlike reward data, which may be sparse or less accessible, the mapping from pre-serving contexts (such as user history) to post-serving contexts (such as feedback) often presents a more abundant and accessible source of information. Our proposed algorithm leverages this relationship, potentially creating a dynamic, adaptive recommendation system that could lead to improved recommendations by predicting user responses. In summary, our research highlights the potential of leveraging the more accessible and abundant data of predicted post-serving features, aligning with practical needs across various domains, and possibly paving the way toward more sophisticated, responsive recommendation systems. \n\n**Re: Q2** Regarding the dependency on $d_u$, if the mapping from x to z is non-linear and without additional assumptions on $\\phi$, we don’t think the dependency on $d_u$ can be improved. This is because the covariance matrix of $(x, \\phi(x))$ can be full rank $d_u$ when $\\phi(x)$ is non-linear.\n\nWe're grateful once again for your time and detailed feedback. Should you have any more questions or concerns, please feel free to contact us. Thank you!"}, {"review_id": "ockW9cXPcK", "reviewer": "Reviewer_FTfP", "summary": "The paper studies a variant of linear contextual bandits where a post-serving context is provided to the learner *after* the learner selects an arm. The reward is linear in the context and the post-serving context (but thus may not be linear in the original context on its own). The post-serving context is specified by noisy perturbation of a fixed (but unknown) function of the pre-specified context. The paper abstracts away the process of learning the function: the function is assumed to be learnable with sufficiently many pairs of context and noisy post-serving context pairs, and the “complexity” of the function is parameterized by the error of this learning process. \n\nThe paper designs an algorithm based on LinUCB that creates a confidence set for the post-serving context in addition to the typical confidence set for the reward function parameters. The regret bound has a $O(T^{1-\\alpha})$ term that depends on the complexity $\\alpha$ of the function and a $O(\\sqrt{T})$ term that depends on the dimension. The paper builds on the classical analysis of LinUCB, but requires a novel elliptical potential lemma. \n\nThe paper further complements the theoretical analysis with simulations on synthetic data and real-world data (MovieLens dataset). \n", "questions": "Questions: \n- Is the dependence on alpha in the regret bound tight?\n\nTypos:\n- “Generlaize” -> “generalize” p.5\n- “Sketche” -> “sketch” p.6\n- “Sthe” -> “the” p.6\n- “Followings” -> “following” p.7\n", "limitations": "Yes, the authors adequately addressed limitations. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper provides an intriguing model for additional information available to the learner beyond the reward. The idea of a post-serving context is natural and well-motivated. The approach of abstracting away the complexity of learning the function mapping contexts to means of post-serving contexts is also clean and elegant. \n\nThe LinUCB-based algorithm in the paper is simple and elegant. The paper also provides a detailed discussion of shortcomings of relying on a point estimate of the post-serving contexts (in Section 2.2) and the need to appropriately address uncertainty in phi via a confidence set when computing an upper confidence-bound. \n\nThe analysis of the algorithm is also technically interesting, with an introduction of the novel elliptical potential lemma. The paper clearly describes how the novel elliptical potential lemma accommodates slower learning rates and allows for noisy contexts, and furthermore highlights how the lemma is tight in several regimes. \n\nThe paper is very well-written and explains the key ideas clearly. \n", "weaknesses": "While the paper focuses solely on upper bounds, it could be interesting to investigate lower bounds. Is the dependence on alpha in the regret bound tight? (See question below.) That being said, this is a fairly minor weakness, since the upper bound analysis is already involved and interesting. \n\nAnother minor weakness is that in Observation 1, it seems that the result is restricted to linear bandit algorithms (which should probably be clarified in the statement too). This seems to be a bit of an unfair comparison because the model is misspecified, and the linear bandit algorithm was not designed to handle misspecified rewards. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer for the thoughtful comments! You can find our responses to each question below.\n\n\n**Re: weakness 1 \\& Q1**  For $\\alpha=1/2$, our bound is tight, which achieves $1/\\sqrt{T}$, which matches the lower bound.  However, for other $\\alpha$, it’s an interesting problem setup which combines the lower bound of offline PAC learning and online learning, and we are currently not sure if our bound is tight. Future directions could be incoporating more complex ways of estimating the phi functions such as manifold regression (see, e.g., Yang \\& Dunson, 2016.), non-parametric ways like k-nearest-neighbors to estimate phi, or to estimate complex non-smooth function (e.g., those in Holder space $H(\\beta, L)$, see the note by Tibshirani \\& Wasserman, 2019) ), which may cover the case of $\\alpha \\in (0.5, 1]$. Whether our regret bound is tight for such more complex situations is an interesting open direction, not only because it is beyond the scope of the current paper but also because even understanding whether the convergence rate for estimating the function $\\phi$ itself is already a highly non-trivial question and, in fact, an active research area.\n\nYang, Yun, and David B. Dunson. \"Bayesian manifold regression.\" (2016): 876-905.\n\nTibshirani, Ryan and Larry Wasserman. \"Nonparametric Regression\", Statistical Machine Learning, Spring 2019 \n\n**Re: weakness 2**  The goal of Observation 1 is to illustrate the issue of misspecified features when directly applying linear bandit algorithms and thus motivates the necessity of modeling the functional relationship between the pre-serving and post-serving context. We did not intend to view it as a comparison between standard linear bandit algorithms and our to-be-developed algorithm. If we don’t model this functional relationship, the model will be misspecified, and thus a linear regret cannot be avoided.\n\nOnce again, we appreciate your time and constructive feedback. If further questions or concerns arise, please don't hesitate to reach out. Thank you!\n"}]

Author rebuttal:
Dear Reviewers,

We have added the figures to the accompanying PDF. We hope you find them useful and informative.

Best,

Authors

Meta-review: The paper studies a contextual bandit model where the contextual information is divided into two - pre-serving information, obtained before choosing an action, and post-serving information, which is obtained after the decision. The authors present a LinUCB-like algorithm for this setting, deriving regret bounds and evaluating it empirically on synthetic data and MovieLens. The algorithm relies on a black-box estimation module for the mean of the post-serving context, given the pre-serving context, and the regret bounds depend on the efficiency of this module.

The reviewers agree that the framework of pre-serving and post-serving contexts suggested in the paper is interesting and well-motivated. Moreover, the authors present novel techniques to analyze their algorithmic approach (the Generalized Elliptical Potential Lemma), which might have independent use.
Decision: Accept (spotlight)