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 모델 없이 학습하는 강화학습

        : 모델 없이 환경과 상호작용을 통해 입력과 출력 사이의 관계를 학습한다.