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.

Additional Metadata
Conference Proceedings of the 1996 1st Joint Conference on Intelligent Systems/ISAI/IFIS
Citation
Oommen, J, & Raghunath, G. (G.). (1996). Stochastic point location: A solution using learning automata and intelligent tertiary search. In Proceedings of the Joint Conference on Intelligent Systems/ISAI/IFIS (pp. 221–227).