Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2205.01970 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908347371880448 |
|---|---|
| author | Liu, Yueyang Kuang, Xu Van Roy, Benjamin |
| author_facet | Liu, Yueyang Kuang, Xu Van Roy, Benjamin |
| contents | Thompson sampling has proven effective across a wide range of stationary bandit environments. However, as we demonstrate in this paper, it can perform poorly when applied to non-stationary environments. We attribute such failures to the fact that, when exploring, the algorithm does not differentiate actions based on how quickly the information acquired loses its usefulness due to non-stationarity. Building upon this insight, we propose predictive sampling, an algorithm that deprioritizes acquiring information that quickly loses usefulness. A theoretical guarantee on the performance of predictive sampling is established through a Bayesian regret bound. We provide versions of predictive sampling for which computations tractably scale to complex bandit environments of practical interest. Through numerical simulations, we demonstrate that predictive sampling outperforms Thompson sampling in all non-stationary environments examined. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_01970 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Non-Stationary Bandit Learning via Predictive Sampling Liu, Yueyang Kuang, Xu Van Roy, Benjamin Machine Learning Thompson sampling has proven effective across a wide range of stationary bandit environments. However, as we demonstrate in this paper, it can perform poorly when applied to non-stationary environments. We attribute such failures to the fact that, when exploring, the algorithm does not differentiate actions based on how quickly the information acquired loses its usefulness due to non-stationarity. Building upon this insight, we propose predictive sampling, an algorithm that deprioritizes acquiring information that quickly loses usefulness. A theoretical guarantee on the performance of predictive sampling is established through a Bayesian regret bound. We provide versions of predictive sampling for which computations tractably scale to complex bandit environments of practical interest. Through numerical simulations, we demonstrate that predictive sampling outperforms Thompson sampling in all non-stationary environments examined. |
| title | Non-Stationary Bandit Learning via Predictive Sampling |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2205.01970 |