Optimal Decision Making in Finite Markov Decision Processes

The Search for a Better Policy

Optimal decision making in a finite Markov decision process can be organized as a repeating search. The method called policy iteration alternates between two jobs: it evaluates the current policy, then uses that evaluation to improve the policy. The evaluation supplies value information, while the improvement stage changes the policy. This cycle continues until no strictly better policy can be produced.

Following Three Policy Iterations

Consider three successive policies named π0, π1, and π2. These labels do not specify particular actions or rewards; they simply make the control process easier to follow. Begin with π0. Evaluation computes the value function associated with π0. Improvement then uses that evaluation to produce π1. If π1 is not optimal, its evaluation is followed by another improvement step, producing π2. The same pattern continues until improvement no longer produces a strictly better policy.

Why Improvement Cannot Stall Early

Policy improvement makes strict progress unless the current policy is already optimal. After a policy has been evaluated, the resulting value information is used to decide whether changing the policy can improve it. If a strictly better policy is available, the improvement stage produces one. If no improvement is possible, the current policy is already optimal. Therefore, stopping is not merely a sign that the method happened to stop changing; it identifies the optimality condition described by the policy-iteration result.

Why Finiteness Guarantees Termination

A finite Markov decision process has only finitely many possible policies. Policy iteration produces strict improvement whenever the current policy is not optimal. Because an endlessly continuing sequence of strict improvements would require moving through infinitely many distinct policies, the finite policy space makes infinite strict progress impossible. The process must therefore reach an optimal policy after finitely many iterations, along with its optimal value function.

Reusing Value Information

Policy evaluation is itself an iterative computation. When a new policy is evaluated, a useful implementation detail is to begin with the value function from the previous policy rather than with an unrelated value function. The previous policy and the newly improved policy are connected by one improvement step, so their value functions may change little. Starting from the previous value function typically makes the next evaluation converge much faster.

From Bandits to Multiple States

A useful way to classify reinforcement learning problems is to ask how many states they contain. A bandit problem has only one state. Finite Markov decision processes provide the general problem formulation for reinforcement learning problems with multiple states. Thus, a bandit problem is not unrelated to a finite Markov decision process; it is the special single-state case, while the finite Markov decision process formulation handles the multiple-state setting.

Value Functions and Bellman Equations

Value functions and Bellman equations are central ideas associated with finite Markov decision processes. In the policy-iteration cycle, the value function is the value information produced during policy evaluation and then used during policy improvement. Bellman equations belong to the same central group of ideas for studying finite Markov decision processes. The source identifies these concepts as central without specifying a particular equation or a particular environment.

Common Classification and Iteration Mistakes

• Treating a bandit problem and a finite Markov decision process as unrelated problem families.

  A bandit problem is the single-state special case, while finite Markov decision processes are the general multiple-state formulation.

  Fix: Classify by the number of states: one state means bandit special case; multiple states means the general finite MDP formulation.

• Assuming policy iteration stops whenever the policy happens not to change during one pass.

  The important result is that improvement produces a strictly better policy unless the current policy is already optimal.

  Fix: Interpret the absence of a strictly better policy as the optimality condition.

• Thinking that policy evaluation and policy improvement are the same operation.

  Evaluation supplies value information; improvement uses that information to change the policy.

  Fix: Keep the stages distinct: evaluate first, then improve.

• Assuming a new policy evaluation must start from an unrelated value function.

  The previous value function can provide a useful starting point and typically makes the next evaluation converge much faster.

  Fix: Reuse the previous value function as the starting information for the new evaluation.

• Explaining termination without mentioning finiteness.

  The stated termination guarantee depends on having finitely many possible policies.

  Fix: Connect strict improvement with the finite policy space: infinite strict progress is impossible.

Key Takeaways

1. Policy iteration alternates between evaluating the current policy and improving it.
2. Policy improvement produces a strictly better policy unless the current policy is already optimal.
3. A finite set of possible policies makes infinite strict progress impossible, so policy iteration reaches an optimal policy after finitely many iterations.
4. Reusing the previous value function typically speeds up the next iterative policy evaluation.
5. Bandit problems have one state; finite Markov decision processes provide the general formulation for multiple-state reinforcement learning problems.
6. Value functions and Bellman equations are central ideas associated with finite Markov decision processes.