Batched Nonparametric Contextual Bandits

Autor:	Jiang, Rong, Ma, Cong
Rok vydání:	2024
Předmět:	Mathematics - Statistics Theory Computer Science - Machine Learning Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	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 a novel batch learning algorithm that achieves the optimal regret (up to logarithmic factors). In essence, our procedure dynamically splits the covariate space into smaller bins, carefully aligning their widths with the batch size. Our theoretical results suggest that for nonparametric contextual bandits, a nearly constant number of policy updates can attain optimal regret in the fully online setting. Comment: Add lower bound when grid is adaptively chosen; add results on adaptivity to margin parameter
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2402.17732 Zobrazit plný text záznamu View this record from Arxiv