Low-Complexity, Low-Regret Link Rate Selection in Rapidly-Varying Wireless Channels

Harsh Gupta, Atilla Eryilmaz, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the problem of transmitting at the optimal rate over a rapidly-varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mm Wave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called Modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.

Original languageEnglish (US)
Title of host publicationINFOCOM 2018 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Electronic)9781538641286
StatePublished - Oct 8 2018
Externally publishedYes
Event2018 IEEE Conference on Computer Communications, INFOCOM 2018 - Honolulu, United States
Duration: Apr 15 2018Apr 19 2018

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other2018 IEEE Conference on Computer Communications, INFOCOM 2018
Country/TerritoryUnited States


  • Computational Complexity
  • Link Rate Selection
  • Regret Minimization
  • Thompson Sampling

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Low-Complexity, Low-Regret Link Rate Selection in Rapidly-Varying Wireless Channels'. Together they form a unique fingerprint.

Cite this