PhiBE: A PDE-based Bellman Equation for Continuous Time Policy Evaluation

1. Problem Statement

The paper addresses Continuous-Time Policy Evaluation (PE) in Reinforcement Learning (RL).

• Context: Many physical systems (e.g., healthcare, robotics, finance) evolve continuously according to Stochastic Differential Equations (SDEs), but data is only available at discrete, potentially irregular time intervals.
• The Challenge: Standard RL approaches typically discretize time and treat the problem as a Markov Decision Process (MDP), solving the discrete-time Bellman Equation (BE).
• The Limitation: The authors argue that the discrete-time BE is a poor approximation of the true continuous-time value function because it ignores the underlying smooth structure of the SDE. It fails to capture the differential nature of the dynamics, leading to significant discretization errors, especially when rewards oscillate rapidly or dynamics evolve slowly.
• Goal: To design an algorithm that leverages the known SDE structure (even if the specific drift/diffusion coefficients are unknown) to approximate the continuous-time value function more accurately than standard discrete-time methods, using only discrete-time observations.

2. Methodology: PhiBE

The core contribution is PhiBE (Physics-informed Bellman Equation), a PDE-based formulation that integrates discrete-time transition information into a continuous-time Partial Differential Equation (PDE).

A. Theoretical Formulation

• Continuous-Time Foundation: The true value function $V(s)$ satisfies the Hamilton-Jacobi-Bellman (HJB) equation:
  $$\beta V(s) = r(s) + \mathcal{L}_{\mu, \Sigma} V(s)$$
  where $\mathcal{L}_{\mu, \Sigma}$ is the infinitesimal generator involving the drift $\mu$ and diffusion $\Sigma$.
• Approximation Strategy: Instead of estimating $\mu$ and $\Sigma$ directly (which is ill-posed from discrete data), PhiBE approximates the operator $\mathcal{L}$ using finite-difference schemes based on observed state transitions.
  • Deterministic Case: Replaces $\mu(s)$ with a finite difference approximation using state transitions $s_{t+\Delta t} - s_t$.
  • Stochastic Case: Estimates both the drift $\hat{\mu}_i$ and diffusion $\hat{\Sigma}_i$ using expectations of state differences and squared differences over the time step $\Delta t$.
• Higher-Order Extensions: The framework supports $i$-th order PhiBEs by using higher-order finite difference schemes (e.g., using $s_{t+2\Delta t}$) to approximate the derivatives, reducing the discretization error from $O(\Delta t)$ to $O(\Delta t^i)$.

B. Model-Free Algorithm

The paper proposes a Galerkin-based model-free algorithm to solve the PhiBE equation:

1. Linear Function Approximation: The value function is approximated as $V(s) \approx \Phi(s)^\top \theta$, where $\Phi$ are basis functions.
2. Projection: The PhiBE equation is projected onto the basis functions using a weighted $L_2$ inner product, resulting in a linear system $A\theta = b$.
3. Data-Driven Estimation: The matrix $A$ and vector $b$ are estimated empirically from trajectory data without explicitly learning the transition dynamics.
4. Connection to LSTD: The algorithm is structurally similar to Least-Squares Temporal Difference (LSTD) but replaces the discrete Bellman operator with the PhiBE operator.

3. Key Contributions

A. Theoretical Guarantees on Discretization Error

• Superior Approximation: The paper proves that the solution to PhiBE is a provably better approximation of the true value function than the solution to the standard discrete-time BE.
• Error Bounds:
  • BE Error: Scales as $O(\Delta t)$ with a coefficient dependent on $\| \mathcal{L}_{\mu, \Sigma} r \|_\infty$ (sensitive to reward oscillation).
  • PhiBE Error: Scales as $O(\Delta t^i)$ (for $i$-th order). The coefficient depends on the smoothness of the dynamics (e.g., $\| \mu \cdot \nabla \mu \|_\infty$) rather than the reward's derivatives.
• Robustness: PhiBE is more robust to rapidly changing reward functions and performs better when system dynamics evolve slowly.

B. Improved Sample Complexity and Convergence

• Model Misspecification: Unlike existing continuous-time RL analyses where the model misspecification error diverges as $\Delta t \to 0$ (due to the discount factor $\gamma \to 1$), the PhiBE error remains independent of $\Delta t$ and well-conditioned. This is achieved by exploiting the ellipticity of the infinitesimal generator.
• Sample Complexity: The paper establishes a finite-sample bound for the model-free algorithm.
  • Standard RL: Sample complexity scales as $O(\Delta t^{-4})$.
  • PhiBE: Sample complexity improves to $O(\Delta t^{-1})$ by leveraging the smoothness of the underlying SDE.

C. Fundamental Trade-off Identification

The authors identify a critical bias-variance trade-off intrinsic to continuous-time PE:

• Bias: Decreases as the sampling interval $\Delta t$ becomes smaller (finer discretization).
• Variance: Increases as $\Delta t$ becomes smaller because the signal-to-noise ratio in the transition differences drops, requiring more samples to maintain accuracy.
• Implication: Excessively frequent sampling does not necessarily improve performance; there is an optimal $\Delta t$ that balances discretization bias and statistical variance. This insight is absent in classical discrete-time RL analyses.

4. Results

• Numerical Experiments:
  • Deterministic & Stochastic Dynamics: Experiments on linear and nonlinear SDEs (including Ornstein-Uhlenbeck processes) show that PhiBE solutions are significantly closer to the true value function than BE solutions, even with sparse data.
  • High-Frequency Rewards: PhiBE maintains accuracy when rewards oscillate rapidly, whereas BE performance degrades significantly.
  • Stabilization Problem: In a control stabilization task (linear and nonlinear), PhiBE achieved lower mean error and variance compared to LSTD across various $\Delta t$ and discount factors $\beta$.
  • High-Dimensional Case: The method scales effectively to 10-dimensional linear-quadratic problems, confirming theoretical predictions.
• Convergence Rates: Empirical results confirm the theoretical convergence orders: BE converges at $O(\Delta t)$, while $i$-th order PhiBE converges at $O(\Delta t^i)$.

5. Significance

• Bridging the Gap: PhiBE provides a systematic framework to bridge continuous-time control theory with discrete-time data, avoiding the pitfalls of naive discretization.
• Efficiency: By reducing the sample complexity dependence on $\Delta t$ from $O(\Delta t^{-4})$ to $O(\Delta t^{-1})$, PhiBE makes continuous-time RL more data-efficient, particularly in scenarios where data collection is expensive or sparse.
• Algorithmic Flexibility: The structural similarity between PhiBE and the standard Bellman equation allows existing RL algorithms (like LSTD) to be adapted with minimal modification, offering "free" accuracy improvements.
• Theoretical Insight: The identification of the bias-variance trade-off in time discretization offers a new perspective for designing sampling strategies in continuous-time RL, moving beyond the assumption that "more frequent data is always better."

In summary, this paper establishes that incorporating the smooth, differential structure of continuous-time dynamics into the Bellman equation formulation leads to superior approximation accuracy, better stability, and improved sample efficiency compared to traditional discrete-time RL methods.