Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Managing Self-Learning Experts under Per-Round Budget Constraints

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Causal and structured bandits

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes M-LCB, a UCB/LCB-style meta-algorithm that manages K self-learning experts under a per-round training budget M, training the M lowest-LCB experts and deploying the lowest-UCB one, with regret O(sqrt(KT/M)+(K/M)^{1-α}T^α c(δ)).

Problem

Sequential decision-making where a meta-procedure must choose which of K learning experts to deploy and which M of them to train each round, when expert losses are endogenous to training.

Approach

Allocate training budget by lowest lower confidence bounds on each expert's optimal loss and select the deployed advisor by lowest upper confidence bounds, with confidence widths built from realized losses and a known anytime expert regret envelope U_k.

Key results

• On Warfarin with M=2, M-LCB reaches cumulative loss 6,604 versus 6,589 for the best fixed expert.
• Theory: if expert regret is O(n^alpha), overall regret is O(sqrt(KT/M) + (K/M)^{1-alpha} T^alpha) with a matching minimax lower bound (up to logs).
• On Cardiotocography with M=4, M-LCB attains 95.0% mean accuracy and 105.6 cumulative loss versus 86.0 for the optimal fixed expert.

Limitations

• Assumes the confidence scaling c(delta) and expert regret envelope U_k are known in advance.
• Gap-dependent logarithmic guarantees are not obtained since the instantaneous gap changes as experts learn.
• Experiments are small-scale (synthetic bandits, GLMs, two clinical datasets) with hyperparameters tuned in separate validation environments.

Experimental setup

Datasets: IWPC Warfarin dosing Cardiotocography

Benchmarks: IWPC Warfarin dosing Cardiotocography synthetic Bernoulli bandit model selection synthetic GLM model selection

Metrics: cumulative regret cumulative loss top-M regret arm selection distribution

Baselines: LimitedAdvice Smooth CORRAL ED2RB RoundRobin EXP3.P smoothing wrapper

Builds on: Prediction with limited advice Smooth CORRAL Learnable arms (self-learning bandits) Multiple-play bandits UCB

Closest papers by meaning

• On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.88)
• Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.87)
• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
• On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice (NeurIPS 2024 · similarity 0.87)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.87)
• Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.87)