Time-Sensitive Bandit Learning and Satisficing Thompson Sampling
By Daniel Russo, David Tse, Benjamin Van Roy. 2017
12 citations recorded by the source corpus.
The literature on bandit learning and regret analysis has focused on contexts where the goal is to converge on an optimal action in a manner that limits exploration costs. One shortcoming imposed by this orientation is that it does not treat time preference in a coherent manner. Time preference plays an important role when the optimal action is costly to learn relative to near-optimal actions. This limitation has not only restricted the relevance of theoretical results but has also influenced the design of algorithms. Indeed, popular approaches such as Thompson sampling and UCB can fare poorly in such situations. In this paper, we consider discounted rather than cumulative regret, where a discount factor encodes time preference. We propose satisficing Thompson sampling -- a variation of Thompson sampling -- and establish a strong discounted regret bound for this new algorithm.
Subfields: Artificial Intelligence, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- George Tucker
- Jasper Snoek
- Carlos Riquelme
- Sergey Levine
- Frank Hutter
- Ruslan Salakhutdinov
- Quoc V. Le
- Chelsea Finn
In Management Science and Operations Research
- Jasper Snoek
- George Tucker
- Carlos Riquelme
- Sergey Levine
- Shixiang Shane Gu
- Ofir Nachum
- Aviral Kumar
- Carl E. Rasmussen
Citations in the corpus
- Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, background): “In addition, Thompson Sampling does not take into account the time horizon where the process ends, and if known, exploration efforts could be tuned accordingly [33].”