Gradient Descent Methods

Prediction 의 gradient descent 로 구현한 알고리즘이 소개 된다.

파라미터들은 컬럼 벡터이며,

$\vec{\theta}_{t} = ( \theta_{t}(1), \theta_{t}(2), ... \theta_{t}(n) ) ^\intercal$

$V_{t}(s)$ 는

• '매끄러운'(smooth 무한번 미분 가능한)
• 미분 가능한 (differentiable)
• $\vec{\theta}_{t}$ 에 대한 함수이다.

Updating $\theta$

아래 식으로 파라미터들을 갱신한다.

식 8.2

$\vec{\theta}_{t+1} = \vec{\theta}_{t} - \frac {1}{2} \alpha \nabla _{ \vec{\theta}_{t} }  [ V^{\pi}(s_{t}) - V_{t}(s_{t}) ] ^{2}$

    $= \vec{\theta}_{t} + \alpha  [ V^{\pi}(s_{t}) - V_{t}(s_{t}) ]  \nabla _{ \vec{\theta}_{t} } V_{t}(s_{t})$

• $\alpha$ 는 양수 step-size 이다.
• $\nabla _{ \vec{\theta}_{t} } f(\vec{\theta}_{t} )$ 는 함수 f 에 대한 편미분 벡터이다.
  • $\nabla f (\theta) = ( \frac { \partial f(\theta)} { \partial \theta_{1} }, \frac { \partial f(\theta)} { \partial \theta_{2} },..., \frac { \partial f(\theta)} { \partial \theta_{n} } )$
  • 이 벡터를 $\theta$ 에 대한 f 의 gradient 라고도 한다.

미분 값을 빼서 갱신하므로 경사 하강 기법이다.

사실, step-size 가 시간에 따라 감소해야 수렴성이 보장된다. ( 2.6 Tracking a Nonstationary Problem 의 식 2.7 혹은 2.8 에 대한 내용으로 보인다. )

( 현재 많은 framework 가 있으므로 위의 내용을 실제로 구현할 필요는 없는 것 같다. )

Not Minimal Loss at One Step

위 식이 의미하는 것은 가중치를 조그만(?) 변경 시킨다는 뜻이다.

아래 나오는 알고리즘을 보면, 한 에피소드에서 한 스텝마다 위의 식으로 가중치를 조그만 변경 시킨다.

한 스텝에서 주어진 입출력으로 loss 값을 최소한으로 줄이지 않는다.

위 식의 값 만큼만 아주 조금 loss 가 줄어든다.

책에서는 한 스텝에 loss 를 최소한으로 줄이지 않는 이유가 loss 의 균형 유지 때문이라고 했다.

loss 균형(?) + Convergence (?)

다음은 책 내용이다.

gradient 방향으로 왜 작은 값만으로 $\theta$ 를 갱신하는지 바로 인식되지 않을 것이다.

바로 loss 를 최소로 줄이면 안되는지 의문을 품을 수 있다.

많은 경우 loss 를 바로 최소로 줄일 수 있지만, 바람직하지 않다.

모든 상태에서 loss 가 0 인 기대값(value function)을 찾는 것이 목표가 아니고, 다른 상태들의 loss 와 균형을 이루는 추정이 목표다.

( loss 균형이 뭔지 불확실함 )

에피소드의 한 스텝마다 loss를 최소화시키면, 앞서 얘기한 균형(?)을 찾을 수 없다.

( 여기서 갑자기 수렴 조건이 나온다. )

사실, gradient 방법의 수렴성은 시간에 따라 감소하는 step-size 가 필요하다.

그것(?)이 확률적 추정 조건 (2.7) (stochastic approximation conditions ) 을 만족하면서 감소한다면, 지역 최적점에 수렴할 것이다.

Unknown $V^{\pi}(s_{t})$

실제 기대값 $V^{\pi}(s_{t})$ 는 알 수 없는 값이다. ( 알고리즘으로 점진적으로 추정해야 될 값이다 )

따라서 $V^{\pi}(s_{t})$ 대신, 현재의 추정치 $v_{t}$를 사용해서 parameter 를 갱신한다.

식 8.3

$\vec{\theta}_{t+1} = \vec{\theta}_{t} + \alpha [ v_{t} - V_{t}(s_{t}) ] \nabla _{ \vec{\theta}_{t} } V_{t}(s_{t})$ 

이런 방법을 일반화된 gradient-descent 갱신 ( general gradient-descent update ) 이라고 한다.

Unbiased Estimate (?) And Local Optimum

만약 $v_{t}$ 가 unbiased estimate (?) 이면, 즉, $E\{v_{t}\} = V^{\pi}(s_{t})$ 이면, $\vec{\theta}$ 는 지역 최적점 (local optimum)에 수렴한다.

다만, step-size 가 감소하는 확률적 추정 조건 ( stochastic approximation conditions 2.7 ? ) 하에서만 보장 되는 듯 하다.

stochastic approximation conditions 는 2.6 Tracking a Nonstationary Problem 에서 언급되어 있다.

Monte Carlo Gradient Descent Convergence (?)

예를 들어, 정책$\pi$을 사용하여 환경과 상호 작용하여 생성된 상태들이 있다고 가정 한다.

$R_{t}$ 를 각 상태들($s_{t})$을 수행(following)해서 얻은 return (보상들의 합) 이라고 지칭하자.

어떤 상태의 실제 가치(the true value)는 Return 의 기대값이기 때문에,

Monte carlo 의 target ($v_{t}=R_{t}$ ) 는 $V^{\pi}(s_{t})$ 에 대한 바이어스가 없는 추정치이다.

이 선택으로 (with this choice ) 식 8.3 은 지역 최적점에 수렴한다.

따라서 monte carlo state-value prediction 에 대한 gradient descent 는 지역 최적점을 찾는 것이 보장 된다.

DP, TD( $\lambda$ ) Gradient Descent No Convergence (?)

비슷하게 , n-step TD Return 들의 평균을 $v_{t}$ 로 볼 수 있다.

예를 들어 TD($\lambda$) 의 gradient descent 는 $\lambda$-return ,$R^{\lambda}_{t} = v_{t}$ 을 $V^{\pi}(s_{t})$ 에 대한 추정치로 사용 한다.

forward view 관점에서 $\theta$ 는 아래 식으로 갱신 된다.

식 8.4

$\vec{\theta}_{t+1} = \vec{\theta}_{t} + \alpha [ R^{\lambda}_{t} - V_{t}(s_{t}) ] \nabla _{ \vec{\theta}_{t} } V_{t}(s_{t})$

불행하게도, $\lambda < 1$ 이면 $R^{\lambda}_{t}$ 는 바이어스가 있는 $V^{\pi}(s_{t})$ 의 추정치다.

따라서 식 8.4 는 지역 최적점에 수렴하지 않는다.

DP 도 target 을 $v_{t} = E_{\pi} \{ r_{t+1} + \gamma V_{t}(s_{t+1} ) | s_{t} \}$ 로 사용하면, 동일하게 수렴하지 않는다.

그럼에도 불구하고, 이런 bootstrap 방법들은 매우 효율적이고, 다음 챕터에 나올 중요하고 특별한 케이스에서 다른 성능상의 이점이 있다.

지금은, 이 방법들과 gradient descent (식8.3) 형태(?)의 관계만 강조한다. (?)

비록 8.4 의 increments 는 gradient 아니지만, 식 8.3 과 같이 원하는 $V^{\pi}(s_t)$ 를 대체하는 bootstrapping 추정 gradient 방법으로 보는게 유용하다.

backward view

식 8.4 는 forward view 관점이다.

backward view 는 다음 식으로 볼 수 있다.

식 8.5
$\vec{\theta}_{t+1} = \vec{\theta}_{t} + \alpha \delta _{t} \vec{e}_{t}$

$\delta _{t}$ 는 봤던 TD-error 이다

 식 8.6
$\delta _{t} = r_{t+1} + \gamma V_t ( s_{t+1} ) - V_t(s_t)$

$\vec{e}_t$ 는 eligibility trace 의 컬럼 벡터이며, 식 8.7 로 갱신된다.

 식 8.7
$\vec{e}_t = \gamma \lambda \vec{e}_{t-1} + \nabla_{ \vec{\theta}_t } V_t(s_t)$

알고리즘 on-line gradient-descent TD($\lambda$)

두 개의 gradient 기반 방법이 강화학습에 많이 사용 된다.

그 중 하나가 다층 인공 신경망이며, 이는 오류 역전파 알고리즘을 사용한다.

두 번째 방법이 선형 방법이며, 다음 챕터에서 다루어진다.