강화학습에서 Approximation 은 어떤 의미인가?

Approximation in Reinformcement Learning

전통적인 강화학습은 상태 $s$ 나 상태-행동 $(s,a)$ 에 대한 Value값 $V(s)$ 혹은 $Q(s,a)$ 를 학습하는 것을 기반으로 합니다. 환경에서 주어지는 상태의 개수가 $|S|$ 그리고 행동의 수가 $|A|$ 라고 한다면, Value 값을 정확하게 위해서는 상태에 따라서 값을 저장해줘야 한다는 단점이 있습니다. 두 명이서 가위바위보를 한다면, 총 가능한 상태는 내가 내는 것 3 가지와 상대방이 내는 3가지의 경우의 수인 9가지가 됩니다. 이와 다르게 마리오 게임이라면 마리오가 조금만 움직여도 위치가 달라지기 때문에 굉장히 많은 상태가 있습니다. (어쩌면 무한대에 가까울 수도 있지만, 최대값은 모든 픽셀의 RGB 경우의 수인 $(256 \times256\times256)^{\#pixel}$ 보다는 적습니다.) 이렇게 많은 상태에 대해서 $V(s)$ 값을 기록한다면, 컴퓨터의 메모리로는 부족할 것이고, 상태를 예측하는 더욱 효과적인 방법이 필요합니다.

상태에 대한 Value 값을 추정하는 방식은 파라미터를 포함하는 parametric 과 파라미터를 사용하지 않고 예측하는 non-parametric 방식이 있습니다. parametric 은 상태에 대해서 함수를 만드는 것으로 생각할 수 있고, non-parametric 은 과거에 방문한 상태를 기반으로 현재 상태를 예측합니다.

Parametric

Parametric 방식의 한 가지 규칙은 파라미터의 수 $d$ 가 상태의 개수 $|S|$ 보다 적다는 것 $(d \ll |S|)$ 입니다. 마리오 게임에서 무수히 많은 상태가 있지만, 비슷한 상태가 꽤나 많이 있습니다. 위의 그림에서 마리오가 조금만 이동한다면, 맵은 크게 바뀌지 않을 것이고, 상태에 대한 Value $V(s)$ 값도 근처의 상태와 비슷할 것 입니다. 아래 그림에서 첫 번째 경우는 상태 5개에 대해서 파라미터는 1개만 필요하고, 두 번째 경우는 2개의 파라미터만 필요합니다. 따라서 파라미터를 이용해서 Value 를 정확하게 표현할 수 있다면 저장해야 하는 정보의 크기가 줄어듭니다.

파라미터 $w$에 대해서 상태 $s$ 에 대한 value function 을 $\hat v(s,w)$ 라고 하겠습니다. (hat 은 근사치라는 표현을 나타냅니다.) 그리고 근사가 아닌 실제 value function 은 $v(s)$ 입니다. 목표는 $\hat v(s,w)$ 값을 $v(s)$ 에 가깝게 만드는 것으로 Mean Squared Value Error 를 줄이는 것 입니다.

$$ \overline{\text{VE}}(w) = \sum_{s\in S} \mu(s) \Big(v(s) - \hat v(s,w)\Big)^2 $$

여기서 $\mu(s)$ 는 상태 $s$ 가 다른 모든 상태에 대해서 상대적으로 방문한 정도를 나타내는 값 입니다. 따라서 $\overline{\text{VE}}$ 는 모든 상태에 대하여 방문한 정도를 기반으로한 Value Error에 대한 값입니다.

Stochastic Gradient

$\overline{\text{VE}}$ 는 모든 상태에 대한 에러를 계산하기 때문에, 비효율적입니다. 실제로는 하나의 상태에 대해서 해당 값을 줄입니다. 혹은 딥러닝이라면 batch에 대해서 값을 줄입니다. $t$ time step에 방문한 상태 $S_t$ 에 대해서 $\Big(v(S_t) - \hat v(S_t,w)\Big)^2$값을 줄이기 위해서 gradient 를 구하고 gradient descent를 이용해서 값을 줄이는 $w_t$ 의 업데이트 방향을 구할 수 있습니다.

$$\nabla \Big(v(S_t) - \hat v(S_t,w_t)\Big)^2 = 2\Big(v(S_t) - \hat v(S_t,w_t)\Big) \nabla \hat{v}(S_t,w_t)$$

$$w_{t+1} \leftarrow w_t - \alpha \Big(v(S_t) - \hat v(S_t,w_t)\Big) \nabla \hat{v}(S_t,w_t)$$

강화학습에서 state value 는 discount return과 동일합니다. $v(S_t) = G_t$.

그러므로 위의 식에서 $v(S_t)$ 는 $G_t = R_{t} + \gamma R_{t+1} + \cdots$ 로 바꿔서 구할 수 있습니다.

$$ w_{t+1} \leftarrow w_t - \alpha \Big(G_t - \hat v(S_t,w_t)\Big) \nabla \hat{v}(S_t,w_t) $$

(TMI) 원래는 $w_t$ 가 아닌 $\mathbf{w}_t$ 라고 기술해야 맞지만, 가독성을 위해서 $w_t$ 를 사용했습니다. 저는 벡터나 메트릭스 표현은 무섭거든요. $A^\text{T} X \mathbf{w} \cdots$

Semi-Gradient

효율적인 강화학습을 위해서라면, 굉장히 먼 미래까지 보상을 구해서 평가하는 $G_t$ 가 아닌 1-step 에 대한 기대값을 추측하는 TD $r + \gamma v(s)$ 나 $n$-step return $G_{t:t+n}$ 을 사용하게 됩니다. 그렇다면 위의 식에서 $G_t$ 는 다음 값으로 대체 됩니다.

$$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n \hat v(S_{t+n},w_t)$$

$$w_{t+1} \leftarrow w_t - \alpha \Big(G_{t:t+n}- \hat v(S_t,w_t)\Big) \nabla \hat{v}(S_t,w_t)$$

여기서 한 가지 이상한 점이 있습니다. 목표는 $\Big(v(S_t) - \hat v(S_t,w)\Big)^2$ 값을 최소화 하는 것이고, $v(S_t)$ 가 타겟입니다. 그런데, 타겟을 $\hat v$으로 근사해서 구합니다.

$$v(S_t) = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n \hat v(S_{t+n},w_t)$$

따라서 구하고자 하는 목표가 학습을 진행하는 대상으로부터 만들어집니다. 마치 학생이 퀴즈를 풀지만, 그 학생이 퀴즈를 만드는 것처럼 불공평한 경우입니다. 그러므로 우리가 구하는 gradient는 실제 $v(s)$ 로부터 구해진 것이 아닙니다. 그래서 거짓 Gradient이고 조금 멋진 이름으로 Semi-Gradient 라고 부릅니다.

Non-Parametric

non-parametric은 현재 상태의 value function $v(s)$ 를 구할 때, 과거에 방문한 상태와의 비교를 통해서 구합니다. 따라서 과거 상태를 하는 저장소가 필요합니다. $\mathcal{D} = \{ s_t | t = \text{과거 }\}$. 현재 상태 $S_t$ 에 대해서 가장 가까운 과거 상태를 고를 수도 있고, 여러 개를 뽑을 수도 있습니다. 여기서 필요한 정보는 과거의 상태 $s$ 에 대해서 어떤 값 $g$ 를 구해놓는 것 입니다. 따라서 모든 상태에 대해서 $s \mapsto g$ 를 구해놓고, 새로운 상태가 왔을 때, 몇 개의 상태로부터 $g$ 값들을 종합해서 value funcion을 구합니다. Kerenl 방식으로 모든 과거 정보를 토대로 구하면 다음과 같습니다.

$$\hat v(s, \mathcal{D} ) = \sum_{s' \in \mathcal{D}}k(s, s')g(s')$$

Conclusion

Value function에 대해서 테이블을 사용해서 값들을 각각 저장하는 Tabular method 와 다르게 Approximate method는 파라미터를 사용하거나, 과거 정보들을 바탕으로 추측합니다. 딥러닝 같은 경우는 후자의 경우로, 수많은 파라미터를 통해서 적당한 값을 예측하게 됩니다. 한 가지 오해하지 말아야 하는 것은 강화학습 방법 자체는 딥러닝과 무관합니다. 딥러닝으로 멋진 강화 학습 방법이 발견된 것이 아닌 상태에 대한 표현력의 발전으로 Value function을 더욱 잘 예측하기 때문입니다.

저작자표시 비영리 동일조건