2023-04-11-bhaskara23a.md

title	abstract	section	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
Competing against Adaptive Strategies in Online Learning via Hints	For many of the classic online learning settings, it is known that having a “hint” about the loss function before making a prediction yields significantly better regret guarantees. In this work we study the question, do hints allow us to go beyond the standard notion of regret (which competes against the best fixed strategy) and compete against adaptive or dynamic strategies? After all, if hints were perfect, we can clearly compete against a fully dynamic strategy. For some common online learning settings, we provide upper and lower bounds for the switching regret, i.e., the difference between the loss incurred by the algorithm and the optimal strategy in hindsight that switches state at most $L$ times, where $L$ is some parameter. We show positive results for online linear optimization and the classic experts problem. Interestingly, such results turn out to be impossible for the classic bandit setting.	Regular Papers	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	bhaskara23a	0	Competing against Adaptive Strategies in Online Learning via Hints	10409	10424	10409-10424	10409	false	Bhaskara, Aditya and Munagala, Kamesh	given family Aditya Bhaskara given family Kamesh Munagala	2023-04-11		Proceedings of The 26th International Conference on Artificial Intelligence and Statistics	206	inproceedings	date-parts 2023 4 11	https://proceedings.mlr.press/v206/bhaskara23a/bhaskara23a.pdf