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

Sep 19, 2026

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

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.

Kenny Guo, Valentio Iverson, Sahan Wijetunga +1

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

Ask PDF

Dec 17, 2025

Adaptive Partitioning and Learning for Stochastic Control of Diffusion Processes

We study reinforcement learning for controlled diffusion processes with unbounded continuous state spaces, bounded continuous actions, and polynomially growing rewards: settings that arise naturally in finance, economics, and operations research. To overcome the challenges of continuous and high-dimensional domains, we introduce a model-based algorithm that adaptively partitions the joint state-action space. The algorithm maintains estimators of drift, volatility, and rewards within each partition, refining the discretization whenever estimation bias exceeds statistical confidence. This adaptive scheme balances exploration and approximation, enabling efficient learning in unbounded domains. Our analysis establishes regret bounds that depend on the problem horizon, state dimension, reward growth order, and a newly defined notion of zooming dimension tailored to unbounded diffusion processes. The bounds recover existing results for bounded settings as a special case, while extending theoretical guarantees to a broader class of diffusion-type problems. Finally, we validate the effectiveness of our approach through numerical experiments, including applications to high-dimensional problems such as multi-asset mean-variance portfolio selection.

Hanqing Jin, Renyuan Xu, Yanzhao Yang

Mathematical Institute, University of Oxford · Department of Management Science and Engineering, Stanford University

RL Control Reinforcement Learning Stochastic Optimal Control Model-Based RL

Ask PDF

Jul 31, 2026

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

This paper studies the policy gradient update for a multi-arm bandit problem in diffusion environment that is described by a stochastic differential equation (SDE) under the continuous-time reinforcement learning framework by Wang et al. (2020), Jia and Zhou (2022b). With the logit parameterization for the stochastic policy, we show that it converges almost surely to the optimal arm under an arbitrary constant learning rate. Furthermore, we derive the non-asymptotic regret upper bound when the constant learning rate is below a time-invariant threshold; and the regret bound has order

O(\log T)

. We improve the analysis in Lattimore (2026a) for the same SDE by constructing a novel Lyapunov function and demonstrate the transparency of analyzing policy gradient using the tools in SDEs. In addition, the same Lyapunov function is also helpful in analyzing the discrete-time policy gradient algorithm.

Yanwei Jia, Du Ouyang

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

Multi-Armed Bandits Regret Minimization in RL Continuous-Time RL Policy Gradient Methods Policy Learning

Ask PDF

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