Venue: ICLR 2017 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a novel exploration strategy that promotes exploration of under-appreciated reward regions. Proposed importance sampling based approach is a simple modification to REINFORCE and experiments in several algorithmic toy tasks show that the proposed model is performing better than REINFORCE and Q-learning.

This paper shows promising results in automated algorithm discovery using reinforcement learning. However it is not very clear what is the main motivation of the paper. Is the main motivation better exploration for policy gradient methods? If so, authors should have benchmarked their algorithm with standard reinforcement learning tasks. While there is a huge body of literature on improving REINFORCE, authors have considered a simple version of REINFORCE on a non-standard task and say that UREX is better. If the main motivation is improving the performance in algorithm learning tasks, then the baselines are still weak. Authors should make it clear which is the main motivation.

Also the action space is too small. In the beginning authors raise the concern that entropy regularization might not scale to larger action spaces. So a comparison of MENT and UREX in a large action space problem would give more insights on whether UREX is not affected by large action space.

--------------------------
After rebuttal:
I missed the action sequences argument when I pointed about small action space issue.

For question regarding weak baseline, there are several tricks used in the literature to tackle high-variance issue for REINFORCE. For example, see Mnih & Gregor, 2014.

I have increased my rating from 6 to 7. I still encourage the authors to improve their baseline.

review_title: Review

final_score: rating: null
review_content: -It's not clear in section 6 what is the action to output a character. Is it an extra action in the action set? A different controller? 
-How does training speed compare for the suggested tasks? Is the convergence speed affected by the task in a similar way across models?
-You hypothesize that UREX does smarter exploration. Intuitively this seems true. Is it something that you have observed experimentally? Could you reproduce e.g. Figure 3 (or a similar measure of "exploration") for other tasks?

Thanks!
review_title: A few questions

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 

overview:
This work proposes to link trajectory log-probabilities and rewards by defining under-appreciated rewards. This suggests that there is a linear relationship between trajectory rewards and their log-probability which can be exploited by measuring the resulting mismatch.
That is, when an action sequence under-appreciates its reward, its log-probability is increased.
This method is a simple modification to the well-known REINFORCE method, requiring only one extra hyperparameter \tau, and intuitively provides us with a better exploration mechanism than \epsilon-greedy or random exploration.
The method is tested on algorithmic environments, and compared to entropy-regularized REINFORCE and double Q-learning, and performs equally or better than those two baselines, especially in more complex environments.


remarks:
- the focus in the introduction on algorithmic tasks may be a double-edged sword. It is an interesting domain to test your hypothesis and benchmark your method. At the same time, it distracts the reader from the (IMO) generality of the proposed method.
- in the introduction you say the reward is sparse, in section 6, on tasks 1-5, you then say there is a reward at each correct emission, i.e. each time step. This is only 'corrected' to end-of-episode-reward in section 7.4, after having discussed results. I'd move or mention this in section 6.
- approach seems quite sensible to tau being in the same range as logpi(a|h), but you only try tau=0.1 for UREX. I'm not sure I understand nor agree with this experimentation choice.
- an alternative to grid search is random search (Bergstra&Bengio, 2012). It may illustrate better hyperparameter robustness, and allow you to explore more in the same number of experiment.

opinion:
- An interesting approach to policy-gradient, to be sure. It tackles the very important question of "how should agents explore?"
- I'm ambivalent to claiming that an algorithm is robust to hyperparmeters simply because it performs better on the selected hyperparameter range. All you really show is that it performs well some amount of time when the hyperparams lay in that range. Couldn't it be that MENT needs different hyperparameters? (Just being devil's advocate here)
- I see why matching 1/tau with logpi is the obvious choice, but it implies a very strong prior: that the reward (to a factor of 1/tau) lies in the same space as the log policy. One point of failure I see (but correct me if I'm wrong) is that as the length of the trajectory grows the reward is expected to grow linearly, so short ways to get some reward will be less explored than long ways of getting the same reward, creating an imbalance unless the reward is shaped such that shorter trajectories get more reward (which is only the case in task 6).
- It might have been good to also compare with methods explicitly trying to explore better with value-functions (e.g. prioritized experience replay, Schaul et al 2015)
- At the risk of repeating myself, tau plays a major role in this method, but there is little analysis on its effect on experiments.


The methodology and reasoning is clearly explained and I think this paper communicates its message very well.
That message is novel, albeit a minor modification to a well-known algorithm, it is well motivated and, I think, a welcome addition to literature concerning exploration in RL.
The experiments are chosen accordingly, and results seem to reflect the hypothesis of the authors.

I realize the tyranny of extensive experimentation and the scarcity of time, but I do think that this paper would benefit from more (or cleverer) experimentation, as well as demonstrating more explicitly the impact of the method on exploration.
Reading this paper convinced me that measuring mismatch between a trajectory's observed reward and its probability given the current policy is a clever (and well motivated) thing to do. Yet, I think that the paper could have a more convincing empirical argument, even if it is for toy tasks.
review_title: Review

final_score: rating: 7: Good paper, accept
review_content: The paper proposes a new algorithm based on REINFORCE which aims at exploring under-appreciate action sequences. The idea is to compare the probability of a sequence of actions under the current policy with the estimated reward. Actions where the current policy under-estimate the reward will provide a higher feedback, thus encouraging exploration of particular sequences of actions. The UREX model is tested on 6 algortihmic RL problems and show interesting properties in comparison to the standard regularized REINFORCE (MENT) model and to Q-Learning.

The model is interesting, well defined and well explained. As far as I know, the UREX model is an original model which will certainly be useful for the RL community. The only drawback of the paper is to restrict the evaluation of this algortihm to algorithmic problems that are specific while it would be easy to test the proposed model onto other standard RL problems. This would clearly help to make the article stronger and I greatly encourage the authors to add some other tasks in their paper. 
review_title: Review

final_score: rating: null
review_content: The main topic of the paper lacks of clarity since the authors are mixing arguments concerning reinforcement learning in general, and arguments for the particular task of learning algorithms. It makes some points unclear to me:

The difference between general RL and learning algorithms concerns the nature of the underlying MDP that can be with stochastic transitions or deterministic ones. In Section 3, second paragraph, the transition between states seems to be deterministic -- s_t+1 = f(s_t,a_t). So I am not sure that the algorithm proposed here is specific or not to deterministic problems. Could you please improve the description on that point ?

Concerning the experimental part, here also the choice of solving algorithms problem is very specific, while the conclusion of the paper is about general RL... could you please provide more details ?

At last, the influence of the use of curriculum learning is not analyzed. Is it possible to provide results with and without curriculum learning ? Particularly, you argue that your method is a good way to deal with reward sparsity, while curriculum learning seems to be in your experiments a way to reduce the sparsity of the reward at the beginning of the process... Dealing with really sparse reward (without curriculum learning) could help to better understand if your method helps. 
review_title: pre-review questions

Meta-review: This paper proposes a nice algorithm for improved exploration in policy search RL settings. The method essentially optimizes a weighted combination of expected reward (essentially the REINFORCE objective without an entropy regularizer) plus a term from the reward augmented maximum likelihood objective (from a recent NIPS paper), and show that the resulting update can be made with a fairly small modification to the REINFORCE algorithm. The authors show improved performance on several sequential "program-like" domains like copying a string, adding, etc.
 
 I'm recommending this paper for acceptance, as I think the contribution here is a good one, and the basic approach very nicely offers a better exploration policy than the typical Boltzmann policy, using a fairly trivial modification to REINFORCE. But after re-reading I'm less enthusiastic, simply because the delta over previous work (namely the RAML paper) doesn't seem incredibly substantial. None of the domains in the experiments seem substantially challenges, and the fact that it can improve over REINFORCE isn't necessarily amazing.
 
 Pros:
 + Well-motivated (and simple) modification to REINFORCE to get better exploration
 + Demonstrably better performance with seemingly less hyperparameter tunies
 
 Cons:
 - Delta over RAML work isn't that clear, essentially is just a weighted combination between REINFORCE and RAML (though in RL context)
 - Experiments are good, but not outstanding relative to simple baselines
Decision: Accept (Poster)