A Distributed Primal-Dual Method for Constrained Multi-agent Reinforcement Learning with General Parameterization

기술 요약: 일반 파라미터화를 가진 제약 다중 에이전트 강화학습을 위한 분산 원 - 쌍대 방법

문제 공식화
본 논문은 네트워크 환경 내의 협력적 제약 다중 에이전트 강화학습 (CMARL) 의 과제를 다룹니다. 이 문제는 공유 환경에서 작동하는 $N$개의 에이전트가 관여하는 제약 마르코프 게임 (CMG) 으로 공식화됩니다. 에이전트들은 $K$개의 전역 제약 조건을 준수하면서, 지역적 기대 비용의 평균으로 정의된 전역 목적 함수를 최소화하기 위해 협력합니다. 이러한 제약 조건들도 또한 모든 에이전트에 걸친 지역적 제약 비용의 평균으로 공식화됩니다.

이 연구의 중요한 차별점은 완전히 분산된 온라인 학습의 요구사항에 있습니다. 중앙 집중식 훈련이나 실행 중 조정이 필요한 방법과 달리, 제안된 접근법은 에이전트들이 이웃과의 지역 정보 및 지역 통신만을 사용하여 독립적으로 행동한다고 가정합니다. 이 문제는 단일 에이전트 제약 RL 과는 달리, 협력적 CMARL 이 일반 함수 근사 (파라미터화된 정책) 를 사용할 때 특히 영이 아닌 쌍대 간격 (non-zero duality gap) 을 자주 나타낸다는 사실로 인해 복잡해집니다. 이 간격은 전역 목적 함수를 최적화하면서 전역 제약 조건을 충족하는 데 본질적인 복잡성을 도입합니다.

방법론
저자들은 액터 - 크리틱 프레임워크에 기반한 분산 원 - 쌍대 알고리즘을 제안합니다. 핵심 혁신은 에이전트들이 전역 제약 조건과 관련된 라그랑주 승수를 처리하는 방식에 있습니다.

1. 승수의 지역적 추정: 중앙 조정자가 전역 라그랑주 승수를 계산하는 데 의존하는 대신, 각 에이전트 $n$은 전역 승수 벡터 $\lambda$의 지역적 추정치 $\hat{\lambda}_n$을 유지합니다.
2. 분해된 목적 함수: 전역 라그랑지안은 이러한 지역적 추정치를 사용하여 재구성됩니다. 에이전트들은 자신의 정책 매개변수 $\theta_n$과 지역 승수 추정치 $\hat{\lambda}_n$에 의존하는 지역 라그랑지안 목적 함수를 최적화합니다.
3. 세 가지 시간 척도 업데이트: 알고리즘은 수렴을 보장하기 위해 세 가지 명확한 시간 척도에서 작동합니다.
   • 가장 빠른 시간 척도 (크리틱): 에이전트들은 지역 라그랑지안 비용을 추정하기 위해 시간 차 (TD) 학습을 사용하여 지역 가치 함수 근사기 (크리틱) 를 업데이트합니다.
   • 중간 시간 척도 (액터): 에이전트들은 추정된 어드밴티지 함수를 활용하여 다중 에이전트 설정에 맞게 적응된 정책 그라디언트 정리를 사용하여 정책 매개변수 (액터) 를 업데이트합니다.
   • 가장 느린 시간 척도 (쌍대/승수): 에이전트들은 지역 라그랑주 승수 추정치를 업데이트합니다. 이 업데이트는 두 단계로 이루어집니다. 하나는 에이전트들이 이웃과 추정치를 평균화하는 합의 단계 (이중 확률 통신 행렬 사용) 이며, 다른 하나는 지역 제약 위반에 기반한 상승 단계입니다.
4. 합의 메커니즘: 이 알고리즘은 네트워크 전반에 걸쳐 지역 승수 추정치 $\hat{\lambda}_n$ 간의 합의를 강제합니다. 이론적 분석은 이러한 지역 추정치가 중앙 집중식 조정 없이 전역 승수를 효과적으로 재구성하는 공통 값으로 수렴함을 증명합니다.

주요 기여
본 논문은 네 가지 주요 기여를 합니다:

1. 분산 공식화: 협력적 CMARL 에서 라그랑주 승수를 위한 새로운 분산 공식화를 도입하며, 각 에이전트는 지역 정보와 이웃 통신만을 사용하여 자신의 지역 추정치를 유지하고 업데이트합니다.
2. 알고리즘 개발: 일반 함수 근사 (선형 크리틱 및 파라미터화된 정책) 를 가진 액터 - 크리틱 방법을 활용하는 분산 온라인 원 - 쌍대 알고리즘을 개발합니다.
3. 수렴 보장: 저자들은 지역 라그랑주 승수가 거의 확실하게 합의를 달성하고 전체 알고리즘이 투영된 동적 시스템의 균형점으로 수렴함을 보여주는 이론적 증명을 제공합니다.
4. 비최적성 및 실현 가능성 분석: 논문은 균형점에서 제약 조건의 실현 가능성을 분석하고 솔루션의 비최적성을 정량화합니다. 정책 파라미터화 및 합의 과정에서 발생하는 오차를 고려하여 파라미터화된 문제에 대한 쌍대 간격의 상한을 유도합니다.

실험 결과
접근법을 검증하기 위해 저자들은 확률적 역학을 가진 제약 협력 쿠르노 게임에서 알고리즘을 평가했습니다. 이 시나리오에서 에이전트들은 시장 내 생산자로 행동하여 가격 기반 제약을 준수하면서 이익을 극대화 (비용 최소화) 하기 위해 생산 수준을 선택합니다.

• 합의: 시뮬레이션 결과 (그림 1) 는 서로 다른 에이전트의 지역적으로 추정된 라그랑주 승수가 합의 값으로 수렴함을 보여줍니다.
• 성능: 훈련 곡선 (그림 2) 은 알고리즘이 전역 제약 위반을 거의 0 으로 유지하면서 전역 목적 비용을 성공적으로 최소화함을 보여줍니다.

의의 및 주장
본 논문은 완전히 분산된 방식으로 결합된 지역 비용과 전역 제약을 가진 일반적인 CMARL 문제를 처리하는 방법이 거의 없다는 문헌의 격차를 해소한다고 주장합니다. 기존 연구들은 종종 중앙 집중식 훈련, 동질 에이전트 간의 매개변수 공유, 또는 실행 시간 통신에 의존하는 반면, 이 방법은 완전히 분산된 온라인 학습을 가능하게 합니다.

저자들은 자신의 기여를 기존 비제약 분산 액터 - 크리틱 방법 (특히 비제약 MARL 에 대한 이전 연구를 참조) 의 제약 확장으로 겸손하게 규정합니다. 그들은 파라미터화된 협력 설정에서 영이 아닌 쌍대 간격으로 인해 알고리즘이 비파라미터화된 문제의 정확한 해에 비해 비최적일 수 있는 균형점으로 수렴함을 인정합니다. 그러나 제안된 방법은 중앙 집중식 접근법의 확장성 병목 현상 없이 스마트 그리드 및 자율 시스템과 같은 복잡하고 현실적인 시나리오에서 제약 준수를 보장하는 확장 가능한 분산 솔루션을 제공합니다.