2
$\begingroup$

UCB uses a padding function such as $$c_t(i)=B\sqrt{\xi \log(t) / N_t(i)},$$ where $B$ is an upper-bound on the reward.

This description comes from reference 2 (also see reference 3). But I have seen it described it as such elsewhere.

I see many people using $B=1$.

My question is, what is $B$ exactly? An upper-bound on the reward distribution? But too often, the reward distribution does not have an upper bound, it follows a Gaussian say. I am new to the literature, so I must be missing something...

References:

  1. The original paper: Sample Mean Based Index Policies with O(log n) Regret for the Multi-Armed Bandit, by Rajeev Agrawal
  2. On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems (see page 3), by Aurélien Garivier and Eric Moulines
  3. A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit, by Giuseppe Burtini, Jason Loeppky, Ramon Lawrence
$\endgroup$
  • $\begingroup$ I believe it's an upper bound on the expected reward, so if you have $k$ arms and a collection of reward distributions over time $\mu_t(k)$, $B = \max\mu_t(k)$. Could be wrong, though. $\endgroup$ – jbowman Feb 27 '18 at 18:26
  • $\begingroup$ Based on the discussion in the paper just before the Algorithm 1 block, I think it's an upper bound on the random variables. A lot of the early bandit work focused on variables in [0,1], which is consistent with the OP saying he sees "B=1" often. $\endgroup$ – combo Mar 3 '18 at 0:00
1
$\begingroup$

The term "UCB" stands for "Upper confidence bound", because the algorithm optimistically selects arms which might be very good. The term $B\sqrt{\xi}$ controls what precisely this means. From your reference 2 (page 3):

$B$ is an upper bound on your rewards and $\xi$ is an appropriate constant

We don't need to limit the analysis to finite rewards - in fact your reference 1 considers Gaussian and Poisson models (see section 5). Typically the constants fall out of the regret analysis and are chosen to minimize the expected regret. Sebastian Bubeck gives a very good review on UCB algorithms which describes this in the context of subgaussian rewards.

| cite | improve this answer | |
$\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.