Piecewise-Stationary Bandit Problems with Side Observations
Abstract
We consider a sequential decision problem where the rewards are generated by a piecewise-stationary distribution. However, the different reward distributions are unknown and may change at unknown instants. Our approach uses a limited number of side observations on past rewards, but does not require prior knowledge of the frequency of changes. In spite of the adversarial nature of the reward process, we provide an algorithm whose regret, with respect to the baseline with perfect knowledge of the distributions and the changes, is $O(k \log(T))$, where $k$ is the number of changes up to time $T$. This is in contrast to the case where side observations are not available, and where the regret is at least $\Omega(\sqrt{T})$.
Cite
Text
Yu and Mannor. "Piecewise-Stationary Bandit Problems with Side Observations." International Conference on Machine Learning, 2009. doi:10.1145/1553374.1553524Markdown
[Yu and Mannor. "Piecewise-Stationary Bandit Problems with Side Observations." International Conference on Machine Learning, 2009.](https://mlanthology.org/icml/2009/yu2009icml-piecewise/) doi:10.1145/1553374.1553524BibTeX
@inproceedings{yu2009icml-piecewise,
title = {{Piecewise-Stationary Bandit Problems with Side Observations}},
author = {Yu, Jia Yuan and Mannor, Shie},
booktitle = {International Conference on Machine Learning},
year = {2009},
pages = {1177-1184},
doi = {10.1145/1553374.1553524},
url = {https://mlanthology.org/icml/2009/yu2009icml-piecewise/}
}