  In this paper, we provide two new stable online algorithms for the problem of
prediction in reinforcement learning, \emph{i.e.}, estimating the value
function of a model-free Markov reward process using the linear function
approximation architecture and with memory and computation costs scaling
quadratically in the size of the feature set. The algorithms employ the
multi-timescale stochastic approximation variant of the very popular cross
entropy (CE) optimization method which is a model based search method to find
the global optimum of a real-valued function. A proof of convergence of the
algorithms using the ODE method is provided. We supplement our theoretical
results with experimental comparisons. The algorithms achieve good performance
fairly consistently on many RL benchmark problems with regards to computational
efficiency, accuracy and stability.
