Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments

We propose **Variance Driven Exploration (VarDE), a principled approach for pure exploration in highly stochastic environments, where the exploration process is dominated by stochastic variance. VarDE is built on a fundamental principle: sampling effort should be allocated to minimize the uncertainty of the final decision. We formalize the uncertainty of the final decision through a smooth decision function and derive allocation rules that explicitly capture how stochastic noise in individual components affects the reliability of the final output. We apply this methodology to three core problems of pure exploration -- Best Arm Identification (BAI), Monte Carlo Tree Search (MCTS), and Best-Policy Identification (BPI) -- with theoretical guarantees on variance decay and simple regret. Empirically, we demonstrate consistent and significant improvements of VarDE over existing methods, with especially strong gains in highly stochastic environments.

In machine learning, "pure exploration" tasks require an AI to identify the absolute best decision from a set of options, without worrying about the costs incurred during the testing phase. However, in highly noisy environments, standard algorithms often mistake random fluctuations for true signals, wasting their limited testing budget and failing to find the best option. To address this problem, we propose Variance Driven Exploration (VarDE). Instead of relying on traditional optimistic guesses, VarDE allocates testing efforts based on a simple principle: focus on the areas that most reduce the uncertainty of the final decision. It achieves this by combining two factors: how strongly the final decision depends on a specific component, and how noisy that component is. We applied this method to three core pure exploration problems—Best-Arm Identification, Monte Carlo Tree Search, and Best-Policy Identification. The results demonstrated consistent and significant performance improvements over existing methods, especially in highly stochastic environments.