References

• Action Branching Architectures for Deep Reinforcement Learning (2017, AAAI)

Motivation

기존의 Discrete-action algorithm(DQN, DDQN, Dueling DDQN 등)은 action dimension이 높아질 수록 그에 따라 output layer의 node 수가 exponential 하게 증가한다는 문제가 있었다. 각 action dimension $d$별로 $n_d$개의 action이 있고 $N$-dimensional action space 상황을 가정한다면 agent가 명시적으로 고려해야 하는 action 수는 $\Pi_{d=1}^Nn_d$ 이다. 이러한 고차원 action dimension에 따른 급격히 팽창하는 행동 공간(= 탐색공간)은 강화학습 에이전트의 학습을 어렵게 한다. Action Branching Architectures for Deep Reinforcement Learning(2018, AAAI) 에서는 이를 해결하기 위해 하나의 Shared Decision Module과 그 뒤를 잇는 여러개의 network branch로 이루어진 network architecture를 제안한다. 이때 branch는 각 action dimension별로 1개씩 할당되며, Shared Decision Module은 개별 branch들을 조율(Coordination)하는 역할을 맡는다. 해당 architecture는 개별 차원의 행동에 독립성을 부여하며 자유도(degree of freedom) 수에 비례하여 output node의 수가 선형적으로 증가할 수 있게 한다. 즉 앞서 가정한 상황과 동일한 상황 하에서 기존 discrete action algorithm의 output node의 개수는 $\Pi_{d=1}^Nn_d$였던 데에 반해 branching architecture를 적용한 알고리즘의 output node 수는 $\sum_{d=1}^N n_d$이다. 해당 논문에서는 이러한 Branching Architecture를 기존의 Dueling Double Deep Q-Network(D3QN)에 적용시켜 Branching-Dueling Q-network (BDQ)라고 명명한다. 해당 논문에서는 Independent Dueling Q-Network (IDQ)와의 비교를 통해 Shared Decision Module의 필요성을 증명한다. 이후 policy based algorithm인 Deep Deterministic Policy Gradient (DDPG)와의 비교를 통해 BDQ의 우수성을 입증한다.

Action Branching Architecture

Figure 1. Schematic of Action-Branching Network Architecture.

BDQ는 이전 칼럼에서 작성한 Dueling Architecture에 Branching Architecture를 더한 구조이다. 앞서 설명한 대로 먼저 input layer와 이어진 Shared Decision Module(Figure 1의 Shared representation)에서는 먼저 latent representation을산출한다. 해당 latent representation은 각각 common state-value와 factorized action advantage value를 계산하는 데에 사용된다. 이렇게 계산된 각각의 state value와 개별 action dimension에 대한 action advantage value들은 aggregate layer에서 합쳐져서 최종적인 Q-value를 산출해낸다 (산출된 전체 Q-value의 개수는 $\sum_{d=1}^N n_d$). 이때 각 action dimension별 value aggregating method는 dueling network에서 사용한 방식과 동일하다. 이는 다음과 같다:

Network update를 위한 temporal-difference (TD) target은 기본적으로 Double DQN에서 제안했던 방식을 차용하여 action selection과 action evaluation을 분리한다. BDQ를 위한 TD target을 계산하는 간단한 방법 중 하나는 action dimension별로 td target을 계산하는 것이다. 이는 다음과 같다:

이때 $r$은 단일 scalar값이다. 또 다른 방법은 global target값을 계산하는 것이다. 논문에서는 아래의 2가지 방법을 제시한다.

저자들에 의하면 식 $(4)$를 이용한 방법이 식 $(3)$을 이용한 방법에 비해 좋은 성능을 보였으며, 모든 실험에 대하여 $(4)$번 방법을 적용한 BDQ를 사용했다.

최종 Loss function을 계산할 때는 아래의 2가지 방법을 고려해볼 수 있다:

실험 결과 식 $(5)$번 방법이 식 $(6)$번에 비해 성능이 소폭 향상되는 것을 확인할 수 있었으므로 식 $(5)$번을 채택하여 사용한다. 이렇게 계산된 loss 값을 이용하여 계산된 Gradient가 backpropagation될 때, 분기점으로 돌아오는 Gradient들은 기본적으로 모두 더해지는 연산을 거치게 된다. 이에 따라 shared network module이 받게 되는 gradient의 크기가 branch의 개수에 비례해서 커지게 되는데 이를 방지하기 위해 backpropagation시에 분기점에서의 graident크기를 $\frac{1}{N+1}$로 rescaling한다. 이때 $N$은 branch의 개수이고 나머지 $1$개는 common-state value estimator로의 분기를 반영한 값이다.

본 논문에서는 Prioritized Experience Replay Buffer (PER)을 적용한다. PER을 적용하기 위해서 개별 transition에 priority를 매겨야 하며, 개별 priority는 td-error를 기반으로 매겨진다. Branch별 td-error의 크기를 유지하며 정보손실을 최소화 하기 위해 priority $p$는 다음과 같이 정의 된다:

Experimental Results

Figure 2. Experimental results of Dueling DDQN and BDQ

왼쪽부터 $N=3,4,5$ 환경이다. $N=3$에서는 $n=5,9$일 때는 BDQ와 Dueling DDQN 모두 안정적으로 학습하는 모습을 보여준다. 차원수가 $N=4$로 높아진 환경에서는 $n=9$일때 Dueling DDQN의 수렴속도와 성능이 현저히 떨어지는 모습을 볼 수 있었으며, $N=5,n=9$인 환경에서는 output node의 수가 $9^5$ ($59,049$)로 폭발하면서 학습 자체가 불가능 했다.

아래의 Figure 3은 OpenAI의 MuJoCo gym의 4개의 benchmark domain에서의 Dueling DDQN, IDQ, DDPG 그리고 BDQ(proposed)의 성능을 보여준다. Action space의 dimension이 높아질 수록 IDQ와 Dueling DDQN은 학습이 되지 않는 것을 확인할 수 있으며 Dueling DDQN같은 경우엔 Walker2d-v1 에서부터는 아예 학습이 되지 않는 모습을 볼 수 있다. 또한 가장 큰 탐색 공간을 가지는 Humanoid-v1에서는 BDQ가 DDPG보다 훨씬 좋은 성능을 내는 모습을 확인할 수 있다. 더하여 Walker2d-v1과 Humanoid-v1 에서 볼 수 있듯이 $n=17$일 때와 $n=33$일 때 total number of possible action에서 큰 차이가 보임에도 불구하고 BDQ는 둘 모두에서 유사한 최종 성능 수준으로 수렴하는 것을 볼 수 있다.

Figure 3. Experimental results of Dueling DDQN, IDQ, DDPG and BDQ for OpenAI’s MuJoCo Gym manipulation and locomotion benchmark domains.

Table1. Dimensionality of the OpenAI’s MujuCo Gym benchmark domains. $\text{dim}(o)$ denotes the observation dimensions(Dimensions of input state vector)

Implementation

Update 예정

• Network 구현상의 차이점 (vs Dueling architecture)
• Train code상의 차이점 (vs Dueling architecture , MuJoCo env상에서)

# Dueling architecture
class DuelingQNetwork(nn.Module):

    def __init__(self, n_states, n_actions, hidden_dim):
        super().__init__()

        self.n_states = n_states
        self.n_actions = n_actions
        
        dim1 = hidden_dim
        dim2 = hidden_dim // 2
        dim3 = hidden_dim // 4
        dim_head = hidden_dim // 8
        
        # === 1. shared network ====
        self.shared = nn.Sequential(
            nn.Linear(self.n_states, dim1),
            nn.Mish(),

            nn.Linear(dim1, dim2),
            nn.Mish(),

            nn.Linear(dim2, dim3),
            nn.Mish()
        )
        
        # === 2. Value Head  === 
        self.value_head = nn.Sequential(
            nn.Linear(dim3, dim_head),
            nn.Mish(),

            nn.Linear(dim_head, 1)
        )

        # === 3. Advantage Head ===
        self.adv_head = nn.Sequential(
            nn.Linear(dim3, dim_head),
            nn.Mish(),

            nn.Linear(dim_head, n_actions)
        )


    def forward(self, state):
        shared = self.shared(state)
        value = self.value_head(shared)
        advs = self.adv_head(shared)

        return value, advs


    def get_q_values(self, state):
        value, advs = self.forward(state=state)
        advs_mean = advs.mean(dim=-1, keepdim=True)
        advs_normalized = advs - advs_mean
        q = value + advs_normalized

        return q
        
        
 
 
 
 
 
 # Branching Dueling architecture
class BD3QNetwork(nn.Module):
    def __init__(self, n_states, n_actions, n_act_dim, hidden_dim): # [Refactoring Point] hidden_dim 추가
        super().__init__()
        
        self.n_states = n_states            # Number of Input States
        self.n_actions = n_actions          # Number of PDR
        self.n_branches = n_act_dim         # Number Of Branches

        dim1 = hidden_dim
        dim2 = hidden_dim // 2
        dim3 = hidden_dim // 4
        dim_head = hidden_dim // 8

        # === 1. shared network ====
        self.shared = nn.Sequential(
            nn.Linear(self.n_states, dim1),
            nn.Mish(),

            nn.Linear(dim1, dim2),
            nn.Mish(),

            nn.Linear(dim2, dim3),
            nn.Mish()
        )

        
        # === 2. Value Head (항상 사용함) === 
        self.value_head = nn.Sequential(
            nn.Linear(dim3, dim_head),
            nn.Mish(),

            nn.Linear(dim_head, 1)
        )

        # === 3. Advantage Head ====
        # n_act_dim(num of branch)만큼 Advantage Head 생성
        self.adv_heads = nn.ModuleList([
            nn.Sequential(
                nn.Linear(dim3, dim_head),
                nn.Mish(),

                nn.Linear(dim_head, n_actions)
            ) for _ in range(self.n_branches)
        ])

    def forward(self, state):
        """
        state: (B, n_states)
        return:
            value: (B, 1)
            advs:  (B, n_branches, n_actions)
        
        이때 B: Batch Size
        """
        shared = self.shared(state)
        value = self.value_head(shared)
        advs = torch.stack([head(shared) for head in self.adv_heads], dim=1)  # shape = (B, n_branches, n_actions)
        
        return value, advs

    def get_q_values(self, state):
        value, advs = self.forward(state=state)
        # value shape = (B, 1)
        # advs shape = (B, n_branches, n_actions)
        
        # 1. 각 branch 내에서 advantage 정규화 (Dueling Network Architecture)
        advs_mean = advs.mean(dim=-1, keepdim=True)     # shape = (B, n_branches, 1)
        advs_normalized = advs - advs_mean              # shape = (B, n_branches, n_actions)

        # 2. Q(s,a) = V(s) + (A(s,a) - E[A(s,a)])
        value_expanded = value.unsqueeze(1)             # shape = (B, 1, 1)
        q = value_expanded + advs_normalized            # shape = (B, n_branches, n_actions)

        return q                                        # shape = (B, n_branches, n_actions)

Appendix

해당 논문에서 저자들은 Independent Dueling Q-Network (IDQ)를 BDQ의 비교군으로 제시하며 Fully-Cooperative Learning(완전 협동 학습) agent들이 겪는 5가지의 주된 문제점을 언급하며 IDQ의 실패 이유를 설명하고 있다. 이는 Multi-Agent Reinforcement Learning (MARL)에서 자주 언급되는 문제점 인것 같으므로 향후 학습을 위해서 한번 짚고 넘어가자.

1. Non-stationarity (끊임없이 변하는 환경)

여러 독립된 Agent를 학습을 시키면, 나를 제외한 나머지 agent들의 정책변화가 나에게는 곧 환경의 변화로 작용한다. 이러한 문제는 agent의 개수가 증가함에 따라서 심화된다.

2. Alter-exploration (타인의 exploration으로 인한 noise)

내 기준에서 최선의 행동(exploitation)을 선택했는데, 다른 agent는 exploration을 했을 경우 전체 결과(joint-action)가 망가지고 낮은 보상을 받는 문제이다. 이또한 agent의 개수가 많아질 수록 매 action decision point마다 누군가 하나라도 exploration을 할 확률이 높아지기 때문에 자신의 행동에 대한 올바른 평가를 할 수 없게 된다.

3. Shadowed equilibria (가려진 균형: 리스크 회피로 인한 하향 평준화)

최고의 보상을 (Global Optimum)을 달성하려면 모든 agent가 합을 맞춰야 한다. 그 합을 맞추는 과정에서 많은 패널티를 받게되는데 패널티를 회피하기 위해 agent들이 suboptimal로 수렴하는 현상을 말한다. 이또한 agent의 수가 많아질 수록 심화된다.

4. Pareto-selection (정답 간의 충돌)

가장 높은 보상을 주는 최적의 행동 조합이 환경 내에 여러개 존재할 때 발생하는 문제이다. 예를들어 3개의 agent가 있는 환경에서 (A,A,A)와 (B,B,B) 이렇게 2개의 최적 행동 조합이 있다고 가정해 보자. 첫번째 agent는 최적의 action 조합이 (A,A,A)라고 학습되어 A를 선택하고 2번째 agent는 (B,B,B)라고 학습되어 B를 선택하게 되면 최종 action은 (A,B,..)가 되며 좋지 않은 결과를 낳게 된다.

5. Stochasticity (불확실성의 증폭)

기본적으로 환경 자체가 가지고 있는 state transition의 무작위성에, non-stationarity와 Alter-exploration이 더해져 시스템 전체의 불확실성으 통제 불가능한 수준으로 증폭되는 현상을 말한다.

IDQ는 이러한 5개의 문제들을 그대로 떠안고 있었으며 action space의 dimension이 커짐에 따라 효율적인 학습을 하지 못하는 것을 확인할 수 있었다. 그에 반해 BDQ는 shared representation module을 도입하여 각 agent(branch)들이 공통된 network에서 도출된 latent representation을 기반으로 action을 선택하게끔하여 위의 문제들을 상당부분 해결했으며, high-dimension action space에서도 안정적인 학습을 하는 모습을 보였다.