Linear Method

특별히 중요한 경사 하강 함수 추정 방법 중 하나가 선형 방법(linear method) 이다.

용어

• $V_t$ 수렴하는 보상의 기대값에 대한 함수 추정치

• $\vec{\theta}_t$ 함수 추정의 parameter 의 벡터

Feature Vector

모든 상태에 대응 되는 feature 에 대한 컬럼 벡터가 있고,

$\vec{\Phi}_s = ( \Phi_s(1), \Phi_s(2), ... , \Phi_s(n) )^T$

같은 원소 개수의 $\vec{\theta}_t$ 가 있다.

feature 생성 방법은 다양하며, 아래 언급된다.

feature 가 적용된 함수 추정은 다음 식과 같다.

 식 8.8

$V_t = \vec{\theta}_t^T \vec{\Phi}_s = \sum_{i=1}^n \theta_t (i) \Phi_s (i)$ 

이런 형태의 함수 추정을 'linear in the pararmeters' 라고 말하고, 간단히 linear 라고 한다.

선형 함수 추정의 gradient-descent 방식을 사용하는 것은 자연스럽다. (?)

선형 함수의 $\vec{\theta}_t$ 대한 gradient ( 미분) 은 아래식과 같이 간단하다.

$\nabla _{\vec{\theta}_t} V_t (s) = \vec{\Phi}_s$

따라서 앞서 언급한 식 8.3 은 선형 방법에서는 간단해진다.

Convergence

선형 방법에서는 최적점이 하나만 존재한다.

따라서 선형 방법을 사용하는 어떤 방법도 지역 최소 혹은 전역 최소에 수렴하는 것이 항상 보장 된다.

선형 방식에서 경사 하강 기법은 간단하기 때문에 수학적인 분석 측면에서 좋은 방법이다.

거의 모든 종류의 학습 시스템에서 유용한 수렴성의 결과는 선형 방법에서 이루어진다. (?)

Convergence of TD($\lambda$)

특히, 앞 섹션에서 언급된 gradient-descent TD($\lambda$) 알고리즘은 선형 방식에서 수렴성이 증명 되었다.

다만, step-size 가 시간에 따라 감소해야 하고 2.7 의 조건을 만족해야 한다.

하지만, 최소점($\vec{\theta}^*$)으로 수렴하는 것은 아니고, $\vec{\theta}_{\infty}$ 에 수렴한다

$MSE(\vec{\theta}_{\infty} )$

 식 8.9

$MSE(\vec{\theta}_{\infty} ) \le \frac {1-\gamma \lambda}{1- \gamma} MSE( \vec{\theta}^*)$ 

위 식은 '점진적 오류'(asymptotic error) 는 최소 MSE 의 $\frac {1-\gamma \lambda}{1- \gamma}$ 배 보다 클 수 없다는 뜻이다.

$\lambda$ 가 1 에 가까워지면, 점점 최소 MSE 보다 커질 수 없게 된다.

이 한계는 다른 on-policy bootstrapping 방법에도 동일 하게 적용된다.

예를 들어, on-policy distribution 이 적용된 식 8.3 의 선형 경사하강 백업 방법은 TD(0)의 결과와 동일하게 수렴한다.

기술적으로 이 한계는 '할인율인 적용된 연속적 작업' ( discounted continuing task) 에만 적용 되지만, 에피소드 작업에서도 비슷한 결과가 나올 것으로 예상 된다.

기술적으로 보상, feature, 감소하는 step-size 등의 조건들이 더 있지만, 이 책에서는 생략 되어 있다.

자세한 사항은 Tsitsiklis and Van Roy, 1997a 의 논문에 나와 있다.

Diverge : not on-policy distribution

위의 결과는 on-policy distribution 에 따라 상태가 백업되었기 때문이다.

다른 백업 분포에 대한 함수 추정을 사용하는 bootstrapping 방법은 무한대로 발산한다.

이에 대한 예제와 가능한 해법에 대한 논의는 섹션 8.5 에 있다.

Choosing Feature

이런 기술적 결과를 감안하더라도 선형 방법은 계산과 데이터 관점에서 매우 효율적이기 때문에 흥미롭다.

아무튼, 이는(?) 상태가 feature 로 표현되는 방식에 매우 의존적이다.

feature를 선택하는 것은 강화 학습 시스템에 해당 분야의 지식을 추가하는 중요한 방법이다.

직관적으로, feature 는 원래 task 에 맞는 것이어야 하며, 이에 따라 일반화도 높아진다. (?)

예를 들어 기하학적 개체에 대해 가치를 매긴다면, 모양, 색상, 크기 또는 기능 등을 feature 로 선택해야 한다.

모바일 로봇의 상태에 대해 가치를 부여한다면, 위치, 배터리 잔량, 최근 음파 탐지 기록 등을 feature 로 선택해야 한다.

Combination Features

일반적으로, 원래 속성들을 조합한 feature 도 필요하다.

이렇게 feature 조합이 필요한 이유는 선형 방식에서 feature 들 간의 상호 작용을 할 수 없게 하기 때문이다.

j 번째 feature 가 부재할 때 i 번째 feature 의 가치가 높아지는 등의 상호 작용이 필요한 경우도 있다.

예를 들어, 막대기 균형잡기 ( example 3.4 ) 에서, 현재의 각속도는 각위치에 따라 좋을 수도 있고 나쁠 수도 있다.

높은 각에서 각속도가 높으면, 넘어질 위험이 높지만, 각이 작을 때 높은 각속도가 높으면 넘어지지 않을 수 있다.

함수 추정에서 이런 상호 작용 때문에 feature 들이 연동된 새로운 feature 가 필요하다.

다음에 좀더 일반적인 경우를 다룰 것이다.