Policy based 강화학습: Policy Gradient with REINFORCE

1. Policy-based 강화학습

지금까지 소개했던 Monte Carlo, Temporal Difference, DQN 등과 같은 알고리즘들은 모두 가치 함수 Q를 추정하고 그로부터 policy를 greedy하게 유도하는 Value-based 강화학습이었다.

Policy-based RL은 \(V_\pi(s)\)나 \(Q_\pi(s|a)\)를 직접적으로 업데이트하며 학습하는 방식이 아닌 Policy \(\pi_\theta(a|s)\) 자체를 파라미터 \(\theta\)로 표현하고 해당 Policy가 받는 Expected Return값이 커지도록 학습한다.

이때 policy를 업데이트하는 대표적인 방법으로 Policy gradient를 이번 챕터에서 정리해보려 한다. Expected Return을 파라미터 \(\theta\)에 대한 목적 함수로 보고 그 gradient를 따라 \(\theta\)를 직접 조정하여 더 높은 Return을 주는 policy로 나아가는 방식이며 대부분의 Policy-based RL이 이 방법을 기반으로 policy를 학습한다.

2. Value-based 강화학습의 한계

Continuous action space를 처리하기 어렵다

위 DQN 구조를 예로 들면 각 action마다 Q값을 출력하는 노드가 하나씩 달려 있다. 그런데 action이 continuous하면 가능한 action이 무한히 많아져 output node도 무한해진다. 당연히 모든 Q값을 계산하는 것은 불가능하거나 비효율적이다.

차량의 속도를 정하는 action을 예로 들어보자. 속도가 0부터 100km/h 사이라면 0, 1, 1.999, 1.999999 처럼 값을 얼마든지 잘게 쪼갤 수 있어 action이 무한해지고 이 모든 값에 대한 Q값을 다 추정할 수는 없다. 이를 해결하려고 연속 구간을 잘라 discrete하게 만드는 quantization 방법도 있지만 한계가 있다. 구간을 크게 나누면 해상도가 떨어진다. 예시로 0부터 10을 하나의 action으로 묶어버리면 정작 그 안에서 어떤 속도를 고를지는 결국 랜덤이 되어버린다.

결국 자율주행이나 로봇처럼 현실 세계의 문제는 discrete action보다 continuous action problem이 훨씬 많고 이런 문제를 Value-based로는 다루기 어렵다.

Stochastic policy를 표현할 수 없다

Value-based의 greedy policy는 학습이 끝나면 현재 state에서 항상 같은 action을 고르는 deterministic policy가 될 수밖에 없다. 이게 왜 문제냐?

포커를 예로 들어보자. 내가 좋은 패일 때만 베팅하고 나쁜 패일 때는 죽는 deterministic policy를 쓴다고 하면 상대는 내가 베팅을 하면 "아 저놈 패 좋네"를 알거고 반대로 베팅을 안하면 "아 저놈 패 썩었구나"를 알게되서 결국 한 푼도 못 먹는다. 그래서 가끔은 나쁜 패로도 베팅하는 블러핑을 섞고 반대로 좋은 패를 죽이는 척도 해야 한다. 이때 최적 전략은 어떤 상황에서 베팅을 몇 % 블러핑을 몇 % 섞을지라는 확률 그 자체다. 즉 최적 policy가 본질적으로 확률적이고 이건 deterministic policy로는 표현할 수 없다. 게다가 상대에게 읽히는 순간 지기 때문에 관측을 아무리 좋게 만들어도 이 문제는 사라지지 않는다.

개인적으로 stochastic policy가 이 state에서 저런 action도 해본다라는 점이 \(\epsilon\)-greedy 탐색과 비슷해 보였었다. 하지만 \(\epsilon\)-greedy는 일단 continuous action에서는 쓸 수 없고 탐색할 때 현재 policy와 무관한 완전히 새로운 action을 고르기 때문에 엄연히 다르다. stochastic policy는 action을 하나의 distribution으로 모델링해서 평균이 되는 가장 가치 높은 action 주변을 표준편차 \(\sigma\) 폭만큼 탐색한다.

Policy가 불연속적으로 바뀌어 불안정하다

Value-based는 \(Q\)값이 조금만 바뀌어도 \(\arg\max\)가 다른 action으로 튀면서 policy가 불연속적으로 확 바뀐다. 이 때문에 학습이 진동하거나 발산하기도 한다. Policy-based는 이런 불연속 문제 없이 policy를 부드럽게 바꿔갈 수 있는데 어떻게 가능한지는 아래에서 설명한다.

결국 Policy-based RL은 앞의 세 가지 문제를 보완한 강화학습 방식이다. 확률적 policy를 사용해 action을 직접 고르는 대신 action에 대한 distribution을 학습하기 때문에 포커처럼 본질적으로 확률적인 최적 policy도 그대로 표현할 수 있다. 또 action을 분포로 내보내므로 모든 action의 Q값을 일일이 추정할 필요 없이 continuous action space도 자연스럽게 다룬다. 마지막으로 policy를 \(\theta\)로 직접 파라미터화하기 때문에 목적 함수를 \(\theta\)에 대해 미분할 수 있고 그 gradient를 따라 policy를 조금씩 부드럽게 업데이트할 수 있다. 이 미분을 가능하게 해주는 것이 바로 policy gradient이고 아래에서 자세히 정리한다.

3. Policy Gradient

이제 어떻게 Policy based RL이 policy를 부드럽게 업데이트하는지 수식으로 설명하려 한다.

Objective Function \(J(\theta)\)

위에서 Policy-based RL은 특정 action이 아니라 distribution 자체를 학습한다고 했다. 그래서 우리가 maximize할 대상도 하나의 action 가치가 아니라 policy \(\pi_\theta\)가 만들어내는 trajectory \(\tau\) 전체의 Expected Return이다. 즉 이 Expected Return을 maximize하는 \(\theta\)를 찾는 것이 목표다.

여기서 trajectory \(\tau\)는 policy \(\pi_\theta\)를 따라 에피소드를 끝까지 진행했을 때 나오는 state·action·reward의 시퀀스다.

\[ \tau = (s_0, a_0, r_1, s_1, a_1, r_2, \ldots, s_T) \]

그리고 \(J(\theta)\)는 이 trajectory가 주는 누적 보상 \(R(\tau)\)의 기댓값이다.

\[ J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\big[ R(\tau) \big], \qquad R(\tau) = \sum_{t=0}^{T-1} \gamma^t r_{t+1} \]

\(J(\theta)\)를 maximize해야 하므로 \(J(\theta)\)가 커지는 방향 즉 gradient 방향으로 \(\theta\)를 조금씩 올리는 gradient ascent를 사용한다.

\[ \theta \leftarrow \theta + \alpha \nabla_\theta J(\theta) \]

여기서 \(\alpha\)는 learning rate다.

Policy Gradient Theorem (REINFORCE)

우선 기울기 \(\nabla_\theta J(\theta)\)는 다음과 정의된다.

\[ \nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[ \left( \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t) \right) R(\tau) \right] \]

그래서 이게 어떻게 gradient ascent가 되냐면 위 \(\nabla_\theta J(\theta)\)를 그대로 업데이트 식에 꽂으면 된다.

\[ \theta \leftarrow \theta + \alpha \left( \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t) \right) R(\tau) \]

그런데 원래 \(\nabla_\theta J(\theta)\)는 모든 trajectory에 대한 기댓값이라 실제로 전부 계산할 수는 없다. 그래서 policy \(\pi_\theta\)로 직접 에피소드를 굴려서 나온 trajectory 샘플로 그 기댓값을 근사한다. 위 식은 trajectory 하나로 근사한 경우이고 보통은 분산을 줄이려고 \(N\)개를 모아 평균을 낸다.

\[ \theta \leftarrow \theta + \alpha \frac{1}{N} \sum_{i=1}^{N} \left( \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t^{(i)} \mid s_t^{(i)}) \right) R(\tau^{(i)}) \]

이게 바로 REINFORCE다. 결국 policy로 에피소드를 굴려 trajectory와 그 Return \(R(\tau)\)를 모으고 Return이 큰 trajectory에서 했던 action들의 \(\log \pi_\theta\)를 키우는 방향으로 \(\theta\)를 업데이트하는 것을 반복한다.

Deriving the Policy Gradient

앞에서 결과만 적은 아래 식을 직접 유도해보자.

\[ \nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta(\tau)}\left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, R(\tau) \right] \]

1. \(J(\theta)\)의 정의에서 출발한다.

\[ J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta(\tau)}[R(\tau)] \]

연속 확률변수 \(X\)의 pdf가 \(p(x)\)일 때 \(f(X)\)의 기댓값은 \(\mathbb{E}_{x \sim p(x)}[f(X)] = \int_x p(x) f(x)\, dx\) 로 정의되므로 \(J(\theta)\)도 적분 형태로 쓸 수 있다.

\[ J(\theta) = \int \pi_\theta(\tau)\, R(\tau)\, d\tau \]

2. 양변에 미분을 적용한다.

\[ \nabla_\theta J(\theta) = \int \nabla_\theta \pi_\theta(\tau)\, R(\tau)\, d\tau \]

3. \(\pi_\theta(\tau)\)를 곱하고 나눈 뒤 정리한다.

\[ \nabla_\theta J(\theta) = \int \nabla_\theta \pi_\theta(\tau)\, \frac{\pi_\theta(\tau)}{\pi_\theta(\tau)}\, R(\tau)\, d\tau = \int \pi_\theta(\tau)\, \frac{\nabla_\theta \pi_\theta(\tau)}{\pi_\theta(\tau)}\, R(\tau)\, d\tau \]

4. log-derivative trick \(\dfrac{d}{dx} \log f(x) = \dfrac{f'(x)}{f(x)}\) 를 쓰면 \(\dfrac{\nabla_\theta \pi_\theta(\tau)}{\pi_\theta(\tau)} = \nabla_\theta \log \pi_\theta(\tau)\) 이고 다시 기댓값 형태로 묶을 수 있다.

\[ \nabla_\theta J(\theta) = \int \pi_\theta(\tau)\, \nabla_\theta \log \pi_\theta(\tau)\, R(\tau)\, d\tau = \mathbb{E}_{\tau \sim \pi_\theta(\tau)}\big[ \nabla_\theta \log \pi_\theta(\tau)\, R(\tau) \big] \]

5. 이제 \(\nabla_\theta \log \pi_\theta(\tau)\)를 구하면 된다. trajectory의 확률분포는 초기 상태 분포 \(p(s_0)\)와 policy \(\pi_\theta(a_t \mid s_t)\)와 전이 확률 \(p(s_{t+1} \mid s_t, a_t)\)의 곱으로 주어진다.

\[ \pi_\theta(\tau) = p(s_0) \prod_{t=0}^{T-1} \pi_\theta(a_t \mid s_t)\, p(s_{t+1} \mid s_t, a_t) \]

6. 양변에 log를 씌우면 곱이 합으로 바뀐다.

\[ \log \pi_\theta(\tau) = \log p(s_0) + \sum_{t=0}^{T-1} \big( \log \pi_\theta(a_t \mid s_t) + \log p(s_{t+1} \mid s_t, a_t) \big) \]

7. \(\theta\)로 미분하면 \(\theta\)와 무관한 \(\log p(s_0)\)와 \(\log p(s_{t+1} \mid s_t, a_t)\) 항은 0이 되어 사라지고 policy 항만 남는다.

\[ \nabla_\theta \log \pi_\theta(\tau) = \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t) \]

8. 이 결과를 4번 식에 다시 넣으면 최종 policy gradient를 얻는다.

\[ \nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta(\tau)}\left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, R(\tau) \right] \]

REINFORCE 알고리즘

이 알고리즘을 REINFORCE 또는 Monte Carlo policy gradient라고 부른다. 전체 루프는 다음과 같다.

1. policy network의 파라미터 \(\theta\)를 랜덤 값으로 초기화한다.
2. 현재 policy \(\pi_\theta\)를 따라 \(N\)개의 trajectory \(\{\tau^{(i)}\}_{i=1}^{N}\) 를 생성한다.
3. 각 trajectory의 Return \(R(\tau)\)를 계산한다.
4. gradient를 계산한다.
   \[ \nabla_\theta J(\theta) = \frac{1}{N} \sum_{i=1}^{N} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, R(\tau) \right] \]
5. gradient ascent로 파라미터를 업데이트한다.
   \[ \theta \leftarrow \theta + \alpha \nabla_\theta J(\theta) \]
6. 2~5번을 여러 번 반복한다.

4. REINFORCE의 한계 — 높은 분산

REINFORCE는 gradient \(\nabla_\theta J(\theta)\)의 분산(variance)이 매우 크다. 매 업데이트마다 gradient 추정값이 크게 출렁여서 학습이 느리고 불안정하다.

두 그래프 모두 평균인 점선은 같지만 왼쪽은 매번 뽑은 값이 평균에서 멀리 흩어지고 오른쪽은 평균 근처에 모여 있다. 이렇게 추정값이 평균에서 크게 퍼져 출렁이는 것이 분산이 크다는 의미다. 그럼 왜 분산이 큰지 이유를 하나씩 보자.

Return \(R(\tau)\)가 stochastic하다

에피소드마다 action 선택과 환경의 전이가 랜덤이라 같은 policy로 굴려도 매번 다른 \(R(\tau)\)가 나온다. 심지어 같은 state \(s_t\)에서 같은 action을 해도 그 이후 trajectory가 어떻게 흘러가느냐에 따라 \(R(\tau)\)가 천차만별이다. 그래서 gradient의 핵심 항인 \(\nabla_\theta \log \pi_\theta(a_t \mid s_t)\, R(\tau)\) 가 \(R(\tau)\) 때문에 크게 흔들린다.

적은 trajectory로만 추정한다

REINFORCE는 끝까지 받은 전체 Return을 쓰고 그것도 몇 개 안 되는 에피소드로 gradient를 추정한다. 특정 에피소드에 크게 의존하니 추정값이 noisy해진다.

Credit assignment 문제

한 에피소드 안의 모든 action에 똑같은 \(R(\tau)\)를 곱한다. 그래서 초반 action과 후반 action이 자기 기여도와 상관없이 동일한 피드백을 받는다. 실제로는 좋았던 행동과 나빴던 행동이 한 trajectory 안에 섞여 있는데 전부 같은 점수를 받아버려 신호가 뭉개진다.

한 예시로 내가 그저께 롤을 한판하고 어제는 시험 공부를 하고 오늘 시험을 쳤는데 100점을 맞았다고 가정해보자 100점이라는 reward를 받았지만 실제로 내 reward에 영향을 준건 어제 공부한건데 그저께 롤한것도 100점에 받은데 기여한걸로 의미가 변질된다.

Baseline이 없다

보상을 어떤 기준점에 맞춰 빼주는 baseline이 없다. 그래서 action들 사이의 상대적 차이가 작아도 raw Return의 절대 크기 자체가 커서 분산이 커진다.

5. 분산을 줄이는 방법

REINFORCE의 큰 분산을 줄이는 대표적인 방법 두 가지를 본다.

Reward-to-Go

원래 gradient는 한 trajectory의 모든 시점에 똑같은 전체 Return \(R(\tau)\)를 곱했다.

\[ \nabla_\theta J(\theta) = \frac{1}{N} \sum_{i=1}^{N} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, R(\tau) \right] \]

그런데 시점 \(t\)에 고른 action이 좋은지 나쁜지를 따질 때 그 이전에 받은 reward는 상관이 없다. 지금 고른 action이 이미 받아버린 과거 reward를 바꿀 수는 없기 때문이다. 이걸 causality라고 한다.

예를 들어 아래와 같은 trajectory를 보자.

전체 Return은 \(R(\tau) = 1 - 1 + 1 + 1 = 2\) 다. 여기서 \(s_2\)에서 고른 action \(right\)이 좋았는지 보려면 \(s_2\) 이전의 \(s_0, s_1\)에서 받은 reward는 볼 필요가 없다. 그림에서 회색으로 흐리게 처리한 앞부분이 그래서 빠지고 초록색으로 표시한 \(s_2\) 이후의 reward만 더한 \(R_2 = (+1) + (+1) = 2\) 가 \(s_2\) action의 reward-to-go가 된다.

그래서 전체 Return 대신 시점 \(t\)부터 끝까지 받은 reward의 합인 reward-to-go \(R_t\) 를 곱한다.

\[ R_t = \sum_{t'=t}^{T-1} r(s_{t'}, a_{t'}) \]

gradient는 다음처럼 바뀐다.

\[ \nabla_\theta J(\theta) = \frac{1}{N} \sum_{i=1}^{N} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, R_t \right] \]

각 action에 자기 이후의 reward만 곱하므로 무관한 과거 reward가 섞이지 않아 그만큼 분산이 줄어든다.

Baseline

또 다른 방법은 baseline이다. reward-to-go gradient에서 출발해 \(R_t\)에서 baseline 함수 \(b\)를 빼준다.

\[ \nabla_\theta J(\theta) = \frac{1}{N} \sum_{i=1}^{N} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, (R_t - b) \right] \]

baseline의 목적은 분산을 줄이는 것이다. 만약 \(b\)가 그 state에서 기대되는 평균적인 Return이라면 \(R_t - b\)는 평균보다 얼마나 더 좋았는지 또는 나빴는지를 나타내고 raw Return보다 값의 크기가 작아져 분산이 줄어든다. \(b\)는 \(\theta\)에만 의존하지 않으면 어떤 함수든 쓸 수 있고 가장 단순하게는 trajectory들의 평균 Return \(b = \frac{1}{N} \sum_{i=1}^{N} R(\tau)\) 를 쓴다.

가장 많이 쓰는 baseline은 value function이다. \(V(s_t)\)는 state \(s_t\)에서 policy를 따라갈 때 기대되는 Return이라 그 state의 평균 성적이라고 볼 수 있다. 이걸 baseline으로 쓰면 다음과 같다.

\[ \nabla_\theta J(\theta) = \frac{1}{N} \sum_{i=1}^{N} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, (R_t - V(s_t)) \right] \]

여기서 \(R_t - V(s_t)\) 는 실제로 받은 reward-to-go가 그 state의 평균보다 얼마나 좋았는지를 나타낸다.

그럼 \(V(s_t)\)는 어떻게 구할까. 또 다른 neural network를 파라미터 \(\phi\)로 두고 근사하는데 이걸 value network라 한다. value network는 예측값 \(V_\phi(s_t)\)가 실제 reward-to-go \(R_t\)에 가까워지도록 다음 MSE loss를 최소화하며 학습한다.

\[ J(\phi) = \frac{1}{N} \sum_{i=1}^{N} \sum_{t=0}^{T-1} \big( R_t - V_\phi(s_t) \big)^2 \]

이건 gradient descent로 업데이트한다.

\[ \phi \leftarrow \phi - \alpha \nabla_\phi J(\phi) \]

결국 policy network는 gradient ascent로 \(\theta\)를 올리고 value network는 gradient descent로 \(\phi\)를 내리며 두 네트워크를 함께 학습한다.

사실 이 구조가 바로 actor-critic이다. 이름 그대로 actor는 직접 행동을 고르는 역할이고 critic은 그 actor가 한 행동이 좋았는지 평가하는 역할이다. 여기서 행동을 내는 policy network가 actor이고 그 행동을 평가하는 value network가 critic이다.

• actor인 policy network는 critic이 예측한 \(V_\phi(s_t)\)와 실제로 받은 \(R_t\)의 차이인 advantage \(A_t = R_t - V_\phi(s_t)\) 로 평가
• critic인 value network는 바로 그 차이를 loss 삼아 평가 실력을 업데이트

즉 actor가 행동하면 critic이 점수를 매기고 critic은 그 점수를 점점 정확하게 다듬어가는 셈이다. 다만 엄밀히 따지면 아직은 actor-critic은 아니다... 이유는 다음 글에서 계속...