다이나믹 프로그래밍 1/3

강화학습에서 MDP는 보통 복잡한 환경에서 동작한다. 상태가 수백 개에 달하고, 가능한 행동도 많아질수록 문제를 해결하는 것이 점점 더 어려워진다. 이럴 때 유용하게 사용할 수 있는 방법이 바로 다이나믹 프로그래밍(Dynamic Programming)이다.

최적화 이론과 MDP

다이나믹 프로그래밍은 어렵고 복잡한 문제를 쉽게 풀 수 있도록 도와주는 대표적인 알고리즘 기법이다. 그 핵심은 큰 문제를 잘게 나누고, 그 조각들을 하나씩 해결해서 전체 해답을 찾는 방식이다. 이 접근법은 최적화 이론(the Principle of Optimality)에 기반하고 있다. 이 이론을 적용하기 위해서는 두 가지 조건이 충족되어야 한다.

첫 번째 조건은 최적의 하부 구조 (Optimal Substructure)이다. 이 조건은 이렇게 말한다.

“큰 문제는 작은 문제로 나눌 수 있고, 그 작은 문제들을 잘 해결하면 결국 전체 문제도 잘 해결된다.”

예를 들어, 목적지까지 가는 가장 빠른 길을 찾고 싶을 때 중간 지점까지 가장 빠르게 가는 방법이 이미 구해져 있다면, 그 정보를 활용해서 전체 경로도 쉽게 구할 수 있는 것과 같다.

두 번째 조건은 겹치는 하위 문제 (Overlapping Subproblems)이다. 이 조건은 말 그대로, 같은 작은 문제가 여러 번 반복해서 등장한다는 의미다. 그래서 한 번 계산한 결과는 따로 저장해두고, 다시 그 문제가 등장하면 이전에 저장했던 결과를 재사용하는 것이 더 효율적이다.

예를 들어, 어떤 상태에서 출발하는 최적의 경로를 여러 번 계산해야 할 경우, 처음 계산한 결과를 그대로 쓰면 반복 계산을 피할 수 있다.

MDP는 이 두 조건을 모두 만족한다. MDP는 최적의 하부 구조도 있고, 같은 상태가 반복해서 등장하는 경우도 많다. 즉, MDP는 다이나믹 프로그래밍을 적용하기에 딱 좋은 구조를 가지고 있다.

그래서 복잡해 보이는 문제라도, 문제를 작게 나누고, 부분 문제를 해결한 뒤 그 결과를 잘 모아가면 결국 전체 문제도 쉽게 해결할 수 있게 되는 것이다.

여기에서 꼭 기억할 점은, MDP는 문제를 작은 단위로 나눌 수 있기 때문에 다이나믹 프로그래밍이 유용하게 적용된다는 것이다. 최적화 이론 자체를 깊이 이해할 필요는 없다. 중요한 것은 MDP가 다이나믹 프로그래밍의 두 조건을 모두 만족하기 때문에 이 방식으로 해결할 수 있다는 점이다.

이제 모델기반 환경에서 MDP 문제를 작은 단위로 나누어서 해결하는 가장 대표적인 방법인 다이나믹 프로그래밍에 대해 알아보자.

모델기반과 모델프리

강화학습에서는 어떤 문제를 모델기반과 모델프리 환경으로 나누어 생각할 수 있다. 이 개념을 쉽게 이해하려면 라우팅 예제를 떠올려보면 좋다.

모델기반과 모델프리의 차이는 다음과 같다.

모델기반 환경에서는 에이전트가 어떤 상태(State)에서 어떤 행동(Action)을 했을 때 그 다음에 어떤 상태로 이동하는지, 그리고 그에 따른 보상이 무엇인지 모든 정보를 알고 있다. 즉, 어떤 길을 선택하면 어디로 가게 되는지를 미리 알고 있는 셈이다.

반면에 모델프리 환경에서는 그렇게 상세한 정보를 미리 알 수 없다. 에이전트는 오직 시작 지점과 목적지만 알고 있을 뿐이다. 어떤 행동을 했을 때 어떤 상태로 이동하는지는 직접 행동을 해봐야만 알 수 있다. 일종의 ‘시행착오’를 통해 배우는 방식이라고 볼 수 있다.

이제 다이나믹 프로그래밍(Dynamic Programming)에 대해 알아보자. 이 방법은 모델기반 강화학습 기법으로, 환경에 대한 정보를 완전히 알고 있을 때 사용할 수 있다.

좀 더 구체적으로 말하면, 다이나믹 프로그래밍은 MDP의 구성요소인 상태(S), 행동(A), 상태전이확률(P), 보상(R), 감가율(γ) 이 다섯 가지를 모두 알고 있는 상태에서 동작한다.

이 정보를 기반으로 하여 정책이 주어졌을 때의 상태가치함수(v_π), 가장 좋은 정책을 따랐을 때의 최적 상태가치함수(v*), 그리고 그 정책 자체인 최적 정책(π*)까지 계산할 수 있다.

다이나믹 프로그래밍은 크게 두 단계로 이루어진다. 정책 평가(Policy Evaluation)와 정책 제어(Policy Control)이다.

(1) 정책 평가 (Policy Evaluation)

우선, 하나의 정책을 고정해 놓고, 그 정책을 따를 경우 각 상태에서 받을 수 있는 보상의 기대 값을 계산한다. 이 과정을 반복하면 각 상태의 가치를 점점 더 정확하게 추정할 수 있다.

이때 사용하는 가치함수는, 처음 타임스텝에서 받는 보상과 그 이후 상태에서 받게 될 미래 보상의 합을 기반으로 구성된다.

각 상태의 가치를 한 번에 정확하게 구할 수는 없지만, 조금씩 업데이트 하면서 반복하다 보면 진짜 정답에 점점 가까워진다. 수학적으로 이 과정이 참된 가치함수(True Value Function)에 수렴한다는 것도 이미 증명되어 있다.

(2) 정책 제어 (Policy Control)

이제 계산한 가치함수를 바탕으로 현재 정책을 개선할 수 있다. 어떤 상태에서 더 높은 가치를 줄 수 있는 행동이 있다면, 그 행동을 선택하도록 정책을 수정하는 것이다. 즉, 가치가 높은 행동을 탐욕적으로(greedy) 선택해서 정책을 조금 더 좋게 만드는 과정이다.

반복을 통해 최적 정책을 찾는다 정책 평가와 정책 제어는 한 번만 하는 것이 아니다. 계속 반복하면서 점점 더 나은 정책을 만들어간다. 현재 정책을 평가하고, 그 결과를 기반으로 정책을 개선하고, 다시 평가하고, 또 개선하고… 이 과정을 반복하면 결국 최적의 정책(π*)에 도달할 수 있다.

이제 이 개념을 좀 더 직관적으로 이해하기 위해 그리드월드(Gridworld) 예제를 살펴보자.

그리드월드는 바둑판처럼 생긴 4×4 격자 환경에서 에이전트가 출발해서 목적지까지 최단 경로로 이동하는 게임이다. 총 16개의 칸(상태)이 있으며, 그중 2개는 목적지(종료 상태)이고 나머지 14개의 칸 중 어디에서 든 무작위로 에이전트가 시작하게 된다.

이때 에이전트가 최단 거리로 목적지에 도달하도록 정책을 설정하는 것이 이 문제의 목표가 된다.

이처럼 MDP 문제는 다이나믹 프로그래밍을 이용해 작은 단위로 나누어 반복적으로 해결할 수 있으며, 이를 통해 강화학습에서 최적의 정책을 구하는 방법을 배울 수 있다.