Constrained Reinforcement Learning Has Zero Duality Gap

Introduction

Autonomous agents must often deal with conflicting requirements, such as completing a task in the least amount of time/energy, learning multiple tasks or contexts, dealing with multiple opponents or with several specifications that are designed to guide the agent in the learning process. In the context of reinforcement learning , these problems are generally addressed by combining modular value functions that encode them individually, by multiplying each signal by its own coefficient, which controls the emphasis placed on it . Although effective, the multi-objective problem has several downsides. First, for each set of penalty coefficients, there exists a different, optimal solution, also known as Pareto optimality . In practice, the exact coefficient is selected through a time consuming and a computationally intensive process of hyper-parameter tuning that often times are domain dependent, as showed in . Moreover, implicit interference between the goals may lead to training plateaus as they compete for resources in the policy .

An alternative, is to embed all conflicting requirements in a constrained RL problem and to use a primal-dual algorithm as in that chooses the parameters automatically. The main advantage of this approach is that constraints ensure satisfying behavior without the need for manually selecting the penalty coefficients. In these algorithms the policy update is on a faster time-scale than the multiplier update. Thus, effectively, these approaches work as if the dual problem of the constrained reinforcement learning problem was being solved. Thus, guaranteeing to obtain the feasible solution with the smallest suboptimality. Yet, there is no guarantee on how small the suboptimality is. In this work we provide an answer to the previous question. In particular we establish that:

Despite its non-convexity, constrained reinforcement learning for policies belonging to a general distribution class has zero duality gap, i.e., it can be solved exactly in the dual domain, where the problem is actually convex

Since working with generic distributions as policies is in general intractable, we extend this result to parametrized policies, by showing that the suboptimality bound also holds when the parametrization is a universal approximator, e.g., a neural network ).

We leverage these theoretical results to establish that the family of primal-dual algorithms for constrained reinforcement learning, e.g. , in fact converge to the optimal solution under mild assumptions.

Constrained Markov Decision Processes (CMDPs) are an active field of research. CMDP applications cover a vast number of topics, such as: electric grids , networking , robotics and finance . The most common approaches to solve this problems can be divided under the following categories. Manual selection of Lagrange multipliers: constrained Reinforcement Learning problems can be solved through by maximizing an unconstrained Lagrangian, for a specific multiplier . The combination of different rewards with manually selected Lagrange multipliers has been applied for instance to learning complex movements for humanoids or to limit the variance of the constraint that needs to be satisfied . Integrating prior knowledge about the system transitions is exploited in order to project the action chosen by the policy to a set that ensures the satisfaction of the constraints . Primal-dual algorithms , allow us to choose dynamically the multipliers by find the best policy for the current set of parameters and then taking steps along the gradient of the Lagrangian with respect to the multipliers. These allow to consider general constraints and the algorithm is reward agnostic and it does not require the use of prior knowledge.

Constrained Reinforcement Learning

Constrained Reinforcement Learning Has Zero Duality Gap

The dual function is then the point-wise maximum of (1) with respect to the policy $\pi$, i.e.,

Notice that $P(0)=P^{\star}$, the optimal value of (PI). We formally state next the conditions under which Problem (PI) has zero duality gap.

Suppose that $r_{i}$ is bounded for all $i=0,\ldots,m$ and that Slater’s condition holds for (PI). Then, strong duality holds for (PI), i.e., $P^{\star}=D^{\star}$.

This proof relies on a well-known result from perturbation theory connecting strong duality to the convexity of the perturbation function defined in(${\text{PI}}^{\prime}$). We formalize this result next.

If (i) Slater’s condition holds for (PI) and (ii) its perturbation function $P(\xi)$ is concave, then strong duality holds for (PI).

If for either perturbation $\xi^{1}$ or $\xi^{2}$ the problem becomes infeasible then $P(\xi^{1})=-\infty$ or $P(\xi^{2})=-\infty$ and thus (3) holds trivially. For perturbations that keep the problem feasible, suppose $P(\xi^{1})$ and $P(\xi^{2})$ are achieved by the policies $\pi_{1}\in\mathcal{P}(\mathcal{S})$ and $\pi_{2}\in\mathcal{P}(\mathcal{S})$ respectively. Then, $P(\xi^{1})=V_{0}(\pi_{1})$ with $V_{i}(\pi_{1})-c_{i}\geq\xi^{1}_{i}$ and $P(\xi^{2})=V_{0}(\pi_{2})$ with $V_{i}(\pi_{2})-c_{i}\geq\xi^{2}_{i}$ for $i=1,\ldots,m$. To establish (3) it suffices to show that for every $\mu\in(0,1)$ there exists a policy $\pi_{\mu}$ such that $V_{i}(\pi_{\mu})-c_{i}\geq\mu\xi^{1}_{i}+(1-\mu)\xi^{2}_{i}$ and $V_{0}(\pi_{\mu})=\mu V_{0}(\pi_{1})+(1-\mu)V_{0}(\pi_{2})$. Notice that any policy $\pi_{\mu}$ satisfying the previous conditions is a feasible policy for the slack $c_{i}+\mu\xi^{1}_{i}+(1-\mu)\xi^{2}_{i}$. Hence, by definition of the perturbed function (${\text{PI}}^{\prime}$), it follows that

If such policy exists, the previous equation implies (3). Thus, to complete the proof of the result we need to establish its existence. To do so we start by formulating a linear program equivalent to (${\text{PI}}^{\prime}$). Notice that for any $i=0,\ldots,m$ we can write

Since the reward functions are bounded the Dominated Convergence Theorem holds. This allows us to exchange the order of the sum and the integral. Moreover, using conditional probabilities and the Markov property of the transition of the system we can write $V_{i}(\pi)$ as

Notice that for every $u>t$ the integrals with respect to $a_{u}$ and $s_{u}$ yield one, since they are integrating density functions. Thus, the previous expression reduces to

Notice that the probability density of being at state $s$ and choosing action $a$ under the policy $\pi$ at time $t$ can be written as

Thus, using again the Dominated Convergence Theorem, one can write compactly (7) as

By defining the occupation measure $\rho(s,a)=\left(1-\gamma\right)\sum_{t=0}^{\infty}\gamma^{t}p_{\pi}^{t}(s,a)$ it follows that $(1-\gamma)V_{i}(\pi)=\int_{\mathcal{S}\times\mathcal{A}}r_{i}(s,a)\rho(s,a)\,dsda$. Denote by $\mathcal{M}(\mathcal{S},\mathcal{A})$ the measures over $\mathcal{S}\times\mathcal{A}$ and define the set $\mathcal{R}$ as the set of all occupation measures induced by the policies $\pi\in\mathcal{P}(\mathcal{S})$ as

where It follows from [24, Theorem 3.1] that the set of occupation measures $\mathcal{R}$ is convex and compact. Hence, we can write the following linear program equivalent to (${\text{PI}}^{\prime}$)

Let $\rho_{1},\rho_{2}\in\mathcal{R}$ be the occupation measures associated to $\pi_{1}$ and $\pi_{2}$. Since, $\mathcal{R}$ is convex, there exists a policy $\pi_{\mu}\in\mathcal{P}(\mathcal{S})$ such that its corresponding occupation measure is $\rho_{\mu}=\mu\rho_{1}+(1-\mu)\rho_{2}\in\mathcal{R}$. Notice that $\rho_{\mu}$ satisfies the constraints with slack $c_{i}+\mu\xi^{1}_{i}+(1-\mu)\xi^{2}_{i}$ for $i=1,\ldots,m$ since the integral is linear and $\rho_{1}$ and $\rho_{2}$ satisfy the constraints with slacks $c_{i}+\xi^{1}_{i}$ and $c_{i}+\xi^{2}_{i}$ respectively. Thus, it follows that

where we have used again the linearity of the integral. Since $\pi_{i}$ are such that $V_{0}(\pi_{1})=P(\xi^{1})$ and $V_{0}(\pi_{2})=P(\xi^{2})$, inequality (3) follows. This completes the proof that the perturbation function is concave. ∎

The theoretical importance of the previous result notwithstanding, it does not yield a procedure to solve (PI) since evaluating the dual function involves a maximization problem that is intractable for general classes of distributions. In the next section, we study the effect of using a finite parametrization for the policies and show that the price to pay in terms of duality gap depends on how “good” the parametrization is. If we consider, for instance, a neural network—which are universal function approximators —the loss in optimality can be made arbitrarily small.

There is (almost) no price to pay by parametrizing the policies

The previous definition includes all parametrizations that induce distributions that are close to distributions in $\mathcal{P}(\mathcal{S})$ in total variational norm. Notice that this is a milder requirement than approximation in uniform norm which is a property that has been established to be satisfied by radial basis functions networks , reproducing kernel Hilbert spaces and deep neural networks . Notice that the objective function and the constraints in Problem (PI) involve an infinite horizon and thus, the policy is applied an infinite number of times. Hence, the error introduced by the parametrization could a priori accumulate and induce distributions over trajectories that differ considerably from the distributions induced by policies in $\mathcal{P}(\mathcal{S})$. We claim in the following lemma that this is not the case.

Let $\rho$ and $\rho_{\theta}$ be occupation measures induced by the policies $\pi\in\mathcal{P}(\mathcal{S})$ and $\pi_{\theta}$ respectively, where $\pi_{\theta}$ is an $\epsilon$- parametrization of $\pi$. Then, it follows that

The previous result, although derived as a technical result required to bound the duality gap for parametric problems, has a natural interpretation. The larger $\gamma$ —the more the operation is concerned about rewards far in the future —the larger the error in the approximation of the occupation measure. Having defined the concept of universal approximator, we shift focus to writing the parametric version of the constrained reinforcement learning problem. This is, to find the parameters that solve (PI), where now the policies are restricted to the functions induced by the chosen parametrization

Likewise we define the dual problem as finding the tightest upper bound for (PII)

As previously stated, the reason for introducing the parametrization is to turn the original functional optimization problem into a tractable problem in which the optimization variable is a finite dimensional vector of parameters. Yet, there is a cost for introducing the aforementioned parametrization: the duality gap is no longer null. The latter means that the solution obtained through the dual problem is sub-optimal. We claim however that this gap is bounded by a function that is linear with the approximation error $\epsilon$, and thus if the parametrization has a good representation power the price to pay is almost zero. This is the subject of the following theorem.

Suppose that $r_{i}$ is bounded for all $i=0,\ldots,m$ by constants $B_{r_{i}}>0$ and define $B_{r}=\max_{i=1\ldots m}B_{r_{i}}$. Let $\lambda_{\epsilon}^{\star}$ be the solution to the dual problem associated to (${\text{PI}}^{\prime}$) for perturbation $\xi_{i}=B_{r}\epsilon/(1-\gamma)$ for all $i=1,\ldots,m$. Then, under the hypothesis of Theorem 1 it follows that

where $P^{\star}$ is the optimal value of (PI), and $D_{\theta}^{\star}$ the value of the parametrized dual problem (DII).

The implication of the previous result is that there is almost no price to pay by introducing a parametrization. By solving the dual problem (DII) the sub-optimality achieved is of order $\epsilon$, i.e., the error on the representation of the policies. Notice that this error could be made arbitrarily small by increasing the representation ability of the parametrization, by for instance increasing the dimension of the vector of parameters $\theta$. The latter means that if we can compute the dual function it is possible to solve (PI) approximately. Moreover, working on the dual domain provides two computational advantages; on one hand, the dimension of the problem is the number of constraints in (PI). In addition, the dual function is always convex, hence gradient descent on the dual domain solves the problem of interest. In the next section we propose an algorithm to solve (PI) approximately based on the previous discussion.

Before doing so notice that we have not assumed anything about the feasibility of problem (PII). Notice that if the problem is infeasible then we have that $D_{\theta}^{\star}=-\infty$ and thus the upper bound on (15) holds trivially. On the other hand if the problem is infeasible it also means that there is no policy $\pi\in\mathcal{P}(\mathcal{S})$ that satisfies the constraints of (PI) with slack $B_{r}\epsilon/(1-\gamma)$ since $\theta$ is an $\epsilon$-universal approximation of $\mathcal{P}(\mathcal{S})$. Hence the perturbed problem is infeasible which yields a dual multiplier $\lambda_{\epsilon}^{\star}$ that has infinite norm. Thus the right hand side of (15) holds as well. In that sense, as long as the parameterization introduced keeps the problem feasible the price to pay for parameterizing is almost zero.

Solving Constrained Reinforcement Learning Problems

As previously stated, the dual function is always a convex function since it is the point-wise maximum of linear functions. Thus the dual problem (DII) can be efficiently solved using (sub)gradient descent, with the caveat that because we require the dual iterates to remain in the positive orthant, we include a projection onto this space after taking the gradient step

Indeed, using the linearity of the expectation, the cumulative discounted cost for the reward $r_{\lambda}(s,a)$ yields

And therefore reinforcement learning algorithms such as policy gradient or actor-critic methods can be used to find the parameters $\theta$ such that they maximize the Lagrangian. The good performance of these algorithms is rooted in the fact that they are able to maximize the expected cumulative reward or at least to achieve a value that is close to the maximum. The next assumption formalizes this idea.

Notice that the previous assumption only means that we are able to solve the regularized unconstrained problem approximately. This means that the parameter at time $k+1$ is

Then, the dual variable is updated following the gradient descent scheme suggested in (16), where we replace the subgradient of the dual function by the constraint of the primal problem (PII). Defining $\hat{\partial}d_{k}\triangleq V(\theta_{k+1})-s$, the update yields

The algorithm given by (19)–(20) is summarized under Algorithm 1.

The previous algorithm relies on the fact that the $\hat{\partial}d_{k}$ does not differ much from $\partial d_{\theta}(\lambda_{k})$. We claim in the following proposition that this is the case. In particular, we establish that the constraint evaluation does not differ from the subgradient in more than $\delta$, the error on the primal maximization defined in Assumption 1.

Under Assumption 1, the constraint in (PII) evaluated at a local maximizer of Lagrangian $\theta^{\dagger}(\lambda)$ approximate the subgradient of the dual function (14). In particular it follows that

The previous proposition is key in establishing convergence of the algorithm proposed since allows us to claim that the dual updated is an approximation of a dual descent step. We formalize this result next and we establish a maximum number of dual steps required to achieve a desired accuracy.

Let $\pi_{\theta}$ be an $\epsilon$ universal parametrization of $\mathcal{P}(\mathcal{S})$ according to Definition 1, $B_{r}=\max_{i=1\ldots m}B_{r_{i}}$ with $B_{r_{i}}>0$ bounds on the rewards $r_{i}$ and $\gamma\in(0,1)$ be the discount factor. Then, if Slater’s conditions hold for (PII), under Assumption 1 and for any $\varepsilon>0$, the sequence of updates of Algorithm 1 with step size $\eta$ converges in $K>0$ steps, with

to a neighborhood of $P^{\star}$ –the solution of (PI)– satisfying

where $B=\sum_{i=1}^{m}\left(B_{r_{i}}/(1-\gamma)-c_{i}\right)^{2}$ and $\lambda^{\star}$ is the solution of (DI).

The previous result establishes a bound on the number of dual iterations required to converge to a neighborhood of the optimal solution. This bound is linear with the inverse of the desired accuracy $\varepsilon$. Notice that the size of the neighborhood to which the dual descent algorithm converges depends on the representation ability of the parametrization chosen, and the goodness of the solution of the maximization of the Lagrangian. Since the cost of running policy gradient or actor-critic algorithms until convergence before updating the dual variable might result in an algorithm that is computationally prohibitive, an alternative that is common in the context of optimization is to update both variables in parallel . This idea can be applied in the context of reinforcement learning as well, where a policy gradient —or actor critic as in —update is followed by an update of the multipliers along the direction of the constraint violation. In these algorithms the update on the policy is on a faster scale than the update of the multipliers, and therefore they operate from a theoretical point of view as (1). In particular, the proofs in rely on the fact that this different time-scale is such that allows to consider the multiplier as constant.

Numerical Example

In this section, we include a numerical example in order to showcase the consequences of our theoretical results. As an illustrative example, we consider a gridworld navigation scenario. This scenario, illustrated in Figure 1, consists of an agent attempting to navigate from a starting position to a goal. To do so, the agent must cross from the left side of the world to the right side using either one of two bridges, one of which is deemed “unsafe”. The agents uses a softmax policy with four possible actions (moving up, down, left, and right) over a table-lookup of states and actions. The agent receives a reward $r(s,a)=10$ for reaching the goal and a reward of $r(s,a)=-1$ for each step it wanders outside of goal. The scenario is designed such that the shortest path requires crossing the unsafe path (red bridge), while the safe path (blue bridge) requires a longer detour. Using our formulation, we constrain the agent to not cross the unsafe bridge with $99\%$ probability.

We train the agent via Algorithm 1, agent and plot in Fig. 2, the resulting normalized duality gap. We consider two cases, an inexact primal maximization via policy gradient and, an exact primal maximization. In order to obtain the global primal minimizer, for a given value of the dual variables $\lambda$, the optimal primal minimizer can be easily found via Dijkstra’s algorithm. We show that by solving Step 4 of Algorithm 1 exactly the duality gap effectively vanishes (red curve). We also showcase a curve in which Step 4 is replaced by a single policy gradient step (blue curve). Since the minimization in Step 4 is done approximately, the duality gap decreases at a slower rate and will only converge to a neighborhood of zero (as per Theorem 3). In any of the two cases, ultimately, the agent learns to navigate from start to goal by crossing the safe bridge (blue path in Fig. 1).

Now, we turn our attention to the effect of the parametrization size. We consider parametrization of different coarseness via state aggregation, as shown in Fig. 1. This will correspond, as per Definition 1, in parametrizations with lager values of $\epsilon$, i.e., looser approximators. Figure 3 displays the effect of using coarser parametrizations, as the parametrization becomes coarser, the duality gap increases (as per Theorem 2). Specially, for very coarse parametrizations (such as the cyan case), the agent cannot learn a successful policy due to the poor covering properties of its parametrization and resultantly such problem will have a large duality gap.

Discussion

Throughout this work we have developed a duality theory for constrained reinforcement learning problems. In particular we have established that for policies belonging to a general class of distributions, the duality gap of this problems is null and therefore by solving the problem on the dual domain —which always yields a finite dimensional convex problem —yields the same result as solving the original problem directly. Moreover, it establishes the equivalence between the constrained problem and the regularized problem —or manual selection of multipliers —in the sense that both problems track the same Pareto optimal front.

These theoretical implications however do not imply that it is always possible to solve the problem. To be able to solve the dual problem, one is required to evaluate the dual function, which might result intractable in several problems, for instance in cases where arbitrary policies are considered. To overcome this limitation, we have shown that for sufficiently rich parametrizations the zero duality gap result holds approximately. However, for the most part, the parametrizations considered in the literature are not necessarily universal approximators of distributions since in general the output of the neural network reduces to the mean —and in some cases the variance —of a distribution.

Regardless of these limitations, the primal dual algorithm considered here and those proposed in provide a manner to solve constrained policy optimization problems without the need to perform an exhaustive search over the weights that we assign to each reward function, as it is the case in . Likewise, the need of imposing constraints might arise directly from the algorithm design, this is for instance the case in Trust Region Policy Optimization , where a constraint on the divergence of the policy is included. Although our theorems do not guarantee that the zero duality gap result holds under these constraints, since they reduce to a projection onto a convex set it would not be surprising that it could be adapted.

References

Appendix A Proofs

Let us start by writing the left hand side of (13) as

Using the triangle inequality, we upper bound the previous expression as

Notice that to complete the proof it suffices to show that the right hand side of the previous expression is bounded by $\epsilon/(1-\gamma)$. We next work towards that end, and we start by bounding the difference $\left|p_{\pi}^{t}(s,a)-p_{\theta}^{t}(s,a)\right|$. Notice that this difference can be upper bounded using the triangle inequality as

Since $\pi_{\theta}$ is an $\epsilon$-approximation of $\pi$, it follows from Definition 1 that

where the last equality follows from the fact that $p_{\pi}^{t}(s)$ is a density. We next work towards bounding the integral of the second term in (26). Using the fact that $\pi_{\theta}(a|s)$ is a density, it follows that

Notice that the previous difference is zero for $t=0$ and for any $t>0$ it can be upper bounded by

Combining the bounds derived in (25), (27), (A) we have that

Notice that the first term on the right hand side of the previous expression is the sum of the geometric multiplied by $1-\gamma$. Hence we have that $(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\epsilon=\epsilon$. The second term on the right hand side of the previous expression is in fact the same as the term on the left hand side of the expression multiplied by the discount factor $\gamma$. Thus, rearranging the terms, the previous expression implies that

Notice that the dual functions $d(\lambda)$ and $d_{\theta}(\lambda)$ associated to the problems (PI) and (PII) respectively are such that for every $\lambda$ we have that $d_{\theta}(\lambda)\leq d(\lambda)$. The latter follows from the fact that the set of maximizers of the Lagrangian for the parametrized policies is contained in the set of maximizers of the non-parametrized policies. In particular, this holds for $\lambda^{\star}$ the solution of the dual problem associated to (PI). Hence we have the following sequence of inequalities

where the last inequality follows from the fact that $D^{\star}_{\theta}$ is the minimum of (DII). The zero duality gap established in Theorem 1 completes the proof of the upper bound for $D_{\theta}^{\star}$. We next work towards proving the lower bound for $D_{\theta}^{\star}$. Let us next write the dual function of the parametrized problem (DII) as

Let $\pi^{\star}\triangleq\operatorname*{argmax}_{\pi\in\mathcal{P}(\mathcal{S})}\mathcal{L}(\pi,\lambda)$ and let $\theta^{\star}$ be an $\epsilon$-approximation of $\pi^{\star}$. Then, by definition of the maximum it follows that

We next work towards a bound for $\mathcal{L}(\pi^{\star},\lambda)-\mathcal{L}_{\theta}(\theta^{\star},\lambda)$. To do so, notice that we can write the difference in terms of the occupation measures where $\rho^{\star}$ and $\rho_{\theta}^{\star}$ are the occupation measures associated to the the policies $\pi^{\star}$ and the policy $\pi_{\theta^{\star}}$

Since $\pi_{\theta^{\star}}$ is by definition an $\epsilon$ approximation of $\pi^{\star}$ it follows from Lemma 1 that

Using the bounds on the the reward functions we can upper bound the difference $\mathcal{L}(\pi^{\star},\lambda)-\mathcal{L}_{\theta}(\theta^{\star},\lambda)$ by

Combining the previous bound with (34) we can lower bound $d_{\theta}(\lambda)$ as

Let us next define $d_{\epsilon}(\lambda)=d(\lambda)-B_{r}\epsilon/(1-\gamma)\left\|\lambda\right\|_{1}$, and notice that in fact $d_{\epsilon}(\lambda)$ is the dual function associated to Problem (${\text{PI}}^{\prime}$) with $\xi_{i}=B_{r}\epsilon/(1-\gamma)$ for all $i=1,\ldots,m$. With this definition, (38) reduces to

Since the previous expression holds for every $\lambda$, in particular it holds for $\lambda_{\theta}^{\star}$, the dual solution of the parametrized problem (DII). Thus, we have that

Recall that $\lambda_{\epsilon}^{\star}=\operatorname*{argmin}d_{\epsilon}(\lambda)$, and use the definition of the dual function to lower bound $D_{\theta}^{\star}$ by

By definition of maximum, we can lower bound the previous expression by substituting by any $\pi\in\mathcal{P}(\mathcal{S})$. In particular, we select $\pi^{\star}$ the solution to (PI)

Since $\pi^{\star}$ is the optimal solution to (PI) it follows that $V_{i}(\pi^{\star})-c_{i}\geq 0$ and since $\lambda_{\epsilon,i}^{\star}\geq 0$ the previous expression reduces to

It follows from Assumption 1 that there exists $\delta>0$ such that $\mathcal{L}_{\theta}(\theta^{\star}(\lambda),\lambda)\leq\mathcal{L}_{\theta}(\theta^{\dagger}(\lambda),\lambda)+\delta$, thus we can upper bound the right hand side of the previous inequality by

Combining the two upper bounds completes the proof of the proposition. ∎

We start by showing the lower bound, which in fact holds for any $\lambda$. Notice that for any $\lambda$ and by definition of the dual problem it follows that $d_{\theta}(\lambda)\geq D^{\star}_{\theta}$. Combining this bound with the result of Theorem 2 it follows that

Expanding the square and using that $B=\sum_{i=1}^{m}\left(B_{r_{i}}/(1-\gamma)-c_{i}\right)^{2}$ is a bound on the norm squared of $V(\theta)-s$ it follows that

Using the result of Proposition 2 we can further upper bound the inner product in the previous expression by the difference of the dual function evaluated at $\lambda_{k}$ and $\lambda_{\theta}^{\star}$ plus $\delta$, the error in the solution of the primal maximization,

Defining $\alpha_{k}=2(\delta+d_{\theta}(\lambda_{\theta}^{\star})-d_{\theta}(\lambda_{k}))+\eta B$ and writing recursively the previous expression yields

Since $d_{\theta}(\lambda_{\theta}^{\star})$ is the minimum of the dual function, the difference $d_{\theta}(\lambda_{\theta}^{\star})-d_{\theta}(\lambda_{k})$ is always negative. Thus, when $\lambda_{k}$ is not close to the solution of the dual problem $\alpha_{k}$ is negative. The latter implies that the distance between $\lambda_{k}$ and $\lambda_{\theta}^{\star}$ is reduced by virtue of (50). To be formal, for any $\varepsilon>0$, when $a_{j}>-2\varepsilon$ we have that

Using the result of Theorem 2 we can upper bound $D_{\theta}^{\star}$ by $P^{\star}$ which establishes the neighborhood defined in (23). We are left to show that the number of iterations required to do so is bounded by

Since $\left\|\lambda_{K}-\lambda_{\theta}^{\star}\right\|^{2}$ is positive the previous expression reduces to $2K\eta\epsilon\leq\left\|\lambda_{0}-\lambda_{\theta}^{\star}\right\|^{2}$. Which completes the proof of the result. ∎