The reviews agree on the interest of the paper, and provide a good number of suggestions for improvements for the final version. In particular, the authors should explain better the motivation for their alternative definition of the regret, and (although most issues raised by the reviewers were addressed in the rebuttal, which tended to convince the reviewers) the criticism of one reviewer on optimality was not addressed properly answered to: improving this point would be a significant good point for the final version.