기술 요약: 약결합된 MDP에 대한 리아푸노프 기반 샘플 복잡도 분석

1. 문제 정의

본 논문은 생성 모델(generative model) 설정 하에서 평균 보상(average-reward)을 목적으로 하는 약결합된 마르코프 결정 과정(Weakly-Coupled MDPs, WCMDPs) 및 **레스틸리스 밴딧(Restless Bandits, RBs)**의 샘플 복잡도(sample complexity) 문제를 다룹니다.

이러한 시스템에는 $N$개의 독립적인 암(arms, 하위 시스템)이 존재하며, 각 암은 하나의 MDP로 모델링됩니다. 이들은 전역적 비용 제약(예: 활성화된 암의 총 개수에 대한 예산)을 통해 서로 결합되어 있습니다. 목표는 장기 평균 보상을 최대화하는 것입니다. 핵심 과제는 "차원의 저주"입니다. 시스템을 하나의 거대한 단일 MDP로 간주할 경우, 상태-행동 공간의 크기가 $|S|^N \times |A|^N$이 되어 $N$에 대해 지수적으로 증가합니다. 기존의 테이블형 MDP(tabular MDP)에 대한 샘플 복잡도 경계(state-action 공간의 크기에 비례함)를 그대로 적용하면 $N$에 대해 지수적인 경계가 도출되어, 대규모 시스템에서의 학습이 불가능해집니다.

본 논문은 다음과 같은 질문에 답하고자 합니다: 어떻게 하면 암의 개수 $N$에 대한 지수적 의존성을 피하면서, 평균 보상 WCMDP(또는 RB)에서 최적에 가까운 정책을 학습할 수 있는가?

2. 방법론

2.1. 참조 정책을 이용한 플러그인 접근법 (Plug-in Approach)

저자들은 플러그인 접근법을 채택합니다. 상호작용으로부터 직접 정책을 학습하는 대신 다음 과정을 거칩니다:

1. 각 암의 모든 상태-행동 쌍에 대해 $n$개의 i.i.d. 샘플을 수집하여 경험적 전이 커널(empirical transition kernel, $\hat{P}$)을 구성합니다.
2. 이 경험적 모델 상에서 계획 알고리즘(planning algorithm)을 풀어 정책을 도출합니다.
3. 효율적인 계획 알고리즘들을 **참조 정책(reference policies)**으로 사용합니다:
   • 이질적(Heterogeneous) WCMDP의 경우: 계획 단계에서 $O(1/\sqrt{N})$의 최적성 갭(optimality gap)을 달성하는 ID 정책(Zhang et al., 2025)을 사용합니다.
   • 동질적(Homogeneous) RB의 경우: 특정 구조적 조건 하에서 지수적으로 작은 최적성 갭($O(e^{-cN})$)을 달성하는 two-set 정책(Hong et al., 2024a)을 사용합니다.

2.2. 새로운 리아푸노프 기반 분석 프레임워크

본 논문의 주요 기술적 혁신은 플러그인 접근법의 샘플 복잡도를 분석하기 위한 새로운 프레임워크입니다.

• 기존의 한계: 전통적인 분석은 성능 차이를 편향 함수(bias function, 상대 가치 함수)를 통해 제한하는 시뮬레이션 레마(simulation lemma)에 의존합니다. 하지만 편향 함수는 종종 암묵적이고 복잡하며, 특히 ID나 two-set 정책과 같은 정교한 계획 알고리즘의 경우 제어하기 어렵습니다.
• 제안된 해결책: 저자들은 편향 함수를 대신하여 명시적으로 구성된 리아푸노프 함수(Lyapunov function, $V$)를 도입합니다.
  • 1단계 (리아푸노프 분석): 참조 정책이 실제 시스템에서 드리프트 경계(drift bound, 리아푸노프 함수가 기대값 측면에서 감소함)와 갭 지배 조건(gap dominance condition, 보상 갭이 리아푸노프 함수에 의해 유계됨)을 만족함을 입증합니다.
  • 2단계 (드리프트 전이): 이러한 경계들을 경험적 시스템으로 전이합니다. 구성된 리아푸노프 함수의 노름(norm)을 명시적으로 제한함으로써, 모델 불일치($P - \hat{P}$)로 인해 발생하는 오차를 제어합니다.
  • 장점: $V$가 명시적으로 구성되었기 때문에 그 노름을 다루기 쉬운 범위 내에서 제한할 수 있으며, 이를 통해 암묵적인 편향 함수를 다룰 때 발생하는 어려움을 피할 수 있습니다.

2.3. 미세한 LP 섭동 분석 (Fine-Grained LP Perturbation Analysis)

동질적 RB의 경우, 최적의 단일 암 정책을 도출하기 위해 사용되는 선형 계획법(Linear Programming, LP) 완화(relaxation)를 분석하는 것이 중요한 단계입니다.

• 저자들은 완만한 구조적 가정(에르고로디시티, 비퇴화성, 국소 안정성) 하에서, LP의 해가 전이 커널의 섭동(perturbation)에 대해 강건함(robust)을 증명합니다.
• 구체적으로, 단 하나의 "중립 상태(neutral state)"를 제외하고는, 최적해의 서포트(support, 어떤 상태에서 어떤 행동을 취하는지)가 작은 섭동 하에서도 안정적으로 유지됨을 보여줍니다.
• 이는 경험적 정책이 리아푸노프 분석이 성립하는 데 필요한 구조적 특성을 유지하도록 보장합니다.

3. 주요 결과

3.1. 이질적 WCMDP

완전 이질적 WCMDP에 대해, 본 논문은 다항 시간 복잡도를 갖는 최초의 유한 샘플 PAC (Probably Approximately Correct) 보장을 확립합니다.

• 결과: 학습된 정책 $\hat{\pi}_{ID}$는 다음과 같은 최적성 갭을 가집니다:
  $$\rho^* - \rho_{\hat{\pi}_{ID}} \leq O\left(\frac{\sqrt{S + \log(N/\eta)}}{\sqrt{n}} \cdot N\right) + O\left(\frac{1}{\sqrt{N}}\right)$$
  여기서 $n$은 암당 상태-행동 쌍당 샘플 수입니다.
• 샘플 복잡도: 갭 $\epsilon = \Omega(1/\sqrt{N})$을 달성하기 위해 필요한 총 샘플 수는 $N$에 대해 다항식 규모(구체적으로 $O(N^3)$ 총 샘플)로 스케일링됩니다(지수적이지 않습니다).

3.2. 동질적 레스틸리스 밴딧

동질적 RB의 경우, 완만한 구조적 가정(가정 2 및 3) 하에서 학습된 정책 $\hat{\pi}_{TS}$는 훨씬 더 타이트한 경계를 달성합니다.

• 결과: 최적성 갭은 다음과 같이 제한됩니다:
  $$\rho^* - \rho_{\hat{\pi}_{TS}} \leq O\left(\frac{\sqrt{S + \log(1/\eta)}}{\sqrt{n}} \cdot N\right) + O(e^{-cN})$$
• 샘플 복잡도: 참조 정책 자체의 갭이 지수적으로 작기 때문에, 학습 알고리즘은 $N$에 대해 다항식 규모인 샘플 크기 $n$을 사용하여 갭 $\epsilon = \Omega(e^{-cN})$을 달성할 수 있습니다.
• 블로킹 기법 (Blocking Scheme): 저자들은 또한 고정된 샘플 크기에 대한 "블로킹" 기법을 제안하여, 암들을 블록으로 나누어 유한 샘플 오차와 참조 정책의 최적성 갭 사이의 균형을 맞춤으로써 접근법의 유연성을 더욱 입증했습니다.

4. 의의 및 주장

본 논문은 세 가지 주요 기여를 주장합니다:

1. 지수적 장벽의 돌파: 약결합된 구조를 활용함으로써, $N$에 대해 다항식 수준의 샘플 및 계산 복잡도로 최적에 가까운 정책을 학습할 수 있음을 보여줍니다. 이는 이들을 단일 MDP로 취급할 때 발생하는 지수적 복잡도와 극명하게 대조되며, 대규모 WCMDP 및 RB 학습 문제를 공식적으로 해결합니다.
2. 새로운 분석 프레임워크: 리아푸노프 기반 분석 프레임워크는 평균 보상 시스템에서 플러그인 접근법을 분석하기 위한 일반적인 도구로 제시됩니다. 제어하기 어려운 편향 함수로부터 분석을 분리하고 명시적인 리아푸노프 함수를 사용함으로써, 이 프레임워크는 복잡한 계획 알고리즘에 대한 유한 샘플 보장을 확립하는 강력한 방법을 제공합니다.
3. LP 기반 정책의 강건성: 미세한 섭동 분석은 LP 완화가 모델 섭동에 대해 내재적인 강건성을 가진다는 점을 밝혀냅니다. 이 결과는 독립적인 가치가 있으며, 문헌에 등장하는 다른 인덱스 및 LP 우선순위 정책들을 분석하기 위한 강건성 모듈로 사용될 수 있습니다.

저자들은 자신들의 결과가 평균 보상 체계에서 직접적으로 샘플 복잡도로 변환되지 않는 회귀(regret) 경계나 점근적 최적성 결과를 넘어, 이러한 환경에 대한 최초의 유한 샘플 PAC 보장임을 강조합니다.