Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems
This work obtains an algorithm that works for a large class of ``monotone''stochastic problems, including prophet inequality, Pandora's box, series testing, stochastic knapsack and stochastic matching, and improves over previous regret bounds by a $\sqrt{n}$ factor.