## On solving the SPL problem using the concept of probability flux

##### Journal article, Peer reviewed

##### Accepted version

##### Permanent lenke

https://hdl.handle.net/10642/8492##### Utgivelsesdato

2019-02-02##### Metadata

Vis full innførsel##### Samlinger

##### Originalversjon

Abolpour Mofrad A, Yazidi A, Hammer HL. On solving the SPL problem using the concept of probability flux. Applied intelligence (Boston). 2019;49(7):2699-2722 http://dx.doi.org/10.1007/s10489-018-01399-9##### Sammendrag

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.