강화학습 공부 - (3) Model Free Prediction

Model Free Prediction

환경이 MDP로 표현될 수는 있지만, MDP가 주어지지 않은 문제를 풀고싶다.

이러한 상황에서 사용할 수 있는 기법들을 설명한다.

 

 

동적 계획법 (Dynamic Programming)

동적계획법은 문제를 작은 단위로 나누고, 반복을 통해 문제를 푸는 것이다.

이 방식은 상태의 수가 증가할 수록 계산 복잡도가 엄청나게 늘어난다.

또한, 동적 프로그래밍은 상태가 모두 알려진 MDP에 대해서만 풀 수 있다.

만약 MDP가 주어지지 않고, 모든 상태에 대해 알 수 없다면, 동적계획법을 사용할 수 없다.

따라서, 정책이 주어졌고, MDP를 알지 못할 때, 가치함수를 찾는 과정을 알아보고자 한다.

 

 

몬테카를로 학습 (Monte-Carlo Learning)

몬테카를로 학습은 직관적으로 에피소드에 대한 여러번의 경험을 통해 학습하는 것이다.

이 학습 방법은 게임과 같이 에피소드가 언젠가는 끝나는 상황에서 사용 가능하다.

한번의 에피소드에 받을 수 있는 보상을 정해두고, 받은 보상들의 평균을 통해 가치함수를 예측한다.

따라서, MDP 상태전환이나 보상이 알려져있지 않아도, 끝이 정해져 있다면 강화학습이 가능하다.

 

몬테카를로 정책 평가 (Policy Evaluation)

목표: 정책 $\pi$를 사용한 에피소드 경험을 통해 가치함수 $v_{\pi}$를 학습한다.

$S_1, A_1, R_2, …, S_k ~ \pi$

 

에피소드의 반환값, 즉 보상은 매 상태마다 감가율이 적용된 보상으로 존재한다.

$G_t = R_{t+1} + \gamma R_{t+2} + … + \gamma^(T-1)R_T$

 

따라서 아래의 벨만 방정식이 적용된 가치함수에서, 벨만 방정식 E를 경험적인 평균으로 대체하는 것이다.

$v_{\pi}(s) = E_{\pi} [G_t | S_t = s]$

 

벨만 방정식은 환경과 보상에 대한 수식, 즉 모델을 알아야 했지만,

몬테카를로 학습은 경험을 통해 각 상태에 대한 보상을 경험적인 평균 (샘플링)을 통해 근사하는 방법인 것이다.

 

이때 각 상태에 대해 근하사는 방법은 두가지가 존재한다.

 

First-Visit

에피소드를 진행하다 보면 하나의 상태에 여러번 방문할 수가 있다.

이 때 First-visit방법은 단순히 각 에피소드의 첫 방문에 대해서만 기록을 한다.

이를 위해 카운터를 두고, 만약 카운터가 이미 증가가 되었다면, 후 방문의 근사는 무시한다.

모든 상태에 대해 첫 방문을 기록해 이를 에피소드별로 쌓고 평균을 낸다.

그리고 몬테카를로 학습의 의미에 따라, 충분히 많은 샘플이 모이면, 실제 값과 거의 같아진다는 가정을 기반해 근사한다.

 

Every-Visit

위와 같은 상황에서, 한 에피소드에서의 모든 방문을 기록한다.

따라서 한 에피소드에서 방문이 여러번 기록될 수 있다.

이후에는 같은 방식으로 모든 방문을 평균을 내 근사하게 된다.

 

 

증분 평균 (Incremental Mean)

평균은 모든 데이터가 있을때만 계산할 수 있는것이 아니다.

데이터가 쌓일 때 순차적으로 더해 계산할 수 있다.

이 수식은 다음과 같다.

시퀀스 $x_1$, $x_2$, …에 대한 평균 $\mu_1$, $\mu_2$, …는 다음과 같이 계산될 수 있다:

$\mu k = \frac{1}{k} \sum_{j=1}^{k} x_j$

    $= \frac{1}{k} (x_k + \sum_{j=1}{k-1} x_j)$

    $=\frac{1}{k} (x_k (K - 1)*\mu_{k-1}$

    $=\mu_{k-1} + \frac{1}{k} (x_k - \mu_{k-1})$

 

강화학습은 순차적인 활동을 많이 하기 때문에, 위의 수식은 앞으로 매우 유용하게 쓰일것이다.

 

증분 몬테카를로 갱신 (Incremental Monte-Carlo Updates)

에피소드 $S_1, A_1, R_2, …, S_T$에 대해 순차적으로 가치함수 V(s)를 갱신한다.

반환값 $G_t$를 가지는 모든 상태 $S_t$에 대해서,

$N(S_t) = N(S_t) + 1$

$V(S_t) = V(S_t) + \frac{1}{N(S_t)} (G_t - V(S_t))$

 

N은 방문 카운터이다.

각 방문 시점에, 실제 가치 V와 리턴 G에 대해 에러를 계산하고, 근사중인 가치함수를 업데이트 한다.

 

 

시간차 학습 (Temporal-Difference Learning)

몬테카를로와 동일하게 시간차학습 역시 환경에서 에피소드를 통해 학습한다.

그리고 시간차학습 역시 상태전환과 보상에 대해 무지하다는 가정이다.

시간차학습은 한번에 하나의 에피소드를 끝내야하는 몬테카를로와는 다르게,

각 상태에 대해서, 에피소드가 끝나지 않은 상태에서 가치함수를 갱신하게 된다.

이를 부트스프래핑 ( bootstrapping)이라고 부른다.

각 상태에서 한스텝을 예측하고, 실제로 그 스텝에 도달했을 때 에러를 계산해 학습하게 된다.

 

평가: 몬테카를로 vs 시간차학습

목표: 정책 $\pi$를 사용한 에피소드 경험을 통해 가치함수 $v_{\pi}$를 학습한다.

 

증분 몬테카를로 every-visit방식에서는 가치 V(S_t)를 실제 리턴 G_t를 통해 갱신한다.

$V(S_t) = V(S_t) + \alpha (G_t - V(S_t))$

 

시간차학습에서는 현재의 가치를 다음 상태의 보상과 추후에 예상되는 보상의 합으로 한다.

따라서 위의 수식에서의 $G_t$가 곧 $R_{t+1} + \gamma V(S_{t+1}$ 이 되는 것이다.

$V(S_t) = V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1}) - V(S_t))$

 

$R_{t+1} + \gamma V(S_{t+1})$를 시간차 목표(TD target)라고 부른다.

$R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$를 시간차 에러 (TD error)라고 부른다.

 

 

장단점 1: 몬테카를로 vs 시간차학습

시간차는 결과가 나오기 전에 학습할 수 있다.

• 시간차는 매 스텝마다 학습을 한다.
• 몬테카를로는 하나의 에피소드가 끝나야만 학습할 수 있다.

시간차는 결과가 없더라도 학습할 수 있다.

• 시간차는 끝이 정해져있지 않은 시퀀스에서도 학습할 수 있다.
• 몬테카를로는 끝이 정해져있는 시퀀스에서만 학습할 수 있다.

 

바이어스 / 분산 등가교환

아래의 기본적인 리턴 수식은 바이어스가 없는 $V_{\pi}(S_t)$의 예측이다.

$G_t = R_{t+1} + \gamma R_{t+2} + … + \gamma^(T-1)R_T$

 

실제(이론상의) 시간차 목표 $R_{t+1} + \gamma V(S_{t+1})$역시 바이어스가 없는 $V_{\pi}(S_t)$예측이다.

 

하지만, 현실의 시간차 목표 $R_{t+1} + \gamma V(S_{t+1})$는 바이어스된 $V_{\pi}(S_t)$의 예측이다.

그리고 시간차 목표는 기본 리턴 수식(몬테카를로 리턴)에 비해 매우 낮은 분산을 갖게 된다.

 

따라서 몬테카를로는 바이어스가 없고 분산이 고른 예측이지만,

시간차학습은 비교적 그렇지 못하다는 의미이다.

 

장단점 2: 몬테카를로 vs 시간차학습

몬테카를로는 높은 분산을 갖고있고, 바이어스가 없다.

• 실제값에 수렴할 요소들을 더 많이 가지고 있다.
• 초기값에 덜 민감하다
• 매우 간단하고 이해가 쉽다

시간차는 적은 분산을 가지고 있고, 바이어스가 있다.

• 훨씬 빠르게 수렴한다.
• 하지만 항상 예측값을 사용하기 때문에 근사치를 이용한다.
• 초기값에 더 민감하다

 

배치 몬테카를로 & 배치 시간차학습

몬테카를로와 시간차학습은 결국 실제 값에 수렴한다.

그렇다면 정해진 수의 에피소드를 진행하고 멈추고 싶다면 어떻게 할까?

 

예제)

두개의 상태 A, B가 있다. 그리고 8번의 에피소드를 진행하였다.

A, 0, B, 0

B, 1

B, 1

B, 1

B, 1

B, 1

B, 1

B, 0

위의 결과값들의 보상을 토대로 V(A), V(B)는 얼마일지 구하라.

몬테카를로의 예측법에 따르면, 결과는 다음과 같이 구할 수 있다.

몬테카를로는 MSE (mean squared error)를 Minimuze하는 답으로 수렴한다.

따라서 실제로 얻는 보상에 최적화된 방식이다.

$\sum_{k=1}{K}\sum_{t=1}{T_k} (g_t^k - V(s_t^k))^2$

A부터 시작해 얻은 결과는 0하나이기 때문에 V(A) = 0이 된다.

 

시간차학습의 예측법에 따르면, 결과는 다음과 같이 구할 수 있다.

B로 가려면, A를 거쳐야한다는 가정을 한다.

위의 예측에 따르면 아래와 같은 MDP가 나온다.

 

시간차는 가장 가능할 법 한 MDP의 결과값으로 수렴한다.

데이터에 가장 알맞는 MDP <S, A, $\hat{P}$, $\hat{R}$, $\gamma$>는.

$\hat{P}^a_{s, s'} = \frac{1}{N(s,a)} \sum^{K}_{k=1}\sum^{T_k}_{t=1} 1(s_t^k, a_t^k, s_{t+1}^k = s, a, s')$

$\hat{R}^a_{s, s'} = \frac{1}{N(s,a)} \sum^{K}_{k=1}\sum^{T_k}_{t=1} 1(s_t^k, a_t^k = s, a, )r_t^k$

 

따라서 MDP의 결과값으로 수렴하기 때문에, V(A)는 0.75가 된다.

 

장단점 3: 몬테카를로 vs 시간차학습

시간차학습은 MDP를 활용한다.

• 따라서 MDP의 환경에서 더 유용하다.

몬테카를로는 MDP를 활용하지 않는다.

• 따라서 MDP가 아닌 환경에서 더 유용하다.

 

부트스트래핑 & 샘플링

부트스트래핑

• 실제 리턴이 아니라 예상치를 사용한다.
• 다이나믹 프로그래밍과 시간차학습은 부트스트래핑을 사용한다.

샘플링

• 기대치를 근사한다
• 몬테카를로와 시간차학습은 샘필링을 이용한다.

 

TD($\lambda$)

앞서 언급한 시간차학습은 TD(0)라고 표기한다.

이는 한 스텝의 예측을 하는 시간차 학습니다.

만약 시간차학습이 예측을 N스텝으로 하게 되면 이것이 TD($\lambda$)가 된다.

이 N이 에피소드의 끝까지 도달한다면 몬테카를로와 같아지는 것이다.

 

 

N-스텝 리턴

n = 1, 2, $\infty$ 에 대해서,

n = 1,      (TD(0)),       $G_t^(1) = R_{t+1} + \gamma V(S_{t+1})$

n = 1,                           $G_t^(2) = R_{t+1} + \gamma R_{t+2} + \gamma^2V(S_{t+1})$

…

n = $\infty$    (MC),          $G_t^(\infty) = R_{t+1} + \gamma R_{t+2} + … + \gamma^{T-1}R_T$

 

n이 1일 때는 한스텝과 감가율이 적용된 나머지를 예측하고,

2일 때는 두스텝과 감가율이 적용된 나머지를 예측한다.

무한대일때는 몬테카를로와 같아진다.

 

$G_t^(2) = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1}R_{t+n} + \gamma^nV(S_{t+n})$

 

그리고 가치함수를 업데이트 하는 수식은 다음과 같다.

$V(S_t) = V(S_t) + \alpha(G_t^{(n)} - V(S_t)$

 

 

N-스텝 리턴 평균

N-스텝 리턴에 대한 값을 평균을 내어 리턴을 계산할 수 있다.

이를 효율적으로 계산한 것이 바로 $\lambda$ 리턴이다.

 

 

위 그림에서의 $\lambda$는 각 리턴의 영향력이 얼마나 되는지를 결정하는 계수이다.

$V(S_t) = V(S_t) + \alpha(G_t^{(\lambda)} - V(S_t)$

 

Eligibility Trace

위의 사건이 순서대로 일어났다면, 어떤 사람은 마지막에 번개가 친 것이 가장 많이 일어난 벨때문이라고 생각할 것이고, 어떤 사람은 가장 최근에 일어난 전등불 때문에 일어났다고 생각할 것이다. Eligibility Trace는 이 두가지 개념을 조합한 것이다.

• Frequency Heuristic은 벨 처럼 가장 많이 일어난 사건에 점수를 준다.
• Recency Heuristic은 가장 최근에 일어난 사건에 점수를 준다.

 

$E_0(s) = 0$

$E_t(s) = \gamma\lambda E_{t-1}(s) + 1(S_t = s)$

 

위의 그림에서 밑의 막대는 한 상태를 방문한 횟수이다. 한번 방문할때마다 Eligibility Trace를 증가시키고, 그렇지 않을 때 지수적으로 감소시키는 것이다.

 

Backward View

TD($\lambda$)의 Backward View에서는 모든 상태 s에 대해 Eligibility Trace를 저장해 놓고, 모든 상태에 대해 가치함수 V(s)를 갱신한다. 이때 해당 갱신은 TD-에러 $\delta_t$와 Eligibility Trace $E_t(s)$에 비례하여 진행 된다.

$\delta_t = R_t + 1 \gamma V(S_{t+1}) - V(S_t)$

$V(s) = V(s) + \alpha \delta_t E_t (s)$