그리드월드는 바둑판처럼 생긴 4×4 격자 환경에서 에이전트가 출발해서 목적지까지 최단 경로로 이동하는 게임이다. 총 16개의 칸(상태)이 있으며, 그중 2개는 목적지(종료 상태)이고 나머지 14개의 칸 중 어디에서 든 무작위로 에이전트가 시작하게 된다.
이때 에이전트가 최단 거리로 목적지에 도달하도록 정책을 설정하는 것이 이 문제의 목표가 된다.
이처럼 MDP 문제는 다이나믹 프로그래밍을 이용해 작은 단위로 나누어 반복적으로 해결할 수 있으며, 이를 통해 강화학습에서 최적의 정책을 구하는 방법을 배울 수 있다.
그리드월드 환경은 다음과 같다.
- 이 환경은 4x4 바둑판 형태로 구성되어 있다.
- 각 칸은 하나의 상태이고, 에이전트는 상·하·좌·우 네 방향 중 하나로 이동할 수 있다.
- 이동은 랜덤이고, 각 방향으로 갈 확률이 25%씩으로 설정되어 있다.
- 매번 움직일 때마다 보상은 항상 -1이다. 즉, 목적지까지 빨리 가는 것이 유리하다.
- 두 개의 칸은 목적지로 설정되어 있고, 이곳에 도달하면 더 이상 이동하지 않는다.
이제 위의 그림에서 각 단계가 무엇을 의미하는지 순서대로 살펴보자.
(1) k = 0: 초기 상태
처음에는 모든 상태의 가치(Value)가 0으로 설정되어 있다. 단, 목적지(왼쪽 위와 오른쪽 아래 칸)는 언제나 가치가 0으로 유지된다. 아직 아무 계산도 이루어지지 않았기 때문에 전체 그리드는 0으로 채워져 있다.
(2) k = 1: 1회 정책 평가
각 칸에서 무작위 정책(상, 하, 좌, 우 각각 25%)을 따라 한 번 움직였을 때의 보상을 반영한다. 이동하면 항상 -1의 보상을 받기 때문에, 한 칸 떨어진 이웃 상태들의 평균적인 가치를 계산한 결과가 -1로 나타난다. 이 단계에서 목적지가 아닌 모든 칸의 가치가 -1로 바뀐다.
(3) k = 2: 2회 정책 평가
이번에는 한 번 더 계산을 반복한 상태이다. 예를 들어 (0,1) 위치의 값은 -1.7로 나타난다. 이 값은 바로 옆 상태들(특히 목적지 쪽)의 가치와 보상을 고려한 결과이다. 반복할수록 각 칸의 값이 점점 더 낮아지고, 목적지에서 가까울수록 가치가 높다(즉, 절댓값이 작다).
(4) k = ∞: 수렴한 상태 (무한 반복 후)
무한히 반복하면 각 상태의 진짜 상태가치(True State Value)를 얻을 수 있다. 목적지에서 가까운 칸은 -14, 좀 더 멀리 떨어진 칸은 -20, -22와 같이 점점 더 낮은 값을 가진다. 이 값은 “현재 이 칸에서 시작했을 때, 무작위 정책을 따르며 목적지까지 이동하면서 받을 총 보상의 기대값”을 의미한다. 보상이 -1이므로, 절댓값이 작을수록 목적지와 가깝다는 뜻이다.
이 그림은 그리드월드 환경에서 특정 칸, 즉 좌표 (0,1)에 있는 상태의 가치를 계산하는 과정을 보여주고 있다. 여기서 가치를 계산한다는 것은, 에이전트가 해당 위치에서 출발했을 때 앞으로 받을 수 있는 보상의 기대값이 얼마인지 추정하는 것을 의미한다.
먼저, 전제 조건부터 살펴보자. 이 환경에서는 에이전트가 상, 하, 좌, 우 네 방향으로 무작위로 움직인다. 각 방향을 선택할 확률은 25%로 동일하며, 한 번 움직일 때마다 보상은 항상 -1이다. 이 말은 에이전트가 어디로 이동하든 무조건 -1의 보상을 받는다는 뜻이다.
- 에이전트가 위치한 좌표 (0,1)에서 네 방향으로 움직이면 다음과 같은 일이 벌어진다.
- 왼쪽으로 이동하면 (0,0)으로 가게 되는데, 이 칸의 가치는 현재 0.0이다.
- 위쪽은 경계 바깥이라 움직일 수 없기 때문에 다시 원래 위치 (0,1)에 남게 되며, 이 칸의 가치는 -1.0이다.
- 오른쪽으로 이동하면 (0,2)로 가게 되고, 이 칸의 가치도 -1.0이다.
- 아래쪽으로 이동하면 (1,1)로 가게 되며, 역시 이 칸의 가치도 -1.0이다.
이렇게 에이전트가 네 방향으로 이동했을 때 만나는 상태들의 가치를 평균 내면 0.0*0.25 + (-1.0) *0.25 + (-1.0) *0.25 + (-1.0) *0.25 = -0.75가 된다. 여기에 한 번 이동했을 때 받는 보상(즉시보상) -1.0을 더하면 현재 위치 (0,1)의 상태 가치는 -1.75가 되는 것이다.
이처럼 무작위로 움직이는 정책 아래에서는 에이전트가 한 칸 이동할 때마다 평균적으로 얼마만큼의 가치를 기대할 수 있는지를 계산하게 된다. 이런 방식으로 각 상태의 가치가 점차 갱신되며, 반복할수록 점점 실제 가치에 가까워지게 된다. 이 과정이 바로 정책 평가이고, 이 그림은 그 중 한 단계를 시각적으로 보여주고 있는 것이다.
이 그림은 다이나믹 프로그래밍에서 정책 평가와 정책 제어가 어떻게 함께 작동하는지를 보여주는 예제이다.
먼저 왼쪽 표는 정책 평가 단계이다. 이 단계에서는 초기 정책(예: 상하좌우로 고르게 0.25의 확률로 움직이는 정책)을 기준으로 각 칸(상태)의 가치를 반복적으로 계산한다. 보상은 한 번 움직일 때마다 -1이 주어지기 때문에, 목적지로부터 멀어질수록 가치가 낮아지며, 반복할수록 점점 정확한 가치로 수렴하게 된다. 이 과정을 충분히 반복하면 각 그리드 상태에서 정책을 따랐을 때 기대할 수 있는 보상 값이 잘 반영된 가치 테이블이 만들어진다.
오른쪽 표는 정책 제어 단계이다. 이 단계에서는 방금 계산한 가치 테이블을 기반으로 각 칸에서 어떤 방향으로 움직여야 가장 높은 가치를 얻을 수 있을지를 판단해, 정책을 새롭게 설정한다.
이때 탐욕적(greedy) 방식이 사용된다. 각 칸에서 상하좌우로 이동할 수 있는 경우 중에서 **가치가 가장 큰 칸(즉, 가장 작은 음수 값을 가지는 칸)**으로 움직이는 방향의 확률을 높게 설정하고, 나머지 방향으로는 움직이지 않도록 확률을 0으로 설정한다.
예를 들어 가운데 칸의 경우 위쪽과 왼쪽에 있는 칸이 둘 다 -14로 가장 가치가 높다면, 이 두 방향에 대해 각각 0.5의 확률로 이동하도록 정책을 설정하고, 나머지 두 방향은 확률을 0으로 만든다. 이렇게 새로 설정된 정책은 이전보다 더 가치 있는 행동을 하게 만들어준다.
이처럼 정책 평가로 가치를 계산하고, 그 값을 바탕으로 정책 제어로 정책을 개선하는 과정을 반복하면, 점점 더 좋은 정책으로 업데이트되며 결국에는 최적의 정책과 최적의 가치 함수에 도달하게 된다.
