35th Conference on Neural Information Processing Systems (NeurIPS 2021)
Abstract
: multi-agent의 scalability problem을 풀기위한 algorithm은 dependency가 static, fixed, local인 경우에만 가능하다고 알려져 있다. 해당 논문에서는 dependency가 non-local, stochastic한 setting에 적용되는 scalable actor critic framework를 제안하고, convergence rate가 network에서 정보 확산 속도에 어떻게 depend하는지 보여주는 finite-time error bound를 제공한다.
Introdunction
: 다양한 MARL problem 중 가장 큰 문제는 scalability이다. 각 agent의 local state space, local action space가 작더라도 global state space, global action space의 크기가 커질 수 있어 Q-learning과 같은 RL algorithm 적용이 불가능하다. scalability problem을 해결하기 위해서 network structure와 같은 application-specific structure을 활용하는 approach가 존재했다. 이는 static, local dependency structure를 기반으로 한다.
- 그러나 실제 networked system에는 본질적으로 time-varying, non-local dependency가 존재한다. 예를 들어, wireless network에서 각 node가 다른 node로 packet을 보낼 때 다른 node로부터 interference를 받을 수 있고, 결과적으로 잠재적인 collision으로 인해 각 node의 local reward는 own local state, own local action에 따라 달라질 뿐만 아니라 다른 node의 action에 따라 달라진다. 이러한 problem은 mobility와 stochastic network 조건을 고려할 때 더욱 복잡해진다.
- dependency model를 항상 수정하고 localize할 수도 있지만, 이는 결과적으로 성능 저하가 발생한다. 따라 dependency가 stochastic하고 non-local setting에서 확장 가능한 algorithm이 필요하다.
→ 실제 env에서는 agent가 action을 현재 time-step에 수행했을 때, 이전에 수행된 다른 agent's action에 잠재적인 영향을 받는 non-local dependency를 가지고 있거나 mobility와 같은 조건에 따른 stochastic dependency를 해결하기 위한 algorithm이 필요하다.
Contribution
: 해당 논문에서는 모든 agents가 random subset of agents에 depend 되도록 허용되는 stochastic non-local dependency structure를 소개한다. 따라 최적에 가까운 local policy를 scalable manner로 학습하는 SAC(Scalable Actor Critic) algorithm을 제안한다. 핵심 방식은 아래와 같다.
1. Dependency class가 μ-decay property로 이어진다.
: 해당 속성은 exponential decay property를 일반화하며 stochastic, non-local dependency setting에 대해 효율적이고 확장 가능한 algorithm 설계를 가능하게 한다. 그러나 깊은 interaction이 더 자주 나타날수록 정보가 network에서 더 빠르게 퍼질 수 있으며 이는 제안된 방법의 효율성 저하가 이루어질 수 있다.
2. Key technical result는 infinite-norm contraction 및 state aggregation을 특징으로 하는 general stochastic approximation scheme이다.
: 이 result를 각 agent의 local neighbor을 사용하여 network MARL에 SA(state aggregation)를 제공한다. 특히 SA를 사용하여 TD/Q-learning에서 finite-time bound를 생성한다는 것을 보여준다. resulting bound는 SA를 사용한 asynchronous Q-learning의 first finite-time bound이다.
Networked MARL
Wireless communication env
: Background paper에서의 env인 multiple access point가 있는 wireless network를 고려한다.
- user set은 N = {1, 2, ... , n}, network access point set은 Y = {y_1, y_2, ... , y_m}로 표기된다.
: 각 user i는 access point의 subset Y_i ⊆ Y에만 access 가능하다. 여기서 user i, j는 access point를 공유하는 경우에만 neighbor로 취급한다. 즉 user i's neighbor는 N_i = {j ∈ N : Y+i Y_j ≠ 0}이다.
Process
1. 각 user는 packet queue를 관리한다. time-step t에서 probability p_i로 user i는 initial deadline이 d_i인 새로운 packet을 수신한다.
2. user i는 queue의 earlist packet을 available set Y_i의 한 access point로 보내거나, 보내지않고 현재 상태를 유지하도록 선택할 수 있다.
3. 만약 y_k ∈ Y_i로 보내는 action이 수행되고, 이 때 다른 user가 동일한 access point로 보내지 않으면 user i's queue에서 earlist packet이 access point y_k에 depend하는 success probability q_k로 전송된다. packet이 성공적으로 전송되면 user i's queue에서 삭제되고 user i는 1의 reward를 받는다. 그러나 다른 user가 y_k로 보내기를 선택하면 충돌이 발생하고 전송이 실패한다.
4. 그 후 system의 time-step t가 이동한다. 나머지 packet들의 모든 deadline이 1씩 감소하고, 0인 경우에은 queue 내의 packet이 폐기된다.
- s_i(t+1)은 s_Ni(t), a_Ni(t)에만 depend하며 이는 우리가 고려하는 Local interaction structure에 적합하다.
State s_i
: user i's local state s_i는 d_i로 표현되는 packet queue의 특성이며 binary tuple s_i = {e_1, e_2, ... , e_di} ∈ S_i = {0, 1}^di로 표시된다. 여기서 각 ￡ ∈ {1, ... , di}, e_￡ ∈ {0, 1}은 user i가 ￡ deadline packet을 가지고 있는지 여부를 나타낸다.
Action a_i
: action space는 A_i = { null } ∪ Y_i이며 여기서 null은 전송하지 않는 동작을 나타낸다.
Reward r_i
: local reward는 전송이 성공했을때만 r_i(s_Ni(t), a_Ni(t) = 1, 아니면 0으로 주어진다.
Experiment env
: undirected graph G(N, E)와 연관된 agent network를 고려한다. 여기서 N{1,2,··· ,n}은 agent set를 나타내고, E ⊆N x N은 edge set을 타나낸다. d_g(i, j)는 graph G에서 두 agent를 연결하는 최단 경로의 edge 수로 정의된다.
- N^k_i는 agent i로부터 k-hop neighborhood를 의미한다. M ⊆ N은 s_M/a_M을 사용하여 M에 있는 agent의 state/action에 의해 형성된 tuple을 나타낸다.
1. Active link set L
: active link set는 agent N에 대한 directed graph이며 agent 간의 interaction structure를 특성화한다. 보다 구체적으로 active link set은 모든 self-loop를 포함한 directed edges set이며, 일반적으로 (j, i) ∈ L은 agent j가 active link set L의 agent i에 영향을 미칠 수 있음을 의미한다.
- active link L이 주어지면 agent i에 영향을 줄 수 있는 자신을 포함한 모든 agents set에 대해 나타낼 수 있다.
- 해당 논문에서는 some joint distribution D에서 독립적으로 그려지는 active link set pair(L^s_t, L^r_t)를 고려한다. L^s_t와 L^r_t의 역할은 시간 t에서 state transition과 reward의 dependence structure를 의미한다.
2. Transitions L^s_t
: time-step t에서 current state s(t), action a(t), active link set L^s_t가 주어지면 다음 개별 state s_i(t+1)이 독립적으로 생성되고 N_i(L^s_t)에 있는 agent's state/action에만 의존한다.
3. Rewards L^r_t
: 각 agent는 reward function r_i와 연결된다. time-step t에서 N_i(L^r_t)의 agent's state/action으로 정의된다. global reward는 local reward의 합으로 정의된다.
4. Policy
: 각 agent는 B-hop neighborhood에 따라 달라지는 localized policy를 따른다. 여기서 B ≥ 0은 fixed integer이다. 특히 time-step t에서 global state s(t)가 주어지면 agent i는 states of neighbor agents N^B_i를 기반으로 local policy를 채택한다.
5. Objective
: 모든 agent가 cooperate하여 discounted global reward를 최대화 하는것이 목표이다. 목적 함수는 다음과 같고, r(s(t), a(t))는 time-step t에서 모든 local reward의 합으로 정의된 global reward이다.
μ-decay Property
: Q-function size가 agent 수에 exponentially하게 크다는 MARL challenge를 해결하기 위해, Q-function에 대한 새로운 structural decay property를 식별하였다. 즉, 각 agent i의 local Q-function은 주로 i 근처에 있는 neighbor agents' state에 의해 결정된다. 해당 property는 agent가 멀리 있는 agent의 state 및 action에 대한 dependency를 절단하여 Q-function의 dimensionality를 줄일 수 있도록 하기 때문에 scalable algorithm 설계에 중요하다.
- recent networked MARL에서 network가 static한 경우 exponential decay가 사용되었다. 그러나 stochastic network setting에서 일반적으로 exponential decay를 기대하는 것은 너무 크므로 보다 일반적인 개념인 μ-decay를 도입한다.
- μ(k)는 k가 infinite가 될 때, 0으로 수렴하는 function이다. 이전에 연구된 exponential decay는 아래와 같다.
- 직관적으로, u-decay property가 유지되고, u(k)가 k가 증가함에 따라 빠르게 감소하면, global Q-function을 대략적으로 분해할 수 있다. 이 때, ^Q_i는 agent i의 k-hop neighborhood의 state 및 action에 depend한다.
- 위 property를 통한 분해가 존재한다는 증명 아래, 위와 같은 value의 분해를 학습하는 approach를 제안한다.
→ u-decay property가 입증 가능하므로 global Q-function은 networked MARL model에서 decomposed Q-function으로 직접 분해될 수 있으며, 분해에 대한 error는 증명이 가능할 정도로 작다.
Scalable actor critic algorithm
: Q-function의 u-decay property에 영감을 받아 새로운 SAC(Scalable Actor Critic) algorithm을 제안한다.
1. Critic part(line 2-7)
: local Q-function을 evaluate하기 위해 local trajectory{(s_(Nki), a_(Nki), r_i)}인 agent i의 k-hop neighbor에 대한 state, action, reward를 사용한다.
2. Actor part(line 8-9)
: local Q-function을 통해 estimated partial derivative를 계산하고, partial derivative로 local parameter를 update한다.
- algorithm은 policy dependency structure를 확장한다. 더 이상 dependency가 completely local하지 않는다. 이제 B-hop neighborhood로 확장된다. 시간에 따라 변하는 dependency는 algorithm에 복잡성을 추가하지 않는다.
- 각 agent i는 학습 process 동안 k-hop neighborhood 내에서 정보를 query 및 저장만 하면 된다. parameter k는 accuracy와 complexity의 균형을 맞추도록 설정할 수 있다. 특히, k가 증가함에 따라 computation, communication, space complexity가 증가하는 대신 error bound가 더욱 tight해진다.
→ u-decay property에 근거해 분해한 local Q-function을 사용한 critic update와 local policy gradient를 이용한 actor update를 진행한다. 즉, global이 아닌 일부 k-hop neighbor agents 정보만을 사용한 근사로도 학습이 가능하다.
Proof idea
: general asynchronuous stochasic approximation(SA) scheme에 대한 새로운 finite-time 분석을 진행한다. u-decay에 의해 활성화된 truncation은 state aggregation의 한 형태를 제공하게 된다. 해당 SA scheme는 TD-learning 또는 asynchronous Q-learning에도 확장이 가능하다.
Stochastic approximation
1. Finite-state Markov chain
: N = {1, 2, ... , n}은 state space이고, {i_t}는 Markov chain에 의해 방문한 sequence of states이다. x ∈ R^N과 function R^N → R^N은 r-contraction in infinity norm를 의미한다.
- update rule of SA scheme는 아래와 같고, w(t)는 noise sequence이다. parameter x(t)는 F의 고유한 고정점에 수렴하는 것으로 나타난다.
일반적으로 networked MARL에서는 parameter x에서 N의 모든 state에 대한 항목을 계산하는 것이 아니라, 'aggregated entries'를 계산하려고 한다. 특히, 각 time-step에서 생성된 후, 추정 h를 사용하여 parameter x의 어떤 차원을 update해야 하는지 결정한다.
2. Generalization of (2)
: N = {1, ... , n}은 state space of {i+t}이고 M = {1, ... , m}, (m <= n)은 abstract state space이다. 추정 h: N → M는 N의 모든 state를 M의 abstraction로 전환해준다. parameter x는 x R^M과 function F: R^N → R^N에서 우리는 x(0) = 0에서 시작하여 x(t) ∈ R^M을 update하는 generalized SA scheme를 고려한다.
→ 여러 Theorem과 Assumption을 통해 stochastic approximation에서 finite-time convergence를 보일 수 있다.
State aggregation
: network setting을 넘어서는 SA의 영향을 설명하기 위해 TD-learning에서의 학습 결과를 소개한다. 또한 도입한 u-decay property가 network setting에서 자연스러운 state aggregation을 제공하므로 분석에 유용하다.
- SA를 사용한 TD-learning에서 Markov chain이 방문한 state sequence가 {i_t}인 경우, TD(0)의 update rule은 아래와 같다. h: N → M은 N의 모든 state를 M의 abstraction state 축소해주며, reward r_t는 time-step t에서의 E[r_t] = r(i_t, i_t+1)를 의미한다.
- F를 bellman policy operator라고 취급하면, function F의 ith dimension는 아래와 같다.
- value function V*는 아래와 같으며, feature matrix와 noise sequence는 다음으로 정의된다.
- equation (6)에서 TD(0)의 update rule를 SA scheme (3)로 재작성할 수 있다. 따라 state aggregation를 사용한 TD-learning에 대한 finite-time error bound를 얻을 수 있다.
→ 여러 수학적 증명을 통해, TD-learning, Q-learning에서도 statea aggregation을 적용 가능하다.
Conclusion
: 모든 agent가 임의 subset과 상호작용이 가능한 setting에서 최적의 local policy를 증명 가능하게 학습하는 Scalable Actor Critic algorihtm을 제안하고 분석한다. local Q-function의 decentralized approximation은 approach의 핵심이다. SAC는 centralized tabular approach보다 훨씬 적은 메모리를 소비하지만, Q^i를 저장하기 위해 각 agent i가 요구하는 메모리는 k에 대해 exponentially 증가한다. 따라 여전히 메모리 문제가 발생할 수 있다. 따라 truncated state / action pair에 추가 function approximation를 적용하고 SAC와 유사한 finite-time convergence를 얻을 수 있는지에 대한 open challenge가 남아있다.
댓글