A Near-Optimal Best-of-Both-Worlds Algorithm for Federated Bandits
Authors: Zicheng Hu
Zihao Wang
Cheng Chen
Venue: ICLR 2026 Poster (2026)
Keywords: Federated Bandits
Mutli-armed Bandits
Best-of-both-worlds
Primary area: learning theory

Abstract: This paper studies federated multi-armed bandit (MAB) problems in which multiple agents work together to solve a common MAB problem through a communication network. We focus on the heterogeneous setting in which no single agent can identify the globally best arm using only locally biased observations. In this setting, different agents may select the same arm at the same time step, but receive different rewards. We propose a novel algorithm called \textsc{FedFTRL} for this problem and, to our knowledge, it is the first to achieve near-optimal regret guarantees in both stochastic and adversarial environments. Notably, in the adversarial regime, our algorithm achieves $O(T^{\frac{1}{2}})$ regret, a significant improvement over the state-of-the-art regret of $O(T^{\frac{2}{3}})$ \citep{yi2023doubly}. We also provide empirical evaluations comparing our algorithm with baseline methods, demonstrating the effectiveness of our approach on both synthetic and real-world datasets.

Published as a conference paper at ICLR 2026
A NEAR-OPTIMAL BEST-OF-BOTH-WORLD ALGORITHM FOR FEDERATED BANDITS
Zicheng Hu, Zihao Wang, Cheng Chen"
East China Normal University (51275902019 9, 102351 01 44 est.:eesttuuuuuueeee...o chchen@sel ecnu. edu. cn
ABSTRACT
This paper studies federated multi-armed bandit (MAB) problems in which mul- tiple agents work together to solve common MAB problem through a communi- cation network. We focus on the heterogeneous setting in which no single agent can identify the globally best arm using only locally biased observations. In this setting, different agents may select the same arm at the same time step, but re- ceive different rewards. We propose novel algorithm called FEDFTRL for this problem and, to our knowledge, it is the first to achieve near-optimal regret guar- antees in both stochastic and adversarial environments. Notably, in the adversarial regime, our algorithm achieves O regret, significant improvement over the state-of-the-ard regret of O Yi & Vojnovic 2023). We also provide empir- ical evaluations comparing algorithm with bascline methods, demonstrating the effectiveness our approach on both synthetic and real-world datasets.
INTRODUCTION
The multi-armed bandit (MAB) problem is one of the most fundamental settings in online learning- Motivated by the emerging paradigm of federated learning in which multiple heterogeneous agents collaboratively train model without sharing their raw data (Kairouz et al.) 2021), many recent studies have explored MAB problems in federated environments. In the federated bandit problem, the goal of all agents is to identify globally best arm, and each agent can only observe locally biased rewards without sharing its raw data with others.
Federated bandits arise in many real-world scenarios where each agent's sequence of arm pulls and outcomes is kept private. For example, in a personalized online education system, optimizing a stu- dent's performance (i.e., rewards) often requires tailoring instructional methods (i.e., arms) to the student's 's individual characteristics (Cai et al.) (021). Given that educational software often operates locally on students' devices, essential for the central educational platform to personalize learn- ing experiences effectively while maintaining strict privacy constraints. Specifically, the platform should adapt tcaching strategies based on each student's unique context without collecting sensitive personal attributes performance data.
In the federated bandit problem, there are agents, each selecting one of K arms in each round. caarooenneit-inndueee locally biased reward for the chosen arm and com-
Each agent observes municates solely with its neighbors. The agents collectively aim to identify the globally best arm and maximize the group's 's cumulative reward, without sharing raw reward observations with one other. Prior works on federated bandits mainly focus on two settings: (i) stochastic settings (Dubey) & Pentland 2020 Zhu al. 2021 (Huang al. 2021] Shi al. 2021 Réda al. (202)). where wards are drawn from underlying distributions: and (ii) adversarial settings (Yi & Vojnovic [2023), where rewards are arbitrarily chosen by an adversary. However, in practice environments are sel- dom purely stochastic or fully adversarial, and their precise nature is often unknown. Despite this, the existing literature on federated bandits continues to adhere the traditional distinction between stochastic and adversarial settings.
"The corresponding author

---

Published as a conference paper at ICLR 2026
Settings
Algorithms
Individual regret
Cossip.UCB (Zuu et al.
2021
0 Σ kotk"
log 7
DRRB-bandit Zhang et al.
2025
0 E VÁ2
2
Stochastic
FEDFTRL (Ours)
log T 0 Σ kxnkk Våz
Lower bound (Zuu al.
2021
Iot 12 E Enyka V'F
FEDEXP3 Yi & Vojnovic 2023)
O( Of log K K & TT)
Adversarial
FEDFTRL (Ours)
O(v VCFT log K)
Lower bound Yi Vojnovic 2023
2 [[xxx {
KT V
Itdmax Av-1(dz)
Voo K})
Table 1: Overview of best-known regret bounds for federated bandits. Here, P denotes the doubly stochastic communication matrix over the network G, and (P( is its second-largen sin- gular value. We define C.P == min((og(VT)..VV) + 2 + D, where is the diameter of G, capturing (P)
the dependence on the network topology. Let M denote the Laplacian matrix of G; 22(M) is its eigenvalue, and dmax is the maximum node degree in G.
In this paper, we study rest-of-bott-worlle (BOBW) algorithms for federated bandits, i.e., methods that achieve near-optimal regret bounds in both stochastic and adversarial regimes. We propose (FTRL) framework for federated bandits, which in-
variant of the corporates novel communication scheme. Since each agent can only communicate with its neigh- bors in each round, information from agents beyond the immediate neighborhood is received only after multiple rounds. We regard the resulting latency as form of feedback delay. Based on this idea, we develop our algorithm by adopting a hybrid regularizer (Zimmert & Seldin 2020 Ma- Isoudian al. 2022) for bandits with delayed feedback and introducing novel learning-rate sched- ule. Additionally, to address the interogeneity-inducce loss estimator that ensures the action probabilities of each agent remain nearly aligned and keeps the aggregate loss estimator at each time step closer to the cross-agent average loss.
feedback, we introduce novel truncated
Another technical contribution of this work is a novel analysis of individual regret. Unlike prior studies on multi-agent bandits that directly analyze each agent's regret, we first establish upper bound on the group regret. Leveraging the fact that agents' action probabilities are nearly aligned, translate the group-regret bound into per-agent regret bounds that scale approximately as 1/V (up to small error terms). This approach allows us to obtain near-optimal individual regret bounds in both stochastic and adversarial regimes.
To keep the presentation simple, we assume that there exists a unique best arm k", Our method can be generalized settings with multiple best arms by leveraging techniques from Ito (2021b). The regret bounds of our method, along with comparisons to recent works, are presented in Table Our contributions are summarized as follows:
We provide an anytime near-optimal federated bandit algorithm, called FEDFTRL, log which achieves an individual regret bound of O [ ke VA, I. log the stochastic regime and simultancously achieves an individual regret bound of
Cf in
AF + log K in the adversarial regime. Here, Cff, defined in equation 2
(V KT 1
captures the topology of the communication graph. To our knowledge, FEDFTRL is the first method to achieve a BOBW regret guarantee in federated bandits, and its individual regret bounds match the corresponding lower bounds up to low-degree polynomial factors.
In the adversarial regime, prior work Yi & Vojnovic, 2023) achieves O(T3) regret bound, whereas our method achieves tighter O bound.
2

---

Published as a conference paper at ICLR 2026
We conduct experiments both synthetic and real-world datasets to demonstrate the ef- fectiveness of our method. The empirical results show that our algorithm significantly outperforms prior approaches.
RELATED WORK
Federated bandits. In the stochastic setting, Dubey & Pentland (2020) and Huang al. (2021)
studied linear contextual federated bandits and extended the classical Lin algorithm (Li et al.
2010) to the federated environment. [Shi et al. (202T) formally defined the federated bandit problem and proposed optimal algorithm for centralized communication network. [Zhu et al. (2021)
were the first to study federated bandits decentralized network, applying efficient gossip-baser communication achieve near-optimal regret bound. Recently, ZZhang et al.] (2025) proposed fully distributed online consensus estimation approach and integrated it into a distributed successive climination algorithm, achieving an optimal regret bound. In the adversarial setting. Yi & Vojnovic (2023) were the first to formalize federated bandits without stochastic assumptions on the rewards, termed the doubly adversarial bandit problem. They also proposed FEDEXP3, which achieves sublinear regret of order OTT 8) in this setting.
Seeoof-Booh-oorteeee Worlds. Traditionally, stochastic and adversarial environments have been studied independently. However, in practice, the nature of the environment is often unknown or may vary over time. This has motivated increasing interest algorithms that perform well in both stochastic and adversarial settings, a paradigm commonly referred to as BOBW (Bubeck & Slivkins 2012 Auer & Chiang, 2016 Seldin & Lugosi 2017. Wei Luo 2018). Zimmert & (eldin|(002] applied a Tsallis-INF regularizer within the FTRI. framework to achieve BOBW guarantees for stochas- tic and adversarial regimes, as well as a continuum of intermediate regimes. Leveraging FTRL's flexibility and strong theoretical properties, subsequent work has extended BOBW results to more complex settings, including combinatorial bandits (Zimmert et al. 2019 Ito 2021a Tsuchiya et al,, 2023b), linear bandits (Lee et al.) 2021] Dann et al. (003)), graph bandits (Rouyer al. [022 Ito et al. 2022), partial monitoring (Tsuchiya et al.] (2023a), and delayed feedback (Masoudian et al., 2022). Among these, FTRL variants addressing delayed feedback
Best-of-Both
particularly relevant our work, as federated bandits inherently involve implicit delays due to decentralized communication. Our algorithm builds on this line of research, adapting the FTRL paradigm accommodate both heterogeneous rewards and decentralized communication while preserving a BOBW guarantee.
PRELIMINARIES
Let (1,2,.... V) and [K] 21, K} denote the sets of agents and arms, respectively. The network of V agents is represented by a simple, connected, undirected graph G = ([V], E), where E is the set of edges. The diameter D is the maximum shortest-path distance between any pair of nodes in G.
We consider heterogeneous multi-agent system which all agents collaboratively solve common K aarmedd bandit problem over horizon of I' rounds. At each time step & [7']. each agent selects an arm ky, according its own strategy and then observes the locally biased loss of the chosen arm, & (ke,)) E [0, 1). where (k))( denotes the loss of arm & for agent at time t. The average loss of arm at time is defined as the average loss across all agents:
V
te(k)
Σ
(k.e()).
V
At the end of each time step t, each agent exchange information with its neighbors A((v) {u E [V] (u, E E). The received information can be used the next round if desired. The communication process is characterized by matrix P [0, V) where Pu,- 0 whenever u * v and (u, v) g E (i.e., agents communicate only with their neighbors). We assume that P is doubly stochastic, i.e.,
Σ Pu.p = ME[V]
Σ DE[V]
Pa.e
Pu.e 2 0.
3

---

Published as a conference paper at ICLR 2026
We consider both adversarial and stochastic regimes with heterogeneous feedback across agents. In the adversarial regime, for each round t and agent v, the losses (x are fixed in advance by adversary (before the game starts) and may differ across agents even for the same arm. In the stochastic regime, for each agent-arm pair (v, k), the sequence (k))(k)) drawn i.i.d. over time from unknown distribution with mean juy, (k))),(k))]. The performance of each agent is evaluated by its individual pseudo-regret:
RT(V)
E
Σ 2e(keee)
min E KE[K]
Σ e (k))
We define the globally best arm (in expectation) as k" E arg min IE Ei= (x(
Notations.
We denote the K-simplex by A {a E RR : F + RU {+oo}, let F* denote its Fenchel conjugate and F its conjugate restricted to the simplex, i.c.
||>|| = 1}. For a convex function
F" (*(()= max (ax, v) F())), F(()) = max (1x, v) F(x)). ZERR
ZEAR
We denote by d, [v) the degree of node v, and by dmax max de the maximum node degree in the graph. For matrix B, we use (B) to denote its i-th largest singular value. For a real symmetric matrix B, we use AB( denote i-th largest eigenvalue. The dynamics of consensus averaging among agents is typically characterized by the (unweighted) Laplacian matrix M of the communication graph G, defined as:
du uf=
Ma
-1 uu and (u,v) E, otherwise.
4 ALGORITHM
In this section, we propose our FEDFTRL method for the federated bandit problem. The details of the algorithm are presented Algorithm [ One challenge in federated bandits that messages from other agents arrive with delays that depend on the network topology. This scenario can be regarded as a bandit problem with delayed feedback. Motivated by this idea, our FEDFTRL algo- rithm adapts the FTRL framework using hybrid regularizer, following prior work on bandits with delayed feedback (Zimmert & Seldin 2020; Masoudian et al. 2022). We present the regularizer used in FEDFTRI as follows:
K
(x(x: = -2m
Σ Vik
+ +
Σ
x& (log xy -1)
We introduce time-varying parameter Of to quantify the delay caused by decentralized commu- nication:
of = min min((lo((V)) VV)
+2+D,
(2)
1-o2(P)
Then we set the lcarning-res sequences (me and (rche11 as
v 169V2D, n 8V CP tolog K + 36D - 1) 4(C!))2
At each time step each agent computes probability distribution over arms follows:
VF
obe = arg min (zz Lobe F((x)}
(3)
DEAM
where P is the communication matrix and i E K is agent v's cumulative loss estimator up to time f. The agent then samples an arm k ~ Fo,t and observes a locally biased loss Ex, (ko,,)) We construct unbiased loss estimator and its truncated variant as follows:
(k,((k) = Ey I(k- kens)
(k., I(k k..t)
and (x,((k) = max(x., (k)), 12V C.T.)
(4)
4

---

Published as a conference paper at ICLR 2026
Algorithm FEDFTRL (local routine for each agent
1: Input: doubly stochastic matrix / E [0, 1]VvV; the diameter D of graph G.
2: Initialize: deviation record set A, +- 0: the cumulative loss estimator T. <- 0K-
3: for 2,2,3 ........
4: Compute Tu,t + arg millZEA-1 { (a, Lggt)) + Fx(x)).
5: Sample kin,t ~ dvut and observe l, (ho.))
6: Construct Euit and be,t by equation
7:
if (ko,t)))) # (Ku,)) then Set Wh,t + (ko,)) - -uve and append (v, l, ku,e, Wo.)) to Av. end if
8:
9:
Exchange the message { (Eghe Au) with neighbors of agent v.
11:
Update cumulative loss estimator:
12:
1
= =uun
(M,0)E Pu Lote + Vl
(5)
13:
Update the deviation record set: A, + UuEN(o)U(E) An.
14:
for each record (u, hi, Wn,a) A, do
15:
if
then
16:
Set Labe 4 (k) <- Lave v, (k) + Wa,s, and remove (u, k, Wa,e) from A..
17:
end if
18: end for
19:
end for
Before communicating with neighbors time t, agent prepares message consisting of (i) its current cumulative loss estimator Labs and (ii) of deviation records A,, A new record (v, t, ku.,, w..x) is appended to A, if and only if (ke,,)) + (ko,)), in which case we set the estimator's 's deviation W..t = (kv.e) Lv (kr.t). Next, agent averages its cumulative loss estimator with those of its neighbors and merges incoming deviation records.
4.1 INTUITION BEHIND THE TRUNCATED LOSS ESTIMATOR
One challenge in federated bandits is that the locally observed loss at agent can be biased in expectation relative to the average loss (k) of the same arm. In FEDFTRL, we address this by updating f.ohe using the truncated estimator t., instead of the unbiased estimator f This choice keeps all agents' action probability distributions nearly aligned.
Specifically, when constructing to,t we replace the denominator with (k) 12 7 which prevents the loss estimator from exploding when (k,)(k) is extremely small. As result, no single rare arm pull can trigger an excessively large update that would cause the agents' prob- ability distributions to diverge. This stabilization ensures well- behlebehhved and nearly aligned action distributions across agents.
4.2 INTUITION BEHIND THE COMMUNICATION SCHEME
Since sharing raw observations is not allowed under the federated setting, our method communi- cates deviation record set A, each round. This communication necessary to correct the bias introduced by the truncated estimator.
Specifically, while truncation keeps agents' action distributions nearly aligned, it can make the local loss estimates deviate from the group-average loss when truncation is active. Therefore, whenever (k.,(k..)) (k,,()),)) agent appends record (v, ł, ku, Wo,s) to Ag. Once record (u, 5, k, Wa,s) has propagated the network for more than D rounds (i.c., t - s > D), every agent will have ohs
received it. At that point, adding the correction Wa,s to u,t+1 (k)) no longer introduces distribution misalignment among agents.
5

---

Published as a conference paper at ICLR 2026
Finally, recall that scale the per-round feedback by factor of V in the cumulative loss up- date (see equation 5). Communication averaging drives the agents toward consensus on the group- average losses; the factor of V counteracts this averaging effect, ensuring that feedback information not overly diluted. Thus, we obtain the following regret guarantee for FEDFTRI, with the proof provided in Appendix [
Theorem 1. If FEDFTRI. is run with given doubly stochastic communication matrix P. then in the adversarial regime, the individual regret of each agent u bounded by
RT(c)= & KTVK + 13 ogg K 156V + 72D(K - 1)$ log K + +24CT log K.
Furthermore, in the stochastic regime, the individual regret of each agent v is bounded by
T
90CT
RT(E) S Σ
Σ
DS log 56D 56Dv log K -11C log K.
VA
Moreover, for each agent v, the expected communication cost per round is O(K).
Remark 1. If the doubly stochastic matrix P is constructed via the max-degree trick (Duchi al. 2017, ie.,
W 1+ 1+
P
where W diag(d .2.....dy) is the degree matrix and the adjacency matrix of the commu- nication graph G, then Corollary I of Duchi et al. (201T) implies that
CT = = (
1 dmax
Xv- V (iin vV})
This result shows that only low-degree polynomial gaps remain between our upper bound and the lower bound Ω maxt
KT
I+dmas (AT)
Volog K}) in the adversarial setting.
5 A SKETCH OF THE PROOF OF THEOREM
this section, we provide a proof sketch of Theorem D We present proof sketches for the regret bounds in the adversarial and stochastic settings in Section 5.1 and Section 5.2 respectively. The detailed proofs are provided in Appendix 12
5.1 ADVERSARIAL BOUND
We start by stating key lemma (Lemma) I that controls the ratio between the action distributions of any two agents at the same time step, whose proof is provided in Section [T in the appendix. This lemma also relates each agent's individual regret to the group regret, i.e., the sum of regrets over all agents.
Lemma 1. For any two agents u and v, and for any arm at time holds that
(k) (k)) and (k,((k) S (k).
Furthermore, for any agent v, its individual regret is bounded in terms of the group regret as
Rr(v)
3 2V
Σ ER(u).
To bound the group regret, we transform the federated bandit into single-agent interaction with the environment over VT rounds. This reduction significantly simplifies the theoretical analysis. We introduce some additional definitions. Let the instantaneous loss estimator be
my ==
1=

---

Published as a conference paper at ICLR 2026
and define the shifted cumulative loss
Le Vmg + (v - 1)m-
Since have E/me] tional to (o - 1). This ensures that when we sum over all agents, the instantaneous loss estimator
Lu, can viewed shifted cumulative loss with an offset propor-
my line up if they were incurred sequentially by a single agent over VT rounds. As a result, can decompose the group regret into three terms:
(U)
E
vv,) [c(k*))
1=1
FM(
iobbe
m²) Pi( i.obe) + (Ioee mi)
(A)
PT(( (
P.t(
i mm)) -F(( Li,s) Fil - Lmv1,))
[=1 t=1
(B)
V
F - t.,,) - Fi( - buti,)))) [k))41(k*))
Term (A) is typical pends on the local norm induced by the regularizer. We can bound as
term arising from the FTRL/OMD analysis, and it de-
T
B[(A)] S
VVKT.
32
16
Term (B) is handled by the analysis in Zimmert & Seldin 2020
which yields
E[[
<
9 v
Σ
T
C log K
9
V V TT K.
32
16
Term (C) can be bounded using standard telescoping-sume techniques. In particular, we obtain
B[(C)] SVVKT + 8V V CfTlog K 104V 4SV 1) log K + 24V Cf log K.
Combining the bounds for (AH(C) above and simplifying completes the proof of the adversarial bound.
5.2 STOCHASTIC BOUND
Inspired by the analysis of stochastic bounds for bandits with delayed feedback in Masoudian al. 2022). let R..t V (-in,,). We then define the drifted pseudo-regret as
T
(Év,e Z.) - Z, Z((k))) )
Rdrift (v) = E
We can use the drifted pseudo-regret to control the group pseudo-regret follows:
V
Σ
(T(v)= <
5
Rd
Rdrift
(v) +VD
3
==1

---

Published as a conference paper at ICLR 2026
T V
5
5 (k)
5
T
V
K
C
n- 1n-18,,1
log (
4vVt
log K
1=1 0=
1=2
1= k=1
(4)
BB)
+ 37V (K 1) log K + 7VC log K + VVD.
(C)
Self-bounding analysis: We apply self- bounding technique to combine terms (A) and (B) with the drifted regret. Specifically,
5
(T(2)=
Reri
(o))s(())))))))({ +VD
3
V
5
(((A)
Rd (drist(u) +
Σ
Ry
Rdrif(())
(v) + (C).
3
1=1
o=1
Using the analysis in Masoudian al.
(2022).
have
3(A) Σ (
(v)
81 log T
3(B)
Σ
Edrist
36V Cf An log K
4
o=1
Combining these bounds with (C) and simplifying yields the stated stochastie regret bound.
EXPERIMENTS
We conducted experiments on both synthetic and real-world datasets under various network topolo- gies to evaluate the performance of FEDFTRL against several baseline methods. We consider the following basclines: FEDEXP3 (Yi & Vojnovic 2023), GOSSIP UCB (Zhu et al. (2021). DRBB- bandit (Zhang et al., 2025), and IND-FTRI, where IND-FTRL denotes running I'salli-FTRRL. (Zim-) mert & Seldin| (021) ) independently at each agent without communication. Following the experi mental design in Yi & Vojnovic (2023). we adopt the max-degree trick to construct the doubly stochastic matrix P, described Remark [ We set the learning-rate schedules of FEDFTRL as
" 0.1 /Vt and 7/ 8V /CFt/ log K. All experiments are repeated for 50 trials, and we report the average results as lines.
Choice of the network graphs. We conduct experiments on several network topologies, including a fully connected graph, a VV x V grid graph, and a random geometric graph (RGG). An RGG- g is constructed by uniformly placing each node in [0, 1]2 and connecting any two nodes whose Euclidean distance at most (Penrose) 2003). In our experiments, we set g = 0.5.
6.1 SYNTHETIC DATASETS
For each agent v and each arm k we independently sample mean loss Pa, uniformly from [0, 1]. When agent v pulls arm k at round t, we draw the feedback (k,(() from a Gaussian distribution (( 0.01) and clip the number of arms K 20.
[0, 1). We set the horizon 3000, the number of agents 16, and
The results in Figure show that FEDFTRL outperforms all baselines in terms of average regret. Notably, IND-FTRL. cannot achieve sublinear regret when only observing locally biased feedback, highlighting the benefits of communication in our method.
6.2 MOVIELENS DATASET: RECOMMENDING POPULAR MOVIE GENRES
We further evaluate FEDFTRL real-world dataset: the MovieLens dataset (Cantador et al.) 2011). This dataset contains 87,585 movies classified into 20 genres, with 32,000,204 ratings (scores in (0.5, 1,..., .)) from more than 280,000 users. Among these users, 3,963 have rated at least one
8

---

Published as a conference paper at ICLR 2026
FedFTRL B
FedExp3
Gossip_UCB
DRBB-bandit
IND-FTRL
282
1.0
Averege Regret
0.8
0.8
0.8
0.6
0.6
Bverr
0.4
0.4
0.2
0.2
0.2
0.0
1.5 Rounds
2.0
2.5
0.0
1.0
1.5
2.0
0.0
0.5
Figure 1: Average cumulative regret of FEDFTRL, FEDEXP3, IND-FTRL, GOSsIP JCB, and DRBB-bandit the synthetic dataset under three communication networks: (left) complete graph, (middle) grid graph, and (right) RGG-0.5.
152
1.0
1.0
Average Regret
0.8
0.8
Averags Regret
0.8
Avcrage
0.4
0.4
0.4
-0095
0.2
0.2
0.2
000
0.80
0.600
163
Figure 2: Average cumulative regret of FEDFTRL, FEDEXP3, IND-FTRL, GOSsIP UCB, and DRBB-bandit the MovielLens dataset under three communication networks: (left) complete graph, (middle) grid graph, and (right) RGG-0.5.
movie in every genre; we select these users as our agents and treat each genre arm. We set 3000, V = 3963, and K 20.
To simulate changes in user preferences over time, we sort each user's 's ratings in chronological order and construct loss sequence as follows. Let (k) the j-th rating of user for genre this sorted order, where j {I,....nkt)
...). The loss for user e on arm la at time is defined as
5.5 (k)
T Tu
T n
)
(k)
for te (j
5.0
where n is the total number of ratings user v has for genre k. In words, we partition each user's interaction timeline into n segments of equal length, and assign the j-th rating (k) as the loss (scaled Jo, 1)) for all time steps the j-th segment for that user-gemt pair.
As shown in Figure 2 FEDFTRL significantly outperforms all baselines, demonstrating its effec- tiveness on real-world data.
6.3 SENSITIVITY TO THE TOPOLOGY PARAMETER
We study the sensitivity to the topology parameter C.'. We keep the experimental setup identical to that in Section and only rescale C₁ by multiplicative factors of 0.1, 0.5, 1.0 (default). 5, and 10. We denote the corresponding variants by FEDFTRL-C, where E is the scaling factor. When = 1.0, Cf is unchanged and we simply write FEDFTRL.
The results in Figure and Figure show that FEDFTRL is robust to the choice of the topology parameter C.P. Even with misspecified Cf, our method still achieves sublinear regret.

---

Published as a conference paper at ICLR 2026
FedFTRL
FedFTRL-0.1
FedFTRL-0.5
FedFTRL-5.0
FedFTRL-1000
2.0 101
2.0 101
2.0 1e1
Veerogg Regret
Averooe Regret
1.0
1.0
0.51
0.5
0.55
0.00 0.
0.3
1.0
1.5 Rounds
2.0
2.5
3.0
0.0
0.5
1.0
1.5 Rounds
2.0
2.5
3.0
0.000
0.5
1.0
1.5 Rounds
2.0
2.5
3.0
163
163
163
Figure 3: Average cumulative regret of FEDFTRL, FEDFTRL-0.1, FEDFTRL-0.5, FEDFTRL-550. and FEDFTRL-10.0 on the synthetic dataset under three communication networks: (left) complete graph, (middle) grid graph, and (right) RGG-0.5.
2.0
2.0
2.0
Averoge Respet
1.5
1.5
Rearet
1155
1.0
1.0
11.0
000
0.80
0.000
Rounds
163
Figure 4: Average cumulative regret FEDFTRL, FEDFTRL-0.1, FEDFTRL-0.5, FEDFTRL- 5.0, and FEDFTRL-1000 the MovieLens dataset under three communication networks: (left) complete graph, (middle) grid graph, and (right) RGG-0.5.
CONCLUSION
this paper, we propose a novel federated bandit algorithm, FEDFTRL, which, to the best of our knowledge, is the first achieve BOBW regret guarantee in both stochastic and adversarial set- tings. Our thcoretical analysis shows that our regret upper bounds match the corresponding lower bounds up to polynomial factors. Furthermore, empirical results corroborate strate the superior performance of our algorithm. An interesting future direction is to further narrow the remaining gap between the upper and lower regret bounds in the adversarial setting.
theory and demon-
ACKNOWLEDGMENT
The authors would like to thank the anonymous reviewers for their helpful comments. Cheng Chen was supported by Natural Science Foundation of China (No. 62306116).
REPRODUCIBILITY STATEMENT
We provide complete proofs for all theoretical claims the appendix. To facilitate reproducibility. include the source code in the supplementary material. We use the MovieLeng dataset in our experiments, which publicly available.
REFERENCES
Jacob Abernethy, Chansoo Lee, Ambuj Tewari. Fighting bandits with a new kind of smooth- In Advances in Neural Information Processing Systems, volume 28, 2015.
10

---

Published as a conference paper at ICLR 2026
Peter Auer and Chao-Kai Kai Chiang. An algorithm with nearly optimal geeudo-regret for both stochas- tic and adversarial bandits. In Conference on Learning Theory, volume 49, pp. 116-120. PMLR, 2016.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference Learning Theory, volume 23, pp. 42.1 PMLR, 2012.
William Cai, Josh Grossman, Zhiyuan Jerry Lin, Hao Sheng, Johnny Tian-Zheng Wei, Joseph Jay Williams, and Sharad Goel. Bandit algorithms to personalize educational chatbots. Machine Learning. (00-2399-24155 2021.
Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik. Second workshop on information heterogeneity and fusion in recommender systems (hetrec2011), 1). In Proceedings the fifth ACM conference on Recommender systems, pp. 387-388, 2011.
Chris Dann, Chen-Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In Conference on Learning Theory, volume 195, pp. 5503-5570. PMLR, 2023.
Advances in Neural Information Processing Systems, volume 33, pp. 6003-6014, 2020. Abhimanyu Dubey and AlexSandy' Pentland. Differentially-prieaa private federated linear bandits. In
John Duchi, Alekh Agarwal, and Martin Wainwright. Dual averaging for distributed optimiza- tion: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57: 592-606, 2011.
Saghar Hosseini, Airlie Chapman, and Mehran Mesbahi. Online distributed optimization via dual averaging. In 52nd IEEE Conference Decision and Control, pp. 1484 1489. IEEE, 2013.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. In Advances in Neural Information Processing Systems, volume 34, pp. 27057-27068, 2021.
Shinji Ito. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits. In Advances in Neural Information Processing Systems, volume 34, pp. 2654-2667, 2021a.
Shinji Ito. Parameter- free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, volume 134, pp. 2552-2583. PMLR, 2021b.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both worlds algorithms for online learning with feedback graphs. Advances Neural Information Processing Systems, volume 35, pp. 28631-28643, 2022.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, et al. Ad- vances and open problems in federated learning. Foundations and Trends in Machine Learning, 14:1-210, 2021.
Shung-Weit Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimality and minimax-optimalit in stochastic and adversarial linear bandits simulta- neously. In International Conference on Machine Learning, volume 139, pp. 6142-6151. PMLR, 2021.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. contextual-bant bandit approach to personalized news article recommendation. In International Conference on World Wide Web, pp- 661-670, 2010.
Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. A with delayed feedback. Advances Neural Information Processing Systems, volume 35, pp. 11752-11762. 2022.
algorithm for bandits
Mathew Penrose. Random geometric graphs. Oxford University Press, 2003.
Clémence Réda, Sattar Vakili, and Emilie Kaufmann. Near-optimal collaborative learning in bandits.
In Advances in Neural Information Processing Systems, volume 35, pp. 14183-14193 2022.

---

Published as a conference paper at ICLR 2026
Chloé Rouyer, Dirk van der Hoeven, Nicolò sot-ooffoothwoorlde algorithm for online learning with feedback graphs. Advances in Neural Information Processing Systems, volume 35, pp. 35035-35048, 2022.
and Yevgeny Seldin. A near-optimal
Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the exp3++ algo- rithm for stochastic and adversarial bandits. In Conference on Learning Theory, pp. 1743-1759. PMLR, 2017.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, volume 130, pp. 2917-2925. PMLR, 2021.
Taira Tsuchiya, Shinji Ito, and Junya Honda. best-of-both-worlle algorithms for partial monitor- ing. In International Conference Algorithmic Learning Theory, volume 201, pp. 1484 1515. PMLR, 2023a.
Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-wond algorithm for combinatorial mani-bandits. In International Conference on Artificial Intelligence and Statistics, volume 206, pp. $117-8144 PMLR, 2023b.
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference on Learning Theory, volume 75, pp. 1263-1291. PMLR, 2018.
Jialin Yi and Milan Vojnovic. Doubly adversarial federated bandits. In International Conference on Machine Learning, volume 202, pp. 39951-39967. PMLR, 2023.
Haoran Zhang, Xuchuang Wang, Hao- Xu Chen, Hao Qiu, Lin Yang, and Yang Gao. Near-optimal regret bounds for federated multi-armee bandits with fully distributed communication. In Inter- national Conference on Uncertainty in Artificial Intelligence, volume 286, pp. 4959-4981, 2025.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Pro- ceedings of the ACM on Measurement and Analysis of Computing Systems, 5:1-29, 2021.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, volume 108, pp. 3285-32944 PMLR, 2020.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1 19, 2021.
Julian Zimmert, Haipeng Luo, and Chen-Ye Yu Wei. Beating stochastic and adversarial semi-bandiss optimally and simultancously. International Conference on Machine Learning, volume 97, pp. 7683-7692. PMLR, 2019.
12

---

Published as a conference paper at ICLR 2026
8 NOTATIONS
We define the instantancous loss estimator m, == V E buze, the cross-agent average cumulative loss estimator
T--1 =
ob v,t-17
and the drifted cumulative loss
Vm, (v 1)m4-
For notational convenience, we adopt the wrap-around convention (V 1, (1, + 1). Finally, for any x E A we introduce the inverse-curvature weights
f((
(1) A
h: E [K].
EES f(
REGULARIZER PROPERTIES
First, we analyze some properties of the regularizer
K
F((x) -2%
k
Given the function fe(x)= -22 Vz Vt' - <<lg((z)) 1).
Fact 1. f((x) is concave function, (x) is monotonically decreasing function, (x) is convex convexfunction function, and fi' is convex monotonically increasing function.
Proof. By definition fz(z) = -n x + +% log(z). whose second derivative is - 1/1 x
1/ - < which conclude the first and the second statement. ft" f((xx) 2, +
71 -11-1 so the second derivative is
1 (2n + 3yeze'
0,
2 (2 7203122
which conclude the third claim. Since ft are Legendre functions, we have f (v) (ft ()))-1= > 0. Therefore the function is monotonically increasing. Since both f (z) as well as ft (y) are increasing, the composition as well and fi 0.
Fact 2. For any convex F, for L R.K and E R:
F' + cl (L) +c.
Proof. By definition FLLL + clx) max 1(2, + clk) F(x) max (2, L) F(x) +c= (L. cc.
Fact 3. For ant Intt there exists E R, such that:
Fett VF VF (-L cla) (VF((u))))
Proof. By the KKT conditions, there exists E IR, such that Ro,t arg max max (x. f.,,a) + F((x) satisfies (F((..,)) -L,, + cl The rest follows by the standard property VF (* of Legendre F.
13

---

Published as a conference paper at ICLR 2026
Fact 4. For any Legendre function F and L E RK it holds that
F FL)),
with equality if and only if there exists E A A such that L (F(x).
Proof. The first statement follows from the definition, since for any A C B f() S max (xx). The second part follows because equality means that arg max, ((x, L) F(x))
VF (L) E K-1, which equivalent to the statement.
Fact 5. For any x E K-1, L L
0 and l: E [K], we have
V F (VF(z) - L))x z (VF (VF(x))) L))
Proof. By Fact 3 there exists
R such that (VF((((( - L) = (VF(((( L +
clg) ). The statement is equivalent to being non-negative, since F? are monotonically increasing.
If c < 0, then
Σ
P (V -1));
K
- L+ =+ = F (F((z)) - Lx + c)
<E Fr (F/()x))
which is a contradiction. Hence e must be non-negative, and the proof complete.
Fact 6. Let DE (z. y) F(x) F(y) (z y. Fy))) be the Bregman divergence function
F. For any Legendre function f with monotonically decreasing second derivative,s E (fm(f), and
2 0, such that f'(xx - E dom(f") we have
&
(--(f()) s 2z'
f Proof. By Taylor's theorem, there exists some 3 [f x), such that
D7-() 2f
Note that 5 is smaller than x, since f is monotonically increasing. Finally, using the fact that the second derivative is decreasing allows us to bound
Hence the stated inequality follows.
Fact 7. For any convex function F, and L2 L1 (coordinate wise), we have
F*(-nn) 2 F- (-I2)-
Proof. We have
(-(-122 (VF ((VF
VVF (1) +F(FF((LLa)
< max zEAK-1
(x,- -1) + F(#))
F F- (-L1).
14

---

Published as a conference paper at ICLR 2026
10 AUXILIARY LEMMAS
In this section, we present several preliminary lemmas that will be used the subsequent proofs. Lemma 2. For any time step and agent v E [V], we have
IL - Logell 10 ||
Lelloo S
1
12%
Proof. As mentioned before, updating with deviation records does not affect [T, all agents perform this operation. Hence, only consider the impact of equation 5
Lobel loaos since
We first record a simple bound that holds for all v, t:
(koa) el max(x (k.,.) 12VCpx) S 12VC. n
Since { is non-inereasing, applying Lemma in Hosseini et al. (0013)
with L = T20 yields
VV
11, igbe 1l S 120,7 n ( 02(P) +2)
(6)
Following the definition of L,, we have
t- v
v Σ
|| 1 iuby 1110 = V
1k/V Pt las +
Eut - Eois
V
==1
V
| - -pt-stl
1 Bu,ello
8=1
u=1
pp- 1x 1x/V|| + 12C
120 ?t
From (23) in Duchi et al.
2011), | 1x/VIl S vV (P()) Hence, if
log(c-1)
s
(Pg(
then
||-=+t 1 VVc.
Setting e- Vt, for 1+12
(Vg(V log(o2(P) 1y obtain
pl--+11 1k /V1l S E.
(8)
For the remaining terms, we simply use sum at
pt- - 1 1 1VIl S 1. The above suggests splitting the
log(V/) (P) 15. Using equation
7 and equation 8 we obtain
lot)
I -
Jobs oit
lloc <
12CP 7t. log( log(o)(P)-1) +2 <
The last inequality follows since (og(o2(P)-)) 2 1 (P). Combining equation 6 and equation completes the proof.
Lemma 3. Fix f and let (FT(-Tn) and x2 that
V (T2)- For any arm k: [K] assume
K
Σ
(alr) (La(1)-L1()) (i))
_
L (k) L2(k) -
02
7t
%
where 01,02 [0, Then
<
a1
02
15

---

Published as a conference paper at ICLR 2026
Proof. Let P1, (2g be the KKT multipliers associated with the simplex constraint, that for all ? E [K].
f(x = (1) + -M1 f((z)) = - + u2.
Since ft is concave (Fact I for every i E [K] we have
(si 2/2) (x1) - f((x1) - f((xa) S (z) x52 fr (x²))
(10)
Using the left inequality in equation and ft" (x1) yields
ij 2 S (z 1 (m| μ2 + L2(1) - Li()).
Summing over i and using
Σx= 2 = E x2 = gives
c x22) v Σ 84 (x -1 (1r 122 + Tz((t) In(i);
and hence
DE (x1) (L2())) - L1) プラ= (z
K (l(e
- (12(1)- < Q1
n2 M1 <
(11)
7
Next, applying the right inequality in equation 10 with k and using f((xb) - f((2f) = 442
A4 L1 (k) (k),,, we obtain
(at x ft (x S 122 - P1 + [k) - L2(1:).
Therefore, by equation
II and the assumption L (k) L2(k) S a2/
22 S क + (x (M2
11 + La (k) L2())) [11 (-= =02)
(12)
$ . + ft (x
Finally, using the structural bound [1) S yoo (which holds for our choice of ft), we have (w I xre and thus
2/2 S xt + (01 02)) x
which rearranges to a S 1-a1-a2" r1
11 PROOF OF LEMMA I
Proof. By Lemma 2 for any agents u,u [V], we have
1
i 1lo0 S ioos T.eloo 1Te i.ghe 11 6%
Consequently,
(Lohe Lobe (i)) < Moreover, for any le E [K].
p (Fv,e) 1| - Lobell 11
-1
Lobell
11
1
67
obs (k))
i. o.s (k)) S iipte
i.obs 11 =I ||
i 1o0 S
B
Applying Lemma 3 with 022 yields
3 k
2 u.t.
Swapping the roles of and gives the reverse inequality
3 k
2
which completes the proof.
16

---

Published as a conference paper at ICLR 2026
12 PROOF OF THEOREM 1
12.1
LEMMAS
Lemma 4. Fix any agents u, V E [V] and time indices s, [2]. Suppose there exists a constant 2 such that (ka(k) S ( for all k E [K]. Then,
K Σ (.
K
S Σ
pl (a s 2a(K - 1)3.
Rmm
Joml
Proof. Now we aim to bound:
Σ Pr (k) f" (Zev -2 In ( (uion
Ex=1 f" (xt,))-
(Zuze 2 Nv (Kin,))) (I (ku,)))))) s/ /u
km f" (xb
1 (Wuss(ku,s)) Fet (kuns))
ΣK (1(1))
af (Zo,e 1) 11 Iz, (ku.e))
Define = (Fun()
(K - 1)f" (
(ku,) K-1 ) + f" (x (ka,)))-
an7 2 3/2 3 27;²"
211)-12-1
(K - -1)(m (((m=((k))
(1-2
-
3/2 + 2% ( K-
1-1) -1 (112-3/1 3/2 + 1-1-1-11 2-12)-111
1/ 1 112 1/2 + 2%
=a 1a(11 The VK 1(1 - 2) + +
+
(13)
where the first incquality follows by u s 1, and the third inequality is due to convexity of f" (x) from Fact Now for z we have two cases, z K and 2 2 k
1: K: a) 2 S
This case implies
1
1- 2
-1
1/2 2) 1/2 11/2 VK S -1/2
2
-1 -12 1/2 + 271
11
(14)
11 VK K 1(1 2) 2%
Plugging equation 14
into equation
13 gives us
Σk I" ((rtt) -h
<a(1-2+2)
K (x
b) = 2 : Similar to previous case 2 K
implies m/:" 1-12 1) VK -1
1/- 1/2
so the minimum
(K- -x2-(11))-1/24235 occurs when 27, = 0. So substituting
2% 1 = 0 in equation 13 leads us to have
EK 1" (xtt)) (en
Sa ((112))//2--11)) 1/2 - 11) =)-
(15)
EK f" (xt,)))
In this case again we have two following cases
b1) 2 (--1)1197. With this we have
a(1 ((112))3/2 -12 ((1-=)))2--11(((11--- 1122+2) s -z <V a (KK -6 (1)1///++1) +1) <
22o(K-1)1/
17

---

Published as a conference paper at ICLR 2026
b2) 2 5 (K- (K-1)=441* This tells us that (1 1 2) 2 1/3
2 1/2
where we can use it in
(K (1-177341
equation 15 as the following
(1 2)3/22 2/3/22-112111 (K 11) 1/22 +2
1/2 11)
S <a(
+ +2)-1
V8
a( 2 1/2 1/2(K - 1) 11111/2 1/2
+ 1/1 - 1)-
+ +2)
2v8
2v8
a (K - 11-1 / & - 1)2/3
3
32
where the second inequality uses AM-GM inequality.
So at the end combining results of all cases to complete the proof.
Lemma 5, Fix any time indices 8, t E [T] and a loss vector E TRKK Let
I1 (-)(-)),
22 (-(L-)..
If& S D, then for every arm & E [K],
5 2 v 4 #1
Proof. Since 11 (- and 32 V (- L), by the KKT conditions 3/1, 182 S.t. Vk:
((at)) I.(k) + pı. (((5)) - -T(()) + 122
We also know that 3 k: at 2 z which leads have
- L(k) + μ2 = (x (((t) S = - + pin
where the first inequality holds because the learning rates are decreasing and the second inequality is due to the fact that (x) is increasing. This implies that μ12 S μn which gives us the following inequality for all k:
f.(1)) =
+ 7
log(xz)
I
+ %. log(z))= = (x4))
T /
1/2
1/ /
x
Define 8 = 2//// / So using above inequality have
1
1
E 7o
log(at)
Te log(at)) - 7t log(B)
7/
1
1/t
+ 2
lotlog( V x)
1/1
+ log(3)
V
v3
7
7t
7/a
7
17t
+ min
2z log()
1/t
7t
+ log(8)
7
0<
9/t
?'s
76
(a)
2
T1t
74
e
7
VB
(6)
17c
17t
77
17
VB
18

---

Published as a conference paper at ICLR 2026
where (a) holds because the subject function of the minimization problem is convex and equating
the first derivative to zero gives G t and (b) follows by Ta 2 1. So rearranging the above result gives
2
7E
B <
(16)
7/t
7t
7
Therefore, we have
4v + 1
V(t s)
1
3
4/
4v 169V"D
169V2D
169
where 21,D2 1 and - 2 D. First, we give an inequality
V + Vy- V =2v20, a a20
We square the left side:
= o
By this inequality, we have
2
(
11t
2
2V 2V
Vvt-s
4
7t
7s
Vt++ 169V
13V VD
13e
Plugging the above inequalities gives us the following bound:
4
5
B
1+
169
13e
Lemma 6. For any time index S t D and any fixed arm k E [K]. it holds that
Fu S 2x 2
k
Proof. First, we decompose obs into the following two parts:
Lobs
Lobs Lo,i
Lo 2e,tt1-0
where the former represents the cumulative loss estimate observed by agent v from time step 1 to s, and the latter is the cumulative loss estimate from time step + 1 to
Using the same analytical method in Lemma
we can obtain:
|
11
Lohe -o,1-sllo> S || Lullo [[, Lobs 1 S 6%
(17)
Where the first inequality because that Lada + (k))
(6)2 0.
Using Lemma 2 for any fixed l we have
t-D
jbs Lohr- (k) - i obs (k) S V
Σ
m²(k) + || - Tobs
(k)
f=e-D
(-D
min(vV, log( (P)
S V Σ
mi(k)
+
(18)
12C,
i=--D
Where the first inequality because only the deviation generated in time period [s D,t D] will be used in (k)..
By Lemma and mathematical induction, we have
(-D
v
K A (1 s WDD(-113 (19)
ΣΣΣ 11
(m,K))
S
ΣΣ i=s-
19

---

Published as a conference paper at ICLR 2026
Furthermore, we have
[-1 V
obs v,+ - (k) V
pt-f-1 0,0
1 (k) + ( <
D
(20)
120
i=a+1 ==1
Combine equation
18,
equation and equation 20
complete the right statement
K Σ
pf uu ) (I)) L (k))
k
K
Σ
pe (In,,)) (Lgh ( +
Σ
pe (Iu,s) Lobs
k=1
min log(V[))
+2 + D) 4V - 1)
12C, y
1_)2(P)
6%
Where the last inequality uses the fact
7 = 8V / K + (K 1)2/3 + 4(CP)2 2 L8VD(K - 1)
Using Lemma
3 and Lemma 5 we can complete the proof:
1
us S 2x
Lemma 7. For any time index = t D. any agents u, [V] and any fixed arm k [K]. Define
Fa,
Then, for every arm & [K].
5
gek
3 u.st
Proof. First, we decompose ibo into the following two parts:
Lobe = Lobe + obe 0,5t1-
where the former represents the cumulative loss estimate observed by agent from time step 1 to s, and the latter is the cumulative loss estimate from time step + to
For any arm A [K], using the same analytical method in Lemma
obtain:
1
Lu (k:) - Lohe (k) < LI..+1 (k) obe (k) S L. (k) Lobe (k) <
(21)
127x
The first inequality uses the fact that Lohe (k) 2 0 for all & E [K].
Using Lemma 2 for any fixed &s have
L obe (k)
Lk,) (V - (k) + Lobe ( L L1,
min VV, log( Vt)}
(k) 12CP Yt
(P) +2
(22)
By Lemma we have
K
(m,)))
ΣΣ
Σ
(k) 4V(K 11
(23)
20

---

Vo,(()))))) Published as a conference paper at ICLR 2026
According to our update rules for deviation records, records generated in time period It D 1, will be used, so we have
obs p 11,+1 (k)
V
[-1
V
P
(k)
(k))
D
(24)
0,0
120 7t
1=0+1
Combine equation
22
equation 23 and equation 24
we have
K
Pi (Tu. (L (k) (k))
k
K
Pr &
(Tn,s) 1,,
(Lr.) ( (k)) Σ
pi (
k=1
k=1
Vonn(vV, OP)
+ +2+ D + (K
12CP n
6%
Where the last inequality uses the fact
7t = 8V
Cf
log K 36D2 1)2/3 + 4(CP)22 (8V(K-)) 1133
Using Lemma and Lemma 5 we can complete the proof:
x
1 u,
S
3 u
Lemma 8. For any round E [T], any arm ls E [K] and any two agents u, u E [V] define
j
V (- (-Lu,)
Then
u,t S 25th
Proof.
Using the same analytical method in Lemma 2] we can obtain:
|
Lu, S Lobe -1,11loo + 11 loo
min [min(vV,log(V1)) 1-02(P)
$
+2
12CPm
12CF
1
log(V))
+ + D
S
(25)
12CPT T
1 - (p))
127r
Where the last incquality comes from D 1. As mentioned before, for any fixed & we have
(k) jobs (k) <
Σ
my(k) + |
Lelloo
t=t- D
1
VV
Σ
my(k)
+2
(26)
12CP 7
1 1-o2(P)
Using mathematical analysis_ we assume that from 1 to f the lemma holds. Then using the same analytical method in Lemma 6 for any time step D < t-
obtain:
2.t < 4. -
21

---

Published as a conference paper at ICLR 2026
By Lemma 4 and mathematical induction, have
K p
i ((( <
ΣΣΣN
Σ
( S 8VD(K - 1)3.
(27)
D
According to our update rules for deviation records, no records generated in time period 1t-D+11. will be used, so we have
D
i ob D
+ (k), S
(28)
a.v
120 Y
(=
D
Combine equation
22
equation
23 and equation
24
we can complete the right statement
K
p (Eon))
Loge (A:)
min (oin(vVloog(Vt) +2+ D) + +SV 1)3 02)
$
120p"
47
Where the last inequality uses the fact
SV C/ log K + 3K - 1)2/3 + 4(CF)) 2 48Vd(K - 1)
By By Lemma
3
we can get
k n,t S 2x
12
12.2 ADVERSARIAL BOUNDS
Then, the group regret can be bounded as follows:
(T(
E
(v.)) - (k()
(BB(me), xu,)) - Bl (k*) 11
(6)
mmg F.,e) - (1.T+1(k*))
E
E
Fr ( igba ma) - (-( + (Ivee
(A)
T
V
Fo
jobby - Fi
(et-ob jabs mm)) - --(o-t)))) + F
(B)
Σ Ft
F - Eotzee -F((-Lo))))
(C)
22

---

Published as a conference paper at ICLR 2026
Where (a) holds because the following facts for all arms k:
(kk (k) (ea(k) (ka
(k))(()),
(b) holds because the following definition:
T (1.T+1(k)) = Σ (k))
V T
= Σ Σ
me(k")
tmll
uml tml
12.2.1 BOUNDING (A)
We introduce the count variable
V Σ
1 1kk, kj.
v=1
which records how many agents select arm at round By this definition, for any arm k we have
mk,t
1
Σ (k)
ke, Zoe((k) >
Σ
3Y
(29)
V
(k)
2V (k))
where the first inequality uses le,t S 1, and the last inequality follows from Lemma
F2
oo
m²) FT (ibbe) + (Frrtt me)
v
-m) mm) - + (2v, mi)
PT - - + (xr,,,
Dr (f' ma.t; I' (xo,))
V D3 (Fo,,,)(())))) - mk....) ((
Yeust
V Dj3 (F((ens(kss)))
I' (duse(krs)))
2Vzo,((ku.)
8V (V (kkn)))
(ko. ) (Zo,e(kio,))
(ko,) 169V2D
32
32
Where (a) applies Facts 2 and 3, the (b) follows from both parts of Fact 4, (d) holds because equa- tion 29 (c) uses Fact 6, and (c) uses the following equality for any arm k:
V
Diz (f'(zo,)) ma.t. (x(,))
Σ kv.
D5z (5' (Ir()) ma.1. I' (xv,)))
Yk,l
v=1
23

---

Published as a conference paper at ICLR 2026
Taking expectations and summing over & [T] yields
[F (- Lobe - m²) - Fÿ (- Logh)) + (Fvr)) Lc))
T
v K
v
I VVKT.
9
(30)
32
VVt
16
1= v=l
k=1
where we use Ex= Vi, S V and E t² 22VT.
12.2.2 BOUNDING (B)
We define ingiiss Li Lobe. Then we have for any v E [V] and L [T]
(-L,)),)) + +Fi( (-(-11)),)) Fi (-L,,,)) + Fi (- m²)
L/" (mi, VF xmm))
L (mi, ( i igg xm.)))dr.
Where the second equality holds by the fundamental theorem of calculus. Therefore, we have for any v [V] and E [T]
V
Σ 0=1
F7 (-
obo
(- -Lote - -m)) - - + (-
(mz. V ( i xmm))ddx L/¹ (me, VP (-i.oha i xm
(mE,s, - ( (1)))))) 1)d
K
(ma,,, 2(x),, - (FF((((((
i Emis (I:))
u,t
(mi,, - İ (k)))
mR, (xx(() ft' F/'(( (f. (Zx(z)) Limis (k)))
K
ma.Ji (3x( miss (k))do
ma.fi (Zx(x)) L (k)dd
mu.ee (3 (2mos(kt)
imiss (k)dx
K
3%
my F.. (k) (k)
2
v= km
(9) 9
mmss (kiu,)-
4V
24

---

Published as a conference paper at ICLR 2026
Where (a) uses the Fundamental theorem of caleulus together with the inequality above, (b) substi- tutes (xx) VFr(- f.ght xm;) and applies Fact 3, (c) follows from the fact that VF; [TT) decreases if the loss in coordinates other than is reduced, (d) applies Fact 5, (e) S is con- L (k)) I -āx(x) ft" E. (f) follows because Es S (k) and F (ar)-1 monotonically increasing, and (g) holds because the following in- equality:
vex, -f- -f (fx(Ex
K V
1
ma (k) (k) mise (k)
T(kk kin,)) (hs (k) Dg masee (k)
Bu ( (ku, Logion (ku,)) (kir,)
Vlu,e (ke Lir (ku)))(kus))) Fu,e
3
Misss (ka,t)-
2V
For any fixed k, U, 4, we have
E (1)1= =
( 120 71 al.0 $.,
le (k)
and
E [1),,))
= I(ko, = k)
e Iy, (k:)
lu (k)
11.
(k))
Using the same analytical method in Lemma
6
we can obtain
E
i f.mis
< E
[
obs - + +11 - jobs
min log(V)) 2 +VD= 1-02(P) (P)
<V
Finally, we have in expectation
E
Σ Lobe) - P- m+) - F (-tmx))) + (- Lot1a))
T
v ΣD
v
9
x
miiss (kin.)
4V
Lozl u=1
9n
4V
9
<
V
CfT K.
(31)
16
12.2.3
BOUNDING (C)
Let
Lt. E arg max (z, -L1,) - F((x). zEAR-1
By the definition of the convex conjugate, we have
(((,)),)) (ār, - -in,)) F((t).))
25

---

Published as a conference paper at ICLR 2026
Moreover, since (i-(--1,,) max -L,,) -Fi-1 evaluating the maximization at 31, yields
Fr-1(-L1,dh S -88,,,, -b1,) + F
(32)
Similarly, we have
F
L (1,1 < -lex, - LI, + Fr(ex=) & LI.T+1 (k*).
(33)
Plugging equation
32
equation into the left-hand side, and using the telescoping identity
T
T
F(((Lre,)) - F ((-o++1+))
Σ (-1()) - F2( F((-111t)))
obtain
Σ T.u,)) F(((-bu+1e)) in (1,7)1(("²))
T
(-In,)) - Pi Fi
F- I1,"=1(h"))
T
s <f +
Σ (t-1( -
s max EEAK-1
(-Fi(x))
Σ
max (Fi-1(z) Pi(x)) DEAR-1
-Fr(1k/K)
-VVVKT + 169V2D + 8V log K CFT//
/ log + 36D2 1) + 4(C
S SVVKVTTTT-..... + 8V CfTlog K + 104V /D + 48V D(K 1) log K + 16V C2f log K.
(34)
Combine equation 30
equation 31| and equation 34
we can get
Σ Rr (v)
137
137 VVKT
v CfT log K + 104V 10 48V -1) log(K + 16V log K.
16
16
Moreover, Lemma
I Implics that the individual regret is controlled by the group regret:
Rr(2) <
(V(
2V
< KTV + 13 CP K 156 72D - 1) log K + 24C log K.
12.3 STOCHASTIC BOUNDS
Inspired the analysis of stochastic bound for bandit with delay feedback in Masoudian et al. 2022 let J., F.F. (-Lu,)), then we define the drifted pseudo-regret as
(5o &.) - Ec(KT))
E
We rewrite the drifted regret as
T
T K
T K
Rdrift (v)=Bi = Σ
(ir,, 41) -
(((()))
= Σ
E
(itt 2, Ex,t [<(K"))) = Σ Σ
(=1 k=
k=
26

---

Published as a conference paper at ICLR 2026
Using the Lemma 7 for any agent y we have
K
T-D
5 R
Rarif(())
(v)
E
J
2
Bla b
3
3 1=1
t=1 k=
Σ
1Ax
K
E Elu D
1=1 k=
(v) - D.
Where the second inequality uses Σ 3 (v) + D and it suffices to upper bound (v))
Σk Bl AA S D. As result, have Rr(u) S
(v). As consequence, the drifted pseudo-
regret bound as follows:
R
(v)
E
l Tv,)) - =k()))
(e,, Fe,e) -(((
(0)
[[E[m]] Fe,e) E fm (k [l)
E
{m F..e) (x,x++((*))
E
F7 (1 - ( Lvv,e) + (Zv,e,
(A)
T V
ΣV
FT(-Lnd bm.)) - F7 (-bnotta)) (1
(B)
Where (a) holds because the following facts for all arms
V V
(ke((k) (k,)(k) (k,(())
((kb)
Σ (k,
Σ
E (k)),
(b) holds because the following definition:
V T
i,.T+1(k)) Σ
(k*)
Σ Σ
m me(k)).
1=1
v=1 t=1
12.3.1 BOUNDING (A)
P7 1.4 (- + (To.e,
V
Σ F. (- mi) - (-La)) + (a)
1=1
27

---

Published as a conference paper at ICLR 2026
V F. (P-- LLe (me - Eeze 2 mm)) - ( + (F m - Fuee 2 m²)
F((-VFi((rrn) (m+ - F.,t 4 m.)) - (- Fe(os)))) + (To me - Bogt ④ m²)
Pt( ((
- + (To mr - Fute 2 m²)
K
Σ
Dr: (f - (me(() - - mi mk))), (ā
K
V
(u sbtt)
Dj
((
f (āv,t)
V
u=1
1
Dji
(((o)))
V
2V2
T u,t
Te.e (k)
J
2V
8V2 /Vt
(1 - 2 )²
VVi
Where (a) applies Facts 2 and 3, the (b) follows from both parts of Fact 4, (c) uses Fact 6, and (d) uses the Lemma 8 In expectation we get
E
(- 1.) -FT( FF (Lo,)) + (Fo,s, mil)
2h, (Eth.))
2VVL
(at
To. (k (1T,,
VVt
2VVV
(7tk (Zt
(k)))
VVt
2/Vt
1=1
(atk
2VVL
V
k
v=1 Kg
(35)
vVL
12.3.2 BOUNDING (B)
For any u E [V] we have
v
T
Σ Σ -L, -F((-o0221))
= Σ
( Lo,e)
Fiti (-L0411))))) - Fi( (-(-)))))
t= v=1
t=1
28

---

Published as a conference paper at ICLR 2026
We have the following bound by Abberettyy et al. (2015)
F (- B.
(1,7+1(((*))
(- - F2 (-mmett)) - (1,7+1('*)
V T
V
x
((Pz- - (Fr(T..))) + Fr(x*) - V
Σ
(Tx.))
1=
which gives us
T v
- (-b+t,))) (1,1+2(k"")
V
T
K
(1oa)) ) (1T - - - Σ
s log log( - 7(-1)
ligh
+ 22V 10(K 1)+ vro Vollog K
Cp nat log( Vlog K
+ +2 n/ 11) + voo log K. (36)
where the first inequality holds because w (k*) S. 1 and the second inequality follows by
7--1
VC T Vlog K
1/ 7 S
Vne and 7t- 72-1
S
7
7--1
Combine equation 35
and equation 36
we can get
V
T
V
3
T TVE
K
-r log(1/#5.1
R
ΣΣΣ
2VVL
log K
1=2 ==
K
22V (K - log K + +VV log K.
(37)
12.3.3 SELF BOUNDING ANALYSIS
We use the self-bounding technique to write V
Σ
Aahift (v) = 3 3V
By
Rarift (v)
2 2D (x))f(()) and then based on equation 37 we have
v
9(
Σ Rerss((
S
Rarist (v)
2VVi
3C To- t v, (og(1//bb
ΣΣΣ
Σ Rarift(u) (v)
log K
DV(K 22V D (K - 1) log K + CV log K.
Here we give bound for the first term:
v
9
)
v
T V
9 )4
Σ
R
(v) =
2b. Ab
2VVt
2/Vt
A
1=1
(=1 v= Kitk'
ΣΣΣ
81
81 B1log T
4VIAR
4
k
29

---

Published as a conference paper at ICLR 2026
where the first inequality uses Vz, 0: u zy + 2yy zy y S called AM-GM. According the proof of Lemma 8 in Masoudian et al. (022). we can get bound for the second term:
V K 3C 7t- 1- , log(1 (1/55)))
V
36V
ΣΣΣ
Rt
Rdrift (v)
-
log K
D log K
In summary, we have
5 Σ RT(U)= S Σ
(V)
+VD
34 T
60
(K- + TVC log K + VD.
A
A log
For any k; f, by Lemma
we can get the individual regret for each agent
(v( S
Rr(v)
2V
51 51 T
90C
+ 56D V(K log K 110f log K 2D.
VÂR
D log
k=
ligh
12.4 PROOF FOR COMMUNICATION COST
At round 4, the message sent by agent v consists of two parts: (i) L and (ii) the deviation-record set A.. The size of i is O(K). Moreover, each deviation record remains the system for most D rounds, so A contains at most the records generated by all agents over the window t- D < S Thus, obtain
E[Comm_size((,t]]] = =(())))))=-)-)
Σ
Σ
VD
O(K) - 0
Σ
i(12VC
O(K) - O
Σ ((22C
12VC Tr
O(K
(1 12V Cf C2'))
Where the last equality comes form the inequality:
ia
2)
Finally, using 12VC''m < 0.75, conclude that BBcommm [|oomm..cstt(p: t)] O(K).
30


Reviews:
[{"review_id": "eeh1peCnoi", "reviewer": "Reviewer_39L1", "summary": "This paper considers a multi-agent multi-armed bandit problem, where $V$ agents each face an identical copy of a set of $K$ arms. At each round, agents can share information with their neighbors according to a communication graph. Due to privacy constraints, agents are only allowed to share statistics of the losses rather than the raw losses themselves. The authors design a best-of-both-worlds (BOBW) algorithm that achieves near-optimal regrets in both stochastic and adversarial regimes. The paper also includes numerical evaluations of the proposed algorithm.", "questions": "- Is the proof of Lemma 2 in the appendix actually meant to support Lemma 1? Please add clear references in the main text to help readers locate the corresponding proofs.\n- Why was IND-FTRL not included in the evaluation shown in Figure 2?\n- This work achieves a significant improvement in the regret bound for the adversarial regime. Could the authors elaborate on which algorithmic components, analysis techniques, or assumptions are responsible for this improvement compared to (Yi & Vojnović, 2023)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper establishes new state-of-the-art BOBW regrets for the multi-agent privacy-preserving bandit setting.\n- The work introduces a truncated loss estimator, which ensures that individual regrets across agents remain similar (Lemma 1). This is a notable contribution, as prior multi-agent bandit works typically require agents to be fully homogeneous to derive individual regret guarantees.", "weaknesses": "- Main concern: The definition of the feedback  $\\ell_{v, t}(k_{v, t})$ is unclear. The paper highlights that it is biased, but does not clearly describe the nature or extent of the bias. Moreover, in Section 6.1, the feedback does not appear to show any bias. Could the authors clarify this point?\n- It is unclear whether the goal of each agent is to minimize its own individual regret or a global regret across all agents. While the abstract emphasizes that no single agent can identify the globally best arm, this distinction is not explicitly modeled in the problem formulation. Additionally, if each agent is minimizing individual regret, identifying the global best arm may not be necessary. Clarification here would be helpful.\n- The use of the term \"federated\" may be misleading, as federated learning typically involves a central server, whereas the setup in this work appears to be fully distributed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "8Nq2DEw6wf", "reviewer": "Reviewer_cGPZ", "summary": "The paper study the Best-of-Both-Worlds (BoBW) problem in decentralized federated bandit setting, where it follows the FTRL algorithm’s idea but handle delay and client heterogeneity in federated settings via a modified learning-rate schedule and truncated loss estimators. Theoretical results are provided for the proposed algorithm and the regret almost matches the lower bound in this setting. Numerical experiments validate the effectiveness of the proposed method.", "questions": "**Learning rates:** How are learning rates in (201) compared with that in the delayed feedback (Masoudian et al., 2022) ?\n\n**Communication cost:** How is $x_{v,t}(k)$ compared to  $12VC_t^{P}\\gamma_t$ in (4)? In practice, how many rounds do we need to truncate the loss and broadcast? \n\n**equation (5):** It seems V multiplies to the loss after communication as well? In this case given $P$ is doubly stochastic, (when the loss estimates of the neighbors are closed), loss estimator seems to have exponential growth as time $t$ increases. Could the author elaborate this more?\n\n**Clarification on matching bounds:** If the graph $G$ is known, could we always construct a doubly stochastic matrix $P$ as in Remark 1 to achieve the nearly matching bounds? \n\nTypos: \nline 155: (u,v)\\not\\in E", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Theoretical guarantee for the proposed method is strong which almost matches the lower bound in this setting.", "weaknesses": "We need to know the topology and $D$ beforehand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "xC1Lsg0Wb3", "reviewer": "Reviewer_yECc", "summary": "This work addresses the federated multi armed bandit problem and focuses on the heterogenous setting where agents cannot determine the globally optimal arm using their local biased observations. The major contribution is the proposed Best-of-Both-Worlds algorithm that performs robustly in both stochastic and adversarial environments. The proposed algorithm adapts the Follow-the-Regularized-Leader framework and incorporate a hybrid regularizer typically used for bandits with delayed feedback. The authors view this as analogous to the latency caused by decentralized communication. Novelty includes the use of a communication scheme that tracks ddeviation records and a truncated loss estiator to keep agent action probabilities nearly aligned despite the heterogeneous feedback. They demonstrate that the FEDFTRL algorithm achieves near optimal regret bounds.", "questions": "1. Given that the communication cost is $O(K + V D)$ bits per round for each agent, can youprovide a more detailed discussion on the practical implications of this dependency on the number of agents $V$ and the network diameter $D$ for typical federated systems? Quantifying how $V$ and $D$ affect runtime in the experiments would be beneficial.\n\n2. The parameter $C_t^P$ in Eq. (2) quantifies the delay caused by decentralized communication and $C_T^P$ captures the dependence on network topology. Can the authors further clarify the intuitive meaning of how these complexity measures dictate the regret?\n\n3. The truncated loss estimator $\\tilde{\\ell}_{v,t}$ is crucial for stabilizing action probabilities. Can the authors comment on the practical robustness of the truncation threshold $(12V C_t^P \\gamma_t)$ of the denominator. Especially, regarding its potential sensitivity to misspecified initial parameters or dynamic changes in the network topology captured by $C_t^P$?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The core contribution of the paper is the first Best-of-Both-Worlds regret guarantee for the heterogeneou federated bandit setting.\n\n2. Achieving $O(\\sqrt{T})$ individual regret in adversarial setting is a clear improvement over previous results.\n\n3. The theoretical analysis seems deep and the derived regret bounds match the known lower bounds.\n\n4. Experiments are comprehensive.", "weaknesses": "1. The major limitation is the communication complexity which is explicitly mentioned by the authors as well. Each agent requires communicating $O(K+VD)$ bits of information every round. This is a potential practical bottleneck for large scale federated systems with many agents or high network diameter.\n\n2. The algorithm relies on special hybrid regularizers and fine tuned time varying learning rates that are defined based on network characteristics. Even though they are necessary for theoretical guarantees, this complexity may hinder deployment and tuning in practice.\n\n3. While the adaptation is novel for federated setting, the theoretical framework relies heavily on importing and combining existing BOBW literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "oP2ngNrNua", "reviewer": "Reviewer_ouUu", "summary": "This paper studies distributed multi-armed bandits with heterogeneous losses under both stochastic and adversarial regimes. It introduces FEDFTRL, a novel algorithm that is the first to achieve near-optimal regret in both settings. Comprehensive experiments are provided to validate the theoretical guarantees.", "questions": "Please explain weaknesses, and I may significantly revise my review comments accordingly.", "limitations": "", "rating": 2, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "### Contributions\n1. First establish an $O(\\sqrt{T})$ regret bound in the adversarial regime.\n2. Prove a best-of-both-worlds guarantee\n3. Paper is well written.", "weaknesses": "1. Requires $O(K + VD)$ bits of communication per round; the protocol differs substantially from prior work (previous only required $O(K)$ ), so direct comparisons are not straightforward.\n2. With an additional $O(VD)$ budget per round, the problem essentially reduces to a standard multi-armed bandit with delayed feedback.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)