algorithm {#Methodology}
---------------------

The problem of sufficiently accurate learning can be formulated as the constrained optimization problem . A possible approach to solve said problem is through primal-dual methods. Let us start by defining a vector of multipliers $\lambda\in\mathbb{R}^P_+$ and the Lagrangian of associated to problem $$L(\theta, \lambda) = \mathbb{E}[ \mathcal{L}( {s},  {a}, \phi_\theta)] + \lambda^\top \mathbb{E} [g( {s},  {a}, \phi_\theta)].$$ where to simplify notation we have defined $\mathcal{L}( {s},  {a}, \phi_\theta)  = l(s,a,\phi_\theta)\mathbb{I}_{\mathcal{K}_0}$ and where each component of $g$ is defined as $g_i(s,a,\phi_{\theta}) = h_i(s,a,\phi_{\theta})\mathbb{I}_{\mathcal{K}_i}-\epsilon$ and we have dropped the distribution $D$. The Lagrangian allows us to define the dual problem as $$\begin{aligned}
\label{eq:opt_problem_dual}
    D_\theta^* &= \max_\lambda \min_\theta L(\theta, \lambda)\\
   &  \text{s.t. } \lambda \succeq 0 \nonumber. \end{aligned}$$ The duality gap is defined by the difference $P_\theta^* - D_\theta^*$. When an optimization problem has zero duality gap (we show in Section \[sec\_zero\_duality\_gap\] that this is the case for the problem of learning sufficiently accurate models), then the solutions of both optimization problems in and are the same. The optimal primal variable, $\theta^*$, must necessarily minimize $L$ given the optimal dual variable, $\lambda^*$. Likewise, the optimal dual variable must maximize the Lagrangian given the optimal primal variable. This leads to 