Efficient Exploration of Unknown Environments.
Yury Smirnov, Sven Koenig, Manuela Veloso.

Assume that an agent has to learn an unknown, bi-directed, strongly connected graph. 
Empirical analysis  shows  that  algorithms  with  optimal  worst-case  complexities
tend to perform poorly in average in this exploration problem.  The  best  practical
approach - the on-line nearest neighbor -  loses  significantly  in  special  cases.
We therefore develop the Variable  Edge  Weight  Algorithm  (VEWA),  an  algorithmic 
framework that can accommodate almost any exploration or search  strategy (including 
the on-line nearest neighbor algorithm). 
We use mathematical models with exponentially growing precision to  build  a  simple 
exploration framework achieving, for example, the optimal  complexity  of  exploring 
bi-directed (Eulerian) static environments with finite number of states and actions.
While "impractical" models appear to be useful in deriving the desirable complexity, 
practical implementations solve the precision problem by considering priority  lists 
instead of growing weights. 
Unlike other exploration strategies VEWA has optimal performance guarantees on sparse
Eulerian graphs and even better performance guarantees on dense bi-directed unit edge
length graphs, has a competitive empirical performance, and is robust in  dynamically 
changing environments.