[mab-wifi] Initial algorithm simulation results

[mab-wifi] Initial algorithm simulation results

[Toke Høiland-Jørgensen]

[-- Attachment #1: Type: text/plain, Size: 1695 bytes --]

So I've finally gotten around to trying out the Python bandit algorithm
implementations from
https://www.math.univ-toulouse.fr/~agarivie/Telecom/bandits/

I have added a very simple WiFi arm implementation to the code base
(which is basically a Bernoulli arm that succeeds with a certain
probability and gives a payoff scaled by the base rate), which can be
instantiated from the rate_stats_csv output from Minstrel in the kernel.

Based on the data from a simple test run in my own testbed I was able to
get three of the algorithms to produce something meaningful; see the
attached graph. The best of the algorithms performs roughly comparable
to Minstrel (I think; the numbers are not quite straight forward to
compare).

I have not been able to get the Thompson and BayesUCB algorithms to work
with this scenario yet (they require a posterior distribution to sample
from, and the included implementation doesn't work with the varying
payoffs of each arm). However, perhaps sticking with the KL-UCB
algorithm is better anyway (same one the "optimal rate sampling"
modifies; haven't quite grokked how they modify it yet).

Anyway, I do believe it is possible to extend this simulation to
something that we can use to guide, say, a dynamic implementation (i.e.,
change the probabilities over the duration of the test run), as well as
evaluating the effects of collapsing arms / defining them differently.
It would probably be good with a better source of the actual
probabilities for each rate, though.

So yeah, bit of a brain dump of where I'm at; but I'll be away for the
next couple of weeks, so though it better to get this out there.

Code here: https://kau.toke.dk/git/pybandits/

-Toke


[-- Attachment #2: initial-wifi.png --]
[-- Type: image/png, Size: 43579 bytes --]

Re: [mab-wifi] Initial algorithm simulation results

[Toke Høiland-Jørgensen]

Björn Smedman <bjorn@openias.org> writes:

> Hi Toke,
>
> It's great to see some practical results! I very much agree that more
> of this is what we need to get going.
>
> 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?

> Any ideas on how we can simulate them?

Well, this is a bit harder. I don't think expanding on the pyBandits
scenario is going to provide any new insights into *how* the arms are
related to each other; we can only encode our assumptions into that
simulation and see how different algorithms are affected by it. But
maybe a full protocol simulation, like that found in ns3, can be more
helpful for exploring these relations. Depends a little bit on the
capabilities of the 802.11 simulation there, I guess; see the separate
thread related to that.

> I have a feeling that estimating/simulating/exploiting these
> dependencies/covariances will be key to achieving something
> significantly better than Minstrel. I think that feeling is rooted in
> an assumption that there are strong dependencies/covariances between
> "arms", combined with my understanding that Minstrel models them as
> independent Bernoulli distributed stochastic variables.

I agree. And yeah, I think you're right that Minstrel basically
considers them independently Bernoulli-distributed. I'm not quite clear
on whether we need to try to collapse rates into fewer arms, or if we
need to handle any relations between arms at the algorithmic level.
Maybe both?

-Toke

Re: [mab-wifi] Initial algorithm simulation results

[Björn Smedman]

On Sun, Mar 26, 2017 at 10:07 PM, Björn Smedman <bjorn@openias.org> wrote:
> On Sun, Mar 12, 2017 at 8:35 PM, Toke Høiland-Jørgensen <toke@toke.dk> wrote:
>> Björn Smedman <bjorn@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