- Published on
[DPG] Deterministic Policy Gradient Algorithms
논문 제목 : Deterministic Policy Gradient Algorithms
- David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, Martin Riedmiller
- 2018
- 논문 링크
- 보충 자료
Summary
- Stochastic Policy 가 아닌 Deterministic Policy 에서도 Policy Gradient Theorem이 성립함을 보이고 있다.
- Deterministic Policy란 결국 Stochastic Policy에서 Variance가 0인 특수한 경우라는 것을 증명하고, 이를 통해 Stochastic Policy Gradient가 적용되는 기존 방법론(Actor-Critic)에서도 Deterministic Policy를 사용할 수 있다는 것을 보이고 있다.
- Actor-Critic에서 Critic을 Function Approximator 로 하여 Performance Gradient를 구할 때, True q-Function이 아니어서 발생하는 Bias를 제거하는 조건을 제시하고 있다.
Policy Gradient Theorem
Policy Gradient란 말 그대로 Policy 를 Parameterize하고, Performance를 극대화하는 방향으로 이를 업데이트하는 강화학습 방법론을 말한다. 이때 Performance라는 것은 다음과 같이 현재의 Policy 를 따를 때 얻을 것으로 기대되는 Reward의 총합으로 정의된다.
\eqalign{ J(\pi_\theta) &= \int_S \rho^\pi(s) \int_A \pi_\theta (s,a) r(s,a) dads\\ &= E_{s\backsim \rho^\pi, a \backsim \pi_\theta} [r(s, a)] }이를 극대화하는 방향이라고 할 수 있는 Gradient는 다음과 같이 구해진다. 이를 Policy Gradient Theorem이라고 한다.
\eqalign{ \nabla J(\pi_\theta) &= \int_S \rho^\pi(s) \int_A \nabla_\theta \pi_\theta (s,a) Q^\pi(s,a) dads\\ &= E_{s\backsim \rho^\pi, a \backsim \pi_\theta} [\nabla_\theta \log \pi_\theta(a \lvert s) Q^\pi(s,a)] }Policy Gradient Theorem은 Performance Gradient를 단순한 기대값 형태로 바꾸어주어 적은 연산량으로 쉽게 추정할 수 있도록 해주었다는 점에서 실용적인 측면에서도 큰 의의를 가지고 있다. 위의 식에 따르면 Performance Gradient를 구할 때 State Distribution 가 고려되기는 하나, 어떤 State에서의 가 얼마나 중요한지 결정하는 것일 뿐 State Distribution의 Gradient 자체는 필요하지 않다.
Actor-Critic Architecture
Actor-Crtic 구조는 Policy Gradient Theorem을 바탕으로 하는 알고리즘 중 하나로서, 이름으로 유추할 수 있듯이 Action을 결정하는 Actor 와 선택한 Action이 얼마나 좋은지 평가하는 Critic 으로 이뤄져 있다. 이러한 점에서 Actor-Critic 구조는 Policy Gradient Theorem에서 True Q Function 을 parameter 를 가지는 로 근사하여 대체하는 방법론이라고 할 수 있다.
\eqalign{ &E_{s\backsim \rho^\pi, a \backsim \pi_\theta} [\nabla_\theta \log \pi_\theta(a \lvert s) Q^\pi(s,a)]\\ & \Rightarrow E_{s\backsim \rho^\pi, a \backsim \pi_\theta} [\nabla_\theta \log \pi_\theta(a \lvert s) Q^w(s,a)] }True Q Function 를 대신하여 근사함수 를 사용하여 학습을 진행하게 되면 Bias가 발생하게 되고 이로 인해 안정적인 학습이 방해받을 수 있다. 이와 관련하여 가 다음 두 조건을 만족하는 경우 Bias는 존재하지 않는다는 것이 Sutton 등에 의해 증명되어 있다.
\eqalign{ & 1. Q^w(s,a) = \nabla_\theta \log \pi_\theta (a \lvert s)^\text{T} w \\ & 2. w \text{ is chosen to minimize } \epsilon^2(w) = E_{s \backsim \rho^\pi, a \backsim \pi_\theta} [(Q^w(s,a) - Q^\pi(s,a))^2] }첫 번째 조건은 Compatible Function Apprximator 는 Policy의 Gradient 의 feature에 대해 선형의 관계를 가진다는 것으로, 두 번째 조건은 로 를 예측하는 선형회귀 문제로 풀어야 한다는 것으로 이해할 수 있다. Actor-Critic 구조에서 자주 사용하는 TD method를 통해 Critic을 업데이트하면 두 번째 조건을 만족하게 된다.
결과적으로 두 가지 조건을 모두 만족하게 되면 REINFORCE 알고리즘과 같이 Critic을 사용하지 않는 알고리즘들과 동일해진다고 한다.
Off-Policy Actor-Critic Architecture
Policy Gradient Thoerem에서 는 On-Policy State Distribution으로, 현재의 Policy 를 따를 때 어떤 State 를 방문할 확률을 의미한다. 이와 달리 State Distribution 처럼 현재 Policy 가 아닌 다른 Policy 를 사용할 수도 있는데, 이를 Off-Policy State Distribution 이라고 한다. 그리고 두 Policy를 각각 를 Behavior Policy, 를 Target Policy라고 한다.
\eqalign{ J_\beta (\pi_\theta) &= \int_S \rho^\beta (s) V^\pi(s) ds\\ &= \int_S \int_A \rho^\beta (s) \pi_\theta(a \lvert s) Q^\pi (s, a) da ds }이때 Performance Gradient는 다음과 같이 구할 수 있다.
\eqalign{ \nabla J_\beta (\pi_\theta) &= \nabla_\theta \int_S \int_A \rho^\beta (s) \pi (s \lvert a) Q^\pi (s, a) da ds\\ &= \int_S \int_A \rho^\beta(s) [\nabla_\theta \pi(a \lvert s) Q^\pi(s,a) + \pi(a \lvert s)\nabla_\theta Q^\pi(s,a)] da ds \\ &\approx \int_S \int_A \rho^\beta(s) [\nabla_\theta \pi(a \lvert s) Q^\pi(s,a)] da ds \\ &= E_{s \backsim \rho^\beta, a \backsim \beta} [ {\pi_\theta (a \lvert s) \over {\beta_\theta (a \lvert s)}} \nabla_\theta \log \pi_\theta(a \lvert s) Q^\pi(s, a)] }위 전개 식의 가장 큰 특징은 세 번째 줄에서 Term이 사라졌다는 데에 있다. Action Value Function에 대한 Gradient를 구하는 것이 까다롭기 때문에 제거한 것인데, Degris 등에 따르면 이 때에도 Local Optima로의 수렴성이 보장된다고 한다. 마지막 줄의 는 를 따를 때의 분포와 를 따를 때의 분포가 다르기 때문에 이를 맞춰주는 Importance Sampling Term이다.
Deterministic Policy Gradient
지금까지 살펴본 Policy Gradient Theorem과 그 변형들은 모두 **Stochastic Policy **를 가정하고 있다. 같은 에 대해서도 다양한 가 확률적으로 결정될 수 있다는 점에서 Stochastic이라는 표현이 붙었다. 반면 논문에서 다루고 있는 주제인 Deterministic Policy Gradient는 Deterministic Policy , 즉 하나의 State 는 항상 하나의 Action 로 매핑되는 함수를 사용할 때의 Policy Gradient를 말한다.
이와 같이 Deterministic Policy를 사용하게 되면 당장 두 가지에 대한 의문이 발생하게 된다. 첫 번째는 수렴성에 대한 증명, 즉 Gradient Theorem이 이 경우에도 만족하는지 확인해야 할 필요가 있다는 것이고, 두 번째는 Exploration을 수행하는 방법에 관한 것이다. 논문에서는 이에 대한 답변으로 (1) Deterministic Policy란 Stochastic Policy의 특수한 형태()일 뿐이고, (2) 앞서 Stochastic한 경우에서 수렴성 증명이 완료되어 있는 Behavior Policy를 사용하는 것으로 Exploration을 도입할 수 있다고 말한다.
Deterministic Policy Gradient Theorem
Stochastic Policy를 고려할 때와 가장 큰 자이점은 Deterministic Policy에서는 더 이상 다양한 Action에 대한 경우의 수를 고려할 필요가 없다는 것이다. 따라서 Performance Objective 또한 다음과 같이 다시 쓸 수 있다
\eqalign{ \text{Stochastic: }& \eqalign{ J(\pi_\theta) &= \int_S \rho^\pi(s) \int_A \pi_\theta (s,a) r(s,a) dads\\ &= E_{s\backsim \rho^\pi, a \backsim \pi_\theta} [r(s, a)] } \\ \\ \text{Deterministic: }& \eqalign{ J(\pi_\theta) &= \int_S \rho^\pi(s) r(s,\mu_\theta(s)) ds\\ &= E_{s\backsim \rho^\pi,} [r(s, \mu_\theta(s))] } }논문에서 제시하는 Deterministic Policy Gradient Theorem은 다음과 같다.
\begin{multline} \shoveleft{ \text{Suppose the the MDP satisfies A.1 conditions below,}}\\ \end{multline} \begin{multline} \shoveleft {\text{Regularity Confitions }}\\ \shoveleft { \quad \text{A.1: } p(s' \lvert s, a), \nabla_a p(s' \lvert s, a), \mu_\theta(s), \nabla_\theta \mu_\theta (s), r(s,a), \nabla_a r(s,a), p_1(s) \text{ are continuous } }\\ \shoveleft{ \qquad \text{in all parameters and variables } s, a s' and x. }\\ \shoveleft{ \quad \text{A.2: there existis a } b \text{ and } L \text{ such that } \sup_s p_1(s) < b, \sup_{a,s,s'} p(s' \lvert s, a) < b, \sup_{a,s} r(s, a) < b, }\\ \shoveleft{ \qquad \sup_{a,s,s'} | \nabla_a p(s' \lvert s, a) | < L \text{ and } \sup_{a,s} | \nabla_a r(s, a) | < L }\\ \end{multline} \begin{multline} \shoveleft{ \text{then, } }\\ \shoveleft{ \qquad \nabla_\theta J(\mu_\theta) = \int_S \rho^\mu (s) \nabla_\theta \mu_\theta (s) \nabla_a Q^\mu (s, a) \lvert_{a = \mu_\theta(s)} }\\ \end{multline}이때 일정한 조건을 만족하는 경우에 한해 Variance 가 0으로 수렴하면() Stochastic Policy Gradient가 Deterministic Policy Gradient Theorem으로 수렴한다는 것 또한 증명이 가능하다고 한다.
\begin{multline} \shoveleft{ \text{Consider a stochastic Policy } \pi_{\mu_\theta, \sigma} \text{ such that } \pi_{\mu_\theta, \sigma} (a \lvert s) = v_\sigma(\mu_\theta (s), a) }\\ \shoveleft{ \text{where } \sigma \text{ is a parameter controlling the variance and } v_\sigma \text{ satisfy condition} }\\ \shoveleft{ \text{B.1(see supplementary) and the MDP satisfies conditions A.1, A.2.} }\\ \shoveleft{ \text{Then, } \lim_{\sigma \rightarrow 0} \nabla_\theta J(\pi_{\mu_\theta, \sigma}) = \nabla_\theta J(\mu_\theta) }\\ \end{multline}이에 따라 Stochasitic Policy Gradient Theorem에서 파생되어 나온 다양한 Application(Actor-Critic, Natural Gradient, Compatible Function Approximation 등)에도 Deterministic Policy를 적용할 수 있다는 것을 알 수 있다.
On-Policy Deterministic Actor-Critic
SARSA 업데이트를 사용하는 On-Policy Deterministic Actor-Critic의 업데이트 식을 다음과 같이 정리할 수 있다.
\eqalign{ \delta_t &= r_t + \gamma Q^w (s_{t+1}, a_{t+1}) - Q^w(s_t, a_t)\\ w_{t+1} &= w_t + \alpha_w \delta_t \nabla_w Q^w(s_t, a_t)\\ \theta_{t+1} &= \theta_t + \alpha_\theta \nabla_\theta \mu_\theta(s_t) \nabla_a Q^w (s_t, a_t) \lvert_{a = \mu_\theta(s)} }Off-Policy Deterministic Actor-Critic
Off-Policy에서는 Stochastic Actor-Critic을 참고하여 다음과 같이 Performance Gradient를 정의할 수 있다.
\eqalign{ \nabla_\theta J_\beta(\mu_\theta) &\approx \int_S \rho^\beta(s) [\nabla_\theta \mu_\theta(s) Q^\mu(s,a)] ds \\ &= E_{s \backsim \rho^\beta} [\nabla_\theta \mu_\theta(s) \nabla_a Q^\mu(s,a) \lvert_{a = \mu_\theta(s)} ] }Stochastic Actor-Critic 식과 비교해 볼 때 가장 큰 차이점은 Importance Sampling Term이 사라졌다는 것이다. 이는 Deterministic Policy에서는 동일한 State에 대해 더 이상 다양한 Action을 고려할 필요가 없기 때문이다.
위 식에 근거하는 **Off-Policy Deterministic Actor-Critic(OPDAC)**의 업데이트 식은 다음과 같다. 여기서는 Actor를 업데이트할 때 SARSA가 아닌 Q-learning을 사용하고 있다.
\eqalign{ \delta_t &= r_t + \gamma Q^w (s_{t+1}, \mu_\theta(s_{t+1})) - Q^w(s_t, a_t)\\ w_{t+1} &= w_t + \alpha_w \delta_t \nabla_w Q^w(s_t, a_t)\\ \theta_{t+1} &= \theta_t + \alpha_\theta \nabla_\theta \mu_\theta(s_t) \nabla_a Q^w (s_t, a_t) \lvert_{a = \mu_\theta(s)} }Compatible Function Approximation
위의 Deterministic Actor-Critic에서도 Stochastic에서와 마찬가지로 근사 함수 의 Bias 문제가 발생할 수 있다. 논문에 따르면 아래와 같은 조건을 만족하면 Deterministic Actor-Critic에서도 Performacne Gradient에 영향을 주지 않으면서 를 대체할 수 있는 Critic 를 찾을 수 있다고 한다.
\begin{multline} \shoveleft{ \text{A function approximator } Q^w(s, a) \text{ is compatible with a deterministic policy } \mu_\theta(s), }\\ \shoveleft{ \nabla_\theta J_\beta(\theta) = E[\nabla_\theta \mu_\theta(s) \nabla_a Q^w(s,a) \lvert_{a = \mu_\theta (s)}], \text{ when satisfy conditions below.} }\\ \shoveleft{ \quad \text{1. } \nabla_a Q^w (s,a) \lvert_{a=\mu_\theta(s)} = \nabla_\theta \mu_\theta (s)^\text{T} w }\\ \shoveleft{ \quad \text{2. } w \text{ minimises the MSE} (\theta, w) = E[\epsilon(s; \theta, w)^\text{T} \epsilon(s; \theta, w)] \text{ where } }\\ \shoveleft{ \qquad \epsilon(s; \theta, w) = \nabla_a Q^w(s, a) \lvert_{a = \mu_\theta(s)} - \nabla_a Q^\mu(s, a) \lvert_{a = \mu_\theta(s)} } \end{multline}증명은 가 0이 될 때 최소가 된다는 점에서 시작한다.
\eqalign{ \nabla_w \text{MSE} (\theta, w) &= 0\\ E[\epsilon(s; \theta, w)^\text{T} \epsilon(s; \theta, w)] & = 0 \\ E[\nabla_\theta \mu_\theta (s) \epsilon(s; \theta, w)] & = 0 \\ E[\nabla_\theta \mu_\theta (s) (\nabla_a Q^w(s, a) \lvert_{a = \mu_\theta(s)} - \nabla_a Q^\mu(s, a) \lvert_{a = \mu_\theta(s)})] & = 0 \\ E[\nabla_\theta \mu_\theta (s) \nabla_a Q^w(s, a) \lvert_{a = \mu_\theta(s)}] & = E[\nabla_\theta \mu_\theta (s) \nabla_a Q^\mu(s, a) \lvert_{a = \mu_\theta(s)}\\ \therefore E[\nabla_\theta \mu_\theta (s) \nabla_a Q^w(s, a) \lvert_{a = \mu_\theta(s)}] & = \nabla_\theta J_\theta (\mu_\theta) \text{ or } \nabla_\theta J(\mu_\theta)\\ }이때 첫 번째 조건은 다음과 같은 형태로 를 정의하면 만족한다.
여기서 는 Action에 독립적인 함수로서 State-Value를 근사하게 된다. 따라서 위 식은 와 에 관한 식으로 볼 수 있으므로 우변의 첫 번째 Term은 Advantage Term이 된다.
\eqalign{ Q^w(s,a) - V^v(s) &= (a - \mu_\theta(s))^{\text{T}} \nabla_\theta \mu_\theta(s)^{\text{T}} w\\ A^w(s, a) &= \phi(s,a)^\text{T}w \\ \text{ where } &\phi(s,a) = \nabla_\theta \mu_\theta(s) (a-\mu_\theta(s)) }두 번째 조건에서는 를 구하는 방법이 문제 된다. 를 SARSA 또는 Q-learning과 같은 기본적인 Policy Evaluation 방식을 통해 업데이트한다는 것만으로는 완벽하게 만족할 수 없기 때문이다. 이에 대해서는 어느 정도의 오차를 감수하고 를 찾으면 도 어느 정도 만족할 것이라는 선에서 정리하고 있다. 한 마디로 의 를 업데이트할 때 에 근사하도록 업데이트하면 그것의 Gradient도 비슷해지는 것으로 보겠다는 것이다.