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.
Figures & tables
Arm
Distribution
true μi
true σi
n sample
empirical μ^i
1
Pr(X=2.0)=0.3, Pr(X=0.0)=0.7
0.60
0.92
40
0.42
2
Pr(X=0.58)=0.5, Pr(X=0.60)=0.5
0.59
0.01
40
0.59
3
Pr(X=0.55)=0.5, Pr(X=0.57)=0.5
0.56
0.01
40
0.56
Table 1: A stylized heteroscedastic BAI snapshot. Arm 1 is optimal in expectation but has larger variance. Empirical ranking can favor the stable suboptimal arms, while decision-relevant uncertainty remains concentrated in Arm 1.
Figure 1: Error probability over time of VarDE–BAI with different smooth decision functions (Appendix F.1 gives function definitions and hyperparameters).
Setting
BAI.1
BAI.2
BAI.3
BAI.4
No. of Pulls
1200
1000
200
150
Uniform
33.23
38.69
28.53
32.98
SH
29.05
29.08
15.75
19.56
SR
16.06
20.70
12.39
15.41
CR-A
17.00
21.07
9.83
11.93
CR-C
16.71
20.84
11.80
12.71
Table 2: Final error probability (in %) for Best-Arm Identification under four benchmark settings.
Figure 2: Monte Carlo value estimates of the recommended root action/policy during planning (mean ± 95% CI over runs).
Figure 4: Normalized value proximity of VarDE–Q-learning against model-free and model-based methods after a fixed interaction budget T on RiverSwim and ForkedRiverSwim (mean ± 95% CI).
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Error probability over time for Experiments BAI.1 to BAI.4.
Method
500
1000
1500
2000
Var-Only
36.40
24.83
18.22
13.09
Weight-Only
19.29
9.37
6.40
5.07
VarDE
13.58
5.21
2.69
1.84
Appendix
Table 3: Component ablation for VarDE–BAI : error probability (%) over time.
τ / σˉ2
10−4
10−3
10−2
10−1
1
0.01
43.75
43.88
44.86
49.08
49.43
0.03
13.55
13.22
13.57
14.78
14.94
0.05
6.22
5.71
5.33
5.68
5.69
0.10
6.27
6.18
6.07
6.14
6.32
0.20
13.15
12.88
12.87
11.28
10.93
0.50
19.72
19.00
19.32
17.08
16.86
Appendix
Table 4: Sensitivity of VarDE–BAI : error probability (%) across temperature τ and variance floor σˉ2 .
Step
Vfull
V1st
Vfull−V1st
VfullVfull−V1st
20
1.227×10−2
3.838×10−3
8.510×10−3
66.4%
400
3.659×10−3
2.530×10−4
3.406×10−3
88.7%
600
2.790×10−3
1.687×10−4
2.622×10−3
88.0%
900
1.916×10−3
1.027×10−4
1.813×10−3
84.9%
Appendix
Table 5: First-order approximation study for τ=0.05 .
Step
Vfull
V1st
Vfull−V1st
VfullVfull−V1st
20
7.112×10−3
2.911×10−3
4.201×10−3
56.1%
400
3.609×10−4
2.398×10−4
1.211×10−4
21.6%
600
2.157×10−4
1.621×10−4
5.369×10−5
14.4%
900
1.198×10−4
1.003×10−4
1.963×10−5
8.4%
Appendix
Table 6: First-order approximation study for τ=0.10 .
Step
Vfull
V1st
Vfull−V1st
VfullVfull−V1st
20
4.644×10−3
2.712×10−3
1.933×10−3
39.5%
400
2.540×10−4
2.390×10−4
1.534×10−5
5.3%
600
1.682×10−4
1.617×10−4
7.276×10−6
3.8%
900
1.026×10−4
1.003×10−4
3.339×10−6
3.0%
Appendix
Table 7: First-order approximation study for τ=0.15 .
Figure 6: Sailing environment wind directions, applicable actions, and rewards under blue-direction wind.