En informatique, un algorithme d'apprentissage incrémental ou incrémentiel est un algorithme d'apprentissage qui a la particularité d'être online, c'est-à-dire qui apprend à partir de données reçues au fur et à mesure du temps. À chaque incrément il reçoit des données d'entrées et un résultat, l'algorithme calcule alors une amélioration du calcul fait pour prédire le résultat à partir des données d'entrées. Puisqu'il ne connait pas l'intégralité des données, un algorithme d'apprentissage incrémental est forcé de faire des choix qui peuvent s'avérer finalement non optimaux ; l'étude des algorithmes d'apprentissage incrémental a ainsi mis l'accent sur la qualité des choix possibles dans une telle configuration. L'analyse compétitive formalise cette idée en comparant la performance, sur les mêmes données, de l'algorithme d'apprentissage incrémental et de l'équivalent ayant à disposition l'intégralité des données. Pour d'autres points de vue sur les algorithmes où les données deviennent disponibles au fur et à mesure du temps, voir les articles algorithme de fouille de flots de données (centré sur la quantité de mémoire nécessaire à représenter les données reçues dans le passé), dynamic algorithm (centré sur la complexité en temps pour manipuler les solutions à des problèmes à inputs online). Un problème illustrant le concept d'algorithme d'apprentissage incrémental est celui du voyageur de commerce canadien. Le but de ce problème est de minimiser le coût d'atteinte d'un sommet dans un graphe pondéré où certaines des arêtes sont peu « fiables » car elles peuvent à tout moment être retirées du graphe. Cependant, si une arête devient inutilisable, cela n'est révélé au "voyageur" uniquement lorsqu'il atteint l'un des sommets de cette arête. Le pire cas de ce problème a lieu lorsque toutes les arêtes peu fiables s'avèrent être inutilisables et le problème se réduit alors au problème du plus court chemin. Une analyse alternative du problème peut être effectuée à l'aide de l'analyse compétitive.