Computing the Feedback Capacity of Finite State Channels using Reinforcement Learning
Computing the Feedback Capacity of Finite State Channels using Reinforcement Learning
复制标题
使用强化学习计算有限状态通道的反馈能力
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
H. Permuter
中科院分区：
文献类型：
--
作者：
Ziv Aharoni;Oron Sabag;H. Permuter
在本文中，我们提出了一种新的方法来计算反馈容量的通道与记忆强化学习（RL）。在强化学习中，人们试图最大化在顺序决策环境中收集的累积奖励。这是通过收集底层环境的样本并使用它们来学习最佳决策规则来完成的。这种方法的主要优点是它的计算效率，即使在高维问题。因此，RL可以用于数值估计具有大字母长度的单股有限状态信道（FSC）的反馈容量。RL算法的结果揭示了最优决策规则的属性，在我们的情况下，是信道的最优输入分布。这些见解可以通过求解相应的下限和上限转换为解析的单字母容量表达式。我们证明了这种方法的效率，通过解析求解的反馈容量的著名的伊辛信道与三进制字母表。我们还提供了一个简单的编码方案，实现了反馈能力。
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.
DOI：
10.1109/jsait.2020.2986752
发表时间：
2018-07
期刊：
IEEE Journal on Selected Areas in Information Theory
影响因子：
--
作者：
Hyeji Kim;Yihan Jiang;Sreeram Kannan;Sewoong Oh;P. Viswanath
通讯作者：
Hyeji Kim;Yihan Jiang;Sreeram Kannan;Sewoong Oh;P. Viswanath