Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

Motivation

• Known: BPI는 discounted MDP에서 δ-Probably-Correct(δ-PC) 프레임워크로 formalize되며, Al Marjani et al. (2021)이 navigation constraint 하에서 instance-specific lower bound와 NaS 알고리즘의 asymptotic optimality를 제시한 바 있다. 또한 bandit 분야의 Best-Arm Identification(BAI)에서는 Track-and-Stop(TAS)에 대한 non-asymptotic guarantee가 최근 연구(Degenne et al., 2019; Poiani et al., 2025a)를 통해 이미 확립되었다.
• Gap: MDP 환경에서의 BPI, 특히 NaS 및 그 변형들에 대한 기존 분석은 전적으로 asymptotic(δ→0)에 머물러 있어, finite-confidence 환경에서의 stopping threshold 효과, 데이터 부족 시 sampling distribution의 transient instability 등을 이해할 수 없다는 근본적 한계가 있었다.
• Why: MDP 상에서의 online navigation 설정은 generative model 설정과 달리 단일 trajectory로만 샘플링이 제한되어 change-of-measure 논증, non-homogeneous Markov dynamics, forced exploration 유지 필요성이 결합되어 bandit보다 훨씬 도전적이며, 이에 대한 non-asymptotic 이론은 실용적 알고리즘 설계와 finite-sample 성능 예측에 필수적이다.
• Approach: NaS-type 알고리즘의 finite-confidence sample complexity를 implicit bound 형태로 도출하고, characteristic time의 linear sharpness 가정 하에서 이를 connectivity, mixing, forced exploration, allocation geometry 등의 instance-dependent quantity로 명시적으로 전개하는 이론적 접근을 취한다.

Achievement

Figure 1. Empirical sharpness scaling for the MDP family of

1. Finite-confidence 상한 증명: single-trajectory discounted tabular MDP에서 NaS-type 알고리즘에 대해 δ-correct하며 E[τ] ≤ inf{t : b(t,δ) ≤ (t−√t)T(M)^{-1} − ℓ(t,M)} + O(1) 형태의 implicit non-asymptotic bound를 최초로 증명하였다.
2. 명시적 확장식 도출: characteristic time의 linear sharpness 하에서 E[τ] ≤ Bδ + Õ(√Bδ + T(M)∑ᵢ Aᵢ Bδ^{rᵢ}) (Bδ = T(M)log(1/δ), rᵢ<1) 형태의 명시적 finite-confidence 전개를 얻어 connectivity, curvature, allocation geometry의 기여를 드러냈다.
3. 핵심 기술 요소 개발: adaptive non-homogeneous Markov dynamics 하에서 empirical visitation frequency의 finite-time tracking, transition perturbation에 대한 optimal-allocation selector의 안정성, continuum alternative class에서 목적함수가 임의로 flat할 수 있음을 보이는 sharpness 분석을 제시하였다.

How

• BPI를 δ-PC 프레임워크로 정식화하고 Al Marjani et al. (2021)의 information constraint 및 navigation constraint에 기반한 lower bound를 재검토
• NaS 알고리즘의 sampling rule(오라클 최적 할당을 추적)과 stopping rule의 finite-time 거동을 분석하기 위해 empirical transition kernel의 concentration과 tracking error를 통제
• characteristic time 함수 T(M)의 curvature(선형 sharpness)를 새로운 instance-dependent 속성으로 정의하고, 이를 통해 alternative set 상에서 objective가 flat해지는 정도를 정량화
• 이러한 요소들을 결합하여 implicit bound에서 명시적 finite-δ expansion으로 유도

Originality

• BAI에서의 non-asymptotic TAS 분석(Degenne et al., 2019; Poiani et al., 2025a)을 MDP의 navigation-constrained BPI 설정으로 확장한 최초의 시도
• characteristic time의 curvature(sharpness)를 도입하여 alternative class의 flatness가 sample complexity에 미치는 영향을 명시적으로 정량화한 점이 새로움
• 단일 trajectory 제약 하 non-homogeneous adaptive Markov dynamics에서 empirical visitation frequency의 finite-time tracking 이론을 새롭게 구축

Limitation & Further Study

• deterministic reward를 가정하고 있어 stochastic reward를 포함하는 일반적인 MDP로의 확장이 필요
• linear sharpness 가정이 성립하지 않는 인스턴스(더 일반적인 curvature 형태)에 대한 분석은 다루지 않음
• 본문 발췌 내용상 실험적 검증(Figure 1 외)이 제한적으로 보이며, 실제 대규모 MDP에서의 실용적 성능 검증이 추가로 필요
• 상한(upper bound)만 제시되었으며, non-asymptotic lower bound와의 tightness 비교가 이루어지지 않음

Evaluation

총평: BPI 분야에서 오랫동안 미해결로 남아있던 non-asymptotic guarantee 문제를 다루는 이론적으로 견실하고 시의적절한 기여이며, MDP의 구조적 특성(connectivity, curvature)을 명시적으로 드러낸 점이 인상적이나, 실험적 검증과 lower bound와의 비교가 보강되면 더욱 완성도가 높아질 것이다.