A dissertation submitted for the degree of Doctor of Philosophy in the University of Cambridge, August 1996
Abstract
: 일반적으로 다른 agents' action이 agent에게 영향을 준다고 가정하지 않는다. agent는 학습 도중, 다른 state에서 unrecognised action이 있을 수 있는데, 이 때 이것들을 모두 action set에 추가하고 모든 state에 대한 모든 action에 대해 huge Q-value를 배우지 않는다. 대신, W-Learning은 각 state에서 W-value를 통해 승리할 가능성이 가장 큰 agent가 승리하지 않을 경우, 가장 큰 고통을 겪을 가능성이 있는 agent로 선택되는 방식을 배운다. 자율 이동 로봇과 같이 여러 병렬 목표를 가진 system을 위한 self-organising action-selection scheme이다. 해당 논문에서는 Q_i(x, a)를 학습하는 것 보다 더 적은 메모리를 요구하는 W_i(x) 학습을 제안한다.
Decentralised model of mind
: 'drive strength' or 'importance variable'와 같은 의미인 W-value는 가장 큰 값이 나머지와의 경쟁 속에서 승리하여 해당 목표의 action을 실행한다. Ant World example 내에서 agent는 다음의 state x = (i, n, f, p)를 받아 action a = {0-7, 8(stay still)}을 실행한다.
- 아래 그림은 W-value에 따라 경쟁에서 이긴 agent의 action을 실행한 결과이다.
→ W-value는 실행한 action에 대해 가장 큰 고통을 받을 가능성의 agent를 선택하는 기준이 된다.
W-learning (Minimize the worst unhappiness)
W-value W_i(x)
: W_i(x)는 현재 state에서의 policy에 따르지 않는 다른 action을 따랐을 때, 얼마나 나쁜지에 대한 estimate를 의미한다. W-learning은 agents가 동일한 action spaces를 공유하지 않을 때, 이러한 estimate를 구축하는 방법이다.
- winner agent A_k가 action을 실행했을 때, A_k를 제외한 나머지 모든 agent는 다음을 update한다. 예측한 값과 실제 값의 차이를 'error term'이라 부르고, 이를 최소화 하기를 원한다. 이 때, r_i는 reward, y는 A_k로부터 일어난 next state y이다.
W-learning
: discrete space에서 lookup table에 W_i(x)를 각각 저장하고 다음을 update한다. 이 때, winner agent W_k(x)는 update하지 않는다.
- W을 통한 측정을 사용하게 되면, agents는 현재 누구와 경쟁하는지에 대한 명확한 지식을 필요로 하지 않고, 그들이 야기하는 inference에 의해 간접적으로만 경쟁을 인식한다. agents는 그들이 따르고 있던 action을 하지 않을 때, 비로소 inference를 인식한다.
- W-learning은 매 time-step마다 다음 pseudocode를 실행한다. W의 변화는 state x에서 next time에 다른 winner가 나올 수 있다는 것을 의미한다.
→ highest W-value를 출력하는 state의 winner agent가 action a_k를 실행하고, 그 외 모든 agents들은 W-value를 update한다.
Comparsion of Q and W
Q-learning
: various actions이 얼마나 좋은지에 대한 평가이다. 우리는 D를 학습하고, agent 자신의 action 실행으로 인해 d가 발생한다.
W-learning
: 다른 actions이 얼마나 나쁜지에 대한 평가이다. D는 이미 학습했고, 다른 agent's action 실행으로 인해 f가 발생한다.
- W-learning은 다음과 같이 update 된다.
→ W-learning은 Q-learning과 유사하게 update를 진행한다.
Progress of competition
: 일반적으로, W를 학습할 때, Q는 이미 사전에 학습되었다고 가정한다. Q는 agent 시작에 한 번 학습되는 반면, W는 반복해서 재학습된다. action a^*_i(x)가 학습되면, 모든 경쟁자들에게 이를 홍보한다.
- A_i의 update는 다음과 같이 근사된다. 이 때, r_i와 y는 winner agent A_k에 의해 야기된다.
- 따라 다음과 같이 표현될 수 있다. 편차 d_ki(x)는 random variable이다. 우리는 이때, A_k's action이 A_i에 의해 확인되지 않더라도, 우리는 a = a^*_k(x)일 때, stationary distribution P^i_xa(r)를 여전히 가지고 있다고 가정한다. 그래서 A_k가 동일한 action을 계속 제안하더라도, 우리는 probabilisitic transitions r_i를 가지고 있기 때문에 y는 constant가 아닌 random variable이다.
- V*_i도 다시 쓰여지게 되어, variation d_ki(x) 은 variation r_i와 variation y에 의해 야기된다. 이 둘은 variation P^i_xa(r), variation P_xa(y)에 의해 야기된다. d_ki(x)는 P^i_xa(r), P_xa(y)에 의해 stationary probability distribution이다. 명확하게는 다음과 같다.
- 만약 현재 policy에 의한 action을 따르게 되면, 우리는 f=D를 기대할 수 있다. 만약 따르지 않는다면, f ≤ D를 기대할 수 있다.
- 우리는 E(d_ki(x))를 P^i_xa(r)과 P_xa(y)를 알지 않는 이상, 계산이 불가능하다. 그래서 Q-learning에서와 같이 sampling을 통해 이를 계산한다.
→ 비록 A_i가 given action set에서 optimal action을 배웠다고 할지라도, 다른 agent에서 A_i보다 더 좋은 unrecognised action이 있을 수 있다. 즉, 스스로의 action을 따르지 않는 것이 A_i에게 긍정적인 결과를 도래할 수 있다.
Scoring W_k(x)
: 다른 agents' W-value들은 E(d_ki(x)) >= 0인데 반해, leader's W-value는 0으로 수렴하기 때문에 update에서 제외한다. agent가 lead를 시작하자마자 잃을 때까지 W-value가 떨어지므로, 우리는 이러한 system 하에 lead가 계속해서 바뀌며 경쟁을 하게 된다.
Strict highest W
: 만약 W_k(x)가 초기에 불공정하게 큰 값으로 설정이 된다면, 다른 agents가 도달이 불가능하여 절대 lead가 바뀌지 않게 된다. 따라 우리는 W_i(x)를 W_min ≤ W ≤ 0 사이의 범위의 랜덤으로 초기화한다.
- 그러나 비행운적 sample에 의해서 지나치게 높은 W_k(x)가 발생하기도 한다. 이 때는 시간이 지남에 따라 감소하는 Boltzmann distribution로 highest W를 선택한다. random winner 선택을 하면, W-value를 완전히 랜덤하게 시작하도록 할 수 있다.
Conclusion
- global reward에 영향을 받지 않는 Q-learning과 hierarchical Q-learning은 경험적으로 좋은 성능을 보였다. 그러나 기존 방식은 explicit global reward로 학습이 어렵다는 한계가 있다. 또한 reward가 global reward function의 일부이며 다른 (x,a) pair에 영향을 주는, generalisation을 사용하기 때문에 collective 방식에서 고통받는다.
- self-organising 방식에서 우리는 agents 자체에게 힘을 양도하여, 가끔 사용되는 agents들을 강력하게 일깨운다. worst unhappiness를 최소화하는 W-learning은 그동안 Q-learning과 Hierarchical Q-learning이 해오지 못했던, 모두의 agents들에게 집중이 가능하다.
- 결국 action selection 방식은 W-problem과 Q-problem으로 분리된다. single goal를 위한 various action selection에는 Q-learning을 사용하는 것이 좋지만 하나의 방식이 모든 것을 포용할 수는 없다. 따라 더 큰 system에서는 Q와 W를 분리하지 않는다면 complexity에 빠질 수 있다.
→ agent가 단독으로 행동하는 이상적인 env에서 action의 goodness / fitness / utility에 대해 Q를 사용하고, 다른 agent에 상대적인 strength / bid에 대해 W를 택하는 적합한 action selection 방식을 선택하는 것이 좋다.
댓글