##  Appendix F Further Discussions

In this section, we provide more details on our privacy notion and algorithm
design.

###  F.1 Silo-level LDP/SDP vs. Other Privacy Notions

In this section, we compare our silo-level LDP and SDP with standard privacy
notions for single-agent LCBs, including local, central, and shuffle model for
DP, respectively.

Silo-level LDP vs. single-agent local DP. Under standard LDP for single-agent
LCBs [ZCHLW20, DJW13, ZT21], each user only trusts herself and hence
privatizes her response before sending it to the agent. In contrast, under
silo-level LDP, each local user trusts the local silo (agent), which aligns
with the pratical situations of cross-silo FL, e.g., patients often trust the
local hospitals. In such cases, standard LDP becomes unnecessarily stringent,
hindering performance/regret and making it less appealing to cross-silo
federated LCBs.

Silo-level LDP vs. single-agent central DP. The comparison with standard
central DP for single-agent LCB (e.g., [SS18]) is delicate. We first note that
under both notions, users trust the agent and the privacy burden lies at the
agent. Under standard central DP, the agent uses private statistics until
round $t$ to choose action for each round $t$, which ensures that any other
users $t^{\prime}\neq t$ cannot infer too much about user $t$’s information by
observing the actions on rounds $t^{\prime}\neq t$ (i.e., joint differential
privacy (JDP) [KPRU14])121212As shown in [SS18], JDP relaxation is necessary
for achieving sub-linear regret for LCBs under the central model.. On the
other hand, silo-level LDP does not necessarily require each agent (silo) to
use private statistics to recommend actions to users within the silo. Instead,
it only requires the agent to privatize its sent messages (both schedule and
content). Thus, silo-level LDP may not protect a user $t$ from the colluding
of all other users within the _same_ silo. In other words, the adversary model
for silo-level LDP is that the adversary could be any other silos or the
central server rather than other users within the same silo. Note that the
same adversary model is assumed in a similar notion for federated supervised
learning (e.g., inter-silo record-level differential privacy (ISRL-DP) in
[LR21]). In fact, with a minor tweak of our Algorithm 1, one can achieve a
slightly stronger notion of privacy than silo-level LDP in that it now can
protect against both other silos/server and users within the same silo. The
key idea is exactly that now each agent will only use private statistics to
recommend actions, see Appendix F.2.

Silo-level LDP vs. Federated DP in [DP20]. In [DP20], the authors define the
so-called notion of _federated DP_ for federated LCBs, which essentially means
that “the action chosen by any agent must be sufficiently impervious (in
probability) to any single data from any other agent”. This privacy guarantee
is directly implied by our silo-level LDP. In fact, in order to show such a
privacy guarantee, [DP20] basically tried to show that the outgoing
communication is private, which is the idea of silo-level LDP. However, as
mentioned in the main paper, [DP20] only privatizes the communicated data and
fails to privatize the communication schedule, which leads to privacy leakage.
Moreover, as already mentioned in Remark A.1, Fed-DP fails to protect a user’s
privacy even under a reasonable adversary model. Thus, we believe that silo-
level LDP is a better option for federated LCBs.

SDP vs. single-agent shuffle DP. Under the single-agent shuffle DP [CZ22a,
TKMS23], the shuffler takes as input a batch of users’ data (i.e., from
$t_{1}$ to $t_{2}$), which enables to achieve a regret of
$\widetilde{O}(T^{3/5})$ (vs. $\widetilde{O}(T^{3/4})$ regret under local
model and $\widetilde{O}(\sqrt{T})$ regret under central model). In contrast,
under our SDP, the shuffler takes as input the DP outputs from all $M$ agents.
Roughly speaking, single-agent shuffle DP aims to amplify the privacy
dependence on $T$ while our SDP amplifies privacy over $M$. Due to this,
single-agent shuffle DP can directly apply a standard amplification lemma
(e.g., [FMT22]) or shuffle protocol (e.g., [CJMP21]) that works well with LDP
mechanism at each user (i.e., the size of dataset is $n=1$). In contrast, in
order to realize amplification over $M$ agents’ DP outputs, we have to
carefully modify the standard amplification lemma to handle the fact that now
each local mechanism operates on $n>1$ data points, which is one of the key
motivations for our new amplification lemma.

###  F.2 A Simple Tweak of Algorithm 1 for a Stronger Privacy Guarantee

As discussed in the last subsection, the adversary model behind silo-level LDP
only includes other silos and the central server, i.e., excluding adversary
users within the same silo. Thus, for silo-level LDP, Algorithm 1 can use non-
private data to recommend actions within a batch (e.g., $V_{t,i}$ includes
non-private recent local bias vectors and covariance matrices). If one is also
interested in protecting against adversary users within the same silo, a
simple tweak of Algorithm 1 suffices.

Algorithm 8 Priv-FedLinUCB-Lazy

1: Parameters: Batch size $B\in\mathbb{N}$, regularization $\lambda>0$,
confidence radii $\\{\beta_{t,i}\\}_{t\in[T],i\in[M]}$, feature map
$\phi_{i}:\mathcal{C}_{i}\times\mathcal{K}_{i}\to\mathbb{R}^{d}$, privacy
protocol $\mathcal{P}=(\mathcal{R},\mathcal{S},\mathcal{A})$

2: Initialize: For all $i\in[M]$, $W_{i}=0,U_{i}=0$,
$\widetilde{W}_{\text{syn}}=0$, $\widetilde{U}_{\text{syn}}=0$

3: for $t\\!=\\!1,\ldots,T$ do

4: for each agent $i=1,\ldots,M$ do

5: $V_{t,i}=\lambda I+\widetilde{W}_{\text{syn}}$,
$\widehat{\theta}_{t,i}=V_{t,i}^{-1}\widetilde{U}_{\text{syn}}$

6: Play arm
$a_{t,i}\\!=\\!\mathop{\mathrm{argmax}}_{a\in\mathcal{K}_{i}}\langle\phi_{i}(c_{t,i},a),\widehat{\theta}_{t,i}\rangle+\beta_{t,i}\left\lVert\phi_{i}(c_{t,i},a)\right\rVert_{V_{t,i}^{-1}}$
and set $x_{t,i}=\phi_{i}(c_{t,i},a_{t,i})$

7: Observe reward $y_{t,i}$

8: Update $U_{i}=U_{i}+x_{t,i}y_{t,i}$ and $W_{i}=W_{i}+x_{t,i}x_{t,i}^{\top}$

9: end for

10: if $t\ \mathrm{mod}\ B=0$ then

11: // Local randomizer $\mathcal{R}$ at _all_ agents $i\in[M]$

12: Send randomized messages
$R_{t,i}^{\text{bias}}=\mathcal{R}^{\text{bias}}(U_{i})$ and
$R_{t,j}^{\text{cov}}=\mathcal{R}^{\text{cov}}(W_{i})$ to the shuffler

13: // Third party $\mathcal{S}$

14: $S_{t}^{\text{bias}}=\mathcal{S}(\\{R_{t,i}^{\text{bias}}\\}_{i\in[M]})$
and $S_{t}^{\text{cov}}=\mathcal{S}(\\{R_{t,i}^{\text{cov}}\\}_{i\in[M]})$

15: // Analyzer $\mathcal{A}$ at the server

16: Construct private cumulative statistics
$\widetilde{U}_{\text{syn}}=\mathcal{A}^{\text{bias}}(S_{t}^{\text{bias}})$
and $\widetilde{W}_{\text{syn}}=\mathcal{A}^{\text{cov}}(S_{t}^{\text{cov}})$

17: // _All_ agents $i\in[M]$

18: Receive $\widetilde{W}_{\text{syn}}$ and $\widetilde{U}_{\text{syn}}$ from
the server

19: Reset $W_{i}=0$, $U_{i}=0$

20: end if

21: end for

As shown in Algorithm 8, the only difference is a lazy update of
$\widehat{\theta}_{t,i}$ is adopted (line 5), i.e., it is only computed using
private data without any dependence on new non-private local data. In fact,
same regret bound as in Theorem 6.1 can be achieved for this new algorithm
(though empirical performance could be worse due to the lazy update). In the
following, we highlight the key changes in the regret analysis. It basically
follows the six steps in the proof of Lemma B.2. One can now define a mapping
$\kappa(t)$ that maps any $t\in[T]$ to the most recent communication round.
That is, for any $t\in[t_{k-1},t_{k}]$ where $t_{k}=kB$ is the $k$-th
communication round, we have $\kappa(t)=t_{k-1}$. Then, one can replace all
$t$ in $V_{t,i}$ and $G_{t,i}$ by $\kappa(t)$. The main difference that needs
a check is Step 4 when bounding the regret in good epochs. The key is again to
establish a similar form as (5). To this end, note that for all
$t\in[t_{k-1},t_{k}]$ $V_{k}\succeq\bar{V}_{t,i}$ and
$G_{\kappa(t),i}+\lambda_{\min}I=V_{k-1}$, which enables us to obtain
$\left\lVert
x_{t,i}\right\rVert_{(G_{\kappa(t),i}+\lambda_{\min}I)^{-1}}\leq\sqrt{2}\left\lVert
x_{t,i}\right\rVert_{\bar{V}_{t,i}^{-1}}$. Following the same analysis yields
the desired regret bound.

###  F.3 Non-unique Users

In the main paper, we assume all users across all silos and $T$ rounds are
unique. Here, we briefly discuss how to handle the case of non-unique users.

  * •

The same user appears multiple times in the same silo. One example of this
could be one patient visiting the same hospital multiple times. In such cases,
one needs to carefully apply group privacy or other technique (e.g., [CZ22a])
to characterize the privacy loss of these returning users.

  * •

The same user appears multiple times across different silos. One example of
this could be one patient who has multiple records across different hospitals.
Then, one needs to use adaptive advanced composition to characterize the
privacy loss of these returning users.

##  Appendix G Additional Details on Simulation Results

(a) Synthetic data (varying $\varepsilon$, $\delta=0.1)$

(b) Synthetic data (varying $\delta$, $\varepsilon=5$)

(c) Real data (varying $\varepsilon$, $\delta=0.1)$

(d) Real data ($M=100$)

Figure 3: Comparison of time-average group regret for FedLinUCB (non-private)
and LDP-FedLinUCB (i.e., under silo-level LDP) on (a, b) synthetic Gaussian
bandit instance and (c,d) bandit instance generated from MSLR-WEB10K Learning
to Rank dataset.

In Figure 3, we compare regret performance of LDP-FedLinUCB with FedLinUCB
under varying privacy budgets.131313All existing non-private federated LCB
algorithms (e.g., [WHCW20]) adopts adaptive communication. We refrain from
comparing with those to maintain consistency in presentation. In sub-figure
(a), we plot results for $\delta=0.1$ and varying level of
$\varepsilon\in\\{0.2,1,5\\}$ on synthetic Gaussian bandit instance, wherein
sub-figure (b), we plot results for $\varepsilon=5$ and varying level of
$\delta\in\\{0.1,0.01,0.001\\}$. In sub-figure (c), we plot results for
$\delta=0.1$ and varying level of $\varepsilon\in\\{0.2,1,5\\}$ on bandit
instance generated from MSLR-WEB10K data by training a lasso model on
bodyfeatures ($d=78$). In all these plots, we observe that regret of LDP-
FedLinUCB decreases and, comes closer to that of FedLinUCB as
$\varepsilon,\delta$ increases (i.e., level of privacy protection decreases),
which support our theoretical results. Here, we don’t compare SDP-LinUCB (with
privacy amplification) since its privacy guarantee holds for
$\varepsilon,\delta\ll 1$. Instead, we do so in sub-figure (d) with
$\varepsilon=\delta=0.0001$. Here also, we observe a drop in regret of SDP-
FedLinUCB compared to that of LDP-FedLinUCB.