🔢 mathematics

Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback

This paper proposes two learning strategies for reliable data transmission over binary erasure channels with unknown erasure probabilities and infrequent empirical feedback, achieving $O(T^{2/3})$ and $O(\sqrt{T})$ regret bounds by effectively balancing the trade-off between channel estimation and information transmission.

Original authors: Haricharan Balasundaram, Krishna Jagannathan

Published 2026-05-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Haricharan Balasundaram, Krishna Jagannathan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a long letter to a friend through a very unreliable postal service. You know that sometimes letters get lost (erased), but you don't know how often they get lost. Is it 1 in 10? 1 in 2? You have a limited amount of time to get as much of your message across as possible.

The big problem is a "Catch-22":

If you guess the loss rate wrong: If you pack your letter too densely (sending too many words per page), the lost pages will make the whole message unreadable. If you pack it too loosely, you waste time and don't send enough words.
If you ask for help too much: You can call your friend to ask, "How many letters have been lost so far?" But every time you call, it costs you time and money. You want to ask as few times as possible.

This paper is about finding the perfect balance between learning the postal service's reliability and sending your actual message.

The Two Strategies Proposed

The authors suggest two different ways to handle this "learning vs. sending" dilemma.

1. The "Test Run" Strategy (Estimate-then-Transmit)

The Analogy: Imagine you are a chef trying to bake a cake for a huge party, but you don't know how hot your oven is.

Phase 1 (Learning): You spend a chunk of your time baking a single, small "test cake" just to see how the oven behaves. You don't serve this cake to anyone; you just measure how many parts burned.
Phase 2 (Sending): Once you have that one measurement, you call your friend once to confirm the result. Then, you spend the rest of your time baking the actual party cakes at the perfect speed for that specific oven temperature.

The Result: This method is very efficient with phone calls (you only call once). However, because you spent a significant amount of time on the test cake, you miss out on a bit of total cake production. The paper proves that the "wasted time" (regret) grows at a specific rate (roughly $T^{2/3}$ ).

2. The "Geometric Ladder" Strategy (Geometric Windowing)

The Analogy: Instead of one big test run, imagine you are climbing a ladder where the rungs get wider and wider.

Step 1: You send a tiny message. You ask your friend, "How did that go?"
Step 2: You send a message twice as big as the last one. You ask again.
Step 3: You send a message twice as big as the previous one. You ask again.

Because the messages get bigger so fast (1, 2, 4, 8, 16...), you don't need to ask many times to cover the whole time horizon. You might ask 10 times to cover a huge amount of data.

The Result: This method is much smarter about how much you send. You waste less time "learning" because you learn while you are sending. The paper shows this method is better overall (the "wasted time" grows slower, at a rate of $\sqrt{T}$ ), but it requires a few more phone calls (about $\log T$ , which is still a very small number compared to the total time).

The "Oracle" Comparison

To measure how good these strategies are, the authors compare them to a magical "Oracle."

The Oracle: A super-smart friend who knows exactly how often the postal service loses letters before you even start.
The Goal: The goal isn't to be perfect; it's to be as close to the Oracle as possible. The "Regret" is simply the difference between how much information you successfully sent and how much the Oracle would have sent.

The Main Takeaway

The paper proves that you don't need to constantly check in with your friend to get a great result.

If you are okay with a slightly higher "wasted time" penalty, you can get away with one single check-in after a test run.
If you want to be more efficient and minimize wasted time, you should use the ladder strategy, checking in a few times as your messages get exponentially larger.

The authors also guess (conjecture) that if you are only allowed one check-in, you cannot do better than the "Test Run" strategy. There is a fundamental limit to how well you can learn and send at the same time with so little information.

In short: You can learn to transmit data efficiently over a noisy, unknown channel by either doing a big test first (1 check-in) or by gradually increasing your message size while checking in a few times (logarithmic check-ins). Both methods get you very close to the performance of someone who already knew the answer.

Technical Summary: Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback

Problem Formulation
This paper addresses the problem of reliable data transmission over a Binary Erasure Channel (BEC) with an unknown, fixed erasure probability $\delta$ within a finite time horizon $T$ . Unlike standard settings where the transmitter knows $\delta$ , this work assumes the transmitter must learn the channel statistics through infrequent feedback. The feedback model is restricted: the transmitter can query the receiver to obtain the empirical erasure rate (the fraction of bits erased up to that point) but not the specific locations of erased bits. The goal is to maximize the number of successfully decoded information bits while maintaining a specific average block error rate ( $\epsilon_{block}$ ).

The performance metric is regret, defined as the difference between the information transmission achieved by an "oracle" (who knows $\delta$ and operates at the same $\epsilon_{block}$ ) and the transmission achieved by the proposed learning strategy. The core challenge is the exploration-exploitation dilemma: balancing the need to query the channel to estimate $\delta$ accurately against the need to transmit useful data.

Methodology and Proposed Strategies
The authors propose two distinct strategies to manage the trade-off between learning the erasure probability and transmitting data, utilizing finite blocklength information theory results (specifically bounds from Polyanskiy, Poor, and Verdú) to characterize block error probabilities.

Estimate-then-Transmit Strategy:
- Approach: A two-phase approach. The first phase ( $T_e$ ) is dedicated to estimation, where the transmitter sends pilot bits (specifically zeroes) to query the empirical erasure rate once. The second phase ( $T_t = T - T_e$ ) utilizes this estimate to set a transmission rate $\rho = \max(0, 1 - \hat{\delta} - b)$ , where $b$ is a rate back-off parameter to ensure reliability.
- Analysis: The authors approximate the block error function as a step function for large $T$ (0 error if rate $< 1-\delta$ , 1 error otherwise). Using the Berry-Esseen theorem, they derive the optimal estimation window size $T_e^*$ and back-off $b$ .
- Result: This strategy achieves a regret of $O(T^{2/3})$ using only one query.
Geometric Windowing Strategy:
- Approach: A multi-phase strategy where the time horizon is divided into blocks with sizes increasing geometrically ( $T_i = 2^{i-1}$ ). After each block, the transmitter queries the empirical erasure rate and adjusts the rate for the next block using a back-off derived from the accumulated data.
- Analysis: This approach continuously refines the estimate of $\delta$ as the window size grows, allowing the transmission rate to approach the channel capacity more closely over time.
- Result: This strategy achieves a regret of $O(\sqrt{T})$ but requires $O(\log T)$ queries.

Key Results and Theoretical Bounds

Regret Bounds: The paper establishes that the Geometric Windowing strategy offers a superior regret bound of $O(\sqrt{T})$ compared to the $O(T^{2/3})$ bound of the Estimate-then-Transmit strategy, at the cost of additional queries.
Conjectured Lower Bound: The authors conjecture that for the single-query case, the regret lower bound is $\Omega(\sqrt{T})$ . This is based on the intuition that the Chernoff bound imposes a $\Theta(1/\sqrt{n})$ error on the empirical rate estimate after $n$ bits, necessitating a rate pessimism of $\Theta(1/\sqrt{n})$ that results in a regret scaling of $\Omega(\sqrt{T})$ .
Numerical Verification: Simulations confirm the theoretical predictions, showing that the optimal estimation window $T_e^*$ scales as $T^{2/3}$ and that the theoretical expressions for the number of successfully decoded bits closely match numerically computed values.

Significance and Claims
The paper claims to provide a foundational framework for "learning to transmit" in scenarios where channel statistics are unknown and feedback is expensive (e.g., IoT and massive Machine Type Communications). The significance lies in:

Formulating the Problem: Defining the regret minimization problem for finite blocklength transmission over unknown erasure channels with limited feedback.
Strategy Design: Demonstrating that even with very limited feedback (as few as one query), reliable transmission is possible with sub-linear regret.
Trade-off Characterization: Explicitly characterizing the trade-off between the number of queries and the regret performance, showing that increasing the number of queries from 1 to $O(\log T)$ improves the regret from $O(T^{2/3})$ to $O(\sqrt{T})$ .

The authors note that while the results are specific to the BEC, the problem formulation opens avenues for future research into other noise models (Binary Symmetric, Gaussian), channels with memory (Markovian), and multi-user scenarios. They also identify the fundamental characterization of the "number of queries versus regret" frontier as an immediate future direction.