최적의 정책을 모르는 우리에게 최적의 가치를 찾기 위해 사용할 수 있는 방법은 정의에서 볼 수 있듯이 현재 가치를 과대 평가하는 정책을 찾는 것입니다.
그러면 우리는 어떤 정책이든 국가의 가치를 평가할 수 있어야 합니다.
정책이 주어진 상태의 값을 얻는 과정을 정책 평가(예측)라고 합니다.
환경에 따라 정책 평가 프로세스가 제한되거나 효율성이 달라질 수 있습니다.
핵심은 정책 평가 방법에 관계없이 모든 상태가 결국 Bellman의 기대 방정식을 충족한다는 것입니다.
물론 정책 평가가 최적의 가치로 이어지지도 않고 정책 변화의 방향을 제시하지도 않는다.
여러 정책을 평가한 후 가장 높은 값을 가진 정책이 있다고 가정합니다.
그렇다면 정책이 최적이라는 것을 보장할 수 있습니까? 당연히 아니지. 무차별 대입으로 전체 정책 영역을 살펴보지 않았다면 최적의 정책이 있을 가능성이 높습니다.
따라서 단순히 정책 간의 가치를 평가하는 것은 적절하지 않습니다.
이 시점에서 사용할 수 있는 한 가지 기술은 가이드라인에서 평가한 값을 주변 q-값과 비교하는 것입니다.
모든 상태에서 q-값이 v_pi보다 크면 해당 q-값을 초래한 조치 선택을 유발하는 정책이 현재 정책을 무시합니다.
정책 강화 정리는 이렇게 찾은 새로운 정책이 기존 값보다 높다는 것을 말합니다.
정책 개선 이론을 바탕으로 자기 비교를 통해 정책을 개선하는 것을 정책 개선(통제)이라고 합니다.
일반적으로 d(aa*)를 pi로 사용하는 욕심 많은 정책은 항상 모든 정책에 대해 정책 향상 정리를 충족합니다.
정책 평가와 정책 개선이 반복되면서 상태의 가치는 고득점 경로가 개선됨에 따라 최대 이득을 내는 최적의 정책으로 수렴된다.
이러한 일련의 프로세스를 정책 반복이라고 합니다.
정책 평가는 보통 더 나은 방법이 있기 때문에 욕심을 잃고, 욕심을 바탕으로 정책을 개선하면 정책 평가가 부정확해집니다.
이 두 프로세스의 대결은 단계적으로 반복되어 서로의 목표를 달성하면서 오류를 줄입니다.
대결을 통한 궁극의 협력은 정책반복의 직관이다.
이론적으로 정책 평가는 무한한 수의 기대 업데이트 후에만 Bellman 기대 방정식으로 수렴하는 것이 보장됩니다.
그러나 현실을 고려하여 일정한 오차 이하로 내려가는 방법을 사용한다.
정책이 반복될 때 최적의 값으로 수렴하는 것이 보장되기 때문에 깨진 정책 평가에 대해 걱정할 필요가 없습니다.
벨만 최적방정식은 최적정책에서 성립하므로 벨만 최적방정식의 기대치를 만족시키면서 벨만 최적방정식을 만족시키는 과정이라고 볼 수 있다.
정책 반복 방식은 세부 설정이 있는 방식을 의미하므로 정책 평가 방식에서 추상화된 원칙, 정책 반복 횟수 및 세부 사항을 GPI(Generalized Policy Iteration)라고 합니다.
대부분의 강화 학습은 GPI를 기반으로 최적의 정책을 학습합니다.
GPI로 도입된 첫 번째 방법은 위에서 언급한 동적 프로그래밍입니다.
동적 프로그래밍이란 최적화 문제들 사이에서 차선 구조가 분할 정복할 수 있고 중복되는 문제가 있는 경우 차선 구조의 솔루션을 저장하여 단계별로 문제를 해결하는 방법을 말합니다.
Bellman 방정식의 경우 값을 다른 값에 신뢰하는 구조를 가지고 있기 때문에 이러한 값을 저장하여 참조 및 업데이트 방법으로 사용할 수 있습니다.
동적 프로그래밍이 해결하는 문제는 알려진 문제(MDP-R, T), 유한 이산(S, A), 에피소드 또는 순차적(S, A), 정적(R), 결정론적 여부(T), 완전히 관찰 가능한(T) , (단일 에이전트)로 가정합니다.
특히 모델 기반의 유일한 배제 분석 방법이기 때문에 다른 알고리즘의 기초가 된다.
즉, MDP(완전한 지식) 기반 정책 평가(E)를 이용하는 거의 유일한 방법이다.
실세계의 많은 부분을 차지하는 미지의 문제는 MDP를 모르기 때문에 V와 Q는 MDP가 아닌 다른 방법으로 구해야 한다.
물론 하위 속성이 이를 알고 있더라도 Experience 또는 ANN을 사용한 구현은 언제든지 가능하다는 점에 유의해야 합니다.
DP를 사용하는 방법 중 가장 기본적인 알고리즘은 정책 반복이다.
정책 반복 방식 중 정책 평가 방식으로는 기대값 업데이트를 무한 반복하는 방식을 사용한다.
기댓값 업데이트는 All-state Sweep 절차에서 Bellman 기대 방정식의 왼쪽을 오른쪽으로 업데이트하는 과정을 말합니다.
주어진 정책 값에 대한 수렴은 모든 상태가 업데이트될 때만 보장되기 때문에 모든 상태를 스위핑하는 것이 중요합니다.
기대값의 갱신이 여러 번 반복되면 두 항 사이의 오차는 모든 상태에 대해 일정 수치 이하가 되며 이때 주어진 정책에 대한 값을 얻었다고 판단한다.
또한 전략 개선 방법으로 델타 함수인 그리디 전략(greedy strategy)을 사용한다.
이러한 정책 평가와 개선을 끝없이 반복하는 방법을 정책 반복이라고 합니다.
정책 반복 방법은 확실히 최적의 정책을 찾을 수 있지만 무한 업데이트 정책 평가와 함께 무한 반복 정책 반복으로 인해 시간이 많이 걸립니다.
다행히 DP는 이를 개선하기 위해 정책 평가 과정에서 Bellman 기대 방정식 대신 최적의 방정식으로 값을 업데이트하는 값 반복 방법이 있습니다.
값반복법은 정책평가 과정에서 벨만 최적방정식을 통해 값을 무한대로 갱신하기 때문에 결국 벨만 최적방정식을 만족하는 값으로 수렴한다.
여기까지는 전략반복법과 비슷한 시간이 소요되지만 값반복법은 벨만 최적화 방정식을 기반으로 업데이트하면서 바로 최적값을 찾기 때문에 전략을 개선하기 위한 여러 과정이 필요하지 않다.
마지막으로, 시간적 이점은 단일 정책 개선 프로세스를 통해 최적의 정책을 얻을 수 있고 정책 반복은 한 번만 발생한다는 것입니다.
물론 정책 평가 과정에서 적절한 수렴에 이르는 시간은 쟁점마다 다르므로 정책 반복 방법이 더 빠를 수 있기 때문에 두 방법 모두 중요하다.
위에서 언급했듯이 정책 반복과 값 반복은 모든 상태를 차례로 정리하여 상태를 업데이트합니다.
이 업데이트 방법을 동기식 DP라고 합니다.
스윕 없이 상태를 업데이트하는 방법을 비동기 DP라고 합니다.
비동기 DP는 정책 평가를 수렴하기 위해 모든 상태를 업데이트해야 하지만 업데이트 순서는 변경할 수 있습니다.
업데이트 순서를 변경하면 수렴 속도를 높일 수 있으므로 일종의 집중 효과를 가져올 수 있습니다.
DP는 이론적 배경과 함께 모델 기반의 방법과 정답에 가까운 값을 평가하는 방법 중 가장 빠른 속도로 최적의 가이드라인을 찾는 방법이라는 점에서 의의가 있다.
최적의 DP 정책을 찾는 데 필요한 시간은 상태 수와 작업 수에 대한 다항식 시간으로 밝혀졌습니다.
최적의 가이드라인이 달성되는 속도는 정확도와 상충됩니다.
가장 정확한 분석 방법은 시간이 많이 걸리고 DP는 다항식 시간으로 처리할 수 있지만 매우 좁은 오차로 끝납니다.
또한 경험적 근사치인 무모델 방법이나 ANN 근사치는 매우 빠르게 값을 추정해도 정확도가 낮아 trade-off 단점이 있다.
에이전트 설계 문제 앤, 하이퍼파라미터
초기화 문제
모델 없는 역학에 대해 이야기해 봅시다.
R과 T를 동시에 결합하는 확률 측정을 역학 P(r, s’|s, a)라고 합니다.
R과 T는 역학의 한계 PDF 또는 PMF로 볼 수 있습니다.