순차적 행동 결정 문제

순차적 행동 결정 문제를 푸는 단계를 세 단계로 나누어 보면 다음과 같다.

1. 순차적 행동 문제를 MDP로 전환한다.
2. 가치함수를 벨만 방정식으로 반복적으로 계산한다.
3. 최적 가치함수와 최적 정책을 찾는다

다이내믹 프로그래밍

다이내믹 프로그래밍의 핵심은 큰 문제를 작은 문제로 쪼개었을 때, 만약 작은 문제들이 겹친다면 즉, 문제의 중첩이 발생한다면 한번만 계산하여 계산량을 줄이자는 것이다.

벨만 방정식과 다이내믹 프로그래밍은 아주 밀접한 관계를 가진다.

$v_\pi(s)$를 구하기 위해 한 번에 구하는게 아닌, $v_0(s) \rightarrow v_1(s) \rightarrow v_2(s) \rightarrow ...$ 의 과정을 통해 계산한다. 이렇게 작은 문제로 쪼개서 푸는 것이 벨만 방정식을 구하는 방법이다. 만약 한번에 구하려고 한다면 행동의 개수와 state의 개수에 따라 계산량이 기하급수적으로 늘어난다. 반면 우리는 전 상태만 알면 현 상태를 구할 수 있으므로 전 상태에 대한 값을 저장해두면 계산량을 현저히 줄일 수 있다. 이런 과정이 dynamic programming과 밀접한 관계를 가진다고 할 수 있다.

MDP를 푸는 방법

1. 정책 이터레이션
2. 가치 이터레이션

MDP로 정의 되는 문제에서의 최종 목적은 에이전트가 받을 보상의 합을 최대로 하는 것이다. 즉, 자신이 받을 보상의 기댓값인 가치함수를 최대화 하는 것이다.
이 가치함수에 대한 방정식이 벨만 기대 방정식과 벨만 최적 방정식이기 때문에 우리는 dynamic programming을 통해 이 방정식을 푸는 것이 목적이 된다.

policy iteration

policy iteration의 과정은 두 단계로 나눌 수 있다.

1. policy evaluation

다음의 벨만 기대 방정식을 dynamic programming을 이용하여 푸는 과정이다.

2. policy improvement

1에서 계산한 state value를 기반으로 가장 가치가 높은 action을 하는 policy를 모든 state에 대해 greedy하게 접근하여 policy를 바꾸는 방법이다.

우리는 state에서 어떤 행동을 할 것인지를 어떻게 알 수 있을까?

이전에 배웠던 action value function (Q함수) 을 이용하여 계산할 수 있다.

여기서 $R_{t+1}$은 확률변수가 아니라 정해진 값이므로 위 식을 계산 가능한 형태로 바꿔보면 다음과 같이 쓸 수 있다.

위 action value를 이용하여 정책을 정할 때 greedy한 방법을 사용한다.

value iteration

다이내믹 프로그래밍의 한계

다이내믹 프로그래밍은 다음과 같은 한계를 지닌다.

1. 계산 복잡도

다이내믹 프로그래밍의 계산 복잡도는 상태 크기의 3제곱에 비례한다. 따라서 state가 많아지면 계산 불가능한 크기를 가지게 된다.

2. 차원의 저주

앞에서 본 gird world와 같이 2차원이 아닌 3차원이 된다면 단순히 3/2배가 아닌 지수적으로 상태의 수가 증가하게 된다.

3. 환경에 대한 완벽한 정보가 필요

이 방법을 사용하기 위해서는 상태 천이 확률과 보상을 계산할 수 있어야 한다. 하지만 보통은 이러한 환경에 대한 정보를 완벽하게 아는 상황이 아니다.

따라서 우리는 환경과의 상호작용을 통해 경험을 바탕으로 학습하는 방법 '강화학습'이 필요하다.

모델링이란 입력과 출력의 관계를 식으로 나타내는 과정을 말한다.
실제 세상에서는 환경을 모델링 할 수 없다.

환경에 대한 정보를 모를 경우의 강화학습

모델을 정확히 알지 못하는 경우에는 입력과 출력 사이의 관계르 알기 위해 두 가지 방법으로 접근해볼 수 있다.

1. 할 수 있는 선에서 정확한 모델링을 한 다음 모델링 오차에 대한 부분을 실험을 통해 조정
2. 모델 없이 환경과의 상호작용을 통해 입력과 출력 사이의 관계를 학습

1번은 우리에게 시스템 안정성을 보장하지만 한계가 있고 2번은 안정성을 보장하진 못하지만 모델이 필요 없다는 것이 장점이며 이것이 바로 '강화학습'이다.