Luca Carlone
email: luca.carlone@polito.it

Vaibhav Srivastava
email: vaibhav@engineering.ucsb.edu

Francesco Bullo
email: bullo@engineering.ucsb.edu

Giuseppe C Calafiore
email: giuseppe.calafiore@polito.it

A Distributed Algorithm for Random Convex Programming

We study a distributed approach for solving random convex programs (RCP) for the case in which problem constraints are distributed among nodes in a processor network. We devise a distributed algorithm that allows network nodes to reach consensus on problem solution by exchanging a local set of constraints at each iteration. We prove that the algorithm assures finite-time convergence to problem solution and we provide explicit bounds on the maximum number of constraints to be exchanged among nodes at each communication round. Numerical experiments confirm the theoretical derivation and show that a parallel implementation of the proposed approach speeds-up the solution of the RCP with respect to centralized computation.

I. INTRODUCTION

Optimization algorithms constitute the core of several problems in estimation, control and machine learning. In order to guarantee some sort of robustness of the optimal solution, the uncertainty in the input data must be taken into account. Particularly, if the constraints defining an optimization problem are functions of a random parameter, then the robustness of the optimal solution is measured by the capacity of the solution to preserve optimality under several realizations of the uncertain parameter. There are several approaches to ascertain robustness of the optimal solution. The robust convex optimization [START_REF] Ben-Tal | Robust optimization: Methodology and applications[END_REF] enforces the optimality of the solution to the worst possible realization of the uncertainty. The chance-constrained optimization [START_REF] Prékopa | Probabilistic programming[END_REF] provides an optimal solution with guaranteed bounds on the probability of constraints violation. In this context, random convex programming [START_REF] Calafiore | Random convex programs[END_REF] approach enforces the optimality on a realization of the uncertainty (scenario) and provides probabilistic assessments on the robustness of the solution towards further unseen random constraints. The power of this approach to uncertain convex optimization lies in its computational tractability (they can be formulated in terms of finite-dimensional convex optimization problems) and in the possibility of trading-off between robustness (i.e., bounds on violation probability) and performance (i.e., value of the optimal objective). Although computing the solution for a given scenario reduces to solve a convex program, an RCP may have a large number of constraints and entrusting the computation to a single processor can be undesirable in terms of computational effort. Moreover, the constraints defining the scenario may be not known to a central unit, since each constraint can be function of local information acquired by different nodes in a network. For such reasons, in this context, we are interested in investigating a distributed approach to random convex programs.

Recently, there has been significant interest in distributed optimization. Widespread approaches for distributed optimization are based on dual decomposition [START_REF] Tsitsiklis | Problems in decentralized decision making and computation[END_REF], [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF], [START_REF] Nedíc | Distributed subgradient methods for multi-agent optimization[END_REF], [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. In dual decomposition-based approaches, the nodes communicate the estimate of the local algorithm and asymptotically achieve the global solution of the problem. An alternative approach to distributed optimization has been proposed in [START_REF] Notarstefano | Distributed abstract optimization via constraints consensus: Theory and applications[END_REF], [START_REF] Burger | A distributed simplex algorithm for degenerate linear programs and multi-agent assignment[END_REF], where the nodes exchange a small set of constraints at each iteration, and converge to a consensus set of constraints that determines the global solution of the optimization problem in finite time.

In this paper, we consider the case in which a network of processors is in charge of solving a random convex program. Each node knows a subset of constraints of the RCP and the network is required to compute the global solution of the RCP (i.e., the solution obtained by considering all the constraints) in a distributed fashion. First, we investigate some basic properties of the constraints sets in convex programs. Then, we exploit these properties to devise a distributed algorithm, namely active constraints consensus (ACC), that allows to solve the RCP in a finite number of iterations. The proposed algorithm is inspired by the recent work [START_REF] Notarstefano | Distributed abstract optimization via constraints consensus: Theory and applications[END_REF], and extends it to convex programming. The ACC algorithm can be also used for parallel computation of the solution of the RCP. For large scale problems, we numerically demonstrate that such parallel computation significantly improves the computation time over the centralized setup. We elucidate on the proposed theory showing an application to distributed classification. A convex program that does not satisfy unique minimum condition can be easily transformed to an equivalent problem that satisfies the unique minimum condition, by applying a suitable tie-breaking rule (e.g., choosing the lexicographic smallest solution 𝑥 * (𝐶 ′ ), ∀𝐶 ′ ⊆ 𝐶 within the set of optimal solutions) [START_REF] Calafiore | Random convex programs[END_REF]. We provide an example of a tie-breaking rule in Appendix I of the paper. Accordingly and without loss of generality, in the following we consider convex programs satisfying the unique minimum condition. We conclude this section with a last definition: Definition 4 (General Position): A set of constraints in a feasible 𝑑-dimensional convex program is said to be in general position if no more than 𝑑 constraints intersect at any point in the domain 𝑋. In the case of possibly unfeasible problems no more than 𝑑+1 constraints intersect at any point of the domain. □

III. PROPERTIES OF THE CONSTRAINTS SETS

We now state some properties of convex programs pertinent to the discussion in this paper. We start by introducing some notations. Let the number of different essential sets in 𝐶 be 𝑏 and es 𝑖 (𝐶) be the 𝑖th essential set. For the optimization problem 𝑃 [𝐶], we define the combinatorial dimension 𝑑 comb as:

𝑑 comb = { 𝑑, if 𝑃 [𝐶] is feasible 𝑑 + 1, otherwise.
We now state some properties of the problem 𝑃 [𝐶]:

Proposition 1 (Monotonicity & Locality, [START_REF] Calafiore | Random convex programs[END_REF]): For the convex optimization problem 𝑃 [𝐶], constraint sets 𝐶 1 , 𝐶 2 ⊆ 𝐶, and a generic constraint 𝑐 ∈ 𝐶, the following properties hold: i) Monotonicity:

𝐽 * (𝐶 1 ) ≤ 𝐽 * (𝐶 1 ∪ 𝐶 2 ); ii) Locality: if 𝐽 * (𝐶 1 ) = 𝐽 * (𝐶 1 ∪ 𝐶 2 ), then 𝐽 * (𝐶 1 ∪{𝑐}) > 𝐽 * (𝐶 1 ) ⇐⇒ 𝐽 * (𝐶 1 ∪ 𝐶 2 ∪{𝑐}) > 𝐽 * (𝐶 1 ∪ 𝐶 2 ).
Proposition 2 (Properties of the constraints): The following statements hold for the constraints sets in optimization problem 𝑃 [𝐶]:

i) The set of support constraints is the intersection of all the essential constraints sets, that is, sc(𝐶) = ∩ 𝑏 𝑖=1 es 𝑖 (𝐶) ii) The set of active constraints contains the union of all the essential sets, that is, ac(𝐶) ⊇ ∪ 𝑏 𝑖=1 es 𝑖 (𝐶). iii) The cardinality of each essential constraints set is at most 𝑑 comb . Proof. We start by establishing the first statement. Assume that

𝑐 ∈ sc(𝐶), that is, 𝐽 * (𝐶∖{𝑐}) < 𝐽 * (𝐶). Suppose now that 𝑐 / ∈ ∩ 𝑏 𝑖=1 es 𝑖 (𝐶), that is, 𝑐 / ∈ es 𝑖 (𝐶), for some 𝑖 ∈ {1, . . . , 𝑏}. Therefore, 𝐽 * (es 𝑖 (𝐶)∖{𝑐}) = 𝐽 * (es 𝑖 (𝐶)). (2)
By the definition of an essential set, 𝐽 * (𝐶) = 𝐽 * (es 𝑖 (𝐶)).

It follows from the assumption and equation ( 2) that

𝐽 * (𝐶∖{𝑐}) < 𝐽 * (𝐶) = 𝐽 * (es 𝑖 (𝐶)∖{𝑐}),
which contradicts monotonicity. Therefore, 𝑐 ∈ sc(𝐶) implies 𝑐 ∈ ∩ 𝑏 𝑖=1 es 𝑖 (𝐶), that is, sc(𝐶) ⊆ ∩ 𝑏 𝑖=1 es 𝑖 (𝐶). We now claim that sc(𝐶) ⊇ ∩ 𝑏 𝑖=1 es 𝑖 (𝐶). Let us assume that 𝐽 * (𝐶 ∖{𝑐}) = 𝐽 * (𝐶), that is, 𝑐 / ∈ sc(𝐶). It follows that there exists es(𝐶 ∖{𝑐}) such that 𝐽 * (𝐶) = 𝐽 * (es(𝐶 ∖{𝑐})). Therefore, es(𝐶 ∖ {𝑐}) is also an essential set for 𝐶 and 𝑐 / ∈ ∩ 𝑏 𝑖=1 es 𝑖 (𝐶). This concludes the proof of the first statement. We now establish the second statement. From the minimality of the essential set, it follows that each constraint in es 𝑖 (𝐶) is a support constraint for the problem 𝑃 [es 𝑖 (𝐶)], and they need to be active for the problem 𝑃 [es 𝑖 (𝐶)], see Appendix II. As a consequence, if 𝑥 * (es 𝑖 (𝐶)) is the optimal solution for 𝑃 [es 𝑖 (𝐶)], and 𝑓 𝑗 (𝑥 * 𝑖 ) = 0, for each 𝑗 ∈ es 𝑖 (𝐶). From the unique minimum condition and locality, it follows that

𝐽 * (es 𝑖 (𝐶)) = 𝐽 * (𝐶) =⇒ 𝑥 * (es 𝑖 (𝐶)) = 𝑥 * (𝐶),
for each 𝑖 ∈ {1, . . . , 𝑏}. Therefore, 𝑓 𝑗 (𝑥 * ) = 0, for each 𝑗 ∈ es 𝑖 (𝐶), 𝑖 ∈ {1, . . . , 𝑏}, and ac(𝐶) ⊇ ∪ 𝑏 𝑖=1 es 𝑖 (𝐶). To prove the last statement, we note from [START_REF] Calafiore | Random convex programs[END_REF] = |𝐶|, and assume that 𝛿 (𝑗) ∈ Δ, 𝑗 = 1, . . . , 𝑁, are independent and identically distributed. Finally, denote with 𝜔 . = (𝛿 (1) , . . . , 𝛿 (𝑁 ) ) ∈ Δ 𝑁 , with

Δ 𝑁 = Δ × Δ ⋅ ⋅ ⋅ Δ (𝑁 times).
We define the distributed random convex program (DRCP) over graph 𝐺 as:

𝑃 [𝐶(𝜔)] . = 𝑃 [𝜔] : min 𝑥∈𝑋 𝑎 ⊤ 𝑥 subject to: (3) 𝑓 𝑗 (𝑥) ≤ 0, 𝑗 ∈ ∪ 𝑛
𝑖=𝑖 𝐶 𝑖 where node 𝑖 knows set of random constraints 𝐶 𝑖 , it can receive information from nodes in the set 𝒩 in (𝑖) and can transmit information to nodes in the set 𝒩 out (𝑖). Since each node has only a partial knowledge of problem constraints, it needs to exploit local computation and inter-nodal communication to compute the global solution of 𝑃 [𝜔]. We refer to the solution of 𝑃 (𝜔) obtained by considering only the local constraints at a given node by the local solution and the associated value of the objective function by the local optimal value. We denote the local solution and the local optimal value at node 𝑖 by 𝑥 * 𝑖 and 𝐽 * 𝑖 , respectively. We refer to the solution and the optimal value of 𝑃 [𝜔] obtained by considering all the constraints by the global solution and the global optimal value, respectively.

We conclude this section with two definitions: Definition 5 (Helly's dimension [START_REF] Calafiore | Random convex programs[END_REF]): Let 𝐶(𝜔) be the set of 𝑁 random constraints associated with realization 𝜔. The □ Definition 6 (Violation probability [START_REF] Calafiore | Random convex programs[END_REF]): For a random convex program 𝑃 [𝜔], the violation probability 𝑉 * (𝜔) is defined as

𝑉 * (𝜔) . = ℙ{𝛿 ∈ Δ : 𝐽 * (𝜔 ∪ {𝛿}) > 𝐽 * (𝜔)}.
where 𝐽 * (𝜔 ∪{𝛿}) is the optimal value of 𝑃 [𝜔] subject to an additional random constraint associated with the realization 𝛿 of the random parameter. □

B. Distributed Computation of the Scenario Solution

We now study the distributed computation of the scenario solution of random convex program 𝑃 [𝜔] under the following assumptions:

Assumption 1: The digraph 𝐺 is strongly connected, that is, the digraph 𝐺 contains a directed path from each vertex to another.

□ Assumption 2: The constraints in the random convex program 𝑃 [𝜔] are in general position almost surely.

□ The global optimal objective value 𝐽 * (𝜔) and the solution 𝑥 * = 𝑥 * (𝜔) are random variables, whose value depend on the realization of the uncertain parameter 𝜔. Moreover, for each realization of 𝜔, random convex program 𝑃 [𝜔] is a convex optimization problem. In the following we present a distributed algorithm that computes the solution to such convex optimization problem. We assume that a generic node 𝑖 at time 𝑡 has knowledge of the local set 𝐶 𝑖 and can store a small candidate set that we call 𝐴 𝑖 (𝑡). Each node initializes the candidate set to 𝐴 𝑖 (0) = ac(𝐶 𝑖 ), by solving the local convex program 𝑃 [𝐶 𝑖 ]. Then, at each iteration 𝑡 of the algorithm, node 𝑖 receives the candidate sets from the incoming neighbors, i.e., 𝐴 𝑗 (𝑡), 𝑗 ∈ 𝒩 in (𝑖), and updates its candidate set with the following rule:

𝐴 𝑖 (𝑡 + 1) = ac ( 𝐴 𝑖 (𝑡) ∪ ( ∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑗 (𝑡) ) ∪ 𝐶 𝑖 )
. The algorithm, named active constraints consensus, is summarized in Algorithm 1. We now state some important properties of the algorithm in the following proposition. [START_REF] Calafiore | Random convex programs[END_REF]. Proof. From Assumption 2 it follows that no point in 𝑋 lies on the boundary of more than 𝑑 comb constraints. For the unique minimum condition, the minimum is attained at a single point, therefore, no more than 𝑑 comb constraints can be active for any subproblem 𝑃 [𝐻], with𝐻 ⊆ 𝐶, and the number of constraints to be transmitted is upper-bounded by 𝑑 comb .

Algorithm 1 Active Constraints Consensus (ACC)

To prove the second statement we first observe that (a) 𝐽 * (ac(𝐻)) = 𝐽 * (es(𝐻)) = 𝐽 * (𝐻), for any 𝐻 ∈ 𝐶. The equality can be proved as follows. 𝐽 * (ac(𝐻)) ≥ 𝐽 * (es(𝐻)) is a consequence of monotonicity and Lemma 2 (ac(𝐻) ⊇ es(𝐻)). Assume now the contradiction that 𝐽 * (ac(𝐻)) > 𝐽 * (es(𝐻)); by monotonicity and by definition of essential set it follows 𝐽 * (𝐻) ≥ 𝐽 * (ac(𝐻)) > 𝐽 * (es(𝐻)) = 𝐽 * (𝐻), leading to contradiction. We can now use this basic property for analyzing the iterations of the active constraints consensus:

𝐽 * (𝐴 𝑖 (𝑡 + 1)) = 𝐽 * (ac(𝐴 𝑖 (𝑡) ∪(∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑗 (𝑡)) ∪ 𝐶 𝑖 )) = fact (a) = 𝐽 * (𝐴 𝑖 (𝑡) ∪(∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑗 (𝑡)) ∪ 𝐶 𝑖 ) monotonicity ≥ 𝐽 * (𝐴 𝑖 (𝑡)).
Thus, the sequence of objective values is non-decreasing in 𝑡. Moreover, the sequence is upper bounded, since for any 𝐻 ⊆ 𝐶, 𝐽 * (𝐻) ≤ 𝐽 * (𝐶). Finally, we notice that 𝐽 * (𝐴 𝑖 (𝑡)) can assume a finite number of values, i.e., 𝐽 * ∈ 𝒥 := {𝐽 * (𝐻) | 𝐻 ⊆ 𝐶}, hence the sequence has to converge to a constant value, say 𝐽 * 𝑖 in finite time. It now remains to demonstrate that after all the nodes in the network have reached convergence, the local objective 𝐽 * 𝑖 . = 𝐽 * (𝐴 𝑖 (𝑇 )) at a generic node 𝑖 is equal to the global objective 𝐽 * (𝐶). For the hypothesis of convergence, in the following development we drop the time indices. We first demonstrate that after convergence all the nodes need to have the same local objective, i.e., 𝐽 * 𝑖 = Ĵ, for each 𝑖 ∈ {1, . . . , 𝑛}. Assume by absurd that two nodes, say 𝑖 and 𝑗, have different objective values, 𝐽 * 𝑖 > 𝐽 * 𝑗 . From the assumption of strongly connectivity of the graph 𝐺, there exist a directed path between 𝑖 and 𝑗. Because of the update law of algorithm, along this path, monotonicity holds, i.e., for any directed edge (𝑖 1 , 𝑖 2 ), that belongs to the path from 𝑖 to 𝑗, it holds:

𝐽 * 𝑖2 = 𝐽 * (𝐴 𝑖2 ) = 𝐽 * (ac(𝐴 𝑖2 ∪(∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑖1 ) ∪ 𝐶 𝑖2 )) fact (a) = 𝐽 * (𝐴 𝑖2 ∪(∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑗 ) ∪ 𝐶 𝑖2 ) monotonicity ≥ 𝐽 * (𝐴 𝑖2 ∪ 𝐴 𝑖1 ∪ 𝐶 𝑖2 ) monotonicity ≥ 𝐽 * (𝐴 𝑖1 ).
Iterating this reasoning along the path we arrive to the contradiction 𝐽 * 𝑖 ≤ 𝐽 * 𝑗 . Therefore, for any pair of nodes 𝑖 and 𝑗, it must hold 𝐽 * 𝑖 = 𝐽 * 𝑗 = Ĵ, implying 𝐽 * 𝑖 = Ĵ, for each 𝑖 ∈ {1, . . . , 𝑛}.

Then, we want to show that the local objective Ĵ actually corresponds to 𝐽 * (𝐶). Let us consider a directed path connecting all nodes and ending at a generic node 𝑖. Now re-label the nodes in this path from 1 to 𝑛 and start by considering the last node. For the hypothesis that the node reached convergence and for the presence of the edge

(𝑛-1, 𝑛) it holds (b) 𝐽 * 𝑛 = 𝐽 * (𝐴 𝑛 ) = 𝐽 * (𝐴 𝑛 ∪ 𝐴 𝑛-1 ∪ 𝐶 𝑛 ). Similarly for node 𝑛 -1 it holds (c) 𝐽 * 𝑛-1 = 𝐽 * (𝐴 𝑛-1 ) = 𝐽 * (𝐴 𝑛-1 ∪ 𝐴 𝑛-2 ∪ 𝐶 𝑛-1 ). But we demonstrated that 𝐽 * 𝑛 = 𝐽 * 𝑛-1 , hence from (b) it follows (d) 𝐽 * (𝐴 𝑛 ∪ 𝐴 𝑛-1 ∪ 𝐶 𝑛 ) = 𝐽 * (𝐴 𝑛-1 ). Since from (c), 𝐶 𝑛-1 does not contain violators of 𝐴 𝑛-1 , applying locality to (d) if holds 𝐽 * 𝑛 = 𝐽 * (𝐴 𝑛 ) = 𝐽 * (𝐴 𝑛 ∪ 𝐴 𝑛-1 ∪ 𝐶 𝑛 ) = 𝐽 * (𝐴 𝑛 ∪ 𝐴 𝑛-1 ∪ 𝐶 𝑛 ∪ 𝐶 𝑛-1
). Repeating the same considerations for node 𝑛 -1 and 𝑛 -2, we conclude that 𝐶 𝑛-2 does not contain violators of 𝐴 𝑛-1 , hence by locality

𝐽 * 𝑛 = 𝐽 * (𝐴 𝑛 ∪ 𝐴 𝑛-1 ∪ 𝐶 𝑛 ) = 𝐽 * (𝐴 𝑛 ∪ 𝐴 𝑛-1 ∪ 𝐶 𝑛 ∪ 𝐶 𝑛-1 ∪ 𝐶 𝑛-2
). Iterating such reasoning along the directed path spanning all nodes, we conclude Point (iii) claims that after convergence is attained the local solution 𝑥 * (𝐴 𝑖 ) coincides with the centralized solution of the RCP. This is a consequence of the fact that 𝐽 * (𝐴 𝑖 ) = 𝐽 * (𝐶): for the unique minimum condition the optimal objective value is attained at a single point, moreover by locality every constraints that violates 𝐴 𝑖 has to violate also 𝐶 and this can happen only if 𝑥 * (𝐴 𝑖 ) = 𝑥 * (𝐶).

𝐽 * 𝑛 = 𝐽 * (𝐴 𝑛 ∪ 𝐴 𝑛-1 ∪ 𝑛 𝑖=1 𝐶 𝑖 );
For proving point (iv) we have to show that the set 𝐴 𝑖 contains all the constraints that are globally active for 𝑃 [𝐶]. According to the claim (iii) we have that 𝑥 * = 𝑥 * 𝑖 = 𝑥 * (𝐴 𝑖 ), 𝑖 ∈ {1, . . . , 𝑛} and this solution coincides with 𝑥 * (𝐶). By contradiction let us suppose that there exists a globally active constraint 𝑐 𝑘 that is contained in the local constraint set 𝐶 𝑖 of a node 𝑖, but is not in the candidate set 𝐴 𝑗 of node 𝑗. Let us consider a directed path from 𝑖 to 𝑗 and re-label the nodes in this path from 1 to 𝑙. Starting from node 1 we observe that, since 𝑥 * 1 = 𝑥 * (𝐶) and 𝑐 𝑘 is active for 𝑃 [𝐶], then 𝑐 𝑘 ∈ 𝐴 1 . According to the update rule of the active constraint consensus, node 2 in the path, computes

𝐴 2 = ac(𝐴 2 ∪(∪ 𝑗∈𝒩in(2,𝑡) 𝐴 𝑗 ) ∪ 𝐶 2 ). Therefore, if 𝑐 𝑘 ∈ 𝐴 1 and 𝑥 * 1 = 𝑥 * 2 , then 𝑐 𝑘 ∈ 𝐴 2 .
Iterating this reasoning along the path from 𝑖 to 𝑗 we conclude that 𝑐 𝑘 ∈ 𝐴 𝑗 leading to contradiction.

The proof of claim (v) is a straightforward consequence of the results on random convex programs, see [START_REF] Calafiore | Random convex programs[END_REF]. □ It is worth noticing that the proof of claim (ii) proceeds along the same lines of the proof of Theorem IV.4 in [START_REF] Notarstefano | Distributed abstract optimization via constraints consensus: Theory and applications[END_REF]. Moreover, it is easy to prove that, if the candidate set at one node does not change for 2diam(𝐺) + 1 iterations, then the local solution at the node has converged to the global solution (the demonstration is similar to the proof of claim (ii) of Proposition 4).

Remark 1: The active constraints consensus algorithm can be used for the distributed computation of the solution of any convex program. It is particularly suited for random convex programs because they have a large number of constraints which are in general position almost surely. □ Remark 2: As a by-product of this work we notice that the approach proposed in [START_REF] Notarstefano | Distributed abstract optimization via constraints consensus: Theory and applications[END_REF] can be applied as a distributed algorithm for convex programming (according to Proposition 1 convex programs are abstract optimization problems). However, [START_REF] Notarstefano | Distributed abstract optimization via constraints consensus: Theory and applications[END_REF] would require the nodes to compute an essential set of the local set of constraints at each iteration, and such computation can be expensive in practice. On the other hand, the ACC algorithm only requires the computation of the active constraints set, which can be easily obtained by solving the local convex problem. Moreover, when the local solution 𝑥 * 𝑖 . = 𝑥 * (𝐴 𝑖 (𝑡)) is not violated by the incoming neighbors constraints, ∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑖 (𝑡), the update of ACC algorithm only requires to check if for some 𝑐 ∈ ∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑖 (𝑡), it holds 𝑓 𝑐 (𝑥 * 𝑖 ) = 0. □

V. NUMERICAL EXAMPLE

We now briefly describe an application of the proposed approach to robust linear classification.

A. Robust Linear Classification

Let us consider a set of features {𝑎 𝑘 ∈ ℝ 𝑝 | 𝑘 ∈ {1, . . . , 𝑚}} and the corresponding class labels 𝑏 𝑘 ∈ {-1, +1}. The linear classification problem determines a hyperplane that separates the features with different labels. In general, the features with different labels are not linearly separable, and a convex loss function penalizing misclassifications is minimized. Suppose that each node in a processor network measures a subset of the features; each feature is measured with uncertainty and the associated distribution is unknown. Let Δ be the sample space and 𝛿 ∈ Δ represent a particular realization of the uncertainty. The robust linear classification problem minimizes the loss due to misclassification in one of the following ways: it minimizes the worst loss due to mis-classifications min

(𝛿)𝜃 + 𝜌)) -𝜆 𝑘 ≤ 0 𝜃 ∈ ℝ 𝑝 , 𝜌 ∈ ℝ, 𝜆 𝑘 ∈ ℝ ≥0 , (5)
where 𝑔 : ℝ 𝑝 → ℝ ≥0 is a convex regularization function, ℎ : ℝ → ℝ ≥0 is a convex loss function, 𝜆, 𝜆 𝑘 ∈ ℝ ≥0 are some parameters. In these formulations, the regularization function imparts special structure to the parameter 𝜃, while the loss function penalizes for misclassification of some feature into wrong label. Problems ( 4) and ( 5) correspond to the robust formulations of the classification problem; we leave to the reader the modifications that allow to retrieve the RCP counterpart.

Example 1: We study the following robust linear classification problem:

min 𝜃,𝜆,𝜌

𝜆

subject to :

𝑥 ⊤ 𝑖 𝜃 + 𝜌 -𝜆 ≤ 0, ∀𝑖 ∈ {1, . . . , 𝑁 𝑥 } 𝑦 ⊤ 𝑗 𝜃 + 𝜌 + 𝜆 ≥ 0, ∀𝑗 ∈ {1, . . . , 𝑁 𝑦 } ∥𝜃∥ 2 ≤ 1 𝜃, 𝑥 𝑖 , 𝑦 𝑗 ∈ ℝ 𝑝 , 𝜌 ∈ ℝ, 𝜆 ∈ ℝ ≥0 ,
where 𝑝 is lately referred to as dimension of the classification problem, 𝑥 𝑖 are the 𝑁 𝑥 features with label +1 and 𝑦 𝑖 are the 𝑁 𝑦 features with label -1. For sake of simplicity we assume 𝑁 𝑥 = 𝑁 𝑦 . In our experiments, 𝑥 𝑖 and 𝑦 𝑖 are sampled from normal distributions, 𝒩 (0 𝑝 , 25𝑰 𝑝 ) and 𝒩 (50 ⋅ 1 𝑝 , 25𝑰 𝑝 ), respectively. Notice that the problem is feasible with probability 1, hence the combinatorial dimension is 𝑑 comb = 𝑝 + 2 (the decision variable also comprises the scalars 𝜌 and 𝜆). Moreover the problem satisfies the unique minimum condition, which is enforced by the constraint ∥𝜃∥ 2 ≤ 1, [START_REF] Boyd | Convex optimization[END_REF].

We first study the parallel solution of the robust classification problem on a complete graph for different number of processors and for 20 different realizations of the constraints (scenarios). For this test we consider 𝑝 = 4 and 𝑁 𝑥 = 10 5 . The simulation results are shown in Figure 1. The top figure shows the average computation time for different numbers of processors. It can be seen that the average computation time decreases with the number of processors. The average processing time saturates for number of processors larger than 50. The bottom figure shows the average number of iterations required for convergence. The average number of active constraints exchanged at each communication round was 4.8.

In the second experiments we investigate the scalability of the approach with respect to the number of constraints in the global RCP. We consider 20 different realizations of the constraints, dimension 𝑝 = 4 and number of processors 𝑛 = 50. In Figure 2 we show the computational time, the number of iterations and the average number of active constraints exchanged among nodes for 𝑁 𝑥 = {10 2 , 10 3 , 10 4 , 10 5 }. It is possible to notice that the computational effort of the parallel approach has better scalability properties with respect to the centralized implementation, which shows a sharp increase of the CPU time for 𝑁 𝑥 > 10 3 . Therefore, the proposed approach has a clear computational advantage over the centralized solution for problems with large number of constraints. Moreover, the number of iterations shows low sensitivity with respect to the number of constraints of the RCP.

As a last test regarding the parallel implementation, we study the performance of the algorithm for different problem dimensions. In Figure 3 we report the computational effort of the proposed approach compared with the centralized implementation for different values of 𝑝. Also in this case, the ACC algorithm shows low sensitivity to problem dimension if compared with its centralized counterpart. The lower plots in Figure 3 show the number of iterations and the average number of constraints exchanged by the nodes at each communication round.

As a conclusion of this section we report further numerical results concerning other graph topologies, which can be of interest for distributed applications in sensor networks. We consider 𝑝 = 2 and 𝑁 𝑥 = 10 3 . In Table I we report number of iterations, number of active constrains and average graph diameter for geometric random graph and chain graph.

VI. CONCLUSION

We considered a setup in which the constraints of a random convex program are distributed among several nodes in a processor network and the network is in charge of solving the global RCP, satisfying all problem constraints.

We first analyzed the properties of the constraint sets in a convex program and then we exploited such properties for devising a distributed algorithm, named active constraints consensus. The algorithm allows network nodes to reach consensus on problem solution by exchanging a local set

  Helly's dimension of a random convex program 𝑃 [𝜔] is the least integer 𝜁 such that ess sup 𝜔∈Δ 𝑁 |sc(𝐶(𝜔))| ≤ 𝜁 holds for any finite 𝑁 ≥ 1.

  finally we observe that by assumption ∪ 𝑛 𝑖=1 𝐶 𝑖 = 𝐶 and 𝐴 𝑛 , 𝐴 𝑛-1 ⊆ 𝐶, therefore 𝐽 * 𝑛 = 𝐽 * 𝑖 = 𝐽 * (𝐶), and this proves point (ii) of the proposition.

Fig. 1 .

 1 Fig. 1. Computation time and number of iterations versus number of nodes for the parallel solution of the robust classification problem. Results are averaged over 20 tests. In the top figure, the red line represents the centralized solution while the blue line represents the proposed parallel solution.

Fig. 2 .

 2 Fig. 2. Computation time, number of iterations and number of active constraints versus 𝑁𝑥 for the parallel solution of the robust classification problem. Results are averaged over 20 tests. In the top figure, the red line represents the centralized solution while the blue line represents the proposed parallel solution.

Fig. 3 .

 3 Fig. 3. Computation time, number of iterations and number of active constraints versus problem dimension for the parallel solution of the robust classification problem. Results are averaged over 20 tests. In the top figure, the red line represents the centralized solution while the blue line represents the proposed parallel solution.

  The rest of this paper is organized as follows. Preliminaries on convex optimization are discussed in Section II. Certain properties of the constraints in convex programs are established in Section III. The ACC algorithm is presented in Section IV. We elucidate on the developed theory with some examples in Section V. Conclusions are presented in Section VI. The support constraints set sc(𝐶)⊆ 𝐶 of problem 𝑃 [𝐶] is the set of constraint 𝑐 ∈ 𝐶 such that 𝐽 * (𝐶∖{𝑐}) < 𝐽 * (𝐶).The cardinality of the set of support constraints is upper bounded by 𝑑 + 1; moreover, the upper bound reduces to 𝑑, if the problem is feasible [3]. □ Definition 2 (Essential Constraint Set): An essential constraint set es(𝐶) ⊆ 𝐶 of problem 𝑃 [𝐶] is a minimal subset such that 𝐽 * (es(𝐶)) = 𝐽 * (𝐶). If the essential constraint set es(𝐶 𝑖 ) is unique for any 𝐶 𝑖 ⊆ 𝐶, the optimization problem 𝑃 [𝐶] is called nondegenerate. □ Definition 3 (Active Constraints): The active constraints set ac(𝐶) ⊆ 𝐶 of problem 𝑃 [𝐶] is the set of constraints that are tight at the optimal solution 𝑥 * (𝐶), that is, ac(𝐶) = {𝑗 ∈ 𝐶 : 𝑓 𝑗 (𝑥 * (𝐶)) = 0}. □ Feasible convex programs may have more than one solution, i.e., several values of the optimization variable may attain the same optimal objective value. The convex program 𝑃 [𝐶] satisfies the unique minimum condition, if the problem 𝑃 [𝐶 𝑖 ] admits a unique solution, for any 𝐶 𝑖 ⊆ 𝐶.

	II. PRELIMINARIES
	Consider a generic 𝑑-dimensional convex program
	𝑃 [𝐶] : min
	We now introduce some definitions:
	Definition 1 (Support Constraints):

𝑥∈𝑋

𝑎 ⊤ 𝑥 subject to :

𝑓 𝑗 (𝑥) ≤ 0, ∀𝑗 ∈ 𝐶,

(1)

where 𝑥 ∈ 𝑋 is the optimization variable, 𝑋 ⊂ ℝ 𝑑 is a closed and convex set, 𝑎 is the objective direction, 𝑓 𝑗 : ℝ 𝑑 → ℝ, 𝑗 ∈ 𝐶 are convex constraints, and 𝐶 ⊆ ℕ is the finite set of constraints. We denote the solution of the problem 𝑃 [𝐶] by 𝑥 * (𝐶) and the corresponding optimal value by 𝐽 * (𝐶).

  that the maximum cardinality of the support set of 𝑃 [𝐶] is 𝑑 comb . Assume that 𝑃 [𝐶] is feasible. Now consider by absurd that 𝑃 [𝐶] has at least one essential set, say es 𝑖 (𝐶) with cardinality d > 𝑑. Notice that es 𝑖 (𝐶) is the unique essential set for 𝑃 [es 𝑖 (𝐶)]. It follows from the first statement that es 𝑖 (𝐶) = sc(es 𝑖 (𝐶)). This means that the support constraint set sc(es 𝑖 (𝐶)) has cardinality d, which is a contradiction. Similar argument applies in the case when 𝑃 [𝐶] is infeasible. This concludes the proof. □ Corollary 3 (Constraints set in nondegenerate programs): For nondegenerate convex programs, es(𝐶 𝑖 ) = sc(𝐶 𝑖 ), for any 𝐶 𝑖 ⊆ 𝐶.Proof. As a consequence of nondegeneracy, the essential set of any 𝐶 𝑖 ⊆ 𝐶 is unique and the statement follows immediately from Proposition 2. □IV. DISTRIBUTED RANDOM CONVEX PROGRAMS A. Problem StatementGiven a function 𝑓 : (ℝ 𝑑 × Δ) → ℝ, where Δ ⊆ ℝ ℓ is the sample space from which a vector of random parameters 𝛿 is drawn, the associated random constraint is defined by𝑓 (𝑥, 𝛿) ≤ 0. A random constraint is said to be convex if 𝑥 → 𝑓 (𝑥, 𝛿) is convex for all 𝛿 ∈ Δ.Consider a networked system with 𝑛 interacting nodes (e.g., processors, sensors). We model node communication by a digraph 𝐺 with vertex set {1, . . . , 𝑛} and edge set ℰ. Let 𝒩 in (𝑖) and 𝒩 out (𝑖) be the set of incoming and outgoing neighbors of node 𝑖, respectively. Denote the diameter of the graph 𝐺 by diam(𝐺). Suppose that node 𝑖 has a local set of random constraints, in the form 𝑓 𝐶 𝑖 , where 𝛿(𝑗) are realizations of some random variable and 𝐶 𝑖 is the set of indexes specifying the local constraint set, with 𝑁

𝑗 (𝑥) . = 𝑓 (𝑥, 𝛿 (𝑗) ), 𝑗 ∈ 𝑖 . = |𝐶 𝑖 |. Define 𝐶 = ∪ 𝑛 𝑖=1 𝐶 𝑖 , 𝑁 .

1 :

 1 Input: 𝑐, 𝐺, and 𝐶 𝑖 , ∀𝑖 ∈ {1, . . . , 𝑛} 2: Output: Scenario solution 𝑥 * (𝐶), active set ac(𝐶) % Initialization 3: Set 𝐴 𝑖 (0) = ac(𝐶 𝑖 ), for each 𝑖 ∈ {1, . . . , 𝑛}; 𝑡 = 1; % Update 4: if 𝐴 𝑖 (𝑡 -𝑙) = 𝐴 𝑖 (𝑡), ∀𝑙 ∈ {1, . . . , 2diam(𝐺) + 1} set ac(𝐶) = 𝐴 𝑖 (𝑡), 𝑥 Proposition 4: Consider a processor network defined over a graph 𝐺 and the distributed random convex program 𝑃 [𝜔]. The following statements hold under Assumptions 1 and 2: i) At each iteration of the Algorithm 1 each node transmits at most 𝑑 comb constraints to the outgoing neighbors; ii) The local optimal objective 𝐽 * (𝐴 𝑖 (𝑡)) is monotonically non-decreasing in the iterations 𝑡 and converges in a finite number of iterations, say 𝑇 , to the global optimal value 𝐽 * (𝐶); iii) At iteration 𝑇 , the local solution at a generic node 𝑖 is the same as the global solution; iv) For each node 𝑖 the local candidate set 𝐴 𝑖 (𝑇 ) at time 𝑇 coincides with the global active set ac(𝐶); v) If the distributed random convex program 𝑃 [𝜔] is almost surely nondegenerate, then the local probability of violation 𝑉 * (𝐴 𝑖 (𝑇 )) is equal to 𝑉 * (𝜔), the violation probability of the global solution obtained in

	5: else 𝐴 𝑖 (𝑡 + 1) = ac (	𝐴 𝑖 (𝑡) ∪	(	∪ 𝑗∈𝒩in(𝑖) 𝐴 𝑖 (𝑡)	)	∪ 𝐶 𝑖	)	;
	𝑡 = 𝑡 + 1; go to 4:;

* (𝐶) = 𝑥 * (𝐴 𝑖 (𝑡)); exit;

This work was funded by MACP4LOG grant (RU/02/26) from Piemonte Region, Italy, by PRIN grant n. 20087W5P2K from the Italian Ministry of University and Research, by NSF Award CPS 1035917 and by ARO Award W911NF-11-1-0092. The third author thanks Giuseppe Notarstefano for insightful discussions about abstract programming.

No. of constraints at each iteration. The algorithm assures finitetime convergence to the scenario solution, which preserves the probabilistic guarantees of the RCP theory. The theoretical derivation was then validated by means of numerical experiments on a distributed classification problem.

VII. APPENDIX Appendix I: Lexicographic Solution

We here discuss an approach for computing the unique lexicographic solution for a given convex optimization problem 𝑃 [𝐶]. Consider a generic convex problem, possibly not satisfying the unique minimum condition. We denote with 𝑂𝑝𝑥[𝐶] the optimal solutions set, i.e., 𝑂𝑝𝑥[𝐶] = {𝑥 | 𝑎 ⊤ 𝑥 = 𝐽 * (𝐶) and 𝑓 𝑗 (𝑥) ≤ 0, ∀𝑗 ∈ 𝐶}. We now want to compute the unique solution

etc. Proposition 5: Given the optimal objective 𝐽 * (𝐶) of a generic convex problem 𝑃 [𝐶], the lexicographic solution 𝑥 * can be obtained by solving the following convex program:

for some arbitrary small positive 𝜆.

Proof. We start by noticing that the feasible set of problem (6) corresponds to the optimal solutions set of the original program 𝑃 [𝐶]; this is consequence of the fact that the additional constraint 𝑎 ⊤ 𝑥 = 𝐽 * (𝐶) restricts the feasible set to the 𝑥 attaining the optimal value 𝐽 * (𝐶). Therefore it only remains to demonstrate that the coefficients of the optimization variables force the lexicographic ordering. For this purpose assume to have two solutions x * and x * , such that x * 1 -x * 1 .

= 𝛾 > 0. Let us consider the Euclidean ball of radius enclosing the compact domain 𝑋. If we call 𝐽 𝑙 (𝑥) the objective value of problem (6) at 𝑥, it is then easy to see that selecting 0 < 𝜆 < 𝛾 2(𝑑-1)𝑀 < 1 assures that 𝐽 𝑙 (x * ) > 𝐽 𝑙 (x * ):

Repeating the same reasoning for the remaining variables (e.g., comparing the objectives in the case in which x * 1 = x * 1 ) it is possible to show that, for some small 𝜆, problem [START_REF] Nedíc | Distributed subgradient methods for multi-agent optimization[END_REF] imposes the lexicographic ordering.

□ We notice that this approach is convenient if some reasonable bound 𝑀 is a priori known. In case this bound is not known or it may cause numerical problems (e.g., 𝜆 is comparable with the machine precision), it can be preferable to consider alternative approaches for computing the lexicographic solution, as the one presented in [START_REF] Calafiore | The scenario approach to robust control design[END_REF].

Appendix II: Support Constraints of Convex Programs

In this appendix we prove that every support constraints of a convex program has to belong to the active constraints set. Let 𝑐 be a support constraint for problem [START_REF] Ben-Tal | Robust optimization: Methodology and applications[END_REF]. Call x * = 𝑥 * (𝐶) and x * = 𝑥 * (𝐶∖{𝑐}). From the definition of support constraints, it holds that 𝑎 ⊤ x * < 𝑎 ⊤ x * . Suppose then, for the purpose of contradiction, that 𝑐 is not active at x * , i.e. that 𝑓 𝑐 (x * ) < 0. Consider a point 𝑧 on the segment connecting x * and x * :

* for all 𝜆 > 0. Moreover, by convexity, 𝑧(𝜆) is feasible for all constraints, except possibly for 𝑐. However, since x * is in the interior of the convex set defined by 𝑓 𝑐 ≤ 0, there must exist values of 𝜆 sufficiently small such that 𝑧(𝜆) satisfies also 𝑓 𝑐 (𝑧(𝜆)) ≤ 0. But then 𝑧(𝜆) would satisfy all constraints and yield an objective value that improves upon that of x * . This contradicts optimality of x * and hence proves that 𝑐 must be active at x * .


Ehud Lehrer
email: lehrer@post.tau.ac.il

Eilon Solan
email: eilons@post.tau.ac.il

Dario Bauso
email: dario.bauso@unipa.it

Repeated games over networks with vector payoffs: the notion of attainability (Invited Paper)

We introduce the concept of strongly attainable sets of payoffs in two-player repeated games with vector payoffs in continuous time. A set of payoffs is called strongly attainable if player 1 has a strategy guaranteeing, even in the worst case, that the distance between the set and the cumulative payoff shrinks with time to zero. We characterize when any vector is strongly attainable and illustrate the motivation of our study on a multiinventory application.

I. INTRODUCTION

In the literature on multi-inventory control [START_REF] Bauso | Optimization of long-run average-flow cost in networks with time-varying unknown demand[END_REF], [START_REF] Blanchini | Control of productiondistribution systems with unknown inputs and system failures[END_REF], [START_REF] Blanchini | Least inventory control of multi-storage systems with non-stochastic unknown input[END_REF], the supplier tries to meet the demand, which is multi-dimensional and given in continuous time. The goal of the supplier is to ensure that the difference between the total demand up to time T and the total supply up to time T converges to 0, as T goes to infinity. The literature on Approachability theory, which was initiated by [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF], answers a similar question (see, e.g., [START_REF] Lehrer | Approachability in infinite dimensional spaces[END_REF]), when one considers the average demand and average supply instead of total demand and total supply.

Motivated by the problem of multi-inventory control, we study in this paper two-player repeated games in continuous time with vector payoffs. We define a new concept, the concept of strongly attainable sets, which is close in spirit to the concept of approachable sets: a set A in the payoff space is strongly attainable if player 1 has a strategy such that, for every strategy of player 2, the total payoff up to time T converges to the set A.

The main contribution of this paper are conditions that ensure that all payoff vectors are strongly attainable.

II. PROBLEM SETUP AND BACKGROUND

A. System model

We study a two-player repeated game with vector payoffs in continuous time. The set of players is N = {1, 2}, and the finite set of actions of each player i is A i . The instantaneous payoff is given by a function u : A 1 × A 2 → R m . We assume w.l.o.g. that payoffs are bounded by 1, so that in fact u :

A 1 × A 2 → [-1, 1] m . We extend u to ∆(A 1 ) × ∆(A 2
) in a multi-linear fashion. We denote the one-shot vector-payoff game (A 1 , A 2 , u) by G.

We study non-anticipating behavior strategies with delay. Denote by a t i the mixed action chosen by player i in time t.

τ k i ≤ t < τ k+1 i .
In the sequel we will refer to the stopping times (τ k i ) k∈N in Definition 1 as the stopping times in the definition of a i or as the stopping times related to σ i .

Every pair of non-anticipating strategies with delay σ = (σ i ) i∈N uniquely determines the play path (a t (σ)) t∈R+ . The payoff vector up to time T associated with the pair of strategies σ is given by

γ T (σ) = T 0 u(a t (σ))dt.
Since payoffs are bounded by 1, the integral, which is the cumulative payoff up to time T , is well-defined.

For every set A ⊆ R m we denote by B(A, ε) the set of all points whose distance from at least one point in A is less than ε:

B(A, ε) := {x ∈ R m : d(x, A) < ε}.
When A is a single point x, we write B(x, ε) instead of B({x}, ε).

In this paper we present two new concepts: attainable sets and strongly attainable sets.

Definition 2: (i) The set A ⊆ R m is strongly attainable by player 1 if there is a strategy σ 1 for player 1 such that for every strategy σ 2 of player 2,

lim T →∞ d(γ T (σ), A) = 0. (1)
(ii) The set A is attainable by player 1, if the set B(A, ε) is strongly attainable for every ε > 0.

The definition of an attainable set looks similar to that of approachable set in games played over discrete set of times (see [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF]. There is, however, a significant difference between the two.

Notation 1: For every mixed action p ∈ ∆(A 1 ) denote by

D 1 (p) = {u(p, q) : q ∈ ∆(A 2 )},
the set of all payoffs that can occur when player 1 plays the mixed action p.

Our goal is to provide a geometric characterization to attainable sets. To this end we define a condition related to auxiliary zero-sum scalar-payoff games. Let λ ∈ R m . Denote by λ, G the zero-sum game whose set of players and their action sets are as in the original game G. Player

1's payoff 1 is λ, u(a 1 , a 2 ) for every (a 1 , a 2 ) ∈ A 1 × A 2 .
As a zero-sum game, the game λ, G has a value, denoted v λ . The inequality v λ > 0 means that there is a mixed action

p ∈ ∆(A 1 ) such that D 1 (p) is a subset of the open half space {x ∈ R m : λ, x > 0}.
Definition 3: (i) Let B ⊆ R m be a subspace and S ⊆ ∆(A 1 ) be a subset of player 1's mixed strategies. We say that the payoff function

u satisfies condition C(B, S) if for every 2 open half space H of B, there is a mixed action p ∈ S such that D 1 (p) ⊆ H. (ii) If B = R m and S = ∆(A 1 ) we say that u satisfies condition C. Note that condition C is satisfied if and only if v λ > 0 for every λ ∈ R m .
Remark 1: Standard continuity and compactness arguments imply that if u satisfies condition C, then there is δ 1 > 0 such that for every half space F there is p ∈ ∆(A 1 ) satisfying d(D 1 (p), F )) ≥ δ 1 . Stated differently, there is δ 2 > 0 such that for every vector λ whose ℓ 1 -norm is 1, u(p, q), λ < -δ 2 for every q ∈ ∆(A 2 ).

The following theorem establishes that condition C is equivalent to all vectors being attainable.

Theorem 1: The following statements are equivalent C1 Every vector x ∈ R m is strongly attainable; C2 Every vector x ∈ R m is attainable; C3 The payoff function u satisfies condition C.

III. PROOF OF THEOREM 1

We show first that C3 implies C1. Assume that condition C is satisfied. Fix a vector x. We show that x is strongly attainable.

We define a strategy σ 1 . Fix a constant η = 1 and let τ k 1 be defined inductively as

τ k 1 = 0 k = 1, τ k-1 1 + η k k > 0.
(

) 2
Denote the payoff up-to time τ k 1 by S k . σ 1 (t) is defined to be an optimal strategy of player 1 in the game

x -S k , G , for τ k 1 ≤ t < τ k+1 1 . That is, σ 1 is constant in the interval [τ k 1 , τ k+1 1
). In case x -S k = 0, σ 1 (t) in this interval is 1 Recall that x, y = m i=1 x i y i for every x, y ∈ R m . 2 H is an open half space if it is of the form {x; x, λ > 0} for some λ ∈ R m . equal to a mixed action that guarantees that the payoff and x -S k lie on different sides of the hyperplane perpendicular to x -S k . Moreover, in light of Remark 1, there is δ 2 > 0 such that when σ 2 is the strategy played by player 2, x-S k

x-S k 1 , u(σ 1 (t), σ 2 (t)) < -δ 2 . Denote by a k the payoff accumulated in the interval

[τ k 1 , τ k+1 1
). Thus,

x -S k 2 = x -S k-1 - 1 k a k 2 = x -S k-1 2 + 1 k 2 a k 2 + 2 1 k x -S k-1 1 x -S k-1 x -S k-1 1 , a k . (3)
Thus, x -S k is smaller than x -S k-1 as long as

1 k 2 a k 2 + 2 1 k x -S k-1 1 x -S k-1 x -S k-1 1 , a k < 0. ( 4
)
Recalling that a k 2 ≤ 1, we infer that Eq. ( 4) occurs when

1 2kδ 2 < x -S k-1 1 . (5)
We claim that lim inf x -S k = 0. Otherwise, from a certain k 0 on x -S k > ε > 0, meaning that from a certain k 0 on Eq. ( 5) is satisfied. But then for every K > k 0 we obtain from Eq. ( 3) that

x -S k 2 ≤ K k=k0 1 k 2 a k 2 + 2 1 k x -S k-1 1 x -S k-1 x -S k-1 1 , a k ≤ K k=k0 1 k 2 a k 2 + 2 1 k ε(-δ 2 ). (6)
Since the RHS converges to -∞, it implies that the LHS is negative for K large enough, which is a contradiction. Thus indeed, lim inf x -S k = 0.

We show now that lim sup x -S k = 0. Fix an ε > 0. By the previous claim there are infinitely many k's for which

x -S k 2 < ε. If x -S k 2 < ε, then x -S k+1 2 < ε + 1 k 2 a k 2 + 2 1 k x -S k-1 1
x-S k-1

x-S k-1 1 , a k < 2ε for k sufficiently large. But when k is large enough 1 2kδ2 < ε, and then Eq. ( 5) is satisfied. In this case x -S k+2 2 < x -S k + 1 2 . In other words, for k large enough, if x-S k 2 < ε, then the next time distance squared, x -S k + 1 2 , cannot jump beyond 2ε. And if this figure jumps above ε, the distance x -S ℓ is then starting to go down. Thus, for k large enough once x -S k 2 is smaller than ε, it will remain smaller than 2ε for ever. We conclude that lim sup x -S k 2 < 2ε and since ε is arbitrary, it shows C1.

It is clear that C1 implies C2 and it remains to show that C2 implies C3. Assume that the payoff function u does not satisfy condition C. Then there exists a half space H such that D 1 (p) is not a proper subset of H, for every p ∈ ∆(A 1 ). From the minimax theorem this implies that there is q ∈ ∆(A 2 ) such that D 2 (q) is disjoint of H. But then any vector x ∈ H is not attainable by player 1, simply because the strategy σ 2 that constantly plays q generates a cumulative payoff that, regardless of σ 1 being player by player 1, is always out of H, which shows that C2 is not satisfied.

IV. CASE STUDY

In this section we carry out a numerical analysis aimed at simulating the play path and integral payoff of a given game. The game under consideration is displayed below

    (6, 7) (1, 7) (6, 2) (1, 2) (6, -4) (1, -4) (6, -9) (1, -9) (-3, -1) (-8, -1) (-3, -6) (-8, -6) (-3, 10) (-8, 10) (-3, 5) (-8, 5)     . ( 7
)
The game is obtained starting from the following multiinventory case study.

f 1 f 2 f 3 w 1 w 2 Fig. 1. Network system.
Consider the system depicted in Fig. 1 representing two warehouses, three controlled flows and two uncontrolled flows. A unit of flow f 1 produces one unit of product γ 1 per time unit. Similarly, flow f 2 uses one unit of γ 1 to produce one unit of γ 2 per time unit. A unit of flow f 3 produces one unit of product γ 2 per time unit. Uncontrolled flows w 1 and w 2 represent the exogenous demand of resource γ 1 and γ 2 respectively. The associated dynamics reads then:

γt 1 γt 2 = u((a t 1 , a t 2 )) = 1 -1 0 0 1 1 F   f t 1 f t 2 f t 3   a t 1 - w t 1 w t 2 a t 2 .
Now, suppose that flows can be processed only in batches and therefore take for instance f i ∈ {-5, -2, 1, 6}, and w i ∈ {-3, 2}.

Let us enumerate all the actions of player 1 and 2, so that we have A 1 = {a 11 , . . . , a 1r } and A 2 = {a 21 , . . . , a 2q } with r = 4 3 and q = 2 2 , where a ij denotes the jth action of player i.

The complete matrix of vector payoffs is then obtained from the following table, where each entry represents a possible vector payoff u((a 1 , a 2 )):

a 1 /
λ = (φ, 1 -φ) ∈ R 2 FOR DIFFERENT φ'S.
As it will be clearer later on, to our purposes we can simply extract from the above table the rows associated to the following four actions of player 1:

a 11 = (1, -2, 6), a 12 = (1, -2, -5), a 13 = (-5, 1, -5), a 14 = (-5, 1, 6).
This procedure reduces the vector payoff matrix to the 4 × 4 matrix displayed in (7).

In fact, the above game satisfies condition C as v λ > 0 for every λ ∈ R m . Thus, the theoretical results developed in the previous part of the work (see in particular Theorem 1) establish that any vector x ∈ R 2 is strongly attainable for this game.

To see that v λ > 0 for every λ ∈ R m , we study the one shot game λ, G where λ = (φ, 1 -φ) ∈ R 2 for φ = 0, 0.1, . . . 1. More specifically, let U λ be the payoff matrix and U ′ λ its transposed, and consider the optimization variables p = p v λ . Then for each λ we solve the linear program below using Matlab in-built function linprog:

(LP ) min{ p 1 | U ′ λ p ≥ 1, p ≥ 0}.
The value of the game is then obtained as v λ = 1 p 1 . In Table I we display the values of the game λ, G for different φ's. Note that the minimum v λ = 1 in correspondence to φ = 1.

We are now in the position to start with the Monte Carlo simulations. We perform 20 sample paths, and in each one the attainable vector x is randomly chosen with uniform distribution from the interval [-1, 1]. At the end of all the 20 sample paths, we compute the sampled average of the variables of interest (integral payoff γ T (σ), distance d(x, γ T (σ)) a.s.o), namely, we average over all the 20 trajectories for varying time T .

To avoid numerical issues, we set the initial payoff γ 0 (σ) = (0.1, 0.1). Each sample path has horizon length τ k 1 with k = 1, . . . , 200, and each interval

[τ k 1 , τ k+1 1
] is subdivided into 10 steps, i.e, the basic length of the interval is

τ k+1 1 -τ k 1 10
. In spirit with the proof of Theorem 1, for each period k = 1, . . . , 200, we denote the payoff up-to time τ k 1 by S k . Then, the strategy of player 1 σ 1 (t) is the optimal strategy in the game

x -S k , G , for τ k 1 ≤ t < τ k+1 1 . More specifically, σ 1 is constant-wise over the intervals [τ k 1 , τ k+1 1
), k = 1, . . . , 200. From a computational standpoint, σ 1 is obtained solving the aforementioned linear program (LP ) with λ = x -S k .

Without loss of generality, we also take σ 2 (t) = (1/4, 1/4, 1/4, 1/4) namely we assume that player 2 simply randomizes over a 2 = 1, . . . , 4 with uniform distribution.

All simulations are carried out with MATLAB on an Intel(R) Core(TM)2 Duo CPU P8400 at 2.27 GHz and a 3GB of RAM. The run time of the only Monte Carlo simulations is about 60 seconds. The results of the simulations are summarized in Figs. 2 to 5.

Figure 2 shows the time plot of sampled average of x -γ T (σ). In accordance to Theorem 1, any x is strongly attainable and therefore we do expect the trajectories converge to zero as in fact depicted in the figure. For the same simulations, Fig. 3 shows the time plot of sampled average of the distance d(γ T (σ), x). Again, from Theorem 1, strongly attainability of x implies that the distance tend to zero as illustrated in the plot. Looking at a single path out of the 20 simulations, we plot in Fig. 4 the trajectory x-γ T (σ) for varying time T where we have set as attainable vector x = (0.1, 0.8). The plot shows that the trajectory of the integral payoff γ T (σ) converges to the prescribed attainable vector x.

Finally, Fig. 5 illustrates the distance d(γ T (σ), x) for varying steps N (rather than time T ) in the same single simulation mentioned above. The plot shows the converging nature of the trajectory as a function of 1 √ N .

V. CONCLUSIONS

We have introduced the concept of strongly attainable sets of payoffs in two-player repeated games with vector payoffs in continuous time. In particular, a set of payoffs is called strongly attainable if player 1 has a strategy that guarantees, even in the worst case, that the distance between the set and the cumulative payoff tends to zero.

As main result we study conditions under which any vector is strongly attainable. Results are illustrated in the context of multi-inventory applications.

Fig. 2 .

 2 Fig. 2. Sampled average of xγ T (σ) vs. time T .

Fig. 3 .

 3 Fig. 3. Sampled average of distance d(γ T (σ), x) vs. time T .

Fig. 4 .

 4 Fig. 4. γ T (σ) vs. time T with x = (0.1, 0.8).

Fig. 5 .

 5 Fig. 5. Distance d(γ T (σ), x) vs. steps N with x = (0.1, 0.8).

ACKNOWLEDGMENT

This research was supported in part by the Google Interuniversity center for Electronic Markets and Auctions. Lehrer acknowledges the support of the Israel Science Foundation, Grant #762/045. Solan acknowledges the support of the Israel Science Foundation, Grant #212/09.


David S Leslie

Jason R Marden

Equilibrium Selection in Potential Games with Noisy Rewards

Game theoretical learning in potential games is a highly active research area stemming from the connection between potential games and distributed optimisation. In many settings an optimisation problem can be represented by a potential game where the optimal solution corresponds to the potential function maximizer. Accordingly, significant research attention has focused on the design of distributed learning algorithms that guarantee convergence to the potential maximizer in potential games. However, there are currently no existing algorithms that provide convergence to the potential function maximiser when utility functions are corrupted by noise. In this paper we rectify this issue by demonstrating that a version of payoff-based loglinear learning guarantees that the only stochastically stable states are potential function maximisers even in noisy settings.

I. INTRODUCTION

The current intensive interest in learning in games places great emphasis on designing learning algorithms which will converge to the set of Nash equilibria in classes of games. When the paradigm is used to study distributed optimisation it is usually possible to ensure that the players only need to learn in a potential game [START_REF] Arslan | Autonomous vehicletarget assignment: a game theoretical formulation[END_REF], [START_REF] Chapman | A unifying framework for iterative approximate best response algorithms for distributed constraint optimisation problems[END_REF], [START_REF] Marden | Cooperative control and potential games[END_REF], [START_REF] Monderer | Potential games[END_REF]. However, the convergence to Nash equilibrium does not actually tell us a great deal about the performance of the optimisation algorithm as a Nash equilibrium could be highly inefficient with regards to the system level objective [START_REF]Algorithmic Game Theory[END_REF], [START_REF] Roughgarden | Selfish Routing and the Price of Anarchy[END_REF]. In many settings, the potential corresponds to the system level objective so it is desirable to find a learning algorithm which will converge to the global optimum of the potential function [START_REF] Arslan | Autonomous vehicletarget assignment: a game theoretical formulation[END_REF].

Log-linear learning [START_REF] Blume | The statistical mechanics of strategic interaction[END_REF], [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] is a process which is known to converge to the global optimum of the potential function. It does so by the use of simulated-annealing-like transitions between actions [START_REF] Geman | Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images[END_REF], although the lack of a central controller means that we lose the ability to insist that exactly one individual updates their action at each time step. However the standard formulation of log-linear learning [START_REF] Blume | The statistical mechanics of strategic interaction[END_REF], and many other game-theoretical algorithms, assumes that all players know their own complete reward function (the map from joint action space to the real line) and can observe the actions of all other players in the game. In the very control-theoretic situations in which game theory is supposed to contribute, these assumptions are very unlikely to hold-the games are probably not well-understood in advance, and the distributed nature of the optimisation problem means that observation of all other players is highly problematic.

A payoff-based implementation of log-linear learning has recently been introduced [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] which allows players to learn even when they do not observe opponent actions, and simply respond to received rewards. However this algorithm still requires that the received rewards are deterministic functions of the actions selected by the players which is also unlikely to hold in applications. The received payoff for a particular selection of actions is much more likely to be a random variable with an expected value that is aligned with this deterministic payoff. Hence, the convergence of log-linear learning in this setting is unknown.

Stochasticity in payoffs may arise, not only naturally as a result of stochasticity in the problem, but as a necessary consequence of utility function design [START_REF] Marden | Distributed welfare games[END_REF]. If the utility of a problem is divided among the players using the Shapley value, then calculation of an individual's utility requires a summation over n! terms, where n is the number of players involved in a particular resource. When n is large this is prohibitively expensive, but it is easy to sample utility values with expectation equal to the Shapley value [START_REF] Conitzer | Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains[END_REF]. This sampling to ease computation naturally gives rise to utilities of the form we consider in this article.

In this paper we present an algorithm that extends the payoff-based implementation of log-linear learning [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] to the case of stochastic rewards. The modification of the original formulation is simply to sample repeated observations of the rewards for each joint action instead of observing a single sample; the challenge we address in this article is to show that the inaccurate estimates do not affect the stochastic stability results of the original analysis [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF]. Note that a very similar technique could be used to analyse numerous algorithms under a similar modification to accommodate stochastic rewards.

II. PROBLEM STATEMENT AND ALGORITHM

We consider a finite strategic-form game with player set I = {1, . . . , n}. Each player i ∈ I has a finite action set A i and a utility function U i : A → R where A = i∈I A i . For an action profile a = (a 1 , a 2 , . . . , a n ) ∈ A, let a -i denote the profile of player actions other than player i. With this notation, we will sometimes write a joint action a ∈ A as (a i , a -i ). Similarly we may write U i (a) as U i (a i , a -i ). We define player i's best response set for an action profile a -i ∈ A -i = j =i A j as

B i (a -i ) = argmax ai∈Ai U i (a i , a -i ).
A Nash equilibrium is any joint action a such that ∀i ∈ I, a i ∈ B i (a -i ).

As indicated in the introduction, many distributed optimisation scenarios may be cast as a potential game. In a potential game, the change in a player's utility that results from a unilateral change in strategy is equal to the change in the global potential function. Specifically, there exists a function

φ : A → R such that ∀i ∈ I, ∀a -i ∈ A -i , ∀a i , a ′ i ∈ A i , U i (a i , a -i ) -U i (a ′ i , a -i ) = φ(a i , a -i ) -φ(a ′ i , a -i ).
Any joint action a maximising the potential function φ is a Nash equilibrium, and so every potential game possesses at least one equilibrium without resorting to mixed strategies.

One way in which distributed optimisation is encoded as a potential game is using the Wonderful Life Utility (WLU) [START_REF] Arslan | Autonomous vehicletarget assignment: a game theoretical formulation[END_REF], [START_REF] Wolpert | An overview of collective intelligence[END_REF], in which individual utility functions are given by

U i (a i , a -i ) = G(a i , a -i ) -G(å i , a -i )
where åi is an arbitrary reference action of player i and G is the global system utility. If the reference action corresponds to 'do nothing' then the WLU payoff to player i corresponds to the marginal contribution to the global utility made by i. For this form of utility it is easily verified that the global utility G acts as a potential function for the game. It is therefore important to know whether the players can reach the global optimum of the potential function of such a game.

Log-linear learning (LLL) [START_REF] Blume | The statistical mechanics of strategic interaction[END_REF], [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] is one of very few algorithms that achieves selection of the equilibrium corresponding to the potential function maximiser. In particular, LLL guarantees that only the joint actions that maximise the potential function are stochastically stable. However all current implementations of LLL assume either that the utility functions are known in advance, or (for payoff-based LLL [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] as described in Algorithm 1) that players observe uncorrupted values of this utility function. In real life implementations of game-theoretical learning for optimisation it is likely that the utility functions are not known in advance, and that observed utilities are subjected to noise. We encapsulate this feature of real distributed optimisation in the following modelling assumption.

Assumption (Noisy rewards): When players select joint action a ∈ A, each player i receives a reward R i = U i (a) + ξ i where the perturbations ξ i have expectation 0, variance V i (a), and are independent of all other random variables.

We therefore require a variant of log-linear learning that can accommodate the stochasticity in the received rewards. Indeed, the algorithm we propose (Algorithm 2) is a direct modification of payoff-based LLL [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] in which the players sample multiple copies of the rewards for each action instead of using a single observation. In our modification, a time counter t no longer indexes single plays of the game, but instead indexes blocks of plays of length 2N . In the first half of each block the players repeat action a(t -1) for N further plays to get a new estimate Û t i (a(t -1)) of U i (a(t -1)); in the second half of block the players play action a(t) for N iterations to obtain an estimate Û t i (a(t)) of U i (a(t)). Let x i (t) be the indicator of whether Player i experiments on block t. If x i (t -1) = 0 then either (with high probability) a i (t) = a i (t -1) and Player i doesn't experiment (x i (t) = 0); otherwise a i (t) is selected uniformly at random from |A i | (Player i experiments:

Algorithm 1 Payoff based log-linear learning [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] Fix parameters τ , ω, and for each i ∈ I set x i (0) = 0 and select a i (0) arbitrarily from A i . For each t ∈ N, each i ∈ I carries out the following:

if x i (t -1) = 0 then {player i did not experiment} With probability 1 -ω set x i (t) = 0, a i (t) = a i (t -1)
Otherwise set x i (t) = 1 and select a i (t) uniformly at random from A i . else {i.e. if x i (t -1) = 1, player i did experiment} Set x i (t) = 0, and set

a i (t) =      a i (t -2) w.p. e 1 τ U i (a(t-2)) e 1 τ U i (a(t-2)) +e 1 τ U i (a(t-1))
a i (t -1) w.p.

e 1 τ U i (a(t-1)) e 1 τ U i (a(t-2)) +e 1 τ U i (a(t-1))
end if

x i (t) = 1). If x i (t-1) = 1, so that a i (t-1) was experimental, then action a i (t) is selected according to a logistic function of the estimates Û t-

1 i = ( Û t-1 i (a(t -2)), Û t-1 i (a(t -1)
)) and x i (t) = 0. Note that the advantage of such a payoffbased scheme is that each player does not need to have information regarding the other players of the game or even their own payoff function-each player simply updates their current action according to the rewards they observe.

Algorithm 2 Sampled payoff based log-linear learning

Fix parameters τ , ω, N , and for each i ∈ I set x i (0) = 0 and select a i (0) arbitrarily from A i . For each t ∈ N, each i ∈ I carries out the following: if x i (t -1) = 0 then {player i did not experiment} With probability 1 -ω set x i (t) = 0, a i (t) = a i (t -1) Otherwise set x i (t) = 1 and select a i (t) uniformly at random from A i . else {i.e. if x i (t -1) = 1, player i did experiment} Set x i (t) = 0, and set

a i (t) =      a i (t -2) w.p. e 1 τ Û t-1 i (a(t-2)) e 1 τ Û t-1 i (a(t-2)) +e 1 τ Û t-1 i (a(t-1)) a i (t -1) w.p. e 1 τ Û t-1 i (a(t-1)) e 1 τ Û t-1 i (a(t-2)) +e 1 τ Û t-1 i (a(t-1))
end if Play action a i (t -1) for N plays of the game, and let Û t i (a(t -1)) be the average reward obtained. Play action a i (t) for N plays of the game, and let Û t i (a(t)) be the average reward obtained.

Note that, even with N = 1, this algorithm differs slightly from Algorithm 1, in that within 'block' t we start by repeating action a(t -1) before playing action a(t). The reason for this repetition is so that we can write down a transition probability on a discrete state space (comprising of actions and experimental status x only). If the action value estimates from block t -1 were to be carried forward from block t -1 into block t + 1 to be used for action selection then the state space of the Markov chain becomes more complicated. We have no doubt that very similar conclusions could be drawn if this repetition were not to be carried out, but for the sake of brevity, and to retain the framework of discrete state space stochastic stability, we modify the algorithm to ensure that we have a discrete space Markov chain.

III. CONVERGENCE OF ALGORITHM 1 WITHOUT STOCHASTIC REWARDS

In this section we prove convergence of Algorithm 2 when there is no stochasticity in the received rewards. Under this scenario Û t i (a(t-1)) ≡ U i (a(t-1)) and Û t i (a(t)) ≡ U i (a(t)). Proposition 1: Consider any finite n-player potential game with potential function φ : A → R where all players adhere to Algorithm 2. Set ω = (e -1/τ ) m . If V i (a) = 0 for all i and a (i.e. rewards are deterministic) then for sufficiently large m the stochastically stable states are contained in the set of potential function maximisers.

Proof: Following [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF], write z(t) = [a(t -1), a(t), x(t)] ∈ A × A × {0, 1} n for the state of the Markov chain, ǫ = e -1/τ , and P ǫ z(t)→z(t+1) for the transition probabilities of the chain. Suppose that z(t) = [a(t -1), a(t), x(t)] → z(t + 1) = [a(t), a(t + 1), x(t + 1)] is a valid transition of the chain (i.e.

x i (t) = x i (t + 1) = 0 ⇒ a i (t + 1) = a i (t), x i (t) = 1 ⇒ (x i (t + 1) = 0 and a i (t + 1) ∈ {a i (t -1), a i (t)})). As in the proof of Claim 6.1 of [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF], the transition probability is given by

P ǫ z(t)→z(t+1) =   i:xi(t)=0,xi(t+1)=0 (1 -ω)     i:xi(t)=0,xi(t+1)=1 ω |A i |   ×   i:xi(t)=1,ai(t+1)=ai(t-1)
ǫ -Ui(a(t-1)) ǫ -Ui(a(t-1)) + ǫ -Ui(a(t))

  ×   i:xi(t)=1,ai(t+1)=ai(t) ǫ -Ui(a(t)) ǫ -Ui(a(t-1)) + ǫ -Ui(a(t))   . ( 1
)
Since this is identical to the transition matrix of the original payoff-based implementation the conclusion of Theorem 6.1 of [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] continues to hold.

IV. SAMPLED LLL HAS THE SAME LIMIT BEHAVIOUR

We now re-introduce stochasticity in the received rewards. To ease notation, throughout this section we fix t, and recall that Û t i = ( Û t i (a(t-1)), Û t i (a(t)). Note that the only resulting change in the transition probabilities of the Markov chain when compared with the deterministic case is in the decision of player i over which action to select at time t+1 if x i (t) = 1 (i.e. the player experimented on the previous block). We will show that by increasing the number of samples N at an appropriate rate as τ → 0 the stochastically stable states of the learning process are not changed.

Proposition 2: Consider any finite n-player potential game with potential function φ : A → R where all players observe noisy rewards (as in the assumption above) and adhere to Algorithm 2. Set ω = (e -1/τ ) m and set

N = g(τ )(1 + e ∆max/τ ) f (τ ) 2 τ 2 , ( 2
)
where f is any function that tends to 0 as τ → 0, g is any function that tends to ∞ as τ → 0, and ∆ max is the maximum difference in reward between any two actions for any player.

Then for sufficiently large m the stochastically stable states are contained in the set of potential function maximisers.

Proof: The method we will use is to show that transitions of Algorithm 2 have the same resistance [START_REF] Young | The evolution of conventions[END_REF] as the transitions when V i (a) ≡ 0 (i.e. the situation covered by Prop. 1). Consider equation [START_REF] Arslan | Autonomous vehicletarget assignment: a game theoretical formulation[END_REF]; in particular notice that the terms

k i (a(t); z(t)) := ǫ -Ui(a(t)) ǫ -Ui(a(t-1)) + ǫ -Ui(a(t)) are simply P(a i (t + 1) = a i (t) | z(t))
where the probability is calculated for when there is no stochasticity. (In what follows, whatever is said for k i (a(t); z(t)) also holds for the equivalently defined k i (a(t-1), z(t)) but we do not repeat the analysis.) In the version where we use estimates Û t i we need to take an expectation over these sampled values to calculate the corresponding probability, and thus the k i terms in (1) are replaced by terms ki (a(t); z(t)) := E ǫ -Û t (a(t))

ǫ -Û t (a(t-1)) + ǫ -Û t (a(t)) z(t) .

We will show that ki (a(t); z(t))

k i (a(t); z(t)) → 1 as τ → 0. (3)
Define P τ z 0 →z 1 to be the transition probability from state z 0 to state z 1 when sampling is used. Under (3), ∀η > 0

P τ z 0 →z 1 = P τ z 0 →z 1 P τ z 0 →z 1 P τ z 0 →z 1 ≤ (1 + η)P τ z 0 →z 1 ≥ (1 -η)P τ z 0 →z 1
for sufficiently small τ (since the ratio tends to 1). Hence P τ z 0 →z 1 → P τ z 0 →z 1 , the resistance [START_REF] Young | The evolution of conventions[END_REF] of each transition is the same under Algorithm 2 as under Algorithm 1, and the conclusion of Prop. 1 continues to hold. To ease notation, for the rest of the proof we condition all probability statements on z(t)

To show (3), start by noting that the action selection decision (and in particular k or k) depends only on the difference between rewards, and we define

∆ i := U i (a(t)) -U i (a(t -1)), ∆i := Û t i (a(t)) -Û t i (a(t -1)) so that k i (a(t); z(t)) = (1 + ǫ ∆i ) -1 . (4)
By our assumption that the random rewards received by player i on each play of the game are independent, with expectation U i (a) and variance V i (a) when joint action a is played,

E( ∆i ) = ∆ i and Var( ∆i ) = V N (5)
where V = V i (a(t)) + V i (a(t -1)). Now consider the event

A δ := {|∆ i -∆i | < δ}, (6)
under which the estimated difference between the actions is close to the true difference. Clearly, when A δ occurs, the transition probabilities under sampling are close to those under perfect reward information. We will show that we can increase the probability of A δ sufficiently quickly to ensure that k overall is close to k. First note that by Chebychev's inequality (see for example [START_REF] Grimmett | Probability and Random Processes[END_REF])

P( Āδ ) ≤ V N δ 2 (7)
where Āδ is the complement of A δ . We now use the partition theorem of probability to see that ki (a(t); z(t)) = P(a

i (t + 1) = a i (t) | A δ )P(A δ ) +P(a i (t + 1) = a i (t) | Āδ )P( Āδ ). Hence | ki (a(t); z(t)) -k i (a(t); z(t))| ≤ P(a i (t + 1) = a i (t) | A δ ) -k i (a(t); z(t)) P(A δ ) + P(a i (t + 1) = a i (t) | Āδ ) -k i (a(t); z(t)) P( Āδ )
The final line is bounded above by 2V /(N δ 2 ), by [START_REF] Marden | Cooperative control and potential games[END_REF] and noting that probabilities are less than 1. Note also that the absolute value of the derivative of (4) with respect to and to prove (3) it suffices to show that the right hand side of this expression tends to 0. In particular if we can show that δ τ → 0, and

∆ i is τ -1 k i (a(t); z(t))(1 -k i (a(t); z(t))) ≤ τ -1 k i (a (
N δ 2 k i (a(t); z(t)) → ∞ (8)
then the result is proved. Note that δ is chosen for our convenience in this proof, so let δ = τ f (τ ), where f is any function that tends to 0 as τ → 0, and (8) will be satisfied. Now note that k(a(t); z(t)) ≥ (1 + ǫ ∆max ) -1 where ∆ max is the maximal utility difference between two actions; therefore (9) holds if

N = g(τ )(1 + e ∆max/τ ) f (τ ) 2 τ 2 ,
where g is any function that tends to infinity as τ → 0. Hence by suitable choice of N we can ensure that the resistance of any transition under Algorithm 2 is the same as the transition when there is no stochasticity. The result of Prop. 1 therefore continues to hold.

V. CONCLUSION

We have extended the method of log-linear learning to the situation where players only observe noisy evaluations of their payoffs and cannot observe actions selected by 'opponents'. We have modified the original proof that only potential function maximisers are stochastically stable [START_REF] Marden | Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation[END_REF] by showing that transitions under sampled reward values have the same resistance as transitions of the algorithm when there is no stochasticity, provided that the number of samples increases at a suitable rate. This is therefore the first algorithm that is proved to select the Nash equilibrium corresponding to the maximum of the potential function under noisy reward observations. This result is important for the application of learning in games to distributed optimisation problems, since distributed optimisation resorts to game theory in precisely the situations where the 'game' is not well-defined in advance, and when payoffs are subject to stochastic shocks. Since standard results on learning in games usually assume, as a minimum, that players receive a payoff equal to the deterministic utility function of the played joint action, the extension to stochastic rewards is an important bridge between the theoretical convergence results and the application scenarios of interest.