Paper deep dive
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
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/25/2026, 7:52:12 AM
Summary
The paper introduces Variance Driven Exploration (VarDE), a methodology for pure exploration in highly stochastic environments. VarDE allocates sampling effort to minimize the uncertainty of the final decision by using a smooth decision function and first-order sensitivity analysis to derive influence-weighted allocation rules. It is applied to Best Arm Identification (BAI), Monte Carlo Tree Search (MCTS), and Best-Policy Identification (BPI), providing theoretical guarantees on variance decay and simple regret, and demonstrating empirical improvements over existing methods.
Entities (7)
Relation Signals (5)
VarDE → appliesto → Best Arm Identification
confidence 95% · We apply this methodology to three core problems of pure exploration -- Best Arm Identification (BAI)
VarDE → appliesto → Monte Carlo Tree Search
confidence 95% · We apply this methodology to three core problems of pure exploration ... Monte Carlo Tree Search (MCTS)
VarDE → appliesto → Best-Policy Identification
confidence 95% · We apply this methodology to three core problems of pure exploration ... Best-Policy Identification (BPI)
Khang Luong → affiliatedwith → Hanoi University of Science and Technology
confidence 90% · Khang Luong Affiliation: Hanoi University of Science and Technology
VarDE → uses → LogSumExp
confidence 90% · Instead of the non-differentiable max... we adopt LogSumExp (LSE) as a smooth approximation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.21995v1
- Canonical: https://arxiv.org/abs/2608.21995v1
Trouble viewing inline? Open PDF directly →
Full Text
125,467 characters extracted from source content.
Expand or collapse full text
Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments Khang Luong Affiliation: Hanoi University of Science and Technology, Hanoi, Vietnam Nam Nguyen Affiliation: Hanoi University of Science and Technology, Hanoi, Vietnam Hoang Ta Affiliation: Hanoi University of Science and Technology, Hanoi, Vietnam Hung The Tran Affiliation: Quantum AI & Cyber Security Institute, FPT Corporation, Vietnam Tuan Dam Affiliation: Hanoi University of Science and Technology, Hanoi, Vietnam Correspondence to: tuandq@soict.hust.edu.vn Abstract 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. Keywords: Pure Exploration, Best-Arm Identification, Monte Carlo Tree Search, Reinforcement Learning, Best-Policy Identification 1 Introduction Many learning and planning problems in Reinforcement Learning reduce to a common goal: making a reliable decision from noisy interactions. In pure exploration settings, the agent is not judged by its performance during data collection but only by the final output—e.g., selecting the best arm in bandits, choosing the best root action in planning, or returning a near-optimal policy in reinforcement learning. Consequently, the central challenge is not balancing exploration and exploitation for cumulative reward but allocating samples to minimize uncertainty in the final decision. A large class of successful algorithms typically allocates samples using optimistic bounds. In bandits, fixed-budget best-arm identification methods allocate pulls via confidence bounds or elimination rules (Audibert et al. 2010; Gabillon et al. 2012; Wang et al. 2023). In planning, UCT-style Monte Carlo Tree Search (Kocsis & Szepesvári 2006; Browne et al. 2012) uses optimism to prioritize promising actions. In episodic reinforcement learning, best-policy identification methods often rely on optimistic value estimates and confidence sets to guide exploration (Ménard et al. 2021). While these approaches are powerful, they share a structural limitation: they primarily regulate local estimation error of each stochastic component without explicitly quantifying how uncertainty in each component propagates to the final returned decision. In highly stochastic environments, optimism-based rules may be dominated by stochastic fluctuations and mistake noise for evidence, overlooking the true signal. Under heteroscedastic variance, a sample is not equally informative across components: high-variance components may remain poorly estimated even after many pulls, while low-variance components quickly appear reliable. Table 1 gives a stylized three-arm snapshot that illustrates this failure mode. Arm 1 is the true best arm but is much noisier; after a number of pulls, its empirical mean can temporarily look worse than those of the two stable suboptimal arms. Empirical ranking may stop treating Arm 1 as competitive, even with a confidence bonus: μ^1+1n1=0.42+140<0.58<μ^2 μ_1+ 1 n_1=0.42+ 1 40<0.58< μ_2, and thus stop sampling from it. The decision-relevant uncertainty, however, is concentrated in Arm 1, because additional samples from this arm are most likely to change the final recommendation. More generally, pure exploration decisions (e.g., an argmax arm, a root action, or a greedy policy) are nonlinear functions of many estimates, so regulating local errors or bonuses does not necessarily reduce uncertainty of the final returned decision; this mismatch is amplified in planning and RL, where uncertainty propagates through value backups and can dominate the root choice. An effective pure exploration strategy should therefore ask a more direct question: Which component, if sampled next, most reduces uncertainty in the final decision we will output? We propose Variance Driven Exploration (VarDE), a general methodology that addresses this question by directly targeting decision-level uncertainty. VarDE formalizes the final decision as a (smooth) decision function of local empirical estimates, and uses a first-order sensitivity analysis to quantify each component’s influence on the output. This yields a simple allocation principle: sample where the (first-order) expected decrement in decision variance is largest. The resulting rule is explicit, modular, and naturally balances two factors: (i) how strongly the final decision depends on a component (an influence weight), and (i) how noisy that component is (its empirical variance). We instantiate VarDE in three canonical pure exploration settings: Best-Arm Identification (BAI), Monte Carlo Tree Search (MCTS), and Best-Policy Identification (BPI). Across these settings, VarDE provides a unified lens on exploration: rather than focusing on local confidence bounds, it allocates effort to directly reduce uncertainty in the returned decision. 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. Arm Distribution true μi _i true σi _i n sample empirical μ^i μ_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 Contributions. Our main contributions are: • From decision-level variance analysis to a generic, implementable allocation rule. In section 3, we introduce VarDE, a general methodology that treats the final recommendation as a smooth decision function of local empirical estimates, and derives an explicit influence-weighted decomposition of decision uncertainty (Lemma 3.4). From the variance decrement analysis (Proposition 3.6), we obtain a simple greedy rule that selects the component maximizing the expected reduction in the decision variance, combining influence weights with empirical variances. • Instantiations across bandits, planning, and RL. In section 4, we derive concrete algorithms VarDE–BAI, VarDE–MCTS, and VarDE–Q-learning, showing how influence weights and variance estimates can be computed in each setting. • Theory in stochastic regimes. We provide a first-order constant characterization and a decision-variance decay guarantee (Theorem 3.7), together with correctness guarantees for the final recommendation: the misidentification probability decays exponentially in BAI (Theorem 4.5) and MCTS (Corollary 4.8), and VarDE–Q-learning converges to an optimal policy with probability 1 (Theorem 4.11). • Empirical validation in stochastic environments. Section 5 demonstrates consistent empirical improvements over strong baselines across bandits, planning, and RL benchmarks, with the largest gains in highly stochastic environments. 2 Related Work Best-arm identification (BAI). Fixed-budget BAI methods can be broadly grouped by how they control uncertainty. A first family allocates pulls using confidence intervals (CI)-derived indices: classic examples include UCB-E (Audibert et al. 2010) and more refined gap-based rules such as UGapE (Gabillon et al. 2012), which use optimistic estimates to prioritize arms that are plausibly optimal. A second family follows a successive reject / elimination principle, progressively discarding arms and focusing the remaining budget on a shrinking candidate set; this includes Successive Halving (Karnin et al. 2013) and Successive Rejects (Audibert et al. 2010). More recently, Continuous Rejects (Wang et al. 2023) refines this reject-based view via continuous-time/large-deviation-inspired allocation. While both CI-based and reject-based designs are effective, they are largely driven by mean-based evidence (gaps, confidence radii, or reject schedules). They do not explicitly model or optimize how heteroscedastic reward variance influences the reliability of the final decision. In contrast, VarDE–BAI is explicitly variance-aware: it selects the next arm by maximizing a decision-variance decrement of the form (influence)×(variance), prioritizing samples that most reduce uncertainty in the final recommendation. Monte Carlo Tree Search (MCTS). A standard approach to exploration in tree search is UCT (Kocsis & Szepesvári 2006), which extends bandit optimism to internal nodes via UCB-style bonuses to balance exploitation of high-value actions and exploration of uncertain ones. In highly stochastic domains, several alternatives encourage broader search by injecting randomness or regularization into action selection, such as maximum-entropy planning (MENTS) (Xiao et al. 2019), convex-regularized variants (RENTS/TENTS/DENTS) (Dam et al. 2021; Dam et al. 2025a), and Boltzmann exploration in trees (BTS) (Painter et al. 2023). A complementary line of work by Dam and coauthors replaces conventional mean backups with generalized power-mean operators in Power-UCT, subsequently extending this framework to stochastic and continuous-action tree search with finite-time guarantees (Dam et al. 2020; Dam et al. 2024; Dam 2025). They also develop uncertainty-aware and robust Monte-Carlo planning through optimal-transport propagation and robustness to model ambiguity (Dam et al. 2025c; Dam et al. 2025b). These methods diversify exploration through optimism or entropy mechanisms, but they do not explicitly optimize how uncertainty along different edges influence the action recommendation. VarDE–MCTS differs by explicitly weighting edges by both their influence on the action decision and their empirical return variance. Best-policy identification (BPI) in RL. Pure-exploration RL (and BPI in particular) has been studied from minimax and adaptive perspectives, with algorithms that provide strong finite-sample guarantees by explicitly reasoning over model uncertainty (Ménard et al. 2021; Domingues et al. 2021; Marjani & Proutiere 2021). Many of the best-theory approaches are model-based: they maintain confidence sets for rewards/transitions and repeatedly solve (optimistic) planning problems to decide where to sample next (Azar et al. 2017; Al Marjani et al. 2021). While statistically powerful, these methods are often implementation-heavy and computationally demanding due to repeated dynamic programming / optimistic MDP solving and the need to manipulate confidence sets over (r,P)(r,P), which can scale poorly with |||S| and |||A| (Ménard et al. 2021; Al Marjani et al. 2021). In contrast, model-free baselines such as Q-learning (and ε -greedy variants), Q-UCB (Jin et al. 2018), PSRL (Osband et al. 2013), and recent fixed-budget model-free BPI methods (Russo & Proutiere 2023) are comparatively simple and scalable, but can be brittle in highly stochastic environments where naive exploration is inefficient. VarDE is complementary: it provides a lightweight, plug-in sampling rule that targets uncertainty of the final greedy decision via a smooth surrogate and an empirical variance signal (TD-target variance), yielding a practical decision-aware alternative without requiring full model construction or repeated optimistic planning. 3 Variance Driven Exploration 3.1 Preliminaries and evaluation Throughout this paper, [n]=1,2,…,n[n]=\1,2,…,n\, ∥⋅∥2\|·\|_2 denotes the Euclidean norm, ∥⋅∥op\|·\|_op denotes the operator norm, and ∥⋅∥∞\|·\|_∞ denotes the ℓ∞ ^∞ norm: ‖x‖∞:=maxi|xi|\|x\|_∞:= _i|x_i|. We formalize the principle of VarDE as a general statistical methodology for decision-level uncertainty minimization. Let X1,…,XnX_1,…,X_n denote local stochastic components (arms, leaf values, or state–action returns), each with unknown mean μi _i and variance σi2<∞ _i^2<∞; for each component i∈[n]i∈[n], we can collect i.i.d. samples to form the empirical mean μ^i μ_i. Let Y=f(μ^1,…,μ^n)Y=f( μ_1,…, μ_n) denote a global scalar decision variable depending on the empirical means μ μ, such as the root value in a planning tree or a smooth surrogate of the best-arm decision in BAI. Our goal in this section is to derive a simple, unified sampling rule that greedily reduces the decision-level uncertainty Var[Y] [Y] by combining (i) how strongly each component influences Y and (i) how noisy that component is. Roadmap. To make this principle actionable, we first relate Var[Y] [Y] to the component-wise estimation errors of μ μ. Assumption 3.1 allows a Taylor linearization of f on the bounded empirical domain, which yields influence weights wi(μ)w_i(μ). We then decompose Var[Y] [Y] into an influence-weighted sum of local variances and derive a one-sample decision-variance decrement, leading to the greedy VarDE sampling rule. Proofs are deferred to Appendix A. Assumption 3.1 (VarDE regularity conditions). Assume observations for every component lie in a common bounded interval [a,b][a,b]; hence μ and every empirical vector μ^(t) μ(t) lie in the compact convex domain D:=[a,b]nD:=[a,b]^n. Assume the decision function f:ℝn→ℝf:R^n is twice continuously differentiable on an open convex set containing D, and that its Hessian is uniformly bounded and Lipschitz on D: there exist constants M,L<∞M,L<∞ such that, for all x,y∈Dx,y∈ D, ‖Hf(x)‖op≤M,‖Hf(x)−Hf(y)‖op≤L‖x−y‖2.\|H_f(x)\|_op≤ M, \|H_f(x)-H_f(y)\|_op≤ L\|x-y\|_2. 3.2 Influence Weights Lemma 3.2 (Local linear approximation). Under Assumption 3.1, for any μ^∈D=[a,b]n μ∈ D=[a,b]^n, f(μ^)=f(μ)+∇f(μ)⊤(μ^−μ)+(M∥μ^−μ∥22).f( μ)=f(μ)+∇ f(μ) ( μ-μ)+O\! (M\| μ-μ\|_2^2 ). Neglecting the quadratic remainder in Lemma 3.2 yields the first-order approximation Y=f(μ^)≈c+∑i=1nwi(μ)μ^i,Y=f( μ)≈ c+ _i=1^nw_i(μ)\, μ_i, where w(μ):=∇f(μ)w(μ):=∇ f(μ), and c=f(μ)−w(μ)⊤μc=f(μ)-w(μ) \,μ. We call wi(μ)w_i(μ) the influence weights, as they quantify how sensitive the global decision variable Y=f(μ^)Y=f( μ) is to small perturbations in the local estimate μ^i μ_i. We use the following nondegeneracy assumption. Assumption 3.3 (Nonvanishing influence weights). There exists ρ>0ρ>0 such that |wi(x)|≥ρ,∀x∈D,∀i∈[n].|w_i(x)|≥ρ, ∀ x∈ D,\;∀ i∈[n]. (3.1) 3.3 Variance Analysis Using influence weights, we can decompose the variance of the decision variable: Lemma 3.4 (First-order variance decomposition). Under Assumption 3.1, the variance floor, Assumption 3.3, and independence across components, let Yt=f(μ^(t))Y_t=f( μ(t)) denote the decision variable after t total samples, then Var[Yt]=∑i=1nwi(μ)2σi2Ni(t)+O(t−2). [Y_t]= _i=1^nw_i(μ)^2 _i^2N_i(t)+O(t^-2). Decision uncertainty Var[Yt] [Y_t] is not simply the sum of local estimation variances. Each local variance is scaled by the squared influence of that component on the final decision variable. Lemma 3.5 (One-Sample Variance Decrement). For each i∈[n]i∈[n], when one additional sample is collected for XiX_i, the change in its local variance is: ΔVar[μ^i]=−σi2Ni(Ni+1). [ μ_i]=- _i^2N_i(N_i+1). Combining the first-order variance decomposition with the local decrement yields the first-order global variance update of VarDE. Proposition 3.6 (Global variance decrement). Fix a step t in which the algorithm collects one additional sample from component it∈[n]i_t∈[n]. Under Assumption 3.1, the variance floor, Assumption 3.3, and independence across components, Var[Yt+1]−Var[Yt]=−wit(μ)2σit2Nit(t)(Nit(t)+1)+O(t−2). [Y_t+1]- [Y_t]=-\,w_i_t(μ)^2\, _i_t^2N_i_t(t)(N_i_t(t)+1)+O(t^-2). This equation expresses how a single new sample from component iti_t reduces the decision-level variance in proportion to its influence weight wit2w_i_t^2 and its local noise σit2 _i_t^2. 3.4 Optimal Sampling Rule Since each additional sample yields the marginal variance decrement above, the optimal greedy sampling rule is to select the component that maximizes the (first-order) variance reduction: i~∈argmaxi∈[n]wi(μ^)2σ~i2Ni(Ni+1), i∈ _i∈[n]\;w_i( μ)^2\, σ_i^2N_i(N_i+1), where σ~i2=max(σ^i2,σ¯2) σ_i^2= ( σ_i^2, σ^2) and σ¯2>0 σ^2>0 is the variance floor. This formulation highlights VarDE as a methodology that unifies stochastic decision processes–from flat bandits to hierarchical planners and value-based learners–under a single principle of minimizing decision-level uncertainty. With this sampling rule, we can establish the following decision-level variance decay guarantee. Theorem 3.7 (Variance decay of VarDE). Under Assumption 3.1, the variance floor, Assumption 3.3, and independence across components, VarDE satisfies Ni(t)=Ω(t)N_i(t)= (t) for every component and therefore Var[Yt]=(t−1). [Y_t]=O(t^-1). Remark 3.8 (First-order allocation constant). Theorem 3.7 gives the variance-decay exponent. The leading constant is the quantity that distinguishes well-spread allocations. Appendix A.7 shows that if Ni(T)=piT+O(1)N_i(T)=p_iT+O(1) with pi>0p_i>0 and ∑ipi=1 _ip_i=1, then Var[YT]=1TC(p)+O(T−2),C(p)=∑i=1nwi(μ)2σi2pi. [Y_T]= 1TC(p)+O(T^-2), C(p)= _i=1^n w_i(μ)^2 _i^2p_i. The unique minimizer of this first-order constant is pi⋆∝|wi(μ)|σip_i |w_i(μ)| _i, giving C⋆=(∑i|wi(μ)|σi)2C_ =( _i|w_i(μ)| _i)^2. Thus VarDE is not claiming a better exponent than all well-spread allocations; its asymptotic target is the optimal first-order constant induced by the decision-level variance decomposition. 4 Applications We now instantiate VarDE in three canonical pure-exploration settings–Best-Arm Identification (BAI), Monte Carlo Tree Search (MCTS), and Best-Policy Identification (BPI)–showing how a common decision-level uncertainty objective yields simple sampling rules and corresponding theoretical guarantees. All proofs are deferred to Appendices B, C, and D. 4.1 Best-Arm Identification Bandit 4.1.1 Problem Setting We consider K stochastic arms Xii=1K\X_i\_i=1^K with unknown means μi=[Xi] _i= [X_i] and finite variances σi2=Var[Xi] _i^2= [X_i]. At each round t, the learner selects an arm i~t i_t and observes a reward rt∼Xi~tr_t X_ i_t, with rt∈[0,1]r_t∈[0,1]. The objective is to identify the best arm i∗=argmaxi∈[K]μi^*= _i∈[K] _i. Accordingly, we seek to minimize the simple regret ℛT=[μi∗−μi^T],R_T= [ _i^*- _ i_T], where i^T i_T denotes the arm recommended after T samples. The decision value in BAI is the maximum empirical mean. Instead of the non-differentiable maxiμ^i _i μ_i, we adopt LogSumExpLogSumExp (LSE) as a smooth approximation: Yτ=LSEτ(μ^)=τlog∑i=1Keμ^i/τ,Y_τ=LSE_τ( μ)=τ _i=1^Ke μ_i/τ, where τ>0τ>0 is a temperature parameter. To apply VarDE, we require a smooth surrogate of maxiμ^i _i μ_i with controlled curvature. The following lemmas show that LSEτLSE_τ (i) approximates max within τlogKτ K, (i) has a uniformly bounded Hessian, and (i) has Lipschitz Hessian on bounded domains, thereby verifying the smoothness requirements of Assumption 3.1 for the BAI decision surrogate. Lemma 4.1 (LSE bound). For any vector μ^∈ℝK μ ^K and any τ>0τ>0, maxiμ^i≤LSEτ(μ^)≤maxiμ^i+τlogK. _i μ_i _τ( μ)≤ _i μ_i+τ K. Lemma 4.2 (LSE curvature). For any fixed τ>0τ>0 and any μ^∈ℝK μ ^K, the Hessian of LSEτLSE_τ satisfies ‖∇2LSEτ(μ^)‖op≤12τ. \|∇^2LSE_τ( μ) \|_op≤ 12τ. Lemma 4.3 (LSE Hessian Lipschitzness). For any fixed τ>0τ>0, ∇2LSEτ∇^2LSE_τ is Lipschitz on any compact convex domain D⊂ℝKD ^K. More explicitly, there exists Lτ,K<∞L_τ,K<∞ such that, for all x,y∈Dx,y∈ D, ‖∇2LSEτ(x)−∇2LSEτ(y)‖op≤Lτ,K‖x−y‖2. \|∇^2LSE_τ(x)-∇^2LSE_τ(y) \|_op≤ L_τ,K\|x-y\|_2. One may take Lτ,K=3K3/2/τ2L_τ,K=3K^3/2/τ^2. The temperature τ therefore controls a bias–smoothness tradeoff. By Lemma 4.1, smaller τ makes LSEτLSE_τ a tighter approximation to the hard maximum, with bias at most τlogKτ K. At the same time, Lemmas 4.2 and 4.3 show that the curvature and Hessian-Lipschitz constants scale as O(τ−1)O(τ^-1) and O(τ−2)O(τ^-2), respectively. Thus very small τ gives a more faithful decision surrogate but amplifies the higher-order Taylor remainder in the variance approximation, whereas larger τ smooths the decision variable and stabilizes the first-order variance surrogate at the cost of additional approximation bias. 4.1.2 VarDE–BAI Algorithm We now instantiate VarDE in the fixed-budget best-arm identification setting. With the smooth decision variable Yτ=LSEτ(μ^)Y_τ=LSE_τ( μ), VarDE reduces to allocating pulls across arms to greedily decrease the decision-level variance Var[Yτ] [Y_τ]. Under the LSEτLSE_τ decision variable, the influence weight of each arm is wi(μ^)=∂Yτ∂μ^i=eμ^i/τ∑j=1Keμ^j/τ.w_i( μ)= ∂ Y_τ∂ μ_i= e μ_i/τ _j=1^Ke μ_j/τ. Lemma 4.4 (LSE nonvanishing influence weights). Fix τ>0τ>0 and a compact box D=[a,b]KD=[a,b]^K. For every x∈Dx∈ D and every i∈1,…,Ki∈\1,…,K\, 1Ke(a−b)/τ≤wi(x)≤1. 1Ke^(a-b)/τ≤ w_i(x)≤ 1. In particular, the LSE influence weights verify Assumption 3.3 on D with ρ=K−1e(a−b)/τ>0ρ=K^-1e^(a-b)/τ>0. VarDE–BAI greedily selects the arm that can contribute the largest expected variance decrement, applying the optimal sampling rule in Subsection 3.4 and updating μ^,σ^2,N μ, σ^2,N online. The complete algorithm is deferred to Appendix E (Algorithm 1). 4.1.3 Theoretical Guarantees We next state finite-sample guarantees for VarDE–BAI in the fixed-budget setting. Under standard bounded-reward assumptions and a unique best arm, we show that VarDE–BAI identifies the optimal arm with exponentially small error probability, which in turn implies an exponential decay of the simple regret. Theorem 4.5 (VarDE–BAI error probability). Assume rewards are supported on [0,1][0,1] and that the best arm i∗i^* is unique. VarDE–BAI (Alg. 1) with temperature τ>0τ>0 and warm start η>0η>0 satisfies Pri^T≠i∗≤Cexp(−cT), \ i_T≠ i^*\≤ C (-cT), for some constants C,c>0C,c>0 that may depend on K, τ, σ¯ σ, and the gaps Δi=μi∗−μi _i= _i^*- _i. Corollary 4.6 (VarDE–BAI simple regret). Under the assumptions of Theorem 4.5, the simple regret of VarDE–BAI satisfies ℛT≤ΔmaxPri^T≠i∗=exp(−Ω(T)),R_T\ ≤\ _ \, \ i_T≠ i^*\\ = (- (T)), where Δmax:=maxi≠i∗(μi∗−μi) _ := _i≠ i^*( _i^*- _i). This exponential decay of the simple regret is order-optimal and matches the minimax lower bound in fixed-budget BAI up to constant factors (Audibert et al. 2010). Other Decision Functions. While we focus on the LSEτLSE_τ decision function for simplicity, VarDE can be adapted to other smooth approximations of the maximum function with analogous guarantees under similar regularity conditions. 4.2 Monte Carlo Tree Search 4.2.1 Problem Setting We plan in an episodic Markov Decision Process (MDP) with horizon H, discount factor γ∈(0,1]γ∈(0,1], finite state set S and action set A. We assume access to a forward model that can simulate transitions and rewards along a trajectory. Given a state s and action a∈(s)a (s) (the set of feasible actions at s), a call to the model returns a next state s′∼P(⋅∣s,a)s P(· s,a) and a reward sample r^∼ν(⋅∣s,a) r ν(· s,a) supported on [0,1][0,1], with mean r(s,a)r(s,a); the next call proceeds from s′s . The optimal action-value function is Q∗(s,a)=supπ[∑t=0H−1γtr(st,at)|s0=s,a0=a],Q^*(s,a)= _π ^π\! [ _t=0^H-1γ^t\,r(s_t,a_t)\, |\,s_0=s,\,a_0=a ], where the supremum is over deterministic policies π, and the expectation is over trajectories s0,a0,s1,…,sHs_0,a_0,s_1,…,s_H with at=π(st)a_t=π(s_t) and st+1∼P(⋅∣st,at)s_t+1 P(· s_t,a_t). Our objective is to identify the best root action a∗=argmaxa∈(s0)Q∗(s0,a)a^*= _a (s_0)Q^*(s_0,a) using T simulated trajectories. Accordingly, we minimize the simple regret ℛT=[Q∗(s0,a∗)−Q∗(s0,a^T)],R_T= \! [Q^*(s_0,a^*)-Q^*(s_0, a_T) ], where a^T a_T is the action recommended after T simulations. 4.2.2 VarDE–MCTS Algorithm To apply VarDE in MCTS, we view each state–action pair (s,a)(s,a) as a local stochastic component whose return is estimated by the empirical Q^(s,a) Q(s,a). The global decision at a state s is the recommended action a a, which depends on comparing action values through the maximization V∗(s)=maxa∈(s)Q∗(s,a)V^*(s)= _a (s)Q^*(s,a). Since max is non-differentiable, we replace it with a smooth surrogate so that influence weights and variance decrements can be defined in closed form. We therefore use a smooth surrogate of maxa∈(s)Q^(s,a) _a (s) Q(s,a) via LSEτLSE_τ: Yτ(s)=LSEτ(Q^(s,⋅))=τlog∑a∈(s)eQ^(s,a)/τ,Y_τ(s)=LSE_τ( Q(s,·))=τ _a (s)e Q(s,a)/τ, where Q^(s,a) Q(s,a) is the empirical value of action a at state s. The influence weight of action a at state s is w(s,a)=∂Yτ(s)∂Q^(s,a)=eQ^(s,a)/τ∑b∈(s)eQ^(s,b)/τ.w(s,a)= ∂ Y_τ(s)∂ Q(s,a)= e Q(s,a)/τ _b (s)e Q(s,b)/τ. The uncertainty of action a at state s is evaluated by the empirical variance σ^(s,a) σ(s,a) of cumulative returns G^(s,a) G(s,a) when taking a at s. G^(s,a):=∑t=0H−1γtr^(st,at), G(s,a)\;:=\; _t=0^H-1γ^t\, r(s_t,a_t), (s0,a0)=(s,a),st+1∼P(⋅∣st,at). (s_0,a_0)=(s,a),\ s_t+1 P(· s_t,a_t). During selection phase, VarDE–MCTS greedily chooses the action that yields the largest estimated (first-order) variance decrement, applying the optimal sampling rule in Subsection 3.4. The simulation phase and backpropagation phase follow standard MCTS procedures with max back-up. The complete algorithm is deferred to Appendix E (Algorithm 2). 4.2.3 Theoretical Guarantees We next provide concentration guarantees for VarDE–MCTS: value estimates concentrate exponentially fast in the number of simulations, which implies an exponentially small probability of recommending a suboptimal root action. Theorem 4.7 (VarDE–MCTS value estimates). Consider a VarDE–MCTS process. For any depth t∈0,…,Ht∈\0,…,H\, any node sts_t, and any fixed tolerance ε>0 >0, there exist constants Cst,ε>0C_s_t, >0 and kst,ε>0k_s_t, >0 such that, conditionally on N(st)=n≥1N(s_t)=n≥ 1, Pr(|V^(st)−V∗(st)|>ε)≤Cst,εexp(−kst,εε2n). \! ( | V(s_t)-V^*(s_t) |> )≤ C_s_t, \! (-k_s_t, \, ^2n ). Moreover, at the root node s0s_0, after T simulations, there exist constants Cε>0C_ >0 and kε>0k_ >0 such that Pr(|V^(s0)−V∗(s0)|>ε)≤Cεexp(−kεε2T). \! ( | V(s_0)-V^*(s_0) |> )≤ C_ \! (-k_ \, ^2T ). Corollary 4.8 (VarDE–MCTS error probability). Under the assumptions of Theorem 4.7, the error probability of VarDE–MCTS satisfies Pra^T≠a∗≤exp(−Ω(T)). \ a_T≠ a^*\≤ \! (- (T) ). This exponential decay of the error probability matches the standard exponential concentration rates established for Monte Carlo Tree Search in stochastic environments (Browne et al. 2012; Dam et al. 2021; Painter et al. 2023). 4.3 Best Policy Identification 4.3.1 Problem Setting We consider the non-episodic infinite-horizon case under the same MDP and forward model assumptions as in Section 4.2.1. When learning under the infinite-horizon MDP, we also need the following assumption. Assumption 4.9 (Communicating MDP). For any states s,s′∈s,s , there exists a stationary policy π such that the expected hitting time of s′s starting from s is finite: sπ[Ts′]<∞,Ts′:=inft≥0:st=s′.E^π_s\! [T_s ]<∞, T_s := \t≥ 0:s_t=s \. Given a sampling budget of T steps, the goal of best-policy identification (BPI) is to output a policy π π with small simple regret ℛT=V∗(s0)−Vπ^(s0),R_T\;=\;V^*(s_0)\;-\;V π(s_0), where Vπ^(s)=π^[∑t=0∞γtr(st,at)|s0=s,at=π^(st)]V π(s)= π\! [ _t=0^∞γ^tr(s_t,a_t)\, |\,s_0=s,a_t= π(s_t) ] is the value of policy π π at state s. Figure 1: Error probability over time of VarDE–BAI with different smooth decision functions (Appendix F.1 gives function definitions and hyperparameters). 4.3.2 VarDE–Q-learning Algorithm We apply the VarDE sampling rule to Q-learning, using a decision function and influence weights defined analogously to VarDE–MCTS. However, instead of targeting the variance of the cumulative return, which cannot be computed in non-episodic infinite-horizon MDP, we use the variance of the one-step TD target y=r^+γmaxa∈Q^(s′,a),y= r+γ _a Q(s ,a), which captures environmental stochasticity (reward and transition randomness) as well as bootstrapping noise. The complete VarDE–Q-learning algorithm is deferred to Appendix E (Algorithm 3). 4.3.3 Theoretical Guarantees We state guarantees in the tabular discounted setting. At a high level, we separate two ingredients: (i) a coverage condition ensuring sufficient exploration of all state–action pairs, under which tabular Q-learning converges; and (i) a standard performance-loss bound translating Q-function error into policy suboptimality. Lemma 4.10 (Coverage). Assume rewards satisfy r(s,a)∈[0,1]r(s,a)∈[0,1], ||,||<∞|S|,|A|<∞, and γ∈(0,1)γ∈(0,1). Let NT(s,a)N_T(s,a) be the number of visits to (s,a)(s,a) up to time T. Then every (s,a)(s,a) is visited infinitely often by VarDE–Q-learning, i.e., NT(s,a)→∞as T→∞,∀(s,a)∈×.N_T(s,a)→∞ T→∞,\ \ ∀(s,a) ×A. Under diminishing step sizes satisfying the standard Robbins–Monro conditions (as used in Alg. 3) and infinite visitation, tabular Q-learning converges to the optimal action-value function. According to Watkins & Dayan 1992, we have the following convergence guarantees. Theorem 4.11 (VarDE–Q-learning convergence). Under the same assumptions as Lemma 4.10, Algorithm 3 satisfies ‖QT−Q∗‖∞→T→∞0with probability 1.\|Q_T-Q^*\|_∞ [T→∞]0 probability 1. Consequently, the greedy policies π^T π_T are optimal for all sufficiently large T (up to tie-breaking). This result is an asymptotic consistency guarantee. Unlike the BAI and MCTS guarantees above, it is not a non-asymptotic fixed-budget BPI bound; deriving such a bound for the adaptive variance-driven Q-learning rule remains an important theoretical direction. Lemma 4.12 (Greedy policy suboptimality from Q-error). Let π π be greedy w.r.t. Q Q. If ‖Q^−Q∗‖∞≤ε\| Q-Q^*\|_∞≤ , then ‖Vπ^−V∗‖∞≤2ε1−γ.\|V π-V^*\|_∞≤ 2 1-γ. In particular, ℛT≤21−γ‖QT−Q∗‖∞R_T≤ 21-γ\|Q_T-Q^*\|_∞. 5 Experiments Common protocol. Unless otherwise stated, curves report the mean over independent runs and shaded regions indicate 95% confidence intervals. Hyperparameters for each baseline are tuned by grid search on a separate validation split (same budget as evaluation), and we report the best validation configuration. Implementation details and additional results are provided in Appendix F. Code is available at https://github.com/luongkhang04/VarDE. Table 2: Final error probability (in %) for Best-Arm Identification under four benchmark settings. 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 UCBE2 15.67 21.59 12.93 19.32 UCBE4 19.38 25.92 16.56 22.99 UCBE8 23.54 28.59 19.25 26.09 UGapE2 15.64 21.75 13.48 20.55 UGapE4 20.43 26.43 17.50 23.48 UGapE8 24.96 30.40 19.55 26.01 VarDE0.05 12.87 17.27 11.56 11.83 VarDE0.1 14.04 19.31 7.34 13.81 VarDE0.15 16.56 21.26 8.21 18.52 Figure 2: Monte Carlo value estimates of the recommended root action/policy during planning (mean ± 95% CI over runs). Figure 3: Value estimation error of VarDE–MCTS and other algorithms on synthetic tree (Lower is better). 5.1 Best-Arm Identification We evaluate VarDE–BAI on four standard Best-Arm Identification (BAI) benchmarks and compare against Uniform, UCB-E (Audibert et al. 2010) (α∈2,4,8α∈\2,4,8\), UGapE (Gabillon et al. 2012) (α∈2,4,8α∈\2,4,8\), Successive Halving (Karnin et al. 2013) (SH), Successive Rejects (Audibert et al. 2010) (SR), and Continuous Rejects (Wang et al. 2023) (CR). All results report the error probability under a fixed sampling budget, averaged over 20,00020,000 independent runs. Full experimental details are deferred to Appendix F.1. Table 2 summarizes the results. VarDE–BAI achieves the lowest error probability in all four experiments. These results empirically validate the advantage of our method. We also provide empirical comparisons of VarDE–BAI with different decision functions. Details about the implemented decision functions are provided in Appendix F.1. The results, presented in Figure 1, show that VarDE–BAI with various smooth decision functions performs competitively, demonstrating the flexibility of the VarDE methodology. Appendix F.1.1 reports additional ablations and parameter sensitivity studies. The ablations show that influence weights and empirical variance are both necessary: combining the two consistently outperforms using either component alone. The sensitivity results show that the method is more sensitive to τ than to σ¯ σ. The variance floor mainly stabilizes early estimates, performance near the best τ is comparatively stable across a broad range of σ¯ σ. Appendix F.1.2 directly quantifies this approximation error by comparing the first-order variance surrogate with the full nonlinear variance of the LSELSE decision function. The discrepancy is largest in the sharp small-temperature regime and becomes substantially smaller for moderate τ as sampling progresses. 5.2 Monte Carlo Tree Search 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). We evaluate VarDE–MCTS on three grid-world environments (Sailing, Taxi, FrozenLake) and a synthetic tree benchmark, and compare against UCT (Kocsis & Szepesvári 2006), MENTS (Xiao et al. 2019), RENTS, TENTS (Dam et al. 2021), DENTS, and BTS (Painter et al. 2023). For the grid worlds we report Monte Carlo value estimates of the recommended root action/policy after every 1000 trials (simulations), averaged over 100 independent runs (Fig. 3). For the synthetic tree we report root value estimation error over simulations (Fig. 3). Full experimental details are deferred to Appendix F.2. Across all environments with sparse rewards (FrozenLake) or dense stochastic rewards (Sailing), the policies recommended by VarDE–MCTS achieve the highest Monte Carlo value estimates throughout planning. On the synthetic tree benchmark, VarDE–MCTS attains the lowest root value estimation error across a range of branching factors and depths. Overall, these results highlight the advantage of decision-variance minimization in MCTS, particularly in highly stochastic settings (Sailing and Synthetic Tree with k=200,d=2k=200,d=2), where several baselines exhibit unstable search and fail to reliably reduce the root value estimation error. 5.3 Best Policy Identification We evaluate VarDE–Q-learning on RiverSwim and ForkedRiverSwim across a range of state sizes |||S|. Each method interacts with the environment for a fixed budget of T steps and returns the greedy policy π^T π_T induced by its final Q-estimate. We evaluate π^T π_T exactly on the true MDP (iterative policy evaluation with tolerance 10−610^-6) and compute V∗V^* by policy iteration. In the main plots we report the normalized value proximity 1−‖V∗−Vπ^T‖∞/‖V∗‖∞1-\|V^*-V π_T\|_∞/\|V^*\|_∞. Baselines include model-free Q-UCB (Jin et al. 2018), PSRL (Osband et al. 2013), MF-BPI (Russo & Proutiere 2023), and ε -Q-learning, as well as model-based MDP-NaS, its posterior-sampling variant PS-MDP-NaS (Al Marjani et al. 2021), and O-BPI (Russo & Proutiere 2023). Full experimental details and applied hyperparameters are provided in Appendix F.3. Fig. 4 demonstrates that VarDE–Q-learning is substantially more robust than existing baselines as the environments scale. On RiverSwim, multiple baselines deteriorate rapidly with increasing |S||S| and show large run-to-run variability, consistent with the difficulty of learning from rare and noisy returns. In contrast, VarDE–Q-learning stays near-optimal across all tested sizes and has tight confidence intervals, indicating both higher final policy quality and greater stability under stochasticity. A similar pattern holds on ForkedRiverSwim: VarDE–Q-learning matches or exceeds the best-performing baselines across sizes and remains consistently stable. These results support the main premise of VarDE—minimizing decision-level uncertainty yields superior fixed-budget performance in highly stochastic environments. 6 Discussion and Future Work VarDE casts pure exploration as decision-variance minimization: allocate samples to the component that is both (i) influential to the final recommendation and (i) empirically noisy. Across BAI, MCTS, and best-policy identification, this view is most beneficial in highly stochastic and heteroscedastic settings, where common optimism/entropy heuristics may misallocate budget by reacting to noise rather than to decision-relevant uncertainty. Limitations. Our rule is derived from a first-order variance approximation, which is most accurate once estimates concentrate and the surrogate decision has controlled curvature; early in learning, variance estimates may be unstable, and the choice of surrogate/temperature introduces a bias–smoothness trade-off. In RL and planning, trajectory coupling and bootstrapping create dependencies that are only approximately captured by the diagonal variance view, suggesting room for sharper analysis. The RL guarantee in this paper is asymptotic rather than a finite-sample fixed-budget BPI bound. Future work. Promising directions include decision-variance control with correlated uncertainty (full covariance); adaptive temperature schedules that automatically balance bias and variance; higher-order allocation rules using Hessian and moment information when the additional estimation cost is justified; non-asymptotic theory for variance-driven RL; and scalable influence estimation under function approximation. Impact Statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. Acknowledgements This research is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 102.01-2025.47. The author Hung The Tran is funded by the Quantum AI & Cyber Security Institute, FPT Corporation. References Al Marjani et al. (2021) Al Marjani, A., Garivier, A., and Proutiere, A. Navigating to the best policy in Markov decision processes. Advances in Neural Information Processing Systems, 34:25852–25864, 2021. Audibert et al. (2010) Audibert, J.-Y., Bubeck, S., and Munos, R. Best arm identification in multi-armed bandits. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), p. 41–53, 2010. Azar et al. (2017) Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, p. 263–272. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/azar17a.html. Browne et al. (2012) Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1–43, 2012. doi: 10.1109/TCIAIG.2012.2186810. Dam et al. (2020) Dam, T., Klink, P., D’Eramo, C., Peters, J., and Pajarinen, J. Generalized mean estimation in monte-carlo tree search. In IJCAI, 2020. Dam et al. (2024) Dam, T., Maillard, O.-A., and Kaufmann, E. Power mean estimation in stochastic monte-carlo tree search. In Kiyavash, N. and Mooij, J. M. (eds.), Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, p. 894–918. PMLR, 15–19 Jul 2024. URL https://proceedings.mlr.press/v244/dam24a.html. Dam et al. (2025a) Dam, T., D’Eramo, C., Peters, J., and Pajarinen, J. A unified perspective on value backup and exploration in monte-carlo tree search. J. Artif. Int. Res., 81, January 2025a. ISSN 1076-9757. doi: 10.1613/jair.1.16019. URL https://doi.org/10.1613/jair.1.16019. Dam (2025) Dam, T. Q. Power mean estimation in stochastic continuous Monte-Carlo tree search. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., Berkenkamp, F., Maharaj, T., Wagstaff, K., and Zhu, J. (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, p. 12344–12376. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/v267/dam25b.html. Dam et al. (2021) Dam, T. Q., D’Eramo, C., Peters, J., and Pajarinen, J. Convex regularization in Monte-Carlo tree search. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, p. 2365–2375. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/dam21a.html. Dam et al. (2025b) Dam, T. Q., Panaganti, K., Driss, B., and Wierman, A. Online robust reinforcement learning through monte-carlo planning. In International Conference on Machine Learning, p. 12314–12343. PMLR, 2025b. Dam et al. (2025c) Dam, T. Q., Stenger, P., Schneider, L., Pajarinen, J., D’Eramo, C., and Maillard, O.-A. Monte-Carlo tree search with uncertainty propagation via optimal transport. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., Berkenkamp, F., Maharaj, T., Wagstaff, K., and Zhu, J. (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, p. 12377–12401. PMLR, 13–19 Jul 2025c. URL https://proceedings.mlr.press/v267/dam25c.html. Domingues et al. (2021) Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. Episodic reinforcement learning in finite MDPs: Minimax lower bounds revisited. In Feldman, V., Ligett, K., and Sabato, S. (eds.), Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, p. 578–598. PMLR, 16–19 Mar 2021. URL https://proceedings.mlr.press/v132/domingues21a.html. Dvoretzky et al. (1956) Dvoretzky, A., Kiefer, J., and Wolfowitz, J. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642–669, 1956. doi: 10.1214/aoms/1177728174. Gabillon et al. (2012) Gabillon, V., Ghavamzadeh, M., and Lazaric, A. Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems, p. 3212–3220. Curran Associates, 2012. Jin et al. (2018) Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, p. 4868–4878, 2018. Karnin et al. (2013) Karnin, Z., Koren, T., and Somekh, O. Almost optimal exploration in multi-armed bandits. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th International Conference on Machine Learning, number 3 in Proceedings of Machine Learning Research, p. 1238–1246, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR. URL https://proceedings.mlr.press/v28/karnin13.html. Kocsis & Szepesvári (2006) Kocsis, L. and Szepesvári, C. Bandit based Monte-Carlo planning. In Fürnkranz, J., Scheffer, T., and Spiliopoulou, M. (eds.), Machine Learning: ECML 2006, volume 4212 of Lecture Notes in Computer Science, p. 282–293. Springer, 2006. doi: 10.1007/11871842_29. Marjani & Proutiere (2021) Marjani, A. A. and Proutiere, A. Adaptive sampling for best policy identification in Markov decision processes. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, p. 7459–7468. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/marjani21a.html. Ménard et al. (2021) Ménard, P., Domingues, O. D., Jonsson, A., Kaufmann, E., Leurent, E., and Valko, M. Fast active learning for pure exploration in reinforcement learning. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, p. 7599–7608. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/menard21a.html. Osband et al. (2013) Osband, I., Russo, D., and Van Roy, B. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, p. 3003–3011, 2013. Painter et al. (2023) Painter, M., Baioumy, M., Hawes, N., and Lacerda, B. Monte Carlo tree search with Boltzmann exploration. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, p. 78181–78192. Curran Associates, Inc., 2023. URL https://proceedings.neurips.c/paper_files/paper/2023/file/f670ef96387d9a5a8a51e2ed80cb148d-Paper-Conference.pdf. Russo & Proutiere (2023) Russo, A. and Proutiere, A. Model-free active exploration in reinforcement learning. In Advances in Neural Information Processing Systems, p. 54740–54753, 2023. Wang et al. (2023) Wang, P.-A., Tzeng, R.-C., and Proutiere, A. Best arm identification with fixed budget: A large deviation perspective. In Advances in Neural Information Processing Systems, p. 16804–16815, 2023. Watkins & Dayan (1992) Watkins, C. J. C. H. and Dayan, P. Q-learning. Machine Learning, 8(3):279–292, 1992. doi: 10.1007/BF00992698. Xiao et al. (2019) Xiao, C., Huang, R., Mei, J., Schuurmans, D., and Müller, M. Maximum entropy Monte-Carlo planning. In Advances in Neural Information Processing Systems, p. 9516–9524, 2019. Appendix This appendix provides additional proofs, full algorithm pseudo-codes, and experimental details referenced in the main text. Unless stated otherwise, notation matches the main text. Contents Item Page Appendix A: Proofs for VarDE Methodology A Appendix B: Proofs for VarDE–BAI B Appendix C: Proofs for VarDE–MCTS C Appendix D: Proofs for VarDE–Q-learning D Appendix E: Full Pseudo-codes of VarDE-BAI, VarDE-MCTS, and VarDE-Q-learning E Appendix F: Experiment Details F Appendix A Proofs for Section 3 (VarDE Methodology) A.1 Proof of Lemma 3.2 (Local Linear Approximation) Proof. Let Δ:=μ^−μ := μ-μ. By Taylor’s theorem with remainder on the segment between μ and μ μ, which lies in D=[a,b]nD=[a,b]^n under Assumption 3.1, f(μ^)=f(μ)+∇f(μ)⊤Δ+12Δ⊤Hf(ξ)Δ,f( μ)=f(μ)+∇ f(μ) + 12 H_f(ξ) , for some ξ on the segment [μ,μ^][μ, μ]. Since ‖Hf(ξ)‖op≤M\|H_f(ξ)\|_op≤ M, |12Δ⊤Hf(ξ)Δ|≤12‖Hf(ξ)‖op‖Δ‖22≤M2‖Δ‖22. | 12 H_f(ξ) |≤ 12\|H_f(ξ)\|_op\| \|_2^2≤ M2\| \|_2^2. Thus the remainder is (M‖μ^−μ‖22)O(M\| μ-μ\|_2^2). Writing wi(μ)=∂if(μ)w_i(μ)= _if(μ) and c=f(μ)−∇f(μ)⊤μc=f(μ)-∇ f(μ) μ gives the stated first-order form. ∎ A.2 Auxiliary min-pulls guarantee Throughout the proof, write Δ(t):=μ^(t)−μ,Δi(t):=μ^i(t)−μi,Yt:=f(μ^(t)), (t):= μ(t)-μ, _i(t):= μ_i(t)- _i, Y_t:=f( μ(t)), and let g:=∇f(μ)g:=∇ f(μ), so that gi=wi(μ)g_i=w_i(μ). Under Assumption 3.1, bounded observations imply μ,μ^(t)∈D=[a,b]nμ, μ(t)∈ D=[a,b]^n for all t, and the segment between them is contained in D. Moreover, because each wiw_i is continuous on the compact set D, W:=maxx∈Dmaxi∈[n]|wi(x)|<∞.W:= _x∈ D _i∈[n]|w_i(x)|<∞. Lemma A.1 (General min-pulls guarantee). Under Assumption 3.1, the variance floor in Section 3.4, and Assumption 3.3, there exist constants c>0c>0 and C>0C>0, depending only on n,ρ,W,σ¯2,a,bn,ρ,W, σ^2,a,b, such that for all t≥nt≥ n and all i∈[n]i∈[n], Ni(t)≥ctn−C.N_i(t)≥ c tn-C. In particular, Ni(t)=Ω(t)N_i(t)= (t) for every component. Proof. Let ℳM be a component with maximal pull count at time t, so Nℳ(t)≥t/nN_M(t)≥ t/n. Let t′≤t ≤ t be the last time at which ℳM is selected. Immediately before that pull, the VarDE rule implies that for every i≠ℳi , wℳ(μ^(t′−1))2σ~ℳ2(t′−1)Nℳ(t′−1)(Nℳ(t′−1)+1)≥wi(μ^(t′−1))2σ~i2(t′−1)Ni(t′−1)(Ni(t′−1)+1). w_M( μ(t -1))^2 σ_M^2(t -1)N_M(t -1)(N_M(t -1)+1)≥ w_i( μ(t -1))^2 σ_i^2(t -1)N_i(t -1)(N_i(t -1)+1). Rearranging gives Ni(t′−1)(Ni(t′−1)+1)Nℳ(t′−1)(Nℳ(t′−1)+1)≥wi(μ^(t′−1))2wℳ(μ^(t′−1))2⋅σ~i2(t′−1)σ~ℳ2(t′−1). N_i(t -1)(N_i(t -1)+1)N_M(t -1)(N_M(t -1)+1)≥ w_i( μ(t -1))^2w_M( μ(t -1))^2· σ_i^2(t -1) σ_M^2(t -1). By Assumption 3.3 and by the definition of W, wi(μ^(t′−1))2wℳ(μ^(t′−1))2≥ρ2W2. w_i( μ(t -1))^2w_M( μ(t -1))^2≥ ρ^2W^2. Also, the variance floor and bounded observations give σ~i2(t′−1)≥σ¯2,σ~ℳ2(t′−1)≤(b−a)24. σ_i^2(t -1)≥ σ^2, σ_M^2(t -1)≤ (b-a)^24. Hence Ni(t′−1)(Ni(t′−1)+1)Nℳ(t′−1)(Nℳ(t′−1)+1)≥ρ2W2⋅4σ¯2(b−a)2=:c0>0. N_i(t -1)(N_i(t -1)+1)N_M(t -1)(N_M(t -1)+1)≥ ρ^2W^2· 4 σ^2(b-a)^2=:c_0>0. Since x↦x(x+1)x x(x+1) is increasing on [0,∞)[0,∞), there exist constants c1,C1>0c_1,C_1>0 depending only on c0c_0 such that x(x+1)≥c0y(y+1)⟹x≥c1y−C1.x(x+1)≥ c_0y(y+1) x≥ c_1y-C_1. Therefore Ni(t′−1)≥c1Nℳ(t′−1)−C1.N_i(t -1)≥ c_1N_M(t -1)-C_1. Counts are nondecreasing and t′t is the last time at which ℳM is selected, so Ni(t)≥Ni(t′−1),Nℳ(t′−1)=Nℳ(t)−1≥tn−1.N_i(t)≥ N_i(t -1), N_M(t -1)=N_M(t)-1≥ tn-1. Combining these inequalities yields Ni(t)≥c1(tn−1)−C1=ctn−CN_i(t)≥ c_1 ( tn-1 )-C_1=c tn-C for suitable constants c,C>0c,C>0. ∎ Corollary A.2. Under the assumptions of Lemma A.1, for every fixed integer k∈1,2,3k∈\1,2,3\, ∑i=1nNi(t)−k=O(t−k),∑i=1nσi2Ni(t)=O(t−1). _i=1^nN_i(t)^-k=O(t^-k), _i=1^n _i^2N_i(t)=O(t^-1). Proof. Lemma A.1 gives Ni(t)≥ct/n−CN_i(t)≥ ct/n-C for all i. Since n is fixed, each Ni(t)−k=O(t−k)N_i(t)^-k=O(t^-k), and summing over i proves the first claim. The second follows immediately because the variances are finite under bounded observations. ∎ A.3 Proof of Lemma 3.4 (First-Order Variance Decomposition) Proof. We prove the stated expansion along a VarDE trajectory under Assumption 3.1, the variance floor in Section 3.4, and Assumption 3.3. Fix t and write Δ:=Δ(t) := (t), μ^:=μ^(t) μ:= μ(t), and Y:=YtY:=Y_t. By Taylor’s theorem, Y=f(μ)+g⊤Δ+Q,Q:=12Δ⊤Hf(ξ)Δ,Y=f(μ)+g +Q, Q:= 12 H_f(ξ) , for some random point ξ on the segment [μ,μ^][μ, μ]. Assumption 3.1 applies to the whole segment. Therefore Var(Y)=Var(g⊤Δ)+Var(Q)+2Cov(g⊤Δ,Q). (Y)= (g )+ (Q)+2 (g ,Q). Leading term. Since the components are independent, Var(g⊤Δ)=∑i=1ngi2σi2Ni(t)=∑i=1nwi(μ)2σi2Ni(t). (g )= _i=1^ng_i^2 _i^2N_i(t)= _i=1^nw_i(μ)^2 _i^2N_i(t). Quadratic remainder. By the bounded Hessian condition, |Q|≤M2‖Δ‖22,|Q|≤ M2\| \|_2^2, where M:=supz∈[a,b]n‖Hf(z)‖opM:= _z∈[a,b]^n\|H_f(z)\|_op. Hence Var(Q)≤[Q2]≤M24‖Δ‖24. (Q)≤ [Q^2]≤ M^24 \| \|_2^4. Using (∑iai)2≤n∑iai2( _ia_i)^2≤ n _ia_i^2 with ai=Δi2a_i= _i^2, ‖Δ‖24≤n∑i=1nΔi4.\| \|_2^4≤ n _i=1^n _i^4. For bounded observations, there are constants C4,i<∞C_4,i<∞ such that [Δi4]≤C4,iNi(t)−2 [ _i^4]≤ C_4,iN_i(t)^-2. By Corollary A.2, ‖Δ‖24=O(t−2),Var(Q)=O(t−2). \| \|_2^4=O(t^-2), (Q)=O(t^-2). Covariance term. Write Q0:=12Δ⊤Hf(μ)Δ,Q1:=Q−Q0.Q_0:= 12 H_f(μ) , Q_1:=Q-Q_0. Then Cov(g⊤Δ,Q)=Cov(g⊤Δ,Q0)+Cov(g⊤Δ,Q1). (g ,Q)= (g ,Q_0)+ (g ,Q_1). For Q0Q_0, since Hf(μ)H_f(μ) is deterministic and [g⊤Δ]=0 [g ]=0, Cov(g⊤Δ,Q0)=[g⊤ΔQ0]=12∑i,j,kgk(Hf(μ))ij[ΔkΔiΔj]. (g ,Q_0)= [g \,Q_0]= 12 _i,j,kg_k(H_f(μ))_ij [ _k _i _j]. By independence and centering, every mixed term vanishes unless i=j=ki=j=k. Hence Cov(g⊤Δ,Q0)=12∑i=1ngi(Hf(μ))ii[Δi3]. (g ,Q_0)= 12 _i=1^ng_i(H_f(μ))_i [ _i^3]. Bounded observations imply |[Δi3]|≤C3,iNi(t)−2| [ _i^3]|≤ C_3,iN_i(t)^-2, and therefore |Cov(g⊤Δ,Q0)|=O(t−2).| (g ,Q_0)|=O(t^-2). For Q1Q_1, Lipschitz continuity of the Hessian gives ‖Hf(ξ)−Hf(μ)‖op≤L‖ξ−μ‖2≤L‖Δ‖2,\|H_f(ξ)-H_f(μ)\|_op≤ L\|ξ-μ\|_2≤ L\| \|_2, so |Q1|≤L2‖Δ‖23.|Q_1|≤ L2\| \|_2^3. By Cauchy–Schwarz, |Cov(g⊤Δ,Q1)|≤Var(g⊤Δ)[Q12].| (g ,Q_1)|≤ (g ) [Q_1^2]. Now Var(g⊤Δ)=O(t−1) (g )=O(t^-1) by Corollary A.2. Also, [Q12]≤L24‖Δ‖26. [Q_1^2]≤ L^24 \| \|_2^6. Using (∑iai)3≤n2∑iai3( _ia_i)^3≤ n^2 _ia_i^3 with ai=Δi2a_i= _i^2 and the bounded-observation moment bound |Δi|6≤C6,iNi(t)−3 | _i|^6≤ C_6,iN_i(t)^-3, ‖Δ‖26=O(t−3). \| \|_2^6=O(t^-3). Thus |Cov(g⊤Δ,Q1)|=O(t−2).| (g ,Q_1)|=O(t^-2). Combining the leading term, Var(Q)=O(t−2) (Q)=O(t^-2), and both covariance bounds gives Var(Yt)=∑i=1nwi(μ)2σi2Ni(t)+O(t−2). (Y_t)= _i=1^nw_i(μ)^2 _i^2N_i(t)+O(t^-2). ∎ A.4 Proof of Lemma 3.5 (One-Sample Variance Decrement) Proof. Let μ^i(N)=N−1∑s=1NXi,s μ_i^(N)=N^-1 _s=1^NX_i,s with Var[Xi,s]=σi2 [X_i,s]= _i^2. Then Var[μ^i(N)]=σi2N,Var[μ^i(N+1)]=σi2N+1. [ μ_i^(N)]= _i^2N, [ μ_i^(N+1)]= _i^2N+1. Therefore ΔVar[μ^i]=Var[μ^i(N+1)]−Var[μ^i(N)]=−σi2N(N+1). [ μ_i]= [ μ_i^(N+1)]- [ μ_i^(N)]=- _i^2N(N+1). ∎ A.5 Proof of Proposition 3.6 (Influence-Weighted Global Variance Decrement) Proof. By Lemma 3.4, Vt:=Var[Yt]=∑j=1nwj(μ)2σj2Nj(t)+O(t−2),V_t:= [Y_t]= _j=1^nw_j(μ)^2 _j^2N_j(t)+O(t^-2), and similarly Vt+1=∑j=1nwj(μ)2σj2Nj(t+1)+O((t+1)−2).V_t+1= _j=1^nw_j(μ)^2 _j^2N_j(t+1)+O((t+1)^-2). If component iti_t is sampled, then Nit(t+1)=Nit(t)+1N_i_t(t+1)=N_i_t(t)+1 and all other counts are unchanged. Hence ∑j=1nwj(μ)2(σj2Nj(t+1)−σj2Nj(t))=−wit(μ)2σit2Nit(t)(Nit(t)+1). _j=1^nw_j(μ)^2 ( _j^2N_j(t+1)- _j^2N_j(t) )=- w_i_t(μ)^2 _i_t^2N_i_t(t)(N_i_t(t)+1). Since O((t+1)−2)−O(t−2)=O(t−2)O((t+1)^-2)-O(t^-2)=O(t^-2), subtracting the two expansions gives Vt+1−Vt=−wit(μ)2σit2Nit(t)(Nit(t)+1)+O(t−2).V_t+1-V_t=- w_i_t(μ)^2 _i_t^2N_i_t(t)(N_i_t(t)+1)+O(t^-2). ∎ A.6 Proof of Theorem 3.7 (Variance Decay of VarDE) Proof. Lemma A.1 gives Ni(T)=Ω(T)N_i(T)= (T) for every i∈[n]i∈[n]. By Lemma 3.4, Var[YT]=∑i=1nwi(μ)2σi2Ni(T)+O(T−2). [Y_T]= _i=1^nw_i(μ)^2 _i^2N_i(T)+O(T^-2). The leading term is O(T−1)O(T^-1) because every Ni(T)N_i(T) is linear in T, while the curvature correction is O(T−2)O(T^-2). Thus Var[YT]=O(T−1)+O(T−2)=O(T−1). [Y_T]=O(T^-1)+O(T^-2)=O(T^-1). ∎ A.7 First-order allocation constant The same decomposition also clarifies what VarDE can improve asymptotically. Suppose an allocation has limiting proportions Ni(T)=piT+ri(T),ri(T)=O(1),pi>0,∑i=1npi=1.N_i(T)=p_iT+r_i(T), r_i(T)=O(1), p_i>0, _i=1^np_i=1. For each fixed i, 1Ni(T)=1piT+ri(T)=1piT+O(T−2), 1N_i(T)= 1p_iT+r_i(T)= 1p_iT+O(T^-2), so Lemma 3.4 gives the sharp first-order expansion Var[YT]=∑i=1nwi(μ)2σi2Ni(T)+O(T−2)=1TC(p)+O(T−2), [Y_T]= _i=1^nw_i(μ)^2 _i^2N_i(T)+O(T^-2)= 1TC(p)+O(T^-2), where C(p):=∑i=1nwi(μ)2σi2pi.C(p):= _i=1^n w_i(μ)^2 _i^2p_i. Thus every allocation with nonzero limiting proportions has the same T−1T^-1 exponent; the meaningful asymptotic comparison is the leading constant C(p)C(p). To minimize C(p)C(p) over the probability simplex, apply Cauchy–Schwarz: (∑i|wi(μ)|σi)2=(∑i|wi(μ)|σipipi)2≤(∑iwi(μ)2σi2pi)(∑ipi)=C(p). ( _i|w_i(μ)| _i )^2= ( _i |w_i(μ)| _i p_i p_i )^2≤ ( _i w_i(μ)^2 _i^2p_i ) ( _ip_i )=C(p). Equality holds if and only if |wi(μ)|σipi=cpifor all i, |w_i(μ)| _i p_i=c p_i all i, for some constant c>0c>0, equivalently pi∝|wi(μ)|σip_i |w_i(μ)| _i. Hence the optimal first-order allocation and constant are pi⋆=|wi(μ)|σi∑j|wj(μ)|σj,C⋆=(∑i|wi(μ)|σi)2.p_i = |w_i(μ)| _i _j|w_j(μ)| _j, C_ = ( _i|w_i(μ)| _i )^2. For uniform allocation pi=1/np_i=1/n, the constant is Cunif=n∑iwi(μ)2σi2,C_unif=n _iw_i(μ)^2 _i^2, and C⋆≤CunifC_ ≤ C_unif, with equality only in the degenerate case where |wi(μ)|σi|w_i(μ)| _i is constant across i. This is the sense in which VarDE is designed to improve the asymptotics. Its empirical one-step score is Si(t)=wi(μ^(t))2σ~i2(t)Ni(t)(Ni(t)+1).S_i(t)=w_i( μ(t))^2 σ_i^2(t)N_i(t)(N_i(t)+1). In the stabilized regime, wi(μ^(t))≈wi(μ)w_i( μ(t))≈ w_i(μ), σ~i2(t)≈σi2 σ_i^2(t)≈ _i^2, and Ni(t)(Ni(t)+1)≈Ni(t)2N_i(t)(N_i(t)+1)≈ N_i(t)^2, so Si(t)≈wi(μ)2σi2Ni(t)2.S_i(t)≈ w_i(μ)^2 _i^2N_i(t)^2. A greedy allocation that repeatedly samples the largest marginal decrement tends to equalize these leading marginal scores among persistently sampled components. Equalization gives wi(μ)2σi2Ni(T)2≈wj(μ)2σj2Nj(T)2, w_i(μ)^2 _i^2N_i(T)^2≈ w_j(μ)^2 _j^2N_j(T)^2, and therefore Ni(T)Nj(T)≈|wi(μ)|σi|wj(μ)|σj. N_i(T)N_j(T)≈ |w_i(μ)| _i|w_j(μ)| _j. After normalization by T, this is exactly the optimal first-order proportion p⋆p . Hence VarDE’s intended advantage is not a better variance-decay exponent than all well-spread allocations, but a smaller first-order constant by targeting the allocation that minimizes the decision-level variance expansion. Appendix B Proofs for Subsection 4.1 (VarDE–BAI) B.1 Proof of Lemma 4.1 (LSE bound) Proof. Lower bound. Since ∑i=1Keμ^i/τ≥emaxiμ^i/τ _i=1^Ke μ_i/τ≥ e _i μ_i/τ, LSEτ(μ^)=τlog∑i=1Keμ^i/τ≥τlogemaxiμ^i/τ=maxiμ^i.LSE_τ( μ)=τ _i=1^Ke μ_i/τ\;≥\;τ e _i μ_i/τ\;=\; _i μ_i. Upper bound. Also ∑i=1Keμ^i/τ≤K⋅emaxiμ^i/τ _i=1^Ke μ_i/τ≤ K· e _i μ_i/τ, hence LSEτ(μ^)=τlog∑i=1Keμ^i/τ≤τlog(Kemaxiμ^i/τ)=maxiμ^i+τlogK.LSE_τ( μ)=τ _i=1^Ke μ_i/τ\;≤\;τ \! (K\,e _i μ_i/τ )\;=\; _i μ_i+τ K. This proves the claim. ∎ B.2 Proof of Lemma 4.2 (LSE curvature) Proof. Let f(x)=LSEτ(x)=τlog∑i=1Kexi/τf(x)=LSE_τ(x)=τ _i=1^Ke^x_i/τ. Then ∂f∂xi(x)=exi/τ∑j=1Kexj/τ=pi(x),i=1,…,K, ∂ f∂ x_i(x)= e^x_i/τ _j=1^Ke^x_j/τ=p_i(x), i=1,…,K, Differentiating once more, ∇2f(x)=1τ(Diag(p(x))−p(x)p(x)⊤).∇^2f(x)= 1τ (Diag(p(x))-p(x)p(x) ). For any v∈ℝKv ^K satisfying ‖v‖2=1\|v\|_2=1, we have v⊤∇2f(x)v v ∇^2f(x)\,v =1τ(∑i=1Kpi(x)vi2−(∑i=1Kpi(x)vi)2) = 1τ\! ( _i=1^Kp_i(x)\,v_i^2- ( _i=1^Kp_i(x)\,v_i )^2 ) =1τVari∼p(x)[vi] = 1τ\, _i p(x)[v_i] ≤1τ(maxivi−minivi)24 ≤ 1τ\, ( _iv_i- _iv_i)^24 ≤1τ(maxivi)2+(minivi)22 ≤ 1τ\, ( _iv_i)^2+( _iv_i)^22 ≤1τ∑i=1Kvi22 ≤ 1τ\, _i=1^Kv_i^22 =12τ. = 12τ. Taking the supremum over all ‖v‖2=1\|v\|_2=1 gives ‖∇2f(x)‖op=sup‖v‖2=1v⊤∇2f(x)v≤12τ∀x.\|∇^2f(x)\|_op= _\|v\|_2=1v ∇^2f(x)\,v≤ 12τ ∀ x. ∎ B.3 Proof of Lemma 4.3 (LSE Hessian Lipschitzness) Proof. Let pi(x)=exi/τ∑ℓ=1Kexℓ/τ.p_i(x)= e^x_i/τ _ =1^Ke^x_ /τ. As in the proof of Lemma 4.2, the Hessian entries are Hij(x)=1τ(δijpi(x)−pi(x)pj(x)).H_ij(x)= 1τ ( _ijp_i(x)-p_i(x)p_j(x) ). The softmax derivative is ∂kpi(x)=1τpi(x)(δik−pk(x)). _kp_i(x)= 1τp_i(x)( _ik-p_k(x)). Therefore ∂kHij(x)=1τ2[δijpi(δik−pk)−pi(δik−pk)pj−pipj(δjk−pk)]. _kH_ij(x)= 1τ^2 [ _ijp_i( _ik-p_k)-p_i( _ik-p_k)p_j-p_ip_j( _jk-p_k) ]. Since pi∈[0,1]p_i∈[0,1] for all i, each bracketed term has absolute value at most one, and hence |∂kHij(x)|≤3τ2| _kH_ij(x)|≤ 3τ^2 uniformly over x∈ℝKx ^K and all i,j,ki,j,k. For any x,y∈Dx,y∈ D, the scalar mean-value theorem applied entrywise gives |Hij(x)−Hij(y)|≤3τ2∑k=1K|xk−yk|≤3Kτ2‖x−y‖2.|H_ij(x)-H_ij(y)|≤ 3τ^2 _k=1^K|x_k-y_k|≤ 3 Kτ^2\|x-y\|_2. Thus ‖H(x)−H(y)‖op \|H(x)-H(y)\|_op ≤‖H(x)−H(y)‖F ≤\|H(x)-H(y)\|_F ≤Kmaxi,j|Hij(x)−Hij(y)| ≤ K _i,j|H_ij(x)-H_ij(y)| ≤3K3/2τ2‖x−y‖2. ≤ 3K^3/2τ^2\|x-y\|_2. This proves the claim with Lτ,K=3K3/2/τ2L_τ,K=3K^3/2/τ^2. ∎ B.4 Proof of Lemma 4.4 (LSE nonvanishing influence weights) Proof. For any x∈D=[a,b]Kx∈ D=[a,b]^K, each coordinate satisfies xi≥ax_i≥ a, so exi/τ≥ea/τe^x_i/τ≥ e^a/τ. Likewise, xj≤bx_j≤ b for every j, so ∑j=1Kexj/τ≤Keb/τ. _j=1^Ke^x_j/τ≤ Ke^b/τ. Therefore wi(x)=exi/τ∑j=1Kexj/τ≥ea/τKeb/τ=1Ke(a−b)/τ=ρτ,D>0.w_i(x)= e^x_i/τ _j=1^Ke^x_j/τ≥ e^a/τKe^b/τ= 1Ke^(a-b)/τ= _τ,D>0. The upper bound wi(x)≤1w_i(x)≤ 1 is immediate from the definition of the softmax weights. This proves the claim. ∎ B.5 Proof of Theorem 4.5 (VarDE–BAI error probability) Lemma B.1 (Confidence interval for the empirical variance). Let X1,…,XnX_1,…,X_n be i.i.d. random variables supported on [a,b][a,b], with μ=[X]μ=E[X] and σ2=Var(X)σ^2=Var(X). Define μ^=1n∑i=1nXi,σ^2=1n∑i=1n(Xi−μ^)2. μ= 1n _i=1^nX_i, σ^2= 1n _i=1^n(X_i- μ)^2. Then for any δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, |σ^2−σ2|≤(b−a)2(log(2/δ)n+log(2/δ)n). |\, σ^2-σ^2\, |\;≤\;(b-a)^2\! ( (2/δ)n+ (2/δ)n ). Equivalently, for any k>0k>0, with probability at least 1−2e−k1-2e^-k, |σ^2−σ2|≤(b−a)2(kn+kn). |\, σ^2-σ^2\, |\;≤\;(b-a)^2\! ( kn+ kn ). Proof. We expand the empirical variance as σ^2 σ^2 =1n∑i=1n(Xi−μ^)2 = 1n _i=1^n(X_i- μ)^2 =1n∑i=1n[(Xi−μ)−(μ^−μ)]2 = 1n _i=1^n [(X_i-μ)-( μ-μ) ]^2 =1n∑i=1n[(Xi−μ)2−2(Xi−μ)(μ^−μ)+(μ^−μ)2] = 1n _i=1^n [(X_i-μ)^2-2(X_i-μ)( μ-μ)+( μ-μ)^2 ] =1n∑i=1n(Xi−μ)2−2(μ^−μ)1n∑i=1n(Xi−μ)+(μ^−μ)2. = 1n _i=1^n(X_i-μ)^2-2( μ-μ) 1n _i=1^n(X_i-μ)+( μ-μ)^2. =1n∑i=1n(Xi−μ)2−2(μ^−μ)2+(μ^−μ)2 = 1n _i=1^n(X_i-μ)^2-2( μ-μ)^2+( μ-μ)^2 =1n∑i=1n(Xi−μ)2−(μ^−μ)2. = 1n _i=1^n(X_i-μ)^2-( μ-μ)^2. Thus, we can write the error as σ^2−σ2 σ^2-σ^2 =(1n∑i=1n(Xi−μ)2−σ2)−(μ^−μ)2 = ( 1n _i=1^n(X_i-μ)^2-σ^2 )-( μ-μ)^2 =1n∑i=1n[(Xi−μ)2−σ2]⏟A−(μ^−μ)2⏟B. = 1n _i=1^n [(X_i-μ)^2-σ^2 ]_A\;-\; ( μ-μ)^2_B. Since Xi∈[a,b]X_i∈[a,b], it follows that (Xi−μ)2∈[ 0,(b−a)2](X_i-μ)^2∈[\,0,\,(b-a)^2\,]. Applying Hoeffding’s inequality to (Xi−μ)2(X_i-μ)^2 gives Pr(|A|≤(b−a)2log(2/δ)n)≥1−δ2. \! (|A|≤(b-a)^2 (2/δ)n )≥ 1- δ2. Next apply Hoeffding to μ μ: Pr(|μ^−μ|≤(b−a)log(2/δ)n)≥1−δ2. \! (| μ-μ|≤(b-a) (2/δ)n )≥ 1- δ2. Hence B=(μ^−μ)2≤(b−a)2log(2/δ)n.B=( μ-μ)^2≤(b-a)^2 (2/δ)n. By a union bound, with probability at least 1−δ1-δ, both bounds on A and B hold. Therefore, |σ^2−σ2|≤|A|+|B|≤(b−a)2(log(2/δ)n+log(2/δ)n). | σ^2-σ^2 |≤|A|+|B|≤(b-a)^2\! ( (2/δ)n+ (2/δ)n ). ∎ Lemma B.2 (Lower bound on each arm’s number of pulls). Assume rewards are supported on [0,1][0,1]. Run VarDE–BAI (Alg. 1) with temperature τ>0τ>0 and warm start η. Then, after T>KT>K total pulls, each arm i has been pulled at least Ni(T)≥ 2e−1/τσ¯(TK−12)−12.N_i(T)\;≥\;2e^-1/τ σ\, ( TK- 12 )- 12. Proof. At each round t, we choose the arm i with the maximum value argmaxiwi(μ^(t))2σ~i2(t)Ni(t)(Ni(t)+1), _i w_i( μ(t))^2\, σ_i^2(t)N_i(t) (N_i(t)+1 ), where wi(μ^(t))=exp(μ^i(t)/τ)∑jexp(μ^j(t)/τ),σ~i(t):=maxσ^i(t),σ¯.w_i( μ(t))= \! ( μ_i(t)/τ ) _j \! ( μ_j(t)/τ ), σ_i(t):= \ σ_i(t),\, σ \. Assume that after all T rounds, the arm M has been chosen with maximum times. At the final time t where arm M is selected, the selection rule implies that wM(μ^(t))2σ~M2(t)NM(t)(NM(t)+1)≥wi(μ^(t))2σ~i2(t)Ni(t)(Ni(t)+1),∀i≠M. w_M( μ(t))^2\, σ_M^2(t)N_M(t) (N_M(t)+1 )\;≥\; w_i( μ(t))^2\, σ_i^2(t)N_i(t) (N_i(t)+1 ), ∀ i≠ M. Rearranging the above inequality yields Ni(t)(Ni(t)+1)NM(t)(NM(t)+1)≥exp(2τ(μ^i(t)−μ^M(t)))⋅σ~i2(t)σ~M2(t). N_i(t)\, (N_i(t)+1 )N_M(t)\, (N_M(t)+1 )\;≥\; \! ( 2τ ( μ_i(t)- μ_M(t) ) )· σ_i^2(t) σ_M^2(t). Since rewards lie in [0,1][0,1], empirical means satisfy μ^k(t)∈[0,1] μ_k(t)∈[0,1]. Consequently, μ^i(t)−μ^M(t)≥−1,∀i≠M μ_i(t)- μ_M(t)\;≥\;-1,\,∀\,i≠ M. Thus, Ni(t)(Ni(t)+1)NM(t)(NM(t)+1)≥e−2/τ⋅σ~i2(t)σ~M2(t). N_i(t)\, (N_i(t)+1 )N_M(t)\, (N_M(t)+1 )\;≥\;e^-2/τ· σ_i^2(t) σ_M^2(t). Since we have 1/4≥σ~i2(t)≥σ¯21/4≥ σ_i^2(t)≥ σ^2, it follows that σ~i2(t)/σ~M2(t)≥4σ¯2 σ_i^2(t)/ σ_M^2(t)≥ 4 σ^2. Therefore, Ni(t)(Ni(t)+1)NM(t)(NM(t)+1)≥ 4e−2/τ⋅σ¯2. N_i(t)\, (N_i(t)+1 )N_M(t)\, (N_M(t)+1 )\;≥\;4e^-2/τ· σ^2. Since Ni(t),NM(t)≥0N_i(t),N_M(t)≥ 0, we also have Ni2(t)+Ni(t)+1/4NM2(t)+NM(t)+1/4≥Ni2(t)+Ni(t)NM2(t)+NM(t)≥ 4e−2/τ⋅σ¯2. N_i^2(t)+N_i(t)+1/4N_M^2(t)+N_M(t)+1/4\;≥\; N_i^2(t)+N_i(t)N_M^2(t)+N_M(t)\;≥\;4e^-2/τ· σ^2. Which is equivalent to (Ni(t)+1/2NM(t)+1/2)2≥ 4e−2/τ⋅σ¯2. ( N_i(t)+1/2N_M(t)+1/2 )^2\;≥\;4e^-2/τ· σ^2. So that Ni(t)≥ 2e−1/τσ¯(NM(t)+12)−12.N_i(t)\;≥\;2e^-1/τ σ\, (N_M(t)+ 12 )- 12. Since M is pulled most frequently after T rounds and t is the last time it was pulled, NM(t)=NM(T)−1≥T/K−1N_M(t)=N_M(T)-1≥ T/K-1. Thus, Ni(t)≥ 2e−1/τσ¯(TK−12)−12.N_i(t)\;≥\;2e^-1/τ σ\, ( TK- 12 )- 12. This inequality holds for all arms i, including M, which is the trivial case. ∎ Proof of Theorem 4.5. We write the empirical gap between the best arm i∗i^* and arm i≠i∗i≠ i^* after T total pulls as μ^i∗(T)−μ^i(T)=1Ni∗(T)∑n=1Ni∗(T)Xi∗,n−1Ni(T)∑n=1Ni(T)Xi,n. μ_i^*(T)- μ_i(T)= 1N_i^*(T) _n=1^N_i^*(T)X_i^*,n- 1N_i(T) _n=1^N_i(T)X_i,n. Since [μ^i∗(T)−μ^i(T)]=μi∗−μi=Δi [ μ_i^*(T)- μ_i(T)]= _i^*- _i= _i and the samples are independent, we can apply Hoeffding’s inequality to get Prμ^i(T)−μ^i∗(T)+Δi≥Δi≤exp(−2Δi21Ni(T)+1Ni∗(T)). \ μ_i(T)- μ_i^*(T)+ _i≥ _i\≤ \! (- 2 _i^2 1N_i(T)+ 1N_i^*(T) ). Using Lemma B.2 and rearranging the terms gives Prμ^i(T)≥μ^i∗(T)≤exp[−Δi2(2e−1/τσ¯(TK−12)−12)]. \ μ_i(T)≥ μ_i^*(T)\≤ \! [- _i^2 (2e^-1/τ σ\, ( TK- 12 )- 12 ) ]. The error probability of VarDE–BAI is obtained by a union bound over all suboptimal arms: Pri^T≠i∗≤∑i≠i∗Prμ^i(T)≥μ^i∗(T)≤∑i≠i∗exp[−Δi2(2e−1/τσ¯(TK−12)−12)]. \ i_T≠ i^*\≤ _i≠ i^* \ μ_i(T)≥ μ_i^*(T)\≤ _i≠ i^* \! [- _i^2 (2e^-1/τ σ\, ( TK- 12 )- 12 ) ]. ∎ Appendix C Proofs for Subsection 4.2 (VarDE–MCTS) Throughout this section, rewards are in [0,1][0,1], the horizon is H, hence returns are therefore bounded in [0,H][0,H]. For each node s and action a∈(s)a (s), we denote that Q∗(s,a)Q^*(s,a) is the true action-value, Q^(s,a) Q(s,a) is its empirical estimate by backpropagation, N(s)N(s) is the number of visits to node s, N(s,a)N(s,a) is the number of times action a has been selected at node s, and (s,a)=s′:P(s′∣s,a)>0S(s,a)=\s :P(s s,a)>0\ is the (finite) set of possible successor states. C.1 Reduction to VarDE–BAI at each node Recall the selection rule of VarDE–MCTS (Algorithm 2): at a node shs_h with empirical estimates Q^(sh,⋅) Q(s_h,·), empirical variances σ^2(sh,⋅) σ^2(s_h,·) and counts N(sh,⋅)N(s_h,·), we first compute influence weights wτ(sh,a):=exp(Q^(sh,a)/τ)∑b∈A(sh)exp(Q^(sh,b)/τ),w_τ(s_h,a):= ( Q(s_h,a)/τ) _b∈ A(s_h) ( Q(s_h,b)/τ), and then select ah∈argmaxa∈A(sh)wτ(sh,a)2σ~2(sh,a)N(sh,a)(N(sh,a)+1).a_h∈ _a∈ A(s_h) w_τ(s_h,a)^2\, σ^2(s_h,a)N(s_h,a)\, (N(s_h,a)+1 )\,. This is exactly the VarDE–BAI selection rule applied to a bandit whose arms correspond to actions a∈A(sh)a∈ A(s_h), with empirical means μ^i≡Q^(sh,a) μ_i≡ Q(s_h,a), empirical variances σ^i2≡σ^2(sh,a) σ_i^2≡ σ^2(s_h,a) and counts Ni≡N(sh,a)N_i≡ N(s_h,a). Therefore, we also have the following lower bound on the number of times each action selected at node s: Lemma C.1 (Min-pulls per action at each node). Run VarDE–MCTS (Alg. 2) with temperature τ. Then, after N(s)>|(s)|N(s)>|A(s)| visits to node s, each action a∈(s)a (s) has been selected at least N(s,a)≥ 2e−1/τσ¯(N(s)|(s)|−12)−12.N(s,a)\;≥\;2e^-1/τ σ\, ( N(s)|A(s)|- 12 )- 12. Corollary C.2. For any state s with N(s)>|(s)|N(s)>|A(s)| visits and any action a∈(s)a (s), exist an α>0α>0 such that N(s,a)≥αN(s)N(s,a)≥α N(s) C.2 Concentration of empirical reward mean Lemma C.3 (Concentration of empirical reward mean). Fix any state s and action a∈(s)a (s) with N(s,a)N(s,a) visits, the ithi^th visit receives reward r^i(s,a) r_i(s,a). Let r¯(s,a)=1N(s,a)∑i=1N(s,a)r^i(s,a) r(s,a)= 1N(s,a) _i=1^N(s,a) r_i(s,a) be the empirical mean of the rewards, and r(s,a)r(s,a) the true expected reward. Then, for any ε>0 >0, conditional on N(s,a)N(s,a) we have Pr(|r¯(s,a)−r(s,a)|>ε)≤ 2exp(−2ε2N(s,a)) (| r(s,a)-r(s,a)|> )\;≤\;2 \! (-2\, ^2N(s,a) ) Proof. Since the rewards are independently sampled from identical distribution ν(⋅|s,a)ν(·|s,a), this lemma can be obtained using Hoeffding’s inequality. ∎ C.3 Concentration of empirical transitions Lemma C.4 (Concentration of empirical transitions). Fix any state s and action a∈(s)a (s). For each s′∈(s,a)s (s,a) let N(s′)N(s ) be the number of observed transitions from (s,a)(s,a) to s′s and recall that P^(s′∣s,a):=N(s′)/N(s,a) P(s s,a):=N(s )/N(s,a). Then, for any ε>0 >0, conditional on N(s,a)N(s,a) we have Pr(maxs′∈(s,a)|P^(s′∣s,a)−P(s′∣s,a)|>ε)≤ 2exp(−12ε2N(s,a)). \! ( _s (s,a) | P(s s,a)-P(s s,a) |> )\;≤\;2 \! (- 12\, ^2N(s,a) ). Proof. Fix (s,a)(s,a) and condition on N(s,a)=n>0N(s,a)=n>0. Each time VarDE–MCTS visits (s,a)(s,a), the next state is drawn from the true kernel P(⋅∣s,a)P(· s,a). The visit times are chosen adaptively by the tree policy, but given n the n successor states of (s,a)(s,a) are i.i.d. with distribution P(⋅∣s,a)P(· s,a). Hence we may work with an i.i.d. sample of size n. Enumerate the (finite) successor set as (s,a)=s1,…,sm.S(s,a)=\s_1,…,s_m\. For j=1,…,nj=1,…,n, let Yj∈1,…,mY_j∈\1,…,m\ be the index of the j-th observed successor of (s,a)(s,a): Yj=k⟺the j-th successor is sk.Y_j=k $j$-th successor is s_k. Then Y1,…,YnY_1,…,Y_n are i.i.d. and Pr(Y1=k)=P(sk∣s,a),k=1,…,m. (Y_1=k)=P(s_k s,a), k=1,…,m. By construction, N(sk)=∑j=1nYj=k,P^(sk∣s,a)=N(sk)n=1n∑j=1nYj=k.N(s_k)= _j=1^n1\Y_j=k\, P(s_k s,a)= N(s_k)n= 1n _j=1^n1\Y_j=k\. Step 1: Empirical and true CDFs. Define the true CDF F(x):=Pr(Y1≤x),1≤x≤m,F(x):= (Y_1≤ x), 1≤ x≤ m, and the empirical CDF Fn(x):=1n∑j=1nYj≤x,1≤x≤m.F_n(x):= 1n _j=1^n1\Y_j≤ x\, 1≤ x≤ m. For integers k=1,…,mk=1,…,m, F(k)=∑j=1kP(sj∣s,a),Fn(k)=∑j=1kP^(sj∣s,a).F(k)= _j=1^kP(s_j s,a), F_n(k)= _j=1^k P(s_j s,a). Step 2: DKW inequality. By the Dvoretzky-Kiefer-Wolfowitz inequality (Dvoretzky et al. 1956), for any δ>0δ>0, Pr(sup1≤x≤m|Fn(x)−F(x)|>δ)≤ 2exp(−2nδ2). \! ( _1≤ x≤ m |F_n(x)-F(x) |>δ )\;≤\;2 \! (-2nδ^2 ). (C.1) Step 3: From CDF errors to mass-function errors. For each k=1,…,mk=1,…,m we can write the probability masses using the CDFs: P(sk∣s,a)=F(k)−F(k−1),P^(sk∣s,a)=Fn(k)−Fn(k−1),P(s_k s,a)=F(k)-F(k-1), P(s_k s,a)=F_n(k)-F_n(k-1), with the convention F(0)=Fn(0)=0F(0)=F_n(0)=0. Therefore |P^(sk∣s,a)−P(sk∣s,a)| | P(s_k s,a)-P(s_k s,a) | =|[Fn(k)−Fn(k−1)]−[F(k)−F(k−1)]| = |\,[F_n(k)-F_n(k-1)]-[F(k)-F(k-1)]\, | ≤|Fn(k)−F(k)|+|Fn(k−1)−F(k−1)| ≤ |F_n(k)-F(k) |+ |F_n(k-1)-F(k-1) | ≤2sup1≤x≤m|Fn(x)−F(x)|. ≤ 2 _1≤ x≤ m |F_n(x)-F(x) |. Taking the maximum over k yields max1≤k≤m|P^(sk∣s,a)−P(sk∣s,a)|≤ 2sup1≤x≤m|Fn(x)−F(x)|. _1≤ k≤ m | P(s_k s,a)-P(s_k s,a) |\;≤\;2 _1≤ x≤ m |F_n(x)-F(x) |. Step 4: Plug DKW with ε/2 /2. Let ε>0 >0. From the previous display we have the inclusion of events max1≤k≤m|P^(sk∣s,a)−P(sk∣s,a)|>ε⊆sup1≤x≤m|Fn(x)−F(x)|>ε2. \ _1≤ k≤ m | P(s_k s,a)-P(s_k s,a) |> \\; \; \ _1≤ x≤ m |F_n(x)-F(x) |> 2 \. Taking probabilities and applying (C.1) with δ=ε/2δ= /2 gives Pr(max1≤k≤m|P^(sk∣s,a)−P(sk∣s,a)|>ε)≤Pr(sup1≤x≤m|Fn(x)−F(x)|>ε2)≤2exp(−12ε2n). \! ( _1≤ k≤ m | P(s_k s,a)-P(s_k s,a) |> )≤ \! ( _1≤ x≤ m |F_n(x)-F(x) |> 2 )≤ 2 \! (- 12\, ^2n ). Replacing n by N(s,a)N(s,a) yields the claimed inequality. ∎ C.4 Induction through the search tree Lemma C.5. Consider an VarDE–MCTS process and a state–action pair (st,at)∈×(s_t,a_t) ×A. Assume that for every st+1∈∪a∈(st)(st,a)s_t+1∈ _a (s_t)S(s_t,a) and every fixed εt+1>0 _t+1>0, there exist constants Cst+1>0C_s_t+1>0 and kst+1(εt+1)>0k_s_t+1( _t+1)>0 such that Pr(|V^(st+1)−V∗(st+1)|>εt+1)≤Cst+1exp(−kst+1(εt+1)εt+12N(st+1)), \! ( | V(s_t+1)-V^*(s_t+1) |> _t+1 )\;≤\;C_s_t+1 \! (-k_s_t+1( _t+1) _t+1^2\,N(s_t+1) ), then, for every fixed ε>0 >0, there exist constants C>0C>0 and kε>0k_ >0 such that Pr(|Q^(st,at)−Q∗(st,at)|>ε)≤Cexp(−kεε2N(st,at)). \! ( | Q(s_t,a_t)-Q^*(s_t,a_t) |> )\;≤\;C \! (-k_ \, ^2\,N(s_t,a_t) ). Proof. By the assumption, Lemma C.1 and a union bound over st+1∈(st,at)s_t+1 (s_t,a_t), for every fixed ε1>0 _1>0 there exist constants C1>0C_1>0 and k1(ε1)>0k_1( _1)>0 such that Pr(ξ1)≥ 1−C1exp(−k1(ε1)ε12N(st,at)), ( _1)\ ≥\ 1-C_1 \! (-k_1( _1) _1^2\,N(s_t,a_t) ), with ξ1=∀st+1∈(st,at):|V^(st+1)−V∗(st+1)|≤ε1.with _1= \∀ s_t+1 (s_t,a_t):\ | V(s_t+1)-V^*(s_t+1) |≤ _1 \. Moreover, by Lemma C.4, there exist constants C2,k2>0C_2,k_2>0 such that for any ε2>0 _2>0, Pr(ξ2)≥ 1−C2exp(−k2ε22N(st,at)), ( _2)\ ≥\ 1-C_2 \! (-k_2 _2^2\,N(s_t,a_t) ), with ξ2=maxst+1∈(st,at)|N(st+1)N(st,at)−P(st+1∣st,at)|≤ε2.with _2= \ _s_t+1 (s_t,a_t) | N(s_t+1)N(s_t,a_t)-P(s_t+1 s_t,a_t) |≤ _2 \. Also, by Lemma C.3, there exist constants C3,k3>0C_3,k_3>0 such that for any ε3>0 _3>0, Pr(ξ3)≥ 1−C3exp(−k3ε32N(st,at)), ( _3)\ ≥\ 1-C_3 \! (-k_3 _3^2\,N(s_t,a_t) ), with ξ3=|r¯(st,at)−r(st,at)|≤ε3. with _3= \ | r(s_t,a_t)-r(s_t,a_t) |≤ _3 \. Under the event ξ1∩ξ2∩ξ3 _1∩ _2∩ _3, we have Q^(st,at) Q(s_t,a_t) =r¯(st,at)+∑st+1∈(st,at)N(st+1)N(st,at)V^(st+1) = r(s_t,a_t)+ _s_t+1 (s_t,a_t) N(s_t+1)N(s_t,a_t)\, V(s_t+1) ≤r(st,at)+ε3+∑st+1(P(st+1∣st,at)+ε2)(V∗(st+1)+ε1) ≤ r(s_t,a_t)+ _3+ _s_t+1 (P(s_t+1 s_t,a_t)+ _2 ) (V^*(s_t+1)+ _1 ) =r(st,at)+∑st+1P(st+1∣st,at)V∗(st+1)+ε2∑st+1V∗(st+1) =r(s_t,a_t)+ _s_t+1P(s_t+1 s_t,a_t)V^*(s_t+1)\;+\; _2 _s_t+1V^*(s_t+1) +ε1∑st+1P(st+1∣st,at)+ε1ε2|(st,at)|+ε3 +\; _1 _s_t+1P(s_t+1 s_t,a_t)\;+\; _1 _2\,|S(s_t,a_t)|\;+\; _3 =Q∗(st,at)+ε2∑st+1V∗(st+1)+ε1+ε3+ε1ε2|(st,at)|. =Q^*(s_t,a_t)\;+\; _2 _s_t+1V^*(s_t+1)\;+\; _1+ _3\;+\; _1 _2\,|S(s_t,a_t)|. and similarly, by the corresponding lower bounds, Q^(st,at)≥Q∗(st,at)−ε2∑st+1V∗(st+1)−ε1−ε3+ε1ε2|(st,at)|. Q(s_t,a_t)≥ Q^*(s_t,a_t)\;-\; _2 _s_t+1V^*(s_t+1)\;-\; _1- _3\;+\; _1 _2\,|S(s_t,a_t)|. For any ε>0 >0, set ε1=ε3=ε4,ε2=minε4(1+∑st+1V∗(st+1)),1|(st,at)|. _1= _3= 4, _2= \! \ 4 (1+ _s_t+1V^*(s_t+1) ), 1|S(s_t,a_t)| \. then give |Q^(st,at)−Q∗(st,at)|≤ε. | Q(s_t,a_t)-Q^*(s_t,a_t) |≤ . Since ξ1∩ξ2∩ξ3→|Q^(st,at)−Q∗(st,at)|≤ε _1∩ _2∩ _3→ | Q(s_t,a_t)-Q^*(s_t,a_t) |≤ , we have |Q^(st,at)−Q∗(st,at)|>ε→¬(ξ1∩ξ2∩ξ3) | Q(s_t,a_t)-Q^*(s_t,a_t) |> → ( _1∩ _2∩ _3). Taking probabilities gives Pr(|Q^(st,at)−Q∗(st,at)|>ε) \! ( | Q(s_t,a_t)-Q^*(s_t,a_t) |> ) ≤Pr(¬(ξ1∩ξ2∩ξ3)) ≤ \! ( ( _1∩ _2∩ _3) ) =Pr(¬ξ1∪¬ξ2∪¬ξ3) = ( _1∪ _2∪ _3) ≤Pr(¬ξ1)+Pr(¬ξ2)+Pr(¬ξ3) ≤ ( _1)+ ( _2)+ ( _3) ≤C1exp(−k1(ε1)ε12N(st,at)) ≤ C_1 \! (-k_1( _1) _1^2\,N(s_t,a_t) ) +C2exp(−k2ε22N(st,at)) +C_2 \! (-k_2 _2^2\,N(s_t,a_t) ) +C3exp(−k3ε32N(st,at)) +C_3 \! (-k_3 _3^2\,N(s_t,a_t) ) ≤Cexp(−kεε2N(st,at)). ≤ C \! (-k_ \, ^2\,N(s_t,a_t) ). After fixing ε , the auxiliary tolerances ε1,ε2,ε3 _1, _2, _3 are fixed as well. Thus one may take C=C1+C2+C3,kε=mink1(ε/4)16,k2(ε2ε)2,k316>0.C=C_1+C_2+C_3, k_ = \! \ k_1( /4)16,k_2 ( _2 )^2, k_316 \>0. This concludes the proof. ∎ Lemma C.6. Consider an VarDE–MCTS process. Fix a depth t∈1,…,Ht∈\1,…,H\ and a node st∈s_t . If for every successor state st+1∈∪a∈(st)(st,a)s_t+1∈ _a (s_t)S(s_t,a) and every fixed εst+1>0 _s_t+1>0, there exist constants Cst+1>0C_s_t+1>0 and kst+1(εst+1)>0k_s_t+1( _s_t+1)>0 such that Pr(|V^(st+1)−V∗(st+1)|>εst+1)≤Cst+1exp(−kst+1(εst+1)εst+12N(st+1)), \! ( | V(s_t+1)-V^*(s_t+1) |> _s_t+1 )\;≤\;C_s_t+1 \! (-k_s_t+1( _s_t+1)\, _s_t+1^2\,N(s_t+1) ), then, for every fixed ε>0 >0, there exist constants C>0C>0 and kε>0k_ >0 such that Pr(|V^(st)−V∗(st)|>ε)≤Cexp(−kεε2N(st)). \! ( | V(s_t)-V^*(s_t) |> )\;≤\;C \! (-k_ \, ^2\,N(s_t) ). Proof. Apply Lemma C.5 to each action a∈(st)a (s_t) and combine with Lemma C.1 to convert the N(st,a)N(s_t,a)-rate into an N(st)N(s_t)-rate; then union bound over a∈(st)a (s_t). Concretely, for every fixed ε1>0 _1>0 there exist constants C1>0C_1>0 and k1(ε1)>0k_1( _1)>0 such that Pr(ξ)≥ 1−C1exp(−k1(ε1)ε12N(st)), (ξ)\;≥\;1-C_1 \! (-k_1( _1) _1^2\,N(s_t) ), with ξ=∀a∈(st):|Q^(st,a)−Q∗(st,a)|≤ε1. with ξ= \∀ a (s_t):\; | Q(s_t,a)-Q^*(s_t,a) |≤ _1 \. Fix ε>0 >0 and set ε1=ε _1= . On the event ξ, |V^(st)−V∗(st)|=|maxa∈(st)Q^(st,a)−maxa∈(st)Q∗(st,a)|≤maxa∈(st)|Q^(st,a)−Q∗(st,a)|≤ε. | V(s_t)-V^*(s_t) |= | _a (s_t) Q(s_t,a)- _a (s_t)Q^*(s_t,a) |≤ _a (s_t) | Q(s_t,a)-Q^*(s_t,a) |≤ . Thus ξ→|V^(st)−V∗(st)|≤εξ→\| V(s_t)-V^*(s_t)|≤ \, and therefore Pr(|V^(st)−V∗(st)|>ε)≤Pr(¬ξ)≤C1exp(−k1(ε)ε2N(st)). \! ( | V(s_t)-V^*(s_t) |> )≤ ( ξ)≤ C_1 \! (-k_1( ) ^2\,N(s_t) ). Taking C=C1C=C_1 and kε=k1(ε)k_ =k_1( ) concludes the proof. ∎ Theorem C.7 (VarDE–MCTS value estimates). Consider a VarDE–MCTS process. For any depth t∈0,…,Ht∈\0,…,H\, any node sts_t, and any fixed tolerance ε>0 >0, there exist constants Cst,ε>0C_s_t, >0 and kst,ε>0k_s_t, >0 such that, conditionally on N(st)=n≥1N(s_t)=n≥ 1, Pr(|V^(st)−V∗(st)|>ε)≤Cst,εexp(−kst,εε2n). \! ( | V(s_t)-V^*(s_t) |> )≤ C_s_t, \! (-k_s_t, \, ^2n ). Moreover, at the root node s0s_0, after T simulations, there exist constants Cε>0C_ >0 and kε>0k_ >0 such that Pr(|V^(s0)−V∗(s0)|>ε)≤Cεexp(−kεε2T). \! ( | V(s_0)-V^*(s_0) |> )≤ C_ \! (-k_ \, ^2T ). Proof. Fix ε>0 >0. The result holds for t=H+1t=H+1 since V^(sH+1)=V∗(sH+1)=0 V(s_H+1)=V^*(s_H+1)=0. Hence the conditional node-wise bound holds for all depths t=0,…,Ht=0,…,H by backward induction using Lemma C.6. At the root, after T simulations we have N(s0)=TN(s_0)=T, which gives the displayed root bound. Since ε>0 >0 was arbitrary, the claim follows. ∎ Corollary C.8 (VarDE–MCTS root error probability). Assume the conditions of Theorem C.7 hold. Suppose the optimal root action a∗=argmaxaQ∗(s0,a)a^*\;=\; _aQ^*(s_0,a) is unique, and define the optimality gap Δmin:=mina≠a∗(Q∗(s0,a∗)−Q∗(s0,a))> 0. _ \;:=\; _a≠ a^* (Q^*(s_0,a^*)-Q^*(s_0,a) )\;>\;0. Let a^T=argmaxaQ^T(s0,a) a_T= _a Q_T(s_0,a) be the action recommended by VarDE–MCTS after T simulations. Then there exist constants c,C>0c,C>0 such that Pr(a^T≠a∗)≤Cexp(−cT). \! ( a_T≠ a^* )\;≤\;C (-cT). Proof. By Theorem C.7, for every fixed ε>0 >0 there exist constants c1(ε),C1>0c_1( ),C_1>0 such that Pr(|V^(s1)−V∗(s1)|>ε)≤C1exp(−c1(ε)ε2N(s1)). \! ( | V(s_1)-V^*(s_1) |> )≤ C_1 (-c_1( ) ^2N(s_1) ). Lemma C.5 implies that exponential concentration of the value estimates propagates to the root action–value estimates. In particular, for each fixed ε>0 >0 and each root action a, there exist constants c2(ε),C2>0c_2( ),C_2>0 such that Pr(|Q^(s0,a)−Q∗(s0,a)|>ε)≤C2exp(−c2(ε)ε2N(s0,a)). \! ( | Q(s_0,a)-Q^*(s_0,a) |> )≤ C_2 (-c_2( ) ^2N(s_0,a) ). Using Lemma C.1, for each fixed ε>0 >0 there exist constants c3(ε),C3>0c_3( ),C_3>0 such that for any root action a, Pr(|Q^(s0,a)−Q∗(s0,a)|>ε)≤C3exp(−c3(ε)ε2T). \! ( | Q(s_0,a)-Q^*(s_0,a) |> )≤ C_3 (-c_3( ) ^2T ). Set ε=Δmin/2 = _ /2, and define the event ℰT:=⋂a|Q^(s0,a)−Q∗(s0,a)|≤Δmin2.E_T:= _a \ | Q(s_0,a)-Q^*(s_0,a) |≤ _ 2 \. On the event ℰTE_T, for any suboptimal action a≠a∗a≠ a^*, Q^(s0,a∗)≥Q∗(s0,a∗)−Δmin2>Q∗(s0,a)+Δmin2≥Q^(s0,a), Q(s_0,a^*)≥ Q^*(s_0,a^*)- _ 2>Q^*(s_0,a)+ _ 2≥ Q(s_0,a), which implies a^T=a∗ a_T=a^*. Therefore, Pr(a^T≠a∗)≤Pr(ℰTc)≤∑aPr(|Q^T(s0,a)−Q∗(s0,a)|>Δmin2). ( a_T≠ a^*)≤ (E_T^c)≤ _a \! ( | Q_T(s_0,a)-Q^*(s_0,a) |> _ 2 ). Applying the exponential concentration bound from Lemma C.5 and absorbing the finite number of root actions into the constants yields Pr(a^T≠a∗)≤Cexp(−cT), ( a_T≠ a^*)≤ C (-cT), which concludes the proof. ∎ Appendix D Proofs for Subsection 4.3 (VarDE–Q-learning) D.1 Proof of Lemma 4.10 (Coverage) Proof. Fix any state s∈s and let NT(s):=∑t=1Tst=s,NT(s,a):=∑t=1T(st,at)=(s,a).N_T(s):= _t=1^T1\s_t=s\, N_T(s,a):= _t=1^T1\(s_t,a_t)=(s,a)\. Step 1 (Min-pulls at each state, VarDE–BAI on the subsequence). Let τs(1)<τs(2)<⋯ _s(1)< _s(2)<·s be the (random) times at which st=s_t=s. On this subsequence, define the per-state pull count N~k(s)(a):=∑j=1kaτs(j)=a. N_k^(s)(a):= _j=1^k1\a_ _s(j)=a\. ⇒N~k(s)(a)=Nτs(k)(s,a)andk=Nτs(k)(s). N_k^(s)(a)=N_ _s(k)(s,a) k=N_ _s(k)(s). At each visit to s, VarDE–Q-learning selects an action by maximizing w(s,a)2σ~2(s,a)N(s,a)(N(s,a)+1) w(s,a)^2 σ^2(s,a)N(s,a)(N(s,a)+1) (with the convention that the score is ∞ when N(s,a)=0N(s,a)=0), which provides a warm-start η=1η=1 on the per-state bandit with arms (s)A(s). Moreover, since r∈[0,1]r∈[0,1] and the TD target satisfies yt=r^t+γmaxbQ^(st+1,b)∈[0,Hγ]y_t= r_t+γ _b Q(s_t+1,b)∈[0,H_γ] with Hγ=11−γH_γ= 11-γ, and the Q-update is a convex combination of the previous value and yty_t, we have Q^(s,a)∈[0,Hγ] Q(s,a)∈[0,H_γ] for all (s,a)(s,a). Hence the weights satisfy w(s,a)=eQ^(s,a)/τ∑b∈(s)eQ^(s,b)/τ=e(Q^(s,a)/Hγ)/(τ/Hγ)∑b∈(s)e(Q^(s,b)/Hγ)/(τ/Hγ),w(s,a)= e Q(s,a)/τ _b (s)e Q(s,b)/τ= e^( Q(s,a)/H_γ)/(τ/H_γ) _b (s)e^( Q(s,b)/H_γ)/(τ/H_γ), i.e., the per-state decision rule is exactly VarDE–BAI applied to normalized means Q^(⋅,⋅)/Hγ∈[0,1] Q(·,·)/H_γ∈[0,1] with temperature τ′:=τ/Hγτ :=τ/H_γ. Therefore, applying Lemma B.2 to the per-state bandit (with K=|(s)|K=|A(s)|, total pulls T=kT=k, warm-start η=1η=1, and temperature τ′τ ), for any k>|(s)|k>|A(s)| and any a∈(s)a (s), N~k(s)(a)≥ 2e−1/τ′σ¯(k|(s)|−12)−12=2e−Hγ/τσ¯(k|(s)|−12)−12. N_k^(s)(a)\;≥\;2e^-1/τ σ ( k|A(s)|- 12 )- 12=2e^-H_γ/τ σ ( k|A(s)|- 12 )- 12. Equivalently, for any time T such that NT(s)>|(s)|N_T(s)>|A(s)|, NT(s,a)≥ 2e−Hγ/τσ¯(NT(s)|(s)|−12)−12,∀a∈(s).N_T(s,a)\;≥\;2e^-H_γ/τ σ ( N_T(s)|A(s)|- 12 )- 12, ∀ a (s). (D.1) In particular, if NT(s)→∞N_T(s)→∞, then NT(s,a)→∞N_T(s,a)→∞ for every a∈(s)a (s). Step 2 (All states are visited infinitely often). Let ℛR be the set of states visited infinitely often: ℛ:=s∈:NT(s)→∞ as T→∞.R:= \s :N_T(s)→∞ as T→∞ \. Since ||<∞|S|<∞ and the process runs forever, ℛ≠∅R≠ almost surely. We claim that ℛR is closed under one-step reachability of any action: if s∈ℛs , a∈(s)a (s), and P(s′∣s,a)>0P(s s,a)>0, then s′∈ℛs almost surely. Indeed, s∈ℛs implies NT(s)→∞N_T(s)→∞, and then (D.1) gives NT(s,a)→∞N_T(s,a)→∞. Let t1<t2<⋯t_1<t_2<·s be the times when (stn,atn)=(s,a)(s_t_n,a_t_n)=(s,a). At each such time, conditionally on the past, stn+1s_t_n+1 is drawn from P(⋅∣s,a)P(· s,a), so Pr(stn+1=s′∣ℱtn)=P(s′∣s,a)=:p>0. \! (s_t_n+1=s _t_n )=P(s s,a)=:p>0. Since there are infinitely many such trials with success probability p>0p>0, stn+1=s′s_t_n+1=s occurs infinitely often almost surely, which implies NT(s′)→∞N_T(s )→∞, i.e., s′∈ℛs . Thus, for every s∈ℛs and every a∈(s)a (s), all states in the support of P(⋅∣s,a)P(· s,a) also belong to ℛR. In other words, ℛR is closed under all actions. Now take any s∈ℛs and any s′∈s . By Assumption 4.9, there exists a stationary policy π such that sπ[Ts′]<∞ _s^π[T_s ]<∞, hence Prsπ(Ts′<∞)=1 _s^π(T_s <∞)=1, so there exists some finite m with Prsπ(Ts′=m)>0 _s^π(T_s =m)>0. Therefore there exists a length-m path s=s0→a0s1→a1⋯→am−1sm=s′s=s_0 a_0s_1 a_1·s a_m-1s_m=s such that π(ak∣sk)>0π(a_k s_k)>0 and P(sk+1∣sk,ak)>0P(s_k+1 s_k,a_k)>0 for all k. Since ℛR is closed under all action transitions and s0∈ℛs_0 , it follows inductively that s1,…,sm∈ℛs_1,…,s_m , in particular s′∈ℛs . Because s′∈s was arbitrary, we conclude ℛ=R=S almost surely, i.e., NT(s)→∞for all s∈N_T(s)→∞ all s . Step 3 (Coverage over state–action pairs). Finally, combining NT(s)→∞N_T(s)→∞ for all s with (D.1) yields NT(s,a)→∞N_T(s,a)→∞ for all (s,a)(s,a) almost surely, proving the lemma. ∎ Appendix E Full Algorithms E.1 VarDE–BAI Algorithm 1 VarDE–BAI Parameters: temperature τ, warm-start η, variance floor σ¯2 σ^2, budget T Initialize: (Ni,μ^i,σ^i2)←(0,0,0)(N_i, μ_i, σ_i^2)←(0,0,0) ∀i∀ i for t=0t=0 to Kη−1Kη-1 do Pull arm i~t=t mod K i_t=t mod K; observe rtr_t; update Ni~tN_ i_t, μ^i~t μ_ i_t, σ^i~t2 σ_ i_t^2 by Welford (Alg. 4) end for for t=Kηt=Kη to T−1T-1 do wi(μ^)←exp(μ^i/τ)∑jexp(μ^j/τ)w_i( μ)← ( μ_i/τ) _j ( μ_j/τ), σ~i2←maxσ^i2,σ¯2 σ_i^2← \ σ_i^2, σ^2\ ∀i∀ i Select arm i~t=argmaxiwi(μ^)2σ~i2Ni(Ni+1) i_t= _i w_i( μ)^2 σ_i^2N_i(N_i+1); observe rtr_t Update Ni~tN_ i_t, μ^i~t μ_ i_t, σ^i~t2 σ_ i_t^2 by Welford (Alg. 4) end for return i^T=argmaxiμ^i i_T= _i μ_i E.2 VarDE–MCTS Algorithm 2 VarDE–MCTS Input: root state s0s_0, budget T, temperature τ, variance floor σ¯2 σ^2 Output: recommended action a^T a_T function SelectChild(s) for a∈(s)a (s) do w(s,a)←exp(Q^(s,a)/τ)∑bexp(Q^(s,b)/τ)w(s,a)← ( Q(s,a)/τ) _b ( Q(s,b)/τ) σ~(s,a)←maxσ^(s,a),σ¯ σ(s,a)← \ σ(s,a), σ\ end for return argmaxaw(s,a)2σ~2(s,a)N(s,a)(N(s,a)+1) _a w(s,a)^2\, σ^2(s,a)N(s,a)(N(s,a)+1) end function function ExpandSimulate(s) Add an unsampled action a to node s Rollout from (s,a)(s,a) to depth H to get return G G Update Q^(s,a)←G Q(s,a)← G; N(s,a)←N(s,a)+1N(s,a)← N(s,a)+1 V^(s)←maxaQ^(s,a) V(s)← _a Q(s,a) return G G end function function Backpropagate(path, G G) while path not empty do Pop last (s,a,r^)(s,a, r) from path G^←r^+γG G← r+γ G Update σ^2(s,a) σ^2(s,a) from G G by Welford (Alg. 4) Q^(s,a)←r¯(s,a)+γ∑s′N(s′)N(s,a)V^(s′) Q(s,a)← r(s,a)+γ _s N(s )N(s,a) V(s ) V^(s)←maxaQ^(s,a) V(s)← _a Q(s,a) end while end function function MainLoop(s0s_0) for t=1,…,Tt=1,…,T do s←s0s← s_0; path←[]←[\ ] while s is not expandable do a←SelectChild(s)a← SelectChild(s) Observe r^∼ν(⋅|s,a) r ν(·|s,a) r¯(s,a)←N(s,a)r¯(s,a)+r^N(s,a)+1 r(s,a)← N(s,a) r(s,a)+ rN(s,a)+1 N(s)←N(s)+1N(s)← N(s)+1; N(s,a)←N(s,a)+1N(s,a)← N(s,a)+1 Transition s′∼P(⋅|s,a)s P(·|s,a) Append (s,a,r^)(s,a, r) to path; s←s′s← s end while G^←ExpandSimulate(s) G← ExpandSimulate(s) Backpropagate(path, G G) end for return a^T=argmaxaQ^(s0,a) a_T= _a Q(s_0,a) end function E.3 VarDE–Q-learning Algorithm 3 VarDE–Q-learning Parameters: budget T, discount γ, temperature τ, variance floor σ¯2 σ^2, initial state s0s_0 Initialize: Q(s,a)←11−γQ(s,a)← 11-γ, σ^2(s,a)←0 σ^2(s,a)← 0, N(s,a)←0N(s,a)← 0 ∀(s,a)∀(s,a); Hγ←11−γH_γ← 11-γ; s←s0s← s_0 for t=1,…,Tt=1,…,T do w(s,b)←exp(Q(s,b)/τ)∑c∈(s)exp(Q(s,c)/τ)w(s,b)← (Q(s,b)/τ) _c (s) (Q(s,c)/τ), ∀b∈(s)∀ b (s) σ~2(s,b)←maxσ^2(s,b),σ¯2 σ^2(s,b)← \ σ^2(s,b), σ^2\, ∀b∈(s)∀ b (s) Take action a←argmaxb∈(s)w(s,b)2σ~2(s,b)N(s,b)(N(s,b)+1)a← _b (s) w(s,b)^2\, σ^2(s,b)N(s,b)(N(s,b)+1) Observe reward r r and next state s′s y←r^+γmaxbQ(s′,b)y← r+γ _bQ(s ,b) Update N(s,a)N(s,a), σ^(s,a)2 σ(s,a)^2 by Welford on samples of y (Alg. 4) α←Hγ+1Hγ+N(s,a)α← H_γ+1H_γ+N(s,a); Q(s,a)←(1−α)Q(s,a)+αyQ(s,a)←(1-α)Q(s,a)+α y; s←s′s← s end for return π^T(⋅)=argmaxaQ(⋅,a) π_T(·)= _aQ(·,a) E.4 Implementation details Division by N(s,a)=0N(s,a)=0. The VarDE score w(s,a)2σ~2(s,a)N(s,a)(N(s,a)+1) w(s,a)^2 σ^2(s,a)N(s,a)(N(s,a)+1) is set to +∞+∞ when N(s,a)=0N(s,a)=0. This ensures that all actions are tried at least once before the algorithm starts exploiting the variance estimates. Expandable node definition in MCTS. An expandable node is defined as a state node s where there exists at least one action a∈(s)a (s) such that N(s,a)=0N(s,a)=0. Welford method for empirical mean and variance update. We use Welford method to update empirical mean and variance online. The method’s pseudo code can be seen in Algorithm 4. Algorithm 4 Welford update for empirical mean and variance Input: count N≥0N≥ 0, mean μ μ, variance σ^2 σ^2, new sample x M2←Nσ^2M_2← N σ^2 N←N+1N← N+1 δ←x−μ^δ← x- μ μ^←μ^+δ/N μ← μ+δ/N δ2←x−μ _2← x- μ M2←M2+δδ2M_2← M_2+δ\, _2 σ^2←M2/N σ^2← M_2/N return (N,μ^,σ^2)(N, μ, σ^2) Appendix F Experimental Details F.1 BAI Experiments We evaluate VarDE–BAI on the four following standard Best-Arm Identification (BAI) benchmarks. • Experiment BAI.1: One group of bad arms. Bernoulli distributions. 20 arms. μ0=0.2 _0=0.2, μ1:19=0.1 _1:19=0.1. T=1200T=1200. • Experiment BAI.2: Two groups of bad arms. Bernoulli distributions. 20 arms. μ0=0.2 _0=0.2, μ1:5=0.12 _1:5=0.12, μ6:19=0.08 _6:19=0.08. T=1000T=1000. • Experiment BAI.3: Geometric progression. Gaussian distributions. 14 arms. μ0=0.4 _0=0.4, μi=0.4−0.9i+9 _i=0.4-0.9^i+9 for all i=1,…,13i=1,…,13. σi _i is shuffled from μi _i. T=200T=200. • Experiment BAI.4: Ten arms divided in three groups. Gaussian distributions. 10 arms. μ0=0.3 _0=0.3, μ1:3=0.22 _1:3=0.22, μ4:6=0.2 _4:6=0.2, μ7:9=0.15 _7:9=0.15. σi _i is shuffled from μi _i. T=150T=150. Besides the error probability at the last pull presented in Table 2, below are additional results showing the evolution of the error probability over time. Figure 5: Error probability over time for Experiments BAI.1 to BAI.4. We also provide empirical comparisons of VarDE–BAI with different decision functions on two additional BAI experiments: • Experiment BAI.5: Arithmetic progression. Gaussian distributions. 15 arms. μi=0.4−0.025i _i=0.4-0.025i for all i=0,…,14i=0,…,14. σi _i is shuffled from μi _i. T=2000T=2000. • Experiment BAI.6: Two good arms and a large group of bad arms. Gaussian distributions. 20 arms. μ0=0.3 _0=0.3, μ1=0.28 _1=0.28, μ2:19=0.17 _2:19=0.17. σi _i is shuffled from μi _i. T=2000T=2000. Below are the implemented decision potentials Y(x)Y(x) and their derivatives w(x)=∇Y(x)w(x)=∇ Y(x) used by VarDE–BAI. In our experiments, we use τ=0.05τ=0.05 (LogSumExp), μ=0.5μ=0.5 (Nesterov), (α,μ)=(2,0.1)(α,μ)=(2,0.1) (EntMax), δ=0.1δ=0.1 (Pairwise Softplus), and p=5p=5 (Power Mean). • LogSumExp (temperature τ): Yτ(x)=τlog(∑i=1Kexp(xi/τ)),wi(x)=exp(xi/τ)∑j=1Kexp(xj/τ).Y_τ(x)=τ ( _i=1^K (x_i/τ) ), w_i(x)= (x_i/τ) _j=1^K (x_j/τ). • Nesterov (quadratic smoothing μ): Yμ(x)=maxp∈ΔK⟨p,x⟩−μ2‖p‖22,w(x)=∇Yμ(x)=ΠΔK(x/μ),Y_μ(x)= _p∈ _K \ p,x - μ2\|p\|_2^2 \, w(x)=∇ Y_μ(x)= _ _K(x/μ), where ΠΔK _ _K denotes Euclidean projection onto the probability simplex. • EntMax (Tsallis / α-entmax smoothing): Yα,μ(x)=maxp∈ΔK⟨p,x⟩−μα(α−1)∑i=1Kpiα,w(x)=∇Yα,μ(x)=argmaxp∈ΔK(⋅).Y_α,μ(x)= _p∈ _K \ p,x - μα(α-1) _i=1^Kp_i^α \, w(x)=∇ Y_α,μ(x)= _p∈ _K(·). Equivalently (as implemented), there exists a threshold θ∈ℝθ such that wi(x)∝[c(xi−θ)]+1α−1,c=(α−1μα)1α−1,∑i=1Kwi(x)=1.w_i(x) [c\,(x_i-θ) ]_+ 1α-1, c= ( α-1μα ) 1α-1, _i=1^Kw_i(x)=1. • Pairwise Softplus (pairwise smooth-max, parameter δ): Define, for a,b∈ℝa,b , mδ(a,b)=a+b2+(a−b2)2+δ2.m_δ(a,b)= a+b2+ ( a-b2 )^2+δ^2. Its partial derivatives are ∂mδ∂a(a,b)=12+a−b2(a−b2)2+δ2,∂mδ∂b(a,b)=1−∂mδ∂a(a,b). ∂ m_δ∂ a(a,b)= 12+ a-b2 ( a-b2 )^2+δ^2, ∂ m_δ∂ b(a,b)=1- ∂ m_δ∂ a(a,b). For x∈ℝKx ^K, Yδ(x)Y_δ(x) is obtained by repeatedly merging pairs using mδm_δ (in a balanced binary-tree order), and w(x)=∇Yδ(x)w(x)=∇ Y_δ(x) is obtained by backpropagating these pairwise derivatives (yielding w(x)∈ΔKw(x)∈ _K). • Power Mean (order p>1p>1): Let x~i=xi x_i=x_i if minjxj>0 _jx_j>0, and otherwise x~i=xi−minjxj+ε x_i=x_i- _jx_j+ (with ε=10−8 =10^-8 in code). Define Yp(x)=(1K∑i=1Kx~ip)1/p.Y_p(x)= ( 1K _i=1^K x_i^p )^1/p. Its gradient (ignoring the constant shift used to ensure positivity) satisfies ∂Yp∂xi(x)∝x~ip−1,wi(x)=x~ip−1∑j=1Kx~jp−1(simplex-normalized, as implemented). ∂ Y_p∂ x_i(x) x_i^p-1, w_i(x)= x_i^p-1 _j=1^K x_j^p-1\ \ (simplex-normalized, as implemented). F.1.1 Component ablations and parameter sensitivity We include additional analyses for VarDE–BAI to separate the two factors in the sampling score and to evaluate the sensitivity to the temperature and variance floor. In the component ablation, Var-Only removes the influence weights from the score and uses only the empirical variance term, while Weight-Only removes the empirical variance term and uses only the influence weights. Table 3 shows that both components are useful, and the full influence-weighted variance rule performs best at every checkpoint. Table 3: Component ablation for VarDE–BAI: error probability (%) over time. 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 Table 4 reports error probability over a grid of LSE temperatures τ and variance floors σ¯2 σ^2. The method is more sensitive to τ than to the variance floor. The variance floor mainly stabilizes early variance estimates, and performance near the best temperature is stable over a broad range of floors. Table 4: Sensitivity of VarDE–BAI: error probability (%) across temperature τ and variance floor σ¯2 σ^2. τ / σ¯2 σ^2 10−410^-4 10−310^-3 10−210^-2 10−110^-1 11 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 1.00 22.19 22.00 21.92 19.69 18.86 2.00 24.16 23.76 23.47 21.11 20.16 F.1.2 First-order approximation study To quantify the effect of neglecting higher-order terms, we compare the first-order variance surrogate V1st=∑iwi(μ^)2σ^i2NiV_1st= _iw_i( μ)^2 σ_i^2N_i with the full nonlinear LSE variance Vfull=Var[τlog∑ieμ~i/τ],μ~i∼(μ^i,σ^i2Ni).V_full= \! [τ _ie μ_i/τ ], μ_i \! ( μ_i, σ_i^2N_i ). Tables 5–7 show that for very small τ=0.05τ=0.05, the first-order surrogate significantly underestimates the full variance throughout learning. For τ=0.10τ=0.10, the approximation becomes much tighter as learning progresses. For τ=0.15τ=0.15, the discrepancy is already moderate early on and quickly becomes very small. Table 5: First-order approximation study for τ=0.05τ=0.05. Step VfullV_full V1stV_1st Vfull−V1stV_full-V_1st Vfull−V1stVfull V_full-V_1stV_full 20 1.227×10−21.227× 10^-2 3.838×10−33.838× 10^-3 8.510×10−38.510× 10^-3 66.4% 400 3.659×10−33.659× 10^-3 2.530×10−42.530× 10^-4 3.406×10−33.406× 10^-3 88.7% 600 2.790×10−32.790× 10^-3 1.687×10−41.687× 10^-4 2.622×10−32.622× 10^-3 88.0% 900 1.916×10−31.916× 10^-3 1.027×10−41.027× 10^-4 1.813×10−31.813× 10^-3 84.9% Table 6: First-order approximation study for τ=0.10τ=0.10. Step VfullV_full V1stV_1st Vfull−V1stV_full-V_1st Vfull−V1stVfull V_full-V_1stV_full 20 7.112×10−37.112× 10^-3 2.911×10−32.911× 10^-3 4.201×10−34.201× 10^-3 56.1% 400 3.609×10−43.609× 10^-4 2.398×10−42.398× 10^-4 1.211×10−41.211× 10^-4 21.6% 600 2.157×10−42.157× 10^-4 1.621×10−41.621× 10^-4 5.369×10−55.369× 10^-5 14.4% 900 1.198×10−41.198× 10^-4 1.003×10−41.003× 10^-4 1.963×10−51.963× 10^-5 8.4% Table 7: First-order approximation study for τ=0.15τ=0.15. Step VfullV_full V1stV_1st Vfull−V1stV_full-V_1st Vfull−V1stVfull V_full-V_1stV_full 20 4.644×10−34.644× 10^-3 2.712×10−32.712× 10^-3 1.933×10−31.933× 10^-3 39.5% 400 2.540×10−42.540× 10^-4 2.390×10−42.390× 10^-4 1.534×10−51.534× 10^-5 5.3% 600 1.682×10−41.682× 10^-4 1.617×10−41.617× 10^-4 7.276×10−67.276× 10^-6 3.8% 900 1.026×10−41.026× 10^-4 1.003×10−41.003× 10^-4 3.339×10−63.339× 10^-6 3.0% F.2 MCTS Experiments F.2.1 Experiment MCTS.1 - Sailing environments Environment. The state is (x,y,d)(x,y,d), where (x,y)(x,y) is the agent’s position on a 6×66× 6 grid and d∈0,…,7d∈\0,…,7\ is the current wind direction (8 compass directions). From each state, the agent selects one of the 8 compass moves that stays within the grid and is not directly into the wind. After moving, the wind transitions stochastically: it stays the same with probability 0.60.6, and turns left or right with probability 0.20.2 each. The reward is dense and negative, corresponding to a movement cost that increases with the angle between the action direction and the wind direction. The agent starts at position (0,0)(0,0) and the episode ends when it reaches the goal at position (5,5)(5,5) or when the horizon H=50H=50 is reached. The 8 available wind directions and the applicable actions with their rewards under the blue-direction wind are illustrated in Figure 6. Figure 6: Sailing environment wind directions, applicable actions, and rewards under blue-direction wind. Evaluation protocol. For each algorithm, we run 100100 independent runs. Within each run, we perform MCTS simulations and evaluate the policy induced by the current search tree at fixed checkpoints using Monte Carlo rollouts. If a rollout reaches a state that is not represented in the current tree, the evaluation policy defaults to uniform random actions. We evaluate after every 10001000 simulations, from 10001000 to 3000030000, and estimate performance using 200200 rollouts per checkpoint. Hyperparameter selection. We select hyperparameters by grid search, using 5050 independent runs, 1000010000 MCTS simulations per run, and 200200 evaluation rollouts. For each algorithm, we choose the configuration with the best average Monte Carlo return. The tuned configurations used are: UCT (bias =10=10, ε=0.1 =0.1), MENTS/RENTS/TENTS (temperature =0.1=0.1, ε=0.25 =0.25), DENTS (temperature =2.0=2.0, ε=0.75 =0.75), BTS (temperature =3.0=3.0, ε=0.25 =0.25), and VarDE (temperature =1.5=1.5, variance floor =100=100). F.2.2 Experiment MCTS.2 - Taxi Environment. Actions are south, north, east, west, pickup, and dropoff. Movement respects the internal wall layout, and in the “raining” setting each move action becomes stochastic: the intended move occurs with probability 0.70.7, and the two orthogonal moves occur with probability 0.150.15 each. Rewards follow the standard Taxi design: −1-1 for movement, −1-1 for a successful pickup, +20+20 for a correct dropoff, and −10-10 for illegal pickup/dropoff attempts. We run with horizon H=20H=20, raining enabled. Evaluation protocol. We evaluate after every 10001000 simulations, from 10001000 to 3000030000, using 200200 evaluation rollouts per checkpoint, averaged over 100100 independent runs. Hyperparameter selection. We select hyperparameters by grid search, using 5050 independent runs, 1000010000 MCTS simulations per run, and 200200 evaluation rollouts. The tuned configurations used are: UCT (bias = auto, ε=0.1 =0.1), MENTS (temperature =1.0=1.0, ε=0.25 =0.25), RENTS (temperature =0.1=0.1, ε=0.5 =0.5), TENTS (temperature =2.0=2.0, ε=0.75 =0.75), DENTS (temperature =3.0=3.0, ε=0.75 =0.75), BTS (temperature =5.0=5.0, ε=0.5 =0.5), and VarDE (temperature =5.0=5.0, variance floor =10=10). F.2.3 Experiment MCTS.3 - FrozenLake Environment. The state is (x,y)(x,y), where (x,y)(x,y) is the agent’s position on a 4×44× 4 map. Each action (left, right, up, down) succeeds with probability p=0.8p=0.8; the remaining probability mass is split equally among the other three directions (slippery environment), with wall/boundary collisions leaving the agent in place. An episode terminates upon reaching the goal, falling into a hole, or when the horizon H=10H=10 is reached. Rewards are sparse: reaching the goal at time t yields reward γtγ^t (with γ=0.95γ=0.95), and all other rewards are 00. Evaluation protocol. We follow the same evaluation procedure as in Experiment MCTS.1. We evaluate after every 10001000 simulations, from 10001000 to 3000030000, using 200200 evaluation rollouts per checkpoint, averaged over 100100 independent runs. Hyperparameter selection. We select hyperparameters by grid search, using 5050 independent runs, 1000010000 MCTS simulations per run, and 200200 evaluation rollouts. The tuned configurations used are: UCT (bias = auto, ε=0.2 =0.2), MENTS/RENTS (temperature =0.01=0.01, ε=0.85 =0.85), TENTS (temperature =0.05=0.05, ε=0.85 =0.85), DENTS (temperature =0.1=0.1, ε=0.85 =0.85), BTS (temperature =0.05=0.05, ε=0.5 =0.5), and VarDE (temperature =0.015=0.015, variance floor =0.01=0.01). F.2.4 Experiment MCTS.4 - Synthetic Tree Environment. We consider a synthetic stochastic tree planning problem. The environment is a balanced k-ary tree of depth d. At each internal node, the agent selects one of the k outgoing actions, but the transition is noisy: the intended child is taken with probability 0.50.5 and each other child with probability 0.5/(k−1)0.5/(k-1). Episodes terminate upon reaching a leaf, where a terminal reward is sampled as r∼(μℓ,0.52)r ( _ ,0.5^2). Leaf means μℓ _ are generated by sampling i.i.d. edge weights and setting each leaf mean to the sum of weights along its root-to-leaf path, then rescaling all leaf means to [0,1][0,1] within each tree. The optimal root value V⋆(s0)V (s_0) is computed exactly by dynamic programming under the true transition model. We evaluate across four tree sizes with (k,d)∈(16,1),(14,3),(16,4),(200,2)(k,d)∈\(16,1),(14,3),(16,4),(200,2)\. Evaluation protocol. For each (k,d)(k,d) setting, we generate 55 random trees and run each method for 10001000 simulations per tree. We report the value estimation error |Vt(s0)−V⋆(s0)||V_t(s_0)-V (s_0)| after each simulation t, averaged over 55 independent runs per tree (mean ± 95% CI). Hyperparameter selection. We tune hyperparameters by grid search on a separate validation split (same simulation budget), selecting the configuration that minimizes the average value estimation error. The tuned configurations used are: UCT (exploration coefficient =0.1=0.1), MENTS (exploration coefficient =0.5=0.5, τ=0.1τ=0.1), RENTS (exploration coefficient =0.5=0.5, τ=0.2τ=0.2), TENTS (exploration coefficient =0.5=0.5, τ=0.5τ=0.5), DENTS (exploration coefficient =0.5=0.5, τ=0.1τ=0.1), BTS (exploration coefficient =0.25=0.25, τ=0.1τ=0.1), and VarDE (temperature =0.1=0.1, variance floor =0.001=0.001). F.3 BPI Experiments Environments. We consider tabular continuing MDPs with Bernoulli rewards rt∈0,1r_t∈\0,1\. In both environments, episodes start at s0=0s_0=0 and we use discount γ=0.99γ=0.99. RiverSwim(L)(L) has state space =0,1,…,L−1S=\0,1,…,L-1\ (so ||=L|S|=L) and two actions =left,rightA=\ left, right\. The left action is deterministic: it moves one step left (and self-loops at s=0s=0). The right action is stochastic: for interior states s∈1,…,L−2s∈\1,…,L-2\ it transitions to s+1s+1 with prob. 0.30.3, stays in s with prob. 0.60.6, and moves to s−1s-1 with prob. 0.10.1; boundary cases follow the standard RiverSwim definition (at s=0s=0, right goes to 11 with prob. 0.30.3 and otherwise stays; at s=L−1s=L-1, right goes to L−2L-2 with prob. 0.70.7 and otherwise stays, while left goes to L−2L-2 deterministically). Rewards are sparse: Pr(rt=1∣st=0,at=left)=0.05 (r_t=1 s_t=0,a_t= left)=0.05, Pr(rt=1∣st=L−1,at=right)=1 (r_t=1 s_t=L-1,a_t= right)=1, and 00 otherwise. ForkedRiverSwim(L)(L) shares a common start state and then splits into two RiverSwim-like branches of length L. It has ||=2L−1|S|=2L-1 states and three actions =left,right,switchA=\ left, right, switch\. Within each branch, left/right behave as in RiverSwim; switch deterministically moves to the state at the same depth on the other branch (and self-loops at the start and at the two terminal states). Rewards are again Bernoulli and sparse: Pr(rt=1∣st=0,at=left)=0.05 (r_t=1 s_t=0,a_t= left)=0.05, the terminal right reward is 11 on one branch and 0.950.95 on the other, and all other rewards are 00. We run RiverSwim with L∈5,10,20,30,50L∈\5,10,20,30,50\ and horizons T∈10,000;20,000;40,000;50,000;80,000T∈\10,000;20,000;40,000;50,000;80,000\ respectively, and ForkedRiverSwim with L∈3,5,10,15,25L∈\3,5,10,15,25\ and horizons T∈20,000;20,000;100,000;200,000;300,000T∈\20,000;20,000;100,000;200,000;300,000\ respectively. Evaluation protocol. For each environment size and each method, we run 1010 independent runs (seeds 0,…,90,…,9) for a fixed interaction budget of T steps. During training, we checkpoint every 200200 steps and evaluate the greedy policy π^t π_t induced by the agent. Since the environments are tabular, we evaluate π^t π_t by exact iterative policy evaluation on the true transition kernel and expected rewards (tolerance 10−610^-6), i.e., we do not use Monte Carlo rollouts. We compute V∗V^* by policy iteration on the same model and report the normalized value proximity 1−‖V∗−Vπ^T‖∞/‖V∗‖∞1-\|V^*-V π_T\|_∞/\|V^*\|_∞ , aggregated as mean ± 95% CI over the 1010 runs. Hyperparameter selection. We use a fixed (singleton) hyperparameter configuration across all environments and sizes. In particular, VarDE–Q-learning uses (τ,var_floor)=(0.1,0.1)(τ, var\_floor)=(0.1,0.1). Q-UCB uses confidence parameter δ=10−3δ=10^-3. MF-BPI uses k¯=1 k=1 and ensemble size 5050. MDP-NaS/PS-MDP-NaS use computation frequencies 200200 for both the greedy policy and allocation updates, with posterior sampling disabled/enabled respectively. O-BPI uses k¯=1 k=1 and update frequency 200200.