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.