2
$\begingroup$

I would like to know if UCB1 for multi armed bandit problems is deterministic or stochastic.

I understand that the arm chosen depends on the expected reward and the "width" of the upper bound, which depends on the number of times I have pulled that arm. So my guess is it's deterministic, but I'm not sure.
Also I am supposing my MAB is not dealing with adversarial rewards - is this the key to say it's deterministic?

- edit - I have since found that it should be stochastic, as opposed adversarial. How can I understand this though? Does this mean than adversarial is deterministic? I wouldn't have said so, the only difference is who/what is giving me my rewards, but I have the same knowledge in the two cases, I guess? Could you help clarify?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ Hello, Claire, and welcome to the site! For people who aren't up on their multi-armed bandit technology, it would help if you wrote out the acronyms the first time you used them, although I'm pretty sure that MAB is "Multi-Armed Bandit". $\endgroup$ – jbowman Jan 20 '18 at 17:04
  • $\begingroup$ Thank you! Yes, you are right, will correct right now! Could you help me with my question? I have since found that it should be stochastic, as opposed adversarial. How can I understand this though? Does this mean than adversarial is deterministic? I wouldn't have said so, the only difference is who/what is giving me my rewards, but I have the same knowledge in the two cases, I guess? Could you helo clarify? Thanks! (imma add this to the OP as well) $\endgroup$ – Claire Jan 20 '18 at 17:12
2
$\begingroup$

UCB1 is a deterministic algorithm, as at each decision-making point (play of the bandit) it selects the best alternative by a deterministic rule:

$$ \text{action} = \arg \min_j \bar{x}_j + \sqrt{2\log(t)/n_j}$$

where $t$ is the iteration count, $n_j$ is the number of times we've already chosen action $j$, and $\bar{x}_j$ is the average reward we've seen from choosing action $j$. There is no randomness in the selection of $\text{action}$ given our state of knowledge $(t, n_j, \bar{x}_j)$ at each decision point, hence the designation of "deterministic".

The rewards are random, but that does not make the algorithm itself a stochastic algorithm, although the sample path of actions chosen is random because the results of the bandit play are random.

Adversarial or non-adversarial has nothing to do with it. Decision-making algorithms in adversarial games can be either deterministic or stochastic.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What you said makes complete sense to me. Here's what I found: The one thing we need to have a full definition of the problem is the characterization of the reward: Deterministic (trivial), Stochastic, Adversary. R is an set of unknown distributions. From then on there are 2 main chapters, stochastic MAB and Adversarial MAB. What the slides are saying are not in opposition to what you said right? The slides referring to the rewards, while the question Is UCB1 a deterministic or a stochastic algorithm? refers to how I choose which arm to pull. THANK YOU! PS Shouldn't it be 2log(t)/n_j? $\endgroup$ – Claire Jan 20 '18 at 17:43
  • 1
    $\begingroup$ @Claire A small addition: typically, ties are broken randomly (if the UCB1 equation gives the same score to multiple different arms). At least, in good implementations of the algorithm that's done. That could technically be viewed as making the algorithm nondeterministic... but obviously that's just a technicality, and only applies to rare cases $\endgroup$ – Dennis Soemers Jan 20 '18 at 18:38
  • $\begingroup$ You're right about $n_i$, @Claire, I'll fix that. $\endgroup$ – jbowman Jan 20 '18 at 20:05
  • $\begingroup$ I also hope I'm right about the rest ;) Thank you so much for this discussion, really helped! $\endgroup$ – Claire Jan 20 '18 at 20:35
  • 1
    $\begingroup$ Yes, you are right, the deterministic vs. stochastic part refers to how you choose which arm to pull, not to how the rewards are generated. $\endgroup$ – jbowman Jan 20 '18 at 20:59

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.