강화학습: 기초
마코프 과정 Markov Process 상태 상태 한 상태에서 다른 상태로 변화는 확률적으로 결정 변화 확률은 직전 상태에 따라 달라짐 직전 상태 이전의 과거는 영향X
마코프 과정 수업 잠 밥 과제
마코프 보상 과정 Markov Reward Process 각 상태에 보상(reward)이 있음
마코프 보상 과정 수업 잠 -10 +10 밥 과제 +5 -5
Return 보상(reward)의 할인된(discounted) 합 예를 들어 할인이 0.9일 경우 수업 잠 밥: -10 + 0.9*10 + 0.92*5 = 3.05 밥 잠 수업: +5 + 0.9*10 - 0.92*10 = 5.9
가치 함수 현재 상태에서 앞으로 Return의 기대값
벨만 방정식 Bellman equation 현재 상태의 가치 = 현재 상태의 보상 + 할인 * 다음 상태의 가치
마코프 결정 과정 Markov Decision Process 마코프 보상 과정 + 행동 상태와 행동에 따라 변화 확률과 보상이 결정
마코프 결정 과정 10% 에라 모르겠다 90% 수업 잠 20% 힘내자! 80%
마코프 결정 과정 -10 에라 모르겠다 5 수업 잠 -10 힘내자! 5
정책 policy 현재 상태에서 어떤 행동을 할 확률
정책 에라 모르겠다 60% 수업 40% 힘내자!
가치 함수 현재 상태에서 특정 행동을 할 때 앞으로 Return의 기대값 벨만 방정식
가치 함수 상태 가치 함수: v 상태-행동 가치 함수: q
최적의 정책 모든 상태에서 가치 함수의 값이 다른 정책보다 높은 정책 바꿔 말하면 모든 상태에서 기대 Return이 다른 정책보다 높은 정책
결정론적 정책 현재 상태에서 최선의 행동을 100%한다
벨만 최적 방정식 현재 상태의 최선의 v = 최선의 행동을 할 때 q 현재상태의 최선의 q = 다음 상태의 v의 기대값
V의 벨만 최적 방정식 현재 상태의 최선의 v는 최선의 행동을 하고 난 상태의 v들의 기대값
Q의 벨만 최적 방정식 현재 상태에서 최선의 q는 다음 상태에서 최선의 행동을 할 때 q들의 기대값
벨만 최적 방정식을 푸는 방법 푸는 공식이 없음 반복해서 푸는 방법 Value Iteration Policy Iteration Q-learning SARSA
동적 계획법 dynamic programming 문제를 작은 문제들로 나누어 푸는 방법
Iterative Policy Evaluation 모든 상태의 가치를 초기화한다 벨만 방정식을 이용해 모든 상태의 가치를 수정 2의 과정을 반복한다
Policy Iteration 모든 상태의 가치를 초기화한다, 초기 정책은 무작위 행동 벨만 방정식을 이용해 모든 상태의 가치를 수정 각 상태에서 가장 가치가 큰 행동을 하도록 정책을 수정 2-3의 과정을 반복
예시: 그리드월드 4×4의 상태 할인 없음(1) 행동은 동서남북 4가지 항상 원하는 결과(변화확률 = 1) 왼쪽위 또는 오른쪽 아래에 도달하면 종료
예시: 그리드월드
Value Iteartion 모든 상태의 가치를 초기화한다 벨만 최적 방정식을 이용해 모든 상태의 가치를 수정 2의 과정을 반복
Model-free 그리드월드는 변화 확률이 알려져 있음(p = 1) 변화 확률을 모를 경우 Model-free Monte-Carlo Temporal-Difference
Value function approximation 그리드월드는 상태의 수가 적음(16개) 상태의 수가 많아지면 value function approx. 기계학습을 이용해 가치 함수를 예측