Managing Self-Learning Experts under Per-Round Budget Constraints

arXiv:2510.22654v3 Announce Type: replace 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 ilde O(T^alpha) by round T, then M-LCB guarantees an overall regret of ilde Oleft(sqrt{KT/M} + (K/M)^{1-alpha}T^alpharight) 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.

Source: arXiv cs.LG | 2026-09-29