- In many cases the best way to find a profile or a set of profiles matching some criteria in a socialnetwork is via targeted crawling. An important challenge in targeted crawling is choosing the next profileto explore. Existing heuristics for targeted crawling are usually tailored for specific search criterionand could lead to short-sighted crawling decisions. In this paper we propose and evaluate a generic ap- proach for guiding targeted crawling which is based on recent developments in Artificial Intelligence. Ourapproach, based on the recently introduced variant of the Multi-Armed Bandit problem with volatile arms(VMAB), aims to provide a proper balance between exploration and exploitation during the crawling process. Unlike other heuristics which are hand tailored for specific type of search queries, our approach isgeneral-purpose. In addition, it provides provable performance guarantees. Experimental results indicate that our approach compares favorably with the best existing heuristics on two different domains.