Global Optimality for Constrained Exploration via Penalty Regularization

• URL: http://arxiv.org/abs/2604.28144v1
• Date: Thu, 30 Apr 2026 17:31:46 GMT
• Title: Global Optimality for Constrained Exploration via Penalty Regularization
• Abstract summary: Real-world exploration is often exploited by properties constrained by objective constraints.<n>We propose Policy Gradient method that enforces general convex pseudo-penalty regularization.
• Score: 28.060709233558654
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient exploration is a central problem in reinforcement learning and is often formalized as maximizing the entropy of the state-action occupancy measure. While unconstrained maximum-entropy exploration is relatively well understood, real-world exploration is often constrained by safety, resource, or imitation requirements. This constrained setting is particularly challenging because entropy maximization lacks additive structure, rendering Bellman-equation-based methods inapplicable. Moreover, scalable approaches require policy parameterization, inducing non-convexity in both the objective and the constraints. To our knowledge, the only prior model-free policy-gradient approach for this setting under general policy parameterization is due to Ying et al. (2025). Unfortunately, their guarantees are limited to weak regret and ergodic averages, which do not imply that the final output is a single deployable policy that is near-optimal and nearly feasible. In this work we take a different approach to this problem, and propose Policy Gradient Penalty (PGP) method, a single-loop policy-space method that enforces general convex occupancy-measure constraints via quadratic-penalty regularization. PGP constructs pseudo-rewards that yield gradient estimates of the penalized objective, subsequently exploiting the classical Policy Gradient Theorem. We further establish the regularity of the penalized objective, providing the smoothness properties needed to justify the convergence of PGP. Leveraging hidden convexity and strong duality, we then establish global last-iterate convergence guarantees, attaining an $ε$-optimal constrained entropy value with $ε$ bounded constraint violation despite policy-induced non-convexity. We validate PGP through ablations on a grid-world benchmark and further demonstrate scalability on two challenging continuous-control tasks.

Related papers

• Boundary-Seeking Policy Gradient for Safe Reinforcement Learning [10.527332705691668]
  Boundary-Seeking Policy Gradient ( BSPG)<n>First-order method whose update combines a tangential component that improves reward while preserving cost to first order with a signed, residual-driven normal component that regulates the policy toward the active boundary from either side.<n>On a standard Safety-Gymnasium navigation task, BSPG attains higher reward while tracking the boundary more tightly than the compared baselines.
  arXiv  Detail & Related papers  (2026-08-10T20:20:01Z)
• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality [53.525547349715595]
  We propose a novel primal-only algorithm called Rectified Robust Policy Optimization (RRPO)<n>RRPO operates directly on the primal problem without relying on dual formulations.<n>We show convergence to an approximately optimal feasible policy with complexity matching the best-known lower bound.
  arXiv  Detail & Related papers  (2025-08-24T16:59:38Z)
• Proactive Constrained Policy Optimization with Preemptive Penalty [11.93135424276656]
  We propose a novel preemptive penalty mechanism for constrained policy optimization.<n>This mechanism integrates barrier items into the objective function as the policy nears the boundary, imposing a cost.<n>We also introduce a constraint-aware intrinsic reward to guide boundary-aware exploration, which is activated only when the policy approaches the constraint boundary.
  arXiv  Detail & Related papers  (2025-08-03T18:35:55Z)
• Ordering-based Conditions for Global Convergence of Policy Gradient Methods [73.6366483406033]
  We prove that, for finite-arm bandits with linear function approximation, the global convergence of policy gradient (PG) methods depends on inter-related properties between the policy update and the representation.<n>Overall, these observations call into question approximation error as an appropriate quantity for characterizing the global convergence of PG methods under linear function approximation.
  arXiv  Detail & Related papers  (2025-04-02T21:06:28Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  We introduce an exploration-agnostic algorithm, called C-PG, which exhibits global last-ite convergence guarantees under (weak) gradient domination assumptions. We numerically validate our algorithms on constrained control problems, and compare them with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-07-15T14:54:57Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  We study the problem of computing an optimal policy of an infinite-horizon discounted Markov decision process (constrained MDP) We develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs.
  arXiv  Detail & Related papers  (2023-06-20T17:27:31Z)
• Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs [23.596546979904613]
  We employ the natural policy gradient method to solve the discounted optimal optimal rates for Conslinear Decision (MDPs)<n>We also provide finitesample guarantees for two sample-based NPG-PD algorithms.
  arXiv  Detail & Related papers  (2022-06-06T04:28:04Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  We propose Penalized Proximal Policy Optimization (P3O), which solves the cumbersome constrained policy iteration via a single minimization of an equivalent unconstrained problem. P3O utilizes a simple-yet-effective penalty function to eliminate cost constraints and removes the trust-region constraint by the clipped surrogate objective. We show that P3O outperforms state-of-the-art algorithms with respect to both reward improvement and constraint satisfaction on a set of constrained locomotive tasks.
  arXiv  Detail & Related papers  (2022-05-24T06:15:51Z)
• Policy-based Primal-Dual Methods for Concave CMDP with Variance Reduction [18.95829896746939]
  We study Concave CMDPs where both the objective and constraints are defined as concave functions of the state-action occupancy measure. We propose the Variance-Reduced Primal-Dual Policy Gradient, which updates the primal variable via policy gradient ascent and the dual variable via projected sub-gradient descent.
  arXiv  Detail & Related papers  (2022-05-22T02:50:16Z)
• Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization [20.651913793555163]
  We revisit the classical entropy regularized policy gradient methods with the soft-max policy parametrization. We establish a global optimality convergence result and a sample complexity of $widetildemathcalO(frac1epsilon2)$ for the proposed algorithm.
  arXiv  Detail & Related papers  (2021-10-19T17:21:09Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  We make the first attempt to study risk-sensitive deep reinforcement learning under the average reward setting with the variance risk criteria. We propose an actor-critic algorithm that iteratively and efficiently updates the policy, the Lagrange multiplier, and the Fenchel dual variable.
  arXiv  Detail & Related papers  (2020-12-28T05:02:26Z)

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.