$κ$-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.