가치 이터레이션에서 Q-러닝으로

정책 이터레이션은 벨만 방정식을 반복적으로 푸는 방법이었다.

 

 

 

정책 이터레이션의 식은 다음과 같다.

 

$$\begin{array}{r}\text{(1)}& & V_{j+1}^{\pi }({\mathbf{x}}_t)=r_t+{\mathbb{E}}_{{\mathbf{x}}_{t+1}\sim p({\mathbf{x}}_{t+1}|{\mathbf{x}}_t,{\mathbf{u}}_t)}[\gamma V_j^{\pi }({\mathbf{x}}_{t+1})]\\ & Q_{j+1}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}_t)=r_t+{\mathbb{E}}_{{\mathbf{x}}_{t+1}\sim p({\mathbf{x}}_{t+1}|{\mathbf{x}}_t,{\mathbf{u}}_t)}[\gamma Q_j^{\pi }({\mathbf{x}}_{t+1},{\mathbf{u}}_{t+1})]\end{array}$$

 

정책 개선을 위한 식은 다음과 같다.

 

$$\begin{array}{r}\text{(2)}& {\pi }_{i+1}& =\arg \underset{{\mathbf{u}}_t}{max}{Q}_{i+1}^{{\pi }_i}({\mathbf{x}}_t,{\mathbf{u}}_t)\\ & =\arg \underset{{\mathbf{u}}_t}{max}[r_t+{\mathbb{E}}_{{\mathbf{x}}_{t+1}\sim p({\mathbf{x}}_{t+1}|{\mathbf{x}}_t,{\mathbf{u}}_t)}[\gamma V_{i+1}^{{\pi }_i}({\mathbf{x}}_{t+1})]]\end{array}$$

 

반면 가치 이터레이션은 벨만 최적 방정식을 반복적으로 푸는 방법이었다. 가치 이터레이션의 식은 다음과 같다.

 

$$\begin{array}{r}\text{(3)}& & V_{i+1}({\mathbf{x}}_t)=\underset{{\mathbf{u}}_t}{max}[r_t+{\mathbb{E}}_{{\mathbf{x}}_{t+1}\sim p({\mathbf{x}}_{t+1}|{\mathbf{x}}_t,{\mathbf{u}}_t)}[\gamma V_i({\mathbf{x}}_{t+1})]]\\ & Q_{i+1}({\mathbf{x}}_t,{\mathbf{u}}_t)=r_t+{\mathbb{E}}_{{\mathbf{x}}_{t+1}\sim p({\mathbf{x}}_{t+1}|{\mathbf{x}}_t,{\mathbf{u}}_t)}[\gamma \underset{{\mathbf{u}}_{t+1}}{max}{Q}_i({\mathbf{x}}_{t+1},{\mathbf{u}}_{t+1})]\end{array}$$

 

중간 계산 단계에서의 정책은 식 (2)와 동일하게 구할 수 있다.

정책 이터레이션과 가치 이터레이션을 수행하려면 환경 모델 $p({\mathbf{x}}_{t+1}|{\mathbf{x}}_t,{\mathbf{u}}_t)$ 가 필요하다. 하지만 모델프리(model-free) 강화학습에서는 환경 모델을 이용하여 가치함수를 계산하는 것이 아니라, 에이전트가 환경에 행동을 가해서 생성한 데이터를 기반으로 하여 가치함수를 추정한다.

강화학습에서도 각각 벨만 방정식과 벨만 최적 방정식에서 유도된 정책 이터레이션과 가치 이터레이션 식이 필요하다.

식 (2)와 (3)를 살펴보면 최대값(max)을 계산하는 부분이 있는데 모두 이터레이션 루프 안에 들어가 있는 것을 알 수 있다. 연속공간(continuous space)에서 매 이터레이션 단계마다 행동에 관한 최대값을 구하는 일은 계산상의 큰 문제점을 야기하기 때문에, 여기서는 행동을 이산공간(discrete space) 행동으로 가정하고자 한다. 이산공간에서의 행동에 관한 최대값은 유한 개의 행동에 대해서 가치함수 값을 계산한 후 그 중 가장 큰 값을 선택하면 얻을 수 있기 때문에 계산이 손쉽다.

또한 상태변수도 이산공간 상태변수로 가정한다. 이유는 식 (1)과 (3)에 있는 행동가치 함수를 유한 개의 셀로 구성된 테이블(table) 형태로 관리하기 위해서다. 그러면 행동가치 함수의 최대값을 쉽게 구할 수 있다.

 

 

연속공간 행동과 상태변수에 관한 문제는 추후 다시 논의하기로 한다. 이산공간의 표기를 연속공간과 구별하기 위하여 행동을 ${\mathbf{u}}_t$ 에서 ${\mathbf{a}}_t$ 로, 상태변수를 ${\mathbf{x}}_t$ 에서 ${\mathbf{s}}_t$ 로 바꾸고자 한다.

 

 

이제 식 (1)과 (3)에 있는 상태가치 함수 업데이트 식을 보자. 상태가치를 정책 이터레이션 또는 가치 이터레이션을 통해 업데이트 한 후에 행동을 다음 식으로 업데이트 해야 한다.

 

$$\begin{array}{}\text{(4)}& {\mathbf{a}}_t=\arg \underset{{\mathbf{a}}_t}{max}[r_t+{\mathbb{E}}_{{\mathbf{s}}_{t+1}\sim p({\mathbf{s}}_{t+1}|{\mathbf{s}}_t,{\mathbf{a}}_t)}[\gamma V({\mathbf{s}}_{t+1})]]\end{array}$$

 

환경 모델 $p({\mathbf{s}}_{t+1}|{\mathbf{s}}_t,{\mathbf{a}}_t)$ 를 알고 있다면 해석적인 방법으로 새로운 행동을 구할 수 있겠지만, 만약 샘플을 이용하여 계산해야 한다면 식 (4)의 최대값을 계산하는 것은 불가능하다. 이런 이유로 상태가치 함수를 이용하여 강화학습 알고리즘을 고안하기는 힘들다.

 

이번에는 식 (1)과 (3)에 있는 행동가치 함수 업데이트식을 다시 써 보자.

 

$$\begin{array}{r}\text{(5)}& & Q^{\pi }({\mathbf{s}}_t,{\mathbf{a}}_t)\leftarrow r_t+{\mathbb{E}}_{{\mathbf{s}}_{t+1}\sim p({\mathbf{s}}_{t+1}|{\mathbf{s}}_t,{\mathbf{a}}_t)}[\gamma Q^{\pi }({\mathbf{s}}_{t+1},{\mathbf{a}}_{t+1})]\\ \text{(6)}& & Q({\mathbf{s}}_t,{\mathbf{a}}_t)\leftarrow r_t+{\mathbb{E}}_{{\mathbf{s}}_{t+1}\sim p({\mathbf{s}}_{t+1}|{\mathbf{s}}_t,{\mathbf{a}}_t)}[\gamma \underset{{\mathbf{a}}_{t+1}}{max}Q({\mathbf{s}}_{t+1},{\mathbf{a}}_{t+1})]\end{array}$$

 

식 (5)에 의하면 알고리즘은 특정 정책 $\pi$ 로 샘플 $\{{\mathbf{s}}_i,{\mathbf{a}}_i,r_i,{\mathbf{s}}_{i+1},{\mathbf{a}}_{i+1}\}$ 을 발생시켜서 $Q^{\pi }$ 를 추정하고, 식 (2)를 통해서 정책을 업데이트 한 후, 다시 업데이트된 정책으로 샘플을 발생시켜서 $Q^{\pi }$ 를 업데이트 하는 프로세스를 반복할 수 있다.

또한 식 (6)에 의하면 특정 정책 $\pi$ 로 샘플 $\{{\mathbf{s}}_i,{\mathbf{a}}_i,r_i,{\mathbf{s}}_{i+1}\}$ 을 발생시켜서 Q를 업데이트 시키면 된다. 두 식 모두 정책을 업데이트하기 위해서 $\underset{{\mathbf{a}}_t}{max}Q({\mathbf{s}}_t,{\mathbf{a}}_t)$ 를 계산해야 하는데 이는 매우 쉽다. 행동가치 함수는 상태변수와 행동의 함수이기 때문에 $Q(\mathbf{s},\mathbf{a})$ 가 저장된 테이블에서 $\mathbf{a}$ 에 관해서 제일 큰 $Q$ 값을 찾기만 하면 된다. 이런 이유로 강화학습에서는 행동가치 함수를 이용하여 알고리즘을 고안한다.

 

 

식 (5)는 샘플 $\{{\mathbf{s}}_i,{\mathbf{a}}_i,r_i,{\mathbf{s}}_{i+1},{\mathbf{a}}_{i+1}\}$ 가 필요하다. 식 (5)를 이용하는 강화학습 알고리즘을 SARSA라고 한다. 필요한 샘플을 보면 왜 이름이 SARSA인지 짐작이 갈 것이다.
반면, 식 (6)을 계산하려면 샘플 $\{{\mathbf{s}}_i,{\mathbf{a}}_i,r_i,{\mathbf{s}}_{i+1}\}$ 가 필요하다. ${\mathbf{a}}_{i+1}$ 는 필요치 않다. 왜냐하면 $\underset{{\mathbf{a}}_t}{max}Q({\mathbf{s}}_t,{\mathbf{a}}_t)=\underset{\mathbf{a}}{max}Q({\mathbf{s}}_t,\mathbf{a})$ 가 성립하기 때문이다. 식 (6)을 이용하는 강화학습 알고리즘을 Q-러닝(Q-learning)이라고 한다.
Q-러닝에서 행동가치 함수는 최적 행동가치 $Q^{\star }$ 를 직접 근사화 한 것으로서 샘플 $\{{\mathbf{s}}_i,{\mathbf{a}}_i,r_i,{\mathbf{s}}_{i+1}\}$ 를 어떤 특정 정책 $\pi$ 로 발생시켜야 한다는 근거가 수식 상에 전혀 없다.

따라서 어떤 정책으로 발생된 샘플인가에 관계없이 모두 행동가치 함수를 업데이트하는데 사용될 수 있다. 이러한 학습 알고리즘을 오프-폴리시(off-policy) 방법이라고 한다. 오프-폴리시 방법은 데이터 효율이 매우 높다. 왜냐하면 이전 정책으로 발생시킨 샘플도 모두 재 사용할 수 있기 때문이다.

 

반면에 SARSA 알고리즘은 온-폴리시(on-policy) 방법이라고 한다. 현재 정책으로 발생시킨샘플로만 정책을 업데이트 할 수 있기 때문이다.

보통 정책 그래디언트 계열의 온-폴리시 정책에서는 일단 정책을 업데이트했다면 사용된 샘플을 모두 폐기해야 한다. 새롭게 업데이트된 정책으로 발생시킨 샘플로만 그 정책을 다시 업데이트할 수 있기 때문이다. 따라서 온-폴리시 방법은 오프-폴리시 방법보다 데이터 효율이 매우 떨어진다.