2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Can you specify the continuous reward distribution? Not very clear what you mean by "common value". $\endgroup$
    – Kostya
    Apr 23 at 16:23
  • $\begingroup$ Extended the description $\endgroup$
    – d56
    Apr 23 at 16:38
  • $\begingroup$ 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). $\endgroup$ Apr 24 at 9:10
  • $\begingroup$ @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? $\endgroup$
    – d56
    Apr 26 at 8:55
  • $\begingroup$ 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. $\endgroup$ Apr 26 at 9:44
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I think the UCB OP is talking about is a more formal one whose error bounds can be determined. S&B uses an informal version of UCB. $\endgroup$
    – user9947
    Apr 26 at 14:17
  • $\begingroup$ 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. $\endgroup$
    – James
    Apr 26 at 14:24
  • $\begingroup$ I mean there are fundamental gurantees for UCB1, In UCB1, c=2 I think, for a very specific reason. But I don't exactly know what OP wants so only OP can clarify. $\endgroup$
    – user9947
    Apr 26 at 14:26
  • $\begingroup$ 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. $\endgroup$
    – James
    Apr 26 at 14:29
  • $\begingroup$ @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 $\endgroup$
    – d56
    Apr 27 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.