Scenario-based decision-making for power systems
investment planning
Jialin Liu1,2 and Olivier Teytaud1,3

arXiv:1607.01313v1 [cs.GT] 5 Jul 2016

1

Inria TAO, LRI, UMR 8623 (CNRS - Univ. Paris-Saclay), Gif-sur-Yvette, France
2
CSEE, University of Essex, Colchester, United Kingdom
3
Google, Zürich, Switzerland
jialin.liu@essex.ac.uk

Abstract—The optimization of power systems involves complex
uncertainties, such as technological progress, political context,
geopolitical constraints. Negotiations at COP21 are complicated
by the huge number of scenarios that various people want
to consider; these scenarios correspond to many uncertainties.
These uncertainties are difficult to modelize as probabilities, due
to the lack of data for future technologies and due to partially
adversarial geopolitical decision makers. Tools for such difficult
decision making problems include Wald and Savage criteria,
possibilistic reasoning and Nash equilibria. We investigate the
rationale behind the use of a two-player Nash equilibrium approach in such a difficult context; we show that the computational
cost is indeed smaller than for simpler criteria. Moreover, it
naturally provides a selection of decisions and scenarios, and
it has a natural interpretation in the sense that Nature does
not make decisions taking into account our own decisions. The
algorithm naturally provides a matrix of results, namely the
matrix of outcomes in the most interesting decisions and for the
most critical scenarios. These decisions and scenarios are also
equipped with a ranking.

I. I NTRODUCTION :

DECISION MAKING IN UNCERTAIN

ENVIRONMENTS

Planning in power systems relies on many uncertainties.
Some of them, originating in nature or in consumption, can
be tackled through probabilities (Pinson, 2013; RTE-ft, 2008;
Siqueira et al., 2006; Vassena et al., 2003); others, such as
technology evolution, geopolitics or CO2 penalization laws,
are somewhere between stochastic and adversarial:
Climate: The United Nations Climate Change Conference,
COP21, aims at achieving a new universal agreement on
climate agreement, which is an issue of cooperation and
competition.
Uranium supply: India has been using imported enriched
uranium from Russia since 2001. In 2004, Russia deferred to
the Nuclear Suppliers’ Group and declined to supply further
uranium for India’s reactors. The uranium supply was not
resumed until the end of 2008 (after the refurbishment was
finished). Now, Russia is already supplying the India’s first
large nuclear power plant under a Russian-financed 3 billion
contract; and in 2014, Russia agreed to help building 10
nuclear reactors in India.
Curtailment risk: Wind and solar curtailment may occur
for several reasons including transmission congestion (or local network constraints), global oversupply and operational

issues (Lew et al., 2013). Each type of curtailment occurs
with different frequencies depending on the generation and
electrical characteristics of the regional and local systems.
Another example is the risk of terrorism in the congested
traffic, which cannot be represented by any stochastic model.
Geopolitical implications: Affected by the dollar, geopolitical and other factors, at the beginning of 2008 the international crude oil prices rose sharply. Another example is the
Ukraine Crisis, which made Europe consider seriously adjusting its energy policy to reduce its dependence on imported
energy supply.
Handling such uncertainties is a challenge. For example,
how should we modelize the risk of gas curtailment in Europe,
and the evolution of oil prices ? We discuss existing methodologies in Section II. Section III compares them. Section IV
describes our proposed approach. In particular, Section IV-C
summarizes our method. Experiments are provided in Section
V. Section VI concludes.
II. S TATE OF

THE ART: DECISION WITH UNCERTAINTIES

The notations are as follows: K is the number of possible
policies. S is the number of possible scenarios. R is the
matrix of rewards and the associated reward function (Rk,s =
R(k, s)), i.e. R(k, s) is the reward when applying policy k ∈
K = {1, . . . , K} in case the outcome of uncertainties is s ∈
S = {1, . . . , S}. The reward function is also called a utility
function or a payoff function. A strategy (a.k.a. policy) is a
random variable k with values in K. A mixed strategy is a
probability distribution of possible policies; this is the general
case of a strategy. A pure strategy is a deterministic policy, i.e.
it is a mixed strategy with probability 1 for one element, others
having probability 0. The exploitability of a (deterministic or
randomized) strategy k is


′
′
max
min
E
R(k
,
s)
− min Ek R(k, s).
k
′
k stochastic s∈{1,...,S}

s∈{1,...,S}

(1)
We refer to the choice of s as Nature’s choice. This does
not mean that only natural effects are involved; geopolitics
and technological uncertainties are included. k is chosen by
us. In fact, natural phenomena can usually be modelized with
probabilities, and are included through random perturbations

- they are not the point in this work - contrarily to climate
change uncertainties.
A. Scenario-based planning
Maybe the most usual solution consists in selecting a small
set s1 , . . . , sM of possible s, assumed to be most realistic.
Then, for each sj , an optimal ki is obtained. The human
then checks the matrix of the R(ki , sj ) for i and j in
{1, . . . , M }. Variants of this approach are studied in scenario planning (Chaudry et al., 2014; Saisirirat et al., 2013;
Schwartz, 1996). Feng (2014) provides examples with more
than 1000 scenarios. When optimizing the transmission network, we must take into account the future installation of
power plants, for which there are many possible scenarios in particular, the durations involved in power plant building
are not necessarily larger than constants involved in big
transmission lines. The scenarios involving large wind farms,
or large nuclear power plants, lead to very specific constraints
depending on their capacities and locations.
B. Wald criterion
The Wald criterion(Wald, 1939) consists in optimizing in the
worst case scenario. For a maximization problem, the Waldvalue is
v=
k

max
pure strategy on

min

{1,...,K} s∈{1,...,S}

Rk,s ,

(2)

C. Savage criterion
The Savage-value(Savage, 1951) is:
k

min
max regret(k, s),
pure strategy on K s∈S

The principle of the Nash equilibrium is that contrarily to
what is assumed in Wald’s criterion (Eq. 2), there is no reason
for Nature (the opponent) to make a decision after us, and to
know what we have decided. The Nash-value v is
v=
k

max
mixed strategy on

min Ek R(k, s).

K s∈S

As a mixed strategy is used, the fact that the maximum is
written before the min does not change the result (v. Neumann,
1928); v is also equal to
min − max Ek R(k, s).
r.v. on S
k
where r.v. stands for “random variable”. The exploitability (Eq.
1) of a (possibly mixed) strategy k is equivalent to
s

Nash-value − min Ek R(k, s).
s∈S

A Nash strategy is a strategy with exploitability equal to 0.
A Nash strategy always exists; it is not necessarily unique. A
Nash equilibrium, for a finite-sum problem, is a pair of Nash
strategies for us and for Nature respectively. In the general
case, a Nash strategy is not pure. Criteria for Nash equilibria
corresponds to Nature and us making decision privately, i.e.
without knowing what each other will do. In this sense, it is
more intuitive than other criteria.
E. Other decision tools

and the recommended policy is k realizing the max. We
choose a policy which provides the best solution (maximal reward) for the worst scenario. Wald’s maximin model provides
a reward which is guaranteed in all cases. Implicitly, it assumes
that Nature will make its decision in order to bother us, and,
in a more subtle manner, Nature will make its decision while
knowing what we are going to decide. It is hard to believe, for
example, that the ultimate technological limit of photovoltaic
units will be worse if we decide to do massive investments in
solar power. Therefore, Wald’s criterion is too conservative in
many cases; hence the design of the Savage criterion.

v=

D. Nash equilibria

(3)

where regret(k, s) = max
(Rk′ ,s − Rk,s ). The Savage critek′ ∈K
rion is an application of the Wald maximin model to the regret.
Contrarily to Wald’s criterion, it does not focus on the worst
scenario. Its interpretation is that we optimize the guaranteed
loss compared to an anticipative choice (anticipative in the
sense: aware of all future outcomes) of decision. On the other
hand, Nature still makes its decision after us, and has access
to our decision before making its decision - Nature, in this
model, can still decide to reduce the technological progress
of wind turbines just because we have decided to do massive
investments in wind power.

Other possible tools for partially adversarial decision making are multi-objective optimization (i.e. for each s, there is
one objective function k 7→ R(k, s)) and possibilistic reasoning (Dubois and Prade, 2012). These tools rely intensively on
human experts, a priori (selection of scenarios) or a posteriori
(selection in the Pareto set).
III. C OMPARISON

BETWEEN VARIOUS DECISION TOOLS

Let us compare the various discussed policies, where K is
the number of possible investment policies, S is the number
of scenarios, K ′ is the number of displayed policies, S ′ is
the number of displayed policies; we provide an overview in
Table I. We see that the Nash approach (at least with the
algorithms reaching the bound mentioned in the table) has
a lower computational cost and some advantages in terms of
modeling; Nature makes its decision privately (which means
we do not know the uncertainties), but not with access to our
decisions. On the other hand, its output is stochastic, which
might be a drawback for users.
IV. O UR PROPOSAL : NASH U NCERTAINTY D ECISION
Our proposed tool is as follows: (i) We use Nash equilibria,
for their principled nature and (as discussed later) low computational cost in large scale settings. (ii) We compute the
equilibria thanks to adversarial bandit algorithms, as detailed
in the next section. (iii) We use sparsity, for (i) improving the
precision (ii) reducing the number of pure strategies in our
recommendation. The resulting algorithm has the following
advantage:

TABLE I: Comparison between several tools for decision under uncertainty.
METHOD

EXTRACTION
OF POLICIES

EXTRACTION
OF CRITICAL
SCENARIOS

COMPUTATIONAL
COST

Wald

One

One per policy

K×S

Savage

One

One per policy

K×S

Nash

Nash-optimal

Nash-optimal

(K + S) × log(K + S)

Scenarios

Handcrafted

Handcrafted

K ′ × S′

It is fast; this is not intuitive, but Nash equilibria, in
spite of the complex theories behind this concept, can
be approximated quickly, without computing the entire
matrix of R(k, s). A pioneering work in this direction
was Grigoriadis and Khachiyan (1995); within logarithmic terms and dependency in the precision, the cost is
roughly the square root of the size of the matrix.
• It naturally provides a submatrix of R(k, s), for the best
k and the most critical s.
We believe that such outcomes are natural tools for including
in platforms for simulating large scale power systems involving huge uncertainties.
•

A. The algorithmic technology under the hood: computing
Nash equilibria with adversarial bandit algorithms
For the computational cost issue for computing Nash
equilibria, there exist algorithms reaching approximate solutions much faster than the exact linear programming approach (von Stengel, 2002). Some of these fast algorithms
are based on the bandit formalism. The Multi-Armed Bandit
(MAB) problem (Auer et al., 1995; Katehakis and Veinott Jr,
1987; Lai and Robbins, 1985) is a model of exploration/exploitation trade-offs, aimed at optimizing the expected
payoff. Let us define an adversarial multi-armed bandit with
K ∈ N+ (K > 1) arms and let K denote the set of arms. Let
T = {1, . . . , T } denote the set of time steps, with T ∈ N+
a finite time horizon. At each time step t ∈ T , the algorithm
chooses it ∈ K and obtains a reward Rit ,t . The reward Rit ,t
is a mapping (K, T ) 7→ R.
The generic adversarial bandit is detailed in Algorithm 1. In
Algorithm 1 Generic adversarial multi-armed bandit. The
problem is described through the arm sets, the budget T , and
most importantly the get reward method, i.e. the mapping
(K, T ) 7→ R.

Require: a time horizon (computational budget) T ∈ N+
Require: a set of arms K
Require: a probability distribution π on K
1: for t ← 1 to T do
2:
Select arm it ∈ K based upon π
3:
Get reward Rit ,t
4:
Update the probability distribution π using Rit ,t .
5: end for

the case of adversarial problems, when we search for a Nash
equilibrium for a reward function (k, s) 7→ R(k, s), two bandit
algorithms typically play against each other. One of them is
Nature, and the other plays our role. At the end, our bandit

INTERPRETATION

Nature decides later,
minimizing our reward.
Nature decides later,
maximizing our regret.
Nature decides
privately, before us.
Human expertise

algorithm recommends a (possibly mixed) strategy over the
K arms. This recommended distribution is often the empirical
distribution of play during the games against the Nature bandit.
Such a fast approximate solution can be provided
by Exp3 (Exponential weights for Exploration and Exploitation) (Auer et al., 2002a) and its Exp3.P variant (Auer et al., 2002b), presented in Algorithm 2. Exp3
has the same efficiency as the Grigoriadis and Khachiyan
method (Grigoriadis and Khachiyan, 1995) for finding approximate Nash equilibria, and can be implemented with two
bandits playing one against each other, e.g. one for us and
one for Nature. Exp3.P is not anytime: it requires the time
horizon in order to initialize some input meta-parameters.
Busa-Fekete et al. (2010) optimized Adaptive Boosting (AdAlgorithm 2 Exp3.P : variant of Exp3, proved to have a
high probability bound on the weak reward. η and γ are two
parameters.
Require: η ∈ R
Require: γ ∈ (0, 1]
Require: a time horizon (computational budget) T ∈ N+
Require: K ∈ N+ is the number of arms
1: y ← 0
2: for i ← 1 to K doq
T
3:
ωi ← exp( ηγ
3
K)
4: end for
5: for t ← 1 to T do
6:
for i ← 1 to K do
ω
γ
7:
pi ← (1 − γ) PK i
+ K
j=1

⊲ initialization

ωj

8:
end for
9:
Generate it according to (p1 , p2 , . . . , pK )
10:
Compute reward Rit ,t
11:
for i ← 1 to K do
12:
if i == it then
Ri ,t
13:
R̂i ← pt
i
14:
else
15:
R̂i ← 0
16:
end if


γ
(R̂i + p √ηT K )
17:
ωi ← ωi exp 3K
i
18:
end for
19: end for
20: return probability distribution (p1 , p2 , . . . , pK )

aBoost), a popular machine-learning meta-algorithm, by the
adversarial bandit algorithm Exp3.P , and proposed two
parametrizations of the algorithm, as detailed in Table II.
Bubeck and Cesa-Bianchi (2012) proved a high probability
bound on the weak reward of Exp3.P .
B. Another ingredient under the hood: sparsity
Teytaud and Flory (2011) proposed a truncation technique
on sparse problem. Considering the Nash equilibria for two-

TABLE II: Notations and parameters of algorithms using in
the experiments. T is the horizon, i.e. simulation number. “+t”
(resp. “+p”) refers to the variant of Exp3.P or tExp3.P with
theoretical (resp. practical) parametrization. ǫ is the precision.
We use ǫ = 1e − 6 in our experiments.
NOTATION
Exp3.P + p
tExp3.P + p
Exp3.P + t
tExp3.P + t

PARAMETERS OF Exp3.P
η
γ
0.3
q
2 log

KT
ǫ

0.15
q
)
min(0.6, 2 3K log(K)
5T

player finite-sum matrix games, if the Nash equilibrium of the
problem is sparse, the small components of the solution can be
removed and the remaining submatrix is solved exactly. This
technique can be applied to some adversarial bandit algorithm
such as Grigoriadis’ algorithm (Grigoriadis and Khachiyan,
1995), Exp3 (Auer et al., 2002a) or Inf (Bubeck et al.,
2009). The properties of this sparsity technique are as follows.
Asymptotically in the computational budget, the convergence
to the Nash equilibria is preserved (Teytaud and Flory, 2011).
The computation time is lower if there exists a sparse solution (Teytaud et al., 2014). The support of the obtained
approximation has at most the same number of pure strategies and often far less (Teytaud and Flory, 2011). Essentially,
we get rid of the random exploration part of the empirical
distribution of play.
C. Overview of our method
We first give a high level view of our method, in Algorithm 3. All the algorithmic challenge is hidden in the
tExp3.P algorithm, defined later. We now present the comAlgorithm 3 The SNash (Sparse-Nash) algorithm for solving
decision under uncertainty problems.
Require: A family {1, . . . , K} of possible decisions (investment policies).
Require: A family {1, . . . , S} of scenarios.
Require: A mapping (k, s) 7→ Rk,s , providing the rewards
Run tExp3.P on the mapping R, get a probability distribution on K and a
probability distribution on S.
Output k1 , . . . , km the policies with positive probability and s1 , . . . , sp the
scenarios with positive probability. Emphasize the policy with highest probability.
Output the matrix of R(ki , sj ) for i ≤ n and j ≤ p.

putation engine tExp3.P . We apply the truncation technique (Teytaud and Flory, 2011) to Exp3.P . We present in
Algorithm 4 the resulting algorithm, denoted as tExp3.P .
V. E XPERIMENTS
We propose a simple model of investments in power systems. Our model is not supposed to be realistic; it is aimed at
being easy to reproduce.
A. Power investment problem
We
consider
each
investment
policy,
sometimes called action or decision, a vector k
=
(C, F, X, S, W, P, T, U, N, A) ∈ {0, 21 , 1}10 . A scenario
is a vector s = (Z, W B, P B, T B, XB, U B, SB, CC, N T ) ∈
{0, 12 , 1}9 . Detailed descriptions of parameters are provided
in Tables IIIa and IIIb.

Algorithm 4 tExp3.P , combining Exp3.P and the truncation
method. α is the truncation parameter.
Require: Rm×n , matrix defined by mapping (i, j) 7→ Ri,j
Require: a time horizon (computational budget) T ∈ N+
Require: α, truncation parameter
1: Run Exp3.P during T iterations; get an approximation (p, q) of the Nash
equilibrium
(T pi )α
⊲ compute the threshold for p
2: ζ =
max
T
i∈{1,...,m}

3: for i ← 1 to m do
4:
if pi ≥ ζ then
5:
p′i = pi
6:
else
7:
p′i = 0
8:
end if
9: end for
10: for i ← 1 to m′ do
p
Pm i ′
11:
p′′
i =
p
j=1

12: end for
13: ζ ′ = max

i∈{1,...,n}

⊲ Truncation

j

(T qi )α
T

⊲ compute the threshold for q

14: for i ← 1 to n do
15:
if qi ≥ ζ ′ then
16:
qi′ = qi
17:
else
18:
qi′ = 0
19:
end if
20: end for
21: for i ← 1 to n′ do
q
22:
qi′′ = Pn i q′
j=1

⊲ Truncation

j

23: end for
24: return p′′ and q′′ as an approximate Nash equilibrium of the problem

Let S be the set of possible scenarios and K be the set
of possible policies. The utility function R is a mapping
(K, S) 7→ R. Given decision k ∈ K and scenario s ∈ S, a
reward can be computed by
2
R(k, s) = (1 + rand) · (N (1 − Z)/5
3
− cost · (N + U + T + P + W + S + X + F + C)
√
+ 7XB · X + W (1 + W B)(SB + S)/2
+ 3P (P B + SB) − 4C · CC − F · N T
+ S(1 − Z) + P · Z + U · U B
+ T · S · (1 + T B − SB/2)

− F · N T + A · (1 + W + P − 2SB)).

where cost is a meta-parameter. This provides a reward function R(k, s), with which we can build a matrix R of rewards.
However, with a ternary discretization for each variable we get
a huge matrix, that we will not construct explicitly - more precisely, it would be impossible to construct it explicitly with a
real problem involving hours of computation for each R(k, s).
Fortunately, approximate algorithms can solve Nash equilibria
with precision ǫ with O(K log(K)/ǫ2 ) requests to the reward
function, i.e. far less than the quadratic computation time K 2
needed for reading all entries in the matrix. We do experiments
on this investment problem and apply the algorithms described
in Table II. We consider policies and scenarios in discrete
domains: K = {0, 21 , 1}10 , S = {0, 21 , 1}9 . The reward
matrix R310 ×39 can be defined by ∀i ∈ {1, . . . , 310 }, ∀j ∈
{1, . . . , 39 }, Ri,j = R(ki , sj ), but the reward is noisy as
previously mentioned, where ki denotes the ith policy in K
and si denotes the j th scenario in S. Thus, each line of the

matrix is a possible policy and each column is a scenario, Ri,j
is the reward obtained by apply the policy ki to the scenario
sj . Experiments are performed for different numbers of time
steps in the bandit algorithms, i.e. we consider T simulations
for each T ∈ {1, 2, 8, 10, 32, 128, 512, 2048}×⌈310/10⌉. Thus
when playing with the “theoretical” parametrization, for each
T , the input meta-parameters η and γ are different, as they
depend on the budget T . In the entire paper, when we show
an expected reward R(k, s) for some s and for k learned
by one of our methods, we refer to 10000 trials; R(k, s)
are played for 10000 randomly drawn pairs (kin , sjn ) i.i.d.
according to the random variables in and jn proposed by the
considered policies. The performance is the average reward of
these 10000 trials R(ki1 , sj1 ), . . . , R(ki10000 , sj10000 ). There is
an additional averaging, over learning. Namely, each learning
(i.e. the sequence of Exp3 iteration for approximating a Nash
equilibrium) is repeated 100 times. The meta-parameter cost
is set to 1 in our experiments.
We use the parametrizations of variants of Exp3.P
presented in Table II. Teytaud and Flory (2011) proposed
α = 0.7 as truncation parameter in truncated Exp3.P and
Teytaud et al. (2014) used the same value. The sparsity level,
as well as the performance, are given in Table IV. We validate
the good performance of α = 0.7. However, the sparsity
is better with higher values - but these higher values do
not always provide better results than the original non-sparse
bandit.
We observe that when the number of simulations is bigger
than the cardinality of the search domain, i.e. the number of
possible pure policies, then α ≃ 0.9 leads to better empirical
mean reward against the uniform policy. Values between 0.5
and 1 are the best ones. When learning with few simulations
(5905 = ⌈K/10⌉), the non-truncated solutions and non-sparse
solutions are as weak as a random strategy. Along with the
increment of simulation times, the non-truncated solutions and
non-sparse solutions become stronger, but still weaker than
the truncated solutions. When we use the truncation, we get
significant mean reward even with a small horizon, i.e. the
tExp3.P + t succeeds in finding better and “purer’ policies
than Exp.3.
1) The parameters of Exp3.P +t: When learning with few
simulations (5905 = ⌈K/10⌉), the non-truncated solutions and
non-sparse solutions are as weak as a random strategy. Along
with the increment of simulation times, the non-truncated
solutions and non-sparse solutions become stronger, but still
weaker than the truncated solutions. Sparsity level “0.01”
means that one and only one solution of the 100 learnings has
one element above the threshold ζ, the other 99 solutions of
the 99 learnings have no element above the threshold ζ. This
situation is not far from the non-truncated or non-sparse case.
If the solution is sparse, we get a better empirical mean reward
even with a small horizon, i.e. the tExp3.P + t succeeds in
finding better pure policies.
We see that truncated algorithms outperform their nontruncated counterparts, in particular, truncation clearly shows
its strength when the number of simulations is small in front

of the size of search domain.
B. A modified power investment problem
Now we modify the reward function as follows:
R′ (k, s) =R(k, s) + c · ((X == XB)

+(C = CC) + (NT = F) + (P == PB)).

where cost and c are meta-parameters.
As presented in the previous section, we can build a matrix
R′ with the reward function R′ (k, s). We do experiments on
this modified investment problem and apply the algorithms
described in Table II. We consider policies and scenarios in
discrete domains as used in the previous section. The metaparameters cost is set to 1 and c is set to {1, 2, . . . , 10}
in our experiments. The reward matrix is normalized in the
experiments.
We present the results with c = 1 and c = 10 in Tables
V and VI: in both testcases, α = 0.9 does not provide good
results when T = K, however α = 0.7 (recommended by
previous works) is always better than the baseline, to which
the truncation technique is not applied; for the testcase with
c = 1, α = 0.9 outperforms the other values of α at most of
time; when the budget is big, α = 0.99 provides better results.
VI. C ONCLUSION : NASH - METHODS

HAVE

COMPUTATIONAL AND MODELING ADVANTAGES FOR
DECISION MAKING UNDER UNCERTAINTIES

We propose a new criterion (based on Nash equilibria)
and a new methodology (based on adversarial bandits + sparsity) for decision making with uncertainty. Technically speaking, we tuned a parameter-free adversarial bandit algorithm
tExp3.P + t, for large scale problems, efficient in terms of
performance itself, and also in terms of sparsity. tExp3.P + t
performed better than tExp3.P without truncation. Moreover,
tExp3.P + t with truncation parameter α = 0.7, which is
theoretically guaranteed (Teytaud and Flory, 2011), got stable
performance in the experiments.
From a user point of view, we propose a tool with the
following advantages: (i) Natural extraction of interesting
policies and critical scenarios. However, we point out that
α = .7 provides stable (and proved) results, but the extracted
submatrix becomes easily readable (small enough) with larger
values of α. (ii) Faster computational cost than the Wald
or Savage classical methodologies. Our methodology only
requires a mapping R : (k, s) 7→ R(k, s), which computes
the outcome if we use the policy k and the outcome is the
scenario s. Multiple objective functions can be handled: if
we have two objectives (e.g. economy and greenhouse gas
pollution), we can just duplicate the scenarios, one for which
the criterion is economy, and one for which the criterion is
greenhouse gas. Given a problem, the algorithm will display
a matrix of rewards for different policies and for several
scenarios (including, by the trick above, several criteria such
as particular matter, greenhouse, and cost).
As a summary, we get a fast criterion, faster than Wald’s or
Savage’s criteria, with a natural interpretation. The algorithm

naturally provides a matrix of results, namely the matrix
of outcomes in the most interesting decisions and for the
most critical scenarios. These decisions and scenarios are also
equipped with a ranking.

Wind and solar curtailment. In Int. Workshop on LargeScale Integration of Wind Power Into Power Systems, pages
1–9, 2013.
Pierre Pinson. Renewable energy forecasts ought to be
probabilistic. In WIPFOR seminar, 2013.
R EFERENCES
RTE-ft. Rte forecast team: Electricity consumption in France
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E.
: Characteristics and forecast method, 2008.
Schapire. Gambling in a rigged casino: the adversarial Peerawat Saisirirat, Nuwong Chollacoop, Manida Tongroon,
multi-armed bandit problem. In Proceedings of the 36th
Yossapong Laoonual, and Jakapong Pongthanaisawan.
Annual Symposium on Foundations of Computer Science,
Scenario analysis of electric vehicle technology penetration
pages 322–331. IEEE Computer Society Press, Los Alamiin thailand: Comparisons of required electricity with
tos, CA, 1995.
power development plan and projections of fossil
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finitefuel and greenhouse gas reduction. Energy Procedia,
time analysis of the multiarmed bandit problem. Machine
34(0):459 – 470, 2013.
ISSN 1876-6102.
doi:
learning, 47(2-3):235–256, 2002a.
http://dx.doi.org/10.1016/j.egypro.2013.06.774.
URL
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E
http://www.sciencedirect.com/science/article/pii/S1876610213010175.
Schapire. The nonstochastic multiarmed bandit problem.
10th Eco-Energy and Materials Science and Engineering
SIAM Journal on Computing, 32(1):48–77, 2002b.
Symposium.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of L. Savage. The theory of statistical decision. Journal of the
stochastic and nonstochastic multi-armed bandit problems.
American Statistical Association, 46:5567, 1951.
arXiv preprint arXiv:1204.5721, 2012.
Peter Schwartz. The Art of the Long View: Paths to Strategic
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure
Insight for Yourself and Your Company. Random House,
exploration in multi-armed bandits problems. In Algorithmic
1996. ISBN 0-385-26732-0.
Learning Theory, pages 23–37. Springer, 2009.
TG Siqueira, Monica Zambelli, Marcelo Cicogna, Marinho G.
Róbert Busa-Fekete, Balázs Kégl, et al. Fast boosting using
Andrade, and Secundino M. Soares. Stochastic dynamic
adversarial bandits. In Proceedings of the 27th International
programming for long term hydrothermal scheduling conConference on Machine Learning, pages 143–150, 2010.
sidering different streamflow models. In Probabilistic
Modassar Chaudry, Nick Jenkins, Meysam Qadrdan, and
Methods Applied to Power Systems, 2006. PMAPS 2006.
Jianzhong Wu. Combined gas and electricity network
International Conference on, pages 1–6. IEEE, 2006.
expansion planning. 113(C):1171–1187, 2014. URL Olivier Teytaud and Sébastien Flory. Upper confidence trees
http://EconPapers.repec.org/RePEc:eee:appene:v:113:y:2014:i:c:p:1171-1187.
with short term partial information. In Applications of
Didier Dubois and Henri Prade. Possibility theory. In
Evolutionary Computation, pages 153–162. Springer, 2011.
Robert A. Meyers, editor, Computational Complexity, pages Olivier Teytaud, David L. Saint-Pierre, Sylvie Ruette, Jialin
2240–2252. Springer New York, 2012. ISBN 978-1Liu, and David Auger. Sparse binary zero-sum games.
4614-1799-6. doi: 10.1007/978-1-4614-1800-9 139. URL
In Asian Conference on Machine Learning, volume 29,
http://dx.doi.org/10.1007/978-1-4614-1800-9 139.
page 16, 2014.
Yonghan Feng. Scenario Generation and Reduction for Long- J. v. Neumann.
Zur theorie der gesellschaftsspiele.
term and Short-term Power System Generation Planning
Mathematische
Annalen,
100(1):295–320,
1928.
under Uncertainties. Theses, Iowa State University, 2014.
ISSN 0025-5831.
doi: 10.1007/BF01448847.
URL
Michael D. Grigoriadis and Leonid G. Khachiyan.
A
http://dx.doi.org/10.1007/BF01448847.
sublinear-time randomized approximation algorithm for ma- Stefano Vassena, Philippe Mack, P Rousseaux, C Druet, and
trix games. Operations Research Letters, 18(2):53–58, Sep
Louis Wehenkel. A probabilistic approach to power system
1995.
network planning under uncertainties. In IEEE Bologna
Michael N Katehakis and Arthur F Veinott Jr. The multiPower Tech Conference Proceedings, 2003.
armed bandit problem: decomposition and computation. Bernhard von Stengel. Computing equilibria for two-person
Mathematics of Operations Research, 12(2):262–268, 1987.
games. In R.J. Aumann and S. Hart, editors, Handbook
T.L. Lai and H. Robbins. Asymptotically efficient adaptive
of Game Theory, volume 3, pages 1723 – 1759. Elsevier,
allocation rules. Advances in Applied Mathematics, 6:4–22,
Amsterdam, 2002.
1985.
A. Wald. Contributions to the theory of statistical estimation
Debra Lew, Lori Bird, Michael Milligan, Bethany Speer,
and testing hypotheses. The Annals of Mathematics, 10(4):
Xi Wang, Enrico Maria Carlini, Ana Estanqueiro, Damian
299–326, 1939.
Flynn, Emilio Gomez-Lazaro, Nickie Menemenlis, et al.

TABLE III: Parameters and descriptions of policy variables (vector k) and scenario (vector s) in power investment problem.
(a) Parameters and descriptions of policy variables (vector k) in power investment problem.
1
2 , 1}

k ∈ {0,
C
F
X
S
W
P
T
U
N
A

(b) Parameters and descriptions of scenario (vector s) in
power investment problem.

CORRESPONDING INVESTMENT

s ∈ {0,

Coal
Nuclear fission
Nuclear fusion
Supergrids
Wind power
PV units
Solar thermal
Unconventional renewable
Nanogrids
massive storage in Scandinavia

1
2 , 1}

Z
WB
PB
TB
XB
UB
SB
CC
NT

NATURE’S ACTION
Massive geopolitical issues
Wind power technological breakthrough
PV Units breakthrough
Solar thermal breakthrough
Fusion breakthrough
Unconventional renewable breakthrough
Local storage breakthrough
Climate change disaster
Nuclear terrorism

TABLE IV: In these tables, the result is averaged over 100 independent learnings. The standard deviation is shown after ±.
“simul.” refers to “simulation number”, i.e. horizon. Top: Average sparsity level (over 310 = 59049 arms), i.e. number of pure
policies in the support of the obtained approximation, of solutions provided by Exp3.P + t in power investment problem.
“non-truncated” means that all elements of the solution provided are below the threshold ζ (line 2 in Algorithm 4); “nonsparse” means that all elements of the solution provided are above the threshold ζ. In both cases, we play with the original
solution provided by Exp3.P + t. Middle: Empirical mean reward obtained using different truncation parameter α. Bottom:
Exploitability using different truncation parameter α for solutions provided by Exp3.P + t in power investment problem. In
this table, we exclude the solutions which can not be truncated, i.e. all elements are below or all elements are above the
truncation threshold ζ. If at least one solution is excluded, we show between parenthesis the number of solutions excluded
from the 100 learning. When α = 1.0, ζ = maxi∈{1,...,K} pi . Thus, the remaining policy (policies), after truncation, is the
element with the highest frequency (i.e., except in the rare case of a tie, only one arm).
α
0.1
0.3
0.5
0.7
0.9
α
0.1
0.3
0.5
0.7
0.9
Pure
α
0.5
0.7
0.9
Pure

8⌈K/10⌉ simul.

K simul.

1873.70 ± 10.87
491.53 ± 7.74
126.18 ± 3.71
24.80 ± 1.23
3.54 ± 0.23

4621.87 ± 28.34
955.32 ± 13.78
216.63 ± 5.53
36.69 ± 1.69
3.73 ± 0.26

8⌈K/10⌉ simul.

K simul.

2.595
3.299
3.896
4.501
5.021
4.853

±
±
±
±
±
±

.006
.010
.016
.030
.058
.158

8⌈K/10⌉ simul.
−5.560
−4.028
−2.012
−0.938

±
±
±
±

0.070
0.094
0.107
0.078

2.174
3.090
3.779
4.454
5.149
5.027

±
±
±
±
±
±

AVERAGE SPARSITY LEVEL OVER 310 = 59049 ARMS
32⌈K/10⌉ simul.
128⌈K/10⌉ simul.
512⌈K/10⌉ simul.
non-truncated
12140.13 ± 234.46
1502.24 ± 33.85
168.02 ± 6.94
7.35 ± 0.49

non-truncated
7577.95 ± 154.37
687.42 ± 19.37
63.04 ± 2.49
5.12 ± 0.29

non-truncated
710.45 ± 11.28
33.01 ± 1.14
6.57 ± 0.27
1.93 ± 0.09

EMPIRICAL MEAN REWARD AGAINST PURE STRATEGIES
32⌈K/10⌉ simul.
128⌈K/10⌉ simul.
512⌈K/10⌉ simul.

.006
.009
.015
.027
.062
.143

-.029 ± .004
2.195 ± .017
3.592 ± .016
4.674 ± .022
5.703 ± .040
5.709 ± .101

1.050
3.892
5.275
6.101
6.536
6.137

±
±
±
±
±
±

.004
.018
.020
.016
.017
.163

2.184
6.555
6.741
6.777
6.813
6.413

±
±
±
±
±
±

.005
.008
.007
.007
.007
.136

EXPLOITABILITY INDICATOR: WORST SCORE AGAINST PURE STRATEGIES
K simul.
32⌈K/10⌉ simul.
128⌈K/10⌉ simul.
512⌈K/10⌉ simul.
−5.693
−4.132
−1.859
−0.971

±
±
±
±

0.058
0.094
0.115
0.092

−5.725
−4.038
−1.369
−0.455

±
±
±
±

0.060
0.074
0.081
0.060

−3.479 ± 0.061
−1.243 ± 0.032
−0.195 ± 0.028
0.182 ± 0.021

−0.576 ± 0.041
0.010 ± 0.018
0.272 ± 0.011
0.323 ± 0.005

2048⌈K/10⌉ simul.
non-truncated
320.43 ± 2.91
10.16 ± 0.27
2.59 ± 0.11
1.17 ± 0.04
2048⌈K/10⌉ simul.
4.105
6.822
6.853
6.858
6.873
6.844

±
±
±
±
±
±

.006
.004
.004
.005
.004
.028

2048⌈K/10⌉ simul.
0.056
0.268
0.330
0.333

±
±
±
±

0.024
0.011
0.003
0.000

TABLE V: Results for reward matrix R′ computed with c = 1. In these tables, the result is the average value of 100 learnings.
The standard deviation is shown after ±. “NT” means that the truncation technique is not applied; “non-sparse” means that all
elements of the solution provided are above the threshold ζ. Top: Average sparsity level (over 310 = 59049 arms), i.e. number
of pure policies in the support of the obtained approximation, of solutions provided by Exp3.P + t in power investment
problem. Middle: Proxy exploitability (to be maximized) using different truncation parameter α for solutions provided by
Exp3.P + t in power investment problem. The proxy exploitability is the difference between the best robust score in the table,
minus the robust score. Bottom: Robust score (to be minimized) using different truncation parameter α for solutions provided
by Exp3.P + t in power investment problem. The robust score is the worst of the scores against pure policies.
α
0.1
0.3
0.5
0.7
0.9
0.99
α
NT
0.1
0.3
0.5
0.7
0.9
0.99
Pure
α
NT
0.1
0.3
0.5
0.7
0.9
0.99
Pure

T =K
13804.380 ± 52.015
2810.120 ± 59.083
395.920 ± 15.835
43.230 ± 2.624
3.600 ± 0.260
1.110 ± 0.031

AVERAGE SPARSITY LEVEL OVER 310 = 59049 ARMS
T = 10K
T = 50K
T = 100K
T = 500K
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
59048.960 ± 196.946
49819.430 ± 195.016
58925.340 ± 26.821
55383.140 ± 150.057
46000.020 ± 277.653
9065.180 ± 159.610
992.940 ± 64.474
796.500 ± 41.724
503.600 ± 24.927
97.670 ± 5.445
2.250 ± 0.171
2.500 ± 0.180
2.310 ± 0.156
1.790 ± 0.121

T =K
4.922e-01 ± 5.649e-07
4.948e-01 ± 5.739e-05
5.004e-01 ± 1.397e-04
5.059e-01 ± 2.272e-04
5.054e-01 ± 1.327e-03
4.281e-01 ± 6.926e-03
3.634e-01 ± 8.191e-03
3.505e-01 ± 7.842e-03

T = 10K
4.928e-01 ± 1.787e-06
4.928e-01 ± 1.787e-06
4.928e-01 ± 1.787e-06
4.928e-01 ± 1.787e-06
4.928e-01 ± 3.835e-06
5.137e-01 ± 4.199e-04
4.357e-01 ± 6.873e-03
3.946e-01 ± 7.181e-03

PROXY EXPLOITABILITY
T = 50K
T = 100K
4.956e-01 ± 4.016e-06
4.991e-01 ± 5.892e-06
4.956e-01 ± 4.016e-06
4.991e-01 ± 5.892e-06
4.956e-01 ± 4.016e-06
4.991e-01 ± 5.892e-06
4.956e-01 ± 4.016e-06
4.991e-01 ± 5.891e-06
4.965e-01 ± 3.896e-05
5.031e-01 ± 1.016e-04
5.151e-01 ± 5.007e-04
5.140e-01 ± 4.965e-04
4.612e-01 ± 5.380e-03
4.683e-01 ± 4.834e-03
4.287e-01 ± 6.203e-03
4.489e-01 ± 5.410e-03

T = 500K
5.221e-01 ± 1.404e-05
5.221e-01 ± 1.404e-05
5.221e-01 ± 1.404e-05
5.242e-01 ± 5.491e-05
5.317e-01 ± 9.573e-05
5.487e-01 ± 9.413e-04
5.242e-01 ± 3.302e-03
5.143e-01 ± 3.597e-03

T =K
1.369e-02
1.109e-02
5.485e-03
0.000e+00
4.328e-04
7.778e-02
1.425e-01
1.554e-01

T = 10K
2.092e-02
2.092e-02
2.092e-02
2.092e-02
2.091e-02
0.000e+00
7.806e-02
1.191e-01

ROBUST SCORE
T = 50K
T = 100K
1.946e-02
1.492e-02
1.946e-02
1.492e-02
1.946e-02
1.492e-02
1.946e-02
1.492e-02
1.854e-02
1.083e-02
0.000e+00
0.000e+00
5.385e-02
4.564e-02
8.638e-02
6.503e-02

T = 500K
2.669e-02
2.669e-02
2.669e-02
2.454e-02
1.705e-02
0.000e+00
2.456e-02
3.443e-02

T = 1000K
non-sparse
non-sparse
non-sparse
non-sparse
52632.820 ± 522.505
6.700 ± 0.612
T =
4.938e-01
4.938e-01
4.938e-01
4.938e-01
4.938e-01
4.960e-01
5.390e-01
4.837e-01

1000K
± 1.687e-06
± 1.687e-06
± 1.687e-06
± 1.687e-06
± 1.687e-06
± 1.828e-04
± 3.167e-03
± 5.558e-03

T = 1000K
4.525e-02
4.525e-02
4.525e-02
4.525e-02
4.525e-02
4.304e-02
0.000e+00
5.537e-02

TABLE VI: Results for reward matrix R′ computed with c = 10. In these tables, the result is the average value of 100 learnings.
The standard deviation is shown after ±. “NT” means that the truncation technique is not applied; “non-sparse” means that all
elements of the solution provided are above the threshold ζ. Top: Average sparsity level (over 310 = 59049 arms), i.e. number
of pure policies in the support of the obtained approximation, of solutions provided by Exp3.P + t in power investment
problem. Middle: Proxy exploitability (to be maximized) using different truncation parameter α for solutions provided by
Exp3.P + t in power investment problem. The proxy exploitability is the difference between the best robust score in the table,
minus the robust score. Bottom: Robust score (to be minimized) using different truncation parameter α for solutions provided
by Exp3.P + t in power investment problem. The robust score is the worst of the scores against pure policies.
α
0.1
0.3
0.5
0.7
0.9
0.99
α
NT
0.1
0.3
0.5
0.7
0.9
0.99
Pure
α
NT
0.1
0.3
0.5
0.7
0.9
0.99
Pure

T =K
6394.625 ± 84.308
1337.896 ± 40.491
206.146 ± 12.647
25.563 ± 2.045
3.729 ± 0.353
1.208 ± 0.072

AVERAGE SPARSITY LEVEL OVER 310 = 59049 ARMS
T = 10K
T = 50K
T = 100K
T = 500K
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
non-sparse
59048.750 ± 0.250
42616.313 ± 1476.644
47581 ± 1015.506
38361.182 ± 1091.373
4510.125 ± 726.595
4.479 ± 0.575
5.333 ± 0.565
6.000 ± 0.969
2.875 ± 1.076

T =K
1.151e-01 ± 6.772e-08
1.158e-01 ± 1.843e-05
1.160e-01 ± 3.441e-05
1.166e-01 ± 9.751e-05
1.165e-01 ± 6.176e-04
1.068e-01 ± 3.176e-03
8.423e-02 ± 3.118e-03
7.810e-02 ± 2.570e-03

T = 10K
1.151e-01 ± 2.175e-07
1.151e-01 ± 2.175e-07
1.151e-01 ± 2.175e-07
1.151e-01 ± 2.175e-07
1.151e-01 ± 2.175e-07
1.156e-01 ± 4.586e-05
1.119e-01 ± 2.316e-03
8.354e-02 ± 2.710e-03

PROXY EXPLOITABILITY
T = 50K
T = 100K
1.153e-01 ± 3.707e-07
1.154e-01 ± 5.797e-07
1.153e-01 ± 3.707e-07
1.154e-01 ± 6.019e-07
1.153e-01 ± 3.707e-07
1.154e-01 ± 6.019e-07
1.153e-01 ± 3.707e-07
1.154e-01 ± 5.797e-07
1.153e-01 ± 3.707e-07
1.154e-01 ± 5.797e-07
1.160e-01 ± 6.348e-05
1.172e-01 ± 9.722e-05
1.189e-01 ± 1.888e-03
1.202e-01 ± 2.101e-03
9.327e-02 ± 2.202e-03
9.658e-02 ± 2.097e-03

T = 500K
1.167e-01 ± 2.046e-06
1.167e-01 ± 2.046e-06
1.167e-01 ± 2.046e-06
1.167e-01 ± 2.046e-06
1.167e-01 ± 2.051e-06
1.266e-01 ± 3.829e-04
1.145e-01 ± 4.519e-03
1.120e-01 ± 3.625e-03

T =K
1.494e-03
7.727e-04
5.838e-04
0.000e+00
9.391e-05
9.758e-03
3.236e-02
3.848e-02

T = 10K
4.594e-04
4.594e-04
4.594e-04
4.594e-04
4.594e-04
0.000e+00
3.647e-03
3.204e-02

ROBUST SCORE
T = 50K
T = 100K
3.592e-03
4.772e-03
3.592e-03
4.772e-03
3.592e-03
4.772e-03
3.592e-03
4.772e-03
3.592e-03
4.772e-03
2.860e-03
2.992e-03
0.000e+00
0.000e+00
2.559e-02
2.362e-02

T = 500K
9.903e-03
9.903e-03
9.903e-03
9.903e-03
9.903e-03
0.000e+00
1.211e-02
1.463e-02

T = 1000K
non-sparse
non-sparse
non-sparse
non-sparse
58323.125 ± 157.971
8.500 ± 2.204
T =
1.152e-01
1.152e-01
1.152e-01
1.152e-01
1.152e-01
1.152e-01
1.186e-01
8.755e-02

1000K
± 1.297e-06
± 1.297e-06
± 1.297e-06
± 1.297e-06
± 1.297e-06
± 4.288e-06
± 7.684e-04
± 6.497e-03

T = 1000K
3.388e-03
3.388e-03
3.388e-03
3.388e-03
3.388e-03
3.371e-03
0.000e+00
3.103e-02

