Paper deep dive

Uncertainty-Aware Selection of Online Algorithms with Simulator Ensembles

Yongyi Guo, Zifan Xu, Ziping Xu, Kelly W. Zhang

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 222

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%

Last extracted: 9/29/2026, 1:16:04 PM

Summary

This paper introduces Uncertainty-Aware (UA) selection, a method for choosing online reinforcement learning algorithms from limited offline data by using an ensemble of simulators (e.g., via bootstrap resampling) rather than a single fitted simulator (Plug-In selection). The authors theoretically prove that UA selection mitigates the effects of limited data in multi-armed bandits by favoring greater exploration, thereby avoiding the high polynomial regret associated with underexploration. Empirical results on robotic control tasks demonstrate that UA selection leads to more reliable algorithm selection and improved online performance compared to the standard Plug-In approach.

Entities (10)

Uncertainty-Aware Selection · method · 98%Plug-In Selection · method · 97%Simulator Ensemble · concept · 95%Regret · metric · 94%Bootstrap Resampling · technique · 93%Multi-Armed Bandit · problem-setting · 92%Thompson Sampling · algorithm · 90%UCB · algorithm · 90%Robotic Control · application-domain · 88%MuJoCo · softwaretool · 85%

Relation Signals (8)

Uncertainty-Aware Selection → uses → Simulator Ensemble

confidence 96% · Uncertainty-Aware selection... forms an ensemble of simulators... and selects the online algorithm with the best average performance across the ensemble.

Simulator Ensemble → constructedvia → Bootstrap Resampling

confidence 95% · forms an ensemble of simulators---for example, obtained by bootstrap resampling

Uncertainty-Aware Selection → outperforms → Plug-In Selection

confidence 94% · theoretically has significant regret gains compared to Plug-In selection in multi-armed bandits.

Uncertainty-Aware Selection → appliedto → Multi-Armed Bandit

confidence 92% · we formally show that this approach can mitigate the effects of limited data... in multi-armed bandits.

Plug-In Selection → suffersfrom → Unreliable Evaluations

confidence 91% · making evaluations unreliable when the offline data used to fit the simulator are limited.

Uncertainty-Aware Selection → appliedto → Robotic Control

confidence 90% · empirically investigate the Uncertainty-Aware selection approach in deep RL experiments on robotic control tasks

UCB → issubjectto → Uncertainty-Aware Selection

confidence 88% · For UCB and Thompson Sampling... we establish a provable... mechanism by which accounting for simulator uncertainty improves algorithm selection.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:The performance of online reinforcement learning depends critically on design choices, especially those that affect exploration. These choices are often selected by fitting a simulator to offline data, evaluating candidate algorithms in that simulator, and deploying the best-performing one. The simplest Plug-In selection rule simply selects the best performing algorithm on the fitted simulator, making evaluations unreliable when the offline data used to fit the simulator are limited. We investigate Uncertainty-Aware selection, which forms an ensemble of simulators---for example, obtained by bootstrap resampling---and selects the online algorithm with the best average performance across the ensemble. While ensemble-based approaches have been used to mitigate distribution shift and facilitate sim-to-real transfer, we formally show that this approach can mitigate the effects of limited data when fitting the simulator and theoretically has significant regret gains compared to Plug-In selection in multi-armed bandits. We also empirically investigate the Uncertainty-Aware selection approach in deep RL experiments on robotic control tasks that involve selecting reward-shaping hyperparameters, and show that it leads to more reliable selection and improved online performance.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

218,493 characters extracted from source content.

Expand or collapse full text

Uncertainty-Aware Selection of Online Algorithms with Simulator Ensembles Yongyi Guo Affiliation: Department of Statistics, University of Wisconsin–Madison Zifan Xu Affiliation: Department of Computer Science, The University of Texas at Austin Ziping Xu Affiliation: School of Data and Information Sciences, University of North Carolina at Chapel Hill Kelly W. Zhang Affiliation: *Authors are listed in alphabetical order. Affiliation: Department of Mathematics, Imperial College London Abstract The performance of online reinforcement learning depends critically on design choices, especially those that affect exploration. These choices are often selected by fitting a simulator to offline data, evaluating candidate algorithms in that simulator, and deploying the best-performing one. The simplest Plug-In selection rule simply selects the best performing algorithm on the fitted simulator, making evaluations unreliable when the offline data used to fit the simulator are limited. We investigate Uncertainty-Aware selection, which forms an ensemble of simulators—for example, obtained by bootstrap resampling—and selects the online algorithm with the best average performance across the ensemble. While ensemble-based approaches have been used to mitigate distribution shift and facilitate sim-to-real transfer, we formally show that this approach can mitigate the effects of limited data when fitting the simulator and theoretically has significant regret gains compared to Plug-In selection in multi-armed bandits. We also empirically investigate the Uncertainty-Aware selection approach in deep RL experiments on robotic control tasks that involve selecting reward-shaping hyperparameters, and show that it leads to more reliable selection and improved online performance. 1 Introduction Selecting an effective online reinforcement learning (RL) algorithm to deploy in practice is challenging because the deployment performance of online RL algorithms can vary substantially with design decisions (e.g., architecture, hyperparameters, and reward scaling or shaping) (Henderson et al., 2018; Wang et al., 2022; Fan and Glynn, 2025). Moreover, deployment of online RL in important domains, including robotics (Kober et al., 2013; Dulac-Arnold et al., 2019; Ibarz et al., 2021), healthcare (Trella et al., 2022; Figueroa et al., 2021), power grids (Zhang et al., 2018; Chen et al., 2022b), is often very expensive and thus, it can be infeasible to test out many candidate online RL algorithms in a real deployment. In many domains, however, one may have access to a (potentially limited) offline dataset before deployment to warm start or inform online RL algorithm design decisions. A common approach is to use the offline dataset to form an environment simulator that can be used as a surrogate to assess candidate algorithms (Mandel et al., 2016). In robotics, system identification approaches use a limited offline data to calibrate a physical simulator for policy training prior to deployment (Ljung, 1999; Peng et al., 2018; Muratore et al., 2022b). In digital health interventions, digital twins built using offline data are used to simulate patients for assessing candidate online intervention algorithms before deployment on a study population (Björnsson et al., 2020; Trella et al., 2022; Xu et al., 2026). The appeal of the simulator approach is its generality: a simulator can run any candidate algorithm end to end no matter how complex the online RL algorithm design grows. Simulators can be constructed nonparametrically, by replaying logged transitions through queues (Mandel et al., 2016), nearest-neighbor retrieval (Wang et al., 2022), rejection sampling (Tang et al., 2022) or parametrically, by fitting a model of the environment to the data (Trella et al., 2022; Ghosh et al., 2024; Moerland et al., 2023; Yang et al., 2023). The evaluated algorithm can be adaptive, history-dependent, or otherwise non-trivial, whereas offline policy evaluation (Precup et al., 2000; Jiang and Li, 2016; Uehara et al., 2026) scores a fixed policy and does not directly extend to online RL algorithms. Many existing approaches to fitting a simulator from offline data involve fitting a single model of the environment and selecting the candidate algorithm that performs the best on that fitted simulator. We call this selection approach the Plug-In selection rule. This approach has been used in practice in a variety of settings, including the Oralytics mobile health trial (Trella et al., 2022; Trella et al., 2024) and the educational game study (Mandel et al., 2016). In this paper, we identify a failure mode of the Plug-In simulator: it carries no information about how uncertain its estimate is, and we show that this omission can be costly when the offline data are scarce and the online horizon is long. In this work, we advocate for an Uncertainty-Aware selection approach that constructs an ensemble of simulators (Figure 1). The ensemble consists of copies of the fitted simulator whose parameters are perturbed according to their estimation uncertainty, for example by refitting on bootstrap resamples of the offline data. Each candidate algorithm is scored by its average return across the simulators in the ensemble. Our contributions are as follows. 1. Provable benefits of Uncertainty-Aware selection in bandits. For UCB and Thompson Sampling in two-armed Gaussian bandits, we establish a provable and empirically validated mechanism by which accounting for simulator uncertainty improves algorithm selection. Specifically, Theorem 1 characterizes the asymmetric costs of exploration: underexploration incurs polynomial regret, whereas overexploration preserves logarithmic regret. Building on this result, we show that Uncertainty-Aware selection asymptotically chooses at least as much exploration as Plug-In (Proposition 2), resulting in no larger asymptotic regret growth and, with nonvanishing probability, a polynomial-to-logarithmic improvement (Theorem 3). Simulations support this mechanism, showing reductions in both the mean and variability of regret. 2. Uncertainty-Aware selection as a curvature regularized version of Plug-In selection. In Proposition 4, we formally show that Uncertainty-Aware selection criterion can be interpreted as a regularized version of the Plug-In selection criterion that depends on the curvature of the objective function with respect to the simulator parameters. This result holds for general decision-making settings (including bandits and Markov decision processes (MDPs)). 3. Empirical benefit for specifying reward-shaping for deep RL. We demonstrate the benefit of Uncertainty-Aware selection empirically in a deep RL reward-shaping task in which physics parameters of a MuJoCo simulator are identified from offline trajectories. Taken together, our results show that ensembles of simulators are not only a tool for training robust policies: they provably improve the selection of online learning algorithms from limited offline data. Figure 1: Selecting an online RL algorithm using limited offline data. Both rules fit simulators to offD_ off and then deploy the selected algorithm in the true environment M∗M^*. The Plug-In rule commits to a single fitted simulator M M; the Uncertainty-Aware rule averages the objective over M^(1),…,M^(n) M^(1),…, M^(n), favoring algorithms that perform consistently across plausible realizations. 2 Problem setup Decision-making environment. States St,hS_t,h take values in state space S and actions At,hA_t,h in action space A. M∗M^* denotes the general decision-making environment, which specifies the distribution of the reward and next state given the most recent action, state, and history, i.e., ℙ(Rt,h,St,h+1∣At,h,St,h,ℋt,h−1)P(R_t,h,S_t,h+1 A_t,h,S_t,h,H_t,h-1), where the history up to episode t and the within-episode timestep h: ℋt,h−1:=(St,h′,At,h′,Rt,h′)h′=1h−1∪(St′,h,At′,h,Rt′,h)t′=1,h=1t′=t−1,h=H. _t,h-1:= \(S_t,h ,A_t,h ,R_t,h ) \_h =1^h-1∪ \(S_t ,h,A_t ,h,R_t ,h) \_t =1,h=1^t =t-1,h=H. In our theory and experiments M∗M^* is either a finite-horizon MDP (Puterman, 2014) or a multi-armed bandit (MAB) environment (Lattimore and Szepesvári, 2020). In the MAB setting, H=1H=1 and ||=1|S|=1 so we use ℋt=(At′,Rt′)t′=1tH_t=\(A_t ,R_t )\_t =1^t to denote the history. Offline dataset. We assume we have access to an offline dataset consisting of ToffT_ off episodes from environment M∗M^* each of horizon H collected by a behavior policy πb _b: off:=(St,1,At,1,Rt,1),(St,2,At,2,Rt,2),…(St,H,At,H,Rt,H)t=1Toff. _ off:= \(S_t,1,A_t,1,R_t,1),(S_t,2,A_t,2,R_t,2),…(S_t,H,A_t,H,R_t,H) \_t=1^T_ off. The policy πb _b takes (ℋt,h−1,St,h)(H_t,h-1,S_t,h) as input and outputs a distribution over actions A. Note, in the MAB special case where H=1H=1 and ||=1|S|=1, for simplicity, we just write off:=(At,Rt)t=1ToffD_ off:=\(A_t,R_t)\_t=1^T_ off. Algorithm selection objective. Our goal is to use the offline dataset offD_ off to inform the selection of an online RL algorithm π∈Ππ∈ , which specifies action selection probabilities π⁡(At,h∣St,h,ℋt,h−1):=ℙ⁡(At,h∣St,h,ℋt,h−1)π(A_t,h S_t,h,H_t,h-1):=P(A_t,h S_t,h,H_t,h-1). The algorithm π will be deployed for T episodes in the same environment M∗M^* where offD_ off was collected. Specifically, we want to select algorithm π to maximize an objective function JT(π,M∗)J_T(π,M^*). Unless stated otherwise, throughout this work, the objective could be the expected cumulative reward JT(π,M∗)=π,M∗[∑t=1T∑h=1HRt,h], J_T(π,M^*)=E_π,M^* [ _t=1^T _h=1^HR_t,h ], (1) where the expectation is taken over the random trajectories induced by the online algorithm π. In other settings like robotic learning, one might also be interested in the expected reward on the final episode JT(π,M∗)=π,M∗[∑h=1HRT,h]J_T(π,M^*)=E_π,M^* [ _h=1^HR_T,h ]. Candidate algorithm class. The class of candidate history-dependent policies Π could include exploration strategies of algorithm (e.g., ϵε-greedy (Wunder et al., 2010), Thompson Sampling (Russo et al., 2018), bonus-based exploration (Bellemare et al., 2016)), model architectures, state specification, reward specification/reward shaping, and algorithm hyperparameters. We index candidate online algorithms by a tuning parameter θ∈Θθ∈ , so Π=πθ:θ∈Θ =\ _θ:θ∈ \. For example, in UCB, θ controls the width of the exploration bonus; in ϵε-greedy Q-learning, it may control the exploration rate. In general, θ may index other design choices, such as model architecture, state representation, or reward shaping. We use θT∗=argmaxθ∈ΘJT(πθ,M∗) _T^*=argmax_θ∈ J_T( _θ,M^*) to denote the optimal θ for a given T. Plug-In simulation selection rule. We use the offline dataset offD_ off to fit an approximate environment model M M of M∗M^*, which may be an explicit dynamics model or a learned generative world model. We then use M M as a proxy environment in which to evaluate candidate decision procedures. A simple and commonly used simulator-based selection rule (Moerland et al., 2023; Wang et al., 2022; Yang et al., 2023) is the Plug-In selection rule which forms an estimated simulator M M π^plug∈argmaxπ∈Π⁡JT(π,M^). π_ plug∈ _π∈ J_T(π, M). (2) The above solution can be solved empirically by repeatedly rolling out the algorithm π in environment M M for different choices of algorithm π∈Ππ∈ . 11 1 Picking the best RL algorithm using replay-style simulators (Mandel et al., 2016; Tang et al., 2022; Wang et al., 2022) is also Plug-In selection where the simulator is an empirical distribution fit non-parametrically. Uncertainty-Aware simulation selection rule. In this work we advocate for an Uncertainty-Aware (UA) selection approach. This approach involves using offD_ off to fit an ensemble of simulators and choosing the algorithm candidate that does well on average across an ensemble of fitted simulators M^(1),…M^(n) M^(1),… M^(n). Then the Uncertainty-Aware selection rule selects the algorithm as follows: π^UA=argmaxπ∈Π⁡1n∑i=1nJT(π,M^(i)), π_ UA= _π∈ \, 1n _i=1^nJ_T (π, M^(i) ), (3) Rather than maximizing performance on the single fitted simulator M M, (3) instead evaluates candidates on average across ensembles M^(n) M^(n), which favors algorithms with consistently strong performance across plausible realizations of the simulator M M. There are a variety of ways to construct the ensemble of simulators—including bootstrap and adding noise to the fitted simulator M M. Throughout, we construct the ensemble of simulators M^(1),…M^(n) M^(1),… M^(n) using bootstrap-based approaches. In particular, we use both empirical and parametric bootstrapping. Empirical bootstrap resamples the episodes in off=(St,1,At,1,Rt,1),(St,2,At,2,Rt,2),…(St,H,At,H,Rt,H)t=1ToffD_ off= \(S_t,1,A_t,1,R_t,1),(S_t,2,A_t,2,R_t,2),…(S_t,H,A_t,H,R_t,H) \_t=1^T_ off with replacement. In simpler models, e.g., Gaussian bandits, we use parametric bootstrap methods to construct the ensemble (van der Vaart, 1998, Chapter 23.1). 2.1 Related work Our main finding is a more robust and plausible algorithm selection through ensembled simulators that are uncertainty-aware. This approach is similar to domain randomization (DR) and its data-calibrated variants (Tobin et al., 2017; Peng et al., 2018; Ramos et al., 2019; Chebotar et al., 2019; Muratore et al., 2022a; Tiboni et al., 2023) that also train against a distribution of simulators. Existing literature on DR primarily concerns the mismatch between the simulator and the deployment environment, and its purpose is to make one fixed policy robust to that mismatch. In our setting there is no mismatch, since the offline data and the deployment come from the same environment; the spread of the ensemble reflects only the sampling variability of a finite dataset and vanishes as the data grow, and the gain arises because the candidates are online learners whose regret responds asymmetrically to the estimation error. Ensembles are also standard inside model-based RL, where bootstrapped or probabilistic ensembles quantify epistemic uncertainty to drive exploration (Osband et al., 2016; Chua et al., 2018) or to penalize policies that visit states where the members disagree (Yu et al., 2020; Kidambi et al., 2020). In those methods the ensemble is part of the algorithm being run and changes how it acts; in ours the ensemble sits outside the candidates, which are evaluated as black boxes, and it changes only which candidate algorithm is chosen. A similar distinction separates our rule from robust and distributionally robust RL (Iyengar, 2005; Nilim and El Ghaoui, 2005; Eysenbach and Levine, 2022), which optimize a worst case over an uncertainty set by solving an optimization problem: we show that a plain average over the ensemble is already a curvature regularization of the Plug-In criterion (Proposition 4), and that this average suffices for the regret gains of Section 3. Finally, the object being selected differs from that of offline policy selection (Konyushova et al., 2021; Yang et al., 2022; Zitovsky et al., 2023), which ranks fixed policies through fitted value functions; we rank learners that keep learning after deployment, so what the simulator must get right is their ordering by online regret. Among the works that select online algorithms (Wang et al., 2022; Tang et al., 2022), no prior work asks how the estimation error of a data-fitted simulator propagates into the choice of an online learning algorithm, or shows that an ensemble corrects it. See Appendix A for a more complete review of the related literature. 3 Plug-In vs. UA selection in multi-armed bandits In this section, we characterize the cost of poor hyperparameter selection and compare the Plug-In and Uncertainty-Aware selection rules in a simple Gaussian multi-armed bandit environment M∗M^*, in which H=1H=1, ||=1|S|=1, =1,2A=\1,2\, and rewards Rt|At=a∼⁡(μa,σ2)R_t|A_t\!=\!a ( _a,σ^2). More specifically, we study two common MAB algorithms with a hyperparameter θ that impacts the amount of exploration. Our results center around two key findings, which we support empirically and theoretically: (a) Underexploration can be substantially more costly than overexploration: an exploration parameter θ that is too small can lead to much larger regret than one that is too large. (b) Uncertainty-Aware selection tends to favor greater exploration than Plug-In selection, thereby reducing the risk of costly underexploration and leading to improved regret. Bandit algorithms. We focus on two MAB algorithms. For both algorithms, θ controls the amount of exploration: larger values of θ induce more exploration, while smaller values induce less exploration. The first, UCB (Auer et al., 2002; Lattimore and Szepesvári, 2020; Abbasi-Yadkori et al., 2011) at round t pulls the arm At∈argmaxa∈⁡μ^a(t−1)+2θlog⁡t/Na(t−1), A_t∈ _a \ μ_a(t-1)+ 2θ t/N_a(t-1) \, (4) where Na(t)=∑τ=1t⁡(Aτ=a)N_a(t)\!=\! _τ=1^t (A_τ\!=\!a) and μ^a(t)=∑τ=1t⁡(Aτ=a)Rτ/Na(t) μ_a(t)\!=\! _τ=1^t (A_τ\!=\!a)R_τ/N_a(t) are the running pull count and mean reward of arm a, respectively. Here the hyperparameter θ>0θ>0 is the exploration radius. The second algorithm, Thompson Sampling (TS) (Russo et al., 2018) forms a Bayesian model of the reward means where we have a flat prior over arm means μa _a, i.e., P⁡(μa)∝1P( _a) 1, and rewards are conditionally Gaussian with variance θ, i.e., Rt|At=a,μa∼(μa,θ)R_t|A_t\!=\!a, _a ( _a,θ). At each time t, the posterior distribution is then μa|ℋt−1∼⁡(μ^a(t−1),θ/Na(t−1)) _a|H_t-1 ( μ_a(t-1),\,θ/N_a(t-1)). TS selects actions via probability matching in that actions are selected according to the posterior probability that they are optimal: ℙ⁡(At=a∣ℋt−1)=ℙ⁡(a=argmaxa′∈μa′∣ℋt−1). (A_t=a _t-1)=P(a= argmax_a \, _a _t-1). (5) We refer to the hyperparameter θ>0θ>0 as the working reward variance. Figure 2: Asymmetric costs of exploration and the benefit of Uncertainty-Aware selection. Simulations are in a two-armed Gaussian bandit with T=5000T=5000, Toff=25T_ off=25, margin μ1−μ2=1 _1- _2=1, and noise standard deviation σ=3σ=3. Top: Regret of UCB (left) and Thompson Sampling (right) as a function of the exploration level θ (see (4) and (5)). Regret rises far more steeply below the optimal value θT∗ _T^* (dotted vertical line) than above it, i.e., underexploration is more costly. Bottom: Using multiple samples of offD_ off, Uncertainty-Aware selection (ensemble models constructed via bootstrap) more often selects higher values of θ compared to Plug-In, which leads to lower regret on average. Additionally, Uncertainty-Aware selection has lower variance in regret across trials. 3.1 Asymmetric costs of under- and overexploration For both UCB and TS, given an exploration parameter θ, we measure the online performance of πθ _θ by its expected cumulative regret: RegT(πθ,M∗)=Tμ∗(M∗)−JT(πθ,M∗), Reg_T( _θ,M^*)=Tμ^*(M^*)-J_T( _θ,M^*), (6) where μ∗(M∗)=maxa∈1,2⁡μaμ^*(M^*)= _a∈\1,2\ _a, and πθ _θ denotes either UCB or TS with hyperparameter θ. Figure 2 (top) illustrates a pronounced asymmetry: regret increases much more sharply when θ falls below the best-performing choice than when it increases above it. We observe the same pattern across a range of environment configurations in Appendix B.5. The following result provides a theoretical characterization of this asymmetry for both UCB and TS. Theorem 1 (Asymmetric regret of UCB and TS). Let M∗M^* be a two-armed Gaussian bandit with μ1>μ2 _1> _2 and σ2>0σ^2>0. Let πθ _θ denote either the UCB algorithm (4) or the TS algorithm (5) with hyperparameter θ>0θ>0. Then: (i) For any θ∈(0,σ2)θ∈(0,σ^2), limT→∞log⁡RegT(πθ,M∗)log⁡T=1−θσ2. _T→∞ Reg_T( _θ,M^*) T=1- θσ^2. (i) For any θ≥σ2θ≥σ^2, limT→∞RegT(πθ,M∗)log⁡T=2θμ1−μ2. _T→∞ Reg_T( _θ,M^*) T= 2θ _1- _2. Theorem 1 identifies σ2σ^2 as a critical exploration level for both algorithms. Below this threshold, regret grows polynomially as T1−θ/σ2+o⁡(1)T^1-θ/σ^2+o(1); at or above the threshold, it grows only logarithmically, with leading constant 2θ/(μ1−μ2)2θ/( _1\!-\! _2). Thus, insufficient exploration can change the order of regret from logarithmic to polynomial, whereas additional exploration above the threshold affects only the leading constant of the logarithmic regret. This asymmetry is also reflected in the finite-horizon results in Figure 2 (top). Theorem 1 is closely related to the results in Fan and Glynn (2025) and Fan and Glynn (2022). In Appendices D and E, we establish stronger results for both algorithms: the regret exponent converges uniformly in θ over compact subsets of (0,∞)(0,∞), while the leading-order logarithmic asymptotics hold uniformly over compact subsets of (σ2,∞)(σ^2,∞). We also provide associated finite-horizon regret bounds that are uniform in both θ and the suboptimality gap (Lemma 8 and 14). These uniformity results are important for analyzing data- and horizon-dependent hyperparameter selection. Our uniform polynomial lower bounds for both algorithms exploit low initial rewards that delay further sampling of the optimal arm, following the intuition of Fan and Glynn (2025). For the upper bounds, we adapt a pull-count decomposition argument to obtain the required uniform control; the TS analysis further builds on the posterior-odds comparison of Agrawal and Goyal (2013), for which we derive uniform bounds on truncated Gaussian odds to handle underexploration. 3.2 Uncertainty-Aware selection favors exploration and improves regret Uncertainty-Aware selection lowers both the mean and the variance of regret (Figure 2). We empirically compare the Plug-In and Uncertainty-Aware selection rules for UCB and Thompson Sampling. We use a Gaussian reward two-armed bandit simulation environment M∗=(⁡(μ1,σ12),⁡(μ2,σ22))M^*= (N( _1, _1^2),N( _2, _2^2) ). The Plug-In selection rule fits M^=(⁡(μ^1,σ^2),⁡(μ^2,σ^2)) M= (N( μ_1, σ^2),N( μ_2, σ^2) ), where μ^a μ_a is the sample mean of arm a∈1,2a∈\1,2\ and σ^2 σ^2 is the reward variance pooled across the two arms, both estimated using offD_ off. The Uncertainty-Aware selection rule forms an ensemble of simulators M^(1),…,M^(n) M^(1),…, M^(n) by a parametric bootstrap: member i is M^(i)=(⁡(μ^1(i),(σ^(i))2),⁡(μ^2(i),(σ^(i))2)) M^(i)= (N ( μ_1^(i),( σ^(i))^2 ),N ( μ_2^(i),( σ^(i))^2 ) ), where μ^a(i) μ_a^(i) and (σ^(i))2( σ^(i))^2 are the same estimates computed on a fresh dataset of ToffT_ off pairs drawn from M M under the behavior policy (Appendix B.3). Figure 2 (bottom) shows that Uncertainty-Aware selection has lower regret compared to Plug-In. The lower regret under UA selection is because it selects higher values of exploration compared to Plug-In. Specifically, for Plug-In selection 61.0%61.0\% of the regret is due to selecting a θ below θT∗ _T^*, while for Uncertainty-Aware selection only 50.6%50.6\% of regret is due to selecting a θ below θT∗ _T^*. The Plug-In rule therefore underperforms not because its estimate of θ is noisy, but because the errors that fall on the side of too little exploration are the expensive ones, and their cost compounds with the horizon. Furthermore, the variance of the cumulative regret across trials is dramatically lower under Uncertainty-Aware selection compared to Plug-In (573 vs 1137 for UCB; 363 vs 869 for TS). We discuss how Uncertainty-Aware selection can be interpreted as a curvature regularized version of the Plug-In objective in Section 4. Uncertainty-Aware selection leads to greater exploration (Figure 3). Figure 3 illustrates the mechanism behind improvement in regret under UA selection. Across much of the region of (Δ^,σ^)( , σ) values supported by the offline data, the Uncertainty-Aware rule selects a normalized exploration parameter θ/σ2θ/σ^2 that is at least as large as that selected by the Plug-In rule. Thus, accounting for uncertainty in the fitted simulator systematically guards against selections that are overly exploitative under a favorable but inaccurate point estimate. This effect is not simply a uniform increase in exploration: it is concentrated in regions where uncertainty about the reward gap and noise level can change the relative performance of candidate settings. By avoiding these costly underexploratory selections while making similar choices when the fitted model is sufficiently informative, the Uncertainty-Aware rule reduces both the mean and variability of regret observed above. Figure 3: Uncertainty-Aware (UA) selection leads to greater exploration than Plug-In under UCB. We independently sample 10610^6 offD_ off datasets and compute an estimate of the margin Δ=μ1−μ2 = _1- _2 and the reward standard deviation σ. The star depicts the true value of Δ=1 =1 and σ=3σ=3 in the environment. The contour lines at 50% depicts where 50% of the 10610^6 estimated Δ^,σ , σ are; similarly for the 90%, and 99% contour lines. We depict the selected value of θ/σ2θ/σ^2 for each combination of (Δ,σ)( ,σ) under the Plug-In selection rule (left) and that for the UA selection rule (center). In the right most plot, we depict the difference in chosen θ/σ2θ/σ^2 for the Plug-In and UA rules. The plot shows that the UA selection rule leads to similar or greater exploration than Plug-In for most values of (Δ,σ)( ,σ). Combined with the asymmetric cost of underexploration (Section 3.1), this helps explain how UA decreases regret compared to Plug-In. We next provide theoretical support for these empirical findings. For simplicity, we assume the offline dataset offD_ off was collected by a behavior policy that samples each arm T1,off:=⌊Toff/2⌋T_1, off:= T_ off/2 times, and let M^=(⁡(μ^1,σ^12),⁡(μ^2,σ^22)) M= (N( μ_1, σ_1^2),N( μ_2, σ_2^2) ) denote the fitted environment. For either UCB or TS, let πθ _θ denote the algorithm with hyperparameter θ. For the selection analysis, we restrict the candidate parameters to a compact interval Θ=[θ¯,θ¯] =[ θ, θ] satisfying 0<θ¯<σ2<θ¯<∞0< θ<σ^2< θ<∞. The Plug-In rule selects θ^plug,T∈argmaxθ∈Θ⁡JT(πθ,M^) θ_ plug,T∈ _θ∈ J_T( _θ, M). For the theoretical analysis of the Uncertainty-Aware rule, we consider a simplified parametric-bootstrap ensemble (van der Vaart, 1998) that perturbs the fitted arm means according to their estimated sampling uncertainty. Conditional on offD_off, each ensemble member is M^(i)=(⁡(μ^1+σ^1/T1,off⋅Z1(i),σ^12),⁡(μ^2+σ^2/T1,off⋅Z2(i),σ^22)), M^(i)= (N ( μ_1+ σ_1/ T_1, off· Z_1^(i),\, σ_1^2 ),~N ( μ_2+ σ_2/ T_1, off· Z_2^(i),\, σ_2^2 ) ), (7) where Z1(i),Z2(i)∼iid⁡(0,1)Z_1^(i),Z_2^(i) iid N(0,1). We analyze the population counterpart of the finite-ensemble UA objective in (3), obtained in the large-ensemble limit: θ^UA,T:=argmaxθ∈Θ⁡[JT(πθ,M^(i))|off]. θ_ UA,T:= _θ∈ E [J_T( _θ, M^(i))\, |\,D_ off ]. (8) The maximizers θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T exist almost surely over offD_ off (see Appendices D, E). Our first result is Proposition 2 which shows that, by accounting for uncertainty in the fitted environment, the UA selection rule asymptotically never selects less exploration than the Plug-In rule. Proposition 2 (Uncertainty-Aware selection leads to higher exploration). Consider a two-armed Gaussian bandit M∗M^* with μ1>μ2 _1> _2 and σ2>0σ^2>0. For either UCB or TS, almost surely over offD_ off, lim infT→∞θ^UA,T≥limT→∞θ^plug,T _T→∞ θ_ UA,T≥ _T→∞ θ_ plug,T. The greater exploration induced by UA selection translates into a more favorable asymptotic regret growth rate. To state this comparison, define the asymptotic log ratio between the cumulative regret growth rates of Plug-In and UA selection: G⁡(off):=lim infT→∞log⁡RegT(πθ^plug,T,M∗)log⁡RegT(πθ^UA,T,M∗).G(D_ off):= _T→∞ Reg_T( _ θ_ plug,T,M^*) Reg_T( _ θ_ UA,T,M^*). (9) Theorem 3. In a two-armed Gaussian bandit M∗M^* with μ1>μ2 _1> _2 and σ2>0σ^2>0, for either UCB or TS: (i) For any Toff≥4T_ off≥ 4, G⁡(off)≥1G(D_ off)≥ 1 almost surely. (i) lim infToff→∞ℙ⁡(G⁡(off)=∞)≥14 _T_ off→∞P\! (G(D_ off)=∞ )≥ 14. Proposition 2 provides the intuition for Theorem 3(i): UA asymptotically selects at least as much exploration as Plug-In, while the regret exponent decreases with the exploration parameter. A formal argument requires uniform regret bounds for the data-dependent sequences θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T. Part (i) further shows that UA can strictly improve the regret growth rate. The proof identifies an event whose probability converges to 1/41/4 as Toff→∞T_ off→∞, on which Plug-In selects an exploration parameter below the critical level σ2σ^2, whereas UA selects above it. By the asymmetric regret analysis in Section 3.1, the resulting deployment regrets are polynomial and logarithmic in T, respectively, and hence G⁡(off)=∞G(D_ off)=∞. Proofs for UCB and TS are given in Appendices D and E, respectively. 4 Bandits and beyond: Uncertainty-Aware simulation selection as a curvature regularization Motivated by the bandit results, we next give a local characterization of how UA selection differs from Plug-In selection. This characterization does not rely on the bandit setting: it applies whenever an offline dataset is used to fit a simulator and candidate decision procedures are evaluated within that simulator. The simulator may be an explicit dynamics-and-reward model or a learned latent world model, and the evaluation criterion JTJ_T may be application-specific, e.g., could incorporate risk-sensitive utility, safety, or another deployment criterion. Plug-In selection ranks candidates using a single fitted simulator, whereas UA selection ranks them by average performance across plausible perturbations of that simulator. We show that, locally, this averaging induces a curvature-dependent adjustment to the Plug-In objective. This provides one interpretation of UA selection as regularization at the selection stage: it can downweight candidates whose favorable Plug-In evaluation is sensitive to uncertainty in the fitted simulator, without modifying the candidate algorithm itself. Curvature correction for simulator uncertainty. To make this interpretation precise, consider a parametric simulator family Mλ:λ∈ℝd\M_λ:λ ^d\ and suppose that the fitted simulator is M^=Mλ M=M_ λ. In particular, λ may parameterize transition dynamics, rewards, or components of a latent world model. Let an ensemble simulator take the form M(i)=Mλ^+ϵ(i)M^(i)=M_ λ+ε^(i) where, conditional on offD_off, ⁡[ϵ(i)∣off]=0E[ε^(i) _off]=0, ⁡[ϵ(i)(ϵ(i))⊤∣off]=ΣE[ε^(i)(ε^(i)) _off]= , and ⁡[‖ϵ(i)‖23∣off]<∞E[\|ε^(i)\|_2^3 _off]<∞. Here, the perturbations ϵ(i)ε^(i) may arise from an empirical bootstrap, a parametric bootstrap, posterior samples, or another ensemble construction intended to represent uncertainty in the fitted simulator. The Plug-In selection rule selects θ^plug,T∈argmaxθ∈Θ⁡JT(πθ,Mλ^) θ_ plug,T∈ _θ∈ J_T( _θ,M_ λ). The UA objective here maximizes the population counterpart of the finite-ensemble UA objective from (3): θ^UA,T∈argmaxθ∈Θ⁡[JT(πθ,Mλ^+ϵ(i))|off]. θ_ UA,T∈ _θ∈ E [J_T ( _θ,M_ λ+ε^(i) )\, |\,D_off ]. (10) Proposition 4 (Ensembles induce a curvature correction). Suppose λ↦JT(πθ,Mλ)λ J_T( _θ,M_λ) is twice continuously differentiable and its Hessian is L-Lipschitz, i.e., ‖∇λ2JT(πθ,Mλ)−∇λ2JT(πθ,Mλ′)‖op≤L‖λ−λ′‖2\| _λ^2J_T( _θ,M_λ)- _λ^2J_T( _θ,M_λ )\|_op≤ L\|λ-λ \|_2 for all λ,λ′λ,λ , where ∥⋅∥op\|·\|_op is the operator norm. Then |⁡[JT(πθ,Mλ^+ϵ(i))∣off]−JT(πθ,Mλ^)−12Tr⁡(∇λ2JT(πθ,Mλ^)Σ)|≤L6[‖ϵ(i)‖23∣off]. |E [J_T( _θ,M_ λ+ε^(i)) _off ]-J_T( _θ,M_ λ)- 12Tr ( _λ^2J_T( _θ,M_ λ) ) |≤ L6\,E [\|ε^(i)\|_2^3 _off ]. (11) Proposition 4 shows that UA selection is locally a curvature-adjusted version of Plug-In selection. In directions of simulator uncertainty along which a candidate’s value is locally concave, the correction in (11) is negative: performance lost under unfavorable perturbations exceeds performance gained under equally sized favorable perturbations. UA selection therefore lowers the ranking of candidates whose high Plug-In score is brittle to uncertainty in the fitted simulator. UA selection favors candidates according to their value curvature in the uncertain directions of the simulator. This is why we view UA selection as a form of regularization rather than as a rule that uniformly penalizes exploration, optimism, or any particular hyperparameter value. The proof is in Appendix F. 5 Deep RL experiments We apply UA selection to continuous control in MuJoCo (Todorov et al., 2012), tuning the reward-shaping weights of PPO (Schulman et al., 2017; Raffin et al., 2021) in the setup of Xie et al. (2025), on simulators whose physics parameters are identified from offline data. Tasks and online learners. The tasks are Hopper and Walker2d from Gymnasium (Towers et al., 2025), in which a planar robot with three (Hopper) or six (Walker2d) actuated joints must move forward without falling, with horizon H=250H=250. Reward shaping trains the learner on a hand-designed reward with several terms, and the weights on those terms strongly affect the trained policy (Xie et al., 2025). Here the tuning parameter θ=(θsurv,θfwd,θctrl)θ=( _ surv, _ fwd, _ ctrl) collects the weights of three handcrafted heuristic reward terms, a survival bonus, a forward-progress term and a control-cost penalty, with θsurv=1 _ surv=1 fixed (Appendix C.1). A larger ratio θfwd/θctrl _ fwd/ _ ctrl pays more for moving forward and charges less for actuation, so the trained policy runs harder; we call such a θ more aggressive. The candidate algorithm πθ _θ is PPO trained on the reward with weights θ, with every other setting held fixed (Appendix C.3), and the candidate set Θ is a grid of 2525 weight vectors on Hopper and 3030 on Walker2d (Appendix C.2). Following Xie et al. (2025), the performance is measured by a success score that is zero if the average squared actuation over the episode exceeds a bound cmaxc_ , and otherwise rises linearly from 00 to 11 as the distance traveled increases from a threshold xlox_ lo to a threshold xhix_ hi (Appendix C.1). We evaluate the performance of the trained policy at T=3×105T=3× 10^5 environment steps. Every reported value is a Monte Carlo estimate over 5050 evaluation episodes, which we call the success score. Simulator and offline data. The simulator family is Mλ\M_λ\, where MλM_λ is the MuJoCo model of the robot with λ=(λmass,λfric,λdamp)∈ℝ3λ=( _ mass, _ fric, _ damp) ^3 multiplying the body masses, the friction coefficients and the joint damping of a baseline model. Estimating λ from logged data is standard practice in robotics, known as system identification (Ljung, 1999; Tiboni et al., 2023). The true environment is M∗=Mλ∗M^*=M_λ^* with λ∗=(1.5,0.7,1.4)λ^*=(1.5,0.7,1.4), a robot that is heavier, slipperier and more damped than the baseline model; the practitioner typically knows the model but not λ∗λ^*. We add Gaussian noise to the observations, in the offline data, in every simulator and on the true environment, so that identifying λ from offD_ off is a nontrivial task (Appendix C.4). Table 1: Success score of the weight vector selected by the Plug-In and UA rules on the true environment, mean ± standard error and 1010th percentile over 300300 paired replications; higher is better. The better of the two rules is in bold, and ∗ marks a significant difference. Hopper, JT(πθT∗,M∗)=0.991J_T( _ _T^*,M^*)=0.991 Walker2d, JT(πθT∗,M∗)=0.689J_T( _ _T^*,M^*)=0.689 ToffT_ off Plug-In UA q10q_10 Plug-In q10q_10 UA Plug-In UA q10q_10 Plug-In q10q_10 UA 2020 0.933±0.0070.933± 0.007 0.956±0.005∗0.956± 0.005^* 0.7640.764 0.9300.930 0.585±0.0060.585± 0.006 0.594±0.0060.594± 0.006~~ 0.4560.456 0.4560.456 8080 0.965±0.0030.965± 0.003 0.971±0.0030.971± 0.003~~ 0.9300.930 0.9300.930 0.594±0.0050.594± 0.005 0.616±0.005∗0.616± 0.005^* 0.4560.456 0.5170.517 320320 0.976±0.0020.976± 0.002 0.981±0.0020.981± 0.002~~ 0.9300.930 0.9360.936 0.590±0.0050.590± 0.005 0.610±0.005∗0.610± 0.005^* 0.4560.456 0.5270.527 The offline dataset offD_ off consists of Toff∈20,80,320T_ off∈\20,80,320\ episodes collected on M∗M^* by a behavior policy πb _b that draws actions uniformly at random. For each offline episode t=1,…,Tofft=1,…,T_ off we fit λ^t λ_t by nonlinear least squares over its transitions (Tiboni et al., 2023) combined with a bias-correction method called SIMEX (Cook and Stefanski, 1994; Carroll et al., 2006). The Plug-In simulator is M^=Mλ M=M_ λ with λ^=Toff−1∑t=1Toffλ^t λ=T_ off^-1 _t=1^T_ off λ_t, the average of the per-episode estimates. The UA ensemble is the empirical bootstrap over episodes. Member i=1,…,n=12i=1,…,n=12 is M^(i)=Mλ^(i) M^(i)=M_ λ^(i) with λ^(i)=Toff−1∑t∈ℐ(i)λ^t λ^(i)=T_ off^-1 _t ^(i) λ_t, where ℐ(i)I^(i) is a multiset of ToffT_ off episodes. We give both rules the same budget of K=12K=12 training runs per θ. We report the success score of the selected θ θ on the true environment, averaged over 300300 replications, each of which draws a fresh offD_ off that both rules then see (Appendix C.7). Results. Table 1 reports the six cells, two tasks by three offline dataset sizes. UA selection has the higher mean success score in every cell, by 0.0050.005 to 0.0230.023, significantly in three. Its 1010th percentile (last two columns) is higher in four cells and equal in the other two. Figure 7 in Appendix 6 validates the regularization effect of UA (Section 4). 6 Discussion Our setting isolates simulator-estimation uncertainty by considering offline data and online deployment from the same environment. This is deliberately complementary to work on distribution shift, where techniques such as domain randomization can improve robustness by accounting for variation between training and deployment conditions. Our results show that simulator ensembles can improve algorithm selection even in the absence of such shift: averaging across plausible simulators mitigates uncertainty arising solely from limited offline data. An important direction for future work is to study how Uncertainty-Aware selection and distribution-shift methods can be combined when the deployment environment may differ systematically from the environment that generated the offline data. Other directions include extending the theoretical analysis beyond bandits to MDPs and a broader range of online algorithms, and studying richer algorithm-design choices such as architectures, state representations, and reward specifications. Finally, practical progress will require ensemble-construction methods that quantify uncertainty reliably in complex simulators. References Abbasi-Yadkori et al. (2011) Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24. Cited by: §3. Agrawal and Goyal (2013) S. Agrawal and N. Goyal Further optimal regret bounds for Thompson sampling. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research, Vol. 31, p. 99–107. Cited by: §3.1. As et al. (2025) Y. As, C. Qu, B. Unger, D. Kang, M. van der Hart, L. Shi, S. Coros, A. Wierman, and A. Krause SPiDR: a simple approach for zero-shot safety in sim-to-real transfer. In Advances in Neural Information Processing Systems 38 (NeurIPS 2025), p. 100933–100975. Cited by: Appendix A. Åström and Eykhoff (1971) K. J. Åström and P. Eykhoff System identification—a survey. Automatica 7 (2), p. 123–162. Cited by: Appendix A. Auer et al. (2002) P. Auer, N. Cesa-Bianchi, and P. Fischer Finite-time analysis of the multiarmed bandit problem. Machine Learning 47 (2–3), p. 235–256. Cited by: §D.2, §3. Barsce et al. (2019) J. C. Barsce, J. A. Palombarini, and E. Martínez A hierarchical two-tier approach to hyper-parameter optimization in reinforcement learning. In Anales del Simposio Argentino de Inteligencia Artificial (ASAI), 48 Jornadas Argentinas de Informática (JAIIO), p. 32–38. Cited by: Appendix A. Bellemare et al. (2016) M. G. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, Vol. 29. Cited by: §2. Björnsson et al. (2020) B. Björnsson, C. Borrebaeck, N. Elander, T. Gasslander, D. R. Gawel, M. Gustafsson, R. Jörnsten, E. J. Lee, X. Li, S. Lilja, D. Martínez-Enguita, A. Matussek, P. Sandström, S. Schäfer, M. Stenmarker, X. Sun, O. Sysoev, H. Zhang, and M. Benson Digital twins to personalize medicine. Genome Medicine 12 (1), p. 4. External Links: Document Cited by: Appendix A, §1. Carroll et al. (2006) R. J. Carroll, D. Ruppert, L. A. Stefanski, and C. M. Crainiceanu Measurement error in nonlinear models: a modern perspective. 2nd edition, Chapman and Hall/CRC. Cited by: §5. Chebotar et al. (2019) Y. Chebotar, A. Handa, V. Makoviychuk, M. Macklin, J. Issac, N. Ratliff, and D. Fox Closing the sim-to-real loop: adapting simulation randomization with real world experience. In IEEE International Conference on Robotics and Automation (ICRA), p. 8973–8979. Cited by: Appendix A, §2.1. Chen et al. (2022a) X. Chen, J. Hu, C. Jin, L. Li, and L. Wang Understanding domain randomization for sim-to-real transfer. In International Conference on Learning Representations, Cited by: Appendix A. Chen et al. (2022b) X. Chen, G. Qu, Y. Tang, S. Low, and N. Li Reinforcement learning for selective key applications in power systems: recent advances and future challenges. IEEE Transactions on Smart Grid 13 (4), p. 2935–2958. Cited by: §1. Chua et al. (2018) K. Chua, R. Calandra, R. McAllister, and S. Levine Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems 31. Cited by: Appendix A, §2.1. Cook and Stefanski (1994) J. R. Cook and L. A. Stefanski Simulation-extrapolation estimation in parametric measurement error models. Journal of the American Statistical Association 89 (428), p. 1314–1328. Cited by: §5. Duchi and Namkoong (2021) J. C. Duchi and H. Namkoong Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics 49 (3), p. 1378–1406. Cited by: Appendix A. Dulac-Arnold et al. (2019) G. Dulac-Arnold, D. Mankowitz, and T. Hester Challenges of real-world reinforcement learning. arXiv preprint arXiv:1904.12901. Cited by: §1. Efron and Tibshirani (1994) B. Efron and R. J. Tibshirani An introduction to the bootstrap. Monographs on Statistics and Applied Probability, Vol. 57, Chapman and Hall/CRC, Boca Raton, FL. Cited by: Appendix A. Eysenbach and Levine (2022) B. Eysenbach and S. Levine Maximum entropy RL (provably) solves some robust RL problems. In International Conference on Learning Representations (ICLR), Cited by: Appendix A, §2.1. Fan and Glynn (2022) L. Fan and P. W. Glynn The typical behavior of bandit algorithms. arXiv preprint arXiv:2210.05660. Cited by: §D.2, §3.1. Fan and Glynn (2025) L. Fan and P. W. Glynn The fragility of optimized bandit algorithms. Operations Research 73 (6), p. 3173–3198. Cited by: Appendix A, §1, §3.1. Figueroa et al. (2021) C. A. Figueroa, A. Aguilera, B. Chakraborty, A. Modiri, J. Aggarwal, N. Deliu, U. Sarkar, J. J. Williams, and C. R. Lyles Adaptive learning algorithms to optimize mobile applications for behavioral health: guidelines for design decisions. Journal of the American Medical Informatics Association 28 (6), p. 1225–1234. Cited by: §1. Fujinami et al. (2025) T. Fujinami, B. D. Lee, N. Matni, and G. J. Pappas Domain randomization is sample efficient for linear quadratic control. In Proceedings of the 7th Annual Learning for Dynamics and Control Conference (L4DC), Proceedings of Machine Learning Research, Vol. 283, p. 907–919. Cited by: Appendix A. Gazi et al. (2026) A. H. Gazi, D. Gao, S. Ghosh, Z. Xu, A. L. Trella, P. Klasnja, and S. A. Murphy Digital twins for just-in-time adaptive interventions (JITAIs): framework for optimizing and continually improving JITAIs. Journal of Medical Internet Research 28, p. e72830. External Links: Document Cited by: Appendix A. Ghosh et al. (2024) S. Ghosh, Y. Guo, P. Hung, L. Coughlin, E. Bonar, I. Nahum-Shani, M. Walton, and S. Murphy reBandit: random effects based online RL algorithm for reducing cannabis use. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24), p. 7278–7286. External Links: Document Cited by: Appendix A, §1. Gordon (1941) R. D. Gordon Values of mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. The Annals of Mathematical Statistics 12 (3), p. 364–366. Cited by: §E.2. Henderson et al. (2018) P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger Deep reinforcement learning that matters. In Proceedings of the AAAI conference on artificial intelligence, Vol. 32. Cited by: Appendix A, §1. Ibarz et al. (2021) J. Ibarz, J. Tan, C. Finn, M. Kalakrishnan, P. Pastor, and S. Levine How to train your robot with deep reinforcement learning: lessons we have learned. The International Journal of Robotics Research 40 (4–5), p. 698–721. Cited by: §1. Iyengar (2005) G. N. Iyengar Robust dynamic programming. Mathematics of Operations Research 30 (2), p. 257–280. Cited by: Appendix A, §2.1. Janner et al. (2019) M. Janner, J. Fu, M. Zhang, and S. Levine When to trust your model: model-based policy optimization. In Advances in Neural Information Processing Systems, Vol. 32. Cited by: Appendix A. Jiang and Li (2016) N. Jiang and L. Li Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, p. 652–661. Cited by: Appendix A, §1. Kidambi et al. (2020) R. Kidambi, A. Rajeswaran, P. Netrapalli, and T. Joachims Morel: model-based offline reinforcement learning. Advances in neural information processing systems 33, p. 21810–21823. Cited by: Appendix A, §2.1. Kober et al. (2013) J. Kober, J. A. Bagnell, and J. Peters Reinforcement learning in robotics: a survey. The International Journal of Robotics Research 32 (11), p. 1238–1274. Cited by: §1. Konyushova et al. (2021) K. Konyushova, Y. Chen, T. Paine, C. Gulcehre, C. Paduraru, D. J. Mankowitz, M. Denil, and N. de Freitas Active offline policy selection. Advances in Neural Information Processing Systems 34, p. 24631–24644. Cited by: Appendix A, §2.1. Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári Bandit algorithms. Cambridge University Press. Cited by: §2, §3. Li et al. (2025) C. Li, A. Krause, and M. Hutter Uncertainty-aware robotic world model makes offline model-based reinforcement learning work on real robots. arXiv preprint arXiv:2504.16680. Cited by: Appendix A, Appendix A. Ljung (1999) L. Ljung System identification: theory for the user. 2nd edition, Prentice Hall. Cited by: Appendix A, §1, §5. Mandel et al. (2016) T. Mandel, Y. Liu, E. Brunskill, and Z. Popović Offline evaluation of online reinforcement learning algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 30. Cited by: Appendix A, §1, §1, §1, footnote 1. Mehta et al. (2020) B. Mehta, M. Diaz, F. Golemo, C. J. Pal, and L. Paull Active domain randomization. In Conference on Robot Learning, p. 1162–1176. Cited by: Appendix A. Moerland et al. (2023) T. M. Moerland, J. Broekens, A. Plaat, and C. M. Jonker Model-based reinforcement learning: a survey. Foundations and Trends in Machine Learning 16 (1), p. 1–118. Cited by: Appendix A, §1, §2. Muratore et al. (2021) F. Muratore, C. Eilers, M. Gienger, and J. Peters Data-efficient domain randomization with Bayesian optimization. IEEE Robotics and Automation Letters 6 (2), p. 911–918. Cited by: Appendix A. Muratore et al. (2022a) F. Muratore, T. Gruner, F. Wiese, B. Belousov, M. Gienger, and J. Peters Neural posterior domain randomization. In Conference on Robot Learning (CoRL), Proceedings of Machine Learning Research, Vol. 164, p. 1532–1542. Cited by: Appendix A, §2.1. Muratore et al. (2022b) F. Muratore, F. Ramos, G. Turk, W. Yu, M. Gienger, and J. Peters Robot learning from randomized simulations: a review. Frontiers in Robotics and AI 9, p. 799893. Cited by: Appendix A, §1. Nesterov and Polyak (2006) Y. Nesterov and B. T. Polyak Cubic regularization of newton method and its global performance. Mathematical programming 108 (1), p. 177–205. Cited by: Appendix F. Nilim and El Ghaoui (2005) A. Nilim and L. El Ghaoui Robust control of markov decision processes with uncertain transition matrices. Operations Research 53 (5), p. 780–798. Cited by: Appendix A, §2.1. Osband et al. (2016) I. Osband, C. Blundell, A. Pritzel, and B. Van Roy Deep exploration via bootstrapped dqn. Advances in neural information processing systems 29. Cited by: Appendix A, §2.1. Peng et al. (2018) X. B. Peng, M. Andrychowicz, W. Zaremba, and P. Abbeel Sim-to-real transfer of robotic control with dynamics randomization. In IEEE International Conference on Robotics and Automation (ICRA), p. 3803–3810. Cited by: Appendix A, §1, §2.1. Precup et al. (2000) D. Precup, R. S. Sutton, and S. Singh Eligibility traces for off-policy policy evaluation. In International Conference on Machine Learning (ICML), p. 759–766. Cited by: Appendix A, §1. Puterman (2014) M. L. Puterman Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Cited by: §2. Queeney et al. (2024) J. Queeney, E. C. Ozcan, I. Ch. Paschalidis, and C. G. Cassandras Optimal transport perturbations for safe reinforcement learning with robustness guarantees. Transactions on Machine Learning Research. Cited by: Appendix A. Raffin et al. (2021) A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann Stable-baselines3: reliable reinforcement learning implementations. Journal of Machine Learning Research 22 (268), p. 1–8. Cited by: §5. Rajeswaran et al. (2017) A. Rajeswaran, S. Ghotra, B. Ravindran, and S. Levine EPOpt: learning robust neural network policies using model ensembles. In International Conference on Learning Representations (ICLR), Cited by: Appendix A. Ramos et al. (2019) F. Ramos, R. C. Possas, and D. Fox BayesSim: adaptive domain randomization via probabilistic inference for robotics simulators. In Robotics: Science and Systems (RSS), Cited by: Appendix A, §2.1. Russo et al. (2018) D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen A tutorial on Thompson sampling. Foundations and Trends in Machine Learning 11 (1), p. 1–96. Cited by: Appendix E, §2, §3. Schulman et al. (2017) J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §5. Smirnova et al. (2019) E. Smirnova, E. Dohmatob, and J. Mary Distributionally robust reinforcement learning. arXiv preprint arXiv:1902.08708. Cited by: Appendix A. Tang et al. (2022) S. Tang, F. V. Frujeri, D. Misra, A. Lamb, J. Langford, P. Mineiro, and S. Kochman Towards data-driven offline simulations for online reinforcement learning. arXiv preprint arXiv:2211.07614. Cited by: Appendix A, §1, §2.1, footnote 1. Tiboni et al. (2023) G. Tiboni, K. Arndt, and V. Kyrki DROPO: sim-to-real transfer with offline domain randomization. Robotics and Autonomous Systems 166, p. 104432. Cited by: Appendix A, §2.1, §5, §5. Tiboni et al. (2024) G. Tiboni, P. Klink, J. Peters, T. Tommasi, C. D’Eramo, and G. Chalvatzaki Domain randomization via entropy maximization. In International Conference on Learning Representations, Cited by: Appendix A. Tobin et al. (2017) J. Tobin, R. Fong, A. Ray, J. Schneider, W. Zaremba, and P. Abbeel Domain randomization for transferring deep neural networks from simulation to the real world. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 23–30. Cited by: Appendix A, §2.1. Todorov et al. (2012) E. Todorov, T. Erez, and Y. Tassa MuJoCo: a physics engine for model-based control. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 5026–5033. Cited by: §5. Towers et al. (2025) M. Towers, A. Kwiatkowski, J. Terry, J. U. Balis, G. De Cola, T. Deleu, M. Goulão, A. Kallinteris, M. Krimmel, A. KG, R. Perez-Vicente, A. Pierré, S. Schulhoff, J. J. Tai, H. Tan, and O. G. Younis Gymnasium: a standard interface for reinforcement learning environments. In Advances in Neural Information Processing Systems 38 (NeurIPS 2025), Datasets and Benchmarks Track, p. 163114–163129. Cited by: §5. Trella et al. (2022) A. L. Trella, K. W. Zhang, I. Nahum-Shani, V. Shetty, F. Doshi-Velez, and S. A. Murphy Designing reinforcement learning algorithms for digital interventions: pre-implementation guidelines. Algorithms 15 (8), p. 255. Cited by: Appendix A, §1, §1, §1, §1. Trella et al. (2024) A. L. Trella, K. W. Zhang, S. M. Carpenter, D. Elashoff, Z. M. Greer, I. Nahum-Shani, D. Ruenger, V. Shetty, and S. A. Murphy Oralytics reinforcement learning algorithm. arXiv preprint arXiv:2406.13127. Cited by: Appendix A, §1. Uehara et al. (2026) M. Uehara, C. Shi, and N. Kallus A review of off-policy evaluation in reinforcement learning. Statistical Science 41 (3), p. 561–581. External Links: Document Cited by: Appendix A, §1. van der Vaart (1998) A. W. van der Vaart Asymptotic statistics. Cambridge Series in Statistical and Probabilistic Mathematics, Vol. 3, Cambridge University Press. Cited by: Appendix A, §2, §3.2. Wang et al. (2022) H. Wang, A. Sakhadeo, A. White, J. Bell, V. Liu, X. Zhao, P. Liu, T. Kozuno, A. Fyshe, and M. White No more pesky hyperparameters: offline hyperparameter tuning for RL. Transactions on Machine Learning Research. Cited by: Appendix A, §1, §1, §2.1, §2, footnote 1. Wunder et al. (2010) M. Wunder, M. L. Littman, and M. Babes Classes of multiagent Q-learning dynamics with ϵε-greedy exploration. In Proceedings of the 27th International Conference on Machine Learning (ICML), p. 1167–1174. Cited by: §2. Xie et al. (2025) Y. Xie, J. Chen, W. Tang, Y. Zhang, C. Yu, and Y. Wang Automatic reward shaping from multi-objective human heuristics. arXiv preprint arXiv:2512.15120. Cited by: §C.1, §5, §5, §5. Xu et al. (2026) Z. Xu, Y. Chang, C. Ni, N. Sugavanam, A. H. Gazi, P. Klasnja, E. Ertin, and S. A. Murphy A diffusion-model subpopulation digital twin for mobile health deployment: a case study on the HeartSteps intervention. arXiv preprint arXiv:2607.21403. External Links: 2607.21403, Link Cited by: Appendix A, §1. Yang et al. (2022) M. Yang, B. Dai, O. Nachum, G. Tucker, and D. Schuurmans Offline policy selection under uncertainty. In International Conference on Artificial Intelligence and Statistics, p. 4376–4396. Cited by: Appendix A, §2.1. Yang et al. (2023) S. Yang, O. Nachum, Y. Du, J. Wei, P. Abbeel, and D. Schuurmans Foundation models for decision making: problems, methods, and opportunities. arXiv preprint arXiv:2303.04129. Cited by: Appendix A, §1, §2. Yu et al. (2020) T. Yu, G. Thomas, L. Yu, S. Ermon, J. Y. Zou, S. Levine, C. Finn, and T. Ma MOPO: model-based offline policy optimization. In Advances in Neural Information Processing Systems, Vol. 33, p. 14129–14142. Cited by: Appendix A, §2.1. Zhang et al. (2018) D. Zhang, X. Han, and C. Deng Review on the research and practice of deep learning and reinforcement learning in smart grids. CSEE Journal of Power and Energy Systems 4 (3), p. 362–370. Cited by: §1. Zitovsky et al. (2023) J. P. Zitovsky, D. De Marchi, R. Agarwal, and M. R. Kosorok Revisiting Bellman errors for offline model selection. In International conference on machine learning, p. 43369–43406. Cited by: Appendix A, §2.1. Appendix A Related work This appendix expands the related-work paragraph of Section 2. We organize the literature by the four bodies of work a reader is most likely to connect with our method: the selection of online algorithms from offline data, the construction of simulators and their calibration through domain randomization, ensembles and the bootstrap as tools for uncertainty in RL, and robust or distributionally robust RL. For each, we state what is shared with our setting and where our question differs. Selection of online algorithms from offline data. The performance of online RL algorithms is known to be sensitive to hyperparameters and other design choices (Henderson et al., 2018; Wang et al., 2022; Fan and Glynn, 2025), which makes the choice of what to deploy a first-order concern. Mandel et al. (2016) formalize the offline algorithm selection problem: choose the best online algorithm from a fixed set using only a logged dataset. The problem is related to offline policy evaluation (Precup et al., 2000; Jiang and Li, 2016; Uehara et al., 2026) and offline policy selection (Konyushova et al., 2021; Yang et al., 2022), also called offline model selection (Zitovsky et al., 2023), which rank a fixed set of policies using an offline dataset. The two problems coincide when the policy being selected is allowed to be non-Markovian, since an online algorithm is a policy over interaction histories. Existing offline policy selection methods, however, assume Markovian candidates and rely on fitted value functions or Bellman errors, which do not extend to candidates whose actions depend on the whole history through adaptive exploration. Hyperparameter optimization methods such as Bayesian optimization over the hyperparameter space (Barsce et al., 2019) tune against returns observed online and therefore require repeated deployments, which is what the offline setting rules out. Existing work on offline algorithm selection has predominantly taken the simulator approach: build a simulator from the offline data and evaluate each candidate algorithm in it. Examples include queue-based replay of logged rewards (Mandel et al., 2016), k-nearest-neighbor simulators that resample observed transitions close to the queried state–action pair (Wang et al., 2022), rejection-sampling simulators that correct for the mismatch between the logging policy and the candidate algorithm (Tang et al., 2022), learned or foundation world models used as the evaluation environment (Moerland et al., 2023; Yang et al., 2023), and parametric models that encode domain knowledge in digital health applications (Trella et al., 2022; Trella et al., 2024; Ghosh et al., 2024). In each of these works the candidates are scored in a single simulator fitted to the data, which is the Plug-In rule we study. The digital health works are a partial exception: following the guidelines of Trella et al. (2022), candidates are additionally evaluated across a small set of hand-designed environment variants, for example with different treatment-effect sizes, as a sensitivity analysis. Those variants are chosen by the designer rather than drawn from the estimation uncertainty of the fitted model, and none of these works analyzes how the estimation error of the simulator affects which algorithm is selected. Simulators from offline data and domain randomization. Using offline data to construct a simulator for decision-making is a common thread connecting system identification in control and robotics, which calibrates physical parameters from recorded trajectories (Åström and Eykhoff, 1971; Ljung, 1999); digital twins in medicine, which model patient dynamics to evaluate treatment strategies (Björnsson et al., 2020; Gazi et al., 2026; Xu et al., 2026); and learned world models, which predict environment transitions to support planning and policy learning (Li et al., 2025). In robotics, the mismatch between such a simulator and the physical system is addressed by domain randomization, which trains a policy on a distribution over simulator parameters so that it transfers to the real system (Tobin et al., 2017; Peng et al., 2018); see Muratore et al. (2022b) for a review. The randomization distribution can be fixed by hand or learned: Bayesian system identification places a posterior over physical parameters and randomizes over it (Ramos et al., 2019), and other work adapts the distribution using real rollouts (Chebotar et al., 2019), Bayesian optimization on real-world returns (Muratore et al., 2021), a neural posterior over simulator parameters (Muratore et al., 2022a), a likelihood fitted to offline trajectories (Tiboni et al., 2023), or objectives that seek informative or maximally wide parameter ranges (Mehta et al., 2020; Tiboni et al., 2024). Sampling a distribution of models is also used directly to obtain robustness: EPOpt trains on an ensemble of simulated models and optimizes a conditional value-at-risk of the return across them (Rajeswaran et al., 2017), and SPiDR incorporates the uncertainty about the sim-to-real gap into safety constraints (As et al., 2025). On the theoretical side, Chen et al. (2022a) bound the sim-to-real gap of a policy trained under domain randomization and show that memory-dependent policies are needed to close it, and Fujinami et al. (2025) show that for linear quadratic control, a controller that averages its objective over a posterior on the system parameters is as sample efficient as certainty equivalence, that is, as the Plug-In controller. Two features separate our setting from this literature. First, domain randomization models a mismatch between the simulator and the deployment environment, whereas in our setting there is no mismatch: offline data and deployment come from the same environment, and the spread of the ensemble reflects only the sampling variability of a finite dataset, which vanishes as the data grow. Second, the object being made robust is a fixed policy, whereas we select among online learners that continue to learn after deployment, so what matters is their ranking by online regret rather than the return of any one policy. The result of Fujinami et al. (2025) is the closest in spirit, since it compares averaging over parameter uncertainty with certainty equivalence, but it concerns a fixed controller and asks about sample efficiency rather than about the selection among learners with asymmetric regret. Ensembles and the bootstrap in RL. The bootstrap is a classical tool for approximating sampling uncertainty by resampling the observed data (Efron and Tibshirani, 1994), and the parametric bootstrap we use for bandits is standard (van der Vaart, 1998, Chapter 23). In RL, bootstrapped and probabilistic ensembles quantify epistemic uncertainty to drive exploration (Osband et al., 2016) and to represent dynamics uncertainty in model-based planning and policy optimization (Chua et al., 2018; Janner et al., 2019). In offline model-based RL, the disagreement across ensemble members is turned into a pessimistic penalty that keeps the learned policy away from states where the model is uncertain (Yu et al., 2020; Kidambi et al., 2020), and recent work propagates epistemic uncertainty through multi-step predictions of autoregressive world models so that policies trained entirely offline can be deployed on physical robots (Li et al., 2025). In all of these methods the ensemble is part of the algorithm being run and changes how that algorithm acts, either by adding an exploration bonus or by penalizing uncertain regions. In our setting the ensemble sits outside the candidate algorithms, which are evaluated as black boxes, and it changes only which candidate is chosen; the candidates themselves are not modified. Robust and distributionally robust RL. Robust MDPs account for model uncertainty by optimizing the worst-case value over an uncertainty set of transition kernels (Iyengar, 2005; Nilim and El Ghaoui, 2005). Distributionally robust optimization extends this to uncertainty sets around an empirical distribution, in supervised learning (Duchi and Namkoong, 2021) and in RL, where it yields risk-averse exploration with lower-bound guarantees on state values (Smirnova et al., 2019) or safe policies with robustness guarantees under optimal-transport perturbations of the dynamics (Queeney et al., 2024). Regularized RL objectives have also been shown to be equivalent to robustness against certain classes of environment perturbations (Eysenbach and Levine, 2022). These methods share our motivation of accounting for model uncertainty, but they do so by changing the objective to a worst case over an uncertainty set, and again the object being optimized is a fixed policy. We keep the objective as a plain average over the ensemble and show that this average already acts as a curvature regularization of the Plug-In criterion (Proposition 4) and suffices for the regret gains of Section 3; no pessimism is required. Summary. The works discussed above primarily take a practical perspective, showing how modeling simulator uncertainty can improve policy robustness and the reliability of model-based learning. In contrast, this paper approaches the problem from a theoretical perspective, demonstrating how a Plug-In simulator that ignores estimation uncertainty can lead to underexploration. This failure is particularly consequential in online algorithm selection, where exploration determines how effectively the selected learner acquires experience during deployment. We characterize the resulting regret and show how accounting for simulator uncertainty through ensemble-based selection mitigates this failure. Appendix B Simulation details for the two-armed bandit figures This appendix states the protocol behind Figure 2, Figure 3 and its Thompson Sampling counterpart, Figure 6. The three figures share one measured objective surface and one pair of selection rules, given in Sections B.1–B.3; Sections B.4 and B.6 say what each figure draws from them. B.1 Environments and candidate sets For a margin Δ∈ℝ and a noise level σ>0σ>0, let MΔ,σM_ ,σ denote the two-armed Gaussian bandit with μ1=Δ _1= , μ2=0 _2=0 and Rt|At=a∼⁡(μa,σ2)R_t A_t=a ( _a,σ^2). The true environment is M∗=M1,3M^*=M_1,3, and the online horizon is T=5000T=5000. Adding a constant to both arm means leaves the action sequence of (4) and of (5) unchanged and shifts JTJ_T by an amount free of θ, and relabeling the arms replaces Δ by |Δ|| | and again shifts JTJ_T by an amount free of θ. A two-armed Gaussian bandit is therefore summarized by (Δ,σ)( ,σ) for the purpose of ranking candidates. The candidate sets are the discrete grids ΘUCB=0.1, 0.2,…, 1.1⋅σ2,ΘTS=0.1, 0.2,…, 1.5⋅σ2, _ UCB=\0.1,\,0.2,\,…,\,1.1\·σ^2, _ TS=\0.1,\,0.2,\,…,\,1.5\·σ^2, (12) where σ=3σ=3 is the noise level of M∗M^*; the grid for (5) runs further because its objective is flatter above θT∗ _T^*. Every axis and legend reports the normalized exploration level θ/σ2θ/σ^2. B.2 The objective surface Write Θ for the candidate set of the algorithm at hand. The objective JT(πθ,MΔ,σ)J_T( _θ,M_ ,σ) is measured by simulation for every θ∈Θθ∈ and every (Δ,σ)∈=0.075, 0.225,…, 5.925×0.9, 1.0,…, 5.7, ( ,σ) =\0.075,\,0.225,\,…,\,5.925\×\0.9,\,1.0,\,…,\,5.7\, (13) which is 40×4940× 49 pairs whose Δ values sit half a step off the origin, so that no cell is centered on Δ=0 =0. The cell of G nearest M∗M^* is M0.975, 3M_0.975,\,3. The runs use common random numbers. Fix a seed and draw ψt,r,a,ζt,r,a∼iid⁡(0,1),t≤T,r≤2000,a∈. _t,r,a,\ _t,r,a iid N(0,1), t≤ T, r≤ 2000, a . (14) In replication r of the run at (θ,Δ,σ)(θ, ,σ), pulling arm a at round t returns μa+σψt,r,a _a+σ _t,r,a, and the posterior draw of (5) at that round is μ^a(t−1)+θ/Na(t−1)ζt,r,a μ_a(t-1)+ θ/N_a(t-1)\, _t,r,a. The single draw (14) serves every (θ,Δ,σ)(θ, ,σ) of the run. With N2,r(T)N_2,r(T) the pull count of the suboptimal arm in replication r, the estimate is J^T(πθ,MΔ,σ)=TΔ−Δ2000∑r=12000N2,r(T), J_T( _θ,M_ ,σ)=T - 2000 _r=1^2000N_2,r(T), (15) which subtracts the cumulative pseudo-regret from the return of the optimal arm. Sixteen runs with distinct seeds are pooled, giving 32,00032,000 replications per (θ,Δ,σ)(θ, ,σ). At the cell nearest M∗M^* the pooled standard error of (15) is 0.940.94 at the best candidate for (4) and 1.121.12 for (5), rising to 8.38.3 and 8.98.9 at the smallest candidate. B.3 Offline data, the Plug-In simulator and the ensemble The behavior policy draws each AtA_t uniformly on A, so offD_ off holds Toff=25T_ off=25 pairs and N1(Toff)N_1(T_ off) is binomial. Let SSa S_a be the within-arm sum of squares of arm a in offD_ off. The Plug-In simulator is M^=MΔ^,σ M=M_ , σ with Δ^=μ^1(Toff)−μ^2(Toff),σ^2=S1+S2Toff−2, = μ_1(T_ off)- μ_2(T_ off), σ^2= S_1+ S_2T_ off-2, (16) one reward variance pooled across the two arms. Ensemble member i is fitted by (16) to a fresh dataset of ToffT_ off pairs drawn from M M under the same behavior policy, giving M^(i)=MΔ^(i),σ^(i) M^(i)=M_ ^(i), σ^(i), a parametric bootstrap of (16). The two selections are θ^plug,T=argmaxθ∈Θ⁡JT(πθ,M^),θ^UA,T=argmaxθ∈Θ⁡1n∑i=1nJT(πθ,M^(i)),n=8000. θ_ plug,T= _θ∈ J_T( _θ, M), θ_ UA,T= _θ∈ 1n _i=1^nJ_T( _θ, M^(i)), n=8000. (17) Both objectives in (17) are read off (15) by bilinear interpolation over (13), the argument first clipped to G; no fresh rollout is simulated at selection time. Selections are tabulated on a common grid of fits: the window and bin size are Δ^∈[−2.5, 4.5],σ^∈[1.5, 4.5],bin 0.15×0.10, ∈[-2.5,\,4.5], σ∈[1.5,\,4.5], bin 0.15× 0.10, (18) and a dataset is assigned the selection computed at the center of the bin its fit (16) falls in. B.4 Figure 2 Both rows are evaluated at the cell of G nearest M∗M^*, with one column per algorithm. The top row plots the cumulative pseudo-regret TΔ−J^T(πθ,MΔ,σ)T - J_T( _θ,M_ ,σ) of (15) against θ/σ2θ/σ^2 over the candidate set (12), and the dotted line marks its minimizer θT∗ _T^*. Its minimum is the pseudo-regret of the best candidate, so the curve does not reach zero. The bottom row plots the distribution of θ^plug,T θ_ plug,T and of θ^UA,T θ_ UA,T over independent draws of offD_ off from M∗M^*. The annotation gives the mean and the variance, over those draws, of the cumulative pseudo-regret of the selected candidate, measured on the scale of the row above. The two rules are compared on one set of offline datasets, each assigned its selection through (18). B.5 Asymmetry across environment configurations The top row of Figure 2 is one environment. This section repeats that measurement over a grid of environments. Each environment is measured on its own noise-relative candidate grid θ=cσ2,c∈0.05, 0.10,…, 2.00, θ=c\,σ^2, c∈\0.05,\,0.10,\,…,\,2.00\, (19) so that the best candidate of every environment lies inside the grid and the horizontal axis θ/σ2θ/σ^2 means the same thing in every panel. The environments are the sixteen pairs (Δ,σ)∈0.25, 0.5, 1, 2×1, 2, 3, 5. ( ,σ)∈\0.25,\,0.5,\,1,\,2\×\1,\,2,\,3,\,5\. (20) Each (θ,Δ,σ)(θ, ,σ) is measured at T=5000T=5000 from 40,00040,000 replications sharing the common random numbers of (14), by a run separate from the surface of Section B.2. At (Δ,σ)=(1,3)( ,σ)=(1,3) the two agree: the cumulative pseudo-regret at c=0.1c=0.1, 0.30.3 and 0.60.6 is 586586, 143143 and 7979 here against 577577, 142142 and 8181 in Figure 2. Write c⋆c for the maximizer of J^T(πcσ2,MΔ,σ) J_T( _cσ^2,M_ ,σ) over (19). Figures 4 and 5 plot the excess regret of a candidate over the best one, as a percentage of the regret of the best one, e⁡(c)=100⋅J^T(πc⋆σ2,MΔ,σ)−J^T(πcσ2,MΔ,σ)TΔ−J^T(πc⋆σ2,MΔ,σ). e(c)=100· J_T( _c σ^2,M_ ,σ)- J_T( _cσ^2,M_ ,σ)T - J_T( _c σ^2,M_ ,σ). (21) The normalization in (21) makes the panels comparable: the regret at c⋆c ranges from 0.40.4 to 11001100 over (20), while e is a ratio. The asymmetry holds in every configuration. Taking e at half and at twice the best exploration level, by linear interpolation in c, the ratio e⁡(c⋆/2)/e⁡(2c⋆)e(c /2)/e(2c ) exceeds one in all sixteen configurations for both algorithms: for (4) it has median 1.71.7 and range 1.11.1 to 3.83.8, and for (5) median 1.91.9 and range 1.41.4 to 4.74.7. Halving the exploration level therefore costs between 1.11.1 and 4.74.7 times what doubling it costs, across margins spanning a factor of eight and noise levels spanning a factor of five. Figure 4: The cost of misspecified exploration is asymmetric in every environment tested, under UCB. Excess regret (21) of UCB(θ)(θ) against θ/σ2θ/σ^2, for the environments (20), at T=5000T=5000. The triangle and the dashed line mark the best candidate. The vertical scale is per panel, since the regret at the best candidate varies by three orders of magnitude across these environments. Figure 5: The cost of misspecified exploration is asymmetric in every environment tested, under Thompson Sampling. The counterpart of Figure 4 for the algorithm of (5). B.6 Figures 3 and 6 The contours are level sets of the law of (Δ^,σ^)( , σ) under (16) applied to the same 10610^6 datasets, at the levels enclosing 50%50\%, 90%90\% and 99%99\% of its mass. The left and center panels report θ^plug,T/σ2 θ_ plug,T/σ^2 and θ^UA,T/σ2 θ_ UA,T/σ^2 over the bins (18), and the right panel reports their difference. Where an ensemble member falls outside G its argument is clipped to the boundary; this affects more than 5%5\% of the members only in the upper right corner of the window, which carries almost none of the mass of the contours. B.7 Budgets Each cell of (15) averages 32,00032,000 runs of T rounds, which is 6.9×1086.9× 10^8 runs over the surface for (4) and 9.4×1089.4× 10^8 for (5). The selections use 10610^6 draws of offD_ off and n ensemble members per bin, each scored by interpolation of (15) rather than by fresh simulation. The bins at the 50%50\%, 90%90\% and 99%99\% contours hold about 22002200, 470470 and 6969 of the 10610^6 datasets. Figure 6: Uncertainty-Aware (UA) selection leads to greater exploration than Plug-In under Thompson Sampling. The counterpart of Figure 3 for the algorithm of (5), on the candidate grid ΘTS _ TS of (12). Star, contours and panels are as in Figure 3. Appendix C Deep reinforcement learning experiments This appendix records the definitions and settings behind Section 5 and the results not shown there. Throughout, MλM_λ, λ∗λ^*, λ λ, λ^(i) λ^(i), θ and JTJ_T are as defined in Section 5. C.1 Tasks, reward and success criterion The tasks are Hopper-v5 (three actuators) and Walker2d-v5 (six actuators) from Gymnasium, with action space =[−1,1]dA=[-1,1]^d_A, where d_A is the number of actuators. An episode ends after H=250H=250 steps or when the robot leaves Gymnasium’s healthy region. The feature vector is φ⁡(S,A)=(1,vx,−∥A∥22), (S,A)= (1,\ v_x,\ - A _2^2 ), (22) where the first entry is a survival bonus paid on every step, vxv_x is the forward velocity of the torso reported by the environment, and the third entry is the squared actuation. The learner trains on Rθ(S,A)=θ⊤φ(S,A)=θsurv+θfwdvx−θctrl∥A∥22,θsurv=1. R_θ(S,A)=θ (S,A)= _ surv+ _ fwd\,v_x- _ ctrl\, A _2^2, _ surv=1. (23) The score of an episode is computed from the true state. Let H′≤H ≤ H be the number of steps the episode lasted, xH′x_H the horizontal distance traveled by its end, and c¯=1H′∑h=1H′∥Ah∥22 c= 1H _h=1^H A_h _2^2 the average squared actuation over those steps. Then score=(c¯≤cmax)⋅min⁡1,max⁡0,xH′−xloxhi−xlo. score=1( c≤ c_ )· \! \1,\ \! \0,\ x_H -x_ lox_ hi-x_ lo \ \. (24) The objective JT(πθ,M)J_T( _θ,M) of Section 5 is the expected score of the policy that πθ _θ has learned in M; its estimate, the average score over 5050 evaluation episodes, is the success score. The thresholds (Table 2) follow the calibration protocol of Xie et al. (2025): a policy is trained at their default weights θ=(1,1,0.002)θ=(1,1,0.002) on the true environment and rolled out for 66 seeds and 100100 episodes each; xhix_ hi is the median of its xH′x_H , xlo=xhi/2x_ lo=x_ hi/2, and cmaxc_ is 0.90.9 times its mean squared actuation. Two details differ from Xie et al. (2025). The thresholds are re-derived at our training budget, because a policy trained for 3×1053× 10^5 steps travels past their published distance thresholds at every weight vector in the grid. The effort constraint is applied to the episode average of ∥A∥22 A _2^2 rather than to its value at every step, because at our budget the per-step maximum equals the actuator limit for every trained policy. Table 2: Thresholds of the success criterion (24), in meters and in units of ∥A∥22 A _2^2. task xlox_ lo xhix_ hi cmaxc_ Hopper 1.5231.523 3.0473.047 1.5481.548 Walker2d 1.6691.669 3.3373.337 3.3463.346 C.2 Candidate set and true success scores The candidate set Θ is the product of θfwd∈0.3,1,3,10,30 _ fwd∈\0.3,1,3,10,30\ and θctrl∈0.002,0.01,0.05,0.25,1 _ ctrl∈\0.002,0.01,0.05,0.25,1\ on Hopper (2525 weight vectors), and of θfwd∈0.03,0.1,0.3,1,3,10 _ fwd∈\0.03,0.1,0.3,1,3,10\ and the same θctrl _ ctrl on Walker2d (3030 weight vectors); the Walker2d range was shifted downward so that its optimum is interior. The value of a weight vector is JT(πθ,M∗)J_T( _θ,M^*), the success score of a policy trained on the true environment under it. Table 3 gives it for every θ∈Θθ∈ ; the success score of a selected θ θ is read from it, and the score of θT∗ _T^* is its ceiling. Both tasks have θT∗ _T^* at (θfwd,θctrl)=(1,0.25)( _ fwd, _ ctrl)=(1,0.25), with JT(πθT∗,M∗)=0.991J_T( _ _T^*,M^*)=0.991 on Hopper and 0.6890.689 on Walker2d. Table 3: Success score JT(πθ,M∗)J_T( _θ,M^*) of every weight vector θ∈Θθ∈ on the true environment, θsurv=1 _ surv=1, under the sensor at σrel=0.05 _rel=0.05; 3030 PPO seeds per cell on Hopper and 3232 on Walker2d, 5050 evaluation episodes per seed. The optimum θT∗ _T^* of each task is in bold; the success score of a selected θ is read from it. Hopper θctrl _ ctrl θfwd _ fwd 0.0020.002 0.010.01 0.050.05 0.250.25 11 0.30.3 0.1900.190 0.0670.067 0.0620.062 0.2180.218 0.0000.000 11 0.3810.381 0.5550.555 0.8720.872 0.9910.991 0.5530.553 33 0.3650.365 0.4560.456 0.7830.783 0.9300.930 0.9360.936 1010 0.3780.378 0.3600.360 0.5520.552 0.7640.764 0.7640.764 3030 0.2550.255 0.3680.368 0.4380.438 0.6140.614 0.6370.637 Walker2d θctrl _ ctrl θfwd _ fwd 0.0020.002 0.010.01 0.050.05 0.250.25 11 0.030.03 0.0010.001 0.0020.002 0.0000.000 0.0000.000 0.0000.000 0.10.1 0.0010.001 0.0580.058 0.0620.062 0.0090.009 0.0000.000 0.30.3 0.0480.048 0.1400.140 0.5270.527 0.5170.517 0.0000.000 11 0.0130.013 0.1340.134 0.4560.456 0.6890.689 0.0000.000 33 0.0130.013 0.0200.020 0.0560.056 0.5360.536 0.0930.093 1010 0.0330.033 0.0400.040 0.0260.026 0.1070.107 0.1430.143 C.3 Learner The learner is PPO from Stable-Baselines3 with a two-hidden-layer MLP policy of width 6464 and tanh activations, 10241024 steps per update, minibatches of 6464, 1010 epochs per update, discount 0.990.99, GAE parameter 0.950.95, clipping range 0.20.2, no entropy bonus, learning rate 3×10−43× 10^-4, and 3×1053× 10^5 environment steps in a single environment. Observations and rewards are normalized by running estimates of their mean and variance, with normalized observations clipped to [−10,10][-10,10]; the observation statistics are frozen for evaluation. Reward normalization makes training invariant to the scale of θ, which is why θsurv _ surv is fixed at 11. Evaluation runs the deterministic policy for 5050 episodes. Every training run in the experiment uses these settings; only the reward weights θ, the physics parameter λ and the seed vary. C.4 True environment, offline data and sensor The physics parameter λ=(λmass,λfric,λdamp)λ=( _ mass, _ fric, _ damp) multiplies the MuJoCo model’s body masses, the sliding coefficient of every geom’s friction, and the damping of every degree of freedom, relative to the factory model at λ=(1,1,1)λ=(1,1,1). The true environment is M∗=Mλ∗M^*=M_λ^* with λ∗=(1.5,0.7,1.4)λ^*=(1.5,0.7,1.4); the simulator MλM_λ is the same model with the factors set to λ. The offline dataset offD_ off is ToffT_ off episodes on M∗M^* under a behavior policy πb _b that draws each action uniformly from A, with the termination rules above. The log records the simulator state (qpos,qvel)(q_ pos,q_ vel) without the horizontal position, not the Gymnasium observation, which clips velocities to ±10± 10; in this appendix St,hS_t,h denotes that logged state at step h of offline episode t. The sensor adds independent Gaussian noise to every coordinate of the logged state and of the observation the policy receives. Its standard deviation on coordinate j is σrelσj _rel\, _j with σrel=0.05 _rel=0.05, where σj _j is the standard deviation of that coordinate over 20002000 steps of the random policy on the factory model, floored at 10−310^-3. The same σj _j and the same σrel _rel apply to the offline log, to training in every simulator, and to training and evaluation on the true environment. The reward features φ and the score are computed from the true state. The noise is what makes identification a statistical problem: MuJoCo is deterministic, so with an exact log a handful of transitions would pin down λ∗λ^* to machine precision, the fitted simulator would equal M∗M^*, and the Plug-In and UA rules would select the same θ. Because the same noise is applied everywhere, the only difference between M∗M^*, M M and the ensemble members is the value of λ. C.5 Identification Per-episode least squares. For one offline episode t with logged transitions (St,h,At,h,St,h+1)(S_t,h,A_t,h,S_t,h+1), at most 8080 of them evenly spaced, the residual at a candidate λ is ϱt,h(λ)=(fλ(St,h,At,h)−St,h+1)/τt, _t,h(λ)= (f_λ(S_t,h,A_t,h)-S_t,h+1 )/ _t, (25) where fλf_λ resets the MuJoCo model to St,hS_t,h, sets the factors to λ, applies At,hA_t,h for one control step and returns the resulting state, and the division is coordinate-wise by τt _t, the per-coordinate standard deviation of the logged next states in episode t. The estimate minimizes ∑h∥ϱt,h(λ)∥22 _h _t,h(λ) _2^2 by trust-region least squares started at (1,1,1)(1,1,1) inside the box [0.1,10]3[0.1,10]^3, with finite-difference step 10−310^-3. The naive estimate of λ is the mean of the per-episode estimates. SIMEX. For each episode t and each noise multiplier ω∈0,0.5,1,1.5,2ω∈\0,0.5,1,1.5,2\, Gaussian noise of standard deviation ωσrelσj ω\, _rel\, _j is added to the logged states and next states and the per-episode estimate is recomputed, averaged over two noise draws for ω>0ω>0; this gives a curve λ^t(ω) λ_t(ω) per episode. For a set ℐI of episodes, the curves are averaged over t∈ℐt , a quadratic in ω is fitted to the average at the five ω values, and the estimate is its value at ω=−1ω=-1, clipped to [0.1,10]3[0.1,10]^3. Because the extrapolation is linear in the curve values, this equals the average over ℐI of the per-episode corrected estimates λ^t λ_t of the main text, up to the final clipping. The Plug-In estimate λ λ takes ℐI to be all ToffT_ off episodes. Table 4 reports the bias and spread of the naive and SIMEX estimates across independent offline datasets. The naive damping bias is between +0.58+0.58 and +0.93+0.93 at every ToffT_ off on both robots; SIMEX reduces it to between +0.13+0.13 and +0.46+0.46, at a larger spread. Table 4: Physics identification under the sensor (σrel=0.05 _rel=0.05). The truth is λ∗=(1.5,0.7,1.4)λ^*=(1.5,0.7,1.4) on both robots. Bias and standard deviation of the estimate across independent offline datasets (1212 datasets for the naive fit, 2424 for SIMEX); the last column is the bootstrap standard deviation of the damping estimate divided by its across-dataset standard deviation, which is 11 for a calibrated ensemble of members. mass friction damping ToffT_ off fit bias sd bias sd bias sd boot/true Hopper 2020 naive +0.008+0.008 0.0420.042 +0.069+0.069 0.1370.137 +0.932+0.932 0.4020.402 0.710.71 2020 SIMEX +0.011+0.011 0.2000.200 +0.162+0.162 0.4700.470 +0.463+0.463 0.9140.914 0.910.91 8080 naive +0.024+0.024 0.0210.021 +0.015+0.015 0.0060.006 +0.814+0.814 0.1220.122 1.151.15 8080 SIMEX +0.022+0.022 0.1330.133 +0.007+0.007 0.1940.194 +0.238+0.238 0.4670.467 1.011.01 320320 naive +0.034+0.034 0.0160.016 +0.046+0.046 0.0290.029 +0.815+0.815 0.0680.068 1.111.11 320320 SIMEX +0.044+0.044 0.0570.057 +0.048+0.048 0.0780.078 +0.128+0.128 0.1550.155 1.561.56 Walker2d 2020 naive +0.044+0.044 0.0250.025 +0.166+0.166 0.1760.176 +0.576+0.576 0.2620.262 0.890.89 2020 SIMEX +0.004+0.004 0.0960.096 +0.020+0.020 0.5250.525 +0.289+0.289 0.8710.871 0.750.75 8080 naive +0.057+0.057 0.0220.022 +0.196+0.196 0.1100.110 +0.697+0.697 0.1830.183 0.790.79 8080 SIMEX +0.008+0.008 0.0470.047 +0.048+0.048 0.2780.278 +0.204+0.204 0.2370.237 1.461.46 320320 naive +0.057+0.057 0.0100.010 +0.147+0.147 0.0280.028 +0.687+0.687 0.0530.053 1.331.33 320320 SIMEX +0.014+0.014 0.0280.028 +0.020+0.020 0.1300.130 +0.184+0.184 0.1620.162 1.081.08 C.6 UA ensemble Member i=1,…,n=12i=1,…,n=12 draws a multiset ℐ(i)I^(i) of ToffT_ off episodes from offD_ off with replacement and uses the SIMEX estimate over ℐ(i)I^(i), λ^(i)=Toff−1∑t∈ℐ(i)λ^t λ^(i)=T_ off^-1 _t ^(i) λ_t, so that M^(i)=Mλ^(i) M^(i)=M_ λ^(i). The per-episode curves are computed once per replication and reused by every member. The last column of Table 4 is the standard deviation of the members’ damping estimate divided by the standard deviation of the Plug-In estimate across independent datasets. C.7 Selection protocol The success score in the simulator is tabulated once per cell and read by every replication. For each task and ToffT_ off, SIMEX estimates are computed on 2424 independent offline datasets, and a 3×53× 5 lattice is placed over the two coordinates of λ with the largest spread, friction and damping in every cell, at the 22nd to 9898th percentiles of the estimates; mass is held at the mean of the estimates (Table 5). At every lattice point λ and every θ∈Θθ∈ , PPO is trained in MλM_λ with 99 seeds and the success score of each seed is stored. The true success scores JT(πθ,M∗)J_T( _θ,M^*) use 3030 seeds on Hopper and 3232 on Walker2d (Table 3). Table 5: The lattice of identified physics parameters λ on which the simulated success scores are tabulated, one per cell. The two axes are the 22nd to 9898th percentiles of the SIMEX estimates over 2424 independent offline datasets; the third parameter is held at their mean. task ToffT_ off friction axis damping axis mass Hopper 2020 0.24,0.72,2.03\0.24,0.72,2.03\ 0.42,1.28,1.77,2.32,3.77\0.42,1.28,1.77,2.32,3.77\ 1.5111.511 Hopper 8080 0.34,0.71,1.06\0.34,0.71,1.06\ 0.79,1.37,1.63,2.05,2.31\0.79,1.37,1.63,2.05,2.31\ 1.5221.522 Hopper 320320 0.60,0.74,0.88\0.60,0.74,0.88\ 1.25,1.40,1.52,1.64,1.78\1.25,1.40,1.52,1.64,1.78\ 1.5441.544 Walker2d 2020 0.10,0.58,2.03\0.10,0.58,2.03\ 0.14,1.03,1.68,2.34,2.95\0.14,1.03,1.68,2.34,2.95\ 1.5041.504 Walker2d 8080 0.44,0.64,1.34\0.44,0.64,1.34\ 1.18,1.43,1.60,1.84,1.96\1.18,1.43,1.60,1.84,1.96\ 1.5081.508 Walker2d 320320 0.42,0.73,0.95\0.42,0.73,0.95\ 1.24,1.49,1.62,1.68,1.81\1.24,1.49,1.62,1.68,1.81\ 1.5141.514 One replication proceeds as follows. 1. Draw offD_ off on M∗M^* and compute λ λ and λ^(1),…,λ^(n) λ^(1),…, λ^(n). 2. The success score of one simulated training run at λ and θ is a seed drawn with replacement from the 99 stored seeds, after bilinear interpolation of the stored table at λ over the friction and damping axes; λ is clipped to the lattice. 3. The Plug-In rule draws K=12K=12 runs per θ at λ λ and selects θ^plug,T θ_ plug,T, the θ with the largest mean, as in (2). The UA rule draws K/n=1K/n=1 run per θ per member and selects θ^UA,T θ_ UA,T, the θ with the largest mean over members, as in (3); the 1010th-percentile and Borda variants replace the mean over members by the 1010th percentile of the member values and by the mean of the members’ ranks. Both rules use K simulated runs per θ. 4. The success score of a rule is JT(πθ^,M∗)J_T( _ θ,M^*), read from Table 3. Each cell runs 300300 replications; the offline dataset and the seed draws are shared between the rules, and the paired t statistic of the difference in score is reported. Because every replication reads the same table, replications are not independent and the standard error of a single rule’s score is optimistic; only paired contrasts are used as evidence. C.8 Results Table 6 reports the six cells of Table 1 under the mean, 1010th-percentile and Borda variants of the UA rule, with paired t statistics, and the fraction of replications in which each rule selects θT∗ _T^*. The mean variant has the highest score of the three in every cell. The 1010th-percentile variant is significantly worse than the Plug-In on Walker2d at Toff=20T_ off=20; the Borda variant is never significantly different from the Plug-In. Table 6: Success score JT(πθ^,M∗)J_T( _ θ,M^*) of the weight vector selected by the Plug-In and by the UA rule under three ways of combining the members, in the six cells of Table 1. Mean score and the paired t statistic of the difference from the Plug-In (positive favors UA; bold where |t|>1.96|t|>1.96), 300300 replications. “share at optimum” is the fraction of replications that select θT∗ _T^*. mean 1010th percentile Borda share at optimum ToffT_ off Plug-In score t score t score t Plug-In UA Hopper, JT(πθT∗,M∗)=0.991J_T( _ _T^*,M^*)=0.991 2020 0.9330.933 0.9560.956 +3.80+3.80 0.9290.929 −0.35-0.35 0.9260.926 −0.89-0.89 62%62\% 69%69\% 8080 0.9650.965 0.9710.971 +1.57+1.57 0.9680.968 +0.69+0.69 0.9690.969 +0.87+0.87 72%72\% 81%81\% 320320 0.9760.976 0.9810.981 +1.91+1.91 0.9780.978 +0.73+0.73 0.9690.969 −1.91-1.91 84%84\% 88%88\% Walker2d, JT(πθT∗,M∗)=0.689J_T( _ _T^*,M^*)=0.689 2020 0.5850.585 0.5940.594 +1.25+1.25 0.5580.558 −3.45-3.45 0.5710.571 −1.71-1.71 47%47\% 53%53\% 8080 0.5940.594 0.6160.616 +3.32+3.32 0.5900.590 −0.72-0.72 0.6060.606 +1.76+1.76 47%47\% 59%59\% 320320 0.5900.590 0.6100.610 +2.96+2.96 0.5930.593 +0.50+0.50 0.6030.603 +1.91+1.91 44%44\% 54%54\% Figure 7 shows the UA selection given the Plug-In selection in every cell, with the weight vectors sorted by θfwd/θctrl _ fwd/ _ ctrl. Relative to θT∗ _T^*, given a Plug-In selection with a larger ratio, UA selects a smaller ratio in 5555 to 95%95\% of those datasets; given a smaller ratio, UA selects a larger one in 7474 to 100%100\%. Selections with a larger ratio than θT∗ _T^* account for 7474 to 98%98\% of the Plug-In’s shortfall in score below θT∗ _T^*. Figure 7: The UA selection θ^UA,T θ_ UA,T given the Plug-In selection θ^plug,T θ_ plug,T, in the six cells of Table 1, 300300 paired offline datasets each. The weight vectors on both axes are sorted by the ratio θfwd/θctrl _ fwd/ _ ctrl; a larger ratio pays more for moving forward and charges less for actuation, so the trained policy runs harder. Only weight vectors selected at least once are shown. Each column is one Plug-In selection, with the number of datasets in parentheses; the bars in a column give the conditional distribution of the UA selection at its position on the vertical axis. Bars on the dashed diagonal mean the two rules agree; red bars above it mean UA selected a larger ratio than the Plug-In did, blue bars below it a smaller one. Appendix D Theoretical analysis of the UCB algorithm In this section, we provide a detailed theoretical analysis of the behavior and selection performance of UCB(θ)(θ) in a two-armed Gaussian bandit, building on the setup in Section 3. For completeness, we restate the algorithm in Alg. 1. Algorithm 1 UCB(θ)(θ) 1: Pull each arm once. 2: for t=3,…,Tt=3,…,T do 3: For i∈1,2i∈\1,2\, compute Ni(t−1,θ)N_i(t-1;θ) and μ^i(t−1,θ) μ_i(t-1;θ), the number of pulls and empirical mean reward for arm i up to time t−1t-1. 4: Pull At=At(θ)∈arg⁡maxi∈1,2Ui(t,θ)A_t=A_t(θ)∈ _i∈\1,2\U_i(t;θ), where Ui(t,θ):=μ^i(t−1,θ)+2θlog⁡tNi(t−1,θ)U_i(t;θ):= μ_i(t-1;θ)+ 2θ tN_i(t-1;θ). 5: end for We first introduce some additional notation. Notation. For x∈ℝx and a compact interval =[v¯,v¯]⊂(0,∞)V=[ v, v]⊂(0,∞), define Π(x):=min⁡v¯,max⁡v¯,x _V(x):= \ v, \ v,x\\. For a random element X, we write σ⁡(X)σ(X) for the sigma-field generated by X. Let Φ and ϕφ denote the cumulative distribution function and density of the standard normal distribution. For a∈ℝa , write a+:=max⁡a,0a_+:= \a,0\. For a generic two-armed Gaussian environment ν=(⁡(μ1,τ12),⁡(μ2,τ22))ν= (N( _1, _1^2),N( _2, _2^2) ) with μ1≠μ2 _1≠ _2 and τ12,τ22>0 _1^2, _2^2>0, let o⁡(ν)o(ν) and s⁡(ν)s(ν) denote its optimal and suboptimal arm, respectively, and let δ⁡(ν):=μo⁡(ν)−μs⁡(ν)>0δ(ν):= _o(ν)- _s(ν)>0. Throughout this section, we let πθ _θ denote the policy induced by UCB(θ)(θ) in Alg. 1; in addition, to simplify writing, ∀θ>0∀θ>0, we denote the expected regret of UCB(θ)(θ) (Alg. 1) in environment ν over horizon T as RegT(θ,ν):=RegT(πθ,ν)=δ⁡(ν)⋅ν[Ns⁡(ν)(T,θ)]. Reg_T(θ;ν):= Reg_T( _θ,ν)=δ(ν)·E_ν [N_s(ν)(T;θ) ]. (26) Here, Ni(T,θ)N_i(T;θ) denotes the number of times arm i is selected over T rounds when UCB⁡(θ)UCB(θ) is deployed. When the two means are equal, we define RegT(θ,ν)=0 Reg_T(θ;ν)=0. Without loss of generality, we assume that given the fitted environment M M obtained from the offline data offD_ off, the Plug-In rule selects the smallest minimizer of the expected regret in M M: θ^plug,T=θ^plug,T(off):=min⁡argminθ∈Θ⁡RegT(θ,M^). θ_ plug,T= θ_ plug,T(D_ off):= _θ∈ Reg_T(θ; M). (27) To define the UA objective, let Z=(Z1,Z2)Z=(Z_1,Z_2) with Z1,Z2∼iid⁡(0,1)Z_1,Z_2 N(0,1), independent of offD_ off. Define the generic perturbed environment M~(Z):=(⁡(μ~1(Z1),σ^12),⁡(μ~2(Z2),σ^22)), M(Z):= (N\! ( μ_1(Z_1), σ_1^2 ),N\! ( μ_2(Z_2), σ_2^2 ) ), where μ~i(Zi):=μ^i+σ^iT1,offZi μ_i(Z_i):= μ_i+ σ_i T_1, offZ_i for each arm i∈1,2i∈\1,2\. The Uncertainty-Aware rule selects the smallest minimizer of the expected regret over an ensemble of perturbed environments: θ^UA,T=θ^UA,T(off):=min⁡argminθ∈Θ⁡RegUA,T(θ,off), θ_ UA,T= θ_ UA,T(D_ off):= _θ∈ Reg_ UA,T(θ;D_ off), (28) where RegUA,T(θ,off):=Z[RegT(θ,M~(Z))∣off] Reg_ UA,T(θ;D_ off):=E_Z[ Reg_T(θ; M(Z)) _ off]. This definition is consistent with the main paper. The existence of θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T is established in Proposition 5. Finally, note that the two relevant deployment regret terms in (9), RegT(θ^plug,T,M∗) Reg_T( θ_ plug,T;M^*) and RegT(θ^UA,T,M∗) Reg_T( θ_ UA,T;M^*), are random variables that depend on the offline data offD_ off for each T≥3T≥ 3. For notational simplicity, we make this dependence explicit and write rplug,T(off)=RegT(θ^plug,T,M∗),rUA,T(off)=RegT(θ^UA,T,M∗).r_ plug,T(D_ off)= Reg_T( θ_ plug,T;M^*), r_ UA,T(D_ off)= Reg_T( θ_ UA,T;M^*). Thus, G⁡(off)=lim infT→∞log⁡rplug,T(off)log⁡rUA,T(off)G(D_ off)= _T→∞ r_ plug,T(D_ off) r_ UA,T(D_ off) is also a random variable that depends on offD_ off. D.1 Main results and proofs In this section, we first establish the existence of θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T in Proposition 5. We then characterize the asymmetric regret landscape in Theorem 6, followed by an analysis of the θ selected by the Plug-In and UA approaches in Theorem 7. D.1.1 Existence of θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T Proposition 5. Consider the Gaussian environment M∗M^* defined in Section 3, and assume Toff≥4T_ off≥ 4. Then for almost every dataset offD_ off, the following holds for any finite horizon T: (i) θ↦RegT(θ,M^)θ Reg_T(θ; M) is continuous on Θ ; (i) θ↦RegUA,T(θ,off)θ Reg_ UA,T(θ;D_ off) is continuous on Θ . Consequently, both argmin sets in (27) and (28) are nonempty and compact. Proof of Proposition 5. Fix any offD_ off such that σ^12,σ^22>0 σ_1^2, σ_2^2>0 and μ^1≠μ^2 μ_1≠ μ_2. We will show (i) and (i) hold. We first prove a generic finite-horizon continuity statement. Fix a Gaussian environment ν with positive arm variances and distinct means. Place two independent infinite reward sequences on one probability space and use the same sequences to run UCB(θ)(θ) for every θ∈Θθ∈ . Fix θ0∈Θ _0∈ . We claim that the complete action sequence through any fixed time T is almost surely locally constant in θ at θ0 _0. The claim follows by induction over time. It is trivial for the two initialization pulls. Suppose the claim holds through time t−1t-1. Then with probability 1, the same reward observations, pull counts Ni(t−1,θ)N_i(t-1;θ), and empirical means μ^i(t−1,θ) μ_i(t-1;θ) used at time t are the same throughout a neighborhood of θ0 _0. Here Ni(t−1,θ)N_i(t-1;θ) denotes the number of pulls at arm i if we deploy UCB(θ)(θ) for t−1t-1 decision points, and μ^i(t−1,θ) μ_i(t-1;θ) denotes the mean reward of all the pulls at arm i if we deploy UCB(θ)(θ) for t−1t-1 decision points. At time t, the difference between the two UCB indices is Dt(θ) D_t(θ) :=U1(t,θ)−U2(t,θ) :=U_1(t;θ)-U_2(t;θ) =μ^1(t−1,θ)−μ^2(t−1,θ)+2θlog⁡t1N1(t−1,θ)−1N2(t−1,θ). = μ_1(t-1;θ)- μ_2(t-1;θ)+ 2θ t \ 1 N_1(t-1;θ)- 1 N_2(t-1;θ) \. Therefore, with probability 1, θ↦Dt(θ)θ D_t(θ) is continuous at θ0 _0. In addition, we also have ℙ⁡(Dt(θ0)=0)=0P(D_t( _0)=0)=0. This is because for each possible action sequence through time t−1t-1, the event that this action sequence occurs and Dt(θ0)=0D_t( _0)=0 is contained in an affine hyperplane of the finitely many Gaussian rewards revealed along that sequence. Since these rewards have a joint density, this event has probability zero. There are only finitely many possible action sequences through time t−1t-1, so taking their union still gives ℙ⁡(Dt(θ0)=0)=0P(D_t( _0)=0)=0. Combining the above arguments, we have that with probability 1, Dt(θ0)≠0D_t( _0)≠ 0, and θ↦Dt(θ)θ D_t(θ) is continuous at θ0 _0. Therefore, with probability 1, the sign of Dt(θ)D_t(θ) is unchanged in a small enough neighborhood of θ0 _0. This implies that with probability 1, UCB(θ)(θ) selects the same arm at time t as UCB(θ0)( _0) throughout that neighborhood. This completes the induction. It follows that Ns⁡(ν)(T,θ)→Ns⁡(ν)(T,θ0)almost surely as θ→θ0.N_s(ν)(T;θ)→ N_s(ν)(T; _0) surely as θ→ _0. The count is bounded by T, so dominated convergence gives continuity of θ↦RegT(θ,ν)θ Reg_T(θ;ν). Applying this result to ν=M^ν= M proves part (i). For part (i), conditional on offD_ off, the perturbed signed gap μ~1(Z1)−μ~2(Z2) μ_1(Z_1)- μ_2(Z_2) is a nondegenerate Gaussian random variable. Thus, it is nonzero for almost every Z, and for almost every Z, the preceding argument gives continuity of θ↦RegT(θ,M~(Z))θ Reg_T(θ; M(Z)). Moreover, 0≤RegT(θ,M~(Z))≤T|μ~1(Z1)−μ~2(Z2)|,0≤ Reg_T(θ; M(Z))≤ T\, | μ_1(Z_1)- μ_2(Z_2) |, (29) and the right-hand side is integrable with respect to Z. We can use the dominated convergence theorem to prove continuity of the averaged objective in (28). Finally, since Θ is compact, both objectives in (27) and (28) have nonempty compact argmin sets. ∎ D.1.2 Asymmetric regret of UCB Theorem 6 (Asymmetric regret of UCB). Consider the two-armed Gaussian bandit environment M∗=(⁡(μ1,σ2),⁡(μ2,σ2))M^*= (N( _1,σ^2),N( _2,σ^2) ), where μ1>μ2 _1> _2, σ2>0σ^2>0. For θ>0θ>0, let πθ _θ denote the policy induced by UCB(θ)(θ) in Alg. 1. Then the following hold for its expected regret: (i) For any θ∈(0,σ2)θ∈(0,σ^2), limT→∞log⁡RegT(πθ,M∗)log⁡T=1−θσ2. _T→∞ Reg_T( _θ,M^*) T=1- θσ^2. (i) For any θ≥σ2θ≥σ^2, limT→∞RegT(πθ,M∗)log⁡T=2θμ1−μ2. _T→∞ Reg_T( _θ,M^*) T= 2θ _1- _2. Thus, θ=σ2θ=σ^2 separates two asymptotic regimes: the expected regret grows polynomially in T for θ<σ2θ<σ^2 and logarithmically in T for θ≥σ2θ≥σ^2. Proof of Theorem 6. Apply Lemma 8 to the true environment M∗M^* with δ=μ1−μ2δ= _1- _2 and τo2=τs2=σ2 _o^2= _s^2=σ^2. For 0<θ<σ20<θ<σ^2, part (i) of the theorem follows from Lemma 8(v) by taking the constant sequence θT≡θ _T≡θ. For θ>σ2θ>σ^2, choose a compact interval K containing θ with inf>σ2 >σ^2. Lemma 8(i), together with RegT(θ,M∗)=δM∗[Ns(T,θ)] Reg_T(θ;M^*)= _M^*[N_s(T;θ)], gives the desired limit. The boundary case θ=σ2θ=σ^2 follows directly from Lemma 8(iv). ∎ D.1.3 Plug-In and UA selection for UCB Let a^:=arg⁡maxi∈1,2⁡μ^i a:= _i∈\1,2\ μ_i denote the optimal arm in the fitted environment obtained from offline data offD_ off. We prove the following stronger theorem. Theorem 7. For any Toff≥4T_ off≥ 4, on the probability-one event ℛToff:=σ^12>0,σ^22>0,μ^1≠μ^2,σ^i2∉θ¯,σ2,θ¯ for i=1,2,R_T_ off:= \ array[]l σ_1^2>0, σ_2^2>0, μ_1≠ μ_2,\\[2.0pt] σ_i^2∉\ θ,σ^2, θ\ for i=1,2 array \, (30) the following statements hold for the Plug-In and UA selection of the UCB algorithm: (i) As T→∞T→∞, θ^plug,T→cplug(off):=ΠΘ(σ^a^2),lim infT→∞θ^UA,T≥cUA(off):=ΠΘ(σ^12∨σ^22). θ_ plug,T→ c_ plug(D_ off):= _ ( σ_ a^2), _T→∞ θ_ UA,T≥ c_ UA(D_ off):= _ ( σ_1^2 σ_2^2). (31) (i) The Plug-In conditional regret satisfies limT→∞log⁡(rplug,T(off))log⁡T=(1−cplug(Doff)σ2)+, _T→∞ (r_ plug,T(D_ off) ) T= (1- c_ plug(D off)σ^2 )_+, (32) and the Uncertainty-Aware conditional regret satisfies lim supT→∞log⁡(rUA,T(off))log⁡T≤(1−cUA(off)σ2)+≤(1−cplug(off)σ2)+. _T→∞ (r_ UA,T(D_ off) ) T≤ (1- c_ UA(D_ off)σ^2 )_+≤ (1- c_ plug(D_ off)σ^2 )_+. (33) (i) G⁡(off)≥1G(D_ off)≥ 1. In addition, define the event Toff:=σ^a^2<σ2<σ^3−a^2∩ℛToffA_T_ off:= \ σ_ a^2<σ^2< σ_3- a^2 \ _T_ off. Then limToff→∞ℙ⁡(Toff)=14 _T_ off→∞P(A_T_ off)= 14, and on ToffA_T_ off, G⁡(off)=+∞G(D_ off)=+∞. Proof of Theorem 7. For part (i), first apply Lemma 9 to the fitted environment M M. Its optimal arm is a a, and the optimal-arm variance is σ^a^2 σ_ a^2. Also, the regularity event excludes equality with the endpoints of Θ , so θ^plug,T→ΠΘ(σ^a^2)=cplug(off). θ_ plug,T→ _ ( σ_ a^2)=c_ plug(D_ off). The UA liminf part follows from Lemma 10. For (32) in part (i), we deploy the selected sequence θ^plug,T θ_ plug,T in the true environment M∗M^*. Its optimal-arm variance is σ2σ^2, and the selected sequence converges to cplug(off)c_ plug(D_ off). Lemma 8(v) then leads to (32). For (33), fix ε>0 >0. By part (i), for sufficiently large T, θ^UA,T≥cUA(off)−ε θ_ UA,T≥ c_ UA(D_ off)- . Apply Lemma 8(i) uniformly over all θ¯≥θ≥cUA(off)−ε θ≥θ≥ c_ UA(D_ off)- , we deduce that lim supT→∞log⁡(rUA,T(off))log⁡T≤(1−cUA(off)−εσ2)+. _T→∞ (r_ UA,T(D_ off) ) T≤ (1- c_ UA(D_ off)- σ^2 )_+. Let ε↓0 0, and since cUA(off)≥cplug(off)c_ UA(D_ off)≥ c_ plug(D_ off), (33) follows. For part (i), first apply Lemma 8(i) in the true environment uniformly over θ∈Θθ∈ gives a constant c⁡(off)>0c(D_ off)>0 such that rplug,T(off)∧rUA,T(off)≥c⁡(off)log⁡Tr_ plug,T(D_ off) r_ UA,T(D_ off)≥ c(D_ off) T (34) for all sufficiently large T. If cplug(off)>σ2c_ plug(D_ off)>σ^2, then cUA(off)≥cplug(off)>σ2c_ UA(D_ off)≥ c_ plug(D_ off)>σ^2. Then (i) implies that both selected sequences have a fixed positive distance above σ2σ^2 for all large T. Lemma 8(i) and (34), yields rplug,T(off)=Θ⁡(log⁡T),rUA,T(off)=Θ⁡(log⁡T).r_ plug,T(D_ off)= ( T), r_ UA,T(D_ off)= ( T). In this case, G⁡(off)=1G(D_ off)=1. If cplug(off)<σ2c_ plug(D_ off)<σ^2, set q=1−cplug(off)/σ2>0q=1-c_ plug(D_ off)/σ^2>0. By (32), log⁡(rplug,T(off)) (r_ plug,T(D_ off)) is qlog⁡T+o⁡(log⁡T)q T+o( T). By (33), lim supT→∞log⁡rUA,T(off)log⁡T≤q _T→∞ r_ UA,T(D_ off) T≤ q. Together with (34), this implies lim infT→∞log⁡rplug,T(off)log⁡rUA,T(off)≥1 _T→∞ r_ plug,T(D_ off) r_ UA,T(D_ off)≥ 1. The remaining equality case cplug(off)=σ2c_ plug(D_ off)=σ^2 is excluded by ℛToffR_T_ off. This proves (i). Finally, we analyze the event ToffA_T_ off. Note that for Gaussian data, the sample means are independent of the sample variances. Thus, a a is independent of (σ^12,σ^22)( σ_1^2, σ_2^2). In addition, the two sample variances are i.i.d., and (T1,off−1)σ^i2σ2∼χT1,off−12 (T_1, off-1) σ_i^2σ^2 χ^2_T_1, off-1. Therefore, condition on either value of a a, the probability that the fitted optimal arm has variance below σ2σ^2 and the other arm has variance above σ2σ^2 is qToff(1−qToff)q_T_ off(1-q_T_ off), where qToff:=ℙ⁡(χT1,off−12<T1,off−1)q_T_ off:=P(χ^2_T_1, off-1<T_1, off-1). This leads to ℙ⁡(Toff)=qToff(1−qToff)P(A_T_ off)=q_T_ off(1-q_T_ off). Moreover, according to the Central Limit Theorem, limToff→∞qToff=1/2 _T_ off→∞q_T_ off=1/2. Thus, ℙ⁡(Toff)→1/4P(A_T_ off)→ 1/4. On ToffA_T_ off, the fitted optimal arm has sample variance below σ2σ^2, and the other arm has sample variance above σ2σ^2. Since θ¯<σ2<θ¯ θ<σ^2< θ, cplug(off)<σ2<cUA(off).c_ plug(D_ off)<σ^2<c_ UA(D_ off). From the previous analysis we obtain that on ToffA_T_ off, rplug,T(off) r_ plug,T(D_ off) =T 1−cplug(off)/σ2+o⁡(1), =T^\,1-c_ plug(D_ off)/σ^2+o(1), rUA,T(off) r_ UA,T(D_ off) =O⁡(log⁡T), =O( T), and hence rplug,T(off)rUA,T(off)→∞,G⁡(off)=∞. r_ plug,T(D_ off)r_ UA,T(D_ off)→∞, G(D_ off)=∞. ∎ D.2 Auxiliary lemmas Lemma 8 (Fixed-environment UCB regret). Consider a 2-arm bandit environment νδ=(⁡(μo,τo2),⁡(μs,τs2)) _δ= (N( _o, _o^2),N( _s, _s^2) ), where μo=μs+δ _o= _s+δ with δ>0δ>0. Let =[θ−,θ+]⊂(0,∞)K=[ _-, _+]⊂(0,∞). Then the following holds for the regret of UCB(θ)(θ) and the arm pull counts in environment νδ _δ: (i) There is a finite constant C, depending only on θ−,θ+,τo2,τs2 _-, _+, _o^2, _s^2, such that for all T≥3T≥ 3, θ∈θ , and δ>0δ>0: RegT(θ;νδ)≤C[δ+log⁡Tδ+1δ(1+∑t=3Tt−θ/τo2)]. Reg_T(θ; _δ)≤ C [δ+ Tδ+ 1δ (1+ _t=3^Tt^-θ/ _o^2 ) ]. (35) (i) Fix 0<δ−≤δ+<∞0< _-≤ _+<∞ and suppose θ+<τo2 _+< _o^2. For every η>0η>0, there is T0<∞T_0<∞ such that, for all T≥T0T≥ T_0, infδ∈[δ−,δ+]θ∈RegT(θ,νδ)≥δ−4T 1−θ+/τo2−η. _ subarraycδ∈[ _-, _+]\\ θ subarray Reg_T(θ; _δ)≥ _-4T^\,1- _+/ _o^2-η. (36) (i) For every fixed δ>0δ>0, lim infT→∞infθ∈δ2νδ[Ns(T,θ)]2θlog⁡T≥1. _T→∞ _θ δ^2E_ _δ[N_s(T;θ)]2θ T≥ 1. (37) If, in addition, θ−≥(1+ξ)τo2 _-≥(1+ξ) _o^2 for some ξ>0ξ>0, then limT→∞supθ∈|δ2νδ[Ns(T,θ)]2θlog⁡T−1|=0. _T→∞ _θ | δ^2E_ _δ[N_s(T;θ)]2θ T-1 |=0. (38) (iv) For every fixed δ>0δ>0, when θ=τo2θ= _o^2, limT→∞RegT⁡(θ;νδ)log⁡T=2θδ. _T→∞ Reg_T(θ; _δ) T= 2θδ. (39) (v) If θT∈ _T and θT→θ _T→θ, then limT→∞log⁡(RegT(θT,νδ))log⁡T=(1−θτo2)+. _T→∞ ( Reg_T( _T; _δ) ) T= (1- θ _o^2 )_+. (40) Proof of Lemma 8. Without loss of generality, we assume that any UCB algorithm is deployed by placing the two independent reward sequences on a common probability space and revealing the reward Yi,tY_i,t when arm i is selected for the ttth time. If UCB⁡(θ)UCB(θ) is deployed, let the arm means and pull counts be Ni(t;θ):=∑r=1tAr(θ)=i,Y¯i,n:=1n∑s=1nYi,s,μ^i(t;θ):=Y¯i,Ni(t,θ).N_i(t;θ):= _r=1^t \A_r(θ)=i\, Y_i,n:= 1n _s=1^nY_i,s, μ_i(t;θ):= Y_i,N_i(t;θ). Part (i). We establish this part using a pull-count decomposition similar to that in Auer et al. (2002); Fan and Glynn (2022), combined with Gaussian concentration bounds. Fix θ∈θ and let mT(θ,δ):=⌈8θlog⁡Tδ2⌉m_T(θ,δ):= 8θ Tδ^2 . For t≥3t≥ 3, define Bt(θ):=Uo(t;θ)<μo−δ4,B_t(θ):= \U_o(t;θ)< _o- δ4 \, where Ui(t,θ)=μ^i(t−1,θ)+2θlog⁡tNi(t−1,θ)U_i(t;θ)= μ_i(t-1;θ)+ 2θ tN_i(t-1;θ) is the UCB index of arm i at time t. If for m∈ℕm , No(t−1,θ)=mN_o(t-1;θ)=m and Bt(θ)B_t(θ) occurs, then Y¯o,m−μo<−δ4−2θlog⁡tm Y_o,m- _o<- δ4- 2θ tm. Gaussian concentration and a union bound over m give ℙ(Bt(θ)) P(B_t(θ)) ≤∑m=1t−1exp⁡−m2τo2(δ4+2θlog⁡tm)2 ≤ _m=1^t-1 \- m2 _o^2 ( δ4+ 2θ tm )^2 \ ≤t−θ/τo2∑m=1∞exp−mδ232τo2 ≤ t^-θ/ _o^2 _m=1^∞ \- mδ^232 _o^2 \ ≤C1τo2δ−2t−θ/τo2. ≤ C_1 _o^2δ^-2t^-θ/ _o^2. (41) Here C1C_1 is a universal constant. Here we use the fact that ex−1≥xe^x-1≥ x for x≥0x≥ 0. Suppose that arm s is selected at time t, Bt(θ)B_t(θ) does not occur, and Ns(t−1,θ)=k≥mT(θ,δ)N_s(t-1;θ)=k≥ m_T(θ,δ). Then Us(t,θ)≥Uo(t,θ)≥μo−δ4U_s(t;θ)≥ U_o(t;θ)≥ _o- δ4, and 2θlog⁡tk≤2θlog⁡TmT(θ,δ)≤δ2 2θ tk≤ 2θ Tm_T(θ,δ)≤ δ2. Thus we deduce that Y¯s,k−μs≥δ/4 Y_s,k- _s≥δ/4. Each pre-pull count k is encountered at most once, so Ns(T,θ) N_s(T;θ) ≤mT(θ,δ)+1+∑t=3TBt(θ)+∑k=mT(θ,δ)∞Y¯s,k−μs≥δ4. ≤ m_T(θ,δ)+1+ _t=3^T \B_t(θ)\+ _k=m_T(θ,δ)^∞ \ Y_s,k- _s≥ δ4 \. (42) The final sum has expectation at most ∑k=mT(θ,δ)∞exp⁡−kδ232τs2≤11−exp⁡−δ232τs2≤1+32τs2δ2. _k=m_T(θ,δ)^∞ \- kδ^232 _s^2 \≤ 11- \- δ^232 _s^2 \≤ 1+ 32 _s^2δ^2. Taking expectations in (42), using (41), and multiplying by δ proves (35). If mT(θ,δ)>Tm_T(θ,δ)>T, the trivial bound RegT(θ,νδ)≤Tδ Reg_T(θ; _δ)≤ Tδ is already bounded by a constant multiple of δ+(log⁡T)/δ+( T)/δ, so the same conclusion holds. Part (i). Choose G>0G>0 large enough such that ∑k=1∞exp⁡−kG22τs2≤12 _k=1^∞ \- kG^22 _s^2 \≤ 12. Let F:=Y¯s,k>μs−G for every k≥1.F:= \ Y_s,k> _s-G for every k≥ 1 \. Then a union bound implies ℙ⁡(F)≥1/2P(F)≥ 1/2. Moreover, define ET:=Yo,1≤μs−G−2θ+log⁡T.E_T:= \Y_o,1≤ _s-G- 2 _+ T \. (43) On ET∩FE_T∩ F, after the two initialization pulls, the optimal arm has index at most μs−G _s-G at every t≤Tt≤ T as long as it is not selected again. The suboptimal arm has index strictly larger than μs−G _s-G at every time by the definition of F. Thus, we can use induction to show that the suboptimal arm is selected at every time 3,…,T3,…,T, so Ns(T,θ)=T−1N_s(T;θ)=T-1 simultaneously for every θ∈θ . Now for any η>0η>0, uniformly over δ∈[δ−,δ+]δ∈[ _-, _+], ℙ(ET)=Φ(−δ+G+2θ+log⁡Tτo)≥T−θ+/τo2−ηP(E_T)= (- δ+G+ 2 _+ T _o )≥ T^- _+/ _o^2-η for all sufficiently large T. Here Φ is the CDF of a standard normal distribution. The above inequality follows directly from the standard property of Gaussian distribution: ∀x>0∀ x>0, Φ(−x)≥x1+x2⋅12πexp(−x2/2) (-x)≥ x1+x^2· 1 2π (-x^2/2), combined with the fact that e−O⁡(log⁡T)=T−o⁡(1)e^-O( T)=T^-o(1). In addition, the events ETE_T and F involve different armwise reward sequences and are independent. Therefore, RegT(θ,νδ)≥δ−(T−1)ℙ(ET)ℙ(F)≥δ−4T1−θ+/τo2−η Reg_T(θ; _δ)≥ _-(T-1)P(E_T)P(F)≥ _-4T^1- _+/ _o^2-η for all large T, which proves (36). Part (i). We first prove (37). Fix ρ∈(0,1)ρ∈(0,1) and define mmax(T):=⌈2θ+(1−ρ)log⁡Tδ2⌉=o⁡(T)m_ (T):= 2 _+(1-ρ) Tδ^2 =o(T). Choose small constants ζ,ϵ>0ζ,ε>0 such that b:=1−ζ−(1+2ϵ)1−ρ>0b:= 1-ζ-(1+2ε) 1-ρ>0. Next, set ℓ0(T)=T−2mmax(T)−1 _0(T)=T-2m_ (T)-1 and define Go,T G_o,T :=⋂ℓ=ℓ0(T)TY¯o,ℓ−μo≤ϵδ, := _ = _0(T)^T \ Y_o, - _o≤εδ \, Gs,T G_s,T :=⋂k=1mmax(T)∑j=1k(Ys,j−μs)>−b2θ−klog⁡T. := _k=1^m_ (T) \ _j=1^k(Y_s,j- _s)>-b 2 _-k T \. A Gaussian union bound gives ℙ⁡(Go,Tc) P(G_o,T^c) ≤∑ℓ=ℓ0(T)Texp⁡−ℓϵ2δ22τo2 ≤ _ = _0(T)^T \- ε^2δ^22 _o^2 \ ≤(2mmax(T)+2)⋅exp⁡−ℓ0(T)ϵ2δ22τo2→0 ≤(2m_ (T)+2)· \- _0(T)ε^2δ^22 _o^2 \→ 0 as T→∞T→∞. Also, for every k≤mmax(T)k≤ m_ (T), ℙ(∑j=1k(Ys,j−μs)≤−b2θ−klog⁡T)≤T−b2θ−/τs2,P ( _j=1^k(Y_s,j- _s)≤-b 2 _-k T )≤ T^-b^2 _-/ _s^2, where we use the fact that for x≥0x≥ 0, Φ(−x)≤exp(−x2/2) (-x)≤ (-x^2/2). Therefore, as T→∞T→∞, ℙ(Gs,Tc)≤mmax(T)T−b2θ−/τs2→0.P(G_s,T^c)≤ m_ (T)T^-b^2 _-/ _s^2→ 0. Also, supt≤T,ℓ≥ℓ0(T),θ∈2θlog⁡tℓ≤ϵδ _t≤ T, ≥ _0(T),θ 2θ t ≤εδ for all sufficiently large T. We now show that on Go,T∩Gs,TG_o,T∩ G_s,T, Ns(T,θ)≥m−(θ,T):=⌊2θ(1−ρ)log⁡Tδ2⌋N_s(T;θ)≥ m_-(θ,T):= 2θ(1-ρ) Tδ^2 for every θ∈θ . Suppose otherwise. Let r be the last time the optimal arm is selected. Since fewer than mmax(T)m_ (T) suboptimal pulls occur, r≥T−mmax(T)r≥ T-m_ (T), and the optimal-arm pre-pull count at time r is at least ℓ0(T) _0(T). Hence Uo(r,θ)≤μo+2ϵδ.U_o(r;θ)≤ _o+2εδ. Writing k=Ns(r−1,θ)<m−(θ,T)k=N_s(r-1;θ)<m_-(θ,T) and using log⁡r≥(1−ζ)log⁡T r≥(1-ζ) T for all large T, we obtain 2θklog⁡r−(1+2ϵ)δk 2θ k r-(1+2ε)δ k ≥ ≥ 2θklog⁡T[1−ζ−(1+2ϵ)δ2k2θlog⁡T] 2θ k T [ 1-ζ-(1+2ε) δ^2k2θ T ] ≥ ≥ b2θklog⁡T≥b2θ−klog⁡T. b 2θ k T≥ b 2 _-k T. On Gs,TG_s,T this implies Us(r,θ)=Y¯s,k+2θlog⁡rk>μs+(1+2ϵ)δ=μo+2ϵδ≥Uo(r,θ),U_s(r;θ)= Y_s,k+ 2θ rk> _s+(1+2ε)δ= _o+2εδ≥ U_o(r;θ), contradicting selection of the optimal arm at time r. Combining the above, we deduce that limT→∞infθ∈ℙ⁡(Ns(T,θ)≥m−(θ,T))=1 _T→∞ _θ P(N_s(T;θ)≥ m_-(θ,T))=1, and thus lim infT→∞infθ∈δ2νδ[Ns(T,θ)]2θlog⁡T≥1−ρ. _T→∞ _θ δ^2E_ _δ[N_s(T;θ)]2θ T≥ 1-ρ. Letting ρ↓0ρ 0 proves (37). We now prove a corresponding upper bound. Assume θ−≥(1+ξ)τo2θ_-≥(1+ξ) _o^2. Fix ρ′∈(0,1)ρ ∈(0,1) and define ϵ′:=13(1−11+ρ′)ε := 13(1- 1 1+ρ ), m+(θ,T):=⌈2θ(1+ρ′)log⁡Tδ2⌉m_+(θ,T):= 2θ(1+ρ ) Tδ^2 . Define Bt′(θ)=Uo(t;θ)<μo−ϵ′δB_t (θ)=\U_o(t;θ)< _o-ε δ\. Using the same analysis as in (41), ℙ(Bt′(θ))≤2τo2ϵ′2δ2t−θ/τo2≤2τo2ϵ′2δ2t−(1+ξ)P(B_t (θ))≤ 2 _o^2ε 2δ^2t^-θ/ _o^2≤ 2 _o^2ε 2δ^2t^-(1+ξ) uniformly over θ∈θ , so the sum over t is uniformly bounded. Now suppose arm s is selected at time t with pre-pull count Ns(t−1,θ)=k≥m+(θ,T)N_s(t-1;θ)=k≥ m_+(θ,T) and Bt′(θ)B_t (θ) does not occur, then Y¯s,k−μs≥2ϵ′δ Y_s,k- _s≥ 2ε δ. Similar to (42) we have Ns(T;θ)≤m+(θ,T)+1+∑t=3TBt′(θ)+∑k=m+(θ,T)∞Y¯s,k−μs≥2ϵ′δ. N_s(T;θ)≤ m_+(θ,T)+1+ _t=3^T \B_t (θ)\+ _k=m_+(θ,T)^∞ \ Y_s,k- _s≥ 2ε δ\. (44) Taking expectations and by controlling the Gaussian tail bound, we deduce that ⁡[Ns(T,θ)]≤2+2θ(1+ρ′)log⁡Tδ2+C,E[N_s(T;θ)]≤ 2+ 2θ(1+ρ ) Tδ^2+C, ∀θ∈∀θ . Here the constant C depends only on ξ, ρ′ρ , δ, τo2 _o^2 and τs2 _s^2. Combining this upper bound with (37) and then letting ρ′↓0ρ 0 proves (38). Part (iv). Fix δ>0δ>0 and assume θ=τo2θ= _o^2. LHS≥ in (39) follows from part (i), applied to a compact interval containing τo2 _o^2. To prove LHS≤ in (39), fix ρ′∈(0,1)ρ ∈(0,1) and use the same definitions of ϵ′ε , m+(θ,T)m_+(θ,T), and Bt′(θ)B _t(θ) as in the proof of part (i). For every t≥3t≥ 3, we have ℙνδ(Bt′(θ)) _ _δ (B _t(θ) ) ≤∑m=1t−1exp⁡−m2τo2(ϵ′δ+2θlog⁡tm)2 ≤ _m=1^t-1 \- m2 _o^2 (ε δ+ 2θ tm )^2 \ =t−1∑m=1t−1exp⁡−m(ϵ′δ)22τo2−2ϵ′δτomlog⁡t =t^-1 _m=1^t-1 \- m(ε δ)^22 _o^2- 2ε δ _o m t \ ≤C1t−1exp⁡−c2log⁡t, ≤ C_1t^-1 \-c_2 t\, where C1:=∑m=1∞exp⁡−m(ϵ′δ)22τo2<∞C_1:= _m=1^∞ \- m(ε δ)^22 _o^2 \<∞, c2:=2ϵ′δτo>0c_2:= 2ε δ _o>0. As ∫e∞exp⁡−c2log⁡xxx=2∫1∞ue−c2uu<∞ _e^∞ \-c_2 x\x\,dx=2 _1^∞ue^-c_2u\,du<∞, we can deduce that ∑t=3∞ℙνδ(Bt′(θ))<∞. _t=3^∞P_ _δ (B _t(θ) )<∞. Now we use the counting decomposition (44) with θ=τo2θ= _o^2. Taking expectations and applying the same suboptimal-arm Gaussian deviation bound to the last term leads to νδ[Ns(T,θ)] _ _δ[N_s(T;θ)] ≤m+(θ,T)+1+∑t=3∞ℙνδ(Bt′(θ))+∑k=1∞exp⁡−2k(ϵ′δ)2τs2 ≤ m_+(θ,T)+1+ _t=3^∞P_ _δ (B _t(θ) )+ _k=1^∞ \- 2k(ε δ)^2 _s^2 \ =2θ(1+ρ′)log⁡Tδ2+O⁡(1), = 2θ(1+ρ ) Tδ^2+O(1), where the O⁡(1)O(1) term may depend on ρ′ρ , δ, τo2 _o^2, and τs2 _s^2, but not on T. Dividing by log⁡T T, letting T→∞T→∞, and then letting ρ′↓0ρ 0 yields lim supT→∞νδ[Ns(T,θ)]log⁡T≤2θδ2. _T→∞ E_ _δ[N_s(T;θ)] T≤ 2θδ^2. Finally, we obtain part (iv) by combining the above analysis and using the fact that RegT(θ,νδ)=δνδ[Ns(T,θ)] Reg_T(θ; _δ)= _ _δ[N_s(T;θ)]. Part (v). If θ<τo2θ< _o^2, choose ε>0 >0 sufficiently small that θ+ε<τo2θ+ < _o^2. For large enough T, eventually θT∈[θ−ε,θ+ε]θ_T∈[θ- ,θ+ ]. Part (i), followed by η↓0η 0 and then ε↓0 0, gives lim infT→∞log⁡RegT(θT,νδ)log⁡T≥1−θτo2 _T→∞ Reg_T(θ_T; _δ) T≥ 1- θ _o^2. On the other hand, Part (i) and θT→θ_T→θ gives lim supT→∞log⁡RegT(θT,νδ)log⁡T≤1−θτo2 _T→∞ Reg_T(θ_T; _δ) T≤ 1- θ _o^2. If θ≥τo2θ≥ _o^2, part (i) gives lim supT→∞log⁡RegT(θT,νδ)log⁡T≤0 _T→∞ Reg_T(θ_T; _δ) T≤ 0, while nonnegativity gives the reverse inequality. This proves (40). ∎ Lemma 9 (Limit of the Plug-In minimizer). Let ν be a fixed two-armed Gaussian environment with distinct means and positive variances. Let τo2 _o^2 denote the variance of its optimal arm and assume τo2∉θ¯,θ¯ _o^2∉\ θ, θ\. For each T, let θT(ν)∈argminθ∈Θ⁡RegT(θ,ν) _T(ν)∈ _θ∈ Reg_T(θ;ν). Then limT→∞θT(ν)=ΠΘ(τo2). _T→∞ _T(ν)= _ ( _o^2). (45) Proof of Lemma 9. For simplicity, write θT=θT(ν)θ_T=θ_T(ν) and c=ΠΘ(τo2)c= _ ( _o^2). If τo2<θ¯ _o^2< θ, by Lemma 8(i), for every fixed ε>0 >0, infθ∈[θ¯+ε,θ¯]RegT(θ,ν)>RegT(θ¯,ν) _θ∈[ θ+ , θ] Reg_T(θ;ν)> Reg_T( θ;ν) for all sufficiently large T, because the leading term is proportional to θlog⁡Tθ T. Hence θT<θ¯+εθ_T< θ+ eventually. Thus θT→θ¯=cθ_T→ θ=c. Suppose τo2∈(θ¯,θ¯) _o^2∈( θ, θ). Fix a sufficiently small ε>0 >0. For θ≤τo2−εθ≤ _o^2- , Lemma 8(i) gives a positive polynomial lower bound, whereas θ0=τo2+ε/2θ_0= _o^2+ /2 has logarithmic regret by Lemma 8(i). Thus for sufficiently large T, θT>τo2−εθ_T> _o^2- . On the other hand, Lemma 8(i) implies infθ∈[τo2+ε,θ¯]RegT(θ,ν)>RegT(θ0,ν) _θ∈[ _o^2+ , θ] Reg_T(θ;ν)> Reg_T(θ_0;ν) for sufficiently large T. Thus, θT<τo2+εθ_T< _o^2+ for sufficiently large T. Letting ε↓0 0 proves convergence to c=τo2c= _o^2. Finally, suppose τo2>θ¯ _o^2> θ. Fix ε>0 >0. By the uniform lower bound in Lemma 8(i), every θ≤θ¯−εθ≤ θ- has regret exponent at least 1−(θ¯−ε)/τo21-( θ- )/ _o^2, whereas the upper envelope in Lemma 8(i) shows that θ¯ θ has exponent at most 1−θ¯/τo21- θ/ _o^2. The former exponent is strictly larger, so θT>θ¯−εθ_T> θ- eventually. Hence θT→θ¯=cθ_T→ θ=c as T→∞T→∞. ∎ Lemma 10 (Limit of the Gaussian-perturbed minimizer). Fix any offline data offD_ off such that σ^12,σ^22>0 σ_1^2, σ_2^2>0. Define σ¯2:=σ^12∨σ^22 σ^2:= σ_1^2 σ_2^2. If θT∈Θ _T∈ and θT→θ _T→θ, then limT→∞log⁡(RegUA,T(θT,off))log⁡T=(1−θσ¯2)+. _T→∞ ( Reg_ UA,T( _T;D_ off) ) T= (1- θ σ^2 )_+. (46) As a result, every sequence of minimizers in (28) satisfies lim infT→∞θ^UA,T≥ΠΘ(σ¯2). _T→∞ θ_ UA,T≥ _ ( σ^2). (47) Proof of Lemma 10. Let X:=|μ~1(Z1)−μ~2(Z2)|X:= | μ_1(Z_1)- μ_2(Z_2) |. Conditional on offD_ off, X has a folded-normal distribution. Its density on (0,∞)(0,∞) is bounded, and ⁡[X]<∞E[X]<∞. For every perturbed environment, the variance of its optimal arm is at most σ¯2 σ^2. Applying Lemma 8 gives RegT(θT,M~(Z))≤C⁡[X+BTX], Reg_T( _T; M(Z))≤ C [X+ B_TX ], (48) where BT:=TqT(1+log⁡T)B_T:=T^q_T(1+ T), qT=(1−θT/σ¯2)+q_T=(1-θ_T/ σ^2)_+; the constant C depends on offD_ off and Θ , but not on T or Z. We also have the trivial bound RegT≤TX Reg_T≤ TX. Let xT=(BT/T)1/2x_T=(B_T/T)^1/2. Since θ¯>0 θ>0, qTq_T is bounded strictly below one for all sufficiently large T, and hence xT→0x_T→ 0. Denote fXf_X as the density of X, then ‖fX‖∞<∞\|f_X\|_∞<∞, and [TXX≤xT] [TX \X≤ x_T\] ≤12‖fX‖∞TxT2=O⁡(BT), ≤ 12\|f_X\|_∞Tx_T^2=O(B_T), [BTXxT<X≤1] [ B_TX \x_T<X≤ 1\ ] ≤‖fX‖∞BTlog⁡(1/xT)=O⁡(BTlog⁡T), ≤\|f_X\|_∞B_T (1/x_T)=O(B_T T), [BTXX>1] [ B_TX \X>1\ ] =O⁡(BT). =O(B_T). Combining these bounds with (48) yields RegUA,T(θT,off)≤C′TqT(1+log⁡T)2. Reg_ UA,T(θ_T;D_ off)≤ C T^q_T(1+ T)^2. (49) Since qT→(1−θ/σ¯2)+q_T→(1-θ/ σ^2)_+, this proves that LHS≤ in (46). Below we prove the reverse direction LHS≥ . The case θ≥σ¯2θ≥ σ^2 is immediate from nonnegativity. Now suppose θ<σ¯2θ< σ^2, and let h be an arm with σ^h2=σ¯2 σ_h^2= σ^2. The signed perturbed gap μ~h(Zh)−μ~3−h(Z3−h) μ_h(Z_h)- μ_3-h(Z_3-h) is a nondegenerate Gaussian random variable. Thus, there exist constants 0<g−<g+<∞0<g_-<g_+<∞ such that the event :=g−≤μ~h(Zh)−μ~3−h(Z3−h)≤g+W:= \g_-≤ μ_h(Z_h)- μ_3-h(Z_3-h)≤ g_+ \ (50) has conditional probability w⁡(off)>0w(D_ off)>0 condition on offD_ off. On this event, arm h is optimal, its variance is σ¯2 σ^2, and the gap lies in [g−,g+][g_-,g_+]. Fix ε,η>0 ,η>0 small enough such that θ+ε<σ¯2θ+ < σ^2. Eventually θT≤θ+εθ_T≤θ+ . Lemma 8(i), applied uniformly on W, gives RegUA,T(θT,off)≥w⁡(off)cT1−(θ+ε)/σ¯2−η Reg_ UA,T(θ_T;D_ off)≥ w(D_ off)cT^1-(θ+ )/ σ^2-η for all sufficiently large T. Letting ε,η↓0 ,η 0 proves the desired inequality. Finally we prove (47). Let c=ΠΘ(σ¯2)c= _ ( σ^2). Suppose otherwise. Then there exists a subsequence of UA minimizers with a limit θ<cθ<c. If σ¯2∈(θ¯,θ¯) σ^2∈( θ, θ), choose a comparator θ′∈(σ¯2,θ¯]θ ∈( σ^2, θ]. By (46), the minimizers along the subsequence have a strictly positive objective exponent, while the comparator has exponent zero, contradicting optimality. If σ¯2≥θ¯ σ^2≥ θ, use the comparator θ′=θ¯θ = θ; then 1−θσ¯2>1−θ¯σ¯21- θ σ^2>1- θ σ^2, again contradicting optimality. If σ¯2≤θ¯ σ^2≤ θ, then c=θ¯c= θ and no θ∈Θθ∈ can be smaller than c. Therefore, no limit lies below c. ∎ Appendix E Theoretical analysis of the Thompson Sampling algorithm In this section, we provide a detailed theoretical analysis of the behavior and selection performance of the Thompson Sampling (TS) algorithm in a two-armed Gaussian bandit. More specifically, we consider the standard Gaussian TS algorithm with an improper flat prior on each arm mean (Russo et al., 2018): The agent keeps a working reward model for each arm i∈1,2i∈\1,2\ as Y|μi∼⁡(μi,θ),Y| _i ( _i,θ), with a flat prior πi(μi)∝1 _i( _i) 1. At each round t, let Ni(t−1,θ)N_i(t-1;θ) and μ^i(t−1,θ) μ_i(t-1;θ) denote the number of pulls and the empirical mean reward for arm i prior to time t under the current algorithm. Then the posterior for μi _i equals μi|ℋt−1∼⁡(μ^i(t−1,θ),θNi(t−1,θ)). _i|H_t-1 ( μ_i(t-1;θ), θN_i(t-1;θ) ). After each arm is pulled once, at each round t, for each arm i∈1,2i∈\1,2\, the agent independently samples a posterior draw Ξi(t,θ)=μ^i(t−1,θ)+θNi(t−1,θ)Zi,t,Z1,t,Z2,t∼iid⁡(0,1), _i(t,θ)= μ_i(t-1;θ)+ θN_i(t-1;θ)Z_i,t, Z_1,t,Z_2,t N(0,1), and then selects At(θ)∈argmaxi∈1,2⁡Ξi(t,θ).A_t(θ)∈ _i∈\1,2\ _i(t;θ). See Alg. 2. Below, we refer to this algorithm as TS(θ)(θ), where the tuning parameter θ represents the working reward variance. Algorithm 2 TS(θ)(θ) 1: Pull each arm once. 2: for t=3,…,Tt=3,…,T do 3: For i∈1,2i∈\1,2\, compute Ni(t−1,θ)N_i(t-1;θ) and μ^i(t−1,θ) μ_i(t-1;θ), the number of pulls and empirical mean reward for arm i up to time t−1t-1. 4: Independently draw Zi,t∼⁡(0,1)Z_i,t (0,1) for each i∈1,2i∈\1,2\ and compute Ξi(t,θ)=μ^i(t−1,θ)+θNi(t−1,θ)Zi,t. _i(t;θ)= μ_i(t-1;θ)+ θN_i(t-1;θ)Z_i,t. 5: Pull At=At(θ)∈arg⁡maxi∈1,2Ξi(t,θ)A_t=A_t(θ)∈ _i∈\1,2\ _i(t;θ). 6: end for Notation. We use the notation introduced in Appendix D whenever it is algorithm-independent. In particular, ΠV _V, σ⁡(X)σ(X), Φ , ϕφ, a+a_+, and, for a generic two-armed Gaussian environment ν, o⁡(ν)o(ν), s⁡(ν)s(ν), and δ⁡(ν)δ(ν) have the same meanings as in Appendix D. In addition, for x∈ℝx , we define the Gaussian odds function H⁡(x):=Φ⁡(−x)Φ⁡(x)H(x):= (-x) (x). Throughout this section, however, πθ _θ denotes the policy induced by TS(θ)(θ) in Alg. 2, and Ni(T,θ)N_i(T;θ) denotes the number of times arm i is selected over T rounds under TS(θ)(θ) instead of UCB(θ)(θ). For a generic two-armed Gaussian environment ν with distinct arm means, we write RegT(θ,ν):=RegT(πθ,ν)=δ⁡(ν)ν[Ns⁡(ν)(T,θ)], Reg_T(θ;ν):= Reg_T( _θ,ν)=δ(ν)E_ν [N_s(ν)(T;θ) ], and when the two arm means are equal, we define RegT(θ,ν)=0 Reg_T(θ;ν)=0. We define the Plug-In and Uncertainty-Aware (UA) selection rules, θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T, as in (27)-(28), with RegT(θ,ν) Reg_T(θ;ν) now referring to the regret of TS(θ)(θ). The corresponding quantities RegUA,T(θ,off) Reg_ UA,T(θ;D_ off), rplug,T(off)r_ plug,T(D_ off), rUA,T(off)r_ UA,T(D_ off), and G⁡(off)G(D_ off) are defined analogously. Also, as in Appendix D, we write μ~i(Zi):=μ^i+σ^i2T1,offZi,i∈1,2, μ_i(Z_i):= μ_i+ σ_i^2T_1, offZ_i, i∈\1,2\, for the perturbed arm means that define M~(Z) M(Z). E.1 Main results and proofs In this section, we first establish the existence of θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T in the TS setting. We then derive the TS analogues of our main UCB results: a characterization of its asymmetric regret landscape, paralleling Theorem 6, followed by an analysis of the θ selected by the Plug-In and UA approaches, paralleling Theorem 7. Without loss of generality, throughout this section, we assume that any TS(θ)(θ) algorithm is deployed by placing the two independent reward sequences and all index randomizations on a common probability space, and the reward Yi,tY_i,t is revealed when arm i is selected for the ttth time. If TS(θ)(θ) is deployed, let the arm means and pull counts be Ni(t;θ):=∑r=1tAr(θ)=i,Y¯i,n:=1n∑s=1nYi,s,μ^i(t;θ):=Y¯i,Ni(t,θ).N_i(t;θ):= _r=1^t \A_r(θ)=i\, Y_i,n:= 1n _s=1^nY_i,s, μ_i(t;θ):= Y_i,N_i(t;θ). E.1.1 Existence of θ^plug,T θ_ plug,T and θ^UA,T θ_ UA,T Proposition 11. Consider the Gaussian environment M∗M^* defined in Section 3, with RegT(θ,⋅) Reg_T(θ;·) corresponding to TS(θ)(θ) as defined above, and assume Toff≥4T_ off≥ 4. Then for almost every dataset offD_ off, the following holds for any finite horizon T: (i) θ↦RegT(θ,M^)θ Reg_T(θ; M) is continuous on Θ ; (i) θ↦RegUA,T(θ,off)θ Reg_ UA,T(θ;D_ off) is continuous on Θ . Consequently, both argmin sets in (27) and (28) are nonempty and compact. Proof of Proposition 11. Fix any offD_ off such that σ^12,σ^22>0 σ_1^2, σ_2^2>0 and μ^1≠μ^2 μ_1≠ μ_2. We will show (i) and (i) hold. We first prove a generic finite-horizon continuity statement. Fix a Gaussian environment ν with positive arm variances and distinct means. Put two independent infinite armwise reward sequences and all standard normal index randomizations Zi,t:i∈1,2,t≥3\Z_i,t:i∈\1,2\,t≥ 3\ on one probability space, and use these same random variables to run TS(θ)(θ) for all θ∈Θθ∈ . Fix θ0∈Θθ_0∈ . We show by induction on t that, almost surely, the action sequence through time t is constant in θ on some neighborhood of θ0θ_0. The initialization pulls are independent of θ. Suppose the claim holds through time t−1t-1. On the corresponding probability-one event, throughout a neighborhood of θ0θ_0 the same armwise rewards have been revealed, so Ni(t−1,θ)N_i(t-1;θ) and μ^i(t−1,θ) μ_i(t-1;θ) are constant in θ. On that neighborhood, write Dt(θ) D_t(θ) :=Ξ1(t,θ)−Ξ2(t,θ) := _1(t;θ)- _2(t;θ) =μ^1(t−1,θ)−μ^2(t−1,θ)+θZ1,tN1(t−1,θ)−Z2,tN2(t−1,θ). = μ_1(t-1;θ)- μ_2(t-1;θ)+ θ \ Z_1,t N_1(t-1;θ)- Z_2,t N_2(t-1;θ) \. For each realized past, θ↦Dt(θ)θ D_t(θ) is continuous. Moreover, conditional on the history through time t−1t-1, Dt(θ0)D_t(θ_0) is a nondegenerate Gaussian random variable with conditional variance θ0[N1(t−1,θ0)−1+N2(t−1,θ0)−1]>0.θ_0 [N_1(t-1;θ_0)^-1+N_2(t-1; _0)^-1 ]>0. Therefore ℙ⁡(Dt(θ0)=0)=0P(D_t(θ_0)=0)=0. Thus, almost surely, the sign of Dt(θ)D_t(θ) is unchanged on a sufficiently small neighborhood of θ0θ_0, proving the induction step. It follows that, for any fixed T, Ns⁡(ν)(T,θ)→Ns⁡(ν)(T,θ0)almost surely as θ→θ0.N_s(ν)(T;θ)→ N_s(ν)(T;θ_0) surely as θ→θ_0. The count is bounded by T, so dominated convergence yields continuity of θ↦RegT(θ,ν)θ Reg_T(θ;ν). Applying this result to ν=M^ν= M proves part (i). For part (i), conditional on offD_ off, the perturbed signed gap is a nondegenerate Gaussian random variable and is nonzero for almost every Z. Hence the preceding continuity statement applies for almost every Z. Also, 0≤RegT(θ,M~(Z))≤T|μ~1(Z1)−μ~2(Z2)|,0≤ Reg_T(θ; M(Z))≤ T | μ_1(Z_1)- μ_2(Z_2) |, and the right-hand side is integrable in Z. Dominated convergence proves continuity of the corresponding objective. ∎ E.1.2 Asymmetric regret of Thompson Sampling Theorem 12 (Asymmetric regret of TS). Consider the two-armed Gaussian bandit environment M∗=(⁡(μ1,σ2),⁡(μ2,σ2))M^*= (N( _1,σ^2),N( _2,σ^2) ), where μ1>μ2 _1> _2, σ2>0σ^2>0. For θ>0θ>0, let πθ _θ denote the policy induced by TS(θ)(θ) in Alg. 2. Then the following hold for its expected regret: (i) For any θ∈(0,σ2)θ∈(0,σ^2), limT→∞log⁡RegT(πθ,M∗)log⁡T=1−θσ2. _T→∞ Reg_T( _θ,M^*) T=1- θσ^2. (i) For any θ≥σ2θ≥σ^2, limT→∞RegT(πθ,M∗)log⁡T=2θμ1−μ2. _T→∞ Reg_T( _θ,M^*) T= 2θ _1- _2. Thus, θ=σ2θ=σ^2 separates two asymptotic regimes: the expected regret grows polynomially in T for θ<σ2θ<σ^2 and logarithmically in T for θ≥σ2θ≥σ^2. Proof of Theorem 12. Apply Lemma 14 to the true environment M∗M^* with o=1o=1, s=2s=2, δ=μ1−μ2δ= _1- _2, and τo2=τs2=σ2 _o^2= _s^2=σ^2. For 0<θ<σ20<θ<σ^2, part (i) follows from Lemma 14(v), applied to the constant sequence θT≡θ _T≡θ. For θ>σ2θ>σ^2, choose a compact interval K containing θ with inf>σ2 >σ^2. Lemma 14(i), together with the fact RegT(πθ,M∗)=RegT(θ,M∗)=δM∗[N2(T,θ)] Reg_T( _θ,M^*)= Reg_T(θ;M^*)=δ\,E_M^*[N_2(T;θ)], gives the desired limit. The boundary case θ=σ2θ=σ^2 follows directly from Lemma 14(iv). ∎ E.1.3 Plug-In and UA selection for Thompson Sampling We now characterize the asymptotic behavior of the Plug-In and UA selection rules for Thompson Sampling. The following result is the TS analogue of Theorem 7 for UCB and provides the full technical characterization of the selected tuning parameters and their resulting deployment regrets. Theorem 13. For any Toff≥4T_ off≥ 4, on the probability-one event ℛToffR_T_ off defined by (30), the following statements hold for the Plug-In and UA selection of the Thompson Sampling algorithm: (i) As T→∞T→∞, θ^plug,T→cplug(off):=ΠΘ(σ^a^2),lim infT→∞θ^UA,T≥cUA(off):=ΠΘ(σ^12∨σ^22). θ_ plug,T→ c_ plug(D_ off):= _ ( σ_ a^2), _T→∞ θ_ UA,T≥ c_ UA(D_ off):= _ ( σ_1^2 σ_2^2). (51) (i) The Plug-In conditional regret satisfies limT→∞log⁡(rplug,T(off))log⁡T=(1−cplug(Doff)σ2)+, _T→∞ (r_ plug,T(D_ off) ) T= (1- c_ plug(D off)σ^2 )_+, (52) and the Uncertainty-Aware conditional regret satisfies lim supT→∞log⁡(rUA,T(off))log⁡T≤(1−cUA(off)σ2)+≤(1−cplug(off)σ2)+. _T→∞ (r_ UA,T(D_ off) ) T≤ (1- c_ UA(D_ off)σ^2 )_+≤ (1- c_ plug(D_ off)σ^2 )_+. (53) (i) G⁡(off)≥1G(D_ off)≥ 1. In addition, recall the event Toff=σ^a^2<σ2<σ^3−a^2∩ℛToffA_T_ off= \ σ_ a^2<σ^2< σ_3- a^2 \ _T_ off. Then limToff→∞ℙ⁡(Toff)=14 _T_ off→∞P(A_T_ off)= 14, and on ToffA_T_ off, G⁡(off)=+∞G(D_ off)=+∞. Proof of Theorem 13. For (i), first apply Lemma 15 (i) to the fitted environment M M, and we deduce that θ^plug,T(off)→ΠΘ(σ^a^2)=cplug(off). θ_ plug,T(D_ off)→ _ ( σ_ a^2)=c_ plug(D_ off). Also, Lemma 16 implies lim infT→∞θ^UA,T(off)≥ΠΘ(σ¯2)=cUA(off). _T→∞ θ_ UA,T(D_ off)≥ _ ( σ^2)=c_ UA(D_ off). Since σ¯2≥σ^a^2 σ^2≥ σ_ a^2 and projection onto an interval is monotone, cUA(off)≥cplug(off)c_ UA(D_ off)≥ c_ plug(D_ off). For (52) in part (i), deploy the selected sequence θ^plug,T θ_ plug,T to the true environment M∗M^*. its optimal-arm variance is σ2σ^2, and the sequence converges to cplug(off)c_ plug(D_ off). Lemma 14(v) gives (52). For (53), fix ε>0 >0. By part (i), for all sufficiently large T, θ^UA,T≥cUA(off)−ε θ_ UA,T≥ c_ UA(D_ off)- . Apply Lemma 14(i) uniformly over all θ∈[(cUA(off)−ε)∨θ¯,θ¯]θ∈[(c_ UA(D_ off)- ) θ, θ], we deduce that lim supT→∞log⁡(rUA,T(off))log⁡T≤(1−cUA(off)−εσ2)+. _T→∞ (r_ UA,T(D_ off)) T≤ (1- c_ UA(D_ off)- σ^2 )_+. Letting ε↓0 0, and since cUA(off)≥cplug(off)c_ UA(D_ off)≥ c_ plug(D_ off), (53) follows. For part (i), first apply Lemma 14(i) in the true environment uniformly over θ∈Θθ∈ , gives a constant c⁡(off)>0c(D_ off)>0 such that, for all large T, rplug,T(off)∧rUA,T(off)≥c⁡(off)log⁡T.r_ plug,T(D_ off) r_ UA,T(D_ off)≥ c(D_ off) T. (54) If cplug(off)>σ2c_ plug(D_ off)>σ^2, then cUA(off)≥cplug(off)>σ2c_ UA(D_ off)≥ c_ plug(D_ off)>σ^2. Part (i) implies that both selected sequences have a fixed positive distance above σ2σ^2 for all large T. Lemma 14(i) and (54) yields rplug,T(off)=Θ⁡(log⁡T),rUA,T(off)=Θ⁡(log⁡T).r_ plug,T(D_ off)= ( T), r_ UA,T(D_ off)= ( T). In this case, ⁡(off)=1G(D_ off)=1. If cplug(off)<σ2c_ plug(D_ off)<σ^2, set q=1−cplug(off)/σ2>0q=1-c_ plug(D_ off)/σ^2>0. By (52), log⁡(rplug,T(off))=qlog⁡T+o⁡(log⁡T) (r_ plug,T(D_ off))=q T+o( T). By (53), lim supT→∞log⁡(rUA,T(off))log⁡T≤q _T→∞ (r_ UA,T(D_ off)) T≤ q. Together with (54), this implies lim infT→∞log⁡(rplug,T(off))log⁡(rUA,T(off))≥1 _T→∞ (r_ plug,T(D_ off)) (r_ UA,T(D_ off))≥ 1. The equality case cplug(off)=σ2c_ plug(D_ off)=σ^2 is excluded on ℛToffR_T_ off. This proves part (i). Finally, we analyze the event ToffA_T_ off. Note that for Gaussian data, the sample means are independent of the sample variances. Thus, a a is independent of (σ^12,σ^22)( σ_1^2, σ_2^2). In addition, the two sample variances are i.i.d. and (T1,off−1)σ^i2σ2∼χT1,off−12 (T_1, off-1) σ_i^2σ^2 χ^2_T_1, off-1. Therefore, condition on either value of a a, the probability that the fitted optimal arm has variance below σ2σ^2 and the other arm has variance above σ2σ^2 is qToff(1−qToff)q_T_ off(1-q_T_ off), where qToff:=ℙ⁡(χT1,off−12<T1,off−1)q_T_ off:=P(χ^2_T_1, off-1<T_1, off-1). This leads to ℙ⁡(Toff)=qToff(1−qToff)P(A_T_ off)=q_T_ off(1-q_T_ off). Moreover, according to the central limit theorem, limToff→∞qToff→1/2 _T_ off→∞q_T_ off→ 1/2. Thus ℙ⁡(Toff)→1/4P(A_T_ off)→ 1/4. On ToffA_T_ off, the fitted optimal arm has sample variance below σ2σ^2, and the other arm has sample variance above σ2σ^2. Since θ¯<σ2<θ¯ θ<σ^2< θ, cplug(off)<σ2<cUA(off).c_ plug(D_ off)<σ^2<c_ UA(D_ off). From the previous analysis we obtain that on ToffA_T_ off, rplug,T(off) r_ plug,T(D_ off) =T1−cplug(off)/σ2+o⁡(1), =T^1-c_ plug(D_ off)/σ^2+o(1), rUA,T(off) r_ UA,T(D_ off) =O⁡(log⁡T), =O( T), and hence ⁡(off)=∞G(D_ off)=∞. ∎ E.2 Auxiliary lemmas Lemma 14 (Fixed-environment TS regret). Consider a 2-arm bandit environment νδ=(⁡(μo,τo2),⁡(μs,τs2)) _δ= (N( _o, _o^2),N( _s, _s^2) ), where μo=μs+δ _o= _s+δ with δ>0δ>0. Let =[θ−,θ+]⊂(0,∞)K=[ _-, _+]⊂(0,∞). Then the following holds for the regret of TS(θ)(θ) and the arm pull counts in environment νδ _δ: (i) For any constant η>0η>0, there is a finite constant CηC_η, depending only on ,τo2,τs2,K, _o^2, _s^2, and η, such that for all T≥3T≥ 3, θ∈θ , and δ>0δ>0, RegT(θ,νδ)≤Cη[δ+log⁡Tδ+1δT(1−θ/τo2)++η]. Reg_T(θ; _δ)≤ C_η [δ+ Tδ+ 1δT^(1-θ/ _o^2)_++η ]. (55) (i) Fix 0<δ−≤δ+<∞0< _-≤ _+<∞ and suppose θ+<τo2 _+< _o^2. For every η>0η>0, there exist constants cη>0c_η>0 and Tη<∞T_η<∞ such that for all T≥TηT≥ T_η, infδ∈[δ−,δ+]θ∈RegT(θ,νδ)≥cηT1−θ+/τo2−η. _ subarraycδ∈[ _-, _+]\\ θ subarray Reg_T(θ; _δ)≥ c_ηT^1- _+/ _o^2-η. (56) (i) For every fixed δ>0δ>0, lim infT→∞infθ∈δ2νδ[Ns(T,θ)]2θlog⁡T≥1. _T→∞ _θ δ^2E_ _δ[N_s(T;θ)]2θ T≥ 1. (57) If, in addition, θ−≥(1+ξ)τo2 _-≥(1+ξ) _o^2 for some ξ>0ξ>0, then limT→∞supθ∈|δ2νδ[Ns(T,θ)]2θlog⁡T−1|=0. _T→∞ _θ | δ^2E_ _δ[N_s(T;θ)]2θ T-1 |=0. (58) (iv) For every fixed δ>0δ>0, when θ=τo2θ= _o^2, limT→∞RegT(θ,νδ)log⁡T=2θδ. _T→∞ Reg_T(θ; _δ) T= 2θδ. (59) (v) If θT∈ _T and θT→θ _T→θ, then limT→∞log⁡(RegT(θT,νδ))log⁡T=(1−θτo2)+. _T→∞ ( Reg_T( _T; _δ) ) T= (1- θ _o^2 )_+. (60) Proof of Lemma 14. Part (i). Fix θ∈θ and let LT(θ,δ):=⌈16θlog⁡Tδ2⌉L_T(θ,δ):= 16θ Tδ^2 . Similar to the UCB analysis, we have Ns(T,θ)≤1+LT(θ,δ)+S1,T+S2,T+S3,T,N_s(T;θ)≤ 1+L_T(θ,δ)+S_1,T+S_2,T+S_3,T, (61) where S1,T S_1,T =∑t=3T⁡At(θ)=s,Ns(t−1,θ)≥LT(θ,δ),Y¯s,Ns(t−1,θ)>μs+δ/4 = _t=3^T \A_t(θ)=s,\,N_s(t-1;θ)≥ L_T(θ,δ),\, Y_s,N_s(t-1;θ)> _s+δ/4 \ S2,T S_2,T =∑t=3T⁡At(θ)=s,Ns(t−1,θ)≥LT(θ,δ),Y¯s,Ns(t−1,θ)≤μs+δ/4,Ξs(t,θ)>μo−δ/4. = _t=3^T \A_t(θ)=s,\,N_s(t-1;θ)≥ L_T(θ,δ),\, Y_s,N_s(t-1;θ)≤ _s+δ/4,\, _s(t;θ)> _o-δ/4 \. S3,T S_3,T =∑t=3T⁡At(θ)=s,Ξs(t,θ)≤μo−δ/4. = _t=3^T \A_t(θ)=s,\, _s(t;θ)≤ _o-δ/4 \. For S1,TS_1,T, note that whenever arm s is selected, its pre-pull count increases by one. Hence each value k=Ns(t−1,θ)k=N_s(t-1;θ) can occur at most once among rounds at which At(θ)=sA_t(θ)=s. Therefore, ∑t=3TAt(θ)=s,Ns(t−1;θ)≥LT(θ,δ),Y¯s,Ns(t−1,θ)>μs+δ/4≤∑k=1∞Y¯s,k>μs+δ/4. _t=3^T \A_t(θ)=s,\,N_s(t-1;θ)≥ L_T(θ,δ),\, Y_s,N_s(t-1;θ)> _s+δ/4 \≤ _k=1^∞ \ Y_s,k> _s+δ/4 \. Since Y¯s,k−μs∼⁡(0,τs2k) Y_s,k- _s (0, _s^2k ), Gaussian concentration gives ℙ⁡(Y¯s,k>μs+δ/4)≤exp⁡−kδ232τs2P( Y_s,k> _s+δ/4)≤ \- kδ^232 _s^2 \. Thus we have ⁡[S1,T]≤1+32τs2δ2.E [S_1,T ]≤ 1+ 32 _s^2δ^2. (62) We next consider S2,TS_2,T. If Ns(t−1,θ)=kN_s(t-1;θ)=k, conditional on ℋt−1H_t-1, the history up to time t−1t-1, Ξs(t,θ)∼⁡(Y¯s,k,θk) _s(t;θ) ( Y_s,k, θk ). Hence on the event Ns(t−1,θ)=kN_s(t-1;θ)=k, Y¯s,k≤μs+δ/4 Y_s,k≤ _s+δ/4, ℙ⁡(Ξs(t,θ)>μo−δ/4|ℋt−1) P ( _s(t;θ)> _o-δ/4|H_t-1 ) =Φ⁡(−μo−δ/4−Y¯s,kθ/k) = (- _o-δ/4- Y_s,k θ/k ) ≤exp⁡−k(μo−δ/4−Y¯s,k)22θ ≤ \- k( _o-δ/4- Y_s,k)^22θ \ ≤exp⁡−kδ28θ. ≤ \- kδ^28θ \. Whenever this term is relevant, k=Ns(t−1,θ)≥LT(θ,δ)k=N_s(t-1;θ)≥ L_T(θ,δ). By the definition of LT(θ,δ)L_T(θ,δ), exp⁡−kδ28θ≤T−2 \- kδ^28θ \≤ T^-2. Taking expectations and then summing over t=3,…,Tt=3,…,T, we obtain that S2,T≤T−1.ES_2,T≤ T^-1. (63) Finally, for S3,TS_3,T, for k≥1k≥ 1, define pk(θ):=Φ⁡((Y¯o,k−μo+δ/4)kθ).p_k(θ):= (( Y_o,k- _o+δ/4) kθ ). Using Lemma 18 leads to ⁡[S3,T]≤∑k=1T−1⁡[min⁡T,1−pk(θ)pk(θ)].E[S_3,T]≤ _k=1^T-1E [ \T, 1-p_k(θ)p_k(θ) \ ]. Lemma 17(i) further implies that, for every η>0η>0, there exists a constant CηC_η such that ⁡[S3,T]≤Cηθ+δ−2T(1−θ/τo2)++η.E[S_3,T]≤ C_ηθ_+δ^-2T^(1-θ/ _o^2)_++η. (64) Substituting the above analysis into (61), we have ⁡[Ns(T,θ)]≤1+LT(θ,δ)+C⁡(1+δ−2)+T−1+Cηθ+δ−2T(1−θ/τo2)++η.E[N_s(T;θ)]≤ 1+L_T(θ,δ)+C(1+δ^-2)+T^-1+C_ηθ_+δ^-2T^(1-θ/ _o^2)_++η. We deduce (55) by multiply both sides by δ, plug in the definition of LT(θ,δ)L_T(θ,δ), and noticing that K is compact. Part (i). Fix G>0G>0 large enough such that ∑k=1∞exp⁡−kG28τs2≤12 _k=1^∞ \- kG^28 _s^2 \≤ 12. Recall that Yi,kY_i,k denotes the reward observed on the kkth pull of arm i, whereas Zi,tZ_i,t denotes the Gaussian index randomization used for arm i at calendar round t. Define FY F_Y :=⋂k≥1Y¯s,k≥μs−G/2, := _k≥ 1 \ Y_s,k≥ _s-G/2 \, FZ F_Z :=⋂k≥1Zs,k+2≥−Gk2θ+, := _k≥ 1 \Z_s,k+2≥- G k2 θ_+ \, HT H_T :=⋂t=3TZo,t≤2log⁡T, := _t=3^T \Z_o,t≤ 2 T \, ET E_T :=Yo,1≤μs−G−2θ+log⁡T. := \Y_o,1≤ _s-G- 2θ_+ T \. A Gaussian union bound gives ℙ⁡(FY)≥1/2P(F_Y)≥ 1/2. Moreover, we have ℙ⁡(FZ)=∏k=1∞Φ⁡(Gk2θ+)=:cZ>0P(F_Z)= _k=1^∞ ( G k2 θ_+ )=:c_Z>0. From a union bound we deduce that limT→∞ℙ⁡(HT)=1 _T→∞P(H_T)=1. We also have ℙ(ET)=T−θ+/τo2−o(1)P(E_T)=T^-θ_+/ _o^2-o(1) uniformly over δ∈[δ−,δ+]δ∈[ _-, _+]: Indeed, define xT(δ):=δ+G+2θ+log⁡Tτox_T(δ):= δ+G+ 2θ_+ T _o. Then uniformly over δ∈[δ−,δ+]δ∈[ _-, _+], xT(δ)22=θ+τo2log⁡T+O⁡(log⁡T) x_T(δ)^22= θ_+ _o^2 T+O( T). Thus the desired bound holds from the Gaussian Mills lower bound (Gordon, 1941), which also implies that for every η>0η>0 and all sufficiently large T, ℙ(ET)≥T−θ+/τo2−ηP(E_T)≥ T^-θ_+/ _o^2-η. Now on ET∩FY∩FZ∩HTE_T∩ F_Y∩ F_Z∩ H_T, we show by induction that arm s is selected at every round t=3,…,Tt=3,…,T, simultaneously for all θ∈θ . Specifically, suppose that arm s has been selected at all preceding post-initialization rounds 3,…,t−13,…,t-1. Then, the pre-pull count of arm s at round t is Ns(t−1,θ)=k=t−2N_s(t-1;θ)=k=t-2, while the optimal arm has not been selected since initialization so No(t−1,θ)=1N_o(t-1;θ)=1. Therefore, the posterior samples generated at round t are Ξs(t,θ)=Y¯s,k+θkZs,k+2,Ξo(t,θ)=Yo,1+θZo,t. _s(t;θ)= Y_s,k+ θk\,Z_s,k+2, _o(t;θ)=Y_o,1+ θ\,Z_o,t. Thus, on FY∩FZF_Y∩ F_Z, Ξs(t,θ)≥μs−G2−θkGk2θ+=μs−G2−G2θ+≥μs−G. _s(t;θ)≥ _s- G2- θk G k2 θ_+= _s- G2- G2 θ_+≥ _s-G. At the same time, on ET∩HTE_T∩ H_T, Ξo(t,θ)≤μs−G−2θ+log⁡T+θ2log⁡T≤μs−G. _o(t;θ)≤ _s-G- 2θ_+ T+ θ 2 T≤ _s-G. Hence arm s is selected at round t, completing the induction. Finally, note that the four events are independent: ETE_T depends only on the optimal-arm reward sequence, FYF_Y only on the suboptimal-arm reward sequence, FZF_Z only on the suboptimal-arm index randomizations, and HTH_T only on the optimal-arm index randomizations. Therefore, from the above probability calculations, RegT(θ,νδ)≥δ−⋅(T−1)⋅ℙ⁡(ET)ℙ(FY)ℙ(FZ)ℙ(HT), Reg_T(θ; _δ)≥ _-·(T-1)·P(E_T)P(F_Y)P(F_Z)P(H_T), uniformly over θ∈θ and δ∈[δ−,δ+]δ∈[ _-, _+], and thus (56) holds. Part (i). We first establish the lower bound (57). We begin with a uniform finite-exploration fact. For every fixed integer k0≥2k_0≥ 2, limt→∞supθ∈ℙ⁡(min⁡No(t,θ),Ns(t,θ)<k0)=0. _t→∞ _θ P ( \N_o(t;θ),N_s(t;θ)\<k_0 )=0. (65) To prove this, let ℬB:=supi∈o,ssupk≥1|Y¯i,k|≤B.B_B:= \ _i∈\o,s\ _k≥ 1| Y_i,k|≤ B \. Since Y¯i,k→μi Y_i,k→ _i almost surely, ℙ⁡(ℬB)↑1P(B_B) 1 as B→∞B→∞. On ℬBB_B, suppose arm i has been pulled r<k0r<k_0 times at the beginning of round t≥3t≥ 3, and let j be the other arm. Uniformly over θ∈θ , conditional independence of the current posterior samples gives ℙ⁡(At=i∣ℋt−1) P(A_t=i _t-1) ≥ℙ⁡(Ξi(t,θ)>B+1,Ξj(t,θ)≤B+1|ℋt−1) ≥P( _i(t;θ)>B+1,\ _j(t;θ)≤ B+1|H_t-1) ≥Φ⁡(−(2B+1)k0−1θ−)Φ(1θ+)=:pB>0. ≥ \! (-(2B+1) k_0-1θ_- ) \! ( 1 θ_+ )=:p_B>0. This implies that as long as arm i has fewer than k0k_0 pulls, the waiting time to its next pull is stochastically dominated by a geometric random variable with success probability pBp_B. Thus, for each arm i∈o,si∈\o,s\ and uniformly over θ∈θ , ℙ⁡(Ni(t,θ)<k0,ℬB)≤ℙ⁡(∑ℓ=1k0−1Gℓ>t−2),P(N_i(t;θ)<k_0,\ B_B)≤P ( _ =1^k_0-1G_ >t-2 ), where G1,…,Gk0−1G_1,…,G_k_0-1 are i.i.d. geometric(pB)(p_B) random variables. Therefore, for every θ∈θ , ℙ⁡(min⁡No(t,θ),Ns(t,θ)<k0) P ( \N_o(t;θ),N_s(t;θ)\<k_0 ) ≤ ≤ ℙ(ℬBc)+ℙ(minNo(t;θ),Ns(t;θ)<k0∩ℬB) P(B_B^c)+P ( \ \N_o(t;θ),N_s(t;θ)\<k_0 \ _B ) ≤ ≤ ℙ⁡(ℬBc)+∑i∈o,sℙ⁡(Ni(t,θ)<k0,ℬB) P(B_B^c)+ _i∈\o,s\P(N_i(t;θ)<k_0,\ B_B) ≤ ≤ ℙ⁡(ℬBc)+2ℙ(∑ℓ=1k0−1Gℓ>t−2). P(B_B^c)+2P ( _ =1^k_0-1G_ >t-2 ). The right-hand side above does not depend on θ, and hence supθ∈ℙ⁡(min⁡No(t,θ),Ns(t,θ)<k0)≤ℙ⁡(ℬBc)+2ℙ(∑ℓ=1k0−1Gℓ>t−2). _θ P ( \N_o(t;θ),N_s(t;θ)\<k_0 )≤P(B_B^c)+2P ( _ =1^k_0-1G_ >t-2 ). For each fixed B, pB>0p_B>0 and k0k_0 is fixed, so ∑ℓ=1k0−1Gℓ<∞ _ =1^k_0-1G_ <∞ almost surely. Therefore, ℙ⁡(∑ℓ=1k0−1Gℓ>t−2)→0P( _ =1^k_0-1G_ >t-2)→ 0 as t→∞t→∞. Therefore, for any fixed B, lim supt→∞supθ∈ℙ⁡(min⁡No(t,θ),Ns(t,θ)<k0)≤ℙ⁡(ℬBc). _t→∞ _θ P ( \N_o(t;θ),N_s(t;θ)\<k_0 )≤P(B_B^c). Letting B→∞B→∞ proves (65). We will also use the following elementary proposition on Bernoulli random variables: Let (ℱj)j=0L(F_j)_j=0^L be a filtration and let Ij∈0,1I_j∈\0,1\ be ℱjF_j-measurable for j=1,…,Lj=1,…,L. Suppose that there exists a constant p∈(0,1]p∈(0,1] and integer m≥1m≥ 1, such that ∀j=1,…,L∀ j=1,…,L, ℙ(Ij=1∣ℱj−1)≥pa.s. on ∑ℓ=1j−1Iℓ<m,P(I_j=1 _j-1)≥ p .s. on \ _ =1^j-1I_ <m \, Then ℙ⁡(∑j=1LIj<m)≤ℙ⁡(Binomial⁡(L,p)<m).P ( _j=1^LI_j<m )≤P(Binomial(L,p)<m). (66) This property follows by coupling the IjI_j’s with i.i.d. Bernoulli(p)(p) variables BjB_j (e.g. using independent uniform random variables), so that Bj≤IjB_j≤ I_j whenever ∑ℓ=1j−1Iℓ<m _ =1^j-1I_ <m. Now return to the proof of (i). Fix ρ∈(0,1)ρ∈(0,1) and set mmax(T):=⌈2θ+(1−ρ)log⁡Tδ2⌉m_ (T):= 2θ_+(1-ρ) Tδ^2 . Choose ε>0 >0 sufficiently small that α:=(1+3ε)2(1−ρ)<1α:=(1+3 )^2(1-ρ)<1. Let ℓ0(T)=⌊T/2⌋−mmax(T)−2 _0(T)= T/2 -m_ (T)-2. For any fixed ζ>0ζ>0, we can choose k0k_0 large enough such that ℙ(Gs)=ℙ(∩k≥k0Y¯s,k≥μs−εδ)≥1−ζ.P(G_s)=P ( _k≥ k_0\ Y_s,k≥ _s- δ\ )≥ 1-ζ. (67) At the same time, a union bound gives limT→∞ℙ(Go,T)=limT→∞ℙ(∩ℓ=ℓ0(T)TY¯o,ℓ≤μo+εδ)=1. _T→∞P(G_o,T)= _T→∞P ( _ = _0(T)^T\ Y_o, ≤ _o+ δ\ )=1. (68) Also, by (65), limT→∞supθ∈ℙ⁡(Ns(⌊T/2⌋,θ)<k0)=0. _T→∞ _θ P (N_s( T/2 ;θ)<k_0 )=0. (69) Fix θ∈θ and consider the event T(θ):=Gs∩Go,T∩Ns(⌊T/2⌋;θ)≥k0G_T(θ):=G_s∩ G_o,T∩\N_s( T/2 ;θ)≥ k_0\. Then we have supθ∈ℙ⁡(T(θ)c)≤ζ+o⁡(1) _θ P(G_T(θ)^c)≤ζ+o(1) as T→∞T→∞. On T(θ)G_T(θ), at any decision point t∈⌊T/2⌋+1,…,Tt∈\ T/2 +1,…,T\ before k:=Ns(t−1,θ)k:=N_s(t-1;θ) reaches m−(θ,T):=⌊2θ(1−ρ)log⁡Tδ2⌋m_-(θ,T):= 2θ(1-ρ) Tδ^2 , we have k≥k0k≥ k_0, k<m−(θ,T)≤mmax(T)k<m_-(θ,T)≤ m_ (T), and No(t−1,θ)=t−1−k≥ℓ0(T)N_o(t-1;θ)=t-1-k≥ _0(T). Thus Y¯s,k≥μs−εδ=μo−(1+ε)δ,Y¯o,No(t−1,θ)≤μo+εδ. Y_s,k≥ _s- δ= _o-(1+ )δ, Y_o,N_o(t-1;θ)≤ _o+ δ. Note that conditional on the history, the two current posterior samples are independent, thus on T(θ)G_T(θ), ℙ⁡(At=s|ℋt−1) P(A_t=s|H_t-1) ≥ℙ⁡(Ξs(t,θ)≥μo+2εδ,Ξo(t,θ)≤μo+2εδ|ℋt−1) ≥P( _s(t;θ)≥ _o+2 δ, _o(t;θ)≤ _o+2 δ|H_t-1) ≥12Φ(−(1+3ε)δk/θ) ≥ 12\, (-(1+3 )δ k/θ ) ≥12Φ(−2αlog⁡T) ≥ 12 (- 2α T ) ≥122αlog⁡T1+2αlog⁡T⋅12πT−α ≥ 12 2α T1+2α T· 1 2πT^-α ≥cα(logT)−1/2T−α=:pT. ≥ c_α( T)^-1/2T^-α=:p_T. Here cαc_α is a constant that depends only on α. We have used the Gaussian Mills lower bound on normal CDF and the fact that k/θ≤2(1−ρ)log⁡T/δ2k/θ≤ 2(1-ρ) T/δ^2. Now for any θ∈θ , for each t=⌊T/2⌋+1,…,Tt= T/2 +1,…,T, define It(θ):=At=s,if Ns(t−1,θ)<m−(θ,T),Y¯s,Ns(t−1,θ)≥μs−ϵδ,Y¯o,No(t−1,θ)≤μo+ϵδ,1,otherwise.I_t(θ):= cases \A_t=s\,&if array[]lN_s(t-1;θ)<m_-(θ,T),\\[-2.0pt] Y_s,N_s(t-1;θ)≥ _s-εδ,\\[-2.0pt] Y_o,N_o(t-1;θ)≤ _o+εδ, array\\[12.0pt] 1,&otherwise. cases By the preceding calculation, for every t=⌊T/2⌋+1,…,Tt= T/2 +1,…,T, ℙ⁡(It(θ)=1∣ℋt−1)≥pTP(I_t(θ)=1 _t-1)≥ p_T. Therefore we deduce from (66) that for every integer m≥1m≥ 1, ℙ⁡(∑t=⌊T/2⌋+1TIt(θ)<m)≤ℙ⁡(Binomial⁡(T−⌊T/2⌋,pT)<m).P ( _t= T/2 +1^TI_t(θ)<m )≤P (Binomial (T- T/2 ,p_T )<m ). Note that if Ns(T,θ)<m−(θ,T)N_s(T;θ)<m_-(θ,T), then on T(θ)G_T(θ), whenever Ns(t−1,θ)≥k0N_s(t-1;θ)≥ k_0, the two empirical-mean conditions in the definition of It(θ)I_t(θ) hold. Hence It(θ)=At=sI_t(θ)= \A_t=s\ throughout t=⌊T/2⌋+1,…,Tt= T/2 +1,…,T. In addition, since Ns(⌊T/2⌋,θ)≥k0N_s( T/2 ;θ)≥ k_0 on T(θ)G_T(θ), ∑t=⌊T/2⌋+1TIt(θ)=Ns(T,θ)−Ns(⌊T/2⌋,θ)<m−(θ,T)−k0≤mmax(T). _t= T/2 +1^TI_t(θ)=N_s(T;θ)-N_s( T/2 ;θ)<m_-(θ,T)-k_0≤ m_ (T). Therefore, ℙ⁡(Ns(T,θ)<m−(θ,T)) P(N_s(T;θ)<m_-(θ,T)) ≤ℙ⁡(T(θ)c)+ℙ⁡(∑t=⌊T/2⌋+1TIt(θ)<mmax(T)) ≤P(G_T(θ)^c)+P ( _t= T/2 +1^TI_t(θ)<m_ (T) ) ≤ζ+o⁡(1)+ℙ⁡(Binomial⁡(T−⌊T/2⌋,pT)<mmax(T)), ≤ζ+o(1)+P (Binomial (T- T/2 ,p_T )<m_ (T) ), uniformly over θ∈θ . Because (T−⌊T/2⌋)pT≍T1−αlog⁡T≫mmax(T)(T- T/2 )p_T T^1-α T m_ (T), the last probability tends to zero. Letting ζ↓0ζ 0 yields limT→∞infθ∈ℙ⁡(Ns(T,θ)≥m−(θ,T))=1. _T→∞ _θ P(N_s(T;θ)≥ m_-(θ,T))=1. Consequently, lim infT→∞infθ∈δ2[Ns(T,θ)]2θlog⁡T≥1−ρ _T→∞ _θ δ^2E[N_s(T;θ)]2θ T≥ 1-ρ. Let ρ↓0ρ 0 to obtain (57). We now show (58). Fix constants ρ>0ρ>0 and ε∈(0,1/2) ∈(0,1/2), and define bε:=μo−εδb_ := _o- δ, LT′(θ):=⌈2θ(1+ρ)log⁡T(1−2ε)2δ2⌉L_T (θ):= 2θ(1+ρ) T(1-2 )^2δ^2 . Similar to part (i), for every θ∈θ , decompose Ns(T,θ) N_s(T;θ) ≤1+LT′(θ)+S1,T′(θ)+S2,T′(θ)+S3,T′(θ), ≤ 1+L_T (θ)+S_1,T (θ)+S_2,T (θ)+S_3,T (θ), (70) where S1,T′(θ) S_1,T (θ) :=∑t=3T⁡At(θ)=s,Ns(t−1,θ)≥LT′(θ),Y¯s,Ns(t−1,θ)>μs+εδ, := _t=3^T \A_t(θ)=s,\,N_s(t-1;θ)≥ L_T (θ),\, Y_s,N_s(t-1;θ)> _s+ δ \, S2,T′(θ) S_2,T (θ) :=∑t=3T⁡At(θ)=s,Ns(t−1,θ)≥LT′(θ),Y¯s,Ns(t−1,θ)≤μs+εδ,Ξs(t,θ)>bε, := _t=3^T \A_t(θ)=s,\,N_s(t-1;θ)≥ L_T (θ),\, Y_s,N_s(t-1;θ)≤ _s+ δ,\, _s(t;θ)>b_ \, S3,T′(θ) S_3,T (θ) :=∑t=3T⁡At(θ)=s,Ξs(t,θ)≤bε. := _t=3^T \A_t(θ)=s,\, _s(t;θ)≤ b_ \. We bound the three terms separately. For S1,T′(θ)S _1,T(θ), Similar to the analysis in part (i), S1,T′(θ)≤∑k=LT′(θ)∞Y¯s,k>μs+εδS_1,T (θ)≤ _k=L_T (θ)^∞ \ Y_s,k> _s+ δ\. Since Y¯s,k−μs∼⁡(0,τs2k) Y_s,k- _s (0, _s^2k ), we have ⁡[S1,T′(θ)]≤∑k=LT′(θ)∞exp⁡−kε2δ22τs2=exp−LT′(θ)ε2δ2/(2τs2)1−exp−ε2δ2/(2τs2). [S_1,T (θ)]≤ _k=L_T (θ)^∞ \- k ^2δ^22 _s^2 \= \-L_T (θ) ^2δ^2/(2 _s^2)\1- \- ^2δ^2/(2 _s^2)\. (71) Since LT′(θ)≥2θ−(1+ρ)log⁡T(1−2ε)2δ2L_T (θ)≥ 2θ_-(1+ρ) T(1-2 )^2δ^2, the numerator in (71) is no larger than T−c1T^-c_1, where c1:=θ−(1+ρ)ε2(1−2ε)2τs2>0c_1:= θ_-(1+ρ) ^2(1-2 )^2 _s^2>0. Thus, supθ∈⁡[S1,T′(θ)]=O⁡(T−cρ,ε)=o⁡(1). _θ E[S _1,T(θ)]=O(T^-c_ρ, )=o(1). (72) Next consider S2,T′(θ)S _2,T(θ). If Ns(t−1,θ)=kN_s(t-1;θ)=k, then conditional on ℋt−1H_t-1, Ξs(t,θ)∼⁡(Y¯s,k,θk) _s(t;θ) ( Y_s,k, θk ). Thus, on the event k=Ns(t−1,θ)≥LT′(θ)k=N_s(t-1;θ)≥ L_T (θ), Y¯s,k≤μs+εδ Y_s,k≤ _s+ δ, ℙ⁡Ξs(t,θ)>bε∣ℋt−1 P\ _s(t;θ)>b_ _t-1\ =Φ⁡(−bε−Y¯s,kθ/k) = (- b_ - Y_s,k θ/k ) ≤exp⁡−k(bε−Y¯s,k)22θ ≤ \- k(b_ - Y_s,k)^22θ \ ≤exp⁡−k(1−2ε)2δ22θ ≤ \- k(1-2 )^2δ^22θ \ ≤T−(1+ρ). ≤ T^-(1+ρ). Taking expectations and summing over t=3,…,Tt=3,…,T gives supθ∈⁡[S2,T′(θ)]≤T−ρ. _θ E[S _2,T(θ)]≤ T^-ρ. (73) Finally, we control S3,T′(θ)S _3,T(θ). For k≥1k≥ 1, define pk(θ):=Φ⁡((Y¯o,k−bε)kθ)p_k(θ):= (( Y_o,k-b_ ) kθ ). Without loss of generality, we can write Y¯o,k=μo+τokZ Y_o,k= _o+ _o kZ for some Z∼⁡(0,1)Z (0,1). Thus we have (Y¯o,k−bε)kθ=εδθk+τoθZ.( Y_o,k-b_ ) kθ= δ θ k+ _o θZ. (74) Moreover, by the assumption θ≥θ−≥(1+ξ)τo2θ≥θ_-≥(1+ξ) _o^2, the parameter λ⁡(θ):=τoθλ(θ):= _o θ ranges over the fixed compact interval [τoθ+,τoθ−]⊂(0,1)[ _o θ_+, _o θ_-]⊂(0,1). We can use Lemma 18 and Lemma 17(i) to obtain ⁡[S3,T′(θ)] [S _3,T(θ)] ≤∑k=1T−1⁡[1−pk(θ)pk(θ)] ≤ _k=1^T-1E [ 1-p_k(θ)p_k(θ) ] ≤∑k=1∞⁡[H⁡(εδθk+τoθZ)] ≤ _k=1^∞E [H ( δ θ k+ _o θZ ) ] ≤C(εδθ)−2≤Cθ+ε2δ2, ≤ C ( δ θ )^-2≤ C θ_+ ^2δ^2, where C<∞C<∞ depends only on K and τo2 _o^2. In particular, supθ∈⁡[S3,T′(θ)]=O⁡(1). _θ E[S _3,T(θ)]=O(1). (75) Combining (70), (72), (73), and (75), we obtain supθ∈⁡[Ns(T,θ)] _θ E[N_s(T;θ)] ≤LT′(θ)+O⁡(1). ≤ L_T (θ)+O(1). (76) Since θ≥θ−>0θ≥θ_->0, lim supT→∞supθ∈δ2[Ns(T,θ)]2θlog⁡T≤1+ρ(1−2ε)2 _T→∞ _θ δ^2E[N_s(T;θ)]2θ T≤ 1+ρ(1-2 )^2. Letting first ε↓0 0 and then ρ↓0ρ 0 yields lim supT→∞supθ∈δ2[Ns(T,θ)]2θlog⁡T≤1. _T→∞ _θ δ^2E[N_s(T;θ)]2θ T≤ 1. (77) Combining this inequality with (57), we obtain (58). Part (iv). Fix δ>0δ>0 and assume θ=τo2θ= _o^2. LHS≥ in (59) follows from part (i) applied to a compact interval containing θ. To prove LHS≤ in (59), fix ρ>0ρ>0 and ε∈(0,1/2) ∈(0,1/2), and use the same definitions of bεb_ , LT′(θ)L _T(θ), and Sj,T′(θ)S _j,T(θ), j=1,2,3j=1,2,3, as in part (i). The analysis for S1,T′(θ)S _1,T(θ) and S2,T′(θ)S _2,T(θ) remain valid. We now show that νδ[S3,T′(θ)]=O⁡(1)E_ _δ[S _3,T(θ)]=O(1). Let a:=εδθ>0a:= δ θ>0, Xk:=(Y¯o,k−bε)kθX_k:=( Y_o,k-b_ ) kθ for k≥1k≥ 1. Since θ=τo2θ= _o^2, we have Xk∼⁡(ak,1)X_k (a k,1). According to Lemma 18, νδ[S3,T′(θ)]≤∑k=1T−1νδ[H⁡(Xk)].E_ _δ[S _3,T(θ)]≤ _k=1^T-1E_ _δ[H(X_k)]. We now show that the corresponding infinite sum is still finite. From Lemma 17, we have νδ[H(Xk)Xk≥0]≤Cνδ[e−Xk2/2]=C2e−a2k/4.E_ _δ [H(X_k)1\X_k≥ 0\ ]≤ CE_ _δ [e^-X_k^2/2 ]= C 2e^-a^2k/4. On the other hand, we also have νδ[H(Xk)Xk<0] _ _δ [H(X_k)1\X_k<0\ ] ≤C2π∫−∞0(1+|x|)exp⁡x22−(x−ak)22x ≤ C 2π _-∞^0(1+|x|) \ x^22- (x-a k)^22 \\,dx =C2πe−a2k/2∫−∞0(1+|x|)eakxdx = C 2πe^-a^2k/2 _-∞^0(1+|x|)e^a kx\,dx =C2πe−a2k/2(1ak+1a2k). = C 2πe^-a^2k/2 ( 1a k+ 1a^2k ). Since a>0a>0 is fixed, both upper bounds summed in k is finite. Consequently, ∑k=1∞νδ[H⁡(Xk)]<∞ _k=1^∞E_ _δ[H(X_k)]<∞, and hence νδ[S3,T′(θ)]=O⁡(1)E_ _δ[S _3,T(θ)]=O(1). Combining this bound with the decomposition and the bounds for S1,T′(θ)S _1,T(θ) and S2,T′(θ)S _2,T(θ) from part (i) yields νδ[Ns(T,θ)]≤2θ(1+ρ)(1−2ε)2δ2log⁡T+O⁡(1),E_ _δ[N_s(T;θ)]≤ 2θ(1+ρ)(1-2 )^2δ^2 T+O(1), where the O⁡(1)O(1) term may depend on ρ,ε,δ,τo2,τs2ρ, ,δ, _o^2, _s^2, but not on T. Thus, lim supT→∞RegT(θ,νδ)log⁡T≤2θ(1+ρ)(1−2ε)2δ. _T→∞ Reg_T(θ; _δ) T≤ 2θ(1+ρ)(1-2 )^2δ. Letting ε↓0 0 and ρ↓0ρ 0, and combining with the first part, we prove (59). Part (v). Suppose first that θ<τo2θ< _o^2. Choose ε>0 >0 such that θ+ε<τo2θ+ < _o^2. For all sufficiently large T, θT∈[θ−ε,θ+ε]θ_T∈[θ- ,θ+ ]. Part (i) gives, for every η>0η>0, lim infT→∞log⁡(RegT(θT,νδ))log⁡T≥1−θ+ετo2−η. _T→∞ ( Reg_T(θ_T; _δ)) T≥ 1- θ+ _o^2-η. By letting η↓0η 0 and ε↓0 0, we obtain that LHS≥ RHS in (60). The ≤ side is a direct consequence of Part (i). Now assume θ≥τo2θ≥ _o^2. Part (i) implies that the limsup in (60) is no larger than zero. Since the initialization pulls the suboptimal arm once, RegT(θT,νδ)≥δ Reg_T(θ_T; _δ)≥δ, so the liminf is at least zero. This proves (60). ∎ Lemma 15 (Limit of the Plug-In minimizer). Let ν be a fixed two-armed Gaussian environment with distinct means and positive variances. Let τo2 _o^2 be the variance of its optimal arm and assume τo2∉θ¯,θ¯ _o^2∉\ θ, θ\. For each T, let θT(ν)∈argminθ∈Θ⁡RegT(θ,ν) _T(ν)∈ _θ∈ Reg_T(θ;ν), where RegT(θ,⋅) Reg_T(θ;·) corresponds to the TS algorithm. Then limT→∞θT(ν)=ΠΘ(τo2). _T→∞ _T(ν)= _ ( _o^2). (78) Proof of Lemma 15. The proof is similar to the UCB setting and is stated here for completeness. For simplicity, write θT=θT(ν)θ_T=θ_T(ν) and c=ΠΘ(τo2)c= _ ( _o^2). If τo2<θ¯ _o^2< θ, by (58), for every fixed ε>0 >0, infθ∈[θ¯+ε,θ¯]RegT(θ,ν)>RegT(θ¯,ν) _θ∈[ θ+ , θ] Reg_T(θ;ν)> Reg_T( θ;ν) for all sufficiently large T, because the leading term is 2θlog⁡T/δ2θ T/δ. Hence θT<θ¯+εθ_T< θ+ eventually. Thus, θT→θ¯=cθ_T→ θ=c. Suppose τo2∈(θ¯,θ¯) _o^2∈( θ, θ). Fix a sufficiently small ε>0 >0. For θ≤τo2−εθ≤ _o^2- , Lemma 14(i) gives a positive polynomial regret lower bound, whereas θ0=τo2+ε/2θ_0= _o^2+ /2 has logarithmic regret by Lemma 14(i). Thus θT>τo2−εθ_T> _o^2- for sufficiently large T. On the other hand, Lemma 14(i) implies infθ∈[τo2+ε,θ¯]RegT(θ,ν)>RegT(θ0,ν) _θ∈[ _o^2+ , θ] Reg_T(θ;ν)> Reg_T(θ_0;ν) for all sufficiently large T. Thus θT<τo2+εθ_T< _o^2+ eventually. Let ε↓0 0 proves convergence to c=τo2c= _o^2. Finally, suppose τo2>θ¯ _o^2> θ. Fix ε>0 >0. By the uniform lower bound in Lemma 14(i), every θ≤θ¯−εθ≤ θ- has regret exponent at least 1−(θ¯−ε)/τo2−o⁡(1)1-( θ- )/ _o^2-o(1), whereas the upper envelope in Lemma 14(i) shows that θ¯ θ has exponent at most 1−θ¯/τo2+o⁡(1)1- θ/ _o^2+o(1). The former exponent is strictly larger, so θT>θ¯−εθ_T> θ- eventually. Hence θT→θ¯=cθ_T→ θ=c as T→∞T→∞. ∎ Lemma 16 (Limit of the Gaussian-perturbed minimizer). Consider the TS(θ)(θ) algorithm defined in Alg. 2. Fix any offline data offD_ off with σ^12,σ^22>0 σ_1^2, σ_2^2>0. Let σ¯2=σ^12∨σ^22 σ^2= σ_1^2 σ_2^2. If θT∈Θ _T∈ and θT→θ _T→θ, then limT→∞log⁡(RegUA,T(θT,off))log⁡T=(1−θσ¯2)+. _T→∞ ( Reg_ UA,T( _T;D_ off) ) T= (1- θ σ^2 )_+. (79) Consequently, every sequence of minimizers in (28) satisfies lim infT→∞θ^UA,T(off)≥ΠΘ(σ¯2). _T→∞ θ_ UA,T(D_ off)≥ _ ( σ^2). (80) Proof of Lemma 16. The proof is similar to the UCB setting and is stated here for completeness. Let X:=|μ~1(Z1)−μ~2(Z2)|X:=| μ_1(Z_1)- μ_2(Z_2)|. Conditional on offD_ off, X has a folded-normal distribution with bounded density on (0,∞)(0,∞) and finite first moment. Fix η such that 0<η<12[1−(1−θ¯/σ¯2)+]0<η< 12[1-(1- θ/ σ^2)_+]. For any perturbed environment, its optimal-arm variance is at most σ¯2 σ^2. Apply Lemma 14(i) gives RegT(θT,M~(Z))≤Cη[X+BTX], Reg_T(θ_T; M(Z))≤ C_η [X+ B_TX ], where BT:=log⁡T+TqT+ηB_T:= T+T^q_T+η, qT:=(1−θTσ¯2)+q_T:= (1- θ_T σ^2 )_+. We also have the trivial bound RegT≤TX Reg_T≤ TX. Let xT:=BT/Tx_T:= B_T/T. Then limT→∞xT=0 _T→∞x_T=0. Denote fXf_X as the density of X, then ‖fX‖∞<∞\|f_X\|_∞<∞, and [TXX≤xT] [TX \X≤ x_T\] ≤12‖fX‖∞TxT2=O⁡(BT), ≤ 12\|f_X\|_∞Tx_T^2=O(B_T), [BTXxT<X≤1] [ B_TX \x_T<X≤ 1\ ] ≤‖fX‖∞BTlog⁡(1/xT)=O⁡(BTlog⁡T), ≤\|f_X\|_∞B_T (1/x_T)=O(B_T T), [BTXX>1] [ B_TX \X>1\ ] =O⁡(BT). =O(B_T). Therefore RegUA,T(θT,off)≤C′BT(1+log⁡T), Reg_ UA,T(θ_T;D_ off)≤ C B_T(1+ T), and hence lim supT→∞log⁡(RegUA,T(θT,off))log⁡T≤(1−θσ¯2)++η. _T→∞ ( Reg_ UA,T(θ_T;D_ off)) T≤ (1- θ σ^2 )_++η. Let η↓0η 0, and we prove LHS≤ in (79). Below we prove the reverse direction LHS≥ . The case θ≥σ¯2θ≥ σ^2 is immediate from nonnegativity. Now suppose θ<σ¯2θ< σ^2, and let h be an arm with σ^h2=σ¯2 σ_h^2= σ^2. The signed perturbed gap μ~h(Zh)−μ~3−h(Z3−h) μ_h(Z_h)- μ_3-h(Z_3-h) is nondegenerate Gaussian. Thus, there exist 0<g−<g+<∞0<g_-<g_+<∞ such that the event :=g−≤μ~h(Zh)−μ~3−h(Z3−h)≤g+W:=\g_-≤ μ_h(Z_h)- μ_3-h(Z_3-h)≤ g_+\ has conditional probability w⁡(off)>0w(D_ off)>0. On W, arm h is optimal, its variance is σ¯2 σ^2, and the gap lies in [g−,g+][g_-,g_+]. Fix ε,η>0 ,η>0 small enough such that θ+ε<σ¯2θ+ < σ^2. Eventually θT≤θ+εθ_T≤θ+ . Lemma 14(i), applied uniformly on W, gives RegUA,T(θT,off)≥w⁡(off)cε,ηT1−(θ+ε)/σ¯2−η Reg_ UA,T(θ_T;D_ off)≥ w(D_ off)c_ ,ηT^1-(θ+ )/ σ^2-η for a constant cε,ηc_ ,η depending only on ε and η. Taking log and letting ε,η↓0 ,η 0 proves the desired inequality. Finally, we prove (80). Let c=ΠΘ(σ¯2)c= _ ( σ^2) and suppose some subsequence of minimizers converges to θ<cθ<c. If σ¯2∈(θ¯,θ¯) σ^2∈( θ, θ), choose a comparator θ′∈(σ¯2,θ¯]θ ∈( σ^2, θ]. Along the subsequence, the minimizers have a strictly positive objective exponent by (79), whereas the comparator has exponent zero, contradicting optimality. If σ¯2≥θ¯ σ^2≥ θ, use the comparator θ′=θ¯θ = θ; then 1−θ/σ¯2>1−θ¯/σ¯21-θ/ σ^2>1- θ/ σ^2, again contradicting optimality. If σ¯2≤θ¯ σ^2≤ θ, then c=θ¯c= θ and no point of Θ is below c. Thus no limit lies below c. ∎ Lemma 17 (Gaussian odds). Recall that H⁡(x)=Φ⁡(−x)Φ⁡(x)H(x)= (-x) (x). There exists a universal constant C<∞C<∞ such that H⁡(x)≤Ce−x2/2,x≥0,C⁡(1+|x|)ex2/2,x<0.H(x)≤ casesCe^-x^2/2,&x≥ 0,\\ C(1+|x|)e^x^2/2,&x<0. cases (81) In addition, fix any a>0a>0 and let λ∈Λ=[λ−,λ+]λ∈ =[ _-, _+], where 0<λ−<λ+<+∞0< _-< _+<+∞. For each k∈ℕ+k ^+, let Xk∼⁡(ak,λ2)X_k (a k,λ^2). Then the following holds: (i) If λ+<1 _+<1, then there exists constant C′C depending only on Λ such that ∑k=1∞⁡[H⁡(Xk)]≤C′a−2. _k=1^∞E[H(X_k)]≤ C a^-2. (82) (i) For every η>0η>0, there exists constant CηC_η depending only on η and Λ such that ∑k=1∞⁡[min⁡T,H⁡(Xk)]≤Cηa−2T(1−λ−2)++η,∀λ∈Λ,T≥3. _k=1^∞E [ \T,H(X_k)\ ]≤ C_ηa^-2T^(1-λ^-2)_++η, ∀λ∈ ,T≥ 3. (83) Proof of Lemma 17. We first prove (81). For x≥0x≥ 0, Φ⁡(x)≥1/2 (x)≥ 1/2 and a standard Gaussian upper-tail bound gives the first line of (81). For x<0x<0, apply the Mills lower bound Φ⁡(x)=Φ⁡(−|x|)≥|x|1+x2ϕ(|x|) (x)= (-|x|)≥ |x|1+x^2φ(|x|) when |x|≥1|x|≥ 1. We can then adjust the constant to accommodate the case x∈[−1,0]x∈[-1,0]. We now prove (i). We first consider the case Xk≥0\X_k≥ 0\. By the first case of (81), H(Xk)Xk≥0≤Ce−Xk2/2Xk≥0≤Ce−Xk2/2H(X_k) \X_k≥ 0\≤ Ce^-X_k^2/2 \X_k≥ 0\≤ Ce^-X_k^2/2. Thus [H(Xk)Xk≥0]≤C[e−Xk2/2].E\! [H(X_k) \X_k≥ 0\ ]≤ C\,E\! [e^-X_k^2/2 ]. Since Xk∼N⁡(ak,λ2)X_k N(a k,λ^2), [e−Xk2/2]=11+λ2exp−a2k2(1+λ2)E[e^-X_k^2/2]= 1 1+λ^2 \- a^2k2(1+λ^2) \. In addition, because λ≤λ+λ≤ _+, we deduce that [H(Xk)Xk≥0]≤Cexp−a2k2(1+λ+2).E\! [H(X_k) \X_k≥ 0\ ]≤ C \- a^2k2(1+ _+^2) \. Summing over k gives ∑k=1∞[H(Xk)Xk≥0] _k=1^∞E\! [H(X_k) \X_k≥ 0\ ] ≤C∑k=1∞exp⁡−a2k2(1+λ+2) ≤ C _k=1^∞ \- a^2k2(1+ _+^2) \ =Cexp⁡a2/[2(1+λ+2)]−1 = C \a^2/[2(1+ _+^2)]\-1 ≤CΛa−2, ≤ C_ a^-2, where CΛC_ depends only on Λ . The last inequality follows from the fact that ex−1≥xe^x-1≥ x for x≥0x≥ 0. Now consider Xk<0\X_k<0\. Since Xk∼⁡(ak,λ2)X_k (a k,λ^2), the second case of (81) gives [H(Xk)Xk<0] \! [H(X_k) \X_k<0\ ] =∫−∞0H⁡(x)12πλexp⁡−(x−ak)22λ2x = _-∞^0H(x) 1 2πλ \- (x-a k)^22λ^2 \\,dx ≤Cλ∫−∞0(1+|x|)exp⁡x22−(x−ak)22λ2x ≤ Cλ _-∞^0(1+|x|) \ x^22- (x-a k)^22λ^2 \\,dx =Cλe−a2k/(2λ2)∫−∞0(1+|x|)exp−1−λ22λ2x2+akλ2xdx. = Cλe^-a^2k/(2λ^2) _-∞^0(1+|x|) \- 1-λ^22λ^2x^2+ a kλ^2x \\,dx. Here note that when x<0x<0, akλ2x≤0 a kλ^2x≤ 0. Moreover, 1−λ22λ2≥cλ+:=1−λ+22λ+2>0 1-λ^22λ^2≥ c_ _+:= 1- _+^22 _+^2>0. Therefore, [H(Xk)Xk<0]≤CΛe−a2k/(2λ2)∫−∞0(1+|x|)e−cλ+x2dx≤CΛ′e−a2k/(2λ+2) \! [H(X_k) \X_k<0\ ]≤ C_ e^-a^2k/(2λ^2) _-∞^0(1+|x|)e^-c_ _+x^2\,dx≤ C_ e^-a^2k/(2 _+^2) for constants CΛC_ , CΛ′C_ depending only on Λ . Hence ∑k=1∞[H(Xk)Xk<0]≤CΛ′∑k=1∞e−a2k/(2λ+2)=CΛ′ea2/(2λ+2)−1≤CΛ′a−2, _k=1^∞E\! [H(X_k) \X_k<0\ ]≤ C_ _k=1^∞e^-a^2k/(2 _+^2)= C_ e^a^2/(2 _+^2)-1≤ C_ a^-2, where CΛ′C_ depends only on Λ . Here the last inequality follows from ex−1≥xe^x-1≥ x. Combining the above arguments, we obtain (82). For (i), fix a small γ>0γ>0. Then there exists a constant CγC_γ such that ∀x<0∀ x<0, 1+|x|≤Cγexp⁡(γx2/2)1+|x|≤ C_γ (γ x^2/2). Thus for x<0x<0, H⁡(x)≤Cγexp⁡(1+γ)x2/2H(x)≤ C_γ \(1+γ)x^2/2\. For any u≥u0:=eCγu≥ u_0:=eC_γ, the event H⁡(Xk)>uH(X_k)>u and Xk<0X_k<0 implies Xk<−yuX_k<-y_u, yu:=21+γlog⁡(u/Cγ)y_u:= 21+γ (u/C_γ). Therefore ∑k=1∞ℙ⁡(Xk<0,H⁡(Xk)>u) _k=1^∞P(X_k<0,H(X_k)>u) ≤∑k=1∞ℙ⁡(Xk<−yu)≤∑k=1∞exp⁡−(yu+ak)22λ2 ≤ _k=1^∞P(X_k<-y_u)≤ _k=1^∞ \- (y_u+a k)^22λ^2 \ ≤exp⁡−yu22λ2∑k=1∞exp⁡−a2k2λ2≤2λ2a2exp⁡−yu22λ2 ≤ \- y_u^22λ^2 \ _k=1^∞ \- a^2k2λ^2 \≤ 2λ^2a^2 \- y_u^22λ^2 \ ≤Cγ′a−2u−1/(1+γ)λ2. ≤ C_γ a^-2u^-1/\(1+γ)λ^2\. Here Cγ′C_γ is a constant that depends only on CγC_γ and Λ . Let S−(T):=∑k=1∞[minT,H(Xk)Xk<0].S_-(T):= _k=1^∞E\! [ \T,H(X_k)\ \X_k<0\ ]. Using the tail-integral identity ⁡[min⁡T,Y]=∫0Tℙ⁡(Y>u)uE[ \T,Y\]= _0^TP(Y>u)\,du for Y≥0Y≥ 0, for T≥u0T≥ u_0, S−(T) S_-(T) =∑k=1∞∫0Tℙ(minT,H(Xk)Xk<0>u)du = _k=1^∞ _0^TP( \T,H(X_k)\ \X_k<0\>u)du ≤∑k=1∞∫0Tℙ(H(Xk)Xk<0>u)du ≤ _k=1^∞ _0^TP(H(X_k) \X_k<0\>u)du =∫0T∑k=1∞ℙ⁡(H⁡(Xk)>u,Xk<0)u = _0^T _k=1^∞P(H(X_k)>u,\ X_k<0)\,du =∫0u0∑k=1∞ℙ⁡(H⁡(Xk)>u,Xk<0)u+∫u0T∑k=1∞ℙ⁡(H⁡(Xk)>u,Xk<0)u = _0^u_0 _k=1^∞P(H(X_k)>u,\ X_k<0)\,du+ _u_0^T _k=1^∞P(H(X_k)>u,\ X_k<0)\,du ≤C2a−2u0+Cγ′a−2∫u0Tu−1/(1+γ)λ2du ≤ C_2a^-2u_0+C_γ a^-2 _u_0^Tu^-1/\(1+γ)λ^2\\,du ≤Cγ′a−2[u0+∫u0Tu−1/(1+γ)λ2du]. ≤ C_γ a^-2 [u_0+ _u_0^Tu^-1/\(1+γ)λ^2\\,du ]. Here C2C_2 is a constant depending on Λ , and Cγ′=C2+Cγ′C_γ =C_2+C_γ . If 3≤T<u03≤ T<u_0, we can similarly obtain that S−(T)≤C2a−2u0S_-(T)≤ C_2a^-2u_0. At the same time, an argument similar to the analysis in (i) gives ∑k=1∞[minT,H(Xk)Xk≥0]≤∑k=1∞[H(Xk)Xk≥0]≤CΛa−2. _k=1^∞E[ \T,H(X_k)\ \X_k≥ 0\]≤ _k=1^∞E[H(X_k) \X_k≥ 0\]≤ C_ a^-2. Here CΛC_ is a constant depending only on Λ . By summarizing the two parts and using the fact that ∫u0Tu−αu≤Cu0T(1−α)+(1+log⁡T) _u_0^Tu^-α\,du≤ C_u_0T^(1-α)_+(1+ T) with a constant Cu0C_u_0 depending only on u0u_0, we obtain that ∑k=1∞⁡[min⁡T,H⁡(Xk)]≤C3a−2T(1−1/(1+γ)λ2)+(1+log⁡T) _k=1^∞E[ \T,H(X_k)\]≤ C_3a^-2T^(1-1/\(1+γ)λ^2\)_+(1+ T) for a constant C3C_3 depending on Λ and γ. Finally, because Λ is a fixed compact interval, we can choose γ to be positive and small so that (1−1(1+γ)λ2)+≤(1−λ−2)++η/2(1- 1(1+γ)λ^2)_+≤(1-λ^-2)_++η/2 holds uniformly for all λ∈Λλ∈ . We absorb 1+log⁡T1+ T into Tη/2T^η/2 and adjust the constant C3C_3 properly to obtain (83). ∎ Lemma 18. Let At(θ)t≥1\A_t(θ)\_t≥ 1 and Ξi(t,θ)i∈o,s,t≥3\ _i(t;θ)\_i∈\o,s\,t≥ 3 denote the actions and posterior samples from deploying the TS(θ)(θ) algorithm in any two-armed bandit, with two arms labeled as o and s. For k≥1k≥ 1, let Y¯o,k Y_o,k denote the empirical mean of the first k observed rewards from arm o. Fix any b∈ℝb and let pk(θ):=Φ⁡((Y¯o,k−b)k/θ)p_k(θ):= (( Y_o,k-b) k/θ ) denote the conditional probability that a posterior sample for arm o exceeds b after k pulls. Then ⁡[∑t=3T⁡At(θ)=s,Ξs(t,θ)≤b]≤∑k=1T−1⁡[min⁡T,1−pk(θ)pk(θ)].E [ _t=3^T \A_t(θ)=s,\ _s(t;θ)≤ b\ ]≤ _k=1^T-1E [ \T, 1-p_k(θ)p_k(θ) \ ]. (84) Proof of Lemma 18. Conditional on the previous history ℋt−1H_t-1, the two current posterior samples Ξs(t,θ) _s(t;θ) and Ξo(t,θ) _o(t;θ) are independent. Define pt:=pNo(t−1,θ)(θ)p_t:=p_N_o(t-1;θ)(θ), qt:=ℙ⁡(Ξs(t,θ)≤b∣ℋt−1)q_t:=P( _s(t;θ)≤ b _t-1), then we have ℙ⁡(At(θ)=s,Ξs(t,θ)≤b∣ℋt−1) P(A_t(θ)=s, _s(t;θ)≤ b _t-1) ≤qt(1−pt), ≤ q_t(1-p_t), ℙ⁡(At(θ)=o∣ℋt−1) P(A_t(θ)=o _t-1) ≥qtpt. ≥ q_tp_t. Thus, ℙ⁡(At(θ)=s,Ξs(t,θ)≤b∣ℋt−1)≤1−ptptℙ(At(θ)=o∣ℋt−1).P(A_t(θ)=s, _s(t;θ)≤ b _t-1)≤ 1-p_tp_tP(A_t(θ)=o _t-1). For k=1,…,T−1k=1,…,T-1, let It,k:=No(t−1;θ)=k,Rk(θ):=1−pk(θ)pk(θ).I_t,k:= \N_o(t-1;θ)=k\, R_k(θ):= 1-p_k(θ)p_k(θ). Then on the event No(t−1;θ)=k\N_o(t-1;θ)=k\, we have pt=pk(θ)p_t=p_k(θ). Moreover, we have ∑t=3TIt,kAt(θ)=o≤1, _t=3^TI_t,k \A_t(θ)=o\≤ 1, since selecting arm o when its pre-pull count is k increases that count to k+1k+1. Now consider the case Rk(θ)≤T\R_k(θ)≤ T\. From the tower property and previous bounds, we have [∑t=3TIt,kAt(θ)=s,Ξs(t;θ)≤bRk(θ)≤T] [ _t=3^TI_t,k \A_t(θ)=s, _s(t;θ)≤ b\ \R_k(θ)≤ T\ ] ≤ ≤ [Rk(θ)Rk(θ)≤T∑t=3TIt,kAt(θ)=o] [R_k(θ) \R_k(θ)≤ T\ _t=3^TI_t,k \A_t(θ)=o\ ] ≤ ≤ [Rk(θ)Rk(θ)≤T]. [R_k(θ) \R_k(θ)≤ T\ ]. On Rk(θ)>T\R_k(θ)>T\, since the number of relevant rounds is trivially at most T, we have [∑t=3TIt,kAt(θ)=s,Ξs(t;θ)≤bRk(θ)>T]≤Tℙ(Rk(θ)>T).E [ _t=3^TI_t,k \A_t(θ)=s, _s(t;θ)≤ b\ \R_k(θ)>T\ ]≤ TP(R_k(θ)>T). Summarizing the above two cases, we deduce that ⁡[∑t=3TIt,k⁡At(θ)=s,Ξs(t,θ)≤b]≤⁡[min⁡T,Rk(θ)].E [ _t=3^TI_t,k \A_t(θ)=s, _s(t;θ)≤ b\ ] [ \T,R_k(θ) \ ]. Finally, because ∑t=3T⁡At(θ)=s,Ξs(t,θ)≤b=∑k=1T−1∑t=3TIt,k⁡At(θ)=s,Ξs(t,θ)≤b, _t=3^T \A_t(θ)=s, _s(t;θ)≤ b\= _k=1^T-1 _t=3^TI_t,k \A_t(θ)=s, _s(t;θ)≤ b\, so taking a sum of the previous bound over k=1,…,T−1k=1,…,T-1 proves (84). ∎ Appendix F Ensembles induce a curvature correction Proposition 4 (Ensembles induce a curvature correction). Suppose λ↦JT(πθ,Mλ)λ J_T( _θ,M_λ) is twice continuously differentiable and its Hessian is L-Lipschitz, i.e., ‖∇λ2JT(πθ,Mλ)−∇λ2JT(πθ,Mλ′)‖op≤L‖λ−λ′‖2\| _λ^2J_T( _θ,M_λ)- _λ^2J_T( _θ,M_λ )\|_op≤ L\|λ-λ \|_2 for all λ,λ′λ,λ , where ∥⋅∥op\|·\|_op is the operator norm. Then |⁡[JT(πθ,Mλ^+ϵ(i))∣off]−JT(πθ,Mλ^)−12Tr(∇λ2JT(πθ,Mλ^)Σ)|≤L6[‖ϵ(i)‖23∣off]. |E [J_T( _θ,M_ λ+ε^(i)) _off ]-J_T( _θ,M_ λ)- 12 Tr ( _λ^2J_T( _θ,M_ λ) ) |≤ L6\,E [\|ε^(i)\|_2^3 _off ]. Proof of Proposition 4. Let E(i):=JT(πθ,Mλ^+ϵ(i))−JT(πθ,Mλ^)−∇λJT(πθ,Mλ^)⊤ϵ(i)−12(ϵ(i))⊤∇λ2JT(πθ,Mλ^)ϵ(i). E^(i):=J_T( _θ,M_ λ+ε^(i))-J_T( _θ,M_ λ)- _λJ_T( _θ,M_ λ) ε^(i)- 12(ε^(i)) _λ^2J_T( _θ,M_ λ)ε^(i). Since the Hessian of JT(πθ,Mλ)J_T( _θ,M_λ) is L-Lipschitz, by Lemma 1 of Nesterov and Polyak (2006), |E(i)|≤L6‖ϵ(i)‖23. |E^(i)|≤ L6\|ε^(i)\|_2^3. Since ⁡[‖ϵ(i)‖23∣off]<∞E[\|ε^(i)\|_2^3 _off]<∞ by assumption, |∇λJT(πθ,Mλ^)⊤ϵ(i)|≤‖∇λJT(πθ,Mλ^)‖2‖ϵ(i)‖2| _λJ_T( _θ,M_ λ) ε^(i)|≤\| _λJ_T( _θ,M_ λ)\|_2\|ε^(i)\|_2 and |(ϵ(i))⊤∇λ2JT(πθ,Mλ^)ϵ(i)|≤‖∇λ2JT(πθ,Mλ^)‖op‖ϵ(i)‖22|(ε^(i)) _λ^2J_T( _θ,M_ λ)ε^(i)|≤\| _λ^2J_T( _θ,M_ λ)\|_op\|ε^(i)\|_2^2, so we may take the following conditional expectations: ⁡[JT(πθ,Mλ^+ϵ(i))∣off]=JT(πθ,Mλ^)+12Tr(∇λ2JT(πθ,Mλ^)Σ)+⁡[E(i)∣off]. [J_T( _θ,M_ λ+ε^(i)) _ off ]=J_T( _θ,M_ λ)+ 12 Tr ( _λ^2J_T ( _θ,M_ λ ) )+E [E^(i) _off ]. where we use that • ⁡[∇λJT(πθ,Mλ^)⊤ϵ(i)∣off]=∇λJT(πθ,Mλ^)⊤[ϵ(i)∣off]=0E[ _λJ_T( _θ,M_ λ) ε^(i) _off]= _λJ_T( _θ,M_ λ) E[ε^(i) _off]=0 • ⁡[(ϵ(i))⊤∇λ2JT(πθ,Mλ^)ϵ(i)∣off]=⁡[Tr(∇λ2JT(πθ,Mλ^)ϵ(i)(ϵ(i))⊤)∣off]=Tr(⁡[∇λ2JT(πθ,Mλ^)ϵ(i)(ϵ(i))⊤∣off])=Tr(∇λ2JT(πθ,Mλ^)Σ)E [(ε^(i)) _λ^2J_T( _θ,M_ λ)ε^(i) _off ]=E [ Tr ( _λ^2J_T( _θ,M_ λ)ε^(i)(ε^(i)) ) _off ]= Tr (E [ _λ^2J_T( _θ,M_ λ)ε^(i)(ε^(i)) _off ] )= Tr ( _λ^2J_T( _θ,M_ λ) ) Thus, we have that |⁡[JT(πθ,Mλ^+ϵ(i))∣off]−JT(πθ,Mλ^)−12Tr(∇λ2JT(πθ,Mλ^)Σ)| |E [J_T( _θ,M_ λ+ε^(i)) _off ]-J_T( _θ,M_ λ)- 12 Tr ( _λ^2J_T( _θ,M_ λ) ) | =|⁡[E(i)∣off]|≤⁡[|E(i)|∣off]≤L6[‖ϵ(i)‖23∣off]. = |E[E^(i) _off] | [|E^(i)| _off ]≤ L6E [\|ε^(i)\|_2^3 _off ]. ∎

Instant research discovery