Bandit Learning in General Open Multi-agent Systems
Abstract
Open systems, where agents arrive and depart over time, are growing in digital platforms. Existing work on online learning in such systems, however, often relies on structural assumptions that may be restrictive in practice. In particular, heterogeneous rewards and general agent patterns create three new challenges: arrivals induce endogenous non-stationarity, agent patterns govern the rate of information accumulation, and uncertainty brought by new agents accumulates over time and scales regret. To this end, we formulate a learning problem for open systems that accommodates both forms of generality. We introduce new concepts to capture the inherent complexities: the \emph{pre-training degree} of new agents quantifies how much information an agent carries upon entry, \emph{stability} measures the impact of population changes on the global optimum, and \emph{global dynamic regret} compares the cumulative expected reward with that of the varying optimal arms. We also study a manifold representation of agents and introduce a \emph{dynamic population embedding} that directly encodes the population functional for each arm. We develop two UCB-based methods. The first combines entry information with online observations through agent-wise confidence bounds and aggregates the estimates and uncertainties for arm selection. The second pools agent-level observations through kernel regression on the manifold and constructs UCBs by projecting the confidence sets onto the current population embedding. Entry uncertainty enters the regret linearly through the pre-training error, while in stable regimes, regret is governed by the time needed to identify the stable optimal arm. With the manifold as a handle, regret is governed by the information gained from agent representations. These bounds all depend on population dynamics, but in different ways.
Related
- Robust Iterative Learning Control for Multi-Agent Systems with Random Impulsive Disturbances
- NeuroMAS: Multi-Agent Systems as Neural Networks with Joint Reinforcement Learning
- Multi-Agent Reinforcement Learning for Movable Antenna-aided Cell-Free Massive MIMO Systems
- Exponential Consensus and Flocking in Multi-Agent Systems with Infinite Fading Memory
- Resilient Monitoring of Social Dynamical Systems through Collaborative Multi-Agent Networks under Latency
BibTeX
@misc{xu2026bandit,
title = {{Bandit Learning in General Open Multi-agent Systems}},
author = {Mengfan Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.06202},
eprint = {2605.06202},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.06202},
}
RIS
TY - UNPB
TI - Bandit Learning in General Open Multi-agent Systems
AU - Mengfan Xu
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2605.06202
UR - https://arxiv.org/abs/2605.06202
AB - Open systems, where agents arrive and depart over time, are growing in digital platforms. Existing work on online learning in such systems, however, often relies on structural assumptions that may be restrictive in practice. In particular, heterogeneous rewards and general agent patterns create three new challenges: arrivals induce endogenous non-stationarity, agent patterns govern the rate of information accumulation, and uncertainty brought by new agents accumulates over time and scales regret. To this end, we formulate a learning problem for open systems that accommodates both forms of generality. We introduce new concepts to capture the inherent complexities: the \emph{pre-training degree} of new agents quantifies how much information an agent carries upon entry, \emph{stability} measures the impact of population changes on the global optimum, and \emph{global dynamic regret} compares the cumulative expected reward with that of the varying optimal arms. We also study a manifold representation of agents and introduce a \emph{dynamic population embedding} that directly encodes the population functional for each arm. We develop two UCB-based methods. The first combines entry information with online observations through agent-wise confidence bounds and aggregates the estimates and uncertainties for arm selection. The second pools agent-level observations through kernel regression on the manifold and constructs UCBs by projecting the confidence sets onto the current population embedding. Entry uncertainty enters the regret linearly through the pre-training error, while in stable regimes, regret is governed by the time needed to identify the stable optimal arm. With the manifold as a handle, regret is governed by the information gained from agent representations. These bounds all depend on population dynamics, but in different ways.
ER -