Managing Self-Learning Experts under Per-Round Budget Constraints

Ilgam Latypov; Alexandra Suvorikova; Alexey Kroshnin; Alexander Gasnikov; Yuriy Dorn

cs.LGOct 26, 2025

Managing Self-Learning Experts under Per-Round Budget Constraints

Authors: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn

Organizations: AI Center, Lomonosov Moscow State University MSU Institute for Artificial Intelligence Moscow, Russia · Weierstrass Institute for Applied Analysis and Stochastics Berlin, Germany · IITP RAS Moscow, Russia · Steklov Mathematical Institute of RAS Moscow, Russia

Abstract

This paper addresses the problem of sequential decision-making under learning budget constraints. Such settings naturally arise in applications like managing a portfolio of bandit or reinforcement learning (RL) algorithms. We propose a novel UCB-type algorithm, M-LCB, designed to manage a pool of $K$ self-learning experts in a stochastic environment while accounting for a limited per-round learning budget $M$ . At each round, M-LCB selects one expert to make a decision and at most $M \le K$ experts to learn. For selection, M-LCB uses confidence bounds constructed from limited prior knowledge about the experts (i.e., mild assumptions) and their observed training losses. We derive anytime regret bounds for M-LCB that scale with the individual regrets of the experts. In particular, if each expert has regret $\tilde O(T^α)$ by round $T$ , then M-LCB guarantees an overall regret of $\tilde O\left(\sqrt{KT/M} + (K/M)^{1-α}T^α\right)$ relative to the best expert in hindsight. Finally, we demonstrate the applicability of M-LCB using self-learning experts instantiated as (i) parametric models and (ii) bandit algorithms.

Figures & tables

Algorithm / Reference	Learnable	Multi-arm	Multiple-play	Regret rate (up to logs)
CORRAL + smoothing wrapper [ 26 ]	$\checkmark$	$\times$	$\times$	$\tilde{O}\!\left(\sqrt{KT}+K^{\alpha}T^{1-\alpha}+K^{1-\alpha}T^{\alpha}c(\delta)\right)$
EXP3.P + smoothing wrapper [ 26 ]	$\checkmark$	$\times$	$\times$	$\tilde{O}\!\left(\sqrt{KT}+K^{\frac{1-\alpha}{2-\alpha}}T^{\frac{1}{2-\alpha}}c(\delta)^{\frac{1}{2-\alpha}}\right)$
Dynamic Balancing [ 12 ]	$\checkmark$	$\times$	$\times$	$\tilde{O}\!\left(\sqrt{KT}+K^{1-\alpha}T^{\alpha}c(\delta)\right)$
Prediction with Limited Advice [ 28 ]	$\times$	$\checkmark$	$\times$	$\tilde{O}\!\left(\sqrt{\tfrac{KT\log K}{M}}\right)$
H-INF [ 34 ]	$\times$	$\checkmark$	$\times$	$\tilde{O}\!\left(\max\{\sqrt{KT/M},\,\sqrt{T\log K}\}\right)$
UCB-based multiple-play bandits [ 22 ]	$\times$	$\times$	$\checkmark$	$\tilde{O}\!\left(\sqrt{KT/M}\right)$ $\alpha=\frac{1}{2}$

Table 1: Assuming

U_{k}(T,\delta)=O(T^{\alpha}c(\delta))

with

\alpha\in[0,1]

and poly-logarithmic

c(\delta)

, we compare regret rates up to logarithmic factors (

\checkmark

indicates supported properties). Regret follows Section 4.1 for multiple-play bandits, specific conventions for [ 28 , 34 ] , and Section 2.3 otherwise. Our M -LCB algorithm attains optimal rates for both regret definitions.

Figure 1: Performance comparison on the MAB model selection. (a) Cumulative Loss. (b) Final distribution of arm selection. (c) Allocation of computational budget across arms.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Nonlinear link functions associated with the arms (top) and the density of generated data points (bottom). One can see that the last three functions are highly similar where the data is concentrated, making it hard to distinguish the optimal arm.

Figure 3: Performance comparison on the GLM model selection problem. (a) Cumulative regret. (b) Final distribution of arm selection. (c) Allocation of computational budget across arms.

Figure 4: Performance comparison on the MAB model selection. (a) Cumulative regret. (b) Final distribution of arm selection. (c) Allocation of computational budget across arms.

Inner algorithm / problem	Inner rate $U_{k}(n,\delta)$	Global regret (up to logs)
OGD / OMD (convex Lipschitz)	$O(G_{k}R_{k}\sqrt{n})$ , $\alpha=\tfrac{1}{2}$ ,	$O\!\big(T^{1/2}\,\\|GD\\|_{M,1/2}\big)$
Bandit Convex Optimization (bounded $f_{t}$ ) [ 18 ]	$O(C_{k}d_{k}n^{5/6})$ , $\alpha=\tfrac{5}{6}$	$O\!\big(T^{5/6}\,\\|Cd\\|_{M,1/6}\big)$
Bandit Convex Optimization ( $L$ –Lipschitz $f_{t}$ ) [ 18 ]	$O(\sqrt{C_{k}L_{k}R_{k}}d_{k}n^{3/4})$ , $\alpha=\tfrac{3}{4}$	$O\!\big(T^{3/4}\,\\|\sqrt{CLR}d\\|_{M,1/4}\big)$
Heavy–tailed stochastic bandits [ 6 ]	$\tilde{O}(n^{\alpha}N_{k}^{1-\alpha})$ , $\alpha=\tfrac{1}{1+\varepsilon}$	$O\!\big(T^{\alpha}\,[\frac{1}{M}\sum_{k=1}N_{k}]^{1-\alpha})$
Heavy–tailed stochastic bandits (Symmetric noise) [ 15 ]	$O(\sqrt{N_{k}n}{\log n}^{\frac{3}{2}})$ , $\alpha=\tfrac{1}{2}$	$O\!\big(T^{1/2}\,[\frac{1}{M}\sum_{k=1}N_{k}]^{\frac{1}{2}}\big)$
Heavy–tailed linear bandits [ 32 ]	$O(d_{k}^{\frac{3}{2}-\alpha}n^{\alpha})$ , $\alpha=\tfrac{1}{1+\varepsilon}$	$O\big(T^{\alpha}\,\\|d^{\frac{3}{2}-\alpha}\\|_{M,1-\alpha}\big)$

Appendix

Table 2: Examples of inner-arm convergence rates

U_{k}(n,\delta)

and resulting global regret (up to logarithmic factors and an additive term

O(\sqrt{(K/M)T})

). For each expert

k

, the inner algorithm satisfies

U_{k}(t,\delta)=O(\beta_{k}\,t^{\alpha}c(\delta))

, and the corresponding global regret scales as

O\!\big(T^{\alpha}c(\delta)\,\|{\boldsymbol{\beta}}\|_{M,1-\alpha}\big)

, where

\|{\boldsymbol{\beta}}\|_{M,\gamma}=\Bigl(\tfrac{1}{M}\sum_{k=1}^{K}\beta_{k}^{\frac{1}{\gamma}}\Bigr)^{\gamma}

. Parameter conventions:

K

— # experts;

M

— per-round training budget;

T

— horizon;

N_{k}

— # base arms/actions;

d_{k}

— feature dimension;

\varepsilon

— heavy-tail moment exponent (

\mathbb{E}|X|^{1+\varepsilon}\!\leq\sigma^{1+\varepsilon}

);

L,R,C,G

— Lipschitz, diameter, range, and gradient constants.

Figure 5: Warfarin dosing results under limited advice budgets. M -LCB achieves the lowest cumulative loss among the compared methods and, at $M=2$ , attains cumulative loss $6{,}604$ , close to the best-fixed-expert reference of $6{,}589$ .

Figure 6: Scaling behavior on the Warfarin dosing benchmark with $K\in\{7,10,15\}$ and fixed budget $M=2$ . Regret grows with the number of experts, matching the qualitative prediction of the $\mathcal{O}(\sqrt{KT/M})$ regret dependence.

Figure 7: Top- $M$ regret on the Cardiotocography benchmark with $K=15$ experts and budgets $M\in\{1,2,4,8\}$ over 30 random seeds. For $M\geq 4$ , M -LCB obtains near-zero top- $M$ regret, matching the best fixed subset of $M$ experts.

Explore similar work

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4
Google Research · Yale University · Google DeepMind
Self-Concordant Perturbations for Linear Bandits
Oct 28, 2025Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1Linear Bandits Efficient Exploration
Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique +1
Learning in Markovian bandits with non-observable states and constrained decision epochs
Jun 25, 2026Thomas Hira, Victor Boone, Urtzi Ayesta +1O(T^Β)$ Simultaneous Regret Markov Decision Processes
IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · Ikerbasque-UPV/EHU, University of the Basque Country, Bilbao, Spain

Sep 23, 2026, stat.MLJ/K move · Enter open · S save

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw+3

Google Research · Yale University · Google DeepMind

Open paper AskPDF arXiv

Prediction with expert advice is a fundamental problem in online learning. When the time horizon

T

is known in advance, the minimax cumulative regret over

n

experts is asymptotically

\sqrt{\frac{T \ln n}{2}}

. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to

T

, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time

t

, the best known guarantee has been

\sqrt{t \ln n}

---a factor of

\sqrt{2}

worse---and it has remained unknown whether this factor of

\sqrt{2}

is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies

R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}

simultaneously for every

t \ge 1

Abstract

Explore similar work

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Self-Concordant Perturbations for Linear Bandits

Learning in Markovian bandits with non-observable states and constrained decision epochs