이번 강의까지가 본격적으로 가기 전 마지막 강의야. 6부터 10이 본격적인 강의니까 여기까지를 마스터 해야되. 어떻게 유도되었는 지도 다 알아야되. 난 정리하면서 거의 마스터 수준이고 이해도가 엄청 높아진 것 같아. 너네도 혹여나 내 글을 본다면 1부터 천천히 혼자 식을 이해해보려고 해봐. 그럼 이해를 쉽게 할 거야.
AutoML에서의 강화학습은 Policy Gradient지만 난 그냥 10강까지는 다 볼라고. 이미 안다고 그냥 지나치기에는 기초를 엄청 확실히 해야 내가 연구를 원활하게 진행할 수 있다는 것을 꺠달았어. 기초 없이 논문만 본다고 아이디어가 그냥 나오지도 않고 논문을 제대로 이해를 할 수 있을 것 같진 않아. AUtoML을 하려고 하는 애들도 있을 거야. 그럼 강화학습과 RNN은 마스터를 하고 접근하기를 바래. 그러지 않으면 아이디어가 안나오지 않을까? 물론 나도 ENAS부터 NAS, NASNEt 그리고 그에 관련해서 활성화 함수를 찾거나 minima에 접근하는 최적화 함수?를 찾는 논문도 보고, 유전 알고리즘말고는 많이 봤지만, 역시 기초가 탄탄해야 된다는 것을 깨달았어. 이미 조금 알고있다고 해서 전부가 아닌 것을 시행착오를 통해 깨달았지. ENAS 코드도 돌려보기도 했고, ENAS를 활용한 아이디어도 몇개 생각은 해두었지만 내가 석사를 이제 막 시작하기 전에 이러지 않으면 나중에 되서 곤혹할 수도 있다고 생각을 했어. 난 강화학습 정리를 다 끝낸 후에 바로 딥러닝과 영상처리를 더 깊게 파고 들 생각이야. 기초가 완벽히 갖추고 난 뒤에 하려고 하면 당연히 늦을 수 도 있기 떄문에 최대한 빨리 끝내고 연구와 논문으로 공부를 할 생각인 거지. 그전까지는 어느 정도는 아는 데 완벽히 안다고 자부할 수는 없었어. 그래서 논문 보고 개념을 다 이해는 해도 완벽히 안다고 할 수 가 없었어. 만일 지금 늦었다고 생각한다면, 기초부터 꼼꼼히 하기에는 시간이 부족한 건 알아. 물론 바로 논문 보고 이리저리 적용하면서 실험할 수도 있고 아이디어를 그냥 낼 수도 있겠지만 기초 공부를 놓지말고 꼼꼼히 하길 바래. 물론 나는 이미 AutoML 관련 핵심적인 논문을 몇개 읽어둔 상태이고 딥러닝에 관련된 지식도 아예 없진 않아. 하지만 그래도 기초가 중요하다는 것을 말해주는 것이야.
NAS를 보면서 개념을 이해했다고 너네가 이해했다고 생각하진 않아. 개념이야 쉽지. 그냥 네트워크를 rnn으로 만들고 정확도를 강화학습의 보상을 삼아서 rnn 파라미터를 update해주고 그리고 다시 생성하게 하고 생성된 네트워크를 학습해 정확도를 얻는 반복.... 이거 누가 몰라.
rnn이 네트워크를 생성하는 과정은 나도 알아. 사람이 정해놓은 순서에 따라 필터 width, height, 개수 뭐 stride 등등을 정해놓고 이러면 되는 건 알아. 근데 중요한 것은 진짜 구체적으로 들어가야 수정하거나 나만의 연구로 돌릴 수 있다고 생각해.
자 기초를 열심히 다잡자. 연구를 시작하기 전에 기초만큼은 뗴놓고 시작해야 난 적성이 풀릴 거 같아.
// Lecture 5 : Model-Free Control
자 이번엔 Lecture 5: Model-Free Control을 말해.
저번 강의는 Model-Free prediction이였지? prediction은 어떠한 policy가 정해져있을 때 예측하는 거야. 이제 얼마가 나올지. 그러니까 prediction이라고 하는 거야. 그래서 value function을 학습하는 건데, 그걸 어떻게 구하냐? 직접 끝까지 해보고 실 값을 갖는 MC와 한번만 해보고 그 앞을 예측하는 TD가 있었어. TD에는 한번만 앞을 볼 수도 있고 더 앞을 볼 수도 있었어. 근데 2번만 본거랑 4번 본거랑 평균내는 방법이 있었는 데, 거기에 가중치를 더한 방법이 TD람다였지. 근데 여기서 TD의 장점이 사라지니까 backward가 나왔었지. 이걸 가능하게 하려면 한 스텝 가서 업데이트를 하되 뒤로 업데이트를 해줄 수 있도록 eligibility trace라는 것이 필요했엇어. 그랬더니 람다가 0일 때는 TD(0)과 같고 1일땐 MC와 같다는 말이 있었어. 맞지?
근데 여태까지는 정해진 policy를 따라갔을 때를 말한 거였어.
근데 이제는 policy를 우리가 조절 할 수있어. 선택할 수 있다는 거야. 더 향상시킬 수도 있고, 정해진 policy보다 더 좋은 policy를 선택할 수 있어야하잖아? 여태까지 넌 바보같은 policy를 따랐을 수도 있잖아. 너의 행동에 policy가 이상하면 어떻게 해. 최고의 policy를 찾아보자 이제.
그래서 이제 배울 거야. control. 환경에 대해 아무것도 모를때!
// Outline
자 뭐 이렇게 볼 건데, 여기서도 이상하게 MC와 TD가 똑같이 있네?
근데 on policy와 off policy는 뭐지?
on policy는 실제 policy와 환경에서 배우는 게 같을 때를 말한대. 무슨 말일까? 우선 나중에 말해줄게
// Model-Free Reinforcement Learning
지난 시간엔 prediction을 배웠고 이번엔 control 배운다는 거야.
알려지지 않은 환경(MDP)에서의 policy를 evaluate한다는 거였어. 즉 value funciton을 구한다는 거였지
이번에는 알려지지 않은 환경에서 policy를 최적화 시킨다는 거야. 즉 value function을 제일 좋게 변환한다고 햇지.
1~5강은 강화학습의 흐름을 배우는 거야. 아까도 말했다시피.
// Uses of Model-Free Control
이게 어디에 사용되는 지 보자.
MDP로 표현할 수 잇는 문제들은 저런 예제들이 있대.
MDP로 표현될 수 있는 문제들과, MDP 환경을 모르는 문제, MDP 를 알아도 너무 커서 못하는 것들을 Model-Free control에서 풀 수 있다고 하는 것 같대.
// On and Off-Policy Learning
On-policy learning와 off-policy learning을 보면 똑같은 것 같지만 달라.
하나는 a라는 policy가 있어. 그럼 a로부터 얻은 경험을 통해 a를 배우는 거고,
하나는 b라는 policy가 있는 데, a로부터 얻은 경험을 통해 b를 배우는 거야.
뭔가 헷갈리지?
직접 배우는 거와 어깨너머로 배우는 거라는 거야.
너가 직접 policy를 경험하면서 배울 수도 있고,
다른 policy를 통해 앗! 저렇게 하면 안되네? 난 하지 말아야지~ 할 수도 있는 거잖아?
자세한 것은 배우다 보면 알아
넘겨
// Generalised Policy Iteration ( REfresher)
일반적인 policy iteration을 설명해주고 잇어.
이거 예전에 3장에서 봤었지?
policy를 평가하고 향상시키는 것을 하면 최적으로 간다는 얘기였잖아.
뭐 3번 평가하고 1번 향상시킬 수도 잇엇고 뭐 이런거 기억나지?
향상은 greedy하게 했었어 그치?
기억나라고 다시 말해주는 거야. 넘겨
// Generalised Policy Iteration with Monte-Carlo Evaluation
이번에는 평가와 향상을 하긴 하는 데, MC로 평가를 할 수는 없을까?
우리는 기존에 policy iteration을 배울 때, 어떤 방법을 써서라도 평가만하면 되고 어떤 방법을 써서라도 향상을 해도 된다는 것을 배우기도 했었어.
MC가 뭐였지? Policy Evaluation하는 방법이였잖아. 언제? 환경을 모를때!!! 직접 해보고 그 policy를 평가하는 방법중 하나였어.
그럼 평가를 할때 MC를 적용하면 안되냐는 거지.
되!
직접 해보고 그 policy를 평가하면 되지.
근데 향상시키려고 greedy하게 할 수 있을 까?
그건 안돼.
왜냐면 환경을 알때는 어느 state로 가는 것이 더 좋은 지 알 수 있었는 데, 지금은 모르잖아?
너가 만약에 1234를 했어. 그럼 넌 value가 1234밖에 없어. 근데 5를 greedy로 갈 수 있을까? 없어. 왜냐? 가본적이 없잖아 5를.
그래서 안된대 greedy를 적용할 수가 없대
// Model-Free Policy Iteration Using Action-Value Function
여기서는 greedy policy를 적용하는 것을 가능하게 해주는 것을 말하고 있어.
state value function 즉 V(s)는 MDP 모델을 알아야지만 할 수 있대. 그래서 안되는 거래.
밑에 식은 3장에서 배운 식이야. 생각해봐
식을 한번 봐보자.
너가 지금 모델 즉 환경을 몰라.
왜냐면, V(s')을 모르잖아? 근데 arg max를 어떻게 알아. 모르지. 너가 예를 들어 state 1 이 0이야. 근데 state 2 는 4, state 3은 5, state4는 6이야. 각 action은 한번 하면 무조건 그 state로 간다고 치면 우선 pass'는 1이야.
보상은 다 똑같다고 해보자. 너는 state 2,3,4를 알아야 제일 좋은 것을 선택할 수 있잖아. 근데 지금 몰라 넌.
근데 state-value function 말고 action-value function으로 생각해보자.
지금 너가 가진 action이 뭐 있는 지는 알아. 그치? 그래서 이건 가능하다는 것을 말해주는 것이야. 이제 q함수를 쓰게 되는 거지.
// Generalised Policy Iteration with Action-Value function
자 이제 다시 보자.
아까는 모든 Value function을 가진 상태였었어. state value
근데 이제는 action value로 하자는 거야. 이제 MC 방법으로 policy 평가를 하긴 하는 데, 내가 가진 action을 해보는 식으로 하자 이거야. 이전까지는 직접 가보고 거기서 얻을 걸로 평가 즉 value function을 update했다면, 이제는 action에 따른 value function이기 때문에 내가 만일 action 3개가 있는데 1 action은 좋았어, 2 action은 안좋았고, 3은 아무 반응이 없어. 그러면 그 action에 대해 greedy 하게 움직이면 어떻게 되겠어? 좋은 1 action만 하도록 policy가 조정되겠지? 그렇게 하면 이제 가능해
근데 문제가 하나 있어. action 3개중에 한번 좋으면 그거에 바로 greedy하게 해서 그거만 선택하겠지?
예전에 1강에서 exploitation과 exploration의 trade off 가 있다고 했어.
내가 가진 것 중에서 제일 좋은 것을 선택하면 exploitation, 지금보다 더 좋은 것을 찾아 나서는 exploration이 있따고 햇지?
근데 greedy는 지금 뭐에 속하지? exploitation이야. 한번 하면 exploitation만 계쏙 반복하는 거잖아.
이렇게 되면 exploration을 안하겟지?
지금 그걸 말하는 거야
예제를 보자
// Example of Greedy Action Selection
이게 그 예제야. 문 2개가 있는데
왼쪽을 한번 여니까 0을 얻었어. 오른쪽은 돈이 나오네?
왼쪽은 한번 열었는 데 0이였으니까 오른쪽만 계속 하는 거야.
근데 과연 이게 제일 좋은 것일까?
왼쪽 한번 더 열었는 데 10이 나오면 어쩔려고?
이게 greedy의 문제라는 거야.
// e-Greedy Exploration
이건 앱실론 그리디 라고 해.
왜 나왔겠어. 당연히 저 문제를 해결하고 싶어서 나온거지.
exploration을 하게끔 하도록 하는 간단한 아이디어야.
모든 m개의 action들은 0의 확률을 가지지 않고 시도가 되.
자 다시 보자
1-e 확률로 greedy를 하게 하고
e의 확률로 랜덤으로 action을 하게 하재. 즉 exploration을 하게 하자는 거지.
확률이니까 0~1사이겠지?
현재 내가 action이 5개 있다고 해봐
그럼 어떠한 action을 할 확률은 각자 1/5니까 e는 1/5로 하자.
ㅠ(a|s)는 이 policy가 이 state에서 a를 할 확률이야.
근데 이거를 함수로 이제 만든거야.
e는 action을 할 확률이니까 1/5
만일 action중에 제일 좋은 것을 할 확률은 e/m + 1-e래.
1/5 * 1/5 + 1 - 1/5 해봐. 1에 가까운 값이 나와.
다른 경우 즉 otherwise에는 e/m이야.
즉 1/25가 나와.
이렇게 한다는 거야. 제일 좋은 것을 할 확률은 24/25이고, 탐험할 확률은 1/25라는 거지.
// e-Greedy policy Improvement
이건 이 입실론 그리디를 증명해주는 거야. 진짜로 더 좋아지나?
이건 증명을 직접 따라가면서 해봐. 위에가 좋아진 policy이고, 밑에가 현재 policy야.
// Monte-Carlo Policy Iteration
그래서...
이제 policy evaluation은 MC 방법을 쓰되, value function은 MDP가 아니니까 못쓰니 q함수로 쓰면 되고,
policy improvement는 그냥 greedy를 쓰면 탐험을 충분히 안하니까 그걸 보장할 수 있는 앱실론 그리디를 쓰면 된다는 거야.
이렇게 반복하면 최적의 poilcy를 만들 수 있대.
// Monte-Carlo Control
어라 이건 그림이 반쪽이네?
화살표가 끝까지 안가.
그리고 반만 가다가 멈추고 다시 와서 향상시키네?
우리는 3장에서 이런 것을 본 적이 잇엇어. modified policy iteration을 봐봐. 거기서 우리가 꼭 policy evaluation을 vㅠ까지 수렴해야하냐고 물어본적이 있었어. 그냥 k번만 평가하고 greedy하게 움직이면 안되냐고 했었어. 그때의 grid world에서는 policy evaluation을 3번했는데도 이미 grredy 하게 policy를 움직이니까 최적의 policy가 나왔었잖아. 기억나? 그래서 나온 질문이였어. 한번만 하고 greedy하게 움직이면 안되냐 이렇게 말을 했었어. 그리고 된다고 했었어. 잘 모르면 잘 봐봐. 지금 얘가 그 얘기야.
Monte-Carlo는 원래 episode가 끝나고 나서 평가를 할 수 있었잖아? 그리고 향상을 했잖아?
근데 항상 그렇듯이 MC는 항상 기다렸었어. episode가 끝날때 까지.
episode 할동안 기다리고 평가를 한 후에 향상을 한 후에 다시 기다리고....
이걸 좀 더 효율적으로 하겠다는 거야.
기다리는 게 싫다 이거지.
그래서 나온 아이디어가 한번만 평가하고 계속 greedy하자! 이거야. 그래서 딱 한번만 episode를 기다려서 평가를 한 후에 improve만 계속적으로 해. 물론 향상은 앱실론 greedy로 한다는 거 알지?
근데 왜 every라는 말이 붙었을 까? 그건 나도 의문이야.
every episode라고 해서 나도 솔직히 한참 봤어. 이게 진짜 한번만 evaluate하는 건가? every라고 적혀있는데?
그리고 그림에는 심지어 evaluate에 가지도 않아. 한번만 한다면 evaluate쪽으로 한번 갔다가 와야되는 거 아닌가? 흠... 이건 나중에 답변으로 남겨놓을 게. 의심적은 것은 Q와 qㅠ가 동일하다고 나와있기도 하고... 나중에 답변해줄게ㅣ
근데 우선 한번만 한다고 다른 강의나 문서에도 나와잇긴 해.
//GLIE
글리라고 읽어
방금 전에 Monte-Carlo Control을 하기 위해 필요한 조건이야.
이것의 정의는 Greedy in the Limit with Infinite Exploration
한정된 탐험에서의 제한된 greedy라고 해석 할 수 있는 데,
몬테 카를로 컨트롤을 만족 시키려면 2가지 조건이 필요하대.
1. 모든 state-action은 충분히 많이 탐험 되어야한다.
2 결국 policy는 greedy policy에 수렴하게 되어야한다.
라는 뜻인데.
이게 뭐냐면,
1번식을 보자.
k가 무한대이고, Nk(s,a)가 무한대이지?
한마디로 어떤 state에서 어떤 action을 하는 숫자(Number)가 무한대여야 한다는 거야. 우리가 greedy하더라도 충분히 탐험을 하도록 앱실론을 넣었지? 확률적으로 적긴해도 탐험을 계속 해보도록!. 근데 어떤 state에서 action을 하는 횟수가 많을 수록 탐험이 아무리 적은 확률이라도 많이 하겠지?
근데 계속 그렇게 하면 어차피 나중에는 뭐가 제일 좋은 지 더이상 탐험을 안해도 되잖아?
그렇기 때문에 나중에는 greedy policy로 수렴을 해야한다는 거야. 나중에 이제 너가 세계지도를 다 그렸어 직접 다 가봐서. 근데 더이상 그릴 필요가 없으면 이제 넌 최고의 policy만 따르면 되는 거니까.
그래서 k가 무한대로 갈 수록, 그니까 점점 많이 할수록 . 뭘 많이 하냐고? 많이 action을 할 수록 policy가 어떤 state에서 action을 고를 확률은 1이다. 즉 단 하나 밖에 없다는 거야. 그리고 그게 바로 제일 좋은 action이라는 것을 괄호안에 설명을 해주고 있어.
1은 state에서의 action인데 그 action은 어떤 state에서의 action들 A중에 제일 좋은 결과를 가져다 주는 action이다~ 라는 거야.
바로 밑에 예시가 있어
앱실론 greedy는 GLIE다. 만일!!! 앱실론이 계속적으로 0으로 작아진다면.... 이라는 뜻이야. 1/k니까 두번째에 탐험을 할 확률은 1/k^2 겠지. 점점 작아잖아.
// GLIE Monte-Carlo Control
자 우선 해석부터 들어간다.
1. 현재 policy가 있겠지? 그 policy에 따라 첫번째 episode를 sample해. 그니까 직접 해본다는 거야. 한번 게임을 끝날때까지 한거지.
2. episode에 있는 각 state St와 At에 대해, 저런 수식을 적용한대.
episode에 있는 각 state와 action이라는 말은 즉, 모든 state와 한 state안에 있는 모든 action을 말하는 게 아니야. 그냥 너가 의자에 앉았다가 일어났고 의료를 마셨어. 그럼 그거만 포함시키는거다? 의자에 앉았다가 action 1 일어난다. action 2 눕는다 action 3 던진다. 이렇게 있으면 저 세개에 다 적용하는 게 아니라 일어난다에만 적용시킨 다 이거야.
식을 보자
N(St,At) <- N(St,At) + 1
우선 State와 Action의 쌍이 1 늘었네. 그렇다는 얘기는 어떠한 state에서 어떤 action을 할 지 어떤 테이블이 필요하겠다 그치? 그래야 +1씩 높일 수 있으니까.
그리고!
Q(St,At) <- Q(St,At) + 1/ N(St,At) * (Gt - Q(St,At))
자 이 식을 보고 어려워 하지 말자.
우선 본인을 업데이트 하는 거야. 맞지?
근데 뭘 좀 더해주고 있어. 그게 뭐냐면, 우선 Gt-Q(S,A)부터 보자.
Gt는 우리가 그 state에서 끝까지 갔을 때의 보상이네? 그리고 Q함수는 어떤 state에서 이 action을 취하고 나서의 보상이네?
그걸 빼주네!
그럼 이게 비슷한 게 많았지? 에러율이라는 뜻이야. 기존에 가지고 있었던 action value 함수를 정답과 뺴줌으로서 그만큼의 차이를 남기는 거고 그만큼 update하겠다는 거야. 근데 무조건 다 update를 하냐? 그건 아니야. 1/ N(St,At)만큼 update를 한대. 즉 state에서 그 action을 많이 하면 할 수록 update를 안하겠다는거야.
즉 기존에 가지고 있었던 어떤 state에서 그 action value함수를 업데이트 해주는 거야. 이 action을 했을 때 얻는 value function이 좀 더 좋아지거나 나빠지겠지. 그러면 계속 나빠진다면 나중에 그걸 안뽑겠지.
3. policy를 이제 improve시킨데. 근데!!! 새로운 action value function를 기반으로 improve시킨대.
잉? 새로운 action value ? 그럼 방금 update를 한거와 관계없는 새로운 action value funciton으로 하겠다는 거야?
이 말이 아니라...
방금 update를 했잖아. 그 update한 것들에 대해서 greedy 하게 움직인다는거야.
그리고 반복된다는 말이 없으니 이게 끝이야.
아! 그럼 아까 내가 궁금했던 게 풀리는 거같애.
내가 생각할 때는 방금 sample할때 k번째 episode를 sample한 후에 그것들을 모두 update시켜준 후에, 마지막에 향상을 계속 시키는 데, 앱실론을 잘 봐보면 앱실론은 1/k로 설정해. 이제 느낌이 오나?
너가 만약에 딱 한번 샘플링 햇어. 샘플링이 뭔진 알지? 한번 해본다는 거야.
그럼 앱실론은 1이야 그치? 그럼 앱실론 greedy에서 앱실론이 1이면... 아까 앱실론 계산하는 ppt를 다시 봐봐. 모든 action이 동등한 확률을 가지고 있고 그거에 따라 greedy 하게 policy를 향상시키네.동등하다고는 말 못하겠따. 만약 aciton이 세개면 앱실론에 따라 앱실론 greedy는 앱실론이 1일 경우에, 제일 좋은 거 선택할 확률 1/3이고 나머지 2개를 선택할 확률 1/3이니까.
즉... 샘플링을 많이 했다? 그러면 앱실론이 엄청 작아지겠지? 즉 제일 좋은 것을 거의 선택할 거야. greedy하게 수렴이 되네? 왜 그렇지?
충분히 많이 샘플링을 했기 때문에 더이상은 탐험을 안해도 되기 때문이야. 식을 이해한다면 무슨 의미인지 알거야.
그러면 아까 내 의문이 풀렸다. 딱 한번만 episode를 평가하는 게 분명히 아닌 거같애. 그건 본인이 결정하는 거같아.
단 한번 하는 건 맞아. 근데 episode는 엄청 많을 수도 적을 수도 잇지.
그 대신 평가한 후에는 계속 greedy하게 움직이는 건 맞는 것 같아. 그 대신 몇번 sample했느냐에 따라 앱실론이 정해지는 거지. 적게했으면 탐험을 많이 하는 greedy가 될 거고, 많이 했으면 탐험을 적게하는 greedy가 될 거고 그치?
그럼 마지감 Theorem 을 보자.
GLIE Monte-Carlo control은 최적읜 action value function으로 수렴하게 된다~ 이거야. 제일 좋은 걸로 수렴한다 이거네.
// Back to the Blackjack Example
예시 보재. 블랙잭
넘겨
// Monte-Carlo Control in Blackjack
아 이렇게 되는 구나~
넘겨
// MC vs TD Control
어라 우린 MC도 적용햇었어. 어디에? evaluation에 .
왜? evaluation은 어떤 방법으로든 평가만 하면 된다고 했잖아. 그래서 MC를 썻어. MC는 왜 썻어. model free방법에서 직접 샘플링을 통해 얻어야 되기 때문이야. MDP가 아니니까 모든 걸 모르잖아.
그럼 어떤 방법이면 TD도 쓰면 안돼? 되 왜 안돼. 어떤 방법이든이라고 했는 데,
그래서 TD를 이제 쓸 거야
TD는 MC보다 몇 가지 장점을 더가지고 있대.
Lower variance - 낮은 variance ( 논문에서도 많이 나오니까 분산이라고 하지말고 variance라고 해)
이건 뭐라고 했어. bias와 variance가 있다고 했었지. MC는 진짜 실제값으로 하기 때문에 값이 편향되지 않아서 unbiased estimate라고 했었지. 근데 TD는 한번 가본것을 Gt로 치니까 biased 하다 그랬어. 그대신 variance가 낮다고 했지. 왜냐? 바로 그 값으로 update를 하니까 그런거라고 생각해. 아직도 variance 개념은 엄청 정확하게 들어오진 않은 것 같아. 그냥 느낌만 이렇다고 생각했어. 근데 MC는 마지막 값으로 모두 update를 시켜버리니까 실 값에 비해 분산도는 크다!
무튼 TD는 variance가 MC보단 적고
- Online
실시간으로 update할 수 있다고 했어. 왜냐? MC는 episode 끝날 때까지 기다려야하는 데, TD는 그냥 바로바로 할 수 있었잖아. 바로 앞을 episode 끝난 걸로 치니까. 근데 MC와 비슷할 때는 언제라고 했어? Foward TD , 그래서 나온 게? Backward TD 맞지? backward는 그래서 eligibility trace를 사용햇지? 거기에 람다를 적용햇고. 맞지?
그리고 Incomplete sequencse
이거는 뭐 episode를 완전하게 끝낸 게 아니다 라는 의미로 위에 말했어.
그래서 말하고자 하는 아이디어가. 이 Control에 MC대신 TD를 쓰자 이거야.
TD를 Q(S,A)로 적용해보재. 이건 무슨 소린가?
Q함수는 state에서 한번 action을 하고 거기서의 return 값이였지? 즉 거기서의 value function을 사용했어. 즉 TD는 한번 하고 얻는 거였잖아. 이걸 그거랑 동일하게 사용하자 이거야.
improvement는 그대로 앱실론 그리디를 쓰고,
매 step마다 update를 하자 이거야.
// Updating Action-Value Functions with Sarsa
action value를 update하기 위해 Sarsa라는 걸 쓴대.
살사라고 읽어.
State와 거기서의 Action 그리고 그 action으로 인한 다음 State와 그 State에서의 ACtion을 이용해서 update하자는 건데.
수식을 봐보자.
기존 Q함수를 update하고 있어.
근데 알파가 있네? 이건 얼만큼 update하느냐 이거야. 수식 많이 봐서 감이 오지? 예전에 무슨 1/N 으로 update 하고 그러기도 했었는 데 그치?
고정으로 알파를 두었네. 1/n으로 하면 시간 지날 수록 뭐 update가 안되서 즉 최신 정보가 update가 덜 되는 현상때문에 알파를 고정하는 거고 고정시키면 최신 정보를 더 update하겠다는 거잖아.
그럼 이제 안에를 보자
R+rQ(S',A') - Q(S,A)
이건 어디서 많이 봤는데? 에러네. TD 에러와 비슷해.
그럼 R+rQ(S',A')가 정답이고 Q(S,A)는 지금꺼네.
그니까 말로 풀어 쓰면.
현재꺼에 실제 정답과 현재를 빼서 그 차이를 알파만큼 더해줘서 update를 하겠다는 거네. Q(S',A')앞에 붙어 있는 건 discount야.
뭔지 대충 감은 오네.
한번 더 정확히 이해를 해보자. 다음
// On-Policy Control With Sarsa
이제는 episode를 k번 간 후에 evaluation을 하는 게 아니라, k번 step을 하고나서 evaluation을 하는 거 같아.
근데 evaluation을 하는 방법은 SarSa라는 거지.잉? TD 아니였어? TD 방법이야. 근데 Sarsa라고 하는 이유는 원래 TD에서는 V(S')- V(s)였었잖아. 맞나? 근데 이제 action에 대해서 해야하기 때문에 Q함수를 쓰는 데, 식만 조금 바꾸고 sarsa라고 한 거야.
별건 없어. 그냥 다 똑같은데, 이제 episode를 하는 게 아니라 바로 앞 step이라고만 생각하고 나머지 다 똑같은거야.
// Sarsa Algorithm for On-Policy Control
자 이제 sarsa 알고리즘을 적용하는 게 나와.
처음으로 알고리즘이 나왔네.
뭔가 이론을 공부하는 입장으로서 넘기고싶지만 컴퓨터과학과라면 다들 어쩔 수 없이 해야되.
자 보자.
우선 초기화를 한대.
Q함수 테이블이 있을 거야. State가 몇개 있고, 거기에 따른 action이 몇개 있겠지. 그 테이블을 우선 초기화 해야되. update해야되잖아. 근데 그냥 초기화 하는 게 아니라 임의로 초기화를 한대. 임의라고 하는 거 보니 사용자들이 정하는 거겠지. 이게 TD는 초기화가 중요하다고 했어. 모르면 4장 봐.
그리고 Q함수 테이블에서 terminal state는 0으로 설정하래. 왜? 이제 얻을 게 없잖아. 게임이 끝나는 데 보상이 어딨어. 0이지.
그리고 우리가 가진 State를 정의하고, State에 따른 action도 초기화를 해야되.
그리고 각 episode마다 반복을 한대 : 이건 진짜 episode를 한번 한다는 게 아니라 이게 하나의 과정이라는 뜻이야.
S를 초기화 한대. 잉? 보통 초기화 하면 0이라고 생각하겠지만 지금은 어떠한 State를 고르는 거야. State S가 여러개가 있을 거 아니야. 그 중에 하나를 고른다는 거지.
그리고 그 State에서 policy를 통해 A라는 action을 하나 뽑아. 근데 그 policy는 현재 Q 테이블이지. 왜냐면 Q 테이블에 state와 그에 따른 action들이 다 있을 거 아니야. 그리고 e.g.이 나오는 데, 이건 for example의 의미를 가지고, 예로 들어 앱실론 그리디 policy를 사용해서 고르라는 거야. 고르는 행위 자체를 말이야.
그리고 한 번 더 반복을 해. 이번에는 하나의 episode가 아닌 episode에서 하나의 step을 본다는 거야.
action을 한 것에 대한 보상과 다음 상태를 받아.
그리고 다음상태에서 또 한번의 action을 앱실론 그리디 같은 걸로 똑같이 골라.
그리고 원래의 Q함수를 sarsa 알고리즘을 적용해서 update를 해.
이거를 sample한 episode가 끝날때 까지 하고 break.
그리고 원래 반복문은 episode를 초기화 한 State가 terminal일때까지 반복해.
그리고 다시 episode 개수 만큼 반복하는 거지.
그리고 하나 더. 앱실론 그리디를 예로 들었다고 향상이라고 오해하지마. 언제까지나 sarsa는 뭐라고? evaluation이다...
evaluation만 한거야 지금.
// Convergence of Sarsa
이건 Sarsa가 진짜 수렴한다는 것을 증명해 주는거야.
두가지 조건 아래 수렴을 한다네.
1. police들이 내놓는 어떤 state에서 action을 할 확률들이 GLIE 해야된다는 거지.
즉 GLIE가 뭐였어. 충분히 많이 반복되어야하고 결국 greedy에 수렴해야한다는 거잖아.
그래야만 sarsa가 최적으로 수렴한다는 뜻이야. 즉 탐험 보장이라고 말할 수 있어
2. 알파는 Robbins-Monro 여야 한다.
한 스텝의 알파들을 늘어놓으면 Robbins-Monro 여야한대.
이게 뭐냐면 수식을 봐보자.
알파를 다 더하니까 무한대가 되지?
근데 알파 제곱은 무한대보다 작아 그치? 우선 이게 Robbins-Monro 라고 해.
알고리즘에서 알파가 무엇을 의미하는 지 알지?
최신 정보를 update해준다고 했어. 고정시킨다고 했잖아. old한 정보들은 점점 잊혀져가는 거지. 또한 얼만큼 update를 더 적용시킬 지 결정해주는 거라고도 했어.
근데 이 값을 다 더하면 무한대가 된대. 그건 음수는 안된다는 거네. -무한대로 안적혀놨으니까?
근데 이건 중요한게 아니야.
어찌도었든 무한대라고 하면 어떤 값이든 무한대가 되 그치?
근데 두번째 식을 보면 알파를 다 더한 무한대보다 알파 제곱하게 작으려면 일반 정수로는 안된다 이거지. 실수가 필요해. 그것도 0과 1사이. 맞지?
그걸 말하는 것 같아.
그렇게 알아두자.
// Windy Gridworld Eample
우리가 기존에 봤던 gridworld인데 바람이 분다네?
S에서 시작해서 G라는 Goal에 도달해야 된대.
움직일 수있는 것은 4방향과 왕의 움직임인 8방향이 있어. 왕이라고 하는 이유는 체스판에서 왕이 4방향 + 대각까지 다 움직일 수 있잖아.
그리고 grid 판 보면 밑에 숫자가 쓰여잇어. 이건 바람의 세기를 말해. 너가 그 칸에 가면 그 숫자만큼 위로 갈수밖에 없는거야.
보상은 -1이래. 그리고 discount는 없대.
// Sarsa on the Windy Gridworld
여기에 sarsa 알고리즘을 적용한 것을 보여주는 거야.
실제로 저렇게 가는 거라고 한 거야. 아마 8방향이겠지? 대각선으로도 움직이니까. 아니면 바람의 영향을 받아서 오른쪽으로 가면 오른쪽 + 위 이렇게 가는 4방향인지 헷갈리지만 무튼 보자.
보면 한 2000번까지는 아예 0이야. 왜그럴까?
한마디로 1번 G까지 도달하기 까지 2000번의 step이 걸렸다는 거야. 엄청 방황한거지. 근데 우연히 한번 도착하게 되면서 점점 가파르게 올라가 그치?
그러면서 나중에는 몇스텝 안가서 바로 정답을 알게 될거야. 저 곡선이 일정한 기울기를 갖게 될 때가 최적을 찾은 거야 그치?
이해 안되?
10step만에 너가 S에서 G로 가는 걸 찾았어. 그럼 10step마다 1episode가 올라갈 것 아냐. 그럼 일정하게 되는거 잖아.
이해 안되면 뭐.... 어쩔수 없구. 걍 그렇다고 알아둬
// n-Step Sarsa
아니. TD랑 비슷하게 나왔네?
똑같은 거야.
아니 한번만 꼭 봐야되? 두 step 보면 안되? 된다 이거야.
두 step이든 무한대든 봐도 되.
이건 너무 똑같아서 그냥 보면 알거야. 무한대면 아니, 끝까지 간다는 것은 MC랑 똑같다는 거고.
// Forward View Sarsa(ㅅ)
자 그럼 TD랑 똑같이 그럼 다 하고 평균내면 안되? 이게 람다 였찌?
MC와 똑같이 모든 것을 다 하고 평균을 내는 건데 그 대신 0일때는 그대로 , 1일때부터는 람다를 적용하고 2일때는 람다 ^2를 적용했엇지?
똑같은 거야. 넘겨
알아둬야 할 것은 그대신 TD에서도 이렇게 하면 MC와 같은 시간을 기다리기 떄문에 TD만의 장점이 사라진다고 했어.
// Backward View Sarsa(ㅅ)
그래서 나온 것이 eligibility를 둔 Backword View TD였어.
똑같은 거야.
여기서도 책임을 묻는 eligibility를 두는 거야.
근데 원래는 하나의 State마다 E를 뒀었잖아.
근데 이제는 action도 있잖아. state의 action마다 다 두는 거야. 어떤 state의 action1에 E, action2에 E, action3에 E를 둔거야. 즉 state에 E를 놓지 않고 state와 action 이렇게 쌍으로 두는 거지.
나머지 공식은 똑같애.
다 똑같애.
여기서 주의해야할 것은 뭐다?
람다의 개념은 Forward와 다르다!
그리고 t가 진행될수록 Eligibility는 t-1이 된다!
// Sarsa(ㅅ) algorithm
이거는 직접 이해하도록 해.
완전 똑같애 아까랑.
근데 반복문이 아까 2개였다면 이번엔 3개야
이 부분이 제일 중요해.
아까는 그 (s,a)만 update 했으면 됬어서 없었는 데, 이제는 한번 할때마다 뒤에 Eligibility를 다 update시켜줘야하잖아. 그래서 한 step할때마다 모든 칸을 update해줘야하는 거지.
근데!!! 사실 3개가 아니라 4개지. for all s E S , a E A(s) 는 2개잖아. for int i ,j 이렇게 되려나. 무튼. 그렇다고
// Sarsa(ㅅ) Gridworld Example
이제 예시를 들자.
이거 Backward야
agent가 경로를 저렇게 갔어.
그러면 one-step Sarsa에서는 딱 바로 전것만 update를 해준대.
그리고 람다가 0.9라고 가정한다면 여태까지 온 경로에 있는 애들은 다 update를 해주는 데 two step은 0.9 , three step은 0.9*0.9를 적용하니까 저렇게 화살표가 점점 작아지지? 0이 아니면 다 update를 해준다는 거야.
어라?
아까 알고리즘에서는 다음 걸로 update를 하고나서 모든칸에 대해서 한다며? 그리고 TD가 한 칸 갈때마다 예측치로 본인것을 업데이트 하는 거라며? 근데 왜 갑자기 끝까지 간다음에 TD방식으로 Update를 해? 그럼 그게 MC랑 뭐가 달라? Sarsa는 online이라며...
나도 좀 의아했는 데, 지금 생각해보니까 람다는 처음부터 끝까지를 다 고려한 것이였잖아. 그렇기 때문에 끝까지 가긴 하는 거지. 무슨 말인지 알려나? 지금 저거는 람다를 아예 끝까지로 한 거 같애. backword로 하는? terminal을 알아야 보상을 계산하기 때문에 처음에는 꼭 끝까지 가긴 가야되는 거같기도 하고 람다 자체가 원래 처음부터 끝까지 하는 것이기 때문에 저런 거 같애.
혹시라도 좀 이상하다면 다시 보던지 개념을 다잡자. 물어보든지.
여기서 드는 의문이 그럼 여태까지 모두 도착하는 순간부터 다 뒤로 다시 계산하는 건가? 생각이 들긴 했지만 지금 생각해보면 그건 아닌 거 같아. 원래 TD는 다음 state로 갔을 때 바로 얻은 값으로 그 전것을 update했었어. 이건 아닌 거 같고. 람다라서 그런 게 맞는 것 같아.
아니라면 진짜로 여태까지 모두 뒤로 계산한다는 거겠지.
// Off-Policy Learning
방금전까지 on-policy Learning이라고 했어.
on policy는 내가 직접 해보고 내가 배운다는 거였고,
off policy는 남이 하는 것을 보고 내가 배운다고 했어. 어깨너머로.
개념이 이렇다는 거야. 좀있따가 결국 내가 계산한느 거 아니야? 라고 할 텐데, 그게 아니라 뭐 물론 직접 하는 거라고 볼 수 도 있겟지. 근데 개념이 다른 사람이 하는 것을 보고 나를 update한다는 거야. 그럼 직접 하는 거랑 뭐가 달라? 라고 할 수 도 있어.
이걸 말해줄게 곧
우선 우리가 원하는 policy를 평가를 해야되.state value funciton이나 action value function을 계산을 하기 위해서 맞지? 우리는 어떤 state에서 이 policy가 어떤 action을 할 건지를 알아야되.
근데 그것을 u(a|s)라는 policy로 한다는 거야. u는 뮤라고 읽어. 뮤는 실제로 샘플링 즉 뮤라는 policy를 따라 실제로 돌아다니면서 값을 취하는 애야.
왜 이게 중요한 지는 밑에 나와있는 데,
우선 우리 인간들도 다른 사람을 관찰함으로써 배우는 게 있잖아? 개를 보고 배우는 게 있고. 이런 개념이야.
그래서 좀 더 정확히 말하자면 policy를 계속 적으로 생성해. 그리고 이 policy들을 보면서 즉 과거에 생성된 policy로부터 그 경험들을 재 사용하는 거야. 마치 노인도 있고 젊은 애도 있고 중년도 있듯이. 노인은 오래전에 생성된 policy 뭐 가치관이라고 하자. 그럼 그 노인의 가치관으로부터 배울 것이 있는 거야. 즉 재사용 re use한다고도 할 수 있지. onpolicy에서는 우리가 한번 평가한 다음에 버렸어. 근데 이젠 재사용하겠다는 거야. 버리지 않고. 다시 생각해봐. 우리는 on policy에서 MC와 TD를 배웠어 그치? 근데 MC적으로 한번 이동하고 그 다음에 계속 greedy하게 움직였었잖아? 만약 한번이 아니라 한 3번 이동했다고 쳐봐. 그럼 3개의 policy가 있었던 것이지. 근데 한번 update하고 다시 update했었잖아. 근데 이제는 본인 것을 update하는 게 아니라 또 하나 만들어서 update한 것을 또 넣겠다는 거야. 메모리적으로 생각해봐.
그래서 탐험하는 policy를 통해 최적의 policy를 배우는 것이고, 하나의 policy를 여러개의 policy로부터 학습? 또는 배우게 하는 거야.
이 Off Policy Learning에는 크게 두가지 종류가 있는 데, Important와 Q Learning이 있어.
Q Learning은 많이 들어봤찌?
// Importance Sampling
이거 엄청 중요해.
자 집중해서 보자
다른 분포로부터의 기대를 평가하다
자, 잘 생각하면서 들어
아까 봤듯이 우리는 policy를 여러개로부터 배울 수 있따고 했지?
그럼 한 policy마다 어떤 행동을 할지에 대한 확률 들이 있다는 거잖아?
그럼 그런 확률 분포들이 여러개 있겠지?
그 여러 개를 간단하게 참고할라면 어떻게 해야겠어?
만일 3개의 policy가 어떤 액션을 70퍼센트로 할라고 하고 1개의 policy만 25퍼센트로 하고 싶어해.
그럼 이 네개를 합친다면 70퍼센트에 가까운 확률이 나오겠지?
자 다시.
수식을 봐보자
우리가 f(x)에서 어떤 값이 나올 확률들의 기대값을 구하려고해.
자 E 어쩌구는 저런 의미야. 기대값이라고 했지? 그니까 시그마가 나오는 거야. 평균 낸다했잖아.
자 잘 보자.
우리는 X가 123야 그리고 f(x) = x+1 이라고 해보자. x를 넣으면 f(x)= 2,3,4지? 자 그럼 f(x)를 하면 보통 정도의 값이 나올까? 라고 기대하는 거야.
그렇기 떄문에 우선 X를 선택할 확률과, F(X) 값을 곱해야되. 아니 확률 구하는 데 왜 F(x)를 곱해?
내가 다시 말하지만 f 라는 함수에 x를 넣으면 보통적으로 얼마가 나오냐를 기대하는 거야. f(X)가 얼마나 나오는 지 궁금한거야.
그러니까 곱하는 거지. X는 몇의 확률로 선택이 되어서 그 때 2,3,4중 하나가 나오고 몇 의 확률로 3이 나오고 등등...
그렇기 때문에 P(X)F(X)를 하는 거야. 그럼 계산을 해보자. X에서 1은 20 2는 20 3은 60 확률이래. 0부터 1까지의 값일 테니 0.2,0.2,0.6이 나오겠지?
그럼 어떻게 계산하냐
P(1)F(1) + P(2)F(2) + P(3)F(3) 이렇게 하는 거야. 근데 기대값이니까 평균내야겠지? 뭐로? X의 개수만큼.
자 그럼 0.2 * 2 + 0.2*3 + 0.6*4 가 나온대. 0.4 + 0.6+2.4 = 3.4인데 3.4 / 3 은 1.1.... 이렇게 나오겟네 그치? 즉 F(X)는 1.1정도는 낭로 수 있다고 기대할 수 있는 거야.
그럼 다음 식을 보자.
Q(X)를 분모 분자 둘다 곱해줬어. 결국 똑같은 식이지?
근데 이게 뭐냐. 지금 보면 왜 Q를 밖으로 빼졋지? 라고 생각할 수 도 있는 데 그게 아니라
P(X) * f(x) == Q(X) * P(X)F(X)/Q(X)
왼쪽이 E x~p엿지? 오른쪽이 Ex~q로 생각한다면?
Ex~p[ f(x) ] 오른쪽은 Ex~q(P(X)F(X)/Q(X)) 인거야. 아직도 모르겠어? px에서 f(x)에 대해서 곱해줬었잖아.
F(x)를 P(X)F(X) / Q(X)로 생각해봐. 결국 같은 식인거야. 다만. Q라는 확률 분포에서 구하는 거지.
자 그니까 P라는 확률을 Q라는 공간에서의 확률을 구한거야.
이건 스스로 잘 이해해봐.
다른 확률에서의 분포를 구하고 싶으면 곱하면 된다라고 표현하기도 한다네.
그리고 이 slide의 제목을 생각해봐. importance sampling이야. sampling의 중요도래. 감만 잡아봐.
// Importance Sampling for Off-Policy Monte-Carlo
Off Policy MC방법에 이 Importance Sampling을 적용한다네
무슨 말인지 몰라도 한번 보자.
u라는 Policy로부터 생성된 returnd을 통해 ㅠ를 평가할거래. 평가하는 방법중에 MC와 TD가 있었다? 직접 끝까지하는 방법이군?
그냥 한글말로 u는 뮤, ㅠ는 파이라고 할게.
두 policy사이의 유사성에 따라 Gt에 가중치를 부여한대. 모든 episode에 걸쳐서 방금한 importance sampling을 곱해준다네.
유사성은 지금 ㅠ/u로 하고 있어.
자 봐봐. 내가 2 인데 만일 너가 나랑 완전 똑같지 그럼 2야. 근데 내가 2인데 너가 10이야. 그럼 8만큼 떨어져있는거지? 지금 봐봐 확률이니까 음수가 나올 수는 없어. 내가 state s1에서 action a1을 선택할 확률이 0.2인데 너는 0.8이야. 그럼 몇이 나와. 0.2/0.8 1/4니까 0.25지? 이런식으로 한번 episode할 동안 너가 한 행동들에 대해서 그 확률들이 나와 비슷한지 보는 거야. 같을 수록 1일테고 다를 수록 조금씩 낮아지겠지? 많이 다르면 확 낮아지고. 만약 총 곱해서 결국 너와 내가 비슷한 정도가 딱 반이래. 그럼 그거를 뮤의 return에 적용하는 거야. 딱 반만 나와 비슷한 결과라고.
그리고 그값을 가지고 본인 State에서의 value function을 update해주는 거야. 자 넌 100인데 나와 반만 비슷해. 그럼 흠~ 딱 반만 참고할 만 하네~ 라는 생각을 가지고 반만 적용하는 거야.
그럼 그 반만큼 update를 하는 거지. 그 방향으로. 좀 이해가 가? 아까 말한 Importance sampling은 여러개의 policy를 돌리고 그거를 나한테 적용할라면, 나와 비슷하면 내가 하는 경험이나 마찬가지잖아. 근데 나는 아니지만 너랑 내가 생각하는 가치관이 같은데 너가 경험을 했다? 그럼 많이 참고하겠소. 근데 가치관이 완전 반대야. 근데 너가 이게 좋대. 그럼 나는 조금만 참고하는 거야. 완전히 믿지는 않고. 한마디로 sampling하는 것에 중요도를 둔다 이거지.
밑에 update하는 식은 MC에서의 Value function에서도 많이 봤어 그치? 그대로 이해하면 되.
근데 여기서 뮤가 0이고 파이가 0이 아니면 사용할수 없대.
당연하겠지. 왜냐면 하나라도 0이면 0이 되니까?
근데 대신에 이 importance sampling은 variance를 극도로 증가시킨대. 원래 MC는 variance가 안그래도 컸는 데, 엄청 증가시킨대.
이유는 음... 정확한 것은 나중에 답변을 해줄게.
우선 내가 생각하는 것은. 안그래도 MC가 variance가 큰 이유는 예전에 한번 설명을 한 적이 있엇어. 하나의 policy만 해도 큰대 지금 여러개의 poilcy를 적용하려고 하니 엄청 커진다고 생각해.
무튼... 상상속의 알고리즘이래. variance가 극도로 커서 사용할 수도 없다고 하네.
그래서 우리에게 남은 것이 있지. TD가 있짢아.
** 방금 다시 깨달은 것인데. 이게 엄청 튈수가 있대. 값이.
왜냐면 분모에 계속 곱해지는 것이기 떄문에 엄청 커지거나 엄청 작아질 수도 있다네.
더 정확하게 이해하면 다시 설명을 해볼게
// Importance Sampling for Off-Policy TD
똑같애.
MC는 원래 직접 하는 return이였지만 TD는 TDtarget 즉 한번을 보지.그리고 그걸 return으로 취급을 하지.
그리고 밑에 식은 어라 익숙하지 않네 라고 할 수 있겠지만 익숙한거야
단 한번 했으니까 그 action에 대해서 유사도를 곱해줘야되는 것일 뿐이야. 다 똑같애.
이렇게 하면 Monte-Carlo보다 훨씬 variance가 낮아진대.
이렇게 하면 policy들 여러개가 딱 하나의 step만 비슷하면 되는 거지.
// Q-Learning
드디어 나오네. 아까 Off Policy를 하는 방법에 2가지가 있다고 했어. Q learning과 importance sampling라고 했었지
importance도 뭔지 설명하고 off policy에 적용했엇지? 여기서도 똑같은 방식으로 할 거야
이건 진짜 유명한 거야.
잘봐봐.
우리는 지금까지 off policy에서 state value function만 다뤘었잖아?
이제 action value function도 학습하는 방법을 배워보자.
우선 우리가 이걸 하는 이유는 importance sampling은 variance가 극도로 커서 할 수 없기 떄문이야. 상상속 알고리즘이니 다른 방법을 알아봐야지. 그리고 Off Policy에서는 Q-Learning이 제일 유명한 것으로 알고 있어.
무튼 우리는 이제 어떠한 다음 state는 몰라도 내가 할 수 있는 action은 알고 있어.
어라 뭔가 sarsa랑 비슷한 거 아니야? 아까도 sarsa 했었잖아!. 맞아. 근데 그건 onpolicy 였었잖아 그치? 이번엔 Off Policy라는 점이야.
이제는 off policy야. 즉 내가 직접 하면서 최적화 하는 게 아니라 남을 통해서 최적화를 하는 거야. 그것도 action value function을 말이야.
이 큐러닝을 쓰게 되면 우리는 더이상 importance sampling을 안해도 되.
importance sampling에서는 뮤라는 policy가 간 것을 유사도를 측정해서 계산했고, TD는 뮤가 딱 한번 앞에 간 것과의 유사도를 측정했었어.
이번에는 좀 달라. 위처럼 하면 variance가 너무 높아지기 떄문에 상상속에서만 쓸 수 있었고, 못했었어.
우리는 이번에 value function이 아닌 action value function으로 생각할거야.
근데 애초에 우리가 왜 Onpolicy에서도 action value를 썼었지? 애초에 평가하고 향상할때에도 value function만 쓰기에는 evaluate까지는 가능했으나 greedy를 할 수가 없었어. 다음 state에 대한 모든 정보가 없잖아. 가본 것만 있고. 그래서 q로 했었어.
직접 해보는 걸로 value function을 쓸 수 있었어. state value 말이야.
근데 이번에는 action value를 생각해보자 이거야. state value function을 할 수 있으면 action value function도 할 수 있는 방법이 있어야겠지?
이제 Importance sampling이 필요가 없어.
우선 간단히 말해볼게
ppt에 있는 내용은 대충
다음액션은 내가 아닌 다른 policy를 통해서 고르게 되.
근데 우리는 그 중에 하나를 골라서 우리가 직접 하는 거야.
간단하지? 그냥 action을 다른 policy들을 통해서 그 중 하나를 골라서 직접 하자 이거야.
다시 말해주자면 예전에는 우리가 직접 커피를 골랐다면, 이제는 어떤 사람 시켜서 몇개 골라오라고 한 뒤에 그 중에 하나를 선택하는 거야.
그리고 그걸 update하는 거지.
잘 이해가 안될수도 있어. 우선 수식은 Sarsa에서 별로 다르지 않아. 우선 개념부터 저렇게 잡고 가보자
// Off-Policy Control with Q-Learning
우리는 이제 target policy인 파이는 greedy하게 할거야. 왜냐면 어떤 사람이 골라온 것 중에 제일 좋은 것만 고르면 되는 거잖아.
그래서 수식을 보면
ㅠ(St+1) 즉, 다음 State에서 내가 선택할 action에 대한 policy는 argmax Q(St+1,a') 이다.
이게 뭐냐면 뮤라는 policy에서 했었던 action들중 제일 좋은 것이다~
당연하지. 제일 좋은 것을 선택해야하니까
그리고 뮤라는 policy는 앱실론 그리디하게 하자 이거야. 그냥 greedy로 하게 되면 항상 같은 거만 나오겠지? 그러니까 exploration도 할 수 있게 해서 여러가지 경우의 수를 갈 수 잇께 하는 거지.
그리고 그 밑에 잇는 Q-Learning의 target 즉 정답을 말하는 거야.
이거를 간단하게 해보재.
Rt+1 + rQ(St+1,A')
여기에 이제 action은 armax한 action이였잖아? 그래서 방금 위에 수식을 저렇게 집어 넣는 거야.
그래서 마지막 식 보면 다 똑같은데, A'가 a'가 됬어.
그냥 action을 뮤 중에서 제일 좋은 것으로 고른다 이거야.
// Q-Learning Control Algorithm
이제 개념은 좀 잘 이해가 될 거야.
저 수식은 위에서 봤던 target을 아까 위에 업데이트하는 수식에 집어 넣은 것일 뿐이야.
그림을 보면 좀 더 쉽게 이해가 가지?
그럼 이렇게 하면 최적을 찾아 갈 수 있다고 밝혀졌어.
자 강의는 여기까지인데 나머지 내용들은 내가 따로 이제 올려줄게. 1부터 5강까지의 뒷 내용들은 내가 안배웠다고 말 안했었잖아. 그걸 이제 다음에 6장 배우기 전에 올려줄게.
근데 우선 여기서 Q-Learning이 왜 더 좋은 지 예시를 ;들어줄게
// Clif'f Waliking Example
이걸 봐봐.
자 이게 뭔지 모를거야.
지금 The Cliff라는 곳에 가면 Start로 돌아오면서 보상을 -100을 받아.
이렇게 될 경우에. optimal path는 바로 일직선으로 가는 거지 G로?
근데 safe path는 좀 더 우회하면서 가고 있어. 분명 최적의 경로는 The CLiff 바로 위야. 그치?
근데 Sarsa를 쓰게 될 경우에.
optimal path를 가다가 중간에 오른쪽으로 빠질 수 도 있찌? 그러면 어떻게 되겠어. 안좋은 값으로 채워지겠지? 몇번 더 빠질 수록 그 쪽은 계속 안 좋은 값들을 넣게 될 거야. 그럼 이제 그 쪽으로는 안가게되겠지.
근데 Q-Leanrnig을 할 경우에, optimal path를 가는 데, 왼쪽, 오른쪽, 위 ,아래를 다 탐사를 보내는 거야 다른사람을. 근데 밑은 별로 안 좋았지만 오른쪽은 괜찮대. sarsa에서는 밑으로 그냥 빠지면 바로 안좋다고 값을 update했었는 데, 이제는 밑으로 갔던 놈도 있지만 오른쪽으로 간 놈은 좋았다고 하니까 그 값을 안좋게 update를 안하는 거야. 이제 좀 이해가 되지?
그래서 밑을 보면 sarsa와 q-learning이 처음 episode를 할 때는 우선 보상이 다 -100이였다가 점점 줄어들지?
한칸이 -1 reward인 것을 생각하면 50번만에 도착하는 거와 25번만에 도착하는 sarsa가 보이지? 근데 내가 생각할때는 반대로 되있는 거 같아. Q-Learning과 sarsa를 바꿔서 써놓은것같아
Q-Learing은 중요하니까 꼭 이해를 하고 넘어가.
Sarsa가 그렇다고 아예 안좋은 건 아니야. 다 상황마다 쓰이는 용도가 다른 거지. 근데 Q가 대체적으로 좋아서 거의 강화학습 기본 알고리즘으로 자리잡혔고, 이걸로 대부분 성능이 좋아서 이걸 많이 쓰인다고 해.
// 질문
variance가 왜 엄청 커질까.