Lipschitz Bandits with Batched Feedback

Yasong Feng · zengfeng Huang · Tianyu Wang

Keywords: [ Lipschitz bandits ] [ batched bandits ]

[ Abstract ]
[

Spotlight presentation: Lightning Talks 2A-1
Tue 6 Dec 5 p.m. PST — 5:15 p.m. PST

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

Chat is not available.