The Reinforcement Learning Problem and Markov Decision Processes

Hook #

Supervised learning had labels. Unsupervised learning had structure. Reinforcement learning has neither — it has a goal and *trial and error.* This is the third and most different paradigm of machine learning, and it's the one closest to how animals and humans actually learn: an agent takes actions in an environment, the environment responds with a new state and a reward (a scalar signal — good, bad, how good), and the agent must learn, purely from that reward feedback, a policy (a strategy for choosing actions) that maximizes reward over the long run. No one tells the agent the right action for each situation (that would be supervised learning); it only learns whether the actions it tried worked out — and, cruelly, often not immediately. This is the defining difficulty of RL, and it's worth naming up front: rewards are often delayed. A chess move that loses the game might have been the right move; the fatal mistake was ten moves earlier. The agent has to figure out which of its many actions deserve credit for a reward that arrives much later — the credit assignment problem. This lesson establishes the RL problem and the mathematical frame that makes it tractable: the Markov Decision Process (MDP) — states, actions, transitions, rewards, and a discount factor that trades off immediate versus future reward. RL is how machines learn to act, not just predict — the paradigm behind game-playing AI, robotics, and (as you'll see) the fine-tuning of the very language models you use.

What you'll be able to do by the end of this lesson #

• Define the RL problem — an agent learning to choose actions in an environment to maximize cumulative reward — and contrast it with supervised learning (no labeled "right answer," only evaluative reward feedback) and unsupervised learning (a goal and reward, not just structure).
• Name the core elements of the agent-environment loop: state (the situation), action (what the agent does), reward (the scalar feedback), policy (the agent's action-choosing strategy), and the loop itself (observe state → act → get reward + new state → repeat).
• Explain the Markov Decision Process (MDP) — the formal frame of RL — including the Markov property (the future depends only on the current state, not the full history) and why it makes the problem tractable.
• Explain return (cumulative future reward) and the discount factor (γ) — why future rewards are worth less than immediate ones, how γ trades off short- vs. long-term thinking — and articulate the credit assignment problem (which actions deserve credit for a delayed reward?).

A quick try before we start #

Picture teaching a dog a trick with only treats — no words it understands, no demonstration, just: the dog does something, and sometimes you give a treat. The dog doesn't know what earned the treat; it has to figure out which of its behaviors led to reward and do more of those. That's reinforcement learning: learn what to do from the consequences of doing, not from being told. Now make it concrete with a simple game. You're an agent in a grid-world maze. Your state is which cell you're in. Your actions are {up, down, left, right}. Most cells give reward 0, one cell (the exit) gives +10, and a lava cell gives −10. You start knowing nothing — not the maze layout, not where the exit is. You just move, and occasionally get a reward. Over many attempts, you must learn a policy: for each cell, which direction to go. Here's what makes it hard and interesting. First, the reward is delayed — you get the +10 only when you reach the exit, so how do you know that the move you made twenty cells ago was a good one? (Credit assignment.) Second, you face a dilemma every step: do you go the way that worked last time (exploit what you know), or try a new direction that might be a shortcut (explore the unknown)? Third — and this is the MDP's key simplification — to decide your next move, you only need to know where you are now (your current cell), not the entire history of how you got there. That "the current state is enough" assumption is the Markov property, and it's what makes the problem solvable. Hold the grid-world: it's the "hello world" of RL, and every concept in this course lands on it.

Why this matters here #

This lesson matters because RL is a fundamentally different way of framing what learning is, and that reframe unlocks an entire class of problems the other two paradigms can't touch: sequential decision-making under a goal. Supervised learning answers "what is this?" (classify, predict) and unsupervised answers "what's in here?" (structure, groups) — but neither can answer "what should I do?" over a sequence of decisions where actions have consequences that unfold over time. That question — how to act to achieve a goal, learning purely from the rewards your actions earn — is the RL question, and it describes an enormous range of real problems: playing games (chess, Go, video games — where AlphaGo and its successors reached superhuman play), controlling robots (a robot learning to walk, grasp, or fly from trial and error), managing resources (data-center cooling, traffic lights, inventory, trading), sequential recommendation (optimizing not the next click but long-term engagement), and — the connection that makes RL suddenly central to your daily work — aligning large language models (RLHF, Reinforcement Learning from Human Feedback, is how models like the one you're reading are tuned to be helpful — the reward is human preference, and the "actions" are the model's outputs). Understanding RL's frame is understanding how machines learn to behave, which is a distinct and powerful capability.

For a working engineer, the deeper value of this lesson is recognizing when a problem is an RL problem — and, just as importantly, when it isn't. RL is seductive (it feels like "real AI" — an agent learning by itself), but it's also notoriously hard to make work: it's sample-inefficient (needs enormous amounts of trial-and-error experience), unstable to train, and hard to debug. So the mature engineer's skill is pattern-matching the problem shape: a true RL problem has (1) sequential decisions (a series of actions, not one prediction), (2) delayed, evaluative feedback (you learn whether outcomes were good, not what the right action was, and often only later), and (3) actions that change the environment's state (what you do affects what you see next). When a problem has all three — a game, a control task, a multi-step strategy — RL is the right frame. When it doesn't (a one-shot prediction with labeled data), it's supervised learning wearing an RL costume, and you should not reach for RL's heavy, unstable machinery. The MDP is the formal tool that makes this precise: casting a problem as an MDP (identifying its states, actions, rewards, and transitions) is itself the crucial modeling step — often the hardest and most important part of applying RL, because a badly-specified reward or state representation dooms everything downstream. And the discount factor encodes a genuine design decision — how much should the agent value the future versus the present? — that shapes the entire behavior you'll get (a myopic agent that grabs immediate reward vs. a far-sighted one that sacrifices now for later). For the engineer, this lesson is the frame that lets you recognize, formulate, and reason about sequential-decision problems — the prerequisite for everything RL can do and the guard against misapplying it.

The engineer's lens #

The first lens is the agent-environment loop and why RL's feedback is evaluative, not instructive — the distinction that makes it a genuinely different paradigm. At the heart of RL is a simple loop that repeats forever: the agent observes the current state of the environment, chooses an action, and the environment responds by transitioning to a new state and emitting a reward (a single number). The agent's entire goal is to learn a policy — a mapping from states to actions (what to do in each situation) — that maximizes the total reward accumulated over time. What makes this fundamentally different from supervised learning is the nature of the feedback, a distinction worth holding precisely: supervised learning gives instructive feedback (for this input, here is the correct output — the label tells you exactly what you should have done), whereas RL gives evaluative feedback (that action earned reward 5 — but was 5 good? was there an action that would have earned 50? the environment doesn't say). Evaluative feedback tells you how good what you did was, not what you should have done — so the agent can't just be told the right answer and copy it; it must discover good actions by trying them and comparing outcomes. This is why RL involves exploration (you can't evaluate an action you never try) and why it's harder than supervised learning (no answer key to imitate). It's also why RL is the paradigm closest to natural learning — animals, children, and organizations mostly learn from consequences, not from a supervisor labeling every situation with the optimal response. For the engineer, internalizing "evaluative, not instructive" is the key to understanding why RL needs its whole distinctive apparatus (exploration, value estimation, credit assignment) that supervised learning doesn't: those tools all exist to cope with feedback that judges your actions without revealing the right ones.

The second lens is the Markov Decision Process — the formal frame — and why the Markov property is the simplification that makes RL solvable. RL problems are formalized as Markov Decision Processes, and understanding the MDP is understanding the structure of every RL problem. An MDP has five pieces: a set of states (the possible situations), a set of actions (what the agent can do), a transition function (given a state and action, the probabilities of landing in each next state — the environment's dynamics, often stochastic, drawing on the probability distributions from the probability course), a reward function (the reward for a given state/action/transition), and a discount factor (below). The crucial, load-bearing assumption is the Markov property: the future depends only on the current state, not on the entire history of how you got there. In the grid-world, to decide your next move you only need to know which cell you're in now — not the path you took to get there — because the current cell contains all the relevant information about your situation. This assumption is what makes RL tractable: it means the agent's policy can be a function of just the current state (not the whole history), collapsing an intractably large "history space" into a manageable "state space." When it holds, the powerful machinery of the coming lessons (value functions, Bellman equations, dynamic programming) all works. The engineer's insight is twofold. First, casting your problem as an MDP is the essential and often hardest modeling step — you must decide what the state is (it must capture everything relevant to the decision — if it doesn't, the Markov property fails and RL struggles), what the actions are, and what the reward function is (and reward design is notoriously tricky — a poorly-chosen reward produces bizarre, unintended behavior, a theme the last lesson returns to). Second, the Markov property is an assumption you're making about your problem, and real problems often violate it (the true state isn't fully observable — a poker player can't see opponents' cards), which leads to harder variants (partially-observable MDPs) — so recognizing whether your problem is genuinely Markov is part of the modeling judgment. The MDP is the lens through which every RL problem is viewed: identify the states, actions, transitions, and rewards, verify the Markov property roughly holds, and you've formulated the problem — which is more than half the battle.

The third lens is return, the discount factor, and credit assignment — how RL handles the fact that reward is cumulative and delayed, which is the source of its central difficulty and a key design lever. The agent doesn't maximize immediate reward; it maximizes the return — the cumulative reward over the future. But summing all future reward has a problem: over an infinite horizon it can be infinite (making different policies incomparable), and, more fundamentally, a reward now is generally worth more than the same reward later (it's more certain, and — as in finance — sooner is better). So RL uses a discount factor, γ (gamma), a number between 0 and 1, and defines the return as reward now plus γ times reward next step plus γ² times the reward after that, and so on — each future reward discounted by how far off it is. This does two things. Mathematically, it keeps the return finite (a geometric series) so policies are comparable. Behaviorally — and this is the design lever — γ tunes the agent's time horizon: a γ near 0 makes the agent myopic (it cares almost only about immediate reward — grab the treat in front of it), while a γ near 1 makes it far-sighted (it weighs distant rewards almost as much as immediate ones — willing to sacrifice now for a big payoff later). Choosing γ is choosing how much the agent should plan for the future, a genuine design decision with large behavioral consequences. And this cumulative-delayed structure is the source of RL's signature difficulty: the credit assignment problem. When a reward finally arrives (you reach the exit, you win the game), which of the many actions you took deserves the credit? The winning move? The move that set it up? The one twenty steps back that made it all possible? RL's central algorithmic challenge — solved by the value functions and temporal-difference methods of the coming lessons — is propagating credit backward from delayed rewards to the earlier actions that earned them. For the engineer, the synthesis of the lesson: reinforcement learning is the paradigm of learning to **act* — an agent taking actions in an environment to maximize cumulative reward from evaluative feedback (how good, not what's right), which is why it needs exploration and value estimation that supervised learning doesn't; the problem is formalized as a Markov Decision Process (states, actions, transitions, rewards) whose Markov property (the current state is sufficient) makes it tractable and whose formulation is the crucial modeling step; and the agent maximizes discounted return, with the discount factor γ tuning its time horizon — all against the backdrop of the credit assignment problem of tracing delayed rewards back to the actions that earned them.* This frame is the foundation the entire course builds on.

What to focus on in the resources #

• Sutton & Barto (free) Ch 1 & 3 — primary. The canonical RL text, free from the authors. Ch 1 frames the problem and paradigm; Ch 3 is the definitive MDP treatment (states, actions, rewards, return, discount). Read slowly — this defines the field's vocabulary. Everything else supplements it.
• David Silver — DeepMind RL, Lectures 1–2 (free). The AlphaGo lead's definitive video course, following Sutton & Barto. Lectures 1–2 cover the RL problem and MDPs with unmatched clarity — especially why RL is different (evaluative, delayed feedback; no supervisor). Watch alongside the book.
• Hugging Face Deep RL Course, Unit 1 (free, hands-on). Introduces the agent-environment loop with runnable code in Gymnasium (the standard environment library). Do it for the practical feel of an agent acting and receiving rewards — it grounds the formalism in something you can run.
• Skip on first pass: partially-observable MDPs (POMDPs), the measure-theoretic treatment of continuous state/action spaces, and average-reward (undiscounted) formulations. Get: the agent-environment loop, evaluative vs. instructive feedback (why RL differs from supervised), the MDP five-tuple, the Markov property (current state is sufficient → tractable) and that formulating the MDP is the hard modeling step, and discounted return + γ as the time-horizon lever, plus the credit assignment problem.

Explain it back #

Explain to a colleague how reinforcement learning differs from supervised learning, what a Markov Decision Process is, and why the discount factor matters. A strong answer: reinforcement learning is the paradigm of learning to act — an agent takes actions in an environment, receives a scalar reward and a new state, and must learn a policy (states → actions) that maximizes cumulative reward. It differs from supervised learning in the feedback: supervised feedback is instructive (the label tells you the correct answer to copy), but RL feedback is evaluative (the reward tells you how good your action was, not what you should have done) — so the agent must discover good actions by trying them (exploration), which is why RL needs machinery supervised learning doesn't. The problem is formalized as a Markov Decision Process: states, actions, a (probabilistic) transition function, a reward function, and a discount factor. Its key assumption is the Markov property — the future depends only on the current state, not the full history — which makes the problem tractable (the policy can depend on just the current state) and means formulating the MDP (choosing the state representation, actions, and reward) is the crucial, often hardest modeling step. The agent maximizes return (cumulative future reward), and the discount factor γ (0–1) weights future rewards less than immediate ones — mathematically keeping the return finite, and behaviorally tuning the time horizon: γ near 0 makes the agent myopic (grab immediate reward), γ near 1 makes it far-sighted (sacrifice now for later). The signature difficulty is credit assignment: when a reward arrives late (you finally win), which of your many earlier actions deserves the credit? — the problem the rest of RL exists to solve.

Where this connects #

Backward: RL is the third learning paradigm, completing the trio with the supervised and unsupervised courses — same field, radically different feedback (evaluative and delayed, not labeled or unlabeled). The MDP's probabilistic transitions draw on the distributions from the probability course, and its expected return is the expectation from the statistics course. The agent-environment loop is a kind of pipeline too, but one where the agent's actions change the data it sees next — unlike the fixed datasets of the prior courses.

Forward: This frame is the foundation for the whole course. The next lesson introduces value functions (V and Q — how good is a state or action?) and the Bellman equation, the tools that solve credit assignment by propagating value backward. Then come the learning-from-experience methods (Monte Carlo, temporal-difference, Q-learning), deep RL (neural networks as function approximators — the bridge to the deep-learning courses), and policy gradients + real-world applications. And the RL frame reaches beyond this course: RLHF (Reinforcement Learning from Human Feedback), the technique that aligns large language models, is RL where the "reward" is human preference — so this paradigm, seemingly about games and robots, is central to the LLM courses ahead. RL is how machines learn to act.