Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning

기술 요약: 뉴런 없는 스마트 교통 – 테이블형 강화 학습을 이용한 공정한 메트로 네트워크 확장

문제 정의
본 논문은 교통 네트워크 설계 문제(TNDP)의 특정 하위 집합인 메트로 네트워크 확장 문제(MNEP)를 다룹니다. 목표는 건설 예산($B$)과 최대 역 개수($T$)라는 제약 조건 하에, 기존 도시 네트워크 내에 새로운 메트로 노선을 설계하여 포착된 통행 수요를 극대화하는 것입니다. 전통적으로 MNEP는 도시를 격자로 표현하며, 목적(Origin-Destination, OD) 수요의 합을 극대화하는 인접 셀의 시퀀스(노선)를 찾는 조합 최적화 문제로 모델링됩니다.

기존 문헌에서 발견된 결정적인 공백은 이러한 문제에 딥 강화 학습(Deep RL)에 과도하게 의존한다는 점입니다. 딥 RL은 복잡한 순차적 의사결정에서 성공을 거두었으나, 계산 비용이 많이 들고 환경적으로 비용이 높으며, 해석이 어려운 "블랙박스"로 작동하는 경우가 많습니다. 저자들은 MNEP가 근본적으로 제한된 입력 특징과 고유한 확장성 제약(예: 고정된 역 간격)을 가진 정적 최적화 문제이며, 따라서 복잡한 신경망이 불필요할 수 있다고 주장합니다. 또한, 기존 방식들은 사회적 형평성(다양한 사회경제적 집단 간의 교통 혜택의 공정한 분배)을 충분히 다루지 못한 채 효율성(공리주의)만을 우선시하는 경향이 있습니다.

방법론
저자들은 문제의 재정의와 사회적 형평성 기준을 명시적으로 포함한 테이블형 강화 학습(Tabular Reinforcement Learning) 접근 방식을 결합한 새로운 프레임워크를 제안합니다.

1. 문제 재정의 (NMRDP):
   MNEP를 비마르코프 보상 결정 과정(Non-Markovian Reward Decision Process, NMRDP)으로 재정의합니다. 모든 격자 셀을 잠재적 행동으로 취급하여 행동 공간이 격자 크기에 따라 선형적으로 확장($O(n \times m)$)되는 기존 딥 RL 방식과 달리, 제안된 방법은 프로세스를 두 단계로 분리합니다:

• 초기 상태 선택: 에이전트는 메트로 노선의 시작 셀을 선택합니다.
• 순차적 탐색: 에이전트는 8가지 이산 방향(N, S, E, W 및 4개 대각선) 중 하나를 선택하여 격자를 이동합니다.
  이를 통해 초기 선택 이후의 모든 단계에서 행동 공간을 상수 크기인 8로 줄여, 시간 복잡도를 $O(1)$로 감소시켰습니다. 상태는 에이전트의 현재 위치로 단순화되었습니다. 보상이 방문한 역의 이력(직접 및 환승 수요 계산을 위해)에 의존하기 때문에, 이 과정은 엄격한 마르코프 성질을 위반하며, 따라서 NMRDP 형식을 취합니다.

2. 알고리즘 (몬테카를로 테이블형 RL):
   저자들은 몬테카를로 기반의 테이블형 RL 알고리즘을 사용합니다. 에이전트는 두 개의 테이블을 유지합니다:

• $V_{start}(S_0)$: 특정 셀을 시작점으로 선택했을 때의 기대 수익(expected return)을 추정합니다.
• $Q(S, A)$: 현재 상태에서 특정 방향 행동을 취했을 때의 가치를 추정합니다.
  에이전트는 탐사(exploration)와 이용(exploitation)을 위해 $\epsilon$-greedy 전략을 사용합니다. 업데이트는 각 에피소드가 끝날 때 총 수익 $J$의 몬테카를로 추정을 통해 수행되며, 추정된 수익과 실제 수익의 차이에 따라 $V$ 및 $Q$ 값을 조정합니다.

3. 사회적 형평성 통합:
   보상 함수는 단순한 수요 극대화를 넘어 사회적 형평성을 포함하도록 확장되었습니다. 저자들은 사회경제적 지표(개발의 대리 지표로서 주택 가격 지수)를 기준으로 그룹($G$)을 정의하고, 세 가지 보상 공식을 테스트했습니다:

• 공리주의 (최대 효율성): 총 충족 수요를 극대화합니다.
• 균등 배분 (수평적 형평성): 일반화된 지니 계수(Generalized Gini Index, GGI)를 사용하여 그룹 간 혜택의 격차를 최소화합니다.
• 롤스적 정의 (수직적 형평성): 가장 취약한 그룹(최저 주택 가격 분위)의 혜택을 극대화합니다.

주요 기여

• 문제 재정의: MNEP를 행동 공간이 분리된 NMRDP로 재정의함으로써, 솔루션 공간을 제한하지 않으면서도 단순한 테이블형 방법을 사용할 수 있게 하여 탐색 공간 복잡도를 획기적으로 줄일 수 있음을 입증했습니다.
• 알리즘 효율성: 딥 RL보다 훨씬 적은 훈련 에피소드로 경쟁력 있는 성능을 달는 몬테카를로 테이블형 RL 알고리즘을 제안했습니다.
• 형평성 인식 프레임워크: 다양한 사회적 선(공리주의, 평등주의, 롤스적 정의)을 RL 프레임워크에 통합하여, 교통 계획에서 효율성과 공정성 사이의 균형을 맞출 수 있는 유연한 메커즘을 제공합니다.
• 해석 가능성: 테이블형 방법은 내재적인 해석 가능성을 제공하여, 딥 RL의 잠재 표현(latent representation)과 달리 의사 결정자가 최적 정책, 보상 분포 및 Q-값을 직접 시각화할 수 있게 합니다.

실험 결과
본 방법은 중국 시안(Xi'an)과 네덜란드 암스테르담(Amsterdam)이라는 두 가지 실제 환경에서 평가되었습니다.

• 성능: TabularMNEP는 모든 보상 함수(Efficiency, GGI(2), GGI(4), Rawls)에 대해 최첨단 딥 RL 방법과 대등한 성능을 달성했습니다. 일부 사례에서는 딥 RL보다 약간 낮은 성능을 보였으나 신뢰 구간 내에 머물렀으며, 유전 알고리즘(Genetic Algorithms) 및 그리디 탐색(Greedy Search) 베이스라인보다는 유의미하게 우수한 성능을 보였습니다.
• 효율성: 테이블형 접근 방식은 딥 RL 베이스라인이 필요로 하는 448,000 에피소드에 비해 현저히 적은 25,000 에피소드만으로 학습을 완료했습니다.
• 환경적 영향: 단축된 훈련 시간과 GPU 의존성 부재 덕분에(비교의 공정성을 위해 GPU 노드에서 테스트됨), 테이블형 방법은 추정 탄소 배출량을 평균 12배 감소시켰습니다.
• 형평성 결과: 실험을 통해 서로 다른 보상 함수가 네트워크 설계를 성공적으로 변화시킨다는 것을 확인했습니다. 최대 효율성 모델은 고수요 지역(종종 부유한 지역)을 선호한 반면, GGI 및 롤스 보상은 전체적인 효율성을 어느 정도 희생하면서도 저소득층에게 혜택을 재분배하는 데 성공했습니다.

의의 및 주장
본 논문은 MNEP와 같은 조합 최적화 문제에 복잡한 블랙박스 형태의 딥 러닝 모델이 항상 필요한 것은 아니라고 주장합니다. 문제를 재정의하여 행동 공간을 줄임으로써, 더 단순하고 자원 효율적이며 해석 가능한 테이블형 방법이 최첨단 결과를 낼 수 있습니다. 저자들은 이 접근 방식이 "재현 가능하고, 모듈화되었으며, 해석 가능하고, 자원 효율적인 솔루션"을 제공한다고 강조합니다.

이 연구는 자동화된 교통 계획에서 사회적 형평성을 고려하는 것의 중요성을 강조하며, RL이 효율성을 크게 훼 sacrifice 하지 않으면서도 공정성을 위해 튜닝될 수 있음을 보여줍니다. 그러나 저자들은 테이블형 방법이 제약된 상태 공간 덕분에 MNEP에서 잘 작동하지만, 본질적으로 거대한 상태 표현을 가진 문제로 일반화될 수 있는지에 대해서는 한계를 인정하며 신중한 입장을 유지합니다. 또한, 세심한 보상 설계와 인간의 감독이 없다면, 자동화된 도시 계획 의사결정이 기존의 편향을 강화할 위험이 있다고 경고합니다.