Non-Stochastic Bandits with Evolving Observations
Abstract
We introduce a novel online learning framework that unifies and generalizes pre-established models, such as delayed and corrupted feedback, to encompass adversarial environments where action feedback evolves over time. In this setting, the observed loss is arbitrary and may not correlate with the true loss incurred, with each round updating previous observations adversarially. We propose regret minimization algorithms for both the full-information and bandit settings, with regret bounds quantified by the average feedback accuracy relative to the true loss. Our algorithms match the known regret bounds across many special cases, while also introducing previously unknown bounds.
Cite
Text
Bar-On and Mansour. "Non-Stochastic Bandits with Evolving Observations." Proceedings of The 36th International Conference on Algorithmic Learning Theory, 2025.Markdown
[Bar-On and Mansour. "Non-Stochastic Bandits with Evolving Observations." Proceedings of The 36th International Conference on Algorithmic Learning Theory, 2025.](https://mlanthology.org/alt/2025/baron2025alt-nonstochastic/)BibTeX
@inproceedings{baron2025alt-nonstochastic,
title = {{Non-Stochastic Bandits with Evolving Observations}},
author = {Bar-On, Yogev and Mansour, Yishay},
booktitle = {Proceedings of The 36th International Conference on Algorithmic Learning Theory},
year = {2025},
pages = {204-227},
volume = {272},
url = {https://mlanthology.org/alt/2025/baron2025alt-nonstochastic/}
}