We study the problem of exploration in Reinforcement Learning and present a novel model-free solution. We adopt an information-theoretical viewpoint and start from the instance-specific lower bound of the number of samples that have to be collected to identify a nearly-optimal policy. Deriving this lower bound along with the optimal exploration strategy entails solving an intricate optimization problem and requires a model of the system. In turn, most existing sample optimal exploration algorithms rely on estimating the model. We derive an approximation of the instance-specific lower bound that only involves quantities that can be inferred using model-free approaches. Leveraging this approximation, we devise an ensemble-based model-free exploration strategy applicable to both tabular and continuous Markov decision processes. Numerical results demonstrate that our strategy is able to identify efficient policies faster than state-of-the-art exploration approaches
Paper
Similar papers
Peer review
Summary
In this paper, the authors propose a way of obtaining tighter PAC bounds for model-free reinforcement learning. The new theoretical results allow the authors to propose new practical methods for exploration in both discrete and continuous state spaces. The proposed algorithms use ensembles of Q-values, and the results are very competitive when compared with model-based approaches.
Strengths
* The new methods adapt to specific problems in an automated way. * The paper is well written, and the discussion is supported by relevant citations. The contributions are backed up by both theoretical arguments and empirical results on a range RL domains. * The contributions seem relevant and important. The results indicate that the proposed methods have merit. * The paper comes with a comprehensive and long appendix (which would be a pain to read for a busy reviewer), but the future readers will most certainly appreciate it. The appendix provides many details that contribute to the quality of the work.
Weaknesses
* The authors should make it clear from the start that the new algorithms are ensembles. After reading a few pages of the paper, I was anticipating a clever algorithm that would be purely based on the proposed theory. It was a bit disappointing that ensembles were used at the end. I don't say that this is bad, well there is no free lunch, but it would be fair to expect that, when the new algorithms are mentioned for the first time, ensembles are mentioned too. * The paper argues that model-base approaches are expensive to run. The methods presented in this paper are ensembles. What is their runtime? Are that they really faster than model-based methods? * Since the new methods proposed in this paper are ensembles, I would expect some discussion on ensembles in RL. I would expect that there must exist ensemble based RL methods that could be competitive with the methods presented here. Literature review on ensembles in RL would be useful. A classic paper on this is: Wiering, M.A. and Van Hasselt, H., 2008. Ensemble algorithms in reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38(4), pp.930-936.
Questions
* How exactly is the alearotic uncertainty in the value function accounted for by the methods proposed in this paper? * There is probability p in Alg. 1. It would be useful if its role and rationale were explained. * The use of the variance of the value function is slick, and the authors are careful saying that this addresses the aleatoric uncertainty only, but it would be useful if the authors explained why epistemic uncertainty is not addressed.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
4 excellent
Limitations
I tried to discuss this in the weaknesses and questions sections above. Even though some of my comments may appear critical, I am very positive about this paper. This is solid work.
Summary
The paper introduces a model-free exploration approach developed on an information theoretical basis. Firstly, the lower bound on the number of samples for a near-optimal policy is estimated, and based on this lower bound, the paper develops an exploration strategy for both tabular and deep RL approaches. The exploration strategy is further validated via experiments, where it is found to be superior to other competing approaches.
Strengths
The paper is generally well written and addresses an important problem. The developed exploration strategy having an information theoretic basis sets it apart from some of the previous approaches which have mainly been based on heuristics.
Weaknesses
The paper does not include experiments in more complex environments such as Montezuma’s revenge, where exploration is known to be a key challenge. A more detailed summary of the main intuitions and theoretical results from [1] could have made the paper more readable.
Questions
1. Can more challenging environments possibly be added? If not, are there any fundamental limitations that make this infeasible? 2. Wouldn’t the approximation errors in the deep RL version of the algorithm affect the suboptimality gap? Is this somehow accounted for? 3. Apart from the current results, perhaps for some of the environments, the actual exploration trajectories could be traced/charted out to explicitly show how the exploration is modified. I noticed something along these lines included in the appendix, but it would be good to bring similar results forward into the main text. 4. It would benefit readers to include more details about the main results in [1]. 5. Although it may be obvious, in the cartpole swingup environment, it would be good to include a brief paragraph regarding why/how increasing k makes the task more difficult. 6. In line 297, what is N? 7. I am not sure why Fig 3 shows the performance in Riverswim vs |S| and ForkedRiverswim vs N 8. How is $\Delta_{min}$ initialized in the Deep RL version?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
Currently, there is no explicit section outlining the limitations. I suggest the authors include a short paragraph about this covering at least the basic assumptions and requirements for the proposed to be applicable. Perhaps some comments regarding the scalability of the approach to more complex environments could also be added if that is indeed an issue.
Summary
The authors propose a model free approach to exploration in RL, that is based around best policy identification. This technique, unlike prior work, uses stochastic approximation to learn a lower bound on the policy performance based on collected samples.
Strengths
- The paper presents an model-free approach that's heavily guided by theory, and results show how this technique can be effective in improving exploration in terms of improved performance as well as reduced performance variance.
Weaknesses
- The paper is a bit tough to get through; being so theoretically heavy, some intuitive high-level explanation of their implications would be really helpful for the reader to follow along the thought process of the authors. - It is unclear where the derivation of the many theorems is in the text. For example, looking for a derivation on how the authors reached at corollary 5.1, the closest reference I found in the appendix was section B.3, but that's just an explanation on how to use that corollary.
Questions
- Could you please clarify where the proof and derivations of the different theorems are? For instance, for theorem 4.2 there is a nice explanation of the implications of the theorem, but it is not stated how that upper bound is derived. The same is true about corollary 5.1. Please clarify this, as the evaluation of soundness of the paper heavily relies on being able to find how these theorems where proved. - Algorithm 1 only samples actions according to the allocation omega, does this mean that over time omega converges to pi^*? - Corollary 5.1, the denominator in H_epsilon contains the term delta_min is defined in terms of the optimal policy for the MDP. How are you sampling according to corollary 5.1 (algorithm 1), when the optimal policy pi^* is needed to compute that value? This is a bit unclear.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
3 good
Limitations
N/A
Summary
This paper introduces an approximation of a lower bound on the number of samples needed to identify a nearly optimal policy directly applicable to model free RL. They further propose a model free exploration strategy that can be applied to the tabular and continuous MDPs.
Strengths
The paper is clear and well written. With experiments showing the proposed approach seems competitive with other exploration approaches.
Weaknesses
The paper lacks a comparison of the current approach with more common exploration strategies in DeepRL such as 34, 37. The results remain very toy. It would be great to have an understanding of the kind of exploration the proposed approach performs well, with increasingly sparse rewards? on which circumstances is this preferable.
Questions
Why have you used the 2k-th moments in the bound? Can the authors clarify which eq. Compute Allocation, training and estimate minimum gap refer to? How is the mask probability being computed? are the results sensitive to this parameter?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
The authors could provide a more thorough limitation description of the approach under which circumstances does the proposed approach fail, how critical and reasonable are the assumptions made, for instance the communicating MDPs. How does the approach perform in more challenging tasks such as Montezuma's revenge, and more structured exploration tasks. Under which types of exploration difficulty does the proposed approach excel or fail.
Summary
This work focuses on the exploration of reinforcement learning and introduces a novel model-free algorithm. The authors derive a new bound for the lower bound of the number of samples needed to identify a near-optimal policy. Based on that, they develop a model-free exploration strategy that is applicable to both tabular and continuous MDPs. Experimental results demonstrate that their strategy is competitive to existing approaches in efficiently identifying optimal policies.
Strengths
- Theoretically, the new proposed bounds look novel and sound. They transform the original lower bound into a more manageable form, making it easier to handle and apply in practical scenarios. - Empirically, the experiments confirm the superiority of the proposed algorithm over existing methods, aligning with their claims.
Weaknesses
- There seems to be a big gap between the theory and the algorithm. The theoretical results involve certain quantities (e.g., $\Delta(s,a)$) that are unknown to the algorithm. The authors addressed this issue by approximating these quantities through Q-value (and M-value) learning, subsequently treating the approximated Q and M as ground truth for all computations. This introduces a substantial gap between the theory and the algorithm. - It would improve if the authors could provide an intuitive explanation of the terms in the complicated expressions presented in Theorems 4.1 and 4.2. Understanding and evaluating these results as a whole seems challenging without a better explanation. - Although I admit that the main contributions lie in the theoretical aspects, it would be better to conduct more complicated experiments.
Questions
- Considering the gap between the theory and the algorithm mentioned above, is there any convergence guarantee for the algorithm? - When the authors select $\bar k=1$ (line 211) and arrive at $\bar{U}^1_{\epsilon}$, does it remain an upper bound for $T_\epsilon$? - I was a bit confused about the main idea. The authors first proposed an upper bound $\tilde{U}$ for the well-established lower bound $T_0$, and then they proceeded to carry out all computations based on this new bound. Although I understand that it is their point to derive this approximation that makes the bound easier to handle, it remains unclear to me why this approach is rational. Typically, what we usually do is to derive a more manageable upper bound on another harder upper bound, or derive a more manageable lower bound on another harder lower bound. Then we just need to minimize the new bound, because in doing so, the original bound is indirectly minimized (or maximized). However, this paper proposed an upper bound for the lower bound, making the aforementioned relationship inapplicable. Therefore, I am curious what the underlying principle here is.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
No negative societal impact was identified.
Thanks for your respones.
I thank the authors for their responses. Overall, the paper could be improved in terms of readability. It seems most of the comments I raised are already addressed in the Appendix. I urge the authors to either bring these into the main paper as much as possible, or at least include sentences in the main paper pointing to the appropriate Appendix locations where these are addressed. It would also benefit readers if the high level messages behind the mathematical results are better emphasized to bring clarity to the overall contribution.
Thanks a lot for your comments and feedback. In the revised version of the manuscript, we will address the points you raised and, to do so, move some parts from the appendices to the main document. We will also discuss in more detail the intuition behind our main mathematical results. Thank you again!
Thanks for the detailed feedback. It addressed most of my concerns. However, I am not certain about the "certainty-equivalence principle" mentioned by the author, so I have reservations about the gap between the theory and the algorithm (as proposed in the first weakness). In addition, I am still worried about the third question (the reason for deriving an upper bound for the lower bound). I can see that the distance between the new minimum and the true minimum is usually hard to estimate. However, if we are deriving the lower bound for the lower bound, then it is fine because we usually don't need to care about the distance between them if we can improve the new lower bound. Nevertheless, since the authors are deriving an upper bound for a lower bound, if we can't estimate the distance between them, there is not any guarantee for the original problem. Hence, I am not sure how the proposed results can be applied.
Thank you for your feedback on our paper. We understand your concerns and will attempt to elucidate further. > However, I am not certain about the "certainty-equivalence principle" mentioned by the author Using the certainty-equivalence principle means that we are using the current estimates (of the sub-optimality gap and the variance of the Q-function) as if they were exact when computing the exploration policy. This does not create a gap between theory and the algorithm, because in our algorithm, we mix the computed exploration policy with an $\epsilon$-soft policy, where the parameter $\epsilon$ is decreased over time (for example, see Lemma B.1 in Appendix to see what is the rate at which $\epsilon$ is decreased). In the code that we provided, you can see how we mix the allocation $\omega$ with this $\epsilon$-soft policy (e.g., in the tabular case, for MF-BPI, check the `forward` function in `RiverSwim/agents/mfbpi.py`, line 68 and 69). We first bootstrap the $Q,M$-values using the ensembles (to account for the parametric uncertainty), compute the exploration policy according to Corollary 5.1, and then mix with an $\epsilon$-soft policy (see also line 266-267 in the main paper). By doing this, we ensure enough exploration so that the estimation error vanishes with time (the estimates converge asymptotically). Mixing with an $\epsilon$-soft policy is often referred to as “forced exploration” in the literature. We will make sure to clarify this point in the paper. Certainty-equivalence principles are common in the RL literature, see e.g. [1, 17, 22, 28, 49, 51, 52, 53]. We haven’t explain all this in detail, but we will add a more exhaustive discussion in the revised version of the manuscript. > I am still worried about the third question (the reason for deriving an upper bound for the lower bound). I can see that the distance between the new minimum and the true minimum is usually hard to estimate. However, if we are deriving the lower bound for the lower bound, then it is fine because we usually don't need to care about the distance between them if we can improve the new lower bound. Nevertheless, since the authors are deriving an upper bound for a lower bound, if we can't estimate the distance between them, there is not any guarantee for the original problem. Hence, I am not sure how the proposed results can be applied. The true lower bound (see e.g (1)) specifies the *minimum* amount of exploration needed to identify an approximately optimal policy with some level of certainty. The lower bound is information-theoretical, and cannot be beaten by any PAC algorithm. Hence, one cannot explore less, because this would imply that we could fail at identifying an approximately optimal policy. In other words, an algorithm starting from a lower bound of the lower bound would not enjoy any performance guarantee, because you are exploring less than needed. This is why we use the upper bound of the lower bound. In this way, we ensure that we identify an approximately optimal policy, but at a cost of "over-exploring" a bit, at a rate corresponding to the gap between the upper bound and the true lower bound. This approach is not unique to our study and has been adopted in several works like [1,28,53]. Guarantee-wise, in the paper, we show that our bound obtains a scaling that is comparable, if not better, to the minimax lower bound, as explained after Theorem 4.2 (please see also the related work section where we discuss the minimax lower bound). We believe this underpins the validity of our approach in the context of the problem that we study. We're always open to continued dialogue to improve and refine our work further. Thank you for your time and dedication to reviewing our paper.
Thanks for your additional response, which addressed my concerns. Although there is still some limitation (eg, unclear how to estimate the gap), I believe the contribution is already significant enough. I have raised my rating to 6 to vote for acceptance.
Thank you for taking the time to engage in this discussion and for recognizing the significance of our work. We genuinely appreciate your feedback and we will keep your suggestions into account to further improve our manuscript, especially in terms of adding more intuitive explanations of the results.
Response to Authors
I thank the authors for their response. You comments and pointing to the right section in appendix for proofs helped clarify some questions, but keep in mind that readers will not be able to ask where to find the derivation of different theorems. The paper with an appendix is over 50 pages long, so it is unreasonable to expect a reader to dig through it and find them. I remain positive about the paper, but I think you can improve readability. I suggest editing the paper so that for every theorem/derivation, you point to the exact appendix section where the proof can be found. Some of those might even make sense to bring into the main text.
Thank you for being positive about the paper and for your constructive feedback. Given the depth of content, we understand your concerns about navigating the manuscript. In our revised version, we will ensure that each theorem or significant point in the main text directly references the corresponding section in the appendix, making the manuscript more accessible. Moreover, based on the feedback, we'll also evaluate if certain crucial derivations or explanations should be shifted from the appendix to the main body to enhance clarity (especially intuitive high-level explanation of the theoretical results, and their implications, as suggested also by some other reviewer). Once again, thank you for your feedback.
Decision
Accept (poster)