Using upper confidence bounds for online learning

@inproceedings{citeulike:2530488, abstract = {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˜(T^1/2) regret over T trials which improves significantly over the previously best O˜(T^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˜(T^3/4) to O˜(T^1/2)}, author = {Auer, Peter }, booktitle = {41st Annual Symposium on Foundations of Computer Science (FOCS 2000)}, citeulike-article-id = {2530488}, doi = {http://dx.doi.org/10.1109/SFCS.2000.892116}, journal = {Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on}, keywords = {adversarial, bandit\_problem, confidence\_bounds, online\_learning}, pages = {270--279}, posted-at = {2008-03-14 03:11:15}, priority = {0}, title = {Using upper confidence bounds for online learning}, url = {http://dx.doi.org/10.1109/SFCS.2000.892116}, year = {2000} }

TY - CONF ID - citeulike:2530488 L3 - citeulike-article-id:2530488 TI - Using upper confidence bounds for online learning T2 - 41st Annual Symposium on Foundations of Computer Science (FOCS 2000) JF - Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on SP - 270 EP - 279 N2 - 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˜(T^1/2) regret over T trials which improves significantly over the previously best O˜(T^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˜(T^3/4) to O˜(T^1/2) KW - adversarial KW - bandit_problem KW - confidence_bounds KW - online_learning AU - Auer, Peter PY - 2000/// UR - http://dx.doi.org/10.1109/SFCS.2000.892116 ER -