Multi armed bandit algorithms failing with un-scaled rewards

Question

I am experimenting with the multi-armed bandit algorithms (namely: epsilon greedy, decaying epsilon greedy, optimistic initial value, upper confidence interval, and Thompson sampling).

My reward is continuous and so I use a Gaussian distribution for the Thompson sampling (I'm not sure if this specifically can be a problem, but my question below is rather general).

All the examples and tutorials I could find (including this related question here) deal with either binary output (win/lose) or rewards with standard normal distribution.

However, playing with the numbers I noticed that nearly all the algorithms either fail, or become very sensitive to the hyper-parameters (if relevant) when the rewards are fairly high (>50), very low (~0.001) or has large variance.

I read several comments on related issues suggesting scaling the data, but this is sometimes not feasible in practice.

My question then is: is this the limit of these methods, or is there something fundamental that I am missing here?

Thank you very much!

Note: overall, the epsilon algorithms are the most 'resilient' in my experience here.

Answer 1

In some sense, yes, it is a limitation of these methods. That's only because most of these methods were created under the assumption of $[0, 1]$ bounded rewards. You mention the $\epsilon$-greedy family of algorithms as the most resilient in your experience, which makes sense because they do not need any bounded reward assumptions. As fairidox mentions in the post you linked, it can be hard to prove anything about the regret when rewards are unbounded. However, some "practical" solutions exist for this type of situation.

Gaussian Thompson Sampling is okay to use, but see this paper for potential problems. TL;DR: The prior matters a significant amount. You may not get optimal performance depending on your choice of prior.

This paper describes the UCB1-tuned algorithm that also estimates variance. Depending on your situation you may be able to get it to work well.

You can also check out this paper that gives a UCB-style and TS-style algorithm for bandit problems with unknown mean and variance based on the first paper I linked

Another practical solution is to use the trick fairidox mentions in the post you linked. Divide your rewards by some large number $S$ to scale to $[0, 1]$. If you find a reward larger than $S$, assign $S := 2S$. If you do this you can use most standard MAB algorithms out of the box that assume rewards bounded by [0, 1]. Of course you're not necessarily guaranteed the regret bounds of the original algorithm in this case.