Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection

Recep Can Yavas

cs.ITOct 27, 2026

Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection

Authors: Recep Can Yavas

Organizations: Department of Electrical and Electronics Engineering at Bilkent University, 06800, Ankara, Turkey

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$ .

Figures & tables

Panel of Figure 1 — Fig. 1: VLF-Bandit system model, with the selected channel $A_{t}=2$ in solid black.

Panel of Figure 2 — Fig. 2: The VLF-Bandit scheme. With probability $\epsilon_{0}$ , the decoder stops at time zero; otherwise, $\ell_{0}$ zero inputs on each channel precede a preliminary packet, $B\geq 0$ exploration packets, and a final packet. Top: the bits of $W-1$ that each packet carries. Heights: the nominal powers, with the saved allocation $\Omega$ in green. Bottom: the number of channel uses of each phase, for the final packet on the best channel. Not to scale. The quantities are defined in Sections IV-C1 to IV-C5 .

Panel of Figure 3 — Fig. 3: Refinement $n\geq 1$ of packet $j$ over channel $J_{j}$ . Both terminals compute the precision estimate (dashed box), the constant $\frac{\eta_{\min}}{2}$ for $n\leq 9$ .

Fig. 4: Rate evaluations for the known variance interval

[0.5,2.5]

\epsilon=10^{-3}

, and

\epsilon_{0}=0

. The instances are

\sigma_{1}^{2}=1

for

K=1

and

\bm{\sigma}^{2}=(1,2)

for

K=2

. Thin and thick curves denote

K=1

and

K=2

, respectively; ETC uses

K=2

. The VLSF-Bandit curves report simulated true-message threshold-crossing rates. Each VLF-Bandit and VLSF-Bandit rate evaluation uses at least 100 000 independent trials; each ETC evaluation uses 50 000. The dashed red curve is the converse.

Panel of Figure 5 — Fig. 5: Steps of the proof of Theorem 2 and the subsections that contain them. An arrow points from a result to a step that uses it, and Lemma 9 also enters the proofs of Lemmas 10 – 12 .

Fig. 6: Second-order coefficients for

K=2

, unit average power,

\sigma_{1}^{2}=1

, and

\sigma_{2}^{2}\in[1.5,2.5]

. The shaded region shows

\rho_{\mathrm{ETC}}-\rho_{\mathrm{joint}}

, evaluated from ( 148 ) and ( 149 ).

Error-Correcting Codes

See all 35 papers

May 29, 2026

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size

B

, and during each batch the learner sends

B

requested arm pulls to an agent, who then observes the corresponding

B

rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that

Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\})

regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of

\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})

. We develop two phased-elimination algorithms based on

G

-optimal designs and 1-bit mean estimation. The first achieves

\widetilde{O}(dB + d\sqrt{T})

regret, matching the lower bound up to logarithmic factors when

\lvert \mathcal{A} \rvert = \exp(Ω(d))

, and the second incorporates a safe-arm identification and warm-start procedure to obtain

\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})

regret, which is near-optimal in broad scaling regimes of

(\lvert \mathcal{A} \rvert, B, d, T)

. Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as

Θ(\sqrt{T})

Ivan Lau, Daniel McMorrow, Kevin Jamieson +1

National University of Singapore · University of Washington

Multi-Armed Bandits Batched Bandits Minimax Regret Communication Complexity Low-Bit Quantization Bandit Learning

Ask PDF

Apr 10, 2026

Diffusion Denoiser Achievable Analysis for Finite Blocklength Unsourced Random Access

Polyanskiy proposed a framework for the unsourced multiple access channel (MAC) problem where users employ a common codebook in the finite blocklength regime. However, existing approaches handle channel noise before the joint decoder. In this work, we introduce a decoder compatible diffusion denoiser as a lightweight analysis within joint decoding. The score network is trained on samples drawn from the channel output distribution, making the method easy to integrate with existing code designs. In our theoretical analysis, we derive a diffusion-denoiser random-coding achievable bound that is strictly tighter. Simulations on existing decoders, including FASURA, MSUG-MRA and pilot-based method, show consistent performance gains with at least a

0.5

\mathrm{dB}

improvement in required

\mathrm{E_b/N_0}

at a fixed error target.

Yuming Han, Yuxin Long

Texas A&M University, Department of ECE, College Station, TX 77843, USA · University of Leeds, Institute for Transport Studies, Leeds, LS2 9JT, UK

Diffusion-Based Denoising Diffusion Models

Ask PDF

Aug 14, 2026

Polar Code Based Federated Learning: Convergence Analysis and Resource Allocation

Federated learning (FL) enables collaborative model training across distributed devices without sharing raw data; however, it faces significant communication bottlenecks and channel impairments in practice. Conventional network layer treatments either idealize the channel as error free or apply equal error protection (EEP) to transmitted model updates, failing to account for the inherently unequal importance of quantization bits within a single local model. To address this limitation, we propose a cross layer polar code based FL scheme that leverages the unequal error protection (UEP) property of polar codes under finite block lengths. Specifically, the proposed design selectively protects more significant quantization bits, thereby mitigating the detrimental effects of channel noise. We further provide a rigorous convergence analysis of the proposed scheme, deriving an upper bound on the convergence gap, which we then jointly optimize over the number of quantization bits and the polar code block length across all training iterations. Experimental results demonstrate that both constant and variable block length configurations of our polar code based scheme consistently achieve substantial performance gains over uncoded and LDPC-based EEP benchmarks, with the advantage becoming increasingly pronounced as the channel quality deteriorating. These findings confirm the efficacy of our cross-layer design in enhancing FL robustness and efficiency under realistic channel conditions.

Han Xiao, Wei Kang, Nan Liu

School of Information Science and Engineering, Southeast University, Nanjing 211189, China · National Mobile Communications Research Laboratory, Southeast University, Nanjing 211189, China

Unequal Error Protection Federated Learning

Ask PDF

Abstract

Error-Correcting Codes

Explore similar work

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

Diffusion Denoiser Achievable Analysis for Finite Blocklength Unsourced Random Access

Polar Code Based Federated Learning: Convergence Analysis and Resource Allocation