Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees
Authors: Andrea Tirinzoni
Matteo Papini
Ahmed Touati
Alessandro Lazaric
Matteo Pirotta
Venue: NeurIPS 2022 Accept (2022)

Abstract: We study the problem of representation learning in stochastic contextual linear bandits. While the primary concern in this domain is usually to find \textit{realizable} representations (i.e., those that allow predicting the reward function at any context-action pair exactly), it has been recently shown that representations with certain spectral properties (called \textit{HLS}) may be more effective for the exploration-exploitation task, enabling \textit{LinUCB} to achieve constant (i.e., horizon-independent) regret. In this paper, we propose \textsc{BanditSRL}, a representation learning algorithm that combines a novel constrained optimization problem to learn a realizable representation with good spectral properties with a generalized likelihood ratio test to exploit the recovered representation and avoid excessive exploration. We prove that \textsc{BanditSRL} can be paired with any no-regret algorithm and achieve constant regret whenever an \textit{HLS} representation is available. Furthermore, \textsc{BanditSRL} can be easily combined with deep neural networks and we show how regularizing towards \textit{HLS} representations is beneficial in standard benchmarks.

Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees
Andrea Tirinzoni
Matteo Papini Universitat Pompeu Fabra matteo. par.nieupp edu
Ahmed Touati
Meta cirinzoni@meta.com
Meta
atouati@meta.com
Alessandro Lazaric
Matteo Pirotta
Meta lazaricSmeta.com com
Meta
pirotta@meta.com com
Abstract
We study the problem of representation learning in stochastic contextual linear bandits. While the primary concern in this domain is usually to find realizable repre- sentations (i.e.. those that allow predicting the reward function at any context-action pair exactly), it has been recently shown that representations with certain spectral properties (called HLS) may be more effective for the enabling LinUCB to achieve constant (i.e., horizon-independene regret. In this paper, we propose BANDITŠRL, a representation learning algorithm that com- bines novel constrained optimization problem to learn realizable representation with good spectral properties with a generalized likelihood ratio test to exploit the recovered representation and avoid excessive exploration. We prove that BAN- DITSRL can be paired with any no-regret algorithm and achieve constant regret whenever HLS representation is available. Furthermore, BANDITSRL can be casily combined with deep neural networks and we show how regularizing towards HLS representations is beneficial in standard benchmarks.
task,
Introduction
The contextual bandit is general framework to formalize the exploration-exploittiio dilemma arising in sequential decision-making problems such as recommendation systems, online advertising, and clinical trials [c.g.. M. When solving real-world problems, where contexts and actions complex and high-dimensional (c.g., users' social graph, items' visual description), it is crucial to provide the bandit algorithm with suitable representation of the context-action space. While several representation learning algorithms have been proposed in supervised learning and obtained impressing empirical results (e.g..21 3. how to efficiently learn representations that are effective for the intporaationeeploitaatii problem still relatively an open question.
The primary objective in representation learning is to find features that map the context-action space into a lower-dimensional embedding that allows fitting the reward function accurately, i.e., realiz- able representations [e.g.. T010 Within the space of realizable representations, bandit algorithms leveraging features of smaller dimension are expected to learn faster and thus have smaller regret. among realizable features, certain problem. In particular,
Nonetheless, Papini et al. (11] have recently shown that,
representations are naturally better suited to solve the opploration-exploitanne they proved that LINUCB [12 [3] achieve constant regret when provided with "good" repre- sentation. Interestingly, this property is not related to "global" characteristics of the feature map (e.g.. dimension, norms), but rather spectral property of the representation (the space associated to optimal actions should cover the context-action space, see HLS property in Def. 2.I). This naturally
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

raises the question whether it is possible to learn such representation at the same time as solving the contextual bandit problem. Papini et al. [T] provided a first positive answer with the LEADER algorithm, which is proved to perform as well as the best realizable representation in given set up to logarithmic factor in the number of representations. While this allows constant regret when a realizable HLS representation is available, the algorithm suffers from two main limitations: 1) it is entangled with LINUCB and it can hardly be generalized to other bandit algorithms; 2) it learns different representation for each context-action pair, thus making it hard to extend beyond finite representations to arbitrary functional space ge.g., deep neural networks).
In this paper, we address those limitations through BANDITSRL, a novel algorithm that decouples representation learning and intioration-explotttate so as to work with any no-regret contextual bandit algorithm and to be easily extended to general representation spaces. BANDITSRL combines two components: 1) a representation learning mechanism based on a constrained optimization problem that promotes "good" representations while preserving realizability; and 2) generalized likelihood ratio test (GLRT)) avoid over exploration and fully exploit the properties of "good" representations. The main contributions of the paper can be summarized as follows:
1. We show that adding a GLRT on the top of any no-regret algorithm enables it to exploit the properties of a HLS representation and achieve constant regret. This generalizes the constant regret result for LINUCB in [I] to any no-regret algorithm.
2. Similarly, we show that BANDITSRL can be paired with any no-regret algorithm and perform effective representation selection, including achieving constant regret whenever a HLS repre- sentation is available in a given set. This generalizes the result of LEADER beyond LINUCB In doing this we also improve the analysis of the misspecified case and prove a tighter bound the time to converge to realizable representations. Furthermore, numerical simulations in synthetic problems confirm that BANDITSRL is empirically competitive with LEADER.
3. Finally, in contrast to LEADER, BANDITSRL can be easily scaled to complex problems where representations are encoded through deep neural networks. In particular, we show that the La- grangian relaxation of the constrained optimization problem for representation learning becomes a regression problem with an auxiliary representation loss promoting HLS-like representations. We test different variants of the resulting NN- SNN-BANDITSRL. algorithm showing how the auxiliary representation loss improves performance in number of dataset- benchmarks.
2 Preliminaries
We consider a stochastic contextual bandit problem with context space X' and finite action set A. At each round 2 1, the leamer observes context 2, sampled i.i.d. from distribution p over X, selects an action dg E A, and receives a reward = _u(ae, ar) + where T/e is a zero-mean noise and :: X x A + IR is the expected reward. The objective of learner 21 minimize its pseudo-regret RT: = Σt= (1r (x:)) - p(ate at)) for any T 2 1, where Ju" (xx)) == maxae (( a). We assume X' the optimal action o := argmax u(zz a) unique and we define the gap AZz, a) == μ² (x) - p(x, a). We say that 21 is a no-regret algorithm if, for any instance of μ,, it achieves sublinear regret, i.e., R = (T))
that for any
We consider the problem of representation learning in given a candidate function space ob S {Ø : X x A Rdo), ]. where the dimensionality de may depend the feature é. Let 8% argminggr* Expp E.(0(z; To p(x, a)) be the best linear fit of μ for representa- tion Ø. We assume that & contains linearly realizable representation.
Assumption 1 (Realizability). There exists an (unknown) subset xx C ④ such that, for each $*, u(z,a) = ((x,a) a T0, Vx E Ex E A.
Assumption 2 (Regularity). Let BB = Rdo 1101|2 I B&} be a ball in Rede We as- sume that, for each & E D, sup,,a ()(1, S Lo. 100/12 I Bs, supa,a T) < 1 for any 0 E Bg and lyel I 1 almost surely for all t. We assume parameters Lip and Bg are known. We also assume the minimum gap A inf inf.eexptehpooeeAAseeaaa ((I a)} > 0 and that
Rd
Amnin (14 Ee non-redundant.
> 0 for any &e E Φb, ie, all realizable representations are

---

Under Asm. 1 when | = 1, the problem reduces to stochastic linear contextual bandit and can be solved using standard algorithms, such as LINUCB/OFUL [ [3, LinTS [4], and e-greedy [[5]. which enjoy sublinear regret and, in some cases, logarithmic problem-dependent regret. Recently, Papini al. [TT showed that LINUCB only suffers constant regret when realizable representation is HLS,, i.e., when the features of optimal actions span the entire dz-dimensional space. HLS
Definition 2.1 (HLS Representation). A representation & is HLS (the acronym refers to the last names of the authors of (T6]) if
(0) Amin (Ezup [0(z, at (1) >
where Amin (A) denotes the minimum eigenvalue of a matrix A.
Papini et al. showed that HLS, together with realizabilityy, is a sufficient and necessary property for achieving constant regret in contextual stochastic linear bandits for non-redundant representations.
In order deal with the general case where may contain non-realizable representations, we rely on the following misspecification assumption from [1].
Assumption (Misspecification), For each o & Φ², there exists EΦ > such that
min min Ezup ((((x - ula, (x))) Z Eg- BEB T
This assumption states that any non-realizable representation has minimum level of misspecification on average over contexts and for any context-action policy. In the finite-context case, sufficient condition for Asm. Dis is that, for each ø & 4*, there exists context E X with p(x) > 0 such that ((z.a)TO + p(x, a) for all a E A and f E B3
Related work. Several papers have focused on contextual bandits with an arbitrary function space to estimate the reward function under realizability assumptions [e.g.. 5 7 While these works consider similar setting to ours, they do not aim to learn "good" representations, but rather focus on problem to obtain sublinear regret guarantees. This often corresponds
the exploration-exploiaae recovering the maximum likelihood representation, which may not lead to the best regret, After the work in [1I] the problem of representation learning with constant regret guarantees has also been studied in reinforcement learning 17 [8]. As these approaches build on the ideas in [.] they inherit the same limitations as
Another related literature is the one of expert learning and model selection in bandits [e.g.. 19 25), where the objective is to select the best candidate among a set of base learning algorithms or experts. While these algorithms are general and be applied to different settings, including representation learning with a finite set of candidates, they may not be able to effectively leverage the specific structure of the problem. Furthermore, at the best of knowledge, these algorithms suffers polynomial dependence in the number of base algorithms ($)) in our setting) and are limited to worst-case regret guarantees. Whether the /T or poly dependency can be improved in general an open question (see (25] and [I]] App. AJ). Finally, [. [6] studied the specific problem of model selection with nested linear representations, where the best representation is the one with the smallest dimension for which the reward is realizable.
Several works have recently focused on theoretical and practical investigation of contextual bandits with neural networks (NNs) (27-29) While their focus was on leveraging the representation power of NNs to correctly predict the rewards, here we focus on learning representations with good spectral properties through a novel auxiliary loss. A related approach to our is 29 where the authors leverage self-supervised auxiliary losses for representation learning in image-based bandit problems.
3 A General Framework for Representation Learning
We introduce BANDITSRL (Bandit Spectral Representation Learner), an algorithm for stochastic con- textual linear bandit that efficiently decouples representation learning from exploration exploration-exploitttioo exploitation. As illustrated in Alg. BANDITSRL has access to a fixed-representation contextual bandit algorithm 2, the base algorithm, and it is built around two key mechanisms: 1 constrained optimization problem where the objective is to minimize representation loss to favor representations with HI.S properties, whereas the constraint ensures realizability; @ generalized likelihood ratio test (GLRT)
3

---

Algorithm BANDITSRL
Input: representations L, no-regret algorithm 21, confidence å (0, 1). update schedule y
2: Initialize j = 0, Φj 0sg,0 arbitrarily, Vo(Ø,) = Alds, i 1, let 0j :- 6/(2(j + 1)²)
3: for / /= 1,...dd. do
4: Observe context 2t
5: if I 01) > 3 (2-1,6/10((0) then
6:
Play d, - argiax
(I2z, a) T 00 and observe reward y/
7:
else
8:
Play or M, (ze: 0g / 1). observe reward ye, and feed it into
9:
end if'
if [nty] and [ then
11: Set j = j + +1 and ; =
12:
Compute 6 argminscs, { and reset 21
end if
14: end for
to ensure that, if HLS representation is learned, the base algorithm 2 does not over-explore and the "good" representation is exploited to obtain constant regret.
Mechanism 1 (line 12). The first challenge when provided with generic set + is to ensure that the algorithm does not converge to selecting misspecified representations, which may lead to linear regret. This is achieved by introducing hard constraint in the representation optimization, so that BANDITSRL only selects representations in the set (see also [T App. F)).
Φ = E E t: min Ex min min (E f
(I)
BEB,
grest DEB
where (x( 1 E. (,)=,, ys) )² is the empirical mean-square error (MSE) of model (0,0) and (0)5 : 10 log ( BBt) "22"
This condition leverages the existence of realizable representation in 4, to eliminate representations whose MSE is not compatible with the one of the realizable representation, once accounted for the statistical uncertainty (i.e., (o))
Subject to the realizability constraint, the representation loss L. (σ) favours learning a HLS representa- tion (if possible). As illustrated in Def. 2.1 HLS representation such that the expected design ma- trix associated to the optimal actions has positive minimum eigenvalue. Unfortunately it is not pos- sible directly optimize for this condition, since have access to neither the context distribution p nor the optimal action in each context. Nonetheless, we can design loss that works as proxy for the HLS property whenever Q is a no-regret algorithm. Let Vi()) Ala, + E'== 6(x,, ag ( a,) be the empirical design matrix built on the context-actions pairs observed up to time t, then we define (Ø) == - -Amin (V) - ATa,) /L². where the normalization factor ensures invariance w.r.t. the feature norm. Intuitively, the empirical distribution of contexts (xx)²21 converges to p and the frequency of optimal actions selected by no-regret algorithm increases over time, thus ensuring that (o / tends to behave as the design matrix under optimal arms (o a (a(,, at)"), As discussed in Sect. 5 alternativv losses can be used to favour learning HLS representations.
Mechanism @ (line 5). While Papini et al. [ proved that LINUCB is able to exploit HLS representations, other algorithms such as e-greedy may keep forcing exploration and do not fully take advantage of HLS properties, thus failing to achieve constant regret. In order to prevent this, we introduce a generalized likelihood ratio test (GLRT). each round t, let éi-1 be the representation used at time t, then BANDITSRL decides whether to act according to the base algorithm 인 with representation di-1 or fully exploit the learned representation and play greedily w.r.t. it. Denote by 0, = ( E d(I, a,)y, the regularized least-squares parameter at time t for representation Φ and by  (z: Φ) = argmax, {ő(x, a) T the associated greedy policy. Then, BRNDITSRL selects the greedy action m (1z;; o1-1) when the GLR test is active, otherwise it selects the action proposed by the base algorithm 21. Formally, for any o E & and z E X, we define

---

the generalized likelihood ratio as
(d(z, m (=; 0)) 0(I, a)) 00r-11
GLR =
min
( |0(2 - (x; (1, a) vi- (())
and, given 30-1,(()= - 2log + de log(1 + (t 1)L3/ + VABa, the GLR test is 2
GLR;-1(Z;;)) 0) > / (0) 16 30 31 If this happens at time f and Φ is realizable, then we have enough confidence to conclude that the greedy action is optimal, i.e., - (Zz; (e-1) = dx An important aspect of this test is that it is run the current context zz and it does not require evaluating global properties of the representation. While at any time /. it is possible that a non-HLS non-realizable representation may pass the test, the GLRT is sound as 1) exploration through 21 and the representation learning mechanism work in synergy to guarantee that eventually a realizable representation is always provided the GLRT; 2) only HLS representations are guaranteed to consistently trigger the test at any context x.
In practice, BANDITSRL does not update the representation each step but in phases. This is necessary to avoid too frequent representation changes and control the regret, but also to make the algorithm more computationally efficient and practical. Indeed, updating the representation may be computationally expensive in practice (c.g., retraining a NN) and a phased scheme with y parameter reduces the number of representation learning steps to J R [log, (T)]. The algorithm Q is reset at the beginning of a phase j when the representation is selected and it is run on the samples collected during the current phase when the base algorithm is selected. If 21 is able to leverage off- off-policy data, the beginning of phase j. we can warm-start it by providing 6j and all the past data (Ir,, as Vs Vst, While the reset is necessary for dealing with any no-regret algorithm, can be removed for algorithms such as LINUCB and e-greedy without affecting the theoretical guarantees.
Comparison to LEADER. We first recall the basic structure of LEADER. Denote by UCB,(Z, a, o) the
bound computed by LINUCB for the context-action pair (x, a) and represen- tation é after t steps. Then LEADER selects the action a, argmax minse., UCB, (I a, Ø). Unlike the constrained optimization problem in BANDITSRI, this mechanism couples representation learning and exploration-eepllotation and it requires optimizing representation for the current Ie and for each action a. Indeed, LEADER does not output single representation and possibly chooses different representations for each context-action pair. While this enables LEADER mix representations and achieve constant regret in some cases even when & does not include any HLS representation, it leads Iwo major drawbacks: 1) the representation selection directly entangled with the LINUCB infinite functional space (e.g.. a deep neural network). The mechanisms I and @ successfully address these limitations and enable BANDITSRL to be paired with any no-regret algorithm and to be scaled to any representation class illustrated in the next section.
strategy, 2) it is impractical in problems where & is an
3.1 Extension Neural Networks
We now consider a representation space O defined by the last layer of a NN. We denote by ø X' A + Rd the last layer and by f a) Φ(2, To 8 the full NN, where A are the last-layer weights. We show how BANDITSRL can be easily adapted to work with deep neural networks (NN).
First, the GLRT requires only to have access to the current context and representation Φj. i.e., the features defined by the last layer of the current network, and its cost linear in the number of actions. Second, the phased scheme allows lazy updates, where we retrain the network only log, (T) times. Third, we can run any bandit algorithm with a representation provided by the NN, including LINUCB, LinTS, and e-greedy. Fourth, the representation learning step can be adapted to allow efficient optimization a NN. We consider a regularized problem obtained through an approximation of the constrained problem:
argmin (1(0) - -Ceg
min (Er(o',)) 8') + ar,((0)) min Eo 00) 6000"
argmin min (L)(d) + Creg E.
0
where Greg 2 0 is tunable parameter. The fact we consider Creg constant allows us to ignore terms that do not depend either ó or 8. This leads to convenient regularized loss that aims to minimize
5

---

the MSE (second term) while enforcing some spectral property on the last layer of the NN (first term). In practice, we can optimize this loss by stochastic gradient descent over a replay buffer containing the samples observed over time. The resulting algorithm, called NN-BANDITSRI, is direct and elegant generalization of the sssortically-groundee algorithm.
While in theory we can optimize the regularized loss (3) with all the samples, in practice it is important to better control the sample distribution. As the algorithm progresses, we expect the replay buffer to contain an increasing number of samples obtained by optimal actions, which may lead the representation to solely fit optimal actions while increasing misspecification on suboptimal actions. This may compromise the behavior of the algorithm and ultimately lead to high regret. This is an instance of catastrophic forgetting induced by a biased/shifting sample distribution [e.g.. B2]. To prevent this phenomenon, we store two replay buffers: i) an explorative buffer Da, with samples obtained when 2 was selected; ii) an exploitative buffer Deire,, with samples obtained when GLTT triggered and greedy actions were selected. The explorative buffer Da, is used to compute the MSE Ee( 8). While this reduces the number of samples, improves the robustness of the algorithm by promoting realizability. On the other hand, we use all the samples D; Da e U Dglrt, for the representation loss [()). This is coherent with the intuition that mechanism O works when the design matrix Ve drifts towards the design matrix of optimal actions, which is at the core of the HLS property. Refer to App. C for a more detailed description of NN- BANDITSRL.
4 Theoretical Guarantees
In this section, we provide a complete characterization of the theoretical guarantees of BANDITSRL when & is a finite set of representations, i.e., | < oc. We consider the update scheme with 2.
4.1 Constant Regret Bound for HLS Representations
We first study the case where a realizable HLS representation is available. For the characterization of the behavior of the algorithm, we need to introduce the following times:
Telim: an upper-bound to the time at which all non-realizable representations are eliminated, i.e., for all t 2 Telim. o 4²:
THis:: upper-bound to the time (if it exists) after which the HLS representation is selected,
i.e. 6, = o* for all t 2 THLS, where o² E x is the unique HLS realizable representation;
Tgint: an upper-bound to the time (if exists) such that the GLR test triggers for the HLS representation 6* for all / Tgirt.
We begin by deriving a constant problem-dependeee dependent regret bound for BANDITSRL with HLS representations. The proof and explicit values of the constants are reported in App. B
Theorem 4.1. Let 2 be any no-regrel algorithm for stochastic contextual linear bandits, & satisfy
Asm.
{ < 30, 7 = 2, and (((0) = Leig,(()) == - -Amin (V(()) - Xla,) // D3. Moreover, let ob' contains a unique HLS representation &² Then, for any E 10 and E N, the regret of
3
BANDITSRL is bounded, with probability at least 45, a
Rr $ 2Tellm + max Rx [xx(TTop -Teli)) T, 6. (Top log2 A T),
0E
where 8j 5/(2(j 1)2) and
L. log(1 (²))))
/
L3. dg.
d (min (
Topt = Tglrt THIS V Telim S Talg
(x+))) +
(4)
A
with Falg finite (independent from the horizon T) constant depending on algorithm (see Tab. and Ra (T, Φ, 8) an anytime bound (non-decreasing in T and 1/8) on the regret accumulated over steps by 2 using representation & and confidence level 6.
7
While Thm. 4.1 provides high-brobability guarantees, we can easily derive constant expected-regret bound by running BANDITSRI. with decreasing schedule for 6 and with a slightly different preof.
We denote by a A (resp. V b) the minimum (resp. the maximum) between and b.

---

The key finding of the previous result is that BANDITSRL achieves constant regret whenever realizable HLS representation is available in the set 4, which may contain non-realizable as well as realizable non-HH.S representations. The regret bound above also illustrates the "dynamies" of the algorithm and three main regimes. be included in +, which may lead to suffering linear regret until time Telim when the constraint in the representation learning step filters out all non non-realizable representations (first term in the regret bound). At this point, BANDITSRL leverages the loss L to favor HLS representations and the base algorithm 2 to perform effective exploration-exploiatiio term in the bound, which corresponds to upper-bound to the sum of the regrets of 2 in each
the early stages, non-realizable representations may
This leads to the second
phase in between Telim and Tgirt V THIS, which is roughly Eiramm <j<Srage Ra Ba(1i+1 13 ④5) S
max (Topt Jelim; Φ) (Tgg)))pp)) In this second regime, in some phases the algorithm may still select non-HL. representations, which leads to a worst-case bound over all realizable representations in क. Finally, after Telrt V Tuuss the GLRT consistently triggers over time. During this last regime, BANDITSRL has reached enough accuracy and confidence so that the greedy policy of the HLS representation is indeed optimal and no additional regret is incurred.
We notice that the only dependency on the number of representations |+] in Thm. 4. is due to the rescaling of the confidence level 8 + 5// Since standard algorithms have logarithmic dependence in 1/6, this only leads to a logarithmic dependency in ( On the other hand, due to the resets, BANDITSRL has extra logarithmic factor in the effective regret horizon Topt.
Single HL. representation. A noteworthy consequence of Thm. 4.1 is that any no-regret algorithm equipped with GLRT achieves constant regret when provided with realizable HLS representation.
Corollary 4.2. Let d = 4+ = { and d" is HLS. Then, Telim = THLS = O and, with probability at least - 46, BANDITSRL suffers constant regret: Rr S (Tght A T, 6²,6), 6).
This corollary also illustrates that the performance of is not affected when 6" is non-HLS (i.e., Tgirt x)), as BANDITSRL achieves the same regret of the base algorithm. Note that there is no additional logarithmic factor in this case since we do not need any reset for representation learning.
4.2 Additional Results
No HLS representation. A consequence of Thm. 4.1 is that when |$| but no realizable HLS exists (Tgirt. o6), BANDITSRL still enjoys a sublinear regret.
Corollary 4.3 (Regret bound without HLS representation). Consider the same setting in Thm. 4.1 and assume that &² does not contain any HLS representation. Then, for any d E (0, 1) and T E N,
the regret of BANDITSRL is bounded, with probability at least 1 4-446 46, as follows:
RT S 2Telim + max Ra (T', o, (1og, (Tg, 0E
This shows that the regret BANDITSRL is of the same order as the base no-regret algorithm when running with the worst realizable representation. While such worst-case dependency is undesirable, it common to many representation learning algorithms,, both in bandits and reinforcement learning [e.g. In App. C we show that an alternative representation loss could address this problem and lead to a bound scaling with the regret of the best realizable representation (Rr S 2Talim + min Re (T, o, 8/ (b) logz (T'),, while preserving the guarantees for the HLS case. Since the representation loss requires an upper-bound on the number of suboptimal actions and a carefully tuned schedule for guessing the gap A, it less practical than the smallest eigenvalue, which we use as the basis for our practical version of BANDITSRL.
4 33
Al Algorithm--ependentt instances and comparison to LEADER. Table T reports the regret bound of B BANDITSRL for different base algorithms. These results make explicit the dependence in the number of representations |b) and show that the cost of representation learning is only logarithmic. In the specific case of LINUCB for HLS representations, we highlight that the upper-bound to the time Topt
NNttiee that the rersstrepresnntttionn dependency is often hidden in the definition of d. which is assumed to contain features with fixed dimension and bounded norm, i.c., + = (Ø : X + R sup,.. (lo a) < L). As d and B are often the only ceteisenttttionddpeeeeee terms in the regret bound Ra. no ropeetreprrssntattoon dependency is reported.
7

---

Algorithm
Ra (T, Φ 6/101)
Talg L. 168(
LINUCB
d² log( 2 TT/))
e-greedy with = 1/1
Vd AA| log /6)/2//
(M)
2 101())
Table 1:
Specific regret bounds when using LINUCB e-gredd base algorithms. We omit numerical constants and logarithmic factors.
in Thm. 4.1 improves over the result of LEADER. While LEADER has no explicit concept of Talg term with the same dependence of Taly in Tab. Jappears also in the LEADER analysis. This term encodes an upper bound to the pulls of suboptimal actions and depends on the LINUCB strategy. As a result, the first three terms in Eq. E are equivalent to the ones of LEADER. The improvement comes from the last term (Telim). where, thanks to a refined analysis of the elimination condition, we are able to improve the dependence on the inverse minimum misspecification (1/ minggg- (6) from quadratic to linear (see App. B for detailed comparison). On the other hand, BANDITSRL suffers from the worst regret among realizable representations, whereas LEADER scales with the best representation. As discussed above, this mismatch can be mitigated by using by different choice of representation loss. In the case of e-greedy, the T2/3 regret upper-bound induces a worse Talg due to a larger number of suboptimal pulls. This in turns reflects into a higher regret to the constant regime. Finally, LEADER is still guaranteed to achieve constant regret by selecting different representations at different context-action pairs whenever non-HLS representations satisfy a certain mixing condition [cf.] [I] Sec. 5.2]. This result is not possible with BANDITSRL, where one representation is selected in each phase. At the same time, it the single-representation structure of BANDIT SRL that allows us to accommodate different base algorithms and scale it any representation space.
5 Experiments
We provide an empirical validation of BANDITSRL both in synthetic contextual linear bandit problems and in non-linear contextual problems [see e.g., 6 27
Linear Benchmarks. We first evaluate BANDITSRI RL on synthetic linear problems to empirically validate our theoretical findings. In partieular, test BANDITSRL with different base algorithms and representation learning losses and we compare it with LEADER We consider the "varying dimension" problem introduced in [1 which consists of six realizable representations with dimension from 2 to 6. Of the two representations of dimension = 6, one is HL.S. In addition seven misspecified representations are available. Details are provided in App. D We consider LINUCB and e-greedy as base algorithms and we use the theoretical parameters, but we perform warm start using all the past data when new representation is selected. Similarly, for BANDITSRL we use the theoretical parameters (7 = 2) and L,(0) == Leig. / (Ø). Fig. [ shows that, as expected, BANDITSRL with both base algorithms is able to achieve constant regret when HLS representation exists. As expected from the theoretical analysis. e-greedy leads to a higher regret than LINUCB. Furthermore, empirically BANDITSRL. with LINUCB obtains a performance that is comparable with the one of LEADER both with and without realizable HLS representation. Note that when no HLS exists, the regret of BANDITSRL with e-greedy is 22/3, while LINUCB-base algorithms are able to achieve log(?") regret. When D contains misspecified representations (Fig. [ center--eft)). we can observe that in the first regime [1, Telim] the algorithm suffers linear regret, after that we have the regime of the base algorithm (Teelim Fglet V THLS)) up to the point where the GLRT leads to select only optimal actions.
Weak HL.. Papini et al. 11 showed that when realizable representations are redundant (i.e., A (0*)) 0), it is still possible achieve constant regret if the representation is "weakly"-HI.. i.e., the features of the optimal actions span the features (fx; a) associated to any context-action pair, but not necessar- ily Rd To test this case, we pad a 5-dimensional vector of ones to all the features of the six realizable representations in the previous experiment. To deal with the weak- HLS condition, we introduce the alternative representation loss Lweak. (Ø) = mingge (0(2,, T(V - (o az)/L3) LL,)-- Since, Ve(Ø) Ala, tends to behave E., [6" (z))"()))) this loss encourages representations where all the observed features are spanned by the optimal arms, thus promoting weak-HLS representations
WW do not report the performance of model selection algorithms. An extensive analysis can be found in [[]. where the author showed that LEADER outperforming all the baselines.
8

---

(see App. for more details). As expected, Fig. rright) shows that the min sain-eigevvalee loss Leig. fails in identifying the correct representation in this domain. On the other hand, BANDITSRL with the novel loss is able to achieve constant regret and converge to constant regret (we cut the figure for readability), and behaves as LEADER when using LINUCB.
Realizable and one HLS
Misspecified and one HLS
Readizable, no HLS
Weak HLS
180
1,000
150
300
Cunulative Regret
140
800
100
200
600
20
40
K
95
+
50
100
200
0.5
1.5
0.5
1.5
2
0.5
1.5
3
Time
-10"
Time
-104
Time
-10*
Time
-104
BandisSHLLLLnnCHH (C(eig))
grody (C(eig))
Leader
BuddISRL-LLaUCE (C(weak))
BanditSRL-e-rreddy (A(weak))
LiaUCB with HLS
Figure 1: Varying dimension experiment with all realizable representations (left), misspecified representations (center-left), realizable non-HI.S representations (center-right) and weak-HI.S (right). Experiments are averaged over 40 repetitions.
NN Architecture: 50,50,50,50 10 ReLu 1/1 oucs =1
I0
wheel
covertype
x10*
magic
1.25
NeusiLUC Srecu 11.
ISW
kg
2.5
1.00
Pseudo Regret
Poeudo Regret
Psoudo Regret
0.73
2.0
1.5
0.25
IGW
IGO (y kueli
0.00
10
2
3
Time
X10
Time
X10'
Time
x10
x
mushroom
x10P
statlog
1.2
Neural-greeeddy
Pseudo Regrot
7.0
Psoudo Regret
NN BandisRL greody (GLRT 6; Couull
-. NN BandkSRL-IGN (GLRT 8: Cosa 10.)
0.5
NeurakinuCB
BandiSSLLL RiL (OURT Cuuua
0,8
Neural-TS
Ra--anddiSRL-T (OURT Coo
NeuralUOB (tuned on protiem) IGW (uned probrem)
0.4
Neuna tros -0.1)
Neval XCR Enos of IOW oel")
0.2
Time
x10
Time
x10
Figure Average cumulative regret (over 20 runs) in non-linear domains.
Non-Linear Benchmarks. We study the performance of NN- UN-BANDITSRL in classical benchmarks where non-linear representations are required. The code available at the following URL. We only consider the weak-HLS loss L (Ø) as it is more general than full HLS. As base algorithms consider e-greedy and inverse gap weighting (IGW) with e: 1/3 and LINUCB and LINTS with theoretical parameters. These algorithms are run on the representation oy provided by the NN at each phase We compare NN-BANDITSRL against the base algorithms using the maximum-likelihood representation (i.c., Neuree- LINTS) [6] and Neural-LIN (28)), supervised learning with the IGW strategy [e.g.. 7 10 and NeuralUCB (27 See App.
D for details.
For ease of comparison, all the algorithms use the same phased schema for fitting the reward and recomputing the parameters. NeuralUCB uses diagonal approximation of the design matrix.

---

In all the problem: h the reward function is highly non-linear w.r.t. contexts and actions and we use network composed by layers of dimension [50, 50, 50, 50, 10] and ReLu activation learn the representation (i.e., d 10). Fig. 2 shows that all the base algorithms (e-GREEDY, IGW, LIN- UCB, LINTS) achieve better performance through representation learning, outperforming the base algorithms. This provides evidence that NN-B IN-BANDITŠRI is effective even beyond the theoretical scenario.
For the baseline algorithms (NEURALUCB, IGW) we report the regret of the best configuration on each individual dataset, while for IN-BANDITSRL we fix the parameters across datasets (i.e.. 4GLRT 5). While this comparison clearly favours the baselines, it also shows that NN- BANDITSRL robust algorithm that behaves better or on par with the ofute-of-thhearr algorithms. In particular, NN- BANDITSRL uses theoretical parameters while the baselines use tuned configura- tions. Optimizing the parameters of NN-BANDITSRL. outside the scope of these experiments.
6 Conclusion
We proposed a novel algorithm, BANDITSRL, for representation selection in stochastic contextual linear bandits. BANDITSRL combines mechanism for representation learning that aims to recover representations with good spectral properties, with a generalized likelihood ratio test to exploit the recovered representation. We proved that, thanks these mechanisms, BANDITSRL is not only able to achieve sublinear regret with any no-regret algorithm 2 but, when a HLS representation exists, is able achieve constant regret. We demonstrated that BANDITSRL can be implemented using NNs and showed its effectiveness in standard benchmarks.
A direction for future investigation is to extend the approach to weaker misspecification assumption than Asm. 3 Another direction is to leverage the technical and algorithmic tools introduced this paper for representation learning in reinforcement learning, e.g., in low-rank problems [e.g. (38
Acknowledgments and Disclosure of Funding
M. Papini was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 950180).
References
[1] Djallel Bouneffouf and Irina Rish. A survey practical applications of multi-armed and contextual bandits. CoRR, abs/1904. 2019.
[2] Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. CoRR, abs//807..no 307.03748. 2018.
[3] Linus Ericsson, Henry Gouk, Chen Change Loy, and Timothy M. Hospedales. Self-supervised representation learning: Introduction, advances, and challenges. IEEE Signal Process. Mag., 39(3):42-62, 2022.
[4] Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert E. Schapire. Contex- tual bandit learning with predictable rewards. In AISTATS, volume 22 of JMLR Proceedings, pages 19-26. JMLR.org, 2012.
[5] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In ICML, volume 32 of JMLR Workshop and Conference P Proceedings, pages 1638-1646. JMLR.org. 2014.
[6] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In ICLR (Poster). OpenReview.net, 2018.
'The dataset- based problems -statog. magic, covertype, mushroom 34 37 are obtained from the standard
multiclass to bandit conversion 66 17 See appendix D for details.
10

---

[7] Dylan J. Foster and Alexander Rakhlin. Beyond UCB: optimal and efficient contextual bandits with regression oracles. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 3199-3210. PMLR, 2020.
[8] Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. In NeurIPS, pages 14714-14725, 2019.
[9] Tor Lattimore, Csaba Szepesvári, and Gellért Weisz. Learning with good feature representations in bandits and in RL with a generative model. In ICML, volume 1 119 of Proceedings of Machine Learning Research, pages 5670. PMLR, 2020.
[10] David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. CoRR, abs/2003. 126999 12699, 2020.
[11] Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Leveraging good representations in linear contextual bandits. In ICML, volume 139 of Proceed- ings of Muchine Learning Reseurch, pages 8371-8380. PMLR, 2021.
[12] Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In AISTATS, volume 15 of JMLR Proceedings, pages 208-214. JMLR.org, 2011.
[13] Yasin Abbasi Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, pages 2320-2320, 2011.
[14] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In AISTATS, volume 54 of Proceedings of Machine Learning Research, pages 176-184. PMI.R, 2017.
[15] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[16] Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics, pages 3536-3545. PMLR, 2020.
[17] Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Reinforcement learning in linear mdps: Constant regret and representation selection. In NeurIPS, 2021.
[18] Weitong Zhang. Jiafan He, Dongruo Zhou, Amy Zhang, and Quanquan Gu. Provably efficient representation learning in low-rank markov decision processes. CoRR, abs/2106. 1935, 2021.
[19] Peter Auer, Nicolo Gesa-Bianchi Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48 77, 2002.
[20] Ombrric-Ambrym Maillard and Rémi Munos. Adaptive bandits: Towards the best history- dependent strategy. In AISTATS, volume 15 of JMLR Proceedings, pages 570-578. JMLR.org, 2011.
[21] Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert Schapire. Corralling a band of bandit algorithms. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 12-38. PMLR, 2017.
[22] Yasin Abbasi- Yadkori, Aldo Pacchiano, and My Phan. Regret balancing for bandit and RL model selection. CoRR, abs/2006.05491, 2020.
[23] Aldo Pacchiano, My Phan, Yasin Yadkori Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvári. Model selection in contextual stochastic bandit problems. In NeurIPS, 2020.
[24] Jonathan N. Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In AISTATS, volume 130 of Proceedings of Machine Learning Research, pages 3348. PMLR, 2021.
[25] Ashok Cutkosky, Christoph Dann, Abhimanyu Das, Claudio Gentile, Aldo Pacchiano, and Manish Purohit. Dynamic balancing for model selection in bandits and RL. In ICMI., volume 139 of Proceedings of Machine Learning Research, pages 2276-2285 PMLR, 2021.
11

---

[26] Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Problem coaillm-oompexity adaptive model selection for stochastic linear bandits. In AISTATS, volume 130 of Proceedings of Machine Learning Research, pages 1404. PMLR, 2021.
[27] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 11922-11502. PMLR, 2020.
[28] Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. CoRR, abs/2012.01780, 2020.
[29] Aniket Anand Deshmukh, Abhimanu Kumar, Levi Boyles. Denis Charles, Eren Manavoglu, and Ürün Dogan. Self-supervised contextual bandits in computer vision. CoRR, fbs/22033084855 2020.
[30] Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. Advances in Neural Information Processing Systems, 33:1417-1427, 2020.
[31] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[32] Ian J. Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empirical investigation of catastrophic forgetting in gradient-based neural networks, 2013.
[33] Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach. CoRR, abs/2202.00063,, 2022.
[34] Jock A. Blackard. Comparison of Neural Networks and Discriminant Analysis Predicting Forest Cover Types. PhD thesis, USA, 1998. AA19921979.
[35] R.K. Bock, A. Chilingarian, M. Gaug, Hakl, Hengstebeck, M. Jiřina, J. Klaschka, E. Kotrě, P. Savický, S. Towers, A. Vaiciulis, and W. Wittek. Methods for multidimensional event classification: case study using images from cherenkov gamma-ray telescope. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 111(2):511-528, 2004.
[36] Jeffrey Curtis Schlimmer. Concept acquisition through representational adjustment. University of California, Irvine, 1987.
[37] Dheeru Dua and Casey Graff. UCI machine learning repository (http://archive ics uci edu/ml]. Irvine, CA: University of California, School of Information and Computer Science 2019.
[38] Alekh Agarwal, Sham M. Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: structural complexity and representation learning of low rank mdps. In NeurlPS, 2020.
[39] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In NIPS, pages 1177-1184. Curran Associates, Inc., 2007.
[40] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy. Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, pages 8035, 2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] (link to the code)
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "hIJnHtk1klF", "reviewer": "Reviewer_8KSa", "summary": "This paper provides better algorithms to learn the good representation from a set of realizable representation in contextual bandits. The algorithm is interesting and enjoys provable guarantees. Experiments are also conducted to justify the performance. ", "questions": "1. HLS condition is never cited. I think that is from the last name of the authors of \"Adaptive exploration in linear contextual bandit\" and should be acknowledged.  ", "limitations": "I feel in experiments the authors could try to discuss some failure cases and when people should be cautious to use this algorithm. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well-written and well-organized. The algorithm is interesting and can be generalized with neural net function approximation. I appreciate the author could carefully compare with prior LEADER algorithms. \n\nI only have some questions for the experiments part, especially  for the Non-Linear Benchmarks. For those datasets statlog, magic, covertype, it looks like the best proposed algorithm can achieve constant regret easily. This is a huge improvement over the class of TS reported in \"DEEP BAYESIAN BANDITS SHOWDOWN\". Can you comment why this could happen and do you make a fair comparsion? I can understand approximate TS does not do representation learning but is your result suggesting HLS is satisfied in those dataset? Do you cherry-pick those dataset? I feel this is important to understand how frequently HLS conditions can be satisfied in real world problems.  \n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Mx0EJqhusxl", "reviewer": "Reviewer_MyZk", "summary": "This paper studies representation learning for stochastic contextual linear bandit problems. This is done by combining a novel constrained optimization problem to learn a realizable representation with a generalized likelihood ratio test to exploit the structural information. The authors propose BANDITSRL algorithm which could be paired with any no-regret algorithm and achieve constant regret.\n", "questions": "See above.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: This paper focuses on a very important question and it explores the structural information contained in the learning problem. It can be viewed as a combination of model-based and model-free learning, which is practically promising and theoretically plausible.\n\nCons: It is not clear how exploration plays a role here and how it could be improved by the  BANDITSRL algorithm. The benefit of finding realizable representations is that representations with certain spectral properties may be more effective for the exploration-exploitation trade-off. In particular, [1] showed that when the regularity condition (Assumption 2 in this paper) is satisfied, the greedy algorithm (with no exploration) is optimal for the linear contextual bandit problem since the feature itself has certain exploratory properties. I am wondering why this does not hold for the feature-based linear contextual bandit.\n\nIn addition, this representation formulation seems to be closely related to the sparse linear contextual bandits problem by replacing the linear contexts with feature contexts. The authors are encouraged to explore the connections and differences.\n\n[1] Ren, Zhimei, and Zhengyuan Zhou. \"Dynamic batch learning in high-dimensional sparse linear contextual bandits.\" arXiv preprint arXiv:2008.11918 (2020).\n\n\n==========\nI have read the reviews from other reviewers and the responses from the authors. The authors have addressed my concerns and I am happy to keep my recommendation to \"accept\" this submission!", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F2MF26QX5h", "reviewer": "Reviewer_Jibx", "summary": "This paper proposes a new algorithm BanditSRL, that can select the realizable HLS representations from a family of representations for linear contextual bandit learning. The new algorithm is a framework that can apply to any constant-regret base algorithms like LinearUCB. Theoretical analysis show that the algorithm can indeed achieve constant regret when an HLS representation is present and sub-linear regret when only realizable representations are available. The algorithm is also extended to a more practical version that utilizes deep neural networks as the representation family. Experiments show the algorithms are efficient and can achieve small regret.", "questions": "At Line 204, Equation (2), what exactly does the Lagrangian relaxation refer to? Here the equality sign is drawn but I cannot easily see why the equality can hold. Could you explain in detail how this is derived? Or is this an approximation.", "limitations": "There are no foreseeable negative societal impact.\n\nI think the authors should also compare the regret bounds in detail with LEADER in terms of all the variables. While the proposed algorithm BanditSRL surely is more general than LEADER, potentially the regret bound dependence can be worse due to a more complicated analysis.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n+ This paper proposes a new solution to representation learning for linear contextual bandit. Compared with previous work, the new algorithm has a very clean structure and can utilize any base linear bandit algorithm. I believe the algorithmic design and the theoretical analysis are quite original.\n+ The paper is written in high quality. It is clearly written and easy to follow. Potential concerns are discussed and addressed.\n+ The improvement compared with Papini et al. can be significant in that the algorithm goes beyond just LinUCB and the NN-based variant can be practical. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept