Published as a conference paper at ICLR 2018 REINFORCEMENT LEARNING ALGORITHM SELECTION
This paper formalises the problem of online algorithm selection in the context of Reinforcement Learning (RL). 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.
The paper considers the problem of online selection of RL algorithms. An algorithm selection (AS) strategy called ESBAS is proposed. It works in a sequence of epochs of doubling length, in the following way: the algorithm selection is based on a UCB strategy, and the parameters of the algorithms are not updated within each epoch (in order that the returns obtained by following an algorithm be iid). This selection allows ESBAS to select a sequence of algorithms within an epoch to generate a return almost as high as the return of the best algorithm, if no learning were made. This weak notion of regret is captured by the short-sighted pseudo regret. 
Now a bound on the global regret is much harder to obtain because there is no way of comparing, without additional assumption, the performance of a sequence of algorithms to the best algorithm had this one been used to generate all trajectories from the beginning. Here it is assumed that all algorithms learn off-policy. However this is not sufficient, since learning off-policy does not mean that an algorithm is indifferent to the behavior policy that has generated the data. Indeed even for the most basic off-policy algorithms, such as Q-learning, the way data have been collected is extremely important, and collecting transitions using that algorithm (such as epsilon-greedy) is certainly better than following an arbitrary policy (such as uniformly randomly, or following an even poorer policy which would not explore at all). However the authors seem to state an equivalence between learning off-policy and fairness of learning (defined in Assumption 3). For example in their conclusion they mention “Fairness of algorithm evaluation is granted by the fact that the RL algorithms learn off-policy”. This is not correct. I believe the main assumption made in this paper is the Assumption 3 (and not that the algorithms learn off-policy) and this should be dissociated from the off-policy learning. 
This fairness assumption is very a strong assumption that does not seem to be satisfied by any algorithm that I can think of. Indeed, consider D being the data generated by following algorithm alpha, and let D’ be the data generated by following algorithm alpha’. Then it makes sense that the performance of algorithm alpha is better when trained on D rather than D’, and alpha’ is better when trained on D’ than on D. This contradicts the fairness assumption. 
This being said, I believe the merit of this paper is to make explicit the actual assumptions required to be able to derive a bound on the global regret. So although the fairness assumption is unrealistic, it has the benefit of existing…
So in the end I liked the paper because the authors tried to address this difficult problem of algorithmic selection for RL the best way they could. Maybe future work will do better but at least this a first step in an interesting direction.
Now, I would have liked a comparison with other algorithms for algorithm selection, like:
- explore-then-exploit, where a fraction of T is used to try each algorithm uniformly, then the best one is selected and played for the rest of the rounds.
- Algorithms that have been designed for curriculum learning, such as some described in [Graves et al., Automated Curriculum Learning for Neural Networks, 2017], where a proxy for learning progress is used to estimate how much an algorithm can learn from data.
Other comments:
- Table 1 is really incomprehensible. Even after reading the Appendix B, I had a hard time understanding these results.
- I would suggest adding the fairness assumption in the main text and discussing it, as I believe this is crucial component for the understanding of how the global regret can be controlled.
- you may want to include references on restless bandits in Section 2.4, as this is very related to AS of RL algorithms (arms follow Markov processes).
- The reference [Best arm identification in multi-armed bandits] is missing an author.