Tracking the Best Expert in Non-stationary Stochastic Environments
By Chen-Yu Wei, Yi-Te Hong, Chi-Jen Lu. 2017
65 citations recorded by the source corpus.
We study the dynamic regret of multi-armed bandit and experts problem in non-stationary stochastic environments. We introduce a new parameter $\Lambda$, which measures the total statistical variance of the loss distributions over $T$ rounds of the process, and study how this amount affects the regret. We investigate the interaction between $\Lambda$ and $\Gamma$, which counts the number of times the distributions change, as well as $\Lambda$ and $V$, which measures how far the distributions deviates over time. One striking result we find is that even when $\Gamma$, $V$, and $\Lambda$ are all restricted to constant, the regret lower bound in the bandit setting still grows with $T$. The other highlight is that in the full-information setting, a constant regret becomes achievable with constant $\Gamma$ and $\Lambda$, as it can be made independent of $T$, while with constant $V$ and $\Lambda$, the regret still has a $T^{1/3}$ dependency. We not only propose algorithms with upper bound guarantee, but prove their matching lower bounds as well.
Subfields: Artificial Intelligence, Computer Networks and Communications, 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
In Computer Networks and Communications
In Management Science and Operations Research
Citations in the corpus
- Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “…is usually termed as shifting regret or tracking regret [Herbster and Warmuth, 1998, Gy¨orgy et al., 2005, Gyorgy et al., 2012, Gy¨orgy and Szepesv´ari, 2016, Mourtada and Maillard, 2017, Adamskiy et al., 2016, Wei et al., 2016, Cesa-Bianchi et al., 2012, Mohri and Yang, 2018, Jun et al., 2017].”
- Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “3 Shifting regret (or tracking regret) The M−shifting regret of an algorithm A ∈ A is defined by [6, 38, 40–47] R̃T := T ∑”
- Competing with Automata-based Expert Sequences (2018, background): “There has also been work deriving guarantees in the bandit setting when the losses are stochastic [Besbes et al., 2014, Wei et al., 2016].”