REINFORCE 알고리즘의 단점은 policy를 update하기 위해서 Episode가 끝날 때까지 기다려야 하고, gradient의 분산이 매우 크다.
A2C는 REINFORCE를 일부 고쳐 성능을 훨씬 능가했다.

Asynchronous Methods for Deep Reinforcement Learning, 2016

1. Gradient of the objective function 재구성

$\nabla_\theta\ J(\theta)=\mathbb{E}_{\tau \sim p_\theta(\tau)}[\sum_{t=0}^T(\gamma^t*\nabla_\theta*log\ \pi_\theta(\mathbf{a_t|x_t})*(\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_k,a_k})))]$

Episode의 전체 trajectory($\tau$)에 대한 기댓값으로 한다면,
시간스텝 k=t부터 episode가 종료되는 T까지 받을 수 있는 Reward-to-go(감가 예정 보상)의 총합인 반환값 $G_t=\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_k, a_k})$

$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ \mathbb{E}_{\tau \sim p_\theta(\tau)}[\gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})*(\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_k,a_k}))]$

1.1 $G_t$ 재정의

$\tau = (\mathbf{x_0, a_0, x_1, a_1, ... , x_T, a_T})$
$= (\mathbf{x_0, a_0, ... , x_t, a_t}) \cup (\mathbf{x_t,a_t,...,x_T,a_T})$
$=\tau_{\mathbf{x_0:a_t}} \cup \tau_{\mathbf{x_{t+1}:a_T}}$

$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ \int_{\tau_{\mathbf{x_0:a_t}}} \int_{\tau_{\mathbf{x_{t+1}:a_T}}} (\gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})*(\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_k,a_k}))*p_\theta(\tau_{\mathbf{x_{0}:a_{t}}}, \tau_{\mathbf{x_{t+1}:a_T}})\ d\tau_{\mathbf{x_{t+1}:a_T}} d\tau_{\mathbf{x_{0}:a_t}}$

$=\sum_{t=0}^T\ \int_{\tau_{\mathbf{x_0:a_t}}} \int_{\tau_{\mathbf{x_{t+1}:a_T}}} (\gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})*(\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_k,a_k}))*p_\theta(\tau_{\mathbf{x_{t+1}:a_{T}}}| \tau_{\mathbf{x_{0}:a_t}})\ p(\tau_{\mathbf{x_0:a_t}})\ d\tau_{\mathbf{x_{t+1}:a_T}} d\tau_{\mathbf{x_{0}:a_t}}$

$=\sum_{t=0}^T\ \int_{\tau_{\mathbf{x_0:a_t}}} (\gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ [\ \int_{\tau_{\mathbf{x_{t+1}:a_T}}} (\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_k,a_k}))*p_\theta(\tau_{\mathbf{x_{t+1}:a_{T}}}| \tau_{\mathbf{x_{0}:a_t}})\ d\tau_{\mathbf{x_{t+1}:a_T}}]\ p(\tau_{\mathbf{x_0:a_t}})\ d\tau_{\mathbf{x_{0}:a_t}}$

Markov 가정에 의해서 다음과 같이 Action-state value function으로 표현
$\int_{\tau_{\mathbf{x_{t+1}:a_T}}} (\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_k,a_k}))*p_\theta(\tau_{\mathbf{x_{t+1}:a_{T}}}| \tau_{\mathbf{x_{0}:a_t}})\ d\tau_{\mathbf{x_{t+1}:a_T}}$
$=r(\mathbf{x_t,a_t})+\int_{\tau_{\mathbf{x_{t+1}:a_T}}} (\sum^T_{k=t+1}\gamma^{k-t}*r(\mathbf{x_k,a_k}))*p_\theta(\tau_{\mathbf{x_{t+1}:a_{T}}}| \tau_{\mathbf{x_{0}:a_t}})\ d\tau_{\mathbf{x_{t+1}:a_T}}$

$=Q^{\pi_\theta}(\mathbf{x_t,a_t})$

__
위 식을 대입하면

$\nabla_\theta J(\theta)=\sum_{t=0}^T\ \int_{\tau_{\mathbf{x_0:a_t}}} \gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ p(\tau_{\mathbf{x_0:a_t}})\ d\tau_{\mathbf{x_{0}:a_t}}$

$=\sum_{t=0}^T\ \int_{\mathbf{(x_t,a_t)}} \gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ p_{\theta}(\mathbf{x_t,a_t})\ d{\mathbf{x}_t}\ d{\mathbf{a}_t}$

Margin Probablity Density Function
random variable $X$와 $Y$의 joint pdf로부터 $X$만의 PDF를 구할 수 있는데, 이를 $X$의 marginal density function이라고 한다. 이 때 X의 pdf라고 하지 않고 mdf로 부르는 이유는 $X$가 다른 random varibale과 joint distribution을 갖는 random variable라는 것을 강조하기 위해서.
$p_X(x)=\int^{\infin}_{-\infin}p_{XY}(x,y)dy$

$p_{\theta}(\mathbf{x_t,a_t})$ 는 나머지 변수를 무시하고 관심 변수인 ($\mathbf{x_t},\mathbf{a_t}$)의 marginal probability density function
$p_{\theta}(\mathbf{x_t,a_t})=p_{\theta}(\mathbf{a_t|x_t})p_\theta(\mathbf{x_t})=\pi_\theta(\mathbf{a_t|x_t})p_\theta(\mathbf{x_t})$

$=\sum_{t=0}^T\ \int_{\mathbf{(x_t,a_t)}} \gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ \pi_\theta(\mathbf{a_t|x_t})p_\theta(\mathbf{x_t})\ d{\mathbf{x}_t}\ d{\mathbf{a}_t}$
$=\sum_{t=0}^T\ \mathbb{E}_{\mathbf{x}_t \sim p_\theta(\mathbf{x}_t),\ \mathbf{a}_t \sim \pi_\theta(\mathbf{a}_t|\mathbf{x}_t)} [\gamma^t*\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ ]$

여기서 상태변수 $\mathbf{x}_t$의 감가된 pdf라고 하면, $\gamma^t$는 episode의 후반부 trajectory에 있는 data 이용도를 크게 떨어뜨리는 단점이 있다. 따라서 이를 상태변수 $\mathbf{x}_t$의 감가된 형태의 pdf $d_\theta(\mathbf{x}_t)=\gamma^t*p_\theta(\mathbf{x}_t)$로 종속한다.
$=\sum_{t=0}^T\ \mathbb{E}_{\mathbf{x}_t \sim d_\theta(\mathbf{x}_t),\ \mathbf{a}_t \sim \pi_\theta(\mathbf{a}_t|\mathbf{x}_t)} [\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ ]$

$d_\theta$를 $p_\theta$로 변환하여 $\gamma^t$를 제거한다.
그러면, 이전 반환값 $G_t$가 아닌 action-value function이 자리한다.
이제 Episode가 끝나 $G_t$를 기다릴 필요가 없다.
기대되는 $G_t$의 기댓값인 action-value $Q^{\pi_\theta}(\mathbf{x_t,a_t})$를 예측하여 Gradient of the objective function을 계산한다.

$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ \mathbb{E}_{\mathbf{x}_t \sim p_\theta(\mathbf{x}_t),\ \mathbf{a}_t \sim \pi_\theta(\mathbf{a}_t|\mathbf{x}_t)} [\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ ]$

2. 분산을 감소시키는 방법

• 분산이 크다면 랜덤 변수가 취하는 실제 값이 평균으로부터 멀리 그리고 넓게 산재
• 분산이 작다면 실제 값이 평균 값 근처에 몰려 있다는 뜻.

Gradient of Objective Function의 분산이 크다면 update될 policy parameter($\theta$) 값 변동이 심해 신경망 학습이 불안정해지고, policy의 불확실성이 커짐.

2.1 baseline 이용하여 분산 줄이기

$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ \mathbb{E}_{\mathbf{x}_t \sim p_\theta(\mathbf{x}_t),\ \mathbf{a}_t \sim \pi_\theta(\mathbf{a}_t|\mathbf{x}_t)} [\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ ]$

$=\sum_{t=0}^T\ \int_{\mathbf{(x_t,a_t)}}\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ \pi_\theta(\mathbf{a_t|x_t})p_\theta(\mathbf{x_t})\ d{\mathbf{x}_t}\ d{\mathbf{a}_t}$

위 적분항에서 $Q^{\pi_\theta}(\mathbf{x_t,a_t})$ 대신에 어떤 parameter $b_t$를 넣으면,

$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ (\int_{\mathbf{(x_t,a_t)}}\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ b_t\ \pi_\theta(\mathbf{a_t|x_t})p_\theta(\mathbf{x_t})\ d{\mathbf{x}_t}\ d{\mathbf{a}_t}$)

관계식 $\nabla_\theta\ log\ \pi_\theta(\mathbf{a_t|x_t})=\cfrac{\nabla_\theta\ \pi_\theta(\mathbf{a_t|x_t})}{\pi_\theta(\mathbf{a_t|x_t})}$ 를 대입

$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ (\int_{\mathbf{(x_t,a_t)}}\nabla_\theta\ \pi_\theta(\mathbf{a_t|x_t})\ b_t\ p(\mathbf{x_t})\ d{\mathbf{x}_t}\ d{\mathbf{a}_t}$)
$=\sum_{t=0}^T\ (\int_{\mathbf{x_t}}[\int_{\mathbf{a_t}}\nabla_\theta\ \pi_\theta(\mathbf{a_t|x_t})\ b_t\ d\mathbf{a}_t] \ p_\theta(\mathbf{x_t})\ d{\mathbf{x}_t}$

$b_t$가 상수이거나, $\mathbf{a_t}$ 함수가 아니라고 가정하면,
위의 대괄호 식 $\int_{\mathbf{a_t}}\nabla_\theta\ \pi_\theta(\mathbf{a_t|x_t})\ b_t\ d\mathbf{a}_t = b_t\nabla_\theta \int_{\mathbf{a_t}} \pi_\theta(\mathbf{a_t|x_t})d\mathbf{a_t}=b_t*\nabla_\theta(1)=0$

적분항에서 $Q^{\pi_\theta}(\mathbf{x_t,a_t})$ 대신에 action $\mathbf{a_t}$에 무관한 상수 $b_t$를 넣으면
$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ (\int_{\mathbf{(x_t,a_t)}}\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ b_t\ \pi_\theta(\mathbf{a_t|x_t})p_\theta(\mathbf{x_t})\ d{\mathbf{x}_t}\ d{\mathbf{a}_t}$) = 0

따라서 Gradient of objective function 식에 $Q^{\pi_\theta}(\mathbf{x_t,a_t})$에서 $b_t$를 빼도 기댓값은 변하지 않는다.
$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ \mathbb{E}_{\mathbf{x}_t \sim p_\theta(\mathbf{x}_t),\ \mathbf{a}_t \sim \pi_\theta(\mathbf{a}_t|\mathbf{x}_t)} [\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ \{Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ - b_t\}]$
여기서 $b_t$를 baseline이라 한다.
baseline은 Gradient of objective function의 분산이 줄기 위해 도입/
따라서 $b_t$의 최적값으로 일반적으로 $\mathbf{a_t}$에 무관한 state-value 함수인 $V^{\pi_\theta}(\mathbf{x}_t)$를 baseline으로 사용.

state-value function은
$V^\pi(\mathbf{x}_t)=\mathbb{E}[Q^\pi(\mathbf{x_t,a_t})]=\int_{\mathbf{a}_t}Q^\pi(\mathbf{x_t,a_t})\pi(\mathbf{a_t|x_t})d\mathbf{a}_t$

baseline은 아래 Advantage function으로 $\mathbf{x}_t$ 상태에서 선택한 행동 $a_t$가 평균에 비해 얼마나 좋은지 평가하는 척도로 해석.

$A^{\pi_\theta}(\mathbf{x_t,a_t})=Q^{\pi_\theta}(\mathbf{x_t,a_t})-V^{\pi_\theta}(\mathbf{x}_t)$

$\nabla_\theta\ J(\theta)=\sum_{t=0}^T\ \mathbb{E}_{\mathbf{x}_t \sim p_\theta(\mathbf{x}_t),\ \mathbf{a}_t \sim \pi_\theta(\mathbf{a}_t|\mathbf{x}_t)} [\nabla_\theta log\ \pi_\theta(\mathbf{a_t|x_t})\ \{Q^{\pi_{\theta}}(\mathbf{x_t,a_t})\ - V^{\pi_\theta}(\mathbf{x}_t)\}]$

이렇게 Action-state가 아닌 Advantage에 Gradient of objective function을 비례하게 하면, Advantage 정의 상 그 값이 Action-state 함수보다 작으므로 gradient의 분산이 작아질 것이라고 기대할 수 있다.

하지만, Advantage 값을 모르기 때문에, 분산을 줄이기 위해 advantage 함수를 얼마나 정확하게 추정하느냐에 따라 $\nabla_\theta J(\theta)$의 분산을 줄이는 것이 달려 있다.

---

3. A2C 알고리즘

Gradient of Objective Function은 샘플링 기법을 이용하여 다음과 같이 근사적 계산
$\nabla_\theta J(\theta) \approx \sum^T_{t=0}[\cfrac{1}{M}\sum^M_{m=1}(\nabla_\theta log\ \pi_\theta(\mathbf{a_t}^{(m)}|\mathbf{x_t}^{(m)})\ A^{\pi_\theta}(\mathbf{x_t^{(m)},\mathbf{a_t^{m}}}))]$

여기서 $m$은 $m$번째 Epsidoe를 뜻하며, $M$은 에피소드의 개수

한개의 Episode만 고려하면 근사적 Gradient of Objective function은
$\nabla_\theta J(\theta) \approx \sum^M_{m=1}(\nabla_\theta log\ \pi_\theta(\mathbf{a_t}^{(m)}|\mathbf{x_t}^{(m)})\ A^{\pi_\theta}(\mathbf{x_t^{(m)},\mathbf{a_t^{m}}}))$

이제 Advantage를 계산하기 위해 action-value 함수의 식을 이용
$Q^\pi(\mathbf{x_t,a_t})=r(\mathbf{x_t,a_t})+\mathbb{E}_{\mathbf{x}_{t+1}\sim p(\mathbf{x_{t+1}|\mathbf{x_t, a_t})}}[\gamma*V^\pi(\mathbf{x}_{t+1})]$

Advantage는 다음과 같이 value 함수로만 근사될 수 있음
기댓값이 아닌 것으로 근사하는 이유는 $\mathbf{x}_t$에서 $a_t$를 선택했을 때 transition probability를 모를뿐더러 $\mathbf{x}_{t+1}$로 확정적으로 이동하기 때문이다.
$A^{\pi_\theta}(\mathbf{x_t,a_t})=Q^{\pi_\theta}(\mathbf{x_t,a_t})-V^{\pi_\theta}(\mathbf{x}_t)$
$\approx r(\mathbf{x_t,a_t})+\gamma*V^{\pi_\theta}(\mathbf{x}_{t+1})-V^{\pi_\theta}(\mathbf{x}_t)$

이제 advantage를 계산하는 문제는 state-value를 얼마나 정확히 계산하느냐의 문제
state-value를 정확히 계산하기 위해 policy network를 이용해 policy를 근사했듯이
다른 network를 이용해 state-value를 근사한다.

policy network는 $\pi_\theta(\mathbf{a_t|x_t})$를 추정하고, value network는 $\phi$ parameter화된 가치함수로 $V_\phi(\mathbf{x}_t) \approx V^{\pi_\theta}(\mathbf{\mathbf{x}_t})$ 다음을 근사한다.
A2C에서는 총 2개의 신경망이 작동한다.

• Actor network: policy network로써 agent가 어떻게 행동해야 하는지 알려줌
• Critic network: value network로써 action을 평가함.
  두 신경망이 중첩되는 부분이 많아서 hidden layer는 공유하고 출력층은 $\pi_\theta(\mathbf{a_t|x_t})$ 값을 내고 $\mathbf{a_t}$ 갯수만큼과 $V_\phi(\mathbf{x}_t)$ 값을 낸다.
  총 $\mathbf{a}_t+1$ 개의 출력을 가진다.

3.1 Critic Network Loss

벨만 방정식에 의해, 현재 state와 다음 state의 value function은 다음과 같은 관계가 있다.
$V^\pi(\mathbf{x}_t)=\mathbb{E}_{\mathbf{a}_t\sim \pi(\mathbf{a_t|x_t})}[r(\mathbf{x_t,a_t})+\mathbb{E}_{\mathbf{x}_{t+1}\sim p(\mathbf{x_{t+1}|x_t, a_t})}[\gamma*V^\pi(\mathbf{x}_{t+1})]$

따라서 state-value 함수를 근사하는 함수는 하나의 action($\mathbf{a}_t$)을 이미 행했다고 가정하면 기댓값이 아닌 다음과 같이 추정. 무수히 많은 action을 하면 할수록 $V_\phi(\mathbf{x}_t)$가 위의 벨만 방정식에 근사하게 됨.
$V_\phi(\mathbf{x}_t)=r(\mathbf{x_t,a_t})+\gamma*V_\phi(\mathbf{x}_t)$

TD target을 $y_i=r(\mathbf{x_t,a_t})+\gamma*V_\phi(\mathbf{x}_t)$로 설정하면
다음 loss 함수가 최소가 되도록 근사 가치함수 $V_\phi(\mathbf{x}_t)$를 추정할 수 있음
$Loss_{critic}(\phi)=\cfrac{1}{2}\sum_i||r(\mathbf{x_i,a_i})+\gamma*V_\phi(\mathbf{x}_{i+1})-V_\phi(\mathbf{x}_i))||^2$

여기서 Transition data는 $\mathbf{(x_i, a_i, r(x_i,a_i), x_{i+1}})$이고,
일정 step N동안 모으면 Transition sample 수도 N개가 된다.
Advantage 함수는 다음과 같이 근사적으로 계산
$A_\phi(\mathbf{x_i, a_i})=r(\mathbf{x_i, a_i})+\gamma*V_\phi(\mathbf{x}_{i+1})-V_\phi(\mathbf{x}_i)$

3.2 Actor Network Loss

Gradient of Objetive function이 $\nabla_\theta J(\theta)=\sum^T_{t=0}(\mathbb{E_{\mathbf{x_t\sim p_\theta(x_t),\ a_t \sim \pi_\theta(a_t|x_t)}}}[\nabla_\theta log \pi_\theta(\mathbf{a_t|x_t})A^{\pi_\theta}(\mathbf{x_t,a_t})])$ 이고
sampling 기법을 활용한 근사는
$\nabla_\theta\ J(\theta) \approx \sum^T_{t=0}(\nabla_\theta\ log \pi_\theta(\mathbf{a_t|x_t})A^{\pi_\theta}{\mathbf{(x_t,a_t)})}$
$A^{\pi_\theta}$가 $\theta$가 아니라 $\phi$에 parameter했기 때문에

$\nabla_\theta\ J(\theta) \approx \nabla_\theta \sum^T_{t=0} log\ \pi_\theta(\mathbf{a_t|x_t})A^{\phi}(\mathbf{x_t, a_t})$이다.

이를 $\theta$에 대해 적분하면
$J(\theta)=\sum^T_{t=0} log\ \pi_\theta(\mathbf{a_t|x_t})A^{\phi}(\mathbf{x_t, a_t})$
loss 함수는 objective function의 부호가 반대이므로

Actor 신경망의 loss함수는
$Loss_{actor}(\theta)=-\sum_i(log\ \pi_\theta(\mathbf{a_i|x_i})*A_\phi(\mathbf{x_i, a_i}))$

loss 함수는 이진분류 문제에서 참값이 항상 1인 Cross Entropy에 Advantage를 곱한 형태

• 따라서 Advantage가 큰 policy의 Sample은 gradient update 시 더 큰 영향을 끼침
• Advantage가 작은 policy의 Sample은 덜 영향을 끼쳐 점진적으로 policy 향상될 것

$\pi_\theta$가 작을수록 애매한 action $\mathbf{a_i}$를 행했기 때문에 loss 값이 커진다고도 볼 수 있다.

3.3 A2C pseudocode