2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much for the detailed and thorough reply! I assumed that this was the case, but I am new to machine learning and wanted to get some external support to my intuition.. I will try those ideas and see which one works best for which cases, Thanks again $\endgroup$ – Tacratis Jan 23 '19 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.