JSM 2015 Preliminary Program

Online Program Home
My Program

Abstract Details

Activity Number: 111
Type: Invited
Date/Time: Monday, August 10, 2015 : 8:30 AM to 10:20 AM
Sponsor: IMS
Abstract #314550
Title: Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
Author(s): Alekh Agarwal and Robert Schapire*
Companies: Microsoft Research and Microsoft Research/Princeton University
Keywords: reinforcement learning ; exploration/exploitation
Abstract:

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only \tilde{O}(\sqrt{KT}) oracle calls across all T rounds. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We further conduct a proof-of-concept experiment which demonstrates the excellent computational and prediction performance of (an online variant of) our algorithm relative to several baselines. [Joint work with Daniel Hsu, Satyen Kale, John Langford, Lihong Li and Rob Schapire]


Authors who are presenting talks have a * after their name.

Back to the full JSM 2015 program





For program information, contact the JSM Registration Department or phone (888) 231-3473.

For Professional Development information, contact the Education Department.

The views expressed here are those of the individual authors and not necessarily those of the JSM sponsors, their officers, or their staff.

2015 JSM Online Program Home