Value Iteration Algorithm

A Capital-Based Decision

The Gambler's Problem looks simple: a gambler wants to reach a capital of $100, and each coin flip either increases or decreases the gambler's capital. The important decision is not merely whether to gamble. Before each flip, the gambler chooses how many dollars to stake. Value iteration studies these choices by estimating the probability of eventually reaching the goal from each capital level.

The Gambler's MDP

The gambler's current capital is the state. At that state, the gambler selects an integer stake as the action. The coin flip creates the random transition: heads increases capital by the stake, while tails decreases capital by the stake. The transition behavior is determined when the probability of heads, represented by p_h, is known.

This is an undiscounted, episodic, finite MDP. It is episodic because each game ends at a terminal outcome. It is undiscounted because the problem does not use discounting. It is finite because the game is bounded by the losing endpoint and the $100 winning endpoint.

What the Value Means

A value estimate for a state is therefore an estimate of the gambler's chance of eventually reaching $100 from that capital level. The estimate depends on the available actions and on the random heads and tails transitions. A value function does not by itself name a stake; it describes how promising each state is. An action-selection step uses those state values to choose a stake intended to maximize the probability of reaching the goal.

Value Iteration Sweeps

Value iteration begins with estimates of state values and repeatedly improves them. During each sweep, it considers the available stakes at each capital level and uses the possible heads and tails outcomes to refine the estimated probability of future success. The successive sweeps produce progressively improved value information.

Once the optimal value function is available, action selection can choose a stake that gives the greatest value. The probability of heads matters because it determines how the possible outcomes of each stake should be evaluated.

Tied Optimal Stakes

The Gambler's Problem does not necessarily have one unique optimal policy. If two or more actions tie when evaluated against the optimal value function, choosing any of those tied actions preserves optimality. A policy is therefore allowed to be one member of a whole family of optimal policies.

A tie is not an error in action selection. It means that the current state has more than one action with the same maximum expected value. Different implementations may select different tied actions while still producing an optimal policy.

Policy Iteration Control

Policy iteration uses a different control structure from value iteration. It begins with arbitrary state values and an arbitrary policy. It then alternates between evaluating the current policy and improving that policy. Evaluation estimates how well the current policy performs. Improvement uses those estimates to check whether another action would produce a greater expected return.

Evaluation and Convergence

During iterative policy evaluation, the algorithm updates V(s) under a fixed policy. It saves the value before an update, computes a newly improved value, and tracks the largest update through ∆. Repeated updates continue until the evaluation process has converged according to its convergence check. The resulting values are then available for policy improvement.

Convergence of value evaluation answers one question: have the values for the current policy been sufficiently updated? Policy stability answers a later question: does policy improvement still want to change any action? These checks belong to different stages and should not be confused.

Improving the Policy

Policy improvement updates π(s) by selecting an action with the greatest expected return according to the current value function. The implementation compares the old action with the newly selected action. If the selected action differs, the policy is not stable and another evaluation-improvement cycle is required. If no action changes, the policy-stability decision allows the algorithm to stop.

• Save the old action for the current state.
• Evaluate candidate stakes using the current value function.
• Use an argmax over expected returns to select a best action.
• Update the policy action for that state.
• Record whether the selected action differs from the old action.
• Stop only when the policy remains stable.

Common Tracing Mistakes

• Treating the stake as the state

  The gambler's capital defines the state; the selected stake defines the action.

  Fix: Record the current capital as the state and the chosen stake as the action.

• Treating the coin flip as the controlled decision

  The coin flip supplies the random transition, while the stake supplies the controlled part of the process.

  Fix: Separate the chosen stake from the random heads-or-tails outcome.

• Stopping after value evaluation converges

  Policy iteration stops only after the policy-stability decision.

  Fix: Run policy improvement and check whether any action changed.

• Assuming one uniquely correct optimal policy

  Multiple actions can tie under the optimal value function.

  Fix: Accept any tied action that preserves the maximum expected value.

• Ignoring the update checkpoints

  The divergence may have occurred during value evaluation, action selection, or termination control.

  Fix: Inspect the saved value, new value, running ∆, old action, updated action, and final stability decision.

Trace the Control Flow

Key Takeaways

1. In the Gambler's Problem, capital is the state and the selected integer stake is the action.
2. Heads and tails create random transitions, and the game ends at the winning or losing endpoint.
3. The value function represents the probability of reaching the $100 goal from each capital level.
4. Value iteration repeatedly refines state-value estimates and uses them to support action selection.
5. Policy iteration alternates between policy evaluation and policy improvement, stopping only when the policy is stable.
6. Tied actions can produce multiple equally optimal policies.