Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback
Haricharan Balasundaram, Krishna Jagannathan · 2025
Read Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback by Haricharan Balasundaram, Krishna Jagannathan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08599.txt.
Introduction
Haricharan Balasundaram and Krishna Jagannathan study sending data over a lossy channel of unknown loss rate in a 2025 paper. Packets vanish at a set chance the sender does not know. Rare check-ins let the sender ask what share was lost so far, and every probe costs time that could carry data.
They frame the cost as regret against an all-knowing sender at the same error rate. One plan probes once, learns the rate, then sends at a set pace, with regret that grows as the two-thirds power of the time span. A windowed plan probes a few more times and cuts the regret's growth to a square root pace.
Catalog record
| CREATOR | Haricharan Balasundaram, Krishna Jagannathan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08599
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback Haricharan Balasundaram, Krishna Jagannathan Abstract We address the problem of reliable data transmission within a finite time horizon T T over a binary erasure channel with unknown erasure probability. We consider a feedback model wherein the transmitter can query the receiver infrequently and obtain the empirical erasure rate experienced by the latter. We aim to minimize a regret quantity, i.e. how much worse a strategy performs compared to an oracle who knows the probability of erasure, while operating at the same block error rate. A learning vs. exploitation dilemma manifests in this scenario—specifically, we need to balance between (i) learning the erasure probability with reasonable accuracy and (ii) utilizing the channel to transmit as many information bits as possible. We propose two strategies: (i) a two-phase approach using rate estimation followed by transmission that achieves an O ( T 2 3 ) O({T}^{\frac{2}{3}}) regret using only one query, and (ii) a windowing strategy using geometrically-increasing window sizes that achieves an O ( T ) O({\sqrt{T}}) regret using O ( log ( T ) ) O(\log(T)) queries. I Introduction Erasure channels are one of the most widely-studied noise models in information theory. We consider a regime where the transmission blocklengths are large but finite, building upon the seminal work of Polyanskiy, Poor, and Verdú [ 1 ] which establishes achievability and converse bounds for transmission over Discrete Memoryless Channels (DMCs). The problem of finite blocklength encoding has since been extensively studied, with extensions to multi-user [ 2 ] , multiple-access [ 3 , 4 ] , fading [ 5 , 6 , 7 , 8 ] , and Gaussian channels [ 9 ] . We address the problem of maximizing the information transmitted through a binary erasure channel over a finite time horizon T . In a key departure from the usual setting, we assume that the erasure probability is unknown to the transmitter. We assume that there is only empirical erasure rate feedback, i.e., whenever the transmitter queries the receiver, the latter conveys only the fraction of bits that have been erased until that point (and not the location of the erased bits). Further, since such queries can be expensive, we are interested in the regime where the number of such queries, q, is ‘small’ in comparison to T . If the receiver provides instantaneous feedback to the transmitter after each symbol reception as studied in [ 10 ] , the transmitter can simply retransmit each erased bit. On average, T(1-\delta) many bits would be received successfully [ 11 ] . However, in our framework this would require T-1 queries to implement, which can be unrealistic and expensive. In our setting, the key challenge lies in balancing the trade-off between learning the erasure probability with reasonable accuracy and transmitting useful information—thus typifying an exploration-exploitation dilemma. To quantify the performance of a transmission strategy, we define the regret of a strategy as the difference between the amount of information transmission achieved by that strategy and the maximum information transmission achieved by an oracle who knows the erasure probability and operates at the same block error rate. Our problem is particularly relevant in the context of IoT and massive Machine Type Communications (mMTC) in cellular networks, where we expect low-resource nodes to transmit a relatively small quantity of information and we expect empirical erasure rate queries to be expensive. We present two transmission strategies and characterize their regret performance over a long but finite time horizon T . The first of these is the Estimate-then-Transmit strategy, a two-phase approach wherein we first send a number of pilot bits to estimate the erasure probability, then query for the empirical erasure rate, and then transmit useful information in the remaining time, which achieves an O(T^{\frac{2}{3}}) regret using only one query. The second strategy uses windows with sizes increasing in a geometric progression, which requires O(\log(T)) queries and achieves an O(\sqrt{T}) regret. Using intuition obtained from the Chernoff bound, we also conjecture the lower bound on the regret if only one query is allowed to be \Omega(\sqrt{T}) , i.e., no oracle-free policy can obtain a better regret for this problem using only one query. This setting is reminiscent of regret minimization in the multi-armed bandits problem. Specifically, the Explore-then-Commit strategy studied in [ 12 , 13 ] achieves an O(T^{\frac{2}{3}}) regret similar to our Estimate-then-Transmit strategy. Likewise, the \Omega(\sqrt{T}) regret lower bound for the instance-independent problem studied in [ 14 ] aligns with our conjecture on the regret lower bound for the single query case in our problem. However, there appears to be no direct correspondence between the two problems, as the multi-armed bandit problem involves arm-pulls that are independent and identically distributed, whereas in our problem encoding over a block requires handling multiple bits jointly. Organization of the Paper. In Section II we define the problem formally and discuss key preliminaries. In Section III we provide theorems regarding the effectiveness of the two proposed strategies. Section IV provides some further insights and concluding remarks. We relegate proofs to the technical appendixes. II Preliminaries and Problem Formulation This section introduces the problem notation, reviews relevant preliminaries, and presents the problem formulation. II-A Notation We study the Binary Erasure Channel (BEC), in which bits are erased with erasure probability \delta . In our model, \delta is fixed but unknown. We assume that these erasures are independent across transmissions. Consider a codebook \mathcal{C} consisting of |\mathcal{C}| codewords. Each codeword in the codebook is a binary string of length n ( \mathcal{C}\subseteq{\{0,1\}^{n}} ). The rate is defined as \frac{k}{n} , where k=\log_{2}(|\mathcal{C}|) . The transmitter does not receive feedback on whether an erasure occurred after each transmission, but can query for the empirical erasure rate (the fraction of bits erased) at any point in the transmission. Let X\in\mathcal{C} be the input codeword to the BEC, and let Y\in{\{0,1,?\}^{n}} be the corresponding output. For a codeword X , there exists a conditional probability mass function \mathbb{P}(Y|X) that describes the output of the BEC conditioned on the input. Upon observing an output Y , we use the Maximum Likelihood Decoder \hat{X}=\argmax_{X\in\mathcal{C}}(\mathbb{P}(Y|X)) to predict the input codeword. The error in our encoder-decoder pair for some X\in\mathcal{C} is 1-\mathbb{P}(\hat{X}=x|X=x) . There are two notions of error defined: Definition 1 (Average probability of error) \epsilon_{av}={\frac{1}{|\mathcal{C}|}\sum_{x\in\mathcal{C}}\left(1-\mathbb{P}(\hat{X}=x|X=x)\right)}. (1) Definition 2 (Maximum probability of error) \epsilon_{max}={\max_{x\in\mathcal{C}}(1-\mathbb{P}(\hat{X}=x|X=x)))}. (2) Clearly, \epsilon_{max}\geq\epsilon_{av} and we will consider \epsilon\equiv\epsilon_{max} hereon. It is noted here that \epsilon is a block error (in contrast to \delta , which is a bit error). \epsilon depends on the erasure probability \delta , the blocklength n , and the rate r and thus we denote it as \epsilon(\delta,n,r) . Definition 3 ( {(n,|\mathcal{C}|,\epsilon)} -code) A code with codebook size |\mathcal{C}| , blocklength n , and maximum probability of error equal to \epsilon . Such a code may not always exist. II-B Preliminaries on Finite Blocklength BEC We recall equivalent versions of the relevant results from the celebrated work of Polyanskiy, Poor, and Verdú on encoding with finite blocklengths [ 1 ] . There are no known exact expressions for \epsilon(\delta,n,r) and we instead resort to upper and lower bounds. Theorem