강화 학습은 마르코프 결정 과정(MDP)으로 정의되는 환경 으로부터 기대 누적 보상을 최대화하는 최적 정책을 찾는 여 러 가지 방법 중 하나이다. 여기서 환경에 해당하는 마르코프 결정 과정은 {S,A,P,R,γ} 의 요소로 구성된다. S는 유한한 크기를 갖는 상태 집합, A는 유한한 크기를 갖는 행동 집합, P(s′|s,a) 는 상태 전이 확률로 현재 상태 s∈S에서 행동 a∈A를 취했을 때 다음 상태가 s′∈S이 되는 확률 분포를 의 미하며, R는 보상 함수, γ∈(0,1)은 할인 계수를 나타낸다. 또 한 강화 학습 에이전트의 역할을 하는 정책 π(a|s) 는 주어진 상태에 대한 행동의 확률 분포를 의미한다. 강화 학습 에이전 트는 이산 시간 t시점에서의 상태 s_t에서 정책 π에 따라 행동 a_t를 취하고 상태 전이 확률 및 보상 함수에 따라 다음 상태 s_t+1과 보상 r_t+1을 얻는다. 이때 강화 학습은 초기 상태로부 터 정책에 따라 연속적인 행동을 취했을 때의 기대 누적 보상 E[∑k=0∞γkrt+k+1] 을 최대화하는 정책을 찾는 것을 목적으로 하며 이때의 정책을 최적 정책 π^∗로 표현한다.

강화 학습은 정책 기반 알고리즘과 가치 기반 알고리즘으 로 분류 가능하며, Q-learning은 행동 가치 함수를 이용하여 최 적 정책을 찾는 가치 기반 알고리즘에 속한다. 행동 가치 함수 Q_π는 식 (1)과 같이 정의되며 상태 s에서 행동 a를 취했을 때 정책 π에 따른 기대 누적 보상을 의미한다.

이러한 Q_π를 실제 알아내는 것은 어려운 일이므로 여러 가 지 방법으로 추정하게 되는데 대표적으로 임의의 값을 가지는 함수 Q에 대해 식 (2)를 반복하면 학습비율 α에 대한 기본 조 건하에서 Q_π로 수렴함이 알려져 있다^[5,6]. Q-learning은 임의 의 값으로 초기화된 함수 Q에 대한 ∈-탐욕 정책을 통해 주어진 상태에 대한 행동을 취하고 환경으로부터 다음 상태와 보상을 얻고 식 (2)를 반복하는 과정으로 최적 정책 π^∗를 찾는다.

고전적인 방식의 Q-learning은 상태 집합의 크기가 커지면 차원의 저주가 발생하기 때문에 실제 문제에 적용하는 것에 제 약이 존재했다. 이에 DQN 알고리즘은 행동 가치 함수를 인공 신경망을 통해 함수 근사 및 학습하는 방법을 사용한다. Q-신경 망은 입력으로 상태가 인가되면 각 행동에 대한 행동 가치 함수 를 출력한다. 신경망은 식 (3)으로 표현되는 시간차 오차의 제곱 을 목적 함수로 정의하고 이에 대한 경사 하강법으로 학습한다.

이 때 ^[7]에서 제안한 double Q-learning 기반의 목적 함수로 확장 적용 가능하며 이는 식 (4)로 표현된다. 또한 DQN 알고 리즘은 학습의 안정성을 위해 경험 재생 메모리 및 타겟 신경 망을 사용한다^[1].

우선순위 경험 재생은 DQN 알고리즘의 성능 향상 기법 중 한 가지로서, 기존 DQN 알고리즘에서는 경험 재생 메모리에 저장되어 있는 데이터를 무작위로 선택하여 학습하는 반면에 PER의 경우 데이터에 대한 우선순위 가중치를 부여하여 이 가 중치를 반영한 확률로 데이터를 선택한다^[8]. i번째 데이터의 우선순위 가중치 p_i는 시간차 오차의 크기에 비례하며 식 (4) 로 정의된다. 이에 따라 i번째 데이터가 선택될 확률 P(i)는 식 (5)로 표현된다. 여기서 α는 우선순위 가중치를 얼마나 반 영할지를 결정하는 변수이다. 우선순위 가중치에 따른 데이터 선택은 전체 데이터 분포를 반영하지 못하고 편향이 발생하기 때문에 이를 완화하는 방법으로 중요도 표집 기법(importance sampling)을 적용한다. i번째 데이터의 중요도 표집 가중치는 식 (6)로 정의되어 목적함수에 곱해진다. N은 메모리에 저장 된 전체 데이터의 개수, β는 중요도 표집 기법을 얼마나 반영 할지를 결정하는 변수이다.

기존 연구에서는 테트리스 보드의 상태를 잘 반영하면서 경우의 수를 줄일 수 있는 특징을 사람의 직관에 따라 정의하 였다. 예를 들어 Bertsekas 특징의 경우 보드의 인접한 열 간의 쌓여있는 블록의 높이 차이, 가장 높게 쌓여있는 블록의 높이, 빈 공간의 개수로 정의된다. 이렇게 사람의 직관에 의존한 특 징은 다양하게 정의될 수 있고, 어떤 특징을 사용하느냐에 따 라 성능의 편차가 발생한다. 따라서 본 논문에서는 직관에 따 른 특징 정의를 사용하지 않고 테트리스의 보드 형태 그대로 를 상태로서 정의하고 이를 합성 곱 신경망(CNN, Convolution Neural Network)을 통해 특징 추출 과정 자체를 학습하도록 설 계하였다. 합성 곱 신경망의 입력이자 테트리스 보드 형태 자 체를 반영한 상태는 14×7 크기의 보드를 기준으로 같은 크기 의 14×7×1 행렬로 정의되며 각 행렬의 요소 값은 블록이 채 워져 있는 경우에 1, 비워져 있는 경우에 0 값을 갖는다.

테트리스 비디오 게임에서 정의되어 있는 기본 행동을 그 대로 학습에 사용한다면 강화 학습 에이전트의 학습 초기 무 작위 탐험 과정에서 왼쪽으로 한 칸 이동하고 다시 오른쪽으 로 한 칸 이동할 경우나 회전을 여러 번 하는 경우 등의 경험이 빈번하게 발생한다. 하지만 이런 경험은 줄 제거라는 목적을 고려했을 때 불필요한 탐험 과정이며 학습을 느리게 하는 원 인이 된다. 본 논문에서는 현재 블록이 쌓일 수 있는 위치 및 형 태의 가짓수에 따라 기본 행동을 조합하여 새로운 행동을 정 의하였다. 예를 들어 [Fig. 1]의 T 모양의 블록은 회전을 통해 위로 볼록, 아래로 볼록, 좌로 볼록, 우로 볼록 으로 4가지 형태 가 가능하다. 이때 각 형태에 대해 블록이 놓일 수 있는 위치는 14×7 크기의 보드를 기준으로 5가지, 5가지, 6가지, 6가지로 총 22가지 경우가 존재한다. 결국 해당 블록이 보드에 쌓일 수 있는 22가지 경우 그 자체가 새롭게 정의되는 행동이 된다. 이 를 일반화하면 7가지 모양의 각 블록의 회전에 의한 형태 변화 는 최대 4가지가 경우가 존재하며, 위치이동은 14×7 크기의 보드를 기준으로 최대 7가지가 경우가 존재한다. 따라서 새롭 게 정의되는 행동의 집합 크기는 28이 된다.

[Fig. 1] 

Tetromino : seven blocks used in Tetris games

기본적으로 테트리스에서 점수를 얻는 방법은 보드의 행을 빈틈없이 채워서 줄을 제거하는 것이다. 이때 한 번에 제거하 는 줄이 많을수록 추가점을 얻어 큰 점수를 얻는다. 따라서 보 상 역시 줄을 제거할 경우에 발생하며 보상의 크기는 줄 제거 수에 비례하도록 정의하였다. 하지만 학습 초기 무작위 행동 을 통해 블록을 빈 공간 없이 채워 줄을 제거하는 경우의 발생 빈도는 매우 적다. 따라서 줄 제거 보상만을 사용할 경우 보상 을 얻는 경험의 빈도가 매우 드물기 때문에 학습에 어려움을 겪게 된다. 그러므로 학습을 보조하기 위한 용도로 몇 가지 추 가 보상을 정의하였다. 줄 제거 보상 및 추가 보상을 모두 고려 한 이산 시간 t시점에서의 보상 r_t는 식 (8)로 표현된다.

여기서 r_dear는 줄 제거 보상이며 순서대로 한 번에 0, 1, 2, 3, 4 줄을 제거 했을 때의 보상 크기를 나타낸다. r_hole은 현재 블록을 쌓는 순간에 빈 공간의 생성 여부에 따른 보상을 의미한다. 빈 공 간이 발생할 경우 음의 보상, 그렇지 않을 경우 양의 보상을 받는 다. r_height는 쌓여 있는 블록의 높이가 보드의 절반을 넘는 경우 음 의 보상을 그렇지 않을 경우 양의 보상으로 정의된다. 마지막으로 r_combo의 경우 연속으로 줄을 제거했을 때 양의 보상을 제공한다.

[Fig. 2]는 본 논문에서 사용한 Q-신경망 구조를 나타낸다. 신경망은 테트리스 보드에서 특징 추출을 하는 합성 곱 신경 망과 추출된 특징을 바탕으로 행동 가치 함수를 학습하는 완 전 연결 신경망으로 이루어져 있다. 합성 곱 신경망의 경우 7×14×1 크기의 입력에 대해 크게 3번의 합성 곱 블록 세트 를 거치는 형태를 가진다. 첫 번째 블록 세트에서는 4×4 크기 의 필터 32개로 구성되며 최종적으로 3×3 크기로 보폭 2의 max pooling을 거친다. 두 번째 블록 세트에서도 비슷한 형태 가 반복된다. 또한 각 블록 세트를 거친 출력은 skip connection 구조로 완전 연결 신경망의 입력으로 연결된다. 추가적으로 테트리스는 행 또는 열의 모양이 중요한 정보를 담고 있을 것 이라는 배경 지식을 활용하여 입력 및 각 pooling에 대해 n_height ×1, 1×n_width 크기의 필터 64개를 갖는 합성 곱 신경 망을 두었다. 이후 완전 연결 신경망은 256개의 뉴런으로 구성 된다. 마지막으로 ^[9]에서 제안한 dueling Q-신경망 구조에 따 라 상태 가치 함수와 이점 함수(advantage function)를 근사하 는 완전 연결 신경망이 각각 256개의 뉴런을 구성하며 최종적 으로 28개의 행동 가치 함수를 출력한다.

[Fig. 2] 

Q-network architecture: the Q-network consists of a convolution layer responsible for the process of feature extraction from a given input and a fully connected layer responsible for the approximation of the action value function

[Fig. 3]은 강화 학습 기반 테트리스 인공지능 에이전트의 학습 프로세스를 블록 다이어그램으로 표현한 그림이다. 먼저 초기 학습 데이터를 수집하는 과정에서는 주어진 상태 s에 대 한 완전한 무작위 행동을 통해 행동 a를 취하고 이에 대한 보 상 r과 다음 상태 s′을 얻는다. 이 과정을 한 번 진행할 때마다 상태 s, 행동 a, 보상 r, 다음 상태 s′을 하나의 학습 데이터 세 트로서 메모리에 저장한다. 일정량의 학습 데이터가 메모리에 저장되면 본격적인 Q-신경망의 학습이 시작된다. Q-신경망 학습이 시작되면 매 순간 행동은 ∈-탐욕 정책으로 취해지며 4 번의 행동을 취할 때 마다 한 번의 Q-신경망 학습이 이루어진 다. Q-신경망 학습의 경우 먼저 식 (5)와 식 (6)로 정의되는 우 선순위 경험 재생 기법에 따라 메모리에서 32개의 데이터를 추출한다. 추출된 데이터로 식 (4)의 double Q-learning 기반 목 적 함수에 식 (7)의 중요도 표집 기법을 적용하여 이에 대한 경 사 하강법으로 Q-신경망의 가중치를 갱신한다. 타겟 신경망 은 Q-신경망의 학습이 1000번 이루어질 때마다 한 번 갱신된 다. 이러한 과정으로 총 48시간 동안 학습을 진행하였다.

[Fig. 3] 

Agent training process : the Tetris agent performs training according to the DQN algorithm, and the experiences collected from the environment are stored and extracted by the PER method

시뮬레이션 환경에서 학습된 신경망을 실제 환경에 적용하 기 위해 카메라에서 본 이미지와 이전에 학습한 이미지가 같 도록 해야 한다. 또한 영상인식에 있어서 카메라의 기울어짐 이나 영상의 휘어짐의 영향이 적도록 하고, 상대방의 게임화 면을 자신의 화면으로 인식하는 것 또한 막아야한다. 그러기 위해서 먼저 게임 화면에 붉은색 테두리를 넣었고 이를 중심 으로 인식하도록 하였다. [Fig. 6]의 좌측은 카메라 원본 이미 지이고 우측의 흑백 이미지가 최종적으로 사용될 데이터이다. 인공지능 로봇이 자신의 화면만 인식할 수 있도록 윤곽선 검 출(contour detection)을 통해 붉은색 사각형을 인식하고, 원근 변환(perspective transform)을 통해 원본 게임 사이즈에 맞게 되돌린다. 이후 각 영역에 블록의 존재 유무에 따라 바이너리 이미지를 만들어낸다.

[Fig. 6] 

Image data transforming: if the camera captures like the left image, it is transformed into a binary data shown in the right side figure