Technical Summary: Learning to Hand Off

Problem Statement

This paper addresses the challenge of learning optimal workflows in sequential decentralized multi-agent systems, specifically within the context of Multi-Agent LLM pipelines. Unlike centralized regimes where a single designer has global visibility into agent trajectories, the target operating regime involves agents that span organizational, vendor, or trust boundaries. In this setting:

1. Sequential Handoffs: Control transfers from one specialized agent to another via a shared artifact (e.g., a message or code snippet).
2. Decentralization: No party accesses joint trajectories during training or execution.
3. Interface Constraints: Each agent observes only the artifact it receives and its own private state; internal states, chains of thought, and proprietary prompts are not exposed across boundaries.
4. Finite-Sample Requirements: Deployments operate under bounded compute and API budgets, necessitating guarantees on sample efficiency rather than just asymptotic convergence.

Existing frameworks fail to address this specific combination of constraints. Decentralized POMDPs (Dec-POMDPs) assume concurrent actions; Centralized Training with Decentralized Execution (CTDE) requires joint trajectory access during training; and the Options framework assumes full state observation at decision epochs. Furthermore, prior work on multi-agent LLM orchestration relies on hand-designed adaptive rules without decision-theoretic foundations or convergence guarantees.

Methodology

Formal Model: IC-SMDP

The authors formalize the problem as an Interface-Constrained Semi-Markov Decision Process (IC-SMDP).

• Structure: The system evolves at a primitive time scale but makes decisions at handoff times. Each agent invocation is treated as a temporally extended "option."
• States:
  • Global Latent State ($x_t$): Unobserved by any agent.
  • Interface State ($m_t$): The artifact passed between agents (the only cross-agent information channel).
  • Private State ($\ell^{(i)}_t$): Local to agent $i$.
• Observations: Agent $i$ observes $o_t = \phi_i(m_t, \ell^{(i)}_t)$, where $\phi_i$ is an agent-specific observation map. This enforces the interface constraint: agents cannot see the raw interface state or other agents' private states directly.
• Actions: Agents select a local action and a successor agent (or a STOP signal).
• Objective: Maximize the expected discounted return over the workflow, subject to the observation constraints.

Algorithm: IC-Q

The authors propose IC-Q, an asynchronous decentralized Q-learning algorithm designed for the pre-configured regime (where local actions are fixed, and only successor selection is learned).

• Mechanism: Each agent maintains a local Q-function over its own AIS (Approximate Information State) observations.
• Value Passing: At every handoff, the successor agent computes a scalar bootstrap target $b_{k+1} = \max_{c'} \hat{Q}_{c'}(o'_{k+1}, c')$ and transmits this scalar, along with the option duration $\tau_{k+1}$ and accumulated reward $R_k$, back to the predecessor.
• Update: The predecessor updates its local Q-function using the regression target $y_k = R_k + \gamma^{\tau_{k+1}} b_{k+1}$.
• Communication Overhead: Cross-agent coordination is restricted to exactly three scalars per handoff, ensuring minimal bandwidth and API costs.

Theoretical Framework

The analysis lifts the Approximate Information State (AIS) framework from single-agent primitive-step MDPs to multi-agent SMDPs.

• AIS Conditions: The authors define reward sufficiency ($\epsilon_\phi$) and evolution sufficiency ($\delta_\phi$) at the option scale, accounting for random option durations and the random discount factor $\gamma^{\tau_{k+1}}$.
• Convergence Proof: The paper establishes a finite-sample convergence bound for IC-Q under standard assumptions (uniform ergodicity, bounded rewards/durations, well-conditioned features, and a specific SMDP-level Bellman contraction condition).

Key Contributions

1. Formal Model (IC-SMDP): Introduction of a decision-theoretic model for sequential handoffs under interface constraints, showing it induces a well-defined SMDP at handoff times with a quantifiable interface gap.
2. Decentralized Algorithm (IC-Q): Design of an asynchronous Q-learning algorithm where cross-agent coordination is minimized to a single scalar per handoff, respecting strict privacy and bandwidth constraints.
3. Finite-Sample Convergence Guarantee: The first finite-sample bound for neural Q-learning under decentralized partial observability. The bound decomposes into three independently controllable error sources:
   • Neural Approximation Error: Vanishes with wider networks.
   • Interface Representation Gap: The price paid for limited observation, bounded by AIS conditions.
   • Mixing-Time Residual: Decays at a rate of $O(1/T)$, dependent on the random duration of options.
4. Theoretical Novelty: The proof addresses three challenges not faced in prior work:
   • Bellman contraction under a random discount (dependent on option duration) rather than a fixed discount.
   • Propagation of the AIS gap at the option scale rather than the primitive-step scale.
   • Control of Markovian noise under random option durations.

Empirical Results

The authors validate the framework and theory across four experiments:

1. Synthetic IC-SMDP: A controlled environment with 10 agents used to isolate the three error terms in the theoretical bound.
   • Result: The empirical value gap correlates strongly ($\rho \approx 0.916$) with the AIS gap as the interface observation degrades. The error scaling matches the predicted $O(1/T)$ mixing residual and the dependence on mixing time.
2. Multi-LLM Mathematical Reasoning: Four LLM agents (Commissioner, Thinker, Checker, Editor) solve math problems. Agents only see a 4-bit AIS encoding (answer status, modification, check, correctness) rather than the full conversation.
   • Result: IC-Q matches a centralized oracle and recovers the optimal predefined workflow (e.g., engaging a checker for hard problems, skipping it for easy ones) without any agent observing joint trajectories.
3. Multi-Agent Routing: 100 agents route tasks in random graphs with exact AIS observations ($\epsilon_\phi = \delta_\phi = 0$).
   • Result: IC-Q achieves 100% routing accuracy across various graph distributions, validating the algorithm in the regime where the AIS gap term vanishes.
4. Multi-Agent CPU Programming: Six agents collaboratively transform memory states. Both local actions and successor selection are learned (adaptable regime).
   • Result: IC-Q achieves $\approx 80\%$ accuracy on unseen target states, demonstrating empirical generalization beyond the pre-configured scope of the formal theorem.

Significance and Claims

The paper claims to provide the first framework that respects the four distinct operating conditions of sequential decentralized workflows (sequential handoffs, full decentralization, interface-limited observation, and finite-sample guarantees).

• Theoretical Significance: It offers the first joint asymptotic and finite-sample bound for neural Q-learning under decentralized partial observability. It extends the AIS framework to multi-agent SMDPs with random durations, a gap not previously addressed.
• Practical Significance: The results demonstrate that high-performance workflow learning is possible without centralized data access or exposure of internal agent states. The algorithm matches centralized oracles in complex LLM tasks while adhering to strict privacy and communication constraints.
• Modesty: The authors explicitly note that the formal convergence proof applies to the pre-configured regime (fixed local policies). The success in the adaptable regime (CPU programming) is presented as empirical evidence of generalization, with formal convergence for the adaptable case left for future work.