High-Dimensional Continuous Control using Generalized Advantage Estimation

논문 제목 : High-Dimensional Continuous Control using Generalized Advantage Estimation[Last revised 9 Sep 2016 (this version, v5)]

●  논문 저자 : John Schulman 

●  논문 링크 : https://arxiv.org/pdf/1506.02438.pdf

●  이전에 보면 좋은 자료 : 

○  Policy Gradient Methods for Reinforcement Learning with Function Approximation(2000)

○  n-Step Return vs. Lambda-Return

●  함께 보면 좋을 논문 :

○  Trust Region Policy Optimization(2015)

○  Proximal Policy Optimization Algorithms(2017)

---

1  Abstract

• 현존하는 Policy Gradient Method들의 목적은 누적되는 reward들을 optimization하는 것이다.

• 하지만 학습할 때에 많은 양의 sample이 필요로 하고, 들어오는 data가 nonstationarity임에도 불구하고 stable and steady improvement가 어렵다.

• 그래서 이 논문에서는 다음과 같은 방법을 제시한다.
1. TD($\lambda$)와 유사한 advantage function의 exponentially-weighted estimator를 사용하여 policy gradient estimate의 variance를 줄이는 것 
2. policy와 value function에 대한 Trust Region Optimization 사용하는 것

• 3D locomotion tasks에 대한 empirical results는 다음과 같다.
1. bipedal and quadrupedal simulated robots의 달리는 자세를 학습
2. bipedal 사람이 땅에 누워있다가 일어서는 것을 학습

---

2  Discussion

• 지금까지 복잡하고 어려운 control problem에서 Reinforcement Learning(RL)은 high sample complexity 때문에 제한이 되어왔다. 

• 따라서 이 논문에서 그 제한을 풀고자 advantage function의 good estimate를 얻는 "variance reduction"에 대해 연구하였다.
1. "Generalized Advantage Estimator(GAE)"라는 것을 제안했고, 이것은 bias-variance tradeoff를 조절하는 두 개의 parameter $\gamma,\lambda$를 가진다.
2. 또한 어떻게 Trust Region Policy Optimization과 value function을 optimize하는 Trust Region Algorithm의 idea를 합치는 지를 보였다.

• 이렇게 함으로써 보다 더 복잡하고 어려운 control task들을 해결할 수 있었다.

• GAE의 실험적인 입증으로는 robotic locomotion을 simulation하는 domain이다.
1. 실험에서도 보여준 것처럼 [0.9, 0.99]의 범위에서 $\lambda$의 적절한 중간의 값을 통해 best performance를 얻는다.
2. 좀 더 나아가 연구되어야할 점은 adaptive or automatic하도록 estimator parameter $\gamma,\lambda$를 조절하는 방법이다.

---

3  Introduction

• 기본적으로 "parameterized stochastic policy"를 가정한다. 

• 이 때 expected total returns의 gradient에 대한 unbiased estimate를 얻을 수 있는데 이것을 REINFORCE라고 부른다.
1. 하지만 하나의 action의 결과가 과거와 미래의 action의 결과로 혼동되기 때문에 gradient estimator의 high variance는 시간에 따라 scaling된다.

• 또 다른 방법은 Actor-Critic이 있다. 이 방법은 empirical returns보다 하나의 value function을 사용한다. 또한 bias하고 lower variance를 가진 estimator이다.
1. 구체적으로 말하자면, high variance하다면 더 sampling을 하면 되는 반면에 bias는 매우 치명적이다. 다시 말해 bias는 algorithm이 converge하는 데에 실패하거나 또는 local optimum이 아닌 poor solution에 converge하도록 만든다.

• 따라서 이 논문에서는 $\gamma\in [0,1]$ and $\lambda\in [0,1]$에 의해 parameterized estimation scheme인 Generalized Advantage Estimator(GAE)를 다룬다.

• 이 논문을 대략적으로 요약하자면 다음과 같다.
1. 효과적인 variance reduction scheme인 GAE를 다룬다. 또한 실험할 때 batch trust region algorithm에 더하여 다양한 algorithm들에 적용된다.
2. value function에 대해 trust region optimization method를 사용한다. 이렇게 함으로서 더 robust하고 efficient한 방법이 된다.
3. A와 B를 합쳐서, 실험적으로 control task에 neural network policies를 learning하는 데에 있어서 효과적인 algorithm을 얻는다. 이러한 결과는 high-demensional continuous control에 RL을 사용함으로서 state of the art로 확장되었다.

---

4  Preliminaries

• 먼저 policy optimization의 "undiscounted formulation"을 가정한다. (undiscounted formulation에 주목하자.)

• initial state $s_0$는 distribution $\rho_0$으로부터 sampling된 것이다. 

• 하나의 trajectory ($s_0, a_0, s_1, a_1, ...$)는 terminal state에 도달될 때 까지 policy $a_t$ ~ $\pi(a_t | s_t)$에 따라서 action을 sampling하고, dynamics $s_{t+1}$ ~ $P(s_{t+1} | s_t, a_t)$에 따라서 state를 sampling함으로써 생성된다.

• reward $r_t = r(s_t, a_t, s_{t+1})$은 매 time step마다 받아진다.

• 목표는 모든 policies에 대해 finite하다고 가정됨으로서 expected total reward $\sum_{t=0}^{\infty} r_t$를 maximize하는 것이다.

• 여기서 중요한 점은 $\gamma$를 discount의 parameter로 사용하는 것이 아니라 "bias-variance tradeoff를 조절하는 parameter로 사용한다" 는 것이다.

• policy gradient method는 gradient $g := \nabla_\theta \mathbb{E} [\sum_{t=0}^\infty r_t]$를 반복적으로 estimate함으로써 expected total reward를 maximize하는 것인데, policy gradient에는 여러 다른 표현들이 있다.

$$g = \mathbb{E} [\sum_{t=0}^\infty \Phi_t \nabla_\theta \log \pi_\theta (a_t | s_t)]$$

1. 여기서 $\Phi_t$는 아래 중의 하나일 수 있다.
1. $\sum_{t=0}^\infty r_t$: trajectory의 total reward
2. $\sum_{t'=t}^\infty r_t'$: action $a_t$ 후의 reward
3. $\sum_{t'=t}^\infty r_t' - b(s_t)$: 2의 baselined version
   
4. $Q^\pi (s_t, a_t)$: state-action value function
5. $A^\pi (s_t, a_t)$: advantage function
6. $r_t + V^\pi (s_{t+1}) - V^\pi (s_t)$: TD residual
2. 위의 번호 중 4, 5, 6의 수식들은 다음의 정의를 사용한다.
1. $V^\pi (s_t) := \mathbb{E}_{s_{t+1}:\infty, a_t:\infty} [\sum_{l=0}^\infty r_{t+1}]$
2. $Q^\pi (s_t, a_t) := \mathbb{E}_{s_{t+1}:\infty, a_{t+1}:\infty} [\sum_{l=0}^\infty r_{t+l}]$
3. $A^\pi (s_t, a_t) := Q^\pi (s_t, a_t) - V^\pi (s_t)$, (Advantage function)
3. 추가적으로 colon notation $a : b$는 포괄적인 범위 $(a, a+1, ... , b)$이다. (잘 기억해두자. 뒤에 계속해서 colon notation이 나온다.)

• 여기서부터 parameter $\gamma$에 대해 좀 더 자세히 알아보자. parameter $\gamma$는 bias하면서 동시에 reward를 downweighting함으로써 variance를 줄인다. 다시 말해 MDP의 discounted formulation에서 사용된 discounted factor와 일치하지만, 이 논문에서는 "$\gamma$를 undiscounted MDP에서 variance reduction parameter"로 다룬다. -> 결과는 같지만, 의미와 의도가 다르다.

• discounted value function들은 다음과 같다.
1. $V^{\pi, \gamma} (s_t) := \mathbb{E}_{s_{t+1}:\infty, a_t:\infty} [\sum_{l=0}^\infty \gamma^l r_{t+l}]$ 
2. $Q^\pi (s_t, a_t) := \mathbb{E}_{s_{t+1}:\infty, a_{t+1}:\infty} [\sum_{l=0}^\infty \gamma^l r_{t+l}]$
3. $A^{\pi, \gamma} (s_t, a_t) := Q^{\pi, \gamma} (s_t, a_t) - V^{\pi, \gamma} (s_t)$

• 따라서 policy gradient에서의 discounted approximation은 다음과 같이 나타낼 수 있다.

$$g^\gamma := \mathbb{E}_{s_{0:\infty} a_{0:\infty}} [\sum_{t=0}^\infty A^{\pi, \gamma} (s_t, a_t) \nabla_\theta \log \pi_\theta (a_t | s_t)]$$

1. 뒤이어 나오는 section에서는 위의 수식에서 $A^{\pi, \gamma}$에 대해 biased (but not too biased) estimator를 얻는 방법에 대해서 나온다.

• 다음으로 advantage function에서 새롭게 접하는 "$\gamma$-just estimator"의 notation에 대해 알아보자.
1. 먼저 $\gamma$-just estimator는 $g^\gamma$ ${}^1$를 estimate하기 위해 위의 수식에서 $A^{\pi, \gamma}$를 $\gamma$-just estimator로 사용할 때, bias하지 않은 estimator라고 하자. 그리고 이 $\gamma$-just advantage estimator를 $\hat{A}_t (s_{0:\infty} , a_{0:\infty})$라고 하고, 전체의 trajectory에 대한 하나의 function이라고 하자.
2. ${}^1$에서 이 논문의 저자가 하고 싶은 말이 있는 것 같다. 개인적으로 $\gamma$-just estimator를 이해하는 데에 있어서 중요한 주석이라 정확히 해석하고자 한다. 
1. $A^\pi$를 $A^{\pi, \gamma}$로 사용함으로써 이미 bias하다라고 말했지만, "이 논문에서 하고자 하는 것은 $g^\gamma$에 대해 unbiased estimate를 얻고 싶은 것이다." 하지만 undiscounted MDP의 policy gradient에 대해서는 당연히 $\gamma$를 사용하기 때문에 biased estimate를 얻는다. 개인적으로 이것은 일단 무시하고 $\gamma$를 사용할 때 어떻게 unbiased estimate를 얻을 지에 대해 좀 더 포커스를 맞추고 있는 것 같다.
2. 그러니까 저 $A^{\pi, \gamma}$를 $\gamma$-just estimator로 바꿔줌으로써 unbiased estimate를 하고 싶다는 것이 뒤이어 나오는 정의와 명제의 핵심이라고 할 수 있다.

• Definition 1.

먼저 가정을 한다. (가정을 바탕으로 이루어지는 정의라는 것을 주목하자.) 만약

$$\mathbb{E}_{s_{0:\infty} a_{0:\infty}} [\hat{A}_t (s_{0:\infty}, a_{0:\infty}) \nabla_\theta \log \pi_\theta (a_t | s_t)] = \mathbb{E}_{s_{0:\infty} a_{0:\infty}} [A^{\pi, \gamma} (s_t, a_t) \nabla_\theta \log \pi_\theta (a_t | s_t)]$$

두 수식이 같다면, estimator $\hat{A}_t$는 $\gamma$-just이다. 

그리고 만약 모든 t에 대해서 $\hat{A}_t$이 $\gamma$-just이라면, 다음과 같이 표현할 수 있다.

$$\mathbb{E}_{s_{0:\infty} a_{0:\infty}} [\hat{A}_t (s_{0:\infty}, a_{0:\infty}) \nabla_\theta \log \pi_\theta (a_t | s_t)] = g^\gamma$$

위의 수식이 바로 unbiased estimate이다.

$\gamma$-just인 $\hat{A}_t$에 대한 한가지 조건은 $\hat{A}_t$이 두 가지 function $Q_t$ and $b_t$로 나뉠 수 있다는 것이다.

1. $Q_t$는 $\gamma$-discounted Q-function의 unbiased estimator이다.
2. $b_t$는 action $a_t$전에 sampling된 states and actions의 arbitrary function이다.

• Proposition 1.

모든 $(s_t, a_t)$에 대해,

$$\mathbb{E}_{s_{t+1}:\infty, a_{t+1}:\infty | s_t, a_t} [Q_t (s_{t:\infty}, a_{t:\infty})] = Q^{\pi, \gamma} (s_t, a_t)$$

로 인하여 $\hat{A}_t$이

$$\hat{A}_{s_{0:\infty}, a_{0:\infty}} = Q_t (s_{0:\infty}, a_{0:\infty}) - b_t (s_{0:t}, a_{0:t-1})$$

형태라고 가정하자. (가정을 바탕으로 이루어지는 명제라는 점을 주목하자.)

그 때, $\hat{A}_t$은 $\gamma$-just이다.

• 이 명제에 대한 증명은 Appendix B에 있다. 그리고 $\hat{A}_t$에 대한 $\gamma$-just advantage estimator들은 다음과 같다.
1. $\sum_{l=0}^\infty \gamma^l r_{t+1}$
2. $A^{\pi, \gamma} (s_t, a_t)$
3. $Q^{\pi, \gamma} (s_t, a_t)$
4. $r_t + \gamma V^{\pi, \gamma} (s_{t+1}) - V^{\pi, \gamma} (s_t)$

• 증명을 보기 전에 먼저 Advantage function에 대해서 먼저 살펴보자.

아래의 내용은 Sutton이 쓴 논문인 Policy Gradient Methods for Reinforcement Learning with Function Approximation(2000)에서 나온 내용을 리뷰한 것이다. (피지여행 블로그에 추가되어 있다. 블로그는 곧 오픈할 예정이다.)

여기서는 "이 수식은 $\sum_a \frac{\partial \pi (s,a)}{\partial \theta} = 0$이기 때문에 가능해진다.", "즉, 이 수식은 $\pi(s,a)$의 gradient에만 dependent하기 때문에 advantage 역할을 하는 함수들을 넣어도 아무런 상관이 없다"라는 두 문장을 기억해두자.

이제 증명을 보면 된다. (증명을 원래 일일히 다 적으려고 했지만, 수식이 너무 많아서 우선 사진을 첨부를 해야겠다..)

위의 증명 수식에서 Q와 b의 각각 세번째 수식과 마지막 수식을 자세히 보자. 

1. $Q$에 대한 증명

- 빨간색 부분

$\mathbb{E}_{s_{t+1:\infty}, a_{t+1:\infty}} [Q_t (s_{0:\infty}, a_{0:\infty})]$를 쉽게 말하자면 "모든(과거, 현재, 미래) state와 action에 대해서 expectation을 $t+1$부터 $\infty$까지 하겠다."라는 말이다. 이렇게 함으로써 원래는 $Q^\pi (s_t, a_t)$가 나와야 맞는 건데, 앞에서 살펴봤다시피 4번째 수식 밑줄 친 자리에는 advantage 역할을 하는 함수들을 넣어도 결과값에 아무런 영향을 끼치지 않기 때문에 의도적으로 $A^\pi (s_t, a_t)$로 바꾼 것이다. 또한 이 증명을 바탕으로 $\hat{A}$이 $\gamma$-just라는 것을 표현하고 싶기 때문이라고 봐도 된다.

- 파란색 부분

또한 $a_{0:t}$에서 $a_{0:t-1}$로 변한 것은 $A^\pi (s_t, a_t)$에 baseline이 들어가기 때문에 바꿔준 것이다.

2. $b$에 대한 증명

- 빨간색 부분

$\mathbb{E}_{s_{t+1:\infty}, a_{t+1:\infty}} [\nabla_\theta \log \pi_\theta (a_t | s_t)]$가 0으로 바뀌는 것은 위에서 설명했듯이 $\nabla_\theta$자체가 $\log \pi_\theta$만 gradient하기 때문에 이것을 expectation을 취하면 0이 된다.

---

5  Advantage Function Estimation

• 이번 section에는 discounted advantage function $A^{\pi, \gamma} (s_t, a_t)$의 accurate estimate $\hat{A}_t$에 대해서 살펴보자. 이에 따른 수식은 다음과 같다. 

$$\hat{g} = \frac{1}{N} \sum_{n=1}^N \sum_{t=0}^\infty \hat{A}_t^n \nabla_\theta \log \pi_\theta (a_t^n | s_t^n)$$

여기서 n은 a batch of episodes에 대하여 index한 것이다.

• $V$를 approximate value function이라고 하자. 그리고 $\delta_t^V = r_t + \gamma V(s_{t+1}) - V(s_t)$이라고 하자.
1. 만약 (이전과 마찬가지로 가정부터 한다.) correct value function $V = V^{\pi, \gamma}$가 있다고 한다면, 이것은 $\gamma$-just advantage estimator이다.
2. 실제로, $A^{\pi, \gamma}$의 unbiased estimator는 다음과 같다.

$$\mathbb{E}_{s_{t+1}} [\delta_t^{V^{\pi, \gamma}}] = \mathbb{E}_{s_{t+1}} [r_t + \gamma V^{\pi, \gamma} (s_{t+1}) - V^{\pi, \gamma} (s_t)]$$

$$= \mathbb{E}_{s_{t+1}} [Q^{\pi, \gamma} (s_t, a_t) - V^{\pi, \gamma} (s_t)] = A^{\pi, \gamma} (s_t, a_t)$$

그러나, "이 estimator는 유일하게 $V = V^{\pi, \gamma}$에 대한 $\gamma$-just이다." 다른 경우라면 이것은 biased policy gradient estimate일 것이다. (우리가 하고 싶은 것은 $V$에 대해서만 unbiased estimator가 아니라 advantage function에 대해서 일반화된 unbiased estimator를 얻고 싶은 것이다. 그래서 아래에서도 나오겠지만, $\gamma$와 함께 $\lambda$를 이용한 estimator가 나온다.)

• 그래서 $\delta$에 대해 $k$의 sum으로 생각해보자. 이것을 $\hat{A}_t^{(k)}$라고 하자. 그러면 아래와 같이 표현할 수 있다.

1. $\hat{A}_t^{(k)}$은 returns의 $k$-step estimate와 연관지을 수 있고, $\delta_t^V = \hat{A}_t^{(1)}$의 case와 유사하게도 $\hat{A}_t^{(k)}$를 advantage function의 estimator로 생각할 수 있다.

• 여기서 $k \rightarrow \infty$로 생각해보면 bias가 일반적으로 점점 더 작아진다. 왜냐하면 $\gamma^k V(s_{t+k})$가 점점 많이 discounted되서 $-V(s_t)$가 bias에 영향을 미치지 못하기 때문이다. $k \rightarrow \infty$를 취하면 다음과 같은 수식이 나온다.

$$\hat{A}_t^{(\infty)} = \sum_{l=0}^\infty \gamma^l \delta_{t+l}^V = -V(s_t) + \sum_{l=0}^\infty \gamma^l r_{t+l}$$

우변의 수식과 같이 empirical returns에서 value function baseline을 뺀 것으로 나타낼 수 있다.

• Generalized Advantage Estimator GAE($\gamma, \lambda$)는 $k$-step estimators의 exponentially-weighted average로 나타낼 수 있다.

(TD($\lambda$)를 떠올려주세요..!)

1. 위의 마지막 수식에서도 알 수 있듯이, advantage estimator는 Bellman residual terms의 discounted sum과 관련있는 간단한 수식이다. 다음 section에서 modified reward function을 가진 MDP에 returns로서의 관점에서 위의 마지막 수식을 더 자세히 살펴보자.
2. 위의 수식은 TD($\lambda$)와 많이 유사하다. 그러나 TD($\lambda$)는 value function를 estimator하고, 여기서는 advantage function을 estimator한다.

• 위의 수식에서 $\lambda = 0$ and $\lambda = 1$에 대해서는 특별한 case가 존재한다. 수식으로 표현하면 다음과 같다.

1. $GAE(\gamma, 1)$은 $V$의 정확도와 관계없이 $\gamma$-just이다. 그러나 returns의 sum때문에 high variance하다.
2. $GAE(\gamma, 0)$은 $V = V^{\pi, \gamma}$에 대해 $\gamma$-just이다. 그리고 bias하지만 일반적으로 훨씬 lower variance를 가진다. 
3. $0 < \lambda < 1$에 대해 GAE는 parameter $\lambda$를 control하여 bias와 variance사이에 compromise를 만든다.

• 두 가지 별개의 parameter $\gamma$ and $\lambda$를 가진 advantage estimator는 bias-variance tradeoff에 도움을 준다. 그러나 이 두 가지 parameter는 각각 다른 목적을 가지고 작동한다.
1. $\gamma$는 가장 중요하게 value function $V^{\pi, \gamma}$ 의 scale을 결정한다. 또한 $\gamma$는 $\lambda$에 의존하지 않는다. $\gamma < 1$로 정하는 것은 policy gradient estimate에서 bias하다.
2. 반면에, $\lambda < 1$는 유일하게 value function이 부정확할 때 bias하다. 그리고 경험상, $\lambda$의 best value는 $\gamma$의 best value보다 훨씬 더 낮다. 왜냐하면 $\lambda$가 정확한 value function에 대해 $\gamma$보다 훨씬 덜 bias하기 때문이다.

• GAE를 사용할 때, $g^\gamma$의 biased estimator를 구성할 수 있다. 수식은 다음과 같다.

$$g^\gamma \approx \mathbb{E} [\sum_{t=0}^\infty] \nabla_\theta \log \pi_\theta (a_t | s_t) \hat{A}_t^{GAE(\gamma, \lambda)}] = \mathbb{E} [\sum_{t=0}^{\infty} \nabla_\theta \log \pi_\theta (a_t | s_t) \sum_{l=0}^\infty (\gamma \lambda)^l \delta_{t+1}^V]$$

여기서 $\lambda = 1$일 때 동일해진다.

---

6  Interpretation as Reward Shaping

• 이번 section에서는 앞서 다뤘던 수식 $\sum_{l=0}^\infty (\gamma \lambda)^l \delta_{t+l}^V$를 modified reward function의 MDP의 관점으로 생각해보자. 조금 더 구체적으로 말하자면, MDP에서 reward shaping transformation을 실행한 후에 적용된 extra discounted factor로서 $\lambda$를 어떻게 볼 것인지에 대해서 다룬다. 

• (개인적인 comment) 한 가지 먼저 언급하자면, 본래의 목적은 reward shaping이 아니라 variance reduction이다. 이번 section은 그저 이전에 이러한 개념이 있었고, gae를 다른 관점에서 생각해보자라는 뜻에서 나온 section인 것 같다. '아~ 이러한 개념이 있구나~!' 정도로만 알면 될 것 같다. 'gae가 reward shaping의 효과까지 있어서 이러한 section을 넣은 것일까?' 라는 생각도 해봤지만 아직 잘 모르겠다. 실험부분에도 딱히 하지 않은 걸로 봐서는.. 아닌 것 같기도 하고.. 아직까지는 그저 'reward shaping의 관점에서 봤을 때에도 gae로 만들어줄 수 있다.' 정도만 생각하려고 한다.

• Reward Shaping이란 개념 자체는 일반적인 알고리즘 분야(최단경로 문제 등)에도 있다. 하지만 이 개념이 머신러닝에 적용된 건 Andrew Y. Ng이 쓴 Policy Invariance under Reward Transformations Theory and Application to Reward Shaping(1999) 논문이다. 논문에서 Reward Shaping을 설명하는 부분은 간략하게 다음과 같다.

• 위의 글만 보고 이해가 잘 안된다. 그래서 다른 자료들을 찾던 중에 다음의 그림을 찾게 되었다. (아래의 그림은 Youtube에 있는 Udacity 영상에서 있는 그림이다.)

이 그림을 통해서 Reward Shaping을 이해해보자.

Reward Shaping(보상 형성)을 통해서 뭘 하고 싶은지 목적부터 보자. reward space가 sparse 한 경우에 reward가 너무 드문드문 나온다. 따라서 이것을 꾸준히 reward를 받을 수 있도록 바꾼다. potential-based shaping function인 $\Phi$를 만들어서 더하고 빼준다. 저 $\Phi$ 자리에는 대표적으로 state value function이 많이 들어간다고 한다. (아직 목적이 이해가 안될 수 있다. Reward Shaping에 대해서 다 보고 나서 다시 한 번 읽어보자.)

위의 그림은 돌고래가 점프하여 불구멍을 통과해야하는 환경이다. 하지만 저 불구멍을 통과하기 위해서는 (1) 점프도 해야하고, (2) 불도 피해야하고, (3) 알맞게 착지까지 완료해야한다. 이렇게 해야 reward를 +1 얻는다. 

생각해보자. 어느 세월에 점프도 해야하고.. 불도 피해야하고.. 알맞게 착지까지해서 reward를 +1 얻겠는가? 따라서 그 전에도 잘하고 있는 지, 못하고 있는 지를 판단하기 위해, 다시 말해 reward를 꾸준히 받도록 다음과 같이 transformed reward function $\tilde{r}$을 정의한다.

$$\tilde{r} (s, a, s') = r(s, a, s') + \gamma \Phi (s') - \Phi (s)$$

1. 여기서 $\Phi : S \rightarrow \mathbb{R}$를 state space에서의 arbitrary scalar-valued function을 나타낸다. 그리고 $\Phi$자리에는 대표적으로 state value function이 들어간다고 생각하자.

2. 형태가 TD residual term의 결과와 비슷하지만 의미와 의도가 다르다. reward shaping은 sparse reward 때문이고, 이전 section에서 봤던 gae는 variance reduction때문에 나온 것이다.

• 이 transformation은 discounted advantage function $A^{\pi, \gamma}$으로도 둘 수 있다. state $s_t$를 시작하여 하나의 trajectory의 rewards의 discounted sum을 표현하면 다음과 같다.

$$\sum_{l=0}^\infty \gamma^l \tilde{r} (s_{t+l}, a_t, s_{t+l+1}) = \sum_{l=0}^\infty \gamma^l r(s_{t+l}, a_{t+l}, s_{t+l+1}) - \Phi(s_t)$$

• $\tilde{Q}^{\pi, \gamma}, \tilde{V}^{\pi, \gamma}, \tilde{A}^{\pi, \gamma}$를  transformed MDP의 value function과 advantage function이라고 하면, 다음과 같은 수식이 나온다.

$$\tilde{Q}^{\pi, \gamma} (s, a) = Q^{\pi, \gamma} (s, a) - \Phi (s)$$

$$\tilde{V}^{\pi, \gamma} (s, a) = V^{\pi, \gamma} (s, a) - \Phi (s)$$

$$\tilde{A}^{\pi, \gamma} (s, a) = (Q^{\pi, \gamma} (s, a) - \Phi (s)) - (V^\pi (s) - \Phi (s)) = A^{\pi, \gamma} (s, a)$$

• 이제 reward shaping의 idea를 가지고 어떻게 policy gradient estimate를 얻을 수 있는 지에 대해서 알아보자. 
1. $0 \le \lambda \le 1$의 범위에 있는 steeper discount $\gamma \lambda$를 사용한다.
2. shaped reward $\tilde{r}$는 Bellman residual term $\delta^V$와 동일하다.
3. 그리고 $\Phi = V$와 같다고 보면 다음과 같은 수식이 나온다.

$$\sum_{l=0}^\infty (\gamma \lambda)^l \tilde{r} (s_{t+l}, a_t, s_{t+l+1}) = \sum_{l=0}^\infty (\gamma \lambda)^l \delta_{t+l}^V = \hat{A}_t^{GAE(\gamma, \lambda)}$$

이렇게 shaped rewards의 $\gamma \lambda$-discounted sum을 고려함으로써 GAE를 얻을 수 있다. 더 정확하게 $\lambda = 1$은 $g^\gamma$의 unbiased estimate이고, 반면에 $\lambda < 1$은 biased estimate이다. 

• 좀 더 나아가서, shaping transformation과 parameters $\gamma$ and $\lambda$의 결과를 보기 위해, response function $\chi$를 이용하면 다음과 같은 수식이 나온다.

$$\chi (l; s_t, a_t) = \mathbb{E} [r_{t+l} | s_t, a_t] - \mathbb{E} [r_{t+l} | s_t]$$

1. 추가적으로 $A^{\pi, \gamma} (s, a) = \sum_{l=0}^\infty \gamma^l \chi (l; s, a)$이다.

• 그래서 discounted policy gradient estimator는 다음과 같이 쓸 수 있다.

$$\nabla_\theta \log \pi_\theta (a_t | s_t) A^{\pi, \gamma} (s_t, a_t) = \nabla_\theta \log \pi_\theta (a_t | s_t) \sum_{l=0}^\infty \gamma^l \chi (l; s, a)$$

---

7  Value Function Estimation

• 이번 section에서는 value function에 Trust Region Optimization을 사용한다. 따라서 "이번 section을 이해하려면 TRPO 논문을 먼저 읽고 보는 것이 좋다." (꼭!) 또한 밑에도 추가해놨지만, code에서는 따로 쓰지 않는다. 이유도 밑에 적어놓긴 했다. 그래서 건너 뛰어도 되긴하지만, 다시 한 번 TRPO 공부도 할 겸 정리해봤다.

• value function을 나타내기 위한 nonlinear function approximator를 사용할 때, 가장 간단한 방법은 nonlinear regression problem을 해결하는 것이다. 관련 수식은 다음과 같다.

$$minimize_{\phi} \sum_{n=1}^N\parallel V_{\phi} (s_n) - \hat{V}_n \parallel^2$$

여기서 $\hat{V}_t = \sum_{l=0}^\infty \gamma^l r_{t+l}$은 rewards의 discounted sum이다. 그리고 n은 trajectories에서 모든 timesteps에 대한 index이다.

• 뒤에 나오는 실험부분에서, batch optimization procedure에 대한 각각의 iteration에서 value function을 optimize를 하기 위해 trust region method를 사용한다.
1. trust region을 함으로써 overfitting을 피하도록 돕는다.
2. trust region problem을 공식화하기 위해, $\sigma^2 = \frac{1}{N} \sum_{n=1}^N \parallel V_{\phi old} (s_n) - \hat{V}_n \parallel^2$를 계산한다. 여기서 $\phi_{old}$은 optimization전에 이루어진 parameter vector이다. 
3. 따라서 constrained optimization problem의 수식은 다음과 같다.

$$minimize_{\phi} \, \sum_{n=1}^N \parallel V_\phi (s_n) - \hat{V}_n \parallel^2$$

$$subject \, \, to \, \frac{1}{N} \sum_{n=1}^N \frac{\parallel V_\phi (s_n) - V_{\phi old} (s_n) \parallel^2}{2 \sigma^2} \le \epsilon$$

1. 이 constraint는 previous value function과 new value function의 사이를 $\epsilon$보다 더 작게하기 위해 average KL divergence를 constraint하는 것이다. 여기서 value function은 평균 $V_\phi (s)$와 분산 $\sigma^2$를 가진 Gaussian distribution을 parameterize하기 위해 사용된다.

• conjugate gradient algorithm (Wright & Nocedal (1999))을 사용하여 위에 있는 trust region problem의 approximate solution을 계산한다. 수식은 다음과 같다.

$$minimize_{\phi} \, g^T (\phi - \phi_{old})$$

$$subject \, \, to \, \frac{1}{N} \sum_{n=1}^N (\phi - \phi_{old})^T H(\phi - \phi_{old}) \le \epsilon$$

1. 여기서 $g$는 objective의 gradient이고, $H = \frac{1}{N} \sum_n j_n j_n^T$이다. 여기서 $j_n = \nabla_\phi V_\phi (s_n)$이다. 
2. $H$는 objective의 Hessian의 "Gauss-Newton" approximation이다. 그래서 이 $H$는 Fisher information matrix가 된다.
3. conjugate gradient algorithm을 사용하기 위해 matrix-vector products $v \rightarrow Hv$를 사용할 때, step direction $s \approx - H^{-1}g$을 계산한다.
4. 그리고 나서, $\frac{1}{2} (\alpha s)^T H(\alpha s) = \epsilon$에 따라 $s \rightarrow \alpha s$로 rescaling한다. 그리고 $\phi = \phi_{old} + \alpha s$를 해준다.

---

8  GAE code

• 아래에 있는 code는 OpenAI baseline에 있는 code이다. (Github Link)

• TRPO에서 사용된 GAE code이다.

1. code에서 보면 value function에 trust region optimization은 따로 하지 않는다. 왜 그런지는 모르겠다. 개인적인 생각은 저자가 넣고도 해보고 빼고도 해봤더니 성능 차이가 얼마 없었던 것 같다. 또한 단점으로 계산량도 많고, 구현도 복잡해지기 때문에 빼고도 성능이 별 차이가 없다면 빼는 것이 낫다고 생각한 것 같다.
   

• 추가적으로, PPO에서 사용된 GAE code이다. 

---

추가적으로 실험부분도 정리하려고 했지만, 여기까지만 해도 내용이 너무 많기 때문에 실험은 생략하도록 하겠다.