Body: <p>My question concerns <strong>Stochastic Combinatorial Multiarmed Bandits</strong>. More specifically, the algorithm called <em><strong>CombUCB1</strong></em> presented in <a href="http://proceedings.mlr.press/v38/kveton15.html" rel="nofollow noreferrer">this</a> paper. It is a UCB-like algorithm.</p>
  <p>Essentially, in each round of the sequential game the learner chooses a super-arm to play. A super-arm is a <span class="math-container">$d$</span>-dimensional vector <span class="math-container">$a \in \mathcal{A}$</span> where <span class="math-container">$\mathcal{A} \subset \{0,1\}^d$</span>. In each super-arm <span class="math-container">$a$</span>, when the <span class="math-container">$i$</span>-element equals to <span class="math-container">$1$</span> ( <span class="math-container">$i \in \{0, \dots, d\}, a(i)=1$</span> ), that means that the basic action <span class="math-container">$i$</span> is active. Basically, in each round the learner plays the basic actions that are active in the chosen super-arm. The rewards of the basic actions are stochastics and a super-arm receives as a reward the sum of the rewards of the basic active actions.</p>
  <p>The algorithm mentioned above presents a UCB-like algorithm, where with each basic action is associated a UCB-index and in each round the learner plays the super-arm that maximises that index.
  My question concerns the confidence interval around the mean of the rewards of the basic actions, presented in equation <span class="math-container">$2$</span> of the <a href="http://proceedings.mlr.press/v38/kveton15.html" rel="nofollow noreferrer">mentioned</a> paper. Here, the exploration bonus is</p>
  <p><span class="math-container">$c_{t,s} = \sqrt{\frac{1.5 \log t}{s}}$</span></p>
  <p>I don't understand where that <span class="math-container">$1.5$</span> is coming from.
  I've always known that one needs to use Chernoff-Hoeffding inequality to derive the exploration bonus in a UCB-algorithm. Am I wrong and it needs to be computed in other ways? I've always seen the same coefficient but with <span class="math-container">$2$</span> instead of <span class="math-container">$1.5$</span> (<a href="https://link.springer.com/article/10.1023/A:1013689704352" rel="nofollow noreferrer">reference</a>).
  Could someone explain me where does <span class="math-container">$1.5$</span> come from, please?</p>
  <p>I know there is a similar question <a href="https://ai.stackexchange.com/questions/24221/why-do-we-have-two-similar-action-selection-strategies-for-ucb1?rq=1">here</a>, but I cannot really understand how that works here.</p>
  <p>Thank you in advance in case you have time to read and answer my questions.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-05T09:28:17.467Z
Comments.Text: Do you mean the $6$ from eq. 6 and $48$ from Theorem 2 in (Kveton et al., 2015)? So, you're saying that if I substitute those constants with variables $k_1, k_2, k_3$ and optimise, I should be able to get back to that 1.5. Have I understood correctly? Thank you for your answer, I really appreciate it!
Comments.UserDisplayName: Adam
Tags: <multi-armed-bandits><online-learning><upper-confidence-bound>
Title: UCB-like algorithms: how do you compute the exploration bonus?
UserDisplayName: Adam
ThreadText: # UCB-like algorithms: how do you compute the exploration bonus?
  
  (Asked by: username_0 on 2021-02-04)
  
  My question concerns **Stochastic Combinatorial Multiarmed Bandits**. More specifically, the algorithm called ***CombUCB1*** presented in [this](http://proceedings.mlr.press/v38/kveton15.html) paper. It is a UCB-like algorithm.
  
  Essentially, in each round of the sequential game the learner chooses a super-arm to play. A super-arm is a $d$-dimensional vector $a \in \mathcal{A}$ where $\mathcal{A} \subset \{0,1\}^d$. In each super-arm $a$, when the $i$-element equals to $1$ ( $i \in \{0, \dots, d\}, a(i)=1$ ), that means that the basic action $i$ is active. Basically, in each round the learner plays the basic actions that are active in the chosen super-arm. The rewards of the basic actions are stochastics and a super-arm receives as a reward the sum of the rewards of the basic active actions.
  
  The algorithm mentioned above presents a UCB-like algorithm, where with each basic action is associated a UCB-index and in each round the learner plays the super-arm that maximises that index.
  My question concerns the confidence interval around the mean of the rewards of the basic actions, presented in equation $2$ of the [mentioned](http://proceedings.mlr.press/v38/kveton15.html) paper. Here, the exploration bonus is
  
  $c\_{t,s} = \sqrt{\frac{1.5 \log t}{s}}$
  
  I don't understand where that $1.5$ is coming from.
  I've always known that one needs to use Chernoff-Hoeffding inequality to derive the exploration bonus in a UCB-algorithm. Am I wrong and it needs to be computed in other ways? I've always seen the same coefficient but with $2$ instead of $1.5$ ([reference](https://link.springer.com/article/10.1023/A:1013689704352)).
  Could someone explain me where does $1.5$ come from, please?
  
  I know there is a similar question [here](https://ai.stackexchange.com/questions/24221/why-do-we-have-two-similar-action-selection-strategies-for-ucb1?rq=1), but I cannot really understand how that works here.
  
  Thank you in advance in case you have time to read and answer my questions.
  
  **Tags:** multi-armed-bandits, online-learning, upper-confidence-bound
  > **Comments:**
  > **username_0**: Do you mean the $6$ from eq. 6 and $48$ from Theorem 2 in (Kveton et al., 2015)? So, you're saying that if I substitute those constants with variables $k_1, k_2, k_3$ and optimise, I should be able to get back to that 1.5. Have I understood correctly? Thank you for your answer, I really appreciate it!  
  
  ---
  
  ## 0 answers
  
  