PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits
Authors: Kyoungseok Jang
Chicheng Zhang
Kwang-Sung Jun
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-armed bandits
linear bandits
sparse linear bandits

Abstract: In sparse linear bandits, a learning agent sequentially selects an action from a fixed action set and receives reward feedback, and the reward function depends linearly on a few coordinates of the covariates of the actions. This has applications in many real-world sequential decision making problems. In this paper, we devise a simple, novel sparse linear estimation method called $\textrm{PopArt}$ that enjoys a tighter $\ell_1$ recovery guarantee compared to Lasso (Tibshirani, 1996). Our bound naturally motivates an experimental design criterion that is convex and thus computationally efficient to solve. Based on our novel estimator and design criterion, we derive sparse linear bandit algorithms that enjoy improved regret upper bounds upon the state of the art (Hao et al., 2020), especially in terms of the geometry of the given action set. Finally, we prove a matching lower bound for sparse linear bandits in the data-poor regime, which closes the gap between upper and lower bounds in prior work.


PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits
Kyoungseok Jang University of Arizona ksajks@arizona..dd
Chicheng Zhang
Kwang-Sung Jun University of Arizona kj kjundes. arizona. edu
University of Arizona chichengzocs. arizona. edu
Abstract
In sparse linear bandits, learning agent sequentially selects action and receive reward feedback, and the reward function depends linearly on a few coordinates the covariates of the actions. This has applications in many real-world sequential decision making problems. In this paper, we propose a simple and computationally efficient sparse linear estimation method called POPART that enjoys tighter & recovery guarantee compared to Lasso (Tibshirani, 1996) in many problems. Our bound naturally motivates an experimental design criterion that convex and thus computationally efficient to solve. Based on our novel estimator and design criterion, we derive sparse linear bandit algorithms that enjoy improved regret upper bounds upon the state of the art (Hao et al., 2020), especially w.r.t. the geometry of the given action set. Finally, we prove a matching lower bound for sparse linear bandits in the data poor regime, which closes the gap between upper and lower bounds in prior work.
1 Introduction
In many modern science and engineering applications, high-dimensional data naturally emerges, where the number of features significantly outnumber the number of samples. In gene microarray analysis for cancer prediction [30), for example, tens of thousands of genes expression data measured per patient, far exceeding the number of patients. Such practical settings motivate the study of dith-immensional statistics, where certain structures of the data are exploited to make statistical inference possible. One representative example is sparse linear models [19], where we assume that linear regression task's underlying predictor depends only on small subset of the input features.
On the other hand, online learning with bandit feedback, due to its practicality in many applications such online news recommendations 25 or clinical trials (26 41 has attracted surge of research interests. Of particular interest is linear bandits, where in n rounds, the learner repeatedly takes medicine) from a of available A.) T): as feedback where 7): E IR is an independent zero-mean, a-sub-Gaussian noise. Sparsity structure is abundant in linear bandit applications: for example, customers' interests on a product depend only on number of its key specs; the effectiveness of medicine only depends on a number of key medicinal properties, which means that the unknown parameter 8* sparse; i.c., it has a small number of nonzero entries.
an action A, (e.g., some feature representation of product
actions A c IRd and receives a reward (O",A.)
Early studies (2 g 24 sparse linear bandits have revealed that leveraging sparsity assumptions yields bandit algorithms with lower regret than those provided by full-dimensional linear bandit algorithms [ [.. However, most existing studies either rely particular set (e.g.. norm ball), which is unrealistic in many applications, or use computationally intractable algorithms.
If we consider an arbitrary arm set, however, the optimal worst-case regret is O (ddd)) where the sparsity level of 0*, which means that as long as O(sd), there exists an instance for which the algorithm suffers a linear regret (23). This is in stark contrast to supervised learning
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

REGRET BOUND
DATA-POOR
ASSUMPTIONS
HAO ET AL.
18
0 2-3 2 min 2 2/3 2
A SPANS Rd
HAO ET AL.
18
A SPANS Rd
ALGORITHM
(OURS)
H2li 2/3) 2 (15 N n
A SPANS R"
THEOREM
5
(QURS)
A SPANS R"
HAO ET AL.
18
O C min 8n)
X A SPANS R", MIN. SIGNAL
ALGORITHM 4 (OURS)
O (V55) 57)
X A SPANS R", MIN. SIGNAL
Table I: Regret bounds of our work and the prior art where 8, d, n are the sparsity level, the feature dimension, and the number of rounds, respectively. The quantities Cmin and H2 are the constants that captures the geometry of the action set (see Eq. (6) and (5). and i. is parameter for specific family of arm sets that satisfies & @(Cmla) - e (H.). In general, H S Cmin S Cmu (Propositon)
where it is possible enjoy nontrivial prediction error bounds for = o(d) [6]. This motivates natural research question: Can we develop computationally efficient sparse linear bandit algorithms that allow a generic arm set yet enjoy problem-depender characteristies?
enjoy nonvacuous bounds in the data-poor regime by exploiting
The seminal work of Hao al. [8]] provides positive answer to this question. They propose algorithms that enjoy nonvacuous regret bounds with an arbitrary arm set in the data poor regime
where Cmin is an den-enede quantity. However, their work still left a few open problems. First, their regret upper bound does not match with their lower bound 22(Cmin -1/3 g//3 2/3). Second, is not clear Cmin is the right
using Lasso. Specifically, they have obtained regret bound of OC -2/3 -2/332/3 n2/3))
constant that captures the geometry of the arm set.
In this paper, we make significant progress in high-dimensional linear regression and sparse linear bandits, which resolves or partly answers the aforementioned open problems.
First (Section D. we propose novel and computationally efficient estimator called POPART (POPu- lation covariance regression with hARd Thresholding) that enjoys tighter & norm recovery bound than the de facto standard sparse linear regression method Lasso in many problems. Motivated by the & norm recovery bound of POPART, we develop cumputationalllytracttt objective for finding the sampling distribution that minimize the error bound of POPART, which is useful in settings where we have control on the sampling distribution (such as compressed sensing). Our design of experiments results in an l norm error bound that depends on the measurement set de- pendent quantity denoted by H2 (see Eq. (5) for precise definition) that provably better than Cmin" -1 that appears in the & norm eтror bound used in Hao et al. [18, thus leading to an improved planning method for sparse linear bandits. Second (Section
design of experiment
Using POPART, we design new algorithms for
the sparse linear bandit problem, and improve the regret upper bound of prior work [18); ; see Table [] for the summary. Third (Section (5). We prove matching lower bound data-poor regime, showing that the regret rate obtained by our algorithm is optimal. The key insight in our lower bound is novel application of the algorithmic symmetrization technique [4]. Unlike the conjecture of Hao et al. [18] Remark 4.5], the improvable part was not the algorithm but the lower bound for sparsity s.
We empirically verify our theoretical findings in Section 6 where POPART shows a favorable per- formance over Lasso. Finally, we conclude our paper with future research enabled by POPART in Section 7 For space constraint, we discuss related work in Appendix A but closely related studies are discussed in depth throughout the paper.
Problem Definition and Preliminaries
Sparse linear bandits. We study the sparse linear bandit learning setting, where the learner given access to an action space A = {a e IRd : |a]l.> S 1}, and repeatedly interacts with the environment as follows: at each round t In. the learner chooses some action A, e A, and receives reward feedback r; = (0" At)+ where 8* Rd is the underlying reward predictor, and is an independent zero-mean subgausssian noise. We assume that 8* is s-sparse; that is, has at most s nonzero entries. The goal of the learner is to minimize its pseudo-regret defined as
Reg(n) max (0', .a) aeA
Σ O Ad) t=1

---

Experimental design for linear regression. In the experimental design for linear regression problem, one has pool of unlabeled examples X, and some underlying predictor 0 to be learned. Querying the label of æ, i.e. conducting experiment æ, reveals random label y (0", ) associated with it, where 1) a zero mean noise random variable. The goal accurately estimate 0", while using as few queries x as possible.
Definition 1. (Population covariance matrix Q) Let P(X) be the space of probability measures over X' with the Borel o-algebra, and define the population covariance matrix for the distribution P(X) follows:
Q(u) = SLe. aa' dp(aa
(1)
Classical approaches for experimental design focus on finding a distribution l such that its induced population covariance matrix (()) has properties amenable for building a low-error estimator, such as D-, A-, G-optimality [4].
Compatibility condition for Lasso. For a positive definite matrix Σ Rdddd and sparsity level s [d] == (I,...,d}, we define its compatibility constant (E, s) as follows:
sv Ev
min S=[d]=[]== olesh mlsshss3/essl
min
Iusll
where Uig E R& denotes the vector that agrees with in coordinates in S and 0 everywhere else and V-S E IR denotes v Us.
Notation. Let be the i-th canonical basis vector. We define [xr] = (1,2,.., Let supp(0) be the set coordinate indices where 0g O. We use $ to denote that there exists an absolute constant such that S cb.
3 Improved Linear Regression and Experimental Design for Sparse Models
In this section, we discuss our novel sparse linear estimator POPART for the setting where the population covariance matrix is known and show strong theoretical properties. We then present variation of POPART called WARM-POPART that amends a potential weakness of POPART, followed by our novel experimental design for POPART and discuss its merit over prior art.
POPART RT (POPulation covariance regression with hA Rd Thresholding). Unlike typical estimators for the statistical learning setup. our main estimator POPART described in Algorithm ! takes the population covariance matrix denoted by Q as input. We summarize our assumption for POPART.
Assumption 1. (Assumptions on the input of POPART) There exists μ such that the input data points
((X,, Y.) satisfy that X, iid. μ and Q = Q(u)= := [x=p[XXX* [XX]]. Furthermore, Y, (0", X,) with y. being zero-mean a-subgaussian noise. Also, Ro 2 max A (a, 0* 0o)l-
Algorithm 1 POPART (POPulation covariance regression with hARd Thresholding)
1: Input: Samples {(X,, H the population covariance matrix Q Rdxd pilot estimator 0g Rd, an upper bound Ro of max ((a 0" Oo)], failure rate 5.
2: Output: estimator θ
3: for t= 1,..., n do
4: 0, = 1---Q"Xxp X,,Y, (Xi, + 0o
5: end for
6: Vi [d], Catoni (0., (0., es) 12 an 2 where a;
2log
n(R3+o
2log
m-2lng
7: 0 - clip, (0' [0] 1 ((0))> A where X; is defined in Proposition
8: return i
POPART consists of several stages. the first stage, for each (X,, Y)) pair, we create a one- sample estimator 0, (step/4). The estimator, 0,, can be viewed as a generalization of doubly-robust estimator [10 12 for linear models. Specifically, it is the sum of two parts: one is the pilot estimator

---

8n that is a hyperparameter of POPART; the other is of the difference 6* do- Thus, it is not hard to see that 0g is an unbiased estimator of 0" As we will see in Theorem [ the variance of 0, is smaller when 0g is closer to 0" showing the advantage of allowing pilot estimator Og as input. If no good pilot estimator is available priori, one can set 0g = O.
Bo)). unbiased estimator
From the discussion above, it is natural to take an average of bj. Indeed, when v. is large, the population covariance matrix (xx)) is close to empirical covariance matrix Q == Σm- X,X7, which makes Oay == E+-1 0g close to the ordinary least squares estimator Pors = ( E X,Y.). However, for technical reasons, the concentration property of Owe is hard to establish. This motivates POPART's second stage (step6), where, for each coordinate E [d], we employ Catoni's estimator [27 (see
Appendix B for a recap) to obtain an intermediate estimate for each 0r, namely 0'.
To use Catoni's estimator, we need to have an upper bound of the variance of 0 for its a, parameter. A direct calculation yields that, for all é [d] and t [n]],
Var(Ox))
max (0" 1 lo, a)² +o² max max(Q(u))))+ aeA
where 0N::= := (0t,es). es). This implies that (R2 + ²²) max: (Q(u)))) i: is an upper bound of Var(O.)). By the standard concentration inequality of Catoni's estimator (see Lemma[T), we obtain the following estimation error guarantee for 8%: the proof can be found Appendix C.I Hereafter, all proofs are deferred to appendix unless noted otherwise.
Proposition 1. Suppose Assumption holds. In POPART, for i [d]. if n 21n 2d the following 8.
inequality holds with probability g:
1 A(R (Q(H)))) )
2d log 8 =: A
- --11
n2
X;) forms confidence interval for 0f Therefore, if O é (0'- - X; Ac), we can infer that 0, # 0, i.e., i supp(0"). Based on the observation above, POPART'S last stage (step performs a hard-thresholding for each of the coordinates of 0', using the threshold X; for coordinate i. Thanks to the thresholding step, with high probability, d's support is contained in that of 0", which means that all coordinates outside the support of 0* (typically the vast majority of the coordinates when < d) satisfy 0, 0g 0. Meanwhile, for coordinate i's in supp((*) ), the estimated value 0, is not too far from 07
Proposition 1 shows that, for each coordinate (8,- 64
The following theorem states POPART's estimation error bound in terms of its output O's lee, to. and & errors, respectively. We remark that replacing hard thresholding in the last stage with soft thresholding enjoys similar guarantees.
Theorem 1. Take Assumption I Let H²(Q)= max +tt. Then, POPART has the following guarantees with probability at least 1 1-8: 8:
ii Vi [d], 0,1 < 2
4 (²)((()))))))))))))))))))))))))) Da log 2d so 10 0¹ 10 <2V
4( ((
log 2d
(ii) supp(() supp(0") so 10 0* s.
(ii) | 0* 11 s 2 A(R "H
log 2d 2d
Interestingly, POPART has no false positive for identifying the sparsity pattern and enjoys Exe error bound, which not available from Lasso, to our knowledge. Unfortunately, a direct comparison with Lasso is nontrivial since the largest compatibility constant ( s) is defined as the solution of the optimization problem (2), let alone the fact that ( s) is function of the empirical covariance matrix. While we leave further investigation as future work, our experiment results in Section
suggest that there might be a case where POPART makes a meaningful improvement over Lasso.
Let max; \ (H²++))))(((())) log From Proposition and the union bound, one can check that
Proof of Theorem 1
n
110' 10'-0'1le 10 <
(3)

---

with probability 1 1-6 8. Therefore, the coordinates in supp(0") will be thresholded out because of |00 10 X. Therefore, (ii) holds and for all i supp (0)) 10, 0 O.
By definition, = clip, (f"), we can say that | 0'1 s A. Plus, by Eq. 3 10" -0- 10 X. By the triangle inequality, |00 ~o s 2A. Therefore, (i) holds.
Lastly, (iii) can be argued as follows:
| 0
Σ =c[d]
10,-011
Σ 0+ Σ
22 S 2s>
iesupp(0*)
WARM-POPART Improved guarantee by warmup. One drawback of the POPART estimator is that its estimation error scales with VRa + o², which can be very large when Rg is large. One may attempt to use the fact that POPART allows pilot estimator Oo to address this issue since Ro gets smaller as Og is closer to 0" However, it is a priori unclear how to obtain 0g close to 0" as 0" is the unknown parameter that wanted to estimate in the first place.
To get around this "chicken and egg" problem, we propose to introduce a warmup stage, which we call WARM-POPART (Algorithm 2
consists of two stages. For the first warmup stage, the algorithm runs POPART RT with the zero vector as the pilot estimator and with the first half of the samples to obtain a coarse estimator denoted by O which guarantees that for large enough no. ||0g - 8' 1|1 $ a. In the second stage, using & as the pilot estimator, it runs POPART on the remaining half of the samples.
Algorithm 2 WARM- POPART
1: Input: Samples {(X,, Y,) 1 the population covariance matrix Q Rdddd an upper bound
Ryna of max ( number samples no. failure rate d.
2: Output: 0, an estimate of 6"
3: Run POPART (X,,, (X), !x)) -2, Rmma)) to obtain do. a coarse estimate of 0 for the next step.
4: Run POPART( (XX,, ) i=/n0/2j-1 Q 0, 0. to obtain 0, an estimate of e".
The following corollary states the estimation error bound of the output estimator ô. Compared with POPART'S & recovery guarantee, WARM-POPARTE dependence on Rmaxi its dependence on Rmax only appears in the lower bound requirement for no.
recovery guarantee (Equation (4) has no
Corollary 1. Take Assumption without the condition on Rg. Assume that Rmax 2 max Ke, 0*) and no > 32s"(R" (R Hr log 2d. 8. Then, WARM-POPART has, with probability at least 1 25,
d²
H²(Q())) 2d
10 - 0' s 880
710
Remark 1. In Algorithm 2] we choose POPART as our coarse estimator, but we can freely change the coarse estimation step (step 3 to other principled estimation methods (such Lasso) without affecting the main estimation error bound 44; the only change will be the lower bound requirement of My to another problem-deppe dependent constant.
Remark 2. WARM-POPART requires the knowledge of R an upper bound of max (8 a>l: this requirement can be relaxed by changing the last argument of the coarse estimation step (step 3)
from Rmax. to some function / (Tan) such that f (no) = (1)) and f(nn) = of /nn) (say, on ): with this change, a result analogous to Corollary I can be proved with different lower bound requirement of rip-
A novel and efficient experimental design for sparse linear estimation. In the experimental
design setting where the learner has freedom to design the underlying sampling distribution μi, the naturally motivates design criterion. Specifically,
l error bound of POPART and WARM-POPA we can choose μ that minimizes (²))) which gives the lowest estimation error guarantee. We denote the optimal value of H (Q()))) by
H min max (ax)(QQ)))))))
(5)
(A) &[d]
5

---

The minimization of (Q)))) is a convex optimization problem, which admits efficient methods for finding the solution. Intuitively, H² captures the geometry of the action set A.
To compare with previous studies that design sampling distribution for Lasso, we first review the standard ( error bound of Lasso.
Theorem 2. (Buhlmann and van de Geer 6 Theorem 6.1]) With probability at least 1 26, the
& e-essimatioon error of the optimal Lasso solution Lasso satisfies
Eq. (2.2)) with X (2d)g(2d/
||0 1
s0
log (ldg()d/))
(g (5,,
where @u (E, is the compatibility constant with respect to the empirical covariance matrix Σ Σn X,X7 and the sparsity s in Eq. (2)
Ideally, for Lasso, experiment design which minimizes the compatibility constant will guarantee the best estimation error bound within a fixed number of samples n. However, naively, the computation of the compatibility constant intractable since Eq. (2) is combinatorial optimization problem which is usually difficult to compute. One simple approach taken by Hao et al. [18 to use the following computationally tractable surrogate of og(5, s):
Cmin : max Amin Ammin(QUu (Q(1))
(6)
(EP(A)
where Amin (A) denotes the minimum eigenvalue of matrix A. With the choice of sampling distribution argmax (Q(H), and n 2 ÿ2( s-polylng(d) ), with high probability, (
Cuin"
(eA(
Cmin/2 22 holds 33 Theorem 1.8), and one can replace do (É,s) s) to Cmin/2 in Theorem 2 to get the following corollary:
Corollary With probability at least 1 - exp(-en) 25 for some universal constant c, the 4
estimation error of the optimal Lasso solution fasso satisfies
280
2 log 2log(2d/6)
1
0*
Cmin
The following proposition shows that our estimator has a better error bound compared to the surrogate experimental design for Lasso Hao et [18].
Proposition 2. We have H2 C dHH.. Furthermore, there exist arm sets for which either of the inequalities is tight to a constant factor.
Therefore, our new estimator has & error guarantees at least a factor C 1/2
better than that provided min
by 18). follows: when we choose the μ as the solution of the Eq. 5). then
In (2d/5)
In(2d/5)
(2(285)) S (RHS of
(RHS of 4 S sa H.
S S0 1122
S so
In addition, we also prove that there exists a case where our estimator has an d/s- d/s-order better error bound compared to the traditional lasso bound in Theorem 2 although this is not in terms of the compatibility constant of the empirical covariance matrix Σ.
Proposition 3. There exists an action set A and an absolute constant C1 0 such that
H. < C
(E,
For the detailed proof about Proposition and Proposition 3 Section D in Appendix.

---

Improved Sparse Linear Bandits using WARM-POPART
We now apply our new WARM-POPART sparse estimation algorithm to design new sparse linear bandit algorithms. Following prior work [18], we adopt the classical Merhorrethen-Comeee (ETC) framework for algorithm design, and use POPART with experimental design to perform exploration. As will see, the tighter l estimation error bound of our POPART-basee estimators helps obtain an improved regret bound.
Algorithm 3 Explore then commit with WARM-POPART
1: Input: time horizon n, action set A. warm-up exploration length no. failure rate d, reward threshold parameter Rmax. an upper bound max (0" a){.
2: Solve the optimization problem in Eq. (5) and denote the solution M4
3: for wort=,.m =..t...... Ay do
4: Independently pull the arm A, according to μa, and receives the reward rı
5: end for
6: Run WARM- (A.) (ra)mn Quv,), 6, Rmax) to obtain 0, estimate of 0*
7: for L== n10 + ,...., do
n
8: Take action A, = arg m (0, a), receive reward Tr = +
9: end for
Sparse linear bandit with WARM- Our first new algorithm, Explore then Commit with WARM-POPART (Algorithm D proceeds follows. For the exploration stage, which consists of the first no rounds, it solves the optimization problem (5) to find μu, the optimal sampling distribution for POPART and samples from it to collect a dataset for the estimation of 0*, Then, we use this dataset compute the WARM-POPAR estimator Å. Finally, in the commit stage, which consists of the remaining n - T2 rounds, we take the greedy action with respect to Ó. We prove the following regret guarantee of Algorithm 3
Theorem 3. If Algorithm has input time horizon n > 16 Riaxx R2 (R +o 20
2d log action
r² 2d R ) A1 40 set A [-1,+1]6, and exploration length no 1 log then with probability least 1 26, Reg(n) &R (s20² H2n n log 2
8
8
log
2d
no
Proof. From Corollary 11 s 2s)1 with probabiliiy at least 1-28. Therefore, with probability 1 25,
H2
2d
Reg(n)= Romax (n no) no) 10 00 Rm 2snA Rmax + 8snJ
log
73g
5
and optimizing the right hand side with respect to ng leads to the desired upper bound.
Compared with Hao et al. [8]'s regret bound Ō Ö(Bmaxx' 2 -2 1/3 Algorithm 3 regret bound Ó((maax
) which at least a factor H2 (H is at most O( 0 C -
Cmin smaller. As we will see in Section we show that the regret upper bound provided by Theorem 3 is unimprovable in general, answering an open question of [8].
Improved upper bound with minimum signal condition. Our second new algorithm, Algorithm
similarly uses WARM-POPAA under an additional minimum signal condition.
Assumption 2 (Minimum signal). There exists known lower bound m 0 such that jinjesuup(00)) |8]| m.
At a high level, Algorithm 4 Jsses the first n2 rounds for identifying the support of 0*; the loe recovery guarantee of POPART makes it suitable for this task. Under the minimal signal condition and a large enough n2, it is guaranteed that 0₂ 's support equals exactly the support of ø* After identifying the support of 0", Algorithm 4 treats this as s-dimensional linear bandit problem by discarding
'This is implicit in
18 they assume that 1 and do not keep track of the dependence a.
7

---

the remaining d coordinates of the arm covariates, and perform phase elimination algorithm 23 Section 22.1] therein. The following theorem provides a regret upper bound of Algorithm 4
Algorithm 4 Restricted phase elimination with WARM-POPART
1: Input: time horizon n, finite action set A, minimum signal m, failure rate 6, reward threshold parameter Rmax: an upper bound of max (0", a'il
2: Solve the optimization problem Eq.
5 and denote the solutions as Q and μas respectively. 32s 32>" to H² log 2d)
3: Let R2 max(
256a H
log
2d
4: for fort= = ?2 do
5: Independently pull the arm A, according to μa and receives the reward
6: end for
7: 82 WWRM- WMAR--POAAR((AA)2.. (R.)) Q, Rmax)
8: Identify the support S supp((,,)
9: for t M2 , do
10: Invoke phased elimination algorithm for linear bandits on S
end for
Theorem 4. Algorithm has input time horizon n max( 2
2 (Riaigt +o9) log a²
m²
action set A c [-1, 17 upper bound of the reward Rmax. then with probability at least - 26, the following regret upper bound of the Algorithm [holdss for universal constant C' 00,
2²22H²
2d 2 maxx + HH² log
2d log 5
Reg(n) S max(
Coy lolg((()))))
m
σ²
For sufficiently large n, the second term dominates, and obtain O( regret upper bound. Theorem f provides two major improvements compared to Hao et al. 18 Algorithm 2]. First, when is moderately small (so that the first subterm in the first term dominates), it shortens the length of the exploration phase n2 by factor of Can Second, compared with the regret bound
Ö(
Ammas (2 22 A,2)) /sn) provided by [18] our main regret term Ö( ) more interpretable
Cmin
and can be much lower.
5 Matching lower bound
We show the following theorem that establishes the optimality of Algorithm 3 problem of Hao al. [T8] Remark 4.5] on the optimal order of regret in terms of sparsity and action set geometry in sparse linear bandits.
This solves the open
x//3 (s 1)2) and Theorem 5. For any algorithm, any d, that satisfies d max(n 3/343
8ns² there exists linear bandit environment action set A and s-sparse 0 Rdd such that C-1 S n Rmax $ 2, o and
Reg, 2 2/K 2,3,,
We give an overview of our lower bound proof techniques, and defer the details to Appendix F
Change of measure technique. Generally, researchers prove the lower bound by comparing two instances based on the information theory inequalities, such as Pinsker's inequality, Bregtanolle- Huber inequality. In this proof, we also use two instances and 0', but we use the change of measure technique, help lower bound the probability of events more freely. Specifically, for any event A,
(r(aaa El Per (relat) & Egr A exp ( E(A,0-009)
n
= E Egr
(8)
Symmetrization. We utilize the algorithmic symmetrization technique of Simchowitz et al. 34 Stoltz (37], which makes suffice to focus on proving lower bounds against symmetric algorithms.

---

Definition 2 (Symmetric Algorithm), An algorithm Alg is symmetric if for any permutation π e Sym(d). R. {ar] AA,
Po.Aig [A "n,"",,n o,)) (i) (A1 (.. x(an))
where for vector v, T()) R2 denotes its permuted version that moves 0; to the T(i)-th -th position.
This approach can help us to exploit the symmetry of to lower bound the right hand side of ( below, := {T'= x(0)) = ) is the set of permutations that keep 0' invariant, and A is an event invariant under II:
Bar
I Axxp( (A)
Ear Axxxp Σ E (T ((r)),00)
which helps us use combinatorial tools over the actions for the lower bound proof.
6 Experimental results
We evaluate the empirical performance POPART and our proposed experimental design, along with its impact sparse linear bandits. One can check our code from here: htttss://githnn com/
jajajange
Case 1
Case 2
+=19.49, 110mi==1599.21 21
1/Cmin
PopART
0.-
PopART
1, esstmaation errors
Cmin-Lasso
Cmin-Lasso
H2-Lasso
estimatioon
1.0
0.-
02-
0.
2000
(200
8000
10000
Time
Time
1Xmmin11669
100000
PopART
5000
PopART Cmin-Lasso
250000
Cmin-Lasso
Cumulative
Cumulaatvve
200050
50000
32
Time Horizon (x110))
25
20
25
30
2000
Time Horizon
.000
5000
8000
30000
Figure Experiment results l estimation error cumulative regret.
For sparse linear regression and experimental design, we compare our algorithm POPART with being the solution of (5) with two basclines. The first baseline denoted by Cmin-Lasso is the method proposed by Hao et al. [18) that uses Lasso with sampling distribution defined by (6). The second baseline -Lsso, uses Lasso with sampling distribution j defined by (5), which is meant to observe if Lasso compared with Lasso as an estimator since they are given the same data. Of course, this experimental intention is to
perform better with our experimental design and to how POPART is
design is favored towards POPART as have optimized the design for it, observe if there ever exists a case where POPART works better than Lasso.
For sparse linear bandits,
variant of our Algorithm that uses MARM-POPARE in place of POPART for simplicity. As baseline, we use ESTC [8] For both methods, we use the exploration length prescribed by theory. We consider two cases:

---

Case 1: Hard instance where H? < Cmin. We use the action set constructed in Appendix D.1
where H and Cmin shows gap of (d). We choose = 10, 8 2, a = 0.1.
Case 2. General unit vectors. In this case, we choose d = 30, s 2, o 0.1 and the action set A consists of [A| = 3d = 90 uniformly random vectors on the unit sphere.
We run each method 30 times and report the average and standard deviation of the & estimation error and the cumulative regret in Figure []
Observation. As we expected from the theoretical analysis, our estimator and bandit algorithm outperform the baselines. In terms of the & error, for both cases, see that POPART converges much faster than -Laso for large enough n. Interestingly, - also improves by just using the design computed for POPART case At the same time, 1/2-Lasso is inferior than POPART even if they are given the same data points. While the design was optimized for POPART and POPART has the benefit of using the population covariance, which is unfair, is still interesting to observe significant gap between POPART and Lasso. For sparse linear bandit experiments, while ESTC requires exploration time almost the total length of the time horizon, ours requires significantly shorter exploration phase in both cases and thus suffers much lower regret.
7 Conclusion
We have proposed novel estimator POPART and experimental design for high-dimensional linear regression. POPART has not only enabled accurate estimation with computational efficiency but also led improved sparse linear bandit algorithms. Furthermore, we have closed the gap between the lower and upper regret bound on an important family of instances in the data-poor regime.
Our work opens up numerous future directions. For POPART, we speculate that (Q) is the statistical limit for testing whether 0, or not - it would be a valuable investigation to prove disprove this. We believe this will also help investigate whether the dependence H? in regret upper bound is unimprovable (note our matching lower bound is only for particular family of instances). Furthermore, it would be interesting to investigate whether relying on the population covariance; e.g., use estimated covariance from an extra set of unlabeled data or find ways use the empirical covariance directly. For sparse linear bandits, it would be interesting to develop an algorithm that achieves the data-poor regime optimal regret and data-rich regime optimal regret v sdn simultaneously. Furthermore, it would be interesting to extend our result changing arm set, which poses a great challenge in planning.
POPART without
Acknowledgments and Disclosure of Funding
We thank Ning Hao for helpful discussions on theoretical guarantees of Lasso. Kwang- Swang-Sung Jun is supported by Data Science Academy and Research Innovation & Impact at University of Arizona.
References
[1] Y. Abbasi-Yadkonf D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Y. Abbasi-Yaade Yadkori, D. Pal, and C. Szepesvari. Application to Sparse Stochastic Bandits. In Proceedings of the International Conference Artificial Intelligence and Statistics (AISTATS), 2012.
Set Conversions and
[3] N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts. In Proceedings of the International Conference on Machine Learning (ICML), pages 3-11, 1999.
[4] Auer and M. Long. Using Confidence Bounds for Exploitation-EExplrraion Trade-offs. Journal of Machine Learning Research, 3:2002, 2002.
[5] H. Bastani and M. Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-294, 2020.
[6] Buhlmann and van de Geer. Statistics for High- Dimensinmmns Data: Methods, Theory and Applications. Springer Publishing Company, Incorporated, 1st edition, 2011. ISBN 3642201911.
10

---

[7] R. Camilleri, K. Jamieson, and J. Sattz-S High- diteemmmmiinall experimental design and kernel bandits. In International Conference on Machine Learning, pages 1227-1237. PMLR, 2021.
[8] A. Carpentier and R. Munos. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In Artificial Intelligence and Statistics, pages 190-198. PMLR, 2012.
[9] O. Catoni. Challenging the empirical mean and empirical variance: a deviation study. In Annales de I'IHP Probabilités et statistiques, volume 48, pages 1188-1885, 2012.
[10] V. Chernozhukov. M. Demirer, G. Lewis. and V. Syrgkamis. Semi cemimparametric efficient policy learning with continuous actions. Advances in Neural Information Processing Systems, 32. 2019.
[11] V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic Linear Optimization under Bandit Feedback. In Proceedings of the Conference on Learning Theory (COLT), pages 355-366, 2008
[12] M. Dudík, J. Langford, and L. Li. Doubly robust policy evaluation and learning. In ICML, 2011.
[13] H. Eftekhari, M. Banerjee, and Y. Ritov, Design of c-optimal experiments for high dimensional linear models. arXiv preprint wrXiv:2010.12580 2020.
[14] V. V. Fedorov. Theory of optimal experiments. Elsevier, 2013.
[15] T. Fiez, I.. Jain, K. G. Jamieson, and L.. Ratliff. Sequential experimental design for transductive linear bandits. Advances in neural information processing systems, 32, 2019.
[16] D. P. Foster and E. I. George. The risk inflation criterion for multiple regression. The Annals of Statistics, 22(4): 1947-1975 1994.
[17] A. Gilbert and P. Indyk. Sparse recovery using sparse matrices. Proceedings of the IEEE, 98(6): 937-947, 2010.
[18] B. Hao, T. Lattimore, and M. Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753-10763 2020.
[19] T. Hastie, R. Tibshirani, and M. Wainwright. Statistical learning with sparsity. Monographs on statistics and applied probability, 143:143, 2015.
[20] Y. Huang, X. Kong, and M. Ai. Optimal designs in sparse linear models. Metrika, 83(2): 255-273, 2020.
[21] A. Javanmard and A. Montanari. Confidence intervals and hypothesis testing for high- dimensional regression. The Journal of Machine Learning Research, 15(1):2869-29)) 2909, 2014.
[22] G.-S. Kim and M. C. Paik. Coubly-Robuss Lasso Bandit. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[23] T. Lattimore and C. Szepesvári. Bandit Algorithms. 2018. URL http://dommloade tor wwt.:/ooor....oooooooooooooooo.. pdf
[24] T. Lattimore, K. Crammer, and C. Szepesvári. Linear multi-resource allocation with semi-bandit feedback. Advances in Neural Information Processing Systems, 28, 2015.
[25] L. Li, W. Chu, Langford, and R. E. Schapire. Contextual-Bandi Approach to Personalized News Article Recommendationn. Proceedings of the International Conference World Wide Web (WWW), pages 661-670, 2010.
[26] Liao, P. Klasnja, A. Tewari, and S. A. Murphy. Sample size calculations for micro-randomized trials in mhealth. Statistics in medicine, 35(12):1944-977) 2016.
[27] G. Lugosi and S. Mendelson. Mean estimation and regression under htave- distributions: survey, Foundations of Computational Mathematics, 1955:11445-1199 2019.
[28] B. Mason, R. Camilleri, S. Mukherjee, K. Jamieson, R. Nowak, and I.. Jain. Nearly optimal algorithms for level set estimation. arXiv preprint 211 2021.
11

---

[29] M.-h. Oh, G. Iyengar, and A. Zeevi. pparsity-agnosti lasso bandit. In International Conference on Machine Learning, pages 8271-8256 PMLR, 2021.
[30] S. Ramaswamy, P. Tamayo, R. Rifkin, S. Mukherjee, C.-H. Yeang, M. Angelo, C. Ladd, M. Reich, E. Latulippe, J. P. Mesirov, et al. Multiclass cancer diagnosis using tumor gene expression signatures. Proceedings of the National Academy of Sciences, (8926):5514915111 2001.
[31] S. N. Ravi, V. Ithapu, S. Johnson, and V. Singh. Experimental design on a budget for sparse linear models and applications. In International Conference on Machine Learning, pages 583-592. PMLR, 2016.
[32] H. Robbins. A remark on stirling's ' formula. The American mathematical monthly, 62(1):26-29, 1955.
[33] M. Rudelson and S. Zhou. Reconstruction from anisotropic random measurements. In Confer- ence on Learning Theory, pages 10-1. JMLR Workshop and Conference Proceedings, 2012.
[34] M. Simchowitz, K. Jamieson, and B. Recht. The simulator: Understanding adaptive sampling in the moderate-confidence regime. In Conference Learning Theory, pages 1794 1834. PMLR, 2017.
[35] V. Sivakumar, Wu, and A. Banerjee. Structured linear contextual bandits: A sharp and geometric smoothed analysis. In International Conference on Machine Learning, pages 9026- 9035. PMLR, 2020.
[36] M. Soare, A. Lazaric, and R. Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
[37] G. Stoltz, S. Bubeck, and R. Munos. Pure exploration in finitely-armed and continuous- armed bandits. Theoretical Computer Science, 4 113(11)11332-1882 apr 2011. URL https //hal- archives wwwp:esowvvttttt..e.eeee.ee ftaeeesfff/aa100000000000
[38] C. Tao, S. Blanco, and Y. Zhou. Best arm identification in linear bandits with linear dimension dependency. In International Conference on Machine Learning, pages 4877-4886, PMLR, 2018.
[39] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series (Methodological), 58(1):267-288, 1996.
[40] S. A. van de Geer. On tight bounds for the lasso. J. Mach. Learn. Res., 19:46:1-46:48, 2018.
[41] M. Woodroofe. A one-armed bandit problem with concomitant variable. Journal of the American Statistical Association, 74(368):799-806 1979.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], or [N/A] . You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section 6
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
12

---

(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] We not aware of any negative impacts.
(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 ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental 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 (e.g.. with respect to the random seed after rumning experiments 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, or cloud provider)? [No] But it was run on 5-year-old laptop and no sigmificant computation was required.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) your work uses existing assets, did you cite the creators? [No]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [No]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [No]
13


Reviews:
[{"review_id": "pQAhh0KTwKv", "reviewer": "Reviewer_7Qj2", "summary": "This paper revisited the analysis of the sparse regression and the sparse linear bandit problem. \nFirstly, they presented the improved linear regression algorithm POPART by combining the idea of Catoni's estimator and the thresholding.\nThen, they showed that using POPART, a simple explore then commit type algorithm improves the regret bound of Hao et al in the data-poor regime.\nThirdly, they showed that by using the POPART for the support estimate and running a linear bandit algorithm, they presented an improved regret upper bound for the data-rich regime.\nMoreover, a tighter lower bound for the data-poor regime is presented.\n", "questions": "\n\n### general questions\n\n(Although the same is true of Hao et al.) the action set has to span the entire high dimension so the requirement for the action set can be a bit strict for the high dimensional setting.\nThe compatibility constant is, in this sense, a much weaker assumption as it does not require the lower bound on the minimum eigenvalue. \nIn the results, the lower bound condition in Hao et al is removed but the terms with the diagonal components of Q are used. Does this mean that the lower bound on the eigenvalue condition can be eliminated? Or do you still need to assume that the action set has to span R^d? My impression was the algorithm utilized the idea of Hao et al, but thanks to the improvement with POPART, the requirement on the action set can be further relaxed.\n\n\n ### minor, typo\nline 53, which can is\n\nI think subgaussian random variable should have zero-mean and no need to state \"zero-mean \\sigma-subgaussian\".\n\n\nEq. (3) I think \\lambda is not defined so far.\n\nAlgorithm 2, Samples are indexed until n, but should be n_0.\n\nAlgorithms 1-4,  \\sigma is also an input.\n\nAlgorithm 4, the phased elimination algorithm is not defined in the main paper. Should cite reference or write pointers.\n\nEq. (6) I think \\lambda_min is not defined. \n\nline 228 and and\n\n \n\n\n", "limitations": "See Questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution of this paper is in its theoretical aspect.\nNovel algorithm/analysis of the linear regression and it's consequence is significant.\nTheir guarantee has tighter dependence than the classical Lasso guarantee by focusing on the different quantities (especially Q^{-1}_{ii}). \n\nWith the help of the novel offline regression analysis, the regret bounds for the sparse linear bandit literature are further improved. For the bandit upper bound part, the algorithmic part may not be so novel but the resulting tighter analysis is significant.\nThey further presented a tighter lower bound for the data-poor regime with the novel application of the change of measure technique with the symmetrization approach, this technique is noteworthy.\n\nAlthough there may be some parts of the paper that can be improved, I think the paper is worth accepted for Neurips.\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": "dGo1AfQc-ew", "reviewer": "Reviewer_ToPD", "summary": "The authors consider the sparse linear regression problem with an application to experimental design in linear bandits. They propose a new sparse linear estimator of the true model based on Catoni's estimator assuming the knowledge of the population covariance.\nThe authors bound the error of the proposed estimator in terms of the spectral properties of the covariance matrix. They also propose a warm start estimator and improve the error bound further. Using the error bound of this estimator, the authors then propose a criterion for designing sampling distribution in the linear bandits problem. Using this sampling distribution, they propose an explore-then-commit algorithm for experimental design in linear bandits. The authors then bound the regret of this strategy and further provides a matching lower bound. Finally, under an additional assumption on the minimum signal of the unknown model, they design a phase-based algorithm using the estimator and provide its regret bound.", "questions": "It would be great if a discussion on implementation of the convex optimization problem is presented.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The authors provide a novel estimator for sparse linear regression and prove a tighter error bound for it compared to well-known Lasso estimator.\n\n2. The tighter error bound for the estimator also leads to a tighter regret bound for linear bandits.\n\n3. They also improve the lower bound for experimental design in linear bandits compared to prior work and establish that it is near to minimax optimal.\n\n4. The results are well-positioned compared to the existing work and the paper is well-written.\n\nWeakness:\n\nThe bandit algorithm for experimental design needs to solve an optimization problem to find the sampling distribution. I find the implementation details and complexity of that procedure missing from the paper.", "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": "9q_S2Q6hjZ", "reviewer": "Reviewer_Vvdf", "summary": "The paper studies multi-armed linear bandits in high dimensions under sparsity\nassumptions. This problem has been studied before (notably by Hao et al '20), but the\npaper presents newer (tighter) upper and lower bounds. Key to the algorithm is a novel\nestimator for sparse linear regression which allows us to design a sampling distribution\nso as to minimize the estimation error. While a s^(2/3) T^(2/3) regret (where s is the\nsparsity and T is the time horizon) seems unavoidable in general, the authors show that\n\\sqrt{sT} rate is possible with a modified version of the algorithm if there is enough\nsignal from the non-zero coefficients. Finally the authors present some simple\nsimulations to corroborate their experimental results.\n\nWhile the results are not earth-shattering, the paper makes solid progress on a\nwell-established and useful problem. While I didn't have the time to read the proofs in\ndetail (hence the lower confidence score), the results appear believable and the\nintuitions are presented clearly. Hence, I would like to see this paper accepted.\n", "questions": "See above.", "limitations": "See above.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I don't have any major comments/criticisms about the paper. But here are some suggestions\nwhich might help improve the presentation.\n1. There were too many in-line equations, and generally, the presentation was somewhat\nequation-driven. While I appreciate that this may be unavoidable for a paper such as this,\nI felt that the authors could have done a better job of making the material easier to\nread.\n2. Please try and use words to describe symbols/notation when they are being introduced\n(e.g: Explain what R0 is in assumption 1 ).\n3. Maybe introduce the compatibility condition (equation 2) closer to the discussion\naround Theorem 2. Right now, it doesn't directly relate to the results in the paper and I\nwas left confused as to what it's purpose was.\n4. Instead of using large equations in the algorithm (e.g. line 6), consider defining the\nquantities in the text and referring to them in the algorithm pseudo-code.\n5. Please explain why knowledge of the signal strenght is necessary for an algorithm to\nachieve \\sqrt{T} regret around Theorem 4.", "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