Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem

arXiv:2404.01198v1 Announce Type: new
Abstract: We give nearly-tight upper and lower bounds for the improving multi-armed bandits problem. An instance of this problem has $k$ arms, each of whose reward function is a concave and increasing function of the number of times that arm has been pulled so far. We show that for any randomized online algorithm, there exists an instance on which it must suffer at least an $\Omega(\sqrt{k})$ approximation factor relative to the optimal reward. We then provide …

abstract approximation arm arxiv cs.ds cs.lg function improving instance multi-armed bandits show stat.ml type