- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper presents related but notably distinct objective from the usual bandit exploration called recommender regret. This objective accounts for regularization in a RL settings, and basically says, under an exploration budget on samples, what is the best way to utilize them so that the final RL estimate is as accurate as possible? They derived lower and upper bounds for recommender regret and arrived at the conclusion that simple uniform sampling is theoretically valid for this estimation objective. These ideas were experimentally validated with synthetic trees, arcade games and biological sequence design and shown that uniform sampling indeed does well then other adaptive approaches.
Critical strengths
- Good range of experiments from different domains
- Moderately positive contribution
- The theory covers different types of common regularizers
- Minor strength to overall assessment
Critical weaknesses
- Unsure on the actual contribution as a new algorithm
- Given that the most of the conclusion is that uniform sampling is good, I am unable to see much value here
- Tree-depth complexity issues
- E.g. for real-world biological cases, going beyond one-step look ahead can be a major issue
- Difficult to understand theoretical results and paper in general
- Major readability issues, making this hard for me to see true value but I will still give some credit for the unusual perspective of bandits
Questions for authors
- What's the main practical difference between this approach and a naive regularized MCTS with uniform exploration?
- Beyond the experiments, if you were given the data and opportunity to apply your approach, which domain would actually be practical and valuable?
- In the arcade experiment, why were the filters added to remove some games (e.g. saturated quickly, didn't improve with search)? Could an aggregated measure be shown?
3 comments
In response to Q3. Environment filtering in the arcade game experiments. We filtered the OCTAX games to a representative subset which was meant to show the performance of MCTS in games that actually benefited from MCTS. In particular, a number of OCTAX games can be beaten quite easily, so MCTS doesn’t make any difference. See Airplane and Flight Runner in Figures 16 and 17 for instance, which demonstrate that these games are already well-played by the no-search agent, and MCTS doesn’t improve performance. Other games seemed not to benefit from search at all (e.g., Squash, Tetris, and Tank), while others like Rocket and Pong saw improved performance, but more search sims did not further improve performance. Thus, we chose to limit the games presented in the main body to the ones that saw improved performance and scaled with search sims. Per the aggregated measure, we did not design these experiments to achieve state-of-the-art performance in OCTAX games, rather we wanted to show that regularised MCTS with uniform and E3W achieve high performance in the games, and that they are competitive with one another across the choice of regulariser. In fact, during this rebuttal period, we ran experiments to measure the time-per-step of each search algorithm, and demonstrated that uniform sampling achieved the fastest results. Thus, if any statement of optimality is to be made, we believe that it should be this: in the OCTAX and scientific discovery tasks, uniform sampling achieved similar or better rewards than E3W and UCT, while also requiring less execution time.
On clarity (Weakness 3): We have added some intuition below Assumption 1 (p.5) as well as below Theorem 3 (p. 5), and additional explanations in Appendix A.3, A.4 and B. We would be grateful for any specific feedback on clarity so as to incorporate it.
We kindly request that you increase your score if our responses have answered your questions and concerns. Thank you again for your questions!
Thank you for the explanation. While I now understand the paper better, I will still continue to keep my current score on the grounds of novelty.
We thank the reviewer for their feedback, and are glad to hear that they found the framework novel and unique. It is immensely valuable for us to understand and address any concerns or issues raised about the paper. We are sorry to hear that the paper was difficult to understand, we tried our best to write clearly but are open to any and all suggestions as to how we could improve our academic writing. Be it general feedback on the writing style itself, or even particular critiques, this would be immensely helpful.
Onto the weaknesses and questions.
In response to W1 and Q1. Unclear contribution and differences with regularised MCTS with uniform sampling. You are absolutely correct to state that we don’t present a new algorithm: this is regularised MCTS with uniform sampling. Our goal in this paper is to provide insights on generating recommendations in regularised RL. Our most important contribution with respect to bandits, and MCTS more generally, is that for the specific recommendation problem we study, uniform sampling seems to be optimal (in a sense). This is a very surprising result, since prior work (https://arxiv.org/abs/2507.10797) showed that exploration was almost unnecessary for a related type of problem. By generalising prior works, we expand the literature on recommendation problems, and the methods for solving them efficiently. We hope that this has addressed your concern. In particular, we want to highlight that the value of our work is not in the algorithm, but in showing that the algorithm is useful and interesting, despite prior work suggesting that uniform sampling should not be necessary.
In response to Q2. Practical domains for recommendation problems. We see practical applications of these sorts of recommendation algorithms all over regularised RL. Take soft actor-critic (SAC). It trains a “critic” network by generating Q-value estimates, and taking a loss against them. Our work can directly plug into an algorithm like SAC, where a Q-value estimate can be generated with a bandit or MCTS problem. The faster and more accurately this estimate converges, the better. Additionally, in works like AlphaZero, MCTS is used to iteratively train a value function and a policy function. A similar approach can be taken with our work, as we have just demonstrated that for regularised RL value and policy functions, MCTS with uniform sampling is in a sense optimal.
We also provide a list of practical applications (other than biological sequence design) in which Regularised RL which we believe our approach could be applied to (and we find interesting): LLM Fine Tuning, as in https://arxiv.org/abs/2310.04363, https://arxiv.org/pdf/2203.02155, https://openreview.net/forum?id=PXD3FAVHJT Combinatorial optimization, as in https://proceedings.neurips.cc/paper_files/paper/2023/hash/27571b74d6cd650b8eb6cf1837953ae8-Abstract-Conference.html Healthcare: https://dl.acm.org/doi/abs/10.1145/3580305.3599800
We amended the Introduction to reflect these domain applications and better motivate our contribution (see changes in red).
In response to W2. Tree depth complexity issues. We do agree in general that in real-world systems, performing an “action” would not be possible, or at least it would be highly expensive. However, the implicit assumption of MCTS (and many RL problems in general) is that a simulator of the environment is available for us to use, hopefully cheaply. So while we agree that in the real world, this sort of search is totally untenable for certain problems, all we require is a simulator and the search algorithms would be achievable. Such is the case in many real-world settings today (like in drug discovery).