  We introduce a new framework for web page ranking -- reinforcement ranking --
that improves the stability and accuracy of Page Rank while eliminating the
need for computing the stationary distribution of random walks. Instead of
relying on teleportation to ensure a well defined Markov chain, we develop a
reverse-time reinforcement learning framework that determines web page
authority based on the solution of a reverse Bellman equation. In particular,
for a given reward function and surfing policy we recover a well defined
authority score from a reverse-time perspective: looking back from a web page,
what is the total incoming discounted reward brought by the surfer from the
page's predecessors? This results in a novel form of reverse-time
dynamic-programming/reinforcement-learning problem that achieves several
advantages over Page Rank based methods: First, stochasticity, ergodicity, and
irreducibility of the underlying Markov chain is no longer required for
well-posedness. Second, the method is less sensitive to graph topology and more
stable in the presence of dangling pages. Third, not only does the reverse
Bellman iteration yield a more efficient power iteration, it allows for faster
updating in the presence of graph changes. Finally, our experiments demonstrate
improvements in ranking quality.
