Implement algorithms from "Multiplayer bandits without observing collision information" arXiv:1808.08416

[Naereen]

This recent article probably called ["Multiplayer bandits without observing collision information", by Gabor Lugosi and Abbas Mehrabian] is really interesting. They quote our work on bandit learning for IoT network, and for multi-player bandit.

• I should read it carefully,
• And implement in SMPyBandits their algorithms,
• To do my own comparison against RandTopM and MCTopM, and Selfish,
• And check and verify their claims. (or disprove them?),
• I need to contact them, AS SOON AS POSSIBLE, to show that I implemented all this and read and love their work, to thank them (and initiate a nice contact/collaboration?).

[Naereen]

A few remarks:

• I don't have (and won't write) support for leaving players (§3 of Th.2.1)
• At first, let's ignore the part about other distributions (§4.2) and estimating the number of players (§2 of Th.2.1)
• So I just have to write the Algorithm1 in page 8. (almost almost done!)

[Naereen]

Yeah, as expected all this work is extremely nice from a theoretical point of view, but quite inpractical for real.

Just have a look at the examples of computation of estimated length of uniform exploration phases (1 and 2):

>>> estimate_length_phases_12(m=2, K=2, Delta=0.1, T=100)
198214307
>>> estimate_length_phases_12(m=2, K=2, Delta=0.01, T=100)
19821430723
>>> estimate_length_phases_12(m=2, K=2, Delta=0.1, T=1000)
271897030
>>> estimate_length_phases_12(m=2, K=3, Delta=0.1, T=100)
307052623
>>> estimate_length_phases_12(m=2, K=5, Delta=0.1, T=100)
532187397

That's just unreasonable! Too bad 😢 !

[Naereen]

That's just unreasonable! Too bad cry !

Note that, after discussing with the author, I tried using a much smaller value for g (instead of 128 just 1), and their algorithm is still very much asymptotic. Sadly 😢.

But… 😺 we can surely improve it and make it usable in practice, I have no doubt (just no time right now to do it properly).