제한된 예산 하에서 최대 정보량 확보: 도구 사용 에이전트 강화 학습을 위한 트리 탐색의 서브모듈러 관점

Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learning

본 논문에서는 제한된 예산 하에서의 정보량(Rollout Informativeness under a Fixed Budget, RIFB)을, 도구 사용 롤아웃 집합이 그룹 상대 정책 최적화(Group Relative Policy Optimization, GRPO)에 미치는 예상되는 정책 기울기 질량으로 공식화합니다. 우리는 예산에 독립적인 모든 독립 샘플러가, 예산의 크기와 상관없이 어려운 프롬프트에 대해 0에서 멀어지지 않는 붕괴율을 갖는다는 것을 증명합니다. 이러한 동기를 바탕으로, 중간 상태 선택을 단조 서브모듈러 최대화 문제로 재구성하며, 탐욕적인 1단계 선택기는 1 - 1/e의 근사 보장 성능을 제공합니다. 본 논문의 불확실성 인지 상한(Uncertainty-aware Upper Confidence Bound, UUCB) 항은 이 목적 함수의 폐쇄형 주변 이득으로 도출됩니다. 이는 토큰 수준의 엔트로피 보너스를 경험적인 트릭이 아닌, 제안된 프레임워크의 분석적 결과로 만듭니다. 우리는 UUCB와 학습된 적응적 예산 할당기(Adaptive Budget Allocator, ABA), 그리고 비동기식 추론 확장(Speculative Expansion) 방식을 결합한 트리 탐색 프레임워크인 InfoTree를 제시합니다. ABA는 초기 트리가 균일한 결과에 낭비되는 프롬프트를 복구하여, 혼합 결과 비율을 58.1%에서 76.3%로 향상시키면서 5% 미만의 예산 오버헤드를 발생시킵니다. 추론 확장은 UUCB 점수의 제한된 노후성을 허용하여, 실제 실행 시간 오버헤드를 14.3%에서 4.8%로 줄입니다. 수학적 추론(AIME 2024 및 2025, MATH-500, OlympiadBench, USAMO), 웹 검색 에이전트(GAIA, HLE-100, BrowseComp-lite), 그리고 다양한 도구를 사용하는 코딩 및 운영 체제 에이전트(APPS-verified, AgentBench-OS)를 포함하는 9개의 벤치마크에서, InfoTree는 flat GRPO, DeepSearch, Tree-GRPO, AT2PO, CW-GRPO, 그리고 RC-GRPO보다 뛰어난 성능을 보입니다. Tree-GRPO의 트리 구조 공유 및 CW-GRPO의 기여도 가중치 결합을 통해 추가적인 성능 향상을 얻을 수 있으며, 이는 제안된 선택기가 롤아웃 재사용 및 경로 재가중과 독립적으로 작동한다는 것을 확인합니다. 5x5x5의 강건성 그리드를 통해, 하이퍼파라미터 공간의 3/4 이상이 성능 향상 수준에 도달하며, 이는 UUCB의 강건성을 확인합니다.

We formalize Rollout Informativeness under a Fixed Budget (RIFB) as the expected non-vanishing policy-gradient mass that a tool-use rollout set injects into Group Relative Policy Optimization (GRPO). We prove that any budget-agnostic independent sampler suffers a collapse rate bounded away from zero for hard prompts regardless of the budget. Motivated by this, we recast intermediate state selection as a monotone submodular maximization problem, where a greedy one-step selector enjoys a 1 minus 1/e approximation guarantee. Our Uncertainty-aware Upper Confidence Bound (UUCB) terms arise as closed-form marginal gains of this objective. This turns the token-level entropy bonus from an empirical trick into an analytic consequence of the formulation. We present InfoTree, a training-time tree-search framework coupling UUCB with a learned Adaptive Budget Allocator (ABA) and an asynchronous Speculative Expansion scheme. ABA rescues prompts whose initial tree is wasted on uniform outcomes, lifting the mixed-outcome ratio from 58.1 percent to 76.3 percent with less than 5 percent budget overhead. Speculative Expansion reduces wall-clock overhead from 14.3 percent to 4.8 percent by tolerating bounded staleness in UUCB scores. Across nine benchmarks spanning math reasoning (AIME 2024 and 2025, MATH-500, OlympiadBench, USAMO), web-search agents (GAIA, HLE-100, BrowseComp-lite), and tool-rich coding and OS agents (APPS-verified, AgentBench-OS), InfoTree outperforms flat GRPO, DeepSearch, Tree-GRPO, AT2PO, CW-GRPO, and RC-GRPO. Head-to-head compositions with Tree-GRPO prefix sharing and CW-GRPO contribution weights deliver further gains, confirming that our selector operates orthogonally to rollout reuse and trajectory re-weighting. A 5 by 5 by 5 robustness grid reveals that over three quarters of the hyperparameter space lies on a performance plateau, confirming UUCB robustness.