TY - GEN
T1 - Maximal-Capacity Discrete Memoryless Channel Identification
AU - Egger, Maximilian
AU - Bitar, Rawad
AU - Wachter-Zeh, Antonia
AU - Gündüz, Deniz
AU - Weinberger, Nir
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85171437339&partnerID=8YFLogxK
U2 - 10.1109/ISIT54713.2023.10206461
DO - 10.1109/ISIT54713.2023.10206461
M3 - Conference contribution
AN - SCOPUS:85171437339
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2248
EP - 2253
BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023
Y2 - 25 June 2023 through 30 June 2023
ER -