The Mathematical Framework for RL

A Markov Decision Process (MDP) is a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision-maker.

An MDP is defined by a tuple: (S, A, P, R, γ)

S: A set of states.
A: A set of actions.
P(s' | s, a): The state transition probability. This is the probability of transitioning to state s' after taking action a in state s.
R(s, a, s'): The reward function. This gives the reward for transitioning from state s to s' by taking action a.
γ (gamma): The discount factor (0 ≤ γ ≤ 1). It determines how much we care about future rewards versus immediate rewards. A γ of 0 means we only care about the immediate reward, while a γ close to 1 means we value future rewards highly.

The Markov Property

The "Markov" in MDP means that the future is independent of the past, given the present. In other words, the current state s contains all the information needed to make the optimal decision. We don't need to know the history of how we got to this state.