Review for NeurIPS paper: Secretary and Online Matching Problems with Machine Learned Advice

Summary and Contributions: Recently there has been a spate of work in online algorithms combining traditional online algorithms with "machine learned" advice. In such problems, one has access to an exogenous prediction about the problem, and one hopes for best of both worlds guarantees of the form: "if the prediction is good, then I do really well (beating the worst-case benchmark), but if the prediction is bad, then I still do (approximately) at least as well as the worst-case benchmark". In the secretary problem, you observe a stream of n real numbers that arrives in a uniformly random order. Your goal is to choose the largest element (or at least achieve a good approximation to the largest element). In the setting with advice, you are given a prediction p of the maximum value of all n real numbers.