Answers.Body: <p>Epsilon greedy is unaffected by scaling of rewards, it always selects a random action with a probability of epsilon.</p>
  <p>On the other hand, if we look at the formulation of UCB (Section 2.7 of Reinforcement Learning, Sutton and Barto):</p>
  <p><span class="math-container">$$A_t \doteq  \underset{a}{\operatorname{argmax}} [\mathcal{Q}_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}}]$$</span></p>
  <p>Where <span class="math-container">$Q_t(a)= \frac{R_1 + R_2 + \dots + R_{n-1}}{n-1}$</span> is the average of rewards seen so far for that action. By scaling the rewards, for example by 1/10, you are essentially scaling <span class="math-container">$Q_t(a)$</span> by 1/10 which will change UCBs behaviour to favour the exploratory right hand term <span class="math-container">$c\sqrt{\frac{\ln t}{N_t(a)}}$</span>. If you want to offset your scaling of the rewards you should scale c by the same amount. Theoretically, I believe this should result in performance the same as that achieved pre-scaling.</p>
  <p>In fact, another way of looking at it is that when using UCB, you could dispense with the <span class="math-container">$c$</span> constant altogether and simply scale the rewards to tune the exploitation/exploration trade-off. Smaller rewards favour exploration, larger rewards favour exploitation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-26T14:24:57.717Z
Answers.Text: I double checked what I believe to be the original paper [P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem]. The UCB1 discussed in this paper and the one presented in Sutton and Barto seem to be essentially the same to me, unless I am missing something.
Answers.UserDisplayName: James
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-26T14:29:39.787Z
Answers.Text: I see, yes, in the original paper they provide guarantees for c = sqrt(2). The reasoning behind why performance is different with scaled rewards remains the same though. The fact that OP referred to scaling c leads me to think they might be using the Sutton and Barto formulation.
Answers.UserDisplayName: James
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-27T12:29:15.490Z
Answers.Text: @James in fact, in my task the reward is a ratio between the users that respond to the effect associated with triggering arm a_n and the total number of users. Then, there is no constant scaling factor for the reward, it varies depending on the situation. Is UCB1 designed to work only with binary rewards and is not suitable for continuous rewards in range [0,1]? I do not think so, as the LinUCB was using click-through-rate as a reward which is also variable and non-binary
Answers.UserDisplayName: d56
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-27T12:45:38.687Z
Answers.Text: @d56 UCB can work with continuous or discrete rewards. If scaling rewards doesn't seem appropriate you should tune the c hyper-parameter of UCB. If the current behaviour is to explorative lower the value of c, if it is to exploitive raise the value of c.
Answers.UserDisplayName: James
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-27T12:51:44.593Z
Answers.Text: yes, so, I do not actually know the distribution of the rewards except that they are non-binary. So, I suppose, as you have noted, that tuning the c hyper-parameter is the only choice. That makes things somewhat more complicated of course...
Answers.UserDisplayName: d56
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-26T13:45:59.473Z
Answers.LastActivityDate: 2021-04-26T13:55:55.123Z
Answers.LastEditDate: 2021-04-26T13:55:55.123Z
Answers.UserDisplayName: James
Body: <p>I notice the following behavior when running experiments with <span class="math-container">$\epsilon$</span>-greedy and UCB1. If the reward is kept binary (0 or 1) both algorithm's performances are on par with each other. However, if I make the reward continuous (and bounded [0, 1]) then <span class="math-container">$\epsilon$</span>-greedy remains good but UCB1 performance plummets. As an experiment, I just scaled the reward of 1 by a factor of 1/10 which negatively influences the performance.</p>
  <p>I have plotted the reward values estimated by the algorithms and see that (due to the confidence interval term) UCB1 largely overestimates the rewards.</p>
  <p>Is there a practical trick to fix that? My guess is that the scaling coefficient <span class="math-container">$c$</span> in front of the upper confidence bound is meant just for this case. Nevertheless, the difference in performance is staggering to me. How do I know when and what scaling coefficient will be appropriate?</p>
  <p>===</p>
  <p><strong>update 1</strong> The reward distribution is very simple. There are 17 arms, for arm 3 and 4 the learning algorithm gets a reward of 1, the other arms return reward of 0. No stochasticity, the algorithm has 1000 iterations.</p>
  <p>If I scale the reward by a factor 1/10, for instance, then UCB1 takes a whole lot of time to start catching up with <span class="math-container">$\epsilon$</span>-greedy</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-23T16:23:01.580Z
Comments.Text: Can you specify the continuous reward distribution? Not very clear what you mean by "common value".
Comments.UserDisplayName: Kostya
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-23T16:38:40.310Z
Comments.Text: Extended the description
Comments.UserDisplayName: d56
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-24T09:10:31.230Z
Comments.Text: UCB1 is known to scale poorly with the number of arms. If you have the true expected rewards to be close (I.e. 0 vs 0.1) then it will take UCB1 longer with a lot of arms than it would with a two rewards that are more different (I.e. 0 and 1).
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-26T08:55:27.950Z
Comments.Text: @DavidIreland as far as I remember in the LinUCB paper they had quite a lot of arms (articles to recommend). Maybe it worked as they had so much data too?
Comments.UserDisplayName: d56
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-26T09:44:14.890Z
Comments.Text: hmm, I am not familiar with LinUCB so it may well be that there are new methods available that can scale well with arms. I am only really familiar UCB1 and it has been a _long_ time since I looked at it, hence why I can't answer your question.
Comments.UserDisplayName: David
Tags: <reinforcement-learning><rewards><multi-armed-bandits><upper-confidence-bound>
Title: Difference in UCB performance when scaling the rewards
UserDisplayName: d56
ThreadText: # Difference in UCB performance when scaling the rewards
  
  (Asked by: username_0 on 2021-04-23)
  
  I notice the following behavior when running experiments with $\epsilon$-greedy and UCB1. If the reward is kept binary (0 or 1) both algorithm's performances are on par with each other. However, if I make the reward continuous (and bounded [0, 1]) then $\epsilon$-greedy remains good but UCB1 performance plummets. As an experiment, I just scaled the reward of 1 by a factor of 1/10 which negatively influences the performance.
  
  I have plotted the reward values estimated by the algorithms and see that (due to the confidence interval term) UCB1 largely overestimates the rewards.
  
  Is there a practical trick to fix that? My guess is that the scaling coefficient $c$ in front of the upper confidence bound is meant just for this case. Nevertheless, the difference in performance is staggering to me. How do I know when and what scaling coefficient will be appropriate?
  
  ===
  
  **update 1** The reward distribution is very simple. There are 17 arms, for arm 3 and 4 the learning algorithm gets a reward of 1, the other arms return reward of 0. No stochasticity, the algorithm has 1000 iterations.
  
  If I scale the reward by a factor 1/10, for instance, then UCB1 takes a whole lot of time to start catching up with $\epsilon$-greedy
  
  **Tags:** reinforcement-learning, rewards, multi-armed-bandits, upper-confidence-bound
  
  > **Comments:**
  > **username_1**: Can you specify the continuous reward distribution? Not very clear what you mean by "common value".  
  > **username_0**: Extended the description  
  > **username_2**: UCB1 is known to scale poorly with the number of arms. If you have the true expected rewards to be close (I.e. 0 vs 0.1) then it will take UCB1 longer with a lot of arms than it would with a two rewards that are more different (I.e. 0 and 1).  
  > **username_0**: @DavidIreland as far as I remember in the LinUCB paper they had quite a lot of arms (articles to recommend). Maybe it worked as they had so much data too?  
  > **username_2**: hmm, I am not familiar with LinUCB so it may well be that there are new methods available that can scale well with arms. I am only really familiar UCB1 and it has been a _long_ time since I looked at it, hence why I can't answer your question.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2021-04-26. Score: 1
  
  Epsilon greedy is unaffected by scaling of rewards, it always selects a random action with a probability of epsilon.
  
  On the other hand, if we look at the formulation of UCB (Section 2.7 of Reinforcement Learning, Sutton and Barto):
  
  $$A\_t \doteq \underset{a}{\operatorname{argmax}} [\mathcal{Q}\_t(a) + c \sqrt{\frac{\ln t}{N\_t(a)}}]$$
  
  Where $Q\_t(a)= \frac{R\_1 + R\_2 + \dots + R\_{n-1}}{n-1}$ is the average of rewards seen so far for that action. By scaling the rewards, for example by 1/10, you are essentially scaling $Q\_t(a)$ by 1/10 which will change UCBs behaviour to favour the exploratory right hand term $c\sqrt{\frac{\ln t}{N\_t(a)}}$. If you want to offset your scaling of the rewards you should scale c by the same amount. Theoretically, I believe this should result in performance the same as that achieved pre-scaling.
  
  In fact, another way of looking at it is that when using UCB, you could dispense with the $c$ constant altogether and simply scale the rewards to tune the exploitation/exploration trade-off. Smaller rewards favour exploration, larger rewards favour exploitation.
  
  > **Comments:**
  > **username_3**: I double checked what I believe to be the original paper [P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem]. The UCB1 discussed in this paper and the one presented in Sutton and Barto seem to be essentially the same to me, unless I am missing something.  
  > **username_3**: I see, yes, in the original paper they provide guarantees for c = sqrt(2). The reasoning behind why performance is different with scaled rewards remains the same though. The fact that OP referred to scaling c leads me to think they might be using the Sutton and Barto formulation.  
  > **username_0**: @username_3 in fact, in my task the reward is a ratio between the users that respond to the effect associated with triggering arm a_n and the total number of users. Then, there is no constant scaling factor for the reward, it varies depending on the situation. Is UCB1 designed to work only with binary rewards and is not suitable for continuous rewards in range [0,1]? I do not think so, as the LinUCB was using click-through-rate as a reward which is also variable and non-binary  
  > **username_3**: @username_0 UCB can work with continuous or discrete rewards. If scaling rewards doesn't seem appropriate you should tune the c hyper-parameter of UCB. If the current behaviour is to explorative lower the value of c, if it is to exploitive raise the value of c.  
  > **username_0**: yes, so, I do not actually know the distribution of the rewards except that they are non-binary. So, I suppose, as you have noted, that tuning the c hyper-parameter is the only choice. That makes things somewhat more complicated of course...  
  
  ---
  
  