Learning Self-Game-Play Agents for Combinatorial Optimization Problems
원문 초록
Recent progress in reinforcement learning (RL) using self-game-play has shown remarkable performance on several board games (e.g., Chess and Go) as well as video games (e.g., Atari games and Dota2). It is plausible to consider that RL, starting from zero knowledge, might be able to gradually approximate a winning strategy after a certain amount of training. In this paper, we explore neural Monte-Carlo-Tree-Search (neural MCTS), an RL algorithm which has been applied successfully by DeepMind to play Go and Chess at a super-human level. We try to leverage the computational power of neural MCTS to solve a class of combinatorial optimization problems. Following the idea of Hintikka's Game-Theoretical Semantics, we propose the Zermelo Gamification (ZG) to transform specific combinatorial optimization problems into Zermelo games whose winning strategies correspond to the solutions of the original optimization problem. The ZG also provides a specially designed neural MCTS. We use a combinatorial planning problem for which the ground-truth policy is efficiently computable to demonstrate that ZG is promising.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
CityDeploy-Bench: 다중 송신기 네트워크 배치를 위한 물리 기반 공간 집합 계획 벤치마킹
CityDeploy-Bench: Benchmarking Physics-Grounded Spatial Set Planning for Multi-Transmitter Network Deployment
도시 규모의 무선 배치 자동화는 복잡한 도심 전파 환경과 네트워크 전역의 간섭 속에서 여전히 어려운 과제로 남아 있다. 본 논문에서는 다중 송신기 배치 문제를 통합된 광선 추적(ray-tracing) 검증기 하에서 물리 기반 공간 집합 계획(physics-grounded spatial set planning) 문제로 재구성한 벤치마크인 CityDeploy-Bench를 소개한다. 이 벤치마크는 유틸리티(utility) 표현과 계획 다이내믹스를 분리함으로써, 다양한 플래너(planner)에 대해 직접적인 스칼라 보상, 관계형 모델, 그리고 고차 상호작용 구조 간의 통제된 비교를 가능하게 한다. 실험 결과, 물리적 결합(coupling)이 커질수록 계획 행동에서 명확한 전환이 나타난다. 배치 품질은 학습된 유틸리티가 송신기 간의 집합적 상호작용을 포착하는지에 점점 더 의존하게 되며, 반면 더 강력한 탐색만으로는 누락된 관계형 구조를 보완할 수 없다. 이는 다중 송신기 배치가 독립적인 공간적 의사결정들의 집합이 아니라, 물리적으로 상호작용하는 집합에 대한 조정(coordination) 문제임을 보여준다. 우리는 의사결정 학습(decision learning)과 물리 기반 무선 네트워크 설계를 연결하는 연구를 위한 재현 가능한 테스트베드로서 CityDeploy-Data와 벤치마크 프레임워크를 공개한다.
민첩 관측 위성을 활용한 해상 이동 표적 관측 스케줄링을 위한 암묵적 Q-러닝 기반 개미 군집 최적화
Implicit Q-learning-bootstrapped ant colony optimization for maritime moving-target observation scheduling with agile satellites
민첩 지구 관측 위성을 활용한 해상 이동 표적 관측 스케줄링은 동적이고 순서 의존적인 조합 최적화(combinatorial optimization) 문제입니다. 해수면 표적은 지속적으로 이동하므로, 표적의 움직임과 위성 궤도 기하 구조에 따라 관측 가능 윈도우가 가변적으로 변합니다. 따라서 스케줄러는 시간 윈도우, 자세 기동 및 탑재 자원 제약 조건 하에서 작업 선택, 위성 할당, 관측 윈도우 선택, 관측 순서를 공동으로 결정해야 합니다. 본 논문에서는 다중 위성 해상 이동 표적 관측 스케줄링을 위해 암묵적 Q-러닝(implicit Q-learning)을 부트스트랩한 개미 군집 최적화(ant colony optimization) 방법인 IQACO를 제안합니다. IQACO는 작업 선택 정책을 직접 학습하는 대신, 오프라인 암묵적 Q-러닝 모듈을 구성적 개미 군집 최적화에 임베딩하여 페로몬 요인, 휴리스틱 요인 및 증발률을 적응적으로 조절합니다. 압축된 탐색 상태 표현은 페로몬 분포, 현재 및 역대 최고 해의 품질, 반복(iteration) 진행 상황을 포착합니다. 온라인 스케줄링 중에는 개미 군집 최적화가 실행 가능한 관측 시퀀스를 구성하는 동시에, 학습된 정책이 현재 탐색 상태에 맞춰 탐색 동작을 조정합니다. 다양한 규모와 위성 구성을 가진 14개 시나리오에서의 실험 결과, IQACO는 비교 알고리즘들보다 지속적으로 우수한 성능을 보였으며 기존 개미 군집 최적화 대비 평균 목적 함수 값을 2.86%~9.41% 향상시켰습니다. 추가 비교 및 보완 실험은 다양한 스케줄링 조건과 문제 설정 전반에서 본 방법의 효과성과 강건성을 입증합니다. 이러한 결과는 오프라인 가치 학습이 제약이 있는 해상 이동 표적 관측 스케줄링을 위한 효과적인 적응형 탐색 제어 메커니즘을 제공함을 보여줍니다.
드래곤체스를 위한 시간차 학습
Temporal-Difference Learning for Dragonchess
본 연구는 두 가지 적응형 AI 방법론인 진화적 전이학습(evolutionary transfer learning)과 TD(lambda)가 3차원 체스 환경인 드래곤체스(Dragonchess)에서 어떻게 작동하는지 조사합니다. 이 게임은 고유한 보드 구조와 계산 부하로 인해 플레이어에게 도전 과제를 제시하므로, 적응형 방법론이 새로운 환경에서 평가 휴리스틱을 어떻게 업데이트할 수 있는지 연구하기에 이상적인 환경을 제공합니다. 본 연구에서는 드래곤체스 엔진을 PyGame 엔진에서 C++로 다시 구현했습니다. 이를 통해 더 빠른 게임 플레이가 가능해져, 단일 소규모 토너먼트 대신 신뢰구간과 유의성 검정을 포함한 10,000회의 게임을 진행할 수 있었습니다. 라운드 로빈 토너먼트에서 두 적응형 방법론 모두 다른 모든 에이전트보다 뛰어난 성능을 보였습니다. 실험 결과, 진화된 평가 방식과 학습된 평가 방식 간에 통계적으로 유의미한 성능 차이는 없는 것으로 나타났습니다. 본 연구는 구조적으로 복잡하고 새로운 게임 도메인에서 적응형 방법론의 효용성을 입증합니다.
잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝
Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling
잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.
학습과 탐색을 통한 조합 최적화에서 인간형 해법 이해
Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search
인간은 고급 컴퓨터 알고리즘에게도 계산적으로 어려운 조합 최적화 문제에 대해 종종 좋은 해를 찾는다. 유클리드 여행 판매원 문제(TSP)에서 사람들은 시간과 계산에 심각한 제약이 있음에도 불구하고 거의 최적인 경로(tour)를 빠르게 생성한다. 경로를 인간형으로 만드는 요인은 무엇이며, 이러한 해를 어떻게 학습할 수 있을까? 본 연구에서는 유클리드 TSP에서 인간의 수행을 대규모 행동 및 계산 조사를 통해 이러한 질문에 답한다. 우리는 TSP 인스턴스의 넓은 공간을 샘플링하고, 인간의 해를 수집했으며, 유효한 경로에 대한 확률 분포를 정의하는 어텐션 기반 포인팅 메커니즘을 갖춘 순환 신경망인 Pointer Networks에 기반한 신경 정책과 이를 비교했다. 우리는 강화학습(RL), 최적 경로로부터의 지도학습, 인간 경로로부터의 지도학습, 그리고 최적 경로 지도학습 사전학습 후 RL 미세조정을 포함한 여러 목적 함수로 이러한 네트워크를 학습시켰다. 인간의 경로는 최적 경로와 동일하지는 않았지만, 거의 최적인 기하학적 분지(basin)를 차지했다: 최적 해와 많은 구조적 특성을 공유하면서도 체계적인 인간 특유의 편차를 유지했다. 인간 경로에 대한 최상의 설명은 최적 경로의 직접적 모방이 아니라, 최적 경로로 사전학습하고 RL로 미세조정한 뒤 $\text{Best-of-}N$ 샘플링을 통해 디코딩한 모델이었다. 이러한 결과는 인간형 해가 구조화된 지도학습, RL, 테스트 시점 탐색의 결합으로부터 창발할 수 있음을 시사하며, 많은 현대 인공지능 시스템의 기반이 되는 계산 원리와 공명한다.
Margin Trader: A Reinforcement Learning Framework for Portfolio Management with Margin and Constraints
토론
이 논문과 연결된 포럼 글이 아직 없습니다.