Solving Stationary and Stochastic Point Location Problem with Optimal Computing Budget Allocation

Stochastic point location (SPL) is to search for a target point on the line in stochastic environment. An SPL solver can be described as a Learning Machine (LM) attempting to locate a target point on a line. By using the prompts from stochastic environment, possibly erroneous, the LM moves along the line yielding updated estimates to approximate the target point. This paper proposes an SPL algorithm based on Optimal Computing Budget Allocation (OCBA), named as SPL-OCBA, which employs OCBA and the historical sample information to guide to the location of a target point in stationary and stochastic environment. The proposed algorithm partitions or combines the subintervals of the target line adaptively. Then, OCBA considers such subintervals as its designs and allocates the sample budget for them based on the historical data, thereby resulting in a new method. Extensive experiments show that the newly proposed algorithm is significantly more efficient than the existing ones.