Experience-efficient learning in associative bandit problems

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.

REFERENCES

• 1: Abe, N., Biermann, A. W., & Long, P. M. (2003). Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37, 263--293.
• 2: Peter Auer, An Improved On-line Algorithm for Learning Linear Evaluation Functions, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.118-125, June 28-July 01, 2000
• 3: Berry, D. A., & Fristedt, B. (1985). Bandit problems: Sequential allocation of experiments. London, UK: Chapman and Hall.
• 4: Elkan, C. (2001). The foundations of cost-sensitive learning. IJCAI (pp. 973--978).
• 5: Fiechter, C.-N. (1995). PAC associative reinforcement learning. Unpublished manuscript.
• 6: Claude-Nicolas Fiechter, Expected Mistake Bound Model for On-Line Reinforcement Learning, Proceedings of the Fourteenth International Conference on Machine Learning, p.116-124, July 08-12, 1997
• 7: Fong, P. W. L. (1995). A quantitative study of hypothesis selection. Proceedings of the Twelfth International Conference on Machine Learning (ICML-95) (pp. 226--234).
• 8: Leslie Pack Kaelbling, Associative Reinforcement Learning: Functions in k-DNF, Machine Learning, v.15 n.3, p.279-298, June 1994 [doi>10.1023/A:1022689909846]
• 9: Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
• 10: Langford, J., & Zadrozny, B. (2005). Estimating class membership probabilities using classifier learners. Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (pp. 198--205).
• 11: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 12: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 13: Bianca Zadrozny , John Langford , Naoki Abe, Cost-Sensitive Learning by Cost-Proportionate Example Weighting, Proceedings of the Third IEEE International Conference on Data Mining, p.435, November 19-22, 2003

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

General Terms:
Algorithms