Markov Decision Process

A Markov Decision Process (MDP) is a mathematical framework used to model decision-making in situations where outcomes are partly random and partly under the control of a decision-maker. It serves as the foundational formalization for Reinforcement Learning problems.

Core Components

An MDP is formally defined by a 5-tuple $(S,A,P,R,\gamma )$:

• States ($S$): The set of all possible environmental configurations or situations.
• Actions ($A$): The set of all choices or moves available to the agent.
• Transition Probability ($P$): The probability $P(s^{\prime }|s,a)$ of moving to state $s^{\prime }$ after taking action $a$ in state $s$.
• Reward Function ($R$): The feedback signal $R(s,a,s^{\prime })$ received after transitioning from state $s$ to $s^{\prime }$ via action $a$.
• Discount Factor ($\gamma$): A value $\gamma \in [0,1]$ that determines the importance of future rewards relative to immediate ones.

Key Features

1. The Markov Property: The future state depends solely on the current state and action, not on the history of previous states or actions. Formally: $P(S_{t+1}=s^{\prime }\mid S_t=s_t,A_t=a_t,S_{t-1}=s_{t-1},\dots )=P(S_{t+1}=s^{\prime }\mid S_t=s_t,A_t=a_t)$
2. Sequential Optimization: Decisions are made over time, where each action influences future states and reward possibilities.
3. Stochastic Nature: Outcomes are probabilistically defined, allowing the framework to model environmental uncertainty.
4. Bellman Optimality: The goal is to discover an optimal policy ${\pi }^{\ast }$ that maps states to actions to maximize the cumulative expected discounted reward, satisfying the Bellman Equations.

Related Topics

• Reinforcement Learning (RL): The study of learning optimal policies in an MDP when transition dynamics are unknown.
• Dynamic Programming (DP): Algorithms like Value Iteration and Policy Iteration used to solve MDPs when the model dynamics are fully known.
• Q-Learning: A model-free reinforcement learning algorithm used to find optimal action-selection policies for any given MDP.
• Partially Observable Markov Decision Process (POMDP): A generalization of MDPs where the agent cannot directly observe the underlying state.