1. Objective Function(목적함수)

강화학습의 목표

• return 값의 기댓값으로 이루어진 $J$(목적함수)를 최대로 만드는 정책($\pi(\mathbf{x_t|a_t})$) 구하는 것
• Policy가 Parameter화된 것이 $\pi_{\theta}(\mathbf{a_t|x_t})$라면, $J(\theta)$를 최대로 만드는 policy parameter($\theta$)를 계산하는 것

$\theta^*=argmax \ J(\theta)$, $J(\theta)=\mathbb{E_{\tau \sim p_0(\tau)}}[\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t})]$

변수	설명
$r(\mathbf{x_t,a_t})$	시간 t일 때 state 변수($\mathbf{x}_t$)에서 action($\mathbf{a_t}$)를 했을 때 agent가 받는 보상
$\gamma$	discount factor(감가율) 0~1
$\tau$	policy($\pi_{\theta})$로 생성되는 trajectory(궤적). $(\mathbf{x_0,a_0,x_1,a_1,...x_T,a_T})$
$p_\theta(\tau)$	정책 $\pi_{\theta}$로 생성되고, 기댓값 계산 시 사용하는 확률밀도함수

policy($\pi_{\theta}$)는 보통 neural network로 parameter화됨.

• $\theta$는 NN의 모든 weight

1.1 Total Discount reward

t=0부터 Episode가 종료될 때까지 받을 수 있는 전체 Trajectory에 대한 Total discount Reward

• $G_0=\sum^T_{t=0}\gamma^t*r(\mathbf{x_t, a_t})$

임의의 시간 k=t부터 Episode가 종료될 때까지 받을 수 있는 Reward-to-go(예정 보상)

• $G_t=\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x_t,a_t})$

위의 확률 $p_{\theta}(\tau)$을 확률의 chain rule(연쇄법칙)에 의해 전개하면,
초기 상태변수 $\mathbf{x}_0$의 PDF($p(\mathbf{x}_0)$)는 $\pi_\theta$(policy)와 무관하므로 첨자 없애기.
또한 $p(\mathbf{x_1|x_0,a_0})$는 환경의 모델로 Transition Probability($\mathbf{x_0 →x_1}$)이므로 알 수 없고 policy와 무관.

$p_{\theta}(\tau)=p_{\theta}(\mathbf{x_0,a_0,x_1,a_1,...,x_T,a_T})=p(\mathbf{x}_0)p_{\theta}(\mathbf{a_0,x_1,a_1...x_T,a_T}|\mathbf{x}_0)$
$=p(\mathbf{x_0})p_{\theta}(\mathbf{a_0|x_0})p(\mathbf{x_1|x_0,a_0})p_{\theta}(\mathbf{a_1|x_0,a_0,x_1})p(\mathbf{x_2|x_0,a_0,x_1,a_1})p_{\theta}(\mathbf{a_2,...,x_T,a_T|x_0,a_0,x_1,a_1,x_2})$

마르코프 시퀀스 가정(Markov Decision Process)에 따라 현재 상태의 이전 상태만이 영향을 줄 수 있기 때문에
$p_{\theta}(\mathbf{a_1|x_0,a_0,x_1})=\pi_{\theta}(\mathbf{a_1|x_1})$
$p(\mathbf{x_2|x_0,a_0,x_1,a_1})=p(\mathbf{x_2|x_1,a_1})$

최종적으로 $p_{\theta}(\tau)=p(\mathbf{x_0})*\Pi^T_{t=0}\pi_{\theta}(\mathbf{a_t|x_t)}p(\mathbf{x_{t+1}}|\mathbf{x_t,a_t})$

1.2 Objective Function

$J(\theta)=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}[\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t}))]=\int_\tau p_{\theta}(\tau)(\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t}))d\tau$

여기서 trajectory를 두 영역으로 분할
$\tau=(\mathbf{x_0,a_0,x_1,a_1,...x_T,a_T})=(\mathbf{x}_0)\cup(\mathbf{a_0,x_1,a_1,...x_T,a_T})=(\mathbf{x}_0)\cup\tau_{\mathbf{a_0:a_T}}$
$p_{\theta}(\tau)=p_{\theta}(\mathbf{x_0,\tau_{\mathbf{a_0:a_T}}})=p(\mathbf{x_0})*p_{\theta}(\tau_{\mathbf{a_0:a_T}}|\mathbf{x_0})$

$J(\theta)=\int_\tau p_{\theta}(\tau)(\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t}))d\tau$
$=\int_{\mathbf{x}_0}\int_{\tau_\mathbf{a_0:a_T}}p_{\theta}(\mathbf{x_0,\tau_{\mathbf{a_0:a_T}}})(\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t}))d\tau_{\mathbf{a_0:a_T}}d\mathbf{x_0}$
$=\int_{\mathbf{x}_0}\int_{\tau_\mathbf{a_0:a_T}}p(\mathbf{x_0})*p_{\theta}(\tau_{\mathbf{a_0:a_T}}|\mathbf{x_0})(\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t}))d\tau_{\mathbf{a_0:a_T}}d\mathbf{x_0}$
$=\int_{\mathbf{x}_0}[\int_{\tau_\mathbf{a_0:a_T}}p_{\theta}(\tau_{\mathbf{a_0:a_T}}|\mathbf{x_0})(\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t}))d\tau_{\mathbf{a_0:a_T}}]p(\mathbf{x}_0)d\mathbf{x_0}$

대괄호항은
$V^{\pi_\theta}(\mathbf{x}_0) = \int_{\tau_{\mathbf{a_0:a_T}}}p_\theta(\tau_{\mathbf{u_0:u_T}}|\mathbf{x}_0)(\sum^T_{t=0}\gamma*r(\mathbf{x_t,a_t}))d\tau_{\mathbf{a_0:a_T}}$

따라서,
$J(\theta)=\int_\mathbf{x_0}V^{\pi_\theta}(\mathbf{x_0})p(\mathbf{x_0})d\mathbf{x}_0$
$=\mathbb{E}_{\mathbf{x}_0 \sim p(\mathbf{x}_0)}[V^{\pi_\theta}(\mathbf{x}_0)]$

Objective Function은 초기 state 변수 $\mathbf{x}_0$에 대한 state value function의 평균값이 된다.

---

2. Policy Gradient

$J(\theta)$를 최대로 만드는 $\theta$를 계산하기 위해 Objective Function을 $\theta$로 미분

$\cfrac{\partial J(\theta)}{\partial \theta}=\nabla_\theta J(\theta)=\nabla_\theta \int_\tau p_\theta(\tau) \sum^T_{t=0}\gamma^t*r(\mathbf{x_t, a_t})d\tau$

$=\int_\tau \nabla_\theta \ p_\theta(\tau) \sum^T_{t=0}\gamma^t(\mathbf{x_t,a_t})d\tau$

2.1 Gradient of Objective Function

$\nabla_\theta \ log\ p_\theta(\tau)=\cfrac{\nabla_\theta\ p_\theta(\tau)}{p_\theta(\tau)}$ 식을 이용하여
위의 식, $\cfrac{\partial \ J(\theta)}{\partial \theta}=\int_\tau \cfrac{p_\theta(\tau)}{p_\theta(\tau)} \nabla_\theta \ p_\theta(\tau) \sum^T_{t=0}\gamma^t(\mathbf{x_t,a_t})d\tau$
$=\int_\tau p_\theta(\tau) \cfrac{\nabla_\theta\ p_\theta(\tau)}{p_\theta(\tau)} \sum^T_{t=0}\gamma^t(\mathbf{x_t,a_t})d\tau$

$=\int_\tau p_\theta(\tau) \nabla_\theta\ log\ p_\theta(\tau) \sum^T_{t=0}\gamma^t(\mathbf{x_t,a_t})d\tau$

$\nabla_\theta\ log\ p_\theta(\tau)$를 전개해보면
$=\nabla_\theta\ log(p(\mathbf{x}_0)\prod^T_{t=0}\ \pi_\theta(\mathbf{a_t|x_t})\ p(\mathbf{x}_{t+1}|\mathbf{x_t,a_t}))$
$=\nabla_\theta(log\ p(\mathbf{x}_0)+\sum^T_{t=0}log\ \pi_\theta(\mathbf{a_t|x_t})+\sum^T_{t=0}log\ p(\mathbf{x_{t+1}|x_t,a_t})$

두번째 항만이 $\theta$에 대한 함수이므로, 첫번째, 세번째 항은 $\theta$에 대해 상수항이므로 $\nabla_\theta=0$이다.
여기서 Transition Probability 또는 Environment의 동역학 모델인 $p(\mathbf{x_{t+1}|x_t,a_t})$가 objective function의 gradient 식에서 사라졌다는 것.
따라서 Model이 필요 없으므로 Gradient of the Objective Function을 이용하는 방법은 Environment의 모델이 필요 없는 model-free 강화학습 방법이다.

$\nabla_\theta\ log \ p_\theta(\tau)=\sum^T_{t=0} \nabla_\theta\ log\ \pi_\theta(\mathbf{a_t|x_t})$

$\nabla_\theta\ J(\theta)=\int_\tau p_\theta(\tau)(\sum^T_{t=0}\nabla_\theta\ log\ \pi_\theta(\mathbf{a_t|x_t}))\ (\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t}))d\tau$

2.2 Gradient of Bias Objective Function

Objective Function이 아래일 때
$J(\theta)=\mathbb{E}_{\tau \sim\ p_\theta(\tau)}[\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t})]$

Gradient of the Objective Function은
$\nabla_\theta\ J(\theta)=\mathbb{E}_{\tau \sim p_\theta(\tau)}[(\sum^T_{t=0}\nabla_\theta\ log\ \pi_\theta(\mathbf{a_t|x_t}))*(\sum_{t=0}^T\gamma^t*r(\mathbf{x_t,a_t})]$

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

오른쪽 2번째 항은 t=0에서 Episode가 종료될때까지 받을 수 있는 trajectory에 대한 total discounted sum $G_0$.
하지만 t=k에서 실행된 policy ($\pi_\theta(\mathbf{a_k|x_k})$)는 t<k에서의 reward 값에 영향을 끼치지 못하는(non-causality)를 고려한다면 위 식은 다음과 같이 수정
즉, 결과인 $r(\mathbf{x_k,a_k})$은 원인인 $t<k$인 $\pi_\theta(\mathbf{a_t|x_t})$에 앞서 발생할 수 없다.

$\mathbf{x_k}$는 {$\mathbf{a}_{k-1}, \mathbf{x}_{k-1}, ..., \mathbf{a}_t,\mathbf{x}_t, ...$}에 영향을 줄 수 없음.
그렇기 때문에 오른쪽 2번째 항은 $G_0$가 아니라, $\sum^T_{k=t}\gamma^k*r(\mathbf{x_t,a_t})$로 변경. 아래와 같이 수정

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

$=\mathbb{E}_{\ \tau \sim p_\theta(\tau)}[\sum^T_{t=0}(\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})))]$

처음 감가율 $\gamma^t$는 log-policy gradient에 곱해지기 때문에 시간이 갈수록 변화율을 점점 작게 만듬. 감가율 $\gamma$가 작을수록 빠른 시간 안에 log-policy gradient($J_\theta(\theta)$)를 0으로 만들 수 있다.
이렇게 되면 episode의 후반부 trajectory에 있는 data의 이용도가 크게 떨어지는 단점.

감가율이 $\gamma=1$이라면 objective function의 gradient는 다음 식

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

• 위 식은 Objective Function의 gradient의 분산을 크게 만들 수 있다는 단점
• 무한 구간 Episode에서는 보상의 총합($G_t$)이 무한대가 될 수 있기 때문에 사용하지 못함.

실용적인 Objective Function의 Gradient

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

예정된 reward에만 감가율 적용. 위 식은 다소 편향된 gradient.
t일 때 $r(\mathbf{x_t,a_t})$,
t+1일 때 $\gamma*r(\mathbf{x_{t+1},a_{t+1}})$,
...
T일 때 $\gamma^{T-t}*r(\mathbf{x_{t+1},a_{t+1}})$

감가율 $\gamma$가 포함된 MDP는 생각보다 까다로운 문제, 아래 논문에서 자세히 논의.
Bias in Natural Actor-Critic Algorithms, 2014

2.3 Summary

Objective Function을 이용해 policy를 update하는 것을 policy gradient라고 한다.
Objective Function을 최대로 하는 parameter $\theta$는 다음과 같이 Gradient Ascent로 구할 수 있음

• Objective Function
  $J(\theta)=\mathbb{E}_{\tau \sim p_\theta(\tau)}[\sum^T_{t=0}\gamma^t*r(\mathbf{x_t,a_t})],\ \tau=(\mathbf{x_0,a_0,x_1,a_1,...,x_T,a_T})$
• 가정
  Stochastic Policy $\mathbf{a}_t \sim \pi_\theta(\mathbf{a_t|x_t})$
• Gradient of O.F
  $\nabla_\theta\ J(\theta)=\mathbb{E}_{\ \tau \sim p_\theta(\tau)}[\sum^T_{t=0}( \nabla_\theta\ log\ \pi_\theta(\mathbf{a_t|x_t)}(\sum^T_{k= t}r(\mathbf{x_k,a_k})))]$
• Update
  $\theta ← \theta+\alpha*\nabla_\theta\ J(\theta)$|