0
$\begingroup$

Consider two 2-arms bandits:

  1. average reward first arm is 2 euro, second arm 4 euro
  2. average reward first arm is 200 cents, second arm 400 cents

From my perspective, the bandits are exactly the same. However, UCB formula would give different results, because it uses absolute values instead of their proportions. Why? Have I missed some normalization step?

As a reminder, here is the formula (found, for example, here: https://www.cs.princeton.edu/courses/archive/fall16/cos402/lectures/402-lec22.pdf):

$A_t = argmax_a(Q_t(a) + sqrt(2 * ln(t) / N_a(t)))$

$\endgroup$
0
$\begingroup$

The reason this is the case is because UCB implicitly assumes that the rewards are scaled to lie in $[0,1]$ (or alternatively, the rewards are drawn from 1-subgaussian distribution). This guarantees that the variance of the random variables are bounded; otherwise, you need the length of your confidence interval to scale with the standard deviation of the random variables. See for reference Chapter 7 of http://downloads.tor-lattimore.com/banditbook/book.pdf.

| 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.