Parallel Best Arm Identification in Heterogeneous Environments
This work addresses the challenge of parallel learning in distributed systems with varying environments, which is incremental as it builds on existing collaborative learning models.
The paper tackles the best arm identification problem in heterogeneous collaborative learning, where multiple agents interact with different environments to learn an aggregated objective function, and shows that this setting is inherently more difficult than homogeneous settings in terms of time-round tradeoffs, with almost tight upper and lower bounds proven.
In this paper, we study the tradeoffs between the time and the number of communication rounds of the best arm identification problem in the heterogeneous collaborative learning model, where multiple agents interact with possibly different environments and they want to learn in parallel an objective function in the aggregated environment. By proving almost tight upper and lower bounds, we show that collaborative learning in the heterogeneous setting is inherently more difficult than that in the homogeneous setting in terms of the time-round tradeoff.