Discussion autour des processus de décision markoviens

À quel point est-il difficile pour un robot de visiter un ensemble de cibles infiniment souvent ? Discussion autour des processus de décision markoviens. Pour tous les processus de décision markoviens et pour tous les ensembles de cibles, les stratégies markoviennes avec seulement 1 bit de mémoire supplémentaire sont suffisantes pour assurer la visite des cibles infiniment souvent, avec une probabilité arbitraire proche de l’optimale. Dans la figure à l’écran, il y a des états "noisette" qui doivent être vus infiniment de fois. La stratégie conserve un compteur de pas et permet de basculer entre deux modes : un écureuil affamé qui doit trouver une noisette à tout prix, et un lapin paniqué qui doit être prudent. Cela résout un problème laissé ouvert en théorie des jeux de hasard pendant 40 ans.