Computing the Feedback Capacity of Finite State Channels using
  Reinforcement Learning
  In this paper, we propose a novel method to compute the feedback capacity of
channels with memory using reinforcement learning (RL). 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. These insights can
be converted into analytic, single-letter capacity expressions by solving
corresponding lower and upper bounds. We demonstrate the efficiency of this
method by analytically solving the feedback capacity of the well-known Ising
channel with a ternary alphabet. We also provide a simple coding scheme that
achieves the feedback capacity.
