숨 니야 2018 . 1 . 1 . 01 : 22 
 이전 포스팅 에서 는 bellman eqn . 을 이용 한 dynamic programming , policy iteration 과 value iteration 에 대해 알아보 았 습니다 . 하 지만 DP 는 우리 가 machine learning 에서 다루 는 learning 이 아니 라 planning 입니다 . 따라서 , 계산 복잡도 가 state 의 크기 3 제곱 에 비례 하 기 때문 에 grid world 보다 차원 의 크기 도 크 고 state 가 무수히 많 은 실제 문제 에 적용 하 기 에 는 많 은 한계 가 있 습니다 . 이 를 보완 한 것 이 , env . 의 model 을 몰라도 trial and error 를 시행 해 보 며 env . 과 상호 작용 을 통해 알 아 가 는 , 강화 학습 입니다 . env . 으로부터 model 을 learning 하 는 것 입니다 . 그래서 강화 학습 은 full - width backup 이 아닌 sample backup 입니다 . sample backup 은 이어지 는 모든 state 들 을 고려 하 지 않 고 그 중 에서 sampling 을 통해 한 길 만 선택 해서 가 보 는 것 입니다 . 그리고 이 를 통해 value func . 을 update 하 게 됩니다 . 
 DP 에서 도 마찬가지 로 강화 학습 에 는 선택 된 정책 을 따를 때 의 value func . 을 sample backup 으로 구하 는 prediction 과 이 를 통해 policy 를 update 하 는 control 이 있 습니다 . prediction 의 종류 에 는 Monte - Carlo prediction 과 Temporal difference prediction 가 있 고 control 에 는 SARSA 와 Q - learning 이 있 습니다 . 이번 포스팅 에서 다룰 내용 은 Monte - Calro Method 으로 어떻 게 prediction 과 control 하 는지 에 대해 다루 겠 습니다 . 
 Monte - Carlo 의 기본 적 인 concept 을 이해 하 기 위해 이 방법 으로 원주율 을 구하 는 예제 를 먼저 설명 하 겠 습니다 . 
 1 ) ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 ) 로 이루어진 좌표 상 에 임의 의 점 ( x , y ) 를 sampling 한다 . 
 2 ) sampling 한 점 이 중심 이 ( 0 , 0 ) 이 고 반지름 이 1 인 사분원 내 에 속하 는 점 인지 를 판단 한다 . 
 3 ) 이 과정 을 충분히 반복 한다 . 
 < Fig 1 . Estimate π by Monte - Carlo Approx . > 
 image source : https : / / en . wikipedia . org / wiki / Monte _ Carlo _ method 
 Indicate func . I 는 주어진 조건 이 만족 하 면 1 , 아니면 0 을 반환 하 는 함수 입니다 . Monte - Carlo 의 핵심 은 " 추정 하 고 싶 은 값 을 random sampling 을 통해 근사 한다 " 정도 로 이해 하 시 면 충분 합니다 . 
 그러면 강화 학습 에서 의 Monte - Carlo 의 의미 를 알아보 기 위해서 , Sutton 교수 님 책 에서 Monte - Carlo 에 대해 언급 된 부분 을 보 겠 습니다 . 
 Monte - Carlo 는 random 한 operation 으로 estimate 하 는 방법 이 라고 설명 하 고 있 습니다 . 그리고 강화 학습 에서 는 complete returns 를 averaging 하 는 것 이 라고 합니다 . 이 뜻 은 무엇 일까요 ? 
 Monte - Carlo vs Temporal Differ . 
 intro 부분 에서 prediction 의 종류 에 는 Monte - Carlo 방법 과 Temporal difference 방법 이 있 음 을 언급 했 습니다 . 이 둘 의 가장 큰 차이 는 value func . 을 estimate 하 는 방법 ( 시기 ) 입니다 . 전자 는 episode 가 끝 날 때 마다 , 즉 , state sampling 결과 선택 된 state 들 을 끝 까지 가 보 고 update 를 합니다 . 후자 는 time - step 마다 한 단계 씩 update 합니다 . 이렇게 되 면 Monte - Carlo 방법 은 terminal state 까지 step 별 로 얻 은 reward 를 모두 저장 하 고 나 서 terminal state 에서 는 이 를 바탕 으로 state 들 의 value func . 들 을 구하 게 됩니다 . 이렇게 Monte - Carlo 방법 으로 true value func . 을 얻 는 과정 을 Monte - Carlo Prediction 이 라고 합니다 . 
 이제 " averaging complete returns " 의 의미 를 생각 하 볼 차례 입니다 . value func . 을 얻 을 때 agent 는 sampling 한 state 를 골라 가 며 terminal state 까지 갑니다 . 그리고 이때 받 은 reward 들 을 저장 해 두 었 다가 이 를 시간 순서 대로 discounting 한 것 이 바로 value func . 입니다 . DP 에서 는 이 를 Bellman eqn . 으로 구했 고 계산 가능 한 형태 로 바꾸 어 풀 었 는데 , Monte - Carlo 방법 에서 는 이 reward 들 의 합 ( discounted ) 의 평균 으로 value func . 을 근사 하 게 됩니다 . 우리 는 MDP 를 다룰 때 , 미래 에 받 을 reward 들 을 현재 가치 로 discounting 하 여 모두 더 한 값 을 return 이 라고 정의 했 습니다 . 또한 , value func . 은 state s 에서 의 return 의 기댓값 이 라고 정의 했 습니다 . Monte - Carlo prediction 은 한 episode 를 마치 고 얻 은 return 들 의 평균값 으로 value func . 를 근사 하 고 이 를 반복 해서 true value 를 찾 자는 아이디어 입니다 . 
 < Fig 2 . The returns of each states in 1 episode > 
 위 그림 은 임의 의 policy 에 대해 첫 번 째 state 부터 terminal state 까지 의 한 episode 를 나타낸 것 입니다 ( 시간 t 에 대한 첨자 는 생략 했 습니다 ) . 그리고 state 를 이동 할 때 마다 얻 은 reward 들 을 통해 , 각 state 별 return 값 G ( s ) 를 구할 수 있 습니다 . 우리 는 이전 포스팅 에서 true value func . 을 위해서 여러 iteration 을 통해 value func . 을 update 하 는 것 을 배웠 습니다 . Monte - Carlo 도 마찬가지 로 여러 episode 를 진행 하 며 해당 state 를 지나가 는 episode 에서 return 값 들 을 모두 구해서 산술 평균 을 내줍니다 . 이러 한 return 값 들 이 episode 반복 을 통해 여러 값 들 이 모이 면 true value func . 으로 근사 할 수 있 습니다 . 이 를 식 으로 나타내 면 아래 와 같 습니다 . 
 N ( s ) 는 total episode 동안 state s 를 방문 한 횟수 , G i ( s ) 는 episode i 에서 state s 의 return 값 입니다 . 
 이 식 을 하나 의 state 에 대해서 만 생각 해 보 겠 습니다 . state 에 대한 notation 을 없애 고 n 개 의 return 값 을 통해 얻 은 value func . 은 Vn + 1 이 라고 쓸 수 있 고 , 가장 최근 얻 은 return 을 Gn 이 라고 한다면 , 아래 와 같이 decompose 시킬 수 있 습니다 . 
 그리고 이 식 을 조금 고쳐 쓰 면 다음 과 같 은 관계 를 얻 을 수 있 습니다 . 
 이 식 은 새로운 return 값 을 받 았 을 때 , Vn 에서 Vn + 1 로 value func . 을 update 하 는 방법 을 나타냅니다 . 이렇게 return 값 을 모두 모으 고 한 번 에 평균 을 내 는 것 이 아니 라 새로운 return 값 을 얻 을 때 마다 update 하 기 때문 에 아래 와 같 은 incremental mean 의 식 으로 나타낼 수 있 습니다 . 
 여기 서 1 / n 을 step - size 라고 하 고 보통 α 로 놓 습니다 ( 이 α 를 위 식이 수렴 하 게 끔 하 는 constant 로 둘 수 도 있 습니다 ) . 그리고 이 에 곱해진 ( Gn - Vn ) 를 오 차 라고 합니다 . 그러면 이 를 통해서 우리 는 아래 와 같이 value func . 이 G ( s ) 라는 target 으로 ( α ㆍ오차 ) 만큼 update 하 여 다가 간다는 것 을 알 수 있 습니다 . 다음 포스팅 에서 다룰 TD ( Temporal - difference ) prediction 에서 도 목표 가 G ( s ) 가 바뀔 뿐 , 개념 은 같 습니다 . 
 < Fig 3 . update value func . to return > 
 First - visit MC or Every visit MC 
 하나 의 episode 를 마치 면 episode 동안 진행 해 왔 던 state 들 마다 return 값 이 존재 하 게 됩니다 . 이때 , 중복 방문 에 대한 return 값 을 처리 하 는 방식 에 따라 first - visit MC 와 every - visit MC 로 나누 어 지 는데 , first - visit MC 는 state 에 첫 번 째 방문 했 을 때 의 return 값 만 취하 고 두 번 째 이후 는 고려 하 지 않 습니다 . every - visit MC 는 이 와 반대 로 방문 할 때 마다 바뀐 return 값 으로 계산 하 는 것 입니다 . 두 방법 모두 true value func . 으로 수렴 하 지만 지금껏 다룬 내용 은 모두 first - visit MC 를 채택 하 여 다루 었 습니다 . 
 DP 에서 Policy Iteration 은 policy evaluation 과 ( greedy ) policy improvement 로 나누 어 집니다 . 여기 서 policy evaluation 에 MC 를 이용 하 면 Monte - Carlo policy Iteration 이 됩니다 . 
 하 지만 MC policy Iteration 은 다음 과 같 은 문제점 들 이 존재 하 는데 , 이 를 해결 한 것 이 Monte - Carlo Control 입니다 . 
 1 ) Value func . 의 model - based 
 2 ) Local optimum 
 3 ) Inefficiency of policy evaluation 
 MC control 은 위 문제점 의 solution 들 을 어떻 게 algorithm 에 반영 하 였 는지 살펴보 겠 습니다 . 
 1 ) The attribute of value func . : model - based 
 MC 로 policy evaluation 을 하 는 부분 에서 value func . 을 이용 합니다 . MC 를 이용 하 는 것 은 model - free 의 속성 을 이용 하 기 위해 도입 했 지만 value func . 을 사용 하 게 되 면 policy 를 improve 할 때 , model 을 알 아야 만 합니다 . 따라서 , value func . 대신 에 action - value func . ( q - func . ) 을 이용 하 면 이 를 해결 할 수 있 습니다 . 우리 가 Ch . 3 에서 배운 action - value func . 의 식 에 model 이 있 어서 , 이 말 이 이해 가 안 가실 수 도 있 는데 이렇게 생각 해 보 겠 습니다 . 
 value - func . 을 이용 할 경우 , agent 가 episode 마다 얻 은 reward 들 로 state 의 return 값 을 계산 하 고 이 를 평균 을 취해 state 마다 value func . 들 을 계산 해 놓 습니다 . 이 과정 이 MC policy evaluation 이 고 이 를 통해 true value func . 을 근사 하 여 얻 을 수 있 습니다 . 하 지만 improve 과정 에서 policy 를 update 할 때 아래 의 식 을 이용 하 는데 reward 와 state transition prob . 를 알 아야 합니다 . Ch . 4 Policy Iteration 의 policy improvement 부분 에서 q . func . 을 이용 해서 policy 를 update 했 습니다 . 이때 , model 이 쓰이 기 때문 에 q - func 의 식대 로 model 필요 한 건 맞 습니다 . 
 action - value func . 을 이용 할 경우 , return 이 아닌 agent 가 episode 마다 random 하 게 움직이 며 얻 은 reward 들 그리고 state transition prob . 를 통해서 action - value func . 을 계산 할 수 있 습니다 . 이렇게 되 면 policy 를 improve 할 때 , model 을 굳이 알 지 못해도 이미 전 과정 에서 q - func . 을 이용 함 으로써 model 의 정보 가 다 담겨 있 습니다 . 따라서 improve 할 때 는 이 를 선택 만 해 주 면 되 는 문제 이 므로 model 을 몰라도 improve 할 수 있 습니다 . 정리 하 자면 model - free 하 다는 개념 은 policy 를 improve 할 때 의 관점 이 고 , q - func . 자체 는 model 을 알 아야지 만 구할 수 있 는 것 은 맞 습니다 . 다만 trial and error 의 과정 속 에서 모든 정보 가 q - func . 에 담겨 있 으므로 policy improvement 의 과정 에서 는 model - free 합니다 . 
 Policy 를 improve 하 는 방법 으로써 greedy policy improvement 를 소개 했 습니다 . 하지만 이 방법 은 현 상황 에서 제일 좋 은 것 만 찾 는 매우 근시안 적 인 방법 이 라 local optimum 에 빠지 는 경우 가 생깁니다 . 경사로 의 공 을 아래 로 옮기 는 일 을 agent 가 수행 한다고 했 을 때 , 어떤 t 시점 에서 의 slope 가 t - 1 시점 에서 의 slope 보다 계속 작아지 는 쪽 으로 옮기 는 action 을 취하 면 됩니다 . 하지만 , 중간 에 움푹 패인 골짜기 를 만나 게 된다면 더 이상 진행 을 못 하 게 되 고 , 이 것 이 local optimum 에 빠진 현상 입니다 . 그래서 우리 는 골짜기 의 공 을 한번 흔들 어서 빼내 어 다시 경사 로 아래 로 굴려 줘야 합니다 . 이 작업 을 가능 하 게 하 는 것 이 ε - greedy policy improvement 입니다 . ε 의 확률 만큼 exploration 을 하 고 , 1 - ε 의 확률 만큼 empirical mean , 즉 , 지금 까지 observe 한 것 중 의 최적 을 택하 는 방법 입니다 . exploration 은 현재 의 optimal 이외 의 다른 무언가 를 찾 기 위해 random 하 게 action 을 선택 하 는 것 을 의미 합니다 . 
 DP 에서 Policy Iteration 의 과정 을 optimal policy 라는 전제 와 함께 q - func . 을 이용 하 여 단 한 번 만 evaluation 하 는 , Value Iteration 이 있 었 습니다 . 마찬가지 로 MC control 에서 도 MC policy iteration 에서 의 evaluation 을 단 한 번 만 진행 하 게 됩니다 . 아래 그림 은 DP 의 Policy iteration 과 MC control 을 비교 한 그림 입니다 . 왼쪽 이 Policy Itearation , Monte - Carlo Control 입니다 . 
 < Fig 4 . Policy Iteration vs Monte - Carlo Control > 
 이제 는 https : / / github . com / rlcode / reinforcement - learning - kr ( Ref . [ 2 ] , [ 3 ] ) 에 있 는 code 를 커 스터 마이 징 해서 MC control agent 를 구현 해 보 겠 습니다 . 먼저 환경 은 5 X 5 gird - world 로써 아래 와 같 습니다 . 
 < Fig 5 . env > 
 초록색 영역 을 피해 서 Goal state 로 가 는 환경 입니다 . agent 가 value func . 을 table 로 저장 하 고 episode 가 끝난 후 에 얻 은 return 값 으로 이 를 update 합니다 . 그리고 ε - greedy method 를 사용 하 여 action 을 택 합니다 . 중간 중간 episode 마다 취한 action 을 보 면 episode 마다 step 의 수 가 다양 합니다 . 부연 설명 은 code 에 있 는 주석 으로 대체 하 겠 습니다 . 
 이번 장 부터 는 강화 학습 의 시작 이 라고 말 할 수 있 습니다 . 하지만 , MC 의 방법 은 episode 가 무한히 길 다면 update 하 기 어려운 단점 이 존재 합니다 . 다음 포스팅 은 이 문제 를 해결 할 수 있 는 Temporal difference learning 에 대해 다루 겠 습니다 . 
 [ 1 ] https : / / dnddnjs . gitbooks . io / rl / content / monte - carlo _ methods . html 
 [ 2 ] 이웅 원 , 양 혁 렬 , 김건우 , 이영무 , 이 의 령 . " 파이썬 과 케 라스 로 배우 는 강화 학습 ". 위키 북스 . p . 110 - 124 
 [ 3 ] https : / / github . com / rlcode / reinforcement - learning - kr / tree / master / 1 - grid - world / 3 - monte - carlo 
 2019 . 01 . 23 17 : 23 댓글 주소 수정 / 삭제 댓글 쓰 기 
 숨 니야 2019 . 04 . 11 19 : 09 신고 댓글 주소 수정 / 삭제 
 답변 이 늦 었 습니다 ! 요즘 계속 진로 고민 도 있 고 여러 시도 도 해 보 느라 블로그 관리 에 소홀 해 졌 네요 . 우선 좋 은 피드백 감사 합니다 ! 수정 해 주 신 부분 반영 하 여 accuracy 가 올라간 것 을 확인 하 였 습니다 . 
 블로그 에 오 셔서 시간 내주 셔서 피드백 주 셔서 감사 합니다 
 궁금 2019 . 12 . 18 08 : 09 댓글 주소 수정 / 삭제 
 소스 코드 중 아래 부분 에서 reversed 는 왜 해 주 는 것 인가요 ? 게임 이 종료 된 시점 부터 역순 으로 Reward 및 Value 를 계산 하 던데 정 방향 ( 0 . 0 ) 부터 시작 하 면 안 되 나요 ? 
 for sample in reversed ( self . memory ) : 
 2019 . 01 . 23 17 : 45 댓글 주소 수정 / 삭제 댓글 쓰 기 
 감사 합니다 2019 . 02 . 19 09 : 50 댓글 주소 수정 / 삭제 댓글 쓰 기 
 혼자 공부 하 던 중 이해 가 안 되 서 너무 힘들 었 는데 좋 은 글 보 고 시원 하 게 해결 하 고 갑니다 ~ 감사 합니다 ~^^ 
 도움 이 되 었 다니 감사 합니다 ! 좋 은 하루 되 세요 : ) 
 asdf 2019 . 04 . 16 11 : 02 댓글 주소 수정 / 삭제 댓글 쓰 기 
 안녕 하 세요 너무 좋 은 블로그 포스팅 감사 합니다 : ) 설명 을 너무 잘 해 주 셨 어요 . 
 다름 이 아니 라 , value funtion update 유도 하 는 부분 에서 < fig 2 > 부분 아래 에 있 어서 
 ' 그리고 이 식 을 조금 고쳐 쓰 면 다음 과 같 은 관계 를 얻 을 수 있 습니다 . ' 라는 말 의 아래 2 번 째 식 이 
 1 / n ( G _ n + ( n - 1 ) * V _ n ) 이 오타 가 난 것 같 아서 댓글 달 아 봅니다 . ㅎ 
 숨 니야 2019 . 04 . 23 22 : 46 신고 댓글 주소 수정 / 삭제 
 반갑 습니다 : ) 우선 도움 이 되 었 다고 하 니 감사 합니다 ㅎㅎㅎ 
 오타 가 났 다고 하 시 는 부분 ( 아래 서 두 번 째 식 ) 은 바로 위 에 있 는 식의 ( n - 1 ) Vn 부분 을 전개 한 후 정리 한 것 입니다 . n * Vn - Vn 
 혹시 제 가 잘못 이해 한 부분 이 있 나요 ? 
 asdf 2019 . 05 . 01 10 : 31 댓글 주소 수정 / 삭제 
 아 넵 그 부분 은 맞 는 것 같 습니다 ! 
 숨 니야 2019 . 05 . 19 04 : 07 신고 댓글 주소 수정 / 삭제 
 아아 맞 습니다 말씀 해 주 신 " 아래 에서 4 번 째 식 " 이 잘못 되 었 네요 
 V _ n 앞 에 붙 은 n - 1 을 없애 야 할 것 같 습니다 . 
 이 부분 을 아 에 삭제 하 고 바로 아래 식 으로 유도 되 는 거 로 생각 해 주 시 면 되 겠 네요 . 
 고쳐 놓 겠 습니다 . 좋 은 피드백 감사 합니다 : ) 
 abc 2019 . 11 . 09 08 : 47 댓글 주소 수정 / 삭제 댓글 쓰 기 
 좋 은 글 감사 합니다 . 다른 책 보 고 있 는데 잘 이해 가 안 되 고 있 었 는데 조금 은 이해 가 갑니다 . 
 예 제 에 대해 질문 이 있 습니다 . 
 예제 에서 최종 적 으로 얻 은 value function 이 아직 수렴 되 지 않 은 것 이 지요 ? 
 프로그램 에서 출력 된 value function 대로 하 면 골 을 찾 지 못하 는 것 같 습니다 . 예 를 들 어 [ 0 , 0 ] 에서 시작 한다면 다음 state 는 주변 에서 가장 큰 값 을 가지 는 아래 칸 [ 1 , 0 ] 으로 가 게 되 고 , 다음 에 는 다시 위 칸 [ 0 , 0 ] 으로 가 게 됩니다 . 즉 무한 반복 을 하 게 될 것 같 습니다 . 
 숨 니야 2019 . 11 . 15 17 : 52 신고 댓글 주소 수정 / 삭제 
 네 맞 습니다 수렴 하 지 않 은 예제 로 process 에 중점 을 두어 설명 했 습니다 
 synops 2019 . 11 . 15 17 : 26 댓글 주소 수정 / 삭제 댓글 쓰 기 
 마지막 작성 하 신 코드 에서 
 memory 를 reversed 하 게 반복 하 면서 visit 되 었 으면 action value func 를 update 하 지 않 으시 는데 
 뒤 에 부터 조사 하 면 first visit 이 라고 할 수 있 나요 ? 최초 에 등장 한 state 가 아니 라 가장 마지막 에 등장 한 state 의 기대 값 으로 업데이트 를 할 것 같 은데 
 first visit 이 꼭 첫 번 째 가 아니 라 에피소드 안 에서 state 가 등장 한 걸 1 번 만 고려 하 면 성립 하 는 건가요 ? 
 숨 니야 2019 . 12 . 30 13 : 07 신고 댓글 주소 수정 / 삭제 
 생각 해 보 니 episode 를 뒤집 어서 reversed 로 tracking 하 면 , first - visit 이 아니 게 되 는군요 정 방향 으로 value 를 계산 하 는 것 이 맞 다고 생각 합니다 . 
 다만 first - visit 의 의의 가 단순히 하나 의 value 값 을 찾 는 것 에 의의 가 있 다면 reversed 로 한 last - visit ( 임의 로 명명 하 겠 습니다 ) 은 똑같이 하나 의 value 값 을 찾 되 , 최근 방문 한 value 가 더 가치 있 다고 생각 할 때 사용 하 면 좋 을 것 같 네요 . 
 궁금 2019 . 12 . 18 10 : 50 댓글 주소 수정 / 삭제 댓글 쓰 기 
 윗 질문 과 유사 한 건데 , reversed 방식 으로 Value 계산 을 하 는 이유 가 있 나요 ? ( 0 , 0 ) 시작점 부터 Discount 해서 Value 계산 하 는 것 과 차이 가 있 는지 궁금 합니다 . 
 바로 위 synops 님 께 리플 한 것 참조 해 주 시 고 다른 의견 있 으시 면 또 주 세요 : )