Technical Note—On Adaptivity in Nonstationary Stochastic Optimization with Bandit Feedback

Yining Wang ()
Additional contact information
Yining Wang: Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080

Operations Research, 2025, vol. 73, issue 2, 819-828

Abstract: In this paper, we study the nonstationary stochastic optimization problem with bandit feedback and dynamic regret measures. The seminal work of Besbes et al. (2015) shows that, when aggregated function changes are known a priori, a simple restarting algorithm attains the optimal dynamic regret. In this work, we design a stochastic optimization algorithm with fixed step sizes, which, combined with the multiscale sampling framework in existing research, achieves the optimal dynamic regret in nonstationary stochastic optimization without prior knowledge of function changing budget, thereby closing a question that has been open for a while. We also establish an additional result showing that any algorithm achieving good regret against stationary benchmarks with high probability could be automatically converted to an algorithm that achieves good regret against dynamic benchmarks (for problems that admit O ˜ ( T ) regret against stationary benchmarks in fully adversarial settings, a dynamic regret of O ˜ ( V T 1 / 3 T 2 / 3 ) is expected), which is potentially applicable to a wide class of bandit convex optimization and other types of bandit algorithms.

Keywords: Stochastic; Models; bandit optimization; nonstationarity; regret analysis (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0576 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:819-828

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().