35. 불규칙한 결정 시점: Semi-MDP 정식화

34편은 이렇게 끝났다 — DES 환경에서는 결정 시점 사이의 간격 ${\tau }_k=t_{k+1}-t_k$가 고정 상수가 아니라 이벤트가 결정하는 확률적 값이고, 그래서 에이전트의 시계(step 번호 $k$)와 모델의 시계(시뮬레이션 시각 $t$)가 분리된다. 이 글은 그 분리가 표준 MDP 정식화를 정확히 어디서 깨뜨리는지, 그리고 Semi-MDP(SMDP) 가 그것을 어떻게 고치는지를 다룬다. 시리즈에서 가장 수학적인 글 중 하나지만, 핵심 아이디어는 한 문장이다 — 할인을 스텝 수가 아니라 경과 시간에 걸어라.

표준 MDP의 숨은 가정

RL 시리즈 2편에서 본 대로, 표준 MDP $⟨S,A,P,R,\gamma ⟩$는 이산 스텝 $t=0,1,2,\dots$마다 결정을 내리고, return을 다음과 같이 정의한다.

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$

이 식이 말하는 것: 미래 보상은 스텝 하나를 건널 때마다 $\gamma$배씩 깎인다. 여기에는 암묵적 가정이 숨어 있다 — 모든 스텝의 실제 시간 길이가 같다는 것이다. Atari 게임(모든 스텝 = 1프레임)이나 바둑(모든 스텝 = 한 수)에서는 이 가정이 자연스러워서 아무도 의식하지 않는다. $\gamma$가 표현하는 time-value(“미래의 보상은 지금의 보상보다 덜 가치 있다”)가 스텝 단위로 균일하게 흐르는 것과 실제 시간 단위로 균일하게 흐르는 것이 같은 말이 되기 때문이다.

DES 환경에서는 이 가정이 무너진다. 34편의 예를 다시 가져오면 — batch 장비 앞에서 “지금 출발시킨다”를 고르면 장비가 곧 다음 lot을 부르므로 몇 분 뒤에 다음 결정이 오지만, “채워질 때까지 기다린다”를 고르면 다음 lot 도착까지 수십 분 뒤에야 다음 결정이 온다. 간격 $\tau$가 확률적일 뿐 아니라, 지금 상태와 내가 고른 행동에 의존한다.

무엇이 깨지나: 왜곡의 방향

$\gamma$를 스텝마다 동일하게 적용하면, 1분짜리 스텝과 1시간짜리 스텝이 같은 비율로 할인된다. 결과는 체계적 왜곡이다 — 시간을 오래 소모하는 행동일수록 그 뒤의 미래가 부당하게 덜 할인된다. 실제로는 1시간 뒤의 보상인데, 장부상으로는 “한 스텝 뒤”로 기록되어 1분 뒤의 보상과 같은 대접을 받는 것이다.

장난감 수치 예로 확인하자. 어떤 상태에서 두 행동 중 하나를 고른다. 어느 쪽이든 즉시 보상은 0이고, 다음 결정 시점에 보상이 하나 실현된다.

• 행동 A (“지금 출발”): $\tau =1$분 뒤 다음 결정, 그때 보상 $10$.
• 행동 B (“기다린다”): $\tau =60$분 뒤 다음 결정, 그때 보상 $11$.

(a) 스텝 할인은 $\gamma =0.9$를 스텝당 한 번 적용하고, (b) 시간 할인은 분당 연속 할인율 $\beta =0.005$로 $e^{-\beta \tau }$를 적용한다.

행동	보상	$\tau$ (분)	(a) 스텝 할인: $\gamma \cdot r$	(b) 시간 할인: $e^{-\beta \tau }\cdot r$
A (지금 출발)	10	1	$0.9\times 10=9.0$	$e^{-0.005}\times 10\approx 9.95$
B (기다린다)	11	60	$0.9\times 11=9.9$	$e^{-0.3}\times 11\approx 8.15$

스텝 할인 기준으로는 $9.9>9.0$이라 B가 우월하지만, 경과 시간 기준으로는 $9.95>8.15$라 A가 우월하다 — 같은 보상 흐름인데 행동 선호가 뒤집힌다. (a)의 장부에서 B의 60분은 “한 스텝”으로 압축되어 1분과 똑같이 취급됐기 때문이다. 시간이 곧 돈인 fab에서 — 기다림은 cycle time이고, cycle time은 비용이다 — 이 왜곡을 안고 학습하면 에이전트는 “오래 기다리는 행동”의 비용을 체계적으로 과소평가한다.

Semi-MDP 정식화

Semi-MDP는 이 문제를 정면으로 고친다 — 전이의 결과에 소요 시간을 포함시킨다. 표준 MDP의 전이가 $(s,a)\to (s^{\prime },r)$이었다면, SMDP의 전이는

$$(s,a)\to (s^{\prime },r,\tau )$$

즉, 상태 $s$에서 행동 $a$를 하면 다음 상태 $s^{\prime }$, 보상 $r$과 함께 소요 시간 $\tau >0$가 확률적으로 함께 실현되며, $\tau$의 분포 역시 $(s,a)$에 의존한다. Markov property는 그대로다 — $(s^{\prime },\tau )$의 분포는 현재 $(s,a)$에만 의존한다. 34편의 DES wrapper가 돌려주던 것이 정확히 이 tuple이다: step(action) 한 번이 (다음 결정 시점의 관측, 구간 보상, 흘러간 시뮬레이션 시간)을 실현한다.

할인은 스텝이 아니라 시간에 건다. 연속 시간 할인율 $\beta >0$을 도입하면, optimal action-value function에 대한 Bellman optimality equation은 다음과 같다. (RL 시리즈 3편의 $Q_{\ast }(s,a)=R_s^a+\gamma {\sum }_{s^{\prime }}{P}_{s{s}^{\prime }}^a{\max }_{a^{\prime }}{Q}_{\ast }(s^{\prime },a^{\prime })$와 나란히 놓고 비교해 보자.)

$$Q_{\ast }(s,a)=E[R(s,a)+e^{-\beta \tau }\underset{a^{\prime }\in A}{\max }{Q}_{\ast }(s^{\prime },a^{\prime })]$$

기댓값은 $(s^{\prime },\tau )$와 구간 내 보상 실현의 결합 분포에 대해 취한다. 성분별로 뜯어 보면:

• $e^{-\beta \tau }$ — 표준 MDP의 $\gamma$ 자리를 차지한 시간 의존 할인 factor다. $\tau$가 클수록 지수적으로 작아진다: 오래 걸린 전이일수록 그 너머의 미래를 더 많이 깎는다. 위 표의 왜곡이 정확히 여기서 교정된다 — 행동 B의 60분은 이제 $e^{-60\beta }$라는 무거운 할인을 정직하게 치른다. 할인이 전이의 확률 변수 $\tau$에 걸려 있으므로 기댓값 밖으로 꺼낼 수 없다는 점이 표준 MDP와의 구조적 차이다.
• $R(s,a)$ — 전이 구간 $[0,\tau )$ 동안 흘러 들어온 보상의 할인 누적이다. DES에서 한 step 사이에도 이벤트들이 보상을 만들 수 있으므로(구간 중간에 lot이 완료되는 등), 구간 내 보상 rate를 $r(u)$라 하면

$$R(s,a)={\int }_0^{\tau }{e}^{-\beta u}r(u)du$$

이 식이 말하는 것: 구간 안의 보상도 공짜가 아니다 — 구간 시작으로부터 $u$만큼 지난 뒤 실현된 보상은 자기 몫의 할인 $e^{-\beta u}$를 받는다. ($R(s,a)$ 자체가 $\tau$와 보상 실현에 따라 달라지는 확률량이고, Bellman 식 바깥의 기댓값이 이것까지 함께 평균한다.) 즉 “구간 보상을 한 덩어리로 뭉쳐 스텝 시작 시점에 준다”는 근사조차 SMDP에서는 엄밀히는 틀린 것이고, 보상이 구간의 어디서 실현됐는지가 값에 반영된다.

• ${\max }_{a^{\prime }}{Q}_{\ast }(s^{\prime },a^{\prime })$ — 다음 결정 시점에서의 최적 행동 가치. 이 부분은 표준 MDP와 완전히 같다. 바뀐 것은 오직 “미래를 얼마나 깎는가”뿐이다.

이 정식화가 표준 MDP의 순수한 일반화임을 확인해 두자. 모든 전이가 $\tau \equiv 1$(균일 시간)인 특수 경우를 대입하면 $e^{-\beta \tau }=e^{-\beta }$가 상수가 되고, $\gamma =e^{-\beta }$로 놓으면 RL 시리즈 3편의 Bellman optimality equation이 그대로 복원된다. 즉 표준 MDP는 “모든 스텝의 길이가 같은” SMDP다. 우리가 여태 써 온 $\gamma$는 사실 “단위 시간당 할인율 $e^{-\beta }$“였는데, 스텝 길이가 균일한 환경에서는 그 구분이 보이지 않았을 뿐이다.

학습 알고리즘 관점의 좋은 소식: 바뀌는 곳이 국소적이다. 예컨대 Q-learning의 target이 $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$에서 $r+e^{-\beta \tau }{\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$로 바뀔 뿐이고, $\tau$는 시뮬레이터가 어차피 알고 있는 값이다(34편의 wrapper에서 info에 ${\tau }_k$를 실어 보내면 된다). 정식화의 교정이 구현에서는 할인 factor 한 줄의 교체로 나타난다.

평균 보상 관점: 할인이 애초에 맞는가

한 걸음 더 나가면, fab 같은 환경에서는 할인 자체가 부자연스럽다는 문제 제기가 가능하다. 할인은 원래 “언젠가 끝나는 과제”나 “미래 불확실성의 반영”을 위한 장치인데, fab은 끝나지 않는 24시간 연속 운영이다(34편의 continuing task 논의). 3주 뒤에 완료될 lot의 가치를 지수적으로 깎아야 할 본질적 이유가 없다.

대안은 평균 보상(average reward) 기준 — 할인 없이, 단위 시간당 벌어들이는 보상의 장기 평균을 최대화하는 것이다.

$${\rho }_{\pi }=\underset{T\to \infty }{\lim }\frac{1}{T}{E}_{\pi }\left[{\int }_0^{T}r(u)du\right]$$

이 식이 말하는 것: 정책 $\pi$의 성적을 “출발 지점 기준으로 할인된 총합”이 아니라 “긴 시간 지평에서 시간당 벌이” 로 매긴다. 분모가 스텝 수가 아니라 경과 시간 $T$ 라는 것이 SMDP에서 본질적인 구분이다 — 스텝마다 길이가 다르므로, “스텝당 평균 보상”과 “시간당 평균 보상”은 다른 양이고 다른 정책을 낳는다. 시간당 기준에서는 “짧은 스텝을 많이 밟는 정책”이 스텝 수로 유리해지는 착시가 사라진다.

두 관점의 실무적 차이를 짧게 정리하면:

• 할인 기준: $\beta$로 근시안의 정도를 조절할 수 있다 — $\beta$가 크면 단기 성과 중심, 작으면 장기 중심. 알고리즘 생태계도 성숙해 있다(대부분의 표준 RL 알고리즘이 할인 기준). 대신 $\beta$라는, 물리적 근거가 약한 hyperparameter가 하나 생긴다.
• 평균 보상 기준: fab이 실제로 관리하는 지표 — 시간당 처리량(throughput), 일평균 tardiness(납기 대비 지연 시간) — 와 목적함수가 직결된다. 정식화로는 더 정직하지만, 지원하는 알고리즘이 상대적으로 적고 학습이 까다롭다.

실무에서는 할인 기준으로 학습하되 $\beta$를 충분히 작게 잡아 평균 보상의 근사로 쓰는 절충이 흔하다.

옵션: SMDP의 또 다른 얼굴

SMDP는 DES 전용 도구가 아니다. hierarchical RL(행동을 여러 층위로 조직하는 강화학습)의 수학적 기초이기도 하다. 핵심 관찰: 여러 primitive 스텝에 걸치는 매크로 행동 — 이를 option이라 부른다. 예컨대 “이 lot의 다음 3개 공정을 툴그룹 X 계열로 몰아서 처리한다” 같은, 시작 조건·내부 정책·종료 조건을 갖춘 행동 덩어리 — 을 실행하면, 그것이 끝날 때까지 걸린 스텝 수가 매번 다르다. 즉 option 수준에서 문제를 보면, 밑이 표준 MDP라도 위는 자연스럽게 SMDP가 된다 — option 하나의 실행이 가변 소요 시간 $\tau$를 가진 SMDP 전이 하나에 대응한다. 이 관점을 정립한 것이 Sutton, Precup, Singh의 1999년 논문으로, “MDP와 SMDP 사이”라는 제목 그대로 두 틀을 잇는 다리다. DES에서는 환경이 가변 $\tau$를 강제해서 SMDP가 됐고, 옵션에서는 에이전트가 행동을 덩어리로 묶어서 SMDP가 됐다 — 도착 경로는 다르지만 도착지의 수학은 위에서 전개한 그 식이다.

멀티에이전트 관점: 비동기 SMDP들

fab 규모에서는 단일 에이전트가 모든 툴그룹의 결정을 다 내리는 대신, 툴그룹별로 에이전트를 하나씩 두는 분해가 자연스럽다. 이때 정식화가 어떻게 되는지만 짚어 두자.

각 에이전트는 자기만의 결정 시점을 가진다 — 포토 툴그룹의 에이전트는 포토 장비가 빌 때, 식각 툴그룹의 에이전트는 식각 장비가 빌 때 깨어난다. 서로 다른 에이전트의 결정 시점은 동기화되어 있지 않으므로, 전체 시스템은 하나의 공유 시뮬레이션 시간 축 위에서 비동기적으로 도는 SMDP들의 묶음이 된다.

• 장점 — 행동 공간 분해: 결합 행동 공간(모든 툴그룹의 결정을 한꺼번에 고르는 공간)은 툴그룹 수에 지수적으로 커지는데, 에이전트별로 쪼개면 각자는 자기 큐의 작은 행동 공간만 다루면 된다.
• 대가 1 — nonstationarity: 한 에이전트의 눈에 다른 에이전트들은 환경의 일부다. 그런데 그들도 학습 중이라 행동이 계속 바뀐다 — 즉 환경의 전이 분포가 시간에 따라 변하는 nonstationarity(비정상성; 환경의 통계적 성질이 고정되어 있지 않은 상황)가 생긴다. 단일 에이전트 RL의 수렴 논리는 환경이 고정되어 있다는 가정 위에 서 있으므로, 이 가정이 깨진다.
• 대가 2 — credit assignment의 증폭: fab의 성과는 공동 성과다. lot 하나의 cycle time에는 수십 개 툴그룹의 결정이 얽혀 있어서, 받은 보상을 어느 에이전트의 어느 행동 덕분/탓으로 배분할 것인가 하는 credit assignment 문제(보상을 과거 행동들에 귀속시키는 문제, 34편)가 에이전트 축으로 한 번 더 어려워진다.

여기서는 정식화 수준의 지도만 그려 두고, 실제 연구들이 이 구조를 어떻게 다뤘는지는 38편(예정)에서 사례로 살핀다.

정리

• 표준 MDP의 ${\gamma }^t$ 할인에는 “모든 스텝의 실제 시간 길이가 같다” 는 암묵적 가정이 있다. DES 환경(34편)에서는 결정 간격 $\tau$가 확률적이고 상태·행동 의존이라 이 가정이 깨지고, 스텝 할인은 오래 걸리는 행동의 미래를 부당하게 덜 할인한다 — 장난감 예에서 행동 선호가 뒤집히는 것을 확인했다.
• Semi-MDP는 전이를 $(s,a)\to (s^{\prime },r,\tau )$로 확장하고 할인을 $e^{-\beta \tau }$로 시간에 건다. Bellman optimality equation에서 바뀌는 것은 할인 factor뿐이며, $\tau \equiv 1$, $\gamma =e^{-\beta }$로 놓으면 표준 MDP가 복원된다 — 표준 MDP는 SMDP의 특수 경우다.
• 끝나지 않는 연속 운영에서는 할인 대신 시간당 평균 보상 $\rho$ 최대화가 대안이다. “스텝당”이 아니라 “시간당”이라는 구분이 SMDP에서 본질적이고, 평균 보상 기준은 fab의 장기 처리량 지표와 직결된다.
• SMDP는 hierarchical RL의 기초이기도 하다 — 여러 스텝짜리 option 하나의 실행이 SMDP 전이 하나다 (Sutton–Precup–Singh 1999).
• 툴그룹별 멀티에이전트 분해는 비동기 SMDP들을 낳는다. 행동 공간은 쪼개지지만 nonstationarity와 공동 성과의 credit assignment라는 대가를 치른다 — 연구 사례는 38편(예정)으로.

정식화는 갖춰졌다. 다음 글 36편(예정)에서는 이론에서 실전으로 — 학습용 시뮬레이터를 실제로 어떻게 설계하고, 34편이 미뤄 둔 보상 설계를 어떻게 풀 것인가를 다룬다.

참고문헌

• R. S. Sutton, D. Precup, S. Singh, “Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning”, Artificial Intelligence 112(1–2), 1999. DOI