Comment by isoprophlex

One trick I used myself in a bayesian bandit-esque approach (thompson sampling from some distribution, eg. a Beta distribution) was to implement some "forgetting rate" on the parameters of the distribution.