dc.contributor.author Yazidi, Anis dc.contributor.author Granmo, Ole-Christoffer dc.contributor.author Oommen, John dc.contributor.author Goodwin, Morten dc.date.accessioned 2015-02-18T10:29:32Z dc.date.accessioned 2017-03-03T11:41:08Z dc.date.available 2015-02-18T10:29:32Z dc.date.available 2017-03-03T11:41:08Z dc.date.issued 2014 dc.identifier.citation IEEE Transactions on Cybernetics 2014, 44(11):2202-2220 language dc.identifier.issn 2168-2267 dc.identifier.uri https://hdl.handle.net/10642/4092 dc.description.abstract Stochastic point location (SPL) deals with the problem of a learning mechanism (LM) determining the optimal point on the line when the only input it receives are stochastic signals about the direction in which it should move. One can differentiate the SPL from the traditional class of optimization problems by the fact that the former considers the case where the directional information, for example, as inferred from an Oracle (which possibly computes the derivatives), suffices to achieve the optimization—without actually explicitly computing any derivatives. The SPL can be described in terms of a LM (algorithm) attempting to locate a point on a line. The LM interacts with a random environment which essentially informs it, possibly erroneously, if the unknown parameter is on the left or the right of a given point. Given a current estimate of the optimal solution, all the reported solutions to this problem effectively move along the line to yield updated estimates which are in the neighborhood of the current solution.1 This paper proposes a dramatically distinct strategy, namely, that of partitioning the line in a hierarchical tree-like manner, and of moving to relatively distant points, as characterized by those along the path of the tree. We are thus attempting to merge the rich fields of stochastic optimization and data structures. Indeed, as in the original discretized solution to the SPL, in one sense, our solution utilizes the concept of discretization and operates a uni-dimensional controlled random walk (RW) in the discretized space, to locate the unknown parameter. However, by moving to nonneighbor points in the space, our newly proposed hierarchical stochastic searching on the line (HSSL) solution performs such a controlled RW on the discretized space structured on a superimposed binary tree. We demonstrate that the HSSL solution is orders of magnitude faster than the original SPL solution proposed by - ommen. By a rigorous analysis, the HSSL is shown to be optimal if the effectiveness (or credibility) of the environment, given by $p$ , is greater than the golden ratio conjugate. The solution has been both analytically solved and simulated, and the results obtained are extremely fascinating, as this is the first reported use of time reversibility in the analysis of stochastic learning. The learning automata extensions of the scheme are currently being investigated. language dc.language.iso en language dc.publisher IEEE language dc.relation.uri http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6742611 dc.subject Controlled random walk language dc.subject Discretized learning language dc.subject Learning automata language dc.subject Stochastic-point problem language dc.subject Time reversibility language dc.title A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme language dc.type Journal article dc.type Peer reviewed language dc.date.updated 2015-02-18T10:29:32Z dc.description.version publishedVersion language dc.identifier.doi http://dx.doi.org/10.1109/TCYB.2014.2303712 dc.identifier.cristin 1166754
﻿