Online Linear Optimization with Sparsity Constraints


Jun-Kun Wang, Chi-Jen Lu, Shou-De Lin ;
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:883-897, 2019.


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.

Related Material