살사(SARSA) / 큐러닝(Q-Learning)

 

 

[강화학습]

강화학습은 환경의 모델을 몰라도 

환경과의 상호작용을 통해서 최적 정책을 학습합니다.

 

예측은 에이전트가 환경과의 상호작용을 통해

정책에 대한 가치함수를 학습하는 과정입니다.

 

예측에는 몬테카를로 예측, 시간차 예측이 있습니다.

제어에는 시간차 체어(살사)가 있습니다.

그리고 오프폴리시 제어인 큐러닝이 있습니다.

 

강화학습에서 정책을 통해 가치함수를 구하는 과정을 에측 이라합니다.

그리고 정책 평가와 정책 발전을 합친 것을 제어 라고합니다.

 

[몬테카를로 예측]

방정식을 알지 못해도 답을 얻을 수 있는 방법이 있습니다.

바로 몬테카를로 예측입니다.

주어진 식이 없이 무작위로 반복하여 답을 얻어낼 수 있는 방식입니다.

 

가치함수를 추정할 때 에이전트가 한 번 환경에서 에피소드를 진행하는 것이 샘플링입니다.

샘플링을 통해 정책에 따른 가치함수를 구하려면 계속 행동하면 됩니다.

에피소드는 끝이 있다고 가정한다면 반환값을 알 수 있습니다.

 

\(G_t = R_{t+1} + \gamma R_{t+2} + .... + \gamma^{T-t+1}R_r\)

위 수식은 시간t부터 마침 상태 T까지의 반환값입니다.

 

몬테카를로 예측을 위해서는 여러 번의 에피소드를 진행하며

반환값들의 평균을 통해 가치함수 값을 추정해야 합니다.

 

몬테카를로 예측에서는 환경의 모델을 알아야 하는 \(E_\pi\)를 계산하지 않고  

여러 에피소드를 통해 구한 반환값의 평균을 통해 \(v_\pi(s)\)를 추정합니다.

 

\(v_\pi(s) \sim {1 \over N(s)} \sum_{i=1}^N(s) G_i (s)\)

 

추정된 가치함수 \(V_{n+1}\)에 대한 수식은 아래와 같습니다.

\(V_{n+1} = {1 \over n} \Sigma_{i=1}^n G_i = {1 \over n} ( G_n + \Sigma_{i=1}^{n-1}G_i)\)

= \({1 \over n} (G_n + (n-1) {1 \over n-1} \Sigma_{i=1}^{n-1}G_i)\)

\({1 \over n-1} \Sigma_{i=1}^{n-1}G_i\)는 \(V_n\) 입니다.

 

따라서 아래와 같습니다.

 

= \({1 \over n-1}(G_n + (n-1)V_n\)

 

= \({1 \over n-1}(G_n + nV_n - V_n)\)

 

= \(V_n + {1 \over n}(G_n - V_n)\)

 

원래 가지고 있던 가치함수 \(V(s)\)에 \({1 \over n}(G_n - V_n)\)를 더함으로써 업데이트를 합니다.

 

\(V(s) \leftarrow V(s) + {1 \over n}(G(s) - V(s))\)

 

가치함수 수식에서 \(G(s) - V(s)\)를 오차라고 하며, \({1 \over n}\)은 스텝사이즈로서

오차를 얼마를 가지고 업데이트할 지 결정합니다.

 

스텝사이즈는 일반식에서 \(\alpha\)로 표시합니다..

 

\(V(s) \leftarrow V(s) +\alpha(G(s) - V(s))\)

 

[시간차 예측]

시간차 예측은 몬테카를로 예측과는 다르게 타임스텝마다 업데이트합니다.

\(G_t\)는 에피소드가 끝나야 알 수 있는 값이였습니다.

시간차 예측에서는 \(G_t\) 대신 \(R_{t+1} + +\gamma v_\pi(s`)\)를 사용합니다.

 

\(v_\pi(s) = E_\pi [ R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t =s ]\)

 

위 수식에서 DP처럼 기대값을 사용하지 않고

\(R_{t+1} + \gamma v_\pi(S_{t+1})\)를 

샘플링하여 업데이트 합니다.

 

결과적으로 시간차 예측의 수식은 아래와 같습니다.

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

 

1. \(R_{t+1} + \gamma V(S_{t+1}))는 업데이트의 목표

2. \(\alpha(R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\)는 업데이트의 크기

를 나타냅니다.

 

2번은 시간차 에러 라고 표현합니다.

 

시간차 예측은 많ㅎ이 샘플링을 통해 업데이트하면 가치함수에 수렴합니다.

그리고 많은 경우에 몬테카를로 예측보다 빠른 시간안에 참 가치함수에 근접합니다.

하지만 초기 가치함수 값에 다라 예측 정확도가 많이 달라집니다.

 

[살사]

시간차제어 = 시간차 예측 + 탐욕 정책

 

살사는 큐함수를 사용한 탐욕 정책을 사용하며

시간차 제어에서 큐함수를 이용하여 업데이트합니다.

 

\(\pi(s) = argmax_{a \in A} Q(s,a)\)

 

\(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t))\)

 

시간차 제어에서의 샘플은 \([S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}]\)을 사용합니다.

 

초기의 에이전트에게 탐욕 정책은 잘못된 학습으로 가게 할 가능성이 크므로

다양한 경험을 할 수 있도록 탐험을 시켜줘야 합니다.

탐험을 위해서는 \(\epsilon\)-탐욕정책이 필요합니다.

 

 \(\epsilon\)-탐욕정책은  \(\epsilon\)만큼 확률로 

탐욕적이지 않은 행동을 선택하게 합니다.

 

\(\pi(s)= \begin{cases} a^* = argmax_{a \in A} Q(s,a) & \mbox{probability of 1-epsilon} \\ a \ne a*, & \mbox{probability of epsilon} \end{cases}\)

 

위 수식은 최적의 큐함수를 찾음에도 불구하고 탐험을 합니다.

그래서 학습을 진행함에 따라 \(\epsilon\)을 줄이는 방법도 있습니다.

 

[살사의 한계]

현재의 상태에서 탐욕적인 행동을 했다고 가정하고

다음 상태에서 탐험을 해서 얻은 보상이 음수라고 가정합니다.

위 상황이 되면 현재 상태에서 탐욕적인 행동을 하는 큐함수 값은 음수가 됩니다.

그래서 다음 에피소드에서 이전의 상태에 도달했을 때

탐욕적인 행동을 하려하면 그 행동을 하지 않게 될 것입니다.

그런데 그 길이 보상을 주어지는 길을 막게 된다면!

갇혀 버리는 상황이 오게 됩니다.

 

살사는 온 폴리시 시간차 제어, 즉 자신이 행동하는 대로 학습하는 시간차 제어입니다.

이러한 딜레마를 해결하기 위해

오프폴리시 시간차 제어 즉, 큐러닝을 사용합니다.

 

[큐러닝]

큐러닝은 살사와는 다르게 현재 상태에서 \(\epsilon\)-탐욕정책을 따릅니다.

그리고 다음 상태에서는 가장 큰 큐함수를 현재 큐함수의 업데이트에 사용합니다.

따라서 현재 상태의 큐함수를 업데이트하기 위해 필요한 샘플은 <s,a,r,s`> 입니다.

 

큐러닝을 통한 큐함수 업데이트 수식은 아래와 같습니다.

\(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha(R_{t+1} + \gamma \underset{a`} max (Q(S_{t+1}, a`) - Q(S_t, A_t))\)

 

위 수식은 벨만 최적 방정식과 비슷합니다.

\(q_*(s,a) = E[R_{t+1} + \gamma \underset{a`}max q_*(S_{t+1}, a`) | S_t = s, A_t = a]\)

 

결과적으로 살사는 큐함수 업데이트를 위해 벨만 기대 방정식을 사용하고

큐러닝은 벨만 최적 방정식을 사용합니다.

 

지금까지 살사 / 큐러닝을 이해하기 위해서 여러 개념들이 소개되었네요.

전부 비슷비슷한 것 같지만 각자 차이점이 있고

처음에 기본적으로 배웠던 

벨만 기대 방정식 / 벨만 최적 방정식

을 사용하여 모든 수식이 성립하는 것을 볼 수 있었습니다.

 

이렇게 보고나니 기초가 정말 중요하다는 생각이 드네요.

이해가 안되는 부분이 있다면 처음부터 천천히 다시보는게 

뒤 부분에 있어서 더 도움이 될 듯 합니다.

 

화이팅입니다~~!!