| Exploration Scavenging | John Langford, Alexander Strehl, and Jennifer Wortman Exploration Scavenging ICML 2008 .tex | This is about how to make use of nonrandom accidental exploration in evaluating and optimizing new policies. | |
| Contextual Bandit->Classification | Alina Beygelzimer, John Langford, and Tong Zhang The Offset Tree for Learning with Partial Labels (in submission) an appendix | This paper reduces contextual bandit learning to binary classification. It also proves a matching lower bound on contextual bandit learning suggesting this problem is fundamentally harder. | |
| Contextual Bandit Learning | John Langford and Tong Zhang The Epoch-Greedy Algorithm for Contextual Multi-armed Bandits NIPS 2007 .tex | Adding side information to bandits creates a new (relatively unanalyzed) setting. This paper analyzes the first practical algorithm in that setting. | |
| Agnostic Active Learning | Nina Balcan, Alina Beygelzimer, John Langford Agnostic Active Learning ICML 2006 .tex Video lecture (journal version) | We show that active learning (the selective sampling version) is possible in situations with adversarially-placed noice. | See also this one which makes the algorithm more algorithmic and Steve's paper characterizing when speedups are possible. |
| Perfect Online Learning | Jacob Abernethy, John Langford, Manfred K. Warmuth Continuous Experts and the Binning Algorithm COLT 2006 .ps.gz .pdf .tex | This paper presents and proves a computationally tractable perfectly optimal online learning algorithm "binning" in the familiar experts setting for classification. |