Code associated with the NeurIPS19 paper Weighted Linear Bandits in Non-Stationary Environments available here. The article is a joint work with Claire Vernade and Olivier Cappé.
This package implements the D-LinUCB algorithm presented in the paper. This algorithm builds an estimate of the unkwown vector of the linear model based on weighted least-squares rather than least-squares. By doing so, the new estimate is more robust to non-stationarity.
The empirical performance of the algorithm is reported in two simulated experiments. Those experiments can be easily reproduced by cloning the package, and running the Jupyter notebook in the Experiment folder.
This experiment can be found on this notebook. In this experiment, the unknown parameter is jumping at different places on the unit circle as can be seen on the scatter plot. We compare the regret of the different policies that were implemented. When the environment is highly noisy, the detection algorithm dLinUCB created in Learning Contextual Bandits in a Non-stationary Environment fails to detect changepoints but the D-LinUCBand SW-LinUCB policies are more robust to those changes. The red dashed lines correspond to the different breakpoints and the blue dashed line is the average detection time of the breakpoint for the dLinUCBalgorithm.
One of the main advantage of our method compared to changepoint detection is that the algorithm produces an estimate that is also robust to slowly-varying parameters. In this environment even with a low level of noise, it is hard for a detection algorithm to see the changes. In this experiment that can be found in this notebook, the unknown parameter starts at [0,1] and moves continuously counter-clockwise on the unit-circle up to the position [1,0] in 3000 steps. We then have a 3000 steps steady period.
Please cite our paper if you use this code in your work.
@inproceedings{russac:hal-02291460,
TITLE = {{Weighted Linear Bandits for Non-Stationary Environments}},
AUTHOR = {Russac, Yoan and Vernade, Claire and Capp{\'e}, Olivier},
BOOKTITLE = {{NeurIPS 2019 - 33rd Conference on Neural Information Processing Systems}},
ADDRESS = {Vancouver, Canada},
YEAR = {2019},
MONTH = Dec,
PDF = {https://hal.inria.fr/hal-02291460/file/main.pdf},
HAL_ID = {hal-02291460},
HAL_VERSION = {v1},
}
Please contact yoanrussac@ens.fr for any further information.