I spent two years[0] designing, building and maintaining a system which used contextual multi-armed bandits at large scale. A couple pieces of advice relating to this post and this subject:
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 :)
> 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.
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.
You could use clustering, dimensionality reduce or feature selection.
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).
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.
Yes! I haven't read all of it yet, but from what I've seen so far, the book spends a lot of time rigorously proving mathematical properties/bounds of various bandit algorithms. I love rigor as much as the next guy, but I also like seeing code :)
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 :)