Efficient algorithms for adversarial contextual learning

Vasilis Syrgkanis, Akshay Krishnamurthy, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We provide the first oracle efficient sublinear regret algorithms for adversarial versions of the contextual bandit problem. In this problem, the learner repeatedly makes an action on the basis of a context and receives reward for the chosen action. with the goal of achieving reward competitive with a large class of policies. We analyze two settings: i) in the transductive setting the learner knows the set of contexts a priori, ii) in the small separator setting, there exists a small set of con-texts such that any two policies behave differently on one of the contexts in the set. Our algorithms fall into the Follow-The-Perturbed-Leader family (Kalai & Vempala, 2005) and achieve regret 0{T3/4 sj'K log(iV)) in the transductive setting and 0{T2t&Ky/\og(N)) in the separator setting, where T is the number of rounds, K is the number of actions, N is the number of baseline policies, and d is the size of the separator. We actually solve the more general adversarial contextual semi-bandit linear optimization problem, whilst in the full information setting we address the even more general contextual combinatorial optimization. We provide several extensions and implications of our algorithms, such as switching regret and efficient learning with predictable sequences.

Original languageEnglish (US)
Title of host publication33rd International Conference on Machine Learning, ICML 2016
EditorsKilian Q. Weinberger, Maria Florina Balcan
PublisherInternational Machine Learning Society (IMLS)
Pages3184-3206
Number of pages23
ISBN (Electronic)9781510829008
StatePublished - Jan 1 2016
Externally publishedYes
Event33rd International Conference on Machine Learning, ICML 2016 - New York City, United States
Duration: Jun 19 2016Jun 24 2016

Publication series

Name33rd International Conference on Machine Learning, ICML 2016
Volume5

Other

Other33rd International Conference on Machine Learning, ICML 2016
CountryUnited States
CityNew York City
Period6/19/166/24/16

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Efficient algorithms for adversarial contextual learning'. Together they form a unique fingerprint.

  • Cite this

    Syrgkanis, V., Krishnamurthy, A., & Schapire, R. E. (2016). Efficient algorithms for adversarial contextual learning. In K. Q. Weinberger, & M. F. Balcan (Eds.), 33rd International Conference on Machine Learning, ICML 2016 (pp. 3184-3206). (33rd International Conference on Machine Learning, ICML 2016; Vol. 5). International Machine Learning Society (IMLS).