On Slowly-varying Non-stationary Bandits
We consider minimisation of dynamic regret in non-stationary bandits with a slowly varying property. Namely, we assume that arms' rewards are stochastic and independent over time, but that the absolute difference between the expected rewards of any arm at any two consecutive time-steps is at most a drift limit $\delta > 0$. For this setting that has not received enough attention in the past, we give a new algorithm which extends naturally the well-known Successive Elimination algorithm to the non-stationary bandit setting. We establish the first instance-dependent regret upper bound for slowly varying non-stationary bandits. The analysis in turn relies on a novel characterization of the instance as a detectable gap profile that depends on the expected arm reward differences. We also provide the first minimax regret lower bound for this problem, enabling us to show that our algorithm is essentially minimax optimal. Also, this lower bound we obtain matches that of the more general total variation-budgeted bandits problem, establishing that the seemingly easier former problem is at least as hard as the more general latter problem in the minimax sense. We complement our theoretical results with experimental illustrations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Regret bound for Non-stationary Multi-Armed Bandits with Fairness Constraints
The multi-armed bandits' framework is the most common platform to study strategies for sequential decision-making problems. Recently, the notion of fairness has attracted a lot of attention in the machine learning commun…
Decision MakingFairnessMulti-Armed BanditsSequential Decision MakingCausal Inference from Slowly Varying Nonstationary Processes
Causal inference from observational data following the restricted structural causal model (SCM) framework hinges largely on the asymmetry between cause and effect from the data generating mechanisms, such as non-Gaussian…
Causal DiscoveryCausal IdentificationCausal InferenceTime Series+1Causal Inference from Slowly Varying Nonstationary Processes
Causal inference from observational data following the restricted structural causal models (SCM) framework hinges largely on the asymmetry between cause and effect from the data generating mechanisms, such as non-Gaussia…
Causal IdentificationCausal InferenceTime SeriesWeighted Linear Bandits for Non-Stationary Environments
We consider a stochastic linear bandit model in which the available actions correspond to arbitrary context vectors whose associated rewards follow a non-stationary linear regression model. In this setting, the unknown r…
regressionOn Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems
We study the non-stationary stochastic multiarmed bandit (MAB) problem and propose two generic algorithms, namely, the limited memory deterministic sequencing of exploration and exploitation (LM-DSEE) and the Sliding-Win…