Answers.Body: <p>The upper bound used here is derived from <a href="https://en.wikipedia.org/wiki/Hoeffding%27s_inequality" rel="nofollow noreferrer">Hoeffding's inequality</a>, which provides a symmetric, two-sided confidence interval. A good pair of blog posts on how this bound used in UCB for bandits is derived can be found here:</p>
  <ol>
  <li><a href="https://banditalgs.com/2016/09/14/first-steps-explore-then-commit/" rel="nofollow noreferrer">First steps: Explore-then-Commit</a></li>
  <li><a href="https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/" rel="nofollow noreferrer">The Upper Confidence Bound Algorithm</a></li>
  </ol>
  <p>Indeed, in practice when using this UCB for bandits, we do not actually care about the lower bound. We only need the upper found for the exploration mechanism. But the lower bound does still exist, even if we don't use it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T18:52:12.247Z
Answers.LastActivityDate: 2021-01-31T18:52:12.247Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I'm a bit confused about the visualization of the upper bound (following the notation of (c.f. <a href="https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf" rel="nofollow noreferrer">Sutton &amp; Barto (2018)</a>)</p>
  <p><span class="math-container">$$Q_t(a)+C\sqrt{\frac{\mathrm{ln}(t)}{N_t(a)}}$$</span></p>
  <p>In many blog posts about the UCB(1)-algorithm, such as visualized in the following image (c.f. <a href="https://www.geeksforgeeks.org/upper-confidence-bound-algorithm-in-reinforcement-learning/" rel="nofollow noreferrer">Link</a> ):</p>
  <p><img src="https://media.geeksforgeeks.org/wp-content/uploads/20200126022459/Screenshot-2020-01-26-at-2.24.37-AM.png" alt="Text" /></p>
  <p>Isn't the upper (confidence) bound simply the upper bound of a <strong>one-sided confidence interval</strong> instead of a <strong>two-sided confidence interval</strong> as shown in the image above?
  A lower bound of the interval is completely useless in this case, or am I wrong?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-19T21:08:38.153Z
Comments.Text: As far as I am aware it is for a two sided confidence interval. I only have a brief knowledge of MAB's so I don't want to write an official answer but I am fairly certain a paper I read on them a few years ago also proved a lower bound (I guess for completeness) because you are right in saying that a lower bound would be useless for a MAB.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-19T21:39:26.490Z
Comments.Text: In the MAB domain, it is possible to specify a lower as well as an upper bound for the regret of an algorithm. Probably you mix it up with that?
Comments.UserDisplayName: D. B.
Tags: <machine-learning><reinforcement-learning><multi-armed-bandits><upper-confidence-bound>
Title: In UCB, is the actual upper bound an upper bound of an one-sided or two-sided confidence interval?
UserDisplayName: D. B.
ThreadText: # In UCB, is the actual upper bound an upper bound of an one-sided or two-sided confidence interval?
  
  (Asked by: username_0 on 2021-01-19)
  
  I'm a bit confused about the visualization of the upper bound (following the notation of (c.f. [Sutton & Barto (2018)](https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf))
  
  $$Q\_t(a)+C\sqrt{\frac{\mathrm{ln}(t)}{N\_t(a)}}$$
  
  In many blog posts about the UCB(1)-algorithm, such as visualized in the following image (c.f. [Link](https://www.geeksforgeeks.org/upper-confidence-bound-algorithm-in-reinforcement-learning/) ):
  
  ![Text](https://media.geeksforgeeks.org/wp-content/uploads/20200126022459/Screenshot-2020-01-26-at-2.24.37-AM.png)
  
  Isn't the upper (confidence) bound simply the upper bound of a **one-sided confidence interval** instead of a **two-sided confidence interval** as shown in the image above?
  A lower bound of the interval is completely useless in this case, or am I wrong?
  
  **Tags:** machine-learning, reinforcement-learning, multi-armed-bandits, upper-confidence-bound
  
  > **Comments:**
  > **username_1**: As far as I am aware it is for a two sided confidence interval. I only have a brief knowledge of MAB's so I don't want to write an official answer but I am fairly certain a paper I read on them a few years ago also proved a lower bound (I guess for completeness) because you are right in saying that a lower bound would be useless for a MAB.  
  > **username_0**: In the MAB domain, it is possible to specify a lower as well as an upper bound for the regret of an algorithm. Probably you mix it up with that?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-01-31. Score: 1
  
  The upper bound used here is derived from [Hoeffding's inequality](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality), which provides a symmetric, two-sided confidence interval. A good pair of blog posts on how this bound used in UCB for bandits is derived can be found here:
  
  1. [First steps: Explore-then-Commit](https://banditalgs.com/2016/09/14/first-steps-explore-then-commit/)
  2. [The Upper Confidence Bound Algorithm](https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/)
  
  Indeed, in practice when using this UCB for bandits, we do not actually care about the lower bound. We only need the upper found for the exploration mechanism. But the lower bound does still exist, even if we don't use it.
  
  
  ---
  
  