Follow-ups Also Matter: Improving Contextual Bandits
via Post-serving Contexts

Chaoqi Wang 1 Ziyu Ye 1 Zhe Feng 2 Ashwinkumar Badanidiyuru 2 Haifeng Xu 1

Abstract

capture the complexity of real-world scenarios (Wang et al.,2016; Yang et al., 2020). Specifically, the learner often
observes valuable follow-up information pertinent to the
payoff post arm selection (henceforth, the post-serving context). Standard contextual bandits framework that neglects
such post-serving contexts may result in significantly suboptimal performance due to model misspecification.

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 withproblems in which valuable additional context
can be observed after arm selection. For example,
content recommendation platforms like Youtube,
Instagram, Tiktok also observe valuable followup information pertinent to the user’s reward after
recommendation (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 isa robustified and generalized version of the wellknown Elliptical Potential Lemma (EPL), which
can accommodate noise in data. Such robustification is necessary for tackling our problem, andwe believe it could also be of general interest.
Extensive empirical tests on both synthetic andreal-world datasets demonstrate the significant
benefit of utilizing post-serving contexts as wellas the superior performance of our algorithm overthe state-of-the-art approaches.

Consider an algorithm designed to recommend educational
resources to a user by utilizing the user’s partially completed coursework, interests, and proficiency as pre-serving
context (exemplified in platforms such as Coursera). Aftercompleting the recommendation, the system can refine theuser’s profile by incorporating many post-serving context
features such as course completion status, how much timespent on different educational resources, performances, etc.
This transition naturally delineates a mapping from user
attributes (i.e., the pre-serving context) to user’s learning
experiences and outcomes (i.e., the post-serving context). It
is not difficult to see that similar scenarios happen in manyother recommender system applications. For instance, in
e-commerce platforms (e.g., Amazon, Etsy or any retailingwebsite), the system will first recommend products based on
the user’s profile information, purchasing pattern and browsing history, etc.; post recommendations, the system can thenupdate these information by integrating post-serving contexts such as this recent purchase behaviour and productreviews. 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 estimation about users’ interaction behavior as well as the rewards.

1. Introduction
Contextual bandits represent a fundamental mathematicalmodel that is employed across a variety of applications, suchas personalized recommendations (Li et al., 2010; Wu et al.,2016) and online advertising (Schwartz et al., 2017; Nuara
et al., 2018). In their conventional setup, at each round t, alearner observes the context xt , selects an arm at ∈ A, andsubsequently, observes its associated reward rt,at . Despite
being a basic and influential framework, it may not always
University of Chicago 2 Google Research. Correspondence to:
Chaoqi Wang <chaoqi@uchicago.edu>.

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 recommendation/serving phase, they can be estimatedfrom the pre-serving context given enough past data. Moreformaly, we assume that there exists a learnable mappingϕ⋆ (·) : Rdx → Rdz that maps pre-serving feature x ∈ Rdx
to the expectation of the post-serving feature z ∈ Rdz , i.e.,
E[z|x] = ϕ⋆ (x).

Interactive Learning with Implicit Human Feedback Workshop at
ICML 2023, Honolulu, Hawaii, USA.

Unsurprisingly, and as we will also show, integrating the estimation of such post-serving features can significantly help

1

1

Improving Contextual Bandits via Post-serving Contexts

Related Works. Our work lies in the extensive linear
contextual bandits literature, however, most of existing studies assume the full contexts are observable before playing
actions (Abe et al., 2003; Auer, 2002; Dani et al., 2008;
Rusmevichientong and Tsitsiklis, 2010; Lu et al., 2010;
Filippi et al., 2010; Li et al., 2010; Chu et al., 2011; AbbasiYadkori et al., 2011; Li et al., 2017; Jun et al., 2017) and they
demonstrate the use of upper confidence bounds for balancing exploration and exploitation, proving minimax optimal
regret bounds using the confidence ellipsoids and the elliptical potential lemma (EPL). In sharp contrast, we assume
partially observable context in this paper, where only partial contexts are observed before making decisions. Partial
information contextual bandits, though limited, have beenstudied (Wang et al., 2016; Qi et al., 2018; Yang et al., 2020;
Park and Faradonbeh, 2021; Yang and Ren, 2021; Zhu andKveton, 2022), focusing on predicting context information
through context history analysis or selective expert requests.
Differently, our work introduces a novel problem setting,separating contexts into pre-serving and post-serving categories. To achieve near-optimal regret bound in this setting, we propose a generalized elliptical potential lemma tohandle the additional noise introduced by the post-serving
features. While the EPL (Lai and Wei, 1982) and its generalizations have been widely used 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 et al.,2020; Wang et al., 2022; Carpentier et al., 2020; Hamidi andBayati, 2022), they fall short for the analysis in our context.
See Appendix A.1 for further related works.

to enhance the performance of contextual bandits. However, most of the existing contextual bandit algorithms,
e.g., (Auer, 2002; Li et al., 2010; Chu et al., 2011; Agarwal
et al., 2014; Tewari and Murphy, 2017), are not designed toaccommodate 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 simultaneously estimate reward parameters and thefunctional mapping from the pre- to post-serving contexts
so to optimize arm selection and achieves sublinear regret.
En route to analyzing our algorithm, we also developed newtechnique tools that may be of independent interest.

Main Contributions.
• First, we introduce a 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 postserving context as a function of the pre-serving context
can be gradually learned from historical data. This newmodel 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 ellipticalpotential 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 a
new algorithm poLinUCB√ and prove that it enjoys a regret
e 1−α dα + du T K), where T denotes the timebound O(Tuhorizon and α ∈ [0, 1/2] is the learning speed of thepre- to post-context mapping function ϕ⋆ (·), whereas
du = dx + dz and K denote the parameter dimension
and number of arms. When ϕ⋆ (·) is easy to learn,√ e.g.,√eα = 1/2, the regret bound becomes O( T du +du T K)
and is tight. For general functions ϕ⋆ (·) that satisfy α ≤1/2, this regret bound degrades gracefully as the function
becomes more difficult to learn, i.e., as α decreases.
• Lastly, we empirically validate our proposed algorithm
through thorough numerical experiments on both simulated benchmarks and real-world datasets. The results
demonstrate that our algorithm surpasses existing stateof-the-art solutions. Furthermore, they highlight the tangible benefits of incorporating the functional relationshipbetween pre- and post-serving contexts into the model,
thereby affirming the effectiveness of our modeling.

2. 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 5. This setting involves afinite 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 x ∈ Rdx , and the postserving context, signified as z ∈ Rdz . When it is clear fromcontext, we sometimes refer to pre-serving context simply as
context as in classic setup, but always retain the post-serving
contextPnotion to emphasize its difference.
We will denotePtt⊤
Xt = s=1 xs x⊤
+
λI
and
Z
=
z
t
s
s=1 s zs + λI. For
the sake of brevity, we employ u = (x, z) to symbolize
the stacked vector of x and z, with du = dx + dz and∥u∥2 ≤ 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 ∈ A, the payoff,ra (x, z), is delineated as follows:ra (x, z) = x⊤ θa⋆ + z ⊤ βa⋆ + η,
2

Improving Contextual Bandits via Post-serving Contexts

where θa⋆ and βa⋆ represent the parameters associated withthe arm, unknown to the learner, whereas η is a random noise sampled from an Rη -sub-Gaussian distribution.
We use ∥x∥√ p to denote the p-norm of a vector x, and∥x∥A := x⊤ Ax is the matrix norm. For convenience,
we assume ∥θa⋆ ∥2 ≤ 1 and ∥βa⋆ ∥2 ≤ 1 for all a ∈ A. Additionally, we posit that the norm of the pre-serving andpost-serving contexts satisfies ∥x∥2 ≤ Lx and ∥z∥2 ≤ Lz ,respectively, and maxt∈[T ] supa,b∈A ⟨θa⋆ − θb⋆ , xt ⟩ ≤ 1 andmaxt∈[T ] supa,b∈A ⟨βa⋆ − βb⋆ , zt ⟩ ≤ 1, same as in (Lattimore and Szepesvári, 2020).

the corresponding regret will degrade as this learning algorithm’s convergence rate becomes worse. More specifically,
we posit that, given the context xt , the post-serving context
zt is generated as1
zt = ϕ⋆ (xt ) + ϵt , i.e., ϕ⋆ (x) = E[z|x].
Here, ϵt is a zero-mean noise vector in Rdz , and ϕ⋆ : Rdx →Rdz can be viewed as the post-serving context generating
function, which is unknown to the learner. However, we
assume ϕ⋆ is learnable in the following sense.
Assumption 1 (Generalized learnability of ϕ∗ ). There exists
an algorithm that, given t pairs of examples {(xs , zs )}ts=1with arbitrarily chosen xs ’s, outputs an estimated functionof ϕ⋆ : Rdx → Rdz such that for any x ∈ Rdx , the following
holds with probability at least 1 − δ,

2.1. Problem Settings and Assumptions.
The learning process proceeds as follows at each time stept = 1, 2, · · · , T :1. The learner observes the context xt .
2. An arm at ∈ [K] is selected by the learner.
3. The learner observes the realized reward rt,at andthe post-serving context, zt .

eδt := ϕbt (x) − ϕ⋆ (x)2α≤ C0 · ∥x∥2X −1 · log (t/δ) ,twhere α ∈ (0, 1/2] and C0 is some universal constant.

Without incorporating the post-serving context, one may
incur linear regret as a result of model misspecification,
as illustrated in the following observation. To see this,consider a setup with two arms, a1 and a2 , and a context x ∈ R drawn uniformly from the set {−3, −1, 1}
with ϕ⋆ (x) = x2 . The reward functions for the arms
are noiseless and determined as ra1 (x) = x + x2 /2 andra2 (x) = −x − x2 /2. It can be observed that ra1 (x) >ra2 (x) when x ∈ {−3, 1} and ra1 (x) < ra2 (x) when x =−1. Any linear bandit algorithm that solely dependent on
the context x (ignoring ϕ⋆ (x)) will inevitably suffer fromlinear regret, since it is impossible to have a linear function (i.e., r(x) = θx) that satisfies the above two inequalities
simultaneously.

The aforementioned assumption encompasses a wide rangeof learning scenarios, each with different rates of convergence. Generally, the value of α is directly proportional to
the speed of learning; the larger the value of α, the quicker
the learning rate. Later, we will demonstrate that the regretof our algorithm is proportional to O(T 1−α ), exhibiting agraceful degradation as α decreases. The ensuing proposition demonstrates that for linear functions, α = 1/2. This2
represents the best learning rate that can be accommodated.
√
In this scenario, the regret of our algorithm is O( T ), aligning with the situation devoid of post-serving contexts (Liet al., 2010; Abbasi-Yadkori et al., 2011).
Observation 2. Suppose ϕ(·) is a linear function, i.e.,⊤ϕ(x)Φ ∈ Rdx ×dz , then eδt = = Φ x for some

Observation 1. There exists linear bandit environments
in which any online algorithm without using post-serving
context information will have Ω(T ) regret.

O ∥x∥X −1 · log (t/δ) .
tThis observation follows from the following inequalitiesb ⊤ x − Φ⋆ ⊤ x∥ ≤ ∥Φb t − Φ⋆ ∥X ·∥ϕt (x) − ϕ⋆ (x)∥ = ∥Φtt
t∥x∥X −1 = O(∥x∥X −1 · log δ ), where the last equationtt
is due to the confidence ellipsoid bound (Abbasi-Yadkori
et al., 2011).

Therefore, it is imperative that an effective learning algorithm must leverage the post-serving context, denoted as zt .
As one might anticipate, in the absence of any relationshipbetween zt and xt , it would be unfeasible to extrapolate
any information regarding zt while deciding which arm topull, a point at which only xt is known. Consequently, it isreasonable to hypothesize a correlation between zt and xt .
This relationship is codified in the subsequent learnability
assumption.

1

Given this, an alternative view of ra is to treat it as a functionof x as follows: ra (x) = x⊤ θa⋆ + ϕ⋆ (x)⊤ βa⋆ + noise. Ouralgorithm can be viewed as a two-phase learning of this structured
function, i.e., using (xt , zt ) to learn ϕ⋆ that is shared among allarms and then using learned ϕ̂ to estimate each arm a’s reward
parameters.
2
To be precise, our analysis can extend to instances where
α > 1/2. However, this would
not enhance the regret bound since√
the regret is already Ω( T ), even with knowledge of z. This
would only further complicate our notation, and therefore, suchsituations are not explicitly examined in this paper.

Specifically, we make the following natural assumption —there exists an algorithm that can learn the mean of the postserving context zt , conditioned on xt . Our analysis will be
general enough to accommodate different convergence ratesof the learning algorithm, as one would naturally expect,3

Improving Contextual Bandits via Post-serving Contexts

2.2. Warm-up: Why Natural Attempts May Be
Inadequate?

post-serving context, during which we also developed a newtechnical tool which may be of independent interest to theresearch community.

Given the learnability assumption of ϕ⋆ , one natural idea forsolving the above problem is to estimate ϕ⋆ , and then run thestandard LinUCB algorithm to estimate (θa , βa ) together
by treating (xt , ϕbt (xt )) as the true contexts. Indeed, this is
the approach adopted by Wang et al. (2016) for addressing
a similar problem of missing contexts zt , except that theyused a different unsurprised-learning-based approach to estimate the context zt due to not being able to observing any
b their algorithm
data about zt . Given the estimation of ϕ,b— which we term it as LinUCB (ϕ) — iteratively carries
out the steps below at each iteration t (see Appendix 2 foradditional details): 1) Estimation of the context-generating
function ϕbt (·) from historical data; 2) Solve of the following
regularized least square problem for each arm a ∈ A, withregularization coefficient λ ≥ 0:ℓt (θa , βa ) =

X



⊤
b
rs,a − x⊤t θa − ϕs (xs ) βa

3. A Robustified and Generalized Elliptical
Potential Lemma
It turns out that solving the learning problem above requires
some novel designs; core to these novelties is a 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 x1 , · · · , xT ∈ Rd . Intuitively, it captures the rateof the sum of additional information contained in each xt ,relative to its predecessors x1 , · · · , xt−1 . Formally,
Lemma (Original Elliptical Potential Lemma). Suppose(1) X0 ∈ Rd×d is any positive definite matrix; (2)x1 , . . . , xT ∈PRd is any sequence of vectors; and (3)tXt = X0 + s=1 xs x⊤
s . Then the following inequality
holds

2

s∈[t]:as =a+λ∥θa ∥22 + ∥βa ∥22



,

T
X

(1)

t=1

Under the assumption that the initialized parameters in theirestimations are very close to the global√ optimum, Wanget al. (2016) were able to show the O( T ) regret of thisalgorithm. However, it turns out that this algorithm will
fail to yield an satisfying regret bound without their strong
assumption on very close parameter initialization, becauseb will significantly enlarge thethe errors arising from ϕ(·)
bconfidence set of θa and βba .3 Thus after removing theirinitialization assumption, the best possible regret bound wee 3/4 ), as illustrated in
can possibly achieve is of order O(Tthe subsequent proposition.
b
Proposition 1 (Regret of LinUCB-(ϕ)).
The regretbof LinUCB-(ϕ) in Algorithm
2
is
upper
bounded
by

p
1+α
1−α α
1−α/2
e
O T
du + T
Kdu
with probability at least1 ∧ ∥xt ∥2X −1 ≤ 2 log
t−1

det XT
det X0,

where a ∧ b = min{a, b} is the min among a, b ∈ R.
To address our new contextual bandit setup with postserving contexts, it turns out that we will need to robustify
and generlaize the above lemma to accommodate noises
in xt vectors and slower learning rates. Specifically, we
present the following variant of the EPL lemma.
Lemma 1 (Generalized Elliptical Potential Lemma). Suppose (1) X0 ∈ Rd×d is any positive definite matrix; (2)x1 , . . . , xT ∈ Rd is a sequence of vectors with bounded l2
norm maxt ∥xt ∥ ≤ Lx ; (3) ϵ1 , . . . , ϵT ∈ Rd is a sequenceof independent (not necessarily identical) bounded zeromean noises satisfying maxt ∥ϵt ∥ ≤ Lϵ and E[ϵt ϵ⊤t ] ≽ft is defined as follows:σϵ2 I for any t; and (4) X

1 − δ, by carefully setting the regularization coefficient1−αλ = Θ(Lu dαlog (T /δ)) in Equation 1.
uT

ft = X0 +XtX(xs + ϵs )(xs + ϵs )⊤ ∈ Rd×d .
s=1

Since α ∈ [0, 1/2], the best possible regret upper bounde 3/4 ), which is considerably inferior to theabove is O(T√e T ). Such deficiency ofsought-after regret bound of O(
b is further observed in all our experiments in
LinUCB-(ϕ)
Section 6 as well. These motivate our following design of anew online learning algorithm to address the challenge ofThen, for any p ∈ [0, 1], the following inequality holds withprobability at least 1 − δ,


T 
p
X
det XTp 1−pp1 ∧ ∥xt ∥2X
≤
2
T
log
−1
f
t−1
det X0
t=1


2
2
2
8L (Lϵ + Lx )32dLϵ (Lϵ + Lx )2
+ ϵ
log
σϵ4
δσϵ4

3

Specifically, Wang et al. (2016) assume that the initial estimab is already very close to ϕb∗ (·) such that the error arisingtion of ϕ(·)
b diminishes exponentially fast due to the local converfrom ϕ(·)
gence property of alternating least squares algorithm (Uschmajew,2012). This strong assumption avoids significant expansion of theconfidence sets, but is less realistic in applications so we do not
impose such assumption.

(2)

Note that the second term is independent of time horizon
T and only depends on the setup parameters. Generally,
this can be treated as a constant. Before describing main
proof idea of the lemma, we make a few remarks regarding4Improving Contextual Bandits via Post-serving Contexts

Lemma 1 to highlight the significance of these generalizations.

union bound and this lemma to show that the above matrix inequality holds for every t ≥ 1 with high probability.
Unfortunately, this turns out to not be true because whent is very small (e.g., t = 1), the above inequality cannot
hold with high probability. Therefore, we have to use theunion bound in a carefully tailored way by excluding all t’s
that are smaller than a certain threshold (chosen optimallyby solving certain inequalities) and handling these termswith small t separately (which is the reason of the secondO(log(1/δ)) term in Inequality 2). Finally, we refine theanalysis of sthe standard EPL by allowing the exponent pin (1 ∧ ∥xt ∥2Xe −1 )p and derive an upper bound on the sum

1. The original Ellipsoid Prediction Lemma (EPL) corresponds to the specific case of p = 1, while Lemma 1 isapplicable for any p ∈ [0, 1]. Notably, the (1 − p) ratein the T 1−p term of Inequality 2 is tight for every p. In
fact, this rate is tight even for xt = 1 ∈ R, ∀t and X0 =2
1 ∈ R since, under these conditions, ∥xt ∥X −1 = 1/t
and, consequently,

PT

t=1


p t−1P
1 ∧ ∥xt ∥2X −1= Tt=1 t−p ,t−1yielding a rate of T 1−p . This additional flexibility gainedby allowing a general p ∈ [0, 1] (with the original EPL
corresponding to p = 1) helps us to accommodate slower
convergence rates when learning the mean context fromobserved noisy contexts, as formalized in Assumption 1.
2. A crucial distinction between Lemma 1 and the originalft in
EPL lies in the definition of the noisy data matrix X
Equation 1, which permits noise. However, the measured
context vector xt 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 noise-free context or the meancontext. 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 anarm, 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 to be useful in different contexts.
For instance, (Carpentier et al., 2020) extends the EPL toallow for the Xt−p -norm, as opposed to the Xt−1 -norm,
while (Hamidi and Bayati, 2022) explores a generalized2
form of the 1 ∧ ∥φ(xt )∥X −1 term, which is motivatedt−1
by variance reduction in non-Gaussian linear regression
models. Nevertheless, to the best of our knowledge, ourgeneralized version is novel and has not been identified
in prior works.

t−1

PT

2
p
f−1 ) with high probability. These together
t=1 (1 ∧ ∥xt ∥X
t−1

yeilds a robustified and generalized version of EPL as inLemma 1.

4. No Regret Learning in Linear Bandits with
Post-Serving Contexts
4.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 andaddress the issue arose from the algorithm introduced in
Section 2.2. The corresponding pseudo-code is delineatedin Algorithm 1. Unlike the traditional LinUCB algorithm,
which solely learns and sustains confidence sets for parameters (i.e., βba and θba for each a), our algorithm also
simultaneously manages the same for the post-serving conb
text generating function, ϕ(·).
Below, we expound on our
methodology for parameter learning and confidence set construction.
Parameter learning. During each iteration t, we fit
the function ϕbt (·) and the parameters {θbt,a }a∈A and{βbt,a }a∈A . To fit ϕbt (·), resort to the conventional empiricalrisk minimization (ERM) framework. As for {θbt,a }a∈A and{βbt,a }a∈A , we solve the following least squared problem
for each arm a,

Proof Sketche of Lemma 1. The formal proof of this lemma
is involved and deferred to Appendix C.1. At a high level,our proof follows procedure for proving the original EPL.
However, to accommodate the noises in the data matrix, wehave to introduce new matrix concentration tools to the original (primarily algebraic) proof, and also identify the rightconditions for the argument to go through. A key lemma
to our proof is a high probability bound regarding the conft (Lemma 2 in Appendix C.1)
structed noisy data matrix X
that we derive based on Bernstein’s Inequality for matrices
under spectral norm (Tropp et al., 2015). We prove that, un2
der mild assumptions on the noise, ∥xt ∥2X
f−1 ≤ ∥xt ∥X −1
t−1
t−1
with high probability for any t. Next, we have to apply theℓt (θa , βa ) =X⊤
rs,a − x⊤s θa − zs βa2s∈[t]:as =a+ λ ∥θa ∥22 + ∥βa ∥22 .

(3)

For convenience, we use w and u to denote (θ, β) and(x, z) respectively. The closed-form solutions to θbt,a andβbt,a for each arm a ∈ A are
"

#
θbt,a
bt,a := bw= A−1t,a bt,aβt,aAt,a = λI +5Pt⊤
s:as =a us us and bt,a =

(4)

Pt

s:as =a rs,a us .

Improving Contextual Bandits via Post-serving Contexts

Algorithm 1 poLinUCB (Linear UCB with post-serving contexts)
1: for t = 0, 1, . . . , T do
2:
Receive the pre-serving context xt
3:Compute the optimistic parameters by maximizing the UCB objective



4:


et =
at , ϕet (xt ), w



arg maxbt−1 ,xt )×Ct−1 (wbt−1,a(a,ϕ,wa )∈[K]×Ct−1 (ϕ

xt
ϕ(x
t)
)

⊤
wa .

Play the arm at and receive the realized post-serving context as zt and the real-valued reward ⊤
xrt,at = t wa⋆t + ηt .
zt

bt,a using Equation 3 for each a ∈ A.
Compute w
6:Compute the estimated post-serving context generating function ϕbt (·) using ERM.
bt,a ) and Ct (ϕbt , xt ) for each a based on Equations 6 and 5.
7:
Update confidence sets Ct (w
8: end for5:

in Eq. 9 depends on ϕ⋆ (xt ) as opposed to zt . This dependency ensures a more pragmatic benchmark, as otherwise,
the noise present in z would invariably lead to a 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.

Confidence set construction. At iteration t, we construct
the confidence set for ϕbt (xt ) byno
Ct ϕbt , xt := z ∈ Rd : ϕbt (xt ) − z ≤ eδt . (5)2Similarly, we can construct the confidence set for the parambt,a for each arm a ∈ A byeters wnobt,a ) := w ∈ Rdx +dz : ∥w − w
bt,a ∥At,a ≤ ζt,a , (6)Ct (wTheorem 1 (Regret of poLinUCB). The regret of
poLinUCB
in Algorithm
1 is upper bounded by√e T 1−α dα
O
+
d
T
K
with
probability at least 1 − δ,uup√where ζt,a = 2 λ+Rη du log ((1 + nt (a)L2u /λ)/δ) andPtnt (a) = s=1 1[as = a]. Additionally, we further define
ζt := maxa∈A ζt,a . By the assumption 1 and Lemma 3, wehave the followings hold with probability at least 1 − δ foreach of the following events,
bt,a ) . (7)ϕ⋆ (xt ) ∈ Ct ϕbt , xt
and w⋆ ∈ Ct (wif T = Ω(log(1/δ)).
The first term in the bound is implicated by learning thefunction ϕ⋆ (·). Conversely, the second term resembles theone derived in conventional contextual linear bandits, withthe exception that our dependency on du is linear. This
linear dependency is a direct consequence of our generalized
robust elliptical potential lemma. The proof is deferred inAppendix C.2.

4.2. Regret Analysis
In the forthcoming section, we establish the regret bound.
Our proof is predicated upon the conventional proof of LinUCB (Li et al., 2010) in conjunction with our robust elliptical potential lemma. The pseudo-regret (Audibert et al.,2009) within this partial contextual bandit problem is defined as,
RT = Regret(T ) =TXrt,a⋆t − rt,at ,5. Generalizations
So far we have focused on a basic linear bandit setup with
post-serving features. Our results and analysis can be easily
generalized to other variants of linear bandits, including
those with feature mappings, and below we highlight someof these generalizations. They use similar proof ideas, up tosome technical modifications; we thus defer all their formal
proofs to Appendix C.3.

(8)

t=1

in which we reload the reward by ignoring the noise,
rt,a = ⟨θa⋆ , xt ⟩ + ⟨βa⋆ , ϕ⋆ (xt )⟩,where a⋆t

(9)5.1. Generalization to Action-Dependent Contexts= arg maxa∈A ⟨θa⋆ , xt ⟩ + ⟨βa⋆ , ϕ⋆ (xt )⟩.

Our basic setup in Section 2 has a single context xt at any
time step t. This can be generalized to action-dependentIt iscrucial to note that our definition of the optimal action, a⋆t ,6

Improving Contextual Bandits via Post-serving Contexts

5.3. Generalization to Linear Bandits with Feature
Mappings

contexts settings as studied in previous works (e.g., Li et al.
(2010)). That is, during each iteration indexed by t, thelearning algorithm observes a context xt,a for each individual arm a ∈ A. Upon executing the action of pulling arm at ,the corresponding post-serving context zt,at is subsequently
revealed. Notwithstanding, the post-serving context for all
alternative arms remains unobserved. The entire procedureis the same as that of Section 2.

Finally, we briefly remark that while we have so far assumed
that the arm parameters are directly linear in the context
xt , zt , just like classic linear bandits our analysis can beeasily generalized to accommodate feature mapping π x (xt )and π z (zt ) = π z (ϕ(xt ) + εt ). Specifically, if the reward
generation process is ra = ⟨θa⋆ , π x (xt )⟩+⟨βa⋆ , π z (zt )⟩+ηtinstead, then we can simply view x̃t = π x (xt ) and z˜t =π z (zt ) as the new features, with ϕ̃(xt ) = Eϵt [π z (ϕ(xt ) +ϵt )]. By working with x̃t , z˜t , ϕ̃, we shall obtain the sameguarantees as Theorem 1.

In extending this framework, we persist in our assumptionthat for each arm a ∈ A, there exists a specific functionϕ⋆a (·) : Rdx → Rdz that generates the post-serving context
z upon receiving x associated with arm a ∈ A. The primarydeviation from our preliminary setup lies in the fact that we
now require the function ϕ⋆a (·) to be learned for each arm
independently. The reward is generated as

6. Experiments
This section presents a comprehensive evaluation of our
proposed poLinUCB algorithm on both synthetic and realworld data, demonstrating its effectiveness in incorporatingbfollow-up information and outperforming the LinUCB(ϕ)
variant.

rt,at = ⟨θa⋆t , xt,at ⟩ + ⟨βa⋆t , zt,at ⟩ + ηt .
The following proposition shows our regret bound for thisaction-dependent context case. Its proof largely draws upon
the proof idea of Theorem 1 and also relies on the generalized EPL Lemma 1.
Proposition 2. The regret of poLinUCB in Algorithm 1for action-dependent contexts
is upper bounded by√√e T 1−α dα
O
K
+
d
T
K
with
probability at least 1−δuu

6.1. Synthetic Data with Ground Truth Models
Evaluation Setup. We adopt three different synthetic environments that are representative of a range of mappings fromthe pre-serving context to the post-serving context: polynomial, periodicical and linear functions. The pre-serving
contexts are sampled from a uniform noise in the range[−10, 10]dx , and Gaussian noise is employed for both thepost-serving contexts and the rewards. In each environment, the dimensions of the pre-serving context (dx ) andthe post-serving context (dz ) are of 100 and 5, respectively
with 10 arms (K). The evaluation spans T = 1000 or 5000
time steps, and each experiment is repeated with 10 different seeds. The cumulative regret for each policy in eachenvironment is then calculated to provide a compararison.

if T = Ω(log(1/δ)).
The main differencewith the bound in Theorem 1 is the√
additional K appeared in the first term, which is causedby learning multiple ϕ⋆a (·) functions with a ∈ A.
5.2. Generalization to Linear Stochastic Bandits
Another variant of linear bandits is the linear stochastic
bandits setup (see, e.g., (Abbasi-Yadkori et al., 2011)). Thismodel allows infinitely many arms, which consists of a decision set Dt ⊆ Rd at time t, and the learner picks an action
xt ∈ Dt . This setup naturally generalizes to our problem with post-serving contexts. That is, at iteration t, thelearner selects an arm xt ∈ Dt first, receives reward rt,xt ,and then observe the post-serving feature zt conditioned
on xt . Similarly, we assume the existence of a mappingϕ⋆ (xt ) = E[zt |xz ] that satisfies the Assumption 1. Consequently, the realized reward is generated as follows whereθ ∗ , β ∗ are unknown parameters:

Results and Discussion. Our experimental results, which
are presented graphically in Figures 1, provide strong evidence of the superiority of our proposed poLinUCB algorithm. Across all setups, we observe that the LinUCB (xand z) 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 poLinUCB (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 (xonly), which operates solely based on the pre-serving context.

rt,xt = ⟨xt , θ ⋆ ⟩ + ⟨zt , β ⋆ ⟩ + ηt .
Therefore, the learner needs to estimate the linear paramb as well as the function ϕ(·).
beters θb and β,
We obtain thefollowing proposition for the this setup.
Proposition 3. The regret of poLinUCB in Algorithm
 1 for the √above setting is upper bounded by
1−α α
e
O T
du + du T with probability at least 1 − δ if
T = Ω(log(1/δ)).
7

Improving Contextual Bandits via Post-serving Contexts

Cumulative Regret51e5

ϕ(x) = W⊤(x2) + b

1e6

1.0

4

0.8

3

0.6

2

0.4

1

0.2

ϕ(x) = W⊤sin(x) + b

2.0

ϕ(x) = W⊤x + b

1e6

1.5

1.0

0

0

1000

2000

3000

4000

Time steps
Random

5000

0.0

0.5

0

LinUCB (x only)

200

400

600

Time steps

800

LinUCB (x and z)

1000

0.0

0

LinUCB (ϕ)̂

200

400

600

Time steps

800

1000

poLinUCB (ours)

Cumulative Regret

Figure 1: Cumulative Regret in three synthetic environments. Comparisons of different algorithms in terms of cumulative
regret across the three synthetic environments. Our proposed poLinUCB (ours) consistently outperforms other strategies (except for LinUCB which has access to 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.
served in our synthetic experiments. Our proposed policy
MovieLens
500
consistently outperforms the other strategies (except for
RandomLinUCB with both pre-serving and post-serving features).
LinUCB (x only)
400
LinUCB (x and z)
Significantly, our algorithm yields superior performance
LinUCB (ϕ)̂
compared to policies operating solely on the pre-serving
300
poLinUCB (ours)
context, thereby demonstrating its effectiveness in leverag200
ing the post-serving information.
100

7. Conclusions and Limitations
0

0

100

200

300

Time steps

400

500

In this work, we have introduced a novel contextual bandit
framework that incorporates post-serving contexts, thereby
widening the range of complex real-world challenges it canaddress. By leveraging historical data, our proposed algorithm, poLinUCB, estimates the functional mapping frompre-serving to post-serving contexts, leading to improved
online learning efficiency. For the purpose of theoreticalanalysis, 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 realworld datasets have demonstrated the significant benefits ofutilizing post-serving contexts and the superior performanceof our algorithm compared to state-of-the-art approaches.

Figure 2: Results on MovieLens.
6.2. Real World Data without Ground Truth
Evaluation Setup. The evaluation was conducted on areal-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
a 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 userfeature vectors were divided into two parts serving as the
pre-serving context (dx = 25) and the post-serving context (dz = 7). We fit the function ϕ(x) using a two-layer
neural network with 64 hidden units and ReLU activation.
The network was trained using the Adam optimizer witha learning rate of 1e-3. At each iteration, we randomly
sampled a user from the dataset and exposed only the preserving context x to our algorithm. The reward was computed as the dot product of the user’s feature vector and theselected movie’s feature vector and was revealed post themovie selection. The evaluation spanned T = 500 iterations
and repeated with 10 seeds.

Our theoretical analysis hinges on the assumption that thefunction ϕ⋆ (·) is learnable, a condition that may not always
be feasible. This especially applies to settings where thepost-serving contexts may hold additional information thatcannot be deduced from the pre-serving context, irrespective of the amount of data collected. In such scenarios,
no function mapping from the pre-serving context to thepost-serving context will satisfy the learnability assumption.
Consequently, a linear regret is inevitable, and it will be
proportional to the level of misspecification. However, froma practical point of view, our empirical findings from thereal-world MovieLens dataset demonstrate that modelingthe functional relationship between the pre-serving and postserving contexts can significantly enhance recommendation.

Results and Discussion. The experimental results, presented in Figure 2, demonstrate the effectiveness of our
proposed algorithm. The overall pattern is similar to it ob8

Improving Contextual Bandits via Post-serving Contexts

References

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.

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advancesin neural information processing systems, 24, 2011.

Tor Lattimore and Csaba Szepesvári. Bandit algorithms.
Cambridge University Press, 2020.

Naoki Abe, Alan W Biermann, and Philip M Long. Reinforcement learning with immediate rewards and linear
hypotheses. Algorithmica, 37:263–293, 2003.

Lihong Li, Wei Chu, John Langford, and Robert E Schapire.
A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670,
2010.

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.

Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimalalgorithms for generalized linear contextual bandits. In
International Conference on Machine Learning, pages
2071–2080. PMLR, 2017.

Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári.
Exploration–exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer
Science, 410(19):1876–1902, 2009.

Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimaxoptimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173–2174. PMLR,
2019.

Peter Auer. Using confidence bounds for exploitationexploration trade-offs. Journal of Machine Learning
Research, 3(Nov):397–422, 2002.
Alexandra Carpentier, Claire Vernade, and Yasin AbbasiYadkori. The elliptical potential lemma revisited. arXiv
preprint arXiv:2010.10182, 2020.

Tyler Lu, Dávid Pál, and Martin Pál. Contextual multiarmed bandits. In Proceedings of the Thirteenth international conference on Artificial Intelligence and Statistics,
pages 485–492. JMLR Workshop and Conference Proceedings, 2010.

Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR
Workshop and Conference Proceedings, 2011.

Alessandro Nuara, Francesco Trovo, Nicola Gatti, and Marcello Restelli. A combinatorial-bandit algorithm for the
online joint bid/budget optimization of pay-per-click advertising campaigns. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.

Varsha Dani, Thomas P Hayes, and Sham M Kakade.
Stochastic linear optimization under bandit feedback.
2008.

Hongju Park and Mohamad Kazem Shirani Faradonbeh.
Analysis of thompson sampling for partially observable
contextual multi-armed bandits. IEEE Control Systems
Letters, 6:2150–2155, 2021.

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.

Yi Qi, Qingyun Wu, Hongning Wang, Jie Tang, andMaosong Sun. Bandit learning with implicit feedback.
Advances in Neural Information Processing Systems, 31,
2018.

Nima Hamidi and Mohsen Bayati. The elliptical potential
lemma for general distributions with an application tolinear thompson sampling. Operations Research, 2022.

Paat Rusmevichientong and John N Tsitsiklis. Linearlyparameterized bandits. Mathematics of Operations Research, 35(2):395–411, 2010.

F Maxwell Harper and Joseph A Konstan. The movielens
datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1–19, 2015.

Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multiarmed bandit experiments. Marketing Science, 36(4):500–522, 2017.

Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, andRebecca Willett. Scalable generalized linear bandits:
Online computation and hashing. Advances in Neural
Information Processing Systems, 30, 2017.

Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. Mobile
Health: Sensors, Analytic Methods, and Applications,pages 495–517, 2017.
9

Improving Contextual Bandits via Post-serving Contexts

Joel A Tropp et al. An introduction to matrix concentration inequalities. 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, Qingyun Wu, and Hongning Wang. Learning hidden features for contextual bandits. In Proceedingsof the 25th ACM international on conference on information and knowledge management, pages 1633–1642,
2016.
Huazheng Wang, Haifeng Xu, and Hongning Wang. Whenare 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 a collaborative environment. In Proceedings of the 39th International ACM
SIGIR conference on Research and Development in Information Retrieval, pages 529–538, 2016.
Jianyi Yang and Shaolei Ren. Robust bandit learning withimperfect context. In Proceedings of the AAAI Conferenceon 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.
Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang,and Haifeng Xu. How bad is top-k recommendation undercompeting content creators? International Conference
on 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.

10

Improving Contextual Bandits via Post-serving Contexts

A. Extended Discussions
A.1. Related Works
Contextual bandits. The literature on (generalized) linear (contextual) bandits is extensive, as evidenced by numerous
studies (Abe et al., 2003; Auer, 2002; Dani et 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 et al., 2017). These approaches
predominantly employ upper confidence bounds as a means of balancing exploration and exploitation, leading to theattainment of minimax optimal regret bounds. The derivation of these regret bounds principally hinges on the utilization ofconfidence ellipsoids and the elliptical potential lemma. All these works assume that the contextual information governing
the payoff is full observable. In contrast, our work focuses on scenarios where the context is not completely observable
during arm selection, thereby presenting additional complexities in managing the 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 theparameter initialization is extremely close to the true optimal parameter, then they develop a sub-linear regret algorithm.
Our algorithm does not need such strong assumption on parameter initialization and we also show that their approach may
perform poorly in our setup. Subsequent research by Qi et 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, thelearning 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 to get a near-optimal regret bound.
Generalizing the elliptical potential lemma (EPL). The EPL, introduced by Lai and Wei (1982), serves as a criticalcomponent in quantifying the rate at which uncertainty decreases with the addition of more observations. Initially employedin 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 et al., 2020;
Wang et 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 Xt−p -norm, as
opposed to the traditional Xt−1 -norm. Meanwhile, (Hamidi and Bayati, 2022) investigated a generalized form of the2
1 ∧ ∥φ(xt )∥X −1 term, which was inspired by the pursuit of variance reduction in non-Gaussian linear regression models.
t−1
However, existing (generalized) EPLs are inadequate for the analysis presented herein.

b
B. Algorithm and Regret Analysis of LinUCB(ϕ)
We present the details of the algorithm described in Section 2.2 and the proof of the regret bound.
B.1. Main Algorithm
Parameter learning. We consider solving the following regularized least squared problem for estimating {θbt,a }a∈A and{βbt,a }a∈A for each arm a:ℓt (θa , βa ) =

t

X

⊤
b
rs,a − x⊤t θa − ϕs (xs ) βa2
+ λ ∥θa ∥22 + ∥βa ∥22 ,(10)s:as =awhere λ ≥ 0 are penalty factors ensuring the uniqueness of minimizers θbt,a and βbt,a .
bIn the same convention, we use w to denote (θ, β), and u to denote x, ϕ(x). The closed-form solutions for θbt,a andβbt,a in this least squared problem then become:
"

#
θbt,a
bt,a := bw= A−1t,a bt,a ,βt,a11Improving Contextual Bandits via Post-serving Contexts

where we reload the notations of At,a and bt,a ,tX

At,a = λI +

us u⊤
s

and

bt,a =

s:as =at
Xrs,a us .

(11)s:as =aConfidence set construction. At iteration t, we construct the confidence set for ϕbt (xt ) byn
Ct ϕbt , xt := z ∈ Rd : ϕbt (xt ) − ϕ⋆ (xt )2o≤ eδt .

(12)bt,a will be different, as we are using the predicted value ϕbt (·) for linear
The construction of the confidence set for w
regression. Consider the following,"At,a#  !






t
t
⊤
X
X
xs
xs
θbt,a
θa⋆
⊤ ⋆
⋆
⋆
b
− ⋆
=
ϵs βa b+ϕ (xs ) − ϕs (xs ) βa b
βaϕs (xs )ϕs (xs )βbt,as:as =as:as =a
|
{z
} |
{z
}
1
2




t
X
xs
θ⋆
+
ηs b
− λ a⋆βaϕs (xs )s:as =a{z} | {z }|4
3

Therefore, the confidence set will be enlarged due to the error introduced by ϕbt (·). In the below, we derive the confidence
set. To build the confidence set, we need to bound"⋆bt,a − wt,a∥w
∥At,a =

#  
θbt,a
θa⋆
−
βa⋆
βbt,a

=

1 + 2 + 3 + 4

At,a

A−1
t,a

Since both {ϵs }ts=1 and {ηs }ts=1 are i.i.d sub-Gaussian random variables, respectively, we can use the self-normalized
inequality to bound the corresponding terms, i.e., the followings hold with probability at least 1 − 2δ,s!
t
1/2 det(λI)−1/2
X
√
L
det(A
)
t,a
u
⋆
bt,a − wt,a
+√
eδ/t
+2 λ
∥w
∥At,a ≤ 2(L2ϵ + Rη2 ) log
s
δ/2
λ s=1
s
!


t
2 /λ
X
√
L
1
+
n
(a)L
t
u
u
δ/t
≤ 2(L2ϵ + Rη2 ) log
+√
es
+2 λ
δ/2
λ s=1


Therefore, the confidence set isbt,a ) = w ∈ Rdu : ∥w − w
bt,a ∥At,a ≤ ζt,a ,Ct,a (w

(13)

 √
√
/ λ + 2 λ. In comparison to the original
confidence set, there is one additional term due to the generalization error introduced from ϕbs (·). In the next section, we

where ζt,a =q2(L2ϵ + Rη2 ) log ((1 + nt (a)L2u /λ)/(δ/2)) + Lu

12

P

δ/t
t
s=1 esImproving Contextual Bandits via Post-serving Contextsb (Linear UCB adapted from Wang et al. (2016) with post-serving contexts; The differences with
Algorithm 2 LinUCB-(ϕ)
Algorithm 1 are highlighted in blue color.)
1: for t = 0, 1, . . . , T do
2:
Receive the pre-serving context xt
3:Compute the optimistic parameters by maximizing the UCB objective



4:




et =
at , ϕet (xt ), w

arg maxbt−1 ,xt )×Ct−1 (wbt−1,a(a,ϕ,wa )∈[K]×Ct−1 (ϕ

xt
ϕ(x
t)
)

⊤
wa .

Play the arm at and receive the realized post-serving context as zt and the real-valued reward
rt,at =

 ⊤
xt
wa⋆t + ηt .
ztCompute the estimated post-serving context generating function ϕbt (·) using ERM.
bt,a by solving Equation 10 for each a.
Compute w
bt,a ) and Ct (ϕbt , xt ) for each a based on Equations 12 and 5.
7:
Update confidence sets Ct (w
8: end for5:
6:will provide a regret analysis, which following from the proof of LinUCB (Li et al., 2010). We simply have the following
v
u T
T
T
u X
X
 X
RT =
rt,a⋆t − rt,at =∆2t∆t ≤ tT
t=1

t=1

v

u
u X
T
u
 ϕet (xt ) − ϕ⋆ (xt )
≤ tT

t=1



xt
ϕ⋆ (xt )βeat +

t=1

v
u
u
≤ tT

"


A−1
t−1,a

2 ϕet (xt ) − ϕ⋆ (xt )

2

2

βeat

2
+ 2ζT,a

 2



 2

1∧

T
X

2 ϕet (xt ) − ϕ⋆ (xt )

2

2

βeat

2
+ 2ζT,axt
ϕ⋆ (xt )

1∧

t=1

s
≤



T · 8C0 T 1−2α log2α

det Xtdet X0



2

#



t

xt
ϕ⋆ (xt )



t=1

v
u
u
≤ tT

t

t

T
X

θeat − θatβea − βaAt−1,at

!!

A−1
t−1,a

t

!!

A−1
t−1,a

t


 

T
T L2u
log2
+ 2KζT2 du log 1 +δλduIn the next, we expand the term ζT2 ,s
ζT2 ≤ 

2(L2ϵ + Rη2 ) log≤ 6(L2ϵ + Rη2 ) log



1 + T L2u /λδ/2

1 + T L2u /λ
δ/2



Lu



P

+

3L2u
+
λ

T
X

δ/T
T
s=1 es

√

λ



√

2

+ 2 λ

!2
eδ/T
s

+ 12λ

s=1

In the next, we bound the second term in the above equation under the learnability assumption 1,
T
X

!2
eδ/T
s

≤ 16T 2−2α log2α

s=1

13



det XT
det X0



log2

 
T
.
δ

Improving Contextual Bandits via Post-serving Contexts

Therefore, naively choosing the value of λ will lead to a linear regret due to the term T 3/2−α in the equation. To minimize
the upper bound, we can choose the value of λ to be
λ = 2Lu T 1−α logα

det XT
det X0


log

 
T
.
δ

Then, we can bound ζT2 byζT2 ≤ 6(L2ϵ + Rη2 ) log



1 + T L2u /λδ/2+ 48Lu T 1−α logα

det XT
det X0


log

 
T
.
δ

By plugging it in and following the simplication as in the proof of Theorem 1, we can get the regret is upper bounded bype T 1−α dα + T 1−α/2 Kd1+α.
Ouu
The above result is summarized as the following proposition.
bb in Algorithm 2 is upper bounded by
Proposition
1 (RegretThe regret of LinUCB-(ϕ)ϕ)).
p of LinUCB-(
1−α/2e T 1−α dαO
Kd1+αwith probability at least 1 − δ, by carefully setting the regularization coefficient
u
u +T
1−α
λ = Θ(Lu dαlog (T /δ)) in Equation 1.
uT

C. Missing Proofs
C.1. Missing Proofs in the Generalized Elliptical Potential Lemma
Lemma 1 (Generalized Elliptical Potential Lemma). Suppose (1) X0 ∈ Rd×d is any positive definite matrix; (2)x1 , . . . , xT ∈ Rd is a sequence of vectors with bounded l2 norm maxt ∥xt ∥ ≤ Lx ; (3) ϵ1 , . . . , ϵT ∈ Rd is a sequence of2independent (not necessarily identical) bounded zero-mean noises satisfying maxt ∥ϵt ∥ ≤ Lϵ and E[ϵt ϵ⊤t ] ≽ σϵ I for any t;
ft is defined as follows:and (4) X
ft = X0 +XtX(xs + ϵs )(xs + ϵs )⊤ ∈ Rd×d .
s=1

Then, for any p ∈ [0, 1], the following inequality holds with probability at least 1 − δ,


T 
p
X
det XT1 ∧ ∥xt ∥2X≤ 2p T 1−p logp
f−1
t−1
det X0
t=1


2
2
2
8L (Lϵ + Lx )32dLϵ (Lϵ + Lx )2
+ ϵ
log
σϵ4
δσϵ4

(2)

Proof. Our proof follows the high level idea for proving the original EPL. However, to accommodate the noises in the data
matrix, we have to introduce new matrix concentration tools to the original (primarily algebraic) proof, and also identify theright conditions for the argument to go through. A key lemma to our proof is the following high probability bound regarding
the noisy data matrix:
Lemma 2. Let x1 , ..., xT ∈ Rd be a fixed sequence of vectors, and ϵ1 , ..., ϵT ∈ Rd are independent random variables⊤
2
satisfying max
 t ∥xt ∥2 ≤ Lx , maxt ∥ϵt ∥2 ≤ Lϵ , and E[ϵt ϵt ] ≽ σϵ I. Then the following hold with probability at least1 − 2d exp−T σϵ48L2ϵ (Lϵ +Lx )2,

TX(xt + ϵt )(xt + ϵt )⊤ ≽

t=1

T
X
t=1

14

xt x⊤
t .

Improving Contextual Bandits via Post-serving Contexts

The Proof of Lemma 2 employs the Bernstein’s Inequality for matrices (Tropp et al., 2015), which is technical; for ease ofpresentation, we defer its proof of Appendix
2, we have that, for every t ∈ [T ], the following inequality C.1. By Lemmaholds with probability at least 1 − 2d exp
ft = X0 +X−tσϵ4
8L2ϵ (Lϵ +Lx )2t
X:(xs + ϵs )(xs + ϵs )⊤ ≽ X0 +

s=1

t
X

xs x⊤
s := Xt ,s=1

under which we have∥xt+1 ∥2Xe −1 ≤ ∥xt+1 ∥2X −1 .
tt

To prove our Lemma 1, we need to apply union bound to guarantee the above hold simultaneously for every t ≥ 1 withhigh probability. Unfortunately, this turns out to not be true because when t is very small (e.g., t = 1), the above inequality
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′ ∈ [T ], as follows
hi
P ∀t ∈ [t′ , T ], ∥xt ∥2Xe −1 ≤ ∥xt ∥2X −1
t−1

t−1

≥1−
≥1−

T
−1
X

−tσϵ4


2d expt=t′ −1∞X
t=t′ −1(8L2ϵ (Lϵ + Lx )2 )


2d exp−tσϵ4
2(8Lϵ (Lϵ + Lx )2 )!
exp − (t′ − 1)σϵ4 /(8L2ϵ (Lϵ + Lx )2 ).
1 − exp − σϵ4 /(8L2ϵ (Lϵ + Lx )2 )= 1 − 2d 16L2ϵ (Lϵ + Lx )2≥ 1 − 2d × exp − (t′ − 1)σϵ4 /(8L2ϵ (Lϵ + Lx )2 ) ×,
σϵ4
where the last inequality uses the fact that σϵ4 /(L2ϵ (Lϵ + Lx )2 ) ≤ (σϵ /Lϵ )4 ≤ 1 and 1 − e−x ≥ x/2 for any x ∈ [0, 1]. By
solving the following inequality,
 16L2ϵ (Lϵ + Lx )2δ
exp − (t′ − 1)σϵ4 /(8L2ϵ (Lϵ + Lx )2 ) ×
,
≤
4
σϵ
2d
we have,
8L2ϵ (Lϵ + Lx )2
t ≥1+
log
σϵ4
′



32dL2ϵ (Lϵ + Lx )2δσϵ4Let T0 denote the ceiling of the right-hand-side of the above term. Therefore, we have the following hold with highprobability at least 1 − δ:
T 
X
t=1

1 ∧ ∥xt ∥2Xe −1
t−1

p≤ (T0 − 1) +T X

1 ∧ ∥xt ∥2Xe −1p1 ∧ ∥xt ∥2X −1p

1 ∧ ∥xt ∥2X −1

p

t−1

t=T0

≤ (T0 − 1) +

T 
X

t−1

t=T0

≤ (T0 − 1) +

T 
X

t−1

t=T0

In the next, we are going to bound the second term in the above equation, whose proof can be adapted from the proof of theoriginal elliptical potential lemma. Using the fact that for any z ∈ [0, +∞], z ∧ 1 ≤ 2 ln(1 + z), we get
T
X
t=1

T 

p X

p
2 log 1 + ∥xt ∥2X −1.
1 ∧ ∥xt ∥2X −1
≤
t−1

t=1

15

t−1

Improving Contextual Bandits via Post-serving Contexts

Additionally, by definition, we have


1/2
−1/2
−1/2
1/2
⊤
Xt = Xt−1 + xt x⊤
=
X
I
+
X
x
x
X
Xt−1 .
t
t
t
t−1
t−1
t−1
This implies the following relationship between the determinant,


−1/2
−1/2
det Xt = det (Xt−1 ) det I + Xt−1 xt x⊤.
t Xt−1Since the only eigenvalues of a matrix of the form I + yy ⊤ are 1 + ∥y∥2 and 1, we have
log 1 + ∥xt ∥2X −1 = log det Xt − log det Xt−1 .
t−1

By taking the power p for both sides and taking the sum, we have
T 
X

T

p X
p
log 1 + ∥xt ∥2X −1=(log det Xt − log det Xt−1 ) .
t−1

t=1

t=1

Since p ∈ [0, 1], the function g(x) = xp is a concave function. Thus, we haveTT

1X
log det Xt − log det Xt−1
T t=1

1X
p
(log det Xt − log det Xt−1 ) ≤
T t=1

!p
=

1
logp
Tp



det XT
det X0.

Therefore, we can conclude that
T
X

1∧

t=1



∥xt ∥2X −1
t−1

p

p

≤2 T

1−p

log

p



det XT
det X0.

By combining the above results, we have the following hold with probability at least 1 − δ:
T 
X
t=1

1 ∧ ∥xt ∥2Xe −1
t−1

p≤ T0 − 1 +

T
X
t=1

!p
1 ∧ ∥xt ∥2X −1
t−1p≤ T0 − 1 + 2 T

det XT
det X0

32dL2ϵ (Lϵ + Lx )2
δσϵ4



1−p

log

p



.

Invoking
8L2ϵ (Lϵ + Lx )2
T0 − 1 ≤
log
σϵ4



32dL2ϵ (Lϵ + Lx )2
δσϵ4


,

we obtained the desired inequality with probability at least 1 − δ:T X1 ∧ ∥xt ∥2Xe −1

p

p

≤2 T

1−p

t−1

t=1

log

p



det XT
det X0

8L2ϵ (Lϵ + Lx )2
+
log
σϵ4



.

Lemma 2. Let x1 , ..., xT ∈ Rd be a fixed sequence of vectors, and ϵ1 , ..., ϵT ∈ Rd are independent random variables⊤
2
satisfying max
 t ∥xt ∥2 ≤ Lx , maxt ∥ϵt ∥2 ≤ Lϵ , and E[ϵt ϵt ] ≽ σϵ I. Then the following hold with probability at least1 − 2d exp−T σϵ48L2ϵ (Lϵ +Lx )2,

TX(xt + ϵt )(xt + ϵt )⊤ ≽

t=1

T
X
t=1

16

xt x⊤
t .

Improving Contextual Bandits via Post-serving Contexts

Proof. We will analyze the term-wise difference, denoted as⊤⊤⊤
St := (xt + ϵt )(xt + ϵt )⊤ − xt x⊤t = ϵ t x t + x t ϵt + ϵt ϵt(14)Moreover, since E[ϵt ] = 0 for any t ∈ [T ], the expectation of St (over randomness of noise) can be lower bounded as⊤⊤⊤
2
E[St ] = E[ϵt ]x⊤
t + xt E[ϵt ] + E[ϵt ϵt ] = E[ϵt ϵt ] ≽ σϵ I.

Since ∥xt ∥2 ≤ Lx and ∥ϵt ∥2 ≤ Lϵ , we know that St ≼ (2Lϵ Lx + L2ϵ )I with probability 1. Thus St is uniformly upperbounded under the spectral-norm denoted by ∥ · ∥, or formally∥St ∥ ≤ 2Lϵ Lx + L2ϵ .
PTConsider the “centered” matrix sum ZT = t=1 St − E[ϵt ϵ⊤], with mean 0. Since the spectral-norm of St is uppertbounded by 2Lϵ Lx + L2ϵ , its variance V(St ) = E St St⊤ 2 is upper bounded by (2Lϵ Lx + L2ϵ )2 . Thus, the variance ofPT
ZT equals the variance of sum t=1 St , which is then upper bounded by T (2Lϵ Lx + L2ϵ )2 . By the Bernstein’s Inequality
for random matrices (Tropp et al., 2015), we have the following high probability upper bound for the spectral norm ∥ · ∥ ofZT :−ι2 /2P [∥ZT ∥ ≥ ι] ≤ 2d exp.
(15)
V(ZT ) + (2Lϵ Lx + L2ϵ )ι/3
Since ZT is a symmetric matrix, its spectral norm upper bounds the absolute value of any eigenvalue. Thus we can lower
bound the smallest eigenvalues as follows:
"
!
#
T
X
P [∥ZT ∥ ≥ ι] ≥ P λmin
St − E[ϵt ϵ⊤
≤ −ι
t ]
t=1

"
≥ P λminT
X!
St − σϵ2 I

#
≤ −ι

t=1

"
= P λminTX!

#≤ T σϵ2 − ι

St

.

t=1

P

T
2
where the second inequality is due to two facts: (1) A ≽ B implies λmin (A) ≥ λmin (B) where A =
S
−
σ
I
ϵ
t=1 t
P

T
⊤
and B =
t=1 St − E[ϵt ϵt ] ; and (2) the event λmin (A) ≤ −ι thus is included within the event λmin (B) ≤ −ι.
Consequently, we have
"
!
#


T
X
−ι2 /2
2
P λminSt ≤ T σϵ − ι ≤ 2d exp,
V(ZT ) + (2Lϵ Lx + L2ϵ )ι/3
t=1
or equivalently,"
P λmin

T
X

!
St

#
≥ T σϵ2 − ι≥ 1 − 2d exp

t=1−ι2 /2
V(ZT ) + (2Lϵ Lx + L2ϵ )ι/3

By choosing the value of ι = T σϵ2 , we get
"
!
#
T
X
P λminSt ≥ 0t=1

−T 2 σϵ4 /2≥ 1 − 2d exp
V(ZT ) + (2Lϵ Lx + L2ϵ )T σϵ2 /3−T 2 σϵ4 /2≥ 1 − 2d exp.
T (2Lϵ Lx + L2ϵ )2 + (2Lϵ Lx + L2ϵ )T σϵ2 /3


17


,

Improving Contextual Bandits via Post-serving Contexts

Using the fact that σϵ ≤ Lϵ , we can further simplify the above equation by
"
!
#


T
X
−T σϵ4
P λmin.
St ≥ 0 ≥ 1 − 2d exp
8L2ϵ (Lϵ + Lx )2
t=1

C.2. Missing Proofs in the Regret Analysis√e T 1−α dαTheorem 1 (Regret of poLinUCB). The regret of poLinUCB in Algorithm 1 is upper bounded by Ou + du T K
with probability at least 1 − δ, if T = Ω(log(1/δ)).
Proof. In the next, we prove the regret bound. For each time step t, the immediate regret is∆t = rt,a⋆t − rt,at


 
xt
θa⋆t − θa⋆t=,ϕ⋆ (xt )βa⋆t − βa⋆t
*
"
#+

D
E
(a)
xt
θeat − θa⋆t≤
, e
+ ϕet (xt ) − ϕ⋆ (xt ), βa⋆t⋆eϕt (xt )βat − βat
*
#+
 
 "
D
E
0
xt
θeat − θa⋆t
et (xt ) − ϕ⋆ (xt ), β ⋆
=
+
+
ϕ
,
⋆
at
ϕ (xt )ϕet (xt ) − ϕ⋆ (xt )βeat − βa⋆t
*
"
#+

D
E
xt
θe − θa⋆t= ϕet (xt ) − ϕ⋆ (xt ), βeat +, eat⋆
ϕ (xt )
βat − βa⋆t
*
#+
 "
(b)
xt
θeat − θa⋆t⋆ee
≤ ϕt (xt ) − ϕ (xt ) · βat +, eϕ⋆ (xt )βat − βa⋆t
#
"


(c)
ea − θ ⋆
θ
x
t
⋆
a
t
t
.
≤ ϕet (xt ) − ϕ (xt ) · βeat +ϕ⋆ (xt ) A−1
βeat − βa⋆tt−1,aAt−1,attwhere the inequality (a) is 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
v
u T
T
u X
X
∆2t
RT =
∆t ≤ tT
t=1

t=1

v

u
u X
T
u
 ϕet (xt ) − ϕ⋆ (xt )
≤ tT


xt
ϕ⋆ (xt ) A−1

βeat +

t=1

v
u
u
≤ tT

T
X

t−1,at2 ϕet (xt ) − ϕ⋆ (xt )

2

2

βeat

T
X

θeat − θatβeat − βat

1∧

2

#


At−1,at

 2xt
ϕ⋆ (xt ) A−1

!!

 2
xt
ϕ⋆ (xt ) A−1!!

+ 2ζT2

t=1

v
u
u
≤ tT

"



t−1,at2 ϕet (xt ) − ϕ⋆ (xt )

2

2

βeat



+ 2ζT21∧

t=1t−1,atIn the next, we bound each term separately. Firstly, we have the following hold with probability at least 1 − δ by using theunion bound,TX

2 ϕet (xt ) − ϕ⋆ (xt )22· βeat

t=1

≤8

T 
2
X
δ/T
et
.
t=1

18

Improving Contextual Bandits via Post-serving Contexts

In the next, to bound the remaining term, we use the result from Lemma 1. We first group the sums based the arm,
T
X

 2
xt
ϕ⋆ (xt ) A−1


1∧

t=1

=

t−1,at

X

X

 2
xt
ϕ⋆ (xt ) A−11∧a∈A t∈[T ]:at =a

(16)

t−1,a

By denoting nT (a) as the number of times that arm a is pulled, we can divide the arms into two groups,
G0 := {a ∈ A : nT (a) = Ω(log(1/δ))}andG1 := A \ G0 .

Then, we can further decompose the r.h.s term of Equation 16 based on if the corresponding arm is in G0 or G1 . Then, byapplying Lemma 1, we have the following holds, with probability at least 1 − δ,
X

X


1∧

a∈A t∈[T ]:at =axt
ϕ⋆ (xt )

 2
A−1
t−1,a

 2

 2
X
X
xt
xt
=
1∧
+
1∧
ϕ⋆ (xt ) A−1ϕ⋆ (xt ) A−1
a∈G1 t∈[T ]:at =aa∈G0 t∈[T ]:at =a
t−1,a
t−1,a




32Kdu L2ϵ (Lϵ + Lx )2T L2u
8KL2ϵ (Lϵ + Lx )2log.
≤2Kdu log 1 +
+
λdu
σϵ4
δσϵ4
X

X



where the last inequality is due to Lemma 1 and apply the union bound on the K arms. To bound the remainder term, sinceα ∈ [0, 1/2], by the learnability assumption as stated in Assumption 1 and Lemma 1, we have
 
T 
T
2 X

2α
X
tT
δ/t
et
≤
C02 · 1 ∧ ∥x∥2X −1· log2
t−1
δ
t=1
t=1


 
det XTT≤ 4C02 T 1−2α log2α
log2
det X0
δ


 
2
T
L
/d
+
λ
T
2α
2
u
2 1−2α 2α≤ 4C0 Tdu loglogλδTherefore, the total regret bound is bounded by the following term with probability at least 1 − 2δ,
s






 



T L2u
det XT
T
48L4ϵ L2u
192Kdu L4ϵ L2u
T · 8C0 T 1−2α log2α
log2+ KζT2 du log 1 ++log
det X0
δ
λdu
σϵ4
δσϵ4

By hiding the logarithmic terms, we can further simplify it to be√e T 1−α dα
O
+
d
T
K
u
u

C.3. Missing Proofs in Generalizations
Proposition
2. The regret of poLinUCB in Algorithm 1 for action-dependent contexts is upper bounded by√√e T 1−α dαOu K + du T K with probability at least 1 − δ if T = Ω(log(1/δ)).
Proof. Our proof follows from the proof of Theorem 1. The immediate regret at each time step t is
∆t = rt,a⋆t − rt,at
19

(17)

Improving Contextual Bandits via Post-serving Contexts

Recall that the definition of a⋆t ,a⋆t := arg max⟨θa⋆ , xt,a ⟩ + ⟨βa⋆ , ϕ⋆a (xt,a )⟩.

(18)

a∈A

To bound the immediate regret, we have∆t = ⟨θa⋆⋆t , xt,a⋆t ⟩ + ⟨βa⋆⋆t , ϕ⋆a⋆t (xt,a⋆t )⟩ − ⟨θa⋆t , xt,at ⟩ − ⟨βa⋆t , ϕ⋆at (xt,at )⟩.

(19)

By the definition of UCB, we further have∆t ≤ ⟨θet,at , xt,at ⟩ + ⟨βet,at , ϕe⋆t,at (xt,at )⟩ − ⟨θa⋆t , xt,at ⟩ − ⟨βa⋆t , ϕ⋆at (xt,at )⟩.

(20)

By rearranging the terms, we get∆t ≤ ⟨θet,at − θa⋆t , xt,at ⟩ + ⟨βet,at − βa⋆t , ϕ⋆at (xt,at )⟩ + ⟨βet,at , ϕet,at (xt,at ) − ϕ⋆at (xt,at )⟩
{z
} |
{z
}
|
1
2

(21)

Bounding the first term 1 is the same as the proof in Theorem 1, while bounding the second term 2 will be slightly
different, as we now have K such functions of ϕ⋆a (·) for a ∈ A to learn. By denoting the error for each estimate of ϕ⋆a (·) at
iteration t as eδt,a . Therefore, the contribution from the second term to the total regret can be bounded by
T 
2 X
X
δ/t
et,at =
t=1


2
t/δ
et,a

X

(22)

a∈A t∈[T ]:at =a≤ 4KC0 T 1−2α log2α

det XT
det X0



log2

 
T
.
δ

(23)

Hence, by following the remaining steps in the proof of Theorem 1, we can conclude that the regret is upper bounded by√√e T 1−α dα
O
K
+
d
T
K
,
(24)
u
u
√
where the only difference is the additional K appeared in the first term.
√ 
e T 1−α dαProposition 3. The regret of poLinUCB in Algorithm 1 for the above setting is upper bounded by Ou + du T
with probability at least 1 − δ if T = Ω(log(1/δ)).
Proof. This proof also follows from the proof of Theorem 1. The immediate regret at each time step t is
∆t = rt,x⋆t − rt,xt(25)

x⋆t := arg max⟨θ ⋆ , x⟩ + ⟨β ⋆ , ϕ⋆ (x)⟩.

(26)∆t = ⟨θ ⋆ , x⋆t ⟩ + ⟨β ⋆ , ϕ⋆ (x⋆t )⟩ − ⟨θ ⋆ , xt ⟩ − ⟨β ⋆ , ϕ⋆ (xt )⟩(27)

Recall that the definition of x⋆t ,x∈Dt

To bound the immediate regret, we have

By the definition of UCB, we further have∆t ≤ ⟨θet , xt ⟩ + ⟨βet , ϕe⋆t (xt )⟩ − ⟨θ ⋆ , xt ⟩ − ⟨β ⋆ , ϕ⋆ (xt )⟩.

(28)

By rearranging the terms, we get∆t ≤ ⟨θet − θ ⋆ , xt ⟩ + ⟨βet − β ⋆ , ϕ⋆ (xt )⟩ + ⟨βet , ϕet (xt ) − ϕ⋆ (xt )⟩
|
{z
} |
{z
}
1
2
Since we only need to fit a single θ ⋆ , β ⋆ and ϕ⋆ (·). We thus have the following bound for the total regret,√ 
e T 1−α dαOu + du T .

20

(29)

(30)

Improving Contextual Bandits via Post-serving Contexts

D. Technical Lemmas
Lemma 3 (Confidence Ellipsoid, based on Theorem 2 of (Abbasi-Yadkori et al., 2011)). Let w⋆ ∈ Rd , V0 = λI, λ > 0.
For any t ≥ 0, let u1 , · · · , ut ∈ Rd , define rt = ⟨ut , w⋆ ⟩ + ηt where ηt is Rη -sub-Gaussian and assume that ∥w⋆ ∥2 ≤ Lw ;Pt
let Vt = V0 + s=1 us u⊤s and ŵt be the corresponding regularised least-square estimator. Then, for any δ > 0 and t ≥ 0,with probability at least 1 − δ, w⋆ lies in the set:
v

!
u
1/2


−1/2
u
√
det (Vt ) det(λI)
Ct = w ∈ Rd : ∥ŵt − w∥Vt ≤ λLw + Rη t2 log
.
(31)


δ
Furthermore, if for all t ≥ 1, ∥ut ∥ ≤ Lu , then for any δ > 0 and t ≥ 0, with probability at least 1 − δ, w⋆ lies in the set:
s
(

)
√
1 + tL2u /λdCt = w ∈ R : ∥ŵt − w∥Vt ≤ λLw + Rη d log.
(32)δ
Lemma 4 (Bernstein’s Inequality for Matrices, Theorem 6.1.1 of (Tropp et al., 2015)). Let X1 , · · · , Xn ∈ Rd1 ×d2 be
independent and centered random matrices. Assume that for each i ∈ [n], Xi is uniformly bounded, that is:∥Xi ∥ ≤ B,

E [Xi ] = 0 and(33)

where ∥ · ∥ denotes the spectral-norm distance here. Introduce the sum
Z=

n
X

Xi ,

(34)

i=1

and let V(Z) denote the matrix variance statistics of the sum Z:
V(Z) = max {∥E [ZZ ∗ ] ∥, ∥E [Z ∗ Z] ∥}
( n
)
n
X
X
∗
∗
= max
Xi Xi ,
Xi Xi
,
i=1

(35)
(36)

i=1

where the asterisk ∗ denotes the conjugate transpose operation. Then, for every ϵ ≥ 0, we have,−ϵ2 /2.
P ∥Z∥ ≥ ϵ ≤ (d1 + d2 ) · exp
V(Z) + Bϵ/3

21(37)