Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits
Authors: Aakash Gore
Prasanna Chaporkar
Venue: Accepted by TMLR ()

Abstract: We study a stochastic multi-armed bandit setting where arms are partitioned into known clusters, such that the parameters of arms within a cluster differ by at most a known threshold. While the clustering structure is known a priori, the arm parameters are unknown. We derive an asymptotic lower bound on the regret that improves upon the classical bound of Lai & Robbins (1985). We then propose Clus-UCB, an efficient algorithm that closely matches this lower bound asymptotically by exploiting the clustering structure and introducing a new index to evaluate an arm, which depends on other arms within the cluster. In this way, arms share information among each other. We present simulation results of our algorithm and compare its performance against KL-UCB and other well-known algorithms for bandits with dependent arms. We discuss the robustness of the proposed algorithm under misspecified prior information, address some limitations of this work, and conclude by outlining possible directions for future research.

Published in Transactions on Machine Learning Research (02/2026)
Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits
Aakash Gore
aakash.goreekitt..ck
Department of Electrical Engineering Indian Institute Of Technology Bombay
Prasanna Chaporkar
chaporkar witb ac
Department Electrical Engineering Indian Institute Of Technology Bombay
Reviewed on OpenReview: https: // oppnrevvee... net/ forun?? QDMUU999T
Abstract
We study a stochastic multi-armed bandit setting where arms partitioned into known clusters, such that the parameters of arms within a cluster differ by at most a known thresh- old. While the clustering struct ure is known a priori, the arm parameters are unknown. We derive an asymptotic lower bound on the regret that improves upon the classical bound of Lai Robbins (1985). We then propose Clus-UCB, an efficient algorithm that closely matches this lower bound asymptotically by exploiting the clustering structure and intro- ducing new index to evaluate arm, which depends other arms within the cluster. In this way, arms share information among each other. We present simulation results of our algorithm and compare its performance against KL-UCB and other well-known algorithms for bandits with dependent armss We discuss the robustness of the proposed algorithm under misspecified prior information, address some limitations of this work, and conclude by outlining possible directions for future research.
1 Introduction
The multi-armed bandit (MAB) is a fundamental problem in probability theory that encapsulates the classic trade-off between exploration and exploitation. It typically abstracted as a scenario in which a gambler is faced with slot machines (arms), each with an unknown reward distribution, and must decide which arm to pull at each timestep maximize the cumulative reward. Arms are assumed belong to the same distribution family, but with different (and unknown) parameters.
A seminal contribution in this area is by Lai & Robbins 1985), who showed that any uniformly good algorithm Just incur at least O(log N) regret, where N is the horizon. Several algorithms such as KL- UCB, UCB, and e-greedy have been proposed that asymptotically attain this logarithmic regret. This framework modols arms that are independent of cach other.
Bandit problems where arms are correlated or dependent have also been studied in the literature. These fall into the category of structured bandit problems. Many times, information about the structure results in fewer suboptimal arm pulls and results in lower regret bounds. In this paper, work with similar structured bandit problem, specifically one in which arms are clustered together.
1.1 Related Work
The classical MAB problem has received significant attention in the past, with one of the most notable contributions being by Lai & Robbins 1985). Using chango-of-measure argument, they derived theoretical
A uniformly good algorithm which incurs o(N)) regret. for all a 0 all instances

---

Published in Transactions on Machine Learning Research (02/2026)
lower bounds on the regret incurred by comparing algorithm's performance on two similar instances that differ only in their optimal arms. They also proposed a framework for constructing asymptotically efficient algorithms that achieve logarithmic regret.
A closely related work is that of Graves & Lai 1997]. where regret bounds were established for bandits in a controlled Markov chain setting. This work generalizes the procedure of finding a regret lower bound as a linear optimization problem. We use this approach in Section 3 to derive the lower bound for our problem.
For the classical MAB setting with independent arms, several algorithms have been proposed to achieve optimal regret asymptotically. Among the most influential are UCB by Auer et al. (2002), and KT.-UCB by Garivier & Cappé (2011). KL-UCB works by selecting the arm with the most optimistic estimate of the mean reward, derived from a Kl-ddiergence--based upper confidence bound. Our proposed algorithm is inspired by this principle and extends it to settings that showcase clustering.
Structured bandits, where dependencics among arms are loveraged to minimize regret, have also been ex- plored. For example; Combes & Proutiere (2014) and [Mauureauu et al. (2014) studied bandits under uni-modal and Lipschitz structures, respectively, and developed near-optimal algorithms. Mersereau & Tsitsiklis (209)) and Dani ct al. (0088) considered lincar bandits, where rewards are assumed to be lincar functions of unknown parameters. Zhang et al. (023)) studied the MAB problem on graph, where an agent has to maximize the cumulative reward collected from the nodes of a known graph. Agrawal et al. (1989) studied the case of controlled IID processes with a known finite parameter space, and drew parallels between this and a specialized MAB setting.
Singh al. (020) studied problem setting in which arms clustered and all arms in a cluster have the same parameter. They assumed that the distributions of rewards for arms in cluster can be different, depending on the cluster parameter. However, we assume that the parameters of arms in a cluster are within known threshold, with the same distribution family for all arms in the cluster. Guppt et al. (2021) worked on correlated bandits, where the expected reward of an arm given the reward of another arm is upper-bounded by a known function. This upper bound might be available through domain knowledge or offline estimates.
Pandey et al. (2007) investigated bandits with dependent arms, specifically instances where arms or- ganized into clusters. They assumed that arm parameters in a cluster are drawn from known generative model. They formulated a two-level policy assuming that the parameter distribution is tightly centered around its mean. Our problem formulation is a special case of this, where the parameter distribution is uniform over a predefined range, making it spread out rather than tightly centered. It can be seen from the simulation results in Section 5 that the amgorithm proposed by them would fail in our setting. This motivates the need for new algorithm, specific to our case.
Another line of work is dedicated to the online clustering of arms. Ban & He 20221) and Gentile et al. (2014) studied clustering in contextual bandits and provided algorithms that confidently cluster users by the proximity of their parameter vectors. Note that this is distinct from our setting, which assumes known clusters.
To our knowledge, our clustering criterion has not been explored in the literature and is useful if confident cluster width estimates are available through domain knowledge or offline data sampling.
1.2 Our Contributions:
We introduce a framework where arms are organized into constrained overlopping clusters, and derive theoretical lower bounds on regret in this structured bandit setting. By constrained, we mean that the arm parameters within a cluster cannot differ by more than a known threshold.
We propose Clus-UCB, an algorithm that efficiently exploits this structure and asymptotically achieves the regret lower bound on most instances.
We provide both the thcoretical analysis of the algorithm's performance in the Appendix, and simulation results in a later section, that demonstrate the practical effectiveness and theoretical optimality of our algorithm.
2

---

Published in Transactions on Machine Learning Research (02/2026)
2 Model and Problem Formulation
In this section, we first describe the standard stochastic bandit framework, followed by the specific structure of clustered arms that we address in this work.
2.1 Stochastic Bandit Framework
At each round n = 1.2.... T, learner selects one of K arms and receives reward sampled from an unknown distribution. Each arm k is associated with an unknown parameter 0g. E @ and known density (a;; 0s) with respect to a measure v. We assume:
I |nl5(x;0) < <c, 40 E 6.
The expected reward for arm k is given by:
Pk = =(=)) = of (x(())
Policy: A sequence of arms (ma), where Th E {I....,,$ K}, where nn is Fe-s-measurablee (depends only past actions and rewards).
Let n² = max 44 and denote by (n) the number of times arm k is pulled up to round n under policy m.
Regret:
Regret under policy x until round n is:
Rd (()) = Σ 1a
Here, f is the parameter vector and v(0) is the instance.
2.1.1 KL Divergence
The Kullback-Leiin LeiLler(KL) divergence is measure of difference between two distributions, In bandit prob- lems, this arises naturally to account for the complexity of the problem. If two arm distributions similar, then it is harder to gauge the optimal arm among these. For densities parameterized by O and 0:
1(0 = f1o0
([r;; (((:00) [xx; 0) ());))dv)))) du(x).
The one-sided KL divergence is defined as:
(+ I(0,0) if ((0) < m(0),
otherwise.
Assumptions:
I(0,0) 00 if m(0) p(0),
I(A, () is continuous in μ()).
For Bernoulli distributions with paramcters 0 and 9,
1(0,0) 0 log -
1-0
+(1 -1 (1-0)
0) log
1 {
For the rest of this work, we analyze settings where there is a one one relation between 0g and μas and hence interchangeably use T(O., 0b) and T(pas Mb) when the context is clear.
3

---

Published in Transactions on Machine Learning Research (02/2026)
Width_green
Width_rea red
Figure The widths represent cluster spans. While the fifth green point also lies within the red span, it's labeled green. Similarly, the first red point also falls within the green span but is labeled red.
2.1.2 KL-UCB Algorithm
For each arm k, define the KT-UCB in the th round as:
sup(0: (2(n) (n0, 0) s log + a logglog).
where (n) is the empirical parameter estimate of 1thh arm the nh round, and is a constant greater than 3. At each round, select the arm with the highest KL-UCB, Note that each arm must be pulled at least once, for the empirical means to be defined.
2.2 Clustered Arm Structure
We now introduce the clustering structure in which arms are grouped into overlapping clusters. Throughout this work, index the M clusters by (1,2....,M) M). Each cluster contains Kg arms, which index by i E (1,2,..., Ke), and denote the set of arms in cluster by K... For simplicity, we assume there is a unique optimal arm.
For any two arms j belonging to the same cluster e with parameters 8 and 0 respectively, we require:
10: 0dl Be, for all i e Ke: CE M),
where 3e O is the known cluster width for cluster We define θ the set of all parameter vectors satislying this clustering condition.
The assumption of known cluster widths is not purely theoretical but also practical when a rough estimate or non-trivial upper bound on Be available through domain knowledge or offline sampling. This framework applies naturally settings where arms share similar attributes. For instance, in online advertising, products from the same category (c.g., electronics) can be assumed cluster together. Similarly, in clinical trials, drugs with similar chemical compositions form natural clusters. While domain knowledge provides guidance cluster membership, the widths Se must be estimated from offinn data. One possible estimator is:
3. max u u(O min 1(0"), AE
ieK.
where u(-) and I(-) are appropriately chosen upper and lower confidence bound functions, respectively.
Importantly, each arm may satisfy the clustering property for multiple clusters. For example, an arm may fall within the allowed parameter ranges of two different clusters simultaneously. However, each arm is assigned to exactly one cluster, and this assignment is known. This overlapping structure is illustrated in Figure
3 Lower Bound for Regret
In this section, we state an asymptotic regret lower bound satisfied by any uniformly good algorithm æ. Let v(0) be an instance dependent on the parameter vector 0, and let R (()) be the regret incurred by x over horizon T on this instance. The algorithm is uniformly good if the regret Rd (T, v(0) o(T") as T grows large for all > and for all O.
4

---

Published in Transactions on Machine Learning Research (02/2026)
Theorem 1: Let II be uniformly good rule. For any 0 θ we have:
R (T)
lim inf T-000
2 C(O),
log
where
1= 16- me
1 maan
1 1 ue. [0c, gr)²
C(O)
Σ
min
Σ kE
E
ag lic
[0mmin 0" - -B)
c=l,fec
NEK. ((ke)
r = e (((6), , 0" = m 0
M = min& (((()), gmnin ming 8%
a 1 (0', 0²) 1t (0t, or Bc) b = (0 l" - Be)
Le 1+
K. k=
b
The lower bound of regret is derived using the results of controlled Markov chains from Graves & Lai 1997) The proof outline is presented in Appendix[A2 In general, the main idea used for deriving lower bounds is to consider an alternate instance, which 'close' to the actual instance under consideration, but has a different optimal mean. The algorithm needs to explore sufficiently to distinguish between the original instance and the alternate instance. For the clustered case under consideration, the alternate instance parameters also belong the clustered parameter space, unlike the classical case, where the parameters were unconstrained. This fact results in better lower bound in the structured case. In the proof, consider alternate instance as mentioned earlier, and the terms in the lower bound arise naturally as result of the cluster constraints. The following are some important points:
The exploration term for arm, i.e., Ler depends the parameters of other arms in that cluster. This is in contrast to the classical regret bound, where this term only depends on that arm's parameter.
This regret bound is always lower than that of the classical bandits derived in Lai & Robbins (1985) which is
R (I,) log T
ue T(0 0r)
Σ ヒー --.
lim inf 70000
ΣΣ KeK.
(005000)
KEK. MP)
For arms belonging to c", the regret term is the same as that of classical bandits. This is because inside c", the cluster structure makes no difference. On the other hand, for suboptimal clusters, we exploit the structure and make improvements in the bound.
It is seen that the regret contains a min(a, 6) term The second argument in this corresponds to the regret incurred by only pulling the worst arm in a cluster. All other arms in the cluster must be pulled sub-logarithmic times in expectation. Intuitively, the second term corresponds to instances where is relatively casier to distinguish the minimum arm a cluster from the best arm the instance, while the first term corresponds to instances where the agent must pull all arms in the cluster to be certain of its suboptimality. Hence, it is likely that if we have a loosely constrained cluster, the first term would be the minimum, while for tight clusters, the second term would be the minimum. However, in most of our presented here or otherwise, we found that the first term appears in the lower bound.
Note that for the trivial case of 3 = 1 for Bernoulli bandits, we essentially have no clustering information. Thus, the lower bound term for that cluster becomes the same as in the classical case. Here, we slightly abuse notation to convey that.
11 pmin
1 1
min
1+ 10min 0" 1m-38 -3a)
0
00,
5

---

Published in Transactions on Machine Learning Research (02/2026)
and
p- -ーー ur at Le
100 1 1(0% 0*) + EMECn 1 (0 BB)
Σ kEA.
Σ kEK.
Σ kEk
100. 0*)
For the trivial case 8e = O, we have Ka arms with the same parameter. Hence, Orenn = 0(let). So, f pu0) = julett.. This essentially means that have only one arm in the cluster.
Pe uann
1 ue 1 (0man H" - 3ce) (+,
-
and
Σ kEK.
11"
Σ I(0,0*)
1
1¹ μ I(0,0*)
Le
Σ Exeek I(8,8-)
kEKe
4 Clus- UCB Algorithm
We now present an algorithm whose regret closely matches the lower bound derived in the previous section for clustered overlapping bandits.
Algorithm Clus-UCI Algorithm
Require:
Horizon T, number of clusters M, arm sets {Ko.) with [Kel Ke, total number of arms K,
c= cluster gap parameters {3e)m M constant a 2 5
Pull each arm once; initialize (K + 1) 1 and estimates OK (K + 1)
2: for n n= K to T do
3: for each cluster == M and each arm k E K. do Update empirical estimate (n)
4:
end for
for each cluster e= 1,...,
......,A. M and each arm E Ka do Compute Clus-UCI index:
(m) sup q: (2)r (05(m)))))))))) + Σ (n) (0% (n), 8c) s log + log log T1
MEKOA(K
8:
end for
9:
if E(c, k) such that (n) s log log then
10:
Pull arm cluster e
11:
else
12:
Select (c', k) arg max. & Pull arm I'' in cluster d'
v (n)
13:
14: end if
15:
Observe reward and update counts
16:
end for
Theorem 2: Assuming that the bandit arms have bounded rewards or belong to the canonical exponential family (=(x) exp(x0 b(0) c(x)), with parameters clustered according to Section 2.2 asymptotic regret is upper-bounded
Clus-UCB:
RdT (T, (TT(Tu(O)
lim inf T-000
< C(H),
log T
where
M Σ
-² v I+ 04)
C(0)
Σ
E
I
o= c=L,eee kEK.
kEko\(ke)

---

Published in Transactions on Machine Learning Research (02/2026)
The proof of Theorem 2 for Bernoulli bandits is present in Appendix family with bounded rewards according to Lemma 9 and Theorem 10 in Garivier & Cappé 2011 Theorem
A.3 This can be extended to any
2 in Magureanu et al. 2014) implies that this holds for the canonical exponential family.
The following are some key points about this algorithm:
Forced Exploration of Under-Explored Arms: The algorithm design ensures that an arm with less than log logn pulls time gets pulled eventually. This ensures that no arm faces starvation and all arms get pulled infinitely often.
Rare Suboptimal Pulls Due to Confidence Underestimation: The event in which an arm of a suboptimal cluster is pulled because the Clus-UCI of the optimal arm falls below its mean occurs only O(log log times.
Pull Ratio Among Arms in Suboptimal Cluster: Within a suboptimal cluster, arms are pulled in inverse proportion to their exploration coefficients. That is, for two arms with exploration parameters 0g and 0gg' the expected number of times they are pulled over a long time satisfies:
BTA ET so a a
Expected Pulls of Arms in Suboptimal Clusters: An arm & belonging to suboptimal cluster c is pulled approximately
log T log
a Le
limes expectation, over a long time, where a and The are as defined earlier.
Near- Tear-Optimmlity: The upper bound presented above, matches the regret lower bound derived carlier on most instances, but not all. This makes the algorithm near-optimal.
The motivation to use the Clus-UCB index as done in the algorithm is through the lower bound derived and the analysis done by Garivier & Cappé 2011 A forced exploration term is also added to ensure all arms get pulled infinitely often.
Intuitively, the optimality of an arm is evaluated not only by its individual performance but also through the collective behavior of its cluster. When other members of the same cluster provide sufficient evidence indicating that the cluster a whole is suboptimal, the index of an arm is accordingly suppressed even if its own empirical mean remains high, thereby reducing unnecessary exploration.
The regret lower bound formally captures this interdependence, justifying the proposed index as a theoreti- cally motivated choice. Specifically, the index quantifies the exploration required to distinguish the current instance from one which arm k in cluster e optimal. The term corresponding to arm & coincides with the standard KL-UCB term, while the additional T+ T+(0",, q B.) components represent the information con- tributions from other arms within the same cluster, under the hypothesis that arm k were optimal. The offset term q Be incorporates the effective range of these dependencies.
5 Simulation Results and Discussion:
We ran simulations comparing KL-UCB, UCB and KL-UCB-based Two-Level-Policy(TLP) different bandit instances, and figures 8 show the results. For simplicity, the simulations omit the forced exploration component (lines 9-10 of the algorithm). Given our time horizon of 10 steps, this omission has negligible impact on performance. All experiments were performed on a computer with 16 gigabyles of RAM. No GPU was used. The plots show the results of 200 simulations, with the means and the 95% confidence intervals presented. To speed up the simulations, we used a multiprocossing framework with CPU cores. Furthermore, we updated the UCBs every 50 timesteps reduce computation time. The UCBs were caleulated using binary search, and accurate up 4 decimal places. Here, is the cluster width vector.
7

---

Published in Transactions on Machine Learning Research (02/2026)
We consider two variants of the Two-Level Policy (TLP) suggested by Pandey et al 2007 MEAN and MAX. TLP treats each cluster "super arm" and uses base policy (KI-UCB) to choose which cluster to play. Once cluster is selected, the base policy is applied to its arms. Cluster selection requires a cluster reward estimate:
In MEAN, this is the total successes of all arms in the cluster divided by the total cluster pulls.
AMAN (n) Etek. (2)))))()) ΣkEK, 18(m)
In MAX, it is the maximum empirical mean among the cluster's arms
Pe MAX (n) max (m)
In our experiments, Clus-UCB consistently outperforms KL-UCB. However, on certain instances, TLP can outperform Clus- UCB. That said, TLP is not asymptotically optimal, as it lacks knowledge of cluster widths. Moreover, since TLP assumes arm parameters are tightly clustered, it is straightforward to construct hard instances where its performance degrades sharply (see Figure 5). This because on average, the suboptimal cluster will have a higher cluster estimate as compared the optimal cluster, which results in the suboptimal cluster being pulled more often. We also ran simulation with 20 clusters and 55 arms, incorporating a wide varicty of cluster types together. The result can be found in the Appendix A.]
5.1 TLP vs UCB
The simulation results demonstrate that TLP either significantly outperforms Clus-UCB or performs simi- larly when clusters non-overla,,ing, while Clus-UCB significantly outperforms TLP for heavily overlap- ping clusters. This performance difference can be explained theoretically: for instances with non-overlapping clusters, the regret lower bound is independent of cluster widths and is lower than the bound presented in Section 3 In such cases, Clus-UCB's design makes it overly conservative during exploitation, leading to unnecessary exploration beyond what is required. TLP, however, does not suffer from this issue, as the non-overlapping structure allows the cluster reward estimates to accurately identify the optimal cluster most times.
Therefore, recommend using TLP when clusters are known to be non-overlapping. However, when such well-separation assumptions cannot be guaranteed, Clus-UCB is the preferred choice, as it leverages cluster width information to achieve more efficient exploration in these challenging scenarios.
6 Misspecification of Cluster Widths
An important point to consider is the misspecification of cluster widths. Cases where the exact widths are not known, but an estimate is available, might be more practical. the widths are overestimated, the proposed algorithm continues outperform KL-UCB. The case of underestimated widths, however, is more nuanced. In the proof of Clus-UCB's optimality (Appendix), divide the votal number of pulls of arm in suboptimal cluster into two cases:
when the Clus-UCB index of the optimal arm is less than its mean, and
when the index is greater than or equal to its mean.
We bound these two terms separately. It is noteworthy that the cluster constraint is used only in bounding the first term, which leads to an O(log log T') bound. Moreover, this bound depends solely on the width of the optimal cluster. In fact, throughout the proof, there no requirement that the other (suboptimal) clusters satisfy their respective constraints.
At first glance, this may appear surprising. However, the problem formulation we present is actually a special case of more general setting of the allowed instances: every cluster has associated width, but the cluster
8

---

Published in Transactions on Machine Learning Research (02/2026)
Aumei Bandit Algorithm Comparison Simulations)
KL-UCB
Clus-UCB ILP-Maan-KL TLP-MbX-KL
IC00
Cumulative Cemulative Expected Regret
800
400
200
0.0
0.2
C.4
0.6
0.8
1.0
Time
Figure Comparison of Clus-UB with other algorithms on the instance (0.40,0.4110.44), 0..60.066.0.62) with B j0.02, 0.02] and a horizon of 10 time steps. These represent well separated clusters. The first term in min appears in the regret lower bound for the suboptimal cluster in this instance.
constraint is required to hold only for the optimal cluster in the fixed instance, while suboptimal clusters may violate it. Our formulation imposes the stricter condition that all clusters satisfy their constraints, which is a subset of the general case. This is distinct from the scenario where, in a given instance, a fixed cluster (which happens be optimal) satisfies the constraint but an originally suboptimal cluster which becomes optimal in alternate instance need not satisfy this constraint. In the general setting, while constructing alternate instance, the originally suboptimal cluster may become optimal and must then satisfy its width constraint. In our setting, the regret lower bound derived earlier continues to apply to this more general case as well.
From this perspective, underestimating the width of suboptimal cluster does not harm performance in fact, improves the performance due to the larger denominator (B, Be) in the regret bound. This is shown in Figures g and where the cluster width estimate for the suboptimal cluster is reduced from correctly estimated to underestimated. However, underestimating the width of the optimal cluster can lead to substantial regret. This is because the O(log log 7') bound may not hold now. This is shown in Figure 7
If all cluster widths are specified correctly or are overestimated, Clus-UCH UCB retains the property of being uniformly good. Hence, for the algorithm to work well, the sufficient condition is that the optimal cluster must have an overestimated width.
7 Limitations and Future Work
The algorithm provided is asymptotically optimal for most instances, but not all. However, we believe that a more carefully chosen optimistic index, might perform optimally on all instances, albeit with increased complexity analysis. It also possible to develop a randomized Bayesian algorithm, similar to Thompson sampling. The beliefs would still be Beta distributed, but only supporting parameter values that satisfy the clustering constraint. We leave the proof of optimality of this algorithm for future work. Finally, though overestimation of the optimal cluster's width does not harm much, underestimating may be significantly

---

Published in Transactions on Machine Learning Research (02/2026)
Multi-Armed Bandit Algorithm Comparison (200 Simulations)
KL-UCB
Clus-UCB TLP-Mean-KL P-MAx-KI
800
Cumulative Expected Regret
600
400
0.4
0.6
Time Step
Figure 3: Comparison of Clus-UCB with other algorithms the instance [0.80,0.82,0.84]] [0.81.0.83.0.85] with 3 [0.04, 0.04] and horizon of 10 time steps. These represent overlapping clusters. The first term in min appears in the regret lower bound for the suboptimal cluster in this instance.
Multi-Armed Bandit Algorithm Comparison (200 Simulations)
KL-UCB
Clus-UCB
ILP-Maan-KL
TLP-MoX-KL
Cumuletive Expected Regret
1000
750
500
250
0.2
C.4
0.6
Time Step
Figure 4: Comparison of Clus-UCH with other algorithms the instance [0.41,0.42,0.43]] (0.43,0.44.0.45) with B [0.02, 0.02] and a horizon of 106 time steps. These represent close but separated clusters. The first term in min appears in the regret lower bound for the suboptimal cluster in this instance.
10

---

Published in Transactions on Machine Learning Research (02/2026)
Multi-Armed Bandit Algorithm Comparison (200 Simulations)
Clus-UCB ILP-Mean-KL TLP-Max-KL
10000
Cumulative Expected Regret
8000
2000
0.0
02
0.4
0.6
0.8
1.0
Time Step
18
Figure 5: Comparison of Clus-UCD awith other algorithms on the instance [0.68,0.69,0.67], [0.1,0.2.0.7] with 3 (0.02, 0.8) and horizon of 10 time steps. This represents instance where the TLP-Mean policy performs poorly. The first term in min appears in the regret lower bound for the suboptimal cluster in this instance.
Multi-Armed Bandit Algorithm Comparison (200 Simulations)
KL-UCB
Clus-UCB TU--Maan-KL
TLP-MaX-KL
Cumulaaive Expected Regret
1250
1000
750
500
250
Time Step
Figure 6: Comparison of UCB with other algorithms on the instance [0.41,0.42,0.43)) (0.43,0.44.0.45 with 3 = [0.00, 0.02] and a horizon of 10 time steps. These represent close but separated clusters. The second term in min appears in the regret lower bound for the suboptimal cluster in this instance.
11

---

Published in Transactions on Machine Learning Research (02/2026)
KL-UCB Clus-UCB with Different Beta Values (48 Simulations)
KL-UCB Average
Clus-UCB [8-[0.5, 0.9]) Average
Clus- [8=[0.4, 0.71) Average
Clus-UCB (8=[0.1. 0.71) Average
Clus-UCB [8-[0.4, 0.2)) Average
Cumu inlulliive Expectest Reggel
633
10060
100660
Time Step
Figure Comparison of Clus-UB and KL-UCB on the instance (0.11007),(01100222008). with $ (0.5.0.9]. 3 0044.077 [0.1, 0.7], and [0.4, 0.2] and horizon of 10 time steps.
harmful. Thus, separate framework dealing with width estimates as unreliable side-information seems worth exploring.
8 Conclusion
this work, we analyzed a clustered bandit setting where prior information on an upper bound of cluster widths available. We established an improved regret. lower bound compared to the classical result of Lai & Robbins (1985) for unstructured bandits, and proposed the Clus-UCI) algorithm exploit this structure. structure-uawware
Our analysis showed its near-optimality, and simulations confirmed its advantages algorithms well as its competitiveness with the two-level policy of Pandey et al. (2007). We further examined cases where cluster widths are misspecified and identified necessary condition for Clus-UCB to remain robust under such settings. Despite these contributions, certain limitations remain. In particular, our algorithm is near-optimal, however, a more carcfully chosen index might lead to an optimal algorithm.
References
R. Agrawal, D. Teneketzis, and V. Anantharam. Asymplotically efficient adaptive allocation schemes for controlled i..d. processes: finite parameter space. IEEE Tronsactions on Automotic Control, 34(3):255 267, March 1989. doi: 10.1109/9. 1911115.
P. Auer, N. Cesa-Biin Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2 3):235 256, 2002.
Yikun Ban and Jingrui He. Local clustering in contextual multi-armed bandits. In Proceedings of the Web Conference 2021, pp. 2335 2346. ACM, 2021. doi: (0.1145/344238813449999 URL https://dl.cc. acm. org/ doi/10. 1145/3442381 9449999992813344999999 3449909
Combes and A. Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. In Proceedings of the 31st International Conference on Machine Learning (ICML), pp. 521- 5219,, 2014.
12

---

Published in Transactions on Machine Learning Research (02/2026)
V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic lincar optimization under bandit feedback. In Proceedings of the 21st Anaual Conference on Learning Theory (COI.T), pp. 355-366, 2008.
A. Garivier and O. Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th Annual Conference on Learning Theory (COLT), 2011.
Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In Eric Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 757 765. PMLR, 2014. URL /ttpps/tt////rooeediii mll. preas/v32/ http:////geneeee....m html
T. L. Graves and T. L. Lai. Asymptotically efficient adaptive choice of control laws in controlled markov chains. STAM Journal on Control and Optémization, 35(3):715-745 743, 1997.
S. Gupta, S. Chaudhari, G. Joshi, and O. Yagan. Multi- armed bandits with correlated arms. IEEE Trans- actions on Information Theory, 67(10):6711-66)) 1-6732, 2021. doi: 10.1109/THT
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mothe- matics, 6(1):4-22, 1985.
S. Magureamu, R. Combes, and A. Proutiere. Lipschitz bandits: Regret lower bounds and optimal algorithms. In Proceedings of the 31st International Conference Machine Learning (ICML), pp. 424-432, 2014.
A. Mersereau and J. N. Tsitsiklis. Dynamic spectrum access with learning for cognitive radio networks. In Proceedings of the 43nd Annual Conference on Information Sciences and Systems (CISS), 2009.
S. Pandey, D. Agarwal, D. Chakrabarti, and V. Josifovski. Multi-armed bandit problems with dependent arms. In Proceedings of the 24th International Conference on Machine Learning (ICML), pp. 721 728, 2007.
R. Singh, F. Liu, Y. Sun, and N. Shrolf. Multi-armed bandits with dependent arms. ar preprinl WxXiv2200009//20 2020. URL httpss//aaxiv.orrt www.:r//////.......//
T. Zhang, K. Johansson, and N. Li. Multi-armed bandit learning on graph. In Proceedings of the 57th Annual Conference Information Sciences and Systems (CISS), pp. 1 6, 2023. doi: 10. 10.1109/C18556502. 1008974.
A Appendix
A.1 Extra Simulation Results:
The instance under consideration was (0.1,0.7,0.9), [0.1,0.15], [0.12,0.14.0.133, [0.23,0.30], [0.28,0.34,0.32], [0.16,0.17], [0.65,0.61, 0.63,0.6666) (0.1,0.2,0.95), [0.91,0.92), [0.40,0.41,0.42]] [0.81,0.86,0.89] (0.78,0.85,0.88) (0.1,..5.0.9). (0.92, [0.01,0.02,0.03] [0.05,0.1]. [0.2,0.36], [0.2,0.21,0.78), (0330029,0033,0.54,)
[0.57,0.6] with cluster widths [ 0.8, 0.05, 0.02, 0.07, 0.06, 0.01, 0.05, 0.85, 0.01, 0.02, 0.08, 0.10, 0.8, 0.02, 0.02, 0.05, 0.16, 0.58, 0.25, 0.03
A.2 Proof of Theorem 1
We follow the analytical framework developed by Graves & Lai (1977.. Let. θ denote the set of all problem instances consistent with the given cluster structure. For each arm J, define O, as the set of instances in which arm is optimal. Given instance 0 E O let (() be the set of optimal arms under 0.
We define the set of bad instances as:
B(0) A E 0: A6 - Vj E J(0), and X & U O, p)) JEJ(B)
13

---

Published in Transactions on Machine Learning Research (02/2026)
Multi-Armed Bandit Algorithm Comparison (200 Simulations)
Clus-UCB ILP-Mean-KL TLP-Max-KL
10000
Cumuiative Expected Regret
4000
2000
0.0
0.2
0.4
0.6
0.8
1.0
Time Step
189
Figure Comparison of CCus-UCB with other algorithms for 20 clusters with arms.
Here v/ is the mean of arm j in the instance v(0). Let C(0) be the value of the following optimization problem:
C,I(b, 2 2
C(O) = inf
Cjlub mb) - C O, inf (EJ(M)
Σ
Σ
( jQJ(O)
where I(::)) the KL divergence.
According Theorem of Graves Lai 1997), this quantity characterizes the asymptotic lower bound regret for any uniformly good algorithm
R (n, v(O)) C(O)-
lim inf
log
Computing C(() reduces to solving linear program. Suppose that under a bad instance X, some arm i from a suboptimal cluster co becomes optimal. The value of
Σ C, SEJ(0)
is minimized when, for all clusters except co, the arm means under À match those of the suboptimal arms in 0. For cluster co, the i-th arm has mean greater than pgg while other arms in co have means
r = max(ug, 1² Bc).
The minimum is achieved when 1² p/g
For a given cluster with Ko arms indexed by t = l...., Kow the system of inequalities becomes:
C.T(E,p))) +
Σ
C&r+ - -3.) 2
keR 100
14

---

Published in Transactions on Machine Learning Research (02/2026)
where Mr Nb: and μ¹ pg.
Let B be a Kep x aa matrix, where each column has elements b.. Let a be diagonal matrix of a terms, and c column vector of the C₁ variables. Define the reward gap vector with entries = uu The linear program becomes:
min c20
aTc
subject to [ BBaac221.
This optimization can solved using standard techniques, and we get the desired lower bound.
This process repeated across all clusters to compute the global infimum C(0).
A.3 Proof of Theorem 2
This work follows the outline of the proof of Theorem 2 in Garivier & Cappé (2011). We now state theorem from Magurcanu al. (2014).
Theorem 3: For all 8 > K + 1, n N, we have:
Σ t (n)d (PE) 28 S se ( [8log n16, [6logn]6, {kkt1)
K
P
K
If 6, log n + a log log ,with a 2 5, then
} Ollog log T)
E
Σ
(n)d+ (RE, 2 8n
Let be the best arm in cluster c. Let An be the arm-cluster pair pulled by the algorithm at time step Now, we proceed by bounding the number of pulls as:
((T)) = Σ = -(,c)(
T Σ [{A, = (i,c), 2 (1)))())))))++1+441 = (1,c),,0 < <}}}, n=l
where (n)) is the Clus-UCB of the optimal arm at timestep n. Now,
T Σ iAA (1,c), < Σ (m))))<<p)))))
T
Notice that
k (n)d (Bt: (m), + Σ
f (n)d (pt. 2 (n)at (m),.(e))
Σ t (m)dt (n), - Bc-)
kEK-
as u. 2 40- - Ba.
Vk E c" and as KL-divergence increasing in the second term
Define
Bn = E5' (n)d ppt (w): + Σ
(n)dt (pt- (n),
(EKe
Cn 1 (n)dt (1% (n),,1)))
Σ
(m)d+ (n)) n²= - -Bo)
BEK.)(K-)
15

---

Published in Transactions on Machine Learning Research (02/2026)
Hence, Bn Cn
Now (n) < x=)== & P(C,, > logn + aloglogn) S P(B,, > log n + alog log
Hence, using Theorem 3, we have
T Σ
E E <()(n)<*)))
P(C, > logn + a aloglogg) & Σ P(Bn logn + a alooooog n) Ollo log 7)
Other term:
T [{An (mc), 2n}
n=1
T Σ n=1
I [An = (2,c). 2 u (2( S log n + Σ 1 (i,), 2 n² (m)) > loglog
x=1
Olog log T)
Σ a=1
1fAn (i.c), u², (((n)) log logn,
Note that
{An - (1,c),, 2 u², ((((m))) loglogn] (n(n) v² v²(n)) n¹
Thus, the inequality continues as
Σ X
Σ (n)dt (pC(n), Bc) s logn log log
kEKO)(1
where
X, =I -(,)) 2 u0, (((()) loglogn)
Xa.I (amilld (1 &
E
(() dt (fE()), B.)] < logn log log n (2(m)
REKAM0
We now make key observations about the behavior of the algorithm:
1. Regret upper bound: The regret of the algorithm can be upper bounded by that of the KL-UCB algorithm. This follows as:
Σ (n) at (pt(n). -B)] log + a log log
Σ I el()) (2) n=1
(((n)
Σ (p < logn logglog
The right hand term is what we get while analyzing KL-UCB. Thus, the regret of Clus-UCB is upper bounded by the regret of KL-UCB, Hence, all suboptimal arms are pulled O(log times in expectation.
2. Convergence of Clus-UCB values: The Clus-UCH values of all suboptimal arms must converge to n², the mean of the optimal arm. We prove this by contradiction:
(a) Suppose the Clus- UCB of a suboptimal arm é converges to some value u < 4²" Then, eventually, the algorithm will stop selecting this arm. As a result, the number of times is pulled will be sub-logarithmic, contradicting the earlier claim that every suboptimal arm is pulled O(log T) times.
16

---

Published in Transactions on Machine Learning Research (02/2026)
(b) Suppose instead that the Clus-UCB of a suboptimal arm converges to μ²" Since the Clus- UCB of the optimal arm converges to n², the suboptimal arm will eventually have a strietly higher UCB. This would lead the algorithm to pull it linearly often, resulting in linear regret, which contradicts the O(log upper bound.
Now, notice that
(((d)d (Pd(m)). +
Σ (l)dd ((((m)) Be) = =log n + a log log n. kER.V10
+ (d o((()) a at (Rt(m), c/(n) Bc))+ + Σ (m(dd (AE(m). - -Ba) llog n + a log n.
kERe
Let = (11 - d+ (pt(m), ((()) - Be)) and g:(n) = =kek. (n)dt (nE(n), (n) - Be) Thus, fe(n)) + (n) = logn + alog log for all arms & in cluster c. Also, since we are interested in the time instances when arm has the maximum cluster index, gi(n) 2 (n(vbkk 1, vg(n) 2 v((n)
This implies, (n) S fe(n)vk 2,,...Ke. Thus,
vn(()) - Be) 2 (1), - (f)(m)) d (n) (n), - dt (n), (n) - Be)
(m)
Due to the design of the algorithm(forced exploration of arms with less than log log pulls), all arms are pulled infinitely often asymptotically, i.e, Numbers, the empirical mean of each arm converges almost surely to its true mean. This implies that for any e > 0, each arm's empirical mean differs from its true mean by more than only finitely many times along its pull sequence. Consequently, almost surely, there exists a random time after which each arm's empirical mean remains e-close to its true mean. For a finite cluster of arms, by taking the maximum of these (finite) random times, we can conclude that almost surely, there exists a finite time N, after which all empirical means in the cluster are simultaneously e-close their true means. Also, (n()) 2 pa and (n) 2 (m). Thus, after time Ne,
faces starvation. Hence, by the Strong Law of Targe
d(p)(m), (m)) - dt (Pt (m) - 3e) (n), (n)) - dt (pt of()) 3c) d(u + e, ef()))))))))))))))))))))) dt (v= + c,( 3c)
2 d(r. - e, (d) - d+ e, vg(()) - Bc)
We also have u 2 , and hence the right hand side is increasing with respect to cn(...
d(pt. e, vm()) - dt (ut e v((m) Bo)
2 a - O(s)
d(p + + vg()) - d (ot + c, vg(()) - Bc))
%%
Thus, the inequality continues as
NN.+ + Σ X ( esmola (1
(n) at (2C(n), BB)] s logn + a log log (t(n)
+ Σ
N1+1
kEK
T
<0(1) + Σ XI.II
(n) +e,+" +
Σ
dd +e, -c)] S log n + annaaaog log O(e)
ax
nm1
kEK.A(1)
<0(1) + Σ I
((m))d(( + +e,x)
Σ
a
ddd (ve +e,p Bc)] < log T + a loglog O())
O(())
a
kE
T
<0(1) + Σ Y sld (HL +e,H+)+ + Σ
Ledt +e,te -Bo] s logT + a log T + O(e)
ot
n=1 1=1
AEK.\(1)
17

---

Published in Transactions on Machine Learning Research (02/2026)
where
Yn = I(A, = (f) = =8}
sat at (pé + t, - - - <logT - alog T O(c) +(c)
x 00 + Σ
n sd (1o + cc,)+ + Σ
ag
n=1 s=1
hEKolli
sa O%
s 0 +
n I sd (1o:
+
Σ
(p.: 1²" - BB) s log T alog log T +
n=l 8=1
hEK.lli
a ddt (WEs - 3c)) S log + a log + O(e)
50 + Σ
nn s(d ((d( + E
1= ==1
kEK
50(1+ +
80 S log T + log log T + O(e)
n= 8=1
< 01)++ Σ
sajLe s log + a loggooog" O(e)
Σn Yn
0 log T + + O(c)
LtLe
Since all Clus-UCBs converge to μ and all empirical means converge to their actual means, we have f((n) fin(n) as n tends to infinity. Thus, for any other amm in the cluster,
((T log T
a a abLe atLe
lim sup T+
18


Reviews:
[{"review_id": "myYZtv1nI6", "reviewer": "Reviewer_Stnc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies stochastic multi-armed bandits where arms are partitioned into known clusters and any two arms in a cluster differ in mean by at most a known width. It derives an asymptotic regret lower bound that is strictly tighter than the classical Lai–Robbins bound by leveraging this structure, then proposes Clus-UCB, an index policy that lets arms share statistical evidence within a cluster via a KL-based confidence term that includes other arms’ observations. The analysis shows near-optimality: Clus-UCB matches the lower bound on most instances and yields interpretable properties. Simulations against KL-UCB and a two-level cluster policy confirm lower regret and examine robustness when cluster widths are misspecified (overestimation is benign; underestimating the optimal cluster’s width can hurt). The paper concludes with limitations and extensions (e.g., exponential-family rewards, Thompson-style variants).", "claims_and_evidence_yn": "Yes", "claims_explanation": "- They prove a tighter regret lower bound for clustered bandits than the classical Lai–Robbins unstructured case, and show Clus-UCB’s regret upper bound matches it on most instances.\n\n- The Clus-UCB index aggregates other arms’ statistics in the same cluster via a KL term, extending KL-UCB to exploit cluster structure—so arms “share” information and explore more efficiently than structure-unaware policies.\n\n- Experiments show Clus-UCB consistently outperforms KL-UCB and remains competitive with two-level policies; moreover, it stays strong when cluster widths are overestimated and its misspecification analysis depends mainly on the optimal cluster’s width.", "audience_yn": "Yes", "audience_explanation": "Yes—bandits are foundational in ML, and this paper’s clustered setting with tighter bounds and a near-optimal algorithm would interest TMLR readers focused on theory and decision-making systems.", "requested_changes": "- Motivation via real deployments.\nAlthough the setting (overlapping clusters with width constraints) is interesting, the paper lacks real-world grounding. Please add concrete applications (e.g., taxonomy-based recommenders where items share categories/attributes; clinical dosing where treatments share pharmacological classes) and explain how cluster overlaps and β-constraints emerge operationally (how practitioners would estimate/monitor them).\n\n- Beyond Bernoulli rewards.\nConsider extensions to general exponential-family/sub-Gaussian rewards, and discuss whether the analysis/indices change. Even better, outline (or prototype) a contextual bandit variant where clusters are defined in feature space and evidence sharing uses context-conditioned similarities.\n\n- Regret upper bounds—clarify and strengthen.\nConsider providing a regret upper bound, which can place this work better in the related literature.\n\n- Real-data evaluation.\nMay add experiments on some public real-world datasets, like recommender or online-decision datasets (e.g., news/recs bandit logs or clinical decision logs). Include offline policy evaluation (IPS/DR) and report sensitivity to β estimates and cluster overlap. This would substantively validate the practicality of the proposed structure.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "F5pdAYKAOI", "reviewer": "Reviewer_n3Dy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Summary\n\nThis paper investigates a clustered stochastic bandit setting where, for each cluster $c$, the mean rewards of arms differ by at most a known threshold $\\beta_c$. The authors first derive an asymptotic regret lower bound that improves upon the classical Lai–Robbins bound by explicitly leveraging the intra-cluster constraints. They then propose Clus-UCB, a KL-UCB-based algorithm that achieves regret matching the lower bound up to constants in most instances. Simulations against KL-UCB and two variants of the Two-Level Policy (TLP) demonstrate the empirical advantages of Clus-UCB.\n\n### Strengths\n\n1. The problem formulation is a natural generalization of existing models where arms in the same cluster are assumed to have identical parameters.\n2. The regret lower bound explicitly captures the effect of cluster structure, especially the threshold $\\beta_c$, and the proposed Clus-UCB algorithm is near-optimal.\n3. The paper includes a clear and detailed theoretical discussion. For instance, Theorem 1 highlights how the proposed bound refines the classical Lai-Robbins bound, and the authors provide insightful explanations through special cases.\n\n### Weaknesses\n\n1. Although the problem setting is general, Theorem 2 and the main analysis are restricted to the Bernoulli case. Providing more details or extensions to other distributions would strengthen the generality claims.\n2. The proofs for both Theorems 1 and 2 follow the standard frameworks from Graves & Lai (1997) and Garivier & Cappé (2011).\n3. There is no textual explanation for Algorithm 1. The authors should clarify the intuition behind including KL terms from other arms with a $q - \\beta_c$ shift, and explain the overall design rationale.\n4. The experimental baselines are either unstructured (KL-UCB) or somewhat outdated (TLP, 2007). Including more recent structured bandit algorithms would offer a fairer and more comprehensive comparison. There are also no error bars in the plots.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical claims are mostly well-supported by the lower bound (Theorem 1) and the algorithm analysis (Theorem 2). However, the generality claims (e.g., extension to the exponential family) are only mentioned briefly and not formalized. The design motivation of Algorithm 1 is also not well-justified.\n\nWhile the evaluations are somewhat limited in scope (See weakness 4), they qualitatively support the theoretical claims.", "audience_yn": "Yes", "audience_explanation": "The topic of multi-armed bandits is relevant to TMLR. The paper examines an underexplored setting that should interest researchers in stochastic bandits, recommendation, and reinforcement learning.", "requested_changes": "1. Clarify Algorithm 1's design and intuition. (Critical)\n2. Include more recent baselines and add error bars in the evaluation results. (Critical)\n3. Extend Theorem 2 to generalized distributions beyond Bernoulli. (would strengthen the work)", "broader_impact_concerns": "There are no broader impact concerns worth noting because this work is primarily theoretical.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yx6biSVote", "reviewer": "Reviewer_7U2N", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a structured variant of the multi-armed bandit (MAB) problem in which arms are grouped into known clusters. The key assumption is that the mean rewards of arms within a single cluster are constrained to be within a known threshold. The authors first establish a regret lower bound that improves upon the classical result of Lai and Robbins (1985). Building on this, they propose Clus-UCB, an algorithm specifically designed to exploit the clustering structure, which asymptotically matches the new lower bound in most cases. The paper then provides empirical comparisons against KL-UCB and two versions of a Two-Level Policy (TLP). The results show that Clus-UCB consistently outperforms KL-UCB, while TLP occasionally achieves better performance on certain instances. Finally, the authors examine robustness under misspecified cluster widths and discuss the limitations of their approach.", "claims_and_evidence_yn": "No", "claims_explanation": "## Introduction\n\nThe introduction is lacking in detail. The paper introduces a structured bandit setting where the mean rewards of arms within a cluster are constrained to lie within a known threshold, and proposes an algorithm to solve this efficiently. However, if a new problem formulation is introduced, the paper should more clearly justify why this setting is needed and how it differs from existing dependent-arm formulations. Currently, there is insufficient explanation of what structured bandit problems already exist, why they are inadequate, and why a new formulation is necessary. A direct comparison with prior work, particularly Pandey et al. (2007), is essential—if their setting is a special case of the current one, then the differences should be spelled out both conceptually and mathematically, including a regret comparison.\n\nThe literature review is also too thin. For example, relevant works such as [1], [2] should be included and discussed.\n\n[1] Singh, R., Liu, F., Sun, Y., & Shroff, N. (2024). Multi-armed bandits with dependent arms. Machine Learning, 113(1), 45-71.  \n[2] Gupta, S., Chaudhari, S., Joshi, G., & Yağan, O. (2021). Multi-armed bandits with correlated arms. IEEE Transactions on Information Theory, 67(10), 6711-6732.\n\n\n## Analysis  \n\nThe theoretical analysis is restricted to Bernoulli bandits, and the paper states that \"we believe this can be extended to the exponential family.\" This claim needs stronger justification. In multi-armed bandit theory, analyses are typically developed for general reward distributions with finite variance, not just Bernoulli, so the current restriction makes the contribution appear less general.\n\nThe paper claims that the regret lower bound is improved, but it does not explicitly restate the original classical bound for direct comparison. A clear side-by-side comparison with the classical Lai and Robbins (1985) bound would make the contribution much clearer. Additionally, the proofs appear to rely heavily on existing frameworks (e.g., Graves & Lai (1997)), so the novelty of the analysis should be clarified. It is natural that imposing a stronger structure would reduce regret, so the precise technical innovation needs to be highlighted.\n\n##  Experiment  \n\nThe experimental evaluation is significantly underdeveloped. The experiments are conducted only on very small-scale synthetic problems (e.g., two clusters with six arms in total). This is insufficient to demonstrate robustness. Larger-scale synthetic experiments—with many clusters, varying levels of overlap, and broader parameter regimes—are needed to support the claims.\n\nMoreover, the simulations assume that the cluster widths ($\\beta_c$) are known, but in practice, this information is usually unavailable. The paper should explain how $\\beta_c$ might be estimated in real-world settings. I believe a direct comparison with algorithms that do not rely on $\\beta_c$ is unfair.  \n\n\n##  Writing and Presentation  \n\nThe writing style is sometimes informal and not consistently academic. There are several minor errors in spacing, grammar, and formatting. For example, the use of a colon \":\" at the end of Section 7 and Section 8 headings is unconventional.\n\nExpositional issues are also present. For instance, when introducing the KL divergence, the paper provides only a formula without explaining its meaning or intuition in words. Similarly, in Section 2.2, the notation $\\mu_c^i$ is used within formulas before it is properly defined in the text, which makes the exposition confusing.", "audience_yn": "Yes", "audience_explanation": "The work introduces a new structured bandit formulation where arms are grouped into clusters with bounded intra-cluster differences, an assumption that has not been fully explored in prior literature. This is accompanied by both a theoretical contribution (an improved regret lower bound) and a practical algorithm (Clus-UCB) that nearly achieves this bound. Since structured bandits and clustering assumptions are an active area of research, at least part of the TMLR readership would be engaged by these findings.", "requested_changes": "Please address the issues raised above. In particular, strengthening the experimental evaluation and providing a more detailed introduction would substantially improve the paper.", "broader_impact_concerns": "Since this work is primarily theoretical and focuses on proposing a new algorithm for sequential decision-making, it does not raise any obvious ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)