벨만 방정식

Bellman equation; 벨만 방정식
어떤 상태의 가치를 "지금 받는 보상 + 다음 상태 가치의 할인값"으로 나타낸 재귀식

벨만 방정식(Bellman equation)은 마르코프 결정 과정(MDP)에서 상태나 상태·행동 쌍의 가치를 바로 다음 단계의 가치로 표현한 재귀 관계식이다. 리처드 벨먼이 1950년대 동적 계획법을 정립하며 쓴 최적성 원리에서 나왔다. 정해진 정책의 가치를 나타내는 벨만 기대 방정식과 최적 가치를 나타내는 벨만 최적 방정식 두 갈래가 있다.

강화 학습 알고리즘 대부분은 이 방정식을 푸는 방법으로 이해할 수 있다. 환경 모델을 알면 동적 계획법(가치 반복, 정책 반복)으로 정확히 풀고, 모르면 시간차 학습·Q-러닝·DQN처럼 경험 표본으로 근사해서 푼다. 서턴과 바토의 교과서도 많은 강화 학습 방법을 "벨만 최적 방정식을 근사적으로 푸는 것"으로 설명한다.^[1]

배경: 최적성 원리

벨먼은 다단계 의사결정 문제를 "최적 정책은 첫 결정이 무엇이었든 그 결과로 생긴 상태에서 남은 결정들도 최적이어야 한다"는 최적성 원리(principle of optimality)로 정리했다. 이 원리 덕분에 긴 문제를 "한 단계 + 나머지 문제"로 쪼개 재귀적으로 풀 수 있다. "동적 계획법"이라는 용어 자체가 벨먼의 1957년 책 《Dynamic Programming》에서 왔고, 같은 해 확률적 이산 MDP도 소개했다. 정책 반복은 벨먼과 하워드(Ronald Howard, 1960)에게서 나왔다.^[2]

같은 원리는 그래프 최단 경로를 구하는 벨만-포드 알고리즘에도 쓰인다. 거리 $d (v) = \min_{u} [d (u) + w (u, v)]$ 를 반복 완화하는 것이 결정론적 MDP에서의 가치 반복과 같은 구조다.

표기

할인율 $γ \in [0, 1)$ , 정책 $π (a ∣ s)$ , 전이 확률 $p (s^{'}, r ∣ s, a)$ (서턴·바토 2판 표기)를 쓴다. 이득은 $G_{t} = R_{t + 1} + γ G_{t + 1}$ 로 재귀적으로 쓸 수 있고, 벨만 방정식은 이 한 줄에 기댓값을 씌운 것이다.

상태 가치 함수: $v_{π} (s) = 𝔼_{π} [G_{t} ∣ S_{t} = s]$
행동 가치 함수: $q_{π} (s, a) = 𝔼_{π} [G_{t} ∣ S_{t} = s, A_{t} = a]$
둘의 관계: $v_{π} (s) = \sum_{a} π (a ∣ s) q_{π} (s, a)$ , $q_{π} (s, a) = \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})]$

벨만 기대 방정식

위 두 관계를 서로 대입하면 정책 $π$ 의 가치가 만족하는 방정식이 나온다.

$v_{π} (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{π} (s^{'})]$

$q_{π} (s, a) = \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ \sum_{a^{'}} π (a^{'} ∣ s^{'}) q_{π} (s^{'}, a^{'})]$

상태가 유한하면 기대 방정식은 상태 수만큼의 선형 연립방정식이다. 정책을 고정했을 때의 전이 행렬 $P^{π}$ 와 기대 보상 벡터 $r^{π}$ 로 쓰면

$v_{π} = r^{π} + γ P^{π} v_{π} ⟹ v_{π} = (I - γ P^{π})^{- 1} r^{π}$

이다. $γ < 1$ 이면 $I - γ P^{π}$ 는 항상 역행렬이 있다. 다만 역행렬 계산은 상태 수 $n$ 에 대해 $O (n^{3})$ 이라, 상태가 많으면 반복법을 쓴다.

벨만 최적 방정식

최적 가치 $v_{*} (s) = \max_{π} v_{π} (s)$ 는 정책에 대한 평균 대신 최대를 취한 방정식을 만족한다.

$v_{*} (s) = \max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v_{*} (s^{'})]$

$q_{*} (s, a) = \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ \max_{a^{'}} q_{*} (s^{'}, a^{'})]$

최댓값 연산 $\max$ 때문에 더는 선형이 아니다. 유한 MDP에서 벨만 최적 방정식의 해는 유일하며,^[1] $q_{*}$ 를 알면 각 상태에서 $\arg \max_{a} q_{*} (s, a)$ 를 고르는 탐욕 정책이 최적 정책이다. 한 단계 앞만 보고 고르는 탐욕 선택이 장기적으로도 최적인 까닭은 $v_{*}$ 가 이미 미래 전체를 반영하고 있기 때문이다.

구분	벨만 기대 방정식	벨만 최적 방정식
대상	주어진 정책 $π$ 의 가치	최적 가치 $v_{}, q_{}$
다음 행동 처리	정책 확률로 평균 $\sum_{a^{'}} π (a^{'} ∣ s^{'}) \cdot$	최대 $\max_{a^{'}}$
형태	선형 연립방정식	비선형(max)
동적 계획법	정책 평가	가치 반복
표본 기반 학습	TD(0), SARSA, 기대 SARSA	Q-러닝, DQN

벨만 연산자와 수렴

벨만 방정식의 우변을 함수에서 함수로 가는 연산자로 보면 이해가 쉽다.

$(T^{π} v) (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v (s^{'})]$ , $(T^{*} v) (s) = \max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ v (s^{'})]$

$v_{π}$ 와 $v_{*}$ 는 각각 $T^{π}$ , $T^{*}$ 의 고정점이다. 두 연산자는 최대 노름에서 $γ$ -축약(contraction)이다.

$‖ T v - T u ‖_{\infty} \leq γ ‖ v - u ‖_{\infty}$

바나흐 고정점 정리에 따라 고정점은 하나뿐이고, 아무 $v_{0}$ 에서 시작해 $T$ 를 반복 적용하면 오차가 매번 $γ$ 배 이하로 줄며 고정점에 수렴한다. 가치 반복이 수렴하는 근거가 이것이다. $γ$ 가 1에 가까우면 수렴이 느려진다.

가치 반복과 정책 반복

환경 모델 $p$ 를 알 때 벨만 방정식을 푸는 두 고전 알고리즘이다.

가치 반복(value iteration): $v_{k + 1} = T^{*} v_{k}$ 를 수렴할 때까지 반복하고, 마지막에 탐욕 정책을 뽑는다. 한 번의 반복 비용은 $O (| S |^{2} | A |)$ .
정책 반복(policy iteration): (1) 정책 평가: 현재 정책의 $v_{π}$ 를 기대 방정식으로 구한다. (2) 정책 개선: $v_{π}$ 에 대해 탐욕적인 새 정책을 만든다. 정책이 바뀌지 않으면 멈춘다. 정책 개선 정리에 따라 매 단계 정책은 나빠지지 않고, 유한 MDP에서 정책 수가 유한하므로 유한 번 안에 끝난다. 보통 가치 반복보다 반복 횟수는 훨씬 적지만 한 번의 평가가 비싸다.
일반화된 정책 반복(GPI): 평가를 끝까지 하지 않고 몇 번만 하고 개선하는 식으로 둘을 섞은 일반적 틀. 서턴·바토는 거의 모든 강화 학습 방법을 GPI로 설명한다.

다음 코드는 Gymnasium(1.x)의 FrozenLake 환경이 공개하는 전이 표 env.unwrapped.P를 써서 두 방법을 구현한다. P[s][a]는 (확률, 다음 상태, 보상, 종료 여부) 튜플의 목록이다.

import numpy as np
import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
P = env.unwrapped.P            # P[s][a] = [(확률, 다음 상태, 보상, 종료 여부), ...]
nS, nA = env.observation_space.n, env.action_space.n
gamma, theta = 0.99, 1e-8

def q_from_v(V, s):
    """한 상태의 모든 행동에 대해 sum_{s'} p (r + gamma V(s'))"""
    return np.array([sum(p * (r + gamma * V[s2] * (not done))
                         for p, s2, r, done in P[s][a]) for a in range(nA)])

def value_iteration():
    V = np.zeros(nS)
    while True:
        delta = 0.0
        for s in range(nS):
            v_new = q_from_v(V, s).max()       # 벨만 최적 방정식으로 갱신
            delta = max(delta, abs(v_new - V[s]))
            V[s] = v_new
        if delta < theta:
            break
    pi = np.array([q_from_v(V, s).argmax() for s in range(nS)])
    return V, pi

def policy_iteration():
    pi = np.zeros(nS, dtype=int)
    while True:
        # 1) 정책 평가: 벨만 기대 방정식을 선형 연립방정식으로 바로 푼다
        P_pi = np.zeros((nS, nS)); R_pi = np.zeros(nS)
        for s in range(nS):
            for p, s2, r, done in P[s][pi[s]]:
                R_pi[s] += p * r
                if not done:
                    P_pi[s, s2] += p * gamma
        V = np.linalg.solve(np.eye(nS) - P_pi, R_pi)
        # 2) 정책 개선: 가치에 대해 탐욕적으로
        new_pi = np.array([q_from_v(V, s).argmax() for s in range(nS)])
        if np.array_equal(new_pi, pi):
            return V, pi
        pi = new_pi

V1, pi1 = value_iteration()
V2, pi2 = policy_iteration()
print(np.round(V1.reshape(4, 4), 3))
print("두 방법의 가치 차이:", np.abs(V1 - V2).max())   # 1e-7 수준

가치 반복 코드는 새 값을 같은 배열에 바로 덮어쓰는 제자리(in-place) 갱신이다. 이렇게 해도 수렴하며, 보통 두 배열을 번갈아 쓰는 방식보다 빨리 수렴한다. 미끄러운 FrozenLake에서는 시작 칸의 최적 가치가 약 0.54로 나온다(목표 도달 확률에 할인이 곱해진 값).

표본 기반 근사: 강화 학습으로

실제 문제에서는 $p (s^{'}, r ∣ s, a)$ 를 모르거나, 알아도 상태가 너무 많다. 그래서 강화 학습은 벨만 방정식의 기댓값을 표본 하나로 바꾸고, 표 대신 함수 근사를 쓴다.

방법	근사하는 방정식	갱신 목표(타깃)
TD(0)	기대 방정식 $v_{π}$	$r + γ V (s^{'})$
SARSA	기대 방정식 $q_{π}$	$r + γ Q (s^{'}, a^{'})$ , $a^{'}$ 는 실제로 고른 행동
Q-러닝	최적 방정식 $q_{*}$	$r + γ \max_{a^{'}} Q (s^{'}, a^{'})$
DQN	최적 방정식 $q_{*}$	$r + γ \max_{a^{'}} Q_{\bar{θ}} (s^{'}, a^{'})$ , 목표 신경망 $\bar{θ}$ 사용
소프트 Q 학습, SAC	소프트 벨만 방정식	$r + γ 𝔼_{a^{'}} [Q (s^{'}, a^{'}) - α \log π (a^{'} ∣ s^{'})]$
분포형 강화 학습(C51 등)	분포 벨만 방정식	이득의 기댓값 대신 분포 전체를 갱신^[3]

딥러닝으로 근사할 때는 벨만 오차를 손실로 둔다.

$L (θ) = 𝔼_{(s, a, r, s^{'})} [(r + γ \max_{a^{'}} Q_{\bar{θ}} (s^{'}, a^{'}) - Q_{θ} (s, a))^{2}]$

여기서 타깃도 같은 신경망에 의존하므로 일반 지도 학습과 달리 목표가 움직인다. 함수 근사, 부트스트래핑(추정값으로 추정값을 갱신), 오프 폴리시 학습이 한꺼번에 쓰이면 발산할 수 있는데, 서턴·바토는 이를 "치명적 삼요소"(deadly triad)라 부른다.^[4] DQN의 목표 신경망과 경험 재생은 이 불안정을 줄이려는 장치다. 또 $\max$ 연산은 잡음 섞인 추정값 중 큰 것을 골라 과대평가를 낳는데, Double DQN과 TD3의 쌍둥이 크리틱이 이를 줄인다.

변형

유한 수평선: 남은 시간 $h$ 를 상태에 포함해 $v_{h} (s) = \max_{a} \sum p [r + v_{h - 1} (s^{'})]$ 로 거꾸로 푼다. 할인이 없어도 된다.
평균 보상: 할인 없이 단위 시간당 평균 보상 $ρ$ 를 최대화하는 경우 $v (s) + ρ = \max_{a} \sum p [r + v (s^{'})]$ 꼴이 된다.
연속 시간: 연속 시간 최적 제어에서는 해밀턴-야코비-벨만(HJB) 편미분 방정식이 된다.
소프트(엔트로피 정규화): $\max$ 대신 $α \log \sum_{a} \exp (q / α)$ 를 쓴다. 최대 엔트로피 강화 학습, 최대 엔트로피 역강화 학습의 기초다.

경제학에서

벨만 방정식과 동적 계획법은 경제학의 동태적 최적화에도 쓰인다. 재고 이론, 소비·저축 결정, 경제 성장 모형이 "오늘의 선택 + 내일 상태의 가치" 꼴의 재귀식으로 표현된다. 로버트 머턴의 1973년 시점 간 자본 자산 가격 결정 모형(ICAPM)이 대표적인 응용이고,^[5] 스토키·루커스·프레스콧의 《Recursive Methods in Economic Dynamics》(1989)가 이 방법을 경제학 교재로 정리했다. 상태 변수가 늘면 계산량이 폭발하는 "차원의 저주"라는 말도 벨먼이 만들었다.^[2]

같이 보기

각주

↑ ^1.0 ^1.1 Richard S. Sutton, Andrew G. Barto, 《Reinforcement Learning: An Introduction》 2판, MIT Press, 2018, 3.6절. 저자 공개본
↑ ^2.0 ^2.1 Sutton & Barto 2판, 4장 참고 문헌 및 역사 절. Bellman(1957a, 1957b), Howard(1960).
↑ Marc G. Bellemare, Will Dabney, Rémi Munos, 〈A Distributional Perspective on Reinforcement Learning〉, ICML 2017. arXiv:1707.06887
↑ Sutton & Barto 2판, 11.3절 The Deadly Triad. 서턴(1995)이 처음 지적했고 치치클리스·밴 로이(1997)가 분석했다.
↑ Robert C. Merton, 〈An Intertemporal Capital Asset Pricing Model〉, Econometrica 41(5), 867~887, 1973. doi:10.2307/1913811

참고 문헌

[sb3-1] 1.0 ^1.1 Richard S. Sutton, Andrew G. Barto, 《Reinforcement Learning: An Introduction》 2판, MIT Press, 2018, 3.6절. 저자 공개본

[sbdp-2] 2.0 ^2.1 Sutton & Barto 2판, 4장 참고 문헌 및 역사 절. Bellman(1957a, 1957b), Howard(1960).

[c51-3] Marc G. Bellemare, Will Dabney, Rémi Munos, 〈A Distributional Perspective on Reinforcement Learning〉, ICML 2017. arXiv:1707.06887

[triad-4] Sutton & Barto 2판, 11.3절 The Deadly Triad. 서턴(1995)이 처음 지적했고 치치클리스·밴 로이(1997)가 분석했다.

[merton-5] Robert C. Merton, 〈An Intertemporal Capital Asset Pricing Model〉, Econometrica 41(5), 867~887, 1973. doi:10.2307/1913811

[1]

[2]

[3]

[4]

[5]