기술 요약: 온라인 강화학습을 위한 자동 탐사(Auto-exploration)

문제 정의

본 논문은 유한한 상태 및 행동 공간을 가진 무한 시계열 할인 마르코프 결정 과정(MDP)에 대한 온라인 강화학습(RL)에서의 근본적인 **탐사-활용 딜레마(exploration-exploitation dilemma)**를 다룹니다. 특히, 데이터가 생성 모델이나 오프라인 배치(batch)로부터가 아니라, 하나의 궤적(trajectory)에 의해 마르코프 체인(Markov chain)으로서 생성되는 온-폴리시(on-policy) 설정을 대상으로 합니다.

현재의 최첨단 알고리즘들은 수렴을 보장하기 위해 종종 두 가지 문제가 있는 가정을 사용합니다:

1. 충분한 탐사(Sufficient Exploration): 모든 행동이 어떤 상태에서도 0보다 큰 확률로 선택될 수 있다고 가정합니다(흔히 명시적인 $\epsilon$-greedy 탐사를 통해 강제됩니다). 그러나 비정규화된 온-폴리시 설정에서는 최적 정책이 결정론적일 수 있어 이 가정이 실패할 수 있습니다.
2. 알고리즘 의존적 파라미터: 기존의 샘플 복잡도 경계는 중간 정책들에 의해 유도된 마르코프 체인의 혼합 시간(mixing time) 및 **정상 분포(stationary distribution)**와 같은 파라미터에 의존하는 경우가 많습니다. 이러한 파라미터들은 실제 적용 시 알 수 없으며 임의로 커질 수 있어, 최적성이 떨어지거나 구현 불가능한 알고리즘을 초래할 수 있습니다.

본 논문은 명시적인 탐사 스케줄 없이, 혼합율이나 정상 분포에 대한 사전 지식 없이도 알고리즘 독립적인 $O(\epsilon^{-2})$ 샘플 복잡도를 달와할 수 있는 파라미터 프리(parameter-free) 방법론을 개발하고자 합니다.

방법론

저자들은 **확률적 정책 미러 디센트(Stochastic Policy Mirror Descent, SPMD)**에 통합된 **자동 탐사(Auto-exploration)**라는 새로운 클래스의 방법을 소개합니다. 핵심 아이디어는 고정된 하이퍼파라미터가 아닌 데이터 기반 메커니즘을 통해 상태와 행동 공간을 자동으로 탐사하는 것입니다.

1. 이론적 토대: 새로운 수렴 보장

저자들은 먼저 SPMD에 대한 새로운 고확률 최종 반복(last-iterate) 수렴 보장을 확립합니다. 평균 반복(average-iterate) 또는 최적 반복(best-iterate) 수렴에 집중하는 기존 연구와 달리, 이 분석은 최종 정책이 최적에 근접함을 보장합니다.

• 가정: 분석은 Q-함수가 유계(bounded)이고, 확률적 추정치가 작은 가중치 편향(weighted bias)과 유계된 2차 모멘트를 가진다는 것만을 요구합니다.
• 기법: 증명은 반복(iterates)의 새로운 그룹화와 할인 계수 $\gamma$에 적응된 브레그만 발산(Bregman divergence)의 새로운 분석을 활용하며, 이를 통해 이전 경계보다 $O((1-\gamma)^{-2})$ 배만큼 개선된 결과를 도출합니다.

2. 테이블 설정(Tabular Setting): 동적 탐사 시간

테이블 케이스의 경우, 저자들은 알려지지 않은 혼합 시간을 대체하기 위해 **동적 탐사 시간(dynamic exploration time)**을 제안합니다.

• 절단된 온-폴리시 몬테카를로(Truncated On-Policy Monte Carlo, TOMC): Q-함수를 위한 절단된 추정기를 사용합니다. 특정 시간 내에 상태-행동 쌍이 방문되지 않으면, 해당 쌍을 선택하지 않도록 큰 값을 할당합니다.
• 동적 정지(Dynamic Stopping): 고정된 탐사 지평 대신, 알고리즘은 상태-행동 쌍의 **첫 번째 도달 시간(first hitting time)**에 의해 결정되는 기간 동안 실행됩니다. 이 시간은 무작위적이며 데이터에 의해 결정됩니다.
• 암묵적 탐사(Implicit Exploration): 이 방법은 기약 마르코프 체인을 유도하는 결정론적 최적 정책의 존재에 의존합니다. 이 가정하에서, 저자들은 명시적인 무작위화 없이도 정책이 자연스럽게 "도달하기 어려운" 상태를 탐사(암묵적 상태 탐사)함을 증명합니다.

3. 선형 함수 근사(Linear Function Approximation): 새로운 샘플링 분포

선형 함수 근사 설정의 경우, 저자들은 알려지지 않은 정상 분포로부터 샘플링하는 문제의 어려움을 해결합니다.

• 할인 방문 분포(Discounted Visitation Distribution): 저자들은 정상 분포 대신, 임의의 기점 상태(origin state)로부터 시작하는 **할인된 상태 방문 분포($\kappa^\pi_{s_{or}}$)**에 기반한 새로운 샘플링 분포를 제안합니다. 이 분포는 항상 잘 정의되어 있으며 혼합 시간을 추정할 필요가 없습니다.
• 조건부 템포럴 디퍼런싱(Conditional Temporal Differencing, CTD): 알고리즘은 두 단계의 샘플링 전략을 사용하여 확률적 연산자를 구성합니다:
  1. 상태 탐사: 고정된 기점 상태 $s_{or}$에 도달하기 위해 섭동된 정책 $\tilde{\pi}^{(S)}$를 사용합니다.
  2. 행동 탐사: $s_{or}$에 도달하면, 현재 정책 $\pi$(선택적 행동 탐사 $\tilde{\pi}^{(A)}$ 포함)로 전환하여 기하 분포를 따르는 단계 수만큼 진행합니다.
• 편향 처리: 이 방법은 함수 근사 오차가 알려진 경우(충분한 암묵적 탐사)와 알려지지 않은 경우(편향에 대비하기 위해 명시적 탐사가 필요한 경우)를 구분합니다.

주요 기여

1. 알고리즘 독립적인 $O(\epsilon^{-2})$ 샘플 복잡도: 본 논문은 테이블 및 선형 함수 근사 설정 모두에서 알고리즘 독립적인 $O(\epsilon^{-2})$ 샘플 복잡도를 달성하는 최초의 SPMD 기반 온-폴리시 RL 알고리즘을 제시합니다. 결정적으로, 복잡도 경계는 문제 특유의 상수(예: 최적 정책의 혼합율)에는 의존하지만, 알고리즘 의존적 파라미터(예: 중간 정책의 혼합율)에는 독립적입니다.
2. 파라미터 프리 구현: 제안된 방법들은 혼합 시간, 정상 분포 또는 기타 문제 의존적 상수에 대한 사전 지식을 요구하지 않습니다. 이들은 실시간 관측값(도달 시간)에서 유도된 동적 탐사 시간을 활용합니다.
3. 고확률 최종 반복 수렴: 저자들은 기존 문헌에서 흔히 볼 수 있는 평균 반복 또는 후회(regret) 경계보다 더 강력한 보장인 SPMD의 최종 반복에 대한 엄격한 고확립 수렴 보장을 제공합니다.
4. 새로운 샘플링 분포: 함수 근사 설정에서, 정상 분포에 의존하는 방식보다 더 일반적인 클래스의 마르코프 체인을 포괄하는 할인된 방문 분포 기반의 샘플링 분포를 도입했습니다.

결과

• 테이블 설정: 알고리즘은 최대 $\tilde{O}(D_{expl}(\delta) \cdot |A|^{2-\frac{1}{2}+\log_2(1/[1-\gamma])} (1-\gamma)^{-5} \epsilon^{-2})$ 샘플을 사용하여 확률 $1-\delta$로 $\epsilon$-정확도를 달성합니다. 여기서 $D_{expl}(\delta)$는 최적 정책의 혼합 특성과 관련된 알고리즘 독립적 상수입니다.
• 함수 근사: 선형 설정에 대해서도 유사한 샘플 복잡도가 확립되었습니다. 분석 결과 트레이드오프가 드러납니다: 만약 함수 근사 오차가 알려져 있다면 암묵적 탐사만으로 충분하지만, 알려져 있지 않다면 편향에 대비하기 위해 명시적 탐사가 필요합니다.
• 기존 연구 대비 개선: 샘플 복잡도는 기존의 암묵적 탐사 경계(예: [37])를 $O(|A|^{1/2}/(1-\gamma))$ 배만큼 개선하며, 알고리즘 특유의 혼합율에 대한 의존성을 제거합니다.

의의 및 주장

본 논문은 명시적인 탐사 스케줄 없이 유한 상태 및 행동 할인 RL에 대해 알고리즘 독립적인 온-폴리시 $O(\epsilon^{-2})$ 샘플 복잡도를 달성하는 데 있어 오랜 미해결 과제를 해결했다고 주장합니다.

• 실용성: 알려지지 않은 혼합율이나 정상 분포에 기반한 하이퍼파라미터 튜닝의 필요성을 제거함으로써, 제안된 방법들은 "구현이 간단"하고 견고합니다.
• 이론적 엄밀성: 저자들은 실제 알고리즘의 출력물인 최종 반복(last iterate)에 대해 성립하는 비점근적(non-asymptotic) 경계를 제공함으로써 이론적 보장과 실제 구현 사이의 간극을 메웁니다.
• 참신성: 동적 정지 시간(dynamic stopping times)을 통한 "자동 탐사" 개념과 샘플링을 위한 할인된 방문 분포의 사용은 온라인 RL의 탐사에 대한 이해를 진전시키는 참신한 기여로 제시됩니다.

저자들은 이 연구를 환경의 역학(및 그에 따른 혼합 특성)을 알 수 없는 실제 환경에서 효율적인 RL 알고리즘을 구현 가능하게 만드는 단계로 위치시킵니다.