제약 마르코프 결정 과정

최적설계 통계 시뮬레이션 마지막 수정: 2026-08-19 04:44:53

1. 개요[편집]

제약 마르코프 결정 과정 Constrained Markov Decision Process (CMDP)
정식화	보상 최대화 + 비용 기대값 제약
표준 참고문헌	Altman (1999)
구성	MDP 다섯 쌍 + 비용 C₁…C_m 과 한계 d₁…d_m
유한 상태 해법	점유측도 위의 선형계획법
최적 정책	일반적으로 확률적, 초기 분포에 의존
심층 RL 해법	라그랑주 PPO/TRPO, CPO

제약 마르코프 결정 과정(Constrained MDP, CMDP)은 **누적 보상을 최대화하되 하나 이상의 누적 비용이 정해진 한계를 넘지 않아야 한다는 제약을 명시적으로 건 마르코프 결정 과정**이다. 목적함수 하나에 모든 요구를 우겨넣는 대신, 목적과 제약을 분리해 적는다.

\max_{\pi}\ J_R(\pi) = \mathbb{E}_\pi\!\left[\sum_t \gamma^t R(s_t,a_t)\right] \quad \text{s.t.} \quad J_{C_i}(\pi) = \mathbb{E}_\pi\!\left[\sum_t \gamma^t C_i(s_t,a_t)\right] \le d_i,\ \ i=1,\dots,m

동기는 실무적이다. “빨리 가되 넘어지지 마라”, “전력을 아끼되 온도 한계를 넘지 마라” 같은 요구를 보상 하나로 표현하려면 $R - \lambda C$ 처럼 벌점 계수를 손으로 정해야 하는데, 그 $\lambda$ 가 얼마여야 제약을 만족하는지는 아무도 모른다. 계수를 튜닝하는 노동은 벌점법의 고전적 병폐 그대로이고, 게다가 환경이 바뀌면 처음부터 다시 해야 한다. CMDP는 그 $\lambda$ 를 사람이 정하는 하이퍼파라미터에서 알고리즘이 푸는 쌍대변수로 승격시킨다. 사람은 물리적 의미가 있는 한계값 $d$ 만 적으면 된다.

MDP의 기초(상태·전이·할인율·가치함수·벨만 방정식)는 마르코프 결정 과정 문서에 있으니 여기서는 반복하지 않는다. 제약이 붙는 순간 무엇이 부서지는가부터 시작한다.

2. 제약이 부수는 것들[편집]

무제약 MDP의 편안한 성질 세 가지가 한꺼번에 사라진다.

최적 정책이 결정론적이지 않다. 무제약 MDP에서는 결정론적 정상 정책만 봐도 충분했다. CMDP에서는 아니다. “위험 행동을 10%의 확률로만 하라”가 최적인 상황이 실제로 생긴다 — 결정론적 정책들의 성능은 이산적인 점들이고, 제약 한계 $d$ 가 그 점들 사이에 떨어지면 두 정책을 섞어야만 제약을 등호로 만족하며 보상을 최대화할 수 있기 때문이다. 다만 무한히 어지러운 확률화가 필요한 것은 아니다. 제약이 $m$ 개면 많아야 $m$ 개의 상태에서만 확률화하는 정상 정책으로 최적을 달성할 수 있다.¹
초기 상태 분포에 의존한다. 무제약 MDP의 $\pi^*$ 는 모든 상태에서 동시에 최적이었다. CMDP의 제약은 궤적 전체에 걸친 하나의 부등식이므로 어디서 출발하느냐가 예산 배분을 바꾼다. 초기 분포 $\mu$ 를 바꾸면 최적 정책도 바뀐다.
벨만 최적 방정식이 없다. 최적성이 상태별로 분해되지 않으니 동적 계획법의 축약 사상 논리를 그대로 쓸 수 없다. 동적 계획법의 가치 반복을 CMDP에 그냥 돌리면 제약을 아무도 지키지 않는다. 남은 예산을 상태에 포함시켜 확장 MDP로 만드는 우회로가 있지만 상태 공간이 커진다.

이 세 가지 때문에 CMDP는 “MDP + 조건 하나”가 아니라 다른 종류의 문제로 취급해야 한다.

3. 점유측도와 선형계획[편집]

그럼에도 유한 상태·유한 행동 CMDP는 놀랍도록 깔끔하게 풀린다. 열쇠는 점유측도(occupancy measure)다. 정책 $\pi$ 와 초기 분포 $\mu$ 에 대해

\rho_\pi(s,a) = (1-\gamma)\sum_{t=0}^{\infty} \gamma^t \Pr\bigl(s_t = s,\ a_t = a \mid \pi, \mu\bigr)

로 정의한다. “이 정책이 상태-행동 쌍 $(s,a)$ 에 할인 가중으로 얼마나 머무는가”를 재는 확률측도다. 결정적인 사실은 모든 성능 지표가 $\rho$ 의 선형 함수라는 것이다.

J_R(\pi) = \frac{1}{1-\gamma}\sum_{s,a}\rho_\pi(s,a)\,R(s,a), \qquad J_{C_i}(\pi) = \frac{1}{1-\gamma}\sum_{s,a}\rho_\pi(s,a)\,C_i(s,a)

그리고 실현 가능한 $\rho$ 들의 집합은 볼록 다면체다. 흐름 보존식과 비음수 조건만 만족하면 된다.

\sum_a \rho(s',a) = (1-\gamma)\,\mu(s') + \gamma \sum_{s,a} P(s' \mid s,a)\,\rho(s,a), \qquad \rho \ge 0

즉 CMDP는 $\rho$ 를 변수로 하는 선형계획법 문제로 정확히 바뀐다. 목적도 선형, 제약도 선형, 실현가능영역도 다면체. 심플렉스법이든 내점법이든 꽂으면 다항시간에 풀린다. 정책은 마지막에 정규화로 복원한다.

\pi(a \mid s) = \frac{\rho(s,a)}{\sum_{a'}\rho(s,a')}

이 복원식이 왜 확률적 정책을 자연스럽게 뱉는지도 보인다 — 한 상태의 $\rho(s,\cdot)$ 가 여러 행동에 나뉘어 있으면 그게 곧 확률화다. 그리고 LP의 기저해 성질(활성 제약 수만큼만 자유도가 생김)에서 “제약 $m$ 개면 확률화하는 상태도 많아야 $m$ 개”라는 앞의 결과가 떨어진다. 정책 공간에서 보면 비볼록해 보이던 문제가 점유측도 좌표계에서는 완전히 볼록하다는 것 — 이것이 CMDP 이론 전체의 뼈대다.²

4. 라그랑주 완화와 쌍대 상승[편집]

문제가 볼록이라는 사실은 곧 강쌍대성을 준다(내부점이 존재하는 슬레이터 조건 아래). 그래서 대규모·연속 문제에서는 LP를 직접 푸는 대신 라그랑주 승수법으로 간다. 승수 $\lambda_i \ge 0$ 를 도입해

\mathcal{L}(\pi, \lambda) = J_R(\pi) - \sum_i \lambda_i\bigl(J_{C_i}(\pi) - d_i\bigr)

를 두면 원문제는 안장점 문제 $\max_\pi \min_{\lambda \ge 0} \mathcal{L}$ 가 되고, 쌍대성에 의해 $\min_{\lambda \ge 0}\max_\pi \mathcal{L}$ 와 값이 같다. 실전 알고리즘은 두 갱신을 번갈아 돌린다.

$\lambda$ 를 고정하고 보상 $R - \sum_i \lambda_i C_i$ 를 갖는 평범한 MDP를 몇 스텝 푼다. 여기가 PPO든 SAC든 아무 강화 학습 알고리즘이나 꽂히는 자리다.
정책을 고정하고 $\lambda_i \leftarrow \bigl[\lambda_i + \eta\,(J_{C_i} - d_i)\bigr]_+$ 로 쌍대 상승법 한 스텝.

두 번째 줄을 제어공학 눈으로 읽으면 적분 제어기다. 제약 위반량 $J_C - d$ 를 누적해 벌점을 키우고, 여유가 생기면 줄인다. 그리고 적분 제어기가 원래 그렇듯 — 진동한다.

4.1. 진동은 버그가 아니라 구조다[편집]

전형적인 학습 곡선은 이렇다. 초기 $\lambda = 0$ 이므로 정책은 제약을 무시하고 보상만 올린다. 비용이 $d$ 를 크게 넘으면 $\lambda$ 가 자라기 시작하는데, $\lambda$ 는 적분값이라 위반이 사라진 뒤에도 한동안 높게 남는다. 과도하게 보수적인 정책이 나오고, 비용이 $d$ 아래로 깊이 내려가면 $\lambda$ 가 다시 줄어들고, 정책은 또 위반 쪽으로 넘어간다. 비용 곡선이 $d$ 를 중심으로 감쇠가 거의 없는 진동을 그리는 것이 이 방법의 지문이다.

이론이 보장하는 것은 평균 반복해의 수렴이지 매 시점의 제약 만족이 아니다. 이 구분이 안전 응용에서 치명적이다 — “평균적으로는 제약을 지켰다”는 실제 로봇이 훈련 중 100번 넘어졌다는 사실을 지워 주지 않는다.

완화책은 대부분 제어기 설계 문제로 번역된다.

PID 승수. $\lambda$ 갱신에 비례항과 미분항을 얹는다. 적분항 하나만 쓰던 것을 완전한 PID로 만들면 오버슈트와 진동이 눈에 띄게 줄어든다.
승수 상한과 학습률 스케줄. $\lambda$ 를 클리핑하고 $\eta$ 를 감쇠시켜 진동 진폭을 강제로 좁힌다. 값싸지만 수렴점을 옮길 수 있다.
비용 가치함수의 품질. $J_C$ 추정이 편향돼 있으면 $\lambda$ 는 잘못된 오차를 적분한다. 비용 크리틱을 보상 크리틱과 같은 정성으로 학습시켜야 한다는 뻔한 이야기지만 자주 생략된다.

5. 심층 RL 쪽의 두 갈래[편집]

연속 상태·신경망 정책으로 오면 접근이 둘로 갈린다.

계열	제약을 다루는 방식	성격
라그랑주형 (PPO-Lagrangian 등)	승수를 학습하며 벌점 보상으로 환원	구현 단순, 학습 중 위반 허용
신뢰영역형 (CPO)	갱신마다 제약 대리식을 함께 선형화해 풀이	반복마다 근사적 제약 만족

CPO(Constrained Policy Optimization, Achiam 외 2017)는 신뢰 영역 정책 최적화의 논리를 제약으로 확장한다. TRPO의 성능 차이 보조정리를 비용 쪽에도 적용해 새 정책의 비용 상한을 얻고, KL 신뢰영역 안에서 목적을 선형화하고 비용 제약도 선형화한 부분문제를 푼다. 결과적으로 매 갱신마다 제약을 (근사적으로) 만족한다는 보장을 얻는다. 대가는 만만치 않다 — 신뢰영역과 제약이 동시에 만족 불가능해지는 경우가 실제로 발생하고, 그때는 비용만 줄이는 복구 스텝으로 빠져나와야 한다. 켤레기울기와 피셔-벡터 곱을 쓰는 TRPO의 구현 부담도 그대로 물려받는다.

역설적이게도 벤치마크에서는 라그랑주형이 CPO를 자주 이긴다. 안전 벤치마크 연구들이 반복해서 보고한 결과이며, 이유도 TRPO 대 PPO와 같다 — 이론적 보장이 요구하는 근사(선형화, 상한의 느슨함)가 실전에서 성능을 깎고, 구현이 단순한 쪽이 같은 예산에서 더 많은 갱신을 돈다. 보장이 있는 쪽이 아니라 벤치마크가 높은 쪽이 이긴다는 이 판의 결말이 여기서도 반복된다.³

6. 기대값 제약이라는 함정[편집]

CMDP를 안전 요구사항의 정식화로 쓸 때 반드시 짚어야 할 것이 있다. $J_C \le d$ 는 기대값에 대한 부등식이다.

비용의 기대값이 한계 이하여도 개별 에피소드는 얼마든지 크게 위반할 수 있다. 분산에 대한 제약이 아니다.
학습이 끝난 정책에 대한 진술이지 학습 과정에 대한 진술이 아니다. 탐험 중 위반은 정식화 밖에 있다. 실제 하드웨어에서 훈련한다면 이것만으로는 부족하다.
확률 1로 금지하고 싶은 사건이 있다면 기대값 제약은 잘못된 도구다. 그런 요구는 차폐(shielding) 계층, 제어 장벽 함수, 또는 모델 예측 제어의 명시적 상태 제약처럼 실행 시점에 강제되는 장치가 맡아야 한다.

꼬리 위험을 정식화 안으로 끌어오고 싶으면 비용 지표 자체를 바꾼다. 위반 확률에 대한 기회 제약(chance constraint)이나 조건부 위험가치 같은 위험 척도를 $J_C$ 자리에 놓는 변형이 이 방향이고, CVaR은 볼록성이 유지되어 위의 쌍대 구조를 상당 부분 재사용할 수 있다.

7. 시뮬레이션 판에서의 위치[편집]

CMDP가 이 바닥에서 편한 이유는 정식화의 어휘가 이미 우리 것이기 때문이다. 제한 응력, 최대 온도, 허용 진동 수준, 전력 예산 — 설계 최적화에서 늘 쓰던 제약을 그대로 $C_i$ 와 $d_i$ 로 옮기면 된다. 목적함수에 가중치를 얹어 스칼라화하던 관행보다, 제약을 제약으로 두는 쪽이 최적설계 관행과 훨씬 자연스럽게 맞는다.

실무 조언 몇 가지를 정리하면.

비용 척도의 단위를 물리량으로 잡아라. “위반 횟수”보다 “초과 응력의 시간 적분”처럼 연속적인 양이 쌍대변수의 진동을 줄인다. 이진 지표는 기울기가 거의 없는 계단이라 $\lambda$ 가 요동친다.
$d$ 를 실제 허용치보다 여유 있게 잡아라. 기대값 제약이라는 점, 학습 곡선이 진동한다는 점 둘 다 안전 여유를 요구한다. 안전율은 여기서도 유효한 개념이다.
제약이 활성인지 확인하라. 수렴 후 $\lambda_i \approx 0$ 이면 그 제약은 애초에 걸리지 않았다는 뜻이다. 쌍대변수는 무료로 딸려 오는 민감도 정보이기도 하다 — $\lambda_i$ 는 한계 $d_i$ 를 한 단위 풀었을 때 얻을 보상의 증가율이다. 여러 제약 중 어느 쪽을 완화하도록 설계를 바꿔야 하는지가 여기서 읽힌다.
훈련은 시뮬레이터에서, 배치는 차폐와 함께. CMDP는 정책의 평균적 성질을 다듬는 도구이지 실시간 안전장치가 아니다. 안전 강화학습 전체 그림에서 CMDP는 “최적성 기준을 바꾸는” 축을 담당하고, 실행 시점 개입은 별도의 축이다.

8. 관련 문서[편집]

Altman, E. (1999). Constrained Markov Decision Processes. Chapman & Hall. 이 책이 사실상 CMDP의 표준 참고문헌이고, 확률화가 필요한 상태 수가 제약 개수로 묶인다는 결과도 여기 있다. 직관적으로는 “제약을 등호로 맞추기 위한 자유도가 딱 그만큼 필요하다”로 읽으면 된다. 제약 하나에 다이얼 하나. ↩
좌표계를 바꾸면 비볼록이 볼록이 되는 이 트릭은 강화학습 바깥에서도 흔하다. 확률 분포를 변수로 잡으면 선형이 되는 구조는 게임 이론의 혼합전략 LP나 최대 엔트로피 강화 학습의 볼록 쌍대에서도 같은 얼굴로 나타난다. 정책은 다루기 어렵고 측도는 다루기 쉽다. ↩
그렇다고 CPO 계열이 무의미하다는 뜻은 아니다. “학습 중 위반 횟수”를 지표에 넣고 재면 그림이 달라진다. 최종 성능만 보는 벤치마크는 훈련 중 로봇이 몇 번 부서졌는지를 채점하지 않는데, 실물을 만지는 사람에게는 그쪽이 청구서로 돌아온다. 지표를 무엇으로 잡느냐가 알고리즘 순위를 정한다는 흔한 이야기. ↩