Experience-efficient learning in associative bandit problems
Experience-efficient learning in associative bandit problems
复制标题
联想强盗问题中的体验高效学习
DOI：
10.1145/1143844.1143956
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
H. Hirsh
中科院分区：
文献类型：
--
作者：
Alexander L. Strehl;Chris Mesterharm;M. Littman;H. Hirsh
我们将 Kaelbling 引入的联想老虎机问题框架形式化为学习理论问题。学习环境被建模为 k 臂老虎机，其中臂收益取决于每次试验中选择的可观察输入。我们证明，如果收益函数被限制在一个已知的假设类，则可以针对该类的 VC 维度有效地进行学习。我们将 PAC 分类问题正式简化为关联老虎机问题，为已知有效分类算法的任何假设类生成有效算法。我们在可扩展的概念类上凭经验演示了该方法。
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.