Vivek S Borkar
email: borkar.vs@gmail.com

Alexandre Reiffers-Masson
email: reiffers.alexandre@gmail.com

Robert Bosch

Opinion shaping in social networks using reinforcement learning

Recent studies have demonstrated that the decisions of agents in society are shaped by their own intrinsic motivation, and also by the compliance with the social norm. In other words, the decision of acting in a particular manner will be affected by the opinion of society. This social comparison mechanism can lead to imitation behavior, where an agent will try to mimic the behavior of her neighbors.

Using this observation, new policies have been designed, e.g., in the context of energy efficiency and transportation choice, to leverage social networks in order to improve altruism and prosocial behavior.

One policy is to use targeting strategies. Indeed, by changing the behavior of influential actors in a social network, it is possible to reshape the global behavior of agents towards more prosocial behavior.

However, discovering who are the influential agents requires a lot of information, such as the matrix of interactions between agents. In this paper, we study how to shape opinions in social networks when the matrix of interactions is unknown. We consider classical opinion dynamics with some stubborn agents and the possibility of continuously influencing the opinions of a few selected agents, albeit under resource constraints. We map the opinion dynamics to a value iteration scheme for policy evaluation for a specific stochastic shortest path problem. This leads to a representation of the opinion vector as an Work supported in part by a J. C.

approximate value function for a stochastic shortest path problem with some non-classical constraints.

We suggest two possible ways of influencing agents. One leads to a convex optimization problem and the other to a non-convex one. Firstly, for both problems, we propose two different online two-time scale reinforcement learning schemes that converge to the optimal solution of each problem. Secondly, we suggest stochastic gradient descent schemes and compare these classes of algorithms with the twotime scale reinforcement learning schemes. Thirdly, we also derive another algorithm designed to tackle the curse of dimensionality one faces when all agents are observed. Numerical studies are provided to illustrate the convergence and efficiency of our algorithms.

Index Terms

Social Networks; Opinion Shaping; Reinforcement Learning; Stochastic Shortest Path

I. INTRODUCTION

In recent times there has been increasing interest in non-price based mechanisms to improve society's behavior in the context of, e.g., energy efficiency or traffic behavior. These policies are usually less expensive to implement and can be politically feasible as opposed to price based policies. One example is the use of lottery with the distribution of coupons for energy efficiency [START_REF] Xia | Energycoupon: A case study on incentive-based demand response in smart grid[END_REF] or for promoting off-peak usage of cars [START_REF] Merugu | An incentive mechanism for decongesting the roads: A pilot program in bangalore[END_REF]. Another example is of leveraging social network for enhancing pro-social behavior. Indeed, social interactions can impact day to day decisions of an agent. For instance, in transportation choice, several works ( [START_REF] Dugundji | Discrete choice with social and spatial network interdependencies: an empirical example using mixed generalized extreme value models with field and panel effects[END_REF], [START_REF] Walker | Correcting for endogeneity in behavioral choice models with social influence variables[END_REF]) have demonstrated that the preferences of people in the decision maker's peer group will impact her choice of mode of transport to work (public transport, bicycle, car). Another practical application concerns how to use social comparison to enhance energy efficiency [START_REF] Schultz | The constructive, destructive, and reconstructive power of social norms: Reprise[END_REF]. One specific way of leveraging social network for such purposes is to exploit the word-of-mouth/imitation process in a network by using a targeted advertising campaign. Targeted advertising on a social network amounts to finding which agents should be convinced in a social network to be pro-social in such a way that by imitation, the maximum number of agents in the whole social network will also be pro-social. Designing such a targeting strategy, however, can be challenging because of: [START_REF] Abounadi | Stochastic approximation for nonexpansive maps: Application to q-learning algorithms[END_REF] computational issues, (2) unknown social network, (3) size or lack of convexity of the resulting optimization problem, and so on. The goal of this paper is to propose different algorithms based on reinforcement learning that address these issues.

Our initial model can be described as follows: The society is composed of a finite set of agents and each agent has an opinion concerning a given pro-social action that she has to take. October 22, 2019 DRAFT

For instance, it could be the opinion concerning whether or not she should take the bus to work or how much she cares about energy efficiency of her apartment. Whether an agent performs or not the pro-social action, the rest of the society that is "close" to her in the social network will observe her and vice versa. Therefore each agent will have a tendency to imitate her neighbors and vice versa. A planner (government, owner of the social network) is interested in choosing which agents she will influence to shape the opinion in a given direction. The planner can influence an agent through two controls which will be described later on. The society is divided into three types of agents. The first set is composed of 'stubborn' agents. In this set, we assume that they have a given opinion and they will not be impacted by the social network. The second set of agents is composed of 'uncontrolled' agents. In this set, agents are influenced by the social network and their opinion will be impacted by the opinion of the others. However, the planner cannot directly influence them. The last set of agents is called the set of 'controlled' agents.

This set is composed of agents that care about the opinion of their neighbors and also can be influenced by the planner. The goal of the planner is to shape the opinion of the social network by targeting specific agents from the latter group. We call this problem the opinion shaping problem. One of the major drawbacks of this initial model is that for shaping the opinion of the society, the planner needs to know the influence matrix. Worse, even if the influence matrix is known, the number of agents is so big that it is not feasible to decide optimally which agent should be chosen. Finally, depending on how the planner can influence the users, the convexity of the problem can be lost.

Our initial model is inspired by [START_REF] Bimpikis | Competitive targeted advertising over networks[END_REF], [START_REF] Vivek S Borkar | Manufacturing consent[END_REF]. In these papers, the influence matrix is assumed to be known. Moreover the authors do not consider efficient and decentralized algorithms to solve the opinion shaping problem. In this paper, we extend these works further in order to address these issues. Throughout our paper, the main assumption is that the planner does not know the influence matrix but he observes when the agents interact. Using these observations, we are able to derive three reinforcement learning based algorithms that will address the aforementioned issues. The proposed algorithms are decentralized. We also provide supporting simulations for the different settings. From a mathematical point of view, we provide the equivalence of the opinion-shaping problem with a stochastic shortest path problem and use this correspondence to motivate our algorithms and their convergence. Additionally, we discuss several possible extensions and future directions.

October 22, 2019 DRAFT

A. Organization and Main Results

The remainder of this paper is organized into eight sections. In section II, we discuss related works. Section III introduces the opinion-shaping problem after first describing the model for the opinion adoption process. Section IV is the main section of this paper. We prove the equivalence of the opinion adoption process with a stochastic shortest path problem. Using this equivalence, we propose a decentralized algorithm accounting for the fact that the influence matrix is unknown.

This is followed by two other variants. The first one is using a unbiased estimator for the gradient and the second one is designed to tackle the curse of dimensionality one faces when all agents are observed. In section V, we prove the convergence of our algorithms. In section VI, a new algorithm is proposed when the opinion-shaping problem is not convex. Numerical studies are discussed in VII. Moreover, we compare the efficiency of the second algorithm, where all the agents are not observed, with the one where all the agents are observed. Finally, we study the efficiency of the annealing scheme for the non-convex opinion-shaping problem. Section VIII concludes with pointers to some possible extensions of this work.

II. RELATED WORKS

The spread of opinions in social networks broadly falls into three families of mathematical models and the influence maximization problem has been studied in the context of each of these.

The first category is cascade threshold models. In the last decade, initial models in this framework for control of user activity were dedicated to maximization of influence [START_REF] Guille | Information diffusion in online social networks: A survey[END_REF], including the seminal work of Kempe et al. [START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF]. One of the drawbacks of this line of work is that the state of each user is assumed to be finite, often even binary. Another key limitation is that it only focuses on the maximization of influence, which reduces its possible scope for applications. Indeed, one may also be interested in other objectives such as minimum activity in a social network or diverse activity and not just activity maximization. Based on these, a second category of models has been proposed, e.g., by Zha et al. in [START_REF] Farajtabar | Shaping social activity by incentivizing users[END_REF], who define a new mathematical problem dubbed the activity shaping problem. First, they use Hawkes processes to model the activity of users in a social network. Undeniably, in recent literature these point processes have proved to be a very effective method to capture users' activity [START_REF] Zhou | Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes[END_REF]. Secondly, the authors consider an activity shaping problem wherein by controlling the exogenous rate vectors of the Hawkes processes, a central controller tries to minimize a convex function which depends on the expected overall October 22, 2019 DRAFT instantaneous intensity of the processes. Since then, other extensions have been suggested, e.g., [START_REF] De | Algorithm for activity maximization in social networks[END_REF], [START_REF] Wang | A stochastic differential equation framework for guiding online user activities in closed loop[END_REF].

Our model of opinion propagation falls in the last category, viz., consensus models. For several years, much effort has been devoted to the study of users' activities in a social network within this framework. The seminal work of Degroot [START_REF] Morris | Reaching a consensus[END_REF] proposes a simple model to capture the diffusion of opinion. In his paper, the author assumes that each agent at each instant will compute the average opinion of her neighbors including possibly herself, and then replace her current opinion by this average. Several extensions of the Degroot model have been considered recently, especially the opinion shaping part [START_REF] Bimpikis | Competitive targeted advertising over networks[END_REF], [START_REF] Vivek S Borkar | Manufacturing consent[END_REF], [START_REF] Reiffers-Masson | Posting behaviour dynamics and active filtering for content diversity in social networks[END_REF]. In [START_REF] Bimpikis | Competitive targeted advertising over networks[END_REF], the authors assume that a planner can directly contaminate a user in the social network by sending him some messages. The user reads the messages according to a certain probability and with the remaining probability, she will sample from the messages sent by her friends. In [START_REF] Vivek S Borkar | Manufacturing consent[END_REF], the authors consider a more drastic control where they can freeze the opinion of a given user. Finally, in [START_REF] Reiffers-Masson | Posting behaviour dynamics and active filtering for content diversity in social networks[END_REF], the authors suggest a control based on the reduction of the interaction between different agents of the social network.

Concerning the opinion shaping problem without the knowledge of the network, the authors in [START_REF] Lin | A learning-based framework to handle multi-round multi-party influence maximization on social networks[END_REF] propose a data-driven model and a learning algorithm in case of a cascade with a linear threshold model. In [START_REF] Yadav | Using social networks to aid homeless shelters: Dynamic influence maximization under uncertainty[END_REF], the authors suggest a Partially Observed Markov Decision Process (POMDP) framework in order to tackle the uncertainty over the topology of the network, again for the case of a cascade with linear threshold model.

To the best of our knowledge, our paper is the first one that tries to shape the opinion under resource constraints using a reinforcement learning approach, under the assumption that the opinion propagation is captured by a consensus model, but without the full knowledge of the topology.

III. PRELIMINARIES AND MODEL

We consider a social network given by a connected directed graph G = (S, E) where S is the set of its agents and E the set of edges. To each edge (i, j) ∈ E we assign a probability weight

p ij > 0 with {j:(i,j)∈E} p ij = 1. We set p ij = 0 if (i, j) / ∈ E. The total number of agents is equal to I.
With each agent i ∈ S, we also associate a process of valuations

x i (k) ∈ [0, 1], n ≥ 0. Let x(k) = [x 1 (k), .
. . , x I (k)] be the associated vector for each k. We write S as a disjoint union S = S ∪ S 0 ∪ S 1 of three sets. Each time instant k, an agent i (more generally, a set of agents)

October 22, 2019 DRAFT from S is selected and updates her valuation. The update mechanism will change depending on which set an agent belongs to:

Set of 'stubborn' agents (S 0 ): the agents that belong to this set have their valuation frozen at some fixed value for good, i.e., i ∈ S 0 =⇒ ∀k,

x i (k) ≡ h(i) ∈ [0, 1].
Set of 'uncontrolled' agents (S 1 ): This set stands for agents for which their valuations evolves according to a gossip mechanism, but they are not amenable to external influence. In this case the valuation update of an agent i ∈ S 1 is captured by the following mechanism: agent i polls a neighbor ∈ S with probability p i and updates

x i (k) to x i (k + 1) = x (k).

Set of 'controlled' agents (S):

The remaining agents that constitute the set S also evolve according to a gossip mechanism, but are amenable to external influence or 'control'. With probability α i ∈ (0, 1), agent i will be influenced directly by the planner and with probability 1 -α i , agent i will be influenced by her peer group. When influenced by the planner, agent

i updates x i (k) to x i (k + 1) = w i (u i ), with u i ∈ R + without
i (k + 1) = x (k).
To summarize, the overall dynamics is then described as follows. Suppose agent i ∈ S performs an update at time k. Then

x i (k + 1) =    w i (u i ) w.p. α i x (k) w.p. 1 -α i i ∈ S, x i (k + 1) = x (k), i ∈ S 1 , x i (k + 1) = h(i), i ∈ S 0 , x j (k + 1) = x j (k) ∀ j = i.
Analogous scheme holds when more than one agent updates.

For each i ∈ S, when k → ∞, x * i = lim k→+∞ E [x i (k)]
is the solution of the following fixed-point equation:

x * i = α i w i (u i ) + (1 -α i ) ∈S p i x * , i ∈ S, x * i = ∈S p i x * , i ∈ S 1 , x * i = h(i), i ∈ S 0 .
For all u ∈ R I + , let W (u) ∈ [0, 1] I be a vector-valued function where the i-th element, W i (u) is equal to 1 i∈S α i w i (u i ) + 1 i∈S 0 h(i). Let A be a I × I substochastic matrix where its ij-entry

is equal to a ij = (1 -1 i∈S 0 )(1 -1 i∈S α i )p ij . The solution x * = [x * 1 , . . . , x * I ]
of the fixed-point equation, is given by:

x * = (Id -A) -1 W (u), (1)
with Id being the identity matrix with appropriate dimension depending on the context.

Optimization problem:

The goal of the planner is to maximize the sum of the valuations when k goes to infinity, i.e., i∈S x * i , by controlling u i , under the resource constraint i∈S u i ≤ M . Here 0 < M < |S| is a prescribed bound. Equivalently, the objective of the planner is to find

u * = (u * i )
i∈S , the solution of the following optimization problem:

u * = arg max u i ∈R + ,∀i∈S 1 T (Id -A) -1 W (u), (2)
subject to:

i∈S u i ≤ M. (3)
To compute u * , we can use the gradient descent algorithm:

u i (k + 1) = Γ u i (k) + 1 k 1 T (I -A) -1 ∂ ∂u i W (u(k)) , (4)
with

∂ ∂u i W (u(k)) = [1 j∈S α j ∂w j ∂u i (u j )] j∈S .
Our object is to do so in a data-driven manner using ideas from reinforcement learning and MCMC. In this paper we assume that the matrix P is unknown. The known parameters are the set of agents S, the vectors α := [α i ] i∈S , h := [h i ] i∈S 0 , the functional vector w = [w i ] i∈S and the budget M . The matrix P is unknown. At each time step k ∈ N + , the planner chooses a vector u(k) = [u i (k)] i∈S , then simultaneously, agent i is activated w.p. q i , and polls agent j probabilistically as described earlier and observes her opinion.

The planner observes this communication between i and j. The objective of the planner is to find an algorithm such that lim k→+∞ u(k) = u * .

IV. REINFORCEMENT LEARNING SCHEME

A. Equivalent controlled Markov chain

Consider an S-valued controlled Markov chain {Y n } with controlled transition probabilities

q ij (u) := p ij , i ∈ S 1 ∪ S, := δ ij , i ∈ S 0 .
October 22, 2019 DRAFT

Here δ ij is the Kronecker delta. Thus the states in S 0 are absorbing states. Also note that the transition probabilities are independent of the control choice, which affects only the running reward. Let τ := min{n ≥ 0 : Y n ∈ S 0 } denote the first passage time to S 0 . We associate with a state-control pair (i, u i ) an instantaneous cost w i (u) and a state-dependent discount factor

(1 -α i ). Note that α i = 0 and w i (u) = 0 for all i ∈ S 0 ∪ S 1 . Suppose u i (k) = v(i) for some v : S → [0, 1], i.e., a 'stationary Markov policy' in Markov decision theoretic parlance [START_REF] Vivek | Convex analytic methods in markov decision processes[END_REF]. Let

xi (k) := E[x i (k)] ∀ i, k. Then {x i (k)} satisfy the dynamics xi (k + 1) = α i w i (u i (k)) + (1 -α i ) p i x (k)), i ∈ S, xi (k + 1) = p i x (k)), i ∈ S 1 .
The matrix P := [[p ij ]] i,j∈S∪S 0 is substochastic, hence the above linear system of equations is stable. Then as k ↑ ∞,

xi (k) → xi (∞),
where x(∞) satisfies the equation

xi (∞) = α i w i (u i (k)) + (1 -α i ) ∈S p i x (∞), i ∈ S, xi (∞) = ∈S p i x (∞), i ∈ S 1 .
This equation can be rewritten as:

xi (∞) = α i w i (u i (k)) + (1 -α i ) ∈S∪S 1 p i x (∞) + ∈S 0 p i h( ), i ∈ S, xi (∞) = ∈S∪S 1 p i x (∞) + ∈S 0 p i h( ), i ∈ S 1 .
By standard 'one step analysis', one sees that xi (∞) has the representation

xi (∞) := E i τ -1 m=0 m-1 k=0 (1 -α Y k ) α Ym w Ym (u(m)) + τ k=0 (1 -α Y k ) h(Y τ ) .
This suggests that we can view the opinion dynamics as the value iteration for evaluating a fixed stationary Markov policy v(•) for the controlled Markov chain {Y n }, the objective being October 22, 2019 DRAFT i∈S∪S 1 xi (∞). This will be recognized as a discounted reward for the stochastic shortest path problem ('Longest path problem', to be precise, since we are maximizing a reward rather than minimizing a cost. The equivalent stochastic shortest path problem corresponds to viewing -w i (•) as a running cost function and -h(•) as the terminal cost.)

We do, however, have an additional constraint (3). This is hard to incorporate in a Markov decision process as a constraint on controls, because it couples actions across different states in a manner unrelated to the dynamics (i.e., without regard to, e.g., how often they are visited). This puts it beyond the reach of traditional dynamic programming based computations such as value or policy iteration, or linear programming version of the dynamic program. Therefore we treat this as a parametric optimization problem over the parameters u i 's instead of as a control problem -this will become apparent from the algorithms we propose. The 'uncontrolled' but parameter-dependent 'dynamic programming' 1 equation is given by standard arguments, as the linear system

V (i) = α i w i (u i ) + (1 -α i ) j p ij V (j), i ∈ S, (5)
V (i) = j p ij V (j), i ∈ S 1 , V (i) = h(j), i ∈ S 0 . (6)

B. First algorithm

Let k ∈ N + be k th time an agent polls another. A gradient based learning scheme for this problem is as follows. Let

I{Y n = i} =    = 1 if Y n = i, = 0, if Y n = i, ν(i, n) := n m=0 I{Y m = i}.
for n ≥ 0. Then ν(i, n), n ≥ 0, can be interpreted as a 'local clock' at agent i, counting its own number of updates till 'time' (i.e., the overall iterate count) n. Pick stepsize sequences

{a(k)}, {b(k)} ⊂ (0, ∞) such that k a(k) = k b(k) = ∞, k (a(k) 2 + b(k) 2 ) < ∞, b(k) a(k) → 0. (7)
We shall also make the following additional assumptions on {a(k)}:

1 'one step analysis', to be precise October 22, 2019 DRAFT 1) a(n + 1) ≤ a(n) from some n onwards;

2) there exists r ∈ (0, 1) such that n a(n) 1+q < ∞, q ≥ r;

3) for x ∈ (0, 1), sup n a([xn]) a(n) < ∞, where [• • • ] stands for the integer part of '• • • '; 4) for x ∈ (0, 1) and A(n) := n m=0 a(i), lim n↑∞ A([yn]) A(n) = 1 uniformly in y ∈ [x, 1].
These conditions are satisfied, e.g., by the popular stepsize a(n) = 1 n+1 , n ≥ 0. The algorithm then is as follows. For k ≥ 0, i, j ∈ S, do: for a prescribed state i 0 ,

Ψ ij (k + 1) = Ψ ij (k) + a(ν(i, k))I{Y k = i} × α i w i (u i (k))δ ij + (1 -α i )Ψ Y k+1 j (k) -Ψ i (k) , (8)
u i (k + 1) = Γ(u i (k) + b(k) j Ψ ji (k)), (9)
Ψ ij (k) = 0, i ∈ S 0 . (10)
Here Γ(•) is the projection onto the simplex

{x = [x 1 , • • • , x |S| ] T : x i ≥ 0 ∀i, i x i ≤ M }.
This is a gradient-based reinforcement learning scheme which is better suited for our purposes than, e.g., the classical Q-learning scheme of [START_REF] Abounadi | Stochastic approximation for nonexpansive maps: Application to q-learning algorithms[END_REF]. This is because it allows us to treat the optimization over control parameters as parametric optimization which can handle the constraint (3). The explanation of this scheme is as follows:

• The iteration (8) estimates the partial derivatives ∂V (i) ∂u j by Ψ ij (k), k ≥ 0. This is arrived at by considering the constant policy dynamic programming equation

V (i) = α i w i (u i ) + (1 -α i ) j p i V ( ), (11)
for i ∈ S. Differentiating both sides w.r.t. u j , we see that

Φ ij := ∂V (i) ∂u j satisfy Φ ij = α i w i (u i )δ ij + (1 -α i ) p i Φ j , (12)
for i ∈ S, with Φ ij = 0 for i ∈ S 0 . The iteration (8) then is the stochastic approximation scheme to solve this equation.

• Iteration (9) operating on a slower time scale (in view of ( 7)), constitutes a stochastic gradient ascent. That is, ( 9) is a stochastic gradient ascent over the control variables which takes the outputs {Ψ ij (k)} of (8) as estimates of the relevant partial derivatives and summing October 22, 2019 DRAFT them over the first index, generates an estimate of the corresponding partial derivative of the reward itself. In turn, the application of the projection Γ(•) makes it a projected stochastic gradient scheme which also imposes the constraint (3).

The chain {Y n }, however, is an imaginary object. To map this scheme back to our original framework, let Z n be the index of the agent that updated its valuation at time n. In other words, it is the Z n -th component x Zn (n) that got updated at time n, the rest were left unperturbed.

Also suppose that this was done by the Z n -th agent by polling a neighbor Z n according to the transition probabilities q zn• defined above.

The iteration (8) of the above scheme can then be written for our original framework as

Ψ ij (k + 1) = Ψ ij (k) + a(ν(i, k))I{Z k = i}× (α i w i (u i (k))δ ij + (1 -α i )Ψ Z k j (k) -Ψ ij (k) . (13)
The third iteration, i.e., [START_REF] Morris | Reaching a consensus[END_REF], remains unaltered, as do the boundary conditions for the Ψ i 's. Now that we no longer have to think of Z k , Zk as realizations of a single trajectory of a Markov chain, we can generalize this further and let Z k be a subset of S. For each i ∈ Z k , we generate a random variable Zi k according to the probability distribution q i• above. The iteration (14) then gets replaced by

Ψ ij (k + 1) = Ψ ij (k) + a(ν(i, k))I{i ∈ Z k }× (α i w i (u i (k))δ ij + (1 -α i )Ψ Z i k j (k) -Ψ i (k) . (14)
In particular when Z n = S, it is a completely synchronous iteration. Note that ν(i, n) has to be defined now as ν(i, n) := n m=0 I{i ∈ Z m }.

C. Stochastic gradient scheme

Along the line of the previous algorithm, we define a new algorithm, where instead of having a biased but consistent estimator of the gradient, we can derive a sampling scheme that will provide, at each iteration, a unbiased estimator of the gradient. Recall the Z n , Zn defined in the preceding section. There we had considerable freedom in choosing how Z n is generated, the key requirement was that Zn should have the prescribed conditional law given Z n . This is because the algorithm at each step calls for a single transition executed according to the given transition matrix. That is, one has to generate a pair of random variables with the conditional law of the latter given the former completely specified and the (marginal) law of the former having full October 22, 2019 DRAFT support at each step. In the algorithm we propose below (with its natural extension), however, we require at each step a path of random duration in S. Generating pairs (Z n , Zn ) as before does not provide that. Hence unlike the previous scheme with full observations, we now need a probing mechanism. Thus we define Z n as before and do (for each fixed n): Let δ •• denote the Kronecker delta.

1) For each i ∈ S, set m = 0 and set Y j0 = Z n = j (say). Here j ∈ S\S 0 can be picked uniformly at random. Initialize ξ ji (n) = 0.

2) With probability α Y j0 = α j (α j = 0 if j ∈ S 1 ), stop and set

ξ ji (n) → ξ ji (n) + δ ji . If not, 3) with probability (1 -α Y j0 )p Y j0 k , continue by setting Y j1 = k, ξ ji (n) → ξ ji (n). 4
(1 -α Y jm )p Y jm .
5) Repeat 4) above for m ≥ 1 till stopping.

6) Perform the following gradient descent step:

u i (n + 1) = Γ u i (n) + a(n)w i (u i (n)) i ξ ij (n) . (15)
An alternative scheme is:

1) For each i ∈ S, and for each j ∈ S, set m = 0 and Y i0 = i, kept fixed for this run.

Initialize ζ i = 1. Set ξ ij → ξ ij + ζ i δ Y i0 j α Y i0 .
Continue by setting Y i1 = k with probability p Y i0 k .

2) At step m, stop if Y im ∈ S 0 . If not, set

ζ i → ζ i (1 -α Y i(m-1) ), ξ ij → ξ ij + ζ i δ Y im j α Y im ,
and continue by setting Y i(m+1) = with probability p Y im .

3) Repeat 2) above for m ≥ 1 till stopping. Freeze ξ ij on stopping and label it ξ ij (n).

4) Perform the following gradient descent step:

u i (n + 1) = Γ u i (n) + a(n)w i (u i (n)) j ξ ji (n) . (16)
By construction, for the two sampling schemes,

w i (u i (n))E [ ξ i (n)],
is the solution of the linear system [START_REF] Forestier | Multilayer control of large markov chains[END_REF]. Therefore, the previous scheme will converge to the optimal u * as long as October 22, 2019 DRAFT the variance of ξ ij (n) is bounded for all k [START_REF] Vivek | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF]. For the stochastic gradient iterate ( 16), a good step-size in this context is a(n) = A/( n M ) for some A > 0 and M ≥ 1.

D. An alternative learning scheme

The problem with the above scheme is that it involves all agents in S, which may lead to a curse of dimensionality. Worse, it requires that all communications between agents be observed.

It makes sense to assume that only a few agents can be monitored. These should include in particular those in S. Without any loss of generality, we assume that only the updates of agents in S are observed. The algorithm we propose next and its analysis extend easily to the case when a few uncontrolled agents are also observed (by using, e.g., the trivial device of setting α i ≡ 0 for such agents). Then it also makes sense that we should treat S * := S ∪S 0 as our effective state space for the algorithm. By analogy to the above stochastic shortest path formulation, consider an S-valued Markov chain {Y n } with transition probabilities {p ij }. If we restrict {Y n } to S * , it means that we observe only {Y Tn } where T n , n ≥ 0, are the successive return times of {Y n } to S * define recursively by

T 0 := min{m ≥ 0 : Y m ∈ S * }, T n+1 := min{m > T n : Y m ∈ S * }, n ≥ 0.
The chain eventually gets absorbed into S 0 as before. Strictly speaking, if we keep track of the T n 's as well, it is a semi-Markov process. Exercising control only when the chain is in S * leads to a supervisory control problem as in [START_REF] Forestier | Multilayer control of large markov chains[END_REF], albeit with a different reward structure compared to theirs. Nevertheless, we do not need to view it in this manner. This is because our controlled Markov chain is an artifact, the actual process is the simple averaging or 'gossip' dynamics. Thus the actual values of T n 's are irrelevant for us and we can work with the chain

Y * n := Y Tn , n ≥ 0. Let q * (j|i), i, j ∈ S * , denote the probability that Y * n+1 = j given Y * n = i. It is of the form q * (j|i) = p ij + j = ∈S p i ϕ(j| )
where ϕ(j|

) := P (Y * ζ = j|Y * 0 = ), for ζ := min{n ≥ 0 : Y * n ∈ S}.
In particular, ϕ(•|•) is independent of the control choice u. After the chain leaves state i, it does not hit any other controlled state before hitting another state (j above) in S * , so the associated running cost is α i w i (u) as before. We now consider the restricted reward i∈S x i (∞) which is not the same as the original, so this is an approximation. The advantage of this reward is that it is expected to October 22, 2019 DRAFT be positively correlated with the full reward, i.e., increase in the former should lead to increase in the latter. More importantly, it depends only on observed quantities. This passage is purely heuristic and avoids in particular having to contend with the full complications of the 'partial observations' framework. The associated (constant policy) dynamic programming equation is then given by

V (i) = α i w i (u i ) + (1 -α i ) p ij + j, ∈S :j = p i ϕ(j| ) V (j), (17)
V (i) = h(i), i ∈ S 0 . ( 18
)
One could write down a reinforcement learning scheme for approximate solution of ( 17)-( 18)

along the lines of the preceding subsections, but the situation is much more difficult here. The problem is similar to the one faced in the stochastic gradient scheme above. We require a path from one state in S * to another, passing through a possibly nonempty set of unobserved states in S\S * . Again, generating pairs (Z n , Zn ) as before does not provide that. We now need a probing mechanism. Thus we define Z n as before, but when node Z n = i ∈ S * polls a neighbor i 1 ∈ S, it passes to i 1 a time-stamped token tagged with i. The node i 1 , if not in S * , does likewise, but retaining the original tag and time stamp. This continues till the token reaches some j ∈ S * .

Then set Zn = j. The corresponding reinforcement learning scheme now becomes

Ψ i (k + 1) = Ψ i (k) + a(ν(i, k))I{i ∈ Z k } × (α i w i (u i (k)) + (1 -α i )Ψ Z i k (k) -Ψ ij (k) , (19)
u i (k + 1) = Γ u i (k) + b(k)Ψ i (k) , (20)
Ψ i (k) = 0, i ∈ S 0 . (21)

V. CONVERGENCE ANALYSIS

The convergence analysis of the first scheme goes along standard lines, essentially piecing together known facts from the theory of two time scale and distributed asynchronous stochastic approximation. With this in mind, we only sketch it in outline. To begin with, note that condition [START_REF] Vivek | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF] implies that the iterates (20) move on a slower, in fact asymptotically negligible, time scale compared to [START_REF] Guille | Information diffusion in online social networks: A survey[END_REF]. Hence they can be viewed as quasi-static, i.e., u i (k) ≈ u i ∀i, for purposes October 22, 2019 DRAFT of analyzing ( 14) ([7], Section 6.1). Then ( 14) constitutes a stochastic approximation scheme to estimate the partial derivatives of V * w.r.t. the u i 's by solving [START_REF] Forestier | Multilayer control of large markov chains[END_REF], which has a unique solution. Its convergence to this solution follows from the theory of asynchronous stochastic approximation developed in [START_REF] Vivek | Asynchronous stochastic approximations[END_REF], wherein the conditions we have imposed on {a(n)} play a crucial role.

But this is under the assumption that u i (k) ≈ u i ∀i, whereas in reality the u i (k)'s are changing on a slower time scale. Thus what the foregoing entails in reality is that

Ψ ij (k) - ∂V * (i) ∂u j u•=u•(k) → 0
a.s. ∀ i, j, i.e., Ψ ij 's track the corresponding partial derivatives of V * with an asymptotically negligible error, as desired. Thus ( 20) is a legitimate stochastic gradient ascent scheme. We need the following lemma.

Lemma 1 The solution V (•) of the constant policy dynamic programming equation ( 17)-( 18) is componentwise concave and continuous in the variables {u i }.

Proof (Sketch) This follows by considering the associated constant policy value iteration and using induction, along with the fact that pointwise limits of concave functions are concave and uniform limits of continuous functions are continuous. The details are routine, see, e.g., [START_REF] Agarwal | Structural properties of optimal transmission policies over a randomly varying channel[END_REF]. 2

Our main result then is the following:

Theorem 1
The above learning policy is asymptotically optimal, a.s.

Proof This is immediate from the fact that the projected stochastic gradient ascent for a concave function on a compact interval converges to the set of its global maxima a.s. (see, e.g., [START_REF] Vivek | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF],

Chapter 10). 2

The stochastic gradient scheme above, by virtue of [START_REF] Forestier | Multilayer control of large markov chains[END_REF], is already of the form

u i (n + 1) = u i (n)+ a(n)I{Z n = i} ∂V (i) ∂u i (u(n)) + M i (n + 1) , where M (n) := [M 1 (n), M 2 (n), • • • ] T is a martingale difference sequence.
That is, it is a classical asynchronous stochastic gradient scheme with a.s. convergence to a local miaximum, which is also a global miaximum by concavity of V (i), under reasonable conditions on {M (n)} -see Chapter 10 of [START_REF] Vivek | Asynchronous stochastic approximations[END_REF].

Finally, the 'alternative scheme' above based on observing few nodes is of the same form as the reinforcement learning scheme above and is analyzed exactly the same way.

October 22, 2019 DRAFT

VI. A MORE GENERAL MODEL

We can also consider the situation where α i 's depend on the control choice u i at i ∈ S. We shall illustrate the changes for the second, i.e., the improved learning scheme above, the situation for the first scheme being completely analogous. Thus the 'dynamic programming equations' become

V (i) = α i (u i )w i (u i ) + (1 -α i (u i )) p ij + ∈S p i ϕ(j| ) V (j), V (i) = h(i), i ∈ S 0 ,
and the corresponding reinforcement learning scheme is

V i (k + 1) = V i (k) + a(ν(i, k))I{i ∈ Z k } × α i (u i (k))w i (u i (k)) + (1 -α i (u i (k)))V Z i k (k) -V i (k) , (22)
Ψ ij (k + 1) = Ψ ij (k) + a(ν(i, k))I{i ∈ Z k } × (α i (u i (k))w i (u i (k)) + α i (u i (k))w i (u i (k)))δ ij -α i (u i (k)))δ ij V Z i k (k) (23)
+ (1 -α(u i (k)))Ψ Z i k j (k) -Ψ ij (k) , (24)
u i (k + 1) = Γ u i (k) + b(k) j Ψ ji (k) , (25)
V k (i) = h(i), i ∈ S 0 , Ψ ij (k) = 0, i ∈ S 0 .
The convergence analysis applies as before except for the fact that we can no longer claim concavity and convergence only to a local minimum can be guaranteed. This could be improved, e.g., by resorting to simulated annealing for the slow time scale iterates, i.e., replacing them by

u i (k + 1) = Γ u i (k) + b(k) j Ψ ji (k) + C 1/b(k) log log(c(k)) W k+1 , (26)
where {W k } are IID N(0,1), C > 0 is a suitably chosen constant as in [START_REF] Saul | Recursive stochastic algorithms for global optimization in R d[END_REF].The difference with the previous scheme is that [START_REF] Farajtabar | Shaping social activity by incentivizing users[END_REF] gets replaced by

V (i) = α i (u i )w i (u i ) + (1 -α i (u i )) j p i V ( ). (27)
October 22, 2019 DRAFT Initial setting: First we specify the number of agents in each set (S, S 1 , and S 0 ) and then randomly allocate an agent to a given set. We assume that α i = α for each i ∈ S 0 ∪ S and α i = 0 for all i ∈ S 1 . For each i ∈ S 0 , h(i) is sampled from a uniform distribution. In our simulations, α = 0.6, M = 5, A = 0.6, B = 0. Convergence for the Karate network. In the first numerical study, we are interested in understanding the convergence of the stochastic approximation scheme and the stochastic gradient to the optimal strategy. We restrict this study to the Karate network. Later on, we shall extend it to the remaining networks. In Figure 2(a), the x-axis denotes the number of iterations and the yaxis captures the evolution of u(k) for the stochastic approximation/reinforcement based scheme (8)- [START_REF] Dugundji | Discrete choice with social and spatial network interdependencies: an empirical example using mixed generalized extreme value models with field and panel effects[END_REF]. We will abbreviate the name of this scheme by SAS (for stochastic approximation scheme). In Figure 2(b), the x-axis denotes the number of iterations and the y-axis captures the evolution of u(k) for the stochastic gradient (SGD) with the two sampling schemes [START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF] and [START_REF] Lin | A learning-based framework to handle multi-round multi-party influence maximization on social networks[END_REF]. In the two figures, the red curve captures the evolution of u(k) using the gradient descent October 22, 2019 DRAFT (GD). The number of controlled agents is equal to 3. Twenty-eight agents belong to S 1 and three agents are in S 0 . In Figure 2(a), before 7500 iterations, we can observe that the gradient descent algorithm already converges and the reinforcement learning scheme did not. In fact the SGD seems to converge faster (see Figure 2(b) after 2500 iterations). However, we observe that the variance over the iterates of SGD is higher than the SAS. The tradeoff therefore is between speed and fluctuations. Moreover we can observe in Figure 2 that one iteration of the SAS is much faster than the ones of the two SGD algorithms. Therefore there is a clear tradeoff between the complexity of a single iteration and the number of iterations, so the latter cannot be the sole basis for comparison. q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.0000 Extension to other networks: The second numerical study applies the same schemes to the other datasets and observes whether or not the same conclusions apply. We do not present the October 22, 2019 DRAFT SGD with the second sampling scheme because the conclusion are similar. In Figure 4(a) and in Figure 4(b), we perform 10 simulations of the stochastic approximation scheme and stochastic gradient for each network. The performance measure on y-axis is the relative difference between the optimal payoff and the current payoff generated by u(k) at iteration k. For the SAS, we observe that for each network, even if we stop the stochastic approximation after 100 iterations, the third quantile will have a relative difference lower than 1%. For each network, when we use the stochastic gradient, we note that relative difference is much lower that for the SAS. The last observation highlights the fact that when the number of iterations is low (under 1000 in this case), the SAS uses a biased estimator of the gradient compared to the stochastic gradient and therefore has lower performance. q q q q q q q 0.0000 Study of the improved learning scheme: In the third numerical study, we are interested in understanding how the second learning scheme compares with the first. The main difference between the two algorithms is that in the first one you have to observe the communication between all the agents and in the improved one, you can only observe a part of it. In order to be able to compare with the previous simulations, we assume the following: The set of controlled agents is the same (S is the same). Only 50% of the agents in S 0 and S 1 are observed. The results are depicted in Figures 1(a), 1(b) and 1(c). In Figure 1(a), we note that the improved stochastic approximation scheme already converges after a number of iterations less than 3000.

The convergence is not to the optimal one but in this case, we can observe that in Figure 1(b), the relative difference of the current payoff and the optimal is below 0.1%, therefore nearly optimal.

October 22, 2019 DRAFT

How to select the initial set of agents: One of the results of this paper is the fact that by observing a small number of agents, we can increase drastically the speed of convergence of the algorithm. Even if the obtained solution is suboptimal, the relative difference observed between the optimal payoff and the suboptimal one, in the simulation, was low (about 0.01%). Therefore, one interesting question would be to find a possible algorithm to choose the initial set of agents?

This question can be related to the problem of selecting sensors k, among n potential sensors.

In future work, we will try to adapt this well-known problem to our setting. See also a greedy scheme for agent selection with performance guarantees proposed in [START_REF] Vivek S Borkar | Manufacturing consent[END_REF].

Other learning schemes: In our current scheme, we observe communications between a set of particular agents. In [START_REF] Abhijit V Banerjee | Using gossips to spread information: Theory and evidence from two randomized controlled trials[END_REF], the authors prove that agents in a social network can easily guess who is central in a diffusion process. Therefore a potential scheme would be to ask a small number of agents who they think is central in the network and factor this information into the opinion-shaping optimization problem.

Pricing scheme for accessing communication data: Accessing the data in the age of information is getting more and more important. Agents start to realize the value of their data. The question that we should ask in our setting is the following: how much should a planner pay an agent to access her information in order to be able to perform opinion shaping, i.e., design an incentivecompatible pricing mechanism for data acquisition.

  Evolution of u(k).

Fig. 1 .

 1 Fig. 1. Simulations for the improved learning scheme.

Fig. 2 .

 2 Fig. 2. Evolution of u(k) for each algorithm.

Fig. 3 .

 3 Fig. 3. Boxplot for the time (in seconds) to perform one iteration of each algorithm.

Fig. 4 .

 4 Fig.4. Box-plot of the relative difference between the payoff obtained at k and the optimum over 10 simulations for the stochastic approximation scheme and the stochastic gradient descent.

  ) At step m, stop if Y jm ∈ S 0 . If not, stop with probability α Y jm and set ξ ji (n) → ξ ji (n) +

δ Y jm i , or else continue with probability (1 -α Y jm ) by setting Y j(m+1) = with probability

  [START_REF] Vivek | Convex analytic methods in markov decision processes[END_REF], denom = 100 and w(x) = x x+0.1 .

	Network	Karate macaque	rfid
	Number of nodes	34	45	75
	Number of edges	78	463	2278
		TABLE I
	DESCRIPTION OF THE NETWORKS

October 22, 2019 DRAFT

ACKNOWLEDGMENT The work of VSB was supported in part by a J. C. Bose Fellowship from the Department of Science and Technology, Government of India, and the project 'Machine Learning for Network Analytics' from the joint DST-INRIA program administered by the Indo-French Centre for Promotion of Advanced Research.

Research (CEFIPRA).

Differentiating through with respect to u i in [START_REF] Forestier | Multilayer control of large markov chains[END_REF] and after replacing α i by α(u i ), we have the additional term α i (u i )(w i (u i ) -p i V ( )) on the right hand side. The second and third term on the right had side of [START_REF] Xia | Energycoupon: A case study on incentive-based demand response in smart grid[END_REF] correspond to these additional terms. As this involves Ṽ (•) as well unlike the previous scheme which did not, one needs the additional iteration [START_REF] Walker | Correcting for endogeneity in behavioral choice models with social influence variables[END_REF] to estimate it, this being the stochastic approximation scheme to solve [START_REF] Farajtabar | Shaping social activity by incentivizing users[END_REF].

For comparison purposes later on in the numerical section, we also state the iterations in the case where we know the matrix P explicitly. Then the only difference would be in the update of V i (k) and Ψ ij (k) which will follow the following scheme:

VII. NUMERICAL EXPERIMENTS

We select three real-world networks for our evaluation. The three networks are Karate, Macaque, Rfid (see Table I) and have from 34 to 75 nodes and from 78 to 2278 links. Each network was retrieved from the R package igraphdata [START_REF] Scardi | igraphdata: A collection of network data sets for the igraph package[END_REF]. The numerical experiments reported here are for the synchronous case, i.e., all components are updated each time. The results are compared with the exact solution computed off-line using gradient descent described in (4). We can conclude that even if the improved stochastic approximation does not converge to the optimal u * , the strategy reached is already quite good. We can observe a similar conclusion in Figure 1(c) for the remaining networks. These preliminary simulations encourage the use of the improved stochastic approximation scheme.

Study of the more general problem: The final numerical study is dedicated to the last reinforcement scheme based on annealing method for non-convex optimization. We restrict this study to the Karate network. We assume that w i (u i ) = h(i) for all i ∈ S and

Also in this simulation study for i ∈ S, α i (u i ) = u i u i +0.1 with #S = 3. The noisy term of ( 26) is parametrized by c(k) := k/denom and C = 10. We study two schemes. The first one is reinforcement learning (( 22), ( 24) and ( 26)). The second one is without the approximation of the reinforcement scheme for the computation of the gradient ((28) and ( 26)). We are interested in understanding how the first scheme tracks the behavior of the second scheme. In Figure 5(a) (resp. Figure 5(b)) , we observe the first algorithm starts to track the trajectory of the second trajectory after 2000 iterations (15000 iterations). Moreover, we observe that in both cases, the two schemes are converging to the same values.

VIII. FURTHER DIRECTIONS

Incorporating subjective risk measures: Since we are modeling social networks, it is desirable that we incorporate behavioral aspects into our model explicitly, such as the risk-measures suggested by behavioral economics. This makes the problem a lot harder, see, e.g., [START_REF] Shen | Risk-sensitive markov control processes[END_REF] for some initial efforts towards the dynamic programming aspects.

October 22, 2019 DRAFT


Alexandre Reiffers-Masson

Isabel Amigo

Online Multi-Agent Decentralized Byzantine-robust Gradient Estimation

In this paper, we propose an iterative scheme for distributed Byzantine-resilient estimation of a gradient associated with a black-box model. Our algorithm is based on simultaneous perturbation, secure state estimation and two-timescale stochastic approximations. We also show the performance of our algorithm through numerical experiments.

INTRODUCTION

The main goal of this paper is to derive a decentralized algorithm which can efficiently learn the gradient of a blackbox model, in a multi-agent context. In a black-box model it is assumed that a function f is unknown but can be accessed through queries to a zero-th order oracle [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF]. Being able to compute the gradient can be used, for instance to design efficient distributed optimization algorithms to find the minimum of f . We assume that there is a finite number of processors/servers (called nodes or agents in the rest of the paper) which participate in the distributed computation of the gradient.

We also assume that some agents can have Byzantine behaviors: that is, they will try to deviate from the suggested protocol. Such behaviors are well known in the literature of distributed algorithms (consensus and leader election algorithms, for instance) and have also recently been studied in the context of machine learning [START_REF] Yin | Byzantine-robust distributed learning: Towards optimal statistical rates[END_REF][START_REF] Wu | Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks[END_REF]. In such contexts, three major points need to be tackled: [START_REF] Augustine | Storage and search in dynamic peer-to-peer networks[END_REF] The fact that unidentifiable Byzantines nodes are present in the system and that it is not possible to guarantee the safety of a given node; (2) the algorithms should be decentralized and each "good" node, should have a good estimation of the gradient (3) the algorithms should be efficient (in terms of speed of convergence and number of operations per iterations).

Our solution is based on a generalization of the gradient estimator algorithm developed in [START_REF] Borkar | Gradient estimation with simultaneous perturbation and compressive sensing[END_REF], using two-timescale stochastic approximations and secure estimation [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF]. We are also able to derive sufficient conditions to ensure that our algorithm will be able to be robust to Byzantine nodes.

PROBLEM FORMULATION

This section is dedicated to the description of our framework and to the problem formulation. Further discussion on the model assumptions is provided in Subsection 2.1.

Copyright is held by author/owner(s)

Nodes' model: Let I = {1, . . . , n} be the set of nodes. We assume that the set of nodes can be partitioned into two disjoint subsets of nodes IB and IG. The set IB (resp. IG) is the set of Byzantine nodes (resp. non-Byzantine nodes). At every instant k 2 N, each node i 2 I controls a variable xi(k) 2 R. For every k 2 N, let x(k) := [xi(k)] 1in be the associated vector. A Byzantine node will try to disobey the protocol. More precisely, we assume that: (1) a Byzantine node can modify its own xi(k) (when it is allowed) without following the prescribed protocol (2) it can report corrupted values (3) it can have complete knowledge of the system and the algorithm. Note that IB is constant for every k, meaning that the set of Byzantine nodes does not change over time (this assumption is similar to the one in [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF]).

Asynchronous Updates: Let Y (k) ✓ I be the set of active nodes at instant k 2 N+. We say that a node i is active at instant k if it can modify xi at instant k. Let YB(k) ✓ IB be the set of active Byzantine nodes and YG(k) ✓ IG is the set of active non-Byzantine nodes, such that Y (k) = YB(k) [ YG(k) and YB(k) \ YG(k) = ; . We assume that Y (k) is an irreducible Markov chain where the state space is a subset U of the power set P(I) of I. This assumption ensures that we are in an asynchronous set-up, where not all nodes are active at the same time. This is crucial to ensure that Byzantine nodes do not have too much power in the system. We use a vector notation u(k) 2 {0, 1} |I| to denote an element of P(I) at instant k. If the i-th component of u(k) is equal to one, it means that node i belongs to the set Y (k) (i.e. it is active). Otherwise, node i is not in the set Y (k) (i.e. it is not active). Note that for a given k, we have u(k) = [1 i2Y (k) ] 1in . The subset of U where each vector contains at least a Byzantine node is

denoted by UB := {u 2 U | 9i 2 IB, ui = 1}.
Challenge: We assume that for every k, the nodes are interested in computing the gradient of f (x(k)) where f : R n ! R is a continuous twice di↵erentiable function. We assume that for every x(k), f (x(k)) is available to every node. However, rf (x(k)) is not readily available, and therefore, the nodes need to collaborate together to obtain a robust estimation. We can easily generalize our approach to the case when f : R n ! R p , but for simplicity's sake, we assume p = 1.

Remarks

We believe that the assumption that Y (k) is an irreducible Markov chain, resulting in mathematical simplicity in our problem, is in line with acceptable models capturing asynchronous updates of the nodes. This assumption is necessary for the proof of the convergence of iterative scheme (see

38

Performance Evaluation Review, Vol. 50, No. 4, March 2023 section 4) We justify below our assumption with a classical example coming from the distributed systems literature. A first classical communication scheme to ensure lightweight communication costs is a simple token-passing implementation of a random walk. Di↵erent implementations of such mechanism have been studied in distributed systems [START_REF] Augustine | Storage and search in dynamic peer-to-peer networks[END_REF][START_REF] Ramiro | Temporal random walk as a lightweight communication infrastructure for opportunistic networks[END_REF] and Byzantine versions of such communication scheme have been studied in [START_REF] Yuan | Fast fault-tolerant sampling via random walk in dynamic networks[END_REF]. The performance of the di↵erent algorithms has been studied using Markov chain models. Another example are wireless networks. In this context, comes naturally the constraint that all links/nodes cannot be activated simultaneously. A natural protocol in such case is the CSMA protocol which has been modeled using Markov chains [START_REF] Jiang | A distributed csma algorithm for throughput and utility maximization in wireless networks[END_REF][START_REF] Borkar | Asynchronous gossip for averaging and spectral ranking[END_REF].

BYZANTINE-ROBUST GRADIENT ES-TIMATION

We first describe a natural, not robust to Byzantine nodes, way to approximate the gradient. Then, by adapting the tools developed in [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF], we present how to construct a robust approximation of rf (x).

Simultaneous Perturbation

We now introduce the simultaneous perturbation scheme to create an estimate of the gradient. We will also illustrate the impact of having Byzantine nodes in such estimator.

In a simultaneous perturbation scheme, at every instant k, for a given x(k), we assume that every node i 2 YG(k) performs the following scheme: (1) Sample ∆i(k) 2 {-1, 1} from a Bernoulli distribution of parameter 1/2, (2) Play xi(k) + δ∆i(k), where δ is positive constant, provided as input. A Byzantine node will not respect such steps. Without loss of generality, we assume that a Byzantine node, instead of playing xi + δ∆i(k) plays xi + δe 1 i (k), with e 1 i (k) 2 R. Therefore, the observation by all nodes at instant k is given by:

z i,u(k) (k) = 8 < : f (x + δ ∆(k)) -f (x) δ ∆i(k) , if i 2 YG(k), 0, if i / 2 Y (k), (1)
where the i-th component of ∆(k) is equal to:

∆i(k) = 8 < : ∆i(k), if i 2 YG(k), e 1 i (k), if i 2 YB(k), 0, if i / 2 Y (k). (2)
In expectation, and using Taylor's theorem (see chap. 10 p.120 in [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF]), the gradient observation,

z i,u(k) (x) := E[z i,u(k) (k)],
can be summarized as follows:

z i,u(k) (x) := 8 > > > > > > > < > > > > > > > : @f @xi (x) + O(δkr 2 f (x)k), if i 2 YG(k) and YB(k) = ;, @f @xi (x) + e u(k) (k) + O(δkr 2 f (x)k), if i 2 YG(k) and YB(k) 6 = ;, 0 if i / 2 Y (k). (3)
Note that we have summarized the impact of having i or j being a Byzantine node by simply adding a perturbation term e(k) 2 R to the observation. Indeed, without loss of generality, because the Byzantine node is not constrained in the choice of e(k), such additive term captures the impact of the perturbation terms e 1 i (k) and e 2 i (k). From this remark, we can also see that z i,u(k) (k) is not a robust estimate of the gradient, due to the fact that the moment YB(k) 6 = ;, the observation z i,u(k) (k) can be any value in R.

Secure gradient estimation

We will now construct a robust estimate of the gradient, in a distributed manner, using the theory developed in [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF]. Let us first introduce the following assumption over f (x).

Assumption A: It exists a function v : R n ! R m , such that the function f : R n ! R satisfies:

rf (x) = Av(x), 8x.
We assume that v : R n ! R m is a continuous function and A is a n ⇥ m real matrix. We also assume that A is known by every node.

To recast our problem in the form described in [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF], we rewrite the observations as the output of a linear system. For a given x the vector z(x) := [[zi,u(x)] 1iI ]u2U , gives the gradient observation for the di↵erent u. The vector v(x) := [v m 0 (x)] 1m 0 m is the vector that we are interested in learning for every x. Note that the relationship between z(x) and v(x) is captured by the following linear system z(x) = A1v(x) + e, where the matrix A1 is equal to

A1 := " A(u1)A(u2) . . .A(u |U | ) # T , with A(u) = u ⌦ A where
⌦ denotes entrywise product. Using the entrywise product will ensure that the i-th line of A(u) is equal to the null line vector if ui = 0, meaning that node i is not active in this case. [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF] The vector e := [eu1 T ]u2U captures the errors injected by the Byzantine nodes, where eu 6 = 0 if and only if YB = ; and where 1 is the all-ones vector of dimension n.

Let us adapt the main result (proposition 6 of [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF]), for the secure estimation of v(x). Note that the next theorem is based on the mean of the observations and not the real observations. We then design an algorithm based on the observations which leverages the next theorem and ensures a safe estimation of the gradient.

Theorem 1. For a given x, let us define solution v ⇤ (x) to be the solution of the following optimization problem:

min v2R m J(v) := X u2U n X i=1 |zi,u(x) -Ai(u)v|, ( 4
)
where

A i(u) is the i-th row of A(u), zi(x) = [zi,u(x)]u2U . If, for all K ⇢ {1, . . . , |U|n}, such that |K| = q, with X k2K |A k-nbk/nc+1 (u bk/nc+1 )z|  X k2K c |A k-nbk/nc (u bk/nc+1 )z|, ( 5
) for all z 2 R m -{0}, then, when δ ! 0, v ⇤ (x) = v(x) when |UB| = bq/nc.
Proof. Directly adapted from proposition 6 in [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF].

The previous theorem indicates us that as long as ( 5) is satisfied, we can use solution (4) to retrieve the gradient. Simpler sufficient conditions have been mentioned in [START_REF] Fawzi | Secure state-estimation for dynamical systems under active adversaries[END_REF].

ALGORITHM AND NUMERICAL STUDY

= ẑk i,u + b(k)1 u,u(k) (z i,u(k) -ẑk i,u ), 8i, 8u, v k+1 = v k + a(k) X u,i Ai(u) T sign(ẑi,u(k) -Ai(u)v k ),
where

v k := [v k m 0 ] 1m 0 m , a(k) and b(k) are such that P k a(k) = P k b(k) = 1, P k (a(k) 2 + b(k) 2 ) < 1 and lim a(k) b(k) ! 0.
• Gradient estimator: Use A1v k as an estimator of rf (x).

The convergence of the algorithm towards v ⇤ (x) comes from the fact that it can be seen as an asynchronous twotime scale stochastic approximation, where on the fast timescale every node runs a moving average on ẑi,u(k) for every k and every i and on the slow time-scale, a gradient descent is used to solve, in an online fashion (4). Convergence can be proved by using the ordinary di↵erential equation approach (see Ch. 6 and 7 in [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF]).

For our illustrative numerical study, we assume f (x) = 1 C-P n i x i , where C is a given constant modelling, for instance, node's capacity. We consider 6 nodes, and di↵erent scenarios for nodes' activation and the presence of Byzantine nodes. Fig. 1 (top) illustrates the convergence of the perturbation scheme to rf (x) when no Byzantine nodes are present, (left) when one node perturbates the network at a time (a.k.a. single perturbation), and (right) when all possible partitions of I are considered for nodes' activation (a.k.a. simultaneous perturbation). Fig. 1 (bottom) shows the results for same 6 nodes, but among which 2 are Byzantine, for the single-perturbation case (left) and simultaneous perturbation (right). The results over 10 simulations and the average are shown. The algorithm approaches the theoretical value of the gradient, while activation scheme and presence of Byzantine nodes have an incidence in the results.

  We now describe the algorithm for the non-Byzantine nodes. It can be summarized as follows: At every instant k, a subset of nodes perturbate the black-box model, obtaining Performance Evaluation Review, Vol. 50, No. 4, March 2023 an estimator of their respective partial derivative. Once the active nodes observe the perturbated function, they broadcast it to all the nodes. Using these observations, each node estimates the gradient based on (4).

	Decentralized Byzantine Gradient Estimation
	Initialization: Input, x, the working point.
	For each round k = 1, 2, . . .:
	• Perturbation Step: For every node i 2 YG(k): (1) Sample ∆i(k) 2 {-1, 1} from a Bernoulli distribution of parameter 1/2, (2) Play xi + δ∆i(k). (3) Observe
	z i,u(k) and u(k) and broadcast z i,u(k) to every node.
	• Decoding step: Update
	ẑk+1 i,u

CONCLUSION

We have proposed a decentralized algorithm to estimate the gradient of a function describing a black-box model. Such algorithm is robust to the presence of Byzantine nodes and takes into account their asynchronous behaviour. Future work will analyse convergence speed and optimize nodes activation.