pith. sign in

arxiv: 2507.08599 · v2 · submitted 2025-07-11 · 💻 cs.IT · math.IT

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

Haricharan Balasundaram , Krishna Jagannathan This is my paper

Pith reviewed 2026-05-19 05:31 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords binary erasure channelregret minimizationempirical feedbackrate adaptationunknown channel parametersfinite-horizon transmissionexploration-exploitation
0
0 comments X

The pith

Infrequent queries for empirical erasure rates let transmitters achieve sublinear regret over unknown binary erasure channels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to transmit reliably over a binary erasure channel whose erasure probability is unknown in advance. A transmitter can query the receiver only rarely to learn the empirical erasure rate and must still send as many bits as possible while keeping block error rate fixed. The central tension is trading off a few queries to estimate the channel against the time spent actually transmitting data. Two concrete methods are presented that keep regret below linear in the horizon T.

Core claim

A two-phase method that estimates the erasure rate once and then transmits for the rest of the horizon attains O(T^{2/3}) regret with a single query. A windowing method that uses geometrically increasing window sizes attains O(sqrt(T)) regret with O(log T) queries. Both methods match the block error rate that an oracle knowing the true erasure probability would achieve.

What carries the argument

The regret metric that measures excess block-error-rate cost relative to an oracle transmitter who knows the erasure probability exactly.

If this is right

  • Only one query suffices to keep regret sublinear in T.
  • O(log T) queries suffice to improve the scaling to square-root regret.
  • Both approaches maintain the same target block error rate as the oracle.
  • The methods apply directly to any finite horizon where the transmitter must finish within T uses.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same query-efficient idea may apply to other unknown channels such as additive white Gaussian noise with unknown noise variance.
  • Window sizes that grow geometrically could be tuned further to trade query count against regret in non-stationary settings.
  • The approach suggests that rate selection can be made adaptive with very low overhead feedback in practical wireless links.

Load-bearing premise

The channel is stationary with independent erasures and the empirical rate measured in a queried interval is close enough to the true probability to guide rate selection.

What would settle it

Run the two-phase strategy on a simulated stationary erasure channel with fixed probability p over horizon T equal to one million and check whether total regret stays within a small constant factor of T to the power 2/3.

Figures

Figures reproduced from arXiv: 2507.08599 by Haricharan Balasundaram, Krishna Jagannathan.

Figure 2
Figure 2. Figure 2: Estimate-then-Transmit strategy Estimation Phase: In this phase of length Te, we send only zeroes in the channel and no meaningful information is transmitted. Let K ∼ Bin(Te, δ) be the binomial random variable of the number of erasures in this phase. At the end of this phase, we query the empirical erasure rate, ˆδ = K Te . Transmission Phase: In this phase of length Tt ≡ T − Te, we send information at the… view at source ↗
Figure 5
Figure 5. Figure 5: Windowing strategy In this section, we consider windowing strategies of the following form: we have M transmission blocks of lengths T⃗ = (T1, T2, . . . , TM) ∈ NM such that PM i=1 Ti = T, as in [PITH_FULL_IMAGE:figures/full_fig_p004_5.png] view at source ↗
Figure 3
Figure 3. Figure 3: Expected number of successfully-decoded information bits, [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: T ∗ e vs T for the Estimate-then-Transmit Strategy for δ = 0.5 and ϵeff = 1 2 C. Numerical Comparison of Strategies We know theoretically that the Geometric Windowing strat￾egy with an O( √ T) regret performs better than the Estimate￾then-Transmit strategy with an O(T 2 3 ) regret for T ∗ e , but uses a greater number of queries. An ‘Arithmetic Windowing‘ strategy with window sizes increasing starting from… view at source ↗
read the original abstract

We address the problem of reliable data transmission within a finite time horizon $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}^{\frac 23})$ regret using only one query, and (ii) a windowing strategy using geometrically-increasing window sizes that achieves an $O({\sqrt{T}})$ regret using $O(\log(T))$ queries.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to solve the problem of reliable data transmission over a finite horizon T on a binary erasure channel with unknown erasure probability. Using a feedback model where the transmitter queries the empirical erasure rate infrequently, it proposes two algorithms: a two-phase rate estimation followed by transmission achieving O(T^{2/3}) regret with one query, and a geometric windowing strategy achieving O(sqrt(T)) regret with O(log T) queries, both matching the oracle block error rate.

Significance. This result, if the bounds are correctly derived, offers practical insights into balancing learning and exploitation in channel coding with limited feedback. It provides specific regret orders that could guide the design of adaptive communication protocols in uncertain environments. The use of empirical feedback is a realistic model for some systems.

major comments (2)
  1. [§3 (Two-phase approach)] The derivation of the O(T^{2/3}) regret bound in the two-phase strategy relies on the empirical erasure rate serving as an accurate proxy for the true p without additional rate backoff. As noted in the stress-test, if only expectation bounds are used rather than high-probability guarantees (e.g., via Hoeffding's inequality to control deviation with high probability), the strategy may require a conservative margin to meet the block error rate, which would add to the regret and potentially invalidate the claimed order.
  2. [§4 (Windowing strategy)] For the geometric windowing strategy, the O(sqrt(T)) regret is claimed using O(log T) queries. The analysis must demonstrate that the cumulative effect of estimation errors across windows does not exceed this order while preserving the exact block error probability constraint. If the proofs use only average-case analysis, the high-probability requirement for the error rate could introduce logarithmic factors or worse.
minor comments (2)
  1. [Abstract] The regret orders are stated as O(T^{2/3}) and O(sqrt(T)), but it would be helpful to clarify if these are upper bounds and under what assumptions on T.
  2. [Introduction] Ensure that the definition of regret is clearly stated early, including how the block error rate is fixed to match the oracle.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful review and constructive comments on our paper. We address each major comment below, providing clarifications on our analysis and indicating any revisions made to strengthen the manuscript.

read point-by-point responses

  1. Referee: [§3 (Two-phase approach)] The derivation of the O(T^{2/3}) regret bound in the two-phase strategy relies on the empirical erasure rate serving as an accurate proxy for the true p without additional rate backoff. As noted in the stress-test, if only expectation bounds are used rather than high-probability guarantees (e.g., via Hoeffding's inequality to control deviation with high probability), the strategy may require a conservative margin to meet the block error rate, which would add to the regret and potentially invalidate the claimed order.

    Authors: We appreciate this observation. In fact, our proof of the O(T^{2/3}) regret bound in Section 3 utilizes Hoeffding's inequality to establish a high-probability guarantee on the accuracy of the empirical erasure rate estimate. The length of the estimation phase is chosen such that the probability of deviation exceeding the required threshold is at most 1/T, ensuring that the transmission rate can be set to achieve the target block error rate without an extra conservative backoff that would alter the regret order. The stress-test in the paper is for empirical validation and does not indicate a reliance on expectation alone. We have added a sentence in the revised version to explicitly reference the use of concentration inequalities in the analysis. revision: yes

  2. Referee: [§4 (Windowing strategy)] For the geometric windowing strategy, the O(sqrt(T)) regret is claimed using O(log T) queries. The analysis must demonstrate that the cumulative effect of estimation errors across windows does not exceed this order while preserving the exact block error probability constraint. If the proofs use only average-case analysis, the high-probability requirement for the error rate could introduce logarithmic factors or worse.

    Authors: Thank you for this comment. Our analysis for the windowing strategy in Section 4 employs a union bound over the O(log T) windows to control the probability of estimation errors across all windows simultaneously. This ensures that with high probability, each window's estimate is sufficiently accurate to maintain the block error rate constraint. The additional logarithmic factors from the union bound are absorbed into the O(sqrt(T)) regret term, as they do not change the asymptotic order. We have included a more detailed explanation of the union bound application in the proof sketch in the revised manuscript to address this concern. revision: yes

Circularity Check

0 steps flagged

No circularity; regret bounds derived from algorithmic analysis

full rationale

The paper presents two explicit algorithmic strategies (two-phase rate estimation followed by transmission, and geometric windowing) and derives their regret bounds O(T^{2/3}) and O(sqrt(T)) via standard analysis of empirical estimation error under i.i.d. erasures, parameter optimization (e.g., choice of tau), and comparison to an oracle that knows the true p. These steps rely on concentration bounds and do not reduce by construction to self-definitions, fitted inputs renamed as predictions, or self-citation chains. The performance metric (regret at fixed block error rate) is defined externally to the algorithms and is not tautological with the claimed bounds. The derivation is therefore self-contained against the stated channel model and query model.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard i.i.d. binary erasure channel model and the assumption that infrequent empirical-rate queries yield usable estimates; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The channel is a memoryless binary erasure channel with fixed but unknown erasure probability p.
    Invoked implicitly when defining the oracle performance and the empirical-rate feedback model.

pith-pipeline@v0.9.0 · 5705 in / 1262 out tokens · 48908 ms · 2026-05-19T05:31:42.663237+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Channel coding rate in the finite blocklength regime,

    Y . Polyanskiy, H. V . Poor, and S. Verdu, “Channel coding rate in the finite blocklength regime,” IEEE Transactions on Information Theory , vol. 56, no. 5, pp. 2307–2359, 2010

    work page 2010

  2. [2]

    Non-asymptotic achievability bounds in multiuser information theory,

    S. Verdú, “Non-asymptotic achievability bounds in multiuser information theory,” in 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , 2012, pp. 1–8

    work page 2012

  3. [3]

    Finite blocklength coding for multiple access channels,

    Y .-W. Huang and P. Moulin, “Finite blocklength coding for multiple access channels,” in 2012 IEEE International Symposium on Information Theory Proceedings, 2012, pp. 831–835

    work page 2012

  4. [4]

    On the dispersions of three network informa- tion theory problems,

    V . Y . F. Tan and O. Kosut, “On the dispersions of three network informa- tion theory problems,” in 2012 46th Annual Conference on Information Sciences and Systems (CISS) , 2012, pp. 1–6

    work page 2012

  5. [5]

    Quasi-static simo fading channels at finite blocklength,

    W. Yang, G. Durisi, T. Koch, and Y . Polyanskiy, “Quasi-static simo fading channels at finite blocklength,” in 2013 IEEE International Symposium on Information Theory , 2013, pp. 1531–1535

    work page 2013

  6. [6]

    Block-fading channels at finite blocklength,

    ——, “Block-fading channels at finite blocklength,” in ISWCS 2013; The Tenth International Symposium on Wireless Communication Systems, 2013, pp. 1–4

    work page 2013

  7. [7]

    Quasi-static multiple-antenna fading channels at finite block- length,

    ——, “Quasi-static multiple-antenna fading channels at finite block- length,” IEEE Transactions on Information Theory , vol. 60, no. 7, pp. 4232–4265, 2014

    work page 2014

  8. [8]

    Finite blocklength information theory: What is the practical impact on wireless communi- cations?

    P. Mary, J.-M. Gorce, A. Unsal, and H. V . Poor, “Finite blocklength information theory: What is the practical impact on wireless communi- cations?” in 2016 IEEE Globecom Workshops (GC Wkshps) , 2016, pp. 1–6

    work page 2016

  9. [9]

    A Unified Approach to Gaussian Channels with Finite Blocklength,

    E. MolavianJazi, “A Unified Approach to Gaussian Channels with Finite Blocklength,” 7 2014

    work page 2014

  10. [10]

    Feedback in the non-asymptotic regime,

    Y . Polyanskiy, H. V . Poor, and S. Verdú, “Feedback in the non-asymptotic regime,” IEEE Transactions on Information Theory , vol. 57, no. 8, pp. 4903–4925, aug 2011

    work page 2011

  11. [11]

    A. E. Gamal and Y .-H. Kim, Network Information Theory . Cambridge: Cambridge University Press, 2011, ch. 17.1, p. 428

    work page 2011

  12. [12]

    Probability Inequalities for Sums of Bounded Ra n- dom Variables

    F. J. Anscombe, “Sequential medical trials,” Jour- nal of the American Statistical Association , vol. 58, no. 302, pp. 365–383, 1963. [Online]. Available: https://www.tandfonline.com/doi/abs/10.1080/01621459.1963.10500851

    work page doi:10.1080/01621459.1963.10500851 1963

  13. [13]

    Lattimore and C

    T. Lattimore and C. Szepesvári, Bandit Algorithms . Cambridge University Press, 2020, ch. 6. [Online]. Available: https://tor- lattimore.com/downloads/book/book.pdf

    work page 2020

  14. [14]

    Com- put.32, 1 (2002), 48–77

    P. Auer, N. Cesa-Bianchi, Y . Freund, and R. E. Schapire, “The nonstochastic multiarmed bandit problem,” SIAM Journal on Computing, vol. 32, no. 1, pp. 48–77, 2002. [Online]. Available: https://doi.org/10.1137/S0097539701398375

    work page doi:10.1137/s0097539701398375 2002

  15. [15]

    The accuracy of the Gaussian approximation to the sum of independent variates,

    A. C. Berry, “The accuracy of the Gaussian approximation to the sum of independent variates,” Transactions of the American Mathematical Society, vol. 49, no. 1, pp. 122–136, 1941

    work page 1941

  16. [16]

    A nonuniform local limit theorem for poisson binomial random variables via stein’s method,

    G. Auld and K. Neammanee, “A nonuniform local limit theorem for poisson binomial random variables via stein’s method,” Journal of Inequalities and Applications , vol. 2024, no. 1, p. 10, 2024. [Online]. Available: https://doi.org/10.1186/s13660-024-03087-4 APPENDIX A PROOF OF THEOREM 3.1 Proof: Let K ∼ Bin(Te, δ). For 0 ≤ K ≤ Te(δ − b), 1 − δ ≤ r ≤ 1 − b,...

    work page doi:10.1186/s13660-024-03087-4 2024