기술적 요약: 정책을 밴딧 암으로 간주한 트리 MDP 의 온라인 학습

1. 문제 정의

본 논문은 **트리 마르코프 의사결정 문제 (T-MDP)**에서의 온라인 학습 문제를 다룹니다. T-MDP 는 시작 상태 $s_1$을 루트로 하는 트리 구조로 상태 전이가 이루어지는 유한 시간 마르코프 의사결정 과정으로 정의됩니다. T-MDP 의 정의상 특징은 모든 상태가 $s_1$로부터 정확히 하나의 상태 - 행동 궤적을 통해 도달 가능하다는 점입니다.

이러한 구조는 정적 (stationary) 인 상대와 플레이하는 **완전 기억을 가진 확장형 게임 (extensive-form games with perfect recall)**의 추상화로 자연스럽게 발생합니다. 구체적인 학습 목표는 반복적인 게임 상호작용을 통해 알려지지 않았으나 정적인 상대에 대한 **최적 대응 (best response)**을 찾는 것입니다. 에이전트는 전이 확률 $p$를 알지 못하지만 보상 함수 $r$은 알고 있습니다. 에이전트는 $s_1$에서 시작하는 완전한 에피소드를 플레이하고, 궤적을 관찰하며, 후속 에피소드를 위해 새로운 정책을 선택함으로써 환경과 상호작용합니다.

본 논문은 이 문제를 두 가지 영역에서 조사합니다:

1. PAC (Probably Approximately Correct, 확률적 근사 정확성): 확률 $1-\delta$ 이상으로 $V(\pi) \geq V(\pi^*) - \epsilon$을 만족하는 정책 $\pi$를 출력하는 것을 목표로 하며, 에피소드 수 (샘플 복잡도) 를 최소화합니다.
2. 후회 최소화 (Regret Minimization): $T$개의 에피소드에 걸쳐 누적 후회 $R_T = \sum_{t=1}^T (V(\pi^*) - \mathbb{E}[V(\pi_t)])$를 최소화하는 것을 목표로 합니다.

2. 방법론

핵심 방법론적 혁신은 T-MDP 의 각 정책을 **밴딧 암 (bandit arm)**으로 간주하는 것입니다. 이 접근법은 개념적으로 직관적이지만, 결정론적 정책의 수가 상태 수에 대해 지수적으로 증가 ($|A|^{|S|}$) 하므로, 단순한 구현은 계산 및 메모리 측면에서 불가능합니다.

이를 극복하기 위해 저자들은 MDP 의 트리 구조에 기반하여 정책들이 데이터를 공유하는 프레임워크를 제안합니다.

2.1 가치 분해

저자들은 임의의 정책 $\pi$의 가치 $V(\pi)$가 종료 반환값들의 볼록 결합으로 표현될 수 있음을 입증합니다. 구체적으로, $V(\pi) = \sum_{\sigma \in X(\pi)} q(\sigma) \cdot \rho(\sigma)$이며, 여기서:

• $X(\pi)$는 정책 $\pi$와 일치하는 종료 상태들의 집합입니다.
• $q(\sigma)$는 $\pi$ 하에서 $s_1$로부터 종료 상태 $\sigma$에 도달할 확률입니다.
• $\rho(\sigma)$는 $\sigma$로 가는 경로상의 할인된 누적 보상입니다.

보상 함수가 알려져 있다고 가정하므로 $\rho(\sigma)$는 알려져 있습니다. 학습 문제는 종료 상태에 대한 전이 확률 $q(\sigma)$를 추정하는 것으로 환원됩니다. 중요한 점은 $q(\sigma)$를 추정하기 위한 데이터는 $\sigma$ 자체뿐만 아니라 $\sigma$와 일치하는 어떤 정책을 플레이함으로써 수집될 수 있다는 것입니다.

2.2 신뢰 구간 및 데이터 공유

본 논문은 정책 간 공유된 데이터를 활용하는 $V(\pi)$에 대한 새로운 신뢰 구간을 도입합니다.

• 계수 메커니즘: 종료 상태 $\sigma$에 대해 알고리즘은 플레이된 정책이 $\sigma$와 일치했던 에피소드 수 $n_t(\sigma)$와 $\sigma$가 실제로 도달된 횟수 $n_t^+(\sigma)$를 추적합니다.
• 정책 계수: 정책 $\pi$에 대해 "플레이 계수" $n_t(\pi)$는 $\min_{\sigma \in X(\pi)} n_t(\sigma)$로 정의됩니다. 이는 $\pi$를 평가하기 위한 데이터 가용성의 병목 현상을 나타냅니다.
• 추정자: 경험적 가치 $\hat{V}_t(\pi)$는 경험적 확률 $\hat{q}_t(\sigma) = n_t^+(\sigma) / n_t(\sigma)$로부터 구성된 편향 없는 추정자입니다.

2.3 이론적 기초: 음의 실린더 의존성 (Negative Cylinder Dependence)

중요한 기술적 과제는 종료 상태 도달의 베르누이 결과인 $V(\pi)$를 추정하는 데 사용되는 확률 변수들이 의존적이라는 점입니다. 이는 여러 정책이 동일한 에피소드에서 플레이될 수 있기 때문입니다.

• 저자들은 이러한 변수들이 **음의 실린더 의존성 (NCD)**을 보임을 증명합니다.
• 그들은 동일한 평균을 가진 독립 베르누이 변수인 "쌍둥이 변수 (twin variables)"를 도입하여 의존적 추정자의 편차를 상한합니다.
• 이러한 쌍둥이 변수에 **베르슈타인 부등식 (Bernstein's Inequality)**을 적용하여 높은 확률로 성립하는 신뢰 구간 (UCB 및 LCB) 을 유도합니다. 이를 통해 밴딧 알고리즘 (Lucb 및 Ucb) 을 지수적인 정책 집합에 적용할 수 있게 되며, 각 단계당 다항식 메모리와 계산만 요구됩니다.

2.4 알고리즘

저자들은 두 가지 표준 밴딧 알고리즘을 적용합니다:

1. Lucb-T: PAC 설정을 위한 Lucb 알고리즘의 적용입니다. 이는 가장 높은 가치 추정을 가진 정책과 나머지 정책들 중 가장 높은 상한 신뢰 구간 (UCB) 을 가진 정책을 반복적으로 선택하여, 두 정책이 $\epsilon$만큼 분리될 때까지 플레이합니다.
2. Ucb-T: 후회 최소화를 위한 Ucb 알고리즘의 적용입니다. 이는 모든 에피소드에서 가장 높은 UCB 를 가진 정책을 선택합니다.

두 알고리즘 모두 모든 정책을 나열할 필요 없이 $O(|S||A||k_{max}| + |\Sigma|)$ 시간 내에 최대화 정책을 효율적으로 계산하는 PU(가장 높은 UCB 를 가진 정책) 라는 절차를 활용합니다.

3. 주요 기여

1. 분석적 결과: T-MDP 에서 정책 가치에 대한 신뢰 구간을 설정하는 새로운 집중 부등식 (Theorem 2). 이 결과는 정책 간 공유된 데이터의 의존성을 처리하며, 순차적 작업에서의 학습에 더 넓은 적용 가능성을 가질 수 있습니다.
2. 알고리즘 설계: 정책을 밴딧 암으로 간주하지만 효율적인 구현을 위해 트리 구조를 활용하는 개념적으로 간단한 알고리즘 (Lucb-T 및 Ucb-T).
3. 이론적 보장:
   • 샘플 복잡도 (Theorem 9): Lucb-T 에 대한 인스턴스 의존적 상한으로, 정책 전체가 아닌 종료 상태에 걸쳐 "갭 항"을 합산합니다 ($\sum_{\sigma \in \Sigma} \frac{1}{(\Delta^\epsilon_\sigma)^2}$).
   • 후회 상한 (Theorem 10): Ucb-T 에 대한 인스턴스 의존적 상한으로, 역시 종료 상태에 걸쳐 합산됩니다.
4. 실증적 검증: 다양한 규모의 세 가지 불완전 정보 게임 (소규모: Kuhn Poker, 중규모: Leduc Poker, 대규모: 수백만 개의 상태를 가진 Reconnaissance Blind Tic-Tac-Toe, RBT) 에 대한 구현 및 테스트.

4. 결과

• 확장성: 제안된 알고리즘은 문제 크기가 증가함에 따라 기존 대안들 (vanilla Lucb, Bpi-Ucrl, Mdp-GapE, Mccfr, Uct 등) 보다 일관되게 우수한 성능을 발휘합니다.
• 데이터 공유 효율성: 소규모 문제 (3 카드 Kuhn Poker) 에서는 데이터 공유가 없는 vanilla Lucb 가 경쟁력을 보이지만, 더 큰 변형 (5 카드 Kuhn Poker, Leduc, RBT) 에서는 "트리" 변형 (Lucb-T, Ucb-T) 이 비공유 기준선보다 현저히 우수하여 확장성을 위한 데이터 공유의 필요성을 입증합니다.
• RBT 성능: $2 \times 10^7$개까지의 상태를 가진 게임인 RBT 에서 알고리즘이 성공적으로 작동하며, 다른 PAC 알고리즘 (Bpi-Ucrl, Mdp-GapE) 은 잘 수행하지 못했습니다.
• 이론과 실제: 실험은 이론적 상한과 실제 성능 사이의 격차, 특히 정지 시간이 prohibitively(부적절하게) 클 수 있는 PAC 설정에서 이를 강조하며, 알고리즘이 이론적으로 타당함에도 불구하고 실제 튜닝이 필수적임을 시사합니다.

5. 중요성 및 주장

본 논문은 정책을 암으로 간주함으로써 잘 알려진 밴딧 알고리즘 (Lucb 및 Ucb) 을 T-MDP 로 일반화하는 것을 주요 기여로 주장합니다. 그 중요성은 다음과 같습니다:

• 지수적 복잡성 극복: 데이터 공유를 위해 트리 구조를 활용함으로써, 정책의 수가 지수적임에도 불구하고 다항식 메모리 및 계산 복잡성을 달성할 수 있음을 입증합니다.
• 인스턴스 의존적 상한: 전체 정책 수가 아닌 종료 상태의 "갭"에 의존하는 이론적 보장을 제공하여, 최악의 경우 상한보다 더 정교한 분석을 제공합니다.
• 실용적 적용 가능성: 고정된 상대에 대한 복잡한 순차적 의사결정 문제에서 최적 대응 학습의 실현 가능성을 벤치마크하는 대규모 불완전 정보 게임 (특히 RBT) 에서 접근법을 검증합니다.

저자들은 알려진 보상 함수에 대한 가정이 동기 부여 도메인 (불완전 정보 게임) 에서는 타당하지만, 보상이 알려지지 않은 일반적인 MDP 에 비해 제한적임을 지적합니다. 또한, 상태 방문 확률 (일반 MDP 에서 임의로 작아질 수 있음) 에 대한 의존성을 피하는 상한을 제공하지만, 이는 T-MDP 구조와 알려진 보상의 특정 이점임을 인정합니다.