Federated $\mathcal{X}$-armed Bandit with Flexible Personalisation
Authors: Ali Arabzadeh
James A. Grant
David S. Leslie
Venue: Accepted by TMLR ()

Abstract: This paper introduces a novel approach to personalised federated learning within the $\mathcal{X}$-armed bandit framework, addressing the challenge of optimising both local and global objectives in a highly heterogeneous environment. Our method employs a surrogate objective function that combines individual client preferences with aggregated global knowledge, allowing for a flexible trade-off between personalisation and collective learning. We propose a phase-based elimination algorithm that achieves sublinear regret with logarithmic communication overhead, making it well-suited for federated settings. Theoretical analysis and empirical evaluations demonstrate the effectiveness of our approach compared to existing methods. Potential applications of this work span various domains, including healthcare, smart home devices, and e-commerce, where balancing personalisation with global insights is crucial.

Published in Transactions on Machine Learning Research (09/2024)
Federated X'mmeeed Bandit with Flexible Personalisation
Ali Arabzadch
School of Mathematioal Sciences
Laneaster University
James A. Grant
j. j.grant@lancaster.ccc
School of Mathematical Sciences Lancaster University
David S. Leslie
d dllesiie@loccssterr.c...
School of Mathematical Sciences Lancaster University
Reviewed OpenReview: https:
httppe://openrevieuu optp//view...e.... net/ forum? id= fr61ToAd9o
Abstract
This paper introduces novel approach to personalised federated learning within the X'armed bandit framework, addressing the challenge of optimising both local and global objectives in highly heterogencous environment. Our method employs surrogate objective function that combines individual client preferences with aggregated global knowledge, allowing for a flexible trade-off between personalisation and collective learning. We propose a phase- based climination algorithm that achieves sublincar regret with logarithmic communication overhead, making it well-suited for federated settings. Theoretical analysis and empirical evaluations demonstrate the effectiveness of our approach compared to existing methods. Potential applications of this work span various domains, including healthcare, smart home devices, and e-commerce, where balancing personalisation with global insights is crucial.
1 Introduction
In the rapidly evolving field of machine learning, realising appropriate levels of personalisation has emerged as a critical challenge. This article addresses this pressing concern within the context of sequential decision-making, specifically focusing on the X'armed bandit (Bubeck al. 2011). The need for both data aggregation and individual customisation evident in various domains. For instance, in the context of healthcare, data can be aggregated across subjects to yield population-level insights into (o.g., dosage efficacy), but individual differences necessitate personalised treatment. Similarly, for smart home devices, data aggregation across the clients can result in improved general policies, but each individual home has different characteristies: privacy should be guaranteed to encourage the beneficial aggregation of data for the common good, but personalised policies need to be implemented at individual devices. These scenarios highlight two key concepts: "federated learning" (Konečný al. 2016; McMahan et al. 2017). which enables data aggregation while maintaining privacy, and "personalisation" (Smith al. 2017). which tailors strategics to individual noeds. However, the optimal level of personalisation varies across different applications and use-cases; therefore, a one-size-ftt--al approach is insufficient. This article develops personalised federated learning framework for the X'armed bandit, designed to allow flexible tradc-offs between global and individual objectives, enhancing user experience by sharing exploration of the decision space, aggregating data securely, and facilitating individually beneficial decisions.
Federated learning (FL) (Koncčný al. 2016 McMahan et al. 2017 is a distributed learning paradigm that addresses efficiency and privacy concerns in real-world, unbalanced and non-IID datasets. As datasets grow and models become more complex, the need to distribute the learning process across multiple machines

---

Published in Transactions on Machine Learning Research (09/2024)
has increased. Conventional distributed learning approaches (a et al. 2017 Reddi et al. 2016 Zhang & Lin 2015 Shamir et al. 2014) were designed for well-regulated environments like data centers, where data is typically balanced and i.idd. across machines. However, these methods are ill suited for privacy-sensitive, heterogencous data found on edge devices such as smartphones.
FI. emerged as a solution to this challenge, enabling the training of models on rich and privacy-sensitiee data from edge clients. In the FL framework, edge clients collaboratively train shared global model under the coordination of central server. This approach preserves the privacy of local data while reducing communication costs. By leveraging the collective knowledge of edge clients, FL offers powerful new paradigm for distributed learning in real-world settings.
While vanilla FL has shown promise in privacy-preserving distributed learning, it can lead to suboptimal performance for individual edge clients with heterogeneous local datasets. To address this limitation, FL with personalisation has been proposed as an extension of the vanilla FL framework. This approach incorporates client-specific objectives to enhance model performance on heterogeneous data distributions (osiuttiioonmmitthhiii (Smith al.,
2017
Wu et al. 1020
In personalised FL, the globally trained model serves as a foundation that is further adapted or fine-tuned to better align with individual clients' specific data or preferences. This methodology enables the development of models that are both privacy-preserving and highly tailored to individual clients, effectively balancing collective knowledge sharing with local specialisation.
1.1 FL and Multi-Arman Bandits
While statc-of-tho-art FL rescarch has prodominantly focused on supervised learning scenarios, there is a growing interest in extending FL to the multi-armed bandit (MAB) framework (Lai & Robbins 1985 Auer et al. 2002). The MAB problem is popular framework for studying decision-making under uncertainty. In its simplest form, the MAB consists of a set of independent "arms", each providing a random reward from its corresponding probability distribution. An agent, without prior knowledge of these distributions, selects one arm in each round, aiming to maximise the total expected reward over time. This process necessitates a delicate balance between exploring arms to learn the unknown distributions and exploiting the current knowledge by choosing the arm that has historically provided the highest reward. The extension of FL to MAB is particularly relevant for applications like recommender systems and clinical trials, where decision-making is inherently distributed across multiple clients.
Unlike centralised MAB models that assume instant dala access, the FL approach processes data locally at each client, thereby reducing communication overhead and enhancing data privacy. However, federated bandits introduce unique challenges beyond the classical exploration--xploitation tradc-off in centralised models. These challenges include data heterogeneity and privacy preservation (Shi & Shen 2021 Shi et al. 2021 Huang et al. 2021 Li et al. 2024b, Réda et al. 2022). Tn FI, scenarios, collaboration among clients becomes crucial for accurate inference on the global model, especially given that each client's data may not be independent and identically distributed. Yet privacy concerns and communication costs motivate clients to avoid direct transmissions of local data.
The X'armed bandit (XAB) problem is an extension of the classic MAB problem, where the decision-space is significantly larger and even contimuus, involving a potentially infinite number arms. Unlike traditional MAB problems which are limited to a discrete set of options, the XAB framework allows for a broader range of actions, making it particularly suited for complex environments where actions cannot be casily cnumcrated. This complexity introduces unique challenges in terms of exploration and exploitation, as the agent must. efficiently navigate vastly expanded action space to optimise outcomes. (Bubeck et al. 2011 Kleinberg
ct al. 2008)
Balancing exploration and exploitation while achieving privacy and personalisation requires a complex yet efficient communication protocol between clients and a central server. While Shi et al. (2021) have addressed this problem for finite, un-structured action spaces in their work on Personalised Federated MAB (PF-MAB), our work extends the principles of personalised federated learning to the XAB problem. In PF-MAB, the high probability guarantee that each client's 's active set eventually converges to single best arm enables
2

---

Published in Transactions on Machine Learning Research (09/2024)
straightforward shift to pure local exploitation after the best arm is identified. This behavior is critical for ensuring minimal exploration once the optimal solution is reached. However, in the continuous action space of XAB, no such discrete "best arm" exists. Instead, the algorithm must continuously balance exploration and exploitation to approximate the optimal action effectively, as convergence to a single point does not apply in continuous seltings. This necessitates a more refined exploration-exploiaaiio trade-off to keep the algorithm both efficient and analytically tractable.
To effectively manage exploration in continuous setting, approach uses partitioning strategy for the action space. This partitioning allows the algorithm to iteratively focus on progressively refined regions with high potential rewards. By adaptively adjusting the granularity of the partitions based on number of samples taken, the algorithm can efficiently explore and narrow down the action space without needing a singular "best" action to emerge.
Our research considers the critical addition of personalisation to recent works in federated XABs, particularly the novel method proposed by [i et al. (2024b). We realise this through a surrogate reward function that combines local and global knowledge, inspired by [Hanzlly & Richtárik (2020). Specifically, we defined a surrogate reward function for each client linear combination of their local reward function and the average reward function across all clients. This formulation inherently emphasises the importance of integrating global information, which is particularly beneficial in scenarios where data heterogeneity is significant and global insights are crucial for informed decision decision-making Our approach offers a tunable balance between global and individualised optimisation, enabling clients to benefit from collective learning while still tailoring the model to their specific conditions.
While recent extension (Li ct al.) 2024a) also considers personalised variant of federated XAB, our approaches differ substantively. The approach of Li et al. (2024a) seeks to optimise each local functions directly, rather than personalised mixtures of local and global effects (as we do), under an assumption that differences among individuals are bounded (via constraints on local reward functions). This model and assumptions leads to an alternative notion of regret, for which the theoretical guarantees are ostensibly sharper, but since the settings are different, the results are not directly comparable. Our framework can capture broader heterogeneity among clients, and allows improved flexibility since the level of personalisation can be determined by the practitioner rather than environment alonc.
The flexibility of our framework offers significant potential benefits across various domains. In healthcare applications, specifically clinical trials, this approach allows the derivation of general medical insights from aggregated data while keeping treatment recommendations personalized to each patient's medical history and condition. To better illustrate this, imagine several hospitals collaborating determine the optimal dosage of a new drug. The action space, denoted as X, represents the continuous range of possible dosages. Each hospital acts as client, with a local objective function umm (x) that quantifies the effectiveness of dosage X' for their specific patient population. Factors such demographics, medical history, and prevalent discase strains contribute to the uniqueness of each (r)).. The global model, aiming to ascertain the average drug effectiveness across all hospitals, utilizes the average of all local objective functions, represented as μ(x). The personalized objective function, denoted as p'm (2), combines each hospital's 's local objective with the global objective, striking a balance between individual hospital needs and overall drug efficacy.
1.2 Main Contributions
Our primary contributions are as follows:
We propose novel personalised federated XAB model that accounts for user preferences and data heterogeneity. This model strategically designed optimise the trade-offs between communication efficiency and learning performance in federated bandit setting.
2. We introduce PF-XAB, a novel algorithm tailored to the personalised federated XAB problem. Key features of PF-XAB include: a) edge clients communicate only their local reward estimates, preserving privacy of raw observations, b) the algorithm achieves sublinear regret while maintaining logarithmic communication cost.
3

---

Published in Transactions on Machine Learning Research (09/2024)
3. We provide theoretical analysis demonstrating that PF-XAB achieves sublinear regret bounds while maintaining logarithmic communication cost.
2 Preliminaries
In this section, we define the framework for our study of the personalised federated XAB problem. We will outline our model and specific objectives, introducing the key notation and assumptions that underpin our analysis. For an integer n E N, we let [n] represent the of integers (1.2....,)). For a set A, |A| denotes the size of set A.
2.1 Problem Formulation
Clients and local models. Let X be the measurable space of arms. We model the problem, following Li et al. (2024b), as federation of M N clients, each with access to distinct bounded local objective Pm (m) X [0,1], II, m [M]. These objectives may be non-convex, non-differentiable, and even discontinuous. As we focus on bounded functions, without loss of generality, we assume these functions are bounded within the unit interval [0, 1].
Given a fixed number of rounds T, each client queries its local objective oracle once per round by selecting an arm Jm,t X round E [T]. This evaluation yields a noisy feedback Tm,t = jum (Xmm,)) 6m.t, where fm. is a zero-mean, bounded random noise, independent of previous observations or other clients' observations, Importantly, the local objectives necessarily equal for distinct clients m and
capture client-spocific preferences, i.c., jmm (m) and (n(x) are not
The global model. The global model is X'armed bandit model that shares the search space with the local models but uses the average of local objectives over all clients as its objective. This average, known as global objective, is defined as
1 M
m(x)=
Σ pm (m)
x E X.
It is important note that while the global model represents the average local models, the global rewards are not directly accessible to any individual client, local observations remain private.
The personalised model. In conventional federated learning framework, clients collaborate optimise the global objective μ.. However, this approach may not always align with individual client interests. To address this, we capture the personalisation aspect via mixed objective, inspired by the well-established and popular technique of Hanzely & Richtárik (2020) in federated learning literature.
Similar to (Shi et al. 2021 Salgia et al. 2023 we define a personalised objective p'm which is a convex combination global and local objectives:
(x) == op (p)(())) + (1) (1)))()x) x E E.
(1)
where a E [0, is the personalisation parameter.
The components of the mixed objective bear similarity to the objectives in (Ti al. 2024bb and (Li et al. 2024ah, however handling the mixed objective brings additional challenges, as well as the flexibility to capture more diverse sets of clients. The personalisation parameter allows for explicit control over the level of personalisation:
a 1: Complete personalisation (oquivalent to local objective)
0: Complete reliance on the global model (no personalisation)
(0, 1): Balances global knowledge with local preferences
4

---

Published in Transactions on Machine Learning Research (09/2024)
By varying a, we address the trade-off between global and local performance. This model integrates personalisation while retaining the benefits of global generic knowledge, potentially mitigating overfitting risks common in fine-tumed models.
It is important to note that optimising this personalised objective is more challenging than scenarios where clients collectively optimise a generic global objective (o = 0) or individually focus on local objectives (a = 1). The mixed nature of the objective introduces complexities in balancing the local and global information.
In this personalised model, each client aims to optimise its personalised objective, which is unique to that client. However, this introduces significant challenge: the estimation of client's personalised objective I'm requires knowledge of other clients' local objectives (unhnmm which are not directly observable by client m.
Optimising this personalised objective is more complex than traditional federated learning scenarios where clients either collectively optimize global objective (a = 0) or individually focus on local objectives (a = 1). The mixed nature of p'm introduces complexities in balancing local and global information, particularly because client m can only directly infer the local component of its personalised objective, while the global component, (1 - a),(x), remains partially unobservable.
2.2 Performance Measure
In our proposed framework, we aim to devise a collaborative optimisation strategy across a federation of personalised models. We assess the performance of this strategy through the expected cumulative regret, which is essentially the sum of the individual clients' regrets, calculated with respect to their individual personalised objectives. Formally, we define the expected regret as
T
M
M M'm (Fma))
E R(T) = Eg
[=1 m=1
t=1 m=1
where / denotes the optimal value of p'm on X. The expectation is taken with respect to randomness in the sequence actions, which arises from the stochasticity of local rewards Tm.t-
Ti important to note that in the context regret, an inevitable increase over time expected. Our focus, therefore, lies in understanding and minimising the rate at which this increase occurs, aiming to minimise the average regret over time.
2.3 Hierarchical Partitioning of Search Space
We employ a recursive partitioning approach denoted by : (Ph,tha which splits into hicrarchy of nodes at various depths. The partitioning follows the rule:
Pa. = X, Ph,s == PM412 U UP++122
where:
Each node Ph.s is defined by its depth h and index i, corresponding to specific region within the discretisation of the search space.
For each h 0, 0 the set (Ph+1.2--)) consists of two disjoint children nodes of P
At each depth h, the union of all nodes is equivalent to the entire space X.
The partition is fixed and shared among all clients and the central server prior to the beginning of the FL process. This ensures a consistent structure for exploration and information sharing across the federation. While we employ binary partitioning of the space in this work, our principles could readily be adapted to a k-ary partitioning approach.
This hicrarchical partitioning provides structured approach to exploring the continuous action space X, facilitating efficient search and information sharing in our federated XAB framework.
5

---

Published in Transactions on Machine Learning Research (09/2024)
2.4 Assumptions
To evaluate the performance of the proposed algorithms,, employ a set of assumptions commonly used in prior works on X'aarmed bandit Bubeek et al. 2011 Gheshlaghi Azar et al. 2014 Grill et al. 2015 Li et al. 2024b
Assumption 2.1. (Dissimilarity Function) The space & is equipped with a dissimilarity function x: + R such that f(z, y) 2 0, (z, E x²2 and x) = 0.
Given a dissimilarity L, we define:
Diameter of any subset A A X: diam(A) == yEA (2x,8)
Open ball with a radius r centered at c: ((c,r) = fxE ((x, c) sr}
Assumption 2.2. (Local Smoothness) We assume that there exist V1, V2 > 0 and 0 < p < 1 such that for all nodes Ph.i, Phij E P on depth h,
diam((h,.) S v1ph
3 Ihhs Ph,s s.t. Ba, = B(onss B200) C Ph,
Ba n = for all #
For any objective a E . Pm3 we have for all x, X.
:¹ - p(v) s n² u(x) + max(u" -
This assumption pertains to the "smoothness" of the objective functions and ensures that as the depth increases, the search regions become increasingly fine, allowing for more detailed exploration of promising areas within the hierarchical partitioning approach.
Remark 2.3. Similar to the existing works the X'armed bandit problem, knowledge of dissimilarity function l is not required for our algorithm. However, knowledge of the smoothness constants v1, P is necessary.
Remark 2.4. In this setup, we do not impose specific assumptions on clients' objective functions beyond the regular smoothness conditions typical in X'armmd bandit literature. This contrasts with (Li et al., 2024ah, the only prior research on this problem and most related and similar to ours, which imposes two additional constraining assumptions (Assumptions 3 and 4 in their work). These assumptions jointly require that near-optimal points with respect to the global objective are also ncar-optimal with respect to all local objectives. Our problem setup is more flexible, allowing for a wider range of real-world scenarios with varying degrees data heterogeneity.
3 Algorithm and Analysis
In this section, we introduce novel phase-based elimination algorithm to address the challenges of personalised federated XAB. We highlight its distinctive features compared to existing algorithms and provide a theoretical analysis of its performance.
A bespoke algorithm is sorely necessitated for the personalised federated XAB, as existing XAB algorithms will fail to meet the challenges of the setting. Unlike the focus on optimisation of the global objective explored in works by Shi & Shen 22021) and Li et al. (2024bb, our interest lies in simultaneously optimising the personalised objectives of the clients. This task is evidently more challenging since it can be viewed as a problem of multi-objective optimisation with communication budget constraint.
Consequently, developing an effective communication strategy that enables an unbiased estimation of the global objective becomes a critical element of algorithm design. This particularly important in scenarios involving large number of clients. Furthermore, the constraints on commuicatiin budget mean that local rewards not instantly accessible. As result, algorithms that depend immediate reward feedback, such

---

Published in Transactions on Machine Learning Research (09/2024)
H HOO Bubeck et al. 2011 and HCT (Gheshlaghi Azar et al. 2014), not appropriate for addressing this
problem.
In the context of federated bandit algorithms, the requirement for minimal communication overhead indeed renders algorithms that are built on phase-based elimination techniques appealing & Shen, 2021 Shi
et al. 2021 Réda al. 2022). Therefore, algorithms such as our own proposal, which eliminate sub-optimal nodes phases, are more suitable for the federated XAB problem, as suggested in works like (Li al.,
2024b a..
3.1
The PF-XAB Algorithm
We now introduce our new phased-elimination algorithm, called Personalised Federated X'-rrmed Bandit (PF-XAB), designed to address the challenges outlined above.
Algorithm : server
Input: T, M
while not reaching the time horizon do
Receive (p) from all clients
Broadcast A(p) = U (p) and f(p) = Muta
2 (2')
mE[M]
Receive local estimates (m (tt.ss))mmmmmMMM,...e....... for every 2) A(p) do
Update P(n,s) M ΣM (m..))m (p) end for Broadcast (P) = end while
The PF-XAB algorithm comprises two components: a client-side algorithm (Algorithm 2 and a server-side algorithm (Algorithm [ The algorithm operates in dynamic phases, leveraging the hierarchical partition to gradually identify the optimum by systematically climinating sub-optimal nodes within the search domain.
The server acts as a coordinator with two primary functions. broadcasts active nodes A(p) in phase p, which represent the collective active nodes across all clients. Additionally, It aggregates empirical estimates of the local objectives (p) for all active nodes (h, i) A(p) from clients, and subsequently broadcasts the empirical estimates of the global objective back to all clients.
On the client side, the algorithm involves a phased interaction with the environment, segmented into three distinct sub-phases: global exploration, local exploration, and exploitation. During both the global and local exploration sub-phases, clients take actions from two sets: the global active set A(p), and their own local active set (p). They use the foedback to these actions to construct empirical estimates of their local objective. These local estimates are then communicated to the server, allowing for centralized estimation of global objective. While client waits for the server to provide the empirical estimates of the global objective (as other clients may have more exploration to perform), it enters the exploitation sub-phase, where it simply exploits the best action based on the most recent evaluations.
PF-XAB offers a degree of privacy and confidentiality by sharing only average rewards (P(n.)), (p)) with the server and not individual reward values (fm,,),,),.) The server then shares summary statistics with other The clients. However, we acknowledge the need for a more formal treatment of privacy considerations in this setting.

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm PF-XAB: m--t client
Input: partitioning P, time horizon T, client count M, personalization parameter a, stopping depth H Initialize p 1, (1) = ((1, 1), (1,2)) while not reaching the depth H do
Receive A(p) and f() from the server
for each (h, i) E A(p) sequentially do
> Global exploration
Pull the node fp) times and receive rewards (rm,(h,0).t)
Update 8(1,6). = 8(h,)). + Ee (m.(),)), and Tm.(h.s) = T mm,( + [(1 [1-=)) end for for each (h, (p) sequentially do
Local exploration
Pull the node [Ma((p)] times and receive rewards (Tm,(hh,))e) Update 8(h,)). 8(h.).m + Ee (m,i),)), and Tm.(h.s) = T (m, + [Maf(p)]
end for
Calculate (( = (...))./Tm.(hh. for every (h E A(p)
Send (M)... to the server
Set (hp. = arg (n, (.). (m Pull node (hp: ip) until (for.)) (P) ((.))e()))))) are received from the server for all (h, (p) do
Exploitation
Fyn.))m (p) = (p.))) (p) + +1 - (1-a)) (b.))))))))))))))))))))))))))))) end for
Compute the elimination set E' = (h, i) E Am) (l + uspp S Mhppissii (p) - 2Bp Compute the new set of active nodes
(' 1) ((h +
1 1. (A (p))
Send (p + 1) to the server p= p=p+1 end while
Select and play the optimal action for the remainder of the time
The algorithm details are presented in Algorithms and In these algorithms,
the notation (h, i) to index node Pr, in the partitioning tree. ( denotes the number of pulled samples from m-th local objective in (h, i). By convention, we always sample the midpoint when playing a node. Due to the structure of the algorithm, (m,(h.s) is equal to [Maf(p)] + [(1 ap) and [(1 (p)(p) for local and global active nodes, respectively. Consequently, the total number of samples taken to compute the empirical mean of the personalised objective (/,,(0.1)) lower bounded by [M)] + M[( a))()) 2 Mf(p) and the
corresponding confidence bound in climination rule is Bp // Mf(p)
[og(T)
3.2 Theoretical Analysis
This section contains our main theoretical analysis and results. Here, we establish an upper bound on the cumulative regret the PF-XAB algorithm, operating under the assumptions previously outlined. Before this statement Theorem 3.9 several key lemmas are introdueed Analysing the regret of PF-XAB is more complex than that of algorithms like Fed-PNE because PF-XAB does not dircctly observe the personalised objectives p' (m). Instead, it works with estimates T( (p) constructed from local and global objective estimates. The proof must carefully account for the discrepancy between these estimates and the true personalised objectives.
We first determine the variance proxy of the empirical estimates of personalised objectives in Lemma 3.3 and use this to construct a high-probability "good event" " in Lemma 3.4 under which the empirical estimates of personalised objectives are sufficiently close to the actual personalised objectives. Lemmas 3.5 and [3.6] demonstrate two key aspects: firstly, that the optimal nodes (those containing the optimal point) will never be eliminated, and secondly, that all points within the remaining region are, in fact, sub-optimal. Proofs of the lemmas are deferred to Appendix B.
8

---

Published in Transactions on Machine Learning Research (09/2024)
To proceed we recall some facts concerning sub-Gaussian random variables.
Definition 3.1. (Sub-Gaussian Random Variables) A zero-mean random variable X e R is said to be sub-Gaussian with variance proxy o² if E [X] and its moment generating function satisfies
(o282 2 E
E [exp(sX)) exp
.n) Definition 3.2. (Sum of sub-Gaussian Random Variables) If (21, ,,) are independent {oi. , (ete)-su-Gaasssee Gaussian random variables, then Y Σ a,X,, for any a E R, a dssYY)sub--auusial random variable, where
+² af
As discussed, we first establish the sub- aub-Gaussianity of our estimators, and from this build a high-probability event.
Lemma 3.3. (Sub-Gaussian) Estimators) Let i), (p) denote the empirical estimate of pln. at the end of phase p. Then, T om (P) is a sub- Gaussian random variable with variance prozy V (M Lemma 3.4. (High Probability Event) Define the good event GT
GT GT: - VYp
Pr, Vm E V(h, E (T) (l).s),.m - 14m0 S scV
(T"
M Mf(p)
where the right hand side the confidence bound Bp for node Ph. and v2 constant. Then for any fizd i, have P(G)) 1-22M11 2M
On this high- probability event, we can establish guarantees both that the optimal node will not be eliminated, and that all other non-eliminated nodes are of good quality.
Lemma 3.5. (Permanence of Optimal Nodes) Under the assumption that the high probability event Gr holds, it can be stated for any client m that by the end of phase p E Pr, the node Phy will not be eliminated. This particular node contains the global optimum zmm of the personalised objective pmm (2) at the depth hp- More precisely, this implies that (hp: km.))) will not be included in the set of eliminating nodes (P)
Lemma 3.6. (Quality of Un-climinated Nodes) Assuming the high probability event GT holds and (log(T) f(p) Mufpat all points in every un-eliminated nodes upon the conclusion of phase p, is at least 12v, optimal.
The algorithm's performance is sensitive to the smoothness parameters V and p. which influence the confidence bounds in the climination process. A conservative estimate of p results smaller confidence bounds and shorter exploration phases, potentially leading to premature convergence to suboptimal regions and unbounded regret. In contrast, overestimating P produces larger confidence bounds and longer exploration phases, yielding regret commensurate with this estimate. Therefore, accurate estimation of these parameters is crucial for achieving robust performance.
To complete the proof of Theorem
3.9 we need one additional concept: that of near-optimality dimension.
Definition 3.7. (Near-optimality dimension) Given function f X R, the v-near- opttmarppt dimension, denoted by dy(c, is the smallest d > 0 such that there exists C. > 0 such that for any c > 0, the covering number of e-oplimal subset of X, denoted as Xt,,, with (-balls of radius ve is less than Ce -d
Remark 3.8. The near-optimality dimension d reflects the complexity of an objective function's 's landscape. For smooth functions with few local optima, d is usually low, near-optimal points remain limited even
9

---

Published in Transactions on Machine Learning Research (09/2024)
with larger search radius. In contrast, highly non-smooth functions with many local optima tend to have higher d, complicating the search for the global optimum. Typically, d is an intrinsic property of the problem and cannot be directly controlled. In many black-bon optimisation cases, d = is common, indicating a simpler landscape, as observed by Bubeck et al. (2011) and Valko et al. (013
Using the definition of near-optimality dimension, we denote dn,, dyc.. (12m)p², v1p") for every m [M].
We now present the central result. that establishes an upper bound on the expected cumulative regret of the PF-XAB algorithm.
Theorem 3.9. (Regret Upper Bound) Suppose that pm (m( satisfies Assumptions 2.2 and let dm denote the near-optine carr-optimality dimension of the mized objective as defined in Definition 3.7 The expected cumulative regret of the PF-XAB algorithm is bownded above by
E
= O(T
d42
where d' max,dd....., d...
Proof. Let la denote the indicator function associated with event G. Firstly decompose the regret into two terms based the presence of the good event
R(T) Σ 1 Pilhesee.o
Σ (ttt plansse..)) lcr +
Σ
Pm M(messe)mm 1oy
Thus [R(TT) = E [ (T)] + E [R)]
The second term of expected regret can be bounded as follows by using Lemma 3.4
M
T
M T
[
n (T) = E
(ni - M(heede)..
S
Σ XV
P(C S 2
To bound E [ (T)), we first bound the regret that we incur under the good event within each phase. This regret could be decomposed into three parts, incurred by three sub-phases that have in the proposed algorithm.
RO(T)= = Σ Re-espr - Re-expe + Resppt
PEAr
Here, eexprr Re expxx and Re Rexpt denote the regret within phase p that incurs to the algorithm in the global exploration, local exploration and exploitation sub-phases, respectively.
During the global exploration sub-phase, each client has to pull non-optimal arms from the active nodes of other clicnts included A(p). Therefore, the regret term associated to the global exploration R be upper bounded by the length of this sub-phase
G-expe can
BC R & [A(p) [(1 ap)(p) S M max LAT (m"()[[[[aa))(())
ME[M]
The nodes in AT (p) are direct descendants of the un-eliminated nodes in ATT 1) \ ETT 1), and the size
of T (p 1p-1) (m (p- 1) is bounded by Cp ddmhh by the definition of near-optimality dimension (Definition 3.7 and Lemma 3.6 Therefore, it means
(A) 2, (p (p- 11) ( 1)] S 2Cp -dmhhppp-
and results the following bound
2 2log(T)
8C - a)) log(T)
E (epp S [A(p) -1) -M 2(1 a)
-p-
p -hp--i(d++2)
Mv 2hp
vîp²
10

---

Published in Transactions on Machine Learning Research (09/2024)
Next, we bound the regret incurred in the rest of each phase, given by Ricexxpr + Resptt From Lemma 3.6 we know that all the actions clients take in these two sub-phases are sub-optimal, thus we can establish the following upper bound:
E Leppr Rexppl I 12 1 x [Maf(p)]
max (p) mE[M]]
(2)
2 (og 2Cp 11-
96Ca log(T) -p-1(dd)1))
s 12 2Ma
Mvsp2h,
vip²
Having established the key components of proof, we now proceed to the final step of the proof. involves determining the depth H which we will halt exploration and start to do pure exploitation. The expected regret under the presence of the good event bounded as follows
E [[(T)) <
8C(1 - a:) (T)
Σ (d-(t)2)) ho {(p((042)))
96Ca log(T)
v1p² Σ
(p-(attt))
" ",,
+121pp Tp)
v2p²
16Mcc(1 - a) (T)
(1 (p-(0)21)) H
ac
(11))((-())) (p-(ett)) H
+ (p="(o=((++))
+ 12u,p
up (dd
where H represents the depth of the partitioning tree by the end of phase P. Thus, the proof concludes by putting everything together as
B[R(T)) S 2M 16Mc(1 a) log(T) 1p (d 1)) (p-(()))
96M log(T)
(o-(d+t))* + 12
vs (p-(0(++++
(4)
and choosing H such that pa O
While a bespoke lower bound for the personalised federated XAB problem is not yet available to assess the 12
tightness of this bound, lower bound by Bubeck et al. (2011). the lower bound for the scenario in which all clients have complete access d'+1
compare our ( to results for similar problems. Notably, based on the
to each other's rewards at all timesteps is of order ((M7**3) where d' denotes the maximum near-optimality dimension among the personalised objectives. This bound, which holds under centralised conditions, provides useful baseline for evaluating the performance of our approach in the federated setting. Providing a regret lower bound for the personalised federated XAB problem, whether under the definition of PF-PNE with respect to local objectives or our definition with respect to personalised objectives, remains an open problem.
The setting of Theorem 3.9 more general compared to that Li et al. (2024)), and therefore the slightly increased order of the regret bound is perhaps unsurprising. Under the restrictive assumptions of (Li et al. 4'41 2024a), our algorithm achieves the same regret upper bound as PF-PNE, which is of order (+T)++)). A sketch of the proof for this claim is provided in the appendix. In any case, the existence of a method which is competitive under stronger assumptions and robust enough to attain sublinear regret under our weaker assumptions is encouraging with view to real-world challenges where strong assumptions may be challenging to verify.
Remark 3.10 (Communication Cost). The number communication rounds is always depends logarithmically on T, as the length of each phase is proportional to p -dd'+114 The communccation cost measured by the d+2
number of messages exchanged between clients and the server, can be bounded by C.M log(T)) where C is a constant.
11

---

Published in Transactions on Machine Learning Research (09/2024)
Remark 3.11 (Effect of Personalisation Parameter). As shown in ( the personalisation parameter influences the second and third terms of the regret bound. However, the third term is dominated by the second and fourth terms, which masks the impact of a on the overall bound. We conjecture that this lack of dependence on a may be due to the upper bound not being tight, as well as the absonce of a parameter bounding the differences between local objectives. Establishing such a bound could reduce the pessimism our analysis, potentially clarifying the role of personalisation parameter in the regret performance.
4 Experiments
In this section we evaluate the empirical performance of PF-XAB through a series of experiments employing synthetic objective functions and real-world dataset. To provide a comprehensive assessment, we benchmark PF-XAB against relevant existing algorithms. Specifically, compare to the federated X-armed bandit. algorithm Fed-PNE (Li et al. 2024b) and the personalised federated X'-armed bandit algorithm PF-PNE (Li et al. 20 Each of these methods adopls different notion of regret, reflecting their distinct models, which makes a truly fair comparison challenging. However, we choose to compare to closest counterparts in the literature, not to suggest their perfect compatibility with our problem, but rather to illustrate the necessity of a bespoke solution. This comparison highlights a performance gap when the algorithms (Li 2024b) and (Li et al. 2024a) are applied to our specific problem domain. Throughout this section, all experiments has been conducted on a federation with M 10 clients.
et al.
Averoge Cumuietive (10%
70
T- 10% 0.1
120
-110, a00
Aver Cururativv (30%
160
M-10.T 10 00
60
Rco me 100
140
Auwe age Curnulative flggrat
P-
50
10
J00
60
80
20
60
20
40
20
20
130
0
20
40
80
100
40
60
80
100
I(10")
(110")
11.0
Figure 1: Comparison of Cumulative Regret for PF-XAB, Fed-PNE, and PF-PNE Algorithms on the Garland Dataset Across Varying Levels of Personalisation a, with M machines over T 2 x 10 Time Steps. Each graph demonstrates the impact of personalisation on the algorithms' performance, with a representing the degree of personalisation from low (a = 0.1) to high (a 0.9).
We first conduct a range of experiments on two synthetic objective functions: the Garland and DoubleSine functions with varying levels of personalisation in the regret definition and in PF-XAB. These two synthetic functions are frequently used in the experiments of X'armed bandit algorithms due to their large number of local optima and extreme non-smoothness (Gheshlaghi Azar et al. 2014 Grill et al. 2015 Shang al. 2019 Bartlett et al.) 2019) The experimental design takes the canonical functions such that each client's 's local optimum is distinct, whereas the global optimum is strategically positioned to be sub-optimal with respective to the local objectives. The average cumulative regrets of different algorithms are provided in Figure 1 and 4 (see Appendix B) for the Garland and DoubleSine functions, respectively. The curves in these figures represent. the averages over 10 independent runs of each algorithm, with the shaded regions indicating 1-standard deviation error bars
baseline and modulates these
In addition to our initial experiments with synthetic objective functions, we extended our experiments to real- www.dwoodddiieeeee scenario using the landmine dataset (Liu et al. 2007). This dataset comprises data from multiple landmine fields, each assigned to client, with features extracted from radar images to determine the presence of landmines at each location. Each client aims to optimise their performance on a classificat tion task, using a Support Vector Machine (SVM) classifier equipped with RBF kernels. Our experiments explore d kernel parameters, y ranging in [0.01, 10), and the regularisation parameter C, selected from the range 140-4, 10*], forms the domain space of our experiments. The local objective for each client is defined as the AUC-ROC score of the classifier on their assigned landmine dataset. The performance of different algorithms
12

---

Published in Transactions on Machine Learning Research (09/2024)
10,0, 5=5x 10S, 0.4
Average Cumulative Regret (10?)
175
FI-AB
150
Ped-INE
125
100
75
50
25
0
0
10
20
30
((10')
Figure Cumulative regret comparison of PF-XAB, Fed-PNE, and PF-PNE on the Landmine dataset.
in this real-world sctting is illustrated in Figure 2 This figure presents the average cumulative regret of each algorithm with 0.4, showcasing our algorithm's effectiveness by its ability to achieve the smallest regret. This outcome not only validates our approach in synthetic settings but also demonstrates its practical applicability and superiority in handling complex, real-world tasks, such as landmine detection.
In the third and final experiment, our intention was to assess PF-XAB's performance in achieving balance between personalisation and generalisation across the federated landscape. Figure 3 indicates that PF-XAB successfully converges to optimal choices across different values of a, effectively demonstrating its proficiency in balancing the trade-off between personalisation and generalisation. This figure outlines the averaged per-step reward attained by the PF-XAB under varying values of a E [0, 1]. Tt benchmarks these results against. the theoretical maximuns for both global and local mean rewards, referred to as "best global" and "best local", respectively.
The analysis encompasses three definition of rewards: personalised, global, and local, each labeled accordingly and derived by clients' actions. At = 0, both personalised and global rewards align with the optimal global reward, while local rewards are significantly sub-optimal. As progressively increased, the personalised and local rewards trend up, indicating shift in focus towards optimizing local rewards, and simultaneously the global reward trends down. At a 1, both personalised and local rewards almost approximate the optimal local reward, while the global rewards are poor. This trend highlights the role of a in mediating a gradual balance between local and global reward optimization, suggesting its importance the strategic adjustment of reward focus.
M 10, T 5 x 107
Average Reward/Step
gloal
personafool
87
86-
Figure 3: PF-XAB averaged per-step reward over varying Personalised (green) adepts to while local (red) and global (purple) remain fixed. Bluc and yellow lincs show optimal local and global values.
13

---

Published in Transactions on Machine Learning Research (09/2024)
5 Conclusion
In this article we have introduced a new model for personalised, federated, bandit learning continuous action spaces, and proposed an effective solution method utilising hierarchical partitioning, batched decision- making and optimism in the face of uncertainty. Our approach achieves a sublinear regret (evidenced both theoretically and empirically) and requires minimal communication ensuring a good level of privacy in the lederated regime.
Our method shows near-deterministic behaviour in certain problems: notice little variability in its regret. This is likely result of its phased structure- the main decisions (climinations) of the policy made during the small number of communication rounds. If the outcomes of these decisions are identical samne across replications, the expected regret will also coincide. Future work may do well do explore whether there is scope to speed up exploration through the use randomised policy, c.g. a variant Thompson Sampling for continuous spaces (Kandasamy et al. 2018 Grant Leslie, 2020), or through the use of ideas from Bayesian Optimisation (Frazier 2018 which have also proven successful X--areddtyype problems, particularly with smooth functions.
Acknowledgments
The authors acknowledge financial support from the Engineering and Physical Sciences Research Council (studentship ref. 2437073, http///tikiiiiiooooo//o//oossoaa
References
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finito-time analysis of the multiarmed bandit problem. Machine learning, 47:235 256, 2002.
Peter Bartlett, Victor Gabillon, and Michal Valko. A simple parameter-free and adaptive approach optimization under minimal local smoothness assumption. In Algorithmic Learning Theory, pp. 184-206. PMLR, 2019.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
Peter I Frazier. A tutorial bayesian optimization. arXiv preprint arXiv:1807.02811 2018.
Mohammed Gheshlaghi Azar, Alessandro Lazaric, and Emma Brunskill. Online stochastic optimization under correlated bandit feedback. International Conference on Machine Learning, pp. 1557-1565. PMLR, 2014.
James Grant and David Leslie. On thompson sampling for smoother-thand than--shtta bandits. In International Conference on Artificial Intelligence and Statistics, pp. 2612 2622. PMLR, 2020.
Lean-Bastien Grill, Michal Valko, and Rémi Munos. Black-bos optimization of noisy functions with unknown smoothness. Advances in Neural Information Processing Systems, 28, 2015.
Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. ar preprint arXiv:2002.05511 2020.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34:27057-27068, 2021.
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabás Póczos. Parallelised bayesian optimisation via thompson sampling. In International Conference on Artificial Intelligence and Statistics, pp. 133 142. PMLR, 2018.
Robert Kleinberg, Alcksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. Proceedings of the fortieth annual ACM symposium Theory of computing, pp. 681-690 2008.
14

---

Published in Transactions on Machine Learning Research (09/2024)
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arviv preprint 16100:6610.00000 05499, 2016.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Wenjie Li, Qifan Song, and Jean Honorio. Personalized federated x-armed bandit. International Conference on Artificial Intelligence and Statistics, pp. 37-45. PMLR, 2024a.
Wenjie Li, Qifan Song, Jean Honorio, and Guang Lin. Federated x-armed bandit. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 13628- 13628-13636, 2024b.
Qiuhua Liu, Xuejun Liao, and Lawrence Carin. Semi-supervised multitask learning. Advances in Neural Information Processing Systems, 20, 2007.
Chenxin Ma, Jakub Konečný, Martin Jaggi, Virginia Smith, Michael Jordan, Peter Richtárik, and Martin Takáč. Distributed optimization with arbitrary local solvers. optimization Methods and Software, 32(4): 813 848, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp- 1273-1282, PMLR, 2017.
Clémence Réda, Sattar Vakili, and Emilie Kaufmann. Near-optimal collaborating learning in bandits. Advances in Neural Information Processing Systems, 35:14183 55:14183-14195, 2022.
Sashank J Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póezós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint arXiv: 1608. 008.06879. 2016.
Sudeep Salgia, Sattar Vakili, and Qing Zhao. Collaborative learning in kernel- bandits for distributed users. IEEE Transactions Signal Processing, 2023.
Ohad Shamir, Nati Srebro, and Tong Zhang. Commuicattion-fffiiett distributed optimization using an approximate newton-type method. In International conference on machine learning, pp. 1000 1008. PMLR, 2014.
Xuedong Shang, Emilie Kaufmann, and Michal Valko. General parallel optimization without metric. In Algorithmic Learning Theory, pp. (62-788. PMIR,, 2019.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35.11, pp. 9603-9611, 2021.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. Tn International Conference on Artificial Intelligence and Statistics, pp. 2917 2925. PMLR, 2021.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. Advances in Neural Information Processing Systems, 30, 2017.
Michal Valko, Alexandra Carpentier, and Rémi Munos. Stochastic simultaneous optimistic optimization. In International Conference on Machine Learning, pp. 19-27. PMLR, 2013.
Qiong Wu, Kaiwen He, and Xu Chen. Personalized federated learning for intelligent iot applications: A cloud-edge based framework. IEEE Open Journal of the Compuler Sociely, 1:35 2020.
Yuchen Zhang and Xiao Lin. Disco: Distributed optimization for self-concordant empirical loss. In International conference on machine learning, pp. 362 370. PMI.R, 2015.
15


Reviews:
[{"review_id": "ZzGm48gpO8", "reviewer": "Reviewer_SYhh", "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": "Strengths:\n- The paper is well-written and the setting is well-motivated\n- The paper proposes a theoretical analysis of the regret of the proposed PF-XAB algorithm\n- The paper validates experimentally the superiority of PF-XAB in the personalised setting (i.e. $\\alpha \\neq 0$), compared to algorithms either tailored for local or global objectives under both synthetic and real-world datasets.\n\n\nWeakness:\n- The challenges/specific hardness of this setting compared to that of [Shi et al. (2021)] and [Li et al. (2024a)] are not fully addressed.\n- The paper affirms that PF-XAB maintains a “logarithmic communication cost”. However, a rigourous analysis of the communication cost of PF-XAB is missing in the paper.\n- The paper claims at the end of Section 3 that the regret of PF-XAB would retrieve the same regret upper bound of [Li et al. (2024a)] if the two additional assumptions from [Li et al. (2024a)] were added. However, this claim is not obvious, and no rigorous/sketch proof is provided.\n- The regret upper bound mainly depends on the parameter $d’$, which seems hard to parse. Specifically, how does this quantity relate to $d_m$ in [Li et al. (2024a)] and to $d’$ in [Bubeck et al. (2011)]?\n- The regret upper bound hides the dependence on the “personalisation parameter” $\\alpha$, which seems to be a critical quantity.\n- No regret lower bounds are provided for this setting.", "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": "This paper studies federated X-armed bandits, where a set of clients want to optimise a convex combination between their local and global objectives controlled by a “personalisation parameter” $\\alpha$. The paper proposes an elimination-based algorithm PF-XAB which enjoys a sublinear regret $\\tilde{O}(T^\\frac{d’+2}{d’ + 3})$ where $d’$ is a quantity related to the near-optimality dimension.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The requested changes are answers to the weakness above. Specifically:\n- A paragraph on the challenges of this setting in comparison to [Shi et al. (2021)] and [Li et al. (2024a)]. Specifically, [Shi et al. (2021)] studies the same mixed objective, but for finite-armed bandits. Does the hardness of your setting reduce to the hardness of going from finite-armed to X-armed bandits in [Shi et al. (2021)]?\n- A communication cost analysis of the PF-XAB algorithm, with the number of communication rounds explicit with respect to the parameters of PF-XAB\n- A proof that PF-XAB retrieves the same regret upper bound as [Li et al. (2024a)] with the additional two assumptions.\n- A discussion on the parameter $d’$ in the regret upper bound. Both a theoretical/experimental intuition about this parameter may be valuable. Also, comparing how this quantity relates to similar quantity appearing in regret upper bounds of X-armed bandits ([Li et al. (2024a)], [Bubeck et al. (2011)]) is interesting.\n- A discussion on the effect of $\\alpha$ on the regret upper bound.\n- Even if the regret lower bound for this specific setting seems to be left as an open problem, a discussion on the lower bounds in similar settings ([Bubeck et al. (2011)], [Shi et al. (2021)] and [Li et al. (2024b)]) and how they relate to your upper bound may provide valuable insights on the hardness of this setting.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZPQFC7rHAL", "reviewer": "Reviewer_TZgT", "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": "**Strengths:**\n- The paper builds on [Li et al 2024a,b] and proposes an algorithm that can deal with different levels of personnalisation (controlled by the parameter $\\alpha$) while working for heterogeneous settings (requires less assumptions). \n- The proposed algorithm was theoretically analysed, enjoys a sub-linear regret and is simple to run.\n- The algorithm was tested on some settings and shows good performance.\n- The writing is good and the paper is easy to follow.\n\n**Weaknesses:**\n- The paper can benefit from better positioning in the literature, especially in comparison to [Li et al 2024a,b]. The contribution can seem very incremental, and discussions about what makes the convex combination problem more difficult should be included. For example, the differences in the technical solutions are not discussed: Is your algorithm an adaptation of the previous ones [Li et al 2024a,b]? Where does the difficulty reside? These insights will make the paper richer.\n\n- The proposed algorithm was analysed theoretically and presents a sub-linear regret that deteriorates the rate of previous approaches. This is not an issue as it is supposed to solve a more general problem. This deterioration seems to come from the drop of the homogeneity assumptions and it would be nice to have a discussion on this, even a proof in the appendix. The rate also depends on the the constant $d$ that is not much discussed. What is its value in simple problems? is $d$ very big to the point of getting linear regret? Is there a way to control its value?\n\n- The experimental section shows good performance for the proposed methods, but does not make much sense for the baselines. If we restrict ourselves to the first experiment, we should expect that $\\alpha \\rightarrow 0$ would make Fed-PNE work better than PF-PNE as it is tailored to solve the global objective, and $\\alpha \\rightarrow 1$ will make the newly proposed method and PF-PNE comparable. This is not the case as Fed_PNE is always performing poorly in $\\alpha \\rightarrow 0$ and PF-PNE shows **worse than linear regret** in $\\alpha \\rightarrow 1$, which are favorable cases for the algorithms. Is there any explanation to this?\n\n- The experimental section would benefit from more experiments. It would be also nice to have different settings with different constants $d$ and different levels of heterogeneity to understand the differences between the algorithms better and quantify their impact on the regret.\n\n- Small typo/ unclear definition: I do not understand the notation with which you define $\\mathcal{P}_{h, i}$, are there missing indices in the union?", "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": "The authors propose a personalised, federated learning approach building on the $\\mathcal{X}$-armed bandit literature that can solve for convex combinations between local and global objectives. This approach generalises the work of [Li et al 2024a,b] as it can be applied for flexible levels of personnalisation, while relying on weaker assumptions about the homogeneity of the data. The proposed algorithm is analysed theoretically and shows good performance empirically.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The changes that can improve the paper are answers for the weaknesses discussed above:\n- Discussion of the proof techniques used and their difference with previous ones in [Li et al 2024a,b].\n- Discussion of the regret rate, impact of $d$, value of $d$ in simple problems, ways to control it.\n- Making the baselines work for their respective settings.\n- Adding more experiments, quantify the impact of $d$ and heterogeneity on all methods.\n- Correcting the small typo.\n\n\nFor now, I am not convinced that the experimental section supports enough the claims of the paper, however, improving it will surely make the paper ready for publication.", "broader_impact_concerns": "I do not find any ethical concerns about this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "htZeW7WGjZ", "reviewer": "Reviewer_Gsth", "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": "Strengths:\n- This work is a valid extension of PF-MAB to $\\chi$-armed bandits.\n\n- The study is complete with algorithm designs, theoretical analysis and experimental results.\n\n- The overall presentation is satisfying and has explained the problem/algorithm/result clearly.\n\nWeakness:\n- The main issue in my mind is that the adopted techniques to handle personalization seems to be exactly from Shi et al. 2021, i.e., the designed exploration lengths, the phased-elimination-algorithm, etc. Then, I believe the main challenge is from the $\\chi$-armed bandits, however, the challenges and contributions are not sufficiently illustrated and highlighted.\n\n- The result is not explained enough, especially its tightness. See the required changes.", "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": "- This work extends the previous study on federated bandits with personalization to the setup of $\\chi$-armed bandits.\n\n- To achieve flexible personalization, an algorithm termed PF-XAB is proposed, which is a phase-elimination-style algorithm with explorations designed to match the desired personalization level.\n\n- Theoretical analyses are provided for PF-XAB, demonstrating its efficiency, which are further corroborated with experimental results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- For the first point in weakness, I believe it is necessary to have a more in-depth illustration of the contributions of this work, rather than extending PF-MAB to PF-XAB. The technical difficulties and novelties of handing PF-XAB should be highlighted, besides the seemingly standard algorithmic framework from PF-MAB.\n\n- I would encourage a more in-depth illustration of the theoretical results.\n  -  For example, the instance-dependent bound of Shi et al. 2021 seems to have a complete discussion on the impact of the personalization level $\\alpha$ which defines the suboptimality gaps; however in Theorem 3.8 seems to have no dependency on $\\alpha$, making it less interpretable. \n  - As I am not an expert in $\\chi$-armed bandits, I would look forward to seeing comparisons with the regret scale therein (e.g., for MAB, it is typically the form of $\\log(T)/\\Delta$ or $\\sqrt{T}$). The current comparison with Li et al. 2024a should also be expanded to include a full context on the more restrictive assumptions therein and why the proposed PF-XAB can achieve a similar order bound.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Rrw3SodMqq", "reviewer": "Reviewer_XxWU", "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": "## Strengths\n1. The overall writing of the paper, aside from the pseudocode (which I address in requested changes), is clear and easy to follow.\n2. The $\\mathcal{X}$-armed bandit (XAB)-based federated learning (FL) framework with a personalization parameter makes sense, and the proposed PF-XAB algorithm fits naturally within this framework and is intuitive.\n3. The authors provide theoretical guarantees for the regret of their algorithm, offering a proof (while not novel) that shows sub-linear regret.\n\n## Weaknesses and questions\n1. From what I understood, the clients and server are working asynchronously. If some clients are faster at sampling their local objectives than others, they will be forced to greedily exploit the best arm (i.e., $\\left(h_p, i_p\\right)$) while waiting for slower clients to finish. How is this scenario accounted for in the regret analysis? Couldn’t the faster clients end up playing suboptimal arms repeatedly due to delays from slower clients? Or is there an implicit assumption that all clients operate at the same \"speed\"?\n   \n2. **Experiment section**:\n    1. In the first plot of Figure 1, it appears that if the simulation ran longer, PF-XAB’s regret might eventually exceed that of PF-PNE. Is this expected behavior, and if so, why?\n    2. In all the plots from Figure 1, there is a noticeable bump in PF-XAB’s regret around $t=40 \\times 10^4$, $30 \\times 10^4$, and $20 \\times 10^4$ respectively. Could the authors clarify the reason behind these bumps?\n    3. In the real-world classification scenario, instead of showing cumulative regret, it would be more informative to see the average AUC-ROC score for each algorithm. Could the authors provide such results?\n\n3. The global objective is currently defined as a simple average of local objectives, which might be restrictive in practice. Could a weighted average or other monotone-increasing functions (with smoothness assumptions) be used instead?\n\n4. Could the authors clarify how their algorithm addresses privacy concerns? The authors mention that the server receives $\\bar{\\mu}_{(h, i), m}$ from each client $m$ for every node $(h, i)$ in every round. Given this, wouldn’t the server have enough information to reconstruct the rewards obtained by individual clients at each step?\n\n5. The paper would benefit from a concrete example to ground the theoretical concepts, such as in the smart home or healthcare domains mentioned in the introduction. Could the authors provide a detailed case where they define the context space $\\mathcal{X}$, the local objectives $\\mu_m$ for each client, and explain what the personalized objective would represent in that scenario?\n\n6. The algorithm needs knowledge of the smoothness parameters. A natural question is how robust is the algorithm to parameter mismatches? Specifically, if parameters related to local smoothness such as $\\nu_1$ and $\\rho$, and thus $H$ are not precisely known for a given problem, how does this affect the performance of the algorithm?", "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 authors propose an $\\mathcal{X}$-armed bandit-inspired federated learning (FL) framework that balances local user preferences with aggregated global knowledge. In this framework, each user has a local objective function, and the global objective is the average of these local objectives. The personalized objective for each user is then a combination of their local objective and the global objective, controlled by a personalization parameter.\n\nThe authors also introduce the PF-XAB algorithm, an $\\mathcal{X}$-armed bandit-based approach designed to maximize the personalized objective through information exchange between clients and a central server. They prove that PF-XAB achieves a sub-linear regret bound and demonstrate through experiments that it outperforms existing FL $\\mathcal{X}$-armed bandit algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I found the pseudocode of the algorithms difficult to parse. It may help to break down each phase (e.g., local exploration, exploitation, etc.) in the text, with a few explanatory sentences that reference the relevant variables/statements in the pseudocode.\n\n## Questions:\n1. What does capital $P$ in the pseudocode represent?\n2. It would be helpful to include a discussion of the algorithm’s space and time complexities for both the client and server sides. For example, the number of nodes in the tree appears to grow exponentially in $H$, and thus polynomial in $T$. Is that correct?\n\n## Minor comments:\n- There is a missing space after the period in the phrase \"remains partially unobservable to individual clients.\", which occurs just before Section 2.2.\n- There’s a typo in the sentence \"It **broadcast** active nodes\" at the start of Section 3.1. (Should be broadcasts).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As explained above, reviewers all agree that the paper meets both the "claims and evidence" and "audience" criteria for acceptance in TMLR. I agree with the reviewers' assessment.
Decision: Accept (poster)