PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling and Remote Estimation for the Ornstein-Uhlenbeck Process through Queues: Age of Information and Beyond

Tasmeen Zaman Ornee, Yin Sun

arXiv:1902.03552v4cs.ITmath.IT

TL;DR

Age alone may not capture signal variation or minimize remote estimation error, motivating sampling strategies for the Ornstein-Uhlenbeck process. The paper solves the sampling problem through threshold policies, including a signal-agnostic policy based on expected estimation error. These policies cover finite-mean service times and settings with or without a sampling-rate constraint.

  • Problem

    Age only partially characterizes signal variation, and minimizing age need not minimize remote estimation error.

    Source: §I · pp. 1–2

  • Method

    The paper formulates causal OU sampling as a continuous-time MDP and derives threshold policies for signal-aware and signal-agnostic sampling.

    Source: §I · p. 2

  • Results

    The optimal signal-aware policy thresholds instantaneous estimation error, while the signal-agnostic policy thresholds expected estimation error; both apply with finite-mean service times and with or without a rate constraint.

    Source: §I · p. 2

  • Takeaways & Limitations

    The identified policy structures may inform optimal sampler designs for more general signal models, such as Feller processes.

    Source: §VI · p. 13

Abstract

from arXiv · show

The age of information, as a metric for evaluating information freshness, has received a lot of attention. Recently, an interesting connection between the age of information and remote estimation error was found in a sampling problem of Wiener processes: If the sampler has no knowledge of the signal being sampled, the optimal sampling strategy is to minimize the age of information; however, by exploiting causal knowledge of the signal values, it is possible to achieve a smaller estimation error. In this paper, we extend a previous study by investigating a problem of sampling a stationary Gauss-Markov process, namely the Ornstein-Uhlenbeck (OU) process. The optimal sampling problem is formulated as a constrained continuous-time Markov decision process (MDP) with an uncountable state space. We provide an exact solution to this MDP: The optimal sampling policy is a threshold policy on instantaneous estimation error and the threshold is found. Further, if the sampler has no knowledge of the OU process, the optimal sampling problem reduces to an MDP for minimizing a nonlinear age of information metric. The age-optimal sampling policy is a threshold policy on expected estimation error and the threshold is found. These results hold for (i) general service time distributions of the queueing server and (ii) sampling problems both with and without a sampling rate constraint. Numerical results are provided to compare different sampling policies.

I. INTRODUCTION

The paper extends remote estimation sampling beyond Wiener processes to the Ornstein-Uhlenbeck process, where age alone does not capture signal variation or minimize estimation error. It develops causal threshold policies for estimation-error minimization and connects signal-agnostic sampling to nonlinear age metrics.

I. INTRODUCTION

  • Age measures time since the freshest received sample, but it only partially captures signal variation and an age-minimizing policy need not minimize estimation error.The paper frames this as motivation for extending the Wiener-process sampling results to more general signals.Source: §I · p. 1
  • The paper studies the Ornstein-Uhlenbeck process, a stationary Gaussian Markov process and continuous-time analogue of the AR(1) process.The process is specified by a stochastic differential equation.Source: §I · p. 1
  • The constrained estimation problem is solved exactly as an uncountable-state continuous-time MDP with a threshold policy on instantaneous estimation error.The threshold depends nonlinearly on β, which combines the optimal objective value and the rate-constraint Lagrange multiplier.Source: §I · p. 2
  • The OU threshold function varies with the signal model, while β is determined in the same way as for the Wiener-process policy.The Wiener-process sampler is a limiting case of the OU result.Source: §I · p. 2
  • Without signal-value knowledge, optimal sampling minimizes a nonlinear age metric using a threshold on expected estimation error.For this signal-agnostic policy, the threshold function is v(β) = β.Source: §I · p. 2
  • The policies apply to finite-mean service-time distributions and problems both with and without a sampling-rate constraint; numerical results suggest improvement over zero-wait and uniform sampling.The reported comparison is numerical rather than a proof of dominance.Source: §I · p. 2

A. Related Work

  • Prior remote-estimation work also found threshold policies, but this queueing model suspends sampling while the server is busy and characterizes the threshold precisely.The paper obtains its OU sampler analytically, unlike cited OU work solved by time discretization and dynamic programming.Source: A. Related Work · p. 2

A. System Model

  • Samples travel from an observer to a remote estimator through a single-server FCFS queue with i.i.d. service times of finite mean.The estimator uses causally received samples to estimate the real-time signal.Source: §I · pp. 1–2, A. System Model · p. 3

C. MMSE Estimator

The paper formulates remote OU-process sampling as a continuous-time MDP and derives an exact optimal policy. The estimator uses causally received samples under an assumption that it ignores the absence of later samples.

C. MMSE Estimator

D. Problem Formulation

A. Signal-aware Sampling without Rate Constraint

  • The optimal sampler waits until the previous sample is delivered, then samples when instantaneous estimation error reaches the nonlinear threshold v(β), with β = mseopt.The threshold is defined for the OU process, and β is the unique root specified by the theorem.Source: A. Signal-aware Sampling without Rate… · p. 4
  • Newton’s method and fixed-point updates converge faster than bisection; both have locally quadratic convergence near the optimum.The convergence comparison is illustrated for i.i.d. exponential service times with mean 1.Source: 1) Three Algorithms for Solving (20) · p. 6, Figure 4 · p. 6, Figure 5 · p. 6

B. Signal-aware Sampling with Rate Constraint

Theorem 2 gives an optimal solution for rate-constrained signal-aware sampling with i.i.d. service times of finite positive mean. Its parameter is selected according to whether the rate constraint is active.

B. Signal-aware Sampling with Rate Constraint

  • Theorem 2 establishes (18)–(20) as optimal when service times are i.i.d. with finite positive mean.Theorem 1 is its special case when fmax = ∞.Source: B. Signal-aware Sampling with Rate… · p. 7
  • The optimal objective value for the constrained problem is given by Theorem 2.The supplied passage introduces its expression but does not include the formula.Source: B. Signal-aware Sampling with Rate… · p. 7
  • β is chosen from the root of (20) when the rate constraint is inactive; otherwise it satisfies the rate constraint with equality.The two cases are distinguished by whether the root of (20) meets condition (37).Source: B. Signal-aware Sampling with Rate… · p. 7
  • Equation (38) has a unique root in [mseYi, mse∞), but the numerical evidence for g(β)'s concavity is unproved.Bisection is guaranteed to converge by Lemma 3; Newton's convergence statement additionally assumes concavity.Source: B. Signal-aware Sampling with Rate… · p. 7

C. Special Case: Sampling of the Wiener Process

The Wiener-process result is a limiting case of the OU analysis, while signal-agnostic sampling reduces to minimizing a nonlinear age penalty. In both settings, the results characterize optimal sampling through a parameter β.

C. Special Case: Sampling of the Wiener Process

  • As σ = 1 and θ → 0, the OU process becomes a Wiener process, and Theorem 3 gives an optimal solution for i.i.d. service times with finite positive mean.The new expression lets β be characterized using the optimal objective value and sampling-rate constraint, as in Theorems 1–2.Source: C. Special Case: Sampling of the… · pp. 7–8

D. Signal-agnostic Sampling

  • For signal-agnostic policies, the OU mean-squared estimation error is strictly increasing in age, making its minimization equivalent to a nonlinear age-penalty MDP.Theorem 4 gives an optimal solution to this MDP for i.i.d. service times with finite positive mean.Source: D. Signal-agnostic Sampling · p. 8
  • The optimal signal-agnostic objective is no smaller than the signal-aware optimum: mseopt ≤ mseage-opt.The signal-agnostic policy class is a subset of the full policy class.Source: D. Signal-agnostic Sampling · p. 8

E. Discussions of the Results

The discussion distinguishes signal-aware thresholds from signal-agnostic thresholds and states the service-time scope of the results. The proof develops the MDP solution, including why sampling during service is suboptimal.

E. Discussions of the Results

  • Signal-aware sampling triggers on instantaneous estimation error, whereas signal-agnostic sampling triggers on expected error at the new sample's delivery.The threshold function depends on the signal model for signal-aware policies; β is determined from the optimal objective and rate constraint.Source: E. Discussions of the Results · p. 8

IV. PROOF OF THE MAIN RESULTS

  • The proof combines suspending sampling during service, Dinkelbach and Lagrangian decomposition, free-boundary optimal stopping, and a zero-duality-gap argument.The free-boundary solution of the per-sample MDP is identified as the most challenging step.Source: §IV · p. 8

A. Preliminaries

  • Within each delivery interval, the estimation error has the same distribution as a time-shifted OU process, enabling the proof to use Dynkin's formula and optional stopping.The cited lemma treats integrable stopping times and separately specifies first exits from bounded sets.Source: A. Preliminaries · p. 9

B. Suspend Sampling When the Server is Busy

  • Taking a new sample while the server is busy is suboptimal; a feasible alternative policy has smaller estimation error.Thus an optimal policy need not sample again before the preceding sample is delivered.Source: B. Suspend Sampling When the Server is… · p. 9

C. Reformulation of Problem (63)

The proof reformulates the estimation-error problem using a parameterized MDP, then applies Lagrangian duality to decompose it into per-sample problems. Strong duality closes the gap between the dual and primal values.

C. Reformulation of Problem (63)

  • The reformulation uses a parameter c and identifies c = mseopt through the condition h(c) = 0, which makes the reformulated and original problems share solutions.The proof seeks c = mseopt ≥ 0 satisfying the stated condition.Source: C. Reformulation of Problem (63) · p. 9

D. Lagrangian Dual Problem of (64)

  • Lagrangian duality decomposes the problem into a sequence of mutually independent per-sample MDPs.The decomposition follows the optimality condition in Lemma 8.Source: D. Lagrangian Dual Problem of (64) · p. 10
  • The dual value initially satisfies d ≤ h(mseopt), and the proof establishes strong duality by showing d = h(mseopt).The stated equality closes the weak-duality bound.Source: D. Lagrangian Dual Problem of (64) · p. 10

E. Analytical Solution to Per-Sample MDP (72)

The per-sample MDP is solved as an optimal-stopping problem with a symmetric threshold on instantaneous state. The resulting threshold is verified to be optimal under the stated condition on β.

E. Analytical Solution to Per-Sample MDP (72)

2) Verification of the Optimality of the Candidate Solution:

F. Zero Duality Gap between (64) and (68)

The paper establishes zero duality gap for the constrained and dual sampling problems, with an optimal threshold-based solution. Numerical comparisons show how estimation error varies across sampling policies and service-time settings, and the conclusion highlights the resulting OU sampling structures.

F. Zero Duality Gap between (64) and (68)

  • For i.i.d. service times with finite positive mean, the duality gap is zero and the threshold-based sequence (Z0(β), Z1(β), …) is optimal.β is selected according to the sampling-rate constraint or the stated service-time condition.Source: F. Zero Duality Gap between (64) and… · p. 11

V. NUMERICAL COMPARISONS

  • mseYi ≤ mseopt ≤ mseage-opt ≤ mseuniform ≤ mse∞, and when feasible, mseage-opt ≤ msezero-wait ≤ mse∞.The comparisons are reported for the sampling policies evaluated in the numerical section.Source: §V · p. 12
  • As log-normal service-time scale α grows, both mseage-opt and mseopt drop, while the gap between them increases.The age penalty for the OU process is upper bounded by mse∞, unlike the Wiener-process age penalty p(∆t) = ∆t.Source: §V · pp. 12–13

VI. CONCLUSION

  • The paper develops causal OU sampling policies that minimize estimation error under a sampling-rate constraint and identifies structural properties for possible study of more general signal models.The conclusion names Feller processes as a future research direction.Source: §VI · p. 13

APPENDIX A PROOF OF LEMMA 2

The appendices establish properties of the optimization functions and estimators used in the main analysis. They also show how the OU threshold analysis connects to a limiting Wiener-process case.

APPENDIX A PROOF OF LEMMA 2

  • The proof shows f(β) is continuous, concave, and strictly decreasing, with f(mseYi) > 0.These properties are established through the behavior of the Lagrangian and the boundary values of f.Source: Appendix A · p. 14

APPENDIX B PROOF OF LEMMA 3

  • The proof establishes that v(β) and R1(v(β)) increase with β, while g(β) decreases continuously and has the stated root behavior.The monotonicity follows from the derivatives of v(β) and R1(v), followed by the definition of g(β).Source: Appendix B · pp. 14–15

APPENDIX C PROOF OF (9)

  • The latest received sample time and its value, (Ut, XUt), form a sufficient statistic for estimating Xt from the delivered sample history.On [Di, Di+1), this statistic is (Si, XSi).Source: Appendix C · p. 15

APPENDIX D PROOF OF LEMMA 4

  • In signal-agnostic sampling, the age penalty is strictly increasing in ∆t, while the proof notes that the same independence step may fail for signal-aware policies.The distinction arises because signal-aware sampling times may be correlated with the delivery intervals.Source: Appendix D · p. 15

APPENDIX E PROOF OF (42)

  • The proof uses a Maclaurin series for G(x) and takes θ → 0 to obtain the limiting threshold expression.The supplied passages identify this as the Wiener-process limit case.Source: Appendix E · pp. 15–16

APPENDIX F PROOF OF LEMMA 5

The appendix proves properties of functions used in the OU analysis and verifies that postponing a sample generated during service does not increase estimation error.

APPENDIX F PROOF OF LEMMA 5

  • Dynkin’s formula and martingale arguments establish the stated properties of R1(v) and R2(v), including their twice continuous differentiability.The functions are shown to solve their respective ODEs.Source: Appendix F · p. 16

APPENDIX G PROOF OF LEMMA 6

  • Postponing a sample generated while the server is busy until service becomes available yields a virtual policy with estimation error no greater than the original policy.Repeating the argument for each sample generated before its service opportunity gives the corresponding sequence of postponed-generation times.Source: Appendix G · pp. 16–17

APPENDIX H PROOF OF (70)

These appendices establish intermediate identities and lemmas used in the paper’s analysis. They reduce the sampling decision to per-sample information, solve an ODE for H(v), and prove the associated results by case analysis.

APPENDIX H PROOF OF (70)

  • The proof of (70) uses iterated expectations and the definition of γ to complete the identity.Source: Appendix H · p. 17

APPENDIX I PROOF OF LEMMA 1

  • Lemma 1 is proved by splitting on whether the absolute estimation error at delivery reaches the threshold, then combining the two cases.Source: Appendix I · p. 18

APPENDIX J PROOF OF LEMMA 8

  • Because the service times are i.i.d., (OYi, Yi) is sufficient for choosing Zi, decomposing the control problem into per-sample MDPs.Source: Appendix J · p. 18

APPENDIX K PROOF OF (79)

  • An integrating-factor solution evaluates the ODE integrals using erf and erfi to obtain H(v).Source: Appendix K · p. 19

APPENDIX L PROOF OF LEMMA 9

The appendix proves Lemmas 9–11 through threshold-based cases and properties of H and G. The final result establishes an expectation inequality for all times and states.

APPENDIX L PROOF OF LEMMA 9

APPENDIX M PROOF OF LEMMA 10

  • Lemma 10 uses the evenness of H and the increase of G to establish H(v) ≥ −γv² below the threshold, with the other case handled separately.Source: Appendix M · p. 20

APPENDIX N PROOF OF LEMMA 11

  • Lemma 12 states the auxiliary bound (1 − 2x²)G(x) ≤ 1 for all x ≥ 0.Source: Appendix N · p. 20
  • For Lemma 11, the proof establishes E_v[H(Vt) − H(v)] ≤ 0 for every t ≥ 0 and v ∈ R.Source: Appendix N · p. 21

APPENDIX O PROOF OF THEOREM 6

The proof constructs a policy and multiplier satisfying the stated optimality conditions for (64). Choosing between two threshold parameters yields a solution with zero duality gap.

APPENDIX O PROOF OF THEOREM 6

  • The proof invokes optimality conditions for (64), including a geometric multiplier, to certify the constructed solution.Source: Appendix O · p. 21
  • The policy uses β1 when its root satisfies (209); otherwise it uses β2, the unique root of (211) in [mseYi, mse∞).Source: Appendix O · p. 21
  • The selected policy and multiplier satisfy (202)–(205), so the duality gap between (64) and (68) is zero and the policy solves both problems.Source: Appendix O · p. 22
Loading 1902.03552v4…