CaltechAUTHORS
  A Caltech Library Service

Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret

Anandkumar, Animashree and Michael, Nithin and Tang, Ao Kevin and Swami, Ananthram (2011) Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret. IEEE Journal on Selected Areas in Communications, 29 (4). pp. 731-745. ISSN 0733-8716. https://resolver.caltech.edu/CaltechAUTHORS:20170922-133040888

[img] PDF - Submitted Version
See Usage Policy.

312Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170922-133040888

Abstract

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/JSAC.2011.110406DOIArticle
http://ieeexplore.ieee.org/document/5738217PublisherArticle
https://arxiv.org/abs/1006.1673arXivDiscussion Paper
ORCID:
AuthorORCID
Tang, Ao Kevin0000-0001-6296-644X
Additional Information:© 2011 IEEE. Manuscript received 1 December 2009; revised 4 June 2010. During the stint of this work, the first author was supported by MURI through AFOSR Grant FA9550-06-1-0324. The second and the third authors are supported in part through NSF grant CCF-0835706. Parts of this paper were presented at [1].
Funders:
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0324
NSFCCF-0835706
Subject Keywords:Cognitive medium access control, multi-armed bandits, distributed algorithms, logarithmic regret
Issue or Number:4
Record Number:CaltechAUTHORS:20170922-133040888
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170922-133040888
Official Citation:A. Anandkumar, N. Michael, A. K. Tang and A. Swami, "Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret," in IEEE Journal on Selected Areas in Communications, vol. 29, no. 4, pp. 731-745, April 2011. doi: 10.1109/JSAC.2011.110406 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5738217&isnumber=5738209
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81748
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:22 Sep 2017 20:56
Last Modified:03 Oct 2019 18:46

Repository Staff Only: item control page