Bandit Learning in General Open Multi-agent Systems

• URL: http://arxiv.org/abs/2605.06202v1
• Date: Thu, 07 May 2026 13:10:24 GMT
• Title: Bandit Learning in General Open Multi-agent Systems
• Abstract summary: We develop global-UCB learning methodologies with provable guarantees.<n>We show 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.
• Score: 5.260137087369842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Systematic Security Evaluation of OpenClaw and Its Variants [26.64519805689193]
  This paper presents a systematic security assessment of six representative OpenClaw-series agent frameworks.<n>We construct a benchmark of 205 test cases covering representative attack behaviors across the full agent execution lifecycle.<n>Our results show that all evaluated agents exhibit substantial security vulnerabilities, and that agentized systems are significantly riskier than their underlying models.
  arXiv  Detail & Related papers  (2026-04-03T15:52:36Z)
• Emergent Social Intelligence Risks in Generative Multi-Agent Systems [106.60961969939676]
  Multi-agent systems are rapidly moving from lab prototypes to real-world deployments, where they jointly plan, negotiate, and allocate resources to solve complex tasks.<n>Here, we present a pioneer study of such emergent multi-agent risk in pathologies that involve competition over shared resources, sequential handoff collaboration, collective decision aggregation, and others.<n>We observe that such group behaviors arise frequently across repeated trials and a wide range of interaction conditions, rather than as rare or pathological cases.<n>These findings expose the dark side of intelligent multi-agent systems: a social intelligence risk where agent collectives spontaneously reproduce familiar failure patterns from human societies.
  arXiv  Detail & Related papers  (2026-03-29T17:10:28Z)
• OMNI-LEAK: Orchestrator Multi-Agent Network Induced Data Leakage [59.3826294523924]
  We investigate the security vulnerabilities of a popular multi-agent pattern known as the orchestrator setup.<n>We report the susceptibility of frontier models to different categories of attacks, finding that both reasoning and non-reasoning models are vulnerable.
  arXiv  Detail & Related papers  (2026-02-13T21:32:32Z)
• Self-Consolidation for Self-Evolving Agents [51.94826934403236]
  Large language model (LLM) agents operate as static systems, lacking the ability to evolve through lifelong interaction.<n>We propose a novel self-evolving framework for LLM agents that introduces a complementary evolution mechanism.
  arXiv  Detail & Related papers  (2026-02-02T11:16:07Z)
• Just Ask: Curious Code Agents Reveal System Prompts in Frontier LLMs [65.6660735371212]
  We present textbftextscJustAsk, a framework that autonomously discovers effective extraction strategies through interaction alone.<n>It formulates extraction as an online exploration problem, using Upper Confidence Bound--based strategy selection and a hierarchical skill space spanning atomic probes and high-level orchestration.<n>Our results expose system prompts as a critical yet largely unprotected attack surface in modern agent systems.
  arXiv  Detail & Related papers  (2026-01-29T03:53:25Z)
• Challenges in Credit Assignment for Multi-Agent Reinforcement Learning in Open Agent Systems [0.19336815376402716]
  This report focuses on the interplay between openness and the credit assignment problem (CAP)<n>CAP involves determining the contribution of individual agents to the overall system performance.<n>Traditional credit assignment methods often assume static agent populations, fixed and pre-defined tasks, and stationary types, making them inadequate for open systems.
  arXiv  Detail & Related papers  (2025-10-31T17:30:32Z)
• STARec: An Efficient Agent Framework for Recommender Systems via Autonomous Deliberate Reasoning [54.28691219536054]
  We introduce STARec, a slow-thinking augmented agent framework that endows recommender systems with autonomous deliberative reasoning capabilities.<n>We develop anchored reinforcement training - a two-stage paradigm combining structured knowledge distillation from advanced reasoning models with preference-aligned reward shaping.<n>Experiments on MovieLens 1M and Amazon CDs benchmarks demonstrate that STARec achieves substantial performance gains compared with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-08-26T08:47:58Z)
• SafeMobile: Chain-level Jailbreak Detection and Automated Evaluation for Multimodal Mobile Agents [58.21223208538351]
  This work explores the security issues surrounding mobile multimodal agents.<n>It attempts to construct a risk discrimination mechanism by incorporating behavioral sequence information.<n>It also designs an automated assisted assessment scheme based on a large language model.
  arXiv  Detail & Related papers  (2025-07-01T15:10:00Z)
• Free Agent in Agent-Based Mixture-of-Experts Generative AI Framework [0.0]
  Reinforcement Learning Free Agent (RLFA) algorithm introduces a reward-based mechanism to detect and remove agents exhibiting persistent underperformance.<n>A primary use case is fraud detection, where RLFA promptly swaps out an agent whose detection accuracy dips below a preset threshold.<n>This dynamic, free-agency cycle ensures sustained accuracy, quicker adaptation to emerging threats, and minimal disruption to ongoing operations.
  arXiv  Detail & Related papers  (2025-01-29T13:00:22Z)
• A Hierarchical Framework with Spatio-Temporal Consistency Learning for Emergence Detection in Complex Adaptive Systems [41.055298739292695]
  Emergence, a global property of complex adaptive systems, is prevalent in real-world dynamic systems, e.g., network-level traffic congestions. This paper proposes a hierarchical framework with CAS-temporal consistency to solve these two problems by learning the system representation and agent representations. Our method achieves more detection than traditional methods and deep learning methods on three datasets with well-known yet hard-to-detect emergent behaviors.
  arXiv  Detail & Related papers  (2024-01-18T08:55:05Z)
• Non-Stationary Bandits with Auto-Regressive Temporal Dependency [14.093856726745662]
  This paper introduces a novel non-stationary MAB framework that captures the temporal structure of real-world dynamics through an auto-regressive (AR) reward structure. We propose an algorithm that integrates two key mechanisms: (i) an alternation mechanism adept at leveraging temporal dependencies to dynamically balance exploration and exploitation, and (ii) a restarting mechanism designed to discard out-of-date information.
  arXiv  Detail & Related papers  (2022-10-28T20:02:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.