Dans un problème d'apprentissage par renforcement, un agent évoluant dans un environnement aléatoire doit cumuler un maximum de récompenses en choisissant au fil du temps la meilleure politique, c'est-à-dire la meilleure réaction possible à ses observations. Une telle situation est modélisée par un processus de décision markovien : on suppose que la suite des états que traverse l'agent est une chaîne de Markov dont les noyaux de transitions successifs sont déterminés par les actions choisies, et on admet que la récompense reçue à chaque instant est une fonction (aléatoires) de l'état courant. Quand les propriétés probabilistes de l'environnement sont connues, la détermination de la politique optimale, qui constitue le problème dit de planification, est typiquement un problème de programmation dynamique.