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!