Efficient Web Spidering with Reinforcement Learning

Consider the task of exploring the Web in order to find pages of a particular kind or on a particular topic. This task arises in the construction of domain-specific search engines. A selective, directed web spider can be much more efficient than a spider that gathers new pages indiscriminantly. This paper argues that the creation of efficient web spiders is best framed and solved by reinforcement learning, a branch of machine learning that concerns itself with optimal sequential decision making. One strength of reinforcement learning is that it provides a formalism for measuring the utility of actions that give no immediate benefit, but do give benefit in the future. Topic-specific spidering fits into the reinforcement learning framework because valuing hyperlinks with future reward is important. Experimental results on large collections of real web data show that a reinforcement learning spider finds relevant pages three times faster than a competing spider based on breadth first sear..