Lipschitz Bandits with Batched Feedback
  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
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
$\Omega(\log\log T)$ batches are necessary for any algorithm to achieve the
optimal regret. Thus, BLiN achieves optimal regret rate using minimal
communication.
