Abstract: Many reinforcement learning algorithms can be seen as versions of approximate policy iteration (API). While standard API often performs poorly, it has been shown that learning can be stabilized by regularizing each policy update by the KL-divergence to the previous policy. Popular practical algorithms such as TRPO, MPO, and VMPO replace regularization by a constraint on KL-divergence of consecutive policies, arguing that this is easier to implement and tune. In this work, we study this implementation choice in more detail. We compare the use of KL divergence as a constraint vs. as a regularizer, and point out several optimization issues with the widely-used constrained approach. We show that the constrained algorithm is not guaranteed to converge even on simple problem instances where the constrained problem can be solved exactly, and in fact incurs linear expected regret. With approximate implementation using softmax policies, we show that regularization can improve the optimization landscape of the original objective. We demonstrate these issues empirically on several bandit and RL environments.
Introduction
Most modern reinforcement learning (RL) algorithms are built upon the framework of Approximate Policy Iteration (API). In this cycle, a policy is evaluated to determine the "advantage" of specific actions, and the policy is subsequently updated to favor those with higher expected returns. However, aggressive updates can lead to policy collapse. To mitigate this, researchers utilize Kullback–Leibler (KL) divergence to ensure that the updated policy remains within a safe proximity of the previous one.
While theoretical foundations suggest using KL-divergence as a regularization term (adding a penalty to the objective), practical implementations like TRPO, PPO, and MPO often treat it as a hard constraint (e.g., limiting the update to a specific $\epsilon$ radius). This paper investigates whether this common design choice is fundamentally sound, particularly when dealing with noisy reward estimates and complex optimization landscapes.
The "Wrong Direction" Trap and Linear Regret
A critical finding of this research is the failure of constrained updates in stochastic environments. In a constrained approach (like TRPO), if a noisy reward estimate erroneously suggests a sub-optimal action, the algorithm will move as far as possible in that "wrong direction" until it hits the constraint boundary. This behavior leads to persistent errors, or linear expected regret, meaning the algorithm never stops making mistakes at a constant rate.
In contrast, regularized updates (such as Mirror Descent) act as a natural filter. By penalizing the KL-divergence rather than capping it, the algorithm effectively maintains a running average of the signal. This allows the true reward signal to emerge over multiple iterations, leading to sublinear regret and eventual convergence to the optimal strategy.
Convexifying the Optimization Landscape
Beyond convergence rates, the choice of objective function deeply impacts the "optimization landscape"—the mathematical terrain the algorithm must navigate. Softmax policies, common in deep RL, often create vast plateaus where gradients vanish, significantly slowing down learning.
The authors demonstrate that using a Surrogate Loss (reversing the KL direction) or specific objectives like VMPO can "convexify" the landscape with respect to the policy's internal activations. This transformation turns a non-convex problem full of plateaus into a more manageable terrain, resulting in faster and more reliable convergence.
Empirical Validation
The theoretical insights were tested across various environments, including a stochastic two-armed bandit, an MNIST contextual bandit, and continuous control tasks from the DeepMind Control Suite (e.g., cartpole, ball_in_cup).
In the MNIST task, regularized and surrogate methods (MDPO, VMPO) converged significantly faster than the constrained approach (CPO). In the DeepMind Control Suite, the constrained CPO algorithm frequently exhibited high variance and oscillations, particularly as it approached the optimal solution. Regularized methods like MDPO provided much smoother and more consistent performance across different random seeds.
Conclusion and Future Work
This work highlights a significant gap between the theoretical stability of KL-regularization and the practical implementation of KL-constraints. While constraints are often perceived as easier to tune, they introduce fundamental optimization issues, including linear regret in noisy settings and slower convergence due to poor landscape properties.
Future research may focus on extending these insights to fully continuous action spaces (as this study utilized discretization) and developing automated methods for tuning regularization strength ($\eta$) to make regularized API as user-friendly as its constrained counterparts.
Summary updated