Solve the Bellman equations.

Put a value on a future opportunity

At Start, choose a safe exit for three points, or spend one point entering a workshop. There, quit for one point or attempt a repair. A success earns ten and ends the episode. A failure costs one and leaves you in the workshop, able to choose again.

The state tells us everything needed for the supplied transition and reward probabilities. This is a Markov decision process, or MDP: states, available actions, transition probabilities, rewards and a discount factor. The model is known and fixed here. It is not learned from a real workshop.

A policy chooses an action in each nonterminal state. A value is expected discounted future reward, not the immediate reward or a guarantee about one episode. The terminal state has value zero because no further action or reward occurs there.

Calculate one backup before introducing the equation

Begin with both values at zero. Let repair success probability be 0.25 and discount gamma be 0.9. Safe exit is worth 3. Enter is worth −1 + 0.9×0 = −1. At the workshop, quit is worth 1. Repair is worth 0.25×10 + 0.75×(−1 + 0.9×0) = 1.75.

Value iteration takes the larger action value at each state, giving the first table (3, 1.75). The second sweep uses that whole old table: Enter is −1 + 0.9×1.75 = 0.575, still worse than Safe. Repair is 2.5 + 0.75×(−1 + 0.9×1.75) = 2.93125. The second table is (3, 2.93125).

Both new entries use values from before the sweep. Updating one state and immediately using that fresh value elsewhere would be a different, asynchronous procedure. Neither is inherently nonsensical, but an implementation and its explanation must agree about which procedure runs.

Let s be the current state, a an action and s′ its possible next state. P(s′|s,a) is its transition probability; r(s,a,s′) is the immediate reward; Vₖ(s′) is the old next-state value; and gamma discounts future rewards. One value-iteration sweep is:

Read it as: for each action, average immediate reward plus discounted next-state value across possible outcomes, then choose the best action. A terminal transition adds no future value. At gamma zero, only immediate rewards matter.

An equation is a condition; iteration is a procedure

At a solution, another optimal Bellman backup leaves the values unchanged. The Bellman optimality equation expresses that consistency. Value iteration is one procedure for approaching it from an initial table. Starting at zero also gives a finite-horizon interpretation: k sweeps calculate optimal return for k available transitions with zero remaining value at the boundary.

For this discounted finite MDP, the backup contracts differences by at most gamma. The Bellman residual is the largest absolute difference between the current value table and one more backup. Dividing that residual by 1−gamma bounds the maximum error relative to the corresponding fixed point. This is an error bound under the supplied model, not a confidence interval about the real world.

The lab also computes a direct reference. It solves each of the four deterministic policies’ equations and compares their values. It does not take a long iterative run and call that an independent exact answer.

Evaluate a policy without changing it

A fixed policy might choose Enter at Start and Try repair at the workshop. Evaluation follows those actions, instead of maximizing over alternatives during each update.

Let W be that policy’s workshop value, p its repair success probability and gamma the discount. Its equation is W = 10p + (1−p)(−1 + gamma W). Collecting the W terms gives:

At p = 0.25 and gamma = 0.9, W = 1.75/0.325 ≈ 5.384615. Enter at Start then has value −1 + 0.9W ≈ 3.846154. This policy outvalues Safe’s 3 under those assumptions. Evaluation answers what the chosen policy earns; it does not automatically choose a better policy.

If the policy chooses Quit, W is simply 1. If it chooses Safe at Start, Start’s value is 3 regardless of the unused workshop action. We still evaluate both states so a later policy improvement can consider entering.

Improve after evaluating

Policy improvement compares actions using the evaluated policy’s values, then chooses a greedy action at each state. Policy iteration alternates evaluation and improvement until the policy stops changing.

With the default model, Safe/Quit has values (3,1). The first improvement changes the workshop action to Try repair, while Start stays Safe. Evaluating that new policy reveals the workshop opportunity’s larger value. A second improvement then changes Start to Enter.

The lab’s improvement button uses exact policy evaluation before changing actions. Its iterative policy-evaluation mode is separate, so you can compare the iterative values with that direct solution. Improvement from rough, insufficiently evaluated values has different error considerations; it is not what that button claims to implement.

Sampled returns are another kind of evidence

A sampled episode follows one sequence of actual outcomes. Its return is the sum of rewards discounted by time: the entry cost occurs at time zero, the next reward at time one, and so on. The average across episodes estimates the selected policy’s expected return.

If n returns have mean M and a new return is G, the updated sample mean is M + (G−M)/(n+1). The lab computes the equivalent average of the generated returns. It does not use the exact value to fabricate episode rewards. Reusing the seed repeats the same public draws.

This differs from a full expected Bellman sweep over known transition probabilities. It also differs from the sampled bootstrapped Q update in the delayed-reward lesson, which uses an observed reward and a next-state estimate. Monte Carlo returns wait for an episode or cutoff; temporal-difference methods can update from partial experience and bootstrapped estimates.

Keep truncation separate from noise

Sampling here stops at 32 transitions. A stopped nonterminal episode is labelled truncated, not successful or naturally terminal. The app compares its sample mean with the exact 32-step expectation for the same policy, alongside the infinite-horizon value.

Try zero repair success, gamma 0.99, Enter and Try repair. The policy receives −1 forever. Its infinite discounted sum is −1/(1−0.99) = −100. A 32-step return omits the remaining negative tail, so it looks less bad. Collecting more 32-step episodes does not repair that bias; they all measure the same truncated quantity.

At other settings, random success creates sampling variation. Changing the seed can change the sample mean without changing the policy’s exact value. Neither a favorable sample nor a small numerical residual proves that the supplied reward captures the intended real task.

Audit a new decision

For guided practice, compute a sweep, explain the selected action and distinguish immediate reward from return. For implementation practice, preserve simultaneous updates, solve the fixed-policy equations independently and test the never-success loop. For a decision brief, state the reward, discount, transition assumptions and acceptable horizon before comparing policies.

Try a different workshop: success probability 0.5, success reward 6, failure reward −2 and gamma 0.8. Under always trying, W = 0.5×6 + 0.5×(−2 + 0.8W). What is W?

Check the fixed-policy calculation

W = 2 + 0.4W, so 0.6W = 2 and W = 10/3. This evaluates always trying; it does not compare a quit action unless its reward is also specified. This is explained practice, not independent assessment.

Three temporary captures export the settings, iterative history and sampled returns. No new saved project qualification is granted. Human review, broader device profiling and learner pilots remain pending.