Token LabSearch

← RL knowledge base
RL / 2 OF 8

Exploration, credit assignment & reward design

Make useful behavior discoverable and measurable.

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

Exploration determines which actions generate training evidence. Credit assignment determines which earlier choices receive credit for a later result. Sparse terminal rewards can be trustworthy but difficult to learn from. Dense intermediate rewards provide more signal but may introduce shortcuts. Separate the intended task utility from the implemented reward function and audit the gap.

Text / 原始公式
Task utility ≠ proxy reward
Potential shaping: r′=r+γΦ(s′)−Φ(s)
Policy-invariance claims require the relevant assumptions.

Mechanism map & worked derivation

Define task utility → Choose exploration strategy → Collect delayed outcomes → Audit proxy and credit
Original schematic; read the steps from top to bottom. SVG ↓
Symbols and assumptions
SymbolMeaning
sₜObserved task context, not necessarily full environment state
aₜSelected tool action with explicit arguments
oₜ₊₁Returned observation, including errors
  1. Use a two-arm bandit with unknown rewards. Greedy selection after a lucky first observation can stop collecting evidence about the other arm.
  2. For ε-greedy with two arms and ε, a non-greedy arm is selected with probability 0.05 if exploration samples uniformly over both arms. State this convention.
  3. For delayed rewards, construct two trajectories with the same final reward but different wasted actions. Decide whether task utility actually penalizes the extra actions before adding a cost term.
Experiment checkpoint

Separate mock control-flow tests from real-policy evaluation. A readable trace is not proof of external task completion.

Original exercise & analysis

For a coding agent, compare “number of tests passed” with “number of tool calls completed”. Construct an agent that maximizes each proxy without fixing the bug. Add hidden tests and a separate test-integrity check; keep the original task evaluation unchanged.

A reward metric improving faster than held-out task success is a warning sign, not proof of stronger intelligence.

Why not reward every intermediate step?

The agent may learn to produce more steps rather than finish the task. Dense rewards need a causal relationship to the desired outcome and independent validation.

Study evidence & continue

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

Assumptions, implementation & acceptance

Policy invariance requires bounded potential, the same γ, and zero terminal potential (or equivalent absorbing-tail handling). Telescoping gives γ_T); an action-dependent final term can change optimal policy.

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

Original return is 2.8, shaped return is 2.8−3. A nonzero terminal potential breaks this equality.

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 exploration-credit.mjs. No third-party runtime dependencies.

const solve=()=>{
const gamma=.9, rewards=[1,2], phi=[3,4,0];
const shaped=rewards.map((r,t)=>r+gamma*phi[t+1]-phi[t]);
return shaped.reduce((g,r,t)=>g+gamma**t*r,0);
};
const actual=solve();
const expected=-0.2;
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
-0.2

Test and transfer

Original return is 2.8, shaped return is 2.8−3. A nonzero terminal potential breaks this equality.

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