A Solution to the Stochastic Point Location Problem in Metalevel Nonstationary Environments

This paper reports the first known solution to the stochastic point location (SPL) problem when the environment is nonstationary. The SPL problem involves a general learning problem in which the learning mechanism (which could be a robot, a learning automaton, or, in general, an algorithm) attempts to learn a "parameter," for example, lambda*, within a closed interval. However, unlike the earlier reported results, we consider the scenario when the learning is to be done in a nonstationary setting. For each guess, the environment essentially informs the mechanism, possibly erroneously (i.e., with probability p), which way it should move to reach the unknown point. Unlike the results available in the literature, we consider the fascinating case when the point sought for is itself stochastically moving (which is modeled as follows). The environment communicates with an intermediate entity (referred to as the teacher/oracle) about the point itself, i.e., advising where it should go. The mechanism that searches for the point in turn receives responses from the teacher/oracle, which directs how it should move. Therefore, the point itself, in the overall setting, is moving, i.e., delivering possibly incorrect information about its location to the teacher/oracle. This in turn means that the "environment" is itself nonstationary, which implies that the advice of the teacher/oracle is both uncertain and changing with time - rendering the problem extremely fascinating. The heart of the strategy we propose involves discretizing the space and performing a controlled random walk on this space. Apart from deriving some analytic results about our solution, we also report the simulation results that demonstrate the power of the scheme, and state some potential applications.