6
$\begingroup$

There is plenty of reading out there about Bayesian (beta-binomial) multiarm bandits for 0/1 data, but I would like to extend this slightly.

To give some context, suppose I have two webpages, A and B. Now I want to test which webpage gets more people to call in, so I begin by randomly serving A, B to incoming visitors.

This is equivalent to starting with the same beta priors on A, B - either $\text{prior}_A = \text{prior}_B = \mathrm{Beta}(0,0)$ aka uninformed or some $\mathrm{Beta}(k_1, k_2)$ for both.

As the binary data comes in (either people call or they don't), I update according to Bayes' Rule and so I end up with $\text{posterior}_A = \mathrm{Beta}(k_1 + \text{wins}_A, k_2 + \text{trials}_A - \text{wins}_A)$ and similarly for B.

Here a trial is me serving the visitor a webpage and a success is a call, to be clear.

My Question

What is the continuous analogue of this binary data model? That is, if my data coming in is now of the form $0.5, 1.6, 8.95$ etc., what can I use to optimize which is better A or B? I have looked into Gaussian processes a little bit but I'm not sure this is what I want. Thanks for any help.

An extension to this question may be found here.

$\endgroup$
3
  • $\begingroup$ Can you tell us more about these numbers? Can they be negative? Zero? Even better, what do they represent? Call duration? Session duration? $\endgroup$ Mar 19, 2015 at 3:33
  • $\begingroup$ @jlimahaverford they can be negative or zero or positive. They represent the profit of a given visit: call duration is factored in as well as how much it cost me to get someone to click on my web page $\endgroup$
    – Moderat
    Mar 19, 2015 at 14:21
  • $\begingroup$ I have extended this question here stats.stackexchange.com/questions/168718/… - editing the question was rejected, thus the duplicate $\endgroup$ Aug 25, 2015 at 15:11

2 Answers 2

4
+50
$\begingroup$

Disclosure: I know almost nothing about bandits. Still, my suggestion seems like a natuaral generalization of the case you presented. It does not consider the experimental design step in detail (since I don't know what people ususally consider as a loss function in this scenario), so might fail in this respect.

Let me ignore the fact that we have two web pages. You have a web page and your prior for "profit per call" (denoted $\theta$) is (say) Gaussian- $p(\theta) = (2\pi)^{-\frac{1}{2}} \exp( -\frac{\theta^2}{2})$. Lets also say that you believe that if you know the average profit per view, your gains are distributed according to another normal $X \sim \mathcal{N}(\theta, 1)$. Then you have a valid (and very simple) bayesian model.

Now, use the same model for both web pages. After observing $n$ (potential) clients' reactions, you have the distributions for the posterior of $A$ and $B$ which are both Gaussian. Based on whatever target you choose for the experimental design step, you can choose which web page to present next. Calculating and differentiating the target should not be too hard, since we know how to integrate Gaussians.

$\endgroup$
10
  • 1
    $\begingroup$ Thanks for your answer. Here are some questions to consider: what would be a good prior for the gaussian distribution? how to update the prior with the data seen (conjugated prior)? for example in binomial case, the beta is also the conjugated prior for the beta-distribution. how to estimate the mean and the variance, given the data? what does gaussian process mean and how is this term related to your answer? how to avoid randomness, let's say the first three data point give a reward of 1000 to arm 1, how to assure that exploration will still occur? $\endgroup$ Aug 24, 2015 at 15:01
  • $\begingroup$ Prior - I used a guassian prior for the Gaussian. If we know the variance (assumed 1 in both prior and likelihood) then the Gaussian is its own conjugate prior - one only needs to complete the squares. I did not use any Gaussian process, just prior and likelihood. I can think of a few ways to avoid randomness (e.g. choose other page every once in a while regardless of what is best or using some Information theory criterion) but if you do believe the bayesian model, then randomness is sub optimal. Please let me know if you want me to write an extended answer. $\endgroup$
    – Yair Daon
    Aug 24, 2015 at 15:21
  • $\begingroup$ I appreciate your answer, my first approach was quiet similiar. A simulation of this approach has shown several weaknesses. For example, consider a reward for the first arm of 10, 15, 20, 15 which results in a mean of 15 and a variance of ~16.6667 and for the second arm 50, 150, 10, 10 having a mean of 55 and a variance of ~4336.7 - now although obviously the second bandit got much higher reward, if you sample from these two gaussian distributions the first arm is explored "too often", the two bells overlap too much. There must be something 'better' in terms of regret bounds out there :-) $\endgroup$ Aug 24, 2015 at 16:08
  • $\begingroup$ Why do you say the first arm is explored too often? If the variance is high it means you can't predict the result well, so you'd like to keep exploring. $\endgroup$
    – Yair Daon
    Aug 24, 2015 at 16:36
  • 2
    $\begingroup$ This answer is consistent to the answer in stats.stackexchange.com/questions/168718/… by Neil G. and accepted for the bounty. $\endgroup$ Aug 26, 2015 at 15:23
3
$\begingroup$

This problem is tackled by the Dearden paper on Bayesian Q-Learning. He considers a normal model for "returns" (future rewards) like @yair's solution. He also considers another term called the "value of information": "the expected improvement in future decision quality that might arise from the information acquired by exploration."

Also, FYI Beta(0, 0) is not "uninformative". The Jeffreys prior is Beta(0.5, 0.5).

Dearden, Richard, Nir Friedman, and Stuart Russell. "Bayesian Q-learning." AAAI/IAAI. 1998.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.