Provably Efficient Multi-Task Meta Bandit Learning via Shared Representations
Authors: Jiabin Lin
Shana Moothedath
Venue: NeurIPS 2025 poster ()
Keywords: Meta learning
Multi-task learning
Linear bandits
Low dimensional learning
Representation learning
Primary area: general_machine_learning
TL;DR: We study meta-learning in linear bandits and provide provably fast, sample-efficient algorithms to learn a common set of features from multiple related bandit tasks and to transfer this knowledge to new, unseen bandit tasks.

Abstract: Learning-to-learn or meta-learning focuses on developing algorithms that leverage prior experience to quickly acquire new skills or adapt to novel environments. A crucial component of meta-learning is representation learning, which aims to construct data representations capable of transferring knowledge across multiple tasks—a critical advantage in data-scarce settings. We study how representation learning can improve the efficiency of bandit problems. We consider $T$ $d$-dimensional linear bandits that share a common low-dimensional linear representation. We provide provably fast, sample-efficient algorithms to address the two key problems in meta-learning: (1) learning a common set of features from multiple related bandit tasks and (2) transferring this knowledge to new, unseen bandit tasks. We validated the theoretical results through numerical experiments using real-world and synthetic datasets, comparing them against benchmark algorithms.

Provably Efficient Multi-Task Meta Bandit Learning via Shared Representations
Jiabin Lin and Shana Moothedath
Department of Electrical and Computer Engineering Iowa State University edu, mshama@iastate.ede
Abstract
Learning-to-ler to-learn meta-learning focuses on developing algorithms that leverage prior experience to quickly acquire new skills or adapt to novel environments. A cru- cial component meta-learning representation learning, which aims to construct data representations capable of transferring knowledge across multiple tasks-a critical advantage data-scarce settings. We study how representation learning can improve the efficiency of bandit problems. We consider T d-dimensional linear bandits that share a common low-dimensional linear representation. We provide provably fast, sample-efficient algorithms to address the two key problems in meta-learning: (1) learning a common set features from multiple related bandit tasks and (2) transferring this knowledge new, unseen bandit tasks. We validated the theoretical results through numerical experiments using real-world and synthetic datasets, comparing them against benchmark algorithms.
Introduction
The ability transfer knowledge across tasks is essential for robust and sample-efficient inference and prediction []] Developing methods that can learn task representations capable generalizing to unseen tasks has become increasingly critical in diverse applications, including deep reinforcement
learning (2), bandit learning 3 4 and natural language processing [5] 6 Despite considerable
advancements in transfer learning, the theoretical foundations of the underlying problem remain underdeveloped. Transfer learning for sequential decision-making problems still in its early stages, requiring further exploration address key gaps in understanding.
Meta-learning involves addressing two key challenges: (1) the upstream problem, which focuses learning shared model representation across set of source tasks to capture transferable knowledge, and (2) the downstream problem, which leverages this shared model to enable efficient adaptation and learning for new target task, often under data-scarce conditions. This paper addresses these challenges in linear bandit problems by proposing a unified framework that learns robust transferable representations and ensures efficient adaptation data-scarce larget tasks.
Recently, a number of emerging works [7111 investigated representation learning for bandits (upstream) and showed that if all tasks share joint low-rank representation, then by leveraging such a joint representation, is possible to learn faster than treating each task independently. The underlying idea is that since the tasks related, we can efficiently extract shared low-dimensional representation (feature extractor) and then apply a simple function-ofter a linear one- on top of this embedding [4] Learning shared representations is inherently non-convex. While existing works have shown the benefits of representation learning, theoretical analyses often rely on convex relaxations and assume access to the optimal solution of the non-convex objective [7 Moreover, the transferability of learned representations to new target tasks remains underexplored 9
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this paper, we focus on ensuring a desired level of accuracy for the learned representation trained on source bandit tasks with tight sample complexity while also proposing an approach that leverages this learned model to effectively handle new, unseen target bandit tasks. To learn the shared model, we introduce an sxplore-thenccomit algorithm. We propose an Optimism in the Face of Uncertainty Learning (OFUL) algorithm designed to transfer the learned representation to unseen target tasks and provide a tight regret guarantee to address this gap. We also provide sample complexity bound of the target task for a meta-learned linear regression. Our contributions in this paper are fourfold.
1. We formulate the meta- meta-learning problem for multi task representation learning in linear bandits, where tasks share oow-iimesiional (rank-r) representation, with the reward parameter for task t E IT + I1. 02 = B wt 0f E Rd and B' E Rdxr. Our objectives are twofold: (i) efficiently estimate the shared model B* from the T source tasks under tight regret and sample complexity guarantees (upstream problem) and (ii) develop an approach to transfer the learned model to (T +++17 1)th unseen target task with limited data (downstream problem).
2. We propose an Explore-then-Comee approach utilizes a careful spectral initialization followed by solving T individual least-squares problems to estimate the reward parameters, avoiding relaxation of the non-convex problem. We prove that the EtC algorithm estimates the shared representation and reward parameters within O(vr/T) We provide the regret guarantee for the source tasks and the sample complexity bounds.
(EIC) algorithm to solve the upstream problem. Our
To transfer the learned model to a new task, we propose two approaches: (1) an OFUL algorithm that constructs a confidence set for the target task parameter 0+ by leveraging the shared repre- sentation estimate B learned from the source tasks. We provide highhprobabillity guarantees that 87+1 lies within the confidence set and establish a tight regret bound of Ö(vrdN) for the target task, for N rounds. This represents significant improvement over the standard bound of Odd N) by leveraging the shared model as r < d. (2) A linear regression estimator that learns from target task data using B estimate. We present the sample complexity of meta-learned linear regression and show that it achieves significant sample reduction.
We evaluated the performance of our approach using synthetic datasets and real-world recom- mender datasets, Movielens and LastFM. We compared our approach against two benchmark methods: (i) a naive algorithm that solves tasks independently, and (ii) the Method-offMoment (MoM) estima- tor in I1 8 15). Our proposed approach consistently outperforms both benchmarks.
2 Related Work
Representation learning aims learning a shared representation among various 'related yet different' tasks. Since the tasks are related, we can more efficiently extract common information rather than treating each task independently [4 16). Multi-task representation learning has been widely studied in the supervised learning context in both empirical applications [5] 17 and theoretical studies (T) [2 14, 15 20 21). These works primarily address statistical rates and do not address the exploration challenges inherent in bandit learning scenarios. Linear bandits are among the most well-studied bandit models, with prominent applications in areas such as recommender systems Recently, representation learning for linear bandits has garnered significant attention, as leveraging task dependencies enables achieving lower regret bounds compared addressing each task independently 17:00 27 28). A significant advantage of representation learning is its ability to transfer learned representations to new, unseen tasks, thereby accelerating the learning process even
(2 26).
under data-sparing settings, which is not explored in the existing literature 7 B 10 28].
Solving multi- task linear bandits with shared representations is inherently non-convex estimation problem. Previous works 77 8 assumed that the optimal solution to a nonconvex cost function is known. This assumption is used in Lemma 2 in 8 and Lemma 1 in 7 derive the initial results for regret analysis. These works primarily focused on regret guarantees under the assumption of known optimal estimator to validate the effectiveness of learning representations. [10] considered a convex relaxation of the problem through trace- regularization (Algorithm 1). The solution to the relaxed problem may not necessarily correspond to a valid solution to the original problem.
28 proposed an alternating gradient descent and minimization algorithm for estimating the unknown reward matrix without relaxing the non-convex cost function. The episodic algorithm relies on independent and identically distributed (i.id.) data in both exploration and commit phases, which becomes restrictive

---

specifically during the commit episodes where actions are chosen greedily. Another related line of work includes low-rank bilinear bandits [1] and generalized linear bandits [32], which consider a single bandit setting where the reward parameter is modeled as a low-rank matrix. The single-handit
setting has also been studied in (33, which proposed a kernel-based multi-task contextual bandit framework that leverages similarities among arms to improve reward estimation. However, the theoretical guarantees in [33] rely on the assumption that the task similarity matrix is known priori. In contrast, our paper presents meta-learning framework for multi-task representation learning in linear bandits, where multiple distinct tasks share a low-rank representation. Notably, our approach learns the shared representation from the source tasks and utilizes this learned structure to facilitate effective adaptation to a new, unseen target task in data-scarce settings.
Building on these works, our goal is to develop a provable approach with regret and estimation guarantees for multi-task representation learning and for both source and target tasks. Our main focus is on the transferability of the learned model to unseen target task in a data-scarce setting. Meta- learning for sequential decision-makinn maaiing problems has recently gained popularity [4 Recently 44 studied transfer learning in linear bandit using shared representations, under the ellipsoid action set assumption. Sparse structures are employed for feature learning to accelerate the learning process in [45488) We present additional related work in Appendix !| To the best of our knowledge, this is the first work that addressed multi-task meta bandit learning using shared representations.
3 Problem Formulation
Notations: For positive integer n, the set [nz] denotes {1, .......... For vector x. ||=r|| represents the f2 norm and [o]] indicates the element-wise absolute value. For any matrix A, || A|l denotes the 2-norm and || denotes the Frobenius norm. The symbol T represents the transpose of matrix or vector. The notation J (or sometimes just I) represents the k x k identity matrix, while ex denotes the k-th canonical basis vector. For basis matrices B1 and B2, we define Subspace Distance (SD) as SD(B), B2) == [ - B B2ll. We use w.p. for with probability.
Multi-task representation learning in linear bandits: Let t E [7] be the index of the T source tasks, and index T + 1 denotes the target task. Each task t E [T] addresses a related but distinct linear bandit problem. Let X' C TR. denote the finite action set. In each round n E [N]. every task t [T] independently chooses an action Fint X. The task receives a corresponding reward yo,t from the environment, determined by the unknown but fixed reward function Vn. = =,,,,,; Tn. where 02 is the unknown reward parameter and T/o,t denotes noise. The expected reward is defined as nnt = =T, 02, where rn, = [[ym,,]. We define O := [0i -...] as the reward matrix, which is unknown. Given tasks are related, we can understand the problem that all tasks share a joint representation. Following prior works such as (0 7 (28] 15 91 we consider that there exists an unknown global feature extractor 8 dRd and an underlying prediction parameters w such that 07 = B", for t E [7]. Thus +* is low-rank (rank-r) matrix, where r < min (d, T}.
The goal of upstream learning is to find near-aceurate model for any task t [T] via sufficient ex- ploration under tight sample complexity, and output a well-learned representation for the downstream task. We are also interested in obtaining the regret guarantee for the source tasks given by
T
RNT =
02).
(I)
n=
where v is the optimal action for task in round n. Let Ni denote the exploration horizon in the upstream problem. Thus the representation learning reduces to obtaining the estimates θ = BW
with the goal of minimizing the cost function JB, W)
T
1 Σ
Σ
In - 110,1
(2)
where B E Rax and W E R The cost function in Eq. 22 non-convex, thus challenging to
solve. Let O+ SVD BVEV* = B' B* E Bdxr Σ E Rexr, and V* E R.xT denote (rank r)
singular value decomposition. Thus B* V are basis matrices and W == ΣV* The maximum and minimum singular values of Σ are a o and o respectively, and condition number k = min
3

---

Algorithm 1 Explore-then-Come (EiC) Algorithm for Representation Learning in Linear Bandits
1: Parameters: Total number of rounds, N; Number of rounds for exploration step, N1; Multiplier in specifying for init step, C' = 9n² 2²: 0₂ < 0 for all t E (T)
2: for t,,..,, N2 do
3: For every task & E [T], randomly select action In,t and observe Vn,t.
4: end for
5: Compute YN Wy,,,, ,NN PNy. [Zi,er- " [NN, for E [T]
6: Spectral Initialization
7: Ye,tran(( == YN,, II where C
NiT E Un
8: O = 1 Ei= N V (a)e,
Ni
9: Set B top-r-singular-vecoor of Oo
10: Update Wi, 0,: For each / E [T], set wh + N and set 0, Bü,
11: for N2 +1, do
12: For each task t E [ choose action Ln,t = arg max TE x 0c, and obtain yn.t
13: end for
Transfer learning in linear bandits: In the transfer (downstream) learning setting, the agent is assigned new unseen target task T + 1. Let N2 denote the learning horizon of the target task. During rounds n [N2). the target task selects an action In,T+1 X, and receives reward Un,T+1 = 01 1 + T+. The target task shares the same feature extractor 3 with the source tasks, specifically 07+1 B w+++ The objective of the target task is utilize the common feature extractor learned from the source tasks to more accurately estimate its own parameter 07+1 i.e. minimize the (pseudo) regret of the target task
N2
N2
RNI.TI1
0
Tn,T+1 0f
Other assumptions: We now present the other assumptions used in our theoretical analysis. Assumption 3.1 (Distribution of Feature Vectors and Noise). We assume that for every source task t [T], the feature vector Fn, follows a standard Gaussian distribution. The noise Tn, is assumed to be i.i.d. Gaussian with zero mean and variance o².
Assumption 3.2 (Bounded Norm of Task Parameter). We assume the existence of constants and u, where 0 < / < u such that / < | [|2 < for all t [T].
Assumption implies column-wise incoherence of the true reward matrix el-bbabrrated in Appendix This is critical for interpolating across columns based on localized observations yn., that depend only on individual columns of O Incoherence the ground-truth matrices a key property required for efficient matrix estimation and other sensing problems with sparse measurements [49] 50 and has been used in recent theoretical works on representation learning 15 21
Assumption 3.]
utilized obtaining the estimation guarantees for B using spectral initialization. We note that Assumption 3.1 applies to the source tasks but not to the transfer learning for the target task. Relaxing the Gaussian model on source task features and noise is part of our future work.
4
Multi-Task Representation Learning for Linear Bandits
4.1 Proposed Explore-then-Comme Algorithm
This section introduces our proposed Explore-then- Commmmm (EtC) algorithm for multi-task represen- tation learning in linear bandits. Our algorithm consists of two phases: an exploration phase and a commit phase. During the exploration phase, the algorithm collects data by exploring the action space. The goal is to gather sufficient information, using as few samples as possible, to estimate the shared feature extractor. Based on the knowledge obtained during the exploration phase, the algorithm estimates the unknown parameters and commits to fixed or near-optimal strategy (policy or model) for subsequent decisions. The pseudocode of the algorithm is given in Algorithm [
Exploration and spectral initialization for estimating B, W): In the exploration phase, for each round and task, n [Ni] and [T], actions In,t chosen randomly. After exploration, our

---

proposed algorithm estimates the shared feature extractor and reward parameters θ = BW by minimizing the cost function f(B, W) in Eq. (2) Due to the non-convex nature of f(B, W), implement a spectral initialization to estimate B and subsequently use the least squares estimator to estimate W2 for each task / E [T] separately. Our goal is to use as few samples (exploration rounds) (MoM) estimator in [ does not bound ||@ e- under the
as possible. The Method-of-Momente desired sample complexity. We provide a detailed explanation in Appendix B We also demonstrate the effectiveness of our approach compared to MoM-based approach through simulations. We
address this by borrowing the truncation idea from the phase retrieval literature [49] [51] 28 Spectral
initialization was employed in [28] for initializing the alternating gradient descent and minimization estimator. While we utilize spectral initialize, we do not employ the alternating approach from (28).
Define the data matrices YN,, == 1y1... ,N,,..] and n,, 2 = [21,t) ... .NN..c] for E [7].
Using the proposed spectral initialization, we define as the top-r singular vectors of
6 =
1 Ni.t Y Vetrnaalaee
where Yittune((a) == YN ( and a G constant. Note that the summation includes only those n, t for which yf is not excessively large, ie., not significantly larger than its empirically computed average. This truncation filters out outlier- like measurements, focusing on the remaining values. Theoretically, this transformation converts the summands into sub-Gaussian random variables with lighter tails compared to the untruncated counterparts, enabling us to establish the desired concentration bound. After fixing the estimate B, we perform T' independent least squares to estimate We in Eq. (2 as given below.
EN In=1t=1 Vn Here, Č ====?p>
9k² is
W (D,,, B) YN.,,, for [T]
The estimates for 0 given by 0. Brü Proposition B.1 28 provides guarantees of the subspace distance for spectral initialization: with high probability, we have SD(B, B*) < on, for dg 0.1.
Commit phase: Each task / E [T] uses the estimates 0, - Bü, obtained from the exploration phase to greedily choose actions that maximize the expected reward. We present the guarantees below.
4.2 Main Results and Guarantees of Algorithm 1
We first present bound for the estimation error |ß,; B* || after the exploration phase of Algorithm 1 and then bound the cumulative regret RN.r-
Theorem 4.1. Assume Assumptions 3.1 3.2 hold, and the noise-to-signal ratio NSR &
eT'5
10: Pick a dn < 0.1. If N₁
> C max(log d, logoo,, and N,T > C₁² d
pacto N:
og
then for each task E [T], with probability at least 1 - -dd-10 aad-1..Algoritmn I at the end of exploration achieves
|Bū, B'will < 1.12+ R2r//N, PV F omaxo
The proof of Theorem 4.1 is given in Appendix C Under the stated assumptions and sample complexity requirements for the exploration step, we develop a high-probability upper bound on The total number of source samples needed for the exploration step NiT is inversely
[ - Bd w/ll. B"włll related to óg. Thus to achieve a smaller dy. i.e., a tighter error bound || |BW, B² ||. a larger sample size is required. This highlights the trade-off between sample complexity and estimation accuracy.
Remark 4.2. Our guarantees hold when the noise-to-signal ratio (NSR) is below a threshold that depends on the number of source task samples, reflecting the increasing accuracy of the estimated representation with more data. NSR in low-rank estimation is defined as the ratio of the maximum eigenvalue of [44 T| Σ. B[peH4
T to the minimum nonzero eigenvalue of O- which
is a This definition ensures that we are considering the ratio between the worst-case (largest) To"
noise power in any direction to the smallest signal power in any direction. Thus NSR
aiin
Theorem 4.3. Assume Assumptions 3.1
3.2 hold, and NSR &
eT5 Palaa No
10:11. Pick a de < 0.1.
8 then for any 8 E (0, 1), with probability at If N₁ > C max d, log T,r) and N T 2 Ce de
5

---

Algorithm 2 OFUL-Based Meta Bandit Learning using Shared Representations
1: Set number of rounds for target task, N2; Vo,T+1 XI
2: Perform representation learning using source tasks and estimate B using Algorithm from line
to line 10
3: for n + 1, ,,,,,,,,,,,,, .22 do
4: Construct the confidence ellipsoid 8, Eq
5: Choose the action-estimate pair (#n,T+1, (#n,r+1,00,7-11)
arg max SE,, x T
6: Play action En,T+1 and receive the reward Un,T+1
7: Update Vn,T+1 = Vn-1TT+1 + Fn,T+12,,T+ V,,++ = VV
#n.I+1= = V) Em=1 B am em.I+UUm,T+1 Gn = B+1
8: end for
least 45
6d-10, 4-6-
the cumulative regret of Algorithml ii bounded by
1 N log log mmx
NT
1 1.12+ + KPVNN MrNTlog 8 8
NT log
RNT & 2uT
8
4.3 Proof Sketch (Details in Appendices C and D
Complete proof of Theorem 4.3 is given in Appendix D Using spectral initialization, we have the guarantee for the estimate of the shared model 3 as SD(B, B*) < do, for do < 0.1. The least squares estimate of W is given by
Tr (BT T Ni. &
NN
YNust
(3)
By substituting YN,, 1 B HN,,, where Hn,t m,. mn,e" we rewrite Eq.
w. TT. Bx. B N, HN. B B'wt (B DN,, B BT 2 &N,, BB BBr)
We multiply both sides by B and simplify further to derive
B B B( N. PN B)
BTT H N (BB -) + B TT NN., - TT PN oI
BB B
To bound || [i BB we utilize the Cauchy- Schwarz inequality, Proposition B.1 and Bernstein inequality. To bound the total cumulative regret RN,T bound the cumulative regret from explo- ration phase R. and cumulative regret of commit phase Ry separately and combine these two bounds. To bound each of these terms, we use a combination of Azuma-Hoeffaae Hoeff-no inequality and the bound of | [Bä, w || from Theorem 4.1
Remark 4.4. By Theorem 4.3 the cumulative regret is linear in the number of source tasks T. However, under Assumption
we demonstrate in Appendix A that the ground-truth matrix is incoherent, i.e., its column norms have similar magnitudes. Incoherence is essential since our measurement matrices are column- wise sparse. Utilizing this, have a sublinear regret guarantee, RN, Ö(VrNT). [8] provided lower bound for the cumulative regret under the infinite action set setting. their scenario, the regret during the exploration phase increases linearly with T. This result is based well-conditioned d-dimensional ellipsoids, which cover all directions nicely.
stringent assumption: the action set for all tasks and all steps is the same
Transfer Learning in Bandits using Shared Representations
5.1 Proposed OFUL-Based Meta Bandit Learning Algorithm
This section presents our proposed OFUL meta-learning algorithm for linear bandits, consisting of T source tasks and target task (T'+ + 1). The algorithm consists of two key phases: first, collaboratively learning shared feature extractor B from the T source tasks; and second, leveraging construct and maintain confidence ellipsoid for the target task parameter 0/+1. The pseudocode is provided in

---

Algorithm 2 In this section, we relax Assumption 3.1 which was essential in Section 4 for estimating the feature representation. Here we assume the noise 77,T+15 are independent random variables and || & T., for >>> 0, which is standard assumption in the literature.
Obtain estimate B from source tasks: We first estimate the shared feature B* via exploration of T source tasks followed by spectral initialization described in Section Using the estimate B we construct a confidence set such that with high probability 0j+1 lies in the confidence set.
Construction of the confidence ellipsoid 3n and estimate ör++1 After estimating B from the source tasks, in each round n E [N2], the target task 7 + constructs a confidence ellipsoid (3, that contains the unknown reward parameter 0++1- The target task then computes an optimistic estimate 0x,7+1 - ()) and chooses action In,T+1 arg max x' 0 n,,++ to maximize the reward based on T- Alternatively, the pair (#n,T+1. (x,T+1) ) is chosen as (In,T+1, (n,T+1) arg max DE3, x 0, optimizing the expected reward. We denote the feature vector and reward as
arg m. (maxxex TT))
In Vn,T+1, respectively, We use the data to update the estimated reward parameter 0n 0n and refine the confidence ellipsoid 3n. At each round n E [N2], we perform g² least squares estimation with regularization parameter À > 0 on the data to estimate Wa,7+1 by minimizing
arg min
Σ m==1
11 -m Bwol + NlIw||e.
WER"
1 From the least squares estimate T and the estimate ß from source tasks, we have 0n,T+1
B We define d x d positive definite matrice Vn,T+1 = Al + " 2 Pn and r X positive definite matrice Vn,++1 B Vu B, where $ n,,++ 11,7+1," #n,r+1]. Using the estimate +1, we construct confidence ellipsoid 8,, as in Eq. 4p. One of the main technical contributions this section is the construction of a tighter confidence ellipsoid estimate 07 in the target task. Theorem 5.1 guarantees that with high probability, 0j E f, for all E [Ng]-
5.2 Main Results and Guarantees for OFUL Algorithm
This section presents the main theoretical results for Algorithm 2 We provide guarantees to show that the true reward parameter 0 lies inside the confidence ellipsoid with high probability, well as the upper bound on cumulative regret for the target task with high probability.
Theorem 5.1. Assume Assumptions 3.1 3.2 hold, |10++1lle & S, and the noise-to-signal to-iinaal ratio cT
NSR < -2xto=2 N. 110,112. Pick 8g < 0.1. N, > C max (log d, log r,r) and N,T 2 Cy2 d
og
then for
for any 5 E (0. 1) and n E [N2), for the target task + 1, it is guaranteed with probability at least 1 - 8 21 that 41 1 is contained within the
del dei(Vn, del(A + ((1 +
8n
0 E Rd -10 Oll so/2log
Furthermore, N,T Cp then w.p least 1 1- 22d-10 07 1 is contained within
8h -
D Rd [|0,TT+1 0 Vll & Sovrlog 1 nI2// + (VX+
VÁ
VN 2 N₂
Proof of Theorem is presented in Appendix E Theorem 5.1 proves that, if the sample complexity conditions for the source task are satisfied, the true reward parameter for the target task #7 consistently lies within the built confidence ellipsoid 3, with high probability. Our approach builds upon the concepts introduced in (22), which constructs a confidence ellipsoid for single bandit problem. A comparative analysis shows that the confidence set scales with v in Theorem 2 (22). while our results achieve vr. Since r & d, our approach improves the bound, validating the advantages of transfer learning over the naive approach of independently learning the target task.
7

---

Theorem 5.2. Assume Assumptions 3.1 3.2 hold, |10 & S, and the noise-to-signe ratio cTE NSR < 22 m Ni
10111. If N₂ > C max(log d, log T,r) and N.T > Cy² 122 N2, then for
any 8 (0, wip least 1 2d 10 cumulative regret of Algorithm for target task T + 1
N2I2
+ +VA+ N2I2/A)
VI VN + 2)S
RN < V 2dNN222 log
1+
(g/rlog
σ rlog
8
given in Appendix F Theorem 5.2 shows that the bound on cumulative regret for the target task is ((vdrN2) Applying the method from [22] directly learn the target bandit task will result in an (d N2) regret. Given that < d, our approach provides significant improvement, validating the benefit of transfer learning.
Proof of Theorem 5.2
5.3 Proof Sketch (Details in Appendices E and
Define Vo,T+I Al + & 0.T+IPR,,Te and Vn,T+1 B VT,T+I. where Ln,T+1
[01,T+1, Fn..+ Using spectral initialization, we have SD(B, B*) & 60, for do < 0.1. The least squares estimator with e regularization is given by
nn = 42. (" B) Yn.+H.
By substituting Yn,T+1 Dn, + B wT+1 +1+ + HI,T+I, where Hn, [ T, we derive
#n.I+1 = Vn.t+1 1b a I - AV B B w/
+ B w
B p $ Pn BB BB'
Consider vector Rd. By multiplying both sides by zJ and utilizing the Cauchy-Schwarz inequality, we obtain
1a (On,T+1 0741) & A|I zllv [ [ 07 41 m
[ =1ly- [| D H Hartlly 0.743
0,744 BB Brrr+ +ilt,lll.. 74,
1e (BB 1)0 ||BT zlly , | [T
TT 2n.
By setting = Vn.T+1 (0., 07+1). we bound each term in the above equation. We use linear algebra concepts, similar techniques as in Theorem in (22,, Cauchy-Schwarz inequality, and SD(B, B*) < 5y guarantee from Section to bound [],, - 0/+1llv, r+1" To bound regret RN,T+I, we use combination of Cauchy-Schhae Schwarz inequality and Theorem
Sample Complexity of Meta-Learned Regression: We present meta-learned linear regression model that uses the learned B and then estimates wr+1 from N₂ target samples. We show that the number of target samples required is O (mmax(lo d, log r)) when using the estimate B, which is significant reduction from direct learning (Appendix G
6 Simulations
This section presents the experimental evaluation of our proposed approaches using both synthetic and real-world datasets. We considered two benchmark approaches: (i) a naive approach that independently solves T tasks using the Thompson Sampling (TS) algorithm or the UCB algorithm, and (ii) MoMM-bsed estimator from I & 15). The MoM estimator, introduced in [ for estimating the feature matrix, serves as baseline for our representation learning approach and has also been
utilized in (8] [5]. The MoM estimator estimates the representation matrix / by calculating the top-r singular vectors of the matrix Ô N,T Em "n, The other existing approaches assume convex relaxation technique in their simulations without learning the representation from the non-convex cost function. The naive approach serves as the performance benchmark for solving the tasks independently rather than jointly. In both the representation learning and transfer learning settings, the reward noise T, is sampled from a zero-mean Gaussian distribution with variance 10 10-6 for the representation learning and 10 for the transfer learning. We present some additional experiments, including comparison with the convex relaxation approach in Appendix
8

---

6.1 Datasets
Synthetic data: The B" Rd matrix is generated by orthonormalizing i..d. standard Gaussian matrix, and W E RRxT is generated from an i.i.d. Gaussian distribution. The feature matrices &,,, are generated from the standard Gaussian distribution. We set d 100, T 100, and r = 2, and alter the parameters d. T, and r in the experiments to assess performance. In the transfer learning setting, we utilize d 100, T 200, and r 2. All results are averaged over 100 independent trials. The error bars show standard errors, calculated as standard deviations divided by v100.
We utilized the Movielens- Morceleess-OOKKKaS dataset [52], which contains user ratings for movies. After pre-processing the data through collaborative filtering to address missing values, we created rating matrix R E 12943x1882 and normalized the scores from to 5 by dividing by 5. We applied non-negative matrix factorization (NMF) with a latent factor dimension of vd, resulting in the factorization R = U.M, where U E R va and M E Rvdx1682, We consider each user as a separate task. For every task t, we obtain the feature vector Zn,t E R by computing the outer product of the f-th row of U and a certain column of M. Thus, the true reward parameter for any task t is represented by the vectorized form of the identity matrix L Given that all tasks share common reward parameter, the matrix O' has rank 1. We set parameters as: d = 100, T = 10, and r = 1.
Movielens:
LastEM: The LastEM dataset is from the online music streaming service Last.fm, including data for 1892 users and 17632 artists. We retain only those artists who have been listened to by a minimum of 30 users and only those users who have listened to at least 30 artists. For artists for whom the user has not engaged, we assign a reward of O. We treat the listening count as the reward and subsequently normalize to the interval [0, 1]. yielding reward matrix R E 727115535 Similarly to the Moviclens datasets, we utilize NMF with a latent factor dimension of d, resulting in the factorization R = UM, where U 741xxd and M E Rdx We consider each user as separate task. For every task t, we formulate the feature vector In,t E Id by computing the element-wist product of the t-th row of U and a column of M. The reward parameter for all tasks is specified as a vector of ones in Rd Thus, O' has a rank of 1. We set parameters as: 100, T 10, and r =
6.2 Results and Discussion
We evaluated the performance of our proposed algorithm against two benchmarks: the MoM estimator and a naive TS-based algorithm. Figure Ta presents the cumulative regret plots comparing the three algorithms for synthetic data. Figures Id Ic and If present the cumulative regret plots for our approach after varying the rank, the number of source tasks, and the feature dimension, respectively. The figures indicate that as the dimension d increases, meaning a more complex model, the cumulative regret increases. Conversely, as the number of tasks increases, indicating enhanced collaboration among tasks, the cumulative regret (summed over all tasks) increases; however, per-task cumulative regret decreases, as expected. Our plots show that increasing the number of tasks, enhancing collaboration reduces cumulative regret. In contrast, higher rank leads to an increased cumulative regret, as expected. Figure compares the performance of the proposed algorithm with respect to the benchmark algorithms for the Movielens data. Figure Tc compares the performance using LastFM. In the exploration phase of LastEM, the naive-UCB approach achieves lower regret since it undergoes estimation in every step, whereas the proposed approach incurs regret due to its random exploration phase. However, after initialization, the proposed approach outperforms the naive method by significant margin. Throughout all experiments, our proposed algorithm consistently outperforms the two benchmarks. Appendix H presents additional results.
Representation learning:
Transfer learning:
We evaluated the performance of our proposed approach for a new target task and compared it with the two benchmarks: Naive-UCB: baseline that applies the UCB algorithm 22 directly for the target task without leveraging the source tasks, (ii) MoM-UCB: a variant of our algorithm that substitutes our spectral initialization with the MoM estimator introduced in (I) Figures| Ia [b], and [c present the cumulative regret plots for the target task using synthetic data, the Moviclens dataset, and the LastFM dataset, respectively, comparing the three algorithms. Our proposed algorithm consistently outperforms the two benchmark algorithms in all experiments. The naive approach presents inadequate generalization due to a lack of shared structure, whereas the MoM-based approach underperforms because the estimator cannot recover an effective representation matrix B in limited source data.
9

---

A63
Synthetic
2.
262
Mostelanss:
182
Proposed fimm
Prodosed Algorithm
Pioposed Algortthm
7.0
7.0
1.5
1.5
1.0
1.0
1.0
0.5
0.3
150
Hound,
Round,
Round,
(a)
(b)
(c)
164
Synthetic data. d 100, 100
263
Syntheeic 61bs, d 100,
Syrthetic data) T- 100, r
1.2
1.0
0.8
0.6
0.7
0.0
150
100
200
(d)
(f)
Figure 1: Results representation learning: the plots the y-axis is cumulative regret for tasks, RN.T and
x-axis is round N. Figures Ta [d] [c.. and results for synthetic data for d 100, 7' 100, Ni = 45, and N 200. Figures la Tb and Ic compare our proposed (ErC) algorithm against benchmark approaches (MoM and Naive) for synthetic, Moviclens, and LastFM datasets. Figure Td present plots by varying rank
(2, 1, 6, Figure Iel plots varying the number of source tasks T (40, 50, 60). Figure Mfaureeppreeeeee presents plots varying the feature dimension as (100, 150, 200}. Figures ab 1c present the results Movielens
data and LastEM data, respectively. The parameters are set as 100, T 10, r =1, Nı = 300, N 1000.
375
Proposed Algunitnmn
Proposed Algoritten
Pruposed Algorithm
150
Balre-ICn
Nalve-ICh
1.2
Nalve-UiC
MoM
MEN
125
1.0
50
0.4
25
0.2
Bound.
Round,
Round
(a)
(b)
(c)
Figure 2: Results of transfer learning: Cumulative regret of target task round. Figure 2a for synthetic data for d 100, T 200, r N₁ 100. Figure 2 for Movielens data for 100, 10,
Ni = 1000. Figure for LastEM data 100, T 10, = 1, N1 = 500.
7 Conclusion
This paper studied meta-lcarning of linear representations for linear bandits. We considered the upstream problem, which focuses on learning a shared representation from T source tasks, and the downstream problem, which focuses on transferring the shared model to an unseen target task. We proposed an guarantees with regret and sample complexity bounds. Using the learned representation, we proposed an OFUL algorithm based on confidence ellipsoid to transfer the knowledge from the source tasks to target task. We proved the regret bound for our OFUL approach and sample complexity bound for the meta-learned regression. Finally, we evaluated the performance of our approach using synthetic data sets and two real-world data sets and compared them with benchmark approaches. As part of future work, we aim to relax Assumption 3.1 to accommodate more general feature distributions.
algorithm for the upstream problem and provided convergence
10

---

8 Acknowledgments and Disclosure of Funding
The authors thank the anonymous reviewers and the area chair whose helpful comments and sugges- tions helped improve the paper. This work was supported by the National Science Foundation grant NSF-CAREER 2440455.
References
[1] Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear repre- sentations. In International Conference on Machine Learning, pages 10434-10443, PMLR, 2021.
[2] Alexei Baevski, Sergey Edunov, Yinhan Liu, Luke Zettlemoyer, and Michael Auli. Cloze-driven pretraining of self-attention networks. arXiv preprint arXiv:1903.07785, 2019.
[3] Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. In International Conference on Machine Leurning, pages 1360-1370, PMLR, 2020.
[4] Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Leveraging good representations in linear contextual bandits. In International Conference on Machine Learning, pages 8371-8380. PMLR, 2021.
[5] Rie Kubota Ando, Tong Zhang, and Peter Bartlett. framework for learning predictive structures from multiple tasks and unlabeled data. Journal of machine learning research, 6(1) (11), 2005.
[6] Xiaodong Liu, Pengcheng He, Weizhu Chen, and Jianfeng Gao. Multi-task deep neural networks for natural language understanding. Annual Meeting of the Association for Computational Linguistics, page 4487-4496, 2019.
[7] Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In International Conference on Machine Learning. pages 4349 4358, 2021.
[8] Jiaqi Yang, Wei Hu, Jason D Lee, and Simon S Du. Impact representation learning in linear bandits. The International Conference on Learning Representations (ICLR), 2021.
[9] Leonardo Cella and Massimiliano Pontil. Multi-task and meta-learning with sparse linear bandits. In Uncertainty Artificial Intelligence, pages 1692-1702. PMLR, 2021.
[10] Leonardo Cella, Karim Lounici, Grégoire Pacreau, and Massimiliano Pontil. Multi-task rep- resentation learning with stochastic linear bandits. In International Conference on Artificial Intelligence and Statisties, pages 4822-4847. PMLR, 2023.
[11] Andrea Tirinzoni, Matteo Pirotta, and Alessandro Lazaric. On the complexity of representation learning in contextual linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 7871-7896. PMLR, 2023.
[12] Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-198, 2000.
[13] Rich Caruana. Multitask learning. Machine learning, 28:41-75, 1997.
[14] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81)11-32, 2016.
[15] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In International Conference on Machine Learning, pages 2089-2099. PMLR, 2021.
[16) Yuzhen Qin, Tommaso Menara, Samet Oymak, ShiNung Ching, and Fabio Pasqualetti. Non- stationary representation learning in sequential linear bandits. IEEE Open Journal of Control Systems, 1 1:41 141-56, 2022.
11

---

[17] Jiayi Li, Hongyan Zhang, Liangpei Zhang, Xin Huang, and Lefei Zhang. Joint collaborative representation with multitask learning for hyperspectral image classification. IEEE Transactions on Geoscience and Remote Sensing, 52(9)) -9366, 2014.
[18] Bharath Ramsundar, Steven Kearnes, Patrick Riley, Dale Webster, David Konerding, and Vijay Pande. Massively multitask networks for drug discovery. arXiv preprint arXiv: trXiv:1502.00077 2015.
[19] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8): 1798-1828, 2013.
[20] Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2021.
[21] Kiran Koshy Thckumparampil. Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Statisti- cally and computationally efficient linear meta-representation learning. Advances in Neural Information Processing Systems, 2021.
[22] Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24:2312 2320, 2011.
[23] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-255 2002.
[24] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. Annual Conference on Learning Theory (COLT), 2008
[25] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.
[26] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 208-214, 2011.
[27] Yihan Du, Longbo Huang, and Wen Sun. Multi-task representation learning for pure exploration in linear bandits. In International Conference on Machine Learning, pages 8511-8564. PMLR, 2023.
[28] Jiabin Lin, Shana Moothedath, and Namrata Vaswani. Fast and sample efficient multi-task representation learning in stochastic contextual bandits. In International Conference on Machine Learning, 2024.
[29] Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learning, pages 3163-3172. PMLR, 2019.
[30] Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna, and Robert Nowak. Multi-task repre- sentation learning for pure exploration bilinear bandits. Advances Neural Information Processing Systems,
2023.
[31] Kyoungseok Jang, Kwang-Sune Jun, Se- Young Yun, and Wanmo Kang. Improved regret bounds of bilinear bandits using action space analysis. In International Conference on Machine Learning, pages 4744 4754. PMLR, 2021.
[32] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, pages 460-468. PMLR, 2021.
[33] Aniket Anand Deshmukh, Urun Dogan, and Clay Scott. Multi-task learning for contextual bandits. Advances in Neural Information Processing Systems, 30, 2017.
12

---

[34] Steven Bilaj. Sofien Dhouib, and Setareh Maghsudi. Meta learning in bandits within shared affine subspaces. In International Conference on Artificial Intelligence and Statistics, pages 523-531, PMLR, 2024.
[35] Amit Peleg, Naama Pearl, and Ron Meir. Metalearning linear bandits by prior update. In International Conference on Artificial Intelligence and Statistics, pages 2885-2926. PMLR, 2022.
[36] Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(7), 2009.
[37] Alessandro Lazaric and Marcello Restelli. Transfer from multiple mdps. Advances in Neural Information Processing Systems, 24, 2011.
[38] Andrei Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distillation. arXiv preprint arXiv: 1511005511 2015.
[39] Emilio Parisotto, Jimmy Lei Ba, and Ruslan Salakhutdinov. Actor-mimic: Deep multitask and transfer reinforcement learning. International Conference on Learning Representations, 2016.
[40] Irina Higgins, Arka Pal, Andrei Rusu, Loic Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, and Alexander Lerchner. Darla: Improving zero-shot transfer in reinforcement learning. In International Conference on Machine Learning, pages 1480-1490. PMLR, 2017.
[41] Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable represen- tation learning for imitation learning via bi-level optimization. In International Conference Machine Learning, pages 367-376. PMLR, 2020.
[42] Branislav Kveton, Martin Mladenov, Chih-Wei Hsu, Manzil Zaheer, Csaba Szepesvari, and Craig Boutilier. Differentiable meta-learning in contextual bandits. CoRR, abs/2006.05094 2020.
[43] Craig Boutilier, Chih-War Hsu, Branislav Kveton, Martin Mladenov, Csaba Szepesvari, and Manzil Zaheer. Differentiable meta-learning of bandit policies. Neural Information Processing Systems (NeurIPS), 2020.
[44] Thang Duong, Zhi Wang, and Chicheng Zhang. Beyond task diversity: provable representation transfer for sequential multitask linear bandits. Advances in Neural Information Processing Systems, 37:37791-38822. 2024.
[45] Yasin Abbasi Aobasi-Yadkori, David Pal, and Csaba Szepesvari. Online-to-confidnncess conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9. PMLR, 2012.
[46] Aditya Gopalan, Odalric-Ambrym Maillard, and Mohammadi Zaki. Low-rank bandits with latent mixtures. arXiv preprint arXiv:1609.011 2016.
[47] Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. Advances in Neural Information Processing Systems, 32, 2019.
[48] Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-294, 2020.
[49] E. J. Candes and B. Recht. Exact matrix completion via convex optimization. Found. of Comput. Math, (9):7777772, 2008.
[50] Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions Signal Processing, 67(20):5239-528 2019.
[51] Seyedehsara Nayer, Praneeth Narayanamurthy, and Namrata Vaswani. Provable low rank phase retrieval. IEEE Transactions Information Theory, 66(9):5875-5903 2020.
13

---

[52] F Maxweel Harper and Joseph A Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (TIIS), 5(4):1-19, 2015.
[53] Roman Vershynin. Hligh-dimensional probability: An introduction with applications data science, volume 47. Cambridge university press, 2018.
[54] Seyedehsara Nayer and Namrata Vaswani. Fast and sample-efficient federated low rank matrix recovery from column-wise linear and quadratic projections. IEEE Transactions on Information Theory, 69(2):1177-12022 2022.
[55] Carlo D' D'Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Sharing knowledge in multi-task deep reinforcement learning, International Conference on Learning Representations, 2020.
[56] Lydia T Liu, Urun Dogan, and Katja Hofmann. Decoding multitask DQN the world of minecraft. In The 13th European Workshop on Reinforcement Learning (EWRL), volume 2016, 2016.
[57] Yee Teh, Victor Bapst, Wojeiech M Czameekk,, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning, Advances in Neural Information Processing Systems, 30, 2017.
[58] Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado Van Hasselt. Multi-task deep reinforcement learning with popart. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3796-3803, 2019.
[59] Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. Uncertainty in Artificial Intelligence (UAI), 2013.
[60] Yuan Cheng, Songtao Feng, Jing Yang. Hong Zhang, and Yingbin Liang. Provable benefit of multitask representation learning in reinforcement learning. Advances in Neural Information Processing Systems, 35:31741-31754, 2022.
[61] Shagun Sodhani, Amy Zhang, and Joelle Pineau. Multi-task reinforcement learning with context- based representations. In International Conference Machine Learning, pages 9767-9779. PMLR, 2021.
[62] Rui Lu, Gao Huang. and Simon S Du. On the power of multitask representation learning in linear MDP. arXiv preprint arXiv:2106.00055 08053, 2021.
[63] Sahin Lale, Kamyar Azizzadenesheli, Anima Anandkumar, and Babak Hassibi. Stochastic linear bandits with hidden low rank structure. arXiv preprint arXiv: arXiv:/901.10 1901.09490, 2019.
[64] Branislav Kveton, Csaba Szepesvári, Anup Rao, Zheng Wen, Yasin Abbasi- Yadkori, and Muthukrishnan. Stochastic low-rank bandits. arXiv preprint arXiv:1712.04644 2017.
[65] Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna, and Robert Nowak. Multi-task repre- sentation learning for pure exploration in bilinear bandits. Advances in Neural Information Processing Systems, 36, 2024.
14

---

A Preliminaries
We present concentration inequalities that used in analysis in this paper.
Proposition A.1 "Azuma-Hoeffüde Inequality), Let {M, : 0, 2, 3....} } be a martingale and [, 11 Q2 almost surely. Then for all positive integers and all positive reals
b²
P| -Mol 3 bj
& exp
2 ² Φ
Proposition A.2 (Theorem 2.8.1, (53). Let Xy. N be independent, mean zero, sub-exponential random variables. Then, for every g 32 O, we have
g² Σ [X max, [
P E
x
exp
-emin
where C is an absolute constant.
Definition A.3. (Incoherence) A rank-r matrix M E R2ch xd2 is defined as j-column-wise incoherent
if for every column E Ri of M, (ax [|mall & MV / [|M where μ > is a constant that remains invariant with respect to d1, d2, According to Assumption
3.2 it follows that
||
1 R VTL.
Also, the Frobenius norm of W satisfies
||"
Σ (W+) Viomaxx
Thus, by defining μ = 1, the norm of the task parameter satisfies
TTI u VT
| 2l2 < u
7 max - IV - max-
T
As stated in Definition A.3 the matrix W is p-column- wise incoherent.
Definition A.4. For the purpose of simplification in the demonstration, we define the matrices and vectors as follows:
$ nnt ( In.e]
Yn,t W1, .. yn and
Hn, ( mn.
B Spectral Initialization vs. MoM Estimator
Spectral Initialization:
Learning the shared model inherently non-convex problem. In this work.
we propose a solution to estimate the unknown reward matrix @ by addressing the non-convex optimization problem via spectral initialization approach.
The standard approach used for initializing iterative algorithms for low-rank matrix estimation is to compute the top left singular vectors of the matrix
1
fo.full
$
T N..1
YN....... NN YN..T)
N₁
T N:
1
ΣΣ
en,
N
t= pm
15

---

Note that E f/oo @ To demonstrate the effectiveness of this initialization approach, sin- theorem, such as Davis-Kahan or Wedin, is typically employed bound SD(B", B) in terms of quantities dependent on θo. - e Therefore, the first requirement is to establish a bound for fu, We note that, the summands of 6o, and hence of @u, -",, are sub-exponential r.V.S. These can be bounded using the aub-enpnnential Bernstein inequality Proposition [A.2 This requires to bound the maximum sub-exponential norm of any summand, say we denote it as Km- For our summands, we can only guarantee Kn, & (1/N) max, ||0; lI & (I/N))) o max This is not small enough, i.c., the summands are not nice enough sub-exponentials: It will require N,T =
(d + TTryT which is too large. To show that f1 < co with high probability under the desired sample complexity, need Km be of order (r/T) smaller. To achieve this we propose a truncation strategy, referred to as spectral initialization 28 54
Spectral initialization estimates the common feature extractor / based on the data gathered from different tasks. Unlike the MoM approach described in Algorithm of (1. our approach uses truncation strategy guarantee that the norm || θ² is bounded within the desired sample complexity. We define as the top-r singular vectors of
T
T No. V Ya)r
ā where (a.rrne(()) == NN. o (I and a = N.T E vh We present the pseu- docode of the spectral initialization approach below.
We have the following guarantee from (28 for spectral initialization in linear contextual multi-task provides an error guarantee for the subspace distance between the estimated feature extractor B, obtained through spectral initialization, and the true feature extractor B*.
bandits. Proposition B.I Propositionn.IIprrovve
Proposition B.1 (Theorem 5.1, (2)). Assume that the noise-to-signal ratio NSR &
|0 Pick a by < 0.1, then with probability at least 1 exp(log T - -cN1 exp(d
Po N N Pg
), we have
SD(B, B*) < 60.
Method of Moments (MoM) Estimator: Estimation guarantee using MoM estimator given
requires the number of source task samples for each task N 2 polylog(N, d, ()r)) max(d, T).
Our estimator, on the other hand, requires N Z max(log T, log r). Estimation guarantee in [I].
Theorem 2, provides subspace distance sin BBB, -- Ö(
Ō(-) here hides the logarithmic terms and constant terms. It shown that the MoM estimator achieves close-to-optimal estimate if the number of tasks is bounded as T < Odd. On the other hand, we provide an optimal estimation guarantee dg, i.e., SD(B, B*) < 6g. where 6p < 0.1, under the given sample complexity. Since our problem setting involves scenarios where the number of tasks T is independent of the feature dimension d, the MoM estimator is not directly applicable in our setting.
( /max(d,T))rog
C Proof of Theorem
In this section we present the proof of Theorem 4.1 We first present the following lemma which is used in the proof of Theorem 4.1 Lemma C.1. Assume Assumption 3. holds. After the exploration step, for each task E [T], with probability at least - 2 exppllog T + - cN1), we have
[ T TT 2 N,, () B
47 Ni
H
HN.ell
1 g
Proof. To determine the upper bound for the term [ perform thorough analysis follows:
N. ,,, -1 B)
T
1 No T H we
[ & N, NN
- B))
+ RN = [1
+ N
2 Ni
B 1b H N: B
+
T
B)
4 N |l No B
16

---

Let us consider fixed 2 E S,.. We have
N₂
B 1 Ny. NN IN,
B2 =
Σ
2 B
Immttf mi Bz
mml
Furthermore, we find that
Blz B Rm m, Bz) = Bl m. = =B Bz =1
and also
E|z T B Immi] =0
Var(z B xm.e) = E[2 B Lmm m. B2] =
The summands are independent sub-exponential random variables with norm Km & 1. We apply sub-exponential Bernstein inequality stated in Proposition A.2 by setting g NN In order to implement this, we show that
g²
2 N 2 N1
N1
m=11
m
9
N1
C1
maxm Km
max
Therefore, for a fixed E Sy, with probability at least exp(-cef
_ B Ni.
NN N
Ni N1
Using epsilon-net over all S, adds factor of exp(r). Thus, with probability least 1 N1). we have minzes. z B TT 1 N, Ny B2 > (1 - -1 N,, Then, the above holds for all [7] with probability at least - exp(log T +r Ni) Setting El = 0.1, we obtain
Φ No. 1 N, B) 1
miin B TTTT Ni.t 2 Ny. B)
millzes, = BT $ No. 1 UN,,,N, NN, Bz
0.9NN
Similarly, us consider a fixed S,. We have
m BT o T H BE
Σ m=1
x B Ima B
Furthermore, we find that
El 1m, Mm, B2 = =T E B = 0 E[2 T DT Im.7Tm. B2] = xT
and also
E|z BT xm =
Elymm, B3 00
Var( ET BT xm,() R TT xm : m., B2
TT "TBB
TE Tf a - T. ΣT BT Bz
Var(mm, = Einin, B B = Emn Bz 2
The summands are independent uub-exponential random variables with norm Kmn & a. We apply sub-exponential Bernstein inequality stated Proposition A.2 by setting g e2Nio, In order to implement this, we show that
g2
22
2g
K2
N102
mm
m
9
N1
N
max
K
17

---

Therefore, for a fixed & E Sy, with probability at least - exp(-oe2.N1),
x B D DN HN. B & 62N110
Using epsilon-net net over all E Sp adds factor of exp(r). Thus, with probability at least cxp(rr N)), we have maxzes. 2 _ Φb N1.1 HN B2 & 22. Then, the above holds for all E (7] with probability at least - exp (lo 7 + ce2NN). Setting e2 = 0.1, we obtain
| T 4 N1. HN, B|| = max = B $ N1. N, HN,, < 0.1N10
=ES,
We can combine these and apply the union bound. This leads us to conclude that with probability at least 1 exp(log T + +r--ar 1N)).
[ 1 N NN BB, 1h, HN.ell & 0.1N
0.9N1
Proof of Theorem 4.1
We start by analyzing We based on its least square estimation given by Wh (B 4 DN B ( (#,,
(B) YN,,
(BT DN Nun
1 No.1 ( B)T ( B Bw, + HNI.))
=(B (BTON 1 NN. B $ N HN,, + (B" o5 NN N; B $ DN. B* w
= -BBTAT N NN. DN. $ HN.. (BT oT NN., BB T N NN , BB B"
+ +(B NT, N B) Nii Ny (T -BB "B"
= = NN. B Ny H No.1 +B BB
NN
+ + DN
B Ni.t 4 NN,,((I -B B
Applying B to both sides, we derive
B B
T N. N₁ B) - TT TT, HN, BB B*u
+ + + N PN B) BT TT, t N.. - BB )B"
-B(BT T o Ni B) - 'BT T N., HN,, B: + (BB - BB
+ B( Φ N,, N, B TT N. (T- (1BB BB",
Therefore, by applying the union bound, with probability at least 1 eexp(logggg T - cNN) exp(d-
eo,,,T 4xpp(log] T + - cN1), we derive
|Bū, B²w; = |B 2 2 DN - BT N HN.. + (BB l'BB"
+ B( T 1 N, B) B a N NI BBB ) wi'l
< [ $
$ n - Hn..l + + - B'BB's
+ | 1N
2 (1
BB "B)BBu' >B"wil
N
< | D
N
-
H
+ + I)B' will
+IIB TT
BB"
< [ a 2 n, B
B N 1 N.
+ (.1))+)))(( BB BB
o 1.12pM
T oi 80
(6)
10:1100 + 1.122
m do
(7)
N
1.12+
)"
max da
(8)
RPr/NN
18

---

where Eg (5) is derived from Proposition B.1 in (8 Eq 66) is derived from Proposition B.1 and
Lemma C.I
Eq
derived from NSR <
cT'
10 l1
Eq
is derived from |07|
| My 7 maxx To ensure probability least 1 - 6d 10 guarantees for theorem, it
is necessary to set the bounds for N1 and N,T. These bounds must guarantee that the following
probability is at least 1-6--10; 1 exp(log 7 --cgg -xx)) = ,
exp(log T + ---ae cNi).
This required that each exponential term be substantially smaller than or equal to 10, We obtain
log T cN1 < -10log N1 > C (oax(log,, log
d co 100log N1 T Cp²
dr
r n²
68
log T + cN1 10 = N1 C max(log d, log T.r).
Consequently, combining these results, we conclude that
N1 >
C max(log d, log T,
Cy²2xa dr2
NiT
80
Thus, the proof is complete.
D Proof of Theorem 4.3
Proof of Theorem 4.3
We start the analysis by founding bound on the cumulative regret R for the exploration step in the following manner:
RMT
Σ
mm
I 0m
m
Let us define My = E EL 0r observed that E[M, M1, ... MM-11 = Mj and
M| < oo constitutes a martingale. According to Assumption 3.1 the feature vector x follows the standard Gaussian distribution. Thus, oi NO 00 (|3). Utilizing Gaussian tail bounds and the union bound over T tasks and Ni rounds, with probability at least 1 - 8,
on & 2lg N.T |0 Given that
T
Mg -
=
N,T
2 log
||0:1|
T ||wž||
Σ
2 log
(9)
N,T
2 2
uf
we utilize the Azuma-Hoeffding inequality stated in Proposition determine that with probability least 1 26, the cumulative regret R for the exploration step bounded as follows:
A. and the union bound to
NIT
R N.T
( 2m, < 2ul V Ni log log
1==
According Assumption 3.2 matrix W p-column-wise incoherence (Appendix Ap. This indicates
that the norm of each task-specific vector is bounded || ||2 & p. max
By applying this
19

---

property into the analysis of Eq. 9 we conclude that with probability at least 1 - 26, the cumulative regret is bounded by RN, & 2pe max / N, Tog log NT7 8
Next, we demonstrate a bound for the cumulative regret RygT in the following round as follows:
N Σ
R3 NNT
m. oi
m== 1
N
Σ
Fm,t 07 -x 10 07 o 2
N1
N
Fm.t 0: Imm 0r + +.
=m 0c "m
M1
t=1
N
Σ
Σ
F E (07 - -0.) + x (0. 07)
M=N
Let us define M Em=N, Ei "m, (0 - 0.) +
T -2)- Observing that
B|M]IM M = - and MI < it can be found that {Má = 0. 1, 2, 3, .....
constitutes martingale as well. According to Assumption 3.1 the feature vector Zm, follows a stan-
dard Gaussian distribution. Thus, T (0; 02) ~ NO0 [1(0; 2.) Utilizing Gaussian tail bounds and the union bound over T tasks and (N- Mi) rounds, with probability least 1 8, x: (0;-0.) <
2 log NT) 10 0.11- By applying the findings from Theorem 4.1 and the union bound, we show that with probability at least 1- ô exp(log T' cNVi) exp(d follows that
25 T 1
exp T +r-cNN
T
Mz My-1
3et (0 σ.) + x 0, 03)
[=1
(0 -0.)
max xEX
(N N1)T
2 log
100 -0:l
Dell
t=1
2
T
log
(N NT)T
1.12 + RPr/N1
MV o
50
8
t=1
(N N:)T WVrTo max Su log 8
= 2
1.12 +
N
Utilizing the Azuma-Hoeffding inequality stated in Proposition A.I and the union bound, we can determine that with probability at least 28 exp(log cNi) exp(d < N;
4 exp(log T + + cNN1). the cumulative regret R for the following round is determined as follows:
N
RNT
Σ
(0) - 0.) 2 07)
Ni
(=1
(N N
4410r max
1.12
50 r(N -N) log 5 log
R2r R N₂
By combining the bounds for R and R 2 N.T and applying the union bound, we can conclude that
c5 with probability least 1 48 exp(log T - cNN1) exp(d 7
4expplog I + c.N1).
20

---

the cumulative regret RNT is given by
RNT -RN, R'xT
1
NIT
(N
NI)T
2uT
N1 log
log
4uo max
(1.12 +
122N/11 J601
r(N NT)
log
8
8
1
NT
1 BoyT.NTlog
NT
2uT N log log
4po max
1.12+
④ log
8
Rrr/N/
= o (TVN + 8gg VTNT
Moreover, by combining the cumulative regret bound for R obtained through the p-column-wise incoherence property of W*, and Rx and applying union bound, we determine that with
probability of least 1 - - exp(log eN1) - exp(d NT the cumulative regret bounded by
expp(log + cNv). p
NT
[.112+
1 NT
RN, T 24 max
NNT log log
+ 440
60 V TNT log log
8
/ N
4cdu
NT
2 4.4860 +
max
NNT log
log
log
x2r/N,
8
Ō (1+ (00+ 60)
VrNT
E
Proof of Theorem 5.1
Definitions:
For À 0, define the matrices
Vo,T41 XI BT TT n. P,, B, and
. -V,T+1 = XI T n,7+1 T TT.4I.
Here V2,T41 = BT V
Proof of Theoremm..1
Let Wn, be the least squares estimate of w/411 with f regularization, where the regularization parameter À > 0. We have
Tn,T+1 V @ T+) B
Yn
V ( B)T BB + Hn,T+1)
VTT B 2 H1 + V= B 4 2 a B
-V 8 DT Hn. + 1-1 1
_ a IT+I I DB B w
V.r TT T T BB
) wh+1
-V B _T H H
V-1 n, (V,TT+1
XIB B B
+ Vo T 2 T1 BB )B" w
Vn TT 11 + B B* 3"
XV n.T+1
B B" B"ur+1
+ 4-1
TT TT AB wi+1
21

---

By multiplying B on both sides, we derive
Būn,T+I - BV BT Du,T+ HT, + BB B B1 XBV
n,7-1 B B" B"
+ +VV B TT
TT u Q T+1 B B B++++
=BV TT T Hn,T+1 + B' W (BB
-IBB"u++1
-BBV x,7+1 BT B BT+++1 + BV B TT nTT Pa,T++ BB w7+1
Considering any vector 2 E R and multiplying both sides, we get
2 T BB,, BB' w1+1
=VV n,T+1 BTg $ n Hn,4I - A2 BV,
n,7+1 BV + - 1)B"
+ +VV n,T+1 BTg n1 2 T+ BB )B 3/++++
((=T B
T n.T H Hn. H4lv A((2) T B)T BB B
+ + + B)B w +(2 B T 8 II BB
) BB
Analyzing the absolute value, the upper bound is given as follows:
12 TWn - = B² w1-1
< 11(2 [lx B) 1|v || T
+ +1l(2 B) Il 1y [ 1' m.741
n,7+1
6.741
+1[(=T T
4 14
BB BB* w/ w/ v
+ + -I)B"
n,741
n.1
(10)
To determine the upper bound for the term || $ n Hn,r+ Hillsr apply the method from Theorem in 22 which gives us
dee((V.T-1))
1)) (AT)
| Φ n Hn, T+1 12 v
& 20 202log
5
with probability least 1 8. To determine the upper bound for the term | B Brw + +1ll have
we
BB B" w
=T+1 B"
BV-1
n
B. B B & 1 B" w V n,r+1l22
BB* 11
B n.1+1l22 & Amiu (Vn, X
S2
To determine the upper bound for the term | t n fn. BB BB
BB
have with probability at least exp(log cN1) exp(d [4p(x())
NiT
B ④ n. Dn BB B wh & (1 BB BB
|| BB )B [all & VTLdos
where the first inequality follows from the matrix inequality 2n.T+1 B(AI B T # P B) 1 BT TT x.7+1 I. The second inequality follows from the Cauchy-Schwarz
inequality. The last inequality follows from | & vnL, || ||0 & S and Propo-
sition B.I Consider Vn.T+1 (BW B* B'w, 41). To determine the upper bound for the term
22

---

1 (BB -1) w1)B*=7++ wT+1 we have with probability at least 1 (xp(logTTTToo -exppd
o6 Ni r2p2
IBB(BB" - 11BBB w (BBūn, B VI,T++(B'' 1B+B
(Bün,T+I - B" w (BB - -1)B"wi++)r,
[BinTT+1 13 13 wT 11 |1(BB
Bwn,I+I B B1 (VA][(BBT -I)BB
+ 1 T)B
< (VV+ V
B -I
To determine the upper bound for the term 11( [1 B)
we have
[1( BIx [ V. 0,7+1
=
BV
BV
n,7+1 BT
(B@n,T+1 - BBw++1) II n,T+1 B Vn V1, B Bru++1)
-BBBn,ITI - B" T
BV
n.I B
pt
n1T+1 n,T+1 (B04)(BB,,.44 - B'
44
n,T+1 n.T+1
[BB -B''---wwjj 1/ 11 m,7
n,7 n,
DV
B V2
n,7+1
Būn B' B' Vn,741
where the last inequality is derived from ||
n, n.T+1 n,T+1 = |1
BV BT V
BV BV
n,T+1 n, n
Amnax (V (V, [n,,74 B 4 V BV
n,1+1
n11+ Amax V
n,7+1 Vn,VV
V (,,+1) = To determine the
upper bound for the term 1z Būn,T+1 B By w have
12 Bun,T+1 -T B" l [BT B" w/
= -BBÖn,T41 BBu++1) Vn,T4I (BW,, - B* w1++
11B - -B'w+++lit 2 11
Substituting these in Eq. (10) gives
Bio, B" P7.T+1 < Bi BB alaill,,, Il of 2 T
det((A)- det((/))))d)()))))
+ X Al
B* B" 1l Vn VX S
+ B - B* B* Il Ceeerrnnie SL
+ (VA+ VI - B" B'wi+illanze
By rearranging and simplifying the inequality above, determine that with probability least 1 - exp(log cN1) - exp(d <d N.
[B B" w' <0/2log ( + 6 +
23

---

Furthermore, det((v,T+1) det(AX+ B o the eigenvalue value of the positive semi cemindefinite matrix B T a n1 nn. B. Given
n. P 2n I (A Ad), where A represent
X E Tr(B"o 2 nT
Tr B Im mm
Σ
m=1
Tr((B 11) T
m=1
Σ T+,)+1) ( Im.T+1) (BTTm
m=1
B
Tm. T+1
[m,T+112
m=1
nn
we conclude that de & Consequently, we show that with probability least 1 1- exx(((o cN1) exp(d
(A+ = (A+nl2y = ( " Setting 60 V/2LL'
N,
,²
1 1+
Ví + +VA+
[B - B"
& Covrlog
+ 2 S.
8
VN2L.
N₂
Note that we have probability of 5 - cxp(log T cN1) exp(d
< x2p2 ) To ensure
probability guarantee of at least 1 - 5 - 2d 10 for our theorem, it is required set the bound for Ni and N₂ T such that the exponential terms are less than or equal to d 1010 We obtain
log T -cNi < 10 d + N₁ C Cmax(log d, log T)
Co N.T
dr
2 & - 10 log NT Cp²
g5
Consequently, combining these results, we conclude that
N1 > C maxx log T)
2r
N,T Cp2K
By setting 6, 1 VNyE*
it is essential to ensure that
N
C maaxloo log T)
NTT L N2.
Thus, we complete the proof.
F Proof of Theorem 5.2
In this section we present the proof of Theorem
5.2
24

---

Proof of Theorem 5.2
We start the analysis by bounding the cumulative regret RN,T+1 for the target task T + 1. With probability least 1 2d--10 have
N2,111
N2
m+ 1 2m,1+101+1
N2
mm,T+ +1 0
T +m
(11)
m=l
N₂
mm (Om,T+1 - 0m,T+1)= + I.T =+ (0, - 07+1)
T
(10m,T+11 Om,T+illin 1x 110m,T+1 0f+1llim 1211) || lll
N2
N₂
2 [10m,T+1 @m. + +110m,++1 07
1.711
(12)
1+ N22/A
VÁ
dee(
< N2
0 r
+(V++
+ +
2 2
(13)
VN²L
del(Al)
1 N212/1/1
VĀ
1+ N212) )
22/N2
N2
vorlog
+VV+
+ +2.
2d
(14)
V
Ō VdNa (orr+ viS)).
where Eq [1 follows by I T+1 0++1 < Fmm.T.. T+1 m. Eg 12
follows by Cauchy-Schweer
inequality. Eq 13) follows by Theorem 5.1 and Lemma 11 in 22
G Transferring Feature Representation to New Target Tasks
In this section, we present a direct linear regression algorithm for transfer learning to a new target task using the shared model extracted from the source tasks. Using the estimated linear feature representation B shared across related tasks from the source task, our goal here is transfer this representation to new, unseen (T + 1)th target task and thereby improve learning and sample complexity as compared to the standard approach that learns the task separately without leveraging the knowledge from the source tasks. Our main focus here is to derive sample complexity bound on
the number of target task samples required when using the biased estimate B. The pseudocode is presented in Algorithm 3 uses B as a plug-in surrogate for the unknown 8 and estimates w7+1- Mathematically, we define our estimator as follows
@T+1 arg min
1lm.T+11 Tm,TT4 Bw
In the result below we present the error guarantee for the linear regression estimator and the sample complexity on the number of target samples required.
Theorem G.1. Axsume Assumptions
3.
holds. For new task + 1, with probability at least 4exp(log T cN2), using Algorithm we have
t-xxpllog T cN1) exp(d
o5 N.T T
1 - + 126621117711
1B - B" B' <
9
25

---

Algorithm 3 Transferring Features to New Tasks
1: Set number of rounds for target task, 22
2: Perform representation learning using source tasks and estimate B using Algorithm from line 1
to line
3: for < 1,.., N2 do
4: choose action 2n,T+1 arg max 0r+1, and obtain Vr,T+1
5: end for
6: Compute YN,,T+1 11,T+111" IN1 T NN,T [11,++1;' (+11
7: Update WT+1, 0r+1: : Set WT41 f- N# B) YY,,T++ and set 0T+1 = BWT++
Furthermore, if
N1
C' maxx(log log
dr²
N1T
Cp k
50
2
Cmax(logd, logTT).
then with probability at least 1 6d-
BuT+1 B w
9 o + 1.1266
Proof. Following the same logic as in Lemma C.I we can demonstrate that with probability at least 1 - exxp(log T +r cN22), we have
1 [ @ NT.T B " 2 TI az.
Following the same logic as in Theorem 4.1 show that
Bür+1 B* w B' B(B NN
Ny TN N..T N41 (BB B)B wi+1
+ B(B TT No.T+1
II NN,T+1 DN, -BB 3BBBBBr
Therefore, with probability least 4 eexp T' + - c.22), we obtain
exp(logT cNi) exp(d
r"p"""
BuT w+++l
[B D 2 BB
Na. #x [(BT w1a1l
| TJ T+1 1 -
N 1+1 NN.TH BßT) B
< |[ NN, 2N.
BT TT H HN.ll
+(1 + 0.12) BB BB
1 < 0 1.126 +1
where the second-las last inequality derived from Proposition B.I in 28). The last inequality is derived from Proposition
B.I
H Additional Experiments
In this section, we present some additional experiments.
Comparison with the convex relaxation approach: We evaluated our proposed algorithm (Algo- rithm [] against the convex relaxation method utilizing the same data generation method described in Section 6. The convex relaxation approach approximates the non-convex cost function through the application of trace-norm regularization 10). The key challenge that the solution to the relaxed problem may not necessarily correspond to valid solution to the original problem. As shown in
26

---

Synthotic daia: d 100, 15,7- 10.0,
le3
Movielens: d 100, T 15
Proposed Algorithm
2000
Convex Approach
1500
1000
0.4
500
0.2
Proposed Aigorithm
Convex Relaxation Approach
0.0
0
20
40
60
80
100
0
20
40
60 80
100
Round, N
Round, N
(a)
(b)
Figure 3: Plots for synthetic data: Figure Ba presents the cumulative regret vs. learning round for synthetic
data, with parameters set d 100, T 15. 10, Ni = 45, o² 0.01. Plots for Movielens data: Figure 3b presents the cumulative regret learning round for Moviclens data, with parameters as d 100,
N1 20, 0.01.
Figure 3a our proposed algorithm outperforms the convex relaxation approach for the synthetic data. Figure 3b indicates that our proposed algorithm shows fast convergence following the exploration phase and consistently outperforms the convex relaxation approach for the Movielens data, which does not converge. A potential reason for this that the solution the convex relaxed problem need not necessarily be the solution to the actual non-convex problem. This experiment validates the effectiveness of the proposed approach.
Additional Related Work
We present some additional related work in this section.
Multi-task reinforcement learning: Multi-tase learning in reinforcement learning (RL) domains is studied in many works, including [36]
56-58) analyzed the problem from the empirical perspective. From the theoretical perspective, [59 analyzed the sample complexity of
39
55
41].
[36
39
multi-task RI. in the tabular setting.
55 demonstrated that representation learning has the potential
to enhance the rate of the approximate value itcration algorithm. 4 proved that representation learning can reduce the sample complexity of imitation learning. Both works require probabilistic assumption similar to that in [44 and the statistical rates are similar forms as those in [4. Representation learning in multi-task RL has been studied recently in
62).
Low-rank and sparse bandits: Some previous work studied the impact low-rank structure in linear bandits 29 63 64). [63] considered setting where the context vectors consist of two parts, ie. x + 1h, so that x: from hidden low-rank subspace and is i.i.d. drawn from an isotropic distribution. The mean reward in (29 65) is defined as the bilinear multiplication x. Oy, where ar, are the actions chosen and the unknown reward matrix with low-rank structure. The bilinear setting is further generalized by [32].
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction explicitly describe the contributions and scope of the paper. The introduction also concludes with comprehensive list of the specific contributions made in this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of this work (Gaussian model on source tasks) are clearly stated in the paper and relaxing this is identified as future work in the conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: For each theoretical result, we present a comprehensive set of assumptions. A proof sketch follows each result, while the complete formal proofs provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
The Simulation section provides comprehensive instructions on data generation and utilization, along with parameter configurations, facilitating complete reproducibility of the experimental results.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
29

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide open access the data and code, along with thorough doc- umentation, enabling others to precisely reproduce the experimental results. (https
//github.com com/ sommmthinggttteree/tsaaaaaooooo
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
Sow.eesuuubsssioooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ctipss.c//ublic//uiie gwwiii/gguee//eeeeeoeooi. CodeeSumiiiseeeeee onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The experimental settings and implementation are comprehensively detailed in the Simulation section.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Results from experiments on synthetic data are averaged across 100 inde- pendent trials, with corresponding error bars provided. Results for real-world datasets are derived from only one trial; therefore, error bars are omitted.
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: We omitted detailed information regarding the computational resources utilized, our concentration mainly on theoretical analysis (e.g., cumulative regret and sample complexity), and the experiments are computationally lightweight.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that NeurlPS Code of Ethics btttps://neutt httpp//wbw.//ceccccsseeeeee..eee
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification: The research conducted in this paper conforms with the NeurIPS Code of Ethics in all aspects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
31

---

Justification:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
All authors and citations have been mentioned, to the best of our knowledge.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
32

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the palasets.papersstt paperssi thcode. com con/dataset package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
33

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The paper does not utilize L.M.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
34


Reviews:
[{"review_id": "OlAFA3Dopm", "reviewer": "Reviewer_h4ME", "summary": "This paper studies the problem of multi-task linear representation learning in the linear bandit setting. Each linear bandit task $t$ has reward vector $\\theta\\_t^\\*=B^\\* w \\_t^\\*$ for a shared ground-truth subspace parameterized by $B^* \\in \\mathbb{R}^{d \\times r}$ and a task-specific vector $w\\_t^*$. The problem then becomes to learn the ground truth subspace using the provided in order to facilitate generalization to a new downstream task with the same structure. The paper proposes an Explore-then-Commit (ETC) algorithm to estimate the ground-truth subspace and an OFUL-based algorithm to solve the downstream task. These algorithms are theoretically analyzed and simulations are provided to verify the theoretical results.", "questions": "Please see weekness 1 -- can you further clarify the novelty?", "limitations": "Yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The formulation is rigorous. The theoretical results are clearly explained. The paper is well-written overall.\n2. The theoretical results demonstrate the utility of representation learning in reducing the new-task regret bound from $O(d\\sqrt{N})$ to $O(\\sqrt{drN})$. A helpful proof sketch is provided, and the analysis seems non-trivial.\n3. The simulations are thorough and consistent with the theory, and also well-explained. \n\nWeaknesses\n1. The paper discusses the series of prior works that have also studied mutli-task linear representation learning in the bandit context, and mentions that these works either use a convex relaxation or assume access to the solution of a non-convex problem in order to obtain their theoretical results on subspace learning. However, in the formal analysis the paper does not discuss what distinguishes their analysis from prior work, which would be helpful to gauge the novelty considering the extensive prior study of this problem.\n2. The level of interest of this problem to the community is not obvious, considering apparent decline in interest in bandits, and also that this method is limited to linear analysis.", "was_revised": true, "final_justification": "I thank the authors for their thorough response. This has helped to mitigate my novelty concern, and I have raised my score.", "rebuttal": "Thank you for appreciating our work and for your valuable feedback. Please see the following for our responses to your questions. Please let us know if there are any further questions.\n\n1. Difference from Prior Work and Novelty\n\nOur paper extends the prior work in two key ways.\n\na) Estimation guarantees for learning the shared representation from source tasks: A key challenge in learning the shared representation from source tasks is that the estimation problem is inherently non-convex. Yang et al., ICLR, 2021 in their Algorithm 1, line 5, and Hu et al., ICML, 2021 in their Algorithm 1, line 2, assume that the optimal solution to the non-convex cost function is known. This assumption is later leveraged in Lemma 2 (Yang et al., ICLR, 2021) to derive the inequality $[x\\_{n,t}^{\\top} \\widehat{B} \\widehat{w}_{t}-y\\_{n,t}]^2 \\leq [x\\_{n,t}^{\\top} B^{\\star} w\\_{t}^{\\star}-y\\_{n,t}]^2$. \n\nSimilarly, Hu et al., ICML, 2021 utilize this assumption in Lemma 1 to obtain $||y\\_{t,i}-x\\_{t,i}^{\\top} \\widehat{B}_{t} \\widehat{w}\\_{t,i}||_2^2 \\leq ||y\\_{t,i}-x\\_{t,i}^{\\top} B^{\\star} w\\_{i}^{\\star}||_2^2$. \n\nThese works primarily focused on providing regret guarantees under the assumption of a known optimal estimator, aiming to validate the effectiveness of learning shared representations. Cella et al., AISTATS, 2023 considered a convex relaxation of the problem through trace-norm regularization (line 4 of Algorithm 1). The key challenge is that the solution to the relaxed problem may not necessarily correspond to a valid solution to the original problem.  Building on this foundation, our goal is to extend and enhance these approaches by establishing both regret and estimation guarantees without assuming the existence of a predefined optimal estimator.\n\nTo address the non-convexity of the learning objective and obtain estimation guarantees for the shared representation without relying on the known optimal solution, we propose an Explore-then-Commit algorithm based on a spectral initialization approach. In the spectral initialization, we initialize the shared representation $\\widehat{B}$ as the top-$r$ singular vectors of  \n$\\widehat{\\Theta}\\_{0} := \\frac{1}{N_1} \\sum _{t=1}^{T} \\Phi\\_{N_1, t}^{\\top} Y\\_{t, trunc}(\\alpha) e\\_t^{\\top}$, \n\nwhere $Y\\_{t, trunc}(\\alpha) := Y\\_{N_1, t} \\circ \\mathbb{1}\\_{\\{|Y\\_{N_1, t}| \\leq \\sqrt{\\alpha}\\}}$ and $\\alpha = \\frac{\\tilde{C}}{N_1 T} \\sum\\_{n=1, t=1}^{N_1, T} y\\_{n, t}^2$.\n\nThis truncation strategy is critical to ensure the error bound of the estimate of the unknown reward parameter with respect to the true reward parameter, $||\\widehat{\\Theta}-\\Theta^{\\star}||$. Using the estimate $\\widehat{B}$, we subsequently estimate the task-specific parameter $\\widehat{w}\\_{t}$ for each source task via a least-squares estimator. In Theorem 4.1, we prove that our proposed approach guarantees $||\\widehat{B}\\widehat{w}\\_{t}-B^{\\star} w\\_{t}^{\\star}||=O(\\sqrt{\\frac{r}{T}})$, resulting in a cumulative regret bound of $\\widetilde{O}(\\sqrt{rNT})$ in Theorem 4.3. This is a significant advantage over the naive approach of solving the $T$ tasks independently, where the regret will be $\\widetilde{O}(\\sqrt{dNT})$.\n\nb) Transfer learning guarantees to the new target task: Another key novelty of our work is its focus on the generalizability of the learned shared representation to new target tasks, a direction not explored in prior work. Our objective is to establish regret and sample complexity bounds for learning a new target task using the shared representation.\n\nWe propose two algorithms to transfer the learned representation to a new, unseen task.\n- OFUL-based approach: We develop a novel construction of confidence sets that utilizes the shared representation $\\widehat{B}$ learned from source tasks. We prove in Theorem 5.1 that, with high probability, the true reward parameter of the target task lies within the confidence set. This further helps us to prove a tight regret bound of $\\widetilde{O}(\\sqrt{drN})$ for the target task in Theorem 5.2. This is a significant advantage over solving the target task without leveraging the shared representation, where the regret will be $\\widetilde{O}(d\\sqrt{N})$, since $r \\ll d$.\n- Regression-based approach: We also develop a linear regression method to estimate the target task reward parameter $\\widehat{w}\\_{T+1}$ by utilizing the learned share representation $\\widehat{B}$ from source tasks. We prove a bound on the estimation error $||\\widehat{B}\\widehat{w}\\_{T+1}-B^{\\star} w\\_{T+1}^{\\star}||$ in Theorem G.1 along with the sample complexity.\n\n2. Community Interest\n\nAlthough the bandit problem is a well-established area of study, recent developments in multi-task learning, federated learning, and transfer learning have revitalized interest in designing scalable and generalizable algorithms for the multi-task bandit problem (e.g., Lin et al., ICML, 2024, Yang et al., ICLR, 2021; Hu et al., ICML, 2021, Cella et al., AISTATS, 2023). These new directions aim to tackle emerging challenges in real-world applications, where learning must occur across multiple related tasks with limited data. \nBy leveraging inherent problem structure and joint learning paradigms, the goal is to accelerate learning and enhance generalization, particularly in low-sample regimes.\nMulti-task bandits have gained prominence in areas such as personalized recommendation systems, where multiple agents share underlying structures while working with localized information. Our paper contributes to this growing body of literature by introducing efficient algorithms with theoretical guarantees."}, {"review_id": "7iL32CtwC4", "reviewer": "Reviewer_CpDY", "summary": "This paper introduces a meta‐learning framework for linear contextual bandits that learns a shared low‐dimensional representation across source tasks, and consequently transfers it to the target task.  For the upstream phase, the authors propose an ETC algorithm using spectral initialization to handle the non-convex nature of the problem. Authors prove that it recovers the subspace with error $\\widetilde{O} (\\sqrt{r / T})$ and leads to $\\widetilde{O}(\\sqrt{r  N  T})$ cumulative regret.  For the downstream transfer, they develop a subspace restricted OFUL variant, which leads to $\\widetilde{O}(\\sqrt{r  d  N})$ regret, compared with the naive $\\widetilde{O} (d\\sqrt{N})$ regret in linear bandits. Empirical results on synthetic data (multiple trials) and real‐world datasets (single trial) confirm significant improvements over baselines.", "questions": "1.\tCould the authors please give additional justifications on applying the gaussian assumption (Assumption 1)? I believe it is important to provide sufficient discussions for this assumption as it is fundamental to your theoretical results, and such assumptions are also not standard from existing linear bandit works. \n2.\tCould the authors include additional discussions comparing your work with the kernelized multi-task learning bandits [1]? In [1], there are no such assumptions on the task feature assumptions, while their task features depend on the arm features within each task. By the way, I do not think it is reasonable to discuss this paper in your Related Works section in its current form, since [1] is not a linear bandit work.\n[1] Deshmukh, Aniket Anand, Urun Dogan, and Clay Scott. \"Multi-task learning for contextual bandits.\" Advances in neural information processing systems 30 (2017).", "limitations": "There is not a designated limitations section. Rather, authors only states that relaxing the Gaussian modeling on task features will be considered as future works. In this context, I suggest authors include more detailed and thorough discussions on their Gaussian assumption of the task features. For instance, why would such assumption be reasonable for real bandit learning scenarios? Could it be justified from perspectives beyond merely deriving the theoretical results presented in this paper?", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "+ The paper is generally well-written and easy to follow, with clear notation definitions, problem definitions, as well as assumptions needed for achieving the theoretical outcomes.\n+ Based on my knowledge, the theoretical results in this paper are interesting. Authors support their theoretical finds with established error bounds, sample complexity and cumulative regret, which are comprehensive.\n+ Experiments are conducted on both synthetic and real datasets in order to demonstrate the effectiveness of the proposed pipeline.\n\n-\tMy main concern aligns with the stated limitation from the authors, namely the Gaussian assumption of feature vectors (Assumption 3.1). In particular, it is insufficient to only justify that this assumption is for the sake of theoretical analysis, instead of justifying it is viable for real application scenarios. Therefore, more thorough discussions for this assumption are needed.\n\n-\tMeanwhile, the assumption on noise $\\eta$ also tends to be stronger than most existing works: it is assumed to be i.i.d. rather than conditional independent in most existing works.\n\n-\tIt would also be beneficial if authors can include the standard deviation results for the experiments. In particular, please also conduct multi-trial experiments for real datasets and report the standard deviation outcomes.", "was_revised": true, "final_justification": "I appreciate the authors rebuttal. However, the reliance on the Gaussian assumption prevents me from further raising my scores.", "rebuttal": "Thank you for appreciating our work and for your valuable feedback. Please see the following for our responses to your questions. Please let us know if there are any further questions.\n\n1. Gaussian Assumption\n\nWe agree with the reviewer that the Gaussian model for the feature vector plays a crucial role in our theoretical analysis as detailed below. Below, we explain the significance and necessity of the Gaussian assumption, provide empirical validation in cases where it does not hold, and outline possible extensions, along with related works that have made similar assumptions. \n\n- a) Why the Gaussian assumption is needed: In the analysis of our Explore-then-Commit Algorithm, we utilize the sub-exponential Bernstein inequality (Proposition A.2) to establish concentration bounds. For example, we use it in lines $559$, $570$, and $584$ of the paper. The Gaussian distribution of the feature vector is utilized here to guarantee the sub-exponential tail behavior of the corresponding random variable.\n\n- b) Gaussian assumption applied only to source tasks: We note that the Gaussian assumption of feature vectors is utilized only for the source tasks. Specifically, it is used for the estimation guarantees of the reward parameter of the source tasks. In Section 5, regarding the transfer to a new, unseen target task, our proposed OFUL-based algorithm utilizes the learned representation and does not require the Gaussian assumption. The guarantees for the confidence set and regret in the target task remain valid without the Gaussian assumption.\n\n- c) Generalization to broader distribution: From a theoretical perspective, we believe that similar results could hold under sub-Gaussian assumptions for both the feature vectors $x_{n,t}$ and the noise $\\eta_{n,t}$. Developing such a relaxation for the source task is a part of our future work.\n\n- d) Empirical validation without Gaussian assumption: For empirical performance, we would also like to highlight that our real-world experiment utilizes datasets with feature distributions that are non-Gaussian. Our proposed algorithm consistently outperforms the baselines across multiple settings, as illustrated in Figures 1(d) and 2(b). This indicates that our method remains effective in practice, even when the Gaussian assumption is not satisfied.\n\n- e) This assumption has been utilized in other works in the linear bandit literature, including Yang et al., ICLR, 2020; Han et al., 2020; Lin et al., ICML, 2024; and Kong et al., AISTATS, 2020.\n\nReferences\n- Kong, W., Brunskill, E., \\& Valiant, G. Sublinear optimal policy value estimation in contextual bandits. In International conference on artificial intelligence and statistics (AISTATS), pp. 4377–4387, 2020.\n- Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits, arXiv:2004.06321, 2020.\n\n2. Noise Assumption\n\nWe agree with the reviewer and plan to address this in our future work. We would like to note that the i.i.d. Gaussian noise model is used in multiple works on bandit learning, including Scarlett et al., COLT, 2017; Djolonga et al., NeurIPS, 2013; and Gornet et al., L4DC, 2024. \n\nReferences\n- J. Scarlett, I. Bogunovic, and V. Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1723–1742, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR.\n- Josip Djolonga, Andreas Krause, and Volkan Cevher. 2013. High-dimensional Gaussian process bandits. In Proceedings of the 26th International Conference on Neural Information Processing Systems.\n- J. Gornet and B. Sinopoli, “Restless bandits with rewards generated by a linear gaussian dynamical system,” in 6th Annual Learning for Dynamics \\& Control Conference. PMLR, 2024, pp. 1791–1802.\n\n3. Standard Deviation in Experiments\n\nOur paper included standard deviation in the plots for the synthetic data experiments, derived from $100$ independent trials. For the real-world data experiments, we now performed multi-trial evaluations using the same parameter settings as in the submitted manuscript and obtained the standard deviation. The conference policy prohibits the uploading of new PDFs or the providing of external links; therefore, we will describe the standard deviation below. For representation learning using the Movielens dataset (Figure 1 (d)), we performed $100$ trials, and the observed trends for the cumulative regret plot are consistent with those previously shown in Figure 1 (d). We present the standard deviation values for the cumulative regret for $T$ source tasks at rounds $100, 200, \\cdots, 1000$:\n\nTABLE I: Standard Deviation for Representation Learning for Movielens data\n\n| Learning Round | 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 | 1000 |\n|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|\n| Proposed  Algorithm | 0.95 | 1.94 | 2.84 | 4.17 | 6.08 | 8.21 | 10.46 | 12.76 | 15.06 | 17.36 |\n| MoM Algorithm | 0.95 | 1.94 | 2.84 | 4.35 | 6.36 | 8.55 | 10.86 | 13.20 | 15.56 | 17.91 |\n| Naive Algorithm | 0.83 | 1.59 | 2.33 | 3.06 | 3.85 | 4.64 | 5.43 | 6.23 | 6.97 | 7.81 |\n\nWe now performed $10$ trials (due to time limitations) for the transfer learning plot for Movielens data (Figure 2 (b)). The observed trends for the cumulative regret plot are consistent with those previously shown in Figure 2 (b). We present the standard deviation values for the cumulative regret for the target task at rounds $300, 600, \\cdots, 3000$:\n\nTABLE II: Standard Deviation for Transfer Learning for Movielens data\n\n| Learning Round | 300 | 600 | 900 | 1200 | 1500 | 1800 | 2100 | 2400 | 2700 | 3000 |\n|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|\n| Proposed Algorithm |  0.0001 | 0.0080 | 0.0078 | 0.0130 | 0.0128 | 0.0242 | 0.0126 | 0.0198 | 0.0197 | 0.0205 |\n| Naive-UCB Algorithm | 0.0181 | 0.0274 | 0.0395 | 0.0344 | 0.0478 | 0.0363 | 0.0485 | 0.0547 | 0.0635 | 0.0523 |\n| MoM-UCB Algorithm | 0.0082 | 0.0079 | 0.0161 | 0.0074 | 0.0288 | 0.0358 | 0.0256 | 0.0356 | 0.0283 | 0.0357 |\n\nWe plan to run this experiment for $100$ trials and revise the corresponding plot in the revised paper.\n\n4. Comparison with Deshmukh et al. (2017)\n\nWe have revised our discussion of Deshmukh et al., NeurIPS, 2017 (reference [33] in revised manuscript) in the Related Work section to more accurately reflect the contribution and distinguish it from the scope of our paper. In line $91$ of the revised manuscript, we now state:\n\nThe single-bandit setting has also been studied in [33], which proposed a kernel-based multi-task contextual bandit framework that leverages similarities among arms to improve reward estimation. The theoretical guarantees in [33] rely on the assumption that the task similarity matrix is known a priori.\nIn contrast, our paper presents a meta-learning framework for multi-task representation learning in linear bandits, where multiple distinct tasks share a low-rank representation. Notably, our approach learns the shared representation from the source tasks and utilizes this learned structure to facilitate effective adaptation to a new, unseen target task in data-scarce settings."}, {"review_id": "MXmP9RO79o", "reviewer": "Reviewer_NDgz", "summary": "The paper tackles meta learning by identifying shared representations in the context of bandit problems. The core contributions are an explore-commit design to first estimate the shared representation and then exploit it in solving source tasks and the target task, with SVD for spectral initialisation. This leads to the possibility of analysing a linear bandits setup without restrictions in previous works. The proof shows that bounds can be derived for characterising the error of identified representation and the regrets of the target task, with an improvement over the previous studies. The theoretical results are verified on real-world datasets about movie recommendation task, showing notable improvement on cumulative regrets comparing to baseline UCB methods.", "questions": "My main question is about the distribution and the exploration policy of generating action $x_{n,t}$. To what extent the conclusions and improvements can still hold if the distribution is not as simple as a unimodal like Gaussian? I see this is listed as a research outlook in the conclusion but would still like to hear the authors' opinions as for now. \n\nPotentially more critical to practitioners, what if the exploration policy is no longer a stationary one as the assumption here. There could be lots of design space in lieu of active exploration/learning. I can see this might break the exploration-then-commit paradigm but in practice it is not always common to see a complete offline stage or an exploration policy agnostic to what has been explored before.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n* General scope of meta-learning of bandits problems, which have good potential to decision-making problems that may bring real-world impacts.\n* Improved theoretical bounds.\n* Demonstration of effectiveness on a real-world dataset. Highly commendable for a theoretical work for me.\n\nWeakness:\n* Unclear about the implication of the selected exploration strategy.\n* Assumptions about feature distribution might be restrictive.", "was_revised": true, "final_justification": "I have read the authors' rebuttal and will stick to the original score and confidence level.", "rebuttal": "Thank you for appreciating our work and for your valuable feedback. Please see the following for our responses to your questions. Please let us know if there are any further questions.\n\n1. Gaussian Assumption\n\nWe explain the significance and necessity of the Gaussian assumption, provide empirical validation in cases where it does not hold, and outline possible extensions.\n\n- a) Why the Gaussian assumption is needed: In the analysis of our Explore-then-Commit Algorithm, we utilize the sub-exponential Bernstein inequality (Proposition A.2) to establish concentration bounds. For example, we use it in lines $559$, $570$, and $584$ of the paper. The Gaussian distribution of the feature vector is utilized here to guarantee the sub-exponential tail behavior of the corresponding random variable.\n\n- b) Gaussian assumption applied only to source tasks: We note that the Gaussian assumption of feature vectors is utilized only for the source tasks. Specifically, it is used for the estimation guarantees of the reward parameter of the source tasks. In Section 5, regarding the transfer to a new, unseen target task, our proposed OFUL-based algorithm utilizes the learned representation and does not require the Gaussian assumption. The guarantees for the confidence set and regret in the target task remain valid without the Gaussian assumption.\n\n- c) Generalization to broader distribution: From a theoretical perspective, we believe that similar results could hold under sub-Gaussian assumptions for both the feature vectors $x_{n,t}$ and the noise $\\eta_{n,t}$. Developing such a relaxation for the source task is a part of our future work.\n\n- d) Empirical validation without Gaussian assumption: For empirical performance, we would also like to highlight that our real-world experiment utilizes datasets with feature distributions that are non-Gaussian. Our proposed algorithm consistently outperforms the baselines across multiple settings, as illustrated in Figures 1(d) and 2(b). This indicates that our method remains effective in practice, even when the Gaussian assumption is not satisfied.\n\n- e) This assumption has been utilized in other works in the linear bandit literature, including Yang et al., ICLR, 2020; Han et al., 2020; Lin et al., ICML, 2024; and Kong et al., AISTATS, 2020.\n\nReferences\n- Kong, W., Brunskill, E., \\& Valiant, G. Sublinear optimal policy value estimation in contextual bandits. In International conference on artificial intelligence and statistics (AISTATS), pp. 4377–4387, 2020.\n- Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits, arXiv:2004.06321, 2020.\n\n2. Active Exploration\n\nA potential approach for addressing this is to adopt an OFUL approach for the source tasks integrated with spectral initialization. Following the initial exploration phase, which used spectral initialization to estimate the shared representation, we can proceed with an OFUL-based algorithm (similar to Algorithm 2) to construct the confidence sets for each source task and iteratively update the parameters. The proposed approach for each source task will proceed as follows:\n\n- Each source task randomly selects actions and receives rewards during an initial data collection phase.\n- Utilize spectral initialization to estimate the shared representation $\\widehat{B}$ using the collected data.\n- For every source task and each round:\n    - Construct a confidence set using the learned $\\widehat{B}$.\n    - Select an action-estimate pair that maximizes the estimated reward within the confidence set.\n    - Play the selected action and receive the reward.\n    - Update the parameters for each source task using the recently obtained data.\n\nThis method allows the algorithm to perform active exploration beyond the initial phase of the Explore-then-Commit algorithm (Algorithm 1). Formulating such an adaptive exploration strategy presents a promising direction for future work."}]

Author rebuttal:

Meta-review: This paper studies the problem of multi-task linear representation learning in the linear bandit setting. The paper proposes an Explore-then-Commit (ETC) algorithm to estimate the ground-truth subspace and an OFUL-based algorithm to solve the downstream task. These algorithms are theoretically analyzed and simulations are provided to verify the theoretical results.

All reviewers think this paper gives a solid contribution to the foundation of learning-to-learn. The AC agrees and thus recommends acceptance.
Decision: Accept (poster)