Stochastic point location: A solution using learning automata and intelligent tertiary search

Consider the problem of a learning mechanism (robot, or algorithm) attempting to locate a point on a line. The mechanism interacts with a random `Oracle' (`Environment') which essentially informs it, possibly erroneously, which way it should move. This problem is a generalization of the `Deterministic Point Location Problem' studied by Baeza-Yates et al. The first reported paper to solve this problem presented a solution which operated in a discretized space. In this paper we present a new scheme by which the point can be learnt using a combination of various learning principles and utilizes the generalized philosophy of Bentley and Yao's unbounded binary search algorithm. The heart of the strategy involves performing a controlled random walk on the underlying space and then intelligently pruning the space using an adaptive tertiary search. The overall learning scheme is shown to be ε-optimal. As in the case of the application of the solution in non-linear optimization has been alluded to. Our strategy can be utilized to determine the best parameter to be used in an optimization module