Markov Decision Processes (MDPs) Explained | CS188 Lecture 8

Added:

Bounded Rationality and Heuristic Decision-Making

While Markov Decision Processes (MDPs) offer mathematically elegant frameworks for calculating optimal policies, critics argue they are computationally intractable for complex, real-world scenarios—a challenge known as the "curse of dimensionality." The theory of Bounded Rationality, pioneered by Herbert Simon, posits that real-world agents (including humans and practical AI systems) have limited computational resources, time, and information. Consequently, they cannot calculate exact transition probabilities or discount factors across vast state spaces. Instead of seeking mathematically optimal policies through value iteration, agents rely on fast and frugal heuristics, satisficing (finding "good enough" solutions), or robust decision-making frameworks that do not assume a perfectly modeled, Markovian environment.

Basic probability theory, including conditional probability, random variables, and expected values.
Classical search algorithms (such as BFS, DFS, and A* search) and how to represent problems using state-space graphs.
The fundamentals of utility theory and the principle of maximizing expected utility in decision-making.
Policy Iteration, as a distinct and often faster algorithm for computing optimal policies compared to Value Iteration.
Reinforcement Learning (RL) foundations, specifically Q-learning and Temporal Difference (TD) learning, where transition probabilities and reward functions are unknown to the agent.
Partially Observable Markov Decision Processes (POMDPs) to model environments where the agent cannot perfectly observe the current state.
Deep Reinforcement Learning (Deep RL) to scale these decision-making algorithms to complex, high-dimensional state spaces using neural networks.
125.7K views1.1Klikes1:07:10@CS188Spring2013Original Release: 2013-02-15

Markov Decision Processes (MDPs) model sequential decision-making under uncertainty using states, actions, transition probabilities, and rewards, where the Markov property ensures future outcomes depend only on the current state and action. The goal is to find an optimal policy that maximizes the expected sum of discounted rewards over time, achieved through value iteration which iteratively computes value functions V(s) and Q(s,a) using the Bellman equation until convergence.