Lipschitz Bandits with Batched Feedback
This addresses communication efficiency in online learning for scenarios like distributed systems, though it is incremental as it builds on existing Lipschitz bandit frameworks.
The paper tackles the Lipschitz bandit problem with batched feedback by introducing the BLiN algorithm, which achieves an optimal regret rate of $\widetilde{\mathcal{O}}\left(T^{ rac{d_z+1}{d_z+2}} ight)$ using only $\mathcal{O}(\log\log T)$ batches, matching a theoretical lower bound.
In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for a $T$-step problem with Lipschitz reward of zooming dimension $d_z$, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate $\widetilde{\mathcal{O}}\left(T^{\frac{d_z+1}{d_z+2}}\right)$ using only $ \mathcal{O} \left( \log\log T\right) $ batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that $Ω(\log\log T)$ batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate (up to logarithmic factors) using minimal communication.