CS231N chapter 14 - Reinforcement Learning

13강 리뷰

1) PixelRNN/CNN

2) VAE

• Autoencoders
• Variational Autoencoders

3) GAN

우리는 지금까지 supervised learning을 배웠다. 지도 학습이란 데이터 x와 레이블인 y가 있고, x를 y에 매핑하는 함수를 학습하는게 목표인 학습이다. 가령 분류(classification)이 이에 해당한다.

그리고 지난 강의에서 비지도 학습(unsupervised learning)을 배웠다. 데이터는 있는데 레이블이 없는 경우다. 데이터에 내재된 구조를 학습하는 것이 목표인 학습이다. 가령 생성모델(generative models)가 이에 해당한다.

오늘 강의를 대충 소개하면

overview

1. What is Reinforcement Learning?
2. Markov Decision Processes(MDP)
   • MDP는 강화학습 문제의 수식체계(formalism)이다.
3. 강화학습의 대표적인 방법
   • Q-Learning
   • Policy Gradients

Reinforcement learning

강화학습에는 에이전트(agent)가 있다. 환경(environment)에서 행동(action)을 취하는 주체다. 에이전트는 행동에 따른 적절한 보상(rewards)을 받는다. 즉, 에이전트는 환경에서 행동을 취하여 적절한 보상을 받는 주체다.

강화학습은 에이전트의 보상을 최대화할 수 있는 행동이 무엇인지를 학습한다.

예를 들어, 고양이가 있고, 빨간색 버튼을 누르면 간식이 나오는 기계가 있다고 가정해보자. 고양이는 어떻게 해야 간식이 나오는지 모를 것이다. 아무거나 다 시도해보다가 버튼을 눌렀을 때 간식이 나오는 것을 확인한다. 이 때, 고양이(agent)는 간식이 나오는 기계(environment)의 버튼을 누르면(action) 간식 나온다는(rewards) 것을 학습한 것이다.

예시로, “cart-pole” 문제가 있다. 이 문제의 목표는 움직이는 카트(cart)와 카트 위에 매달려있는 막대기(pole)의 균형을 유지하는 것이다. 상태(state)에는 현재 시스템이 기술되어 있다. 막대기의 각, 각속도, 카트의 위치 등이 있을 것이고, 에이전트는 카트를 수평으로 미는 행동을 취할 수 있다. 카트를 밀면서 동시에 막대기의 균형을 잘 유지해야 한다. 막대기가 균형을 잘 맞춰 제대로 서 있으면 환겨으로부터 보상을 받을 수 있다.

고전적인 RL(Robot Locomotion = 로봇 보행) 에 대한 예시도 살펴보자. 사진을 보면 휴머노이드 로봇과 개미 로봇 모델이 있다. 로봇이 앞으로 나아가도록 하는 것이 목표다. 이 문제에서 상태(state)는 로봇의 모든 관절들의 각과 위치다. 에이전트가 취할 수 있는 행동(action)은 각 관절들에 가해지는 토크다. 이 문제에서 하고 싶은 것은 로봇이 앞으로 전진하는 것이다. 앞으로 가면 보상을 받고, 휴머노이드는 바로 서있어도 보상을 받는다.

RL을 통해 게임 문제도 풀 수 있다. 여기 아타리 게임(atrari games)가 있다. 깊은 강화학습이 아주 큰 성과를 이룬 종목이다. 아타리 게임은 가능한 가장 높은 점수로 게임을 마치는 것이 목적이다. 에이전트가 게임 플리에어가 되어 게임을 진행한다. 위의 사진처럼 우리가 게임할 때 보이는 화면 그 자체가 상태(state)이다. 에이전트의 행동은 우리가 게임 플레이할 때처럼 위아래/좌우로 움직일 수 있다. 매 스텝마다 게임 점수를 확득할 수도, 잃을 수도 있다. 게임 종료 시점까지 점수를 최대화하는 것이 목표다.

마지막으로 바둑이 있다. 딥마인드의 알파고가 세계 최고 바둑기사가 된 것이다. 바둑에서는 게임을 이기는 것이 목표다. 바둑을 둘 수 있는 모든 자리가 상태(state)이다. 행동은 다음 수를 두는 것이고, 게임을 이겼을 경우에만 보상이 주어진다.

Markov Decision Process

강화학습을 수학적으로 나타내면 다음과 같다.

앞서 본 것처럼 환경(environment)은 에이전트(agent)에게 상태(state)를 부여한다. 그러면 에이전트는 행동을 취한다. MDP(Markov Decision Process)를 통해 강화학습 문제를 수식화시킬 수 있다.

MDP는 Markov property를 만족한다. Markov Property란 현재 상태만으로 전체 상태를 나타내는 성질이다. 그리고 MDP는 몇 가지 속성으로 정의할 수 있는데,

• S: 가능한 상태들의 집합
• A: 가능한 행동들의 집합
• R: (state, action)쌍이 주어졌을 때 받게되는 보상의 분포 - (state, action)이 보상으로 매핑되는 함수
• P: 전이확률(transition probability) - (state, action)쌍이 주어졌을 때 전이될 다음 상태에 대한 분포
• γ: 보상을 받는 시간에 대해 우리가 얼마나 중요하게 생각할 것인가

작동 방식은 다음과 같다.

1. 처음 time step인 t=0이다. 환경은 초기 상태 분포인 p(s_0)에서 s_0를 샘플링한다.
2. t=0에서부터 완료 상태가 될 때까지 반복한다.
   • 에이전트가 행동 a_t를 선택
   • 환경은 어떤 분포로부터 보상을 샘플링(보상은 우리의 상태와 우리가 택한 행동이 주어졌을 때의 보상)
   • 환경은 다음 어떤 분포에서 상태 s_t+1을 샘플링
   • 에이전트는 보상과 다음 상태를 받는다.
   • 에피소드가 종료될 때까지 이를 반복한다.

또한, 정책(polity) π를 정의할 수 있다. 정책은 각 상태에서 에이전트가 어떤 행동을 취할지를 명시해주는 기능을 수행한다. 정책은 확률적인 값일 수도 있고, 명확한 값일 수도 있다.

우리의 목적은 최적의 정책 π*을 찾는 것이다. 즉, 누적 보상(cumulative discounted reward)를 최대화시키는 것이다.

보상에는 미래에 얻을 보상도 포함되는데, 이 보상은 discount factor에 의해 할인된 보상으로 얻게 된다.

간단한 MDP 예제가 있다. 격자로 된 grid world가 있다. 이 곳에서 테스크를 수행할 것이므로 이 것이 상태이자 환경이다. 여기서 격자 중 어디로든 이동할 수 있다. 우리는 상태에 따라 행동을 취할 수 있다. 행동은 상/하/좌/우로 움직이는 것이다. 우리는 한 번 움직일 때마다 음의 보상을 받게 된다. 가령 r = -1이 될 수도 있다.

우리의 목표는 회식으로 칠해진 종료 상태를 최소한의 행동으로 도달하는 것이다. 종료 상태에 도달하는 시간이 길수록 음의 보상은 점점 쌓인다.

먼저 random policy에서는 기본적으로 어떤 방향으로 움직이든 무작위로 방향을 결정한다. 모든 방향이 동일한 확률을 갖는다.

하지만, 일련의 학습을 거쳐 얻게될 optimal policy의 경우 점점 더 종료 상태에 가까워지도록 만드는 적절한 방향을 선택해서 행동을 취하게 된다. 종료 상태 바로 주변에 위치하는 경우라면 종료 상태로의 방향으로 이동하도록 하는 것이다. 종료 상태와 먼 곳에 있더라도 가장 가깝게 이동할 수 있는 방향으로 이동한다.

이렇게 MDP를 정의하고 나면 최적의 정책인 π*를 찾아야 한다. 최적의 정책은 보상의 합을 최대화시킨다. 최적의 정책은 우리가 어떤 상태에 있더라도 그 상황에서 보상을 최대화시킬 수 있는 행동을 알려준다.

Q-Learning

MDP에서 발생하는 무작위성(randomness)는 어떻게 다뤄야 할까?

초기 상태를 샘플링할 시 무작위성이 있고, 전이 확률 분포의 경우에도 다음 상태는 확률적이다. 이를 위해서는 보상의 합에 대한 기댓값을 최대화시키면 된다.

수식적으로 보면, 최적의 정책 π*는 정책 π에 대한 미래의 보상들의 합의 기댓값을 최대화시키는 것이다.

초기 상태(s_0)는 어떤 상태 분포를 따르고, 우리가 취하는 행동은 어떤 상태가 주어졌을 때 정책이 가지는 분포로부터 샘플링된다. 또한, 다음 상태는 전이 확률 분포로부터 샘플링된다.

사용하게 될 정의들을 먼저 살펴보자.

우리가 정책을 따라 무언가를 수행하게 되면 결국은 모든 에피소드마다 어떤 경로를 얻게 될 것이다. 초기 상태인 s_0,a_0,r_0부터 시작해서 s_1,a_1,r_1 … s_2,a_2,r_2 이런 식으로 나아갈 것이다. 그렇게 되면 우리가 얻을 수 있는 상태(s), 행동(a), 보상(r)들의 하나의 경로가 생기게 된다.

임의의 상태 s에 대한 가치함수는 상태 s와 정책 π가 주어졌을 때 누적 보상의 기댓값이다.

그렇다면 (state, action)쌍이 얼마나 좋은지 알 수 있는 방법은 Q-value function을 통해 정의할 수 있다. Q-value function은 정책 π, 행동 a, 상태 s가 주어졌을 때 받을 수 있는 누적 보상의 기댓값이다. 최적의 Q-value function인 Q*은 (state, action) 쌍으로부터 얻을 수 잇는 누적 보상의 기댓값의 최대값이다.

강화학습에서 중요한 요소 중 하나인 벨만 방정식(bellman equation)을 살펴보도록 하자.

우선 최적의 정책으로부터 나온 Q-value function인 Q*가 있다고 할 때, Q*는 벨만 방정식을 만족한다. 이는 어떤 (s,a)이 주어지던 간에 현재 (s,a)에서 받을 수 있는 r 과 에피소드가 종료될 s’까지의 보상을 더한 값이다.

여기에서는 우리가 이미 최적의 정책을 알고 있기 때문에 s’에서 우리가 할 수 있는 최상의 행동을 취할 수가 있다. s’에서의 Q*의 값은 우리가 현재 상태에서 취할 수 있는 모든 행동중에 Q*(s’,a’)를 최대화시키는 값이 된다. 이를 통해 최적의 Q값을 얻는다.

우리는 어떤 상태인지에 대한 무작위성이 존재하므로 기댓값을 취한다. 또한, Q*를 통해 특정 상태에서의 최상의 행동을 취할 수 있는 최적의 정책을 구할 수 있다. Q*는 어떤 행동을 취했을 때 미래에 받을 보상의 최대치다. 그러므로 우리는 그저 Q*에 대한 정책을 따라 행동을 취하기만 하면 최상의 보상을 받을 수 있다.

최적의 정책을 구하는 방법은 value iteration algorithm이다. 반복적인 업데이트를 위해 벨만 방정식을 사용할 것이다. 벨만 방정식을 통해 각 스텝마다 Q*를 조금씩 최적화시킨다. 수학적으로 보면 Q_i의 i가 무한대일 때, 최적의 Q*로 수렴한다.

하지만 여기서 문제가 있다. 이 방법은 scalable하지 않다는 것이다. 반복적으로 업데이트하기 위해서는 모든 (state, action)마다 Q(s)를 계산해야 한다. 예를 들어, 아타리 게임의 경우 스크린에 보이는 모든 픽셀이 상태가 된다. 이 경우 상태 공간이 매우 크며 기본적으로 전체 상태 공간을 계산하는 것은 불가능하다.

그래서 우선 neural network를 사용하여 함수 Q(s,a)를 근사시킨다. 앞서 배웠듯 복잡한 함수를 추정하고 싶을 때는 neural network를 사용했다.

여기에서는 행동 가치 함수를 추정하기 위한 함수 근사를 이용할 것이다. 함수 근사로는 deep neural network를 사용할 것이고, 이를 deep Q-learning이라 한다.

deep Q-Learning은 강화학습하면 빠지지 않고 등장하는 방법이다. 여기에서는 함수 파라미터 ϴ가 있다. ϴsms neural network의 가중치다.

Q-function은 벨만 방정식을 만족해야 한다. 그렇다면 해야할 일은 neural network로 근사시킨 Q-function을 학습시켜 벨만 방정식의 에러를 최소화시켜야 한다. 손실 함수는 q(s,a)가 목적 함수와 얼마나 멀리 떨어져 있는지 측정한다. 여기 보이는 y_i가 바로 앞서 살펴본 벨만 방정식이다.

forward pass에서는 손실 함수를 계산한다. 손실이 최소로 만든다. backward pass에서는 계산한 솔실을 기반으로 파라미터 ϴ를 업데이트한다.

이런식으로 반복적인 업데이트를 통해 Q-function이 타겟과 가까워지도록 학습시킨다.

deep Q-learning이 적용된 아타리 게임을 살펴보자. 게임의 목적은 동일하게 최대한 높은 점수를 획득하는 것이다. 상태는 게임의 픽셀이 그대로 사용되고, 행동도 상/하/좌/우로 동일하다. 게임이 진행됨에 따라 매 time-step마다 점수가 늘어나거나 줄어듬에 따라 보상을 얻는다. 스코어를 기반으로 전체 누적 보상을 계산할 수 있다.

Q-function에 사용한 네ㅡ워크는 다음과 같이 생겼다. Q-network는 가중치 ϴ를 가진다. 네트워크의 입력은 상태 s, 즉 현재 게임 스크린의 픽셀들이다. 실제로는 4프레임 정도 누적시켜 사용한다. 입력을 grayscale로 변환, downsampling, cropping 등의 전처리 과정을 거친다. 전처리를 거친 입력은 4프레임씩 묶어 84x84x4의 형태가 된다.

그 다음으로는 컨볼루션, FC-layer들로 구성된다. FC-layer의 출력 벡터는 네트워크의 입력인 상태가 주어졌을 때 각 행동의 Q-value이다. 가령 네 가지 행동이 존재하면 출력도 4차원이다. 이는 현재 상태 s_t와 여기에 존재하는 행동들 a_1,a_2,a_3,a_4에 대한 Q값들이다. 각 행동들마다 하나의 스칼라 값인 Q를 얻는다.

참고로 행동의 수는 아타리 게임의 종류에 따라 4~18가지로 변할 수 있다.

이런 네트워크의 장점은 한 번의 forward pass만으로 현재 상태에 해당하는 모든 함수에 대한 Q-value를 계산할 수 있다. 현재 상태의 각 행동들에 각각 Q-value가 존재할텐데 현재 상태를 네트워크의 입력으로 넣어주기만 하면 모든 Q-value를 한번에 forward pass로 계산하는 것이다.

이 네트워크를 학습시키기 위해서는 손실 함수가 필요하다.neural netowork로 근사시킨 함수도 벨만 방정식을 만족해야 한다. 따라서 네트워크의 출력인 Q-value가 타겟 값과 가까워지도록 반복적으로 학습시켜야 한다.

여기 알아야 할 개념이 있다. experience replay는 Q-network에서 발생할 수 있는 문제들을 다룬다. 첫번째로, Q-network를 학습시킬 때 하나의 배치에서 시간적으로 연속적인 샘플들로 학습하면 안좋다. 그렇게 되면 모든 샘플들이 상관관계를 가지게 되어 비효율적이다.

두번째로, 현재 Q-network 파라미터를 생각해보면 네트워크는 우리가 어떤 행동을 해야할지에 대한 정책을 결정한다는 것은 우리가 다음 샘플들도 결정하게 된다는 의미다. 이는 학습에 안좋은 영향을 미칠 수 있다. 예를 들어, 현재 상태에서 왼쪽으로 이동하는 것이 보상을 최대화하는 행동이라고 하면, 결국 다음 샘플들도 전부 왼쪽에서 발생할 수 있는 것들로만 편향된다.

이 두 가지를 해결하기 위해 experience replay라는 방법을 사용한다.

이 방법은 replay memory를 이용한다. replay memory에는 (상태, 행동, 보상, 다음상태)로 구성된 전이 테이블이 있다. 게임 에피소드를 플레이하면서 더 많은 경험을 얻음에 따라 전이 테이블을 지속적으로 업데이트시킨다. 여기에는 replay memory에서의 임의의 미니배치를 이용하여 Q-network를 학습시킨다. 연속적인 샘플을 사용하는 대신 전이 테이블에서 임의로 샘플링된 샘플을 사용하는 것이다.

이 방식을 통해 상관관계를 해결할 수 있다. 추가적인 이점으로 각각의 전이가 가중치 업데이트에 여러 차례 기여할 수 있다는 것이다. 전이 테이블로부터 샘플링을 하면 하나의 샘플도 여러번 뽑힐 수 있다. 이를 통해 데이터 효율이 훨씬 증가한다.

이제 experience replay를 적용한 Q-learning 알고리즘을 살펴보자.

1. replay memory를 초기화한다. memory 용량은 N으로 지정한다. 그리고 Q-network를 임의의 가중치로 초기화시킨다.
2. 에피소드는 M번 진행할 것이다. 즉 학습을 M번 한다. 그리고 각 에피소드마다 상태를 초기화시켜야 한다.
3. 상태는 게임 시작 픽셀이 된다. 앞서 언급한 입력 상태를 만들기 위한 전처리 과정을 진행하고, 게임이 진행중인 매 time-stpe마다 임의의 행동을 취한다. 이는 충분한 탐사를 위해 중요하다.
4. 이를 통해 다양한 상태 공간을 샘플링한다. 낮은 확률로 임의의 행동을 취하거나 현재 정책을 따라 행동을 취한다. 즉, 대부분은 현재 상태에 적합하다고 판단되는 행동을 취하지만, 가끔씩은 임의의 행동을 선택한다.
5. 이렇게 행동 a_t를 취하면 보상(r_t)와 다음 상태(s_t+1)를 얻는다.
6. 그 후 전이(transition)(s_t,a_t,r_t,s_t+1)을 replay memory에 저장한다.
7. 이제 네트워크를 학습할 것이다. 학습에는 experience replay를 이용할 것이다. replay memory에서 임의의 미니배치 전이들을 샘플링한 다음 이를 이용해 업데이트한다.

게임을 진행하는 동안 experience replay를 이용하여 미니배치를 샘플링하고, 이를 통해 Q-network를 학습시킨다.

google deepmind에서 atari 게임을 q-learning으로 학습시키는 영상의 주소는 참고용으로 넣었다.

지금까지 Q-learning을 살펴보았다. Q-learning에 문제가 존재하는데, 그것은 Q-funciton이 매우매우 복잡하다는 것이다. Q-learning에서는 모든 (state, action) 쌍들을 학습해야만 한다. 그런데 만약, 로봇이 어떤 물체를 손에 쥐는 문제를 풀어야 한다고 가정할 때, 이는 아주 고차원의 상태 공간이다. 또, 로봇의 모든 관절의 위치와 각도가 이룰 수 있는 모든 경우의 수를 생각해볼 수 있을 것이다.

따라서 이 모든 (s,a)를 학습시키는 것은 아주 어려운 문제다. 반대로 정책은 간단해질 수 있다. “손을 움켜쥐는 것”과 같이 말이다. 그렇다면 손가락을 특정 방향으로만 움직이도록 하면 된다.

Policy Gradients

그렇다면 정책 자체를 학습시킬 수 있을까?

그것이 가능해진다면 여러 정책들 가운데 최고의 정책을 찾아낼 수 있다. 정책을 결정하기에 앞서 Q-value를 추정하는 과정을 거치지 않고도 말이다. 이러한 접근 방식이 policy gradients 이다.

이를 수식적으로 매개변수화된 정책을 정의해보자. 정책들은 가중치 ϴ에 의해 매개변수화된다.

각 정책에 대해 정책의 값을 정의하면 사진 속 아래 식과 같다. J(ϴ)는 미래에 받을 보상들의 누적 합의 기댓값으로 나타낼 수 있다. 이는 우리가 지금까지 사용했던 보상과 동일하다.

이런 상황에서 우리가 하고 싶은 것은 최적의 정책인 ϴ*를 찾는 것인데, 이는 argmaxJ(ϴ)로 찾을 수 있다.

이를 통해 보상의 기댓값을 최대로 하는 정책 파라미터를 찾으면 된다. policy parameter에 대해 gradient ascent를 수행하면 된다. ascent를 통해 parameter를 연속적으로 업데이트하면 된다.

좀 더 구체적으로 살펴보자

REINFORCE 알고리즘을 보면, 경로에 대한 미래 보상의 기댓값으로 나타낼 수 있다.

이를 위해서 경로를 샘플링해야 하는데, 이는 앞서 배운 s_0,a_0,r_0,s_1 등이 된다. 이들은 어떤 정책 π_ϴ을 따라 결정될 것이다. 그러면 각 경로에 대해 보상을 계산할 수 있고, 그 보상은 우리가 어떤 경로를 따라 얻을 수 있는 누적 보상이 될 것이다.

따라서 정책인 π_ϴ의 값은 샘플링된 경로로부터 받게 될 보상의 기댓값이 될 것이다.

gradient ascent를 수행해야 한다. J(ϴ)를 미분하면 위의 식과 같다. 하지만 여기서 문제가 있다. 미분을 했지만, 이 값은 계산할 수가 없다. p가 ϴ에 종속되어 있는 상황에서 기댓값 안에 gradient가 있으면 문제가 될 수 있다. 위의 식을 보면 p(τ;ϴ)에 대한 gradient를 구해야 하는데 τ에 대한 적분을 계산하기 어렵다.

이를 해결하기 위해 분모분자에 p(τ;ϴ)를 곱해준다. 그리고 log(p)의 gradient는 (1/p)*p의 gradient와 같기 때문에 바꿀 수 있다.

이렇게 바꾸고 나서 원래의 gradient식에 대입하게 되면, log(p)에 대한 gradient를 모든 경로에 대한 확률과 곱하는 꼴이 되고, 이를 τ에 대해서 적분하는 꼴이 되기 때문에, 이는 다시 경로 τ에 대한 기댓값의 형식으로 바꿀 수 있다.

처음에는 기댓값에 대한 gradient를 계산하려 했지만, 이제는 gradient에 대한 기댓값으로 바꾼 셈이다.

이와 같은 방법을 통해 gradient를 추정하기 위해 경로들을 샘플링하여 사용할 수 있게 되었다. 이로 인해 monte carlo 샘플링을 할 수 있다.

좀 더 자세히 살펴보자.

p(τ;ϴ)를 전이확률을 모른 채 계산할 수 있을까?

우선 p(τ)는 어떤 경로에 대한 확률이다. 이는 현재 (state, action)이 주어졌을 때, 다음에 얻게될 모든 상태에 대해 전이확률과 정책 π로부터 얻은 행동에 대한 확률의 곱의 형태로 이루어진다. 이를 모두 곱하면 경로에 대한 확률을 얻어낼 수 있다.

그렇다면 log(p;τ)의 경우를 보면 앞서 곱했던 것들이 모두 합의 형태로 바뀌게 될 것이다.

log(p)를 θ에 대해 미분하는 경우 첫번째항인 전이확률은 θ와 무관하다. 두번째 항인 logπ_θ(a_t|s_t)만이 θ와 관련이 있다. 따라서 gradient를 계산할 때 전이확률은 필요하지 않다. 따라서 우리는 어떤 경로 τ에 대해서도 gradient를 기반으로 J(θ)를 추정할 수 있다.

지금까지는 하나의 경로만 고려했었지만 기댓값을 계산하기 위해서는 여러 개의 경로를 샘플링할 수도 있다.

gradient계산을 위해 어떤 경로로부터 얻은 보상이 크다면, 즉 일련의 행돌들이 잘 수행한 것이라면 일련의 행동들을 할 확률을 높혀준다. 그 행동이 좋은 선택이었다는 것을 알려주는 것이다.

반면 어떤 경로에 대한 보상이 낮다면 해당 확률을 낮춘다. 이런 행동이 좋지 않은 행동이었으며 따라서 그 경로가 샘플링되지 않게 하기 위해서다.

여기 수식을 보면 π(a

s)는 우리가 취한 행동들에 대한 likelihood이다. 파라미터를 조정하기 위해 gradient를 사용할 것이고, gradient는 likelihood를 높히기 위해 어떻게 해야 하는지를 알려준다. 이것은 우리가 받게될 보상, 즉 행동들이 얼마나 좋았는지에 대한 gradient를 통해 파라미터를 정하는 것을 의미한다.

어떤 경로가 좋았다면, 그 경로에 포함되었던 모든 행동이 좋다고 판단한다. 기댓값에 의해 이 모든 것들이 averages out된다. averages out을 통해 unbiased estimator를 얻을 수 있고, 충분히 많은 샘플링을 한다면 gradient를 잘 이용해서 정확하고 좋은 estimator을 얻읋 수 있다.

이 방법이 좋은 이유는 gradient를 잘 계산한다면 손실 함수를 작게 만들 수 있고, 정책 파라미터 θ에 대한 local optimum을 구할 수 있기 때문이다.

하지만, 여기서도 문제가 존재한다. 문제의 원인은 높은 분산이다. 왜냐하면 신뢰할당문제(credit assignment)가 아주 어렵기 때문이다. 일단 보상을 받았으면 해당 경로의 모든 행동들이 좋았다는 정보만 알려줄 것이다. 하지만 우리는 구체적으로 어떤 행동이 최선이었는지를 알고 싶지만, 이 정보는 average out된다. 그래서 구체적으로 어떤 행동이 좋았는지 알 수가 없기에 좋은 추정를 위해서는 샘플링을 충분히 해야만 한다.

이 문제는 결국 분산을 줄이고, 추정의 성능을 높이기 위해서는 어떻게 해야 하는지에 대한 질문으로 귀결된다.

분산을 줄이는 것은 policy gradient에서 아주 중요하다. 샘플링을 더 적게 하면서도 추정의 성능을 높일 수 있어서다.

Variance Reduction

그래서 이를 해결할 수 있는 방법들을 살펴보고자 한다.

첫번째 아이디어는 해당 상태로부터 받을 미래의 보상만을 고려하여 어떤 행동을 취할 확률을 키워주는 방법이다. 이 방법은 해당 경로에서 얻을 수 있는 전체 보상을 고려하는 대신 현재부터 종료 시점까지 얻을 수 있는 보상의 합을 고려하는 것이다. 이 방법이 의도하는 바는 어떤 행동이 발생시키는 미래의 보상이 얼마나 클지를 고려하겠다는 말이다.

두번째 방법은 지연된 보상에 대해 할인률을 적용하는 것이다. 수식을 보면 할인률이 추가되어 있다. 할인율이 의미하는 바는 당장 받을 수 있는 보상과 조금 더 늦게 받은 보상간의 차이를 구별하는 것이다. 어떤 행동이 좋은 행동인지 아닌지를 해당 행동에 가까운 곳에서 찾는다. 나중에 수행하는 행동에 대해서는 가중치를 조금 낮춘다.

• Baseline

경로에서부터 계산된 값을 그대로 사용하는 것은 문제가 있다. 그런 값들 자체가 반드시 의미가 있는 값은 아닐 수 있기 때문이다. 보상이 모두 양수이기만 해도 행동들에 대한 확률이 계속 커지기만 할 수도 있다. 나름 의미가 있을 수 있지만, 정말 중요한 것은 얻은 보상이 우리가 얻을 것이라 예상했던 것보다 더 좋은지, 아닌지를 판단해야 한다. 이를 위해 baseline function을 사용한다.

baseline 함수가 말하는 것은 해당 상태에서 우리가 얼마만큼의 보상을 원하는지이다. 그렇게 되면 확률을 키우거나 줄이는 보상 수식이 바뀌지만, 이를 수식에 적용하면 미래에 얻을 보상들의 합을 특정 기준이 되는 값(baseline)에서 값을 빼주는 형태가 되고, 이를 통해 우리가 기대했던 것에 비해 보상이 어떤지를 확인할 수 있다.

baseline을 어떻게 선택하면 좋을까?

가장 단순한 것은 에피소드를 수행하는 학습 과정에서 지금까지 봤던 모든 경로들에 대해 보상이 어땠는지에 대한 평균을 낸다. 이를 통해 현재 보상에 대해 좋은지, 나쁜지 알 수 있다.

위의 variance reduction 방법들을 vanilla REINFORCE라고 한다. 할인율을 적용하여 미래에 받을 보상을 누적시키고 여기에 단순한 baseline을 추가한다.

baseline의 주요 아이디어와 더 좋은 baseline을 선택하는 방법에 대해 살펴보자.

우선 더 좋은 baseline이란 어떤 것일까?

우리는 어떤 행동이 그 상태에서의 기댓값보다 좋은 경우에는 해당 상태에서 그 행동을 수행할 확률이 크길 원한다. 그럼 그 상태로부터 기대할 수 있는 값이라 하면, 앞서 Q-learning에서 배운 value function을 이용할 수 있다.

어떤 상태 s에서 어떤 행동을 취했을 때 어떤 조건을 만족하면 그 행동이 좋았다고 판단한다. 그 조건은 어떤 상태에서 특정 행동을 했을 때 얻을 수 있는 Q-value가 그 상태에서 얻을 수 있는 미래의 받을 누적 보상들의 기댓값이라는 가치함수보다 더 큰 경우를 의미한다. 이는 그 행동이 우리가 선택하지 않은 다른 행동들보다 더 좋았다는 것을 의미한다. 반대로 그 차이 값이 음수거나 작은 경우 안 좋은 행동을 취했다는 것을 의미할 것이다.

이를 추정(estimator) 수식에 적용해보면, 수식 자체는 같지만, 의미하는 바는 현재 행동이 얼마나 좋은 행동이었는지를 해당 상태에서의 Q-function과 value function의 차이를 통해 나타낸다.

하지만 우리가 지금까지 살펴본 REINFORCE 알고리즘에서는 Q-function과 value function을 구하지 않았다.

그러나, 우리는 policy gradient와 Q-learning을 조합해서 모델을 학습시킬 수 있다.

여기 actor가 policy이고, critic이 Q-function이라 하고, 이들은 어떤 상태가 얼마나 좋은지, 그리고 상태에서의 어떤 행동이 얼마나 좋았는지를 말해준다.

actor-critic 알고리즘에서 actor는 어떤 행동을 할지 결정한다. 그리고 critic은 그 행동이 얼마나 좋았으며, 어떤 식으로 조절해 나가야 하는지를 알려준다.

기존의 Q-learning에서는 모든 (상태, 행동)쌍에 대한 Q-value를 학습해야만 했지만, 여기서는 policy가 만들어낸 (상태, 행동)쌍에 대해서만 학습시키면 된다.

왼쪽 사진의 식을 보면 Q(s,a) - V(s)를 보상함수로 나타낸다. 즉, 보상함수는 어떤 행동을 했을 때 얼마나 많은 보상이 주어지는지를 나타낸다. 행동이 예상했던 것 보다 얼마나 더 좋은지를 나타내는 것이다.

직접 알고리즘을 보면,

1. policy 파라미터인 θ와 critic 파라미터인 π를 초기화시킨다.
2. 매 학습마다 현재의 정책을 기반으로 M개의 경로를 샘플링한다. policy에 기반해서 경로인 (s_0,a_0,r_0,s_1…)를 뽑아내는 것이다.
3. 각 경로마다 보상 함수에 대한 gradient를 계산하고 이를 전부 누적시킨다.
4. critic 파라미터인 π를 학습시키기 위해 가치 함수를 학습시켜야 한다. 보상 함수를 최소화시키는 것과 같다. 이를 통해 가치 함수가 벨만 방정식에 근사하도록 학습시킨다.
5. 이런 식으로 policy function(actor)과 critic function을 반복적으로 학습시킨다. gradient도 반복적으로 업데이트시킨다.

REINFORCE를 활용한 몇 가지 예제를 살펴보자

우선 RAM(Recurrent Attention Model)이 있다. 우선 hard attention에 대해 말하고자 하는데, image classifiction과 관련있는 이미지 클래스를 분류하는 문제이나 이미지의 일련의 glimpses(순간)를 가지고만 예측해야 한다. 이미지 전체가 아닌 지역적인 부분만 본다는 것이다. 어떤 부분을 볼지를 선택할 수 있다.

이런 식의 접근 이유는 우리가 복잡한 이미지를 볼 때의 방식을 본땄다. 또한, 이런 식의 지역적인 부분만 살펴보면 이미지 전체를 처리할 필요가 없기에 계산을 절약할 수 있다. 그리고, 이 방법은 실제로 classification 성능을 높혀주기도 한다. 이 방법을 사용하면 필요없는 부분을 무시할 수 있기 때문이다.

이 문제를 강화학습 수식으로 살펴보자.

우선 상태(state)는 지금까지 관찰한 glimpses이다. 우리가 지금까지 얻어낸 정보라고 할 수 있다. 행동(action)은 다음에 이미지 내에 어떤 부분을 볼지를 선택하는 것이다. 실제로는 다음 스텝에서 보고 싶은 고정된 사이즈의 glimpse의 중간 x-y좌표가 될 수 있다.

강화학습에서 분류 문제를 풀 때 보상은 최종 스텝에서 1인데, 이미지가 올바르게 분류되면 1, 그렇지 않으면 0이다.

이 문제에서 강화학습이 필요한 이유는 이미지에서 glimpse를 뽑아내는 것은 미분이 불가능한 연산이기 때문이다. 어떻게 glimpse를 얻어낼 것인지를 REINFORCE를 통해 학습한다.

누적된 glimpses가 모델에 주어지고, 여기에서는 상태를 모델링하기 위해 RNN을 이용한다. 그리고 policy 파라미터를 이용해 다음 action을 선택하게 된다.

전체 과정을 보게 되면

1. 입력 이미지가 들어온다.
2. 이미지에서 glimpse를 추출한다.
3. 추출된 glimpse는 neural network를 통과한다.(모델은 태스크에 따라 달라질 수 있다.)
4. RNN을 이용해서 지금까지 있었던 glimpses를(state) 전부 결합시켜 준다.

neural network의 출력은 x-y 좌표다. 실제로는 출력 밧이 행동에 대한 분포의 형태이고, 이 분포는 가우시안 분포를 따르며 결국 출력 값은 분포의 평균이 될 것이다. 평균과 분산을 모두 출력하는 경우도 있고, 분산은 고정된 값으로 설정하기도 한다.

이 분포로부터 특정 x,y 위치를 샘플링하여 x-y좌표를 이용해서 다음 glimpse를 얻어낸다. 이것을 반복하여 여러 개의 glimpse를 누적시켜 RNN을 이용하여 policy를 모델링한다. RNN 모델은 다음 위치의 glimpse에 대한 분포를 추출한다.

이 과정을 6~8번 반복한다. 마지막에는 분류를 위해 softmax를 통해 각 클래스 확률 분포를 출력한다.

hard attention이라는 방법은 다양한 컴퓨터 비전에 사용된다. 계산 효율이 좋고, 이미지 내의 불필요한 정보들을 무시할 수 있기 때문이다.

지금까지는 policy gradient를 활용한 hard attention의 예시를 보았다. 이제는 policy gradient를 이용한 방법을 살펴보자

바둑을 학습시키는 모델이다. Deepmind에는 알파고라는 바둑을 두는 에이전트가 있다. 알파고에는 지도학습과 강화학습이 섞여 있다. 또한 monte carlo tree search와 같은 방식과 deep RL 방법도 섞여 있다.

작동 방식

1. 입력 벡터를 만들어야 한다. 바둑판과 바둑 돌의 위치와 같은 요소들을 특징화시켜 알파고의 입력으로 사용한다. 이는 상태를 설계하는 아주 좋은 방법이다.
2. 성능 향상을 위해 바둑 돌의 색에 따라 채널을 따로 만들기도 했다.
3. 네트워크를 학습시킨다. 네트워크는 프로 바둑기사의 기보를 지도학습으로 학습시킨다. 바둑판의 현재 상태가 주어지면 행동을 어떻게 취할지를 결정한다.
4. policy network를 초기화한다. policy network는 바둑판의 상태를 입력으로 받아서 어떤 수를 둬야하는지를 반환한다. 지금까지의 policy gradient는 이런 식으로 동작한다.
5. 알파고는 임의의 이전 반복에서의 자기 자신과 대국을 두며 학습을 진행한다. 스스로 대국을 둬서 이기면 보상 1을 받고, 지면 -1의 보상을 받는다.
6. 앞서 배운 critic network를 통해 value network도 학습해야 한다.

알파고가 다음 수를 어디에 둬야 할지는 value function과 MCTS로 계산된 값의 조합으로 결정된다.

Summary

• policy gradient => gradient descent/ascent를 통해 policy 파라미터를 업데이트
• 높은 분산을 처리하기 위해 Q-learning을 적용한다.

Reference

• http://cs231n.stanford.edu/slides/2017/cs231n_2017_lecture14.pdf