본문 :
다중 에이전트 강화 학습(MARL)은 주어진 환경 내에서 상호 작용하는 다수개의 에이전트를 기반으로 하는 특정 시스템입니다.
각 에이전트는 각 시간 단계에서 결정( action )을 내리고 다른 에이전트와 협력하여 주어진 목표를 달성합니다.
기본적으로 에이전트는 환경과의 상호 작용을 통해 장기적인 보상을 극대화하기 위해 주어진 정책을 학습하려는 학습 가능한 요소로 정의 될 수 있습니다.
환경의 복잡성과 문제의 조합적 특성으로 인해 에이전트 훈련은 어려운 문제로 분류되는데 대부분의 MARL 문제는 NP-Hard 문제로 분류됩니다.
참조 :
https://arxiv.org/abs/1301.3836
MARL 문제에 대해 에이전트를 훈련시키는 일반적인 접근 방식은 중앙 집중형으로 하나의 서버가 모든 에이전트를 훈련하는 것일 수 있습니다.
이는 실제로 각 시간 단계에서 실행할 모든 에이전트의 공동 작업을 얻기 위해 단일 에이전트 RL 문제로 전환됩니다. 그러나 이 접근 방식에서는 작업 수가 기하급수적으로 증가하는 경우에 문제를 다루기 어려워 집니다.
게다가 각 에이전트는 자신의 로컬 정보를 중앙 컨트롤러로 보내야 하며 에이전트 수가 증가함에 따라 이 접근 방식은 비용이 많이 들거나 latency가 증가하게 됩니다.
통신 비용 외에도 이 접근 방식은 중앙 서버의 부하와 네트워크 연결성에 좌우되는 문제에 취약합니다.
또한 일반적으로 MARL 문제에서 각 에이전트는 일부 로컬 정보에만 액세스하며 개인 정보 보호 문제로 인해 다른 에이전트 및 서버와 정보를 공유하지 못할 수 있습니다.
이에 기존 접근 방식은 (i) 중앙 집중식 또는 분산식 제어, (ii) 완전히 또는 부분적으로 관찰 가능한 환경, (iii) 협동 또는 경쟁 환경으로 문제를 모델링 해왔습니다.
i 의 분산식 제어는 중앙 집중식 컨트롤러 내에서 중앙 장치는 각 시간 단계에서 각 에이전트에 대한 모든 결정을 내리는 반면 분산형 시스템에서는 각 에이전트가 스스로 결정을 내려야 한다는 점에 차이가 있다는 특징을 갖습니다.
Single-Agent RL
이전의 다양한 포스트에서도 보았듯이 RL은 에이전트가 환경과 상호 작용하는 순차적인 의사 결정 문제를 가정합니다.
에이전트는 시간 $t$에서 상태 $s_t ∈ S$ ($S$는 상태 공간)를 관찰하고 $a_t \in A(s_t)$는 상태 $s_t$에 대한 유효한 행동 공간)에서 action을 취하고 이를 환경에서 실행하여 보상 $r_t$을 받아 업데이트 하는것으로 이전 포스트에서 알아보았습니다.
그 후 새로운 상태 $s_{t+1} ∈ S$로 전송합니다. 이때 에이전트는 장기 보상을 최대화하는 정책을 결정하는 것을 목적으로 합니다. 상태 $s$에서 시작하여 $V_π(s)$로 표시되는 정책 $π$를 따르는 가치 함수는 아래와 같이 정의 됩니다.
이전 포스트에서 가치 함수는 내가 지금 있는 상태가 갖는 가치를 말한다고 했습니다. 즉 $s$의 잠재적인 가치는 $\gamma$에 의해 할인된 잠재적인 이득의 총합입니다.
이와 같은 문제는 Markov Decision Process로 알려져 있으며 이전 포스트에서 충분히 알아 보았습니다.
이에 벨만 방정식은 주어진 확률분포를 따르는 state transition 및 reward 행렬에 대해 모든 시간 상태에서 다음과 같이 정의 되었습니다.
여기서 평균을 취하는 대신에 action의 잠재 가치중 가장 높은 값을 취해 최적의 state-value 와 oprimal polivy는 다음과 같이 구했습니다.
Q-learning에서의 최적 Q 값 또한 state-action에 대한 벨만 방정식으로 표현되었습니다.
이를 통해 최적의 정책을 얻을 수 있습니다.
Value Approximation
위의 가치 함수는 평균의 형태를 띄고 있습니다. 다시 말해 관찰 횟수가 충분하면 선형 근사가 local opmimal에 수렴하는것으로 나타납니다.
그럼에도 불구하고 선형 근사기는 복잡한 환경의 모든 복잡성을 포착할 만큼 충분한 표현을 하기 어렵습니다.
이를 해결하기 위해 가치 기반의 신경망에 의한 비선형 근사가 연구되었습니다.
참조 :
https://arxiv.org/abs/1312.5602
특히나 DQN은 replay memory buffer와 Target network를 활용하여 훈련을 안정화합니다.
replay memory는 $d_t$가 에피소드가 현재의 관찰로 끝났는지 여부를 결정하는 이전 관찰 튜플$(s_t, a_t, r_t, s_{t+1}, d_t)$을 저장합니다.
그런 다음 replay memory에서 임의의 미니 배치를 가져와 신경망을 훈련합니다. DQN 알고리즘은 상태 $s_t$에 대한 CNN(Convolutional Neural Network)을 입력으로 다음 CNN의 출력을 $|A|$를 포함하는 완전 연결된 신경망에 전달해 각 가능한 action에 대한 Q 값을 근사화합니다. 가중치 $θ$(weight)가 있는 이 신경망 은 손실 함수를 최소화하기 위해 replay memory에서 크기 $m$의 미니 배치를 뽑는것으로 sample간에 correlation을 방지 합니다.
이러한 신경망 기반의 모든 알고리즘에서 일반적으로 탐색을 보장하기 위해 $\epsilon$-Greedy 알고리즘이 사용됩니다. 즉, 확률이 $\epsilon$인 각 시간 단계에서 행동이 무작위로 선택되고 그렇지 않으면 상태에 대한 Q-값에 대한 argmax를 얻음으로써 탐욕법에 따른 탐색을 수행하게 합니다.
Uploaded by N2T