Scalable Coordinated Exploration in Concurrent Reinforcement Learning
We consider a team of reinforcement learning agents that concurrently operate in a common environment, and we develop an approach to efficient coordinated exploration that is suitable for problems of practical scale. Our approach builds on seed sampling [1] and randomized value function learning [11]. We demonstrate that, for simple tabular contexts, the approach is competitive with previously proposed tabular model learning methods [1]. With a higher-dimensional problem and a neural network value function representation, the approach learns quickly with far fewer agents than alternative exploration schemes.
Main ideas of the submission The authors investigate the problem of efficient coordinated concurrent exploration in environments too large to be addressed by tabular, model-based methods. This is a continuation of [1], where the principles of seed sampling were developed for efficient coordinated concurrent exploration, using a tabular model based algorithm. Since the algorithm was only tested on trivial tasks in [1], the authors first demonstrate the effectiveness of this tabular method on a more challenging problem (swinging up and balancing a pole), compared to trivial extensions of known methods (UCB, Posterior sampling) to the concurrent setting. Following that, they suggest a model-free extension to seeding that is based on function approximation with randomized value functions [9] – a concept that facilitates the combination of the seeding principle with generalization. The authors also suggest some concrete algorithms (SLSVI, STD) that support this concept, show that its performance on the trivial examples of [1] is comparable to that of tabular seed sampling, and show its effectiveness on another pole-balancing problem, which is too difficult to be addressed by tabular methods.  Strong points • Showing that the tabular seed sampling method suggested in [1] is effective compared to other concurrent exploration methods, even on the more difficult problem of balancing up and stabilizing a pole. • Extending the seeding idea in [1] to complex continuous environments. • Although the authors suggest some concrete algorithm implementations (SLSVI, STD) – the concept itself is very general and can be employed in various versions. • The authors also discuss attempts to lower the computational cost – such as limiting the number of operating models (section 3.2.3). • The suggested method is shown to achieve a performance, which is almost as good as the one achieved by the tabular seeding method from [1], although the current method has a much less informative prior. They also use a high dimensional task to demonstrate that the exploration becomes more efficient as the number of agents increases, and is more efficient than \epsilon-greedy high dimensional exploration.  Weak points and suggestions • Although seeding is a promising principle for efficient concurrent exploration, this idea is not backed up by any theoretical analysis and the benefits are only exemplified computationally. Although [14] has developed provable upper exploration cost bounds for the concurrent exploration case, [12] and [9] have only developed such results only for the single-agent case. In a wider perspective, while the current submission and [1] repeatedly claim that they have found three necessary properties for efficient concurrent exploration, there is no supporting theory for that. • The concrete suggested algorithms essentially rely on existing methods (LSVI and TD) for which the computational cost has been well tested in previous work. The only additional cost per agent is the drawing of a random seed, and they also suggest a way to limit the number of active models to save computational costs. This means that essentially – the computational cost of the algorithm itself is the number of active models times the exploration cost for a single agent. I think that this should be noted in the submission, so that the readers are able to compare the computational requirements with previous works. • The seeding method suggested in this paper is quite general, and lacks some guidelines on how to choose the distribution of the seed Z. The authors of [1], make the effort to show that the distribution of the seed Z at the beginning of the episode, is chosen in a specific manner so that at each time - \hat\theta(z,H_t)\sim \theta|H_t  (Where \theta|H_t is the posterior estimation of the model parameter \theta, based on the history up to that time H_t, and \hat\theta(z,H_t) is the parameter chosen by an agent based on a seed z and history H_t. Note that the randomness stems from the seed z).  However, there is no indication at all on a how to effectively choose the seed Z in the current submission. Although the concept of a randomizing seed is intuitive, a poor choice can ruin the exploration (as the seed acts to modify sampled rewards), which makes this work incomplete. • The agents all explore the same MDP, but a more interesting situation is concurrent exploration on a set of different environments with some shared properties (as investigated in [14]). Since the environments are not identical, there are some properties that agents should share and some that they should not, and that is another difficulty that the agents must overcome. This also closely relates to the problem of transfer learning. • The two example tasks discussed in the submission (balancing up a pole) are not complicated enough in the sense that the environment is deterministic. It would be interesting to see how the algorithms operate in such a system where, for example, a noisy wind is introduced. Furthermore, the task of steadying a pole can surely benefit from concurrent exploration: When effective, the concurrent exploration can make the learning converge faster. However, there are surely more interesting tasks where concurrent exploration and cooperation between agents is necessary for the achievement of the overall target, and it would be interesting to see if the seeding-method operates well in these tasks too.  Technical details: • In the example task of balancing up a pole – the differential equations for the cart and mass are taken from [18] in their references, which seems to direct to the following paper: Cohen, Michael A., and Stephen Grossberg. "Absolute stability of global pattern formation and parallel memory storage by competitive neural networks." IEEE transactions on systems, man, and cybernetics 5 (1983): 815-826.  Even when taking the friction \mu to be zero, the equations does not seems to match the ones presented in the submission. • Line 79: There is no detailed explanation regarding the state-actions that receive a reward of 1. For example, it is unclear whether the pole must be balanced with a zero velocity, or must just be in an upright position. In fact, the authors explain it more clearly in the second pole example (Note 1 on page 7 of the submission), but it should be explained here as well. • Line 138: The paraphrasing should be changed, as it is unclear whether the samples perturbed by an agent are also visible to other agents. • The formula for computing \tilde\theta_h used in the SLSVI of section 3.2.1 is said to run for h=H-1,...,0. Since we consider a finite horizon problem in which each agent only takes H actions at each episode – wouldn’t it make more sense for this equation, before the m-th action, to run for only h=H-1,...,m?  Since LSVI aims to find the parameters for which the Q-function is the closest to satisfying the finite horizon Bellman equations, restricting this equation to h=H-1,...,m  means that at the m-th action, this would be the next choice considering that there are only H-m transitions left. • The minimization operation present in the formula for computing L(\theta) following eq. 209 seems to be a typo, since a minimization operation is the purpose of the SGD. Furthermore, there seems to be a discount factor added to this formula – which means that this SGD is used to solve the discounted MDP problem, and not the finite horizon one as stated before. However, this is never specified within the text. • The example tasks of section 4.1 employ the generalized seeding algorithms, but it is not specified how the random seed is set (meaning, the distribution of the random noise terms Z that are added to the rewards is not mentioned) – and thus, these results cannot be reproduced by readers. • Example 4.2 – it is unclear what the "instantaneous reward" axis in figure 3 is. Is it the reward received per agent divided by one second, or is it the reward per time ste