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

Sep 23, 2026stat.ML

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

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

Yang Cai, Vineet Gupta, Yanchen Jiang +4

Google Research · Yale University · Google DeepMind

Topic pending

Ask PDF

Oct 28, 2025stat.ML

Self-Concordant Perturbations for Linear Bandits

We consider the adversarial linear bandits setting and present a unified algorithmic framework that bridges Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FTPL) methods, extending the known connection between them from the full-information setting. Within this framework, we introduce self-concordant perturbations, a family of probability distributions that mirror the role of self-concordant barriers previously employed in the FTRL-based SCRiBLe algorithm. Using this idea, we design a novel FTPL-based algorithm that combines self-concordant regularization with efficient stochastic exploration. Our approach achieves a regret of

\mathcal{O}(d\sqrt{n \ln n})

on both the

d

-dimensional hypercube and the

\ell_2

ball. On the

\ell_2

ball, this matches the rate attained by SCRiBLe. For the hypercube, this represents a

\sqrt{d}

improvement over these methods and matches the optimal bound up to logarithmic factors.

Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1

Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique +1

Linear Bandits Efficient Exploration Scratch

Ask PDF

Jun 25, 2026cs.LG

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

This paper studies the problem of regret minimization in Markovian bandits with \emph{non-observable states} and possibly \emph{constrained} decision epochs. The focus is restricted to a ``pure'' regret benchmark, that compares the performance of the learning algorithm to the best \emph{pure policy} which -- akin to optimal policies of stochastic bandits -- picks the optimal arm from start to finish without ever switching. We introduce a generalization of rested Markovian bandits, \emph{self-degrading Markovian bandits}, for which pure policies are always asymptotically optimal.We show that without prior knowledge on the underlying bandit, the regret of algorithms that switch arms rarely necessarily scales super-logarithmically for every bandit, i.e., as

ω(\log(T))

, where

T

is the learning horizon. Despite the unreachability of the logarithmic regime, we design UCB-NOM, an optimistic algorithm inspired by UCB, of which the regret is nearly logarithmic. Lastly, we show that given prior knowledge on the Markovian bandit in the form of a bound on the bias functions of its arm, a proper instantiation of UCB-NOM achieves

O(\log(T))

regret. We further show that this prior knowledge allows for a

O(\sqrt{T \log(T)})

worst-case regret bound for UCB-NOM. Notably, our regret bounds do not depend on the number of states of the underlying Markov chains. Our findings suggest that the non-observability of states is a mild inconvenience in self-degrading Markovian bandits.

Thomas Hira, Victor Boone, Urtzi Ayesta +1

IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · Ikerbasque-UPV/EHU, University of the Basque Country, Bilbao, Spain

O(T^Β)$ Simultaneous Regret Markov Decision Processes Optimal Policies Partial Observability Best-Epoch Metrics

Ask PDF