AI Seminar

Efficient Optimal Learning for Contextual Bandits

Satyen Kale

IBM Research
Tuesday, September 24, 2013
4:00pm - 5:30pm
3725 BBB

Add to Google Calendar

About the Event

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time polylog(N), where N is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting.


Satyen Kale is a research staff member at IBM T.J. Watson Research Center working on algorithms for fundamental problems in Machine Learning and Optimization. His main research interests are decision making under uncertainty, statistical learning theory, combinatorial optimization and convex optimization. Previously, he was a postdoc at Yahoo! Research, Santa Clara, CA and Microsoft Research New England, Cambridge, MA. In 2007, he completed his Ph.D. in the department of Computer Science at Princeton University, under the supervision of Prof. Sanjeev Arora. He completed his B.Tech in Computer Science at the Indian Institute of Technology, Bombay in 2002.

Additional Information

Sponsor(s): Toyota

Open to: Public