[NIPS 2013]Playing Atari with Deep Reinforcement Learning

안녕하세요 이번 논문은 Q Learning의 Q값을 Regression하는 DQN(Deep Q Network)를 적용해서 게임을 하는 강화학습 논문 입니다. DNN과 RL을 결합하는 최초의 시도는 아니지만 정말 의미있는 수준의 결과가 나온 첫번째 논문이라고 합니다. 저번주에 리뷰한 내용이 아직 미숙한 상태여서 조금 더 앞에서부터 공부하고 논문 리뷰도 해보려고 합니다,,

Q-Learning

우선 DQN은 Q-Learning을 바탕으로 하기 때문에 Q-Learning에 대해 간단하게 적고 넘어가도록 하겠습니다. Model free 강화학습이고, time step 별로 state와 action에 대한 보상을 추정하는 함수인 Q(s,a)를 학습하여 각 주어진 상태에서 행동을 선택했을 때 기대되는 누적 보상을 벨만 방정식을 기반으로 아래 식과 같이 업데이트 합니다. α는 learning rate(새로운 Q값을 얼마나 비중있게 반영할 것인지) , γ는 할인율(지금 state와 멀수록 얼만큼 보상을 약화시킬 것인지), r은 현재 상태 s에서 행동 a를 했을 때의 reward, s′은 t+1시점의 상태를 의미합니다. 이 식을 활용해 Q값이 최대가 되는 행동을 선택해나가면서 exploration과 exploitation을 활용한 엡실론-그리디 방식의 전략을 통해 state-action의 reward를 학습하게 됩니다.

뭔가 식이 복잡해보였는데, 쉽게 생각하면 지금 한 행동에서 실제로 받은 보상과, 그 다음 시간 t+1 에서 가장 잘한 행동의 가치(앞으로 받을 수 있는 최대 기대 보상)을 더해서, 지금의 Q값을 조금씩 더 정확하게 바꿔나가는 식입니다. 결론적으로, Q-learning은 에이전트가 직접 부딪혀보면서 “아, 이럴 땐 이게 낫구나”를 직접 몸으로 배워나가는 느낌입니다. 추가로 배워나가는 과정에서 엡실론을 통해 (엡실론은 0~1 사이의 숫자입니다.) 엡실론의 확률 만큼 기존의 reward를 따라서 greedy하게 action하지 않고 random한 action을 취하는데, 이는 혹시 모를 다른 방향에서의 보상이 클 수 있기 때문에 모험을 하는 exploration의 개념입니다. 이러한 Q함수를 신경망으로 근사시킨 것이 DQN인데요, 논문을 자세히 살펴보도록 하겠습니다.

Introduction

강화학습에서 가장 어려운 부분 중 하나는 에이전트가 복잡한 환경을 센서 데이터만으로 스스로 조작할 수 있도록 만드는 것이라고 합니다. 게임 화면과 같은 vision 데이터를 그대로 받아들이고, 이를 기반으로 행동을 결정하게 만드는 것이 hand craft feature 없이는 매우 힘들었다고 합니다. 대부분 사람이 설계한 feature를 먼저 뽑고, 그 위에 간단한 정책 모델이나 가치 함수만 얹는 구조였고, 얼마나 좋은 특징을 미리 설계했냐에 따라 성능이 결정되었고, 이렇기 때문에 범용성이나 확장성 측면에서 한계가 있었다고 합니다. 하지만 딥러닝은 raw image나 음성 같은 입력으로부터 고차원 표현을 스스로 학습할 수 있게 만들었고, 강화학습에도 적용해 사람처럼 화면만 보고 게임을 배울 수 있는 에이전트를 만들 수 있다는 접근이었습니다.

하지만 강화학습은 딥러닝과는 다른 부분이 있었는데, 딥러닝은 보통 ‘정답 라벨이 주어진 대량의 데이터’를 전제로 학습하지만, RL은 보상 신호 하나만 가지고 학습해야 하는 것이 가장 핵심적인 부분이었다고 합니다. 그럼에도 저자들은 이 논문에서 CNN 기반의 신경망이 영상 입력만으로 게임 플레이를 학습하고, Q-learning의 변형된 형태로 정책을 학습했다고 합니다. 그리고 강화학습의 불안정성을 줄이기 위해 off-policy 방식을 채택하고 여기서 Experience Replay 기법을 사용해, 과거 데이터를 무작위로 섞어 안정적인 학습 분포를 만들었다고 합니다. (핵심 contribution인 것 같습니다.)

실험은 Atari 2600 게임을 대상으로 진행했습니다. Atari 2600은 아래 스크린샷과 같이 블럭 깨기나 팩맨같은 여러가지 미니게임을 할 수 있는 환경인데, DQN 네트워크는 어떤 게임이든 동일한 구조와 하이퍼파라미터로 학습되고, 오직 게임 화면, 보상, 종료 신호, 그리고 가능한 행동만을 입력으로 사용해 하나의 네트워크가 여러 게임을 학습하는 데 성공했다고 합니다. 이러한 알고리즘은 기존의 알고리즘들을 능가했고, 심지어 3개의 게임에서는 인간 전문가보다 높은 점수를 기록했다고 합니다.

Background

앞서 말했듯 이 연구에서는 에이전트가 Atari 게임 에뮬레이터 환경과 상호작용 하고, 에이전트는 매 시점마다 가능한 게임 행동 집합 A 중 하나를 선택해 수행했습니다. 행동은 에뮬레이터 내부 상태를 변화시키고 게임 점수에 영향을 미칩니다.(말그대로 게임에서 조작할 수 있는 키 중에 하나를 선택해 수행하며 플레이 해나갔다는 얘기입니다.) 에이전트는 에뮬레이터의 내부 상태를 직접 볼 수 없고 에뮬레이터의 현재 화면을 구성하는 픽셀 값 벡터 형태의 x_t와 행동에 따른 점수 변화인 보상 r_t​만을 observe할 수 있습니다. 하지만x_t​만으로는 게임 상황을 완전히 파악하기 어려운 경우가 많았다고 합니다. 이는 동일한 화면이 서로 다른 게임 맥락을 나타낼 수 있기 때문이었다고 합니다. 저자들은 이러한 상황을 ‘perceptual aliasing’이라고 부릅니다. 따라서 이 연구에서는 단일 이미지를 넘어서, 이전 관측과 행동의 시퀀스 s_t = x_1,a_1,x_2, …, a_t-1, x_t (처음부터 현재 상황까지의 액션과 그에 따른 환경 변화의 시퀀스)를 상태로 간주하고, 이 시퀀스를 기반으로 게임 전략을 학습했다고 합니다.

모든 시퀀스는 유한한 시간 안에 종료된다고 가정되며, 이로 인해 이 문제는 유한 상태 공간을 갖는 MDP로 모델링했습니다. 이를 통해 일반적인 강화학습 기법을 적용할 수 있고, 시점 t에서의 state로 전체 시퀀스 s_t​를 사용함으로써 학습을 진행했습니다. Value Iteration을 통해 최적의 Q*를 찾아야 하지만 실제로는 각각의 시퀀스에 대해 별도로 Q(s,a)를 추정해야 하기 때문에 계산량이 방대하고 일반화가 어려웠다고 합니다. 따라서 저자는 신경망을 사용한 Q-네트워크 Q(s,a;θ)를 도입하여 state-action 함수를 근사했다고 합니다. 식에서 θ는 신경망의 가중치입니다.

Q-네트워크는 반복마다 바뀌는 손실 함수 Li(θi)를 최소화하는 방식으로 학습됩니다. 이 손실 함수는 다음과 같은 형태입니다.

계산량을 줄이기 위해 위의 기대값 대신 샘플 하나만 사용하여SGD를 통해 한 시점마다 샘플을 통해 Q-네트워크를 업데이트하게 되며, 이는 우리가 잘 알고 있는 Q-learning 알고리즘의 형태와 일치하게 된다고 합니다. 따라서 model-free 방식으로 작동해 환경 E의 모델을 명시적으로 학습하지 않고, 시뮬레이터로부터 얻은 샘플만으로 정책을 학습합니다. 또한 off-policy 방식이기 때문에, 실제로 따르는 action policy와 별개로 target policy에 대한 학습을 진행합니다.

Deep Reinforcement Learning

앞에서도 간단히 언급했지만 Linear Regression이 어떤 분포를 잘 나타내는 선을 근사하는 것 처럼 Deep Q Network는 게임과 같은 무수하게 많은 state를 가지는 환경에서 주어진 샘플들을 통해 regression으로 어떤 Q_w값을 잘 구할 수 있도록 w를 업데이트 해주는 것 핵심입니다. 해당 논문에서는 CNN을 통한 feature 추출을 통해 아타리 게임의 raw input으로부터 직접 학습하며, 업데이트 했습니다. 다만 Q learning이 Q(S_t,a_t)를 구할 때 s_t, a_t를 둘 다 식에 넣고 계산한 것에 반해 CNN을 통해 얻은 출력이 입력 state에 대한 각 action을 했을 때의 Q값이 된다고 합니다. 단일 상태 입력에 대해 모든 행동의 Q값을 동시에 출력하는 구조를 사용해서 (state, action)을 쌍으로 신경망에 넣고 Q값을 추정하는 방식은 각 행동마다 한 번씩 신경망을 실행해야 하므로 계산 비용이 행동 수에 비례하게 되지만, 해당 방법은 신경망 입력으로 상태만 넣고, 출력층에서 가능한 모든 행동에 대한 Q값을 한 번에 출력하는 구조라 효율적이라고 합니다.

이와 유사한 접근의 초기 예시로는 Tesauro의 TD-Gammon이 있었다고 합니다. 이 방식은 value function을 추정하는 네트워크의 파라미터를 환경과의 상호작용에서 얻은 on-policy 샘플을 바탕으로 직접 업데이트합니다. 하지만 이번 논문은 Ton-policy 방식이 아닌, Experience Replay 기법을 활용했다고 합니다. 이는 매 타임스텝마다 에이전트가 얻은 경험 e_t=(s_t,a_t,r_t,s_t+1)를 데이터셋 D={e_1,…,e_N}에 저장해두고, 이를 여러 에피소드에 걸쳐 재활용하는 방식입니다. 알고리즘의 내부 루프에서는, 이 저장된 샘플 풀에서 무작위로 선택한 미니배치 샘플을 사용해 Q-learning 업데이트를 수행합니다. 그 다음, 에이전트는 ε-greedy 정책에 따라 행동을 선택하고 실행합니다. 하지만 시퀀스 기반의 상태 히스토리를 신경망의 입력으로 사용하는 것은 실질적으로 어렵기 때문에, 본 논문에서는 이 히스토리를 고정 길이 벡터로 변환하는 함수 φ를 정의하고, 이 φ를 통해 생성된 표현 위에서 Q-함수를 학습합니다. 이러한 전체 과정을Deep Q-learning이라고 정의했고, 구체적인 알고리즘은 다음과 같습니다.

알고리즘은 Experience Replay와 신경망 기반의 Q-함수 근사를 중심으로 구성됩니다. 우선, 에이전트는 환경과 상호작용하며 시간 순서에 따라 s_t,a_t,r_t,s_t+1로 이루어진 전이 정보를 수집합니다. 이때의 state는 실제 게임 화면 이미지이며, 여러 개의 프레임을 시퀀스로 묶어 과거 정보를 포함하는 형태로 구성됐습니다. 이 시퀀스는 신경망에 직접 입력되기 어렵기 때문에, 이를 고정된 길이의 벡터로 변환하는 전처리 함수 φ를 통해 표현을 정제한다고 하빈다.

학습은 에피소드 단위로 이루어지며, 각 에피소드 내에서 타임스텝 t마다 다음과 같은 방식으로 작동합니다. 먼저, 에이전트는 현재 상태 표현 ϕ(s_t)에 대해 확률 ε로 무작위 행동을 선택하거나, 그렇지 않은 경우에는 Q-네트워크의 출력을 기반으로 가장 큰 Q값을 가지는 행동을 선택합니다. 이 방식은exploration과 exploitation 사이의 균형을 유지하기 위한 것으로, 정책은 ε-greedy 방식으로 구현했습니다. 선택된 행동은 환경(Atari 에뮬레이터)에 적용되며, 그 결과로 보상 r_t​ (reward로는 게임 점수를 사용했습니다.)와 다음 화면 이미지가 반환됩니다. 이 이미지와 기존의 시퀀스를 결합해 새로운 상태 시퀀스 s_t+1을 구성하고, 이를 다시 전처리하여 ϕ(s_t+1)를 생성합니다. 이렇게 구성된 전이 (ϕ(s_t),a_t,r_t,ϕ(s_t+1))는 Experience Replay Memory (D)에 저장됩니다. 이 메모리는 고정된 크기 N을 가지며, 가장 오래된 샘플부터 순차적으로 덮어쓰는 방식이라고 합니다.

학습의 핵심은 이 저장된 전이들을 활용해 Q-네트워크를 업데이트하는 데 있습니다. 알고리즘은 리플레이 메모리에서 무작위로 일정 수의 전이 샘플을 mini batch로 추출하고, 각 샘플에 대해 다음 상태 ϕ(s_j+1)이 종결 상태(terminal)인지에 따라 타깃 값을 설정합니다. 종결 상태인 경우 타깃은 단순히 보상 r_j​이고, 비종결 상태에서는 타깃 값 y_j​를 r_j+γ*max(⁡a′Q(ϕ(s_j+1),a′;θ)로 계산합니다. 이때 Q값의 두 번째 항은 현재 네트워크의 파라미터 θ를 사용해 추정됩ㄴ디ㅏ. 이후, 각 샘플에 대해 loss 함수의 그래디언트를 계산하고, 이를 바탕으로 신경망 파라미터 θ를 SGD를 통해 업데이트합니다. 이 과정을 반복함으로써, 에이전트는 점차 다양한 시각 입력에 대한 Q값을 정교하게 추정할 수 있게 되고, 이는 곧 더 나은 행동 선택으로 이어지게 한다고 합니다. 정리하면, 알고리즘은 여러 경험을 저장하고 재사용함으로써 표본 효율성과 안정성을 높이고, CNN을 활용해 Q함수를 근사함으로써 고차원의 vision input에서도 end to end로 직접 강화학습을 할 수 있다는 강점을 가지게 됩니다.

모델의 구조와 input에 대해 조금 더 부가적인 설명을 하자면 Atari의 프레임은 210×160 해상도의 RGB 이미지로, 128색 팔레트를 사용합니다. Input으로 들어갈 때는 RGB에서 그레이스케일로 변환되며, 이어서 110×84 크기로 다운샘플링한 후에 주요 게임 영역만 포함하도록 이미지의 중앙에서 84×84 크기의 정사각형 영역을 크롭하여 최종 입력으로 사용한다고 합니다. 정사각형으로 crop하는 것을 통해 GPU에서 효율적인 2D 컨볼루션 연산을 수행할 ㅜㅅ 있다고 하네요. 이렇게 전처리된 이미지는 단일 프레임만 사용하는 것이 아니라, 최근 4개의 프레임을 φ 함수로 처리한 뒤 스택하여 입력으로 사용합니다. 따라서 Q-네트워크의 입력은 84×84×4 크기의 텐서가 되며, 이는 시간 축의 정보를 반영하여 현재 상태의 움직임이나 방향성 같은 동적 특성을 포착할 수 있게 됩니다.

이런 알고리즘을 따르는 방식은 기존의 Q-learning 방식에 비해 여러 가지 장점을 갖고 있다고 합니다. 하나의 경험 샘플이 여러 번 학습에 사용될 수 있기 때문에, 데이터 효율성이 높습니다. 또, 연속된 시간 단계에서 수집한 샘플들은 강한 상관관계를 가지므로, 이들을 그대로 학습에 사용하지 않고 무작위 샘플링을 통해 이 상관성을 깨뜨리면, 업데이트의 분산이 줄어들고 학습이 더 안정적으로 이루어집니다. Mini batch SGD를 사용하는데, 이 때 independent한 정도를 높여주는 느낌입니다.

더 나아가 안정적인 학습을 진행할 수 있습니다. on policy 방식에서는 현재 모델 파라미터에 따라 다음 샘플이 결정되기 때문에, 학습이 지나치게 편향될 수 있는 피드백 루프가 발생한다고 합니다. 예를 들어, 현재 최적 행동이 왼쪽으로 이동하는 것이라면 대부분의 샘플은 왼쪽에서 수집될 것이고, 나중에 최적 행동이 오른쪽으로 바뀌면 전체 샘플 분포가 급격히 이동하게 되고, 이러한 편향된 학습 분포는 지역 최적점에 갇히거나, 심할 경우 파라미터가 발산하는 원인이 될 수 있다고 합니다. 반면, Experience Replay 방식은 다양한 상태에서 수집한 데이터를 혼합하여 사용하기 때문에, 행동 분포를 평균화하고 학습을 부드럽게 만들어준다고 합니다. 또한, 이는 파라미터의 진동이나 발산 현상을 줄이는 데에도 효과적이라고 합니다. 이러한 방식은 현재 학습 중인 정책과 샘플을 생성했던 정책이 다르기 때문에 off-policy 학습이 필요하며, Q-learning이 이 조건에 적합한 알고리즘이라는 점에서 선택되었다고 합니다.

다만 실제로는 buffer 메모리의 한계로 인해, 알고리즘은 최근 N개의 경험만을 리플레이 메모리에 저장합니다. 업데이트 시에는 메모리 D에서 uniform한 랜덤 샘플링을 하며 학습을 수행합니다. 이 방식은 간단하고 구현이 쉬운 장점이 있지만, 중요한 transition과 그렇지 않은 transition을 구분하지 않고 모두 동일한 확률로 샘플링하기 때문에, 학습에 더 큰 기여를 하는 전이에 집중하지 못한다는 한계가 있다고 합니다.

Experiments

Deep Q-learning 알고리즘을 실제 Atari 게임에 적용했습니다. Beam Rider, Breakout, Enduro, Pong, Q*bert, Seaquest, Space Invaders의 총 7가지 게임을 대상으로 실험을 진행했으며, 모든 게임에서 동일한 신경망 구조, 학습 알고리즘, 하이퍼파라미터를 사용하였다고 합니다. (reward로 게임 점수만을 활용해서 가능했던 것 같습니다) 이를 통해 특정 게임에 맞춘 설계 없이도 학습이 가능하다는 알고리즘의 Robustness를 검증하고자 했다고 합니다.

다만 학습 안정성과 효율성을 위해 보상 신호에 한 가지 조정을 했는데요, Atari 게임마다 점수의 범위가 상이하기 때문에, 학습 중에는 모든 양의 보상은 1로, 음의 보상은 -1로 클리핑하고, 0 보상은 그대로 유지하였다고 합니다. 이 방식은 오차의 크기를 제한하여 학습 시 기울기가 튀는것을 방지하고, learning rate를 모든 게임에서 통일되게 적용할 수 있도록 한다고 합니다. 하지만 클리핑으로 인해 서로 다른 크기의 보상이 동일하게 처리되므로, 에이전트는 보상의 상대적 중요도를 구분하지 못할 수 있다고도 합니다.

학습은 총 1,000만 프레임에 걸쳐 진행되었고, 최근 100만 프레임을 저장하는 리플레이 메모리가 사용되었습니다. 최적화 알고리즘으로는 RMSProp을 사용하였고, mini batch 크기는 32로 설정되었스빈다. Action은 ε-greedy 정책을 따르며, ε은 처음에 1에서 시작하여 100만 프레임 동안 선형적으로 0.1까지 감소한 후, 그 이후로는 0.1로 고정되었다고 합니다.

또한 Atari 게임 환경의 특성을 고려하여 프레임 스킵 기법도 적용했다고 합니다. 에이전트는 모든 프레임에서 행동을 선택하는 것이 아니라, 매 4번째 프레임마다 행동을 결정하고, 그 외의 프레임에서는 마지막 행동을 반복했습니다. 이렇게 하면 에이전트는 더 많은 게임을 경험할 수 있으면서도 계산 비용을 줄일 수 있다고 하는데요, 게임이 진행되는 양상이 연속적이어서 가능한 것 같습니다. 그래서인지 Space Invaders에서는 이 설정이 문제를 일으켰다고 합니다. 해당 게임의 레이저는 특정 주기로 깜빡이는데, 4프레임 간격으로 행동을 선택하면 레이저가 보이지 않는 문제가 발생해서 프레임 스킵 값을 3으로 조정했다고 합니다.

평가의 경우 지도학습에서는 성능을 검증 데이터셋으로 쉽게 측정할 수 있지만, 강화학습에서는 정확한 성능 평가가 어렵고 불안정한 경우가 많아서 에피소드별 누적 보상의 평균을 성능 지표로 사용했다고 합니다. 하지만 이 지표는 매우 노이즈가 심하며, 정책의 미세한 변화가 에이전트가 방문하는 상태 분포를 급격히 바꾸기 때문에, 학습이 실제로 진행되고 있는지를 명확히 확인하기 어려운 문제가 있어 저자들은 보다 안정적인 대안 지표로서 Q값의 추정치를 사용했다고 합니다. 학습 전에 무작위 정책으로 수집한 일정 수의 상태들을 고정하고, 학습이 진행되는 동안 각 상태에 대해 예측된 Q값의 평균을 추적했습니다. 이 Q값의 평균은 아래와 같이 누적 보상보다 훨씬 부드럽고 일관된 증가 추세를 보였으며, 다른 게임들에서도 마찬가지로 안정적인 곡선을 나타냈다고 합니다.

다른 RL 방법들과 점수를 비교해 본 결과는 다음과 같습니다.

먼저, Sarsa와 Contingency는 Atari 게임을 위해 설계된 hand crafted feature들을 기반으로 선형 정책을 학습한 알고리즘이라고 합니다. 특히 Contingency는 배경 제거, 128개 색상을 각각 하나의 채널로 처리하는 등 시각 구조에 대한 사전 지식을 적극 활용했음에도 점수가 낮았습니다. 이에 반해, DQN은 어떠한 사전 지식도 사용하지 않고, 오직 RGB 스크린샷만을 입력으로 받아 학습했습니다. 이를 통해 네트워크는 객체나 중요한 시각 정보를 스스로 학습을 통해 추출하고 입력에 대한 사전 가공 없이도 전략을 형성할 수 있다는 점을 증명했다고 합니다.

평가는 Bellemare et al.의 방식에 따라, 학습된 정책을 ε=0.05의 ε-greedy 방식으로 고정된 시간 동안 실행하여 얻은 평균 점수를 기준으로 진행했다고 합니다. 위의 표의 상위 5개 행은 이 기준으로 평가한 각 게임의 평균 점수를 비교한 결과이며, DQN은 모든 게임에서 기존 학습 기반 방법들을 큰 차이로 앞섰습니다. 사람보다 잘한다는게 진짜 신기한 것 같습니다. HyperNEAT 기반의 진화적 탐색 방법과의 비교도 포함되어 있는데, Space Invaders를 제외한 모든 게임에서 평균 및 최대 점수 모두 HNeat 방법보다 우수한 결과를 달성했습니다.