Skip to content

Code associated with the NeurIPS19 paper "Weighted Linear Bandits in Non-Stationary Environments"

License

Notifications You must be signed in to change notification settings

YRussac/WeightedLinearBandits

Repository files navigation

WeightedLinearBandits

Description

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.

Experiments

Abruptly changing environment

Plots

Comments

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.

Slowly-varying environment

Plots

Comments

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.

Citation

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},
}

Contact

Please contact yoanrussac@ens.fr for any further information.

About

Code associated with the NeurIPS19 paper "Weighted Linear Bandits in Non-Stationary Environments"

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published