Anne Mounier

The Hatano-Sasa equality: transitions between steady states in a granular gas

Keywords: 05.70.Ln -Non-equilibrium and irreversible thermodynamics 05.40.-a -Fluctuation phenomena, random processes, noise, and Brownian motion 47.70.Nd -Non-equilibrium processes, gas dynamics

An experimental study is presented, about transitions between Non-Equilibrium Steady States (NESS) in a dissipative medium. The core device is a small rotating blade that imposes cycles of increasing and decreasing forcings to a granular gas, shaken independently. The velocity of this blade is measured, subject to the transitions imposed by the periodic torque variation. The Hatano-Sasa (HS) equality, that generalises the second principle of thermodynamics to NESS, is verified with a high accuracy (a few 10 -3 ), at different variation rates. Besides, it is observed that the fluctuating velocity at fixed forcing follows a generalised Gumbel distribution. A rough evaluation of the mean free path in the granular gas suggests that it might be a correlated system, at least partially.

Introduction. -Recent decades have seen significant progress in nonequilibrium statistical mechanics, with the advent of the Fluctuation Theorems, the Jarzynski and Crooks relations [1][2][3]. These relations were at the time theoretical advances, with the support of the numerics. Experimental contributions came later, mostly because of technical limits. Indeed, the scales at which thermal energy dominates are small. Measurements of fluctuations at such scales has been prohibitively difficult until recently.

Usually, an inequality involving the average entropy production is the expression of the second principle of thermodynamics. The improvement brought by the fluctuation theorems is that an instantaneous rate of entropy production is expressed by an equality. It is somehow a local formulation.

The Jarzynski equality relates the Helmholtz free energy difference ∆F between two states A and B, to the average of the exponentiated work needed to perform the transition: e -β∆F = e -βW .

(1)

The brackets denote the average over a large number of transition paths, and β = 1/k B T , with k B the Boltzmann constant and T the temperature of the heat reservoir.

It can be equivalently written:

e -βW diss = 1, (2)
where W diss = W -∆F is the work dissipated into heat during the transition. The Jarzynski relation is valid for any transformation, whatever the rate. For a reversible transition, W diss is obviously zero. The fluctuation theorems, as well as the Jarzynski and Crooks relations, refer to systems in equilibrium states, or submitted to transitions between equilibrium states, reversible or not.

Another relation was derived latterly by Hatano and Sasa, in 2001. Generalising the Jarzynski equality, their prediction is drastically distinct as it addresses transitions between NESS of overdamped Langevin-type instead of equilibrium states. In that case, the forcing consists in nonconservative and potential forcings, together with a Gaussian white noise forcing, uncoupled to each other [4]. It writes similarly as the Jarzynski's equality (eq. 2):

e -Y = 1, (3)
with:

Y = τ dt α ∂ ln [ρ ss (x; α)] ∂α . ( 4
)
The integral is evaluated over the transition time τ between two distinct NESS. The dot refers to time derivative, and ρ ss (x; α) is the steady state probability density function (PDF) of the observable x at a specified value α of the control parameter.

It is implicitly assumed that for any fixed value of α, the system relaxes to a single steady state characterised by ρ ss (x; α). Eq. 3 is expected whatever the transition rate.

In a sense, the Jarzynski relation is a local extension of the 2 nd principle for equilibrium states, whereas Hatano-Sasa (HS) equation is its extension for NESS. Beyond the formal analogy between eq. 2 and 3, the HS relation comes from a distinct and more general phenomenological framework, called Steady State Thermodynamics [5,6].

Regarding the prediction of eq. 3, only two experimental confirmations have been produced so far. First is that of Trepagnier et. al. [START_REF] Trepagnier | Proc. Natl Acad. Sci. USA[END_REF], that dragged periodically a colloidal particle in water, with an optic tweezer. This system verifies all the requirements of the theorem, as the solvent is at equilibrium. It is a perfect case of Brownian motion, biased by an external conservative force. More innovative is the recent work of Gomez-Solano et. al. [START_REF] Gomez-Solano | [END_REF]. These authors performed a similar experiment, dragging a colloidal particle with an optic tweezer in water. But instead of equilibrium states, it is prepared in NESS before cycling of the order parameter, according to a specified protocol.

A step beyond, the present study is an experimental evidence that the HS equality also holds in a granular gas, i.e. for transitions between NESS in a dissipative medium.

The HS relation (eq. 3) refers to NESS Markovian processes, where fluctuations are not specifically of thermal origin. Therefore, the smallness of k B T must not be a limit... In other words, there is no need to study microscopic systems. The experiment presented here actually addresses a macroscopic system: it is extremely simple on its principle, and rather easy technically.

In a dilute, continuously shaken granular gas, a blade is rotated around a vertical axis by a small DC motor at controlled torque. The angular velocity, resulting of this external torque and the numerous collisions with the beads, is the stationary fluctuating quantity under study. It is measured by the very same DC motor that forces the rotation. The torque, which is the control parameter, is ramped up and down periodically, causing transition between steady states of different mean velocities. Histograms of the velocity are recorded for different values of the torque.

These histograms appeared unexpectedly well fitted by a generalised Gumbel (GG) distribution. This is an intermediate outcome of the present study, extremely useful for the calculations of eq. 4. Indeed, as the derivative of a GG distribution can be expressed exactly, the integral can be formulated. Therefore, it is easy to verify eq. 3, for different ramps of the control parameter.

However, a tentative interpretation of this interesting observation is given in the last section.

Experiment. -The set-up is sketched in fig. 1. It is an improved version of the one used recently to study Fluctuation Theorem [9]. It makes use of a DC motor, converting current into torque, reversely used as a generator to convert momentum into voltage. The same device is thus employed as actuator and sensor. A light plastic blade, embedded into a vibrated granular gas, is driven by a small and light DC motor. Forcing the rotation of the blade through the current (torque), one can measure simultaneously the rotation velocity through the voltage. The granular gas is composed of about 300 stainless steel beads of 3 mm diameter, vibrated in an aluminum vessel by a shaker. The vessel is 5 cm diameter and 6 cm deep, and its bottom is slightly cone-shaped to enhance horizontal momentum transfer. Thanks to a generator and a power amplifier, the shaker is supplied by a sine current at 40 Hz, providing a vertical acceleration of 41 ms -2 . In that conditions, the granular gas is rather dilute. The blade is 2 cm × 2 cm, placed a few mm from the bottom. The nominal power of the DC motor is 0.75 W . The rotor is ironless, to minimise inertia, and precious metal brushes improve the electrical contact with the commutator.

A current I injected into this motor results in a torque: Γ ∝ I, performing work against the granular gas. The same device can be used as a generator. In that case, the induced voltage e is proportional to the angular velocity: e ∝ θ. The proportionality factor accounts for the electro-mechanical characteristics of the motor. As it is the same in the motor or generator function, calibration is not needed.

Note that the excitation of the vibrator that keeps the granular gas in a NESS by compensating the dissipation, is totally distinct of the torque applied by the motor to probe the gas. The former is a few Watts, as the later is a few mW to minimise perturbation as much as possible.

The electric circuit is shown in fig. 2. The DC voltage supply is u 0 = 10 V (stabilised). The current I is driven by the voltage u supplied by a function generator. A time constant related to the inductance is irrelevant. The motor is depicted in fig. 2 as the assembly of a voltage source e (∝ θ), and the internal resistance r ≃ 21.2 Ω. The current is measured, thanks to a shunt resistor R = 56 Ω. A 24 bits simultaneous data acquisition system records the signals u 0 , u 1 and u 2 at a sampling frequency of 1024 Hz. The instantaneous current I(t) and induced voltage e(t) are easily calculated from these voltage measurements:

I(t) = (u 0 (t) -u 1 (t))/R and e(t) = u 1 (t) -u 2 (t) -r I(t).
The voltage generator is programmed to perform a cycle between low and high current regimes, i.e. torque cycles (fig. 3). Various periods and transition rate have been performed, as discussed below. Each of the regime L or H, corresponds to a NESS. One precaution to be taken concerns the values of u 0 and u. They must allow currents I such that the motor never completely stops rotating. Thus, no static friction is to be accounted for. Avoiding this difficulty is the reason why low values of torque are not explored in this work. A thermometer has been added on the vessel's cover to follow the temperature drift during the measurement. The temperature increases of about 5 • during a typical transient time of 5 hours. This elevation of temperature perturbs the measurements, probably because of the variation of air viscosity. Only the measurements performed after this transient of a few hours are considered.

Principle. -When the torque is fixed, the blade rotates with a fluctuating angular velocity. The fluctuations are caused by the collisions with the granular gas. The equation of motion of the blade + rotor mobile writes:

M θ + γ( θ) = Γ(t) + η(t), ( 5
)
where θ is the angle, and dots stand for time derivatives. M and γ are respectively the moment of inertia and the viscous friction term. This γ( θ) stands for an effective viscous damping due to the collisions, like in Brownian motion. It also includes a negligible (turbulent) drag on air. A small solid friction term is present, mostly in the commutator of the motor. It is constant, as the driving is such that the mobile never stops rotating. It can therefore be included as an offset in the torque Γ, and play no role.

The deterministic torque Γ(t) is imposed from outside.

The last term η(t) is the random force accounting for the shocks of the beads. It represents the coupling with the NESS granular gas heat bath, i.e. the momentum transfer rate at each shock with the beads. All this description is written with Brownian motion theory in mind. Hints are given below that this description might not be correct. Eq. 5, that mimics the probing device, governs the velocity resulting from the balance between a deterministic forcing, the coupling with a stady state reservoir, and friction. At first glance, it takes the form of a Langevin equation, if the noise η can be considered short-time correlated. However, a first difficulty comes from the dependences of the forcings with one another. Indeed, the random force η(t) is affected when Γ(t) is changed, as shown below. The whole balance between deterministic and random forcings is varied. The angular velocity θ follows in a non trivial manner. All things considered, the description of this system with eq. 5 as a Langevin equation is not as simple as it first appears.

The purpose of this work is to study transitions between two NESS, characterised by the fluctuating angular velocity θ(t), while Γ(t) is ramped at fixed rate between two specified values corresponding to 'states' L and H. The HS equality is verified with a very good accuracy.

For convenience, another set of variables than { θ, Γ} is used. The observable e (in Volts) is centered and normalised, such as x(t) = (e(t) -ē)/σ, with the mean e, and the variance σ 2 = (e -e) 2 . (The bar denotes time-average within a single steady state.) The control parameter is from now on the current I(t) (in Amperes).

As already mentioned, the calibration factor is left aside, not necessary to test eq. 3. This equation is rewritten with the new working electric variables:

exp - τ dt İ ∂ ln [ρ ss (x ; I )] ∂I = 1. ( 6
)
As discussed above, the quantities {x, I} are directly measured. The whole analysis procedure is performed on this new set of variables. The derivative of ln [ρ ss (x; I)] is to be taken from the histograms calculated over large samples of x, at fixed values of I. The integration over the transition time is easy, as well as the average over a large number of transitions. The derivative of histograms with respect to the control parameter I is actually more difficult. However, a specific character of these histograms is to be well fitted by a GG distribution (see next section). This observation is of great help for the analysis procedure.

The generalised Gumbel distribution. -The histograms of x at fixed I have an asymmetric but universal shape, whatever the value of the control parameter I. They are very well fitted by a GG distribution (fig. 4). Assuming the variable x is distributed according to a GG law, it is characterised by a single shape parameter a, that accounts for the asymmetry: a ∼ 1/< x 3 > 2 . (The PDF tends to a Gaussian distribution if a → ∞.) It writes:

ρ ss (x) = K a exp [a [-b a (x + s a ) -exp (-b a (x + s a ))]] , (7)
The mean and the variance, as well as the normalisation factor, can all be expressed as functions of a:

b a = d 2 lnΓ (a) da 2 , ( 8a
)
s a = 1 b a ln(a) - dlnΓ (a) da , (8b)
K a = a a b a Γ (a) , (8c)
thanks to the gamma-function: Γ(a) = ∞ 0 t a-1 e -t dt . As the PDF's shape as well as the mean and standard deviation only depends on a, it can be rewritten as ρ ss (x; a) after a change of variable. The integral term Y of eq. 6 is therefore rewritten:

Y = τ dt İ da dI ∂ ln [ρ ss (x ; a)] ∂a . (9)
The dependance in I of the parameter a, obtained from the fitting of the histograms, allows to calculate da dI . Assuming ρ ss is a GG distribution, the differentiation needed in eq. 9 can be performed exactly.

Results. -To center and normalise the variable e, the mean e and standard deviation σ are directly measured from the voltage time series corresponding to stationary states for over ten fixed values of I. They are plotted against the current I in fig. 5 The standard-deviation σ is a growing function of I, not expected to cancel for I = 0. Indeed, at zero-torque, fluctuations of velocity remain, because of the random forcing η. By effecting certain calibration, it could be linked in a non local manner to a granular temperature [10].

I (A) σ (V )
It is to be noticed that an extrapolation of e following the linear fitting does not go to 0 for I = 0. This is obviously abnormal, as the blade should not rotate without torque (for symmetry reason, as < η >= 0). There might be a nonlinearity γ( θ) in the 'viscous drag' of eq. 5. This point is discussed below. Now, the fitting of the histograms for different values of I is performed, and the parameter a is extracted. It is plotted against I in fig. 6. This parameter a increases for lower I, meaning that the distribution symmetrises when the external excitation decreases. Joubaud et. al. recently observed in a granular gas, that velocity fluctuations without external forcing look Gaussian [11]. Their experiment is designed for small static friction. It is not quite accurate to do such measurements here in this low-torque regime, because of the friction in the commutator of the DC motor.

It is not surprising to notice that the statistical noise is larger for increasing order moments: e, σ, and a.

A tedious derivation leads to the following exact expression for the log-derivative of the GG distribution:

∂ln [ρ ss (x; I)] ∂a = 1 2Ψ ′ Ψ ′′ -2xΨ ′3/2 + (a -e Ψ-x √ Ψ ′ )(2Ψ ′2 -x √ Ψ ′ Ψ ′′ ) , (11)
where Ψ(a) = dlnΓ(a) da is the so-called digamma function, Ψ ′ and Ψ ′′ its successive derivatives with respect to a.

In the limit a → ∞, this expressions reduces to a quadratic form: ∂ln[ρss(x;I)] ∂a = 1 2a (x 2 -1), consistent with a Gaussian ρ ss (x; I), as da dI < 0. This limit refers to vanishing I, as discussed above; the linear relation between I and a is only a working approximation.

The log-derivative is computed for all the measured time series x(t), then multiplied by İ and da dI . Realisations of Y are obtained by integration for each transient. Thence, the average of the exponential over dozens of transitions is carried out, separately for leading and trailing edges (increasing and decreasing torques), for slow and fast transition rate. Results are shown in the following table: Y is equivalent for one path between two NESS to the dissipated work between two equilibrium states calculated through Jarzynski equation. It would certainly be interesting to compute its histogram. However, the sample would have to be much larger than that presently available.

Discussion. -This article presents an experimental study of a granular gas, regarded as an ersatz of a heat reservoir. The granular gas is considered as a thermostat, however dissipative. A simple device coupled to this reservoir exchanges energy with it.

This experiment takes advantage of the fact that smallness of the systems is not required. The granular gas is probed with a blade rotating about its vertical axis, which velocity is measured at controlled torque. The torque is cycled in such a way that angular velocity undergoes transitions between stationary states.

The Clausius inequality gives a lower bound to the work dissipated in transitions between equilibrium states. The HS equality generalises it to transitions between NESS. This article describes the first experimental observation of the HS prediction in a dissipative system. The agreement is impressive even if the dependence of the distribution is not known over the full range. It appears to hold indifferently whether the forcing is undergoing an increasing or decreasing transient, whether steep or gentle.

Strictly speaking, the HS relation is expected to be valid for stationary states. However, one could expect no departure as long as the transition time τ is larger than a microscopic time of the reservoir's fluctuations, where rearrangements can occur during the evolution of the order parameter. As it is the mean time between two shocks, such rapid transition is probably limited in the present experiment by the inertia of the blade. Therefore, the range of applicability of the HS relation is larger than expected, from this point of view. A generalisation of HS theorem to non stationary processes is discussed in [12].

It is assumed from the beginning that the gas is dilute. To make this statement quantitative, the mean free path is evaluated, thanks to crude dimensional arguments. First, the density. Because of vertical stratification, density is larger in the lower part of the cell. If all the beads are assumed uniformly distributed in the lower h = 1 cm of the cell, the density is n = N/(πR 2 h), with R the radius of the vessel and N = 300 the number of beads. It gives n ∼ 16 cm -3 , which means that the mean distance between beads is about 4 mm. Now, following the kinetic theory of gases, the mean free path is: λ = 1/(nπr 2 ), where r = 1.5 mm is the radius of a bead. It gives λ ∼ 9 mm. This evaluation is a rough order of magnitude, it should be improved. However, it is close to any length in this experiment! Besides, the correlation time of x(t) is of the order of 24 ms. This corresponds roughly to λ/(L θ). Correlation in space and time are consistent.

This result, associated with the asymmetry of the PDF and the nonlinearity of the 'drag' γ( θ), shows that a description of this system in terms of a simple Brownian motion is too simplistic. The Knudsen number must be considered, defined as: Kn = λ/L, L being a characteristic length of the system, like the radius of the blade.

The central requirement for a process to verify the HS equality is to follow an overdamped Langevin equation. The gas being rarefied means that collisions come one by one on the blade. Therefore, the noise η(t) is not likely to be a Gaussian white noise, and assuming a (nonlinear) friction γ(x) is not representative of the physical reality. There is no reason to neglect the inertial term in eq. 5. For all these reasons the equation of motion does probably not verify required conditions, i.e. with such a high Kn, the system does not behave like simple Brownian motion. In such case, the experimental verification of the HS equality enlarges its range of validity. A better determination of λ, or a direct test of the Markovian character of the process is badly needed. (Numerically?) An opening would be trying this relation with experimental processes clearly non-Markovian, or rapidly varying, change parameters like stratification, density, sizes, excitation, to identify which conditions causes failure of HS prediction.

Besides, it is shown that the fluctuations of velocity at fixed forcing, and therefore the power injected by the blade into the granular gas, are asymmetric and resemble a GG distribution. Such kind of distribution have been found describing fluctuations of power injected in dissipative or correlated systems (see experiments on turbulent flows in [13,14], numerical simulations on granular gases in [15]), or other global quantities such as the fluctuations of magnetisation in critical ferromagnetic systems with finite size effects (see XY or Ising model computations in [16,17]). The usual theoretical explanation for such statistics is that global quantities's fluctuations are affected by correlations (see [18,19] and references therein). The very basic idea is that the shape parameter a is linked to the number of degrees of freedom of the system: asymmetry comes from the finiteness of this number. In the present situation, the tentative explanation rely on a dependance between the relatively large value of Kn and correlation.

Another cause of asymmetry in statistics can be clustering, due to dissipation. However, it would simply enhance vertical density stratification, without causing clusters that the blade would hit during its rotation.

A blade of half width (1 cm × 2 cm) has been tried in the same configuration. As a result, the fluctuations are much more asymmetric (a is much smaller, for instance 5.52 → 2.45). This observation corroborates qualitatively the previous argument, as Kn is doubled.

At this point, it is important to clarify the Markovian character of the process involved, and the correlations in the system. Answers to these questions could mean a widening of the conditions of this theorem, and explain the asymmetric statistics altogether. It could also be interesting to relate the parameter a to Kn.

Fig. 1 :

 1 Fig. 1: The mechanical system is composed of a vibrating vessel containing the beads, excited by a shaker. The probing DC motor is fixed on the cover, here pulled out for clarity.

Fig. 2 :

 2 Fig. 2: The electrical sketch of the motor's command.

Fig. 3 :

 3 Fig. 3: Sketch of the control parameter cycles, driving the system at 'High' torque and 'Low' torque NESS, or in constant rate transitions in-between. Transition time is τ .

Fig. 4 :

 4 Fig.4: A histogram of the centered and normalised induced voltage x(t) = (e(t) -e)/σ at fixed current I is plotted in semilog axis (dots). The fitting is performed with a GG distribution (line). The best fit is obtained for a = 2.5.

Fig. 5 :

 5 Fig.5: The mean value e (up) and the standard deviation σ (down) at fixed current I is plotted against I. A linear fitting is performed over the range available.

Fig. 6 :

 6 Fig. 6: The asymmetry coefficient a is obtained for each I by fitting the histogram with a GG distribution. a is plotted against the current I, together with the inverse squared skewness. The linear fittings give the simplest dependance of those three quantities with I: e = 9.3 I + 0.12, (10a) σ = 2.6 I + 3.2 10 -2 , (10b) a = -4.7 10 2 I + 10 ⇒ da dI = -4.7 10 2 . (10c)

  . A linear fitting is performed, valid at least in the range of interest.

		0.26
	e (V )	0.24
		0.22
			0.01	0.011 0.012 0.013 0.014 0.015
		0.08
		0.07
		0.06
		0.05	0.01	0.011 0.012 0.013 0.014 0.015

Table 1 :

 1 The HS eq. 3 is confirmed with a very good accuracy:

		leading edge trailing edge
	τ = 10 s	0.9890	1.0069
	τ = 30 s	1.0012	0.9985

We gratefully acknowledge S. Ciliberto for the original suggestion of investigating the HS relation in our system, for so many discussions and advises, and rereading. Many thanks to E. Bertin and M. Clusel for explanations on extreme values statistics, M. Bourgoin, E. Lutz, M. Peyrard, A. Boudaoud, J. R. Gomez-Solano, J.-P. Zaygel, F. Delduc for many discussions and suggestions, as well as all the students and members of the ENS-Lyon Physics Lab. Thanks to F. Maurel for help in figures.


Hélène Le

Jean-Sébastien Bedo
email: jeansebastien.bedo@orange.com

Distributed Learning in Hierarchical Networks

Keywords: Algorithmic Game Theory, Coalition, Distributed Learning, Regret

In this article, we propose distributed learning based approaches to study the evolution of a decentralized hierarchical system, an illustration of which is the smart grid. Smart grid management requires the control of non-renewable energy production and the integration of renewable energies which might be highly unpredictable. Indeed, their production levels rely on uncontrolable factors such as sunshine, wind strength, etc. First, we derive optimal control strategies on the nonrenewable energy productions and compare competitive learning algorithms to forecast the energy needs of the end users. Second, we introduce an online learning algorithm based on regret minimization enabling the agents to forecast the production of renewable energies. Additionally, we define organizations of the market promoting collaborative learning which generate higher performance for the whole smart grid than full competition.

I. INTRODUCTION

We describe and test distributed learning algorithms in the context of a hierarchical highly connected network of agents, an illustration of which is the smart grid. A first class of algorithms will be used to control the non-renewable energy production. Then a second class will be proposed to favor the introduction of renewable energy sources. The first class of algorithms belongs to the reinforcement learning category. Tit for tat and fictitious play are well-known in repeated game theory [START_REF] Fudenberg | The Theory of Learning in Games[END_REF], [START_REF] Young | Strategic Learning and its limits, the Arne Ryde Memorial Lecture Series[END_REF]. They require different knowledge levels i.e., the access to the agents' previous decisions under tit for tat and the access to the full history of the agents' past decisions under fictitious play. They form a natural bridge with more sophisticated learning rules used in machine learning such as regret based learning [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF], [START_REF] Young | Strategic Learning and its limits, the Arne Ryde Memorial Lecture Series[END_REF]. This latter is a rather original approach in the machine learning community [START_REF] Bubeck | Online Optimization[END_REF], [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF]. When properly designed, its performance to learn mixed strategies over various datasets overperform other classical machine learning approaches such as support vector machines, autoregressive processes and artificial neural networks [START_REF] Cadre | Energy Demand Prediction: A Partial Information Game Approach[END_REF]. The originality of this article for the machine learning community relies on the study of these algorithms in a decentralized and hierarchical framework resulting from the double leaderfollower structure of the game.

We have chosen to place the model in the context of the smart grid although the results that we derive are quite generic and can be applied to any hierarchical network with a distributed access to the scarce resource and no capacity storage. Such framework is quite common in the revenue management literature [START_REF] Talluri | The Theory and Practice of Revenue Management[END_REF] and can be applied to many other industries like to model the interconnections between autonomous systems or content providers and access providers in the Internet, to better understand the relations between suppliers and retailers in the retail industry, etc. Going back to the smart grid, we give a broad definition of it. Initially, smart grids are networks enabling a decentralized production of the energy and involving bidirectional energy flows which are controlled by a complex, global and secured communication network. The network is said to be smart because it is capable of integrating efficiently each agent's action (producers, providers and consumers) in order to guarantee a sustainable and secure supply at lower cost.

Nowadays, in Europe and in France especially, traditional electrical networks rely on nuclear based energies [START_REF] De Ladoucette | The electricity of the future: a mondial challenge[END_REF]. The main difficulty is to adapt the production level so as to meet the uncertain demand level. In this article, we build a first model where two learning strategies based on tit for tat and fictitious play are used to adapt the production level to meet the demand level. In this context, the distributed learning algorithms can be used as distributed control algorithms providing boundaries on the agents' biases in the prediction process.

Because of their structure, smart grids offer a substantial opportunity for the integration of renewable energies. Renewable energies like wind power, photovoltaic, geothermal, biomass, small hydroelectric facilities, etc., are highly unpredictable since they depend on uncontrolable exterior factors like wind, level of sunshine, etc. They are cleaner but their production being more difficult to forecast, they are far more difficult to integrate into the electrical network. It requires to develop efficient learning algorithms to predict both the consumers' demand, which can be highly erratic due to their new active role in the grid, and the renewable energy productions.

In practice, the electrical network based on the smart grid model is composed of a multitude of microgrids. Microgrids are modern, small-scale versions of the centralized electrical system. They can be either sellers in case where they have a surplus of power to transfer, or buyers in case where they need to buy additional power to meet their demand. Saad et al. propose a distributed microgrid coalition formation algorithm enabling a decrement of 31% of the average power losses relative to the non-cooperative case, in [START_REF] Saad | Coalitional Game Theory for Cooperative Micro-Grid Distribution Networks[END_REF]. However, their result relies on strong assumptions. Indeed, they make the hypothesis that the consumers' demand is random since it depends on unpredicable factors such as consumption level, consumption behavior, etc. [START_REF] Li | QoS routing in smart grids[END_REF]. Additionally, they make the simplifying assumption that the power surplus which is defined as the difference between the total power and the demand, is distributed according to a known density function.

Actually, the justification of the fitting of a specific parametric density function requires the game designer to learn at least its parameters. In the statistical learning literature, there are three major learning approaches, each of them corresponding to a particular abstract learning task: supervised learning, unsupervised learning and reinforcement learning [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF], [START_REF] Young | Learning by trial and error[END_REF]. Tasks that fall within the paradigm of reinforcement learning are control and online optimization problems, games and other sequential decision making tasks. Learning based on regret minimization as described in [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF], belongs to this category. Additionally, we observe in [START_REF] Cadre | Energy Demand Prediction: A Partial Information Game Approach[END_REF] that the performance resulting from learning based on regret minimization tested on real data bases, are clearly superior to the ones obtained using supervised learning approaches. As a result, these points have convinced us to use a learning approach based on regret minimization. The difficulty is then to extend the already existing method to a distributed learning framework and to clearly identify how such a decentralized access to the information will affect the smart grid economic organization.

The existing literature on distributed learning primarly focuses on distributed learning algorithms that are suitable for implementation in large scale engineering systems [START_REF] Li | Decoupling coupled constraints through utility design[END_REF], [START_REF] Pradelski | Learning efficient Nash equilibria in distributed systems[END_REF], [START_REF] Young | Learning by trial and error[END_REF]. The results mainly concentrate on a specific class of games, called games of potential [START_REF] Shapley | Stochastic games, in proc[END_REF]. This class of games is of particular interest since they have inherent properties that can provide guarantees on the convergence and stability of the system. However, there exist some limitations to this framework. The most striking one is that it is frequently impossible to represent the interaction framework of a given system as a potential game [START_REF] Marden | Achieving Pareto Optimality Through Distributed Learning[END_REF].

The learning game studied in this paper belongs to the category of repeated uncoupled games. Indeed one agent cannot predict the forecasts and so actions of the other agents at a given time period. To take his decision i.e., optimal prices and traded quantities of energy, each agent is aware of the history of forecasts of all the agents and of his utility. Recent work has shown that for finite games with generic payoffs there exist completely uncoupled learning rules i.e., rules where the agents observe only their own prediction history and their utility, that lead to Nash equilibria that are Pareto optimal [START_REF] Pradelski | Learning efficient Nash equilibria in distributed systems[END_REF]. Marden et al. exhibit a different class of learning procedures that lead to Pareto optimal vector of actions that do not necessarily coincide with Nash equilibria [START_REF] Marden | Achieving Pareto Optimality Through Distributed Learning[END_REF]. A well-known illustration of the practical interest of Pareto optimality can be found in the prisoner dilemma where the Nash equilibrium is inefficient compared to the Pareto optimum that would be obtained if the prisoners had collaborated [START_REF] Myerson | Game Theory: An Analysis of Conflict[END_REF]. However, one serious concern regarding Pareto optimality is that the optimum is generally not unique and deciding which one should be implemented by the system might in some cases, require contracts, communication or bargaining mechanisms to be designed at the beginning of the game. Of course this is not always the case, as proven by [START_REF] Marden | Achieving Pareto Optimality Through Distributed Learning[END_REF] and [START_REF] Pradelski | Learning efficient Nash equilibria in distributed systems[END_REF]. Under conditions stating that it is not possible to divide the interacting agents into two distinct subsets that do not mutually interact with one another, Marden et al. prove that the game dynamics induce a Markov process over the finite state space which is defined as the set of the triples containing the chosen action, the resulting utility and an additional binary parameter called the agent's mood [START_REF] Marden | Achieving Pareto Optimality Through Distributed Learning[END_REF]. Then they focus on characterizing the support of the limiting stationary distribution i.e., the stable states. In particular, they prove that any stable state maximizes the social welfare under an initial assumption on agent interdependency. Compared with our model, Marden et al. study a stochastic game where the agents always control their production. They take as an example the wind turbines which can adapt their power to maximize the whole wind farm's social welfare defined as the sum of the total power produced by each turbine. In our game setting, the production of the renewable energies cannot be controlled since it relies on exogeneous events. Therefore, it requires to introduce decentralized learning approaches based on online optimization [START_REF] Bubeck | Online Optimization[END_REF] and to study the resulting economic interactions using a game theoretic approach.

The article is organized as follows. In Section II, we introduce the economic interplays between the agents, describe the repeated game setting and the optimization program for each agent. Then the double Stackelberg game is solved in Section III in complete and partial information frameworks. In Section IV, we consider the case where producers control their productions while service providers need to make predictions about the microgrid energy needs to optimize their prices and traded quantities of energy. The performance of two learning algorithms: tit for tat and fictitious play are evaluated analytically. In Section V, the integration of renewable energies in the grid requires the development of an efficient online learning algorithm based on regret minimization. We finally prove that collaborative learning through a grand coalition generates higher performance for the whole smart grid than in the case of individual learning under full competition.

II. THE MODEL

The smart grid ecosystem is made of three categories of agents:

• K energy producers e 1 , ..., e K which can be associated with nuclear plants, photovoltaic park managers, wind farm administrators, etc. The produced energy can be either non-renewable like in the case of nuclear plants or renewable when it comes from photovoltaic parks, wind farms, etc. • n service providers s 1 , ..., s n which might buy energy from each of the K producers and route it through their transport network to their clients.

• n microgrids M 1 , ..., M n , each one of them being committed with a single energy provider. We assume that each end user contracts with only one service provider and does not churn from one service provider to another during all the period of our study. This assumption holds well if we consider local or regional utility companies for example. We introduce two individual sequences: ν s i (t), which contains the energy needs issued from the clients of service provider s i and ν e k (t), which coincides with producer e k 's production, at time period t. The economic relationships between the agents in the grid are pictured in Figure 1. The symbol $ is used to represent the directed monetary transfers between the involved agents.

A. Repeated game setting

We model the interplay between all the agents through a repeated game. At each time period t of the game:

(1) The energy producers e k communicate their prices pk (t) > 0 for one energy unit (i.e., W h) to the service providers (2) The service providers s i place energy quantity orders to energy producers: the quantity ordered by s i to e k is denoted by q ik (t)

(3) The service providers s i communicate their prices p i (t) > 0 for one energy unit to their end users The end users M i need ν s i (t) energy units for the period (which could depend on weather, cooking, etc.) (4) The end users decide to find alternative sources of energies for a i (t) energy units. They buy the rest of their needs ν s i (t) -a i (t) to service provider s i Each energy producer e k produces ν e k (t) energy units The energy producers distribute their production to service providers: e k delivers α ki (t)ν e k (t) energy units to service provider s i ( ) The energy producers incur penalties if they did not fulfill the energy orders placed by the service providers ( ) The service providers incur penalties if they did not fulfill the energy needs of their end users The penalties are proportional to the difference between the initial energy order and the final energy delivery. More precisely, e k incurs the penalty γi q ik (t) -α ki (t)ν e k (t)

+ with γi > 0, from service provider s i , and s i incurs the penalty

γ i ν s i (t) -a i (t) -k α ki (t)ν e k (t)
+ with γ i > 0, from end users M i . The penalties are donated to the unbiased regulator who is supposed to control the overall energy distribution system. Various mechanisms of transfer can then be implemented by the unbiased regulator. The penalties can be distributed to shareholders of the energy producers or used for social purposes.

B. Optimization program for each agent

The only decision variable for the end users is the quantity of energy that they decide to get from alternative sources: a i (t). We assume that the end users have no lever to influence their random energy needs: ν s i (t). The information available to end users is the price of an energy unit from their service provider and their energy needs ν s i (t) for the time period. We assume that finding alternative energy sources rather than buying it to the service provider has some costs for the end users. More precisely, finding a i (t) energy units through alternatives costs them ai(t) 2 2 per time period. As a result, the total cost of energy for the end users M i is:

p i (t) ν s i (t) -a i (t) + a i (t) 2 2 (1)
End users M i choose a i (t) in order to minimize their total cost of energy depending on the energy price.

The decision variables for each service provider s i are the energy unit price p i (t) and the energy orders q ik (t) for each energy producer e k . The only information available to service provider s i when he makes his decision are the energy unit prices pk (t) of all the energy producers. He has to forecast the energy needs of his customers and the energy production of all the energy producers. Following our description of the interplay between the agents, the utility for service provider s i at time period t is:

π i (t) = p i (t) ν s i (t) -a i (t) - k=1,...,K q ik (t) pk (t) -γ i ν s i (t) -a i (t) - k=1,...,K α ki (t)ν e k (t) + (2)
where for any real x, we set: x + = max{x; 0}. Service provider s i chooses his energy unit price and his energy orders toward energy producers so that π i (t) is maximized.

The only decision variable for each energy producer e k is the energy unit price pk (t) that he proposes to the service providers. We assume that the energy producer cannot influence directly the energy he produces at each time period. This assumption holds well if, for example, we look at a wind turbine farm without any investment in an additional wind turbine during the study period. The variation of the wind intensity will make vary the energy produced without any lever for the energy producer. When energy producer e k makes his decision, he has no information because he is the first agent to play in the time period. He has to forecast the energy quantity that he will produce and the energy orders of all the service providers.

To define the sharing coefficients α ki (t), we consider a weighted proportional allocation of resource that allows producers to discriminate energy allocation by providers. This framework is a generalization of the well-known proportional allocation [START_REF] Saad | Coalitional Game Theory for Cooperative Micro-Grid Distribution Networks[END_REF] to weighted energy orders with penalty coefficients as weights. Such a resource sharing mechanism has already been introduced by Nguyen and Vojnović, in [START_REF] Nguyen | Weighted Proportional Allocation[END_REF]. This means that between two providers booking the same quantity, the one having the highest penalty coefficient will receive the largest part of the producer's available energy. Indeed, the producer wants to minimize his overall penalty and therefore allocates larger parts of his production to providers who appear to him as more threatening than the others. More precisely, in the rest of the article, we will assume that:

α ki (t) = γi q ik (t) j=1,...,n γj q jk (t) (3)
Then the utility of energy producer e k at time period t equals:

πk (t) = pk (t) i=1,...,n q ik (t) - i=1,...,n γi q ik (t) 1 -γi ν e k (t) j=1,...,n γj q jk (t) -1 + (4)
Energy producer e k chooses his energy unit price so that πk (t) is maximized.

III. DOUBLE STACKELBERG GAME RESOLUTION

At first we consider that the double Stackelberg game described in Section II-A is played in a complete information setting on the individual sequences ν s i (t), ν e k (t), ∀i = 1, ..., n, ∀k = 1, ..., K.

Proposition 1: If the system is in energy shortage (Inequality ( 16)) and if penalties are fair (Inequality (15)), the double Stackelberg game under complete information admits a unique equilibrium :

• for each provider s i , ∀i = 1, ..., n, a i (t) = p i (t) is defined by Equation ( 11) and the quantity orders q ik (t) are defined by Equation ( 14) • for each producer e k , ∀k = 1, ..., K., pk (t) is defined by Equation ( 17) Proof of Proposition 1. The proof detailing the agents' optimal decisions can be found in Appendix and in [START_REF] Cadre | Collaborative Learning is Better, working paper of the Alternative Energy and Nuclear Power Commission[END_REF].

We now consider that the individual sequences ν s i (t), ν e k (t), ∀i = 1, ..., n, ∀k = 1, ..., K are not public knowledge. To simplify, we will assume that the energy needs ν s i (t) are all drawn from a common set X s and that energy productions ν e k (t) are all drawn from a common set X e . We assume that X s and X e are public knowledge and are finite i.e., |X s | < +∞ and |X e | < +∞.

In the rest of the article, the game settings (energy needs of the microgrids, energy production and penalties) will be chosen so that we are always in energy shortage and with fair penalties. It can be ensured easily by choosing the maximum value of X e small enough compared to the minimum value of X s .

According to the analytical expression of the equilibrium derived in the proof of Proposition 1 and in [START_REF] Cadre | Collaborative Learning is Better, working paper of the Alternative Energy and Nuclear Power Commission[END_REF], service providers need to forecast the energy productions of each energy producer and the energy needs of the microgrids to optimize their decisions. We will denote by f i (X, t) the forecast of service provider s i at time period t for the random variable X. We will also use the following notations:

• f i (t) = f i (ν s i , t), f i (ν e 1 , t), ..., f i (ν e K , t
) to denote the predictions made by service provider s i about microgrid M i instantaneous needs and about the production of each energy producer e k , k = 1, ..., K.

• f (t) = f 1 (t), ..., f n (t) which contains the forecasts of all the service providers.

• f -i (y, t) = f 1 (t), ..., f i-1 (t), y, f i+1 (t), ..., f n (t) which contains the forecasts of all the service providers except s i which prediction is set equal to y.

• ν(t) = ν s 1 (t), ..., ν s n (t), ν e 1 (t), ..., ν e K (t) which contains the microgrid energy needs and the production of each energy producer e k , k = 1, ..., K. By substitution of the forecasters in the Stackelberg game solution at equilibrium as obtained in Proposition 1 proof and in [START_REF] Cadre | Collaborative Learning is Better, working paper of the Alternative Energy and Nuclear Power Commission[END_REF], we infer the optimal decisions for service provider s i at each time period t:

p i (t) = f i (ν s i , t) + γ i 2 q ik (t) = f i (ν e k , t) pk (t)

L(i) γi

n -1 δ As a result, the utility of service provider s i at each time period t is:

π i (t) = f i (ν s i , t) + γ i 2 ν s i (t) - f i (ν s i , t) + γ i 2 - L(i) γi n -1 δ k=1,...,K f i (ν e k , t) -γ i ν s i (t) - 1 2 f i (ν s i , t) + γ i - k=1,...,K f i (ν e k , t)L(i) j=1,...,n f j (ν e k , t)L(j) ν e k (t) + (5)
The choice of the agents' forecasting strategies varies depending whether we consider renewable or non-renewable energies. Indeed, in case of non-renewable energies, the producers have the opportunity to control their production and the providers can play on their prices to control their demand level. Therefore, in this case, the distributed learning problem becomes a distributed control problem.

IV. CASE OF NON-RENEWABLE ENER-GIES: A DISTRIBUTED CONTROL PROBLEM

In this section, we suppose that each producer controls his production. This is typically the case for nuclear plants or hydraulic centrals which constitute today the majority of energy sources in Europe [START_REF] De Ladoucette | The electricity of the future: a mondial challenge[END_REF]. Additionally, providers can adjust the demand of their mircrogrid through price incentives.

Substituting the optimal price pk (t) and traded quantities of energies q ik (t), ∀i = 1, ..., n in producer e k 's utlility as defined through Equation ( 4), we observe that it is linear increasing in ν e k (t). As a result, producer e k will maximize his production at any time period, i.e.: ν e k (t) = max{X e }. The service providers anticipating the behavior of the producers, they will align their forecasts concerning the productions on the value max{X e }. By differentiation of service provider s i 's utility defined in Equation ( 5) under energy shortage assumption, we obtain that it is maximized in f i (ν s i , t) if, and only if, f i (ν s i , t) = ν s i (t) i.e., the forecast made by s i about microgrid M i energy needs coincides with its true value. The problem of course, is that at the beginning of time period t, provider s i does not observe ν s i (t). Therefore he needs to develop learning approaches to predict it.

In this section, we apply two learning approaches which are quite classical in the theory of learning in games [START_REF] Fudenberg | The Theory of Learning in Games[END_REF], [START_REF] Young | Strategic Learning and its limits, the Arne Ryde Memorial Lecture Series[END_REF]. While tit for tat requires a rather low level of information, agents basing their forecasts on fictitious play need to keep track of the history of all the past predictions. In spite of this larger memory requirement, fictitious play forms a natural bridge between rather naive type of learning such as tit for tat where the agents' forecasts are based solely on their earlier observation, and more sophisticated rules like regret based learning that will be detailed in the case of renewable energies in Section V.

A. Tit for tat

Tit for tat is a commonly used strategy in repeated game theory. An agent using this strategy begins by cooperating, and then answers to his opponent's previous action. For example, in the repeated prisoner dilemma with infinite or unknown time horizon, the prisoners begin by cooperating, since it enables them to maximize the sum of their utility. They repeat this strategy until one of them defect in which case the other defects too in the next time step [START_REF] Myerson | Game Theory: An Analysis of Conflict[END_REF].

Assuming that providers use tit for tat as learning strategy, they estimate their microgrid energy needs at time period t using the commonly shared energy needs of the microgrid at time period t -1. Judging by the form of π i (t -1) as defined in Equation ( 5), once they have observed the utility value at the end of time period t -1, it is quite straigthforward for them to infer ν s i (t -1) since π i (t -1) is linear in ν s i (t -1) and they know all the other terms in the equality. Therefore under tit for tat, for any provider s i , the forecaster takes the form: f s i (ν s i , t) = ν s i (t -1), ∀i = 1, ..., n. At time period t, provider s i forecasts microgrid M i energy needs using its previous value.

In the following proposition, we give the analytical expression of provider s i 's loss:

l i f (t), ν(t) = π 0 i (t) -π i (t)
It is the difference between what he would have received if his predictions were correct or unbiased (π 0 i (t)) and what he really receives in the course of the game.

Proposition 2: Under the assumption that provider s i 's forecasting strategies about microgrid M i energy needs are based on tit for tat, his loss at time period t is:

l i f (t), ν(t) = ν s i (t) -ν s i (t -1) γ i 2 - 1 4 ν s i (t -1) -ν s i (t)
Proof of Proposition 2. We have made the assumption that the penalty coefficients are chosen so that we are always in energy shortage. It corresponds to Case 2 described in Subsection B.2 of Appendix. Practically, this means that the penalty term in Equation ( 5) is positive. Substituting the tit for tat prediction rule: f i (ν s i , t) = ν s i (t -1) in Equation ( 5), we obtain that:

l i f (t), ν(t) = ν s i (t)+γi 2 ν s i (t)- ν s i (t)+γi 2 + γ i ν s i (t)+γi 2 - ν s i (t-1)+γi 2 ν s i (t)- ν s i (t-1)+γi 2 +γ i ν s i (t-1)+γi 2
. Simplifying the identical terms of opposite sign, we obtain the stated formula:

l i f (t), ν(t) = ν s i (t) -ν s i (t -1) γi 2 - 1 4 ν s i (t -1) -ν s i (t) .

B. Fictitious play

Fictitious play is a widely used model of learning [START_REF] Fudenberg | The Theory of Learning in Games[END_REF]. In this process, agents behave as if they think they are facing a stationary, but unknown, distribution of opponents' strategies. This assumption might be too strong in particular if the system in which the agents are learning fails to converge.

Considering fictitious play as the learning rule, producers and providers choose their forecast of microgrid M i energy needs as a best response to the empirical distribution of the others' play up to time period t -1. As all service providers align their predictions about energy productions on the value max{X e } and as the profit of s i does not depend on the energy needs of other microgrids than M i , the learning strategy can be determined as solution of the optimization problem:

f i (ν s i , t) = arg max y∈Xs 1 t -1 t-1 l=1 π i (l)| fi(ν s i ,l)=y (6)
As in Subsection IV-A, we give in the proposition below the analytical expression of provider s i 's loss.

Proposition 3: Under the assumption that provider s i 's forecasting strategy about microgrid M i energy needs is based on fictitious play, his loss at time period t is:

l i f (t), ν(t) = ν s i (t) + γ i 2 2 - γ i 2 + 1 4 (γ i 1 t -1 t-1 l=1 ν s i (l)) ν s i (t) + γ i 2 - 1 4 (γ i + 1 t -1 t-1 l=1 ν s i (l))
Proof of Proposition 3. Going back to Equation ( 6) defining the updating rule under fictitious play, we express the objective function as a function of y:

1 t-1 t-1 l=1 π i (l)| fi(ν s i ,l)=y = -( y+γi 2 ) 2 - L(i) γi n-1 δ K max{X e } + γi 2 (y + γ i ) + γ i K max{Xe}L(i) j=1,...,n L(j) + ( y+γi 2 -γ i ) 1 t-1 t-1 l=1 ν s i (l).
It is then maximized if, and only if,

y = 1 2 γ i + 1 t-1 t-1 l=1 ν s i (l)
. By substitution in provider s i 's utility as defined in Equation ( 5), we obtain provider s i 's loss at time period t:

l i f (t), ν(t) = γ i 2 + 1 4 (γ i + 1 t -1 t-1 l=1 ν s i (l)) 2 - γ i 2 + 1 4 (γ i + 1 t -1 t-1 l=1 ν s i (l)) ν s i (t) -γ i γ i 2 + 1 4 (γ i + 1 t -1 t-1 l=1 ν s i (l))
After simplifications and factorizations, we obtain the stated formula:

l i f (t), ν(t) = ν s i (t)+γi 2 2 -γi 2 + 1 4 (γ i 1 t-1 t-1 l=1 ν s i (l)) ν s i (t) + γ i 2 - 1 4 (γ i + 1 t -1 t-1 l=1 ν s i (l)) .

V. RENEWABLE ENERGIES INTEGRATION IN THE GRID: A DISTRIBUTED LEARNING GAME

Compared with Section IV and the literature [START_REF] Cadre | Collaborative Learning is Better, working paper of the Alternative Energy and Nuclear Power Commission[END_REF], [START_REF] Marden | Achieving Pareto Optimality Through Distributed Learning[END_REF], in this section, the energy productions cannot be controlled anymore since it comes from renewable sources exclusively. Service providers optimize their prices and booking quantities at each time period, having no information about the productions and the energy needs of the microgrid at this instant. As a result, the game can be considered as having partial information [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF]. Its study requires the introduction of performance measures captured here by loss functions, enabling the agents to evaluate the accuracy of their predictions.

We recall the definition of provider s i 's loss which has already been introduced in Subsections IV-A and IV-B:

l i f (t), ν(t) = π 0 i (t) -π i (t)
where π 0 i (t) corresponds to provider s i 's utility evaluated in f i (ν s i , t) = ν s i (t) and f i (ν e k , t) = ν e k (t), ∀k = 1, ..., K. It means that π 0 i (t) contains the utility that provider s i would have received if his forecasts were perfectly aligned with microgrid M i instantaneous needs and with the production of each energy producer.

Having no a priori information about the dynamic evolution of the produced renewable energies and about the energy needs of the microgrids, we assume that everything happens as if the system were in the worst case: Nature and consumers allie together to form a meta-player who is supposed to be the most unfavorable to the service providers. It means that the meta-player tries to maximize the sum of the providers' losses. His loss can be expressed as the opposite of the sum of all the providers' losses. Therefore, it takes the form:

l f (t), ν(t) = i=1,...,n π i (t) -π 0 i (t)
The agents' external regret over the sequence of time periods 1, ..., T , is expressed as the realized difference between the cumulative loss and the loss of the best prediction i.e., pure strategy (in the sense that this prediction minimizes their cumulative loss).

To be more precise, for service provider s i , it coincides with the difference between s i 's truly observed cumulative loss and the cumulative loss that would be obtained in case where s i made the best constant prediction over time interval [1; T ]. It takes the form:

R i (T ) = T t=1 l i f (t), ν(t) -min y∈Xs×X K e T t=1 l i f -i (y, t), ν(t)
Finally, for the meta-player, the regret coincides with the difference between his cumulative loss and the loss of the constant predictions over [1; T ] about the unknown sequences minimizing his cumulative loss or equivalently maximizing the sum of the providers' losses over the interval. We have:

R(T ) = T t=1 l f (t), ν(t) -min z∈X n s ×X K e T t=1 l f (t), z
The service providers and the meta-player try to determine randomized strategies such that asymptotically their external regrets remain in o(T ) where T is the number of time periods which have been played. It means that with probability 1:

lim sup T →+∞ 1 T T t=1 R i (t) = 0
for provider s i , ∀i = 1, ..., n and lim sup

T →+∞ 1 T T t=1 R(t) = 0
for the meta-player. Forecasters satisfying these inequalities are said Hannan consistent [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF].

In the following lemma, we prove that it is possible to construct learning strategies for the service providers which minimize their external regret asymptotically.

Lemma 4: A Hannan consistent learning strategy exists for each service provider s i .

Proof of Lemma 4. In our case setting, at the end of each time period, service provider s i knows the energy quantity bought by his customers M i and he can infer ν s i (t) from that quantity. s i also knows the energy which has been delivered by each energy producer e k to him. He can infer from that the energy which could have been delivered to him, if he had ordered a different quantity q ik (t), all other providers ordering the same energy quantities. As a result, s i can calculate his loss for all his possible actions. In [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF], it is proved that a Hannan consistent learning strategy always exists when the player can calculate his loss for each possible action at the end of each time period.

The repetition of the Stackelberg game introduced in Subsection II-A in a context of partial information can be rewritten by introducing randomization in the strategies. We denote by d t (f i ) : X s × X K e → [0; 1] and d t (ν) : X n s × X K e → [0; 1] the randomized strategies for service provider s i and for the meta-player respectively at time period t. We then have to cope with a repeated learning game. At each time period t, the repeated game timing introduced in Subsection II-A is updated according to the following rules to incorporate the forecasting tasks of the providers:

(1) All the service providers s i , i = 1, ..., n make their forecasts f i (ν s i , t), f i (ν e k , t), ∀k = 1, ..., K following distributions d t (f i ) respectively.

(2) Energy producers reveal their energy prices.

(3) Service producers reveal their energy orders q ik (t) and their service prices at the same time.

(4) The meta-player chooses ν s i (t) and ν e k (t), ∀i = 1, ..., n and ∀k = 1, ..., K following the distribution d t (ν).

(5) Each service provider s i obtains his profit π i (t), the demand of M i and the energy quantities offered by each service producer e k . Service providers update their forecasting strategies d t (f i ) and the meta-player updates his forecasting strategy d t (ν) depending on the value of the expected utilities. The step corresponding to the generation of unexpected random events resulting in microgrid energy needs and production variations is now controlled by the meta-player whereas the penalty rules introduced in Subsection II-A remain unchanged.

A. Regret based learning

We consider two types of updates for the forecasting randomized strategies d t (X) at each time period based on the exponential forecaster for signed games: one based on the external regret and the other based on the internal regret [START_REF] Cesa-Bianchi | Prediction, Learning, And Games[END_REF]. We will use the generic notation X to refer either to X e or to X s . For a given forecast X, we derive the payoffs H X (x, t) for each value x ∈ X of the forecast at each time period t by going back to the utilities of the agents and by keeping only the terms depending on forecast X. We assume that this is a signed game because the range of values of payoff function H X (.) might include a neighborhood of 0. We let:

V t = t s=1 V ar H X (X s , s)) = t s=1 E H X (X s , s)) -E[H X (X s , s)]
2 be the sum of the variances associated with the random variable H X (X t , t) which is the payoff for forecaster X at time period t assuming that the forecast at time period t has been set to X t , under the mixed strategy X which is defined over space X . Using the exponential forecaster for signed games with external regret means that the randomized strategy is updated according to the algorithm described below.

External Regret Learning Algorithm

Initialization. For t = 0, we set:

w 0 (x) = 1 |X | , ∀x ∈ X .
Step 1 to T . The updating rules are the following:

d t+1 (x) = w t+1 (x) x∈X w t+1 (x)
, ∀x ∈ X

w t+1 (x) = exp η t+1 t s=1 H X (x, s) = d t (x) η t+1 η t exp η t+1 H X (x, t) , ∀x ∈ X η t+1 = min 1 2 max{|H X (.)|} ; 2( √ 2 -1) e -2 ln|X | V t V t = V t-1 + V ar H X (X t , t)
For the internal regret, it is similar but with d t (.) =

i =j d i→j t (.)∆ (i,j) (t) where d i→j t (.
) is the modified forecasting strategy obtained when the forecaster predicts j each time he would have predicted i and

∆ (i,j) (t) = ω (i,j) (t) k =l ω (k,l) (t) with: ω (i,j) (t) = exp η t t-1 s=1 x∈X d s (x)H X (x, s) .
We see that we need to compute the maximum of the absolute value of the payoff function |H X (.)| for all forecasts X to run a simulation of the game. This maximum is reached for x = min{X } or x = max{X } for all payoff functions except for H fi(ν s i ) (.) because their differentiate with respect to x is never equal to 0. For H fi(ν s i ) (.), the differentiate equals 0 if, and only if, f i (ν s i , t) = ν s i (t), so the maximum of |H X (.)| is reached either for x = min{X } or x = max{X } or x = ν s i (t).

B. Collaborative learning is better

In this subsection, we want to know how distributed learning by service providers introducing (in)voluntary biases in their predictions, affects the smart grid global performance. Agents will most probably exchange information concerning their forecasts. Some agents might appear as more credible than others and coalitions might emerge. Collaboration will then take place within coalitions. In cooperative game theory literature, a coalition is a group of agents who have incentives to collaborate by sharing resource access, information, etc., in the hope to increase their revenue, knowledge, social welfare (in case of altruism), etc., compared to the case where they behave non-cooperatively [START_REF] Myerson | Game Theory: An Analysis of Conflict[END_REF], [START_REF] Shapley | Stochastic games, in proc[END_REF]. Adapted to our hierarchical learning context, we define coalitions of agents as follows:

We prove in [START_REF] Cadre | Collaborative Learning is Better, working paper of the Alternative Energy and Nuclear Power Commission[END_REF] that under external regret minimization, the smallest upper-bound on the agents' average loss over time interval [1; T ] is reached when the service providers integrate a grand coalition. As a result, this economic organization will remain stable provided the agents have incentives to consider the optimization of the whole system performance.

The objective of the next part of this subsection is to test on a toy network made of 2 producers and 3 providers that collaborative learning through a grand coalition provides better guarantees on the smart grid global performance than full competition.

For our numerical illustration, we have chosen n = 3 and K = 2. We have also used γ 1 = γ 2 = γ 3 = 0.9 and γ1 = 0.5, γ2 = 0.4, γ3 = 0.6 and X e = [1; 2] for the producers, X s = [5; 8] for the providers which ensure that we are always in energy shortage (cf. Case 2 described in Subsection B.2 of Proposition 1 proof) i.e., that penalties are imposed to the providers.

In the following pictures, we compare the cumulative regret of each agent to the cumulative regret of the same agent who would have forecasted the best value at each time period in terms of payoffs. More precisely, we display:

1 t t s=1 X∈F H X (X s , s) -max x (H X (x, s))
where F is the generic set of forecasts made by the service provider or the meta-player or the considered coalition.

We start by comparing the cumulative internal and external regrets in the case of full competition between service providers in Figures 2(a The service providers are in black for s 1 , green for s 2 and red for s 3 . We can see that in all cases, the difference between regrets converge toward 0 which means that the cumulative payoff obtained at the end of the game following the exponential forecaster strategy is close to the best possible cumulative payoff. This is in coherence with the theoretical result for the internal regret but is better than what we could expect for the external regret which means that we are in a game setting which performs well for regret based learning. We also remark that the algorithm converges faster for the external regret compared to the internal regret.

We compare these graphs with the graphs obtained when service providers integrate a grand coalition in Figures 3(a Again, we observe that the differences between the best achievable regrets and those obtained converge toward 0. The rate of convergence under cooperative learning seems higher than in the non-cooperative case. In addition, we observe that after 400 time periods the sum of differences between regrets under collaborative learning is close to -0.2 whereas the sum of differences between regrets is close to -0.26 in the full competition case. This is in coherence with the theory which says that collaborative learning is better.

VI. CONCLUSION

In this article, we focus on the identification of distributed learning algorithms enabling the agents to forecast hidden individual sequences in a decentralized hierarchical network which typical illustration is the smart grid. The upper-level agents are called the producers. They provide energy to the lower-level agents. The lower-level agents are called the providers. They provide energy access to the end users. The problem at hand is quite different depending on whether the produced energy is renewable or not. In case where it is non-renewable, the producers control their productions so as to maximize their utility. The providers can also adapt their prices, so as to force the end users to consume as much as they want. However, we prove that their utility is maximized if, and only if, their prediction coincides with the true value of the end users' energy needs which is not observed at the beginning of the time period. As a result, providers need to perform learning to optimize their utility. The performance of two well-known learning algorithms (tit for tat and fictitious play) are derived analytically. When renewable energies are introduced in the smart grid, the energy productions become highly uncertain adding more forecasts to perform. This requires to develop more sophisticated learning algorithms. We propose an online learning algorithm based on regret minimization and analyze its performance. Furthermore, we show through simulation that collaborative learning generates higher performance for the whole smart grid than full competition.

A possible extension of the work initiated in this paper might be to determine which economic organizations remain stable in case of unexpected attacks i.e., to design a resilient system.

APPENDIX

Proof of Proposition 1

The game setting described in Subsection II-A implies that in the relationship producers-providers, producers appear as leaders whereas providers are followers. Identically, in the relationship providers-consumers, providers appear as leaders whereas consumers are mere followers. Under such a setting, the game is called a Stackelberg game and as usual, it should be solved using backward induction [START_REF] Myerson | Game Theory: An Analysis of Conflict[END_REF].

We make the assumption that each energy producer receives at least one energy order from a service provider guaranteeing that the Stackelberg game admits non trivial solutions.

A. Optimization of the end users' decision

To minimize their total cost of energy defined by Equation (1), end users M i have to choose a i (t) so that the differentiate of the total cost of energy equals 0 which means:

a i (t) = p i (t) (7)
We will assume that p i (t) < ν s i (t) to ensure that this value for a i (t) does not exceed the energy needs of microgrid M i . Then the optimal a i (t) is defined by Equation [START_REF] Li | Decoupling coupled constraints through utility design[END_REF].

B. Optimization of the service providers' decisions

To find his optimal price and energy orders, service provider s i has to replace a i (t) by its optimal value in π i (t) defined in Equation ( 2), and to differentiate the result in p i (t) and in q ik (t). This differentiation raises two cases.

B.1 Case 1: the energy production fulfills the energy demand of the end users

It is the case when:

ν s i (t) -p i (t) ≤ k=1,...,K α ki (t)ν e k (t) (8)
Then differentiating the service provider's utility in q ik (t) leads to:

∂π i (t) ∂q ik (t) = -pk (t)
which means that s i will try to minimize all his energy orders to maximize his utility. As a result, s i will tend to break the inequality defining Case 1 in Inequality (8) because α ki (t) will tend toward zero. As a result the optimal decision for s i will always fall in Case 2 described below or on the frontier between Case 1 and Case 2. The frontier between these two cases is defined by the equation:

ν s i (t) -p i (t) = k=1,...,K α ki (t)ν e k (t) (9)
B.2 Case 2: the energy production does not fulfill the energy demand of the end users It is the case when ν s i (t) -p i (t) ≥ k=1,...,K α ki (t)ν e k (t). Then differentiating s i 's utility gives us:

∂π i (t) ∂p i (t) = ν s i (t) + γ i -2p i (t) ∂π i (t) ∂q ik (t) = -pk (t) + γ i ν e k (t) ∂α ki (t) ∂q ik (t) (10)
By using the definition of α ki (t) given in Equation (3), we obtain:

∂α ki (t) ∂q ik (t) = γi C k (t) -γi q ik (t) C k (t) 2
where we have let: C k (t) = j=1,...,n γj q jk (t). Then going back to System of equations ( 10), we conclude that the differentiates equal 0 when:

p i (t) = ν s i (t) + γ i 2 (11) pk (t)C k (t) 2 = γ i ν e k (t) γi C k (t) -γi q ik (t) (12)
On one side, we obtain directly the price for which the differentiate of π i (t) equals 0 through Equation [START_REF] Nguyen | Weighted Proportional Allocation[END_REF]. On the other side, Equation ( 12) can be rewritten as follows:

γi q ik (t) = C k (t) - pk (t)C k (t) 2 ν e k (t)γ i γi (13)
If s i anticipates that the other service providers will make the same optimization program, replicating Equation ( 13) for the n service providers and summing them all, results in the following equality: [START_REF] Saad | Coalitional Game Theory for Communication Networks: A Tutorial[END_REF], we obtain the energy orders for which the differentiates of π i (t) equals 0:

C k (t) = nC k (t
q ik (t) = ν e k (t) pk (t) n -1 δ γi L(i) (14)
where we have introduced the notation L(i) = 1 -n-1 δγi γi to simplify future calculations.

Presently, we have to check that the price and energy orders for which the differentiates of π i (t) equal 0 satisfy the conditions of Case 2.

First, it is easy to check that the price is positive through Equation [START_REF] Nguyen | Weighted Proportional Allocation[END_REF]. However, the energy orders defined in Equation ( 14) are non-negative if, and only if, 1 ≥ n-1 δγi γi which is equivalent to:

γ i γi ≥ n -1 δ (15)
This inequality means that the penalties related to s i are close to the penalties related to the other service providers. Indeed, if all penalties are equal to γ, then δ = n γ 2 and Inequality ( 15) is true for all service providers. On the contrary, if all penalties are equal to γ except for s 1 which has a penalty of γ n-1 , then δ = (n-1)n γ 2 and Inequality [START_REF] Shapley | Stochastic games, in proc[END_REF] becomes n ≥ (n -1) 2 which is false as soon as n > 2.

Second, by replacing the energy orders defined by Equation [START_REF] Saad | Coalitional Game Theory for Cooperative Micro-Grid Distribution Networks[END_REF] in Equation ( 3), we obtain α ki (t) = L(i) j=1,...,n L(j) = L(i) meaning that the total energy delivered to the customers of s i is k=1,...,K α ki (t)ν e k (t) = L(i) k=1,...,K ν e k (t). As a result, the price and energy orders for which the differentiates of π i (t) equal 0 verify the inequality defining Case 2 if, and only if:

ν s i (t) ≥ γ i + 2L(i) k=1,...,K ν e k (t) (16)
This inequality states that the total production of energy by energy producers should not be too large compared to the energy needs of customers. If Inequalities ( 15) and ( 16) are true, the optimum for s i is reached for p i (t) defined by Equation ( 11) and q ik (t) defined by Equation [START_REF] Saad | Coalitional Game Theory for Cooperative Micro-Grid Distribution Networks[END_REF]. If one of these inequalities is not true, then the optimum for s i is reached on the frontier defined by Equation [START_REF] Marden | Achieving Pareto Optimality Through Distributed Learning[END_REF].

C. Optimization of the energy producers' decision

After substituting q ik (t) and C k (t) by the expressions found in the previous section in energy producer e k 's utility as defined in Equation (4), we obtain: The only part of this equation depending on pk (t) has always a negative impact on the profit of the energy producer under the assumption of fair penalties. Indeed, in that case, as raised in the previous section, we have: L(i) ≥ 0 for all service providers s i . As a result, to maximize his profit, the energy producer has to choose pk (t) such that the part depending on pk (t) in the above equation equals 0. It implies that the term 1 -pk (t) γiδ n-1 is inferior to 0 for all i = 1, ..., n. It is equivalent to: pk (t) ≥ n-1 δ γi . Consequently, the optimal price for the energy producer with fair penalties is defined by: pk (t) = n -1 δ min i=1,...,n { γi }

πk (t) = ν e k (t
In theory, the price could be higher than this value and it would change nothing for the utility of the energy producer. But the energy producer has an incentive to be moderate on his price to avoid competition from other energy producers.

Fig. 1 .

 1 Fig. 1. Economic relations between the agents in the grid.

  ) and 2(b).

Fig. 2 .

 2 Fig. 2. Difference between the best achievable cumulative regret and the one obtained with the internal regret minimization algorithm in (a) and with the external regret minimization algorithm in (b) under full competition.

Fig. 3 .

 3 Fig. 3. Difference between the best achievable cumulative regret and the one obtained with the internal regret minimization algorithm in (a) and with the external regret minimization algorithm in (b) for the grand coalition of service providers.

  Then as C k (t) is not zero because each producer e k receives at least one order of energy, by dividing the previous equation by C k (t) and reordering we obtain: By replacing C k (t) in Equation

			) -	pk (t)C k (t) 2 ν e k (t)	j=1,...,n	1 γ j γj
	by definition of C k (t).
		C k (t) =	ν e k (t) pk (t)	n -1 δ
	where δ =	j=1,...,n	1 γj γj .

  )

		n -1 δ	i=1,...,n	L(i) γi	-	i=1,...,n	L(i) pk (t)
	(1 -	pk (t) γi δ n -1	) +

• A coalition of agents is a group of agents who share their information and align their predictions to a common value.• Agents who belong to the same coalition are said to collaborate.