Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Cases

이 논문은 할인 및 평균 보상 설정 모두에서 최적 정책이 유일하고 단일 체인 (unichain) 일 때, 기존 이론보다 빠른 기하급수적 수렴을 보장하는 통합된 기하학적 분석을 통해 가치 반복 (Value Iteration) 알고리즘의 이론적 수렴 보장을 실험적 관찰과 일치하도록 재정의합니다.

핵심

이 논문은 인공지능이 세상을 배우는 가장 기초적인 방법 중 하나인 '가치 반복 (Value Iteration, VI)' 알고리즘에 대한 새로운 해석을 제시합니다.

기존의 학계에서는 이 알고리즘이 특정 조건에서는 천천히 수렴할 것이라고 믿어 왔지만, 저자들은 **"아니요, 실제로는 훨씬 더 빠르고 효율적으로 작동합니다"**라고 주장하며 이론과 실제의 괴리를 해소합니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

---

🎮 비유: 미로 찾기 게임과 나침반

상상해 보세요. 여러분은 거대한 미로 (Markov Decision Process) 안에 있고, 가장 빠른 길로 출구 (최적 정책) 에 도달해야 합니다. 여러분은 '가치 반복'이라는 나침반을 들고 있습니다. 이 나침반은 "지금 서 있는 곳에서 다음 단계로 가면 얼마나 좋은 결과가 나올까?"를 계산해 줍니다.

1. 기존의 오해: "할인율이 높으면 미로에서 헤매는 시간이 길어진다"

기존 이론 (과거의 학자들) 은 다음과 같이 말했습니다.

• 할인된 보상 (Discounted Reward): 미래의 보상을 조금만 덜 중요하게 여기면 (할인율 $\gamma$가 작을 때), 나침반은 빠르게 출구를 찾습니다. 하지만 미래의 보상을 아주 중요하게 여길수록 ($\gamma$가 1 에 가까워질수록), 나침반은 출구까지 가는 데 엄청난 시간이 걸릴 것이라고 예측했습니다. 마치 "미래가 중요할수록, 지금 당장 무엇을 해야 할지 결정하기가 더 어려워진다"는 논리였습니다.
• 평균 보상 (Average Reward): 미래의 보상을 100% 중요하게 여기는 경우 ($\gamma=1$) 에는 이론상 나침반이 거의 멈추다시피 하거나, 매우 느린 속도로만 수렴할 것이라고 믿었습니다.

하지만 실제 실험 (실제 게임 플레이) 을 해보면, 이론이 예측한 것보다 나침반이 훨씬 더 빠르게 출구를 찾아냅니다. 왜 그럴까요?

2. 이 논문의 발견: "나침반의 시야를 넓히면 훨씬 빠르다!"

저자들은 이 의문을 해결하기 위해 **기하학적 (Geometric)**인 새로운 렌즈를 들이댔습니다.

• 기존의 렌즈 (오래된 방식): 나침반이 각 방 (상태) 의 높이를 따로따로 재서 비교했습니다. 하지만 $\gamma=1$이 되면 모든 방의 높이가 비슷해져서 구분이 안 되고, 혼란이 생깁니다.
• 새로운 렌즈 (이 논문의 방식): 저자들은 **"방들의 높이 차이 (Span)"**에 집중했습니다. 즉, "가장 높은 방과 가장 낮은 방의 차이는 얼마나 줄어들었나?"를 봅니다.

핵심 비유: "등산과 지도"

• 기존 이론은 "등산가들이 정상에 도달하는 데 걸리는 시간을 개별적으로 재서, 가장 느린 사람 때문에 전체가 느리다고 결론 내렸습니다."
• 하지만 저자들은 **"등산가들이 서로의 위치를 비교하는 '높이 차이'만 보면, 그들이 얼마나 빠르게 정상에 가까워지는지 알 수 있다"**고 말합니다.

이 논문에 따르면, 미로가 **하나의 연결된 길 (Unichain, 단일 순환)**을 가진다면, 나침반은 이론이 예측한 것보다 훨씬 빠르게 모든 방의 높이 차이를 좁혀냅니다. 즉, 수렴 속도가 기하급수적 (Geometric) 으로 빠릅니다.

3. 주요 결론: "이론은 틀렸다? 아니다, 조건만 맞으면 된다!"

이 논문은 두 가지 중요한 사실을 밝혀냈습니다.

1. 조건이 맞으면 무조건 빠르다: 만약 미로가 "한 번 들어오면 다시 나올 수 있는" 하나의 연결된 구조 (Unichain) 라면, 미래의 보상을 100% 중요하게 여겨도 (평균 보상), 나침반은 기하급수적으로 빠른 속도로 정답을 찾습니다.
2. 이론과 실제의 괴리 해소: 왜 실제 실험에서는 이론보다 빨랐을까요?
   • 기존 이론은 "최악의 경우 (Worst Case)"를 가정하고, 아주 짧은 시간 동안의 정보 전달 속도만 계산했습니다. (예: 미로 끝에서 시작점까지 정보가 전달되려면 $N$번의 이동이 필요하므로, $N$번 미만일 때는 정보가 안 닿아 느리다고 본 것).
   • 하지만 저자들은 **"충분한 시간 ($N^2$번 정도) 이 지나면 정보가 미로 전체에 퍼지고, 그 이후로는 매우 빠르게 수렴한다"**는 것을 증명했습니다.

💡 요약: 이 논문이 우리에게 주는 메시지

• 과거의 생각: "미래를 중요하게 생각하면 (할인율이 1 에 가까우면), AI 는 학습이 매우 느릴 것이다."
• 새로운 통찰: "아니다! 미로가 잘 연결되어 있다면, AI 는 어떤 경우든 매우 빠르게 학습한다. 우리가 그동안 너무 보수적인 이론을 믿고 있었을 뿐이다."
• 실제 영향: 이 발견은 AI 개발자들이 "내 AI 가 학습이 느린 건 알고리즘이 문제인가, 아니면 데이터/모델의 문제인가?"를 구분하는 데 도움을 줍니다. 이론적으로 빠른 수렴이 보장되므로, 느린 학습은 알고리즘의 한계가 아니라 다른 원인 (예: 신경망의 근사 오차) 일 가능성이 높다는 것을 알게 해줍니다.

한 줄 요약:

"AI 가 미로를 찾는 나침반은 우리가 생각했던 것보다 훨씬 똑똑하고 빠릅니다. 다만, 미로가 하나로 잘 연결되어 있다면 말이죠!"

기술 요약

1. 문제 정의 (Problem)

강화학습 (RL) 의 가장 근본적인 알고리즘 중 하나인 **가치 반복 (Value Iteration, VI)**의 수렴성에 대한 이론적 보장과 실제 실험적 행동 사이에는 지속적인 불일치가 존재합니다.

• 할인 보상 (Discounted Reward) 경우: 고전적 이론은 VI 가 할인율 $\gamma$로 기하급수적 (geometric) 수렴함을 보장합니다. 그러나 $\gamma$가 1 에 가까워질수록 최악의 경우 수렴 속도가 느려지는 것으로 알려져 있습니다.
• 평균 보상 (Average-Reward) 경우 ($\gamma=1$): 최근 연구 (Lee & Ryu, 2025) 는 평균 보상 설정에서 VI 의 수렴이 기하급수적이 아닌 **아선형 (sublinear)**일 수밖에 없으며, 이는 최적의 경우임을 시사했습니다.
• 실제 관측: 실제 실험에서는 이론적 예측보다 VI 가 훨씬 빠르게 수렴하는 것이 자주 관찰됩니다. 특히 $\gamma \to 1$에 가까워지거나 평균 보상 설정에서도 기하급수적 수렴이 관찰되는데, 기존 이론은 이를 설명하지 못합니다.

이 논문은 이러한 이론과 실험 간의 격차를 해소하고, 기존 분석이 왜 보수적인지, 그리고 더 강력한 수렴 보장이 가능한 조건을 규명하는 것을 목표로 합니다.

2. 방법론 (Methodology)

저자들은 할인 보상과 평균 보상 설정을 분리하여 분석하는 기존 관행을 탈피하고, **MDP 의 기하학적 해석 (Geometric Interpretation)**을 기반으로 한 **통합 분석 (Unified Analysis)**을 제시합니다.

A. 새로운 가치 표현 및 기하학적 프레임워크 확장

• 기존 접근의 한계: 기존 기하학적 해석 (Mustafin et al., 2025) 은 할인 보상 ($\gamma < 1$) 에서는 잘 작동하지만, $\gamma = 1$일 때 가치 함수가 정의되지 않거나 (특이 행렬), 상태별 가치 선이 하나로 뭉개져 기하학적 구조가 무너진다는 문제가 있었습니다.
• 새로운 가치 함수 도입: 저자들은 상태별 가치 (inner vertical line) 대신 **외부 수직선 (outer vertical lines)**을 따라 가치를 측정하는 새로운 가치 벡터 $v^\pi$를 정의합니다.
  • 이는 행렬 $(I + \gamma E - \gamma P^\pi)$의 가역성을 보장하여, $\gamma=1$ (평균 보상) 인 경우에도 유니체인 (unichain) 정책 하에서 유일한 해를 갖도록 합니다.
  • 여기서 $E$는 모든 원소가 1 인 행렬입니다.
• 통합된 이점 (Advantage) 함수: 새로운 가치 표현을 통해 할인 보상과 평균 보상 모두에서 **이점 함수 (Advantage Function)**가 동일하게 정의되고, 정책 하이퍼플레인이 유지됨을 증명합니다. 즉, 두 설정이 기하학적으로 동등함을 보여줍니다.

B. 정규화 (Normalization) 및 수렴 분석

• MDP 정규화: 최적 정책 $\pi^*$의 가치를 0 으로 맞추는 변환을 적용하여 MDP 를 정규화합니다. 이 경우 최적 행동의 보상은 0 이 되고, 비최적 행동의 보상은 음수가 됩니다.
• 스팬 반노름 (Span Seminorm) 분석: $L_\infty$ 노름 대신 스팬 반노름 ($sp(V) = \max V - \min V$) 을 사용하여 수렴 속도를 분석합니다. 이는 정책의 상대적 차이에 초점을 맞추어 더 강력한 수렴 보장을 가능하게 합니다.
• 수렴성 증명: $T = n^2$ (상태 수의 제곱) 단계 내에서greedy 정책들이 생성하는 전이 커널의 곱이 기하급수적으로 수축 (contraction) 됨을 증명합니다. 이는 최적 정책이 **유니체인 (unichain)**이라는 가정 하에 성립합니다.

3. 주요 기여 (Key Contributions)

1. 기하급수적 수렴의 재확인 및 개선:

   • MDP 가 고유한 유니체인 최적 정책을 가진다는 가정 하에, 할인 보상과 평균 보상 두 경우 모두에서 VI 가 기하급수적으로 수렴함을 증명했습니다.
   • 기존 분석보다 더 빠른 수렴 속도를 보이며, 평균 보상 경우에도 아선형 수렴이 아닌 기하급수적 수렴이 가능함을 입증했습니다.

2. 할인 및 평균 보상의 통합 분석:

   • 기존에 분리되어 분석되던 두 설정을 하나의 기하학적 프레임워크로 통합했습니다. 동일한 가치 표현과 동역학을 사용하여 두 경우를 동시에 분석할 수 있게 되었습니다.

3. 이론적 한계와 실험적 관측의 격차 해소:

   • Lee & Ryu (2025) 의 아선형 수렴 주장이 $L_\infty$ 노름과 짧은 시간 ($t \le n-2$) 에 국한된 분석에서 비롯된 것임을 지적했습니다.
   • $n^2$ 단계 이후에는 상태 간 정보 전달이 완료되어 기하급수적 수렴이 나타남을 보였습니다.

4. 주요 결과 (Results)

• 수렴 속도:
  • 할인 보상 ($\gamma < 1$): 스펜 반노름에서 수렴 속도는 $\gamma \cdot \iota$ (단, $\iota < 1$) 로, 기존 $\gamma$보다 빠릅니다.
  • 평균 보상 ($\gamma = 1$): 수렴 속도는 $\iota$ (단, $\iota < 1$) 로 기하급수적입니다.
• 반복 횟수 복잡도:
  • 할인 보상: $\epsilon$-최적 정책을 얻기 위한 반복 횟수는 $O\left(\frac{\log(1/\epsilon) + \log(1/(1-\gamma))}{\log(1/\gamma) + \log(1/\iota)} n^2\right)$입니다.
  • 평균 보상: $\epsilon$-이득 (gain) 최적 정책을 얻기 위한 반복 횟수는 $O\left(\frac{\log(1/\epsilon)}{\log(1/\iota)} n^2\right)$입니다.
• 실험적 검증:
  • 인위적으로 구축된 MDP 와 무작위 MDP 에 대한 실험 결과, $\gamma$가 1 에 가까워지거나 평균 보상 설정에서도 오차의 스펜 (span) 이 기하급수적으로 감소함을 확인했습니다.

5. 의의 및 중요성 (Significance)

• 이론적 기여: VI 알고리즘의 수렴성에 대한 기존 통념을 깨뜨리고, 유니체인 가정 하에서 평균 보상 문제에서도 기하급수적 수렴이 보장됨을 증명함으로써 강화학습 이론을 발전시켰습니다.
• 실용적 함의:
  • 현대 RL (Actor-Critic 등) 에서 VI 는 Critic 업데이트의 핵심입니다. 이론적 수렴 속도가 실제보다 느리게 예측되면, 학습 지연을 '근사 오차'나 '최적화 문제'로 오해할 수 있습니다.
  • 본 논문의 엄밀한 이론적 보장은 실제 학습 속도가 느린 원인이 VI 자체의 수렴 특성 때문인지, 아니면 다른 요인 (함수 근사, 데이터 부족 등) 때문인지 구분하는 데 도움을 줍니다.
• 방법론적 확장: MDP 를 기하학적 공간 (Action Space) 에서 해석하는 프레임워크를 평균 보상 문제까지 확장하여, 다양한 RL 문제 해결에 새로운 분석 도구를 제공합니다.

결론적으로, 이 논문은 가치 반복 알고리즘이 평균 보상 설정에서도 기하급수적으로 수렴할 수 있음을 증명하고, 이를 통해 이론과 실험 간의 괴리를 해소하며 강화학습의 기본 알고리즘에 대한 이해를 심화시켰습니다.