A Caltech Library Service

Feedback Capacity of Ising Channels With Large Alphabet via Reinforcement Learning

Aharoni, Ziv and Sabag, Oron and Permuter, Haim H. (2022) Feedback Capacity of Ising Channels With Large Alphabet via Reinforcement Learning. IEEE Transactions on Information Theory, 68 (9). pp. 5637-5656. ISSN 0018-9448. doi:10.1109/tit.2022.3168729.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We propose a new method to compute the feedback capacity of unifilar finite state channels (FSCs) with memory using reinforcement learning (RL). The feedback capacity was previously estimated using its formulation as a Markov decision process (MDP) with dynamic programming (DP) algorithms. However, their computational complexity grows exponentially with the channel alphabet size. Therefore, we use RL, and specifically, its ability to parameterize value functions and policies with neural networks, to evaluate numerically the feedback capacity of channels with a large alphabet size. The outcome of the RL algorithm is a numerical lower bound on the feedback capacity, which is used to reveal the structure of the optimal solution. The structure is modeled by a graph-based auxiliary random variable that is utilized to derive an analytic upper bound on the feedback capacity with the duality bound. The capacity computation is concluded by verifying the tightness of the upper bound by testing whether it is Bahl-Cocke-Jelinek-Raviv (BCJR) invariant. We demonstrate this method on the Ising channel with an arbitrary alphabet size. For an alphabet size smaller than or equal to 8, we derive the analytic solution of the capacity. Next, the structure of the numerical solution is used to deduce a simple coding scheme that achieves the feedback capacity and serves as a lower bound for larger alphabets. For an alphabet size greater than 8, we present an upper bound on the feedback capacity. For an asymptotically large alphabet size, we present an asymptotic optimal coding scheme.

Item Type:Article
Related URLs:
URLURL TypeDescription
Aharoni, Ziv0000-0003-0204-4034
Sabag, Oron0000-0002-7907-1463
Permuter, Haim H.0000-0003-3170-3190
Additional Information:This work was supported in part by the German Research Foundation (DFG) via the German–Israeli Project Cooperation (DIP), in part by the Israeli Science Foundation (ISF) under Research Grant 899/21, and in part by the Israeli Innovation Authority as part of the Worldwide Innovative Networking (WIN) Consortium. The work of Oron Sabag was supported in part by the Israeli Scholarship Education Foundation (ISEF) International Postdoctoral Fellowship. An earlier version of this paper was presented in part at the International Symposium on Information Theory (ISIT) 2019.
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)UNSPECIFIED
Israel Science Foundation899/21
Israel Innovation AuthorityUNSPECIFIED
Israel Scholarship Education FoundationUNSPECIFIED
Issue or Number:9
Record Number:CaltechAUTHORS:20220909-232698000
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116867
Deposited By: Olivia Warschaw
Deposited On:29 Oct 2022 21:18
Last Modified:29 Oct 2022 21:18

Repository Staff Only: item control page