4
$\begingroup$

I know that the multi-armed bandit can be formalised in multiple ways - two of them being the stochastic and adversarial ways. I am familiar with the fact that adversarial way is a game theoretic approach to this problem. In the book Regret Analysis of Stochastic and Non-stochastic Multi-armed Bandit Problems the author says that the adversarial way is non-stochastic. I believe that non-stochastic means deterministic. But, isn't it true that a game can involve randomness in it? - For example, the adversary/opponent can have some randomness in him.......etc

So, I am confused by that statement by the author and would be happy if someone could explain why a game-theoretic approach of the Multi Armed Bandit Problem is a non-stochastic approach.

Thanks in advance.

$\endgroup$

1 Answer 1

3
$\begingroup$

The adversarial setting isn't deterministic in the sense that randomness is not allowed, but rather in the sense that the stochasticity assumption that the rewards are generated from a fixed distribution is dropped. The important part of the adversarial setting is not that we are making a deterministic assumption, but rather that we are not making any assumptions about the generation of the rewards. It's possible the adversary is behaving stochastically, and we are allowed to behave stochastically as well (in fact, you typically have to).

In some cases the oblivious adversary assumption is made, where it's assumed all rewards are determined before the interaction begins. Obviously in this case the rewards can be considered deterministic.

$\endgroup$
6
  • $\begingroup$ So, are you telling me that 'random' and 'stochastic' are two different things mathematically? With 'stochastic' referring to the fact that we are assuming the scenario to have an underlying distribution. If yes, this notion seem a little less intuitive for me. I have always thought that any real life situation has an underlying distribution always. I would be happy if you can elaborate more on this. Thank you! PS: In the second paragraph, even in the oblivious adversary case, we can have an adversary that draws the reward for each arm from a fixed distribution - then isnt it stochastic? $\endgroup$ Commented Dec 19, 2018 at 20:26
  • $\begingroup$ No, random and stochastic are synonymous. The important distinction here is what assumptions are made rather than what's actually happening. In the adversarial case, we are not saying the adversary has to behave deterministically. We are just saying that we won't assume anything about the mechanism that generates the rewards. It's possible the oblivious adversary drew each reward i.i.d. from a fixed distribution for each arm. But it's also possible that they didn't. We don't assume anything about that reward generating mechanism, it's allowed to be anything, which is a harder problem to solve. $\endgroup$ Commented Dec 19, 2018 at 21:07
  • $\begingroup$ I need one more clarification. If what you say is true, how can one define the expectation of the regret? Because, for expectation we need a probability function right and a probability function will mean that there is a distribution assumed. How does one reconcile with this notion? $\endgroup$ Commented Dec 24, 2018 at 8:52
  • 1
    $\begingroup$ I was able to answer it myself - thanks!. Refer to this book's chapter on Adversarial bandits $\endgroup$ Commented Dec 24, 2018 at 10:37
  • $\begingroup$ @braceletboy broken link. Do you remember the title? $\endgroup$
    – Daniel
    Commented Feb 9, 2022 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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