[mab-wifi] Initial algorithm simulation results

[Björn Smedman]

On Sun, Mar 26, 2017 at 10:07 PM, Björn Smedman <bjorn at openias.org> wrote:
> On Sun, Mar 12, 2017 at 8:35 PM, Toke Høiland-Jørgensen <toke at toke.dk> wrote:
>> Björn Smedman <bjorn at openias.org> writes:
>>> I had a quick look at your pybandits code and the attached graph. Some
>>> quick questions: What are your thoughts regarding
>>> dependencies/covariances between "arms"? Will we be able to estimate
>>> those from the data Thomas is collecting?
>>
>> Yeah, hopefully Thomas' data set will allow us to build some assumptions
>> on relations between arms (and check those put forward in prior work). I
>> have also been meaning to go digging for similar WiFi measurement
>> studies in the literature; surely there is bound to be something that
>> evaluates the same kinds of things we are interested in? Are you aware
>> of any?
>
> No I'm not. And a quick google search (for "802.11 conditional
> probability of packet loss") turns up very little. I guess this is
> unfortunate on the one hand, and an opportunity on the other. :P

I was researching something called Mixture of Multivariate Bernoulli
(MMB) models the other day and came across an interesting paper titled
"M&M: Multi-level Markov Model for Wireless Link Simulations" [1].
They model a wireless link (in their case 802.15.4) using Hidden
Markov Models (HMM) for longer term variability, and MMBs for the
short-term variability / uncertainty.

I'm not sure it's discussed in the paper, but one very interesting
aspect of MMBs is that they can model correlation between "arms", and
they allow very efficient computation of conditional distributions
(i.e. answering questions like "if MCS-13 just failed, twice, what is
the probability that MCS-15 will succeed?").

One interesting thought that pops up in this context is that Minstrel
actually fits quite beautifully into an MMB framework. As I understand
Minstrel:

1. For every time slot (of 100 ms or so) we estimate a multivariate
Bernoulli distribution (i.e. the packet success probability) over the
different "arms".

2. We assume that the distribution over the next time slot will be an
"exponentially weighted average" of those estimated over previous time
slots.

3. For (most) transmissions in the next time slot we "pull the arm"
with the highest expected payoff, based on the "weighted average"
distribution computed in 2 above.

Seen in an MMB light I guess the main problems with Minstrel are then
more "implementation issues": (a) the "weighted average" of a number
of multivariate Bernoulli distributions (as computed in 2 above) is
not a multivariate Bernoulli distribution itself, it's an MMB(!); and
(b) when deciding which "arm to pull next" the question is not which
arm had the highest expected payoff when the time slot started, it's
what arm has the highest expected payoff given the result of all the
pulling we've been doing so far in the time slot(!). Adding Bayesian
uncertainty and Thompson sampling to that should not be too hard...

Cheers,

Björn

1. http://andes.ucmerced.edu/papers/Kamthe09b.pdf