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

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed Bandits Batched Bandits
National University of Singapore · University of Washington
Diffusion Denoiser Achievable Analysis for Finite Blocklength Unsourced Random Access
Apr 10, 2026Yuming Han, Yuxin LongDiffusion-Based Denoising Diffusion Models
Texas A&M University, Department of ECE, College Station, TX 77843, USA · University of Leeds, Institute for Transport Studies, Leeds, LS2 9JT, UK
Polar Code Based Federated Learning: Convergence Analysis and Resource Allocation
Aug 14, 2026Han Xiao, Wei Kang, Nan LiuUnequal Error Protection Federated Learning
School of Information Science and Engineering, Southeast University, Nanjing 211189, China · National Mobile Communications Research Laboratory, Southeast University, Nanjing 211189, China

May 29, 2026J/K move · Enter open · S save

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

Ivan Lau, Daniel McMorrow, Kevin Jamieson, Jonathan Scarlett

National University of Singapore · University of Washington

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

Open paper AskPDF arXiv

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})

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