Lagrangian duality for constraints on expectations

post by jessicata (jessica.liu.taylor) · 2016-05-04T04:37:28.000Z · LW · GW · 0 comments

Contents

    Proof of theorem
  When does a Nash equilibrium exist?
    Example: Secondary objectives
    Example: Generative adversarial exponential families
None
No comments

Summary: It's possible to set up an zero-sum game between two agents so that, in any Nash equilibrium, one agent picks a policy to optimize a particular objective subject to some constraints on expected features of the state resulting from the policy. This seems potentially useful for getting an approximate agent to maximize some objective subject to constraints.

---

Consider the following optimization problem:

Maximize $f\left(\pi \right)$ subject to $E\left[a\right(X\left)|do\right(\pi \left)\right]⪰b$.

where $\pi$ is a policy, $f$ maps policies to reals, $X\in X$ is a random variable representing the state of the world, $a\in X\to R^n$ is a feature vector, and $b\in R^n$ is a vector. This objective instructs the agent to maximize some objective $f\left(\pi \right)$ while ensuring that random variables $a_1\left(X\right),...,a_n\left(X\right)$ have expectations at least $b_1,...,b_n$ respectively.

How might we design a agent that solves the constrained optimization problem, if all we have available are agents that optimize unconstrained objectives? Consider a game between two agents, an actor and a critic:

1. The critic picks Lagrange multipliers $\lambda \in R^n,\lambda ⪰0$.
2. The actor picks a policy $\pi$, which results in world state $X$.
3. The actor gets utility $f\left(\pi \right)+\lambda \cdot \left(a\right(X)-b)$. The critic gets the negation of this utility.

Let's assume the critic and actor pick their $\lambda$ and $\pi$ simultaneously, and attempt to find the Nash equilibrium. Since the critic has an infinite action space, there is not guaranteed to be a Nash equilibrium.

To make the problem easier, let's assume that the set of allowed policies is convex, and $f$ is concave (that is, for any two policies ${\pi }_1$ and ${\pi }_2$, and $\theta \in (0,1)$, then if ${\pi }_3$ is the policy formed by first picking ${\pi }_1$ with probability $\theta$ or ${\pi }_2$ with probability $1-\theta$ and then running that policy, $f\left({\pi }_3\right)\ge \theta f\left({\pi }_1\right)+(1-\theta )f\left({\pi }_2\right)$).

We will prove:

Theorem: in any Nash equilibrium, the actor's policy solves the original optimization problem.

This is due to Lagrangian duality; the critic is picking Lagrange multipliers. It's possible that a setup like this results in reasonable behavior if we use approximate agents instead of optimal agents (and perhaps place some high absolute limit on $\lambda$), which would be the main practical application of this idea, though I'm not sure if it does.

Proof of theorem

The actor's expected utility is $g_{\lambda }\left(\pi \right):=f\left(\pi \right)+\lambda \cdot \left(E\right[a\left(X\right)|do\left(\pi \right)]-b)$.

With the assumptions above, we need only consider pure Nash equilibria. The critic's utility is linear in $\lambda$ and the actor's utility is concave in $\pi$; thus a pure strategy $\lambda$ weakly dominates any mixed strategy with mean $\lambda$, and a policy $\pi$ weakly dominates any distribution over policies whose mean is $\pi$.

First consider the game from the critic's perspective. Consider a few different cases:

1. Suppose $E\left[a_i\right(X\left)|do\right(\pi \left)\right]<b_i$ for some $i$. Then the critic gets more expected utility the higher ${\lambda }_i$ is; thus there is no best-response ${\lambda }_i$ value. Therefore, no Nash equilibria have this property.
2. Suppose $E\left[a_i\right(X\left)|do\right(\pi \left)\right]=b_i$ for some $i$. Then the critic is indifferent about ${\lambda }_i$ and may set it to anything.
3. Suppose $E\left[a_i\right(X\left)|do\right(\pi \left)\right]>b_i$ for some $i$. Then the critic must set ${\lambda }_i=0$ to maximize expected utility.

So in any Nash equilibrium we must have:

Property 1: $E\left[a\right(X\left)|do\right(\pi \left)\right]⪰b$

Property 2: $\lambda \cdot \left(E\right[a\left(X\right)|do\left(\pi \right)]-b)=0$; equivalently, $g_{\lambda }\left(\pi \right)=f\left(\pi \right)$

These properties correspond to the primal feasibility and complementary slackness KKT conditions.

Now let's consider the game from the actor's perspective. The actor will pick $\pi$ to maximize

$$g_{\lambda }\left(\pi \right):=f\left(\pi \right)+\lambda \cdot \left(E\right[a\left(X\right)|do\left(\pi \right)]-b)$$

Let ${\pi }^{\ast }$ solve the original optimization problem: it maximizes $f\left({\pi }^{\ast }\right)$ subject to $E\left[a\right(X\left)|do\right({\pi }^{\ast }\left)\right]⪰b$. Now observe that, in any Nash equilibrium:

1. $f\left(\pi \right)\le f\left({\pi }^{\ast }\right)$. This is because $\pi$ satisfies the constraints of the original optimization problem and ${\pi }^{\ast }$ maximizes $f$ subject to the constraints.
2. $f\left(\pi \right)\ge f\left({\pi }^{\ast }\right)$. This is because we have $f\left({\pi }^{\prime }\right)\le g_{\lambda }\left({\pi }^{\prime }\right)$ for all ${\pi }^{\prime }$ satisfying the constraints; in particular, $f\left({\pi }^{\ast }\right)\le g_{\lambda }\left({\pi }^{\ast }\right)\le g_{\lambda }\left(\pi \right)=f\left(\pi \right)$.

So in any Nash equilibrium, we have

Property 3: $f\left(\pi \right)=f\left({\pi }^{\ast }\right)$

Properties 1 and 3 together imply the theorem:

Theorem: in any Nash equilibrium, the actor's policy solves the original optimization problem.

When does a Nash equilibrium exist?

We've shown a property that all Nash equilibria of this game satisfy, but is a Nash equilibrium guaranteed to exist? Whenever some policy satisfies the constraints of the original optimization problem, I think one does, but I haven't been able to prove this.

There's no Nash equilibrium when no $\pi$ satisfies the constraints; in that case the critic would always want to set the ${\lambda }_i$ value corresponding to a violated constraint to an extremeley high value.

Example: Secondary objectives

Consider the following optimization problem:

Maximize $f\left(\pi \right)$ subject to $E\left[a\right(X\left)|do\right(\pi \left)\right]\ge b$.

In effect, an agent solving this optimization problem will ensure that it solves the primary objective of getting a high-enough expected $a\left(X\right)$ value, and will otherwise attempt to optimize the secondary objective $f\left(\pi \right)$.
In the game corresponding to this optimization problem, the critic picks $\lambda$ to be the exchange rate between the primary and secondary objectives that causes the actor to maximize the secondary objective subject to getting enough of the primary objective.

It's possible that something like this could be used for mild optimization, though I haven't worked out the details. We would want to set $f$ to be something simple that we're pretty comfortable with an AI approximately maximizing under the constraint, and I haven't found anything of this form yet.

Example: Generative adversarial exponential families

(note: this probably isn't actually useful)

Suppose we want to approximately sample from an exponential family $p_{\eta }\left(x\right)=\exp (\eta \cdot \varphi (x)-g(\eta \left)\right)$ with $\eta$ set to maximize likelihood of the training data $x_1,...,x_m$. Define $\mu \left(q\right):=E_{X\sim q}\left[\varphi \right(X\left)\right]$, and ${\mu }_{data}:=\frac{1}{m}{\sum }_{i=1}^m\varphi \left(x_i\right)$.

We would like to obtain a distribution $q$ that maximizes $H\left(q\right)$ subject to $\mu \left(q\right)={\mu }_{data}$. By the maximum entropy theorem, the optimal $q$ will be $p_{\eta \ast }$, where ${\eta }^{\ast }$ is chosen to maximize the likelihood of the data according to $p_{{\eta }^{\ast }}$.

Consider the following game, which resembles generative adversarial networks:

1. The critic picks a natural parameter $\eta \in R^n$.
2. The actor picks a distribution $q:\Delta X$
3. We take a sample $X\sim q$.
4. The actor gets utility $-\log q\left(X\right)+\eta \cdot \left(\varphi \right(X)-{\mu }_{data})$; the critic gets the negation of this utility.

Note that $-\log q\left(X\right)$ is an unbiased estimate of $H\left(q\right)$, so we can consider $H\left(q\right)$ to be the objective to be optimized subject to the constraints $\mu \left(q\right)={\mu }_{data}$.

At any Nash equilibrium, we will have:

1. The actor picks $q:=p_{\eta \ast }$
2. The critic picks $\eta :={\eta }^{\ast }$

The first fact is proven as a special case of the original theorem (plus the maximum entropy theorem); the second fact is not difficult to show given the first fact.

I believe this approach is similar to contrastive divergence. To recover the power of the original generative adversarial networks, perhaps $\varphi$ ought to be features output by a neural net. An advantage of this approach over generative adversarial networks is that the actor is penalized for differing from the training distribution in a hard-to-detect way (such as by plagiarizing from training data, or encoding steganographic messages; this is similar to the informed oversight problem), because the exponential family distribution $p_{{\eta }^{\ast }}$ is the uniquely optimal solution (although this doesn't guarantee that the approximate solution will be very close to $p_{{\eta }^{\ast }}$).

Unfortunately, this approach requires estimating $q\left(X\right)$, so $q$ must be represented as a variational autoencoder or something similar. But if we're using variational autoencoders, then we might as well directly train a generative model. So the approach I'm sketching here is probably not directly useful on its own (though I can see it being inspiration for a more useful approach to training generative models in a safely scalable way).

0 comments

Comments sorted by top scores.