Answers.Body: <p>Here is an intuitive description/explanation.</p>
  <p><span class="math-container">$c$</span> is there for a trade-off between exploration and exploitation. If <span class="math-container">$c=0$</span> then you only consider <span class="math-container">$Q_t(a)$</span> (no exploration). If <span class="math-container">$c \rightarrow \infty$</span> then you only consider exploration term.<br />
  <span class="math-container">$\frac{\ln t}{N_t(a)}$</span> is there to balance out exploration term. If you consider a simple case where you only have one action (then it wouldn't make sense to explore you could always pick that action but let's pretend there is) then as <span class="math-container">$t \rightarrow \infty$</span>, because <span class="math-container">$\ln t$</span> has sublinear growth,
  <span class="math-container">\begin{equation}
  \frac{\ln t}{N_t} \rightarrow 0
  \end{equation}</span>
  So, after you picked an action infinitely many times, the exploration term will completely diminish, i.e. you already know a lot about what that action does. If you picked a numerator that doesn't have sublinear growth, then as <span class="math-container">$t \rightarrow \infty$</span> exploration term would not diminish, so you would always have a chance to explore and exploration term can &quot;overpower&quot; action value term if <span class="math-container">$Q_t$</span> is very small, even after you picked an action infinitely many times, which is not desired.</p>
  <p>A similar thing is with multiple actions, <span class="math-container">$\ln t$</span> will make sure the exploration term <span class="math-container">$\rightarrow 0$</span> if you picked it many times, but it's still better than constant term <span class="math-container">$K/N_t(a)$</span>, where <span class="math-container">$K$</span> is some constant, because it can diminish too fast.</p>
  <p>With <span class="math-container">$\ln t$</span> you will also not stop exploring completely if you haven't picked some action in a long time, because <span class="math-container">$\ln t$</span> will keep growing and <span class="math-container">$N_t(a)$</span> will remain the same, so their fraction will increase with time, which is useful in non-stationary environments.</p>
  <p>The <em>square root</em> is also there probably to balance out the magnitude of exploration term.</p>
  <p>You can also see this <a href="https://stats.stackexchange.com/questions/323867/upper-confidence-bound-in-machine-learning">answer</a>. It has couple of links to some papers for a more mathematical description.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-11T09:15:20.457Z
Answers.LastActivityDate: 2020-10-23T10:08:39.370Z
Answers.LastEditDate: 2020-10-23T10:08:39.370Z
Answers.UserDisplayName: Brale
Body: <p>I came across the formula for Upper Confidence Bound Action Selection (while studying multi-armed bandit problem), which looks like:</p>
  
  <p><span class="math-container">$$
  A_t \dot{=} \operatorname{argmax}_a \left[ Q_t(a) + c \sqrt{ \frac{\ln t}{N_t(a)} } \right]
  $$</span></p>
  
  <p>Although, I understand what the second term in the summation actually means but I am not able to figure out how and from where the exact expression came from, what is the log doing there? What effect does <span class="math-container">$c$</span> have? And, why a square root?</p>
  
Tags: <reinforcement-learning><multi-armed-bandits><upper-confidence-bound>
Title: How do we reach at the formula for UCB action-selection in multi-armed bandit problem?
UserDisplayName: SAGALPREET SINGH
ThreadText: # How do we reach at the formula for UCB action-selection in multi-armed bandit problem?
  
  (Asked by: username_0 on 2020-04-11)
  
  I came across the formula for Upper Confidence Bound Action Selection (while studying multi-armed bandit problem), which looks like:
  
  $$
  A\_t \dot{=} \operatorname{argmax}\_a \left[ Q\_t(a) + c \sqrt{ \frac{\ln t}{N\_t(a)} } \right]
  $$
  
  Although, I understand what the second term in the summation actually means but I am not able to figure out how and from where the exact expression came from, what is the log doing there? What effect does $c$ have? And, why a square root?
  
  **Tags:** reinforcement-learning, multi-armed-bandits, upper-confidence-bound
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-11. Score: 3 | Accepted answer
  
  Here is an intuitive description/explanation.
  
  $c$ is there for a trade-off between exploration and exploitation. If $c=0$ then you only consider $Q\_t(a)$ (no exploration). If $c \rightarrow \infty$ then you only consider exploration term.  
  $\frac{\ln t}{N\_t(a)}$ is there to balance out exploration term. If you consider a simple case where you only have one action (then it wouldn't make sense to explore you could always pick that action but let's pretend there is) then as $t \rightarrow \infty$, because $\ln t$ has sublinear growth,
  \begin{equation}
  \frac{\ln t}{N\_t} \rightarrow 0
  \end{equation}
  So, after you picked an action infinitely many times, the exploration term will completely diminish, i.e. you already know a lot about what that action does. If you picked a numerator that doesn't have sublinear growth, then as $t \rightarrow \infty$ exploration term would not diminish, so you would always have a chance to explore and exploration term can "overpower" action value term if $Q\_t$ is very small, even after you picked an action infinitely many times, which is not desired.
  
  A similar thing is with multiple actions, $\ln t$ will make sure the exploration term $\rightarrow 0$ if you picked it many times, but it's still better than constant term $K/N\_t(a)$, where $K$ is some constant, because it can diminish too fast.
  
  With $\ln t$ you will also not stop exploring completely if you haven't picked some action in a long time, because $\ln t$ will keep growing and $N\_t(a)$ will remain the same, so their fraction will increase with time, which is useful in non-stationary environments.
  
  The *square root* is also there probably to balance out the magnitude of exploration term.
  
  You can also see this [answer](https://stats.stackexchange.com/questions/323867/upper-confidence-bound-in-machine-learning). It has couple of links to some papers for a more mathematical description.
  
  
  ---
  
  