ISL & IT Forum present "Feedback capacity of channels with memory via Reinforcement Learning and Graph-based auxiliary random variable""
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.