From a young age we learn to use grammatical principles to hierarchically combine words into sentences. Action grammars is the parallel idea, that there is an underlying set of rules (a grammar) that govern how we hierarchically combine actions to form new, more complex actions. We introduce the Action Grammar Reinforcement Learning (AG-RL) framework which leverages the concept of action grammars to consistently improve the sample efficiency of Reinforcement Learning agents. AG-RL works by using a grammar inference algorithm to infer the action grammar of an agent midway through training. The agent's action space is then augmented with macro-actions identified by the grammar. We apply this framework to Double Deep Q-Learning (AG-DDQN) and a discrete action version of Soft Actor-Critic (AG-SAC) and find that it improves performance in 8 out of 8 tested Atari games (median +31%, max +668%) and 19 out of 20 tested Atari games (median +96%, maximum +3,756%) respectively without substantive hyperparameter tuning. We also show that AG-SAC beats the model-free state-ofthe-art for sample efficiency in 17 out of the 20 tested Atari games (median +62%, maximum +13,140%), again without substantive hyperparameter tuning.
The authors propose a method for learning macro-actions in a multi-step manner, where Sequitur, a grammar calculator, is leveraged together with an entropy-minimisation based strategy to find relevant macro-actions. The authors propose a system to bootstrap the weights of these macro-actions when increasing the policy's action space, and a system to increase the amount of data (and bias it towards macro-actions) used to learn a policy for when conditioned on this increased action-space. The authors test against a subset of the Arcade Learning Environment suite.
Overall, I'm conflicted by this paper. On one hand, the framework is interesting, and their method involves the usage and exploration of quite a few nice ideas; on the other hand, (a) the quality of the scientific contribution is hard to judge considering the significant differences between the proposed baselines and and their methods, and (b) the experimental section doesn't provide a lot of qualitative analysis and signal wrt. each component.
Furthermore, I have the following issues / questions:
1. I'm not convinced that the usage of Sequitur to build the macro-actions is sufficient to declare this work novel wrt. other macro-action papers. Sequitur usage in this case seems to be particularly overkill, since ultimately all that the method seems to be doing is finding frequent sequences of actions, which can be done quite fast (at least given the amount of training steps) simply using search and pattern matching. From my point of view, there doesn't seem to be a lot in that work that exploits the fact that the macro-actions are constructed as a "grammar" (beyond, maybe, HAR)
2. The Abandon Ship heuristics is effectively a fixed termination policy, which makes the entire setup somewhat similar to options. In this case, what is traded is learning complexity for a hyperparameter and a significant restriction in how the macro-actions terminate. Did you attempt to learn this function at all? Do you have any insights / experiments that might show how the heuristics behaves with changing values of $z$? Would it be possible to plot the distribution of attempted vs executed move lengths rather than then averages (since I doubt they would be normally distributed)?
3. Given points 1 and 2, the literature review is lacking - there's a lot of prior work done on macro-actions in both RL and robotics (planning, HRI, ...) that goes well beyond the few recent papers mentioned by the authors, and I think it might be necessary to mention work on options where the termination function is structured / biased in some way.
4. I have some doubt the experimental setup for DDQN fairly gives a fair assessment of the method. When using a pretrained features, the problem becomes significantly easier, and thus AG-DDQN potentially doesn't need to deal with the problem of learning extremely bad / noisy macro-actions. I would love to see the method trained for a more reasonable amount of frames without pre-training. Also, did the 8 / 20 atari games get chosen randomly, or were they picked based on some environment features?
5. How do the Q-values for the policy evolve with training time? The proposed methods seem to somewhat imply that the action space grows unboundedly, which might seriously destroy the policy for tasks that require much longer training. Would it be possible to add a paragraph about how the policies evolve in at least some of these environments? Are macro-actions used most of the times after some full iterations? How many <learning -> action distillation> iterations are actually done in the current experiments?
At this point, I cannot recommend the acceptance of this work, however I'd be willing to reconsider my rating if the authors address the above points.