동적 계획법과 확률 동적 계획법으로 설계하는 순차 의사결정

순차 의사결정은 상태 변화와 함께 최적화한다

작업 연구에서 Dynamic Programming(DP)과 Stochastic Dynamic Programming(SDP)은 여러 단계로 이어지는 의사결정의 최적해를 구하는 기법이다. Bellman의 최적성 원리를 바탕으로 현재 상태와 행동, 다음 상태로의 전이를 연결한다.

결정론적 전이를 전제로 하면 DP로 모델링할 수 있다. 수요, 시간, 고장처럼 다음 상태가 확률적으로 달라지는 경우에는 SDP로 확장하며, 이는 Markov Decision Process(MDP) 구조와 맞닿아 있다. 공급망, 생산, 에너지, 금융 영역에서 정책을 설계할 때 활용된다.

DP는 다단계 문제를 상태 전이와 누적 비용 또는 보상으로 나누어 푸는 방법이다. 결정론적 전이 아래에서는 Bellman 방정식으로 각 부분 문제의 최적값을 누적 계산한다.

SDP는 확률적 수요·시간·고장 등 불확실한 전이를 포함한 DP의 확장이다. MDP의 (S, A, P, r, γ) 형식으로 상태, 행동, 전이확률, 보상, 할인요소를 나타내고 기대값 기준의 Bellman 연산자로 정책을 최적화한다.

가치 반복은 다음 식으로 표현한다.

V(s) ← max_a [ r(s,a) + γ·Σ_s' P(s'|s,a)·V(s') ]

정책 반복은 고정 정책의 가치함수를 계산하는 정책평가와, 상태별 argmax_a를 선택하는 정책개선을 번갈아 수행한다.

모델의 성패는 상태와 전이 설계에서 갈린다

상태공간 S는 모델 성능과 계산 복잡도에 직접 영향을 준다. 상태가 지나치게 세분화되면 상태 폭발이 발생하므로 상태 집계나 특징화가 필요하다.

전이모형 P는 DP에서는 결정적 전이를, SDP에서는 확률 전이를 표현한다. 확률 전이는 경험이나 도메인 지식을 토대로 추정할 수 있으며, 빈도 또는 베이지안 추정도 활용한다. 보상 또는 비용 r에는 즉시효용뿐 아니라 페널티와 위반 비용을 함께 반영한다.

할인요소가 γ<1이면 수축사상 성질에 따라 가치 반복의 수렴을 보장한다. 무할인 유한기간 문제는 후진귀납(backward induction)으로 풀 수 있다.

가치 반복은 구현이 단순하고 폭넓게 적용할 수 있지만, 수렴 속도는 문제 구조에 좌우된다. 정책 반복은 선형연립 해법 또는 반복 평가로 정책을 평가한 뒤 개선하며, 빠르게 수렴하는 경향이 있다. 다단계 제약이 포함될 때는 라그랑주 이완이나 페널티 기법을 결합할 수 있다.

대규모 문제에서는 Approximate DP(ADP)를 사용한다. 선형·신경망 함수근사, 상태 집계, 시뮬레이션 기반 몬테카를로 평가가 이에 해당한다. 모델을 알 수 없는 경우에는 강화학습(RL)의 샘플 기반 정책 개선으로 이어지며, 오프폴리시와 온폴리시 사이의 트레이드오프를 고려한다.

시간·공간 분해, 히어라키 DP, 시나리오 축소, 컷 생성 기반 근사도 상태 폭발을 줄이는 방법이다. 캐시와 메모이제이션, 희소 행렬, 병렬화는 실제 운영 성능을 개선하는 데 쓰인다.

재고부터 리밸런싱까지 이어지는 적용 모델

재고 및 주문 정책 (s, S)에서는 수요 분포, 리드타임, 보유·부족 비용, 주문 고정·가변비용을 입력으로 사용한다. SDP가 재고 상태와 주문 결정의 기대비용을 최소화하고, 시뮬레이션으로 서비스레벨을 검증한다. 결과는 임계재고 수준, 안전재고, 주문 배치 정책으로 이어진다.

예방·예측 정비에서는 고장 확률, 상태 진단 신뢰도, 다운타임·정비비를 모델에 넣는다. MDP는 수리·교체·유지 중 무엇을 선택할지 결정하며, 잔여수명(RUL)을 반영해 가치함수를 갱신한다. 상태 구간별 최적 정비 시점과 비용-가용성 균형 정책을 얻을 수 있다.

동적 라우팅과 차량경로 문제는 시변 이동시간 분포, 운행 제약, 서비스 시간 윈도를 다룬다. SDP 또는 롤링호라이즌으로 경로를 재계획하고 지연 페널티를 고려해 실시간 경로, 재루팅 트리거 조건, 지연률·연료비 KPI 개선으로 연결한다.

에너지 저장장치(ESS) 운영과 전력 입찰에서는 가격 시계열 또는 분포, 충방전 효율, SoC 제약이 주요 입력이다. SDP는 충방전 결정을 내릴 때 제약 위반 페널티와 수명비용을 포함하며, 가격 민감 정책과 수익-수명 트레이드오프의 균형을 산출한다.

포트폴리오 리밸런싱은 수익·공분산 추정, 거래비용, 리스크 한도를 바탕으로 한다. MDP 또는 ADP로 거래 임계값을 정하고 포지션 조정 빈도를 최적화해 규칙 기반 리밸런싱 전략과 턴오버·샤프 지표 개선을 목표로 한다.

SDP 반복 과정과 예외 처리

⤢✕

전이 확률의 합이 맞지 않으면 정규화하고 로그 경고를 남긴다. SoC, 용량, 예산 제약을 위반하면 페널티를 부과한 뒤 유효 상태로 투영한다. 수렴이 정체될 때는 Modified Policy Iteration, 상태 집계, γ 조정을 검토할 수 있다.

결정론적 DP와 확률적 SDP의 운영 차이

항목	DP(결정론)	SDP(확률론)
성능	전이 결정성으로 연산 단순, 빠른 수렴 경향	기대 연산 포함으로 비용 증가, 샘플·시나리오 병렬화로 보완
확장성	상태 폭발 시 근사 필요	상태·시나리오 동시 폭발, ADP·RL·샘플링 필수
일관성(최적성)	구조적 가정 하 전역 최적 보장	γ<1, 충족 가정 하 기대 최적 정책 보장
안정성(수렴)	후진귀납/수축사상으로 안정적	확률성·근사로 수렴 속도 변동, 가속 기법 요구
운영 편의	모델 구성 용이	데이터 추정·교정 필요, 모형 유지보수 비용 증가

가치 반복 템플릿을 실행할 때의 전제

유한 상태·행동 MDP를 전제로 하며, P.shape = (S, A, S), R.shape = (S, A), 0 ≤ γ < 1을 사용한다. 실행 환경은 Python 3.10+와 numpy 1.26+이다.

import numpy as np

def value_iteration(P, R, gamma=0.95, theta=1e-6, max_iter=10000):
    S, A, S2 = P.shape
    assert S == S2
    V = np.zeros(S, dtype=float)
    for it in range(max_iter):
        V_prev = V.copy()
        # Q(s,a) = r(s,a) + γ Σ P(s'|s,a)V(s')
        Q = R + gamma * np.einsum('sas,s->sa', P, V_prev)
        V = Q.max(axis=1)
        if np.max(np.abs(V - V_prev)) < theta:
            break
    # Greedy policy
    Q = R + gamma * np.einsum('sas,s->sa', P, V)
    pi = np.argmax(Q, axis=1)
    return V, pi

# 예시(작은 MDP)
S, A = 3, 2
P = np.zeros((S, A, S))
R = np.zeros((S, A))

# 전이/보상 설정(예시)
P[0,0,0]=0.1; P[0,0,1]=0.9; R[0,0]=1.0
P[0,1,2]=1.0; R[0,1]=0.5
P[1,0,1]=0.7; P[1,0,2]=0.3; R[1,0]=0.0
P[1,1,0]=1.0; R[1,1]=0.2
P[2,0,2]=1.0; R[2,0]=0.0
P[2,1,2]=1.0; R[2,1]=0.0

V_star, pi_star = value_iteration(P, R, gamma=0.95)
print("V*:", V_star)
print("pi*:", pi_star)  # 상태별 최적 행동 인덱스

수렴을 앞당기려면 Modified Policy Iteration이나 Gauss–Seidel 업데이트를 사용할 수 있다. 보상 스케일링, γ 조정, θ(허용오차), max_iter 관리는 수치 안정성과 연관된다. 대규모 환경에서는 희소 행렬, 배치 연산, JIT(Numba), 분산 샘플링을 적용한다.

정책 설계가 만드는 운영상 효과

재고·정비·라우팅에서는 총비용 5~~20% 절감과 서비스레벨·가동률 2~~5%p 개선을 기대할 수 있다. 에너지와 금융 트레이딩에서는 기대수익 증대와 변동성(리스크) 감소를 목표로 한다.

임계값과 규칙을 도출해 정책의 해석 가능성을 확보할 수 있고, 운영 일관성도 강화된다. 불확실성 아래의 의사결정은 재현성과 강건성을 높이는 방향으로 설계할 수 있다.