Solving Decision-Dependent Games by Learning from Feedback

Our work incorporates themes from games, learning, as well as stochastic optimization with decision-dependent distributions. We highlight the relationship with this relevant literature below.

Games. Within the context of games, our work is specifically focused on solving Nash equilibrium problems using gradient-based methods and a variational inequality (VI) framework. The literature on stochastic games is extensive; for a comprehensive yet concise review of the subject, we refer the reader to the tutorials [scutari2010convex] and [lei2022stochastic]; see also pertinent references therein. A common denominator of existing frameworks is that the data distribution is stationary. The work of [rosen1965existence] demonstrates that strictly monotone games have unique solutions and that gradient play converges to it. The modern approach of solving Nash equilibrium problems for continuous games via variational inequalities can be attributed to Facchinei and Pang [facchinei2003finite, harker1990finite]. For solving strongly monotone variational inequalities, the projected gradient method is capable of converging linearly.

Our work adds the additional complexity of minimizing communication between agents and hence we use a distributed gradient approach in our optimization algorithm. Distributed gradient methods have been explored extensively in the literature on convex optimization, though less so in that of variational inequalities. We refer the reader to [nedic2020distributed] for a review in the convex optimization setting, and [kovalev2022optimal] for variational inequalities.

Decision-Dependent Data. This paper contributes to the growing body of literature that studies stochastic optimization with decision-dependent data distributions. While the concept of decision-dependent distributions has existed for some time, its roots go back to the framework “Performative Prediction” and its use within the machine learning community [perdomo2020performative]; this work posits the formulation of optimization problems in which the data distribution is explicitly dependent on the optimization variables, and proposes repeated retraining (and the limit points thereof) as a solution. This is a family of points that solve the induced stationary optimization problem. For repeated retraining, convergence of various stochastic gradient algorithms are studied in [drusvyatskiy2022stochastic, mendler2020stochastic] in the batch setting, and in the time-varying setting in [cutler2021stochastic, wood2021online]. The extension of problems with to games includes two-player zero-sum games in [wood2021online], and general multiplayer games in [narang2022learning]. Additional recent extensions to this line of work include distributionally robust optimization[basciftci2021distributionally, luo2020distributionally] and time varying optimization [wood2021online, cutler2021stochastic].

Recent works have since pivoted towards directly solving the optimization problem by incorporating a model for the distributional map. In [miller2021outside], the authors provide conditions that ensure convexity of the expected cost, alongside a learning-based algorithm for finding solutions to problems with location scale families. The show that location scale families can be learned from the system prior to optimization without requiring further interaction with the system during optimization. The work of [lin2023plug] extends this learning framework beyond location scale families and derives regret bounds that incorporate the associated approximation and statistical errors arising from the statistical learning problem. Outside of the distribution learning approach, derivative-free methods have been studied in [miller2021outside, narang2022learning, wood2023stochastic]. While these methods do not depend on a learned model of the distributional map, they generally exhibit slower convergence rates. On the other hand, adaptive learning strategies, particularly for location-scale models, have shown promise, as discussed in [narang2022learning] whereby the model is learned during optimization. However, their exploration remains limited to this specific model category.

This work complements the technical findings in [lin2023plug] by offering a generalization of the so called “plug-in” approach presented in this work to the multi-agent setting. Relative to [narang2022learning], we focus on solving the Nash equilibrium problem for a general class of models by learning the distributional map prior to optimization—thereby reducing the required number of interaction with the system to receive a reasonable answer.

In this work, we provide the following contributions to the body of work on stochastic optimization and Nash equilibrium problems with decision-dependent distributions.

• (i)

  We propose an algorithm for finding a Nash equilibrium in stochastic games with decision-dependent distributions where: (i) the distributional map for each player’s cost is estimated from samples, and (ii) the estimated distributional map is used in gradient-based strategies.

• (ii)

  We provide guarantees on the approximation error of distributional maps for a class of map learning problems.

• (iii)

  We show that the parameterized cost approximates the ground-truth in high-probability.

• (iv)

  We propose a stochastic gradient-based algorithm for solving a parameterized strongly-monotone game, and we demonstrate linear convergence in expectation.

• (v)

  Finally, we provide numerical simulations of an EV charging market formulation using real-world data. The EV market formulation is new in the context of energy markets, thus providing contributions in this area.

In Section 2, we provide necessary notation and background for our analysis. In Section 3 we discuss the proposed learning algorithm in detail and present our primary result. Section 5 discusses the details of the optimization stage. We provide our numerical simulations in Section 5. Proofs of the results are provided in the Appendix.

Throughout this work, we restrict our focus to random variables drawn from continuous probability distributions supported over the Euclidean space. When random variables $X,Y\in\mathbb{R}^{k}$ are equal in distribution, i.e., $P(X\leq x)=P(Y\leq x)$ for all $x\in\mathbb{R}^{k}$, we write $X\overset{d}{=}Y$.

Our analysis includes study of sub-exponential random vectors. A univariate random variable $X\in\mathbb{R}$ is said to be sub-exponential with modulus $\theta>0$ provided that the survival function satisfies ${\mathbb{P}}(|X|\geq t)\leq 2\exp(-t/\theta)$ for all $t\geq 0$. By extension, a random vector $X\in\mathbb{R}^{k}$ is sub-exponential provided that $\langle u,X\rangle$ is a sub-exponential random variable for all $u\in{\cal S}^{k-1}$.

To compare probability distributions, we will be interested in computing the distance between their associated probability measures—for which we need a complete metric space. We let $\mathcal{P}(\mathbb{R}^{k})$ denote the set of finite first moment probability measures supported on $\mathbb{R}^{k}$ and write the Wasserstein-$1$ distance as

for any $\mu,\nu\in\mathcal{P}(\mathbb{R}^{k})$, where $\mathcal{L}_{1}$ is the set of all $1$-Lipschitz continuous functions $h:\mathbb{R}^{k}\rightarrow\mathbb{R}$. Under these conditions, the set $(\mathcal{P}(\mathbb{R}^{k}),W_{1})$ forms a complete metric space [bogachev2012monge].

We consider a game that consists of $n$ players. Each player has a cost function $F_{i}$, distributional map $D_{i}$, and decision set $\mathcal{X}_{i}\subseteq\mathbb{R}^{d_{i}}$. Hence, each player chooses a decision, or strategy $x_{i}\in\mathcal{X}_{i}\subseteq\mathbb{R}^{d_{i}}$. The concatenation of the decision variables is written as $x=(x_{1},\ldots,x_{n})\in\mathcal{X}\subseteq\mathbb{R}^{d}$ where $\mathcal{X}=\prod_{i=1}^{n}\mathcal{X}_{i}$ and $d=\sum_{i=1}^{n}d_{i}$. For a fixed agent $i$, we will decompose the decision $x$ as $x=(x_{i},x_{-i})$ where $x_{-i}\in\mathbb{R}^{d-d_{i}}$ is the strategy vector of all agents excluding the $i$th one.

The collection of costs $F_{i}$ and decision sets ${\cal X}_{i}$ defines the game

A Nash equilibrium of this game is a point $x^{*}\in\mathcal{X}$ provided that

for all $i\in[n]$. Intuitively, $x^{*}$ is a strategy such that no agent can be incentivized by its cost to deviate from $x_{i}^{*}$ when all other agents play $x_{-i}^{*}$. Finding Nash equilibria is the primary focus of this work.

Games of this form are commonly cast into a variational inequality framework. This is due, in part, to the observation that the Nash equilibria $x^{*}\in{\cal X}$ are the solutions to the variational inequality

where the gradient map $G:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ is defined as

Here, the notation $\nabla_{i}$ is used to represent the partial gradient $\nabla_{x_{i}}$. We will denote the set of Nash equilibrium of a game with gradient map $G$ and domain ${\cal X}$ as $\texttt{Nash}(G,{\cal X})$. Existence of solutions to variational inequalities of this form is guaranteed provided that the set ${\cal X}$ is convex and compact and the gradient map $G$ is monotone; uniqueness is guaranteed when $G$ is strongly-monotone [facchinei2003finite]. We say that $G$ is $\alpha$-strongly-monotone on ${\cal X}$ provided that there exists $\alpha>0$ such that

and monotone when $\alpha=0$. In this work, we primarily focus on strongly-monotone games. While monotone games are tractable, methods for solving them with decision-dependent distributions require alternative gradient estimators—a topic we leave to future work.

In this work, we introduce the additional complexity to the formulation in (4) that the $F_{i}$’s are the expected cost over a distributional map $D_{i}:\mathbb{R}^{d}\rightarrow{\cal P}(\mathbb{R}^{k_{i}})$. In particular, we write the cost as

This can be written alternatively as the integral

where $p_{i}$ is the probability density function for the distribution $D_{i}(x)$. When the integral satisfies the Dominated Convergence Theorem, computing the gradient amounts to differentiating under the integral and using the product rule. We then obtain

where we recall that $G(x)=\left(\nabla_{1}F_{1}(x),\ldots,\nabla_{n}F_{n}(x)\right)$. In short, characterizing the gradient of this decision-dependent game requires assumptions not only on $f_{i}$, but also on the properties of the distributional map $D_{i}$. Sufficient conditions for strong monotonicity of the game in (4) are due to [narang2022learning] and are stated in terms of the decoupled costs, given by

for all $x,y\in\mathbb{R}^{d}$, and their associated decoupled partial gradients

for all $x,y\in\mathbb{R}^{d}$ and

for all $x,y\in\mathbb{R}^{d}$. A key observation used in the proof is that $G_{i}(x)=\nabla_{i}F_{i}(x)=G_{i}(x,x)+H_{i}(x,x)$.

A critical component of our analysis is the estimation or learning of the distributional map and the subsequent characterization of the estimation error. In this section, we outline a class of expected risk minimization problems, which we call regular problems, for which we can characterize the distance between expected risk minimization solutions and empirical risk minimization solutions. Throughout, we write $R_{i}(\beta_{i})={\mathbb{E}}_{(x,z)}[R(x,z_{i},\beta_{i})]$ and $\widehat{R}_{i}(\beta_{i})=(1/m)\sum_{j=1}^{m}R_{i}(x^{(j)},z_{i}^{(j)},\beta_{i})$ for $\beta_{i}\in\mathbb{R}^{\ell_{i}}$ to denote the expected and empirical risk, respectively.

Items (a) and (c), taken together, guarantee existence of $\widehat{\beta}$ and uniqueness of $\beta^{*}$ as defined in (16) and (15), respectively. Furthermore, the inclusion of item (b) is necessary to guarantee that first-order stochastic gradient methods will converge at least sub-linearly to $\widehat{\beta}$. Lastly, the heavy-tail assumption [vershynin2018high] will allow us to describe the concentration of the gradient estimates. Together, they allow us to relate the solutions to the sample complexity in the following lemma.

The proof of this result is provided in the Appendix 6.1. This result offers a broad generalization of [mou2019diffusion, Equation (19b)] to any risk with Lipschitz-continuous sub-exponential gradients over any convex and compact set. Our result is comparable to the $\mathcal{O}(\sqrt{\ell_{i}}{m})$ rate that can be found for specific problem instances such as linear least squares regression and logistic regression, but with the addition of a $\sqrt{\log m}$ factor. Indeed, the generality of the risk function requires that we enforce compactness of the domain, thus giving rise to this extra logarithmic factor. This gradient estimation result will now allow us to reach our desired bounded distance result, which we present in the following theorem.

The proof of Theorem 3 is provided in the Appendix 6.2. The power in this characterization lies in the fact that it holds for any statistical learning problem satisfying the assumptions listed in Definition 1, and is not specific to the setting of learning distributional maps. We note that our Definition 1, which is a property used in the Theorem 3, is different from the one in [lin2023plug] and it involves conditions that are easier to check.

As an example, we provide conditions for which a linear least squares problem satisfies the regularity conditions and hence is subject to the above ERM approximation result.

The proof of Proposition 4 is provided in Appendix 6.3. Deriving conditions for the more general case of non-linear regression is attainable but outside the scope of this work.

Finding a relationship between $\widehat{x}$ and $x^{*}$ will require that we first characterize an appropriate hypothesis class of distributions for learning. Here, we formalize the notion of misspecification and sensitivity for a hypothesis class ${\cal H}_{{\cal B}_{i}}$.

Observe that if $\eta_{i}=0$, then our approximation error is zero and we incur no bias in our problem formulation. This corresponds to the case where the map $D_{i}$ is realizable [shalev2014understanding]. Though, small values of $\eta_{i}$ are appropriate as $D_{i}$ may be complex enough that approximating it with a finite-dimensional parameter space is difficult.

Sensitivity of ${\cal H}_{{\cal B}_{i}}$ is merely a convenient name for the condition that $\beta\mapsto D_{\beta_{i}}(x)$ be $\varepsilon_{i}$-lipschitz continuous for all realizations of $x\in{\cal X}$. In the result that follows, we demonstrate that an appropriately misspecified and sensitive hypothesis class induces a cost that has bounded distance to the ground truth cost in (1).

The proof of Theorem 5 is provided in the Appendix 6.4. By including an additional assumption on the Lipschitz continuity of the cost $f_{i}$ with respect to to other agents decisions $x_{-i}$, we can provide an analog of the excess risk result in  [lin2023plug].

The analysis in this section demonstrates that the estimation procedure in Algorithm 1 yields a cost function that approximates the original cost in (1) with an error the decreases as the number of samples increases. Furthermore, this bound exists independent of the conditioning of the Nash equilibrium problem we solve in the optimization phase. We note that (23) is similar to the result in [lin2023plug], but it is based on a different definition of regular problem (see Definition 1); the bound (25) is unique to this paper.

In the section that follows, we examine a family of hypothesis classes that allows the approximated game to be monotone, and provide suitable algorithms for solving them with convergence guarantees.

In our optimization phase, we seek to use a gradient-based algorithm that respects the agent’s communication structure with the system. For the sake of readability, we will suppress the $\beta_{i}$ subscript and instead refer to quantities $G_{i}$ keeping in mind that they will correspond to the approximate Nash equilibrium problem in (17) with solution $\widehat{x}$.

We will assume that each agent has access to an estimator of the gradient $\nabla_{i}F_{i}$ and is capable of projecting onto their decision set ${\cal X}_{i}$. In the constant step-size setup, each agent chooses a rate $\omega_{i}>0$ and performs the update

where $g_{i}^{t}$ is a stochastic gradient estimator for $\nabla_{i}F_{i}$ used at iteration $t$, which is then reported to the system and made available to all agents. For the sake of analysis, we will assume without loss of generality that the steps-sizes satisfy the ordering

and hence $\omega_{1}=\max_{i\in[n]}\omega_{i}$ and $\omega_{n}=\min_{i\in[n]}\omega_{i}$. The collective update can be written compactly as

where $W=\mathsf{diag}(\omega_{1}{\bf\mathds{1}}_{d_{1}},\ldots,\omega_{n}{\bf\mathds{1}}_{d_{n}})$ and $g^{t}$ is an estimator for $G(x^{t})$ at iteration $t$. Convergence of this procedure hinges on the following assumptions.

Assumption 1 is standard for guaranteeing convergence of gradient play [facchinei2003finite], and the uniformly bounded variance component of Assumption 2 is standard for convergence for stochastic algorithms. As we will show shortly, convergence with bias is possible and the result reduces to the unbiased case when $\rho^{t}=0$. The next result will quantify the one-step improvement of (32).

The proof of Lemma 8 is provided in the Appendix 6.5. We note that setting $\omega_{i}=\omega$ for some $\omega>0$ recovers the result in [narang2022learning, Theorem 15]. Following this one-step analysis, we can show convergence to a neighborhood of the Nash equilibrium.

The proof can be found in Appendix 6.6. The result shows that the algorithm converges linearly to a neighborhood of the Nash equilibrium $\widehat{x}$, where the radius of the neighborhood is dictated by the step-size, variance, and bias bounds. When $\rho=\sigma=0$, we retrieve linear convergence. In order to converge to $\widehat{x}$ directly, we will require a decaying step-size policy. For example, we consider the following policy:

for fixed constant $r>2$, which we assumed to be shared by all agents. Hence, the decaying step-size update is given by

In the theorem that follows, we show that this sequence converges to $\widehat{x}$ provided that the bias shares an asymptotic rate with $(\omega^{t})^{-1}$.

The proof of this result follows by a standard induction argument, and can be found in Appendix 6.7.