잠재 RL 액션 투영: 일반화 가능하고 확장 가능한 그래프 조합 최적화(Graph Combinatorial Optimization)를 향하여

그래프 조합 최적화 (Graph Combinatorial Optimization, GCO)는 많은 NP-hard 문제들이 자연스럽게 그래프 형식으로 표현될 수 있음에도 불구하고, 조합 폭발 (combinatorial explosion)로 인해 정확한 방법론을 사용하는 것이 계산적으로 다루기 어렵다는 점 때문에 점점 더 많은 관심을 끌고 있습니다. 최근 그래프 신경망 (Graph Neural Networks, GNNs)과 결합된 강화학습 (Reinforcement Learning, RL)의 발전은 학습 기반의 GCO 솔버들을 크게 개선해 왔습니다. 그러나 기존의 접근 방식들은 다양한 그래프 인스턴스에 대한 일반화 (generalization) 능력과 액션 공간 (action spaces)이 커짐에 따른 계산 확장성 (computational scalability) 측면 모두에서 한계에 직면해 있습니다. 이러한 두 가지 과제를 해결하기 위해, 우리는 연속적인 GNN 기반 액션 임베딩 공간 (action embedding space)에서 직접 작동하는 새로운 RL-GCO 접근 방식인 프로젝션 에이전트 (projection agents)를 소개합니다. 이 방식은 단 한 번의 순전파 (forward pass)를 통해 원하는 잠재 액션 (latent action)을 예측한 다음, 이를 유효한 이산 액션 (discrete action)으로 디코딩합니다. 또한, 관측값 (observations)과 액션 모두에 대해 공유된 임베딩 공간을 사용함으로써 RL 방법론 간의 공정한 비교를 가능하게 합니다. 다양한 벤치마크에서 우리의 접근 방식은 단순한 최근접 이웃 (nearest-neighbor) 디코딩만을 사용하는 기존 솔루션보다 최대 16.2배 빠른 추론 (inference) 속도와 최대 40% 더 나은 일반화 성능을 달성하였으며, 동시에 여러 상호 의존적인 변수가 존재하는 초선형 (super-linear) 결정 공간에서 강력한 RL 성능을 발휘할 수 있는 길을 열었습니다. 마지막으로, 우리는 잠재 액션 공간 구축을 자동화하고 기존의 RL-GCO 솔루션들을 지원하여 재현성 (reproducibility)과 새로운 GCO 벤치마크로의 적응을 촉진하는 Python 라이브러리인 LaGCO-RL을 공개합니다.