Computing the Feedback Capacity of Finite State Channels using Reinforcement Learning
| Autor: | Ziv Aharoni, Haim H. Permuter, Oron Sabag |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Mathematical optimization Computer science Computer Science - Information Theory Information Theory (cs.IT) 020206 networking & telecommunications 02 engineering and technology 010501 environmental sciences 01 natural sciences Machine Learning (cs.LG) 0202 electrical engineering electronic engineering information engineering Reinforcement learning Finite state Ising model Computer Science::Information Theory 0105 earth and related environmental sciences Communication channel |
| Zdroj: | ISIT |
| DOI: | 10.1109/isit.2019.8849364 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|