Source-linked AI summary
Accuracy of Discretely Sampled Stochastic Policies in Continuous-time Reinforcement Learning
Yanwei Jia, Du Ouyang, Yufei Zhang
TL;DR
The state dynamics induced by frequent sampling of stochastic policies and the resulting performance of continuous-time RL algorithms have not been rigorously characterized. The paper samples actions at discrete times, executes them as piecewise-constant controls, and analyzes the resulting dynamics and learning algorithms. With sufficiently regular coefficients, sampled dynamics converge weakly at rate O(|G|) to aggregated dynamics; discrete-observation estimators have O(|G|) bias, with bounded variance for the policy-gradient estimator.
Problem
The state dynamics induced by frequent sampling of stochastic policies and the resulting performance of continuous-time RL algorithms have not been rigorously characterized.
Source: Execution of stochastic policies · p. 2Method
The paper samples actions at discrete times, executes them as piecewise-constant controls, and analyzes the resulting dynamics and learning algorithms.
Source: Execution of stochastic policies · p. 2, Our contributions · p. 2Results
With sufficiently regular coefficients, sampled dynamics converge weakly at rate O(|G|) to aggregated dynamics; discrete-observation estimators have O(|G|) bias, with bounded variance for the policy-gradient estimator.
Source: Our contributions · pp. 2–3Takeaways & Limitations
The convergence results rigorously justify the exploratory control framework proposed in.
Source: Our contributions · p. 2The analysis assumes coefficient regularity, including Lipschitz continuity in the state and a growth bound involving distance from a fixed action.
Source: §3.1 · p. 5
Abstract
from arXiv · showhide
Stochastic policies (also known as relaxed controls) are widely used in continuous-time reinforcement learning algorithms. However, executing a stochastic policy and evaluating its performance in a continuous-time environment remain open challenges. This work introduces and rigorously analyzes a policy execution framework that samples actions from a stochastic policy at discrete time points and implements them as piecewise constant controls. We prove that as the sampling mesh size tends to zero, the controlled state process converges weakly to the dynamics with coefficients aggregated according to the stochastic policy. We explicitly quantify the convergence rate based on the regularity of the coefficients and establish an optimal first-order convergence rate for sufficiently regular coefficients. Additionally, we prove a $1/2$-order weak convergence rate that holds uniformly over the sampling noise with high probability, and establish a $1/2$-order pathwise convergence for each realization of the system noise in the absence of volatility control. Building on these results, we analyze the bias and variance of various policy evaluation and policy gradient estimators based on discrete-time observations. Our results provide theoretical justification for the exploratory stochastic control framework in [H. Wang, T. Zariphopoulou, and X.Y. Zhou, J. Mach. Learn. Res., 21 (2020), pp. 1-34].
1. Introduction
Continuous-time RL needs theory that accounts for the gap between continuously evolving systems and discretely updated actions. This paper analyzes executable stochastic policies sampled at discrete times and their effects on learning algorithms.
Execution of stochastic policies.
- The paper addresses the gap between stochastic policies’ frequent-sampling dynamics and aggregated dynamics, whose continuous sampling is computationally infeasible and raises measure-theoretic concerns.Its practical alternative samples actions at discrete times and applies them as piecewise-constant controls; prior analysis was limited to LQ problems with Gaussian policies.Source: Execution of stochastic policies · p. 2
Our contributions.
- With sufficiently regular coefficients, sampled dynamics converge weakly at the optimal first-order rate O(|G|) to aggregated dynamics as the sampling step shrinks.The paper also quantifies weak convergence rates for less regular coefficients.Source: Our contributions · p. 2
- At order O(|G|^1/2), convergence holds uniformly over sampling-noise realizations with high probability; without volatility control, it also holds for almost every system-noise realization.The latter condition is necessary for convergence for each fixed system-noise realization; the results support a law-of-large-numbers interpretation as sampling frequency increases, without averaging across realizations.Source: Our contributions · p. 2
- Discrete execution introduces O(|G|) bias in reward evaluation and martingale orthogonality calculations, and policy-gradient estimation has O(|G|) bias with bounded variance.The risk-sensitive q-learning method with a quadratic-variation penalty also has discretization error of a similar order.Source: Our contributions · p. 3
Our approaches and key technical challenges.
- The analysis distinguishes control randomization from system noise and uses PDE regularity and martingale concentration tools to study different convergence criteria.For weak error conditioned on sampling noise, it uses Azuma–Hoeffding; almost-sure convergence analysis uses conditional Orlicz norms for sub-exponential martingales.Source: Our approaches and key technical… · p. 3
Most related works.
- Earlier work either assumed observations came from the target continuous-time dynamics, studied continuously evaluated policies without rates, or restricted drift controls to bounded coefficients.This paper studies discrete-time policy evaluation, provides convergence-rate results, and allows drift coefficients with linear growth.Source: Most related works · pp. 3–4
2. Preliminary
The section reviews classical continuous-time control and how stochastic policies are used in reinforcement learning. It contrasts a heuristic aggregated model with practical discrete-time action sampling, whose dynamics converge to that model as sampling frequency increases.
2.1. Classical stochastic control.
- Classical stochastic control selects non-anticipative actions to optimize rewards, with an optimal feedback policy applying actions as a function of time and state.The policy is implemented by evaluating it at the current state.Source: §2.1 · p. 4
2.2. Stochastic policy in RL and the associated state dynamics.
- In reinforcement learning, agents learn from a black-box continuous-time environment, often using stochastic policies that sample actions to support exploration.The agent observes state transitions and refines the policy without direct access to the system coefficients.Source: §2.2 · p. 4
- The aggregated dynamics average system coefficients under the policy distribution, but their derivation assumes continuous independent action sampling and differs from the practically observed process.The cited heuristic derives the model from the first and second moments of infinitesimal state changes.Source: §2.2 · pp. 4–5
- Discrete-time action sampling yields piecewise constant controls, and the resulting state dynamics converge to the aggregated dynamics as sampling frequency increases.The section motivates quantifying this approximation and its impact on algorithms based on the aggregated model.Source: §2.2 · p. 5
3. Probabilistic Setup for Aggregated and Sampled Dynamics
The probabilistic setup imposes regularity and integrability conditions on the system coefficients and stochastic policy. These conditions ensure the aggregated coefficients are measurable with controlled growth, while further regularity is assumed for the aggregated dynamics to be well-posed.
3.1. Aggregated dynamics.
- The system drift and volatility are assumed measurable, Lipschitz in the state, and of at most linear growth in the state and action distance.The growth condition is measured relative to a fixed action a0.Source: §3.1 · p. 5
- The stochastic policy is a probability kernel with mild growth and integrability requirements, under which the aggregated drift and volatility are measurable and have at most linear growth.The passage refers to these requirements as Condition (H.1(2)).Source: §3.1 · p. 5
- The aggregated dynamics are additionally assumed sufficiently regular to be well-posed.The stated sufficient regularity includes local Lipschitz continuity in the state under (H.1).Source: §3.1 · p. 5
H.2. The functions ˜bπ and ˜σπ are sufficiently regular so that (2.3) admits a unique strong solution ˜X on the filtered probability space (ΩW , FW , FW , PW ).
The section formalizes policy execution through randomized actions sampled on a time grid and held constant between updates. It distinguishes weak convergence, which depends on the policy, from pathwise error, which also depends on the sampling function.
H.2. The functions ˜bπ and ˜σπ are sufficiently regular so that (2.3) admits a unique strong solution ˜X on the filtered probability space (ΩW , FW , FW , PW ).
- Continuous independent action sampling creates a measure-theoretic obstacle: the controlled coefficients may not be progressively measurable, leaving the conventional stochastic integral ill-defined.The cited discussion says no essentially pairwise independent family of non-constant random variables can also be Lebesgue measurable in time.Source: §H.2 · p. 5
3.2. Sampled dynamics with randomized actions.
- A sampling procedure represents policy execution by generating an action from the policy distribution at a given time and state.The definition allows a general Borel sampling space and a measurable sampling function.Source: §3.2 · p. 6
- Weak convergence rates depend on properties of the stochastic policy rather than the sampling scheme, whereas pathwise error analysis uses properties of the sampling function.Weak convergence is established under mere measurability of that function; additional regularity is imposed for strong convergence.Source: §3.2 · p. 6
- The sampled state evolves continuously while each randomized action remains fixed over its grid interval and is updated at the next observation time.This matches the described setting in which the agent observes a continuous-time system at discrete points and adjusts actions then.Source: §3.2 · pp. 6–7
H.2. The functions ˜bπ and ˜σπ are sufficiently regular so that (2.3) admits a unique strong solution ˜X on the filtered probability space (ΩW , FW , FW , PW ).
- The sampled dynamics have a unique strong solution adapted to the filtration generated by system noise and execution noise, under the stated regularity condition.The aggregated dynamics are also assumed to admit a unique strong solution under H.2.Source: §H.2 · p. 5, §3.2 · p. 7
4. Error Estimates for the Sampled Dynamics
This section studies error estimates for sampled dynamics, covering weak convergence errors averaged over execution noise or conditioned on its realization, estimator complexity, and pathwise convergence. It also numerically illustrates weak and strong convergence rates under uncontrolled and controlled volatility.
4.1.1. Weak convergence for regular coefficients
- With sufficiently regular coefficients and test functions, the weak error is O(|G|); the estimator is biased with first-order vanishing bias and uniformly bounded variance.The regularity requirement includes sufficient regularity of the state coefficients and the associated Kolmogorov PDE solution. Generating one trajectory costs linearly in the number of grid points.Source: §4.1.1 · pp. 7–8
4.1.2. Weak convergence with irregular coefficients
- For Hölder-continuous coefficients, the weak convergence order is quantified in terms of their smoothness, with extensions to polynomial growth and degenerate volatility when the associated PDE has a classical solution.The result relaxes the regularity conditions of the first-order theorem; its stated extension requires a classical PDE solution with polynomial growth.Source: §4.1.2 · pp. 9–10
4.2. Weak error conditioned on execution noise
- With high probability over execution noise, the weak error averaged over system noise converges at half-order uniformly over sampling-noise realizations.Increasing sampling frequency suffices for convergence without averaging multiple sampling-noise realizations at fixed time points, reducing estimator sample complexity.Source: §4.2 · pp. 10–11
- The estimator achieves sample complexity O(ε^-2) up to a logarithmic factor, matching the optimal order for direct Monte Carlo sampling of aggregated-dynamics trajectories.For the specified choice mε = nε = ⌈ε^-2 (1 + ln(2/ε))⌉, its sample complexity is 2⌈ε^-2 (1 + ln(2/ε))⌉ with probability at least 1 − ε.Source: §4.2 · p. 11
4.2. Weak error conditioned on execution noise.
- The naive Monte Carlo estimator (4.9) has O(ε^-3) total complexity to achieve error ε, higher than estimator (4.8), because each trajectory requires regenerated sampling noises.The stated choices are mε = O(ε^-2) and nε = O(ε^-1).Source: §4.2 · p. 11
4.3. Strong convergence.
- Under H.6 with uncontrolled volatility, sampled dynamics converge pathwise at order 1/2 to aggregated dynamics for almost every fixed system-noise realization as the mesh shrinks.Theorem 4.4’s bound applies to grids satisfying its stated mesh condition.Source: §4.3 · p. 12
- Pathwise convergence can fail with controlled volatility: in Example 4.7, the strong error does not vanish as the sampling mesh shrinks unless the action distribution is a Dirac distribution.The example takes zero drift and volatility equal to the sampled action.Source: §4.3 · p. 13
4.4. Numerical illustration.
- In simulations, weak error had slope −1 in both volatility cases; RMSE had slope −1/2 without volatility control but remained essentially constant with control.The uncontrolled-volatility RMSE confirms the O(|G|^1/2) strong rate; the controlled-volatility result illustrates its failure.Source: Figure 1 · p. 13, §4.4 · pp. 13–14, Figure 2 · p. 14
5. Applications
The section quantifies how discrete sampling affects policy evaluation and learning estimators in continuous-time RL. It analyzes Monte Carlo evaluation, temporal-difference learning, policy gradients, and risk-sensitive q-learning.
5.1. Accuracy of the Monte-Carlo evaluation.
- Proposition 5.1 characterizes the unconditional bias of discrete-sampling Monte Carlo policy evaluation, and conditional weak error can refine simulation budgets by policy-sampler realization.The section also considers a high-probability bound for the value function.Source: §5.1 · p. 15
5.2. Accuracy of Temporal-Difference learning.
- The section characterizes bias and variance for discretized temporal-difference estimates; refining the grid improves accuracy while variance remains uniformly bounded.With a suitable grid-refinement schedule, the authors expect typical stochastic-approximation convergence conditions to hold.Source: §5.2 · p. 16
5.3. Accuracy of policy gradient.
- A general policy-gradient estimator of the form (5.7) is analyzed for its limiting value, bias, and variance.Because its test function depends on the sampled action, this estimator is not a direct discretization along the aggregated dynamics and is defined using sampled dynamics.Source: §5.3 · p. 17
- Refining the grid improves policy-gradient accuracy, while the estimator variance remains uniformly bounded in grid size.These properties are presented as important for choosing a sampling frequency for convergence of the overall policy-gradient algorithm.Source: §5.3 · p. 18
5.4. Accuracy of risk-sensitive q-learning.
- Risk-sensitive q-learning is treated through a quadratic-variation penalty, which can be approximated using sampled dynamics.The section relates this penalty to the quadratic variation of the value-function process.Source: §5.4 · pp. 18–19
- General actor-critic convergence is left for future research because the value function is typically approximated through policy evaluation rather than known exactly.The convergence also depends on conditions involving the policy-gradient parameter.Source: §5.4 · p. 18
6.1. Proofs of Theorems 4.1, 4.2, 4.3, and 4.4.
The proofs use backward equations, conditional expectations, and martingale concentration to establish convergence and error bounds for the sampled dynamics. They treat weak-error estimates and high-probability or almost-sure convergence separately.
6.1.1. Proof of Theorem 4.1.
- Theorem 4.1 is proved by solving a backward PDE for the aggregated dynamics, applying Feynman–Kac, and estimating interval errors with Itô’s lemma.The smoothness assumption supplies the required bound on the PDE solution.Source: §6.1.1 · p. 19
6.1.2. Proof of Theorem 4.2.
- Theorem 4.2’s weak-error estimate follows by bounding the terms in the proof with Lemma 6.2 and the regularity of the PDE solution.The resulting bound scales with the grid size and the regularity index.Source: §6.1.2 · pp. 20–21
6.1.3. Proof of Theorem 4.3.
- Theorem 4.3 uses martingale-difference decompositions and the Azuma–Hoeffding inequality to control sampling-noise deviations.The proof bounds the interval contributions before applying concentration.Source: §6.1.3 · pp. 21–22
6.1.4. Proof of Theorem 4.4.
- Theorem 4.4 bounds the sampled process using sub-exponential concentration and a time-difference estimate, then obtains almost-sure convergence by Borel–Cantelli.The proof also bounds the maximum interval contribution by a term involving log(1 + n).Source: §6.1.4 · pp. 24–25
6.2. Proof of Corollary 4.1.
The proof conditions on the policy-sampling randomness, applies Hoeffding’s inequality to independent bounded rollout estimates, and combines the result with Theorem 4.3.
6.2. Proof of Corollary 4.1.
- Conditioned on policy-sampling randomness, the rollout estimates are independent and bounded, so Hoeffding’s inequality yields the sampling bound combined with Theorem 4.3.The proof chooses the grid and sample count according to the corollary’s stated target probability.Source: §6.2 · pp. 25–26
6.3. Proofs of Propositions 5.1, 5.3 and 5.5.
The proofs of the estimator propositions reduce bias terms to the convergence results for sampled dynamics and use moment bounds for variance. Itô’s formula and the established weak-error estimates provide the principal bias arguments.
6.3. Proofs of Propositions 5.1, 5.3 and 5.5.
- For Proposition 5.3, Itô’s formula decomposes the bias, and the proof bounds a term using Theorems 4.1 and 4.2 before applying Proposition 5.1.The variance argument is handled separately using Lemma 3.1.Source: §6.3 · pp. 26–27
- The Proposition 5.1 bias proof applies the weak-error results for the sampled dynamics to the relevant terms.The proof invokes Theorems 4.1 and 4.2 for the respective regularity conditions.Source: §6.3 · p. 27
- The Proposition 5.5 proof handles variance and bias separately, using Theorem 4.1 and Proposition 5.1 for the bias bounds.The proof also treats a special case where S does not depend on the action.Source: §6.3 · pp. 26–28
6.4. Proofs of Examples 4.1 and 4.2.
These proofs establish regularity for the aggregated volatility coefficient under the stated conditions. The argument uses differentiation under the integral, coefficient bounds, and uniform ellipticity.
6.4. Proofs of Examples 4.1 and 4.2.
- The desired result follows from the stated estimates together with uniform ellipticity of σσ⊤.The proof of Example 4.2 also uses λ^-1 ≤ ε^-1 under uniform ellipticity.Source: §6.4 · p. 28
- Example 4.2 proves bounded x-derivatives of the aggregated volatility coefficient in the case d = m = 1.The proof exchanges integration and differentiation, then applies Hölder's inequality and extends the bound to s ≤ 4.Source: §6.4 · p. 28
- The displayed derivative identities express higher derivatives using derivatives of λ and powers of λ.The supplied expressions include terms involving ∂xλ and ∂2_xλ.Source: §6.4 · p. 28
Appendix A. Proofs of Lemmas 3.1, 6.1 and 6.3
The appendix proofs establish well-posedness and moment estimates for the discretely controlled process. They use interval-by-interval solution construction, conditional estimates, and Grönwall's inequality.
Proofs of Lemmas 3.1, 6.1 and 6.3
- Lipschitz continuity of b and σ in x uniformly over time and actions gives a unique strong solution on each time interval, and induction yields well-posedness.The stated solution has finite p-th moments of its supremum for all p ≥ 2.Source: Appendix A · p. 30
- The proof of Lemma 3.1 uses conditional expectation and Condition (H.1(2)), then concludes the desired estimate by Grönwall's inequality.The proof denotes by C a generic constant independent of t_i.Source: Appendix A · pp. 30–31
- For the discretely controlled process, the appendix derives finite moment bounds and states that its moments are independent of the grid size.The proof uses the grid notation δ(u) = t_i on u ∈ [t_i, t_{i+1}) and invokes Condition (H.5).Source: Appendix A · pp. 31–32