Neuro-dynamic programming for the exploration of unknown graphs

In this paper, the problem of exploring stochastic graphs is addressed. The definition of the entropy related to the a-priori unknown parameters (the lengths of the a-priori unknown links) leads to the formulation of the problem as a stochastic optimal control one. The application of exact Dynamic Programming suffers the so-called curse of dimensionality. To overcome this drawback, an approximate technique is proposed making use of Neuro-Dynamic Programming. Exploiting the concept of frontier, any approximate solution of the problem is shown to generate a "proper" policy.