당신이 로봇에게 미로를 통과하는 법을 가르치거나, 비디오 게임 캐릭터에게 보스전을 마스터하도록 훈련시키거나, 혹은 AI에게 완벽한 이야기를 쓰도록 가르치는 세상을 상상해 보십시오. 이것이 바로 **강화 학습(Reinforcement Learning, RL)**의 영역입니다. 강화 학습은 에이전트가 자신의 '점수'나 '보상'을 극대화하기 위해 시행착오를 거치며 배우는 인공지능의 한 분야입니다. 이는 마치 개에게 기술을 가르치는 것과 같습니다. 잘했을 때는 간식을 주고, 잘못했을 때는 부드럽게 "안 돼"라고 말하는 식이죠. 시간이 흐르면서 개는 가장 많은 간식을 얻기 위한 최적의 행동 순서를 터득하게 됩니다.

이 세계에는 게임을 설정하는 두 가지 주요 방식이 있습니다. 때로는 게임이 영원히 계속되며, 목표는 무한한 시간 동안 최적의 평균 점수를 얻는 것입니다. 하지만 종종 게임에는 엄격한 결승선이 있습니다. 예를 들어 100단계의 던전이나 30초의 스프린트처럼 정해진 단계 수가 있는 것이죠. 이를 유한 지평선(finite-horizon) 설정이라고 부릅니다. 여기서 문제는 '최선의 움직임'이 남은 시간에 따라 달라진다는 점입니다. 만약 100단계가 남았다면 위험한 지름길을 택할 수도 있지만, 5단계만 남았다면 안전하게 플레이할 것입니다. 이 때문에 수학적으로 훨씬 까다로워집니다. 시간이 흐름에 따라 게임의 규칙이 변하기 때문입니다. 과학자들은 "영원한" 게임에서 에이전트를 가르치는 방법은 오랫동안 알고 있었지만, 이러한 "카운트다운" 게임에서 에이전트가 정확히 어떤 속도로 학습하는지를 밝혀내는 것은 풀리지 않은 숙제였습니다.

이 논문은 그 간극을 메우기 위해 **내추럴 정책 경사(Natural Policy Gradient, NPG)**라는 강력하고 특정한 학습법을 분석합니다. NPG를 매우 똑똑하고 신중한 코치라고 생각할 수 있습니다. 단순히 "잘했던 것은 더 많이 하고, 못했던 것은 덜 해라"라고 말하는 기초적인 코치와 달리, N당 NPG는 학습 공간의 '모양'을 이해합니다. 어떤 방향이 더 가파르거나 곡률이 큰지 알기 때문에, 흔들리거나 목표치를 지나치지 않도록 조절하며 발걸음을 옮깁니다. 이 방법은 오늘날 게임과 로보틱스 분야에서 거둔 유명한 AI 성공들의 핵심 비결입니다.

저자들은 다음과 같은 단순하지만 어려운 질문을 던졌습니다. "게임에 엄격한 종료 시점이 있을 때, 이 똑똑한 코치는 실제로 얼마나 빨리 학습하는가?" 그들은 단순히 추측한 것이 아니라, 오차가 시간이 지남에 따라 어떻게 줄어드는지를 증명하기 위해 고도의 수학적 작업을 수행했습니다. 그들은 만약 코치가 일정하고 변하지 않는 보폭을 유지한다면 학습 속도는 준수하지만 시간이 지남에 따라 느려지며, 게임의 길이에 따른 특정 패턴을 따른다는 것을 발견했습니다. 그러나 만약 코치가 결승점에 가까워질수록 더 큰 보폭을 취할 수 있다면, 학습 속도는 기하급수적인 질주로 폭발할 것입니다. 저자들은 이 속도를 단순하고 완벽한 환경 모델에서 수학적으로 증명했으며, 시뮬레이션을 통해 실제 테스트가 그 예측과 일치함을 보여주었습니다.

카운트다운 코치의 이야기

이 연구의 세부 사항인 **유한 지평 마르코프 결정 과정(Finite-Horizon Markov Decision Processes)**에 대해 자세히 알아보겠습니다. 쉽게 말해, 이는 정해진 횟수의 턴, 가능한 상태의 집합(예: 보드 위의 위치), 그리고 행동의 집합(예: 왼쪽이나 오른쪽으로 이동)이 있는 게임을 뜻합니다. "지평선(horizon)"은 게임이 끝나기 전까지의 총 턴 수를 의미합니다.

연구진은 **내추럴 정책 경사(NPG)**라는 알고리즘을 연구했습니다. 당신이 안개 낀 산맥에서 가장 높은 봉우리를 찾으려고 한다고 상상해 보십시오. 일반적인 접근 방식은 가장 가파르게 느껴지는 방향으로 발을 내딛는 것입니다. 하지만 NPG는 지형이 울퉁불퉁하다는 것을 아는 지도와 같습니다. 지형의 곡률을 고려하여 발을 내디딤으로써, 미끄러지거나 지형에 비해 너무 큰 발걸음을 옮기지 않도록 합니다. 이 방법은 인간을 이긴 복잡한 게임들을 가능케 했던 TRPO나 PPO와 같은 대중적인 도구들의 기초가 됩니다.

이 논문이 다루는 핵심 문제는 대부분의 NPG 수학적 증명이 영원히 지속되는 게임에 대해서만 유효했다는 점입니다. 하지만 현실 세계의 많은 과업에는 마감 기한이 있습니다. 게임이 $H$ 단계 후에 끝난다면, 1단계에서의 "최선의 움직임"은 $H-1$ 단계에서의 최선의 움직임과 같지 않습니다. 이는 도미노 효과를 일으킵니다: 1단계의 전략을 바꾸면 2단계의 결과가 바뀌고, 이는 다시 2단계의 최선의 움직임을 바꾸는 식으로 이어집니다. 이는 수학적으로 매우 복잡한 의존 관계의 그물망을 형성합니다.

학습의 두 가지 속도

이 논문은 이러한 카운트다운 시나리오에서 이 알고리즘에 대한 최초의 "유한 시간(finite-time)" 보증을 제공합니다. 즉, 단순히 "결국 도달할 것이다"라고 말하는 것이 아니라, "$t$ 단계 후에 얼마나 근접할 것인가"를 명시합니다. 저자들은 "보폭(step size)"을 어떻게 선택하느냐에 따라 알고리즘이 보이는 두 가지 뚜렷한 행동 양상을 발견했습니다.

1. 꾸준한 보행자 (일정한 보폭)
먼저, 저자들은 결승점에 얼마나 가까워지든 상관없이 매번 같은 크기의 보폭을 유지할 경우 어떤 일이 발생하는지 살펴보았습니다. 이 시나리오에서 알고리즘은 **아선형(sublinearly)**으로 수렴한다는 것을 증명했습니다.

이것이 무엇을 의미할까요? 벽을 향해 걷고 있다고 상상해 보십시오. 처음에는 큰 걸음으로 걷다가 가까워질수록 속도가 느려집니다. 오차(현재 점수와 완벽한 점수 사이의 거리)는 줄어들지만, 점점 더 느려집니다. 논문은 $t$ 번의 반복 후에 오차가 대략 $O(H^2/t)$에 비례함을 증명했습니다.

여기서 $H$는 게임의 길이(지평선)이고, $t$는 알고리즘이 수행한 단계 수입니다. $H^2$ 부분이 핵심입니다. 이는 게임이 두 배 길어지면, 이 꾸준한 방식으로 마스터하기가 네 배 더 어려워지거나 느려진다는 것을 의미합니다. 저자들은 게임의 길이 $H$에 대해, 특정 지점 $h$에서 아주 작은 오차 $\epsilon$ 이내로 들어가기 위해 대략 $2(H-h+1)^2/\epsilon$ 번의 단계가 필요함을 보여주었습니다. 또한 이 증명을 "선형 MDP(Linear MDPs)"로 확장했는데, 이는 게임의 규칙이 거대한 룩업 테이블이 아닌 수학적 공식으로 기술되는 더 복잡한 환경입니다. 완벽한 "오라클(마법의 조력자)"이 값을 정확히 계산할 수 있다는 전제하에 동일한 느리지만 꾸준한 속도가 적용됨을 보여주었습니다.

2. 스프린터 (증가하는 보폭)
다음으로, 저자들은 "결승점에 가까워질수록 코치가 더 큰 보폭을 취하게 한다면 어떻게 될까?"라는 질문을 던졌습니다. 여기서 흥미로운 일이 벌어집니다. 보폭을 특정 방식으로 늘려준다면, 알고리즘이 느린 걸음에서 기하급수적(선형) 수렴으로 전환된다는 것을 증명했습니다.

기하급수적 수렴은 로켓과 같습니다. 속도가 줄어드는 대신, 매 단계마다 오차가 절반(또는 고정된 비율)으로 줄어듭니다. 논문은 적절한 스케줄을 사용할 경우 오차가 $O((1 - 1/\vartheta_\rho)^t)$의 속도로 줄어든다는 것을 증명했습니다.

$\vartheta_\rho$라는 항은 게임이 어떻게 설정되었는지와 시작 위치가 어떻게 분포되어 있는지에 따라 달라지는 "미스매치 계수(mismatch coefficient)"입니다. 게임이 완벽하게 균형 잡힌 최선의 경우, 이 계수는 지평선 길이 $H$와 같습니다. 이는 매 단계마다 오차가 $(1 - 1/H)$의 비율로 줄어듦을 의미합니다.

이를 실용적으로 만들기 위해 저자들은 "지평선 전용 강건한 스케줄(horizon-only robust schedule)"을 제안했습니다. 이는 게임의 구체적인 세부 사항이 아니라 오직 게임의 길이($H$)에만 의존하여 보폭을 늘리는 규칙입니다. 그 규칙은 다음과 같습니다:
$$\eta_t = \eta_0 \left( \frac{H}{H-1} \right)^t$$
이 공식은 코치에게 매 턴마다 보폭을 얼마나 키워야 하는지 정확히 알려줍니다. 논문은 이 규칙을 사용하면 게임의 구체적인 "미스매치"를 알지 못하더라도 기하급수적인 빠른 속도를 보장한다는 것을 증명했습니다.

시뮬레이션 증명

수학적 증명도 훌륭하지만, 실제로도 통할까요? 저자들은 이론을 검증하기 위해 컴퓨터 시뮬레이션을 실행했습니다.

첫 번째 실험에서, 그들은 15개의 위치, 4개의 행동, 7단계의 지평선을 가진 무작위 게임을 만들었습니다. 그리고 일정한 보폭을 사용하여 알고리즘을 실행했습니다. 결과는 이론과 완벽히 일치했습니다: 오차는 $O(1/t)$ 곡선을 따르며 꾸준히 감소했습니다. 게임의 다른 지점(지평선)들을 살펴보았을 때, 미래의 변수가 적기 때문에 나중 단계일수록 오차가 더 작게 나타났으며, 이는 수학적 예측과 일치했습니다.

두 번째 실험에서는 미스매치 계수가 정확히 지평선 길이($H=7$)와 같은 게임을 설정했습니다. 그리고 증가하는 보폭 스케줄을 사용했습니다. 결과는 극적이었습니다. 오차는 단순히 떨어지는 것이 아니라 기하급수적으로 급락했습니다. 그래프는 오차가 매 단계 약 $(1 - /7)$의 비율로 줄어드는 것을 보여주며 "스프린터"의 동작을 확인시켜 주었습니다. 또한 다양한 시작점에서 테스트를 진행했으나, 수학적 모델은 매번 유효했습니다.

이것이 왜 중요한가

이 논문은 기초적인 단계입니다. 모든 AI 문제를 해결했다고 주장하거나, 규칙을 완벽히 모르는 채로 불완리한 데이터로 작동하는 실제 세계의 문제를 해결한다고 주장하는 것이 아닙니다. 대신, 이 논문은 이론적 토대를 제공합니다. "완벽한 세계" 버전의 이러한 카운트다운 게임에서 내추럴 정책 경사가 얼마나 빨리 학습되는지를 우리는 정확히 알고 있다는 것을 증명합니다.

이 논문은 만약 우리가 빠른 결과를 원한다면, 단순히 꾸준한 보폭을 취하는 것이 아니라 용기를 가지고 보폭을 키워나가야 한다는 것을 알려줍니다. 또한 하나의 트레이드오프를 강조합니다: 게임이 길어질수록 꾸와한 보폭으로는 빠르게 배우기가 더 어려워지지만, "스프린터" 전략은 적절히 조정된다면 그 어려움을 극복할 수 있습니다.

이러한 속도를 확립함으로써, 저자들은 미래의 연구자들에게 기준점(baseline)을 제공했습니다. 이제 누군가가 불완전한 데이터로부터 학습하는 새로운 AI를 만들 때, 노이즈와 불확실성 때문에 얼마나 손실을 보고 있는지 확인하기 위해 이 증명된 "완벽한 세계"의 속도와 비교할 수 있게 되었습니다. 이는 경로가 맑을 때 가장 똑똑한 코치들이 얼마나 빨리 달릴 수 있는지를 보여주는 지도와 같습니다.