Most online learning research assumes a fixed set of agents, but real digital platforms see agents constantly join and leave. This paper from Mengfan Xu formulates a bandit learning problem for such open multi-agent systems, allowing for heterogeneous rewards and general arrival and departure patterns. The author argues that these conditions break standard assumptions: arrivals create endogenous non-stationarity, the rate of information accumulation depends on agent turnover, and uncertainty from new agents accumulates over time.

To make the problem tractable, the paper defines three new concepts. The pre-training degree of a new agent measures how much useful information it carries upon entry. Stability quantifies how much population changes affect the global optimum. And global dynamic regret compares cumulative reward against a moving optimal arm, rather than a fixed one. The author also introduces a dynamic population embedding that encodes the population functional for each arm, allowing the algorithm to reason about the current set of agents.

Two UCB-based methods are developed. The first combines entry information with online observations using agent-wise confidence bounds, aggregating estimates and uncertainties for arm selection. The second pools agent-level observations through kernel regression on a manifold, projecting confidence sets onto the current population embedding. In both cases, regret bounds depend on population dynamics, but in different ways: entry uncertainty enters regret linearly through the pre-training error, while in stable regimes regret is governed by the time needed to identify the stable optimal arm. The manifold-based method shifts this to depend on the information gained from agent representations.

The paper does not claim a single universal bound; instead, it shows how different sources of difficulty—entry uncertainty, stability, and representation quality—each shape regret. This provides a more general toolkit for designing learning algorithms in open systems, though the practical performance of the proposed methods on real platforms remains to be tested.