Using Confidence Bounds for Exploitation-Exploration Trade-offs Export

@article{citeulike:2561921, 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 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 apply our technique to two models with such an exploitation-exploration trade-off. For the adversarial bandit problem with shifting our new algorithm suffers only O (( ST ) 1/2 ) regret with high probability over T trials with S shifts. Such a regret bound was previously known only in expectation . 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 ).}, address = {Cambridge, MA, USA}, author = {Auer, Peter}, citeulike-article-id = {2561921}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=944941}, comment = {Journal version of Auer's 2000 paper "Using Upper Confidence Bounds for Online Learning".}, issn = {1532-4435}, journal = {The Journal of Machine Learning Research}, keywords = {adaptive\_adversarial, bandit\_problem, confidence\_bounds, exploitation\_exploration}, pages = {397--422}, posted-at = {2008-03-19 14:46:09}, priority = {0}, publisher = {JMLR.org}, title = {Using Confidence Bounds for Exploitation-Exploration Trade-offs}, url = {http://portal.acm.org/citation.cfm?id=944941}, volume = {3}, year = {2003} }

TY - JOUR ID - citeulike:2561921 L3 - citeulike-article-id:2561921 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 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 apply our technique to two models with such an exploitation-exploration trade-off. For the adversarial bandit problem with shifting our new algorithm suffers only O (( ST ) 1/2 ) regret with high probability over T trials with S shifts. Such a regret bound was previously known only in expectation . 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 ). JF - The Journal of Machine Learning Research SN - 1532-4435 AD - Cambridge, MA, USA EP - 422 TI - Using Confidence Bounds for Exploitation-Exploration Trade-offs PB - JMLR.org VL - 3 SP - 397 KW - adaptive_adversarial KW - bandit_problem KW - confidence_bounds KW - exploitation_exploration N1 - Journal version of Auer's 2000 paper "Using Upper Confidence Bounds for Online Learning". AU - Auer, Peter PY - 2003/// UR - http://portal.acm.org/citation.cfm?id=944941 ER -