CS06: Control and Estimation in Stochastic Systems

Organizer: Alessandro Arlotto (Duke University)

Goggin’s corrected Kalman Filter: Guarantees and Filtering Regimes

Itai Gurvich

In this paper we revisit a non-linear filter for non-Gaussian noises that was introduced by Goggin in 1992. Goggin proved that transforming the observations by the score function and then applying the Kalman Filter (KF) to the transformed observations results in an asymptotically optimal filter. In the current paper, we study the convergence rate of Goggin’s filter in a pre-limit setting that allows us to study a range of signal-to-noise regimes which includes, as a special case, Goggin’s setting. Our guarantees are explicit in the level of observation noise, and importantly, we do not assume Gaussianity of the noises.

Our proofs build on combining simple tools from two separate literature streams. One is a general posterior Cramér-Rao lower bound for filtering. The other is convergence-rate bounds in the Fisher information central limit theorem.

Along the way, we also study filtering regimes for linear state-space models, characterizing clearly degenerate regimes—where trivial filters are nearly optimal—and a balanced regime, which is where Goggin’s filter has the most value.

Sequential policies and the distribution of their total rewards in dynamic and stochastic knapsack problems

Alessandro Arlotto

We study a dynamic and stochastic knapsack problem in which a decision maker is sequentially presented with \(n\) items with unitary rewards and independent weights that are drawn from a known continuous distribution. The decision maker seeks to maximize the expected reward she collects by including items in a knapsack while satisfying a capacity constraint, and while making terminal decisions as soon as each item weight is revealed. We propose a reoptimized heuristic and compare its total rewards with that of the optimal dynamic programming policy. We show that the two total rewards have the same asymptotic mean, the same asymptotic variance, and the same limiting distribution. In contrast, we also note that other asymptotically optimal heuristics that have been considered in the literature have different (larger) higher moments and different limiting distributions.

Optimal Sparse Graph Design for Stochastic Matching

Jiaming Xu

The problem of designing sparse graphs to enable efficient stochastic matching arises in a variety of resource allocation and operations research contexts, including process flexibility and package delivery systems. Various graph families—such as K-chains and Erdős–Rényi random graphs—have been studied and shown to achieve strong performance. However, the question of what is the optimal graph design has remained open. In this paper, we resolve this question by proving that random regular graphs are asymptotically optimal.