The Library
Optimistic bayesian sampling in contextual-bandit problems
Tools
May, Benedict C., Korda, Nathan, Lee, Anthony and Leslie, David S. (2012) Optimistic bayesian sampling in contextual-bandit problems. Journal of Machine Learning Research, Vol.98888 . pp. 2069-2106. ISSN 1532-4435.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dl.acm.org/citation.cfm?id=2343676&picked=p...
Abstract
In sequential decision problems in an unknown environment, the decision maker often faces a dilemma over whether to explore to discover more about the environment, or to exploit current knowledge. We address the exploration-exploitation dilemma in a general setting encompassing both standard and contextualised bandit problems. The contextual bandit problem has recently resurfaced in attempts to maximise click-through rates in web based applications, a task with significant commercial interest. In this article we consider an approach of Thompson (1933) which makes use of samples from the posterior distributions for the instantaneous value of each action. We extend the approach by introducing a new algorithm, Optimistic Bayesian Sampling (OBS), in which the probability of playing an action increases with the uncertainty in the estimate of the action value. This results in better directed exploratory behaviour. We prove that, under unrestrictive assumptions, both approaches result in optimal behaviour with respect to the average reward criterion of Yang and Zhu (2002). We implement OBS and measure its performance in simulated Bernoulli bandit and linear regression domains, and also when tested with the task of personalised news article recommendation on a Yahoo! Front Page Today Module data set. We find that OBS performs competitively when compared to recently proposed benchmark algorithms and outperforms Thompson's method throughout.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||
Journal or Publication Title: | Journal of Machine Learning Research | ||||
Publisher: | M I T Press | ||||
ISSN: | 1532-4435 | ||||
Official Date: | 6 January 2012 | ||||
Dates: |
|
||||
Volume: | Vol.98888 | ||||
Page Range: | pp. 2069-2106 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |