Multi-Armed Bandits, Conjugate Models and Bayesian Reinforcement Learning
eigenfoo.xyz
eigenfoo.xyz
1. Thompson sampling is great. It's intuitive and computationally tractable. The literature is full of other strategies, specifically semi-uniform strategies, but I strongly recommend using Thompson sampling if it works for your problem.
2. This is broadly true about ML, but for contextual bandits, most of the engineering work will probably be the feature engineering, not algorithm implementation. Plan accordingly. Choosing the right inputs in the first place makes a big difference. The hashing trick (a la sklearn's dictvectorizer) can make a huge difference.
3. It can be difficult to obtain organizational alignment on the intention of using reinforcement learning. Tell stakeholders early and often that you're using bandit algos to produce some kind of outcome — say, clicks or conversions — and not to do science which will uncover deep truths.
[0] along with an excellent data scientist and a team of excellent engineers, of course :)
Spot on. For more information about the advantages of Thompson sampling over other approaches, see Why is Posterior Sampling Better than Optimism for Reinforcement Learning? [1] by Osband and Van Roy.
[1] http://proceedings.mlr.press/v70/osband17a/osband17a.pdf
I'm not a huge fan of that. Hash collisions can lead to unexpected behaviors in production and make feature attribution for debugging harder.
It's slightly more effort to implement, but with a trie data structure you can store even the biggest feature mapping in memory.
However, the way I have seen the hashing trick being used is not to compress the feature space. For most problems it would be a bad idea to just lump your most discriminative features together with some other random ones. Instead people just choose a very large feature space which makes collisions unlikely. For model implementations using sparse matrices it doesn't matter if the feature space is very large. The main advantage of this is that you don't have to keep an expensive hash map of your vocabulary in memory (hence my suggestion to use a trie).
Great tutorial on Thompson sampling.
I implemented something like this for my company and found the latter article quite helpful in explaining the concept to people who understood the basics of probability but not programming.