기술 요약: 수학적 강화 학습에서의 투 험프(Two-Hump) 문제

문제 정의

본 논문은 조합군론(combinatorial group theory)의 저명한 미해결 난제인 앤드류스-커티스(Andrews–Curtis, AC) 추측에 강화 학습(RL)을 적용할 때 발생하는 과제를 다룹다. 이 추측은 균형 잡힌 자명한 군(balanced presentation of the trivial group)의 표현이 특정 일련의 이동(AC1: 역원, AC2: 공액/연결, AC3: 순환 치환)을 통해 자명한 표현 $\langle x, y \mid x, y \rangle$로 변환될 수 있음을 상정한다.

핵심적인 어려움은 탐색 공간의 본질에 있다:

1. 방대한 탐색 공간: 가능한 표현들의 그래프는 무한하다.
2. 희소한 보상(Sparse Rewards): 에이전트는 완전한 자명화에 도달했을 때만 보상을 받는다. 중간 단계의 실패 신호나 부분적인 진행 지표가 존재하지 않는다.
3. "투 험프(Two-Hump)" 현상: 저자들은 문제 사례들이 이봉 분포(bimodal distribution)를 보이는 결정적인 구조적 장벽을 식별했다. 대부분의 표현은 사소하게 해결 가능(단순한 탐욕적 길이 감소를 통해)하거나, 사실상 불가능(길이를 일시적으로 증가시키는 경로를 요구하며, 표준 휴리스틱은 이를 거부함)하다. 결정적으로, "어렵지만 해결 가능한" 중간 단계의 사례가 부족하여 커리큘럼 학습을 방해하는 "골짜기(valley)"가 형성된다.

방법론

어려움의 간극을 메우고 투 험프 분포를 극복하기 위해, 저자들은 알고리즘 혁신, 아키텍처 설계, 그리고 표적화된 데이터 생성을 결합한 세 가지 접근 방식을 제안한다.

1. 행동 공간: 치환 슈퍼무브(Substitution Supermoves)

기본적인 AC 이동 대신, 저자들은 **치환 이동(substitution moves)**을 주요 행동 공간으로 도입한다.

• 메커니즘: 치환은 관계식(relator)을 순환 시퀀스로 취급하고, 상쇄가 발생하는 지점에서 하나를 다른 하나에 삽입한다. 이는 여러 기본 이동(AC1, AC2, AC3)을 하나의 행동으로 결합한다.
• 이점: 이를 통해 에이전트는 AC 그래프를 통해 더 크고 의미 있는 단계를 밟을 수 있으며, 순환 치환을 무시함으로써 유효 상태 공간을 크게 줄일 수 있다.
• 이론적 근기: Ivanov(2018)는 AC 추측이 참이라면, 치환이 모든 AC 변환을 실현하기에 충분하다는 것을 증명했다.

2. 아키텍처: 듀얼 링 트랜스포머(Dual-Ring Transformer)

치환의 거대하고 구조화된 행동 공간을 처리하면서 문제의 수학적 대칭성을 존중하기 위해, 저자들은 듀얼 링 트랜스포머를 개발했다.

• 순환 대칭성: 절대적 위치 인코딩을 사용하는 표준 트랜스포머와 달리, 이 아키텍처는 관계식을 순환 링으로 취급한다. 이는 어텐션 점수가 순환 거리 $d(i, j) = (i - j) \mod L$에 의존하는 순환 상대적 위치 인코딩을 채택한다.
• 교차 어텐션(Cross-Attention): 네트워크는 두 관계식을 병렬로 처리하며, 교차 어텐션을 사용하여 $r_1$과 $r_2$ 사이의 일치하는 부분 문자열을 식별한다. 이는 유효한 치환 이동을 결정하는 데 매우 중요하다.
• 정책 헤드(Policy Head): 출력은 유효한 치환 이동에 대한 분포이며, 상쇄가 발생하는 경우($r_1[i] = \pm r_2[j]$)에만 비제로 확률을 갖도록 마스킹된다.

3. 데이터 생성: 골짜기 채우기

표준적인 "스크램블링(scrambling)" 전략이 어렵지만 해결 가능한 사례를 생성하는 데 실패한다는 점을 인식하여, 저자들은 두 가지 새로운 데이터 생성 기법을 사용한다.

• 자기동형사상 섭동(Automorphism Perturbation): 알려진 자명한 표현(예: $AK(2)$)에 자기동형사상을 적용하면, 표현의 경로 특성이 급격히 변화한다. 원래의 표현은 쉬울 수 있지만, 그 자기동형 이미지는 길이를 증가시키는 단계를 요구할 수 있어, 이를 "쉬운" 언덕에서 "골짜기"로 이동시킨다.
• 생성자-해결사 게임(Generator-Solver Game): 비대칭적인 2인 게임을 구성한다. 생성자(PPO 에이전트)는 자기동형사상 시퀀스를 적용하여 표현의 난이도를 높이고, 해결사(탐욕적 탐색)는 이를 자명화하려고 시도한다. 생성자는 해결사를 어렵게 만드는 사례, 특히 중간 난이도 영역을 타겟팅하도록 보상을 받는다.
• 결과 데이터셋: 이 과정은 AC-19(길이 $\le 19$인 125,192개의 짧은 AC-자명 표현)와 AC-1M(길이 $\le 30$인 1,136,154개의 어려운 AC-자명 표현)을 생성하며, 이는 이와 같은 종류의 최초 대규모 공개 데이터셋이다.

주요 결과

저자들은 1,190개의 표현으로 구성된 Miller–Schupp 벤치마크 데이터셋에서 방법론을 평가했다.

• 성능 향상: 치환 슈퍼무브와 듀얼 링 트랜스포머를 결합한 모델(PPO-Sub-DRT)은 610개의 표현을 해결했으며(5개 시드 평균), 이는 이전 최상위 RL 베이스라인인 457개(PPO-AC-ResNet)보다 유의미하게 증가한 수치이다.
• 데이터의 영향: 생성된 AC-1M 데이터셋을 포함했을 때 성능이 더욱 향려되었으며, 이는 표적화된 데이터 생성이 에이전트가 어려운 표현에 대한 일반적인 전략을 학습하는 데 성공적으로 기여함을 입증한다.
• 경로 효율성: 치환을 사용하는 탐욕적 탐색(GS)이 더 많은 사례(640개)를 해결하지만(철저한 탐색 덕분), PPO 에이전트는 특히 어려운 표현에서 상당히 짧은 해결 경로를 찾아낸다. PPO는 탐욕적 휴리스틱이 거부하는 길이 증가 우회 경로를 식별함으로써, 비자명한 수학적 구조를 학습했음을 증명한다.
• 아키텍처의 우월성: 절대적 인코딩을 사용하는 정형화(canonical form) 전처리 방식의 변형 모델보다 듀얼 링 트랜스포머(순환 상대적 인코딩 사용)가 약 25개의 표현을 더 많이 해결함으로써, 대칭성을 인식하는 표현 학습의 중요성을 보여주었다.
• 수학적 진전: 저자들은 이전에 해결되지 않았던 Miller–Schupp 패밀리의 100개 이상의 표현을 성공적으로 자명화했다. 남은 550개의 미해결 사례를 **261개의 뚜렷한 AC 동치류(AC-equivalence classes)**로 축소함으로써, 향후 연구를 위한 구체적인 체크리스트를 제공했다.

의의 및 주장

본 논문은 앤드류스-커티스 추측에 대한 진전이 단순히 컴퓨팅 자원을 확장하는 것이 아니라, 문제 고유의 난이도 구조를 이해하는 데서 온다고 주장한다.

• 투 험프 통찰: 이봉 난이도 분포의 식별은 왜 기존 접근 방식이 어려움을 겪었는지 설명하며, 알고리즘 개선과 표적화된 데이터 생성을 결합해야 할 필요성을 뒷받침한다.
• 희소 보상 환경에서의 RL: 본 연구는 수백 번의 정밀한 순차적 결정이 필요한 극도로 희소한 보상 환경에서도 RL이 성공할 수 있음을 보여주며, 로보틱스, 정리 증명, 프로그램 합성 분야로 전이 가능한 통찰을 제공한다.
• 수학적 유용성: AC 추측이 최종적으로 참인지 거짓인지와 상관없이, 본 연구는 구체적인 진전을 이룬다. 만약 참이라면, 모든 새로운 자명화는 증명에 기여하는 것이며, 만약 거짓이라면, 겉보기에 자명해 보이는 반례를 자명화함으로써 진정한 반례를 찾는 범위를 좁혀준다.
• 전이 가능성: "투 험프" 구조와 개발된 기술들(치환, 순환 아키텍처, 생성자-해결사 게임)은 이봉 난이도 분포와 진행을 방해하는 이동이 존재하는 다른 수학적 탐색 문제에도 일반화될 수 있는 것으로 제시된다.

저자들은 향후의 진전이 고전적 탐색의 미세한 개선에서 오는 것이 아니라, 고정된 휴리스틱이 포착할 수 있는 범위를 넘어서는 구조를 활용할 수 있는 학습 기반 방법론에서 올 것이라고 결론짓는다.