Source-linked AI summary
Log-Derivative Trick for Parametric Markov Chains
Arthur Gall, Ichiro Hasuo, Thomas Seiller
TL;DR
Gradient-based optimization can be difficult when computing gradients requires global state-space operations, and finite-horizon approximations introduce bias. This paper estimates gradients from sampled trajectories, proving unbiasedness under stated conditions and reporting faster gradient computation and optimization on models beyond exact techniques’ reach.
Problem
Gradient-based optimization is practical for high-dimensional parameter spaces, but computing expected-reward gradients efficiently remains challenging, while explicit-state methods scale poorly.
Source: §1 · p. 2Method
The paper uses a Monte Carlo log-derivative estimator along sampled trajectories, generalized with Radon–Nikodym derivatives to handle general measurable state spaces.
Source: §1 · pp. 2–3Results
The estimator provides unbiased gradient estimates under almost-sure termination and standard regularity conditions, and yields accurate gradient approximations orders of magnitude faster than exact linear solvers.
Source: §1 · p. 3, §4 · p. 12Takeaways & Limitations
Trajectory sampling supports rapid parameter synthesis on models beyond the reach of exact techniques and extends naturally to discrete and continuous state spaces.
Source: §1 · p. 3, §4 · p. 12Finite-horizon truncation introduces uncontrollable bias, while explicit-state methods face memory limits on large models.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Optimizing expected rewards and reachability probabilities in parametric Markov chains (pMCs) is central to the analysis and synthesis of probabilistic systems with loops. While traditional symbolic synthesis approaches--such as parameter lifting and rational function generation--suffer from scalability bottlenecks, gradient-based optimization emerges as an effective alternative. However, existing gradient-based techniques still rely on symbolic gradient computation--such as solving large linear systems--over the global state space, inheriting scalability limits. Finite-horizon approximation is possible but introduces uncontrollable bias. In this paper, we introduce a scalable Monte Carlo gradient estimator based on a measure-theoretic generalization of the log-derivative trick. We prove that our estimator provides unbiased gradient estimates under almost-sure termination and standard regularity conditions. Crucially, our method avoids global state-space materialization and linear system solving entirely: it operates purely along sampled trajectories, requiring only black-box evaluations of local transition probabilities (or densities) and their derivatives. Unlike existing pMC techniques that are fundamentally restricted to finite discrete systems, our measure-theoretic framework naturally extends to continuous and general $\sigma$-finite state spaces. Empirical evaluations on synthetic discrete pMCs and continuous-state case studies demonstrate that our method scales to state spaces far beyond the reach of existing solvers, significantly reducing execution time without introducing bias.
1 INTRODUCTION
The paper addresses the difficulty of optimizing expected rewards in pMCs when symbolic synthesis and global-state gradient computation scale poorly. It presents a trajectory-sampling estimator with unbiasedness guarantees under stated conditions and applicability to general state spaces.
1 INTRODUCTION
- Symbolic synthesis scales poorly with parameter count, while global linear-system gradients require explicit state-space representations; fixed-horizon Jacobi approximation introduces uncontrollable bias.The cited symbolic tools rarely scale beyond dozens of parameters.Source: §1 · p. 2
- Under almost-sure termination and standard regularity conditions, the estimator provides unbiased gradient estimates, including for σ-finite transition structures.The measure-theoretic generalization uses Radon–Nikodym derivatives.Source: §1 · p. 3
- The estimator samples trajectories and uses local transition probabilities or densities and their derivatives, avoiding global state-space materialization and linear-system solving.The log-derivative trick turns each path’s reward-weighted sum of transition log-derivatives into a gradient estimate.Source: §1 · pp. 2–3
- The authors report faster gradient approximations than exact linear solvers and synthesis on models orders of magnitude larger than linear solvers can handle.The Monte Carlo estimator reduces computational cost at the price of increased variance.Source: §1 · p. 3
RELATED WORK
- Prior log-derivative work targets infinite-horizon average rewards under ergodicity, unlike this paper’s terminating chains and terminal rewards.The preliminaries establish conventions for measurable spaces, measures, paths, and derivatives.Source: RELATED WORK · p. 3, PRELIMINARIES AND NOTATIONS · pp. 3–4
2 OPTIMIZATION OF PARAMETRIC SIGNED MARKOV CHAINS
The section formalizes pMCs over general measurable state spaces using Markov and signed kernels, then derives a pathwise log-derivative identity and a Monte Carlo gradient sampler. The sampler estimates expected-reward gradients without constructing the full state-space transition matrix or solving linear systems.
2.1 PARAMETRIC MARKOV KERNELS AND SIGNED KERNELS
- Parametric Markov kernels model transitions over general measurable spaces, while signed kernels represent parameter derivatives that may take positive and negative values.In the finite discrete case, kernels reduce to stochastic transition matrices and composition to matrix multiplication.Source: §2.1 · p. 4
2.2 ABSOLUTE DIFFERENTIABILITY
- Absolute differentiability requires kernel derivatives to vanish on sets assigned zero probability, and its Radon–Nikodym derivative corresponds to a log-derivative of transition probabilities or densities.The paper describes this condition as satisfied by most standard discrete and continuous parametric distributions.Source: §2.2 · pp. 4–5
2.3 PARAMETRIC (SIGNED) MARKOV CHAINS
- The paper defines pMCs through parametric kernels over input, internal, and output state spaces, with path and output kernels induced by finite internal paths.Its definition extends beyond finite discrete systems to discrete-time chains over σ-finite state spaces with explicit input and halting-output boundaries.Source: §2.3 · p. 5
2.4 THE LOG-DERIVATIVE TRICK
- The log-derivative theorem expresses the path-kernel derivative as the path probability weighted by an additive sum of local transition log-derivatives.The resulting output-kernel identity assumes regularity allowing differentiation to interchange with summation; the paper notes almost-sure termination with bounded expected path length as a sufficient setting.Source: §2.4 · p. 6
2.5 GRADIENT SAMPLING AND OPTIMIZATION
- The sampler accumulates local transition-gradient vectors along sampled trajectories and returns a terminal state, yielding an unbiased estimate of the output-kernel gradient without linear systems or a full transition matrix.For terminal reward R, multiplying the accumulated vector by R(y) gives an unbiased expected-reward gradient estimate.Source: §2.5 · p. 7
3 EMPIRICAL EVALUATION
Across discrete pMC benchmarks, LogDerivative improves reward efficiently and scales favorably as parameter and state-space sizes grow, with sample count affecting runtime and estimation quality. Experiments also show optimization on continuous-state cases.
RQ1
- As parameter count grows, sampling methods’ runtime advantage over linear solvers widens; LogDerivative also outperforms UniformPath in estimation precision.At 105 sample paths, LogDerivative has normalized distance 0.050 and cosine similarity 0.998 relative to the exact gradient.Source: §3 · p. 9, Figure 4 · p. 9
RQ2
- Constrained C-AdaGrad and C-AdamW achieve fast reward improvement, whereas unconstrained AdaGrad, Adam, and AdamW leave valid parameter bounds within seconds.Standard SGD and step-clamped SmallSGD stay in bounds but make slow progress.Source: §3 · p. 10, Figure 5 · p. 10
- LogDerivative substantially outperforms SparseLU, BiCGSTAB, and UniformPath in cumulative normalized reward improvement; low-sample settings deliver the fastest initial gains.The comparison covers full optimization runs under a 100-second timeout.Source: §3 · p. 10, Figure 6 · p. 11
RQ3
- Increasing N from 10 to 10^6 raises runtime by less than two orders of magnitude, while LogDerivative steadily converges toward the exact gradient and UniformPath’s precision plateaus.Runtime growth is strongly sublinear for both sampling methods.Source: §3 · pp. 10–11, Figure 7 · p. 11
RQ4
- At 2.6 × 10^5 states, SparseLU exceeds 200 seconds, while LogDerivative reaches cosine similarity 1.000 and normalized distance 0.013 at N=10^6.The benchmarks use 102 parameters.Source: §3 · pp. 11–12, Figure 8 · p. 12
RQ5
- On continuous benchmarks T3 and T4, LogDerivative optimizes effectively and converges to the theoretical maximum reward.The experiments use a constrained-AdamW optimizer.Source: §3 · p. 12
4 CONCLUSIONS AND FUTURE WORK
The paper presents a trajectory-sampling framework for terminating pMCs over general measurable state spaces, with unbiasedness guarantees and reported speed and scalability benefits. It also outlines foundational and practical future work and states how generative AI tools were used.
4 CONCLUSIONS AND FUTURE WORK
- The framework provides unbiased gradient estimates and, empirically, accurate approximations orders of magnitude faster than exact linear solvers, while accelerating optimization on models beyond exact techniques.It uses the log-derivative trick generalized via Radon–Nikodym derivatives and is tailored to terminating pMCs over general measurable state spaces.Source: §4 · p. 12
- Future work includes structural analysis through categorical and compositional semantics, machine-learning applications, and GPU parallelization of independent sampled paths.Source: §4 · pp. 12–13
- Figure 9 evaluates continuous benchmarks T3 and T4 using 104 path samples per step over 103 iterations, with analytically computed optimal rewards indicated.Source: Figure 9 · p. 13
- The score-function approach needs no reparameterization and accommodates stochastic branching and loops.Source: §4 · p. 13
AI USE STATEMENT
- The authors report using generative AI only for minor code-optimization and manuscript-polishing support, not for theoretical or experimental design.They state that generated suggestions were verified by the authors, who take responsibility for the text, code, and theoretical results.Source: AI USE STATEMENT · p. 13
A BENCHMARK GENERATION
The benchmark generator creates connected sparse pMC topologies and parameterized transitions, with local conditions ensuring valid differentiable models around the initialization point.
A BENCHMARK GENERATION
- The generator builds accessible, co-accessible sparse graphs and scales large cyclic topologies by duplicating modular subgraphs and linking them with bridging transitions.Source: A BENCHMARK GENERATION · p. 15
- Outgoing transition probabilities use affine univariate polynomials whose formal sum is one, and remain strictly between zero and one in a neighborhood of the initial parameter point.Source: A BENCHMARK GENERATION · p. 15
- Although individual transitions are degree-one, cyclic and branching paths yield high-degree multivariate rational functions; generated models are exported as PRISM files for shared evaluation.The generator scales to models with 105 states and millions of transitions in seconds.Source: A BENCHMARK GENERATION · p. 15