Partition Tree Weighting for Non-Stationary Stochastic Bandits
It addresses the challenge of adapting universal source coding to interactive settings like bandit problems, which is incremental as it extends an existing technique to a new domain.
The paper tackles the problem of constructing a universal coding distribution for interactive data streams with actions and observations, addressing the self-delusion issue, and presents an efficient algorithm for non-stationary stochastic Bernoulli bandits that generalizes Partition Tree Weighting from passive prediction to control.
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 \emph{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.