Leveraging Offline Data in Linear Latent Contextual Bandits
Authors: Chinmaya Kausik
Kevin Tan
Ambuj Tewari
Venue: ICML 2025 poster (2025)
Keywords: bandits
latent bandits
hybrid RL
online learning with offline datasets
dimensionality reduction
linear bandits
Primary area: theory->online_learning_and_bandits
TL;DR: We study how to use offline data to accelerate online learning in latent bandits. We first establish the generality of latent bandits and then focus on linear latent bandits, presenting algorithms with matching upper and lower bounds and experiments.

Abstract: Leveraging offline data is an attractive way to accelerate online sequential decision-making. However, it is crucial to account for latent states in users or environments in the offline data, and latent bandits form a compelling model for doing so. In this light, we design end-to-end latent bandit algorithms capable of handing uncountably many latent states. We focus on a linear latent contextual bandit &mdash; a linear bandit where each user has its own high-dimensional reward parameter in $\mathbb{R}^{d_A}$, but reward parameters across users lie in a low-rank latent subspace of dimension $d_K \ll d_A$. First, we provide an offline algorithm to learn this subspace with provable guarantees. We then present two online algorithms that utilize the output of this offline algorithm to accelerate online learning. The first enjoys $\tilde O(\min(d_A\sqrt{T}, d_K\sqrt{T}(1+\sqrt{d_AT/d_KN})))$ regret guarantees, so that the effective dimension is lower when the size $N$ of the offline dataset is larger. We prove a matching lower bound on regret, showing that our algorithm is minimax optimal. The second is a practical algorithm that enjoys only a slightly weaker guarantee, but is computationally efficient. We also establish the efficacy of our methods using experiments on both synthetic data and real-life movie recommendation data from MovieLens. Finally, we theoretically establish the generality of the latent bandit model by proving a de Finetti theorem for stateless decision processes.

Leveraging Offline Data in Linear Latent Contextual Bandits
Chinmaya Kausik
Kevin Tan
Ambuj Tewari
Abstract
dation (Li al. 2010), distributed networks (Kar al. 2011), and portfolio design (Brochu et al.) 2011). There is often wealth of offline data in such domains, which has led to growing interest in using offline data to accelerate online learning. However, there often also exist unobserved contexts in the population that influence the distribution of rewards, making it non-trivial to leverage offline data. In Hong et al. (2020), is shown that this uncertainty can be modeled by latent bandit (or mixture of bandits). This is bandit where an unobserved latent state determines the reward model for the trajectory. For example, a patient's un- derlying genetic conditions in healthcare and user's 's tastes in recommendation systems are both examples of latent states in sequential decision making. Typically, these latent states are less complex than the actual models underlying users or patients, making it valuable reduce the online task to learning the latent state (Hong et al. 2020 2022).
Leveraging offline data an attractive way to ac- celerate online sequential decision-making. How- ever, it is crucial to account for latent states in users environments in the offline data, and la- tent bandits form a compelling model for doing so. In this light, we design end-to-end latent ban- dit algorithms capable of handing uncountably many latent states. We focus on a linear latent contextual bandit - linear bandit where each user has its own high-dimensional reward param- eter in Rda, but reward parameters across users lie in low-rank latent subspace of dimension dx & dA- First, we provide an offline algo- rithm to learn this subspace with provable guar- antees. We then present two online algorithms that utilize the output of this offline algorithm to accelerate online learning. The first enjoys Ó(min(dvvT) dx TT(
(dxT)))))) re- gret guarantees, that the effective dimension is lower when the size N of the offline dataset is larger. We prove a matching lower bound on regret, showing that our algorithm is minimax op- timal up to coverage terms. The second a prac- tical algorithm that enjoys only slightly weaker guarantee, but is computationally efficient. We also establish the efficacy of our methods using experiments both synthetic data and real-life movie recommendation data from MovieLens, Fi- nally, we theoretically establish the generality of the latent bandit model by proving a de Finetti theorem for stateless decision processes.
The latent bandit framework therefore has high practical value, and efficient principled algorithms are needed for using offline data to speed up online learning. Using tradi- tional bandit algorithms in this setting does not leverage the offline data that is often available to the agent. Naturally, one also cannot treat the offline data as coming from a sin- gle bandit. For example, different user tastes or different underlying genetic conditions require modeling the offline data as coming from latent bandit. So, we have develop algorithms specific to the latent bandit setting that leverage the offline data to improve online performance.
We note that in bandit literature, it is common to impose structure on bandit rewards when designing algorithms, the most popular one being linear structure (Li et al., 2010 Abbasi- Yadkori et al., 201I). In this light, we study a linear contextual bandit setting where each user has its own high-dimensional reward parameter, but reward parameters across users lie in a low-rank subspace. This is a linear latent contextual bandi [ and is much more general than existing models that restrict themselves to finitely many latent states (Hong et al. 2020 2022). We design two- pronged algorithm to tackle this setting. First, we provide a method to approximate the low-dimensional subspace spanned by latent states from an offline dataset of unlabeled trajectories collected under some behavior policy m.. This non-trivial since the trajectories are unlabeled, and standard
1. Introduction
Many requential-decisonn making problems can be effec- tively modeled using the bandit framework. This can span domains as diverse as healthcare (Lu et al., (022bb) ran- domized clinical trials (Press) 2009). search and recommen-
'Department of Statistics, University of Michigan, USA 'Department of Statistics and Data Science, The Wharton School, University Pennsylvania, USA. Correspondence to: Chinmaya Kausik <ckausik @ umuch.edus.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
'This can also be thought as a continuous mixture of handits.

---

Leveraging Offline Data in Linear Latent Contextual Bandits
unsupervised learning methods fail. Second, we use this subspace speed up online learning. However, since the subspace is only learnt approximately, we also tackle the non-trivial task of accounting for the uncertainty in the subspace. We design two methods for the latter, facing a trade-off between computational tractability and tightness of guarantees. Experiments show the efficacy of our methods.
Meta learning, multi-task learning and mixture learn-
ing. A long line of work studies learning with multiple underlying tasks or models. For example, the work of Vempala and Wang (2004); KKng et al. (2020); A mar et al. (2014); Tripuraneni et al. (022) study learning under latent variable or multi-task models in a supervised setting. The work of Kausik et al. (2023); Chen and Poor (2022) extend some of these ideas to unsupervised but purely offline learning in a time-series setting. On the other hand, work like Yang et al. (2022); [Clla et al. (2022) instead focuses on the purely online setting of learning the low-rank structure while simultaneously in- teracting with multiple finitely many bandit instances. Finally, Zhou et al. (2024); Lu et al. (2021a) work with multiple underlying models in MDPs but in purely of- fline and generative model setting respectively. Unlike these papers, we crucially combine the offline and online settings for sequential data and study the problem of using offline data to accelerate online learning in bandits.
While latent bandits have thus shown to be powerful and tractable framework for accounting for uncertainty in re- ward models, the extent of their generality is unclear. Are there other stateless decision processes that generalize over latent bandits? We end by theoretically demonstrating that under very reasonable assumptions, the answer is no. We show a de Finetti theorem for decision processes, demon- strating that every "coherent" and "exchangeable" stateless (contextual) decision process is a latent (contextual) bandit. With this in mind, we outline our contributions below:
Offline method: We present SOLD, a novel offline method for learning low-dimensional subspaces of re- ward parameters with guarantees, inspired by the novel spectral methods in Kausik et al. (2023).
Hybrid (offfine-online) RL. Work in hybrid RL studies the use of offline data to accelerate online RL, first pro- posed by Song et al. (2023), with extensions to linear MDPs by Wagenmaker and Pacchiano (2023); Tan et al.) 2024). Cai al. (0224 studies the same problem for contextual bandits. However, all work so far assumes that the offline data is generated by a single model, and does not account for latent states. Our work explores a hybrid offline-online setting while also accounting for the offline data being generated by multiple underlying models.
Tight online algorithm: We present LOCAL- UCB, an online algorithm leveraging the subspace estimated offline to sharpen optimism, achieving ((min(dAv dxv + (daT/dxN)) regret.
We establish a matching lower bound showing that LOCAL-UCB minimax optimal. To the best of our knowledge, this is the first lower bound in a hy- brid (offline-online) sequential decision-making setting.
Lower Bound:
2. Linear Bandits With Latent Structure
Tractable online algorithm: Finally, we present ProBALL-UCB, practical and computationally efficient online algorithm with slightly looser regret guarantee. This also illustrates a general algorithmic idea for integrat- ing offline subspace estimation into optimistic algorithms.
We will first introduce latent contextual bandits, and then specialize to our linear model later in this section. A latent contextual bandit is a decision process with contexts X, actions A and an random latent state 0 that is sampled independently at the beginning of each trajectory. Given a sequence of contexts and actions, the rewards at all steps are independent conditioned on 0, and depend on the latent state 0, the context and the action. Since we often have access to an offline dataset of trajectories coming from different kinds of users or patients, it is important to account for a changing latent state 0 between trajectories.
Experiments: We establish the efficacy of our algo- rithms outlined above through a simulation study and a demonstration on real recommendation problem with the MovieLens-IM IM (Harper and Konstan 2015) dataset.
Theoretical generality: We are the first, to our knowl- edge, to prove de Finetti theorem for decision processes. This establishes the generality of the latent bandit model.
As we will see in Section 8 latent bandits are a powerful and general framework for encoding uncertainty in reward models. However, this generality is both a blessing and a curse. It is hard to design concrete algorithms without further assumptions on the structure and effect of the latent state A. We therefore focus on a linear structure here. We consider the natural generalization of the linear contextual bandit to the latent bandit setting, where we impose a lin- ear structure on the effect of low-dimensional latent states. We further justify this by noting that in most application domains, it is reasonable to assume that parsimonious,
Related work. There are three main threads of related work.
Latent Bandits. The line of work most relevant to us has been on latent bandits. The work of Hong et al.] (2020) 2022) studies the latent bandit problem under finitely many states. However, they black-box the offline step and do not provide end-to-end guarantees, and their ideas do not extend to infinitely many states. Our work seeks to provide end-to-end guarantees for both the offline and online component under infinitely many latent states.
2

---

Leveraging Offline Data in Linear Latent Contextual Bandits
low-dimensional latent state affects the reward distribution. This motivates the following definition.
both unknown a priori, making it hard leverage the low- dimensional structure of the problem. Second, a good choice of dimension dx is itself unknown a priori, and must be determined from data in a principled manner. Third, even if we learn the low-dimensional structure, our learning will be approximate, and the online procedure must account for this uncertainty. In the following sections, we will provide method to estimate and use latent subspaces given offline data that allows us to overcome these challenges.
Definition 1. A linear latent contextual bandit is a lin- ear bandit equipped with feature map for context-action pairs & : X' x A + IRdA, a latent random variable E R with distribution Do and a map U, : R + Rda such that for any H and context-action sequence ((11; (1 an)), the rewards (Vi,... .Y.... are in- dependent conditioned on O. Moreover, Yn 0 6( an)
T B + e, where is subgaussian noise indepen- dent of all actions and all other observations, and B = U.O.
Additional Notation. We use V denote regularized de- sign matrices given by μur + > ((x.a) ((2, a))(1, a)". We define D,,; = I - VV. and DN.; N >>>>> D De- note by 1, 2n.2 independent estimates of 3, from Tn Let M, = (3m, 1h.2 + 3n..3TT.) and My + Σ M..
Further, we note that WLOG U. has orthonormal columns: U. U. = -dd.- This is because for any invertible map A : Rdx + [Ráx, the observation distribution does not change upon replacing f with AO and U. with U.A-' One can see this as generalization of the fact that with finitely many latent states, the observations are not changed by permuting the latent states. That is, the observations are not changed by permuting latent trajectory labels while keeping trajectories with the same label together.
3. Estimating Latent Subspaces Offline
Although we do not have access to the values of the latent states O or to the map U., we can still extract useful informa- tion from data, To that effect, recall that we have access to a dataset Doff of N trajectories Tn = ([Fn,h On,h; Ja,h) )),a)) of length Ht collected by some behavior policy Tb.
Let us now assume that we have access to a dataset Doft of N short trajectories Tn ((In,1 (1,1, 1 ..., (Z..H. Hn.H: ) of length H, collected by some be- havior policy Tb. The trajectories are short in the sense that in most relevant domains, individual trajectories are not long enough to learn the underlying reward model. Each trajec- tory Tn has a different B, = U.O.. In online deployment, a single latent label 0. is chosen and rewards are generated using 3, = U.O.. At each timestep e, an agent observes contexts 2, and uses both the offline data and the online data at time t to execute a policy Te. Define the optimal action at time t by af := max, o(I,, dt) T B, We tackle the problem of minimizing the frequentis/ regret in linear latent contextual bandits, given by
How can offline data help us in online deployment? To minimize the regret, one must learn the reward parameter B. online. However, it is much easier to search among all latent states O E Rdx than to search among all possible reward parameters B E Rd since typically, dg < dA. So, it will help to learn some projection matrix U R U Rda + Rdx offline so that for any estimate 3g of B.. U' B. is an estimate of O, E Rdx, This amounts to learning a subspace of the feature space from logged bandit data. We therefore provide a method for Subspace estimation from Offline Latent bandit Data (SOLD) in Algorithm [ Recall that since the learnt subspace is approximate, we also need to compute the uncertainty over the subspace to get subspace confidence set that we can use online.
T Regr- Σ paz ai) B. Eaam, Cawn,l@(z ( B.).
On trajectory splitting and corrections. To extract the dx dimeennnsoonal subspace, we aim to estimate T
For example, in medical applications, data from short ran- domized controlled trials can be used to help an agent sug- gest treatment decisions for a new patient online. In this case, we would like the algorithm to administer the cor- rect treatments for each patient. This means that the fre- quentist regret is the relevant performance metric here, and not the Bayesian regret over some prior. Additionally, any worst-case bound on the frequentist regret is a bound on the Bayesian regret for arbitrary priors.
U, J.E which has the same dlg-dimensional span as U. This cannot be achieved by using a single estimator
Bn for each trajectory Tn and averaging the outer products B across all n. That is because the per-reward noise e will be shared by both copies of 3,,, and so the variance of will make E[ full rank. We therefore split each tra- jectory Tn to obtain two independent estimators fn,,, Bn,2, compute the outer products ar. 2, and obtain the top dx cigenvectors of the mean outer product across trajectories.
Challenges with latent bandits. Despite the linear as- sumption, and the dimension reduction obtained in the com- mon case when dx < d,. significant challenges remain. First, the value of the latent state 0 and the map U, are
However, there is a further wrinkle here. We cannot simply take the top dx eigenvectors of the mean outer product My. One can compute that E MMx] = EF 1D,,,1B,,3, T.T.D.D... Dn,2] =
3

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Algorithm 1 Subspace estimation from Offline Latent ban- dit Data (SOLD)
ized controlled trials or A/B testing, which are common sources of offline datasets. Even if this is not satisfied, Algo- rithm can learn a good subspace whenever M N22 has eigenspace close to the span of U.. e.g. when high- reward actions contribute heavily to D,,;- This can happen if offline trajectories were collected maximize rewards.
1: Input: Dataset Doft of collected trajectories Tn ((Tn,1. An.1, Tn. (In,H, An,H, Tn,1)) under a be- havior policy πT, dimension of latent subspace dk.
2: Divide each Tn into odd and even steps, giving trajec- tory halves T,,1 and Fn,2-
Returning to our scrutiny of My. let the covariance ma- trix of 0 be A and let its mean be μa. Then we have that E[My] = Ej Dr = [[Dm.]] (A + pape )0. E Dr.2]. So, we still cannot merely consider the top dx eigenvectors of My without accounting for D,..1- Intuitively, Da.,I captures the distortion in reward estimation caused by regularization in ridge regression We there- fore construct correction matrices DN.: and use them to "neutralize" the distortion from regularization. In particular, DN.MMNNN2 N.2 is an estimator for U. (A + pa " Cru- cially, this allows us to aggregate information across many trajectories to overcome the challenge of learning from short trajectories. We can now take the top dx eigenvectors of D Tw.MMNDr N22 to estimate the subspace determined by U.. To give guarantees, we must make a coverage assumption. Unlike in standard offline RL, where only coverage along actions is needed, we also need coverage along latent states.
3: Estimate reward parameters Bnii + n, bn where Vnçi pll Eizarrer... a))(())) a) and b E (z.a,)))r.. 0 a)r for i 1,2.
4: Compute Mn + (Bm,117,2 n + B,,2 and com- pute My < E Mn.
5: Compute DN. + 1 En -UT--VW-i w.,. i = 1,2.
N
6: Obtain U, the top dx eigenvectors of D N.1 My D D222
7: return Projection matrix ÜÜT, Doff as in Theorem
E[D,,,U,0,0,, Dn,2l- To separate E from this, we need Dm,1, Br, Da, to be independent. If mi does not use 0 and contexts are generated independently of each other and of 0, then this is satisfied. Intuitively, we need the offline trajectories to be non-adaptive. In fact, we show in the lemma below that if any of these three conditions is violated, then it is in fact impossible to determine the latent subspace U* using any method, even with infinitely many infinitely long trajectories.
MyDN,2
Assumption 2 (Boundedness and Coverage). Rewards |nn, S R 3 for all n, ht [ a)Il I and || I R. Also, X = min Amin (n.)) > 0 and Xg :=
1 R2 Amiu (A) > 0.
Lemma (Contexts, 0, and To cannot be dependent). For each of these conditions:
Intuitively, XA measures coverage along actions, while A measures coverage along latent states 0. Both must be non-zero to expect satisfactory estimation of the subspace. Unlike the setting of Yang et al. (2022), whose setting is purely online, we work with an offline dataset of trajectories spanning multiple bandit instances. The learner has no con- trol over the behavior policy that collected the data. Without structural assumptions on the dataset, estimating a useful subspace becomes infeasible, and the regret degenerates to the standard dav Similar coverage assumptions are commonplace within the offline linear MDP literature (Jin et al. 2021 Duan and Wang 2020).
1. Contexts in a trajectory are dependent but do not depend on 0, and Tr also does not use A,
2. Contexts are generated independently using 0, while To does not use 0,
3. Contexts are generated independently without using 0, while Th uses O,
there exist two different linear latent contextual bandits with orthogonal latent subspaces satisfying the condition, and a behavior policy Ta so that the offline data distributions are indistinguishable and cover all (I, a) pairs with probability at least 1/4. Since the latent subspaces are orthogonal, an action that gives the maximum reward on one latent bandit gives reward on the other.
We can then use confidence bounds for M and D to give data-dependent confidence bound Dorr for the projection matrix ÚÙ" as in Theorem 1 below. In one instantiation, Propositions T and 2 in Appendix C derive simple data- dependent bounds for My and D,, respectively. Under this choice, we control the growth of Doff in terms of the unknown problem parameters at the end of Theorem I
To estimate the latent subspace, one is thus forced to make the following assumption.
Assumption 1 (Unconfounded Offline Actions). The offline behavior policy मe does not use to choose actions, and contexts Tn. are stochastic and generated independently of each other and of 0.
?This not unique to regularization. Pseudo-inverse, cause an analogous problem of distortion caused by unseen actions. RR-bounded rewards are automatically R-subgaussian. We can easily extend results more general subgaussian rewards, but stick to bounded rewards for simplicity of proofs.
This is satisfied when the offline data comes from random-
4

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Theorem (Computing and Bounding Aoa). Let M N E|Mi]le
Algorithm 2 Latent Offline subspace Constraints for Accel-
I]ll 222 S AM and I allll S AD for i 1, 2
erating Linear UCB (LOCAL-UCB)
with probability 1 6/3 each. Then, with probability 1 6,
1: Input: Projection matrix ÚÚT, confidence bound Aoff from an offline uncertaint--awar method, e.g. SOLD.
J00 - U.U__ 112 S Aott where for BD = ||N 2| and
= =dx (MN) - (Mxn)
2: Initialize V1 + Iد b1 < 0, at
3: for 1 I.... T do
4: Play action or and receive reward r, according to:
Doff= 2/2dk
(2 - BDDD)
(12 AMMDD
X
(1 B2
01 Br, U, + arg max o( a) B such that
BD
)
2
B1. U(U" V.U) U Dr,
1 I-BDAD
AM/
||U (8 - -100Bllll a1,
B2 + V, || - 32,1)ll v/ 022t
Obtaining AM and AD from Propositions 0 x N 1/2 N-1/2 / /dkda log(da/0)).
and 2 Aoft
||3] S R, U = -lik UU 3 = B.
1 y 211
Estimating dx offline. As our estimator N.I My D N2 is approximately rank-dx, the number of nonzero eigenvalues of the estimator is principled heuristic for determining dx.
5: Compute bi+1 t- b + M(x,, V + V o[T, () a) .441 6: end for
Insufficiency of PCA and PMF for subspace estimation. Naively performing PCA on the raw rewards or on single reward estimates 3n can lead to erroneous subspaces - as while the PCA target is aleebbralebba similar to MN. is statistically different. The PCA target (e.g. E[ is typically full rank due the variance of the per-reward noise c. On the other hand, PMF (Mnih and Salakhutdinov 2007a) offers neither confidence bounds on the estimated subspace, nor principled method for determining dx.
We formalize this intuition in Algorithm 2 by formulating the sharpened optimism as an optimization problem in step 4. The first two constraints represent the low dimensional confidence ellipsoids in the subspace spanned by given U, while the next two merely represent the usual high dimen- sional ellipsoid. The remaining constraints let U range over our subspace confidence set.
4. Offline Data Sharpens Online Optimism
We provide the following guarantee for LOCAL-UCB. No- tice that our guarantee shows that for enough offline data with N > T, the effective dimension of the problem is dx. It increases to d as T gets closer to N. The quality of the offlin data is reflected in the coverage constants Xg and AA-
Here, we motivate and describe LOCAL-UCB, a natural algorithm that accelerates LinUCB with offline data. The core idea is sharpening optimism by being optimistic over the intersection of two confidence sets one obtained using offline and online data and another purely from online data.
We geometrically motivate our update rule here, and illus- trate it in Figure I After any steps, we can construct a dx dx-dimmnsional confidence ellipsoid for every subspace in the subspace confidence set obtained from SOLD. The union of all these ellipsoids gives us our "offline confidence set [ called C. (B). The usual diddeennsol ellipsoid forms our "online confidence set." We call this Ct (G).. Since the true parameter lies in both confidence sets with high proba- bility, being optimistic over their intersection allows us to sharpen or "further localize" optimism. Even though the of- fline confidence set uses both offline and online data, will never shrink to a point due to the frozen subspace confidence set. So, we need the intersection of both sets to be sharply optimistic. This is the intuition behind LOCAL-UCB.
Theorem 2 (LOCAL-UCB Regret). Under Assumptions 7 and 2 if a1, RVT + CR dx 1og(2T/6) and 0q2, RVT CR (2g for a universul constant C, then with probability at least - 8 over offtine data and online rewards, LOCAL-UCB has regret Regr bounded by
o min [ROATT. RdxVT (1+
daT tork dxN
1
However, the subspace constraint U0| vdk - - is nonconver. In fact, we lower bound a convex function in the constraint, making us search for U, over a complicated shar-shaped set. So, it is unclear if LOCAL-UCB can be made computationally efficient.
"The set is not only dependent on offline data, since online data used to construct the dg dimensiioaal ellipsoids.
5

---

Leveraging Offline Data in Linear Latent Contextual Bandits
5. Lower Bound
sPogt
We now establish that LOCAL-UCB is in fact minimax optimal up to the coverage constants Xa, Ag defined in As- sumption 2 While we provide a full statement and proof of our lower bound in Appendix F we provide informal version here. Much like how we generate families of reward parameters in lower bound proofs for purely online regret, we are now generating a family of tuples of latent bandits (for the offlin data) and reward parameters represented in the latent bandit (for the online interaction).
Ploeen
107
Figure 1: Left: Geometric interpretations of LOCAL-UCB. Showing Con ( C (3) in green for three timepoints
t1, &g t3. The dotted lines delineate the subspace confidence set. Right: Geometric interpretation of ProBALL-UCB. Ca & Th (3), so we continue to use projections; but by time 12, Cha (3) C Cair (G), we stop using projections.
There exists a family of tuples (F, where F is latent bandit with a rank dx latent subspace and B is reward parameter in its support, so that for any offline behavior policy Th and any learner, (i) do is uniformly boundedfrow from below for all F, (ii) there exists a (F, (3 such that the regret Reg(T,, () of the learner under offline data from T and F and online reward parameter B3r is bounded below by
Theorem 3.
rithm maintains a low-dimensional confidence set, high- dimensional confidence set, and swaps between them to achieve acceleration. Once the cumulative error of using the low-dimensional confidence set ( A in ProBAL.-- UCB) exceeds the cumulative error of using the high- dimensional confidence set (= d dTV we stop using the former. This instantiated with LinUCB, but the same idea can be immediately applied to other algorithms like SupLin- UCB or Bayesian algorithms like Thompson sampling.
2 (min min (x (1+
dAT (1+ Nx
dAVT,dRVT
To the best of our knowledge, this is the first lower bound in hybrid (offlin-oonliee) sequential decision-making set- The key challenge is in selecting instance space
ting[" Fl that yields an informative lower bound. When the offline data has insufficient coverage, one can show a trivial d TT lower bound. Assuming A is uniformly bounded from below for all F models scenarios with sufficient offline coverage, and our lower bound shows that even in these non-trivial settings, no algorithm can achieve a regret better than min dA V (1 daT' N
We geometrically motivate our update rule here as relax- ation of LOCAL-UCB, and illustrate it in Figure [ like in Section 4 over LOCAL-UCB, which suprisingly only leads to a minor degradation in provable guarantees.
We go through three stages of simplification
Cruder offline confidence sets are used, We take the sub- space estimated by SOLD, compute a point estimate for B. within the subspace, and construct a ball that contains the LOCAL-UCB offline confidence set. The online con-
While
alyze worst-case performance over a meaningful class of
instances where the offline data is of sufficiently high quality, there remains room for future work on sharper, instance-
fidence set is still the standard d -immenssioa ellipsoid.
We wait for the offline confidence ball to contain the online confidence set, instead of taking intersections.
dependent lower bounds that reflect explicit dependence on both >o and AA-
We use computable proxy for this subset condition in- stead of explicitly checking it.
6. Practical Optimism with ProBALL-UCB
As a final note before presenting the regret bound proper, there is a technical challenge with analyzing ProBALL- UCB. Since B) lies in U but G, might not, the dx- dimensional confidence ellipsoid bound no longer applies. We therefore prove our own confidence ellipsoid bound in Lemma 6, to bypass this issue.
While LOCAL-UCB is minimax-ouu minimax-optimal, it is not computa- tionally efficient due to the non-convex constraint discussed in Section 4 We address this by introducing ProBALL-UCB (Algorithm 3. a practical and computationally efficient al- gorithm. In this section, we first sketch the algorithm and then describe how it can be geometrically motivated as relaxation of LOCAL-UCB.
Theorem 4 (Regret for ProBALL-UCB). Let 01, RVT + r' d'RAORK + CR/dd (T)( and let 022 R da log(T Let S be the first timestep when Algorithm dooes not play Line 6 and let S = T if no such timestep exists. For T = = we have that
ProBALL-UCB works in the subspace estimated by SOLD until the online confidence set is small enough. The algo-
Pal et al. 2023) give lower bounds on the cumulative regret for structure type of latent bandits (with hidden clusters). Their setting is purely online, although they rely on offline matrix completion oracle during online learning.
Regr = Ō (min (Regm,T: Regnye.))
6

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Algorithm 3 Projection and Bonuses for Accelerating La- tent bandit Linear UCB (ProBALL-UCB)
real-life data. While specific details of the experiments and many ablation studies are in Appendix Hi we sketch our experiments and discuss key observations in this section.
1: Input: Projection matrix ÜÜ confidence bound Aotf. Hyperparameters a1,t: 0r2,1, T.
In all experiments, we obtain confidence bounds A.ff using three different concentration inequalities (1) Hoeffddigg as in Proposition 2 (HH-ProBLL), (2) empirical Bernstein as in Proposition T (E-ProBALLL), and (3) the martingale Bernstein concentration inequalities of (Waudby-Smith and Ramdas 2023 (M-ProBALL). We use simpler expres- sion for Aod. set r' 0, and choose a suitable value of the hyperparameter 7 to adjust for overly conservative A We later vary T in ablation experiments to demon- strate that our results are not a consequence of our choice of hyperparameters.. Finally, for the MovieLens experiments, we additionally design natural Thompson sampling ver- sion of ProBALL-UCB to highlight the applicability of the ProBALL idea called ProBALL-TS in Appendix G All experiments for ProBALL-TS are in Appendix H.3.2
2: Initialize V1= + T, bj + 0, 0
3: for t = I.... do
4: if WOATTV DORT' dx 1 S dA then
5: Compute 31,1 + U(U V-,)) U b
6: Play at
arg maxa ((12, a) J0 BI,
(1,el)((z()))) a) v)
7: else
8: Compute
B2, + V. b, arg max, o(2,, a)T B2,
9: Play at +
02 (1 a)llv?'
10:
end if
11:
Observe reward rt and update bet1 a)r,, V441 f V1 o(x,, a))(z,)))
b
12:
Update C++1 C. + Ü ( aT)
Simulation study. We first perform a simulation study on a latent linear bandit with d = 50 and dx = 2, with 5000 trajectories generated offline. Further details are provided in Appendix H and the results are presented in Figure 2 Note that ProBALL-UCB (Algorithm 3 performs no worse than LinUCB, no matter what we choose for T and Dott. However,
K + [[C
13: end for
where Reg
RdA T and Regbyb, is defined as
clear benefit from using tighter confi- dence bounds- - as Aoff gets smaller, Algorithm 3 chooses to utilize the projected estimate B1,; more often, resulting in better performance. Note that the kinks in the regret curves correspond to points where Algorithm 3 switches over to the higher dimensional optimism in step 7.
dAT dxN
dA SN
Rd vT
1+
1920
V
+
x
In the worst case, K₂z O() and so 1/2 Ee
nēt E
)
but if all features 6(x;, az) lie in the span of U fort S S,
then? 3/2 Σi= n²- O(T).
MovieLens dataset. In line with (Hong et al. 2020), we assess the performance of our algorithms real data using the MovieLens dataset. Like them, we filter the dataset to include only movies rated by at least 200 users and vice versa, and apply probabilistic matrix factorization (PMF) to the rating matrix to generate ground truth user preferences for online experiments. Applying PMF gives dx = 18 and we choose da = 200, generating 5000 trajectories offline. For baselines, we reproduce the methods of (Hong) et al. 2020 2022) and implement LinUCB with canonical hyperparameter choices.
While the regret bound looks weaker in the worst case, we emphasize that the "good case" in Theorem i is quite common. As an illustrative example, if the feature set F, = (ő(12, a) a E A}} is an & ball, then the maximization problem in Step 6 will always choose a; with o(T,, az) in the span of Ù. This can also approximately hold if the features are roughly isotropic or close to the span of Ù. We direct the reader to Appendix forr further discussion.
Furthermore, Theorem 4 shows that ProBALL-UCB per- forms no worse than LinUCB, and can significantly outper- form it both in theory and in practice, as we will see in the following section.
We initialize ProBALL-UCB with a subspace estimated with an unregularized variant of SOLD (see Appendix G that uses pseudo-inverse instead of inverses. This is due to dif- ficulties in finding an appropriate regularization parameter for this large, noisy, and high- tigh-diimnsionall dataset. Figure 2 depicts the result of this experiment. Once again, ProBALL- UCB performs worse than LinUCB, no matter what we choose for 7 and Aon. and the benefit of using tighter con-
7. Experiments
We now establish the practical efficacy of SOLD (Algorithm I and ProBALL-UCB (Algorithm/3 3) for linear latent con- texttal bandits through series of numerical experiments 5 We perform simulation study and a demonstration using
Namely, we set Ap 0 in Aoft Also, Lemma and some thought reveal that choosing 7' recovers the "good" version of ProBALL-UCB guarantees, if features are isotropic enough.
"See https//gghhua..ommcccnnerrpppppp for source code.
7

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Simulation Study
MovieLens (UCB)
MovieLens (TS)
Regret vs Offline Samples
H-FREBALL-UCC
350
M-PRBAALL-CC
H+PrOBAL-UCS
120
EPHOSALL-JC
300
E-FrRALL--ACR
100
Liucc
300
TS
Regret
80
200
mmmic
mucn
Regret
MINTS
merT5
Regret
90-
200
80
50
150
40
70-
+-FIBALLLUCE
EhhSALL-KX8
20
50-
60
0-
0-
0-
Rro of F.th S.topase
50
150
50
150
50
100
150
200
10'
10"
10
Timesteps
Timesteps
Timesteps
Offline Samples
Figure 2: Left Right. First: Simulation study comparison of ProBALL-UCB against LinUCB for = 5. Second/Third: Comparison of ProBALL-UCB initialized with SOLD against (LinUCB, mUCB, and mmUCB, TS, mmTS, and MixTS), for r = 0.1 and various confidence bound constructions. ProBALL-UCB outperforms all other algorithms, and approaches the performance of LinUCB when Hoeffding confidence sets are used. Fourth: ProBALL-UCC regret on Movielenss against offline samples used in SOLD, compared to LinUCB on ground-truth low-dimensional features. Here, T = 0.1, = 200. As the number of offline samples increases, SOLD recovers a low-rank subspace almost as good as ground-trum -tuund The shaded area in each sub-figure depicts 1-s.e. confidence intervals over 30 trials with fresh 0, accounting for the variation in frequentist regret for changing 0.
fidence bounds remains. With 5 0.5, ProBALL-UCB with martingale Bernstein confidence bands stops using the projected estimates at around timestep 70, but still continues to outperform LinUCB. Although mUCB and mmUCB per- form slightly better than ProBALL-UCB and LinUCB at the beginning. the model misspecificatiin incurred by discretiz- ing the features into dx clusters ensures that it typically suffers linear regret in this scenario. The lower initial perfor- mance of ProBALL-UCB and Lin-UCB is consequence of their higher initial exploration.
theorem for decision processes. demonstrating that every "coherent" and "exchangeable" stateless (contextual) deci- sion process is a latent (contextual) bandit. We first define a stateless decision process at a high level of generality 8
Definition 2. A stateless decision process (SDP) with ac- tion set A is probability space (92, G, P) with a family of random maps FH S + (A + R for H E EENUURE {oo}.
That is, given a sequence of actions (01,...a:). an SDP generates a random sequence of rewards (Y,,... Yn). As such, we abuse notation to denote by FH (a1...... aH) the random variable w + Fi (W aH). Without any coherence between FH across H, stateless process can behave arbitrarily for different horizons H. We present a natural coherence condition below, essentially requiring that given action sequence should produce consistent rewards.
Ablation study. While the end-to-end performance of ProBALL-UCB significantly improves over existing algo- rithms, we also address further questions about various com- ponents of our method in Appendix H We first show that the rank dx can be determined from offline data via the procedure outlined in Section 3 of using the eigenvalues of N My M D,N.y N.2 to determine the rank of our subspace. Second, we study the effect of varying the hyperparame- ter and note that our method stably outperforms existing methods at all reasonable values of r. Third, we compare different combinations of algorithms in our figures above, side by side. Finally, we evaluate the effect of offline data by plotting the online regret against the number of offline samples used to estimate the latent subspace.
Definition 3. A stateless decision process is coherent if for any < k < H' E NU {xc} and for any two action sequences T, of lengths H and H' sharing the same actions (any...ap) from index h to k with Fu (T) = (Yi.... Yh) and (T' = (Yi,... ... Yir),, we have (Y (Yn,... Yv) = -Y, (Y),,..)), viewed functions of Ω.
It is natural to require equality in value and not just in distribution, since after taking an extra action, the values of past rewards stay the same, not just their distribution. For example, if we pull 10 different jackpot levers and then pull new one, the previous 10 outcomes stay the same in value, not just in distribution. We also give a natural definition for exchangeability of stateless decision process namely that
8. How General Are Latent Bandits?
While have established that latent bandits are powerful framework for accounting for uncertainty in reward models, the extent of their generality is unclear. Are there other state- less decision processes that generalize over latent bandits? We cap off our contributions by establishing the general- ity of latent bandits. In this section, we show a de Finetti
LLu et al. 2023 work with much more restrictive notion of a generalized bandit and use the original de Finetti theorem in some of their lemmas. See Appendix [B. for a discussion.
8

---

Leveraging Offline Data in Linear Latent Contextual Bandits
exchanging any two rewards should lead the distribution obtained by exchanging the corresponding actions.
A linear latent contextual bandit is latent contextual ban- dit where the random measure-valued function F : 52 + ((X x A) + P(R)) is defined by setting F F(w)(z, a) to be the distribution given by Φ(I, a) [U,((w)))))))))) + e, for any w E Ω and (x, a) E (X' x A). We have seen that every coherent and exchangeable stateless contextual decision process is latent contextual bandits, of which the linear latent contextual bandit is an important special case.
Definition 4. A stateless decision process is ex- changeable if for any permutation [H] and Fn(ai.....a. .u) Xx()). ((()))..Y((())....
[ +
(YI.... YH), we have
(((((())....0())))>>>) (Y=()).... (Y=())))~>()).-..>...>>>>>>>>>))
Finally, latent bandit is SDP that behaves like bandit conditioned on random latent state F that determines the reward distribution. As F' determines a distribution, it is random measure-valued function on AA
9. Discussion, Limitations and Further Work In this paper, we have addressed the problem of leverag- ing offline data to accelerate online learning in linear la- tent bandits. Our work has a few limitations. First, while ProBALL-UCB is practical and computationally efficient, it has a slightly weaker worse-case guarantee than LOCAL- UCB. Second, when the data is noisy, it can be hard to tune the regularization J.. We use a pseudoinverse-basee version of SOLD in such a case (Appendix G) implemented in our code. This variant is easy to tune and performs well empir- ically. Third, the offline uncertainty sets computed using Aof can be overly conservative, and discount hyperpa- rameter T for deciding when to switch between using the offline confidence ball and the online confidence set within ProBALL-UCB must be fine-tuned online.
Definition 5. A latent bandit is a stateless decision pro- cess equipped with a random measure-value function F: Q + (A + ((R) so that for any H and action sequence (01,...az)) the rewards (Yi.... YH²) are independent conditioned on F. Moreover, the condi- tional distribution L|Y, F] = F(a)) for all h < H
==
as))
As such, the latent bandit is indeed a special case of an SDP, where the function Fx is induced by the latent state random variable F.
While exchangeability and coherence are reasonable condi- tions an SDP and are clearly satisfied by latent bandits, it is a-priori unclear if they are sufficient to ensure that the SDP is latent bandit. As only exchanging rewards from the same action preserves the distribution, standard de Finetti proof ideas do not immediately apply. After all, is possible that an SDP could be cleverly designed to choose rewards adaptively across time and satisfy these properties. Reas- suringly, no such counterexamples exist, guaranteed by the following theorem.
Despite these limitations, our work enjoys strong theoretical guarantees and convincing empirical performance. We hope that this method opens the door for developing other efficient and scalable algorithms for sequential decision-making with continuous latent states. One can use ideas presented in this paper to design similar algorithms for MDPs, linear MDPs, and RL or bandits with general function approximation.
Theorem 5 (De Finetti Theorem for Stateless Decision Pro- cesses). Every exchangeable and coherent stateless decision process is a latent bandit.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We show in Lemma 2 in Appendix A that coherence is not consequence of exchangeabiliity it is necessary condition for being a latent bandit. Finally, we analogously consider contexts and define "transition-annosiic contextual decision processes" (TACDPs) in Appendix B.2 We define coherence and coherence and exchangeability for TACDPs, and define latent contextual bandits by simply replacing A with X' x A in the definitions above. We then show analogous de Finetti theorem, corollary of our proof of Theorem 5 See Appendix 6.6 for more details.
A Acknowledgements
CK would like acknowledge the support of the Rackham International Student Fellowship (the Indian Alumni Fel- lowship) for this work. KT is supported in part by the NSF grant CCF-2106778.
References
Linear latent contextual bandits and SDPs. Finally, note that this section is faithful to the rest of this paper.
Abbasi-Yaude Yadkori, Y., Pál, D., and Szepesvári, C. (2011), Improved algorithms for linear stochastic bandits. In Ad- vances in Neural Information Processing Systems, pages 2312-2320.
We abuse notation twice here. First, we write F(ax): := (w + F (ax)). Second, as the regular conditional distribution C|Y% F] is kernel that maps from Q x B - R, we view F(as) as curried map (w,, B) (ww))w))(B) A discussion of issues (measurability and well-definedness) is Appendix B.2
Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M., and

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Telgarsky, M. (2014). Tensor decompositions for learning latent variable models.
Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010). A contextual-bandit approach personalized news article recommendation. In Proceedings of the 19th interna- tional conference on World wide web, WWW '10. ACM.
Brochu, E., Hoffman, M. W., and de Freitas, N. (2011). Portfolio allocation for bayesian optimization.
Liu, Y., Kuang, X., and Roy, B. V. (2023). definition of non-stationary bandits.
Cai, C., Cai, T. T., and Li, H. (2024). Transfer learning for contextual multi-armes bandits.
Lu, R., Huang, G., and Du, S. S. (2021a). On the power of multitask representation learning in linear mdp.
Cella, I.., Lounici, K., and Pontil, M. (2022). Meta repre- sentation learning with contextual linear bandits.
Lu, Y., Xu, Z., and Tewari, A. (2021b). Bandit algorithms for precision medicine.
Chen, Y. and Poor, H. V. (2022). Learning mixtures of linear dynamical systems. CoRR, abs/2201.112111.
Duan, Y. and Wang, M. (2020). Minimax-optimal off-policy evaluation with linear function approximation.
Mnih, A. and Salakhutdinov, R. R. (2007a). Probabilistic matrix factorization. In Platt, J., Koller, D., Singer. Y., and Roweis, S., editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc.
Harper, F. M. and Konstan, J. A. (2015). The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4).
Mnih, A. and Salakhutdinov, R. R. (2007b). Probabilistic matrix factorization. In Platt, J., Koller, D., Singer. Y., and Roweis, S., editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc.
Hong. J., Kveton, B., Zaheer, M., Chow, Y., Ahmed, A., and Boutilier, C. (2020). Latent bandits revisited.
Hong, J., Kveton, B., Zaheer, M., Ghavamzadeh, M., and Boutilier, C. (2022). Thompson sampling with mixture
Pal, S., Sai Suggala, A., Shanmugam, K., and Jain, P. (2023). Optimal algorithms for latent bandits with cluster struc- ture. In Ruiz, F., Dy, J., and van de Meent, J.-W., editors, Proceedings of The 26th International Conference Ar- tificial Intelligence and Statistics, volume 206 of Proceed- ings of Machine Learning Research, pages 7540-7577. PMLR.
prior.
Jiang N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2016). Contextual decision processes with low bellman rank are pac-learnable.
Jin, Y., Yang, Z., and Wang, Z. (2021). Is pessimism prov- ably efficient for offline rI? In International Conference on Machine Learning, pages 5084-5096 PMLR.
Press, W. H. (2009). Bandit solutions provide unified eth- ical models for randomized clinical trials and compara- tive effectiveness research. Proceedings of the National Academy of Sciences, 106(52):22387-22399
Kar, S., Poor, H. V., and Cui, S. (201 Bandit problems in networks: Asymptotically efficient distributed allocation rules. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, pages 1771 1778.
Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishna- murthy, A., and Sun, W. (2023). Hybrid rl: Using both offline and online data can make rl efficient.
Kausik, C.. Tan, K., and Tewari, A. (2023). Learning mix- tures of Markov chains and MDPs. In Krause, A., Brun- skill, E.,, Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J., editors, Proceedings of the 40th International Con- ference on Machine Learning, volume 202 of Proceed- ings of Machine Learning Research, pages 15970-16017. PMLR.
Tan, K., Fan, W., and Wei, Y. (2024). Hybrid reinforcement learning breaks sample size barriers in linear mdps. In Advances in Neural Information Processing Systems.
Tripuraneni, N., Jin, C., and Jordan, M. I. (2022). Provable meta-learning of linear representations.
Vempala. S. and Wang, G. (2004). A spectral algorithm for learning mixture models. J. Comput. Syst. Sci, 68:2004.
Klenke, A. (2008). Probability theory: A comprehensive course. In Universitexi, Springer Cham.
Wagenmaker, A. and Pacchiano, A. (2023). Leveraging offline data in online reinforcement learning.
Kong, W., Somani, R., Song, Z., Kakade, M., and Oh, S. (2020). Meta-learning for mixed linear regression. CoRR, abs/2002.08936.
Waudby-Smite I. and Ramdas, A. (2023). Estimating means of bounded random variables by betting. Jour- nal of the Royal Statistical Sociery Series B: Statistical Methodology, 86(1):1-27.
Lattimore, T. and Szepesvári, C. (2018). Bandit algorithms. preprint.
10

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Wei, Y., Cao, Y., and Xiang. H. (2005). A note the componentwise perturbation bounds of matrix inverse and linear systems. Applied Mathematics and Computation, 169():1221-1236.
Yang, J., Lei, Q.. Lee, J. D., and Du, S. S. (2022). Nearly minimax algorithms for linear bandits with shared repre- sentation.
Yu, Y., Wang, T., and Samworth, J. (2014). A useful variant of the davis-kahan theorem for statisticians.
Zhou, D., Zhang, Y., Sonabend-W, W, A., Wang, Z., Lu, J., and
Cai, T. (2024). Federated offline reinforcement learning.

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Contents
Introduction
2
Linear Bandits With Latent Structure)
Estimating Latent Subspaces Offline
Offline Data Sharpens Online Optimism
5
Lower Bound
Practical Optimism with ProBALI-UCB
6
Experiments
8
How General Are Latent Bandits?
8
Discussion, Limitations and Further Work
Additional Lemmas and Discussion
14
A.1
Broader Impacts
14
A.2
Coherence with Equality is Necessary
14
A.3
Contexts, Latent State and Behavior Policy cannot be Dependent
14
A.3.1
Contexts cannot be dependent on each other
14
A.3.2
Contexts and latent state cannot be dependent
15
A.3.3
Latent state and behavior policy cannot be dependent
15
B
A de Finetti Theorem for decision processes
16
B.1
Discussion on (Liu et al. 22023)'s smaller class of generalized bandits
16
B.2
Proof of the De Finetti Theorem for Stateless Decision Processes
16
B.3
Constructing F
16
B.4
Establishing that C(Y,,, F F (aa) almost surely for all h
17
B.5
Establishing conditional independence of rewards
18
B.6
A de Finetti theorem for TACDPS
19
C
Proofs for SOLD
20
Proots for LOCAL-UCB
24
Proofs for ProBALL-UCB
26
E.1
Confidence bound for the cow-dimnnsional reward parameter
26
E.2
Proof of the theorem
28
E.2.1
Understanding fgg
30
Lower Bounds
31
F.1
Setup
31
F22
Proof Sketch and Intuition
................................
31
F3
Regret Lower Bound Decomposition
32
................................
F.4
Bounding Eg (1) + Eg U.( when dx
32
F.5
Bounding Eg (1) + E. U.( when > dx
33
F6
Lower bounding regret using averaging trick
34
F7
The Other Two Regimes
35
Additional Algorithms
36
12

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Experimental Details and Additional Experiments
37
H.1
Determining the Latent Rank from Offline Data
37
H.2
Simulation Study
38
................................
MovieLens
39
H.3.1
UCB Algorithms
40
H.3.2
TS Algorithms
H.3.3
Comparison Against Low- Dimenniona Ground Truth Subspaces
42
H.3.4
No Usage of SOLD
43
H.4
Sample Complexity of SOLD
44
13

---

Leveraging Offline Data in Linear Latent Contextual Bandits
A. Additional Lemmas and Discussion
A.1. Broader Impacts
Often, protected groups with private identities have temporal behavior correlated with their private identities. Latent state estimation methods have the potential to identify such private identities online, and must be used with care. Use of such methods should comply with the relevant privacy and data protection acts, and corporations with access a large customer base well as governments should be mindful of the impact of the use of latent state methods on their customers and citizens respectively.
A.2. Coherence with Equality is Necessary
Lemma 2 (Coherence with Equality is Necessary). There exists a stateless decision process that is exchungeuble and not coherent but satisfies the following property: for any two action sequences T, T' of lengths H and H' sharing the same actions (an....ox, .x) from index h to k with FH( = (Y,.... .u) and (T'(T')= (Yi,... ......Yyr. YH we have (Ynz...Yo Y2)= ~
(Y,... Yf). Additionally, since the SDP not coherent, it is not a latent bandit.
Proof. Consider an SDP with action set A = {0, 1} equipped with a random variable 0 E (0, 13 distributed as (er(1/2). If the first action is O, then all rewards are given by 0. If the first action is 1, then the first reward X1 = 0 while all future rewards are 1 0.
Notice now that for any timestep h, its rewards are Ber(1/2). We note that this process is clearly exchangeable. Moreover, this process is coherent in a weaker sense - for any two action sequences T, of lengths H and H' sharing the same actions (0h,...ap) from index
k. with (T) = (Yi,... Yu) and (r) (Yí,.. Yir.), ....... ..). That is, the reward subsequences are only equal in distribution. This is easy see, since if a1 is not included in the action subsequence or if a O, the reward subsequence is always given by (X,.. X)) for X ~ Ber(1/2). If aa = 1 and a1 is in the action subsequence, then the reward subsequence is always given by (-X. X) for X ~ Ber(1/2).
we have (Yn,... Ys)
However, the reward subsequences not equal in value. If the action subsequence is inside two action sequences (a1,... ah) and 7' (a'.... d'n)) with a1 0 and a 1. then their rewards negatives of each other. So, this SDP is not coherent. This means that this SDP is not a latent bandit.
A.3. Contexts, Latent State and Behavior Policy cannot be Dependent
Lemma (Contexts, 0, and na cannot be dependent). For each of these conditions:
1. Contexts in trajectory are dependent but do not depend on 0, and Try also does not use 0,
2. Contexts are generated independently using O, while Th does not use O
3. Contexts generated independently without using O, while Thb uses O.
there exist two different linear latent contextual bandits with orthogonal latent subspaces satisfying the condition, and a behavior policy Ti, so that the offline data distributions are indistinguishable and cover all (x, a) pairs with probability at least 1/4. Since the latent subspaces are orthogonal, an action that gives the maximum reward one latent bandit gives reward 0 on the other.
Proof. Let e1, 62 be the standard basis of R2. For all these examples, our two latent bandits will satisfy the following:
Latent contextual bandit 1: Let take values é1 + 62 and -e - E2 with probability 1/2 each.
LLatent contextual bandit 2: Let take values 61 - 62 and 62 - e1 with probability 1/2 each.
1.3.1. CONTEXTS CANNOT BE DEPENDENT ON EACH OTHER
We consider two actions, so A {0, }} We have two contexts x. y so that 0)x = el, 6lx, 1) 2e, while Φ(v, 0) = e2. o(y, 1)= = 2e2. We design them to be dependent so that any trajectory either only sees x or only sees However, x and y are both seen with probability 1/2. Pick n, so that it takes each action with probability 1/2. Now note that the mean reward of r, 0 in either latent bandit takes values 11 with probability 1/2. So, the offline data distributions are also indistinguishable and every context-action action pair is seen with probability at least 1/4.
14

---

Leveraging Offline Data in Linear Latent Contextual Bandits
A.3.2. CONTEXTS AND LATENT STATE CANNOT BE DEPENDENT
We consider two actions, so A {0, Again, consider two contexts x, y so that ((x, 0) c1, 6(x; 1) 2e1 while p5, 0) 22, ( 1) 2e2. Let say that for either latent bandit and for any O, the context distribution is Dirac-ò over the context whose features have positive dot product with 0. Then, note that either context is seen in both latent bandits with probability 1/2. Again, let т take either action with probability 1 1/2. So, the offline data distributions are indistinguishable and every context-action pair is seen with probability at least 1/4.
A.3.3. LATENT STATE AND BEHAVIOR POLICY CANNOT BE DEPENDENT
We consider four actions, so that A = {0, 1, 2, 3). Let there be single context x with ((x, 0) = e1, O(xx ()x = c2, ( 2) = -61; (xx, 3) -22- For any latent state in either bandit, let n uniform over actions that have positive dot product with 0. It is then easy to see that the offline data distributions are indistinguishable and every context-action pair seen with probability least 1/4.
15

---

Leveraging Offline Data in Linear Latent Contextual Bandits
B. A de Finetti Theorem for decision processes
B.1. Discussion on (Liu et al.. 2023y's is smaller class of generalized bandits
We prove the de Finetti theorem for a very general formulation of decision processes. However, past work (Liu et al. 2023 has studied a simpler generalization of bandits, namely a stochastic process valued in I--,, A sample point in this space is a sequence of functions in A R, which rules out the possibiliity of adaptivity. In contrast, sample point in our space is a function of sequences, which subsumes all sample points of their space, but allows for adaptivity.
Liu et al. 2023) are able to use the original de Finetti theorem on their random process directly, but work with a much more restrictive kind of decision process. We show that even when considering much more general stateless decision processes, latent bandits are the "right" objects produced by a de Finetti theorem for stateless decision processes.
B.2. Proof of the De Finetti Theorem for Stateless Decision Processes
note on F, measurability and well-definedness in the definition of a latent bandit. Recall that F in the definition of latent bandit needs to be measurable map 52 + (A - P(R)). To define measurability for the output space functions (A + P()),, we endow P(R) with the topology of weak convergence, endow the space P(R) of maps A + P(R) with the topology of point-wise convergence, and require F to be measurable w.r.t. the induced Borel o-algebra. We also recall two abuses of notation in the definition of latent bandit. First, we abuse notation to define the random measure F(a)= : (w + F(w) (a)). Second, we also abuse notation to conflate F(a) with the curried map Ka (w, B) == (B), which is a map x B + [0, 1]. This map Ka will turn out to be a kernel by the construction of F. Equating F(a) to a regular conditional distribution the definition of latent bandit requires that Ka be kernel.
We recall our de Finetti theorem for stateless decision processes here.
Theorem (De Finetti Theorem for Stateless Decision Processes). Every exchangeable and coherent stateless decision process is a latent bandit.
Proof. Consider an exchangeable and coherent stateless decision process. We will establish that there is a latent bandit with the same reward distribution as this process for any sequence of actions.
For any sequence (a1,... aH), denote by (Y,,1,... Yr, Fa ax). We intend to establish that there is random measure-valued function F such that (V., Yz,H) are independent given F and L F] = F(as) ) for all
< H almost surely. Since conditional independence is a property of finite subsets of a set of random variables, it suffices to show this for finite H. The version for H oo will immediately follow by coherence.
First recall that regular conditional distributions L|Y space of Y is countably generated. Since the Borel o-algebra on IR is countably generated, this is true for our case. We also recall for the rusty reader that conditioning on a random variable is the same as conditioning the induced allgebrra in the domain.
F]
almost surely unique under if the o-algebra of the output
B.3. Constructing F
Fix any finite trajectory 7 = (01,...ay) and index h.
The trick:
Consider the infinite sequence Tox = (an, (hy By coherence, Yr,6 Yr...-- Now Too is sequence where exchanging any finite set of rewards preserves the reward distribution, since all actions are identical. Since IR is locally compact, we can apply the usual de Finetti representation theorem (Theorem 12.26 in (Klenke 2008)) to conclude that:
The random measure Eaa_ = wlim,,roc n EE=1 oY is well defined. Here wlim the weak limit of measures.
The regular conditional distribution LY Ban = Ea, for all
Since Yr,h- .he we conclude that the conditional distribution C|YT,h E.,.] C[Y [.,.] Eag
Constructing F: For every action, consider such a random measure E.g and define random measure-valus valued function F:Ω- - (A- + P(R) in the following manner: for any w E Ω define Fa))(() == E.,. (w). We know that for any a, E.,. is measurable w.r.t the topology weak convergence on P(R). It now tedious but straightforward to verify that F is measurable w.r.t. the Borel r-algebra generated by the topology of pointwise convergence on P(R)4.
16

---

Leveraging Offline Data in Linear Latent Contextual Bandits
B.4. Establishing that ,| F] F(an) almost surely for all h. Again, fix any finite trajectory random-measure w + (a). In particular, for any measurable set B R, we conflate P(a)(w)) (a)) (w)) B), where the last equality holds since F is regular conditional distribution. Note that F(On) Eas by the construction of F. Since Ea.- = F(an), we have f|Y F(as)] = F(as). Thus, it suffices to show that L F) , F.
(d)....0r) and index h. Recall that we abuse notation to denote by F(a) the
Lemma 3. 4 F| , F(an)) almost surety.
Proof. First note that F(a,) is measurable w.r.t F. For showing this, view the of maps P(R) the product set Il P(R)at. Now merely note that F-1(E P(R) (F(an)) (E) for any measurable subset E c P(R).. Hence, F(aa)) is measurable w.r.t. F.
Let B be the Borel o-algebra on R. Now recall that the regular conditional distribution C|X G] for real-valued random variable X is the almost surely unique kernel KG.X S x B + IR such that:
w + KG.X (w, B) is G-measurable for any set B B
B - KG,x (w, B) is probability measure on R for any sample point w E Q.
For any measurable set B C R and any G-measurable set A,
[\)(()) f ( = f
B)
We will show claim using the definition and a.s. uniqueness of the regular conditional distribution in our case. Consider any F-measurable set A C Ω and Borel-measurable set B C R, B E B. Denote by C[Yr. F] and by Kan == L(r,,) F(ax)] F(a). Note that by the coherence and exchangeability in section B.3
f |K>lu |KF(,, B)IA = L[1 = MAl= 1
for all j. Averaging all these equations and taking a limit, we get that
/ RR B)) = E[L,(Y,,) E[l=]=E[1p (Y
lim
E[1 Y
[Al
n 71
=E
lim Σ 1 (Y(raa))))
a
where the last equality holds by the dominated convergence theorem, if the limit exists. To establish that the limit exists and compute it, we apply the usual de Finetti theorem specificaly point (i) of remark 12.27 in (Klenke 2008) with f set to the identity map. This gives us that lim Σ/= 1 ().)) = [LL n)) Eaa1 1 = Ean (B), where Ea, (B) is the random variable +> Ea, (B). This in turn satisfies E.g, (B) = F(an) (w) Kan, (w. B). This establishes that for any f-measurable set A and Borel set B,
I [krlw,
= ff Kan (w, (WWW)))(())
In conclusion, Kaz, satisfies:
(Ba))(B) = w - Ha,, (w, B) is F-measurable for any set B E B since F(a is F(a;) measurable by definition of Kay, and F(nn) is F-measurable from above.
-> Kan (w: B) is probability measure on for any sample point ws E Ω by definition of Kan
17

---

Leveraging Offline Data in Linear Latent Contextual Bandits
For any measurable set B C IR and any F-measurable set A, by the argument above,
[[]a(Y+))Aa)= = f ( ( = -f Kas (w, B))A(W)(())))
By the definition well as a.s. uniqueness of regular conditional distributions in our case, this establishes that C[Y, F) RP Kian. = F(ax)) almost surely.
B.5. Establishing conditional independence of rewards
This is the trickier to establish. It suffices to show that for any finite length h trajectory = (a1....ap) and any tuple
(Ji,.. -U) of bounded measurable functions, [ (a((,,)) F = II ((,,( F]. Equivalently, it suffices show that for any bounded F-messurable real- valued random variable U, the following holds.
U IV h=1
(1 =E E II E[A(Y,,)) F]
We will show this by induction on H. This clearly holds for H = 1 by section B.3 above. Now assume that this holds for
H = 1.
.Q)))..a)). First consider the infinite trajectory (a1.... at-1, at, at, ......). This creates random sequence of rewards Y7 Yr.,...... Define TJ by switching indices / and [ + in r' and considering the first I actions. In particular, 7f gives the sequence of rewards SF.,,,...r,.11 Yr))
Replacing the last term, fi(),,), by an empirical average: Fix any trajectory
First note that To = т. By coherence, (Yr.1.... .Y,1) = (Yr..,.... Yr.)). By exchangeability and coherence, (Yrt,1,...Y Yr,1-1, (),)) ~ (Vr...... Y7,-1, (r))))) This means that for any j 2 0,
E U I (A
=E I (M(K))))) FICKMAAD)
h=1
1=
We can then consider the average over all these equations for j + n and get that for 2 1,
( A.C (
E U
E U II
/111
==
Taking limits and using the dominated convergence theorem, we get that
lim =E U II (A(Ckra))
Σ C ==U
E U U f.(()N)))
(I)
n2
h=1
the limit on the right side exists.
Showing that the empirical average the conditional expectation: Again, consider different infinite trajectory (a,, o.,...). Again, by coherence, Yr,++j Yy for all j 2 O. From the usual de Finetti theorem, specifically point (i) of remark 12.27 in (Klenke 2008), we have that ΣØ= fi(Yn.)) + E[f((Yna)) F]. We can then observe that by general properties of convergence, the tollowing holds.
m
1
E(f(( Fl lim Σ ((Yr))) = lim
Σ 1=1
f((
m- m
m- m -
1=1
m-1
n-1 f((+..45)
lim
Σ
lim
m-+00 m -
2 n j=0
j=l
18

---

Leveraging Offline Data in Linear Latent Contextual Bandits
We combine this with equation T to get that
1-1 II (A
E U II
=E
E(Si(Yn))) FJ
Since both U and (l,)( F] are now F measurable, we can apply the induction hypothesis to 7' truncated at I and conclude that
=F (UEMNY
1-1 F) II h=1
U (I
E U I
Iw h=1
(&,,,,))
V==
Thus, the induction step holds and the claim holds for all finite H. We discussed at the beginning of the section how this implies conditional independence for H = oc as well.
B.6. A de Finetti theorem for TACDPs
We consider contexts and define contextual decision processes in manner agnostic to context transitions. That is, the process only carries the data of how rewards are generated from given sequences of contexts and actions, while the context transitions themselves may be generated by a different process.
Definition transition-agnasie contextual decision process (TACDP) with action set A and context set X' is probability space (9, P) equipped with a family of random maps FH Ω - ((X A)" R") for H E I as well as a map F . - ((X' AA RN).
It is natural to isolate away context dynamics for processes like stochastic contextual bandits, in which actions do not affect the context transitions in contrast to transition-anes aware definitions in (Jiang et al. (016)).
Definition 7. A TACDP is said to be coherent for any h < h S H, H' E N foo} and for any two context-action sequences T' of lengths H and H' sharing same context-action pairs ((In, .............. (IT ax)) from index to k. with FH(7) (Yi.... Yн) and FHr (7') (Yi,... ...... we have (Y,.... Yk) (Y,,... Yf), viewed functions of Ω
Definition 8. A stateless decision process is said to be exchangeable if for any permutation Fn((E1,a1), ... (Ln,,a))
[H] [H] and
(Y,,.. Yn), we have Fr (FF(((())) (x(1)),.... (I))())) (x()))) (Ya(),....,,,
Definition 9. A latent contextual bandit is stateless decision process equipped with a random measure-valued function F : Ω + ((X' x A) + P(R)) so that for any and context-action sequence ((11, a1)... (# Q. )), the rewards (Yi.... YR) = F2((11, a1).... (æ aH)) are independent conditioned on Moreover, the conditional distribution 4[V, F) F((2h, ax)) for all <
Theorem (De Finetti Theorem for Stateless Decision Processes). Every exchangeable and coherent TACDP is latent contextual bandit.
Proof. The proof is verbatim the same as that for Theorem after merely replacing A with X' x A and a with (z, a).
1eWe abuse notation twice here. First, we write F([Z,, ax)) = (w + ([w)((z), ax))). Second, as the regular conditional distribution
C[Y, | F] is kernel that maps from f2 x B R, view F F( an)) its curried map (w, B) F((T,, (B).. A discussion
of issues like measurability and well-definedeess is Appendix [8.2
19

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Proofs for SOLD
Recall that 140 == [ and define μa == E[3] = U- Also recall that A == [[ For a trajectory with index n,
denote by Bn == O,O.. Denote by X, := 1 u1),... ((H utr)]" Denote by yn- := 1 en.2... ....,,. 6n,
T the vector of subgaussian noises with subgaussian parameter o². Since rewards are bounded by R. we know that 0² R². Denote by Xx,; and i the action matrix and noise vector corresponding the trajectory halves Tn, for i bounded by R. En is subgaussian for all h and so Thii is o² -ubbausssian for i = 1, 2. Also note that
Since rewards
Ba, = (μI +
"X nn
(ML + +X X (X + +mm.))
(1 pudd + X Xn, Xn 1n + (ul + Xn,)) -1 "Xp
(I culI + x ( (μl + Xn,) - -1x Mm,
Note that Bn,1 and Bn,2 are identically distributed. Now recall that
M, ; (3mm, + 3,,)
are i.i.d. random matrices. Denote by D,,i (I- pu(u X x x,,))=1)) and denote by u4 (uT X. N,, xn,)) -XX Iniaa Lemma 4. the per-reward noise is 0² ossuaaaussn,n then the following inequalities hold
H
M R2
2
2/1
a (d +
E 11 S R
8p42
Proof. We prove various bounds and assemble them.
Bounding [1(1 + X XT Xm.i) X 222 Consider any X with SVD X U ΣV. This means that
l1(t + xX 12 = V (E² -
= =1|V [ +1) || 1)) 1112
a
< max a² 1
2/F
We now apply this X Xn,i and conclude that [1(ul (n,,),,)-11000 <
Wy are independent, o² subgaussian and av H. -bounded: We claim that u, are independent, o² subgaussian and || < 4u
2/p
4p
HyH 2VB
Recall that Th,i are o²-subgaussian vectors and [[(dl +
S T So, we have that u;
(pl + Xxx mm is Ín -ubgauusssia. Also recall that un and u2 are independent since both contexts and reward- noise generated independently at each timestep. Finally, since (c,,al R, also have that || 11 S R H. so
o²
||u,112 < n² since [[ + XT, Xn.s) -x, S 2/7
Bounding ||M, Note that ||Dn,illa 1, 11,2112 R and |/i1122 <
AVH. 2/
So, have that
2
RVH
H
|M, <
R
RR
2
2/P
2μ
Bounding || ( 1 We compute that
E M = (EID, DM..I
D",3Aal + E(D,., D..2 E[
20

---

Leveraging Offline Data in Linear Latent Contextual Bandits
E((3, n,, 3,, ),. 1,, 22,2 [[ Da, D 2 ) Dn. un [1lE[ugg + u2 [ + Elu un uul + Elugui uzul))
Now since Da,illa E and |13,112 I R. the norm of the first four terms bounded by R². Now note that
[E] 1 Ille
max v.livlla31
E[v u.u.v]
max El(u v) S
v.livlesa
2p
o¹dA 2/
||| 12lll2 = Tr uu 1) S [T],u,]11224 S
[[2u u2u Ill2 = [| u1 un 1lle
max
Elv us U2 U U2 v]
v.livlaa11
0²
max Flv' unnn v] v|= v.ll
Tr(v' T E(uru] [E = ||F u |F [22u2 lll2 S
max v.l
4422
Combining all of these, we get that
(dd
EE S Rd
8y12
Proposition (Confidence Bound for My).
With probability least - 8/2, we have that MNN E[Mi]lla S Aas with
N
log( (8)(
H
3/1 [2log(Ad
A =
2
2
M
+ 2R
2
72
N
2/1
N
2
H
log(4da/0)
AR²
2
2p1
3N
Proof. Now since || <
M < Rd
2
11
we have that [MM E[M]]l2
S 2R (2 ) by the matrix
Tu
Hoeffding bound, we have that with probability
- 6/2.
N Σ
H
2
log(da/0)
M -
< 4R
2
N
2/r
N
n=1
Further, by the matrix Bernstein inequality, we have that with probability 1 - 1-0/2,
1 N
log (dg())/))
+ 4R² ( H
log(da/6)
Σ M,
E.M.]
<
22
2+ 2p,
N
N
3N
n=1
2
Combining the two results and using a union bound, we get that with probability 1 - 15/2
N M - [[M
My - E MM]l2
n=1
log log(2da/0)
H H) 2+
(2log(2da/0)
3/4
2
M
+ 2
N
2μ/
2
H
log(da/0)
+ 4R²
+
2/1
3N
21

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Proposition 2 (Confidence Bound for Dx,). With probability 1 8/4, for 1,2, we have that DN, E(D N L Dr. E[Du,l] An with
8log (1)
AD S
N
Proof. Since |Dnnalle & 1, this immediately follows by the matrix Hoeffding inequality.
Lemma (Confidence Bound for D N,1 My D.2) We have that with probability -
BB (2 -BDAD)
DN,,MMDNN2 EID -
S
(R² + AAm)An
(1 B)
(1 BD
2
AM
BDAD
where BD =1x [ D.lll2
Proof. For brevity, just for this proof, we define D; E(...,] for 1,2 and by M E[M]] E[My]. By union
bound, Propositions and with probability least 1 6. The statements the rest of this proof thus hold with probability at least 1 6. Now note that
D D MN, D N22
MD
S
[D |D MM, I22| N.2 - D2'11
+ D N,1 D, 1/2 MN. |e 112
12 M M |2
Now note that by inequality (1.1) from Wei al. (2005). have that
BD
D N
Dj 11 < BDAD
This means that
BD
[D] lla < D D
[DN. D.
BpAp
Also, since contexts in both trajectory halves have the same distribution and contexts generated independently. M E D D. So, |M|]2 | D2 R2 < R2. This implies that
M la & R MN M|1a s R
+ AM
Combining all these with the bound above, get that
[B -BDAp)
D N. My D
F(D..l] (F FM D - <
(R² + AM)AD
BDAD)}
BD
2
+
Am
BD
Proof. First note that E[DN.a] M = U.(A + "an J Also recall that Ú is given by the top-d
eigenvectors for E[D> My. N. D N-2)- This means that there is a dx x dx unitary matrix W such that U,W forms the
eigenvectors for (A + μal J This means that by the Pavis-Kahan theorem for statisticians Yu et al. 2014) and
Lemma we have that with probability 8
JOOT U.U. 1|2 |0O
U. UU.WTT U. ll2 V2(dx - 1 U.T.)))
22

---

Leveraging Offline Data in Linear Latent Contextual Bandits
2v 2dk
N. MN MN,,N,DDD2 D
2/22k X
(
B--BB)D))))) (R² AMM)AD +
( BD
(1-BpAp) BDDD)
AM
1-BDAA
We thus Aof be the value above.
Bounding A Now note that for large enough N, [E[ 1E
Blog(da/8) AaN
S 2'
In particular, by applying
inequality (1.1) from Wei et al. (2005), we have that Bn s 2I expression
2.
This already gives us the much simpler
2v2dx
64 1
16
Auf off
RR +
+AM)AD +
AM
X
Also note that by Lemma 4 and the matrix Hoeffding inequality, we have that
H
log da/o)
M ||[M]]]
+ 4R
2+
2p
N
o (dd
+1
H
log(da/0)
R +
+ 4R
2
8p²
2p1
N
We combine this with Proposition to get that
AM =0 =0
((10= o²
log(da/0)
V
N
Since o² < R22, we get that
dA log(ds/o)
AM =
R2
= -O(R²)
N
Also recall from Proposition
we get that
8 (og(da/))
DD
N
Also recall that Ày is the minimum eigenvalue of Fe A, and so the minimum eigenvalue of U, + palie JU. is larger than for large enough N. Combining all these, we get that
R2 Ag. We then conclude that Á > R²Aa 2AM M 2
Vdk
R2
R2
log(dA/0 N
A = 0
dA
V
12
dxdA log(d a0)
=0
Aa
N
23

---

Leveraging Offline Data in Linear Latent Contextual Bandits
D. Proofs for LOCAL-UCB
Theorem 2 (LOCAL-UCB Regret), Under Assumptions 7 and 2 if a1,
RVT CRy dx (2g(2T and 022
RyU++ CR/da (8) for a universal constant C, then with probability at least over offline data and online rewards, LOCAL-UCB has regret Regr bounded by
0 min (dAVVT,RR RdxVT
dAT dx
1+
Proof. Let the true latent state for the given trajectory be 0., so that the reward parameter B, = U.O..
Showing that U., B, are our confidence set: We check all our constraints:
Note that with probability 1- 8/33, U, satisfies ||Ü U.Ilø 2 vdk 2
From the standard confidence ellipsoid bound for linear models applied to dimension dA, with probability 1 - 8/3T,
||32, - B.1lv;" S 022 for all
Note that U.U. B. 9..
Finally, we apply the standard confidence ellipsoid bound for linear models to dimension dx instead of da with model (é(I), oT) (U,
(U, 3.) + 4. This means that ||U 3. U. Br.llvv.: S 0n, where V1, = (Idx +
E'Il (z)z T Note that since U.U. Ldx. we have that V1, V.... So, | (B (..))lauv.....-11 S a1, holds with probability at least 5/3T for all
U.).
So, by a union bound over all events, we get that for all actions a, the tuple (a, B., U.) satisfies our conditions with probability 5.
Leveraging optimism in low dimension: From above and by the optimistic design of the algorithm, with probability 1 1-6 6, 6(2,, 0z) T, Br is an upper bound on ((1,,a) TT B, for any action Thus, we have the following regret decomposition with probability at least 1 - 8:
Regr
Mar, ai) B. -(I,, ot) B. B,
o(1,, T a1)r,a))
az)
p( 01) ",ū, 3. o(x,, TU.
T
Σ
MaF, a:) T,U,Ü - U.U. )r, + (1) U.U. (B. - 3.)
RT - U.U. 122 Σ oa a.) T.U. TU. -B. -3-3.)) B.)
RT
p0 a1) U.U. (Be B.)
RT RTA Duft
(1 ( U.ll(uV...)) I/ (B. 3.)l
< RTA Autt
02.1l0(a ar) U.ll(u
(8)
RT A
Σ
222 ar2 [0(,,, az) T
24

---

Leveraging Offline Data in Linear Latent Contextual Bandits
(8is)
RTA O (dx VllxTloo Tlo (T/6)
(1))
RAD
T dddd log(da/0,
Rdk T'log (T/8)
+
Amin
N
XD Amin
Tda log(da) dx N
=0
Rd / (T/6)
1+
Tda dx
Rdx VT
1+
where (i) holds since Ü,0, 3. - 3r and U,U, B. = Bx (ii) holds since Vi, (U, V.U.)=+ (iii) holds by the usual proof of LinUCB applied to dimension dk. and (év) holds by Theorem !
Leveraging optimism in high dimension: This is merely the proof of LinUCB. From above and by the optimistic design of the algorithm, with probability - 5, (x ax) B. is upper bound on pbI,, a) Ga for any action a. Thus, we have the following regret decomposition with probability at least 1 ò:
Regr
px, ( B. 6(1,, at) B.
(1 az) T B.
M1F1, as) T
T
Σ ( ur) 1lv. - B.llv.
O(RdA Tlog(T/6))
Ö(RdAVA) VT)
where the last line follows from the standard regret bound for LinUCB applied to dimension dA- Combining the two bounds, we have our result.
X Amin
Tda log(da) dx N
Regr = 0 min RdA T (og(T/)), Rd V log (T/6)
1+
Tda N
min
RdAVT, R
1+
25

---

Leveraging Offline Data in Linear Latent Contextual Bandits
E. Proofs for ProBALL-UCB
E.1. Confidence bound for the low-dimensional reward parameter Lemma 6 (Confidence Bound for B1,)) If for all timesteps I, ((T,, az) lies in the span of U, we have that for a universal constant C,
10 -0 Vi!!
S SR/U+ ERV CR logg(/1
Otherwise, we have that
U Bi 8T Br VT.
S RVR + Rog + Aon CRy da log(1/5)
where |1 X, x v, with notation |Alco == VII CAll2
Proof. For brevity, in this proof we will denote by X; == 10(21, a1)... p( ac-1)) which a x dA matrix. Recall
that V. = pld. + X X, We will also denote V1, = U V,U. Note that the vector of rewards is given by X,3, + Th- where 1)t is random vector of independent R2 -subgauussian entries. So, b, X, (X,3, m1). Also define the notation Ay UÜ U.U..
If actions the span of Ú. Note that since all actions taken lie in the span of Ú, x, = X,OU This is the key observation. Now note that
B1, UV (X,3, + m1))
úV x, X.G. + U x, 1/
= üVi, x 0, 3. + -V, x n
UVT 1. Nl ÚT 3. UV X n
ÚU B. - - UT B. + UV _ m
The rest of the proof is similar Theorem 2 in (Abbasi- Yadkori et al. 2011
We first note that for any x, have that
x T(O,, TTTB))) < (a V() B. ú X ml)
| =llv=: [[-nbT B. U x nh) Iiv
s | allvy (pIIOT Bally,t + |10 x, nelly
Now note that 21|l from (Abbasi- Yadkori et al.
B. llv "
< |1 B.llaVT RVT and by the self normalized martingale concentration inequality
2011) applied to dx dimensional vectors Ô X;, we have that with probability at least 5, X, Th ll S CRVdd d log (t/8)) for some universal constant C. So we have with probability at least 1 that
[
| OUT T0 |
S | - OOT TOTTl a.l (RVT+CRVV, da dolo((1)))
This means that
BT. - 0T 0,1,,11, v-
= -1,3,, - 00 B. vi
S RR/ - CR da (tg(1/8)
26

---

Leveraging Offline Data in Linear Latent Contextual Bandits
If all actions don't lie in the span of Ü. This time note that
Bi OV 1.2 x (X,8. + m/))
UV x X,3, + UVT X th
iV x X,x,UU UV x
-VV,)"" x X,ÜU B. 3.+ x, X, + ÜV x, T
-V1. - pl B. + x X, + -V x
OU B. - B. OV x, X, 3. UVT x, "
The of the proof is similar Theorem 2 in (Abbasi- Yadkori et al. 2011).
We first note that for any x. have that
x (B1, úū B.) = (a V.VV Lū B. X, x, 3. U X mo)
|10 2 <llv,.
(-uÜ² B. U X X, A B. + Ú X mh)
vi.
110 2 llv
(R10" B.lly + X, x A. + || x mellyytt
0 v7
(MIIO (MI0TTAllV;: + 3 1| X Xellv;; + |10 x! ne nellvy7
allv,,
(NIlOT B. + R| l2 | x Xelly, + | xJ melly
zllv! Ti/i"TBBlyy + RA Ú X, X Xelly:: + 110 x nellyy
Here, (1) holds because for any matrices A, C. and any vector we have that |Avlc VV CAv S
IVllay |A CC = |/vl2/|AA||c where we recall that ||A|c: := VIIATAAII
Now note that p B. l S B. S RVT and by the self normalized martingale concentration inequality
from Abbass- Yadkori et al. 2011) applied to dk dimensional vectors Ü Xr, we have that with probability at least 1 8. | X, T/ l S CR d log(t/5) for some universal constant C. Also recall that | x, Xelly:: = fig. So we have with probability at least 5 that
| -U 3
2 vnl
I ( ûûT (OTTBa)l (RVT- RAOHK + +CR dA log((()
This means that
1 B 0J B. [
B.l| - =1(0(à,, ÚÙ B.) B.)
S RVU+ + RAOTTR dA log(t/)
Note that Ki | ÜT disss ag (
E Ú (6 ag (o)ss, 7/. O(),, but this is worst
V
case bound.
We also state a lemma, borrowed from the standard proof of LinUCB regret.
Lemma 7. For any sequence of actions and contexts It, ag and V. = jul + + olze, ar (ax,, To) we have that
T
Σ
min (0)( =0(vdA)
T
min (10 o(x,, al O(vdk)
27

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Proof. This follows immediately from Lemma 11 of Abbasi-Yadkond al. 2011)
E.2. Proof of the theorem
Theorem 4 (Regret for PrOBALL-UCB). Let 01, RV RA CR dx log(T/o) and let 02, RVD CR (Tg). Let S the first timestep when Algorithm does not play Line 6 and let T if no such timestep exists. For 7' we have that
Regr Ō (min (Reg,, Regagbr))
where Reg RdAVE and Regayh,T r is defined as
dAT V
A
S
Rd VT 1+
2
22
dxN
SN
In the worst case, O(t) and Ei x² O(T2), but if all features o(x,, ar) lie in the span of U for S S, then =² = OT)).
Proof. We will first show that bonuses give optimistic estimates of the reward whp and then leverage the optimism.
Showing optimism when 7 VT < dA: In this case, are inside the "if" statement and are running projected and modified version of LinUCB. In that case, for all timesteps the projected version is run, all features will lie in the span of U, This is because the maximization problem is given by
ÜÜ Br,, + +Iū" p(z, a) a)
a₂ = arg
max
(.l
If our features are isotropic, then this is only maximized by feature in the span of U. So, the conditions of the first bound in Lemma 6 are fulfilled. We will denote Vi.- = Ú V.U. We have that with probability 8/2, for all a, the following holds.
()xxa))Tp a( O0 Bul = l0(z, a) 0@Ú 3. - B1.,)1 + 10(z, a) T) TU.U, 00T -T
< ((0 ally: [ -ÜTA BI + U.U. 00 1|2
I "u ő(z, a)lv + +RAuf
This shows that with probability at least - and for all x, a,
(xx T,, B, - p(x, a) 00 Br. + an ((2,a))lv; + RAoff
This implies that with probability at least 8, for any action a,
o(x, TT
B. s max (1 a) ÜÜ Br + an o(z,, a)lxy + RAoll
a(),, T Bi,, + a oax, an) 1v77 + RA
Leveraging optimism when 7 VT S dA: Consider the standard regret decomposition, which holds with probability
1-8:
T Regr Σ
bar,, a glaa, at) TB.
((a,, uz) T TOÜT Bi,r
blu,, ax) T B. ((r,,a))ll;; + RAoff
28

---

Leveraging Offline Data in Linear Latent Contextual Bandits
20 a( V:) + 2RAoff
(2)
(0
20 min (10 (i,,, aw + 2RAoff
2( 2i + C dv log((/6)) min (11 (()) an) ai)llyy;) + 2f
T
2RA of min (IÙJ MTT ailxzt)
+
t
(18)
2(RVT dv (Tg())
Σ min (( 2RA
(10 (1Fr
+ 2RA off
Ki
2
min
(00)
Σ KY
Oldx Tlog(//)) + 2R T +RR
VdkT
(3)
T
VT
Rdk Mudk/Tlog(11/ 1
dk
Tdk
where (i) holds since ci T B. a B3 2R, (it) holds by the Cauchy Schwarz inequality and (iii holds by
Lemma 7 So, we have that
dA log(dA) Ndk
dx
s
1)
Regr =0
Rd V Tlog (T/5)
1+
VT
K
2420
T
1 1²/0
dAT
dA TN
=
R
1+
Nd
t=1
min(S,T)
dAT
da min
= = RdxVT
1+
1220
V
Ndk
where the last incquality holds since T < S for the first timestep satisfying Aoil (VB+ v 4g Es 12t
2 dA
Additionally, since Aoi (VT+
dx V4 T
Σtn nit
S d,. we have using equation that
Regr = Ō(dAVT)
well. So, we have that when 7 Aool VT S da.
min(S,7)
Regr = min da dAVT, RdRVT
dAT V Ndx
dA min(S,T)N
1+ 23500
Bounding regret when 7 (VT+ V dx EE m3
2 da: In this regime, after the first timestep S satisfying
Auti (V3 + V dx - mZ 2 da. we run standard LinUCB with dimension dA and incur (ddvVT) regret with
29

---

Leveraging Offline Data in Linear Latent Contextual Bandits
probability 1 8. Until timestep S - 1, we run the projected and modified version of LinUCB and incur regret bounded by
Ei= mt Vdks= (ddvs+ dkvs)
Ō(dxVS) + S + 2R
TO(dAV++dRV) =((AVV))
Combining these, we incur ((dAVT) regret during the whole method.
Also, since da LT S Doff
(VTS+
V
d
Ei
Kiz
we get that our regret is also bounded by
d
5
Regr Ō Doff
VTS+
5
dxT
8
= Ö(dxVV Doll
VTS +
2
S
1=1
min(S,7)
dAT Ndx
d
=Ō RdkVT
1+
13
min(S,
TYN
So, our regret satisfies
min(S,T)
Regr = min dAVT,
Rdx Rdx vT
1+
1
dAT
da min(S,
Σ
x
22
Ndx
E.2.1. UNDERSTANDING Letting X, Ú [0(x1, a1)................. (1,, az)l recall that Ki = 1ÚXX X, 1(xx4x7xx)-1 In the worst case, S ||ÚX Xellz O(t) since actions have norm 1. In that case, 1 Eim 0(52). However, if X, lies in the span of ÚT, then X,U Ú= Xx. This means that for Y, x.U
3
+ x, X,U" YY + Y.)
=aa- m(al+ Y.)YY Ö(VV
So, 1
3 -
30

---

Leveraging Offline Data in Linear Latent Contextual Bandits
F. Lower Bounds
We formally state and prove the lower bound below. Much like how we generate families of reward parameters in lower bound proof' for purely online regret, we are now generating a family tuples latent bandits (for the offline data) and reward parameters represented in the latent bandit (for the online interaction).
Theorem 7 (Regret Lower Bound). Let d 2T, d2 S N, dx > 1. Consider the action set A {a |a]|2 S $1}. For each regime, either (da-dK)N being larger thun 1, or between 1 and 1/2, or less than 1/2, there exists family of tuples F), where F is latent bandit with a rank dg latent subspace and [3 a reward parameter its support, satisfying the sollowing:
dxcT
(i) For any offline behavior policy Tb, all F have uniformly bounded No associated to the offline data.
(ii) For any offtine behavior policy Th and any learner, there is a (F, 3) such that the regret Reg(T, (3) of the learner under offline data from T6 and F and online reward parameter B is bounded below by
Reg(T (T 2 min dAVT, dx VT (1+
(
dAT dx
Remark 1.
We are stating a version with no contexts and only actions here for notational simplicity, the version for contextual bandits has the same proof verbatim. One just replaces A with {Ø(2, a) x E X,a a E A}.
Note that the theorem statement is complicated ensure that it is essentially the strongest version of the theorem possible. Condition (i) is needed to ensure that we aren't 't cheating by ensuring that the offline data itself obscures the correct subspace. Condition (ii) is the actual regret lower bound.
Proof. The proof is inspired by the proof of Theorem 24.2 in Lattimore and Szepesvári (018). giving a regret lower bound for standard stochastic linear bandits with a unit ball action set. Without loss of generality, we can assume that da Z 1.01dk, otherwise both terms in the minimum have the same order and the proof is complete. An astute reader
S dAvT.. We will first address the will note that the regimes are separated based whether dx VT (1+ (I+V (da-dx)))
dx
difficult regime where S V
dxT (da-di)) S 1. Until stated otherwise in this proof, will work in this regime and assume
that 2
Tx J
S
(da
F.1. Setup Consider in 5/3 V dx/T and Aont = - V dx/N. B= (+ Jdx x {0} x (=Aoot) dda-dx and let ,3 E 4v3
We set the dth coordinate to for technical reasons. For any bandit instance B, let the rewards have Gaussian noise with variance 1. Construct family of latent bandit-online latent state pairs follows. Define Fg to be latent bandit with uniform distribution over all 2dx reward parameters obtained by negating any of the first dæ
coordinates of B. Notice that this latent bandit has 2dx latent states sharing dx dimenssion subspace. Let us construct the family of pairs (F3,, B), where Fa is the latent bandit used to generate offline data and ,3 is the reward parameter underlying the online trajectory.
Note that condition (i) is satisfied by merely computing the matrix Eg[33T] and noticing that eigenvalues are merely norms dx
dx or
N up to constant. Now note that ||@||2 / dx
d3 + dx (da ddx) up to constant, so X is bounded since
TIB Ta IN <
Notice that if 3' is 3 with any of the first dx coordinates negated, then Far is the same latent bandit as Fg. Assume that a fixed behavior policy T6 is used to produce offline data, producing known dataset of contexts and actions shared across all latent bandit instances. We will repeatedly use the fact that dk 1 > dx in this proof.
F.2. Proof Sketch and Intuition
Notice that we are working in the regime where N is significantly larger than T. That means that are treating the first dx coordinates the main subspace and the rest of the coordinates as perturbations out of the subspace. This is represented in
the notation An and Aout- In our regime, where / (da dx
d < 1, Dout should be thought of as much smaller than Ain-
31

---

Leveraging Offline Data in Linear Latent Contextual Bandits
Eventually, we intend to lower bound the average regret over all pairs (Fg, ranging over the vertices of hypercuboid B of reward parameters. This will allow to claim that there exists one parameter / E B for which the regret is larger than this average. To lower bound this average, we first use change of measure inequalities, careful computation and clever design of B to get an intermediate lower bound, bounding the average regret over any pair of "adjacent" tuples (F",3) and (F, (3). These are pairs where the sign of only one coordinate is flipped from ,3 to B and F and F' at most differ in their "out of subspace" perturbation. We can then average over all such pairs to lower bound the regret averaged over all B E B, as desired.
We will need two separate computations for the intermediate lower bound one for when the pair of adjacent reward parameters corresponds to coordinate < dx, and another for when it corresponds to coordinate >> dx. The proof ends with the averaging trick mentioned in the previous paragraph.
E.3. Regret Lower Bound Decomposition
For i < dx. define ;; T min(t= Ei=1 A2, 2 T/dx). For i dx; define TÜ T A min : E N T/ - -x)) For now, let us denote the regret under parameter B to be Reg(T, B3.. Now note the following decomposition of the lower bound.
dg-
Re = LB
Ain
Ass (ign(33))
Vdx -1
T
da
1
Ass sign(Bi) ]
+ Dout
Vda= dd
1=1 i=dx+1 +1
in V dk
T
dx -1
Avi sign( 2
2 E3
2
Vd
i=1
Aont dA - dx
T
Vdd -dk Ass sign((3)) 21 ]
1
2
1=1
i=dx+1
dx
2
in
dK
F
Vdx -1 - Ass
2
1=1
Aout vdA
dx
27
Eg
An sign (3:)
Vdda
dx
i=dx+1
The first inequality holds by merely evaluating the square, simplifying and noting that ||4.112 < 1. The second inequality
For < dx and x E {+1), define (+(x)= == E/ (vok= Aes sign((3)) For i > dx and x E {+11, define
DZ (vai-ax An sign((:)) (3,)
Fix i and let , be such that = B, for # and 8 = -B, Let IP and P' be the joint laws of the offline data and the bandit/leameer interaction measure for B and 33' respectively. We will bound Eg [1)] + Eg (-](-1) in the following subsections, treating < dx and i >> dx separately. This will allow us to bound Epes averaging trick.
(3:)) later and apply an
F.4. Bounding E, [3(U,(1)] + (U.(()) when i< dx
Note that
( Es(Ui(1)] 2 E.r (U,(-1)
(6 dx
I +2) v D(P, Pr) Pr)
(6)
2 [Up(
(-)((1))
Ain
3T
+1)
Σ
A3
dx
-=1
32

---

Leveraging Offline Data in Linear Latent Contextual Bandits
(Gx))
3T
T
Fgr [U:(-1)]
Ai
dk
dx
(60)
5v3AmT
2 Egr (U((-1)))
dx
V
dx
(4)
where in (i), rely the bound below and then the TV distance change of measure inequality, followed by Pinsker's inequality. The bound below relies on the fact that dx- - 1 2 dx/2.
To Σ
2
T
T1
4T
2T dx
6T
(1(1)
vdk - Au sign(3,)
2
dx +2
+2
A
+
+
dk
dk
For the bound above, we use the definition of T. In (it), we use the chain rule for KL divergence under stopping time, and crucially note that the offline data distributions is identical in this case since F3 Fgg. Inequality (iti) holds by the definition of Ti, and inequality (iv) holds since dx S dA S 2T since d' H s 2T.
So, we can conclude that
5V34in
T
T
+ (u((1))
L (1) + U.(-1)]
V dx
dk
5V3AmT
T
2T gv
Σ Anp
V dx
dk
dx
2T
5 5VAAmT
T
dx
dx
V
dx
T
(5)
dx
F.5. Bounding (1) + [=((((-1)] when i dk Note the following computation, where we let Ar, be the action chosen at step offline trajectories d, where = 1 - H and 1 N.
En(U 2 Eg [[(-1)]] (
4T
dA -dx dk
+2
D(P,P" Pr)
(8) 2 (U((((-1)) - Dout
(,,2T)
2T
+1)
T
dk
A
dA dk
48N
1=1
(a)
2T
T
dg
2 Eo (o)(((-1))) - Dout
dA - dx +1)
+
da
dk
48
(2)
5v3Aout
T
2 [U: (-1]
d dx
V da
dk
where again (1), we rely on the bound below and use the TV distance change of measure inequality, followed by Pinsker's inequality.
4T
0.(1) = Σ E= VdA dx
An sign(3))
2 Σ [=1 dA dk
+2
A2 < d
+2
dk
1=1
For the bound above, we use the definition of T,. In (i). we use the chain rule for KL divergence under a stopping time and include the non-zero KI. divergence coming from the offline term this time, which appears as the second term
33

---

Leveraging Offline Data in Linear Latent Contextual Bandits
in the square root. Inequality (dit) holds by the definition of 7 and the fact that A 1. Inequality (iv) holds since dd(da dx) H v H2H S 27.
So, we can conclude that
4V3 T
T
Eg[U+(1)] + (o 2 (1)) +((-1)]
dA
dk
dA dk
= F3r
dA dx
T
+
Σ
Ape
4V3
dA dx
V dd - dx
T
t=1
21
4v3Doui
T
Ax dk
d1 dk
dr dx
21
T
dRT
dA dk
dA dk V ((a-d)))
T
2 da - dk
(6)
where crucially, the last inequality holds since
dxT [dA- S 1.
F.6. Lower bounding regret using an averaging trick
For I dk, define by B_, == {n jdx vary. Similarly, for i >> dx, define the slice B_, == { )dx jxx-1 -1 x {0} x Ant d We will denote the tuple of
x {0) x (+ da-dx which is the slice of B where all coordinates but 8;
coordinates of B other than i by B_s. We thus get the following lower bound on regret, using inequalities and
Ain Vin I
dx -1
Σ Reg(T, 3) 2 BEB
Σ
(sgUn()ign(
2
i=1
BEB
out V
d
dk
Σ
2
d=dx +1 BEB
A in vdk
-1
dx-1
Σ
[s(U((sign(B.)]]
2
B. :EB i (A.E(tAm)
da
A out V
d
dx
Σ
Σ
(sggn())
2
i=dx +1 ALIEB_. (
in
dk
dx -1
T
Dont v dA
dk
da
Σ
T
2
dx
2
da dx
i=1
B-IEB_.
i=dk +1 BB.EB_:
A in Vdk
A Anut Vda
dx
Σ
+
2/2
2
2
B. :
A
2d
(dA - dx
dx VT
1 1
2
80/6
dx
That means that there exists / E B so that
1 dxVT
(da - dx)T
Reg(T.3)
1
8066
Nx
As desired.
34

---

Leveraging Offline Data in Linear Latent Contextual Bandits
E.7 The Other Two Regimes
In the regime dx T (da-dx)) dR) one can simply use the 2d bandit instances the standard unit ball regret lower bound from Theorem 24.2 in Lattimore and Szepesvári (2018) with dimension d'A. and follow the proof essentially verbatim. The only difference is that we will be choosing pairs of tuples (F", and (F, (3) instead of just pairs of reward parameters 3'' and B. One can choose any latent bandit with dx reward parameters in its support, two of which are B and 3 and set both F' and F" to this. For this, it is convenient to choose the latent bandit to have a uniform distribution over 2d reward parameters obtained by flipping signs of dx chosen coordinates, since then one can easily compute that X = 1. This will ensure that offline data distributions are identical and the KL divergence contribution from the offline data distribution O, allowing us follow the proof of Theorem 24.2 Lattimore and Szepesvári (2018) essentially verbatim. This establishes condition (ii), and we have also establis
Similarly, when d < -dd NN, (2018) again, this time with dimension dg. Fix F to be the latent bandit with a uniform distribution over all 2 reward parameters B = } x {0)dd--a dd and consider the family (F, () of tuples with fixed F and /3 varying through B, We can now follow the proof of Theorem 24.2 in Lattimore and Szepesvári (2018) verbatim. Again, the only difference that we will be choosing pairs of tuples (F, 3") and (F, () instead just pairs of reward parameters 3 and ,. And ye again, we can check that Da and condition (i) is thus satisfied.
use the standard lower bound from Theorem 24.2 in Lattimore and Szepesvári
35

---

Leveraging Offline Data in Linear Latent Contextual Bandits
G. Additional Algorithms
We provide a version of SOLD that utilizes pseudoinverses. We use this within our experiments to avoid having to search for regularization parameters, and recommend that the user use this instead of Algorithm when finding a suitable regularization parameter is a concern.
Algorithm 4 Subspace estimation from Offline Latent bandit Data (SOLD) Pseudoinverse Version
1: Input: Dataset Dfrr of collected trajectories Tn ((In, I, 1n In, 1), >.... (In, On, (n,,1), under behavior policy Tb, dimension of latent subspace dk.
2: Divide each Tn into odd and even steps, giving trajectory halves Tn,1 and Tn.2.
3: Estimate reward parameters Br,i
vt nn,s where V Vn,a Eaaneee (1x,)) a) and D
((....)ETT. Ó(I, a)r for = 1,2.
4: Compute M,, - (8,,, 1r + 2n,2 and compute MN + Σ M,.
5: Compute W n, the eigenvectors of V nn corresponding to nonzero eigenvalues. (W,,, 7: Obtain U, the top dx eigenvectors of N,1 MMM N.
6: Compute D D,T - N I WT,)) == 1,2.
return Projection matrix OÜT, Aoff as in Theorem
8:
We also provide a method of instantiating the ProBALL framework with linear Thompson sampling. Like ProBALL- UCB, ProBALL-TS operates within the estimated subspace until the online uncertainty is low enough. We therefore maintain two normal posterior distributions, one over the latent state parameter the estimated subspace, and one over the high-dimensional reward parameter, and sample from them as such.
Algorithm 5 Projection and Bonuses for Accelerating Latent bandit Thompson Sampling (ProBALL-TS)
1: Input: Projection matrix ÚÜT, confidence bound Aof. Hyperparameters 01,1, 02,1, T,T'. 2: Initialize V, + 7, b +- 0, +
3: for = 1.... T do
4: if WOBTTV + DOFT'N V d R//t S dA then
5: Compute 01, + (0 -
6: Sample Ô1,, ~ N BBI,, (
7: Play at arg max, o(x a) U0..
8:
else
9:
Compute B2,t V.
Sample B2, N (B2,,, a² V; Play arg max, obat,, a) 32,
11:
12:
end if'
13: Observe reward r, and update b + b, + 6l0, a)r, V.- + V. + ((1,,
14:
Update C,-1 +- C, + 0 dax, (x)a(a ae) NI-1 +- ([C.+ll@Tv,.n)
15:
end for
36

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H. Experimental Details and Additional Experiments
H.1. Determining the Latent Rank from Offline Data
We note that as discussed in 3 can use the eigenvalues of D D Mr.MMDDNN. determine the rank of our subspace. We the version of this arising from pseudo-inverses instead of regularization, just like in the MovieLens experiments. We demonstrate that we can indeed determine that the dæ 18 by finding the significant eigenvalues of the pseudo-inverse version of D N.. MyD estimated from the offline dataset of 5000 samples. We show the plots and log plots these eigenvalues. We also plot the eigenvalues of the completed ratings matrix for comparison. Notice that they match and both fall after 18 eigenvalues.
Plot of Eigenvalues from SOLD, Rating Model 1.0
Eigenvalues from SOLD
Rating
Eigenvalue Magnitude
0.4
0.2
0.0
25
50
75
100
125
150
175
200
Sorted Eigenvalues
Figure 3: Plot of eigenvalues of aforementioned matrix. Notice the drop after 18 eigenvalues.
Log Plot of Eigenvalues from SOLD, Rating Model
Elgenvalues from SOLD
Rating
Eigenvalue Magnitude
10-3
10
10-
10-9-
25
50
75
100
125
150
175
200
Sorted Eigenvalues
Figure 4: Log-plot of eigenvalues of aforementioned matrix. Notice the drop after 18 eigenvalues.
37

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H.2. Simulation Study
We generate with U.y i.idd. On dgd We simulate the hidden labels 0, ~ NN, dx Idx) generate feature vectors
db (n.h) (O, ( Ia,) normalized unit norm, and sample noise 6r.h i.i.d. (0, 0.52). We use SOLD estimate Ú from the offline dataset Doft. which consists of 5000 trajectories of length 20 each. In accordance with the confidence set determined by (Li et al. 2010), we choose on 0.33 /dx log(1 + 10T /dx) and 02, 0.33 log(1 10T/da).
and share the LinUCB and ProBALL-UCB hyperparameters by assigning 022
T 0.1
1
5
10
Cumulattve Regret
H-ProBALL
E-ProBALL
LinUCB
50
50
50
50
100 Timesteps
200
100
200
100
200
100
200
Timesteps
Timesteps
Timesteps
Figure 5: Comparison of ProBALL-UCB with LinUCB, for different choices of T and confidence bound constructions. All variants perform no worse than LinUCB, with martingale Bernstein performing the best. The shaded area depicts 1-standard error confidence intervals over 30 trials.
11 All experiments single computer with Intel i9-13900k CPU, 128GB of RAM, and NVIDIA RTX 3090 GPU, in more an hour total.
38

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H.3. MovieeLens
MovieLLnns (Harper and Konstan 2015) a large-scale movie recommendation dataset comprising 6040 users and 3883 movies, where each user may rate one or more movies. Like (Hong al. 2020), filter the dataset include only movies rated by at least 200 users and vice-versa. We factor the sparse rating matrix into parameters f and movie features & using the probabilistic matrix factorization algorithm of (Mnih and Salakhutdinoy (007b). using nuclear norm regularization so that the rank of [ is dx 18. However, we consider a much higher dimensional problem than (Hong) et al. 2020) do we let d 200 so 3 E IR1589 200 Φ E R At each round for user i, the agent chooses between 20 movies of different genres with features & :...... 2 Pazo and has to recommend the best movic presented to it to maximize the user's rating of the movie. We generate rewards for recommending movie j user by 3 Φ3 + Caj. Gzj i.i.d. N/ 0.5).
Our hyperparameters
chosen and varied just as in the simulation study. To reproduce the methods of (Hong et al. 2020), cluster the user features into dæ clusters using k-means, and provide mUCB and mmUCB with the mean vectors of each cluster as latent models. We initialize ProBALL-UCB with a subspace estimated with an unregularized variant of SOLD, that uses pseudo-ine pseudo-inverses inverses instead of inverses, because of difficulties in finding an appropriate regularization parameter for this large, noisy, and high-dimensional dataset. The subspace was estimated from 5000 trajectories of length 50 simulated from the reward model and the uniform behavior policy. Note that we assign Doff for mmUCB, as this their tolerance parameter for model misspecification.
0.01
0.1
0.5
T=1
H.PrOBALLUUCE
400
400
PCC
Cumulative Regret
M-PrOBALL-UCO LiUCB
300
300
300
T5
200
MINTS
200
200
200
100
100
100
100
0
0
100
200
100
200
100
200
100
200
Timesteps
Timesteps
Timesteps
Timesteps
Figure 6: Comparison of ProBALL-UCB with LinUCB and TS algorithms, for different choices of r and confidence bound constructions. All variants perform no worse than LinUCB and outperform the TS algorithms, with martingale Bernstein performing the best. The shaded area depicts 1-standard error confidence intervals over 30 trials.
T 0.01
T 0.1
== 0.5
T=
400
M-PrOBALL-UCE
400
400
Linuca
Cumulative Regret
M-PrOBALL-TS
300
300
MWTSS
200
200
200
100
100
100
0
0-
0-
100
200
100
Timesteps
Timesteps
Timesteps
Timesteps
Figure 7: Comparison of ProBALL-UCE and ProBALL-TS initialized with SOLD against LinUCB, TS, MixTS, and mmTS, for different choices of 7 and confidence bound constructions. ProBALL-UCE outperforms LinUCB, and ProBALL-TSS outperforms MixTS and mmTS. Shaded area depicts 1-standard error confidence intervals over 30 trials with fresh 0. The confidence intervals on regret thus account for the variation in frequentist regret for changing 9.
39

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H.3.1. UCB ALGORITHMS
T=
0.01
T=
0.1
T= 0.5
T=1
300
PrOOBALLAUCE
350
ProBALL-UCE
Cumulative Regret
250
M-PrOBAL-UCU
300
LiUCC
200
250
mmuCE
200
200
150
100
100
100
100
50
50
0-
100
Timesteps
Timesteps
Timesteps
Timesteps
Figure 8: Comparison of ProBALL-UCB initialized with SOLD against LinUCB, mUCB, and mmUCB, for different choices of and confidence bound constructions, in terms of regret. All variants of ProBALL-UCB perform worse than LinUCB, and outperform mUCB and mmUCB. Shaded area depicts 1-standard error confidence intervals over 30 trials with fresh 0. The confidence intervals on regret thus account for the variation frequentist regret for changing 0.
== 0.01
== 0.1
== 0.5
==
4.0
3.0
3.0
Average Rating
2.5
2.5
3.0
2.0
2.5
H-PIOBAL-UCE
2.0
M-PrOBALL-UCD
1.5
1.5
1.5
mUCA
1.0
1.0
1.0
mYnUE
50
100
150
200
100
150
200
100
150
200
50
100
150
200
Timesteps
Timesteps
Timesteps
Timesteps
Figure Comparison ProBALL-UCE initialized with SOLD against LinUCB, mUCB, and mmUCB, for different choices of and confidence bound constructions, in terms of rolling average rating over 25 timesteps. ProBALL-UCB performs worse than LinUCB, and outperforms mUCB and mmUCB.
40

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H.3.2. TS ALGORITHMS
T=
0.01
T= 0.1
T= 0.5
T=1
500
H-POBBALLTS
400
400
PPOOBALL-TS
Cumulative Regret
400
N-PrOBALL-TS
300
300
MIXTS
200
200
200
100
100
100
100
0
0
100 Timesteps
Timesteps
Timesteps
Timesteps
Figure 10: Comparison of ProBALL-TS initialized with SOLD against TS, mmTS, and MixTS, for different choices of and confidence bound constructions, in terms of regret. All variants of ProBALL-TS outperform TS, mmTS, and MixTS.
0.01
0.1
0.5
T=
3.0
3.5
2.5
Average Rating
2.5
2.0
2.5
2.0
2.0
H-PrOBALL-TS -T
1.5
E-PIOBALL-TS
1.5
M.PrOBALLTS
1.0
1.0
mmnS
0.5
0.5
MixTS
0.5
50
100
150
200
50
100
150
200
50
100
150
200
50
100
150
200
Timesteps
Timesteps
Timesteps
Timesteps
Figure 11: Comparison ProBALL-TS initialized with SOLD against TS, mmTS, and MixTS, for different choices of т and confidence bound constructions, in terms rolling average rating over timesteps. All variants ProBALL-TS outperform TS, mmTS, and MixTS. Shaded area depicts 1-standard error confidence intervals over 30 trials with fresh 6. The confidence intervals regret thus account for the variation in frequentist regret for changing 0.

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H.3.3. COMPARISON AGAINST LOW-DIMENSIONAL GROUND TRUTH SUBSPACES
T=
T= 0.1
T= 0.5
T=1
250
400
500
E-ProBALL
Cumulative Regret
200
M-ProBALL LinUCB
300
300
LinUCB Small
mUCB Small
300
minUB Small
200
100
200
100
50
0
0
0
0
100 Timesteps
200
100
200
200
Timesteps
Timesteps
Timesteps
Figure 12: Comparison of ProBALL-UCB initialized with SOLD against LinUCB, mUCB, and mmUCB on low-dimensional ground-truth features, for different choices of and confidence bound constructions. When T small enough, all variants of ProBALL-UCB perform no worse than low-dimensional LinUCB, and outperform mUCB and mmUCB, on ground truth features. This showcases the efficacy of SOLD, and demonstrates that we recover subspaces that are just as good as ground-truth. Shaded area depicts 1-standard confidence intervals 30 trials with fresh 0. The confidence intervals on regret thus account for the variation in frequentist regret for changing A.
T = 0.01
T 0.1
T == 0.5
T= 1
4.0
3.5
3.5
3.5
3.5
Average Rating
3.0
2.5
3.0
2.5
2.0
2.5
E. PYOBALL
2.0
M-ProBALL
1.5
2.0
LinUCB
1.5
LinUCB Small
1.0
1.5
mUCB Small
mmUCB
0.5
50
100
150
200
50
100
150
200
50
100
150
200
50
100
150
200
Timesteps
Timesteps
Timesteps
Timesteps
Figure Comparison of ProBALL-UCB initialized with SOLD against LinUCB, mUCB, and mmUCB on low-dimensional ground-truth features, for different choices of 7 and confidence bound constructions. When small enough, all variants of ProBALL-UCB perform no worse than low-dimensional LinUCB, and outperform mUCB and mmUCB, ground truth features. This showcases the efficacy of SOLD, and demonstrates that we recover subspaces that are just as good as ground-truth. Shaded area depicts 1-standard error confidence intervals over 30 trials with fresh 0, The confidence intervals on regret thus account for the variation in frequentist regret for changing 0.
42

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H.3.4. No USAGE OF SOLD
T= 0.01
T=
0.1
T= 0.5
T=
300
400
250
E-ProBALL
Cumulative Regret
M-ProBALL
250
LinUCB
300
300
200
mUCB
mmUCB
150
150
200
100
100
100
50
50
0-
0
0
0
100
200
100
200
Timesteps
Timesteps
Timesteps
Timesteps
Figure 14: Comparison of ProBALL-UCE initialized with ground truth subspaces against LinUCB, mUCB, and mmUCB. for different choices of r and confidence bound constructions. All variants of ProBALL-UCB perform no worse than LinUCB, and outperform mUCB and mmUCB. Shaded area depicts 1-standard error confidence intervals over trials with fresh 0. The confidence intervals on regret thus account for the variation in frequentist regret for changing A.
T = 0.01
T 0.1
T == 0.5
t= 1
3.5
3.0
3.0
3.0
Average Rating
3.0
2.5
2.5
2.5
2.5
2.0
2.0
2.0
E-PrOBLL
2.0
M-ProBALL
1.5
1.5
1.5
mmuCa
mUCB
1.0
1.0
1.0
Perfect
0.5
0.5
50
100
150
200
100
150
100
150
200
150
200
Timesteps
Timesteps
Timesteps
Timesteps
Figure 15: Comparison of ProBALL-UCB initialized with ground truth subspaces against LinUCB, mUCB, and mmUCB, for different choices of and confidence bound constructions, terms of rolling average rating over 25 timesteps. All variants of ProBALL-UCB perform no worse than LinUCB, and outperform mUCB and mmUCB. Shaded area depicts 1-standard error confidence intervals over 30 trials with fresh 0. The confidence intervals regret thus account for the variation in frequentist regret for changing 6.
43

---

Leveraging Offline Data in Linear Latent Contextual Bandits
H.4. Sample Complexity of SOLD
We perform an empirical study of the sample complexity of SOLD on the MovieLens dataset. To do so, we compare the end-t--end regret
200 timesteps of both ProBALL-UCB and ProBALL-TS, against LinUCB and Linear Thompson sampling using ground-truth truth low-dimensional features. When is small enough, both PrOBALL-UCB and ProBALL-TS converges to that of LinUCB and Linear Thompson sampling using ground-truth low-dimensional features. This shows that we lose little from needing to estimate the subspace with SOLD when enough offline samples are present.
that the end-to-end regret of
Subspace Estimation Error Against Offline Samples
5
Subspace Error 10/sqrt(N)
4
Frobenius Norm
3
2
1
10
102
103
Offline Samples
Figure 16: Subspace estimation error of SOLD against the number of offline samples, in the Frobenius norm. This was performed on the MovieLens dataset. We compare the error of SOLD against the parametric rate of 1/v 1/VN. This shows that the error of SOLD indeed decreases very quickly in practice.
44

---

Leveraging Offline Data in Linear Latent Contextual Bandits
T 0.01
0.1
T= 0.5
1
120
110
110
110
100
100
100
90
Regret
H-PrOBALL-UCE
90
E-PrOBALL-UCE
80
M-ProBALL-UCB
Ground Truth Suaspece
70
60
60
60
50
10
10
10a
10
102
10a
10
10a
10a
Offline Samples
Offline Samples
Offline Samples
Offline Samples
Figure 17: End-to-end regret 7 200 timesteps of ProBALL-UCB initialized with SOLD, against the number of offline samples used in fitting SOLD. With low enough the regret of ProBALL-UCB approaches the regret of LinUCB on ground-truti truth low-dimensional features, showing that we lose next to nothing from needing to estimate the subspace with SOLD. Shaded area depicts I-standard error confidence intervals over 30 trials with fresh
T 0.01
0.1
0.5
T= 1
350
325
325
300
300
300
275
275
275
Regret
250
250
250
250
225
225
225
H-ProBALL-TS
200
200
200
E-ProBALL-TS
200
M-ProBALL-TS
175
Ground Truth Subapace
175
102
10
Offline Samples
Offline Samples
Offline Samples
Offline Samples
Figure 18: End-to-end regret at 7 = 200 timesteps of ProBALL-TS initialized with SOLD, against the number of offline samples used in fitting SOLD. With low enough the regret of ProBALI--T approaches the regret of TS on ground-truth low-dimensional features, showing that we lose next to nothing from needing to estimate the subspace with SOLD. Shaded area depicts 1-standard error confidence intervals over 30 trials with fresh 6.
45


Reviews:
[{"review_id": "jHkh94ROYW", "reviewer": "Reviewer_iZXM", "summary": "This paper studies the setting of _linear latent contextual bandits_. If you are given multiple trajectory data under some unknown behavior policy, with possibly different latent states for each trajectory, how do you efficiently use it in an online setting? This paper proposes three algorithms and their analysis — an algorithm for estimating the linear subspace for the latent variables, a minimax optimal (under expected regret) online algorithm, and a computationally efficient algorithm that is almost optimal under some settings. Finally, the paper shows the generality of latent bandits by defining a notion of exchangeable and coherent stateless decision processes and showing that every such process is a latent bandit.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your review and your confidence in our paper! We appreciate that you enjoyed our:\n1. Clarity and thoroughness of evidence.\n2. Presentation of intuition and writing quality.\n3. Demonstration of practical utility through experiments.\n4. Generality over existing work in leveraging offline data for bandits.\n5. Technical ideas behind SOLD.\n\nWe acknowledge the typo and will address it in the camera ready version!\n\n## Questions\n### Question 1\nLinearity is a standard structural assumption in bandits, and it is not unreasonable that a continuous latent state could have a linear effect on the reward parameters of a bandit instance. This neatly generalizes the tabular assumption that each latent state comes with a specific reward parameter while allowing us to tackle continuous latent states. We demonstrate the practical relevance of this assumption by evaluating our algorithms on real-life MovieLens data.\n\nHowever, we agree that more complex relations between the latent state and reward parameters are possible, and we leave the general function approximation case to future work.\n\n### Question 2\nThis seems to be a misunderstanding in choice of terminology, and we are glad you brought it up. $U_\\star$ is indeed not a square matrix at all! By virtue of our setting, it is a $d_K \\times d_A$ matrix, and so in fact has very skewed dimensions. \n\nBy orthogonal, we simply mean that the columns of $U_\\star$ are orthonormal, not the rows. That is, $U_\\star^\\top U_\\star$ is the $d_A$-dimensional identity matrix, but indeed, $U_\\star U_\\star^\\top$ is almost never the $d_K$-dimensional identity matrix. Naturally, we only rely on the first fact (that $U_\\star^\\top U_\\star = I$) in our proofs, which does hold WLOG. \n\nWe will clarify our language in the camera ready version.\n\n### Question 3\nBy \"permuting labels and rewards together,\" we mean permuting the latent labels so that the reward trajectories assigned to a given label stay together. This is the same as permuting latent states. \n\nWe recognize the confusion this language can create and will clarify by simply saying \"just like in the case of finitely many latent states, observations are not changed by permuting the latent states. That is, observations are not changed by permuting latent trajectory labels while keeping trajectories with the same label together.\"\n\n### Question 4\nThe latent bandit is indeed a special case of an SDP, where the function $\\mathcal{F}_H$ is induced by the latent state random variable $F$. \n\nSpecifically, as we state in the definition of a latent bandit, a latent bandit is an SDP where the function $\\mathcal{F}_H(a_1, \\dots a_H) = Y_1, \\dots Y_H$ for SDPs is defined by drawing $Y_1 \\dots Y_H$ independently conditioned on $F$ according to the distributions $Y_h \\sim F(a_H)$. So, an SDP does not have a latent state $F$, but a latent bandit is a special case of an SDP where the functions $\\mathcal{F}_H$ are induced by the latent state $F$ associated with the latent bandit. \n\nJust to help clarify this point, special cases of a general object can and usually do have extra structure. So, a latent bandit has the extra structure $F$ on top of the SDP functions $\\mathcal{F}_H$ induced by $F$, just like how a linear bandit comes with the extra feature map $\\phi$ and reward parameter $\\beta$ on top of the general bandit reward function $r$ induced by $\\phi$ and $\\beta$.", "claims_and_evidence": "The paper is exceptionally clear and thorough. Almost every claim is convincingly supported. It also does an excellent job conveying the intuition behind the definitions, algorithms and the proofs.", "methods_and_evaluation_criteria": "This is a paper of theoretical nature, but does a great job of demonstrating the practical utility of the proposed algorithms by doing some experiments demonstrating their efficiency against reasonable baselines.", "theoretical_claims": "No, I cannot attest to checking the proofs carefully. I only skimmed some of the proofs in the appendix. However, what I read made sense and it seems the authors have given full proofs of everything.", "experimental_designs_or_analyses": "I checked the appendix detailing the experimental results and they look good to me.", "relation_to_broader_scientific_literature": "The paper studies a more general setting of latent bandits introduced by Hong et al. (2020).", "essential_references_not_discussed": "Nothing comes to mind here.", "other_strengths_and_weaknesses": "As I said before in the review this is a very nicely written piece of work. As a reviewer it is always appreciated to review a paper from which I learn a lot.\n\nI really like the SOLD algorithm. The idea of trajectory splitting is very cool!", "other_comments_or_suggestions": "There is a small typo when defining $\\overline{\\mathbf{D}}_{N,i}$ in the additional notation section.", "questions_for_authors": "1. Why is the map $U_\\star$ assumed linear?\n2. I did not understand the argument why $U_\\star$ can be assumed to be orthogonal without loss of generality. It may not even be a square matrix! A change of basis enforced by $A^{-1}$ does not necessarily makes $U_\\star$ orthogonal.\n3. On line 123, it is stated that \"permuting the labels and rewards\". But $A$ is permuting latent states.\n4. From the discussion in section 8, I am unable to see how a latent bandit is an SDP. The definition of latent bandit has an extra measure-valued function $F$ which an SDP doesn't have.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KFqP4d8WP4", "reviewer": "Reviewer_qrXz", "summary": "In this paper, the authors study the linear latent contextual bandit problem. They consider a setting in which the latent reward vectors lie within a low-dimensional subspace. An offline dataset from tasks whose hidden reward vectors share the same subspace is assumed to be available. They first present an algorithm that estimates the subspace, which is proven to recover the subspace with a bounded error. Then, using the subspace estimation algorithm, they show that, under the assumption that the distribution of latent reward vectors spans the space, the algorithm can provably utilize the offline dataset to achieve a better regret bound. A complementary regret lower bound is then presented to show the near-optimality of the algorithm. As the previous algorithm is not computationally efficient, they present an algorithm that approximates the confidence set with a corresponding regret bound. Finally, experiments on both synthesized and real data are presented to demonstrate the practical performance of their algorithm.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We appreciate that you recognize:\n\n1. The clarity and veracity of our theorems and proofs.\n2. The application of our algorithms to both synthetic and real data.\n3. Our contribution to the problem of leveraging offline data in bandits.\n\nWe address your qualms below. **If our responses have adequately addressed your concerns, we implore you to consider raising your score.**\n\n## Claims and Evidence\n\nWhile we agree there is subtlety in its nature compared to typical purely online bounds, we maintain that our regret bound is optimal. We appreciate the opportunity to clarify this and will include the discussion in the camera-ready appendix.\n\n1. **Disappearance of $\\lambda_\\theta$ and $\\lambda_A$ in the worst-case bound:** As you would agree, minimax lower bounds are worst-case bounds that optimize over “all problem instances.” So, instance-specific parameters like $\\lambda_\\theta$ and $\\lambda_A$ naturally disappear in the worst-case expression. This is standard in lower bounds for bandits. However, it is crucial to carefully choose the space of “all problem instances,” especially in our offline+online setting.\n2. **The insufficient offline coverage case is trivial, we need a more informative lower bound:** The key challenge is in selecting an instance space that yields an informative lower bound.\n\n    a. **Typical and trivial choice of problem-instance space:** In online linear bandits, it’s common to vary all parameters after fixing the dimension and bounding the reward parameter $\\beta$. Applying that here yields a trivial $d_A\\sqrt{T}$ bound, achieved when offline data has insufficient coverage (when offline data \"does not span the whole space,\" as you said). Many algorithms (including ours) attain this, showing minimax optimality but not any benefit over Lin-UCB.\n\n    b. **Our more informative choice of problem-instance space:** To demonstrate a real advantage over Lin-UCB, we constrain the instance space further - we fix the offline data quality by assuming $\\lambda_\\theta$ is bounded below. This models scenarios with sufficient offline coverage, and our lower bound shows that even in these non-trivial settings, no algorithm can outperform ours. Further we establish a clear advantage over the $d_A\\sqrt{T}$ bound for Lin-UCB.\n3. **Potential for more instance-dependent lower bounds:** While we analyze worst-case performance over a meaningful class, there’s room for future work on sharper, instance-dependent lower bounds that reflect explicit dependence on both $\\lambda_\\theta$ and $\\lambda_A$. However, we believe that our introduction of a nontrivial lower bound in this hybrid offline+online setting is already a significant step.\n\n## Other Strengths and Weaknesses\n\nIt is unclear what you mean by “better regret bound in general.” You might be comparing to either LOCAL-UCB or Lin-UCB - we address each of the two below:\n1. **ProBALL-UCB vs LOCAL-UCB:** We explicitly state that ProBALL-UCB has weaker guarantees than LOCAL-UCB in general (lines 86 and 303). However, as noted in lines 303–310 and proven in Appendix E.2.1, ProBALL-UCB matches LOCAL-UCB in “good” cases, like when the feature set is an $\\ell_2$ ball, since then $\\phi(x_t, a_t)$ lies in the span of $\\hat{\\mathbf{U}}$. Such an assumption is standard in the literature, including [1] (Yang et al, 2022), which you referenced. We acknowledge not citing Appendix E.2.1 in the main text and will correct that in the camera-ready version.\n2. **ProBALL-UCB vs Lin-UCB:** ProBALL-UCB is better than LinUCB, as we can see from Theorem 4. In fact, ProBALL can improve significantly on Lin-UCB, as we see both from Theorem 4 and the experiments. \n\n## Questions for Authors\n\n### Question 1\nYes, this assumption is essential—due to a key difference between our setting and that of [1] (Yang et al, 2022).\n1. **[1] is purely online:** In [1], the setting is purely online and the learner chooses actions in each of M concurrent bandit instances. This allows for coordinated exploration across tasks.\n2. **Our “multi-task” dataset is collected offline:** We work with an offline dataset of trajectories spanning multiple bandit instances. The learner has no control over the behavior policy that collected the data. Without structural assumptions on the dataset, estimating a useful subspace becomes infeasible, and regret degenerates to the standard $d_A\\sqrt{T}$.\n\nCoverage assumptions similar to ours are commonplace within the offline linear MDP literature, like in [2,3], and they all take the form of concentrability-type assumptions [4] within the broader offline RL literature proper. \n\n## Refs\n1. Yang et al. (2022), Nearly Minimax Algorithms for Linear Bandits with Shared Representation\n2. Jin et al. (2021), Is Pessimism Provably Efficient for Offline RL?\n3. Duan et al. (2020), Minimax-optimal off-policy evaluation with linear function approximation\n4. Zhan et al. (2022), Offline Reinforcement Learning with Realizability and Single-policy Concentrability", "claims_and_evidence": "The major problem is that the regret bound presented in Theorem 2 is not minimax optimal, as the regret upper bound depends on the coverage factors $\\lambda_\\theta$ and $\\lambda_A$. In contrast, the lower bound presented in Theorem 3 has no dependency on either $\\lambda_\\theta$ or $\\lambda_A$. As a result, in the case where the feature vector or the hidden latent reward vector does not span the whole space, the algorithm is not minimax optimal and has no advantage compared to the vanilla LinUCB algorithm for contextual bandits.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "All the claims are clear and proved.", "experimental_designs_or_analyses": "They apply their algorithm to both synthesized and real data.", "relation_to_broader_scientific_literature": "This paper extends the understanding of leveraging offline data in bandits problem, showing that the offline data can provably improve the performance of the algorithm.", "essential_references_not_discussed": "They have cited all relevant papers to my knowledge.", "other_strengths_and_weaknesses": "Although ProBALL-UCB is presented as an approximation of the LOCAL-UCB algorithm to ensure computational efficiency and has been shown to leverage offline data in experiments, it is not provably established that the algorithm achieves a better regret bound in general. Specifically, since $\\hat{U}$ is determined by the algorithm routine, it is unclear in which situations $\\phi(x_t, a_t)$ lies in the span of $\\hat{U}$. It would be valuable to formally establish the cases in which ProBALL-UCB can effectively leverage offline data.", "other_comments_or_suggestions": "See above", "questions_for_authors": "- Do you think the data coverage assumption (i.e., Assumption 2) is necessary? In comparison, it has been shown that in multi-task linear bandits, this assumption is not required to obtain a provably improved regret bound by leveraging data from other tasks (see, e.g., Yang et al., 2022).  \n\nYang, Jiaqi, et al. \"Nearly minimax algorithms for linear bandits with shared representation.\" arXiv preprint arXiv:2203.15664 (2022).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lstzkPL2Cg", "reviewer": "Reviewer_D3RP", "summary": "This paper explores linear latent contextual bandit problems and how offline data can be used to speed up online learning. The authors introduce an offline algorithm that learns a low-dimensional latent subspace with provable guarantees. Building on this, they propose an online algorithm that achieves minimax-optimal regret, meaning its performance is as good as theoretically possible. They also present a more practical version of this algorithm that is computationally efficient but comes with a slightly weaker guarantee. Empirical results further support their theoretical findings, demonstrating the effectiveness of their approach.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and confidence in our paper! We are grateful for your appreciation of:\n1. The clarity of our claims and the strength of the theoretical and empirical support for them.\n2. The expansion of the scope of linear bandits to include latent states and hybrid offline-online learning.\n3. The novelty of our algorithms.\n4. The thorough coverage of literature in our related work section. \n5. The strengthening of the paper due to the lower bound analysis and the empirical results.\n\nWe address your qualms below. **If our responses have adequately addressed your concerns, we would be delighted if you would consider raising your score.**\n\n## Methods and Evaluation Criteria\n\nWe are grateful for your appreciation of our proposed method and our heuristic for estimating $d_K$. We do in fact perform experiments for estimating $d_K$ in the Appendix, and we thank you for allowing us to reiterate our experiments involving this principled estimation method below.\n\n1. **In practice, we don’t need to know $d_K$:** As you point out, in lines 206-209 (right column), we mention that one can use our theory to derive a principled estimate for $d_K$.\n2. **Experiments estimating $d_K$ in Appendix H.1:** We direct the reviewer to Appendix H.1, where we provide experiments where we determine $d_K$ from offline data within the MovieLens experiments. \n3. **Effect of $d_K$ estimation on downstream regret:** For your satisfaction, we also discuss the effect on downstream regret here. Overestimating $d_K$ is not a huge issue, as this simply leads to a slightly larger confidence set. Underestimating $d_K$, on the other hand, can lead to the learning of a misspecified subspace, and the regret bound then degenerates into the $d_A\\sqrt{T}$ bound.\n\nWe apologize for not explicitly mentioning appendix H.1 in the experiments section and will do so in the camera-ready version.\n\n## Experimental Designs Or Analyses\n\nWe appreciate your concern about the practical applicability of ProBALL-UCB, but we want to point out that we discuss in the paper how the experimental observations are consistent with our expectations and highlight the superiority of ProBALL-UCB over Lin-UCB. \n\n1. As we discuss in lines 290-297 (left column) of the paper as well as show in the algorithm for ProBALL-UCB, ProBALL-UCB switches to standard Lin-UCB after a certain threshold is reached. \n2. As we discuss in lines 366-368 (left column), the kinks or “rapid increases” that we see in Figure 2 correspond to switching to Lin-UCB once the aforementioned threshold is reached.\n3. This means that the growths of these graphs after the rapid increases are _identical_ to Lin-UCB, not greater or lesser. An example of this can be found in Appendix H.2, Figure 5, in the right-most subfigure labeled $\\tau=10$. Within this subfigure, ProBALL-UCB switches over to Lin-UCB earlier than in the illustration in Figure 2, with a similar initially steeper slope, but the regret of ProBALL-UCB is never worse than that of Lin-UCB.\n\nSo, the warm-start provided by ProBALL-UCB makes it superior to vanilla Lin-UCB, and ProBALL-UCB is at least as good as Lin-UCB after the \"rapid increase.\"\n\n## Questions for Authors\n### Question 1\nIndeed, as we mention in line 131 (left column) as well as in other parts of the paper, the offline data comes from multiple latent states. In fact, as encapsulated in Assumption 2, there have to be enough latent states in the offline data to cover the low-rank latent subspace.\n### Question 2\nYes, it does, as we clarify conceptually in our response to your qualm under “Experimental Designs or Analyses” above.\n### Question 3\nAs clarified in our response to your qualm under “Methods and Evaluation Criteria” above, we do in fact do so in Appendix H.1. We apologize for not mentioning this in the main paper, and we will do so in the camera-ready version.", "claims_and_evidence": "The overall claims in the paper are clear and well-supported by both theoretical analysis and empirical results.", "methods_and_evaluation_criteria": "Overall, the  proposed methods make sense for the problem setting. However, one concern is that they assume the proposed algorithm (including in the empirical results) knows $d_K$, which is often difficult to determine in practice. The authors mention that $d_K$ can be estimated heuristically, but the empirical results do not include any experiments where $d_K$ is estimated rather than given. Including such results would have strengthened the evaluation and provided a clearer understanding of the method’s practical applicability.", "theoretical_claims": "The theoretical claims are strong and well-reasoned. While I didn’t go through every detail of the proofs, they seem correct.", "experimental_designs_or_analyses": "In Figure 2, the first plot (Simulation Study) shows that the regret curves of the proposed algorithm increase rapidly at certain points, with a noticeably steep slope. In particular, the red line has a steeper incline than LinUCB. This raises concerns about the practical effectiveness of the proposed methods for larger timesteps, as it is unclear whether they consistently outperform LinUCB in the long run.", "relation_to_broader_scientific_literature": "This paper expands the scope of linear bandits by incorporating latent states and hybrid offline-online learning settings. It introduces novel algorithms that leverage offline data to accelerate online decision-making while accounting for latent structures in user behavior or environments.", "essential_references_not_discussed": "I think the paper covers the related work quite thoroughly.", "other_strengths_and_weaknesses": "The lower bound analysis and empirical results clearly strengthen the paper, demonstrating both theoretical optimality and practical effectiveness of the proposed methods.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "1. Is the offline data generated from multiple different latent states, rather than just from the latent state $\\theta^\\star$? If so, could you explain this in more detail?\n\n2. In the \"simulation study\" experiment, does your proposed algorithm outperform LinUCB when the number of timesteps is sufficiently large?\n\n3. In the experiments, what happens if we estimate $d_K$ from the data instead of assuming it's known?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BWwTCwXLyy", "reviewer": "Reviewer_EkCv", "summary": "This paper introduces a linear version of latent bandit models, where the reward for user u and action a of feature $\\phi_{u,a}$ at step t is $Y_{u,a} = \\phi_{u,a}U\\theta+\\varepsilon_t$ where $\\varepsilon_t$ is an iid subgaussian noise, U an unitary matrix and $\\theta$ a low-dimensional latent vector. U and $\\theta$ are unknown. Moreover, the authors assume the access to a prior offline set of N short trajectories to speed up online learning. The goal is to minimize the cumulative regret at fixed horizon T.\nFirst, an offline algorithm called SOLD is introduced to learn a confidence set and an estimator of the latent subspace by estimating the matrix $UU^ T$ on the offline data. Second, a LinUB-inspired algorithm named LOCAL-UCB is proposed and uses arm indices leveraging the confidence set learned on the offline data and the iteratively updated confidence set on online data to get lower-bound matching guarantees on the regret, at the cost of computational tractability. Eventually, another online algorithm named ProBALL-UCB avoids solving the difficult optimization problem in LOCAL-UCB at the price of no longer matching regret upper bounds.\nExperimental results are provided on several baselines and synthetic and real-life data sets.\n\n## update after rebuttal\nAll my questions have been answered and I keep my very positive score on this paper.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful to the reviewer for their kind and constructive comments. We are excited to hear that the reviewer highlights so many strengths of our work, including:\n1. The strength of our theoretical contributions.\n2. Our problem formulation.\n3. Our novel and interesting algorithmic contributions.\n4. The writing of the paper.\n5. The reproducibility of our code (thank you for looking through the code!). \n6. The robustness of our empirical results.\n\nAgain, we appreciate your thorough review, and address your comments below.\n\n## Essential References Not Discussed\nWe were indeed not aware of the lower bound in [1] (Pal et al, 2023). As the reviewer remarks, there is a subtlety since this is also a purely online setting unlike our hybrid offline-online setting, although it relies on an offline matrix completion oracle. Nevertheless, we agree that this paper is relevant to ours and a remark should be added within our paper addressing it. We thank the reviewer for bringing this to our attention. \n\n## Other Strengths and Weaknesses\nNote that in the second plot of Figure 2, LinUCB performs better than the algorithms mUCB and mmUCB from [2] (Hong et al, 2020), the same as H-ProBALL-UCB, and worse than E-ProBALL-UCB and M-ProBALL-UCB.\n1. **Why LinUCB is better than mUCB and mmUCB:** The outperformance over mUCB and mmUCB makes sense, since these two algorithms only work with standard multi-arm bandits with finitely many latent states without a linear structure. LinUCB can leverage an approximately linear structure in the MovieLens data by working in a linear bandit setting. We know that given K arms in a linear bandit, standard UCB algorithms have Ksqrt{T} regret, while LinUCB has d\\sqrt{T} regret, which can be lower if $d<K$. It is certainly still a bit surprising that even using offline data in mUCB and mmUCB is not enough to outperform LinUCB - a purely online algorithm that simply leverages a potential linear structure in rewards.\n2. **Why LinUCB performs the same as H-ProBALL-UCB:** ProBALL-UCB performs best when we achieve tight subspace concentration in constructing our subspace confidence sets. Specifically, given loose confidence sets, ProBALL-UCB switches to LinUCB very early on. As the Hoeffding (H) confidence sets are not as tight as the empirical Bernstein (E) and martingale Bernstein (M) confidence sets, the performance of H-ProBALL-UCB accordingly is similar to that of LinUCB. \n3. **Why LinUCB is worse than E-ProBALL-UCB and M-ProBALL-UCB:** As we mention above, ProBALL-UCB is able to leverage offline data better when we use tight subspace concentration bounds in constructing our subspace confidence sets. The empirical Bernstein (E) and martingale Bernstein (M) confidence sets are much tighter than Hoeffding confidence sets. So, ProBALL-UCB is able to work in the learnt low-dimensional subspace for long enough before having to switch to LinUCB.\n\n## Refs\n1. Pal et al, 2023. Optimal algorithms for latent bandits with cluster structure.\n2. Hong et al, 2020. Latent Bandits Revisited.", "claims_and_evidence": "To me, all claims (regret bounds, empirical results, conditions for stateless decision processes being a latent bandit) are backed by convincing evidence.", "methods_and_evaluation_criteria": "Experiments are performed both on synthetic and real-life data sets relevant to the recommendation task. The selected baselines (LinUCB for linear bandits without relying on offline, mTS and mUCB for latent bandits without the linear structure, different concentration bounds and hyperparameter values for ProBALL-UCB) are relevant.", "theoretical_claims": "I did not check the proofs in Appendix.", "experimental_designs_or_analyses": "See Methods and Evaluation Criteria.", "relation_to_broader_scientific_literature": "The idea of splitting trajectories to learn the latent subspace in the SOLD algorithm comes from a prior work [1]. Linearity is a popular structure in the bandit literature [2] and latent bandits with optimism have been investigated since at least 2014 [3].\n\n[1]  Kausik, C., Tan, K., & Tewari, A. (2023, July). Learning mixtures of markov chains and mdps. In International Conference on Machine Learning (pp. 15970-16017). PMLR.\n\n[2] Li, L., Chu, W., Langford, J., & Schapire, R. E. (2010, April). A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web (pp. 661-670).\n\n[3] Maillard, O. A., & Mannor, S. (2014, January). Latent Bandits. In International Conference on Machine Learning (pp. 136-144). PMLR.", "essential_references_not_discussed": "Lines 81-82 on page 2: “To the best of our knowledge, this is the first lower bound in a hybrid (offline-online) sequential decision-making setting”: a paper from 2023 [1] gives lower bounds on the cumulative regret for a structure type of latent bandits (with hidden clusters) where their algorithmic contribution leverages an offline matrix completion oracle during online learning. It is not exactly the same “hybrid” setting with offline collected trajectories and their lower bound does not take into account offline information, but, as it is a very similar setting, I would advise discussing (shortly) this paper and rephrasing the quoted sentence. \n\n[1] Pal, S., Suggala, A. S., Shanmugam, K., & Jain, P. (2023, April). Optimal algorithms for latent bandits with cluster structure. In International Conference on Artificial Intelligence and Statistics (pp. 7540-7577). PMLR.", "other_strengths_and_weaknesses": "Strengths\n- The theoretical contributions are novel, strong and diverse (conditions for learning unconfounded estimators, regret lower bound, generality of latent bandits).\n- The algorithmic contributions are novel and interesting (latent subspace and confidence set learning from offline data, lower-bound-matching algorithm, tractable counterpart). The latter can be extended to Bayesian approaches to regret minimization.\n- The empirical results seem robust with an acceptable number of iterations (30), provide variations on hyperparameter values, and clearly show an improvement over the state-of-the-art in related settings, as the linear latent bandit was first introduced in this paper.\n- The problem of cumulative regret minimization in structured latent bandits makes sense.\n- The paper is well-written.\n- The code is available, reusable (presence of a specific Python module) and reproducible (presence of notebooks for each data set).\n\nWeaknesses\n- I am surprised that LinUCB performs that well in Figure 2, second plot, as it does not rely on offline data. Could you explain this?", "other_comments_or_suggestions": "None.", "questions_for_authors": "See Weaknesses. This is a minor concern to me.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes two contextual bandit algorithms for latent bandits. Both algorithms have the following structure: estimate the latent subspace offline from previously logged data and then act with respect to it online. The first algorithm is impractical but has a lower regret. The second algorithm is practical but has a higher regret. Both algorithms are analyzed and the practical one is also empirically evaluated. The initial scores of the paper were 2x Strong Accept, Accept, and Weak Reject, which reflects its quality. Congratulations! Please take the feedback of the reviewers into account when updating the paper.
Decision: Accept (poster)