2021-07-01-baudry21b.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
On Limited-Memory Subsampling Strategies for Bandits	There has been a recent surge of interest in non-parametric bandit algorithms based on subsampling. One drawback however of these approaches is the additional complexity required by random subsampling and the storage of the full history of rewards. Our first contribution is to show that a simple deterministic subsampling rule, proposed in the recent work of \citet{baudry2020sub} under the name of “last-block subsampling”, is asymptotically optimal in one-parameter exponential families. In addition, we prove that these guarantees also hold when limiting the algorithm memory to a polylogarithmic function of the time horizon. These findings open up new perspectives, in particular for non-stationary scenarios in which the arm distributions evolve over time. We propose a variant of the algorithm in which only the most recent observations are used for subsampling, achieving optimal regret guarantees under the assumption of a known number of abrupt changes. Extensive numerical simulations highlight the merits of this approach, particularly when the changes are not only affecting the means of the rewards.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	baudry21b	0	On Limited-Memory Subsampling Strategies for Bandits	727	737	727-737	727	false	Baudry, Dorian and Russac, Yoan and Capp{\'e}, Olivier	given family Dorian Baudry given family Yoan Russac given family Olivier Cappé	2021-07-01		Proceedings of the 38th International Conference on Machine Learning	139	inproceedings	date-parts 2021 7 1	http://proceedings.mlr.press/v139/baudry21b/baudry21b.pdf	label link Supplementary PDF http://proceedings.mlr.press/v139/baudry21b/baudry21b-supp.pdf