Nous étudions le problème du prèchargement (prefetching) quand il s'agit de minimiser le nombre de fois qu'un surfeur alèatoire tente d'accéder à un document qui n'est pas en mémoire. Contrairement aux études précédentes, nous supposons que le graphe de documents n'est pas connu entièrement et est découvert au fur et à mesure. Spécifiquement, nous supposons que ce graphe est un arbre aléatoire de profondeur d dont les noeuds ont un degré uniformément distribué entre 1 et p. Nous déterminons la politique de préchargement optimale pour certaines valeurs de d, p et du nombre de documents qu'il est possible de précharger à chaque tour. Les outils utilisés sont ceux de la théorie des processus de décision Markoviens.