The offset tree for learning with partial labels

ABSTRACT

We present an algorithm, called the Offset Tree, for learning to make decisions in situations where the payoff of only one choice is observed, rather than all choices. The algorithm reduces this setting to binary classification, allowing one to reuse any existing, fully supervised binary classification algorithm in this partial information setting. We show that the Offset Tree is an optimal reduction to binary classification. In particular, it has regret at most (k-1) times the regret of the binary classifier it uses (where k is the number of choices), and no reduction to binary classification can do better. This reduction is also computationally optimal, both at training and test time, requiring just O(log₂ k) work to train on an example or make a prediction.

Experiments with the Offset Tree show that it generally performs better than several alternative approaches.

REFERENCES

• 1: N. Abe, A. Biermann, and P. Long. Reinforcement learning with immediate rewards and linear hypotheses, Algorithmica, 37(4): 263--293, 2003.
• 2: Peter Auer, Using confidence bounds for exploitation-exploration trade-offs, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.322, October 23-25, 1995
• 4: Sham M. Kakade , Shai Shalev-Shwartz , Ambuj Tewari, Efficient bandit algorithms for online multiclass prediction, Proceedings of the 25th international conference on Machine learning, p.440-447, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390212]
• 5: Eyal Even-Dar , Shie Mannor , Yishay Mansour, Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems, The Journal of Machine Learning Research, 7, p.1079-1105, 12/1/2006
• 6: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 7: Trevor Hastie , Robert Tibshirani, Classification by pairwise coupling, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.507-513, July 1998, Denver, Colorado, United States
• 8: J. Heckman. Sample selection bias as a specification error, Econometrica, 47(1): 153--161, 1979.
• 9: M. Kearns, Y. Mansour, and A. Y. Ng. Approximate planning in large POMDPs via reusable trajectories, Advances in Neural Information Processing Systems (NIPS), 12, 2000.
• 10: S. Kulkarni. On bandit problems with side observations and learnability, Proceedings of the 31st Allerton Conference on Communication, Control, and Computing, 83--92, 1993.
• 11: John Langford, Tutorial on Practical Prediction Theory for Classification, The Journal of Machine Learning Research, 6, p.273-306, 12/1/2005
• 12: J. Langford and A. Beygelzimer. http://hunch.net/?p=343.
• 13: J. Langford and T. Zhang. The Epoch-greedy algorithm for contextual multiarmed bandits, Advances in Neural Information Processing Systems (NIPS), 2007.
• 14: S. Pandey, D. Agarwal, D. Chakrabati, V. Josifovski. Bandits for taxonomies: a model based approach, Proceedings of the 7th SIAM International Conference on Data Mining (SIAM SDM), 2007.
• 15: H. Robbins. Some aspects of the sequential design of experiments, Bulletins of the American Mathematical Society, 58: 527--535, 1952.
• 16: Alexander L. Strehl , Chris Mesterharm , Michael L. Littman , Haym Hirsh, Experience-efficient learning in associative bandit problems, Proceedings of the 23rd international conference on Machine learning, p.889-896, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143956]
• 17: C. Blake and C. Merz. UCI Repository of machine learning databases. University of California, Irvine.
• 18: C. C. Wang, S. Kulkarni, and H. Vincent Poor. Bandit problems with side observations, IEEE Transactions on Automatic Control, 50(5), 2005.
• 19: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 20: M. Woodru . A one-armed bandit problem with concomitant variates, Journal of the American Statistical Association, 74 (368): 799--806, 1979.
• 21: B. Zadrozny. Ph.D. Thesis, University of California, San Diego, 2003.
• 22: 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.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Theory

Keywords:
associative reinforcement learning, contextual bandits, interactive learning