🤖 machine learning

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

본 논문은 표형, 로그-선형 및 복잡한 비선형 정책 설정에 걸친 제약 조건이 있는 마르코프 결정 과정에 대해 검증 가능한 전역 마지막 반복 수렴을 달성하는 부정확한 증강 라그랑주 방법을 기반으로 한 일반적 프레임워크를 제안하여 기존 혼합 정책 접근법의 실용적 한계를 해결합니다.

원저자: Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani

게시일 2026-05-13

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

로봇이 비디오 게임을 플레이하도록 훈련한다고 상상해 보세요. 목표는 간단합니다: 가능한 최고 점수를 얻는 것입니다. 하지만 함정이 하나 있습니다. 로봇은 게임이 끝날 때까지 배터리가 방전되어서는 안 된다는 엄격한 규칙을 따릅니다.

이것이 이 논문이 다루는 핵심 문제이며, 기술계에서는 **제약 마르코프 결정 과정 (Constrained Markov Decision Process, CMDP)**으로 알려져 있습니다. 로봇 (즉, '에이전트') 은 배터리 수명이라는 예산을 초과하지 않으면서 보상 (점수) 을 극대화해야 합니다.

기존 방법의 문제점: "섞고 맞추기"의 혼란

이 문제를 해결하기 위한 대부분의 기존 AI 방법은 완벽한 수프를 만들려는 셰프처럼 작동합니다. 그들은 여러 가지 다른 레시피 (정책) 를 하나씩 시도해 봅니다. 그리고 끝날 때쯤, 찾은 단일 최상의 레시피를 제공하기 대신 다음과 같이 말합니다: "우리가 시도해 본 모든 레시피를 조금씩 무작위로 섞어 만든 수프 한 그릇을 여기 있습니다."

이 "섞인 수프"는 이론상 (수학적으로는 규칙을 만족하므로) 잘 작동하지만, 현실 세계에서는 악몽과 같습니다:

메모리 과부하: 이 혼합물을 만들기 위해 시도해 본 모든 단일 레시피를 기억해야 합니다.
예측 불가능성: 만약 실제로 그 혼합물에서 한 숟가락을 떠서 제공한다면, 그것은 끔찍할 수 있습니다. 평균적인 그릇은 괜찮을지라도, 무작위로 떠낸 한 숟가락은 순수한 소금일 수 있습니다 (배터리 규칙 위반).
진동: 로봇의 행동은 종종 "너무 빠름"과 "너무 느림" 사이를 격렬하게 오가며 결코 안정화되지 않습니다.

이 논문은 실제 생활 (자율주행차나 의료 기기 등) 에서는 "무작위 혼합"에 의존할 수 없다고 주장합니다. 우리는 안전하고 즉시 효과적인 단일 최종 로봇이 필요합니다. 이를 **"최종 반복 수렴 (Last-Iterate Convergence)"**이라고 합니다.

해결책: "증강 라그랑주 (Strict Coach)"

저자들은 로봇을 훈련시키기 위해 수학의 고전적인 기법인 증강 라그랑주 (Augmented Lagrangian, AL) 방법을 사용하는 새로운 방식을 제안합니다.

AL 방법을 엄격한 코치로 생각하세요. 이 코치는 단순히 "더 빠르게 가라!" (보상 극대화) 고 외치는 것뿐만 아니라, 로봇이 규칙을 위반할 경우 로봇의 등에 무거운 벌점 무게를 지웁니다.

코치의 작동 방식은 다음과 같습니다:

벌점 무게: 로봇이 배터리가 방전될 위험에 처하면, 코치는 목표에 무거운 2 차 벌점 (무거운 배낭과 같은) 을 추가합니다. 규칙 위반이 심할수록 배낭은 더 무거워져 앞으로 나아가는 것이 어려워집니다.
조정: 코치는 그 무게를 그대로 두지 않습니다. 로봇의 수행도에 따라 배낭의 무게를 끊임없이 조정합니다.
- 로봇이 안전하면 코치는 짐을 약간 가볍게 합니다.
- 로봇이 위험하면 코치는 즉시 짐을 더 무겁게 합니다.
결과: 로봇이 "너무 빠름"과 "너무 느림" 사이를 격렬하게 오가는 대신, AL 방법은 로봇을 높은 점수를 얻으면서도 안전을 유지하는 단일하고 안정적인 경로로 부드럽게 안내합니다.

"마법" 성분: 투사형 Q-상승 (Projected Q-Ascent, PQA)

이 논문의 가장 큰 돌파구는 로봇이 걷거나 비행하는 것과 같은 복잡한 기술을 학습할 때에도 이 "엄격한 코치"가 효율적으로 작동하도록 하는 방법을 찾은 것입니다.

그들은 **투사형 Q-상승 (Projected Q-Ascent, PQA)**이라는 특정 훈련 기법을 사용합니다.

비유: 로봇이 최고봉 (최고 점수) 을 찾기 위해 언덕을 오르고 있다고 상상해 보세요. 하지만 그 언덕에는 "출입 금지 구역" (안전 제약) 이 있습니다.
구식 방식: 로봇이 오르다 출입 금지 구역에 있음을 깨닫고는 앞뒤로 점프하며 결코 정착하지 못합니다.
PQA 방식: 로봇이 언덕을 한 걸음 오릅니다. 그 발걸음이 출입 금지 구역으로 이어진다면, PQA 는 자석 벽처럼 작용합니다. 로봇을 안전 구역의 가장자리로 부드럽지만 단호하게 밀어내되, 가능한 최상의 방향으로 계속 이동하게 합니다. 로봇의 움직임을 안전한 경로로 "투사"하는 것입니다.

그들이 증명한 것

저자들은 단순히 멋진 로봇을 만든 것이 아니라, 이 접근 방식이 수학적으로 작동함을 증명했습니다:

수렴: 로봇은 결국 흔들림을 멈추고 단일 최종 정책으로 정착합니다.
안전성: 그 최종 정책은 평균적으로가 아니라 높은 확률로 안전 규칙 (배터리 제한) 을 준수합니다.
효율성: 그들은 이 방법이 간단한 그리드 (표 형식) 와 비디오 게임의 연속 제어와 같은 복잡하고 현실적인 작업에서도 로봇의 수천 가지 이전 버전을 저장할 필요 없이 작동함을 보였습니다.

현실 세계의 결과

이 팀은 로봇이 벽에 부딪히지 않고 미로를 탐색하는 것과 같은 표준 안전 벤치마크에서 그들의 방법 (PPQA-ALM 또는 SPMA-ALM 이라고 명명됨) 을 테스트했습니다.

비교: 그들은 PPO-Lag 및 CPO 와 같은 다른 인기 있는 방법들과 비교했습니다.
결과: 그들의 방법은 높은 점수를 얻는 데 있어 다른 방법들과同等이었지만, 훨씬 더 안정적이었습니다. 진동하지 않았습니다. 다른 방법들이 정착하는 데 어려움을 겪거나 작동하기 위해 복잡한 "혼합" 트릭이 필요했던 반면, 그들의 방법은 안전 제약을 존중하는 단일하고 신뢰할 수 있는 해결책을 찾았습니다.

요약

간단히 말해, 이 논문은 안전 규칙이 있는 AI 에이전트를 훈련시키는 더 똑똑한 방식을 소개합니다. 많은 실패한 시도들의 혼란스러운 "평균"에 의존하는 대신, 벌점 배낭을 지닌 엄격한 코치와 자석 벽을 사용하여 AI 를 단일하고 완벽하며 안전한 최종 행동으로 안내합니다. 이는 안전이 타협할 수 없는 현실 세계의 응용 분야에 이 기술을 준비시킵니다.

기술 요약: 제약 조건이 있는 MDP 에 대한 마지막 반복 수렴을 위한 증강 라그랑주 방법

문제 정의

본 논문은 무한 시간, 할인된 제약 조건이 있는 마르코프 결정 과정 (CMDP) 에 대한 정책 최적화 문제를 다룹니다. 이 설정에서 에이전트는 누적 보상 $V^\pi_r(\rho)$ 를 최대화해야 하는 동시에, $m$ 개의 제약 조건에 대해 누적 제약 보상 $V^\pi_{c_i}(\rho)$ 가 지정된 임계값 $b_i$ 를 만족하도록 해야 합니다. 최적 정책이 결정론적인 표준 MDP 와 달리, CMDP 의 최적 정책은 일반적으로 확률적입니다.

기존의 원형 - 쌍대 (Primal-Dual, PD) 방법의 한계로 인해 중요한 실용적 도전 과제가 발생합니다. PD 방법에 대한 이론적 보장이 존재하지만, 이러한 보장은 일반적으로 훈련 중 생성된 모든 중간 정책의 균일 평균인 **혼합 정책 (mixture policy)**에만 적용됩니다. 모든 중간 정책을 저장해야 하므로 이러한 혼합 정책을 배포하는 것은 계산 및 메모리 측면에서 매우 비용이 많이 듭니다. 또한, 안전이 중요한 응용 분야에서는 혼합에 의존하는 것이 위험합니다. 혼합이 기대값으로는 제약을 만족하더라도, 혼합에서 무작위로 샘플링된 정책은 제약을 크게 위반할 수 있기 때문입니다. 따라서 실무자들은 종종 **마지막 반복 정책 (last-iterate policy, 최종 생성된 정책)**을 배포하지만, 표준 PD 방법은 이 특정 정책에 대한 이론적 보장이 부족하여 진동하는 행동을 보이고 실현 가능한 해에 수렴하지 못하는 경우가 많습니다.

최근 마지막 반복 수렴을 증명하려는 시도들은 대부분 표 (tabular) 설정에 국한되거나, 구현이 어렵거나 대규모 문제에는 비실용적인 알고리즘 변형 (예: 강력한 정규화) 에 의존해 왔습니다.

방법론

저자들은 CMDP 에 대해 증명 가능한 마지막 반복 수렴을 달성하기 위해 제약 최적화의 고전적 접근법인 증강 라그랑주 (Augmented Lagrangian, AL) 방법을 기반으로 한 일반적인 프레임워크를 제안합니다.

1. 증강 라그랑주 프레임워크

PD 방법에서 사용되는 표준 라그랑주 대신, 이 프레임워크는 증강 라그랑주 함수 $L_\beta(\pi, \lambda)$ 를 최적화합니다:
$L_\beta(\pi, \lambda) := V^\pi_r(\rho) + \frac{\beta}{2} \sum_{i=1}^m \left( -\min\left\{ V^\pi_{c_i}(\rho) - b_i - \frac{\lambda_i}{\beta}, 0 \right\}^2 + \frac{\lambda_i^2}{\beta^2} \right)$
여기서 $\beta > 0$ 는 페널티 매개변수이고 $\lambda$ 는 라그랑주 승수입니다. 2 차 페널티 항은 제약 위반을 억제합니다. 알고리즘은 이 함수를 대략적으로 최대화하도록 정책 (원형 변수) 을 반복적으로 업데이트하고, 제약 위반에 기반하여 쌍대 변수 (라그랑주 승수) 를 업데이트합니다.

2. AL 부분 문제 해결

핵심적인 어려움은 $L_\beta(\pi, \lambda)$ 가 정책 $\pi$ 에 대해 **비오목 (non-concave)**이어서 부분 문제를 해결하기 어렵다는 점입니다. 저자들은 이 문제를 두 가지 설정으로 분해하여 해결합니다:

표 (Tabular) 설정: 저자들은 **프로젝티드 Q-어센트 (Projected Q-Ascent, PQA)**를 사용하여 AL 부분 문제를 해결하는 것을 제안합니다. 그들은 현재 정책의 제약 만족도에 의존하는 비정상적 의사 보상 (non-stationary pseudo-reward) $\Gamma(\pi)$ 를 포함하는 AL 부분 문제에 대한 정책 기울기를 유도합니다. PQA 를 사용하여 부분 문제에 대한 전역 마지막 반복 수렴 보장을 확립합니다.
함수 근사 (로그 - 선형 정책): 큰 상태 - 행동 공간을 처리하기 위해 프레임워크를 매개변수화된 정책 (특히 로그 - 선형 정책) 으로 확장합니다. 저자들은 원래 보상과 제약 구성 요소로 선형적으로 분해되는 AL 정책 기울기를 유도하여 PPO 나 SPMA 와 같은 표준 추정 도구를 사용할 수 있도록 합니다. 그들은 프로젝티드 PQA (PPQA) 업데이트를 도입하는데, 이는 다음을 포함합니다:
1. 이상적인 정책 업데이트 (PQA 단계) 계산.
2. 이를 프론트 KL-발산 (forward KL-divergence) 을 사용하여 실현 가능한 정책 클래스에 투영하는 것. 이는 서브rogate 최적화 문제 (소프트 라벨을 가진 다중 클래스 로지스틱 회귀) 로 공식화됩니다.

3. 수렴 분석

저자들은 모듈식 분석을 제공합니다:

먼저 부분 문제 솔버가 특정 정확도 ( $O(1/\epsilon^2)$ 반복, 외부 루프) 를 달성한다면 부정확한 AL 방법이 CMDP 에 대한 $\epsilon$ -최적 해에 수렴함을 증명합니다.
그런 다음 특정 솔버 (PQA 및 PPQA) 를 분석하여 부분 문제에 필요한 정확도를 달성할 수 있음을 보여줍니다.
이러한 결과를 결합하여 전체 알고리즘이 표 및 로그 - 선형 설정 모두에 대해 $O(1/\epsilon^6)$ 의 기울기 평가 샘플 복잡도로 전역 마지막 반복 수렴을 달성함을 증명합니다.

주요 기여

범용 부정확한 AL 프레임워크: 본 논문은 부정확한 AL 방법을 사용하여 CMDP 를 해결하기 위한 모듈식 프레임워크를 소개합니다. AL 반복의 분석과 부분 문제 솔버 선택을 분리하여, 부분 문제가 충분한 정확도로 해결된다면 $O(1/\epsilon^2)$ 개의 외부 반복으로 $\epsilon$ -최적 정책을 찾는 데 충분함을 증명합니다.
표 설정에서의 마지막 반복 수렴: 표 설정에 대해 프로젝티드 Q-어센트 (PQA) 로 프레임워크를 구체화함으로써, 저자들은 $O(1/\epsilon^6)$ 의 복잡도로 전역 마지막 반복 수렴을 확립합니다. 이는 AL 부분 문제에서 의사 보상의 비정상성을 해결합니다.
함수 근사로의 확장: 프레임워크를 로그 - 선형 정책으로 일반화합니다. 저자들은 AL 정책 기울기를 유도하고, 동등한 $O(1/\epsilon^6)$ 수렴 보장을 달성하는 프로젝티드 변형 (PPQA) 을 제안합니다. 이전 연구와 달리 이 방법은 비표준 알고리즘 수정 (제한된 심플렉스로 투영 등) 이나 제한적인 구조적 가정 (호환 가능한 함수 근사 등) 을 요구하지 않으며 여러 제약을 지원합니다.
실증적 검증: 프레임워크는 PPO 와 최근의 정책 최적화 알고리즘인 SPMA 를 사용하여 구체화되었으며, Safety-Gymnasium 의 대규모 연속 제어 작업에서 평가되었습니다. 결과는 제안된 접근 방식이 PPO-Lag 및 CPO 와 같은 공학적으로 정교한 베이스라인과 유사한 성능을 발휘하면서도 최종 정책에 대한 이론적 보장을 제공함을 보여줍니다.

결과

이론적: 본 논문은 제안된 알고리즘이 $O(1/\epsilon^6)$ 개의 기울기 평가 후 CMDP 문제에 대한 $\epsilon$ -근사 해인 확률적 정책을 반환함을 증명합니다. 이는 표 및 로그 - 선형 정책 클래스 모두에 대해 성립합니다.
실증적 (표): 표 환경 (제약 조건이 있는 절벽 세계, 제약 조건이 있는 심해 보물) 에서 제안된 PQA-ALM 및 PPQA-ALM 방법은 최소 진동으로 최적 정책에 부드럽게 수렴하여 RPG-PD 및 ReLOAD 와 같은 다른 마지막 반복 방법보다 우수하거나 이에 필적합니다.
실증적 (연속 제어): Safety-Gymnasium 작업 (SafetyAntVelocity, SafetyHalfCheetahVelocity, SafetyHopperVelocity) 에서 SPMA-ALM 및 PPO-ALM 변형은 PPO-Lag 및 CPO 와 유사한 보상과 제약 위반을 달성합니다. 특히, AL 기반 방법은 베이스라인에 비해 덜 진동하는 행동과 더 일관된 제약 만족도 (낮은 평균 및 꼬리 위반) 를 보입니다.

중요성과 주장

본 논문은 제약 조건이 있는 강화 학습에서 이론적 보장과 실용적 배포 간의 간극을 해소한다고 주장합니다.

실용성: 표 설정에 국한되거나 비실용적인 정규화에 의존하는 이전의 마지막 반복 수렴 연구와 달리, 이 프레임워크는 표준 함수 근사를 사용하여 대규모 문제에 효율적이고 확장 가능하도록 설계되었습니다.
안전성: 혼합이 아닌 마지막 반복 정책에 대한 수렴을 보장함으로써, 배포된 정책 자체가 제약을 만족하도록 합니다. 이는 혼합에서 무작위 샘플링이 허용되지 않는 안전이 중요한 응용 분야에 매우 중요합니다.
원칙적 접근: 이 방법은 고전적인 증강 라그랑주 방법에 의존하여, 실무적인 제약 조건이 있는 RL 구현에서 흔히 발견되는 임시 휴리스틱 (예: 승수로 목적 함수 조정) 없이 명확한 이론적 기반을 제공합니다.

저자들은 표 설정에서 최소 상태 방문 확률 ( $\rho_{min}$ ) 에 대한 강한 의존성과 로그 - 선형 정책에 대한 편향 항 ( $\epsilon_{bias}$ ) 을 한계로 인정하며, 이를 향후 연구 방향으로 제시합니다. 또한 향후 방향으로는 액터 - 크리틱 또는 오프 - 정책 방법을 이론적 프레임워크에 통합하는 것을 포함한다고 언급합니다.