electricity reserve markets ,online learning ,auction ,regret

1 Introduction↩︎

A balance between power supply and demand is necessary to maintain the stability of a power grid. Depending on the power grid one considers, this balance is ensured through different mechanisms. In most countries, consumers’ and producers’ schedules are coordinated ahead of time in order to provide this equilibrium. For most European countries, including France, this coordination takes place the day before delivery through a common market mechanism: the wholesale spot market.

To ensure robustness of the supply/demand equilibrium, one needs to be able to compensate for sudden, unpredictable changes in the behavior of a consumer or a producer (for instance, in case of the outage of a power plant). This is usually dealt with by leveraging the ability of producers and consumers to change their production or consumption in order to maintain the balance of the power grid. This capacity to modify upward or downward one’s power production or consumption is called flexibility. Transmission System Operators (TSO) make an agreement with flexibility owners to be able to use their flexibility for a fixed price beforehand. These are called reserve capacity, and the price and allocation of this reserve capacity are determined by a market mechanism.

To meet operational requirements such as response time, total uptime, and transmission capacities, reserves are categorized into different types. One of these is the Frequency Containment Reserve (FCR), which is the focus of our market analysis. The FCR is activated immediately following a supply or demand imbalance and remains in use until a more sustainable reserve can take over, typically from 15 seconds to a few minutes after the incident.

This work investigates algorithms and methods that enable a market actor to decide the best price to offer its flexibility in the FCR mechanism. To maximize its wealth, each market actor has an incentive to derive relevant participation strategies and to run them consistently over time. This is a challenging problem, as it involves both known factors (such as the market rules and production costs) and unknown ones (notably, the prices offered by competing producers). Moreover, beyond the design of the strategy of participation in an auction, the actor can benefit from the daily repetition of the auction to try to learn the behaviour of other participants.

Our approach builds on the observation that, from the point of view of one participant who is located in a single country, the FCR mechanism can be reduced to a uniform-price auction with a fixed number of units to be procured. While in these auctions, as in most, the best prices to submit depend on other participants’ strategies, when the same auction takes place repeatedly, these strategies can be learned through online learning algorithms. Because reserve markets are also repeated frequently, this reduction allows us to leverage existing results from the literature on learning in auctions, which we adapt to our specific setting.

1.1 Literature review↩︎

Online learning for auctions was first studied from the point of view of the auctioneer, notably by [1], trying to maximize revenue, or [2], who focused on learning the reserve pricing. These online procedures were then first explored to be used by participants in these auctions by [3]. While early work focused on learning single-item auctions, multi-unit auctions were also examined and first mentioned in [4]. The uniform price setting, which is of particular interest to our problem, was specifically explored in [5] and then improved by [6]. Further work on these auctions with particular learning objectives or comparing uniform auctions to other auction formats was also developed recently [7], [8].

Sequential learning has been applied extensively to study energy markets. It has been studied for bidding in energy markets under the adversarial opposing bid hypothesis by [9]. A similar approach was presented in [10], where they designed a variation of the EXP3 algorithm for a general model that resembles procurement auctions. Similarly, [11] studied how the use of no-regret algorithms by participants in forward electricity markets could influence social welfare. Machine learning-based approaches have also been explored more recently, such as in [12] that leverages deep reinforcement learning or [13], which focuses on more traditional machine learning techniques such as decision trees or SVMs.

The online learning algorithms used in the previously described settings benefit from theoretical guarantees. However, these guarantees vary widely depending on the environment (adversarial or stochastic), and one has to choose EXP3 or UCB accordingly [14]. In practice, one usually cannot tell beforehand if the environment is stochastic or not. Best Of Both Worlds (BOB) algorithms were introduced in [15] and they adapt automatically to both environments. Recent advances in BOB algorithms allow a simple formulation as an optimization problem [16]. [17] proposes an algorithm with guarantees not only for adversarial and stochastic environments but also for settings smoothly interpolating the two.

1.2 Our Contributions↩︎

The main contributions of this work are threefold: (i) modeling of the FCR auction and, in particular, simplification arising from the point of view of a participant, (ii) algorithm design of a bidding algorithm and theoretical guarantees for the performance, (iii) numerical simulation and backtesting on real data.

This work provides a precise description of the FCR market rules and of the details of the clearing mechanism available on the website [18]. We give a formal modeling of this mechanism with several countries interconnected by a given capacity and a description of the price fixing and allocation rules. Focusing on a utility-maximizing flexibility provider’s bidding strategy, we show that the problem he faces can be reduced to bidding in a uniform price auction, under weak assumptions. In particular, this remains valid in practice when only accepted bids are revealed. This reduction is a key contribution of this work. Its benefits are twofold: first, it allows us to disregard irrelevant variables such as demand in foreign countries, and second, it allows us to leverage on the existing literature on bidding in uniform price auctions.

Building on the aforementioned reduction, we adapt existing online learning algorithms for learning to bid in auctions to the problem faced by a flexibility provider. Specifically, we focus on BOB algorithms which provide optimal theoretical guarantees on the performance without prior knowledge of the behaviour of other participants. We particularly leverage the ones developed for semi-bandit feedback [19]: their structure closely matches that of the auction studied in this paper, and in our reformulation, the corresponding coordinate-level signals can be reconstructed from the market-level bandit observations (allocation and clearing price). We also provide an efficient method to solve the optimization problem at each step of the BOB algorithm, which allows the algorithm to run in a reasonable time.

To illustrate our results, we provide both synthetic market simulations and simulations based on actual reserve market data. The synthetic simulations showcase the guarantees provided by our learning procedure. The simulations based on actual data show that the approach can be used in practice to learn bid prices in the FCR market, and highlight that algorithm choice should depend on product characteristics: BOB performs well on more stable products, while EXP3-type methods can be preferable when non-stationarity is stronger.

The remainder of the paper is organized as follows. 2 formalizes the FCR clearing mechanism and states the reduction to a uniform-price auction from the perspective of one participant. We then introduce, in 3 , the repeated-auction learning setting (the feedback models and regret benchmarks) as well as our algorithm and its guarantees. The numerical study, which evaluates the method on both synthetic and historical FCR data is presented in 4. We finally conclude and summarize our findings in 5; the appendix (6) gathers the full proofs and technical constructions.

2 FCR Market Modelling and reduction to Auction↩︎

In this paper, we focus on the European Frequency Containment Reserve (FCR) cooperation, operated under the ENTSO-E framework and national TSOs’ joint procurement rules. The FCR is a symmetric reserve, meaning it can be activated in both upward and downward directions. As a result, we consider symmetric flexibility, without distinguishing between upward and downward services. Furthermore, since both consumers and producers can provide flexibility, we will refer to both types of actors as flexibility providers or participants. The FCR divides electricity into units of 1 MW, which we will call units in the following.

The general rules of this mechanism are drafted in the official report [20], and daily clearing data is available in [18]. The model presented below omits some operational refinements but preserves the core dynamics that shape the price formation. In particular, it accounts for the multi-country nature of the mechanism and the restricted interconnection capacities between national grids. These two elements together create discontinuities in the price-setting process.

Let \(\mathcal{S}\) be the set of countries involved in the mechanism. For each \(s \in \mathcal{S}\), denote \(\mathcal{J}_s\) the set of flexibility providers within that country, and \(\mathcal{J}:= \cup_{s \in \mathcal{S}} \mathcal{J}_s\) the set of all flexibility providers.

The FCR market proceeds as follows:

1. For each country \(s \in \mathcal{S}\), the demand for reserve \(D_s\) and the maximum available transmission capacity \(T_s\) (the maximum amount of electricity that can be transferred in or out of country \(s\)) dedicated to reserve are made public.

2. Each flexibility provider \(j \in \mathcal{J}\) submits a set of bids denoted \(\mathbf{b}_j\), reflecting how many units they are willing to provide and at which prices.

3. The market clears, determining one price \(p_s\) for each country \(s \in \mathcal{S}\) (which applies to all providers from that country), and an allocation \(x_j\) for each flexibility provider \(j \in \mathcal{J}\).

4. Each flexibility provider \(j \in \mathcal{J}\) located in country \(s\), is paid the price \(p_s\) for each unit of reserve it is allocated, i.e., it receives \(x_j p_s\) euros.

We define the maximum quantity of reserve that can be procured in country \(s\) by \(D_{max,s}:= D_s + T_s\).

The following paragraph provides details on the bidding procedure and the following 2.1 expands on the market clearing mechanism.

2.0.0.1 Bidding

In practice, flexibility providers submit bids in the form of a set of prices and corresponding quantities, representing how many units they are willing to sell above each price. For ease of notation, we assume that the bid prices (which in practice have upper and lower bounds) are rescaled between \(0\) and \(1\). We also assume that flexibility providers submit one price for each unit of reserve they are willing to sell.

Under this assumption, we can complete each offer up to \(D_{\max,s}\) by inserting the maximal price \(1\) without changing outcomes: these completed bids are never accepted and therefore do not affect prices or allocations. Empirically, this assumption is consistent with the historical FCR data considered in this paper.
Since bids are made in euros, the smallest price increment is one cent. The rescaled bids therefore belong to a corresponding uniform discretization of \([0,1]\), denoted by \(\mathcal{B}\). Hence, to participate in the market, each flexibility provider emits a bid vector \(\mathbf{b}_j \in \mathcal{B}^{D_{max,s}}\), whose coordinates are assumed to be ordered in non-decreasing order.

2.1 Clearing FCR market↩︎

The clearing of the market is described in the following section. It aims at minimizing the total cost of procuring the required reserve across all countries, while respecting national demand constraints, transfer limits, and the bids of all flexibility providers. It is formulated as a constrained minimization problem which determines both the allocation \(\left( x_j \right)_{j \in \mathcal{J}}\) (i.e., how many units of reserve each provider sells) and the per-unit price paid in each country \(\left( p_s \right)_{s \in \mathcal{S}}\): \[\left( (x_j)_{j \in \mathcal{J}}, (p_s)_{s \in \mathcal{S}} \right) = \underset{ \substack{ \mathbf{p} \in \mathcal{P}(\mathbf{b}) \\ (x_j)_{j \in \mathcal{J}} \in \mathcal{A}(\mathbf{b}, \mathbf{p}) }}{\arg\min} \sum_{s \in \mathcal{S}} \sum_{j \in \mathcal{J}_s} x_j \, p_s , \label{eq:fcr95minimization}\tag{1}\] where \(\mathcal{P}(\mathbf{b})\) denotes the set of admissible price vectors given the submitted bids \(\mathbf{b}\), and \(\mathcal{A}(\mathbf{b}, \mathbf{p})\) the corresponding set of admissible allocations. We formally define these constraint sets below.

2.1.0.1 Bids and Allocations.

Each provider \(j \in \mathcal{J}_s\) in country \(s\) submits a set of bids \(\mathbf{b}_j = (b_{j,l})_{l \in [D_{max,s}]} \in \mathcal{B}^{D_{max,s}}\). For a given price \(p_s\), the maximum allocation a provider can receive is the number of units it offered below that price: \[\bar{x}_j(\mathbf{b}_j, p_s) := \sum_l \ifthenelse{ \equal{}{} } {\mathbb{1} } {\mathbb{1} \left \{ \right \}} \{ b_{j,l} \le p_s \}.\] Similarly, we can define the minimum allocation a flexibility provider can receive as the number of bids strictly below the price \[\underline{x}_j(\mathbf{b}_j, p_s) := \sum_l \ifthenelse{ \equal{}{} } {\mathbb{1} } {\mathbb{1} \left \{ \right \}} \{ b_{j,l} < p_s \}.\] We denote by \(x_j(\mathbf{b}_j,p_s)\) the actual allocation chosen by the clearing mechanism; it is an integer satisfying \(\underline{x}_j(\mathbf{b}_j, p_s) \leq x_j(\mathbf{b}_j,p_s) \le \bar{x}_j(\mathbf{b}_j, p_s)\).

2.1.0.2 Transfers.

For each pair of countries \((s, s') \in \mathcal{S}^2\), let \(t_{s,s'} \in \mathbb{R}^+\) represent the transfer from \(s\) to \(s'\), and let \(\mathcal{T}\) denote the set of valid transfers, i.e.,

1. \(\forall s \in \mathcal{S}, \sum_{s' \ne s} t_{s,s'} \le T_s\) (exports bounded by capacity),

2. \(\forall s \in \mathcal{S}, \sum_{s' \ne s} t_{s',s} \le T_s\) (imports bounded by capacity),

3. \(\forall s,s' \in \mathcal{S}^2, \;t_{s,s'} \cdot t_{s',s} = 0\) (no simultaneous import and export with a specific country).

We say that the transmission capacity of country \(s\) is saturated if either its total imports or exports reach \(T_s\).

2.1.0.3 Admissible Prices and Allocations.

A vector of prices \(\mathbf{p} = (p_s)_{s \in \mathcal{S}}\) is admissible given the bids \(\mathbf{b}\) if there exist valid transfers \(\mathbf{t} = (t_{s,s'})_{s,s' \in \mathcal{S}^2} \in \mathcal{T}\) such that: \[\begin{align} & \forall s \in \mathcal{S}, \; \sum_{j \in \mathcal{J}_s} \bar{x}_j(\mathbf{b}_j, p_s) \ge D_s + \sum_{s' \in \mathcal{S}} (t_{s,s'} - t_{s',s}), \tag{2} \\ & \exists p \in \mathcal{B}, \forall s \in \mathcal{S} \begin{cases} \text{if} \left| \sum_{s'} (t_{s,s'} - t_{s',s}) \right| < T_{s} & \text{then } p_s =p \\ \text{if} \sum_{s'} (t_{s,s'} - t_{s',s}) = T_s & \text{then } p_s \leq p \\ \text{if} \sum_{s'} (t_{s,s'} - t_{s',s}) = - T_s & \text{then } p_s \geq p \end{cases} \tag{3} \end{align}\]

Condition 2 on admissible prices ensures each country can meet its (demand + net exports). Condition 3 ensures that prices behave as in the true FCR market. It enforces equal prices across countries connected by non-saturated transfers and, respectively, higher/lower prices when import/export capacities are saturated.

Given admissible prices \(\mathbf{p}\), an admissible allocation \(\left( x_j \right)_{j \in \mathcal{J}}\) satisfies: \[\begin{align} & \forall s \in \mathcal{S}, \forall j \in \mathcal{J}_s, \underline{x}_j(\mathbf{b}_j, p_s) \leq x_j \le \bar{x}_j(\mathbf{b}_j, p_s), \tag{4} \\ & \forall s \in \mathcal{S}, \;\sum_{j \in \mathcal{J}_s} x_j = D_s + \sum_{s'} (t_{s,s'} - t_{s',s}). \tag{5} \end{align}\]

2.2 Utility maximizing flexibility provider↩︎

We focus on the perspective of a flexibility provider participating in the FCR market from a single country, that we will also call the principal. It faces the problem of selecting bid values to maximize its expected utility. We fix this provider as \(j \in \mathcal{J}_s\), in country \(s\), for the rest of the paper. We adopt the following quasi-linear model for its utility: let \(\left \{ c_1,\ldots,c_{D_{max,s}} \right \} \in [0,1]^{D_{max,s}}\) be the marginal costs of producing each unit of flexibility sold. We assume these marginal costs are non-decreasing. The utility of the principal after the auction writes as follows : \[\begin{align} \label{eq32:32utility32flex32producer} u_j(\mathbf{b}) := \sum_{i=1}^{x_j(\mathbf{b})} \left ( p_s(\mathbf{b}) - c_i \right ) \end{align}\tag{6}\]

From the point of view of the principal, the only relevant outcomes of the market clearing are its own allocation \(x_j(\mathbf{b})\) and the local clearing price \(p_s(\mathbf{b})\) (this is clear from the utility formula 6 ). This results in the following: everything happens as if it were participating in a uniform price auction (introduced below and fully described in 6.2), which is simpler than the clearing mechanism described in 2.1. The following [lemma32:32equivalence32market-auction] provides a formal statement of this reduction.

2.3 Reduction to a Uniform Auction↩︎

The equivalence described below provides a direct structural justification for applying existing online learning techniques, developed for uniform price auctions, to the real FCR market. Before stating our result, let us briefly introduce the mechanism that is the focus of this equivalence.

2.3.0.1 Uniform Price auction

A uniform-price auction is a mechanism that selects the \(D_{max,s}\) lowest bids from a set of submitted bids. It accepts the corresponding units and pays every accepted unit the same clearing price, equal to the last (highest) accepted bid. We denote by \((p^U(.),x^U(.))\) the resulting clearing price and accepted quantity (called allocation). Full details are provided in 3.1.0.1.

We denote \(\mathbf{b}_{-j,s}\) and \(\mathbf{b}_{-s}\) respectively the bids of the other producers in country \(s\) and the bids of producers in all other countries \(s' \neq s\). Then the following holds:

The full proof is available in Appendix 6.2. We provide below a proof sketch to provide insight into both how \(\boldsymbol{\beta}\) can be computed, and where the equivalence between the two mechanisms arises.

3 Online Learning↩︎

We focus on the problem faced by the principal: the choice of the best bid \(\mathbf{b}\) in order to maximize its utility. We are interested in leveraging the repeated aspect of the FCR auction to accumulate knowledge about the behaviour of opposing bids. We formally describe below the uniform auction, the repeated setting as well as the information available to the principal, allowing them to accumulate knowledge.

3.1 Setting and Notations↩︎

[lemma32:32equivalence32market-auction] demonstrates that, when considering the problem faced by the principal, the FCR auction can be viewed as an instance of an uniform auction, where \(D_{max,s}\) units are to be bought and in which other participants’ bids are \(\boldsymbol{\beta}\). Therefore, from this section onward, we work in the reduced uniform-auction representation, which is sufficient because of [lemma32:32equivalence32market-auction]. Since there is no ambiguity remaining, we write \(p(\mathbf{b},\boldsymbol{\beta})\), \(x(\mathbf{b},\boldsymbol{\beta})\), \(u(\mathbf{b},\boldsymbol{\beta})\) for outcomes instead of \(p^{\mathrm U}(\mathbf{b},\boldsymbol{\beta})\), \(x^{\mathrm U}(\mathbf{b},\boldsymbol{\beta})\), \(u^{\mathrm U}(\mathbf{b},\boldsymbol{\beta})\). We detail below how this auction proceeds:

3.1.0.1 Uniform Price auction

We describe below in detail the uniform price auction mentioned above, where \(D_{max,s}\) units are to be bought, from the point of view of the principal, whose cost of producing the \(\text{k}^\text{th}\)-unit of electricity is denoted by \(c_{k}\in [0,1]\). In this auction, the principal faces opposing bids \(\boldsymbol{\beta}\) (which, by [lemma32:32equivalence32market-auction] can be computed from actual opposing bids in FCR markets). The auction proceeds as follows:

1. The principal submits its bids \(\mathbf{b}:=(b_{k})_{k\in[K]} \in B\), where \(K=D_{max,s}\) and \(B= \left \{(b_l)_{l \in [K]} \in \mathcal{B}^{D_{max,s}} \right .\), such that \(\left. 0 \leq b_{1}\leq b_{2} \leq \ldots \leq b_{K} \leq 1 \right \}\).

2. The opposing bids \(\boldsymbol{\beta}= (\beta_k)_{k \in [K]} \in B\) (in non-decreasing order)¹ are submitted to the auction.

3. The per-unit price is set as the \(D_{max,s}^\text{th}\) lowest bid from \((\mathbf{b}_j,\boldsymbol{\beta})\), denoted by \(p \left(\mathbf{b}_j, \boldsymbol{\beta}\right)\).

4. The principal sells to the auctioneer every unit of flexibility they proposed below the price \(p \left( \mathbf{b}_j,\boldsymbol{\beta}\right)\) and receives this price in exchange. Their allocation \(x\in[K]\) of production is therefore as follows²: \[\begin{align} x\left (\mathbf{b},\boldsymbol{\beta}\right ) & := \left \lvert \left \{k \in [K] \text{ s.t. } b_{k} \leq p \left ( \mathbf{b},\boldsymbol{\beta}\right ) \right \} \right \rvert .\addtocounter{equation}{1}\label{def32:32allocation32elec32market} \end{align}\tag{7}\]

This setup gives rise to the quasi-linear utility \(u(\mathbf{b},\boldsymbol{\beta}) = \sum_{l=1}^{x(\mathbf{b},\boldsymbol{\beta})} \left [ p(\mathbf{b},\boldsymbol{\beta}) - c_l\right]\).

Let \(T\) be the time horizon of the repeated auction. Sequentially, at each time \(t \in [T]\), the auction proceeds as described in 3.1.0.1, or equivalently as described above. We extend the notations introduced above to describe the auction with a superscript \(t\) (i.e., the principal bids \(\mathbf{b}^t\), opposing bids \(\boldsymbol{\beta}^t\), etc.). The following convention allows us to completely describe the online learning problem faced by the principal.

3.1.0.2 Feedback

For learning, specifying the information available after each round, usually referred to as feedback, is pivotal. We describe below the two types of feedback we consider.

• Full information feedback: All the information about the auction is revealed to the principal, formally, the principal observes \(\boldsymbol{\beta}^t\).

• Bandit Feedback: The principal only observes its allocation \(x(\mathbf{b}^t,\boldsymbol{\beta}^t)\) and the price \(p(\mathbf{b}^t,\boldsymbol{\beta}^t)\).

In the original auction representation, it is common to only receive Bandit Feedback. As such, the algorithm we propose below (1) works with this minimal feedback. Naturally, if the principal receives richer feedback, 1 remains valid and can be implemented by reconstructing the weaker bandit feedback.

3.1.0.3 Opposing bids

We consider two possibilities regarding the process generating the opposing bids \(\left ( \boldsymbol{\beta}^t \right )_{t\in [T]}\). Either the opposing bids are adversarial, or they are stochastic. We describe below these two settings as well as the two notions of regret, a common benchmark in online learning, which correspond to the settings.

• The opposing bids are stochastic. This setting is defined by \(\mathcal{D}\), a distribution from which, for each timestep \(t \in [T]\), the opposing bids \(\boldsymbol{\beta}^t\) are sampled.

• The opposing bids are adversarial. In this case, the opposing bids \((\boldsymbol{\beta}^t)_{t \in [T]}\) can be any fixed sequence.

Notice that the stochastic setting is a special case of the adversarial one. The purpose of having these two separate settings is to be able to provide stronger results in the stochastic setting.

3.1.0.4 Regret

It is common in online learning literature to quantify the quality of a learning algorithm by its regret: the difference between the cumulative utility received and the one generated by the best bid in hindsight. We define it below: \[R_T = \sup_{\mathbf{b}\in B}{\mathbb{E}} \left [ \sum_{t=1}^T u(\mathbf{b},\boldsymbol{\beta}^t) - \sum_{t=1}^T u(\mathbf{b}^t,\boldsymbol{\beta}^t) \right ]\]

In the stochastic setting, the pseudo-regret is a similar benchmark which takes into account the random nature of the rewards: \[\tilde{R}_T = T \sup_{\mathbf{b}\in B} \underset{ \boldsymbol{\beta}\sim \mathcal{D}}{\mathbb{E}} \left [ u(\mathbf{b}, \boldsymbol{\beta}) \right ] - {\mathbb{E}} \left [ \sum_{t=1}^T u(\mathbf{b}^t, \boldsymbol{\beta}^t) \right ]\]

3.2 Proposed algorithm↩︎

We describe in this section the algorithm we propose to solve the regret minimization problem introduced above, by first explaining how the bidding problem faced by the principal maps to a combinatorial semi-bandit model, then stating the chosen algorithm and its regret guarantees, and finally discussing how to compute its key minimization step efficiently. Our mapping to combinatorial semi-bandits builds upon insights from both [5] and [6], which study the same type of multi-unit auction 3.1 in a repeated setting. We combine this structural insight with the online learning algorithm from [19], which adapts to both stochastic and adversarial instances.

Using the results from Lemma 1 and Lemma 3 in [6] allows us to transform our bidding space \(\mathcal{B}\) into \(\mathcal{H} \subseteq \{0,1\}^N\) (with a one-to-one correspondence between \(\mathcal{B}\) and \(\mathcal{H}\)). We can also rewrite the utility as follows:\[u(\mathbf{b},\boldsymbol{\beta}) = \mathbf{h} (\mathbf{b}) \mathbf{W}(\boldsymbol{\beta})\]

We provide a quick summary of how \(\mathbf{h}(\cdot)\) and \(\mathbf{W}(\boldsymbol{\beta})\) are defined in the appendix, 6.3.

This rewriting of the action space and utility matches the combinatorial semi-bandits framework presented in [19], allowing us to leverage their Best-of-Both-Worlds algorithm’s results. The algorithm is detailed in 1 and uses the following regularizer, parameterized by \(\gamma \in (0,1]\): \[\label{def32:32regularizer} \Psi_{\gamma} (x) := \sum_{i=1}^N - \sqrt{x_i} + \gamma \left ( 1- x_i \right ) \log \left ( 1- x_i \right )\tag{8}\]

The update in 1 is written in semi-bandit form in the transformed action space \(\mathcal{H}\). The principal observes market-level bandit feedback only, i.e., the clearing price and obtained allocation \((p_t,x^t)\). The reconstruction claim is made explicit in 1: once \(\mathbf{b}^t\) is known, active-coordinate outcomes \(y_{t,i}=h^t_iW_i(\boldsymbol{\beta}^t)\) are functions of \((\mathbf{b}^t,p_t,x^t)\) for coordinates with \(h_i^t=1\). Hence the estimator is implementable from bandit feedback in the original auction representation; richer feedback (winning bids or full \(\boldsymbol{\beta}^t\)) is optional.

We restate below a simplified version of Theorem 2 from [19], whose guarantees extend to our setting:

3.2.0.1 Computing the minimum efficiently

The previous theorem ensures the good performance of 1 according to our benchmark. Since our goal is to produce a working algorithm with a real application in mind, we now discuss the implementability of the minimization step in [eq32:32algorithm32compute32min].

In our setting, this step amounts to solving a constrained convex optimization problem on \(\mathrm{Conv}(\mathcal{H})\). We use a conditional gradient (Frank–Wolfe) procedure, because the feasible set is a polytope with a simple combinatorial structure and the corresponding linear minimization oracle is tractable: each oracle call reduces to selecting an extreme point in \(\mathcal{H}\), which can be formulated as a maximum-weight path problem in a directed acyclic graph.

Put simply, the optimization step is tractable in practice: with our current implementation, in the FCR setting we can run the method for all required values up to \(K=500\) at the target precision in less than one minute per iteration.

4 Numerical Study↩︎

Finally, we apply the algorithm we designed to bid in FCR markets. We conduct two types of numerical study: one on synthetic data and one on real data from the FCR market. The complete code used to conduct this analysis is made available as supplementary material attached to this work, and FCR data is accessible at [18].

To evaluate our algorithm fairly, we compare it to an EXP3-based algorithm developed in [6]. This is a common no-regret baseline and is used in similar settings by [11].

4.1 Synthetic data↩︎

In order to fully assess the behaviour of the algorithm we developed, we conduct synthetic tests to compare 1 with the EXP3 baseline. As mentioned above, the algorithm we developed benefits from asymptotic theoretical performance guarantees (and as such may hide large constants in \(\mathcal{O}\) notation). These tests complement asymptotic results by examining empirical short-term behaviour and by serving as implementation sanity checks. In these synthetic experiments, we use \(K=4\) units and a bid discretization step of \(0.1\). These two choices keep the action space relatively small and computation time low.

2 (a) reports pseudo-regret trajectories in the synthetic setting for BOB and EXP3 over \(10{,}000\) rounds, both receiving bandit feedback and facing uniformly distributed opposing bids. The figure also shows the reference curves \(\sqrt{t}\) and \(\log(t)\) to compare empirical growth with theoretical rates. The curves are averages over repeated runs, and the colored areas represent \(95\%\) intervals (from the \(2.5\%\) to the \(97.5\%\) quantiles). In this experiment, both algorithms remain below their corresponding reference scales, which is consistent with the expected qualitative behaviour.

We also provide synthetic result of pseudo regret of both learning, under the richer full information feedback (when all opposing bids \(\boldsymbol{\beta}^t\) are revealed) in 2 (b), with the same experimental setting. As expected under this more informative setting, both algorithms drastically improve the incurred pseudo-regret, while our improved 1 still outperforms EXP3 algorithms. Overall, the synthetic study validates expected scaling and implementation behaviour, while the next subsection tests performance under realistic market conditions.

4.2 FCR market Data↩︎

We now focus on using historical data in order to quantify how 1 performs.

4.2.0.1 Experimental setup.

We study repeated bidding in the European FCR capacity market from the point of view of one French flexibility provider. The analysis is based on public clearing data (offers, demand, and market outcomes) from July 1, 2020 to May 31, 2024. As in the market design itself, we treat the six 4-hour products (NEGPOS_00_04, 04_08, 08_12, 12_16, 16_20, 20_24) as distinct auction environments. This is important in practice, because observed price levels and variability differ substantially across products, and pooling them would mix structural intraday effects with the learning dynamics we want to measure.

Full implementation details are provided in the released code and reproducibility material, available as supplementary material, attached to this work.

The learning protocol is online and therefore fully chronological. At each auction date, the learner submits a bid, observes market-level bandit feedback (clearing price and awarded quantity), reconstructs the coordinate-level outcomes required by 1 through the \(B \leftrightarrow \mathcal{H}\) reformulation, and updates before the next auction. This matches the feedback model used in our theoretical guarantees. We compare BOB and EXP3 on exactly the same product-specific auction streams, with the same marginal costs of production, action discretization, and time horizon. For each product and each algorithm, we perform 102 Monte Carlo runs (with non-fixed seeds), and define regret against the best fixed bid in hindsight on the same evaluation window.

3 shows the regret incurred by the algorithms in our counterfactual experiments (backtesting). For this test, the learner is subjected to fully realistic conditions: it has no access to future data, and no data were used beforehand to train or calibrate it. Since the compared algorithms are stochastic, experiments were repeated to assess empirical averages and distributional behaviour of regret. The figure shows both the mean and the \(2.5\)–\(97.5\%\) quantiles.

These experiments show that BOB incurs lower regret on the illustrated products, outperforming the EXP3 baseline in those settings.

4.3 Non-stationarity↩︎

As shown in 4 (b), these positive results need to be tempered: we obtain drastically different results for the “day” products (08h–12h and 12h–16h). In these cases, while BOB behaves similarly, the regret incurred by the EXP3-based algorithms varies widely, with a significant probability of obtaining negative regret.

This behaviour is straightforward to interpret: it is consistent with stronger non-stationarity in opposing bids. For regret to become negative, submitted bids must, on average, outperform the best fixed bid in hindsight; this may happen when regime shifts change the best response over time. Since BOB is designed to exploit stochastic stability, it may fail to capture these shifts as effectively as more robust EXP3-type algorithms.

5 Conclusion↩︎

This paper addresses the following question: how should a flexibility provider price its offers in the FCR market when competitors’ bids are unknown? We first provide a detailed model of the market-clearing rules and then focus on the point of view of a single participant. Under mild assumptions, this reduces the bidding problem to a uniform-price auction, a simpler setting with a well-understood online learning structure.

Building on this reduction, we formulate bidding against unknown opposing bids as an online learning problem and adapt Best-of-Both-Worlds algorithms to the FCR setting. The resulting procedure uses only market-level bandit feedback (allocation and clearing price), relies on induced semi-bandit observations in the reformulated action space, and yields regret guarantees of \(\mathcal{O}(\log T)\) in stochastic environments and \(\mathcal{O}(\sqrt{T})\) in adversarial environments. The optimization step admits a tractable conditional-gradient implementation through an efficient linear minimization oracle on \(\mathcal{H}\). In both synthetic experiments and backtests on real FCR data, these guarantees translate into competitive empirical performance.

From an operational perspective, the evidence supports a product-dependent policy. BOB is a strong default on products with more stable bid distributions, which in our data typically correspond to night/base-load-like periods. For products with stronger non-stationarity, notably day products, EXP3-type methods can be safer and may even outperform BOB by adapting better to regime shifts. In practice, this motivates an adaptive deployment strategy: select the learner by product and revise that choice over time as market stability changes.

Several extensions would broaden applicability. A natural next step is to handle participants active in multiple countries and account for interconnection constraints directly in the learning loop. Another is to include contextual covariates (e.g., plant availability, weather, or seasonality) to move beyond stationary product-level models. It would also be valuable to study strategic interactions when several participants learn simultaneously, and to test whether the same reduction-and-learning approach extends to other reserve or energy market mechanisms.

Acknowledgement↩︎

Marius Potfer acknowledges the support of ANR through the PEPR IA FOUNDRY project (ANR- 23-PEIA-0003) and the Doom project (ANR-23-CE23-0002), as well as the ERC through the Ocean project (ERC-2022-SYG-OCEAN-101071601). Pierre Gruet and Cheng Wan acknowledge support from the FiME Lab.

6 Appendix↩︎

6.1 Some characteristic lemma of the FCR clearing↩︎

The following lemma formalizes the (local) stability property of the FCR clearing that we use in the proof sketch of the market/auction equivalence: changing only the last accepted bid of bidder \(j\) (making it lower) or only the first rejected bid (making it higher) cannot change bidder \(j\)’s allocation.

6.2 Equivalence with uniform price auction↩︎

To fully prove the equivalence result, we first restate how the uniform price auction mechanism is defined:

6.2.0.1 Uniform Price auction

We describe below in detail the uniform price auction mentioned above, where \(D_{max,s}\) units are to be bought. We describe this auction from the point of view of the flexibility provider, whose cost of producing the \(\text{k}^\text{th}\)-unit of electricity is denoted by \(c_{k}\in [0,1]\), against opposing bids \(\boldsymbol{\beta}\). The auction proceeds as follows:

1. The principal submits its bids \(\mathbf{b}_j :=(b_{j,k})_{k\in[K]} \in B\), where \(K=D_{max,s}\) and \(B=\{(b_l)_{l \in [K]} \in \mathcal{B}^{D_{max,s}}, \text{ such that } 0 \leq b_{1}\leq b_{2} \leq \ldots \leq b_{K} \leq1 \}\).

2. The opposing bids \(\boldsymbol{\beta}= (\beta_k)_{k \in [K]} \in B\) (in non-decreasing order)⁴ are submitted to the auction.

3. The per-unit price is set as the \(D_{max,s}^\text{th}\) lowest bid from \((\mathbf{b}_j,\boldsymbol{\beta})\), denoted by \(p^{\mathrm U} \left(\mathbf{b}_j, \boldsymbol{\beta}\right)\).

4. The principal sells to the auctioneer every unit of flexibility they proposed below the price \(p^{\mathrm U} \left( \mathbf{b}_j,\boldsymbol{\beta}\right)\) and receives this price in exchange. Their allocation \(x^{\mathrm U}\in[K]\) of production is therefore as follows⁵: \[\begin{align} x^{\mathrm U}\left (\mathbf{b}_j,\boldsymbol{\beta}\right ) & := \left \lvert \left \{k \in [K] \text{ s.t. } b_{j,k} \leq p^{\mathrm U} \left ( \mathbf{b}_j,\boldsymbol{\beta}\right ) \right \} \right \rvert .\addtocounter{equation}{1}\label{app:def:allocation-elec-market} \end{align}\tag{9}\]

Before providing the complete proof, to ensure clarity, we restate the theorem.

6.3 Rewriting the utility↩︎

The point of this section is to restate/make the link to the correct notation with Lemma 1 and Lemma 3 from [6]. This shows that the utility can be rewritten as a dot product between two vectors: \(\mathbf{h}\) and \(\mathbf{W}\), each depending either on \(\mathbf{b}\) or \(\boldsymbol{\beta}\).

We begin by recalling how the utility is traditionally written in a uniform-price auction. In this section, since we focus on uniform auctions, we use \(x(.)\) instead of \(x^{\mathrm U} (.)\) and \(p(.)\) instead of \(p^{\mathrm U} (.)\).

\[u(\mathbf{b},\boldsymbol{\beta}) = \sum_{l=1}^{x(\mathbf{b},\boldsymbol{\beta})} \left [ p(\mathbf{b},\boldsymbol{\beta}) -c_l \right ]\]

We then move to writing this in a similar fashion as in [6], by using indicator functions, denoted \(\ifthenelse{ \equal{}{} } {\mathbb{1} } {\mathbb{1} \left \{ \right \}}\). Then, we can just recall their Lemma 1 for the existence and uniqueness of \(\mathbf{h} (\mathbf{b})\) and their Lemma 3 to write the following formula for \(\mathbf{W}(\boldsymbol{\beta})\).

Let \(N:=\frac{2K}{\varepsilon}\) and \(\mathbf{W}(\boldsymbol{\beta}):=(w_k(\boldsymbol{\beta}))_{k=1}^{N}\). For each coordinate \(k\in[N]\), define \[m_k:=\left \lfloor \frac{k}{2\varepsilon} \right \rfloor,\qquad q_k:=\left(\frac{k}{2\varepsilon}-m_k\right)\varepsilon.\] Then \[w_k(\boldsymbol{\beta}):= \begin{cases} \sum_{l=1}^{m_k}\left(\beta_{K-m_k}-c_l\right) & \text{if } \lfloor \frac{k}{\varepsilon} \rfloor \text{ is odd and } q_k=\beta_{K-m_k},\\ \sum_{l=1}^{m_k}\left(q_k-c_l\right) & \text{if } \lfloor \frac{k}{\varepsilon} \rfloor \text{ is even and } \beta_{K-m_k}<q_k<\beta_{K-m_k+1},\\ 0 & \text{otherwise.} \end{cases}\] For boundary indices, we use the convention \(\beta_0:=0\) and \(\beta_{K+1}:=1\).

As for \(\mathbf{h} (\mathbf{b})\), instead of indexing it directly as a 1D vector, the mapping is based on a flattened 2D matrix, defined by binary variables that track the structural properties of the bid sequence across items and price levels. Let \(\mathcal{K} = \{1, \frac{3}{2}, 2, \dots, K - \frac{1}{2}, K\}\) be the set of item indices including half-steps.

We now define these indicators without ambiguity. Let the price grid be \[\mathcal{J}_\varepsilon := \{0,\varepsilon,2\varepsilon,\dots,1\}.\] For any unit index \(k\in[K]\) and any grid value \(q\in\mathcal{J}_\varepsilon\), define \[h_{k,q}(\mathbf{b}):= \ifthenelse{ \equal{}{} } {\mathbb{1} } {\mathbb{1} \left \{ \right \}} \{b_{k}=q\}.\] For any \(k\in[K-1]\) and any grid value \(q\in\mathcal{J}_\varepsilon\setminus\{1\}\), define the half-step indicators \[h_{k+\frac{1}{2},q}(\mathbf{b}):= \ifthenelse{ \equal{}{} } {\mathbb{1} } {\mathbb{1} \left \{ \right \}} \{b_{k}<q< q +\varepsilon \le b_{k+1}\}.\] This interval condition records the price grid transition crossed between consecutive bids.

Finally, to compute the linear utility \[u(\mathbf{b},\boldsymbol{\beta})=\mathbf{h}(\mathbf{b})^\top\mathbf{W}(\boldsymbol{\beta}),\] the pseudo-bid vector \(\mathbf{h}(\mathbf{b})\in\{0,1\}^{N+ K -\frac{1}{\epsilon}}\) is obtained by flattening the family \[\{h_{k,q}(\mathbf{b}):k\in[K],q\in\mathcal{J}_\varepsilon\}\cup\{h_{k+\frac{1}{2},q}(\mathbf{b}):k\in[K-1],q\in\mathcal{J}_\varepsilon\setminus\{1\}\}\] in lexicographic order (first by \(k\in\mathcal{K}\), then by decreasing \(q\)).

References↩︎

---

1. We take \(\boldsymbol{\beta}\in B\), this is without loss of generality : if \(\boldsymbol{\beta}\) has more than \(D_{max,s}\) elements then, when only keeping the \(D_{max,s}\) the auction results remain the same regardless of \(\mathbf{b}_j\)↩︎

2. This allocation breaks ties in favor of the flexibility provider for simplicity; our results still follow through if tie-breaking is random or always against the principal.↩︎

3. The same argument is unchanged for any deterministic tie-breaking rule fixed ex ante and independent of the local bid perturbation applied to bidder \(j\).↩︎

4. We take \(\boldsymbol{\beta}\in B\), this is without loss of generality : if \(\boldsymbol{\beta}\) has more than \(D_{max,s}\) elements then, when only keeping the \(D_{max,s}\) the auction results remain the same regardless of \(\mathbf{b}_j\)↩︎

5. This allocation breaks ties in favor of the flexibility provider for simplicity; our results still follow through if tie-breaking is random or always against the principal.↩︎