Maximizing and Satisficing in Multi-armed Bandits with Graph Information
Authors: Parth Kashyap Thaker
Mohit Malu
Nikhil Rao
Gautam Dasarathy
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-armed Bandits
Pure Exploration
Graph Smoothness
Best Arm Identification
Sample Complexity

Abstract: Pure exploration in multi-armed bandits has emerged as an important framework for modeling decision making and search under uncertainty. In modern applications however, one is often faced with a tremendously large number of options and even obtaining one observation per option may be too costly rendering traditional pure exploration algorithms ineffective. Fortunately, one often has access to similarity relationships amongst the options that can be leveraged. In this paper, we consider the pure exploration problem in stochastic multi-armed bandits where the similarities between the arms is captured by a graph and the rewards may be represented as a smooth signal on this graph. In particular, we consider the problem of finding the arm with the maximum reward (i.e., the maximizing problem) or one that has sufficiently high reward (i.e., the satisficing problem) under this model. We propose novel algorithms GRUB (GRaph based UcB) and zeta-GRUB for these problems and provide theoretical characterization of their performance which specifically elicits the benefit of the graph side information. We also prove a lower bound on the data requirement that shows a large class of problems where these algorithms are near-optimal. We complement our theory with experimental results that show the benefit of capitalizing on such side information.

Maximizing and Satisficing in Multi-armed Bandits with Graph Information"
Parth K. Thaker Arizona State University pkthaker@asu. edu
Mohit Malu Arizona State University mmalu@an asu. edu
Nikhil Rao Microsoft
Gautam Dasarathy
Arizona State University gautamdBasu. edu
nikhilrao8 68 gmail com
Abstract
Pure exploration in multi- bandits has emerged as an important framework for modeling decision making and search under uncertainty. In modern applications however, one is often faced with a tremendously large number of options and even obtaining one observation per option may be too costly rendering traditional pure exploration algorithms ineffective. Fortunately, one often has access to similarity relationships amongst the options that can be leveraged. In this paper, we consider the pure exploration problem in stochastic multi-armed bandits where the similarities between the arms is captured by a graph and the rewards may be represented as smooth signal on this graph. In particular, we consider the problem of finding the arm with the maximum reward (i.e., the maximizing problem) or one that has sufficiently high reward (i.e.. the satisficing problem) under this model. We propose novel algorithms GRUB (GRaph based UcB) and (-GRUB for these problems and provide theoretical characterization of their performance which specifically elicits the benefit of the graph side information. We also prove lower bound on the data requirement that shows large class of problems where these algorithms are near-optimal. We complement our theory with experimental results that show the benefit of capitalizing on such side information.
Introduction
The multi-armed bandit has emerged as an important paradigm for modeling sequential decision making and learning under uncertainty. Practical applications include design policies for sequential experiments [44], combinatorial online leaning tasks [9], collaborative learning on social media networks [30, 4]. latency reduction in cloud systems [23] and many others [8, 59, 50, 24]. In the traditional multi-armed bandit problem, the goal of the agent is to sequentially choose among a set of actions arms to maximize desired performance criterion
reward. This objective demands a delicate tradeoff between exploration (of new arms) and exploitation (of promising arms) An important variant of the reward maximization problem is the identification of arms with the highest (or near-highest) expected reward. This best arm identification [41, 13] problem, which is one of pure exploration, has wide range of important applications like identifying and testing drugs to treat infectious diseases like COVID-19, finding relevant users to run targeted ad campaigns, hyperparameter optimization in neural networks and recommendation systems. The broad range of
"This work was supported in part by the National Seience Foundation through the awards 2CF-2048223, CNS-2003111, CCF-2029044, and Center
This work also supported partly by the ASU SenSIP
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

applications of this paradigm is unsurprising given its ability to essentially model any optimization problem of black-box functions on discrete (or discretizable) domains with noisy observations.
While pure exploration problems in bandits show considerable promise, there are significant hurdles to their practical usage. In modern applications, one is often faced with tremendously large number of options (sometimes in the order of hundreds of millions) that need to be considered for decision making. In such cases, playing (i.e., obtaining a random sample from) each bandit arm even once could be intractable. This renders traditional approaches to pure exploration ineffective. Fortunately, in several applications, the arms and their rewards are related to each other and information about the reward of one arm may be deduced from plays of similar arms, In this paper, we consider the pure exploration problem in stochastic multi-armes bandits where the similarities between arms is captured by a graph and the rewards may be represented as a smooth signal on this graph. Such graph side information is available in a wide range of applications: search and recommendation systems have graphs that capture similarities between items [17, 43, 53, 11]; drugs, molecules and their interactions can be represented on a graph [19]; targeted advertising considers users connected to each other in social network [20], and hyperparameters for training neural network are often inter-related [57]. It is worth noting that such graphs are sometimes intrinsic to the problem (e.g., spatial coordinates or social/computer networks), or may be inferred based on a similarity metrics defined on arm features; a recent line of work considers constructing such graphs to enable more effective learning [see e.g., 58, 31].
Our Contributions: We consider the pure exploration in multi-arm bandits problem when a graph that captures similarities between the arms is available. In particular, we consider the problem of finding the arm with the maximum reward (i.e., the maximizing problem) or one that has sufficiently high reward (i.e., the satisficing problem²) under the assumption that arm rewards are smooth with respect to a known graph. Our main contributions may be summarized as follows:
(a) We devise novel algorithm GRUB for the best arm identification problem (i.e., the maximizing problem) that specifically exploits the homophily (strong connections imply similar average rewards) on the graph (Section 3).
(b) We provide theoretical characterization of the performance of GRUB. To this end, we define a novel measure J that we dub the "inftuence "aattrrn which depends on the resistance distance of the underlying graph. This measure captures the benefit of the graph side information and plays a central role in the analysis of GRUB. In the traditional (graph-free) best arm identification problem, the sample complexity know to scale as Σ A? where A; is the gap between the expected rewards of the best arm and arm i. On the other hand, we show that GRUB roughly has complexity that scales like Σien x? samples where the set H a set dependent on the influence factor, which contains
arms which are hard to distinguish from optimal arm. For broad range of problems [7|] < n, yielding significant improvement over traditional best arm identification algorithms (Section 4). (c) In Section 5, we provide lower bounds the minimum number of samples required for iden- tification of the optimal arm when a graph encoding arm similarities is available. This shows the near-optimality of GRUB for an important class of representative problems.
(d) many real world scenarios, the aim of finding the absolute best arm can often be too costly or even intractable. In these situations, it may be more appropriate to solve the satisficing problem, where the algorithm returns an arm that is good enough. We propose a variant of GRUB, dubbed <-GRUB for this important setting in Section 6
(e) Finally, in Section 7, we complement our theoretical results with an empirical evaluation of our algorithms. We further provide algorithmic improvements to GRUB and discuss novel sampling policies for best arm identification in the presence of graph information.
1.1 Related Work
The textbook [32] is an excellent resource for the general problem of multi-armed bandits. The pure exploration variant of the bandit problem more recent, and has also received considcrable attention in the literature [6. 7, 15, 14, 4, 21J. These lines of work treat the bandit arms or actions as independent entities and playing a particular arm yields no information about any other arm. This leads to great difficulty in scaling such methods, since in the problem setups with large number of
named after Herbert Simon's celebrated alternative model of decision making [48]

---

arms, attempting to play all arms is not practical. We resolve this precise roadblock by introducing a convenient way of of appending graph side information into the mix which provably accelerates the process of sub-optimal arm elimination (potentially without playing it even once!)
A recent line of work [35, 32, 18, 56, 16, 39] has proposed the leveraging of structural side- information for the multi-armed bandit problem for regret minimization. Such ropology-basee bandit methods work under the assumption that pulling an arm reveals information about other, correlated arms [18, 47], which help in developing better regret methods. Similarly, spectral bandits [29, 56, 51] assume user features are modelled as signals defined on an underlying graph, and use this to assist in learning. The works [3] and [54] consider similar graph information models, albiet at a degraded level. The authors in [33] use the graphs to improve the regret bounds in a thresholding bandit setting. Work revolving around spectral bandits utilize the spectrum of the graph laplacian. In contrast, we focus on the combinatorial properties of the graphs to devise algorithms and analyse them. Another line of work [12, 52, 36, 37] considers search problems on graphs under different model and there an opportunity for future work to combine these techniques.
Most of the aforementioned works focus on regret minimization in the presence of graph information. The problem of pure exploration with similarity graphs has received far less attention. The authors in [29] were the first to attempt at filling this gap for the spectral bandit setting. They provide an coormatioo-thhorede
lower bound and a gradient-basee algorithm to estimate this lower bound to sample the arms. The authors provide performance guarantees for the algorithm, but these results only indirectly capture the benefit brought by the graph; our results on the other hand are based on a novel complexity measure that explicitly elicits the benefit of having the graph side information.
Note that, similarity graph information considered in this work is fundamentally different from linear rewards assumption in contextual/linear bandits. In the linear bandits problem, the reward behavior is assumed to be low dimensional and this is crucial for the improved regret bounds and sample complexity guarantees [32, 49]. In the current work we do not make any assumptions on low dimensionality of the rewards but still show improvements in sample complexity provided good arm-simille mim-iiiilaryty graph is available. We show a toy example in Appendix H where low dimensional linear bandit cannot be competitive with the corresponding graph- bandit setting.
2 Problem Setup and Notation
We consider an n-armed bandit problem with the set of arms given by [n] 2 (1,2, ....,....,,.)) n). Each
arm i E [n] is associated with --suubGauusiin distribution v4. That is, Ex [exp (s(X - -xa))] <
exp
Vs E R, where 14, = EF: [X] is said to be the (expected or mean) reward associated to
arm i. We will let μ RR denote the vector of all the arm rewards. A "play" of an arm i is simply an observation of an independent sample from 14; this can be thought of as a noisy observation of the corresponding mean μ4. The goal of the best-arm identification problem is to identify, from such noisy samples, the arm a" - arg max M4 that has the maximum expected reward, denoted by μ²" For each arm i E [m). we will let A; _ nr" fa denote the sub-optimality of the arm.
As discussed in Section 1, our goal is consider the best-arm identification where one has additional access to information about the similarity of the arms under consideration. In particular, we model this side information weighted undirected graph G (Vg, ÉG, Aa) where the vertex set, VG [n]]
identified with the set of arms, the edge set EG S (In)), and adjacency matrix Ag R describes the weights of the edges E between the arms which captures the similarity in means of connected arms; the higher the weight, the more similar the rewards from the corresponding arms. We will let T.G Da Ag denote the combinatorial Laplacian of the graph [10], where DG = diag(AG AG x 1,, is a diagonal matrix containing the weighted degrees of the vertices. We will suppress the dependence on G when the context is clear. Subsequently, we show that if one has access to this graph and the vector of rewards j is smooth with respect to the graph (that is, highly similar arms have highly similar rewards), then one can solve the pure exploration problem extremely efficiently. We will capture the degree of smoothness of μ with respect to the graph using
3 All our results continue to hold if this is replaced with the normalized, random walk, or generalized Laplacian.
3

---

the following seminorm":
lllll a LOHL
E (ii)
Aij(u-- kz)?
(I)
The second equality above can be verified by a straightforward calculation. Also, notice that || being small implies b4; = M4 for (i. E. In such scenario we say that the mean vector is smooth over graph G. This observation has inspired the use of the Laplacian in several lines of work to enforce smoothness the vertex-valued functions [2, 51, 60, 33]. For 0, we say that arms (rewards) are e-smooth with respect to a graph G if || la S e.
Let C(G) C 2 denote the set of all connected components and let kGG) & |C(G) denote the number of connected components of the graph G. For vertex i [n], we will let CG C(G) denote the connected component that contains i. When the context is clear we sometimes let Ci also refer all the nodes in the connected component. We say a graph G ([n], E) has k-isolated cliques if can be divided into fully connected sub sub-graphs G; (V,, E,) such that Vú S [n], E, = (%) for all i E [k.], V3 V = 0, E, n Fg- = ( for all j E is fully connected.
[k], and U V [m]] U E. = E. Notice that
we only have one clique
To solve the best-arm identification problem, we need a sampling policy to sequentially and interac- tively select the next arm to play, and stopping criterion. For any time E the sampling policy bage is a function that maps t to an arm in [n] given the history of observations up to time t 1. With slight abuse of notation, we will let मe denote the arm chosen by an agent time t. Let tt.m. denote the random reward observed at time t from arm Te. We use t. (TT)) (referred as i; for simplicity) to denote the number of times arm played under the sampling policy Te In this paper we tackle the following problems:
T; -fr,,.st
P1 (Best arm identification): Given v arms and an arbitrary graph G capturing similarity between the arms, can we design a policy TT that exploits the similarity to find the best arm efficiently?
P2 (Ç-best arm identification): Under the setting in PL, can we design a similarity exploiting policy T so as to find an arm belonging to the set B()) & {i E [n]] : 114 - pa S {} efficiently?
3 The GRUB Algorithm
We now introduce GRUB (GRaph based Upper Confidence Bound), novel but natural algorithm for best arm identification in the presence of graph side information. We begin with an intuitive description of how GRUB incorporates the graph side information into an upper confidence bound (UCB) strategy. Most UCB algorithms [32, 51] compute the estimates of mean and variance, and use these climinate arms that have been deduced be sub-optima. The key idea behind GRUB is that the arm similarity information allows to create high-quality estimates of mean rewards and confidence intervals for arms that have not been (sufficiently) sampled yet. In what follows, we describe the building blocks of GRUB.
3.1 Leveraging Graph Side Information
We introduce two key ideas that lie at the heart of the GRUB algorithm. First, at each step, GRUB computes a regularized estimate of the means of all the arms; the regularization based on the graph Laplacian essentially promotes the smoothness of the mean vector on the given graph. This allows the algorithm to estimate means of arms it has never sampled. To do this, at any given time step T, squares optimization program:
the algorithm solves the following
ju.
arg min HER
Σ (rem Mmx)² + plue, Lawi
(2)
'Lo is not positive definite, and can be verified to have as many zero eigenvalues as the number of connected components in G

---

where p > O is a tunable parameter. Equation (2) admits closed form solution of the form
T
T
Pr
Σ
C.. on. + pLG
Σ
Cz. Tt,m
provided the matrix VT 2 2i-=1 ex,, TT. + pLg is invertible; e, denotes the i-th standard basis vector for the Euclidean space R". In Appendix B we show that invertibility holds if and only if the sampling policy yields least one sample per connected component of G. This is a rather mild condition that we arrange for explicitly in our algorithm, given that we know the graph G. In what follows we assume that every connected component of graph G is sampled at least once. This regularized mean estimation procedure yields an estimate of the mean that is both in agreement with observations and smooth on the graph thereby allowing information sharing among similar arms.
The second key idea of our algorithm is the utilization of the graph G in tracking the confidence bounds of all the arms simultaneously, Intuitively, for identifying the best arm, we must be reasonably certain about the sub-optimality of the other arms. This in turn would require the algorithm to track high-probabilltty confidence bound on the means of all the arms. In the traditional (graph-free) best arm identification problem, the confidence interval of an arm's 's mean estimate depends on the number of times the arm has been played. Requiring multiple plays of all suboptimal arms for obtaining high confidence bounds is potentially disastrous when the number of arms is very large. In our setup, we show that the knowledge of the similarity graph greatly improves this situation. In particular, we show that play of any arm not only tightens its own confidence interval, but also has an impact on the confidence intervals of all connected arms. To quantify the benefit of graph information for the confidence bounds, we will define a novel quantity for each arm the effective number of plays.
Definition 3.1 (Effective Number of Plays). Let p > O and (4 }=> denote the number of plays of each of the arms when a sampling policy TT employed for T time steps. Suppose that for each connected component C E C(G), there is at least one arm ic E C such that tic > 0. Then the pLG)) -1 where Nr i
effective number of plays for each arm E [n]] is defined lett, _ [[NT + pLa)
a diagonal matrix of [1 and LG denotes the Laplacian of the given graph G.
Effective number of plays feft.; for any arm i is influenced by two factors: (a) the number of samples of arm i itself, and (b) the number of samples of any arm the connected component j E C(t.. j + i. It can be shown that for any arm i, fears depends on the number of connections of node i in graph G and its value increases as the connectivity of the node increases. The choice of the terminology for this quantity is justified by the following lemma. which provides a high confidence bound for the mean estimate of each arm
Lemma 3.2 (Concentration inequality). For any T k(G),, the following holds with probability at least 1 - 8:
1 V Leggs
(wx(TT)
104 - uul S
201
14
+ pllealla)
Vi e [x]]
(3)
where w. (x(T)) = agntt eff for any constant ag > O, pup is the i-th coordinate of the estimate from (2)
Notice that the effective number of plays has similar role as the number of plays in traditional pure exploration algorithms [13]. Indeed, in the absence of graph information, laft.s reduces to L; the total number of plays of individual arms. Lemma 3.2 recovers high confidence bounds for standard best-arm identification problem [13]. It should be noted that while our work is the first to identify this interpretable quantity explicitly, the result of Lemma 3.2 in other forms has appeared before in the literature [1. 51, 56].
We introduce our algorithm GRUB for best arm identification when the arms can be approximately cast as nodes on a graph. GRUB uses insights from graph-based mean estimation (2) and upper confidence bound estimation (3) for its elimination policies to search for the optimal arm.
GRUB accepts as input a graph G on n arms (and its Laplacian Lg), a regularization parameter P > 0, smoothness parameter > 0, and an emror tolerance parameter 8 (0, 1). It is composed of the following major blocks.
Initialization: First, GRUB identifies the clusters in the G using Cluster- Celluster-ddentee ificaiion
5

---

routine. Any algorithm that can efficiently partition graph can be used here, e.g METIS [25]. GRUB then samples one arm from each cluster. This ensures V > 0, which enables GRUB to estimate pr using the closed form solution of eq. (2). A great advantage of GRUB is that the initialization phase only requires steps equal to the number of disconnected components in the graph. This is in direct contrast with traditional best arm identification algorithms, which require atleast one sample from every arm initially.
Sampling policy: At each round, GRUB obtains a sample from the arm returned by the routine Sampling ing Policy, which cyclically samples arms from different clusters while ensuring that no arm is resampled before all arms in consideration have the same number of samples. This is distinct from standard cyclic sampling policies that is traditionally used for best arm identification [13], but any of them may be modified readily provide a cluster-aware sampling policy for GRUB. In our experiments, we show that replacing cyclic sampling with more statistics- and structure-aware sampling greatly improves performance; theoretical analysis of these is promising avenue for future work. One of the major advantage of GRUB is the lite nature of the computation. Every loop just requires rank-1 inverse update which can be performed very efficiently and it does not need any subroutines, unlike [29]
Bad arm climination At any time t, let A be the of all arms in consideration for being optimal. Using the uncertainty bound from (3), GRUB uses the following criteria for sub-optimal arm elimi-
nation. At each iteration, GRUB identifies an arm Omax E A, amax = arg max 1 3:(1) eff
2naotin
where Bi(1)
20 14 log
+ pe with the highest lower bound on its mean esti-
Followoo this, GRUB removes arms from the set A according to the following climination policy,
A A- A fa a E A 10max - ig S Ba(l) Cett.a Bamaax ( Velt amax
Note that GRUB does not require any optimization innerloop as in [29]. This potentially provides GRUB with a significant computation advantage, especially when the dimensionality of the problem is very large. The pseudocode for GRUB can be found in Appendix E.
Next, we derive performance guarantees the sample complexity for GRUB to return the best arm with high probability.
4 Theoretical Analysis of GRUB
In this section we provide formal statement of the sample complexity of GRUB. To do this, first introduce novel quantity we call inftuence from resistance distance, a classical graph theoretic concept. This adds to the interpretability and understanding of the instances where using graph side information might be of tremendous use to the application. The usage of graph through the influence factor allows us to identify arms that can be eliminated quickly from consideration.
The influence factor of an arm is derived
4.1 Resistance Distance and Influence Factor
We first recall the definition of resistance distance in graph.
Definition 4.1 (Resistance Distance). [5] For any graph G with nodes, given constant 5 > 0, the resistance distance (i,)(i.j) between two nodes i, is defined as,
To,a(i,5)
Ra + R5 Rij Rjs:
(5)
where R. A (LG+ (617)117) + denotes the Moore-Penrose inverse, LG is the Laplacian of graph G, and 1 E R" is the vector of all I's.
When the context is clear we denote the resistance distance simply as r.( The terminology comes from circuit theory: Suppose that graph G ([n), E) is thought of as resistor network on the nodes [rx] where each edge {i,j) j) has unit resistance. Then, the effective resistance between two nodes i and j is preciscly the resistance distance r(i.j). It can be shown in general that nodes

---

that are close by or connected by several paths have a small resistance distance. Given its ability to capture closeness of nodes in graph, the resistance distance has found broad range of applications and has been the subject of much study; see e.g., [28, 5, 55J.
Using the notion of resistance distance, define the influence factor J(:,G) of vertex below. This novel measure quantifies the impact of the graph on the parameter estimation of arm j. and in particular, allows us use the combinatorial properties of the graph and the arm means classify arms into two sets: competítive and non-compelitive; the definition of these sets follows right after. As our theory will show, the competitive arms are sampled though we were the traditional graph-free setting; on the other hand, compoeteeeeivee arms are eliminated rapidly, often with zero plays! Indeed, the smoother the reward vector with respect the graph, the fewer competitive arms there are it is this phenomenon that is captured using the influence factor.
Definition 4.2 (Influence Factor), Let G be a graph on the vertex set [n].. For each j E [nx], define influence factor J(j as:
min (C), (ra(i.1)~', if 1C,(a)> 1,
G(,
(6)
0,
otherwise
Here, r)( is the resistance distance between arm i and j in G as in Definition 4.1.
Definition 4.3 (Competitive and Con-Competitive Arms). Fix l E R", graph D, regularization parameter confidence parameter 6, and smoothness parameter We define HD to be the set of competitive arms and ND to the set of non-competitive arms as follows:
2aonp2 D)3 + pc) }
HD. = j Inlla S S2 D)
20 14
(7)
8
and ND & [nd] HDD
As the name suggests, the arms in H are close to the optimal arm a" in mean (competitive compared to the optimal arm a²) and requires several plays before they be discarded, shown in the theorem below. Note from the above definition that an arm more likely to be part of this set its mean is high (i.e., A; is low) and its influence factor is low. Similarly, the non-competitive is composed of arms whose means are not competitive with the optimal arm
Armed with these definitions, we now ready state our main theorem that characterizes the performance of GRUB.
4.2 Sampling policy performance
Cyelic sampling policies have been traditionally used in multi-armes bandit problems for best-arm identification [13]. The sample complexity bound for GRUB with cyclic sampling is as follows:
vector μ E R Let G (V. E) be the similarity graph with the vertex set V = [n] and edge set E, let g be the set of subgraphs of G, and further suppose that P e-smooth i.e., || S e. Define
Theorem 4.4 (GRUB Sample Complexity). Consider n-armed bandit problem with
T Funfficient arg min
DEg
CEC
Σ
Σ iЕCпAAD
AZ
CI log
JA:
C2
+
Pe
2
+
RECrUND
max
2 A
log AA;
2
($1
where 11, all suboptimal arms, HDD and ND are as Definition 4.3, Cp is the set of connected components of given graph D and C1, C2 are constants independent of system parameters. Then, with probability at least - 5, GRUB: (a) terminates in no more than T sufficciet rounds, and (b) returns the best arm a" arg max; μ4:
Remark 4.5, The required number of samples for successful elimination of suboptimal arms, and therefore the successful identification the best arm, can split into two categories based on the sets defined in Definition 4.3. Each sub-optimal highly competitive arm j H requires ( (1/ samples, which is comparable to the classical (graph-free) best-arm identification problem. Additionally, the non-competitive arms A can be climinated without being played, depending the influence factor:
7

---

one round of the cyclic sampling suffices to eliminate these arms (even if they are never played!). We refer the reader Appendix E for more detailed discussion. Indeed, the smaller [H]] is, the more the graph side information benefits GRUBand vice-versa.
Remark 4.6. Note that sufficient in Theorem 4.4 involves the minimum over all subgraphs. As show in Lemma 1.8 the appendix, can actually increase if one restricts their attention to certain subgraphs of G; this in turn increases the size of /V and decreases the size of H. hence, giving tighter upper bound on the performance of the algorithm. GRUB automatically adapts to the best subgraph to maximize the influence factor (.,-)) -) obtain the best possible sample complexity and this is reflected in the statement of Theorem 4.4.
The complete proof of Theorem 4.4 can found in Appendix E, where we also provide more insights on the behavior of the confidence bound as a function of the number of samples acquired. These results may of independent interest to the reader.
Lower Bounds
Let consider n-armed bandit setup with arm indices [1, ni. Let μ² indicate the mean of the optimal arm and μi; indicate the mean values of all other arms such that (4s < j²" For the rest of this section, without loss of generality, let the index of optimal arm be 1.
Theorem 5.1. Given an n-armed bandit model with associated mean vector μ E R" and similarity graph smooth on μ. i.e. (n, Lop) S c, for any only isolated cliques and w.l.o.g let arm be the optimal arm. Then define
< co- Let = ([n], E) be the graph with
4a log
4o log5
Tnecessary
Σ
min
Σ jEC*/1
(8)
JEC
(A, -
A
CECa/C-
min where C" is the clique with the optimal arm and tElml/1.JEC(O
A
1
4
Then
VA any 8-PAC algorithm will need at-least Tncessory steps to terminate, provided S 0.1.
Using Theorem 5.1, certain class of similarity graph G. The following result shows that the upperbound on the sample
show that GRUB is minimax optimal for a n-armed bandit problems for
complexity provided in Theorem 4.4 matches the lower bound established in Theorem 5.1 A up to constant factor.
Corollary 5.2 (Isolated clusters). Consider the setup as in Theorem 5.1 with the further restriction that graph G be such that the optimal node is isolated and c minnje(])
A?
3. Define,
802 log
Tnecestary
Σ
max jEC
A
CECA/ (1)
Then any algorithm that takes fewer than T Tnecessory samples will have probability of error at least 0.1.
As can be seen in Corollary 5.2, the lower bound expression can scale as standard r-armed bandit (implying no added advantage of having graph sideiiforrmatio) or can behave -Cal-armed bandit problem (scales as the number of clusters in graph G rather than number of nodes n) purely by changing the similarity graph G. The difference between Cp (connected components in the subgraph constructed by making optimal arm isolated) and CG (connected components in the given similarity graph) can lead to more interesting behaviour in terms of lower bound expressions on sample complexity.
6 <bestt-rr identification
can observed from Theorem 4.4 that the fact that the means are e-smooth implies that distinguish-
ing arm j from a* would require at least (c--2) samples. A tighter upper bound on the violation and edge between j and a* would make the suboptimal arm j harder to eliminate. However, stands to reason that in such situations, it might be more practical to not demand for the absolute best

---

arm, but rather an arm that is nearly optimal. Indeed, in several modern applications we discuss in Section finding an approximate best arm is tantamount solving the problem. In such cases, simple modification of GRUB can be used to quickly eliminate definitely suboptimal arms, and then output an arm that is guaranteed to nearly optimal. To formalize this, we consider the Ç-hest arm identification problem as follows.
Definition 6.1. For given ( > 0, arm is called Ç-best arm if p4 2 Pa- -. where a' = arg max; (4
The goal of the Ç-best arm identification problem is return arm à that (-optimal. We achieve this by simple modification to GRUB, which we dub Ç- GRUB which ensures that all the remaining arms i satisfy (1,),) V Carl S. It then outputs the best arm amongst those that are remaining. The following theorem characterizes the sample complexity for (-GRUB:
Theorem 6.2. Consider n-armed bandit problem with mean vector ja E IR". Let G be the given similarity graph on vertex set [n), and further suppose that μ is e-smooth. Let be the set of connected components of G. Define,
T sufficient
A arg min
E CECD
Σ
C1 log
C2
Pe
DEg
LiECNHO
(A V)
8(A, V
2
Pe 11
+
max
C1 log 8(A; V
(10)
iECOND
(A
2
where = for all suboptimal arms, Hn and ND are as in Definition 4.3, Cp is the set of connected components of a given graph Dand A; V = max Ai) and C1 02 are constants independent of system parameters. Then, with probability at least - 5 S-GRUB: (a) terminates in no more than T sufficien rounds, and (b) returns Ç-best arm.
The pseudocode for the X-GRUB can be found in Appendix G.
7 Experiments
For all our experiments, we use Intel Core 17-10875H CPU @ 2.30GHz x 16 with 32 GB memory. We set 5 = 1e 3, p 2.0, 2.0. We evaluate GRUB with different sampling strategies from section and compare its performance to standard UCB algorithm on both synthetic and real datasets.
Theorem 4.4 established a baseline w.t.. sampling protocol by solving T Tuffiiient for naive cyclic sampling policy (a sampling policy which does not exploit the graph properties). Note that, even if the sampling policy does not utilize any graph properties, the similarity graph is still being utilized in computing the mean estimate and the confidence widths. For the safe elimination of suboptimal arms, the ultimate goal of GRUB is shrink the confidence bounds Bey/ Bey((etr (teft,)) as quickly as possible. For the complete description of all the alternatives please refer to Appendix J
Better sampling strategies:
Synthetic Data:
We consider an n-armed bandit setup with the aim of finding the best arm. The number of arms scale from n = 50 to 200 in steps 50. We consider 2 cases: G a Stochastic Block MSdel(SBM) with parameters (p.q) 9) = (0.9. 14=4) and G is a Barabási-Allert(B. with parameter m = 2, both containing 10 clusters. We run every setup for 20 runs and record the stopping time for all runs. In Figure 1, compar the baseline cyclic algorithm (Nograph-UCB) with GRUB and its variants (GRUB-MVM, JVM-O, JVM-N), more details on this in Appendix J.
graph
As can be seen in Figure 1, all graph-awan algorithms (GRUB with different sampling policies) outperform the standard UCB based best-arm identification algorithm. Within the different GRUB, different sampling policies exploit the graph infromation in different ways, leading to variations in their performance. GRUB (cyclic sampling based) is outperformed by all other sampling based GRUB methods.
We show additional experiments with different graph parameters for Stochastic block model and Garabási-Albert graphs and different cluster sizes well as real data in Appendix K. The full code used for conducting experiments can be found at the following Github repository. Discussion about limitations, future works and broader impact are provided in Appendix A.

---

Barobdo--Alert.. m-2
Model, p=0.95,, q=5x100
2450
GRUB VMN
GRUB-AWM- GRUD-ANN-N UCB
2300
CRUS
GRUD 104
ReCrepesUC
1750
Snopinng time
1500
2000
730
310
53
120
150
203
Number
Figure 1: (Best seen in color) Performance of GRUB and its variant sampling protocols for SBM (p,.) (0.95, 1)) [Left] and BA (m 2) [Right]. GRUB outperforms the standard cyclic UCB method
References
[1] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In J. Shawe-Taylor,, R. Zemel, P. Bartlett, F. Pereira, and K. Q- Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] Rie Kubota Ando and Tong Zhang. Learning on graph with laplacian regularization. Advances in neural information processing systems, 19:25, 2007.
[3] Alexia Atsidakou, Orestis Papadigenopoulos, Constantine Caramanis, Sujay Sanghavi, and Sanjay Shakkottai. Asymptotically-optnnn Kamalika Chaudhuri. Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 1057-1077. PMLR, 17-23 Jul 2022.
Gaussian bandits with side observations. In
[4] lean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pages 41-53, 2010.
[5] Ravindra B Bapat and Somit Gupta. Resistance distance wheels and fans. Indian Journal of Pure and Applied Mathematics, 41(1):1-13, 2010.
[6] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[7] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in finitely-armar and continuous-armen bandits. Theoretical Computer Science, (12(11):1832-188 2011.
[8] Wei Cao, Jian Li, Yufei Tao, and Zhize Li. On top-k selection in multi-armed bandits and hidden bipartite graphs. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[9] Shouyuan Chen, Tian Lin, Irwin King, Michael Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. In NIPS, pages 379-387, 2014.
[10] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
[11] G Dasarathy, N Rao, and R Baraniuk. On computational and statistical tradeoffs in matrix completion with graph information. In Signal Processing with Adaptive Sparse Structured Representations Workshop SPARS, 2017.
[12] Gautam Dasarathy, Robert Nowak, and Xiaojin Zhu. S2: An efficient graph based active learning algorithm with application to nonparametrie classification. Conference on Learning Theory, pages 503-522. PMLR, 2015.
10

---

[13] Eyal Even- Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi- armed bandit and reinforcement learning problems. Journal of muchine learning research, 7(6). 2006.
[14] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach fixed budget and fixed confidence. NiPntt Sixth Annual Conference on Neural Information Processing Systems, 2012.
[15] Aurélien Garivier and Emilie Kaufmann. Non-asympiotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models, 2019.
[16] Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits, 2014.
[17] Jiafeng Guo, Xueqi Cheng. Gu Xu, and Huawei Shen. A structured approach query recom- mendation with social annotation data. In Proceedings of the 19th ACM international conference on Information and knowledge management, pages 619-628, 2010.
[18] Samarth Gupta, Shreyas Chaudhari, Gauri Joshi, and Osman Yagan, Multi-armer bandits with correlated arms, 2020.
[19] Vassilis N. loannidis, Xiang Song, Saurav Manchanda, Mufei Li, Xiaoqin Pan, Da Zheng, Xia Ning. Xiangxiang Zeng, and George Karypis. Drkg drug repurposing knowledge graph for covid-19. https: / /g thub. com/ / 2020.
[20] Mohsen Jamali and Martin Ester. Trustwalker: a random walk model for combining trust-based and item-based recommendation. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 397-406, 2009.
[21] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits the fixed confidence setting. 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2014.
[22] Ming Ji and Jiawei Han. A variance minimization criterion to active learning on graphs. In Neil D. Lawrence and Mark Girolami, editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 556-564, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
[23] Gauri Joshi, Emina Soljanin, and Gregory Wornel. Efficient redundancy techniques for latency reduction in cloud systems, 2017.
[24] Kirthevasan Kandasamy, Gautam Dasarathy, Barnabas Poczos, and Jeff Schneider. The multi- fidelity multi-armed bandit. In Advances in Neural Information Processing Systems, pages 1777-1785, 2016.
[25] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM JOURNAL ON SCIENTIFIC COMPUTING, 20(1):359-335 -322 1998.
[26] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of a/b testing, 2015.
[27] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models, 2016.
[28] Douglas Klein and Milan Randić. Resistance distance. Journal of mathematical chemistry, 12(1):81-95, 1993.
[29] Tomáš Kocák and Aurélien Garivier. Best arm identification in spectral bandits. arXiv preprint 2XXv:20005008441 2020.
[30] Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan. Collaborative learning of stochastic bandits over a social network. IEEE/ACM Transactions on Networking, 1784): 1795, 2018
[31] Dan Kushnir and Luca Venturi. Diffusion- deep active learning. CoRR, abs/2003. 10339, 2020.

---

[32] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[33] Daniel LeJeune, Gautam Dasarathy, and Richard Baraniuk. Thresholding graph bandits with grapl. In International Conference on Artificial Intelligence and Staristics, pages 2485-2485 PMLR, 2020.
[34] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: / snap. stanford. edu/ data, June 2014.
[35] Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits, 2016.
[36]
John Lipor and Gautam Dasarathy. Quantile search with time-varying search parameter. In 2018 52nd Asilomar Conference on Signals, Systems, and Computers, pages 1016-1018. IEEE, 2018.
[37] Yifei Ma, Roman Garnett, and Jeff Schneider. o -optimality for active learning on gaussian random fields. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[38] Yifei Ma, Roman Garnett, and Jeff Schneider. o-optimality for active learning on gaussian random fields. In NIPS, pages 2751-2759, 2013.
[39] Yifei Ma. Tzu- Kuo Huang, and Jeff Schneider. Active search and bandits graphs using sigma-optimality. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pages 542-551, 2015.
[40] Yifei Ma, Tzu- Kuo Huang, and Jeff Schneider. Active search and bandits on graphs using sigma-optimality. UAI' 15, page 542-551, Arlington, Virginia, USA, 2015. AUAI Press.
[41] Shie Mannor and John N. Tsitsiklis. The sample complexity of exploration in the multi-armed December 2004.
bandit problem.
[42] Kenneth Nordström. Convexity of the inverse and moore-penrooe inverse. Linear Algebra and its Applications, 134(6):1499-1512, 2011.
[43] Nikhil Rao, Hsiang-Fu Yu, Pradeep Ravikumar, and Inderjit Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In NIPS, volume 2, page 7. Citeseer, 2015.
[44] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[45] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, 2019.
[46] Benedek Rozemberczki and Rik Sarkar. Characteristic Functions on Graphs: Birds of Feather, from Statistical Descriptors to Parametric Models. In Proceedings the 29th ACM International Conference on Information and Knowledge Management (CIKM 20), page 1325- 1334, ACM, 2020.
[47] Ohad Shamir. A variant of azuma's inequality for martingales with subgaussian tails, 2011.
[48] Herbert A Simon. A behavioral model of rational choice. The quarterly journal of economics, 69(1)999-118, 1955.
[49] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits, 2014.
[50] Cem Tekin and Eralp Turgay. Multi-objective contextual multi-armed bandit with a dominant objective. IEEE Transactions on Signal Processing, (6614):379--3113 2018.
[51] Michal Valko, Rémi Munos, Branislav Kveton, and Tomá' Koeák. Spectral bandits for smooth graph functions. In International Conference on Machine Learning, pages 46-54. PMLR, 2014.
12

---

[52] Dingyu Wang, John Lipor, and Gautam Dasarathy. Distance-penalizee active learning via markov decision processes. In 2019 IEEE Data Science Workshop (DSW), pages 155-159. IEFF, 2019.
[53] Liwei Wu, Hsiang-Fu Yu, Nikhil Rao, James Sharpnack, and Cho-Jui Hsieh. Graph dna: Deep neighborhood aware graph encoding for collaborative filtering. In Interaational Conference on Artificial Intelligence and Statistics, pages 776-787. PMLR, 2020.
[54] Yifan Wu, András György, and Csaba Szepesvári. Online learning with gaussian payoff's and side observations, 2015.
[55] Wenjun Xiao and Ivan Gutman. Resistance distance and laplacian spectrum. Theoretical chemistry accounts, 110(4):84--89, 2003.
[56) Kaige Yang. Xiaowen Dong, and Laura Toni. Laplacian-regullrrzzed graph bandits: Algorithms and theoretical analysis, 2020.
[57] M Todd Young, Jacob Hinkle, Arvind Ramanathan, and Ramakrishnan Kannan. Hyperspace: Distributed bayesian hyperparameter optimization. In 2018 30th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 339-347. IEEE, 2018.
[58] Jifan Zhang, Julian Katz-Samuels, and Robert D. Nowak. GALAXY: graph-based active learning at the extreme. CoRR, abs/2202.01 2022.
[59] Yuan Zhou, Xi Chen, and Jian Li. Optimal pac multiple arm identification with applications to crowdsoureing. In International Conference on Machine Learning, pages 217-225. PMLR, 2014.
[60] Xiaojin Jerry Zhu. Semi-supervised learning literature survey. 2005.
13

---

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] Please refer to Appendix for full discussion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Please refer to Appendix 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 of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] we include them in the supplementary material.
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] We include the code in supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We specify them in the experiment section 7
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(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)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] We did not.
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
We did not.
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [No] Data is public.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "YM6z3Rd5dhe", "reviewer": "Reviewer_XXzj", "summary": "The paper tackles the problem in which a MAB setting with a pure-exploration goal having a large number of arms, has also some structure among the arms by means of a similarity matrix stating how much the expected value of the arms can differ from each other. They propose an algorithm able to exploit such a structure and analyse the problem in terms of lower bound complexity. Finally, they show that exploiting the structure of the graph provides significant improvements over the standard MAB algorithms.", "questions": "Could you give more details on the settings in which the smoothness assumption is satisfied? How it is possible to infer \\epsilon?\n\nWhat happens if the algorithm is used on settings in which the assumption about the smoothness of the problem?\n\nDid you compare your approach also with Thompson Sampling?", "limitations": "I do not foresee limitations and potential negative societal impacts of this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic analysed by the paper is interesting. The setting is clear, even if it is not clear how often the assumption required by the formulation of the problem is satisfied in real settings.\n\nThe paper requires some proofreading to polish it from orthographic errors. I mentioned a few of them in the minor section. Overall it is clear and well structured.\n\nOverall, the paper is not self-contained. In my opinion, the authors should have done a better job in the identification of the crucial points of the paper, avoiding repetitions and inclusion of the elements which are crucial to having a self-contained paper. For instance, you decided to defer the parameters c_1 and c_2 to the appendix. The same holds for the pseudo-codes of the algorithms and the definitions of the sampling strategies.\n\nMinor:\nLine 85 (and following comments) State that \"potentially without playing it even once!\" is not necessary.\nLine 155: \"natural\" it is not clear to me what you mean with \"natural\"\nLine 159: sub-optima -> sub-optimal\nLine 178> utilization -> use\nLine 217: e.g -> e.g.,\nLine 221: atleast -> at least\nLine 279: in mean -> in terms of expected reward", "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": "6cvquCEuFhw", "reviewer": "Reviewer_vans", "summary": "In this work, the authors introduce and study a novel variant of the multi-armed bandit problem, where side-information on the similarity (in mean reward) among different arms is provided to the decision-maker. In particular, the authors consider a weighted graph on the arms/nodes, where the weight of each edge indicates how similar the two \"adjacent\" arms are. For this model, the authors provide a novel algorithm for the problem of best-arm identification, for which they provide associated guarantees. By providing a lower bound, they show that their algorithm achieves minimax optimality for an interesting class of instances. A variant of the algorithm for the problem of \\zeta-best-arm identification is also provided. Finally, the authors evaluate the empirical performance of their algorithm on synthetic and real data.\n", "questions": "- Could the authors comment on how the smoothness parameter \\epsilon scales (or should naturally scale) with the number of arms? Specifically, consider the example of a (dense) unit-weight random graph, where each edge appears with probability p = 0.1. What is \\epsilon in that case? To rephrase, how \\epsilon increases by adding a new arm to the graph? How this affects the provided guarantees compared to the case where no similarity structure is assumed?\n\n\n- Personally, I would move the section on $\\zeta$-GRUB to the Appendix (I do not think it contributes much to the main part). This would free some valuable space to add the pseudocode of GRUB and/or maybe some proof sketches of the main results.\n\n\n- Maybe it would be reasonable to discuss the line of work \"Online Learning with Gaussian Payoffs and Side Observations\" (NeurIPS '15) by Wu et al. and \"Asymptotically-optimal Gaussian bandits with side observations\" (ICML'22) by Atsidakou et al. \nThe side information structure assumed there (weighted graph) bears some similarities with the one considered in this paper.", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS:\n\n- Overall, the paper is very well-written and well-organized (including parts of the Appendix).\n\n- The proposed model is (to the best of my knowledge) novel, and applies to several scenarios where the number of actions is very large, yet some form of similarity structure between \"adjacent\" actions is available (e.g., social networks).\n\n- The proposed algorithm cleverly exploits the given graph structure and achieves minimax optimality a special class of natural problems.  \n\nWEAKNESSES:\n\n- Assuming some form of graph-encoded similarity structure is a reasonable assumption (e.g., all friends in a social network can have unit weight). However, knowledge of the smoothness parameter \\epsilon on the graph seems critical for the perormance of the algorithm, which, in my opinion, weakens the obtained results.", "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