Constrained Reinforcement Learning Has Zero Duality Gap

By Santiago Paternain, Luiz F. O. Chamon, Miguel Calvo-Fullana, Alejandro Ribeiro. 2019

258 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Cognitive Neuroscience, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Cognitive Neuroscience

In Computational Theory and Mathematics

Citations in the corpus

The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “, 2021), safety (Paternain et al., 2019), or fairness (Cotter et al.”
A Review of Safe Reinforcement Learning: Methods, Theory and Applications (2022, methodology): “To achieve safety policy, a growing number of approaches have been developed over the last few decades, such as primal-dual methods [51, 152, 160, 207, 235, 239, 271, 301], trust region with safety constraints methods [4, 32, 33, 106, 283, 307], formal methods [15, 23, 25, 86, 87, 120, 189, 208, 229”
Responsive Safety in Reinforcement Learning by PID Lagrangian Methods (2020, background): “Although they have been shown to converge to optimal, constraint-satisfying policies (Tessler et al., 2018; Paternain et al., 2019), a shortcoming of gradient Lagrangian methods for safe RL is that intermediate iterates often violate constraints.”
A Review of Safe Reinforcement Learning: Methods, Theories, and Applications (2024, unknown): “…growing number of approaches have been developed over the last few decades, such as policy optimization methods [3], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], formal methods [27], [28], [29], [30], [31], [32], controy theory methods [33], [34],…”
MuZero with Self-competition for Rate Control in VP9 Video Compression (2022, background): “J ck π ≤ βk ∀k (2) There are a number of approaches to solving this constrained RL objective [Altman, 1999, Tessler et al., 2018, Efroni et al., 2020, Achiam et al., 2017, Bohez et al., 2019, Chow et al., 2018, Paternain et al., 2019, Zhang et al., 2020].”