The Cost of Missed States: Online Tracking with Current-Observation Resets

Hiroyasu Usami

Submitted by Hiroyasu Usami

Published October 29, 2026 · Version v1, October 29, 2026 · DOI 10.66977/xsci.2610.003a

Theoretical Computer Science

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.

View PDF