Markov Decision Process

An MDP is the formal framework for sequential decision-making under uncertainty.

Defined by the tuple $(S, A, P, R, \gamma)$:

• $S$ — set of states
• $A$ — set of actions
• $P(s'|s,a)$ — transition probability (dynamics): probability of reaching $s'$ from $s$ after action $a$
• $R(s,a)$ — reward function: immediate reward for taking action $a$ in state $s$
• $\gamma \in [0,1)$ — discount factor: how much future rewards are worth relative to immediate

Markov property: the future depends only on the current state, not the history: $P(s_{t+1}|s_t, a_t) = P(s_{t+1}|s_0, a_0, \dots, s_t, a_t)$

Policy $\pi(a|s)$: probability of taking action $a$ in state $s$. The agent's strategy.

Return: total discounted reward from time $t$: $G_t = \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}$

The goal: find policy $\pi^*$ that maximizes expected return $\mathbb{E}_\pi[G_0]$.

Discount factor $\gamma$:

• $\gamma \to 0$: myopic, only cares about immediate reward
• $\gamma \to 1$: far-sighted, values future reward almost equally
• Also ensures the infinite sum converges (if rewards are bounded)

See also: Value Functions, Bellman Equations, Dynamic Programming in RL