The notion of regret to the top epsilon-quantile was actually considered earlier by Bobby Kleinberg in his work on multi-armed bandit problems with very large or infinite strategy sets [1,2]. [1] R. Kleinberg, Online decision problems with large strategy sets. Ph.D. Thesis, MIT, 2005. [2] R. Kleinberg, Anytime algorithms for multi-armed bandit problems. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 928-936. We thank Bobby for pointing us to his work and apologize for this oversight!