From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from rs224.mailgun.us (rs224.mailgun.us [209.61.151.224]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 3CDAA3B29E for ; Thu, 20 Apr 2017 18:16:11 -0400 (EDT) DKIM-Signature: a=rsa-sha256; v=1; c=relaxed/relaxed; d=openias.org; q=dns/txt; s=k1; t=1492726570; h=Content-Transfer-Encoding: Content-Type: Cc: To: Subject: Message-ID: Date: From: References: In-Reply-To: MIME-Version: Sender; bh=Po7TAlIk6+PP8Cpi48+7Uswqn+KiMOq1yzc+2x+acE8=; b=ZjIwoNb3C6f0rNJQpQIBdIEnm/D66s2afaJXSiQszLvjeUTee2h5KQNztWMfMpQKvW/YwXwW h55AVLWzilBfNRRxCBfRrdX8rDidW5KX+TUweHaMPiWgE+8tq7yVXeHnq66aonjAd/EAZOt3 eanKT+1LFL2VueTjO8CM8KqH6xE= DomainKey-Signature: a=rsa-sha1; c=nofws; d=openias.org; s=k1; q=dns; h=Sender: MIME-Version: In-Reply-To: References: From: Date: Message-ID: Subject: To: Cc: Content-Type: Content-Transfer-Encoding; b=iViXxjK5he1mOo/BXwuX7y/kFbJGlVntSJPVGmMiSi47fKy40vQ3KW2d0ktUJ1GSvYymLH 1hVpzEP9Kr9FpPvC0DPlL4UFJZEWaz9tZ4TSsxV2KbpnLksYKT8cKcqwGY51j1zYP4e/Ajgv CM+k9rjtTULikdHl+np+CaGSFtqEg= Sender: bjorn@openias.org X-Mailgun-Sending-Ip: 209.61.151.224 X-Mailgun-Sid: WyJkYTEwYiIsICJtYWItd2lmaUBsaXN0cy5idWZmZXJibG9hdC5uZXQiLCAiYWZiYTk5YiJd Received: from mail-oi0-f51.google.com (mail-oi0-f51.google.com [209.85.218.51]) by mxa.mailgun.org with ESMTP id 58f93329.7f908dc4fcf0-smtp-out-n01; Thu, 20 Apr 2017 22:16:09 -0000 (UTC) Received: by mail-oi0-f51.google.com with SMTP id y11so38392508oie.0 for ; Thu, 20 Apr 2017 15:16:09 -0700 (PDT) X-Gm-Message-State: AN3rC/4/BHxtfNaaveUCy0LKvkJcDyltKltwaR/jPg6r4gAWJUNtEL+y 7hZWtk0T8Rd804fyVjq3uNnESMW73w== X-Received: by 10.157.31.74 with SMTP id x10mr6423227otx.3.1492726569420; Thu, 20 Apr 2017 15:16:09 -0700 (PDT) MIME-Version: 1.0 Received: by 10.202.77.144 with HTTP; Thu, 20 Apr 2017 15:16:08 -0700 (PDT) In-Reply-To: References: <87mvcyshia.fsf@alrua-kau> <87d1dmthjr.fsf@alrua-karlstad> From: =?UTF-8?Q?Bj=C3=B6rn_Smedman?= Date: Fri, 21 Apr 2017 00:16:08 +0200 X-Gmail-Original-Message-ID: Message-ID: To: =?UTF-8?B?VG9rZSBIw7hpbGFuZC1Kw7hyZ2Vuc2Vu?= Cc: mab-wifi@lists.bufferbloat.net Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [mab-wifi] Initial algorithm simulation results X-BeenThere: mab-wifi@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Multi-armed-bandit WiFi rate control List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 20 Apr 2017 22:16:11 -0000 On Sun, Mar 26, 2017 at 10:07 PM, Bj=C3=B6rn Smedman wr= ote: > On Sun, Mar 12, 2017 at 8:35 PM, Toke H=C3=B8iland-J=C3=B8rgensen wrote: >> Bj=C3=B6rn Smedman 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=C3=B6rn 1. http://andes.ucmerced.edu/papers/Kamthe09b.pdf