Reinforcement Learning

Markov Decision Process Formalism

An MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior.

status: reviewimportance: criticaldifficulty 4/5math: graduateread: 20mlive demo

Back to Reinforcement Learning Next: Bellman Equations (review)

Concept Structure

Markov Decision Process Formalism

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

1prerequisites

5next concepts

3related links

Learner Contract

What this page should let you do.

You are here becauseAn MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior.

This Reinforcement Learning concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

Before thisProbability Basics

1 prerequisite listed; refresh them before leaning on the math or code.

Probability Basics

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextBellman Equations (review)

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.Then continue to Bellman Equations (review)

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.

Claims1/1 reviewed

Sources3 cited

Codeattached

Demolive

Reviewed2026-07-03

Updatedpage 2026-07-03

Learning item flow

4/4 sections readyAsk about this Research room

ConceptMarkov Decision Process FormalismReinforcement Learning EquationMarkov Decision Process Formalism equation 1Exact equation CodeMarkov Decision Process Formalism runnable code 1Exact runnable code DemoMarkov Decision Process Formalism interactive demoInteractive demo ClaimIn a finite discounted MDP, current state plus action determines the...Exact claim check SourceReinforcement Learning: An Introduction, Second EditionExact source

ConceptMarkov Decision Process FormalismReinforcement Learning

3 sources attachedLocal snapshot ready

concept:reinforcement-learning/mdp-formalism

Codenearby Predictbefore reveal Roomitem handoff

01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

Reinforcement learning begins with a promise:

If the agent tells us where it is and what it does, then the environment has a well-defined probability law for what happens next.

That promise is the Markov decision process, or MDP. It is not an algorithm. It does not say how to find a good policy. It is the formal contract that makes later ideas such as Bellman equations, value iteration, Q-learning, policy gradients, and RLHF-as-RL possible.

A state is useful only if it carries the information needed for prediction. If two histories look like the same state but have different next-state probabilities, the state description is incomplete. The fix is not to hope the Bellman equation saves us later. The fix is to add the missing variable, or explicitly treat the problem as partially observable.

Keep three objects separate:

$P(s' \mid s,a)$ is the environment's transition kernel for one chosen action.
$\pi(a \mid s)$ is the agent's policy, a distribution over actions.
$P_\pi(s' \mid s)$ is the next-state law after the policy mixes the action kernels.

Many RL confusions come from collapsing those three objects into one vague "what happens next" table.

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt

Equation 1 $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma,\rho_0).$ Equation 2 $\sum_{s'\in\mathcal{S}}P(s'\mid s,a)=1, \qquad P(s'\mid s,a)\ge 0.$

For a finite discounted MDP, define

\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma,\rho_0).

Here:

$\mathcal{S}$ is a finite set of states;
$\mathcal{A}$ is a finite set of actions;
$P(s'\mid s,a)$ is the probability of moving to next state $s'$ after taking action $a$ in state $s$ ;
$R(s,a,s')$ is the immediate reward received on that transition;
$\gamma\in[0,1)$ is the discount factor;
$\rho_0$ is the start-state distribution.

For every state-action pair, the transition kernel is a probability distribution:

\sum_{s'\in\mathcal{S}}P(s'\mid s,a)=1, \qquad P(s'\mid s,a)\ge 0.

The Markov property says the next step depends on the current state and action, not on the whole past history once those are known:

P(S_{t+1}=s'\mid S_t=s,A_t=a,S_{t-1},A_{t-1},\ldots) = P(S_{t+1}=s'\mid S_t=s,A_t=a).

A stochastic policy is another conditional distribution:

\pi(a\mid s)=P(A_t=a\mid S_t=s), \qquad \sum_{a\in\mathcal{A}}\pi(a\mid s)=1.

If the agent follows $\pi$ , the one-step next-state law from state $s$ marginalizes over actions:

P_\pi(s'\mid s) = \sum_{a\in\mathcal{A}} \pi(a\mid s)P(s'\mid s,a).

The expected immediate reward under one action is

r(s,a) = \sum_{s'\in\mathcal{S}}P(s'\mid s,a)R(s,a,s').

The discounted return from time $t$ is

G_t = R_{t+1} +\gamma R_{t+2} +\gamma^2R_{t+3} +\cdots = \sum_{k=0}^{\infty}\gamma^k R_{t+k+1}.

Later, value functions will ask for expectations of this return. This page stops one step earlier: it makes sure the objects inside that expectation are not blurry.

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt

Runnable code 1states = ["Start", "Practice", "Confused", "Mastered"] kernel = { "drill": [ ("Practice", 0.6...python

states = ["Start", "Practice", "Confused", "Mastered"]
kernel = {
    "drill": [
        ("Practice", 0.62, 1.0),
        ("Confused", 0.23, -0.5),
        ("Mastered", 0.15, 3.0),
    ],
    "skim": [
        ("Start", 0.30, 0.1),
        ("Practice", 0.45, 0.5),
        ("Confused", 0.25, -0.2),
    ],
}
policy = {"drill": 0.70, "skim": 0.30}

def action_law(action):
    law = {s: 0.0 for s in states}
    reward = 0.0
    for next_state, prob, r in kernel[action]:
        law[next_state] += prob
        reward += prob * r
    return law, reward

def policy_law(policy):
    law = {s: 0.0 for s in states}
    reward = 0.0
    for action, weight in policy.items():
        action_next, action_reward = action_law(action)
        reward += weight * action_reward
        for state, prob in action_next.items():
            law[state] += weight * prob
    return law, reward

drill_law, drill_reward = action_law("drill")
mix_law, mix_reward = policy_law(policy)

print("row sum:", round(sum(drill_law.values()), 3))
print("P(. | Start, drill):", drill_law)
print("E[R | Start, drill]:", round(drill_reward, 3))
print("P_pi(. | Start):", {k: round(v, 3) for k, v in mix_law.items()})
print("E_pi[R | Start]:", round(mix_reward, 3))

The code mirrors the math. First it reads one action-conditioned row $P(\cdot\mid s,a)$ . Then it builds the policy-conditioned law $P_\pi(\cdot\mid s)$ by averaging rows with policy weights.

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Use the MDP Transition Lab as a state-action prediction check.

Pick a case, then decide which formal object explains the next step:

one action-conditioned transition kernel,
a policy mixture over action kernels,
or an incomplete state description.

Before reveal, the next-state probabilities and reward ledgers stay locked. After reveal, inspect the transition row, the policy mixture, or the hidden variable that the visible state forgot to include.

Live Concept Demo

Explore Markov Decision Process Formalism

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 4/5graduatecode-aligned

Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Markov Decision Process Formalism should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

An MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior.

Prediction open01 / Intuition

Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Markov Decision Process Formalism should make visible.

Visual Inquiry

Make the image answer a mathematical question

An MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior.

4/4 stages readyLive demo connected

Visual cueWhich visible object should carry the first intuition?

Inspection depth2/4

Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Markov Decision Process Formalism easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

book · 2018Reinforcement Learning: An Introduction, Second EditionRichard S. Sutton and Andrew G. Barto

Canonical source for agent-environment interaction, finite MDPs, one-step transition dynamics over next state and reward, policy, and return notation.

Open source

course-notes · 2026Stanford CS234: Reinforcement LearningStanford CS234

Graduate course context for MDP problem formulation, tabular planning, model-free control, and policy-gradient prerequisites.

Open source

course-notes · 2026UC Berkeley CS188: Markov Decision ProcessesUC Berkeley CS188

Course-note source for state/action/reward/transition/discount framing and the Markov property in small decision processes.

Open source

Claim Review

An MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources3 references

sutton-barto-2018-rl, stanford-cs234-2026, berkeley-cs188-mdp

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedIn a finite discounted MDP, current state plus action determines the one-step next-state/reward law, and a stochastic policy mixes those action rows.Claim metadata: source checked

The sources support the finite MDP tuple, the action-conditioned transition kernel, immediate reward framing, discounted return notation, and the Markov assumption that state must carry the information needed for one-step prediction. The policy-mixture equation follows by marginalizing over actions under a stochastic policy.

Sources: Reinforcement Learning: An Introduction, Second Edition, Stanford CS234: Reinforcement Learning, UC Berkeley CS188: Markov Decision ProcessesFinite tabular teaching MDP only; excludes continuous state/action spaces, partial observability beyond the state-completeness warning, Bellman equations, function approximation, off-policy data, exploration, and policy-gradient derivations.A bounded review summary is present; still check caveats and exact reference scope.

Checked Sutton and Barto for finite MDP interaction, one-step dynamics, policy and return notation; Stanford CS234 for graduate RL topic inclusion and MDP formulation; and Berkeley CS188 for the state/action/transition/reward/discount framing plus Markov-property explanation. GPT Pro publication critique remains pending because 127.0.0.1:51672 is unavailable.

Reviewer: codex-local-source-review; reviewed 2026-07-03

source-span-sutton-barto-2018-rl source-span-stanford-cs234-2026 source-span-berkeley-cs188-mdp Equation 1 Equation 2 Runnable code 1 Interactive demo

Source support candidates

book 2018Reinforcement Learning: An Introduction, Second Edition

Canonical source for agent-environment interaction, finite MDPs, one-step transition dynamics over next state and reward, policy, and return notation.

course-notes 2026Stanford CS234: Reinforcement Learning

Graduate course context for MDP problem formulation, tabular planning, model-free control, and policy-gradient prerequisites.

course-notes 2026UC Berkeley CS188: Markov Decision Processes

Course-note source for state/action/reward/transition/discount framing and the Markov property in small decision processes.

Mechanism checks

Equation 1

\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma,\rho_0).

Equation 2

\sum_{s'\in\mathcal{S}}P(s'\mid s,a)=1, \qquad P(s'\mid s,a)\ge 0.

Runnable code 1states = ["Start", "Practice", "Confused", "Mastered"] kernel = { "drill": [ ("Practice", 0.6...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

An MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior.

Readiness0/3 checks ready

Predict

Before touching the demo, predict one visible change that should happen in Markov Decision Process Formalism.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Your answer canvas

Local checks

Claim

A concrete answer is on the canvas.

Mechanism

The answer names why the claim should hold.

Bridge

It touches the page context or a neighboring idea.

Misconception check

Grounded research drawerClose

ConceptMarkov Decision Process FormalismReinforcement Learning

Runnable code comparisonMarkov Decision Process Formalism runnable code 1states = ["Start", "Practice", "Confused", "Mastered"] kernel = { "drill": [ ("Practice", 0.6...Prediction before revealMarkov Decision Process Formalism interactive demoManipulate one control and predict the visible change.

Grounded room questionWhat is the smallest example that makes Markov Decision Process Formalism click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.

Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptReinforcement Learning

Markov Decision Process Formalism

Attached question

What is the smallest example that makes Markov Decision Process Formalism click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action

Local action draft

This draft stays in this browser, attached to the selected learning item.

Draft noteNext action

No local draft saved.

Evidence to inspect

References to inspect: attached references on this page.
Definition, prerequisite, and contrast concept links
The equation or runnable code that makes the concept operational
One demo state that shows the invariant instead of a slogan

What would resolve this

The learner can state the mechanism in their own words
The learner can name the prerequisite that would repair confusion
The learner can predict how the mechanism changes under one perturbation

Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Markov Decision Process Formalism Selected item key: recorded for copy. Context: Reinforcement Learning Page anchor: recorded for copy. Open question: What is the smallest example that makes Markov Decision Process Formalism click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context

concept/concept-notebook/reinforcement-learning/mdp-formalism
concept:reinforcement-learning/mdp-formalism

Learning Map

Before / Now / Try / Next

BeforeProbability Basics

NowIntuition -> Math -> Code -> Demo

TryManipulate one control and predict the visible change.

NextBellman Equations (review)

Intuitionready
Mathready
Codeready
Interactive Demoready

AI Companion

Ask beside the selected object

An MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior.

Your question

GoalComfortStyleStuck on

Context prompt

You are my AI learning companion for Continuous Function. Current context: Reinforcement Learning concept. Learning surface: Markov Decision Process Formalism. What this page says: An MDP is the RL contract for one-step prediction: current state plus action gives a next-state and reward law, while a policy mixes action kernels into behavior. Current section: Intuition, math, code, and interactive demo. Suggested next step: Manipulate one control and predict the visible change.. Learner goal: Understand the idea. Learner comfort level: New to this. Preferred explanation style: Visual first. Task: Explain the central idea in plain language, then restate it with the exact math objects from the page. Answer in a way that helps me learn: ask one clarifying question only if needed, use intuition before notation, and end with one thing I should try on the page.

Domain

Reinforcement Learning

reinforcement-learningmdpstochastic-processespolicytransition-kernel

Prerequisites

Probability Basics

Leads To

Bellman Equations (review)Dynamic Programming and Value Iteration (review)Monte Carlo Reinforcement Learning (review)Policy Gradient (review)RLHF as Reinforcement Learning (review)

RLHF: Reward Modeling + KL-Regularized Policy Optimization Monte Carlo Estimation and Importance Sampling (review)Bayesian Networks (review)

Within this domain