The paper has been discussed after the rebuttal that the reviewers found useful and actionable (e.g., concerns about the confidence bound). The paper is recommended for acceptance. All reviewers have acknowledged that the paper is well motivated, well written and establishes a nice interplay between theory and a practical problem of interest.