Source-linked AI summary
Robust Sensitivity Analysis for Stochastic Systems
Henry Lam
TL;DR
The paper addresses how to measure stochastic-system performance sensitivity when the true model is only known to lie near a baseline under KL divergence. It develops infinitesimal approximations whose coefficients are computable by simulation, yielding asymptotic expansions of worst-case performance as the divergence vanishes.
Problem
The paper studies worst-case performance impacts of model errors when no specific form of the true model misspecification is known, using KL divergence to define proximity to a baseline.
Method
The paper formulates worst-case optimization problems over models near a baseline and analyzes their optimal values through asymptotic expansions and worst-case changes of measure.
Results
As KL divergence η approaches zero, the optimal values admit asymptotic expansions under mild assumptions, with coefficients that can be computed via simulation.
Takeaways & Limitations
The first-order model-misspecification effect scales with the square root of KL divergence, and the results extend to multiple random sources and selected sources with known distributions.
Takeaways & Limitations
Further relaxation of the assumptions for more general stopping times is outside the scope of the work.
Abstract
from arXiv · showhide
We study a worst-case approach to measure the sensitivity to model misspecification in the performance analysis of stochastic systems. The situation of interest is when only minimal parametric information is available on the form of the true model. Under this setting, we post optimization programs that compute the worst-case performance measures, subject to constraints on the amount of model misspecification measured by Kullback-Leibler (KL) divergence. Our main contribution is the development of infinitesimal approximations for these programs, resulting in asymptotic expansions of their optimal values in terms of the divergence. The coefficients of these expansions can be computed via simulation, and are mathematically derived from the representation of the worst-case models as changes of measure that satisfy a well-defined class of functional fixed point equations.
1. Introduction
The paper evaluates worst-case effects of model misspecification in stochastic-system performance analysis when the true model is only approximately known. It develops KL-divergence-based infinitesimal approximations whose coefficients can be computed through simulation.
- Worst-case optimization evaluates performance across models close to a baseline under a nonparametric statistical distance such as KL divergence.
- Infinitesimal asymptotic expansions address the non-convex, infinite-dimensional worst-case optimizations arising in stochastic systems.The expansion coefficients are computable via simulation and capture worst-case effects from nonparametric model deviations.
- The approach analyzes performance measures E[h(X_T)] for i.i.d. random inputs over a finite time horizon.The cost function may be computable without a closed form, such as a queueing-system waiting time.
2. Formulation and Highlights
The formulation treats the unknown true distribution as a decision variable within a KL-divergence neighborhood of a baseline model and optimizes the resulting performance measure. For small divergence, the optimal value admits an expansion around baseline performance with explicitly characterizable coefficients.
- The baseline distribution P0 is assumed to approximately describe each i.i.d. input, with baseline performance E0[h(X_T)].
- The unknown true distribution Pf is optimized over distributions absolutely continuous with respect to P0 and constrained by D(Pf∥P0) ≤ η.
- The optimization seeks the most extreme performance measures among models within η units of KL divergence from P0.
- Because all inputs share Pf and are i.i.d., the optimization programs are generally non-convex and difficult to solve.
- As η approaches zero, the optimal values expand as E0[h(X_T)] + ζ1(P0,h)√η + ζ2(P0,h)η + ···.The coefficients are explicitly expressible in terms of h and P0.
3. Main Results
The paper derives small-KL-divergence asymptotic expansions for worst-case performance in stochastic systems, beginning with a single-variable case and extending to finite and random horizons. The results characterize optimal values through variance, third cumulants, and problem-specific dependence terms under moment and non-degeneracy assumptions.
- Single-Variable Case: For T = 1, the worst-case objective admits a precise small-η expansion under finite exponential moments and non-constant h(X).The expansion is expressed around E0[h(X)] and uses Var0(h(X)) and κ3(h(X)).
- Single-Variable Case: The single-variable optimization is transformed from probability measures to likelihood ratios, yielding an optimizer characterized through a Lagrangian relaxation.The likelihood ratio L = dPf/dP0 belongs to L1(P0), and the KL constraint determines the relevant multiplier through βψ′(β) − ψ(β) = η.
- Finite Horizon Problems: For finite horizons, the expansion replaces h(XT ) with a function g derived from conditional expectations across time steps.The leading coefficients involve Var0(g(X)) and κ3(g(X)), while ν captures a cross-term involving G(X,Y), g(X), and g(Y).
- Random Time Horizon Problems: The finite-horizon framework extends to random time horizons under stopping-time and boundedness conditions, with a corresponding generalized expansion.When the horizon is finite and deterministic, this result reduces to the finite-horizon theorem.
- Extensions: For minimization, the first-order term changes sign while the second-order term remains unchanged under the same assumptions.The single-variable minimization case uses the unique negative solution for β∗, equivalently obtained by replacing h with −h.
- Extensions: The first-order misspecification effect scales with the square root of KL divergence, and the framework also accommodates multiple random sources when other distributions are known.For a known random object Y, the finite-horizon result applies after replacing h(XT ) with E[h(XT ,Y)|XT ].
4. Connections to Past Literatures
The paper situates its approach within sensitivity analysis and perturbation analysis, while distinguishing its treatment of model uncertainty from classical parametric methods.
- Classical sensitivity analysis focuses on derivative estimation under parametric uncertainty.
- Perturbation analyses of Markov chains often express sensitivity through Taylor expansions of transition-matrix perturbations.
- For finite horizons, the paper reformulates the worst-case maximization in terms of a likelihood ratio and KL-divergence constraint.
5. Mathematical Developments for Finite Horizon Problems
For finite-horizon stochastic systems, the paper converts the worst-case problem into a likelihood-ratio optimization and characterizes its solution through functional fixed-point analysis.
- Problem formulation: The finite-horizon maximization is written as an optimization over likelihood ratios subject to an expected KL-divergence constraint.
- Problem formulation: The product-form likelihood ratio creates the main technical challenge in the objective function.
- Fixed-point characterization: A functional operator K characterizes the relaxed optimum through a fixed-point equation on a suitable function space.
- Lagrangian analysis: The Lagrangian relaxation is analyzed through optimality conditions involving its multiplier and the relaxed objective.
- Convergence: For sufficiently large α, K is a contraction, its iteration converges to a fixed point, and the scaled objective is non-decreasing along the iteration.
- Asymptotic expansion: The fixed-point characterization is then used to obtain an asymptotic expansion of the optimal likelihood ratio in terms of α*.
6. Extension to Random Time Horizon Problems
The random-time-horizon extension rewrites the objective using likelihood-ratio martingales and reduces bounded stopping-time problems to the finite-horizon framework.
- For a stopping time τ bounded almost surely by T, the objective satisfies E0[h(Xτ)Lτ] = E0[h(Xτ)LT] by the martingale property.
- The random-time problem therefore falls within Theorem 3.2 with h(Xτ) as the cost function.
- Independence and measurability arguments make terms in the resulting representations constant, while translation invariance preserves the first- and second-order coefficients.
- Theorem 3.3 is extended beyond bounded stopping times by considering truncated times τ ∧ T.
- The expansion coefficients dominate parametric derivatives under the stated parametric-family assumptions.
7. Bounds on Parametric Derivatives
The paper compares robust KL-based sensitivity with derivatives restricted to a parametric model family and shows that the robust first-order coefficients provide bounds under regularity assumptions.
- The comparison assumes the baseline distribution belongs to a one-dimensional parametric family and imposes local absolute continuity.
- For small nonzero divergence levels, the two nearby parametric solutions on opposite sides of the baseline are feasible for the worst-case optimization programs.
- The first-order robust expansion coefficients dominate parametric derivatives because the parametric family is more restrictive than the full model space.
- The robust upper and lower optimal values bound the corresponding parametric performance changes.
- The limiting bounds involve 2V ar0(g(X)) under Theorem 3.2.
8. Numerical Examples
The numerical examples estimate first-order KL-sensitivity coefficients for queueing performance measures and compare the resulting bounds with simulated perturbations. Across M/M/s and G/G/s systems, the approximations capture observed performance over small divergence levels.
- For M/M/s queues, the waiting-time tail probability decreases from 0.52 to 0.08 as servers increase from 1 to 5.
- The first-order coefficient decreases from 1.69 at s = 1 to 0.96 at s = 5, while relative misspecification impact increases from 3.25 to 11.46.
- The first-order approximation represents worst-case deviations as E0[h(XT)] ± sqrt(2V ar0(g(X))η), with η measuring KL divergence.
- η = 0.005 corresponds to roughly 10% service-rate discrepancy within the exponential family, while service rate 1.1 gives η = 0.0044.
- For η up to 0.005, the first-order bounds appear to contain all simulated performance measures in the parametric comparison.
- In G/G/s systems, both performance measures and first-order coefficients are smaller than in M/M/s, while relative impacts are relatively similar.
9. Proofs
The proofs establish explicit optimizers for KL-constrained problems and characterize the fixed-point equations governing worst-case changes of measure. Under small-parameter conditions, contraction arguments provide uniqueness and convergence of the relevant fixed-point iterations.
- Convexity and Jensen’s inequality show that the optimizer is unique because equality holds only when h(X)/α − log L is constant.
- The KL-constrained optimization has optimal solution L* and value α log E0[e^(h(X)/α)] when 1/α lies in the exponential-moment domain.
- For sufficiently small β = 1/α, the operator K is a strict contraction, so it has a unique fixed point and its recursion converges from any admissible initial value.
- The fixed point satisfying the stated condition is an optimal solution to the broader KL-constrained problem.
- The fixed point of the reduced operator is well-defined, closed, and a strict contraction, and it equals each identical component of the fixed point of K.
Appendix A. Sufficiency Theorem
The appendix supplies a sufficiency theorem for certifying optimality in entropy-constrained optimization. It applies the theorem by selecting the feasible class and objective appropriate to each main result.
- For Theorems 3.1–3.3, the theorem is applied with problem-specific feasible classes and objectives involving E0[h(X)L], E0[h(XT)LT], or E0[h(Xτ)Lτ].