30
$\begingroup$

The most well-known bandit algorithm is upper confidence bound (UCB) which popularized this class of algorithms. Since then I presume there are now better algorithms. What is the current best algorithm (in terms of either empirical performance or theoretical bounds)? Is this algorithm optimal in some sense?

$\endgroup$
25
$\begingroup$

A paper from NIPS 2011 ("An empirical evaluation of Thompson Sampling") shows, in experiments, that Thompson Sampling beats UCB. UCB is based on choosing the lever that promises the highest reward under optimistic assumptions (i.e. the variance of your estimate of the expected reward is high, therefore you pull levers that you don't know that well). Instead, Thompson Sampling is fully Bayesian: it generates a bandit configuration (i.e. a vector of expected rewards) from a posterior distribution, and then acts as if this was the true configuration (i.e. it pulls the lever with the highest expected reward).

The Bayesian Control Rule ("A Minimum Relative Entropy Principle for Learning and Acting", JAIR), a generalization of Thompson Sampling, derives Thompson Sampling from information-theoretic principles and causality. In particular, it is shown that the Bayesian Control Rule is the optimum strategy when you want to minimize the KL between your strategy and the (unknown) optimum strategy and if you take into account causal constraints. The reason why this is important is because this can be viewed as an extension of Bayesian inference to actions: Bayesian inference can be shown to be the optimal prediction strategy when your performance criterion is the KL between your estimator and the (unknown) true distribution.

| cite | improve this answer | |
$\endgroup$
17
$\begingroup$

UCB is indeed near optimal in the stochastic case (up to a log T factor for a T round game), and up to a gap in Pinsker's inequality in a more problem dependent sense. Recent paper of Audibert and Bubeck removes this log dependence in the worst case, but has a worse bound in the favorable case when different arms have well-separated rewards.

In general, UCB is one candidate from a larger family of algorithms. At any point in the game, you can look at all arms that are not "disqualified", that is, whose upper confidence bound is not smaller than the lower confidence bound of some arm. Picking based on any distribution of such qualified arms constitutes a valid strategy and gets a similar regret up to constants.

Empirically, I do not think there has been a significant evaluation of many different strategies, but I think UCB is often quite good.

Most of the more recent research has focused on extending bandit problems beyond the simple K-armed setting with stochastic rewards, to very large (or infinite) action spaces, with or without side information, and under stochastic or adversarial feedback. There has also been work in scenarios where the performance criteria are different (such as the identification of best arm only).

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

The current state of the art could be summed up like this:

  • stochastic: UCB and variants (regret in $R_T = O(\frac{K \log T}{\Delta})$)
  • adversarial: EXP3 and variants (regret in $\tilde{R}_T = O(\sqrt{T K \log K})$)
  • contextual: it's complicated

with $T$ is the number of rounds, $K$ the number of arms, $\Delta$ the true difference between the best and second best arm (gap).

| cite | improve this answer | |
$\endgroup$

Your Answer

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