Batched Nonparametric Contextual Bandits

arXiv:2402.17732v1 Announce Type: cross
Abstract: We study nonparametric contextual bandits under batch constraints, where the expected reward for each action is modeled as a smooth function of covariates, and the policy updates are made at the end of each batch of observations. We establish a minimax regret lower bound for this setting and propose Batched Successive Elimination with Dynamic Binning (BaSEDB) that achieves optimal regret (up to logarithmic factors). In essence, BaSEDB dynamically splits the covariate space into smaller bins, …

abstract arxiv constraints cs.lg function math.st minimax policy stat.ml stat.th study the end type updates