397.32 가치 반복(Value Iteration) 기반 정책 계산

1. 개요

가치 반복(Value Iteration)은 마르코프 결정 과정(MDP)에서 최적 가치 함수와 최적 정책을 계산하는 대표적인 동적 프로그래밍 알고리즘이다. 이 알고리즘은 벨만 최적 연산자(Bellman Optimality Operator)를 반복적으로 적용하여 임의의 초기 가치 함수로부터 최적 가치 함수 $V^*$ 로 수렴하는 시퀀스를 생성한다. Richard Bellman이 제안한 동적 프로그래밍의 원리(Principle of Optimality)에 직접적으로 기초하며 (Bellman, 1957), 수축 사상 정리(Contraction Mapping Theorem)에 의해 수렴성이 엄밀하게 보장된다.

로봇 임무 계획에서 가치 반복은 유한 상태 공간의 MDP에 대해 $\epsilon$ -최적 정책을 계산하는 데 널리 활용된다. 알고리즘의 구현이 직관적이고 각 반복의 계산이 독립적으로 병렬화 가능하다는 장점이 있어, 실시간 임무 계획 시스템에서 효과적으로 적용할 수 있다.

2. 알고리즘의 정의

2.1 벨만 최적 연산자

가치 반복 알고리즘의 핵심은 벨만 최적 연산자(Bellman Optimality Operator) $\mathcal{T}^*$ 이다. 이 연산자는 가치 함수 $V: \mathcal{S} \rightarrow \mathbb{R}$ 위에서 다음과 같이 정의된다:

$[\mathcal{T}^* V](s) = \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V(s') \right]$

여기서 $\mathcal{S}$ 는 상태 공간, $\mathcal{A}(s)$ 는 상태 $s$ 에서 실행 가능한 행동 집합, $R(s, a)$ 는 보상 함수, $T(s, a, s')$ 는 전이 확률, $\gamma \in [0, 1)$ 는 할인 계수이다.

2.2 알고리즘 절차

가치 반복 알고리즘은 다음의 절차로 수행된다.

알고리즘: Value Iteration

입력: MDP M = ⟨S, A, T, R, γ⟩, 수렴 임계값 ε > 0
출력: ε-최적 가치 함수 V, 최적 정책 π

1. 초기화: V₀(s) ← 0, ∀s ∈ S
2. k ← 0
3. repeat
4.     for each s ∈ S do:
5.         V_{k+1}(s) ← max_{a ∈ A(s)} [R(s,a) + γ Σ_{s'} T(s,a,s') V_k(s')]
6.     end for
7.     δ ← max_{s ∈ S} |V_{k+1}(s) - V_k(s)|
8.     k ← k + 1
9. until δ < ε(1-γ)/(2γ)
10. for each s ∈ S do:
11.     π(s) ← argmax_{a ∈ A(s)} [R(s,a) + γ Σ_{s'} T(s,a,s') V_k(s')]
12. end for
13. return V_k, π

초기 가치 함수 $V_0$ 는 임의의 값으로 설정할 수 있으며, 관례적으로 모든 상태에 대해 0으로 초기화한다. 알고리즘은 연속적인 반복 사이의 가치 함수 변화가 충분히 작아질 때까지 벨만 갱신(Bellman Update)을 수행한다.

3. 수렴성 분석

3.1 수축 사상 기반 수렴 증명

가치 반복의 수렴성은 벨만 최적 연산자 $\mathcal{T}^*$ 가 최대 노름(Supremum Norm) $\|\cdot\|_\infty$ 하에서 $\gamma$ -수축 사상(Contraction Mapping)임에 기초한다.

정리 1 (수축 사상 성질). 임의의 두 가치 함수 $V_1, V_2$ 에 대해:

$\|\mathcal{T}^* V_1 - \mathcal{T}^* V_2\|_\infty \leq \gamma \|V_1 - V_2\|_\infty$

이 성질과 바나흐 고정점 정리(Banach Fixed-Point Theorem)에 의해, $\mathcal{T}^*$ 는 유일한 고정점 $V^*$ 를 가지며 다음이 성립한다:

$V^* = \mathcal{T}^* V^*$

가치 반복의 $k$ 번째 반복에서의 오차 한계(Error Bound)는 다음과 같다:

$\|V_k - V^*\|_\infty \leq \gamma^k \|V_0 - V^*\|_\infty$

이 부등식은 가치 반복이 기하급수적(Geometric) 수렴률로 최적 가치 함수에 접근함을 보여준다. $V_0 = \mathbf{0}$ 으로 초기화하면:

$\|V_0 - V^*\|_\infty \leq \frac{R_{\max}}{1 - \gamma}$

이므로, $k$ 번째 반복 후의 오차는:

$\|V_k - V^*\|_\infty \leq \frac{\gamma^k R_{\max}}{1 - \gamma}$

3.2 수렴에 필요한 반복 횟수

$\epsilon$ -최적 가치 함수를 얻기 위해 필요한 반복 횟수 $K$ 는 다음의 부등식으로부터 도출된다:

$\frac{\gamma^K R_{\max}}{1 - \gamma} \leq \epsilon$

이를 $K$ 에 대해 풀면:

$K \geq \frac{1}{1 - \gamma} \log \frac{R_{\max}}{\epsilon(1 - \gamma)}$

따라서 필요한 반복 횟수는 $O\left(\frac{1}{1-\gamma} \log \frac{R_{\max}}{\epsilon(1-\gamma)}\right)$ 이다. 할인 계수 $\gamma$ 가 1에 가까울수록 수렴이 느려지며, 이는 장기적 보상을 중시하는 설정에서 계산 비용이 증가함을 의미한다.

3.3 종료 조건의 정당성

알고리즘의 종료 조건 $\delta < \epsilon(1-\gamma)/(2\gamma)$ 는 다음의 정리에 의해 정당화된다.

정리 2 (사후 오차 한계). 연속된 두 반복 사이의 최대 변화 $\delta_k = \|V_{k+1} - V_k\|_\infty$ 가 주어졌을 때:

$\|V_{k+1} - V^*\|_\infty \leq \frac{\gamma}{1 - \gamma} \delta_k$

따라서 $\delta_k < \epsilon(1-\gamma)/(2\gamma)$ 이면:

$\|V_{k+1} - V^*\|_\infty \leq \frac{\gamma}{1 - \gamma} \cdot \frac{\epsilon(1-\gamma)}{2\gamma} = \frac{\epsilon}{2}$

이 $\frac{\epsilon}{2}$ -최적 가치 함수로부터 도출된 탐욕적 정책은 $\epsilon$ -최적 정책임이 보장된다.

4. 계산 복잡도

4.1 시간 복잡도

각 반복에서 모든 상태에 대해 벨만 갱신을 수행하므로, 한 반복의 시간 복잡도는:

$O(|\mathcal{S}|^2 \cdot |\mathcal{A}|)$

여기서 $|\mathcal{S}|^2$ 항은 각 상태-행동 쌍에 대해 모든 후속 상태의 전이 확률을 합산하는 데 소요되는 비용이다. 전이 확률이 희소(Sparse)한 경우, 즉 각 상태-행동 쌍에서 도달 가능한 후속 상태의 수가 $b$ 개로 제한되면 한 반복의 복잡도는 $O(|\mathcal{S}| \cdot |\mathcal{A}| \cdot b)$ 로 감소한다.

총 시간 복잡도는 반복 횟수를 곱하여:

$O\left(\frac{|\mathcal{S}|^2 \cdot |\mathcal{A}|}{1 - \gamma} \log \frac{R_{\max}}{\epsilon(1-\gamma)}\right)$

4.2 공간 복잡도

가치 함수를 저장하기 위해 $O(|\mathcal{S}|)$ 의 메모리가 필요하며, 전이 확률 테이블을 저장하기 위해 $O(|\mathcal{S}|^2 \cdot |\mathcal{A}|)$ (또는 희소 표현에서 $O(|\mathcal{S}| \cdot |\mathcal{A}| \cdot b)$ )의 메모리가 필요하다.

5. 가치 반복의 변형

5.1 비동기 가치 반복(Asynchronous Value Iteration)

표준 가치 반복(동기적 가치 반복)은 모든 상태의 가치를 동시에 갱신하는 반면, 비동기 가치 반복은 상태를 임의의 순서로, 임의의 빈도로 갱신한다. 비동기 가치 반복의 수렴성은 모든 상태가 무한히 자주 갱신된다는 조건 하에서 보장된다 (Bertsekas & Tsitsiklis, 1996).

비동기 가치 반복의 주요 장점은 다음과 같다:

우선순위 기반 갱신: 가치 함수의 변화가 큰 상태를 우선적으로 갱신하여 수렴을 가속화할 수 있다.
실시간 적용: 로봇이 현재 방문 중인 상태와 인접 상태만 갱신함으로써 실시간 의사 결정에 활용할 수 있다.
메모리 효율성: 전체 상태 공간을 동시에 처리할 필요가 없으므로, 대규모 문제에서 메모리 사용량을 줄일 수 있다.

5.2 가우스-자이델 가치 반복(Gauss-Seidel Value Iteration)

가우스-자이델 가치 반복은 가치 함수를 즉시 갱신(In-Place Update)하는 기법이다. 상태 $s$ 의 가치를 갱신할 때, 이미 현재 반복에서 갱신된 상태의 값을 즉시 사용한다:

$V_{k+1}(s) = \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') \tilde{V}(s') \right]$

여기서 $\tilde{V}(s')$ 는 $s'$ 가 이미 현재 반복에서 갱신된 경우 $V_{k+1}(s')$ 을, 그렇지 않은 경우 $V_k(s')$ 을 사용한다. 이 방법은 동기적 가치 반복보다 수렴이 빠른 경우가 많으며, 추가적인 메모리가 필요하지 않다.

5.3 우선순위 소거(Prioritized Sweeping)

Moore와 Atkeson이 제안한 우선순위 소거는 벨만 잔차(Bellman Residual)가 큰 상태를 우선적으로 갱신하는 기법이다 (Moore & Atkeson, 1993). 우선순위 큐(Priority Queue)를 사용하여 갱신 순서를 관리한다.

벨만 잔차(Bellman Residual)는 다음과 같이 정의된다:

$\text{BR}(s) = \left| V_k(s) - \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s'} T(s, a, s') V_k(s') \right] \right|$

벨만 잔차가 큰 상태일수록 가치 함수의 변경이 필요한 정도가 크므로, 해당 상태를 먼저 갱신함으로써 전체 수렴 속도를 향상시킬 수 있다. 또한, 상태 $s$ 의 가치가 갱신되면 $s$ 를 후속 상태로 갖는 선행 상태(Predecessor State)들의 우선순위를 증가시켜 연쇄적인 갱신을 유도한다.

5.4 실시간 동적 프로그래밍(RTDP)

실시간 동적 프로그래밍(Real-Time Dynamic Programming, RTDP)은 Barto, Bradtke, 그리고 Singh이 제안한 기법으로, 에이전트가 환경과 상호작용하면서 방문하는 상태만 선택적으로 갱신한다 (Barto et al., 1995). RTDP는 다음의 특성을 갖는다:

시작 상태로부터 탐욕적 정책을 따라 시뮬레이션(Trial)을 수행한다.
시뮬레이션 과정에서 방문하는 상태의 가치를 벨만 갱신으로 개선한다.
목표 상태에 도달하거나 설정된 깊이에 이르면 시뮬레이션을 종료하고 새로운 시뮬레이션을 시작한다.

RTDP는 도달 가능한 상태 공간(Reachable State Space)에 집중하여 계산을 수행하므로, 전체 상태 공간이 크지만 실제 도달 가능한 상태가 적은 경우에 매우 효율적이다.

LRTDP(Labeled RTDP): Bonet과 Geffner가 제안한 LRTDP는 RTDP에 수렴 판정 레이블링(Convergence Labeling) 기법을 추가하여 수렴을 보장한다 (Bonet & Geffner, 2003). 가치 함수가 수렴한 상태에 “해결됨(Solved)” 레이블을 부착하고, 시작 상태가 해결되면 알고리즘을 종료한다.

6. 로봇 임무 계획에서의 적용 사례

6.1 그리드 세계 기반 순찰 임무

로봇 순찰 임무를 $n \times m$ 그리드 세계로 모델링하는 예를 고려하자. 상태는 로봇의 위치와 각 감시 지점의 방문 여부로 구성되며, 행동은 상하좌우 이동과 대기이다.

상태: $s = (x, y, v_1, v_2, \ldots, v_k)$ , 여기서 $(x, y)$ 는 위치, $v_i \in \{0, 1\}$ 는 $i$ 번째 감시 지점의 방문 여부
전이 확률: 이동 성공 확률 $p = 0.9$ , 정지 확률 $1 - p = 0.1$
보상: 미방문 감시 지점 방문 시 $+10$ , 이동 비용 $-1$ , 위험 지역 진입 시 $-50$
상태 공간 크기: $n \times m \times 2^k$

가치 반복을 적용하면 모든 가능한 상태에 대해 최적 행동을 결정하는 정책 테이블을 생성할 수 있다. 감시 지점이 $k = 5$ 개이고 그리드가 $10 \times 10$ 인 경우 상태 공간의 크기는 $100 \times 32 = 3{,}200$ 으로 가치 반복이 효율적으로 처리 가능하다.

6.2 에너지 인식 임무 계획

배터리 잔량을 상태 변수로 포함하는 에너지 인식 임무 계획에서, 상태는 $s = (l, e, \mathbf{m})$ 으로 정의된다. 여기서 $l$ 은 위치, $e$ 는 이산화된 배터리 잔량, $\mathbf{m}$ 은 임무 진행 상태이다. 이동 행동은 배터리를 소모하고, 충전소 방문 행동은 배터리를 회복시킨다. 가치 반복은 배터리 잔량에 따라 최적 행동이 달라지는 복잡한 정책을 자동으로 도출한다.

7. 수치적 안정성과 구현 고려 사항

7.1 수치 정밀도

부동소수점 연산의 정밀도 한계로 인해, 가치 함수의 절대값이 매우 클 경우 수치적 오차가 누적될 수 있다. 보상 함수를 정규화하거나, 가치 함수의 스케일링을 적용하여 수치적 안정성을 확보하는 것이 권장된다.

7.2 종료 상태 처리

목표 상태(Terminal State)에 도달하면 에피소드가 종료되는 에피소딕(Episodic) MDP에서는, 종료 상태의 가치를 0으로 고정하고 갱신 대상에서 제외한다. 이를 통해 벨만 수축 성질이 할인 계수 없이도 성립할 수 있으며, 목표 지향적(Goal-Directed) 임무 계획에서 수렴을 보장한다.

7.3 초기값의 영향

가치 반복의 수렴은 초기값에 무관하게 보장되지만, 적절한 초기값은 수렴 속도를 크게 향상시킬 수 있다. 예를 들어, 이전에 계산된 유사한 MDP의 가치 함수를 초기값으로 사용하는 웜 스타트(Warm Start) 기법은 임무 재계획(Replanning) 시 효과적이다.

8. 확장성 한계와 대응 전략

가치 반복의 기본 형태는 $|\mathcal{S}|$ 에 비례하는 계산 복잡도를 가지므로, 상태 공간이 매우 큰 경우 적용이 어렵다. 이에 대한 대응 전략은 다음과 같다:

상태 공간 축약: 상태 변수의 이산화 해상도를 조절하여 상태 공간의 크기를 관리한다.
함수 근사(Function Approximation): 가치 함수를 선형 모델이나 신경망으로 근사하여 대규모 상태 공간을 처리한다. 이는 근사적 동적 프로그래밍(Approximate Dynamic Programming, ADP)의 핵심 기법이다 (Powell, 2011).
분해 기법: 인수분해된 MDP(Factored MDP)의 구조적 독립성을 활용하여 지역적(Local) 가치 갱신을 수행한다.

9. 참고 문헌

Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Bertsekas, D. P. & Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming. Athena Scientific.
Moore, A. W. & Atkeson, C. G. (1993). “Prioritized Sweeping: Reinforcement Learning with Less Data and Less Time.” Machine Learning, 13(1), pp. 103-130.
Barto, A. G., Bradtke, S. J., & Singh, S. P. (1995). “Learning to Act Using Real-Time Dynamic Programming.” Artificial Intelligence, 72(1-2), pp. 81-138.
Bonet, B. & Geffner, H. (2003). “Labeled RTDP: Improving the Convergence of Real-Time Dynamic Programming.” Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS-03), pp. 12-21.
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience.
Powell, W. B. (2011). Approximate Dynamic Programming: Solving the Curses of Dimensionality, 2nd edition. Wiley.

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