The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems, AAAI 1998
학회: AAAI
년도: 1998
저자: Caroline Claus and Craig Boutilier
1. introduction
RL이 problem of coordination in multiagent system에 generality와 robustness인 것 때문에 쓰일 수 있다.
이 논문에서 3가지 질문은 가진다.
1) 다른 에이전트가 없는것처럼 러닝하는 에이전트와 다른 에이전트와의 joint action의 value와 다른 agent의 strategy를 러닝하는거랑 다른가
2) 멀티 에이전트 상황에서 RL 알고리즘이 converge하는 것을 보증할 수 있나
3) rate of converge와 limit point가 시스템 구조나 action selection strategy에 영향을 받을 수 있나?
이 논문에서는 위 질문을 agent가 공통의 interest(reward)를 갖는 repeated game에 대해 생각한다. 또한 이 문제에 Q-Learning을 사용하는 대해 다룬다.
2 Preliminary Concept and Notation
2.1 single stage games
multiagent에 의해 컨트롤되는 시스템에서의 연속적 결정 문제를 다루는데 이를 간단히 하기 위해 n-player cooperative repeated games에 다룬다. stage game, cooperative, randomized strategy, strategy profile, best response, Nash equilibrium에 대해 설명
2.2 learning in coordination games
여러 multiple optimal joint action이 있을 경우 문제가 생길 수 있다. suboptimal이나 uncoordinated joint action을 선택할 경우가 있다. 이를 problem of equilibrium selection이라고 한다.
coordinated action 선택은 stage게임을 같은 agent끼리 반복해서 플레이해서 학습해 나갈 수 있다. 예로 fictitious play가 있다 (다른 agent의 strategy를 count를 통해 belief를 가짐)
이 방법을 통해 에이전트가 multiple best responses가 존재할 때 randomize한다면 한 equilibrium으로 converge하고 적절한 mechanism을 적용하면 optimal equilibrium에 도달할 수 있다.
다른 agent에 action selection에 대해 정확히 볼 수 있는 경우말고 observation을 갖는 경우가 있다.
2.3 reinforcement learning
RL을 통해 agent는 expect reward를 과거의 경험을 기반으로 estimate할 수 있다. 여기서는 Q-Learning에 대해 알아본다.
Q-Learning으로 학습해 나가는 과정에서 다른 exploration strategy가 적용될 수 있는데 Q-Learning은 exploration strategy에 종속적이지는 않다.
exploration strategy 에는 action을 uniform하게 선택하는 nonexploitive exploration과 가장 잘 estimate 된 action을 선택하려고 하는 exploitive exploration이 있다. exploitive exploration의 대표적인 예로는 Boltzmann exploration이 있다.
동시에 학습하는 경우 다른 agent의 존재는 Q-learning에 장애가 될 수 있다. agent가 다른 agent들이 존재하는 경우에 Q-learning을 할 때, agent는 nonstationary environment에서 학습하는 것이다(다른 agent의 행동에 따라 Q-value값이 달라짐). 즉, Q-value의 converge가 보장되지 않는다.단, agent들의 strategy가 정착되면 Q-learning이 성공적으로 된다고 볼 수 있다.
두 다른 방식이 multiagent system에서 Q-learning에 적용될 수 잇다.
1) independent learner
다른 agent들의 행동에 관계 없이 Q-Learning을 수행한다.
2) Joint action learner
Q-value를 다른 agent들의 action까지 고려한 joint action을 가지고 학습한다. 이는 다른 agent들의 행동을 볼 수 있다는 것을 의미.
이때 한 action에 대한 expected value값은 다른 agent들의 행동에 대한 확률값과 조인트 action의 Q값을 이용해서 구함.
이 값을 Boltzmann exploration의 Q 값으로 씀.
다른 사용자들의 action을 직접적으로 보는게 아니라 observation을 받아 partially observable model이 되는 경우가 있음
3. Comparing Independent and Joint-Action Learner
1의 1)에 대한 답변 내용
IL에 있어서 nonexploitive exploration을 하는 것은 평균적으로 agent의 action선택중 어느 하나가 다른 하나보다 좋다고 여기지 않는다. 다른 이의 전략이 확률적이고 learning rate의 감소로 인해 Q-value의 값이 같지 않을 수 있다.
대신 여기서는 explotivie exploration을 사용. 알려진 value의 사용은 agent들이 그들의 선택에 있어서 같은 이유로 선택을 조직하게 한다.
JAL이 다른 joint action에 대해 Q-value값을 구분해도, action selection mechanism에 이 구분 능력이 제한된다. Q-value값을 직접적으로 update하는 것이 아니라 belief를 이용하여 나온 평균값으로 boltzmann exploration을 하기 때문.
4.Convergence and Game Structure
1의 2) 3)에 대한 답변 내용
앞에서 IL과 JAL이 exploration을 줄여가면서 equilibria에 수렴해 가는 것을 봤다면 game structure에 따라 어떻게 수렴하는지 본다.
예1) penalty 문제
구조에 따라 optimal에 수렴하느냐 마느냐
예2) climbing game
구조에 따라 한 equilibrium에 쉽게 수렴하느냐 마느냐
어느 한 곳에 도달하는 것은 보임. 그럴려면 4가지 조건 만족.
(3조건이 필요한 이유는 어떤 2조건에 의해 모든 action이 샘플 되지만 어떤 경우 시간에 따라 deterministic한 경우가 잇을 수 있기 때문)
Theorem1.
위 네 조건이 만족하면, 델타와 입실론의 함수인 T가 있고 어떤 시간 t에서의 deterministic할 확률을 Et 나타낼 때, Et와 1의 차이가 입실론보다 작을 확률이 1-델타보다 크다. 시간이 늘어나면 determinitic에 가까워 진다를 의미(?)
agent가 어떤 equilibrium에 잇을 경우 그 곳을 벗어날 확률이 0이 아니다. 그러나 이는 agent들이 agent들에 대한 exploratory move의 연속을 요구한다. 이게 일어날 확률은 시간이 지남에 따라 작아지고 (exploitive exploration이라서) 벗어나기 힘들어진다. 각 agent의 exploration의 감소는 동시에 exploration할 확률이 크게 줄어든다.
convergence는 exploration의 감소에 달렸다. converge가 오래걸리고 learning rate가 작을 수록 초기에 편향된 Q-value를 극복하는데 많은 경험이 필요하다.
JAL의 단점으로는 많은 경험을 바탕으로 하는 belief는 많은 반대되는 경험을 요구한다.(상대방 action의 belief를 바꾸는데 많은 경험이 필요)
5. Biasing Exploration Strategies for Optimality
위에서 살펴본걸로 optimal equilibrium에 convergence하지 않는다. optimal에 converge하려면 agent들이 동시에 벗어나는 경우를 생각해야함. 이러한 경우는 best response를 선택하는데 위배됨.
궁극적으로 long run optimal equilibrium에 이르는 결정은 sequential decision problem과 같음
long run optimality을 위한 exploration strategy, 근시적 휴리스틱(현재 state에만 기초하므로)
1) Optimistic Boltzman
boltzman exploration에서 action을 수행할 때 받을 수 잇는 가장 큰 Q값(가능한 다른 agent들의 action도 고려)을 사용.
2) Weighted OB
OB의 Q값에 weight를 붙임 weight는 match가 일어날 확률, 즉 다른 agent들이 max가 되게 하는 action을 선택할 확률
3) Combined
최대값과 평균값을 비율을 주어 더한 값을 사용, 기존 boltzman에 잠재성을 추가.
Normal Boltz만과의 penalty game(k=-10) 실험결과
1) normal boltman: optimal이나 suboptimal로 converge
2) OB: multiple equilibria에 때문에 결과가 구림, 다른 사람의 전략에 대한 생각에 제한이 없어서?
3) WB: belief를 써서 매번 optimal에 수렴
4) optimal에 수렴하고 제일 좋은 퍼모먼스