$κ$-Explorer: Minimax Active Model Estimation in MDPs

Accurately estimating the transition dynamics of an unknown Markov decision process (MDP) is a central problem in reinforcement learning. The accuracy of overall model estimation, however, depends on both the stochasticity of the transitions given state--action pairs, what we call the intrinsic (statistical) complexity of each pair, and the visitation frequency of each state--action pair, dictated extrinsically by the exploration policy and its induced occupancy measure. We propose κ-Explorer, an active exploration algorithm that constructs an exploration reward for each state--action pair, using a κ-powered ratio of estimated intrinsic complexity to extrinsic visitation frequency of each pair. By planning with these rewards, κ-Explorer adapts its extrinsic visitation frequency to the intrinsic complexity of transitions. More specifically, we show that κ-Explorer optimizes a surrogate objective function which bounds the minimax estimation error. Furthermore, we establish a surrogate objective gap of \widetilde{O}(t^{-1/3}), yielding a finite-sample guarantee for sufficiently large κ. Finally, we extend the framework to alternative estimation losses and objectives beyond the minimax setting.