Stochastic Online Greedy Learning with Semi-bandit Feedbacks - Lin, Tian; Li, Jian; Chen, Wei (Proceedings of the 29th Annual Conference on Advances in Neural Information Processing Systems (NIPS'2015), 2015)
The greedy algorithm is extensively studied in the ﬁeld of combinatorial optimization for decades. In this paper, we address the online learning problem when the input to the greedy algorithm is stochastic with unknown parameters that have to be learned over time. We ﬁrst propose the greedy regret and -quasi greedy regret as learning metrics comparing with the performance of ofﬂinegreedy algorithm. We then propose two online greedy learning algorithms with semi-bandit feedbacks, which use multi-armed bandit and pure exploration bandit policies at each level of greedy learning, one for each of the regret metrics respectively.Both algorithms achieve O(logT) problem-dependent regret bound (T being the time horizon) for a general class of combinatorial structures and reward functions that allow greedy solutions. We further show that the bound is tight in T and other problem instance parameters.