기술 요약: 연속 상태 MDP에서 평균 비용 기준 하의 Q-러닝

1. 문제 정의

본 논문은 연속적인 상태 및 행동 공간을 가지며 **무한 시간 지평 평균 비용 기준(infinite-horizon average cost criterion)**을 따르는 마르코프 결정 과정(MDP)을 해결하는 과제를 다룬다. 모델은 $(X, U, \mathcal{T}, c)$ 튜플로 정의되며, 여기서 $X$와 $U$는 표준 보렐 공간(complete, separable metric spaces)이고, $\mathcal{T}$는 전이 커널, $c$는 비용 함수이다. 목적은 다음의 장기 평균 비용을 최소화하는 정책 $\pi$를 찾는 것이다:
$$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$$

저자들은 벨만 연산자의 수축 성질(contraction properties)을 사용하여 연속 공간에서의 유한 지평 및 할인 비용 문제를 해결하는 연구는 잘 정립되어 있는 반면, 평균 비용 문제는 독특한 어려움을 안고 있음을 강조한다. 구체적으로, 할인 계수의 부재는 즉각적인 수축 매핑을 제거하여 대안적인 안정성 및 에르고디시티(ergodicity) 가정을 요구한다. 또한, 기존의 평균 비용 강화 학습(RL) 문헌은 주로 유한 공간에 집중하거나, 일반적인 연속 공간에 대한 적용성을 제한하는 엄격한 구조적 가정(예: 선형 역학, 리프시츠 정책)을 부과하는 경향이 있다.

2. 방법론

본 논문은 두 가지 접근 방식인 **양자화를 통한 유한 근사(finite approximation via quantization)**와 이러한 근사를 위해 설계된 강화 학습 알고리즘을 채택한다.

2.1 이산화 및 근사

핵심 방법론은 양자화를 통해 연속 공간을 유한 상태, 유한 행동의 근사 MDP로 구축하는 것이다.

• 상태 양자화: 상태 공간 $X$를 대표 상태 $y_i$를 가진 서로 소의 빈(bin) $\{B_i\}_{i=1}^M$으로 분할한다. 매핑 $q: X \to Y$ (여기서 $Y$는 유한한 대표 집합)가 정의된다.
• 행동 양자화: 행동 공간 $U$는 유한 집합 $\Lambda$에 의해 근사된다.
• 근사 모델 구축: 근사 모델 $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$은 가중 측도 $\mu$(흔히 상태 프로세스의 불변 측도)를 사용하여 정의된다. 근사된 비용 및 전이 커널은 양자화 빈에 대한 원래 함수들의 평균이다:
  $$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$$
• 완화된 연속성 조건: 중요한 방법론적 변화는 기존 근사 문헌(예: Saldi et al., 2018)에서 표준이었던 전 변동(Total Variation, TV) 연속성 조건을 완화하는 것이다. 저자들은 다음 조건 하에서 근사 결과를 입증한다:
  1. 약한 연속성 (Feller): 격자 크기가 작아짐에 따라 오차의 점근적 수렴에 충분하다.
  2. 와서스타인(Wasserstein) 연속성: 격자 크기가 작아짐에 따라 명시적인 수렴 속도(오차 범위)를 설정하는 데 충분하다.

2.2 강화 학습 알고리즘

본 논문은 데이터로부터 근사 모델의 최적 정책을 직접 학습하기 위한 양자화된 Q-러닝(Quantized Q-Learning) 알고리즘을 제안한다.

• 동기식 알고리즘 (Algorithm 1): 유한 격자의 모든 상태-행동 쌍에 대해 Q-값을 동시에 업데이트한다. 이는 사전 결정된 측도에 따라 각 빈에서 상태를 샘플링하는 것에 의존한다.
• 비동기식 알고리즘 (Algorithm 2): 원래의 연속 프로세스로부터 추출된 단일 궤적(trajectory)을 기반으로 Q-값을 업데이트한다. 이는 더 실용적이지만, 양자화된 프로세스 $q(X_t)$가 마르코프 체인이 아니기 때문에(양자화된 상태의 관점에서는 부분 관측 MDP임) 비마르코프 노이즈 항을 도입한다.
• 수렴 메커니즘: 평균 비용 기준과 Q-반복값의 유계성 결여(할인된 경우와 달리)를 처리하기 위해, 저자들은 다음을 활용한다:
  • 동기식 업데이트를 위한 스팬 준-노름(Span Semi-norms).
  • 에르고디시티 가정: 탐사 정책(exploration policy)은 양자화된 빈 전체에 걸쳐 완전한 지지(full support)를 갖는 유일한 불변 측도를 유도해야 한다.
  • 이동 업데이트(Shifted Updates): 비동기식 알고리즘은 특정 빈을 기준으로 하는 참조 값을 차감하여 반복을 안정화하며, 양자화된 프로세스를 POMDP로 취급한다.

3. 주요 기여

본 논문은 세 가지 주요 기여를 통해 연속 공간의 평균 비용 제어 분야의 최신 기술 수준을 진전시킨다:

1. 더 약한 조건을 갖춘 근사 이론:

   • 저자들은 이전 연구들(예: Saldi et al., 2018)에서 요구되었던 엄격한 전 변동 연속성에서 벗어나, 약한 연속성 및 와서스타인 연속성 하에서의 오차 범위를 제공한다.
   • 와서스타인 연속성(수축 상수 $K_T < 1$ 포함) 하에서, 최적 평균 비용의 오차는 양자화 오차(구체적으로 $L_X^\delta$)에 비례하는 속도로 감소함을 입증한다.
   • 약한 연속성만으로도, 이산화가 미세해짐에 따라 근사된 정책의 비용이 최적 비용으로 점근적으로 수렴함을 증명한다.

2. 양자화된 Q-러닝의 수렴:

   • 본 논문은 연속 공간에 대한 동기식 및 비동기식 Q-러닝 알고리즘의 거의 확실한(almost sure) 수렴을 입증한다.
   • 결정적으로, 이 알고리즘들이 단순히 원래의 연속 모델이 아니라, 구성된 유한 근사 모델의 최적 Q-값으로 수렴함을 증명한다. 양자화된 프로세스는 엄밀히 말해 마르코프적이지 않으므로 이 구분은 매우 중요하다.
   • 이 분석은 할인 비용에서 더 까다로운 평균 비용 기준으로 Kara와 Yüksel (2023) 등의 기존 결과를 일반화하며, 이를 위해 유계되지 않은 Q-반복값을 처리하기 위한 새로운 기술적 분석을 요구한다.

3. 근사 최적성 보장 (Near-Optimality Guarantees):

   • 근사 오차 범위와 학습 알고리즘의 수렴을 결래하여, 양자화된 Q-러닝을 통해 학습된 정책이 원래의 연속 MDP에 대해 **근사 최적(near-optimal)**임을 보여준다.
   • 성능 손실은 비용 및 전이 커널의 리프시츠 상수와 양자화 해상도에 의해 명시적으로 제한된다.

4. 주요 결과 및 정리

• 정리 1 & 2 (근사 경계): 원래 모델의 최적 평균 비용($\rho$)과 근사 모델의 최적 평균 비용($\hat{\rho}$) 사이의 차이에 대한 상한을 설정한다.
  • 와서스타인 연속성 하에서: $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$, 여기서 $L_X$는 양자화 오차이다.
  • 약한 연속성 하에서: $\lim_{n \to \infty} \rho(\pi_n) = \rho$.
• 정리 5 & 6 (알고리즘 수렴): 동기식 및 비동기식 Q-러닝 반복이 유한 근사 모델의 최적 Q-값으로 수렴함을 증명한다. 비동기식 수렴은 상태 프로세스의 에르고디시티에 의존한다.
• 따름정리 1: 근사와 학습 결과를 결래하여, 학습된 정책 $\hat{\pi}$가 $\rho(\hat{\pi}) - \rho \leq \epsilon$을 만족하며, 여기서 $\epsilon$은 이산화 격자 크기가 0으로 수렴함에 따라 사라짐을 보여준다.

5. 의의 및 주장

저자들은 이 연구를 연속 공간의 평균 비용 MDP를 위한 강화 학습의 미해결 과제를 해결하는 작업으로 포지셔닝한다.

• 가정의 완화: 본 논문은 실무적 모델에서 지나치게 제한적일 수 있는 전 변동 연속성에서 벗어나 약한 및 와서스타인 연속성으로 이동함으로써 중요한 이론적 진전을 이루었다고 주장한다. 이는 이론적 보장을 제공할 수 있는 시스템(예: 가법 노이즈 또는 특정 역학을 가진 시스템)의 범위를 넓힌다.
• 이론과 실제의 연결: Q-러닝이 잘 정의된 유한 근사의 해로 수렴함을 증명함으로써, 본 논문은 연속 평균 비용 설정에서 이산화 기반 RL을 사용하는 것에 대한 엄격한 정당성을 제공한다. 이는 "근사 최적성"이 학습 알고리즘의 산물이 아니라 근사 품질의 직접적인 결과임을 명확히 한다.
• 비마르코프적 양자화 처리: 본 논문은 양자화된 상태 프로세스가 MDP가 아닌 POMDP라는 기술적 어려움을 명시적으로 다루며, 평균 비용 기준 하에서 비동기식 학습에 대한 수렴 증명을 제공하여 기존 문헌(예: Wan et al., 2021)에서 지적된 공백을 메운다.

본 논문은 연속 제어 문제에 대한 수치적 사례 연구를 통해 결론을 맺으며, 양자화율이 증가함에 따라 가치 함수가 수렴하고 후회(regret)가 감소함을 보여줌으로써 이론적 경계를 검증한다.