An actor-critic algorithm
지난 글에서 다뤘던 기본적인 (batch) actor-critic 알고리즘은 아래와 같다.
결과적으로 actor-critic algorithm의 핵심은 샘플링된 reward sum을 estimate할 수 있는 value function \(\hat{V}^{\pi}_{\phi}(s)\) 를 학습하는 것이고, 이를 바탕으로 advantage function \(\hat{A}^{\pi}(s_i, a_i)\) 까지 계산하는 것이다. 그리고 이전에 학습된 신경망에서 뽑은 값으로 next target을 구하는 bootstrapping 방식을 사용한다는 것까지 다뤘다.
Aside: discount factors
그래서 결국 value function을 fit 하는 문제는 아래와 같이 정의할 수 있게 된다.
\[ y_{i, t} \approx r(s_{i, t}, a_{i, t}) + \hat{V}^{\pi}_{\phi}(s_{i, t+1}) \] \[ \mathcal{L}(\phi) = \frac{1}{2} \sum_{i} \Vert \hat{V}^{\pi}_{\phi}(s_{i, t}) - y_{i, t} \Vert^2 \]
그런데 만약, value function의 boundary, 즉 episode의 길이가 무한정이라면 어떻게 될까? 그 말은 episode가 끝나지 않으면서 계속 reward를 더하는 형태로 value function이 update될 것이고, 위 식에 따르면 \(\hat{V}_{\phi}^{\pi}\) 도 역시 무한정으로 커지게 된다. 이를 다룰 수 있는 방법은 현재의 순간과 가까운 시점에 받은 reward에 대해서 더 큰 가중치를 주는 것이고, 이때 discount factor \(\gamma\) 를 사용한다. 그러면 value function은 다시 정의할 수 있다.
\[ y_{i, t} \approx r(s_{i, t}, a_{i, t}) + \gamma \hat{V}^{\pi}_{\phi}(s_{i, t+1}) \qquad ,\gamma \in [0, 1] \]
일반적으로 \(\gamma\) 는 0.99라는 1에 가까운 값을 사용하는데, 현재 시점에 먼 시점에 reward를 받은 것에 대해서는 \(\gamma^n\) 의 형태로 가중치가 감가된다. (n은 시점의 차이, 그래서 보통 번역본에는 감가 상수라고 표현되어 있다.) 보통 \(\gamma\) 는 학습자가 정하는 hyperparameter로 알려져 있지만, 실제로 어떤 \(\gamma\) 를 사용했느냐에 따라서 MDP가 변하는 경우도 존재한다. 강의에서는 \(n\) step후에 죽는 경우에 대한 예시를 들었는데, 어떤 값을 선택하냐에 따라서 episode가 끝나는 시점이 달라지면서, 결국에는 환경의 transition probability에 영향을 주기도 한다.
Aside: discount factors for policy gradient
그러면 위에서 다룬 discount factor를 (monte carlo) policy gradient에 적용할 수 있느냐에 대한 의문이 생길 수 있다. 다르게 표현하면 policy gradient에서도 현재에 가까운 시점에 받은 reward의 비중을 더 크게 반영할 수 있느냐인데, 실제 식으로 넣게 된다면 해당 강의에서 다뤘던 reward-to-go 부분에 \(\gamma\) 를 넣어주면 된다.
\[ \text{Option 1:} \qquad \nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}(a_{i, t}|s_{i, t}) \left( \sum_{t'=t}^{T} \gamma^{t'-t} r(s_{i, t'}, a_{i, t'}) \right) \]
\[ \text{Option 2:} \qquad \nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \left( \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}(a_{i, t}|s_{i, t}) \right) \left( \sum_{t=1}^{T} \gamma^{t-1} r(s_{i, t'}, a_{i, t'}) \right) \]
여기에서 잠깐 Option 2에 대해서 살펴볼 필요가 있다. 이 식은 바로 위에 있는 Option 1과 유사해보이지만, 뒤에 reward가 더해지는 부분에서 reward-to-go가 아닌 처음 시점부터 보게끔 되어 있다는 부분에서 조금 차이가 있다. 그런데 사실 첫번째 bracket과 두번째 bracket의 시점이 \(t=1\) 부터 \(T\) 까지의 시점이므로, 두번째 bracket의 \(\gamma\) 를 쪼개서 (\(\gamma \rightarrow \gamma^{1 \sim t-1} \times \gamma^{t \sim T}\)) 첫번째 bracket에 넣어주면 Option 1과 유사한 식이 만들어진다.
\[ \nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} {\color{red}\gamma^{t-1}} \nabla_{\theta} \log \pi_{\theta}(a_{i, t}|s_{i, t}) \left( \sum_{t=1}^{T} \gamma^{t-1} r(s_{i, t'}, a_{i, t'}) \right) \]
사실 위 식의 \(\gamma^{t-1}\) 의 역할은 reward에서의 discount factor의 역할과 비슷하다. reward에서의 discount factor는 정의 그대로 현재에 가까운 시점에 받은 reward에 대한 가중치를 의미하고, 위 식의 \(\gamma\) 도 역시 현재에 가까운 시점에 취한 policy \(\pi_{\theta}\)에 가중치를 더 부여하겠다는 것을 의미한다. 예를 들어서 내가 현재 시점에 100 달러를 받으면서 한 행동과 1년 뒤에 100 달러를 받으면서 한 행동의 가치를 다르게 부여하겠다는 것이다. 어떻게 보면 Option 2에서 정의한 식이 실제 policy gradient를 계산하는데 더 적합하다고 볼 수도 있다. 강의에서는 이를 later steps matter less, 즉 뒤로 갈수록 더 적은 가중치를 부여한다고 표현하였다.
Which version is the right one?
그럼에도 불구하고 실제로 사용하는 식은 Option 2가 아닌, Option 1이다. 왜일까? 사실 우리가 discount factor를 사용함으로써 원하는 것은 policy의 영향력을 변화시키는 것이 아니라, 현재와 가까운 reward에 가중치를 부여하는 것이다. 앞에서 언급한 것처럼 finite한 episode 상에서는 최대한 빠르게 goal에 도달하는 것을 원하기 때문에, 상식적으로는 Option 2처럼 policy에도 \(\gamma\) 를 가하는게 맞는 것처럼 보일지는 몰라도 실제로는 Option 1처럼 reward-to-go term에만 \(\gamma\) 를 사용하는 것이다. 그리고 이는 결국 policy gradient의 variance를 줄여주는 역할도 같이 수행한다.
Actor-critic algorithm (with discount)
그래서 결국 discount factor가 적용된 actor-critic algorithm은 아래와 같이 정의할 수 있다. 사실 Algorithm 1 에서 3번째 줄의 advantage function을 계산하는 부분에서 discount factor를 적용하는 차이가 생기는 것일뿐, 거의 동일하다.
혹은 online 상황에서 single time step에서 얻은 trajectory로 update하는 경우에는 아래와 같이 정의할 수 있다.