sfex tistory blog

https://velog.io/@nawnoes/10.-RNDExploration-by-Random-Network-Distillation

​

RND (Exploration by Random Network Distillation)

​

OpenAI에서 발표한 Exploration에 대한 논문. 18년도까지 여러 강화학습 알고리즘이 있었지만 Reward가 Sparse 한 환경인 몬테주마의 복수에서 인간의 성능을 최초로 넘은 방법이다.

​

Abstract

​

이 논문에서 강화학습을 휘한 Exploration bonus를 소개한다.

이 Exploration bonus는 적용하기 쉽고, 동작하는데 최소의 오버헤드가 든다.

이때 bonus는 고정되고 랜덤하게 초기화된 네트워크로부터 얻은 관측(observations)의 특징(feature)을 예측하는 신경망의 에러를 말한다.

intrinsic and extrinsic reward를 적절하게 결합하여 사용한 flexibility에 대한 method를 소개한다

이 알고리즘을 통해 몬테주마의 복수에서 SOTA를 달성하였고 인간의 성능을 뛰어넘게 된 첫 번째 방법으로 의의를 가진다.

​

1. Introduction

​

기존의 제한 사항들

강화학습은 Policy의 반환값(return)의 기댓값을 극대화하도록 동작한다. 보상(reward)가 밀집된(dense) 한 경우, 대체적으로 잘 학습한다. 하지만 보상이 뜨문뜨문한(sparse) 경우, 학습시키기 어렵다.

실제 세계에서도 모든 보상들이 밀집된 경우는 드물다. 따라서 보상이 드문 경우에도 잘 학습하기 위한 방법이 필요하다.

18년 당시 RL에서는 어려운 문제들을 풀기 위해 환경을 병렬적으로 크게 만들고 경험들을 샘플링하여 얻었지만 이러한 방법은 당시에 소개된 exploration 방법들에 대해서는 적용하는데 어려움이 있었다.

​

제시하는 것

​

간단하고 고차원의 관측에서도 잘 동작하는 Exploration bonus를 소개한다.

이 알고리즘은 policy optimization과 함께 적용할 수도 있고, 계산 효율적이기도 하다.

​

아이디어

유의미한 이벤트가 발생할 때 내부 보상이 높은 것을 볼 수 있다. (2, 8, 10, 21) 은 life를 잃을 때, (3, 5, 6, 11, 12, 13, 14, 15)는 적을 아슬아슬하게 피할 때, (7, 9, 18) 은 어려운 장애물을 피할 때, 그리고 (19, 20, 21) 은 아이템을 습득할 때

​

이 논문에서 제시된 Exploration bonus는 신경망에서 학습된 것들과 유사한 예들에 대해서 prediction error가 현저하게 낮은 것에서 아이디어를 얻었다.

새로운 경험들의 참신함을 측정하기 위해, 에이전트의 과거 경험들에 대해 학습한 네트워크의 prediction error를 사용하였다.

​

prediction error를 극대화하는 것의 문제 이전에 많은 저자들이 지적했듯이 prediction error를 최대화하는 에이전트의 경우는 prediction problem의 답이 입력의 확률적 함수인 transition 들에 대해 끌리게 된다.

​

예를 들어 Noise TV 와 같은 예가 있다. 현재 obsevation에서 다음 observation을 예측하는 prediction problem이 있고, 이때 에이전트가 prediction error를 극대화하도록 행동한다면, 확률적 전환(stochastic transitions)을 찾도록 하는 경향이 있다.

그 예로 무작위로 변하는 아래와 같은 화면인 Noise TV와 무작위로 동전을 던지는 이벤트와 같은 것들이 있다.

​

​

문제를 극복하기 위한 대안

논문의 저자들은 적절하지 않은 stochasticity에 대한 대안을 제시한다. 답이 그것의 입력에 deterministic function인 prediction problem을 exploration bonus으로 정의하면서 대안으로 제안한다.

대안으로는, 현재 Observation에 대해서 output을 fixed randomly initialized network를 사용해서 예측한다는 것이다.

​

강화학습에서 어려운 게임들 🤦‍♂️

Bellemare의 2016년 논문에서 보상이 드물고 탐색이 어려운 게임들을 확인했다. 그 게임들로는 Freeway, Gravitar, Montezuma's Revenge, Pitfall, Private Eye, Solaris, Venture 들이 있고, 어떤 경우에서는 단 하나의 긍정보상도 찾지 못했다.

​

그중에서도 어려운 몬테주마의 복수

​

몬테주마의 복수는 강화학습에서 어려운 게임으로 여겨진다. 게임에서 치명적인 장애물을 피하기 위해 다양한 게임 스킬들에 대한 조합들이 필요하고, 최적의 플레이를 하면서도 보상이 수백 스텝 이상 떨어져 있기 때문에, 보상을 찾기에 어려운 과제로 여겨진다.

몇 논문들에서 꽤 좋은 성과를 거두었지만, expert demonstrations와 emulator state에 대한 접근 없이는 가장 좋은 성과가 전체 방의 절반만 찾아내었다.

​

논문에서 발견한 것 🔍

​

extrinsic reward 없는 경우

extrinsic reward를 무시하여도 agent가 RND exploration bonus를 극대화하도록 한다면 일관되게 몬테주마의 복수 게임에서 절반 이상의 방을 찾았다.

​

extrinsic reward와 exploration bonus 결합

exploration bonus와 extrinsic reward를 결합하기 위해서 수정된 PPO(Poximal Policy Optimization)을 제안한다.

수정된 PPO는 2개의 보상을 위해 2개의 value head를 사용한다.

서로 다른 보상(reward)에 대해 서로 다른 discount rate를 사용하고, episodic과 non-episodic 반환값(return)을 결합한다.

​

성과

first level에서 종종 몬테주마 게임에서 24개의 방 중에서 22개를 찾았고, 이따금씩 클리어하기도 했다. 그리고 같은 방법으로 Venture와 Gravitar에서 SOTA를 달성하였다.

​

​

​

2. Method

​

2.1 Exploration Bonuses

​

1) Count-Based

​

2.2 Random Network Distillation

​

2.2.1 Source of Prediction Errors

일반적으로 prediction error 들은 아래 요소들로부터 나온다.

1. Amount of training data

predictor가 전에 학습한 example 들과 다를수록 prediction error가 높다

2. Stochasticity

target function이 확률적이기 때문에 prediction error가 크다. stochastic transition들은 forward dynamic prediction과 같은 에러들의 원인이다.

3. Model misspecification

필요한 정보가 부족하거나 모델이 target funtion의 복잡도에 맞추기 위해 제한적인 경우

4. Learning dynamics

predictor가 target funtion을 근사하는 과정에서 최적화를 실패했을 때,

2번째 요소는 noisy TV 문제를 야기하고 3번째 요소도 적절하지 않기 때문에 RND에서는 요소 2,3을 제거한다. 3 since the target network can be chosen to be deterministic and inside

the model-class of the predictor network.

​

2.2.2 Relation to Uncertaionty Quantification

RND의 prediction errror는 불확실한 것을 수량화하는 것과 관련이 있다.

​

2.3 Combining Intrrinsic and Extrinsic Return

​

2.4 Reward and Observation Normalization

​

reward

prediction error를 exploration bonus로 사용하는 것이 보상의 크기가 환경에 따라, 시간에 따라 크게 다르기 때문에 모든 환경에서 동작하는 하이퍼파라미터를 찾는 것은 어려운 부분이 있다.

일정한 크기의 reward를 유지하기 위해서 intrinsic reward를 intrinsic reward의 표준편차들에 대한 추정치로 나누어 주어 normalization 과정을 거친다.

​

observation

랜덤 신경망을 사용할 때는 파라미터들이 고정되고 다른 데이터 셋들에 대해서도 조정되면 안 되기 때문에 observation normalization이 중요하다. normalization이 부족하면 임베딩의 분산이 극단적으로 낮아지고 입력에 대한 정보가 조금만 전달되는 결과가 발생할 수 있다.

이러한 문제를 해결하기 위해 continuous control 문제에서 사용하는 observation normalization scheme을 사용하고, 각 dimension에 running mean을 빼고 running standard deviation을 나누어 값을 normalization.

그 후 값이 -5와 5사이에 오도록 잘라준다.

predictor와 target network는 동일한 obsevation nomalization, policy network에 대해서는 사용하지 않는다.

​

References

https://arxiv.org/pdf/1810.12894.pdf

https://kr.endtoend.ai/slowpapers/rnd

https://bluediary8.tistory.com/37

https://seolhokim.github.io/deeplearning/2019/10/11/Exploration-by-random-network-distillation-review/

https://openai.com/blog/reinforcement-learning-with-prediction-based-rewards/

https://bluediary8.tistory.com/37

​

Random Network Distillation 방법은 다음과 같습니다.

​

1. State의 feature를 뽑기 위한 Network를 랜덤으로 초기화 시키고 고정시킵니다. (Target Network, 이 네트워크는 학습하지 않습니다)

​

2. Target Network와 똑같은 구조를 가지는 네트워크를 초기화 시키고 (Predictor Network), Target network에서 나온 state의 feature와 이 predictor network에서 나온 feature의 차이가 최소화 되도록 학습시킵니다.

​

즉, predictor network를 Target Network 화 시키는 거죠. 그리고 그때 state의 차이를 Intrinsic reward로 정의합니다. 결국 다음 state의 feature space가 predictor network가 잘 예측하지 못한 state라면 더 많은 reward를 주게 되는 것이죠.

​

예측한 다음 state와 실제 다음 state의 차이를 intrinsic reward로 정의하는 것은 일반적인 curiosity 모델의 컨셉과 같습니다.

그러나 기존의 curiosity 모델은 현재 state와 action을 통해 다음 state를 "예측해야만" 했다면, RND는 실제 다음 state를 가지고 "feature만을 추출"합니다. 즉, 예측을 잘 해야 할 필요가 없는 것이죠.

​

그러므로 RND의 predictor model을 stochastic 한 게 아니라 deterministic 하게 되는 것입니다.

랜덤으로 초기화시키고 고정시킨 target network 또한, feature를 예측하는 것이 아니라, 추출의 목적이 있기 때문에 굳이 학습 시킬 필요가 없습니다.

어차피 비슷한 state에 대해서는 비슷한 output feature를 내뱉게 됩니다.

Target network의 output을 predictor network로 학습을 시키면 결국 predictor network는 target network와 비슷한 모델이 되어갑니다.

​

하지만 episode 과정 중에 계속 보았던 state에 대해 학습이 되기 때문에, 이전에 보았던 state에 대해서 overfitting 되게 되고, 보지 않았던 새로운 state를 보게 된다면, target network의 output 과는 조금 다른 output을 내게 됩니다.

즉, 새로운 state를 찾아가면서 하는 행동에 대해서는 reward를 많이 줄 수 있게 되는 것이죠.

이때, predictor network와 target network가 완전히 동일하게 돼서 무조건 같은 output을 내지 않을까 하는 의문이 들 수도 있습니다만, MNIST 데이터를 학습시키는 CNN 모델만 생각해도 완전히 overfitting 되는 열 개의 모델을 만들어도 각기 NN의 weight는 다르다는 것을 생각해 보면 직관적으로 절대 같아질 수 없다는 것을 이해할 수 있습니다.

https://medium.com/data-from-the-trenches/curiosity-driven-learning-through-random-network-distillation-488ffd8e5938

Predictor: A series of 3 convolutional layers and 3 fully connected layers that predict the feature representation of s(t+1).

Target: A series of 3 convolutional layers and 1 fully connected layer that outputs a feature representation of s(t+1).

Combining Intrinsic and Extrinsic Returns

In ICM, we used only IR — treating the problem as non-episodic resulted in better exploration because it is closer to how humans explore games. Our agent will be less risk averse since it wants to do things that will drive it into secret elements.

Two Value Heads

Our new PPO model needs to have two value function heads: because extrinsic rewards (ER) are stationary whereas intrinsic reward (IR) are non-stationary, it’s not obvious to estimate the combined value of the non-episodic stream of IR and episodic stream of ER.

The solution is to observe that the return is linear i.e R = IR + ER. Hence, we can fit two value heads VE and VI and combine them to give the value function V = VE + VI. Furthermore, the paper explains that it’s better to have two different discount factors for each type of reward.

DQN

1. 더 깊은 네트워크

2. experience replay

데이터를 버퍼에 모았다가 랜덤 샘플링해서 학습

3. 두 개의 네트워크(train main)로 한쪽을 고정하고 학습 후 고정된 쪽 update

https://youtu.be/S1Y9eys2bdg

https://youtu.be/Fbf9YUyDFww

https://youtu.be/ByB49iDMiZE

https://github.com/hunkim/ReinforcementZeroToAll

hunkim/ReinforcementZeroToAll

Contribute to hunkim/ReinforcementZeroToAll development by creating an account on GitHub.

github.com

몬테카를로 방법 vs 시간차학습(Temporal Difference Learning)

몬테카를로 방법은 종료 상태 sT에 도달해야 가치함수의 갱신이 일어나지만,

시간차 학습(temporal difference learning)은 다음 상태로 진입할 때 곧바로 갱신이 가능합니다.

​

시간차학습 종류

1.Sarsa(onpolicy)

- 출력 : 최적 상태-행동 가치함수

2.Q-Learning(offpolicy)

- 출력 : 최적 정책, 최적 상태-행동 가치함수

3.DQN(CNN + Q-Learning)

https://wordbe.tistory.com/entry/RL-%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-part3-Temporal-Difference-Learning-RL-application

​

[RL] 강화학습 part3 - Temporal Difference Learning, RL application

​

5. 시간차 학습(Temporal difference learning)

가장 혁신적인 알고리즘입니다.

동적 프로그래밍과 몬테카를로 방법의 장점을 겸비하였습니다.

​

1) 정책 평가

에피소드 e = [s0,r0]a0[s1,r1]a1⋯[sT,rT] 에서 샘플 zt를 처리한다면

몬테카를로 방법은 Z(st)에 이 샘플을 추가한 다음 아래 식으로 가치함수를 갱신합니다.

​

​

샘플 zt가 k번째로 추가되었다면, 추가된 순서를 고려하여 다음 식을 세울 수 있습니다.

​

​

v(old)π(st)vπ(old)(st)는 직전까지의 가치함숫값, 즉 먼저 추가된 k-1개의 샘플 평균이고,

r(zt)는 k번째 추가된 샘플의 누적 보상액 입니다.

위 식은 아래와 같은 형식으로 바꿀 수 있습니다. 아래 식은 덧셈 두번과, 곱셈 한번만으로 평균을 갱신하므로 효율적입니다.

​

​

몬테카를로 방법은 종료 상태 sT에 도달해야 가치함수의 갱신이 일어나지만,

시간차 학습(temporal difference learning)은 다음 상태로 진입할 때 곧바로 갱신이 가능합니다.

이것이 시간차 학습의 핵심 아이디어입니다.

특별히 시간차 학습에서는 상태 가치함수를 구할 때 위와 같이 새로운 보상을 구하여 식을 재정의 합니다.

γ는 할인율입니다.

​

상태-행동 가치함수를 추정하려면 아래의 식을 사용합니다.

정책평가

1) 모든 상태에 대해 가치함수vπ(s)를 0으로 초기화한다.

2) 에피소드 e를 생성한다.

3) 위 상태 가치함수 식을 이용하여 각 상태별로 (t=0부터 t= T까지) 가치함수를 갱신한다.

4) 2~3을 반복하여, 멈춤조건에서 멈춘다.

​

다른 상태가치함수의 값을 이용해서 현재의 상태가치함수를 갱신한다는 점에서 부트스트랩과 유사한 점이 있고(즉, 동적프로그래밍와 유사하다.),

에피소드 e를 생성하여 학습한다는 측면에서는 몬테카를로 방법과 유사합니다. 따라서 시간차 학습은 둘의 장점을 취하는 알고리즘으로 평가할 수 있습니다.

​

2) Sarsa

최적 정책을 찾는 알고리즘

시간차를 이용하여 최적 정책을 탐색하는 알고리즘으로 Sarsa, Q-learning 두가지가 있습니다.

​

Sarsa는 상태-행동 버전 식을 사용합니다.

알고리즘은 반복할 때마다 st,at,rt+1,st+1,at+1 라는 정보를 처리하므로 앞글자를 따서 Sarsa라고 합니다.

line 7에서 볼 수 있듯이 Sarsa는 다음 행동을 정책에 따라 결정합니다.

line 8에서는 결정된 행동에 따라 가치함수를 갱신합니다.(즉, 정책을 갱신합니다.)

이러한 방식을 on-policy라고 합니다.

​

3) Q-Learning

Watkins, 1992

Q-learning은 가치함수 갱신을 정책이 아닌 max 연산자로 결정합니다.

Q-learning은 off-policy를 사용한다고 말합니다.

​

Sarsa와 다른 점은 qπ(st+1,at+1)이 maxqqπ(st+1,a)로 바뀐 것입니다.

TD Learning 중 Q-learning을 사용하여 최적 정책을 구하는 방식은 강화학습에서 가장 혁신적이라고 평가하고 있습니다.

6. 근사 방법

위에서 언급한 알고리즘의 출력은 π^ 또는 최적 가치함수 v^ 또는 q^입니다.

π^을 구하기 위해서는 모든 상태와 모든 행동 확률을 표현하기 위해 |S|x|A| 크기의 배열이 필요합니다.

v^는 |S|,

q^는 |S|x|A|

크기의 배열이 필요합니다.

이 배열을 한 번 구하면, 배열을 참조하여 값을 읽으면 되므로, 배열을 참조표(lookup table)라고 합니다.

그런데 |S|,|A|가 크면 메모리 문제가 발생합니다. 모든 배열 요소의 확률을 구하기도 불가능해집니다.

강화학습은 이러한 종류의 문제를 풀기 위해 lookup table을 버리고, 근사 방법을 이용합니다.

선형방정식을 통해 근사하는 방법이 있습니다.

​

가치함수 v는 k개의 매개변수 θ로 표현됩니다.

보통 k<<|S|입니다.

πi(s)는 기저함수로, 서로다른 기저함수가 매개변수만큼 있습니다.

기저함수는 사람이 설계하여 훈련집합으로 최적의 매개변수를 찾는 일은 학습 알고리즘이 담당합니다.

하지만 현재 강화학습은 위 식보다 신경망을 주로 사용합니다.

입력으로는 상태(state), 출력은 보상(reward)입니다.

훈련집합은 에피소드(episode)를 수집하여 구성하고,

학습시 역전파 알고리즘(backpropagation)을 이용합니다. (Sutton, 2017)

​

7. Application Example

TD-gammon은 MLP를, DQN은 딥러닝 기술을 사용하여 가치함수를 근사합니다.

​

1) TD-gammon

Backgammon 게임입니다.

검은 말은 낮은 번호로, 빨간 말은 높은 번호로 이동합니다.

15개의 검은 말이 모두 16번으로 이동한 후 빠져나오면 검은 말이 이기고, 빨간 말이 1924로 이동한 후 먼저 빠져나와면 빨간 말이 이깁니다.

주사위를 굴려 나온 수만큼 한 개의 말을 이동시킬 수 있습니다. 주사위는 2번 던져 서로 다른 말에 적용시킵니다. 하지만 24번의 검은말 하나가 주사위 5가 나와 빨간말로 꽉 찬 19번으로 이동할 수 없습니다. 막는 것이 일종의 전략이 될 수 있습니다.

또한 빨간말이 하나뿐이라면 검은 말이 빨간 말을 잡을 수 있습니다.

잡은 말은 바깥에 두었다가 처음 위치에서 다시 시작해야 합니다.

서로 다른 상태가 10^20개 이상 있으므로 근사 가치함수를 사용합니다.

​

은닉층이 하나인 MLP를 사용하였고,

검은 말, 빨간 말이 놓인 위치를 표현하기 위해 24개 위치 각각에 노드를 4개씩 배정하였습니다.

2 * 24 * 4 = 192개의 노드가 사용됩니다.

또한 시간차 알고리즘을 사용해서 TD-gammon이라 불립니다.(Tesauro, 1995)

​

TD-gammon은 사람의 전략을 가르쳐 주지 않은 채 프로그램 2개가 겨루는 과정에서 학습하는 self-play 방식입니다.

승패의 여부에 따라 상태에 +1, -1 보상을 부여하고 보상이 TDL 알고리즘을 통해 이전 상태로 파급됩니다.

TD-gammon은 지도학습을 전혀 이용하지 않고 자가 플레이로 세계 챔피언 수준에 도달하였습니다.

​

강화학습과 보드게임

틱택토(tic-tac-toe), checkers, 체스, 장기, 바둑입니다.

보드게임을 가장 잘하기 위한 강화학습 연구가 진행되었고 가장 어려운 바둑에서 세계 챔피언 수준의 이세돌을 4:1로 이기는 성과를 기록합니다.

틱택토는 상태의 수가 3^9=19,6833^9=19,683 정도로 근사 가치함수를 사용하지 않더라도 쉽게 최적 정책을 알아낼 수 있습니다.

틱택토는 새로운 프로그램을 테스트하는 용도로 자주 쓰입니다.

checkers는 열약한 하드웨어에서도 체커 게임을 해결하는 시도를 하였습니다.(Samuel, 1959)

체스는 Deepblue라는 프로그램이 세계 챔피언을 이겼습니다.(Campbell, 2002)

당시 VLSI칩은 딥블루라는 슈퍼컴퓨터로 발전하였고, 당시에는 기계 학습 알고리즘보다 하드웨어 속도를 향상시켜 높은 수준을 달성하였습니다. 장기도 이와 마찬가지입니다.

바둑은 훨씬 탐색 공간이 커서 고성능 하드웨어에도 한계가 있었습니다. alphago는 몬테카를로 트리탐색, 프로기사들의 기보를 활용한 지도학습, self-play를 활용한 강화학습, CNN 적용, 고성능 하드웨어와 결합하여 세계 챔피언을 이길 수 있었습니다.(Silver, 2016)

​

2) DQN: Atari video game

므니 등은 Atari 2600 게임 49종에서 자동으로 플레이하는 프로그램을 개발하였습니다. (Mnih et al., 2015)

다양한 게임 해서 동일한 입력, 신경망 구조, 하이퍼 파라미터를 사용하여 전문 플레이어 수준을 달성하였습니다. 29종에서 좋은 성능을 보였습니다.

CNN과 Q-Learning을 결합한 DQN으로 상태를 입력하고, 게임 종류마다 필요한 만큼 출력 노드를 정합니다.

훈련 집합으로 상태, 행동->보상을 학습하여 입력 상태에 따라 최대의 보상이 기대되는 행동을 선택한다.

​

정책 : 현재 상태에서 최대의 가치를 주는 상태로 가는 행동을 선택하는 것

가치 : 상태 최대 기대 보상 값

​

최대한 넓게 깊게(많은 샘플링) 탐색한다.

(행동선택) 정책 모델로 넓게를 효율적으로

(가치 예측) 가치 모델로 깊게를 효율적으로

​

동적 프로그래밍 vs. 몬테카를로 방법

동적 프로그래밍에서는 r(z)를 직접 추정할 수 없어서 순환식을 사용했지만,

몬테카를로 방법은 샘플을 만들어 이를 직접 계산합니다.

또한 몬테카를로 방법에서는 어떤 상태가 자신에 속한 샘플만 가지고 자신의 값을 결정할 수 있으므로, 특정 상태만 골라 가치 함수를 계산하여 시간을 줄일 수 있는 장점이 있습니다.

​

훈련 데이터 수집 방식

1. 현장 샘플링 -> 훈련 집합

2. 시뮬레이션(환경, 에이전트(정책)) -> 에피소드 -> 샘플링 -> 훈련 집합

3. 불완전 모델 정보 -> 샘플 생성 -> 훈련 집합

​

훈련 데이터 형식

1. Z(s) 집합 = 상태 샘플

2. Z(s, a) 집합 = 상태-행동 샘플

​

정책 π 평가(policy evalutation)

정책 π 평가 = 가치 함수(π) = vπ = 샘플의 평균

​

Z(s)를 이용한 상태 가치 함수

Z(s, a)를 이용하여 상태-행동 가치 함수

​

정책 반복

for 정책

for 가치

for 정책

​

가치 반복

for 가치

for 상태

​

최적 정책 탐색

- 모델(MDP, P(s',r|s,a))이 있는 경우: max가 되는 행동을 찾아 정책으로 변환합니다.

- 모델이 없는 경우: Z(s, a)를 사용하여 탐험, 탐사 조절

​

탐험과 탐사 조절

- 오프라인(offline) 방식

- 충분히 큰 훈련 집합 Z를 한꺼번에 수집합니다.

- 지역 최적점을 구하는 것을 걱정할 필요가 없습니다.

- 온라인(online) 방식

- 알고리즘 수행하면서 에피소드를 발생시킵니다.

- 어떤 상태에 우연히 열등한 행동이 먼저 발생했다면 이후 그 행동만 선택할 가능성이 커져

지역 최적점으로 조기 수렴(premature convergence) 현상이 나타날 수 있습니다.

이에 따라 온라인 방식에서는 탐험을 강제할 기법이 추가되어야 합니다.

​ 1) 탐험형 시작(exploring starts) : 에피소드 생성 시 모든 상태-행동 쌍이 골고루 발생하도록 배려

​ 2) ϵ-soft : 주류에서 벗어난 상태-행동에 일정한 확률을 배정하여 선택될 가능성 열기

​

Monte-Carlo method 특성

1) 환경 모델이 없어도 됩니다. (샘플링)

2) bootstrap 방식이 아니므로 관심 있는 상태만으로 구성된 부분집합으로 최적 가치와 최적 정책을 추정할 수 있습니다.

3) Markov property에서 크게 벗어나는 상황에서도 성능 저하가 적습니다. 시작부터 종료까지 정보를 포함하여 에피소드를 충분히 많이 사용하여 학습하기 때문입니다.

https://wordbe.tistory.com/entry/RL-%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-part2-Dynamic-programming-Monte-Carlo-Method?category=1080129

[RL] 강화학습 part2 - Dynamic programming, Monte Carlo Method

​

3. 동적프로그래밍

​

Dynamic programming 강화학습에서 사용하는 고전적인 방법입니다.

MDP 확률분포가 주어지고, 상태, 행동 개수가 적어 계산 시간과 메모리 요구량이 현실적이어야 구현이 가능합니다.

알고리즘 교과서에서 배우는 동적 프로그래밍은 결정론 문제를 풀도록 설계되어 있으므로, 강화학습에 적용할 수 없습니다.

​

강화학습은 스토캐스틱 동적 프로그래밍을 사용합니다.

​

1) 정책 반복 알고리즘

평가 : 현재 정책에서 가치함수 계산

개선 : 가치함수를 이용해 정책을 갱신

정책 반복 알고리즘(policy iteration)은 평가 개선 사이클을 최적 정책을 찾을 때까지 반복합니다.

이때 평가단계는 여러 번 반복하여 개선된 가치함수가 이전보다 좋아야 하므로 많은 시간이 소요 됩니다. 따라서 상태의 개수가 많은 현실 문제에는 적용할 수 없는 단점이 있습니다.

​

2) 가치 반복 알고리즘

value iteration

입력인 MDP를 보고 최적 가치함수를 찾은 후, 그로부터 최적 정책을 찾습니다.

line 6에서 계산한 가치함수는 장기 이득을 내포하고 있으므로, 순간 이득에 머물지 않습니다.

​

위 알고리즘은 반복할 때마다 가치함수를 저장하는 메모리를 별도로 사용합니다. 따라서 그대로 구현하면 메모리 사용이 과다해집니다. 하지만 알고리즘은 현재 - 다음 단계의 2개의 배열만 정의하고 이것을 번갈아 사용함으로써 이 문제를 조금 줄이는 효과가 있습니다.

​

line 13에서 확률을 배분할 때는 A(s) 안의 원소 개수 n 만큼 나누어 1/n씩 공정하게 해도 좋고, 또는 다른 방식으로 모든 합이 1이 되게 배분하면 됩니다. 이 행동 중 어느 것을 취하든 최적을 보장하기 때문입니다.

​

정책 반복과 가치 반복 알고리즘은 다른 상태 값을 보고 자신의 값을 갱신하는 부트스트랩(bootstrap) 방식입니다.

수렴하기 이전까지는 모든 상태가 불완전한 상황입니다.

​

추측 과정에서 MDP는 정확한 보상 값을 제공하고, 보상이 점점 정확한 추측 값에 근접하여 최적점에 도달합니다.

부트스트랩 방식은 모든 상태가 이전 값을 이용해 현재 값을 계산하여야 공평하므로, 하나의 배열만 가지고 갱신하는 제자리(in-place) 연산이 불가능하고, 2개의 배열을 필요로 합니다.

하지만, 제자리 연산으로 구현해볼 수도 있습니다. 이는 비록 공평성은 무시하지만 최적으로 수렴만 할 수 있다면 문제 될 것이 없습니다. 또한 실제 여러 실험에 따르면 제자리 연산을 통해 수렴 속도가 빨라지는 장점이 있는 것으로 밝혀졌습니다.

위 가치 반복 알고리즘에서 v(t+1)(s)를 하나의 v(s)로 표현하고 각 상태를 계산하자마자 대치해 주면 됩니다.

​

정책 반복은

for 정책

​ for 가치

​ for 정책

3중 for 문 구조이지만,

​

가치 반복은

for 가치

​ for 상태

2중 for 문 구조로 가치 반복이 더 빠릅니다.

​

하지만 상태공간이 방대한 백가몬(backammon)과 같은 응용에서 여전히 계산이 불가능합니다.

4. 몬테카를로 방법

​

MDP에 대한 완벽한 지식은 없지만, 불완전한 모델 정보로부터 샘플을 생성할 수 있거나, 에이전트와 환경에서 직접 샘플을 수집할 수 있다면 샘플을 훈련 집합으로 하여 최적 정책을 찾아낼 수 있습니다.

훈련 집합(train set)을 사용하여 학습에 기반을 둔 몬테카를로(Monte Carlo)방법을 설명합니다.

​

1) 훈련집합 수집과 정책 평가

적절한 방법으로 에피소드를 수집했다고 가정합니다.

예를 들어 바둑에서는 게임 시작부터 종료까지 기록, 즉 기보 하나를 에피소드로 사용할 수 있습니다.

에피소드 e를 다음 식으로 표현합니다.

e = [s0,r0]a0 [s1,r1]a1 ⋯[st,rt]at ⋯[sT,rT]

​

한 에피소드로부터 샘플을 여러 개 수집할 수 있습니다.

방법은 두 가지가 있습니다.

​

첫 방문(first visit): 상탯값이 여러 번 발생하면 최초 발생만 인정

모든 방문(every visit): 전부 인정

예제를 들어봅시다.

e = [10,0]동[11,0]북[7,0]남[11,0]서[10,0]서[9,0]북[5,0]북[1,5]

​

상태 10은 t=0, t=4 두곳에서 나오므로

first visit에서는 t=0만 인정하여 수집하므로

Z(10) = [10,0]동[11,0]북[7,0]남[11,0]서[10,0]서[9,0]북[5,0]북[1,5]

​

입니다.

every visit에서는 t=0, t=4 둘다 모두 수집하여

Z(10) = [10,0]동[11,0]북[7,0]남[11,0]서[10,0]서[9,0]북[5,0]북[1,5] , [10,0]서[9,0]북[5,0]북[1,5]

​

가 됩니다.

샘플은 몬테카를로 방법을 사용하기 위해 Z(s)에 추가됩니다.

몬테카를로 방법은 주로 환경 모델에 대한 완벽한 확률분포 없이 수행되는데,

상태만으로 최적 정책을 추정할 수 없어 상태-행동 정보가 필요합니다.

따라서 상태-행동 샘플을 수집하여 Z(s, a) 집합을 구해야 합니다.

에피소드는 실제 현장 수집 또는 시뮬레이션으로 생성합니다.

알파고를 만든 DeepMind는 KGS 바둑 서버에서 16만 개의 기보에서 3천만 개의 샘플을 수집해 알파고를 학습하였습니다. (Silver, 2016)

경기당 평균 184수까지 둔 꼴이며, T=184인 셈입니다. 알파고는 자신 복제 프로그램 2개를 대결하게 하여 샘플을 수집하기도 했습니다.

시뮬레이션은 환경 모델을 활용합니다. 모델의 확률분포 P(s', r | s, a)가 주어진 경우 확률분포에 따른 난수를 이용하여 쉽게 생성할 수 있습니다.

정책 평가(policy evalutation)

정책 π를 평가, 즉 π에 해당하는 가치함수를 추정하는 일은 아주 쉽습니다.

샘플의 평균으로 vπ를 추정합니다.

위 식은 Z(s)를 이용하여 상태 가치함수를 추정,

아래 식은 Z(s, a)를 이용하여 상태-행동 가치함수를 추정합니다.

​

동적프로그래밍 vs. 몬테카를로 방법

동적 프로그래밍에서는 r(z)를 직접 추정할 수 없어서 순환식을 사용했지만,

몬테카를로 방법은 샘플을 만들어 이를 직접 계산합니다.

또한 몬테카를로 방법에서는 어떤 상태가 자신에 속한 샘플만 가지고 자신의 값을 결정할 수 있으므로, 특정 상태만 골라 가치함수를 계산하여 시간을 줄일 수 있는 장점이 있습니다.

​

2) 최적 정책 탐색

모델(MDP, P(s',r|s,a))이 있는 경우: max가 되는 행동을 찾아 정책으로 변환합니다.

모델이 없는 경우: Z(s, a)를 사용하여 탐험, 탐사 조절합니다.

탐험과 탐사 조절

​

오프라인(offline) 방식 : 충분히 큰 훈련집합 Z를 한꺼번에 수집합니다. 지역 최적점을 구하는 것을 걱정할 필요가 없습니다.

​

온라인(online) 방식 : 알고리즘 수행하면서 에피소드를 발생시킵니다. 어떤 상태에 우연히 열등한 행동이 먼저 발생했다면 이후 그 행동만 선택할 가능성이 커져 지역 최적점으로 조기 수렴(premature convergence) 현상이 나타날 수 있습니다.

이에 따라 온라인 방식에서는 탐험을 강제할 기법이 추가되어야 합니다.

​

​ 1) 탐험형 시작(exploring starts) : 에피소드 생성 시 모든 상태-행동 쌍이 골고루 발생하도록 배려

​ 2) ϵ-soft : 주류에서 벗어난 상태-행동에 일정한 확률을 배정하여 선택될 가능성 열기

Exploring starts

여기서의 예는 상태-행동 데이터 Z(s, a)를 훈련집합으로 사용하는 버전입니다.

탐험형 시작은 상태가 가질 수 있는 값과 행동이, 가질 수 있는 값의 모든 조합이 0보다 큰 발생 확률을 갖게 하여 한 번도 시도되지 않은 조합을 배제하는 전략입니다.

ϵ−soft

가능한 모든 상태-행동 쌍이 골고루 발생하도록 배려하는 방침이 반영되었습니다.

line 12가 핵심인데, 최적행동으로 선택되지 못한 나머지 행동에 작은 확률을 배분하여 현재 최적이 아니더라도 선택될 가능성을 열어 정책 개선에 공헌을 할 수 있도록 합니다.

Monte-Carlo method 특성

1) 환경 모델이 없어도 됩니다. (샘플링)

2) bootstrap 방식이 아니므로 관심 있는 상태만으로 구성된 부분집합으로 최적 가치와 최적 정책을 추정할 수 있습니다.

3) Markov property에서 크게 벗어나는 상황에서도 성능 저하가 적습니다. 시작부터 종료까지 정보를 포함하여 에피소드를 충분히 많이 사용하여 학습하기 때문입니다.

Reference

기계학습, 오일석, 2017, 09. 강화학습

환경(environment)

에이전트(agent)

상태(state)

행동(action)

보상(reward)

탐험과 탐사 갈등(Exploration and exploitation conflict)

마르코프 결정 프로세스(MDP) Markov Decision Process

정책(policy)

가치(value)

상태 가치 함수(State value function)

벨만 수식(Bellman equation)

상태-행동 가치함수(state-action value function)

할인 누적 보상액(discounted accumulating reward)

MDP(Markov Decision Process) 확률분포

상태 -> 상태 가치 함수 -> 상태-행동 가치함수 -> 행동

상태 -> 가치 -> 정책 -> 행동

https://wordbe.tistory.com/entry/RL-%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-part1-policy-value-function

[RL] 강화학습 part1 - policy, value function

[RL] 강화학습 part1 - policy, value function Reinforcement Learning 1. 강화학습 원리와 성질 state, action을 번갈아 가면서 목표를 달성합니다. 강화학습 교과서(Sutton, 2017) 참고 1) 계산 모형 상태, 행..

wordbe.tistory.com

강화학습의 목표는 '누적' 보상액을 최대화하는 것입니다.

에이전트가 행동을 선택하는 데 사용하는 규칙을 정책(policy)이라고 하며, 강화 학습 알고리즘은 최적의 정책을 찾아야 합니다.

탐험과 탐사 갈등(Exploration and exploitation conflict) :

k-손잡이 밴딧(k-am bandit) 문제

이 둘의 방식을 보완하기 위해 균형 방식을 사용합니다.

2번에서 잭팟이 나온 이후로 2번 기계를 더 자주 선택하는 대신 다른 기계에게도 계속 기회를 주며 잭팟이 또 터지면 새로운 정보를 고려하여 확률을 배분하고 수정하는 것입니다.

마르코프 결정 프로세스(MDP) Markov Decision Process

현재 상태에서 행동을 결정할 때 이전 이력은 중요하지 않고, 현재 상황이 중요한 조건을 마르코프 성질(Markov Property)을 지녔다고 합니다. 예를 들면 바둑이 있습니다.

강화학습은 마르코프 성질을 만족한다는 전제하에 동작합니다.

따라서 Markov property를 근사하게라도 만족하는 문제에 국한하거나, 근사하게 만족할 수 있도록 상태 표현을 설계해서 적용합니다.

결정론적(Deterministic) MDP :​ 딱 한가지 상태와 보상이 있는 경우, 나머지 보상은 전부 0

확률론적(Stochastic) MDP :​ 다음 상태와 보상이 확률적으로 결정되는 경우

정책과 가치함수

강화 학습의 핵심은 좋은 정책을 찾아내는 것입니다.

좋은 정책이 있으면 누적 보상을 최대로 만들 최적 행동을 매 순간 선택할 수 있습니다.

정책 공간은 너무 방대해서 최적 정책을 찾는 접근 방법은 무모하며,

최적 정책을 찾아가는 길잡이 역할을 하는 가치함수를 소개합니다.

1) 정책(policy)

정책이란 상태 s에서 행동 a를 취할 확률을 모든 상태와 행동에 대해 명시한 것입니다.

최적 정책 찾기

goodness(π)가 정책 π의 품질을 측정해주는 함수라고 합시다.

학습 알고리즘은 위를 만족하는 정책 π^를 알아내어야 합니다.

바둑 같은 문제 에서는 상태공간(state space)이 방대합니다.

정책 공간(policy space)은 서로 다른 정책 집합을 뜻하며, 상태 공간보다 훨씬 방대합니다.

따라서 강화학습에서는 정책공간을 일일이 직접 탐색하는 대신 '가치함수'를 이용합니다.

최적 가치함수를 찾으면 최적 정책을 찾는 것은 사소한(trivial) 문제가 됩니다.

2) 가치함수(Value function)

가치함수는 특정 정책의 좋은 정도(상태 s로부터 종료 상태 이르기까지 누적 보상치의 추정치)를 평가합니다.

정책 π에서 추정하며 상태 s의 함수이므로 vπ(s)로 표기합니다.

즉, 위에서 쓰인 goodness는 곧 가치함수로 바뀝니다.

P(z)는 경로 z의 발생확률, r(z)는 경로 z의 누적 보상액입니다.

강화학습에서 유한 경로를 가진 과업을 에피소드 과업(episode task)이라고 합니다.

반면, 무한경로를 가진 과업을 영구과업(continuing task)이라고 합니다.

특별히 영구과업은 무한대 보상을 막기 위해 할인 누적 보상액(discounted accumulating reward)을 사용합니다.

γ를 할인율(discounting rate)이라고 하며, 0≤γ≤1입니다.

0이면 rt+1만 남으므로 순간의 이득을 최대화하는 탐욕 방법인 근시안적 보상액이 되며,

1이면 맨 위의 식처럼 된다.

따라서 할인 누적 보상액은 현재에서 멀어질수록 보상을 할인하여 공헌도를 낮추는 전략을 사용합니다.

가치함수 추정을 위한 순환식

마치 점화식처럼, 다음 상태에서의 가치함수를 표현하여, 가치함수를 간단히 쓸 수 있습니다.

스토캐스틱 프로세스에서 가치함수 추정

지금 까지 수식은 결정론적 프로세스(deterministic process)였습니다.

결정론적 프로세스는 많은 응용을 설명하지 못하지만,

현실에서 모든 요인을 상태 변수에 반영하는 대신 주요 요인만 반영하고 나머지는 무시한 상황서의 상태, 행동, 보상을 스토캐스틱 프로세스(stochastic process)라고 합니다.

스토캐스틱한 성질은 P(s', r|s,a) 확률로 표현됩니다. 이는 MDP 확률분포입니다. 즉, 상태 s에서 행동 a를 취했을 때 상태 s'로 전환하고 보상 r을 받을 확률입니다. 스토캐스틱은 이 값이 여러개일 수 있으므로, 모두 더해줍니다.

가치함수는 MDP 확률분포가 제공하는 정보와 정책 π가 제공하는 정보를 모두 활용하여 정책을 평가합니다.

무한 경로를 가진 응용문제에는 할인율을 적용한식을 사용하면 됩니다.

위 두식은 상태 가치 함수(State value function)라고 합니다.

위 두식의 순환식을 가치함수를 위한 벨만 수식(Bellman equation)이라고 하며, 현재 상태의 가치는 다음 상태의 가치의 관계를 간결하게 표현합니다.

이와는 다르게 상태와 행동에 대한 가치함수는 상태-행동 가치함수(state-action value function)라고 하며 식은 아래와 같습니다.

3) 최적 가치 함수

최적 가치함수를 알아 최적 정책을 쉽게 결정할 수 있습니다.

상태 가치함수는 mean 연산을 통해 구하는 반면, 최적 가치함수는 max 연산을 통해 구합니다.

1) 처음에는 임의값으로 정책을 설정하고 출발합니다.

2) 정책에 따라 가치함수를 계산합니다.(정책의 품질 평가)

3) 얻은 가치함수로 더 나은 정책으로 개선합니다.

​ 정책의 평가와 개선은 MDP 확률분포를 기초로 이루어집니다.

4) 정책 개선 싸이클이 없을 때까지 반복합니다.

​ 동적 프로그래밍, 몬테카를로 방법, 시간차 학습 알고리즘은 모두 이 아이디어에 근거합니다.

[출처] http://www.aitimes.com/news/articleView.html?idxno=129355

인공지능이 타협도 한다고?...딥마인드, 승부 넘어 윈윈하는 AI 교육 - AI타임스

딥마인드가 인공지능(AI)에게 협력과 타협을 교육시켜 여러 이익관계자들의 선호사항을 최대한 반영한 결과를 도출시키고 있다.

www.aitimes.com

벤처비트(https://venturebeat.com)는 10일(현지시각) 구글 알파벳 자회사인 딥마인드가 ‘디플로머시(Diplomacy)’라는 보드게임으로 AI를 훈련시킴으로써 승패가 갈리는 기존 게임에서 벗어나 AI가 한 단계 더 나아간 타협과 협력을 학습하도록 하고 있다며 이를 소개했다.

[영어 기사] https://venturebeat.com/2020/06/10/deepmind-hopes-to-teach-ai-to-cooperate-by-playing-diplomacy/

타협과 협상을 학습시키기 위한 AI 교육용 게임 ‘디플로머시(Diplomacy)’는 윈윈을 꾀하도록 고안된 말 그대로 ‘외교’ 게임인 셈이다.   

이들은 프리프린트 서버인 아카이브(Arxiv.org)에 게재된 논문에서 ‘디플로머시(Diplomacy)’ 게임 결과 ‘지속적인 개선’을 보이며 높은 점수를 얻은 AI 시스템에 대해 설명했다.

딥마인드의 기존 AI 시스템은 헥스(Hex) 게임, 장기, 포커와 같은 대규모의 복잡한 게임에서 강력하고 경쟁력 있는 플레이를 했지만 이 중 대부분은 다른 플레이어의 패배해야 승리할 수 있는 2인용 제로섬 게임이다.

그러나 안타깝게도 이러한 빼어난 성과를 보여주는 AI이지만 모든 것이 제로섬 게임이 아닌 인간의 현실 세계에 적용하기엔 부족한 점이 있다.

예를 들면 혼잡한 도로를 둘러싼 교통 노선 계획, 계약 협상, 그리고 고객과의 상호 작용과 같은 업무들을 처리하는 일은 제로섬 게임이 될 수 없다. 이 문제들을 해결하기 위해서는 모든 관련 당사자들의 선호가 어떻게 일치하고 충돌하는지에 대한 타협과 고려를 포함시킬 수밖에 없다.

AI 소프트웨어 에이전트들이 이기적일 때에도 조정과 협력을 통해 공동의 이익을 얻을 수 있기 때문에 다양한 그룹 간 상호 작용은 타인의 목표와 동기 부여에 대한 복잡한 추론을 필요로 한다. (에이전트는 최대한의 보상을 얻기 위해 시행착오를 거치며 여러 번의 반복으로 가장 효율적인 길을 스스로 탐색하는 시스템을 말한다.)

이를 훈련시키기 위해 고안된 딥마인드의 ‘디플로머시(Diplomacy)’ 게임은 7명의 플레이어가 유럽의 주(Province) 단위 지도 상에서 여러 단위부대(유닛)들을 제어토록 함으로써 AI가 이러한 상호작용을 하도록 한다.

디플로머시 게임에서 ‘주’는 보급센터다. ‘유닛’들은 주를 점령함으로써 보급센터를 확보한다. 보급 센터를 더 많이 소유한 플레이어는 더 많은 유닛을 만들 수 있고, 보급센터 대부분을 소유하는 플레이어가 게임에서 승리한다.

매 게임마다 모든 플레이어들은 자신의 모든 부대를 동시에 34개 지역 중 한 곳으로 이동시켜야 하며, 하나의 유닛은 같은 플레이어나 다른 플레이어 소유의 다른 유닛을 지원함으로써 또 다른 유닛의 저항을 극복하게 만들 수 있다. (대체로, 힘이 같은 유닛은 한 지방을 지탱하거나 인접한 공간으로 이동할 수 있다.)

유닛 간의 상호 의존성 때문에 플레이어들은 자신의 유닛 움직임에 대해 다른 플레이어들과 협상해야 한다. 그들은 다른 선수들의 움직임과 그들의 움직임을 조정함으로써 이익을 얻기 위해 대기하며, 다른 선수들이 어떻게 행동할지 예측하고 그들의 행동에 이러한 예상을 반영해야 한다.

저자들은 “우리는속임수 행동의 등장과 발견을 연구하고...실제 세상에서 어떻게 그러한 행동을 완화시킬 수 있는지알고 있다는 것을 확실히 하기 위해 디플로머시 같은  게임을 사용할 것을 제안한다"라고 썼다. 이들은 “디플로머시에 관한 연구는신뢰와 동맹을 수립하고 유지하는 것을 둘러싸고 발생하는 어려운 문제 해결을 포함하는,타인과 성공적으로 협력할 수 있는 인공 에이전트를 만드는 길을 열어주게 될 것이다“라고 덧붙였다.

딥마인드는 어떤 노골적 소통도 허용되지 않는 ‘언론 없는’ 디플로머시 변종에 초점을 맞췄다.

이 AI는SBR(Sampled Best Response)라는 접근법으로정책 반복 기법을 사용해 일부 보상을 극대화해 주며 강화 학습 에이전트들을 훈련시켰다. SBR는 가상 플레이는 물론 플레이어 액션에 대한 거의 최고 수준의 반응에 근접하는 정책 반복 기술을 가지고 많은 수의 액션(10⁶⁴)을 보여주는 플레이어들이 디플로머시를 받아들이도록 했다. 

딥마인드의 시스템은 이를 반복할 때마다 게임 데이터 세트를 생성하는데, 개선 운영자(improvement operator)로 불리는 모듈이 선택한 동작으로 이전 전략(정책)과 가치 함수를 사용해 이전 정책을 무너뜨리는 정책을 찾아낸다. 그런 다음, 게임 결과뿐만 아니라 개선 운영자가 선택할 행동을 예측하는 정책 및 가치 함수(기능)를 훈련한다.(It then trains the policy and value functions to predict the actions the improvement operator will choose as well as the game results.)

앞서의 SBR은 반대자의 정책에 대항해 플레이어 시스템 에이전트의 예상 반응을 극대화해 줄  정책을 알아낸다. SBR는 다수 플레이어의 게임에서 SBR을 사용하도록 맞춤화된 알고리즘 제품군인BRPI(Best Response Policy Iteration)와 결합돼 있다. 이 중 최고급의 것은 최신 BR만 예측하도록 정책을 훈련시키고, 현재의 경험적 전략을 제공하기 위해 역사적 체크포인트를 명시적으로 평균화해 제시한다.

딥마인드는 이 시스템의 성능을 평가하기 위해 서로 다른 알고리즘의 6개 에이전트와 참조 코퍼스(말뭉치)에서 독립적으로 추출한 6명의 플레이어 간에 이뤄진 정면 대결 승률을 측정했다. 이 시스템의 승률은 특별히 높지 않았다. 각 게임의 평균 5개의 시드를 기록했는데 12.7~ 32.5%였다. 그러나 딥마인드는 이 시드들이 지도학습으로 훈련된 에이전트들에 비해 크게 향상됐다고 말한다.

딥마인드의 시스템에 의해 6개 에이전트가 제어되는 6 대 1의 게임에서 특히 딥넷(Dip Net)이라는 알고리즘에 대한 딥마인드 에이전트들의 승률은 훈련을 통해 꾸준히 향상됐다.

향후 연구에서 연구자들은 에이전트 악용 가능성(exploitability)을 줄이고, 잠재적으로커뮤니케이션을 통해 다른 사람들의 인센티브(동기)에 대해 추론하는 에이전트 구축 방법을 찾아 나설 계획이다.

저자들은 이 게임에서 플레이를 향상시키는 것은외교이며 게임의 복잡하게 혼합된동기와여러 플레이어의 상황을 조사하기 위한 필수 조건이라고 하며…디플로머시에 적용된 방법은 외교에 대한 직접적 영향을 넘어 비즈니스, 경제, 물류 영역 등에 적용될 수 있다고 한다…

디플로머시나 유사한 게임에 사용될 외교 훈련 능력을 갖춘전술적 기본(베이스) 에이전트를 제공함으로써 이 연구결과는-그것이 다른 기계와 함께든 인간과 함께든 간에-동맹을 결성할 능력이 있고 보다 진보된 커뮤니케이션 능력을 이용하는 에이전트 연구를 위한 길을 열었다고 말했다.

출처 : AI타임스(http://www.aitimes.com)

[논문] https://arxiv.org/pdf/2006.04635.pdf

This example highlights elements that make Diplomacy unique and challenging. Due to simultaneous move resolution, players must anticipate how others will act and reflect these expectations in their own actions. Players must also use a stochastic policy (mixed strategy), as otherwise opponents could exploit their determinism. Finally, cooperation is essential: Germany would not have been able to prevent France from moving to BUR without Italy’s help.

Diplomacy is specifically designed so that no player can win on their own without help from other players, so players must form alliances to achieve their ultimate goal. In the No-Press variant, this causes pairwise interactions that differ substantially from zero-sum, so difficulties associated with mixed-motive games arise in practice.

Evaluation Methods

- Head-to-head comparision(일대일 비교)

- Winrate Against a Population(인구 대비 승리)

- Policy Transitivity(정책 전이)

- Exploitability(악용 가능성)