PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Recep Can Yavas

arXiv:2610.36818v1cs.ITcs.LGmath.IT

TL;DR

The VLF-Bandit problem requires decoding while the receiver learns and schedules among multiple AWGN channels with unknown noise variances. The paper develops two joint coding and channel-selection schemes and proves second-order achievability bounds; the VLF-Bandit bound has a smaller coefficient magnitude than VLSF-Bandit and improves on explore-then-commit for K≥2.

  • Problem

    VLF-Bandit couples decoding from adaptively collected observations with learning which of several unknown-noise AWGN channels should be used more often.

    Source: B. Motivation and the VLF-Bandit Problem · p. 3

  • Method

    The paper develops a single-phase Gaussian-codebook VLSF-Bandit scheme and a packetized Schalkwijk–Kailath VLF-Bandit scheme that jointly select channels and communicate.

    Source: D. Contributions · p. 4

  • Results

    Both bounds attain the first-order term NC⋆, and the VLF-Bandit bound has a smaller log N coefficient magnitude than VLSF-Bandit and improves on explore-then-commit for K≥2.

    Source: B. VLF-Bandit Scheme · pp. 11–12, §IX · p. 22

  • Takeaways & Limitations

    The VLF-Bandit design lets exploration packets carry message bits and uses the saved energy in the final packet, while its bound is strictly better than the explore-then-commit bound for K≥2.

    Source: D. Contributions · p. 4, §IX · p. 22

    A tight second-order converse remains open; it is unknown whether sufficiently low suboptimal-channel use must incur a Lai–Robbins-order exploration cost.

    Source: §IX · p. 22

Abstract

from arXiv · show

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

I. INTRODUCTION

The paper formulates VLF-Bandit coding as joint decoding and receiver-side channel scheduling when channel qualities are unknown. It develops two code classes and achievability bounds that combine variable-length coding, universal decoding, and channel exploration.

A. VLF Literature

  • For VLF codes, the cited finite-blocklength bounds give a lower bound NC(1−ϵ)−log N+O(1) and an upper bound NC on log M*VLF(N,ϵ).The lower bound is achieved by VLSF codes; Yavas and Tan improve its log N coefficient for VLF codes.Source: A. VLF Literature · pp. 1–2
  • Universal VLF results described here concern a single unknown channel; replacing known-channel information density with a universal score adds a 1/2 log N cost in the cited BSC and AWGN bounds.The paper extends the setting to several simultaneously available channels.Source: A. VLF Literature · p. 2

B. Motivation and the VLF-Bandit Problem

  • Receiver-side channel selection avoids letting the channel-index sequence itself carry message information, which could reach log K nats per channel use.The selection rule depends on common randomness and past selections and outputs, not directly on the message.Source: B. Motivation and the VLF-Bandit Problem · p. 2
  • The VLF-Bandit problem couples decoding from adaptively collected observations with scheduling that favors high-capacity channels; VLSF-Bandit fixes the codeword, while VLF-Bandit permits feedback-adaptive symbols.The setting combines tasks not jointly addressed by prior universal VLF, bandit, or channel-identification formulations.Source: B. Motivation and the VLF-Bandit Problem · p. 3, C. Multi-Armed Bandit Literature · pp. 3–4
  • A modular explore-then-commit baseline spends pilot observations on channel estimation without carrying message information, whereas joint schemes use channel observations to refine both channel knowledge and the message estimate.The baseline then sends a single-channel VLF code over the channel declared best.Source: B. Motivation and the VLF-Bandit Problem · p. 3

C. Multi-Armed Bandit Literature

  • Unlike a separate best-arm sensing phase, the receiver continues selecting channels while decoding, so suboptimal-channel use creates an opportunity cost measured against average decoding time.The scheduling problem is therefore closer to regret minimization than best-arm identification.Source: C. Multi-Armed Bandit Literature · p. 3

D. Contributions

  • The two schemes have second-order achievability bounds: VLSF-Bandit has a baseline-one plus exploration coefficient, while VLF-Bandit replaces that baseline with a universal-decoding term and a smaller exploration term.The VLF-Bandit coefficient is strictly smaller than the VLSF-Bandit coefficient.Source: D. Contributions · p. 4

A. Channel Models and Code Definitions

  • The model assumes K AWGN channels with unknown noise variances in a known interval; VLSF fixes the transmitted sequence before communication, whereas VLF permits adaptation to past outputs.Both code classes specify their rules without knowing the individual channel variances.Source: A. Channel Models and Code Definitions · pp. 5–6

B. Performance Metrics

This section describes the performance requirements and the VLSF-Bandit scheme. The scheme combines a Gaussian random codebook, a ratio-of-mixtures decoding score, and output-power-based channel selection.

B. Performance Metrics

  • One code must satisfy the error-probability and average-power constraints at every admissible noise-variance vector with a unique best channel, while average decoding time is evaluated at each instance.The best-channel uniqueness assumption implies positive capacity gaps and divergences for the other channels.Source: B. Performance Metrics · p. 6, C. Instance-Dependent Quantities · p. 6

1) Random Gaussian codebook: 

  • The common randomness supplies independent infinite-length Gaussian codewords, and the transmitter sends the message's time-t code symbol on the receiver-selected channel.Under the random-coding ensemble, the output variance is conditioned on the selected channel and prior observations.Source: 1) Random Gaussian codebook:  · p. 6

2) Per-channel statistics and exploration budget:

  • The channel-selection rule uses per-channel use counts and an exploration-budget function defined for a design horizon T≥K and integer s≥1.The available passage specifies the budget's domain but not its formula.Source: 2) Per-channel statistics and… · p. 6

3) Ratio-of-mixtures score:

  • For each channel, the decoder compares likelihood mixtures for candidate-codeword residuals and outputs, mixing over unknown noise variance with a log-uniform prior on an enlarged interval.If the prior were concentrated at the true variance, the per-channel score would equal accumulated information density.Source: 3) Ratio-of-mixtures score · p. 7
  • After round-robin initialization, the receiver selects the channel with the largest optimistic capacity estimate, applying kl-UCB++ to output power.The largest-capacity channel corresponds to the smallest output variance under the random-coding ensemble.Source: 3) Ratio-of-mixtures score · p. 7

B. VLSF-Bandit Scheme

C. VLF-Bandit Scheme

VLF-Bandit sends the message in packets using SK feedback transmission while both terminals learn channel noise precision from normalized outputs. Preliminary and exploration packets support channel comparison, and the final packet carries the remaining bits.

C. VLF-Bandit Scheme

  • The scheme sends successive message packets by SK feedback transmission, using normalized outputs to estimate noise precision within packets and compare channels across packets.Exploration packets carry message bits, and the final packet uses power saved during exploration.Source: C. VLF-Bandit Scheme · p. 8

1) Message packets:

2) Feedback transmission of a packet:

  • Within each packet, SK refinements use normalized outputs as noise samples; both terminals estimate precision, making the packet a universal version of SK.The normalized outputs within a packet are i.i.d. Gaussian samples with the selected channel’s noise variance.Source: 2) Feedback transmission of a packet · pp. 8–9

3) Initial observations and preliminary packet:

  • The receiver first takes zero-input observations on every channel, then sends a preliminary packet whose order-ψ² uses estimate its channel’s variance for later comparisons.The preliminary packet provides an accurate variance estimate of channel J0.Source: 3) Initial observations and… · p. 9

4) Exploration packets:

  • Exploration packets each carry ℓ0 bits; confidence intervals eliminate channels, and the receiver samples the active channel with the fewest retained observations until a stopping condition or cap.The exploration cap is ⌈ψ²⌉ channel uses, and a packet already started is completed even if it crosses the cap.Source: 4) Exploration packets · p. 10

5) Final packet and decoding:

  • The final packet uses the selected channel for all remaining bits, spreading exploration’s saved power over its initial refinements; decoded packet strings are concatenated for final decoding.Scheme parameters and channel selections use initial zero-input observations and normalized outputs from completed packets, known to both terminals through feedback.Source: 5) Final packet and decoding · p. 10

V. MAIN RESULTS

The main results give second-order achievability bounds for both VLSF-Bandit and VLF-Bandit, with both schemes attaining the optimal first-order term. The VLF-Bandit bound has a strictly smaller log N coefficient magnitude, and the numerical illustration shows higher rates than ETC at N = 2000 for K = 2.

A. VLSF-Bandit Scheme

  • For VLSF-Bandit, the log N coefficient magnitude combines a single-phase VLSF baseline with the time cost of suboptimal channel selections.The exploration cost weights each channel's capacity gap by the inverse divergence Dk,k*; kl-UCB++ attains the relevant pull-count bound.Source: A. VLSF-Bandit Scheme · p. 11

B. VLF-Bandit Scheme

  • For VLF-Bandit, the universal-decoding term comes from estimating noise precision in the final packet, with refinement losses accumulating to order log log M.For K = 1, the bound improves the log N coefficient magnitude from 1/2 + C*/C1,* in [17, Th. 5] to 1/(2v*^2).Source: B. VLF-Bandit Scheme · p. 11
  • Both bounds attain the optimal first-order term NC*/(1−ϵ), and VLF-Bandit has a strictly smaller log N coefficient magnitude than VLSF-Bandit.The VLF-Bandit coefficient has no single-phase baseline; its universal-decoding term replaces that baseline, and its exploration terms are smaller.Source: B. VLF-Bandit Scheme · pp. 11–12

C. Numerical Illustration

  • With variance interval [0.5, 2.5] and one channel of variance 1, the coefficient magnitudes are 1 for VLSF-Bandit and 0.125 for VLF-Bandit.For K = 2 and variances (1, 2), the respective magnitudes are approximately 4.043 and 0.754.Source: C. Numerical Illustration · p. 12
  • At N = 2000 with K = 2, VLF-Bandit achieves about 0.483 bits per channel use versus 0.179 for ETC.The illustration evaluates rates at ϵ = 10−3 and ϵ0 = 0.Source: C. Numerical Illustration · p. 12

VI. PROOF OF THE VLSF-BANDIT RESULTS

  • The VLSF-Bandit proof bounds error through wrong-message threshold crossings and stopping-time tails, then bounds expected time using information density, overshoot, and suboptimal-channel counts.It then applies the stop-at-time-zero strategy and expands the bound as M grows.Source: §VI · p. 12

A. Supporting Lemmas

  • The supporting lemmas include a fixed-horizon kl-UCB++ pull-count bound for suboptimal arms under bounded variance and a unique best arm.The stated expected pull bound depends on the KL divergence threshold and an additive term proportional to V K.Source: A. Supporting Lemmas · pp. 13–14

B. Wrong-Message Error Control

This proof controls errors by bounding wrong-message score crossings, then bounds decoding time using the true-message score and channel-selection pull counts.

C. True-Message Score

D. Output-Power kl-UCB++ Pull Counts

  • Output-power rewards are modeled as an exponential family so kl-UCB++ pull-count bounds can control uses of suboptimal channels.The algorithm uses negative squared outputs as rewards, with means determined by output variances.Source: D. Output-Power kl-UCB++ Pull Counts · pp. 14–15

1) Error probability bound:

  • A lemma bounds the probability that a wrong message’s score reaches a given level within a given number of uses by c0(M − 1)(1 + log T) exp{−γ} + c3 γ2 log3 γ.Source: B. Wrong-Message Error Control · p. 14, 1) Error probability bound · p. 15
  • The error analysis shows that the selected threshold makes the error-bound remainder vanish as γ grows, uniformly over the admissible variance instances.For sufficiently large M, the error and power conditions hold across the prescribed variance interval.Source: 1) Error probability bound · p. 15

2) Average decoding time bound:

  • The decoding-time bound combines the information accumulated by the true-message stopping time with the expected use counts of suboptimal channels.The proof bounds the stopped information by the true-message score lemma and controls each channel count up to the design horizon.Source: 2) Average decoding time bound · p. 15

3) Power constraint: 

The proof verifies the VLSF scheme’s power and second-order bounds, then establishes packet-length and normalized-output properties used for the VLF-Bandit result.

3) Power constraint: 

  • The Gaussian-input VLSF scheme meets its power constraint with equality, and the bound holds throughout the prescribed variance interval.The proof conditions on the transmission history to show each input has distribution N(0, 1).Source: 3) Power constraint:  · p. 16

4) Second-order expansion:

  • The VLSF second-order expansion is obtained by translating the decoding-time bound into a bound on log M with a log N term.The passage states that the remainder is O((log N) 3 4 ).Source: 4) Second-order expansion · p. 16

VII. PROOF OF THE VLF-BANDIT RESULTS

  • The VLF-Bandit proof derives error and energy bounds from the conditional Gaussian law of normalized packet outputs, then combines packet durations and channel-selection bounds.Figure 5 maps dependencies among the proof steps and subsections.Source: §VII · p. 16, Figure 5 · p. 16

A. Packet Lengths

  • Each packet transmits its first nine refinements, and the packet-length analysis bounds durations for preliminary, exploration, and final packets.The final packet has a positive integer number of bits.Source: A. Packet Lengths · p. 17

B. Normalized Outputs and Decoding Error

  • Conditioned on the packet’s retained history and message, normalized outputs and the normalized error have independent Gaussian laws; packet history is independent of the message.The packet message is uniform given the retained history, supporting the packet error analysis.Source: B. Normalized Outputs and Decoding Error · p. 18

C. Power Constraint

The proof bounds packet energy and duration, including the cost of estimating noise precision, and then controls channel exploration for Theorem 2.

C. Power Constraint

  • The packet-energy lemma bounds each transmitted packet’s expected energy by its nominal allocation.The proof sums these bounds while accounting for the initial uses that carry no energy.Source: C. Power Constraint · p. 18

D. Expected Packet Duration

  • Packet duration is compared with the duration under known precision, and accumulated precision-estimation losses produce the universal-decoding term.The proof sums the refinement-level loss bounds before converting the capacity-sum bound into packet durations.Source: D. Expected Packet Duration · p. 19
  • The expected-duration analysis bounds the stopped sum of refinement losses and applies the resulting packet-duration lemma to preliminary and exploration packets.The stopping event depends on earlier normalized outputs, which also enter the precision estimate.Source: D. Expected Packet Duration · p. 19

E. Channel Selection

  • The channel-selection lemma supplies bounds on exploration uses, powers, and channel-selection errors for the final decoding-time analysis.Source: E. Channel Selection · p. 20

F. Proof of Theorem 2

The proof combines packet payloads, durations, and channel-selection costs to establish Theorem 2, then compares its second-order cost with explore-then-commit.

F. Proof of Theorem 2

  • The proof combines packet-duration bounds and exploration costs, applies stop-at-time-zero randomization, and derives the stated second-order expansion for Theorem 2.The resulting bound is established throughout the prescribed variance interval.Source: F. Proof of Theorem 2 · pp. 20–21

VIII. COMPARISON WITH THE EXPLORE-THEN-COMMIT STRATEGY

  • Explore-then-commit spends zero-input pilot observations identifying a channel before sending the message in one packet over the declared channel.The pilot observations identify the channel but do not carry message bits.Source: §VIII · pp. 21–22
  • The joint scheme has a strictly smaller second-order cost than explore-then-commit for every instance with K ≥2.The comparison attributes the gap partly to explore-then-commit probing the best channel with zero-input observations, while joint exploration carries message bits.Source: §VIII · p. 22
  • The achievability bounds are ρETC ≈3.362 and ρjoint ≈0.754, with a difference of about 2.608.Source: §VIII · p. 22

IX. CONCLUSION

  • A tight second-order converse remains open, including whether sufficiently infrequent use of suboptimal channels must incur a Lai–Robbins-order exploration cost.The cited change-of-measure arguments constrain deterministic-horizon bandit policies and do not directly apply to codes.Source: §IX · p. 22

APPENDIX A PROOF OF THE VLSF-BANDIT LEMMAS

The proofs control decoding and channel-selection behavior using likelihood-mixture comparisons and bounds on their accumulated redundancy. For the coefficient comparison at K = 2, the shaded region represents the difference between the explore-then-commit and joint coefficients.

I. Proof of Lemma 4

  • For K = 2 and unit average power, Fig. 6 compares second-order coefficients, with its shaded region showing ρ_ETC − ρ_joint over σ²₂ ∈ [1.5, 2.5].The figure caption identifies the setting; the accompanying text defines the shaded difference.Source: §I · p. 23, Figure 6 · p. 23
  • The likelihood ratio between the true output law and the auxiliary mixture law is a martingale under the auxiliary law, supporting a threshold-crossing bound for false candidate messages.The proof applies a union bound over incorrect messages after expressing the stopping event as a maximum of candidate scores.Source: §I · pp. 23–24

II. Proof of (79)

  • The residual-mixture and output-mixture redundancies each have leading terms of about one-half log j, which cancel in their difference up to fluctuations and constants.The proof bounds the first redundancy above and the second below before controlling the remaining fluctuation.Source: §II · p. 24

III. Proof of (80)

These proofs establish control of the score threshold, characterize the output-power reward distribution, and bound the stopping time. The resulting stopping-time tail bounds are polynomial in the threshold parameter, up to logarithmic factors.

III. Proof of (80)

  • The score increments are log ratios of predictive residual and output densities, and their integrable bounds establish the threshold-crossing bound (80).The proof bounds the mean excess of the score increments before applying Lemma 2.Source: §III · p. 26

IV. Proof of Lemma 6

  • The reward −Y² belongs to a one-parameter canonical exponential family, whose mean, variance, and divergences follow from its cumulant.Conditioned on selecting channel k, Y has distribution N(0, v_k).Source: §IV · pp. 26–27

V. Proof of Lemma 7

  • P[τ_W > T] is bounded by c3 γ² log³ γ in (207) and by c3 γ log γ in (208).The bounds are stated for the stopping-time tail in the proof of Lemma 7.Source: §V · p. 27

VI. Proof of Lemma 8

The proof bounds channel-selection regret over a finite horizon and establishes that early refinements reserve energy to cover later estimation bias. The latter result relies on the first nine refinements using a conservative variance estimate.

VI. Proof of Lemma 8

  • The channel-selection bound is obtained by applying the bandit regret lemma at horizon T with projected means and restricted indices.The proof uses δ = (log T)^−1/4 and relates the resulting divergence to D_k,k⋆.Source: §VI · p. 28

I. Proof of Lemma 10

  • The first nine refinements reserve half their nominal energy, and that reserve covers the bias of later estimates in the proof of (116).For these refinements, the estimate uses η_min, which is at most 1/(2s).Source: §I · pp. 28–29

II. Proof of (122) and (123)

The bounds are analyzed conditional on a transmitted packet, where normalized outputs provide repeated noise samples. The proof controls precision-estimation error and compares estimated with true-precision reductions in the stopped sums.

II. Proof of (122) and (123)

  • Conditioned on the transmitted packet and its initial information, the normalized outputs are i.i.d. N(0, s) at every deterministic index.The constants in the subsequent bounds depend only on the known variance interval.Source: §II · p. 29

1) Moments of the precision estimate:

  • For m ≥ 9, projection of the unprojected precision estimate cannot increase its distance to 1/s.The proof first bounds moments of the unprojected estimate before applying this projection property.Source: 1) Moments of the precision estimate · p. 29

2) Proof of (122):

  • The proof of (122) uses a Taylor expansion at η = 1/s and bounds the quadratic and cubic terms using the precision-estimate moment bounds.It takes expectations of the expansion and uses q ≤ 1.Source: 2) Proof of (122) · p. 29

3) Proof of (123):

  • The proof of (123) compares the stopped sum with a deterministic-time sum at which the true-precision reduction crosses the threshold.It bounds how often the estimated- and true-precision stopping indicators differ, then controls the difference between the sums.Source: 3) Proof of (123) · p. 30

III. Proof of Lemma 11

The proof separates preliminary and exploration packets from the final packet, then establishes variance-estimation guarantees used in the VLF-Bandit bound.

2) Final packet, proof of (126):

IV. Proof of Lemma 12

  • For K = 1, the lemma holds directly; for K ≥ 2, the proof first establishes high-probability accuracy of variance estimates before deriving the remaining bounds.The argument uses retained zero-input outputs and normalized packet outputs as variance observations.Source: §IV · p. 31, 1) Variance estimates · p. 31

1) Variance estimates:

  • On the simultaneous confidence event, the best channel remains active throughout exploration, and any singleton active set contains it.The proof represents retained outputs as independent channel-specific reward stacks and uses their empirical second moments to form variance estimates.Source: 1) Variance estimates · pp. 31–32

2) Preliminary channel, proof of (132):

The preliminary-channel argument uses variance estimates to keep the best channel out of exploration and limit exploration of suboptimal channels; the final-channel argument bounds the chance of an incorrect choice at the exploration cap.

2) Preliminary channel, proof of (132):

  • On E ∩ Vδ, the best channel is never explored, and each suboptimal channel is explored only until its observation count reaches nk.The elimination rule removes a suboptimal channel once its confidence interval lies above the best channel’s interval.Source: 2) Preliminary channel, proof of (132) · p. 32
  • The minimum-count rule gives Tk⋆ = 0, while the total number of exploration uses is O(ψ).The proof bounds the suboptimal-channel counts and the additional observations from their last packets.Source: 2) Preliminary channel, proof of (132) · p. 32

4) Final channel, proof of (133):

  • On E, an incorrect final channel can occur only if exploration reaches its cap with at least two active channels.At the cap, sufficiently accurate variance estimates force elimination of all suboptimal active channels, so the exceptional probability is o(1).Source: 4) Final channel, proof of (133) · p. 33

Related papers

Loading 2610.36818v1…