2021-03-18-ding21a.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
An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling	We consider the contextual bandit problem, where a player sequentially makes decisions based on past observations to maximize the cumulative reward. Although many algorithms have been proposed for contextual bandit, most of them rely on finding the maximum likelihood estimator at each iteration, which requires $O(t)$ time at the $t$-th iteration and are memory inefficient. A natural way to resolve this problem is to apply online stochastic gradient descent (SGD) so that the per-step time and memory complexity can be reduced to constant with respect to $t$, but a contextual bandit policy based on online SGD updates that balances exploration and exploitation has remained elusive. In this work, we show that online SGD can be applied to the generalized linear bandit problem. The proposed SGD-TS algorithm, which uses a single-step SGD update to exploit past information and uses Thompson Sampling for exploration, achieves $\tilde{O}(\sqrt{T})$ regret with the total time complexity that scales linearly in $T$ and $d$, where $T$ is the total number of rounds and $d$ is the number of features. Experimental results show that SGD-TS consistently outperforms existing algorithms on both synthetic and real datasets.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	ding21a	0	An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling	1585	1593	1585-1593	1585	false	Ding, Qin and Hsieh, Cho-Jui and Sharpnack, James	given family Qin Ding given family Cho-Jui Hsieh given family James Sharpnack	2021-03-18		Proceedings of The 24th International Conference on Artificial Intelligence and Statistics	130	inproceedings	date-parts 2021 3 18	http://proceedings.mlr.press/v130/ding21a/ding21a.pdf	label link Supplementary PDF http://proceedings.mlr.press/v130/ding21a/ding21a-supp.pdf