Multi Armed Bandit Augmented With Machine Learning Priors

Question

Suppose we have a list of items $I_1,\cdots,I_K$, and we would like to order them by popularity using a Multi Armed Bandit approach. As a concrete example, imagine we're trying to advertise a toy on the internet and each $I_k$ is an image of the toy, so that we're trying to figure out which image has the highest click-thru rate. Since the click-thru rate is extremely low for all such advertisements, it becomes really expensive and long to figure out which image performs best.

Suppose now we have a deep learning model $P$ that predicts imagine popularity (based on prior data). We train this model and are now able to get popularity predictions (i.e. click-thru rate) $P(I_k)$ for each image. The model is far from perfect, but we do end up observing some correlation $C$ between our predictions and the true popularity.

I would like to augment this model with a multi-armed bandit to figure out which image is the most popular. The setup is a list of images $I_k$, along with a list of priors $P(I_k)$, with a correlation coefficient $C$ between the priors and the true popularity.

I'm not an expert in this area, so I was hoping to get some advice on what the exact augmentation procedure should be. As an example, reading this led me to Boltzmann Exploration, which generalizes the epsilon-greedy method to selecting arms based on their empirical means. In this case, we select image $i$ to test on at time $t+1$ based on:

$$p_i(t+1)=\frac{e^{\mu_i(t)/\tau}}{\sum_{i=1}^Ke^{\mu_i(t)/\tau}},$$

where $\mu_i(t)$ are the empirical means observed at time $t$ and $\tau$ is hyperparameter that controls for how uniformly random (or singular) we want the predictions to be. With the above neural network output, the easiest thing I can think of is replacing $\mu_i(t)\rightarrow \mu_i(t)+P(I_i)$. Are there better approaches? I would sincerely appreciate any literature references on this.

Answer 1

I did a little informal research here and it seems that heuristics are all that are left once your reward model leaves the parametric domain. But if you haven't already come across some of Michel Tokic's papers, I'd recommend checking them out. Value-Difference based Exploration: Adaptive Control between epsilon-Greedy and Softmax is pretty good.

The idea behind this Value-Difference based exploration (VDBE) is, if you're going to use a simple heuristic like $\epsilon$-greedy, let $\epsilon$ be proportional to the amount that your reward model is changing. Say $\epsilon$ is .10, leading to get thousands of exploratory data points in a time period, but you refit your reward model and it barely changes. Then according to VDBE you should reduce that learning rate. Tokic has an easy equation for that in Section 2.3, but it does depend on an arbitrary tuning parameter. And unless there's something special about the Boltzmann distribution, it didn't seem theoretically motivated. I'd imagine you could roll your own and it would be just as good.

Rereading your question, it's not so different from what you found. I guess VDBE focuses more on getting a good model than pulling the right arm. I wish you the best in your journey to find the right heuristic.

Answer 2

Typically a multi-armed bandit approach is not supposed to order your images by popularity, but rather to trade off exploration and exploitation to maximize your cumulative rewards.

Your deep learning model gives you a good initial guess for the mean value, and (loosely speaking) the "correlation coefficient" is useful in that it gives you an estimate of the confidence of the model. The next step is to figure out how measurements change your confidence.

I think a reasonable approach would be to use posterior sampling (aka Thompson sampling). In this case, you would set up your network so that you feed in on-line data and it produces estimates of the distribution of the popularity of each image. Then at each iteration you sample from the posterior distribution and select the action with the highest sampled value. If your network is actually able to learn the model, then this approach should work pretty well (and you don't have to try and argue that everything is Gaussian!), and I would argue is a step above 'heuristic'.

I think if you are trying to incorporate $P(I_k)$ into a sample mean based approach, you should initialize $\mu_i(0) = P(I_k)$, and then update as $\mu_i(t+1) \gets (y_i(t) + (t+b_k) \mu_i(t))/(t+1+b_k)$, where a large value of $b_k$ means that you think $P(I_k)$ is close to the true value. This is essentially like saying that you started by measuring $b_k$ values of $P(I_k)$, before starting all of your experiments.