Multi-agent Intro

Main Paper https://link.springer.com/content/pdf/10.1007/s10462-020-09938-y.pdf

A survey on multi‐agent deep reinforcement learning: from the perspective of challenges and applications

Introduction

large number of real-world multi-agent systems are cooperative multi-agent systems. else, multi-agent systems contatin subgroups that can be usefully modeled as cooperative multi-agent system.

/* 일반적으로 세상에는 여러 다양한 multi-agent 문제들이 존재하고, 특히 cooperative한 multi-agent system이 실용적으로 모델링되고 있다. */

 

Multi-Agent Systems are Everywhere

 

 

---

Types of Multi-agent Systems (Settings)

Fully Cooperative

: all the agents are on the same team. interests are perfectly aligned because they're maximizing the same shared team reward function. so the key question is how can they efficiently coordinate their behavior to achieve this shared objective. 

/* 결국 공통된 reward function maximization을 위해서 어떻게 효과적으로 행동을 조절하는가에 대한 문제이다. */

 

this cooperate setting is the simplest one conceptually because our definitions, objectives and solution concepts the carry over nicely from the single-agent setting. 

/* cooperative setting이 접근이 쉬운 이유는 기존의 single-agent에서의 정의, 목적, 솔루션 컨셉과 그대로 이어지기 때문이다. */

 

 

Fully Competitve

: the agents interests are diametrically opposed. so this requires us to really start reasoning in a new game theoretic way and new solution concepts like minimax equilibrium.

/* agent의 이익이 정반대이고, 따라 single-agent problem과는 다르게 새로운 솔루션 컨셉과 게임 이론적 방식을 요구한다. */

 

however such concepts give us a sensible way forward with RL as long as we're happy to take a risk-averse approach of planning for the worst-case scenario in which the other agent behaves optimally.

/* 언급한 컨셉들은, 다른 agent가 optimal하게 행동하는 worst-case scenario에 대해 불확실성을 낮추려고 시도하는(risk-averse) 접근 방식을 취하는 한, RL을 통한 현명한 방법을 제공한다. */

 

여러 agent가 서로 영향을 받는 상황에서 모든 reward의 총합이 항상 0를 유지하는 zero-sum 학습에서 사용될 수 있다. 그에 따라worst-case에서 발생가능한 최대 손실을 최소화하는 Maxmin equilibrium이 유지된다. 

 

 

Mixed

: is called general-sum games which contain both cooperative and competitive aspects. for example, in a negotiation both party stand to benefit from striking a deal but the seller would like a high price and the byer would like a low price. so mixed setting are obviously the most realistic but there are also the most problematic. 

/* cooperative + competitive 문제의 융합이며, 가장 현실적이지만 가장 어렵다. */

 

we can extend solution concepts like minimax equilibrium to Nash equilibrium but learning such equilibrium with RL methods often requires making unrealistic assumptions about the other agents and how they learn which are hard to justify because the agents are not on our team so who knows what they're doing. and even if we can learn these Nash equilibrium that they may not predict though the behavior of agents even if those agents behave actually.

/* RL 방식을 통한 equilibrium을 학습하더라도 다른 agent와 그들이 어떤것을 학습하는지에 대해 비현실적 가정을 하게되고, agent가 내 env 내부에 없기 때문에 무엇을 하고 있는지 알 수 없어 이 equilibrium에 대한 정당화가 어렵다. 만약 Nash equilibrium을 학습하여 agent가 실제로 행동하더라도 agent의 행동을 예측하지 못할 수도 있다. */

=> RL을 통한 method로도 예측이 사실상 어렵다. cooperative한 문제에 비해 훨씬 복잡하다. 

 

어느 한 agent가 큰 이득을 얻게 되더라도, 다른 쪽 역시 여전히 이득을 볼 수 있는 general-sum 학습에서 사용될 수 있다.

그에 따라 서로의 이익이 보장되는 경우 상대방이 선택을 바꾸지 않는 한 자신의 선택 또한 바꾸지 않는 Nash equilibrium이 유지된다.

 

 

---

MDRL research progress: challenges and structures (Multi-agent reinforcement learning)

Many MDRL methods suffer from scalability issues and are sensitive to partial observability. There are two

mainstream structures used in multi-agent settings.

/* MDRL은 scalability issues와 partially observability에 민감하다. */

=> scalability가 가장 중요한 issue이며, 이는 training과 execution하는 구조에 correlate하다.

 

 

decentralizing training and decentralizing execution structure (DTDE)

: each agent is trained independently of the other agents. This structure can handle the scalability problems

caused by the growth of the number of agents, but other problems are emerging, including environment non-

stationary, reward distribution, and independent agents is sensitive to partial observability. 

/* 각 agent가 다른 agent와 indepent하게 훈련되는 구조는 agent 수의 증가로 인한 scalability problem을 해결할 수 있지만, 그에 따른 환경의 non-stationary, 보상 분배, 독립된 각 agent가 부분 관찰성에 민감한 문제 등이 발생된다. */

 

 

centralized training and centralized execution (CTCE) 

: agents are modeled together to learn a joint policy. The disadvantage of this centralized structure is the 

huge input and output space dimension. With the increase in the number of agents, the space dimension 

of the output joint policy renders an exponential increase. 

/* joint policy를 학습하기 위해 함께 모델링 되는 여러 문제를 해결 가능하지만, 너무 큰 input과 output space dimension이 생긴다. agent 수의 증가에 따라, joint policy의 output space dimension이 기하급수적으로 증가한다. 

 

 

centralized training and decentralized execution (CTDE)

: which can solve partial observability problems meanwhile avoid huge input and output space dimensions 

caused by centralized execution.

/* CTCE의 거대한 input, output space dimension을 피하면서, partial observability 문제 또한 해결 가능하다. */

 

 

DTDE와 CTDE 구조에서의 각 issue에 따른, 다양한 방식의 알고리즘들이 연구 및 개발 진행 중이다. 

 

 

---

multi-agent를 다음의 main approach에서 바라보고, 그에 대한 model들이 존재한다. 

Communication learning

=> 어떤(who?) agent와 언제(when?) communicate할 것인지 결정하자

Communication between agents is one of the hotspots in the MDRL field in recent years. Communication learning setting usually considers a set of cooperated agents in the partially observable environment where agents exchange information through communication to promote the cooperation between agents.

/* agent간 communitation setting은 일반적으로, agent간 cooperate를 촉진하기 위해 정보를 교환하는 partially observable env에서의 cooperated agents sets를 고려한다. */

 

 

Agent-modeling

=> communication overhead를 줄이기 위해, 정보를 주는 agent들에 대해 model을 만들어  상대방에 대해 예측하자

An important ability of agents is to reason about the other agents’ behaviors. By constructing model agents can make predictions about the modeled agents’ properties of interest, including actions, goals, beliefs.

/* agent의 중요한 능력은 다른 agent의 action을 추론하는 것. 모델을 구성하면서, agent는 관심 properties에 대해 예측할 수 있다. */

 

Typically, a model is a function that takes a portion of the observed interaction history as input and outputs predictions about some of the related properties of the modeled agent. The interaction history contains information such as past actions taken by the modeled agent in various situations. Various modeling approaches now exist in multi-agent environments, with vastly different approaches and underlying assumptions.

/* model은 observed interaction history의 일부를 입력으로 사용하고, 모델링된 agent의 관련 속성에 대해 prediction한다. interaction history에는 다양한 상황에서 modeled agent가 수행한 과거 action 같은 내용이 포함한다. */

 

 

---

Applications and prospect of MDRL

Deep reinforcement learning has shown success in many single-agent fields, and the next step is to focus on multi-agent scenarios. However, deep reinforcement learning for multi-agent settings is fundamentally more difficult due to non-stationarity, the increase of dimensionality, the partial observability and the credit assignment problem, among other factors.

/* DRL은 많은 single-agent field에서 성공을 보였으며, 그에 심화하여 이제는 multi-agent scenario에 집중할 차례이다. 그러나 MDRL은 non-stationarity, increase of dimensionality, partial observability, credit assignment problem 등의 이유 덕에 근본적으로 multi-agent setting이 어렵다. */

 

In many practical problems and fields, multi-agent deep reinforcement learning has shown great potential, 

with endless research results and various algorithms emerging. In recent years, MDRL methods have been applied in various fields to solve complex real- world tasks. 

/* 그러나 많은 실제 문제와 분야에서 다중 에이전트 심층 강화 학습은 끝없는 연구 결과와 다양한 알고리즘이 등장하면서 큰 잠재력을 보였다. 따라 복잡한 실제 작업을 해결하기 위해 MDRL이 다양한 분야에 적용 중이다.  */

 

Although MDRL is a recent area, there are still many open-source benchmarks that can be used for different characteristics, such as Starcraft Multi-agent Challenge, Hanabi and so on.

/* 또한 MDRL은 최근 영역이지만 Starcraft Multi-agent Challenge, Hanabi 등과 같이 다양한 특성에 사용할 수있는 오픈 소스 벤치 마크가 많이 존재한다. */