지금까지 포스팅 되어 온 Q-learning, Policy gradient, actor-critic, DQN, DDQN 과 같은 알고리즘은 특정 환경에서 하나의 에이전트를 훈련하고 동작하는데 의미가 있었습니다.
하지만 환경이 커지고 변수가 많아지면 (action) 하나의 “똑똑한” 에이전트가 모든 문제를 해결하는것으로 올바른 환경의 변화를 이끌 수 있는 것만은 아닙니다.
그림과 같이 다수의 에이전트가 네트워크 에 의해 동작하는 경우를 가정해 봅니다. Multi-Agent 환경에서 각 에이전트의 Action은 환경의 변화만이 아니라 다른 에이전트의 행동을 위한 정책에도 유의미한 영향을 끼치게 됩니다. 다시 말해 각 에이전트의 상호 작용이 non-stationary합니다.
환경은 각 에이전트 $a_1, …, a_i$ 에 대해서 State 및 action에 대한 보상을 도출합니다. 이때 각 에이전트는 이 State 와 reward를 통해 각 에이전트가 갖는 독립된 정책을 통해 행동을 도출합니다. 하지만 환경에 의해 action이 결정되는것으로 간주할때 환경의 변화가 독립 에이전트 $a_x$ 뿐이 아니므로 다음과 같은 상황을 생각할 수 있습니다.
에이전트 $a_x$가 특정 시간 도메인 t에서 행동한 action에 의해 환경에 $\alpha_t$ 만큼 변화했습니다. 하지만 이와 동시에 다른 에이전트 $a_y$의 action에 의해 환경이 $\beta_t$만큼 변화 합니다. 그러면 에이전트 $a_x$입장에서는 행동에 대한 환경의 변화가 기대값 $\alpha_t$에서 $\beta_t$ 만큼 변화한 $\alpha_t+\beta_t$ 라고 생각할 수 있습니다.
여기서 $\beta_t$는 에이전트 $a_x$의 정책에 의한 행동 확률 분포와 동일시 되는 Transition이 아니므로 행동정책의 stationary를 잃습니다. 이때 다수의 접근법에서는 이를 노이즈로 취급할 수 있습니다. 하지만 agent의 수가 선형적으로 증가 하는경우 그 stationary는 더이상 유지되지 않습니다.
Neighborhood Q-learning
이와 같은 환경을 생각해 볼 수 이있니다.다수의 에이전트가 하나의 공간 env에서 상호작용하며 동작하는 과정입니다.
이때 중요한 점은 나의 행동에 영향을 미치는 대부분의 요인은 내 주위의 다른 에이전트의 행동이라는 점 입니다. 그러면 나와 abs dist가 먼 에이전트의 행동정책에 대한 환경의 반영은 노이즈로 처리할 수 있게 됩니다.
마치 POMDP에서 환경전체를 관찰하지 못하고 partial observation만으로 action을 특정 belief에 의존해 처리하는것과 같은 개념입니다.
이렇게 주위의 (neighbor) 즉 이웃의 크기를 제한하는것으로 에이전트는 이웃에 대해 설정한 고정 observation으로 shared action space의 기하급수적인 growth를 restrict 할 수 있습니다.
예를 들어 각 에이전트에 대해 10개의 action을 수행하는 서로 다른 100개의 에이전트가 있는 다중 에이전트 ENV가 있는 경우 전체 action space의 조합은 $10^100$으로 증가합니다. 이는 다루기 힘든 크기입니다. 이를 훈련하기 위한 state action table을 생성할 수 없음은 물론 비선형함수를 근사 하는것도 어렵습니다.
그러나 ENV의 partial space를 observation하고 각 부분 공간(이웃)의 크기를 $N$으로 제한하면 단일 에이전트보다는 훨씬 큰 $10^N$이지만 이는 계산가능한 성질을 유지하고 있습니다.
이 때 에이전트 $a_x$에 대한 Q 값을 계산하면 에이전트 $a_x$와 가장 가까운 거리에 있는 $N$개의 에이전트를 찾고 이 $N$개의 에이전트에 대해 길이가 action의 조합의 크기에 비례하는 벡터를 생성할 수 있습니다.
그러면 보다 낮은 비용으로 다수의 agent에 대한 훈련을 stationary를 최소화 한체 진행 할 수 있습니다.
Mean Field Multi-Agent Reinforcement Learning
공동 행동을 위한 차원은 에이전트 수 $N$에 비례적으로 커진다는것을 알았습니다.
모든 에이전트가 공동 행동을 결과를 기반으로 동시에 정책에 의한 가치를 평가하는 과정에서 non-stationary가 있을 수 있다는 것 또한 알았습니다.
이에 이 접근에서는 pairwise local interaction만을 통해 Q함수를 factorize 합니다.
여기서 $N(j)$는 이웃 에이전트의 집합입니다.
이러한 이웃 에이전트의 근사는 상호작용의 복잡성을 줄이면서 에이전트 쌍간의 global 한 상호작용은 보존하게 됩니다.
이에 에이전트 $j$의 이웃 $N(j)$ 기준으로 평균화된 행동을 계산하고 이때 다른 이웃의 행동을 작은 노이즈로 취급하는 (flucuation)방식을 취하면 다음과 같습니다.
그러면 데일러 전개에 의해 Q함수의 확장은 다음과 같아집니다.
그러면 이웃내의 모든 에이전트의 행동은 하나의 평균화된 목적을 가진 행동으로 근사화 되고 모든 에이전트에 대해 같은 영향을 미치는 동질성을 갖게 됩니다. 그리고 그 외의 에이전트는 노이즈 취급되게 됩니다.
그러면 다수의 서로 다른 에이전트의 상호작용은 두개의 에이전트간 상호작용의 집합의 집합으로 효과적으로 변환 될 수 있습니다.
그러면 Q-function의 업데이트 또한 다음과 같습니다.
이와 같은 방식을 통해 다중에이전트의 복잡성을 상쇄하고 영향을 미치는 에이전트간의 pairwise를 통해 근사함으로써 Meanfield를 만들고 다른에이전트의 영향을 상쇄 할 수 있습니다.
Uploaded by N2T