Experience-efficient learning in associative bandit problems Export

@inproceedings{citeulike:3363223, abstract = {We formalize the associative bandit problem framework introduced by Kaelbling as a learning-theory problem. The learning environment is modeled as a k -armed bandit where arm payoffs are conditioned on an observable input selected on each trial. We show that, if the payoff functions are constrained to a known hypothesis class, learning can be performed efficiently with respect to the VC dimension of this class. We formally reduce the problem of PAC classification to the associative bandit problem, producing an efficient algorithm for any hypothesis class for which efficient classification algorithms are known. We demonstrate the approach empirically on a scalable concept class.}, address = {New York, NY, USA}, author = {Strehl, Alexander L. and Mesterharm, Chris and Littman, Michael L. and Hirsh, Haym}, booktitle = {ICML '06: Proceedings of the 23rd International Conference on Machine Learning}, citeulike-article-id = {3363223}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1143956}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1143844.1143956}, doi = {10.1145/1143844.1143956}, isbn = {1-59593-383-2}, keywords = {associative\_bandits, bandit\_problem, learning\_theory}, location = {Pittsburgh, Pennsylvania}, pages = {889--896}, posted-at = {2008-10-01 17:11:09}, priority = {2}, publisher = {ACM}, title = {Experience-efficient learning in associative bandit problems}, url = {http://dx.doi.org/10.1145/1143844.1143956}, year = {2006} }

TY - CONF ID - citeulike:3363223 L3 - citeulike-article-id:3363223 N2 - We formalize the associative bandit problem framework introduced by Kaelbling as a learning-theory problem. The learning environment is modeled as a k -armed bandit where arm payoffs are conditioned on an observable input selected on each trial. We show that, if the payoff functions are constrained to a known hypothesis class, learning can be performed efficiently with respect to the VC dimension of this class. We formally reduce the problem of PAC classification to the associative bandit problem, producing an efficient algorithm for any hypothesis class for which efficient classification algorithms are known. We demonstrate the approach empirically on a scalable concept class. CY - Pittsburgh, Pennsylvania SN - 1-59593-383-2 AD - New York, NY, USA EP - 896 TI - Experience-efficient learning in associative bandit problems PB - ACM T2 - ICML '06: Proceedings of the 23rd International Conference on Machine Learning SP - 889 KW - associative_bandits KW - bandit_problem KW - learning_theory AU - Strehl, Alexander AU - Mesterharm, Chris AU - Littman, Michael AU - Hirsh, Haym PY - 2006/// UR - http://dx.doi.org/10.1145/1143844.1143956 ER -