• 대한전기학회
Mobile QR Code QR CODE : The Transactions of the Korean Institute of Electrical Engineers
  • COPE
  • kcse
  • 한국과학기술단체총연합회
  • 한국학술지인용색인
  • Scopus
  • crossref
  • orcid

  1. (Dept. of Electrical Engineering and Information Technology, Seoul National University of Science and Technology, Korea.)



Reinforcement Learning, Sparse Reward Problem

1. 서 론

강화학습은 주어진 환경과 상호작용하는 에이전트가 특정 상황에서 어떤 행동을 취해야 하는지 학습시키는 기계학습의 한 분야이다. 강화학습에서 에이전트는 현재 상태에서 한 행동을 취할 때마다 환경으로부터 수치적인 보상 신호와 다음 상태 값을 받는다. 에이전트는 수많은 시행착오를 통해 보상을 얻을 수 있는 행동들을 경험하고 그것을 기억한다. 강화학습의 목표는 한정된 시간 안에서 에이전트가 받는 보상들의 합을 최대화할 수 있도록 학습시키는 것이다(1). 보상 신호는 에이전트의 목표에 따라 결정된다. 만약 에이전트의 목표가 정해진 일련의 과정을 거쳐야만 달성할 수 있는 것이라면, 목표를 달성하기 이전 과정에서 에이전트는 명확한 보상 신호를 받기 힘들고 많은 시행착오를 거쳐야 한다. 따라서 그런 환경에서 에이전트가 목표에 도달하는데 필요한 과정이 복잡해지면 에이전트가 보상을 얻는 경험이 희박해지며, 이는 에이전트의 학습을 어렵게 한다(2). 이러한 환경을 희소 보상 환경 (sparse reward environment)이라 한다(1).

희소 보상 환경은 강화학습의 학습 효율을 떨어뜨리는 대표적인 요인 중 하나이다. 강화학습 알고리즘의 대표적인 형태인 모델 프리 (model-free) 방식은 다양한 환경 및 다양한 문제에 적용될 수 있고 높은 성능을 낼 수 있지만, 학습 결과 성능이 높은 수준에 도달하는데 매우 많은 수의 데이터 샘플이 필요하다. 그러므로 희소 보상 환경에서는 보상을 얻은 데이터 샘플이 매우 희소하여 에이전트의 학습이 어렵다. 따라서 보상을 얻는 경우가 희귀할수록 에이전트는 더 많은 데이터 샘플을 얻어야 한다. 일반적으로 희소 보상 환경은 샘플 효율성 (sample efficiency)이 매우 낮은 환경이며, 이는 학습 성능을 크게 저해하는 요인이다.

최근에 강화학습 분야는 샘플 효율성을 증대시킬 수 있는 방향으로 연구가 진행되고 있다. 다양한 데이터 샘플을 빠르게 모으기 위해선 분산 학습 알고리즘을 활용할 수 있다. 하드웨어의 발전과 가용 컴퓨팅 자원의 증대에 따라 다수의 에이전트를 동시에 시뮬레이션 할 수 있으며, GPU를 활용하여 이를 가속화 할 수 있다(3). 그러나 데이터 샘플을 모으는 속도가 빨라질 뿐 보상을 얻는 샘플이 희소한 근본적인 문제는 해결되지 않는다. 또 다른 방법으로는 에이전트의 목표를 상태 정보로 특정할 수 있다면 강제적으로 에이전트가 목표에 도달한 샘플을 만들어 줄 수 있다(4). 이를 통해 희소 보상 환경에서도 샘플 효율성을 크게 올릴 수 있다. 하지만 이러한 방법은 에이전트의 목표가 상태 정보로 정의될 수 있는 문제에만 적용 가능하다. 모델 기반 (model-based) 방식 또한 샘플 효율성을 증대시킬 수 있는 것으로 알려져 있다. 근래의 이러한 방법은 대게 환경 모델을 학습할 인공 신경망을 따로 두어 이를 지도학습을 통해 환경 모델을 모사하도록 한다(5). 하지만 환경 모델이 복잡하고 확률적인 성질이 강할수록 환경 모델의 모사가 어려워진다.

에이전트의 환경을 최대한 그대로 이용하는 선에서 사용할 수 있는 방법은 탐험 (exploration) 알고리즘의 성능을 개선하는 것이다. 일반적으로 강화학습에서 탐험은 에이전트에게 임의의 행동을 강제로 하게 하여 다양한 상태를 경험해보도록 하는 것이다. 에이전트에게 지속적으로 탐험을 유도하면 이전에 만나지 못한 상태와 보상 신호를 찾을 수 있다. 이를 통해 희소 보상 환경에서도 보상을 얻는 샘플을 많이 얻을 수 있도록 유도할 수 있다. (2)에서는 에이전트에게 학습 중에도 강제로 무작위 행동을 하게 하여 탐험을 유도했지만 무작위 행동은 이미 겪어본 상태를 다시 경험하게 할 수도 있어 비효율적이다. 최근 탐험 알고리즘 중 하나로 내적 보상 (intrinsic reward)을 활용하여 에이전트에게 탐험을 유도하는 Random Network Distillation (RND)알고리즘이 제안되었다(6). 본 논문에선 이와 유사한 내적 보상을 활용하여 탐험 성능을 올리도록 한다. RND의 내적 보상 알고리즘은 에이전트가 경험하지 못한 상태를 만나면 추가 보상을 주어 효율적인 탐험을 유도한다.

본 논문에서는 대표적인 희소 보상 환경 중 하나인 테트리스 게임을 학습 환경으로 활용한다. 학습 알고리즘은 대표적인 모델 프리 on-policy 알고리즘 중 하나인 Proximal Policy Optimization (PPO)(7) 을 기반으로 구현하고, RND의 보상 알고리즘을 같이 사용하여 희소 보상 환경에서 보상을 받는 샘플을 더 많이 얻을 수 있도록 한다. 이전 논문 (15)에서는 보상을 얻는 샘플을 추가적으로 생성하여 희소 보상 문제를 해결하도록 하였지만, 본 논문에서는 내적 보상으로 탐험 성능을 높여 추가적인 샘플을 생성하지 않고 희소 보상 문제를 해결하고자 한다. 또한 데이터 샘플을 빠르게 모으기 위해 비동기 멀티 쓰레딩으로 다수의 환경에서 동시에 데이터를 수집한다(9). 결론 부분에선 내적 보상을 사용하지 않은 PPO, 잘 알려진 actor-critic 기반 알고리즘 (9)(15), 가치 기반 알고리즘(14), 본 논문에서 제안한 PPO+RND 방법들의 성능을 비교하여 테트리스 환경에서 희소 보상 문제의 개선을 검증한다.

2. 희소 보상 환경의 강화학습

강화학습은 마르코프 결정 과정 (MDP, Markov Decision Process)으로 정의된 환경 안에서 한정된 시간 동안에 보상 값의 합을 최대화하도록 에이전트의 행동을 결정하는 알고리즘이다. 즉, 에이전트는 타임 스텝 $t$에서 현재 상태 $s_{t}$를 입력으로 받아 행동 $a_{t}$를 출력한다. 환경 MDP 모델은 $s_{t},\:a_{t}$를 통해 다음 상태 $s_{t+1}$과 보상 $r_{t+1}$을 내놓는다. 이 과정은 마지막 타임 스텝 $t_{end}$까지 반복되며, 이러한 과정의 반복 하나를 한 에피소드 (episode)라 한다. 다음 상태 $s_{t+1}$은 MDP의 상태 전이 확률 모델을 통해 결정된다. 현재 상태가 $s_{t}=s$이고 행동 $a_{t}=a$를 수행했을 때 다음 상태 $s_{t+1}=s'$일 확률을 $T_{s,\:a}^{s'}=P[s_{t+1}=s'|s_{t}=s,\:a_{t}=a]$라 정의한다. 보상 $r_{t+1}$는 미리 정의된 보상함수 $r(s_{t},\:a_{t})$에 의해 결정된다. 보상함수는 환경의 일부이며 에이전트가 보상함수 자체를 알 수 없다. 에이전트가 내놓는 행동은 에이전트가 학습한 정책 $\pi(a_{t}|s_{t})$에 의해 결정되며 $\pi(a_{t}|s_{t})$는 상태 $s_{t}$가 주어졌을 때 행동 $a_{t}$가 결정될 확률이다. 에이전트와 MDP 환경의 상호작용을 도식화하면 그림 1과 같다.

그림. 1. MDP 환경과 에이전트의 상호작용 구조

Fig. 1. The structure of the interaction between the agent and MDP environment.

../../Resources/kiee/KIEE.2021.70.3.506/fig1.png

최적 정책 $\pi^{*}$는 시간 $t_{end}$까지 기대 보상 합을 최대화하는 정책이며 식(1)과 같이 정의된다(13).

(1)
$\pi^{*}=\arg\max_{\pi}\sum_{t=0}^{t_{end}}E_{s_{t},\: a_{t}}[\gamma^{t-1}(r(s_{t},\: a_{t}))]$

여기서 $\gamma\in[0,\:1]$는 감가율을 의미하며 $E[\bullet]$는 한정된 개수의 샘플들의 평균을 의미한다. 정책 $\pi(a_{t}|s_{t})$를 인공 신경망으로 구성하여 최적 정책을 만드는 신경망의 파라미터 $\phi$를 찾는 방법을 정책 경사 (policy gradient)라 하며, 정책 경사를 이용하는 강화학습을 정책 기반 강화학습이라 한다. 정책의 최적 파라미터 $\phi^{*}$를 찾는 최적화 문제의 목적함수 $J^{PG}$는 식(2)와 같이 정의된다(13).

(2)
$J^{PG}(\phi)=E_{s_{t},\:a_{t}}[\log\pi_{\phi}(a_{t}|s_{t})A_{t}]$

식(2)에서 $A_{t}$는 타임스텝 $t$에서 이점 함수 (advantage function)이며 $A_{t}=Q(s_{t},\:a_{t})-V(s_{t})$로 정의된다. $Q(s_{t},\:a_{t})$와 $V(s_{t})$는 각각 행동 가치 함수(action-value function)와 상태 가치 함수 (state-value function)를 의미한다(1), (13). 상태 가치 함수는 상태 $s_{t}= s$가 주어졌을 때 기대 보상 합으로 $V(s)=E_{\pi}[\sum_{t}^{t_{end}}\gamma^{t-1} · r(s_{t},\:a_{t})|s_{t}=s]$이고, 행동 가치 함수는 상태 $s_{t}=s$와 행동 $a_{t}=a$가 주어졌을 때 기대 보상 합으로 $Q(s_{t},\:a_{t})=r(s_{t},\:a_{t})+ E_{s_{t+1}}[V(s_{t+1})]$이다. 이점 함수 $A_{t}$는 현재 정책으로부터 기대되는 보상 합의 척도이다. 정책의 최적 파라미터 $\phi^{*}$는 식(2)를 최대화하는 값이며, 그 값은 경사상승법 (gradient ascent)을 통해 얻어진다. 이를 통해 에이전트의 정책 $\pi_{\phi}(a_{t}|s_{t})$ 는 기대 보상 합을 최대로 하는 정책 $\pi^{*}$가 되도록 학습된다. 다음 장에서는 위와 같은 정책 기반 방법의 학습 성능을 높일 수 있는 PPO를 설명하고, 이어서 희소 보상 환경에 대응할 수 있는 RND (Random Network Distillation) 알고리즘에 대해 설명한다.

2.1 Proximal Policy Optimization (PPO)

정책 기반의 강화학습 방법은 학습 성능을 높이면서 일반화 성능을 향상시킬 수 있는 방향으로 발전해왔다. 그 중 TRPO (Trust Region Policy Optimization)는 정책의 파라미터가 학습 중 크게 변하는 것을 방지하기 위하여 trust region이라 불리는 제약조건 (constraint)을 도입한 알고리즘이다(8). TRPO는 일반화 성능이 우수한 것으로 알려져 있지만, 구현이 복잡하고 계산이 다소 느리다는 단점이 있다. PPO (Proximal Policy Optimization)는 그 단점을 극복하면서 더 높은 일반화 성능을 얻을 수 있다고 알려져 있는 강화학습 알고리즘이다 (7). PPO는 TRPO의 trust region 제약조건을 클리핑 (clipping) 방법으로 대체하였다. PPO는 목적함수의 크기를 일정 상수 범위 내로 들어오도록 강제로 조절한다. 이는 TRPO보다 훨씬 간단한 방법이지만 더 좋은 일반화 성능을 나타내었다. PPO의 목적함수는 식(3)과 같이 나타나며 이를 최대화하도록 파라미터 $\phi$를 학습시킨다.

(3)
$J^{CLIP}(\phi)= E_{s_{t},\:a_{t}}[\min(\rho_{t}(\phi)A_{t},\:clip(\rho_{t}(\phi),\:1-\epsilon ,\:1+\epsilon)A_{t})] $

식(3)에서 $\rho_{t}(\phi)$는 TRPO에서 활용된 보존적 정책 이터레이션 (conservative policy iteration) 알고리즘의 정책 보존 비율이며, $\rho_{t}(\phi)=\dfrac{\pi_{\phi}(a_{t}|s_{t})}{\pi_{\phi_{old}}(a_{t}|s_{t})}$로 정의된다. 이는 정책 $\pi_{\phi}(a_{t}|s_{t})$가 학습될 때, 학습되기 이전 정책 $\pi_{\phi_{old}}(a_{t}|s_{t})$보다 성능이 악화되지 않는 것을 보장한다. 식(3)에서 $clip$은 식(4)와 같이 정의된다.

(4)
$clip(\rho_{t}(\phi),\:1-\epsilon ,\:1+\epsilon)=\begin{cases} 1+\epsilon ,\: & {if}\rho_{t}(\phi)>1+\epsilon \\ 1-\epsilon ,\: & {if}\rho_{t}(\phi)<1-\epsilon \\ \rho_{t}(\phi),\: & otherwise \end{cases}$

식(4)의 $\epsilon$은 $0<\epsilon <1$인 상수이며 이 논문에서는 $\epsilon =0.2$로 설정한다. 위 식(4)에서 $\rho_{t}(\phi)>1+\epsilon$인 경우는 일반적으로 기대 보상 합 $A_{t}$가 $A_{t}>0$인 경우이며, 학습된 최근 정책 $\pi_{\phi}(a_{t}|s_{t})$는 이전 정책 $\pi_{\phi_{old}}(a_{t}|s_{t})$보다 높은 값을 가질 것이다. 따라서 $\rho_{t}(\phi)$는 1보다 큰 값을 가진다. 이때 $clip$은 목적함수 (3)이 과도하게 커지는 것을 방지하기 위해 $\rho_{t}(\theta)\le 1+\epsilon$ 는 것을 유지하도록 정책 보존 비율을 규제한다. 반대로, $\rho_{t}(\theta)<1-\epsilon$인 식(4)의 두 번째 경우는 일반적으로 $A_{t}<0$ 인 경우이다. 이때 학습된 정책 $\pi_{\phi}(a_{t}|s_{t})$는 이전 정책 $\pi_{\phi_{old}}(a_{t}|s_{t})$보다 낮은 값을 가진다. 따라서 $\rho_{t}(\theta)$는 1보다 작은 값을 가지는데, 이때 목적함수 (3)이 너무 낮게 책정되는 것을 방지하기 위해 $\rho_{t}(\theta)\ge 1-\epsilon$를 보장한다. 결과적으로 좋은 정책 (높은 기대 보상 합을 얻을 수 있는 정책)에 대해선 과대평가를 방지하고, 좋지 않은 정책에 대해선 빠르게 탈피하도록 한다. 식(3)에서 이점 함수(advantage function) $A_{t}$는 식(5)와 같이 정의된다.

(5)
$A_{t}=-V_{\psi}(s_{t})+r_{t}+\gamma r_{t+1}+\cdots +\gamma^{T-t+1}r_{T-1}+\gamma^{T-t}V_{\psi}(s_{T})$

식(5)의 $V_{\psi}(s_{t})$는 기대 보상 합의 예측을 위해 근사된 상태 가치 함수 (approximated state-value function)로 (9)의 액터-크리틱(actor-critic) 구조에서와 같이 신경망을 통해 근사한 상태 가치 함수이다. 파라미터 $\psi$는 식(6)이 최소화되도록 학습된다.

(6)
$J^{V}(\psi)=E_{s_{t}}[\dfrac{1}{2}(r_{t}+\gamma V_{\psi}(s_{t+1})-V_{\psi}(s_{t}))^{2}]$

PPO 알고리즘은 on-policy 구조로서 현재 시간 $t$부터 $t_{end}$ 까지 데이터 샘플을 얻은 후에 학습을 진행할 수 있다. 이러한 형태의 알고리즘은 (9) 와 같이 비동기적 병렬 학습 환경으로 학습 속도를 높일 수 있다. 따라서 본 논문에선 여러 개의 환경에서 동시에 데이터를 샘플링하여 학습 속도를 높인다.

2.2 Random Network Distillation (RND)

희소 보상 환경에 대응하기 위해 외적 보상(extrinsic reward)과 내적 보상(intrinsic reward)을 동시에 사용하는 방법이 제안되었다(6). 식(1)에서 보상 $r(s_{t},\:a_{t})$는 일반적으로 외적 보상을 의미한다. 외적 보상은 에이전트가 목표에 도달했을 때 양수 값의 보상신호를, 목표 도달에 실패했을 때 음수 값의 보상신호를 에이전트에게 전달한다. 따라서 이 보상 값은 직접적으로 에이전트의 목표와 연관된다. 반면 내적 보상은 에이전트의 성능과 직접적으로 연관되지 않는다. 내적 보상은 에이전트 스스로의 동기에 의해 부여되는 보상 값이다. 가령 에이전트 스스로 더 탐험을 하고 싶다거나 특정 행동을 목표와 상관없이 중점적으로 하고 싶다와 같은 동기가 내적 보상이 될 수 있다. 희소 보상 환경에서 에이전트는 더 많은 탐험(다양한 행동과 상태)이 요구된다. RND 알고리즘에서는 내적 보상이 에이전트에게 탐험에 대한 동기 부여를 증대시키도록 한다. RND에서는 동일한 구조의 두 개의 신경망이 필요하다. 두 신경망은 각각 파라미터 $\theta$와 $\bar{\theta}$로 이루어진 $f_{\theta}$와 $f_{\bar{\theta}}$이며, 학습 초기에 두 파라미터 $\theta$와 $\bar{\theta}$는 서로 다른 무작위의 값으로 초기화된다. 이 두 신경망은 상태 정보 $s_{t}$를 입력으로 하여 동일한 길이($k$)의 벡터 $f_{\theta}(s_{t})$와 $f_{\bar{\theta}}(s_{t})$를 출력할 수 있다. 즉, $f_{\bar{\theta}}(s_{t})\ne f_{\theta}(s_{t})$이며, $f_{\bar{\theta}}(s_{t}),\:f_{\theta}(s_{t})\in R^{k}$ 이다. 파라미터 $\theta$는 식(7)의 평균제곱오차 형태의 손실함수를 최소화하도록 학습된다.

(7)
$J^{RND}(\theta)=E_{s_{t}}[\dfrac{1}{2}(f_{\theta}(s_{t})-f_{\bar{\theta}}(s_{t}))^{2}]$

파라미터 $\bar{\theta}$은 학습 초기에 무작위로 얻은 특정 값으로 고정되어 있다. (6)에 소개된 RND 기법에서는 파라미터 $\theta$로 이루어진 신경망을 예측 신경망 (prediction network), $\bar{\theta}$로 이루어진 신경망을 무작위 신경망(random network)으로 명명한다. 예측 신경망은 무작위 신경망의 출력을 예측할 수 있도록 학습한다. 즉, 예측 신경망은 입력 $s_{t}$에 대해 무작위 신경망과 동기화할 수 있도록 학습된다. 이 학습은 식(3)식(6)의 최적화가 진행되는 것과 동시에 수행한다. 상태 정보 $s_{t}$가 에이전트가 이미 여러 번 경험한 상태이면 식(7)의 오차는 낮게 측정될 것이다. 반면 $s_{t}$가 이전에 겪어보지 못한 상태이면 오차 값은 크게 책정될 수 있다. 즉 식(7)의 오차는 상태 정보 $s_{t}$가 에이전트에게 얼마나 희귀한 상태인가를 평가해주는 값이다. 이를 이용하여 에이전트가 새로 얻은 다음 상태 $s_{t+1}$에 대한 내적 보상 (intrinsic reward) $r_{t+1}^{i}$ 를 식(8)과 같이 정의할 수 있다.

(8)
$r_{t+1}^{i}=\dfrac{1}{2}(f_{\theta}(s_{t+1})-f_{\bar{\theta}}(s_{t+1}))^{2}$

내적 보상 $r_{t+1}^{i}$와 함께 에이전트가 현재 시간 $t$에 얻는 보상 $r_{t+1}$를 식(9)와 같이 정의한다.

(9)
$r_{t+1}=r_{t+1}^{e}+\alpha r_{t+1}^{i}$

식(9)에서 $\alpha$는 상수이며 본 논문에선 $10$으로 고정하였다. 식(9)에서 $r_{t+1}^{e}$는 외적 보상 (extrinsic reward)으로 에이전트의 성능과 직접적으로 연관된 보상 값이다. 따라서 에이전트는 내적 보상과 외적 보상이 합쳐진 보상 값 (9)를 최대화하도록 학습한다. 즉, 에이전트는 목표에 도달하는 것(외적 보상)과 동시에 많은 상태를 경험하여 탐험 성능을 높이는 것(내적 보상)을 달성하도록 학습되어진다. 내적 보상의 도출 구조를 나타내면 그림 2와 같다.

그림. 2. 내적 보상과 RND의 구조

Fig. 2. The structure of the intrinsic reward and RND

../../Resources/kiee/KIEE.2021.70.3.506/fig2.png

3. 학습 환경 및 학습 과정

본 논문에서는 PPO와 RND 알고리즘을 결합하여 테트리스 환경의 희소 보상 문제를 해결한다. 테트리스는 대표적인 희소 보상 환경으로 알려져 있으며, 기계학습으로 이를 해결하려는 연구가 계속 진행되고 있다 (10,11). 테트리스는 7개의 테트로미노(tetromino) 블록들을 이용하여 가로줄을 만들면 해당 블록들이 제거되어 많은 줄을 제거할수록 높은 점수를 얻을 수 있는 게임이다. 본 논문에선 크기의 테트리스 환경을 고려한다. 테트리스 환경에서 강화학습 에이전트의 목표는 높은 점수를 얻는 것이고, 줄 제거 후 받는 점수가 곧 보상이 될 수 있다. 보상을 얻기 위해 가로줄을 제거하려면 블록들을 빈칸 없이 화면에 채워 넣어야 한다. 그림 3은 테트리스에서 보상을 얻는 경우와 얻지 못하는 경우를 비교하였다. 그림 3표 1을 함께 보면 보상을 얻는 경우가 보상을 얻지 못하는 경우에 비해 매우 희소하며, 에이전트가 보상을 얻는 경우를 경험하려면 특정한 일련 과정을 거쳐야 하는 것을 확인할 수 있다.

그림. 3. 테트리스 환경에서 보상을 얻는 방법

Fig. 3. How to get the reward in Tetris environment

../../Resources/kiee/KIEE.2021.70.3.506/fig3.png

테트리스 환경에서 에이전트의 외적 보상(extrinsic reward)은 줄 제거에 따른 점수와 비례하게 정의할 수 있다. 식(9)의 외적 보상 $r_{t}^{e}$를 아래 식(10)과 같이 정의한다.

(10)
$r_{t}^{e}\in\{-0.5,\:0,\:1,\:3,\:6,\:10\}$

식(10)의 정수 값들은 각각 0줄에서 4줄까지의 보상 값을 의미한다. 음수 보상 값은 블록이 게임 화면 맨 위층에 닿아 에피소드가 끝났을 때의 패널티 보상이다. 이 보상 함수는 학습 중 대부분의 경우에서 0을 출력하기에 테트리스 게임은 희소 보상을 가지는 MDP이다. 반대로 보상 값이 대부분의 경우에 0이 아닌 값을 가지면 밀집 보상 MDP(dense reward)로 해석할 수 있다. 따라서 식(9)에 정의된 보상 함수는 내적보상의 정의에 따라 희소 보상과 밀집 보상이 합쳐진 형태로 볼 수 있다. 다만 식(9)의 내적 보상은 테트리스의 목표(줄 제거)와 직접적인 연관은 없다.

테트리스 환경에서 가능한 행동은 현재 주어진 블록을 좌, 우, 회전, 소프트-드롭 (soft-drop), 하드-드롭(hard-drop)으로 움직이는 것으로 총 5가지이다. 여기서 소프트-드롭과 하드-드롭은 각각 블록을 한 칸 내리는 것과 바닥까지 한 번에 내리는 것을 의미한다. 에이전트는 이 행동들을 조합하여 쌓여진 블록에서 줄을 제거할 수 있는 위치로 현재 조종하는 블록을 움직여야 한다. 학습이 진행되기 이전에 에이전트의 정책은 무작위로 초기화된 정책 $\pi_{\phi^{\in}}(a_{t}|s_{t})$를 따른다. 따라서 이 정책은 무작위적인 행동을 내놓게 되고, 무작위 행동들을 통해 식(10)의 보상을 얻는 경우는 매우 희소하다. 이는 표 1에서 확인할 수 있다. 복잡한 행동들의 조합에 대한 문제를 완화하기 위해 (12)에서는 일련의 행동 조합을 정의하여 사용하였다. 이를 통해 에이전트의 목표를 유지하면서 불필요한 행동들을 억제할 수 있다. 본 논문에서는 이와 유사하게 5개 행동들의 조합을 그룹으로 만들어 행동을 재정의하였다. 블록을 아래로 내리는 것은 하드-드롭으로 통일하고, 게임 화면 가로 8칸 안에서의 횡 방향 이동 7가지와 블록 회전 최대 4회를 조합하여 28개의 묶음 행동 (group-action)으로 에이전트의 행동을 정의하였다. 따라서 $a_{t}$는 28가지의 행동으로 이루어지며, $a_{t}\in\{0,\:1,\:2,\:\ldots ,\:28\}$으로 정의된다. 이를 통해 보상의 희소성을 표 1과 같이 완화할 수 있다.

표 1. 보상의 희소성 비교 (무작위 행동)

Table 1. Comparison of reward sparsity

5 actions

28 group actions

Total step

1,000,000

1,000,000

Total episode

16368

50902

Total clear line

8

986

Step / Episode

61

20

Line / Episode

0.00048

0.01937

테트리스 환경에서 현재 상태 정보는 $8\times 16$의 게임 화면을 그대로 이용한다. 테트리스에 적용된 이전 기계 학습 결과들에서는 특징 정보를 직접 정의하여 정책 함수의 입력으로 사용하기도 했다(11). 본 논문에선 종단 간 학습(end-to-end learning) 알고리즘을 목표로 하여, 게임 화면의 특징을 CNN (Convolution Neural Network)이 학습을 통해 찾아내도록 한다. 현재 상태 $s_{t}$는 그림 4와 같이 정의된다. $8\times 16$ 게임 화면에서 블록이 있는 곳을 1, 없는 곳을 0으로 한 binary image의 형태로 저장한다. 여기서 특징 추출이 용이하도록 현재 시점에 쌓인 블록과 조종할 수 있는 블록의 이미지를 분리한다. 따라서 $s_{t}$는 $8\times 16\times 2$의 크기를 가진다.

그림. 4. 테트리스 환경에서 상태 정보

Fig. 4. The state information of Tetris environment

../../Resources/kiee/KIEE.2021.70.3.506/fig4.png

현재 상태 이미지를 입력하는 신경망은 그림 5와 같이 구성한다. 파라미터 $\phi ,\:\psi ,\:\theta ,\:\bar{\theta}$ 각각이 이루는 신경망의 구조는 모두 그림 5의 구조로 동일하게 구성하였다. 즉, 그림 6과 같이 $\phi ,\:\psi ,\:\theta ,\:\bar{\theta}$ 파라미터로 이루어진 각각의 신경망은 서로 동일한 구조를 가지고 상태 정보를 입력으로 받으며, 각자의 역할은 서로 다르다. 신경망은 CNN을 기반으로 하고 입력 이미지의 크기가 작기 때문에 각 층은 padding을 한다. 일정 부분마다 max-pooling을 하여 상위 특징을 추출하는데 용이하도록 하였다. 또한 max-pooling을 할 때마다 skip-connection 구조를 추가하여 이전 정보를 유지할 수 있도록 하였다. 상태 정보는 두 부분으로 나뉘어 신경망을 통과한다. 그림 5의 윗부분에는 $5\times 5,\:3\times 3,\:1\times 1$과 같은 일반적인 크기의 CNN 커널을 통과하여 다양한 수용 영역 (receptive field)을 인지하도록 설계하였고, 아랫부분에 $1\times 8,\:16\times 1,\:1\times 6,\:14\times 1,\:\cdots$와 같은 커널들은 상태정보의 가로 또는 세로 픽셀의 정보를 추론하도록 설계하였다. 이는 (11)에서 언급된 수작업 특징 정보(hand-crafted feature)를 신경망으로 대체한 것이다. 이를 통해 쌓인 블록들의 높이, 블록과 블록 사이의 구멍과 같은 세부적인 정보를 신경망이 더 쉽게 파악할 수 있도록 하였다. 신경망의 출력은 완전 연결(fully-connected)층을 거친 후 그림 6과 같이 각 신경망의 역할에 맞게 정책 $\pi_{\phi}(a_{t}|s_{t})$, 가치 함수 $V_{\psi}(s_{t})$ 또는 RND 예측 $f_{\theta}(s_{t})$를 출력한다. 여기서 정책과 가치 함수에 해당하는 신경망은 (9)와 같은 actor-critic 구조에 해당하며 각각 actor와 critic에 대응한다. 각 신경망의 상태정보 입력을 통한 추론 과정은 그림 7과 같다. 그림 7은 정책 신경망과 RND 신경망의 입출력 과정을 그림 1의 MDP에 대입하여 MDP와 신경망들의 상호작용을 표현한 그림이다. 학습 중에는 이 과정을 계속해서 반복하며, 이로부터 얻은 데이터 $\left\{s_{t},\:a_{t},\:s_{t+1},\:r_{t+1}\right\}$들을 replay memory에 저장한다.

그림. 5. 신경망 구조

Fig. 5. The structure of the designed neural network

../../Resources/kiee/KIEE.2021.70.3.506/fig5.png

그림. 6. 각 신경망의 입출력

Fig. 6. Input and output of each neural network

../../Resources/kiee/KIEE.2021.70.3.506/fig6.png

그림. 7. 각 신경망과 MDP의 상호작용

Fig. 7. Interaction of each neural network and MDP

../../Resources/kiee/KIEE.2021.70.3.506/fig7.png

비동기 멀티 쓰레딩 환경은 (9)의 방법을 사용한다. 총 $n$개의 환경을 생성하여 각 환경의 타임 스텝은 $t_{1},\:t_{2},\:t_{3},\:\ldots ,\:t_{n}=0$으로 초기화한다. 각 환경에서 게임 에이전트는 현재 상태 $s_{t_{n}}$을 입력으로 하여 정책 $\pi_{\phi}(a_{t_{n}}|s_{t_{n}})$으로 행동 $a_{t_{n}}$을 수행하고, 샘플 $\left\{s_{t_{n}},\:a_{t_{n}},\:s_{t_{n}+1},\:r_{t_{n}+1}\right\}$을 생성하여 로컬 버퍼 $L$에 저장한다. 샘플은 최대 $M$개까지 수집하고, 샘플 개수가 $M$개가 되면 정책 $\pi_{\phi}(\bullet |\bullet)$, 가치함수 $V_{\psi}(\bullet)$, RND 예측 $f_{\theta}(\bullet)$을 수집한 $M$개 샘플을 이용하여 학습시킨다. 각각의 학습은 $\lambda$의 학습률 (learning rate)을 가지고 최적화를 진행한다.

전체 학습 과정은 표 2에 요약하였으며, 학습 과정을 종합한 구조도는 그림 8과 같다. 또한 학습에 사용된 하이퍼 파라미터들은 표 3과 같이 설정하였다.

표 2. 학습 알고리즘 의사 코드

Table 2. Pseudo-code of the proposed method

../../Resources/kiee/KIEE.2021.70.3.506/table2.png

표 3. 학습에 사용된 하이퍼 파라미터

Table 3. Hyper parameters used for the training

Notation

Value

Batch size

$M$

256

Discount factor

$\gamma$

0.99

Number of agents

$n$

8

Learning rate

$\lambda$

0.000025

RND constant

$\alpha$

10

그림. 8. 전체 학습 과정 구조 (PPO + RND)

Fig. 8. Structure of the entire learning process

../../Resources/kiee/KIEE.2021.70.3.506/fig8.png

4. 성능 평가

그림 9는 400,000 에피소드 동안의 학습 중 에이전트의 줄 제거 (Line clear) 성능 양상을 확인한 그래프이다. RND를 사용하지 않은 에이전트(그림 9의 파랑)는 RND를 사용한 에이전트(그림 9의 주황)보다 학습 초반에 더 빠르게 성능이 향상되었다. 그러나 RND를 사용한 에이전트는 학습이 진행되면서 RND를 사용하지 않은 에이전트 보다 더 높은 성능을 얻을 수 있었다. RND는 에이전트에게 더 많은 상태를 탐험하게 한다. 이를 통해 보상을 받는 샘플을 학습 중에 더 다양하게 얻을 수 있고 더 나은 정책을 학습할 수 있다. RND를 사용하지 않은 에이전트는 RND를 사용한 에이전트에 비해 상대적으로 보상을 받는 샘플을 적게 경험했기에 더 일찍 성능이 수렴했다.

그림. 9. 학습 양상 비교 그래프 (400,000 에피소드)

Fig. 9. Training performance (400,000 episodes)

../../Resources/kiee/KIEE.2021.70.3.506/fig9.png

그림 10은 학습 중 RND의 손실 함숫값을 보이는 그래프다. RND의 손실 값은 식(7)에서 도출된 값을 사용한다. 학습 초기엔 손실 값이 계속 감소하지만, 보상을 얻는 정책을 찾으면서 손실 값이 다시 상승하는 양상을 볼 수 있다. RND의 손실 값은 이전에 경험하지 못한 상태를 입력으로 받으면 그 값이 높아진다. 그림 9그림 10을 대조하여 보면 PPO+RND의 성능이 높아질 때 비슷한 시점에 RND의 손실값이 상승하는 것을 확인할 수 있다. 또한 이 손실값은 계속해서 높아지지 않고 특정 시점(200,000 에피소드 부근)에서 다시 감소하는 추세를 보인다. 따라서 에이전트가 높은 보상을 얻는 정책을 학습할수록 새로운 상태를 경험하는 것으로 볼 수 있다. 새로운 상태를 경험하면 RND 알고리즘은 게임 점수와 무관한 긍정적 보상을 에이전트에게 부여한다. 이는 에이전트에게 새로운 상태를 경험하는 것이 좋은 정책 학습 방향임을 알려주고 더 높은 성능에 도달할 수 있도록 한다.

그림. 10. RND 손실값 그래프 (400,000 에피소드)

Fig. 10. RND loss graph (400,000 episodes)

../../Resources/kiee/KIEE.2021.70.3.506/fig10.png

그림 11표 4는 PPO 이외의 다른 알고리즘과 학습 성능 및 최종 성능을 비교한 자료이다. 표 4는 학습 성능이 수렴하는 양상을 보이면 학습을 중지하고, 1,000번의 게임을 통해 최대 점수와 평균 점수를 나타낸 것이다. 각 알고리즘들은 환경, 하이퍼 파라미터, 에피소드 수, 하드웨어를 동일하게 적용하였다. 그림 11표 4의 DQN+PER에서는 가치 기반 알고리즘인 Deep Q-Network (DQN)와 샘플 효율성을 향상시키는 Prioritized Experience Replay(PER) 알고리즘을 활용하여 테트리스 환경을 해결하고자 하였다(14). (14)에서도 묶음 행동을 사용하여 성능을 향상시켰지만 정책 기반 알고리즘인 PPO에 비해 평균적인 성능이 좋지 않다. 또한 PPO 알고리즘은 다른 actor-critic 기반 알고리즘 보다 높은 성능을 나타내었다. 기본적인 actor- critic 구조인 A3C(9)와 soft actor-critic과 hindsight experience replay를 사용한 SAC+HER(15) 보다 높은 성능을 나타내었다. PPO는 일반적으로 기본적인 actor-critic 알고리즘 보다 더 높은 성능을 낼 수 있다고 알려져 있으며(7), soft actor-critic은 연속 행동 작업을 해결하는데 좋은 알고리즘으로 알려져 있어(16) 이산 행동 문제인 테트리스 게임과 같은 환경에서 높은 성능을 기대하지 못했다. 그림 9그림 11에서 볼 수 있듯 단순 PPO보단 PPO+RND가 더 높은 성능을 나타내는 것을 확인할 수 있다. 이는 RND 알고리즘의 탐험 유도 보상 함수가 좋은 정책을 찾는데 좋은 영향을 끼쳤다고 볼 수 있다.

표 4. 학습 후 줄 제거 성능 (1,000 에피소드)

Table 4. Performance result after training (1,000 episodes)

Average

Maximum

PPO

166.02

284

PPO+RND

366.16

1294

DQN+PER

87.44

713

A3C

28.26

139

SAC+HER

25.48

58

그림. 11. 알고리즘 별 학습 성능 비교 그래프

Fig. 11. Comparison graph of learning performance of each algorithm

../../Resources/kiee/KIEE.2021.70.3.506/fig11.png

5. 결 론

탐험 알고리즘은 강화학습 에이전트에게 특정 정책에 고착되지 않고 여러 상태를 경험하게 하여 희소 보상 문제를 해결할 수 있는 방법이다. RND와 같은 내적 보상을 통한 탐험의 유도는 강화학습 알고리즘 종류에 구애받지 않고 적용할 수 있으며, 에이전트가 더 높은 성능을 얻도록 학습에 도움을 준다. 테트리스와 같은 희소 보상 환경은 단순한 모델 프리 강화학습 방법보다는 탐험을 향상시키는 RND와 같은 보상 함수를 추가하는 방식으로 학습 성능을 크게 향상 시킬 수 있다.

테트리스는 심층 강화학습을 사용하지 않은 결과들이 더 좋은 성능을 내는 것으로 알려져 있다(11). 이전의 결과들은 게임의 특징 정보를 직접 추출하거나 직관적 (heuristic) 보상 함수들을 정의하여 성능향상을 도모하였다. 이는 인위적으로 에이전트에게 더 쉽게 상태와 보상을 기억하게 한다. 하지만 다양한 환경에 쉽게 적용할 수 있고 일반화 성능을 높이기 위하여 본 연구에서 제안한 내적 보상 함수와 같은 방법의 연구가 필요하다. 추후 연구에서는 모델 기반 방법을 이용하여 샘플 효율성을 높이는 알고리즘을 고려한다. 또한 PPO와 같은 on-policy 알고리즘이 아닌 off-policy 알고리즘을 이용하여 더 효율적인 학습 알고리즘을 구현하고자 한다.

Acknowledgements

This work was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (NRF-2019R1F1A1061197, NRF- 2019R1A6A1A03032119).

References

1 
Richard S. Sutton, Andrew G. Barto, 2018, Reinforcement learning: An introduction, MIT pressGoogle Search
2 
Volodymyr Mnih, 2015, Human-level control through deep reinforcement learning, Nature, Vol. 518.7540, pp. 529-533DOI
3 
Lasse Espeholt, 2018, IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures, International Conference on Machine LearningGoogle Search
4 
Marcin Andrychowicz, 2017, Hindsight experience replay, Advances in Neural Information Processing SystemsGoogle Search
5 
Łukasz Kaiser, 2019, Model based reinforcement learning for atari, International Conference on Learning Represen- tationsGoogle Search
6 
Yuri Burda, 2018, Exploration by random network distil- lation, International Conference on Learning Represen- tationsGoogle Search
7 
John Schulman, al et, 2017, Proximal policy optimization algori- thms, arXiv preprintGoogle Search
8 
John Schulman, al et, 2015, Trust region policy optimization, International Conference on Machine LearningGoogle Search
9 
Volodymyr Mnih, 2016, Asynchronous methods for deep reinforcement learning, International Conference on Machine LearningGoogle Search
10 
Erik D. Demaine, Hohenberger Susan, Liben- Nowell David, 2003, Tetris is hard, even to approximate, International Computing and Combinatorics Conference, Vol. springer, No. berlin, heidelbergGoogle Search
11 
Simón Algorta, Şimşek Özgür, 2017, The game of tetris in machine learning, International Conference on Machine LearningGoogle Search
12 
Oriol Vinyals, 2019, Grandmaster level in StarCraft II using multi-agent reinforcement learning, Nature, Vol. 575.7782, pp. 350-354DOI
13 
Richard S. Sutton, 2000, Policy gradient methods for reinforcement learning with function approximation, Advances in Neural Information Processing SystemsGoogle Search
14 
Dongki Han, Myeongseop Kim, Jaeyoun Kim, 2019, Deep Q-network based game agents, Journal of Korea Robotics Society, Vol. 14, No. 3, pp. 157-162DOI
15 
Myeongseop Kim, Jung-Su Kim, 2020, Reinforcement learning game agent for sparse reward environment, The 51th KIEE Summer ConferenceGoogle Search
16 
Tuomas Haarnoja, 2018, Soft actor-critic: Off-policy maxi- mum entropy deep reinforcement learning with a stochastic actor., International Conference on Machine Learning. PMLRGoogle Search

저자소개

MyeongSeop Kim
../../Resources/kiee/KIEE.2021.70.3.506/au1.png

He received the B.S. degree in electrical engineering from Seoul National University of Science and Technology, Seoul, South Korea, in 2019, where he is currently pursuing the M.S degree in electrical engineering.

His research interests include artificial intelligence and reinforcement learning.

Jung-Su Kim
../../Resources/kiee/KIEE.2021.70.3.506/au2.png

He received B.S,, M.S. and Ph.D. degrees in electrical engineering from Korea University, Seoul, South Korea, in 1998, 2000, and 2005, respectively.

He was a Visiting Scholar at Seoul National University in South Korea, the University of Stuttgart in Germany and the University of Leicester in the UK from March 2005 to February 2006, from March 2006 to December 2007, from January 2008 to January 2009 respectively.

He is currently a full pro- fessor in the Dept. of Electrical Engineering and Information Technology at Seoul National University of Science and Technology, Seoul, South Korea since 2009.

His research interests include model predictive control, distributed control, energy systems and deep learning.