Token LabSearch

← RL knowledge base
RL / 1 OF 8

MDPs, returns & Bellman equations

Define the task before choosing an algorithm.

Study guide & lesson outlineLEARNING CONTRACT

Understand → implement → investigate

Goal: explain the mechanism in this lesson, reproduce one example and test a failure case. Reading alone does not mark mastery.

Prerequisite route →Related implementation practice →
  • Understand: state assumptions, shapes/units and a counterexample.
  • Implement: reproduce a numerical example and inspect boundaries.
  • Investigate: compare one alternative under a matched budget.

Understand the mechanism

Specify states, actions, transition probabilities, rewards, terminal conditions and what the agent can observe. A language-model prefix can serve as a state representation; a token or tool invocation can be an action, depending on the abstraction. The Markov property is an assumption about whether the state contains enough information, not a property granted by naming a variable “state”.

Text / 原始公式
Gₜ=Σₖ≥₀ γᵏrₜ₊ₖ₊₁
Vπ(s)=Eπ[r+γVπ(s′)|s]
Q*(s,a)=E[r+γ maxₐ′Q*(s′,a′)]

Mechanism map & worked derivation

Define state and actions → Specify reward and transitions → Backup future value → Evaluate or improve policy
Original schematic; read the steps from top to bottom. SVG ↓
Symbols and assumptions
SymbolMeaning
γDiscount factor
Vπ(s)Expected return from a state under policy π
terminalA state with no future reward in this episodic example
  1. In a deterministic chain s₀→s₁→terminal with rewards 1 then 2, and γ×2. At γ,
  2. Bellman evaluation substitutes the next state value recursively. Bellman optimality adds a maximization over next actions; do not mix policy evaluation with control.
  3. For a stochastic transition, average over its probabilities. If half the time the next reward is 2 and half 0, the expected next reward is 1, not the maximum 2.
Experiment checkpoint

Write terminal and truncation handling explicitly. A one-step hand calculation should agree with the code.

LOCAL / SYNTHETIC / INTERACTIVE

Change one variable. Explain what moves.

Original teaching calculation, not a reproduction of the paper’s benchmark. Bars are relative within this panel; numeric values and units are authoritative.

Original exercise & analysis

Compare taking reward 2 now against waiting one step for reward 5. At γ they tie; at γ waiting gives 4.5. Explain how terminal states remove the bootstrap term.

Discounting changes the objective. Do not silently change γ between methods or bootstrap past a true terminal state. Time-limit truncation can require different handling.

Does adding a long text history guarantee the Markov property?

No. Relevant hidden environment state may remain unobserved; the resulting problem may be partially observable.

Study evidence & continue

Sutton & Barto, Chapters 3–4 ↗
Interview questions & answers →
MATHEMATICAL REVIEW · 2026-10-26

Assumptions, implementation & acceptance

Condition the Bellman expectation on s,a. Continuing discounted tasks use 0≤γ<1; terminal value is zero. Rewards use r_(t+1), received after action a_t.

Formula conditions, units and worked arithmetic reviewed. The implementation isolates one numerical mechanism; it does not train a policy or control real hardware.

Before running: predict a boundary case

Delayed option is 4.5; γ makes it zero.

Hint: isolate the assumption

Keep the baseline input fixed, change one parameter or boundary, and compare both the numerical result and the claimed units. A passing example verifies this fixture only.

Minimal executable example

Save the example and linked modules in one folder. Use Node.js 22 or newer, then run node mdp-bellman.mjs. No third-party runtime dependencies.

const solve=()=>{
const gamma=0.9; return [2, gamma*5];
};
const actual=solve();
const expected=[2,4.5];
if(JSON.stringify(actual)===JSON.stringify(expected)){console.log('PASS',actual)}else{
const a=[actual].flat(), b=[expected].flat();
if(a.length!==b.length||a.some((v,i)=>!Number.isFinite(v)||Math.abs(v-b[i])>1e-10))throw Error('Numerical mismatch');
console.log('PASS within 1e-10',actual);
}
Download this example
Reference output — reveal after predicting
[
  2,
  4.5
]

Test and transfer

Delayed option is 4.5; γ makes it zero.

Record input, code version, expected result and observed result in the notebook below. Then construct a counterexample that violates the assumption above and explain why the original conclusion no longer follows.

Download complete kit (.tar.gz) · Complete reference kit and regression checks

Predict, test and keep evidence

Before revealing an answer, predict one result. After the exercise, record the discrepancy and a transfer test. Saved locally across language editions.

Open notebook / export / clear →

The mathematical review scope is recorded per lesson. It does not establish empirical paper reproduction; report suspected errors in your notes. Review scope