Actor-critic is implicitly biased towards high entropy optimal policies

Abstract

We show that the simplest actor-critic method -- a linear softmax policy updated with TD through interaction with a linear MDP, but featuring no explicit regularization or exploration -- does not merely find an optimal policy, but moreover prefers high entropy optimal policies. To demonstrate the strength of this bias, the algorithm not only has no regularization, no projections, and no exploration like $\epsilon$-greedy, but is moreover trained on a single trajectory with no resets. The key consequence of the high entropy bias is that uniform mixing assumptions on the MDP, which exist in some form in all prior work, can be dropped: the implicit regularization of the high entropy bias is enough to ensure that all chains mix and an optimal policy is reached with high probability. As auxiliary contributions, this work decouples concerns between the actor and critic by writing the actor update as an explicit mirror descent, provides tools to uniformly bound mixing times within KL balls of policy space, and provides a projection-free TD analysis with its own implicit bias which can be run from an unmixed starting distribution.

arXiv commentv2 primarily improved the proofs, with minimal changes to the body

References in corpus (12)

• Maximum a Posteriori Policy Optimisation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• A Theory of Regularized Markov Decision Processes
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Risk and parameter convergence of logistic regression
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima