The Contextual Bandits Problem: A New, Fast, and Simple Algorithm

Channel:
Microsoft Research
Subscribers:
342,000
Published on ● Video Link: https://www.youtube.com/watch?v=gzxRDw3lXv8


Duration: 1:00:56
11,958 views
151

We study the general problem of how to learn through experience to make intelligent decisions. In this setting, called the contextual bandits problem, the learner must repeatedly decide which action to take in response to an observed context, and is then permitted to observe the received reward, but only for the chosen action. The goal is to learn through experience to behave nearly as well as the best policy (or decision rule) in some possibly very large and rich space of candidate policies. Previous approaches to this problem were all highly inefficient and often extremely complicated. In this work, we present a new, fast, and simple algorithm that learns to behave as well as the best policy at a rate that is (almost) statistically optimal. Our approach assumes access to a kind of oracle for classification learning problems which can be used to select policies; in practice, most off-the-shelf classification algorithms could be used for this purpose. Our algorithm makes very modest use of the oracle, which it calls far less than once per round, on average, a huge improvement over previous methods. These properties suggest this may be the most practical contextual bandits algorithm among all existing approaches that are provably effective for general policy classes. This is joint work with Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford and Lihong Li.



Other Videos By Microsoft Research


2016-06-21Challenges in automated verification and synthesis for molecular programming
2016-06-21Decompositions of Natural Signals Still Need Fresh Ideas
2016-06-21Provable Non-convex Projections for High-dimensional Learning Problems -Part2
2016-06-21Optimal Design for Social Learning
2016-06-21Introduction to Machine Learning in Python with Scikit-Learn
2016-06-21Lab tutorial: Learning about Shape
2016-06-21Improving Behavioral Health Intervention Technologies: Harnessing the Human Side of Apps
2016-06-21Charles River Crypto Day - The Power of Negations in Cryptography
2016-06-21Scalable Kernel Methods via Doubly Stochastic Gradients
2016-06-21Molecular Tumor Boards: What they are; What they do; What they need
2016-06-21The Contextual Bandits Problem: A New, Fast, and Simple Algorithm
2016-06-21Cell cycle switching by an algorithm
2016-06-21Provable Non-convex Projections for High-dimensional Learning Problems - Part1
2016-06-21Northwest Probability Seminar 2014 - Sampling from the Fomin-Kirillov distribution
2016-06-21Computer Vision - StAR Lecture Series: Object Recognition
2016-06-21Local Deep Kernel Learning for Efficient Non-linear SVM Prediction
2016-06-21An Introduction to Concentration Inequalities and Statistical Learning Theory
2016-06-21Intelligible Machine Learning Models for HealthCare
2016-06-21An evolutionary view on information processing in cells
2016-06-21Online Learning and Bandits - Part 1
2016-06-21X1-Locally Non-linear Embeddings for Extreme Multi-label Learning


Tags:
microsoft research
machine learning
deep neural networks