arXiv preprint ·
The Cost of Missed States: Online Tracking with Current-Observation Resets
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
An online tracker retains one state and may reset only to the current observation, although its complete observed history is available. Offline knows the future and obeys the same reset rule. Under a hard discrepancy radius, for every horizon $T\ge5$ and every feasible randomized causal policy, a fixed path on a known five-point metric requires at least $(T+1)/2$ expected refreshes, against exactly two offline refreshes with a strict radius margin. Missing the useful prefix center forces a refresh at every suffix observation. The path visits four values, with resolution fixed as $T$ grows. Write $J_λ$ for cumulative discrepancy plus a charge $λ>0$ per refresh, and $V_T$ for the sum of successive observation distances. A candidate prefix adapts Bienkowski and Schmid's randomized lower bound to this objective under current resets, even with a known horizon and $V_T<3λ$. This construction needs finer grids; a fixed finite metric with positive minimum separation instead admits a competitive policy for penalized tracking. An anytime policy satisfies $J_λ\leλ+4\sqrt{λTV_T}$ without knowing the horizon or final variation. Clipping for a known horizon gives $J_λ\leλT$ and a factor-three comparison with the minimum of three analytical bounds, without knowing final variation. Current-value diameter and readout sensitivity give same-input output bounds for mixtures, including squared-distance softmax.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
Optimal Mixing for Local Edge-Coloring Dynamics on Trees
Optimal Labeling Schemes for $Γ$-Free Matrices
Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
On the Largest Cardinality Subset Sum
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.