Frequency-Uniform Log-Regret Reinforcement Learning for Diffusions

Jose Blanchet; Lutong Hao; Renyuan Xu

math.OCOct 27, 2026

Frequency-Uniform Log-Regret Reinforcement Learning for Diffusions

Authors: Jose Blanchet, Lutong Hao, Renyuan Xu

Organizations: Department of Management Science and Engineering, Stanford University.

Abstract

High-frequency control problems are often studied through time discretization, but refining the timestep $δ$ increases the discrete horizon $H=T/δ$ 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 $δ$ . 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 $δ$ .

Figures & tables

Figure 1: Mean deployed-policy gap against the true-model optimum after

n

training episodes, in the model with two branch points. Each curve averages 64 independent runs at resolution

H=1/\delta

; shading gives pointwise 95% percentile bootstrap intervals from 2,000 resamples of complete runs. The gray dashed line is an

n^{-1}

rate reference.

Figure 2: Experiment 1(a): cumulative regret after the 64 exploration episodes, at fixed physical horizon $T=5$ . Lines are seed means; shading gives 95% intervals. Each timestep uses its own matched Euler reference. Dashed line segments are linear fits in $\log_{2}K$ over the last 5 values of $K=1024,\ldots,16384$ .

$\delta$	$H$	$R_{2048}-R_{64}$	Terminal gap
0.200	25	$7.64\ [4.06,11.22]$	$0.001183\ [0.000507,0.001858]$
0.100	50	$8.36\ [5.06,11.67]$	$0.000851\ [0.000645,0.001057]$
0.050	100	$7.37\ [4.75,9.99]$	$0.000644\ [0.000380,0.000908]$
0.025	200	$6.82\ [4.20,9.45]$	$0.000824\ [0.000510,0.001139]$

Table 1: Experiment 1(b): timestep refinement at

T=5

and

K=2048

. The terminal gap evaluates the recommendation fitted after episode 2048; cumulative regret includes only deployed policies.

$\delta$	CD-FQ (ours)	DW without replay	DW + replay	Online little- $q$ native Gibbs	Batch little- $q$ greedy
0.200	$0.21\;[0.11,0.30]$	$162\;[139,185]$	$44.2\;[39.5,49.0]$	$43.3\;[43.1,43.5]$	$25.9\;[22.5,29.2]$
0.100	$0.17\;[0.12,0.23]$	$196\;[181,212]$	$62.0\;[54.0,70.0]$	$46.1\;[45.9,46.3]$	$24.1\;[21.8,26.3]$
0.050	$0.18\;[0.14,0.23]$	$224\;[216,232]$	$89.6\;[78.0,101]$	$47.7\;[47.6,47.9]$	$24.8\;[22.9,26.6]$
0.025	$0.12\;[0.08,0.16]$	$233\;[226,241]$	$129\;[118,139]$	$48.5\;[48.3,48.6]$	$23.7\;[21.7,25.6]$

Table 2: Experiment 2(a): percentage terminal value gaps after

K=512

episodes. Each method entry is

100

times the mean paired-simulation gap divided by the deterministic Euler reference cost

V_{\delta}^{\rm grid}

; both endpoints of its marginal 95% interval across 15 training seeds are scaled by the same factor. All method entries are percentages; comparator entries are rounded to three significant digits. Absolute gaps and reference costs appear in Table 7 in Appendix E.6 .

$\delta$	$n$	CD-FQ (ours)	DW without replay	DW + replay	Batch little- $q$ greedy
0.200	100	$0.0049\;[0.0036,0.0063]$	$2.31\;[1.97,2.64]$	$0.596\;[0.531,0.662]$	$0.349\;[0.304,0.394]$
	400	$0.0040\;[0.0027,0.0053]$	$2.29\;[1.96,2.62]$	$0.608\;[0.543,0.673]$	$0.357\;[0.310,0.404]$
	1600	$0.0038\;[0.0024,0.0052]$	$2.28\;[1.95,2.61]$	$0.614\;[0.550,0.677]$	$0.360\;[0.312,0.408]$
0.100	100	$0.0039\;[0.0032,0.0045]$	$2.75\;[2.52,2.97]$	$0.844\;[0.733,0.956]$	$0.320\;[0.291,0.349]$
	400	$0.0030\;[0.0024,0.0035]$	$2.72\;[2.50,2.95]$	$0.846\;[0.736,0.956]$	$0.324\;[0.295,0.354]$
	1600	$0.0028\;[0.0021,0.0035]$	$2.71\;[2.49,2.94]$	$0.847\;[0.737,0.956]$	$0.326\;[0.296,0.356]$

Table 3: Experiment 2(b): physical-cost gaps of policies frozen after 512 Euler episodes over the matched fixed-stage queue reference. Entries give means and marginal 95% intervals across 15 training seeds; comparator entries are rounded to three significant digits. Batch little-

q

uses greedy extraction. Online little-

q

is omitted because its terminal deployed policy remains effectively unchanged from initialization; see Appendix E.6 . Reference costs range from

1.337

1.392

Method	Scaled mean wait	Delay probability	Effort	Physical cost
CD-FQ (ours)	$0.165$ – $0.189$	$0.264$ – $0.280$	$0.511$ – $0.538$	$1.340$ – $1.396$
DW without replay	$0.106$ – $0.148$	$0.162$ – $0.209$	$2.992$ – $3.989$	$3.672$ – $4.532$
DW + replay	$0.145$ – $0.284$	$0.209$ – $0.340$	$0.651$ – $2.378$	$1.978$ – $3.106$
Online little- $q$ , native Gibbs	$0.322$ – $0.339$	$0.336$ – $0.346$	$0.409$	$1.970$ – $2.007$
Batch little- $q$ , greedy	$0.199$ – $0.258$	$0.283$ – $0.320$	$0.533$ – $0.683$	$1.651$ – $1.752$

Table 4: Experiment 2(b): customer-level outcomes after 512 Euler training episodes. Entries are ranges of point estimates over the 12

(\delta,n)

cells, not uncertainty intervals. Waits and delay probabilities are pooled customer ratios; effort is integrated over

[0,T]

; physical cost is from uniformization. Figure 4 gives per-cell operational means and intervals.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Mean cumulative regret through

K

executed episodes in the model with two branch points, including the 16 exploration episodes. Each curve averages 64 independent runs at resolution

H=1/\delta

; shading gives pointwise 95% percentile bootstrap intervals from 2,000 resamples of complete runs.

Steps $H$	Exploration regret (16 episodes)	Mean learning regret	95% interval	Total regret
4	0.01356	0.01399	$[0.01163,\,0.01678]$	0.02755
8	0.01524	0.01360	$[0.01125,\,0.01621]$	0.02884
16	0.01611	0.01429	$[0.01207,\,0.01676]$	0.03040
32	0.01656	0.01679	$[0.01348,\,0.02090]$	0.03335
64	0.01678	0.01445	$[0.01202,\,0.01748]$	0.03124

Appendix

Table 5: Final cumulative regret at

K=8192

. Exploration regret is deterministic; learning regret is reported as its mean and 95% percentile bootstrap interval from 64 independent runs and 2,000 complete-run resamples per resolution. Totals may differ from component sums due to rounding.

$\delta$	$H$	$R_{16384}-R_{64}$ , mean [pointwise 95% CI]
0.200	25	10.503 [7.580, 13.426]
0.100	50	10.653 [8.127, 13.179]
0.050	100	8.622 [5.264, 11.980]

Appendix

Table 6: Experiment 1(a): cumulative regret after exploration at

K=16384

. Intervals are pointwise 95% Student-

t

intervals across eight training seeds.

$\delta$	Reference cost $V_{\delta}^{\rm grid}$	CD-FQ (ours)	DW source style	DW + replay	Online little- $q$ native Gibbs	Batch little- $q$ greedy
0.200	$1.408281$	$0.0029\;[0.0016,0.0043]$	$2.28\;[1.96,2.60]$	$0.623\;[0.556,0.690]$	$0.610\;[0.607,0.613]$	$0.364\;[0.317,0.411]$
0.100	$1.378613$	$0.0024\;[0.0017,0.0032]$	$2.71\;[2.49,2.92]$	$0.855\;[0.744,0.965]$	$0.636\;[0.633,0.639]$	$0.332\;[0.301,0.362]$
0.050	$1.363004$	$0.0025\;[0.0019,0.0031]$	$3.05\;[2.94,3.16]$	$1.22\;[1.06,1.38]$	$0.651\;[0.649,0.652]$	$0.338\;[0.313,0.363]$
0.025	$1.355958$	$0.0017\;[0.0011,0.0022]$	$3.16\;[3.06,3.27]$	$1.74\;[1.60,1.89]$	$0.658\;[0.655,0.660]$	$0.321\;[0.295,0.348]$

Appendix

Table 7: Experiment 2(a): terminal value gaps after

K=512

episodes. Method entries give the mean and its marginal 95% Student-

t

confidence interval across 15 training seeds; comparator entries are rounded to three significant digits. The reference-cost column gives the deterministic Euler Bellman-grid value

V_{\delta}^{\rm grid}

. Calculations use the unrounded source estimates.

$\delta$	CD-FQ	DW (source style)	DW + replay	Online little- $q$	Batch little- $q$
0.200	$10.04\;[-7.03,27.12]$	$1263.89\;[1186.36,1341.42]$	$477.32\;[449.72,504.91]$	$301.06\;[275.36,326.76]$	$293.42\;[272.29,314.55]$
0.100	$15.12\;[-4.18,34.43]$	$1367.83\;[1280.00,1455.67]$	$705.24\;[643.89,766.60]$	$321.53\;[293.12,349.94]$	$294.66\;[268.41,320.91]$
0.050	$19.46\;[7.96,30.96]$	$1469.01\;[1433.00,1505.02]$	$958.45\;[910.29,1006.61]$	$338.93\;[321.11,356.75]$	$297.07\;[285.21,308.92]$
0.025	$18.29\;[4.68,31.90]$	$1490.74\;[1422.62,1558.86]$	$1171.23\;[1137.89,1204.58]$	$341.55\;[318.67,364.42]$	$294.25\;[271.24,317.26]$

Appendix

Table 8: Experiment 2(a): realized post-exploration excess

\widehat{R}_{512}-\widehat{R}_{32}

over episodes 33–512. Entries are means and 95% Student-

t

intervals across the same 15 seeds as Table 7 . Both little-

q

columns describe native Gibbs data collection.

$\delta$	CD-FQ	DW (without replay)	DW + replay	Online little- $q$ native Gibbs	Batch little- $q$ native Gibbs
0.200	$91.24\;[74.93,107.54]$	$1345.08\;[1266.14,1424.03]$	$558.51\;[530.46,586.56]$	$382.26\;[357.34,407.17]$	$374.61\;[353.45,395.78]$
0.100	$97.02\;[77.64,116.40]$	$1449.73\;[1362.83,1536.63]$	$787.13\;[725.44,848.83]$	$403.42\;[374.79,432.05]$	$376.55\;[349.92,403.19]$
0.050	$101.54\;[89.52,113.56]$	$1551.09\;[1515.42,1586.75]$	$1040.53\;[990.44,1090.62]$	$421.01\;[402.69,439.32]$	$379.14\;[367.09,391.20]$
0.025	$101.93\;[86.92,116.95]$	$1574.38\;[1506.64,1642.13]$	$1254.88\;[1218.90,1290.85]$	$425.19\;[401.62,448.77]$	$377.89\;[354.35,401.44]$

Appendix

Table 9: Experiment 2(a): realized cumulative excess at

K=512

, including the common 32 exploration episodes. Entries give means and marginal 95% Student-

t

confidence intervals across training seeds, including trajectory and action-sampling variation. Both little-

q

arms collect data with Gibbs policies.

Figure 4: Experiment 2(b): service and effort after

K=512

Euler training episodes and

n_{0}=32

common exploration episodes. The five frozen policies are CD-FQ with zero coefficient ridge, source-style DW, DW + replay, online little-

q

native Gibbs, and batch little-

q

greedy, all on their training decision clocks. Columns are queue sizes; rows show scaled mean wait, delay probability, and effort cost (log scale). Points are pooled customer ratios or seed means; bars are pointwise 95% intervals using 15 seed clusters and 16,384 paths per policy/seed.

Notation	Meaning	Reference
Sampling, model, and coverage
$T$ , $\delta$ , $H$ ; $n$ , $d$ , $p$	Physical horizon, timestep, stages $H=T/\delta$ ; state, action, and drift-parameter dimensions.	Sections 2 and A.4
$K$ , $n_{0}$ , $n_{j}$ ; $J_{K}$ , $\bar{J}_{K}$	Episode budget, exploration count, and observed episodes $n_{j}=2^{j}n_{0}$ before epoch $j$ ; last epoch index and epoch-count bound.	( 25 ), ( 26 )
$\Phi_{\mu}$ , $\theta^{\star}$ , $B_{\theta}$	Known drift features, unknown parameter, and its norm bound.	Assumption A.4
$B_{\Phi_{\mu}}$ , $L_{\Phi_{\mu},s}$ , $L_{\mu,s}$	Feature magnitude and derivative bounds; drift-derivative bounds $L_{\mu,s}=B_{\theta}L_{\Phi_{\mu},s}$ .	Assumptions A.4 and 3.1
$\Sigma^{\star}$ , $\lambda_{0}$ , $\Lambda_{0}$ , $\mathcal{S}_{0}$	True covariance, known lower and upper eigenvalue bounds, and admissible covariance set.	Assumption A.4 ; ( 36 )

Appendix

Table 10: Notation and constants for Sections 3 and 4 . References point to definitions or the corresponding bounds.

Regret Minimization in RL

Regret minimization in reinforcement learning develops agents that learn effective policies while limiting cumulative loss against an optimal benchmark.

See all 60 papers

Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
Sep 19, 2026Kenny Guo, Valentio Iverson, Sahan Wijetunga +1Markov Decision Processes Continuous-Time RL
Department of Economics, Yale University, New Haven, Connecticut, USA · Department of Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA · Department of Mathematics, University of California, Los Angeles, Los Angeles, California, USA
Adaptive Partitioning and Learning for Stochastic Control of Diffusion Processes
Dec 17, 2025Hanqing Jin, Renyuan Xu, Yanzhao YangRL Control Reinforcement Learning
Mathematical Institute, University of Oxford · Department of Management Science and Engineering, Stanford University
Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment
Jul 31, 2026Yanwei Jia, Du OuyangMulti-Armed Bandits Regret Minimization in RL
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong SAR · Department of Mathematical Sciences, Tsinghua University, Beijing, Beijing 100084, China

Sep 19, 2026J/K move · Enter open · S save

Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs

Kenny Guo, Valentio Iverson, Sahan Wijetunga, William Chang

Department of Economics, Yale University, New Haven, Connecticut, USA · Department of Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA · Department of Mathematics, University of California, Los Angeles, Los Angeles, California, USA

Markov Decision Processes Continuous-Time RL Regret Minimization in RL Model-Based RL Q-Learning

Open paper AskPDF arXiv

Many real-world reinforcement learning (RL) problems evolve in continuous time, where decisions occur at irregular, event-driven intervals rather than at fixed discrete steps. We study episodic continuous-time Markov Decision Processes (MDPs) in which decision epochs are governed by a homogeneous Poisson process and the reward and transition dynamics vary smoothly over time. We consider both a fixed number of jumps per episode and a fixed time budget with a random number of Poisson decision epochs. Under a Lipschitz continuity assumption in time, we exploit local smoothness through discretization and extend both UCRL (Auer and Ortner 2006) and Q-learning (Jin et al. 2018) to this setting, proving

\widetilde{O}(T^{2/3})

regret bounds for both model-based and model-free algorithms. Finally, we establish matching

\widetildeΩ(T^{2/3})

minimax lower bounds, showing that the rate is optimal up to logarithmic factors. These results provide the first tight regret guarantees for Lipschitz-smooth continuous-time episodic MDPs with Poisson decision epochs.

Abstract

Regret Minimization in RL

Explore similar work

Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs

Adaptive Partitioning and Learning for Stochastic Control of Diffusion Processes

Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment