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

Feb 23, 2026

κκ-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 O~(t−1/3)\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.
Sep 27, 2026

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayesian regret under arbitrary correlated priors. The difficulty is that a posterior-sampled transition model is coupled with its own continuation value. We overcome this with a common empirical transition reference that isolates the resulting value mismatch and a Bellman-based variance argument that controls it without an extra leading-order state-space factor. For finite-horizon, time-inhomogeneous tabular MDPs with unknown stochastic rewards, this yields the minimax O~(SAH3K)\widetilde{O}(\sqrt{SAH^3K}) regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax O~(dH3K)\widetilde{O}(d\sqrt{H^3K}) rate for linear-mixture MDPs under arbitrary joint parameter priors.
Feb 18, 2026

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

We study reward-free and reward-agnostic exploration in episodic finite-horizon Markov decision processes (MDPs), where an agent explores an unknown environment without observing external rewards. Reward-free exploration aims to enable εε-optimal policies for any reward revealed after exploration, while reward-agnostic exploration targets εε-optimality for rewards drawn from a small finite class. In the reward-agnostic setting, Li, Yan, Chen, and Fan achieve minimax sample complexity, but only for restrictively small accuracy parameter εε. We propose a new algorithm that significantly relaxes the requirement on εε. Our approach is novel and of technical interest by itself. Our algorithm employs an online learning procedure with carefully designed rewards to construct an exploration policy, which is used to gather data sufficient for accurate dynamics estimation and subsequent computation of an εε-optimal policy once the reward is revealed. Finally, we establish a tight lower bound for reward-free exploration, closing the gap between known upper and lower bounds.