Spectrum Bandit Optimization

Marc Lelarge 1, 2, 3 Alexandre Proutière 4 Sadegh Talebi 4
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider the problem of allocating radio channels to links in a wireless network. Links interact through interference, modelled as a conflict graph (i.e., two interfering links cannot be simultaneously active on the same channel). We aim at identifying the channel allocation maximizing the total network throughput over a finite time horizon. Should we know the average radio conditions on each channel and on each link, an optimal allocation would be obtained by solving an Integer Linear Program (ILP). When radio conditions are unknown a priori, we look for a sequential channel allocation policy that converges to the optimal allocation while minimizing on the way the throughput loss or {\it regret} due to the need for exploring sub-optimal allocations. We formulate this problem as a generic linear bandit problem, and analyze it first in a stochastic setting where radio conditions are driven by a stationary stochastic process, and then in an adversarial setting where radio conditions can evolve arbitrarily. We provide, in both settings, algorithms whose regret upper bounds outperform those of existing algorithms for linear bandit problems.
Type de document :
Communication dans un congrès
IEEE Information Theory Workshop, Sep 2013, Seville, Spain. 2013
Liste complète des métadonnées

Contributeur : Marc Lelarge <>
Soumis le : mercredi 11 décembre 2013 - 18:49:06
Dernière modification le : mercredi 21 mars 2018 - 18:57:46


  • HAL Id : hal-00917427, version 1



Marc Lelarge, Alexandre Proutière, Sadegh Talebi. Spectrum Bandit Optimization. IEEE Information Theory Workshop, Sep 2013, Seville, Spain. 2013. 〈hal-00917427〉



Consultations de la notice