Abstract
We study the linear stochastic bandit problem, relaxing the standard i.i.d.assumption on the observation noise. As an alternative to this restrictiveassumption, we allow the noise terms across rounds to be sub-Gaussian butinterdependent, with dependencies that decay over time. To address thissetting, we develop new confidence sequences using a recently introducedreduction scheme to sequential probability assignment, and use these to derivea bandit algorithm based on the principle of optimism in the face ofuncertainty. We provide regret bounds for the resulting algorithm, expressed interms of the decay rate of the strength of dependence between observations.Among other results, we show that our bounds recover the standard rates up to afactor of the mixing time for geometrically mixing observation noise.