Nicolas Gast

Dan-Cristian Tomozei

Jean-Yves Le Boudec

Optimal Generation and Storage Scheduling in the Presence of Renewable Forecast Uncertainties

Renewable energy sources, such as wind, are characterized by non-dispatchability, high volatility, and non-perfect forecasts. These undesirable features can lead to energy loss and/or can necessitate a large reserve in the form of fast-ramping fuel-based generators. Energy storage can be used to mitigate these effects. In this paper, we are interested in the tradeoff between the use of the reserves and the energy loss. Energy loss includes energy that is either wasted, due to the inefficiency of the storage cycle and the inevitable forecasting errors, or lost when the storage capacity is insufficient. We base our analysis on an initial model proposed by Bejan, Gibbens, and Kelly. We first provide theoretical bounds on the trade-off between energy loss and the use of reserves. For a large storage capacity, we show that this bound is tight, and we develop an algorithm that computes the optimal schedule. Second, we develop a scheduling strategy that is efficient for small or moderate storage. We evaluate these policies on real data from the UK grid and show that they outperform existing heuristics. In addition, we provide guidelines for computing the optimal storage characteristics and the reserve size for a given penetration of wind in the energy mix.

I. INTRODUCTION

R ENEWABLE energy sources, such as wind and solar, are highly volatile and difficult to predict (current forecast techniques for wind power 12 hours in advance have normalized mean absolute errors to the order of 20% [START_REF] Costa | A review on the young history of the wind power short-term prediction[END_REF]). When renewables fall short of providing the required power, a large reserve needs to be available in order to avoid blackouts. From a social planner's perspective, it is shown in [START_REF] Holttinen | Impacts of large amounts of wind power on design and operation of power systems, results of iea collaboration[END_REF]- [START_REF] Ulbig | On operational flexibility in power systems[END_REF] that the undesired effects of the volatility of renewables can be mitigated via the use of energy storage, with a manageable increase in energy costs. Another approach for compensating forecast uncertainties is to increase reserves. Algorithms for computing the optimal reserves needed to insure reliability in the presence of forecast errors are developed in [START_REF] Doherty | A new approach to quantify reserve demand in systems with significant installed wind capacity[END_REF]- [START_REF] Warrington | Robust reserve operation in power systems using affine policies[END_REF]. They update reserve capacities as new forecasts become available.

The economic aspects have also been analyzed. Fabbri et al. show that the cost associated with prediction errors can be up to 10% of the total generation costs [START_REF] Fabbri | Assessment of the cost associated with wind generation prediction errors in a liberalized electricity market[END_REF]. Hence, several authors investigate profit maximization for wind producers. Constantinescu et al. study the optimal scheduling of thermal generators with uncertain wind forecasts [START_REF] Constantinescu | A computational framework for uncertainty quantification and stochastic optimization in unit commitment with wind power generation[END_REF]. They use a stochastic optimization approach to minimize fuel generation costs. Storage can be used to deal with forecast uncertainties and therefore maximize revenue. The authors of [START_REF] Brekken | Optimal energy storage sizing and control for wind power applications[END_REF]- [START_REF] Korpaas | Operation and sizing of energy storage for wind power plants in a market system[END_REF] consider the day-ahead market with time-varying prices and study the sizing and operation of an electrical storage system owned by a wind-producer. Wind producers can also reduce penalties due to deviations from forecasts by aggregating their production to exploit the spatial smoothing of errors. Incentives and optimal redistribution strategies to encourage this behavior are studied in [START_REF] Bitar | Optimal sharing of quantity risk for a coalition of wind power producers facing nodal prices[END_REF].

Storage management can also be done by an independent storage operator via price arbitrage. When the actors on the market are price-takers (i.e., there is a large number of actors), it is shown in [START_REF] Chatzivasileiadis | Incentives for optimal integration of fluctuating power generation[END_REF]- [START_REF] Sioshansi | Welfare impacts of electricity storage and the implications of ownership structure[END_REF] that decoupling generation control and storage management is socially optimal. However, in the case where the price-taking hypothesis does not hold (small number of actors), the authors of [START_REF] Sioshansi | Welfare impacts of electricity storage and the implications of ownership structure[END_REF], [START_REF] He | Coupling electricity storage with electricity markets: a welfare analysis in the french market[END_REF] show that storage can be overused or underused if it is owned by independent users or by consumers. The question of the viability of independent storage operation is raised in [START_REF] Walawalkar | Economics of electric energy storage for energy arbitrage and regulation in new york[END_REF]- [START_REF] Tuohy | Impact of pumped storage on power systems with increasing wind penetration[END_REF]. Although installing more storage reduces the negative effect of variability, storage owners might have an incentive to undersize their storage system [START_REF] Gast | Impact of storage on the efficiency and prices in real-time electricity markets[END_REF]. Moreover, installing solar panels threatens the revenues of pumped-storage hydroplant operators by generating energy during the noon peak [START_REF] Hildmann | Electricity grid in-feed from renewable sources: A risk for pumped-storage hydro plants?[END_REF].

In this paper we are interested in the global impact of the volatility of renewables and how it can be mitigated by an optimal use of storage. Optimality is defined by adopting the viewpoint of a social planner. We follow the approach of Bejan et al. [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF] and address two performance metrics: (1) the energy loss and (2) the actual use of reserves. The energy loss accounts for the inefficiency of the storage cycle, as well as renewable energy that has to be curtailed. The actual use of reserves is considered as a social performance metric as it often consists of fast-ramping fuel-based generation. Our focus is on wind-energy sources, but a similar analysis can be conducted for other types of renewables. We can think of our system model as a national or regional transmission operator, equipped with a storage system (such as pumphydro) and a large set of wind sources. The operator schedules a certain amount of production one day ahead, and, according to updated forecasts of wind and demand, updates the value of this scheduled production before the actual consumption (of the order of several hours before). In real time, the mismatch between scheduled production, wind production, and demand is compensated using the storage system and the secondary reserve provided by last-minute fast-ramping generators.

The authors of [START_REF] Doherty | A new approach to quantify reserve demand in systems with significant installed wind capacity[END_REF]- [START_REF] Warrington | Robust reserve operation in power systems using affine policies[END_REF] consider reserve dimensioning in terms of power. Our approach is complementary: in our analysis, we consider that there is always enough reserve power available and evaluate its actual use. Our results can be used to find optimal scheduling policies. In particular, they show that, when the storage capacity is large enough, it is optimal to use a deterministic policy that schedules a certain fixed surplus of generation, that we are able to compute numerically. If a larger surplus is scheduled, a dramatic increase in energy loss occurs, whereas a smaller scheduled surplus increases the use of reserves without significantly reducing energy loss. Thus, although our approach does not explicitly consider market aspects, it can be used by a social planner to determine various market parameters, such as the required secondary reserve.

Bejan et al. [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF] propose a production scheduling policy that aims to maintain the storage system at a constant level (e.g., half the storage capacity). This policy can be regarded as a flavor of model predictive control (MPC): in order to make a scheduling decision, it uses the model of the storage to predict its future level, along with updated wind forecast data and past control decisions. It is a quasi-deterministic policy, as forecast errors are implicitly reduced by using the present storage level as a starting point for predicting the future one. The intuition behind this scheduling policy is that a balanced storage system can better cope with mismatches. We question this intuition in our analysis. Like [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF], we do not consider network constraints. We discuss the implications of this simplification in Section VI.

Contributions: Under the statistical assumption that the wind forecasts cannot be improved, we show a fundamental bound on the best performance of any production scheduling policy. This bound is determined by the distribution of forecast errors and by the storage system parameters. We show that the quasi-deterministic policy of [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF] does not reach this bound. We exhibit a simple deterministic policy ("fixed offset", FO) that achieves this bound when the storage capacity is large. We demonstrate the existence of an optimal operation point, and we develop an algorithm that uses the distribution of forecast errors to compute this point.

For medium and small storage capacity, we use the statistical properties of the wind-forecast errors to build a heuristic production scheduling policy (called "dynamic offset", DO), obtained via stochastic dynamic programming. We perform numerical evaluations on real measures of aggregated demand and wind production, measured in the UK over a period of almost three years. We find that, for various parameters of the storage system, the policy that maintains the storage in a balanced state is suboptimal and is outperformed by DO. In addition, we provide guidelines for computing optimal storage characteristics and the size of the reserve for a given penetration of wind in the energy mix.

A preliminary version of the ideas in this paper can be found in the extended abstract of our talk at the Greenmetrics Workshop [START_REF] Gast | Optimal storage policies with wind forecast uncertainties[END_REF].

Outline: We begin by describing our storage model and the dataset that we use in Section II. We provide a lower bound on the performance and we show that the fixed offset policy is optimal for large storage capacity in Section III. We study scheduling policies for small and medium storage capacity in Section IV. We introduce the dynamic offset policy and show that it outperforms the other considered heuristics in all scenarios. In Section V, we provide heuristics for computing the optimal storage characteristics and the size of the reserve using the statistics of the forecast errors. Finally, we discuss our results and conclude in Section VI.

II. SYSTEM MODEL

A. Storage Model

We consider a slotted time model similar to [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF]. We assume that at each time step t we observe a certain power demand D(t) that needs to be satisfied during time period t. We use both non-dispatchable and dispatchable energy sources to satisfy the demand. Non-dispatchable energy sources provide an imposed power at each time; a fraction of this power can be discarded. Dispatchable energy sources can be modulated at the beginning of the time slot to exactly match the demand. Specifically, we rely on 1) scheduled base load power production P f t-n (t), computed n steps ahead (i.e., at time t -n), 2) non-dispatchable wind power W (t), 3) energy storage system (e.g., pumped-storage hydro), and 4) fast-ramping generation G(t) (secondary reserve). The demand is always satisfied by using the above energy sources. However, we might be confronted with energy losses if the aggregate scheduled power production and available wind power are larger than the demand.

In this paper, we analyze various power scheduling policies for computing P f t (t+n) at time t, given the predictions of future wind power. Due to inaccurate predictions, the demand D(t) might not match the scheduled and non-dispatchable generation P f t-n (t)+W (t). We denote the mismatch, i.e., the additional power required to satisfy the demand, by Note that M (t) can take negative values in the case of overproduction, in which case we want to store as much of the surplus power as possible. We also want to use the storage system to compensate a positive mismatch. We consider that the charging process of the storage has an efficiency η 1 and the discharging process an efficiency η 2 . Thus, the storage system has a cycle efficiency η = η 1 η 2 : only a fraction η of the injected energy can be restored. The factor η accounts for the losses due to charging or discharging, such as losses in transformers or water turbines. The energy capacity, B max , is the quantity of energy that can be retrieved from a fully charged system: the storage can store up to B max /η 2 units of energy but can only produce B max unit of energy. We denote by B(t) ∈ [0, B max ] the quantity of energy stored at the beginning of time slot t divided by η 2 . B(t) represents the net amount of energy that can be extracted and is referred to as the storage level. Due to power constraints, no more than C max power can be injected in the storage system during a single time-slot and no more than D max can be generated. We neglect the ramping constraints of the storage system, as they are usually much larger than the ones of conventional generators.

M (t) := D(t) -W (t) -P f t-n (t). (1)
The storage is used to compensate the mismatch |M (t)|. Taking into account the constraints described above, we describe the evolution of the storage level by a function 1 of the current storage level and mismatch:

B(t + 1) = φ(B(t), M (t)), (2)
φ(B, M ) = (B -min(M + , D max )) + if M ≥ 0, min(B + η min(M -, C max ), B max ) if M < 0.

B. Cost Model and Performance Metrics

If M (t) ≥ 0, then the scheduled power is insufficient. We compensate by using the storage (2) and, only if necessary, the reserve for the remaining unmatched demand:

G(t) = M + (t) -(B(t + 1) -B(t)) -. (3)
In this case, the energy loss L(t) during time slot t equals 0.

If M (t) < 0, then the scheduled production exceeds current demand, and we store the surplus. There is no use of reserves, hence G(t) = 0. The total energy loss L(t) equals

L(t) = M -(t) -(B(t + 1) -B(t)) + . ( 4
)
1 Throughout the paper, we use the standard notations: (a) + = max(a, 0) and (a) -= max(-a, 0).

Note that as opposed to [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF], the energy loss is composed of both the energy that cannot be stored and the losses due to inefficiency of the storage.

Our cost model assumes that the wind energy is free (wind turbines are already in place), that one unit of energy scheduled in advance costs c P and that one unit of energy produced by reserve generators costs c G > c P . As we ignore market aspects, these costs do not vary with time. Over a long timehorizon, the total energy produced is equal to the demand plus the losses: P + W + G = D + L. Therefore, the total cost for the operator is equal to

c P P + c G G = c P (D -W ) + c P L + c G -c P c P G . ( 5
)
Note that L = W -D + G + P . Thus, even if the wind production exceeds the demand, the first term of this equation D -W will be negative but the total cost remains positive.

The demand or the wind cannot be controlled. Hence, to minimize the costs, the operator must minimize a weighted sum of the energy loss and the reserves used. We do not focus on a particular value of (c G -c P )/c P in this paper. We consider the multi-objective problem of finding a policy π that minimizes both the losses, Lπ (T ), and the actual use of reserves, Ḡπ (T ), over time-horizon T . We define

Ḡπ (T ) := T t=1 G(t) T t=1 W (t) ; Lπ (T ) := T t=1 L(t) T t=1 W (t) . (6)

C. Scheduling Policies and Forecast

At each time t, we assume that we are given a forecast {W f t (t+i)} i=1...n for the wind production at times t+1 to t+n. We follow [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF] and assume that the demand is completely predictable, and that the demand always exceeds the wind production. Hence, mismatches are caused only by wind forecast errors. Our methodology does not rely on a particular forecast method and we do not claim to present a new forecast methodology. Of course, better forecasts will lead to better performance. Hence, our goal is to answer the question: Given a particular forecast, what performance can we achieve and how?

The operator uses the forecasted values of wind production to schedule the power production P . A first approach is to schedule a production at time t equal to the difference in demand and forecast wind production. A specific scheduling policy defines a method of computing an offset u f t (t+n) in the scheduled power. Specifically, the scheduled power production P f t (t + n) at time t + n takes the following value:

P f t (t + n) := (D t (t + n) -W f t (t + n) + u f t (t + n)) + . (7)
A negative value of u f essentially entails dispatching generation at time t + n from the storage or, in the worst, case from the fast ramping generation. A positive value of u f means that we plan to store energy: we increase the chance of losing energy, but we reduce the use of reserves.

D. Numerical Data Set

To evaluate numerically the performance of the policies, we use data obtained from the BMRA data archive, available at elexonportal.co.uk. This archive is composed of daily reports that contain, among other things, values of aggregated electricity production and consumption in the UK, and weather forecast data. These values are averaged over 30min intervals. Hence, in the simulation, we use a time-step of 30min.

We consider a demand D(t) equal to the aggregated demand and use wind production and day-ahead wind production forecast in the time interval from June 2009 to April 2012. In the considered time frame, the maximum capacity for wind-power generation increased due to the deployment of additional wind farms. In our analysis we normalize the values of production to maintain a constant wind capacity. Hence we use normalized values:

W (t) :=
production at time t total wind capacity at time t × load factor .

The load factor is the ratio between the average power to the peak power. In our data, this factor is around 28%, which is typical for a good site with modern turbines [START_REF] Mackay | Sustainable Energy-without the hot air[END_REF]Chapter 4]. Using this normalization, all units will be expressed in average wind power (AWP). 1 AWP is equal to the average over time of W (t). Similarly, the unit AWPh corresponds to the average wind energy generated during 1h.

According to the DECC calculator [START_REF]UK DECC pathway calculator[END_REF], UK produced 16TWh of wind energy in 2010. This means that currently in the UK, one AWP corresponds 2GW. Depending on the scenario, these values should grow to 10GW to 20GW in 2020, 30GW to 30GW in 2035 and 30GW to 120GW in 2050 [START_REF]UK DECC pathway calculator[END_REF]. As a comparison, the most powerful pumped-storage hydro power station is currently the Bath County Pumped Storage Station. It has a power capacity of 3GW, an energy capacity of 30GWh and an cycle-efficiency of about η = 0.77 [28]. In the UK, the most powerful station is the Dinorwig Power Station. It has a power capacity of 1.7GW, an energy capacity of 10GWh and an cycle-efficiency of η = 0.75 [29]. This power-plant corresponds to 0.85 AWP and 5 AWPh for today's UK power production or 0.085 AWP to 0.17 AWP and 0.5 AWPh to 1 AWPh for the 2020 scenario. The maximum charging and discharging power is similar for both powerplants. In the numerical evaluation, we will use two values of efficiency: η=0.8, which is close to today's value for pumpedstorage, and η=1, which represents an idealistic scenario.

We use three forecast methods in our numerical analysis: 1) W PF : persistence forecast: The first method is to use the average value of wind power during the previous hour to predict any value in the future:

W PF t (t + i) := W (t).
This forecast is the one used by Bejan et al. [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF]. It is widely studied in the literature [START_REF] Hodge | Wind power forecasting error distributions over multiple timescales[END_REF], [START_REF] Bludszuweit | Statistical analysis of wind power forecast error[END_REF] and performs well on short timescales (see [START_REF] Costa | A review on the young history of the wind power short-term prediction[END_REF] and Figure 3).

2) W WP : numerical weather prediction: The second method is to use the forecast data available in our data set. This data set contains the forecasts of wind-power production, made available each day at 3p.m. for a 24h interval starting at 9p.m. the same day. Thus, the forecast Ŵ (t) was available between 6h and 30h in advance. To remove seasonality, we subtract the average forecast error over the previous week and we define

W WP t (t+i) := Ŵ (t+i) - 1 7days t-7days<s≤t ( Ŵ (s)-W (s))
These values are well defined for i ≤ 30h.

3) W LC : weather prediction with a linear correction: This forecast method is a combination of the two preceding ones. It exploits the fact that weather prediction errors are positively correlated. The forecast for time t+i is obtained by subtracting a fraction α i of the current weather forecast error:

W LC t (t + i) = W WP t (t + i) -α i (W WP t-i (t) -W (t)). (9)
The coefficient α i depends on the time horizon i. It is chosen in order to minimize the mean absolute error, defined in Equation [START_REF] Warrington | Robust reserve operation in power systems using affine policies[END_REF]. Its value is computed using data from the 6 months preceding the considered evaluation interval.

Accuracy of the forecasts: We plot a typical sample of both the wind production and the forecasts W WP and W LC in Figure 2. The forecast W LC is often better than W WP , but sometimes it over-corrects (e.g., on March, 21st). We measure the accuracy of a forecast as the normalized mean absolute error:

t∈3 years W f (t+i) -W (t+i) t∈3 years W (t). (10)
The mean absolute errors of the three forecasts are reported in Figure 3. As expected [START_REF] Costa | A review on the young history of the wind power short-term prediction[END_REF], the persistence forecast outperforms the weather prediction for short time-horizon (i ≤ 6h). W LC is always the best forecast. The performance of W WP does not depend on the time horizon considered because it uses forecasts from the day-ahead. We also evaluated more complicated statistical corrections (non-linear or with a larger time-horizon) than W LC , but they were not significantly better.

The parameters values used in the simulation are summarized in Table I. Fig. 3. Mean absolute error of the three wind forecasts, W PF (persistence forecast), W WP (day-ahead weather forecast) and W LC (weather forecast with linear correction) as a function of the horizon of the prediction i.

III. OPTIMALITY OF THE FIXED OFFSET POLICY FOR LARGE STORAGE CAPACITY

At time t, the fixed offset policy FO(u) schedules a production at time t+n equals to the forecasted mismatch between demand and wind power plus a constant power u:

P FO t (t + n) := D(t + n) -W f t (t + n) + u. (11)
A higher offset u results in higher losses but a lower use of reserves. As we will see next, this policy is optimal for large storage capacity.

A. A Lower Bound on the Energy Cost

The quantity P f t (t+n) of energy production scheduled for time t+n is set at time t, with the information 2 available at time t. A scheduling policy π defines a method of computing the additional scheduled power u f t (t + n) based on all the information available at time t. For such a scheduling policy π, we denote by Ḡπ (T ) and Lπ (T ) the average values of the use of reserves and energy loss over time horizon [1; T ].

Let e f t (t+n) = W (t+n)-W f t (t+n) denote the forecast error. The next theorem provides a bound on the performance of any scheduling policy, assuming that the prediction cannot be improved by using the knowledge up to time t and that errors are identically distributed. By this, we mean that there exists a random variable ε such that the forecast error e f t (t+n) is independent of the passed values of predictions or generation and e f t (t+n) is distributed as ε. Note that we do not assume e f t (t+n) to be independent of e f t (t+1) or e f t (t+n-1). For a fixed offset u, let (u) and g(u) be defined by

(u) := E (ε+u) + -f (u) (12) g(u) := E (ε+u) --f (u) ( 13
)
where

f is equal to f (u) = min(ηE [min ((ε+u) + , C max )] , E [min ((ε+u) -, D max )]).
Theorem 1 (Lower Bound on the Energy Cost): Let us assume that for all t, the forecast error e f t (t+n) is independent of F t and distributed as a random variable ε. Then, for any control policy π, there exists u such that 2 The information available at time t is denoted Ft. Ft is also called the filtration associated with the process. Ft represents the knowledge of wind production and prediction up to time t as well as production scheduled for time t to t+n-1 and prediction for time t to t+n. By Theorem 1, the performance of a policy cannot be in the gray zone without improving the forecast. By Theorem 2, the fixed offset policy performs close to optimally for large storage capacity: its performance is on the dashed curve.

Ḡπ (T ) ≥ g(u) - B max T and Lπ (T ) ≥ (u) - B max T . (14)
Moreover, the function g(u) → (u) is well defined, decreasing and convex.

Proof: The proof is given in Appendix A. When the time horizon T is large, the term B max /T becomes negligible. Thus, this theorem shows that the performance of any policy will be above the curve u → ( (u), g(u)).

Theorem 1 provides a lower bound on the energy cost. The next theorem shows that this bound is attained by the fixed offset policy when the storage capacity is large.

Let LFO(u) be the average lost energy when using the fixed offset policy FO(u): LFO(u) = lim sup T →∞ LFO(u) (T ) and ḠFO(u) = lim sup T →∞ ḠFO(u) (T ) the average use of reserves.

Theorem 2 (The fixed policy is optimal for large storage): For all δ > 0, there exists a storage capacity B 0 such that for all u, if B max ≥ B 0 , we have ḠFO(u) ≤ g(u) + δ, and LFO(u) ≤ (u) + δ (15)

Proof: The proof is given in Appendix B. This theorem, combined with Theorem 1, shows that when the storage capacity is large, the FO policies perform at least as well as any other policy. This fact is illustrated in Figure 4: the performance of the fixed offset policy is close to the lower bound. These policies are Pareto-optimal: the performance of any other policies must be above this curve.

B. Desirable Operating Point

All the points of the curve corresponding to the lower bound of Theorem 1 are Pareto-optimal points: for point on this curve and any storage capacity, there exists no policy that simultaneously uses less reserves and wastes less energy. Moreover, as shown in Figure 4, this curve exhibits a sharp knee: it is composed of two branches that intersect in a single point, that we denote the desirable operating point.

This point is desirable in the sense that for a large range of weight factors γ, it minimizes the weighted sum L + γG. Because of the particular shape of the curve, any policy that decreases the use of reserves by a few percents will at least double its energy loss. This indicates that any reasonable policy should operate close to this point. The value of this point depends on the power capacity and cycle-efficiency of the storage.

C. Optimal Fixed Offset

When the storage capacity is large, the fixed offset policy acheives the lower bound. FO can operate close to the desirable operating point when the offset u is such that on average, we charge ηE [min ((ε+u) + , C max )] as much as we discharge E [min ((ε+u) -, D max )]. This shows that the optimal fixed offset is largely independent of the cost ratio between energy produced using reserve generators and scheduled energy. Algorithm 1 uses this fact to provide an efficient way of computing a fixed offset u * that is optimal for most values of γ.

Algorithm 1 Computation of the optimal fixed offset

Require:

Samples of W f -W , C max , D max , η. Let ε t := W f t (t + n) -W (t + n) Use a binary search to find u such that: η t min((ε t +u) + , C max )= t min((ε t +u) -, D max ).
Return u.

IV. HEURISTICS FOR LOW AND MODERATE STORAGE

CAPACITIES

When the storage capacity is low, the fixed offset policy performs far from the lower bound as it does not take into account the level of the storage. In this section, we describe two scheduling policies (BGK and DO) that choose u f t (t+n) as a function of the estimate B f t (t+n) of the storage level at time t+n. This estimate is computed by using all the previously computed decisions P f t-n (t), . . . , P f t-1 (t+n-1) and wind forecasts available at time t: B f t (t + 1) := B(t + 1) and

B f t (t+i+1) := φ(B f t (t+i), D(t+i)-P f t+i-n (t+i)-W f t (t+i)).

A. The Bejan-Gibbens-Kelly Policy (BGK)

The Bejan-Gibbens-Kelly policy BGK(λ), introduced in [2], aims at maintaining a constant level of the storage B = λB max (typically, λ = 0.5). To compute P BGK t (t + n) at time t, this policy first forecasts the storage level at time t + n. Subsequently, u BGK t (t + n) is computed as the required energy to bring the storage level at time t + n + 1 closest to B under the operating constraints:

P BGK t (t + n) := D(t + n) -W f t (t + n) + f λ (B f t (t + n)), where f λ (B)=min( 1 η (λB max -B) + , C max ) -min((λB max -B) -, D max ).

B. The Dynamic Offset Policy (DO)

The dynamic offset policy chooses decision u DO t (t + n) as a deterministic precomputed function δ

γ : [0, B max ] → R of the forecast storage level B f t (t + n): P DO t (t+n) := D(t+n) -W f t (t+n) + δ γ (B f t (t+n)), (16)
The control law δ γ is derived from the optimal policy of a Markov decision process (MDP) that represents a simplified storage model. It takes into account the statistics of forecast errors made on the wind W f (t + n) and on the storage level B f t (t + n). In the remainder of the paper, we show that it performs at least as good as the two previous heuristics in all scenarios studied and outperforms them in most of them.

1) Description of the MDP: We consider a MDP, whose state is the storage level [0, B max ], and whose action space is R. Let ε be an i.i.d. sequence of variables on R, with the same distribution as the errors of the corrected forecast W (t+n)-W f t (t+n); and let ξ be an i.i.d. sequence of variables on R, with a similar distribution as the error made on the storage level i<n (W (t+i)-W f t (t+i)). If B(t) is the state at time t, and u(t) the offset chosen for the next time slot, the state at time t+1 becomes

B(t+1)=φ B(t) + ξ(t+1) Bmax 0 , -ε(t+1) -u(t) , (17)
The function φ represents the evolution of the storage in one time step and is defined by Equation ( 2). The notation (x) Bmax 0 denotes a truncation of x: (x) Bmax 0 = max(0, min(B max , x)). Given a storage level b := x + ξ and a mismatch m := -u -ε, we consider an instantaneous cost that is a weighted sum of the lost energy and the use of reserves:

c(b, m) =m -(1 -η) + m + η min B max -b η , C max - + γ (m -max(-b, -D max )) + (18)
The first line corresponds (for its first term) to the losses due to inefficiencies in the storage system, and (for its second term) to the losses due to ramp-up constraints or overflows. The second line corresponds to the use of reserves (derived via Equation ( 3)). The weight γ characterizes the trade-off and indexes the family of policies. We consider a controller that seeks to minimize the average cost over an infinite time horizon:

min u∈policy lim T →∞ 1 T E T t=1 c((B(t)+ξ) Bmax 0 , u(t)+ε) . (19)
The choice of u(t) can depend on the value of B(t), as well as all values of B(s) and u(s) until time s < t.

2) Numerical computation of the control law δ γ : We consider a discretized version of the MDP, by replacing the state space [0, B max ] by 1+(B max /h) values: {0, h, 2h, . . . , B max }. By [32, Theorem 8.1.2], there exists an optimal control law δ γ that only depends on B(t). Moreover, this MDP belongs to the class of communicating MDPs with average cost. This guarantees that the relative value iteration algorithm (Algorithm 2) converges to v (see [START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF]Chapter 9]). It provides an efficient way to numerically compute the control law δ γ .

+ V k (φ((b+ξ) Bmax 0 , u+ε)) V k+1 (b)← Vk+1 (b) -inf b Vk+1 (b) end for k ← k + 1. end while δ γ (b):=arg min u∈R E c((b+ξ) Bmax 0 , u+ε)+V k (φ(b+e, u+ε))
In our numerical evaluations, we apply Algorithm 2 with a precision threshold of 10 -7 . To accelerate the computation, we restrict the search to control laws that decrease in u. An illustration of the optimal control law δ γ as computed by Algorithm 2 is shown in Figure 5. We see that the control law δ γ is less aggressive than BGK and reacts more smoothly. The policy DO differs from the dynamic reserve (DR) policy described in our previous work [START_REF] Gast | Optimal storage policies with wind forecast uncertainties[END_REF] through Equation [START_REF] Bitar | Optimal sharing of quantity risk for a coalition of wind power producers facing nodal prices[END_REF]. This equation includes the term ξ(t+1), i.e., the error on the forecasted storage level. DR can be computed using Algorithm 2 by setting ξ(t + 1) = 0. Although we do not show the comparison, DO performs at least as well as DR in all our examples.

C. Performance for Various Storage Characteristics

To evaluate the performance, we simulate the fixed offset policy (FO), dynamic offset policy (DO), and the BGK policy. Figure 6 reports the results for a small storage capacity B max =3 AWPh and a large storage capacity B max =20 AWPh. Each time, we set C max =0.30 AWP and we simulate η=0.8 and η=1. We apply the BGK policy with the three wind forecasts W PF , W WP , and W LC . For the dynamic offset policy, we use the corrected forecast W LC and we vary its parameter γ from 0.01 to 100. We make three important observations. First, the plots show that, for all tested values of storage characteristics, the BGK policies, which try to maintain the storage at a fixed level, are outperformed by the dynamic offset policies with corrected forecast. Even when η = 1, the DO policy reduces both the energy loss and the use of reserves. This suggests that taking into account the statistical nature of the prediction error leads to performance gains higher than trying to maintain the storage in a balanced state. For these storage capacities, the fixed offset policy is not optimal.

Second, when the storage capacity is large (20 AWPh here), both the fixed offset policy and the dynamic offset achieve the lower bound. The BGK policy is not optimal for both η=0.8 and η=1 and loses more energy than the best fixed offset policy. In this case, the performance of BGK is best when run with W WP , but it is still away from the lower bound.

Finally, as we see in the different graphs, BGK can perform better either with W WP or W LC , depending on the storage size or the target storage level λ. For example, when n = 6h, B max = 3 AWPh and C max = D max = 0.30 AWP, high threshold favors BGK run with W LC , whereas low thresholds favor BGK run with W WP .

D. Consistency of the Dynamic Offset Policy

As shown in Figure 6, the performance of BGK does not necessarily improve as the forecast improves: BGK with W WP performs better than BGK with W LC that, in turn, performs better than BGK with W PF , although the relative error exhibits the opposite order for n ≤ 6h (see Figure 3). We attribute this performance mismatch to the fact that BGK performs better when the prediction does not depend on the time at which the prediction was issued. As the control law of BGK is sharper than the one of DO (see Figure 5), a time-varying prediction causes BGK to overreact to certain situations.

To verify this assumption, we construct two artificial scenarios A and B. For the two scenarios, the wind generation is equal to its real value W (t). We define the two forecasts W A , W B as follows. Let (L(t)) t be a sequence of i.i.d. Laplace random variables of mean 0. The forecasted wind production issued at time t for time t+i is

W A t (t+i) = W (t+i)+ i k=0 L(t+k) and W B t (t+i) = W (t+i)+ i k=i-n L(t+k). The prediction error of W A is i k=0 L(t + k),
which is smaller than the one corresponding to W B . For a given time s, the forecast W B t (s) does not depend on time t at which it has been issued, whereas the forecast W A t (s) does. Figure 7 reports the values of loss energy and fast ramping generation used for a capacity B max = 10 AWPh, C max = 0.5 AWP and two efficiencies: η=0.8 or η=1. We observe that in each case, the performance of BGK degrades when we use the better prediction W A . The dynamic offset policy always outperform BGK and does not exhibit this problem: it performs (slightly) better with the better forecast W A . This is why we say that DO is consistent: a smaller error results in a better performance.

V. OPTIMAL STORAGE CHARACTERISTICS

A. Optimal Charging and Discharging power (C max , D max ) Let us define the global performance of a policy π by the sum of the energy loss plus the total use of reserve:

Global performance of π := Lπ + Ḡπ . (20)
Figure 8 depicts the global performance of the dynamic offset policy DO run with W LC and the BGK policy run with W WP . For BGK, we chose W WP as it often outperforms BGK with W LC (see Figure 6). For each point, we choose the parameter (γ or λ) that minimizes L+ Ḡ. The time horizon is n = 6h.

As observed in the previous sections, DO performs always at least as well as BGK. It significantly outperforms BGK for low storage capacities. Moreover, the performance improves dramatically for small power capacities and does not change much when C max >0.80 AWP. This indicates that 0.80 AWP is enough to mitigate forecast error for 6h. Note that this optimal ramping constraints does not depend on η. 20)) of the dynamic offset policy and of BGK as a function of Cmax = Dmax. We see that the knee of the performance is close 0.80 AWP. All values are expressed in percentage of average wind production (AWP).

Increasing the ramping constraints C max does not improve the performance when the forecast error has a small probability of exceeding the ramping constraints. Therefore, we define the optimal ramping constraints of the storage as

C opt (n) = min{c s.t P (|ε| > c) ≤ 1%}. (21)
In this equation, ε is defined as in §IV-B1: it is distributed as the forecast error W (t+n) -W LC t (t+n) and depends on n. Figure 9(a) indicates that this optimal power capacity converges to 1 AWP as n goes to infinity. It quickly reaches 0.80 AWP for n = 6h and then saturates. This is consistent with the relative error of W LC shown on Figure 3.

Using statistical analysis, the authors of [START_REF] Bludszuweit | Statistical analysis of wind power forecast error[END_REF] argue that the power capacity needed to compensate for persistence forecast errors is between 50% and 100% of AWP for n=1h and 150% to 250% for n=12h. The values reported in Figure 9 are significantly smaller because W LC is significantly better than W PF . Applying our methodology to W PF leads to 50% for n = 1h and 190% for n = 12h, close to the number of [START_REF] Bludszuweit | Statistical analysis of wind power forecast error[END_REF].

B. Optimal Storage Capacity

The storage capacity influences the lost energy or the reserve use when there is an overflow or an underflow of the storage system. As the storage capacity increases, the probability of such an event occurring decreases. As we observe on Figure 10, this decrease is significant for low values of B max but saturates for high capacity. For example, when C max =0.30 AWP, η=0.8 and n=6h, increasing the storage capacity to more than 10 AWPh has a negligible effect. 20)) of the policy DO as a function of Bmax. A different value of n is associated to each row and a different value of Cmax=Dmax and η to each column. In each case, the knee of the performance is between the two vertical lines which represents B opt (n) and 2B opt (n), defined in Eq.( 23). The knee does not depend on Cmax or η.

If we remove power constraints and efficiency, the control problem [START_REF] Bitar | Optimal sharing of quantity risk for a coalition of wind power producers facing nodal prices[END_REF] becomes

B(t + 1) = max(min(B(t) + ξ + ε + u, B max ), 0). (22)
By setting u := B max /2 -B(t), the probability of having an overflow or an underflow is P (2 |ξ + ε| > B max ). This suggests that if B max is such that this probability is small, there is no need to increase the storage capacity.

Therefore, we define the optimal storage capacity as

B opt (n) = min{b s.t P (2 |ξ + ε| > b) ≤ 1%}. (23)
where ξ and ε are defined as in §IV-B1, and depend on n.

Figure 10 shows a good match between this heuristic and the observed value of the optimal storage: the observed optimal storage capacity lies between B opt and 2B opt .

A numerical evaluation of B opt given by Equation ( 23) is depicted in Figure 9(b). This indicates that the optimal storage capacity grows sub-linearly for n < 6h and then increases by about 1.5 AWPh per hour of time horizon for n ≥ 6h. This corresponds to 150% of the average wind energy produced in one hour, or 40% of the peak production.

VI. CONCLUSION AND FUTURE WORK

In this paper, we adopt the viewpoint of a social planner and investigate efficient ways of integrating renewables in the power mix with the aid of fast-reacting energy storage systems characterized by a cycle efficiency η < 1. The cost is decomposed into two metrics: the amount of used reserves versus the wasted renewable energy. In Theorem 1, we derive a fundamental lower bound on the cost of any production scheduling policy, given a certain irreducible stochasticity in the forecast errors of the renewable production. We define FO, a deterministic policy that schedules an amount of production equal to the production mismatch, i.e., the difference between the forecast demand and the forecast renewable output, offset by a fixed value. We use the statistics of forecast errors to construct a second policy (DO) through stochastic optimization. The policy DO schedules an amount of production equal to the production mismatch, offset by a dynamic value that depends of the forecasted storage level. When the available energy capacity of storage is sufficiently large, we prove that the policy FO matches the theoretical lower bound. In all cases, DO outperforms all tested policies, in particular the policy that aims to keep the storage level balanced (at half the capacity) [START_REF] Bejan | Statistical aspects of storage systems modelling in energy networks[END_REF]. We show that there exists a desirable operating point for the system, which achieves a trade-off between the two metrics of interest. This point can be determined using the heuristic provided in Algorithm 1. The proposed policies are evaluated on real data collected in the UK made available by ELEXON. This study can serve for designing an efficient energy market that accounts for the available storage, more specifically, incentive and pricing mechanisms that match the socially-optimal performance.

Our dynamical storage management policy, DO, could also be adapted for profit maximization in a market environment with variable or uncertain prices. The only difference in the construction of the the stochastic optimization problem is that the instantaneous cost [START_REF] Chatzivasileiadis | Incentives for optimal integration of fluctuating power generation[END_REF] needs to be replaced by a timevarying cost function that depends on instant prices. When storage is large, we conjecture that the cost of the policy DO attains the lower bound (like the deterministic FO policy). This conjecture is left for further study.

In order to keep the model tractable and to develop a generic methodology, we do not consider the network physical constraints. They intervene in a situation where the transmission network is unable to balance a local overproduction of renewable sources and an underproduction in a remote location. In this case, the placement of storage becomes crucial. Our methodology can be used in a multiple-stage optimization problem: first by using local storage to solve local imbalance, and finally by aggregating these results.

APPENDIX A PROOF OF THEOREM 1

Proof: Equations ( 12) and ( 13) come from two terms: one is due to the charging constraint C max and storage inefficiencies and the other to discharging constraint D max .

By definition (4), if M (t) := -e f t-n (t) -u(t) is negative, we store energy and the energy loss between t and t + 1 is M (t) minus what is stored in the dam 3 . If we neglect the overflows due to B max , we obtain the lower bound [START_REF] Tuohy | Impact of pumped storage on power systems with increasing wind penetration[END_REF]:

L(t) = (M (t)) --(B(t + 1) -B(t)) + ≥ (M (t)) --η min((M (t)) -, C max ). (24)
Similarly, the use of reserves is

G(t) ≥ (M (t)) + -min((M (t)) + , D max ) (25)
For any x ∈ R, let us define C(x) and D(x) by:

C(x) = ηE min((ε + x) + , C max ) (26) D(x) = E min((ε + x) -, D max ) . (27)
To ease the notation, we denote by u(t) the additional power u f t-n (t) that was scheduled at time t -n. As u(t) was scheduled using information available at time t-n, it is F t-nmeasurable. Therefore, using that M (t) = -e f t-n (t)-u(t) and that e f t-n (t) is independent of F t-n , Equation ( 24) implies

E [L(t)] = E [E [L(t)|F t-n ]] ≥ E E (e f t-n (t)+u(t)) + -η min((e f t-n (t)+u(t)) + , C max )|F t-n = E (ε + u(t)) + -η min((ε + u(t)) + , C max ) = E (ε + u(t)) + -D(u(t)). (28)
For a fixed value ε, x →(ε+x) + -η min((ε+x) + , C max ) is convex. Therefore, the function x → E [(ε+x) + ] -C(x) is convex. Combined with Equation (28), this shows that

L(T ) = 1 T T t=1 E [L(t)] = 1 T T t=1 E (ε + u(t)) + -D(u(t)) ≥ E (ε+ū) + -C(ū) (29)
where the last inequality comes from Jensen's inequality and ū = T t=1 u f t (t+n)/T . Starting from (25) and using similar ideas for, we also have

Ḡ(T ) ≥ E (ε+ū) --D(ū). (30)
Using the energy balance equations ( 3) and (4), we have

B(t + 1) -B(t) = G(t) -L(t) -M (t). (31)
Summing this equation from t=1 to T implies that

Ḡ(T ) = L(T )+ 1 T T t=1 E [M (t)] + 1 T (B(T )-B(0)). (32)
As |B(0) -B(T )| ≤ B max , combining this with (29) and Equation [START_REF] Hodge | Wind power forecasting error distributions over multiple timescales[END_REF] shows that

Ḡ(T ) ≥ L(t) -E [ε+ū] -B max /T (33) = E (ε+ū) --C(ū) -B max /T (34) L(T ) ≥ Ḡ(t) + E [ε+ū] -B max /T (35) = E (ε+ū) + -D(ū) -B max /T. (36)
Since the function f is defined by f (u) = min(C(u), D(u)), this concludes the proof of Equations ( 13) and [START_REF] Constantinescu | A computational framework for uncertainty quantification and stochastic optimization in unit commitment with wind power generation[END_REF]. It should be clear that g(u) is decreasing in u and (u) is increasing in u. This implies that the function g(u) → (u) is well-defined and decreasing. Moreover, by definition of and g, we have

(u) = E [(ε+u) + ] -f (u) = E [ε] +u+g(u).
Thus, the derivative of (u) w.r.t g(u) equals

d dg = d /du dg/du = 1 + 1 dg(u)/du . ( 37
)
Since g is convex (it is the maximum of two convex functions), the function u → dg/du is increasing. As g is a decreasing function of u, the dg/du decreases with g. This implies that (37) increases with g, which shows that the parametric curve u → (g(u), (u)) is convex.

APPENDIX B PROOF OF THEOREM 2

We first start by a technical lemma. We say that a sequence of variable (X(t)) t=0,1,... is uniformly integrable if for every ν > 0, there exists R > 0 such that E |X(t)| 1 |X(t)>R| ≤ ν. In particular, this is true if the variables (X(t)) t are identically distributed.

Lemma 1: (X(t)) t be a uniformly integrable sequence of random variables adapted to a filtration F t . Assume that E [X(t)|F t-n ] = 0. Then, for all α, δ > 0, there exists T 0 > 0 such that for all T ≥ T 0 , we have:

P sup τ <T τ t=1 X(t) > αT ≤ δ. ( 38
)
Proof: For all 1 ≤ k ≤ n and t ≥ 0, we define the variable Y k (t) := X(nt + k) and we define G k t := F nt+k . It should be clear that (Y k (t) t≥0 is a G k t -adapted process. Moreover, the sequence of variable (Y k (t)) t≥0 is uniformly integrable and satisfies E Y k (t + 1)|G l t = 0. Therefore, by Lemma 16 of [START_REF] Gast | Markov chains with discontinuous drifts have differential inclusion limits[END_REF], there exists T k > 0 such that for all T ≥ T k :

P sup τ <T τ t=1 Y k (t) > αT ≤ δ k . (39)
Let T 0 := n max 1≤k≤n T k . Applying the union bound, we have that for all T ≥ T 0 , P sup We are now ready to prove the main theorem.

Proof: Let us now consider that the dispatcher applies the fixed offset policy u and let us first assume that D(u) > C(u).

The only neglected terms in Equation ( 24) are the losses due to overflows (i.e. the storage is full and cannot be charged):

L(t) = M -(t) -η min(M -(t), C max ) + overflow(t). (42)
The mismatch at time t is M (t) = -(e(t) + u), where e(t) denotes the forecast error at time t. Let c(t) = η min((e(t) + u) + , C max ) be the quantity that is charged at time t.

An overflow occurs at time t + 1 if c(t) is greater than

By the assumptions on the noise e(t) and the definition of C and D, X(t) satisfies the assumption of Lemma 1. Let ν = δ/(2E [c(t)]) (this is independent on t as we use the fixed offset policy and the noise is identically distributed). By Lemma 1, there exists T 0 such that if T ≥ T 0 :

P sup k≤T k t=1 X(t) > α 4 T ≤ ν. (51)
Let B = T 0 α and assume that B max ≥ min(B, 2b 0 ). Let T = B max /α. For all t ≥ T the probability P(B(t) ≥ B max /2) satisfies

• If B(s) = 0 for all t ≤ s < T , then

B(T ) ≤ B(0) -αT + T t=1 X(t) ≤ T t=1 X(t) (52)
• Otherwise, let t be such that B(t ) = 0 and B(s) = 0 for all s such that t ≤ s < T . We have This proof applies mutatis mutandis to the case D(u) < C(u). In that case, this leads to Ḡ ≤ E [(ε + u) + ] -D(u) + δ.

B(T ) ≤

Using Equation [START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF], this implies that for D(u) = C(u), L ≤ (u) + δ and Ḡ ≤ g(u) + δ. Since L is an increasing function of u (and Ḡ a decreasing function of u) and (u) and g(u) are continuous in u, this also holds for D(u) = C(u).

Fig. 1 .

 1 Fig. 1. The total energy balance: P + W + M = D.

Fig. 2 .

 2 Fig. 2. Typical sample of day-ahead forecast W WP and forecast with linear correction W LC versus actual wind power production (March 2010).

(8Fig. 4 .

 4 Fig.4. Illustration of Theorems 1 and 2. The performance of each policy is represented by a point ( L, Ḡ) where L is the average lost energy and Ḡ the average use of reserves. The dashed curve is the lower bound of Theorem 1. By Theorem 1, the performance of a policy cannot be in the gray zone without improving the forecast. By Theorem 2, the fixed offset policy performs close to optimally for large storage capacity: its performance is on the dashed curve.

Algorithm 2

 2 DO: computation of the control law δ γ . Require: Trade-off γ, step-size h, statistics of errors ξ and ε. k ← 0; V 0 (b) ← 0 for all b ∈ {0, h, 2h, . . . , B max } while sup b |V k (b) -V k-1 (b)| ≥ precision threshold do for all b ∈ {0, h, 2h, . . . , B max }, do Vk+1 (b)← inf u∈R E c((b+ξ) Bmax 0 , u+ε)

5 (b) η = 1 Fig. 5 .

 515 Fig.5. Offset set by the different policies as a function of the forecasted storage level Bt(t + n). We plot the three policies FO(30AWP), BGK(0.5) and DR[START_REF] Gast | Optimal storage policies with wind forecast uncertainties[END_REF]. The offset set by FO does not depend of the forecasted storage level. The offset of BGK varies abruptly around 0.5Bmax. DO reacts more smoothly. The parameters of the storage system are Bmax=10 AWPh and Cmax=Dmax=1 AWP. The offset are expressed in percentage of average wind production (AWP).

Fig. 6 .

 6 Fig.6. Performance of the fixed offset policy, the BGK policy and the dynamic offset policy for various storage characteristics. The left plots are for an efficiency of η = 0.8 while the right plots are for η = 1. Values are expressed in percentage of average wind production (AWP).

1 Fig. 7 .

 17 Fig. 7. Performance of BGK and DO for the two forecasts W A and W B . Although the forecast W A is better than the forecast W B , BGK performs better with W B . The performance of DO is slightly better with W A . All values are expressed in percentage of average wind production (AWP). The storage capacity is Bmax = 10 AWPh and the maximum power is Cmax=Dmax=0.5 AWP.

1 Fig. 8 .

 18 Fig.8. Global performance (Eq.(20)) of the dynamic offset policy and of BGK as a function of Cmax = Dmax. We see that the knee of the performance is close 0.80 AWP. All values are expressed in percentage of average wind production (AWP).

  hours) opti. ramping constr. (% AWP) C opt (a) C opt as a function of n B opt as a function of n Fig. 9. Optimal storage characteristics C opt and B opt as a function of n, given by Equation (21) and Equation (23).

Fig. 10 .

 10 Fig.10. Global performance (Eq.(20)) of the policy DO as a function of Bmax. A different value of n is associated to each row and a different value of Cmax=Dmax and η to each column. In each case, the knee of the performance is between the two vertical lines which represents B opt (n) and 2B opt (n), defined in Eq.(23). The knee does not depend on Cmax or η.

  B max -B(t). Let us denote O(t+1) = (c(t)+B(t)-B max ) + the quantity of overflow at time t + 1. Then, for any b > 0,E [O(t+1)] = E O(t+1)1 B(t)≤Bmax-b (43) + E O(t+1)1 B(t)>Bmax-b(44)Let δ > 0. The first term, Equation (43), is equal toE (c(t) + B(t) -B max ) + 1 {B(t)≤Bmax-b} (45) ≤ E (c(t) -b) + 1 {B(t)≤Bmax-b} ≤ E (c(t) -b) + (46)Since the errors are identically distributed, there exists b 0 such that if b ≥ b 0 , then Equation (43) is less than δ/2. As for the second term, (44), we haveE O(t+1)1 B(t)>Bmax-b ≤ E [c(t)] P (B(t) > B max -b) .(47)Let us define X(t) by:X(t) = η min((e f t-n (t) + u) + , C max ) -C(u)(48)-min((e f t-n (t) + u) -, D max ) + D(u).(49)Let α = D(u) -C(u). The storage B(t) satisfies B(t + 1) = (B(t) + X(t) -α) Bmax 0 .

  51), this is lower than B max /2 with probability ν. Let B 0 := max(B, 2b 0 ). Equations (43-44) imply that forB ≥ B 0 , E [O(t + 1)] ≤ δ for all t ≥ T + 1.This shows that for all B max ≥ B 0 , we have: by definition of the losses, Equation (42), implies thatL = lim sup k→∞ 1 k k t=1 E [L(t)] ≤ E (ε+u) + -C(u)+δ. (57)

Recall that we denote by (M (t)) -the negative part of M (t), which is equal to 0 if M (t) ≥ 0 and to -M (t) otherwise.

He is or has been on the program committee or editorial board of many conferences and journals, including Sigcomm, Sigmetrics, Infocom, Performance Evaluation and ACM/IEEE Transactions on Networking.