🤖 machine learning

Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning

이 논문은 선형적 상호작용 궤적을 전역 상태 전이 그래프로 변환하여 보상 희소성을 완화하고 신용 할당을 개선함으로써, 장기적 에이전트 작업에서 대규모 언어 모델의 성능을 크게 향상시키는 새로운 그룹 기반 강화 학습 알고리즘인 Group-Graph Policy Optimization (G2PO)를 제안한다.

원저자: Yunan Wang, Minghui Song, Zihan Zhang, Shaohan Huang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, Qi Zhang

게시일 2026-06-23

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yunan Wang, Minghui Song, Zihan Zhang, Shaohan Huang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, Qi Zhang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 아주 똑똑하지만 경험은 부족한 로봇에게 거대한 창고에서 특정 물건을 찾거나, 웹사이트에서 완벽한 선물을 사는 것과 같은 복잡한 퍼즐을 푸는 법을 가르치고 있다고 상상해 보세요. 로봇은 일을 끝내기 위해 여러 단계(회전/이동)를 거쳐야 하며, 임무가 다 끝난 후에야 비로소 "잘했어!" 또는 "다시 해봐"라는 피드백을 받습니다.

현재의 학습 방식은 로봇의 여정을 하나의 직선처럼 취급한다는 문제가 있습니다. 만약 로봇이 초반에는 아주 멋진 움직임을 보였더라도 나중에 자기 발에 걸려 넘어지면, 전체 과정이 실패로 처리됩니다. 그러면 로봇은 그 멋진 움직임조차도 나쁜 것이었다고 학습하게 되어, 매우 혼란스러워하고 학습 속도가 느려집니다.

이 논문은 G2PO(Group-Graph Policy Optimization)라고 불리는 새로운 교수법을 소개합니다. 이 방식이 어떻게 작동하는지 쉬운 비유를 통해 설명하겠습니다.

1. 직선에서 경로의 그물망으로

기존 방식은 로봇이 시작부터 끝까지 걷는 하나의 직선 경로만을 관찰합니다. 만약 로봇이 길을 잃으면, 그 경로는 막다른 길이 됩니다.
G2PO는 관점을 바꿉니다. 단순히 직선을 보는 대신, 로봇이 시도했던 모든 경로를 엮어 하나의 **거대한 그물망(또는 그래프)**을 구축합니다.

비유: 로봇이 동굴을 탐험하고 있다고 상상해 보세요. 기존 방식은 특정 터널 하나만을 봅니다. 하지만 G2PO는 동굴 전체의 지도를 봅니다. 로봇이 서로 다른 경로를 택했더라도, 결국 똑같은 방(상태)에 여러 번 도달한다는 사실을 포착해 냅니다.

2. 실수를 위한 "그룹 포옹" (Group-Aggregation)

기존 방식에서는 로봇이 특정 방에 들어갔다가 실패하면, 그 방을 "나쁜 곳"이라고 낙인찍습니다. 만약 나중에 똑같은 방에 들어갔는데 성공한다면, 그 방은 "좋은 곳"이 됩니다. 이는 혼란을 야책니다. 방 자체는 변하지 않았는데, 그 이후의 경로만 바뀌었기 때문입니다.
G2PO는 이렇게 말합니다. "로봇이 그 특정 방에 들어갔던 모든 순간을 살펴보자."

비유: 학생의 숙제를 채점하는 선생님을 상상해 보세요. 단순히 시험지 한 장을 보고 "너 틀렸어"라고 말하는 대신, G2PO는 학생이 같은 주제로 치른 10개의 서로 다른 시험을 살펴봅니다. 만약 학생이 10번 중 7번은 맞히고 3번은 틀렸다면, 선생님은 "아, 이 학생은 이 주제를 잘 이해하고 있구나. 3번의 실수는 그저 운이 나빴던 거야"라고 판단합니다.
결과: 이를 통해 로봇이 운이 나빠서 겪은 일 때문에 벌을 받는 것을 방지하고, 설령 나중에 실수하여 최종 결과가 실패로 끝났더라도, 로봇이 내린 결정이 좋았다면 그에 대해 보상을 해줍니다.

3. 목적지가 아닌 '발걸음'을 판단하기 (Edge-Centric Advantage)

기존 방식은 로봇의 움직임을 바로 그 순간의 방에서 가능한 다른 움직임들과만 비교하곤 합니다.
G2PO는 도약의 가치 자체를 살핍니다. "이 특정 움직임이 로봇을 시작 지점보다 얼마나 더 목표에 가깝게 만들었는가?"라고 묻습니다.

비유: 등산객이 산을 오르고 있다고 상해 봅시다.
- 기존 방식: "방금 한 걸음 위로 올라갔네. 좋아. 그런데 나중에 또 한 걸음 올라갔네. 첫 번째 걸음이 두 번째 걸음보다 더 나았을까?" (국소적인 비교)
- G2PO: "너는 바닥(낮은 가치)에서 시작했어. 그런데 한 걸음을 내디뎌서 산 중턱(높은 가치)에 도착했구나. 이건 정말 엄청난 도약이었어! 설령 네가 나중에 절벽에서 떨어졌더라도, 그 특정 발걸음은 정말 훌륭했어."
결과: G2PO는 실제로 과업을 진전시키는 "결정적인 도약"을 식별하여 추가 점수를 주는 한편, 별로 중요하지 않은 사소한 움직임은 무시합니다.

4. 이것이 왜 중요한가

이 논문은 세 가지 어려운 과업에 대해 테스트를 진행했습니다:

WebShop: 온라인 쇼핑하기.
ALFWorld: 가상의 집에서 집안일 하기.
AppWorld: 앱을 관리하는 코드 작성하기.

결과:

로봇은 훨씬 더 빠르게 학습했고 실수도 적게 했습니다.
기존 방식보다 성공률이 현저히 높았습니다 (어떤 경우 최대 22% 더 높은 성능).
가장 놀라운 점: 이 모든 것을 더 많은 컴퓨터 자원을 사용하지 않고도 해냈습니다. 단지 이미 가지고 있는 데이터를 더 똑똑하게 정리했을 뿐입니다 (마치 더 큰 책상을 사는 대신, 물건을 빨리 찾기 위해 책상을 깔끔하게 정리하는 것과 같습니다).

요약하자면:
G2PO는 로봇의 학습 여정을 하나의 취약한 선으로 취급하는 것을 멈춥니다. 대신, 모든 가능성을 담은 지도를 만들고, 운의 요소를 평균 내어 진실을 찾아내며, 목표에 더 가까이 다가가게 만든 구체적인 발걸음에 보상을 줍니다. 이는 마치 하나의 경로만 보여주는 GPS에서, 도시 전체를 파악하고 어떤 회전이 가장 중요한지를 알려주는 스마트 내비게이션 시스템으로 업그레이드하는 것과 같습니다.

기술 요약: 장기 호라이즌 에이전트 강화 학습을 위한 그룹-그래프 정책 최적화 (G2PO)

문제 정의

대규모 언어 모델(LLM)이 단순한 챗봇을 넘어 복잡하고 실제적인 문제를 해결할 수 있는 자율 에이전트로 진화하기 위해서는 견고한 장기 호라이즌(long-horizon) 의사결정 능력이 필요합니다. 강화 학습(RL)은 단일 턴 작업(예: 수학 및 코딩)에서의 추론 능력을 향상시키는 데 성공했지만, 이를 멀티 턴 에이전트 시나리오에 적용하는 데는 상당한 어려움이 따릅니다.

기존의 에이전트 RL 프레임워크는 컨텍스트 폭발과 메모리 소비를 완화하기 위해 궤적 수준(trajectory-level)에서 스텝 수준(step-level) 학습으로 전환해 왔습니다. 그러나 이러한 스텝 수준 접근 방식은 장기 호라이즌 작업에서 두 가지 결정적인 한계를 가집니다:

상태 가치 추정의 높은 분산: 현재의 방법들은 에이전트의 탐색을 고립된 선형 궤적들의 집합으로 취급합니다. 동일한 환경 상태에서 시작한 서로 다른 궤적들이 확률성으로 인해 매우 다른 결과에 도달할 수 있기 때문에, 단일 궤적의 보상만으로 상태의 가치를 추정하는 것은 신뢰할 수 없으며 분산이 매우 높습니다.
조밀하지 못한 크레딧 할당(Credit Assignment): 기존의 스텝 수준 방법(예: GiGPO)은 일반적으로 동일한 상태를 가진 로컬 그룹 내에서만 액션을 비교합니다. 이러한 국소적 관점은 전역적 중요성을 포착하지 못합니다. 즉, 사소한 상태에서의 미미한 개선과 최종 목표를 향한 절대적 진전을 이끄는 결정적인 돌파구로서의 액션을 구분하지 못하여, 근시안적인 크레딧 할당을 초래합니다.

또한, 장기 호라이즌 작업은 피드백이 수십 번의 상호작용 단계가 끝난 후에야 주어지는 희소한 보상(sparse rewards)의 특성을 가지므로, 중간 단계의 크레딧 할당이 어렵습니다.

방법론: 그룹-그래프 정책 최적화 (G2PO)

이러한 병목 현상을 해결하기 위해 저자들은 선형 상호작용 궤적을 전역적인 **상태 전이 그래프(state-transition graph)**로 명시적으로 변환하는 새로운 그룹 기반 RL 알고리즘인 **그룹-그래프 정책 최적화(G2PO)**를 제안합니다.

1. 상태 그룹 그래프 구축

궤적을 독립적인 선으로 취급하는 대신, G2PO는 모든 샘플링된 궤적 전반에 걸쳐 동일하거나 유사한 환경 관측값들을 상태 그룹(노드)으로 집계합니다. 에이전트의 액션은 이 노드들을 연결하는 유향 에지(edge) 역할을 하여 통합된 상태 전이 그래프를 형성합니다. 이 구조는 서로 다른 궤적들이 종종 동일한 환경 상태(예: 동일한 웹페이지 또는 물리적 구성)로 수렴한다는 점을 인정합니다.

2. 그룹 집계 상태 가치 추정

단일 궤적 평가에 내재된 높은 분산을 완화하기 위해, G2PO는 그룹 집계 메커니즘을 도입합니다:

메커니즘: 임의의 상태 그룹 $G_k$ 에 대해, 가치 $V(G_k)$ 는 모든 샘플링된 궤적 중 해당 그룹에 속하는 모든 중간 단계의 할인된 리턴(discounted returns)의 평균으로 정의됩니다.
이점: 동일한 상태를 통과하는 여러 궤적의 결과를 평균함으로써, 이 방법은 단일 샘플의 우연한 결과가 아닌 해당 상태의 내재적인 기대 가치를 추정합니다. 이론적 분석에 따르면, 이는 그룹 크기에 비례하여 가치 추정의 분산을 선형적으로 감소시킵니다.

3. 다중 입도(Multi-Granularity) 어드밴티지 추정

G2PO는 조밀하고 세밀한 피드백을 제공하기 위해 세 가지 유형의 어드밴티지를 합성합니다:

노드 중심 어드밴티지 (ANC): 현재 노드에서 가능한 모든 다음 상태들의 평균 가치와 결과 상태의 가치를 비교하여 액션을 평가합니다. 이는 국소적인 선호도를 포착합니다.
에지 중심 어드밴티지 (AEC): 이것이 핵심 혁신입니다. 액션은 상태 노드 간의 전이로 취급됩니다. 어드밴티지는 시간차(Temporal Difference, TD) 오차 ( $\delta = V_{next} - V_{current}$ )를 기준으로 계산되며, 이는 전이의 절대적인 가치 획득을 나타냅니다. 결정적으로, 이 TD 오차는 특정 상태 그룹 내에서가 아니라 전체 그래프 전체에 걸쳐 전역적으로 표준화됩니다. 이를 통해 G2PO는 특정 궤적이 결국 실패하더라도, 실질적인 절대적 진전을 이끄는 결정적인 전이를 명시적으로 식별하고 우선순위를 정할 수 있습니다.
에피소드 수준 어드밴티지 (AEP): 학습 과정이 궁극적인 태스크 목표와 일치하도록 유지하기 위해 표준 GRPO에서 유지되었습니다.

최종적인 스텝의 어드밴티지는 다음 구성 요소들의 가중 결합입니다:
$A_{ij} = A_{EP}(a_{ij}) + w \cdot (A_{NC}(a_{ij}) + A_{EC}(a_{ij}))$

주요 기여

본 논문은 네 가지 주요 기여를 설명합니다:

G2PO 알고리즘: 선형 궤적을 상태 그룹 그래프로 변환하도록 설계된 장기 호라이즌 에이전트 작업용 그룹 기반 RL 알고리즘입니다.
그룹 집계 상태 가치 추정: 서로 다른 궤적의 동일한 상태들에 대한 결과를 집계함으로써 상태 가치 추정의 높은 분산을 해결하는 방법입니다.
에지 중심 어드밴티지 추정: 액션을 전이로 재정의하고 전역적으로 표준화된 TD 오차를 통해 글로벌 진전에 대한 절대적 기여도를 측정함으로써, 국소적 그룹 비교의 한계를 극복하는 전략입니다.
실증적 검증: G2PO가 무시할 만한 계산 오버헤드로 최신 베이스라인들을 능가함을 보여주는 광범적인 실험을 수행했습니다.

실험 결과

저자들은 세 가지 대표적인 장기 호라이즌 벤치마크인 WebShop(이커머스), ALFWorld(체화된 물리 환경), AppWorld(복잡한 소프트웨어 생태계)에서 G2PO를 평가했습니다. 실험은 Qwen-2.5 모델(1.5B, 7B, 14B)을 사용하여 진행되었습니다.

성능: G2PO는 프롬프트 기반 방법(예: ReAct, Reflexion)과 RL 베이스라인(PPO, RLOO, GRPO, GiGPO)을 일관되게 능가했습니다.
- WebShop에서 G2PO는 GRPO 대비 최대 **22.2%**의 성공률 향상을 달了했습니다.
- ALFWorld에서 GRPO 대비 **14.4%**의 향상을 달성했습니다.
- AppWorld에서 G2PO는 다른 모든 RL 학습 방법을 앞서며 복잡한 API 기반 작업에 대한 강력한 일반화 능력을 입증했습니다.
효율성: G2PO로 학습된 모델은 GRPO 및 GiGPO에 비해 작업을 완료하는 데 필요한 상호작용 턴 수가 적었으며, 이는 의사결정 효율성이 향상되었음을 나타냅니다.
계산 비용: 그래프 구축 및 어드밴티지 추정 파이프라인은 전적으로 CPU 프로세싱에 의존합니다. 저자들은 G2PO가 학습 단계당 약 1초의 추가 오버헤드(전체 시간의 약 0.4%)만을 발생시켜, 기본 GRPO 프레임워크의 높은 효율성을 유지한다고 보고했습니다.

의의 및 주장

본 논문은 G2PO가 고립된 선형 궤적에서 전역 그래프 구조로 관점을 전환함으로써 에이전트 RL의 중요한 진보를 이루었다고 주장합니다. 상태 전이 그래프를 명시적으로 모델링하고 그룹 집계를 활용함으로써, 이 방법은 학습된 크리틱 네트워크의 계산 오버헤드나 프로세스 보상 모델(PRM)의 어노테이션 비용 없이 희소한 보상이 발생하는 장기 호라이즌 시나리오의 크레딧 할당 문제를 효과적으로 해결합니다.

저자들은 이 접근 방식이 경험적 평균을 활용하는 철학(GRPO에서 볼 수 있는 것과 같이)을 따르면서도, 이를 상태 전이의 구조적 수준으로 확장한 것이라고 강조합니다. 결과는 멀티 턴 상호작용의 내재된 그래프 구조를 인식하는 것이 분산을 줄이고 결정적인 돌파 액션을 식별하여, 복잡한 에이전트 작업에서 상당한 성능 향상을 이끄는 데 매우 중요하다는 것을 시사합니다.