397.33 정책 반복(Policy Iteration) 기반 정책 계산

1. 개요

정책 반복(Policy Iteration)은 마르코프 결정 과정(MDP)에서 최적 정책을 계산하는 동적 프로그래밍 알고리즘이다. Ronald Howard가 1960년에 제안한 이 알고리즘은 정책 평가(Policy Evaluation)와 정책 개선(Policy Improvement)의 두 단계를 교대로 반복하여 최적 정책에 수렴한다 (Howard, 1960). 정책 반복은 가치 반복과 달리 매 반복에서 명시적으로 정책을 유지하며, 유한 MDP에서 유한 횟수의 반복으로 정확한 최적 정책에 도달한다는 강력한 수렴 보장을 제공한다.

로봇 임무 계획에서 정책 반복은 상태 공간이 적당한 크기일 때 정확한 최적 정책을 효율적으로 도출하는 데 활용된다. 가치 반복이 근사적 수렴(\epsilon-최적)을 제공하는 반면, 정책 반복은 유한 단계에서 정확한 최적 정책을 보장하며, 실제로 대부분의 문제에서 매우 적은 반복 횟수로 수렴하는 특성을 보인다.

2. 알고리즘의 구조

정책 반복은 다음의 두 단계를 교대로 수행한다.

2.1 단계 1: 정책 평가(Policy Evaluation)

주어진 정책 \pi_k에 대해 가치 함수 V^{\pi_k}를 정확하게 계산한다. 정책 \pi_k를 따를 때의 가치 함수는 벨만 기대 방정식(Bellman Expectation Equation)을 만족한다:

V^{\pi_k}(s) = R(s, \pi_k(s)) + \gamma \sum_{s' \in \mathcal{S}} T(s, \pi_k(s), s') V^{\pi_k}(s'), \quad \forall s \in \mathcal{S}

이 방정식은 |\mathcal{S}|개의 미지수를 포함하는 |\mathcal{S}|개의 선형 연립 방정식 체계를 형성한다. 벡터 형태로 표현하면:

\mathbf{V}^{\pi_k} = \mathbf{R}^{\pi_k} + \gamma \mathbf{P}^{\pi_k} \mathbf{V}^{\pi_k}

여기서 \mathbf{V}^{\pi_k} \in \mathbb{R}^n은 가치 벡터, \mathbf{R}^{\pi_k} \in \mathbb{R}^n은 보상 벡터([\mathbf{R}^{\pi_k}]_i = R(s_i, \pi_k(s_i))), \mathbf{P}^{\pi_k} \in \mathbb{R}^{n \times n}은 전이 확률 행렬([\mathbf{P}^{\pi_k}]_{ij} = T(s_i, \pi_k(s_i), s_j)), n = |\mathcal{S}|이다.

이 선형 체계의 해는 다음과 같다:

\mathbf{V}^{\pi_k} = (\mathbf{I} - \gamma \mathbf{P}^{\pi_k})^{-1} \mathbf{R}^{\pi_k}

\gamma < 1이므로 \gamma \mathbf{P}^{\pi_k}의 스펙트럼 반경이 \gamma를 초과하지 않아 (\mathbf{I} - \gamma \mathbf{P}^{\pi_k})는 항상 비특이(Nonsingular) 행렬이다. 따라서 역행렬이 반드시 존재하며, 가치 함수는 유일하게 결정된다.

2.2 단계 2: 정책 개선(Policy Improvement)

계산된 가치 함수 V^{\pi_k}를 사용하여 개선된 정책 \pi_{k+1}을 도출한다. 각 상태에서 행동 가치 함수(Q-함수)를 최대화하는 행동을 선택한다:

\pi_{k+1}(s) = \arg\max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V^{\pi_k}(s') \right]

이는 현재 가치 함수에 대한 탐욕적(Greedy) 정책을 도출하는 과정이다. 최대값을 달성하는 행동이 여러 개인 경우, 임의의 결정 규칙(예: 사전 순서)에 따라 하나를 선택한다.

2.3 전체 알고리즘

알고리즘: Policy Iteration

입력: MDP M = ⟨S, A, T, R, γ⟩
출력: 최적 정책 π*

1. 초기화: π₀(s) ← 임의의 행동, ∀s ∈ S
2. k ← 0
3. repeat
4.     [정책 평가]
5.     V^{πₖ} 계산: (I - γP^{πₖ})V^{πₖ} = R^{πₖ} 풀기
6.     [정책 개선]
7.     for each s ∈ S do:
8.         π_{k+1}(s) ← argmax_{a ∈ A(s)}
9.             [R(s,a) + γ Σ_{s'} T(s,a,s') V^{πₖ}(s')]
10.    end for
11.    k ← k + 1
12. until π_k = π_{k-1}
13. return π_k

알고리즘은 연속된 두 반복에서 정책이 동일하면 종료한다. 이 시점에서 \pi_k는 최적 정책이다.

3. 수렴성 분석

3.1 단조 개선 성질

정책 반복의 핵심 성질은 정책 개선 정리(Policy Improvement Theorem)에 의해 보장되는 단조 개선이다.

정리 1 (정책 개선 정리). 정책 \pi_k에 대해 탐욕적으로 도출된 정책 \pi_{k+1}은 다음을 만족한다:

V^{\pi_{k+1}}(s) \geq V^{\pi_k}(s), \quad \forall s \in \mathcal{S}

등호가 모든 상태에서 성립하는 경우, \pi_k는 최적 정책이다.

증명. 탐욕적 정책의 정의에 의해:

Q^{\pi_k}(s, \pi_{k+1}(s)) = \max_{a} Q^{\pi_k}(s, a) \geq Q^{\pi_k}(s, \pi_k(s)) = V^{\pi_k}(s)

따라서:

V^{\pi_k}(s) \leq R(s, \pi_{k+1}(s)) + \gamma \sum_{s'} T(s, \pi_{k+1}(s), s') V^{\pi_k}(s')

이 부등식의 우변에서 V^{\pi_k}(s')에 대해 동일한 부등식을 재귀적으로 적용하면:

V^{\pi_k}(s) \leq \mathbb{E}_{\pi_{k+1}} \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, \pi_{k+1}(s_t)) \;\middle|\; s_0 = s \right] = V^{\pi_{k+1}}(s)

\square

3.2 유한 단계 수렴 보장

정리 2 (유한 수렴성). 유한 MDP에서 정책 반복은 최대 |\Pi| = \prod_{s \in \mathcal{S}} |\mathcal{A}(s)|번의 반복 후에 최적 정책에 도달한다.

증명. 정리 1에 의해 가치 함수는 매 반복마다 엄밀하게 개선되거나 변하지 않는다. 가치 함수가 변하지 않으면 알고리즘이 종료되고, 변하면 정책이 반드시 변경된다(동일한 정책은 동일한 가치 함수를 유도하므로). 유한 MDP에서 가능한 결정론적 정책의 수는 유한하고, 정책은 반복되지 않으므로(가치가 단조 증가하므로), 알고리즘은 유한 단계에서 반드시 종료한다. \square

실제로 정책 반복은 이론적 상한보다 훨씬 적은 반복 횟수로 수렴한다. Ye의 분석에 의하면, 할인 MDP에서 정책 반복의 반복 횟수는 O\left(\frac{|\mathcal{S}| \cdot |\mathcal{A}|}{1-\gamma} \log \frac{1}{1-\gamma}\right)로 상한이 주어진다 (Ye, 2011). 경험적으로는 대부분의 문제에서 5~20회의 반복으로 수렴하는 것으로 관측된다.

4. 정책 평가의 계산 방법

4.1 직접 해법(Direct Solution)

선형 연립 방정식 (\mathbf{I} - \gamma \mathbf{P}^{\pi_k})\mathbf{V}^{\pi_k} = \mathbf{R}^{\pi_k}를 직접 풀 수 있다. 가우스 소거법(Gaussian Elimination)이나 LU 분해(LU Decomposition)를 사용하면 O(n^3)의 시간 복잡도로 정확한 해를 구할 수 있다. 이 방법은 상태 공간의 크기가 수천 이하인 경우에 실용적이다.

4.2 반복적 정책 평가(Iterative Policy Evaluation)

상태 공간이 큰 경우, 직접 해법 대신 반복적 방법을 사용할 수 있다. 벨만 기대 연산자 \mathcal{T}^{\pi_k}를 반복 적용한다:

V_{j+1}(s) = R(s, \pi_k(s)) + \gamma \sum_{s'} T(s, \pi_k(s), s') V_j(s')

벨만 기대 연산자 \mathcal{T}^{\pi_k}도 \gamma-수축 사상이므로, 이 반복은 V^{\pi_k}로 수렴함이 보장된다. 수렴 속도는 가치 반복과 동일하게 기하급수적이다.

정책 평가를 반복적으로 수행할 때, 정확한 수렴까지 기다리지 않고 유한 횟수(J번)만 반복한 후 정책 개선으로 넘어가는 접근도 가능하다. 이러한 불완전한 정책 평가(Truncated Policy Evaluation)와 정책 개선의 결합을 **수정된 정책 반복(Modified Policy Iteration)**이라 한다.

4.3 연립 방정식의 구조적 특성

전이 확률 행렬 \mathbf{P}^{\pi_k}는 확률적 행렬(Stochastic Matrix)이므로 각 행의 합이 1이다. \gamma < 1일 때 (\mathbf{I} - \gamma \mathbf{P}^{\pi_k})는 엄밀한 대각 우세(Strictly Diagonally Dominant) 행렬이 되어, 야코비(Jacobi) 반복법이나 가우스-자이델(Gauss-Seidel) 반복법의 수렴도 보장된다. 전이 행렬이 희소(Sparse)한 경우에는 이러한 반복적 해법이 직접 해법보다 효율적일 수 있다.

5. 정책 반복의 변형

5.1 수정된 정책 반복(Modified Policy Iteration)

수정된 정책 반복은 정책 평가 단계에서 벨만 기대 연산자를 J번(J < \infty)만 적용하여 근사적 가치 함수를 구한 후, 정책 개선을 수행한다:

V_0 = V^{\pi_{k-1}} \quad (\text{이전 반복의 가치 함수로 초기화})
V_{j+1}(s) = R(s, \pi_k(s)) + \gamma \sum_{s'} T(s, \pi_k(s), s') V_j(s'), \quad j = 0, \ldots, J-1

J = 1인 경우 수정된 정책 반복은 가치 반복과 동일해진다. J = \infty이면 표준 정책 반복이 된다. 따라서 수정된 정책 반복은 가치 반복과 정책 반복을 연결하는 매개변수적 알고리즘 체계이다.

최적의 J 값은 문제에 의존하지만, 실무적으로 J = 10 \sim 20 정도로 설정하면 대부분의 경우에 좋은 성능을 달성한다. 이 접근법은 정책 평가의 정확한 해를 구하는 O(n^3) 비용을 피하면서도, 가치 반복보다 빠른 수렴을 달성할 수 있다.

5.2 단순 정책 반복(Simplex Method Analogy)

정책 반복은 선형 프로그래밍의 단순 알고리즘(Simplex Method)과 구조적으로 유사하다. MDP의 최적 정책을 선형 프로그래밍으로 정식화할 때, 각 결정론적 정책은 선형 프로그래밍의 꼭짓점(Vertex)에 대응하며, 정책 개선은 다음 꼭짓점으로의 이동에 대응한다. 이 유사성은 정책 반복의 유한 수렴성을 직관적으로 설명한다 (Ye, 2011).

5.3 λ-정책 반복(λ-Policy Iteration)

Bertsekas와 Ioffe가 제안한 λ-정책 반복은 시간차 학습(Temporal Difference Learning)의 자격 흔적(Eligibility Trace) 개념을 정책 평가에 통합한 기법이다 (Bertsekas & Ioffe, 1996). 정책 평가에서 (1-\lambda)-가중된 다단계 수익(Multi-Step Return)을 사용하여 편향-분산 절충(Bias-Variance Trade-off)을 조절한다.

6. 계산 복잡도

6.1 시간 복잡도

여기서 n = |\mathcal{S}|, m = |\mathcal{A}|, K는 최적 정책에 수렴할 때까지의 반복 횟수이다. K는 일반적으로 매우 작은 값이므로(경험적으로 5~20), 정책 반복의 실제 성능은 이론적 최악의 경우보다 크게 우수하다.

6.2 공간 복잡도

정책 반복은 가치 벡터 \mathbf{V} \in \mathbb{R}^n, 정책 벡터 \pi, 전이 행렬 \mathbf{P}^{\pi} \in \mathbb{R}^{n \times n} (또는 전체 전이 텐서 T)을 저장하여야 하므로, 공간 복잡도는 O(n^2 m)이다.

7. 가치 반복과의 비교

가치 반복은 각 반복의 비용이 낮지만 많은 반복이 필요한 반면, 정책 반복은 각 반복의 비용이 높지만 적은 반복으로 수렴한다. 할인 계수 \gamma가 1에 가까운 경우 가치 반복의 수렴이 매우 느려지는 반면, 정책 반복은 \gamma에 덜 민감한 수렴 특성을 보인다.

8. 로봇 임무 계획에서의 적용

8.1 실내 서비스 로봇의 임무 계획

실내 환경에서 서비스 로봇이 복수의 서비스 요청을 처리하는 임무를 정책 반복으로 계획할 수 있다. 상태는 로봇의 위치와 미처리 서비스 요청의 목록으로 구성되며, 정책 반복은 각 상태에서 어떤 서비스 요청을 우선적으로 처리할지, 어떤 경로로 이동할지를 최적화하는 정책을 도출한다.

정책 평가 단계에서 각 정책의 기대 서비스 완료 시간을 정확하게 계산하고, 정책 개선 단계에서 서비스 효율을 극대화하는 방향으로 정책을 개선한다. 이동 실패 확률, 서비스 실행의 불확실성 등이 전이 확률에 반영된다.

8.2 다중 로봇 작업 할당

복수의 로봇에 대한 분산 임무 할당 문제에서, 각 로봇의 MDP를 독립적으로 정의하고 정책 반복을 적용할 수 있다. 로봇 간의 상호작용은 보상 함수의 수정이나 전이 확률의 조건부 모델링을 통해 반영한다. 이 접근법은 중앙집중식 MDP의 상태 공간 폭발 문제를 완화하면서도 합리적인 정책을 도출할 수 있다.

8.3 연속 상태 공간에서의 적용

연속 상태 공간을 갖는 로봇 임무 계획 문제에서는 상태 공간을 이산화(Discretization)하거나 함수 근사(Function Approximation)를 도입하여 정책 반복을 적용할 수 있다. 선형 함수 근사를 사용하는 경우, 정책 평가 단계는 최소 제곱 시간차(Least-Squares Temporal Difference, LSTD) 방법으로 대체되며, 이를 **최소 제곱 정책 반복(Least-Squares Policy Iteration, LSPI)**이라 한다 (Lagoudakis & Parr, 2003).

LSPI는 정책 평가에서 특성 벡터(Feature Vector) \phi(s, a)를 사용하여 행동 가치 함수를 Q(s, a) \approx \phi(s, a)^\top \mathbf{w}로 근사하고, 시간차 오차를 최소화하는 가중치 벡터 \mathbf{w}를 추정한다. 이 기법은 연속 또는 대규모 이산 상태 공간을 갖는 로봇 임무 계획에 특히 유용하다.

9. 참고 문헌

• Howard, R. A. (1960). Dynamic Programming and Markov Processes. MIT Press.
• Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience.
• Ye, Y. (2011). “The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate.” Mathematics of Operations Research, 36(4), pp. 593-603.
• Bertsekas, D. P. & Ioffe, S. (1996). “Temporal Differences-Based Policy Iteration and Applications in Neuro-Dynamic Programming.” Technical Report LIDS-P-2349, MIT.
• Lagoudakis, M. G. & Parr, R. (2003). “Least-Squares Policy Iteration.” Journal of Machine Learning Research, 4, pp. 1107-1149.
• Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control, Vol. II, 4th edition. Athena Scientific.

본 절은 정책 반복 알고리즘의 구조, 수렴성 분석, 계산 복잡도, 주요 변형 기법, 및 로봇 임무 계획에서의 적용을 다루었다. v1.0