Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret

By Anima Anandkumar, Nithin Michael, Andy Tang, Ananthram Swami. IEEE Journal on Selected Areas in Communications, 2010

358 citations recorded by the source corpus.

The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement among the secondary users and sensing and access decisions are undertaken by them in a completely distributed manner. We propose policies for distributed learning and access which achieve order-optimal cognitive system throughput (number of successful secondary transmissions) under self play, i.e., when implemented at all the secondary users. Equivalently, our policies minimize the sum regret in distributed learning and access, which is the loss in secondary throughput due to learning and distributed access. For the scenario when the number of secondary users is known to the policy, we prove that the total regret is logarithmic in the number of transmission slots. This policy achieves order-optimal regret based on a logarithmic lower bound for regret under any uniformly-good learning and access policy. We then consider the case when the number of secondary users is fixed but unknown, and is estimated at each user through feedback. We propose a policy whose sum regret grows only slightly faster than logarithmic in the number of transmission slots.

Subfields: Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/6b07c5f1e970f2de74612b70b53f190f6ef47562

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards (2010, background): “Liu and Zhao [4], and Anandkumar et al. [3] have both developed policies for the problem of M distributed players operating N independent arms.”
Introduction to Multi-Armed Bandits (2019, background): “Bandit problems directly motivated by radio networks have been studied starting from (Lai et al., 2008; Liu and Zhao, 2010; Anandkumar et al., 2011).”