 Efficient exploration of MDPs is given in Burnetas and Katehakis (1997).Finite-time performance bounds have also appeared for many algorithms, but these bounds are expected to be rather loose and thus more work is needed to better understand the relative advantages and limitations.For incremental algorithms, asymptotic convergence issues have been settled.