Under review as a conference paper at ICLR 2018

R EINFORCEMENT L EARNING A LGORITHM S ELECTION
Romain Laroche1 and Raphaël Féraud2
1

Microsoft Research Maluuba, Montréal, Canada

2

Orange Labs, Lannion, France

arXiv:1701.08810v3 [stat.ML] 14 Nov 2017

A BSTRACT
This paper formalises the problem of online algorithm selection in the context of
Reinforcement Learning. The setup is as follows: given an episodic task and a
finite number of off-policy RL algorithms, a meta-algorithm has to decide which
RL algorithm is in control during the next episode so as to maximize the expected
return. The article presents a novel meta-algorithm, called Epochal Stochastic
Bandit Algorithm Selection (ESBAS). Its principle is to freeze the policy updates
at each epoch, and to leave a rebooted stochastic bandit in charge of the algorithm
selection. Under some assumptions, a thorough theoretical analysis demonstrates
its near-optimality considering the structural sampling budget limitations. ESBAS
is first empirically evaluated on a dialogue task where it is shown to outperform
each individual algorithm in most configurations. ESBAS is then adapted to a true
online setting where algorithms update their policies after each transition, which
we call SSBAS. SSBAS is evaluated on a fruit collection task where it is shown to
adapt the stepsize parameter more efficiently than the classical hyperbolic decay,
and on an Atari game, where it improves the performance by a wide margin.

1

I NTRODUCTION

Reinforcement Learning (RL, Sutton & Barto (1998)) is a machine learning framework for optimising
the behaviour of an agent interacting with an unknown environment. For the most practical problems,
such as dialogue or robotics, trajectory collection is costly and sample efficiency is the main key
performance indicator. Consequently, when applying RL to a new problem, one must carefully choose
in advance a model, a representation, an optimisation technique and their parameters. Facing the
complexity of choice, RL and domain expertise is not sufficient. Confronted to the cost of data, the
popular trial and error approach shows its limits.
We develop an online learning version (Gagliolo & Schmidhuber, 2006; 2010) of Algorithm Selection
(AS, Rice (1976); Smith-Miles (2009); Kotthoff (2012)). It consists in testing several algorithms on
the task and in selecting the best one at a given time. For clarity, throughout the whole article, the
algorithm selector is called a meta-algorithm, and the set of algorithms available to the meta-algorithm
is called a portfolio. The meta-algorithm maximises an objective function such as the RL return.
Beyond the sample efficiency objective, the online AS approach besides addresses four practical
problems for online RL-based systems. First, it improves robustness: if an algorithm fails to terminate,
or outputs to an aberrant policy, it will be dismissed and others will be selected instead. Second,
convergence guarantees and empirical efficiency may be united by covering the empirically efficient
algorithms with slower algorithms that have convergence guarantees. Third, it enables curriculum
learning: shallow models control the policy in the early stages, while deep models discover the best
solution in late stages. And four, it allows to define an objective function that is not an RL return.
A fair algorithm selection implies a fair budget allocation between the algorithms, so that they can
be equitably evaluated and compared. In order to comply with this requirement, the reinforcement
algorithms in the portfolio are assumed to be off-policy, and are trained on every trajectory, regardless
which algorithm controls it. Section 2 provides a unifying view of RL algorithms, that allows information sharing between algorithms, whatever their state representations and optimisation techniques.
It also formalises the problem of online selection of off-policy RL algorithms.
Next, Section 3 presents the Epochal Stochastic Bandit AS (ESBAS), a novel meta-algorithm
addressing the online off-policy RL AS problem. Its principle is to divide the time-scale into epochs
1

Under review as a conference paper at ICLR 2018

of exponential length inside which the algorithms are not allowed to update their policies. During
each epoch, the algorithms have therefore a constant policy and a stochastic multi-armed bandit
can be in charge of the AS with strong pseudo-regret theoretical guaranties. A thorough theoretical
analysis provides for ESBAS upper bounds. Then, Section 4 empirically evaluates ESBAS on a
dialogue task where it is shown to outperform each individual algorithm in most configurations.
Afterwards, in Section 5, ESBAS, which is initially designed for a growing batch RL setting, is
adapted to a true online setting where algorithms update their policies after each transition, which we
call SSBAS. It is evaluated on a fruit collection task where it is shown to adapt the stepsize parameter
more efficiently than the classical hyperbolic decay, and on Q*bert, where running several DQN with
different network size and depth in parallel allows to improve the final performance by a wide margin.
Finally, Section 6 concludes the paper with prospective ideas of improvement.

2

Agent

A LGORITHM S ELECTION FOR RL
o(t + 1)

2.1

U NIFYING VIEW OF RL ALGORITHMS

r(t + 1)

a(t)
Stochastic
environment

The goal of this section is to enable information
sharing between algorithms, even though they
are considered as black boxes. We propose to Figure 1: RL framework: after performing action
share their trajectories expressed in a universal a(t), the agent perceives observation o(t + 1) and
receives reward r(t + 1).
format: the interaction process.
Reinforcement Learning (RL) consists in learning through trial and error to control an agent behaviour
in a stochastic environment: at each time step t ∈ N, the agent performs an action a(t) ∈ A, and then
perceives from its environment a signal o(t) ∈ Ω called observation, and receives a reward r(t) ∈ R,
bounded between Rmin and Rmax . Figure 1 illustrates the RL framework. This interaction process is
not Markovian: the agent may have an internal memory.
In this article, the RL problem is assumed to be episodic. Let us introduce two time scales with
different notations. First, let us define meta-time as the time scale for AS: at one meta-time τ
corresponds a meta-algorithm decision, i.e. the choice of an algorithm and the generation of a full
episode controlled with the policy determined by the chosen algorithm. Its realisation is called
a trajectory. Second, RL-time is defined as the time scale inside a trajectory, at one RL-time t
corresponds one triplet composed of an observation, an action, and a reward.
Let E denote the space of trajectories. A trajectory ετ ∈ E collected at meta-time τ is formalised
as a sequence of (observation, action, reward) triplets: ετ = hoτ (t), aτ (t), rτ (t)it∈J1,|ετ |K ∈ E,
where |ετ | is the length of trajectory ετ . The objective is, given a discount factor 0 ≤ γ < 1,
to generate trajectories with high discounted cumulative reward, also called return, and noted
P|ετ | t−1
µ(ετ ) = t=1
γ rτ (t). Since γ < 1 and R is bounded, the return is also bounded. The trajectory
set at meta-time T is denoted by DT = {ετ }τ ∈J1,T K ∈ E T . A sub-trajectory of ετ until RL-time t is
called the history at RL-time t and written ετ (t) with t ≤ |ετ |. The history records what happened in
episode ετ until RL-time t: ετ (t) = hoτ (t0 ), aτ (t0 ), rτ (t0 )it0 ∈J1,tK ∈ E.
The goal of each RL algorithm α is to find a policy π ∗ : E → A which yields optimal expected
returns. Such an algorithm α is viewed as a black box that takes as an input
set D ∈ E + ,
S a trajectory
+
+
T
where E is the ensemble of trajectory sets of undetermined size: E = T ∈N E , and that outputs
α
a policy πD
. Consequently, a RL algorithm is formalised as follows: α : E + → (E → A).
Such a high level definition of the RL algorithms allows to share trajectories between algorithms: a
trajectory as a sequence of observations, actions, and rewards can be interpreted by any algorithm
in its own decision process and state representation. For instance, RL algorithms classically rely
α
on an MDP defined on a explicit or implicit state space representation SD
thanks to a projection
α
α
Φα
:
E
→
S
.
Then,
α
trains
its
policy
π
on
the
trajectories
projected
on its state space
D
D
DT
representation. Off-policy RL optimisation techniques compatible with this approach are numerous in
the literature (Watkins, 1989; Ernst et al., 2005; Mnih et al., 2013). As well, any post-treatment of the
state set, any alternative decision process (Lovejoy, 1991), and any off-policy algorithm may be used.
The algorithms are defined here as black boxes and the considered meta-algorithms will be indifferent
to how the algorithms compute their policies, granted they satisfy the off-policy assumption.
2

Under review as a conference paper at ICLR 2018

2.2

O NLINE ALGORITHM SELECTION
Pseudo-code 1: Online RL AS setting

The online learning approach is tackled in
this article: different algorithms are experienced and evaluated during the data collection. Since it boils down to a classical exploration/exploitation trade-off, multi-armed bandit (Bubeck & Cesa-Bianchi, 2012) have been
used for combinatorial search AS (Gagliolo &
Schmidhuber, 2006; 2010) and evolutionary algorithm meta-learning (Fialho et al., 2010). The
online AS problem for off-policy RL is novel
and we define it as follows:

Data: D0 ← ∅: trajectory set
Data: P ← {αk }k∈J1,KK : algorithm portfolio
Data: µ : E → R: the objective function
for τ ← 1 to ∞ do
Select σ (Dτ −1 ) = σ(τ ) ∈ P;
σ(τ )
Generate trajectory ετ with policy πDτ −1 ;
Get return µ(ετ );
Dτ ← Dτ −1 ∪ {ετ };
end

• D ∈ E + is the current trajectory set;
• P = {αk }k∈J1,KK is the portfolio of off-policy RL algorithms;
• µ : E → R is the objective function, generally set as the RL return.
Pseudo-code 1 formalises the online RL AS setting. A meta-algorithm is defined as a function from
a trajectory set to the selection of an algorithm: σ : E + → P. The meta-algorithm is queried at
each meta-time τ = |Dτ −1 |+1, with input Dτ −1 , and it ouputs algorithm σ (Dτ −1 ) = σ(τ ) ∈ P
σ(τ )
controlling with its policy πDτ −1 the generation of the trajectory ετ in the stochastic environment.
The final goal is to optimise the cumulative expected return. It is the expectation of the sum of rewards
obtained after a run of T trajectories:
"
Eσ

T
X

#

"

µ (ετ ) = Eσ

τ =1

T
X

#
σ(τ )
EµDσ
τ −1

,

(1)

τ =1

α
α
with Eµα
D = EπD [µ (ε)] as a condensed notation for the expected return of policy πD , trained on
trajectory set D by algorithm α. Equation 1 transforms the cumulative expected return into two nested
expectations. The outside expectation Eσ assumes the meta-algorithm σ fixed and averages over
the trajectory set generation and the corresponding algorithms policies. The inside expectation Eµ
assumes the policy fixed and averages over its possible trajectories in the stochastic environment.
Nota bene: there are three levels of decision: meta-algorithm σ selects algorithm α that computes
policy π that is in control. In this paper, the focus is at the meta-algorithm level.

2.3

M ETA - ALGORITHM EVALUATION

In order to evaluate the meta-algorithms, let us formulate two additional notations. First, the optimal
expected return Eµ∗∞ is defined as the highest expected return achievable by a policy of an algorithm
in portfolio P. Second, for every algorithm α in the portfolio, let us define σ α as its canonical metaalgorithm, i.e. the meta-algorithm that always selects algorithm α: ∀τ , σ α (τ ) = α. The absolute
pseudo-regret ρσabs (T ) defines the regret as the loss for not having controlled the trajectory with an
optimal policy:
"
ρσabs (T )

=

T Eµ∗∞

− Eσ

T
X

#
σ(τ )
EµDσ
τ −1

.

(2)

τ =1

It is worth noting that an optimal meta-algorithm will unlikely yield a null regret because a large
part of the absolute pseudo-regret is caused by the sub-optimality of the algorithm policies when
the trajectory set is still of limited size. Indeed, the absolute pseudo-regret considers the regret for
not selecting an optimal policy: it takes into account both the pseudo-regret of not selecting the best
algorithm and the pseudo-regret of the algorithms for not finding an optimal policy. Since the metaalgorithm does not interfere with the training of policies, it ought not account for the pseudo-regret
related to the latter.
3

Under review as a conference paper at ICLR 2018

2.4

R ELATED WORK

Related to AS for RL, Schweighofer & Doya (2003) use meta-learning to tune a fixed RL algorithm
in order to fit observed animal behaviour, which is a very different problem to ours. In Cauwet et al.
(2014); Liu & Teytaud (2014), the RL AS problem is solved with a portfolio composed of online
RL algorithms. The main limitation from these works relies on the fact that on-policy algorithms
were used, which prevents them from sharing trajectories among algorithms (Cauwet et al., 2015).
Meta-learning specifically for the eligibility trace parameter has also been studied in White & White
(2016). Wang et al. (2016) study the learning process of RL algorithms and selects the best one for
learning faster on a new task. This work is related to batch AS.
An intuitive way to solve the AS problem is to consider algorithms as arms in a multi-armed bandit
setting. The bandit meta-algorithm selects the algorithm controlling the next trajectory ε and the
objective function µ(ε) constitutes the reward of the bandit. The aim of prediction with expert advice
is to minimise the regret against the best expert of a set of predefined experts. When the experts learn
during time, their performances evolve and hence the sequence of expert rewards is non-stationary.
The exponential weight algorithms (Auer et al., 2002b; Cesa-Bianchi & Lugosi, 2006) are designed
for prediction with expert advice when the sequence of rewards of experts is generated by an oblivious
adversary. This approach has been extended for competing against the best sequence of experts by
adding in the update of weights a forgetting factor proportional to the mean reward (see Exp3.S in
Auer et al. (2002b)), or by combining Exp3 with a concept drift detector Allesiardo & Féraud (2015).
The exponential weight algorithms have been extended to the case where the rewards are generated
by any sequence of stochastic processes of unknown means (Besbes et al., 2014). The stochastic
bandit algorithm such as UCB can be extended to the case of switching bandits using a discount
factor or a window to forget the past Garivier & Moulines (2011). This class of switching bandit
algorithms are not designed for experts that learn and hence evolve at each time step.

3

Pseudo-code 2: ESBAS with UCB1

E POCHAL S TOCHASTIC BANDIT Data: D , P, µ: the online RL AS setting
0

for β ← 0 to ∞ do
ESBAS description – To solve the offfor αk ∈ P do
k
policy RL AS problem, we propose a novel
πD
: policy learnt by αk on D2β −1
2β −1
meta-algorithm called Epochal Stochastic
end
Bandit AS (ESBAS). Because of the nonn ← 0, ∀αk ∈ P, nk ← 0, and xk ← 0
stationarity induced by the algorithm learning,
for τ ← 2β to 2β+1 − 1 do r
the stochastic bandit cannot directly select al!
log(n)
gorithms. Instead, the stochastic bandit can
k
kmax
α
= argmax x + ξ
choose fixed policies. To comply with this
nk
αk ∈P
constraint, the meta-time scale is divided into
kmax
Generate trajectory ετ with policy πD
epochs inside which the algorithms policies
2β −1
cannot be updated: the algorithms optimise
Get return µ(ετ ), Dτ ← Dτ −1 ∪ {ετ }
their policies only when epochs start, in such
nkmax xkmax + µ(ετ )
kmax
x
←
a way that the policies are constant inside each
nkmax + 1
epoch. As a consequence and since the returns
nkmax ← nkmax + 1 and n ← n + 1
are bounded, at each new epoch, the problem
end
can rigorously be cast into an independent end
stochastic K-armed bandit Ξ, with K = |P|.
The ESBAS meta-algorithm is formally sketched in Pseudo-code 2 embedding UCB1 Auer et al.
(2002a) as the stochastic K-armed bandit Ξ. The meta-algorithm takes as an input the set of algorithms
in the portfolio. Meta-time scale is fragmented into epochs of exponential size. The β th epoch lasts
2β meta-time steps, so that, at meta-time τ = 2β , epoch β starts. At the beginning of each epoch,
the ESBAS meta-algorithm asks each algorithm in the portfolio to update their current policy. Inside
an epoch, the policy is never updated anymore. At the beginning of each epoch, a new Ξ instance is
reset and run. During the whole epoch, Ξ selects at each meta-time step the algorithm in control of
the next trajectory.
Theoretical analysis – ESBAS intends to minimise the regret for not choosing the algorithm
yielding the maximal return at a given meta-time τ . It is short-sighted: it does not intend to optimise
4

Under review as a conference paper at ICLR 2018

the algorithms learning. We define the short-sighted pseudo-regret as follows:
" T 
#
X
σ(τ )
σ
α
ρss (T ) = Eσ
max EµDτσ−1 − EµDσ
.
τ =1

(3)

τ −1

α∈P

The short-sighted pseudo-regret depends on the gaps ∆α
β : the difference of expected return between
the best algorithm during epoch β and algorithm α. The smallest non null gap at epoch β is noted
∆†β . We write its limit when β tends to infinity with ∆†∞ .
Based on several assumptions, three theorems show that ESBAS absolute pseudo-regret can be
expressed in function of the absolute pseudo-regret of the best canonical algorithm and ESBAS shortsighted pseudo-regret. They also provide upper bounds on the ESBAS short-sighted pseudo-regret.
The full theoretical analysis can be found in the supplementary material, Section B. We provide here
an intuitive overlook of its results. Table 1 numerically reports those bounds for a two-fold portfolio,
depending on the nature of the algorithms. It must be read by line. According to the first column:
the order of magnitude of ∆†β , the ESBAS short-sighted pseudo-regret bounds are displayed in the
second column, and the third and fourth columns display the ESBAS absolute pseudo-regret bounds
∗
also depending on the order of magnitude of ρσabs (T ).
Regarding the short-sighted upper bounds, the main result appears in the last line, when the algorithms
converge to policies with different performance:
ESBAS logarithmically converges to the best

algorithm with a regret in O log2 (T )/∆†∞ . Also, one should notice that the first two bounds are
obtained by summing the gaps. This means that the algorithms are almost equally good and√their gap
goes beyond the threshold of distinguishability. This threshold is structurally at ∆†β ∈ O(1/ T ). The
impossibility to determine which is the better algorithm is interpreted in Cauwet et al. (2014) as a
budget issue. The meta-time necessary to distinguish through evaluation arms that are ∆†β apart takes
√
†
†2
Θ(1/∆†2
β ) meta-time steps. As a consequence, if ∆β ∈ O(1/ T ), then 1/∆β ∈ Ω(T ). However,
the budget, i.e. the length of epoch β starting at meta-time T = 2β , equals T .
√
Additionally, the absolute upper bounds are logarithmic in the best case and still inferior p
to O( T ) in
the worst case, which compares favorably with those of discounted UCB and Exp3.S
in O( T log(T ))
√
and Rexp3 in O(T 2/3 ), or the RL with Policy Advice’s regret bounds of O( T log(T )).
ESBAS

Table 1: Bounds on ρσss

ESBAS

(T ) and ρσabs

(T ) given various settings for a two-fold portfolio AS.
ESBAS

∆†β

ESBAS
ρσss
(T )

Θ (1/T )

O (log(T ))

†

Θ(T −c ), and c† ≥ 0.5

O(T

1−c†

ρσabs

∗

(T ) in function of ρσabs (T )

∗

ρσabs (T ) ∈ O(log(T ))

∗

∗

ρσabs (T ) ∈ O(T 1−c )

O (log(T ))
†

†

O(T 1−c )

)

O(T 1−c )
∗

†

†

Θ(T −c ), and c† < 0.5

O(T c log(T ))

Θ (1)

O log2 (T )/∆†∞

4

O(T 1−c ), if c† < 1 − c∗

†

O(T c log(T ))


O log2 (T )/∆†∞

†

O(T c log(T )), if c† ≥ 1 − c∗


∗

O(T 1−c )

ESBAS D IALOGUE E XPERIMENTS

ESBAS is particularly designed for RL tasks when it is impossible to update the policy after every
transition or episode. Policy update is very costly in most real-world applications, such as dialogue
systems (Khouzaimi et al., 2016) for which a growing batch setting is preferred (Lange et al.,
2012). ESBAS practical efficiency is therefore illustrated on a dialogue negotiation game (Laroche
& Genevay, 2016) that involves two players: the system ps and a user pu . Their goal is to find an
agreement among 4 alternative options. At each dialogue, for each option η, players have a private
uniformly drawn cost νηp ∼ U[0, 1] to agree on it. Each player is considered fully empathetic to the
other one. The details of the experiment can be found in the supplementary material, Section C.1.1.
5

Under review as a conference paper at ICLR 2018

(2a) simple vs simple-2

(2c) simple-2 vs constant-1.009

(2e) 8 learners

(2b) simple vs simple-2

(2d) simple-2 vs constant-1.009

(2f) 8 learners

Figure 2: The figures on the top plot the performance over time. The figures on the bottom show the
ESBAS selection ratios over the epochs.
All learning algorithms are using Fitted-Q Iteration (Ernst et al., 2005), with a linear parametrisation and an β -greedy exploration : β = 0.6β , β being the epoch number. Several algorithms
differing by their state space representation Φα are considered: simple, fast, simple-2, fast-2, n-ζ{simple/fast/simple-2/fast-2}, and constant-µ. See Section C.1.2 for their full descriptions.
The algorithms and ESBAS are playing with a stationary user simulator built through Imitation
Learning from real-human data. All the results are averaged over 1000 runs. The performance figures
plot the curves of algorithms individual performance σ α against the ESBAS portfolio control σ ESBAS
in function of the epoch (the scale is therefore logarithmic in meta-time). The performance is the
average return of the RL problem. The ratio figures plot the average algorithm selection proportions
of ESBAS at each epoch. We define the relative pseudo regret as the difference between the ESBAS
absolute pseudo-regret and the absolute pseudo-regret of the best canonical meta-algorithm. Relative
pseudo-regrets have a 95% confidence interval about ±6 ≈ ±1.5 × 10−4 per trajectory. Extensive
numerical results are provided in Table 2 of the supplementary material.
Figures 2a and 2b plot the typical curves obtained with ESBAS selecting from a portfolio of two
learning algorithms. On Figure 2a, the ESBAS curve tends to reach more or less the best algorithm
in each point as expected. Surprisingly, Figure 2b reveals that the algorithm selection ratios are not
very strong in favour of one or another at any time. Indeed, the variance in trajectory set collection
makes simple better on some runs until the end. ESBAS proves to be efficient at selecting the best
algorithm for each run and unexpectedly obtains a negative relative pseudo-regret of -90. Figures
2c and 2d plot the typical curves obtained with ESBAS selecting from a portfolio constituted of a
learning algorithm and an algorithm with a deterministic and stationary policy. ESBAS succeeds in
remaining close to the best algorithm at each epoch and saves 5361 return value for not selecting
the constant algorithm, but overall yields a regret for not using only the best algorithm. ESBAS also
performs well on larger portfolios of 8 learners (see Figure 2e) with negative relative pseudo-regrets:
−10, even if the algorithms are, on average, almost selected uniformly as Figure 2f reveals. Each
individual run may present different ratios, depending on the quality of the trained policies. ESBAS
also offers some curriculum learning, but more importantly, early bad policies are avoided.
Algorithms with a constant policy do not improve over time and the full reset of the K-multi armed
bandit urges ESBAS to unnecessarily explore again and again the same underachieving algorithm.
One easy way to circumvent this drawback is to use this knowledge and to not reset their arms. By
operating this way, when the learning algorithm(s) start(s) outperforming the constant one, ESBAS
simply neither exploits nor explores the constant algorithm anymore. Without arm reset for constant
algorithms, ESBAS’s learning curve follows perfectly the learning algorithm’s learning curve when
this one outperforms the constant algorithm and achieves strong negative relative pseudo-regrets.
Again, the interested reader may refer to Table 2 in supplementary material for the numerical results.
6

Under review as a conference paper at ICLR 2018

5

S LIDING S TOCHASTIC BANDIT

In this section, we propose to adapt ESBAS to a true online setting where algorithms update their
policies after each transition. The stochastic bandit is now trained on a sliding window with the last
τ /2 selections. Even though the arms are not stationary over this window, there is the guarantee of
eventually forgetting the oldest arm pulls. This algorithm is called SSBAS for Sliding Stochastic
Bandit AS. Despite the lack of theoretical convergence bounds, we demonstrate on two domains
and two different meta-optimisation tasks that SSBAS does exceptionally well, outperforming all
algorithms in the portfolio by a wide margin.
5.1

G RIDWORLD DOMAIN

The goal here is to demonstrate that SSBAS can perform efficient hyperparameter optimisation on a simple tabular domain: a 5x5 gridworld
problem (see Figure 3), where the goal is to collect the fruits placed at
each corner as fast as possible. The episodes terminate when all fruits
have been collected or after 100 transitions. The objective function µ
used to optimise the stochastic bandit Ψ is no longer the RL return,
but the time spent to collect all the fruits (200 in case of it did not).
The agent has 18 possible positions and there are 24 − 1 = 15 nonterminal fruits configurations, resulting in 270 states. The action set is
Figure 3: gridworld
A = {N, E, S, W }. The reward function mean is 1 when eating a fruit,
0 otherwise. The reward function is corrupted with a strong Gaussian white noise of variance ζ 2 = 1.
The portfolio is composed of 4 Q-learning algorithms varying from each other by their learning rates:
{0.001, 0.01, 0.1, 0.5}. They all have the same linearly annealing τ -greedy exploration.
The selection ratios displayed in Figure 5 show that SSBAS selected the algorithm with the highest
(0.5) learning rate in the first stages, enabling to propagate efficiently the reward signal through the
visited states, then, overtime preferentially chooses the algorithm with a learning rate of 0.01, which
is less sensible to the reward noise, finally, SSBAS favours the algorithm with the finest learning rate
(0.001). After 1 million episodes, SSBAS enables to save half a transition per episode on average
as compared to the best fixed learning rate value (0.1), and two transitions against the worst fixed
learning rate in the portfolio (0.001). We also compared it to the efficiency of a linearly annealing
learning rate: 1/(1 + 0.0001τ ): SSBAS performs under 21 steps on average after 105 , while the
linearly annealing learning rate algorithm still performs a bit over 21 steps after 106 steps.
5.2

ATARI DOMAIN : Q* BERT

We investigate here AS for deep RL on the Arcade Learning Environment
(ALE, Bellemare et al. (2013)) and more precisely the game Q*bert (see
a frame on Figure 4), where the goal is to step once on each block. Then
a new similar level starts. In later levels, one needs to step twice on
each block, and even later stepping again on the same blocks will cancel
the colour change. We used three different settings of DQN instances:
small uses the setting described in Mnih et al. (2013), large uses the
setting in Mnih et al. (2015), and finally huge uses an even larger network
(see Section C.2 in the supplementary material for details). DQN is
known to reach a near-human level performance at Q*bert. Our SSBAS
instance runs 6 algorithms with 2 different random initialisations of each
DQN setting. Disclaimer: contrarily to other experiments, each curve
Figure 4: Q*bert
is the result of a single run, and the improvement might be aleatory.
Indeed, the DQN training is very long and SSBAS needs to train all the models in parallel. A more
computationally-efficient solution might be to use the same architecture as Osband et al. (2016).
Figure 6 reveals that SSBAS experiences a slight delay keeping in touch with the best setting
performance during the initial learning phase, but, surprisingly, finds a better policy than the single
algorithms in its portfolio and than the ones reported in the previous DQN articles. We observe that
the large setting is surprisingly by far the worst one on the Q*bert task, implying the difficulty to
predict which model is the most efficient for a new task. SSBAS allows to select online the best one.
7

Under review as a conference paper at ICLR 2018

1.0

Q-Learning with learning rate: 0.001
Q-Learning with learning rate: 0.01
Q-Learning with learning rate: 0.1
Q-Learning with learning rate: 0.5

0.8

×104

2.0

0.6

1.5

0.4

1.0

0.2

0.5

0.0

0

20000

40000

60000

80000

100000

0.0

Figure 5: gridworld ratios (3000 runs).

6

small network
large network
huge network
SSBAS

0

20000

40000

60000

80000

100000

120000

140000

Figure 6: Q*bert performance per episode (1 run).

C ONCLUSION

In this article, we tackle the problem of selecting online off-policy RL algorithms. The problem
is formalised as follows: from a fixed portfolio of algorithms, a meta-algorithm learns which one
performs the best on the task at hand. Fairness of algorithm evaluation is granted by the fact that the
RL algorithms learn off-policy. ESBAS, a novel meta-algorithm, is proposed. Its principle is to divide
the meta-time scale into epochs. Algorithms are allowed to update their policies only at the start
each epoch. As the policies are constant inside each epoch, the problem can be cast into a stochastic
multi-armed bandit. An implementation is detailed and a theoretical analysis leads to upper bounds
on the regrets. ESBAS is designed for the growing batch RL setting. This limited online setting is
required in many real-world applications where updating the policy requires a lot of resources.
Experiments are first led on a negotiation dialogue game, interacting with a human data-built
simulated user. In most settings, not only ESBAS demonstrates its efficiency to select the best
algorithm, but it also outperforms the best algorithm in the portfolio thanks to curriculum learning,
and variance reduction similar to that of Ensemble Learning. Then, ESBAS is adapted to a full online
setting, where algorithms are allowed to update after each transition. This meta-algorithm, called
SSBAS, is empirically validated on a fruit collection task where it performs efficient hyper-parameter
optimisation. SSBAS is also evaluated on the Q*bert Atari game, where it achieves a substantial
improvement over the single algorithm counterparts.
We interpret ESBAS/SSBAS’s success at reliably outperforming the best algorithm in the portfolio as
the result of the four following potential added values. First, curriculum learning: ESBAS/SSBAS
selects the algorithm that is the most fitted with the data size. This property allows for instance to use
shallow algorithms when having only a few data and deep algorithms once collected a lot. Second,
diversified policies: ESBAS/SSBAS computes and experiments several policies. Those diversified
policies generate trajectories that are less redundant, and therefore more informational. As a result, the
policies trained on these trajectories should be more efficient. Third, robustness: if one algorithm fails
at finding good policies, it will soon be discarded. This property prevents the agent from repeating
again and again the same obvious mistakes. Four and last, run adaptation: of course, there has to be
an algorithm that is the best on average for one given task at one given meta-time. But depending on
the variance in the trajectory collection, it did not necessarily train the best policy for each run. The
ESBAS/SSBAS meta-algorithm tries and selects the algorithm that is the best at each run. Some of
those properties are inherited by algorithm selection similarity with ensemble learning (Dietterich,
2002). Wiering & Van Hasselt (2008) uses a vote amongst the algorithms to decide the control of the
next transition. Instead, ESBAS/SSBAS selects the best performing algorithm.
Regarding the portfolio design, it mostly depends on the available computational power per sample
ratio. For practical implementations, we recommend to limit the use of two highly demanding
algorithms, paired with several faster algorithms that can take care of first learning stages, and to use
algorithms that are diverse regarding models, hypotheses, etc. Adding two algorithms that are too
similar adds inertia, while they are likely to not be distinguishable by ESBAS/SSBAS. More detailed
recommendations for building an efficient RL portfolio are left for future work.

8

Under review as a conference paper at ICLR 2018

R EFERENCES
Robin Allesiardo and Raphaël Féraud. Exp3 with drift detection for the switching bandit problem.
In Proceedings of the 2nd IEEE International Conference on the Data Science and Advanced
Analytics (DSAA), pp. 1–7. IEEE, 2015.
Jean-Yves Audibert and Sébastien Bubeck. Best Arm Identification in Multi-Armed Bandits. In
Proceedings of the 23th Conference on Learning Theory (COLT), Haifa, Israel, June 2010.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit
problem. Machine Learning, 2002a. doi: 10.1023/A:1013689704352.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed
bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002b.
Marc G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:
253–279, 2013.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with nonstationary rewards. In Advances in neural information processing systems, pp. 199–207, 2014.
Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multiarmed bandit problems. Foundations and Trends in Machine Learning, 2012. doi: 10.1561/
2200000024.
Marie-Liesse Cauwet, Jialin Liu, and Olivier Teytaud. Algorithm portfolios for noisy optimization:
Compare solvers early. In Learning and Intelligent Optimization. Springer, 2014.
Marie-Liesse Cauwet, Jialin Liu, Baptiste Rozière, and Olivier Teytaud. Algorithm Portfolios for
Noisy Optimization. ArXiv e-prints, November 2015.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university
press, 2006.
Thomas G. Dietterich. Ensemble learning. The handbook of brain theory and neural networks, 2:
110–125, 2002.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning.
Journal of Machine Learning Research, 2005.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov
decision processes. In Computational Learning Theory. Springer, 2002.
Álvaro Fialho, Luis Da Costa, Marc Schoenauer, and Michele Sebag. Analyzing bandit-based
adaptive operator selection mechanisms. Annals of Mathematics and Artificial Intelligence, 2010.
Matteo Gagliolo and Jürgen Schmidhuber. Learning dynamic algorithm portfolios. Annals of
Mathematics and Artificial Intelligence, 2006.
Matteo Gagliolo and Jürgen Schmidhuber. Algorithm selection as a bandit problem with unbounded
losses. In Learning and Intelligent Optimization. Springer, 2010.
Aurélien Garivier and Eric Moulines. On Upper-Confidence Bound Policies for Switching Bandit
Problems, pp. 174–188. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. ISBN 978-3642-24412-4. doi: 10.1007/978-3-642-24412-4_16. URL http://dx.doi.org/10.1007/
978-3-642-24412-4_16.
Hatim Khouzaimi, Romain Laroche, and Fabrice Lefevre. Optimising turn-taking strategies with
reinforcement learning. In Proceedings of the 16th Annual Meeting of the Special Interest Group
on Discourse and Dialogue (Sigdial), 2015.
Hatim Khouzaimi, Romain Laroche, and Fabrice Lefèvre. Reinforcement learning for turn-taking
management in incremental spoken dialogue systems. In Proceedings of the 25th International
Joint Conference on Artificial Intelligence (IJCAI), pp. 2831–2837, 2016.
9

Under review as a conference paper at ICLR 2018

Lars Kotthoff. Algorithm selection for combinatorial search problems: A survey. arXiv preprint
arXiv:1210.7959, 2012.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement
learning, pp. 45–73. Springer, 2012.
Romain Laroche and Aude Genevay. A negotiation dialogue game. In Proceedings of the 7th
International Workshop on Spoken Dialogue Systems (IWSDS), Finland, 2016.
Jialin Liu and Olivier Teytaud. Meta online learning: experiments on a unit commitment problem.
In Proceedings of the 22nd European Symposium on Artificial Neural Networks, Computational
Intelligence and Machine Learning (ESANN), 2014.
William S. Lovejoy. Computationally feasible bounds for partially observed markov decision
processes. Operational Research, 1991.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan
Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint
arXiv:1312.5602, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare,
Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control
through deep reinforcement learning. Nature, 518(7540):529–533, 2015.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc G. Bellemare. Safe and efficient
off-policy reinforcement learning. CoRR, abs/1606.02647, 2016.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via
bootstrapped dqn. In Proceedings of the 29th Advances in Neural Information Processing Systems
(NIPS), 2016.
John R. Rice. The algorithm selection problem. Advances in Computers, 1976.
Nicolas Schweighofer and Kenji Doya. Meta-learning in reinforcement learning. Neural Networks,
2003.
Kate A. Smith-Miles. Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM
Computational Survey, 2009.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction (Adaptive
Computation and Machine Learning). The MIT Press, March 1998. ISBN 0262193981.
Jane X. Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z. Leibo, Rémi Munos,
Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. CoRR,
abs/1611.05763, 2016.
C.J.C.H. Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge
(England), May 1989.
Martha White and Adam White. Adapting the trace parameter in reinforcement learning. In
Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems
(AAMAS). International Foundation for Autonomous Agents and Multiagent Systems, 2016.
Marco A Wiering and Hado Van Hasselt. Ensemble algorithms in reinforcement learning. IEEE
Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38(4):930–936, 2008.

10

Under review as a conference paper at ICLR 2018

A

G LOSSARY

Symbol
t
τ, T
a(t)
o(t)
r(t)
A
Ω
Rmin
Rmax
ετ
|X|
Ja, bK
E
γ
µ(ετ )
DT
ετ (t)
π
π∗
α
E+
α
SD
Φα
D
α
πD
P
K
σ
σ(τ )
Ex0 [f (x0 )]
Eµα
D
Eµ∗∞
σα
ρσabs (T )
O(f (x))
κ
Ξ
β
ξ
ρσss (T )
∆
†
∆†β
bxc
σ ESBAS
Θ(f (x))
σ∗

Designation
Reinforcement learning time aka RL-time
Meta-algorithm time aka meta-time
Action taken at RL-time t
Observation made at RL-time t
Reward received at RL-time t
Action set
Observation set
Lower bound of values taken by R
Upper bound of values taken by R
Trajectory collected at meta-time τ
Size of finite set/list/collection X
Ensemble of integers comprised between a and b
Space of trajectories
Discount factor of the decision process
Return of trajectory ετ aka objective function
Trajectory set collected until meta-time T
History of ετ until RL-time t
Policy
Optimal policy
Algorithm
Ensemble of trajectory sets
State space of algorithm α from trajectory set D
State space projection of algorithm α from trajectory set D
Policy learnt by algorithm α from trajectory set D
Algorithm set aka portfolio
Size of the portfolio
Meta-algorithm
Algorithm selected by meta-algorithm σ at meta-time τ
Expected value of f (x) conditionally to x = x0
α
Expected return of trajectories controlled by policy πD
Optimal expected return
Canonical meta-algorithm exclusively selecting algorithm α
Absolute pseudo-regret
Set of functions that get asymptotically dominated by κf (x)
Constant number
Stochastic K-armed bandit algorithm
Epoch index
Parameter of the UCB algorithm
Short-sighted pseudo-regret
Gap between the best arm and another arm
Index of the second best algorithm
Gap of the second best arm at epoch β
Rounding of x at the closest integer below
The ESBAS meta-algorithm
Set of functions asymptotically dominating κf (x) and dominated by κ0 f (x)
Best meta-algorithm among the canonical ones

11

First use
Section 2
Section 2
Figure 1
Figure 1
Figure 1
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2
Section 2.2
Section 2.2
Section 2.2
Section 2.2
Equation 1
Equation 1
Section 2.3
Section 2.3
Definition 1
Section 3
Theorem 3
Section 3
Section 3
Pseudo-code 2
Definition 2
Theorem 2
Theorem 2
Theorem 2
Theorem 2
Theorem 2
Table 1
Theorem 3

Under review as a conference paper at ICLR 2018

Symbol
p, ps , pu
η
νηp
U[a, b]
sf
Rps (sf )
R EF P ROP(η)
A SK R EPEAT
ACCEPT(η)
E ND D IAL
SERsu
scoreasr
N (x, v)
R EF I NSIST
R EF N EW P ROP
ACCEPT
β
Φα
φ0
φasr
φdif
φt
φnoise
simple
fast
simple-2
fast-2
n-1-simple
n-1-fast
n-1-simple-2
n-1-fast-2
constant-µ
ζ
P(x|y)

Designation
Player, system player, and (simulated) user player
Option to agree or disagree on
Cost of booking/selecting option ν for player p
Uniform distribution between a and b
Final state reached in a trajectory
Immediate reward received by the system player at the end of the dialogue
Dialogue act consisting in proposing option η
Dialogue act consisting in asking the other player to repeat what he said
Dialogue act consisting in accepting proposition η
Dialogue act consisting in ending the dialogue
Sentence error rate of system ps listening to user pu
Speech recognition score
Normal distribution of centre x and variance v 2
R EF P ROP(η), with η being the last proposed option
R EF P ROP(η), with η being the best option that has not been proposed yet
ACCEPT(η), with η being the last understood option proposition
-greedy exploration in function of epoch β
Set of features of algorithm α
Constant feature: always equal to 1 α
ASR feature: equal to the last recognition score
Cost feature: equal to the difference of cost of proposed and targeted options
RL-time feature
Noise feature
FQI with Φ = {φ0 , φasr , φdif , φt }
FQI with Φ = {φ0 , φasr , φdif }
FQI with Φ = {φ0 , φasr , φdif , φt , φasr φdif , φt φasr , φdif φt , φ2asr , φ2dif , φ2t }
FQI with Φ = {φ0 , φasr , φdif , φasr φdif , φ2asr , φ2dif }
FQI with Φ = {φ0 , φasr , φdif , φt , φnoise }
FQI with Φ = {φ0 , φasr , φdif , φnoise }
FQI with Φ = {φ0 , φasr , φdif , φt , φnoise , φasr φdif , φt φnoise , φasr φt ,
φdif φnoise , φasr φnoise , φdif φt , φ2asr , φ2dif , φ2t , φ2noise }
FQI with Φ = {φ0 , φasr , φdif , φt }
Non-learning algorithm with average performance µ
Number of noisy features added to the feature set
Probability that X = x conditionally to Y = y

12

First use
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.1
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Section C.1.2
Equation 35

Under review as a conference paper at ICLR 2018

B

T HEORETICAL ANALYSIS

The theoretical aspects of algorithm selection for reinforcement learning in general, and Epochal
Stochastic Bandit Algorithm Selection in particular, are thoroughly detailed in this section. The
proofs of the Theorems are provided in Sections E, F, and G. We recall and formalise the absolute
pseudo-regret definition provided in Section 2.3.
Definition 1 (Absolute pseudo-regret). The absolute pseudo-regret ρσabs (T ) compares the metaalgorithm’s expected return with the optimal expected return:
" T
#
X σ(τ )
σ
∗
ρabs (T ) = T Eµ∞ − Eσ
EµDσ
.
(4)
τ −1

τ =1

B.1

A SSUMPTIONS

The theoretical analysis is hindered by the fact that AS, not only directly influences the return
distribution, but also the trajectory set distribution and therefore the policies learnt by algorithms for
next trajectories, which will indirectly affect the future expected returns. In order to allow policy
comparison, based on relation on trajectory sets they are derived from, our analysis relies on two
assumptions.
Assumption 1 (More data is better data). The algorithms train better policies with a larger trajectory
set on average, whatever the algorithm that controlled the additional trajectory:
 α

∀D ∈ E + , ∀α, α0 ∈ P, Eµα
(5)
D ≤ Eα0 EµD∪εα0 .
Assumption 1 states that algorithms are off-policy learners and that additional data cannot lead to
performance degradation on average. An algorithm that is not off-policy could be biased by a specific
behavioural policy and would therefore transgress this assumption.
Assumption 2 (Order compatibility). If an algorithm trains a better policy with one trajectory set
than with another, then it remains the same, on average, after collecting an additional trajectory from
any algorithm:
h
i
h
i
α
α
α
(6)
∀D, D0 ∈ E + , ∀α, α0 ∈ P, Eµα
D < EµD 0 ⇒ Eα0 EµD∪εα0 ≤ Eα0 EµD 0 ∪εα0 .
Assumption 2 states that a performance relation between two policies trained on two trajectory sets
is preserved on average after adding another trajectory, whatever the behavioural policy used to
generate it. From these two assumptions, Theorem 1 provides an upper bound in order of magnitude
in function of the worst algorithm in the portfolio. It is verified for any meta-algorithm σ.
Theorem 1 (Not worse than the worst). The absolute pseudo-regret is bounded by the worst algorithm
absolute pseudo-regret in order of magnitude:


α
ρσabs (T ) ∈ O max ρσabs (T ) .
∀σ,
(7)
α∈P

Contrarily to what the name of Theorem 1 suggests, a meta-algorithm might be worse than the
worst algorithm (similarly, it can be better than the best algorithm), but not in order of magnitude.
Its proof is rather complex for such an intuitive result because, in order to control all the possible
outcomes, one needs to translate the selections of algorithm α with meta-algorithm σ into the
canonical meta-algorithm σ α ’s view.
B.2

S HORT- SIGHTED PSEUDO - REGRET ANALYSIS OF ESBAS

ESBAS intends to minimise the regret for not choosing the best algorithm at a given meta-time τ . It
is short-sighted: it does not intend to optimise the algorithms learning.
Definition 2 (Short-sighted pseudo-regret). The short-sighted pseudo-regret ρσss (T ) is the difference
between the immediate best expected return algorithm and the one selected:
" T 
#
X
σ(τ )
σ
α
ρss (T ) = Eσ
max EµDτσ−1 − EµDσ
.
(8)
τ =1

α∈P

13

τ −1

Under review as a conference paper at ICLR 2018

Theorem 2 (ESBAS short-sighted pseudo-regret). If the stochastic multi-armed bandit Ξ guarantees
a regret of order of magnitude O(log(T )/∆†β ), then:


blog(T )c
X β
ESBAS
.
(9)
ρσss
(T ) ∈ O 
†
∆
β
β=0
Theorem 2 expresses in order of magnitude an upper bound for the short-sighted pseudo-regret of
α0
α
ESBAS. But first, let define the gaps: ∆α
β = maxα0 ∈P Eµ σ ESBAS − Eµ σ ESBAS . It is the difference
D

D

2β −1

2β −1

of expected return between the best algorithm during epoch β and algorithm α. The smallest non null
†
gap at epoch β is noted: ∆†β = minα∈P,∆αβ >0 ∆α
β . If ∆β does not exist, i.e. if there is no non-null
gap, the regret is null.
Several upper bounds in order of magnitude on ρss (T ) can be easily deduced from Theorem 2,
depending on an order of magnitude of ∆†β . See the corollaries in Section F.1, Table 1 and more
generally Section 3 for a discussion.
B.3

ESBAS ABSOLUTE PSEUDO - REGRET ANALYSIS

The short-sighted pseudo-regret optimality depends on the meta-algorithm itself. For instance, a poor
deterministic algorithm might be optimal at meta-time τ but yield no new information, implying the
same situation at meta-time τ + 1, and so on. Thus, a meta-algorithm that exclusively selects the
deterministic algorithm would achieve a short-sighted pseudo-regret equal to 0, but selecting other
algorithms are, in the long run, more efficient. Theorem 2 is a necessary step towards the absolute
pseudo-regret analysis.
The absolute pseudo-regret can be decomposed between the absolute pseudo-regret of the best
canonical meta-algorithm (i.e. the algorithm that finds the best policy), the regret for not always
selecting the best algorithm, and potentially not learning as fast, and the short-sighted regret: the
regret for not gaining the returns granted by the best algorithm. This decomposition leads to Theorem
3 that provides an upper bound of the absolute pseudo-regret in function of the best canonical
meta-algorithm, and the short-sighted pseudo-regret.
But first let us introduce the fairness assumption. The fairness of budget distribution has been
formalised in Cauwet et al. (2015). It is the property stating that every algorithm in the portfolio has
as much resources as the others, in terms of computational time and data. It is an issue in most online
AS problems, since the algorithm that has been the most selected has the most data, and therefore
must be the most advanced one. A way to circumvent this issue is to select them equally, but, in an
online setting, the goal of AS is precisely to select the best algorithm as often as possible. Our answer
is to require that all algorithms in the portfolio are learning off-policy, i.e. without bias induced by
the behavioural policy used in the learning dataset. By assuming that all algorithms learn off-policy,
we allow information sharing Cauwet et al. (2015) between algorithms. They share the trajectories
they generate. As a consequence, we can assume that every algorithm, the least or the most selected
ones, will learn from the same trajectory set. Therefore, the control unbalance does not directly lead
to unfairness in algorithms performances: all algorithms learn equally from all trajectories. However,
unbalance might still remain in the exploration strategy if, for instance, an algorithm takes more
benefit from the exploration it has chosen than the one chosen by another algorithm. For analysis
purposes, Theorem 3 assumes the fairness of AS:
Assumption 3 (Learning is fair). If one trajectory set is better than another for training one given
algorithm, it is the same for other algorithms.
∀α, α0 ∈ P, ∀D, D0 ∈ E + ,

0

0

α
α
α
Eµα
D < EµD 0 ⇒ EµD ≤ EµD 0 .

(10)

Theorem 3 (ESBAS absolute pseudo-regret upper bound). Under assumption 3, if the stochastic
multi-armed bandit Ξ guarantees that the best arm has been selected in the T first episodes at least
T /K times, with high probability δT ∈ O(1/T ), then:

ESBAS
∗
ESBAS
T
(11)
+ ρσss
(T ) + κ log(T ),
∃κ > 0, ∀T ≥ 9K 2 , ρσabs (T ) ≤ (3K + 1)ρσabs 3K
14

Under review as a conference paper at ICLR 2018

α

where meta-algorithm σ ∗ selects exclusively algorithm α∗ = argminα∈P ρσabs (T ).
Successive and Median Elimination (Even-Dar et al., 2002) and Upper Confidence Bound (Auer et al.,
2002a) under some conditions (Audibert & Bubeck, 2010) are examples of appropriate Ξ satisfying
both conditions stated in Theorems 2 and 3. Again, see Table 1 and more generally Section 3 for a
discussion of those bounds.

15

Under review as a conference paper at ICLR 2018

C

E XPERIMENTAL DETAILS

C.1
C.1.1

D IALOGUE EXPERIMENTS DETAILS
T HE N EGOTIATION D IALOGUE G AME

ESBAS practical efficiency is illustrated on a dialogue negotiation game (Laroche & Genevay, 2016)
that involves two players: the system ps and a user pu . Their goal is to find an agreement among
4 alternative options. At each dialogue, for each option η, players have a private uniformly drawn
cost νηp ∼ U[0, 1] to agree on it. Each player is considered fully empathetic to the other one. As a
result, if the players come to an agreement, the system’s immediate reward at the end of the dialogue
is Rps (sf ) = 2 − νηps − νηpu , where sf is the state reached by player ps at the end of the dialogue,
and η is the agreed option; if the players fail to agree, the final immediate reward is Rps (sf ) = 0,
and finally, if one player misunderstands and agrees on a wrong option, the system gets the cost of
selecting option η without the reward of successfully reaching an agreement: Rps (sf ) = −νηps − νηp0u .
Players act each one in turn, starting randomly by one or the other. They have four possible actions.
First, R EF P ROP(η): the player makes a proposition: option η. If there was any option previously
proposed by the other player, the player refuses it. Second, A SK R EPEAT: the player asks the other
player to repeat its proposition. Third, ACCEPT(η): the player accepts option η that was understood
to be proposed by the other player. This act ends the dialogue either way: whether the understood
proposition was the right one or not. Four, E ND D IAL: the player does not want to negotiate anymore
and ends the dialogue with a null reward.
Understanding through speech recognition of system ps is assumed to be noisy: with a sentence error
rate of probability SERsu = 0.3, an error is made, and the system understands a random option instead of the one that was actually pronounced. In order to reflect human-machine dialogue asymmetry,
the simulated user always understands what the system says: SERus = 0. We adopt the way Khouzaimi et al. (2015) generate speech recognition confidence scores: scoreasr = 1+e1−X where X ∼
N (x, 0.2). If the player understood the right option x = 1, otherwise x = 0.
The system, and therefore the portfolio algorithms, have their action set restrained to five non parametric actions: R EF I NSIST ⇔ R EF P ROP(ηt−1 ), ηt−1 being the option lastly proposed by the system;
R EF N EW P ROP ⇔ R EF P ROP(η), η being the preferred one after ηt−1 , A SK R EPEAT, ACCEPT⇔
ACCEPT(η), η being the last understood option proposition and E ND D IAL.
C.1.2

L EARNING ALGORITHMS

All learning algorithms are using Fitted-Q Iteration (Ernst et al., 2005), with a linear parametrisation
and an β -greedy exploration : β = 0.6β , β being the epoch number. Six algorithms differing by
their state space representation Φα are considered:
• simple: state space representation of four features: the constant feature φ0 = 1, the last recognition score feature φasr , the difference between the cost of the proposed option and the next
0.1t
best option φdif , and finally an RL-time feature φt = 0.1t+1
. Φα = {φ0 , φasr , φdif , φt }.
• fast: Φα = {φ0 , φasr , φdif }.
• simple-2: state space representation of ten second order polynomials of simple features.
Φα = {φ0 , φasr , φdif , φt , φ2asr , φ2dif , φ2t , φasr φdif , φasr φt , φt φdif }.
• fast-2: state space representation of six second order polynomials of fast features. Φα = {φ0 ,
φasr , φdif , φ2asr , φ2dif , φasr φdif }.
• n-ζ-{simple/fast/simple-2/fast-2}: Versions of previous algorithms with ζ additional features
of noise, randomly drawn from the uniform distribution in [0, 1].
• constant-µ: the algorithm follows a deterministic policy of average performance µ without
exploration nor learning. Those constant policies are generated with simple-2 learning from
a predefined batch of limited size.
16

Under review as a conference paper at ICLR 2018

C.1.3

E VALUATION PROTOCOL

In all our experiments, ESBAS has been run with UCB parameter ξ = 1/4. We consider 12 epochs.
The first and second epochs last 20 meta-time steps, then their lengths double at each new epoch,
for a total of 40,920 meta-time steps and as many trajectories. γ is set to 0.9. The algorithms and
ESBAS are playing with a stationary user simulator built through Imitation Learning from realhuman data. All the results are averaged over 1000 runs. The performance figures plot the curves of
algorithms individual performance σ α against the ESBAS portfolio control σ ESBAS in function of the
epoch (the scale is therefore logarithmic in meta-time). The performance is the average return of the
reinforcement learning return: it equals γ || Rps (sf ) in the negotiation game. The ratio figures plot
the average algorithm selection proportions of ESBAS at each epoch. We define the relative pseudo
regret as the difference between the ESBAS absolute pseudo-regret and the absolute pseudo-regret
of the best canonical meta-algorithm. All relative pseudo-regrets, as well as the gain for not having
chosen the worst algorithm in the portfolio, are provided in Table 2. Relative pseudo-regrets have a
95% confidence interval about ±6 ≈ ±1.5 × 10−4 per trajectory.
C.1.4

A SSUMPTIONS TRANSGRESSIONS

Several results show that, in practice, the assumptions are transgressed. Firstly, we observe that
Assumption 3 is transgressed. Indeed, it states that if a trajectory set is better than another for a
given algorithm, then it’s the same for the other algorithms. Still, this assumption infringement does
not seem to harm the experimental results. It even seems to help in general: while this assumption
is consistent curriculum learning, it is inconsistent with the run adaptation property advanced in
Subsection 6 that states that an algorithm might be the best on some run and another one on other
runs.
And secondly, off-policy reinforcement learning algorithms exist, but in practice, we use state space
representations that distort their off-policy property (Munos et al., 2016). However, experiments do
not reveal any obvious bias related to the off/on-policiness of the trajectory set the algorithms train
on.
C.2

Q* BERT EXPERIMENT DETAILS

The three DQN networks (small, large, and huge) are built in a similar fashion, with relu activations
at each layer except for the output layer which is linear, with RMSprop optimizer (ρ = 0.95 and
 = 10−7 ), and with He uniform initialisation. The hyperparameters used for training them are also
the same and equal to the ones presented in the table hereinafter:
hyperparameter

value

minibatch size

32

replay memory size

1 × 106

agent history length

4

target network update frequency
discount factor

5 × 104
0.99

action repeat

20

update frequency

20
2.5 × 10−4

learning rate

5 × t−1 × 10−6

exploration parameter 

5 × 10−4

replay start size
no-op max

30
17

Under review as a conference paper at ICLR 2018

Only their shapes differ:
• small has a first convolution layer with a 4x4 kernel and a 2x2 stride, and a second convolution layer with a 4x4 kernel and a 2x2 stride, followed by a dense layer of size 128, and
finally the output layer is also dense.
• large has a first convolution layer with a 8x8 kernel and a 4x4 stride, and a second convolution
layer with a 4x4 kernel and a 2x2 stride, followed by a dense layer of size 256, and finally
the output layer is also dense.
• huge has a first convolution layer with a 8x8 kernel and a 4x4 stride, a second convolution
layer with a 4x4 kernel and a 2x2 stride, and a third convolution layer with a 3x3 kernel and
a 1x1 stride, followed by a dense layer of size 512, and finally the output layer is also dense.

18

Under review as a conference paper at ICLR 2018

D

E XTENDED RESULTS OF THE DIALOGUE EXPERIMENTS

Portfolio
w. best
simple-2 + fast-2
35
simple + n-1-simple-2
-73
simple + n-1-simple
3
simple-2 + n-1-simple-2
-12
all-4 + constant-1.10
21
all-4 + constant-1.11
-21
all-4 + constant-1.13
-10
all-4
-28
all-2-simple + constant-1.08
-41
all-2-simple + constant-1.11
-40
all-2-simple + constant-1.13
-123
all-2-simple
-90
fast + simple-2
-39
simple-2 + constant-1.01
169
simple-2 + constant-1.11
53
simple-2 + constant-1.11
57
simple + constant-1.08
54
simple + constant-1.10
88
simple + constant-1.14
-6
all-4 + all-4-n-1 + constant-1.09
25
all-4 + all-4-n-1 + constant-1.11
20
all-4 + all-4-n-1 + constant-1.14
-16
all-4 + all-4-n-1
-10
all-2-simple + all-2-n-1-simple
-80
4*n-2-simple
-20
4*n-3-simple
-13
8*n-1-simple-2
-22
simple-2 + constant-0.97 (no reset)
113
simple-2 + constant-1.05 (no reset)
23
simple-2 + constant-1.09 (no reset)
-19
simple-2 + constant-1.13 (no reset)
-16
simple-2 + constant-1.14 (no reset)
-125

w. worst
-181
-131
-2
-38
-2032
-1414
-561
-275
-2734
-2013
-799
-121
-256
-5361
-1380
-1288
-2622
-1565
-297
-2308
-1324
-348
-142
-181
-20
-13
-22
-7131
-3756
-2170
-703
-319

Table 2: ESBAS pseudo-regret after 12 epochs (i.e. 40,920 trajectories) compared with the best and
the worst algorithms in the portfolio, in function of the algorithms in the portfolio (described in the
first column). The ’+’ character is used to separate the algorithms. all-4 means all the four learning
algorithms described in Section C.1.2 simple + fast + simple-2 + fast-2. all-4-n-1 means the same four
algorithms with one additional feature of noise. Finally, all-2-simple means simple + simple-2 and
all-2-n-1-simple means n-1-simple + n-1-simple-2. On the second column, the redder the colour, the
worse ESBAS is achieving in comparison with the best algorithm. Inversely, the greener the colour
of the number, the better ESBAS is achieving in comparison with the best algorithm. If the number
is neither red nor green, it means that the difference between the portfolio and the best algorithm is
insignificant and that they are performing as good. This is already an achievement for ESBAS to
be as good as the best. On the third column, the bluer the cell, the weaker is the worst algorithm
in the portfolio. One can notice that positive regrets are always triggered by a very weak worst
algorithm in the portfolio. In these cases, ESBAS did not allow to outperform the best algorithm in
the portfolio, but it can still be credited with the fact it dismissed efficiently the very weak algorithms
in the portfolio.
19

Under review as a conference paper at ICLR 2018

E

N OT WORSE THAN THE WORST

Theorem 1 (Not worse than the worst). The absolute pseudo-regret is bounded by the worst algorithm
absolute pseudo-regret in order of magnitude:


σ
σα
∀σ,
ρabs (T ) ∈ O max ρabs (T ) .
(7)
α∈P

Proof. From Definition 1:
"
ρσabs (T )

=

T Eµ∗∞

− Eσ

T
X

#
σ(τ )
EµDσ
τ −1

,

(12a)

τ =1





σ
|subα (DT
)|

ρσabs (T ) = T Eµ∗∞ −

X

X

Eσ 

Eµα
D σα

τ −1
i

i=1

α∈P


ρσabs (T ) =

X

,

(12b)


σ
|subα (DT
)|

Eσ |subα (DTσ )|Eµ∗∞ −

X

Eµα
D σα
τ

i=1

α∈P

i

−1

,

(12c)

where subα (D) is the subset of D with all the trajectories generated with algorithm α, where τiα is
the index of the ith trajectory generated with algorithm α, and where |S| is the cardinality of finite set
S. By convention, let us state that Eµα
= Eµ∗∞ if |subα (DTσ )|< i. Then:
D σα
τ −1
i

ρσabs (T )

=

T
XX


Eσ Eµ∗∞ − Eµα
D σα


.

τ −1
i

α∈P i=1

(13)

To conclude, let us prove by mathematical induction the following inequality:


h
i
α
Eσ Eµα
≥ Eσα Eµα
σ
D α
Dσ
τ −1
i

i−1

is true by vacuity for i = 0: both left and right terms equal Eµα
∅ . Now let us assume the property true
for i and prove it for i + 1:





 ,
Eσ Eµα
= Eσ Eµα
(14a)
D σα
τ
−1
i+1

Dτσα −1 ∪εα ∪ Dτσα
i


Eσ Eµα
D σα



τ
−1
i+1

\Dτσα
i

#
Dτσα −1 ∪εα ∪

α −1
Sτi+1

i



−1

"
= Eσ Eµ

τ
−1
i+1


Eσ Eµα
D σα

i+1

τ =τ α +1
i

εσ(τ )

,

"

(14b)
#

= Eσ Eµ

Sτ α −τiα −1 σ(τ α +τ )
Dτσα −1 ∪εα ∪ τi+1
ε i
=1

.

(14c)

i

If |subα (DTσ )|≥ i + 1, by applying mathematical induction assumption, then by applying Assumption
2 and finally by applying Assumption 1 recursively, we infer that:


h
i
α
α
Eσ EµDσα
≥ Eσα Eµα
,
(15a)
Dσ
τ −1
i


Eσ Eµα
D σα
τ
i

20

i−1


∪εα
−1

h
i
α
≥ Eσα Eµα
,
σ
α
D
∪ε
i−1

(15b)

Under review as a conference paper at ICLR 2018


Eσ Eµα
D σα
τ
i


∪εα
−1

"

i
h
α
,
≥ Eσα Eµα
Dσ

(15c)

i
h
α
.
≥ Eσα Eµα
Dσ

(15d)

i

#
Sτ α −τiα −1 σ(τ α +τ )
Dτσα −1 ∪εα ∪ τi+1
ε i
=1

Eσ Eµ

i

i

If |subα (DTσ )|< i + 1, the same inequality is straightforwardly obtained, since, by convention
EµkD k = Eµ∗∞ , and since, by definition ∀D ∈ E + , ∀α ∈ P, Eµ∗∞ ≥ Eµα
D.
τ
i+1

The mathematical induction proof is complete. This result leads to the following inequalities:
ρσabs (T ) ≤

T
XX

i
h
α
,
Eσα Eµ∗∞ − Eµα
σ
D

(16a)

i−1

α∈P i=1

ρσabs (T ) ≤

X

α

ρσabs (T ) ,

(16b)

α∈P
α

ρσabs (T ) ≤ K max ρσabs (T ) ,
α∈P

(16c)

which leads directly to the result:
∀σ,

ρσabs (T ) ∈ O




k
max ρσabs (T ) .

αk ∈P

(17)

This proof may seem to the reader rather complex for such an intuitive and loose result but algorithm
selection σ and the algorithms it selects may act tricky. For instance selecting algorithm α only
when the collected trajectory sets contains misleading examples (i.e. with worse expected return
than with an empty trajectory set) implies that the following unintuitive inequality is always true:
α
Eµα
Dτσ−1 ≤ EµD σα . In order to control all the possible outcomes, one needs to translate the selections
τ −1
of algorithm α into σ α ’s view.

21

Under review as a conference paper at ICLR 2018

F

ESBAS SHORT- SIGHTED PSEUDO - REGRET UPPER ORDER OF MAGNITUDE

Theorem 2 (ESBAS short-sighted pseudo-regret). If the stochastic multi-armed bandit Ξ guarantees
a regret of order of magnitude O(log(T )/∆†β ), then:


blog(T )c
X β
ESBAS
.
(9)
ρσss
(T ) ∈ O 
†
∆
β
β=0
α
Proof. By simplification of notation, Eµα
Dβ = Eµ σ ESBAS . From Definition 2:
D

2β −1

"
ESBAS
ρσss
(T )

= Eσ ESBAS

T 
X
τ =1

"
ESBAS
ρσss
(T )

= Eσ ESBAS

T 
X
τ =1

max Eµα σ ESBAS
Dτ −1
α∈P
max Eµα
βτ
α∈P

−

σ ESBAS (τ )

− Eµ

#

ESBAS

Dτσ−1

σ ESBAS (τ )
Eµβτ

,

#
,

(18b)


ESBAS

ρσss

blog2 (T )c 2β+1 −1 

X

(T ) ≤ Eσ ESBAS 

X

ESBAS
ρσss
(T )

blog2 (T )c

≤

X

ESBAS

ρσss

σ

max Eµα
β − Eµβ

ESBAS

(τ )




,

α∈P

τ =2β

β=0

(18a)

(18c)

(β),

(18d)

β=0
ESBAS

(β) for each
where βτ is the epoch of meta-time τ . A bound on short-sighted pseudo-regret ρσss
epoch β can then be obtained by the stochastic bandit Ξ regret bounds in O (log(T )/∆):

ESBAS

ρσss

2β+1
X−1 

(β) = Eσ ESBAS 

σ

max Eµα
β − Eµβ

ESBAS

α∈P

τ =2β

(τ )




,

(19a)


log(2β )
,
∆β
 
β
σ ESBAS
ρss
(β) ∈ O
,
∆β
ESBAS

ρσss

⇔ ∃κ1 > 0,

ESBAS

ρσss
where



(β) ∈ O

(β) ≤

(19b)

(19c)

κ1 β
,
∆β

(19d)

X 1
1
=
∆β
∆α
β

(19e)

α∈P

and where


 +∞
∆α
=
β
 max

0

α
if Eµα
β = maxα0 ∈P Eµβ ,
0

α0 ∈P

α
Eµα
β − Eµβ

(19f)

otherwise.

Since we are interested in the order of magnitude, we can once again only consider the upper bound
of ∆1β :
!
[
1
1
∈
O
,
(20a)
∆β
∆α
β
α∈P

22

Under review as a conference paper at ICLR 2018

1
1
∈ O max α
α∈P ∆β
∆β

!
,

(20b)

1
κ2
≤ †,
∆β
∆β

⇔ ∃κ2 > 0,

(20c)

where the second best algorithm at epoch β such that ∆†β > 0 is noted αβ† . Injected in Equation 18d,
it becomes:
ESBAS

ρσss

blog2 (T )c

(T ) ≤ κ1 κ2

X

β

β=0

∆†β

,

(21)

which proves the result.
F.1

C OROLLARIES OF T HEOREM 2

Corollary 1. If

∆†β

∈ Θ (1), then

ESBAS
ρσss
(T )

!
log2 (T )
, where ∆†∞ = µ∗∞ − µ†∞ > 0.
∆†∞

∈O

Proof. ∆†β ∈ Ω (1) means that only one algorithm α∗ converges to the optimal asymptotic performance µ∗∞ and that ∃∆†∞ = µ∗∞ − µ†∞ > 0 such that ∀2 > 0, ∃β1 ∈ N, such that ∀β ≥ β1 ,
∆†β > ∆†∞ − . In this case, the following bound can be deduced from equation 21:
blog(T )c
ESBAS

ρσss

ESBAS

ρσss

(T ) ≤ κ4 +

(T ) ≤ κ4 +

X

κ1 κ2

β=β1

∆†∞ − 

β,

(22a)

κ1 κ2 log2 (T )
,
2(∆†∞ − )

(22b)

where κ4 is a constant equal to the short-sighted pseudo-regret before epoch β1 :
ESBAS

κ4 = ρσss

2β1 −1



(23)

Equation 22b directly leads to the corollary.




†
ESBAS
†
Corollary 2. If ∆†β ∈ Θ β −m , then ρσss
(T ) ∈ O logm +2 (T ) .
Proof. If ∆†β decreases slower than polynomially in epochs, which implies decreasing polylogarith†

mically in meta-time, i.e. ∃κ5 > 0, ∃m† > 0, ∃β2 ∈ N, such that ∀β ≥ β2 , ∆†β > κ5 β −m , then,
from Equation 21:
blog(T )c
ESBAS

ρσss

X

(T ) ≤ κ6 +

β=β2
blog(T )c
ESBAS

ρσss

X

(T ) ≤ κ6 +

β=β2
ESBAS

ρσss

(T ) ≤

κ1 κ2
β,
κ5 β −m†

(24a)

κ1 κ2 m† +1
β
,
κ5

(24b)

†
κ1 κ2
logm +2 (T ),
κ5

23

(24c)

Under review as a conference paper at ICLR 2018

where κ6 is a constant equal to the short-sighted pseudo-regret before epoch β2 :

ESBAS
2β2 −1 .
κ6 = ρσss

(25)

Equation 24c directly leads to the corollary.


 †

ESBAS
†
Corollary 3. If ∆†β ∈ Θ T −c , then ρσss
(T ) ∈ O T c log(T ) .
Proof. If ∆†β decreases slower than a fractional power of meta-time T , then ∃κ7 > 0, 0 < c† < 1,
†

∃β3 ∈ N, such that ∀β ≥ β3 , ∆†β > κ7 T −c , and therefore, from Equation 21:
blog(T )c
ESBAS

ρσss

(T ) ≤ κ8 +

X
β=β3
blog(T )c

ESBAS

ρσss

(T ) ≤ κ8 +

X

κ1 κ2

β=β3

κ7 (2β )

−c†

blog(T )c
ESBAS

ρσss

(T ) ≤ κ8 +

κ1 κ2
β,
κ7 τ −c†

X
β=β3

(26a)

β,

κ1 κ2  c† β
β 2
,
κ7

where κ8 is a constant equal to the short-sighted pseudo-regret before epoch β3 :

ESBAS
κ8 = ρσss
2β3 −1 .

(26b)

(26c)

(27)

The sum in Equation 26c is solved as follows:
n
X

ixi = x

n
X

ixi−1 ,

i =i0

i=i0

n
X


n
X
d xi
,
ix = x
dx
i=i

i =i0
n
X

i

i

ix = x

d

Pn

i=i0

dx

d

ixi = x

i =i0
n
X

(28b)

0

i =i0

n
X

(28a)

ixi =

i =i0

xi


,

(28c)


xn+1 − xi0
x−1
,
dx

(28d)


x
(x − 1)nxn − xn − (x − 1)i0 xi0 −1 + xi0 .
2
(x − 1)

(28e)

This result, injected in Equation 26c, induces that ∀3 > 0, ∃T1 ∈ N, ∀T ≥ T1 :
†

ESBAS
ρσss
(T )

κ1 κ2 (1 + 0 )2c
†
≤ κ8 +
log(T )2c log(T ) ,
κ7 (2c† − 1)

ESBAS
ρσss
(T )

κ1 κ2 (1 + 0 )2c c†
≤ κ8 +
T log(T ),
κ7 (2c† − 1)

(29a)

†

which proves the corollary.

24

(29b)

Under review as a conference paper at ICLR 2018

G

ESBAS ABOLUTE PSEUDO - REGRET BOUND

Theorem 3 (ESBAS absolute pseudo-regret upper bound). Under assumption 3, if the stochastic
multi-armed bandit Ξ guarantees that the best arm has been selected in the T first episodes at least
T /K times, with high probability δT ∈ O(1/T ), then:
ESBAS

ρσabs

∃κ > 0, ∀T ≥ 9K 2 ,

∗

T
3K

(T ) ≤ (3K + 1)ρσabs



ESBAS

+ ρσss

(T ) + κ log(T ),

(11)

α

where meta-algorithm σ ∗ selects exclusively algorithm α∗ = argminα∈P ρσabs (T ).
Proof. The ESBAS absolute pseudo-regret is written with the following notation simplifications :
ESBAS
Dτ −1 = Dτσ−1 and kτ = σ ESBAS (τ ):
"
ESBAS
ρσabs (T )

=

T Eµ∗∞

− Eσ ESBAS

T
X
τ =1

"
ESBAS

ρσabs

(T ) = T Eµ∗∞ − Eσ ESBAS

T
X

σ ESBAS (τ )

Eµ

#

ESBAS

Dτσ−1

,

(30a)

#
EµkDττ −1 .

(30b)

τ =1

Let σ ∗ denote the algorithm selection selecting exclusively α∗ , and α∗ be the algorithm minimising
the algorithm absolute pseudo-regret:
k

α∗ = argmin ρσabs (T ).

(31)

αk ∈P

Note that σ ∗ is the optimal constant algorithm selection at horizon T , but it is not necessarily the
optimal algorithm selection: there might exist, and there probably exists a non constant algorithm
selection yielding a smaller pseudo-regret.
ESBAS

The ESBAS absolute pseudo-regret ρσabs (T ) can be decomposed into the pseudo-regret for not
having followed the optimal constant algorithm selection σ ∗ and the pseudo-regret for not having
selected the algorithm with the highest return, i.e. between the pseudo-regret on the trajectory and the
pseudo-regret on the immediate optimal return:
"
ESBAS
ρσabs (T )

=

T Eµ∗∞

− Eσ ESBAS

T
X

#
Eµ∗sub∗ (Dτ −1 )

(32)

τ =1

"
+ Eσ ESBAS

T
X

#
Eµ∗sub∗ (Dτ −1 ) − Eσ ESBAS

τ =1

"

T
X

#
EµkDττ −1 ,

τ =1

∗
where Eµ∗sub∗ (Dτ −1 ) is the expected return of policy πsub
, learnt by algorithm α∗ on trajectory
∗ (D
τ −1 )
set sub∗ (Dτ −1 ), which is the trajectory subset of Dτ −1 obtained by removing all trajectories that
were not generated with algorithm α∗ .

First line of Equation 32 can be rewritten as follows:
"
T Eµ∗∞

− Eσ ESBAS

T
X
τ =1

#
Eµ∗sub∗ (Dτ −1 )

=

T 
X

h
i
Eµ∗∞ − Eσ ESBAS Eµ∗sub∗ (Dτ −1 ) .

(33)

τ =1

The key point in Equation 33 is to evaluate the size of sub∗ (Dτ −1 ).
On the one side, Assumption 3 of fairness states that one algorithm learns as fast as any another over
any history. The asymptotically optimal algorithm(s) when τ → ∞ is(are) therefore the same one(s)
25

Under review as a conference paper at ICLR 2018

whatever the the algorithm selection is. On the other side, let 1 − δτ denote the probability, that at
time τ , the following inequality is true:

τ −1
|sub (Dτ −1 ) |≥
.
3K


∗

(34)

With probability δτ , inequality 34 is not guaranteed and nothing can be inferred about Eµ∗sub∗ (Dτ −1 ) ,
τ −1
except it is bounded under by Rmin /(1 − γ). Let E3K
be the subset of E τ −1 such that ∀D ∈
τ −1
∗
E3K , |sub (D)|≥ b(τ − 1)/3Kc. Then, δτ can be expressed as follows:
X

δτ =

P(D|σ ESBAS ).

(35)

τ −1
D∈E τ −1 \E3K

With these new notations:
h
i
Eµ∗∞ − Eσ ESBAS Eµ∗sub∗ (Dτ −1 ) ≤ Eµ∗∞ −

X

P(D|σ ESBAS )Eµ∗sub∗ (D) − δτ

τ −1
D∈E3K

Rmin
, (36a)
1−γ

h
i
Eµ∗∞ − Eσ ESBAS Eµ∗sub∗ (Dτ −1 )


X
Rmin
∗
ESBAS
∗
∗
.
≤ (1 − δτ )Eµ∞ −
P(D|σ
)Eµsub∗ (D) + δτ Eµ∞ −
1−γ
τ −1

(36b)

D∈E3K

Let consider E ∗ (α, N ) the set of all sets D such that |subα (D)|= N and such that last trajectory
in D was generated by α. Since ESBAS, with Ξ, a stochastic bandit with regret in O(log(T )/∆),
guarantees that all algorithms will eventually be selected an infinity of times, we know that :
X

∀α ∈ P, ∀N ∈ N,

P(D|σ ESBAS ) = 1.

(37)

D ∈E + (α,N )

By applying recursively Assumption 2, one demonstrates that:
X
D

∈E + (α,N )

X

X

P(D|σ ESBAS )Eµα
subα (D) ≥

P(D|σ α )Eµα
D,

(38a)

D∈E N

h
i
α
P(D|σ ESBAS )Eµα
subα (D) ≥ Eσ α EµD σα .

(38b)

N

D ∈E + (α,N )

One also notices the following piece-wisely domination from applying recursively Assumption 1:


X
X
(1 − δτ )Eµ∗∞ −
P(D|σ ESBAS )Eµ∗sub∗ (D) =
P(D|σ ESBAS ) Eµ∗∞ − Eµ∗sub∗ (D) ,
τ −1
D ∈E3K

τ −1
D∈E3K

(39a)
(1 −

δτ )Eµ∗∞

−

X
τ −1
D ∈E3K



P(D|σ ESBAS ) Eµ∗∞ − Eµ∗sub∗ (D) ,

X

P(D|σ ESBAS )Eµ∗sub∗ (D) ≤

−1
D∈E + (α∗ ,b τ3K
c)&|D|≤τ −1

(39b)
(1 − δτ )Eµ∗∞
X
−
P(D|σ ESBAS )Eµ∗sub∗ (D) ≤
τ −1
D ∈E3K



P(D|σ ESBAS ) Eµ∗∞ − Eµ∗sub∗ (D) ,

X
−1
D∈E + (α∗ ,b τ3K
c)

26

(39c)

Under review as a conference paper at ICLR 2018

X

(1 − δτ )Eµ∗∞ −
D

X

P(D|σ ESBAS )Eµ∗sub∗ (D) ≤ Eµ∗∞ −

P(D|σ ESBAS )Eµ∗sub∗ (D) .

−1
D∈E + (α∗ ,b τ3K
c)

τ −1
∈E3K

(39d)
Then, by applying results from Equations 38b and 39d into Equation 36b, one obtains:

Eµ∗∞

− Eσ ESBAS

h

Eµ∗sub∗ (Dτ −1 )

i

Eµ∗∞

≤



∗
− Eσ∗ Eµα
Dσ

τ −1
3K



 + δτ


Eµ∗∞


Rmin
−
. (40)
1−γ

Next, the terms in the first line of Equation 32 are bounded as follows:
"
T Eµ∗∞ − Eσ ESBAS

T
X



#

Eµ∗sub∗ (Dτ −1 ) ≤ T Eµ∗∞ − Eσ∗ 

+

T
X

δτ

τ =1

T Eµ∗∞ − Eσ ESBAS

T
X


∗
Eµα
Dσ

τ −1
3K

τ =1

τ =1

"

T
X

#

T

Eµ∗sub∗ (Dτ −1 ) ≤



(41a)



Rmin
Eµ∗∞ −
,
1−γ

∗

T
b 3K
c

τ =1



ρσabs

j
 
 T
Rmin X
T k
δ(41b)
+ Eµ∗∞ −
τ.
3K
1 − γ τ =1

Again, for T ≥ 9K 2 :
"
T Eµ∗∞

− Eσ ESBAS

T
X

#
Eµ∗sub∗ (Dτ −1 )

≤ (3K

∗
+ 1)ρσabs

τ =1



T
3K




+

Eµ∗∞

 T
Rmin X
δτ . (42)
−
1 − γ τ =1

Regarding the first term in the second line of Equation 32, from applying recursively Assumption 2:
h
i


Eσ ESBAS Eµ∗sub∗ (Dτ ) ≤ Eσ ESBAS Eµ∗Dτ ,

(43a)



h
i
Eσ ESBAS Eµ∗sub∗ (Dτ ) ≤ Eσ ESBAS max Eµα
Dτ .

(43b)

α∈P

From this observation, one directly concludes the following inequality:
"
Eσ ESBAS

T
X

#
Eµ∗sub∗ (Dτ )

"
− Eσ ESBAS

τ =1

T
X

#
EµkDττ

"
≤ Eσ ESBAS

τ =1

T
X
τ =1

max Eµα
Dτ
α∈P

−

T
X

#
EµkDττ

,

τ =1

(44a)
"
Eσ ESBAS

T
X

#

"

Eµ∗sub∗ (Dτ ) − Eσ ESBAS

τ =1

T
X

#
EµkDττ

ESBAS

≤ ρσss

(T ).

(44b)

τ =1

Injecting results from Equations 42 and 44b into Equation 32 provides the result:
ESBAS
ρσabs (T )

≤ (3K +

∗
1)ρσabs



T
3K


+

ESBAS
ρσss
(T )


+

Eµ∗∞

 T
Rmin X
−
δτ .
1 − γ τ =1

(45)

We recall here that the stochastic bandit algorithm Ξ was assumed to guarantee to try the best
algorithm α∗ at least N/K times with high probability 1 − δN and δN ∈ O(N −1 ). Now, we show
that at any time, the longest stochastic bandit run (i.e. the epoch that experienced the biggest number
of pulls) lasts at least N = τ3 : at epoch βτ , the meta-time spent on epochs before βτ − 2 is equal to
27

Under review as a conference paper at ICLR 2018

Pβτ −2

2β = 2βτ −1 ; the meta-time spent on epoch βτ − 1 is equal to 2βτ −1 ; the meta-time spent
on epoch β is either below 2βτ −1 , in which case, the meta-time spent on epoch βτ − 1 is higher
than τ3 , or the meta-time spent on epoch β is over 2βτ −1 and therefore higher than τ3 . Thus, ESBAS
is guaranteed to try the best algorithm α∗ at least τ /3K times with high probability 1 − δτ and
δτ ∈ O(τ −1 ). As a result:

 T


Rmin X κ3
ESBAS
∗
ESBAS
T
∃κ3 > 0, ρσabs (T ) ≤ (3K + 1)ρσabs
+ ρσss
, (46)
(T ) + Eµ∗∞ −
3K
1 − γ τ =1 τ


ESBAS
∗
ESBAS
T
∃κ > 0, ρσabs (T ) ≤ (3K + 1)ρσabs
+ ρσss
(T ) + κ log(T ),
(47)
3K


Rmin
with κ = κ3 Eµ∗∞ −
, which proves the theorem.
1−γ
β=0

28

