Maximal-Capacity Discrete Memoryless Channel Identification

Maximilian Egger, Rawad Bitar, Antonia Wachter-Zeh, Deniz Gündüz, Nir Weinberger

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

We consider the problem of finding the channel with the highest capacity among several discrete memoryless channels (DMCs) with the same input-output alphabet sizes by means of exploration using multi-armed bandits. This setting is motivated by the problem of exploring channel statistics in communication systems by the invocation of training sequences. We particularly focus on the best arm identification problem and rank the candidate DMCs by their capacities. We propose a capacity estimator based on channel sensing and derive associated concentration results. Using this capacity estimator, we introduce BestChanID, a gap-elimination algorithm, oblivious to the capacity-achieving input distribution, which is guaranteed to output the best DMC, i.e., DMC with the largest capacity, with a desired confidence. We further introduce NaiveChanSel, an algorithm that outputs with certain confidence a DMC whose capacity is close to the largest capacity, and can be used as a subroutine in BestChanID. We analyze the sample complexity of both algorithms, i.e., the total number of channel senses, as a function of the desired confidence parameter, the number of available channels, and the input and output alphabet sizes of the channels. We show that the cost of best channel identification scales cubically with the alphabet size.

Original languageEnglish
Title of host publication2023 IEEE International Symposium on Information Theory, ISIT 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2248-2253
Number of pages6
ISBN (Electronic)9781665475549
DOIs
StatePublished - 2023
Event2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China
Duration: 25 Jun 202330 Jun 2023

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2023-June
ISSN (Print)2157-8095

Conference

Conference2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/TerritoryTaiwan, Province of China
CityTaipei
Period25/06/2330/06/23

Fingerprint

Dive into the research topics of 'Maximal-Capacity Discrete Memoryless Channel Identification'. Together they form a unique fingerprint.

Cite this