Solving Stochastic Point Location Problem in a Dynamic Environment with Weak Estimation

Abstract

The Stochastic Point Location (SPL) problem introduced by Oommen [7] can be summarized as searching for an unknown point in the interval under a possibly faulty feedback. The search is performed via a Learning Mechanism (LM) (algorithm) that interacts with a stochastic environment which in turn informs it about the direction of the search. Since the environment is stochastic, the guidance for directions could be faulty. The first solution to the SPL problem which was pioneered by Oommen [7] two decades ago relies on discretizing the search interval and performing a controlled random walk on it. The state of the random walk at each step is considered to be the estimation of the point location. The convergence of the latter simplistic estimation strategy is proved for an infinite resolution. However, the latter strategy yields rather poor accuracy for low resolutions. In this paper, we present sophisticated tracking methods that outperform Oommen strategy [7]. Our methods revolve around tracking some key statistical properties of the underlying random walk using the family of weak estimators. Furthermore, we address the settings where the point location is non-stationary, i.e. LM is searching with uncertainty for a (possibly moving) point in an interval. In such settings, asymptotic results are no longer applicable. Simulation results show that the proposed methods outperform Oommen method for estimating point location by reducing the estimated error up to 75%.