Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimation

## Abstract

Abstract Continuous-time reinforcement learning (CTRL) provides a natural framework for sequential decision-making in dynamic environments where interactions evolve continuously over time. While CTRL has shown growing empirical success, its ability to adapt to varying levels of problem difficulty remains poorly understood. In this work, we investigate the instance-dependent behavior of CTRL and introduce a simple, model-based algorithm built on maximum likelihood estimation (MLE) with a general function approximator. Unlike existing approaches that estimate system dynamics directly, our method estimates the state marginal density to guide learning. We establish instance-dependent performance guarantees by deriving a regret bound that scales with the total reward variance and measurement resolution. Notably, the regret becomes independent of the specific measurement strategy when the observation frequency adapts appropriately to the problem’s complexity. To further improve performance, our algorithm incorporates a randomized measurement schedule that enhances sample efficiency without increasing measurement cost. These results highlight a new direction for designing CTRL algorithms that automatically adjust their learning behavior based on the underlying difficulty of the environment.

## 1 Introduction

Many real-world systems—such as autonomous robots, financial markets, and medical interventions—evolve in continuous time, where actions and feedback unfold without discrete intervals. This motivates the study of continuous-time reinforcement learning (CTRL), a framework where the agent learns to interact with a dynamic environment in real time to maximize cumulative reward. Unlike its discrete-time counterpart, CTRL is grounded in the natural temporal structure of many applications, making it particularly well-suited for control in physical and continuous systems. Recent work has highlighted its empirical potential, drawing on tools from continuous control theory (Greydanus et al., 2019; Yildiz et al., 2021; Lutter et al., 2021; Treven et al., 2024a) and the emerging use of diffusion-based models (Yoon et al., 2024; Xie et al., 2023). These developments underscore CTRL’s growing relevance and its advantage in capturing fine-grained interactions that discrete-time methods often approximate only coarsely.

In this paper, we focus on the adaptivity of CTRL—that is, the ability of a learning algorithm to adjust its behavior and complexity in response to the difficulty of the problem instance. Intuitively, simpler environments should require less exploration and faster convergence, while more complex dynamics or reward structures may demand prolonged learning and finer control. For example, in robotic manipulation, navigating an open space may require significantly less precision and feedback sensitivity compared to threading a needle or interacting with deformable objects. Despite its importance, adaptivity remains largely underexplored in the CTRL literature: existing methods often lack theoretical guarantees or empirical mechanisms to modulate learning effort according to task complexity. This motivates our first core question:

Can we design a CTRL algorithm that is provably adaptive to problem difficulty, offering instance-dependent performance guarantees?

A natural starting point to investigate adaptivity in CTRL is to approximate the continuous-time process using discrete-time reinforcement learning with equidistant measurement spaced observations. This allows us to draw from a rich body of work on adaptivity in discrete-time RL, where regret bounds and learning dynamics have been thoroughly analyzed (Zhao et al., 2023; Zhou et al., 2023; Wang et al., 2024b, a). However, equidistant measurement imposes a fixed temporal structure that may be ill-suited for many continuous-time environments. For tasks characterized by unevenly evolving system dynamics—such as sudden shifts in patient vital signs or abrupt state transitions in mechanical systems—uniform sampling might either overlook important events or waste resources on redundant observations. This rigidity limits the ability of CTRL to adapt its learning to the underlying complexity of the environment. Consequently, a key question arises:

How does the choice of measurement strategy in CTRL influence its ability to adapt across problem instances?

In this work, we aim to address the two core questions outlined above. Our main contributions are summarized as follows.

Figure: Figure 1: We depict the state trajectory $x_{n}(t)$ over $t\in[0,T]$ in episode $n$, with $x_{n}(0)=x_{\text{ini}}$ and $x_{n}(T)$ at the endpoints. Observation times $t_{n}^{k}$ are marked by black dots. Each measurement interval $\Delta_{n,k}=t_{n}^{k+1}-t_{n}^{k}$ is overlaid by a brown rectangle of width $\Delta_{n,k}$ and height proportional to $\Delta_{n,k}$, so that its area encodes $\Delta_{n,k}^{2}$ in our regret bound. The green shading illustrates the total variance $\operatorname{{\rm Var}}^{u_{n}}$. Proper measurement gap should be selected in accordance with policy variance $\operatorname{{\rm Var}}^{u_{n}}$ to achieve an optimal instance-dependent performance.
Refer to caption: demo_alt.png

- •
We introduce a conceptually simple model-based algorithm for CTRL, termed CT-MLE (Continuous-Time Reinforcement Learning with Maximum Likelihood Estimation). Unlike previous methods that estimate the underlying system dynamics directly (Treven et al., 2024a; Zhao et al., 2025), CT-MLE instead estimates the marginal state density using maximum likelihood estimation (MLE) with a general function approximator (e.g., neural networks or kernel models). This shift—from modeling dynamics to modeling marginal distributions—offers greater modeling flexibility and improved sample efficiency in practice. Additionally, CT-MLE is modular and compatible with a broad range of policy classes and sampling strategies, making it applicable to a wide variety of CTRL settings.
- •
From a theoretical perspective, we establish a regret bound for CT-MLE over the first $N$ episodes of interaction. Specifically, we show that the regret satisfies
$d^{2}+d\sqrt{\sum_{n=1}^{N}\sum_{k=0}^{m_{n}-1}\Delta_{n,k}^{2}+\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}},$
where $d$ denotes the complexity of the function class used for marginal density estimation, $m_{n}$ represents the number of measurements in episode $n$, $\Delta_{n,k}$ represents the $k$-th measurement gap in episode $n$, and $\operatorname{{\rm Var}}^{u_{n}}$ quantifies the total variance of the integrated reward under policy $u_{n}$. A central insight of our analysis is that when the measurement schedule is adapted to the problem instance—i.e., when $\sum_{k=0}^{m_{n}-1}\Delta_{n,k}^{2}$ is chosen in accordance with $\operatorname{{\rm Var}}^{u_{n}}$—the regret becomes primarily dependent on the reward variance and is nearly independent of the measurement schedule itself. This instance-dependent property highlights a key distinction from traditional discrete-time reinforcement learning, where measurements are typically uniform and agnostic to problem complexity. Figure [1](https://arxiv.org/html/2508.02103v1#S1.F1) provides a demonstration of this phenomenon. Our results underscore the importance of adaptive measurement strategies for achieving instance-optimal performance in the continuous-time setting.
- •
A core technical innovation in CT-MLE is its Monte Carlo-type randomized measurement strategy, which augments the default measurement grid with additional observation points sampled within each interval. This randomization enables unbiased estimation of the reward integral across each measurement gap, while maintaining the total number of measurements (i.e., measurement complexity) at the same order. This design not only enhances the practical effectiveness of CT-MLE but also introduces a general technique that may be of independent interest for continuous-time decision-making problems.

#### Notation.

We use lower case letters to denote scalars, and use lower and upper case bold face letters to denote vectors and matrices respectively. We denote by $[n]$ the set $\{1,\dots,n\}$.
For two positive functions $a(x)$ and $b(x)$ defined on a common domain, we write $a(x)\lesssim b(x)$ if there exists an absolute constant $C>0$ such that $a(x)\leq Cb(x)$ for all $x$ in the domain. Given a distribution $p(x)$, we use $\mathbb{E}_{x\sim p}[\cdot]$ to denote expectation and $\mathbb{V}_{x\sim p}[\cdot]$ to denote variance. For two distributions $p$ and $q$, we define their squared Hellinger distance as $\mathbb{H}^{2}(p\,\|\,q):=1-\int\sqrt{p(x)q(x)}\,dx$.

## 2 Related Work

### 2.1 Continuous-time reinforcement learning

Our work resides within the paradigm of CTRL, a foundational research thread in the control community. Early studies emphasized planning in analytically tractable settings such as the linear–quadratic regulator (LQR) (Doya, 2000; Vrabie and Lewis, 2009; Faradonbeh and Faradonbeh, 2023; Caines and Levanony, 2019; Huang et al., 2024; Basei et al., 2022; Szpruch et al., 2024). A pivotal advance occurred when Chen et al. (2018) introduced neural function approximation for learning nonlinear dynamics and value functions, thereby catalysing data-driven CTRL. Building on this foundation, Yildiz et al. (2021) proposed an episodic model-based framework that alternates between fitting ODE models to collected trajectories and solving the resulting optimal-control problem with a continuous-time actor–critic. Subsequently, Holt et al. (2024) showed that under costly observations, uniform time sampling is suboptimal and that state-dependent schedules can yield higher returns. Parallel efforts (Karimi, 2023; Ni and Jang, 2022; Holt et al., 2023) have bridged continuous-time theory with practical implementations by considering deterministic systems with discrete measurements or control updates. More recent analyses have extended these ideas to deterministic and stochastic dynamics with nonlinear approximation (Treven et al., 2024a, b), and Zhao et al. (2025) further broadened the approximation class while relaxing assumptions on epistemic-uncertainty estimators. Yet the existing theory largely provides worst-case guarantees. We close this gap by establishing the first variance-aware, nearly horizon-free *second-order* regret bound for stochastic CTRL under general function approximation—measured via the eluder dimension—and show that a simple, standard MLE-based model-based algorithm attains this bound.

### 2.2 Variance-aware reinforcement learning

There has been a series of work studying variance-aware or horizon-free sample complexity for discrete-time reinforcement learning (Simchowitz and Jamieson, 2019; Jin et al., 2020; Dann et al., 2021; Xu et al., 2021; Wagenmaker et al., 2022; He et al., 2021a, b; Zhou et al., 2021b, a; Zhao et al., 2022; Zhou and Gu, 2022). To mention a few, early online-learning work provided second-order bounds: Cesa-Bianchi et al. (2007) derived refined regret bounds based on squared losses in expert advice, and Ito et al. (2020) established tight first- and second-order regret for adversarial linear bandits using Bernstein-type concentration. Extending to MDPs, Zanette and Brunskill (2019)’s EULER algorithm achieves regret scaling with the maximum per-step return variance rather than $H$, and Foster and Krishnamurthy (2021) used triangular-discrimination bonuses to obtain small-loss bounds in contextual bandits. For structured function approximation, Kim et al. (2022) obtained horizon-free, variance-adaptive regret for linear mixture MDPs via weighted least-squares, Zhao et al. (2023) provided computationally efficient variance-dependent bounds for linear bandits and mixtures, and Zhang et al. (2021) devised variance-aware confidence sets giving logarithmic horizon dependence. Distributional RL has delivered second-order guarantees under general classes by modeling full return distributions (Zhang et al., 2022), and Huang et al. (2024) achieved sublinear regret for continuous-time stochastic LQR by estimating transition. Despite these advances, all require specialized variance or distributional machinery; our work shows that a standard MLE-based model-based RL approach attains nearly horizon-free, second-order variance-dependent bounds under general function approximation without bespoke variance estimation or distributional techniques, similar to Wang et al. (2024b) but under the continuous-time setup.

## 3 Problem Setup

#### Stochastic differential equation formulation.

We consider a general nonlinear continuous-time dynamical system governed by a stochastic differential equation (SDE). Let $x(\cdot)$ denote the state trajectory over a fixed planning horizon $[0,T]$, where $x(t)\in\mathcal{X}\subseteq\mathbb{R}^{l}$ for all $t\in[0,T]$. The system dynamics under a deterministic policy $u\in\Pi:\mathcal{X}\to\mathcal{U}\subseteq\mathbb{R}^{r}$ are described by

$$ $\displaystyle dx(t)=f(x(t),u(x(t)))\,dt+g(x(t),u(x(t)))\,dw(t),$ $$

where $w(t)\in\mathbb{R}^{l}$ is a standard Wiener process and the SDE is interpreted in the Itô sense. Here, $f\in\mathcal{F}$ and $g\in\mathcal{G}$, where each $f:\mathcal{X}\times\mathcal{U}\to\mathbb{R}^{l}$ and $g:\mathcal{X}\times\mathcal{U}\to\mathbb{R}^{l\times l}$ denote the drift and diffusion functions, respectively. Given an initial state $x(0)=x$, we denote by $p_{f,g}(u,x)$ the law of the trajectory $x(\cdot)$. We write $p_{f,g}(u,x,s)$ for the marginal distribution of $x(s)$ and use $p_{f,g}(\cdot\mid u,x,s)$ to denote its corresponding density function.

#### Learning protocol.

The learning process unfolds in episodes. In each episode $n=1,\dots,N$, the agent executes a policy $u_{n}$ and observes the trajectory $x(\cdot)\sim p_{f^{*},g^{*}}(u_{n},x_{\text{ini}})$, where $(f^{*},g^{*})$ denotes the unknown environment and $x_{\text{ini}}$ is the fixed initial state. During execution, the agent selects a set of measurement times $\{t_{n}^{k}\}_{k=1}^{m_{n}}\subset[0,T]$ at which observations are collected. These observations are used to update the policy for the next episode. The agent’s objective is to find a policy that maximizes the expected cumulative reward under the reward function $b:\mathcal{X}\times\mathcal{U}\to\mathbb{R}$:

$$ $\displaystyle u^{*}=\arg\max_{u\in\Pi}R_{f^{*},g^{*}}(u),\quad\text{where}\quad R_{f,g}(u):=V_{f,g}(u,x_{\text{ini}},0),$ $$

and the value function is given by

$$ $\displaystyle V_{f,g}(u,x,s):=\mathbb{E}_{x(\cdot)\sim p_{f,g}(u,x_{\text{ini}})}\left[\int_{t=s}^{T}b(x(t),u(x(t)))\,dt\,\bigg{|}\,x(s)=x\right].$ $$

#### Performance metrics.

We evaluate algorithmic performance using several metrics. The regret is defined as

$$ $\displaystyle\text{Regret}(N):=\sum_{n=1}^{N}\left(R_{f^{*},g^{*}}(u^{*})-R_{f^{*},g^{*}}(u_{n})\right),$ $$

We say a policy $u$ is $\epsilon$-optimal if $R_{f^{*},g^{*}}(u^{*})-R_{f^{*},g^{*}}(u)\leq\epsilon$. For any CTRL algorithm that returns an $\epsilon$-optimal policy after $N$ episodes, we define the *episode complexity* as $N$, and the *measurement complexity* as $\sum_{n=1}^{N}m_{n}$, where $m_{n}$ denotes the number of measurements in episode $n$. We also consider the *$\lambda$-total complexity* for any $\lambda\in[0,1]$, defined as the weighted sum: $(1-\lambda)N+\lambda\sum_{n=1}^{N}m_{n}.$
This interpolates between pure episode complexity ($\lambda=0$) and pure measurement complexity ($\lambda=1$).

Figure: Algorithm 1 Continuous-Time Reinforcement Learning with Maximum Likelihood Estimation

## 4 CTRL with Maximum Likelihood Estimation

In this section, we introduce our algorithm, CT-MLE, as described in Algorithm [1](https://arxiv.org/html/2508.02103v1#alg1). At a high level, each episode $n$ follows the standard optimistic model-based approach in CTRL (Treven et al., 2024b). Specifically, the agent constructs a confidence set for the unknown drift $f^{*}$ and diffusion $g^{*}$, and then applies the principle of optimism to select a near-optimal policy $u_{n}\in\Pi$. The selected policy is executed in the environment, yielding a continuous-time trajectory $x_{n}(\cdot)$. The agent then collects informative observations from this trajectory to refine its confidence set for the next episode. This framework parallels optimistic approaches in discrete-time RL (Abbasi-Yadkori et al., 2011; Jin et al., 2019; Russo and Van Roy, 2013; Jin et al., 2021), though applied to the continuous-time setting.

A key distinction in CTRL is that the agent must decide *when* to observe the trajectory, since data is generated in continuous time. To address this, CT-MLE introduces a sequence of measurement times $(t_{n}^{k})_{k=1}^{m_{n}}$ for each episode $n$. The agent collects observations only at these time points, i.e., $\{x_{n}(t_{n}^{k})\}_{k=1}^{m_{n}}$. Importantly, we allow the measurement times to be non-uniformly spaced, meaning the measurement gap $\Delta_{n,k}:=t_{n}^{k+1}-t_{n}^{k}$ can vary across time.

#### Maximum likelihood estimation.

To construct the confidence set, we begin by examining the learning objective in CTRL. Due to the Markov property of the Itô process, for any drift-diffusion pair $(f,g)$, policy $u$, state $x$, time $s$, and measurement gap $\Delta$, the following identity holds:

$$ $\displaystyle V_{f,g}(u,x,s)=\mathbb{E}_{x^{\prime}\sim p_{f,g}(u,x,\Delta)}\left[V_{f,g}(u,x^{\prime},s+\Delta)\right]+\mathbb{E}_{x(\cdot)\sim p_{f,g}(u,x)}\left[\int_{t=0}^{\Delta}b(x(t),u(x(t)))\,dt\right].$ (4.1) $$

This can be viewed as a continuous-time analogue of the Bellman equation. It implies that to evaluate the value function $V_{f^{*},g^{*}}(u,x_{\text{ini}},0)$, it suffices to estimate the marginal distribution $p_{f^{*},g^{*}}(u,x,\Delta)$ and the trajectory distribution $p_{f^{*},g^{*}}(u,x)$ over the interval $[0,\Delta]$. To estimate the first term in ([4.1](https://arxiv.org/html/2508.02103v1#S4.E1)), we construct a confidence set $\mathcal{P}_{n}$ based on MLE over historical observations, as defined in line [3](https://arxiv.org/html/2508.02103v1#algx1.l3) of Algorithm [1](https://arxiv.org/html/2508.02103v1#alg1), inspired by existing works about MLE for discrete-time RL (Agarwal et al., 2020; Liu et al., 2022; Wang et al., 2024a, b). Specifically, $\mathcal{P}_{n}$ contains all drift-diffusion pairs $(f,g)$ whose likelihood on the conditional distribution $p_{f,g}(x_{i}(t_{i}^{k+1})\mid u_{i},x_{i}(t_{i}^{k}),\Delta_{i,k})$ is sufficiently close to that of the MLE solution. The proximity is controlled via a confidence radius parameter $\beta$.

We note that existing approaches (Treven et al., 2024a; Zhao et al., 2025) typically aim to learn the underlying dynamics $(f^{*},g^{*})$ by directly estimating the drift term $f^{*}(x(t))$. In the corresponding deterministic setting where the diffusion term is zero, this drift is equivalent to the time derivative $\dot{x}(t)$. However, estimating this term from discrete and noisy trajectory data often requires non-trivial procedures like finite-difference approximations, which introduces additional algorithmic complexity and sensitivity to noise. In contrast, our approach relies solely on the observed states at discrete measurement times, making the estimation process both simpler and more robust.

#### Randomized additional measurement.

The second term in ([4.1](https://arxiv.org/html/2508.02103v1#S4.E1)) involves an integral over the trajectory segment $x(\cdot)$ governed by the law $p_{f,g}(u,x)$. While this integral could in principle require full knowledge of the process, it can instead be estimated using a single sample point via a Monte Carlo-style approach. To implement this, we augment CT-MLE with an additional randomized measurement step, as described in Algorithm [2](https://arxiv.org/html/2508.02103v1#alg2). Specifically, for each interval $[t_{i}^{k},t_{i}^{k+1})$, we sample a random time $\widehat{t}_{i,k}=t_{i}^{k}+\widehat{\Delta}_{i,k}$ uniformly from the interval and record the state $x_{i}(\widehat{t}_{i,k})$. It is worth noting that this modification requires only one additional measurement per interval, effectively doubling the number of measurements compared to CT-MLE without Algorithm [2](https://arxiv.org/html/2508.02103v1#alg2). Using these additional samples, we construct a second confidence set $\widehat{\mathcal{P}}_{n}$, based on the conditional distribution
$p_{f,g}(x_{i}(\widehat{t}_{i,k})\mid u_{i},x_{i}(t_{i}^{k}),\widehat{\Delta}_{i,k})$
. Notably, our algorithm does not explicitly compute the integral in ([4.1](https://arxiv.org/html/2508.02103v1#S4.E1)); instead, the randomized measurements serve to implicitly capture the integral’s behavior by refining the confidence set around the true dynamics $(f^{*},g^{*})$. This enables us to eliminate the continuity assumption without compromising performance guarantees.

Figure: Algorithm 2 Monte Carlo-Type Estimation

## 5 Analysis of CT-MLE

We present the theoretical analysis of Algorithm [1](https://arxiv.org/html/2508.02103v1#alg1). We begin by introducing the following regularity assumption, which summarizes all the conditions we impose on the system dynamics.

###### Assumption 5.1 .

The continuous-time system dynamics satisfy the following conditions:

- •
The policy class $\Pi$, drift class $\mathcal{F}$, and diffusion class $\mathcal{G}$ are all finite.
- •
The reward function $b(x,u)$ and the initial state $x_{\text{ini}}$ are known to the agent.
- •
The reward function is bounded: $0\leq b(x,u)\leq 1$ for all $(x,u)\in\mathcal{X}\times\mathcal{U}$. Furthermore, for any trajectory $x(\cdot)\sim p_{f^{*},g^{*}}(u,x_{\text{ini}})$, the cumulative reward is bounded as $\int_{0}^{T}b(x(t),u(x(t)))\,dt\leq 1$.

###### Remark 5.2 .

The finiteness assumption on $\Pi$, $\mathcal{F}$, and $\mathcal{G}$ is made to simplify the theoretical analysis, following prior works on sample complexity in discrete-time RL (Wang et al., 2023, 2024b). Our results can be extended to infinite model classes by replacing $\Pi$, $\mathcal{F}$, and $\mathcal{G}$ with their appropriate covering sets, without changing the core analysis (Wang et al., 2023, 2024b).

###### Remark 5.3 .

The boundedness assumption on $b$ is made for simplicity. For any general reward function $b$ satisfying $0\leq b(x,u)\leq B_{1}$ and $\int_{0}^{T}b(x(t),u(x(t)))\,dt\leq B_{2}$, one can normalize the reward by defining $b^{\prime}:=b/\max(B_{1},B_{2})$ and apply the algorithm and analysis to $b^{\prime}$.

Next, we introduce the notion of total variance for a policy $u$, a concept originating from discrete-time reinforcement learning (Wang et al., 2024b; Zhou et al., 2023), which serves as an instance-dependent measure of problem hardness.

###### Definition 5.4 .

For any policy $u\in\Pi$, we define its total variance $\operatorname{{\rm Var}}^{u}$ and the maximal total variance $\operatorname{{\rm Var}}^{\Pi}$ as

$$ $\operatorname{{\rm Var}}^{u}:=\mathbb{V}_{x(\cdot)\sim p_{f^{*},g^{*}}(u,x_{\text{ini}})}\left[\int_{0}^{T}b\bigl{(}x(t),u(x(t))\bigr{)}\,dt\right],\quad\operatorname{{\rm Var}}^{\Pi}:=\max_{u\in\Pi}\operatorname{{\rm Var}}^{u}.$ $$

By Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1), it immediately follows that $\operatorname{{\rm Var}}^{u}\leq 1$ for any $u\in\Pi$. The total variance $\operatorname{{\rm Var}}^{u}$ quantifies the uncertainty in the cumulative reward under the stochastic dynamics, and is tightly connected to the diffusion term $g$. The following proposition formally characterizes this dependence.

###### Proposition 5.5 .

Suppose the following conditions hold:

- •
The reward function $b$ is $L_{b}$-Lipschitz continuous: for all $x,x^{\prime}\in\mathcal{X}$ and $y,y^{\prime}\in\mathcal{U}$,
$|b(x,y)-b(x^{\prime},y^{\prime})|\leq L_{b}\left(\|x-x^{\prime}\|_{2}+\|y-y^{\prime}\|_{2}\right).$
- •
The drift $f\in\mathcal{F}$ is $L_{f}$-Lipschitz continuous, and the policy $u\in\Pi$ is $L_{u}$-Lipschitz continuous:
$\|f(x,y)-f(x^{\prime},y^{\prime})\|_{2}\leq L_{f}\left(\|x-x^{\prime}\|_{2}+\|y-y^{\prime}\|_{2}\right),\quad\|u(x)-u(y)\|_{2}\leq L_{u}\|x-y\|_{2}.$
- •
The diffusion term $g$ has bounded Frobenius norm: $\|g(x,y)\|_{F}\leq G$ for all $x\in\mathcal{X}$ and $y\in\mathcal{U}$.

Then, for any $u\in\Pi$, the total variance is bounded as

$$ $\displaystyle\operatorname{{\rm Var}}^{u}\leq\min\left\{1,\,G^{2}\cdot\frac{TL_{b}^{2}(1+L_{u})}{2L_{f}}\left(e^{2L_{f}(1+L_{u})T}-1\right)\right\}.$ $$

Proposition [5.5](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem5) shows that the total variance $\operatorname{{\rm Var}}^{u}$ is controlled by the magnitude of the diffusion term $G$. In particular, in a deterministic environment ($G=0$), we have $\operatorname{{\rm Var}}^{u}=0$ for all $u\in\Pi$. Furthermore, if the policy $u$ is less sensitive to its input (i.e., has small $L_{u}$), the total variance is also reduced. These observations support the use of $\operatorname{{\rm Var}}^{u}$ as a meaningful measure of instance difficulty in continuous-time reinforcement learning.

Next, we introduce the notion of the eluder dimension (Russo and Van Roy, 2013; Wang et al., 2023, 2024b; Zhao et al., 2025), which we use to characterize the complexity of the system dynamics class $\mathcal{F}\times\mathcal{G}$.

###### Definition 5.6 .

Let $\Psi$ be a class of real-valued functions defined on a domain $\mathcal{Y}$. The *$\epsilon$-eluder dimension* $\mathrm{DE}_{p}(\Psi,\mathcal{Y},\epsilon)$ is the length of the longest sequence $y^{1},\ldots,y^{L}\subseteq\mathcal{Y}$ such that for all $t\in[L]$, there exists $\psi\in\Psi$ satisfying $\sum_{\ell=1}^{t-1}|\psi(y^{\ell})|^{p}\leq\epsilon^{p}$ and $|\psi(y^{t})|>\epsilon$.

In this work, we specify $\mathcal{Y}=\Pi\times\mathcal{X}\times[0,T]$ and define the function class $\Psi=\{\psi_{f,g}\}_{(f,g)\in\mathcal{F}\times\mathcal{G}}$, where

$$ $\displaystyle\psi_{f,g}(u,x,t):=\mathbb{H}^{2}\left(p_{f,g}(u,x,t)\,\|\,p_{f^{*},g^{*}}(u,x,t)\right).$ $$

We use $d_{1/\epsilon}$ to denote $\mathrm{DE}_{1}(\Psi,\mathcal{Y},\epsilon)$.

###### Remark 5.7 .

The function class $\Psi$ is chosen for analytical clarity. First, by assuming a known reward function (Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1)), we isolate the core challenge to learning the unknown dynamics $(f^{*},g^{*})$. This allows for a focused analysis of how the measurement strategy and stochasticity affect regret. While a unified analysis incorporating the reward function is common in other settings Jin et al. (2021); He et al. (2021b), its extension to continuous time is a nontrivial challenge deferred to future work. Second, using the squared Hellinger distance provides a direct analytical bridge between the statistical error of our estimator and the regret decomposition, which is central to the proof for the final regret bound.

###### Remark 5.8 .

Treven et al. (2024a) introduced a model complexity notion $\mathcal{I}_{N}$ based on an external estimator for the epistemic uncertainty of $f^{*},g^{*}$. In contrast, our eluder dimension requires no such estimator, offering a broader, self-contained characterization. Zhao et al. (2025) also considered eluder dimension in CTRL, but theirs targets only the nonlinearity in estimating $f^{*}$, while ours captures the nonlinearity of the full induced distribution $p_{f^{*},g^{*}}$, yielding a more general measure.

The following proposition shows that under a quadratic density model, the eluder dimension of $\Psi$ is low.

###### Proposition 5.9 .

Suppose the marginal density function $p_{f,g}(\cdot\mid u,x,t)$ admits the form

$$ $\displaystyle p_{f,g}(\cdot\mid u,x,t)=\left(\phi(u,x,t)^{\top}\mu_{f,g}(\cdot)\right)^{2},\quad\phi,\mu_{f,g}\in\mathbb{R}^{d},\quad\|\phi\|_{2}\leq 1,\,\int_{y}\|\mu_{f,g}(y)\|_{2}^{2}dy\leq B,$ $$

then the corresponding $\psi_{f,g}$ satisfies $d_{1/\epsilon}\lesssim d^{2}\log\left(1+\frac{B^{2}}{\epsilon^{2}}\right)$.

While the quadratic density form in Proposition [5.9](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem9) may seem restrictive, such structures naturally emerge in continuous-time systems (see Appendix [A.3](https://arxiv.org/html/2508.02103v1#A1.SS3) for details).

We now present our main theory.

###### Theorem 5.10 .

For any fixed grid $(t_{n}^{k})$, define $\bm{\Delta}_{n}:=\sqrt{\sum_{k=0}^{m_{n}-1}\Delta_{n,k}^{2}}$ and $\bm{m}_{N}:=\sum_{n=1}^{N}m_{n}$.
Given $0<\delta<1$, set $\beta=\log(|\mathcal{F}||\mathcal{G}|N/\delta)$ and $\iota:=\log(N/\delta)\log(\bm{m}_{N})$. Then, under Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1), with probability at least $1-8\delta$, we have

$$ $\displaystyle\text{Regret}(N)\lesssim\iota\bigg{(}d_{8\beta\bm{m}_{N}}\beta+\sqrt{d_{\bm{m}_{N}}\beta\bigg{(}\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}+\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}\bigg{)}}\bigg{)}.$ (5.1) $$

###### Proof.

See Appendix [B](https://arxiv.org/html/2508.02103v1#A2).
∎

To the best of our knowledge, the resulting regret bound of Algorithm [1](https://arxiv.org/html/2508.02103v1#alg1) is the first instance-dependent second-order regret bound established in CTRL. Notably, the dependence on $\operatorname{{\rm Var}}^{u_{n}}$ is independent of the measurement strategy, highlighting it as a fundamental quantity characterizing the intrinsic difficulty of the continuous-time system dynamics. We summarize several key remarks below.

###### Remark 5.11 .

The regret bound ([5.1](https://arxiv.org/html/2508.02103v1#S5.E1)) remains unchanged as long as the total measurement budget $\bm{\Delta}_{n}$ is fixed. This implies that CTRL is *robust* to different choices of measurement schedules, provided the total measurement effort remains the same. This aligns with recent observations (Treven et al., 2024b) suggesting that CTRL is relatively insensitive to the minimum measurement gap $\min_{k}\Delta_{n,k}$. In particular, while equidistant measurements may seem natural—as they mirror discrete-time RL—they are not the only strategy capable of achieving near-optimal regret guarantees.

###### Remark 5.12 .

Many prior works on CTRL derive regret or sample complexity bounds that scale exponentially with the planning horizon $T$, i.e., contain terms of the form $\exp(T)$ (Treven et al., 2024a; Zhao et al., 2025), making the bounds vacuous for large $T$. In contrast, our regret bound in ([5.1](https://arxiv.org/html/2508.02103v1#S5.E1)) depends on $T$ only logarithmically, due to the use of the total variance $\operatorname{{\rm Var}}^{u_{n}}$, which is bounded by 1 under Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1). We emphasize that avoiding the exponential dependence on $T$ is made possible by analyzing the problem through the lens of total variance. Without this perspective, one would recover an exponential dependence on $T$, as shown in Proposition [5.5](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem5).

Next we discuss a more refined version of regret bound and $\lambda$-total complexity of CT-MLE.

###### Corollary 5.13 .

Suppose there exists a constant $d>0$ such that $d\geq\max\{d_{8\beta\bm{m}_{N}},d_{\bm{m}_{N}},\beta\}$. Using the notations defined in Theorem [5.10](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem10), and selecting equidistant measurements $\Delta_{n,k}=\Delta$, the regret is bounded as

$$ $\displaystyle\text{Regret}(N)\lesssim\log(N/\delta)\log(TN/\Delta)\big{(}d^{2}+d\sqrt{NT\Delta+N\operatorname{{\rm Var}}^{\Pi}}\big{)}.$ $$

Furthermore, to find an $\epsilon$-optimal policy $\widehat{u}$, the $\lambda$-total complexity is bounded, up to logarithmic factors, by

$$ $\displaystyle(1-\lambda)\bigg{(}\frac{d^{2}}{\epsilon}+\frac{d^{2}\operatorname{{\rm Var}}^{\Pi}}{\epsilon^{2}}\bigg{)}+\lambda\frac{d^{2}T^{2}}{\epsilon^{2}}+\frac{(1-\lambda)d^{2}T\Delta}{\epsilon^{2}}+\bigg{(}\frac{d^{2}}{\epsilon}+\frac{d^{2}\operatorname{{\rm Var}}^{\Pi}}{\epsilon^{2}}\bigg{)}\frac{\lambda T}{\Delta}.$ (5.2) $$

We have the following remarks about the total complexity ([5.2](https://arxiv.org/html/2508.02103v1#S5.E2)).

###### Remark 5.14 .

When $\lambda=0$, i.e., we only care about the episode complexity and ignore the measurement complexity, selecting the measurement gap as $\Delta=\operatorname{{\rm Var}}^{\Pi}/T$ yields an episode complexity of $d^{2}\operatorname{{\rm Var}}^{\Pi}/\epsilon^{2}$. This result suggests that to fully exploit the instance-dependent property of Algorithm [1](https://arxiv.org/html/2508.02103v1#alg1), it suffices to choose an instance-dependent measurement gap. In particular, achieving instance-adaptive performance requires measuring more frequently in less stochastic environments. Meanwhile, the measurement complexity becomes $d^{2}T^{2}/\epsilon^{2}$, which is independent of the specific problem instance.

###### Remark 5.15 .

When $\lambda=1$, i.e., we focus solely on the measurement complexity and ignore the episode complexity, the optimal choice is $\Delta=T$. The total measurement complexity is proportional to $\frac{d^{2}\operatorname{{\rm Var}}^{\Pi}}{\epsilon^{2}}\cdot\frac{T}{\Delta}$.
To minimize this expression, $\Delta$ must be maximized. This implies a sparse sampling strategy where for each episode, we collect samples at the start and end points, $x(0)$ and $x(T)$, along with one additional sample at a random time $\widehat{t}\in[0,T]$. This result highlights a theoretical trade-off, favoring many "measurement-cheap" episodes over a few "measurement-expensive" ones. Interestingly, the measurement complexity asymptotically matches the complexity when episode complexity is the sole focus $\lambda=0$. This observation leads to an interesting conjecture: the problem instance influences only the episode complexity, but not the measurement complexity. Verifying the tightness of these bounds remains an open direction for future work.

###### Assumption 5.1 .

###### Remark 5.2 .

###### Remark 5.3 .

###### Definition 5.4 .

###### Proposition 5.5 .

###### Definition 5.6 .

###### Remark 5.7 .

###### Remark 5.8 .

###### Proposition 5.9 .

###### Theorem 5.10 .

###### Proof.

###### Remark 5.11 .

###### Remark 5.12 .

###### Corollary 5.13 .

###### Remark 5.14 .

###### Remark 5.15 .

## 6 Conclusion and Limitations

#### Conclusion.

In this work, we presented CT-MLE, a simple and general model-based algorithm for CTRL that learns through marginal density estimation rather than explicit dynamic modeling. Our approach leverages MLE with flexible function approximators, enabling compatibility with a wide range of policy classes and continuous-time settings. We introduced a randomized measurement strategy, including a Monte Carlo-style scheme that provides unbiased integral estimation while preserving measurement efficiency. Theoretically, we established regret bounds that reveal the benefit of instance-dependent measurement schedules, and we demonstrated that the regret can be made primarily dependent on total reward variance, effectively decoupling it from fixed measurement grids.

#### Limitations.

While our work provides a theoretical foundation, several gaps remain. First, we assume access to general function approximators, but do not provide a computationally efficient, provably correct algorithm. A key next step is to develop an adaptive method that estimates variance online and sets measurement gaps accordingly. Second, our analysis relies on a simplified continuous-time structure for tractability, which may not hold in practice. Future work could identify realistic dynamics that still support Eluder-dimension-based analysis. Third, our framework assumes a known deterministic reward and stationary policy. Extending to stochastic rewards and time-varying policies $u(t,x)$ would require generalizing existing tools to the joint state-time domain. Lastly, empirical validation on standard CTRL benchmarks is needed to assess the practical utility of our approach.

## References

- Abbasi-Yadkori et al. (2011)
Abbasi-Yadkori, Y., Pál, D. and Szepesvári, C. (2011).
Improved algorithms for linear stochastic bandits.
In Advances in Neural Information Processing Systems.
- Agarwal et al. (2019)
Agarwal, A., Jiang, N., Kakade, S. M. and Sun, W. (2019).
Reinforcement learning: Theory and algorithms.
CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep 32 96.
- Agarwal et al. (2020)
Agarwal, A., Kakade, S., Krishnamurthy, A. and Sun, W. (2020).
Flambe: Structural complexity and representation learning of low rank mdps.
Advances in neural information processing systems 33 20095–20107.
- Basei et al. (2022)
Basei, M., Guo, X., Hu, A. and Zhang, Y. (2022).
Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon.
Journal of Machine Learning Research 23 1–34.
- Brockman et al. (2016)
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J. and Zaremba, W. (2016).
Openai gym.
arXiv preprint arXiv:1606.01540 .
- Caines and Levanony (2019)
Caines, P. E. and Levanony, D. (2019).
Stochastic $\varepsilon$-optimal linear quadratic adaptation: An alternating controls policy.
SIAM Journal on Control and Optimization 57 1094–1126.
- Cesa-Bianchi et al. (2007)
Cesa-Bianchi, N., Mansour, Y. and Stoltz, G. (2007).
Improved second-order bounds for prediction with expert advice.
Machine Learning 66 321–352.
- Chen et al. (2018)
Chen, R. T., Rubanova, Y., Bettencourt, J. and Duvenaud, D. K. (2018).
Neural ordinary differential equations.
Advances in neural information processing systems 31.
- Dann et al. (2021)
Dann, C., Marinov, T. V., Mohri, M. and Zimmert, J. (2021).
Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning.
Advances in Neural Information Processing Systems 34 1–12.
- Doya (2000)
Doya, K. (2000).
Reinforcement learning in continuous time and space.
Neural Computation 12 219–245.
- Dzhaparidze and Van Zanten (2001)
Dzhaparidze, K. and Van Zanten, J. (2001).
On bernstein-type inequalities for martingales.
Stochastic processes and their applications 93 109–117.
- Fan et al. (2017)
Fan, X., Grama, I. and Liu, Q. (2017).
Martingale inequalities of type dzhaparidze and van zanten.
Statistics 51 1200–1213.
- Faradonbeh and Faradonbeh (2023)
Faradonbeh, M. K. S. and Faradonbeh, M. S. S. (2023).
Online reinforcement learning in stochastic continuous-time systems.
In The Thirty Sixth Annual Conference on Learning Theory. PMLR.
- Foster and Krishnamurthy (2021)
Foster, D. J. and Krishnamurthy, A. (2021).
Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination.
Advances in Neural Information Processing Systems 34 18907–18919.
- Greydanus et al. (2019)
Greydanus, S., Dzamba, M. and Yosinski, J. (2019).
Hamiltonian neural networks.
Advances in neural information processing systems 32.
- He et al. (2021a)
He, J., Zhou, D. and Gu, Q. (2021a).
Logarithmic regret for reinforcement learning with linear function approximation.
In International Conference on Machine Learning. PMLR.
- He et al. (2021b)
He, J., Zhou, D. and Gu, Q. (2021b).
Uniform-pac bounds for reinforcement learning with linear function approximation.
Advances in Neural Information Processing Systems 34 14188–14199.
- Holt et al. (2023)
Holt, S., Hüyük, A. and van der Schaar, M. (2023).
Active observing in continuous-time control.
In Thirty-seventh Conference on Neural Information Processing Systems.
- Holt et al. (2024)
Holt, S., Hüyük, A. and van der Schaar, M. (2024).
Active observing in continuous-time control.
Advances in Neural Information Processing Systems 36.
- Huang et al. (2024)
Huang, Y., Jia, Y. and Zhou, X. Y. (2024).
Sublinear regret for a class of continuous-time linear–quadratic reinforcement learning problems.
arXiv preprint arXiv:2407.17226 .
- Hyvärinen and Dayan (2005)
Hyvärinen, A. and Dayan, P. (2005).
Estimation of non-normalized statistical models by score matching.
Journal of Machine Learning Research 6.
- Ito et al. (2020)
Ito, S., Hirahara, S., Soma, T. and Yoshida, Y. (2020).
Tight first-and second-order regret bounds for adversarial linear bandits.
Advances in Neural Information Processing Systems 33 2028–2038.
- Jin et al. (2020)
Jin, C., Krishnamurthy, A., Simchowitz, M. and Yu, T. (2020).
Reward-free exploration for reinforcement learning.
In International Conference on Machine Learning. PMLR.
- Jin et al. (2021)
Jin, C., Liu, Q. and Miryoosefi, S. (2021).
Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.
Advances in neural information processing systems 34 13406–13418.
- Jin et al. (2019)
Jin, C., Yang, Z., Wang, Z. and Jordan, M. I. (2019).
Provably efficient reinforcement learning with linear function approximation.
arXiv preprint arXiv:1907.05388 .
- Karimi (2023)
Karimi, A. (2023).
Decision frequency adaptation in reinforcement learning using continuous options with open-loop policies.
- Kim et al. (2022)
Kim, Y., Yang, I. and Jun, K.-S. (2022).
Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps.
Advances in Neural Information Processing Systems 35 1060–1072.
- Kingma (2014)
Kingma, D. P. (2014).
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980 .
- Lillicrap et al. (2015)
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D. and Wierstra, D. (2015).
Continuous control with deep reinforcement learning.
arXiv preprint arXiv:1509.02971 .
- Liu et al. (2022)
Liu, Q., Chung, A., Szepesvári, C. and Jin, C. (2022).
When is partially observable reinforcement learning not scary?
In Conference on Learning Theory. PMLR.
- Loshchilov and Hutter (2017)
Loshchilov, I. and Hutter, F. (2017).
Decoupled weight decay regularization.
arXiv preprint arXiv:1711.05101 .
- Lutter et al. (2021)
Lutter, M., Mannor, S., Peters, J., Fox, D. and Garg, A. (2021).
Value iteration in continuous actions, states and time.
In International Conference on Machine Learning. PMLR.
- Ni and Jang (2022)
Ni, T. and Jang, E. (2022).
Continuous control on time.
In ICLR 2022 Workshop on Generalizable Policy Learning in Physical World.
- Pabbaraju et al. (2023)
Pabbaraju, C., Rohatgi, D., Sevekari, A. P., Lee, H., Moitra, A. and Risteski, A. (2023).
Provable benefits of score matching.
Advances in Neural Information Processing Systems 36 61306–61326.
- Risken and Frank (1996)
Risken, H. and Frank, T. (1996).
The Fokker-Planck Equation: Methods of Solution and Applications, vol. 18.
Springer Science & Business Media.
- Russo and Van Roy (2013)
Russo, D. and Van Roy, B. (2013).
Eluder dimension and the sample complexity of optimistic exploration.
Advances in Neural Information Processing Systems 26.
- Silver et al. (2014)
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D. and Riedmiller, M. (2014).
Deterministic policy gradient algorithms.
In International conference on machine learning. Pmlr.
- Simchowitz and Jamieson (2019)
Simchowitz, M. and Jamieson, K. G. (2019).
Non-asymptotic gap-dependent regret bounds for tabular mdps.
Advances in Neural Information Processing Systems 32.
- Song et al. (2020)
Song, Y., Garg, S., Shi, J. and Ermon, S. (2020).
Sliced score matching: A scalable approach to density and score estimation.
In Uncertainty in artificial intelligence. PMLR.
- Szpruch et al. (2024)
Szpruch, L., Treetanthiploet, T. and Zhang, Y. (2024).
Optimal scheduling of entropy regularizer for continuous-time linear-quadratic reinforcement learning.
SIAM Journal on Control and Optimization 62 135–166.
- Towers et al. (2024)
Towers, M., Kwiatkowski, A., Terry, J., Balis, J. U., De Cola, G., Deleu, T., Goulao, M., Kallinteris, A., Krimmel, M., KG, A. et al. (2024).
Gymnasium: A standard interface for reinforcement learning environments.
arXiv preprint arXiv:2407.17032 .
- Treven et al. (2024a)
Treven, L., Hübotter, J., Dorfler, F. and Krause, A. (2024a).
Efficient exploration in continuous-time model-based reinforcement learning.
Advances in Neural Information Processing Systems 36.
- Treven et al. (2024b)
Treven, L., Sukhija, B., As, Y., Dörfler, F. and Krause, A. (2024b).
When to sense and control? a time-adaptive approach for continuous-time rl.
arXiv preprint arXiv:2406.01163 .
- Vrabie and Lewis (2009)
Vrabie, D. and Lewis, F. (2009).
Neural network approach to continuous-time direct adaptive optimal control for partially unknown nonlinear systems.
Neural Networks 22 237–246.
- Wagenmaker et al. (2022)
Wagenmaker, A. J., Chen, Y., Simchowitz, M., Du, S. and Jamieson, K. (2022).
First-order regret in reinforcement learning with linear function approximation: A robust estimation approach.
In International Conference on Machine Learning. PMLR.
- Wang et al. (2024a)
Wang, K., Oertell, O., Agarwal, A., Kallus, N. and Sun, W. (2024a).
More benefits of being distributional: Second-order bounds for reinforcement learning.
arXiv preprint arXiv:2402.07198 .
- Wang et al. (2023)
Wang, K., Zhou, K., Wu, R., Kallus, N. and Sun, W. (2023).
The benefits of being distributional: Small-loss bounds for reinforcement learning.
Advances in neural information processing systems 36 2275–2312.
- Wang et al. (2024b)
Wang, Z., Zhou, D., Lui, J. and Sun, W. (2024b).
Model-based rl as a minimalist approach to horizon-free and second-order bounds.
arXiv preprint arXiv:2408.08994 .
- Xie et al. (2023)
Xie, E., Yao, L., Shi, H., Liu, Z., Zhou, D., Liu, Z., Li, J. and Li, Z. (2023).
Difffit: Unlocking transferability of large diffusion models via simple parameter-efficient fine-tuning.
In Proceedings of the IEEE/CVF International Conference on Computer Vision.
- Xu et al. (2021)
Xu, H., Ma, T. and Du, S. (2021).
Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap.
In Conference on Learning Theory. PMLR.
- Yildiz et al. (2021)
Yildiz, C., Heinonen, M. and Lähdesmäki, H. (2021).
Continuous-time model-based reinforcement learning.
In International Conference on Machine Learning. PMLR.
- Yoon et al. (2024)
Yoon, T., Myoung, K., Lee, K., Cho, J., No, A. and Ryu, E. (2024).
Censored sampling of diffusion models using 3 minutes of human feedback.
Advances in Neural Information Processing Systems 36.
- Zanette and Brunskill (2019)
Zanette, A. and Brunskill, E. (2019).
Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.
In International Conference on Machine Learning. PMLR.
- Zhang et al. (2022)
Zhang, Z., Ji, X. and Du, S. (2022).
Horizon-free reinforcement learning in polynomial time: the power of stationary policies.
In Conference on Learning Theory. PMLR.
- Zhang et al. (2021)
Zhang, Z., Yang, J., Ji, X. and Du, S. S. (2021).
Improved variance-aware confidence sets for linear bandits and linear mixture mdp.
Advances in Neural Information Processing Systems 34 4342–4355.
- Zhao et al. (2023)
Zhao, H., He, J., Zhou, D., Zhang, T. and Gu, Q. (2023).
Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency.
In The Thirty Sixth Annual Conference on Learning Theory. PMLR.
- Zhao et al. (2022)
Zhao, H., Zhou, D., He, J. and Gu, Q. (2022).
Bandit learning with general function classes: Heteroscedastic noise and variance-dependent regret bounds.
CoRR .
- Zhao et al. (2025)
Zhao, R., Yu, Y., Zhu, A. Y., Yang, C. and Zhou, D. (2025).
Sample and computationally efficient continuous-time reinforcement learning with general function approximation.
In The 41st Conference on Uncertainty in Artificial Intelligence.
- Zhou and Gu (2022)
Zhou, D. and Gu, Q. (2022).
Computationally efficient horizon-free reinforcement learning for linear mixture mdps.
Advances in neural information processing systems 35 36337–36349.
- Zhou et al. (2021a)
Zhou, D., Gu, Q. and Szepesvari, C. (2021a).
Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.
In Conference on Learning Theory. PMLR.
- Zhou et al. (2021b)
Zhou, D., He, J. and Gu, Q. (2021b).
Provably efficient reinforcement learning for discounted mdps with feature mapping.
In International Conference on Machine Learning. PMLR.
- Zhou et al. (2023)
Zhou, R., Zihan, Z. and Du, S. S. (2023).
Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments.
In International Conference on Machine Learning. PMLR.

## Contents of the Appendix

[section]
\printcontents[section]l1

## Appendix A Additional Results from Main Paper

### A.1 Proof of Proposition 5.5

###### Proof.

For any deterministic policy $u$, we have

$$ $\displaystyle\operatorname{{\rm Var}}^{u}$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p_{f^{*},g^{*}}(u,x_{\text{ini}})}\left[\int_{0}^{T}b(x(t),u(x(t)))-\mathbb{E}_{x(\cdot)\sim p_{f^{*},g^{*}}(u,x_{\text{ini}})}\int_{0}^{T}b(x(t),u(x(t)))\right]^{2}.$ $$

Applying the Cauchy–Schwarz inequality yields

$$ $\displaystyle\operatorname{{\rm Var}}^{u}$ $\displaystyle\leq\mathbb{E}_{x(\cdot)\sim p_{f^{*},g^{*}}(u,x_{\text{ini}})}\left[\int_{0}^{T}\left(b(x(t),u(x(t)))-\mathbb{E}_{x\sim p_{t}}b(x,u(x))\right)^{2}dt\right]$ $\displaystyle=\int_{0}^{T}\mathbb{E}_{x\sim p_{t}}\left(b(x,u(x))-\mathbb{E}_{x^{\prime}\sim p_{t}}b(x^{\prime},u(x^{\prime}))\right)^{2}dt,$ (A.1) $$

where we denote $p_{t}=p_{f^{*},g^{*}}(u,x_{\text{ini}},t)$ for simplicity.

For the integrand in ([A.1](https://arxiv.org/html/2508.02103v1#A1.E1)), by the Lipschitz continuity of $b$ and $u$, we have

$$ $\displaystyle\mathbb{E}_{x\sim p_{t}}\left(b(x,u(x))-\mathbb{E}_{x^{\prime}\sim p_{t}}b(x^{\prime},u(x^{\prime}))\right)^{2}$ $\displaystyle=\mathbb{E}_{x,x^{\prime}\sim p_{t}}\left(b(x,u(x))-b(x^{\prime},u(x^{\prime}))\right)^{2}$ $\displaystyle\leq\mathbb{E}_{x,x^{\prime}\sim p_{t}}\left(L_{b}(\|x-x^{\prime}\|_{2}+L_{u}\|x-x^{\prime}\|_{2})\right)^{2}$ $\displaystyle=L_{b}^{2}(1+L_{u})^{2}\mathbb{E}_{x,x^{\prime}\sim p_{t}}\|x-x^{\prime}\|_{2}^{2}$ $\displaystyle=2L_{b}^{2}(1+L_{u})^{2}\,\mathbb{E}_{x\sim p_{t}}\left\|x-\mathbb{E}_{x^{\prime}\sim p_{t}}x^{\prime}\right\|_{2}^{2}.$ $$

Define

$$ $\displaystyle V(t):=\mathbb{E}_{x\sim p_{t}}\left\|x-\mathbb{E}_{x^{\prime}\sim p_{t}}x^{\prime}\right\|_{2}^{2},\quad\mu(t):=\mathbb{E}_{x\sim p_{t}}[x].$ $$

Next we calculate the derivate of $V(t)$. First, by applying Itô’s formula to $\|x(t)\|^{2}$, we have

$$ $\displaystyle d\|x(t)\|_{2}^{2}$ $\displaystyle=2\langle x(t),f(x(t),u(x(t)))\rangle\,dt+\|g(x(t),u(x(t)))\|_{F}^{2}\,dt$ $\displaystyle+2\langle x(t),g(x(t),u(x(t)))\,dw(t)\rangle.$ $$

Then taking expectation for both side and using the fact $\mathbb{E}dw(t)=0$, we have

$$ $\displaystyle\frac{d}{dt}\mathbb{E}\|x(t)\|_{2}^{2}=2\,\mathbb{E}\!\langle x(t),f(x(t),u(x(t)))\rangle+\mathbb{E}\|g(x(t),u(x(t)))\|_{F}^{2}.$ $$

Next, we have

$$ $\displaystyle\frac{d}{dt}\|\mu(t)\|_{2}^{2}=2\bigl{\langle}\mu(t),\mathbb{E}f(x(t),u(x(t)))\bigr{\rangle}.$ $$

Then by the fact that $V(t)=\mathbb{E}\|x(t)\|_{2}^{2}-\|\mu(t)\|_{2}^{2}$ we obtain

$$ $\displaystyle\frac{d}{dt}V(t)$ $\displaystyle=2\,\mathbb{E}\left[\langle x(t)-\mu(t),f(x(t),u(x(t)))-f(\mu(t),u(\mu(t)))\rangle\right]+\mathbb{E}\left[\|g(x(t),u(x(t)))\|_{F}^{2}\right]$ $\displaystyle\leq 2\,\mathbb{E}\|x(t)-\mu(t)\|_{2}\cdot\|f(x(t),u(x(t)))-f(\mu(t),u(\mu(t)))\|_{2}+\mathbb{E}\|g(x(t),u(x(t)))\|_{F}^{2}$ $\displaystyle\leq 2L_{f}(1+L_{u})V(t)+G^{2},$ $$

where the last inequality follows from the Lipschitz continuity of $f$ and $u$.

Applying Grönwall’s lemma, we get

$$ $\displaystyle V(t)\leq\frac{G^{2}}{2L_{f}(1+L_{u})}\left(e^{2L_{f}(1+L_{u})t}-1\right)\leq\frac{G^{2}}{2L_{f}(1+L_{u})}\left(e^{2L_{f}(1+L_{u})T}-1\right).$ (A.2) $$

Substituting ([A.2](https://arxiv.org/html/2508.02103v1#A1.E2)) into ([A.1](https://arxiv.org/html/2508.02103v1#A1.E1)) completes the proof.
∎

###### Proof.

### A.2 Proof of Proposition 5.9

###### Proof.

By the definition of Hellinger distance, we have $\operatorname{H}$

$$ $\displaystyle\mathbb{H}^{2}(p_{f,g}(u,x,t)\|p_{f^{*},g^{*}}(u,x,t))$ $\displaystyle=1-\int_{y}\sqrt{p_{f,g}(y|u,x,t)\cdot p_{f^{*},g^{*}}(y|u,x,t)}\,dy$ $\displaystyle=1-\int_{y}\phi(u,x,t)^{\top}\mu_{f,g}(y)\mu_{f^{*},g^{*}}(y)^{\top}\phi(u,x,t)\,dy$ $\displaystyle=1-\phi(u,x,t)^{\top}\left[\int_{y}\mu_{f,g}(y)\mu_{f^{*},g^{*}}(y)^{\top}dy\right]\phi(u,x,t).$ (A.3) $$

Therefore, the squared Hellinger distance is a linear function of the feature matrix $\phi(u,x,t)\phi(u,x,t)^{\top}\in\mathbb{R}^{d\times d}$. Since $\|\phi(u,x,t)\|_{2}\leq 1$, it follows that

$$ $\displaystyle\|\phi(u,x,t)\phi(u,x,t)^{\top}\|_{F}\leq 1.$ (A.4) $$

Now we bound the Frobenius norm of the matrix inside the integral:

$$ $\displaystyle\left\|\int_{y}\mu_{f,g}(y)\mu_{f^{*},g^{*}}(y)^{\top}dy\right\|_{F}$ $\displaystyle\leq\int_{y}\|\mu_{f,g}(y)\|_{2}\cdot\|\mu_{f^{*},g^{*}}(y)\|_{2}\,dy$ $\displaystyle\leq\left(\int_{y}\|\mu_{f,g}(y)\|_{2}^{2}dy\right)^{1/2}\left(\int_{y}\|\mu_{f^{*},g^{*}}(y)\|_{2}^{2}dy\right)^{1/2}$ $\displaystyle\leq B,$ (A.5) $$

where the last inequality uses the Cauchy–Schwarz inequality and the assumed boundedness of the $\mu$ functions.

Putting together the bounds in ([A.3](https://arxiv.org/html/2508.02103v1#A1.E3)), ([A.4](https://arxiv.org/html/2508.02103v1#A1.E4)), and ([A.5](https://arxiv.org/html/2508.02103v1#A1.E5)), and invoking Proposition 19 in Liu et al. (2022) and Proposition 6 in Russo and Van Roy (2013), we conclude that

$$ $\displaystyle d_{1/\epsilon}\leq\mathrm{DE}_{2}(\Psi,\mathcal{Y},\epsilon)\lesssim d^{2}\log\left(1+\frac{B^{2}}{\epsilon^{2}}\right).$ $$

∎

###### Proof.

### A.3 Construction example for Proposition 5.9

The quadratic form presented in Proposition [5.9](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem9) is well-motivated and can be constructed explicitly. For simplicity, let us consider a quadratic density function $p(y\mid t)$ that is independent of policy $u$ and state $x$. Let us assume $p(y\mid t)=(\phi(t)^{\top}\mu(y))^{2}$ with $\phi(t),\mu(y)\in\mathbb{R}^{2}$. Then we can take $\phi(t)=(\cos(t),\sin(t))^{\top}$ and $\mu(y)=(c_{1}e^{-y^{2}},c_{2}ye^{-y^{2}})^{\top}$, where $c_{1}=(2/\pi)^{1/4}$ and $c_{2}=2(2/\pi)^{1/4}$. The resulting density is

$$ $\displaystyle p(y\mid t)=\left[(2/\pi)^{1/4}\cos(t)e^{-y^{2}}+2(2/\pi)^{1/4}\sin(t)ye^{-y^{2}}\right]^{2}.$ $$

This defines a valid, time-evolving probability density because the basis functions in $\mu(y)$ are orthonormal, satisfying $\int\mu_{i}(y)\mu_{j}(y)\,dy=\delta_{ij}$, and the coefficients in $\phi(t)$ satisfy $\cos^{2}(t)+\sin^{2}(t)=1$, ensuring $\int p(y\mid t)\,dy=1$ for all $t$.

The drift $f(y,t)$ and diffusion $g(y,t)$ of an SDE generating this density can be obtained from the Fokker–Planck equation $\partial_{t}p=-\partial_{y}(fp)+\frac{1}{2}\partial_{y}^{2}(g^{2}p)$. Setting $g=1$, we have

$$ $\displaystyle f(y,t)=\frac{1}{p(y\mid t)}\int_{-\infty}^{y}\left[\frac{1}{2}\frac{\partial^{2}p}{\partial z^{2}}-\frac{\partial p}{\partial t}\right]dz.$ $$

Although the resulting drift does not have a simple closed form, it can be computed explicitly given $p(y\mid t)$. In this sense, the SDE with $(f,1)$ provides a valid example satisfying Proposition [5.9](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem9).

Additionally, though classical SDEs do not directly yield the quadratic form of Proposition [5.9](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem9), we can identify related structures in well-known processes. The classical Ornstein–Uhlenbeck (OU) process provides a case that satisfies a linear form $p(y\mid t)=\phi(t)^{\top}\mu(y)$. Its spectral representation (see Chapter 5.4 of Risken and Frank (1996)) is given by

$$ $\displaystyle p(y\mid t,y_{0})=\sum_{n=0}^{\infty}e^{\lambda_{n}t}\psi_{n}(y)\psi_{n}(y_{0}),$ $$

where $\lambda_{n}=-n\gamma$ with $\gamma>0$ denoting the mean-reversion rate, and $\{\psi_{n}(y)\}$ are the Hermite eigenfunctions of the corresponding OU generator. This representation constitutes a linear inner product in an infinite-dimensional space, illustrating that such structures arise naturally even when the SDE itself has simple drift and diffusion coefficients.

## Appendix B Proof of Main Theorem

We first define several notations for convenience. Let

$$ $\displaystyle p^{*}_{n}(x,t)$ $\displaystyle:=p_{f^{*},g^{*}}(u_{n},x,t),$ $\displaystyle p_{n}(x,t)$ $\displaystyle:=p_{f_{n},g_{n}}(u_{n},x,t),$ $\displaystyle V^{*}_{n}(x,t)$ $\displaystyle:=V_{f^{*},g^{*}}(u_{n},x,t),$ $\displaystyle V_{n}(x,t)$ $\displaystyle:=V_{f_{n},g_{n}}(u_{n},x,t).$ $$

### B.1 Auxiliary lemmas

The following lemma shows that the difference in expectations between two distributions can be bounded by the variance of one distribution and their Hellinger distance, which plays a key role in deriving our variance-dependent regret bound.

###### Lemma B.1 ( Wang et al. 2024b , a ) .

Let $p,q\in\Delta([0,1])$ be two probability distributions over $[0,1]$. Define the variance of $p$ as

$$ $\displaystyle\mathrm{VaR}_{p}:=\mathbb{E}_{x\sim p}\left[(x-\mathbb{E}_{x\sim p}[x])^{2}\right].$ $$

Then the following inequality holds:

$$ $\displaystyle\left|\mathbb{E}_{x\sim p}[x]-\mathbb{E}_{x\sim q}[x]\right|\lesssim\sqrt{\mathrm{VaR}_{p}\cdot\mathbb{H}^{2}(p\,\|\,q)}+\mathbb{H}^{2}(p\,\|\,q).$ $$

The following lemma provides a concentration inequality for martingale difference sequences without boundedness assumptions, which is essential for handling heavy-tailed or unbounded noise in our analysis.

###### Lemma B.2 (Unbounded Freedman’s inequality, Dzhaparidze and Van Zanten ( 2001 ); Fan et al. ( 2017 ) ) .

Let $\{x_{i}\}_{i=1}^{n}$ be a stochastic process adapted to a filtration $\{\mathcal{G}_{i}\}_{i=1}^{n}$, where $\mathcal{G}_{i}=\sigma(x_{1},\dots,x_{i})$. Suppose $\mathbb{E}[x_{i}\mid\mathcal{G}_{i-1}]=0$ and $\mathbb{E}[x_{i}^{2}\mid\mathcal{G}_{i-1}]<\infty$ almost surely. Then, for any $a,v,y>0$, we have

$$ $\displaystyle\mathbb{P}\left(\sum_{i=1}^{n}x_{i}>a,\ \sum_{i=1}^{n}\left(\mathbb{E}[x_{i}^{2}\mid\mathcal{G}_{i-1}]+x_{i}^{2}\cdot\operatorname{\mathds{1}}\{|x_{i}|>y\}\right)<v^{2}\right)\leq\exp\left(\frac{-a^{2}}{2(v^{2}+ay/3)}\right).$ $$

Equivalently, with probability at least $1-\delta$, the following high-probability bound holds:

$$ $\displaystyle\sum_{i=1}^{n}x_{i}\leq\sqrt{2\sum_{i=1}^{n}\left(\mathbb{E}[x_{i}^{2}\mid\mathcal{G}_{i-1}]+x_{i}^{2}\cdot\operatorname{\mathds{1}}\{|x_{i}|>y\}\right)\log(1/\delta)}+\frac{y}{3}\log(1/\delta).$ $$

The next lemma bounds the sum of truncated random variables in terms of their conditional expectations, which is useful for controlling tail contributions in martingale-adapted processes.

###### Lemma B.3 (Lemma 8, Zhang et al. 2022 ) .

Let $\{x_{i}\}_{i=1}^{n}$ be a nonnegative stochastic process adapted to a filtration $\{\mathcal{G}_{i}\}_{i\geq 1}$, i.e., $x_{i}\geq 0$ almost surely. Then, for any $\delta\in(0,1)$, with probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{i=1}^{n}\min\{x_{i},y\}\leq 4y\log(4/\delta)+4\log(4/\delta)\sum_{i=1}^{n}\mathbb{E}[x_{i}\mid\mathcal{G}_{i-1}].$ $$

We also include the following two auxiliary lemmas that will be used in our analysis.

###### Lemma B.4 (Lemma 11, Wang et al. 2024b ) .

Let $G>0$ and $a<G/2$ be positive constants. Let $\{C_{i}\}_{i=0}^{M}$ be a sequence of positive real numbers, where $M=\lceil\log_{2}(H/G)\rceil$, satisfying:

- •
$C_{i}\leq 2^{i}G+\sqrt{aC_{i+1}}+a$ for all $i\geq 0$;
- •
$C_{i}\leq H$ for all $i\geq 0$, where $H>0$ is a positive constant.

Then it holds that $C_{0}\leq 4G$.

###### Lemma B.5 .

For any random variable $X\in[0,1]$, we have $\operatorname{{\rm Var}}(X^{2})\leq 4\operatorname{{\rm Var}}(X)$.

###### Proof.

Let $Y$ be an independent copy of $X$. Then,

$$ $\displaystyle\operatorname{{\rm Var}}(X^{2})$ $\displaystyle=\tfrac{1}{2}\,\mathbb{E}[(X^{2}-Y^{2})^{2}]=\tfrac{1}{2}\,\mathbb{E}[(X-Y)^{2}(X+Y)^{2}]\leq\tfrac{1}{2}\cdot 4\,\mathbb{E}[(X-Y)^{2}]=2\,\mathbb{E}[(X-Y)^{2}],$ $$

where we used $(X+Y)^{2}\leq 4$ since $X,Y\in[0,1]$.

Next, we observe:

$$ $\displaystyle\mathbb{E}[(X-Y)^{2}]$ $\displaystyle=\mathbb{E}[X^{2}]+\mathbb{E}[Y^{2}]-2\,\mathbb{E}[X]\,\mathbb{E}[Y]=2\,\mathbb{E}[X^{2}]-2\,\mathbb{E}[X]^{2}=2\,\operatorname{{\rm Var}}(X),$ $$

where the last equality follows from $\mathbb{E}[X]=\mathbb{E}[Y]$ and $\mathbb{E}[X^{2}]=\mathbb{E}[Y^{2}]$. Combining both steps, we get

$$ $\displaystyle\operatorname{{\rm Var}}(X^{2})\leq 2\cdot 2\,\operatorname{{\rm Var}}(X)=4\,\operatorname{{\rm Var}}(X),$ $$

which concludes the proof.
∎

###### Lemma B.1 ( Wang et al. 2024b , a ) .

###### Lemma B.2 (Unbounded Freedman’s inequality, Dzhaparidze and Van Zanten ( 2001 ); Fan et al. ( 2017 ) ) .

###### Lemma B.3 (Lemma 8, Zhang et al. 2022 ) .

###### Lemma B.4 (Lemma 11, Wang et al. 2024b ) .

###### Lemma B.5 .

###### Proof.

### B.2 Lemmas on confidence sets

We now introduce a sequence of lemmas that are instrumental for proving Theorems [5.10](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem10).

###### Lemma B.6 .

With probability at least $1-\delta$, the following holds for all $n\in[N]$: $(f^{*},g^{*})\in\mathcal{P}_{n}$, and

$$ $\displaystyle\sum_{i=1}^{n-1}\sum_{k=0}^{m_{i}-1}\mathbb{H}^{2}\left(p_{f_{n},g_{n}}(u_{i},x_{i}(t_{i}^{k}),\Delta_{i,k})\,\|\,p_{f^{*},g^{*}}(u_{i},x_{i}(t_{i}^{k}),\Delta_{i,k})\right)\leq\beta,$ (B.1) $$

where $\beta=\log\left(|\mathcal{F}||\mathcal{G}|N/\delta\right)$.

###### Proof.

We apply Theorem E.4 in Wang et al. (2023) to the function class $\mathcal{F}\times\mathcal{G}$, using delta distributions $D_{i,k}$ centered at $(u_{i},x_{i}(t_{i}^{k}),\Delta_{i,k})$. This guarantees that $(f^{*},g^{*})\in\mathcal{P}_{n}$ and that inequality ([B.1](https://arxiv.org/html/2508.02103v1#A2.E1)) holds with probability at least $1-\delta$, for the specified choice of $\beta$.
∎

Next, we present a key lemma that uses the eluder dimension to bound the accumulated Hellinger distances.

###### Lemma B.7 .

Let $\mathcal{E}_{\ref{lemma:confidence}}$ denote the event described in Lemma [B.6](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem6). Then, under event $\mathcal{E}_{\ref{lemma:confidence}}$, there exists a subset $\mathcal{N}\subseteq[N]$ such that:

- •
$|\mathcal{N}|\leq 13\log^{2}(4\beta\bm{m}_{N})\cdot d_{8\beta\bm{m}_{N}}$;
- •
For each $n\in[N]$, the indicator $n\in\mathcal{N}$ corresponds to a stopping time;
- •
The cumulative Hellinger distance outside $\mathcal{N}$ is bounded:
$\displaystyle\sum_{i\in[N]\setminus\mathcal{N}}\sum_{k=0}^{m_{i}-1}\mathbb{H}^{2}\left(p_{f_{i},g_{i}}(u_{i},x_{i}(t_{i}^{k}),\Delta_{i,k})\,\|\,p_{f^{*},g^{*}}(u_{i},x_{i}(t_{i}^{k}),\Delta_{i,k})\right)\leq 3d_{\bm{m}_{N}}+7d_{\bm{m}_{N}}\beta\log(\bm{m}_{N}).$

###### Proof.

We apply Lemma 6 from Wang et al. (2024b), using the distribution class $p_{f,g}$, the input space $\Pi\times\mathcal{X}\times[T]$, and the function class $\Psi$.
∎

###### Lemma B.6 .

###### Proof.

###### Lemma B.7 .

###### Proof.

### B.3 Lemmas about regret decomposition

The following lemma provides a decomposition of the regret into four interpretable components based on differences between the learned and ground-truth dynamics.

###### Lemma B.8 (Simulation Lemma, Agarwal et al. 2019 ) .

At episode $n$, the following decomposition holds:

$$ $\displaystyle V_{n}(x_{\text{ini}},0)-V_{n}^{*}(x_{\text{ini}},0)=I_{0,n}+\sum_{k=0}^{m_{n}-1}\left(I_{1,n}^{k}+I_{2,n}^{k}+I_{3,n}^{k}+I_{4,n}^{k}\right),$ $$

where the individual terms are defined as follows:

$$ $\displaystyle I_{0,n}$ $\displaystyle:=\int_{0}^{T}b(x_{n}(t),u_{n}(t))\,dt-V_{n}^{*}(x_{\text{ini}},0),$ $\displaystyle I_{1,n}^{k}$ $\displaystyle:=\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})-V_{n}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1}),$ $\displaystyle I_{2,n}^{k}$ $\displaystyle:=\mathbb{E}_{x(\cdot)\sim p^{*}_{n}(x_{n}(t_{n}^{k}))}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u_{n}(t))\,dt\right]-\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x_{n}(t),u_{n}(t))\,dt,$ $\displaystyle I_{3,n}^{k}$ $\displaystyle:=\mathbb{E}_{x\sim p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1}),$ $\displaystyle I_{4,n}^{k}$ $\displaystyle:=\mathbb{E}_{x(\cdot)\sim p_{n}(x_{n}(t_{n}^{k}))}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u_{n}(t))\,dt\right]-\mathbb{E}_{x(\cdot)\sim p^{*}_{n}(x_{n}(t_{n}^{k}))}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u_{n}(t))\,dt\right].$ $$

###### Proof.

We apply a telescoping argument over the discretization grid $\{t_{n}^{k}\}_{k=0}^{m_{n}}$. From the definition of the value function, we have

$$ $\displaystyle V_{n}(x_{\text{ini}},0)$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p_{n}(x_{\text{ini}})}\left[\int_{0}^{T}b(x(t),u_{n}(t))\,dt\right]$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p_{n}(x_{\text{ini}})}\left[\int_{0}^{t_{n}^{1}}b(x(t),u_{n}(t))\,dt\right]+\mathbb{E}_{x\sim p_{n}(x_{\text{ini}},\Delta_{n,0})}V_{n}(x,t_{n}^{1}).$ $$

Subtracting the realized cumulative reward yields

$$ $\displaystyle V_{n}(x_{\text{ini}},0)-\int_{0}^{T}b(x_{n}(t),u_{n}(t))\,dt$ $\displaystyle=\underbrace{\mathbb{E}_{x(\cdot)\sim p_{n}(x_{\text{ini}})}\left[\int_{0}^{t_{n}^{1}}b(x(t),u_{n}(t))\,dt\right]-\int_{0}^{t_{n}^{1}}b(x_{n}(t),u_{n}(t))\,dt}_{I_{2,n}^{0}+I_{4,n}^{0}}$ $\displaystyle\quad+\underbrace{\mathbb{E}_{x\sim p_{n}(x_{\text{ini}},\Delta_{n,0})}V_{n}(x,t_{n}^{1})-\mathbb{E}_{x\sim p^{*}_{n}(x_{\text{ini}},\Delta_{n,0})}V_{n}(x,t_{n}^{1})}_{I_{3,n}^{0}}$ $\displaystyle\quad+\underbrace{\mathbb{E}_{x\sim p^{*}_{n}(x_{\text{ini}},\Delta_{n,0})}V_{n}(x,t_{n}^{1})-V_{n}(x_{n}(t_{n}^{1}),t_{n}^{1})}_{I_{1,n}^{0}}$ $\displaystyle\quad+V_{n}(x_{n}(t_{n}^{1}),t_{n}^{1})-\int_{t_{n}^{1}}^{T}b(x_{n}(t),u_{n}(t))\,dt.$ (B.2) $$

By the Markov property of the Itô SDE, we have

$$ $\displaystyle\mathbb{E}_{x(\cdot)\sim p_{f,g}(u,x)}\left[\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x(t),u(t))\,dt\right]=\mathbb{E}_{x(\cdot)\sim p_{f,g}(u,x)}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u(t))\,dt\right].$ $$

Using this identity recursively up to some $0\leq m^{\dagger}\leq m_{n}$ leads to the expression

$$ $\displaystyle V_{n}(x_{\text{ini}},0)-\int_{0}^{T}b(x_{n}(t),u_{n}(t))\,dt$ $\displaystyle=\sum_{k=0}^{m^{\dagger}-1}\left(I_{1,n}^{k}+I_{2,n}^{k}+I_{3,n}^{k}+I_{4,n}^{k}\right)$ $\displaystyle\quad+\underbrace{\mathbb{E}_{x(\cdot)\sim p_{n}(x_{n}(t_{n}^{m^{\dagger}}))}\left[\int_{t_{n}^{m^{\dagger}}}^{t_{n}^{m^{\dagger}+1}}b(x(t),u(t))\,dt\right]-\int_{t_{n}^{m^{\dagger}}}^{t_{n}^{m^{\dagger}+1}}b(x_{n}(t),u_{n}(t))\,dt}_{I_{2,n}^{m^{\dagger}}+I_{4,n}^{m^{\dagger}}}$ $\displaystyle\quad+\underbrace{\mathbb{E}_{x\sim p_{n}(x_{n}(t_{n}^{m^{\dagger}}),\Delta_{n,m^{\dagger}})}V_{n}(x,t_{n}^{m^{\dagger}+1})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{m^{\dagger}}),\Delta_{n,m^{\dagger}})}V_{n}(x,t_{n}^{m^{\dagger}+1})}_{I_{3,n}^{m^{\dagger}}}$ $\displaystyle\quad+\underbrace{\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{m^{\dagger}}),\Delta_{n,m^{\dagger}})}V_{n}(x,t_{n}^{m^{\dagger}+1})-V_{n}(x_{n}(t_{n}^{m^{\dagger}+1}),t_{n}^{m^{\dagger}+1})}_{I_{1,n}^{m^{\dagger}}}$ $\displaystyle\quad+V_{n}(x_{n}(t_{n}^{m^{\dagger}+1}),t_{n}^{m^{\dagger}+1})-\int_{t_{n}^{m^{\dagger}+1}}^{T}b(x_{n}(t),u_{n}(t))\,dt.$ (B.3) $$

Applying ([B.3](https://arxiv.org/html/2508.02103v1#A2.E3)) with $m^{\dagger}=m_{n}-1$ and noting that $t_{n}^{m_{n}}=T$ and $V_{n}(\cdot,T)=0$, we obtain

$$ $\displaystyle V_{n}(x_{\text{ini}},0)-\int_{0}^{T}b(x_{n}(t),u_{n}(t))\,dt=\sum_{k=0}^{m_{n}-1}\left(I_{1,n}^{k}+I_{2,n}^{k}+I_{3,n}^{k}+I_{4,n}^{k}\right),$ $$

which completes the proof.
∎

###### Lemma B.9 .

Let $I_{0,n},I_{1,n}^{k},\dots,I_{3,n}^{k}$ be terms introduced in Lemma [B.8](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem8). Let $\widetilde{\mathcal{N}}\subseteq[N]$ be an episode index set satisfying $\widetilde{\mathcal{N}}\subseteq[N]\setminus\mathcal{N}$ and satisfying $n\in\widetilde{\mathcal{N}}$ is a stopping time. Then under event $\mathcal{E}_{\ref{lemma:confidence}}$, with probability at least $1-4\delta$, the following bounds hold:

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}I_{0,n}$ $\displaystyle\lesssim\sqrt{\log(1/\delta)\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}_{f^{*},g^{*}}}+\log(1/\delta),$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}I_{1,n}^{k}$ $\displaystyle\lesssim\sqrt{\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\left[V_{n}(x,t_{n}^{k+1})\right]\cdot\log(1/\delta)}+\log(1/\delta),$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}I_{2,n}^{k}$ $\displaystyle\lesssim\sqrt{\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\log(1/\delta)},$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m-1}|I_{3,n}^{k}|$ $\displaystyle\lesssim\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\left[\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\right]}+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N}).$ $$

###### Proof.

First, by Azuma-Bernstein inequality, with probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}I_{0,n}$ $\displaystyle=\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\bigg{(}\int_{t=0}^{T}b(x_{n}(t),u_{n}(t))dt-\mathbb{E}_{x(\cdot)\sim p_{n}^{*}(x_{\text{ini}})}\bigg{[}\int_{t=0}^{T}b(x(t),u(t))dt\bigg{]}\bigg{)}$ $\displaystyle\lesssim\sqrt{\log(1/\delta)\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}_{f^{*},g^{*}}}+\log(1/\delta).$ $$

Next, by definition,

$$ $\displaystyle I_{1,n}^{k}:=\mathbb{E}_{x\sim p_{n}^{*}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\left[V_{n}(x,t_{n}^{k+1})\right]-V_{n}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1}).$ $$

Each $I_{1,n}^{k}$ is a zero-mean random variable whose variance is:

$$ $\mathbb{V}_{x\sim p_{n}^{*}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\left[V_{n}(x,t_{n}^{k+1})\right]\leq 1,$ $$

since $V_{n}\in[0,1]$.

We apply Bernstein’s inequality for zero-mean, bounded ($\leq 1$) random variables. We have with probability at least $1-\delta$,

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}I_{1,n}^{k}$ $\displaystyle=\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}I_{1,n}^{k}$ $\displaystyle\lesssim\sqrt{\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p_{n}^{*}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\left[V_{n}(x,t_{n}^{k+1})\right]\cdot\log(1/\delta)}+\log(1/\delta).$ $\displaystyle=\sqrt{\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p_{n}^{*}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\left[V_{n}(x,t_{n}^{k+1})\right]\cdot\log(1/\delta)}+\log(1/\delta).$ $$

Next, we recall the definition:

$$ $\displaystyle I_{2,n}^{k}:=\mathbb{E}_{x(t)\sim p_{n}^{*}(x_{n}(t_{n}^{k}))}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u_{n}(t))dt\right]-\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x_{n}(t),u_{n}(t))dt.$ $$

Each $I_{2,n}^{k}$ is a martingale difference and satisfies $|I_{2,n}^{k}|\leq 2\Delta_{n,k}$, since $b(x,u)\leq 1$ by Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1).

We apply the Azuma-Hoeffding inequality for bounded martingale differences. With probability at least $1-\delta$:

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}I_{2,n}^{k}$ $\displaystyle=\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}I_{2,n}^{k}$ $\displaystyle\lesssim\sqrt{\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\Delta_{n,k}^{2}\log(1/\delta)}$ $\displaystyle\leq\sqrt{\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\log(1/\delta)}.$ $$

Finally, by Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1), the stage-wise reward is bounded in $[0,1]$. Leveraging Lemma [B.1](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem1), we can bound

$$ $|\mathbb{E}_{x\sim p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\bigl{[}V_{n}(x,t_{n}^{k+1})\bigr{]}-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\bigl{[}V_{n}(x,t_{n}^{k+1})\bigr{]}|$ $$

in terms of the corresponding variance and squared Hellinger distance:

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{3,n}^{k}|$ $\displaystyle=\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}|\mathbb{E}_{x\sim p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\bigl{[}V_{n}(x,t_{n}^{k+1})\bigr{]}-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\bigl{[}V_{n}(x,t_{n}^{k+1})\bigr{]}|$ $\displaystyle\lesssim\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\left[\sqrt{\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\cdot\mathbb{H}^{2}\Big{(}p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\|p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\big{)}}\right]$ $\displaystyle\quad+\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\left[\mathbb{H}^{2}\Big{(}p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\|p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\big{)}\right].$ (B.4) $$

Applying the Cauchy–Schwarz inequality to ([B.4](https://arxiv.org/html/2508.02103v1#A2.E4)) yields

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{3,n}^{k}|$ $\displaystyle\leq\sqrt{\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\left[\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\right]}$ $\displaystyle\quad\cdot\sqrt{\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\left[\mathbb{H}^{2}\Big{(}p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\|p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\big{)}\right]}$ $\displaystyle\quad+\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\left[\mathbb{H}^{2}\Big{(}p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\|p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})\big{)}\right]$ $\displaystyle\leq\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}\left[\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\right]}+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})$ $\displaystyle=\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\left[\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\right]}+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N}),$ $$

where the final inequality follows directly from Lemma [B.7](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem7). ∎

###### Lemma B.8 (Simulation Lemma, Agarwal et al. 2019 ) .

###### Proof.

###### Lemma B.9 .

###### Proof.

### B.4 Lemmas to control total variance

The following lemma provides an upper bound on the cumulative variance of the value function estimates $V_{n}(x,t_{n}^{k+1})$ in terms of the variances of their reference optimal values $V_{n}^{*}(x,t_{n}^{k+1})$, an eluder-dimension-dependent complexity term, and an additional error term.

###### Lemma B.10 .

Let $\widetilde{\mathcal{N}}\subseteq[N]$ be the episode index set defined in Lemma [B.9](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem9). Under the event $\mathcal{E}_{\ref{lemma:mds}}$, with probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})$ $\displaystyle\lesssim\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|.$ $$

###### Proof.

First we have

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})$ $\displaystyle\leq 2\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})$ $\displaystyle\quad+2\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}(x,t_{n}^{k+1}),$ (B.5) $$

where $\widehat{V}_{n}(x,t):=V_{n}(x,t)-V_{n}^{*}(x,t)$.
Next we focus on bound the second term. We introduce a more general high order momentum $C_{i},i=0,\dots,\log(\bm{m}_{N})$, where

$$ $\displaystyle C_{i}:=\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i}}(x,t_{n}^{k+1}).$ $$

Then we have

$$ $\displaystyle C_{i}$ $\displaystyle=\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i+1}}(x,t_{n}^{k+1})-[\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i}}(x,t_{n}^{k+1})]^{2}$ $\displaystyle=\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i+1}}(x,t_{n}^{k+1})-\widehat{V}_{n}^{2^{i+1}}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1})$ $\displaystyle\quad-[\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i}}(x,t_{n}^{k+1})]^{2}+\widehat{V}_{n}^{2^{i+1}}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1})$ $\displaystyle\leq\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\underbrace{\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i+1}}(x,t_{n}^{k+1})-\widehat{V}_{n}^{2^{i+1}}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1})}_{J_{1,n,i}^{k}}$ $\displaystyle\quad\underbrace{-[\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i}}(x,t_{n}^{k+1})]^{2}+\widehat{V}_{n}^{2^{i+1}}(x_{n}(t_{n}^{k}),t_{n}^{k})}_{J_{2,n,i}^{k}},$ (B.6) $$

where the last line holds since we move the index one step earlier and we use the fact $\widehat{V}_{n}(x,t_{n}^{m})=0$.

Next, for $J_{1,n,i}^{k}$, by Azuma-Bernsetin inequality, we have with probability at least $1-\delta$ for all $i=0,\dots,\log(\bm{m}_{N})$,

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}J_{1,n,i}^{k}$ $\displaystyle=\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}J_{1,n,i}^{k}$ $\displaystyle\lesssim\sqrt{\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i+1}}(x,t_{n}^{k+1})\log(\log(\bm{m}_{N})/\delta)}+\log(\log(\bm{m}_{N})/\delta)$ $\displaystyle\leq\sqrt{C_{i+1}\log(\log(\bm{m}_{N})/\delta)}+\log(\log(\bm{m}_{N})/\delta).$ (B.7) $$

For $J_{2,n,i}^{k}$, we have

$$ $\displaystyle J_{2,n,i}^{k}$ $\displaystyle=[\widehat{V}_{n}^{2^{i}}(x_{n}(t_{n}^{k}),t_{n}^{k})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i}}(x,t_{n}^{k+1})][\widehat{V}_{n}^{2^{i}}(x_{n}(t_{n}^{k}),t_{n}^{k})+\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i}}(x,t_{n}^{k+1})]$ $\displaystyle\leq[\widehat{V}_{n}^{2^{i}}(x_{n}(t_{n}^{k}),t_{n}^{k})-[\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i-1}}(x,t_{n}^{k+1})]^{2}][\widehat{V}_{n}^{2^{i}}(x_{n}(t_{n}^{k}),t_{n}^{k})+\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}^{2^{i}}(x,t_{n}^{k+1})]$ $\displaystyle\leq\prod_{j=0}^{i}[\widehat{V}_{n}^{2^{i}}(x_{n}(t_{n}^{k}),t_{n}^{k})+\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}(x,t_{n}^{k+1})]\cdot|\widehat{V}_{n}(x_{n}(t_{n}^{k}),t_{n}^{k})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}(x,t_{n}^{k+1})|$ $\displaystyle\leq 2^{i+1}|\widehat{V}_{n}(x_{n}(t_{n}^{k}),t_{n}^{k})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}(x,t_{n}^{k+1})|,$ (B.8) $$

where we use the fact that $\mathbb{E}X^{2}\geq[\mathbb{E}X]^{2}$. Then taking summation of ([B.8](https://arxiv.org/html/2508.02103v1#A2.E8)) over $n\in\widetilde{\mathcal{N}}$ and $k$, we have

$$ $\displaystyle 2^{-(i+1)}\cdot\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}J_{2,n,i}^{k}$ $\displaystyle\leq\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|\widehat{V}_{n}(x_{n}(t_{n}^{k}),t_{n}^{k})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}\widehat{V}_{n}(x,t_{n}^{k+1})|$ $\displaystyle=\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|V_{n}(x_{n}(t_{n}^{k}),t_{n}^{k})-V_{n}^{*}(x_{n}(t_{n}^{k}),t_{n}^{k})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})$ $\displaystyle\quad+\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})|$ $\displaystyle=\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\bigg{|}\underbrace{\mathbb{E}_{x\sim p_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})}_{I_{3,n}^{k}}$ $\displaystyle\quad+\underbrace{\mathbb{E}_{x(t)\sim p_{n}(x_{n}(t_{n}^{k}))}\bigg{[}\int_{t=0}^{\Delta_{n,k}}b(x(t),u_{n}(t))dt\bigg{]}-\mathbb{E}_{x(t)\sim p_{n}^{*}(x_{n}(t_{n}^{k}))}\bigg{[}\int_{t=0}^{\Delta_{n,k}}b(x(t),u_{n}(t))dt\bigg{]}}_{I_{4,n}^{k}}\bigg{|}$ $\displaystyle\leq\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\bigg{(}\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\left[\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\right]\bigg{)}}$ $\displaystyle\quad+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|,$ (B.9) $$

where the last inequality holds due to the upper bounds of $|I_{3,n}^{k}|$ obtained in Lemma [B.9](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem9). Combining ([B.6](https://arxiv.org/html/2508.02103v1#A2.E6)), ([B.7](https://arxiv.org/html/2508.02103v1#A2.E7)) and ([B.9](https://arxiv.org/html/2508.02103v1#A2.E9)), we have $a<G/2$, $C_{i}\leq 2^{i}G+\sqrt{aC_{i+1}}+a$ and $C_{i}\leq H=\bm{m}_{N}$, where

$$ $\displaystyle G$ $\displaystyle:=\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\bigg{(}\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\left[\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\right]\bigg{)}}$ $\displaystyle\quad+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|,$ $\displaystyle a$ $\displaystyle:=\log(\log(\bm{m}_{N})/\delta).$ $$

Therefore, by Lemma [B.4](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem4), we have

$$ $\displaystyle C_{0}$ $\displaystyle\lesssim G.$ (B.10) $$

Finally, substituting ([B.10](https://arxiv.org/html/2508.02103v1#A2.E10)) back to ([B.5](https://arxiv.org/html/2508.02103v1#A2.E5)), we have

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})$ $\displaystyle\lesssim\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|$ $\displaystyle\quad+\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\bigg{(}\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\left[\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})\right]\bigg{)}}.$ $$

Using the fact that $x\lesssim\sqrt{ax}+b\Rightarrow x\lesssim a+b$, we obtain our final bound.
∎

The following lemma bounds the cumulative variance of the optimal value function $V_{n}^{*}$ by the measurement gaps.

###### Lemma B.11 .

With probability at least $1-\delta$, for all $n\in[N]$, we have

$$ $\displaystyle\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\lesssim\log(N/\delta)+\sqrt{\log(N/\delta)\max_{1\leq n\leq N}\bm{\Delta}_{n}^{2}}.$ (B.11) $$

###### Proof.

Fix any $n\in[N]$. For simplicity, define $J_{n}:=\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})$. We begin by expanding the variance:

$$ $\displaystyle J_{n}$ $\displaystyle=\sum_{k=0}^{m_{n}-1}\left[\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})^{2}-\left(\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\right)^{2}\right]$ $\displaystyle\leq\sum_{k=0}^{m_{n}-1}\biggl{\{}\underbrace{\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})^{2}-V_{n}^{*}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1})^{2}}_{J_{1,n}^{k}}$ $\displaystyle\quad+\underbrace{V_{n}^{*}(x_{n}(t_{n}^{k}),t_{n}^{k})^{2}-\left(\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\right)^{2}}_{J_{2,n}^{k}}\biggr{\}},$ (B.12) $$

where the inequality uses the monotonicity $V_{n}^{*}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1})\leq V_{n}^{*}(x_{n}(t_{n}^{k}),t_{n}^{k})$.

By the Azuma–Bernstein inequality, with probability at least $1-\delta/N$,

$$ $\displaystyle\sum_{k=0}^{m_{n}-1}J_{1,n}^{k}$ $\displaystyle\lesssim\sqrt{\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})^{2}\cdot\log(N/\delta)}+\log(N/\delta)$ $\displaystyle\leq 2\sqrt{\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\cdot\log(N/\delta)}+\log(N/\delta)$ $\displaystyle=2\sqrt{J_{n}\log(N/\delta)}+\log(N/\delta),$ (B.13) $$

where the second inequality follows from Lemma [B.5](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem5).

For $J_{2,n}^{k}$, using ([4.1](https://arxiv.org/html/2508.02103v1#S4.E1)) and the Markov property of Itô’s SDE, we write

$$ $\displaystyle J_{2,n}^{k}$ $\displaystyle=\left[V_{n}^{*}(x_{n}(t_{n}^{k}),t_{n}^{k})-\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\right]$ $\displaystyle\quad\cdot\left[V_{n}^{*}(x_{n}(t_{n}^{k}),t_{n}^{k})+\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\right]$ $\displaystyle=\left[\mathbb{E}_{x(\cdot)\sim p^{*}_{n}(x_{n}(t_{n}^{k}))}\int_{t=0}^{\Delta_{n,k}}b(x(t),u(t))dt\right]$ $\displaystyle\quad\cdot\left[V_{n}^{*}(x_{n}(t_{n}^{k}),t_{n}^{k})+\mathbb{E}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\right]$ $\displaystyle\lesssim\mathbb{E}_{x(\cdot)\sim p^{*}_{n}(x_{n}(t_{n}^{k}))}\int_{t=0}^{\Delta_{n,k}}b(x(t),u(t))dt,$ (B.14) $$

since $V_{n}^{*}\leq 1$. Hence, with probability at least $1-\delta/N$, we have

$$ $\displaystyle\sum_{k=0}^{m_{n}-1}J_{2,n}^{k}$ $\displaystyle\lesssim\sum_{k=0}^{m_{n}-1}\biggl{\{}\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x_{n}(t),u_{n}(t))dt$ $\displaystyle\quad+\left[\mathbb{E}_{x(\cdot)\sim p^{*}_{n}(x_{n}(t_{n}^{k}))}\int_{0}^{\Delta_{n,k}}b(x(t),u(t))dt-\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x_{n}(t),u_{n}(t))dt\right]\biggr{\}}$ $\displaystyle\leq 1+\sum_{k=0}^{m_{n}-1}\left[\mathbb{E}_{x(\cdot)\sim p^{*}_{n}(x_{n}(t_{n}^{k}))}\int_{0}^{\Delta_{n,k}}b(x(t),u(t))dt-\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x_{n}(t),u_{n}(t))dt\right]$ $\displaystyle\lesssim 1+\sqrt{\bm{\Delta}_{n}^{2}\log(N/\delta)},$ (B.15) $$

where the second inequality follows from Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1), and the third comes from Azuma-Hoeffding inequality using the bound $\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x(t),u(t))dt\leq\Delta_{n,k}$.

Substituting ([B.13](https://arxiv.org/html/2508.02103v1#A2.E13)) and ([B.15](https://arxiv.org/html/2508.02103v1#A2.E15)) into ([B.12](https://arxiv.org/html/2508.02103v1#A2.E12)), and replacing each individual confidence level $1-\delta/N$ in ([B.13](https://arxiv.org/html/2508.02103v1#A2.E13)) and ([B.15](https://arxiv.org/html/2508.02103v1#A2.E15)) with $1-\delta/(2N)$ (which does not affect the order of the bounds), we can apply a union bound to obtain an overall high-probability guarantee of $1-\delta$. Consequently, with probability at least $1-\delta$, for all $n\in[N]$,

$$ $\displaystyle J_{n}\lesssim\sqrt{J_{n}\log(N/\delta)}+1+\sqrt{\bm{\Delta}_{n}^{2}\log(N/\delta)}$ $\displaystyle\Rightarrow J_{n}\lesssim\log(N/\delta)+\sqrt{\bm{\Delta}_{n}^{2}\log(N/\delta)}\leq\log(N/\delta)+\sqrt{\log(N/\delta)\max_{1\leq n\leq N}\bm{\Delta}_{n}^{2}}.$ $$

∎

The following lemma provides a global bound on the cumulative variance of the optimal value functions $V_{n}^{*}$ over all episodes. It shows that this quantity is controlled by the total variance and measurement gaps.

###### Lemma B.12 .

Under event $\mathcal{E}_{\ref{lemma:var1}}$, with probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{n=1}^{N}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})\lesssim\log^{2}(N/\delta)\bigg{(}1+\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}+\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\bigg{)}.$ $$

###### Proof.

We define $J_{n}:=\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})$ following Lemma [B.11](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem11). Then by ([B.11](https://arxiv.org/html/2508.02103v1#A2.E11)) we have

$$ $\displaystyle J_{n}\lesssim\log(N/\delta)+\sqrt{\log(N/\delta)\max_{1\leq n\leq N}\bm{\Delta}_{n}^{2}}.$ $$

Next we prove that the conditional expectation of $J_{n}$ can be bounded. First, following ([4.1](https://arxiv.org/html/2508.02103v1#S4.E1)),

$$ $\displaystyle V_{n}^{*}(x,t)$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p_{n}^{*}(x)}\biggl{[}\int_{t}^{T}b(x(t),u(t))dt\biggr{]}$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p_{n}^{*}(x)}\biggl{[}\int_{t}^{t+\Delta}b(x(t),u(t))dt\biggr{]}+\mathbb{E}_{x^{\prime}\sim p_{n}^{*}(x,\Delta)}V_{n}^{*}(x^{\prime},t+\Delta)$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p_{n}^{*}(x)}\biggl{[}\int_{0}^{\Delta}b(x(t),u(t))dt\biggr{]}+\mathbb{E}_{x^{\prime}\sim p_{n}^{*}(x,\Delta)}V_{n}^{*}(x^{\prime},t+\Delta).$ (B.16) $$

Then, we have

$$ $\displaystyle\operatorname{{\rm Var}}^{u_{n}}$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p_{n}^{*}(x_{\text{ini}})}\left[\sum_{k=0}^{m_{n}-1}\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x(t),u(t))dt-V_{n}^{*}(x_{\text{ini}},0)\right]^{2}$ $\displaystyle=\mathbb{E}_{x(\cdot)\sim p^{*}_{n}(x_{\text{ini}})}\biggl{[}\sum_{k=0}^{m_{n}-1}\underbrace{\int_{t_{n}^{k}}^{t_{n}^{k+1}}b(x(t),u(t))dt+V_{n}^{*}(x_{n}(t_{n}^{k+1}),t_{n}^{k+1})-V_{n}^{*}(x_{n}(t_{n}^{k}),t_{n}^{k})}_{J_{n,k}}\biggr{]}^{2}$ $\displaystyle=\mathbb{V}_{x(\cdot)\sim p^{*}_{n}(x_{\text{ini}})}\left[\sum_{k=0}^{m_{n}-1}J_{n,k}\right]$ $\displaystyle=\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x_{\text{ini}})}\left[J_{n,k}\right].$ (B.17) $$

The first equality follows immediately from the definition of variance, and the second comes from ([B.16](https://arxiv.org/html/2508.02103v1#A2.E16)). Next, on each subinterval $[t_{n}^{k},t_{n}^{k+1}]$ we introduce the *temporal increment* $J_{n,k}$, for which, by construction, $\mathbb{E}[J_{n,k}]=\mathbb{E}[J_{n,k}|x_{n}(t_{n}^{k})]=0$, yielding the third equality. Then, $\{J_{n,k}\}_{k=0}^{m_{n}-1}$ is a martingale-difference sequence with respect to the natural filtration
$\mathcal{F}_{k}=\sigma\bigl{(}x_{n}(t_{n}^{0}),\dots,x_{n}(t_{n}^{k})\bigr{)}$, so orthogonality implies

$$ $\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x_{\text{ini}})}\left[\sum_{k=0}^{m_{n}-1}J_{n,k}\right]=\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x_{\text{ini}})}[J_{n,k}].$ $$

Moreover, by the law of total variance, together with $\mathbb{E}[J_{n,k}|x_{n}(t_{n}^{k})]=0$, we have

$$ $\displaystyle\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x_{\text{ini}})}\left[J_{n,k}\right]$ $\displaystyle=\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}\bigl{[}\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x)}[J_{n,k}|x]\bigr{]}+\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x)}\bigl{[}\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}[J_{n,k}|x]\bigr{]}$ $\displaystyle=\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}\bigl{[}\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x)}[J_{n,k}|x]\bigr{]}$ $\displaystyle=\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}\left[\mathbb{V}_{\begin{subarray}{c}x(\cdot)\sim p_{n}^{*}(x),\\ x^{\prime}\sim p_{n}^{*}(x,\Delta_{n,k})\end{subarray}}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u(t))dt+V_{n}^{*}(x^{\prime},t_{n}^{k+1})\right]\right].$ (B.18) $$

Furthermore, by Assumption [5.1](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem1) we have $\int_{0}^{\Delta_{n,k}}b(x_{n}(t),u_{n}(t))dt\leq\Delta_{n,k}$ for each $\Delta_{n,k}$. Thus,

$$ $\displaystyle\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}\left[\mathbb{V}_{\begin{subarray}{c}x(\cdot)\sim p_{n}^{*}(x),\\ x^{\prime}\sim p_{n}^{*}(x,\Delta_{n,k})\end{subarray}}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u(t))dt+V_{n}^{*}(x^{\prime},t_{n}^{k+1})\right]\right]$ $\displaystyle\leq 2\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}\left[\mathbb{V}_{x^{\prime}\sim p_{n}^{*}(x,\Delta_{n,k})}\left[V_{n}^{*}(x^{\prime},t_{n}^{k+1})\right]\right]$ $\displaystyle\quad+2\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}\left[\mathbb{V}_{x(\cdot)\sim p_{n}^{*}(x)}\left[\int_{0}^{\Delta_{n,k}}b(x(t),u(t))dt\right]\right]$ (B.19) $\displaystyle\leq 2\mathbb{E}_{x\sim p_{n}^{*}(x_{\text{ini}},t_{n}^{k})}\left[\mathbb{V}_{x^{\prime}\sim p_{n}^{*}(x,\Delta_{n,k})}\left[V_{n}^{*}(x^{\prime},t_{n}^{k+1})\right]\right]+2\Delta_{n,k}^{2}.$ (B.20) $$

Here, ([B.19](https://arxiv.org/html/2508.02103v1#A2.E19)) follows from the fact that $\operatorname{{\rm Var}}(a+b)=\operatorname{{\rm Var}}(a)+\operatorname{{\rm Var}}(b)+2\text{Cov}(a,b)\leq\operatorname{{\rm Var}}(a)+\operatorname{{\rm Var}}(b)+2\sqrt{\operatorname{{\rm Var}}(a)\cdot\operatorname{{\rm Var}}(b)}\leq 2\operatorname{{\rm Var}}(a)+2\operatorname{{\rm Var}}(b)$.
Summing ([B.20](https://arxiv.org/html/2508.02103v1#A2.E20)) over $k=0,\dots,m_{n}-1$.

Thus we have, for each $n$,

$$ $\displaystyle\mathbb{E}[J_{n}|J_{n-1},\dots,J_{1}]\lesssim\operatorname{{\rm Var}}^{u_{n}}+\bm{\Delta}_{n}^{2}.$ (B.21) $$

Applying Lemma [B.3](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem3) to ([B.21](https://arxiv.org/html/2508.02103v1#A2.E21)) then yields

$$ $\displaystyle\sum_{n=1}^{N}\min\{J_{n},y\}$ $\displaystyle\lesssim y\log(1/\delta)+\log(1/\delta)\sum_{n=1}^{N}\mathbb{E}[J_{n}|J_{n-1},\dots,J_{1}]$ $\displaystyle\lesssim y\log(1/\delta)+\log(1/\delta)\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}+\log(1/\delta)\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}.$ (B.22) $$

Finally, we plug $y$ as the upper bound of $J_{n}$ in ([B.11](https://arxiv.org/html/2508.02103v1#A2.E11)) in ([B.22](https://arxiv.org/html/2508.02103v1#A2.E22)), leading to

$$ $\displaystyle\sum_{n=1}^{N}J_{n}$ $\displaystyle\lesssim\log^{2}(N/\delta)\bigg{(}1+\sqrt{\max_{1\leq n\leq N}\bm{\Delta}_{n}^{2}}+\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}+\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\bigg{)}$ $\displaystyle\lesssim\log^{2}(N/\delta)\bigg{(}1+\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}+\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\bigg{)},$ $$

where for the second inequality we use the fact $\sqrt{x}\leq 1+x$, thus completing the proof.
∎

The following lemma gives the final high-probability upper bound on the cumulative regret in terms of decomposition results established in previous lemmas.

###### Lemma B.13 .

Let $\widetilde{\mathcal{N}}\subseteq[N]$ be the episode index set defined in Lemma [B.9](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem9). Under events $\mathcal{E}_{\ref{lemma:confidence}},\mathcal{E}_{\ref{lemma:mds}},\mathcal{E}_{\ref{lemma:var3}},\mathcal{E}_{\ref{lemma:var1}},\mathcal{E}_{\ref{lemma:var2}}$, we have

$$ $\displaystyle\text{Regret}(N)$ $\displaystyle\lesssim\log(N/\delta)\bigg{(}\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\bigg{(}\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}_{f^{*},g^{*}}+\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\bigg{)}}$ $\displaystyle\quad+N-|\widetilde{\mathcal{N}}|+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|\bigg{)}.$ $$

###### Proof.

By Lemma [B.6](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem6), we have $R_{f^{*},g^{*}}(u_{n})\leq R_{f_{n},g_{n}}(u_{n})$. For any $n\in\widetilde{\mathcal{N}}$, by Lemma [B.8](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem8), we have

$$ $\displaystyle R_{f^{*},g^{*}}(u_{n})-R_{f^{*},g^{*}}(u_{n})$ $\displaystyle\leq R_{f_{n},g_{n}}(u_{n})-R_{f^{*},g^{*}}(u_{n})$ $\displaystyle\leq\min\bigg{\{}1,\sum_{k=0}^{m-1}(I_{1,n}^{k}+I_{2,n}^{k}+I_{3,n}^{k}+I_{4,n}^{k})+I_{0,n}\bigg{\}}.$ $$

Then we can bound the regret as

$$ $\displaystyle\text{Regret}(N)$ $\displaystyle\lesssim N-|\widetilde{\mathcal{N}}|+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m-1}(I_{1,n}^{k}+I_{2,n}^{k}+I_{3,n}^{k}+I_{4,n}^{k})+I_{0,n}.$ (B.23) $$

From Lemma [B.9](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem9), we have

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\bigg{(}I_{0,n}+\sum_{k=0}^{m-1}I_{1,n}^{k}+I_{2,n}^{k}+I_{3,n}^{k}+I_{4,n}^{k}\bigg{)}$ $\displaystyle\lesssim d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta)}\left[V_{n}(x,t_{n}^{k+1})\right]}$ $\displaystyle\quad+\log(1/\delta)\bigg{(}\sqrt{\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}_{f^{*},g^{*}}}+\sqrt{\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}}\bigg{)}+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|.$ (B.24) $$

From Lemma [B.10](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem10), we have

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}(x,t_{n}^{k+1})$ $\displaystyle\lesssim\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{V}_{x\sim p^{*}_{n}(x_{n}(t_{n}^{k}),\Delta_{n,k})}V_{n}^{*}(x,t_{n}^{k+1})+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|$ $\displaystyle\lesssim\log^{2}(N/\delta)\bigg{(}1+\sum_{n=1}^{N}\operatorname{{\rm Var}}^{u_{n}}_{f^{*},g^{*}}+\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\bigg{)}+d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})+\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|,$ (B.25) $$

where the second inequality holds due to Lemma [B.12](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem12). Substituting ([B.25](https://arxiv.org/html/2508.02103v1#A2.E25)) into ([B.24](https://arxiv.org/html/2508.02103v1#A2.E24)), then substituting them into ([B.23](https://arxiv.org/html/2508.02103v1#A2.E23)), we have our final regret bound.
∎

###### Lemma B.10 .

###### Proof.

###### Lemma B.11 .

###### Proof.

###### Lemma B.12 .

###### Proof.

###### Lemma B.13 .

###### Proof.

### B.5 Proof of Theorem 5.10

We first have our concentration lemma.

###### Lemma B.14 .

With probability at least $1-\delta$, we have for all $n\in[N]$, $(f^{*},g^{*})\in\mathcal{P}_{n}$, and

$$ $\displaystyle\sum_{i=1}^{n-1}\sum_{k=0}^{m_{i}-1}\mathbb{H}^{2}(p_{f_{n},g_{n}}(u_{i},x_{i}(t_{i}^{k}),\widehat{\Delta}_{i,k})\|p_{f^{*},g^{*}}(u_{i},x_{i}(t_{i}^{k}),\widehat{\Delta}_{i,k}))\leq\beta,$ (B.26) $$

where $\beta=\log(2|\mathcal{F}||\mathcal{G}|N/\delta)$.

###### Proof.

We apply Theorem E.4 in Wang et al. (2023) with $D_{i,k}$ being the delta distribution at $(u_{i},x_{i}(t_{i}^{k}),\widehat{\Delta}_{i,k})$ guarantees $(f^{*},g^{*})\in\widehat{\mathcal{P}}_{n}$ and ([B.26](https://arxiv.org/html/2508.02103v1#A2.E26)) holds with probability at least $1-\delta/2$. Taking a union bound over the two events, we conclude that with probability at least $1-\delta$, both statements hold simultaneously.
∎

Next we have the following lemma.

###### Lemma B.15 .

Let the event $\mathcal{E}_{\ref{lemma:confidence}}$ be the event of Lemma [B.6](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem6). Then under event $\mathcal{E}_{\ref{lemma:confidence}}$, there exists a set $\mathcal{N}_{1}\subseteq[N]$ such that

- •
We have $|\mathcal{N}_{1}|\leq 13\log^{2}(4\beta\bm{m}_{N})\cdot d_{8\beta\bm{m}_{N}}$.
- •
For any $n\in[N]$, $n\in\mathcal{N}_{1}$ is a stopping time.
- •
We have
$\displaystyle\sum_{i\in[N]\setminus\mathcal{N}_{1}}\sum_{k=0}^{m_{i}-1}\mathbb{H}^{2}\left(p_{f_{i},g_{i}}(u_{i},x_{i}(t_{i}^{k}),\widehat{\Delta}_{i,k})\|p_{f^{*},g^{*}}(u_{i},x_{i}(t_{i}^{k}),\widehat{\Delta}_{i,k})\right)\leq 3d_{\bm{m}_{N}}+7d_{\bm{m}_{N}}\beta\log(\bm{m}_{N}).$

###### Proof.

We apply Lemma 6 in Wang et al. (2024b) here with the distribution class $p_{f,g}$, input space $\Pi\times\mathcal{X}\times[T]$ and function class $\Psi$.
∎

Next is our key lemma.

###### Lemma B.16 .

Let $\widetilde{\mathcal{N}}\subseteq[N]$ be an episode index set satisfying $\widetilde{\mathcal{N}}\subseteq[N]\setminus\mathcal{N}_{1}$. Under event $\mathcal{E}_{\ref{lemma:confidence}}$, with probability at least $1-\delta$, the quantities $I_{4,n}^{k}$ introduced in introduced in Lemma [B.8](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem8) satisfy

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m-1}|I_{4,n}^{k}|\lesssim\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}}.$ $$

###### Proof.

Fix $n\in\widetilde{\mathcal{N}}$ and $0\leq k<m_{n}$. We have

$$ $\displaystyle|I_{4,n}^{k}|$ $\displaystyle=\bigg{|}\mathbb{E}_{x(\cdot)\sim p_{n}(x_{n}(t_{n}^{k}))}\bigg{[}\int_{t=0}^{\Delta_{n,k}}b(x(t),u(t))dt\bigg{]}-\mathbb{E}_{x(\cdot)\sim p_{n}^{*}(x_{n}(t_{n}^{k}))}\bigg{[}\int_{t=0}^{\Delta_{n,k}}b(x(t),u(t))dt\bigg{]}\bigg{|}$ $\displaystyle\leq\int_{t=0}^{\Delta_{n,k}}\bigg{|}\mathbb{E}_{x\sim p_{n}^{*}(x_{n}(t_{n}^{k}),t)}b(x,u)-\mathbb{E}_{x\sim p_{n}(x_{n}(t_{n}^{k}),t)}b(x,u)\bigg{|}dt$ $\displaystyle\lesssim\int_{t=0}^{\Delta_{n,k}}\sqrt{\mathbb{V}_{x\sim p_{n}^{*}(x_{n}(t_{n}^{k}),t)}b(x,u)\mathbb{H}^{2}(p_{n}^{*}(x_{n}(t_{n}^{k}),t)\|p_{n}(x_{n}(t_{n}^{k}),t))}$ $\displaystyle\quad+\mathbb{H}^{2}(p_{n}^{*}(x_{n}(t_{n}^{k}),t)\|p_{n}(x_{n}(t_{n}^{k}),t))dt$ $\displaystyle\lesssim\int_{t=0}^{\Delta_{n,k}}\mathbb{H}(p_{n}^{*}(x_{n}(t_{n}^{k}),t)\|p_{n}(x_{n}(t_{n}^{k}),t))dt$ $\displaystyle=\underbrace{\Delta_{n,k}\cdot\mathbb{H}(p_{n}^{*}(x_{n}(t_{n}^{k}),\widehat{\Delta}_{n,k})\|p_{n}(x_{n}(t_{n}^{k}),\widehat{\Delta}_{n,k}))}_{J_{1,n}^{k}}$ $\displaystyle\quad+\underbrace{\int_{t=0}^{\Delta_{n,k}}\mathbb{H}(p_{n}^{*}(x_{n}(t_{n}^{k}),t)\|p_{n}(x_{n}(t_{n}^{k}),t))dt-\Delta_{n,k}\mathbb{H}(p_{n}^{*}(x_{n}(t_{n}^{k}),\widehat{\Delta}_{n,k})\|p_{n}(x_{n}(t_{n}^{k}),\widehat{\Delta}_{n,k}))}_{J_{2,n}^{k}},$ $$

where we use the fact that $b\leq 1$ and $\mathbb{H}\leq 1$.
For $J_{1,n}^{k}$, we have:

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}J_{1,n}^{k}$ $\displaystyle\leq\sqrt{\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\Delta_{n,k}^{2}}\cdot\sqrt{\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\mathbb{H}^{2}(p_{n}^{*}(x_{n}(t_{n}^{k}),\widehat{\Delta}_{n,k})\|p_{n}(x_{n}(t_{n}^{k}),\widehat{\Delta}_{n,k}))}$ $\displaystyle\leq\sqrt{d_{\bm{m}_{N}}\beta\log(\bm{m}_{N})\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}},$ (B.27) $$

where the first inequality is by Cauchy-Schrawz inequality and the last one holds due to Lemma [B.7](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem7).

For $\{J_{2,n}^{k}\}_{n,k}$, because $\widehat{\Delta}_{n,k}$ is sampled uniformly from $[0,\Delta_{n,k}]$,
the sequence $\{J_{2,n}^{k}\}_{n,k}$ forms a martingale difference sequence (MDS).
Noting $|J_{2,n}^{k}|\leq 2\Delta_{n}^{k}$ we can apply Azuma-Hoeffding inequality to $J_{2,n}^{k}$,
which infers that with probability at least $1-\delta$,

$$ $\displaystyle\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}J_{2,n}^{k}=\sum_{n=1}^{N}\operatorname{\mathds{1}}(n\in\widetilde{\mathcal{N}})\sum_{k=0}^{m_{n}-1}J_{2,n}^{k}\lesssim\sqrt{\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}\Delta_{n,k}^{2}\log(1/\delta)}\leq\sqrt{\sum_{n=1}^{N}\bm{\Delta}_{n}^{2}\log(1/\delta)}.$ (B.28) $$

Therefore, from ([B.27](https://arxiv.org/html/2508.02103v1#A2.E27)) and ([B.28](https://arxiv.org/html/2508.02103v1#A2.E28)), we obtain our bound. ∎

Then we have our final proof of Theorem [5.10](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem10).

###### Proof of Theorem 5.10 .

We set $\widetilde{\mathcal{N}}=[N]\setminus(\mathcal{N}\cup\mathcal{N}_{1})$. Since both $n\in\mathcal{N},n\in\mathcal{N}_{1}$ are stopping time, then $\widetilde{\mathcal{N}}$ is also a stopping time. Clearly we have $\widetilde{\mathcal{N}}\subseteq[N]\setminus\mathcal{N}$ and $\widetilde{\mathcal{N}}\subseteq[N]\setminus\mathcal{N}_{1}$, thus we can apply both Lemma [B.13](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem13) and [B.16](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem16). Then substituting the bound of $\sum_{n\in\widetilde{\mathcal{N}}}\sum_{k=0}^{m_{n}-1}|I_{4,n}^{k}|$ from Lemma [B.16](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem16) into Lemma [B.13](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem13) and using the fact that

$$ $\displaystyle N-|\widetilde{\mathcal{N}}|\leq|\mathcal{N}|+|\mathcal{N}_{1}|\leq 26\log^{2}(4\beta\bm{m}_{N})\cdot d_{8\beta\bm{m}_{N}}$ $$

concludes our proof. Here, the second inequality holds due to the bounds of $|\mathcal{N}|$ in Lemma [B.6](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem6) and $|\mathcal{N}_{1}|$ in Lemma [B.14](https://arxiv.org/html/2508.02103v1#A2.Thmtheorem14).
∎

###### Lemma B.14 .

###### Proof.

###### Lemma B.15 .

###### Proof.

###### Lemma B.16 .

###### Proof.

###### Proof of Theorem 5.10 .

## Appendix C Numerical Experiments

### C.1 Implementation details

We discuss several issues about practical implementation of Algorithm [1](https://arxiv.org/html/2508.02103v1#alg1) here. The first and major one is how to compute the conditional probability density function $p_{f,g}(x_{i}(t_{i}^{k+1})\mid u_{i},x_{i}(t_{i}^{k}),\Delta_{i,k})$ where $\Delta_{i,k}=t_{i}^{k+1}-t_{i}^{k}$. Direct maximization of such conditional log-likelihood is infeasible because the normalizing constant of the SDE transition density is unknown. In practice, we adopt the score matching method (Hyvärinen and Dayan, 2005) to tackle such task in continuous-time, which can eliminate the intractable term by minimizing the Fisher divergence between the model score and the (unknown) data score, and is proven to be as a tractable and computationally efficient surrogate of MLE (Pabbaraju et al., 2023). Here, we follow the sliced formulation of score matching (Song et al., 2020) and obtain the unbiased and computationally light estimators for the drift-diffusion parameters $(f_{\theta},g_{\theta})$ used in Algorithm [1](https://arxiv.org/html/2508.02103v1#alg1).

The second major challenge is, given the estimates of the drift term $f$ and the diffusion term $g$, how to find the best policy $u_{n}$. Using the learnt SDE, we generate model roll-outs and apply an actor-critic update in continuous time:
the critic $V_{\xi}$ minimizes the mean-squared TD error, while the actor $u_{\phi}$ maximizes discounted $n$-step returns via stochastic gradient ascent.
Our implementation follows deterministic policy gradients (Silver et al., 2014; Lillicrap et al., 2015) but back-propagates through the ODE to obtain exact gradients, similar to neural ODE policy evaluation in continuous time (Chen et al., 2018; Yildiz et al., 2021).

As outlined above, we preserve the core structure of the continuous-time model-based RL algorithm from Yildiz et al. (2021)-augmented with additive Gaussian noise to cast the environment dynamics as an SDE rather than an ODE-but substitute its original dynamic-learning objective with a continuous-time sliced score matching (SSM) loss (Song et al., 2020). Specifically, over each of the $N_{\mathrm{dyn}}$ gradient update steps, we:

- 1.
Draw a batch size $B_{\text{dyn}}$ of length-$H_{\text{dyn}}$ subsequences
$\bigl{\{}\left(x_{i}(t_{0}),\,u_{i}(t_{0})\right),\dots,\left(x_{i}(t_{H_{\text{dyn}}}),\,u_{i}(t_{H_{\text{dyn}}})\right)\bigr{\}}_{i=1}^{B_{\mathrm{dyn}}}\sim\mathcal{D}.$
Here $x_{i}(t_{k})$ is the state at measurement time $t_{k}$, $u_{i}(t_{k})=u\bigl{(}x_{i}(t_{k})\bigr{)}$ is the control input under policy $u$ at time $t_{k}$, and $\mathcal{D}$ is the training data set.
- 2.
For each subsequence $i$ and each time-step $k=0,\dots,H_{\text{dyn}}-1$:
(a)
Compute the interval length
$\Delta t_{i}^{k}=t_{i}^{k+1}-t_{i}^{k}.$
(b)
Compute the conditional mean of each interval via ODE integration
$\mu_{\theta}^{(i,k)}=\mathrm{ODEInt}\bigl{(}f_{\theta}\bigl{(}\cdot,\,u_{i}(t_{k})\bigr{)},\;x_{i}(t_{k}),\;[0,\Delta t_{i}^{k}]\bigr{)},$
where $\mathrm{ODEInt}(\cdot)$ refers to a numerical ordinary-differential-equation solver (in our case the Dormand-Prince "RK45" integrator), $f_{\theta}(\cdot,\,u_{i}(t_{k}))$ is the learned drift network which follows the control input policy $u_{i}(t_{k})$, $x_{i}(t_{k})$ is the initial state of the $i$-th sample $k$-th interval, and $\left[0,\Delta t_{i}^{k}\right]$ is the relative time-interval over which we integrate.
(c)
For each interval, evaluate the instantaneous covariance
$\Sigma_{\theta}^{(i,k)}=\bigl{(}g_{\theta}\bigl{(}x_{i}(t_{k}),\,u_{i}(t_{k})\bigr{)}\bigr{)}^{2}\,\Delta t_{i}^{k}.$
In other words, we first square the instantaneous noise-scale vector elementwise to obtain the variance rate, then acquire the diagonal covariance matrix by multiplying the time interval length.
(d)
Form the model score of each sample at interval endpoint $x_{i}(t_{k+1})$:
$s_{\theta}^{(i,k)}=-\,\left(\Sigma_{\theta}^{(i,k)}\right)^{-1}\left(x_{i}(t_{k+1})-\mu_{\theta}^{(i,k)}\right).$
(e)
Draw $M_{\mathrm{proj}}$ Rademacher vectors $v_{i,k,m}\in\{\pm 1\}^{d}$, and compute
$\ell_{i,k,m}=\frac{1}{2}\left\|s_{\theta}^{(i,k)}\right\|^{2}\;+\;v_{i,k,m}^{\top}\nabla_{x}\bigl{[}v_{i,k,m}^{\top}s_{\theta}^{(i,k)}\bigr{]}\bigg{|}_{x=x_{i}(t_{k+1})},\quad m=1,\dots,M_{\mathrm{proj}}.$
In other words, for each random projection, we measure both the "energy" of the score ($\tfrac{1}{2}\|s_{\theta}^{(i,k)}\|^{2}$) and its directional derivative along $v_{i,k,m}$, which together provide an unbiased Monte Carlo estimate of the sliced score matching loss on that projection.
- 3.
Average to get the batched sliced score matching loss
$\mathcal{J}(\theta)=\frac{1}{B_{\mathrm{dyn}}\>H_{\mathrm{dyn}}\>M_{\mathrm{proj}}}\sum_{i=1}^{B_{\mathrm{dyn}}}\sum_{k=0}^{H_{\mathrm{dyn}}-1}\sum_{m=1}^{M_{\mathrm{proj}}}\>\ell_{i,k,m},$
and update $\theta$ with AdamW optimizer (Kingma, 2014; Loshchilov and Hutter, 2017).

### C.2 Numerical simulation

#### Main results.

We conduct numerical experiments to validate our theoretical claims, running CT-MLE on the three classical control problem in the Gymnasium environment (Brockman et al., 2016; Towers et al., 2024): Pendulum, Cart Pole and Acrobot. Since these environments are originally deterministic, we follow Treven et al. (2024b) by adding Gaussian noise $\mathcal{N}(0,\sigma^{2}\cdot I)$ to the transition dynamics during each interaction, e.g., both the angle $\theta$ and angular velocity $\omega$ in the Pendulum environment.

Figure: Figure 2: Optimal $\Delta_{\sigma}$ and mean success round ($\pm 1$ standard error) under varying levels of environment stochasticity $\sigma$. Each configuration is evaluated with $10$ random seeds for the Pendulum environment and $5$ random seeds for the Cart Pole and Acrobot environments.
Refer to caption: exp.png

We implement CT-MLE using score matching for dynamics learning and an actor-critic framework for policy learning, as described in Section [C.1](https://arxiv.org/html/2508.02103v1#A3.SS1). Following Yildiz et al. (2021), the tasks are considered "solved", when all rewards collected after a warm-up phase ($T_{\text{warm-up}}=3$ seconds) are at least $0.9$ within a planning horizon of $T=10$ seconds. For each volatility level $\sigma\in\{0,0.4,\dots,2.0\}$, we run CT-MLE with equidistant measurement gaps $\Delta=2^{-i}$ for $i=0,1,\dots,7$. We define the optimal gap, $\Delta_{\sigma}$, as the largest gap that achieves the minimum number of episodes to succeed.

Figure [2](https://arxiv.org/html/2508.02103v1#A3.F2) presents the empirical results, validating two key theoretical claims. First, the optimal measurement gap $\Delta_{\sigma}$ increases with the environment’s volatility $\sigma$, directly corroborating our theoretical analysis. Specifically, higher volatility $\sigma$ corresponds to a larger total variance $\text{Var}^{\Pi}$, and as stated in Remark [5.14](https://arxiv.org/html/2508.02103v1#S5.Thmtheorem14), the optimal gap for minimizing episode complexity should scale with this variance ($\Delta\propto\text{Var}^{\Pi}$).

Second, the results support our algorithm’s instance-dependent sample complexity guarantee. In our framework, the number of episodes until success reflects the episode complexity, i.e., the total amount of interaction data required. Figure [2](https://arxiv.org/html/2508.02103v1#A3.F2) clearly shows that as $\sigma$ increases, the episode complexity also increases, confirming that our algorithm identifies more difficult instances (with higher $\sigma$) and adaptively allocates more samples to solve them.

Additionally, for low-stochasticity cases ($\sigma=0$ or $0.4$), the optimal $\Delta_{\sigma}$ is not the smallest tested gap ($2^{-7}$), aligning with our theoretical result that beyond a certain resolution, finer measurements yield diminishing returns.

Finally, experiments conducted across three distinct control environments demonstrate the robustness and generalizability of our findings, reinforcing the practical relevance of our theoretical framework.

#### Numerical convergence rate approximation.

While our main focus was to validate the relationship between the optimal measurement gap $\Delta_{\sigma}$ and environment stochasticity $\sigma$, examining the convergence rate is also valuable.
Thus, we report the reward error (mean $\pm 1$ standard error over $10$ seeds) across rounds for the Pendulum environment with $\sigma=2.0$,

Figure: Figure 3: Reward error trend of the given setup is closely aligned with the $1/\sqrt{N}$ line.
Refer to caption: exp_con.png

using the corresponding optimal gap $\Delta_{\sigma}=0.125$ in Figure [3](https://arxiv.org/html/2508.02103v1#A3.F3).
We observe that the reward error decreases with the number of rounds $N$, and the decay trend is consistent with an approximate $1/\sqrt{N}$ convergence rate, which aligns with our theoretical analysis well.

### C.3 Experiment setup

All experiments were conducted on a single NVIDIA A6000 GPU. Each $15$-episode Pendulum swing-up task required approximately $5$ hours to complete; each $30$-episode Cart Pole task required approximately $15$ hours to complete; and each $25$-episode Acrobot task required approximately $12$ hours to complete. The peak GPU memory utilization per run ranges from $4$GB to $20$GB approximately.
We listed all the key hyper-parameters used in the numerical experiment in Table [1](https://arxiv.org/html/2508.02103v1#A3.T1).

**Table 1: Hyper-parameters in numerical experiment**
| Hyperparameter | Default | Description |
| --- | --- | --- |
| $N_{0}$ | 3 | Number of trajectories at observation time points in initial data set |
| $H$ | 50 | Trajectory length (in seconds) in the data set |
| $N_{\mathrm{inc}}$ | 1 | Number of trajectories at observation time points added to the data |
| set after each episode |  |  |
| $B_{\mathrm{dyn}}$ | 5 | Batch size of the dynamic learning |
| $N_{\mathrm{dyn}}$ | 500 | Number of dynamic learning update iterations in each episode |
| $H_{\mathrm{dyn}}$ | 5 | Length of each subsequence (horizon) in dynamic learning |
| $M_{\mathrm{proj}}$ | 1 | Rademacher projections per sample in dynamic learning |
| $N_{\mathrm{pol}}$ | 250 | Number of policy learning update iterations in each episode |
| $H_{\mathrm{pol}}$ | 5 | Length of each subsequence (horizon) in policy learning |
| $T$ | 10 | Length of each test trajectory at the end of every episode |
| $T_{\mathrm{warm-up}}$ | 3 | The warm-up subsequence of each test trajectory that does not |
| collect rewards and evaluate at observation time points |  |  |
| $N_{\mathrm{test}}$ | 10 | Number of test trajectories at the end of every episode |

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: If model misspecification is present, how would it affect the algorithm and the theoretical guarantees? To what extent do the main insights reported here still hold (e.g., grid-shape insensitivity, variance-driven behavior)? These questions are optional.
soundness: 3
strengths: 1. Interesting and novel idea: While instance-dependent analysis has been studied in standard discrete-time RL, it is interesting to see how it adapts to continuous-time RL, where irregular measurement times introduce an extra layer of complexity. This paper tackles that setting.

2. New insights for CTRL: By analyzing instance-dependent regret, the paper offers guidance for designing measurement schedules. In particular, as long as the total measurement budget is upper bounded by the total cumulative variance (the intrinsic difficulty of the problem), it is quite flexible to design measurement strategies. The regret also exhibits only logarithmic dependence on the horizon T under the assumption that cumulative reward is bounded by 1, in contrast to the exponential dependence reported in some prior work.

3. Solid theoretical development: The proofs and main results appear reasonable (although I did not check every step in detail).

4. Empirical illustration: Although this is primarily a theoretical paper, it includes numerical experiments to support the claims.
summary: This paper studies instance-dependent guarantees for continuous-time reinforcement learning (CTRL). Under some conditions, it establishes an instance-dependent second-order regret bound for CTRL. The results provides some new insights for CTRL, including robustness on choice of measurements and weaker horizon dependence compared with prior related works.
weaknesses: 1. Limited intuitive exposition in the main text: The theoretical results are dense. I suggest adding a brief proof sketch in the main paper. It would also help to discuss the key challenges and obstacles specific to the continuous-time setting, and how they differ from standard discrete-time RL (e.g., [1]).

2. My biggest concern is the quadratic density assumption (Proposition 5.9). Although Appendix A.3 provides some discussion, a more general treatment would strengthen the paper. If possible, I suggest the authors to include additional examples or at least more intuition for broader density families. It seems plausible that the Eluder dimension remains tractable for richer classes, but the paper does not currently justify this.

[1] Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds. Wang et. al.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: - I do not get Figure 1. I mean, in the text you criticize equidistant measurements, but here all the three options regard equidistant measurements, and what changes is just the frequency of the measurements
- where does Eq. (4.1) comes from? I would expect a formal proof for it, where you show (or at least reference and formally present) the Markov property of the Ito process, and all the passages to obtain it.
- why the regret bound does not depend on the size of the action space?

typos:
- lines 101-104: Something is missing here
- definitions/propositions/theorems should be all italics
soundness: 3
strengths: - The continuous time RL problem is both interesting and important for the RL community as it can tackle more realistic settings than standard MDPs
- The paper provides a theoretical analysis of the proposed algorithm, proving that its regret grows only logarithmically.
summary: This paper analyzes the continuous-time RL setting where the dynamics is modelled as an SDE with both a drift and a diffusion terms. In this setting, the authors present an algorithm for minimizing the regret during interaction with the environment. Crucially, the algorithm is based on constructing two confidence sets around the max likelihood estimate of the dynamics, and then acting optimistically w.r.t. them. The paper next provides a theoretical analysis of the algorithm.
weaknesses: - The algorithm cannot be implemented in practice for meaningful and general classes of dynamics F,G and policies Pi. The authors address this in Appendix C with a relaxation of the considered optimization problems. However, this makes the algorithm loose its theoretical properties.
- The analysis assumes Pi,F,G to be finite. Although the authors mention in Remark 5.2 that the analysis can be extended to more general sets using the same arguments as in a previous work (Wang et al. 2024b), they should at least add an appendix where they derive these results explicitly. Indeed, unless the theoretical analysis of this work is merely copied by (Wang et al. 2024b), it is better to add the proof for the more interesting setting explicitly.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: How sensitive is CT-MLE to the choice of function approximator in practice? Are there guidelines for selecting appropriate models?

Could the framework be extended to handle partially observable or non-stationary environments?

In what types of real-world continuous-time systems (e.g., finance, healthcare) do the authors expect the adaptive measurement mechanism to be most impactful?
soundness: 3
strengths: The shift from dynamic estimation to marginal density estimation via MLE is elegant and conceptually simple, offering a new angle on continuous-time RL problems.

The authors derive a variance-dependent, nearly horizon-free regret bound, marking a notable advance over existing CTRL works that rely on worst-case analysis or have exponential dependence on the time horizon.

The introduction of reward variance as a measure of instance difficulty is insightful, connecting continuous-time control with established ideas in variance-aware RL.
summary: This paper introduces CT-MLE, a model-based algorithm for continuous-time reinforcement learning (CTRL) that uses maximum likelihood estimation (MLE) of the state marginal density instead of directly modeling system dynamics.
The key idea is to achieve instance-dependent adaptivity, where the algorithm’s regret scales with the total reward variance rather than with fixed measurement schedules.
The authors derive theoretical guarantees, showing that regret can become independent of the measurement strategy when observation frequency adapts to problem complexity.
Additionally, they propose a randomized measurement schedule to enhance sample efficiency without additional measurement cost.
weaknesses: The empirical component appears secondary; the paper would benefit from more thorough experiments demonstrating practical performance, robustness, and scalability of CT-MLE.

The assumptions of finite policy, drift, and diffusion classes simplify analysis but reduce applicability to large-scale or continuous policy spaces.