정책 그래디언트(Policy Gradient)

Value-Based vs Policy-Based

정책 기반의 방법론에 대해 알아볼 것입니다.

하지만 그전에 가치 기반 방법론이 갖는 문제를 몇 가지 살펴보도록 하겠습니다.

 

SARSA, Q-learning 과 같은 가치 기반 방법론은 행동 가치 함수인 $Q$ 를 학습하고 greedy 정책을 통해 각 상태에서 행동 가치가 가장 높은 최선의 행동을 선택하는데 이를 확정적 정책(deterministic policy) 이라고 합니다.

 

결정론적 정책은 가위바위보 같은 게임에서 적용할 수 있을까요?

 

가위바위보에서 최적의 정책은 하나의 최선의 행동이 아닌 동일한 확률 분포를 갖는 정책일 것입니다.

 

이러한 문제에서 정책 기반 방법론은 확률적 정책(stochastic policy)을 취할 수 있습니다.

 

또 다른 문제는 환경이 연속적인 행동 공간(continuous action space)을 갖는 경우입니다.

 

행동 집합이 $0 <= x <= 1$ 의 실수 범위를 갖는다면 무한에 가까운 행동의 범위에 대하여 모든 가치를 저장하기 어려울 것입니다.

 

위와 같은 문제에서도 정책 기반 방법론을 통해 적용할 수 있습니다. 

 

 

정책 그래디언트(Policy Gradient, PG)

정책 기반의 방법론으로 가치 함수 없이 행동을 선택할 수 있는 파라미터 기반의 정책(parameterized policy)을 직접 학습하는 방법입니다. 가치 기반 방법론과는 달리 $\pi_\theta$ 을 근사하는 것이기 때문에 $Q$ 를 보고 행동을 선택하는 것이 아닌 상태 $s$ 에 대해 바로 행동을 선택합니다.

 

이러한 정책 그래디언트 방법론은 확률적 정책(stochastic policy)을 취할 수 있는데 환경이 이산적인 행동 공간(discrete action space)을 갖는다면 이를 상태-행동 쌍에 대해 파라미터화된 수치적 선호도로 확률을 나타낼 수 있으며 이는 소프트맥스 함수(softmax function)로 하여 출력의 합을 1로 하는 확률 분포를 만듭니다.

 

$\pi(a|s,\theta) \doteq { e^{h(s,a,\theta)} \over \sum_b e^{h(s,b,\theta)}}$

 

소프트맥스 함수를 구현하면 다음과 같습니다.

import numpy as np

def softmax(array): 
    r = [] 
    for z in array: 
        r.append(np.exp(z) / sum(np.exp(array))) 
    return r 

a = np.array([0.3, 2.6, 4.1]) 

a = softmax(a)
print(a)
print(sum(a))

[0.01796126464567195, 0.1791489306951451, 0.8028898046591829]
1.0

 

텐서플로에서는 활성화 함수 tf.nn.softmax 를 이용합니다.

import tensorflow as tf

x = tf.placeholder(tf.float32, [None, 1])

y = tf.layers.dense(x, 3, tf.nn.softmax)

with tf.Session() as sess:
    sess.run(tf.global_variables_initializer())
    
    _y = sess.run(y, {x: [[0.1]]})
    
    print(_y)
    print(np.sum(_y))

[[0.35735703 0.3322687  0.3103743 ]]
1.0

 

 

또한 환경이 연속적인 행동 공간(continuous action space)을 갖는다면 정책 파라미터에 의해 추정된 연속 확률 분포(continuous probability distribution)에서 실수값의 행동을 선택할 수 있습니다. 그 연속 확률 분포를 나타내는 확률 밀도 함수(probability density function, PDF)에 대한 평균과 표준 편차는 정책 파라미터에 의한 것입니다.

 

가우시안 분포(gaussian distribution)를 나타내는 확률 밀도 함수는 다음과 같습니다.

 

$p(x) \doteq {1 \over \sigma \sqrt{2 \pi}} \text{exp} \left( - { (x \, - \, \mu)^2 \over 2 \sigma^2 } \right)$

 

확률 밀도 함수를 통해 가우시안 분포를 그리면 다음과 같습니다.

import numpy as np
import matplotlib.pyplot as plt

def pdf(x, mu, sigma):
    return 1 / (sigma * np.sqrt(2 * np.pi)) * np.exp(-(x - mu) ** 2 / (2 * sigma ** 2))

x = np.linspace(-5, 5, 100)

plt.plot(x, pdf(x, mu=0, sigma=1), x, pdf(x, mu=1, sigma=2))
plt.title('Gaussian distribution')
plt.xlabel('x')
plt.ylabel('probability density')
plt.show()

 

텐서플로에서는 가우시안 분포에 대한 함수 tf.distributions.Normal 를 이용할 수 있습니다.

import tensorflow as tf
import numpy as np

MU = 0.
SIGMA = 1.

def pdf(x):
    return 1 / (SIGMA * np.sqrt(2 * np.pi)) * np.exp(-(x - MU) ** 2 / (2 * SIGMA ** 2))

a = tf.placeholder(tf.float32)
dist = tf.distributions.Normal(tf.constant([MU]), tf.constant([SIGMA]))
sample = dist.sample()
prob = dist.prob(a)

x = -0.1

with tf.Session() as sess:
    sess.run(tf.global_variables_initializer())
    print('action sample:', sess.run(sample))
    print('probability density:', sess.run(prob, {a: x}))
print('probability density:', pdf(x))

action sample: [0.16933359]
probability density: [0.39695257]
probability density: 0.3969525474770118

 

 

정책 그래디언트 정리(Policy Gradient Theorem)

목적 함수는 다음과 같이 정의됩니다. (episodic 문제라고 가정)

 

$J(\boldsymbol{\theta}) \doteq v_{\pi_{\theta}}(s_0)$

 

에피소드의 시작 상태의 가치를 나타내는 것으로 이러한 목적 함수를 최대화하는 방향으로 정책 파라미터를 학습하고자 하는 것입니다. ($s_0$ 는 무작위하지 않은 특정 상태에서 시작한다고 가정하는 것을 의미)

 

$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t + \alpha \widehat { \nabla J(\boldsymbol{\theta}_t) }$

 

하지만 파라미터 기반의 함수 근사(function approximation)하는 것은 어려움이 있습니다. 이는 행동 선택과 그 행동으로 인한 상태의 분포가 달라진다는 것인데 정책에 의해 영향을 받은 상태의 분포는 환경에 따라 변하는 함수이고 이는 일반적으로 모른다는 것입니다.

 

정책의 변화가 상태의 분포에 미치는 영향을 모르는 상황에서 어떻게 정책 파라미터를 학습할 수 있을까요?

 

이는 정책 그래디언트 정리라는 이론적인 해결책을 통해 다음 관계를 성립합니다.

 

$\begin{aligned}    
\nabla J(\boldsymbol{\theta}) & \propto \sum_s \mu(s) \sum_a q_{\pi}(s,a) \nabla \pi (a|s, \boldsymbol{\theta}) & \scriptstyle{ \text{ episodic } } \\   
& = \sum_s \mu(s) \sum_a q_{\pi}(s, a) \nabla \pi(a|s, \boldsymbol{\theta}) & \scriptstyle{ \text{ continuous } }    
\end{aligned}$

 

 

증명(Proof of Policy Gradient Theorem)

상태 가치 함수의 미분으로 시작합니다.

 

$\begin{aligned}         
\nabla v_{\pi}(s) & = \nabla \left[ \sum_a \pi_\theta(a|s) q_{\pi}(s, a) \right] & \\         
& = \sum_a \Big[ \nabla \pi(a | s)q_{\pi}(s, a) + \pi(a|s) \color{red} {\nabla q_{\pi}(s, a)} \Big] & \scriptstyle{\text{곱의 법칙}} \\         
& = \sum_a \Big[ \nabla \pi(a | s)q_{\pi}(s, a) + \pi(a|s) \color{red} {\nabla \sum_{s', r} p(s',r | s,a)(r + v_{\pi}(s')) } \Big] & \scriptstyle{q_{\pi} \text{ 를 } v_{\pi} \text{ 대한 식으로}} \\         
& = \sum_a \Big[ \nabla \pi(a | s)q_{\pi}(s, a) + \pi(a|s) \sum_{s'} p(s' | s,a) \color{red} {\nabla v_{\pi}(s' )} \Big] & \scriptstyle{p(s',r | s,a) \text{ 와 } r \text{ 은 } \theta \text{ 의 함수가 아니므로 }} \\ 
& = \sum_a \Big[ \nabla \pi(a | s)q_{\pi}(s, a) + \pi(a|s) \sum_{s'} p(s' | s,a) \\  
& \qquad\quad \sum_{a'} [ \nabla \pi(a' | s') q_{\pi}(s', a') + \pi(a'|s') \sum_{s'} p(s'' | s', a') \nabla v_{\pi}(s'') ] \Big] & \scriptstyle{ \text{ 이 과정을 무한히 반복 } } \\

& = \sum_{x \in S} \sum_{k=0}^\infty \text{Pr}( s \rightarrow x, k, \pi ) \sum_a \nabla \pi(a|x) q_{\pi} (x,a)
\end{aligned}$

 

$Pr(s \rightarrow x, k, \pi)$ 는 정책 $\pi$ 에 의해서 상태 $s$ 에서 $k$ 단계만에 전이할 확률을 나타냅니다.

 

$\begin{aligned}     
\nabla J(\boldsymbol{\theta}) & = \nabla v_{\pi}(s_0) \\     

& = \sum_s \Big( \color{red} {\sum_{k=0}^\infty \text{Pr}( s_0 \rightarrow s, k, \pi )} \Big) \sum_a \nabla \pi(a|s) q_{\pi}(s,a) \\    

& = \sum_s \color{red} {\eta (s)} \sum_a \nabla \pi(a|s) q_{\pi}(s,a) \\    

& = \sum_s' \eta (s') \sum_s \color{red}{ \eta (s) \over \sum_{s'} \eta (s') } \sum_a \nabla \pi(a|s) q_{\pi}(s,a) \\  

& = \sum_s' \eta (s') \sum_s \color{red}{ \mu(s) } \sum_a \nabla \pi(a|s) q_{\pi}(s, a) & \scriptstyle { \mu(s) \text{ 는 고정 분포(stationary distribution) } }\\  

& \propto \sum_s \mu(s) \sum_a \nabla \pi (a|s) q_{\pi}(s, a)

\end{aligned}$  

 

$\mu$ 는 정책 $\pi$ 을 따르는 고정 분포(stationary distribution)로 이를 on-policy distribution 라고 합니다.

 

episodic 문제의 경우 비례 상수 $\propto$ 는 에피소드의 평균 길이이고 continous 문제의 경우 비례 상수는 1이 됨으로써 관계식은 등식으로 바뀌게 됩니다.

 

$\begin{aligned}   
\nabla J(\boldsymbol{\theta}) & \propto \sum_s \mu(s) \sum_a q_{\pi}(s,a) \nabla \pi (a|s, \boldsymbol{\theta}) & \scriptstyle{ \text{ episodic } } \\  
& = \sum_s \mu(s) \sum_a q_{\pi}(s, a) \nabla \pi(a|s, \boldsymbol{\theta}) & \scriptstyle{ \text{ continuous } }   
\end{aligned}$

 

 

증명의 내용 중 일부 변동 사항은 다음 링크를 통해 확인할 수 있습니다.

 

Sutton and Barto, 2020; p325

Sutton and Barto, 2017; p269

 

 

REINFORCE(MC Policy Gradient)

정책 그래디언트를 기반으로 하며 기초가 되는 알고리즘입니다.

 

샘플 기반 그래디언트의 기댓값이 실제 그래디언트에 근사하는 것을 목적으로 다음과 같이 표현할 수 있습니다.

 

$\begin{aligned}

\nabla J(\boldsymbol{\theta}) & \propto \sum_s \mu(s) \sum_a q_{\pi}(s, a) \nabla \pi(a|s, \boldsymbol{\theta}) \\

& = \mathbb{E}_{\pi} \left[ q_{\pi}(S_t, a) \nabla \pi(a|S_t, \boldsymbol{\theta}) \right]

\end{aligned}$

 

또한 $\nabla J(\theta)$ 는 다음과 같이 유도됩니다.

 

$\begin{aligned}  

\nabla J(\boldsymbol{\theta}) & = \mathbb{E}_{\pi} \left[ \color{red} {\sum_a \pi(a|S_t, \boldsymbol{\theta})} q_{\pi}(S_t, a) { \nabla \pi(a|S_t, \boldsymbol{\theta}) \over \pi(a|S_t, \boldsymbol{\theta})} \right] & \scriptstyle{ \text{ 행동 a 를 샘플 } A_t \thicksim \pi \text{ 로 대체 } } \\  
& = \mathbb{E}_{\pi} \left[ \color{red}{q_{\pi}(S_t, A_t)} { \nabla \pi(A_t|S_t, \boldsymbol{\theta}) \over \pi(A_t|S_t, \boldsymbol{\theta})} \right] & \scriptstyle{ \mathbb{E}_{\pi}[ G_t | S_t, A_t ] \; = \; q_{\pi}(S_t, A_t) } \\ 
& = \mathbb{E}_{\pi} \left[ G_t \color{red}{ \nabla \pi(A_t|S_t, \boldsymbol{\theta}) \over \pi(A_t| S_t, \boldsymbol{\theta})} \right] & \scriptstyle{ \nabla \text{ln}x \; = \; { \nabla x \over x }} \\ 
& = \mathbb{E}_{\pi} \Big[ G_t \nabla \text{ln } \pi(A_t|S_t, \boldsymbol{\theta}) \Big] 
\end{aligned}$ 

이처럼 REINFORCE 는 리턴 $G_t$ 를 이용하기 때문에 MC policy gradient 라고도 합니다.

 

 

위에서 얻은 그래디언트를 통해 정책 파라미터는 다음과 같이 업데이트됩니다.

 

$\boldsymbol{\theta}_{t+1} \doteq \boldsymbol{\theta}_t + \alpha \, G_t \nabla \text{ln } \pi(A_t|S_t, \boldsymbol{\theta_t})$

 

파라미터의 벡터 $\boldsymbol{\theta_{t+1}}$ 의 증가량은 리턴 $G_t$ 에 의해 비례하고 행동이 선택될 확률에 반비례합니다. 행동이 선택될 확률에 반비례하지 않으면 자주 선택되는 행동이 유리할 것이고 최대의 리턴을 얻지 못하더라도 더 많이 선호될 수 있다는 것입니다.

 

 

알고리즘은 다음과 같습니다.

 

 

 

구현

REINFORCE 알고리즘 테스트 환경은 OpenAI Gym 의 CartPole-v0 입니다.

 

 

CartPole 은 좌우로 카트를 이동하여 막대기가 쓰러지지 않도록 오래 유지하는 문제입니다. 

 

환경으로부터 받을 수 있는 정보를 출력합니다.

import gym

env = gym.make('CartPole-v0')

print('obs:', env.observation_space.shape[0])
print('act:', env.action_space.n)

 

상태 정보는 4차원의 벡터로 연속적인 공간을 갖으며 에이전트가 취할 수 있는 행동은 스칼라로 2개의 범위를 갖는 이산적인 공간입니다.

obs: 4
act: 2

 

신경망을 정의합니다.

def build_net(self):
    with tf.name_scope('inputs'):
        self.s = tf.placeholder(tf.float32, [None, N_S], name='state')
        self.a = tf.placeholder(tf.int32, name='action')
        self.g = tf.placeholder(tf.float32, name='return')

    with tf.variable_scope('layer'):
        self.fc = tf.layers.dense(self.s, 32, tf.nn.relu)

    with tf.variable_scope('output'):
        self.act_prob = tf.layers.dense(self.fc, N_A, tf.nn.softmax)

    with tf.name_scope('loss'):
        self.loss = tf.log(self.act_prob[0, self.a]) * self.g

    with tf.name_scope('optimizer'):
        self.train_op = tf.train.AdamOptimizer(LR).minimize(-self.loss)

 

상태, 행동, 리턴을 입력으로 받습니다.

with tf.name_scope('inputs'):
    self.s = tf.placeholder(tf.float32, [None, N_S], name='state')
    self.a = tf.placeholder(tf.int32, name='action')
    self.g = tf.placeholder(tf.float32, name='return')

 

출력층으로 입력으로 받은 상태에 대한 행동의 확률을 출력합니다.

with tf.variable_scope('output'):
    self.act_prob = tf.layers.dense(self.fc, N_A, tf.nn.softmax)

 

소프트맥스 활성화 함수를 이용하여 출력의 합이 1인 확률 분포를 출력하는 것입니다.

 

출력된 확률은 np.random.choice 를 이용해서 행동을 선택할 수 있습니다.

def get_action(self, s):
    act_prob = self.sess.run(self.act_prob, {self.s: s[np.newaxis, :]})[0]
    return np.random.choice(range(N_A), p=act_prob)

 

손실 함수를 정의합니다.

with tf.name_scope('loss'):
    self.loss = tf.log(self.act_prob[0, self.a]) * self.g

 

해당 타임스텝에서 취한 행동에 대해서 리턴 값이 양수이면 취한 행동의 확률은 증가하고 음수이면 그 확률은 감소할 것입니다. 또한 log 함수를 통해 높은 확률을 갖는 행동에 대해서는 변화량이 작으며 낮은 확률을 갖는 행동의 변화량은 클 것입니다.

 

마이너스를 붙여 손실값이 최대가 되는 방향으로 학습하도록 설정합니다.

with tf.name_scope('optimizer'):
    self.train_op = tf.train.AdamOptimizer(LR).minimize(-self.loss)

 

에이전트와 환경의 상호작용입니다.

num_episode = 200
for i in range(num_episode):
    memory = []

    state = env.reset()
    done = False
    while not done:
        action = agent.get_action(state)
        next_state, reward, done, _ = env.step(action)
        memory.append((state, action, reward))
        state = next_state
    
    agent.train(memory)

 

에이전트는 각 타임스텝의 상태, 행동, 보상을 메모리에 저장하며 에피소드가 종료되면 학습을 진행합니다.

 

역방향으로 계산하여 감쇠된 리턴은 각 상태에 대해 업데이트를 수행합니다.

def train(self, memory):
    g = 0
    for s, a, r in reversed(memory):
        g = r + GAMMA * g
        self.sess.run(self.train_op, {self.s: s[np.newaxis, :], self.a:a, self.g: g})

 

 

 

200번의 에피소드 동안 학습한 결과입니다.

 

 

저장된 모델을 불러와 테스트합니다.

INFO:tensorflow:Restoring parameters from ./tmp/reinforce_cartpole/model/model
episode: 0 / step: 123
episode: 1 / step: 200
episode: 2 / step: 179
episode: 3 / step: 144
episode: 4 / step: 200