14
$\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 number 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.

Improve this question
$\endgroup$
1
  • $\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, 2018 at 14:08

2 Answers 2

Reset to default
7
$\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.

Auer, Peter, Nicolo Cesa-Bianchi, and Paul Fischer. "Finite-time analysis of the multiarmed bandit problem." Machine learning 47.2-3 (2002): 235-256.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Please add a full citation to the article. This will help users locate the resource even if the hyperlink breaks. $\endgroup$
    – Sycorax ♦
    Oct 23, 2020 at 16:48
5
$\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

Improve this answer
$\endgroup$

Your Answer

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

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