Re:The Multi-Armed Bandit Problem and Its Solutions (2018)
by Matumio on Tuesday February 05, 2019 @03:56PM
(#19089761)
I agree. I did some research out of curiosity in the past about multi-armed bandits. The optimal solution is quite involved, and not worth the effort of studying in my opinion.
Thompson sampling, on the other hand... I'm in love. Clean, simple, straight-forward, and so close to the optimal solution that you will never notice the difference. If you don't understand how to implement it, the stuff that you need to learn (mostly about the beta distribution) is generally useful and well worth studying. Though, after several years now, I'm still looking for an excuse to apply it somewhere. I can't get this method out of my head.
Re:The Multi-Armed Bandit Problem and Its Solutions (2018)
by joshuamorton on Tuesday February 05, 2019 @07:19PM
(#19091479)
I'm a bit confused, as far as I know, Thompson Sampling is optimal (insofar as it minimizes regret in expectation).
Re:The Multi-Armed Bandit Problem and Its Solutions (2018)
by wolfgangK on Wednesday February 06, 2019 @10:30AM
(#19095842)
> Thompson sampling itself is not difficult (specifically, 6 lines, as I'm looking at my Clojure code),
Going through "A tutorial on Thompson Sampling" and being eager to hone my skills in Clojure, I would be very interested in reading this code if there would be a repository online or a gist you could share with us.
Best Regards.
Thompson sampling is easy to implement, predictable, stable, and you can leave your experiments running forever without supervision. It has very few drawbacks.
With a combination of two HyperLogLogs and a Bloom filter, you can also have a really nice scalable distributed implementation (HLLs and BFs combine in an idempotent manner, so updates are lock-free), albeit at the cost of low precision early on as the number of samples is low.
Don't use a library. Thompson sampling itself is not difficult (specifically, 6 lines, as I'm looking at my Clojure code), you will need to understand it very well anyway, and most libraries will include lots of superfluous garbage. Most of the work is not with Thompson sampling, but with processing your events, and that is something which is application-specific anyway and can't be abstracted well.