PaperlayerView exact revision on arXiv

Source-linked AI summary

Frequency-Uniform Log-Regret Reinforcement Learning for Diffusions

Jose Blanchet, Lutong Hao, Renyuan Xu

arXiv:2610.36758v1math.OCcs.LG

TL;DR

At a fixed physical horizon, finer decision grids increase the stage count and can worsen standard regret guarantees. The paper frames episodic value-based learning for Euler models of controlled diffusions and studies bounds uniform in the timestep. In finite-queue experiments, CD-FQ has the smallest reported mean queue gap across the tested configurations.

  • Problem

    At fixed physical horizon, stage-polynomial regret bounds can worsen as timestep refinement increases the number of decision stages.

    Source: §1 · pp. 1–2

  • Method

    The paper formulates episodic learning over Euler models of controlled diffusions, separating episode count, physical horizon, and decision frequency while benchmarking against the corresponding Euler optimum.

    Source: §1.1 · p. 2

  • Results

    CD-FQ’s mean queue gap is 0.0018–0.0049, the smallest in all 12 tested configurations.

    Source: §5.2.5 · p. 33

  • Takeaways & Limitations

    The Euler-model benchmark separates statistical learning regret from continuous-time discretization error, while observation counts and computational effort can still grow as the grid is refined.

    Source: §1.1 · p. 2

    The exponential-coefficient sharpness result is not a minimax lower bound over learning algorithms, and its unbounded-drift example lies outside the localized model class in Section 3.

    Source: §2.2.2 · p. 12

Abstract

from arXiv · show

High-frequency control problems are often studied through time discretization, but refining the timestep $\delta$ increases the discrete horizon $H=T/\delta$ and can make standard finite-horizon regret guarantees deteriorate even when the physical horizon $T$ is fixed. We study episodic value-based reinforcement learning for Euler discretizations of controlled diffusions. The performance is measured as the cumulative regret over $K$ episodes relative to the optimal policy of the corresponding Euler model. Under stability and regularity conditions on value function gradients, Bellman residual derivatives, and fitted critics, we prove an $\mathcal{O}(\log K)$ regret bound with constants uniform in $\delta$. For dynamics with drift linear in unknown parameters and unknown constant diffusion covariance, we verify localized versions of these conditions for a constrained, model-based controlled-diffusion fitted-$Q$ algorithm (CD-FQ) and obtain high-probability $\mathcal{O}(\log K\log\log K)$ regret for fixed and finite $T$, again with constants uniform in $\delta$.

1 Introduction

Refining a time grid can increase the stage count—and worsen standard regret bounds—even when physical operating time stays fixed. The paper develops a value-based learning framework for controlled diffusions with regret guarantees uniform in the timestep, then positions it against related learning and discretization work.

1 Introduction

  • At fixed physical horizon, refining the timestep increases the stage count and can make stage-polynomial regret bounds grow, obscuring learning difficulty versus temporal resolution.For value-based learning, the one-step action signal also shrinks with the timestep while error must be controlled across T/δ stages.Source: §1 · pp. 1–2

1.1 Our work and contributions

  • The framework separates episode count, physical horizon, and decision frequency, and benchmarks regret against the corresponding Euler model rather than continuous-time discretization error.Statistical regret bounds at fixed physical horizon do not imply that observation counts or computational effort stay fixed as the grid is refined.Source: §1.1 · p. 2
  • Under quadratic advantage and value-gradient stability, Bellman-residual derivatives of order δ/k yield critic action-gradient errors of the same order and O(log K) regret with constants uniform in δ.The logarithmic-regret coefficient can grow exponentially in T for guarantees uniform over this general class.Source: §1.1 · p. 2
  • For drift linear in unknown parameters and unknown constant diffusion covariance, CD-FQ fits the model and constrained critics, then chooses greedy policies.Under regularity, exploration, approximation, and simulation-budget conditions, it obtains high-probability O(log K log log K) regret with constants uniform in δ; the analysis also establishes continued self-exploration.Source: §1.1 · pp. 2–3

1.2 Related work

  • The paper distinguishes online regret against an Euler-model optimum from related work on policy gaps, continuous-time learning mechanisms, and discrete-to-continuous approximation error.It studies deterministic greedy fitted-Q policies and verifies derivative accuracy for a learned parametric diffusion.Source: §1.2 · pp. 3–4

2 From Bellman residuals to logarithmic regret

This section develops a transfer from Bellman-residual derivative accuracy to logarithmic regret for the Euler model, combining optimal-benchmark inequalities, fitted-critic regularity, and residual control. Under conditions uniform in the timestep, the resulting bound is discretization-uniform at fixed physical horizon, with its coefficient controlled by remaining physical time.

2 From Bellman residuals to logarithmic regret

  • The Euler learning problem fixes physical horizon T, varies K and δ, and measures cumulative regret against the optimal policy of the corresponding Euler model.The drift and constant covariance are unknown, and admissible timesteps satisfy δ ≤ δmax and T/δ ∈ N.Source: §2 · pp. 4, 6

2.1.1 Optimal advantage performance difference

  • The optimal-advantage performance-difference identity expresses a policy’s suboptimality through its stagewise losses under that policy’s trajectory law, without requiring a selected optimal policy.This permits nonunique maximizing actions.Source: §2.1.1 · p. 6

2.1.2 Benchmark inequalities and quadratic policy loss

  • Quadratic advantage loss and value-gradient stability turn greedy-action gradient error into fast regret: an O(δ/k) residual-derivative rate yields logarithmic regret uniformly in δ.The recursion preserves the order of the gradient error; quadratic loss squares it at a 1/δ cost before summing over H = T/δ stages and K episodes.Source: §2.1.2 · pp. 6–7

2.2 Residual accuracy and regret transfer

  • Regret control reduces to bounding critic action-gradient errors at selected actions, which are transferred from true Bellman-residual derivatives using Euler structure and value-gradient stability.The backward transfer does not depend on how the fitted critics were constructed.Source: §2.2 · p. 8

2.2.1 Fitted critics and true residual certificates

  • Criterion 1 supplies fitted-envelope regularity, while Criterion 2a bounds state and action derivatives of the true residual at greedy actions with δ-independent radii.The derivative bounds scale linearly in δ, matching the Euler scaling used in the transfer.Source: §2.2.1 · pp. 8–9

2.2.2 Residual derivatives to regret transfer

  • Theorem 2.7 transfers residual-derivative bounds to regret by closing a backward value-gradient recursion and converting action-gradient error through the quadratic advantage bound.The transfer applies to arbitrary finite residual radii; the root-k rate yields the logarithmic regret guarantee.Source: §2.2.2 · p. 10
  • O(log K) regret holds uniformly over admissible timesteps δ for fixed T when fitted critics satisfy the stated regularity and root-k residual-accuracy conditions.Theorem 2.7 gives the transfer for finite residual radii; its rate condition is applied in the final step.Source: §2.2.2 · p. 10
  • The δ² factor cancels the 1/δ factor in the quadratic advantage bound and the stage count H = T/δ when summing losses over updates.The resulting cumulative bound is stated for arbitrary finite radii, with the initial episode bounded by 2BJ.Source: §2.2.2 · p. 12
  • The transfer proof uses both benchmark inequalities only at fitted greedy actions, where Section 3 establishes bin entry and backward transfer.On the full action set, the quadratic-advantage inequality implies that any action with dh(x, a) = 0 is optimal.Source: §2.2.2 · p. 12
  • O(T e^{2LE T} log K) regret is discretization-uniform for fixed T when the stated stability and residual constants are uniform in δ.The same bound extends to nonuniform grids with step sizes Δh ≤ δ.Source: §2.2.2 · p. 12
  • The exponential growth of the large-K logarithmic-regret coefficient is unavoidable under the general transfer conditions, but this is not a minimax lower bound over learning algorithms.The sharpness example uses unbounded drift and lies outside the localized model class in Section 3.Source: §2.2.2 · p. 12

3 Localized learning: algorithm and main result

This section develops localized regret analysis and the CD-FQ estimation scheme, using coarse residual control for bin entry and sharper within-bin control for local bounds; the bins are used only in the analysis. It gives high-probability logarithmic regret without polynomial dependence on $1/\delta$ at fixed physical horizon $T$.

3.1 Model assumptions and setup

  • The environment assumptions include Euler dynamics with drift linear in unknown bounded parameters, unknown constant covariance with known timestep-uniform bounds, and known smooth rewards.Assumptions A.4–A.6 restrict the environment, A.7, A.8, and A.10 are learner choices, and A.9 links them; the parametric dynamics and finite initial moment condition imply the stated regularity bounds.Source: §3.1 · p. 13, §3.1.1 · p. 13

3.1.1 Experiment, epochs, and the parametric model

  • After initial exploration, the learner doubles its episode count per epoch, fitting a policy from completed episodes and deploying it for the next epoch.The analysis fixes an admissible δ for each experiment; uniformity in δ applies to deterministic constants.Source: §3.1.1 · p. 13

3.1.2 Optimal-action sets and local bin geometry

  • Under Assumptions A.4–A.6, fitted greedy actions enter the union of optimal-action bins, where the benchmark inequalities hold with κ = L̄_xa/m̄.The local geometry also implies C1 regularity of the optimal critic and a common active state gradient continuous in the state and uniformly bounded in h and δ.Source: §3.1.2 · pp. 14–15

3.1.3 Coverage and self-exploration

  • A known exploration policy supplies drift-parameter coverage, while optimal policies are assumed to self-explore; learned policies need not be assumed to self-explore.Once fitted greedy policies enter a known-radius neighborhood of the optimal-action sets, that neighborhood inherits self-exploration uniformly over admissible timesteps.Source: §3.1.3 · pp. 15–16

3.1.4 Critic class and feasible envelopes

  • The affine critic separates order-one value levels from order-δ action differences, while its sieve level and coefficient dimension can increase with the episode count.At a fixed sieve level, its features do not scale with δ, supporting timestep-uniform regularity through the feasible critic class.Source: §3.1.4 · p. 16

3.1.5 Synthetic design and projected Bellman approximation

  • The two-scale Bellman approximation requires a coarse full-action residual bound below the entry margin and a sharper derivative bound on the optimal-action bins.The synthetic design is chosen predictably before fresh labels and can enforce a well-conditioned Gram matrix by construction, at no regret cost.Source: §3.1.5 · pp. 17–18

3.2 Estimation scheme and learning algorithm

  • At each epoch, CD-FQ checks empirical coverage, estimates dynamics from real transitions, fits critics backward using fresh synthetic Bellman targets, and deploys the greedy policy; if coverage fails, it explores instead.The estimator uses observed Euler state increments to estimate the drift parameter and projects the covariance estimate onto the prescribed covariance set.Source: §3.2 · pp. 18–19
  • CD-FQ fits critics backward using fresh conditionally independent synthetic labels after fixing the predictable design, without additional environment interaction for fitting.The design rows and fresh next-state draws form synthetic transitions; fitting adds no environment interaction.Source: §3.2 · p. 19
  • After exploration, the coverage check passes on the main high-probability event, without the learner knowing or testing bins, and any measurable greedy selection is covered.Entry and containment follow from the analysis.Source: §3.2 · p. 19

3.3 Two-scale residual control and main guarantee

  • The two-scale certificate uses a global action-derivative bound for bin entry and a local certificate restricted to optimal bins; the criterion does not require radius decay.The exploration threshold ensures empirical coverage and entry into the union of optimal bins, while the gradient-error coefficient controls action-gradient error at greedy actions; the threshold depends on K only through log log K factors.Source: §3.3 · p. 21
  • The Monte Carlo confidence level is absorbed into the simulation budget and does not enlarge the statistical regret numerator once that budget is imposed.The budgets limit Monte Carlo fitting error to O(δ/√nj) in both state and action derivatives.Source: §3.2 · p. 20, §3.3 · p. 21
  • O(log K) high-probability localized regret holds under the stated assumptions and doubling schedule, with no polynomial dependence on 1/δ at fixed T.The theorem requires K to exceed the exploration threshold; its implicit constant may depend on T, including exponentially through gradient propagation.Source: §3.3 · p. 22

4 Proof of the main theorem

The proof verifies fitted-critic regularity, establishes bin entry and local gradient control, and maintains coverage across fitted epochs. It then bounds and sums policy losses to obtain the fixed-horizon regret rate.

4.1 Verification of criteria on fitted critics

  • Every fit has a unique measurable coefficient minimizer and satisfies Criterion 1; coverage and sample thresholds enable verification of Criterion 2b with a δ-independent residual coefficient.Source: §4.1 · pp. 22–23

4.2 Bin entry and local gradient control

  • Under the stated criteria and margin conditions, backward transfer yields bin entry and local gradient control, with post-entry containment beyond a finite episode threshold independent of δ.Source: §4.2 · pp. 24–25

4.3 Coverage at every epoch

  • Exploration and fitted policies in the local neighborhood retain information, enabling empirical coverage at fitted epoch boundaries without exploration fallback.Source: §4.3 · pp. 25–26

4.4 Proof of the main theorem’s regret bound

  • Within entered bins, strong concavity and greedy stationarity bound one-policy loss by local action-gradient error; summing stage and epoch losses gives the regret bound.Source: §4.4 · p. 27
  • O(log K log log K) regret holds for fixed T and structural parameters, with bounds uniform in δ.Source: §4.4 · p. 27
  • The fixed-T rate’s coefficient can grow exponentially with T through backward gradient propagation, although the explicit horizon bound remains uniform in δ.Source: §4.4 · p. 28

5 Numerical experiments

This section examines CD-FQ in a model satisfying the theory’s assumptions and in a Halfin–Whitt queueing stress test, reporting regret across timestep refinements and benchmark types. The appendix establishes Euler-kernel derivative regularity and extends the bounds to nonuniform time grids.

5.1 Constructive verification: a model with two branch points

  • In the two-branch-point model, the construction satisfies Theorem 3.5’s assumptions, while the experiment’s deployed-policy gap decays approximately as n^-1 and final regret ranges from 0.0136 to 0.0168 across H.All pairwise bootstrap intervals contain zero; the model has multiple optimal actions, and every policy provides information about the unknown drift.Source: §5.1 · pp. 28–29, Figure 1 · p. 29

5.2.1 Experimental setup

  • The queueing experiments are a stress test beyond Theorem 3.5’s assumptions: the action set is a finite grid, qx+ is not C1, and the known drift term is unbounded and not C1.CD-FQ estimates the unknown queue parameters and diffusion variance, while retaining the known drift term; its constrained spline critics are fitted using fresh Gaussian next-state samples from the estimated model.Source: §5.2.1 · p. 30

5.2.2 Experiment 1(a): growth of cumulative regret

  • Cumulative regret grows near-logarithmically in episode count, and its fitted slopes per doubling—1.82, 1.68, and 1.41—do not increase as δ decreases.The last doubling adds 0.82, 1.00, and 0.97 times the previous increment; the observations are consistent with the O(log K log log K) bound with a δ-independent constant.Source: §5.2.2 · p. 30, Figure 2 · p. 31

5.2.3 Experiment 1(b): stability under timestep refinement

  • At T = 5 and K = 2048, cumulative regret and terminal policy gaps are comparable as δ decreases from 0.2 to 0.025, while decisions per episode rise from 25 to 200.Terminal gaps are 0.05–0.08% of reference cost; the 64 exploration episodes account for about 96% of cumulative regret, and the average later policy gap is 0.0034–0.0042.Source: §5.2.3 · p. 30, Table 1 · p. 31

5.2.4 Experiment 2(a): common-budget Euler learning

  • After K = 512 episodes, CD-FQ has the smallest terminal value gap, averaging 0.12–0.21% of reference cost across four timesteps, versus batch little-q’s 24–26% (125–195 times larger).This describes the finite-budget instantiation and its data-reuse choices, not the source paper’s general stability framework or conditional guarantee.Source: §5.2.4 · p. 32, Table 2 · p. 32

5.2.5 Experiment 2(b): transfer to finite queues

  • CD-FQ transfers best to finite queues, with mean queue gaps of 0.0018–0.0049, the smallest in all 12 configurations; batch little-q gaps are 0.314–0.360.CD-FQ’s gap decreases with server count; these point estimates are consistent with a residual Euler discretization effect but do not establish a convergence rate.Source: §5.2.5 · p. 33, Table 3 · p. 33
  • On transferred finite-queue policies, CD-FQ has the lowest physical cost throughout and balances congestion with effort: source-style DW uses 5.8–7.4 times its effort, while online little-q uses 20–24% less effort but roughly doubles scaled mean wait.These are frozen-policy transfer results; batch little-q has longer waits and higher delay probability in all 12 cells without saving effort.Source: §5.2.5 · p. 34, Table 4 · p. 34

A.4 Differentiation of the Euler kernel

  • Bounded value gradients ensure finite Euler-kernel expectations, while dominated convergence yields derivative formulas and their continuity under continuous drift Jacobians and value gradients.The argument uses directional difference quotients and applies dominated convergence again to the derivative formulas.Source: §A.4 · p. 38

A.5 Nonuniform time grids

  • Theorem 2.7’s bounds hold relative to the nonuniform grid’s Euler optimum with constants uniform over partitions, without a minimum step size, if residual derivative bounds scale with each step.The grid steps satisfy Δh ≤ δ and sum to T.Source: §A.5 · p. 39

A.6 Sharpness of exponential physical time dependence

The sharpness construction shows that uniform logarithmic-regret guarantees over the stated fitted-critic class can require exponential dependence on physical time. The accompanying reward-growth argument establishes integrability and continuity properties for the Euler model.

A.6 Sharpness of exponential physical time dependence

  • The threshold k0 may grow exponentially with T, while each episode’s loss remains at most mT/2 in the small-residual regime.The construction’s primitive constants are independent of T and δ, while BJ = mT/2.Source: §A.6 · pp. 39–40
  • M(T) ≥ B^T is necessary for bounds uniform in δ over fitted-critic sequences when κ = 0, but this is not a minimax lower bound for learning algorithms.The sharpness claim also does not establish the full exponent for κ > 0 or necessity of the extra factor T in the upper bound.Source: §A.6 · p. 40

A.7 Reward growth and moment bounds

  • The reward and drift growth bounds yield an integrable Euler weight and continuity of the transition expectation W dP⋆(· | x, a).The argument uses an integrable, locally uniform bound on W of the Euler draw.Source: §A.7 · p. 40

A.8 Optimal-envelope regularity and self-exploration

The appendix establishes regularity of the optimal value envelope and shows that policies near optimal actions retain information coverage. It also specifies the conditional histories and fresh randomness used in the later concentration arguments.

A.8 Optimal-envelope regularity and self-exploration

  • Backward induction establishes differentiability of the optimal value envelope, continuity of its gradient, and a gradient bound uniform in stage and timestep.The argument uses regularity of the Bellman recursion and the separated optimal branches to control the envelope locally.Source: §A.8 · p. 41
  • Policies within radius ϱ of optimal actions retain information coverage when ϱ is small enough, with constants independent of δ.The smallest eigenvalue bound is λminΓ(π) ≥ 4λloc − LΓϱ; choosing a radius with LΓϱcov ≤ 2λloc yields the stated coverage condition.Source: §A.8 · pp. 41–42

B.1 Filtrations and fresh randomness

  • Before each episode, the learner’s policy is fixed given its history, while the initial state and transition innovations are fresh; synthetic-fit draws are likewise conditionally independent after the fit design is fixed.The doubling endpoints are deterministic functions of (K, n0).Source: §B.1 · p. 42

B.2 Adaptive matrix coverage

The proofs use adaptive matrix concentration to obtain empirical information coverage at prescribed episode endpoints. They then transfer parameter and covariance estimation accuracy into kernel and derivative bounds uniform over timesteps.

B.2 Adaptive matrix coverage

  • At prescribed episode-count endpoints, matrix martingale concentration relates empirical information to its conditional population matrices, supporting coverage once deployed policies meet the population condition.The proof uses matrix Freedman concentration and a union bound over the eligible endpoints.Source: §B.2 · pp. 42–43

B.3 Model estimation and kernel derivative transfer

  • Kernel and derivative errors transfer uniformly over 0 < δ ≤ δmax and apply to adaptive fitted continuations under the stated gradient and Lipschitz bounds.The same event works for every continuation v satisfying the specified envelope bounds.Source: §B.3 · pp. 44–46
  • On covered epochs, the model estimates the drift parameter and diffusion covariance with bounds holding simultaneously across epochs.The constants depend on model bounds and the coverage level.Source: §B.3 · pp. 44–45

B.4 Conditional Monte Carlo fits

Conditional Monte Carlo fitting controls critic error across the fits actually performed by the algorithm. Combining those fitting bounds with model-transfer bounds verifies two-scale residual control with coefficients independent of the timestep.

B.4 Conditional Monte Carlo fits

  • After the dimension and confidence factor is absorbed by the simulation budget, the fitting coefficients are independent of epoch, stage, timestep, episode budget, and confidence level.The fitting event holds simultaneously for all epoch-stage fits performed by the algorithm.Source: §B.4 · p. 46
  • Fresh stage labels are sampled after the fit design is fixed, enabling conditional concentration bounds that are combined with approximation bounds for the fitted critic.The noiseless projection’s variational inequality makes the approximation-residual contribution nonpositive in the comparison with the noisy fit.Source: §B.4 · pp. 46–47

B.5 Verification of two-scale residual control and event assembly

  • Model-transfer and fitting bounds verify Criterion 2b, with resulting residual coefficients independent of epoch, stage, and δ.The event probability is assembled by a union bound over the relevant events.Source: §B.5 · p. 47

C Detailed proofs and calibration for the main theorem

Appendix C supplies proof details for fitted-envelope regularity, local error transfer, and exploration thresholds; Appendix D verifies the two-branch controlled example under timestep-uniform constants.

C.1 Verification of fitted-envelope regularity

  • A common active-state gradient makes each fitted value envelope C1 with bounded gradient, while the class condition bounds its gradient’s Lipschitz constant and yields a measurable greedy selector.The constrained least-squares fit is unique and measurable, so fitted coefficients compose with the selector to give a Borel greedy policy.Source: §C.1 · pp. 47–48

C.3 Entry and exploration thresholds; C.6 Coverage and entry at all fitted epochs

  • Once sample-count thresholds are met, coverage, bin entry, and proximity to the local-policy class persist at fitted epochs.The overall threshold combines model-sample, entry/proximity, and coverage requirements.Source: §C.3 · p. 50, §C.6 · p. 51

C.2 Backward bin entry and local transfer; C.4 Local one-episode policy loss

  • Backward bin entry transfers local residual bounds to fitted greedy actions, yielding the local one-episode policy-loss bound after summing over stages.The comparison uses strong concavity within a bin containing an optimal branch point.Source: §C.2 · p. 49, §C.4 · p. 50

C.5 Size of the fixed-horizon constants

  • For fixed T, the calibrated bounds retain timestep-uniform orders, but structural multipliers may depend on T, so uniformity in δ does not give a uniform or polynomial bound in T.The appendix exposes continuation, entry, and exploration factors behind the fixed-horizon orders.Source: §C.5 · pp. 50–51

D.1 Feasible critics and envelope regularity

  • Feasible critics in the example have a unique interior maximizer, with the implicit function theorem providing envelope regularity despite the absence of global action concavity.The maximizer lies in [1/4, 7/4].Source: §D.1 · p. 52

D.2 Bin geometry and exploration

  • The two-branch example has exactly one optimal branch point per bin and verifies exploration through a coverage check that always passes.The optimal action magnitude depends nontrivially on the unknown drift parameter.Source: §D.2 · p. 53

D.3 Synthetic design and projected approximation

  • The synthetic design uses repeated tensor anchors and a projected approximation whose error decays exponentially with sieve level, establishing the example’s critic approximation condition.The approximation is shape-feasible when ε_L(δ) ≤ δ/100.Source: §D.3 · pp. 53–54

D.4 Budgets and completion of the verification

  • The example verifies the theorem’s structural and normalized-error assumptions with constants independent of δ, while its construction assumes exact constrained regression and effective-action maximization.The implementation approximates these operations using fixed sieves and numerical constraint checks.Source: §D.4 · p. 55

D.5 Numerical details and supplementary results

This appendix reports the two-branch example’s implementation and supplementary queue experiments, including their modeling scope, estimation procedure, and computational settings.

D.5 Numerical details and supplementary results

  • The two-branch implementation uses 128 periodic state points and 16 Fourier modes, and every fitted critic passed its numerical feasibility checks.Figure 3 reports mean cumulative regret and Table 5 its decomposition at K = 8192, but the supplied passages give no table values.Source: §D.5 · p. 55, Figure 3 · p. 55, Table 5 · p. 56

E.1 Queue scaling and experimental scope

  • The queue experiments use a diffusion limit with drift −β + μx− − κa and infinitesimal variance 2μ, then transfer learned policies to finite queues.These experiments use nonsmooth coefficients and a finite action grid, so they do not verify the theorem’s smoothness and approximation hypotheses.Source: §E.1 · p. 56

E.2 Estimation, critic, and computational budgets

  • The queue learner estimates drift parameters by radially projected regression and clips a residual-based diffusion variance estimate before simulating synthetic Bellman successors.The variance estimate is the second moment of residual increments divided by δ, clipped to [0.25, 8].Source: §E.2 · p. 56
  • Spline critics use constrained coefficients, with ridge regularization varying by experiment; the synthetic work per fit grows about 64-fold under the eightfold timestep refinement.At the terminal fit in Experiment 1(b), H = 50 gives N = 630 and M = 1050, or about 3.3 × 10^7 synthetic draws.Source: §E.2 · pp. 56–57
  • Saved coverage checks pass in both studies, and fitted policies are held between scheduled refits.Experiment 2(a) uses a shared 32-episode exploration prefix; the terminal fit is used only for evaluation.Source: §E.2 · p. 57

E.3 Euler reference and evaluation protocol

The evaluation protocol compares learned policies with a numerical Euler reference and reports uncertainty across training seeds. The appendix also presents descriptive cumulative-regret growth fits and cautions against interpreting them as a rate test.

E.3 Euler reference and evaluation protocol

  • The numerical reference uses a state grid and nine-action grid, so it is not a certified optimum over continuous states and actions.A resolution check supports the reported gap scale but does not certify reference errors uniformly in δ.Source: §E.3 · p. 57
  • Policy gaps use 32,768 paired evaluation paths, while cumulative training costs are evaluated differently across Experiments 1 and 2.The reported intervals use independent training seeds as replicates and are marginal, unadjusted for multiple comparisons; they do not propagate reference-solver bias.Source: §E.3 · pp. 57–58

E.4 Growth fits and endpoint uncertainty

  • The fitted cumulative-regret slopes per doubling were 1.82, 1.68, and 1.41 for δ = 0.2, 0.1, and 0.05, respectively.The fits are descriptive because cumulative measurements are dependent, and overlapping endpoint intervals do not establish that smaller timesteps improve performance.Source: §E.4 · p. 58
  • Table 6 reports cumulative regret after exploration at K = 16,384, with pointwise 95% Student-t intervals across eight training seeds.The supplied table passage gives its scope and interval construction, not the table’s cell values.Source: Table 6 · p. 58

E.5 Comparison-method implementations

The comparison-method appendix specifies each learner’s fitting data, policy deployment, and refit schedule, distinguishing model-free fitted-Q baselines from little-q variants.

Comparison-method implementations

  • The four baselines share Experiment 2(a)’s observation format and action grid, and their terminal policies are frozen for queue transfer.The supplied passages specify these shared conditions but do not report comparative outcomes.Source: §E.5 · p. 58

Source-style DW; DW + replay

  • Source-style DW fits a backward cost target using real Euler successors and newest-epoch data, while its replay variant pools all episodes without action mixing.Both use deterministic greedy deployment; source-style DW estimates no transition model or synthetic successors.Source: §E.5 · p. 58

Online little-q

  • Online little-q updates value and action-score parameters after every episode, including exploration, and deploys its native Gibbs policy between refits.Its greedy policy is a secondary output; both policies are evaluated under unregularized cost.Source: §E.5 · pp. 58–59

Batch little-q

  • Batch little-q pools episodes by solving discretized martingale orthogonality conditions, using a behavior-policy instrument fixed by the data.Damped Newton refits deploy the native Gibbs policy between scheduled fits.Source: §E.5 · p. 59
  • Batch little-q’s parameters are selected on separate development data and then fixed for the reported runs.The specified settings are ν = 0.2 and ρ = 10^-5.Source: §E.5 · p. 59

E.6 Comparison diagnostics and realized training excess

The diagnostics compare learned policies’ terminal gaps, coverage, convergence, and computational costs, while the realized-excess analysis distinguishes observed regret from benchmark and sampling variation.

Online little-q diagnostics

  • Online little-q’s greedy terminal policy selects action zero at every timestep, while its sampled mean action stays near 0.2840, the zero-score Gibbs policy’s mean.Euler gaps range from 1.0813 to 1.1652; comparisons with greedy methods also include entropy-induced randomization cost.Source: §E.6 · p. 59

DW coverage

  • Replay improves DW’s mean gap at every timestep, but later refits remain rank one for source-style DW and replay’s benefit depends on data reuse and coverage.Both variants have first-stage rank three at the initial fit; replay preserves that rank later, though the fixed initial state prevents full rank in the 33-dimensional feature space.Source: §E.6 · p. 60

Batch little-q diagnostics

  • Batch little-q’s mean terminal gaps are 0.5267–0.5414 for native Gibbs policies and 0.3211–0.3642 after greedy extraction.Of 300 fits, 196 meet the stopping rule and 104 do not; all prespecified runs remain in the reported estimates.Source: §E.6 · p. 60

Computational cost

  • Learning wall times span 8.78–708.17 seconds for CD-FQ, 0.96–7.87 for source-style DW, 0.97–7.80 for DW + replay, 2.97–21.64 for online little-q, and 80.25–175.27 for batch little-q.Timings were collected under potentially different machine loads and do not establish an equal-computation or simultaneous speed comparison.Source: §E.6 · p. 60

Realized training excess

  • CD-FQ’s post-exploration mean is 10.04–19.46, with intervals crossing zero at the two coarser timesteps; replay lowers DW’s mean at each timestep.Replay’s mean rises from 477.32 to 1171.23 under refinement.Source: §E.6 · p. 60
  • Realized excess is reported both after exploration over episodes 33–512 and at K = 512 including the common 32 exploration episodes.The random policy-dependent benchmark gap need not be unbiased conditional on the full adaptive policy sequence, and trajectory and action-sampling variation can obscure logarithmic growth in individual runs.Source: §E.6 · pp. 60–61, Table 8 · p. 61, Table 9 · p. 61

E.7 Finite-queue transfer evaluation

The finite-queue evaluation compares frozen policies through customer-level outcomes and effort across queue sizes and timesteps. It uses event-driven paths and paired seed-cluster uncertainty estimates.

Evaluation procedure

  • Frozen policies are evaluated by uniformization; online little-q costs average stage costs and transitions under Gibbs probabilities while sampled actions are held for each stage.The reference and policy costs are numerical quantities subject to truncation, while Table 3 intervals use 15 training seeds without Monte Carlo evaluation error.Source: §E.7 · pp. 61–62

Customer-level evaluation

  • Customer outcomes use admitted arrivals before T, full FCFS waits including zeros, and action zero drains the admitted cohort after arrivals stop at T.Intervals use a seed-cluster delta method with t14 across 15 clusters, preserving within-seed covariance; customers are not independent training replicates.Source: §E.7 · p. 62
  • Figure 4 compares five frozen policies across queue sizes using scaled mean wait, delay probability, and log-scale effort cost, with pointwise 95% intervals across 15 seed clusters.Each policy and seed uses 16,384 paths.Source: Figure 4 · p. 62

Finite-queue outcomes

  • The largest pooled blocking-probability estimate is 6.46×10^-5, and sampled customer-level costs agree with uniformization within a maximum absolute standardized discrepancy of 3.20.Batch little-q’s paired effort intervals relative to CD-FQ cross zero at δ = 0.2; operational intervals are marginal and unadjusted.Source: §E.7 · p. 62

F Notation and constants for localized learning

Table 10 organizes the notation and constants used in Sections 3 and 4, including localized bounds, estimation events, and conditions on timestep uniformity.

Notation and constants

  • The symbols glob, loc, and ent denote the full action set, optimal-bin union, and bin entry, respectively; residual and action-gradient radii are normalized by δ.Timestep uniformity is for fixed T, with events defined separately for each fixed-δ experiment.Source: F Notation and constants for localized… · p. 63
  • Table 10 is a notation index for Sections 3 and 4, with references directing readers to definitions or the corresponding bounds.Its labels cover derivatives, residuals, critic and value errors, exploration thresholds, events, and fitting quantities.Source: Table 10 · p. 63, F Notation and constants for localized… · p. 64

Localized bounds

  • The notation distinguishes global and local residual-derivative radii, with local bounds holding on U⋆; global action bounds also include the bin-entry term.Critic and value errors transfer backward, with terminal value error set to zero.Source: F Notation and constants for localized… · p. 64

Exploration thresholds and events

  • The listed success events cover drift-score and covariance-noise deviations, simultaneous Monte Carlo fitting, and transfer from population to empirical coverage.Their intersections support the coverage–entry induction, while n⋆ collects thresholds for model estimation, entry, proximity, and coverage.Source: F Notation and constants for localized… · p. 64

Coefficient dependence

  • The residual and gradient error coefficients depend on K and ρ through ℓmdl when other stated parameters are fixed, not uniformly over those parameters.The notation table also lists design-size and Monte Carlo fitting coefficients.Source: F Notation and constants for localized… · p. 64
Loading 2610.36758v1…