CS234 5강 Summary

CS234 강의 중 Lecture 5(Value Function Approximation)을 듣고 정리해보자

본 포스팅은 Stanford Univ의 CS234:Reinforcement Learning 강의를 듣고 정리한 글입니다.

Generalization이 필요한 이유

지난 시간에, (CS234 4강의 내용) 경험을 토대로 좋은 policy를 얻는 방법(SARSA, Q-Learning, Monte Carlo 등등)을 배웠었다.

그런데, 지금까지 이런 내용들을 배울 땐 state value function $V$ 나 state-action value function $Q$를 벡터나 매트릭스 형태로 나타낼 수 있다는 가정 하에 배웠었다. (이를 Tabular representation이라고 한다.)

그러나, 실제로는 value function이 벡터나 매트릭스 형태로 되어있는 경우는 흔치 않다.

가령 자율운전 자동차를 만든다고 할 때, state가 얼마나 많겠는가 ?

왼쪽으로 1도 갔을 때, 2도 갔을 때…. 180도 갔을 때, 하물며 오른쪽의 경우도 마찬가지다. 거기다가 속도나 주변 차들의 유무 등등 수없이 많은 state들이 존재하게 될 것이다.

그렇기 때문에, 벡터나 매트릭스로 value function을 나타내는 tabular representation은 강화 학습의 실제 적용에 부족한 점이 있다.

이를 해결하기 위해서, 1강에서 언급했던 Generalization 을 사용하게 될 것이다.

Value Function Approximation (VFA)

Value Function Approximation이란, Value function(V or Q)을 state, action을 parameter로 갖는 function으로 만드는 것이다.

(V와 Q 위에 있는 건 hat이라고 하고, 예측값을 의미한다.)

Neural Network에 대해서 공부해본 사람이라면 이해가 쉬울 것이다. state, action s,a와 weight vector W를 이용해서 V,Q값을 계산하는 것이므로 Neural Network와 상당히 비슷한 모습을 보인다.

VFA를 하는 이유

Value Function Approximation (VFA)를 하는 이유는 모든 state에서 Dynamics or reward model, Value, Q(State-action value), Policy들을 명시적으로 알 필요 없이, state 혹은 state와 action을 모두 아우르는 간단한 일반항을 만들기 위함이다.

가령, V(s,w) 함수를 제대로 만들어 놨다면, 어떤 state에서도 그냥 저 V(s,w)에 s값만 대입하면 value가 그대로 튀어나온다. 즉, w 벡터 하나만 있으면 어떤 상황에서도 value가 그냥 나온다. (딥러닝에서 가중치랑 비슷하네요)

이렇게 Generalization을 하면 좋은 점은,

(P,R) / V / Q / π를 저장하는데 메모리가 덜 들고,

(P,R) / V / Q / π를 계산하는데 연산이 덜 필요하며,

좋은 (P,R) / V / Q / π를 찾을 때 experience가 줄어든다.

(여기서 experience란 좋은 (P,R) / V / Q / π를 찾는 데 필요한 데이터의 수를 의미한다.)

주의할 점은, 필요한 data의 수가 줄어든다고 하더라도 적은 데이터만을 갖고 VFA를 하게 되면, 좋지 못한 approximation이 될 수 있다는 것이다.

데이터가 적게 들어와도 fitting을 잘 할 수 있겠지만 그렇다고 그게 실제 data에 잘 적용 가능한 approximation이 아닌것 처럼 말이다. (Neural network 에서의 Overfitting과 유사한 개념인 것 같습니다)

또한, 위와 비슷한 이유로 VFA를 사용하면 메모리 / 연산 횟수 / 데이터 갯수는 줄어들겠으나, representational capacity도 같이 줄어들게 된다. (representational capacity는 머신러닝 모델의 flexibility, 즉 실제 데이터의 적응력 정도를 의미한다.)

VFA에 사용할 Approximator

그러면 VFA에 사용할 Function Approximator에는 어떤 것들이 있을까 ?

Linear approximator를 사용할 수도 있고, Neural Network를 사용할 수도 있고, Decision tree를 사용할 수도 있다. 이는 머신러닝 모델을 선택하는 것과 비슷한 맥락으로 볼 수도 있을 것 같다.

이 중에서 오늘은 Linear feature representation을 다룰 것이다. (다음 포스팅에서 Neural network도 다룬다.)

Model-Free VFA

일단 본격적인 VFA에 들어가기 앞서, 일단 쉬운 버전 먼저 시작해보자.

어떤 state s에 대해서든 완벽한 진짜 Value 값을 던져주는 오라클이라는 존재가 있다고 가정하자.

그리고 그 데이터들을 바탕으로, state s에 대해 value를 찾는 function을 구하려고 한다. 즉 state s가 주어졌을 때 value 값을 찾아내는 w의 값을 찾아내고 싶다는 것이다.

이렇게 하면, Supervised Learning을 하는 과정과 거의 동일해진다. 오라클이 던져준 실제 V값(지도학습에서는 Label을 의미)과 우리가 구하고 싶은 Value function을 가지고 Gradient Descent 알고리즘을 적용하면 최적의 Value function이 나올테니 말이다

그런데 실제로 우리가 오라클이라는 존재를 알고 있진 않다. (지도학습과의 차이점이겠죠 ?) 즉, 실제 Value값을 알려주는 존재같은건 없다는 것이다.

이런 상황에서, 우리는 지금처럼과 같이 model에 의존하지 않고 Model-Free한 VFA를 만들 방법을 강구해야 한다.

3강에서 배웠었던 Monte Carlo(MC) methods와 Temporal Difference(TD) methods를 그대로 VFA에 가져와서, update 과정에서 function approximator을 fitting하는 과정만 추가해서 사용하면 어떨까 ?

본격적으로 들어가기에 앞서 Feature Vector$(x(s))$가 뭔지 먼저 정의해보자.

Feature Vectoc란 각각의 state에 대한 정보를 담고 있는 vector라는 뜻이다.

예를 들어, 자동으로 청소를 해주는 로봇청소기에 대해 생각해보자. 만약 이 로봇청소기에 왼쪽부터 오른쪽까지 전방 180도에 대한 거리를 알려주는 센서가 달려있다면 이 로봇청소기의 Feature Vector는 1도에서 180도까지의 거리가 될 것이다.

$x_{1}(s)$ 에는 1도까지의 거리, $x_{2}(s)$ 에는 2도까지의 거리 …. 처럼 말이다.

Linear VFA for Prediction with An Oracle

일단, 오라클을 다시 데려와서 Value 값($V^{\pi}$)을 알려달라고 해보자. 그러면 위처럼 Value function의 Approximation을 구할 수 있게 된다.

즉, 위의 슬라이드와 같이 Value Function$(\hat{V}(s;w)$을 나타낼 수 있으며 여기서 $x$와 $w$는 state의 Feature(180도 거리 측정값)를 제공할 것이다. (우리는 특정 Policy의 가치를 평가하는 것에 대해 관심이 있으므로 일단 Q대신 V에 대해서만 생각해보자.)

Linear Approximation(선형 근사)에서는 목적 함수(손실 함수)로 주로 MSE(Mean Squared Error)를 사용하므로 위 슬라이드에서도 동일하게 MSE를 사용하는 것을 확인할 수 있고, 가중치($w$)도 위 슬라이드에서 교수님이 써주신 수식을 통해 업데이트할 수 있다.

참고로 목적 함수는 예측값과 실제 값의 차이를 나타내는 함수로 주로 우리는 이 차이를 0으로 만들기 위해(즉, 예측값을 실제값에 가깝게 만들기 위해) Gradient Descent 알고리즘을 사용한다. (혹시 이해가 안되신다면 LG Aimers 강의 정리를 참고해주세요)

마지막으로 Linear VFA의 경우, SGD(Stochastic Gradient Descent를 사용하면 Linear이 할수 있는 최선으로 fitting된다. (물론 거의 무한하게 계속계속 update할 경우에 그렇게 된다는 거다.)

Monte Carlo VFA

그런데 아까도 말했다시피, 우리한테는 오라클 같은건 없다. 그러니, 저번에 배웠던 Monte Carlo 방식을 사용해보자.

Monte Carlo Value Function Approximation의 정확한 수식은 위의 슬라이드를 참고하자.

Monte Carlo 방식에서 return $G_{t}$는 unbiased, noisy한 Value 값이었다. 그리고, Monte Carlo는 지금까지의 경험을 그대로 $G_{t}$를 내놓는다. 즉, 이 $G_{t}$값은 어떤 state에 대한 True discounted Value 값이 된다.

(그러니까 이 $G_{t}$값은 경험했던 state에 대해서만큼은 오라클이 던져주는 Value값과 동일한 실제 Value값이다.)

이를 사용하면, 아까 전에 했던 supervised learning과 동일한 방식으로 VFA를 적용할 수 있다.

Monte Carlo VFA 알고리즘

위의 슬라이드는 Monte Carlo 방식을 사용한 VFA가 어떻게 작동하는지 잘 알려준다. 원래 MC에서 weight update가 추가된 것 뿐이다.

참고로 5번째 줄에서 First visit 대신 Every-visit을 사용해도 된다.

또한, 7번째 줄(교수님이 적으신 부분)에서 $x(s)$는 아까 이야기 했던 Feature Vector이다.

Monte Carlo VFA 예제

위 그림 $(s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}, s_{7}) $ 을 통해서 봤을 때, 원 안의 수식은 각 state의 feature vector의 계산식을 의미한다.

즉, 가중치 $w$값의 초기값을 [1 1 1 1 1 1 1 1]이라고 하면,

state $s_{1}$의 feature vector는 [2 0 0 0 0 0 0 1],

state $s_{2}$의 feature vector는 [0 2 0 0 0 0 0 1],

state $s_{3}$의 feature vector는 [0 0 2 0 0 0 0 1],

….

state $s_{7}$의 feature vector는 [0 0 0 0 0 0 1 2] 가 된다.

action의 경우 $a_{1}$과 $a_{2}$ 두 가지가 있는데,

$a_{1}$은 그림에서 실선으로 표시되며, 무조건 Deterministic하게 $s_{7}$으로 가게 되고,

$a_{2}$는 그림에서 점선으로 표시되며, 각각 1/6의 확률로 $s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}$로 가게 된다.

또한, 어떤 state, 어떤 action에도 reward는 0이다.

우리는 이 상황을 Monte Carlo 방식을 사용해서 w의 값을 update하고 싶은데, Monte Carlo 방식은 무조건 episodic한, 즉 termination이 존재하는 경우에만 사용이 가능하기 때문에 state $s_{7}$ 에서 action $a_{1}$을 취하면 0.999의 확률로 $s_{7}$ 으로 가고, 0.001의 확률로 terminate가 된다고 가정하고 시작할 것이다.

이 때, 우리에게 다음과 같은 episode가 주어졌다고 가정해보자 :

\[[s_{1}, a_{1}, 0, s_{7}, a_{1}, 0, s_{7}, a_{1}, 0, terminate]\]

이런 상황에서 $\alpha = 0.5$ 라고 할 때, w의 값은 어떻게 update 될까 ?

우선 state $s_{1}$ 에서 return 값 G는 무엇인가 ? 모든 reward가 0이므로, return G도 0이 될 것이다.

그렇다면 state $s_{1}$의 예측 value function$(\hat{V})$의 초기값은 무엇이 될까 ?

w를 모두 1로 초기화한다고 했고, state $s_{1}$ 의 feature vector$(x(s_{1}))$ 가 [2 0 0 0 0 0 0 1] 이었으므로

1x2 + 1x0 + 1x0 + … + 1x1 = 3이 된다.

이쯤에서 아까 w값을 update하는 방식을 가져오면,

\[w = w + \alpha (G(s) - \hat{V}(s,a)) * x(s)\]

였으므로, 위에서 구한 값들을 여기에 대입하면

w = [1 1 1 1 1 1 1 1] + 0.5(0 - 3) * [2 0 0 0 0 0 0 1]

= [1 1 1 1 1 1 1 1] + -1.5 * [2 0 0 0 0 0 0 1]

= [1 1 1 1 1 1 1 1] + [-3 0 0 0 0 0 0 -1.5]

= [-2 1 1 1 1 1 1 -0.5]

이렇게 w값이 update가 된다.

그런데 방금 전의 예시처럼 episode가 하나하나씩 들어오는 것들을 갖고 w를 update해도 되기야 하겠지만, 만약 episode들의 데이터가 있으면 그냥 그거 그대로 쭉 사용해도 된다.

다시 말해서, episode를 하나하나씩 진행시키면서 update하지 말고 데이터들을 가지고 한방에 update할 수 있다.

이를 Batch Monte Carlo Value Function Approximation이라고 부른다. 수식은 위의 슬라이드를 참고하자.

Temporal Deifference(TD(0)) Learning VFA

일단 저번 저번 시간에 배웠던 TD learning을 잠깐 살펴 보자면,

TD learning은 DP 방식에서 사용하던 bootstrapping을 사용하며 MC 방식에서 사용한 sampling 방식도 사용했었다.

또한 들어가기에 앞서, 지금까지 배운 세 가지 approximation을 생각보자.

1. (지금 하고 있는) function approximation

2. bootstrapping (DP / TD)

3. sampling (MC / TD)

우리는 지금까지 배웠던 내용을 토대로 이 세개 모두 다 on-policy라는 것을 쉽사리 알 수 있을 것이다.

결국 지금 갖고 있는 데이터를 바탕으로 가는 것이니 말이다.

그러면, 결국 이 모든 것이 전부 supervised learning과 크게 다르지 않게 된다.

즉, 우리가 하고 있는 대부분의 것들 (위에 세가지) 는 convergence의 문제에서 어느 정도 자유로울 수 있다는 것이다. (거의 항상 수렴한다는 뜻이다)

이제 본격적으로 들어가서, 원래 TD의 target (sampling)은 $r + \gamma V^{\pi}(s^{\prime})$ 이었다면, VFA에서의 target은 $r + \gamma \hat{V^{\pi}}(s^{\prime},w)$ 가 된다.

즉 w값도 찾아야 한다, 이말이다.

이렇게 위 슬라이드에서의 J(w)값을 최소화시키는 w값을 찾아가는 것이 바로 Temporal Deifference(TD(0)) Learning VFA 이다.

$\triangle w$의 경우 위 슬라이드 수식을 통해 구할 수 있다.

Temporal Deifference(TD(0)) Learning VFA 알고리즘

위에서 배웠던 수식들을 의사코드로 표현하면 위 그림과 같다.

Temporal Deifference(TD(0)) Learning VFA 예제

MC VFA 예제에서 다루었던 내용을 TD method에서도 다루어보자.

참고로, 이번 상황에선 MC가 아닌 TD를 사용 즉, episodic 하지 않아도 되므로, MC에서 teminate 될 확률이 0.001라고 가정 했던 부분은 빼도 된다.

튜플(Trajectory)이 $[s_{1}, a_{1}, 0, s_{7}]$라고 가정하고, $\gamma = 0.9$ 라고 하자. 그러면 w의 update는 어떻게 될까?

위 슬라이드에서의 TD update 수식을 그대로 사용하면,

$\triangle w$ = 0.5 * (0 + 0.9 * ([0 0 0 0 0 0 1 2]$^{T}$ [1 1 1 1 1 1 1 1]) - [1 0 0 0 0 0 0 2]$^{T}$ [1 1 1 1 1 1 1 1]) * [1 0 0 0 0 0 0 2]

= 0.5 * (2.7 - 3) * [1 0 0 0 0 0 0 2]

= 0.5 * -0.3 * [1 0 0 0 0 0 0 2]

= [-0.15 0 0 0 0 0 0 -0.3] 이다.

따라서 이러한 $\triangle w$ 를 $w$에다가 더하면 update 된 $w$ = [0.85 1 1 1 1 1 1 0.7] 가 된다.

Control using VFA

이제 Control 부분을 다뤄 보도록 하자.

일단 들어가기 앞서서, Function Approximation / Bootstrapping / Off-policy learning 을 한번에 적용하려 하면 불안정해질 수도 있다.

다시 말해서, converge가 안 될 수도 있고, 잘 될 수도 있다는 것이다.

Control을 할 때, 우리는 V가 아니라 Q function을 사용할 것이다. (Action-Value 쌍)

일단 오라클이라는 존재가 우리에게 답을 알려준다면, 어떻게 하면 될까?

아까 전까지 했던 것과 거의 똑같이 하면 된다.

실제 Q값에서 Q의 예측값을 빼서, w값을 최소화시켜주면 되는 것이다.

(위에서는 SGD를 사용한다.)

만약에 오라클이 없다면, 아까처럼 feature vector을 만들어야 한다는 점은 동일하지만,

VFA 즉, V함수를 사용했을 때와 달리

$x(s) = [x_{1}(s),x_{2}(s) … ]$ 가 아니라, state-action 쌍을 이루도록

$x(s,a) = [x_{1}(s,a), x_{2}(s,a) …]$ 로 만들어 줘야 한다.

그 외의 나머지 부분도 아까 전과 동일하다.

또한 3강에서 배웠던 MC, SARSA, Q-learning 방법들을 Control 하는 것도 아까 전에 V함수에서 $ \triangle w$를 구했던 방법과 매우 비슷하다.

위 슬라이드 처럼 단지 Returen 값 $G_{t}$와 target이 Q(s,a)와 관련된 식으로 변화하였고, function approximator을 추가해줬을 뿐이다.

여기서 function approximator 란 parameter(w)를 이용하여 실제 값$(Q^{\pi}(s,a))$에 approximate하는 함수를 의미하며, 위 슬라이드의 수식 중 $\hat{Q} (s,a)$ 등의 부분들이 해당된다.

Reference

• 강화학습 강의 (CS234) 5강 - Value Function Approximation