기술적 요약: 적대적 손실을 가진 선형 CMDP 를 위한 원-쌍대 정책 최적화

문제 설정

본 논문은 안전 제약 조건이 적대적 교란에도 불구하고 충족되어야 하는 환경에서의 안전 강화 학습 (Safe Reinforcement Learning, RL) 과 관련된 과제를 다룹니다. 구체적으로, 저자들은 유한 시간 범위 적대적 선형 제약 마르코프 결정 과정 (Finite-Horizon Adversarial Linear Constrained Markov Decision Processes, CMDPs) 을 고려합니다.

이 설정은 $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$라는 튜플로 정의되며, 여기서:

• 적대적 손실 (Adversarial Losses): 손실 함수 $f^k = \{f^k_h\}$는 각 에피소드 $k$의 시작 시 적대자에 의해 임의로 선택됩니다 (전체 정보 피드백). 이러한 손실은 고정된 분포에서 추출되지 않습니다.
• 확률적 비용 (Stochastic Costs): 비용 함수 $g^k = \{g^k_h\}$는 고정된 분포 $G$에서 i.i.d.로 샘플링됩니다 (밴디트 피드백). 이는 안전 제약 조건을 나타냅니다.
• 선형 구조 (Linear Structure): 전이 커널, 손실 함수, 비용 함수는 알려진 특징 매핑 $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$에 대해 선형 구조를 가집니다.
• 목표 (Objective): 에이전트는 누적 기대 손실을 최소화하면서 기대 누적 비용이 예산 $b$를 초과하지 않도록 정책을 찾습니다.

성능은 후회 (Regret) (최적 정책 대비 누적 손실 차이) 와 제약 위반 (Constraint Violation) (예산 초과 누적 비용) 으로 측정됩니다. 목표는 두 지표 모두에 대해 부분 선형 (sublinear) 경계를 달성하는 것입니다.

방법론

저자들은 선형 함수 근사 설정에서 적대적 손실과 확률적 제약 간의 상호작용을 처리하도록 설계된 원 - 쌍대 정책 최적화 (Primal-Dual Policy Optimization) 알고리즘 (알고리즘 1) 을 제안합니다. 이 알고리즘은 네 가지 주요 구성 요소를 통합합니다:

1. 에포크 초기화 및 특징 수축:
   알고리즘은 에포크 단위로 작동합니다. 에포크는 설계 행렬 $\Lambda^k_h$의 행렬식이 배수 인자로 증가할 때 시작됩니다. 초기화 시 정책은 균일 정책으로 재설정되고, 쌍대 변수는 0 으로 재설정됩니다. 중요한 점은 알고리즘이 특징 수축 (feature contraction) 을 사용하여 원래 특징 $\phi$를 시그모이드 함수로 축소함으로써 Q 함수 추정이 통제 불가능하게 팽창하는 것을 방지한다는 것입니다. 이 기법은 Cassel & Rosenberg(2024) 에서 차용된 것으로, 덮개 수 (covering number) 논증을 위해 정책 표현을 단순화합니다.

2. 정책 실행 및 추정:
   각 에피소드에서 에이전트는 현재 정책에 기반하여 행동을 실행하고, 적대적 손실과 확률적 비용을 관찰한 후 설계 행렬을 업데이트합니다. 그런 다음 손실 및 비용 함수의 매개변수를 추정하고, 축소된 특징과 낙관적 보너스를 사용하여 Q 함수 추정치 ($\hat{Q}$) 와 가치 함수 추정치 ($\hat{V}$) 를 계산합니다.

3. 주기적 정책 혼합:
   핵심 혁신은 주기적 정책 혼합 (periodic policy mixing) 입니다. 매 에피소드마다 정책을 혼합 (균일 정책 방향으로 교란) 하는 대신, 알고리즘은 $K^B$ 에피소드당 한 번 (여기서 $B=3/4$) 만 혼합을 적용합니다.

   • 동기: 빈번한 혼합은 쌍대 변수를 경계하기 위해 (드리프트 분석을 통해) 필요하지만 정책 클래스의 복잡성 (덮개 수) 을 증가시킵니다. 주기적 혼합은 이러한 상충되는 요구 사항을 균형 있게 조정합니다.
   • 메커니즘: $K^{3/4}$ 에피소드마다 현재 정책 $\hat{\pi}^k$는 볼록 결합을 통해 균일 정책 $\pi_{unif}$와 혼합됩니다: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. 정규화된 쌍대 업데이트:
   비용 제약과 관련된 쌍대 변수 $Y^k$는 정규화된 경사 상승 (regularized gradient ascent) 단계로 업데이트됩니다:
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   정규화 항 ($-4\alpha\eta H^3 Y^k$ 및 상수) 은 쌍대 변수를 0 으로 끌어당기도록 설계되어, 적대적 설정에서 실패하는 강한 쌍대성 가정에 의존하지 않고도 $Y^k$를 경계할 수 있게 하는 리야푸노프 드리프트 분석 (Lyapunov drift analysis) 을 가능하게 합니다.

5. 가중 LogSumExp 소프트맥스 정책:
   결과적으로 생성된 정책 클래스는 가중 LogSumExp 소프트맥스입니다. 주기적 혼합으로 인해 정책은 Q 함수 합의 단순 지수 형태가 아니라, Q 함수 추정치의 부분 합의 지수의 가중 합 형태가 됩니다. 이 구조는 정책이 적대적으로 선택된 손실에 적응하면서도 다루기 쉬운 덮개 수를 유지할 수 있게 합니다.

주요 기여

1. 적대적 선형 CMDP 에 대한 첫 번째 부분 선형 경계:
   본 논문은 적대적 손실과 확률적 비용을 가진 선형 CMDP 설정에서 부분 선형 후회 및 제약 위반 경계를 달성하는 첫 번째 알고리즘을 제시합니다. 경계는 $\tilde{O}(K^{3/4})$이며, 여기서 $K$는 에피소드 수입니다.

2. 새로운 덮개 수 논증:
   저자들은 가중 LogSumExp 소프트맥스 정책에 대한 새로운 덮개 수 논증을 확립합니다. 균일한 가중치를 갖는 표준 소프트맥스 정책과 달리, 혼합 과정은 다양한 가중치 매개변수 $\zeta_i$를 도입합니다. 저자들은 이 클래스의 덮개 수의 로그가 $\tilde{O}(n^2 d^2)$로 증가함을 증명합니다. 여기서 $n$은 혼합 단계 수이고 $d$는 특징 차원입니다. 이 결과는 가중치 매개변수가 혼합 매개변수와 Q 함수 추정치 모두에 의존하기 때문에 비자명합니다.

3. 제어를 위한 알고리즘 구성 요소:
   본 논문은 덮개 수와 쌍대 변수를 공동으로 제어하기 위해 두 가지 새로운 구성 요소를 도입합니다:

   • 주기적 정책 혼합: 혼합 빈도를 조절하여 $O(K)$ 혼합 단계가 발생할 경우 발생할 수 있는 덮개 수의 과도한 증가를 방지하면서도 쌍대 변수를 경계하기에 충분히 빈번하게 혼합이 일어나도록 합니다.
   • 정규화된 쌍대 업데이트: 드리프트 기반 분석을 용이하게 하기 위해 정규화 항을 포함하는 새로운 업데이트 규칙으로, 강한 쌍대성이 부재한 상황에서도 쌍대 변수를 경계할 수 있게 합니다.

결과

이론적 보장:
Slater 조건 (가정 1) 하에서 $H^2 \leq K$라고 가정할 때, 확률 $1-\delta$ 이상으로 알고리즘은 다음을 달성합니다:

• 후회: $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• 제약 위반: $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

두 지표 모두 $K$에 대해 부분 선형 (구체적으로 $K^{3/4}$) 으로 스케일링되므로, 에피소드 수가 증가함에 따라 평균 후회와 평균 제약 위반이 0 으로 수렴함을 의미합니다.

수치 실험:
적대적 손실이 있는 수정된 작업 스케줄링 CMDP 에서 알고리즘을 평가했습니다. 100,000 에피소드 동안:

• 후회: 부분 선형적으로 증가하여 이론적 경계를 확인했습니다.
• 제약 위반: 초기에는 급격히 증가했으나 약 45,000 에피소드 이후 0 으로 수렴하여, 장기적으로 안전 제약 조건을 충족하는 알고리즘의 능력을 검증했습니다.

중요성과 주장

본 논문은 적대적 설정에서 선형 함수 근사를 사용하는 안전 RL 에 대한 첫 번째 증명 가능한 효율적 알고리즘이라고 주장합니다. 그 중요성은 다음 두 가지 사이의 간극을 메우는 데 있습니다:

1. 표 (Tabular) 적대적 CMDP: 이전 연구들 (예: Qiu et al., 2020) 은 적대적 설정을 처리했지만 작은 유한 상태 공간으로 제한되었습니다.
2. 선형 확률적 CMDP: 이전 연구들 (예: Ghosh et al., 2022) 은 큰 상태 공간을 처리했지만 정적 (확률적) 환경을 가정했습니다.

가중 LogSumExp 소프트맥스 정책과 주기적 혼합 전략을 도입함으로써, 저자들은 선형 근사를 통해 큰 상태 공간을 처리함과 동시에 적대적 손실을 다룰 수 있음을 보여줍니다. 논문은 $\tilde{O}(K^{3/4})$가 달성되었지만, 혼합 단계와 덮개 수 간의 트레이드오프와 관련하여 이 특정 설정에 대한 최적의 $\tilde{O}(\sqrt{K})$ 경계는 여전히 열린 질문이라고 겸손하게 언급합니다. 또한 이 작업은 적대적 선형 CMDP 에서 점유율 측정 기반 쌍대 업데이트를 정책 기반 방법으로 확장하는 것의 어려움을 강조하여, 제안된 원 - 쌍대 정책 최적화 접근 방식을 정당화합니다.