들어가며...

지금까지는 State마다 Value를 한 칸씩 저장했다.

$$S_1 \rightarrow V(S_1), \qquad S_2 \rightarrow V(S_2)$$

State가 몇십 개라면 이 방식이 가장 직관적이다. 그런데 카메라 이미지 한 장이 State가 되면 가능한 픽셀 조합을 전부 표로 만들 수 없다. Robot의 관절 각도처럼 State가 연속적이어도 마찬가지다. 한 번도 똑같은 자세를 다시 만나지 않을 수 있다.

이때 필요한 생각은 “State마다 답을 외우기”에서 “State의 특징을 보고 답을 계산하기”로 바꾸는 것이다.

$$\text{Value table} \quad\longrightarrow\quad \hat v(s,\mathbf w)$$

$\mathbf w$는 여러 State가 함께 사용하는 Parameter다. 이번 글에서는 Value Function Approximation의 가장 단순한 형태인 Linear function부터 시작해, Monte Carlo와 TD Target을 어떻게 함수 학습에 연결하는지 천천히 살펴본다.

Table이 막히는 지점

Tabular method는 방문한 State의 칸만 고친다.

$$V(S_t) \leftarrow V(S_t)+\alpha\left[U_t-V(S_t)\right]$$

$U_t$는 Monte Carlo Return일 수도 있고 TD Target일 수도 있다. 중요한 점은 $S_t$의 칸과 다른 State의 칸이 서로 독립이라는 것이다.

이 독립성은 작은 문제에서는 편하다. 하지만 다음 두 문제가 생긴다.

1. State가 너무 많으면 모든 칸을 저장할 수 없다.
2. 비슷한 State에서 배운 내용을 서로 나누지 못한다.

예를 들어 자율주행 State의 차선 위치가 $0.201$에서 $0.202$로 바뀌었다고 하자. 두 State는 거의 같은 상황인데 표에서는 완전히 다른 주소가 된다. $0.201$에서 충분히 배웠더라도 $0.202$는 처음 보는 State다.

Function approximation은 비슷한 State가 비슷한 표현과 Parameter를 공유하도록 만든다.

정확한 값이 아니라 근사값

Policy $\pi$의 진짜 State value를 $v_\pi(s)$라고 하자. 우리가 만드는 함수는 이를 근사한다.

$$\hat v(s,\mathbf w) \approx v_\pi(s)$$

모자 표시는 “현재 Parameter로 계산한 추정값”이라는 뜻이다.

• $s$: 입력 State
• $\mathbf w$: 학습할 Parameter
• $\hat v(s,\mathbf w)$: 함수가 예측한 Value
• $v_\pi(s)$: 알고 싶지만 직접 볼 수 없는 진짜 기대 Return

Supervised learning과 구조가 비슷하다. 입력 $s$를 넣어 예측값을 만들고, Target과의 차이를 줄이도록 $\mathbf w$를 Update한다. 차이는 RL에서는 정답 Label을 누군가 주지 않는다는 점이다. 경험으로 만든 Return이나 Bootstrap Target을 임시 정답으로 사용한다.

Feature는 State를 숫자로 설명한다

함수에 State를 넣으려면 먼저 숫자 Vector로 표현해야 한다.

$$\mathbf x(s) = \begin{bmatrix} x_1(s) \\ x_2(s) \\ \vdots \\ x_d(s) \end{bmatrix}$$

엘리베이터 State를 예로 들면 Feature는 다음처럼 잡을 수 있다.

• 현재 층을 정규화한 값
• 위쪽 호출 버튼이 켜졌는지
• 아래쪽 호출 버튼이 켜졌는지
• 문이 열려 있는지

Feature는 State를 설명하는 질문 목록과 비슷하다. Neural Network에서는 이 Feature 자체도 Network가 학습하지만, Linear function에서는 사람이 정한 Feature를 입력으로 사용하는 경우가 많다.

Linear Value Function

가장 단순한 근사 함수는 Feature의 가중합이다.

$$\hat v(s,\mathbf w) = \mathbf x(s)^\top\mathbf w = \sum_{j=1}^{d}x_j(s)w_j$$

예를 들어,

$$\mathbf x(s) = \begin{bmatrix} 1 \\ 0.5 \\ -1 \end{bmatrix}, \qquad \mathbf w = \begin{bmatrix} 2 \\ 4 \\ 1 \end{bmatrix}$$

라면,

$$\hat v(s,\mathbf w) = 1\times2 +0.5\times4 +(-1)\times1 =3$$

이다.

$w_j$는 해당 Feature가 Value에 어느 방향으로 얼마나 영향을 주는지 나타낸다. 두 번째 Feature가 커질 때 Value가 높아지는 경험이 반복되면 $w_2$가 커지는 식이다.

Error를 줄이는 방향

어떤 Target $U_t$가 있다고 하자. 한 Sample의 Squared error는,

$$L_t(\mathbf w) = \frac{1}{2} \left[ U_t-\hat v(S_t,\mathbf w) \right]^2$$

이다. $1/2$은 미분할 때 앞의 $2$를 없애기 위한 편의다.

Gradient descent로 Parameter를 Update하면,

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ U_t-\hat v(S_t,\mathbf w) \right] \nabla_{\mathbf w}\hat v(S_t,\mathbf w)$$

가 된다.

식은 세 덩어리로 읽으면 쉽다.

1. $\alpha$: 얼마나 움직일지 정하는 Step size
2. $U_t-\hat v$: 현재 예측이 얼마나 틀렸는지 나타내는 Error
3. $\nabla_{\mathbf w}\hat v$: 어떤 Parameter를 움직이면 예측이 바뀌는지 나타내는 방향

Linear function에서는 Gradient가 Feature 자체다.

$$\nabla_{\mathbf w}\hat v(s,\mathbf w) = \mathbf x(s)$$

Update도 더 단순해진다.

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ U_t-\hat v(S_t,\mathbf w) \right] \mathbf x(S_t)$$

값이 큰 Feature와 연결된 Weight가 더 많이 움직인다.

한 State를 배웠는데 다른 State도 바뀐다

Table에서는 $S_A$를 Update해도 $S_B$의 값은 그대로다. Function approximation에서는 같은 $\mathbf w$를 공유하므로 $S_A$로 한 Update가 $S_B$와 $S_C$의 예측도 바꾼다.

이것이 Function approximation의 장점이자 위험이다.

• 좋은 Feature를 공유하면 적은 경험으로 비슷한 State를 함께 학습한다.
• 잘못 일반화하면 한 State의 Error가 관련 없는 State의 예측까지 망가뜨린다.

표는 느리지만 한 칸의 실수가 다른 칸으로 번지지 않는다. 함수는 빠르게 일반화하지만 Update의 영향 범위가 넓다.

Monte Carlo Target을 넣으면

Episode가 끝난 뒤 실제 Return $G_t$를 계산할 수 있다면,

$$U_t=G_t$$

로 둔다.

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ G_t-\hat v(S_t,\mathbf w) \right] \nabla_{\mathbf w}\hat v(S_t,\mathbf w)$$

Target에 현재 Value 함수가 들어가지 않으므로 익숙한 Supervised regression과 가장 비슷하다. 다만 Episode 끝까지 기다려야 하고 Return의 Variance가 크다는 Monte Carlo의 성질은 그대로 남는다.

TD Target을 넣으면

TD(0)는 한 Step 뒤의 추정을 Bootstrap한다.

$$U_t = R_{t+1} + \gamma\hat v(S_{t+1},\mathbf w)$$

TD error는,

$$\delta_t = R_{t+1} + \gamma\hat v(S_{t+1},\mathbf w) - \hat v(S_t,\mathbf w)$$

이고 Update는,

$$\mathbf w \leftarrow \mathbf w + \alpha\delta_t \nabla_{\mathbf w}\hat v(S_t,\mathbf w)$$

가 된다.

여기서는 Target도 같은 Parameter $\mathbf w$로 만든다. 하지만 Update할 때는 Target 쪽의 미분을 따라가지 않고 현재 State 예측 $\hat v(S_t,\mathbf w)$만 고친다. 그래서 Semi-gradient TD라고 부른다.

처음에는 “다음 State의 추정값을 임시 정답으로 고정하고 현재 예측만 그쪽으로 움직인다”고 이해하면 충분하다.

Function approximation이 항상 안정적인 것은 아니다

Function approximation, Bootstrapping, Off-policy learning이 함께 있을 때 학습이 불안정해질 수 있다. 이 세 요소는 흔히 Deadly Triad라고 불린다.

• Function approximation: 여러 State가 Parameter를 공유한다.
• Bootstrapping: Target 안에 현재 추정값이 들어간다.
• Off-policy: 경험을 만든 Policy와 학습하려는 Policy가 다르다.

하나의 과대 추정이 공유 Parameter를 통해 퍼지고, 그 잘못된 추정으로 다시 Target을 만들면 Error가 커질 수 있다. 다음 글의 DQN은 Experience replay와 Target network를 이용해 이 문제를 완화한다.

이번 글에서 기억할 것

Value Function Approximation은 State별 값을 저장하는 대신, 공유 Parameter를 가진 함수로 Value를 계산해 본 적 없는 State까지 일반화한다.

1. $\hat v(s,\mathbf w)$는 $v_\pi(s)$를 근사한다.
2. Linear function은 $\hat v=\mathbf x(s)^\top\mathbf w$로 쓴다.
3. Update는 Step size, Prediction error, Gradient의 곱으로 읽을 수 있다.
4. Monte Carlo는 $G_t$, TD는 $R_{t+1}+\gamma\hat v(S_{t+1})$를 Target으로 사용한다.
5. 공유 Parameter는 일반화를 만들지만 잘못된 Update도 여러 State로 퍼뜨릴 수 있다.

다음 글에서는 $Q(s,a)$를 Neural Network로 근사해 픽셀 입력에서 Action value를 바로 만드는 DQN을 살펴본다.

참고 자료

• David Silver, Lecture 6: Value Function Approximation
• 서울대학교 DSBA 연구실, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition