CS Paper Radar

Scaling Bayesian Bandit Encoding with Shared Learning

Bhaskar Krishnamachari

cs.IT ·submitted 2026-09-05 23:03 UTC · v1

Abstract

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.

Comment
15 pages, 2 figures, 5 tables; includes appendices

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT cs.LG ·2026-10-27 ·Recep Can Yavas
theory similarity 0.69
Abstract · 34 pages, submitted to Transactions on Information Theory

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

0.20

Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

cs.LG cs.CLstat.ML ·2026-09-22 ·Qian Xie, Yueli He, Nairen Cao
publishedbenchmark similarity 0.64
Abstract · Spotlight at ICML 2026 Workshop on Decision-Making from Offline Datasets to Online Adaptation: Black-Box Optimization to Reinforcement Learn…

Exhaustively evaluating every candidate LLM configuration on every benchmark item to identify a high-performing one is costly. We formulate configuration selection as a cost-aware Bayesian bandit problem and propose GittinsEval, which draws on the Bayesian-optimal Gittins policy to determine which configuration to evaluate next and when to stop. We extend the policy with an anytime recommendation rule over both fully and partially evaluated configurations, using an LCB-style score to account for posterior uncertainty. GittinsEval is computationally efficient, requiring only lightweight online updates after offline precomputation. Across GSM8K, PIQA, AlpacaEval, and MMLU response matrices, GittinsEval is consistently competitive, with particularly strong gains over configuration-level Bayesian optimization on large-example benchmarks and over cost-unaware bandit baselines on large-candidate tasks. Crucially, GittinsEval often attains near-zero simple regret using only 1% to 2% of the exhaustive-evaluation cost; it also offers an adaptive stopping rule that typically triggers at 1% to 10%.

0.51

An Efficient Synchronization Scheme for Distributed Bandits

cs.IT ·2026-11-06 ·Raymond Zhang, Henrique Miyamoto, Richard Combes, Sheng Yang
publishedtheory similarity 0.63
Abstract · Accepted at IEEE ISIT2026. 3 Figures, 6 pages. Theorem 7 redrawn

We study the problem of synchronizing two players in a \emph{distributed multi-armed bandit} setting. The probability of \emph{synchronization error} is analyzed by recasting synchronization as a \emph{communication problem}. Using a well-designed random coding ensemble, we derive error exponents for the maximum-likelihood decoder. We then introduce a \emph{universal decoder} that achieves the same error exponents as the optimal decoder. Finally, applying these results to distributed multi-armed bandits, we show an upper bound on the regret of our synchronization scheme.

0.56

Detection Augmented Learning In Non-Stationary Bandit Environments

cs.LG stat.ML ·2026-10-19 ·Argyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose, Venugopal V. Veeravalli
similarity 0.62
Abstract · 36 pages, 1 table, 5 figures, extension of https://arxiv.org/abs/2501.19401

We study the problem of non-stationary bandits without knowledge of the environmental changes. We propose Detection Augmented Learning (DAL) a black-box paradigm that comprises three modular components: a bandit algorithm, a change detector, and a forced exploration schedule. This modular design enables its applicability across a broad spectrum of bandit problems, from classical to highly structured settings. First, we provide theoretical insights into DAL's strong empirical performance: a single regret bound shows that DAL transfers the regret of its stationary input to the piecewise stationary setting, attaining or improving the best known bounds in every setting considered. We further identify conditions under which DAL performs well in drifting environments. Then, we showcase DAL's practical performance and versatility through extensive experimentation in which DAL consistently surpasses all state-of-the-art methods, both prior-free and prior-based, across diverse non-stationary scenarios in nine bandit settings. Finally, we investigate the effectiveness of the forced exploration and show that a bandit-driven strategy improves performance and shortens detection delay.

0.24

Online Learning with LLM Experts from Limited Feedback

cs.LG stat.ML ·2026-09-05 ·Wang Wei, Soumyabrata Pal, Koyel Mukherjee, Franck Dernoncourt, Ryan A. Rossi +2 more
similarity 0.62
Abstract · 21 pages, 4 figures

We study adaptive routing of prompts to large language model (LLM) experts to maximize response quality in an online setting with limited feedback. We formulate it as a bandit problem with $K$ actions that represent experts and $d$ features that encode prompts, over a horizon of $T$ rounds. We propose algorithms that strategically select and observe rewards to minimize regret. In the full-information setting, we achieve a regret of $\tilde{O}(d T / \sqrt{m})$, while in the bandit setting we achieve $\tilde{O}(d T \sqrt{K / m})$, where $m \ll T$ is a budget on feedback. Our experiments show that we efficiently learn high-quality routing strategies across diverse LLMs from limited feedback.

0.32

Can Bandits Learn to Share a Channel? Distributed Multi-Armed Bandits for Slotted ALOHA

cs.NI ·2026-11-18 ·Kamil Szczech, Maksymilian Wojnar, Krzysztof Rusek, Katarzyna Kosek-Szott, Szymon Szott
similarity 0.61
Abstract

Slotted ALOHA networks constitute a playground for research on machine learning (ML)-based channel access schemes. We consider ML agents deployed in such networks and operating under severe constraints: fully distributed (independent operation), fully online (no pre-training), aperiodic (no fixed schedule), and with no explicit coordination (no signaling). We ask whether a multi-armed bandit (MAB), a minimal reinforcement learning agent, can learn the optimal policy for a capture-free slotted ALOHA system. We evaluate several MAB algorithms on aggregate network throughput and per-node fairness. Our best-performing agent is based on a Softmax bandit, which we call SALSA (Softmax ALOHA Learning for Shared Access). SALSA learns a per-node transmission policy close to optimal, with throughput near the theoretical maximum for fair random access. We achieve performance comparable to a competing state-of-the-art solution, but without requiring a priori knowledge of the network size.

0.11

Dynamic Minimax Regret Optimization for Robust LLM Post-Training

cs.LG ·2026-10-05 ·Chengbo Zang, Haoyu Dong, Mehmet Kerem Turkcan, Gil Zussman, Zoran Kostic +1 more
theory similarity 0.61
Abstract

Modern LLM training increasingly relies on heterogeneous data sources spanning different domains, tasks, preference distributions, and difficulty levels. We study dynamic minimax regret for group-distributionally robust LLM post-training under instantaneous mini-batch-only bandit feedback. The framework views the training as a two-player sampler-optimizer process: a sampler adaptively selects among data sources using bandit feedback, while an optimizer updates the model parameters using stochastic gradients from the selected source. We focus on the practically restrictive setting where source losses evolve with model training but historical data are not re-evaluated, requiring the sampler to track instantaneous worst-sources from stale partial feedback. We propose DUCB-OGD, a simple and scalable algorithm that couples a Discounted Upper-Confidence-Bound sampler with an Online Gradient Descent optimizer. The sampler maintains exponential moving average loss estimates and confidence radii based on discounted effective sample sizes, avoiding costly re-evaluation of past data or intrusive changes to standard training pipelines. For $K$ data sources and $T$ training steps, we prove that DUCB-OGD achieves a dynamic minimax regret of $\tilde{O}(K^{1/4}T^{3/4})$, which is optimal up to logarithmic factors for the undiscounted objective under our feedback model. Extensive experiments across supervised fine-tuning, preference optimization, and reinforcement learning show that DUCB-OGD integrates seamlessly into modern LLM training pipelines and improves worst-group robustness with negligible computational overhead compared with standard sampling baselines.

0.24

Pay to Learn, Share to Earn: Incentivized Federated Multi-Player Bandits

cs.LG ·2026-10-05 ·Pavamana K J, Chandramani Singh
hot direction similarity 0.61
Abstract

Federated multi-player multi-armed bandit problems model collaborative sequential decision-making where multiple players interact with a common bandit environment and share information through a central server to accelerate learning. Existing federated bandit frameworks typically assume that all players willingly share their local observations with the server. However, this assumption is often unrealistic in practical settings where players are self-interested and may not participate in collaboration without explicit incentives. To address this challenge, we propose an incentive-aware federated bandit framework in which players receive rewards for sharing information with the server and incur costs when buying information from the server. We develop a UCB-based algorithm, termed Buying-UCB, that balances individual exploration and collaborative learning by incorporating both sharing incentives and information acquisition costs into the learning process. We theoretically analyze the proposed algorithm and derive upper bounds on the group regret and buying cost. Our analysis further characterizes the trade-off between fully collaborative federated learning and completely independent learning. Extensive numerical experiments validate the theoretical findings and demonstrate the effectiveness of the proposed framework under different collaboration and pricing regimes.

0.29