기술적 요약: 제어된 마르코프 연쇄의 모델 기반 부트스트랩

문제 정의

본 논문은 행동 정책이 비정상적이거나 과거 의존적일 수 있는 환경에서 유한 제어된 마르코프 연쇄 (CMC) 에 대한 통계적 추론의 과제를 다룹니다. 이러한 시나리오는 데이터가 정상성 또는 마르코프성 가정을 반드시 만족하지 않는 알려지지 않은 정책 $\pi_b$에 의해 수집되는 오프라인 강화학습 (RL) 에서 흔하게 발생합니다.

마르코프 연쇄에 대한 기존 부트스트랩 방법들은 종종 정상성이나 특정 혼합 조건에 의존하는데, 이는 과거 의존적 제어를 갖는 일반적인 CMC 에서는 성립하지 않습니다. 또한, 중심극한정리 (CLT) 에 기반한 표준 플러그인 신뢰구간 (CIs) 은 공분산 추정을 필요로 하며, 이는 유한 표본 성능을 저하시킬 수 있습니다. 저자들은 두 가지 미해결 문제를 식별했습니다:

1. 제어 정책의 정상성이나 마르코프성을 요구하지 않고 유한 CMC 를 위한 모델 기반 부트스트랩을 개발할 수 있는가?
2. 그러한 부트스트랩 추정량의 분포적 일관성을 확립하고 오프-정책 평가 (OPE) 및 최적 정책 복원 (OPR) 과 같은 하류 RL 작업으로 확장할 수 있는가?

방법론

모델 및 데이터 설정

저자들은 상태 공간 $\mathcal{S}$와 행동 공간 $\mathcal{A}$를 갖는 유한 CMC $\{(X_i, A_i)\}_{i \ge 0}$를 고려합니다. 전이 커널은 $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$입니다. 관찰된 오프라인 데이터셋 $\mathcal{D}_n$은 알려지지 않은 행동 정책 $\pi_b$에 의해 생성된 고정 길이 $T$의 $K$개 에피소드로 구성되며 ($n=KT$), 정책$\pi_b$는 비정상적이고 과거 의존적일 수 있습니다.

$\mathcal{D}_n$으로부터 저자들은 다음을 계산합니다:

• 카운트 기반 경험적 전이 추정량: $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• 경험적 행동 정책: $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

모델 기반 부트스트랩 절차

제안된 방법은 경험적 전이 커널 $\hat{M}$과 경험적 행동 정책 $\hat{\pi}_b$를 사용하여 부트스트랩 CMC $\{(X^*_i, A^*_i)\}_{i \ge 0}$를 구성합니다.

1. 초기화: 각 부트스트랩 반복 $j$에 대해, 과정은 원래 에피소드의 관찰된 초기 상태 $X^{*(k,j)}_0 = X^{(k)}_0$에서 시작합니다.
2. 시뮬레이션: 전이는 행동 $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$와 다음 상태 $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$를 샘플링하여 순차적으로 생성됩니다.
3. 추정: 시뮬레이션된 데이터셋 $\mathcal{D}^*_n$으로부터 부트스트랩 전이 추정량 $\hat{M}^*$이 계산됩니다.
4. 반복: 이 과정은 $B$번 반복되어 부트스트랩 반복 $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$를 얻습니다.

하류 응용

부트스트랩은 두 가지 하류 목표에 적용됩니다:

• 오프-정책 평가 (OPE): $\hat{M}$과 $\hat{M}^*$를 사용하여 벨만 방정식을 풀고 고정된 목표 정책 $\pi$에 대한 가치 함수 $V_\pi$와 Q-함수 $Q_\pi$를 추정합니다.
• 최적 정책 복원 (OPR): $\hat{M}$과 $\hat{M}^*$를 사용하여 최적 벨만 방정식을 풀고 최적 가치 함수 $V_\star$와 $Q_\star$를 추정합니다.

신뢰구간은 부트스트랩 반복의 경험적 분위수 (백분위수 CI) 또는 피벗 방법을 사용하여 구성됩니다.

주요 이론적 기여

1. 부트스트랩 분포적 일관성

본 논문은 잠재적으로 비정상적이거나 과거 의존적인 정책을 갖는 유한 CMC 에서 모델 기반 부트스트랩에 대한 최초의 분포적 일관성 결과를 확립합니다.

• 단일 연쇄 체계 ($K=1, T \to \infty$): 정리 1 은 데이터 $\mathcal{D}_n$에 조건부일 때, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$이 가우스 극한 $N(0, \bar{\Lambda})$으로 분포 수렴하며, 이는 원래 추정량 $\sqrt{n} \text{vec}(\hat{M} - M)$의 점근적 분포와 일치함을 증명합니다.
• 에피소드 체계 ($T$ 고정, $K \to \infty$): 제안 1 은 에피소드를 의사 전이를 통해 단일 연쇄에 임베딩함으로써 에피소드 설정으로 이 결과를 확장합니다. 에피소드가 리셋으로 분리되어 있더라도 부트스트랩이 일관성을 유지함을 확인합니다.

기술적 도구:

• 방문 횟수에 대한 새로운 부트스트랩 대수의 법칙 (LLN) ($N^*_s/n \to p_s$ a.s.).
• 약한 혼합 조건 (가정 1–3) 을 활용하여 의존성 구조를 처리하는 부트스트랩 전이 증가분에 대한 **마팅갈 중심극한정리 (CLT)**의 새로운 적용.

2. OPE 및 OPR 에 대한 유효성

제안 2 는 델타 방법을 사용하여 가치 및 Q-함수 추정량으로 분포적 일관성을 확장합니다.

• 저자들은 전이 블록 행렬에 대한 벨만 연산자의 하마르 미분 가능성을 검증합니다.
• OPE 의 경우, $V_\pi$와 $Q_\pi$의 부트스트랩 반복은 원래 추정량과 동일한 가우스 극한으로 수렴합니다.
• OPR 의 경우, 비퇴화 조건 (최적 행동과 비최적 행동 간에 엄격히 양수인 갭) 하에서 $V_\star$와 $Q_\star$의 부트스트랩 반복도 분포적 일관성을 달성합니다.

실험 결과

저자들은 불균형한 방문 빈도와 거의 퇴화된 최적 정책으로 인해 탐색이 어려운 것으로 알려진 벤치마크인 RiverSwim 문제 ($S=6, A=2$) 에서 유한 표본 성능을 평가합니다.

• 설정: 다양한 표본 크기 ($n$) 와 에피소드 길이 ($T$) 에 걸쳐 에피소드 부트스트랩 (Hao et al., 2021) 과 플러그인 CLT 신뢰구간 (Zhu et al., 2024; Su et al., 2026) 과 비교했습니다.
• 결과:
  • 제안된 모델 기반 부트스트랩 백분위수 신뢰구간은 베이스라인을 크게 능가하여 잘 샘플링된 체계 ($n \ge 500$) 에서 명목 커버리지에 근접한 성능을 달성했습니다 (예: 50% 의 경우 0.48–0.54, 90% 의 경우 0.87–0.94, 95% 의 경우 0.92–0.97).
  • 베이스라인 (에피소드 부트스트랩 및 플러그인 CLT) 은 특히 작은 표본 크기와 짧은 에피소드 길이에서 체계적인 언커버리지를 나타냈습니다.
  • 에피소드 부트스트랩은 $n=50$이고 $T \ge 50$일 때 완전히 실패했습니다 (커버리지가 0 으로 붕괴). 이는 단일 에피소드가 부트스트랩 변동을 제거하기 때문입니다.
  • 성능은 드물게 방문된 상태 - 행동 쌍 (상태 6 근처) 과 짧은 시간 범위 ($T=10$) 에서 가장 약했으며, 이는 점근적 정규성과 비퇴화성의 이론적 제약과 일치합니다.

중요성 및 한계

중요성:
본 논문은 행동 정책이 비정상적이거나 과거 의존적일 수 있는 영역의 격차를 해소하여 오프라인 RL 에서 모델 기반 부트스트랩 사용에 대한 엄격한 이론적 기반을 제공합니다. 이는 명시적인 공분산 추정을 요구하지 않으면서 전이 커널과 하류 RL 목표 모두에 대해 점근적으로 유효한 신뢰구간을 생성함을 보여줍니다.

한계 및 향후 방향 (저자들이 명시한 바):

• 보상 함수: 분석은 알려진 보상 함수를 가정합니다. 저자들은 보상 추정량이 수렴한다면 유효성이 유지될 가능성이 있음을 언급하지만, 보상 추정 오차의 유한 표본 효과는 분석되지 않았습니다.
• 상태 - 행동 공간: 현재 결과는 유한 상태 - 행동 공간으로 제한됩니다. 함수 근사 또는 연속 공간으로의 확장은 향후 작업으로 남깁니다.
• 점근적 체계: 에피소드 분석은 $T$가 고정되고 $K \to \infty$라고 가정합니다. $K$가 고정 ($K>1$) 되고 $T \to \infty$인 체계에서 부트스트랩의 일관성은 여전히 미해결 질문입니다.
• 비정상 정책: 이론이 비정상 정책을 수용하지만, 수치 실험은 주로 정상 행동 정책을 사용했습니다. 비정상 정책을 사용한 추가 실험이 제안됩니다.