解决开放多智能体系统中动态接入带来的学习难题。
Bandit Learning in General Open Multi-agent Systems
- 提出预训练度、稳定性等新概念刻画系统复杂性
- 首次建立全局动态遗憾的理论边界并证明其紧性
- 适合研究动态系统学习与智能体协作的学者
数字平台的发展凸显了开放系统中智能体可动态接入与退出的普遍性。现有工作常依赖不切实际的结构假设。本文构建通用开放系统上的统一多臂赌博机模型，支持异质奖励与任意智能体模式。引入预训练度量化新智能体携带信息量，稳定性衡量其对系统影响，全局动态遗憾则比较所有活跃智能体累积收益与随时间变化的最优动作收益。设计具有可证明保证的认证全局UCB算法。理论分析表明，进入不确定性以线性方式通过预训练度影响遗憾；在稳定情形下，遗憾取决于识别持久最优动作所需时间及智能体模式。通过硬实例的下界证明这些依赖关系是紧的。
原文摘要 · Abstract (English)
Recent developments in digital platforms have highlighted the prevalence of open systems, where agents can arrive and depart over time. While bandit learning in open systems has recently received initial attention, existing work imposes structural assumptions that are frequently violated in practice. A learning paradigm for general open systems creates fresh challenges: newly arriving agents induce endogenous non-stationarity; agent patterns determine how quickly information accumulates; and new agents make regret scale further with the time horizon. To this end, we formulate a unified open-system bandit problem with general dynamics, including heterogeneous rewards and general agent patterns. 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 new agents on the system, and \emph{global dynamic regret} compares the cumulative expected reward of all active agents with that of the varying optimal arms. We develop certified global-UCB learning methodologies with provable guarantees. Our regret bounds reveal that entry uncertainty enters linearly via the pre-training degree, while in stable regimes, regret is governed by the time needed to identify a persistent optimal arm, as well as by the agent patterns. We further show that these dependencies are tight via lower bounds in hard instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。