Answers.Body: <p>In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. <span class="math-container">$c$</span> decides whether they indeed would, and <span class="math-container">$c=\sqrt{2}$</span> is the minimum choice of <span class="math-container">$c$</span>.</p>
  <p>We want to show that the number of runs for non-optimal machines (<span class="math-container">$n_i$</span>, for non-optimal <span class="math-container">$i$</span>s, in your notation) is asymptotically logarithmic. In other words, you may run them for a few times and well, it's fine, but not too often. We're devising some indicator value <span class="math-container">$a_i(t)=\hat \mu_i+(\epsilon...)$</span> such that the <em>mistaken</em> cases, where values of non-optimal ones surpass values of optimal ones (<span class="math-container">$a^*(t)&lt;a_i(t)$</span>), are minimized.</p>
  <p>Think about the last inequality. We know that <span class="math-container">$\mu^* &gt; \mu_i$</span> (again, optimal and non-optimal ones). Therefore, for that inequality to be true, it seems either the left-hand side should be <em>quite</em> small or the right-hand side should be <em>quite</em> large. But wait, <span class="math-container">$\hat \mu$</span>s are actually some random trials for <span class="math-container">$\mu$</span>, so we cannot claim directly from <span class="math-container">$\mu^* &gt; \mu_i$</span> to <span class="math-container">$\hat{\mu^*} &gt; \hat{\mu_i}$</span>; it might be that we just need more trials.</p>
  <p>The equations (7), (8) and (9) of the paper is the three conditions mentioned in the paragraph above; left-hand side is small, right-hand side is large or the trials are lacking. Well, in fact, as we stated <em>the number of runs ... is <strong>asymptotically</strong> logarithmic</em> at first, the third case can be eliminated(!), assuming that we've run this machine enough.</p>
  <p>For the first and second case, since <span class="math-container">$\hat \mu_i$</span> is the average of some random variable in <span class="math-container">$[0, 1]$</span>, we can use Chernoff–Hoeffding bound (or so called in the paper; stated as <a href="https://en.wikipedia.org/wiki/Hoeffding%27s_inequality" rel="nofollow noreferrer">Hoeffding's inequality</a> in Wikipedia). Now, a good choice of <span class="math-container">$(\epsilon ...)$</span> will guarantee (from Hoeffding's inequality) that the first two cases will occur <em>sufficiently scarcely</em>, or in other words, in the order of <span class="math-container">$t^{-4}$</span>. To achieve this, we need <span class="math-container">$c \ge \sqrt 2$</span>.</p>
  <p>Now back to the third case, the <em>enough</em> number of runs is actually <span class="math-container">$l = \left \lceil 2 c^2 \ln n / (\mu^* - \mu_i)^2\right \rceil$</span>. Thus, you may choose larger <span class="math-container">$c$</span> but receive longer convergence speed in penalty.</p>
  <p>Funnily enough, after all the proofs the authors find <span class="math-container">$c=1/4$</span> to converge well and actually perform substantially better(!!) than <span class="math-container">$c=\sqrt{2}$</span>. It seems they could not prove the bound as we did above.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-24T11:28:23.990Z
Answers.Text: @user9947 the t^{-4} comes from there being a t^{2} multiplying factor outside. Together they become t^{-2} which converges fast enough to converge to a constant. The sum of t^{-1} does not converge for instance.
Answers.UserDisplayName: ijuneja
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-24T11:29:11.630Z
Answers.Text: Sufficiently scarcely is just scarce enough for logarithmic regret expectation to hold.
Answers.UserDisplayName: ijuneja
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-23T19:06:22.403Z
Answers.LastActivityDate: 2020-10-23T19:06:22.403Z
Answers.UserDisplayName: Namnamseo
Body: <p>In the literature, there are at least two action selection strategies associated with the UCB1's action selection strategy/policy. For example, in the paper <a href="https://arxiv.org/pdf/1402.6028.pdf" rel="nofollow noreferrer">Algorithms for the multi-armed bandit problem</a> (2000/2014), at time step <span class="math-container">$t$</span>, an action is selected using the following formula</p>
  <p><span class="math-container">$$
  a^*(t) \doteq \arg \max _{i=1 \ldots k}\left(\hat{\mu}_{i}+\sqrt{\frac{2 \ln t}{n_{i}}}\right) \tag{1}\label{1},
  $$</span>
  where</p>
  <ul>
  <li><span class="math-container">$\hat{\mu}_{i}$</span> is an estimate of the expected return for arm <span class="math-container">$i$</span></li>
  <li><span class="math-container">$n_i$</span> is the number of times the action <span class="math-container">$i$</span> is selected</li>
  <li><span class="math-container">$k$</span> is the number of arms/actions</li>
  </ul>
  <p>On the other hand, <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=57" rel="nofollow noreferrer">Sutton &amp; Barto</a> (2nd edition of the book) provide a slightly different formula (equation 2.10)</p>
  <p><span class="math-container">$$
  a^*(t) \doteq \arg \max _{i=1 \ldots k}\left(\hat{\mu}_{i}+c\sqrt{\frac{\ln t}{n_{i}}}\right) \tag{2}\label{2},
  $$</span>
  where <span class="math-container">$c &gt; 0$</span> is a hyper-parameter that controls the amount of exploration (as explained in the book or <a href="https://ai.stackexchange.com/a/20170/2444">here</a>).</p>
  <p>Why do we have these two formulas? I suppose that both are &quot;upper confidence bounds&quot; (and, in both cases, they are constants, though one is a hyper-parameter), but why (and when) would we use one over the other? They are not equivalent because <span class="math-container">$c$</span> only needs to be greater than <span class="math-container">$0$</span>, i.e. it can be arbitrarily large (although, in the mentioned book, the authors use <span class="math-container">$c=2$</span> in one experiment/figure). If <span class="math-container">$c = \sqrt{2}$</span>, then they are the same.</p>
  <p>The answer to my question can probably be found in <a href="https://homes.di.unimi.it/cesa-bianchi/Pubblicazioni/ml-02.pdf" rel="nofollow noreferrer">the original paper that introduced UCB1</a> (which actually defines the UCB1 as in \ref{1}),  or in a paper that derives the bound, in the sense that the bound probably depends on some probability of error, but I have not fully read it yet, so, if you know the answer, feel free to derive both bounds and relate the two formulas.</p>
  
Tags: <reinforcement-learning><policies><sutton-barto><multi-armed-bandits><upper-confidence-bound>
Title: Why do we have two similar action selection strategies for UCB1?
UserDisplayName: nbro
ThreadText: # Why do we have two similar action selection strategies for UCB1?
  
  (Asked by: username_0 on 2020-10-23)
  
  In the literature, there are at least two action selection strategies associated with the UCB1's action selection strategy/policy. For example, in the paper [Algorithms for the multi-armed bandit problem](https://arxiv.org/pdf/1402.6028.pdf) (2000/2014), at time step $t$, an action is selected using the following formula
  
  $$
  a^\*(t) \doteq \arg \max \_{i=1 \ldots k}\left(\hat{\mu}\_{i}+\sqrt{\frac{2 \ln t}{n\_{i}}}\right) \tag{1}\label{1},
  $$
  where
  
  * $\hat{\mu}\_{i}$ is an estimate of the expected return for arm $i$
  * $n\_i$ is the number of times the action $i$ is selected
  * $k$ is the number of arms/actions
  
  On the other hand, [Sutton & Barto](http://incompleteideas.net/book/RLbook2020.pdf#page=57) (2nd edition of the book) provide a slightly different formula (equation 2.10)
  
  $$
  a^\*(t) \doteq \arg \max \_{i=1 \ldots k}\left(\hat{\mu}\_{i}+c\sqrt{\frac{\ln t}{n\_{i}}}\right) \tag{2}\label{2},
  $$
  where $c > 0$ is a hyper-parameter that controls the amount of exploration (as explained in the book or [here](https://ai.stackexchange.com/a/20170/2444)).
  
  Why do we have these two formulas? I suppose that both are "upper confidence bounds" (and, in both cases, they are constants, though one is a hyper-parameter), but why (and when) would we use one over the other? They are not equivalent because $c$ only needs to be greater than $0$, i.e. it can be arbitrarily large (although, in the mentioned book, the authors use $c=2$ in one experiment/figure). If $c = \sqrt{2}$, then they are the same.
  
  The answer to my question can probably be found in [the original paper that introduced UCB1](https://homes.di.unimi.it/cesa-bianchi/Pubblicazioni/ml-02.pdf) (which actually defines the UCB1 as in \ref{1}), or in a paper that derives the bound, in the sense that the bound probably depends on some probability of error, but I have not fully read it yet, so, if you know the answer, feel free to derive both bounds and relate the two formulas.
  
  **Tags:** reinforcement-learning, policies, sutton-barto, multi-armed-bandits, upper-confidence-bound
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-10-23. Score: 2
  
  In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. $c$ decides whether they indeed would, and $c=\sqrt{2}$ is the minimum choice of $c$.
  
  We want to show that the number of runs for non-optimal machines ($n\_i$, for non-optimal $i$s, in your notation) is asymptotically logarithmic. In other words, you may run them for a few times and well, it's fine, but not too often. We're devising some indicator value $a\_i(t)=\hat \mu\_i+(\epsilon...)$ such that the *mistaken* cases, where values of non-optimal ones surpass values of optimal ones ($a^\*(t)<a\_i(t)$), are minimized.
  
  Think about the last inequality. We know that $\mu^\* > \mu\_i$ (again, optimal and non-optimal ones). Therefore, for that inequality to be true, it seems either the left-hand side should be *quite* small or the right-hand side should be *quite* large. But wait, $\hat \mu$s are actually some random trials for $\mu$, so we cannot claim directly from $\mu^\* > \mu\_i$ to $\hat{\mu^\*} > \hat{\mu\_i}$; it might be that we just need more trials.
  
  The equations (7), (8) and (9) of the paper is the three conditions mentioned in the paragraph above; left-hand side is small, right-hand side is large or the trials are lacking. Well, in fact, as we stated *the number of runs ... is **asymptotically** logarithmic* at first, the third case can be eliminated(!), assuming that we've run this machine enough.
  
  For the first and second case, since $\hat \mu\_i$ is the average of some random variable in $[0, 1]$, we can use Chernoff–Hoeffding bound (or so called in the paper; stated as [Hoeffding's inequality](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality) in Wikipedia). Now, a good choice of $(\epsilon ...)$ will guarantee (from Hoeffding's inequality) that the first two cases will occur *sufficiently scarcely*, or in other words, in the order of $t^{-4}$. To achieve this, we need $c \ge \sqrt 2$.
  
  Now back to the third case, the *enough* number of runs is actually $l = \left \lceil 2 c^2 \ln n / (\mu^\* - \mu\_i)^2\right \rceil$. Thus, you may choose larger $c$ but receive longer convergence speed in penalty.
  
  Funnily enough, after all the proofs the authors find $c=1/4$ to converge well and actually perform substantially better(!!) than $c=\sqrt{2}$. It seems they could not prove the bound as we did above.
  
  > **Comments:**
  > **username_2**: @user9947 the t^{-4} comes from there being a t^{2} multiplying factor outside. Together they become t^{-2} which converges fast enough to converge to a constant. The sum of t^{-1} does not converge for instance.  
  > **username_2**: Sufficiently scarcely is just scarce enough for logarithmic regret expectation to hold.  
  
  ---
  
  