Managing Self-Learning Experts under Per-Round Budget Constraints

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 ≤ 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 Oleft(√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.