A Time and Space Efficient Algorithm for Contextual Linear Bandits
Abstract
We consider a multi-armed bandit problem where payoffs are a linear function of an observed stochastic contextual variable. In the scenario where there exists a gap between optimal and suboptimal rewards, several algorithms have been proposed that achieve O(logT) regret after T time steps. However, proposed methods either have a computation complexity per iteration that scales linearly with T or achieve regrets that grow linearly with the number of contexts |i¾?|. We propose an e-greedy type of algorithm that solves both limitations. In particular, when contexts are variables in $I\!R^d$ , we prove that our algorithm has a constant computation complexity per iteration of O(poly(d)) and can achieve a regret of O(poly(d) logT) even when |i¾?| = Ω(2 d ) . In addition, unlike previous algorithms, its space complexity scales like O(Kd 2) and does not grow with T.
Cite
Text
Bento et al. "A Time and Space Efficient Algorithm for Contextual Linear Bandits." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2013. doi:10.1007/978-3-642-40988-2_17Markdown
[Bento et al. "A Time and Space Efficient Algorithm for Contextual Linear Bandits." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2013.](https://mlanthology.org/ecmlpkdd/2013/bento2013ecmlpkdd-time/) doi:10.1007/978-3-642-40988-2_17BibTeX
@inproceedings{bento2013ecmlpkdd-time,
title = {{A Time and Space Efficient Algorithm for Contextual Linear Bandits}},
author = {Bento, José and Ioannidis, Stratis and Muthukrishnan, S. and Yan, Jinyun},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2013},
pages = {257-272},
doi = {10.1007/978-3-642-40988-2_17},
url = {https://mlanthology.org/ecmlpkdd/2013/bento2013ecmlpkdd-time/}
}