Summary
The paper considers the setting in which several good policies are available for some Markov Decision Process, and the agent has to learn how to combine them in a way that allows to achieve higher performance than following a single of the constituent policies. This problem is quite wide and a large number of methods exist to combine policies, with varying assumptions and properties. This paper proposes a method that can realistically be implemented, by considering that per-policy value functions can be learned for an ever-increasing horizon $h$, and then the action to execute in the environment is the one executed by the policy that has the largest value in the current state and current horizon.
The novel aspect of the contribution seems to be the reliance on $h$ and the iterative nature of the algorithm. In MDPs with a finite time horizon, we have a finite amount of $h$ values, so a finite amount of value functions to learn. Combined with the fixed amount of constituent policies, this leads to an algorithm whose complexity scales well even to very large state-spaces, because the size of the state space does not intervene in the compute requirements of the algorithm.
The proposed method is discussed from a theoretical perspective, and promising empirical results are provided. The experiments consider complicated robotic tasks, with an interesting setting and motivation for this work: the constituent policies are almost-optimal policies for various tasks, and the new policy to learn from a combination of the existing ones is learned against a new task. So, this work seems to be applicable to multi-task RL.
Strengths
The proposed method seems sound, easily to implement (provided that the paper is made clearer) and to lead to impressive empirical results. The assumptions and limitations of the approach are well-discussed, which helps deciding whether it would apply well on some specific problem.
Weaknesses
While the contribution seems of high quality, the paper lacks clarity and intuition, which may make it difficult to reproduce.
- Examples of oracles for the value functions should be given, to better indicate to people whether the oracle can be a value function learned on another task, or obtained from rollouts, or requires a simulator. The oracle is an important part of the algorithm, as it is queried $K$ times per horizon step and its output is directly used to perform an argmax operation (the result of the oracle does not seem to be distilled to some learned function)
- The paper should be a bit more explicit about how to produce the $\mu_h$ distributions and the fact that this requires resetting the environment and performing actions in it. Not every environment is resettable at will by the agent, and executing all these actions requires an online setting.
- The core of the paper is the use of approximate max-following policies, defined in Definition 2.3. The definition is very dry and the reader has to carefully look at the notations to understand where everything comes from. For such an important definition, an intuition and maybe an example would have been very useful. Later in the paper (Figure 2), examples of environments and corresponding max-following policies are used in some argument, but without explaining what a max-following policy is. Thus, the definition is very dry, yet at the core of important arguments in the paper.
Questions
Given the average-low clarity of the paper, I may have mis-understood several parts of the contribution. I expect the authors to disagree with some of the remarks written above. I would welcome to be corrected, and for the authors to take the opportunity to improve the paper given the possible ways it can be mis-understood.
Limitations
The paper does not seem to have potential negative societal issues, and its scientific limitations are well-discussed.