- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
the paper studies the problem of ReMax, a criteria that can be used directly as a stochastic algorithm in multi-armed bandits, where M virtual arms selection happens and measure the expected improvement. in each round a distribution over all the arms is selected which maximizes the ReMax objective. as its major contribution, the authors prove the regret achieves the optimal rate from Lai and Robbins, which is very classic and established lower bound for multi-armed bandits. the paper also shows a set of experiments where the proposed algorithm can achieve similar performance as TS.
Critical strengths
- the paper is very well written and structured, it is easy to read and understand what is happening.
- the theoretical result is elegant, an algorithm as simple as classic thompson sampling that achieves the asymptotic optimal regret from Lai and Robbins.
- tho lack direct connection, but potentially analysis tools of this paper can be insightful for future understanding the best of n sampling often used in llm area now.
Critical weaknesses
it makes a lot sense that the regret analysis is done under Gaussian assumption. but since the ReMax is a more generical definition, the experiments could be more comprehensive if it is eval-ed for other distribution, such as Bernoulli, and it would be even more interesting if the authors can test on certain llm reward (since the authors mentioned llm in the introduction, but I totally understand it is beyond the scope of the paper.)
two minor writing issues:
- the two references Nishimorietal.,2026 and Koyamadaetal.,2022 in line 102, they seem to be two papers with exactly same title name but slightly different for the author's names, maybe better to clarify a bit.
- the paper doesnt have a conclusion section. maybe some of the limitations can be summarized there.
Questions for authors
- the objective ReMax, it is easy but also not so easy to understand why it works so well. Can the author explain more on why such an objective can incentive exploration? it would be better if a simple example can be provided showing how the algorithm behaves in toy case across different round.
- can the author show experiment on a non-Gaussian distribution?
2 comments
Thank you again for your time and thoughtful review. We truly appreciate your feedback on our work.
Response to Reviewer s4Pu
We thank the reviewer for the careful reading and the constructive suggestions. Following them, we added an experiment with Bernoulli rewards (Appendix G), a toy example of how ReMax explores (Appendix H), and a conclusion section (Appendix E.2) to the updated PDF. Our point-by-point responses are below.
W1
Thank you for the suggestion and for the understanding. We do not have experiments with LLM rewards at present. The closest existing evidence for ReMax beyond bandits is Nishimori et al. (2026), who optimize the same objective with policy gradients and evaluate it on deep reinforcement learning benchmarks (MinAtar, Atari and Craftax). Evaluating ReMax with LLM rewards is an interesting direction that we leave for future work. For Bernoulli rewards, please see our answer to Q2.
W2
Thank you for the careful reading. The two titles differ in the last word: Koyamada et al. (2022) is "... via Resetting" and Nishimori et al. (2026) is "... via Retrying". Koyamada et al. (2022) originally proposed the ReMax objective and relied on a resettable simulator to estimate policy gradients. Nishimori et al. (2026) extended it with a Q-function-based formulation that does not require simulator resets.
W3
Thanks for the suggestion, we agree that the paper should have a conclusion section. A conclusion that also summarizes the limitations is given in Appendix E.2 of the updated PDF. We will merge it into the main paper in the next version.
Q1
The intuition is easiest to see for M=2. ReMax draws two arms from π and is rewarded with the better of the two posterior samples. Suppose π puts almost all of its mass on the arm with the highest posterior mean, call it arm b, and we move a small mass to another arm j. Then, with small probability, one draw is b and the other is j, and the outcome is
max(θb,θj)=θb+(θj−θb)+.
So trying arm j next to arm b can only help: if θj turns out to be low, the other draw covers it, and if it turns out to be high, we gain. The expected gain is the expected improvement E[(θj−θb)+], which is large when the posterior of arm j is wide, that is, when the arm has few samples. The cost only appears when both draws are j. Balancing this gain against this cost is exactly the expected-improvement balance in Proposition 1. As a result, ReMax explores an arm in proportion to how much better it could still be, and stops exploring it once its posterior is narrow enough that this upside disappears.
We added a toy example in Appendix H of the updated PDF (Figure 8). There are three arms with true means (1.0,0.9,0.5). At the start, arm 1 has 20 samples with empirical mean 1.0, arm 3 has 5 samples with empirical mean 0.5, and arm 2 has a single unlucky sample with empirical mean 0.3. Arm 2 has the lowest estimate, but its posterior is the widest, so its expected improvement over arm 1 is the largest. ReMax with M=2 therefore gives arm 2 about 15% of the probability in the first round and gives arm 3 almost none. In the trajectory shown in Figure 8(a) and (b), arm 2 is pulled within the first few rounds, its estimate moves from 0.3 to about 0.8, and its probability rises sharply while the two leading arms are hard to tell apart. As more samples arrive, the posteriors narrow, the probability of arm 2 decays, and arm 1 receives about 95% of the probability by round 400. Over 1,000 trajectories, arm 2 is pulled again within 20 rounds in 95% of them (Figure 8(c) shows the average policy).
Q2
Yes. We added an experiment with Bernoulli rewards in Appendix G of the updated PDF (Figure 7 and Table 2).
The instance has K=16 Bernoulli arms with means 0.90,0.85,…,0.15, and the horizon is T=105. We run ReMax with M=2,3,4 using Beta posteriors in the same objective, and compare it with Bernoulli Thompson sampling and KL-UCB. Thanks to a comment of Reviewer wifM, we have also improved how the ReMax policy is computed now: for M=3 and M=4 we no longer use the stochastic-gradient approximation based ReMaxGrad, and instead maximize the objective directly with a numerical solver. All results are over 1,000 trajectories.
The picture is the same as in the Gaussian experiments. In mean regret at T=105, Thompson sampling is the lowest (119), followed by ReMax with M=3 (139), KL-UCB (180), ReMax with M=2 (185) and ReMax with M=4 (205). Increasing M reduces the regret caused by underestimation of the best arm, from 147 at M=2 to 31 at M=3 and 26 at M=4. For M=2 the mean is driven by a few trajectories with long underestimation: its median regret is 56, the lowest of all methods, and it is below Thompson sampling in 83% of the trajectories.