강화학습 3번째 강의야
// Lecture 3: Planning by Dynamic Programming
우리는 Lecture 2에서 MDP를 배웠지. 그리고 내가 강화학습 문제는 Planning과 reinforcement learning 문제로 나눌 수 있다고 했어. 그 두 차이는 환경을 아냐 모르냐라고 했지. 지금 Planning은 환경을 아는 상태. 즉 MDP일 떄를 말하고 환경에 대한 모델이 있을 때 최적의 policy를 찾는 방법이야
// Outline
개요야
6번은 강의에 설명 안해서 안배울 것이고 234가 핵심.
저번 강의에서는 벨만 수식이 핵심이였어.
여태까지는 벨만 수식으로 표현한 것을 행렬로 만들고 어떻게 넘겨서 한방으로 풀 수가 있다고 했었지. 근데 이렇게 할 시 문제가 너무 커서 조그만한 문제가 아니면 풀 수 없다고 했었어. 더군다나 bellman expectation equation은 그렇게 풀 순 있었어도 커서 반복적인 것이 필요했다면 bellman optimal equation은 최적을 구하는 것이라 최적은 *로 나타냈었고, 본인이 가진 것중 제일 좋은 것을 선택하다보니 max가 붙어서 행렬로 나타낼 수도 없다고 햇지. 왜냐면 비선형적이니까. 이번에 그런 것들을 iterative하게 해서 최적을 찾아가는 방법 2개를 배울 건데 Policy iteration과 value iteration이 있어. 이 두개의 차이점은 iterative한 방법으로 최적의 Policy를 찾아간다는 거야. 그 대신 policy 기반 방법이 있고, value 기반 방법이 있는 것이지. 이렇게 하기 위해서는 지금 찾은 policy가 최적인지 아닌 지 평가를 할 수 있어야겠지? 그걸 Policy Evaluation이라고 하는 거야.
어떤 찾은? 아님 정해진 Policy를 따라갔을 때 value function이 어떻게 될 지 찾는 다는 거야.
// What is Dynamic programming
근데 왜 DP를 쓸까?
DP란 무엇이지?
DP는 복잡한 문제를 푸는 방법중 하나 인데, 큰 문제를 작은 문제들로 쪼개서 푸는 거야. 그리고 그 작은 문제들을 하나씩 풀고 그것들을 합쳐서 결국에는 큰 문제를 푸는 방법인데.
모르면 찾아보시길...
여기서 DP를 쓰는 이유는, 강화학습이란 풀어야한 큰 문제에 속하고 여기에는 모델이 있는 지 , 모델이 없는 지에 따른..... 즉 환경에 대한 정보가 없을 때( reinforce learning)와 환경에 대한 정보가 있을 때 ( Planning)ㅣㅇ란 문제들이 있고, 환경에 대한 모델이 있을 때 쓰이는 방법론이 Planning이고 이 Planning에 DP를 쓰겠다는 거야.
// Requirements for Dynamic Programming
DP는 일반적으로 두가지 조건이 필요해.
Optimal substructure 와 Overlapping subproblems인데,
Optimal substructure : 전체 문제가 작은 문제로 나뉠 수 있어야 한다.
Overlapping sub problems : 작은 문제를 풀었던 것이 반복될 수 잇고, 어딘가 저장되었다가 다시 사용될 수 도 있다.
이 두가지 조건을 MDP가 딱 만족한다고 해.
왜냐고?
벨만 수식을 보면 반복적인 수식임을 알 수 있잖아.
그리고 value function을 구할 때 저장하고 재사용한다
뭐 이런 얘기들이 있어
// Planning by Dynamic Programming
DP는 MDP의 모든 것을 알고있다고 가정하고 MDP에서 planning할 떄 쓰이지.
그래서 여기에는 두 가지가 있어.
prediction과 control이야. DP로 prediction을 풀 때와 DP로 control을 풀 때가 있다는 것이야. 그냥 문제의 종류? 라고 보면되.
prediction은 value function을 찾는 다고 보면 되고,
control은 policy를 찾는 것이라고 예전에도 설명을 한 적이 있지.
근데 잘 이해가 안갈거야.
잘 보면 MDP에서 policy가 정해져 있어. 그럼 그 policy를 따라갔을 때 얻을 수 있는 value function이 있을 거 아니야? 그걸 구한다는 거야. 근데 가만 보면 2장에서 MDP에서의 state-value function과 비슷하지 않아? 이것도 똑같이 state s에서 정해진 policy를 따라갔을 때 얻을 수 있는 value function인데... 아마 비슷할 거라고 예상해.
control은 Policy가 정해져 잇찌 않아. MDP만 주어지면 거기안에서의 최고 좋은 policy를 찾는 것이고, 또는 제일 좋은 value function을 찾을 수 있다는 것이야. *가 붙어있으니 최적이지?
뭐 DP로 prediction을 풀면 value function, control을 풀면 최적의 policy나 value function이라고 생각하자.
// Other Applications of Dynamic Programming
뭐 DP로 많은 것을 풀 수 있대.
읽어보던지
넘겨
// Iterative Policy Evaluation
이제 드디어 policy를 평가할 때가 왔어.
이 policy를 따라갔을 때 return을 얼마나 받냐? 가 즉 이 policy를 평가하는 것이고, return을 얼마나 받을 수 있을 까는 역시 episode를 평균내겠지. 그래서 value functin을 얻겠다는 것이야. value function은 prediction이였지?
자
문제는 주어진 policy를 평가해보자
여기서 Solution이라고 푸는 방법을 말해줘.
Solution : bellman expectation backup의 반복으로 풀 수 잇대.
여기서 backup은 잠깐 저장한다의 의미를 가져. 이건 좀 있다가 다시 말해줄게, 그리고 벨만 기대 수식을 반복적으로 수행한다는 의미야.
v1-> v2 ...vㅠ가 있지?
이걸 하는 방법은 맨 처음에 랜덤으로 초기화를 한 대, 그리고 그것을 계속적으로 반복해서 v2를 구하고 v3를 구하면 결론적으로 우리가 지금 구하고자 하는 정해진 policy에 수렴한다는 것이야.
그니까 v1이 어떻게 보면 맨 처음 random policy를 만든 것을 평가한 것이지. v2는 update한 v1을 평가하는 것이고, vㅠ는 최적의 policy를 말하는 것 같아.
사실 여기서 좀 헷갈릴 수 있는 게, 주어진 policy 인 (파이)를 평가하는 것인데, 랜덤 폴리시를 적용한다는 게 살짝 이해가 안가. 그렇게 해서 최종적으로 파이 value function을 얻는다니... 우리는 policy pie를 구하려고 하는 것인데, 왜 v1 v2 v3 이런 게 있고 이런 것들을 update하면 나중에 poilcy ㅠ를 어떻게 구한다는 것이지? ㅇㅅㅇ;;;;
자 다시 정리해보자.
우리는 기존에 bellman 기대 수식을 배웠지?
그리고 행렬로 나타냈잖아?
그리고 한방식으로 나타냈었지?
원래는 한방으로 푸는 식이 아니라 그냥 행렬로 표현 가능 한 것이였고, 여기서 벨만 수식을 계속 적용해보면서 푸는 거였는 데, 한방에 풀 수 있는 방법이 있었던 것이지. 근데 분명 한방에 푸는 것은 엄청난 계산을 요구한다고 했었어. 그렇기 때문에 반복해서 푼다고 했었지. 이제 감이와?
이건 policy ㅠ를 구하는 게 맞아. 그리고 그 과정에 우린 여태까지 한방에 풀어서 이게 어떻게 가능하지?라고 하겠지만 원래 이렇게 푸는 게 맞다는 거지. 우리 여태까지 한방에 푼거야. 근데 한방에 풀지 않고 DP적인 방법으로 조금씩 나누어서 풀자 이거지.
그렇게 반복하다 보면 우리가 한방에 풀었던 그 policy를 우리도 풀 수 있다는 거야!
그럼 여기서 어떻게 update를 할까?
여기서는 synchronous backups라고 하는 데, 간단히 말하면 모든 state에 대해 한번 update 하는 것을 synchronous backup이라고 해.
full swip이라고도 해. 모든 state를 다 방문하는 것을.
모~든 state를 다 방문하는 것을 synchronous라고 해
그럼 asynchronous는 나중에 말해줄게.
그래서 방법을 보면,
1. 매번 한 반복문 마다
2. 모든 state를 돌면서
3. vk(s')으로 부터 vk+1(s)를 update한다.~
여기 부분이 이해안갈거야. 단순하게 말하면. 너가 (0,0) state가 있어. 그럼 갈 수 있는 state들이 잇겠지? 그 state들을 보고 지금 너의 (0,0) state를 update 한다는ㄱ ㅓㅅ이야. 어려워 보이지만 단순해. 그냥 주변을 보고 본인을 update한다는 것이지. 이게 bellman expectation equation이 적용되는 때야.
여기서 만일 행렬이라고 하면 한개만 필요할까? 아니지 update한 것들을 기록하는 행렬이 따로 있어야 하고, 현재 행렬도 있어야하니까 2개가 필요해. 이해 되지? 그러니까 backup이라는 용어를 쓰는 거지. 다른 것들도 현재 k로 update해야할 거 아니야. update 된거를 그대로 가져다가 쓰는 경우가 없어야한다 이 말이야.
뭐 이게 증명되는 것은 나중에 말해준대.
// Iterative Policy Evaluation(2)
이 그림은 어딘가 익숙 할 거야. 우리가 Bellman Expectation에서 배웠던 거지? state action value function 식이잖아. 그떄 막 action value function을 어쩌구 넘기고 그래서 저런 수식으로 유도했었잖아. 저렇게 하면 v로만 표현할 수 있었다고 했었잖아.
저 식을 보면 vk+1 = Rㅠ + rPㅠvk 로 행렬로도 표현하네. 이것도 전에 그대로 있었어.
근데 뭐라고? 예전엔 저걸 어떻게 넘겼더니 한방에 풀 수 있었잖아. 근데 지금은 아니잖아. 그래서 넘기질 못하는 거야. 무튼 저 식으로 유도하겠다는 거야. update하겠다는 거지.
아니 근데 처음에 랜덤값을 하면 그게 진짜 가능하냐고?
신기하게 가능해.
그리고 다른 것은 다 엉망이더라도 보상은 정확하잖아?
그래서 수렴할때까지 계속하면 결국 구할 수 있대 ㅎ
// Evaluating a Random Policy in the Small Gridworld
자 문제를 통해서 좀 더 이해를 해보자.
하나하나 천천히 말해줄게.
우린 우선 action은 4가지야. 상 하 좌 우. 그리고 우리의 policy는 각 상하좌우를 갈 확률을 일정하게 0.25로 하는 policy를 따라. policy는 agent의 행동을 결정해주는 애야. 알지? 그냥 균일하게 랜덤하게 하겟대. 0.25확류로.
상태는 1부터 14까지 있고,
discount는 1이네.
Terminal state 즉 종료 state는 1개래. 근데 보여지기로는 2개로 보여졌대.
보상은 terminal state에 도달하지 않는 이상 -1이래. 예전에 우리 maze가 생각나네.
// Iterative Policy Evaluation in Small Grid world
왼쪽은 random policy에 관한 value function들을 말해줘. k에 따른 value function이지.
오른쪽은 Vk에 의존한 Greedy policy를 보여주는 거야.
여기서 잡상식으로 w.r.t는 with respect to 라는 뜻이야.
여기서 오른쪽은 보지 말고 왼쪽부터 일단 보자.
우리는 우선 policy는 주어졌지? random policy야. 상하좌우 모두 똑같은 확률인 0.25
자 그럼 한번 보자.
맨 처음에는 아무 값으로나 초기화 한다고 했지?
여기서는 0으로 초기화를 했어.
k=0에서 모든 값은 그래서 0으로 된 거야.
k=1부터는 bellman expectation equation을 적용해서 update를 한거야. 여기서는 terminal이 0인 이유는. 앞서 말했다시피 terminal에 도착하기 전까지 보상이 -1이야. terminal이니까 더 이상 안가도 되고 보상도 없는 거지. 0이야.
자 그럼 계산을 해보자. k=1일때 우리는 계산을해서 k=2를 구해보자는거야.
방금 전 bellman expectation equation을 사용해서 하는 거야.
저 칸들이 0부터 시작한다고 쳤을 때 우리는 1,1을 계산해보자.
벨만 기대식을 보면서 따라가보자.
우선 액션은 4개가 있어. 상하 좌우
다 0.25야.
자 그럼 계산해보자. 벨만 수식 보면서 계산해보는거야.
우선 ㅠ(a/s) 는 0.25지? 이걸 네번 해야되 a E A 니까 각 action 마다 해야되.
그리고 Ras는 -1이야.
그리고 r은 1이라고 했어. pass'는 1이지? 왜냐면 한 액션을 하면 바로 다른 데로 가잖아. 그림 보면 저거는 액션에 따라서 어느 state에 갈지 또 갈라져 잇찌? 하지만 여기선 한번 action하번 그 쪽 state로 가니까 1인거야.
그리고 그때의 vk(s')은 뭐 지금 다 -1이잖아?
그럼 이제 다 구했지?
왼쪽 : 0.25 * ( -1 + 1*1*-1) = 0.25 * -2 = -0.5야
위 , 아래, 오른쪽은 다 똑같지? 왜라는 의문이 들면 다 계산해봐.
그럼 -0.5를 다 더하면 -2.0가 나오지?
이렇게 계산한거야.
복잡한 건 너네가 직접 해봐
// Iterative Policy Evalutation in Small Gridworld
이제 보면 k=3, 10 그리고 무한대까지 갔어.
무한대는 곧 수렴을 했다는 의미야. 그니까 policy를 평가했더니 결국 저길로 수렴했다는 것이지
random policy에 대한 value function으로 수렴했다는 거야.
혹시 이거 오른쪽 policy에 관한 거 아니야? 라고 묻는 다면 직접 해봐. 아니야. 내가 직접 계산해봄으로써 아니라는 것을 확인했음.
그래서 결국 k=무한대일때 ( 수렴할때) 저게 random policy에 대한 value function이야.
이제 여기서 오른쪽 greedy들을 다시 한번 봐보자.
greedy policy를 보면 vk에 전적으로 greepy하게 만든거야. 그니까
k=0일때 말이야. 맨 처음에는 random policy를 그대로 따르고 있어. 왜냐면 저기선 value function이 모두 0이라서 greedy하게 할 일이 없거든.
근데 k=1일때 그냥 단순히 값이 작은 쪽으로 greedy하게 policy를 바꾸었어. 왼쪽 value function은 아직도 k=0일때의 greedy policy에서 볼 수있는 random policy를 계속 따르고 있는 거야. 이해됬지?
이런 식으로 값이 작은 쪽으로만 policy를 계속 바꾸다 보니까 k=3일떄 이미 최적의 policy를 도달했어.
아직 random policy를 다 평가하지도 않았는 데 ? greedy하게 계속 움직였더니 최적에 도달했네? 심지어 올바른 value도 아니였는데 말이야.
여기서 우리가 알아야할 것은 바보같은 (random 같은) policy를 평가만 했는 데도, 거기에 대해서 greedy하게 움직이면 최적의 policy를 차을 수 있다는 거야.
// How to Improve a Policy
그래서 여기서는
Policy를 평가한 후에, 그 Policy에 대하서 greedy하게 움직이면 최적의 policy를 구할 수 있다고 나와잇어.
방금 small gridworld는 한 k가 3번일때 바로 찾았지만 실제로는 훨씬 더 많은 반복을 구해야한대.
// Policy Iteration
이제 나온다. Policy Iteration이야.
아까 말했듯이 평가와 향상을 반복한다는 거야.
평가 evaluate / 향상 improvment를 말해.
// Jack's Car Rental
넘겨
내가 자세히 안봄
// Policy Iteration in Jack's Car Rental
예시인데 난 안봤어
넘겨
// Policy Improvement
이거는 진짜 improve 된 policy가 더 낫다는 증명을 하는 거야.
우선 해석부터 해보자.
--Consider a deterministic policy a= ㅠ(s)
state를 넣으면 a라는 action을 출력해주는 policy가 있다고 해보자
( 예전에 우리 policy의 종류에는 policy에 state넣으면 그냥 action을 바로 출력해주는 것이 있었고, action을 할 확률을 뱉어주는 애가 있었다고 했었지? 그게 stochastic이고 이거는 deterministic이야.)
--we can improve the policy by greedily
우리는 greedy하게 하여 policy를 향상시킬 수 있다
( 저 q함수는 state action value function이라고 했어. 식을 잘 보면 a E A는 할 수 있는 모든 action 중에서 가장 좋은 q 함수를 주는 거야. 아니? 가장 큰 값을 넣는 거 아니야? 라고 생각하겠지만 max는 가장 큰 값을 주는 거고, arg max는 가장 큰 값을 주는 input을 주는 것이라고 알아둬)
즉 이얘기는 q가 제일 좋은 것을 고르는 것을 greedy하다고 하는 거야. 그리고 그게 바로 policy를 향상시킨다는 거야.
--This improves the value from any state s over one step
어떤 상태든 한 스텝을 가면 즉 k+1이면 value가 증가한다. 왜냐면 고를 수 있는 action중에서 최고를 고른 것이니까
근데 저기 괄호 안에 q(s,a)이였는 데 왜 갑자기 ㅠ(s)로 적혀있냐고 묻는 다면 .... 위에도 말했다 시피 action은 Policy(s)라는 것을 기억해둬. policy에 따라 고른 action 1개보다 action 여러개중에 제일 좋은 것을 고른 것이 더 좋거나 같다라는 거지. 왜냐면 같을 수도 있으니까 같을 수 있다고 한거야. 그래도 더 좋아진다 이거지.
-- it therefore improves the value function v'(s) >= v(s)
그러므로서, v'(s) 는 v(s)보다 더 좋아지거나 같아진다. 이런 의미인데, v(s')라는 것은 state S의 successor state지? 그니까 action을 해서 간 다음 state였잖아. 작은 따옴표의 의미를 다시 기억하고.
이제 증명을 해주는 거야.
내 손이 좀 귀찮아서 ㅠ는 뺄게.
우선 v'(s)는 저렇게 큐함수로 나타낼 수 있어. 왜냐? v(s')는 v(s)에서 action을 한번 하고 난 뒤의 v(s)니까 q함수의 의미가 action을 한번 하고나서의 v(s)였잖아? 그니까 저렇게 나타낼 수 있는 거지. 근데 중요한 것은 action을 했던 것이 argmax를 했다는거야.
그리고 q함수의 수식?이 나오잖아? 저거는 뭐 2장에서도 배웠고, s라는 상태일때 action을 한번 했으니 보상을 한번 받고나서의 v(s+1)과 같다라는 거야.
근데 저 v쪽을 q로 바꿀 수 가 있엇잖아? 그래서 단지 그거만 바꾼거야.
그래서 잘 따라가보면 원래 state value function이랑 똑같은 거 아니야? 라고 느낄 거야. 결국 value funciton이거든.
그럼 뭐가 바뀌냐고? 바뀐거 없어. 진짜 value function이야. 단지.. arg max해서 얻은 action이 적어도 같을 수도 있지만 클 수도 있다는 것을 나타내는 거지.
그렇게 생각했어 난.
증명 끝
// Policy Improvement(2)
근데 이 반복을 언제까지 하냐고? 라고 묻는다면... (지금 반복은 평가하고 향상하는 것을 반복하는 행위를 말해)
이걸 언제 까지 하냐면
조건 만족시 optimal에 도달했기 떄문에 멈춘대. 그니까 지금 보이는 4개가 다 동일하면 이제 최고의 선택을 해서 얻는 게 이미 최고일때? 라는 대충 해석하자면 이런 의미야. 하나씩 직접 생각해봐. 지금 내가 선택할 수 있는 action이 항상 최선이라는 뜻이지. 그러면 optimal이라고 생각하고 멈춘다는 거야.
그래서 저 조건이면,
벨만의 최적 식이 만족 되었다는 거야.
그래서 모든 상태는 다 최적이라는 거고 최적의 Policy를 찾았다는 거지.
// Modified Policy Iteration
이건 좀 바보같은 질문들이지만 정말 중요한 거야.
- 꼭 policy를 평가하는 게 vㅠ에 수렴해야되?
- 중간에 멈추는 조건 만들면 안되?
- 아니면 k 번 반복했을 때 그냥 간단하게 멈추면 안되는 거야?
왜 이런 생각을 하냐면 아까 k가 무한대로 즉 수렴을 안했는 데도 optimal policy를 찾았잖아. 3번만에!
그니까 이런 생각을 하는 거야. 아니~ 꼭 끝까지 안가도 찾을 수 있는 데 꼭 끝까지 가야되? 라는 생각을 하는 ㄱ어ㅑ.
그리고 또, 꼭 한번씩 번갈아 가면서 해야되? 3번 평가하고 한번 greedy하거나 3번 greedy하고 1번 평가하면 안되? 뭐 이렇게 하는 건데
결론은 그렇게 해도 된대. 그게 바로 value iteration이래. 우린 여태까지 policy Iteration이였잖아.
더 자세한 건 앞으로 말해줄게
// Generalised Policy Iteration
이건 아까 보던 그림이랑 똑같애.
단지..
any policy evaluation algorithm
any policy improvement algorithm
즉... 어떤 방법을 쓰든 평가만 하면 되고, 어떤 방법을 쓰든 향상만 시키면 된다는 거야. 범용적이라는 거지.
// Principle of Optimality
어떠한 최적의 policy든 두개의 요소로 나눌 수 있대.
1. 첫 action이 optimal하고
이 뜻은 최적의 policy는 처음 action이 최적이면 그 다음부터는 또 다른 최적의 policy를 따라갈 수 잇는거거든.
넌 그냥 너 할거만 잘 하면 되는 거야. 그 다음은 그 다음의 애가 또 optimal한 action을 하면 되는 것이지.
2. 다음? state인 즉 Successor state인 s'로부터의 optimal policy를 따르면 된대.
이게 그말이야.
그래서 이론이 나와. if and only if 는 필요충분이라는 말이야.
어떠한 policy는 이럴 때 필요충분적으로 최적 value를 이룬다는 데,
그 두개가 뭐냐면
s에서 갈 수 있는 어떠한 s'든, policy가 s'에서 optimal value를 이룬다..
이게 그 말이야. 어떠한 action을 해도 다음 state에서의 value가 제일 좋은 거라는 거지. 뭐 단순하게 생각해 그냥.
내 행동을 제일 좋게 만들어주는 policy는 항상 좋은 value function만 선택하도록 해줄 거 아니야.
너가 포커를 칠 때, 너의 행동을 조종하는 애가 optimal policy면 항상 좋은 패만 골라서 돈 많이 따도록 해줄 거아니야. 그런 의미야.
// Deterministic Value Iteration
자 그래서 여기서 말하는 것은 만일 우리가 부분문제인 v*(s')를 알면 v*(s)도 알 수 있다는 거야. *는 제일 좋은 거를 뜻하는 거라고 했지? 최적을 말해. 한마디로 우리가 한 차례 앞을 볼 수 있다면 현재에서 최선의 value도 알 수 있다는 거야. 한마디로 우리가 할 수 잇는 행동중에서 가장 좋은 행동을 골라서 제일 좋은 행동을 할 수 있다면, 현재 있는 state에서의 최적의 value도 알 수 있다는 거지.
그래서 one step lookahead라는 거야. 한 스텝 앞을 본다.
그래서 여기서 말하는 것은 이런 식으로 쭉쭉 한다는 가정하에 마지막 뒤에서부터 시작할 수 잇다는 거지.
방금 말한 한 스텝을 가서 보는 것을 반복해서 하자는 것이라는 아이디어가 value iteration의 아이디어래.
즉 마지막 보상부터 시작해서 ( 끝에서부터 시작해서 , 보통 끝은 최종 terminal이라던지 우리가 이루고자 하는 목표지. 목표로부터 시작하자 이거야.) work backwards 뒤로 가자 이거야. 우리가 살아갈때도 이런식으로도 많이 하잖아? 우리가 어떤 수학문제를 풀 때 우리가 생각해서 답을 내기도 하지만 답을 안다면 답으로부터 시작의 식을 유도할 수도 있잖아 그치?
혹시 헷갈릴까봐 말한다면 방금까지의 내용은 평가를 하고 greedy하게 policy를 향상시켜서 최적의 policy를 얻을 수 잇다는 것이였고, policy를 향상시키는 것은 내가 가진 행동 중에 제일 좋은 것을 고르는 것이였고 이렇게 하면 적어도 같거나 더 좋은 것이라는 것을 증명하는 단계였어.
그렇기 때문에 지금 내가 할 수 있는 제일 좋은 행동을 고르면 최적으로 간다는 거였어. 맞지? 틀리면 댓글로 남겨줘.
그래서 지금 이 아이디어도 생각할 수 있는 거야. 반대로 내가 제일 좋은 행동으로 얼마를 얻을 지 안다면, 그걸 활용해서 나를 update 할 수 있다는 거지. 이것도 가능하다고 증명이 되었어. 굳이 말하진 않았지만?
우선 식부터 보자.
말로 풀어서 설명해 줄게
우선 v*(s)의 식을 뭔지 모르겠으면 2장에서 봐봐. state value function인데 최적의 state value function이였고
max v(s)였어. v*(s) = max Ras + r Sigma ( Pass' * v*(s') 였지. 기억해.
max aE A Ras : state s에서 어떠한 action을 통해 얻는 보상인데, 이 보상은 내가 할 수 있는 action 중에 제일 좋은 action이래. 그러니까 제일 좋은 action을 통해 얻는 보상이고,
r * Pass' * v*(s') : discount는 뭐 알테고, 뭐 이 뒤는 똑같애. 앞에서 action이 제일 좋은 거라고 했잖아. 거기서의 value function을 말해.
이정도면 이해가지?
// Example: Shortest Path
이 예제로 설명을 조 ㅁ더 도와보자.
우선 problem은 문제 정의야. 가장 짧은 경로를 찾는 건데, 각 칸에 value function을 채워야되.
그래서 우선은 아무 값이 없어. 단지 목적지인 terminal만 검정색으로 되어있고 0이라고 채워져 잇는 것이지. 여기서 discount등은 말해주진 않네. 여태까지 자연스레 1이였으니 1이라고 생각을 해보자.
그리고 아까도 그랬듯이 v1에는 랜덤하게 아무 값이나 채운대. 그래서 0을 다 채우네. 보상은 여기서 -1인거같애.
그럼 v1에서 이제 v2로 갈때 방금 위에 식을 그대로 적용해보자. 이번에도 (1,1)로 봐보자?
0인데, 지금 내가 할 수 있는 최선의 행동이 뭔지는 아직 모르겠지. 그니까 우선 어떤 행동이든 간에 보상은 -1이겠지. 맞지?
그리고 r은 1이고 내가 max인 a로 갈 수 잇는 데는 무조건 한군데지? 위로 가면 위로만 가잖아. 아래로 가면 아래 상태로만 갈테고, 그니까 Pass'도 1이야 그리고 어떤 제일 좋은 상태에서 내가 얻을 수 있는 것은 어떤 최선의 선택이더라도 0이지 지금? 그니까
결국 계산해보면 ( 지금 옆에 식 보면서 따라하는 거 맞지? 옆에라고 말한 이유는 내가 지금 프린트를 pdf 4장을 한눈에 보고 있어서 deterministic value iteration 을 보고 있어서 그래) -1이 되.
맞지? 현재는 모든 값이 그래서 다 -1이 되는 거야. 보상은 -1이고 얻을 수 있는 게 다 0이니까 본인을 -1로 update한거야.
그럼 v3를 한번 봐보자. 다시 말하자면 v2에서 v3로 넘어가는 것을 계산해보자. 여전히 1,1을 봐봐
우선 어떤 곳을 선택해도 얻을 수 있는 보상이 뭐야. -1이지? 거기다가 어떤 곳도 -1이야. 그래서 뭐 위랑 똑같이 계산해서 -2가 되.
근데 0,1을 봐보자. -1이지? 왜 다를까.
거기서 계산을 해보자면 우선 보상은 -1이야. 근데 제일 좋은 곳이 terminal이지? 그니까 terminal의 v(s)는 현재 0이야. 그니까 -1이 여전히 유지되는 거야. 그걸로 본인을 udpate햇으니까 -1이 되는 거지.
마지막으로 이해를 돕기위해서 v3을 update해보자. (1,1)
우선 보상이 -1이야.
그리고 나머지 r, pass'도 1이야 맞지?
근데 가장 좋은 선택은 지금 왼쪽이나 위로 가야 되는 거잖아 그치? 오른쪽이 더 좋지는 않잖아. 그래서 -1을 더하는 거야. 그럼 -2가 그대로 되는 거야. 나머지도 계산해바.
// Value Iteration
아까는 evaluation과 improvement를 반복했었어. 그때는 policy가 있었지? 근데 지금은 policy가 없고 value만 가지고 논대. policy 함수가 아예 없는 상황에서 한다네?
problem은 최적의 policy인 ㅠ를 찾자는 거야.
이걸 어떻게 하냐? bellman optimality backup을 통해서 한대. 아까는 bellman expectation이였어. 근데 지금은 optimality야.
뭐야 방금까지 policy iteration아니였어? 라고 한다면 다시 제목들을 봐봐. shortest path도 value iteration이였어....
무튼 다시 말해줄게.
policy 없이 value function 못 구한다며? 근데 어떻게 구하라는 거야? 라고 하지만 여기서 말하는 policy는 아예 없는 게 아니라 explicit policy가 없다는 거야. 예전에 1강에서 agent 종류 설명할 때도 이런 얘기를 했었지. implicit policy는 잇지만 explicit policy가 없는 것이라고. 나도 이거는 살짝 이해는 안가. 근데 분명 policy는 존재해. 근데 그게 greedy하다라고 하면 이해가 갈라나? 아까 policy iteration에서는 어떠한 명백한 policy들이 있었던 거야. 그 policy를 평가한 후에 greedy하게 계속 하는 것을 반복했더니 최적으로 갔다는 것이고, 여기서는 그냥 greedy한 policy 그냥 좋은 거로만 계속 가는 policy가 있다는 뜻이 아닐까? 난 그렇게 받아들였어. 어떤 특정한 게 없이 그냥 value만 가지고 좋게만 계속 만드는 거? 라고 생각해.
그리고 여기서 차이는 bellman optimality backup을 쓴대. 내가 생각한 대로라면 어찌 보면 당연해. 그냥 bellman expectation backup을 쓰면 그냥 나를 평가하는 거 외에는 안되. 아까 policy iteration에서는 어떠한 멍청이들이 있어. 그럼 그 policy를 이용해서 그 value 함수를 보면서 새로운?이라고 할 수 있나? 무튼 그런 거기에 맞춰서 greedy하게 움직이는 policy를 만든거라면....
근데 여기서 어떤 policy 조차도 없다면 우선 평가한 후에 계속 좋게만 만들게 하는 거라 당연히 policy가 없다면 그냥 내가 할 수 있는 행동중에 제일 좋은 것을 선택하는 bellman optimal을 쓸 수 밖에 없는 것 아닐까? 그게 어떻게 보면 policy긴 한데, random policy같이 랜덤하게 하겠따같은 어떤 policy는 아니니까.... 이런걸 implicit이라고 하는 지는 모르겠네.
무튼 다른 점은 bellman 수식이 달라진다는 것이고
이것도 저번에 봤던 거와 똑같애. synchronous backup이고, 대신 계속 update하다보면 최적의 value function이 만들어지고,
( 저번엔 update 하다보면 그 policy의 value function을 구한다는 거였지 최적을 구한다는 건 아니였어)
그래서 이거에 대한 증명은 나중에 보여준다는 데 강의에 없음. 그냥 그렇다고 알어.
// Value Iteration (2)
이 수식이 뭔지 알지? bellman optimality equation
뭐 2장봐 모르면
넘겨
// Example of Value Iteration in Practice
넘겨
보고싶음 보고
이해를 위해선 봐
영어 못하면, 대충 해석해줄게
자바가 잘 안되서 FireFox에서 test해봤대.
10x10 의 grid world에서의 value iteration을 보여준대.
여기서 따로 value function이 어떻게 되는 지 보여주는 거 같아. 왜냐면 이 다음 장을 계속 봐도 value iteration을 설명해주지 않거든. 아까 그 grid world로 이해를 하던지 아니면 이걸로 이해하던지 하면 될 것 같아.
// Synchronous Dynamic Programming Algorithms
이건... synchronous한 DP 알고리즘들을 말해주네.
prediction에는 벨만 기대 수식이 쓰였고, 알고리즘은 iterative policy evaluation 알고리즘을 쓰고
control을 구하는 방법에는 두가지가 있는 데, policy와 value iteration을 사용했다고 하네.
prediction은 value function을 구하는 거였는 데, 어떠한 policy의 value function을 구하는 것은 policy evaludation이였어.
그리고 policy iteration과 value iteration을 하면 최적의 poilcy를 구하는 것이였는 데 이제 정리가 좀 되지?
알고리즘은 state value function에 기반하였대.
복잡도를 말해주는 데, state value function을 쓰면 복잡도가 m*n^2인데, action value function도 쓸 수 있지만 복잡도가 더 복잡해지네. 그래서 일반적으로는 value function을 쓰는 것 같아. 왜 action value 함수 가 m^2 * n ^2인지는 직접 생각해봐. 아니면 넘겨.
// Asynchronous Dynamic Programming
지금까지는 synchronous로 했었지? 모든 state를 다 돌면서 update했었어. 즉, 한번 state들을 쭉 돌면서 update한 거야. 무슨 말인지 더 정확하게 말해주자면 너가 주문을 받았어 커피 주문을 10개 받으면 10개를 다 만든 후에 한꺼번에 준거야. 그리고 남은 커피 계산한다던지 한 거지. 근데 이거는 그냥 만드는 즉시 주고 계산하고 뭐 이런거야. 대충 말하자면? 이해 되? 다 독릭적으로 할 ㅜ 있다는 거야.
원래는 주변을 참고해서 하나를 만들었잖아. 근데 그건 다음 step에서의 value였지 그 떄 바로 바꾸는 게 아니였잖아. 바로 바꾸면 옆에 애가 참고할때 바꾼 걸로 참고하는 참사가 생기잖아. 이해되지?
그래서 한번에 계산을 해놓고 쑝 바꾼 거였어. 근데 이건 그냥 바꾼대. 그래도 된다네. 계산량도 엄청나게 줄어든대.
이렇게 해도 수렴이 가능하대.
// Asynchronous Dynamic Programming
Asyn의 방법 3가지를 말해주고 있어.
3개 일겅봐
// In-Place Dynamic Programming
silver 교수는 이건 그냥 일반적인 코딩 기술에 가깝다고 하고 있어. 물론 신기한 점도 있지만.
중요한 개념은 앞에 설명한 게 훨씬 중요하니까 그거만 봐도 되.
이거는 단순하게 말해서, 내가 아까부터 하나를 update할 거면 계산한 것을 다른 데다가 저장을 해놔야된다고 했지? 바꾼 값으로 참조 하면 안되니까? 근데 이거는 그냥 update하면 바로 바꿔버리는 거야. 한마디로 행렬이 1개여도 된다는 거지. 그렇게 해도 된대.
행렬 1개로 하는 방법을 ㄹ보여주는 거야. 식은 뭐 이미 보던거고 old와 new만 봐봐. 원래는 old행렬을 참고해서 new에 집어 넣는 방식이였어. 근데 이제는 old <- new를 집어넣어서 그냥 old 행렬을 계속 사용하는거야.
// Prioritised Sweeping
이건 priority가 뭘 의미하는 지 알지? 우선순위 말할 때 많이 쓰이지. 운영체제나 이런거 공부했으면 익숙하겠지.
여태까지는 그냥 순서적으로 하나씩 update를 했었어 맞지?
근데 이거는 어떤 순서로 update하던 상관이 없는 데, 중요한 애들 먼저 하겠다이거야.
흔히 벨만 에러가 큰 애들부터 update하겠다는 거야.
여기서 bellman error가 처음 등장하지.
쉽게 말해서 정답 - 현재로 에러율을 측정해. 이건 뭐 다음에 나와. 그냥 이런게 있다고만 알아둬. 나도 이렇게 들었어.
// Real-Time Dynamic Programming
이건 state space가 넓은데 agent가 가는 데가 한정적일 때, agent를 움직이게 하고 방문하면 update한대.
무슨 말이냐면, 지금까지는 모든 state에 대해서 다 update를 했었지? 근데 agent가 직접 policy에 따라서 가보는 거야. 그래서 실제로 방문한 state들이 있을 거잖아? 그런 애들만 update한다는 거지. 안가본 데는 update 안하것지.
// Full-Width Backups
지금까지는 full swip이라고 했지? 다 한다고. 모든 state에 관련해서 다 update를 했었잖아.
근데 사실 이게 진짜 비 효율적이기도 하지만 중요한 것은 계산할 게 너무 많아. state만 해도 너무 많아 실제에서는.
그래서 원래는 state s 에서 가능한 모든 s' 를 고려했엇잖아? 근데 그럴 필요가 없다는 거지.
큰 문제에서는 너무 커져서 차원의 저주에 빠진대. 기하학적으로 계산이 늘어가니까.
실제에서는 그런 계산할 게 너무 커서 한번 backup을 할 때도 엄청 비용이 비싸대.
그래서 나온 것이 Sample backup이라는 개념이야.
// Sample Backups
앞으로 다룰 강의들에서는 우리는 좀 더 실제적인 방법으로 sample backup을 다룰 거야.
이 sample backup은 MDP와는 좀 달라
생각해봐
MDP는
SAPRr ㅠ 이렇게 필요했엇지?
이제는 SARS' 이렇게만 필요해.
이제 다음 state로 전이할 확률이였던 P가 없어지고 보상이였던 R이 없어져.
잉? SARS'에도 R 있는 데? 라고 생각하면 오산. R은 모든 전이가능한 P에 관련된 R이였잖아
여기서는 몇개만 sample한 보상을 말해.
그니까 너는 여태까지 지금 1이라는 state에서 2,부터 10까지의 갈 확률 인 P와 2부터 10까지의 보상 R을 가지고 한거야.
근데 이제는 1에서 sample을 해서 3, 5, 7 에 대한 상태와 그에 대한 보상 3개만 가지는 거지.
뭐 대충 이렇게 알아둬
이해 되지?
이걸 하는 이유는 뭐라고? 계산을 너~ 무 많이 하니까 ㅠㅠ.
그래서 이거의 장점은
Model-fee에서도 쓸 수 있때. MDP가 아닌. 즉 우리가 환경을 모를 때에도 할 수 있다는 거야. 여태까지는 환경을 다 알고 있엇어. 무엇이 들어올지. 맞잖아? 근데 sample하면 MDP에서도 쓸 수는 있겠지만 환경을 모를 때에도 즉 내가 모든 행동을 고려할 순 없고 거기에 대한 모든 것을 알지 못할 때에도 적용할 수 있따는 거지. 점점 더 현실적으로 다가오는 거야.
그리고 이렇게 하면 backup하는 비용이 항상 일정해서 이제 차원의 저주에 빠지질 않아. 항상 일정한 비용만 들게 되. 왜냐면 많으면 sample 적게 하면 되잖아. 예를 들어서 너가 어떤 걸 계산할때 아까 처럼 1부터 10이야. 그럼 다 생각을 했었고, 1부터 100이면 100까지 다 생각을 했었어.
근데 sample backup은 달라. 너가 1부터 100까지를 생각하던 만 , 조를 생각하던 그냥 나는 3개만 뽑으면 되. 그니까 일정한 비용이 발생한다는 거야. 이해되지?
나머지는 직접 읽어봐. 강의에서 안다뤄
그대신 너가 궁금했던 value Iteration의 수렴을 증명한다던지 이런걸 말해주고 있어. 읽어서 나쁠 건 없어. 다 읽어봐.
원하면 말해 설명해줄게.
대충 보니 value iteration과 policy iteration이 진짜 수렴하는 지에 대한 이론과 증명을 말해주고 있어.
3강 끝
제가 틀린 것이나 잘못 설명한 것 또는 이해를 잘 못한 부분이 있따면 말해주세요.
// 질문
1. Prediction은 value function을 구한다고 했는 데, 2장에서의 state-value function과 똑같은 것 아닌가?
2. Value iteration에서 policy가 없다고 했는 데, implicit policy가 있다는 거 아닌가? 그럼 그건 그냥 greedy로 볼 수 있는 건가?