cs.LGNov 18, 2026

Bayesian κκ-Explorer for Minimax Model Estimation in MDPs

Authors: Xihe Gu, Urbashi Mitra, Tara Javidi

Organizations: University of Southern California

Abstract

We study active exploration for minimax transition estimation in unknown Markov decision processes (MDPs). Frequentist κκ-Explorer~\citep{gu2026kappa} addresses this problem through a parameterized family of exploration objectives, but requires confidence-bound constructions and joint optimization over plausible transition kernels and occupancy measures, introducing a computational burden that limits its practical applicability. We develop Bayesian κκ-Explorer, which simplifies this procedure by placing Dirichlet priors on the transition distributions. Under the posterior mean estimator, the posterior expected squared ℓ2\ell_2 error equals the total posterior variance, providing a closed-form exploration signal. The algorithm plans under the posterior mean model, eliminating confidence-set optimization. Under the stated assumptions, this simpler planning procedure retains the O~(T−1/3)\widetilde{O}(T^{-1/3}) surrogate convergence rate of frequentist κκ-Explorer. We further bound the maximum posterior variance relative to the optimal asymptotic minimax allocation benchmark. Experiments on Pendulum, Mountain Car, and Taxi demonstrate lower worst-case transition-estimation errors than the tested baselines.

Figures & tables

Explore similar work

CardsList
  1. κκ-Explorer: Minimax Active Model Estimation in MDPs

    Feb 23, 2026Xihe Gu, Urbashi Mitra, Tara JavidiFrank-Wolfe AlgorithmsRL Exploration

  2. Improved Bounds for Reward-Agnostic and Reward-Free Exploration

    Feb 18, 2026Oran Ridel, Alon CohenRL ExplorationReward-Free RL