Spectrum bandit optimization

We consider the problem of allocating radio channels to links in a wireless. Links interact through interference, modelled as a conflict graph(i.e., two interfering links cannot be simultaneously active on the same). We aim at identifying the channel allocation maximizing the total throughput over a finite time horizon. Should we know the average radio on each channel and on each link, an optimal allocation would be by solving an Integer Linear Program (ILP). When radio conditions are a priori, we look for a sequential channel allocation policy that to the optimal allocation while minimizing on the way the throughput or {\ regret} due to the need for exploring sub-optimal allocations. We this problem as a generic linear bandit problem, and analyze it first a stochastic setting where radio conditions are driven by a stationary process, and then in an adversarial setting where radio conditions evolve arbitrarily. We provide new algorithms in both settings and derive bounds on their regrets.