POMO: Policy Optimization with Multiple Optima for Reinforcement Learning

Digest (CISELQ)

• Context: 신경망 기반 조합 최적화(Neural Combinatorial Optimization, NCO)는 TSP, CVRP, KP 등 NP-hard 문제를 end-to-end 학습된 정책으로 해결하려 한다. 기존 Attention Model(AM, Kool et al., 2019)은 greedy rollout baseline 기반 REINFORCE로 학습하지만, 단일 시작점 탐색과 high-variance baseline으로 인해 local optima에 취약하다.
• Issue: 조합 최적화 해(solution)는 동일한 순회 경로를 여러 노드 순서로 표현할 수 있는 **본질적 대칭성(symmetry)**을 갖는다. 기존 RL 학습은 이 대칭성을 무시하여 하나의 특정 표현에만 정책을 집중시키고, 학습 신호의 variance가 크다.
• Solution: **POMO(Policy Optimization with Multiple Optima)**는 모든 노드를 각각 하나의 시작점으로 삼아 N개의 서로 다른 trajectory rollout을 병렬 생성하고, 이들의 평균 보상을 shared baseline으로 사용한다. Inference 시에는 입력 좌표에 8가지 대칭 변환(flip/rotate)을 적용해 앙상블한다.
• Evidence: TSP100에서 optimality gap 0.14% (AM 대비 한 자릿수 이상 향상), CVRP·KP에서도 모든 learned heuristic 대비 SOTA. 추론 시간은 기존 sampling baseline 대비 한 자릿수 이상 단축.
• Limits: 대칭성이 명확한 Euclidean 문제에 최적화. 시작점 N개에 따라 배치 크기가 N배 증가(메모리).
• Questions: 비대칭 문제(비Euclidean, constrained routing)에서도 다중 optima 가정이 유효한가? Attention 이외의 encoder에서도 동일한 이득이 있는가?

Intro 요약

조합 최적화에서 RL 기반 NCO는 Pointer Network(Vinyals, 2015), AM(Kool, 2019)으로 발전해왔다. 기존 방법은 단일 trajectory와 greedy rollout baseline을 사용해 학습하지만, solution symmetry를 활용하지 못해 exploration이 제한된다. POMO는 “N개의 optimal trajectory가 존재한다”는 가정 하에 모든 시작점에서 병렬 rollout을 생성하여 학습 signal을 다양화한다.

Methods 요약

• Multiple trajectory sampling: N개 노드(도시) 각각을 시작점으로 하여 N개의 trajectory ${\tau }^1,\dots ,{\tau }^N$를 policy ${\pi }_{\theta }$로 샘플링.
• Shared baseline: $b_{\text{shared}}=\frac{1}{N}{\sum }_{i}R({\tau }^i)$를 모든 rollout의 advantage 계산에 공통 사용. 이는 문제 인스턴스별 variance를 크게 줄이며 greedy rollout baseline보다 안정적.
• REINFORCE gradient: ${\nabla }_{\theta }J\approx \frac{1}{N}{\sum }_i(R({\tau }^i)-b_{\text{shared}}){\nabla }_{\theta }\log p_{\theta }({\tau }^i)$
• Instance augmentation (inference): 2D 좌표에 8가지 대칭 변환(x,y 반전·회전)을 적용해 8×N개 후보를 생성, 최단 경로를 선택.

Results 요약

문제	크기	지표	POMO	Attention Model	OR-Tools / LKH3
TSP	100	optimality gap	0.14%	2.26%	0.00% (LKH3)
CVRP	100	gap	0.32%	4.97%	0.00% (LKH3)
KP	200	gap	≈0.00%	0.03%	optimal

추론 시간은 AM sampling 대비 한 자릿수 이상 단축.

Discussion 요약

POMO는 “symmetry-aware RL”의 대표 사례로, combinatorial 문제에서 policy gradient의 variance 감소와 exploration 다양성을 동시에 달성한다. 핵심 통찰은 problem-intrinsic symmetry를 baseline 설계에 직접 반영한 것이다.

Insights

• Solution space의 대칭성은 공짜 데이터 증강으로 활용 가능하다.
• Shared baseline은 per-instance variance를 제거하여 greedy rollout보다 안정적 학습 신호를 제공한다.
• Inference-time augmentation은 학습 비용 없이 성능을 추가로 끌어올린다.

Discussion Points

• 비Euclidean/비대칭 문제(e.g., asymmetric TSP, VRPTW)로의 확장성.
• N 시작점 병렬화가 야기하는 메모리 증가를 어떻게 완화할 것인가.
• 시작점 외의 내부 대칭(순환 회전 등)을 추가로 활용할 수 있는가.

메타데이터

항목	내용
저자	Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Seungjai Min, Youngjune Gwon
학회	NeurIPS 2020
코드	https://github.com/yd-kwon/POMO
벤치마크	TSP(20/50/100), CVRP(20/50/100), KP(50/100/200)
기반 모델	Attention Model (Kool et al., 2019) encoder-decoder

왜 이 연구를 하는가?

NP-hard 조합 최적화는 물류·반도체·네트워크 설계의 핵심 문제이지만 기존 heuristic(LKH3, Concorde)은 문제별 수작업 설계와 긴 추론 시간이 필요하다. 신경망 정책은 저차 다항 시간 추론으로 대규모 인스턴스를 즉시 풀 수 있지만, 학습 안정성과 품질이 classical solver에 미치지 못한다. POMO는 이 격차를 학습 알고리즘 수준의 대칭성 활용으로 좁히는 것을 목표로 한다.

방법 (Method)

flowchart LR
    A[입력 인스턴스 N개 노드] --> B[Encoder Attention Model]
    B --> C{N개 시작점 선택}
    C -->|각 노드 s_i 시작| D[Decoder rollout tau_i]
    D --> E[보상 R tau_i]
    E --> F[shared baseline 평균 R]
    F --> G[Advantage R tau_i - baseline]
    G --> H[REINFORCE gradient]
    H --> B
    D --> I[Inference 8x augmentation]
    I --> J[최단 경로 선택]

• Training step: batch 내 각 인스턴스에 대해 N trajectory를 샘플 → shared baseline으로 advantage 계산 → policy gradient 업데이트.
• Inference: 단일 인스턴스에 대해 8가지 좌표 변환 + N 시작점 = 8N rollout → 최고 보상 선택.

발견

발견	의미
Shared baseline이 greedy rollout baseline 대비 수렴 빠름	variance 감소가 convergence에 핵심
N 시작점 rollout이 학습 품질을 크게 향상	multiple optima 가정이 경험적으로 유효
Instance augmentation이 추가 0.1–0.5% gap 개선	symmetry를 학습·추론 모두에서 활용 가능
TSP100에서 LKH3 대비 0.14% gap	신경망 heuristic이 classical solver에 근접

이론적 의의

POMO는 policy gradient의 baseline 설계에 problem structure를 주입하는 프레임워크로 해석될 수 있다. 이는 일반적인 control variate 기법에서 더 나아가, solution space의 등가류(equivalence class)를 명시적으로 이용해 variance를 줄이는 접근이다. RL4CO 문헌의 표준 기법으로 자리잡았고, 후속 연구(Sym-NCO, MDAM, Poppy 등)의 기반이 되었다.

재현성 및 신뢰도 평가

항목	평가	근거
코드 공개	A	공식 GitHub 저장소 제공
데이터/벤치마크	A	표준 TSP/CVRP/KP 분포
하드웨어 명시	A	Single GPU 학습 시간 보고
결과 재현성	A	다수 독립 연구에서 재현 확인
비교 baseline 적절성	A	AM, OR-Tools, LKH3, Concorde 포함

관련 연구

• Vinyals et al., 2015, Pointer Networks — NCO의 시초.
• Kool et al., 2019, Attention, Learn to Solve Routing Problems (AM) — POMO의 encoder-decoder 기반.
• Nazari et al., 2018, RL for VRP — policy gradient NCO 선행.
• Kim et al., 2022, Sym-NCO — POMO의 symmetry 관점을 일반화.
• Grinsztajn et al., 2023, Poppy — 다중 정책으로 POMO 확장.

원자적 인사이트

1. 대칭성은 baseline을 위한 공짜 통계량이다: 동일 해를 표현하는 N개의 rollout을 평균내면 per-instance expected reward에 대한 unbiased·low-variance 추정치가 된다. 이는 critic 네트워크 없이도 actor-critic에 근접한 안정성을 제공한다.
2. 학습 시 탐색 다양성과 추론 시 앙상블은 동일 원리(symmetry)의 두 얼굴이다: POMO는 training의 multiple starting nodes와 inference의 instance augmentation을 하나의 대칭성 가설로 통합하여, 추가 파라미터 없이 양쪽 모두에서 이득을 얻는다.
3. Problem structure를 algorithm에 주입하는 것이 scale보다 먼저다: AM과 동일한 네트워크를 POMO 방식으로 학습하기만 해도 gap이 2.26%→0.14%로 줄어드는데, 이는 RL4CO에서 모델 규모보다 학습 신호 설계가 더 큰 지렛대가 될 수 있음을 시사한다.

핵심 용어 정리

• POMO: 다중 시작점 rollout + shared baseline을 사용하는 REINFORCE 변형.
• Shared baseline: 동일 인스턴스 내 N rollout 보상의 평균으로 정의되는 control variate.
• Instance augmentation: 2D 좌표 대칭 변환(8가지)으로 추론 시 여러 후보 solution을 생성하는 기법.
• Optimality gap: (model_cost - optimal_cost) / optimal_cost.
• Solution symmetry: 동일 최적해를 여러 다른 action sequence로 표현할 수 있는 성질(e.g., TSP 경로의 시작점 회전).
• REINFORCE: Monte-Carlo policy gradient 알고리즘.

태그

RL combinatorial-optimization POMO REINFORCE policy-gradient TSP CVRP NeurIPS2020 neural-combinatorial-optimization symmetry