Complexity-Driven Policy Optimization

• URL: http://arxiv.org/abs/2509.20509v1
• Date: Wed, 24 Sep 2025 19:32:03 GMT
• Title: Complexity-Driven Policy Optimization
• Authors: Luca Serfilippi, Giorgio Franceschelli, Antonio Corradi, Mirco Musolesi,
• Abstract summary: We propose replacing the entropy bonus with a more robust complexity bonus.<n>This regularizer encourages policies that balance quantity (high entropy) with structure (high disequilibrium)<n>Such behaviors arise because the regularizer suppresses both extremes, e.g., maximal disorder and complete order, creating pressure for agents to discover structured yet adaptable strategies.
• Score: 5.757876638037014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Policy gradient methods often balance exploitation and exploration via entropy maximization. However, maximizing entropy pushes the policy towards a uniform random distribution, which represents an unstructured and sometimes inefficient exploration strategy. In this work, we propose replacing the entropy bonus with a more robust complexity bonus. In particular, we adopt a measure of complexity, defined as the product of Shannon entropy and disequilibrium, where the latter quantifies the distance from the uniform distribution. This regularizer encourages policies that balance stochasticity (high entropy) with structure (high disequilibrium), guiding agents toward regimes where useful, non-trivial behaviors can emerge. Such behaviors arise because the regularizer suppresses both extremes, e.g., maximal disorder and complete order, creating pressure for agents to discover structured yet adaptable strategies. Starting from Proximal Policy Optimization (PPO), we introduce Complexity-Driven Policy Optimization (CDPO), a new learning algorithm that replaces entropy with complexity. We show empirically across a range of discrete action space tasks that CDPO is more robust to the choice of the complexity coefficient than PPO is with the entropy coefficient, especially in environments requiring greater exploration.

Related papers

• Arbitrary Entropy Policy Optimization: Entropy Is Controllable in Reinforcement Fine-tuning [36.00460460149206]
  We propose Arbitrary Entropy Policy Optimization (AEPO), which eliminates entropy collapse by replacing entropy bonuses with REINFORCE policy gradient on temperature-adjusted distributions.<n>AEPO integrates three key designs: policy gradient as regularization, distribution as regularization, and REINFORCE as regularization, enabling precise entropy control without distorting optimization.
  arXiv  Detail & Related papers  (2025-10-09T12:24:08Z)
• The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models [99.98293908799731]
  This paper aims to overcome a major obstacle in scaling RL for reasoning with LLMs, namely the collapse of policy entropy.<n>In practice, we establish a transformation equation R=-a*eH+b between entropy H and downstream performance R.<n>We propose two simple yet effective techniques, namely Clip-Cov and KL-Cov, which clip and apply KL penalty to tokens with high covariances respectively.
  arXiv  Detail & Related papers  (2025-05-28T17:38:45Z)
• Robust Policy Optimization in Deep Reinforcement Learning [16.999444076456268]
  In continuous action domains, parameterized distribution of action distribution allows easy control of exploration. In particular, we propose an algorithm called Robust Policy Optimization (RPO), which leverages a perturbed distribution. We evaluated our methods on various continuous control tasks from DeepMind Control, OpenAI Gym, Pybullet, and IsaacGym.
  arXiv  Detail & Related papers  (2022-12-14T22:43:56Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  This paper focuses on the most basic setting of competitive multi-agent RL, namely two-player zero-sum Markov games. We propose a single-loop policy optimization method with symmetric updates from both agents, where the policy is updated via the entropy-regularized optimistic multiplicative weights update (OMWU) method. Our convergence results improve upon the best known complexities, and lead to a better understanding of policy optimization in competitive Markov games.
  arXiv  Detail & Related papers  (2022-10-03T16:05:43Z)
• Optimal scheduling of entropy regulariser for continuous-time linear-quadratic reinforcement learning [9.779769486156631]
  Herein agent interacts with the environment by generating noisy controls distributed according to the optimal relaxed policy. This exploration-exploitation trade-off is determined by the strength of entropy regularisation. We prove that the regret, for both learning algorithms, is of the order $mathcalO(sqrtN) $ (up to a logarithmic factor) over $N$ episodes, matching the best known result from the literature.
  arXiv  Detail & Related papers  (2022-08-08T23:36:40Z)
• Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization [28.401280095467015]
  We study the finite-time convergence of independent entropy-regularized natural policy gradient (NPG) methods for potential games. We show that the proposed method converges to the quantal response equilibrium (QRE) at a sublinear rate, which is independent of the size of the action space.
  arXiv  Detail & Related papers  (2022-04-12T01:34:02Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  We propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors.
  arXiv  Detail & Related papers  (2021-05-18T04:35:41Z)
• Maximum Entropy Reinforcement Learning with Mixture Policies [54.291331971813364]
  We construct a tractable approximation of the mixture entropy using MaxEnt algorithms. We show that it is closely related to the sum of marginal entropies. We derive an algorithmic variant of Soft Actor-Critic (SAC) to the mixture policy case and evaluate it on a series of continuous control tasks.
  arXiv  Detail & Related papers  (2021-03-18T11:23:39Z)
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee [61.176159046544946]
  In safe reinforcement learning (SRL) problems, an agent explores the environment to maximize an expected total reward and avoids violation of certain constraints. This is the first-time analysis of SRL algorithms with global optimal policies.
  arXiv  Detail & Related papers  (2020-11-11T16:05:14Z)
• Implicit Distributional Reinforcement Learning [61.166030238490634]
  implicit distributional actor-critic (IDAC) built on two deep generator networks (DGNs) Semi-implicit actor (SIA) powered by a flexible policy distribution. We observe IDAC outperforms state-of-the-art algorithms on representative OpenAI Gym environments.
  arXiv  Detail & Related papers  (2020-07-13T02:52:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.