본문으로 바로가기

Welcome to Spinning Up in Deep RL!

원본은 Part 3: Intro to Policy Optimization

Table of Contents

  • Part 3: Intro to Policy Optimization
    • Deriving the Simplest Policy Gradient
    • Implementing the Simplest Policy Gradient
    • Expected Grad-Log-Prob Lemma
    • Don’t Let the Past Distract You
    • Implementing Reward-to-Go Policy Gradient
    • Baselines in Policy Gradients
    • Other Forms of the Policy Gradient
    • Recap

이번 절에서 policy optimization 알고리즘의 수학 기초에 대해서 얘기해보고 이를 코드와 연결지어서 볼 예정입니다. policy gradients의 이론을 다음 3가지 중요한 키포인트들로 다룰겁니다.

  • 정책 파라미터에 관한 정책 성능(performance)의 gradient을 설명하는 간단한 수식
  • 수식에서 필요없는 항을 제거하는 규칙
  • 수식에서 유용한 항을 더하는 규칙

마지막으로 위의 결과들을 모두 묶어서 policy gradient를 위한 advantage-based 수식을 설명할 겁니다. 이는 Vanilla Policy Gradient 구현에서 사용합니다.

Deriving the Simplest Policy Gradient

여기서 확률적으로 파라미터화된 정책(stochastic, parameterized policy) $\pi_\theta$의 경우를 가정해보겠습니다. 우리의 목적은 기대되는 반환값(expected return) $J(\pi_{\theta}) = E_{\tau \sim \pi_{\theta}}{R(\tau)}$을 최대화하는 것이죠. 미분을 위해 $R(\tau)$을 가져와서 finite-horizon undiscounted return에 넣을겁니다. 그런데 이는 infinite-horizon discounted return 미분과 거의 동일합니다.

다음과 같이 gradient ascent로 정책을 최적화하길 원합니다.

$$ \theta_{k+1} = \theta_k + \alpha \left. \nabla_{\theta} J(\pi_{\theta}) \right|_{\theta_k}. $$

정책 성능(performance)의 gradient $\nabla_{\theta} J(\pi_{\theta})$을 policy gradient라 하며 위와 같은 방법으로 정책을 최적화하는 알고리즘을 policy gradient algorithms이라 합니다. (Vanilla Policy Gradient, TRPO를 예로 들 수 있으며, 약간 부정확하지만 PPO도 종종 policy gradient 알고리즘으로 언급되기도 합니다.)

실제로 이 알고리즘을 사용하려면 수치적으로 계산할 수 있는 policy gradient에 대한 식이 필요합니다. 이는 두 단계로 구성되어있는데, 먼저 1) 정책 성능(preformance)의 analytical gradient를 도출하여 기대되는 가치(expected value)의 형태를 갖게 한 다음 2) 에이전트와 환경의 상호작용을 유한한 수만큼 하여 얻은 데이터로 계산한 기대되는 가치(expected value)의 샘플 추정치를 형성합니다.

(이 부분은 해석이 어려웠습니다. loss의 gradient를 expected value형태로 만들어서 이 값을 추정하는 데에 상호작용한 데이터를 쓰라는 것 같습니다)
analytical이라는 의미는 우리가 알고 있는 수식을 통해 문제를 정확히 풀어가는 방법을 말합니다. 앞으로 나올 gradient에 대한 식을 통해 gradient 식을 약간 변경시킬듯 합니다

이번 하위 절에서, 저 수식의 간단한 형태를 알아보고 다음 하위 절에서는 표준 policy gradient 구현에서 실제로 사용하는 버전을 얻기 위해 가장 간단한 형태를 개선하는 방법을 보여줄 예정입니다.

analytical gradient를 도출하기 위해 유용한 몇 가지들을 보여드리겠습니다.

1. Probability of a Trajectory. 정책 $\pi_{\theta}$에 따라 행동했을 때 trajectory $\tau = (s_0, a_0, ..., s_{T+1})$의 확률은 다음과 같습니다.

$$ P(\tau|\theta) = \rho_0 (s_0) \prod_{t=0}^{T} P(s_{t+1}|s_t, a_t) \pi_{\theta}(a_t |s_t). $$

2. The Log-Derivative Trick. log 미분 트릭은 미적분학에서 나오는 간단한 규칙을 기반하여 나온 것으로 $x$에 대한 $\log x$ 미분은 $1/x$입니다. 연쇄 법칙(chain rlue)에 의해 재배치해서 결합하면 다음과 같이 얻을 수 있습니다.

$$ \nabla_{\theta} P(\tau | \theta) = P(\tau | \theta) \nabla_{\theta} \log P(\tau | \theta). $$

3. Log-Probability of a Trajectory. trajectory의 log 확률은 다음과 같습니다.

$$ \log P(\tau|\theta) = \log \rho_0 (s_0) + \sum_{t=0}^{T} \bigg( \log P(s_{t+1}|s_t, a_t) + \log \pi_{\theta}(a_t |s_t)\bigg). $$

4. Gradients of Environment Functions. 환경은 $\theta$에 의존하는게 없어서 $ \rho_0(s_0)$, $P(s_{t+1}|s_t, a_t)$와 $R(\tau)$의 gradient는 0입니다.

5. Grad-Log-Prob of a Trajectory. trajectory의 log 확률의 gradient는 결국 다음과 같게 됩니다.

이것들을 모두 종합하면, 다음과 같이 나타낼 수 있습니다.

Basic Policy Gradient 미분


(혹시나 더 이해가 잘 안되신다면 이웅원님의 RLCode와 A3C 쉽고 깊게 이해하기를 참조해주세요.)

이는 샘플 평균으로 추정할 수 있는 기대값이라는 얘기입니다. 만약 정책 $\pi_{\theta}$을 통해 에이전트가 환경에서 행동해 얻은 trajectory들의 집합 $\mathcal{D} = {\{\tau_i\}}_{i=1,...,N}$을 모았다고 할 때, policy gradient는 다음과 같이 추정될 수 있습니다.

$$ \hat{g} = \frac{1}{|\mathcal{D}|} \sum_{\tau \in \mathcal{D}} \sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_t |s_t) R(\tau) $$

여기서 $|\mathcal{D}|$는 $\mathcal{D}$에서 trajectory의 개수($N$) 를 의미합니다.

마지막 수식은 바라왔던 계산 가능한 가장 단순한 형태입니다. $\nabla_{\theta} \log \pi_{\theta}(a|s)$을 계산할 수 있는 방법으로 정책을 나타내고, 환경에서 policy에 따라 trajectory 데이터셋을 모을 수 있다면, policy gradient를 계산하고 업데이트를 할 수 있습니다.

Implementing the Simplest Policy Gradient

spinup/examples/pg_math/1_simple_pg.py에서 policy gradient 알고리즘의 단순하고 짧은 Tensorflow 구현 보여드리겠습니다. (이는 github에서도 볼 수 있습니다.) 122줄 정도의 길이이기에, 한번 깊이 있게 읽어보시는 것을 적극 추천합니다. 여기서 코드 전체를 다루지는 않겠지만, 몇 가지 중요한 부분을 강조하고 설명하겠습니다.

1. Making the Policy Network

# 정책 네트워크 핵심
obs_ph = tf.placeholder(shape=(None, obs_dim), dtype=tf.float32)
logits = mlp(obs_ph, sizes=hidden_sizes+[n_acts])

# 행동 선택 (정책으로부터 샘플링된 행동 출력(int))
actions = tf.squeeze(tf.multinomial(logits=logits,num_samples=1), axis=1)

이 블록은 feedforward neural network categorical policy를 생성합니다. (기억을 되새기기 위해 Stochastic Policies를 다시 한번 보세요. logits 텐서는 log 확률과 행동에 대한 확률을 생성하는데 사용될 수 있고, action 텐서는 logits가 가지는 확률을 기반으로 행동을 샘플링합니다.

2. Making the Loss Function

# loss function을 만듭니다. 여기서 gradient는 (올바른 데이터에 대해) policy gradient입니다.
weights_ph = tf.placeholder(shape=(None,), dtype=tf.float32)
act_ph = tf.placeholder(shape=(None,), dtype=tf.int32)
action_masks = tf.one_hot(act_ph, n_acts)
log_probs = tf.reduce_sum(action_masks * tf.nn.log_softmax(logits), axis=1)
loss = -tf.reduce_mean(weights_ph * log_probs)

이 블록에서는 policy gradient 알고리즘을 위해 "loss" 함수를 만들었습니다. 올바른 데이터가 들어오면 loss의 gradient는 policy gradient와 같습니다. 여기서 올바른 데이터라는 말은 현재 정책에 따라 행동을 해서 모인 (상태, 행동, 가중치(weight)) 튜플을 의미합니다. 이때 상태-행동 쌍에 대한 가중치(weight_ph)는 해당 에피소드의 return이 들어갑니다.(이후 하위 절에서 보이겠지만, 동작이 올바르게 되도록 가중치에 다른 값을 넣을 수도 있습니다.)

알아두세요

loss function이라 설명했지만 지도 학습(supervised learning)에서 말하는 loss function이 아닙니다. 표준 loss function과는 주로 두 가지 차이점이 있습니다.

1. 데이터 분포는 파라미터에 의존합니다. loss function은 최적화하고자 하는 파라미터와 독립적이고 고정된 데이터 분포에 의해 정의됩니다. 하지만 여기선 아니죠. 데이터가 가장 최근 정책에 의해 샘플링됩니다.

2. 성능(performance)를 측정하지 않습니다. loss function은 보통 신경쓰고 있는 performance metric을 평가합니다. 여기서는 expected return $J(\pi_{\theta})$을 신경쓰고 있지만, "loss" function은 이를 전혀 근사(approximate)하지 않습니다. 심지어 기댓값에서도 말이죠. 현재 파라미터로 생성된 데이터를 가지고 다시 현재 파라미터를 평가될 때, 성능(performance)의 gradient는 음수의 값을 가지기 때문에, 이 "loss" function은 우리에게만 유용합니다. (번역자 추측: 제가 생각하기로는 return값은 높을 수록 좋은데 이 loss 값에 의해서 gradient는 음수 값만 가지기 때문에 낮은 값이 나와 return에는 별 도움이 안된다라는 의미 같습니다.)

gradient descent 한 번 하고 난 이후에는, performance와 더이상의 접점이 없게됩니다. 이 말은 데이터 배치로 "loss" function을 최소화 하는 것이 expected return을 개선시킬지 보장할 수 없다는 뜻입니다. 즉, loss 값을 $-\infty$로 만들어도 policy performance가 떨어질 수 있다는 것이고, 실제도로도 그럴겁니다. 가끔, deep RL 연구원들은 이러한 결과를 가지고 데이터 배치에 대한 policy가 "overfitting되었다"라고 설명하기도 합니다. 설명이 괜찮긴 하지만(descriptive) 일반화 오류(generalization error)를 말하는 것은 아니므로, 말 그대로 받아들여서는 안됩니다.

ML 종사자들에겐 loss function을 학습할 때 유용한 신호 정도로 해석하는게 보통이기 때문에 이 부분에 문제점이 있습니다. "loss값이 내려간다면, 모든게 잘되고 있는 것이다." policy gradient에서는 틀린 말입니다. 여기서는 오로지 average return만을 고려해야합니다. loss function은 아무런 의미도 없습니다.

알아두세요

action mask를 만들고 이를 사용해 특정 log 확률을 선택하도록 하는 log_probs tensor를 생성한 방법은 categorical policy에서만 동작합니다. 일반적으로 되는 것이 아닙니다.

3. Running One Epoch of Training

# 정책(policy) 학습
def train_one_epoch():

    # log를 남기기 위해 빈 list를 만듭니다.
    batch_obs = []          # observations
    batch_acts = []         # 행동들
    batch_weights = []      # policy gradient에서 가중할(weighting) R(tau)
    batch_rets = []         # 에피소드 return값
    batch_lens = []         # 에피소드 길이

    # 에피소드용 변수들 리셋
    obs = env.reset()       # 시작분포에 따른 처음 observation
    done = False            # 에피소드가 끝났음을 환경으로부터 받는 신호
    ep_rews = []            # 에피소드를 통해 발생하는 보상 리스트

    # 각 에폭 첫 번째 에피소드 때 렌더링
    finished_rendering_this_epoch = False

    # 현재 정책으로 환경에서 행동하여 경험을 모읍니다.
    while True:

        # 렌더링
        if not(finished_rendering_this_epoch):
            env.render()

        # observation 저장
        batch_obs.append(obs.copy())

        # 환경에서 행동
        act = sess.run(actions, {obs_ph: obs.reshape(1,-1)})[0]
        obs, rew, done, _ = env.step(act)

        # 행동과 보상을 저장
        batch_acts.append(act)
        ep_rews.append(rew)

        if done:
            # 에피소드가 끝나면 에피소드에 대한 기록을 남기기
            ep_ret, ep_len = sum(ep_rews), len(ep_rews)
            batch_rets.append(ep_ret)
            batch_lens.append(ep_len)

            # 각 log확률(행동|상태)에 대한 가중치는 R(tau)
            batch_weights += [ep_ret] * ep_len

            # 에피소드 변수 리셋
            obs, done, ep_rews = env.reset(), False, []

            # 이 에폭 뒤로는 렌더링 하지 않습니다.
            finished_rendering_this_epoch = True

            # 만약 경험이 충분히 모였다면 이 루프(loop)를 종료합니다.
            if len(batch_obs) > batch_size:
                break

    # 한 번 policy gradient 업데이트합니다.
    batch_loss, _ = sess.run([loss, train_op],
                             feed_dict={
                                obs_ph: np.array(batch_obs),
                                act_ph: np.array(batch_acts),
                                weights_ph: np.array(batch_weights)
                             })
    return batch_loss, batch_rets, batch_lens

train_one_epoch() 함수는 policy gradient의 한 "에폭(epoch)"을 동작시키고 다음과 같이 정의 되어있습니다.

  1. 경험을 모으는 단계(62 ~ 97줄), 에이전트는 가장 최근 정책에 따라 환경에서 몇 에피소드동안 행동을 합니다. 그 다음에
  2. policy gradient 업데이트를 한 번 합니다 (99 ~ 105줄)

알고리즘 메인 루프에서는 이 train_one_epoch()을 반복적으로 호출합니다.

Expected Grad-Log-Prob Lemma

이 절에서는, policy gradient 이론을 통해 널리 사용되는 중간 결과(intermediate result)를 도출할 겁니다. 이를 앞으로 Expected Grad-Log-Prob (EGLP) lemma라고 부르겠습니다.

EGLP Lemma. $P_{\theta}$가 임의의 변수 $x$에 대해서 매개변수화(parameterized)된 확률 분포라고 가정하겠습니다. 그렇다면 다음과 같이 됩니다.

$$
\mathbb{E}_{x \sim P_{\theta}}\left [\nabla_{\theta} \log P_{\theta}(x)\right ] = 0.
$$

증명

모든 확률 분포가 정규화되어 있었었죠.

$$\int_x P_{\theta}(x) = 1.$$

양쪽 다 gradient를 취합니다

$$ \nabla_{\theta} \int_x P_{\theta}(x) = \nabla_{\theta} 1 = 0. $$

여기서 log 미분 트릭을 사용합니다.

$$ 0 = \nabla_{\theta} \int_x P_{\theta}(x) $$
$$ = \int_x \nabla_{\theta} P_{\theta}(x) $$
$$ = \int_x P_{\theta}(x) \nabla_{\theta} \log P_{\theta}(x)$$
$$ \therefore 0 = E_{x \sim P_{\theta}}[\nabla_{\theta} log P_{\theta}(x)]. $$

Don’t Let the Past Distract You

policy gradient에 대한 가장 최근 식을 보죠.

$$\nabla_{\theta} J(\pi_{\theta}) = \mathbb{E}{\tau \sim \pi_{\theta}}]\left [\sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_t |s_t) R(\tau)\right ]. $$

이 gradient 만큼 움직여서 $R(\tau)$에 비례하게 각 행동의 log 확률을 높이면, 모든 보상의 합을 얻을 수 있겠지만, 사실 별 의미가 없습니다.

에이전트는 결과를 기반으로 하여 행동을 강화해야만 합니다. 행동을 취하기 전에 얻은 보상은 그 행동이 얼마나 좋은지와 아무런 관련이 없습니다. 오직 행동하고 난 뒤에서야 의미가 있습니다.

이러한 직관이 수학에 나타나 있고, policy gradient가 다음과 같이 표현될 수도 있다는 것을 보일 수 있습니다.

$$
\nabla_{\theta} J(\pi_{\theta}) = E_{\tau \sim \pi_{\theta}}\left [ \sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \sum_{t'=t}^T R(s_{t'}, a_{t'}, s_{t'+1})\right ].
$$

이 식에서, 행동들은 취한 뒤에야 얻을 수 있는 보상을 기반으로 강화됩니다.

이 식을 "reward-to-go policy gradient"라고 부르겠습니다. 왜냐하면 trajectory에서 어떤 지점이 지난 뒤에 얻은 보상의 합이기 때문입니다.

$$
\hat{R}_t \doteq \sum_{t'=t}^T R(s_{t'}, a_{t'}, s_{t'+1}),
$$

이를 어떤 지점에서 reward-to-go라고 부르며, policy gradient 표현은 상태 행동 쌍의 reward-to-go에 달려있습니다.

알아두세요

근데 이게 더 좋을까요? policy gradients의 문제는 적은 분산을 가지면서 얼마나 많은 trajectory가 필요한지 입니다. 시작할 때 나왔던 식에서는 지난 reward들에 비례하여 행동을 강화시켰었는데, 평균은 0이였지만 분산은 0이 아니였습니다. 결과적으로, policy gradient의 estimate를 샘플하는데 노이즈를 더한 것일 수 있습니다. 이를 제거함으로써, 필요한 trajectory 수를 줄입니다.

(선택사항) 이 주장에 대한 근거는 여기서 찾아볼 수 있으며, 궁극적으로 EGLP lemma에 의존합니다.

Implementing Reward-to-Go Policy Gradient

spinup/examples/pg_math/2_rtg_pg.py에서 reward-to-go policy gradient의 짧은 Tensorflow 구현을 보여드리겠습니다.(github에서 자세히 볼 수 있습니다.)

1_simple_pg.py의 loss function에서 이제 다른 weight를 사용하도록 바뀌었습니다. 코드 변화는 매우 작아서, 새로운 함수를 추가하고, 2줄만 바꾸었습니다. 새로운 함수는 다음과 같습니다.

def reward_to_go(rews):
    n = len(rews)
    rtgs = np.zeros_like(rews)
    for i in reversed(range(n)):
        rtgs[i] = rews[i] + (rtgs[i+1] if i+1 < n else 0)
    return rtgs

그런 다음 이전의 코드 86~87줄을

# the weight for each logprob(a|s) is R(tau)
batch_weights += [ep_ret] * ep_len

다음과 같이 바꾸었습니다.

# the weight for each logprob(a_t|s_t) is reward-to-go from t
batch_weights += list(reward_to_go(ep_rews))

Baselines in Policy Gradients

EGLP lemma는 상태에 따른 어떤 함수 $b$가 생긴 것입니다.

$$
E_{a_t \sim \pi_{\theta}}\left [\nabla_{\theta} \log \pi_{\theta}(a_t|s_t) b(s_t)\right ] = 0.
$$

기댓값 내부를 변화시키지 않으면서 policy gradient 식에 b 항 부분에 몇 개든 넣거나 뺄 수 있습니다.

$$
\nabla_{\theta} J(\pi_{\theta}) = E_{\tau \sim \pi_{\theta}}\left [\sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_t |s_t) \left(\sum_{t'=t}^T R(s_{t'}, a_{t'}, s_{t'+1}) - b(s_t)\right)\right].
$$

여기서 사용되는 함수 $b$는 baseline이라 부릅니다.

baseline에 들어가는 가장 일반적인 것은 on-policy value function $V^\pi(s_t)$입니다. 이는 상태 $s_t$에서 시작해서 policy $\pi$에 따라 계속 행동했을 때 에이전트가 받는 평균 return이였습니다.

경험적으로 봤을 때, $b(s_t)=V^\pi(s_t)$로 하면 policy gradient에서 sample estimate에서 분산을 줄이는 효과가 있습니다. 이는 더 빠르고 안정적인 정책을 학습하게 합니다. 개념적인 관점에서도 볼만한데요. 만약 agent가 기대한 것을 얻는다면 그것에 대해 중립적으로 느껴야한다는 직관을 얻을 수 있습니다.

알아두세요

실제로 $V^\pi(s_t)$는 정확하게 계산될 수 없어서, 근사(approximate)해야 합니다. 보통 정책과 동시에 업데이트되는 neural network $V_\phi(s_t)$로 이루어져 있습니다. (그래서 value network가 항상 가장 최근 정책의 value function와 비슷합니다.)

정책 최적화 알고리즘(VPG, TRPO, PPO, 그리고 A2C) 대부분 구현에 사용되는 $V_\phi$를 학습하기 위해 사용되는 가장 단순한 방법은 mean-squared-error를 최소화 하는 것입니다.
$$ \phi_k = \arg \min_{\phi} E_{s_t, \hat{R}t \sim \pi_k}\left [ \left( V{\phi}(s_t) - \hat{R}t \right)^2 \right ] $$
$\pi_k$는 epoch $k$에서 정책입니다. 이전의 value parameter $\phi
{k-1}$에서 시작해서 한 번 이상의 gradient descent가 이루어집니다.

Other Forms of the Policy Gradient

지금까지 본 것은 policy gradient의 일반적인 형태입니다.

$$\nabla_{\theta} J(\pi_{\theta}) = \mathbb{E}_{\tau \sim \pi_{\theta}} \left [ \sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_t |s_t) \Phi_t \right ]$$

$\Phi_t$는
$$ \Phi_t = R(\tau) $$
또는
$$ \Phi_t = \sum_{t'=t}^T R(s_{t'}, a_{t'}, s_{t'+1}) $$
또는
$$ \Phi_t = \sum_{t'=t}^T R(s_{t'}, a_{t'}, s_{t'+1}) - b(s_t) $$
이 될 수 있습니다.

이 것들은 모두 다른 분산을 가지는데도 policy gradient에서 같은 expected value가 나옵니다. weight $\phi_t$에 들어갈 수 있는 2가지가 더 있으며 알아야할 중요한 부분입니다.

1. On-Policy Action-Value Function

$$
\Phi_t = Q^{\pi_{\theta}}(s_t, a_t)
$$

가 유효한 것으로 (선택 사항으로) 이 페이지에 증명이 있습니다.

2. The Advantage Function $A^{\pi}(s_t,a_t) = Q^{\pi}(s_t,a_t) - V^{\pi}(s_t)$로 정의된 행동의 advantage에 대해서 다시 떠올려보면, (현재 정책에 관련된) 평균으로 다른 행동보다 더 좋은지 나쁜지를 의미했었습니다.

$$
A^{\pi}(s_t,a_t) = Q^{\pi}(s_t,a_t) - V^{\pi}(s_t),
$$

이것도 유효한데요. 증명은 $\Phi_t = Q^{\pi_{\theta}}(s_t, a_t)$를 사용한 다음 value function $\Phi_t = R(\tau)$를 사용한 것과 같습니다. 그러니 자유롭게 써도 되는 거죠.

알아두세요

advantage function으로 policy gradient하는 식은 아주 흔하고, 다른 알고리즘을 사용해 advantage function을 estimate하는 다양한 방법들이 있습니다.

알아두세요

이 주제를 자세히 다루려면, $\phi_t$에 다른 것들을 넣는 데 있어 깊이 있게 가는 Generalized Advantage Estimation(GAE) 논문을 읽어야 합니다.

이 논문은 널리 사용되는 policy optimization 알고리즘에서 advantage function을 근사(approximating)하는 방법, GAE를 설명합니다. 예를 들어, Spinning Up의 VPG, TRPO, 그리고 PPO 구현에서 이를 사용합니다. 결국, GAE를 연구하시기를 강력 추천합니다.

Recap

이번 챕터에서, policy gradient의 기본 이론에 대해서 설명하고 초기 방법들 중 일부를 코드 예제와 연결했습니다. 흥미로운 학생들은 이후 방법들(policy gradient에서 value function baseline과 advatnage을 쓰는 부분)이 어떻게 Spinning Up의 Vanilla Policy Gradient 구현으로 되는지 연구할 수 있게 여기서부터 계속 나아가면 됩니다.