Ein sogenannter diskreter -stufiger Prozeß ist ein Prozeß, bei dem der Zustand des Prozesses durch aufeinanderfolgende `Entscheidungen' (Aktionen) geändert wird. Ein diskreter -stufiger Prozeß hat die Markov-Eigenschaft, wenn nach Entscheidungen der Effekt der ausstehenden Entscheidungen auf eine den `Nutzen' von Entscheidungsfolgen bestimmende Kostenfunktion nur noch von dem Zustand des Systems nach der -ten Entscheidung und den folgenden Entscheidungen abhängt.
Viele deterministische Prozesse sind Markov-Prozesse. Beispiele sind nahezu alle Brettspiele: Es kommt nicht darauf an, wie man zu einem Spielzustand gekommen ist. Zu jedem Zeitpunkt ist alle Information, die man zum Weiterspielen braucht, in dem gegenwärtigen Zustand enthalten. Auch das oben erwähnte Balancierproblem kann zu einem Markov-Problem vereinfacht werden, wenn der Roboter zu jedem Zeitpunkt die zeitlichen Ableitungen der Stabposition als zusätzliche Eingabe bekommt.
Viele Prozesse sind jedoch keine Markov-Prozesse. Insbesondere für biologische Systeme typische Handlungsweisen hängen oft nicht nur vom gegenwärtig wahrnehmbaren Zustand der Umgebung ab, sondern auch von vergangenen Perzeptionen. Wir unterscheiden daher im folgenden zwischen Markov-Umgebungen und Nicht-Markov-Umgebungen und beziehen uns dabei auf die Natur der Schnittstelle zwischen Umgebung und Lernsystem: In einer Markov-Umgebung reicht stets die letzte Eingabe zur Voraussage der nächsten Eingabe aus. In Nicht-Markov-Umgebungen sind unter Umständen beliebig weit zurückliegende vergangene Ereignisse mit zu berücksichtigen.