Variable length coding learns unknown channels with bandit feedback
Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection
Information TheoryMachine Learning
Summary
Communicating over multiple unknown noisy channels is challenging because the best channel isn’t known in advance. The authors study how to send messages efficiently while learning which channel works best by combining feedback communication methods with strategies from multi-choice decision problems called bandits. They propose two schemes that simultaneously decode the message and explore the channels, proving their methods perform optimally with respect to decoding speed and learning. Their work improves on previous methods when multiple channels are involved and when there is only one channel.
What this means in practice
- •For wireless network engineers: Design communication protocols that adaptively select the best noisy channels to improve data transmission efficiency without prior channel knowledge.
- •For satellite communication teams: Implement feedback coding schemes that simultaneously learn channel qualities and decode messages to optimize throughput over unknown noisy links.
Authors
Recep Can Yavas
Abstract
We study variable-length feedback (VLF) coding over $K$ additive white Gaussian noise (AWGN) channels whose noise variances are unknown to both terminals but lie in a known interval. The receiver selects one channel at each time, conveys the selection over noiseless feedback, and must learn the channel qualities while decoding, to avoid overusing suboptimal channels. This setting, which we call the VLF-Bandit problem, combines VLF coding, universal decoding, and bandit channel selection. We develop two joint coding and channel-selection schemes. The VLSF-Bandit scheme is a single-phase variable-length stop-feedback (VLSF) scheme based on a Gaussian random codebook, a score formed from a ratio of likelihood mixtures, and the asymptotically optimal $\text{kl-UCB}^{++}$ bandit algorithm applied to the received power. The VLF-Bandit scheme sends the message in packets by Schalkwijk--Kailath transmission, uses its normalized outputs as noise samples to learn the variances, and lets its exploration packets carry message bits. We prove second-order achievability bounds for both schemes, which are first-order optimal. In the logarithm of the achievable codebook size, the magnitude of the $\log N$ coefficient, with $N$ the average decoding time, is a baseline of one plus a channel-exploration term for VLSF-Bandit. For VLF-Bandit, this magnitude is smaller, with a universal-decoding term replacing the baseline and a smaller channel-exploration term. The VLF-Bandit bound improves on the universal VLF bound of Yavas and Tan (2025) for $K=1$ and on the bound of an explore-then-commit strategy whenever $K\geq2$.