다항 로지스틱 (Multinomial Logistic) MDP를 위한 미니맥스 최적 분산 인식 후회 한계 (Minimax Optimal

우리는 전이(transition)가 다항 로지스틱 (Multinomial Logistic, MNL) 모델로 모델링되는 에피소드형 마르코프 결정 과정 (Markov Decision Processes, MDPs)에 대한 강화학습 (Reinforcement Learning)을 연구합니다. MNL 혼합 MDP를 위한 기존 알고리즘들은 $d$가 특징 차원 (feature dimension), $H$가 에피소드 길이 (episode length), $T$가 에피소드 횟수일 때 $\smash{\tilde{O}(dH^2\sqrt{T})}$ (Li et al., 2024)의 후회 (regret)를 산출합니다. 로지스틱 밴딧 (logistic bandit) 문헌 (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026)에서 영감을 받아, 우리는 학습자의 궤적 (trajectory)을 따라 최적의 다운스트림 가치 함수 (downstream value function)의 정규화된 평균 분산 (normalised average variance)을 측정하는 문제 의존적 상수 $\smash{\bar\sigma_T \leq 1/2}$를 도입합니다. 우리는 $\smash{\tilde{O}(dH^2\bar\sigma_T\sqrt{T})}$의 후회를 달성하는 알고리즘을 제안하며, 이는 최악의 경우 기존의 한계를 회복하면서 구조화된 MDP (structured MDPs)에 대해서는 이를 개선합니다. 예를 들어, KL 제약 로버스트 MDP (KL-constrained robust MDPs)의 경우 $\bar\sigma_T = O(H^{-1})$가 되어, 호라이즌 (horizon) 의존성을 $H$ 배만큼 줄여줍니다. 나아가 우리는 이에 상응하는 $\smash{\Omega(dH^2\bar\sigma_T\sqrt{T})}$ 하한 (lower bound)을 확립하여, (로그 인자를 제외한) 미니맥스 최적성 (minimax optimality)을 증명하고 MNL 혼합 MDP의 후회 복잡도 (regret complexity)를 최초로 완전히 규명합니다.