On Reinforcement Learning for computing channel capacity with feedback
Prof. Haim Permuter
Department of Electrical & Computer Engineering
In this talk we present two novel ideas: the first is novel method to compute the feedback capacity of channels with memory using reinforcement learning (RL). The second is a new technique of using Graph-based auxiliary random variable to convert a multi-letter expression of feedback capacity formula into a single letter expression.
In RL, one seeks to maximize cumulative rewards collected in a sequential decision-making environment. This is done by collecting samples of the underlying environment and using them to learn the optimal decision rule. The main advantage of this approach is its computational efficiency, even in high dimensional problems. Hence, RL can be used to estimate numerically the feedback capacity of unifilar finite state channels (FSCs) with large alphabet size. The outcome of the RL algorithm sheds light on the properties of the optimal decision rule, which in our case, is the optimal input distribution of the channel.
The insights gained from the RL computation can be converted into analytic, single-letter capacity expressions by solving corresponding lower and upper bounds. The bounds are based on another novel idea of using Graph-based auxiliary random variable
We demonstrate the efficiency of this method by analytically solving the feedback capacity of the well-known Ising channel with a large alphabet. We also provide a simple coding scheme that achieves the feedback capacity.
Haim Permuter received his B.Sc. (summa cum laude) from Ben-Gurion University (BGU) and Ph.D. from Stanford University, both in in Electrical Engineering, in 1997 and 2008, respectively. Between 1997-2004, he served as a scientific research officer in an R&D unit in the Israeli Defense Forces. In summer 2002 he worked for IBM, Almaden research center. He is a recipient of several rewards including Eshkol Fellowship, Wolf Award, Fulbright Fellowship, Stanford Graduate Fellowship, U.S.-Israel Binational Science Foundation Bergmann Memorial Award, and Allon Fellowship. Haim joined the faculty of Electrical Engineering Department at BGU in Oct 2008 as a tenure-track faculty, and is now a Professor, Luck-Hille Chair in Electrical Engineering. Haim also serves as head of the communication, cyber and information track in his department. Haim served on the editorial boards of the IEEE Transactions on Information Theory in 2013-2016.