Q-prop 논문 리뷰

Q-prop 리뷰

본제목은 sample efficient policy gradient with an off-policy critic

1. introduction

Major obstacle

high sample complexity in the real world

1.1. Trial

bias-variance trade-off 를 다루기 위해 policy gradient방법을 사용하면
on-policy sample을 수집해야하므로 sample efficiency 문제 발생.
그래서 off-policy 방법으로 시도가 있었다.

1. off-policy actor-critic
2. off-policy Q-learninig

1.2. Limitation

1. biased

   이유: non-linear function approximator로는 알고리즘의 수렴이 보장되지 않음.

2. instability

   sensitive to hyperparameter when using supervision.

1.3. Idea

on-policy policy gradient + off-policy 샘플을 사용한 learning을 하면
correct bias + increase stable learning + sample efficency의 효과를 낼 수 있다.
first-order Taylor expansion을 사용하여 off policy critic을 통한 analytic gradient term 과
advatange approximation과 실제 값의 차이로 구성된 policy gradient term을 더해서 만든다.

1.3.1 Two variant

Q-prop with conservative adaptation -> substantial gain in sample efficency over TRPO and stability over DDPG Q-prop with aggressive adaptation

1.4. Contribution

Real world 적용에 가장 중요한 data efficiency와 learning stability 문제를 해결했다.

1.5. 다른점

1. off-policy learning 과 달리 bias를 더하지 않고 variance를 줄였다.
2. critic기반의 value function으로 on-policy learning하지 않고
   action-value function으로 off-policy learning함으로써
   sample effiency장점을 살리며 variance를 줄였다.

2. Background

2.1. Monte carlo policy gradient method(TRPO)

\[\nabla_{\theta} J (\theta) = \mathbb{E}_{s_{t} \sim \rho_{\pi}(\cdot), a_{t} \sim \pi(\cdot| s_{t})} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (R_{t} - b(s_t))]\]

unbiased estimation 이지만 high variance이고 sample ineffienct하다.

단점 해결을 위한 시도들

1. 어떻게 unbiased estimation에서 variance를 줄일까?
   baseline을 잘 선택하면 된다.
   action value function의 적절한 baseline은 advantage function이다.
2. 어떻게 sample efficiency를 해결할까?
   importance sampling을 통해 off-policy data를 사용하면 된다.
   하지만, action space dimension이 클때 importance weight곱해주게 되어서
   return의 scale이 많이 달라지게 되고 곧 variance의 증가를 초래했다.

2.2. Policy gradient with function approximation(DDPG)
critic을 optimize하는 policy evaluation 과정과
actor를 optimize하는 policy improvement 과정으로
진행해야하지만 full optimization은 expensive하기 때문에
아래 와 같이 stochastic optimziation으로 approximation하여 사용된다.

\[\nabla_{\theta}J(\theta) \approx \mathbb{E}_{s_{t} \sim \rho_{\beta}(\cdot)} [\nabla_{a}Q_{w}(s_t, a)|_{a=\mu_{\theta}(s_t)} \nabla_{\theta}\mu_{\theta}(s_t)] \\\]

여기에서 $\rho_{\beta}$는 replay buffer로 부터 sampling한 state의 분포이고
$\beta$는 임의의 exploration distribution이다.
장점은 off-policy 방법이여서 sample efficient하고 biased estimation이다. 그리고 reinforce gradient에 high variance가 있더라도 비의존적이다.
다시말해, $\nabla_{\theta} \log \pi_{\theta}(a_t | s_t)$ 대한 변화폭이 크더라도 비의존적이라는 말이다. 단점은 수렴성이 보장되지 않고 불안정하다.

3. Q-prop

on-policy의 장점인 수렴안정성을 유지하면서 off-policy의 sample efficiency를 이득을 취하는 방법.
어떻게?

1. unbiased 되어있는 monte carlo policy gradient로 부터 줄발.
2. determinsitic biased estimator를 control 확률변수(variate)의 특정 형태를 사용.
3. baised와 unbiased 두가지 유형의 gradient가 포함된 새로운 estimator를 유도.

3.1. Q-prop Estimator

policy gradient를 위한 Q-prop estimator를 유도하자.

Taylor expension.
임의의 함수 $f(s_t,a_t)$에 대해서 1st order taylor 근사는 $a_t$ 근방의 $\bar{a}_t$에 대해서 \(\bar{f}(s_t,a_t) = f(s_t,\bar{a}_t) + \nabla_a f(s_t, a)|_{a=\bar{a}_t}(a_t - \bar{a}_t)\)

Monte carlo policy gradient로 부터 출발. 1차 taylor 근사를 한 임의의 함수를 더하고 빼서 항을 나눔.

\[\require{cancel} \begin{align} \nabla_{\theta} J (\theta) &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \hat{Q}(s_t,a_t)] \\ &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (\hat{Q}(s_t,a_t) - \bar{f}(s_t,a_t) + \bar{f}(s_t,a_t))] \\ g(\theta) &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \bar{f}(s_t,a_t)] \\ &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (f(s_t,\bar{a}_t) + \nabla_a f(s_t, a)|_{a=\bar{a}_t}(a_t - \bar{a}_t))] \\ &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (f(s_t,\bar{a}_t) + \nabla_a f(s_t, a)|_{a=\bar{a}_t} a_t - \nabla_a f(s_t, a)|_{a=\bar{a}_t} \bar{a}_t))] \\ &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) f(s_t,\bar{a}_t)] + \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \nabla_a f(s_t, a)|_{a = \bar{a}_t} a_t ] - \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \nabla_a f(s_t, a)|_{a=\bar{a}_t} \bar{a}_t] \\ &= \mathbb{E}_{\rho_{\pi}} [\int_{a_t} \cancel{\pi_{\theta}(a_t | s_t)} \frac{\nabla_{\theta} \pi_{\theta}(a_t | s_t)}{\cancel{\pi_{\theta}(a_t | s_t)}} f(s_t, a)|_{a=\bar{a}_t}] + \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \nabla_a f(s_t, a)|_{a=\bar{a}_t} a_t ] - \mathbb{E}_{\rho_{\pi}} [\int_{a_t} \cancel{\pi_{\theta}(a_t | s_t)} \frac{\nabla_{\theta} \pi_{\theta}(a_t | s_t)}{\cancel{\pi_{\theta}(a_t | s_t)}} \nabla_a f(s_t, a)|_{a=\bar{a}_t} \bar{a}_t] \\ &= \mathbb{E}_{\rho_{\pi}} [ f(s_t, a)|_{a=\bar{a}_t} \cancel{\nabla_{\theta} \int_{a_t} \pi_{\theta}(a_t | s_t)}] + \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \nabla_a f(s_t, a)|_{a=\bar{a}_t} a_t ] - \mathbb{E}_{\rho_{\pi}} [ \nabla_a f(s_t, a)|_{a=\bar{a}_t}\bar{a}_t \cancel{\nabla_{\theta} \int_{a_t} \pi_{\theta}(a_t | s_t)}] \\ &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) \nabla_a f(s_t, a)|_{a=\bar{a}_t} a_t ] \\ &= \mathbb{E}_{\rho_{\pi}} [\int_{a_t} \nabla_{\theta} \pi_{\theta}(a_t | s_t) \nabla_a f(s_t, a)|_{a=\bar{a}_t} a_t ] \\ &= \mathbb{E}_{\rho_{\pi}} [\nabla_a f(s_t, a)|_{a=\bar{a}_t} \int_{a_t} \nabla_{\theta} \pi_{\theta}(a_t | s_t) a_t ] \\ &= \mathbb{E}_{\rho_{\pi}} [\nabla_a f(s_t, a)|_{a=\bar{a}_t} \nabla_{\theta} \mathbb{E}_{\pi}[a_t]] \\ &= \mathbb{E}_{\rho_{\pi}} [\nabla_a f(s_t, a)|_{a=\bar{a}_t} \nabla_{\theta} \mu_{\theta}(s_t)] \\ \therefore \nabla_{\theta} J (\theta) &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (\hat{Q}(s_t,a_t) - \bar{f}(s_t,a_t))] + \mathbb{E}_{\rho_{\pi}} [\nabla_a f(s_t, a)|_{a=\bar{a}_t} \nabla_{\theta} \mu_{\theta}(s_t)] \end{align}\]

유도된 위의 식에서 $f$ 대신에 $Q_w$(critic)를 대입하고,
$\bar{a}t$ 대신에 $\mu{\theta}(s_t)$(actor)를 대입.

\[\nabla_{\theta} J (\theta) = \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (\hat{Q}(s_t,a_t) - \bar{Q_w}(s_t,a_t))] + \mathbb{E}_{\rho_{\pi}} [\nabla_a Q_w (s_t, a)|_{\mu_{\theta}(s_t)} \nabla_{\theta} \mu_{\theta}(s_t)]\]

on-policy 항의 action value function에서 advantage function의 관점으로 변경.

\[\begin{align} \nabla_{\theta} J (\theta) &= \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (\hat{A}(s_t,a_t) - \bar{A_w}(s_t,a_t))] + \mathbb{E}_{\rho_{\pi}} [\nabla_a Q_w (s_t, a)|_{\mu_{\theta}(s_t)} \nabla_{\theta} \mu_{\theta}(s_t)] \\ \bar{A}(s_t,a_t) &= \bar{Q}(s_t, a_t) - \mathbb{E}_{\pi_{\theta}}[\bar{Q}(s_t, a_t)] \\ &= \nabla_a Q_w (s_t, a)|_{a = \mu_{\theta}(s_t)}(a_t - \mu_{\theta}(s_t)) \end{align}\]

이로써 Monte carlo policy gradient 식에서
residual reinforce graident term과 analytic gradient term 의 합으로 유도했다.
이렇게하면 critic의 off-policy로 update가능하고,
actor는 on-policy로 update가능하다.

3.2. Control variate analysis and adaptive Q-prop

직관적으로 생각했을 때 $Q_w$가 $Q_{\pi}$를 잘 근사할수록 분산도 작을 것이고,
수렴속도도 향상시킬 것이다. 그런데 control variate analysis에서
그럴 필요없이 critic의 approximation error만 줄이면 분산이 줄어든다는 것을 보일 것이다.
control variate를 조절하는 weighing variable인 $\eta(s_t)$를 도입해보자.
그러면 Q-prop gradient는 아래와 같이 표현된다.

\[\nabla_{\theta} J (\theta) = \mathbb{E}_{\rho_{\pi}, \pi} [\nabla_{\theta} \log \pi_{\theta}(a_t | s_t) (\hat{A}(s_t,a_t) - \eta(s_t) \bar{A_w}(s_t,a_t))] + \mathbb{E}_{\rho_{\pi}} [\eta(s_t)\nabla_a Q_w (s_t, a)|_{\mu_{\theta}(s_t)} \nabla_{\theta} \mu_{\theta}(s_t)]\]

$\eta(s_t)$ 를 도입하더라도
$-\eta(s_t)\bar{f}(s_t, a_t) + \eta(s_t)\bar{f}(s_t, a_t) = 0$ 이기 때문에
bais가 생기지는 않는다.

original MCPG의 estimator variance는 아래와 같다.
\(Var = \mathbb{E}_{\rho_{pi}}[\sum_{m}Var_{a_t}(\nabla_{\theta_{m}} \log \pi_{\theta} (a_t| s_t) \hat{A}(s_t, a_t))]\)

Q-prop gradient의 경우 off-policy 부분인 analytic gradient term은
biased estimator인 대신 variance가 0 이라고 생각하면
Q-prop gradient estimator variance는 on-policy 부분인
residual reinforce graident term만 고려하여 아래와 같다. \(Var^{*} = \mathbb{E}_{\rho_{pi}}[\sum_{m}Var_{a_t}(\nabla_{\theta_{m}} \log \pi_{\theta} (a_t| s_t) (\hat{A}(s_t, a_t) - \eta(s_t)\bar{A}(s_t, a_t)))]\)

만약 Var*< Var 를 만족하는 $\eta(s_t)$를 고른다면 variance를 줄일 수 있다.
하지만 직접 variance를 구하는 것은 사실상 non-trivial하다.
이유는

1. optimal baseline을 계산하는 것을 어렵다.
2. 실제로 하나의 같은 state에서 여러개의 action sample을 얻는 것이 불가능하다.

대신에 저자는 아래와 같은 surrogate variance를 제시했다.
\(\begin{align} Var &= \mathbb{E}_{\rho_{\pi}}[Var_{a_t}(\hat{A}(s_t, a_t))] \\ Var^{*} &= \mathbb{E}_{\rho_{\pi}}[Var_{a_t}(\hat{A}(s_t, a_t) - \eta(s_t)\bar{A}(s_t, a_t))] \\ &= \mathbb{E}_{\rho_{\pi}}[\mathbb{E}_{\pi}[(\hat{A}(s_t, a_t) - \eta(s_t)\bar{A}(s_t, a_t))^2]] \;\;,since\;\; \mathbb{E}_{\pi}[\hat{A}(s_t, a_t)] = \mathbb{E}_{\pi}[\bar{A}(s_t, a_t)] = 0 \\ &= \mathbb{E}_{\rho_{\pi}}[\mathbb{E}_{\pi}[\hat{A}(s_t, a_t)^{2}] - 2\eta(s_t)\mathbb{E}_{\pi}[\hat{A}(s_t, a_t)\bar{A}(s_t, a_t) + \eta(s_t)^{2}\mathbb{E}_{\pi}[\bar{A}(s_t, a_t)^{2}]] \\ &= Var + \mathbb{E}_{\rho_{\pi}}[- 2\eta(s_t) Cov_{a_t}(\hat{A}(s_t, a_t), \bar{A}(s_t, a_t)) + \eta(s_t)^{2} Var_{a_t}(\bar{A}(s_t, a_t))] \end{align}\)

여기서 $\bar{A}(s_t,a_t) = \nabla_{a} Q_{w} (s_t, a)

{a = \mu{\theta} (s_t)} (a_t - \mu_{\theta}(s_t))$ 이므로 $\sum_{\theta}(s_t)$를 stochastic policy $\pi_{\theta}$의 covariance matrix라고 할 때 analytic gradient term의 variance 추가항은 아래와 같다.

\(\begin{align} Var_{a_t}(\bar{A}(s_t, a_t)) &= \mathbb{E}_{\pi}[\bar{A}(s_t, a_t)^{2}] \\ &= \nabla_a Q_w (s_t, a)|_{a = \mu_{\theta}(s_t)}^{T} \sum_{\theta}(s_t) \nabla_a Q_w (s_t, a)|_{a = \mu_{\theta}(s_t)} \end{align}\) 위의 식으로 부터 gradient estimator의 variance를 조절하는 Q-prop의 adaptive 확률변수를 유도했다.

3.2.1. Adaptive Q-prop

$\eta^{*}(s_t) = \frac{Cov_{a_t}(\hat{A}(s_t, a_t), \bar{A}(s_t, a_t))}{Var_{a_t}(\bar{A}(s_t, a_t))}$ 로 두면
\(\begin{align} Var^{*} &= \mathbb{E}_{\rho_{\pi}}[Var_{a_t}(\hat{A}(s_t, a_t)) - \frac{Cov_{a_t}(\hat{A}(s_t, a_t), \bar{A}(s_t, a_t))}{\cancel{Var_{a_t}(\bar{A}(s_t, a_t))}}\cancel{Var_{a_t}(\bar{A}(s_t, a_t))}] \\ &= \mathbb{E}_{\rho_{\pi}}[(1 - \frac{Cov_{a_t}(\hat{A}(s_t, a_t), \bar{A}(s_t, a_t))}{Var_{a_t}(\hat{A}(s_t, a_t))})Var_{a_t}(\hat{A}(s_t, a_t))] \\ &= \mathbb{E}_{\rho_{\pi}}[(1 - \rho_{corr}(\hat{A}, \bar{A})^2) Var_{a_t}(\hat{A})] \end{align}\)

따라서 만약 $\hat{A}$ 와 $\bar{A}$ 가 correlate 되어 있는 만큼 variance는 줄어드는 것을 보장한다. 즉, adaptive Q-prop에서 variance는 $Q_w$가 $Q_{\pi}$를 잘 근사하는것에 의존적이지 않는다는 것을 보였다.

3.2.2 Conservative and Aggressive Q-prop

두가지 실행법이 있다.

1. conservative Q-prop $\mathbb{1}(\hat{Cov}_{a_t}(\hat{A}, \bar{A}) > 0)$
2. aggressive Q-prop $sign(\hat{Cov}_{a_t}(\hat{A}, \bar{A}))$

첫번째, conservative Q-prop은 1차 approximation에 대해서 uncorrelated 되어있는 샘플에 대해서는 Q-prop하지 않는 방법이다.
두번째, aggressive Q-prop은 범위를 sign 과 같은 squash function을 사용하여 -1,1 사이로 bound시켜서 variance가 너무 급격히 커지거나 작아지지 않게 적용하는 방법이다.

3.3. Limitation

1. simulation rollout 시간이 빠를 때, critic이 학습되는 시간에서 bottleneck이 될 수 있음
2. bad critic에 강인한 나머지 critic 학습이 잘 안될 수 있음