03장 강화학습의 기초 2: 그리드월드와 다이내믹 프로그래밍
- 다이내믹 프로그래밍 : 작은 문제가 큰 문제 안에 중첩돼 있는 경우, 작은 문제의 답을 다른 작은 문제에 이용함으로써 효율적으로 계산하는 방법.
- 다이내믹 프로그래밍은 강화학습의 근간이 되었고, 다이내믹 프로그래밍의 한계를 벗어나고자 강화학습을 사용.
- 강화학습과 다이내믹 프로그래밍 둘다 벨만 방정식을 푸는 방법의 일종.
- 가치함수란 현재의 정책을 따라갔을 때 받을 보상에 대한 기댓값.
1. 정책 이터레이션
1-1 정책 평가
$$ v_{k+1} = \sum_{a \in A}\pi(a|s)(r_{(s,a)}+\gamma v_{k}(s')) \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \\ \scriptsize{k번째 가치함수를 통해 k+1번째 가치함수를 계산} \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$$
-> 1회차 가치함수로 구한 수치들로 2회차 가치함수 수치들을 구하고. 2회차 가치함수 수치들로
3회차 수치들을 계산..... k회차 가치함수로 k+1회차 가치함수 수치들을 계산.
->이전 회차의 수치들과 차이가 없어지면. 계산 끝.?
1-2 정책 발전
1-2-1 탐욕 정책 발전(Greedy Policy Improvement)
- 에이전트는 상태 s에서 선택 가능한 행동의 q π ( s )를 비교하고 그중에서 가장 큰 큐함수를 가지는
행동을 선택.
$$ \pi'(s) = argmax_{a \in A} q_{\pi}(s,a) \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $$
- 탐욕 정책 발전을 통해 정책을 업데이트하면 이전 가치함수에 비해 업데이트된 정책으로
움직였을 때 받을 가치함수가 무조건 크거나 같음.
->맨 처음 계산 시, 오차가 매우 커서 max값을 선택된 값이 사실 max값이 아니었다면?
2. 가치 이터레이션
- 명시적인 정책과 내재적인 정책
: 정책 이터레이션은 명시적인으로 정책을 표현, 그 정책을 평가하는 도구로서 가치함수를 사용.
가치 이터레이션은 가치함수 안에 정책 결정이 내재되어 있음.
$$ v_{k+1}(s) = max_{a \in A}(r_{(s,a)}+\gamma v_{k}(s')) \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $$
: max라는 함수의 특성으로 인해 어떠한 상태에서 여러 행동중 가장 큰 가치를 가지는 행동을
선택(정책 결정)을 하게됨. <-> 탐욕 정책 발전과 유사.
3. 다이내믹 프로그래밍의 한계와 강화학습
3-1 다이내픽 프로그래밍의 한계
: 다이내믹 프로그래밍은 계산을 빠르게 하는 것이지 "학습"을 하는 것은 아님.
3-1-1 계산의 복잡도
: 다이내믹 프로그래밍의 계산 복잡도는 상태 크기의 3제곱에 비례.
3-1-2 차원의 저주
: 상태의 차원이 늘어난다면 상태의 수가 지수적으로 증가할 것임.
=> 차원의 저주(Curse of Dimentionality)
3-1-3 환경에 대한 완벽한 정보가 필요
: 보통 보상과 상태 변환 확률은 "환경의 모델"에 해당하므로 정확히 알 수 없음.
3-2 모델 없이 학습하는 강화학습
: 모델 없이 환경과 상호작용을 통해 입력과 출력 사이의 관계를 학습한다.