The paper is a refinement of a previous work of from ICML 2018. The bounds are sometimes significantly better. The main reservation expressed by reviewers is a lack of quantitative comparison to that prior work [22], and generally some understanding of whether this new work finally identifies the "right" dependence on these various quantities. Some interesting examples could help with the first issue, and proving lower bounds could help with the second issue. (It follows from known results that \tilde{\theta} would not show up in a lower bound, but it would still be good to know whether the new bound has the right dependence on the other quantities, say in the case that \tilde{\theta} is O(1)). I believe the paper is acceptable. However, I would like to strongly suggest that the authors try to address these issues in the camera ready version, ideally providing interesting (and non-contrived) examples to illustrate the improvements in the new bound, and trying to provide a lower bound that reflects what the "right" dependence on various parameters is.