The original paper of Auer [1] requires bandit arms to have a reward distribution bounded on [0,1] for the Upper-Confidence-Bound (UCB) theorems to hold. I was wondering how strict this requirement is in practice, i.e. does UCB performs well when this reward bound requirement is not met?

If this requirement is strict, I'm aware I could attempt to rescale the rewards. I was however not able to find much pointers on how to rescale a floating point (say an IEEE-754 double precision float) properly to a double precision float in [0,1]. With properly, I mean, to retain as much of the features of the reward distribution as possible and to keep the updating of Q values as numerically stable as possible.

[1] Auer, Peter, Nicolo Cesa-Bianchi, and Paul Fischer. "Finite-time analysis of the multiarmed bandit problem." Machine learning 47.2-3 (2002): 235-256.


1 Answer 1


UCB algorithms work well for more general distributions, though the weighting between the mean and variance may change a bit. For example in the case where rewards are sampled from a high-dimensional Gaussian process, Srinivas et al. derive near-optimal regret bounds for a UCB algorithm in their paper "Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.