8
$\begingroup$

I came across the formula for obtaining the upper confidence bounds on the k-armed bandit problem:

$$c\sqrt{\frac{\text{ln} N_i}{n_i}}$$

where $n_i$ is the amount of samples we have for this particular bandit and $N_i$ is the total amount of samples we have from all bandits. The same algorithm is used in the Monte Carlo Tree Search as well to obtain the upper confidence bound.

I understand very clearly what an upper confidence bound is, but what I don't understand is where this formula comes from. I have tried looking online in several places but could not find a clear explanation of how this formula is derived. Can someone please explain where this formula comes from? Please assume I don't have a great background in statistics.

$\endgroup$
  • $\begingroup$ I personally found banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm to contain a good explanation. It does include some heavy math, but it's possible to get a good understanding even when skipping some of the heavier equations in my opinion. Just read the intuition and some of the more simple equations $\endgroup$ – Dennis Soemers Jan 21 '18 at 14:08
4
$\begingroup$

What you have there is commonly called the exploration term. The upper confidence bound is the empirical mean plus this exploration term.

Let's consider each term separately:

$c$ is a constant which lets the user set the exploration/exploitation trade-off. For theoretical results it is often optimized for the problem at hand (e.g. k-armed bandits with Gaussian priors).

$\sqrt{1/n_i}$ is proportional to the posterior standard deviation after $n_i$ samples of action $i$. Essentially this says that as you pull an arm more often, there is less unknown about the arm.

$\sqrt{ln(N_i)}$ ensures that you don't stop exploring too early. As $N_i$ becomes very large, the sample variances become small enough that we need to compensate to ensure that we never completely stop exploring. Most of the technical math is to show that $\sqrt{ln(N_i)}$ is just enough (but not too much) compensation.

For a more technical description, the paper by Auer et al. is a good starting point.

$\endgroup$
  • $\begingroup$ the link at the end doesn't work for me. $\endgroup$ – chessprogrammer Jan 24 '18 at 0:58
  • $\begingroup$ Should work now, sorry about that $\endgroup$ – combo Jan 25 '18 at 2:54
2
$\begingroup$

It comes from Hoeffding's inequality, which provides an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. See https://en.wikipedia.org/wiki/Hoeffding%27s_inequality for more on Hoeffding's inequality. See the text around equation (3) in the original UCT paper for a detailed discussion relating this to UCB1 in the bandit setting http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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