Policy oscillation is overshooting.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Reinforcement Learning

Background:

• Approximate dynamic programming methods in reinforcement learning often fall into greedy value function or value-based policy gradient categories.
• Greedy methods are fast but prone to policy oscillation, a phenomenon hindering performance.

Purpose of the Study:

• To re-examine the policy oscillation phenomenon in reinforcement learning.
• To introduce a novel algorithm that bridges greedy and policy gradient methods.
• To improve performance on the Tetris benchmark problem using approximate dynamic programming.

Main Methods:

• Casting a subset of greedy value function methods as a limiting case of value-based policy gradient methods within non-optimistic policy iteration.
• Developing the constrained natural actor-critic algorithm.
• Empirical analysis on the Tetris benchmark problem.

Main Results:

• The policy oscillation phenomenon is explained through a new theoretical lens.
• The constrained natural actor-critic algorithm is derived, interpolating between existing approaches.
• Performance on the Tetris problem is improved by an order of magnitude compared to prior dynamic programming methods.

Conclusions:

• The theoretical re-framing provides a deeper understanding of policy oscillation in reinforcement learning.
• The new algorithm offers a flexible approach to reinforcement learning.
• The study demonstrates significant advancements in solving complex benchmarks like Tetris with approximate dynamic programming.