Markov Decision Processes

Tags: #◇Computer Science #◇CSINTSY #◇Markov Decision Processes #◇Problem Solving #◇M6

---

◇Overview

A Markov Decision Process (MDP) provides a mathematical framework for modeling decision-making in environments where outcomes are uncertain. Unlike standard state-based models where actions deterministically lead to a specific state, MDPs account for the probability that an action might lead to various different states.

Key Components of an MDP:
States ($S$): The set of all possible states.
Actions ($A$): The set of actions available from a given state.
Transition Distribution $T(s, a, s')$: The probability of reaching a next state $s'$ given the current state $s$ and action $a$.
Reward $R(s, a, s')$: The reward received after transitioning from $s$ to $s'$ via action $a$.
Start / End States.

Goal:
The objective in an MDP is to find an Optimal Policy ($\pi_{opt}$), which is a rule or strategy defining the best action to take in every state to maximize the expected cumulative reward.

Discount Factor ($\gamma$):
A value between 0 and 1 that determines how much future rewards are valued compared to immediate rewards. A $\gamma$ close to 1 heavily weights long-term rewards.

◇Important Formulas

Optimal Value Function ($V_{opt}$):
Calculates the maximum expected reward achievable from state $s$.
$V_{opt}(s) = \begin{cases} 0 & \text{if IsEnd}(s) \\ \max_{a \in \text{Actions}(s)} \sum_{s'} T(s, a, s') \left( R(s, a, s') + \gamma V_{opt}(s') \right) & \text{otherwise} \end{cases}$

Optimal Policy ($\pi_{opt}$):
Determines the best action to take in state $s$.
$\pi_{opt}(s) = \arg\max_{a \in \text{Actions}(s)} \sum_{s'} T(s, a, s') \left( R(s, a, s') + \gamma V_{opt}(s') \right)$

◇Worked Examples

Iterative Algorithm (Value Iteration / Bellman Equation):

1. Initialize $V^{(0)}_{opt}(s) = 0$ for all states $s$.
2. For iteration $t = 1, 2, \dots$ until convergence:
   For each state $s$:
   $V^{(t)}_{opt}(s) = \max_{a} \sum_{s'} T(s,a,s') \left( R(s,a,s') + \gamma V^{(t-1)}_{opt}(s') \right)$
3. The process repeats until the change in optimal values between iterations falls below a specific threshold. The policy is then extracted using $\arg\max$.

Transport Puzzle with Uncertainty:
Walking takes 1 min deterministically (cost -1). Taking a tram takes 2 mins (cost -2) but has a 50% chance of failing to move the agent forward. The algorithm iteratively computes expected costs based on probabilities until the optimal path policy stabilizes.

◇References & Navigation

• Previous Topic: ◇Expert Systems Overview
• Next Topic: ◇Q-Learning
• Related Notes: ◇MDP, ◇Bayesian Inference