💻 computer science

Hierarchical Deep Counterfactual Regret Minimization

이 논문은 사전 정의된 전문 지식과 전이 가능한 기술의 사용을 가능하게 함으로써 대규모 불완전 정보 게임을 해결하는 효율성을 높이기 위해, 기술 기반 계층적 전략 학습을 Deep CFR과 통합한 새로운 알고리즘인 계층적 딥 카운터팩추얼 레그렛 최소화(Hierarchical Deep Counterfactual Regret Minimization, HD CFR)를 소개한다.

원저자: Jiayu Chen, Xudong Wu, Zhekai Wang, Vaneet Aggarwal

게시일 2026-10-05

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Jiayu Chen, Xudong Wu, Zhekai Wang, Vaneet Aggarwal

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

인공지능의 세계에서 가장 어려운 과제 중 일부는 플레이어가 보드 전체를 볼 수 없는 게임에서 발생합니다. 포커 테이블을 생각해 보십시오. 당신은 자신의 카드와 테이블 위의 카드는 알지만, 상대방이 무엇을 들고 있는지는 전혀 알 수 없습니다. 이러한 불완전한 정보는 모든 결정이 숨겨진 가능성에 대비해 무게를 달아야 하는 불확실성의 풍경을 만들어냅니다. 수십 년 동안 연구자들은 컴퓨터에게 이러한 게임을 플레이하는 법을 가르치기 위해 '역사실적 후회 최소화(counterfactual regret minimization)'라고 불리는 방법을 사용해 왔습니다. 그 논리는 간단합니다. 게임이 끝난 후, 컴퓨터는 자신이 내린 모든 선택을 되돌아보며 "만약 내가 다른 선택을 했다면 어땠을까?"라고 자문합니다. 만약 그 선택을 바꿈으로써 더 나은 결과를 얻을 수 있었다면, 컴퓨터는 일종의 '후회'를 느낍니다. 수백만 번의 게임을 거치며 컴퓨터는 이 후회를 최소화하는 법을 배우고, 결국 어떤 상대도 일관되적으로 이길 수 없는 강력한 전략에 도달하게 됩니다. 이 접근 방식은 역사상 가장 강력한 포커 플레이 AI들을 탄생시켰습니다.

하지만 게임이 너무 복잡해지면 큰 문제가 발생합니다. 단순한 포커 변형 모델에서는 컴퓨터가 게임이 진행될 수 있는 모든 가능한 경로를 그려낼 수 있습니다. 하지만 플레이 시퀀스가 더 긴 복잡한 버전에서는 가능한 경로의 수가 수조 개로 폭발합니다. 모든 경로를 확인하여 후회를 계산해야 하는 전통적인 방식은 컴퓨터가 우주에 존재하는 것보다 더 많은 데이터를 처리해야 하기 때문에 불가능해집니다. 이를 해결하기 위해 연구자들은 딥러닝을 활용하여, 모든 가능성을 확인하는 대신 신경망을 통해 적절한 수를 추측하도록 했습니다. 그럼에도 불구하고, 이러한 고급 시스템들조차 게임이 긴 지평에 걸쳐 길게 늘어질 때 어려움을 겪으며, 단 몇 개의 경로만을 샘플링하여 생성된 엄청난 양의 무작위 노이즈 속에서 길을 잃곤 합니다. 이들은 인간이 수천 개의 개별 단계를 기억하려 애쓰는 대신 몇 가지 익숙한 루틴을 인식하는 것처럼, 자신의 사고를 관리 가능한 덩어리로 조직화하는 방법을 갖추지 못했습니다.

홍콩 대학교, 북경 대학교, 퍼듀 대학교의 연구팀은 이러한 한계를 극복하기 위해 설계된 '계층적 딥 역사실적 후회 최소화(Hierarchical Deep Counterfactual Regret Minimization, HDCFR)'라는 새로운 접근 방식을 도입했습니다. 연구 논문에 발표된 이들의 작업은 AI에게 모든 작은 움직임을 처음부터 학습하도록 강요하는 대신, '기술(skills)'을 먼저 배우도록 가르쳐야 한다고 제안합니다. 이 시스템에서 AI는 특정 베팅 패턴이나 방어 기동과 같이 게임의 작은 부분을 해결하기 위한 구체적인 기술로서 작용하는 저수준 구성 요소를 학습합니다. 그러면 고수준 구성 요소가 매 순간 어떤 기술을 사용할지, 그리고 언제 기술을 전환할지를 결정하는 관리자 역할을 수행합니다. 이 구조는 인간이 게임을 하는 방식을 모방합니다. 우리는 운전할 때 근육의 모든 움직임을 생각하지 않고, '좌회전', '차선 변경', '정지'와 같은 개념으로 생각하며 상황이 변함에 따라 이러한 고수준의 목표 사이를 전환합니다.

연구진은 전체 게임 트리가 너무 커서 볼 수 없는 환경, 즉 '모델 프리(model-free)' 설정에서도 작동하도록 알고리즘을 구축했습니다. 이러한 시나리오에서 AI는 가능한 모든 미래를 보기 위해 앞을 내다볼 수 없으며, 오직 몇 개의 경로만을 샘플링하고 그 결과로부터 학습할 수 있습니다. 학습 과정이 무작위적인 변동으로 인해 불안정해지지 않도록 하기 위해, 팀은 분산 감소 기법을 도입했습니다. 이는 AI가 진정으로 좋은 전략과 운 좋게 얻은 결과를 구분할 수 있도록 돕는 안정 장치 역할을 합니다. 연구진은 이 계층적 방법이 최적의 전략으로 수렴한다는 것을 수학적으로 증명했습니다. 즉, 이 방식은 기존 방식처럼 결국 완벽하게 플레이하는 법을 배우게 되지만, 훨씬 더 깊고 복잡한 게임을 다룰 수 있는 능력을 추가로 갖추게 된다는 의미입니다.

HDCFR은 분야 내 가장 강력한 기존 알고리즘들과 테스트했을 때, 특히 게임이 어려워질수록 명확한 우위를 보여주었습니다. 연구진은 몇 장의 카드로 이루어진 단순한 변형 모델부터 30조 개 이상의 노드를 가진 복잡한 버전의 포커에 이르기까지 여러 버전의 포커로 시스템을 평가했습니다. 단순한 게임에서는 이 새로운 방식이 기존의 최고 도구들과 대등한 성능을 보였습니다. 그러나 게임이 길어지고 결정 지평이 확장됨에 따라 기존 방식들은 흔들리기 시작했고, 성능이 불규칙해지거나 개선되지 못했습니다. 반면, HDCFR은 효과적으로 학습을 지속하며 더 높은 수준의 플레이에 도달했습니다. 연구진은 계층적 구조 덕분에 게임이 길어져도 AI가 안정성을 유지할 수 있었으며, 이는 이전의 딥러닝 방식들이 데이터의 노이즈에 압도되지 않고는 달성할 수 없었던 성과라고 밝혔습니다.

본 연구의 핵심 발견 중 하나는 한 작업에서 다른 작업으로 지식을 전이하는 능력입니다. 연구진은 AI를 더 단순한 버전의 게임으로 훈련시킨 후, 그것이 배운 것을 더 복잡한 버전에 적용하도록 했습니다. 그들은 AI가 습득한 저수준 기술(예: 특정 베팅 전략)이 더 어렵고 새로운 게임에서도 재사용될 수 있다는 것을 발견했습니다. 이러한 기술 전이는 학습 과정을 크게 가속화했습니다. 어떤 경우에는 AI가 기초적인 것을 다시 배울 필요 없이, 이러한 기술들의 고수위 관리에만 온전히 집중할 수 있었습니다. 이는 시스템이 단순히 특정 게임을 암기하는 것이 아니라, 새로운 도전에 적응할 수 있는 유연한 도구 세트를 실제로 학습하고 있음을 시사합니다. 또한 연구진은 AI가 이러한 기술을 장기간 사용하는 것을 관찰했는데, 때로는 하나의 전략을 바꾸기 전까지 열 번 이상의 수 동안 하나의 전략을 고수하기도 했습니다. 이는 인간 전문가들이 개별적인 행동이 아닌 단계(phases)의 관점에서 생각하는 방식과 유사합니다.

연구에는 시스템의 특정 부분이 제거되었을 때 어떤 일이 발생하는지에 대한 상세한 분석도 포함되었습니다. 연구진이 AI가 기술을 일정 시간 동안 지속하도록 하는 메커니즘을 제거했을 때, 시스템은 기존 방식들과 마찬가지로 수렴에 어려움을 겪었습니다. 마찬가지로 분산 감소 안정 장치를 제거했을 때, 특히 긴 게임에서 학습 성능이 현저히 떨어졌습니다. 이러한 테스트는 계층적 구조와 노이즈 감소 기술 모두가 깊고 복잡한 환경에서 시스템이 작동하는 데 필수적임을 확인시켜 주었습니다. 연구진은 이 시스템을 훈련하는 데 가장 큰 게임의 경우 표준 서버에서 약 일주일 정도 소요되는 상당한 컴퓨팅 파워가 필요하다고 언급했지만, 결과는 거대한 상태 공간을 가진 게임을 위한 실질적인 경로를 보여줍니다.

궁극적으로, 이 작업은 불확실성 하에서의 복잡한 의사결정에 접근하는 방식의 변화를 나타냅니다. 기술과 관리자의 계층 구조로 학습을 조직함으로써, 연구진은 이전보다 더 효과적으로 광대하고 숨겨진 불완전 정보 게임의 풍경을 탐색할 수 있는 시스템을 만들었습니다. 이 연구 결과는 AI가 가장 복잡한 전략적 과제를 정복하기 위해서는 모든 가능성을 계산하려고 노력하는 대신, 구조화되고 재사용 가능한 기술의 관점에서 생각하는 법을 배우기 시작해야 한다는 점을 시사합니다. 이러한 접근 방식은 게임 성능을 향상시킬 뿐만 아니라, 정보가 불완전하고 미래를 상세히 지도화하기에는 너무나 방대한 실제 세계에서 지능형 에이전트가 어떻게 작동하는지를 배우는 데 대한 청사진을 제공합니다.

기술 요약: 계층적 딥 카운터팩추얼 레그렛 미니마이제이션 (HDCFR)

문제 정의

포커와 같은 불완전 정보 게임(IIG)은 에이전트가 완전한 상태 정보를 갖지 못하는 불확실성 하에서의 의사결정을 모델링합니다. 카운터팩추얼 레그렛 미니마이제이션(CFR)은 IIG를 해결하기 위한 지배적인 알고리즘이지만, 표준 테이블 방식의 CFR은 매 반복마다 전체 게임 트리를 순회해야 하므로, 상태 공간이 방대하고 의사결정 수평(decision horizon)이 깊은 게임에서는 실행이 불가능합니다. 딥 러닝 확장 방식인 Deep CFR은 확장성을 개선했지만, 백트래킹을 위해 명시적인 게임 모델에 의존하거나, 결과 샘플링만 가능한 모델 프리(model-free) 환경에서 높은 분산을 겪는 경우가 많습니다. 또한, 기존의 딥 러닝 방법들은 대개 평면적인(flat) 전략을 학습하며, 인간과 유사한 계획 능력을 모방하거나 유사한 작업 간의 지식 전이를 용이하게 하는 도메인 특화 기술 또는 계층적 의사결정 구조를 통합하는 능력이 부족합니다.

방법론

본 논문은 대규모 모델 프리 IIG를 위해 설계된 최초의 계층적 Deep CFR 확장형인 **계층적 딥 카운터팩추얼 레그렛 미니마이제이션 (HDCFR)**을 제안합니다. 방법론은 세 가지 단계적 과정으로 개발되었습니다.

1. 이론적 토대: 계층적 CFR (HCFR)

저자들은 계층적 전략을 포함하도록 표준 IIG 정의를 확장했습니다. 각 단계에서 에이전트의 결정은 옵션(skill) $z_t$ 와 원시 행동(primitive action) $a_t$ 로 구성된 계층적 행동 $(z_t, a_t)$ 로 이루어집니다.

전략 분해: 전략 $\sigma_i$ 는 고수준 정책 $\sigma^H_i(z|I)$ (옵션 선택)와 저수준 정책 $\sigma^L_i(a|I, z)$ (옵션 내 행동 실행)로 분해됩니다.
레그렛 분해: 단일 글로벌 레그렛을 최소화하는 대신, HCFR은 고수준 카운터팩추얼 레그렛( $R^H$ )과 저수준 카운터팩추얼 레그렛( $R^L$ )의 합을 최소화합니다.
수렴성: 저자들은 이러한 분해된 레그렛들을 독립적으로 최소화하는 것이 표준 테이블 CFR과 동일한 수렴 속도( $O(T^{-0.5})$ )로 내쉬 균형(NE)에 도달함을 증명합니다.

2. 모델 프리 확장: 저분산 몬테카를로 샘플링

전체 트래버설이 불가능한 깊은 게임 트리를 다루기 위해, 저자들은 HCFR을 모델 프리 결과 샘플링(Outcome Sampling, OS) 환경에 적응시켰습니다.

불편 추정량(Unbiased Estimators): 이들은 계층적 카운터팩추얼 레그렛을 위한 불편 몬테카를로 추정량을 도출합니다.
분산 감소: 장기 호환 샘플링이 높은 분산을 유발한다는 점을 인식하여, 저자들은 베이스라인 함수 $b_t$ 를 도입했습니다. 이론적 분석(정리 5)을 통해 베이스라인을 상태의 기대값과 일치시키면 레그렛 추정량의 분산이 최소화됨을 입증했습니다. 이는 깊은 게임에서 학습을 안정화하는 데 매우 중요합니다.

3. 딥 근사: HDCFR

마지막으로, 무한한 상태 공간을 처리하기 위해 신경망(NN)을 사용하여 테이블 함수를 근사합니다.

네트워크 아키텍처: 시스템은 세 가지 유형의 네트워크를 학습시킵니다:
1. 레그렛 네트워크: 누적 카운터팩추얼 레그렛( $R^H, R^L$ )을 근사합니다.
2. 전략 네트워크: 평균 전략( $\sigma^H, \sigma^L$ )을 근사합니다.
3. 베이스라인 네트워크: 분산 감소를 위해 가치 함수를 근사합니다.
학습 목표: 네트워크는 정확한 피팅 하에서 테이블 타겟과 일치하도록 학습됩니다. 구체적으로, 레그렛 네트워크는 예측된 값과 샘플링된 즉각적 레그렛 사이의 제곱 오차를 최소화하며, 전략 네트워크는 예측된 값과 샘플링된 평균 전략 사이의 오차를 최소화합니다.
단일 단계 옵션 프레임워크: 고수준 정책은 멀티 헤드 어텐션(MHA) 메커니즘을 활용하여 현재 옵션을 계속 유지할지 아니면 새로운 옵션으로 전환할지를 동적으로 결정하며, 이를 통해 명시적인 종료 조건 없이도 효과적으로 시간적 추상화(temporal abstraction)를 학습합니다.

주요 기여

최초의 계층적 CFR: 본 논문은 최초의 계층적 Deep CFR 버전을 도입하여, IIG에서 계층적 전략을 학습하기 위한 이론적 수렴 보장을 확립했습니다.
모델 프리 분산 감소: 불편 몬테카를로 추정량과 이론적으로 근거가 있는 베이스라인 함수를 포함하여, 장기 태스크에서 분산을 제어하는 샘플 기반의 모델 프리 계층적 CFR을 제안했습니다.
확장 가능한 딥 러닝 통합: HDCFR은 이러한 이론적 구성 요소들을 신경망과 성공적으로 결려하여, 테이블 설정의 수렴 속성을 유지하면서도 방대한 상태 공간에서 학습할 수 있게 합니다.
기술 전이 가능성: 이 프레임워크는 유사한 작업에서 사전 학습된 기술(옵션)을 사용할 수 있게 하여, 새로운 IIG에서의 학습 속도를 높이고 전이를 용이하게 합니다.

실험 결과

저자들은 Leduc Hold'em 및 Heads-Up Flop Hold'em (FHP)를 포함하여 결정 수평(스택 크기 및 레이즈 횟수)이 증가하는 다양한 포커 벤치마크에서 HDCFR을 평가했습니다.

SOTA 대비 성능: HDCFR은 DREAM, OSSDCFR, NFSP, ESCHER와 비교되었습니다.
- 심층 수평(Leduc 15, 20)의 Leduc 변형에서, HDCFR은 베이스라인 모델들에 비해 현저히 낮은 착취 가능성(exploitability, NE에 더 가까움)을 달acia했습니다. DREAM이 이러한 깊은 수평 설정에서 수렴에 어려움을 겪는 동안, HDCFR은 안정성을 유지했습니다.
- FHP 벤치마크(노드 수가 $10^{12}$ 개를 초과하는 게임 트리)에서, HDCFR은 DREAM, OSSDCFR, NFSP를 상대로 양의 평균 페이오프를 달성하며 우수한 성능을 보여주었습니다.
절제 연구(Ablation Studies):
- 멀티 헤드 어텐션(MHA) 컴포넌트를 제거하면 에이전트가 깊은 게임에서 수렴에 실패했으며, 이는 시간적 추상화의 필요성을 확인시켜 주었습니다.
- 베이스라인 함수를 제거하면 높은 분산으로 인해 성능이 크게 하락하여, 분산 감소 메커니즘의 유효성을 입증했습니다.
- 트래버서(traverser)의 샘플링 전략에서 탐색률( $\epsilon$ )을 높이는 것이 학습 성능을 향상시켰습니다.
기술 전이: 작은 규모의 Leduc 게임에서 학습된 기술을 Leduc 20으로 전이하는 실험을 통해, 사전 학습된 기술이 수렴을 가속화할 수 있음을 보여주었습니다. 이러한 기술을 고정하면 에이전트가 고수준 전략 선택에 집중할 수 있었고, 동적으로 조정하면 추가적인 최적화가 가능했습니다. 기술 전환 빈도 분석을 통해 고수준 정책이 매 원시 행동마다 전환하는 대신, 기술을 시간적으로 연장(평균 지속 시간 ~10 스텝)하도록 학습되었음을 확인했습니다.

의의 및 주장

본 논문은 옵션 프레임워크와 카운터팩추얼 레그렛 미니마이제이션을 결합함으로써 경쟁적인 다중 에이전트 시스템을 위한 새로운 프레임워크를 제공한다고 주장합니다. 주요 의의는 다음과 같습니다:

확장성: 결과 샘플링과 분산 감소를 활용하여 깊은 게임 트리에서의 백트래킹 한계를 해결합니다.
인간과 유사한 의사결정: 계층적 전략을 학습함으로써 기술과 하위 목표에 의존하는 인간의 의사결정 과정을 모방하며, 평면적 정책보다 더 나은 해석 가능성을 제공합니다.
전이 학습: 하나의 불완전 정보 게임에서 학습된 기술이 유사하고 더 복잡한 작업에 효과적으로 전이될 수 있음을 입증하여, 새로운 도메인에 대한 데이터 요구량을 줄입니다.

저자들은 HDCFR가 특히 결정 수평이 길어질수록 선도적인 모델 프리 알고리즘들을 능가하며, 복잡하고 깊은 수평을 가진 불완전 정보 게임을 해결하기 위한 새로운 기준을 세웠다고 결론짓습니다.