Zhengyuan Zhou
email: zyzhou@stanford.edu

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

Aris L Moustakas
email: arislm@phys.uoa.gr

Nicholas Bambos
email: bambos@stanford.edu

Peter Glynn
email: glynn@stanford.edu

Robust Power Management via Learning and Game Design

Keywords: power management, online learning, Nash equilibrium, monotone games. 1

We consider the target-rate power management problem for wireless networks and we propose two simple, distributed power management schemes that regulate power in a provably robust manner by efficiently leveraging past information. Both schemes are obtained via a combined approach of learning and "game design" whereby power management is reformulated as a Nash equilibrium problem for a game with suitably designed payoff functions, and the networks' users employ a no-regret learning algorithm to maximize their individual utility over time. To establish convergence, we focus on the well-known online learning algorithm called online (lazy) gradient descent (OGD) in a general class of (weighted) monotone games. In this class of games (which properly includes all concave potential games), we show that multi-agent OGD converges to the unique Nash equilibrium, even when players only have imperfect/stochastic feedback at their disposal.

In the context of power management in static (deterministic) networks, we show that the designed games are monotone when the network is feasible in the first place (i.e. when all users can concurrently attain their target rates). Otherwise, in time-varying (stochastic) networks where channel quality fluctuates ergodically over time, the designed games are monotone even when the network is only feasible on average (i.e. even though users may be unable to meet their requirements with positive probability). As a result, the proposed power management algorithms converge almost surely to the joint optimal transmission power when the network is feasible on average. This comes in stark contrast to existing algorithms (like the seminal Foschini-Miljanic algorithm and its variants) that may fail to converge altogether.

Introduction

Viewed abstractly, power management (or power control ) is a collection of techniques that allows the users of a wireless network to achieve their performance requirements (e.g. in terms of throughput) while minimizing the power consumed by their equipment. Thus, given the key part played by transmitted power in increasing battery life and network capacity, power control has been a core aspect of network design ever since the early development stages of wireless networks.

In this general context, distributed power management has proven to be the predominant power management paradigm, and with good reason: centralized coordination is extremely difficult to achieve in large-scale wireless networks, a single point of failure in a centralized allocator could have devastating network-wide effects, the communication overhead alone becomes unmanageable in cellular networks, and the list goes on [START_REF] Rappaport | Wireless Communications: Principles and Practice[END_REF][START_REF] Goldsmith | Wireless communications[END_REF]. Consequently, considerable effort has been devoted to designing distributed power management algorithms that are provably capable of attaining various performance guarantees required by the network's users while leaving a sufficiently small footprint at the device level.

The problem of distributed power management becomes even more important and challenging in the exciting era Internet of Things (IoT) [START_REF] Bradley | Embracing the internet of everything to capture your share of $14.4 trillion[END_REF], which paints the compelling vision (in part already under way) of embedding uniquely identifiable wireless devices in the world around us and connecting these devices/sensors to the existing Internet infrastructure to form an intelligent and coherently functional entity -as in "smart cities" [START_REF] Deakin | Smart Cities: Governing, Modelling and Analysing the Transition[END_REF], patient monitoring [START_REF] Byrne | The ingestible telemetric body core temperature sensor: a review of validity and exercise applications[END_REF] and digital health [START_REF] Au-Yeung | A networked system for self-management of drug therapy and wellness[END_REF]. Thus, as the exponentially growing number of wireless communicating "things" has been pushing the entire wireless ecosystem from the low-traffic, low-interference regime to the high-traffic, high-interference limit, the power management question grows ever more urgent: how can the power of battery-driven (and hence energy-constrained) devices be regulated in a distributed, real-time manner so as to achieve the quality-of-service guarantees using minimum power in the presence of the inherent stochastic fluctuations of the underlying wireless network?

The current gold standard for power management is the seminal method of [START_REF] Foschini | A simple distributed autonomous power control algorithm and its convergence[END_REF], which, owing to its elegance, simplicity and strong convergence properties, is still widely deployed (in one variant or another). The original Foschini-Miljanic (FM) algorithm was expanded upon in a series of subsequent works [START_REF] Mitra | An asynchronous distributed algorithm for power control in cellular radio systems[END_REF][START_REF] Yates | A framework for uplink power control in cellular radio systems[END_REF], [START_REF] Ulukus | Stochastic power control for cellular radio systems[END_REF] that considered different variants of the problem (e.g. working with maximum power constraints, allowing devices to asynchronously update their power, etc.). Thereafter, various other objectives related to power management have been considered in wireless networks (as well as in the closely related wireline networks), resulting in more sophisticated models and more complex algorithms addressing issues related to throughput (El Gamal et al. 2006a,b, Seferoglu et al. 2008[START_REF] Reddy | Distributed power control in wireless ad hoc networks using message passing: Throughput optimality and network utility maximization[END_REF], fairness [START_REF] Eryilmaz | Randomized algorithms for throughputoptimality and fairness in wireless networks[END_REF], delays [START_REF] Eryilmaz | On the delay and throughput gains of coding in unreliable networks[END_REF][START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[END_REF], backlog [START_REF] Bambos | Channel access algorithms with active link protection for wireless communication networks with power control[END_REF][START_REF] Gitzenis | Power-controlled data prefetching/caching in wireless packet networks[END_REF][START_REF] Reddy | On distributed scheduling with heterogeneously delayed network-state information[END_REF][START_REF] Gopalan | Wireless scheduling with partial channel state information: large deviations and optimality[END_REF] and weighted-sum-of-rates [START_REF] Candogan | Near-optimal power control in wireless networks: A potential game approach[END_REF][START_REF] Weeraddana | Weighted sum-rate maximization in wireless networks: A review[END_REF]). 1 Importantly, most of the existing (distributed) power management/control schemes tend to rely implicitly only on the previous power iterate when selecting the power for the current iteration (especially when pertaining to the target-rate power management problem that we consider here).

In some respects, there is good reason to do so: the resulting power control algorithm is simple to use and implement; it does not need to use up memory to keep track of the entire radiated power history (a scarce resource in small wireless devices); and, as a pleasant by-product, the algorithm becomes much easier to analyze theoretically.

Notwithstanding, a crucial and well-known downside to this approach is that such algorithms tend to be unstable because a single power iterate is the sole power selection criterion. In particular, despite the various convergence and optimality guarantees observed when the underlying wireless network is static/slowly-varying (see e.g. Chiang et al. 2008, Tan 2015, andreferences therein), this Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!) instability is acutely manifested in time-varying, stochastic networks, especially when the number of mobile devices is large and/or power control is occasionally infeasible due to device mobility (a case that is much less studied and understood; cf. Section 2.3 for a detailed discussion). As we discuss in the rest of this paper, this instability is in some sense the root cause for the lack of both convergence and optimality results when the network is stochastic and time-varying. Under this light, the explicit use of all past iterates holds great promise for the overall stability of a power management policy, as the influence of the last iterate cannot have a dominating effect over the algorithm's previous iterates (provided they are utilized in an intelligent, memory-efficient way).

Our aim in this paper is to provide a distributed power control algorithm satisfying the above desiderata. This task faces two key challenges from a practical perspective: First, such an algorithm cannot take for granted that each transmitter has access to the power characteristics of all other transmitters, as such information is typically unavailable in practical scenarios. This dictates that any given transmitter can only make explicit use of link-specific information such as its signal-tointerference plus noise ratio (SINR) and/or the total interference and noise at the receiver (i.e. information that can be sensed by each individual link in the network). Second (and perhaps more stringently), a transmitter should not be required to store all past information (including past power, SINR and/or interference measurements) in an explicit fashion. If met, this requirement is highly desirable for memory-constrained wireless transmitter where such bookkeeping is in general infeasible -in words, past information must be exploited in an implicit, parsimonious manner.

Our Contributions and Related Work

Our main contributions are highlighted below in the context of related work on the topic:

1. A Learning and Game Design Approach to Power Management. To tackle the power management question (in both deterministic and stochastic networks) we map the original problem to that of finding the unique Nash equilibrium of a suitably designed continuous game (i.e. a game with continuous action spaces) and then apply a well-known no-regret learning algorithm. To streamline the presentation of the results, we start by formally describing in Section 3 the two simple and efficient power control algorithms based on dual averaging (Variants A and B), both of which only require very little operational overhead while leveraging past information in an efficient way. In particular, the information on past power iterates is represented in the most parsimonious form possible: it takes only a constant amount of memory independent of the number of time steps involved. In fact, the amount of memory required is the same as that of the algorithms using only the last power iterates (e.g. FM), even though the latter do not make explicit use of past power information.

Furthermore, by mapping the proposed power management algorithms to a game-theoretic learning problem (our second contribution; see below and Section 4), we are able to examine in depth the properties of the two variant dual averaging algorithms and establish theoretical guarantees in both deterministic (static) and stochastic (time-varying) environments. More precisely, in the case of static channels, we show that feasibility of a network directly implies convergence of dual averaging to the joint optimum transmission power vector (Theorem 6). 2 Furthermore (and perhaps most surprisingly), in the stochastic case (where the fluctuating network is sometimes feasible and sometimes not), we show that convergence to a deterministic power vector is still guaranteed with probability 1 as long as the network is feasible in the mean -i.e. even if the network is infeasible with positive probability (Theorem 7). This last property is particularly appealing because it incorporates elements of both stability and optimality (and hence robustness): the former because the proposed algorithms converge almost surely to a fixed constant power vector (despite the persistent, random fluctuations in the network); the latter because the algorithm's end state is an optimal solution of the network's power management problem with respect to the network's mean value. This comes in sharp contrast to the FM algorithm which, when the channel is feasible on average, may fail to converge altogether -or, at best, only converges in distribution to a power profile that is not optimal in any way [START_REF] Zhou | A stochastic stability characterization of the foschini-miljanic algorithm in random wireless networks[END_REF].

Importantly, establishing the algorithms' convergence takes us through a distinct (albeit related) line of research, namely utility-based models of power management in wireless networks [START_REF] Famolari | A new framework for power control in wireless data networks: Games, utility, and pricing[END_REF][START_REF] Alpcan | Cdma uplink power control as a noncooperative game[END_REF], 2006, Fan et al. 2006, Menache and Ozdaglar Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!) 2010, [START_REF] Han | Game Theory in Wireless and Communication Networks[END_REF]. This flourishing literature has taken the view that each device is a self-interested entity with its individual objective depending on how much power it uses as well as how much power all the other devices use (via the interference that they create). In this literature, the cost function of each device (as a function of, say, signal-to-interference ratio) is modeled explicitly and pertains to the utility of each user of that device: in other words, the resulting game is a priori assumed to model the underlying reality. In contrast, the "game design" approach that we take in this paper leads to a virtual game that only enters the problem as a theoretical tool to aid the design of robust power management algorithms (which are implemented at the device level and are not subject to game-theoretic rationality postulates). Nevertheless, the resulting games do admit a natural interpretation as they effectively measure the distance betweeen the users' achieved throughput and their target rates.

The idea of "game design" has been explored before and our approach here is inspired by the remarkable works of [START_REF] Candogan | Near-optimal power control in wireless networks: A potential game approach[END_REF] and [START_REF] Li | Designing games for distributed optimization[END_REF]. In more detail, Candogan et al. ( 2010) designed a near-potential game for the maximum weighted-sum-ofrates problem and used best-response dynamics to derive a power control algorithm. [START_REF] Li | Designing games for distributed optimization[END_REF] designed a potential game and used a particular method (called gradient-play) to derive a distributed optimization algorithm for the network consensus problem. In addition to considering a different problem altogether (power minimization subject to rate constraints), our work here differs from the above in several key aspects: First, our game-theoretic analysis is not limited to potential (or near-potential) games, but it instead applies to all (weighted) monotone games (cf. Section 4). Second, by focusing on online gradient descent (see below), our results can also be framed in the context of no-regret learning in games. Finally, to tackle the stochastic regime, we consider a more general framework with imperfect feedback which is only accurate up to a bounded-variance error (again, see below). The above elements cannot be treated with the techniques of [START_REF] Candogan | Near-optimal power control in wireless networks: A potential game approach[END_REF] and/or [START_REF] Li | Designing games for distributed optimization[END_REF], leading us to introduce a new set of tools from stochastic approximation, martingale limit theory and variational analysis.

2. Online Gradient Descent and No-Regret Learning in Games. To establish the convergence properties of the proposed power management algorithms, we consider a much more general framework for no-regret learning in games with continuous action sets and individually concave (but otherwise unknown) payoff functions. Working at this level of generality achieves two distinct goals: First, by abstracting away the problem's functional details, it shows that distributed power control can be interpreted in a natural way as a multi-agent regret minimization problem (more on this below). Second, it allows us to provide a general convergence result for no-regret learning in concave games with imperfect first-order, gradient feedback.

As such, our theoretical investigation here falls within the broader inquiry of game-theoretic learning, an area that stands at the intersection of learning and game theory and that seeks to answer the following question: what is the evolution of play when every player adopts a noregret learning algorithm? In particular, if all players of a repeated game employ an updating rule that leads to no regret, do their actions converge to a Nash equilibrium of the one-shot game?

The first (and, to this date, the most widely studied) algorithm for no-regret learning in online decision processes with convex action spaces is the online gradient descent (OGD) method pioneered by [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF]. 3 Up to a multiplicative constant related to the problem's dimensionality, the O( √ T ) regret minimization rate of OGD is well-known to be minmax optimal [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF], so OGD has seen extensive use in online decision problems. With this in mind, our first key observation is that the proposed power control algorithms can be seen as OGD schemes for a specific utility function capturing each user's power control objective (the "game design" component described above).

The importance of this observation is clear: a no-regret learning algorithm provides a player with sharp worst-case guarantees, so it is natural to expect that every player will adopt such an algorithm in selecting their actions in the decision process. On that account, a flourishing line of research tackling this problem has emerged in the past decade or so. However, most "considerably more difficult", because Nash equilibrium is significantly finer than its correlated variants: 4 in general, these convergence results do not extend to Nash equilibria.

To account for this, a growing corpus of literature has been devoted to studying the problem of equilibrium convergence under no-regret learning, typically focusing on special classes of games (such as convex potential games, zero-sum games, routing games, etc.). Here again, most efforts have focused on the convergence of the time-averaged sequence of play because of its connection to the players' regret [START_REF] Krichene | Convergence of heterogeneous distributed learning in stochastic routing games[END_REF][START_REF] Balandat | Minimizing regret on reflexive banach spaces and learning nash equilibria in continuous zero-sum games[END_REF][START_REF] Lam | On learning how players learn: estimation of learning dynamics in the routing game[END_REF]). Nevertheless, the convergence of the actual sequence of play is also crucial to investigate for several reasons: First, from a practical standpoint, since the players' payoffs are determined by the sequence of chosen actions and not some fictitious variant thereof, convergence to Nash equilibrium should also be stated in terms of the actual sequence of play. Second, from a theoretical standpoint, convergence of the latter implies convergence of the former, so it is a stronger result.

Our focal point in this paper is the class of λ-monotone games, i.e. games that satisfy Rosen's diagonal strict concavity condition (Rosen 1965a). Mathematically, this condition implies that the profile of the players' individual payoff gradients is a monotone operator in the sense of variational analysis (possibly up to a player-specific weight coefficient); as an immediate corollary, if a game is monotone, it admits a unique Nash equilibrium. Importantly, going back to the problem of power control, the key tie-in observation is that our game-theoretic reformulation leads to a monotone game whenever power control is feasible on average (Lemma 3). Thus, by establishing the convergence of OGD in monotone games, we readily recover the convergence of our proposed power control policies when power control is feasible in the first place.

Motivated by the random, time-varying nature of channel feasibility in realistic wireless environments, we frame all of the above in a bona fide stochastic setting where exact gradient information is not available, either because the players' payoffs are themselves stochastic in nature, or because the players' feedback is contaminated by noise, observation errors, and/or other exogenous stochastic effects. To model all this, we consider a noisy feedback model where players only have access to a first-order oracle providing unbiased, bounded-variance estimates of their payoff gradients at each step. Apart from this, players are assumed to operate in a "black box" setting, without any knowledge of the game's structure or their payoff functions (or even that they are playing a game).

In this general framework, our main results are as follows: For a general class of continuous games called λ-monotone games (first studied by Rosen 1965b), OGD converges to the unique Nash equilibrium in the perfect gradient case (Theorem 4). Further, for λ-monotone games, even when only a noisy and unbiased gradient is available, OGD converges to the unique Nash equilibrium almost surely (Theorem 5).

Model, Background, Motivation

We describe below the target-rate power management problem on wireless networks [START_REF] Weeraddana | Weighted sum-rate maximization in wireless networks: A review[END_REF][START_REF] Tan | Wireless network optimization by perron-frobenius theory[END_REF]. After introducing the problem in Section 2.1, we discuss in Section 2.2 the well-known Foschini-Miljanic (FM) power control algorithm [START_REF] Foschini | A simple distributed autonomous power control algorithm and its convergence[END_REF]. This discussion will provide an account of some of the drawbacks of the FM algorithm, both quantitative and qualitative, and will serve as the motivation of the paper (cf. Section 2.3).

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Setup

Consider a wireless network of N communication links, each link consisting of a transmitter and an intended receiver. Assume further that the i-th transmitter transmits with power p i and let p = (p 1 , . . . , p N ) ∈ R N + denote the joint power profile of all users (transmitters) in the network. In this context, the most commonly used measure of link service quality is the signal-to-interference-andnoise ratio (SINR). Intuitively, link i's SINR depends not only on how much power its transmitter is employing, but also on how much power all the other transmitters are concurrently employing.

Specifically, link i's SINR, which we denote by r i (p), is given by the following ratio:

r i (p) = G ii p i j =i G ij p j + η i , (1)
where η i is the thermal noise associated with the receiver of link i and G ij ≥ 0 is the power gain between transmitter j and receiver i, representing the interference caused to receiver i by transmitter j per unit transmission power used. We further assume throughout the paper that G ii > 0 for otherwise transmission for link i is meaningless. We collect all the power gains G ij into the gain matrix G and all the thermal noises into the noise vector η. Note that the power gain matrix G depends on the underlying network topology of the wireless links. Each link has a target SINR threshold r * i > 0: the minimum acceptable service quality threshold for that link.

The target-rate power management problem [START_REF] Weeraddana | Weighted sum-rate maximization in wireless networks: A review[END_REF][START_REF] Tan | Wireless network optimization by perron-frobenius theory[END_REF] then lies in finding a power assignment p, such that the following quality-of-service constraints hold:

r i (p) ≥ r * i , ∀i. (2)
In order to find a joint transmission power p that satisfies the quality-of-service constraints in Equation ( 2), such a p must exist in the first place: the notion of wireless network channel feasibility, formalized in the next definition, characterizes such scenarios.

Definition 1. The channel given by (G, η) is feasible with respect to a target SINR vector r * = (r * 1 , . . . , r * N ) if there exists a p satisfying Equation ( 2). The channel is otherwise said to be infeasible.

In their original paper, [START_REF] Foschini | A simple distributed autonomous power control algorithm and its convergence[END_REF] presented a simple necessary and sufficient condition for deciding when a channel is feasible. To state it, we first need a convenient and equivalent characterization of a wireless network channel:

Definition 2. A wireless network channel (or channel for short) specified by (G, η) can be alternatively represented by the pair (W, γ) consisiting of the following components:

1. The re-weighted gain matrix W , where for i, j ∈ {1, 2, . . . , N }:

W ij :=          0, i = j r * i G ij G ii , i = j.
(3)

2. The re-weighted noise vector γ, where

γ i = r * i η i G ii , i ∈ {1, 2, . . . , N }. ( 4
)
Theorem 1. A channel is feasible with respect to r * if and only if the largest 5 eigenvalue λ max (W )

of the re-weighted gain matrix W satisfies λ max (W ) < 1.

When the channel is feasible, there is a special joint transmission power p * that satisfies the quality-of-service constraints in Equation 2:

Fact 1. Given a feasible channel (G, η), we have λ max (W ) < 1, which implies that (I -W ) -1 exists and is component-wise strictly positive. This further implies that the joint transmission power p * = (I -W ) -1 γ satisfies the quality-of-service constraints given in Equation ( 2) and it is component-wise strictly positive. Finally, p * is the unique vector that satisfies the following property: if p is any vector satisfying Equation (2), then p * ≤ p (component-wise).

In other words, p * is the "smallest" joint transmission power that satisfies the quality-of-service constraints. To highlight the importance of this quantity and to recognize the fact that the results in this paper will mostly pertain to p * , we have the following definition:

Definition 3. In a feasible channel (G, η) (or equivalently (W, γ)), p * defined in Fact 1 is called the optimal joint transmission power vector.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Foschini-Miljanic Power Control Algorithm

We now present the well-known Foschini-Miljanic (FM) power control algorithm, which finds the optimal joint transmission power if one exists (i.e. in a feasible channel). Following the standard convention in wireless communications literature [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models, and Applications[END_REF]), the transmission power p i for transmitter i is assumed to lie in a compact interval

P i = [0, p max i ].
Therefore, p is constrained to lie in the feasible support set P

N i=1 P i = N i=1 [0, p max i ].
We shall adopt this convention for the rest of the paper. The FM algorithm is then formally given in Algorithm 1 below:

Algorithm 1 FM Algorithm: Bounded Power Support 1: Each link i chooses an initial power p 0 i ∈ [0, p max i ]
.

2: for t = 0, 1, 2, . . . do 3:

for i = 1, . . . , N do 4:

p t+1 i = min(p t i r * i r i (p t ) , p max i ) 5:
end for 6: end for

In the classical power control setting, the channel (G, η) is assumed to be deterministic and timeinvariant, i.e. (G, η) remains the same from iteration to iteration. By a monotonicity argument, [START_REF] Foschini | A simple distributed autonomous power control algorithm and its convergence[END_REF] provide the following characterization:

Theorem 2. Let the channel (G, η) be deterministic and time-invariant.

• If the channel is feasible with respect to r * and if the power support includes the optimal power vector (i.e. p * ∈ P), then the joint power iterate p t in Algorithm 1 converges to the optimal joint transmission power p * , irrespective of the initial point p 0 .

• If the channel is infeasible with respect to r * or if the power support does not include the optimal power vector (i.e. p * / ∈ P), then the joint power iterate in Algorithm 1 converges to p max , irrespective of the initial point p 0 .

Motivation of the Paper

Although the FM algorithm enjoys good convergence properties in a deterministic and timeinvariant channel (as given in Theorem 2 above), it quickly loses its appeal in cases where the channel is stochastic and time-varying (i.e. when (G t , η t ) ∞ t=0 are stochastic processes): this can occur when the transmitters and receivers in the wireless network are moving while communicating with each other, thereby causing the channel gain matrix (and potentially the thermal noises) to fluctuate from iteration to iteration. This is because FM, in only using the last power iterate p t to determine the next power iterate p t+1 , has certain inherent instability, which is particularly manifested when the underlying channel is stochastic and time-varying.

When the channel environment is stochastic and time-varying, we use W t and γ t to denote the random re-weighted gain matrix and the random re-weighted noise at iteration t, respectively. We will use P t to denote the random power vector at iteration t generated by some power control algorithm. More concisely, denoting Π P (y) = arg min x∈P xy and denoting the projection operator Π P (•) for P, the FM update can be written as

P t+1 = Π P (W t P t + γ t ). ( 5
)
In a stochastic and time-varying channel, the power iterates generated by FM will be random variables and may fail to converge altogether. Even when FM does converge, it will at best, under uncertain conditions of the channel, converge to a stationary distribution [START_REF] Zhou | A stochastic stability characterization of the foschini-miljanic algorithm in random wireless networks[END_REF]), as opposed to a deterministic power vector, which is more desirable. This reveals two main drawbacks of FM. First, as mentioned previously, convergence to a limiting stationary distribution is not the most desired case. Consequently, when operating in a stochastic and time-varying channel, FM is not very stable. As alluded to before, the fact that FM uses only the last power iterate is the reason that such stochastic stability type of results is the best one can hope for on FM. Second, even when FM converges to a stationary distribution, it is not clear what performance guarantees are achieved by that limiting power distribution. Specifically, the stationary distribution that FM converges to is not optimal in any sense.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

The above two drawbacks lead to the problem of designing a distributed power control algorithm that has both stability and performance guarantees. More specifically, in light of the root cause of the instability of FM, it is natural to ask whether it is possible to incorporate all the past power iterates to synthesize a distributed power control scheme so as to stabilize the power iterate more quickly, such that the resulting power iterate converges (almost surely) to a fixed vector even in the presence of a stochastic and time-varying channel? If so, would this vector be optimal in some (average) sense? As we shall see in the next section, both questions have affirmative answers.

Power Control via Dual Averaging

In this section, we present two new and closely-related distributed power control algorithms that utilize all the power iterates in the past to achieve better stability and optimality guarantees. The design of such a distributed algorithm (that uses past information) faces at least two challenges.

First, such an algorithm cannot assume that each transmitter has access to the power used by all the other transmitters, as such communications is infeasible in practice. This dictates that a transmitter can only use the aggregate information, such SINR and/or total interference and noise (i.e. information that can be sensed by each individual link) as opposed to the exact individual powers. Second, more stringently, one should not expect a transmitter to store all the past information that is available to it, which could include its own past transmission powers, past SINRs etc. This additional constraint, if met, can be highly desirable in practice because for a memoryconstrained wireless transmitter, such bookkeeping is in general infeasible. This second constraint further implies that an economic representation that incorporates all such information is needed.

Here we propose the dual averaging power control algorithm that satisfies those two constraints.

The dual averaging algorithm has two variants, which we call Variant A and Variant B. For each variant, the past information is represented and stored in the most economic form possible: it takes only constant amount of memory independent of time steps. For ease of exposition, and to highlight the specific modeling assumptions, we break the discussion into two cases: one where the channel is deterministic and time-invariant, the other where the channel is stochastic and time-varying.

However, each variant of the dual averaging stays the same (except for the slight difference on the notation) across different environments.

Deterministic and Time-Invariant Channel

Here we present the dual-averaging algorithms for the case where the channel (G, η) is deterministic and time-invariant. Algorithm 2 provides a formal description of variant A of dual averaging.

Algorithm 2 Dual Averaging Variant A: Deterministic and Time-Invariant Channel 1: Each link i chooses an initial y 0 i ∈ R.

2: for t = 0, 1, 2, . . . do 3:

for each link i do 4:

p t i = Π P i (y t i )
5:

y t+1 i = y t i -1 t+1 (G ii p t i -r * i ( j =i G ij p t j + η i )) 6:
end for 7: end for Remark 1. Several remarks are in order. First, note that y t i 's serve to fulfill the role of keeping a compact representation that aggregates all the past information at any given time t, thereby eliminating the need to keep track of the past p t 's. Second, as we shall see and make precise in Section 5, each y t i is the weighted average of the gradients of a certain cost function. Consequently, y t (the vector of all individual y t i 's) resides in the dual space of the space P of possible transmission power; hence the name "dual averaging". In fact, Line 4 shows that the projection transforms a point in this dual space to a point in the action space (i.e. P). In particular, while P is a bounded set, the dual space that y t is the whole R N . Finally, note that to perform the update in Line 5

does not require transmitter i to know the transmission powers used by others: it need only know the interference and noise as a whole as well the SINR.

We now give the description of Variant B in Algorithm 2: the only difference lies in updating the discounted gradient y t i . All the points in Remark 1 apply to this variant except the last one: note that in Variant B, only the SINR j =i G ij p t j +η i G ii p t i is needed, because from this SINR and p t i , the ratio

j =i G ij p t j +η i G ii
can be recovered. Consequently, the requirement to implement Variant B is even less Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!) stringent than that of Variant A. However, as we shall see in later (Theorem 7), Variant B needs slightly stronger assumption on the channel gains for convergence and optimality.

Algorithm 3 Dual Averaging Variant B: Deterministic and Time-Invariant Channel 1: Each link i chooses an initial y 0 i ∈ R.

2: for t = 0, 1, 2, . . . do 3:

for each link i do 4:

p t i = Π P i (y t i )
5:

y t+1 i = y t i -1 t+1 (p t i -r * i j =i G ij p t j +η i G ii ) 6:
end for 7: end for

Stochastic and Time-Varying Channel

Next we present the two variants of the dual averaging algorithm for the stochastic and timevarying channel case. Before stating the algorithm, we shall first present the model of the stochastic and time-varying channel within which the algorithm will operate. We adopt the same stochastic model of a wireless network channel as in [START_REF] Zhou | A stochastic stability characterization of the foschini-miljanic algorithm in random wireless networks[END_REF]:

Assumption 1. (G t , η t ) is drawn iid from an arbitrary (discrete or continuous, bounded or unbounded) support on R N ×N + × R N
+ , satisfying the following assumptions:

1. Finite mean: ∀i, j, ∀t, E[G t ij ] < ∞, E[η t i ] < ∞. 2. Finite variance: ∀i, j, ∀t, Var[G t ij ] < ∞, Var[η t i ] < ∞.
Note that under this model, (G t ij , η t k ) can be arbitrarily correlated with (G t i j , η t k ) and G t can be correlated with η t . Algorithm 4 gives the description of Variant A in the stochastic and timevarying channel case. Here we use the upper case for gradient and power to highlight the fact that all the quantities are now random variables.

Continuing with the same notation, we next give the description of Variant B as follows.

Algorithm 4 Dual Averaging Variant A: Stochastic and Time-Varying Channel 1: Each link i chooses an initial Y 0 i ∈ R.

2: for t = 0, 1, 2, . . . do 3:

for each link i do 4:

P t i = Π P i (Y t i ) 5: Y t+1 i = Y t i -1 t (G t ii P t i -r * i ( j =i G t ij P t j + η t i )) 6:
end for 7: end for Algorithm 5 Dual Averaging Variant B: Stochastic and Time-Varying Channel 1: Each link i chooses an initial Y 0 i ∈ R.

2: for t = 0, 1, 2, . . . do 3:

for each link i do 4:

P t i = Π P i (Y t i ) 5: Y t+1 i = Y t i -1 t (P t i -r * i j =i G t ij P t j +η t i G t ii ) 6:
end for 7: end for

Online Gradient Descent Learning in Continuous Games

In this section, we present the framework of online gradient descent (OGD) learning on continuous games that both serves as the foundation for the game-design approach of power control and enables us to subsequently establish (in Section 5 and Section 6) the theoretical guarantees of dual averaging power control algorithms in both the constant and time-invariant channel and the stochastic and time-varying channel. For both simplicity and direct applicability to the power control application, the presentation here will be on the simplest setting needed: the action set of each player is assumed to lie in R. However, all the results in this section generalize in a straightforward manner to the settings where each player's underlying action set is some finite dimensional real vector space. Wherever possible, we shall use the notation that matches the power control setting to make explicit the connection between OGD learning on concave games and power control as well as to ease the subsequent transition from the former to the latter.

λ-Monotone Games

We start with the definition of a λ-Monotone game, which will set the stage for both the theoretical study in this section and the practical design and application for the subsequent sections.

Definition 4. A continuous game G is a tuple G = (N , X = N i=1 X i , {u i } N i=1
), where N is the set of N players {1, 2, . . . , N }, X is the joint action space with X i being the action space for player i and u i : X → R is the utility function for player i, such that the following assumptions hold:

1. Each X i is a compact and convex subset of R.

2. Each u i is continuous in x and continuously differentiable in x i and ∂u i (x)

∂x i is continuous in x.
Throughout the paper, x -i denotes the joint action of all players but player i. Consequently, the joint action x will frequently be written as (x i , x -i ). Further, we denote v(x) to be the column vector of partial derivatives of the utility functions:

v(x) = (v 1 (x), . . . , v N (x)), where v i (x) ∂u i (x) ∂x i .
Note that per the definition of a continuous game (Definition 4), the gradient v(x) always exists and is a continuous function on the joint action space X .

Definition 5. A continuous game G = (N , X = N i=1 X i , {u i } N i=1
) is called λ-monotone for some λ ∈ R N ++ if the following holds (with equality if and only if x = y):

N i=1 λ i (v i (x) -v i (y))(x i -y i ) ≤ 0, ∀x, y ∈ X . (6)
Condition given in Equation ( 6) is essentially the diagonal stricty concavity condition first introduced in Rosen (1965b). Note that this condition necessarily implies that all utility functions u i are concave. In the special case that λ = 1, we simply say the game is monotone. We use the terminology monotone because when λ = 1, this condition is equivalent to that v(x) is a monotone operator, a key concept in variational analysis [START_REF] Rockafellar | Variational analysis[END_REF]. Next, we recall the definition of a Nash equilibrium, a key quantity that will concern us for the rest of the paper.

Definition 6. Given a continuous game G = (N , X = N i=1 X i , {u i } N i=1 ), x * ∈ X is called a Nash equilibrium if for each i ∈ N , u i (x * i , x * -i ) ≥ u i (x i , x * -i ), ∀x i ∈ X i .
The celebrated result established in Rosen (1965b) is that there is always a unique Nash equilibrium for every λ-monotone game:

Theorem 3. (Rosen) A λ-monotone game G = (N , X = N i=1 X i , {u i } N i=1
) admits a unique Nash equilibrium x * .

Rosen (1965b) also gives a convenient sufficient condition ensuring that a continuous game is λ-monotone, a condition that is used later to establish that the designed games are λ-monotone.

Lemma 1. Given a continuous game G = (N , X = N i=1 X i , {u i } N i=1 )
, where each u i is twice continuously differentiable. For each x ∈ X , define the λ-weighted Hessian matrix H λ (x) as follows:

H λ ij (x) = 1 2 λ i ∂v i (x) ∂x j + 1 2 λ j ∂v j (x) ∂x i . (7)
If H λ (x) is negative-definite for every x ∈ X , then G is λ-monotone.

Online Gradient Descent: Perfect and Imperfect Information

When players play a repeated game with each stage game being a fixed continuous game, it is an interesting question as to what learning dynamics the players would adopt. A well-known class of learning dynamics that enjoys the no-regret property (see [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] for a precise formulation and proof) when the utility function is concave is online gradient descent 6 (OGD), as presented below:

Several comments are in order here. First, y t i can be seen as an auxiliary (dual) variable that accumulates gradient steps discounted by the step-size sequence {α t } ∞ t=1 ; the chosen actions are then given by the (lazy) projection of y t i onto X i . As for the step-size sequence α t , Algorithm 7 can be run with any positive, non-increasing sequence that satisfies the widely used non-summablebut-square-summable (" 2 -1 ") condition below:

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Algorithm 6 Online Gradient Descent under Perfect Information 1: Each player i chooses an initial y 0 i .

2: for t = 0, 1, 2, . . . do 3:

for i = 1, . . . , N do 4:

x t i = arg min x i ∈X i y t i -x i 5:

y t+1 i = y t i + α t v i (x t ) 6:
end for 7: end for Definition 7. A positive and non-increasing sequence {α t } ∞ t=0 is called slowly vanishing if

∞ t=0 α t = ∞ and ∞ t=0 (α t ) 2 < ∞.
We can further generalize OGD to allow for imperfect information, where an exact gradient is not available. Algorithm 7 gives a formal description of this generalized version. The main difference between Algorithm 7 and Algorithm 6 lies in Step 5, where only a noisy gradient is available. In addition, the iterates are capitalized to make explicit the fact that due to the noisy gradient used in

Step 5, they are now random variables. Specifically, we have used the capital letters X t i and Y t i in Algorithm 7 because these iterates are now random variables as a result of the noisy gradients ṽi .

Of course, in order for convergence to be guaranteed, ṽi (X t ) cannot be just any noisy perturbation of the gradient. Here we make a rather standard assumption on the noisy gradient:

Algorithm 7 Online Gradient Descent under Imperfect Information 1: Each player i chooses an initial Y 0 i .

2: for t = 0, 1, 2, . . . do 3:

for i = 1, . . . , N do 4:

X t i = arg min X i ∈X i Y t i -X i 5: Y t+1 i = Y t i + α t ṽi (X t ) 6:
end for 7: end for Assumption 2. Let F t be the canonical filtration induced by the (random) iterates up to time t:

X 0 , X 1 , . . . , X t . We assume:

1. The noisy gradients are conditionally unbiased:

∀i ∈ N , ∀t = 0, 1, . . . , E[ṽ i (X t ) | F t ] = v i (X t ), a.s.. (8)
2. The noisy gradients are bounded in mean square:

∀i ∈ N , ∀t = 0, 1, . . . , E[ ṽi (X t ) 2 | F t ] ≤ V, a.s., (9)
for some constant V > 0, where • is some finite dimensional norm (note that all finite dimensional norms are equivalently up to a multiplicative constant).

Remark 2. An equivalent and useful characterization of Assumption 2 is that the noisy gradient can be decomposed as ṽi

(X t ) = v i (X t ) + ξ t+1 i
, where the noise ξ t = (ξ t i ) N i=1 satisfies:

1. ∀t = 0, 1, . . . , E[ξ t+1 | F t ] = 0 (a.s.). 2. ∀t = 0, 1, . . . , E[ ξ t+1 ) 2 | F t ] ≤ Ξ (a.s.).

λ-Fenchel Coupling

We now introduce an important notion, λ-Fenchel coupling, that will serve as an energy function and will play a indispensable role in establishing the convergence of the OGD dynamics. For ease of exposition, we will directly define λ-Fenchel coupling in the current continuous game context (where each X i is a subset of R), although it shall be instantly clear that one can easily extend it to more general contexts where each X i is a finite dimensional real vector space.

We begin with some basic definitions and notation:

Definition 8. Let G = (N , X = N i=1 X i , {u i } N i=1
) be a continuous game and, for each player i, let

h i (x i ) = 1 2 x i 2 (10)
denote the Euclidean squared norm on X i . Then:

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

1. The convex conjugate h * i : R → R of h i is defined as:

h * i (y i ) = max x i ∈X i { y i , x i -h i (x i )} for all y i ∈ R. (11)
2. The choice function C i : R → X i for player i is defined as the (lazy) projection map

C i (y i ) = arg min x i ∈X i x i -y i = arg max x i ∈X i { y i , x i -h i (x i )} for all y i ∈ R. ( 12
)
3. The λ-Fenchel coupling F λ : X × R N → R is defined as:

F λ (x, y) = N i=1 λ i (h i (x i ) + h * i (y i ) -y i , x i ), ∀x ∈ X , ∀y ∈ R N . ( 13
)
Remark 3. Two things worth noting is that although the domain of h i is X i ⊂ R, the domain of its conjugate h * i is R. Further, since h i is proper, lower semi-continuous and convex, it follows that (h * i ) * = h i (Theorem 11.1 in Rockafellar and Wets ( 2009)), a result to be used later. Second, The choice function C i projects y i from the gradient space to x i in the decision space, and corresponds to Line 4 in both Algorithm 6 and Algorithm 7.

The two key properties of λ-Fenchel coupling that will be useful later are:

Lemma 2. For all i ∈ {1, . . . , N }, and all x ∈ X , ỹ, y ∈ R N , we have:

1. F λ (x, y) ≥ 1 2 N i=1 λ i C i (y i ) -x i 2 i ≥ 1 2 (min i λ i ) N i=1 C i (y i ) -x i 2 i . 2. F λ (x, ỹ) ≤ F λ (x, y) + N i=1 λ i ( ỹi -y i )(C i (y i ) -x i ) + 1 2 (max i λ i ) N i=1 ( ỹi -y i i ) 2 .
Remark 4. Collecting each individual choice map into a vector, we obtain the aggregate choice map C : R N → X , with C(y) = (C 1 (y 1 ), . . . , C N (y N )). Since each space X i is normed, we can define the induced aggregate norm • on the joint space X as x = N i=1 x i i . Henceforth, it shall be clear that the convergence in the joint space (e.g. C(y t ) → x, y t → y) will be defined under the respective aggregate norm.

Convergence of Online Gradient Descent with Perfect Information

In this subsection, we tackle the problem of convergence of OGD when the perfect gradient information is available (i.e. v i (x t ) is known exactly in Step 5 of Algorithm 6). Our main result here is that when a given continuous game is λ-monotone, then OGD given in Algorithm 6 converges to the unique Nash equilibrium.

Theorem 4. Let G = (N , X = N i=1 X i , {u i } N i=1
) be a λ-monotone game with the unique Nash equilibrium x * . If the step-size sequence α t of Algorithm 6 is slowly vanishing, the OGD sequence of play x t converges to x * for any initial condition y 0 .

Since this theorem is a special case 7 of Theorem 5, we will defer its proof to that of Theorem 5.

Almost Sure Convergence of Online Gradient Descent under Imperfect Information

In this subsection, we tackle the even harder problem of convergence of OGD under imperfect information, i.e. when an exact gradient is not known but, instead, only a noisy gradient ṽi (x t ) is available in Step 5 of Algorithm 7). Our main result here is that, when a given continuous game is λ-monotone, OGD given in Algorithm 7 converges to the unique Nash equilibrium almost surely.

Mathematical Preliminaries

We begin by collecting in one place the minimal set of definitions and results that will be used later to prove the almost-sure convergence result. The first two came from [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF].

Definition 9. A semiflow φ on a metric space (M, d) is a continuous map φ : R + × M → M :

(t, x) → φ t (x), such that the semi-group properties hold: φ 0 = identity, φ t+s = φ t • φ s for all (t, s) ∈ R + × R + .

Remark 5. A standard way to induce a semiflow is via an ordinary differential equation (ODE).

Specifically, as mentioned in [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF], if F : R m → R m is a continuous function and if the following ODE has a unique solution trajectory for each initial point x ∈ R m :

dx dt = F (x),
x(0) = x, then φ t (x) defined by the solution trajectory x(t) ∈ R m as follows is a semiflow: φ t (x) x(t) with

x(0) = x. We say φ defined in this way is the semiflow induced by the corresponding ODE.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Definition 10. Let φ be a semiflow on the metric space (M, d). A continuous function s : R + → M is an asymptotic pseudotrajectory for φ if for every T > 0, the following holds:

lim t→∞ sup 0≤h≤T d(s(t + h), φ h (s(t))) = 0. ( 14
)
Remark 6. Per its definition, when s is an asymptotic pseudotrajectory for φ, s and φ are very close for sufficiently large t. Specifically, for each fixed T > 0, one can find a large enough t 0 , such that ∀t > t 0 , the curve s(t + h) approximates the trajectory φ h (s(t)) on the interval h ∈ [0, T ] with any pre-specified degree of accuracy. A more thorough discussion on asymptotic pseudotrajectory can be found in Bena [START_REF] Ïm | Asymptotic pseudotrajectories and chain recurrent flows, with applications[END_REF].

Convergence Analysis

We now turn to the main convergence result.

Theorem 5. Let G = (N , X = N i=1 X i , {u i } N i=1
) be λ-monotone with the unique Nash equilibrium

x * . If the following conditions are satisfied:

1. Assumption 2 holds.

Each

v i (x) is Lipschitz continuous in x on X .
3. The step size sequence {α t } ∞ t=0 in Algorithm 6 is slowly vanishing.

then the OGD sequence of play X t converges to x * almost surely, for any initial condition Y 0 .

Remark 7. For clarity, we break the proof into several steps.

1. Let B(x * , ) {x ∈ X | xx * < } be the open ball centered around x * with radius . We

show that any open ball around x * is recurrent. Mathematically, for any > 0 and any initial point y 0 , the iterate X t visit B(x * , ) infinitely often almost surely. Further, fix any δ > 0 and

consider the set B(x * , δ) {C(y) | F λ (x * , y) < δ}. Although F λ (x * , y) is not a metric, B(x * , δ)
contains an open ball within it. Mathematically, the claim is that for any δ > 0, ∃ (δ) > 0 such that: B(x * , ) ⊂ B(x * , δ). Putting the above two pieces together, it follows that for any δ > 0, X t must almost surely visit B(x * , δ) infinitely often, irrespective of the initial point.

2. Next we consider the ordinary differential equation (ODE) approximation of OGD as follows:

ẏ = v(x), x = C(y).
Note that this can be written as ẏ = v(C(y)), which we can then verify that it admits a unique solution trajectory for any given initial condition. Consequently, per Remark 5, this solution induces a semiflow 8 , which we denote φ t (y): it is the state at time t given it starts at y initially. Note that we have used y as the initial point (as opposed to y 0 ) to indicate that the semiflow representing the solution trajectory should be viewed as a function of the initial point y.

3. We now relate the iterates generated by OGD to the above ODE's solution. First, we con-

nect linearly the OGD iterates Y 0 , Y 1 , Y 2 , . . . , Y k , . . . at times 0, α 0 , α 0 + α 1 , . . . , k-1 i=0 α i , . . .
respectively to form a continuous, piecewise affine curve. Namely:

Y (t) = Y k + (t - k-1 i=0 α i ) Y k+1 -Y k α k , for t ∈ [ k-1 i=0 α i , k i=0 α i ), k = 0, 1, . . . ,
where we adopt the usual convention that the latter (the semiflow given by the ODE trajectory). A desirable property of φ t (y) is that the distance F λ (x * , φ t (y)) between the primal variable x * and the dual variable φ t (y)) (as measured by the Lyapunov function λ-Fenchel coupling) can never increase as a function of t.

We refer to this as the monotonicity property of λ-Fenchel coupling under the ODE trajectory, to be contrasted to the discrete-time dynamics, where such monotonicity is absent (even when perfect information on the gradient is available). More formally, we show that ∀y, ∀0 ≤ s ≤ t,

F λ (x * , φ s (y)) ≥ F λ (x * , φ t (y)). ( 15
)
Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

5. Continuing on the previous point, not only the distance F λ (x * , φ t (y)) can never increase as t increases, but also, provided that φ t (y) is not too close to x * (under the λ-Fenchel coupling divergence measure), F λ (x * , φ t (y)) will decrease no slower than linearly. This suggests that either φ t (y) is already close to x * (and hence x(t) = C(φ t (y)) is close to x * ), or their distance will be decreased by a meaningful amount in (at least) the ensuing short time-frame. We formalize this discussion into the following mathematical claim: ∀ > 0, ∀y, ∃s > 0, such that: should also be small on the entire interval h ∈ [0, T ], if λ-Fenchel coupling has a regular enough structure. It turns out that this is indeed the case. This can be made precise as follows:

F λ (x * , φ s (y)) ≤ max{ 2 , F λ (x * , y) -2 }. (
∀ , T > 0, ∃τ ( , T ) > 0 such that ∀t ≥ τ, ∀h ∈ [0, T ]: thereby establishing that, at least for t large enough, if F λ (x * , Y (t)) is small, then F λ (x * , Y (t+ h)) will remains small ∀h > 0. As it turns out, this means that after long enough time, if X t ever visits B(x * , ), it will (almost surely) be forever trapped inside the neighborhood twice that size (i.e. B(x * , 2 )). Since Claim 1 ensures that X t visits B(x * , ) infinitively often (almost surely), the hypothesis is guaranteed to be true. Consequently, this leads to the following formal claim: ∀ > 0, ∃τ 0 (a positive integer), such that:

F λ (x * , Y (t + h)) < F λ (x * , φ h (Y (t))) + 2 , a.s.. ( 17
F λ (x * , Y (τ 0 + h)) < , ∀h ∈ [0, ∞), a.s.. ( 18
)
To conclude, Equation ( 18) in Claim 7 implies that F λ (x * , Y t ) → 0, a.s. as t → ∞, where the OGD iterates Y t are values at integer time points of the affine trajectory Y (τ ). Per Statement 1 in Lemma 2, this leads to that C(Y t ) -x * → 0, a.s. as t → ∞, thereby establishing that

X t = C(Y t ) → x * , a.s. as t → 0.

Theoretical Guarantees of Dual Averaging Power Control: Deterministic and Time-Invariant Channels

In this section, we establish the theoretical guarantees of the two variants of the dual averaging power control algorithm in the deterministic and time-invariant channel case. Our approach lies in designing two λ-monotone games such that each variant of the dual averaging algorithm can be interpreted as a special instance of the OGD learning dynamics for the corresponding game.

We emphasize that it is not the case that the transmitters are playing a repeated game where their utilities are prescribed by the designed function. Instead, this is merely used as an analytical framework to study the proposed algorithms. In fact, this is the analytical framework we use to design and derive the dual averaging power control algorithms in the first place.

Designed λ-Monotone Games

Under the notation introduced in Section 2, we consider the following two games G 1 , G 2 as given below, where the set N of players is the set of links in the power control contexts:

1. G 1 = (N , P, {u i } N i=1 ), where

u i (p) = - 1 2G ii (G ii p i -r * i ( j =i G ij p j + η i )) 2 . ( 19
) 2. G 2 = (N , P, {ũ i } N i=1 ), where ũi (p) = - 1 2G 2 ii (G ii p i -r * i ( j =i G ij p j + η i )) 2 . ( 20
)
We first point out an interesting feature shared by both of these games when the channel is feasible: per Fact 1, a (necessarily unique) optimal joint transmission power p * exists. Since the optimal joint transmission power matches the quality-of-service constraints exactly, every player's

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

utility will be 0 if they transmit according to p * . This implies that p * must be a Nash equilibrium, since 0 is the highest utility that can be possibly achieved for any given player (link). In fact, at p * , not only will any player fail to obtain better utility by unilaterally deviating from p * , the players cannot achieve better utility through collusion of any type. Furthermore, p * is the unique Nash equilibrium, because if p were any other Nash equilibrium, then necessarily one player's utility is below 0. For this player, he will have the incentive to transmit at a higher power compared to the current prescribed transmission power so as to achieve better utility.

The preceding discussion essentially establishes that when the channel is feasible, both of these games admit a unique Nash equilibrium p * , which is the optimal joint transmission power. However, it still remains a question as to whether they are λ-monotone. The following lemma presents a rather intriguing result: the feasibility of the channel not only guarantees the existence of a unique Nash equilibrium, but also, more importantly, implies that both games are λ-monotone.

Lemma 3. Fix λ = ( 1 G 11 , 1 G 22 , . . . , 1 G N N ).
Assume that the channel (G, η) is feasible and thereby let p * be the optimal joint transmission power as defined in Definition 3, where p * is assumed to lie in P. The the following statements hold:

1. The designed game G 1 = (N , P, {u i } N i=1 ) is a λ-monotone game with the unique Nash equilibrium p * .

2. The designed game G 2 = (N , P, {ũ i } N i=1 ) is a monotone game with the unique Nash equilibrium p * .

Proof: We first establish the first statement. For each i:

v i (p) = ∂u i (p) ∂p i = -(G ii p i -r * i ( j =i G ij p j + η i )), (21)
which can be easily seen as affine in p i and hence concave, with all the smoothness assumptions satisfied. For each i, j:

∂v i (p) ∂p i = -G ii , ∂v i (p) ∂p j = r * i G ij .
Computing the λ-weighted Hessian matrix of the designed game, we obtain:

H λ ij (p) = 1 2G ii ∂v i (p) ∂p j + 1 2G jj ∂v j (p) ∂p i . If i = j, then H λ ii (p) = 2 × 1 2G ii ∂v i (p) ∂p i = -1. If i = j, then H λ ij (p) = 1 2G ii r * i G ij + 1 2G jj r * j G ji = 1 2 (r * i G ij G ii + r * j G ji G jj ).
Let W be the re-weighted gain matrix as defined in Equation 3 and I ∈ R N ×N be the identity matrix. From the previous calculations, it follows that

H λ = 1 2 (W -I) + 1 2 (W T -I).
Since the channel (G, η) is feasible, per Theorem 1, λ max (W ) < 1. Consequently, (W -I) is negative definite (although not necessarily symmetric, i.e. may have complex eigenvalues):

∀p ∈ R N , p(W -I)p = pW p -p 2 ≤ (λ max (W ) -1) p 2 < 0. Similarly, (W T -I) is negative definite, thereby implying H ij (p) is negative definite. Since H ij (p)
is negative definite for every p (since it is independent of p), Lemma 1 establishes that the game is λ-monotone.

Since p * results the maximum utility for every player: u i (p * ) = 0, p * must be a Nash equilibrium and hence the unique Nash equilibrium.

Statement 2 follows by a similar argument by noting that in this case,

v i (p) = ∂ ũi (p) ∂p i = -(p i -r * i j =i G ij p j + η i G ii ). ( 22
)
Computing the β-weighted Hessian for β = (1, 1, . . . , 1) yields:

H β = 1 2 (W -I) + 1 2 (W T -I),
thereby establishing the conclusion.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Convergence of Dual Averaging in the Power Control Problem

With the above two designed games, we can now connect the dual averaging power control algorithms to the OGD learning dynamics, as made precise by the following lemma.

Lemma 4. Variant A of dual averaging (Algorithm 2) and Variant B of dual averaging (Algorithm 3) are OGD (Algorithm 6) for the designed games (N , P, {u i } N i=1 ) and (N , P, {ũ i } N i=1 ) respectively, where

1. h i (p i ) = 1 2 p 2 i .
2. α t = 1 t+1 .

Proof: First, note that it is a standard result in convex analysis that h i (p i ) = 1 2 p 2 i is 1-strongly convex with respect to the Euclidean 2-norm and that the corresponding choice map C i (y i ) is simply the closest-point projection:

C i (y i ) = arg max p i ∈P i {p i y i -1 2 p 2 i } = Π P i (y i ).
The lemma therefore follows by noting that ∂u i (p)

∂p i = -(G ii p i -r * i ( j =i G ij p j + η i )) and ∂ ũi (p) ∂p i = -(p i -r * i j =i G ij p j +η i G ii
).

Combining all the pieces together, we therefore have the following convergence and optimality guarantees for dual averaging power control:

Theorem 6. Let the channel (G, η) be feasible with the optimal joint transmission power p * ∈ P.

1. p t → p * as t → ∞, where p t is given in Algorithm 2.

2. p t → p * as t → ∞, where p t is given in Algorithm 3.

Proof: Per Lemma 4, Algorithm 2 is OGD for the game (N , P, {u i } N i=1 ) and Algorithm 3 is OGD for the game (N , P, {ũ i } N i=1 ), where

α t = 1 t+1 and h i (p i ) = 1 2 p 2 i . Note that the sequence { 1 t+1 } ∞ t=0 is
clearly slowly vanishing. The two results follow immediately from Theorem 4.

Theoretical Guarantees of Dual Averaging Power Control: Stochastic and Time-Varying Channels

In this section, we establish the theoretical guarantees of the two variants of the dual averaging power control algorithm in the stochastic and time-varying channel case. Our approach again lies in designing two λ-monotone games, which build on the ones presented in the previous section.

Designed Concave Games

Note that in a stochastic and time-varying channel, (G, η) (or (W, γ)) is random. We consider the following two games G 1 , G 2 as given below, where the set N of players is again the set of wireless links in the power control contexts:

1. G 1 = (N , P, {u i } N i=1 ), u i (p) = E[-1 2G ii (G ii p i -r * i ( j =i G ij p j + η i )) 2 ]. 2. G 2 = (N , P, {ũ i } N i=1 ), ũi (p) = E[-1 2G 2 ii (G ii p i -r * i ( j =i G ij p j + η i )) 2 ].
Under the above two designed games, it is straightforward to verify that

∂u i (p) ∂p i = -E[(G ii p i -r * i ( j =i G ij p j + η i ))] = -(E[G ii ]p i -r * i ( j =i E[G ij ]p j + E[η i ])), (23)
∂ ũi (p) ∂p i = -E[(p i -r * i j =i G ij p j + η i G ii )] = -(p i -r * i j =i (E[ G ij G ii ]p j +E[ η i G ii ])) = -(p i - j =i (E[W ij ]p j +E[γ i ])). (24)
Before, we move on to establish the theoretical guarantees for dual averaging in the stochastic and time-varying channel case, we need a notion that characterizes the channel feasibility in this case. Since the channel is fluctuating, it would be too strong to require that each channel realization on any given time step is feasible. Instead, here we only impose the mild requirement that a channel is mean feasible: the channel can be feasible sometimes and infeasible some other times as long as it is feasible on average. The next definition formalizes it:

Definition 11. A channel (G, η) (or equivalently (W, γ)) is:

1. Type-I mean-feasible if (E[G], E[η]
) is feasible, where expectation is taken component-wise.

Type-II mean-feasible if (E[W ], E[γ]

) is feasible, where expectation is taken component-wise.

The two types of mean-feasible channels are closely related: although in general neither implies the other, in the important special case that G ij 's are independent of G ii , Type-I mean-feasible is weaker than Type-II mean-feasible, as formalized by the following lemma:

Lemma 5. If for each i ∈ {1, 2, . . . , N }, G ij and G ii are pairwise independent for each j = i, then a channel that is Type-II mean-feasible is Type-I mean-feasible.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Proof: Let a channel (G, η) be Type-II mean-feasible. Defined the matrix W to be:

Wij :=          0, i = j r * i E[G ij ] E[G ii ] , i = j. (25)
We have:

E[ G ij G ii ] = E[G ij ]E[ 1 G ii ] ≥ E[G ij ] E[G ii ] , (26)
where the equality follows from independence and the inequality follows from Jensen's inequality and the fact that f (x) = 1 x is convex when x is positive. This immediately implies:

E[W ] ≥ W ,
where inequality holds component-wise. Since each entry in both matrices is non-negative, we have:

λ max (E[W ]) = max u∈R N : u 2 =1 uE[W ]u = max u∈R N + : u 2 =1 uE[W ]u, λ max ( W ) = max u∈R N + : u 2 =1 u W u = max u∈R N + : u 2 =1 u W u.
Further, for each u ∈ R N + , Equation (26) implies uE[W ]u ≥ u W u, which then leads to

λ max (E[W ]) = max u∈R N + : u 2 =1 uE[W ]u ≥ max u∈R N + : u 2 =1 u W u = λ max ( W ).
By Theorem 1, λ max ( W ) < 1 and hence the channel must be Type-I mean-feasible.

Almost Sure Convergence of Dual Averaging Power Control: Stability and Optimality

We are now ready for the main result for the stochastic and time-varying channel case. We obtain this result by casting the dual averaging power control algorithms in the OGD learning framework.

Theorem 7. Given a stochastic and time-varying channel (G, η) (or equivalently (W, γ)) according to Assumption 1.

1. If the channel is Type-I mean feasible, with p * ∈ P being the optimal joint transmission power for (E[G], E[η]), then P t → p * almost surely, as t → ∞, where P t is given in Algorithm 4.

2.

If the channel is Type-II mean feasible, with p * ∈ P being the optimal joint transmission power for (E[W ], E[γ]) and for each i, there exists some g i > 0 such that G ii ≥ g i a.s., then P t → p * almost surely, as t → ∞, where P t is given in Algorithm 5.

Remark 8. Two things to note here. First, the almost sure convergence to a constant joint transmission power in the presence of persistent stochastic channel fluctuations is a manifestation of the stability of dual averaging. The intuition behind this stability is that as past powers are incorporated into the current power via a weighted sum, the random environments have less and and less impact on the current power iterate because the step-sizes are decreasing. Second, G ii ≥ g i a.s. is a rather mild assumption as it means that power gain between each transmitter and its intended receiver is lower bounded by some positive constant.

Proof: For the first claim, per Assumption 1, we can write

G t ij = E[G ij ] + Gt ij , η t i = E[G ij ] + ηt i
, where Gt ij and ηt i are both sequences of iid, zero-mean and finite-variance random variables.

Consequently, the gradient update (Line 5) in Algorithm 4 can be equivalently written as: is still linear under expectation. Condition 3 was already verified in the proof to Theorem 6. The result therefore follows.

Y t+1 i = Y t i - 1 t (E[G ii ] + Gt ii )P t i -r * i ( j =i (E[G ij ] + Gt ij )P t j + E[η i ] + ηt i ) (27) = Y t i - 1 t E[G ii ]P t i -r * i ( j =i E[G ij ]P t j ) + E[η i ] + { Gt ii P t i -r * i j =i Gt ij P t j + ηt i } . ( 28
For the second claim, using the same line of reasoning, it follows that Algorithm 5 is a special case of Algorithm 7. The only thing to note here is that the bounded second moments assumption holds because G ii ≥ g i a.s..

Conclusion

We close with two remarks. First, from a technical standpoint, our result for the almost sure convergence of online gradient descent (OGD) to Nash equilibrium in λ-monotone games was established via a multi-step argument that can be best described in two parts as follows. The first part is to establish the algorithm's recurrence: the game's (necessarily unique) Nash equilibrium is an accumulation point of the sequence of play generated by OGD. The second part is to use a mean-field approximation to push this recurrence result one step further and show that the algorithm does not admit any other accumulation points. Specifically, we do this by a) converting the stochastic discrete process into a deterministic continuous process; b) establishing the convergence of the resulting continuous trajectories; and, finally, c) using a stochastic approximation argument to map this "mean field" convergence back to the discrete process. Even though this general program differs on a case-by-case basis (our case is particularly involved due to the non-invertibility Euclidean projections), the underlying philosophy above has been successfully used in other important applications in operations research, the most notable of which is in queueing networks (see [START_REF] Gamarnik | Fluid models of queueing networks[END_REF] for a landmark survey).

Second, even though our focus in this paper was on power minimization subject to rate constraints, the general "mean field" framework above can be applied to a broad spectrum of other power management (and/or more general game-theoretic) problems. We intend to explore these directions in future work.

Endnotes 1. The literature on power control is too broad to review here; for a comprehensive survey, we refer the reader to [START_REF] Chiang | Power control in wireless cellular networks[END_REF].

2. Feasibility means here that there exists a power allocation vector under which every user's throughput requirements are satisfied.

3. In our case, the algorithm should be ascending the payoff to be maximized, but we use the more standard "descent" terminology to be consistent with the literature.

4. Specifically, a Nash equilibrium profile is a correlated equilibrium, which in turn is in the Hannan set; in general, all these inclusions are proper.

5. As noted in Tan ( 2014), the re-weighted gain matrix W is a non-negative (and without loss of generality, irreducible) matrix; thus by Perron-Frobenius theorem, there is a unique positive real eigenvalue ρ * that has the largest magnitude.

6. To be precise, the version of OGD considered here is called lazy OGD. There is also a variant called eager OGD. Shalev-Shwartz et al. 2012 provides a nice tutorial on the (minor) differences.

Note that the no-regret property holds for both variants; further, they have the same regret bound.

7. Strictly speaking, Theorem 5 has an additional assumption that v be Lipschitz continuous. It turns out that even when this assumption is violated, the result here (i.e. perfect gradient case) still holds, although it requires a different argument (i.e. a non-ODE approach). Due to space limitation and due to that in the application considered here v is indeed Lipschitz, we omit in the current draft this argument.

8. A crucial point to note is that since C is not invertible, there may not exist a unique solution for x(t).

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Appendix. Auxiliary Results and Missing Proofs

A. Martingale Convergence Theorems

We present two martingale convergence theorems that shall be useful later. These are adapted statements that come from [START_REF] Hall | Martingale limit theory and its application[END_REF], which contains detailed proofs. The first one is a law of large number theorem for Martingales.

Theorem 8. Let S t = t k=0 X k be a Martingale adapted to the filtration S t . Let {u t } ∞ t=0 be a nondecreasing sequence of positive numbers with

lim t→∞ u t = ∞. If ∃p ∈ [1, 2] such that ∞ t=0 E[|X t+1 | p |S t ] (u t ) p < ∞,

B. Proof of Lemma 2

For the first statement, note that by a well-known result in convex analysis (see [START_REF] Rockafellar | Convex analysis[END_REF])

when x * i = C i (y i ), it holds that y i is a subgradient of h i at the point x * i : h i (x i ) ≥ h i (x * i ) + y i (x i -x * i
). This then implies that, for any β ∈ (0, 1]:

λ i (h i (x * i ) + y i (β(x i -x * i ))) ≤ λ i h i (x * i + β(x i -x * i )) = λ i h i ((1 -β)x * i + βx i ) ≤ (29) λ i {(1 -β)h i (x * i ) + βh i (x i ) - 1 2 β(1 -β) x i -x * i 2 i }, (30)
where the last inequality follows from the fact that h i is 1-strongly convex.

Connecting the first and the last term of the above inequality chain, we have:

λ i y i β(x i -x * i ) ≤ λ i (-β)h i (x * i ) + λ i βh i (x i ) - 1 2 λ i β(1 -β) x i -x * i 2 i .
Dividing both sides by β (since β > 0) and rearranging, we obtain:

1 2 λ i (1 -β) x i -x * i 2 i ≤ λ i h i (x i ) -λ i h i (x * i ) -λ i y i (x i -x * i ).
Taking the limit that β approaches 0 (from above) results:

λ i h i (x i ) -λ i h i (x * i ) -λ i y i (x i -x * i ) ≥ 1 2 λ i x i -x * i 2 i .
Summing over all i's, we then obtain:

N i=1 {λ i h i (x i ) -λ i h i (x * i ) -λ i y i (x i -x * i )} ≥ N i=1 1 2 λ i x i -x * i 2 i .
The conclusion then follows by noting that:

F λ (x, y) = N i=1 λ i (h i (x i ) -x i y i + h * i (y i )) = N i=1 λ i (h i (x i ) -x i y i + x * i y i -h i (x * i )) (31) ≥ N i=1 1 2 λ i x i -x * i 2 i ≥ 1 2 (min i λ i ) N i=1 C i (y i ) -x i 2 i , (32)
where the last inequality follows by noting that x * i = C i (y i ). For the second statement, we start by citing here a useful result in [START_REF] Rockafellar | Variational analysis[END_REF] (Theorem 12.60): For a proper, lower semi-continuous and convex function f : R n → R and a value σ > 0, f * is σ-strongly convex (with respect to norm • * ) if and only if f is differentiable and satisfies: Next, we note that in our case, each h i is 1-strongly convex with respect to norm • i and per Remark 3, (h * i ) * = h i . Further, it can be easily checked that h * i is proper, lower semi-continuous and convex (since it is a point-wise maximum of affine functions per its definition), it therefore follows that the 1-strong convexity of (h * i ) * (with respect to • * * i = • i ) implies that h * i is differentiable and satisfies:

f (x) ≤ f (x)+ < ∇f (x), x -x) > + 1 2σ x -x 2 , ∀x, x, where R = [-∞, ∞].
h * i ( ỹi ) ≤ h * i (y i ) + (h * i ) (y i )( ỹi -y i ) + 1 2 ( ỹi -y i * i ) 2 , ∀y i , ỹi (33)
= h * i (y i ) + C i (y i )( ỹi -y i ) + 1 2 ( ỹi -y i * i ) 2 , ∀y i , ỹi (34)
where the equality follows because (h * i ) (y i ) = C i (y i ). Therefore, it then follows that upon substituting the preceding inequality for each h

* i ( ỹi ) into F λ (x, ỹ) = N i=1 λ i (h i (x i ) -x i ỹi + h * i ( ỹi ))
, we have:

F λ (x, ỹ) ≤ N i=1 λ i (h i (x i ) -x i ỹi ) + N i=1 λ i {h * i (y i ) + C i (y i )( ỹi -y i ) + λ i 2 ( ỹi -y i * i ) 2 } (35) = N i=1 λ i {h i (x i ) + h * i (y i ) -x i y i + x i (y i -ỹi ) + C i (y i )( ỹi -y i ))} + N i=1 λ i 2 ( ỹi -y i * i ) 2 (36) = F λ (x, y) + N i=1 λ i ( ỹi -y i )(C i (y i ) -x i ) + N i=1 λ i 2 ( ỹi -y i * i ) 2 (37) ≤ F λ (x, y) + N i=1 λ i ( ỹi -y i )(C i (y i ) -x i ) + 1 2 (max i λ i ) N i=1 ( ỹi -y i * i ) 2 . ( 38
)
Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

C. Proof of Theorem 5

We prove in turn each of the 7 claims laid out in Remark 7.

1. Let Y t = (Y t 1 , . . . , Y t N ), X t = (X t 1 , . . . , X t N ) be the iterates generated in Algorithm 7. Fix an arbitrary > 0. Assume for contradiction purposes that X t only visits B(x * , ) a finite number of times and hence let t 0 -1 be the last time X t is in B(x * , ). Set β t = 1 2 (α t ) 2 max i λ i . Using the representation ṽ(X t ) = v(X t ) + ξ t+1 given in Remark 2, we have that ∀t ≥ t 0 : F λ (x * , Y t+1 ) = F λ (x * , Y t + α t ṽ(X t )) = F λ (x * , Y t + α t (v(X t ) + ξ t+1 ))

(39)

≤ F λ (x * , Y t ) + N i=1 λ i (α t (v i (X t ) + ξ t+1 i )(C i (Y t i ) -x * i ) + β t ( ṽ(X t ) * ) 2 (40) = F λ (x * , Y t ) + α t N i=1 λ i v i (X t )(X t i -x * i ) + α t N i=1 λ i ξ t+1 i (X t i -x * i ) + β t ( ṽ(X t ) * ) 2 (41) ≤ F λ (x * , Y t ) + α t b max ( ) + α t N i=1 λ i ξ t+1 i (X t i -x * i ) + β t ( ṽ(X t ) * ) 2 (42) ≤ F λ (x * , Y t 0 ) + ( t k=t 0 α k )b max ( ) + N i=1 (λ i t k=t 0 α k ξ k+1 i (X k i -x * i )) + t k=t 0 β k ( ṽ(X k ) * ) 2 (43) = F λ (x * , Y t 0 ) + ( t k=t 0 α k ) b max ( ) + N i=1 (λ i t k=t 0 α k t k=t 0 α k ξ k+1 i (X k i -x * i )) + t k=t 0 β k ( ṽ(X k ) * (44)
where the last inequality follows from telescoping from k = t 0 to k = t.

Next, note that ∀i = 1, . . . , N ,

t k=t 0 α k ξ k+1 i (X k i -x * i ) is a Martingale adapted to F t+1 because E[α k ξ t+1 i (X t i -x * i )|F t ] = α k (X t i -x * i )E[ξ t+1 i |F t ] = 0.
Furthermore, setting p = 2 and u t = t k=t 0 α k (the first t 0 terms of u t can be set arbitrarily and are not essential), it is clear that u t is increasing and lim t→∞ u t = ∞ by assumption. It then follows that

∞ t=0 E[|α t ξ t+1 i | p | F t ] (u t ) p ≤ ∞ t=0 (α t ) 2 Ξ (u t ) p ≤ Ξ ∞ t=0 (α t ) 2 ( t k=t 0 α k ) 2
< ∞, a.s., where the last inequality follows from the fact that α t is square-summable. Consequently, by Theorem 8, Finally, note that since • * is a norm, S t = t k=t 0 β k ( ṽ(X k ) * ) 2 is a submartingale adapted to F t+1 . We check that S t is l 1 -bounded:

E[S t ] = t k=t 0 β k E[( ṽ(X k ) * ) 2 ] ≤ t k=t 0 β k V < V ∞ k=t 0 β k < ∞, ∀t.
Consequently, by Theorem 9, it follows that S t → S, a.s., t → ∞, with S finite almost surely. This then leads to

( t k=t 0 α k ) b max ( ) + N i=1 (λ i t k=t 0 α k t k=t 0 α k ξ k+1 i (X k i -x * i )) + t k=t 0 β k ( ṽ(X k ) * ) 2 → -∞, a.s., t → ∞.
This further implies that F λ (x * , Y t ) → -∞, a.s., t → ∞, which contradicts the first statement in Lemma 2.

For the second part, assume for contradiction purposes no B(x * , ) is contained in B(x * , δ), which means that for any δ > 0, ∃y l , such that Q(y l ) -x * = δ but F λ (x * , y l ) ≥ . This produces a sequence {y l } ∞ l=0 such that C(y l ) → x * but F λ (x * , y l ) ≥ , ∀l. However, this is a contradiction, because C i (h i ) = Π P i (y i ) and hence h * i (y i ) = Π P i (y i )y i -1 2 (Π P i (y i )) 2 . Consequently, if C(y t ) → p for some p ∈ P, then Π P (y t ) = C(y t ) → p, leading to:

F λ (p, y t ) = N i=1 λ i (h i (p i ) -p i y i + h * i (y i )) = N i=1 λ i ( 1 2 p 2 i -p i y i + Π P i (y i )y i - 1 2 (Π P i (y i )) 2 ) (45) = 1 2 N i=1 λ i (p 2 i -(Π P i (y i )) 2 ) + 1 2 N i=1 λ i y i (Π P i (y i ) -p i ) → 0, (46)
Consequently, the claim follows.

2. Since each h i (•) is 1-strongly convex, h(•) = (h 1 (•), . . . , h N (•)) is 1-strongly convex. By a standard result in convex analysis [START_REF] Rockafellar | Convex analysis[END_REF], C(•) is 1-Lipschitz continuous. Since v is lipschitz continuous by assumption, v(Q(•)) is Lipschitz continuous. Consequently, standard results in differential equations [START_REF] Coddington | Theory of Ordinary Differential Equations[END_REF]) imply that a unique solution exists for the ODE.

3. [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF] gives sufficient conditions that ensure a random trajectory to be an asymptotic pseudotrajectory of a semiflow almost surely. We shall state one set of sufficient conditions directly in the current context as follows.

If for some q ≥ 2, the following list of conditions are satisfied:

(a) sup t E[( ξ t+1 * ) q ] < ∞.

for some positive constant a ˜ .

Starting at y, by time s, there are two possibilities. The first possibility is that x(s) ∈ B(x * , 2 ). In this case, by definition,

F λ (x * , φ s (y)) < 2 . ( 54
)
The second possibility is that x(s) / ∈ B(x * , 2 ). This implies that x(t) / ∈ B(x * , ˆ ), ∀t ∈ [0, s],

because otherwise, since B(x * , ˆ ) ⊂ B(x * , 2 ), it must be that x(s 0 ) ∈ B(x * , 2 ) for some

s 0 ∈ [0, s].

  = 0. We then show that Y (t) (a random trajectory) is almost surely an asymptotic pseudotrajectory of the semi-flow φ induced by the above ODE, under the metric induced by the dual norm • * defined in Remark 4. Mathematically, we establish that ∀T > 0, lim t→∞ sup 0≤h≤T Y (t + h), φ h (Y (t)) * = 0, a.s.. 4. Having characterized the relation between the OGD trajectory (affine interpolation of the discrete OGD iterates) and the ODE trajectory (the semi-flow), we now turn to studying

) 7 .

 7 Finally, we are ready to put the above pieces together. Claim 6 gives us a way to control the amount by which the two λ-Fenchel coupling functions differ on the interval [0, T ]. Claim 4 and Claim 5 together allow us to extend such control over successive intervals [T, 2T ), [2T, 3T ), . . . ,

  i -x * i )) → 0, a.s., t → ∞. Since ∞ k=t 0 α k = -∞, we therefore have ( * i )) → -∞, a.s., t → ∞.

  Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)of this literature has focused on the convergence of the time-averaged sequence of play xt = (where γ t is the step-size and x t is the joint action at time t) as opposed to the actual sequence of actions employed by the players. For instance, in the context of

	t k=1 γ k x k / k=1 γ k finite games, it is well-known that if each player employs a no-regret learning algorithm, the t
	time-averaged sequence of play converges to the game's Hannan set, also known as the set
	of coarse correlated equilibria (Cesa-Bianchi and Lugosi 2006). Refining this result, if each
	player plays employs a no-internal-regret learning algorithm (a stronger regret notion), the
	time-averaged sequence of play converges to the game's set of correlated equilibria, a strict
	refinement of Hannan-consistent strategies (Cesa-Bianchi and Lugosi 2006). On the other
	hand, convergence to Nash equilibrium is, in the words of Cesa-Bianchi and Lugosi (2006)

  Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

  16) 6. Now consider an arbitrary fixed horizon T . If at time t, F λ (x * , φ 0 (Y (t))) is small, then by the monotonicity property in Claim 4, F λ (x

* , φ h (Y (t))) will remain small on the entire interval

h ∈ [0, T ]. Since Y (t) is an asymptotic pseudotrajectory of φ (Claim 3), Y (t + h) and φ h (Y (t))

should be very close for h ∈ [0, T ], at least for t large enough. This means that F λ (x * , Y (t + h))

  , . . . , P t ] < ∞, a.s.. Since P is bounded, there exists a constant B > 0 such that , . . . , P t ] ≤ B, a.s., ∀t. Consequently, the martingale noise ξ t satisfies Assumption 2 per Remark 2. This implies that Algorithm 4 is a special case of Algorithm 7. Further, since the channel is Type-I mean feasible, Lemma 3 implies thatG 1 is ( 1 E[G 11 ] , . . . , 1 E[G N N ])-monotone with p * being the unique Nash equilibrium. It therefore suffices to verify the conditions given in Theorem 5 are satisfied. Condition 1 is just verified above as ξ t satisfies Assumption 2. Condition 2 holds v i (p)

					)
	Denoting ξ t+1 i	= Gt ii P t i -r * i	j =i	Gt ij P t j + ηt i , it follows that E[ξ t+1 i	| P 0 , . . . , P t ] = 0, a.s. and
	Var[ξ t+1 i | P 0 Var[ξ t+1 i | P 0

  The second one is Doob's Martingale convergence theorem.Theorem 9. Let S t be a submartingale adapted to the filtration S t , where t = 0, 1, 2, . . . . If S

	a.s. , then
	lim t→∞	S t u t = 0, a.s.,

t is l 1 -bounded: sup t≥0 E[|S t |] < ∞, then S t converges almost surely to a random variable S with E[|S|] < ∞.

  Note that in the original statement, only the Euclidean norm • 2 is used (Definition 12.58 in[START_REF] Rockafellar | Variational analysis[END_REF] defined strong convexity implicitly in terms of the Euclidean norm), in which case • * 2 = • 2 . However, as stated here, the same result holds true for any pair of norms ( • , • * ) by a straightforward adaptation of their proof.

  This then implies that, by the monotonicity property established in Claim 4,F λ (x * , φ s (y)) ≤ F λ (x * , φ s 0 (y)), thereby leading to x(s) ∈ B(x * , 2 ), a contradiction. Since x(t) / ∈ B(x * , 2 ), ∀t ∈ [0, s], we have x(t) / ∈ B(x * , ˜ ), ∀t ∈ [0, s],leading to that Equation 53 holds for t ∈ [0, s]. Therefore, taking s = 2a ˜ , we obtain:F λ (x * , φ s (y)) ≤ F λ (x * , y) -a ˜ s = F λ (x * , y) -2 . Fix some T > 0 and define K λ = max i λ i and δ = √ (λmaxR) 2 +2 K λ -K λ R 4K λ = 0, a.s.. Consequently, choose τ (δ, T ) such that Y (t + h), φ h (Y (t)) * < δ, ∀t ≥ τ . Expanding λ-Fenchelcoupling, we obtain that ∀t ≥ τ and ∀h ∈ [0, T ]:F λ (x * , Y (t + h)) = F λ (x * , φ h (Y (t)) + Y (t + h) -φ h (Y (t))) ≤ F λ (x * , φ h (Y (t))) K λ ( Y (t + h) -φ h (Y (t)) * ) 2 (59) ≤ F λ (x * , φ h (Y (t))) + λ max R Y (t + h) -φ h (t) * + K λ ( Y (t + h) -φ h (Y (t))

		(55)
	Equation (54) and Equation (55) together establish that:
		F . Per Claim 3, we have
		∀T > 0, lim
		(58)
	N
	+	λ i (Y i (t + h) -φ i h (Y (t)) (C i (φ i h (Y (t))) -x * i ) +
	i=1

λ (x * , φ s (y)) ≤ max{ 2 , F λ (x * , y) -2 }.

6. Let R = sup x∈X x , which is finite since X is compact. By the definition of dual norm and denote λ max = max i λ i , we have

N i=1 λ i (Y i (t + h) -φ i h (Y (t + h)) (C i (φ i h (Y (t + h))) -x * i ) ≤ (56) N i=1 λ i (Y i (t + h) -φ i h (Y (t + h)) * i (C i (φ i h (Y (t + h))) -x * i ) ≤ λ max R Y (t + h) -φ h (t + h) * ,

(57)

where

φ i h (Y (t + h)) is the i-th component of φ h (Y (t + h)). t→∞ sup 0≤h≤T Y (t + h), φ h (Y (t)) * * ) 2

(60)

≤ F λ (x * , φ h (Y (t))) + λ max Rδ + K λ δ 2 (61)

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

(c) sup t x t < ∞.

Then the affinely interpolated process Y (t) is an asymptotic pseudotrajectory of the semi-flow φ induced by the ODE almost surely:

∀T > 0, lim t→∞ sup 0≤h≤T Y (t + h), φ h (Y (t)) * = 0, a.s..

Choose q = 2, the above conditions can be easily verified: (a) holds by Assumption 2; (b) holds since α t is square summable; (c) holds since the decision space X is compact. Therefore the claim follows.

4. By a well-known result in variational analysis [START_REF] Rockafellar | Variational analysis[END_REF]), each h i (•) is differentiable and

Note further that since φ t (y) is the solution to the ODE (under the initial condition y), we have dφ t (y) dt = v(x(t)). Written out component-wise, we have

We can thus compute the derivative of λ-Fenchel coupling as follows:

where the second equality follows from Equation ( 47), the third equality follows from Equation (48), and the last inequality follows from x * is λ-variationally stable. The monotonicity property therefore follows.

5. For any given > 0, pick an ˆ > 0 such that B(x * , ˆ ) ⊂ B(x * , 2 ). By Equation ( 52), we have

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

where the first inequality follows from Equation ( 57) and the last equality follows from straightforward algebraic verification. The claim is therefore established.

7. We start by fixing an arbitrary > 0. Per Claim 5, there exists an s > 0 (depending on ) such that Equation ( 16) holds. Set the horizon T = s. Per Claim 6, there exists a τ (depending on both and T ) such that Equation ( 17) holds ∀t ≥ τ . Now, per Claim 1, X t visits B(x * , δ)

infinitely often 9 . Therefore, pick an integer τ 0 ≥ τ such that X τ 0 ∈ B(x * , 2 ). With this choice of τ 0 , we know that by definition of B,

Our goal is to establish that

Per Claim 4, the monotonicity property given in Equation ( 15) implies that:

where the equality follows from the semi-group property of a semiflow.

Per Equation ( 17), for h ∈ [0, T ), we then have:

where the last inequality follows from Equation (66). Now assume inductively that Equation (67) holds for every h ∈ [nT, (n + 1)T ), where n is a non-negative integer. We then have ∀h ∈ [nT, (n + 1)T ):

where the first inequality follows from Equation ( 17), the second inequality follows from Equation ( 16), and the third inequality follows from the induction hypothesis F λ (x * , Y (τ 0 + h)) < .

Consequently, Equation (67) holds for every h ∈ [(n + 1)T, (n + 2)T ), thereby completing the induction and establishing that: