Paper deep dive
Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis
Harsh Shrivastava, Yuta Kawakami, Junpei Komiyama, Jin Tian
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 7/7/2026, 12:47:15 PM
Summary
This paper addresses the problem of identifying the optimal treatment (arm) in a causal bandit setting by maximizing the expected natural direct potential outcome (NDPO), which isolates the direct effect of an intervention while excluding pathways through a mediator. The authors establish population-level identification of NDPO using observable interventional distributions, derive a sample complexity lower bound, and propose a Track-and-Stop (TaS-NDPO) algorithm that employs a cutting-set method to solve a semi-infinite optimization problem. The algorithm is proven to be δ-correct and asymptotically optimal, with empirical validation conducted on the IPinYou advertising dataset.
Entities (10)
Relation Signals (9)
Causal Bandit → enables → Best-Arm Identification (BAI)
confidence 96% · In causal bandit problems, the conventional objective is to maximize the interventional mean under arm... identify the target arm using as few samples as possible
Natural Direct Potential Outcome (NDPO) → iscomponentof → Natural Direct Effect (NDE)
confidence 96% · focus exclusively on the first term of the NDE, which we call the natural direct potential outcome (NDPO)
Natural Direct Potential Outcome (NDPO) → measures → direct intervention effect
confidence 95% · captures the potential outcome of an intervention while excluding the pathway transmitted through a mediator
Track-and-Stop (TaS) → optimizes → Natural Direct Potential Outcome (NDPO)
confidence 95% · develop a new BAI algorithm (TaS-NDPO) for identifying the expected NDPO-optimal arm based on the Track-and-Stop (TaS) framework
Structural Causal Model (SCM) → underpins → Natural Direct Potential Outcome (NDPO)
confidence 95% · We use the language of Structural Causal Models (SCM) as our basic semantic and inferential framework... NDPO is a nested counterfactual quantity
Best-Arm Identification (BAI) → guarantees → δ-correctness
confidence 94% · satisfies δ-correctness and asymptotic optimality
Best-Arm Identification (BAI) → guarantees → Asymptotic Optimality
confidence 94% · satisfies δ-correctness and asymptotic optimality
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This paper studies the problem of identifying the treatment that maximizes the expected natural direct potential outcome (NDPO), which captures the potential outcome of an intervention while excluding the pathway transmitted through a mediator that researchers may wish to remove from evaluation. We first establish population-level identification of the expected NDPO in a causal bandit setting using observable interventional distributions. We then develop a fixed-confidence best-arm identification (BAI) algorithm based on the Track-and-Stop (TaS) framework, employing a cutting-set method to solve the resulting semi-infinite optimization problem. The proposed algorithm achieves sample-efficient identification with a high-probability correctness guarantee. We prove that it satisfies $\delta$-correctness and asymptotic optimality. Finally, we validate the approach through empirical evaluations on a large-scale real-world advertising dataset (IPinYou).
Tags
Links
- Source: https://arxiv.org/abs/2607.04315v1
- Canonical: https://arxiv.org/abs/2607.04315v1
Trouble viewing inline? Open PDF directly →
Full Text
99,853 characters extracted from source content.
Expand or collapse full text
Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis Harsh Shrivastava Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) Abu Dhabi, UAE Yuta Kawakami Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) Abu Dhabi, UAE Junpei Komiyama Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) Abu Dhabi, UAE RIKEN AIP, Tokyo, Japan Jin Tian Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) Abu Dhabi, UAE Abstract This paper studies the problem of identifying the treatment that maximizes the expected natural direct potential outcome (NDPO), which captures the potential outcome of an intervention while excluding the pathway transmitted through a mediator that researchers may wish to remove from evaluation. We first establish population-level identification of the expected NDPO in a causal bandit setting using observable interventional distributions. We then develop a fixed-confidence best-arm identification (BAI) algorithm based on the Track-and-Stop (TaS) framework, employing a cutting-set method to solve the resulting semi-infinite optimization problem. The proposed algorithm achieves sample-efficient identification with a high-probability correctness guarantee. We prove that it satisfies δ-correctness and asymptotic optimality. Finally, we validate the approach through empirical evaluations on a large-scale real-world advertising dataset (IPinYou). 1 Introduction Causal mediation analysis studies how a treatment (X) influences an outcome (Y) through different pathways [Sobel1982, Baron1986, Robins1992IdentifiabilityAE, Avin2005, Pearl09, Imai2010]. To elucidate causal mechanisms in nonlinear models, Pearl2001 introduced path-specific effects, including the expected natural direct effect (NDE) via a mediator (Z), defined as [Yx,Zx0]−[Yx0]E[Y_x,Z_x_0]-E[Y_x_0], where Yx,Zx0Y_x,Z_x_0 denotes the potential outcome under treatment level x with the mediator set to the value it would attain under a reference level x0x_0, and Yx0Y_x_0 denotes the potential outcome under treatment level x0x_0. The expected NDE measures the causal effect of a treatment on an outcome that is not mediated through the mediator. In causal bandit problems, the conventional objective is to maximize the interventional mean under arm (treatment) X=xX=x, i.e., [Yx]=[Y|do(X=x)]E[Y_x]=E[Y|do(X=x)] [Lattimore2016, Lee2018, Lee2019]. However, the interventional mean aggregates effects along all causal pathways, including mechanisms that the researcher may wish to exclude from evaluation (e.g., unethical factor or positioning bias in advertisements). To isolate the influence via the direct pathway, this paper studies the problem of identifying the arm that maximizes the expected natural direct potential outcome (NDPO), i.e., [Yx,Zx0]E[Y_x,Z_x_0], in a causal bandit setting. The NDPO corresponds to the first term of the NDE and is defined via a nested counterfactual. In a causal bandit setting, actions correspond to interventions on X [Lattimore2016, Lee2018], and one observes i.i.d. samples from the interventional distribution ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)). The identification results of Pearl2001 are not directly formulated for this setting. Instead, Pearl2001 established the identification using ℙ(Yx,z)P(Y_x,z) and ℙ(Zx0)P(Z_x_0). Therefore, we first establish the corresponding identification assumptions of the expected NDPO at the population level using the interventional distribution ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)). Moreover, in the bandit setting, a further objective is to identify the target arm using as few samples as possible while ensuring correctness with high probability. Such a problem has been extensively studied in the fixed-confidence best-arm identification (BAI) framework for multi-armed bandits [mannor&shie, glynnjuneja2004, audibert2010best, Jamieson&Novak2014, garivier2016optimalbestarmidentification]. We subsequently investigate the fixed-confidence BAI problem for identifying the expected NDPO-optimal arm, which maximizes the expected NDPO, leveraging the established population-level identification results. To develop a BAI algorithm for identifying the expected NDPO-optimal arm, we first derive a lower bound on the sample complexity required to identify the arm that maximizes the expected NDPO. Compared with the standard BAI framework [garivier2016optimalbestarmidentification], the BAI for the expected NDPO-optimal arm is more challenging because evaluating the expected NDPO for a given arm x requires combining information from the outcome distribution under x conditional on Z=zZ=z, ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)), with the mediator distribution under the different baseline arm x0x_0, ℙ(Z|do(X=x0))P(Z|do(X=x_0)). We then develop a new BAI algorithm (TaS-NDPO) for identifying the expected NDPO-optimal arm based on the Track-and-Stop (TaS) framework [garivier2016optimalbestarmidentification], using a cutting-set method [mutapcic2009cutting] to solve the resulting semi-infinite optimization problem. We prove that it satisfies the desired properties of δ-correctness and asymptotic optimality. δ-correctness guarantees that the algorithm identifies the optimal-arm with probability at least 1−δ1-δ and asymptotic optimality refers to achieving the lower bound of sample complexity in the limit as δ→0δ→ 0. Finally, we conduct empirical evaluations on a large-scale real-world advertising dataset (IPinYou) to demonstrate the effectiveness of the proposed method. 2 Notation and Background In this section, we introduce notation and background material. Uppercase letters (e.g., X,Z,YX,Z,Y) denote random variables, and lowercase letters (e.g., x,z,yx,z,y) denote their realizations. Data-dependent quantities such as the stopping time τδ _δ and the recommendation x^(τδ) x( _δ) are random variables. Let ⋅1\·\ denote the indicator function. For two probability distributions P and Q over A, the KL divergence is KL(P∥Q):=∑a∈P(a)logP(a)Q(a)KL(P\|Q):= _a P(a) P(a)Q(a). An event happens almost surely (a.s.) if it occurs with probability 1. Structural Causal Models. We use the language of Structural Causal Models (SCM) as our basic semantic and inferential framework [Pearl09]. An SCM ℳM is a tuple ⟨,,ℱ,ℙ⟩ < V, U,F,P_ U >, where U is a set of exogenous (unobserved) variables following a joint distribution ℙP_ U, and V is a set of endogenous (observable) variables whose values are determined by structural functions ℱ=fViVi∈F=\f_V_i\_V_i∈ V such that vi:=fVi(Vi,Vi)v_i:=f_V_i(pa_V_i, u_V_i) where Vi⊆PA_V_i V and UVi⊆U_V_i U. Each SCM ℳM induces an observational distribution ℙP_ V over V, and a causal graph G(ℳ)G(M) over V in which there exists a directed edge from every variable in ViPA_V_i to ViV_i. An intervention of setting a set of endogenous variables X to constants x, denoted by do()do( x), replaces the original equations of X by the constants x and induces a sub-model ℳM_ x. We denote the potential outcome Y under intervention do()do( x) by Y()Y_ x( u), which is the solution of Y in the sub-model ℳM_ x given = U= u. Causal Mediation Analysis. Let X be a treatment variable (arm), Y be an outcome, and Z be a mediator variable. The following nonparametric SCM (ℳM) is used in causal mediation analysis. ℳ:X:=fX(UX),Z:=fZ(X,UZ),Y:=fY(X,Z,UY), gatheredM:X:=f_X(U_X),Z:=f_Z(X,U_Z),\\ Y:=f_Y(X,Z,U_Y), gathered (1) where UXU_X, UZU_Z, and UYU_Y are latent exogenous variables, with bidirected edges indicating unmeasured confounders affecting the variables. Figure 1 shows a causal graph representing ℳM. Under SCM ℳM, Pearl2001 defined the unit-level NDE given a reference value x0x_0 as Yx,Zx0()−Yx0()Y_x,Z_x_0( u)-Y_x_0( u) for each subject u, and the expected NDE given a reference value x0x_0 as [Yx,Zx0]−[Yx0]E[Y_x,Z_x_0]-E[Y_x_0]. [Pearl2001] provided identification conditions of the expected NDE, that is Yx,z⟂Zx0Y_x,z \!\!\! Z_x_0 for any x and z. ZZYYXX Figure 1: A causal graph representing ℳM. Throughout this paper, we consider SCM ℳM with a discrete arm (treatment) variable X∈0,1,…,K−1=:X∈\0,1,…,K-1\=:X, and a discrete mediator Z∈0,1,…,M−1=:Z∈\0,1,…,M-1\=:Z, and a binary outcome Y∈0,1=:Y∈\0,1\=:Y. We fix a baseline arm x0∈x_0 . The choice of x0x_0 is predetermined based on domain knowledge in practice. Best-arm identification. In the fixed-confidence best-arm identification (BAI) setting, a learner sequentially samples arms and aims to identify the optimal-arm with probability at least 1−δ1-δ for a prescribed confidence level δ∈(0,1)δ∈(0,1). A sequential algorithm consists of a sampling rule, a stopping time τδ _δ, and a recommendation rule x^(τδ) x( _δ). An algorithm is said to be δ-correct if ℙ(τδ<∞,x^(τδ)≠x⋆)≤δP\! ( _δ<∞, x( _δ)≠ x )≤δ, where x⋆x denotes the optimal-arm under the true model. The objective is to design a δ-correct algorithm that minimizes the expected stopping time [τδ]E[ _δ]. 3 Research Objective In this paper, we focus exclusively on the first term of the NDE, which we call the natural direct potential outcome (NDPO). Definition 1 (NDPO). For each subject u, we define the unit-level natural direct potential outcome (NDPO) at a reference x0x_0 as Yx,Zx0()Y_x,Z_x_0( u). Its population-level expectation is defined as [Yx,Zx0]:=[Yx,Zx0()]E[Y_x,Z_x_0]:=E_ U[Y_x,Z_x_0( U)]. We do not study the contrast with the baseline Yx0Y_x_0. The expectation of NDPO means: “the expected outcome if we set the arm X to x, while keeping the mediator Z at the level it would have taken under the reference arm x0x_0." NDPO is a nested counterfactual quantity that measures the influence of the intervention X=xX=x, removing the effect transmitted through Z. In causal bandit problems, the conventional objective is to maximize the interventional mean [Yx]=[Y|do(X=x)]E[Y_x]=E[Y|do(X=x)] [Lattimore2016, Lee2018, Lee2019]. This paper studies the maximization of the expectation of the NDPO. We denote the optimal-arm w.r.t. the expected NDPO under SCM ℳM as follows: x⋆:=argmaxx∈[Yx,Zx0].x := _x E[Y_x,Z_x_0]. (2) The optimal-arm w.r.t. the expected NDPO is the arm that maximizes the expectation of NDPO. We present motivating examples illustrating why we study the maximization of the expectation of NDPO in Appendix A. 4 Bridging Causal Inference and Best Arm Identification Population-level identification of causal quantities has been extensively studied within the causal inference framework [Pearl09]. In this section, we establish the population-level identification of the expected NDPO using interventional distribution ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)) for a discrete Y and a connection between the causal inference framework and best arm identification (BAI) theory [garivier2016optimalbestarmidentification]. All proofs are provided in Appendix F. Population-level causal identification of the expected NDPO under the causal bandit setting. We consider a causal bandit setting in which researchers sequentially collect samples by pulling arms in order to identify the optimal-arm w.r.t. NDPO. Pulling arm x corresponds to performing the intervention do(X=x)do(X=x) [Lattimore2016]. In our mediation setting, pulling arm x yields i.i.d. samples from the interventional distribution ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)). To identify [Yx,Zx0]E[Y_x,Z_x_0] from ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)), we impose the following assumption on potential outcomes. Assumption 1 (Assumption for Identification for NDPO). Yx,z⟂Zx′Y_x,z \!\!\! Z_x for all x,x′∈x,x and z∈z . Here, x′x denotes an arbitrary reference level. Pearl2001 considers the reference-specific condition (which we call Assumption 1’ here): “Yx,z⟂Zx0Y_x,z \!\!\! Z_x_0 for all x∈x and z∈z for a fixed x0x_0.” Formally, Assumption 1 appears stronger, as it requires independence w.r.t. (Zx′Z_x ) for every (x′x ), rather than a single reference level (x0x_0). However, in practice, such reference-specific assumptions are typically understood to hold irrespective of the particular choice of baseline level. That is, Assumption 1’ is implicitly required to hold for any admissible x0x_0. More importantly, Pearl2001 provides a graphical characterization of Assumption 1’: Y⟂Zin GX¯,Z¯,Y Z G_ X, Z, (3) that is, Y is d-separated from Z in the graph obtained by removing all outgoing edges from X and Z. This condition is purely graphical and therefore does not depend on the specific value of x′x . Consequently, under the graphical interpretation, Assumptions 1 and 1’ are equivalent, as they correspond to the same d-separation condition. Neither Assumption 1 nor Assumption 1’ is testable from observed data alone. In applications, what can be assessed is the plausibility of the underlying causal graph. Both assumptions basically correspond to the absence of unmeasured confounding between Z and Y. Then, we have the following identification theorem for a discrete Y: restatabletheoremTheoremone Under SCM ℳM and Assumption 1, the expected NDPO is identified by θ(x)θ(x), where θ(x) θ(x) =∑y,zyPx(y|z)Px0(z), = _y,zyP_x(y|z)P_x_0(z), (4) where Px(y|z)=ℙ(Y=y|Z=z,do(X=x))P_x(y|z)=P(Y=y|Z=z,do(X=x)) and Px(z)=ℙ(Z=z|do(X=x))P_x(z)=P(Z=z|do(X=x)). This differs in form from Theorem 1 of Pearl2001: we express θ(x)θ(x) using the joint interventional distribution ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)), rather than using ℙ(Yx,z)P(Y_x,z) and ℙ(Zx0)P(Z_x_0) [Pearl2001]. The equality ℙ(Yx,z)=ℙ(Y|do(X=x),do(Z=z))P(Y_x,z)=P(Y|do(X=x),do(Z=z)) corresponds to intervening on both X and Z, which does not match our causal bandit setting. Connection to BAI theory. Estimation of mediated effects from a fixed dataset has been widely studied in the causal inference literature. For example, θ(x)θ(x) can be directly estimated using plug-in empirical estimators of Px(y|z)P_x(y|z) and Px(z)P_x(z) [Imai2010b]. Moreover, VanderWeele2010, Tchetgen2012 used parametric or semiparametric regression models to estimate mediated effects. In contrast, under a bandit setting, data are collected sequentially. In this setting, the researcher is motivated to identify the target using as few samples as possible while guaranteeing correctness with high probability [garivier2016optimalbestarmidentification]. Accordingly, our goal is to develop a BAI algorithm that identifies the arm maximizing the NDPO through θ(x)θ(x) with minimal sample complexity, subject to a high-probability correctness guarantee. We next investigate the BAI problem of identifying the arm that maximizes θ, apart from the causal inference perspective, rather than directly optimizing the expected NDPO. 5 Sample Complexity Lower Bound We derive a lower bound on the expected stopping time of any δ-correct algorithm that identifies the arm maximizing θ, analogous to the classical fixed-confidence BAI lower bounds for a binary outcome Y∈0,1Y∈\0,1\ (for simplicity) [lairobbins1985, garivier2016optimalbestarmidentification]. This reveals the fundamental limitations of the BAI framework. To study BAI for θ, we introduce the following notation. Let P denote the set of all P, where P is a collection of interventional distributions (Px)x∈(P_x)_x , where PxP_x denotes ℙ(Z,Y|do(X=x))P(Z,Y|do(X=x)). For each P∈P , we define θP(x):=∑z∈Px(1|z)Px0(z), _P(x):= _z P_x(1|z)\,P_x_0(z), (5) x⋆(P):=argmaxx∈θP(x). x (P):= _x _P(x). (6) We impose the following assumption. Assumption 2 (Unique optimum). For the true model P∈P , the maximizer x⋆(P)x (P) is unique. Let τδ _δ denote the stopping time at confidence level δ, and let x^τδ x_ _δ be the recommended arm. We define a δ-correct algorithm for the optimal-arm w.r.t. θ as follows: Definition 2 (δ-correct algorithm). Let δ∈(0,1)δ∈(0,1). An algorithm for identifying the optimal-arm w.r.t. θ is δ-correct if, for every P∈P , ℙP(τδ<∞,x^τδ≠x⋆(P))≤δ.P_P\! ( _δ<∞, x_ _δ≠ x (P) )≤δ. (7) To derive the lower bound, we consider an alternative model in which the optimal-arm differs from that in the underlying model. For a fixed model P∈P , define the set of alternatives: Alt(P):=Q∈:x⋆(Q)≠x⋆(P)Alt(P):= \Q :x (Q)≠ x (P) \. Equivalently, Q∈Alt(P)Q (P) if there exists x≠x⋆(P)x≠ x (P) such that θQ(x)≥θQ(x⋆(P)). _Q(x)≥ _Q(x (P)). (8) For two models P,Q∈P,Q and an arm x∈x , define the interventional joint distribution Px(z,y):=ℙP(Z=z,Y=y|do(X=x)),P_x(z,y):=P_P(Z=z,Y=y|do(X=x)), (9) and similarly Qx(z,y)Q_x(z,y) for model Q. We denote the corresponding marginals and conditionals by Px(z):=∑y∈Px(z,y),Px(y|z):=Px(z,y)Px(z),P_x(z):= _y P_x(z,y),P_x(y|z):= P_x(z,y)P_x(z), (10) and similarly for Qx(z)Q_x(z) and Qx(y|z)Q_x(y|z). Since Px(z,y)=Px(z)Px(y|z)P_x(z,y)=P_x(z)P_x(y|z), the KL divergence decomposes as KL(Px∥Qx)=KL(Px(Z)∥Qx(Z)) (P_x\|Q_x)=KL (P_x(Z)\|Q_x(Z) ) +∑z∈Px(z)KL(Px(Y|z)∥Qx(Y|z)). + _z P_x(z)\,KL (P_x(Y|z)\|Q_x(Y|z) ). (11) The KL decomposition in (5) splits KL(Px∥Qx)KL(P_x\|Q_x) into a mediator term and a conditional outcome term weighted by Px(z)P_x(z). Hence discrepancies in Px(1|z)P_x(1|z) at rare mediator values contribute little to the total divergence, so distinguishing such differences requires more samples from arm x. Then, we have the following theorem: restatabletheoremTheoremtwo[Instance-dependent lower bound] Let δ∈(0,1)δ∈(0,1). Under Assumption 2, for any δ-correct algorithm and any P∈P , P[τδ]≥T⋆(P)kl(δ,1−δ),E_P[ _δ]\;≥\;T (P)\,kl(δ,1-δ), (12) where kl(δ,1−δ)=δlogδ1−δ+(1−δ)log1−δkl(δ,1-δ)=δ \! δ1-δ+(1-δ) \! 1-δ and (T⋆(P))−1=supw∈ΣKinfQ∈Alt(P)∑x∈wxKL(Px∥Qx)(T (P))^-1= _w∈ _K _Q (P) _x w_x\,KL(P_x\|Q_x) (13) with ΣK:=w∈ℝ+K:∑x∈wx=1 _K:=\w _+^K: _x w_x=1\. Here ℝ+K:=v∈ℝK:vx≥0,∀xR_+^K:=\v ^K:v_x≥ 0,∀ x\. The vector w∈ΣKw∈ _K represents asymptotic sampling proportions: wxw_x is the fraction of samples allocated to arm x in the long run. The kl(⋅,⋅)kl(·,·) denotes the binary relative entropy. The sup–inf form in (13) chooses proportions w that maximize the worst-case information rate for distinguishing the true model P from alternatives under which the identity of the optimal-arm differs. Technical difficulties in BAI for θ. The lower bound in Theorem 2 highlights two essential differences from classical best-arm identification. In classical BAI, the objective is μx=P[Y|do(X=x)] _x=E_P[Y|do(X=x)], and the characteristic time reduces to (TBAI⋆(P))−1=supw∈ΣKinfx≠x⋆(P)∑a∈waKL(Pa∥Qa(x))(T _BAI(P))^-1= _w∈ _K _x≠ x (P) _a w_aKL(P_a\|Q^(x)_a), where Q(x)Q^(x) denotes an alternative model that coincides with P on all arms except x⋆(P)x (P) and x, and is chosen so that x becomes optimal under Q(x)Q^(x) [garivier2016optimalbestarmidentification]. This yields a low-dimensional convex program in which, for each suboptimal-arm x≠x⋆(P)x≠ x (P) (called a competitor), the alternative model modifies only the true best arm and the single competing arm x. In contrast, θ couples outcome behavior under arm x with the mediator distribution under the baseline arm x0x_0. The constraint (8) depends jointly on mediator and outcome mechanisms, so the inner minimization cannot be reduced to modifying only the best arm and a single competitor while keeping all other arms fixed, as in classical BAI. Instead, the baseline mediator distribution Qx0(Z)Q_x_0(Z) enters the objective for every arm through θQ(⋅) _Q(·), creating an explicit coupling across arms. Moreover, the KL decomposition (5) shows that deviations in Px(y|z)P_x(y|z) are weighted by the mediator probability Px(z)P_x(z). If decisive differences occur at mediator values with small probability mass, the effective information rate is reduced, increasing the characteristic time T⋆(P)T (P). These two features—the non-separable alternative constraint and the information that accumulates at the level of mediator–outcome cells (x,z)(x,z) —do not arise in classical BAI. We call each pair (x,z)∈×(x,z) ×Z a cell, corresponding to the conditional outcome parameter Px(y|z)P_x(y|z) and the frequency with which mediator value z occurs under arm x. 6 A Track-and-Stop Algorithm for Causal Mediation Analysis We adapt the Track-and-Stop (TaS) framework for fixed-confidence BAI [garivier2016optimalbestarmidentification] to the objective θ. TaS combines forced exploration, a plug-in solution of the characteristic max–min allocation problem, and a generalized likelihood ratio stopping rule. However, the structure of the lower bound in Section 5 prevents a direct application of the classical arm-local TaS analysis. Two modifications are required: (i) Cell-level information control. By the KL decomposition (5), information accumulates at the mediator–outcome cell level (x,z)(x,z). Arm-level forced exploration alone does not ensure that all cell counts Nx,z(t)N_x,z(t) diverge, which is necessary for consistent estimation of Px(y|z)P_x(y|z) and evaluation of the likelihood-ratio statistic used in the stopping rule. (i) Non-separable alternative optimization. The alternative constraint defining Alt(P)Alt(P) couples arms through the baseline mediator distribution Px0(Z)P_x_0(Z). As a result, the inner minimization in the characteristic time cannot be reduced to a single best-arm–competitor pair, and instead yields a bi-convex projection problem. By modifying these components, we develop a new algorithm, TaS-NDPO, which is presented in Algorithm 1. The following subsections detail the resulting sampling rule and the associated optimization procedure. 6.1 Plug-in Estimates We first define the empirical model and the corresponding plug-in estimators of θ(x)θ(x). At round s=1,2,…s=1,2,…, the learner selects Xs∈X_s and observes (Zs,Ys)∼PXs(Z_s,Y_s) P_X_s. Define the arm and cell counts at the round t Nx(t):=∑s=1tXs=x, N_x(t):=Σ _s=1^t1\X_s=x\, (14) Nx,z(t):=∑s=1tXs=x,Zs=z, N_x,z(t):=Σ _s=1^t1\X_s=x,Z_s=z\, (15) Sx,z(t):=∑s=1tXs=x,Zs=z,Ys=1. S_x,z(t):=Σ _s=1^t1\X_s=x,Z_s=z,Y_s=1\. (16) Then, the empirical distributions are P^x(z;t):=Nx,z(t)Nx(t),P^x(1|z;t):=Sx,z(t)Nx,z(t). P_x(z;t):= N_x,z(t)N_x(t), P_x(1|z;t):= S_x,z(t)N_x,z(t). (17) The empirical joint model at time t is the collection P^(t):=(P^x(⋅;t))x∈ P(t):=( P_x(\,·\,;\,t))_x , where for each arm x∈x , P^x(⋅;t) P_x(\,·\,;\,t) denotes the empirical joint distribution of (Z,Y)(Z,Y) under arm x, with probability mass function P^x(z,y;t):=P^x(z;t)P^x(y|z;t) P_x(z,y;\,t):= P_x(z;\,t)\, P_x(y|z;\,t) for (z,y)∈×0,1(z,y) ×\0,1\. The plug-in estimate of θ is θ^t(x):=∑z∈P^x(1|z;t)P^x0(z;t), θ_t(x):= _z P_x(1|z;t)\, P_x_0(z;t), (18) and the empirical best arm is the smallest index in the argmax set x^(t)∈argmaxx∈θ^t(x). x(t)∈ _x θ_t(x). (19) 6.2 Computation of the Plug-in Allocation In contrast to classical BAI, the alternative constraint couples mediator and outcome mechanisms, yielding a non-separable KL projection with bilinear structure of Eq. (13). In this section, after reducing the dimension of the optimization, we introduce a cutting-set method that solves this optimization. Plug-in allocation. Replacing the true model P by P^(t) P(t) in the characteristic-time optimization, we define the alternative set Alt(P^(t)):=Q∈:x⋆(Q)≠x^(t)Alt( P(t)):=\Q :x (Q)≠ x(t)\ and the target allocation w^(t)∈argmaxw∈ΣKinfQ∈Alt(P^(t))∑x∈wxKL(P^x(t)∥Qx). w(t)∈ *arg\,max_w∈ _K _Q ( P(t)) _x w_x\,KL( P_x(t)\|Q_x). (20) Decomposition over competitors. Let P∈P admit a unique maximizer x⋆(P)x (P). The alternative set is given as Alt(P):=⋃x′≠x⋆(P)Q∈:θQ(x′)≥θQ(x⋆(P)).Alt(P):= _x ≠ x (P)\Q : _Q(x )≥ _Q(x (P))\. (21) Accordingly, the inner infimum in (20) decomposes into K−1K-1 subproblems indexed by competitors x′≠x⋆(P)x ≠ x (P). Reduction to three arms. Fix a competitor x′≠x⋆(P)x ≠ x (P) and consider infQ∈∑a∈waKL(Pa∥Qa) s.t. θQ(x′)≥θQ(x⋆(P)). _Q _a w_a\,KL(P_a\|Q_a) s.t. _Q(x )≥ _Q(x (P)). (22) restatable propositionPropositionone[Reduction to three arms] For the inner minimization oracle in (22), it is without loss of optimality to restrict attention to solutions satisfying Qa=PaQ_a=P_a for all a∉x0,x⋆(P),x′a∉\x_0,x (P),x \. Hence, the inner minimization effectively involves only three arms: x0x_0, x⋆(P)x (P), and a single competitor x′x . Reduced inner problem. Let x⋆=x⋆(P)x =x (P) and fix x′≠x⋆x ≠ x . After restriction, the free variables are q0(z):=Qx0(z),r⋆(z):=Qx⋆(1|z),r′(z):=Qx′(1|z),z∈q_0(z):=Q_x_0(z),r (z):=Q_x (1|z),r (z):=Q_x (1|z),z . The feasible set is Δ||×[0,1]||×[0,1]|| _|Z|×[0,1]^|Z|×[0,1]^|Z|, where Δ||:=q∈ℝ+||:∑z∈q(z)=1 _|Z|:=\q _+^|Z|: _z q(z)=1\ is the probability simplex over Z. This set is compact and convex. The objective becomes wx0∑zKL(P^x0(z)∥q0(z)) w_x_0Σ _zKL( P_x_0(z)\,\|\,q_0(z)) (23) +wx⋆∑zP^x⋆(z)KL(P^x⋆(1|z)∥r⋆(z)) +w_x Σ _z P_x (z)KL( P_x (1|z)\|r (z)) +wx′∑zP^x′(z)KL(P^x′(1|z)∥r′(z)). +w_x Σ _z P_x (z)KL( P_x (1|z)\|r (z)). The original constraint is ∑zr′(z)q0(z)≥∑zr⋆(z)q0(z).Σ _zr (z)q_0(z)≥Σ _zr (z)q_0(z). (24) This inequality must hold with equality at an optimal solution. Indeed, if there were an optimal solution for which the inequality were strict, then there would exist a sufficiently small α>0α>0 such that replacing r⋆(z)←(1−α)r⋆(z)+αP^x⋆(1|z), r (z)←(1-α)r (z)+α P_x (1|z), (25) r′(z)←(1−α)r′(z)+αP^x′(1|z). r (z)←(1-α)r (z)+α P_x (1|z). reduces the objective value in (LABEL:eq:reduced_objective), while not changing the sign of the difference between the left-hand side and right-hand side of the constraint. Therefore, no optimal solution can satisfy the constraint with strict inequality, and the constraint reduces to the scalar bilinear equality ∑zr′(z)q0(z)=∑zr⋆(z)q0(z).Σ _zr (z)\,q_0(z)=Σ _zr (z)\,q_0(z). (26) restatable propositionPropositiontwo[Bi-convex structure] The optimization problem defined by (LABEL:eq:reduced_objective)–(26) is convex in (r⋆,r′)(r ,r ) for fixed q0q_0, and convex in q0q_0 for fixed (r⋆,r′)(r ,r ), but not jointly convex. Cutting-set method. Even after reducing the dimension to three, the resulting problem is still a linear semi-infinite program in w=(wx0,wx⋆,wx′)w=(w_x_0,w_x ,w_x ). This is because the constraint involving (r′(z),q0(z),r⋆(z))(r (z),q_0(z),r (z)) must hold over a continuous domain. The cutting-set method [mutapcic2009cutting] starts with some initial set (1)⊂Alt(P^)Q^(1) ( P). 111In our implementation, the active set is initialized with one constraint for each competitor arm. This avoids degenerate initial allocations and ensures that each competitor is represented in the master problem. If a candidate allocation assigns zero mass to an arm a, then the competitor subproblem with x′=ax =a is selected as a hardest constraint and added to the active set; the subsequent master update then accounts for this arm and assigns it positive mass when needed. At each iteration s=1,2,…s=1,2,…, the method maintains a finite active set (s)⊂Alt(P^)Q^(s) ( P) and proceeds as follows: (i) solving maxw∈ΣKminQ∈(s−1)∑xwxKL(P^x∥Qx) _w∈ _K _Q ^(s-1) _xw_xKL( P_x\|Q_x) on w, which is a finite-dimensional linear programming, and (i) computing a most-violated alternative model via the reduced bi-convex problem, and add it to (s)Q^(s). Optimization properties. Under mild conditions, including boundedness of the objective and empirical means bounded away from 0 and 11, the cutting-set method converges to a global optimum [mutapcic2009cutting, Section 5.2] assuming that (i) is exact. These conditions are satisfied in our setting when the empirical estimates remain in [ε,1−ε][ ,1- ] for some ε>0 >0. Regarding the optimality of (i), we solve it via alternating minimization. The implementation details are provided in Appendix C. Under standard regularity conditions, block coordinate descent for bi-convex problems converges to a stationary point [Tseng2001]. However, in general, such a stationary point may not be globally optimal. For ease of discussion, our theoretical analysis in Section 7 assumes access to the exact optimizer. Computation. In our experiments, the optimization routine is not a major computational bottleneck: TaS-NDPO takes 22.5 seconds on average for runs with up to 100,000 samples; detailed runtime comparisons are reported in Appendix E.2. 6.3 Sampling Rule We use the convention that after t pulls we have counts Nx(t),Nx,z(t)N_x(t),N_x,z(t) (Section 6.1), and we choose the next arm Xt+1X_t+1 based on plug-in quantities computed from data up to time t. Given the plug-in allocation w^(t) w(t), the algorithm follows a D-tracking rule augmented with (i) competitor coverage and (i) cell-level forcing. D-tracking. When neither coverage nor forcing is active, we apply the D-tracking rule [garivier2016optimalbestarmidentification], i.e., Xt+1X_t+1 is updated by the smallest index of argmaxx∈(tw^x(t)−Nx(t)) _x (t\, w_x(t)-N_x(t) ). Competitor coverage. Let Cx(t)C_x(t) denote the number of times arm x has been selected as the competitor up to time t, with initialization Cx(0)=0C_x(0)=0 and update Cx(t)=Cx(t−1)+x′(t)=x.C_x(t)=C_x(t-1)+1\x (t)=x\. (27) Fix a∈(0,1)a∈(0,1) and define h(t):=⌈ta⌉h(t):= t^a , where ⌈⋅⌉ · denotes the ceiling function. After observing t samples, we select the next competitor x′(t+1)x (t+1) as follows. If minx∈Cx(t)<h(t) _x C_x(t)<h(t), choose x′(t+1)∈argminCx(t):Cx(t)<h(t),x (t+1)∈ \C_x(t):C_x(t)<h(t)\, (28) breaking ties by the smallest index. Otherwise, choose x′(t+1)x (t+1) as any competitor x′≠x^(t)x ≠ x(t) attaining the minimum among the competitor-wise inner problems described in Section 6.2, breaking ties by the smallest index. This rule guarantees that each arm is selected as a competitor at least h(t)−1=Ω(ta)h(t)-1= (t^a) times (for all sufficiently large t). Cell-level forcing. Define the relevant arm set at time t+1t+1 by rel(t+1)=x0,x^(t),x′(t+1)A_rel(t+1)=\x_0, x(t),x (t+1)\. Let g(t)g(t) be nondecreasing with g(t)→∞g(t)→∞ and g(t)=o(h(t))g(t)=o(h(t)). For any arm x, define its minimum cell count mx(t):=minz∈Nx,z(t)m_x(t):= _z N_x,z(t). Define the set of deficient relevant arms (computed from time-t counts) (t):=x∈rel(t+1):mx(t)<g(t)D(t):=\x _rel(t+1):m_x(t)<g(t)\. If (t)≠∅D(t)≠ , we force exploration by choosing Xt+1∈argminu∈(t)(mu(t),Nu(t))X_t+1∈ _u (t)(m_u(t),\,N_u(t)), i.e., we minimize mu(t)m_u(t) and break ties by the smallest total count Nu(t)N_u(t) (and then by the smallest index). Otherwise, we perform D-tracking breaking ties by the smallest index. Role of coverage and forcing. Competitor coverage ensures each arm is compared often enough, while cell-level forcing ensures all relevant cell counts Nx,z(t)N_x,z(t) grow, which is needed for consistency and for the likelihood-ratio statistic in the stopping rule. Both mechanisms act on a vanishing fraction of rounds since h(t)=tah(t)=t^a with a∈(0,1)a∈(0,1) and g(t)=o(h(t))g(t)=o(h(t)), so the dominant sampling dynamics are governed by D-tracking. Algorithm 1 Algorithm of TaS-NDPO 0: Confidence δ∈(0,1)δ∈(0,1); baseline arm x0x_0; h(t)=⌈ta⌉h(t)= t^a for some a∈(0,1)a∈(0,1); nondecreasing g(t)g(t) such as g(t)→∞g(t)→∞ and g(t)=o(h(t))g(t)=o(h(t)). 1: Pull each arm once and update counts; set Cx←0C_x← 0 for all x∈x . 2: for t=||,||+1,…t=|X|,|X|+1,… do 3: Compute P^(t) P(t), θ^t(⋅) θ_t(·), x^(t)∈argmaxx∈θ^t(x) x(t)∈ _x θ_t(x), and w^(t) w(t). 4: Compute Zt(x,x^(t))Z_t(x, x(t)) for all x≠x^(t)x≠ x(t). 5: if minx≠x^(t)Zt(x,x^(t))≥β(t,δ) _x≠ x(t)Z_t(x, x(t))≥β(t,δ) then 6: return x^(t) x(t) 7: end if 8: Competitor coverage: 9: if minx∈Cx<h(t) _x C_x<h(t) then 10: x′(t+1)x (t+1) is updated by the smallest index of argminCx:Cx<h(t) \C_x:\ C_x<h(t)\. 11: else 12: x′(t+1)←x (t+1)← a minimizer of the competitor-wise inner problems described in Section 6.2. 13: end if 14: Cx′(t+1)←Cx′(t+1)+1C_x (t+1)← C_x (t+1)+1,rel←x0,x^(t),x′(t+1)A_rel←\x_0, x(t),x (t+1)\,←u∈rel:minz∈Nu,z(t)<g(t)D←\u _rel:\ _z N_u,z(t)<g(t)\. 15: Arm selection: 16: if ≠∅D≠ then 17: Xt+1X_t+1 is updated by the smallest index of argminu∈(minzNu,z(t),Nu(t)). _u ( _zN_u,z(t),\,N_u(t)). 18: else 19: Xt+1X_t+1 is updated by the smallest index of argmaxx∈(tw^x(t)−Nx(t)). _x (t w_x(t)-N_x(t)). 20: end if 21: Pull Xt+1X_t+1; observe (Zt+1,Yt+1)(Z_t+1,Y_t+1); update counts. 22: end for 23: return x^(t) x(t) 6.4 Stopping rule The stopping rule should guarantee δ-correctness while stopping as soon as the data exclude every model under which a suboptimal-arm could be optimal. As in classical TaS, we use a likelihood-based test against the closest alternative model. Likelihood function. For any Q∈Q , define the negative log-likelihood ratio ℒt(Q):=∑a∈Na(t)KL(P^a(t)∥Qa)L_t(Q):= _a N_a(t)\,KL( P_a(t)\|Q_a), where P^a(t) P_a(t) denotes the empirical joint distribution of (Z,Y)(Z,Y) under arm a. GLRT statistic. At time t, for each competitor x≠x^(t)x≠ x(t), define the generalized likelihood ratio statistic (GLRT) Zt(x,x^(t)):=infQ∈:θQ(x)≥θQ(x^(t))ℒt(Q),Z_t(x, x(t)):= _Q :\, _Q(x)≥ _Q( x(t))L_t(Q), (29) where θQ(x)=∑z∈Qx(1|z)Qx0(z) _Q(x)= _z Q_x(1|z)\,Q_x_0(z). The statistic Zt(x,x^(t))Z_t(x, x(t)) measures the minimal empirical KL divergence to a model under which arm x is at least as good as the current empirical best arm x^(t) x(t). Stopping condition. Let β(t,δ)β(t,δ) be a nondecreasing threshold. Define the stopping time τδ:=inft≥1:minx≠x^(t)Zt(x,x^(t))≥β(t,δ), _δ:= \t≥ 1:\; _x≠ x(t)Z_t(x, x(t))\;≥\;β(t,δ)\, (30) and output x^(τδ) x( _δ). A concrete choice of β(t,δ)β(t,δ) ensuring δ-correctness is provided in Appendix B. 7 Theoretical Guarantees In this section, we establish δ-correctness and asymptotic optimality of Algorithm 1. We first assume Assumption 3 (Uniform interior (KL-regularity)). There exists ε∈(0,1/2) ∈(0,1/2) such that for every model R∈R , every arm x∈x , and every mediator value z∈z , Rx(z)≥ε,Rx(1|z)∈[ε,1−ε].R_x(z)≥ ,R_x(1|z)∈[ ,1- ]. (31) This assumption guarantees that all KL divergences in the characteristic-time optimization are finite and continuous. It ensures that the relevant probability vectors remain in the interior of the simplex, which is needed for the continuity and compactness arguments in the asymptotic analysis. Then, our algorithm has δ-correctness. restatabletheoremTheoremthree[δ-correctness] Assume β(t,δ)β(t,δ) is chosen as in Appendix B. For any δ∈(0,1)δ∈(0,1) and any P∈P , Algorithm 1 satisfies ℙP(τδ<∞,x^(τδ)≠x⋆(P))≤δ.P_P\! ( _δ<∞, x( _δ)≠ x (P) )≤δ. (32) For the asymptotic optimality result, we also assume uniqueness of the characteristic allocation. Assumption 4 (Unique characteristic allocation). The maximizer w⋆(P)w (P) of the characteristic optimization problem is unique. We show the following lemmas: restatable lemmaLemmaone Under Assumption 3. Let h(t)=⌈ta⌉h(t)= t^a for some a∈(0,1)a∈(0,1) and let g(t)g(t) be nondecreasing with g(t)→∞g(t)→∞ and g(t)=o(h(t))g(t)=o(h(t)). Under the sampling rule of Section 6.3, Nx(t)→∞,Nx,z(t)→∞,∀x∈,z∈,a.s.N_x(t)→∞,N_x,z(t)→∞,∀ x ,\ z ,a.s. (33) Since Nx,z(t)→∞N_x,z(t)→∞ for all x,zx,z, the strong law yields P^x(z;t)→Px(z),P^x(1|z;t)→Px(1|z) a.s. P_x(z;t)→ P_x(z), P_x(1|z;t)→ P_x(1|z) a.s. (34) Hence P^(t)→P P(t)→ P almost surely. restatable lemmaLemmatwo[Consistency of plug-in allocation] Under Assumption 2, if P^(t)→P P(t)→ P almost surely, then w^(t)→w⋆(P) w(t)→ w (P) almost surely. restatable lemmaLemmathree[Sublinearity of forced rounds] Let F(t)F(t) denote the number of rounds up to time t in which either competitor coverage or cell-level forcing overrides the D-tracking update. Then F(t)=O(h(t))+O(g(t))F(t)=O(h(t))+O(g(t)). In particular, if h(t)=tah(t)=t^a with a∈(0,1)a∈(0,1) and g(t)=o(h(t))g(t)=o(h(t)), then F(t)=o(t)F(t)=o(t) almost surely. restatable lemmaLemmafour[Tracking of sampling proportions] Under Assumptions 3 and 4, the sampling proportions satisfy Nx(t)/t→wx⋆(P)N_x(t)/t→ w_x (P) for all x∈x almost surely. This follows from Lemmas 4 and 4. Let T⋆(P)T (P) denote the characteristic time in Theorem 2. restatable lemmaLemmafive[Asymptotic growth of the GLRT] For every competitor x≠x⋆(P)x≠ x (P), ℙP(lim inft→∞t−1Zt(x,x^(t))≥ _P ( _t→∞t^-1Z_t(x, x(t))\;≥\; (35) infQ∈:θQ(x)≥θQ(x⋆(P))∑a∈wa⋆(P)KL(Pa∥Qa))=1. _ subarraycQ : _Q(x)≥ _Q(x (P)) subarray _a w_a (P)\,KL(P_a\|Q_a) )=1. Consequently, ℙP(lim inft→∞t−1minx≠x⋆(P)Zt(x,x^(t))≥T⋆(P)−1)=1.P_P\! ( _t→∞t^-1 _x≠ x (P)Z_t(x, x(t))\;≥\;T (P)^-1 )=1. (36) Then, our algorithm has asymptotic optimality. restatabletheoremTheoremfive[Almost sure asymptotic optimality] Fix a true model P∈P satisfying Assumptions 2, 3 and 4. Then Algorithm 1 satisfies ℙP(lim supδ→0τδkl(δ,1−δ)≤T⋆(P))=1.P_P\! ( _δ→ 0 _δkl(δ,1-δ)≤ T (P) )=1. (37) Finally, under Assumption 1, the expected NDPO is identified by θ. Therefore, the δ-correctness and asymptotic optimality of our algorithm for maximizing θ translate directly into δ-correctness and asymptotic optimality for the expected NDPO under Assumption 1. 8 Experiments We evaluate our method on simulations based on synthetic and real-world data. The real-world experiments use two datasets: the IPinYou advertising dataset and the framing dataset from the mediation package. Additional synthetic experiments are reported in Appendix E. These experiments empirically support the validity of the lower bound in Theorem 2, illustrate cases where the arm maximizing [Y|do(X=x)]E[Y|do(X=x)] differs from the expected NDPO-optimal arm, and study sensitivity to gap structure, mediator sparsity, baseline-arm choice, and mediator cardinality. Runtime comparisons are reported in Appendix E.2. Table 1: Stopping-time statistics on the IPinYou. The error rate is the proportion of runs in which the algorithm chooses a suboptimal-arm. Lower values show better performance. Method Median Interquartile range Error TaS-NDPO (ours) 12,928 [4,864, 33,984] 0.00 TaS-NDPO (arm-level) 25,856 [11,520, 38,848] 0.00 Baseline-First 18,304 [8,960, 38,016] 0.01 Uniform 21,248 [9,472, 38,016] 0.00 Dataset. We use the IPinYou dataset [zhang2015realtimebiddingbenchmarkingipinyou], a publicly available benchmark for computational advertising, available at (https://contest.ipinyou.com). The dataset contains approximately N=3.16×106N=3.16× 10^6 ad impressions. From this dataset, we select K=10K=10 creatives with sufficient support (i.e., each with at least 30,000 impressions). The mediator Z corresponds to discretized slot visibility with three levels, and the outcome Y is a binary click indicator. We impose Assumption 1, corresponding to the absence of unmeasured mediator–outcome confounding under treatment interventions, which guarantees identification of the expected NDPO from interventional data. Algorithms. We compare the following algorithms: • TaS-NDPO (ours). Algorithm 1. • TaS-NDPO (arm-level). Variant of TaS-NDPO by replacing cell-level forcing with classical arm-level forced exploration. • Baseline-First. The algorithm first estimates the baseline distribution Px0(z)P_x_0(z) using uniform sampling, and then samples arms uniformly to estimate Px(1|z)P_x(1|z). • Uniform. Uniform sampling over arms combined with the same plug-in estimator and stopping rule as ours. To avoid zero empirical probabilities when some counts are small, we use Laplace smoothing [Manning2008], i.e., P^x(z;t)=(Nx,z(t)+α)/(Nx(t)+α||) P_x(z;t)=(N_x,z(t)+α)/(N_x(t)+α|Z|) with α=0.05α=0.05. Results. We first compare the arms that maximize the interventional mean [Y|do(X=x)]E[Y|do(X=x)] with those that maximize the expected NDPO. On the IPinYou dataset, creative 10,722 (ID) achieves the highest interventional mean, while creative 10,720 maximizes the expected NDPO. Examining mediator distributions reveals that creative 10,722 appears in the top slot 23.7%23.7\% of the time, compared to only 9.9%9.9\% for creative 10,720. Thus, part of its click-rate advantage is mediated through favorable slot positioning, which is removed under the NDPO perspective. We next evaluate all BAI algorithms with a confidence level δ=0.05δ=0.05 over 100 independent runs. Table 1 summarizes stopping time statistics, and Figure 2 reports the empirical cumulative distribution function (ECDF) of stopping times. As shown in Table 1, all methods exhibit empirical error rates below 0.05. Thus, all methods empirically satisfy the δ-correctness requirement. The TaS-NDPO (ours) achieves a median stopping time of 12,928 samples, reducing sample complexity by roughly 50% compared to the arm-level variant (25,856). It also improves upon uniform sampling and the two-stage baseline while maintaining zero empirical error. Figure 2 further illustrates the distributional behavior of the stopping times: the ECDF curve of TaS-NDPO lies uniformly above the alternatives, indicating consistently faster identification across runs. The separation is most pronounced in the lower quantiles, demonstrating that cell-level exploration in our algorithm accelerates early evidence accumulation. These results support that our algorithm substantially improves sample efficiency for identifying the optimal-arm w.r.t. the expected NDPO. 10310^310410^410510^500.20.20.40.40.60.60.80.811Stopping time ttECDFTaS-NDPO (ours)TaS-NDPO (arm-level)Baseline-FirstUniform Figure 2: ECDF of stopping times on the IPinYou. Higher curves correspond to faster identification. Additional real-world validation. We also evaluate the algorithms on the framing dataset from the mediation package at (https://cran.r-project.org/web/packages/mediation/index.html), using the same evaluation protocol as above. Table 2 reports the median stopping time, interquartile range, and empirical error rate. TaS-NDPO achieves the lowest median stopping time and zero empirical error, providing additional real-world validation beyond the IPinYou dataset. Table 2: Stopping-time statistics on the framing dataset. The error rate is the proportion of runs in which the algorithm chooses a suboptimal arm. Lower values show better performance. Method Median Interquartile range Error TaS-NDPO (ours) 5,888 [2,624, 9,408] 0.00 TaS-NDPO (arm-level) 6,400 [3,840, 10,304] 0.00 Baseline-First 8,704 [7,168, 9,984] 0.00 Uniform 7,680 [3,392, 11,518] 0.02 The additional sensitivity experiments in Appendix E show that the benefit of cell-level forcing is regime-dependent. The gains are most substantial in settings with rare mediator–outcome cells, while the arm-level Track-and-Stop variant remains competitive in easier regimes. The gap-scaling experiment varies the NDPO gap while holding the mediator structure fixed. 9 Conclusion We study the fixed-confidence BAI problem of selecting the arm that maximizes the expected NDPO and develop a TaS–based algorithm that is δ-correct and asymptotically optimal. We then evaluate its efficiency through simulation experiments. We focus on the expected NDPO in this paper. Other related quantities include the controlled direct effect and the natural indirect effect, defined as [Yx,z]−[Yx0,z]E[Y_x,z]-E[Y_x_0,z] and [Yx0,Zx]−[Yx0]E[Y_x_0,Z_x]-E[Y_x_0], respectively [Pearl2001]. In Appendix D, we consider the corresponding BAI problems for optimizing [Yx,z]E[Y_x,z] over x (for fixed z) and for optimizing [Yx0,Zx]E[Y_x_0,Z_x] over x. The former reduces to a standard BAI problem, whereas the latter closely parallels our algorithm for the expected NDPO. Furthermore, we focused on the case of a binary outcome since it covers a wide range of applications related to website optimization. Extending our statistical framework to multi-category outcomes (e.g., five-star reviews) is relatively easy. An interesting direction for future work is to extend these ideas to path-specific objectives in more general causal structures [Avin2005, Shpitser2018, Malinsky2019]. Acknowledgements.The authors thank the anonymous reviewers for their time and thoughtful comments. J. Komiyama was supported by the MBZUAI Start-up Fund [BF0121]. References Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis (Supplementary Material) Appendix A Motivating Examples We present motivating examples illustrating why we study the maximization of the expectation of NDPO. Example 1 (Advertisement). We present a motivating example illustrating why we study the maximization of the expectation of NDPO. We consider the problem of selecting an advertisement creative (X) from multiple candidates, where the outcome (Y) represents a click indicator, purchase amount, or conversion. Researchers often select the optimal advertisement by maximizing the expected potential outcome under arm x. In practice, however, an advertisement may improve the outcome Y partly through undesirable mechanisms-for example by exploiting user confusion, eliciting accidental clicks, or leveraging platform-specific presentation artifacts. We treat such undesired factors as a mediator (Z). Improving outcomes primarily by changing Z should not be considered a legitimate success (e.g., due to ethical or regulatory concerns). In reality, for example, 10.1145/3487552.3487850 pointed out the widespread use of misleading and manipulative tactics in online political advertising. The NDPO ignores effects achieved through such undesirable factors. Consequently, selecting the optimal advertisement by maximizing the NDPO leads to fairer advertising decision-making, based purely on the direct effect rather than on effects mediated by undesirable factors. Example 2 (Medicine). In medical decision-making, physicians aim to select treatments that optimally improve patient outcomes. However, some treatments may achieve their effects through adverse intermediate responses (e.g., fever or other adverse reactions). In such cases, it is desirable to evaluate treatment effects that exclude pathways operating through these adverse mediators. Researchers therefore seek to maximize the direct effect, thereby maximizing the treatment benefit while avoiding pathways through these adverse mediators. The indirect effect is also of interest, as it quantifies the effect transmitted through these adverse mediators, and minimizing this effect is another important research objective. In this paper, however, we focus on maximizing the direct effect. Example 3 (Politics). In political decision-making, policymakers often aim to select policies that effectively reduce inflation. However, some policies may achieve this through undesirable mechanisms, such as increasing unemployment or reducing economic growth. In such cases, it may be preferable to evaluate policies based on their effects that exclude these undesirable pathways. Although the direct effect cannot generally be reproduced by real-world interventions, it provides a useful measure of the desirability of treatment policies under a preference for avoiding specific mediating pathways. In some applications, such as political science, researchers may focus on the indirect effect to understand the underlying mechanisms through which an intervention exerts its influence. In contrast, our objective is to identify the treatment policy that is most preferred under this criterion. Example 4 (Education). In educational decision-making, teachers often choose among candidate classes or programs to improve students’ performance. However, some classes may increase test scores through undesirable mechanisms, such as excessively stressful learning environments. In such cases, it may be preferable to evaluate options based on their effects that exclude these undesirable pathways. Example 5 (Legal). In legal decision-making, policymakers often design laws or regulations to reduce crime. However, some policies may achieve this through undesirable mechanisms, such as excessive surveillance. In such cases, it may be preferable to evaluate policies based on their effects that exclude these undesirable pathways. Appendix B Stopping Condition This appendix justifies the stopping rule introduced in Section 6, and in particular the choice of the confidence radius β(t,δ)β(t,δ) ensuring δ-correctness. B.1 Uniform concentration for discrete distributions We begin with a standard concentration inequality for empirical distributions on a finite alphabet. Lemma 1 (Concentration on a finite alphabet). Let P^n P_n be the empirical distribution obtained from n i.i.d. samples drawn from a categorical distribution P supported on an alphabet of size M. Then, for any u>0u>0, Pr(KL(P^n∥P)≥u)≤(n+1)Me−nu. \! (KL( P_n\|P)≥ u )\;≤\;(n+1)^Me^-nu. (38) Lemma 1 is a classical concentration inequality for discrete symbols (see, e.g., Cover2009). Lemma 2 (Concentration on a combination of finite alphabets). Let i=1,2,…,Ii=1,2,…,I for some finite positive integer I. For each i, let P^ni,i P_n_i,i be the empirical distribution obtained from nin_i i.i.d. samples drawn from a categorical distribution PiP_i supported on an alphabet of size MiM_i. Let M=maxiMiM= _iM_i. Then, for any u>0u>0 and for any (n1,n2,…,nI)(n_1,n_2,…,n_I) such that n=∑i=1Inin= _i=1^In_i, Pr(∑i=1IniKL(P^ni,i∥Pi)≥nu)≤(n+1)3MIe−nu \! ( _i=1^In_iKL( P_n_i,i\|P_i)≥ nu )\;≤\;(n+1)^3MIe^-nu (39) holds. Proof. Let V be the number of possible combinations of empirical means (P^n1,1,P^n2,2,…,P^nI,I)( P_n_1,1, P_n_2,2,…, P_n_I,I) such that ∑ini=n _in_i=n. Since there are I empirical distribution of categories at most M and each category’s empirical mean is in 0,1/ni,2/ni,…,1\0,1/n_i,2/n_i,…,1\ such that ni≤n_i≤ n, we have ||≤n2MI|V|≤ n^2MI. Let u=(P^n1,1,P^n2,2,…,P^nI,I)∈:∑i=1IniKL(P^ni,i∥Pi)≥nu.P_u= \( P_n_1,1, P_n_2,2,…, P_n_I,I) : _i=1^In_iKL( P_n_i,i\|P_i)≥ nu \. (40) Then, Lemma 1 states that the probability that each such set of empirical distributions in uP_u realizes is at most ∏i(ni+1)Mie−niu≤(n+1)MIe−nu, _i(n_i+1)^M_ie^-n_iu≤(n+1)^MIe^-nu, (41) and thus Pr(∑i=1IniKL(P^ni,i∥Pi)≥nu) \! ( _i=1^In_iKL( P_n_i,i\|P_i)≥ nu ) ≤|u|×(The right-hand side of (41)) ≤|P_u|×(The right-hand side of ineq_singlecomb) (42) ≤n2MI×(n+1)MIe−nu ≤ n^2MI×(n+1)^MIe^-nu (43) ≤(n+1)3MIe−nu. ≤(n+1)^3MIe^-nu. (44) ∎ B.2 Application to mediator and outcome distributions We apply Lemma 2 to both components of the causal model. For each arm x, let P^Z|x,n P_Z|x,n denote the empirical distribution of the mediator Z after n pulls of arm x. Let MZ:=||M_Z:=|Z| and MY:=||M_Y:=|Y| denote the alphabet sizes of the mediator and outcome, respectively. In our setting MY=2<MZM_Y=2<M_Z. Time-uniform confidence allocation. To obtain bounds that hold uniformly over all t≥1t≥ 1, define δt:=δπ2t2+2KMZ. _t:= δπ^2t^2+2KM_Z. (45) Since ∑t=1∞1/(π2t2)≤1 _t=1^∞1/(π^2t^2)≤ 1, a union bound over all t and all possible combinations of (Nx(t),Nx,z(t))(N_x(t),N_x,z(t)) (number of such possible combinations is at most t2KMZt^2KM_Z) yields an event of probability at least 1−δ1-δ. Namely, by setting β(t,δ) β(t,δ) =log(π2t2+2KMZδ)+6MZKlog(t+1), = ( π^2t^2+2KM_Zδ )+6M_ZK (t+1), (46) we have ∀tℒt(Q)≤β(t,δ) ∀ t\L_t(Q)≤β(t,δ)\ (47) holds with probability at least 1−δ1-δ. Appendix C IMPLEMENTATION DETAILS FOR THE REDUCED INNER OPTIMIZATION This appendix describes the numerical solution of the reduced inner optimization problem appearing in the plug-in allocation (20) and in the GLRT statistic (29), after reduction to a single competitor and restriction to the relevant arms. C.1 Reduced weighted inner problem Fix a competitor x′≠x⋆x ≠ x and let γ0:=wx0,αs,z:=wx⋆P^x⋆(z),αp,z:=wx′P^x′(z), _0:=w_x_0, _s,z:=w_x \, P_x (z), _p,z:=w_x \, P_x (z), (48) where w denotes the current allocation vector. Let P0(z):=P^x0(z),ps(z):=P^x⋆(1|z),p(z):=P^x′(1|z).P_0(z):= P_x_0(z), p_s(z):= P_x (1|z), p_p(z):= P_x (1|z). (49) After the three-arm reduction (Section 6.2), the inner problem reduces to minq0∈Δ()qs,qp∈(0,1)|| _ subarraycq_0∈ (Z)\\ q_s,q_p∈(0,1)^|Z| subarray γ0KL(P0∥q0)+∑z∈αs,zKL(ps(z)∥qs(z)) _0\,KL(P_0\|q_0)+ _z _s,z\,KL(p_s(z)\|q_s(z)) +∑z∈αp,zKL(p(z)∥qp(z)) + _z _p,z\,KL(p_p(z)\|q_p(z)) (50) s.t. ∑z∈q0(z)(qp(z)−qs(z))≥ 0. _z q_0(z)\,(q_p(z)-q_s(z))\;≥\;0. (51) The feasible set is compact and the objective is continuous. Moreover, the problem is convex in (qs,qp)(q_s,q_p) for fixed q0q_0 and convex in q0q_0 for fixed (qs,qp)(q_s,q_p), but not jointly convex. We solve (50)–(51) via block coordinate descent (alternating optimization). C.2 Update of (qs,qp)(q_s,q_p) for fixed q0q_0 For fixed q0q_0, the subproblem in (qs,qp)(q_s,q_p) is convex: minqs,qp _q_s,q_p ∑zαs,zKL(ps(z)∥qs(z))+∑zαp,zKL(p(z)∥qp(z)) _z _s,z\,KL(p_s(z)\|q_s(z))+ _z _p,z\,KL(p_p(z)\|q_p(z)) (52) s.t. ∑zq0(z)(qp(z)−qs(z))≥0. _zq_0(z)(q_p(z)-q_s(z))≥ 0. If the constraint is inactive at the unconstrained minimizer (qs,qp)=(ps,p)(q_s,q_p)=(p_s,p_p), then this is the solution. Otherwise, the constraint is active and we introduce a Lagrange multiplier λ≥0λ≥ 0. For each z, the subproblem separates and we must solve minq∈(0,1)αKL(p∥q)+bq, _q∈(0,1)α\,KL(p\|q)+b\,q, (53) where b=λq0(z)b=λ q_0(z) (with opposite signs for qsq_s and qpq_p). Using ∂qKL(p∥q)=q−pq(1−q), ∂ qKL(p\|q)= q-pq(1-q), (54) the stationarity condition yields the quadratic equation bq2−(α+b)q+αp=0.bq^2-(α+b)q+α p=0. (55) Among its real roots in (0,1)(0,1), the one minimizing the objective is selected. The multiplier λ is chosen by one-dimensional bisection so that the constraint (51) holds with equality when active. Monotonicity of the constraint function in λ ensures existence and uniqueness of the solution. C.3 Update of q0q_0 for fixed (qs,qp)(q_s,q_p) For fixed (qs,qp)(q_s,q_p), define d(z):=qp(z)−qs(z).d(z):=q_p(z)-q_s(z). (56) The subproblem in q0q_0 is minq0∈Δ() _q_0∈ (Z) KL(P0∥q0) s.t. ∑zq0(z)d(z)≥0. (P_0\|q_0) s.t. _zq_0(z)\,d(z)≥ 0. (57) If the constraint is satisfied at q0=P0q_0=P_0, then this is optimal. Otherwise, introducing a multiplier μ≥0μ≥ 0 and using KKT conditions yields the closed-form solution q0(z)=P0(z)ν−μd(z),q_0(z)= P_0(z)ν-μ d(z), (58) where ν is determined by the normalization condition ∑zq0(z)=1 _zq_0(z)=1. The multiplier μ is obtained by one-dimensional bisection so that the constraint holds with equality when active. C.4 Alternating optimization and convergence The algorithm alternates between: • updating (qs,qp)(q_s,q_p) given q0q_0, • updating q0q_0 given (qs,qp)(q_s,q_p). Each block subproblem is solved exactly and is convex. The objective in (50) is non-increasing at every iteration, and the feasible set is compact. Therefore, by standard results on block coordinate descent for bi-convex problems [Tseng2001], every limit point of the sequence is a stationary point of (50)–(51). In practice, the dimensionality is O(||)O(|Z|) and convergence is rapid. This procedure is used both in the plug-in allocation computation and in evaluation of the GLRT statistic. Appendix D BAI Algorithms for other mediation measures Finding the best arm in terms of [Yx,z]E[Y_x,z], which is the first term of the controlled direct effect (CDE) at Z=zZ=z, is relatively straightforward using a best arm identification algorithm. For ease of discussion, let us consider [Yx,z]E[Y_x,z] at z=1z=1 P[Yx,z=1].E_P\! [Y_x,z=1 ]. (59) This boils down to standard bandits/BAI but we only count the sample when it is shown at a specific position z=1z=1. Namely, Nx(t)=∑s=1tXt=x,Z=1,P^x(t)=∑s=1tYtXt=x,Z=1Nx(t) N_x(t)= _s=1^t1\X_t=x,Z=1\, P_x(t)= _s=1^tY_t1\X_t=x,Z=1\N_x(t) (60) and one can run Track-and-Stop or Top-two Thompson sampling [russottts] based on these statistics. Regarding the Natural Indirect effect (NIE), the first term of NDE is P[Yx0,Zx]=∑zPx0(1|z)Px(z). _P\! [Y_x_0,Z_x ]= _zP_x_0(1|z)P_x(z). (61) We can consider the alternative distributions as: Alt(P) (P) :=Q∈:∃x≠x∗(P) such that ∑z∈Qx0(1|z)Qx(z)>∑z∈Qx0(1|z)Qx∗(P)(z). := \Q :∃ x≠ x^*(P) such that _z Q_x_0(1|z)Q_x(z)> _z Q_x_0(1|z)Q_x^*(P)(z) \. (62) We hypothesize that our Track-and-Stop algorithm with a cutting-plane procedure (Section 6.2) can also achieve asymptotically optimal sample complexity for identifying the best arm w.r.t. the [Yx0,Zx]E[Y_x_0,Z_x]-criterion. In summary, finding the best arm for [Yx,z]E[Y_x,z] is straightforward. Finding the best arm for [Yx0,Zx]E[Y_x_0,Z_x] can be done using our framework. Appendix E Synthetic Experiments In this appendix, we conduct synthetic experiments. Setting. We consider instances with K=3K=3 arms and M=3M=3 mediator values. Full parameter specifications are as follows: Let x0=0x_0=0 and =0,1,2Z=\0,1,2\. Fix P0(Z)=(0.8,0.15,0.05)P_0(Z)=(0.8,0.15,0.05). Let P(Z|X=1)=(0.1,0.2,0.7)P(Z|X=1)=(0.1,0.2,0.7) and P(Z|X=2)=P(Z|X=0)=P0(Z)P(Z|X=2)=P(Z|X=0)=P_0(Z). Set P(Y=1|X=0,Z=z)=0.2P(Y=1|X=0,Z=z)=0.2, P(Y=1|X=1,Z∈0,1)=0.2P(Y=1|X=1,Z∈\0,1\)=0.2, P(Y=1|X=1,Z=2)=0.9P(Y=1|X=1,Z=2)=0.9, and P(Y=1|X=2,Z=z)=0.235+ΔP(Y=1|X=2,Z=z)=0.235+ for all z. Then θ(1)=0.235θ(1)=0.235 and θ(2)=0.235+Δθ(2)=0.235+ , so the expected NDPO gap equals Δ , while [Y1]=0.69E[Y_1]=0.69 is the largest interventional mean. To avoid zero empirical probabilities when some counts are small, we use Laplace smoothing [Manning2008], i.e., P^x(z;t)=(Nx,z(t)+α)/(Nx(t)+α||) P_x(z;t)=(N_x,z(t)+α)/(N_x(t)+α|Z|) with α=0.05α=0.05. All methods use the same confidence level δ=0.05δ=0.05 and the same stopping threshold β(t,δ)β(t,δ) from Appendix B. Optimization tolerances and forcing schedules are matched whenever applicable. Performance was robust to moderate changes in these settings. Algorithms. We compare the following algorithms: • TaS-NDPO (ours). Algorithm 1. • TaS-NDPO (arm-level). Variant of TaS-NDPO by replacing cell-level forcing with classical arm-level forced exploration. • Baseline-First. The algorithm first estimates the baseline distribution Px0(z)P_x_0(z) using uniform sampling, and then samples arms uniformly to estimate Px(1|z)P_x(1|z). • Uniform. Uniform sampling over arms combined with the same plug-in estimator and stopping rule as ours. • TaS-IM (diagnostic). TaS algorithm for optimizing the interventional mean (IM) [Yx]E[Y_x]. Gap-scaling family. Mediator distributions are fixed while the NDPO gap Δ:=θ(x⋆)−maxx≠x⋆θ(x) :=θ(x )- _x≠ x θ(x) (63) is controlled through the outcome model of arm 2. This isolates the effect of gap magnitude. To validate Theorem 2, we vary Δ and measure the median stopping time. Figure 3 shows log–log scaling. The empirical slope aligns with the reference 1/Δ21/ ^2, confirming the predicted instance-dependent complexity. Figure 3: Median stopping time vs. NDPO gap Δ (log–log scale). Dashed line: 1/Δ21/ ^2. Decision differences. In this model, the interventional-mean-optimal arm differs from the expected NDPO-optimal arm. TaS-IM selects arm 1, while TaS-NDPO consistently identifies arm 2, demonstrating that optimizing expected NDPO can lead to different decisions. E.1 Additional sensitivity experiments We further evaluate the effect of mediator sparsity, mediator cardinality, and baseline-arm choice. The gap-scaling experiment above varies the NDPO gap while holding the mediator structure fixed. In contrast, the experiments below vary the mediator structure or the reference arm. Overall, the results show that the advantage of cell-level forcing is regime-dependent, with substantial gains in settings with rare mediator–outcome cells. The arm-level Track-and-Stop baseline already represents a strong adaptive method and performs well in easier regimes. Mediator sparsity. Table 3 reports median stopping times as the mediator sparsity parameter η varies. Smaller values of η correspond to rarer mediator–outcome cells. Our method is best or tied for best across all values of η. The improvement over arm-level forcing becomes more pronounced as rare cells become important, showing the benefit of explicit cell-level forcing in sparse mediator regimes. Table 3: Median stopping time as a function of mediator sparsity η. Lower is better. Bold indicates the best method for each η. η TaS-NDPO (ours) TaS-NDPO (arm-level) Uniform Baseline-First 0.5 2048 2048 2560 6912 0.1 20368 20608 28928 21664 0.05 29184 36864 33664 31960 0.01 36480 47104 46080 41216 0.005 41216 57088 46208 47520 0.001 45056 54528 47616 49024 Mediator cardinality. Table 4 reports median stopping times as the number of mediator values M varies. The results are not monotone in M, confirming that the benefit of cell-level forcing depends on the structure of the instance. Our method performs best for M=2M=2 and M=16M=16, while the arm-level variant is best for M=8M=8 and Baseline-First is slightly better for M=4M=4. This shows that arm-level exploration can be competitive in easier regimes, whereas cell-level forcing is most useful when the relevant mediator–outcome cells drive the difficulty of identification. Table 4: Median stopping time as a function of mediator cardinality M. Lower is better. Bold indicates the best method for each M. M TaS-NDPO (ours) TaS-NDPO (arm-level) Uniform Baseline-First 2 13312 15360 15872 13440 4 21632 23592 25432 21504 8 21504 14976 18560 19584 16 10752 20864 22016 22016 Baseline-arm choice. Table 5 reports median stopping times for different choices of the baseline arm x0x_0. Changing x0x_0 changes the expected NDPO target and may also change the NDPO-best arm. For x0=0x_0=0, the instance is harder and our method achieves the smallest stopping time. For x0=1x_0=1 and x0=2x_0=2, the instance is easier, and TaS-NDPO, the arm-level variant, and Uniform all stop at the same median time. Baseline-First is slower in these easy cases because it separately estimates the baseline distribution before sampling the remaining arms. Table 5: Median stopping time as a function of baseline-arm choice x0x_0. Lower is better. Bold indicates the best method for each baseline choice in a 4-arm instance. x0x_0 NDPO best arm TaS-NDPO (ours) TaS-NDPO (arm-level) Uniform Baseline-First 0 3 59904 69248 70144 61952 1 1 512 512 512 5376 2 2 512 512 512 5376 E.2 Runtime comparison We also measure the wall-clock runtime of each method. Table 6 compares statistical efficiency, measured by median stopping time, with computational cost, measured by average runtime per run. TaS-NDPO incurs a moderate computational overhead relative to non-adaptive baselines, but its runtime is comparable to the arm-level adaptive baseline and it achieves the lowest median stopping time. Table 6: Comparison of statistical efficiency and computational cost. The median stopping time measures sample complexity, and the average runtime is measured in seconds per run. Lower is better. Method Median stopping time Average runtime (s) TaS-NDPO (ours) 36,480 22.5 TaS-NDPO (arm-level) 47,104 25.3 Uniform 46,080 6.75 Baseline-First 46,336 6.43 Appendix F Proofs In this appendix, we provide the proofs of the theorems, propositions, and lemmas stated in the main text. F.1 Proof of Theorem 1 * Proof. Under Assumption 1, we have [Yx,Zx0] [Y_x,Z_x_0] (64) =∑y,zyℙ(Yx,z=y|Zx0=z)ℙ(Zx0=z) = _y,zyP(Y_x,z=y|Z_x_0=z)P(Z_x_0=z) =∑y,zyℙ(Yx,z=y)ℙ(Zx0=z)(∵Assumption 1) = _y,zyP(Y_x,z=y)P(Z_x_0=z)( idenNDE) =∑y,zyℙ(Yx,z=y|Zx=z)ℙ(Zx0=z)(∵Assumption 1) = _y,zyP(Y_x,z=y|Z_x=z)P(Z_x_0=z)( idenNDE) =∑y,zyℙ(Yx=y|Zx=z)ℙ(Zx0=z)(∵Counterfactual Consistency) = _y,zyP(Y_x=y|Z_x=z)P(Z_x_0=z)( Consistency) =∑y,zyℙ(Y=y|Z=z,do(X=x))ℙ(Z=z|do(X=x0)). = _y,zyP(Y=y|Z=z,do(X=x))P(Z=z|do(X=x_0)). Then, we have the theorem. ∎ F.2 Proof of Theorem 2 * Proof. The proof follows the standard change-of-measure argument [lairobbins1985]. Let Nx(t)N_x(t) denote the (random) number of times arm x is sampled up to time t, and let τδ _δ be the stopping time of a δ-correct algorithm. For any alternative model Q∈Alt(P)Q (P), the transportation inequality (Lemma 1 in garivier2016optimalbestarmidentification) yields ∑x=0K−1P[Nx(τδ)]KL(Px∥Qx)≥kl(δ,1−δ), _x=0^K-1E_P\! [N_x( _δ) ]KL(P_x\|Q_x)\;≥\;kl(δ,1-δ), (65) where PxP_x and QxQ_x denote the joint distributions of (Z,Y)(Z,Y) under arm x for models P and Q, respectively. Define the sampling proportions wx:=P[Nx(τδ)]P[τδ],∑xwx=1.w_x:= E_P[N_x( _δ)]E_P[ _δ], _xw_x=1. (66) Dividing both sides by P[τδ]E_P[ _δ] gives P[τδ]∑xwxKL(Px∥Qx)≥kl(δ,1−δ).E_P[ _δ] _xw_xKL(P_x\|Q_x)\;≥\;kl(δ,1-δ). (67) Under the joint mediator–outcome observation model, the KL divergence for a fixed arm x decomposes as KL(Px∥Qx)=∑z∈Pz|xKL(PY|x,z∥QY|x,z)+KL(PZ|x∥QZ|x).KL(P_x\|Q_x)= _z P_z|xKL\! (P_Y|x,z\|Q_Y|x,z )+KL\! (P_Z|x\|Q_Z|x ). (68) Substituting this decomposition yields P[τδ]≥kl(δ,1−δ)∑xwx[∑zPz|xKL(PY|x,z∥QY|x,z)+KL(PZ|x∥QZ|x)].E_P[ _δ]≥ kl(δ,1-δ) _xw_x[ _zP_z|xKL(P_Y|x,z\|Q_Y|x,z)+KL(P_Z|x\|Q_Z|x)]. (69) Since the above bound holds for all Q∈Alt(P)Q (P), we may take the infimum over Q, and since the strategy is arbitrary, we may take the supremum over w∈ΣKw∈ _K. Thus, P[τδ]≥kl(δ,1−δ)supw∈ΣKinfQ∈Alt(P)∑xwxKL(Px∥Qx).E_P[ _δ]≥ kl(δ,1-δ) _w∈ _K _Q (P) _xw_xKL(P_x\|Q_x). (70) Finally, using the inequality DBLP:journals/jmlr/KaufmannCG16 of kl(δ,1−δ)≥log(1/(2.4δ))=log(1/δ)+Θ(1)kl(δ,1-δ)≥ (1/(2.4δ))= (1/δ)+ (1) completes the proof. ∎ F.3 Proof of Proposition 6.2 * Proof. The constraint depends only on Qx0,Qx⋆(P),Qx′Q_x_0,Q_x (P),Q_x . For any a∉x0,x⋆(P),x′a∉\x_0,x (P),x \, the term KL(Pa∥Qa)KL(P_a\|Q_a) is uniquely minimized at Qa=PaQ_a=P_a by strict convexity of KL divergence. Any deviation from PaP_a strictly increases the objective while leaving the constraint unchanged, and hence cannot be optimal. ∎ F.4 Proof of Proposition 6.2 * Proof. For fixed q0q_0, the objective is a sum of KL divergences in r⋆r and r′r , which are convex functions. The constraint (26) is affine in (r⋆,r′)(r ,r ) when q0q_0 is fixed. Similarly, for fixed (r⋆,r′)(r ,r ), the objective is convex in q0q_0, and the constraint is affine in q0q_0. Joint convexity fails due to bilinearity of the constraint. ∎ F.5 Proofs for Section 7 Throughout, fix a true model P∈P . Recall that for each arm x∈x , pulling x yields i.i.d. samples (Zt,Yt)∼Px(Z_t,Y_t) P_x, and that the algorithm is adaptive but non-anticipating. We use ℙPP_P and PE_P for probability and expectation under P. We also recall the empirical joint model P^(t)=(P^x(t))x∈ P(t)=( P_x(t))_x , where P^x(t) P_x(t) is the empirical distribution of (Z,Y)(Z,Y) under arm x up to time t. For Q∈Q , define the negative log-likelihood ratio ℒt(Q)=∑x∈Nx(t)KL(P^x(t)∥Qx),L_t(Q)= _x N_x(t)\,KL( P_x(t)\|Q_x), (71) which is equivalent to the decomposed form used in (29). The GLRT statistic is Zt(x,y)=infQ∈:θQ(x)≥θQ(y)ℒt(Q).Z_t(x,y)= _Q :\ _Q(x)≥ _Q(y)L_t(Q). (72) F.5.1 Proof of Theorem 3 (δ-correctness) * Proof. For each t≥1t≥ 1, define the likelihood-based confidence set t:=Q∈:ℒt(Q)≤β(t,δ).U_t:= \Q :\ L_t(Q)≤β(t,δ) \. (73) Step 1: time-uniform containment of the true model. By the uniform concentration inequality stated and proven in Appendix B, the threshold β(t,δ)β(t,δ) can be chosen so that ℙP(P∈tfor all t≥1)≥1−δ.P_P\! (P _t\ for all t≥ 1 )≥ 1-δ. (74) Let ℰ:=P∈t∀t≥1E:=\P _t\ ∀ t≥ 1\ denote this event. Step 2: stopping implies no alternative remains in tU_t. Fix t≥1t≥ 1 and an arm x≠x^(t)x≠ x(t). By definition, Zt(x,x^(t))=infQ:θQ(x)≥θQ(x^(t))ℒt(Q).Z_t(x, x(t))= _Q:\ _Q(x)≥ _Q( x(t))L_t(Q). (75) Hence the condition Zt(x,x^(t))≥β(t,δ)Z_t(x, x(t))≥β(t,δ) implies that for every Q such that θQ(x)≥θQ(x^(t)) _Q(x)≥ _Q( x(t)) we have ℒt(Q)≥β(t,δ)L_t(Q)≥β(t,δ), i.e., no such Q lies in tU_t. Equivalently, ∀Q∈t:θQ(x^(t))≥θQ(x).∀ Q _t: _Q( x(t))≥ _Q(x). (76) At the stopping time τδ _δ, the algorithm stops only if minx≠x^(τδ)Zτδ(x,x^(τδ))≥β(τδ,δ), _x≠ x( _δ)Z_ _δ(x, x( _δ))≥β( _δ,δ), (77) so (76) holds for all competitors x≠x^(τδ)x≠ x( _δ). Thus, for all Q∈τδQ _ _δ, θQ(x^(τδ))≥θQ(x)∀x≠x^(τδ), _Q( x( _δ))≥ _Q(x) ∀ x≠ x( _δ), (78) which means x^(τδ)∈argmaxx∈θQ(x) x( _δ)∈ _x _Q(x) for every Q∈τδQ _ _δ if τδ<∞ _δ<∞. Step 3: correctness on the event ℰE. On the event ℰE, we have P∈τδP _ _δ (since τδ≥1 _δ≥ 1), and by Assumption 2, the conclusion above gives x^(τδ)=x⋆(P) x( _δ)=x (P) on ℰE. Therefore, ℙP(x^(τδ)≠x⋆(P),τδ<∞)≤ℙP(ℰc)≤δ,P_P( x( _δ)≠ x (P), _δ<∞) _P(E^c)≤δ, (79) using (74). This proves δ-correctness. ∎ F.5.2 Proof of Lemma 4 * Proof. Fix an arm x∈x . We first show that Nx(t)→∞N_x(t)→∞ almost surely. Step 1: x enters the relevant set infinitely often. Let Cx(t)=∑s=1tx′(s)=xC_x(t)= _s=1^t1\x (s)=x\ be the competitor counter. By construction of the competitor-coverage rule, for every t, minu∈Cu(t)≥h(t)−1. _u C_u(t)\ ≥\ h(t)-1. (80) In particular, Cx(t)≥h(t)−1C_x(t)≥ h(t)-1 for all sufficiently large t, hence Cx(t)→∞C_x(t)→∞. Moreover, whenever x′(s)=x (s)=x we have x∈rel(s)x _rel(s). Therefore, x belongs to rel(t)A_rel(t) infinitely often. Step 2: contradiction argument for Nx(t)N_x(t). Suppose by contradiction that Nx(t)N_x(t) is bounded on some event E with ℙP(E)>0P_P(E)>0. Then there exists B<∞B<∞ such that on E, Nx(t)≤B∀t,and hencemx(t):=minz∈Nx,z(t)≤Nx(t)≤B∀t.N_x(t)≤ B\ \ ∀ t, hence m_x(t):= _z N_x,z(t)≤ N_x(t)≤ B\ \ ∀ t. (81) Since g(t)→∞g(t)→∞ and is nondecreasing, there exists T such that g(t)>Bg(t)>B for all t≥Tt≥ T. Thus, on E, for every t≥Tt≥ T with x∈rel(t)x _rel(t) we have mx(t)<g(t)m_x(t)<g(t), i.e., x∈(t)x (t). Let :=t≥T:x∈rel(t).T:=\t≥ T:\ x _rel(t)\. (82) By Step 1, T is infinite. For each t∈t , the set (t)D(t) is nonempty and the forcing rule selects Xt+1∈argminu∈(t)(mu(t),Nu(t)).X_t+1∈ _u (t) (m_u(t),\,N_u(t) ). (83) Assume that on E the arm x is selected only finitely many times. Then there exists T′≥T ≥ T such that for all t∈t with t≥T′t≥ T , the forced choice satisfies Xt+1≠xX_t+1≠ x. Since only finitely many arms exist, there must be an arm u⋆≠xu ≠ x that is selected infinitely often among these forcing rounds. By Assumption 3, Pu⋆(z)>0P_u (z)>0 for all z, and hence, conditional on selecting arm u⋆u infinitely often, the strong law yields Nu⋆,z(t)→∞N_u ,z(t)→∞ for every z, so in particular mu⋆(t)→∞m_u (t)→∞ almost surely. Therefore, on E we have mu⋆(t)>Bm_u (t)>B for all sufficiently large t. But for all t we also have mx(t)≤Bm_x(t)≤ B. Hence, for all sufficiently large t∈t , the arm x satisfies mx(t)<mu⋆(t)m_x(t)<m_u (t) and belongs to (t)D(t), so x must be chosen by the minimization of mu(t)m_u(t) in the forcing rule, a contradiction. We conclude that Nx(t)→∞N_x(t)→∞ almost surely. Step 3: divergence of all cell counts. Fix z∈z . Consider the subsequence of rounds at which Xs=xX_s=x. Conditional on these pull times, the mediator observations are i.i.d. with law Px(⋅)P_x(·). By the strong law of large numbers applied to Z=z1\Z=z\ along this subsequence, Nx,z(t)Nx(t)→Px(z)almost surely. N_x,z(t)N_x(t)→ P_x(z) surely. (84) By Assumption 3, Px(z)>0P_x(z)>0, and since Nx(t)→∞N_x(t)→∞, it follows that Nx,z(t)→∞N_x,z(t)→∞ almost surely. Since x and z were arbitrary, the claim holds for all (x,z)(x,z). ∎ F.5.3 Proof of Lemma 4 * Proof. Define for any model R∈R and w∈ΣKw∈ _K, ΦR(w):=infQ∈Alt(R)∑x∈wxKL(Rx∥Qx),Alt(R):=Q∈:x⋆(Q)≠x⋆(R). _R(w):= _Q (R) _x w_x\,KL(R_x\|Q_x), (R):=\Q :\ x (Q)≠ x (R)\. (85) By definition, w^(t)∈argmaxw∈ΣKΦP^(t)(w) w(t)∈ *arg\,max_w∈ _K _ P(t)(w). Step 1: Stabilization of the plug-in best arm. Since x⋆(P)x (P) is unique, there exists a gap Δ:=θP(x⋆(P))−maxx≠x⋆(P)θP(x)> 0, := _P(x (P))- _x≠ x (P) _P(x)\;>\;0, (86) where θP(x) _P(x) denotes the objective value of arm x under model P. Because θR(x) _R(x) is a continuous function of R on P (it is a finite sum/product of probabilities on a finite alphabet), P^(t)→P P(t)→ P almost surely implies θP^(t)(x)→θP(x) _ P(t)(x)→ _P(x) for every x. Hence, on an event of probability one, there exists a (random) time T0T_0 such that for all t≥T0t≥ T_0, θP^(t)(x⋆(P))>maxx≠x⋆(P)θP^(t)(x), _ P(t)(x (P))> _x≠ x (P) _ P(t)(x), (87) which implies x^(t)=x⋆(P^(t))=x⋆(P) x(t)=x ( P(t))=x (P) for all t≥T0t≥ T_0. Step 2: For large t, the alternative set becomes fixed. On the same event, for all t≥T0t≥ T_0 we have Alt(P^(t))=Q∈:x⋆(Q)≠x^(t)=Q∈:x⋆(Q)≠x⋆(P)=:Alt⋆,Alt( P(t))=\Q :\ x (Q)≠ x(t)\=\Q :\ x (Q)≠ x (P)\=:Alt , (88) which no longer depends on t. We now work on t≥T0t≥ T_0 and treat Alt⋆Alt as fixed. Step 3: Compactness of Alt⋆Alt . Since P is a product of simplices over a finite alphabet, it is compact. Moreover, for each x≠x⋆(P)x≠ x (P), the set x:=Q∈:θQ(x)≥θQ(x⋆(P))C_x:=\Q :\ _Q(x)≥ _Q(x (P))\ (89) is closed because θQ(⋅) _Q(·) is continuous in Q. Therefore Alt⋆=⋃x≠x⋆(P)xAlt = _x≠ x (P)C_x (90) is a finite union of closed sets, hence closed, and thus compact as a closed subset of compact P. Step 4: Continuity of the value function on a fixed alternative set. Fix w∈ΣKw∈ _K and define G(R,w,Q):=∑x∈wxKL(Rx∥Qx),Q∈Alt⋆.G(R,w,Q):= _x w_x\,KL(R_x\|Q_x), Q . (91) Under Assumption 3, all probabilities involved are bounded away from 0 and 11 uniformly over R,Q∈R,Q . Hence KL(Rx∥Qx)KL(R_x\|Q_x) is finite and continuous in (R,Q)(R,Q) for each x, and therefore G is continuous in (R,w,Q)(R,w,Q) on ×ΣK×Alt⋆P× _K×Alt . Since Alt⋆Alt is compact, the value function Φ~R(w):=infQ∈Alt⋆G(R,w,Q) _R(w):= _Q G(R,w,Q) (92) is continuous in (R,w)(R,w) by Berge’s maximum theorem. Step 5: Continuity of the argmax and convergence of w^(t) w(t). Define f(R,w):=Φ~R(w)f(R,w):= _R(w) on ×ΣKP× _K. We have shown f is continuous and ΣK _K is compact. Let w∗(P)w^*(P) denote the unique maximizer of w↦f(P,w)w f(P,w). Consider any sequence tn→∞t_n→∞ and write Rn:=P^(tn)R_n:= P(t_n) and wn:=w^(tn)w_n:= w(t_n). By compactness of ΣK _K, (wn)(w_n) has a convergent subsequence (not relabeled) with limit w¯∈ΣK w∈ _K. On the almost sure event where P^(t)→P P(t)→ P and tn≥T0t_n≥ T_0 eventually, we have Rn→PR_n→ P and Alt(P^(tn))=Alt⋆Alt( P(t_n))=Alt for all large n. Since wnw_n maximizes f(Rn,⋅)f(R_n,·), f(Rn,wn)≥f(Rn,w)for all w∈ΣK.f(R_n,w_n)≥ f(R_n,w) all w∈ _K. (93) Taking limits along the convergent subsequence and using continuity of f gives f(P,w¯)≥f(P,w)for all w∈ΣK,f(P, w)≥ f(P,w) all w∈ _K, (94) so w¯∈argmaxw∈ΣKf(P,w)=w∗(P) w∈ *arg\,max_w∈ _Kf(P,w)=\w^*(P)\ by uniqueness. Hence w¯=w∗(P) w=w^*(P). Because every convergent subsequence of (w^(t))( w(t)) has the same limit w∗(P)w^*(P), it follows that w^(t)→w∗(P) w(t)→ w^*(P) almost surely. ∎ F.5.4 Proof of Lemma 4 * Proof. Write F(t)=Fcov(t)+Fcell(t)F(t)=F_cov(t)+F_cell(t), where Fcov(t)F_cov(t) (resp. Fcell(t)F_cell(t)) counts the rounds up to t on which competitor coverage (resp. cell-level forcing) is active. Step 1: competitor coverage is deterministically O(h(t))O(h(t)). Recall Cx(t)=∑s=1tx′(s)=xC_x(t)= _s=1^t1\x (s)=x\ and the coverage rule that, whenever minxCx(t−1)<h(t) _xC_x(t-1)<h(t), selects x′(t)x (t) among arms with Cx(t−1)<h(t)C_x(t-1)<h(t) and increments only that counter. Thus, for each arm x, the rule can select x under the condition Cx(t−1)<h(t)C_x(t-1)<h(t) at most h(t)h(t) times up to time t. Summing over K:=||K:=|X| arms yields the deterministic bound Fcov(t)≤∑x∈Cx(t) 1Cx(t)<h(t)+1≤Kh(t)+K,F_cov(t)≤ _x C_x(t)\,1\C_x(t)<h(t)+1\≤ K\,h(t)+K, (95) hence Fcov(t)=O(h(t))F_cov(t)=O(h(t)) and therefore Fcov(t)=o(t)F_cov(t)=o(t) since a∈(0,1)a∈(0,1). Step 2: cell-level forcing is O(g(t))O(g(t)) almost surely. Fix an arm x∈x and define the cell counts Nx,z(t)=∑s≤tXs=x,Zs=zN_x,z(t)= _s≤ t1\X_s=x,Z_s=z\ and Nx(t)=∑zNx,z(t)N_x(t)= _zN_x,z(t). Let pmin:=minx∈,z∈Px(z)∈(0,1)p_ := _x ,\;z P_x(z)∈(0,1) (96) which exists and is strictly positive by Assumption 3. Consider the event ℰx:=∀z∈:limn→∞Nx,z(tn)n=Px(z)along the pull times of x.E_x:=\∀ z :\; _n→∞ N_x,z(t_n)n=P_x(z)\ along the pull times of $x$\. (97) By the strong law of large numbers applied to the i.i.d. mediator draws under repeated pulls of x, we have ℙ(ℰx)=1P(E_x)=1. On ℰxE_x, there exists an (a.s. finite) random time TxT_x such that for all t≥Txt≥ T_x and all z∈z , Nx,z(t)≥pmin2Nx(t).N_x,z(t)\ ≥\ p_ 2\,N_x(t). (⋆ ) Consequently, for t≥Txt≥ T_x, mx(t):=minz∈Nx,z(t)≥pmin2Nx(t).m_x(t):= _z N_x,z(t)\ ≥\ p_ 2\,N_x(t). (98) Therefore, if x is cell-deficient at time t≥Txt≥ T_x, i.e. mx(t)<g(t)m_x(t)<g(t), then necessarily Nx(t)<2pming(t).N_x(t)\ <\ 2p_ \,g(t). († ) Now let Fcell,x(t)F_cell,x(t) be the number of times up to t that the algorithm selects arm x because of cell-level forcing. Trivially, Fcell,x(t)≤Nx(t)F_cell,x(t)≤ N_x(t). Moreover, once († ‣ F.5.4) fails (i.e. once Nx(t)≥2pming(t)N_x(t)≥ 2p_ g(t)) and t≥Txt≥ T_x, the arm x cannot be cell-deficient anymore, hence it cannot be selected due to cell forcing. Thus, on ℰxE_x and for all large enough t, Fcell,x(t)≤2pming(t)+Tx.F_cell,x(t)\ ≤\ 2p_ \,g(t)+T_x. (99) Summing over all x∈x and using finiteness of X gives, on ⋂xℰx _xE_x (an event of probability one), Fcell(t)=∑x∈Fcell,x(t)≤2Kpming(t)+∑x∈Tx=O(g(t))a.s.F_cell(t)= _x F_cell,x(t)\ ≤\ 2Kp_ \,g(t)+ _x T_x\ =\ O(g(t)) .s. (100) Since g(t)=o(h(t))g(t)=o(h(t)) and h(t)=tah(t)=t^a with a∈(0,1)a∈(0,1), we have g(t)=o(t)g(t)=o(t) and hence Fcell(t)=o(t)F_cell(t)=o(t) almost surely. Step 3: conclusion. Combining the bounds yields, almost surely, F(t)=Fcov(t)+Fcell(t)=O(h(t))+O(g(t))=o(t).F(t)=F_cov(t)+F_cell(t)=O(h(t))+O(g(t))=o(t). (101) ∎ F.5.5 Proof of Lemma 4 * Proof. We work on the almost sure event on which both w^(t)→w∗(P)andF(t)=o(t) w(t)→ w^*(P) F(t)=o(t) (102) hold, where F(t)F(t) denotes the number of forced rounds up to time t. Let ℱ⊆ℕF be the (random) set of forced rounds and define n(t):=t−F(t)n(t):=t-F(t), the number of non-forced rounds up to time t. Then n(t)→∞n(t)→∞ and n(t)/t→1n(t)/t→ 1. Let τ1<τ2<… _1< _2<… denote the (decision) times at which the arm selection rule uses D-tracking rather than forcing. Since at time t the algorithm chooses Xt+1X_t+1, the non-forced pull counts are defined by N~x(k):=∑j=1kXτj+1=x. N_x(k):= _j=1^k1\X_ _j+1=x\. (103) We have the decomposition Nx(t)=N~x(n(t))+NxF(t),0≤NxF(t)≤F(t).N_x(t)= N_x(n(t))+N_x^F(t), 0≤ N_x^F(t)≤ F(t). (104) Step 1: induced dynamics on non-forced rounds. On each non-forced decision time τk _k, the algorithm selects Xτk+1∈argmaxx∈(τkw^x(τk)−Nx(τk)).X_ _k+1∈ _x ( _k w_x( _k)-N_x( _k)). (105) Using (104), τkw^x(τk)−Nx(τk)=kw^x(τk)−N~x(k)+Rk,x, _k w_x( _k)-N_x( _k)=k\, w_x( _k)- N_x(k)+R_k,x, (106) where Rk,x=(τk−k)w^x(τk)−NxF(τk).R_k,x=( _k-k) w_x( _k)-N_x^F( _k). (107) Since τk−k=F(τk)=o(τk)=o(k) _k-k=F( _k)=o( _k)=o(k) and 0≤NxF(τk)≤F(τk)=o(k)0≤ N_x^F( _k)≤ F( _k)=o(k), we have uniformly in x, supx∈|Rk,x|=o(k). _x |R_k,x|=o(k). (108) Thus the update rule on non-forced rounds is an o(k)o(k) perturbation of the ideal D-tracking rule argmaxx(kw^x(τk)−N~x(k)). _x(k\, w_x( _k)- N_x(k)). (109) Step 2: convergence along non-forced rounds. Since w^(τk)→w∗(P) w( _k)→ w^*(P), the deterministic stability argument for D-tracking (cf. [garivier2016optimalbestarmidentification, Appendix B.2–B.3]) yields N~x(k)k→wx∗(P)for all x∈. N_x(k)k→ w_x^*(P) all x . (110) Step 3: lifting back to real time. Using (104), Nx(t)t=n(t)t⋅N~x(n(t))n(t)+NxF(t)t. N_x(t)t= n(t)t· N_x(n(t))n(t)+ N_x^F(t)t. (111) Since n(t)/t→1n(t)/t→ 1, N~x(n)/n→wx∗(P) N_x(n)/n→ w_x^*(P), and NxF(t)/t≤F(t)/t→0N_x^F(t)/t≤ F(t)/t→ 0, we conclude Nx(t)t→wx∗(P)for all x∈. N_x(t)t→ w_x^*(P) all x . (112) ∎ F.5.6 Proof of Lemma 4 * Proof. Work on an event of probability one on which the following hold simultaneously: (i) P^(t)→P P(t)→ P, (i) Na(t)/t→wa∗(P)N_a(t)/t→ w_a^*(P) for all a∈a , and (i) x^(t)=x⋆(P) x(t)=x (P) for all sufficiently large t. All three were established in Section 7. Fix a competitor x≠x⋆(P)x≠ x (P). For all sufficiently large t, we have x^(t)=x⋆(P) x(t)=x (P), and therefore Zt(x,x^(t))=infQ∈:θQ(x)≥θQ(x⋆(P))∑a∈Na(t)KL(P^a(t)∥Qa).Z_t(x, x(t))= _ subarraycQ :\\ _Q(x)≥ _Q(x (P)) subarray _a N_a(t)\,KL( P_a(t)\|Q_a). (113) Let (tn)(t_n) be a subsequence with tn→∞t_n→∞. For each n, choose QnQ_n in the constraint set such that Ztn(x,x^(tn))≥∑a∈Na(tn)KL(P^a(tn)∥(Qn)a)−1n.Z_t_n(x, x(t_n))≥ _a N_a(t_n)\,KL( P_a(t_n)\|(Q_n)_a)- 1n. (114) Since P is compact, we may extract a subsequence (not relabeled) such that Qn→Q∞∈Q_n→ Q_∞ . Because P^(tn)→P P(t_n)→ P and θQ(⋅) _Q(·) is continuous in Q, the constraint θQn(x)≥θQn(x⋆(P)) _Q_n(x)≥ _Q_n(x (P)) passes to the limit, hence Q∞Q_∞ satisfies θQ∞(x)≥θQ∞(x⋆(P)) _Q_∞(x)≥ _Q_∞(x (P)). Under Assumption 3, KL(⋅∥⋅)KL(·\|·) is continuous on ×P×P. Thus for each arm a, KL(P^a(tn)∥(Qn)a)→KL(Pa∥(Q∞)a).KL( P_a(t_n)\|(Q_n)_a) (P_a\|(Q_∞)_a). (115) Combining with Na(tn)/tn→wa∗(P)N_a(t_n)/t_n→ w_a^*(P) yields limn→∞1tn∑a∈Na(tn)KL(P^a(tn)∥(Qn)a)=∑a∈wa∗(P)KL(Pa∥(Q∞)a). _n→∞ 1t_n _a N_a(t_n)\,KL( P_a(t_n)\|(Q_n)_a)= _a w_a^*(P)\,KL(P_a\|(Q_∞)_a). (116) Therefore, lim infn→∞1tnZtn(x,x^(tn))≥∑a∈wa∗(P)KL(Pa∥(Q∞)a)≥infQ∈:θQ(x)≥θQ(x⋆(P))∑a∈wa∗(P)KL(Pa∥Qa). _n→∞ 1t_nZ_t_n(x, x(t_n))≥ _a w_a^*(P)\,KL(P_a\|(Q_∞)_a)≥ _ subarraycQ :\\ _Q(x)≥ _Q(x (P)) subarray _a w_a^*(P)\,KL(P_a\|Q_a). (117) Since the sequence (tn)(t_n) was arbitrary and limit infimum corresponds to one of such subsequences, we conclude lim inft→∞1tZt(x,x^(t))≥infQ∈:θQ(x)≥θQ(x⋆(P))∑a∈wa∗(P)KL(Pa∥Qa)w.p. 1. _t→∞ 1tZ_t(x, x(t))≥ _ subarraycQ :\\ _Q(x)≥ _Q(x (P)) subarray _a w_a^*(P)\,KL(P_a\|Q_a) .p. 1. (118) Taking the minimum over x≠x⋆(P)x≠ x (P) and recalling the definition of T∗(P)T^*(P) from Theorem 2 yields lim inft→∞1tminx≠x⋆(P)Zt(x,x^(t))≥1T∗(P). _t→∞ 1t _x≠ x (P)Z_t(x, x(t))≥ 1T^*(P). (119) ∎ F.5.7 Proof of Theorem 4 (Almost-sure asymptotic optimality) * Proof. Let Z(t):=minx≠x^(t)Zt(x,x^(t))Z(t):= _x≠ x(t)Z_t(x, x(t)) (120) be the GLRT statistic used in the stopping rule τδ=inft≥1:Z(t)≥β(t,δ). _δ= \t≥ 1:\;Z(t)≥β(t,δ)\. (121) Step 1: Linear growth of the GLRT. By Lemma 4, lim inft→∞Z(t)t≥1T⋆(P)w.p. 1 _t→∞ Z(t)t≥ 1T (P) .p. 1 (122) Hence, for every ε>0 >0, there exists a (random) finite time tεt_ (w.p. 1) such that for all t≥tεt≥ t_ , Z(t)≥t(1+ε)T⋆(P)w.p. 1Z(t)≥ t(1+ )T (P) .p. 1 (123) Step 2: Dominating β(t,δ)β(t,δ) by a polynomial. From (46) β(t,δ)=log(π2t2+2KMZδ)+6MZKlog(t+1).β(t,δ)= ( π^2t^2+2KM_Zδ )+6M_ZK (t+1). (124) For all t≥1t≥ 1, using log(t+1)≤log(2t)=log2+logt (t+1)≤ (2t)= 2+ t, we obtain β(t,δ) β(t,δ) ≤log(1/δ)+log(π2)+(2+2KMZ)logt+6KMZ(log2+logt) ≤ (1/δ)+ (π^2)+(2+2KM_Z) t+6KM_Z( 2+ t) =log(Ctαδ), = \! ( C\,t^αδ ), (125) where α:=2+8KMZ,C:=π2 26KMZ.α:=2+8KM_Z, C:=π^2\,2^6KM_Z. (126) Step 3: Solving the implicit inequality. Combining (123) and (125), for all t≥tεt≥ t_ , the condition Z(t)≥β(t,δ)Z(t)≥β(t,δ) is implied by t(1+ε)T⋆(P)≥log(Ctαδ). t(1+ )T (P)≥ \! ( Ct^αδ ). (127) Let a:=(1+ε)T⋆(P)a:=(1+ )T (P). Then it suffices that t≥alog(Ctαδ).t≥ a \! ( Ct^αδ ). (128) Applying Lemma 18 of garivier2016optimalbestarmidentification yields that, for all sufficiently small δ, τδ≤a(log(C/δ)+αloglog(C/δ)+O(1))w.p. 1 _δ≤ a ( (C/δ)+α (C/δ)+O(1) ) .p. 1 (129) Step 4: Limsup bound. Dividing (129) by kl(δ,1−δ)kl(δ,1-δ) and letting δ↓0δ 0 gives, w.p. 1, lim supδ→0τδkl(δ,1−δ)≤(1+ε)T⋆(P), _δ→ 0 _δkl(δ,1-δ)≤(1+ )T (P), (130) since kl(δ,1−δ)=log(1/δ)+O(1)kl(δ,1-δ)= (1/δ)+O(1) and loglog(1/δ)=o(kl(δ,1−δ)) (1/δ)=o(kl(δ,1-δ)). As ε>0 >0 is arbitrary, letting ε↓0 0 yields lim supδ→0τδkl(δ,1−δ)≤T⋆(P)w.p. 1. _δ→ 0 _δkl(δ,1-δ)≤ T (P) .p.\ 1. (131) ∎