Behind the Myth of Exploration in Policy Gradients

Dear reviewer,

Thank you for your valuable feedback, which we have carefully considered and integrated into the document. We've addressed most of the minor remarks and recognize the need for improved clarity on certain points. Notably, we've made substantial changes to Section 4.1 and the introduction, providing a more comprehensive overview of our contributions.

We hope that these revisions have clarified the significance of our contributions to the RL community. With the manuscript modifications, we believe we now align with the acceptance standards of ICLR. Consequently, we kindly request you to reconsider your final decision.

Below, we provide detailed responses to your specific questions.

The contribution is entirely empirical (there are some nice theory concepts, but no proofs or useful properties are shown except empirically), and the empirical results are based entirely on extremely simple toy problems. In my opinion, this does not invalidate their interesting perspectives on the issues that they illustrate with these results, but it does make the contribution less substantial.

We acknowledge that the paper was rather vague on this point, but the criteria also introduce theoretical guarantees. Following your comment, Sections 3.1 and 4.1 have been reworked to better highlight the assumptions and results they imply. In particular, if our two criteria in Section 3 are met (note that we have changed the name of the second to better fit in the literature), it is possible to compute a policy by stochastic gradient ascent that is suboptimal by at most epsilon. Under the assumptions clarified in Section 4.1, the probability of improvement defines the probability of having a good solution after optimization. We agree, however, that there is future work to establish additional theoretical convergence guarantees and have introduced some avenues of reflection in conclusion.

Regarding generalization, we acknowledge that our illustrations were conducted on relatively simple use cases. The low-dimensional spaces of states, actions, and parameters were chosen for clarity in visual representation. In addition, the experimental results were computed through exhaustive search in the parameter space combined with Monte-Carlo estimations, constraining the parameter space to low dimensions. Moreover, most exploration methods rely on function approximators for dealing with high dimensions, introducing complexities in learning dynamics that prevent isolating the sole effect of exploration. Nevertheless, we believe that the strongly non-linear dynamics in the first environment and the sparse reward function in the second reflects sufficient complexity from an optimization perspective.

The paper overall is a bit challenging to read. For an example of a well-written bit that does not have this issue, the conclusion says “First, it modifies the learning objective in order to remove local extrema. Second, it modifies the gradient estimates and increases the likelihood that the update steps lead to optimal policies.” This is great; more “high-level summary” passages like this in sections 3-4 would've made it much easier to read. For an example of a hard-to-understand part, see the last question below.

We acknowledge your remarks concerning the clarity and have modified the paper substantially, including the two particular points you mentioned. In particular, the revised introduction aims to provide a clearer high-level view of the paper, related works, and contributions.

In 4.1, J^d seems less like an exploration term, and more like a “reward-engineering” term that simply makes the problem easier. Am I missing a perspective on this? This leads to a larger concern, in that much of the contribution of 4.1 hinges on this term, and I have doubts about whether this term can be legitimately thought of as an exploration bonus that is superior to the entropy bonus.

Firstly, we have clarified in the introduction the distinction between exploration in policy gradient as intended in theory, i.e. optimizing a sufficiently stochastic policy, and how it is implemented in practice, i.e. involving reward shaping and optimizing a surrogate learning objective to increase stochasticity. In our paper, we analyse the second aspect by studying the exploration-based learning objective functions. Nevertheless, no assumption is made on the structure of the intrinsic rewards that may thus be built with any reward-shaping strategy. The analyses and discussions thus hold true for the expert-knowledge reward shaping in Section 4.1, which illustrates the potential achievements of exploration when well-designed for the problem at hand. We furthermore emphasize that all discussions are also validated on the standard entropy regularized objective.

Dear reviewer,

We thank you for reviewing our paper and answer your two questions below. We believe these are due to a slightly unclear presentation that we have rectified in the revised paper version. Your remark gave us the opportunity to clarify this in the main paper, and we also better explain it below. We are confident that the paper offers a new way of analyzing exploration and is of interest to the ICLR community. We are receptive to any suggestions for improvements and kindly request a reconsideration of your decision for acceptance.

My concern lies in practicality. While intuitively, the proposed four criterion all make sense, however, for a general RL question, how to effectively compute these four measures is somehow challenging.

The purpose of the paper is to provide a framework facilitating the interpretation of policy gradients and to identify relevant criteria for obtaining guarantees in policy gradients. As is often the case when theoretical criteria are proposed, their empirical verification is as complex as solving the problem at hand. If such criteria were easy to verify empirically, the problem would certainly be much more easy to solve too. However, we still believe that these criteria provide a good account of the effect of current exploration techniques, and their trade-offs. Moreover, we think that they provide some valuable, and often lacking, intuition for the design of new exploration techniques. We have added the development of more problem-specific bounds to our future work.

Current simulations are good for readers to get the idea of the paper, but insufficient to demonstrate the capacity. It would be nice if the authors could take an concrete example, say a maze, with a few popular regularized objectives, compute (estimate) the proposed four criterion of these objectives, see which one is more effective based on these criterion. Then valid such prediction on the trained agent's behaviors.

The examples primarily serve to illustrate the criteria, which are derived from optimization theory. The experimental results were computed through exhaustive search in the parameter space combined with Monte-Carlo estimations, constraining the parameter space to low dimensions. Moreover, most exploration methods rely on function approximators for dealing with high dimensions, introducing complexities in learning dynamics that prevent isolating the sole effect of exploration. Nevertheless, we believe that the strongly non-linear dynamics in the first environment and the sparse reward function in the second reflects sufficient complexity from an optimization perspective. We have also clarified in the introduction that finding good exploration strategies is known to be problem specific and that we thus introduce a general framework for the study and interpretation of exploration in policy gradient methods instead of trying to find the best exploration method for a given task.

Dear authors,

Thank you for your response. It somewhat addressed my concern~

I would like to acknowledge the contribution of theoretically defining the four criteria. But to have a practical impact, it feels some further work needs to be donem, either some further theoretically investigation (e.g. some sufficient condition to check these four criteria ) or a more comprehensive simulation is needed to validate the proposed criteria.

Otherwise, even we have these four criteria in mind, why these are good, how to design a policy that fit these etc are unclear. Hence, i decide to keep my original score.

Dear reviewer,

We appreciate your feedback and the interest you give to our work. We have taken your comments into account and included your references into the document. We have significantly reworked the introduction and Section 4.1. Please find our detailed responses to your questions below.

I would have liked to see however how these methods generalize over problem instances, as it is known from \citet{mei2020} that PG methods are highly impacted by initialization and problem instances.

Indeed, initialization plays a crucial role in the optimization. This influence is implicitly embedded in our criteria that consider the complete parameter space and in our examples for which all (potentially initial) parameters are analysed in the light of the criteria. Furthermore, the criteria can be extended and defined over a set of parameters where they hold true, such that policies initialized within this set would benefit from the properties and guarantees outlined in the paper. Section 3 illustrates that, with a fixed exploration strategy, gradient ascent can compute the optimal solution when we are in the "basin of attraction" of the global optimum. Additionally, the probabilities in the criteria from Section 4 may be low for certain parameters that will never be encountered by gradient ascent depending on the initialization, as illustrated in the example without exploration when the policy is initialized close to the optimum.

Regarding generalization, we acknowledge that our illustrations were conducted on relatively simple use cases. The low-dimensional spaces of states, actions, and parameters were chosen for clarity in the visual representations. In addition, the experimental results were computed through exhaustive search in the parameter space combined with Monte-Carlo estimations, constraining the parameter space to low dimensions. Moreover, most exploration methods rely on function approximators for dealing with high dimensions, introducing complexities in learning dynamics that prevent isolating the sole effect of exploration. Nevertheless, we believe that the strongly non-linear dynamics in the first environment and the sparse reward function in the second reflects sufficient complexity from an optimization perspective.

Some statements are rather vague, e.g. the authors claim that there is a trade-off between quasiconcavity and eps-coherence, but i’m not sure how general this statement is, and the authors do not provide proofs that guarantee these statements hold on all problem instances. At other times the authors use vague words like “appears” so its difficult to understand if these small illustrations would carry over to agents at scale, and are general enough.

As mentioned above, we have reworked the paper to clarify a number of points. Concerning the trade-off, in the general case, modifying the objective has no guarantee of preserving the global optimum. So, the greater the lambda weights, the greater the objective modification, and the greater the epsilon value. Similarly, if you modify the objective only slightly, the shape of the learning objective will not be greatly modified, and the concavity remains unchanged. There is thus at best a trade-off, which we observe in the example, and at worst both criteria are violated.

The experiment illustrated in Fig 2 is interesting, but wasn’t this already known, the problem generally is that we cannot know the value of lambda beforehand as these are problem dependent, sometimes state-dependent and might also change over the optimization landscape for different policies on the way toward the optimal solution.

Related works have been clarified in Section 1. A similar result had been stated (less formally) in the case of entropy regularization (maximum entropy RL) but had not been formalized nor stated in a general case to our knowledge.