Optimization Methods for Reinforcement Learning
Global and local optima differ according to how widely the candidate weight vector is compared.
The Optimization Target
In reinforcement learning, an optimization method adjusts a weight vector to improve a prediction objective. For MSVE optimization, the goal is not simply to find weights that perform better than the weights used previously. The stronger goal is to identify weights whose MSVE is no greater than the MSVE produced by any other possible weight vector. That strongest target is a global optimum.
Reading the MSVE Landscape
A useful teaching model represents every possible weight vector as a location in a landscape. The height at a location represents that weight vector's MSVE. Moving to a lower location represents finding weights with a smaller MSVE. This landscape is only a model for reasoning; it does not mean that an optimizer literally observes a physical surface. The model helps separate three outcomes: reaching the lowest point anywhere, settling at a low point near the current location, or failing to settle at all.
Global and Local Optima
A global optimum is a weight vector whose MSVE is no greater than the MSVE of every other possible weight vector. The comparison covers the entire set of possible choices, not just the candidates near the current weights.
A local optimum is a weight vector whose MSVE is at least as good as the alternatives sufficiently close to it. The comparison is restricted to a neighborhood, so a local optimum can be stable nearby without being best across the full optimization problem.
Comparing the Scope of the Search
Suppose a candidate weight vector has a lower MSVE than every weight vector in its nearby neighborhood, but another weight vector farther away has an even lower MSVE.
Check nearby alternatives: The candidate is at least as good as the alternatives sufficiently close to it, so it satisfies the local comparison.
Check every possible vector: The farther-away vector has a lower MSVE, so the candidate is not at least as good as every possible weight vector.
Classify the candidate: The candidate is a local optimum but not a global optimum.
Local optimality depends on a neighborhood; global optimality depends on the entire set of possible weight vectors.
Weight Updates and Outcomes
An optimization method changes the current weight vector. That change is only an adjustment; it is not proof that an optimum has been reached. To establish global optimality, the candidate would need to satisfy the comparison against every possible weight vector. To establish local optimality, it would need to be at least as good as the alternatives in the relevant neighborhood. Simply observing that the weights are changing does not establish either result.
Why Convergence Is Hard
Complex function approximators make the optimization problem difficult to search. In many reinforcement-learning cases of interest, convergence to an optimum cannot be guaranteed. Even convergence to within a bounded distance of an optimum may not be assured. Because complex approximators rarely reach a global optimum, local convergence can be the more realistic target, but it remains important not to treat that target as guaranteed.
When Optimization Diverges
Failure is not limited to settling at a less-than-global solution. An optimization method may fail to converge to an optimum at all. Some methods can diverge rather than approach an optimum, with their MSVE approaching infinity in the limit. This outcome is qualitatively different from reaching a local optimum: the process does not settle at a stable nearby point.
Three Possible Results
Classify three hypothetical optimization traces: one reaches the best result across all possible vectors, one settles at a nearby low point, and one continues away so that MSVE approaches infinity.
Trace A: The candidate is no worse than every possible weight vector. This is a global optimum.
Trace B: The candidate is no worse than alternatives sufficiently close to it, but it is not established as best across all vectors. This is a local optimum.
Trace C: The process does not settle at an optimum, and MSVE approaches infinity in the limit. This is divergence.
Global optimum, local optimum, and divergence are distinct outcomes that should not be treated as degrees of the same success.
Mistakes in Evaluating Optimization
Treating every weight update as evidence of convergence.
An update only shows that the current weight vector was adjusted. It does not establish global or local optimality.
Fix:
Ask what comparison has been established: every possible vector for a global claim, or nearby alternatives for a local claim.Calling a candidate global because nearby alternatives have worse MSVE.
Global optimality requires comparison with every possible weight vector, not only a neighborhood.
Fix:
Use the term local optimum unless the full comparison required for global optimality is satisfied.Assuming temporary MSVE improvement guarantees eventual convergence.
MSVE can improve for a while even though convergence is not guaranteed.
Fix:
Keep improvement, convergence, and optimality as separate claims.Treating divergence as merely a poor local optimum.
Divergence means the method fails to settle at an optimum; some methods can have MSVE approaching infinity.
Fix:
Report non-convergence or divergence rather than labeling the outcome a local optimum.
Practice: Classify the Outcome
A method changes its weights and produces a lower MSVE than before. No comparison with all possible weight vectors has been made, and the later behavior of the method is unknown. What can you conclude now, and what can you not conclude?
Hints
- Separate an observed update from a claim about convergence.
- Ask whether the evidence covers every possible weight vector, only a neighborhood, or neither.
What do you think happens?
Can the observed lower MSVE alone establish that the method has reached a global or local optimum?
Reveal answer
Answer: No. It establishes an observed improvement, but it does not establish convergence or optimality.
Global optimality requires comparison with every possible weight vector. Local optimality requires comparison with alternatives sufficiently close to the candidate. A single improvement does not provide either comparison.
Key Takeaways
- A global optimum has MSVE no greater than that of every possible weight vector.
- A local optimum is at least as good as alternatives sufficiently close to it.
- Adjusting weights or temporarily lowering MSVE does not prove that an optimum has been reached.
- Complex function approximators rarely reach a global optimum, and convergence may not be guaranteed even within a bounded distance of one.
- An optimization method may diverge, with MSVE approaching infinity, rather than settle at a global or local optimum.
Key Takeaways
- Global and local optimality differ by the scope of the comparison over weight vectors.
- Global optimality considers every possible weight vector; local optimality considers only a neighborhood.
- A weight update or temporary MSVE improvement is not proof of convergence.
- Complex function approximators make global convergence difficult to guarantee.
- Some optimization methods diverge instead of approaching an optimum.