# Partition Tree Weighting for Non-Stationary Stochastic Bandits

arXiv: https://arxiv.org/abs/2502.19325 · HTML: https://mlsanity.com/paper/2502.19325/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 26 Feb 2025.

## Builds on (most cited first, 8 of 8)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Shaking the foundations: delusions in sequence models for interaction and control](https://mlsanity.com/paper/2110.10819/) (2021)
- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [Thompson Sampling is Asymptotically Optimal in General Environments](https://mlsanity.com/paper/1602.07905/) (2016)
- [Generalized Thompson Sampling for Sequential Decision-Making and Causal Inference](https://mlsanity.com/paper/1303.4431/) (2013)

## Abstract (arXiv)

This paper considers a generalisation of universal source coding for interaction data, namely data streams that have actions interleaved with observations. Our goal will be to construct a coding distribution that is both universal and can be used as a control policy. Allowing for action generation needs careful treatment, as naive approaches which do not distinguish between actions and observations run into the self-delusion problem in universal settings. We showcase our perspective in the context of the challenging non-stationary stochastic Bernoulli bandit problem. Our main contribution is an efficient and high performing algorithm for this problem that generalises the Partition Tree Weighting universal source coding technique for passive prediction to the control setting.