Markov Decision Process (MDP) in Reinforcement Learning

 

✅ Markov Decision Process (MDP) in Reinforcement Learning

A Markov Decision Process (MDP) is the standard mathematical framework used to model decision-making problems where outcomes depend on both randomness and the agent’s actions.

It describes how an agent interacts with an environment to learn the best behavior.

Core Idea (Simple Intuition)

An agent repeatedly:

  1. Observes the current state

  2. Takes an action

  3. Receives a reward

  4. Moves to a new state

The goal is to choose actions that maximize total future reward.

The Markov Property

MDPs assume the Markov property:

The future depends only on the current state, not on past history.

P(St+1∣St,At,St−1,...)=P(St+1∣St,At)P(S_{t+1}|S_t,A_t,S_{t-1},...) = P(S_{t+1}|S_t,A_t)

This makes learning and optimization tractable.

Components of an MDP

An MDP is defined by the tuple:

(S,A,P,R,γ)(S, A, P, R, \gamma)

✅ 1. States (S)

All possible situations of the environment
Example: robot position, game board configuration

✅ 2. Actions (A)

Choices available to the agent
Example: move left/right, accelerate, pick object

✅ 3. Transition Probability (P)

P(s′∣s,a)P(s'|s,a)

Probability of moving from state ss to s′s' after action aa.

Handles uncertainty in environment.

✅ 4. Reward Function (R)

R(s,a,s′)R(s,a,s')

Immediate feedback received after action.

  • Positive → good action

  • Negative → penalty

✅ 5. Discount Factor (γ\gamma, 0–1)

Controls importance of future rewards.

  • γ≈0\gamma \approx 0→ focus on immediate reward

  • γ≈→ long-term planning

Objective of Reinforcement Learning

Find a policy π(a∣s)\pi(a|s) that maximizes expected return:

Gt=Rt+1+γRt+2+γ2Rt+3+⋯G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots

Policy = rule for choosing actions in each state.

Example: Robot Navigation

Environment

Grid world

States

Robot positions on grid

Actions

Up, Down, Left, Right

Rewards

  • +10 for reaching goal

  • −1 for each step

  • −10 for hitting obstacle

Transition

Sometimes movement fails → randomness

This forms a complete MDP model.

Value Functions in MDP

🔹 State Value Function

Vπ(s)=expected total reward from state sV^\pi(s)=\text{expected total reward from state } s

Measures how good a state is under policy π\pi.

🔹 Action Value Function (Q-function)

Qπ(s,a)=expected reward after taking action a in state sQ^\pi(s,a)=\text{expected reward after taking action } a \text{ in state } s

Used in algorithms like Q-learning.

Bellman Equation (Key Concept)

The value of a state equals:

V(s)=R(s)+γ∑s′P(s′∣s,a)V(s′)V(s)=R(s)+\gamma\sum_{s'}P(s'|s,a)V(s')

Meaning:

Current value = immediate reward + discounted future value.

This recursive relationship enables dynamic programming methods.

Why MDPs Are Important in RL

They provide:

  • Formal model of agent-environment interaction

  • Basis for algorithms:

    • Value Iteration

    • Policy Iteration

    • Q-Learning

    • SARSA

    • Deep RL methods

Almost all reinforcement learning problems are modeled as MDPs.

Real Applications

  • Robotics navigation

  • Game playing (chess, Go, Atari)

  • Self-driving cars

  • Recommendation systems

  • Resource allocation and scheduling

Comments

Post a Comment

Popular posts from this blog

Advanced Mathematics for Computer Science HNCST409 KTU BTech Honors 2024 Scheme

About Me Syllabus Advanced Mathematics for Computer Science HNCST409 BTech Honors 2024 Model Question Paper and Answers Module- I Number Theory  Introduction Group , Ring and Fields Divisibility Modular Arithmetic and Congruences Equivalence Relation - Congruence Linear Congruences Solving simultaneous congruences- CRT Modular Inverses      Euclidean algorithm      Extended Euclidean algorithm  Euler’s and Fermat’s little theorem  Euler's Totient Function Prime Numbers and Prime-Power Factorization Fermat and Mersenne Prime Primality Testing and Factorization Wilson's Theorem Pseudo Primes and Carmichael Numbers Primality testing       Miller-Rabin      AKS Galois Field (introduction and basic operations) RSA cryptosystem: key generation - encryption/decryption  Hash functions (introduction) Module - II Optimization Convex and Non Convex sets Convex Hull Identifying convex sets Applicatio...
Read more

Convex and Non Convex Sets

Image
Convex Sets Intuitive Idea A convex set is a collection of points such that the straight line segment connecting any two points in the set lies entirely within the set . Think of a solid ball or a solid square : no matter which two points you choose, the line between them never goes outside. A non-convex set has dents, holes, or gaps , so a line between two points may pass outside the set. Visual Intuition Convex → no dents or holes Non-convex → has indentations or holes Pic Curtesy: wikipedia Definition (Simple Terms) The Rule Pick any two points in the set. Draw the straight line segment between them. If the entire line stays inside the set , the set is convex. If this fails even once, the set is non-convex . Mathematical Definition A set C ⊆ R n C \subseteq \mathbb{R}^n   is convex if for any two points x 1 , x 2 ∈ C x_1, x_2 \in C  and for any number θ ∈ [ 0 , 1 ] \theta \in [0,1] , θ x 1 + ( 1 − θ ) x 2 ∈ C \theta x_1 + (1 -...
Read more

Gradient-Based Methods for Optimization-Gradient Descent Algorithm

  Gradient-Based Methods for Optimization (with Gradient Descent Algorithm) 1. Optimization Problem Setup In optimization, we aim to find min ⁡ x ∈ R n f ( x ) \min_{x \in \mathbb{R}^n} f(x) where: f ( x ) f(x)  is a real-valued objective function x = ( x 1 , x 2 , … , x n ) x = (x_1, x_2, \dots, x_n)  is a vector of variables In machine learning, f ( x ) f(x)  is typically a loss or cost function . 2. What is a Gradient-Based Method? A gradient-based method uses first-order derivative information (the gradient) to guide the search for an optimum. Key Idea The gradient ∇ f ( x ) \nabla f(x)  points in the direction of steepest increase The negative gradient points in the direction of steepest decrease 📌 Hence, to minimize a function, we move in the negative gradient direction . 3. Geometric Interpretation of the Gradient The gradient is perpendicular to level curves Moving along − ∇ f ( x ) -\nabla f(x)  decreases th...
Read more