강화학습 강의 (CS234) 5강 - Value Function Approximation
- 본 포스팅은 CS234 5강의 내용을 정리합니다.
* 기본적인 Neural Network 및 머신러닝 지식이 있으면 이해가 훨씬 빠릅니다! (그냥 알고 있어야 이해가 될것 같습니다 ㅎㅎ)
이번 강의에선 Value Function Approximation, 줄여서 VFA에 대해서 배운다.
주로 다룰 내용은 위 목차의 2번이 되겠다.
(3번은 시간 문제상 대부분 생략된다. 어뜨케 1강에서 5강까지 죄다 후반내용은 생략하시네 교수님;;)
지난 시간에, (CS234 4강의 내용) 경험을 토대로 좋은 policy를 얻는 방법을 배웠었다.
SARSA, Q-Learning, Monte Carlo, TD 등등...
그런데, 지금까지 이런 내용들을 배울 땐 value function이나 state-action value function을 벡터나 매트릭스 형태로 나타낼 수 있다는 가정 하에 배웠었다.
(이를 Tabular representation이라고 한다.)
그러나, 실제로는 value function이 그렇게 돼 있는 경우는 흔치 않다.
가령 자율운전 자동차를 만든다고 할 때, state가 얼마나 많겠는가?
왼쪽으로 1도 갔을 때, 2도 갔을 때.... 180도 갔을 때 등등만 하더라도 그렇겠지만,
거기다가 속도나 주변 차들의 유무 등등 수없이 많은 state들이 존재하게 될 것이다.
그렇기 때문에, 벡터나 매트릭스로 value function을 나타내는 tabular representation은 강화 학습의 실제 적용에 부족한 점이 있다.
이를 해결하기 위해서, 1강에 배웠던 Generalization을 사용하게 될 것이다.
이걸 왜쓰냐고? 일단 계속 보자.
Value Function Approximation이란, Value function을 state, action을 parameter로 갖는 function으로 만드는 것이다.
위의 사진을 보면 이해가 쉬울 듯 하다.
(V와 Q 위에 있는 건 hat이라고 하고, 예측값을 의미한다.)
Neural Network를 배우고 온 사람들이라면 이해가 쉬울 것이라 생각한다.
state, action s,a와 weight vector W를 이용해서 V,Q값을 계산하는 것이므로...
Neural Network와 상당히 비슷한 모습을 보인다.
이 짓 (VFA) 를 하는 이유는...
모든 state에서 Dynamics, Value, Q, Policy들을 명시적으로 알 필요 없이,
state와 state, function 을 모두 아우르는 간단한 일반항을 만들기 위함이다.
가령, 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이 될 수 있다는 것이다.
Neural network와 굉장히 유사한 느낌이라고 보면 될듯 하다.
데이터가 적게 들어와도 fitting을 잘 할 수 있겠지만 그렇다고 그게 실제 data에 잘 적용 가능한 approximation이 아닌것 처럼 말이다.
또한, 위와 비슷한 이유로 VFA를 사용하면 메모리 / 연산 횟수 / 데이터 갯수는 줄어들겠으나, representational capacity도 같이 줄어들게 된다.
*representational capacity는 머신러닝 모델의 flexibility, 즉 실제 데이터의 적응력 정도를 의미함.
그러면 VFA에 사용할 approximator에는 어떤 것들이 있을까?
Linear approximator를 사용할 수도 있고,
Neural Network를 사용할 수도 있고, Decision tree를 사용할 수도 있다.
이는 머신러닝 모델을 선택하는 것과 비슷한 맥락으로 볼 수도 있을 것 같다.
이 중에서 오늘은 Linear feature representation을 다룰 것이다.
(다음 시간에 Neural network도 다룬다.)
여기서 Gradient Descent에 대한 설명이 나오는데, 여기다가 다시 Gradient Descent를 설명하긴 좀 그렇고 하니 이미 아는 사람은 그냥 넘어가고, 모르면 다음 링크를 타고 들어가서 확인해보자.
https://cding.tistory.com/21?category=704767 - Gradient Descent
https://cding.tistory.com/56?category=704767 - 미분과 Gradient Descent에 대한 이해
왜 다 내 블로그 링크냐고?
아니 뭐 그럼 다른데 가서 보등가 ㅎㅎ...
일단 본격적인 VFA에 들어가기 앞서, 일단 쉬운 버전 먼저 시작해보자.
어떤 state s에 대해서든 완벽한 진짜 Value 값을 던져주는 오라클이라는 존재가 있다고 가정하자.
그리고 그 데이터들을 바탕으로, state s에 대해 value를 찾는 function을 구하려고 한다.
즉 state s가 주어졌을 때 value 값을 찾아내는 w의 값을 찾아내고 싶다는 것이다.
이렇게 하면, Supervised learning하는 과정과 거의 동일해진다.
오라클이 던져준 실제 V값과 우리가 구하고 싶은 Value function을 갖고 Gradient Descent 알고리즘을 적용하면 최적의Value function이 나올테니 말이다.
여기서 잠깐 Stochastic Gradient Descent (SGD)에 대한 설명이 나온다.
그냥 Gradient Descent 알고리즘은 모든 데이터의 cost값들과 미분값들을 토대로 w값을 update해 주었다면,
SGD는 모든 데이터가 아니라 랜덤하게 몇개의 데이터의 cost값들과 미분값들만을 가지고 w값을 update한다.
이렇게 하면 한번 update할 때 시간도 덜 걸리고, 일단 Gradient Descent와 거의 유사한 결과를 낼 수 있다.
근데 갑자기 이걸 왜 알려주냐고?
솔직히 나도 모르겠다 ㅎㅎ;
그런데 실제로 우리가 오라클이라는 존재를 알고 있진 않다.
즉, 실제 Value값을 알려주는 존재같은건 없다는 것이다.
이런 상황에서, 우리는 지금처럼과 같이 model에 의존하지 않고 model-free한 VFA를 만들 방법을 강구해야 한다.
그런데 Model-free.. model.... free...?
이거 우리 한번 하지 않았나?
맞다. CS234 3강의 내용이 바로 Model-free policy evaluation이었다!
그 때 우리는 Monte Carlo methods와 Temporal Difference methods, 줄여서 TD methods를 배웠었다.
이 방법을 그대로 VFA에 가져와서, update 과정에서 function approximator을 fitting하는 과정만 추가해서 사용하면 어떨까?
일단 들어가기 앞서 Feature vector이 뭔지 먼저 정의하고 넘어가겠다.
..라고 해도 그냥 별거 없다. 각각의 state에 대한 정보를 담고 있는 vector라는 뜻이다.
자동으로 청소를 해주는 로봇청소기를 예로 들어보자.
만약 이 로봇청소기에 왼쪽부터 오른쪽까지 전방 180도에 대한 거리를 알려주는 센서가 달려있다고 해보자.
그렇다면, 이 로봇청소기의 feature vector은 1도에서 180도까지의 거리가 될 것이다.
x1(s)에는 1도까지의 거리, x2(s)에는 2도까지의 거리 .... 처럼 말이다.
그리고 이것을 x(s)라고 정의해 두도록 하겠다.
그런데 일단, 오라클을 다시 데려와서 Value 값을 알려달라고 해보자.
그러면 위처럼 Value function의 approximation을 구할 수 있게 된다.
위의 내용이 대충 어떤 내용이냐면,
(대충 x(s)값을 사용해서 Supervised learning과 비슷하게 흘러간다고 설명하는 말)
자, 이제 이해했길 바란다.
절대 설명하기 귀찮아서 저렇게 둔 것이 아니다.
그런데 아까도 말했다시피, 우리한테는 오라클 같은건 없다.
그러니, 저번에 배웠던 Monte Carlo 방식을 사용해보자.
Monte Carlo 방식에서 return Gt는 unbiased, noisy한 Value 값이었다.
그리고, Monte Carlo는 지금까지의 경험을 그대로 Gt를 내놓는다.
즉, 이 Gt값은 어떤 state에 대한 true discounted Value 값이 된다.
(그러니까 이 Gt는 경험했던 state에 대해서만큼은 오라클이 던져주는 Value값과 동일한 실제 Value값이다.)
이를 사용하면, 아까 전에 했던 supervised learning과 동일한 방식으로 VFA를 적용할 수 있다.
(수식은 위 수식 참고)
위는 Monte Carlo 방식을 사용한 VFA가 어떻게 작동하는지 잘 알려준다.
사실 이건 딱히 말할 게 없다. 위에 너무 잘 적혀있으니 그냥 위 ppt를 보고 알아가도록 하고, 자세한건 나중에 나올 예시로 짚어보도록 할 것이다.
그래도 대충 설명을 하자면,
(대충 원래 MC에서 weight update가 추가된 것 뿐이라는 내용)
참고로 알아둘 사항만 적어두자면,
Line 5 : First-visit이라고 적혀있긴 하지만, Every-visit MC에도 동일하게 적용가능하다.
Line 7 : X(s)는 아까 했던 feature vector이다.
그럼 직접 예제로 알아보도록 하자.
위 그림 (s1, s2, s3 ... s7)을 통해서 봤을 때,
저 원 안의 수식은 각 state의 feature vector의 계산식을 의미한다.
w 값의 초기화를 [1 1 1 1 1 1 1 1]이라고 하면,
State s1의 feature vector는 [2 0 0 0 0 0 0 1],
State s2의 feature vector는 [0 2 0 0 0 0 0 1],
....
State s7의 feature vector는 [0 0 0 0 0 0 1 2] 가 된다.
action은 a1, a2 두가지가 있는데,
a1은 그림에서 실선으로 표시되며, 무조건 Deterministic하게 s7으로 가게 되고,
a2는 그림에서 점선으로 표시되며, 각각 1/6의 확률로 s1, s2, s3, ... , s6로 가게 된다.
또한, 어떤 state, 어떤 action에도 reward는 0이다.
그리고 우리는 이 상황을 Monte Carlo 방식을 사용해서 w의 값을 update하고 싶은데,
모두 알다시피 Monte Carlo 방식은 무조건 episodic한, 즉 termination이 존재하는 경우에만 사용이 가능하기 때문에
s7에서 a1을 취하면 0.999의 확률로 s7으로 가고, 0.001의 확률로 terminate가 된다고 가정하고 시작할 것이다.
이 때, 우리에게 다음과 같은 episode가 주어졌다고 가정해보자 :
s1, a1, 0, s7, a1, 0, s7, a1, 0, terminate
(State, Action, Reward 쌍이다.)
α = 0.5라고 할 때, w의 값은 어떻게 update되는가?
우선 state s1에서 return 값 G는 무엇인가?
모든 reward가 0이므로, return G도 0이 될 것이다.
그렇다면 s1의 value function의 초기값은 무엇이 될까?
w를 모두 1로 초기화한다고 했고,
s1의 feature vector( x(s1) )가 [2 0 0 0 0 0 0 1] 이었으므로
1*2 + 1*0 + 1*0 + ... + 1*1 = 3이 된다.
이쯤에서 아까 저 위에서 w값을 update하는 방식을 가져오면,
w = w + α(G(s) - 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들로도 한번 연습해 봐도 좋을 듯 하다.
위 두 슬라이드는 Linear VFA가 Converge하는가를 다루는 내용인데, 본인이 이해를 잘 못한 관계로 설명은 생략 ㅎㅎ...
강의 안볼거면 그냥 SGD를 사용하면 Linear VFA는 Linear이 할수 있는 최선으로 fitting된다는 정도로만 알아두자..
(물론 거의 무한하게 계속계속 update할 경우에 그렇게 된다는 거다..)
그런데 방금 전의 예시처럼 episode가 하나하나씩 들어오는 것들을 갖고 w를 update해도 되기야 하겠지만,
만약 episode들의 데이터가 있으면 그냥 그거 그대로 쭉 쓰면 안될까?
그러니까, episode를 하나하나씩 진행시키면서 update하지 말고 한방에 데이터들을 갖고 update할 수 있지 않을까?
...있으니까 말했겠지 뭐!
이를 Batch Monte Carlo Value Function Approximation이라고 부른다.
이름이 너무 길긴 하다..
이건 그냥 Linear Regression에 적용하듯, Analytic하게 적용이 가능하다.
위의 수식만 봐도 대충 이해 가능할 듯 하다.
Monte Carlo 방식은 여기까지만 알아보도록 하고,
이제 TD learning 방식으로 넘어가도록 하자.
일단 저번 저번 시간에 배웠던 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 + 𝛾Vπ(s') 이었다면,
VFA에서의 target은 r + 𝛾Vπ(s', w) (V위에 hat은 마음의 눈으로 보자 ㅎ)가 된다.
즉, w값도 찾아야 한다, 이말이다.
아무튼 이렇게 J(w)의 값을 최소화시키는 w값을 찾아가는 것이 바로 TDVFA이다. (길게 쓰기 싫어서 줄여씀)
그냥 위 식을 막 바꾸다 보면 아래까지로 바꿀 수 있다는 뜻 ㅎ
이건 TD때 비슷하게 했으니 그냥 넘기겠읍니다 ^^7
그리고 이를 의사코드로 바꾸면 위처럼 쓸 수 있다.
아까 전의 ppt 내용과 동일하다는 것을 알 수 있다. (거의)
아까 전의 그 예제로 돌아가보도록 하자.
기억이 안난다고?
예제 설명한거 복사해서 메모장에 붙여넣고 해보도록 하자 ㅎ
뭐 아무튼, 그 상황에서 MC 대신 TD learning을 적용해보자.
(참고로, 이번 상황에선 MC가 아닌 TD를 사용하므로, 0.999 어쩌구 하는 부분은 걸러도 된다. episodic 하지 않아도 되니깐 ㅎ)
episode는 [s1, a1, 0, s7]이라고 가정하고, 𝛾=0.9라고 하자.
그러면, w의 update는 어떻게 될까?
위의 수식을 그대로 빼다 박으면,
Δ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]
그리고 이 Δw를 w에다가 더하면,
w = [0.85 1 1 1 1 1 1 0.7]
이런 식으로 바뀌는 것이다.
TD에서도 특정 값에 수렴하는 성질이 있다.
여기두 본인이 이해가 잘 안되는 관계로 생략 ㅎ..
참고로 짤막하게 지나가지만, TD가 MC보다 조금 더 좋은 성적을 내는 경향이 있다.
(그냥 조금 더 좋다)
이제 Control 부분을 다뤄 보도록 하자.
일단 들어가기 앞서서, Function approximation / Bootstrapping / Off-policy learning 을 한번에 적용하려 하면 불안정해질 수도 있다.
그러니까, converge가 안 될 수도 있고, 잘 될 수도 있다는 것이다.
그리고 Control을 할 때, 우리는 Q function을 사용할 것이다. (Action-Value 쌍)
일단 오라클이라는 존재가 우리에게 답을 알려준다면, 어떻게 하면 될까?
아까 전까지 했던 것과 거의 똑같이 하면 된다.
실제 Q값에서 Q의 예측값을 빼서, w값을 최소화시켜주면 되는 것이다.
(위에서는 SGD를 사용한다.)
오라클이 없다면?
아까처럼 feature vector을 만들어야 한다는 점은 동일하지만,
x(s) = [x1(s), x2(s) ... ] 가 아니라, state-action 쌍을 이루도록
x(s, a) = [x1(s, a), x2(s, a) ... ] 로 만들어 둔다.
그 외의 나머지 부분도 아까 전과 동일하다.
그리고 위의 내용들도 아까 전에 했던 것과 4강때 했던 것과 배우 비슷하다.
단지 Return값 Gt와 target이 Q와 관련된 식으로 변화하였고,
function approximator을 추가해줬을 뿐이다.
이쯤에서 5강 내용은 마치도록 하겠다.
본인이 이해를 못한 부분이 꽤 있어서, 이 뒤 부분은 사실 설명을 잘 할 자신이 없다.
나중에 다시 한번 정리하면서 수정할 날이 오면, 더 보충설명을 진행하도록 하겠다.
'인공지능 > 강화 학습 정리 (CS234)' 카테고리의 다른 글
| 강화학습 강의 (CS234) 7강 - Imitation Learning / Inverse RL (1) | 2019.08.26 |
|---|---|
| 강화학습 강의 (CS234) 6강 - CNN + DQN (Deep Q Network) (0) | 2019.06.06 |
| 강화학습 강의 (CS234) 4강 - MC / SARSA / Q-learning (1) | 2019.05.08 |
| 강화 학습 강의 (CS234) 3강 - Model-Free Policy Evaluation (Monte Carlo / Temporal Difference) (3) | 2019.04.21 |
| 강화학습 강의 (CS234) 2강 - Markov Process / MDP / MRP (2) | 2019.04.15 |