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

Resource information

Authors

Xihe Gu, Urbashi Mitra, Tara Javidi

Research area

Machine learning

Application domain

General AI research

AI methods

Reinforcement learning

Research topics

cs.LG

arXiv record date

2026-10-18

Publication

arXiv

Upstream last modified

Oct 20, 2026

Last record update

Nov 4, 2026

Abstract

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 $\widetildeO(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.