2021-07-01-alieva21a.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
Robust Pure Exploration in Linear Bandits with Limited Budget	We consider the pure exploration problem in the fixed-budget linear bandit setting. We provide a new algorithm that identifies the best arm with high probability while being robust to unknown levels of observation noise as well as to moderate levels of misspecification in the linear model. Our technique combines prior approaches to pure exploration in the multi-armed bandit problem with optimal experimental design algorithms to obtain both problem dependent and problem independent bounds. Our success probability is never worse than that of an algorithm that ignores the linear structure, but seamlessly takes advantage of such structure when possible. Furthermore, we only need the number of samples to scale with the dimension of the problem rather than the number of arms. We complement our theoretical results with empirical validation.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	alieva21a	0	Robust Pure Exploration in Linear Bandits with Limited Budget	187	195	187-195	187	false	Alieva, Ayya and Cutkosky, Ashok and Das, Abhimanyu	given family Ayya Alieva given family Ashok Cutkosky given family Abhimanyu Das	2021-07-01		Proceedings of the 38th International Conference on Machine Learning	139	inproceedings	date-parts 2021 7 1	http://proceedings.mlr.press/v139/alieva21a/alieva21a.pdf	label link Supplementary PDF http://proceedings.mlr.press/v139/alieva21a/alieva21a-supp.pdf