Markov Decision Process

An MDP is a mathematical framework for modeling decision-making under uncertainty. It consists of a set of states, actions, and transition probabilities. At each time step, an agent selects an action in a given state, leading to a new state and a reward. The process follows the Markov property, where future states depend only on the current state and action. The goal is to find an optimal policy that maximizes the expected cumulative reward over time. MDPs are widely used in fields such as artificial intelligence and robotics for modeling and solving sequential decision problems.

Model

An MDP is defined as a tuple $(S,A,T,R,\gamma )$ where

• $S$ is the set of the environmental states
• $A$ is the set of actions that can be performed (can depend on the state)
• $T:S\times A\to S$ is a transition function
• $R:S\times A\to \mathbb{R}$ is a reward function
• $\gamma$ is a discount factor

The objective of an agent in this setup is to maximize the sum of rewards by learning what to do: in each state find the optimal policy.

Mathematical framework

Let $t$ be an integer and denote by:

• $S_t$ the state of the agent at time $t$
• $R_t$ the immediate reward at time $t$
• $p(s^{\prime },r|s,a)=\mathbb{P}(S_t=s^{\prime },R_t=r|S_{t-1}=s,A_{t-1}=a)$
• $p(s^{\prime }|s,a)=\mathbb{P}(S_t=s^{\prime }|S_{t-1}=s,A_{t-1}=a)=\sum _{r}p(s^{\prime },r|s,a)$
• $r(s,a)=\mathbb{E}(R_t|S_{t-1}=s,A_{t-1}=a)$
• $G_t={\displaystyle \sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}}$
• $\pi (a|s)$ : probability of choosing action $a$ in state $s$ (policy)

Bellman equation

Denote by $Q^{\star }$ an optimal $Q$-function, that is an optimal choice of action $a$ in state $s$. Then $Q^{\star }$ satisfies the Bellman equation below:

This is a consequence of the law of total probabilities and the fact that for a given policy $\pi$:

If the environment is stochastic, that is if taking action $a$ in state $s$ will lead to a stochastic state $s^{\prime }$, the Bellman equation becomes:

See also

• Q-Learning
• Deep Q-Learning