weakness in the algorithm is the handling of the discretization. It seems that two improvements are somewhat easily achievable: First, there should probably be a way to obtain instance dependent bounds for the continuous setting. It seems that by taking a confidence bound of size \sqrt{log(st)/T_{i,t}} rather than \sqrt{log(t)/T_{i,t}}, one can get a logarithmic dependence on s, rather than polynomial, which may solve this issue. If that doesnât work, the paper should benefit from an explanation for why that doesnât work. Second, it seems that the discretization should be adaptive to the data. Otherwise, the running time and memory are dependent of the time horizon in cases where they do not have to. Overall, the paper is well written and motivated. Its results, though having room for improvement are non-trivial and deserve publication. Minor comments: - Where else was the k-max problem discussed? Please provide a citation for this.
- Where else was the k-max problem discussed? Please provide a citation for this.