Online Linear Optimization with Sparsity Constraints
Abstract
We study the problem of online linear optimization with sparsity constraints in the semi-bandit setting. It can be seen as a marriage between two well-known problems: the online linear optimization problem and the combinatorial bandit problem. For this problem, we provide an algorithm which is efficient and achieves a sublinear regret bound. Moreover, we extend our results to two generalized settings, one with delayed feedbacks and one with costs for receiving feedbacks. Finally, we conduct experiments which show the effectiveness of our methods in practice.
Cite
Text
Wang et al. "Online Linear Optimization with Sparsity Constraints." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.Markdown
[Wang et al. "Online Linear Optimization with Sparsity Constraints." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.](https://mlanthology.org/alt/2019/wang2019alt-online/)BibTeX
@inproceedings{wang2019alt-online,
title = {{Online Linear Optimization with Sparsity Constraints}},
author = {Wang, Jun-Kun and Lu, Chi-Jen and Lin, Shou-De},
booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory},
year = {2019},
pages = {883-897},
volume = {98},
url = {https://mlanthology.org/alt/2019/wang2019alt-online/}
}