이번에 Lecture 2 : Markov Decision Processes을 배울 거임.
// 1 제목
넘겨
// 2 목차
넘겨
대충 3번까지가 메인 핵심
// Introduction to MDPs
먼저 MDP가 뭔지 알지? Markov Decision Process 인거 모른거면 내꺼 전꺼 안본거고, 이건 Fully Observable 한 상황이란 건 알고 잇어야해.
이 왠만한 강화학습 문제는 다 MDP로 표현할 수 있대.
POMDP도 MDP로 변환시킬 수 있고, 등등.... 뭐 무튼 그렇대
// Markov Property
" 미래는 과거로부터 독립적이고 현재만 필요"
즉 현재 State만 필요하고, 사실 history 자체는 없어도 된대.
그래서 정의가 하나 나오는 데 이건 전에 배웠던 거지.
이런 걸 마르코프 상태라고 하고..
State는 미래를 충분히 표현한 것이다~ 라고 말하네
// State Transition Matrix
state transition은 기억나? 어떤 상태에서 다른 상태로 전이하는ㄱ ㅓ잖아.
여기서는 행렬로 표현하고 있어.
어떠한 markov state 인 s와 다음 state s'가 있을 때, Pss'로 나타낼 수 잇대.
그럼 이 state 자체가 10개가 있다면 s1 에서 s2로 갈 확률, s1에서 s3로 갈 확률 ...... .... sn까지 잇겠지?
1에서 2로 갈 확률을 P12이라고 한다면 이걸 다 모아보면 P11부터 P1n이 가로 한 행으로 볼 수 있꼬, P21부터 P2n 한 행, 계속 해서 Pn1부터 Pnn까지 행이 있겠지. 그걸 행렬로 표현한 것을 P로 나타낼 수 있어.
가로인 한 행을 다 더하면 1이 되. 왜냐면 너가 붕어빵을 먹을 때 꼬리먹을 확률이 60이면 안먹을 확률은 40이잖아. 0.6 + 0.4는 1이잖아. 행렬자체가 아닌 가로야. 주의해
// Markov Process
마르코프 프로세스는 memoryless random process라고 하는 데, 이게 뭐냐면,
memoryless는 마르코프 state니까 내가 어느 시작점에서 왔는 지 생각할 필요 없이 즉 지금 이 state에 온 순간 정의가 된다 이거지. 이거는 markov property를 말해. 현재 상태가 미래를 충분히 표현한 것이니까.
그리고 random process는 sampling이 가능하다는 얘기야. 그니까 어떤 상태에서 계속 이동하게 되면 어떤 이동 경로가 나오잖아? 근데 다시 그 state에서 시작해도 또 다른 경로를 생성할 수 있다는 거지. 이걸 샘플링이라고 해.
그래서 정의 하나가 나오는 데,
Markov Process는 사실 Markov Chain이라고도 말하고 Chain으로 더 많이 불리는 거 같기도 하고?
무튼 MP는 S와 P로 표현할 수 있어.
S는 유한한 상태 집합이야.
P는 아까 말한 상태 전이 확률 행렬이야.
// Example : Student Markov Chain
이건 예제야.
동그라미들인 노드들은 다 State야.
그리고 가중치같이 보이는 숫자들은 다 상태로 전이할 확률인거지.
Class 2를 보면 Sleep 상태로 갈 확률이 0.2고 Class 3으로 갈 확률 0.8이야.
// Example : Student Markov Chain Episodes
여기서 C1은 그냥 현재 state들을 보면 Class 1 어쩌구 되어있잖아. 그래서 그냥 그렇게 표현한 것일 뿐이고 실제로는 뭐 S1이야.
그래서 아까 말한 Sample이라는 것은 어떠한 State에서 시작해서 게임이 끝날 때까지 전이한 sequence를 말해.
그런 sequence를 생성하는 것을 샘플링이라고 해.
그리고 하나의 sequence 즉 시작해서 끝나는 것을 하나의 episode라고 해.
여기서는 시작을 C1 = Class 1 으로 정의했어.
그래서 한번 샘플링 해서 C1 c2 c3 pass sleep이라는 하나의 episode를 만들어낸거야.
episode와 sample 개념을 잘 알도록
// Example : Student Markov Chain Transition Matrix
이제 보면 아까 보던 행렬 P에 각각 전이될 확률이 저기에 다 써있지?
전이 확률 행렬을 보여주는 거야.
비어있는 칸은 뭐냐고? 빵이야
보기편하라고 뺸 거야 그냥
// Markov Reward Process
이건 MRP라고 해.
Markov Chain즉 Markov Process에서 보상이 추가된거야.
그래서 이제는 S,P,R,r로 표현할 수 잇어. R은 알다시피 보상이고, r은 감마. 전에 설명햇지?
나머진 다 똑같고, 상태 S에서 받을 수 잇는 보상 s가 추가되었어. 어떤 State S로 가면 몇을 주겠따는 거야.
r은 discount factor라고 하고 전에 말했다시피 0에서 1사이로 구성되어 있어.
discount는 할인? 이란 뜻인데 왜인지는 전꺼를 봤다면 알겠지
// Example: Student MRP
이제 R이 추가됬어. 현재 discount factor인 r은 안써져있어. 그냥 1로 생각해.
이제 c1에서 c2로 가면 보상인 -2를 받는거야.
// Return
이거 아~~주 중요해.
강화학습은 Return을 최대화하는 게 목적이라고 볼 수 있어. 예전에 강화학습에서는 보상을 최대화한다고 했잖아? 더 정확하게 말하면 return을 최대화 하는 게 맞아
return은 보통 Gt로 표현해.
이거 사실 좀 비슷해보이지 않아? 첫번째 강의랑?
여기서 다시 말해줄게, Lecture 1에서의 value function과 지금 return 보면 완전 똑같애. 계산 방식은 Lecture 1에서 설명했어 내가. 그거 봐.
근데 다른 점이라고 하면 E랑 뭐 S가 없네?
이거는 좀있다가 나중에 말하겠지만. 기대하는 값과 return은 비슷하지만 달라. 기댓값은 말 그대로 기대하는 값이야. 앞으로의 얻을 보상들을 다 더하면 return이라고 했지? 이건 아까 우리가 example에서 일련의 sequence들을 sample 했었잖아? 그게 하나의 episode가 된다고 했고? return은 샘플된 경로에서의 모든 보상들의 합이야. 반면 value function은 모든 보상들의 합은 맞는데 그걸 경로의 개수 만큼 평균 낸거야. 생각해봐 너가 어떤 길 A 에서 3가지 갈래길이 잇는 데, 1개는 별로 안 좋았는 데 2개의 길은 좋았어. 그러면 그 A 라는 길은 선택하는 것은 대체적으로(평균 적으로) 좋았다~ 라고 생각할 수 있어. 그렇기 떄문에 기댓값이라고 하는 거야. 한 길의 총 보상 합이 return이고 모든 길의 return을 평균낸게 value function으로 생각해.
근데 여기서 discount는 왜해? 라고 할 수 있어. 물론 내가 lecture 1에서도 근시안이냐 원시안이냐를 말한 것도 있지만 가장 현실적으로는 더 계산하기 쉽대. 왜냐면 이렇게 하면 수렴이 증명된다고 하네. 뭐 그냥 ㄱ렇다고 생각해.
// Why Discount?
왜 discount하는 지 나오는 데,
수학적으로 편리하고 등등 이유 읽어봐 한번.
수렴이 가능하다는 이유는, 만약에 순환이 있다고 해봐 경로에. 그러면 discount factor가 1이면 return이 무한인게 들어와. 그러지 않게 하기 위해 그런거야. 근데 1이 가능한 건 순환이 없을때래.
// Value Function
여기서 또 나오는 데, Return의 기대값이라고 보면되. 아까 말했듯이 얼마정도의 return이 오겠다고 생각하는거지. 평균적으로
내가 이 다음 state로 가면 어느정도의 return을 기대할 수 있겠구나~ 라고 생각하면 되.
그래서 정의 보면 어떤 State S에서의 Gt ( return) 기대값이라고 할 수 있어.
// Example : Student MRP Returns
저거 보면 discount가 0.5래
그럼 첫번째 episode부터 봐봐 저거 계산 가능하지?
하나의 State에서 저렇게 많아. 갈수 있는 경로가.
그래서 오른쪽 -2.25 등등 이렇게 나오는 것을 평균낸거야. 이해되지?
// Example : State-Value Function for Student MRP (1)
여기서의 discount는 0이래. 그럼 어떻게 되겠어.
원래는 끝까지 가보면서 reward를 다 더하는 데, 그냥 더하는 게 아니라 discount랑 곱하면서 더하잖아. 근데 그 discount가 0이래. 한마디로 다른거 다 필요없고 바로 앞만 보겠다 이거야. 바로 다음 상태에서 받는 reward만 보겠다는 거지.
그래서 보면 원래 상태였었는 데, 지금은 다 값이 바뀌었어.
숫자를 보면 다 자기 상태로 왔을 때의 보상값이지?
당연하지
왜냐면 내가 아까도 말했다시피 그 상태로 갔을 때의 보상만 보겠다고 discount를 0으로 설정한거라고 했잖아.
그니까 그 상태를 가면 그냥 -2를 얻는거야.
이해 되려나?
원래 C1이 보상이 -2였잖아.
누군가가 C1을 가게되면 얼마를 받겠어?
원래는 C1 C2 C3도 있고, C1 C3 C2 뭐 이런 것들을 평균내서 해야하는데, 이제 discount가 0이야. 그니까 C1 (C2,c3) C1(c3,c2)가 되는 거야. 괄호는 안본다는 의미로 쳐썽. 그러면 return을 평균내면 value function은 당연히 그냥 C1의 보상값인 -2가 되겠지.
그래서 다 본인들 보상값을 가지고 있는 거야
// Example : State-Value Function for Student MRP (2)
이제는 discount가 0.9야.
값이 바뀌었지? 이제 경로들을 가본 것들을 평균 낸 게 저렇게 됬다는 의미야. 근데 계산을 해보려고 하니까 어떻게 계산할 지 모르겠지?
아직 안배웠으니까.
그걸 좀있다가 배울거야
// Example : State-Value Function for Student MRP (3)
이거지.
discount 빼먹었잖아.
그니까 다시 정리하면
v(s) = Rt+1 + r * v(s+1) 이거지.
한 스텝을 가서의 보상과 discount * 거기서의 valuefunction과 같다는 의미야.
살짝 점화식과 ㅣㅂ슷하지?
//Bellman Equation for MRPs (2)
자 방금 바로 윗 식은 그 식이지?
그리고 그림은 그냥 이해해.
이걸 다시 정리하자면
v(s) 즉 State s의 value function은 우선 State s로 갔을 때 얻을 보상 + discount * 어쩌구인데
이 어쩌구를 설명하자면
그림 보면 갈래가 2갈래지?
다음 상태로 갈 수 있는 게 2가지잖아. 당연히 상태는 1개만 있는 게 아니잖아. 여기서는 예시로 2개만 보여준건데. 무튼...
그럼 2가지 중에 1개를 선택할 확률을 골라야할 거 아니야.
그게 Pss'잖아. s에서 s'로 갈 확률과 s'에서의 value function이야.
너무 어렵게 생각하지말고 봐봐.
그냥 똑같은거야. 단지 그 상태를 선택할 확률을 곱해준거지.
다시 말로 풀어 쓰면,
State s에서의 value function은 그 상태를 갔을 때의 보상과 discount * s에서 s'으로 갈 확률 * s'에서의 value function이지.
근데 여기서 딱 한 s'을 하는 게 아니라 갈 수 있는 모든 s'를 더한거야. 왼쪽을 계산했으면 오른쪽도 계산해봐야 할 거 아냐.
// Bellman Equation for Student MRP
이제 다시 풀어보자.
4.3이라는 State 봐봐. 저기 가면 4.3이라는 value function을 얻을 수 잇대. 그럼 계산해보자.
(1) 우선 그 상태에서 얻을 있는 보상은 -2 지?
+
(2) 4.3에서 갈 수 있는 상태는 10과 0.8이지? 10으로 갈 확률은 0.6이래. 그리고 거기서의 value function은 10이야. 여기서의 discount는 1이야.
어떻게 아냐고? 아까 나왔잖아. 모르면 전에 똑같은 slide를 잘 봐봐.
그리고 하나 더 선택할 수 있지?
0.8로도 갈 수 있잖아
거기로 갈 확률은 0.4래 근데 그 상태의 value function은 0.8이래
그러면 식을 계산해보자
현재 State 자체에 써져있는 숫자가 value function이라는 것을 알아둬.
4.3 state 보상 ( -2 ) + discount(1) *10 state 로 갈 확률 (0.6) * 10 state에서의 value function (10) + discount(1) *0.8 state로 갈 확률 (0.4) * 0.8 state에서의 value ( 0.8)
이거 이해 안가면 다시 공부해.
계산해보면 4.3 나와.
여기서 아니 10 value function만 구하며 안되지~ 앞으로의 끝날때까지의 보상이라며~ 그럼 더 가서 구해야지!
0.8에서도 쭉쭉가서 모든 상황을 구해야하는 거 아니야?
라고 묻는다면 지금 이해를 못한 거야 너가
이미 지금 value function이 구해져있짢아 10 state는 value가 10이라고. 그니까 그 뒤를 뭐하러 구해. 구할라고 한다면 직접 해봐. 그게 맞지만 구하면 그대로 나올 거야.엄청 복잡해 지긴 하겠따만 한번 해보는 것도 나쁘진 않아
// Bellman Equation in Matrix Form
이건 지금 아까 그 식을 행렬로 표현할 수 잇따는 거야.
v는 모든 유한한 state의 개수이고, R도 각 state 개수만큼의 보상이겠지?
그리고 P1에서 갈 수 있는 모든 경로인 가로를 보면 P11부터 P1n까지 있고, 그거 * 그때의 value function.
행렬을 못하면 이런 질문도 나올거야
어? V1은 R1+ P11...P1n * V(1)???? 이런 질문 설마 안하겠지.
행렬이 어떻게 곱해지는 지 잘 모르면 다시 공부를 추천.
그리고 저기에 오타 있는데 P11~P1n은 맞는 데, P11~Pnn은 아니야. Pn1이겠지
무튼 이렇게 하면 한방에 계산할 수 잇때
// Solving the Bellman Equation
위 계산식을 저렇게 바꿀 수 있다는 거야
저거 넘길 수 있다는 것은 조건이 만족이 되는 데, 넘겨지는 거 어떻게 하는 지 모르면 곤란해.
직접 보면서 넘겨봐. 어렵진 않아
근데 저렇게 하면 어째뜬 P와 R을 곱하게 되잖아? P는 n제곱이지? R은 n이니까 빅오 n^3이라서 엄청 커.
그래서 지금 이렇게 한방에 구할 수는 있지만 너무 커서 작은 문제에서만 쓰여.
생각해봐 state가 10개만 있겠어? 사실 만개로만 생각해도 조단위구만.
그래서 한방에 계산안하고 반복적으로 조금씩 바꾸는 방법들이 이제 DP, MC, TD 뭐 이런게 있때. 이건 나중에 배울거야.
// Markov Decision Process
이제 드디어 MDP가 나와.
모든 상태가 Markov한 환경이래.
여태까지는 이상하게 action이 없었지? 이제 action이 나와
MRP에 action을 추가한거야.
그래서 MRP와 다 똑가은데 A라는 actino이 추가되었어. action이 decision이나 마찬가지야. 유한개고.
// Example : Student MDP
지금 보면 action을 하면 예를 들면 action study를 하면 보상 -2를 받는 것을 볼 수 잇어.
근데 여기서 특징이 Pub이라는 action을 하니까 보상을 받기는 하는 데, 잘 보니까 분기점같은 게 잇지? 어떤한 state에 도달하는 게 아니라 거기서 또 3갈래로 갈리잖아?
action을 한다고 다른 상태로 바로 가는 게 아니야. 그 action에서 또 주사위를 던져서 확률에 따라 갈 수가 있다는 것이지.
// Policies (1)
MRP에서는 그냥 확률분포가 있었고 거기에 따라 움직였다면,
이제는 action을 하기는 하는 데, 넌 뭐를 기준으로 action을 할래?
그냥 막해? action 할 수 잇는 게 3개가 있다면 어떤 기준에 의해 action을 골라야 할 거 아니야.
lecture 1 에서도 말했지만 이게 바로 action을 결정해주는 policy야.
policy는 다시말하지만 ㅠ 파이로 나타내지.
ㅠ( a | s ) 는 State s에 있을 때 action a를 할 확률이야.
Policy가 Stationary라고 하는 이유는 , 시간에 독립적이라는 건데, 이게 뭐냐면 너가 어떤 행동을 있어서 선택하는 기준은 시간에 흐름에 따른 게 아닌 어떤 기준이 있고 그 기준에 따라 선택하는 것이기 때문에 시간과는 독립적이라고 말하는 거로 난 이해했어.
MDP에서 policy는 현재 state에서만 결정된대.
// Policies(2)
이제 action을 어떻게 하도록 정해진 Policy ㅠ라는 기준이 주어진 MDP라고 생각해보자.
그러면 Markov Process는 S와 Pㅠ로 할 수 있어. 왜냐몀ㄴ P는 상태에서 상태로 가는 확률이잖아. policy가 정해져 있다면 어느 상태에서 어떤 action을 할 지가 정해져 있따는 거니까 그 말은 즉 어떤 state로 갈 지 안다는 것이지.
그리고 거기에 따른 보상도 policy에 따라 정해진 거니까 저렇게 표현할 수 도 있고,
밑에 2가지 식이 나오지?
너무 어렵게 생각하지마
첫번째껀 Pㅠs,s' 인데 이건 정해진 Policy를 따라갈 때( 어떤 action할 지 다 정해져잇음) s에서 s'으로 갈 확률.
보면 s에서 Policy에 따라 action a를 선택할 확률 * s에서 action a를 선택했을 때 s'로 갈 확률을 곱하고 잇어. 아까 예시를 생각하면 pub이 있었잖아? 그게 이해가 쉬울 거야. pub이라는 액션을 할 확률과 pub이라는 액션을 햇을 때 3갈래로 나뉘지? 그니까 다음 state로 갈 확률을 곱하는 것일 뿐이야.
단 Policy가 지금 정해져 있다는 걸 알아둬.
방금처럼 MDP를 저렇게 표현 가능하다는 건데, 그러면 Markov Process가 되는 거고,
밑에 꺼는 똑같은 원리로 보상을 적용했어. 그럼 MPR이 될 수 있따는 거야.
그래서 왠만한 문제는 다 MDP로 풀 수 있다는 거야. MP 문제도 MRP문제도 다 풀 수 있으니까.
// Value Function
이제 MRP에서도 있었던 Value Function을 MDP에서도 설명할게. 당연 달라
MRP에서는 policy가 없었잖아. 이제 value function을 설명하려면 Policy 인 ㅠ(파이)가 필요해
정의는 2개가 있어
State-value function 과 Action-value function이야. ( action value function은 state-action value function 이라고도 해)
State-value function은 State S에서 Policy인 ㅠ를 따라갔을 때 나오는 기대값이야. 전과 똑같은데 policy만 따라간다고 생각하면되.
Action-value function은 State S에서 Action a를 하고나서 Policy ㅠ를 따라갔을 때 나오는 기대값이야.
차이는 ACtion이 있냐 없냐야.
state만 들어가면 state value / state, action이 둘 다 들어가면 state action value
그리고 보면 q(s,a)라고 되어잇지?
이걸 q 함수라고도 해.
// Example : State-value function for student MDP
자 이제 예시야. State-value function이고, discount 는 1이네.
지금 Policy는 정해져있어. 0.5확률로 action을 선택하라고 되어있어.
이거 어떻게 계산할래?
몰라
아직 안배웠거든
다음에 배워
// Bellman Expectation Equation
이번에도 벨만 수식을 통해 풀 수 있어. 이게 2개가 있는 데 , 벨만 기대 수식과 벨만 최적 수식이 두개가 있어
지금은 벨만 기대 수식이야.
기대값에 관한 것이야.
첫번째 수식을 보면 state-value function이야. MRP랑 똑같지?
근데 파이(Policy)가 추가된 것이야.
두번째 수식은 action value function인데, 비슷~ 한데. 이제 q니까 당연히 원래 v로 되어있던 것도 q로 바꿔줘야지.
어려운거 아님.
이것도 아까처럼 한방에 풀 수가 있어
그래서 이것도 수식을 먼저 표현한 뒤에 행렬로 표현할거야.
// Bellman Expectation Equation for Vㅠ
우선 state value function은 action value function으로 나타낼 수가 있어.
value function은 다음 state로 갈려면 action을 해야하잖아? 지금은 MDP니까.
그럼 그 action을 할 확률이 있어야겠지? 그게 ㅠ(a|s)야
그리고 그 다음 state value function이어야겠지? 근데 생각해보면 한번 action을 한 후의 value function이 q(s,a)였잖아?
그니까 저렇게 표현이 가능한거야.
// Bellman Expectation Equation for Qㅠ
마찬가지로 q함수(action value function)도 state value function으로 표현할 수가 있어
우선 q함수는 분명 말했다시피 action을 한번 하고 나서의 value function이라고 했잖아?
MDP에서는 action을 하면 Reward를 받는다고 했지?
그래서 state S에서 action a를 햇을 때 받을 보상이 Ras가 되는거야. 이걸 왜 받냐고 물어본다면, 다시 말하지만 state value function으로도 표현 가능하다는 것을 말해주는 거야. state value function같은 경우에는 s에서 파이를 따라갔을 때의 value function이고 action value function은 s에서 a를 한번 한 이후의 value function이잖아.
그니까 한번 했을 때가 보상인 Ras이고, 그 다음 에 나오는 discount는 뭐 원래 있는 거고 그 뒤는 다시 q(s+1,a+1)이였잖아?
그니까 그걸 state value function으로 표현하면 s에서 a를 했을 때 s'로 가는 확률 * s' 에서의 value function으로 나타낼 수가 있는 거지.
discount는 더 설명 안할게.
그리고 좀 더 추가설명을 해주자면,
지금 그림을 자세히 보면, value function은 흰원 즉 state 에서 시작을 해.
근데 q 함수는 검정원 즉 action에서 시작을 해.
좀 감이 올거야 이제.
state value function은 이 state를 가면 얻을 수 있는 value 함수인거고,
action value function은 이 action을 선택하면 얻을 수 있는 value 함수인거야.
왜냐면 검정원이 action이잖아? 이미 action을 했으니까 보상은 받고, 그 다음에 갈 수 있는 state가 지금 2개지? 분명 더 많겠지만 무튼 여기서는 2개야. 그럼 그 state에 가면 얻을 수 있는 value function은 state value function인거잖아
이렇게 말해도 모르겠다면 lecture 1을 다시 복습해보던지 좀 더 깊게 이해를 해보려고 해봐.
나도 이정도가 한계야 ㅠ 이게 틀렸다면 꼭 얘기해줘. 계속 이해하려고 하다보니 내가 틀렸을 수도 있어.
// Bellman Expectation Equation for vㅠ(2)
그럼 이제 아까 Vㅠ 두번째 버전이야.
한 층 더 확장이 되었지?
별건 없고 아까 state value function를 q로 표현할 수 있었다고 했잖아?
그리고 q를 state로 표현했엇지?
q자리에 q를 state로 표현한 것을 그대로 가져다가 넣은 것이야.
이렇게 하는 이유는 행렬로 표현하기 위함이야.
// Bellman Expectation Equation for qㅠ(2)
이건 q의 두번째 버전?
무튼 이것도 똑같이 넣은 거야.
// Example : Bellman Expectation Equation in Student MDP
이제 계산 할 수 있어.
7.4 에서의 state value function을 구해보자.
Vㅠ(2)를 그대로 적용해보는 거야.
우선 아까 policy 즉 action을 선택하는 기준은 그냥 0.5라고 정해놓은 상태야.
지금 7.4에서 할 수 있는 action은 2개지? pub이랑 study야. 물론 pub은 3갈래로 나뉘어져.
우선 쉬운 거부터 하자. 위 식을 계속 보면서 따라가봐. 지금 식에서 A = 2야. a 가 2개인거지.
그럼
1. Study
ㅠ(a|s) : 이건 Policy 지? 0.5
Ras : 이건 10이지?
discout : 1
Pass' : s에서 a를 통해 s'로 갈확률은 안봐도 1이네.
v(s')는 0이지?
10 + discount * pass' * v(s') 는 10이지?
그니까 0.5 * 10이 되겠네
이제 다음
2. Pub
ㅠ(a|s) : 이건 Policy 지? 0.5
Ras : 1
discout : 1
Pass' : s에서 a를 통해 s'로 갈확률은 지금 3개로 갈리지? 0.2일때는 value가 -1.3이고 0.4확률로 가는 state는 2.7이고 , 본인한테 오는 거는 0.4 확률로 7.4야. 이걸 다 서로 곱해서 더하자. 그럼
저 식이 나오는 거야.
이 두개를 더해주면 7.4 나와. 직접 해봐.
// Bellman Expectation Equation (Matrix Form)
MRP에서 소개한 것 처럼 이것도 행렬식으로 표현할 수 잇어.
행렬식으로 표현한 것을 바로 계산될 수 있도록 바꾼 게 두번째 식이야.
이것 또한 당연히 큰 문제는 잘 못해.
그리고 아직 우리는 value만 다뤘어.
무슨 얘기냐면 MDP는 Policy가 있잖아. 근데 지금 이건 다 policy가 정해졌을 때를 말한 거란 말이야.
그럼 action을 결정을 어떻게 해야할 지에 대해서는 말하지 않았잖아.
이제 그걸 말할거야
// Optimal Value Function
지금까지는 주어진 어떤 Policy인 파이가 있을 때 value를 구한거야.
근데 주어진 게 없으면 어떻게 할지 생각해 봣어?
여기서 개념 하나 더 나와.
파이라고 부르는 ㅠ은 정해진 Policy를 말해
*는 무한의 Policy중에 가장 좋은 Policy를 말해.
여기서도 MDP이기 떄문에 당연히 value function이 두개가 나오는 데, optimal state-value function ( v*(s) ) 이랑 optimal action-value function ( q*(s,a)가 나와.
optimal state-value function은 모든 policy 중에 value fucntion이 가장 좋은 애야.
optimal action-value function은 모든 policy중에 action value function이 ㄱ자ㅏㅇ 좋은 애야.
모든 Policy는 당연한 거 아니야? 라고 하겠지만 여기서 말하는 모든 policy는 가지고 있는 policy를 말해.
그래서 이걸 알면 MDP 문제를 풀었다고 한대.
그리고 value function은 벨만 수식으로 푼다고 했는 데 아까 MDP에서는 벨만 수식 2개가 있다고 했지?
bellman expectation equation이랑 bellman optimization equation이라고 햇지? 기대랑 최적 수식.
이 optimal value function은 optimization 수식으로 풀수 잇는 거야.
// Example: Optimal Value Function for Student MDP
이거는 discount가 1일때 Optimal value function을 나타낸거야. optimal state-value function이겠지.
그래서 State에 빨간 글씨가 써져 잇는 게 보이지?
우선 이런게 최적의 state value function이다~ 라고 알아두고
// Example : Optimal Action value function for student MDP
이건 action value 의 최적이야. 뭐 이렇다고만 알아둬
// Optimal Policy
자 아까 최적의 policy를 구한다고 했잖아.
그럼 어떤 policy가 더 좋은 지를 구별 할 수 있어야 있어야하잖아? 이걸 partial ordering이라고 하는 데,
모든 State 에 대해서!!! v(s)가 더 큰 쪽이 더 좋은 policy래.
항상 비교를 정의할 수 있는 것은 아니기도 하고..
그리고 증명이 된건데 최적의 policy는 존재한다네.
최적의 policy는 최적의 optimal value function을 달성하고 optimal action value function을 만족한다네.
// Finding an Optimal Policy
그럼 이제 Optimal Policy를 찾아보자.
여기서 말하는 것은 optimal policy는 q*를 하나 찾는 순간 무조건 찾아진대. q*는 위에서 말했다시피 action value function이야. q*는 state에서 어떤 액션이 제일 좋은 지 알려줘. 왜냐면 s에서 a를 했을 때 value function이니까 어떤 a가 가장 좋은 value function인지 알려준다는 거잖아.
만약에 q*를 하면 1이라고 하고 나머지는 0이라고 하면, optimal policy는 당연히 q*를 따라가는 거야. 맞지? 나머지는 다 0이니까 안갈거아니야
1을 따라간다는 것은 결국 q*를 따라간다는 것과 마찬가지잖아. 그럼 결국 그 q*를 따라가는 policy는 optimal policy가 되는 거지.
근데 여기서 deterministic optimal policy가 어느 MDP에서 있다고 하네?
원래 policy 자체가 (각 acton에 대해) 확률이잖아. 근데 이 확률을 위와 같이 0과 1로 나타내면 deterministic이래. 왜냐면 어떤 state에서 q* 즉 1이라고 하면 그 state는 더이상 stochastic(확률적) 한게 아니잖아? 어디로 갈 지 정해져 잇으니까.
뭐 어려워도 일단 알아둬 그냥. q*를 알면 q*를 따라가기만 하면 되니까 넌 문제를 풀었어 이런 의미야
// Example : Optimal Policy for Student MDP
저 빨간 색이 deterministic Optimal Policy야. 너무 쉬워서 별거 아닌거 같지?
도로로 생각하면 수많은 도로중에 가장 최적의 길을 우리에게 알려주는 거와 같아. 그건 안쉽잖아. 너가 부산에서 출발해서 중국 상하이까지 도착하는 도로를 계산한다고 생각하면 더 커지지. 무튼 이렇게 생각하면 저 빨간 줄을 구하기는 상당히 어려운 것이지.
바둑은 상태자체가 10의 51승인가 뭔가 그랬어.
어떻게 보면 사람도 optimal policy를 구하려고 해. 우리도 게임을 하거나 그럴 때 어떻게 하면 이길까 이렇게 고민하고 그러잖아. 그거야.
// Bellman Optimality Equation for V*
이제는 Optimal policy에 벨만 수식을 적용할 거야.
별거 없어.
다 똑같애. 근데 max만 적용했을 뿐이야. 이제 좀 익숙해 져야지.
State s에서의 Optimal state value function은 q*를 알면 된다. q마다 a들이 잇을 텐데 그중에서 가장 좋은 a를 선택하면 된다. 이거야.
혹시 이해가 안가나?
state마다 할수 잇는 action이 여러개 있짢아.
그 action을 q로 표현할 수 잇는 거잖아.
// Bellman Optimality Equation for Q*
q*도 똑같애. v*를 알면 되는 거야. 여기선 max는 아니지만?
// Bellman Optimality Equation for V* (2)
아까와 비슷하지?
똑같이 한거야
바뀐거 없어 *만 햇을 뿐
근데 아까 우리가 이런 거를 행렬로 표현했잖아. 맞지? 그게 되는 이유는 linear하기 때문이야. 그래서 막 이리저리 넘겼더니 수식 하나로 딱 됬었잖아? 그래서 한방에 풀 수 있다고 했지
근데 이거는 max가 붙기 때문에 linear하지 않아서 식을 전개해서 풀수가 없어. 이게 bellman expectation equation이랑의 차이점이야.
// Bellman Optimality Equation for Q* (2)