Learning Online Algorithms with Distributional Advice

We study the problem of designing online algorithms given advice about the input. While prior work had focused on deterministic advice, we only assume distributional access to the instances of interest, and the goal is to learn a competitive algorithm given access to i.i.d. samples. We aim to be competitive against an adversary with prior knowledge of the distribution, while also performing well against worst-case inputs. We focus on the classical online problems of skirental and prophet-inequalities, and provide sample complexity bounds for the underlying learning tasks. First, we point out that for general distributions it is information-theoretically impossible to beat the worst-case competitive-ratio with any finite sample size. As our main contribution, we establish strong positive results for wellbehaved distributions. Specifically, for the broad class of log-concave distributions, we show that poly(1/ ) samples suffice to obtain (1 + )competitive ratio. Finally, we show that this sample upper bound is close to best possible, even for very simple classes of distributions.