PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data

Yang Peng

arXiv:2609.38880v2stat.MLcs.LG

TL;DR

Asynchronous TD from a single Markov trajectory faces uneven state coverage and dependent updates. The paper analyzes importance-weighted updates using reverse-time and hitting-time arguments. The last iterate attains a cubic-horizon statistical rate with an additive reverse hitting-time cost, with matching lower bounds up to logarithmic factors.

  • Problem

    Single-trajectory TD updates are dependent and visit states unevenly, while existing guarantees leave a factor-H gap from the synchronous statistical rate.

    Source: §1 · p. 2

  • Method

    The analysis separates stochastic fluctuations from initialization error using reverse-time Poisson control and compensation of successive hitting costs.

    Source: §9 · p. 35

  • Results

    The last iterate achieves eO(ϱH^3/(µminε^2) + h⋆) transitions, and the lower bound matches both terms up to logarithmic factors on the stated parameter classes.

    Source: §1 · p. 3, §9 · p. 35

  • Takeaways & Limitations

    The framework extends the rate to affine prediction updates, including successor features and generalized value predictions, and supports simultaneous mean and variance estimation.

    Source: §1 · p. 3, §9 · p. 35

    The behavior state chain must be finite and irreducible, although periodic chains are allowed and the target chain need not be irreducible.

    Source: §1 · p. 2

Abstract

from arXiv · show

We study the last iterate of standard importance-weighted temporal-difference (TD) learning from a single trajectory of a finite Markov decision process. The trajectory follows a behavior policy $b$ with an irreducible, possibly periodic state chain; a target policy $\pi$ covered by $b$ is evaluated with action importance ratios bounded by $\varrho$. Write $H=(1-\gamma)^{-1}$, with $\mu_{\min}$ the minimum stationary probability and $\mathfrak h_\star$ the largest expected hitting time of the reverse behavior state chain. We prove that the last iterate achieves sup-norm error at most $\varepsilon$ with high probability after $\widetilde O(\varrho H^3/(\mu_{\min}\varepsilon^2)+\mathfrak h_\star)$ transitions for $0<\varepsilon\le1$. The statistical term retains the cubic effective-horizon dependence of synchronous TD, while the initialization cost is additive in $\mathfrak h_\star$. Setting $b=\pi$ and $\varrho=1$ recovers the on-policy rate. For aperiodic behavior chains, $\mathfrak h_\star=\widetilde O(t_{\rm mix}/\mu_{\min})$ recovers a mixing-time bound. The proof combines an anchored local Poisson equation in reverse time to control fluctuations without a mixing-time factor, a compensation argument for successive hitting costs, and an expected cumulative propagation mass bound for decreasing step sizes. Given the policy ratios and their bound, an empirical state-count rule attains the same rate without prior knowledge of model parameters. The framework covers nonnegative affine importance-weighted prediction updates, including successor features, transition-dependent discounting, and coupled finite-mode predictions. A perturbation estimate yields a time-uniform guarantee for online return-variance estimation. A three-state, two-action construction gives matching minimax lower bounds for both terms up to logarithmic factors on the considered parameter classes.

1 Introduction

The paper studies off-policy evaluation from a single behavior-policy trajectory, where uneven state visitation and dependent updates complicate finite-sample analysis. It establishes near-minimax guarantees for asynchronous TD and extends the analysis to affine prediction updates and return-variance estimation.

1 Introduction

  • Single-trajectory analysis must account for uneven state visitation and dependent updates, while existing guarantees use minimum stationary probability and mixing time.In the off-policy setting, these chain parameters refer to the behavior policy, and the action importance ratios are bounded by ϱ.Source: §1 · pp. 1–2

1.1 Related work

  • Earlier asynchronous bounds left a factor-H gap from the synchronous statistical rate, while a variance-reduced guarantee incurred an additive mixing-time transient.The paper contrasts its ordinary TD recursion with that variance-reduced result and gives a mixing-time consequence without the extra effective-horizon factor.Source: §1 · p. 2, §1.1 · p. 3

1.2 Contributions

  • The matching lower bounds apply to both the statistical and hitting-time terms on the parameter classes specified in Theorem 8.3.Corollary 8.4 gives the corresponding mixing-time minimax lower bound.Source: §1 · p. 3, §1.2 · p. 4
  • The last iterate retains a cubic statistical term while its initialization cost is additive in the reverse-chain hitting time; matching lower bounds hold up to logarithmic factors.The guarantees cover constant and decreasing step sizes, with the decreasing-step guarantee holding simultaneously beyond a transient threshold.Source: §1 · p. 3, §1.2 · p. 4
  • The transfer framework covers importance-weighted nonnegative affine prediction updates, including successor features, transition-dependent discounts, and finite prediction modes.A perturbation estimate also gives a time-uniform guarantee for joint online estimation of return mean and variance.Source: §1 · p. 3, §1.2 · p. 5

2 Problem Formulation

The formulation evaluates a target policy using a trajectory generated by a behavior policy, then tracks how asynchronous updates propagate estimation error. Its assumptions permit periodic irreducible behavior chains and dependent reward-transition outcomes.

2.1 Markov decision process and policies

  • The behavior-policy trajectory is time-homogeneous, with action, reward, and next-state outcomes governed by the behavior policy and reward-transition kernel.The reward and next state may be dependent given the current state and action.Source: §2.1 · p. 5
  • Action coverage requires every target-policy action to have positive behavior-policy probability, and the importance ratio is bounded by ϱ.The target transition matrix is formed by weighting behavior transitions by the action ratio.Source: §2.1 · p. 5
  • Rewards lie in [0,1], γ is in (0,1), and the initial estimate is bounded between zero and H; the initial state distribution is arbitrary.The target value is defined by the target-policy process and lies between zero and H entrywise.Source: §2.1 · p. 5

2.2 State chain, hitting times, and mixing

  • The behavior state chain is finite and irreducible, with positive minimum stationary mass; it may be periodic, and the target chain need not be irreducible.The analysis uses the largest expected hitting time of the reverse behavior chain; for an aperiodic chain, hitting-time bounds yield mixing-time bounds.Source: §2.2 · p. 6
  • Augmenting inventory state with the phase of an m-period demand cycle gives a time-homogeneous periodic chain, for which mixing time is infinite but reverse hitting time is finite.The hitting-time guarantee applies to the observed seasonal-system trajectory, including evaluation of other replenishment policies covered by the behavior policy.Source: §2.2 · pp. 6–7

2.3 Asynchronous TD learning and error propagation

  • Importance-weighted asynchronous TD changes only the currently visited coordinate, and the action ratio multiplies the entire temporal-difference error.The method permits constant steps or a nonincreasing schedule with eventual rate log(t)/t; a data-driven rule uses observed state counts without prior model parameters.Source: §2.3 · p. 7
  • The weighted Bellman innovation is centered under the behavior trajectory, but its propagation coefficient depends on future observations, motivating reverse-time analysis.Subtracting the true value yields an exact decomposition into remaining initial error and accumulated transition and reward noise through the same random matrices.Source: §2.3 · p. 7

3 Main Results

The main results separate statistical error from initialization cost, with an additive reverse hitting-time term. Constant and decreasing step sizes provide guarantees, and the decreasing schedule is time-uniform.

3 Main Results

  • The guarantees separate a cubic statistical term from an additive reverse hitting-time cost.The results cover constant and decreasing step sizes; lower bounds match both terms up to logarithmic factors on the specified parameter classes.Source: §3 · p. 8, §3.2 · p. 10

3.1 Constant step size

  • For each fixed terminal time T ≥ T⋆, the constant-step iterates satisfy a high-probability error guarantee, with the transition-count terms corresponding to fluctuations and initialization.The initialization threshold uses a block decomposition that is part of the proof, not the TD algorithm.Source: §3.1 · p. 8
  • In the on-policy case, the bound improves the statistical dependence from H^4 to H^3 and removes a factor of H from the mixing transient.The comparison is to the one-action specialization of Li et al. (2024, Theorem 4).Source: §3.1 · p. 8
  • As ξ ↓ 0, the two-state example has bounded sufficient transition count despite diverging mixing time; at ξ = 0, the chain alternates deterministically and h⋆ = 1.This illustrates why the hitting-time bound can remain useful for nearly periodic chains.Source: §3.1 · p. 9

3.2 Step sizes decreasing at rate log(t)/t

  • The decreasing schedule depends on H, d, ϱ, and µmin, while an empirical state-count rule can choose step sizes without prior knowledge of µmin.The empirical rule uses observed frequencies to set a step size at the start of each doubling epoch.Source: §3.2 · pp. 9–10
  • The log(t)/t schedule gives a time-uniform guarantee: with high probability, all iterates after a sufficient transition count have sup-norm error at most ε.Its guarantee matches the constant-step sample complexity up to logarithmic factors; for aperiodic chains it also yields a mixing-time bound.Source: §3.2 · pp. 9–10

4 A Framework for Affine Prediction

The framework transfers TD-style guarantees to importance-weighted affine prediction updates along a Markov trajectory. It separates propagation from stochastic noise and preserves the physical-chain hitting-time analysis.

4 A Framework for Affine Prediction

  • The framework covers importance-weighted affine prediction updates, including standard off-policy TD as a scalar special case.The updates use nonnegative transport matrices with row sums at most γ, and all prediction components at a visited state are updated together.Source: §4 · p. 10, §4.1 · p. 11

4.1 Affine prediction along a Markov trajectory

  • Under the marked-kernel assumptions, the transfer theorem gives constant-step, decreasing-step, and empirical-occupancy guarantees for the affine prediction error.The results hold under every initial distribution of the physical state chain.Source: §4.1 · p. 11
  • The number m of prediction components enters the sufficient transition count only logarithmically, while coverage and reverse hitting times refer to the physical state chain.The bound replaces d with dm in logarithmic terms; empirical state counts are still computed over the d physical states.Source: §4.1 · p. 11

4.2 Noise and propagation as separate inputs

  • The proof separates initial-table memory from a stochastic convolution, then uses reverse-time predictability and an anchored local Poisson equation to control noise.Scalar propagation dominates block propagation on every realized trajectory, so the physical-chain hitting-time analysis applies to block updates.Source: §4.2 · pp. 11–12

5 Reverse-Time Analysis

The reverse-time analysis separates stochastic fluctuations from initialization error while tracking the propagation mass that connects updates across a trajectory. Anchored Poisson corrections, variance certificates, and concentration bounds support the transfer theorem.

5.1 Reverse transport and its mass budget

  • Reverse transport yields a predictable, nonnegative propagation vector for analyzing how updates move across the trajectory.The analysis uses the reversed marked path and deterministic steps ordered by reversal.Source: §5.1 · pp. 12–13

5.2 An anchored correction for centered edge observables

  • The anchored local Poisson correction keeps its range within a single source-component innovation, rather than introducing a generic hitting-time range.It produces a reverse martingale correction with bounded increments.Source: §5.2 · pp. 13–14

5.3 A variance certificate from auxiliary routing

  • Auxiliary routing represents affine predictions as discounted returns, yielding a variance certificate for their importance-weighted innovations.The routed return lies in [0, H], and its conditional variance supplies the certificate.Source: §5.3 · pp. 14–15

5.4 Weighted energy and reverse variance compensation

  • The weighted-energy bound combines the variance certificate with reverse variance compensation, uniformly over initial pairs and interval lengths.For block prediction, the certificate uses V = ϱH^2 and bosc = ϱH.Source: §5.4 · pp. 15–16

5.5 Concentration on an arbitrary deterministic interval

  • The interval-concentration result applies to arbitrary initial state distributions and uses the variance certificate to control the stochastic convolution.The scalar TD convolution is treated as a specialization of the generic bound.Source: §5.5 · p. 17

5.6 Proof of the transfer theorem

  • The transfer-theorem proof combines concentration and forgetting bounds for constant steps, decreasing steps, and empirical-occupancy guarantees.The empirical rule selects steps from state counts, with the marked future conditionally following the same kernel at epoch boundaries.Source: §5.6 · p. 18

6 Forgetting the Initialization

Initialization error is analyzed through an auxiliary particle whose survival represents propagation mass. Compensation of successive reverse hitting costs bounds its lifetime and yields uniform forgetting guarantees.

6 Forgetting the Initialization

  • The initialization cost includes the worst-case reverse-chain hitting time additively.The hitting-cost compensation uses a potential difference so successive relocation costs can cancel.Source: §6 · p. 18, §6.1 · pp. 19–20

6.1 Hitting times and a compensation identity

  • The compensation identity expresses average relocation costs through a potential difference and a return-time term, without requiring the target chain to be irreducible.The weighted consequence uses coverage and the importance-ratio bound.Source: §6.1 · pp. 19–20

6.2 An auxiliary particle and its expected lifetime

  • Conditional on the marked driver path, the particle's surviving mass equals the propagation-vector mass; its expected lifetime is uniformly bounded under ηϱH ≤ 1/4.A potential in the lifetime argument avoids an additional horizon factor on the hitting-time cost.Source: §6.2 · pp. 20–22

6.3 From lifetime to uniform forgetting

  • The initialization propagator is uniformly small for every T beyond the stated threshold, giving a simultaneous guarantee for bounded initial errors.The result uses contraction after a single fixed-time bound rather than a union bound over later times.Source: §6.3 · pp. 22–23
  • For aperiodic behavior chains, the additive initialization cost is of order eO(H/(ηµmin) + tmix/µmin), while the hitting-time bound can be smaller on some chains.The argument uses forward mixing directly and does not require an equality or comparison between forward and reverse total-variation mixing times.Source: §6.3 · pp. 23–24

7 Extensions

The affine framework extends trajectory-based prediction to multiple quantities and prediction modes while retaining guarantees on the physical behavior chain. It also supports online return-variance estimation.

7 Extensions

  • The affine framework covers multiple predictions updated from shared transitions under a finite irreducible behavior chain, including periodic chains.Observed marks and the next state have a fixed conditional Markov kernel.Source: §7 · p. 24

7.1 Successor features and simultaneous reward evaluation

  • Successor features yield simultaneous value guarantees for reward weights selected after observing the trajectory.The number of prediction coordinates enters the sample bound only logarithmically when all coordinates are updated at each visited state.Source: §7.1 · p. 25

7.2 Generalized value predictions and finite modes

  • Generalized value predictions allow transition-dependent continuation factors, including predictions that stop at a specified state set while the physical chain continues.The continuation-factor law need not be known for the step-size schedules.Source: §7.2 · pp. 25–26
  • Finite-mode predictions switch coordinates according to observed marks without changing physical dynamics or requiring an irreducible joint state–mode process.The number of modes enters the transition count only through logarithms.Source: §7.2 · p. 26
  • The framework also covers importance-weighted SARSA on an irreducible state–action support, with the corresponding stationary coverage and reverse hitting-time parameters.When b = π, the update is the usual on-policy SARSA update.Source: §7.2 · p. 26

7.3 Online estimation of the return variance

  • A perturbation argument yields a time-uniform guarantee for online return-variance estimation alongside the mean estimate.The second-moment recursion uses the learned mean, and the analysis controls its difference from an oracle recursion.Source: §7.3 · pp. 27–28

8 Lower Bounds and the Scope of Optimality

The section establishes coverage and statistical lower bounds for trajectory-based value estimation, including a joint construction with known rewards. It then shows these bounds match the learning rates under hitting-time and mixing-time budgets, up to logarithmic factors.

8 Lower Bounds and the Scope of Optimality

  • The lower bounds apply to every estimator based on the full trajectory, including randomized estimators, and the joint construction allows the estimator to know the reward function.The two-state example isolates the case where the reward at a rare state is unknown until that state is visited.Source: §8 · p. 28, §8.2 · p. 31

8.1 A two-state coverage obstruction

  • Even when the trajectory starts in stationarity, the two-state coverage obstruction persists; for TD, the rare-state coordinate can remain unchanged until that state is visited.The direct TD lower bound holds with zero rewards and initialization V0 = H1.Source: §8.1 · p. 29

8.2 A joint lower bound with known rewards

  • The three-state construction makes both lower-bound terms necessary with fixed, known policies and rewards, varying only transitions.Rare-state entrance controls coverage, while transitions within the rare-state set control statistical difficulty.Source: §8.2 · pp. 29, 32
  • The joint construction fixes H, ϱ, and µ_min while keeping the orders of h⋆ and t_mix controlled uniformly across the family.The behavior chains in the family are irreducible, aperiodic, and reversible.Source: §8.2 · p. 30

8.3 Minimax optimality under hitting-time and mixing-time budgets

  • Under a mixing-time budget, the same family supplies a matching lower bound, while importance-weighted last-iterate TD attains the corresponding upper bound up to logarithmic factors.The stated class assumes either t ≥ 16H or ϱ ≥ 2 and t ≥ 4.Source: §8.3 · p. 34
  • When ϱ = 1, the construction reduces to the on-policy case; its minimax orders also hold with stationary initialization in the stated confidence range.The stationary-initialization result is stated for δ ≤ 1/8; the on-policy lower bounds apply in the ranges h ≥ 8H/p and t ≥ 16H.Source: §8.3 · p. 34

9 Discussion

The discussion connects last-iterate TD guarantees to minimax lower bounds and extends the reverse-time analysis to broader prediction updates. The appendices establish the reverse marked-process law and supply tools for concentration, hitting-time identities, and mixing bounds.

9 Discussion

  • Importance-weighted asynchronous TD achieves sup-norm error ε with high probability in Õ(ϱH^3/(µ_minε^2) + h⋆) transitions, with minimax matching up to logarithms on the stated classes.The result allows periodic behavior chains; the affine-update framework also covers successor features and generalized value predictions.Source: §9 · p. 35

A.1 The stationary reverse marked law

  • The stationary reverse marked law conditions the next reverse edge and its mark on the current reverse state, even given the full reverse history.The reverse transition matrix is P⋆(x,y) = µ(y)P(y,x)/µ(x).Source: §A.1 · p. 38

B.1 A discrete exponential-moment lemma

  • The discrete Khasminskii bound turns a uniform expectation bound for a nonnegative additive functional into an exponential-moment bound.Markov’s inequality then yields a tail bound.Source: §B.1 · pp. 39–40

B.2 A scalar martingale tail bound

  • The scalar Freedman bound makes explicit the probability cost of controlling a random predictable quadratic variation.It is stated for bounded real martingale differences.Source: §B.2 · p. 40

C Hitting-Time Identities and Mixing Amplification

  • The hitting-time and forward-mixing arguments concern the behavior state chain, allow reward-transition dependence, and do not require reversibility.The appendix proves the identities used in the main text.Source: C Hitting-Time Identities and Mixing… · p. 41

C.1 Return excursions and their last predecessor

  • Return-excursion occupation counts establish the stationary distribution and relate expected return times to its state probabilities.The excursion includes its initial state and excludes the returning state.Source: §C.1 · pp. 41–42

C.2 Time reversal of hitting means

  • The time-reversal argument derives the hitting-mean reversal identity from a finite matrix identity and a boundary-value calculation.The proof includes the case i = j.Source: §C.2 · pp. 42–43

C.3 Amplifying forward mixing

  • Mixing amplification iterates the total-variation profile to bound convergence and control singleton probabilities.The bound follows from the profile’s submultiplicative property.Source: §C.3 · pp. 43–44

D Proof of the Constant-Step Theorem

The constant-step proof combines stochastic and initialization bounds, while the decreasing-step analysis handles deterministic nonincreasing schedules. Its reverse-time formulation supports interval-wise propagation and stochastic concentration estimates.

D Proof of the Constant-Step Theorem

  • For constant step sizes, the proof applies stochastic and initialization bounds on deterministic terminal intervals and combines their failure probabilities.For aperiodic behavior chains, the hitting-time bound is related to mixing time to recover the stated mixing-time rate.Source: D Proof of the Constant-Step Theorem · pp. 44–45

E Decreasing Step Sizes

  • For decreasing steps, the proof establishes interval estimates for any deterministic nonincreasing step sequence and controls initialization through reverse-mass compensation.The assumptions of the main results remain in force.Source: E Decreasing Step Sizes · p. 45

E.1 Reverse propagation on a deterministic interval

  • Unrolling the error recursion on a deterministic interval yields reverse propagation, with forward nonincreasing steps becoming reverse nondecreasing steps.The reverse update uses the marked trajectory and propagation weights.Source: §E.1 · p. 45

E.2 Stochastic concentration on an interval

  • The variable-step stochastic-convolution bound applies to deterministic nonincreasing steps and arbitrary initial distributions on the interval.Its stated step-size restriction is η_(T−1) ≤ ··· ≤ η_s ≤ (ϱH)^−1.Source: §E.2 · p. 46

E.3 Integrated reverse mass and initialization

The section bounds integrated reverse propagation mass to control initialization under changing step sizes. It uses an anchored potential and hitting-time compensation, and extends the forgetting estimate to higher powers.

E.3 Integrated reverse mass and initialization

  • The expected integrated reverse mass is bounded while retaining an additive reverse hitting-time contribution, giving a route to initialization control for varying steps.The proof uses an anchored potential and telescoping identities to bound contributions from the reverse weights.Source: §E.3 · pp. 46–48
  • The anchored potential is constructed from reverse hitting equations and a source-centered importance-weight observable.The potential’s range is bounded using the importance-ratio bound.Source: §E.3 · pp. 47–48
  • The decreasing-step forgetting proposition bounds propagation mass over blocks and extends the estimate to arbitrary initial distributions.The proof applies the expected-mass bound blockwise and uses a density comparison involving µ_min.Source: §E.3 · pp. 48–49
  • A higher-power forgetting corollary is available when pϱHη_s ≤ 1/2, using a scalar comparison with auxiliary propagation.The comparison preserves the original importance weights and marked kernel.Source: §E.3 · p. 49

E.4 Proof of Theorem 3.4

Theorem 3.4’s proof controls the last-iterate error by analyzing a suffix of the trajectory and bounding initialization, noise, and propagation contributions. The next section introduces empirical-occupancy step sizes for the case where the minimum stationary probability is unknown.

E.4 Proof of Theorem 3.4

  • The suffix analysis controls stochastic noise and propagation while preserving the update range [0, H]^d.The proof applies conditional probability bounds to the suffix and does not condition on the random estimate at the suffix start.Source: §E.4 · p. 51
  • The proof bounds three error contributions on a high-probability event, yielding the guarantee simultaneously for every target precision 0 < ε ≤ 1.It uses a suffix trajectory and a pathwise bound on the initialization error; the threshold makes each of the three terms at most ε/3.Source: §E.4 · p. 51

F TD Learning with Unknown Minimum Stationary Probability

F.1 An empirical-occupancy step-size rule

The rule estimates state occupancy from observed counts at doubling epochs and uses those estimates to set step sizes without μ_min as an input. A hitting-time argument controls the empirical occupancies, supporting the stated transition rate.

F.1 An empirical-occupancy step-size rule

  • At doubling epochs, the rule estimates occupancy from observed state counts and holds its step size constant within each epoch.It uses H, d, ϱ, and observed counts; once frequencies are within constant factors of stationary probabilities and the cap is inactive, steps have order H log(t)/(μ_min t).Source: §F.1 · p. 51
  • For sup-norm error ε, when ∥V_T − V^π∥∞ ≤ ε, the sufficient transition count is eO(ϱH^3/(μ_min ε^2) + h⋆).Source: §F.1 · p. 52
  • The guarantee depends on μ_min, h⋆, and δ, but none is an input to the step-size rule.Source: §F.1 · p. 52

F.2 Concentration of the empirical occupancies

  • For fixed state x, the cited tails combine to give 4e^(−n/(48F)) when n ≥ 2m; for n < 2m ≤ 2F, this bound exceeds one but remains valid.Here F = 1 + 2h⋆, and the return-time mean is m = 1/μ(x).Source: §F.2 · pp. 52–53

F.3 Proof of Theorem F.1

The proof analyzes eligible epochs, where empirical state frequencies are close to stationary probabilities, and combines epoch-wise noise and forgetting bounds. These controls yield a high-probability guarantee across terminal times.

F.3 Proof of Theorem F.1

  • Eligible epochs are those whose starting times meet deterministic analysis conditions, and their occupancy event places every state frequency within a factor of two of stationarity.The occupancy estimate makes the step-size cap inactive in an eligible epoch on that event.Source: §F.3 · p. 53
  • Conditioning on each epoch’s history permits noise bounds uniform over the epoch’s initial state and its fixed step size.A union bound combines occupancy, forgetting, and noise events into one event for all terminal times.Source: §F.3 · pp. 54–55
  • Completed-epoch forgetting and contraction over a partial current epoch bound the terminal iterate’s error.The proof combines the preceding epoch bound with noise terms and chooses constants so the resulting three terms are each at most ε/3.Source: §F.3 · p. 55

G Proof of the Return-Variance Guarantee

The return-variance guarantee transfers an oracle recursion’s analysis to the coupled mean-and-variance process using a pathwise perturbation bound. It combines the variance and mean guarantees on a shared high-probability event.

G Proof of the Return-Variance Guarantee

Related papers

Loading 2609.38880v2…