Using Upper Confidence Bounds for Online Learning

We show how a standard tool from statistics, namely confidence bounds, can be used to elegantly deal with situations which exhibit an exploitation/exploration trade-off. Our technique for designing and analyzing algorithms for such situations is very general and can be applied when an algorithm has to make exploitation-versus-exploration decisions based on uncertain information provided by a random process. We consider two models with such an exploitation/exploration trade-off. For the adversarial bandit problem our new algorithm suffers only O/spl tilde/(T/sup 1/2/) regret over T trials which improves significantly over the previously best O/spl tilde/(T/sup 2/3/) regret. We also extend our results for the adversarial bandit problem to shifting bandits. The second model we consider is associative reinforcement learning with linear value functions. For this model our technique improves the regret from O/spl tilde/(T/sup 3/4/) to O/spl tilde/(T/sup 1/2/).

Authors

• Peter Auer

Keywords

• Algorithm design and analysis
• Random variables
• Learning
• Computer science
• Statistical analysis
• Information analysis
• Random processes
• Uncertainty
• Confidence Level
• Upper Confidence
• Upper Confidence Bound
• High Probability
• Learning Algorithms
• Linear Function
• Assertive
• Gambling
• Weight Vector
• Simple Algorithm
• Associative Learning
• Algorithm For Problem
• Independent Random Variables
• Unknown Vector
• Reinforcement Learning Model
• Confidence In The Use
• Exploitation And Exploration
• Slot Machines
• Bandit Problem