Learning to Hand Off: Provably Convergent Workflow Learning under Interface Constraints

We study workflow learning in a setting where specialized agents hand off control through a shared artifact, each agent observes only a local function of that artifact and its own private state, and no centralized learner accesses joint trajectories -- the operating regime of multi-agent LLM pipelines that span organizational, vendor, or trust boundaries. We formalize this regime as an interface-constrained semi-Markov decision process (IC-SMDP), whose decision epochs occur at handoff times, and design IC-$Q$, an asynchronous decentralized $Q$-learning algorithm in which cross-agent coordination at every handoff is exactly one scalar. Our main result is a finite-sample bound for neural IC-$Q$ that decomposes into three independently controllable error sources: neural function-approximation error, interface representation gap, and a mixing-time residual, under the random option-duration discount. Establishing this bound requires lifting the approximate information state (AIS) framework from single-agent primitive-step MDPs to multi-agent SMDPs and controlling Markovian noise under random duration, neither of which has been done in prior work. To our knowledge this is the first finite-sample guarantee for neural $Q$-learning under decentralized partial observability. Four experiments: a controlled synthetic IC-SMDP that validates the bound term-by-term, multi-LLM mathematical reasoning, multi-agent routing, and multi-agent CPU programming, show that IC-$Q$ matches a centralized oracle without any agent observing joint trajectories, with each of the three error sources scaling along its corresponding axis as the bound predicts.

한 줄 요약

**[멀티 에이전트 RL / 이론]** 에이전트들이 공유 아티팩트를 통해 인터페이스 제약 하에 hand-off하며 각자 로컬 함수만 관측하는 환경을 IC-SMDP로 형식화하고, 신경망 IC-Q에 대한 최초의 finite-sample 보장을 제시.

핵심 기여도

조직·벤더·신뢰 경계를 가로지르는 multi-agent LLM 파이프라인의 실제 운영 체제(공유 artifact를 통한 hand-off, 부분 관측, 중앙 학습자 없음)를 인터페이스 제약 semi-MDP(IC-SMDP)로 형식화.
handoff 시점마다 cross-agent 조율이 단 하나의 스칼라뿐인 asynchronous decentralized Q-learning 알고리즘 IC-Q 설계.
신경망 IC-Q의 finite-sample bound를 (1) 신경 함수 근사 오차, (2) 인터페이스 표현 간극, (3) mixing-time residual의 세 독립 제어 가능 오차로 분해하는 main result 입증 (random option-duration discount 하).
AIS framework를 single-agent primitive-step MDP에서 multi-agent SMDP로 들어 올리고 random duration 하의 Markovian noise를 통제 → 분산 부분 관측 하 신경 Q-learning의 첫 finite-sample guarantee.

핵심 아이디어

실세계 멀티 에이전트 LLM 파이프라인은 "공동 trajectory를 보는 중앙 학습자"가 없고 에이전트마다 부분 관측만 한다. 이 환경을 IC-SMDP로 정확히 형식화하고, 인터페이스에 흐르는 스칼라만으로 조율되는 IC-Q를 신경망으로 안전하게 학습시킬 수 있음을 이론·실험으로 동시에 증명.

기술적 접근법

**모델/방법론**: 인터페이스 제약 semi-Markov decision process(IC-SMDP) 형식화 + asynchronous decentralized neural Q-learning IC-Q.
**핵심 기법**: handoff 시점에 단일 스칼라 cross-agent 조율, AIS framework의 multi-agent SMDP 확장, random option-duration discount 하의 Markovian noise 제어, finite-sample bound 분해 (function approx + interface representation + mixing-time).

주요 결과

통제된 합성 IC-SMDP에서 finite-sample bound를 항별로 검증.
multi-LLM 수학 추론, multi-agent routing, multi-agent CPU programming 세 실험에서 IC-Q가 공동 trajectory를 보는 centralized oracle 성능에 필적.
세 오차 항이 bound가 예측한 축을 따라 독립적으로 스케일됨을 실증.

의의 및 한계

**의의**: 멀티 에이전트 LLM 파이프라인 학습에 결여되어 있던 "분산 부분 관측 하 신경 RL의 이론적 보장"을 제공해 실제 운영 환경의 학습 알고리즘 설계에 디딤돌 마련. **한계**: 분석이 single-scalar handoff 인터페이스에 기반, 더 풍부한 인터페이스(여러 메시지·구조화 객체) 학습 이론은 후속 연구.

실용적 활용

조직 경계를 넘는 multi-agent LLM 파이프라인의 학습 알고리즘 설계.
인터페이스 제약을 갖는 multi-agent 라우팅·도구 사용 시스템의 견고한 최적화.
분산 RL 이론 연구의 새로운 multi-agent SMDP 분석 도구.