Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems
Authors: Yue Kang
Cho-Jui Hsieh
Thomas Chun Man Lee
Venue: NeurIPS 2022 Accept (2022)
Keywords: contextual bandits
online learning

Abstract: In the stochastic contextual low-rank matrix bandit problem, the expected reward of an action is given by the inner product between the action's feature matrix and some fixed, but initially unknown $d_1$ by $d_2$ matrix $\Theta^*$ with rank $r \ll \{d_1, d_2\}$, and an agent sequentially takes actions based on past experience to maximize the cumulative reward. In this paper, we study the generalized low-rank matrix bandit problem, which has been recently proposed in \cite{lu2021low} under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms on this problem, we first propose the G-ESTT framework that modifies the idea from \cite{jun2019bilinear} by using Stein's method on the subspace estimation and then leverage the estimated subspaces via a regularization idea. Furthermore, we remarkably improve the efficiency of G-ESTT by using a novel exclusion idea on the estimated subspace instead, and propose the G-ESTS framework. We also show that both of our methods are the first algorithm to achieve the optimal $\tilde{O}((d_1+d_2)r\sqrt{T})$ bound of regret presented in \cite{lu2021low} up to logarithm terms under some mild conditions, which improves upon the current regret of $\tilde{O}((d_1+d_2)^{3/2} \sqrt{rT})$~\citep{lu2021low}. For completeness, we conduct experiments to illustrate that our proposed algorithms, especially G-ESTS, are also computationally tractable and consistently outperform other state-of-the-art (generalized) linear matrix bandit methods based on a suite of simulations.

Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems
Yue Kang
Cho-Jui Hsieh
Department of Statistics University of California. Davis
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 chohsieh@cs. ucla.
Davis, CA 95616
yuekang@ucdaviis.ed
Thomas C. M. Lee Department of Statistics University of California, Davis
Davis, CA 95616 tcmlee@ucdavis.. edu
Abstract
In the stochastic contextual low-rank matrix bandit problem, the expected reward an action is given by the inner product between the action's feature matrix and some fixed, but initially unknown d1 by de matrix O* with rank r < {d1, d2), and an agent sequentially takes actions based on past experience maximize the cumulative reward. In this paper, we study the generalized low-rank matrix bandit problem, which has been recently proposed in (26) under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms on this problem, we first propose the G-ESTT framework that modifies the idea from [17 by using Stein's 's method on the subspace estimation and then leverage the estimated subspaces via a regularization idea. Furthermore, novel exclusion idea on the estimated subspace instead, and propose the G-ESTS framework. We also show that both of our methods the first algorithm to achieve the optimal Ó((1 + d2 /T) bound of regret presented in (26 up to logarithm terms under some mild conditions, which improves upon the current regret Ö(d, + 3/2 3/T2)) (26). For completeness, we conduct experiments to illustrate that proposed algorithms, especially G-ESTS, also computationally tractable and consistently outperform other state-of-the-arr (generalized) linear matrix bandit methods based suite of simulations.
remarkably improve the efficiency of G-ESTT by using
Introduction
The contextual bandit has proven to be a powerful framework for sequential decision-making prob- lems, with great applications to clinical trials [36), recommendation system [22). and personalized medicine This class of problems evaluates how an agent should choose an action from the poten-
tial action set at each round based on updating policy on-the-fly as to maximize the cumulative reward or minimize the overall regret. With high dimensional sparse data becoming ubiquitous in various fields nowadays, the most fundamental (generalized) linear bandit framework, although has been extensively studied, becomes inefficient in practice. This fact consequently leads line of work stochastic high dimensional bandit problems with low dimensional structures [16] 24 such as the LASSO bandit and low-rank matrix bandit.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Comparison with other low-rank matrix bandit algorithms in rounds T. (d = max d2).
D,, is the r-th largest singular value of @" that is free of d)
METHOD
REGRET BOUND; ORDER OF d COMMENT
UCB-GLM (2017)
Ó(d,daVT); 2
ESTR (2019)
Oldd, / 1.5
BILINEAR BILINEAR
c-FALB (2021)
Õ ((VdidodT); ); 1.5
Low(G) (2021)
((dd,22dTT) 1.5
LOwESTR (2021)
OlvdndzdrT / (Dr)): 1.5
G-ESTT (OURS)
(d (rr); O(drrT/DD.);
G-ESTS (OURS)
In this work, we investigate on the generalized low-rank matrix bandit problem firstly studied in [26]: at round / = 1, ,,...; T, the algorithm selects an action represented by a di by d2 matrix X from the admissible action set X; (At may be fixed), and receives its associated noisy reward ye = u((0", X,))+ where O' Ed x is some unknown low-rank matrix with rank < {dl, d2} and uu-) is the inverse link function. More details about this setting are deferred to Section 3 This problem has vast applicability in real world applications. On the one hand, matrix inputs are appropriate when dealing with paired contexts which are omnipresent in practice. For instance, to design a personalized movie recommendation system, we can formulate each user as m d1 -immensioonll feature vectors (ZI..... Zm E Idd and each movie as m dz-dimensional feature vectors (y),... Ym. E I2). A user-item pair can then naturally represented by a feature matrix defined as the summation of the outer products -k= J&DE Tgd: which will become the contextual feature observed by the bandit algorithm. Other applications involve interaction features between two groups, such as flight-hotel bundles (26] and dating service [17] can also be similarly established. Besides, low-rank models have gained tremendous success in various areas (5). In particular, our problem can be regarded as an extension of the inductive matrix factorization problem D4 38), which estimates
low-rank matrices with contextual information, under the online learning scenario.
Our study is inspired by a line of work on stochastic contextual low-rank matrix bandit [1 17 26 To design an algorithm for matrix bandit problems, naive approach is flatten the d1 by d2 feature matrices into vectors and then apply any (generalized) linear bandit algorithms,, which, however, would be inefficient when di d2 is large. To take advantage of the low-rank structure, [77 have introduced the bilinear low-rank bandit problem and proposed two-stage algorithm named ESTR which could achieve a regret bound of Ō((d) + (d))3/22777 VTT/DTT [ Subsequently, [I5] constructed new algorithm called e-FALB for bilinear bandits and achieved better regret of d(dd1d2(d; + d2)T). However, they only studied the linear reward framework and also restricted the feature matrix as a rank-one matrix. As follow-up work, (26) further released the rank-one restriction on the action feature matrices, and they introduced an algorithm LowGLOC based on the online-to-confidene co-confidence- set conversion 22 for generalized low-rank matrix bandits with Ö(v(di
(dj + (TT) regret bound.
However, this regret bound is still loose compared with the optimal rate Ö((d) + dv) deduced in [15]. and the arm set is still assumed fixed at each round. This algorithm also computationally prohibitive since it requires to calculate the weights of self-constructed covering of the admissible parameter space at each iteration. And how to find this covering for low-rank matrices is also unclear.
In this work, we propose two efficient methods called G-ESTT and G-ESTS for this problem by modifying two stages of ESTR appropriately from different perspectives. To the best of our knowledge. the proposed methods are the first two generalized (contextual) low-rank bandit algorithms that are upon all existing
computationally feasible, and achieve an improved regret bound of (2)1+d2)rr( works on (bilinear) low-rank bandits. The main contributions of this paper can be summarized as: 1) we propose two novel two-stage frameworks G-ESTT and G-ESTS under some mild assumptions. Compared with ESTR in [17, e-FALB in [15] and LOwESTR in 266,, our algorithms are proposed for the nonlinear reward framework with arbitrary action matrices. Compared with LowGLOC in 126), our algorithms not only achieve a better regret bound in theory. but also are computationally fcasible in practice. 2) For G-ESTT, we extend the GLM-UCB algorithms [II] via novel regularization technique. 3) Our proposed G-ESTS is simple and could be easily implemented based on any
'Ō ignores the polylogarithmic factors.

---

tfate-of-the-ad generalized linear bandit algorithms. In particular, when we combine G-ESTS with some efficient algorithms (e.g. SGD-TS 99) the total time complexity after wa stage scales as (Trr(d + d2)). 4) We verify that G-ESTT and G-ESTS are the first two algorithms to attain the Ö((d, + d2) optimal regret bound of low-rank matrix bandit problems up to logarithmic terms. And their practical superiority is also validated in experiments.
Notations: For a vector R", use || to denote the 1p-norm of the vector x and ||
Vz Hz to denote its weighted 2- 2-norm with regard to positive definite matrix H E R=*". For IR"1*"2 we use || ||X and || to define the operator norm, nuclear matrices X,Y E
norm and Frobenious norm of matrix X respectively, and we denote (X, Y) trace YY) as the inner product between X and Y. We write (')) x g(n) if f(n) = (gg(n) and g(n) = (f)))).
2 Related Work
In this section, we briefly discuss some previous algorithms on low-rank matrix bandit problems. Besides the works we have discussed in the former section. [18 33] considered the rank-one bandit problems where the expected reward forms a rank-one matrix and the player selects an element from this matrix the expected reward at each round. In addition,
19 also studied the rank-one matrix
bandit via an elimination-base matrix bandit, and furthermore [13] considered a stochastic low-rank tensor bandit. However, for all these works the feature matrix of an action could be flattened into a one-hot basis vector, and our work yields a more general structure.
algorithm. Alternatively, [12 20 25 considered the general low-rank
Additionally, [4 extended some previous works [6] and presented a unified algorithm based on a greedy search for high-dimensional bandit problems. But it's nontrivial to extend the framework to the matrix bandit problem. For example, they assume that the minimum eigenvalue of the covariance matrix could be strictly lower bounded, but this lower bound would mostly depend on the size of feature matrices, and hence would affect the regret bound consequently.
3 Preliminaries
In this section review problem setting and introduce the assumptions for our theoretical analysis. Let T be the total number of rounds and X, be the action set (X, could be fixed or not). Throughout this paper, we denote the action set X, X' as fixed for notation simplicity, while our frameworks also work with the same regret bound when X₂ varies over time (see Appendix [H.3] for more details.) Algorithms along with theory could be identically obtained when the action set varies (Appendix H.3p. At each round E (T). The agent selects an action X, E X, and gets the payoff y which is conditionally independent of the past payoffs and choices. For the generalized low-rank matrix bandits, we assume the payoff follows a canonical exponential family such that:
yr.3 b(3)
pe- (ye (x)) = exp
+ c(ve: o)): where 8 = vec(X,, T veo(O") = (X,, 0"), (1)
Ee (y X+)) = 6' ((((,, 0-)) = u((X,, 0*)),
where O* C O is fixed but unknown matrix with rank < {dg, {d],d2} and θ is some admissible compact subset of xda (w.l.o.g. d1 (d2)). We also call ((X,,, Q²)) the reward of action X,-
In addition, one can represent model [ in the following Eqn. 2 Note that we relax the definition of (1-) to any real univariate function with some centered exogenous random noise nh, the model shown in Eqn. (2) generalizes our problem setting to single index model (SIM) matrix bandit, and the generalized low-rank matrix bandit problem is special case of this model.
yv = (((X,, θ*)) + ne-
(2)
Here, 7) follows the Gau-Saussian property with some constant parameter dy conditional on the }. We also denote d = max d1. d2). And it is natural to evaluate the agent's s strategy based on the regret [3) defined as the difference between the total reward of optimal policy and the agent's total reward in practice:
filtration F. = [X,,X,11 ......., _X1
Regret, = Σ max ( (x,0") - ,((X,, 0*)).
XEX
3

---

We also present the following two definitions to facilitate further analysis via Stein's 's method:
Definition 3.1. pe R - R be a univariate probability density function defined on R. The score function S" IR- + R regarding density p(-) is defined as:
(*)x)= = (=)) - -Va(())/p(z), I I R.
In particular, for a random matrix with its entrywise probability density p = (pt)) Rdd xd2 +
Rdixds, we define its score function SD = (s.) Rddixd, + Rdixda as S (z) SP (x) by applying the univariate score function to each entry of p independently.
Definition 3.2. (Fact 2.6, (27] Given a rectangular matrix A E [Rd4xdd, the (Hermitian) dilation
H R xd2 - R (R: -da-dddaaxaaa (di dd2) is defined as:
0 H(A) = A
A)
We would omit the subscript of V and the superscript p of S when the underlying distribution is clear. With these definitions, we make the following mild assumptions:
Assumption 3.3. (Finite second-momen moment score) There exists a sampling distribution D over X' such that for the random matrix X drawn from D with its associated density p : RR - Rd xda we have E[(SP (S(SP(X)) (X)) S M, Vi
Assumption 3.4. The norm of true parameter @* and feature matrices in X' is bounded: there exists S E IR+ such that for all arms X E X, || || ||O0]| | S So
Assumption 3.5. The inverse link function j(()) in GLM is continuously differentiable and there exist two constants Cuo Kp such that 0 < C₁ S (z) ky. for all |x < So.
Assumption 3.3 is commonly used in Stein's method 77, and easily satisfied by a wide range of distributions that are non-zero-mean or even non sub-Gaussian thereby allowing us to work with cases not previously possible. For example, to find D we only need the convex hull of X' contains a ball with radius R, and then we use Psj as centered normal p.d.f. with variance R (d,d,) This choice works well in our experiments and please refer to Appendix for more details. Furthermore, Assumption (nd are also standard in contextual generalized bandit literature, and they explicitly imply that we have an upper bound as [u 0}) I |p(0)] + max{ [cpl. |/ == Sy.
4 Main Results
In this section, we present our novel two-stage frameworks, named Generalized Explore Subspace Then Transform (G-ESTT) and Generalized Explore Subspace Then Subtract (G-ESTS) respectively. These two algorithms are inspired by the two-stage algorithm ESTR proposed in 117. ESTR estimates the row and column subspaces for the true parameter O" in stage 1. In stage 2, exploits the estimated subspaces and transforms the original matrix bandits into linear bandits with sparsity, and then invoke a penalized approach called LOWOFUL.
To extend their work into the nonlinear reward setting, we firstly adapt stage into the GLM framework by estimating O' via the following quadratic optimization problem in Eqn. (6) inspired by a line of work in nonlinear signal estimation [29 37). And then we propose two different methods based on the estimated subspaces to deal with GLM bandits for stage 2: for G-ESTT we adapt the idea of LOwOFUL into the GLM framework and propose improved algorithm with regularization. For G-ESTS we innovatively drop all negligible entries to get a -ow-dimensional bandit, which could efficiently be solved by any modern generalized linear bandit algorithm with much less computation.
4.1 Stage 1: Subspace Exploration
For any real-value function f() defined on H. and symmetric matrix A E ddddd with its SVD decomposition as
UT. To explore the valid subspace of the parameter matrix O", we firstly define a function & : R + R 27 in Eqn. (5) and subsequently we define 2i Rddixds - Rd xda as (A) = (bHH((())))))))))))))))))))(((() (d
DUT, we define (A) == U diag(f (DnI,.. ... f f(Daa)
for some parameter E I
vxxx = log(1 + x + x²2 x²/22), logg1 - x + x² 22/2),
x 2 0: I <<< 0.
(5)

---

Algorithm Generalized Explore Subspace Then Transform (G-ESTT)
Input: X, TT, D, the probability rate 6, parameters for Stage 2: X, A1.
Stage 1: Subspace Estimation
for to T do
2: Pull arm X, A' according to D, observe payoff yt.
3: end for
4: Obtain θ based on Eqn. 6
5: Obtain the full SVD of θ [7,01] DIV, V where Ú E Ruxx, V Rdxx..
Stage 2: Sparse Generalized Linear Bandits
6: Rotate the arm feature set: X" [U, x(V. V1] and the admissible parameter space:
θ' = [ Ü I T V.J.
7: Define the vectorized arm set so that the last (d1 - r) (d2 r) components are negligible:
Ko (vec(X()r,
1.),, vec(A(ir. Iedd
and similarly define the parameter set:
e = {vec( 1,,,,,, vee( 66 (f'+1:d (1rc(((11 veo(6)+1ad,,r11.h)
(4)
8: For T2 T - 71 rounds, invoke (P)LowGLM-UCH with Xo, Ou k (d1 + dg) - (A0: (Ao;>1) d1).
We consider the following well-defined regularized minimization problem with nuclear norm penalty:
Ti Σ Whl S(X))), (6)
arg min 0 x42
= (9, In (0) + >n ||0|| (
T
An interesting fact is that our estimator is invariant under different choices of function uu-), and could present the following oracle incquality regarding the estimation error nonzero constant μ by adapting generalized Stein's 's Method 77)
θ μ 0 for some
Theorem 4.1. (Bounds for GLM) For any low-rank generalized linear model with samples
X . XT, drawn from X according to D in Assumption 3.3 and assume Assumption 3.4 and
3.5 hold, then for the optimal solution to the nuclear norm regularization problem with
/2 ((2o)) + 53)MTT and
2(4o + Md) log(2(d1 + d2)/8)
\T 41
Ti
with probability at least 1 8 it holds that:
Cid der log(
2(ds 2 +22)
e μ - 1
Ti
for C1 = 36 M and some nonzero constant p."
The proof of Theorem 4.1 is based on novel adaptation of Stein-typed Lemmas and is deferred to Appendix B We believe this oracle bound is non-trivial since the rate of convergence is better than that deduced from the restricted strong convexity (details in Appendix J even without assuming the sub-Gaussian property. We also present an intuitive explanation on why our Stein-type method is better than existing matrix estimation approaches under our problem setting in Appendix [.2 Remark. In addition, this bound also holds under a more general SIM in Eqn. (2) other than just GLM. Furthermore, although there exists non-zero constant μ in the error term, it will not affect the singular vectors and subspace estimation of O* at all.
After acquiring the estimated θ in stage 1, we can obtain the corresponding SVD as θ [Ū, D [V, V_]T, where Ò E dr xr 01 E (4x((d-r)) f E xd and V1 E Rd (d2-r). And we assume the SVD of the matrix O* can represented as O' UDV where U e IRd xr and V xd To transform the original generalized matrix bandits into generalized linear bandit
5

---

Algorithm 2 LowGLM-UCB
Input: T2, k, No, the probability rate 6, penalization parameters (Ao, A i)).
Initialize M1 (c²c Enn Ti
Ts " A/Cy-
for t 1 1 do
Estimate Og according (1O).
Choose the arm It arg ma (p(x + po(0) | ((,,)) receive yt.
Update (ca)(ca) < Mc(cw) t.z
end for
problems, follow the works in 1 and penalize those covariates that complementary to i and V. Specifically, we could orthogonally rotate the parameter space and the action X as:
e' = ,0, Vi), x' =0=10, Vi).
Define the total dimension p = d1d2. the effective dimension k: dıd2 (dl r)( r) and the r-th largest singular value for O as D and vectorize the new arm space X' and admissible parameter space as shown in Eqn. (3) and 4 Then for the true parameter 0" after transformation, we know that 0% k+1p = vec(O 1:dd 1:da almost null based on results in [32] and Theorem 4.1
1 1:+1lp122 = - vi
|
VTv
|| op E
d1d2r log T2D2,
d1 + d2
S1.
Therefore, this problem degenerates to equivalent with sparse structure (i.e. last p entries of 6* are almost null according Eqn. (8)) To reload the notation we define Ny, Ou as the new feature set and parameter space as shown in Algorithm
generalized linear bandit
Remark. Note the magnitude of Dry would be free of since O' contains only nonzero singular values, and hence we assume that D,, = @(1 under Assumption 3.4 This issue has been ignored in all previous analysis of suplore-then-commii-ss
algorithms (e.g- ESTR [17], Low- ESTR (66),, where the final regret bound of them should be of order (dd instead of the originally- used (dd3/2 /rT))) because of the existence of D,r. However, due the fact that r < is intriguing and crucial to reduce the order of d in the final regret bound, while the order of r is less important. shown in Table [ the regret bounds of all previous low-rank matrix bandits algorithms depend on d by the order 3/2, and we would show that both of our frameworks could improve the cumulative regret bound by factor of vd, which coincides with the dependence of d in the minimax lower bound of the low-rank matrix bandit problem deduced in (66.. detailed analysis is presented in the rest of our paper.
4.2 Stage 2 of G-ESTT
After reducing the original generalized matrix bandit problem into an identical p-dimensional gen- eralized linear bandit problem in stage 2, we can reformulate the problem in the following way: at each round the agent chooses a vector x, of dimension p from the transformed action set X,, and observes a noisy reward = a(,, 000) + To make use of our additional knowledge shown in Eqn. (8), we propose LowGLM-UCHH as an extension of the standard generalized linear bandit algorithm GLM-UCB [II] combined with nelf-noomalized martingale technique [ Specifically, we consider the following maximum quasi-likelilne
estimation problem shown in Eqn. (9) for each round with a weighted regularizer, where the regularizer is ||@]| /2 = T A0/2 for some positive definite diagonal ......;, A1) with Xn only applied to the first h diagonal entries. By enlarging À we ensure more penalization forced on the last k element of 0* as desired.
matrix A diag(Ao. do ......,
0: arg max (0).
T Σ 1=1
1-1
1 TØ]] |0013
IA(0)=
(en To b(Ie, T0) +
[y To -bxx
(9)

---

Here a in Eqn. (9 is the special vectorization shown in Eqn. (3) of [Ū [T, X, V1] where X; is the arm we randomly pull at i-th step in stage I, and Us is the corresponding payoff we observe. 24 in the second summation of Eqn. (9) refers to the arm we pull at i-th step in stage 2. Since (A( (0) is strictly concave function of 8, we have its gradient equal to 0 the maximum é, i.c. VeLa
In what follows, for 2 2, 0 E Rp we define the function ge) and have that
(O) = Σ 3 T s
Σ (( TO) e +
u(xx [0)z + A0
Yo 24
(0
T1 Vol.t Esii
VoLA =0 = (c(0)) =
Σ Yi Zz.
(10)
We also define a matrix function M,(s) = Th Ia ΣE= T + AAss for s ER and denote V22 == (1). Furthermore, a remarkable benefit of reusing the actions {X,) pull in stage 1 is that they contain more randomness and are preferable to the ones we select based on some strategy in stage regarding the parameter estimation because most vector recovery theory requires sufficient randomness during sampling. More inspiring, the projection step in the tradition GLM-UCB [1I], which might be nonconvex and hence hard to solve, is no longer required due the consistency of Og after reutilizing (.x,) Specifically, if we assume the true parameter 0 lies in the interior of On and the sampling distribution D satisfies sub-Gaussian property with parameter and Assumption 3.4 3.5 held. then we can show that |0, 801,, < 1 holds with probability at least
randomly
2B 2/2 holds for some absolute constants C1 C2 with the definition B = 16 (p log(1/ (10))// An intuitive explanation along with rigorous proof are deferred to Appendix [ due to the space limit. The proposed LowGLM-UCB is shown in Algorithm and its regret analysis is presented in Theorem C.I in Appendix.
long Ti 2 (CCvpD+ + (og(/log)))//////
Notice that we can simply replace Mz(cp) by V, in Algorithm and the regret bound would increase at most up to a constant factor (Appendix GG. A potential drawback of Algorithm is that in each iteration we have to calculate Q., which might be computationally expensive. We could resolve this problem by only recomputing O, whenever [Me()]]] increases significantly, i.e. by a constant factor
C'> 1 in scale. And consequently we only need to solve the Eqn. (IO) for ([lgg(T)) times up to the horizon T2, which remarkably saves the computation. Mcanwhile, the bound of the regret would only increase by a constant multiplier vC. We call this modified algorithm as PLowGLM- GLL-UBB with the initial letter "P" standing for "Parsimonious" Its pseudo-code and regret analysis are given in Appendix H.I Equipped with LowGLM-UCB in stage 2, we deduce the overall regret of G-ESTT:
4.2.1 Overall regret of G-ESTT
To quantify the performance of our algorithm, we first define (-) and (-) as
(6) = ky
CuSgt kλo t
Spt log(62) + VeulV VALSL)). (11)
0o k log(11
(5) = (6) ||0|| (ow)"
(12)
And the following Theorem exhibits the overall regret bound for G-ESTT.
Theorem 4.2. (Regret of G-ESTT) Suppose set Ti x dyrd log((d; + d2)/8)/Drr.. and we invoke LowGLM-UCH (or PLOWGLM-UCB) in stage 2 with px(5) = C++T, (5/2), = d1d2, k = (di + (di+d)r-- d2)r-12 22 X1 ST /K (klog((1 + CT.STT / (k:A)))) and the rotated arm sets Xn and available parameter space Og The overall regret of G-ESTT is, with probability at least 1 - 5,
Regrely =Ō
(
(vrddd
+ RYVT)
D
Note G-ESTT improves all existing regret bounds by v factor based on Table I given that < d.
7

---

Algorithm 3 Generalized Explore Subspace Then Subtract (G-ESTS)
Input: X, TT, D, the probability rate 6, parameters for Stage 2: X, A1.
Stage 1: Subspace Estimation
1: Randomly choose X E X according to D and record X,, Y for t 1,... Tí.
2: Obtain θ from Eqn. (6) and calculate its full SVD as θ = [Ū. Ü DIV, I where O e
Rdixr V E dRdx..
Stage 2: Low Dimensional Bandits
3: Rotate the arm feature set: X' [.UL]TVVV V1] and the admissible parameter space:
O' :Ū, ( @ V.].
4: Define the vectorized arm set so that the last (d1 r) (d2 r) components are negligible, and then drop them:
oub {vec(Xi + vec( veo(X (X1 )}:
(13)
and also refine the parameter set accordingly:
0u, == {vec( ((.,,,>),, vec( 0 0'+1,, 1.r), veo( 6 (1rr2++2d22)+
(14)
5: For T3 TT - rounds, invoke any generalized linear bandit algorithm with Nu. O0, k (d1 + d2)r r2.
4.3 Stage 2 of G-ESTS
Although G-ESTT is more efficient than all existing algorithms on our problem setting, it still needs to calculate the MLE in high dimensional space which might be increasingly formidable with large sizes of feature matrices. Note this computational issue remains ubiquitous among most bandit algorithms on high dimensional problems with sparsity, not to mention these algorithms rely on multiple unspecified hyperparameters. Therefore, to handle this practical issue, we propose another fast and efficient framework called G-ESTS in this section.
Inspired by the success of dimension reduction machine learning 34 we propose G-ESTS as shown in Algorithm 3 And we summarize the core idea of G-ESTS as: After rearranging the vectorization of the action set 2' and the unknown O'* as we have shown in Eqn. and for G-ESTT, we can simply exclude, rather than penalize, the subspaces that are complementary to the rows and columns of θ. In other words, could remove the last p k entries directly, i.e. Eqn. (B3 and (14). Intriguingly, not only can we get oow-dimensional (k) generalized linear bandit problem in stage 2, where redundant dimensions
excluded and hence any state-of-the-ar algorithms could be readily invoked. But also obtain the optimal regret bound of scale (dr again as shown in Table I with D,r = Orl/rr.. Besides, G-ESTS requires exceedingly less computation compared with other existing algorithms since consequently get a low-dimensional bandit problem. In summary, our G-ESTS is superior regarding both theoretical guarantee and computational efficiency.
4.3.1 Overall regret of G-ESTS
Theorem 4.3. (Regret of G-ESTS) Suppose we set Ti X /didzrT log((d; + /2)/ /))Drrr Dro. and we invoke any efficient generalized linear bandit algorithm with regret bound ((kVT)) Bin stage 2 with p d2d2, ls (dl + d2)r r2, and the reduced arm sets Xo,sub and available parameter space Oo. The overall regret of G-ESTS is, with probability at least 1 5,
Regrett =Ö
(vrdi2 ( BYTT) Drr
According to Theorem 4.2 and 4.3 both G-ESTT and G-ESTS could achieve an improved Ö /T) regret bound with D,,, (1/ Vr). Surprisingly, this matches the lower bound low-rank matrix bandits presented in (26) up to logarithm terms. To the best of our knowledge, our methods are the first two methods that attain this optimal rate. In addition, given the finite arm set, our G-ESTS
Modem generalized linear bandit algorithms can achieve Ô(kVT)) bound of regret.

---

Table 2: Time in minutes required to make decisions all over round T in simulations (480 arms).
10
12
2
G-ESTS
39.46
45,41
41.28
48.52
G-ESTT
516.14
531.95
520.25
539.83
SGD-TS
99.57
101.34
101.82
104.42
LOWESTR
401.88
419.15
410.31
425.92
framework can even achieve a better regret bound of order Ö( D(Vd/d2rT/D,, (detailed proof in Appendix F22 and this result is better than the lower regret bound with infinite arms by kvT term.
In the following experiments, We will implement the SGD-TS algorithm 9 in stage 2 of G-ESTS since SGD-TS could efficiently proceed with only OddT) complexity for d-dimensional features over T rounds. Therefore, the total computational complexity of stage 2 most (TT + d2) which is significantly less than that of other methods for low-rank matrix bandits (c.g. LowESTR (26)). And the total time complexity of G-ESTS would only scale ( d2 2 + T2(d1 d2)r) where c is the accuracy for subgradient methods in stage 1. This fact also firmly validates the practical superiority of our G-ESTS approach. We naturally believe that this G-ESTS framework can be easily implemented in the linear setting as special case of GLM, where in stage one can utilize any linear bandit algorithm accordingly. In addition, we can easily modify our approaches for the contextual setting by merely transforming the action sets at each iteration with the same regret bound. More details with pseudo-codes for the contextual case are Appendix H.3
5 Experiments
In this section, we show by simulation experiments that our proposed G-ESTT (with LowGLM-UCB)) G-ESTS (with SGD-TS) outperform existing algorithms for the generalized low-rank matrix bandit problems. Since we are the first to propose a practical algorithm for this problem, currently there is no existing literature for comparison. In order to validate the advantage of utilizing low-rank structure and generalized reward functions, we compare with the original SGD-TS after naively flattening the dj by d2 matrices without using the low-rank structure, and LOwESTR 266, which works well for linear low-rank matrix bandits.
We simulate dataset with di = d2 = 10 (12) and r (2): when = 1, we set the diagonal matrix O' as diag((O) = (0.8, 0, ... .). When = 2, we set O = fara + daea for two random orthogonal vectors U1, U/ with ||u] ll2 = ||22112 = 3. For arms we draw 480 (1000) random matrices from (X E dd2xx2 : ||X]|| P S 1}. and we build logistic model where the payoff y/ drawn from Bernoulli distribution with mean p(XxT00 0*). More details on the hyper-parameter tuning are in Appendix[] | Each experiment is repeated 100 times for credibility and the average regret, along with standard deviation, displayed in Figure Note that our experiments are more comprehensive than those in [26]. And due to the expensive time complexity of UCB-based baselines (Table 2 it is formidable for us to increase d here.
From the plots, we observe that our algorithms G-ESTT and G-ESTS always achieve less regret compared with LowESTR and SGD-TS in all four scenarios consistently. Intriguingly, in the warm-up period SGD-TS incurs less regret compared with our methods due to the sacrifice random sampling in stage but our proposed framework quickly overtakes SGD-TS after utilizing the low-rank structure as desired. This phenomenon exactly coincides with our theory. Notice that G-ESTT is slightly better than G-ESTS in the case for 2 especially the very beginning of stage 2, and we believe it is because that our GEESTT could reutilize the actions in stage 1 and hence could yield more robust performance when switching to stage 2. However, G-ESTS would gradually catch up with G-ESTT in the long run as expected. Besides, it costs G-ESTS extremely less running time than other existing methods to update the decisions due to dimensional reduction as shown in Table
2 We also observe that the cumulative regret of G-ESTS tends to become better eventually if we increase Ti decently. (Further investigation and plots for 1000 arms are in Appendix [] Moreover, to pre-check the efficiency of our Stein's 's lemma-basee method for subspace estimation shown in Eqn.

---

Cumulative Reggee
Cumulative Regies
1607
C-01
CCCSTT
GLSTT
GESTT
DIESTT
Curmueette
Curuuaatve
186 Serations
Iteraioons
Iterations
Reeations
(a)
(b)
(c)
(d)
Figure 1: Plots of regret curves of algorithm G-ESTS, G-ESTT, SGD-TS and LowESTR under four
settings (480 arms). (a): diagonal @ d1 = d2 10, = 1; (b): diagonal @* dl = d2 12, r =;
(c): non-diagonal @* d1 d2 = 10, r 2; (d): non -on-diagonal O* dj d2 = r2, =2
( also tried some other low-rank subspace detection algorithms for comparison. The details also deferred to Appendix I.4 due to the space limit.
6 Conclusion
In this paper, we discussed the generalized linear low-rank matrix bandit problem. We proposed two novel and efficient frameworks called G-ESTT and G-ESTS, and both methods could achieve an improved (dr bound of our problem setting up to polylogarithmic terms. The practical superiority our proposed frameworks is also validated under comprehensive experiments.
bound of regret under some mild conditions, which matches the optimal lower
There several directions for our future work. Firstly, although the GLM has achieved tremendous success various settings, recently some other models 39) that are proved to be powerful were proposed, so we can study these modern frameworks the low-rank matrix case. Secondly, it seems more reasonable to continuously update the subspace estimation via online SVD over the total time horizon [17] on-the-fly with randomized strategy. Therefore, we can consider something like arbitrarily choosing an admissible subset of the action set at each round 31 without hurting the regret too much.
Acknowledgments and Disclosure of o Funding
We grateful for the constructive comments from the anonymous reviewers and area chair. This work was partially supported by the National Science Foundation under grants CCF- 1934568, DMS-1811408 DMS-181100 1661, DDMS-116123, DMS-21 13605, IIS-2048280. CJH is also supported by Samsung, Google, Sony and the Okawa Foundation.
IIS-2008 17,, and
References
[1] Yasin Abbasi- Yadkori. Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320 2011.
[2] Yasin Abbasi-Yadkori. David Pal, and Csaba Szepesvari. Online-to-confidence- conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9, PMLR, 2012.
[3] Jvan-Yves Audibert, Rémi Munos, and Csaba Szepesvári. exploration-exploiattoo tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876- 1902, 2009.
[4] Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-299 2020.
[5] Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, (66):717-772 2009.
[6] Kani Chen, Inchi Hu, Zhiliang Ying, al. Strong consistency of maximum quasi-likelihood estimators in generalized linear models with fixed and adaptive designs. Annals of Statistics, 2755):1155-1163 1163, 1999.
10

---

[7] Louis HY Chen, Larry Goldstein, and Qi-Man Shao. Normal approximation by Stein's 's method. Springer Science & Business Media, 2010.
[8] Persi Diaconis, Charles Stein, Susan Holmes, and Gesine Reinert. Use of exchangeable pairs in the analysis simulations. Stein's Method, pages 1-25. Institute of Mathematical Statistics, 2004.
[9] Qin Ding, Cho-Jui Hsich, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics, pages 1585-1593. PMLR, 2021.
[10] Jianqing Fan, Wenyan Gong, and Ziwei Zhu. Generalized high-dimensional trace regression via nuclear norm regularization. Journal of econometrics, 217(1):177-20,, 2019.
[11] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case, In NIPS, volume 23, pages 586-594, 2010.
[12] Aditya Gopalan, Odalric-Ambrym Maillard, and Mohammadi Zaki. Low-rank bandits with latent mixtures. arXiv preprint arXiv:1609.07 2016.
[13] Botao Hao, Jie Zhou, Zheng Wen, and Will Wei Sun. Low-rank tensor bandits. arXiv preprint 1oXi::2007.15788 2020.
[14] Prateek Jain and Inderjit S Dhillon. Provable inductive matrix completion. arXiv preprint arXiv:1306.0626, 2013.
[15] Kyoungseok Jang, Swang-Sung Jun, Se- Young Yun, and Wanmo Kang. Improved regret bounds of bilinear bandits using action space analysis. In International Conference on Machine Learning, pages 4744-4754 PMLR, 2021.
[16] Nicholas Johnson, Vidyashankar Sivakumar, and Arindam Banerjee. Structured stochastic linear bandits. arXiv preprint 1606v 2016.
[17] Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learning, pages 3163-3172. PMLR, 2019.
[18] Sumeet Katariya, Branislav Kveton, Csaba Szepesvári, Claire Vernade, and Zheng Wen. Bernoulli rank-1 bandits for click feedback. arXiv preprint arXiv:1703.065133 2017.
[19] Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, and Zheng Wen. Stochas- tic rank-1 bandits. In Artificial Intelligence and Statistics, pages 392-401. PMLR, 2017.
[20] Branislav Kveton, Csaba Szepesvári, Anup Rao, Zheng Wen, Yasin Abbasi- Yadkori, and Muthukrishnan. Stochastic low-rank bandits. arXiv preprint arXiv:1712.04644 2017.
[21] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[22] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[23] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[24] Wenjie Li, A darsh Barik, and Jean Honorio. A simple unified framework for high dimensional bandit problems. arXiv preprint ww.ivv2202.000 102.09666, 2021.
[25] Xiuyuan Lu, Zheng Wen, and Branislav Kveton. Efficient online recommendation via low-rank ensemble sampling. In Proceedings of the 12th ACM Conference on Recommender Systems, pages 460-464, 2018.
11

---

[26] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, pages 460-46 4668. PMLR, 2021.
[27] Stanislav Minsker. Sub- Sub-gaussian estimators of the mean of random matrix with heavy-tailed entries. The Annals of Statistics, 46(6A):2871-2903 2018.
[28] Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, Bin Yu, et al. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Statistical science, 27(4):538-55) 557, 2012.
[29] Yaniv Plan and Roman Vershynin. The generalized lasso with non-linear observations. IEEE Trunsactions on information theory, 62(8):1528-1555 2016.
[30] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Restricted eigenvalue properties for correlated gaussian designs. The Journal of Machine Learning Research, 11:2241-2255 2010.
[31] Candice Schumann, Zhi Lang, Nicholas Mattei, and John Dickerson. Group fairness in bandit arm selection. arXiv preprint arXiv: arXiv: 1912.03002, 2019.
[32] Gilbert W Stewart. Matrix perturbation theory. 1990.
[33] Cindy Trinh, Emilie Kaufmann, Claire Vernade, and Richard Combes. Solving bernoulli rank-one bandits with unimodal thompson sampling. In Algorithmic Learning Theory, pages 862-889. PMLR, 2020.
[34] Laurens Van Der Maaten, Eric Postma, Jaap Van den Herik, et Dimensionality reduction: comparative. J Mach Learn Res, 10(66-71):13,, 2009.
[35] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[36] Michael Woodroofe. A one ared bandit problem with a concomitant variable. Journal of the American Statistical Association, 74(368):799-806, 1979.
[37] Zhuoran Yang. Krishnakumar Balasubramanian, and Han Liu. High-dimensional non -ou-gaassian single index models via thresholded score function estimation. In International Conference Machine Learning, pages 3851-3860. PMLR, 2017.
[38] Kai Zhong, Prateek Jain, and Inderjit S Dhillon. Efficient matrix sensing using rank-1 gaussian measurements. In International conference algorithmic learning theory, pages 3-18. Springer, 2015.
[39] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with base exploration. International Conference on Machine Learning, pages 1492-11500 PMLR, 2020.
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] We discuss the limitation of our
first algorithm G-ESTT in the beginning of Subsection 4.2
(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]
12

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect 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 (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you 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 participants and screenshots, 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": "rzeawkFlZkd", "reviewer": "Reviewer_Bwj4", "summary": "This paper proposes efficient algorithms for matrix GLM bandit with regret and runtime guarantees additive in the matrix dimensions a significant improvement from previous work on low-rank bandits with linear and non-linear rewards (generalized linear model). Both the algorithms are verified on a suite of numerical experiments. ", "questions": "--\nDid the authors consider other methods to detect low-rank especially those based on random projections, thresholding and PCA, at least int the numerical section?", "limitations": "--\nWriting can be significantly improved. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-- Strengths:\n1. The extension to GLM reward using a quadratic optimization problem is non-trivial. This forms the key novel step in the first algorithm, while the second step relies on a standard GLM-UCB algorithm. The novelty for the reduction to low-dimensional space lies in construction of an oracle inequality. Although, this reduces the regret incurred by the bandit algorithm making its implementation computationally expensive.\n\n2. In order to improve the computational complexity of the proposed algorithm, the authors suggest another algorithm by excluding inclusions into a properly determined subspace thereby allowing to invoke any low-dimensional GLM bandit algorithm. Surprisingly, this inclusion doesn't lead to large estimation error as compared to the previous algorithm. \n\n-- \nWeakness: \n\n1. Writing can be significantly improved. While the paper is technical, the description of the results and the intuition behind them can be elucidated using a clear language. ", "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": "rjetvKBsfh2", "reviewer": "Reviewer_APoi", "summary": "The paper considers generalized low-rank matrix bandit problems. The expected rewards are modeled as $\\mu(\\langle \\Theta^*, X_t\\rangle)$ and $\\Theta^* \\in \\mathbb{R}^{d_1 \\times d_2}$ is an unknown low-rank matrix with rank $r$. \nFor this problem, the authors firstly proposed the subspace extraction-based algorithm G-ESTT. \nG-ESTT's subspace extraction guarantee is based on Stein's method.\nIn stage 2 of the G-ESTT, based on the extracted subspace, LowGLM-UCB is run. \nThe overall regret guarantee is improved from the previous algorithm. \nThey further proposed G-ESTS, which is an even faster (in time complexity) algorithm than G-ESTT.\nG-ESTS achieves the same order of the bound of G-ESTT, and improved bound when the action set is finite. \nFinally, numerical experiments on the synthetic data have shown the efficacy of the proposed algorithm in terms of the empirical time complexity and the overall regret.\n", "questions": "### Major question\n\nWith the constant upper bounds on the matrix norm, S_f, can D_{rr} be kept constant independent of d?\nIntuitively, I feel that since the magnitude of the element of the matrix is suppressed by 1/d, etc., the size of the eigenvalue also depends on d for wide range of instances.\nI would like to know if there are many examples that are not dependent on d.\n\n### minor \n\nline 180, k-dimensional?\n\nline 194, x_t, should be x_k?\n\nimprovement from (d_1 + d_2)^{3/2} \\sqrt{rT} to (d_1 + d_2)r \\sqrt{T} is only in d_1 and d_2? for some regime, dependence on r is disimproved?\n\nline 253, experments\n\nline 244, why you say O(\\sqrt{kT}) in theorem statement but O(k\\sqrt{T}) in the footnote?\n\n LowGLM-UCB,  (P)LowGLM-UCB,  PLowGLM-UCB: namings are a little bit confusing. \n\nIt looks to me that G-ESTS is better than G-ESTT in every aspect. Is there any reason why you present G-ESTT too, instead of only presenting G-ESTS? Is there any advantage of G-ESTT over G-ESTS?\n\nWhy numerically, the algorithm is only compared with LowESTR?\n\n\n\n\n\n", "limitations": "See questions above.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n\nImproved regret guarantees the problem with standard assumptions and with additional assumptions. \n\nComputationally efficient algorithm (G-ESTS) is proposed.\n\n- Weaknesses\n\nExplore then commit type algorithm (although two stages are sharing some data, I think it's true for subspace extractions.) is not practical.\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": ""}, "extra_text": {}}, {"review_id": "jbJLqca3MHN", "reviewer": "Reviewer_SuJ7", "summary": "This paper proposes two efficient algorithms called G-ESTT and G-ESTS for generalized low-rank matrix bandit problems. Both algorithms achieve the optimal regret bound up to logarithm terms. G-ESTT extends the two-stage algorithm LowESTR to the nonlinear reward setting, and G-ESTS further drops all negligible entries to get a low-dimensional bandit, significantly reducing the computational costs.\n", "questions": "1. Since G-ESTT adopt the similar two-stage framework as LowESTR, I hope the authors can provide some intuitive explanation why G-ESTT can improve the regret bound by $\\sqrt{d}$.\n2. Assumption 3.3 seems proposed for fixed action set. If the action set is time-varying, should the sampling distribution be also time-varying?\n3. In the experiments, Which sampling distribution is used in stage 1? the accuracy for subgradient methods?\n4. SGD-TS algorithm is designed for the finite arm setting. I hope the authors can provide some efficient generalized linear bandit algorithms for infinite arms.\n5. The proposed algorithms only achieves the optimal regret when $d_1=d_2$. What is the lower bound of the low-rank matrix bandits where $d_1$ is far from $d_2$? If the lower bound is $O(r\\sqrt{d_1d_2T})$ rather than $O((d_1+d_2)r\\sqrt{T})$, the proposed algorithms are suboptimal in this case.\n6. What is the lower bound of generalized low-rank matrix bandit problem with finite arm? \n", "limitations": "no potential negative societal impact ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is mostly clear.\n2. The technical contribution is solid. The proposed algorithms achieve the optimal regret up to logarithm terms. In addition, the G-ESTS algorithm is very efficient.\n\n\nWeaknesses:\n1. The paper only contains experiments with synthetic data. It would be better if real data experiments were included.\n2. Some details need more clarifications (see Question part).", "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": "4_i_lxJ86oH", "reviewer": "Reviewer_gC7G", "summary": "This paper deals with the generalized low-rank matrix bandit problem, where for each time the learner choose one action with its own feature matrix, and receives a noisy reward by the inner product of the chosen action feature matrix and a hidden matrix $\\Theta^*$ with know rank $r$. \n\nThis paper uses ingenious Stein's method based approach to estimate the subspace even more accurately compare to the previous approaches, and this is the core originality of this paper. Thanks to this new estimation, the author invented the algorithms G-ESTT and G-ESTS, which shows $O(dr\\sqrt{T}/D_{rr})$ regret bound which matches to the known regret lower bound of the generalized linear bandit problem. The second algorithm, G-ESTS, removes the redundant dimensional parts in calculation and still theoretically performs well. \n\nThe author also shows the practicality of their algorithm by the experiment. ", "questions": "Main question (will change my opinion)\n\nabout the reusing the data\n\nI feel quite suspicious about reusing the data. In line 195-206, they advertise that they need no more projection or additional sampling by reusing the data from Stage 1. However, I doubt about the independence. The samples in Stage 1 already affects the coordinates, and this re-organizing coordinate affects the calculation of $ {L}_t^{\\Lambda} (\\theta) $, especially about the last regularizer term $\\|\\theta\\|_\\Lambda$. The new coordinate is decided by $X_i ( i=1, \\cdots t)$ and every calculation is based on this new coordinate rotation. $\\Lambda$ penalizes some of the new coordinates where the experiment results from $X_i ( i=1\\cdots t)$ shows high regret. Are you sure that you can guarantee the independence of the result and okay to mix the data from the 1st stage and 2nd stage?\n\nI believe that this is the point that the author should clarify. \n\n\n\nOther questions\n\n1) Could you tell me intuitively why the Stein's method works better to estimate matrix completion compare to the previous approaches? I read your proof and understand that your proof will be correct (about theorem 2), but I want to get some hunch about why it shows more accurate estimation ($\\frac{dr}{T}$) in terms of Frobenius norm than the previous approach ($\\frac{\\sqrt{d^3r}}{T}$). \n\n2) This paper assumes that we already got a distribution $\\mathcal{D}$ which satisfies a certain assumption. It would be great if this paper describes how to get such a distribution from a given action set. I know that you described something in Line 129-135, but it doesn't make sense to me, even after I read your Appendix I. You said, \n\n1-find the convex hull of $\\mathcal{X}$ which contains the ball of radius R\n2-$p_ij$ is now centered gaussian with variance $\\frac{R^2}{d_1 d_2}$\n\nAre you sure that sample from $\\mathcal{D}$ always lies in $\\mathcal{X}$? For example, imagine a thin shell action set with out-radius R and inner radius 0.99R. Then there might be almost no hope that your distribution lies in this shell, right? In fact, there's no detail description about the sampling method in Appendix I. Please let me know if there's a detail I missed.\n\nThere are several papers related with this exploration planning in the linear bandit field, especially using something like G-Optimality. I want this level clear, if possible. \n\n3) Is the minimum eigenvalue condition really necessary in this problem? Could you introduce any related works where this term is inevitable? At least (Jang et al, 2021) didn't have the minimum eigenvalue term in the algorithm as far as I remember. ", "limitations": "1) There is a hidden factor in regret which is the 'minimum eigenvalue' term. It is not intuitive to me that when minimum eigenvalue is extremely small, this matrix can be additional dimensional dependency which makes this paper weaker. \n\n2) The way to draw the samples should be suggested. The author should prove that their assumption is really a mild one. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) Originality:\n1-1) Strength \n\nTheir strength is the new subspace estimation method, which is based on a different approach called Stein's method. As far as I know, there was no similar work using Stein's method in this field. \n\nThey also provide a bold subtraction approach (in ESTS). Previous papers with similar structure with this paper usually keep caring of the redundant dimensions, $(r+1: d_1, r+1:d_2)$, for the rest of the bandit calculation (mainly for the theoretical safety). This paper proves that the learner don't need to care the redundant dimensions anymore. \n\nThis paper also introduces Stein's method for the matrix completion, which provides more accurate estimation than the previous approaches.\n\n1-2) Weakness:\n\nThis paper is basically follows the similar structure with ESTR (Jun et al, 2019, Lu et al, 2021) and shares the similar drawback. \nMost importantly, the regret bound depends on the size of the minimum eigenvalue of $\\Theta^*$. \nThis is of course not intuitive - it's like, for the traditional multi-armed bandit sense, the regret increases when the reward of the minimum reward arm is small. Usually the gap between the optimal and sub-optimal is important in the regret analysis of the bandit, not the minimum one. \nI think this is a kind of the hidden dimensional dependency for the result of this paper, and should be improved in the future.\n\n\n\n2) Quality - Problematic\n\nOverall, the proof seems correct for the core part(Theorem 4.1 and Theorem 4.2 - assuming their re-using the data is not problematic) so their claim is supported by theoretical analysis. It also provides several theoretical discussions in the Appendix, like Appendix J. \n\nHowever, I feel quite suspicious about reusing the data. In line 195-206, they advertise that they need no more projection or additional sampling by reusing the data from Stage 1. However, I doubt about the independence. The samples in Stage 1 already affects the coordinates, and this re-organizing coordinate affects the calculation of ${L}_t^{\\Lambda} (\\theta)$, especially about the last regularizer term $\\|\\theta\\|_\\Lambda$. The new coordinate is decided by $X_i (i=1, \\cdots t)$ and every calculation is based on this new coordinate rotation. $\\Lambda$ penalizes some of the new coordinates where the experiment results from $X_i (i=1, \\cdots t)$ shows high regret. Are you sure that you can guarantee the independence of the result and okay to mix the data from the 1st stage and 2nd stage?\n\nI believe that this is the point that the author should clarify. \n\n\nPlus, I am not clear how to get the distribution $\\mathcal{D}$ if only action sets are given. If it is difficult to create such distribution, then Assumption 3.3 is not trivial, which makes this paper weaker. \n\n\n3) Clarity: \n\nBasically, the paper describes what they do with some clarity, but of course there are some typos and abuse of notations. I think these are minor, and I believe these drawbacks will be fixed after this paper is accepted. \n- The use of $S$ is very confusing. Sometimes it is the bound of $\\|\\Theta^*\\|$, and sometimes it is the score function when the distribution is 'obvious'. I was spending quite a time for finding the line 119. \n- In line 152, I want the writers to clarify that they will apply the function entrywise. \n- In line 175 and Eq. (8), I believe this result is not that obvious. At least make a section in the Appendix will be great (or at least the exact place of reference)\n- In Eq. (10), the time index for two summation ($T_1$ and $t$) confuses the reader. I believe it might be the first exploration stage and the second bandit stage, but it confuses me first. \n- In Lemma B.2, what is g?\n- In the last equation of line 457, it seems like the index is missing in the summation.\n- In line 458, first inequality, $n$ to $T_1$\n\nNot about clarity, but it is known that if X is $\\sigma$-subgaussian, then $var(X)\\leq \\sigma^2$. See the Lemma 5.4 of the book 'Bandit Algorithm', Lattimore and Szepesvari\n\n\n\n\n4) Significance:\n\n4-1) Strength\n\nThis paper proves the matching upper bound compare to the lower bound proved by Lu et al (2017), and finishes the argument what is the optimal regret order for the generalized low-rank bandit. It also introduces a new method called Stein's method to this field. \n\n4-2) Weakness\n\nThis matrix bandit field itself is a relatively small field, so it would be better if the author explains how his ingenious approach can be extended to other larger fields. ", "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