Restless dependent bandits with fading memory

Autoren: O Zadorozhnyi, G Blanchard, A Carpentier (2019)

We study the stochastic multi-armed bandit problem in the case when the arm samples are dependent over time and generated from so-called weak $\cC $-mixing processes. We establish a $\cC-$ Mix Improved UCB agorithm and provide both problem-dependent and independent regret analysis in two different scenarios. In the first, so-called fast-mixing scenario, we show that pseudo-regret enjoys the same upper bound (up to a factor) as for iid observations; whereas in the second, slow mixing scenario, we discover a surprising effect, that the regret upper bound is similar to the independent case, with an incremental {\em additive} term which does not depend on the number of arms. The analysis of slow mixing scenario is supported with a minmax lower bound, which (up to a factor log(T)) matches the obtained upper bound.


zur Übersicht der Publikationen