4
$\begingroup$

Consider a simplified version of the multi-armed bandit problem, where:

  • like in the standard multi-armed bandit: when you pull the lever of 1 bandit you win/lose some amount from that bandit

  • differently from the standard version: after you have pulled the lever of your choice, every other bandit reveals what you would have won/lost, had you pulled its lever instead (but now it's too late 🙂).

So let's play:

  • at round #1 you don't know anything, you choose random, say bandit A, and incur in some real profit/loss form bandit A

  • at round #2 you have 1 data point about each bandit from the previous round, that could help you decide slightly better than random

  • at round #3 you have two data points about each bandit to rely on, and so forth...

What is the optimal strategy to maximise cumulative returns after N rounds?

$\endgroup$
8
  • $\begingroup$ How exactly would you "get to know what you would have won/lost"? $\endgroup$
    – Tim
    Commented May 27, 2020 at 8:41
  • $\begingroup$ thanks @Tim - Once you pull the lever of say bandit #5, you incur into a real profit/loss from bandit #5. At the same time the other slot machines display the message "had pulled my lever, you would have incurred in such profit/loss this time". Sorry, the bandit may be a bad analogy. I could repost the question as "choosing 1 out of N envelopes, and then all envelopers are open, to reveal some profit/loss" - did I provide the clarification you asked? $\endgroup$
    – elemolotiv
    Commented May 27, 2020 at 9:14
  • $\begingroup$ But how would you know the outcome if you didn't pull the lever? If you knew it before, you didn't need to do anything about exploration. If you have an all-knowing oracle, then there is no problem to solve in here, you just exploi the best option. You cannot have cake and eat cake. E.g. if you are testing online ads, then you don't know how someone would respond to the ads, so you test it. You can only show one add at a time, so you cannot check all of them. $\endgroup$
    – Tim
    Commented May 27, 2020 at 9:18
  • 1
    $\begingroup$ Probably worth including the information in last comment into the body of your question. $\endgroup$
    – Tim
    Commented May 27, 2020 at 9:47
  • 1
    $\begingroup$ Yes I understand, it was just an example to see if I got the settings of the problems, thank you. I see it's a problem of online learning. $\endgroup$
    – Ale
    Commented May 27, 2020 at 10:08

1 Answer 1

3
$\begingroup$

As discussed in the comments, this is not exactly a multi-armed bandit problem. In multi-armed bandit you know the rewards only after you "pull the arm" of your slot machine. For example, if you are running online ad campaign and you want to test between different ads, then you can only one add to user at a time and you don't know the rewards that you would get if showing different ads. This is why there is the exploration/exploitation trade-off: you can either explore "what would happen" by picking different arms, or exploit the one arm that is known to work best. Everything comes here at some cost and multi-armed bandit problem aims at suggesting the most optimal actions to balance those factors.

In your case, you have zero knowledge only before the first round, so first move can be done at random. After first move, you know all the rewards, so you can update the data on all arms simultaneously. Next, and the following steps, is to pick the arm that is currently known to give best rewards. You do not need the exploration step (i.e. randomizing the choices) since you have equal knowledge on all arms. The more steps you make, the better decisions you can make since you have more knowledge. You still can use something like randomized strategies to choose between arms, but all the further considerations is standard decision theory.

As a quick recap of decision theory, for each arm, you can expect some reward $r$ and we can define a preference, or utility, $U(r)$ of such reward, that defines your preferences over such rewards (e.g. utility of money is known to be non-linear). If two arms have different probability distributions $P_1$ and $P_2$ for the rewards, then the general approach would be to prefer to play the arm that gives us the greatest expected utility, e.g. when

$$ E_{P_1}[U(r)] < E_{P_2}[U(r)] $$

then $P_2$ is preferred to $P_1$. Why do we care about expected value? This is nicely answered in the Why is the expected value named so? thread, in fact the whole idea of expected value emerged from gambling. You don't know $P_1$ and $P_2$, so you need to estimate expected value from the data, and you can use arithmetic mean for that.

Regarding your comments, it is true that with small samples your estimates of mean would be imprecise, but estimates of variance would be imprecise as well, and dividing one by another does not fix this. Moreover, you have equally imprecise information for all arms, since you saw the same number of samples for each. With the arm that has big variance, you could expect the the possible rewards to vary a lot, so they could be either very small, or very large. Your correction by dividing by variance seems to be a kind of hack to implement some sort of risk aversion in your utility function. This could, or could not, make sense in your particular application, but keep in mind, that this is your choice of what you consider as "acceptable". In standard multi-armed bandit problem, we randomize the choices to explore the space of possible rewards better, here you don't have this problem since you have equal knowledge on all arms, so it's pure exploitation.

$\endgroup$
7
  • $\begingroup$ thank you again @tim re your point: "Next, and the following steps, is to pick the arm that is currently known to give best rewards." this is not necessarily the best strategy, because the mean estimation error is heavily dependent on variance. For example, when I run simulations, choosing the bandit with the highest historical average profit yields worse cumulative return than choosing the bandit with the highest historical μ/σ ratio. But these are empirical results, I am looking for the general theory... $\endgroup$
    – elemolotiv
    Commented May 27, 2020 at 12:16
  • $\begingroup$ @elemolotiv assuming equal rewards? Could you share the simulation code? $\endgroup$
    – Tim
    Commented May 27, 2020 at 15:45
  • $\begingroup$ in my simulation I have 1000 bandits each with its own distribution of profits $N[μ_i, σ_i^2]$ so yes, I assume different reward mean and dev for each bandit. The challenge is to single out the best bandit out of 1000 bandits as you collect data. The simulation code is 1000 lines in C - not sure it is so edible 😅 But I will repost this problem in a more structured way, explaining the simulation and the results. I am grateful that you are helping me polish the question! $\endgroup$
    – elemolotiv
    Commented May 27, 2020 at 16:14
  • $\begingroup$ @elemolotiv so negative rewards are possible? $\endgroup$
    – Tim
    Commented May 27, 2020 at 16:22
  • 1
    $\begingroup$ @elemolotiv I may be missing something, but I can't see it. By curiosity, I've run a simple simulation, where there are $k$ arms, with normally distributed rewards, and the choice of arm is by choosing arm with greatest cumul rewards and this seems to work, moreover it does work better then mean/sd criteria. $\endgroup$
    – Tim
    Commented May 28, 2020 at 8:11

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.