PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Khang Luong, Nam Nguyen, Hoang Ta, Hung The Tran, Tuan Dam

arXiv:2608.21995v1cs.LGcs.AIstat.ML

TL;DR

Pure exploration must allocate samples to reduce uncertainty in the final decision, but local uncertainty measures may not reflect decision-level uncertainty. VarDE targets decision variance through influence-weighted allocation and improves results across BAI, MCTS, and BPI, especially in highly stochastic environments.

  • Problem

    Pure exploration lacks a direct way to allocate samples for minimizing uncertainty in nonlinear final decisions affected by noisy components.

  • Method

    VarDE models the final recommendation as a smooth function of empirical estimates and samples the component with the largest influence-weighted expected variance reduction.

  • Results

    VarDE provides variance-decay and correctness guarantees across BAI, MCTS, and BPI, with consistent empirical improvements and largest gains in highly stochastic environments.

  • Takeaways & Limitations

    Decision-level variance minimization is most beneficial for pure exploration in highly stochastic and heteroscedastic settings.

  • Takeaways & Limitations

    The RL guarantee is asymptotic rather than a finite-sample fixed-budget BPI bound, while first-order variance approximations and dependency assumptions limit the analysis.

Abstract

from arXiv · show

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.

1. Introduction

The paper frames pure exploration as reliable final decision-making under noisy interactions, arguing that optimism-based sampling can confuse stochastic fluctuations with evidence. It introduces VarDE, which allocates samples to reduce decision-level uncertainty, and develops theoretical and empirical results across BAI, MCTS, and BPI.

  • Motivation: Pure exploration evaluates only the final output, such as selecting the best arm, root action, or near-optimal policy, rather than data-collection performance.
  • Problem: Optimism-based allocation can mistake noise for evidence in highly stochastic, heteroscedastic environments, where component estimates differ in informativeness.
  • Method: VarDE models the final recommendation as a smooth decision function and samples the component with the largest first-order expected decrement in decision variance.
  • Instantiations: VarDE is instantiated as VARDE–BAI, VARDE–MCTS, and VARDE–Q-LEARNING, computing influence weights and variance estimates across bandits, planning, and reinforcement learning.
  • Theory: The methodology provides decision-variance decay and correctness guarantees, including exponentially decaying misidentification in BAI and MCTS and almost-sure optimal-policy convergence for VARDE–Q-LEARNING.
  • Empirical validation: Experiments show consistent improvements over strong baselines across bandits, planning, and reinforcement-learning benchmarks, with the largest gains in highly stochastic environments.

2. Related Work

Related work spans confidence- and elimination-based BAI, optimism- and entropy-driven MCTS, and model-based BPI methods that reason about uncertainty. VarDE differs by explicitly allocating exploration to reduce decision uncertainty using influence and variance.

  • Best-arm identification (BAI): Fixed-budget BAI methods use confidence-interval indices or successive reject/elimination schemes to prioritize plausibly optimal arms and discard inferior ones.Examples include UCB-E and UGAPE among confidence-based methods.
  • Best-arm identification (BAI): VARDE–BAI addresses the limitation of mean-driven designs by selecting arms that maximize a decision-variance decrement combining influence and variance.The approach explicitly models heteroscedastic reward variance as a contributor to final-decision reliability.
  • Monte Carlo Tree Search (MCTS): MCTS commonly uses UCT’s UCB-style bonuses, while alternative methods broaden search through randomness, regularization, optimism, entropy, and robust uncertainty-aware planning.These approaches balance exploitation and exploration or diversify action selection in stochastic domains.
  • Monte Carlo Tree Search (MCTS): VARDE–MCTS explicitly weights tree edges by both their influence on the recommended action and their empirical return variance.This distinguishes it from methods that do not optimize how uncertainty along different edges affects action recommendation.
  • Best-policy identification (BPI): BPI research includes minimax and adaptive methods with finite-sample guarantees, often using confidence sets for rewards and transitions followed by optimistic planning.These methods are predominantly model-based and use model uncertainty to determine where to sample.

3. Variance Driven Exploration

VarDE minimizes decision-level uncertainty by allocating samples according to each component’s influence on the final decision and its stochastic noise. Under regularity, nondegeneracy, variance-floor, and independence assumptions, the resulting greedy rule guarantees linear sampling of every component and targets the optimal first-order variance constant.

  • General formulation: VarDE models local stochastic components through empirical means and a global decision variable Y = f(ˆµ), covering arms, tree leaves, and state–action returns.The decision variable can represent a planning-tree root value or a smooth surrogate for the best-arm decision.
  • Decision-level uncertainty: Influence weights quantify how sensitively the global decision changes with each local estimate, while the method combines influence and component noise to reduce Var[Y].The variance decomposition scales each local estimation variance by the squared influence of that component.
  • Greedy allocation: Under Assumption 3.1, Taylor linearization yields influence-weighted local variance terms and a one-sample decrement that defines the greedy VarDE rule.The regularity conditions require bounded observations and a twice continuously differentiable decision function with controlled Hessian behavior.
  • Unified methodology: VarDE unifies stochastic decision processes from flat bandits to hierarchical planners and value-based learners under one principle: minimizing decision-level uncertainty.Its sampling rule selects the component with the largest first-order variance reduction.
  • Guarantees: Ni(t) = Ω(t) for every component, so VarDE provides a decision-level variance decay guarantee under the stated regularity, variance-floor, nondegeneracy, and independence assumptions.The theorem establishes the variance-decay exponent rather than claiming a better exponent than all well-spread allocations.
  • Guarantees: The asymptotic target is the optimal first-order constant induced by the decision-level variance decomposition, distinguishing VarDE through allocation quality rather than a superior exponent.The leading constant distinguishes well-spread allocations when sample counts satisfy Ni(T) = piT + O(1) with pi > 0.

4. Applications

Section 4 instantiates VarDE for Best-Arm Identification, Monte Carlo Tree Search, and Best-Policy Identification, deriving decision-level sampling rules and theoretical guarantees. Across these applications, the method targets uncertainty reduction and establishes exponential or asymptotic performance guarantees under stated assumptions.

  • Applications: VarDE is instantiated in BAI, MCTS, and BPI through a common decision-level uncertainty objective, yielding simple sampling rules and theoretical guarantees.Proofs are deferred to Appendices B, C, and D.
  • Best-Arm Identification: In BAI, VARDE–BAI uses the smooth LSEτ surrogate and greedily selects the arm with the largest expected decision-level variance decrement.The temperature τ trades approximation bias, bounded by τ log K, against curvature scaling as O(τ −1) and O(τ −2) for Hessian-Lipschitzness.
  • Best-Arm Identification: VARDE–BAI identifies the unique best arm with exponentially small error probability, implying exponentially decaying simple regret that is order-optimal up to constant factors.The guarantees assume rewards supported on [0, 1], temperature τ > 0, and warm start η > 0.
  • Monte Carlo Tree Search: In MCTS, VARDE–MCTS treats state–action returns as stochastic components and greedily selects actions producing the largest estimated first-order variance decrement.Simulation and backpropagation follow standard MCTS procedures with max backup.
  • Monte Carlo Tree Search: VARDE–MCTS achieves exponential concentration of value estimates and exponentially small root-action error probability, matching standard exponential MCTS concentration rates.The concentration statements hold under the theorem’s fixed-tolerance conditions and positive simulation counts.
  • Best-Policy Identification: For infinite-horizon BPI, VARDE–Q-LEARNING converges to the optimal action-value function under Robbins–Monro step sizes, infinite visitation, and the stated communicating-MDP assumptions.The resulting greedy policies are optimal for all sufficiently large T, up to tie-breaking; adaptive variance-driven Q-learning remains an open theoretical direction.

5. Experiments

Across BAI, MCTS, and Q-learning experiments, VarDE consistently improves fixed-budget exploration performance, especially in highly stochastic environments. Ablations further show that combining influence weights with empirical variance is necessary for these gains.

  • Best-Arm Identification: VARDE–BAI achieves the lowest error probability in all four BAI experiments under fixed sampling budgets averaged over 20,000 independent runs.Comparisons include UNIFORM, UCB-E, UGAPE, SUCCESSIVE HALVING, SUCCESSIVE REJECTS, and CONTINUOUS REJECTS.
  • Ablations and Sensitivity: Combining influence weights and empirical variance consistently outperforms using either component alone, while performance near the best τ remains stable across a broad range of ¯σ.The variance floor mainly stabilizes early estimates, and the method is more sensitive to τ than to ¯σ.
  • Monte Carlo Tree Search: VARDE–MCTS achieves the highest Monte Carlo value estimates in stochastic grid worlds and the lowest root value estimation error on synthetic trees.The strongest results occur in FROZENLAKE, SAILING, and the synthetic-tree benchmark across tested planning conditions.
  • Q-Learning: VARDE–Q-LEARNING stays near-optimal across tested RIVERSWIM and FORKEDRIVERSWIM state sizes, with tight confidence intervals as environments scale.Existing baselines deteriorate rapidly on RIVERSWIM and exhibit large run-to-run variability when learning from rare, noisy returns.

6. Discussion and Future Work … A.6. Proof of Theorem 3.7 (Variance Decay of VarDE)

The discussion presents VarDE as decision-variance minimization for stochastic pure exploration, while the appendix establishes its allocation, variance-decomposition, decrement, and O(T^-1) variance-decay guarantees. It also identifies approximation limitations and directions for extending the methodology.

  • 6. Discussion and Future Work: VarDE allocates samples to components that are both influential to the final recommendation and empirically noisy, benefiting highly stochastic and heteroscedastic settings.The discussion contrasts this principle with optimism and entropy heuristics that may react to noise rather than decision-relevant uncertainty.
  • 6. Discussion and Future Work: The first-order variance approximation is most accurate after concentration, while unstable early estimates, surrogate temperature, trajectory coupling, and bootstrapping limit the current analysis.These issues create a bias–smoothness trade-off and mean diagonal variance only approximately captures dependencies in reinforcement learning and planning.
  • 6. Discussion and Future Work: Future work includes full-covariance uncertainty, adaptive temperature schedules, Hessian- and moment-based allocation, non-asymptotic variance-driven RL theory, and scalable influence estimation.The proposed extensions target correlated uncertainty, bias–variance balancing, higher-order information, finite-sample guarantees, and function approximation.
  • Appendix: The appendix supplies additional proofs, complete algorithm pseudocodes, and experimental details, using the main text’s notation unless stated otherwise.This establishes the appendix as supporting material for the paper’s theoretical and empirical claims.
  • A. Proofs for Section 3 (VarDE Methodology); A.1. Proof of Lemma 3.2 (Local Linear Approximation): Taylor expansion with bounded Hessian control yields the local linear approximation underlying VarDE’s surrogate decision function.The proof uses a remainder bound involving the operator norm of the Hessian and the squared estimation error.
  • A.2. Auxiliary min-pulls guarantee: Every component receives linear-in-time sampling, with Ni(t) = Ω(t), and fixed-order inverse-count sums satisfy the corresponding asymptotic bounds.The min-pulls guarantee depends on bounded observations, the variance floor, and Assumption 3.3.
  • A.3. Proof of Lemma 3.4 (First-Order Variance Decomposition): The first-order variance decomposition separates the independent leading term from a quadratic curvature remainder, with the latter contributing O(t^-2).The proof uses Taylor expansion, bounded Hessian conditions, bounded fourth moments, independence, and covariance bounds.

A.7. First-order allocation constant … B.4. Proof of Lemma 4.4 (LSE nonvanishing influence weights)

The section shows that well-spread allocations share the same T^-1 variance-decay exponent, so VarDE’s asymptotic benefit comes from minimizing the leading decision-level variance constant. It also records proof steps for the LSE properties used in the VarDE–BAI analysis, including curvature, Hessian Lipschitzness, and nonvanishing influence weights.

  • A.7. First-order allocation constant: All allocations with nonzero limiting proportions have the same T^-1 exponent, making the leading constant C(p) the meaningful asymptotic comparison.
  • A.7. First-order allocation constant: The optimal first-order allocation satisfies p_i ∝ |w_i(µ)|σ_i.
  • A.7. First-order allocation constant: The optimal constant obeys C⋆≤C_unif, with equality only when |w_i(µ)|σ_i is constant across i.
  • A.7. First-order allocation constant: VarDE’s greedy marginal-decrement allocation targets the optimal first-order proportion p⋆ and improves the first-order constant rather than the variance-decay exponent.
  • B.1. Proof of Lemma 4.1 (LSE bound): The LSE bound proof establishes its claim through a lower-bound argument beginning from P_K.
  • B.2. Proof of Lemma 4.2 (LSE curvature): The LSE curvature proof differentiates the expression twice and uses bounds involving (max_i v_i)^2+(min_i v_i)^2.
  • B.3. Proof of Lemma 4.3 (LSE Hessian Lipschitzness): The Hessian Lipschitzness proof bounds softmax derivatives uniformly and concludes with L_τ,K = 3K^3/2/τ^2.
  • B.4. Proof of Lemma 4.4 (LSE nonvanishing influence weights): For x∈D=[a,b]^K, the proof lower-bounds softmax coordinates using x_i≥a and x_j≤b, while the upper bound w_i(x)≤1 is immediate.

B.5. Proof of Theorem 4.5 (VARDE–BAI error probability) … C.3. Concentration of empirical transitions

The proofs establish concentration and sampling guarantees for VARDE–BAI and extend them to VARDE–MCTS through node-wise reduction, reward concentration, and transition concentration. Together, these arguments control empirical variance, ensure minimum sampling, and bound estimation errors under adaptive visitation.

  • B.5. Proof of Theorem 4.5 (VARDE–BAI error probability): Hoeffding’s inequality controls deviations of squared centered rewards and empirical means, while a union bound combines the resulting bounds for empirical variance confidence.The proof uses Xi ∈ [a, b], so (Xi − µ)^2 lies in [0, (b − a)^2].
  • B.5. Proof of Theorem 4.5 (VARDE–BAI error probability): After T > K pulls, VARDE–BAI’s temperature-based selection rule guarantees a lower bound on every arm’s number of pulls.The argument analyzes the most frequently selected arm and uses rewards supported on [0, 1].
  • B.5. Proof of Theorem 4.5 (VARDE–BAI error probability): Theorem 4.5 derives VARDE–BAI’s error probability by applying Hoeffding’s inequality to empirical gaps and taking a union bound over suboptimal arms.The empirical gap is between the best arm i∗ and each arm i ≠ i∗, with expected gap ∆i.
  • C. Proofs for Subsection 4.2 (VARDE–MCTS): VARDE–MCTS operates with bounded returns in [0, H] and estimates action values, variances, and visit counts at each state-action node.The successor set S(s, a) is finite, and Q∗(s, a) denotes the true action-value.
  • C.1. Reduction to VARDE–BAI at each node: At each node, VARDE–MCTS is exactly VARDE–BAI applied to actions as arms, yielding a corresponding minimum-pulls guarantee for every action.The node-wise bandit identifies empirical means with action-value estimates and uses empirical variances and counts.
  • C.2. Concentration of empirical reward mean: Empirical reward means concentrate conditionally on N(s, a) through Hoeffding’s inequality because rewards are independently sampled from ν(·|s, a).The lemma compares the empirical reward mean ˆr(s, a) with the true expected reward r(s, a).
  • C.3. Concentration of empirical transitions: Conditional on N(s, a), observed successor states are i.i.d. from P(· | s, a), enabling DKW-based concentration of empirical transition probabilities.The proof converts empirical and true CDF errors into mass-function errors and substitutes n = N(s, a).

C.4. Induction through the search tree · D. Proofs for Subsection 4.3 (VARDE–Q-LEARNING)

This section proves that VARDE–MCTS value-estimate concentration propagates backward through the search tree to the root, yielding exponentially decreasing root error probability under a unique optimum.

  • C.4. Induction through the search tree: Lemma C.5 propagates successor-state concentration to state–action estimates by combining component bounds with a union bound.The argument fixes auxiliary tolerances and combines upper and lower bounds to obtain constants for the desired tolerance.
  • C.4. Induction through the search tree: Lemma C.6 lifts action-level concentration to node-level concentration by applying Lemma C.5 to each action and converting N(st, a)-rates into N(st)-rates.A union bound over actions completes the induction step at a fixed depth.
  • C.4. Induction through the search tree: Theorem C.7 establishes conditional concentration bounds for VARDE–MCTS value estimates at every node and depth, including the root after T simulations.The proof uses the zero terminal value as the base case and backward induction through Lemma C.6.
  • C.4. Induction through the search tree: At the root, Theorem C.7 substitutes N(s0) = T after T simulations to obtain the corresponding root estimate bound.The root statement follows directly from the node-wise conditional result.
  • C.4. Induction through the search tree: Corollary C.8 shows that, when the optimal root action is unique, the action recommended by VARDE–MCTS has an exponentially decreasing root error probability.The proof transfers value-estimate concentration to root action–value estimates and uses the optimality gap to identify the best action.
  • C.4. Induction through the search tree: The root recommendation proof combines concentration across root actions with a finite-action union bound, absorbing the number of actions into the constants.On the concentration event, every suboptimal action is ruled out and the recommended action equals the unique optimum.

D.1. Proof of Lemma 4.10 (Coverage) … E.3. VARDE–Q-LEARNING

The coverage proof shows that VARDE–Q-LEARNING samples every reachable state–action pair infinitely often, while the full algorithms instantiate VarDE for BAI, MCTS, and Q-learning. These procedures combine variance-aware allocation, online variance estimation, and problem-specific updates or recommendations.

  • D.1. Proof of Lemma 4.10 (Coverage): VARDE–Q-LEARNING’s per-state action rule is exactly VARDE–BAI on normalized Q-values, with warm-start η = 1 and temperature τ′ = τ/Hγ.The Q-values remain in [0, Hγ], where Hγ = 1/(1−γ), enabling the normalization.
  • D.1. Proof of Lemma 4.10 (Coverage): If a state is visited infinitely often, every action at that state is also sampled infinitely often.The result follows by applying the per-state VARDE–BAI guarantee once the state visit count exceeds its action count.
  • D.1. Proof of Lemma 4.10 (Coverage): All states are visited infinitely often almost surely because infinitely sampled actions propagate visits through every positive-probability transition, and the reachability assumption connects the state space.Thus R = S almost surely, and combining state coverage with per-state action coverage yields NT(s,a) → ∞ for every pair.
  • E. Full Algorithms: The full algorithm suite applies VarDE to BAI, MCTS, and Q-learning using temperature, warm-start or variance-floor parameters, finite budgets, and online statistics.The implementations initialize counts, estimates, and variance-related quantities before executing their respective sampling loops.
  • E.1. VARDE–BAI: VARDE–BAI warm-starts by pulling each arm cyclically, then updates arm statistics with Welford’s method and returns the arm with the largest estimated mean.The initialization lasts Kη rounds before variance-driven selection begins.
  • E.2. VARDE–MCTS: VARDE–MCTS expands unsampled actions, simulates to depth H, backpropagates discounted returns, updates variances with Welford’s method, and recommends arg maxa Q̂(s0,a).Each simulation transitions through the environment while maintaining state–action counts and path information.
  • E.3. VARDE–Q-LEARNING: VARDE–Q-LEARNING initializes Q(s,a) at Hγ, estimates target variance with Welford’s method, and updates Q using a count-dependent convex-combination step.The target is y = r̂ + γ maxb Q(s′,b), with α = (Hγ + 1)/(Hγ + N(s,a)).

E.4. Implementation details · F. Experimental Details

The implementation ensures every action is sampled before variance-based exploitation, using an infinite score for untried actions and defining MCTS expandability through unvisited actions. Empirical means and variances are updated online with Welford’s method.

  • E.4. Implementation details: The VarDE score is set to +∞ when N(s, a) = 0.This handles division by zero for untried state-action pairs.
  • E.4. Implementation details: This score rule ensures all actions are tried at least once before exploitation begins.Variance estimates are used only after initial action sampling.
  • E.4. Implementation details: In MCTS, an expandable node is a state node with at least one action satisfying N(s, a) = 0.Expandability is therefore determined by the existence of an unvisited action.
  • E.4. Implementation details: Empirical means and variances are updated online using the Welford method.The update procedure is provided in Algorithm 4.
  • E.4. Implementation details: The Welford update takes a count N ≥0, mean ˆµ, variance ˆσ2, and new sample x as inputs.It initializes the second-moment accumulator with M2 ←N ˆσ2.
  • E.4. Implementation details: The update computes δ2 ←x −ˆµ and updates the mean with ˆµ ←ˆµ + δ/N.It then updates M2 using M2 ←M2 + δ δ2.

F.1. BAI Experiments

The VARDE–BAI evaluation uses four standard BAI benchmarks spanning Bernoulli and Gaussian arms, varying arm-group structures, and budgets from T = 150 to T = 1200. Two additional Gaussian experiments compare VARDE–BAI under different decision functions.

  • F.1. BAI Experiments: The four standard benchmarks include one-group and two-group Bernoulli settings with 20 arms and budgets T = 1200 and T = 1000.BAI.1 uses µ0 = 0.2 and µ1:19 = 0.1; BAI.2 uses µ0 = 0.2, µ1:5 = 0.12, and µ6:19 = 0.08.
  • F.1. BAI Experiments: The remaining standard benchmarks use Gaussian arms: a 14-arm geometric progression with T = 200 and a 10-arm, three-group configuration with T = 150.In both experiments, σi is shuffled from µi.
  • F.1. BAI Experiments: The section also reports error-probability evolution over time for Experiments BAI.1 to BAI.4, complementing the last-pull results in Table 2.Figure 5 presents the error probability over time for Experiments BAI.1 to BAI.4.
  • F.1. BAI Experiments: Additional comparisons evaluate VARDE–BAI with different decision functions on a 15-arm arithmetic progression and a 20-arm setting with two good arms, both using T = 2000.Both additional experiments use Gaussian distributions, and σi is shuffled from µi.

F.1.1. COMPONENT ABLATIONS AND PARAMETER SENSITIVITY … F.3. BPI Experiments

The analyses show that VarDE–BAI benefits from combining influence weights with empirical variance, is more sensitive to temperature than variance floors, and requires care with first-order variance approximations. The MCTS and BPI experiments evaluate VarDE across stochastic environments using specified protocols, horizons, and tuned or fixed configurations.

  • F.1.1. COMPONENT ABLATIONS AND PARAMETER SENSITIVITY: Both influence weights and empirical variance are useful in VARDE–BAI, with the full influence-weighted variance rule performing best at every checkpoint.VAR-ONLY removes influence weights, while WEIGHT-ONLY removes empirical variance.
  • F.1.1. COMPONENT ABLATIONS AND PARAMETER SENSITIVITY: VARDE–BAI is more sensitive to temperature τ than to the variance floor, while performance near the best temperature remains stable across many floors.The variance floor mainly stabilizes early variance estimates.
  • F.1.2. FIRST-ORDER APPROXIMATION STUDY: For τ = 0.05, the first-order surrogate significantly underestimates full variance; for τ = 0.10 and τ = 0.15, the discrepancy narrows during learning.At τ = 0.15, the discrepancy is moderate early and quickly becomes very small.
  • F.2.1. EXPERIMENT MCTS.1 - SAILING ENVIRONMENTS: In the sailing environment, hyperparameters are selected by grid search, with VARDE using temperature = 1.5 and variance floor = 100.The selection uses 50 runs, 10000 MCTS simulations per run, and 200 evaluation rollouts.
  • F.2.3. EXPERIMENT MCTS.3 - FROZENLAKE: FrozenLake uses slippery actions with success probability p = 0.8, sparse discounted rewards with γ = 0.95, and VARDE temperature = 0.015 with variance floor = 0.01.Episodes terminate at the goal, a hole, or horizon H = 10.
Loading 2608.21995v1…