On solving the SPL problem using the concept of probability flux

Abstract

The Stochastic Point Location (SPL) problem [20] is a fundamental learning problem that has recently found a lot of research attention. SPL can be summarized as searching for an unknown point in an interval under faulty feed- back. The search is performed via a Learning Mechanism (LM) (algorithm) that interacts with a stochastic Environment which in turn informs it about the direc- tion 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 two decades ago by Oommen, relies on discretizing the search interval and perform- ing 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, i.e., infinite memory. However, this strategy yields rather poor accuracy for low discretization resolutions. In this paper, we present two major contributions to the SPL problem. First, we demonstrate that the estimation of the point location can significantly be improved by resorting to the concept of mutual probability ux between neighboring states along the line. Second, we are able to accurately track the position of the optimal point and simultaneously show a method by which we can estimate the error probability characterizing the Environment. Interestingly, learning this error probability of the Environment takes place in tandem with the unknown location estimation. We present and analyze several experiments discussing the weaknesses and strengths of the different methods.