Markov Decision Process

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

Key Features

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

• States ($S$): A finite or infinite set of environmental states.
• Actions ($A$): A finite set of actions available to the agent.
• Transition Probability ($P$): The probability $P(s^{\prime }|s,a)$ that action $a$ in state $s$ at time $t$ will lead to state $s^{\prime }$ at time $t+1$.
• Reward ($R$): The immediate reward $R(s,a,s^{\prime })$ received after transitioning from state $s$ to state $s^{\prime }$ due to action $a$.
• Discount Factor ($\gamma$): A factor $\gamma \in [0,1]$ representing the difference in value between present and future rewards.
• Markov Property: The key assumption that the transition probabilities depend only on the current state and action, not on historical states or actions: $P(S_{t+1}|S_t,A_t,\dots ,S_0,A_0)=P(S_{t+1}|S_t,A_t)$.

Related Topics

• Bellman Equation: Recursive equations that decompose value functions into immediate rewards and discounted future values.
• Dynamic Programming: Model-based techniques like Value Iteration and Policy Iteration used to solve MDPs when transition and reward functions are fully known.
• Q-Learning: A model-free reinforcement learning algorithm used to find optimal action-selection policies for any given MDP.
• Partially Observable MDPs (POMDPs): A generalization of MDPs where the agent cannot directly observe the complete environment state.