2021. 5. 27. 09:19ㆍ관심있는 주제/RL
"게임 이론 역학은 다중 에이전트 강화 학습 시스템의 모든 곳에 존재합니다. 그것에 대해 무엇을 알아야 합니까?"
오늘날 대부분의 인공 지능 (AI) 시스템은 작업을 처리하는 단일 에이전트 또는 적대적 모델의 경우 시스템의 전반적인 동작을 개선하기 위해 서로 경쟁하는 두 개의 에이전트를 기반으로 합니다.
그러나 현실 세계의 많은 인지 문제는 많은 사람들이 만든 지식의 결과입니다.
예)
self-driving car scenario 같은 경우, 모든 에이전트의 결정들은 시나리오에서 다른 많은 에이전트의 행위의 결과입니다.
금융시장이나 경제학에서 많은 시나리오들은 개체들의 많은 그룹 사이에서 조정된 행동들의 결과입니다.
인공 지능 (AI) 에이전트에서 이러한 행동을 어떻게 모방할 수 있습니까?
MARL (Multi-Agent Reinforcement Learning)은 환경과 동적으로 상호 작용하여 학습하는 여러 에이전트를 포함하는 모델에 초점을 맞춘 딥 러닝 분야입니다.
단일 에이전트 강화 학습 시나리오에서 환경의 상태는 에이전트의 작업의 결과로만 변경되지만, MARL 시나리오에서는 환경이 모든 에이전트의 작업을 받습니다.
그런 관점에서 우리는 MARL 환경을 튜플 {X1-A1, X2-A2…. Xn-An}으로 생각할 수 있습니다.
여기서 Xm은 주어진 에이전트이고 Am은 주어진 작업입니다.
그러면 환경의 새로운 상태는 다음과 같습니다.
$A_1 x A_2 x …. A_n$에 의해 정의된 결합된 동작 집합의 결과.
즉, MARL 시나리오의 복잡성은 환경의 에이전트 수에 따라 증가합니다.
다른 MARL 시나리오들의 추가된 복잡성은 에이전트의 행위들이 연관되어 있다는 것입니다.
많은 시나리오에서 MARL 모델의 에이전트는 협력적으로, 경쟁적으로 행동하거나 중립적인 행동을 보일 수 있습니다.
이러한 복잡성들을 다루기 위해서, MARL 기술들은 게임이론의 몇 가지 아이디어를 빌려옵니다.
이 이론들은 여러 참가자가 있는 모델 환경에서 매우 유용할 수 있습니다.
특히 대부분의 MARL 시나리오는 다음 게임 모델 중 하나를 사용하여 표현할 수 있습니다.
- Static Games
- 정적 게임은 모든 플레이어가 다른 플레이어가 선택한 전략에 대한 지식 없이 동시에 결정을 내리거나 전략을 선택하는 게임입니다
- 결정이 다른 시점에서 내려질 수 있지만 각 플레이어가 다른 사람의 결정에 대한 정보를 가지고 있지 않기 때문에 게임은 동시에 진행됩니다. 따라서 마치 동시에 결정을 내리는 것과 같습니다.
- Stage Games
- 스테이지 게임은 정적 게임의 특정 단계에서 발생하는 게임입니다. 즉, 게임의 규칙은 특정 단계에 따라 다릅니다.
- 죄수의 딜레마는 스테이지 게임의 전형적인 예입니다
- 죄수의 델레 마는 2명의 참가자가 비제로섬 게임의 일종임.
- Repeated Games
- 플레이어가 유사한 스테이지 게임 (예 : 죄수의 딜레마)을 여러 번 플레이하여 상호 작용하는 것을 반복 게임이라고 합니다.
- 한 번 플레이하는 게임과 달리 반복 게임은 전략이 과거의 움직임에 따라 달라지므로 평판 효과와 보복을 허용합니다.
대부분 MARL 시나로 이들은 static, stage, repeated games로 모델링 됩니다.
평균 필드 게임(mean field game)과 같은 게임 이론의 새로운 분야는 MARL 시나리오에서 매우 가치가 높아지고 있습니다.
평균 필드 게임 이론은 매우 많은 인구에서 상호 작용하는 소규모 에이전트에 의한 전략적 의사 결정 연구입니다.
"평균 장"이라는 용어의 사용은 개별 입자가 시스템에 거의 영향을 미치지 않는 많은 수의 입자 시스템의 거동을 고려하는 물리학의 평균장 이론에서 영감을 얻었다고 합니다.
내쉬 이론을 사용하고 싶은데, 에이전트가 너무 많아서 내쉬 균형을 잘 찾기 어려울 때, 에이전트 주변의 상호작용을 하나의 평균 상호 작용을 고려하여 문제의 복잡도를 줄인 다음 내쉬 평균을 찾는 이론이다.
즉 많은 수의 비협조적이고 합리적인 에이전트를 사용하여 문제를 모델링하는 게임 이론 분야입니다.
MARL Algorithms and Game Theory
최근에, 연구실에서 만들어지는 MARL 알고리즘의 수가 폭발적으로 증가했습니다.
이 모든 연구를 따라가는 것은 정말 어렵지만 여기서는 게임 이론 아이디어를 사용할 수도 있습니다.
MARL 공간을 이해하는 데 가장 좋은 분류법 중 하나는 에이전트의 행동을 완전히 협조적이거나 완전히 경쟁적이거나 혼합된 것으로 분류하는 것입니다.
이 수준에 MARL 시스템의 에이전트가 수행해야 하는 작업 유형을 기반으로 하는 또 다른 흥미로운 분류 기준을 추가할 수 있습니다.
예)
일부 MARL 환경에서 에이전트는 다른 에이전트와 완전히 격리된 상태에서 결정을 내리고 다른 경우에는 협력자 또는 경쟁자와 조정합니다.
MARL Agents의 어려운 점들
MARL 모델은 실제 세계에서 많은 인지 활동의 비실 제적인 표현이라는 점에서 딥러닝 작업에 가시적인 이점을 제공합니다.
그러나 이러한 유형의 모델을 구현할 때 고려해야 할 많은 과제가 있습니다.
완전한 목록을 제공하지 않고 MARL 모델 구현을 고려할 때 모든 데이터 과학자가 염두에 두어야 할 세 가지 과제가 있습니다.
- The Curse of Dimensionality딥 러닝 시스템의 유명한 과제(차원의 저주)는 특히 MARL 모델과 관련이 있습니다.
특정 게임 환경에서 작동하는 많은 MARL 전략은 에이전트 / 플레이어 수가 증가함에 따라 크게 실패합니다. - Training
많은 에이전트들을 서로 조정해서 학습하는 것은 MARL 시나리오에서 또 다른 악몽입니다.
일반적으로 MARL 모델은 일부 교육 정책 조정 메커니즘을 사용하여 교육 작업의 영향을 최소화합니다. - Ambiguity
MARL 모델은 에이전트 모호성 시나리오에 매우 취약합니다.
두 에이전트가 환경에서 정확히 동일한 위치를 차지하는 멀티 플레이어 게임을 상상해보십시오.
이러한 문제를 처리하기 위해 각 에이전트의 정책은 다른 에이전트가 취한 조치를 고려해야 합니다.
MARL 모델은 향후 10년간 가장 관련성이 높은 딥 러닝 분야가 될 것으로 불린다.
이러한 모델들이 더 복잡한 시나리오를 다루면서, 우리는 게임 이론에서 MARL 시나리오에 이르기까지 더 많은 아이디어가 기초가 되는 것을 보게 될 것 같다
Single-Agent vs. Discrete Multi-Agent vs. Infinite Multi-Agent Reinforcement Learning
현재 유명한 성공 사례에 사용된 알고리즘(Alpha GO) 같은 것들은 다 Single Agent입니다.
이러한 싱글 에이전트 강화 학습(SARL)은 환경의 상태와 행동의 조합을 기본으로 간단하게 리워드 함수를 구성할 수 있습니다.
MARL 같은 경우 환경에서 다른 에이전트의 액션에 의해서 영향받은 하나의 에이전트의 리워드 함수를 구성하는 데 있어서 어려움을 느낍니다.
지금까지 MARL 성공 사례는 Dota 2 , Starcraft 등이 있습니다.
MARL 방법들은 많은 수의 에이전트가 연관된 시나리오들을 적용할 때 어려움이 발생합니다.
그런 점에서, MARL을 뒤흔드는 가장 큰 질문 중 하나는 그것이 무한한 수의 에이전트로 향하는 시나리오에서 효과가 입증될 수 있는가 하는 것입니다.
무한한 에이전트가 있는 MARL 시나리오는 우리 주위에 있습니다.
예)
거래자의 행동이 많은 다른 거래자나 거시경제적 사건들에 의해 영향을 받을 수 있는 주식시장의 역학에도 적용될 것이며, 무역 또는 통화 정책과 같은 분야의 많은 현대 경제 문제는 많은 수의 에이전트가 있는 MARL 환경으로 모델링 될 수 있을 것입니다.
무한 에이전트를 사용하는 MARL 시나리오의 복잡성은 매우 간단한 수학적 설명을 가지고 있다.
다중 에이전트 게임의 설루션은 일반적으로 영화 A Beautiful Mind에서 잘 묘사된 내쉬 평형을 사용하여 모델링 된다고 합니다.
그러나 내쉬-이 평형의 계산 복잡성은 환경의 에이전트 수에 따라 선형적으로 확장되어 무한 에이전트를 사용하는 MARL 시나리오에서는 사용할 수 없다.
에이전트 수의 증가로 인해서 복잡성이 증가하는데, 이 문제를 해결하기 위해서 강화 학습에서 Mean Field Game을 적용하기 시작합니다.
Enter Mean Field Games
평균 필드 게임(MFG)은 다수의 비협조적이고 합리적인 에이전트를 사용하여 문제를 모델링하는 게임 이론 분야입니다.
이 혁명 모델은 수학자들에 의해 깊이 연구되었고 멕시코 파동, 주식 시장, 스마트 그리드 같은 복잡한 다중 에이전트 동적 시스템을 설명하기 위해 적용되었습니다.
그러나 MFG는 대게 이론적인 연습으로만 남아있습니다.
이론적으로, MFG 자체는 대규모 모집단 시스템의 동작을 설명할 수 있지만, 모델은 종종 해결할 수 없는 비선형 부분 미분 방정식을 처리해야 할 수 있다. 다행히 MARL은 정확한 방정식을 요구하지 않기 때문에 그런 문제는 없습니다.
MFG and MARL
MFG와 MARL의 조합은 두 개의 풀 수 없는 요인이 해결 가능한 방정식을 생성하는 경우 중 하나입니다.
MARL은 효율적으로 부정확한 확률 모델들을 사용하여 작동합니다. 그러나 그 결과는 환경 안에 무한한 에이전트에서 비 실용적입니다.
MFG는 효율적으로 수많은 에이전트들의 행동을 모델링할 수 있지만, 종종 풀 수 없는 식이 만들어집니다.
그래서 각각이 가지는 단점을 해결하기 위해서 하나로 합치면 어떻게 될까요?
| MARL | MFG | |
| 장점 | 부정확환 확률 모델 사용 하여 효율적으로 사용 가능 | 효울적으로 수 많은 에이전트를 모델링 할 수 있음. |
| 단점 | 에이전트가 비실용적으로 움직임 | 풀 수 없는 식이 나오는 경우가 있음. |
두 경우 모두 연구는 MFG 방법이 많은 수의 에이전트를 가진 MARL 시나리오의 복잡성을 획기적으로 줄일 수 있다는 것을 보여주었다고 합니다.
예를 들어, MFG는 MARL 시나리오에서 에이전트의 행동을 모델링할 수 있습니다.
모델링을 할 때, 모든 에이전트들이 유사한 리워드 함수를 가진 상태에서 확률 분포 함수를 가정하기 때문입니다.
(주식 시장의 모든 트레이더는 거래당 수익을 최대화하는 데 초점을 맞추고 있다).
이러한 단순화는 많은 수의 에이전트를 가진 MARL 시나리오를 계산 가능하게 합니다.
다른 에이전트의 작업에 개별적으로 응답하는 에이전트 대신, 이제 각 에이전트는 모든 에이전트에 대한 상태 수집을 공동으로 나타내는 질량에 대응하여 작업을 수행한다.
Prowler.io 연구팀은 MFG와 MARL을 결합한 몇 가지 실험을 실시했습니다.
실험 중 하나는 N 에이전트가 초기 위치에 따라 각 에이전트가 터미널 상태인 원하는 위치로 이동하기 위해 동작을 선택하는 유명한 공간 정체(SC) 게임을 기반으로 했습니다.
특정 지역이 다른 지역보다 점유하기에 더 바람직하지만, 에이전트들은 혼잡한 지역을 점유하는 것을 반대하게 했습니다..
에이전트는 바람직하고 상대적으로 에이전트 농도가 낮은 부품을 점유한 경우 가장 큰 보상을 받는다.
파라미터에 상관없이 2000 정도 되면, 안정화되는 경향이 있는 것을 확인할 수 있었습니다.
이전 실험에서 충격적인 결과는 MFG 또한 RL 에이전트가 long-term planning에서 최적화하기 위해서 영향을 끼쳤다는 것입니다.
예를 들어 SC 게임에서 에이전트는 개체를 충족시키기 위해 바로 가기(수평 이동)를 사용하여 전체적인 보상을 증가시킬 수 있다는 것을 배웁니다.
이러한 방식으로 작동하려면 먼저 에이전트가 개체의 경로와 일치하지 않는 수평 경로를 통과할 때 낮은 보상으로 비용을 발생시켜야 합니다.
이러한 의미에서 에이전트는 장기적인 보상을 극대화하는 경로를 택하는 데 유리한 즉각적인 보상을 포기함으로써 계획을 보여준다.
MFG를 사용하여 MARL 시나리오를 모델링하는 것은 여전히 이론적인 연구에 있습니다.
그러나 초기 연구는 MARL에서 가장 큰 한계점에 대해서 결국에 깨는 잠재력을 보여줬다고 할 수 있다고 합니다.
(operating at large scale with infinite agents)
MARL이 가지는 임팩트는 엄청나게 클 것으로 기대한다.
하지만 MARL 쪽 관련해서 글들을 몇개 보고 확인해보면, 아직은 많이 실험단계에 남아있는 것 같다.
현실에 적용하기 위해서는 많은 문제를 어떻게 푸는 지 잘 관찰하여 참고해야할 것 같다...
Reference
블로그
How Modern Game Theory is Influencing Multi-Agent Reinforcement Learning Systems
Game theory dynamics are present everywhere in multi-agent reinforcement learning systems. What do you need to know about it?
medium.com
Scaling Reinforcement Learning to Infinite Agents Using Mean Field Games
The relatively unknown game theory method might hold the key to massively scalable reinforcement learning systems.
medium.com
자료
https://www.koreascience.or.kr/article/JAKO202022663814865.pdf
https://slidetodoc.com/multiagent-systems-lecture-12-13-university-politehnica-of/
MultiAgent Systems Lecture 12 13 University Politehnica of
1 Learning in AI n What is machine learning? Herbet Simon defines learning as: “any change in a system that allows it to perform better the second time on repetition of the same task or another task drawn from the same population (Simon, 1983). ” In ML
slidetodoc.com
https://cse.buffalo.edu/~avereshc/rl_fall19/lecture_24_MARL.pdf
'관심있는 주제 > RL' 카테고리의 다른 글
| RL) DuelingDQN 알아보기 (0) | 2021.06.03 |
|---|---|
| Paper) Reward is Enough 관련 자료 (4) | 2021.05.31 |
| RL) Double DQN 알아보기 (0) | 2021.05.09 |
| RL) MARL 설명 자료 -2 Stochastic Games (0) | 2021.05.06 |
| RL) MARL 설명 자료 -1 도입과 배경 (0) | 2021.05.05 |