Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Efficient Optimal Learning for Contextual Bandits
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang
Abstract:
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. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.
Keywords:
Pages: 169-178
PS Link:
PDF Link: /papers/11/p169-dudik.pdf
BibTex:
@INPROCEEDINGS{Dudik11,
AUTHOR = "Miroslav Dudik and Daniel Hsu and Satyen Kale and Nikos Karampatziakis and John Langford and Lev Reyzin and Tong Zhang",
TITLE = "Efficient Optimal Learning for Contextual Bandits",
BOOKTITLE = "Proceedings of the Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "169--178"
}


hosted by DSL   •   site info   •   help