PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaling Bayesian Bandit Encoding with Shared Learning

Bhaskar Krishnamachari

arXiv:2609.06293v1cs.ITmath.IT

TL;DR

The paper studies how packet feedback can guide selection among code and decoder configurations as channel conditions change. It extends Bayesian bandit encoding with offline-learned shared performance patterns and online updates, then reports lower regret from sharing on a six-arm shortlist and faster criterion attainment after channel changes. The tested utility-optimal arms nevertheless retain substantial packet loss.

  • Problem

    Selecting effective error protection and decoding effort as channel conditions change is difficult because code performance depends on error arrangement as well as channel conditions.

    Source: §1 · p. 1

  • Method

    The selector learns shared performance patterns from training simulations and updates them online from selected-arm feedback while decoder noise models remain fixed.

    Source: §1 · pp. 1–2

  • Results

    33.5% lower regret for latent than independent learning on the same six-arm shortlist; after channel changes, pruned latent met the criterion in 88.5% of events by 2,000 packets versus 54.2% for pruned independent learning.

    Source: §4 · p. 6, §5 · p. 7

  • Takeaways & Limitations

    The results support combining sharing and pruning for configuration selection, while the fixed training-selected configuration matches the shared learner searching the full catalog.

    Source: §4 · p. 6, §6 · p. 8

    Utility-optimal arms have BLER from 7.9% to 34.9%, so efficient selection in this catalog still leaves substantial packet loss.

    Source: §4 · p. 6

Abstract

from arXiv · show

A communication system must choose error protection and decoding effort as channel conditions change. A Bayesian bandit encoder (BBE) uses receiver feedback to learn which transmission configuration to select. We study a receiver that decodes by guessing error patterns, using Guessing Random Additive Noise Decoding (GRAND). We extend BBE's selection component to 1,008 code and decoder configurations by learning shared performance patterns offline and updating their weights online. Decoder noise models remain fixed. On a six-configuration training-selected shortlist, sharing reduces accumulated utility loss by 33.5% relative to independent learning. A fixed training-selected configuration matches the shared learner that searches the full catalog. After channel changes, the pruned shared learner first meets a near-optimal selection criterion in 88.5% of events by 2,000 packets, compared with 54.2% for pruned independent learning with the same discounting. The results support combining sharing and pruning for configuration selection, although packet losses remain high for the tested codes under severe noise.

1 Introduction

The paper extends Bayesian bandit encoding to select among many complete code and decoder configurations using receiver feedback. It learns shared performance patterns from training data while keeping decoder noise models fixed during online selection.

1 Introduction

  • GRAND tests proposed error patterns by reversing their flips and checking whether the result is a valid encoded packet; its query order depends on the noise model.A query limit bounds decoding effort, while interleaving changes which code positions a burst affects.Source: §1 · p. 1
  • The starting architecture couples Bayesian interference estimation with decoder adaptation and selection between a random linear code and its interleaved version.Its learned interference parameters feed an HMM that infers bit-flip probabilities used to reorder GRAND queries.Source: §1 · p. 1
  • The selector treats each code, interleaver, noise ordering, and query limit combination as an arm, and rewards information delivery while charging for queries.Decoder noise models are fitted offline and held fixed, isolating configuration selection within the broader BBE architecture.Source: §1 · p. 1
  • Unlike independent learning, the latent model uses a few shared variables so one selected-arm observation updates predictions for other arms.Training simulations provide the performance matrix from which shared patterns are learned.Source: §1 · p. 1
  • The study evaluates shared learning and training-based pruning across 1,008 configurations, including comparisons with fixed-arm baselines and adaptation after channel changes.The empirical study examines a telemetry representation, a GRAND configuration catalog, and their combination with pruning.Source: §1 · p. 2

2 Related Work

Related work spans noise-aware GRAND variants, shared learning for link adaptation, and low-rank models, pruning, and discounting for changing channels. The paper distinguishes its complete GRAND configuration selection and learned performance relationships from these prior approaches.

2.1 Noise-aware decoding

  • GRAND and GRANDAB use likelihood-ordered noise guesses, while GRAND Markov Order exploits correlated errors and can favor keeping bursts over interleaving in suitable regimes.These results motivate selecting both error-pattern ordering and interleaver.Source: §2.1 · p. 2
  • Soft GRAND, ORBGRAND, and GRAND methods for confidence estimation and iterative decoding add signal reliability or richer decoding feedback beyond the hard-decision experiments here.The passage presents these methods as potential ways to improve reliability and enrich feedback.Source: §2.1 · p. 2
  • The context-tree weighting method inspires a practical backoff ordering, while Miyamoto and Yang [9] study decoding with an unknown noise law rather than learning relative configuration utility.Shorter histories receive more weight when data are scarce.Source: §2.1 · p. 2

2.2 Sharing observations in link adaptation

  • Prior link-adaptation work selects among modulation and coding schemes using shared channel estimates, whereas this study learns from decoder telemetry and selects complete code–interleaver–GRAND configurations.Combes et al. also formulate transmission-rate selection as a bandit problem with structure among choices.Source: §2.2 · p. 2
  • Joint-Thompson sampling [12] shares through a prior that preserves success-probability ordering, while this work learns relationships from a performance matrix without imposing one quality axis.This accommodates arms whose relative strengths depend on error arrangement as well as error rate.Source: §2.2 · p. 2

2.3 Low-rank models, pruning, and changing channels

  • Low-rank reward models [13, 14] motivate shared factors, and linear Thompson sampling supplies online inference; here arm features are learned offline and shared performance variables online.Source: §2.3 · p. 3
  • Greedy set cover builds a training-based shortlist, while discounting [17] is used to track channel changes under an approximate training-derived performance model.Pruning reduces the choices; latent learning shares evidence among those choices.Source: §2.3 · p. 3

3 What the Learner Observes and Optimizes

The learner scores selected-arm packet feedback as utility, then uses an offline performance matrix to share information among configurations online. Training-based pruning and fixed-arm baselines provide alternative ways to restrict or avoid online selection.

3.1 Packet feedback and utility

  • Packet utility credits the transmitted information fraction for successful recovery and charges for queries; its mean also reflects BLER and expected query count.A lower-rate code must recover enough additional packets to compensate for its redundancy, and average utility is not aggregate delivered bits divided by transmitted bits.Source: §3.1 · p. 3
  • The learner observes telemetry only for the selected arm, while success is simulator ground truth rather than proof that the accepted codeword was transmitted.The feedback represents ideal error detection with no overhead.Source: §3.1 · p. 3

3.2 How the performance matrix enables sharing

  • Training performance is organized as an arm-by-channel telemetry matrix, standardized by measurement type, with shared patterns fit by singular-value decomposition and rank chosen using withheld-data prediction error.The shared variables need not correspond directly to bit error probability, burst length, or a training channel.Source: §3.2 · p. 3
  • Each arm has a training baseline and a feature matrix mapping shared variables to predicted telemetry, so updating the shared variables changes predictions for every arm.The Gaussian observation model uses arm-specific covariance estimated from within-packet telemetry; discounting exponentially downweights older observations while retaining the prior.Source: §3.2 · pp. 3–4
  • Success, abandonment, and normalized query count inform inference, but utility weights give abandonment no separate penalty.The shared Thompson sampler predicts each available arm's telemetry and utility, clips the sampled utility to arm-specific bounds, and selects a maximizing arm.Source: §3.2 · p. 4

3.3 Choosing a shortlist or a fixed arm

  • Greedy pruning retains arms whose training mean utility is within tolerance of the best across conditions, adding the arm that covers the most still-uncovered conditions.Pruned independent and latent learners use the same shortlist and retain their original priors.Source: §3.3 · p. 4
  • The diverse-training static baseline chooses the highest average-utility arm across equally weighted training conditions, while the severe-IID baseline uses one severe IID channel and is test-informed.Learners, priors, shortlist, and diverse-training static choice use training data only.Source: §3.3 · p. 4

4 Experiments I: Learning on a Fixed Channel

The experiments compare shared and independent learning across a 1,008-configuration catalog and training-selected shortlists under fixed-channel conditions. Sharing lowers regret on the six-arm shortlist, while a diverse-training static choice matches the full shared learner; utility-optimal choices can still have substantial BLER.

4 Experiments I: Learning on a Fixed Channel

  • The utility design sets κ = 0.016384, making maximum-budget decoding cost about 1.64 percentage points of rate-weighted success.This is a design choice, not an empirically estimated channel parameter; fixed-channel trials use γ = 1.Source: §4 · p. 5
  • The 1,008-arm catalog combines 16 short codes, four interleavers, four GRAND orderings, and four query limits, with duplicates removed.Codes carry 16 information bits in 24, 32, 40, or 48 transmitted bits; noise models are fitted on training noise and held fixed in testing.Source: §4 · p. 5
  • Trials compare methods over 128 matched runs of 600 packets, balanced across 16 test conditions, using feedback only from the selected arm.The 24 training conditions span nominal bit error probabilities 0.015–0.12; the 16 test conditions use new parameters at 0.035 and 0.10.Source: §4 · p. 5
  • At 1,008 arms, latent full regret was 6.85 versus 22.41 for independent full and 6.81 for the static baseline.Figure 1 reports cumulative regret over 600 packets, averaged over 128 trials.Source: §4 · p. 6, Figure 1 · p. 6
  • On the six-arm shortlist, sharing reduced regret by 33.5%: latent learning had 4.24 versus 6.37 for independent learning.The 95% bootstrap interval was 8.3% to 55.7%.Source: §4 · p. 6
  • The severe-IID static choice had regret 61.29 at 1,008 arms and average observed utility about 0.395, versus about 0.486 for diverse-training static.Its regret rose when the catalog added a rate-1/2 Reed–Muller configuration that won the severe-IID comparison, sacrificing utility on other channels.Source: §4 · p. 6
  • The rank-two telemetry model had 0.0247 root-mean-square utility prediction error on withheld training measurements.A separate utility-matrix diagnostic found ranks 3, 4, and 7 explained 90%, 95%, and 99% of squared variation, respectively.Source: §4 · p. 6
  • Reference-optimal arms had BLER from 7.9% to 34.9%, so efficient selection still left substantial packet loss.The reported training-bank and analysis timings are partial and are not receiver latencies or an end-to-end training benchmark.Source: §4 · p. 6

5 Experiments II: Learning after Channel Changes

The experiments test how learners adapt after channel changes, using discounted updates without change notifications or resets. The pruned latent learner attains the near-optimal criterion more often and sooner than pruned independent learning, though difficult destinations remain.

Experimental setup

  • The 12 ordered scenarios cover changes in error probability, error arrangement, and channel families absent from training; each transition is followed for up to 2,000 packets.Across four repetitions, the study includes 96 transitions; all learners discount past observations by 0.99 without change notifications or resets.Source: §5 · p. 7

Measures

  • Figure 2(a) reports first attainment, while panel (b) groups utility shortfall by destination channel and visit role.Panel (b) averages the first 600 packets of each visit; the figure caption describes bootstrap intervals and notes that missing markers indicate untested roles.Source: §5 · p. 7, Figure 2 · p. 7

Results

  • 88.5% of changes met the criterion within 2,000 packets for the pruned latent learner, versus 70.8% for full latent and 54.2% for pruned independent learning.Without discounting, the pruned latent learner met the criterion in 62.5% of changes.Source: §5 · p. 7
  • The pruned latent learner reached the criterion in half of changes by packet 136, versus packet 488 for pruned independent learning.Over packets 1,501–2,000, their mean fractions of near-optimal choices were 83.3% and 59.4%, respectively.Source: §5 · p. 8, Table 2 · p. 8
  • For severe isolated flips, utility shortfall was 8.5% on visits to B and 8.9% on returns to A, versus 5.1% on initial visits.The comparison covers the first 600 packets of each visit; different source channels may precede visits to B and returns to A, so matched histories are needed to isolate a return-specific penalty.Source: §5 · p. 8

6 Conclusion and Limitations

Latent sharing extends BBE selection to a large catalog and improves selection on a shortlist. The study also identifies limits in packet loss and offline measurement requirements, and proposes joint learning as future work.

Conclusion

  • Latent sharing extends BBE’s selector to a large catalog and reduces regret by 33.5% against independent learning on the same six-arm shortlist.The offline model uses measurements of every configuration, while tested utility-optimal arms still incur substantial packet loss.Source: §6 · p. 8

Limitations and future work

  • Decoder noise models remain fixed, and the tested codes still incur substantial packet loss under severe noise.Future work would jointly learn the channel, adapt the decoder, and select code–decoder configurations.Source: §6 · p. 8

AI Use Statement

The author reports using ChatGPT and Codex for code and simulations, algorithm design, and paper preparation, and accepts responsibility for the paper’s contents.

AI use statement

  • The author reports using ChatGPT and Codex for code, simulations, algorithm design, writing, editing, proofreading, and formatting.The human author accepts full responsibility for the work’s contents.Source: AI Use Statement · p. 8

Appendices

The appendix describes fitting a shared representation from centered and scaled training measurements. Missing entries are iteratively completed with low-rank SVD fits, and the resulting coordinates are centered for deployment.

Fitting the shared representation

  • Measurements are centered by arm and scaled by their population standard deviation, with a 0.03 minimum scale.When an arm has no observed channels, its offset uses the overall measurement mean; constant measurements remain well defined.Source: A Fitting the shared representation · p. 10
  • Centered measurements are arranged in a 3A × Z matrix, with rows indexed by arm and measurement and columns by channel.The three measurements are success, abandonment, and queries divided by 16,384.Source: A Fitting the shared representation · p. 10
  • Missing entries start at zero and are replaced by fitted values over 20 rank-d SVD completion iterations, while observed entries remain unchanged.A final SVD follows completion; no completion is needed for a fully observed matrix.Source: A Fitting the shared representation · p. 10
  • The final decomposition supplies shared features and training coordinates; centering the coordinates preserves fitted means and yields parameters in original feedback units.The deployment prior is N(0, Id), describing shared performance variation rather than uncertainty in fitted code or decoder parameters.Source: A Fitting the shared representation · p. 10

A.1 Validation and rank choice

The shared-pattern rank is selected using held-out arm–channel prediction error. Per-arm telemetry covariance is estimated from training data and incorporated into Gaussian updates that discount older evidence.

A.1 Validation and rank choice

  • 0.02470, 0.04313, 0.06608, and 0.08522 mean errors for d=2, 4, 6, and 8 select d=2 under the one-standard-error rule.The smaller catalog experiments use subsets of the full-catalog model, not independently refitted representations.Source: §A.1 · p. 10
  • Residual-utility diagnostic ranks describe cumulative squared singular values of the centered 1,008 × 24 matrix and do not set the telemetry model’s rank.The diagnostic applies SVD to the residual utility matrix formed from training means.Source: §A.1 · p. 10

A.2 Observation covariance and inference

  • Each arm’s 3×3 telemetry covariance averages unbiased sample covariances across 24 training channels and floors eigenvalues at 10^-4.The covariance is fixed across online channel conditions; its components may be correlated.Source: §A.2 · pp. 10–11
  • Independent learning assigns each arm a Gaussian prior; its discounted update retains the identity prior and leaves zero-variance directions fixed.Only the selected arm’s count and information vector receive the packet update.Source: §A.2 · p. 11

B Codes and selectable configurations

The catalog comprises short binary linear codes carrying 16 information bits, constructed from several code families and screened using sampled message weights.

B Codes and selectable configurations

  • All listed constructions are short representative binary linear codes with k=16, and randomized constructions are fixed before channel evaluation.Table 3 summarizes the codes; its final column counts constant-zero transmitted positions.Source: B Codes and selectable configurations · p. 11, Table 3 · p. 11
  • Polar candidates select 16 transform rows using recursive reliability values, while Reed–Muller variants select 16 monomials by degree and then lexicographic order.For N=32, the selected monomials form the second-order Reed–Muller code; for N=64, they form a 16-dimensional subcode of it.Source: B Codes and selectable configurations · pp. 11–12
  • Random-linear candidates use generators [I16 P], while LDPC candidates use retained full-row-rank parity-check matrices and their binary nullspaces.The random-linear construction considers eight generators; the LDPC procedure tries up to 160 matrices and retains up to eight.Source: B Codes and selectable configurations · p. 12
  • Candidates are screened by the minimum weight among 4,096 sampled nonzero messages and generator rows, not by a minimum-distance calculation.The highest score wins, with the earliest candidate breaking ties.Source: B Codes and selectable configurations · p. 12

B.1 Interleavers, budgets, and duplicate removal

The catalog combines code, interleaver, decoder ordering, and query-budget choices, with duplicate configurations removed. Frozen noise orderings and a defined training/test channel grid provide the evaluation setting.

B.1 Interleavers, budgets, and duplicate removal

  • Removing equivalent length-32 Reed–Muller configurations reduces 1,024 nominal configurations to 1,008 arms in 252 physical groups.The four permutations act within a codeword, and query limits are 64, 512, 4,096, and 16,384.Source: §B.1 · p. 12
  • The six retained configurations form a training-selected shortlist, and excluded code families are not thereby shown to be intrinsically inferior.Pruning seeks coverage of training conditions within absolute utility 0.01 of their best arm.Source: Table 4 · p. 12, §B.1 · p. 12

C Frozen GRAND noise orderings

  • The four GRAND noise orderings are fitted on training sequences and held fixed; their exact fitted-model orderings may be mismatched to the actual channel.The orderings include IID, Markov, context backoff, and run length; each length–ordering list reaches 16,384 patterns.Source: C Frozen GRAND noise orderings · p. 13

D Channel processes and parameter grids

E Packet sampling and evaluation

Evaluation reuses packet banks across configurations while exposing each learner only to its selected arm’s feedback. The reported offline timings omit some setup stages, and validation checks test information boundaries and candidate ordering.

E Packet sampling and evaluation

  • Packet outcomes are correlated across arms, but each online decision receives only the selected arm’s feedback; methods share packet indices for matched comparisons.The changing-channel replay samples separate A, B, and return-to-A collections.Source: E Packet sampling and evaluation · pp. 14–15
  • Attainment windows restart at each channel change, and unattained events remain in the denominator as right-censored at 2,000 packets.The 90th percentile exceeds the observation horizon for all four reported policies; sustained performance averages the near-optimal indicator over the final 500 packets.Source: E Packet sampling and evaluation · p. 15

E.1 Recorded offline cost

  • 10.61, 7.86, 15.95, and 67.77 seconds were recorded for training, validation, test-replay, and test-reference processing, respectively, excluding setup stages.No complete first-run wall-clock time or peak-memory measurement is recorded; these timings do not measure sequential GRAND latency or hardware throughput.Source: §E.1 · p. 15

E.2 Validation checks

  • Changing evaluator-only reference values or unselected packet outcomes left learner choices unchanged, and small-block candidate ordering was checked against exhaustive likelihood sorting.These checks test posterior updates and information boundaries.Source: §E.2 · p. 15

Related papers

Loading 2609.06293v1…