강화학습 논문 정리 1편 : DQN 논문 리뷰 (Playing Atari with Deep Reinforcement Learning)

작성자 : 한양대학원 융합로봇시스템학과 유승환 석사과정 (CAI LAB)

 

 

 오늘은 강화학습 논문 DQN : Deep Q-Networks를 리뷰해보겠습니다~! 강화학습의 기초를 공부할 때는 DQN, DDPG 논문을 공부하면 좋다는 github.com/CUN-bjy 선배의 말을 듣고 강화학습 공부를 시작해봅니다!ㅎㅎ 논문에서 policy, agent, value function과 같은 강화 학습의 용어들이 자주 등장하는데, 아래의 링크 3을 참고하시면 됩니다~!

Q-learning과 DQN의 차이 // 출처 : https://greentec.github.io/reinforcement-learning-second/

---

링크 0 (승환 강화학습 논문 리뷰 모음) : github.com/RobotMobile/rl-paper-review

RobotMobile/rl-paper-review

 

링크 1 (DQN 원문) : www.cs.toronto.edu/~vmnih/docs/dqn.pdf

 

링크 2 (DQN 참고 블로그) : sumniya.tistory.com/18

[Ch.9] DQN(Deep Q-Networks)

링크 3 (강화학습 용어 정리) : wordbe.tistory.com/entry/RL-%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-part1-policy-value-function

[RL] 강화학습 part1 - policy, value function

---

0. Abstract

 <DQN>

  - 강화 학습(Reinforcement Learning) 사용

  - high-dimensional sensory input(vision, speech 등)으로부터 policy를 control하는 것을 배우는 딥러닝 모델

  - Q-learning으로 학습된 Convolutional Neural Network

  - input : raw pixels

  - output : value function (미래의 reward를 추정하는 함수)

  - 이 알고리즘을 Atari 2600 게임에 적용

 

---

1. Introduction

(1) RL의 challenges

  - vision, speech 같은 high-dimensional sensory inputs으로부터 agents를 control하는 것을 학습하는 것

  - 기존 연구 : feature representation(데이터)의 품질(quality)에 의존

 

(2) 딥러닝의 진보

  - 딥러닝은 raw data로부터 high-level feature를 extract할 수 있게 만들어줌 --> 데이터의 품질이 크게 중요하지 않게 됨

  - 이미지와 음성 인식에서는 딥러닝과 관련된 다양한 기법들이 탄생 (ex : CNN, multilayer perceptrons, Recurrent Neural Networks 등등)

  - 이 기법들은 RL에도 효과가 있을까?

 

(3) RL에 딥러닝 기법을 적용하기 위해 해결이 필요한 문제들

  - 첫째, 딥러닝 학습에는 라벨링된 대량의 학습 데이터 필요

  - 반면 강화학습 알고리즘의 데이터 특징 : 희박(sparse)하고 노이즈가 많으며 딜레이가 있는 스칼라 reward 신호

      --> quality가 좋은 대량의 데이터를 얻기 힘들다는 의미인 것 같습니다. 

  - agent가 action을 해야 reward를 받을 수 있는데, 이 action을 수행하는 시간 만큼 delay가 발생

 

  - 둘째, 대부분의 딥러닝 알고리즘의 데이터는 독립적이나, 강화학습은 highly correlated sates의 시퀀스를 마주침 --> (강화학습의 데이터는 비독립적이라는 뜻으로 이해 --> 데이터가 알고리즘에 영향을 미친다(?))

  - 게다가 agent가 새로운 action을 할 때 마다 데이터의 분포가 변경됨

  - 이는 데이터는 고정된 분포를 갖는다라는 딥러닝 방법에 문제가 됨

 

(4) 논문의 기여점

  - 본문에서는 이러한 문제를 CNN으로 극복하여, raw video data로부터 policy를 control하는 것을 성공적으로 학습을 함

  - Q-learning 알고리즘으로 이 네트워크를 학습

  - SGD(Stochastic gradient Descent) 알고리즘으로 weight를 업데이트

  - 데이터가 비독립적이며, 변하는 데이터 분포인 문제를 해결하기 위해 experience replay 기법 적용

  - 이 기법은 과거의 transition을 랜덤하게 샘플링하고, 학습 분포를 smooth하게 함

 

(5) 실험 환경

  - DQN을 적용한 게임 : Atari 2600 games

  - 게임 화면 : 210 x 160 (pixel) RGB video (60 Hz)

  - 연구 목표 : single neural network agent 생성 --> 가능한 많은 게임을 play하는 법을 학습

아타리 게임들 (출처 : DQN 논문)

---

2. Background

 (1) 본문에서의 고려 사항

  - agent가 actions, observations 그리고 rewards의 시퀀스로, 환경 E와 상호작용하는 것을 고려함

      * 환경 : 여기에서는 Atari emulator, 일반적으로 확률적(stochastic)

  - 각 time-step마다 agents는 game actions 세트 중에서 a_t라는 action을 선택함

      * game actions 세트 : A = {1, ... , K}

  - action은 state와 game score를 수정함

 

  - 환경(Atari emulator)의 state는 agent에 의해 관찰되지 않음

  - 대신 agent는 이미지 x_t를 관찰함

      * 이미지 x_t : 현재 화면을 표현하는 raw pixel value를 의미하는 vector

  - agent는 최종적으로 reward r_t를 받음

      * 보상 r_t : game score를 의미

  - 일반적인 게임에서는 action과 observations의 전체 순서에 의존

  - action에 대한 feedback(최종 reward)은 수천번의 time-step 이후에 받게 됨

 

(2) MDP : Markov Decision Process

  -  agent는 현재 화면만으로 모든 상황을 완전히 이해하는 것은 불가능

  - 따라서 action과 observatioin의 시퀀스에 의존하여 게임 전략 학습

      * s_t = x_1, a_1, x_2, a_2, ... , a_(t-1), x_t

      * x : 이미지 (obesrvation)

      * a : action

  - 모든 시퀀스는 time-step에 의해 의존 --> MDP가 유도됨

  - 결과적으로 MDP를 강화학습에 적용할 수 있게됨

  - 시퀀스 s_t를 시간 t의 표현으로 사용함으로써!

 

(3) Reward 수식

  - agent의 목표 : 미래의 reward를 극대화하는 action을 선택 

  - reward는 미래에 받는 것보다 가까운 시일 내에 받는 것이 더 좋음 --> reward에 감가율과 관련된 factor를 설정

  - 이 factor는 γ 이라고 표기 (time과 관련된 factor)

  - 보상의수식적 표현은 아래와 같음

reward의 수식, T : 게임이 끝나는 시점

(4) Action Value Function 수식 

<Action-Value Function>

  - Optimal Action-Value Function을 다음과 같이 표기 : Q∗ (s, a)

  - Q*(s, a)는 해당 sequence s에 action a를 취했을 때 최고의 보상을 받을 수 있는 함수

  - 이때, policy π가 등장하며, 이는 sequence를 action에 mapping

optimal action value function의 수식

 

 <Action-Value Function을 구하기 위한 Basic Apporach : Value Iteration>

  - Optimal Action Value Function은 bellman equation을 따름

  - bellman 방정식 : 다음 time-step에서 sequnce s'의 최적 값 Q*(s', a')가 모든 action a'에 대해 아는 경우, 최적의 전략은 기댓값(expected value)인 r + γQ*(s', a')를 최대화하는 action a'를 선택

Bellman Equation

  - bellman 방정식을 이용하여 action-value function을 업데이트함

  - 이러한 알고리즘을 value iteration라고 하며, 시간이 지나면서 최적의 Q 값을 찾음

Bellman 방정식을 활용한 action-value function의 update

  - 그러나 이러한 basic한 접근은 어떠한 일반화도 없이 각 sequence마다 action-value function을 추정하기 때문에 비현실적임

  - 함수의 근사치를 사용하여 action-value fucntion을 추정하는 것이 일반적

 

 <Action-Value Function을 구하기 위한 New Apporach : Neural Network>

  - 이 근사치를 neural network를 통해 비선형적 함수를 추정함

  - 이를 수행하는 neural network function approximator를 Q-Network라고 부름

  - Q-network는 Loss Function의 최솟값을 찾음으로써 학습됨

      * y_i : 정답 값

      * Q(s,  a : θ_i) : 예측값   // θ : 가중치

Q-Network의 loss function 수식

위 수식에서 y_i의 수식적 표현

  - neural network 학습을 통해 최적의 θ를 찾게 되는데, 이 과정을 다음과 같은 수식으로 표현 (SGD를 사용)

neural network 학습

---

3. Related Work

(1) TD-Gammon

  - Reinforcement Learning에서 가장 성능이 좋았던 알고리즘은 TD-gammon

  - TD-Gammon은 backgammon 게임을 사람의 게임 실력 수준만큼 play할 수 있음

Backgammon game 화면 // 출처 : https://www.youtube.com/watch?v=aK0PFA3oJkc

  - TD-gammon은 model-free reinforcement learning 알고리즘이며, Q-learning과 유사함

    * model-free란? : dreamgonfly.github.io/blog/rl-taxonomy/

강화학습 알고리즘 분류 | Dreamgonfly's blog

  - 1개의 hidden layer를 가진 multi-layer 퍼셉트론을 사용하여 Value Function을 근사화 함 

  - 그러나 TD-gammon은 체스나 바둑에서는 성능이 좋지 않음

 

(2) Model-Free Reinforcement Learning

  - Q-Learning : 비선형 함수로 Value Function을 근사화

  - Q-network : off-policy learning 

 

(3) 최근 연구

  - Reinforcement에 Deep Learning을 적용 시도

  - Deep Neural Networks는 environment ε를 구하기 위해 사용

  - Boltzmann machines : value 혹은 policy function을 구하기 위해 사용 -> 비선형 함수 근사치를 사용하여 고정된 policy를 평가할 때 수렴 가능

  - Q-learning의 발산 문제 : gradient temporal difference 방법으로 극복 -> Q-Learning의 변형을 사용하여 선형 함수 근사치를 갖는 control policy를 학습할때 수렴 가능

  - 그러나 Boltzmann machine과 Q-learning 등과 같은 방법들은 non-linear control에는 확장되지 못함

 

(4) 최근 연구 : NFQ (Neural Fitted Q-learning)

  - 본 연구(DQN)과 가장 유사한 접근 방식을 지닌 선행 연구는 NFQ : Neural Fitted Q-Learing

  - NFQ는 아래의 loss function 수식을 RPROP 알고리즘을 사용하여 Q-network의 파라미터를 업데이트 및 최적화 함

Loss function

  - 그러나 모든 데이터셋을 한번에 학습하는 batch update를 이용하기 때문에 연산량이 어마어마 함

  - 그래서 본 연구에서는 대량의 데이터도 효율적으로 연산할 수 있는 SGD 알고리즘을 고려함

  - DQN과 NFQ의 차이점은 end-to-end 여부 (DQN은 end-to-end : visual input으로 바로 결과를 보여줌)

  - Q-learning을 experience replay와 간단한 neural netowrk로 병합함

---

4. Deep Reinforcement Learning

<본 연구의 목표>

  - 강화학습 알고리즘을 deep neural network에 연결

  - SGD 업데이트를 통해 학습 데이터(RGB images)를 효과적으로 process함

 

<영감을 받은 선행 연구 : TD-Gammon architecture (On-policy)>

출처 : 위키백과

  - 이 아키텍쳐는 on-policy samples(s_t, a_t, r_t, s_t+1, a_t+1)을 통해 value function을 추정하는 network의 파라미터를 업데이트 함

 

<본 연구와 선행 연구의 차이점 : Experience Replay>

  - Experience Replay : agent의 experience를 각 time-step마다 저장함 (e_t = (s_t, a_t, r_t, s_t+1))

  - 많은 에피소드를 걸쳐 replay memory에 pool함 (?)

  - experience samples에 Q-Learning과 mini-batch update를 적용

  - experience replay를 수행한 후, agent는 greedy policy에 따라 action을 선택 및 수행

 

  - 이러한 접근은 표준적인 online Q-learning보다 다양한 이점을 지님

  - 첫째, 각 step의 experience(e_t)는 많은 weight 업데이트에 사용될 수 있음 -> 데이터를 효율적으로 사용 가능

  - 둘째, 표본을 랜덤하게 추출함으로써, weight 업데이트의 분산을 줄게 함 

      * 연속된 샘플에서 직접 학습하는 것은 샘플 간의 강한 상관 관계 (특히 시간의 흐름) 때문에 비효율적임

  - 셋째, 학습을 안정적으로 만듦

      * on-policy로 학습하는 경우, 현재의 파라미터가 다음의 데이터 샘플을 결정함

      * 이렇게 되면 local minimum에 빠질 가능성이 높아짐

      * 그러나 experience replay를 사용하면, behavior distribution이 평등해짐

 

  - experience replay로 학습하려면, off-policy를 학습하는 것이 필수적

  - 왜냐하면 현재의 파라미터는 sample을 generate하는데 사용하는 것과 다르기 때문

  - 이는 Q-Learning의 선택에 영감을 줌

 

  - DQN 알고리즘은 replay 메모리 D에서 최근 N개의 experience tuples만을 저장

  - 그리고 학습을 할 때, D에서 random한 sample(experiece tuples)를 샘플링함

  - 이러한 접근은 D의 메모리 용량이 한정적이기 때문에 모든 experience를 저장할 수 없다는 점에서 제한적임

  - 따라서 experience를 최대한 균일하게 추출하기 위한 방법들이 필요함 (ex : Prioritized sweeping)

      * Prioritized sweeping은 1993년도 논문이라 정리된 글이 없네욥...

---

[Deep Q-learning with Experience Replay's Algorithm]

출처 : DQN 원문

(1) 변수 초기화

  - replay memory D 초기화 (D의 메모리 용량은 N)

  - action-value function Q 초기화 (= random한 weight를 지니도록 초기화)

변수 초기화

(2-1) 반복문 : 에피소드 별 반복 (학습 횟수)

  - sequence 초기화 : s1 = {x1}

  - sequence 전처리

    * 전처리에 대한 내용은 아래 4.1절에서 나옴 (단순한 이미지 resize)

에피소드 반복문

(2-2) 반복문 : 한 에피소드 내에서 시간에 따라 반복

  - ϵ의 확률로 랜덤한 action a_t를 선택

  - 이때 a_t를 선택하는 기준은 Q-value를 최대화 시키는 a_t를 선택

  - a_t를 emulator(Atari)에서 실행하고 reward r_t와 다음 이미지 x_t+1를 관찰

(a_t, r_t, x_t+1)를 취득하는 과정

  - sequence를 다음과 같이 정의 : s_t+1 = s_t, a_t, x_t+1 

  - 그 후 sequence를 전처리하고 replay memory D에 저장

     * 다음의 sequence를 transition이라고 정의 : [ Φ_t, a_t, r_t, Φ_t+1 ]

  - D로 부터 transition을 minibatch 형태로 랜덤하게 추출함

DQN 데이터 형태 : transitions

  - 정답 값 y_j은 아래와 같이 정의하고, 이 정답값과 DQN의 판단값의 차이를 이용하여 SGD로 DQN을 최적화 시킴

 

DQN 최적화 과정

    * terminal과 non-terminal의 차이를 모르겠습니다... 추후 공부하게 되면 업데이트 하겠습니다.

---

4.1 Preprocessing and Model Architecture

(4.1-1) Preprocessing

Preprocessing // 출처 : https://sumniya.tistory.com/18

  - 아타리 게임 이미지 크기 : 210 * 160 (pixel)

  - 다음과 같은 전처리 과정을 거침

1. 110 * 84 pixel로 이미지 사이즈를 줄이고, gray-scale로 변경 (채널 수 3 -> 1)
2. 실질적으로 게임이 이루어지는 영역으로 84*84 pixel 사이즈 만큼 crop함

  - CNN의 입력은 정사각형이여야 하므로 이 과정은 필수라고 논문에 적혀있지만, 최근에는 SPP layer를 이용하여 이러한 제한이 많이 사라짐

  - 위 DQN 알고리즘에서 function Φ이 이에 대한 내용임

---

(4.1-2) Model Architecture

DQN 아키텍쳐 // 출처 : https://sumniya.tistory.com/18

  - Q 함수는 Q-value의 추정치를 mapping하기 때문에, history(sequence)와 action은 neural network의 input으로 사용됨

    * 선행 연구 1 : Deep auto-encoder neural networks in reinforcement learning(2010)

    * 선행 연구 2 : Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method(2005))

  - 이러한 접근은 각 action에 대한 Q-value를 계산하기 위해 별도의 forward pass (연산 과정)이 필요함 (action이 input으로 들어가기 때문)

 

  - 반면 DQN은 state representation만을 network의 input으로 사용함

  - 이때의 output은 input state에 대한 개별 action의 예측한 Q-value에 해당함

  - 이러한 아키텍쳐 구조는 주어진 state에 대해 가능한 모든 action의 Q-value를 계산 가능함 (오로지 single forward pass를 통해)

---

5. Experiments

(1) 테스트 환경 : ATARI Game

  - 7개의 유명한 ATARI game에 대해서 DQN의 성능을 테스트함 (Beam Rider, Breakout, Enduro, Pong, Q*bert, Sequest, Space Invaders.)

  - 모든 게임에 대해 동일한 조건(네트워크 구조, 학습 알고리즘, 파라미터 셋팅 등등)으로 실험을 진행

  - 이에 대한 실험 결과는 우리의 접근이 다양한 게임에서 효과가 있다는 것을 증명함

  - 본 실험에서 agent를 실제의 game에서 평가하기 때문에, 모든 reward는 정수로 표기함

    * 1 : positive reward

    * -1 : negative reward

    * 0 : unchanged

  - 이러한 셋팅은 error의 scale를 제한함으로써 다양한 게임에서 동일한 학습률(learning rate)을 더 쉽게 사용할 수 있게 해줌

 

(2) 실험 설정 값

  - 최적화 알고리즘으로 RMSProp을 사용 (minibatch size : 32)

  - 학습에는 총 천만 프레임을 사용했으며, 최근 백만 프레임만을 replay memory에 사용

  - 처음의 백만 프레임에서 ε값을 1에서 0.1로 선형적으로 조정 & 그 이후 프레임에서는 모두 0.1로 고정 (ε-greedy)

 

(3) Frame Skipping technique

  - 본 연구에서는 간단한 frame-skipping technique 기법을 사용함

    * 관련 선행 연구 : The arcade learning environment: An evaluation platform for general agents.

  - agent는 모든 프레임이 아니라, k번째 프레임만을 보고, action을 선택함

  - 그 외의 프레임에서는 가장 최근의 action을 선택

  - 이 기법을 적용하면 k배 만큼 더 게임을 play할 수 있음 (연산량이 줄었기 때문)

  - 본 실험에서는 k=4로 설정 (4 배수 프레임에서만 action을 선택)

  - 단 Space Invader 게임에서만 k=3으로 설정 (4배수 프레임에서 비행기에서 쏘는 레이저가 사라지는 문제점 때문)

Space Invaders 게임 화면 // 출처 : https://www.denofgeek.com/games/how-space-invaders-became-a-gaming-phenomenon/

---

5.1 Training and Stability

에피소드별 평균 reward 그래프 (좌 : BreakOut, 우 : Sequest)

평균 action value (Q) 그래프

  - 10,000 step 동안  ε=0.05적용하여 계산된 value들

    * (위 실험 설정값에서는  ε=0.1이라고 했는데 왜 갑자기 0.05지,,?)

  - 1 에포크는 50,000 mini-batch의 weight 업데이트 혹은 30분 가량의 학습 시간을 의미

  - 학습이 진행될수록 reward와 action value가 증가하는 것을 볼 수 있음

---

5.2 Visualizing the Value Function

Seqquest game의 value function의 시각화 (좌 : A, 중앙 : B, 우 : C)

---

5.3 Main Evaluation

알고리즘 별 Atari 게임의 총 reward (Human은 사람이 직접 플레이)

---

6. Conclusion

  - 본문에서는 Reinforcemnet learing을 위한 새로운 deep learning model을 소개함

  - input으로 raw pixels을 사용하며, Atari 2600 컴퓨터 게임에서 테스트를 진행

  - experience replay memory로 mini-batch 방식을 사용하는 변형된 online Q-learning을 제안함

  - 우리의 접근은 아키텍쳐나 하이퍼 파라미터의 조정 없이, 7개의 아타리 게임에서 모두 최고의 성능을 발휘함

---