Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration

컴퓨터가 끝없는 시행착오 게임을 통해 의사결정 방법을 배우는 세상을 상상해 보십시오. 이것이 바로 비디오 게임 봇부터 자율주행 자동차에 이르기까지 모든 것에 동력을 공급하는 인공지능의 한 분야인 **강화 학습(Reinforcement Learning, RL)**의 핵심입니다. 강화 학습의 본질은 에이전트가 시간이 지남에 따라 가장 많은 보상을 얻기 위해 주어진 상황에서 어떤 최선의 움직임을 취해야 하는지 알아내는 것입니다. 이를 해결하기 위해 수학자들은 모든 가능한 움직임의 가치를 보여주는 지도와 같은 역할을 하는 **벨만 방정식(Bellman equation)**이라는 유명한 규칙을 사용합니다. 하지만 이 지도에는 까다롭고 울퉁불퉁한 가장자리가 있습니다. 바로 단 하나의 최선책을 선택하는 "max" 함수를 포함하고 있어, 컴퓨터가 빠르게 해결할 수 있도록 수학적으로 매끄럽게 다듬기가 매우 어렵다는 점입니다.

이 울퉁불퉁한 가장자리를 고치기 위해 연구자들은 종 often "정규화 항(regularizer)"을 추가합니다. 이것은 컴퓨터에게 현재 자신이 최고라고 생각하는 한 가지 방식에 맹목적으로 매달리기보다 다양한 옵션을 탐색하도록 권장하는 부드러운 자극이나 완만한 제약이라고 생각하면 됩니다. 이는 마치 학생에게 "단순히 정답을 암기하지 말고, 몇 가지 다른 해결책 뒤에 숨겨 있는 논리를 이해하려고 노력해 봐"라고 말하는 것과 같습니다. **정규화된 정책 반복(Regularized Policy Iteration, RPI)**이라고 알려진 이 기술은 실제로 엄청난 성공을 거두며 오늘날 사용되는 강력한 알고리즘들을 이끌어냈습니다. 그러나 이러한 알고리즘들이 현실 세계에서 매우 잘 작동함에도 불구하고, 과학자들은 왜 그것들이 그렇게 잘 작동하는지, 그리고 이론적으로 얼마나 빨리 완벽한 해답에 수렴해야 하는지를 이해하기 위해 머리를 싸매 왔습니다.

이 논문은 그 미스터리를 해결하기 위해 등장했습니다. 저자들은 이러한 현대적인 "부드러운(soft)" 학습 알고리즘과 고전적이고 전통적인 수학 도구인 **뉴턴-랩슨 방법(Newton–Raphson method)**을 연결하는 숨겨진 다리를 발견했습니다. 뉴턴-랩슨 방법을 지형의 경사를 이용하여 거대하고 정밀한 발걸음을 내디뎌 골짜기의 바닥을 찾는 초고속 방법이라고 생각할 수 있습니다. 이 논문은 우리가 "부드러운" 정규화 항을 벨만 방정식에 추가할 때, 그 결과로 나타나는 알고리즘이 수학적으로 이 강력한 뉴턴 방법과 동일하다는 것을 증명합니다. 이것은 막연한 유사성이 아니라 엄격하고 공식적인 동등성입니다. 이 발견 덕분에 저자들은 이 알고리즘들이 해답을 향해 **이차 수렴(quadratic convergence)**하며, 즉 해답에 가까워질수록 오차가 믿을 수 없을 정도로 빠르게 줄어든다는 것(작은 숫자를 제곱하여 훨씬 더 작게 만드는 것처럼)을 증명할 수 있었습니다. 또한, 모든 단계를 완벽하게 해결하지 못하더라도(현실에서는 흔한 일입니다), 알고리즘이 여전히 작동하며 다만 약간 더 느리고 예측 가능한 속도로 작동한다는 것을 보여주었습니다. 마지막으로, 이 연결 고리에서 영감을 얻어, 저자들은 표준적인 방법보다 더 빠르게 수렴하는 "3차(third-order)" 도약을 수행하는 새로운 더 빠른 알고리즘을 구축했으며, 컴퓨터 시뮬레이션을 통해 이것이 실제로 시간을 절약한다는 것을 입증했습니다.

매끄러운 경로의 이야기

이 모험 속으로 더 깊이 들어가 봅시다. 당신이 광활하고 안개가 자욱한 지형(최적의 해답)에서 가장 낮은 지점을 찾으려고 노력한다고 상상해 보십시오. 지형은 갑작스러운 절벽과 날카로운 봉우리(벨만 방정식의 "max" 연산자) 때문에 까다롭습니다. **정책 반복(Policy Iteration)**과 같은 전통적인 방법은 하이커가 매 지점마다 멈춰 서서 주변을 둘러보고, 눈에 보이는 가장 좋은 방향을 향해 직선으로 걷기로 결정하는 것과 같습니다. 이것도 효과는 있지만, 느리고 덜컥거릴 수 있습니다.

이 논문은 반전을 도입합니다: 바로 **정규화(Regularization)**입니다. 이것은 전체 지형 위에 부드럽고 매끄러운 젤을 붓는 것과 같습니다. 날카로운 절벽은 완만한 경사가 됩니다. 갑자기, 예전에는 울퉁불퉁한 절벽이었던 "max" 연산자가 매끄러운 곡선이 됩니다. 이것이 바로 **매끄러운 벨만 방정식(Smoothed Bellman Equation)**입니다.

저자들의 결정적인 "아하!" 순간은 이 젤이 덮인 매끄러운 지형을 항해하는 것이 정확히 뉴턴-랩슨 방법이 하는 일이라는 것을 깨달은 것이었습니다. 수학의 세계에서 뉴턴 방법은 그 속도로 유명합니다. 만약 당신이 해답에 근접해 있다면, 이 방법은 단순히 한 걸음을 내딛는 것이 아니라, 매 단계마다 정확한 숫자의 개수를 두 배로 늘리며 당신을 훨씬 더 가깝게 데려다 놓을 수 있도록 완벽하게 계산된 발걸음을 내딛습니다. 이 논문은 당신이 **정규화된 정책 반복(RPI)**을 사용할 때, 사실 비밀리에 바로 이 작업을 수행하고 있다는 것을 증명합니다. 당신은 단순히 추측하는 것이 아니라, 문제의 매끄러운 버전에 대해 정밀한 뉴턴 단계를 수행하고 있는 것입니다.

해답의 속도

이것이 왜 중요할까요? 컴퓨팅에서 속도는 전부이기 때문입니다. 저자들은 RPI가 **국소적 이차 수렴(local quadratic convergence)**을 누린다는 것을 증려했습니다. 쉬운 말로, 일단 알고리즘이 "충분히 가까워지면", 단순히 천천히 좋아지는 것이 아니라 폭발적으로 좋아진다는 뜻입니다. 만약 당신이 아주 조금 틀렸다면, 다음 단계에서는 그 오차가 제곱만큼 작아져서 거의 제로에 가깝게 만듭니다.

또한 이 논문은 매우 현실적인 문제, 즉 매번 완벽한 단계를 계산할 수 없다면 어떻게 될지에 대해서도 다룹니다. 현실 세계에서 컴퓨터는 바쁘며, 때로는 계산을 조기에 중단해야 합니다. 이를 **부정확한 정책 평가(inexact policy evaluation)**라고 합니다. 저자들은 만약 당신이 전체 무한 루프 대신 몇 단계($M$이라고 합시다)의 계산만 수행하는 지름길을 택하더라도, 알고리즘이 여전히 작동함을 보여주었습니다. 이 알고리즘은 **부정확한 뉴턴 방법(inexact Newton method)**처럼 작동합니다. 저자들은 이 지름길의 속도가 당신이 수행하는 단계 수($M$)에 달려 있음을 증명했습니다. 더 많은 단계를 밟을수록 더 빨라지며, 오차는 $\gamma^M$의 비율로 줄어듭니다(여기서 $\gamma$는 0과 1 사이의 할인 계수입니다). 이는 각 단계에서 조금 더 많은 작업을 하는 것이 상당한 보상으로 돌아온다는 것을 설명해 줍니다.

새로운 슈퍼 알고리즘

하지만 저자들은 기존의 방식을 설명하는 데서 멈추지 않았습니다. 그들은 "뉴턴 방법이 그렇게 훌륭하다면, 이를 더 좋게 만들 수는 없을까?"라고 물었습니다. 수학의 세계에는 더 많은 정보를 사용하여 훨씬 더 크고 똑똑한 도약을 수행하는 "고차(higher-order)" 뉴턴 방법들이 존재합니다.

이에 영감을 받아, 그들은 **3차 정규화 정책 반복(Third-Order Regularized Policy Iteration, T-RPI)**이라는 새로운 알고리즘을 설계했습니다. 표준적인 방법이 하나의 거대한 발걸음을 내딛는 동안, T-RPI는 한 걸음을 내딛고, 발 디딤을 확인한 다음, 동일한 정보를 사용하여 두 번째 정밀한 발걸음을 내딛는 것을 상상해 보십시오. 이를 통해 **3차 수렴(third-order convergence)**을 달于할 수 있습니다. 이것은 이차 수렴보다도 더 빠르게 해답에 도달한다는 뜻입니다. 오차는 단순히 제곱되는 것이 아니라 세제곱되어, 적절한 영역에 들어서는 즉시 순식간에 사라집니다.

증명된 결과

이 논문은 단순히 화이트보드 위의 수학에만 의존하지 않고, 실제로 테스트를 진행했습니다. 그들은 100개의 상태와 20개의 행동을 포함하는 시뮬레이션 환경에서 수치 실험을 수행했습니다.

• 그들은 표준 RPI 알고리즘이 실제로 이론적 예측과 일치하게 이차적으로 가속화됨을 확인했습니다.
• 그들은 RMPI(지름길을 사용하는 버전)가 선형적으로 가속화되지만, 그 속도가 그들이 수행한 단계 수($M$)에 정확히 의존한다는 것을 확인하여 $\gamma^M$ 규칙을 검증했습니다.
• 가장 흥고하게도, 그들은 새로운 T-RPI 알고리즘을 테스트했습니다. 그 결과, 이 알고리즘이 표준 방법보다 더 적은 단계로 동일한 수준의 정확도에 도달한다는 것을 발견했습니다. 더욱이, 계산을 재사용하는 방식(동일한 "골격"을 가진 두 방정식을 동시에 해결함)을 영리하게 설계했기 때문에, 이 새로운 알고리즘은 실제 작동 시간(clock time) 기준으로 표준 방법을 약 1.3배 앞질러 더 빠르게 작업을 마쳤습니다.

이것이 의미하는 바

이 논문은 현대 AI를 구동하는 실용적인 "부드러운" 알고리즘과 수치 해석의 엄격한 "딱딱한" 수학 사이의 가교 역할을 합니다. 이러한 현대적 알고리즘들이 사실은 변장한 뉴턴 방법이라는 것을 증명함으로써, 저자들은 이를 이해할 수 있는 강력한 새로운 관점을 제공했습니다. 그들은 이러한 알고리즘들이 왜 빠른지, 어떻게 하면 더 빠르게 만들 수 있는지 보여주었으며, 차세대 의사결정 AI를 구축하기 위한 청사진을 제시했습니다. 이는 때때로 가장 진보된 기술이 단지 새로운 부드러운 외투를 입은 고전적인 아이디어일 뿐이라는 사실을 상기시켜 줍니다.