Source-linked AI summary
Constrained Reinforcement Learning Has Zero Duality Gap
Santiago Paternain, Luiz F. O. Chamon, Miguel Calvo-Fullana, Alejandro Ribeiro
TL;DR
Conflicting RL objectives are difficult to balance with manually weighted rewards or value functions, and primal-dual methods lack general optimality guarantees because constrained RL is non-convex. This paper proves zero duality gap under stated conditions, extends the result approximately to sufficiently rich policy parametrizations, and connects it to primal-dual convergence. The result supports solving constrained RL through a convex dual problem, while general dual evaluation and policy-distribution approximation remain practical limitations.
Problem
Balancing conflicting RL requirements requires difficult manual reward or coefficient design, while existing primal-dual methods lack general guarantees of convergence to the optimum.
Method
The paper analyzes constrained RL through strong duality, occupation measures, policy parametrization, and primal-dual algorithms.
Results
Constrained RL has zero duality gap under bounded rewards and Slater’s condition; sufficiently rich parametrizations incur suboptimality of order ϵ, and the analyzed primal-dual algorithms converge under mild assumptions.
Takeaways & Limitations
The constrained, dual, and regularized formulations can achieve the same Pareto-optimal front, enabling exact dual-domain treatment in the unparametrized setting.
Takeaways & Limitations
Dual optimization may remain intractable for general policy distributions, and common neural-network parametrizations may not universally approximate distributions.
Abstract
from arXiv · showhide
Autonomous agents must often deal with conflicting requirements, such as completing tasks using the least amount of time/energy, learning multiple tasks, or dealing with multiple opponents. In the context of reinforcement learning~(RL), these problems are addressed by (i)~designing a reward function that simultaneously describes all requirements or (ii)~combining modular value functions that encode them individually. Though effective, these methods have critical downsides. Designing good reward functions that balance different objectives is challenging, especially as the number of objectives grows. Moreover, implicit interference between goals may lead to performance plateaus as they compete for resources, particularly when training on-policy. Similarly, selecting parameters to combine value functions is at least as hard as designing an all-encompassing reward, given that the effect of their values on the overall policy is not straightforward. The later is generally addressed by formulating the conflicting requirements as a constrained RL problem and solved using Primal-Dual methods. These algorithms are in general not guaranteed to converge to the optimal solution since the problem is not convex. This work provides theoretical support to these approaches by establishing that despite its non-convexity, this problem has zero duality gap, i.e., it can be solved exactly in the dual domain, where it becomes convex. Finally, we show this result basically holds if the policy is described by a good parametrization~(e.g., neural networks) and we connect this result with primal-dual algorithms present in the literature and we establish the convergence to the optimal solution.
1 Introduction
Conflicting requirements in reinforcement learning are commonly handled by combining modular value functions or weighting multiple signals, but both approaches require difficult balancing decisions. Constrained RL with primal-dual methods removes manual coefficient selection, although prior methods lacked a guarantee on optimality.
- Multi-objective RL combines modular value functions by assigning each signal a coefficient that controls its emphasis.
- Different penalty coefficients produce different Pareto-optimal solutions, making coefficient selection domain-dependent and computationally intensive.
- Implicit interference between competing goals can produce training plateaus as objectives compete for policy resources.
- Constrained RL uses primal-dual algorithms to choose parameters automatically while constraints enforce the required behavior.
- The paper establishes zero duality gap for constrained RL, extends the result to universal-approximator parametrizations, and proves convergence of primal-dual algorithms under mild assumptions.
2 Constrained Reinforcement Learning
Constrained RL formulates multiple objectives as reward constraints over policies rather than manually balancing them in a single regularized reward. Although the resulting problem is infinite-dimensional and non-convex in the primal domain, its dual is finite-dimensional and convex.
- Constrained RL seeks a policy that satisfies multiple reward specifications, including task completion, spatial containment, and battery constraints.
- The constrained formulation uses thresholds ci for reward specifications instead of manually selecting regularization weights wi.
- Manual weights are difficult to tune because their relationship to the final policy values Vi(π⋆) is not straightforward.
- The primal constrained problem is infinite-dimensional and non-convex, whereas its dual is convex and has dimension equal to the number of constraints.
- Before this work, the dual generally supplied only an upper bound on the primal optimum, with policy quality depending on the bound’s tightness.
3 Constrained Reinforcement Learning Has Zero Duality Gap
The paper proves that constrained RL has zero duality gap under bounded rewards and Slater’s condition, despite non-convexity. This makes the constrained, dual, and regularized formulations equivalent at the optimum, while policy parametrization introduces only an approximation-dependent loss and leaves general dual evaluation potentially intractable.
- Strong duality holds when all reward functions are bounded and Slater’s condition holds, giving P⋆ = D⋆.
- The proof establishes concavity of the perturbation function by representing policies through convex combinations of occupation measures.
- Zero duality gap makes the constrained problem exactly solvable in the dual domain, where the problem is convex and finite-dimensional.
- The constrained and regularized formulations trace the same Pareto front, although the relationship between specifications ci and weights wi is nontrivial.
- Parametrizing policies with sufficiently rich approximators yields suboptimality of order ϵ, which can be made arbitrarily small by increasing representation capacity.
- The theoretical result does not itself provide a tractable procedure because evaluating the dual function can require intractable maximization over general policy distributions.
4 There is (almost) no price to pay by parametrizing the policies
Parametrizing policies makes constrained RL tractable in finite dimensions, while the resulting duality-gap cost is bounded by representation error and is nearly zero for sufficiently expressive parametrizations.
- Policy parametrization: An ϵ-universal parametrization can approximate any policy in P(S) within a stated accuracy ϵ.The parametrization may use neural-network coefficients or linear-combination weights and is defined through approximation of policies in P(S).
- Policy parametrization: Parametrization converts the infinite-dimensional functional optimization problem into a tractable optimization over a finite-dimensional parameter vector.The parameter vector is denoted θ ∈ R^p.
- Duality-gap bound: The parametrized problem generally has a nonzero duality gap, but the gap is bounded linearly in the approximation error ϵ.Thus, stronger representation power reduces the suboptimality introduced by parametrization.
- Duality-gap bound: Increasing the representation ability, such as by enlarging θ, can make the parametrization error arbitrarily small and leave almost no price for solving the dual problem.This conclusion concerns the suboptimality achieved through the parametrized dual problem.
- Dual solution: The dual formulation has dimensionality equal to the number of constraints and remains convex, enabling approximate solution in the dual domain.The supplied passages state that the dual function is convex and that this domain provides computational advantages.
- Scope condition: The parametrization analysis assumes feasibility is preserved; if the relevant parametrized problem is infeasible, the associated upper-bound argument becomes trivial.The text explicitly notes that feasibility of the parametrized problem was not assumed and that preserving feasibility is required for the near-zero price conclusion.
5 Solving Constrained Reinforcement Learning Problems
The proposed solver alternates approximate primal RL updates with projected dual updates. Convexity of the dual function and controlled primal-optimization error support convergence to a neighborhood of the optimal solution.
- Dual optimization: The dual function is convex, so the dual problem can be solved by subgradient descent with projection onto the nonnegative orthant.Projection keeps dual iterates in the required positive orthant.
- Dual optimization: A dual subgradient can be obtained by evaluating the constrained rewards at a primal maximizer of the Lagrangian.Finding that maximizer is difficult because the Lagrangian is non-convex in θ.
- Primal update: Maximizing the Lagrangian with respect to θ is equivalent to learning with a linear combination of the original reward functions.The resulting reward is denoted r_λ(s,a).
- Primal update: Policy-gradient and actor-critic methods can approximate the primal maximization, provided the RL algorithm achieves a local maximum within error δ of the global maximum.This approximation assumption is used to relate the constraint evaluation to a dual subgradient.
- Algorithm: Algorithm 1 alternates approximate Lagrangian maximization with a projected dual update based on the constraint values.The procedure initializes θ and λ at zero and repeats the primal and dual steps.
- Convergence: The constraint evaluation at a local Lagrangian maximizer differs from the dual subgradient by at most the primal maximization error δ.This proposition establishes that the practical dual update approximates a dual descent step.
- Convergence: Under the stated universal-parametrization, bounded-reward, Slater, and approximation assumptions, the update sequence converges after sufficiently many steps to a neighborhood of the optimum.The bound includes contributions from the parametrization, step size, primal error, and target accuracy.
- Convergence: The required number of dual iterations grows linearly with the inverse of the desired accuracy ε.The limiting neighborhood depends on representation ability and the quality of Lagrangian maximization.
6 Numerical Example
The numerical example tests constrained navigation under unsafe-path constraints, showing how exact or approximate primal maximization affects the duality gap and learned policy. Coarser policy parametrizations increase the gap and can prevent successful learning.
- Environment: The gridworld agent navigates from a start to a goal across either a safe or unsafe bridge.The softmax policy uses four actions over a state-action table.
- Constraint: The shortest route crosses the unsafe bridge, whereas the safe bridge requires a longer detour.The formulation constrains unsafe-bridge crossings to 99% avoidance.
- Duality gap: Exact primal maximization makes the normalized duality gap effectively vanish, while one policy-gradient step reduces it more slowly to a neighborhood of zero.The exact primal solution is obtained with Dijkstra’s algorithm for fixed dual variables.
- Learned policy: Both exact and approximate training ultimately learn the safe blue route from start to goal.The result is reported for both primal-maximization procedures.
- Parametrization: As parametrizations become coarser, the duality gap increases; very coarse parametrizations can prevent learning a successful policy.The example attributes this failure to poor covering properties and larger approximation error.
7 Discussion
The discussion interprets zero duality gap as an equivalence between constrained and regularized policy optimization, while emphasizing computational and parametrization limits. Approximate zero-gap behavior requires sufficiently rich policy representations.
- Implications: For general policy distributions, solving the finite-dimensional convex dual problem yields the same result as solving the constrained problem directly.The constrained and regularized formulations trace the same Pareto-optimal front.
- Limitations: The theory does not ensure tractability because evaluating the dual function can remain intractable for arbitrary policies.Sufficiently rich parametrizations provide an approximate zero-duality-gap result.
- Limitations: Many neural-network parametrizations output only distribution means, and sometimes variances, so they are not necessarily universal distribution approximators.The approximate guarantee therefore depends on the representation used.
- Practical consequence: Primal-dual methods avoid exhaustive searches over manually assigned reward weights when solving constrained policy-optimization problems.The discussion also notes possible relevance to algorithmic constraints such as trust-region divergence limits, without guaranteeing the theorem applies there.
A Proofs
The proofs bound the effect of policy approximation on Lagrangian and dual objectives, then use these bounds to relate parametrized and unrestricted dual solutions. The convergence argument combines dual-function bounds with projected dual updates.
- Dual comparison: Because parametrized-policy maximizers form a subset of unrestricted-policy maximizers, dθ(λ) ≤ d(λ) for every λ.The comparison is then evaluated at the unrestricted dual optimum λ⋆.
- Theorem 2: Theorem 2’s upper bound follows because θ is the minimizer of the parametrized dual problem, together with the zero-duality-gap result.The proof explicitly invokes the minimum of (DII) and Theorem 1’s strong duality.
- Approximation bounds: The proof bounds policy-induced differences through occupation measures, density properties, reward bounds, and the approximation error ϵ.Several steps use triangle inequalities and the discount factor to control these differences.
- Approximation bounds: The parametrized Lagrangian gap is bounded by (Br0 + ∥λ∥1 Br) ϵ/(1−γ).This bound depends on reward magnitudes, multiplier norm, approximation error, and discounting.
- Dual comparison: The proof constructs a perturbed dual function dϵ(λ) by subtracting Brϵ∥λ∥1/(1−γ) from the unrestricted dual function.This converts the approximation effect into uniformly relaxed constraint terms.
- Theorem 3: The convergence proof bounds projected dual iterates using inner products with the dual-function difference and controls the iteration count needed to enter an optimal neighborhood.The neighborhood-entry index is defined as the first iterate satisfying αj > −2ε.