Value Iteration Algorithm

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 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.

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 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.

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 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.

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.

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.