11institutetext: School of Computer Science and Eng., The Hebrew University of
Jerusalem, Israel 22institutetext: Sagol Brain Institute, Tel Aviv Sourasky
Medical Center, Israel 33institutetext: Department of Biomedical Engineering,
Tel Aviv University, Israel 44institutetext: Division of Pediatric Radiology,
Tel Aviv Sourasky Medical Center, Tel Aviv, Israel 55institutetext: Sackler
Faculty of Medicine, Tel Aviv University, Israel 66institutetext: Sagol School
of Neuroscience, Tel Aviv University, Israel

# Test-time augmentation-based active learning and self-training for label-
efficient segmentation

Bella Specktor-Fadida 11 Anna Levchakov 22 Dana Schonberger 2233 Liat Ben-Sira
4455 Dafna Ben-Bashat 225566 Leo Joskowicz 11

###### Abstract

Deep learning techniques depend on large datasets whose annotation is time-
consuming. To reduce annotation burden, the self-training (ST) and active-
learning (AL) methods have been developed as well as methods that combine them
in an iterative fashion. However, it remains unclear when each method is the
most useful, and when it is advantageous to combine them. In this paper, we
propose a new method that combines ST with AL using Test-Time Augmentations
(TTA). First, TTA is performed on an initial teacher network. Then, cases for
annotation are selected based on the lowest estimated Dice score. Cases with
high estimated scores are used as soft pseudo-labels for ST. The selected
annotated cases are trained with existing annotated cases and ST cases with
border slices annotations. We demonstrate the method on MRI fetal body and
placenta segmentation tasks with different data variability characteristics.
Our results indicate that ST is highly effective for both tasks, boosting
performance for in-distribution (ID) and out-of-distribution (OOD) data.
However, while self-training improved the performance of single-sequence fetal
body segmentation when combined with AL, it slightly deteriorated performance
of multi-sequence placenta segmentation on ID data. AL was helpful for the
high variability placenta data, but did not improve upon random selection for
the single-sequence body data. For fetal body segmentation sequence transfer,
combining AL with ST following ST iteration yielded a Dice of 0.961 with only
6 original scans and 2 new sequence scans. Results using only 15 high-
variability placenta cases were similar to those using 50 cases. Code is
available at: https://github.com/Bella31/TTA-quality-estimation-ST-AL

###### Keywords:

Self-training Active learning Test-time augmentation Fetal MRI

##  1 Introduction

Segmentation of anatomical structures in CT and MRI scans is a key task in
many clinical applications. However, manual annotation requires expertise, is
tedious, time-consuming, and is subject to annotator variability. State-of-
the-art automatic volumetric segmentation methods are based on deep neural
networks. While effective, these methods require a large, high-quality dataset
of expert-validated annotations, which is difficult to obtain. A variety of
methods have been proposed to address annotation scarcity in semantic
segmentation [18].

Self-training (ST), also called pseudo-labeling, is a method for iterative
semi-supervised learning (SSL). In ST, a model improves the quality of the
pseudo-annotations by learning from its own predictions [4]. It is performed
by alternatively training two or more networks with an uncertainty-aware
scheme [4, 15, 18]. Nie et al. [13] describe an adversarial framework with a
generator segmentation network and a discriminator confidence network. Xia et
al. [20] propose a method for generating pseudo-labels based on co-training
multiple networks. Consistency regularization (CR) [3, 14], another popular
SSL method, relies on various perturbation techniques to generate disagreement
on the same inputs, so that models can be trained by enforcing prediction
consistency on unlabeled data without knowing the labeled information.

Active learning (AL) aims to identify the best samples for annotation during
training. The most common criterion for sample selection is based on
prediction uncertainty estimation, following the premise that more information
can be learned by the model using uncertain samples [2]. AL often uses
ensembled uncertainty measurements that require training multiple models or
Monte-Carlo dropout [9, 22]. Ensemble-based methods measure the agreement
between different models, with higher model disagreement potentially implying
more uncertainty and less informativeness. Jungo et al. [9] indicated the need
for subject-level uncertainty for quality estimation.

Segmentation quality estimation is used in ST to discard low-quality pseudo-
labels and in AL to select low-quality samples for manual annotation. Wang et
al. [19] show that aleatory uncertainty scoring with Test-Time Augmentations
(TTA) provides a better uncertainty estimation than test-time dropout-based
model uncertainty. They show that TTA helps to eliminate overconfident
incorrect predictions. Specktor et al. [16] discard low-quality pseudo-labels
for ST with TTA-based Dice estimation. Others use TTA-based error estimation
for AL with the Volume Overlap Distance and the Jensen-Shannon divergence [5,
7].

Frameworks that combine SSL and AL have been recently proposed for both
natural and medical images [6, 7, 8, 10, 12, 23]. Zhang et al. [23] propose a
closed loop pseudo-labeling and informative active annotation framework. Nath
et al. [12] describe a two-stage learning framework for each active iteration
where the unlabeled data is used in the second stage for semi-supervised fine-
tuning. Gaillochet et al. [7] applies cross-augmentation consistency during
training and inference at each iteration to both improve model learning in a
semi-supervised fashion and identify the most relevant unlabeled samples to
annotate next. However, these methods do not take into account the data
properties at each iteration. A key question remains whether it is always best
to combine SSL and AL, and when it is better to use each separately.

Recently, an offline self-training scheme with one or two teacher-student
iterations has been reported to yield superior segmentation results [21, 25].
It consists of teacher training on annotated data followed by pseudo-labels
generation on unlabeled data and student training that jointly learns from the
manual and the high-quality generated pseudo-labels.

In this paper we present a new human-in-the-loop method based on TTA for a
combined training of actively selected and offline-calculated self-trained
examples. It performs simultaneous computation of pseudo-labels for self-
training and segmentation quality estimation for an active selection of
samples and filtering of unreliable pseudo-labels. The method also uses border
slices annotations to improve the pseudo-labels and the quality estimation
accuracy.

##  2 Method

The method consists of: 1) training a teacher network on a small number of
examples; 2) training a student model using a fully-automatic ST module
(optional); 3) training a second student model with a combined AL and ST
module using the base network from step 1 or 2. The combined AL and ST
iteration is performed either directly after the initial model training or
after ST iteration.

###  2.1 ST module

The fully automatic ST iteration is optionally performed before the combined
AL and ST module iteration. It uses soft teacher predictions instead of hard
teacher predictions, as these were found to perform better [1, 24]. See the
Supplementary Material (Section 1, Table A1). The pseudo-labels are either
network predictions without post-processing (soft network predictions) or TTA
predictions medians for each voxel, depending on the benefit of using TTA for
a given segmentation task. Unreliable training examples are filtered out with
quality estimation ranking using a threshold. The threshold is selected so
that the number of pseudo-labels will be at least the same as the number of
labeled examples.

The student self-training network is trained with the original data of the
initial network and with the new self-training examples using an optimization
scheme with learning rate restarts [11].

####  2.1.1 TTA-based quality estimation:

The quality estimation is obtained by computing the mean Dice score between
the median prediction and each of the augmentation results [16]. For TTA we
use flipping, rotation, transpose and contrast augmentations. A median
prediction is first assigned for each voxel, and then the estimated Dice score
is obtained by computing the median Dice score between the median and each one
of the augmentation results.

Figure 1: Flow diagram of the combined active learning and self-training
method illustrated on the placenta (dark green). The human annotation steps
are marked in yellow; light green steps are automatic.

###  2.2 Combined AL and ST module

The combined AL and ST module consists of five steps: 1) TTA inference is
performed with a base network; 2) border slices of the region of Interest
(ROI) are annotated for the TTA inference data; 3) cases are selected for
annotation and unreliable pseudo-labels are filtered using TTA-based quality
estimation on the slices of the structure of interest; 4) manual correction of
the selected cases is performed for annotation; and 5) training is performed
with the newly selected annotated cases, existing annotated cases, and
additional ST cases.

The new network uses the original data in combination with new actively
selected cases and pseudo-labels. Let $D$ be the set of all cases. The
training set $D_{train}\subset D$ is $D_{train}=D_{base}\cup D_{AL}\cup
D_{ST}$, where $D_{base}$ is the set of training examples of the initial
network, $D_{AL}$ is the set of actively selected examples, and $D_{ST}$ is
the set of selected pseudo-labeled examples. Training is performed by fine-
tuning the base network with learning rate restarts optimization [11].

Fig. 1 illustrates the process of generating the new training datasets
$D_{AL}$ and $D_{ST}$. The process includes: 1) segmentation inference with
TTA using the base network; 2) calculation of the median of TTA results for
each voxel (soft median prediction) and thresholding with t=0.5 to produce the
final median prediction mask (median prediction); 3) manual annotation of
border slices; 4) TTA Dice estimation and ranking of new unlabeled cases by
estimated Dice metric; 5) selection of cases with the lowest estimated Dice
for annotation, and from the rest of the cases selection of pseudo labels
above an estimated Dice threshold; 6) manual annotation of the actively
selected cases.

Both the AL and ST cases use the quality estimation method described in [10],
similar to the quality estimation in the fully automatic self-training module.
The cases with the lowest estimated Dice score are selected for annotation and
cases with estimated quality above a threshold are used as pseudo-labels. See
the Supplementary Material for illustrations (Section 2, Fig. A1-A2).

###  2.3 Border Slices Annotation

For this human-in-the-loop method, various types of manual annotations are
performed on the unlabeled cases. To decrease errors in the background slices
outside of the structure of interest, the uppermost and lowermost slices of
the ROI that includes the structure of interest are manually selected by the
annotator [17]. This is an easy task that, and unlike segmentation
annotations, can be quickly performed for a large number of cases. These
annotations are used to correct the self-training result outside of the
structure of interest and to estimate more accurately the Dice score in the
selected region.

##  3 Experimental Results

To evaluate our method, we retrospectively collected fetal MRI scans and
conducted three studies. The fetal MRI body scans were acquired with the
FIESTA and the TRUFI sequences as part of routine fetal assessment of fetuses
with gestational ages (GA) of 28-39 weeks from the Tel-Aviv Sourasky Medical
Center, Israel. They included the segmentation of the fetal body or the fetal
placenta.
Datasets and Annotations: The FIESTA sequence fetal body dataset consists of
104 cases acquired on a GE MR450 1.5T scanner with a resolution range of
$1.48-1.87\times 1.48-1.87\times 2-5.0$ $mm^{3}$. The TRUFI sequence fetal
body dataset consists of 101 cases acquired on Siemens Skyra 3T, Prisma 3T,
and Aera 1.5T scanners, with a resolution range of $0.6-1.34\times
0.6-1.34\times 2-4.8$ $mm^{3}$.

The placenta in-distribution (ID) dataset includes 88 cases, 50 TRUFI and 38
FIESTA. The TRUFI scans were acquired on Siemens Prisma and Vida scanners with
a resolution of $0.781\times 0.781\times 2$ $mm^{3}$. The FIESTA sequence
scans were acquired on a GE MR450 1.5T scanner with a resolution range of
$1.48-1.87\times 1.48-1.87\times 2-5.0$ $mm^{3}$. For placenta segmentation,
an additional Out-Of-Distribution (OOD) dataset with 24 TRUFI scans and
restricted field of view not including the entire placenta was used. The OOD
cases were acquired with Siemens Prisma and Vida scanners with a resolution of
$0.586\times 0.586\times 4$ $mm^{3}$.

Both the annotations and the corrections were performed by a clinical trainee.
All segmentations were validated by an expert fetal radiologist with >20 years
of experience in fetal imaging.
Studies: We conducted three studies, two with fetal body segmentation data and
one with placenta data. To address the high variability in segmentation
quality of the low-data regime, we performed all the experiments with four
different randomizations and averaged between them. In all experiments, we
used 16 TTA variations. We evaluated the experiments with the Dice score, 2D
average symmetric surface distance (ASSD), and Hausdorff robust (95
percentile) metrics. A network architecture similar to Dudovitch et al. [5]
was utilized with the Keras and Tensorflow frameworks.
Study 1: We evaluate the performance of the ST method alone on the fetal body
segmentation ID and OOD data. Baseline networks with 6 training examples were
first trained with cases randomly selected from the 30 FIESTA scans dataset.
The ST was applied to the remaining 24 cases. Performance of the automatic ST
method was tested on 68 ID FIESTA scans and 58 OOD TRUFI scans. Since
sometimes longer training may result in improved performance [17], the
performance of the ST method was also compared to that of fine-tuned networks
without ST using learning rate restarts optimization scheme.

Figure 2: Experimental results for the self training method on FIESTA ID and
TRUFI OOD data averaged across four runs. Dots represent the mean Dice scores;
grey bars show the minimum and the maximum; standard deviation: ID data (blue
bar), OOD data (green bar). FT: Fine-tuning, ST: Self-training. Comparison
between (x-axis): 1) 6 training examples (baseline); 2) 6 training examples
with FT; 3) 6 training examples with ST 4) 30 training examples; 5) 30
training examples with FT

For ID data, using self-training (ST) improved the Dice score from 0.964 to
0.971, the ASSD from 1.88 $mm$ to 1.52 $mm$ and the Hausdorff distance from
6.15 $mm$ to 4.8 $mm$. For the OOD data, the difference in performance was
higher, with the self-training method improving the Dice score from 0.920 to
0.941, the ASSD from 4.7 $mm$ to 3.67 $mm$, and the Hausdorff distance from
21.01 $mm$ to 15.76 $mm$. Fig. 2 shows the results with the Dice score. The
self-training also improved the standard deviation from 0.04 to 0.023 and from
0.06 to 0.036 for ID and OOD data respectively, and achieved the same
performance of a network trained on manually segmented 30 cases for both ID
and OOD data.

Study 2: We evaluate the performance of the combined AL and ST method for
FIESTA to TRUFI sequence transfer for fetal body segmentation. We subsequently
performed sequence transfer for the TRUFI sequence using the ST network from
the previous experiment as the initial network. To evaluate the differences in
performance between the four runs, this time we calculated the average, STD,
minimum, and maximum for the average performance of each one of the runs. We
added either: 1) 3 additional randomly selected TRUFI scans; 2) 3 additional
AL TRUFI scans; 3) 3 additional AL TRUFI scans in combination with ST, or; 4)
2 additional AL TRUFI scans in combination with ST and with border slices
annotations. We also obtained results for: 5) a network trained without the
automatic ST step using 3 additional TRUFI AL scans and with ST that includes
border slices annotations, and; 6) a baseline of 30 fully annotated TRUFI
scans.

Table 1: Fetal body segmentation results comparison with the Dice, Hausdorff 95 percentile and 2D ASSD metrics between: 1) 6 FIESTA cases and additional 3 randomly selected TRUFI scans; 2) 6 FIESTA cases and 3 additional actively selected TRUFI scans; 3) 6 FIESTA cases and 3 additional actively selected TRUFI scans in combination with ST; 4) 6 FIESTA cases and 2 additional actively selected TRUFI scans in combination with ST and with additional annotations of border slices. 5) a network trained without the automatic ST step using 6 FIESTA cases and 3 additional TRUFI actively selected scans with ST and border slices annotations, and; 6) a baseline of 30 fully annotated TRUFI scans. For (1-5), average $\pm$ STD and min-max range are listed for the four runs. | Dice | Hausdorff | ASSD
---|---|---|---
1\. 6 FIESTA + 3 TRUFI Random | $0.957\pm 0.005$ | $8.36\pm 0.35$ | $2.51\pm 0.28$
0.950-0.963 | 7.76-8.67 | 2.29-2.97
2\. 6 FIESTA + 3 TRUFI AL | $0.957\pm 0.003$ | $8.85\pm 0.74$ | $2.53\pm 0.14$
0.953-0.961 | 7.6-9.58 | 2.34-2.74
3\. 6 FIESTA + 3 TRUFI AL ST | $0.959\pm 0.002$ | $7.84\pm 1.16$ | $2.45\pm 0.15$
0.956-0.962 | 6.29-9.54 | 2.23-2.65
4\. 6 FIESTA + 2 TRUFI AL ST \w borders | $\textbf{0.961}\pm 0.001$ | $\textbf{6.40}\pm 0.41$ | $\textbf{2.20}\pm 0.14$
0.960-0.963 | 5.73-6.78 | 2.00-2.38
5\. 6 FIESTA + 3 TRUFI AL ST \w borders \wo ST iteration | $0.959\pm 0.003$ | $8.09\pm 1.14$ | $2.37\pm 0.25$
0.955-0.963 | 6.23-9.08 | 1.95-2.59
6\. 30 Baseline scans | 0.964 | 6.99 | 2.14

Table 1 lists the results. The best results were achieved using only two
additional labeled TRUFI scans with border slices annotations, yielding a mean
Dice score of 0.961, close to that of the 30 fully annotated TRUFI scans
baseline of 0.964. There was almost no difference between active versus random
scan selection. Using the combined AL and ST method without the automatic ST
step yielded very good results, although slightly worse than those of a
network trained following the ST step, despite an additional annotated TRUFI
scan. The worse network performance without the automatic ST iteration yielded
an average Dice score of 0.955 vs. 0.960 using the ST iteration.

Study 3: This study evaluates ST method and the combined AL and ST method on
the high-variability data of placenta segmentation with both FIESTA and TRUFI
sequences. Four initial networks were trained with 10 randomly selected
training examples out of the 50 FIESTA and TRUFI scans, with the rest 40 cases
used for ST and AL. The combined FIESTA and TRUFI data was split into 50/4/34
train/validation/test cases. An additional 24 scans were used for OOD data
validation. Again, we evaluated the average, STD, minimum, and maximum for the
average performances of the four runs. We compared between six scenarios: 1) a
baseline network trained on 10 scans; 2) a network trained on 10 initial scans
and additional ST scans; 3) a network trained on 10 initial scans and
additional 5 randomly selected scans; 4) a network trained with 10 initial
scans and additional 5 AL scans; 5) a network trained with 10 initial scans, 5
AL scans, and additional ST scans; 6) a network trained on 50 scans.

Table 2 lists the results. Using ST alone improved segmentation results from a
mean Dice score of 0.806 to 0.819 for ID data and from 0.641 to 0.703 for OOD
data. Using actively selected scans performed better than random selection,
with a much smaller STD, reaching the performance of a network trained on 50
annotated scans. For ID data, the mean and minimum average Dice scores with
actively selected scans were 0.827 and 0.819, respectively, and a mean and
minimum average Dice scores of random selection were 0.821 and 0.809,
respectively. For OOD data, the mean and minimum average Dice scores of
actively selected scans were 0.710 and 0.661, compared to a mean of 0.688 and
a minimum of 0.620 using random selection.

Combining ST with AL did not improve the results, except for the OOD data Dice
score STD, which was the lowest of all setups, and a minimum Dice score of
0.691, which was the highest. It slightly hurt performance on ID data,
indicating that ST might induce excessive noise in the pseudo-labels. Adding
automatic ST iteration may improve the pseudo-labels quality, but the effect
may be negligible as the results are already on-par with a network trained on
50 cases.

Table 2: Placenta segmentation results for ID and OOD data using the Dice, Hausdorff percentile 95, and 2D ASSD metrics. |  | ID Data | OOD Data
---|---|---|---
|  | Dice | Hausdorff | ASSD | Dice | Hausdorff | ASSD
1\. 10 Baseline | Mean | 0.806 | 20.98 | 7.64 | 0.641 | 35.53 | 17.65
| STD | 0.003 | 1.13 | 0.26 | 0.021 | 8.12 | 1.62
| Min | 0.803 | 19.08 | 7.34 | 0.628 | 25.53 | 15.12
| Max | 0.811 | 22.00 | 8.03 | 0.678 | 46.46 | 19.48
2\. 10 ST | Mean | 0.819 | 19.75 | 7.11 | 0.703 | 29.23 | 18.86
| STD | 0.010 | 2.24 | 0.35 | 0.028 | 7.08 | 1.93
| Min | 0.806 | 16.95 | 6.65 | 0.656 | 23.22 | 16.49
| Max | 0.833 | 23.21 | 7.47 | 0.727 | 40.74 | 21.56
3\. 10+5 Random | Mean | 0.821 | 19.30 | 7.02 | 0.688 | 29.29 | 13.68
| STD | 0.008 | 1.25 | 0.33 | 0.039 | 6.64 | 0.90
| Min | 0.809 | 17.81 | 6.68 | 0.620 | 23.81 | 12.50
| Max | 0.832 | 21.06 | 7.46 | 0.717 | 40.35 | 14.91
4\. 10+5 AL | Mean | 0.827 | 17.34 | 6.59 | 0.710 | 25.49 | 12.88
| STD | 0.006 | 1.10 | 0.46 | 0.030 | 1.76 | 1.35
| Min | 0.819 | 16.52 | 5.96 | 0.661 | 23.59 | 11.52
| Max | 0.835 | 19.21 | 7.11 | 0.743 | 27.98 | 15.12
5\. 10+5 AL + ST | Mean | 0.822 | 19.69 | 6.90 | 0.711 | 26.50 | 12.59
| STD | 0.006 | 1.25 | 0.12 | 0.014 | 3.35 | 0.92
| Min | 0.813 | 18.33 | 6.76 | 0.691 | 21.82 | 11.48
| Max | 0.829 | 21.68 | 7.09 | 0.728 | 31.29 | 13.82
6\. 50 Baseline | Mean | 0.825 | 18.34 | 7.16 | 0.710 | 24.32 | 13.81

##  4 Conclusion

We presented a novel TTA-based framework for combined training with AL and ST
in one iteration. The ST uses soft labels acquired from TTA results and border
slices annotations when appropriate. Our experimental results show the
effectiveness of the ST method alone for both low and high variability data
regimes of fetal body and placenta segmentation, respectively. The combined
iteration of AL and ST was effective when applied to the low data variability
of the fetal body segmentation, especially with border slices annotations
which have a low annotation cost, yielding a Dice score of 0.961 for sequence
transfer using 6 examples from the original sequence and only 2 examples from
the new sequence, close to that of 30 annotated cases from the new sequence.
In this scenario of low variability data, AL did not improve upon random
selection. However, AL was effective for the high data variability setup, but
adding ST to AL resulted in slight performance decline for ID data, indicating
that ST might induce excessive noise in the pseudo-labels. In this case, AL
may be better without ST. This suggests that for methods that combine AL with
ST or CR SSL, a supervised network iteration with AL cases can be beneficial
before the semi-supervised fine-tuning. Future work can explore this for
different data variability settings.

## References

  * [1] Arazo, E., Ortego, D., Albert, P., O’Connor, N. & McGuinness, K. Pseudo-labeling and confirmation bias in deep semi-supervised learning. Proc. Int. Joint Conference on Neural Networks (IJCNN). pp. 1-8 (2020)
  * [2] Budd, S., Robinson, E. & Kainz, B. A survey on active learning and human-in-the-loop deep learning for medical image analysis. Medical Image Analysis 71:102062 (2021)
  * [3] Chen, X., Yuan, Y., Zeng, G. & Wang, J. Semi-supervised semantic segmentation with cross pseudo supervision. Proc. IEEE/CVF Conference On Computer Vision and Pattern Recognition. pp. 2613-2622 (2021)
  * [4] Cheplygina, V., Bruijne, M. & Pluim, J. Not-so-supervised: a survey of semi-supervised, multi-instance, and transfer learning in medical image analysis. Medical Image Analysis 54:280-296 (2019)
  * [5] Dudovitch, G., Link-Sourani, D., Ben Sira, L., Miller, E., Ben Bashat, D. & Joskowicz, L. Deep learning automatic fetal structures segmentation in MRI scans with few annotated datasets. Medical Image Computing And Computer Assisted Intervention–MICCAI 2020: 23rd International Conference, Lima, Peru, October 4–8, 2020, Proceedings, Part VI 23. pp. 365-374 (2020)
  * [6] Fathi, A., Balcan, M., Ren, X. & Rehg, J. Combining self training and active learning for video segmentation. Tech. Report, Georgia Institute of Technology (2011)
  * [7] Gaillochet, M., Desrosiers, C. & Lombaert, H. TAAL: Test-time augmentation for active learning in medical image segmentation. Data Augmentation, Labelling, And Imperfections: Second MICCAI Workshop, DALI 2022, Held In Conjunction With MICCAI 2022, Singapore, September 22, 2022, Proceedings. pp. 43-53 (2022)
  * [8] Guan, L. & Yuan, X. Iterative Loop Learning Combining Self-Training and Active Learning for Domain Adaptive Semantic Segmentation. ArXiv Preprint ArXiv:2301.13361 (2023)
  * [9] Jungo, A. & Reyes, M. Assessing reliability and challenges of uncertainty estimations for medical image segmentation. Medical Image Computing And Computer Assisted Intervention–MICCAI 2019: 22nd International Conference, Shenzhen, China, October 13–17, 2019, Proceedings, Part II 22. pp. 48-56 (2019)
  * [10] Lai, Z., Wang, C., Oliveira, L., Dugger, B., Cheung, S. & Chuah, C. Joint semi-supervised and active learning for segmentation of gigapixel pathology images with cost-effective labeling. Proc. IEEE/CVF Int. Conference On Computer Vision. pp. 591-600 (2021)
  * [11] Loshchilov, I. & Hutter, F. Sgdr: Stochastic gradient descent with warm restarts. ArXiv Preprint ArXiv:1608.03983 (2016)
  * [12] Nath, V., Yang, D., Roth, H. & Xu, D. Warm start active learning with proxy labels and selection via semi-supervised fine-tuning. Medical Image Computing And Computer Assisted Intervention–MICCAI 2022: 25th International Conference, Singapore, September 18–22, 2022, Proceedings, Part VIII. pp. 297-308 (2022)
  * [13] Nie, D., Gao, Y., Wang, L. & Shen, D. ASDNet: attention based semi-supervised deep networks for medical image segmentation. Medical Image Computing And Computer Assisted Intervention–MICCAI 2018: 21st International Conference, Granada, Spain, September 16-20, 2018, Proceedings, Part IV 11. pp. 370-378 (2018)
  * [14] Ouali, Y., Hudelot, C. & Tami, M. Semi-supervised semantic segmentation with cross-consistency training. Proceedings Of The IEEE/CVF Conference On Computer Vision And Pattern Recognition. pp. 12674-12684 (2020)
  * [15] Shen, W., Peng, Z., Wang, X., Wang, H., Cen, J., Jiang, D., Xie, L., Yang, X. & Tian, Q. A Survey on Label-Efficient Deep Image Segmentation: Bridging the Gap Between Weak Supervision and Dense Prediction. IEEE Transactions On Pattern Analysis And Machine Intelligence (2023)
  * [16] Specktor-Fadida, B., Link-Sourani, D., Ferster-Kveller, S., Ben-Sira, L., Miller, E., Ben-Bashat, D. & Joskowicz, L. A bootstrap self-training method for sequence transfer: state-of-the-art placenta segmentation in fetal MRI. Uncertainty For Safe Utilization Of Machine Learning In Medical Imaging, And Perinatal Imaging, Placental And Preterm Image Analysis: 3rd International Workshop, UNSURE 2021, And 6th International Workshop, PIPPI 2021, Held In Conjunction With MICCAI 2021, Strasbourg, France, October 1, 2021, Proceedings 3. pp. 189-199 (2021)
  * [17] Specktor-Fadida, B., Link-Sourani, D., Ben-Sira, L., Miller, E., Ben-Bashat, D. & Joskowicz, L. Partial annotations for the segmentation of large structures with low annotation cost. Medical Image Learning With Limited And Noisy Data: First International Workshop, MILLanD 2022, Held In Conjunction With MICCAI 2022, Singapore, September 22, 2022, Proceedings. pp. 13-22 (2022)
  * [18] Tajbakhsh, N., Jeyaseelan, L., Li, Q., Chiang, J., Wu, Z. & Ding, X. Embracing imperfect datasets: A review of deep learning solutions for medical image segmentation. Medical Image Analysis 63:101693 (2020)
  * [19] Wang, G., Li, W., Aertsen, M., Deprest, J., Ourselin, S. & Vercauteren, T. Aleatoric uncertainty estimation with test-time augmentation for medical image segmentation with convolutional neural networks. Neurocomputing 338:34-45 (2019)
  * [20] Xia, Y., Yang, D., Yu, Z., Liu, F., Cai, J., Yu, L., Zhu, Z., Xu, D., Yuille, A. & Roth, H. Uncertainty-aware multi-view co-training for semi-supervised medical image segmentation and domain adaptation. Medical Image Analysis 65:101766 (2020)
  * [21] Yang, L., Zhuo, W., Qi, L., Shi, Y. & Gao, Y. St++: Make self-training work better for semi-supervised semantic segmentation. Proceedings Of The IEEE/CVF Conference On Computer Vision And Pattern Recognition. pp. 4268-4277 (2022)
  * [22] Yang, L., Zhang, Y., Chen, J., Zhang, S. & Chen, D. Suggestive annotation: A deep active learning framework for biomedical image segmentation. Medical Image Computing And Computer Assisted Intervention- MICCAI 2017: 20th International Conference, Quebec City, QC, Canada, September 11-13, 2017, Proceedings, Part III 20. pp. 399-407 (2017)
  * [23] Zhang, W., Zhu, L., Hallinan, J., Zhang, S., Makmur, A., Cai, Q. & Ooi, B. Boostmis: Boosting medical image semi-supervised learning with adaptive pseudo labeling and informative active annotation. Proc. IEEE/CVF Conference On Computer Vision and Pattern Recognition. pp. 20666-20676 (2022)
  * [24] Zhu, Y., Zhang, Z., Wu, C., Zhang, Z., He, T., Zhang, H., Manmatha, R., Li, M. & Smola, A. Improving semantic segmentation via efficient self-training. IEEE Transactions On Pattern Analysis And Machine Intelligence (2021)
  * [25] Zoph, B., Ghiasi, G., Lin, T., Cui, Y., Liu, H., Cubuk, E. & Le, Q. Rethinking pre-training and self-training. Advances In Neural Information Processing Systems 33:3833-3845 (2020)


$(Au)^{\intercal}((AX)(AX)^{\intercal}+(AY)(AY)^{\intercal})^{\dagger}(Av)=0.$

∎

###### Remark 7

We point out that Lemma 10 can be treated as a special instance of Lemma 18.

###### Theorem 7

For the federated linear contextual bandits considered in this work, partition
clients into equivalence classes where two clients $i$ and $j$ are in the same
class if there exists an arm $a\in[K]$ such that $x_{i,a}\sim x_{j,a}$. Let
$S$ be the class that includes client $i$, and $X\in\mathbb{R}^{d\times m}$ be
a matrix with
$\operatorname{span}(X)\subseteq\operatorname{span}(\\{x_{j,a}\\}_{j\in S})$.
Let $Y\in\mathbb{R}^{d\times n}$ be another matrix with
$\operatorname{span}(X)\cap\operatorname{span}(Y)=\\{0\\}$. Let
$u_{X},v_{X}\in\operatorname{span}(X)$ and $v_{Y}\in\operatorname{span}(Y)$.
Then, for a given policy $\pi$, if the local estimates for any arm $a\in[K]$
are in the following forms

$\displaystyle\hat{r}_{i,a}$
$\displaystyle=u_{X}^{T}(XX^{\intercal}+YY^{\intercal})^{\dagger}(v_{X}+v_{Y})$
(174) $\displaystyle\hat{\sigma}_{i,a}$
$\displaystyle=u_{X}^{T}(XX^{\intercal}+YY^{\intercal})^{\dagger}u_{X}$ (175)

and the decisions are made based solely on those quantities besides other
system parameters, then $\pi$ is a collinearly-dependent policy.

###### Proof.

Based on Lemma 18, we can show that

$\displaystyle\hat{r}_{i,a}$
$\displaystyle=u_{X}^{T}(XX^{\intercal}+YY^{\intercal})^{\dagger}(v_{X}+v_{Y})$
(176)
$\displaystyle=u_{X}^{T}(XX^{\intercal}+YY^{\intercal})^{\dagger}v_{X}+u_{X}^{T}(XX^{\intercal}+YY^{\intercal})^{\dagger}v_{Y}$
(177) $\displaystyle=u_{X}^{T}(XX^{\intercal})^{\dagger}v_{X},$ (178)
$\displaystyle{\sigma}_{i,a}$
$\displaystyle=u_{X}^{T}(XX^{\intercal}+YY^{\intercal})^{\dagger}u_{X}=u_{X}^{T}(XX^{\intercal})^{\dagger}u_{X}.$
(179)

Since $\hat{r}_{i,a}$ and $\hat{\sigma}_{i,a}$ only depend on the feature
vectors associated with clients in the same class $S$, and the decisions under
$\pi$ are based on those estimates only, $\pi$ is a collinearly-dependent
policy. ∎

###### Corollary 2

Fed-PE and Enhanced Fed-PE are both collinearly-dependent policies.

Corollary 2 can be easily verified by checking the expressions of
$\hat{r}_{i,a}^{p}$ and $\sigma^{p}_{i,a}$ under Fed-PE and Enhanced Fed-PE,
respectively.

###### Corollary 3

LinUCB type of policies are collinearly-dependent policies if we include $d$
dummy clients with $d$ unit feature vectors in $\mathbb{R}^{d}$.

###### Proof.

For single-agent sequential linear contextual bandits with disjoint
parameters, the LinUCB algorithm (Li et al.,, 2010) works as follows: at time
$t$, for any incoming context $c_{t}=i$, the learner obtains estimated reward
and uncertainty for each arm $a\in[K]$ as follows:

$\displaystyle\hat{r}_{i,a}(t)$
$\displaystyle=x^{\intercal}_{i,a}V^{-1}_{a}(t)\left(\sum_{s=1}^{t-1}\mathbbm{1}\\{a_{s}=a\\}x_{c_{s},a}y_{s}\right)$
(180) $\displaystyle\hat{\sigma}_{i,a}(t)$
$\displaystyle=\|x_{i,a}\|_{V^{-1}_{a}(t)},$ (181)

where

$\displaystyle
V_{a}(t)=\sum_{s=1}^{t-1}x_{c_{s},a}x_{c_{s},a}^{\intercal}\mathbbm{1}\\{a_{s}=a\\}+\lambda
I_{d}.$ (182)

It then picks the arm with the highest upper confidence bound
$\hat{r}_{i,a}(t)+\alpha\hat{\sigma}_{i,a}(t)$, where $\alpha$ is a real
number.

If we view each context to be associated with a fixed client as in our
federated linear contextual bandits setting, and treat the identity matrix
$I_{d}$ as $\sum_{i=1}^{d}e_{i}e_{i}^{\intercal}$ where $e_{i}$’s are unit
feature vectors associated with $d$ dummy clients, then, the estimate at
client $i$ for arm $a$ only depends on clients with $x_{j,a}\sim x_{i,a}$.
Thus, the decision at client $i$ only depends on other clients in the same
equivalent class, and such LinUCB type of policies are collinearly-dependent.
∎

###### Corollary 4

Thompson sampling based policies with Gaussian priors are collinearly-
dependent policies.

###### Proof.

To make the setting consistent, we first modify the Thompson sampling
algorithm proposed for the shared parameter linear contextual bandits (Agrawal
and Goyal, 2013b, ) to a disjoint parameter setting.

Similar to LinUCB, the learner would calculate the mean and variance of the
Gaussian distribution for the parameter $\theta_{a}$ associated with each arm
$a\in[K]$ according to

$\displaystyle\hat{\theta}_{a}(t)$
$\displaystyle=V^{-1}_{a}(t)\left(\sum_{s=1}^{t-1}\mathbbm{1}\\{a_{s}=a\\}x_{c_{s},a_{s}}y_{s}\right),$
(183) $\displaystyle\hat{\sigma}_{i,a}(t)$
$\displaystyle=\alpha^{2}V_{a}^{-1}(t),$ (184)

where $\alpha\in\mathbb{R}$ is a constant and $V_{a}^{-1}(t)$ is defined in
the same way as in (182). It then samples $\theta_{a}(t)$ from the
distribution $\mathcal{N}(\hat{\theta}_{a}(t),\hat{\sigma}_{i,a}(t))$, and
then plays the arm $a_{t}:=\arg\max_{a}x_{i,a}^{\intercal}\theta_{a}(t)$ if
the incoming context $c_{t}=i$.

We note that under the Thompson sampling procedure, the reward associated with
arm $a$ and incoming context $i$ at time $t$ is actually a Gaussian random
variable with distribution
$\mathcal{N}\left(x_{i,a}^{\intercal}V_{a}^{-1}(t)\left(\sum_{s=1}^{t-1}\mathbbm{1}\\{a_{s}=a\\}x_{c_{s},a_{s}}y_{s}\right),\alpha^{2}x_{i,a}^{\intercal}V_{a}^{-1}(t)x_{i,a}\right)$.
According to Theorem 7, since the mean and variance are in the form specified
in (174)-(175), the distribution of the reward under the incoming context $i$
only depends on other contexts that in the same equivalence class.

If we associate each context with a fixed client, then, we can see that the
decision at client $i$ only depends on other clients in the same equivalence
class. Thus, such Thompson sampling type of policies are collinearly-
dependent. ∎

###  F.2 Proof of Theorem 2

We provide the detailed proof for the minimax regret bound in Theorem 2. For
simplicity, we assume $M/d$ is an integer. We use $\mathbf{1}$ and
$\mathbf{0}$ to denote the all-one and all-zero vectors, respectively.

First, divide $[M]$ into $d$ groups, each with $M/d$ clients. Let the $s$-th
group be $G_{s}=\\{(s-1)M/d+1,\ldots,sM/d\\}$, where $s\in\\{1,2,\ldots,d\\}$.
We thus have $[M]=\cup_{s=1}^{d}G_{s}$. Consider the case where
$x_{i,a}=e_{s}$ for all $i\in G_{s}$ and $a\in[K]$, where $e_{s}$ is the
$s$-th canonical basis vector.

We first choose $\theta=\\{\Delta\mathbf{1},\mathbf{0},\ldots,\mathbf{0}\\}$,
i.e. $\theta_{1}=(\Delta,\Delta,\ldots,\Delta)^{\intercal}$, and
$\theta_{a}=(0,0,\ldots,0)^{\intercal}$ for any $a\geq 2$. ($\Delta$ will be
specified later.) Then, the reward for client $i$ pulling arm $a_{t}$ at time
$t$ would be $y_{i,t}:=x_{i,a_{t}}^{\intercal}\theta_{a_{t}}+\eta_{i,t}$,
where $\eta_{i,t}$ is independently drawn from a standard Gaussian
distribution.

Consider a collinearly-dependent policy $\pi$. Denote $\mathbb{P}_{\theta}$ as
the probability measure induced by $\theta=\\{\theta_{a}\\}_{a\in[K]}$ under
policy $\pi$, and $\mathbb{E}_{\theta}$ as the corresponding expectation. Let
$T_{i,a}$ be the number of times that client $i$ pulls arm $a$ within time
horizon $T$. Note that $\sum_{a\in[K]}T_{i,a}=T$.

Define $\bar{T}_{s,a}:=\sum_{i\in G_{s}}T_{i,a}$, i.e., the total number of
times that arm $a$ has been pulled by the clients in group $s$ over time
horizon $T$. Then, we have

$\sum_{a\in[K]}\mathbb{E}_{\theta}[\bar{T}_{s,a}]=\frac{MT}{d}.$

Thus, there must exist an arm $a_{s}^{*}>1$ for each group $s$ such that
$\mathbb{E}_{\theta}[\bar{T}_{s,a_{s}^{*}}]\leq\frac{MT}{d(K-1)}$.

Define a new instance $\tilde{\theta}=\\{\tilde{\theta}_{a}\\}_{a\in[K]}$,
where

$\tilde{\theta}_{a}=\theta_{a}+\sum_{s=1}^{d}2\Delta
e_{a_{s}^{*}}\mathbbm{1}{\\{a_{s}^{*}=a\\}},\quad\forall a\in[K].$

Therefore, while arm $1$ being optimal for all clients under instance
$\theta$, the optimal arm of clients in group $G_{s}$ is arm $a_{s}^{*}$ under
instance $\tilde{\theta}$.

Before we proceed, we introduce the following notations. Let
$\mathcal{H}_{t}:=\\{a_{i,\tau},y_{i,\tau}\\}_{i\in[M],\tau\in[t]}$,
$\mathcal{H}_{s,t}:=\\{a_{i,\tau},y_{i,\tau}\\}_{i\in G_{s},\tau\in[t]}$, and
$\mathcal{G}_{t}:=\\{a_{i,t},y_{i,t}\\}_{i\in[M]}$,
$\mathcal{G}_{s,t}:=\\{a_{i,t},y_{i,t}\\}_{i\in G_{s}}$.

Then, we prove a useful lemma.

###### Lemma 19

Denote $D(P\|Q):=\int\log\frac{dP}{dQ}dP$ as the KL divergence between two
distributions $P$ and $Q$, and $\mathcal{N}(\mu,\sigma^{2})$ as a Gaussian
distribution with mean $\mu$ and variance $\sigma^{2}$. Then,

$D(\mathbb{P}_{\theta}(\mathcal{H}_{s,T})\|\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{s,T}))=\mathbb{E}_{\theta}[\bar{T}_{s,a_{s}^{*}}]\cdot
D(\mathcal{N}(0,1)\|\mathcal{N}(2\Delta,1)).$

###### Proof.

Based on the definition of KL divergence, we have

$\displaystyle
D(\mathbb{P}_{\theta}(\mathcal{H}_{s,T})\|\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{s,T}))$
$\displaystyle=\mathbb{E}_{\theta}\left[\log\frac{\mathbb{P}_{\theta}(\mathcal{H}_{s,T})}{\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{s,T})}\right]$
(185) $\displaystyle=\mathbb{E}_{\theta}\left[\log\frac{\int_{i\notin
G_{s}}\mathbb{P}_{\theta}(\mathcal{H}_{T})}{\int_{i\notin
G_{s}}\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{T})}\right]$ (186)
$\displaystyle=\mathbb{E}_{\theta}\left[\log\frac{\int_{i\notin
G_{s}}\mathbb{P}_{\theta}(\mathcal{H}_{T-1})\mathbb{P}_{\theta}(\mathcal{G}_{T}|\mathcal{H}_{T-1})}{\int_{i\notin
G_{s}}\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{T-1})\mathbb{P}_{\tilde{\theta}}(\mathcal{G}_{T}|\mathcal{H}_{T-1})}\right]$
(187) $\displaystyle=\mathbb{E}_{\theta}\left[\log\frac{\int_{i\notin
G_{s}}\mathbb{P}_{\theta}(\mathcal{H}_{T-1})\prod_{r}\mathbb{P}_{\theta}(\mathcal{G}_{r,T}|\mathcal{H}_{r,T-1})}{\int_{i\notin
G_{s}}\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{T-1})\prod_{r}\mathbb{P}_{\tilde{\theta}}(\mathcal{G}_{s,T}|\mathcal{H}_{r,T-1})}\right]$
(188) $\displaystyle=\mathbb{E}_{\theta}\left[\log\frac{\int_{i\notin
G_{s}}\mathbb{P}_{\theta}(\mathcal{H}_{T-1})\prod_{r\neq
s}\mathbb{P}_{\theta}(\mathcal{G}_{r,T}|\mathcal{H}_{r,T-1})}{\int_{i\notin
G_{s}}\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{T-1})\prod_{r\neq
s}\mathbb{P}_{\tilde{\theta}}(\mathcal{G}_{r,T}|\mathcal{H}_{r,T-1})}+\log\frac{\mathbb{P}_{\tilde{\theta}}(\mathcal{G}_{s,T}|\mathcal{H}_{s,T-1})}{\mathbb{P}_{\tilde{\theta}}(\mathcal{G}_{s,T}|\mathcal{H}_{s,T-1})}\right]$
(189) $\displaystyle=\mathbb{E}_{\theta}\left[\log\frac{\int_{i\notin
G_{s}}\mathbb{P}_{\theta}(\mathcal{H}_{T-1})}{\int_{i\notin
G_{s}}\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{T-1})}\right]+\mathbb{E}_{\theta}\left[\sum_{i\in
G_{s}}\mathbbm{1}{\\{a_{i,T}=a_{s}^{*}\\}}D(\mathcal{N}(0,1)\|\mathcal{N}(2\Delta,1))\right],$
(190)

where in (185), we integrate over all variables that are associated with
clients outside group $s$ to obtain the marginal distributions
$\mathbb{P}_{\theta}(\mathcal{H}_{s,T})$ and
$\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{s,T})$, respectively. Based on the
assumption that $\pi$ is collinearly-independent, we can decompose the
conditional distributions
$\mathbb{P}_{\tilde{\theta}}(\mathcal{G}_{T}|\mathcal{H}_{T-1})$ and
$\mathbb{P}_{{\theta}}(\mathcal{G}_{T}|\mathcal{H}_{T-1})$ into products of
conditional distributions where only variables associated with clients in each
group are dependent. Noticing that within group $s$, $\mathbb{P}_{\theta}$ and
$\mathbb{P}_{\tilde{\theta}}$ only differs over arm $a_{s}^{*}$, based on
which (190) is obtained.

Express the first term in (190) recursively, we eventually have

$\displaystyle
D(\mathbb{P}_{\theta}(\mathcal{H}_{s,T})\|\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{s,T}))$
$\displaystyle=\sum_{t\in[T]}\mathbb{E}_{\theta}\left[\sum_{i\in
G_{s}}\mathbbm{1}{\\{a_{i,t}=a_{s}^{*}\\}}D(\mathcal{N}(0,1)\|\mathcal{N}(2\Delta,1))\right]$
(191) $\displaystyle=\mathbb{E}_{\theta}[\bar{T}_{s,a_{s}^{*}}]\cdot
D(\mathcal{N}(0,1)\|\mathcal{N}(2\Delta,1)).$ (192)

∎

Now we are ready to bound the regrets under policy $\pi$ and two instances
$\theta$ and $\tilde{\theta}$. Since the selection of any sub-optimal arm will
incur a regret of $\Delta$, we have

$\displaystyle R(T;\pi,\theta)+R(T;\pi,\tilde{\theta})$
$\displaystyle\geq\Delta\frac{MT}{2d}\sum_{s=1}^{d}\left(\mathbb{P}_{\theta}\left[\bar{T}_{s,1}\leq\frac{MT}{2d}\right]+\mathbb{P}_{\tilde{\theta}}\left[\bar{T}_{s,1}>\frac{MT}{2d}\right]\right)$
(193)
$\displaystyle\geq\Delta\frac{MT}{4d}\sum_{s=1}^{d}\exp(-D(\mathbb{P}_{\theta}(\mathcal{H}_{s,T})\|\mathbb{P}_{\tilde{\theta}}(\mathcal{H}_{s,T})))$
(194)
$\displaystyle=\Delta\frac{MT}{4d}\sum_{s=1}^{d}\exp\left(-\mathbb{E}_{\theta}[\bar{T}_{s,a_{s}^{*}}]\cdot
D(\mathcal{N}(0,1)||\mathcal{N}(2\Delta,1))\right)$ (195)
$\displaystyle\geq\Delta\frac{MT}{4d}\sum_{s=1}^{d}\exp\left(\frac{MT}{d(K-1)}\cdot
2\Delta^{2}\right)$ (196)
$\displaystyle=\frac{MT\Delta}{4}\exp\left(\frac{2MT\Delta^{2}}{d(K-1)}\right),$
(197)

where (194) follows from the high probability Pinsker inequality, (195) is due
to Lemma 19, and (196) follows from the definition of $\bar{T}_{s,a_{s}^{*}}$.

Let $\Delta:=\sqrt{\frac{d(K-1)}{4MT}}$. Then, we have

$\max\left(R(T;\pi,\theta)+R(T;\pi,\tilde{\theta})\right)\geq\frac{\sqrt{d(K-1)MT}}{8\sqrt{e}}=\Omega(\sqrt{dKMT}).$

##  Appendix G Fed-PE for Shared Parameter Case

###  G.1 Algorithm Details

We slightly modify Fed-PE for the shared parameter case where
$\theta_{a}=\theta,\forall a\in[K]$. Such minor tweaks, as opposed to a full-
blown re-design, lead to a unified algorithmic framework that can be flexibly
applied to both disjoint and shared parameter cases. Similar to the disjoint
parameter case, at the client side, each client $i$ treats
$\\{\theta_{a}\\}_{a}$ separately, i.e., it does not aggregate rewards
collected by pulling different arms to estimate the shared parameter $\theta$;
Rather, at phase $p$, it will output $|\mathcal{A}_{i}^{p}|$ different
estimates $\\{\hat{\theta}_{i,a}\\}_{a\in\mathcal{A}_{i}^{p}}$ and send them
to the central server for aggregation.

The major difference occurs in the server side subroutine. Once different
estimates $\\{\hat{\theta}_{i,a}\\}_{i,a}$ are received, the central server
would aggregate them to obtain a global estimate of the shared parameter
$\theta$. Specifically, the global aggregation step at the server side in (4)
can be changed as follows: after obtaining

$\displaystyle V_{a}^{p+1}$
$\displaystyle\leftarrow\bigg{(}\sum_{i\in\mathcal{R}_{a}^{p}}f_{i,a}^{p}\frac{\hat{\theta}_{i,a}^{p}(\hat{\theta}^{p}_{i,a})^{\intercal}}{\|\hat{\theta}_{i,a}^{p}\|^{2}}\bigg{)}^{\dagger},$
(198)

the server would calculate

$\displaystyle V^{p+1}$
$\displaystyle\leftarrow\bigg{(}\sum_{a\in\mathcal{A}^{p}}\left(V_{a}^{p+1}\right)^{\dagger}\bigg{)}^{\dagger},$
(199) $\displaystyle\hat{\theta}^{p+1}$ $\displaystyle\leftarrow
V^{p+1}\bigg{(}\sum_{i\in[M]}\sum_{a\in\mathcal{A}_{i}^{p}}f_{i,a}^{p}\hat{\theta}_{i,a}^{p}\bigg{)}.$
(200)

Correspondingly, the multi-client G-optimal design at phase $p$ can be
formulated as

$\displaystyle\text{minimize\ \
}G(\pi)=\sum_{i=1}^{M}\max_{a\in\mathcal{A}_{i}^{p}}e_{i,a}^{\intercal}\bigg{(}\sum_{j\in[M]}\sum_{a\in\mathcal{A}_{j}^{p}}\pi_{j,a}^{p}e_{j,a}e_{j,a}^{\intercal}\bigg{)}^{\dagger}e_{i,a}\quad\text{s.t.
}\pi^{p}\in\mathcal{C}^{p}.$ (201)

Compared with the multi-client G-optimal design for the disjoint parameter
case in Eqn. (9), the only difference is that (201) now has a double summation
over both arms and clients inside $(\cdot)^{\dagger}$ in the objective
function, while (9) only contains a summation over the clients. This is
consistent with the different constructions of the “potential matrices” for
those two cases.

Once the estimated shared parameter and potential matrix
$(\hat{\theta}^{p},V_{a}^{p})$ is broadcast to the clients, they will use it
to obtain estimates $\hat{r}_{i,a}^{p}$ and $u_{i,a}^{p}$, as in (2) under
Fed-PE. The process then continues.

###  G.2 Theoretical Analysis

We present the regret upper bound and analysis for the shared parameter case
in this subsection.

######  Theorem 8 (Complete version of Theorem 3)

Consider time horizon $T$ that consists of $H$ phases with $f^{p}=cn^{p}$,
where $c$ and $n>1$ are fixed integers, and $n^{p}$ denotes the $p$th power of
$n$. Let

$\alpha=\min(\sqrt{2\log(H/\delta)+d\log(ke)},\sqrt{2\log(2MKH/\delta)}),$
(202)

where $k>1$ is a number satisfying $kd\geq 2\log(H/\delta)+d\log(ke)$. Then,
with probability at least $1-\delta$, the regret of the adapted Fed-PE for the
shared parameter case is upper bounded as

$R(T)\leq
4\alpha\frac{L}{\ell}\sqrt{dM}\left(\frac{\sqrt{n^{2}-n}}{\sqrt{n}-1}\sqrt{T}+\frac{K}{\sqrt{cn}-\sqrt{c}}\right).$

In particular, if $K=O(\sqrt{T})$, the regret upper bound scales in

$O\left(\sqrt{dMT(\log({(\log T)}/{\delta})+\min\\{d,\log MK\\})}\right),$

and the communication cost scales in $O((KdM+d^{2}M)\log T)$.

Following similar analysis as in the proof of Lemma 7 by replacing $v_{j,a}$
with $e_{j,a}$, we can show that the multi-client G-optimal design in (201) is
equivalent to the following determinant optimization problem:

$\displaystyle\text{maximize\ \
}F(\pi)=\log\operatorname{Det}\bigg{(}\sum_{j\in[M]}\sum_{a\in\mathcal{A}_{j}^{p}}\pi_{j,a}^{p}e_{j,a}e_{j,a}^{\intercal}\bigg{)}\quad\text{s.t.
}\pi^{p}\in\mathcal{C}^{p}.$ (203)

and the optimal solution $(\pi^{p})^{*}$ satisfies
$G((\pi^{p})^{*})=\operatorname{rank}(\\{e_{i,a}\\}_{i\in[M],a\in\mathcal{A}_{i}})\leq
d$.

Note that compared with the optimal solution $\pi^{*}$ in Lemma 7 where
$G(\pi^{p})=\operatorname{rank}(\\{v_{i,a}\\}_{i\in[M],a\in\mathcal{A}_{i}})\leq
Kd$, the upper bound on $G(\pi)$ has been reduced by a factor of $K$, due to
the dimension difference between $e_{i,a}$ and $v_{i,a}$. Besides, we also
note that the block diagonal structure inside $\operatorname{Det}(\cdot)$ in
(33) does not exist in (203) any more, which implies that the BCA algorithm in
Algorithm 3 cannot be applied for this case. Designing alternative efficient
optimization algorithms to solve (203) is one of our future steps.

With a little abuse of notation, in this section, we define

$\displaystyle\alpha_{2}$ $\displaystyle:=\sqrt{2\log(H/\delta)+d\log(ke)}$
(204) $\displaystyle\sigma_{i,a}^{p}$
$\displaystyle:=\|x_{i,a}\|_{V^{p}}/\ell$ (205) $\displaystyle X_{p}$
$\displaystyle:=\bigg{\|}\sum_{i\in[M]}\sum_{a\in\mathcal{A}_{i}}\frac{e_{i,a}}{\|x_{i,a}\|}\ell\xi_{i,a}^{p-1}\bigg{\|}_{V^{p}}^{2}$
(206) $\displaystyle a_{(i,a),(j,b)}$
$\displaystyle:=\sqrt{f_{i,a}^{p-1}}e_{i,a}^{\intercal}\bigg{(}\sum_{k\in[M]}\sum_{a\in\mathcal{A}_{k}^{p-1}}f_{k,a}^{p-1}e_{k,a}e_{k,a}^{\intercal}\bigg{)}^{\dagger}e_{j,b}\sqrt{f_{j,b}^{p-1}}$
(207) $\displaystyle\xi$
$\displaystyle:=\left(\frac{\ell\xi_{i,a}^{p-1}}{\|x_{i,a}\|\sqrt{f_{i,a}^{p-1}}}\right)_{i\in[M],a\in\mathcal{A}_{i}^{p-1}}\in\mathbb{R}^{\sum_{i\in[M]}|\mathcal{A}_{i}^{p-1}|}$
(208) $\displaystyle A$
$\displaystyle:=(a_{(i,a),(j,b)})\in\mathbb{R}^{\left(\sum_{i\in[M]}|\mathcal{A}_{i}^{p-1}|\right)\times\left(\sum_{i\in[M]}|\mathcal{A}_{i}^{p-1}|\right)}.$
(209)

It can be verified that $X_{p}=\|A\xi\|^{2}$, $A^{2}=A$, and
$\text{trace}(A)\leq d$.

Then, following the same definition of “bad” event $\mathcal{E}(\alpha)$ by
using the new set of variables, we can show that Lemma 11 still holds by
slightly modifying the analysis in Appendix D. For the probability of the bad
event, we can show that $\mathbb{P}[\mathcal{E}(\alpha_{1})]\leq\delta$
similarly as in the proof of Lemma 12, while
$\mathbb{P}[\mathcal{E}(\alpha_{2})]\leq\delta$ can be derived using the new
definitions of $X_{p}$, $A$, $\xi$. In particular, we can show the following
lemma.

###### Lemma 20

Under the adapted Fed-PE algorithm for the shared parameter case, for any
$p\in[H]$, we have
$\mathbb{P}[X_{p}\geq\sqrt{2\log(H/\delta)+d\log(ke)}|\mathcal{F}_{p-1}]\leq\delta/H$.

$\mathbb{P}[\mathcal{E}(\alpha_{2})]\leq\delta$ then follows by applying a
union bound over all phases $p\in[H]$.

Then, in order to bound the regret when the good event happens, we follow the
same steps as in the proof of Lemma 14, except that we utilize the following
lemma to remove the factor of $\sqrt{K}$ in the upper bound.

###### Lemma 21

Under the adapted Fed-PE algorithm for the shared parameter case, for any
$p\in[H]$, we have
$\sum_{i\in[M]}\max_{a\in\mathcal{A}_{i}^{p}}\frac{x^{\intercal}_{i,a}}{\|x_{i,a}\|_{2}}V^{p}\frac{x_{i,a}}{\|x_{i,a}\|_{2}}\leq\frac{d}{f^{p-1}}$.

Lemma 21 is a direct consequence of the multi-agent G-optimal design for the
shared parameter case, as elaborated earlier. Thus, when we put all pieces
together, the regret is reduced by a factor of $\sqrt{K}$ compared with
Theorem 1, while the other factors remain the same.

##  Appendix H Experiment Details and Additional Results

Experiment Environment. The experiments in both Section 6 and this section are
carried out using a MacBook Pro with a 2.3GHz Quad-Core Intel Core i5 CPU and
8GB 2133 MHz LPDDR3 memory. The programming language is Python3 with packages
Numpy, Scipy, and Pandas. All experiments are computationally light – the
running time ranges from less than a minute to slightly more than 1 hour.

Regret versus System Parameters. In addition to the results reported in the
main paper, we also plot the regret with varying $M,K$ and $d$ under Enhanced
Fed-PE in Fig. 2. The experimental setup remains the same as the synthetic one
in Section 6, except that $T$ is set as $2^{16}$. We see that the per-client
regret is proportional to the number of arms and the context dimensions, and
inversely proportional to the number of clients, which is reasonable.

Figure 2: Per-client pseudo-regret over $T$, with varying $M,K$, and $d$.
Shaded area indicates the standard deviation.

Sparsity Level. A sparse solution $\pi$ of the optimization problem (9) has
many zero entries, which is desirable because it means each client only needs
to explore a few arms in one phase even if the active arm set is very large.
Define the Sparsity Level of $\pi$ as:

$\text{{Sparsity Level}}=\frac{\\#\text{the number of non-zero entries of
}\pi}{M}.$

The smaller the Sparsity Level is, the sparser the solution is. Since there
are $M$ linear equality constraints, the number of non-zero entries in $\pi$
should be at least $M$. Thus, the minimum value of Sparsity Level is 1.
Moreover, if the elimination procedure works well, we expect to eventually
observe only $M$ non-zero entries in $\pi$, and constant regret under a
specific realization of the bandits problem. Therefore, Sparsity Level also
characterizes how many arms that one client pulls on average within a phase.
Besides, a smaller Sparsity Level indicates less communication cost per
client.

Figure 3: Sparsity level over phase index $p$, with varying $M,K$ and $d$.
Shaded area indicates the standard deviation.

In Figure 3, we plot the Sparsity Level as a function of the phase index $p$.
The result suggests that our algorithm assigns each client only approximately
2 arms (on average) to explore. We also see that the Sparsity Level and the
communication per client are proportional to $K$ and $d$, and inversely
proportional to $M$.

Number of Iterations. To measure the efficiency of the BCA algorithm, we
define the Number of Iterations as the minimum number $k$ such that
$G(\pi^{(k)})\leq d_{a}^{p}+\epsilon$, where the notations remain the same as
in the Appendix C.2. In the experiment, we choose $\epsilon=0.1$.

In Figure 4, we observe that the Number of Iterations is inversely
proportional to $M$, and proportional to $K$ and $d$, which suggests that
increasing the number of clients will not affect the efficiency significantly,
although we should bear in mind that one iteration includes $M$ block updates.

Figure 4: Number of iterations over phase index $p$, with varying $M,K$, and
$d$. Shaded area indicates the standard deviation.

Different Phase Length Selection. In Figure 5, we plot the regret performances
of the three selections of $f^{p}$ introduced in Appendix E.2. Specifically,
we construct the “greedy” phase length the same as in Appendix E.2. The
“exponential” selection is $f^{p}=2^{p}$. For the “uniform” selection, we set
$f^{p}=100$ rather than $10$ for time-saving. Note that the greedy selection
leads to $\log_{2}\log_{2}T-1=3$ phases, while the exponential selection
consists of 15 phases, and uniform has 655 phases. As we observe, the uniform
selection results in the lowest regret, while the exponential selection has
slightly worse regret performance. The regret under the greedy selection is
much worse than those under the other selections. The results suggest that
exponential selection has the best tradeoff between regret and communication
costs, corroborating the theoretical results in Table 2.

Figure 5: Regret with different selection of $f^{p}$. Shaded area indicates
the standard deviation.

## References

  * Abbasi-Yadkori et al., (2011) Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011).  Improved algorithms for linear stochastic bandits.  In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages 2312–2320.
  * Agarwal et al., (2020) Agarwal, A., Langford, J., and Wei, C.-Y. (2020).  Federated residual learning.  arXiv 2003.12880.
  * Agrawal and Goyal, (2012) Agrawal, S. and Goyal, N. (2012).  Analysis of Thompson sampling for the multi-armed bandit problem.  In Conference on Learning Theory, pages 39–1.
  * (4) Agrawal, S. and Goyal, N. (2013a).  Further optimal regret bounds for Thompson sampling.  In Artificial Intelligence and Statistics, pages 99–107.
  * (5) Agrawal, S. and Goyal, N. (2013b).  Thompson sampling for contextual bandits with linear payoffs.  In Proceedings of the 30th International Conference on International Conference on Machine Learning, pages 1220–1228.
  * Anandkumar et al., (2011) Anandkumar, A., Michael, N., Tang, A. K., and Swami, A. (2011).  Distributed algorithms for learning and cognitive medium access with logarithmic regret.  IEEE J. Select. Areas Commun., 29(4):731–745.
  * Auer, (2003) Auer, P. (2003).  Using confidence bounds for exploitation-exploration trade-offs.  J. Mach. Learn. Res., 3:397–422.
  * Auer et al., (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2-3):235–256.
  * Auer and Ortner, (2010) Auer, P. and Ortner, R. (2010).  UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem.  Periodica Mathematica Hungarica, 61(1):55–65.
  * Avner and Mannor, (2014) Avner, O. and Mannor, S. (2014).  Concurrent bandits and cognitive radio networks.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 66–81. Springer.
  * Bastani and Bayati, (2015) Bastani, H. and Bayati, M. (2015).  Online decision-making with high-dimensional covariates.  SSRN Electronic Journal.
  * Besson and Kaufmann, (2018) Besson, L. and Kaufmann, E. (2018).  Multi-player bandits revisited.  In Proceedings of Algorithmic Learning Theory, pages 56–92.
  * Bogunovic et al., (2021) Bogunovic, I., Losalka, A., Krause, A., and Scarlett, J. (2021).  Stochastic linear bandits robust to adversarial attacks.  In International Conference on Artificial Intelligence and Statistics, pages 991–999. PMLR.
  * Boursier and Perchet, (2019) Boursier, E. and Perchet, V. (2019).  SIC-MMAB: Synchronisation involves communication in multiplayer multi-armed bandits.  In Advances in Neural Information Processing Systems, pages 2249–2257.
  * Boyd and Vandenberghe, (2004) Boyd, S. and Vandenberghe, L. (2004).  Convex Optimization.  Cambridge University Press.
  * Bubeck and Cesa-Bianchi, (2012) Bubeck, S. and Cesa-Bianchi, N. (2012).  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends® in Machine Learning, 5(1):1–122.
  * Calafiore and El Ghaoui, (2014) Calafiore, G. and El Ghaoui, L. (2014).  Optimization Models.  Control systems and optimization series. Cambridge University Press.
  * Cesa-Bianchi et al., (2013) Cesa-Bianchi, N., Gentile, C., and Zappella, G. (2013).  A gang of bandits.  In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1, pages 737––745, Red Hook, NY, USA. Curran Associates Inc.
  * Chan et al., (2021) Chan, J., Pacchiano, A., Tripuraneni, N., Song, Y. S., Bartlett, P., and Jordan, M. I. (2021).  Parallelizing contextual linear bandits.
  * Chu et al., (2011) Chu, W., Li, L., Reyzin, L., and Schapire, R. (2011).  Contextual bandits with linear payoff functions.  In Gordon, G., Dunson, D., and Dudík, M., editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208–214, Fort Lauderdale, FL, USA. PMLR.
  * Dani et al., (2008) Dani, V., Hayes, T. P., and Kakade, S. M. (2008).  Stochastic linear optimization under bandit feedback.  In 21st Annual Conference on Learning Theory - COLT, pages 355–366.
  * Dimakopoulou et al., (2017) Dimakopoulou, M., Zhou, Z., Athey, S., and Imbens, G. (2017).  Estimation considerations in contextual bandits.  arXiv preprint arXiv:1711.07077.
  * Dubey and Pentland, (2020) Dubey, A. and Pentland, A. (2020).  Differentially-private federated linear bandits.  Advances in Neural Information Processing Systems, 33.
  * Gao et al., (2019) Gao, Z., Han, Y., Ren, Z., and Zhou, Z. (2019).  Batched multi-armed bandits problem.
  * Gentile et al., (2017) Gentile, C., Li, S., Kar, P., Karatzoglou, A., Zappella, G., and Etrue, E. (2017).  On context-dependent clustering of bandits.  In International Conference on Machine Learning, pages 1253–1262. PMLR.
  * Gentile et al., (2014) Gentile, C., Li, S., and Zappella, G. (2014).  Online clustering of bandits.  In Xing, E. P. and Jebara, T., editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 757–765, Bejing, China. PMLR.
  * Goldenshluger and Zeevi, (2013) Goldenshluger, A. and Zeevi, A. (2013).  A linear response bandit problem.  Stoch. Syst., 3(1):230–261.
  * Han et al., (2020) Han, Y., Zhou, Z., Zhou, Z., Blanchet, J., Glynn, P. W., and Ye, Y. (2020).  Sequential batch learning in finite-action linear contextual bandits.
  * Harman et al., (2014) Harman, R., Bachratá, A., and Filová, L. (2014).  Heuristic construction of exact experimental designs under multiple resource constraints.  arXiv preprint arXiv:1402.7263.
  * Harman and Benková, (2014) Harman, R. and Benková, E. (2014).  Approximate D-optimal experimental design with simultaneous size and cost constraints.  arXiv preprint arXiv:1408.2698.
  * Harper and Konstan, (2015) Harper, F. M. and Konstan, J. A. (2015).  The MovieLens Datasets: History and context.  ACM Trans. Interact. Intell. Syst., 5(4).
  * Holbrook, (2018) Holbrook, A. (2018).  Differentiating the pseudo determinant.  Linear Algebra and its Applications, 548:293–304.
  * Hsu et al., (2012) Hsu, D., Kakade, S., and Zhang, T. (2012).  A tail inequality for quadratic forms of subgaussian random vectors.  Electronic Communications in Probability, 17:1 – 6.
  * Kairouz et al., (2021) Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D’Oliveira, R. G. L., Eichner, H., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konečný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Raykova, M., Qi, H., Ramage, D., Raskar, R., Song, D., Song, W., Stich, S. U., Sun, Z., Suresh, A. T., Tramèr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F. X., Yu, H., and Zhao, S. (2021).  Advances and open problems in federated learning.  Foundations and Trends® in Machine Learning, 14(1).
  * Kannan et al., (2018) Kannan, S., Morgenstern, J. H., Roth, A., Waggoner, B., and Wu, Z. S. (2018).  A smoothed analysis of the greedy algorithm for the linear contextual bandit problem.  In Advances in Neural Information Processing Systems, pages 2231–2241.
  * Kiefer and Wolfowitz, (1960) Kiefer, J. and Wolfowitz, J. (1960).  The equivalence of two extremum problems.  Canadian Journal of Mathematics, 12:363–366.
  * Korda et al., (2016) Korda, N., Szorenyi, B., and Li, S. (2016).  Distributed clustering of linear bandits in peer to peer networks.  In Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1301–1309, New York, New York, USA. PMLR.
  * Lai and Robbins, (1985) Lai, T. L. and Robbins, H. (1985).  Asymptotically efficient adaptive allocation rules.  Advances in applied mathematics, 6(1):4–22.
  * Landgren et al., (2016) Landgren, P., Srivastava, V., and Leonard, N. E. (2016).  On distributed cooperative decision-making in multiarmed bandits.  In 2016 European Control Conference (ECC), pages 243–248. IEEE.
  * Landgren et al., (2018) Landgren, P., Srivastava, V., and Leonard, N. E. (2018).  Social imitation in cooperative multiarmed bandits: partition-based algorithms with strictly local information.  In 2018 IEEE Conference on Decision and Control (CDC), pages 5239–5244. IEEE.
  * Langford and Zhang, (2008) Langford, J. and Zhang, T. (2008).  The epoch-greedy algorithm for multi-armed bandits with side information.  In Advances in Neural Information Processing Systems, pages 817–824.
  * Lattimore and Szepesvári, (2020) Lattimore, T. and Szepesvári, C. (2020).  Bandit Algorithms.  Cambridge University Press.
  * Laurent and Massart, (2000) Laurent, B. and Massart, P. (2000).  Adaptive estimation of a quadratic functional by model selection.  The Annals of Statistics, 28(5):1302–1338.
  * Li et al., (2010) Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010).  A contextual-bandit approach to personalized news article recommendation.  In Proceedings of the 19th International Conference on World Wide Web, pages 661–670.
  * Li et al., (2020) Li, T., Song, L., and Fragouli, C. (2020).  Federated recommendation system via differential privacy.  In IEEE International Symposium on Information Theory (ISIT), pages 2592–2597.
  * Liu and Zhao, (2010) Liu, K. and Zhao, Q. (2010).  Distributed learning in multi-armed bandit with multiple players.  IEEE Transactions on Signal Processing, 58(11):5667–5681.
  * Magnus and Neudecker, (1999) Magnus, J. R. and Neudecker, H. (1999).  Matrix Differential Calculus with Applications in Statistics and Econometrics (Revised ed.).  Wiley. ISBN 0-471-98633-X.
  * Martínez-Rubio et al., (2019) Martínez-Rubio, D., Kanade, V., and Rebeschini, P. (2019).  Decentralized cooperative stochastic bandits.  In Advances in Neural Information Processing Systems, pages 4529–4540.
  * McMahan et al., (2017) McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. (2017).  Communication-efficient learning of deep networks from decentralized data.  In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1273–1282, Fort Lauderdale, FL, USA.
  * Morabia, (2019) Morabia, K. (2019).  Collaborative-filtering.  https://github.com/kevalmorabia97/Collaborative-Filtering.
  * Perchet et al., (2016) Perchet, V., Rigollet, P., Chassang, S., and Snowberg, E. (2016).  Batched bandit problems.  The Annals of Statistics, 44(2):660 – 681.
  * Raghavan et al., (2018) Raghavan, M., Slivkins, A., Wortman, J. V., and Wu, Z. S. (2018).  The externalities of exploration and how data diversity helps exploitation.  In Bubeck, S., Perchet, V., and Rigollet, P., editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1724–1738. PMLR.
  * Rosenski et al., (2016) Rosenski, J., Shamir, O., and Szlak, L. (2016).  Multi-player bandits – a musical chairs approach.  In International Conference on Machine Learning, pages 155–163.
  * Rusmevichientong and Tsitsiklis, (2010) Rusmevichientong, P. and Tsitsiklis, J. N. (2010).  Linearly parameterized bandits.  Math. Oper. Res., 35:395–411.
  * Shi and Shen, (2021) Shi, C. and Shen, C. (2021).  Federated multi-armed bandits.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI).
  * Shi et al., (2021) Shi, C., Shen, C., and Yang, J. (2021).  Federated multi-armed bandits with personalization.  In Proceedings of the 24rd International Conference on Artificial Intelligence and Statistics (AISTATS).
  * Shi et al., (2020) Shi, C., Xiong, W., Shen, C., and Yang, J. (2020).  Decentralized multi-player multi-armed bandits with no collision information.  In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), Palermo, Sicily, Italy.
  * Szorenyi et al., (2013) Szorenyi, B., Busa-Fekete, R., Hegedus, I., Ormandi, R., Jelasity, M., and Kegl, B. (2013).  Gossip-based distributed stochastic bandit algorithms.  In Proceedings of the 30th International Conference on Machine Learning, pages 19–27.
  * Todd, (2016) Todd, M. J. (2016).  Minimum-Volume Ellipsoids.  Society for Industrial and Applied Mathematics, Philadelphia, PA.
  * Valko et al., (2013) Valko, M., Korda, N., Munos, R., Flaounas, I., and Cristianini, N. (2013).  Finite-time analysis of kernelised contextual bandits.  In Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, pages 654–663.
  * Wang et al., (2020) Wang, Y., Hu, J., Chen, X., and Wang, L. (2020).  Distributed bandit learning: Near-optimal regret with efficient communication.  In International Conference on Learning Representations.
  * Wu et al., (2016) Wu, Q., Wang, H., Gu, Q., and Wang, H. (2016).  Contextual bandits in a collaborative environment.  In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 529–538.
  * Zhu et al., (2021) Zhu, Z., Zhu, J., Liu, J., and Liu, Y. (2021).  Federated bandit: A gossiping approach.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1–29.