Impact of Representation Learning in Linear Bandits
Authors: Jiaqi Yang
Wei Hu
Jason D. Lee
Simon Shaolei Du
Venue: ICLR 2021 Poster (2021)
Keywords: linear bandits
representation learning
multi-task learning

Abstract: We study how representation learning can improve the efficiency of bandit problems. We study the setting where we play $T$ linear bandits with dimension $d$ concurrently, and these $T$ bandit tasks share a common $k (\ll d)$ dimensional linear representation. For the finite-action setting, we present a new algorithm which achieves $\widetilde{O}(T\sqrt{kN} + \sqrt{dkNT})$ regret, where $N$ is the number of rounds we play for each bandit. When $T$ is sufficiently large, our algorithm significantly outperforms the naive algorithm (playing $T$ bandits independently) that achieves $\widetilde{O}(T\sqrt{d N})$ regret. We also provide an $\Omega(T\sqrt{kN} + \sqrt{dkNT})$ regret lower bound, showing that our algorithm is minimax-optimal up to poly-logarithmic factors.  Furthermore, we extend our algorithm to the infinite-action setting and obtain a corresponding regret bound which demonstrates the benefit of representation learning in certain regimes. We also present experiments on synthetic and real-world data to illustrate our theoretical findings and demonstrate the effectiveness of our proposed algorithms.

Published as a conference paper at ICLR 2021
IMPACT OF REPRESENTATION LEARNING IN LINEAR BANDITS
Jiaqi Yang
Wei Hu
Tsinghua University yangiql 76 gmail. com
Princeton University
hwweeiec..prineettoooo edu
huweiica pwwnceton.ccccmmmoomom
Jason D. Lee
Simon S. Du
Princeton University
University of Washington ssduêcs, washington, edu
jasonlee@princetoo..com
ABSTRACT
We study how representation learning can improve the efficiency of bandit prob- lems. We study the setting where we play T linear bandits with dimension d concurrently, and these 7 bandit tasks share a common k(< d) dimensional lin- ear representation. For the finite-action setting, we present new algorithm which achieves O(TVkN + VdkNT) regret, where N the number of rounds we play for each bandit. When T' is sufficiently large, our algorithm significantly outperforms the naive algorithm (playing bandits independently) that achieves (TVVNN regret. We also provide an Q(Tv/N + VT) regret lower bound, showing that algorithm minimax-optima up to poly-logarithmic factors. Furthermore, we extend our algorithm to the infinite-action setting and obtain corresponding regret bound which demonstrates the benefit of representation learning in certain regimes. We also present experiments on synthetic and real- world data to illustrate our theoretical findings and demonstrate the effectiveness of our proposed algorithms.
INTRODUCTION
This paper investigates the benefit of using representation learning for sequential decision-making problems. Representation learning learns joint low-dimensional embedding (feature extractor) from different but related tasks and then uses a simple function (often linear one) on top of the embedding (Baxter, 2000; Caruana, 1997; Li et al., 2010) The mechanism behind is that since the tasks are related, we can extract the common information more efficiently than treating each task independently.
Empirically, representation learning has become a popular approach for improving sample efficiency across various machine learning tasks (Bengio et al., 2013). In particular, recently, representation learning has become increasingly more popular sequential
problems (Tch et al.,
2017: Taylor & Stone, 2009; Lazaric & Restelli, 2011; Rusu al., 2015; Liu et al., 2016; Parisotto et al., 2015; Higgins et al., 2017: Hessel et al., 2019; Arora et al., 2020; D D'Eramo et al., 2020). For example, many sequential decision-making tasks share the same environment but have different reward functions. Thus a natural approach is to learn a succinet representation that describes the environment and then make decisions for different tasks on top of the learned representation.
While representation learning is already widely applied in sequential decision-making problems empirically, its theoretical foundation still limited. One important problem remains open:
When does representation learning provablyy improve efficiency of sequential decision-making problems?
We take a step to characterize the benefit of representation learning in sequential decision-making problems. We tackle the above problem in the linear bandits setting, of the most fundamental

---

Published as a conference paper at ICLR 2021
and popular settings in sequential decision decision-making problems. This model is widely used in applica- tions as such clinical treatment, manufacturing process, job scheduling, recommendation systems, etc (Dani et al., 2008; Chu et al., 2011). We study the multi- version of linear bandits, which naturally models the scenario where one needs to deal with multiple different but closely related sequential decision-making problems concurrently.
We will mostly focus on the finite-action setting. Specifically, we have T tasks, each of which is governed by an unknown linear coefficient O: R At the n-th round, for each task [T], the player chooses an action an,t that belongs to finite set, and receive a reward Tn,t with expectation Tn. (0., Fn.t.an..) where In,1,a., represents the context of action an For this problem, straightforward approach is to treat each task independently, which leads to Ö(TvdN)) total regret. Can we do better?
Clearly, the tasks are independent, then by the classical ((vdN) per task lower bound for linear bandit, it is impossible to do better. We investigate how representation learning can help if the tasks are related. Our main assumption is the existence of an unknown linear I extractor B E gd with & < d and set of linear coefficients {w, ) such that Oz Bw,, Under this assumption, the tasks are closely related as is a shared linear feature extractor that maps the raw contexts In,1.a E Rd to a low-dimensional embedding B In,t.a R In this paper, we focus the regime where l < d, N.T. This regime is common in real-world problems, e.g., computer vision, where the input dimension is high, the number of data is large, many task related, and there exists a low-dimension representation among these tasks that we can utilize. Problems with similar assumptions have been studied in the supervised learning setting (Ando & Zhang, 2005). However, to our knowledge, this formulation has not been studied in the bandit setting.
Our Contributions We give the first rigorous characterization on the benefit of representation learning for multi-task linear bandits. Our contributions are summarized below.
We design new algorithm for the aforementioned problem. Theoretically, we show our algorithm incurs Ö(VdkTN TVKN) total regret in N rounds for all T tasks. Therefore, our algorithm outperforms the naive approach with O /dN) regret. To our knowledge, this is the first theo- retical result demonstrating the benefit of representation learning for bandits problems.
To complement our upper bound, we also provide an 52( (VVdkTN +TvKN) lower bound, showing our regret bound is tight up to polylogarithmic factors.
We further design a new algorithm for the infinite-action setting, which has a regret Ö(dL- + kTVN), which outperforms the naive approach with O(TdvN) regret in the regime where T = ((dk?).
We provide simulations and experiment MNIST dataset illustrate the effectiveness of our algorithms and the benefits of representation learning.
Organization This paper organized as follows. In Section 2, we discuss related work. Sec- tion 3, we introduce necessary notation, formally set up problem, and describe our assumptions. In Section 4, we present our main algorithm for the finite-action setting and its performance guar- antee. In Section 5, describe algorithm and its theoretical guarantee for the infinite-action setting. In Section 6, we provide simulation studies and real-world experiments to validate the ef- fectiveness of our approach. We conclude in Section 7 and defer all proofs the Appendix.
RELATED WORK
Here we mainly focus on related theoretical results. We refer readers to Bengio al. (2013) for empirical results of using representation learning.
For supervised learning, there is long line of works on multi task learning and representation learn ing with various assumptions (Baxter, 2000; Ando & Zhang, 2005; Ben-David & Schuller, 2003; Maurer, 2006; Cavallanti et al., 2010; Maurer et al., 2016; Du al., 2020; Tripuraneni al., 2020).
(-) omits logarithmic factors.
2

---

Published as a conference paper at ICLR 2021
All these results assumed the existence of common representation shared among all tasks. How- ever, this assumption alone is not sufficient. For example, Maurer et al. (2016) further assumed every task is i..dd drawn from underlying distribution. Recently, Du et al. (2020) replaced the i..d. as- sumption with a deterministic assumption on the input distribution. Finally, is worth mentioning that Tripuraneni al. (2020) gave the method-of-moment estimator and built the confidence ball for the feature extractor, which inspired our algorithm for the infinite-action setting.
The benefit of representation learning has been studied in sequential decision-making problems, especially in reinforcement learning domains. D D'Eramo et al. (2020) showed that representation learning can improve the rate of approximate value iteration algorithm. Arora et al. (2020) proved that representation learning can reduce the sample complexity of imitation learning. Both works require a probabilistic assumption similar to that in (Maurer al., 2016) and the statistical rates are of similar forms as those in (Maurer et al., 2016).
We remark that representation learning is also closely connected to meta-learning (Schaul & Schmidhuber, 2010). Raghu et al. (2019) empirically suggested that the effectiveness of meta- learning is due to its ability to learn useful representation. There is line of works that analyzed the theoretical properties of meta-learning (Denevi et al., 2019; Finn et al., 2019; Khodak et al., 2019; Lee et al., 2019; Bertinetto et al., 2018). We also note that there are analyses for other rep- resentation learning schemes (Arora al., 2019; McNamara & Balcan, 2017; Galanti et al., 2016; Alquier et al., 2016; Denevi et al., 2018).
Linear bandits (stochastic linear bandits/ / linearly parameterized bandits contextual linear bandits) have been studied in recent years (Auer, 2002; Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010; Abbasi-Yadkorf et al., 2011; Chu et al., 2011; Li et al., 2019a;b). The studies are divided into two branches according to whether the action set is finite or infinite. For the finite-action setting, ((vdN) has been shown to be the near-optimal regret bound (Chu et al., 2011; Li et al., 201 9a),,,, and for the infinite-action setting, ((dVN) regret bound has been shown to be near-optimal (Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010; Li et al., 2019b).
Some previous work studied the impact of low-rank structure in linear bandit. Lale al. (2019) studied a setting where the context vectors share a low-rank structure. Specifically, in their setting, the context vectors consist of two parts, i.e. ob x+ so that is from hidden low-rank subspace and &b is i.i.d. drawn from an isotropic distribution. Jun et al. (2019) and Lu et al. (2020) studied the bilinear bandits with low-rank structure. In their setting, the player chooses two actions æ, y and receives the stochastic reward with mean x Oy, where @ is an unknown low-rank bilinear form. The algorithms proposed in the aforementioned papers share some similarities with our Algorithm for our infinite-action setting, in that both used Davis-Kahan theorem to recover and exploit the low-rank structure.
Some previous work proposed multi-task bandits with different settings. Deshmukh et al. (2017) proposed a setting under the contextual bandit framework. They assumed similarities among arms. Bastani et al. (2019) studied setting where the coefficients of the tasks were drawn from a gaussian distribution fixed across tasks and proposed an algorithm based on Thompson sampling. Soare et al. (2018) proposed a setting where tasks were played one by sequentially and the coefficients of the tasks were near in f2 distance. In our setting, the tasks are played simultaneously and the coefficients share common linear feature extractor.
PRELIMINARIES
Notation. We use bold lowercases for vectors and bold uppercases for matrices. For any positive integer n, use [n] to denote the set of integers 21, n). For any vector æ, use || to denote its Ez norm. For a matrix A, we use ||A]] to denote the 2-norm of A, || F to denote the Frobenius norm, and ||A|] mmx max,,j |Aii to denote the max-norm. For two expressions a, 3 > O. we denote a S. 3 if there is a numerical constant e > 0 such that a s c3. We denote 3 if S a.
Problem Setup. Let be the ambient dimension and k(s d) be the representation dimension. In total, we have 7' tasks and play each task concurrently for N rounds. Each task / E [T] has an
3

---

Published as a conference paper at ICLR 2021
unknown vector 0, E R.. At each round E [N] the player chooses action ax,t An, for each task t [T] where A is the action set at round n for the task t.
After the player commits to a batch of actions {an, Herry. it receives a batch of rewards (Tn, (e(()) where we assume 'n. (an,r: 0²) + Sn,t- Here we assume the noise En,t are independent 1-sub- Gaussian random variables, which a standard assumption in the literature.
We use the total expected regret to measure the performance of our algorithm. When we have N rounds and T tasks, it is defined RN.T Σn Σi= maxaeA... (a, 0₂) (an.t Qt). When the action set finite, we assume that all An.t have the same size K,i.e i.e. |AA,, = K. Furthermore, we write An, f (In,t,ly &n.t,K] J. Besides, we interchangeably use the number On,t [K] and the vector .n Bn,ta... E IRd to refer to the same action.
Assumptions. Our main assumption the existence of a common linear feature extractor.
Assumption (Common Feature Extractor). There exists a linear feature extractor B E Rddk and set of linear coefficients ) such that the expected reward of the t-th task at the n-th round satisfies E[rr.0] (w,, B Tn.t.an,))
For simplicity, we let W- (1..... Wr]- Assumption implies that O (0....., 0r] BW. Note this assumption is in a sense necessary to guarantee the effectiveness of representation learning because without it one cannot hope that representation learning helps.
In this paper, we mostly focus on the finite-action setting. We put the following assumption on action sets.
Assumption 2. Marginally, for every E [N], [T], E [K], the contexts satisfy an,ta (0 Σ,) such that Amaxx (Ex) I O(1/d) and Amin (Ex) 2 Q(1/d).
With this assumption, we have an unknown covariance matrix Σ, for each task. At each round, the actions of the t-th task are sampled from a Gaussian distribution with covariance Σ, This is prototypical setting for theoretical development on linear bandits with finite actions (See e.g., Han et al. (2020)). At a population level, each one of the K actions is equally good but being able to select different actions based on the realized contexts allows the player to gain more reward.
We will also study the infinite-actics action setting, We first state assumption about the action sets.
Assumption 3 (Ellipsoid Action Set). We assume An,: A = { Q x S 1 E Rd) is an ellipsoid with (imin(q) 2 Xo (2())
The first assumption states that each action set is ellipsoid that covers all directions. This is standard assumption, e.g., see Rusmevichientong & Tsitsiklis (2010).
In this setting, will also need to put additional assumptions on the underlying parameters B and W.
Assumption (Diverse Source Tasks). assume that Amin W )) K where v = =Q()..
This assumption roughly states that the underlying linear coefficients {wr}?=1 equally spans all directions in R This common assumption representation learning literature that enables us to learn the linear feature extractor (Du et al., 2020; Tripuraneni et al., 2020). For example, the assumption holds with high probability when w, is uniformly chosen from the sphere Sk-1,
Assumption 5. We assume
|we/|| 2 w 9(1).
This is normalization assumption on the linear coefficients.
4 MAIN RESULTS FOR FINITE-ACTION SETTING
In this section focus on the finite-action setting. The pseudo-code is listed in Algorithm 1. Our algorithm uses a doubling schedule rule (Gao et al., 2019; Simchi-Levi & Xu, 2019; Han et al., 2020; Ruan et al., 2020). We only update samples collected within the epoch. In Line 5, we solve an empirical fi-r minimization problem on the data collected in the last epoch estimate the feature extractor B and linear predictors
estimation of 0 after epoch is finished, and only use
4

---

Published as a conference paper at ICLR 2021
Algorithm 1: MI.inGreedy: Multi-task Linear Bandit with Finite Actions
1: Let M [loga log, NN. Gu 0, 9M N, Nm N1-2 for 1 I m S M 1, let 0,, 0:
2: for m f- ...... M do
&: for n f- 9m-1 + 1,...,,.. 9 do
For each task E [T]: choose action an,t = arg max aE|K] 2. n,t,o m In Ei=1 [2 Pn,taan Bw, Tn,t]=
4:
& Compute BW + arg min
BER W ERAAT
6 For each task t E [T]: let mm, Bid;
W. similar to Du et al. (2020). Given estimated feature extractor B and linear predictors W. we compute estimated linear coefficients of task O. - Bü, in Line 6. For choosing actions, for each task, we use a greedy rule, i.e., we choose the action that maximizes the inner product with our estimated 0 (cf. Line 4).
The following theorem gives an upper bound on the regret of Algorithm 1.
Theorem (Regret of Algorithm 1). Suppose T,T S poly(d) and N 2 d?. Under Assumption and Assumption 2, the expected regret of Algorithm I is upper bounded by
E| Ö(TVEN +
VVWKKN+VKKNNT vdkNT).
There are two terms in Theorem 1, and we interpret them separately. The first term Ö(TVKN) represents the regret for playing T independent linear bandits with dimension & for N rounds. This if we know the optimal feature extractor, with which we can
is the regret need to pay reduce the original problem to playing T i'ndependent linear bandits with dimension k (recall wy are different for different tasks). The second term O(Vdk VT)NT) represents the price we need to pay to learn the feature extractor B. Notably, this term shows we are using data across all tasks to learn B as this term scales with VNT.
Now comparing with the naive strategy that plays T independent d-dimensional linear bandits with regret (dT) upper bound is smaller as long as T 2(()). Furthermore, when T is large, our bound is significantly stronger than ddN), especially when k d. To our knowledge, this is the first formal theoretical result showing the advantage of representation learning for bandit problems. We remark that requiring = (2k) is necessary. One needs least ie tasks recover the span of W, only in this regime representation learning can help.
Our result also puts a technical requirement on the scaling K,T S poly(d) and N 2 dZ These are conditions that are often required in linear bandits literature. The first condition ensures that K and are not too large, so we need not characterize log( ((T) factors regret bound. If they are too large, c.g. K,T l(e"), then would have log KT (dd) and we could no longer omit the logarithmic factors in regret bounds. The second condition ensures one can at least learn the linear coefficients up constant error. See more discussions in (Han et al., 2020, Section 2.5).
While Algorithm is a straightforward algorithm, the proof of Theorem requires a combination of representation learning and linear bandit techniques. First, prove the in-sample guarantee of representation learning, as done in Lemma 2. Second, we exploit Assumption 2 to show that the learned parameters could extrapolate well analysis then follows naturally. We defer the proof of Theorem 1 to Appendix A.
contexts, as shown in Lemma 4. The regret
The following theorem shows that Algorithm is minimax optimal up to logarithmic factors.
Theorem 2 (Lower Bound for Finite-Action Setting). Let A denote an algorithm and I denote finite- actiinedt multi-task linear bandit instance that satisfies Assumption and Assumption Then for any N. d, k EEEEZ 2 with k < d, k < T, we have
inf sup E RR St (TVEN + VakNT
A I
Theorem 2 has the exactly same two terms as in Theorem 1. This confirms our intuition that the two prices to pay are real: playing 7 independent k-dimensional linear bandits and 2) learning
5

---

Published as a conference paper at ICLR 2021
Algorithm 2: TCTC:
Seplore-Then--- Chem-CCommit
Input: N: total number of rounds, N1: number of rounds for stage 1, N2: number of rounds
for stage 2
1: Stage 1: Estimating Linear Feature Extractor with of
2: for Vt. E [T), E [11] do
3: Play Tn.t Uni (d-1) and receive reward Tn,ti
4: Compute M <- 1
NIT Σm Et= "n,
*: Let TD + top-k singular value decomposition of M. Denote b, the i-th column of B;
& Stage 2: Estimating Optimal Actions on Low-dimensional Space;
7: for Vt E [T], E [k] do
N 8: Play V2, A VAgb; for N2/k times and receive rewards {In,t I n +0- (120)--111--1111
9: for Vt E [T'] do
N2 No Estimate w. arg min wERK 2N No ( Bw) Tn,al
Let 0, Bw,; Bu;;
Stage 3: Committing to Near-optimal Actions;
is for Vt E [T), N1 + N2 + I.....N do
14:
Play an,1 5- arg aEA, (a, 0,) and receive reward fn,ti
the d x k-dimensional feature extractor. We defer the proof of Theorem 2 to Appendix B. At a high level, separately prove the two terms in the lower bound. The first term established by the straightforward observation that our multi-task linear bandit problem is at least as hard as solving T independent k-dimensional linear bandits. The second term is established by the observation that multi-task linear bandit can be seen as solving k independent d-dimensional linear bandits, each has NT/k rounds. Note that the observation would directly imply the regret lower bound k d(NT/A) = v dR,T, which is exactly the second term. To our knowledge, this lower bound also the first of its kind for multi- task sequential decision-making problems. We believe our proof framework can be used in proving lower bounds for other related problems.
EXTENSION TO INFINITE-ACTIO SETTING
In this section we present and analyze an algorithm for the infinite-action setting. Pseudo-code is listed in Algorithm 2. Our algorithm has three stages, and explain each step below.
Stage 1: Estimating Linear Feature Extractor with Method-of-Momenn stage is to estimate the linear feature extractor B. Our main idea to view this problem rank estimation problem for which we use method-of- this sampling scheme because the sample each Fn,t [ni 3d for N₁ times. We action set is an ellipsoid. Note this sampling scheme has a sufficient coverage on all directions, which help us estimate B. Next, we compute the empirical weighted covariance matrix M NT ΣN ΣT n2 "n, To proceed, we compute the singular value decomposition of M and keep its top-k column space accurate estimator (cf. Theorem 5).
The goal of the first
low- estimator. In more detail, we first
estimated linear feature extractor B, which is sufficiently
Stage 2: Estimating Optimal Actions Low-Dimensional Space. In the second stage, our estimated linear feature extractor to refine our search space for the optimal actions. Specifically, we denote B [b.....,br, and for i [k] and t E [T], we let ot,; Vdpb;. Under Assumption 3, we know 24 A, for all i [R... Therefore, we can choose Vt,; to explore. Technically, our choice _ BT v,,,V,,.. 2 Ap-
of actions v also guarantees sufficient cover the sense that Amin In particular, this coverage is on low-dimensional space instead of the original ambient space.
The second stage has N₂ rounds and on the t-th task, we just play each v,,; for N2 rounds. After that, we use linear regression to estimate w. for each task. Given the estimation Wi, we can obtain an estimation to the true linear coefficient 0 2 Biö

---

Published as a conference paper at ICLR 2021
k
k = 10
h: =
15
400
Regret per FANK
350
3300
250
MLinGreedy
200
Naive
10
20
50
10
20
40
50
10
20
40
T: Number of Tasks
Figure 1: Comparisons of Algorithm with the naive algorithm for d = 30 on synthetic data.
k
=
300
Regret per FISK
250
200
MLinGreedy
Naive
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
T: Number of Tasks
Figure 2: Comparisons of Algorithm with the naive algorithm for d 20 on synthetic data.
Stage 3: Committing to Near-Optimal Actions. After the second stage, we have an estimation
O, for each task. For the remaining (N N₁ N2) rounds, we just commit to the optimal action indicated by our estimations. Specifically, we play the action an,t arg max (a,, 0₂) for round = N1 + N2 + I.
The following theorem characterizes the regret of our algorithm.
Theorem (Regret of Algorithm 2). If we choose N1 = cid--5k/ k and N2 = V for some constants C1, C2 0. The regret of Algorithm 2 is upper bounded by
= O + ATVNN.
The first term represents the regret incurred by estimating the linear feature extractor. Notably, the term scales with vTN, which means we utilize all TN data here. The first term scales with di.5%, which we conjecture is unavoidable at least by our algorithm. The second term represents playing I' independent k-dimensional infinite-action linear bandits.
Notice that if one uses standard algorithm, e.g. the PEGE algorithm (Rusmevichientong & Tsit- siklis, 2010), to play T tasks independently, one can achieve an (dT regret. Comparing with this bound, our bound's second term is always smaller and the first is smaller when ((kk?). This demonstrates that more tasks indeed help learn the representation and reduce the regret.
We complement our upper bound with a lower bound below. This theorem suggests our second term is tight but there still a gap in the first term. We leave it open problem design algorithm to match the lower bound or to prove a stronger lower bound.
Theorem (Lower Bound for Infinite- Action Setting). Let A denote an algorithm and I denote an infinite-action multi-task linear bandit instance that satisfies Assumption I, A Assumption 3, Assump- tion 4, Assumption Then for any N.T, I, d, l zt with & < d, lo S T, we have
inf sup E RNT.
(dVENT +TTVN)
(2)
A I

---

Published as a conference paper at ICLR 2021
100
k
k = 8
= 16
10
Regret 66
6-
MLinGreedy Naive
4
2-
2
x10
N: Time Horizon
x x10"
x x10
Figure 3: Comparisons of Algorithm with the naive algorithm for T 10 on MNIST
x 10
k
Regret
MLinGreedy Naive
2-
1-
0
2
3
4
0
0
2
x 107
N: Time Horizon
x x10
x10*
Figure Comparisons of Algorithm I with the naive algorithm for T 45 on MNIST. EXPERIMENTS
6
In this section, demonstrate the effectiveness of our Algorithm for the finite-action setting. We also have simulation studies for the infinite-action setting, which we defer to Appendix F. The baseline is the naive algorithm which plays T tasks independently. and for each task, thie algorithm uses linear regression estimate 0g and choose the action greedily according the estimated 0,.
synthetic data and MNIST data to illustrate theoretical findings and
6.1 SYNTHETIC DATA
Setup. The linear feature extractor B is uniformly drawn from the of d k matrices with orthonormal columns.? Each linear coefficient w; is uniformly chosen from the k-dimensional sphere. The noises are i.i.d. Gaussian: tn, NO, 1) for every n E [N], [T], [K]. We fix K = 5 and N = 10000 for all simulations on finite-action setting. We vary k and T to compare Algorithm and the naive algorithm.
Results and Discussions. We present the simulation results in Figure and Figure 2. We emphasize that the y-axis our figures corresponds to the regret per task, which is defined as N.T /T. We fix K K==,, 5, N 10000. These simulations verify our theoretical findings. First, as the number of tasks increases, the advantage of our algorithm increases compared to the naive algorithm. Secondly, we notice that as & becomes larger (relative to df, the advantage of our algorithm becomes smaller. This can be explained by our theorem that as & increases, our algorithm pays more regret, whereas the naive algorithm's 's regret does not depend on k.
6.2 FINITE-ACTION LINEAR BANDITS FOR MNIST
Setup. We create a linear bandits problem on MNIST data (LeCun al., 2010) to illustrate the effectiveness of our algorithm on real-world data. We fix K 2 and create T (20) tasks and each task is parameterized by pair (i,j), where 0 < < j < 9. We use D; to denote the set of MNIST images with digit i. At each round n E [N], for each task (i,j), we randomly choose one picture
We uniformly (under the Haar measure) choose random element from the orthogonal group O(d) and uniformly choose of its columns generate B.
8

---

Published as a conference paper at ICLR 2021
from D, and one from D,, then we present those two pictures to the algorithm and assign the picture with larger digit with reward 1 and the other with reward The algorithm is now required to select an image (action). We again compare
algorithm with the naive algorithm.
Results and Discussions. The experimental results are displayed in Figure for T 10 (done by constructing tasks with first five digits) and Figure 4 for T = 45. We observe for both T 10 and T= 45, our algorithm significantly outperforms the naive algorithm for all k. Interestingly. unlike our simulations, we find the advantage of algorithm does decrease as increase k. We believe the reason is the optimal predictor is not exactly linear, and we need to develop an agnostic theory to explain this phenomenon, which we leave as future work.
7 CONCLUSION
We initiate the study on the benefits of representation learning in bandits. We proposed new al- gorithms and demonstrated that in the multi-task linear bandits, if all tasks share a common linear feature extractor, then representation learning provably reduces the regret. We demonstrated empir- ical results to corroborate our theory. An interesting future direction to generalize our results to general reward function classes (Li al., 2017: Agrawal et al., 2019). In the following, discuss some future directions.
Adversarial Contexts For the finite-action setting, we assumed the context are i.i.d. sampled from a Gaussian distribution. In the bandit literature, there large body on developing low- regret algorithms for the adversarial contexts setting. We leave it as open problem to develop algorithm with Ö(TVKN VdkNT) upper bound or show this bound is not possible in the adversarial contexts setting. One central challenge for the upper bound is that existing analyses for multi-task representation learning requires i.i.d. inputs even in the supervised learning setting. Another challenge is how to develop confidence interval for an unseen input in the multi-task linear bandits setting. This confidence interval should utilize the common feature extractor and is tighter than the standard confidence interval for linear bandits, e.g. LinUCB
Robust Algorithm The current approach is tailored the assumption that there exists common feature extractor. One interesting direction is to develop robust algorithm. For example, consider the scenario where whether there exists a common feature extractor unknown. We want to de- velop an algorithm with regret bound as in this paper when the common feature extractor exists and gracefully degrades the regret T independent linear bandits when the common feature extractor does not exist.
General Function Approximation In this paper, we focus on linear bandits. In the bandits litera- ture, sublinear regret guarantees have been proved for more general reward function classes beyond the linear one (Li et al., 2017; Agrawal et al., 2019). Similarly, in the supervised representation learning literature, general representation function classes have also been studied (Maurer et al., 2016: Du et al., 2020). An interesting future direction is to merge these two lines of research by de- veloping provably efficient algorithms for multi-task bandits problems where general function class is used for representation.
ACKNOWLEDGMENT
The authors would like thank the anonymous reviewers for their comments and suggestions on our paper. is supported by NSF, ONR, Simons Foundation, Schmidt Foundation, Amazon Research, DARPA and SRC. JDL acknwweddes support of the ARO under MURI Award W91 11-1-000, the Sloan Research Fellowship, and NSF CCF 2002272.
REFERENCES
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. selectiin Operations Research, 6755) 2019.

---

Published as a conference paper at ICLR 2021
Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret bounds for lifelong learning. arXiv preprint 9rXiv:1610.08623 2016.
Rie Kubota Ando and Tong Zhang. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research, 6(Nov):1817-1853, 2005.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Sanjeev Arora, Simon $ Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable represen- tation learning for imitation learning via bi-level optimization. arXiv preprint arXiv:2002.1 10544, 2020.
Peter Auer. Using confidence bounds for exploitaiion-exploraiion trade-offs. Journal of Machine Learning Research, 3(N4v):397-422, 2002.
Hamsa Bastani, David Simchi-Levi, and Ruihao Zhu. Meta dynamic pricing: Learning across periments. arXiv preprint arXivv 10918, 2019.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Shai Ben- BeviDavid and Reba Schuller. Exploiting task relatedness for multiple task learning. Learn- ing Theory and Kernel Machines, pp. 567-580. Springer, 2003.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 7888,187, 2013.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-leaming with differ- entiable closed-fome form solvers. arXiv preprint arXiv:1805.081.3. 2018.
Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
Rich Caruana. Multitask learning. Machine learning, 2811):1177,, 1997.
Giovanni Cavallanti, Nicolo Cesa-Bianchi, and Claudio Gentile. Linear algorithms for online mul- titask classification. Journal of Machine Learning Research, (((Occt:2901-2933)) 2010.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. 2011.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade, Stochastic linear optimization under bandit feedback. In COLT, 2008.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to learn with statistical guarantees. arXiv preprint / /80308808, 2018.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-learn stochastic gradient descent with biased regularization. In Proceedings of the 36th International Conference on Machine Learning. 2019.
Carlo D' Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Sharing knowl- edge in multi-task deep reinforcement learning. International Conference on Learning Repre- sentations, 2020. URL https: : / /pwereveiiiveeeeeeeeeeeeeeeeeeee ew nwt.//ee//eeee wwrumfrruuoooooo (itammmmd==rre dtt.rmm2vv.rrr
Aniket Anand Deshmukh, Urun Dogan, and Clay Scott. Multi-task learning for contextual bandits. In Advances neural information processing systems, pp. 4848-4856, 2017.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09434 2020.
Kai Wang Fang. Symmetric multivariate and related distributions. CRC Press, 2018.
10

---

Published as a conference paper at ICLR 2021
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-leaming. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Tomer Galanti, Lior Wolf, and Tamir Hazan. A theoretical framework for deep transfer learning. Information and Inference: Journal of the IMA, 5(2):159-209) 2016.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. In Advances Neural Information Processing Systems, pp. 503-513, 2019.
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits. arXiv preprint 2rXiv:2004.06331, 2020.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojeiech Czamecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 33, pp. 3796-3803, 2019.
Irina Higgins, Arka Pal, Andrei Rusu, Loic Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, and Alexander Lerchner. Darla: Improving zero-shot trans- fer in reinforcement learning. In Proceedings of the 34th International Conference on Machine Searning-Volume Volume 70, pp. 1480-1490. JMLR. org, 2017.
Learning-
Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low- rank structure. In International Conference on Machine Learning, pp. 3163-3172, 2019.
Mikhail Khodak, Maria AaorinFlorina Balcan, and Ameet Talwalkar. Adaptive gradient- based meta- learning methods. arXiv preprint arXiv:/906.02711 2019.
Sahin Lale, Kamyar Azizzadenesheli, Anima Anandkumar, and Babak Hassibi. Stochastic linear bandits with hidden low rank structure. arXiv preprint arXiv: 190100990 2019.
Alessandro Lazaric and Marcello Restelli. Transfer from multiple mdps. In Advances in Neural Information Processing Systems, pp. 1746-1754 2011.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecue www.:..c....c..co..o.ee wwtp//////////ist...ommm 2, 2010.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 10657-10665, 2019.
Lihong Li. Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In Proceedings of the 34th International Conference Machine Learning-Volie Volume 70, pp. 2071-2080 JMLR.org, 2017.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pp. 2173-2174, 2019a.
Yingkai Li, Yining Wang, and Yuan Zhou Tight regret bounds for infinite-armed linear contextual bandits. arXiv preprint (tt.:1905.04440 2019b.
Lydia T Liu, Urun Dogan, and Katja Hofmann. Decoding multitask dqn in the world of minecraft.
In The 13th European Workshop on Reinforcement Learning (EWRI.) 2016, 2016.
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari, Low-rank generalized linear bandit problems. arXiv preprint arXiv:2006.02%4 2020.
Andreas Maurer. Bounds for linear multi-task learning. Journal of Machine Learning Research, 17-1): 2006.
11

---

Published as a conference paper at ICLR 2021
Andreas Maurer, Massimiliano Pontil, and Bernardino Komera-Paredes.. The benefit of multitask representation learning. The Journal of Machine Learning Research, 17(1):2853-288 2016.
Daniel McNamara and Maria-Florina Balcan. Risk bounds for transferring representations with and without fine-tuning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2373-2381. JMLLR. JMLR. org, 2017.
Emilio Parisotto, Jimmy Lei Ba, and Ruslan Salakhutdinov. Actor-mimic: Deep multitask and transfer reinforcement learning. arXiv preprint arXiv:151 2015.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse?
towards understanding the effectiveness of maml. arXiv preprint htt.:/99999.999 2019.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distri- butional optimal design. arXiv preprint urXiv:2007.01980 2020.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Operations Research, 35(2):395-411, 2010.
Mathematics of
Andrei Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirk- patrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distil- lation. arXiv preprint arXiv:1511.06295, 2015.
Tom Schaul and Jürgen Schmidhuber. Metalearning. Scholarpedia, 5(6):4650, 2010.
David Simchi-Levi and Yunzong Xu. Phase transitions and cyclic phenomena in bandits with switch- ing constraints. In Advances Neural Information Processing Systems, pp. 7523-7532, 2019.
Marta Soare, Ouais Alsharif, Alessandro Lazaric, and Joelle Pineau. Multi-task linear bandits. 2018.
Matthew Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(Jul): (03Jl))1633-1600 1685, 2009.
Yee Teh, Victor Bapst, Wojeiech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In Advances in Neural Information Processing Systems, pp. 4496 4566, 2017.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations.
arXiv preprint arXiv:2002.11684 2020.
Roman Vershynin. High digh-ddimessooal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Zirui Wang, Zihang Dai, Barnabás Póczos, and Jaime Carbonell. Characterizing and avoiding nega- tive transfer. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1129--1330 2019.
12

---

Published as a conference paper at ICLR 2021
A PROOF OF THEOREM
Lemma (General Hoeffding's s inequality, Vershynin (2018), Theorem 2.6.2). Let Xi.... Xn be independent random variables such that E[[;] = 0 and X; is Py-sub-GGussiian Then there exists constant e > O, such that for any > O, we have
n X
Pr
Σ of log (1/8)
8.
(3)
Lemma 2. Let be the number of tasks and No be the number of samples. For every (n, t) E [No] x [T), let In.t E Rd be fixed vectors and let Yn. x En,t. where 0₂ E R is vector and Eng is an independent
variable. Let
No
BW
arg min
Σ
Bü, yn
(4)
BEROXA W WEREXT X
R=
where W (wi
Tr.. Then with probability 8, we have
No
T
Σ
n, (Bw, Bwx))2 $ (dk + log((TTg + log(1/0).
n=1 1=1
Proof. By (4), we have
nn Bw, vn.ol²
- Bw, vn.1l²
t=1
==1 1=1
Since Un.t = TT, Buy + En,to we have
Σ
mn BB: Bw,) + +n, 5
t=
n=1 t=1
which implies
T
No T
T (Bw. Bw:))² <
28n a n (Bw; Bw.).
(5)
12 tm
Next bound the right-hand side of (5) via uniform concentration argument. We let
B = (B's E Rack
|B Imaxa 1)),
= W= E R
[ max 1).
For any fixed matrices B' E B, W W, we write W (wi w'r) and define
Bn (B', W') 2$ t0 B' Bw.).
Note that ( W is an independent sub-Gaussian variable with sub-Gaussian norm Tx B''w' Bw,). By the general Hoeffding's inequality (Lemma 1), with probability 1 - 5, we have
To,iB'' W') S Vf(B', W') log(1/),
(6)
N T
where f(B', W') =
ΣΣ
x Th, (B'w;, Bw,)
n=1
Next apply the e-net. Let B' = NBB I1-llmxx e), W" = N(W, 11 Illae E). Applying union bound over B' x W for (6), we have
No
Pr (BB
ΣΣ
na Vf(B', W') 21- WW
13

---

Published as a conference paper at ICLR 2021
Since f(B', W is (BNTdk))Lipschitt with respect to || we have
No T
Pr A B' W J
EBEX W
Σ
Mntt & Vf(B', W log(1))) + 24NTcke 2 21 - 21-8 x WI
Note that 134|
O((1/e)ah) dk) and [W| 0((1/6)/T). Let 8 6o/1B' W and
(24NTdk) -1 We have
Pr V (B', E
Nott & VJ(B', [') + KT) (NT()) + log(1/6o)]
-1-6 -dp-
Now assume that the above event holds. Combining (5) and (7), we have
Pr F W) S Vikk KT) log (NoggNNTdb))) + log(1/)))
Pr
Pr [ W (B, [(dk KT) log(NTdk)) log(1 (1/66)]
2 1 8u.
which proves our lemma.
Lemma 3. With probability 1 O((NT) 3), for every E [M], [2], we have
Gm
gm 9m-1
Amin
Dn,t.on. Dn.tann
n=
Proof. The proof can be done by following the proof of Lemma in Han et al. (2020).
Lemma 4, For each epoch E [M], with probability 1 - O((NTT))), we have
BW - BWl (dk: + AT) log(Tdk)) + log(1/6)
(9m 9m-1)/d
where B, W are computed at Line 5 in Algorithm 1.
Proof.
Placing No 9m 9m-1 in Lemma 2, with probability 1- (((NT))))) have
9m
T
c ant,a
BBo Bux))) $ (dk- + KT) (og((Ndk))
(8)
By Lemma 3, with probability 1 O((NT)- we have
Gm
Σ
ap.ttaan. (Bw, Bw:))²
1==m-11
Bw: Bwi)
In,laan, Int.ant
(Bw: Bw.)
pm
Bw, Bwi) Im gm-1
Bid Bw:)
G Gm-1
BW BW
(9)
d
We conclude by combining (9) with (8).
14

---

Published as a conference paper at ICLR 2021
Let
Gm
T
Rm
max Ln,t,a 01) (an,taan.e 01)
aE[K]
n Om
1+1
be the regret incurred in the m-th epoch. We have the following lemma. Lemma 5, We have
B[Rml & (vNTdk + (og (og(NNTd)))))
Proof. At round n that belongs to epoch m, for task i, we have
max 0, (In,ta kn,t.an.)) S max {0, (In,t. In,t,an.e) 10--0111-0 (,h,,,,,,, Bn,r,a)) aE(K]
= max (0, 0m-1,)) Iniia + (0m-1. - -1) In,tann aEKK]
S 2 max
(0: - 1,- 1,,,,,,,,ttaa xn,tia
KE[K]
By Assumption 2 and union bound over K actions, T tasks, and (9m 9m-1) rounds, we have with probability (NKT) 2, for every n (9m-1: 9m] and t [T).
(Ng(NKT)
max aE aE[K]
(0. - 1,1) an,t. $ 0, 0
(10)
d
Using union bound over (10) and Lemma 4, with probability 1 - ((NN)) 3), the regret incurred in the m-th epoch is
9m
T
B Bm S
Σ
max
0,
(In,1.a In.t,an,)
aE[K]
n Sm
1+1
T
log(NKT)
log(NKT)
S 19mm 9m-1)
Σ
02
0 0m-200
9m VT Ô
F
t=1
(11)
(dk + KT) (Tgk)
(og(NKT)
9m VT
(12)
(Gm-1 2)
d
(Nk + KT) log(NTdk) (KT
(13)
(VNT TVKN) (oT() log(lo (NKT),
where denote C (#m-1.1
θm-1.) (11) and the second inequality in (11) uses
Cauchy, (12) uses Lemma 4, (13) uses Gm- < 9mm Gm- and 9m/9m-15 S /N. Since that the above bound holds with probability O((N)) and that the regret is bounded by NT, we prove the lemma.
Proof of Theorem 1. The regret is bounded by
N.
E B $ M M(NNTdk + Llogk))ooooo/oll log(NKT)
m=1
= (VNTdk + DVVTE/H+TTTVV//////TV////d/L/// log log N.
B PROOF OF THEOREM 2
In this appendix, we assume that E, = in Assumption 2 and that all noises are gaussian, ie. Eng NN for all [N), / (7].
15

---

Published as a conference paper at ICLR 2021
For each task & [T], we denote the regret incurred on task as
RNO
max (En,t,a 01) (anttaame Oz).
aE[K]
We divide Theorem 2 into the following two lemmas.
Lemma 6. Under the setting of Theorem we have sup, N. (TTVKN). Lemma 7. Under the setting of Theorem 2, we have inf supu E A.I 2 2 (dkNT).
Proof of Theorem 2. We combine Lemma 6 and Lemma 7.
Our proofs to the lemmas will be based on the lower bounds for the (single-task) linear bandit setting, which corresponds to the T = 1 case in multi-task setting. For this single-task setting, we assume = and B = Ia- We write the regret as RN = RM.. and call algorithms for the single-task setting as single-task algorithms.
Lemma 8 (Han et al. (2020), Theorem 2). Assume N de and d 2. Let Nu, E) be the multivariate normal distribution with mean μ and covariance matrix E. There is a constant C > O, such that for any single-task algorithm S, we have
EIR CVaN, ||wl|
sup
where I is the instance with hidden linear coefficients
Next we use it to prove Lemma 6 and Lemma 7. The main idea to prove Lemma 6 is to note that we can treat our setting as T independent k- k-dimensional linear bandits.
Proof of Lemma 6. Suppose there is an algorithm A that achieves supy B N.T we have
A. S CTVKN. Then
sup E
Σ
A.
N.T I Sup
CTVEN.
Therefore, there exists [T'] such that
sup
R
N.0
1 T
CTVEN = CCEN,
which contradicts Lemma 8.
Proof of Lemma 7. Suppose there is an algorithm A that achieves sup, EI S CVdKNT. We complete the proof separately, based whether A I _g not. Note that when 2. the lower bound Lemma 6 becomes C(TVv: ((T ANN). Since T 2 k, we have V S TVaN. Thus conclude by Lemma 6.
In the remaining, we assume < Without loss of generality, we assume that is even and that 2k divides T'. For I,..., kt we denote the regret of group i
ST/k Σ
R
N.(C)) AI
AA
(ii-I)//k41
We consider instances such that tasks from the same group share the same hidden linear coefficients 0,. Since there are & groups, we have
sup 0.
E
Σ
R
N.O AA
< R N.T
& CVOKNT.
(14)
16

---

Published as a conference paper at ICLR 2021
Therefore, there exists group
[k] such that
dNT CVAKNT CC k
(O) AI
sup E I
(15)
which means that the regret incurred in group i is less than C MVdNN/k. Since the tasks in group i share the same hidden linear coefficients, they could be regarded as one large linear bandit problem. Since there T/k tasks in group the large linear bandit is played for N T/k rounds. By Lemma the algorithm A must have incurred C ddNTT/ regret on group i, which contradicts with (15).
C METHOD-OF-MOMENT ESTIMATOR UNDER BANDIT SETTING
The following theorem shows the guarantee of the method-of sooood-of-oomeee momemts (MoM) estimator used to find the linear feature extractor B. In this appendix, for matrix B with orthogonal columns, we write B to denote its orthogonal complement matrix matrix whose columns the orthogonal complement those of B).
Theorem (MoM Estimator). Assume N,T Z polylog(N,, T)
We have with probability at Age
least 1 (N,
d'-sk k
B B
B S 5
(16)
A N
The theorem guarantees that our estimated B is close to the underlying B in the operator norm so long as the values N, and are sufficiently large. We add a remark that our theorem is similar to Theorem 3 in Tripuraneni et al. (2020). The key differences are: (i) we use uniform distribution to find the feature extractor, while they assumed the input distribution standard dddimensiinal Gaussian; (ii) the SNR signal-to-noise ratio) in linear bandit setting is worse than that in their supervised learning setting, and thus we get an extra factor in our theorem.
In the sequel, prove the theorem.
Lemma (Hoeffding). Let EI, be i.i.d. 1-sub- Gaussian random variables. We have
Pr
Σ E.
Ex,) 2
2e
Lemma 10 (Matrix Bernstein's inequality, Vershynin (2018), Theorem 5.4.1), Let X1,..., Xm Rdxd be independent, mean zero, symmetric random matrices that X, < M almost surely for all i E [m]. Let o² | x?1
We have
82/2
Pr
x
8
<
2d 2de
M5/3
Equivalently, with probability at least
8, we have
m
Σ X;
S v 02 log(d/8) + M log(d/8).
Lemma 11 (Moments of Uniform Distribution on Sphere). Let a Unil(gd-1) be a uniformly 15
chosen unit vector. We have Exf Z(r2))d=4) Ext 2(d+2) Exf 3. Moreover, we have
Ext03 ((4+))
Proof. We need to recall the fact that when x ~ Ud its coordinate x; follows the Beta distribution: اnيh ~ Beta( d=1 1))). Then we prove the lemma by noting the moments of the 2
Beta distribution (Fang, 2018).
17

---

Published as a conference paper at ICLR 2021
Corollary 6 (Uniform Distribution on Sphere), Let Unif(s be uniformly chosen unit vector. We have the following statements.
(a) IE (z, xxxx T
200" +1
d(d+2)
(b) E (x,, 0) axxx 2[d+2)d+4]
1200 4-3 +31
Proof. Le (1,0,.... I2 be the unit vector. For (a), note that
i.j * and i indiig J.
0,
i= 1 + j
= x
(E (a,, 2x) )5 Exjazz
i i=
a(d+2)
i i=j=
d(d+2)
Therefore, we have Ea e1) 2rxx ] a(442] @Z + I). By the isotropy (rotation invariance) of uniform distribution, we have
(r,, 2mar
(200 I) d(d + 2)
For (b), note that
0,
i.j + 1 and + j. i= + or joj j= i
0,
(E (xx, e1) xx" Dis E Eajar
i= # 11,
M(++21d+1)
15
i=j=1
2(d+)](d44)
Therefore, we have E (a, e Aax = J(0+2((41)) (12e)e) +3I). By the isotropy, we have
1
E (x, xxx
d(d + 2) 11200 +I).
Let An,t = = n, M = NTT En ΣT= An,t We decompose M into three terms M
M + M2 + +M,, where
N1
M
Kn.t 2
NT #=1
M2
1
Σ
Σ
n (In,1, 0z) 0.)
N,T
N.
1
M.
2
NJT
Let Aim 1
NiT (In,t, 0 T. Next we analyze each error |M, - E. M.
Lemma 12. With probability least 1
N.T have
log(dN,7
log (g(N)TT N.T
|| EMISS
NN
Proof. We have
120.0. +II NPT2 (I , 0,) I d(d + 2) d + 4)N
A2 int
Using Lemma 10 with m = NIT, M 1 0² S m
we have with probability
N.T
NNTT TM.T
at least 1 N.TD
log(dN,T)
log(dN(T)
M EEMIS
N.
N.T
18

---

Published as a conference paper at ICLR 2021
Next analyze the errors of M2 and Mg. Since these errors contain the unbounded sub- Gaussian terms En,t, we need to cut their tails before applying the matrix Bernstein inequality. Define e,,
En, 14 En,el I RR. We have
E EEn, E
- E E > R}
> R /
R- Pr-ernlen.l
Pr[lenal > x) dx
R²
+00
2RE
+
2e dx
R
1
$ 2
|e
2
R
Let "1,, = = 1[ss,, S RJ. We have
E B REE, S RE 1| R²}
R²] + f +o0
= Pr(c", m,t
.
Pr(en. > x)) dd
+00
S SRRe 7
2e $ dd.
< (2R² + 4)e
#2
Define
1 T
M2
28 (I 11)
N.T
T
1
M
2n at TT,
NIT
Lemma 13. With probability at least 1 - (N1T) 33, we have
log(dN(7)
R Rlog(dNN
[ - EEMEI
dN,,T
N,T
Proof. Let Aznt 1 20 e to We find that
N.T
4E (5'N,,)²
E (o 0,) 4E(( 20,0, +I
E A2
2nd
NJT2
NºT2 2)
We conclude by using Lemma 10 with m N,T.M .
02 S m
PNTT= d'N,T"
Lemma 14. With probability least 1 (N1T) 3, we have
||M EMII $ log(dN(T) R2 log(dN,7)
dN,T
N,T
Proof. Let Agnt
N.T "" In We find that
EE (E!!_))
E 22
A2 2nt
E t0 n,t
N7T2
N²T2 d'
We conclude by using Lemma 10 with m N,T,M
n² NIT.
0² S m. aNF12 dN
Lemma 15. With probability least 1 (N₂T) 2, we have
log(dN,T)
log (dN,T) N.T
MM- E M S
dN,T
19

---

Published as a conference paper at ICLR 2021
Proof. Let R v log(NNT)) With probability at least 1 1 ( have [xn I R for every n E [N1] and E [T). Note that in this case, we have M2 = M2 and M3 = M Using a union bound over Lemma 12, Lemma 13, and Lemma 14, we have with probability at least (N1T)*
M E M ||
Σ | IE Mil II + M IE M2 + MM IE M3
= | M IE M1| + M E3 M2ll |M3 E M&ll
- M TE Mill + | - MM2 + |E M -
+ IMM E MIll Il + |E JEM' - IE M3
log(dN,T)
2 (dN,T)
dN.T
N,T
Proof of Theorem 5. We note that 0++1 OK+I M) M) S | Under Assumption 3, we have
2Ao 00 +al,, M
M
MM; ca
d(d + 2)T
where C12 C3 E R are constants. Since
0x 0 - ok+1 (- oxl WWT)= k²' 00
we have
Ag d2k
Th (EM) ok+1 (E (EM)
x
Assume 7 2 polylog(N1, T) so that we have with probability at least (N1T)
E|| <
Age 2P
Together with Davis-Kahan sin theorem,
100
B
EB
B B
(17)
(E 0
M)
(E
M)
|
E
E
O+ M)
(E M)
E
/pv/d2k
d2k
log(dN,T)
(dN,
dl.5k
polylog(d, N, N,T),
dN,T
NrT
VN,T
where (17) uses the Davis-Kaie Kahan sin 0 theorem (Bhatia, 2013, Section VII.3).
D PROOF OF THEOREM
Our proof is similar to the proof of Theorem 3.1 of Rusmevichientong & Tsitsiklis (2010).
Lemma 16 (Rusmevichientong Tsitsiklis (2010), Lemma 3.5), For two vectors u, E Rdd we have
2 2
||u|||
||
max
[4/11 |
Lemma 17. Let 24 arg max max (or, Q.). We have
max (x., 0.) - (Ire 0.) < 0 0,12
#EA,
|0.11
20

---

Published as a conference paper at ICLR 2021
Proof. For 0 IRd, we define fo( maxaEA, (a, 0). Let xi = arg 2 (xr, 01). Then have
max (z, 01) (x),, 02) (x) Ft, 01) [ي] 0 0.) + (a) I1, 0²) -xx 0: 02) mE
S (aj 0, - 0.) + (ot, 0: 02) = ( - xc. 0,
O.)
0, fe
0,
(I((O.) (O))), O. 0.) (fel
0, 0.)
10:11
10.
O:
O₂
0,
0.
S [[fe( |0+11
Je(
|||
0,0, 0.11 - J|l
110, 0.11
|01l
00:1
||0+1
(18)
10: 0r11
- 2J
(19)
||0||l
where the first inequality in (18) uses Cauchy and (19) uses Lemma 16.
Lemma 18. For each task t E [T]. we have EllO, 0el1²
N +
B
Proof. We define 0 -B 0.. Note that 0, + BI. We have
0, 0.-0: = Bw; (BB 0. + B B])o.
B(w; - B 0.) B B Bw.
Note that B is perpendicular B1 and that | = 1. We have
10, - 0.11 = [( - TT,1I+ + B B Bw: 1 < 1 TTO.11 B Bl
Let U. Voobi. The OLS estimator is given by
No+1
N
01
Σ
B Toe B
Σ
B TRnntin
N1+1
Ni+1
Ni N
Ni+
Σ
B Fa
Σ
BT nn, ( But + Ent)
N=
N=N++1
N1+N
-1
N1+No
w/
Σ
B
Σ
B En.t
R=
DE N1+1
Write A = 2n=Ni+1
N2+ B
TT B.
Ni N2
E 11;- w1,12 =
Σ
x T, BB
En,1 E
N=
N1+N,
k22
Σ
BA-
In,t S N2 No
)2
No
A3.22
+1
Putting together, we have
E - -0,1 <
N2 + B B
21

---

Published as a conference paper at ICLR 2021
Proof of Theorem 3. Note that J (1) under our assumptions, as indicated by Rusmevichientong & Tsitsiklis (2010). So we have
Ni N2).J E 0z|
B[R S TN TN2 + T(N
0
B B + k2 (12
S TN + 2 + TNJ
dº
log'(N)) (NT) + TN k2
5 TNN: + 2N2 + TN
log
NJT
N2
STN Nd
log'(NT) + TN2 + TN k.
N1
N2
S
(NT) + NTVN.
E PROOF OF THEOREM 4
In this appendix, assume all action sets spherical, i.e. An,t = for [N], [T]. Note that these action sets meet Assumption
For each task E [2'] we use RN.00 = = [maxxeAn (x, 01) -E ( U.)1 to denote the regret incurred on task t.
Lemma 19. Under the setting of Theorem 4, have in supp E R C' 0.0001.
CKTVN, where
Lemma 20. Under the setting of Theorem 4, we have inf sup, E N.T C' = 0.0001.
CdvKTN, where
A.T.
Proof of Theorem 4. We combine Lemma 19 and Lemma 20.
The proofs in this appendix would largely follow the proofs in Appendix B, yet this appendix is much longer, because we need to construct instances that satisfies Assumption 3, Assumption 4, and Assumption 5.
Our proofs to the lemmas are based on the lower bounds for the (single-task) linearly parameterized bandit setting, which corresponds the T' = 1 in our setting. For this single-task setting, we assume k: = d and B = Ia- (This setting need not meet Assumption 4 and Assumption 5). We write the regret as RN R and call algorithms for the single-task setting as single-task algorithms.
We invoke the following lower bound for the single-task setting.
Lemma 21. Assume N 2 d' and d 2 2. Let N(, E) be the multivariate normal distribution with mean i and covariance matrix E. For any single-task algorithm, have
E (
I 110.09 < ||w||| < 331 2 0.006dV
(20)
The lemma can be proved by following the proof of Theorem 2.1 of Rusmevichientong & Tsitsiklis (2010). Next we use to prove Lemma 19 and Lemma 20. The main idea to prove Lemma 19 is to note that we can treat our setting T independent k-dimensional linear bandits.
Let Ha be the conditional probability measure whose density function is given by
g(z) Pex 1000 0.
0.09 < ||~||| < 3,
f(x)
otherwise,
where X (0, Ia/d) is the multivariate gaussian vector and g is the probability density function of X. Then (20) implies
E Woi
[RN] > 0.006d
(21)
22

---

Published as a conference paper at ICLR 2021
Proof of Lemma 19. Without loss of generality, assume 2 divides T. Suppose, for contradic- tion, that there is algorithm A', such that for every instance I, it incurs regret B N:7 S CTKVN. We replace the condition well I by | S 3 in our setting, Note that A'' implies an algorithm A that incurs regret E[R N.
A.I. I 3CTkyN.
We construct the following instances I
(B, W), where B = (Ix 0) and W
(w) wr) as follows. Let
Wr/2k E1, Wr/2k-1
Wryk E2,
(k (k-11)//2b+1 W1/2 = Ek:
where e1...., Ck E IR K the standard basis. Let
WT/2+1,... WT ~ Hdd
be i.i.d. drawn. Thanks to the first 2 tasks, the instance I always satisfies Assumption 4. Note that
|w/]] 0.09, the instance also satisfies Assumption 5. Then we have
[ 3CTKVN.
E WT/2 WT Wrrup
Thus
Σ
E
E
[
[R
S 3CTRVN.
t=T/2+1
wr/2+1 ppp
Therefore, we can find & E ET/22 + 1, such that
E
N.00 R
AI
3CT T/2
KVN 6CKVN.
WT 1o Ma
We note that the expectation operator Eurr/s4 is over all randomness on tasks 7 * and its parameter w/-- So there is realization of the randomness on other tasks * that satisfies
E
(.(1) AAZ
W,,
* + 6CkvN.
Based on the realization Wr, Er, we design single-task algorithm S, which plays task and simu- lates other tasks * L with Wr, Er. The algorithm achieves
R SI
E wirrp
N.(0)
E T + 6CKVN,
which contradicts (21) because C 0.0001.
Proof of Lemma 20. Without loss of generality, assume that d is and that 2k divides T. Suppose, for contradiction, that there is an algorithm A', such that for every instance I, incurs regret E < CdvkTN. We replace the condition ||w.l| < 1 by |well < 3 in our setting.
Note that A' implies an algorithm A that incurs regret E.RNN I 3Cdv KTN.
We prove the lemma separately, based on whether k 2 $ or not.
1. Consider 7: $. We generate i vectors v/ ,1,...,, t/2 that N/, 14-1411 For every dimension we consider map
G : Rdxi + Rdx(d-i+1)
(#1...., vz)) + (V1,.. Vd-i+1);
that when {II...., 2 are orthogonal, the set {vi,.. fd-s+11 } is the orthonormal basis of the orthogonal complement spanfæ)...... x.) of Rdd Note that e; can be computed efficiently, e.g. by Gram-Schmidt process.
23

---

Published as a conference paper at ICLR 2021
We define Φ1 1 and (--1 01-1) t/ for i 2 2. We observe that (0I,..., ,6x) orthogonal. Next define our instance I = (B, W), where B (b1 bx) and b; l1 For W (w) Wr), we let
W1 wT/k | || e1
WT/R41 = =... = W2T/k || 62:
W(k-1)T/b+1 = WT = | .kk:
e C I is the standard basis. Note that the instance I always satisfies Assump- tion 4 and Assumption 5 by our choice of w, Note that we have divided the tasks into groups, so that each group share the same vector wp. For i = -I....,e k, we denote the regret of group as
where (ei,...,
sT/K
N.(()) R
Σ
N.10
AI
RAI
(//1///
For the algorithm A, it incurs regret
E
RAZ
N.10))
S 3CdVKNT.
So there is group i [k)], such that
E
R (.
A.
3CdVENT =3Cd k
NT
$1....02
Similar to the proof of Lemma 19, we can fix the randomness for groups j * i to obtain a realization, such that
NT
E
N.(())
EjJ # 3CaVKNT = =3CdV k
K
Here we note that di could depend on Φ, for 2 i 1. Now we let p4-k+1 and let ck- A = ( (01,-.., di-1, Pit1,...,,
of Anh,
(22)
Note that of and Φi Φ5(ز)5) are identical, so we have
NT
(.0()) de de
E
1 3CdVENT =3dd k
(23)
We complete the proof by showing that (23) implies single-task algorithm S that plays a (d-k+1). dimensional linear bandit for NT times. Let v// Then w is independently drawn from Mddk+11- Next we design the algorithm S, which runs A by playing the tasks 1 E T = {(i 1)T/k +
1,...,77] iT/kk and simulates other tasks & T. Note that playing the task playing the single-task bandit defined by w, because we have 0, = Bw; = d, = Any and the matrix A is known (as in (22)) after we fix the randomness on other tasks. Since [7] = E and A is played for N times, S can play the single-task bandit specified by w for NT times. As result, we k
T is the same as
T
have
E
(Z))
= E
[A
N-((E) A.T
| Ej $5,5$$$10 +
w-
$1=0!
NT
30d
NT k
6C k 1)V
which contradicts to (21) because C = 0.0001.
2. Consider k > d In this case, the lower bound in Lemma 19 becomes (( = S((dVN). 7.
Since T ' k. have d/ENN & TdvN. Thus we conclude by Lemma 19.
24

---

Published as a conference paper at ICLR 2021
x 10
1
c= 1.5
3.5
ECTC
Regret per Task
3.0
PEGE
2.5
2.0
1.5
1.0
100
200
300 100
200
300 100
200
300
T: Number of Tasks
Figure 5: Comparisons E2TC with PEGE for = 3.
x10
1.5
C= 2
E²TC
3.0
Regret per Task
PEGE
2.5
2.0
1.5
1.0
50
100
150 50
100
150 50
100
150
T: Number of Tasks
Figure 6: Comparisons of E2TC with PEGE for k 2.
F EXPERIMENTS FOR INFINITE-ARM SETTING
Setup In all experiments, we set d = 10, N = 10a and the action A, = Sd-1, The parameters are generated as follows. We consider k = 2, in our experiments. The noise En, ~ No0, 1) are ii.d. Gaussian random variables. To verify our theoretical results, we consider
E {0.5, 1, 1.5 each run E2TC with N1 / N and N₂ -kV..
Results and Discussions We present the simulation results in Figure and Figure 6. We empha- size that the y-axis in our figures corresponds to the regret per task, which is defined as RegN.T Our main observation is that only when the number of tasks T is large and we choose the right scaling N₂ = dz.5k / N implications of our results. First, representation learning does help, especially when there many tasks available for us to learn the representation, as we see in all figures that the regret per task of E²TC decreases as T increases. Second, the help of representation learning is bounded. In the figures, we see that the curves of E²TC bends to a horizontal line as T increases, which suggests a lower bound on the regret per task. Meanwhile, we also proved an l(kv/N lower bound on the regret per task in Theorem 4. Third, representation learning may have adverse effect without enough task. In our figures, this was established by noting that our algorithm cannot outperform PEGE when T is small. This corresponds to the "negative transfer" phenomenon observed in previous work (Wang et al., 2019). Fourth, the correct syper-parameter e = 1.5 is crucial. For hyper- parameter other than e 1.5, the figures show that our algorithm would require much more tasks to outperform PEGE. Lastly, by comparing the two figures, we notice that our algorithm has bigger advantage when is smaller, which corroborates the scaling with respect to & in our regret upper bound. In contrast, PEGE does not benefit from smaller k.
T, our method can outperform the PEGE algorithm. We discuss several
25


Reviews:
[{"review_id": "yrifL6eNBZG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- Pros.\n   -  Learning the representation is crucial to model an efficient linear MAB. However, there is lot of room to include the characteristic of the learned representation into theoretical guarantee. This paper throws a light on this interesting problem.\n   - The paper is well-written and the bounds look convincing. I have not gone through the detailed derivations (in the appendix), but the overall idea looks good.\n\n- Cons.\n   -  It would have been better if the paper could throw some light on other variants of representation learning.\n   -  Linear bandit is quite popular news/ad recommendation systems. However, posing hand-writing recognition on MNIST data as linear bandit seems to be unnatural. There are DNN based approaches that solve the problem with a great accuracy. It will be interesting to see how does the algorithm perform on a real data set of news/ad recommendation.\n   - Assumption 2 is a quite strong assumption to make.\n   \nI believe the exiting work: A Contextual-Bandit Approach to Personalized News Article Recommendation by Li et al (2010) deserves a citation in this paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ib6L7Yvh8U7", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary*\n\nThis paper theoretically studies the benefits of representation learning in linear bandit problems. The key assumption is the existence of a common linear feature extractor. Two different setting are studied. In the finite-action setting, the authors provide the MLinGreedy algorithm that achieves matching upper and lower bounds (up to polylog factors). In the infinite-action setting, the authors provide the $E^2TC$ algorithm that can achieve lower regret than the naive method when the number of tasks is large. Experiments on both synthetic and real-world data are conducted, which confirm the theoretical results.\n\n*Assessment*\n\nOverall I'm leaning towards acceptance. Representation learning in sequential decision making problems is an important problem that many readers of ICLR will care about, and it is valuable to offer some theory insights into this problem. Besides, the paper is overall clearly written and enjoyable to read. Still I have some questions regarding the assumptions that the theoretical results are based on (see questions).\n\n*Questions/Comments*\n- The context vectors $x_{t,a}$ can be arbitrarily chosen in LinUCB (Chu et al. 2011). Is it possible to allow for adversarially chosen context in the finite-action setting?\n- Intuitively, what is the reason that we do not need explicit exploration in MLinGreedy? I assume it has something to do with Lemma 3, which seems to rely on Assumption 2 ($\\lambda_{\\min}(\\Sigma_t) \\ge \\Omega(1/d)$). Following the previous question, Assumption 2 looks rather strong; is there any good motivating example showing that Assumption 2 is likely to be true in practice?\n- It would be better to give a concrete motivating example at the begining to give the readers a better idea of what $N, T, d, k$ look like order-wise.\n- There's a gap between upper and lower bound in the infinite-action setting, but this is acceptable as a conference submission.\n\n*Minor comments*\n- Page 4, first line: $[w_1, \\dots, w_T]$ should be in bold.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hKgpj03cEco", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper introduced the representation learning techniques into the linear bandits and showed that representation learning could improve the regret bound when multiple tasks shared a common low dimensional linear representation. The authors also proved a lower bound and extended the algorithm to the infinite-action setting. They also present experiments to validate their theoretical findings.\n\nPros:\n(1) The idea of representation learning + linear bandits is very interesting.  Their results are also impressive which showed that combination will be better than naive algorithm. \n(2) The paper is well written and easy to read. Their proof part looks good.\n\nCons:\n The assumptions (1,3,4) are based on the representation learning setting. Some of them seems very strong compared to the general linear bandits, e.g.,  assumption 4. Is this fair to compare your result with naive algorithm ? The naive algorithm could have better regret bound under the same setting. e.g., if the source tasks are diverse enough, the linear bandits will become much easier.\n\nMinor Comments:\nThe author should use the better notations for bandit setting. It is strange that using T as the number of bandit tasks since T usually will be used as the time horizon of the experiments.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "THoN1ZjAQfD", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This article provide a theoretical analysis of the impact of learning a shared low-rank representation in multi-task linear bandits.\nTwo types of linear bandits are considered: the finite actions and the continuous actions settings.\nFor the finite-actions setting the authors propose an algorithm called MLinGreedy and provide a theoretical analysis with a tight minimax regret bound (Theorem 1 & 2). For the continuous-actions setting they propose an \"explore-then-explored-then-commit\" algorithm called E2TC. They provide an upper-bound for the regret (Theorem 3), and a lower bound (Theorem 4). A gap remains between upper and lower regret bounds for this setting.\nTheses bounds are roughly constituted of two parts: one part for the cost of learning the low-rank representation and one part which correspond to the cost of a linear bandit on a perfect low-rank representation.\nIn section 6 the authors provide two experiments for the finite actions setting. One experiment on a synthetic environment, another which is simulated-from \"real-life\" data. These experiments underline the advantage of learning a shared low-rank representation against a baseline where that tasks are considered independently. It does not expose situations where, according to the bounds, it should be at disadvantage.\n\nIf we omit the numerous typos that I listed at the end of this review, I found the paper clear and well written.\nI did not have time to delve deeply into all the demonstrations, but the proof of Theorem 1 seems solid.\nAs explained on page 5 it relies on three lemma. Lemma 2 give guarantees on the low-rank approximation. It  is based on a Hoeffding concentration inequality combined with an epsilon-net argument. Lemma 3, borrowed from (Han et al., 2020), and Lemma 4 show that this estimate works well with the doubling schedule of MLinGreedy.\n\n## Pro:\n- The paper is well written\n- The maths seem solid\n- The results give a theoretical insight on the impact/benefit of representation learning in the specific case of linear bandits.\n\n## Con:\n- The multi-task linear bandit models rely on several assumptions and simplifications which obfuscate its realism. These assumptions are however justified thoroughly on page 3 and 4.\n- I did not like the bias toward improvement of the introduction: for instance, according to the bound, if k is in Omega(d), the cost of learning the low-rank matrix is linear in d which results in a regret which is worse than the one of the \"naive\" approach for large dimensions. The authors should not be afraid to develop on the cases where the shared representation does not improve, it will not devaluate the significance of their work.\n\n## Minor remarks & typos:\np1: I am not a fan of the \"Provable benefits of\" phrase in the title. This work is more about the impact of shared low-rank representation and when it can improves from the naive, but much simpler, independent-tasks approach. As mentioned on page 5 it requires T to be in Omega(k) to improve. \"Impact of\" would be more appropriate.\np1: \"In this paper, we\" -> \"We\"\np2: The \\mathbold{x}_{n,t,a_{n,t}} notation is heavy and  not really needed. As mentioned on the bottom of page 3 one may interchangeably use \\mathbold{a}_{n,t} and \\mathbold{x}_{n,t,a_{n,t}} to refer the same action, so I would get rid of the heaviest notation.\np3: \"line of work analyzed\" -> \"line of work that analyzed\"\np3: \"as our algorithm\" -> \"with our algorithm\"\np3: \"In this paper, we\" -> \"We\"\np4: \"In this assumption\" -> \"With this assumption\"\np4: \"for at each task\" -> \"for each task\"\np4: \"In each round\" -> \"At each round\"\np4: \"task are sample from\" -> \"task are sampled from\"\np5: \"up to an constant error\" -> \"up to a constant error\"\np5: \"we use an method-of\" -> \"we use a method-of\"\np6:  \"value decomposition of \\hat{B}\" -> \"value decomposition of \\hat{M}\"\np7&8: the theoretical bounds should appear on Figure 2 and 4.\np8: Replacing the Time Horizon n with the number of tasks T as on Figure 2 would be more informative.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CIQ8gnM2ma", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the benefits of learning a low-rank feature extractor in multi-task linear bandits. Specifically, the paper studies the setting where an unknown common linear feature extractor $B \\in R^{d \\times k}$ maps the original $d$-dimensional contexts $x$ to a $k$-dimensional representation. Essentially, for multi-task linear bandit problem $r_t = \\theta_t^T x$, this paper assumes the matrix of model parameters $\\Theta \\in R^{d\\times T}$ is low-rank and be factorized as $\\Theta = BW$ with rank k. The paper proposed algorithms to estimate both $B$ and $W$ in finite actions setting and infinite actions setting. In finite action setting, the proposed solution is a greedy algorithm while in infinite actions setting, the proposed solution is a explore-the-commit method. Theoretical result shows that the regret is $O(T\\sqrt{kN} + \\sqrt{dkTN})$ and matches the lower bound. Simulation result shows that the algorithm outperforms baselines running independent linear bandit algorithms. \n\nPros:\n1) The problem studied in this paper is interesting and important. It is a well-known concern that linear bandits has a $O(d)$ regret for infinite actions and $O(\\sqrt{d})$ regret for finite actions, which is too large for practical problem. Many recent studies aim to address this problem from varies perspectives, such as low-rank structure, sparsity, etc. The authors proposes to estimate a low-rank feature extractor for multi-task linear bandits to reduce the regret.\n\n2) The paper is generally well-written and easy to follow (only a few confusing descriptions, mentioned below). The required assumptions are presented and discussed clearly.\n\n3) The analysis of regret upper bound and lower bound are good contributions.\n\n\nCons:\n1) The paper introduces a very strong assumption (Assumption 2) that the context features are sampled from Gaussian  (a stochastic context setting), and is a serious limitation of this paper. Most linear bandits research focus on the adversarial contexts setting, where the solution can also solve bandits with stochastic context but not the other way around. The gaussian feature assumption suggests that arms are equally informative and thus the classical exploration-exploitation dilemma does not exist.  It is not clearly discussed in the paper that why this paper must be limited to the stochastic feature setting. The paper heavily follows Theoretical results from [1] and both adversarial and stochastic contexts settings are discussed in [1]. What is the challenge to propose a solution for adversarial contexts, for example a linear UCB based solution? \n\n2) It seems unclear on how to estimate both $B$ and $W$ and what is the estimation quality. According to the description the algorithm is doing an explicit matrix factorization. Since matrix factorization does not have a closed form solution, what is the guarantee of the estimation quality? In Lemma 2 the analysis requires the estimated $\\hat B$ and $\\hat W$ minimize the square loss so that the square loss with estimated $\\hat B$ and $\\hat W$ is smaller than the square loss with true $B$ and $W$(the first step of derivation)-- is this guaranteed to be achievable?\n\n3) The authors argued that the problem of learning a low-rank feature extractor has not been studied in the bandit setting before, which seems incorrect: [2] studies a very similar problem that tries to estimate a hidden projection matrix for linear bandits with low-rank structure. In [2] the project matrix is estimated by PCA.  I strongly suggest the authors to compare this paper with [2]. One difference is that in [2] the low-rank structure is about the features (thus can be directly estimated from the features), while in this paper the low-rank structure is about the parameters $\\Theta$. One potential advantages I can think of is this paper achieves regret in $O(\\sqrt{k})$ while [2] has regret in $O(k)$ -- is it because of the assumption on features are sampled from gaussian? \n\n\nOther questions:\n\n1) What is the baseline naive algorithm in Figure 1? It seems to be linear regression + greedy strategy and I would suggest the authors to clarify it.\n\n2) Is rank $k$ assumed to be an input to the algorithm? What if the algorithm does not know it or have a wrong knowledge of $k$?\n\n\n==========================================================================================\n\nWhile I still hold my concern on the i.i.d. assumption of the context as it is less interesting both practically and theoretically, the author response and the revised paper clearly resolve my other questions and concerns.  I am increasing my score to 6.\n\n\nReferences:\n[1] Han, Yanjun, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W. Glynn, and Yinyu Ye. \"Sequential Batch Learning in Finite-Action Linear Contextual Bandits.\" arXiv preprint arXiv:2004.06321 (2020). \n[2] Lale, Sahin, Kamyar Azizzadenesheli, Anima Anandkumar, and Babak Hassibi. \"Stochastic linear bandits with hidden low rank structure.\" arXiv preprint arXiv:1901.09490 (2019).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the representation learning problem in the linear bandit setting, where each bandit "task" shares a common low-dimensional representation. The paper introduces a novel algorithm, it provides theoretical regret guarantees, and it illustrates the effectiveness of the proposed method in a number of experiments.

There is a general agreement among the reviewers about the relevance of the problem and the contribution of the paper. The authors properly addressed concerns about the novelty (e.g., comparison with linear bandit and low-rank structure) and about the underlying assumptions. Although some of them do seem relatively strong (and in some cases stronger than the state-of-the-art in bandit, such as the distribution on the contexts), it is indeed non trivial to understand whether such assumptions can be easily relaxed in the representation learning context. 

The novelty of the algorithm is more on the specific problem and set of assumptions, but it mostly relies on known principles (e.g., using method-of-moment for estimating the underlying representation). In this sense, I see this paper more as a useful addition to the fast growing landscape of representation learning methods in online learning, rather than a breakthrough. Also, the structure of the algorithm seems very "theoretical" in nature, since the explore-than-commit approach is very rarely a good strategy in practice. 

Another issue the authors clarified in their revised submission is the actual improvement obtained in the bounds depending on the parameters T, k, d, N. In this respect, I still would like to encourage the authors to further illustrate the regime where the bound is actually better than for the single-task approach. For instance, they could consider N fixed to a convenient value and produce a plot with x-axis T and y-axis the regret bound and report different curves for varying values of k and d. This would further clarify to the reader when representation learning can *provably* improve over plain single-task learning.

Overall, given the general support from the reviewers and the revised version of the paper, I consider this contribution is significant enough to propose acceptance. As mentioned above, I believe it will serve as a reference for developing further the literature in this domain.
Decision: Accept (Poster)