Bayesian Bandits at LinkedIn

In a reinvigorated effort to look into more detail at the implementation of Bayesian Bandits, today I came across a paper from last fall (2013) by some folks at LinkedIn: Automatic Ad Format Selection via Contextual Bandits by L Tang, R. Rosales, A Singh, and D. Agarwal. Tang is a Ph.D. student at Florida International, and the others are in the Applied Relevance Science group at LinkedIn.

Bayesian Bandits - Just the Beginning of the Story

Earlier this year, I put together an online Bayesian Bandit explorer as part of learning how these things work. These are used in lots of different areas, but one in particular is for selecting ads for display on a web page. Really, this would be applicable in any scenario where there will be lots of potential chances for putting something in front of someone, and you can measure the success or not of this placement.

What I have not done yet is look more deeply into exactly how this would actually be applied. I will being to scratch the surface on that here (as I understand it).

Musings on the Bound for Expected Regret for Thompson Sampling

I came across a talk at TechTalks.tv by Emilie Kaufman on Bayesian Bandits, and she mentioned the current upper bound on the expected regret for Thompson sampling, which I had not looked at in detail yet.  It was derived by Shipra Agrawal and Navin Goyal at Microsoft in this 2012 paper - see Theorem 2.  This bound is O(#ln(pulls)), but the bound is also inversely related to the difference between each sub-optimal bandit's probability of success and that of the optimal bandit.  This makes intuitive sense, and jives with what you see happen when the algorithm runs: when the optimal bandit is much better than the others, the algorithm converges very fast.  If some of the bandits have a probability of success close to that of the optimal bandit, it takes longer to converge, as it will try the (slightly) suboptimal bandits more frequently for a longer period, and hence regret increases.