Markov Decision Processes

This is the formal backbone of reinforcement learning — the branch of AI where an agent learns by trying actions and receiving rewards. Understanding MDPs unlocks: how LLM agents decide which tool to call, how a robot learns to walk, how AlphaGo chose moves, and how a recommendation system decides what to show next. Nearly every modern AI system that acts over time is solving an MDP — often without knowing its exact rules. Master this and you can read any reinforcement learning paper, understand 'reward hacking', and design the reward functions that shape agent behaviour.

Imagine you are playing a board game where you roll a die and move tokens. The game has a few positions on the board (states). At each position you can choose an action — say move left, move right, or stay. The die is random, so your action doesn't always lead where you want: sometimes you roll a 6 and jump ahead. Each time you land on a square, you get a reward — maybe points, maybe nothing. You want to maximise the total points you collect over the whole game, not just the immediate one. The key trick: you need to think ahead. A move that gives a small reward now might lead to a huge reward later, or a quick reward might trap you in a dead end. An MDP captures exactly this: a set of states (squares), a set of actions (moves), a rule for how the die changes your position (transition probabilities), a reward for each landing, and a way to 'discount' future rewards so you don't just wait for a distant jackpot while starving now. If the game's rules are unknown — you have to discover them by playing — then you are doing reinforcement learning, which is just solving an MDP from experience.

Think of a taxi driver navigating a city to earn fares. The 'states' are the intersections — each corner has a different set of possible passengers, traffic, and destinations. The 'actions' are the decisions: turn left, go straight, turn right. The driver doesn't know exactly what will happen after each turn: a turn might lead to a traffic jam (bad) or a shortcut (good). The 'transition probability' is the likelihood of each outcome — turning onto a main road usually moves you fast, but sometimes there's a parade. The 'reward' is the fare earned when a passenger gets out, plus a small penalty for time wasted in traffic. The driver wants to maximise total income over the shift, not just the next fare — so they sometimes skip an immediate pickup because heading to the airport will pay more later. The 'discount factor' is like a driver who values money now more than money in an hour: a ₹100 fare now is worth more than a ₹100 fare promised two hours later. The Markov property is the claim that the driver only needs to remember where they are now — not every street they've driven before — to decide the next good turn. That's true in a city where traffic depends only on the current intersection, not on your history. Where it breaks: if a road is closed behind you because you just drove over a bridge that collapsed, then the history matters — you need to know you came from that bridge. In that case, you'd artificially add 'came from the collapsed bridge' to your state, so the Markov property holds again. The analogy stops at that point: real navigation sometimes needs history, but MDPs assume you can encode everything relevant into the current state.

A Markov Decision Process is a formal model of sequential decision-making: a set of states, a set of actions, transition probabilities (the chance of moving from one state to another given an action), a reward function (the payoff for each transition), and a discount factor between 0 and 1 that weights future rewards against immediate ones, all under the Markov property that the future depends only on the current state, not on the history.

This sits inside Probability Theory, your library's parent concept. The transition probabilities are conditional probabilities — the chance of the next state given the current state and action. The reward you expect to accumulate is an expectation (a weighted average over outcomes). The discount factor is a geometric series, which you've met in interest calculations. Your library also has notes on Concentration Inequalities, which bound how far an average reward estimate can stray from its true value — useful when you estimate transition probabilities from limited experience. Eigenvalues and Eigenvectors appear in the linear algebra of solving large MDPs, but you don't need them yet. The Markov property is the same idea as in a Markov chain, but with actions added.