acceptodds
Under review as a conference paper at ICLR 2027

Regret Analysis of Retry-Based Bandits

10 views

Abstract

We provide the first regret analysis of ReMax in stochastic multi-armed bandits. Originally introduced for reinforcement learning, ReMax is motivated by the role of exploration when multiple attempts are allowed, and is closely related to retry-based objectives such as pass@ and max@, which value the best outcome across those attempts. Given a posterior over arm values, ReMax chooses a sampling distribution that maximizes the posterior expected maximum arm value over virtual draws. For Gaussian rewards with arms and any fixed integer , we characterize optimal sampling distributions through an expected-improvement balance condition and prove an finite-time bound on expected regret. Our analysis separates a logarithmic contribution from rounds without optimal-arm underestimation and a recovery term that dominates the bound. For every fixed instance with pairwise distinct arm means, we further prove an asymptotic logarithmic regret upper bound whose coefficient is at most times the optimal coefficient by Lai and Robbins. When , this bound implies the asymptotic optimality of ReMax. Gaussian-bandit experiments show that ReMax performs competitively with Thompson sampling and KL-UCB. They also reveal a trade-off: larger reduces regret incurred during optimal-arm underestimation, but this reduction does not necessarily translate into lower total regret. Controlled recovery experiments show that separating suboptimal means accelerates recovery, while severe underestimation of the optimal arm can lead to long delays before it is sampled again.

Primary area:
learning theory
Keywords:
Multi-armed Bandits, ReMax, Retry-based Exploration, Regret Analysis, Asymptotic Optimality

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_s4PuOpenReview ↗
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
  1. the paper is very well written and structured, it is easy to read and understand what is happening.
  2. the theoretical result is elegant, an algorithm as simple as classic thompson sampling that achieves the asymptotic optimal regret from Lai and Robbins.
  3. 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:

  1. 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.
  2. the paper doesnt have a conclusion section. maybe some of the limitations can be summarized there.
Questions for authors
  1. 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.
  2. can the author show experiment on a non-Gaussian distribution?
2 comments
AuthorsOpenReview ↗

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=2M=2. ReMax draws two arms from π\pi and is rewarded with the better of the two posterior samples. Suppose π\pi puts almost all of its mass on the arm with the highest posterior mean, call it arm bb, and we move a small mass to another arm jj. Then, with small probability, one draw is bb and the other is jj, and the outcome is

max⁡(θb,θj)=θb+(θj−θb)+.\max(\theta_b, \theta_j) = \theta_b + (\theta_j - \theta_b)^+ .

So trying arm jj next to arm bb can only help: if θj\theta_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)+]\mathbb{E}[(\theta_j - \theta_b)^+], which is large when the posterior of arm jj is wide, that is, when the arm has few samples. The cost only appears when both draws are jj. 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)(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=2M=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=16K=16 Bernoulli arms with means 0.90,0.85,…,0.150.90, 0.85, \dots, 0.15, and the horizon is T=105T=10^5. We run ReMax with M=2,3,4M=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=3M=3 and M=4M=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=105T=10^5, Thompson sampling is the lowest (119), followed by ReMax with M=3M=3 (139), KL-UCB (180), ReMax with M=2M=2 (185) and ReMax with M=4M=4 (205). Increasing MM reduces the regret caused by underestimation of the best arm, from 147 at M=2M=2 to 31 at M=3M=3 and 26 at M=4M=4. For M=2M=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.

Thank you again for your time and thoughtful review. We truly appreciate your feedback on our work.

Reviewer_BX6AOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the regret of ReMax in stochastic multi-armed bandits. Given a posterior over arm means, ReMax selects a sampling distribution that maximizes the posterior expected maximum value over MM virtual draws. Repeated selections of the same arm reuse its posterior sample, and only one arm is actually pulled per round. The objective therefore serves as a mechanism for exploration, while performance is measured by ordinary cumulative regret.

The authors first prove that the ReMax objective is concave and characterize its optimal sampling distributions through an expected-improvement balance condition. For independent unit-variance Gaussian rewards and exact optimization, they establish an instance-dependent finite-time regret bound of order O(Tlog⁡T)O(\sqrt{T\log T}) for fixed MM. When all arm means are pairwise distinct, they further prove

\frac{\mathbb E[\operatorname{Reg}(T)]}{\log T} \le 2(M-1)\sum_{j>1}\frac{1}{\Delta_j}.$$ For $M=2$, this matches the Lai–Robbins coefficient and establishes asymptotic optimality on the stated instance class. Experiments compare a stochastic-gradient approximation of ReMax with Thompson sampling and Gaussian KL-UCB, and investigate recovery from underestimation of the optimal arm.
Critical strengths
  1. The paper provides a meaningful theoretical connection between retry-based optimization and cumulative-regret minimization. Although ReMax optimizes a virtual best-of-MM objective, the learner is evaluated by ordinary cumulative reward. Establishing that this objective induces sufficient exploration for sublinear regret helps explain why the mechanism can be effective beyond its original motivation.

  2. The expected-improvement characterization is clear and useful. Concavity makes the optimality conditions sufficient, and the balance condition explains how the algorithm distributes probability among arms according to their potential contributions to the virtual maximum. This provides an interpretable description of the sampling rule and a central tool for the regret analysis.

  3. The asymptotic optimality result for M=2M=2 is strong. The analysis identifies the leading logarithmic coefficient rather than only establishing the order of regret. Matching the Lai–Robbins coefficient is a substantial guarantee for an exploration rule derived from a different objective. For larger fixed MM, the upper bound also quantifies a possible exploration cost through the factor M−1M-1.

  4. The experimental evaluation helps explain the algorithm’s behavior. Reporting both total regret and regret incurred during optimal-arm underestimation reveals that larger MM can improve recovery without monotonically improving total performance. The controlled recovery experiments and the comparison between exact ReMax and its numerical approximation further connect the theoretical analysis to observable behavior.

Critical weaknesses
  1. The finite-time guarantee has substantial gap dependence that is not apparent from the headline rate. The abstract emphasizes an O((M−1)KTlog⁡T)O(\sqrt{(M-1)KT\log T}) bound, whereas Theorem 1 includes the multiplicative factor \qquad \epsilon\le \min\{1,\Delta_{\min}/5\},$$ in the underestimation term. This can make the bound large when the minimum gap is small. Although the main text acknowledges that the result is distribution-dependent, the abstract should make this qualification explicit. Moreover, it remains unclear whether the square-root dependence on the horizon reflects an actual limitation of ReMax or looseness in the recovery analysis.
  2. The logarithmic regret result requires all arm means to be pairwise distinct, rather than only requiring a unique optimal arm. This excludes simple instances such as (1.5,1,1)(1.5,1,1), where identifying the best arm does not require distinguishing the two suboptimal arms. The paper provides a useful explanation and empirical evidence for slower recovery when suboptimal means coincide, but does not establish whether such ties actually prevent logarithmic regret or only limit the current proof. For nearly tied means, the dependence of the recovery constants and the horizon needed to observe the asymptotic behavior also remain unclear.
Questions for authors
  1. Can the authors state the gap dependence explicitly in the abstract and clarify whether a gap-independent regret bound can be obtained?

  2. Is there an instance showing that square-root-order regret is necessary for exact ReMax, or can the finite-time underestimation bound be improved?

  3. Does exact ReMax achieve logarithmic regret when the optimal arm is unique but some suboptimal arms have equal means? Can the authors extend the theorem or provide a lower bound demonstrating slower regret in this case?

  4. How do the recovery constants depend on the minimum separation between suboptimal means? Can the analysis quantify how this separation affects the horizon required for the logarithmic asymptotic behavior to become informative?

2 comments
AuthorsOpenReview ↗

Response to Reviewer BX6A

We sincerely thank the reviewer for the careful reading. The comments point precisely to several places that the paper had left unclear, and addressing them has given a more complete picture of ReMax, including a new lower bound for tied suboptimal arms (Proposition 5 in Appendix F).

W1 & Q1

Thanks for the suggestion, we agree that the abstract should state it explicitly. The revised abstract is given in Appendix E of the updated PDF. We will merge it into the main paper in the next version.

As for the gap-independent regret bound, unfortunately, we currently don't have one. Our analysis requires ε=Θ(Δmin⁡)\varepsilon = \Theta(\Delta_{\min}), so the bound cannot be directly converted into a distribution-independent one, as noted in the discussion after Theorem 1. We leave this as an open question.

W1 & Q2

Consider M=2M=2 and three arms with μ1>μ2=μ3\mu_1 > \mu_2 = \mu_3, for example (1.5,1,1)(1.5, 1, 1), and let Δ=μ1−μ2\Delta = \mu_1 - \mu_2. Below GijG_{ij}, ϕ\phi and Φ\Phi are as in Equation (6) of the paper. We give the intuition here; the formal statement is in our answer to the next question. The scenario is the following. Suppose that the first sample of arm 1 falls at μ2−a\mu_2 - a for some large aa, so that arm 1 looks much worse than the other two arms.

First, as long as arm 1 is not pulled, its posterior stays N(μ2−a,1)\mathcal{N}(\mu_2 - a, 1), and its expected improvement over arms 2 and 3 stays at about ϕ(a)−aΦ(−a)≈e−a2/2\phi(a) - a\Phi(-a) \approx e^{-a^2/2}: a fixed, very small number.

Second, while arm 1 is excluded, arms 2 and 3 share all the pulls, so after tt rounds each of them has order tt samples and the posterior of θ2−θ3\theta_2 - \theta_3 has standard deviation 1/N2+1/N3\sqrt{1/N_2 + 1/N_3} of order 1/t1/\sqrt{t}. Since the true means are equal, the difference of the empirical means is also of order 1/t1/\sqrt{t}. Hence their mutual expected improvement is

G23≈G32≈ctG_{23} \approx G_{32} \approx \frac{c}{\sqrt{t}}

for a constant cc. In contrast, if the two means were separated, this quantity would decay exponentially in tt.

Third, by the expected-improvement balance (Proposition 1), arm 1 stays outside the support as long as its expected improvement is below the common level of arms 2 and 3:

e−a2/2<ct⟺t<c2ea2.e^{-a^2/2} < \frac{c}{\sqrt{t}} \quad\Longleftrightarrow\quad t < c^2 e^{a^2}.

While arm 1 is outside the support it is not pulled, so its expected improvement stays at e−a2/2e^{-a^2/2}, whereas the common level of arms 2 and 3 decays only as c/tc/\sqrt{t}. Arm 1 is therefore not pulled for about ea2e^{a^2} rounds.

Finally, take a=log⁡Ta = \sqrt{\log T}. Then arm 1 stays out for the whole horizon, and the regret is about ΔT\Delta T. The first sample of arm 1 is N(μ1,1)\mathcal{N}(\mu_1, 1), so this happens with probability about

e−(a+Δ)2/2=T−1/2⋅e−Δlog⁡T−Δ2/2,e^{-(a+\Delta)^2/2} = T^{-1/2} \cdot e^{-\Delta\sqrt{\log T} - \Delta^2/2},

where the last factor decays more slowly than any power of TT. Multiplying the two suggests that the expected regret grows like T1/2T^{1/2} up to subpolynomial factors. This is made rigorous in our answer to the next question, so the square-root rate of the underestimation term reflects the actual behavior of ReMax on instances with tied suboptimal arms.

W2 & Q3

No, ReMax doesn't achieve logarithmic regret when some suboptimal arms have equal means. Following our answer to the previous question, we provide a formal proof of the lower bound for the instance described there in Appendix F of the updated PDF (Proposition 5): for M=2M=2 and three arms with μ1>μ2=μ3\mu_1 > \mu_2 = \mu_3, the expected regret of exact ReMax is at least T1/2−ηT^{1/2-\eta} for every η>0\eta > 0 and all sufficiently large TT. Since ReMax cannot do better on this instance, logarithmic regret does not hold in general when the optimal arm is unique but some suboptimal arms have equal means.

W2 & Q4

Let γ\gamma denote the minimum separation between suboptimal means (γ−\gamma_- in Appendix C). We understand both parts of the question as being about the additive constant in the bound of Theorem 2: how it depends on γ\gamma.

The separation enters the proof through Lemma 12, which bounds the expected improvement between two suboptimal arms with mm samples each by a term of order exp⁡(−γ2m/16)\exp(-\gamma^2 m/16) (Equation (80)). Lemma 15 uses this bound, and making it small enough requires mm of order γ−2log⁡(1/γ)\gamma^{-2}\log(1/\gamma). This threshold becomes the constant of Proposition 4 (Equation (139)), which enters the regret bound through Equation (168) and ends up in the O(1)O(1) term of Equation (174). The additive constant is therefore at most Cγ−2log⁡(1/γ)C \gamma^{-2}\log(1/\gamma) for a constant C>0C>0. The logarithmic term dominates this bound once ∑j≥2log⁡T/Δj\sum_{j \ge 2} \log T / \Delta_j (asymptotically optimal logarithmic term) exceeds $C \gamma^{-2}\log(1/\gamma) $.

Thank you again for your time and thoughtful review. We truly appreciate your feedback on our work.

Reviewer_wifMOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper provides the regret analysis of ReMax in stochastic multi armed bandits. ReMax selects a sampling distribution that maximizes the posterior expected maximum value over M virtual draws. The authors prove an expected improvement balance condition, derive a finite time regret bound of order square root of T log T, and establish a logarithmic asymptotic bound when all arm means are distinct. For M = 2, the asymptotic coefficient matches the Lai and Robbins lower bound. Experiments on Gaussian bandits compare ReMaxGrad with Thompson sampling and KL UCB, while controlled recovery studies examine optimal arm underestimation.

Critical strengths

1.Strong theoretical contribution. The paper moves ReMax from an empirically motivated retry objective to an algorithm with finite time and asymptotic regret guarantees. The asymptotic optimality for M = 2 is particularly consequential because it precisely characterizes when the induced exploration is information theoretically efficient.

2.Clear analysis of the recovery mechanism. The decomposition into saturation and optimal arm underestimation explains the main bottleneck of ReMax. The result that competition between similar suboptimal arms can delay recovery gives useful insight into both the theory and the observed experimental behavior.

Critical weaknesses

1.Mismatch between theory and experiments. The theorems require an exact ReMax optimizer, whereas the main experiments use the approximate ReMaxGrad algorithm. The exact comparison is limited to M = 2 and a shorter horizon, leaving the empirical results for larger M only indirectly connected to the theory.

2.Limited scope relative to the retry motivation. The virtual retry budget influences exploration, but performance is still measured by standard single pull regret rather than an actual best of M or pass at k objective. The analysis is also restricted to exact optimization under unit variance Gaussian rewards, so its implications for broader retry based learning remain uncertain.

Questions for authors

Please address the concerns raised in the Weaknesses section. I am willing to reconsider and increase my score.

4 comments
AuthorsOpenReview ↗

Response to Reviewer wifM

We sincerely thank the reviewer for pointing out the gap between the approximate ReMaxGrad algorithm and the theory. This comment led us to build an exact solver for M≥3M \ge 3. With it, we found that the fast regret growth of ReMaxGrad with M=3M=3 and M=4M=4 in Figure 2(c) comes from the approximation error of ReMaxGrad and not from ReMax itself.

W1

We have implemented a solver that computes the ReMax policy exactly for M≥3M \ge 3; it is described in Appendix I of the updated PDF. For M=2M=2 the policy is computed analytically, as in the submission.

With this solver we reran the fixed-instance experiment of Section 4.2 (Figure 2) using exact ReMax for M=2,3,4M=2,3,4; the results are in Appendix J (Figure 9 and Table 3). The table below reports the slope of the cumulative regret against log⁡t\log t between t=107t=10^7 and t=2×107t=2\times10^7 (mean over 100100 trajectories with one standard error) and compares it with the coefficient (M−1)CLR(M-1)C_{\mathrm{LR}} of Theorem 2, where CLR≈66.36C_{\mathrm{LR}} \approx 66.36. For exact ReMax the slope stays below this coefficient for every MM, consistent with Theorem 2, whereas for ReMaxGrad with M=3M=3 and M=4M=4 it is well above it.

MethodSlope(M−1)CLR(M-1)C_{\mathrm{LR}}Slope // (M−1)CLR(M-1)C_{\mathrm{LR}}
ReMax, M=2M=247.9±2.747.9 \pm 2.766.466.40.720.72
ReMax, M=3M=3116.1±3.2116.1 \pm 3.2132.7132.70.870.87
ReMax, M=4M=4181.9±5.0181.9 \pm 5.0199.1199.10.910.91
ReMaxGrad, M=2M=247.5±3.347.5 \pm 3.366.466.40.720.72
ReMaxGrad, M=3M=3273.8±15.8273.8 \pm 15.8132.7132.72.06\mathbf{2.06}
ReMaxGrad, M=4M=42121.2±83.82121.2 \pm 83.8199.1199.110.65\mathbf{10.65}

We also extended the comparison between exact ReMax and ReMaxGrad (Figure 6 of the submission) to a longer horizon and to larger MM: from T=20,000T=20{,}000 and M=2M=2 to T=106T=10^6 and M=2,3,4M=2,3,4, with 1,0001{,}000 trajectories (Figure 10 in Appendix J).

We will rerun the experiments of the paper with the exact solver in place of ReMaxGrad and update them in the next version. We hope these results connect the experiments for larger MM more directly to the theory.

W2

We agree that the emphasis on retry-based objectives in the title and the introduction can suggest that the paper evaluates a best-of-MM or pass@kk objective. The retry idea behind these objectives, valuing the best outcome among several attempts, is indeed the central idea of ReMax and the source of its exploration, which is why we emphasize it. The setting we study, however, is the standard bandit problem, and the learner does not actually spend the budget MM on pulling arms. The MM attempts enter only through the objective in Equation (1): at each round the algorithm takes the distribution πt\pi_t that maximizes this objective under the current posterior, and then pulls a single arm drawn from πt\pi_t. For example, our implementation computes πt\pi_t directly from the posterior and does not actually draw MM arms. Since one arm is pulled and one reward is observed per round, we measure performance by the standard regret, as for Thompson sampling and KL-UCB. We will state this positioning explicitly in the introduction of the final version (the added sentence is given in Appendix E.3 of the updated PDF).

However, if the reviewer is specifically interested in the relationship between the standard regret and a best-of-nn metric, we could define the best-of-nn regret of round tt as

rn(πt)=μ1−E[max⁡m≤nμAm],r_n(\pi_t) = \mu_1 - \mathbb{E}\Bigl[\max_{m \le n} \mu_{A_m}\Bigr],

where A1,…,AnA_1, \dots, A_n are independent draws from πt\pi_t. Since the maximum of nn values is at least the first one, rn(πt)≤μ1−E[μA1]r_n(\pi_t) \le \mu_1 - \mathbb{E}[\mu_{A_1}], which is the expected single-pull regret of round tt. Summing over tt, the cumulative best-of-nn regret is bounded by the standard regret E[Reg(T)]\mathbb{E}[\mathrm{Reg}(T)] for every n≥1n \ge 1, so Theorems 1 and 2 also bound it, but this is not the focus of the paper. If the reviewer thinks this would aid the paper, we would be happy to include it.

The regret analysis is indeed for Gaussian rewards. The algorithm itself is general and not restricted to Gaussian rewards: the objective (Equation (1)), the sampling rule (Equation (2)), and the concavity and expected-improvement balance of Proposition 1 are stated for a general posterior. Appendix G of the updated PDF gives an example with Bernoulli rewards and Beta posteriors (Figure 7 and Table 2; see also our response to Reviewer s4Pu), where ReMax shows the same trade-off in MM as in the Gaussian experiments.

Thank you again for your time and thoughtful review. We truly appreciate your feedback on our work.

Thank you for the detailed response and additional experiments. After considering the clarifications, I maintain my current rating of 3.

Thank you for your comment! We might be able to change the title to "Regret Analysis of Retry-Based Bandit Algorithms" to make it clear that it is about retry-based algorithms. We will also include the implementation details and results of the exact solver and the experiments with Bernoulli rewards in the final version. Please let us know if you have any further concerns

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Changes in the Updated PDF

We thank all reviewers for their careful reading and constructive comments. We have uploaded an updated PDF. The main text is unchanged during the discussion phase; all additions are in new appendices placed after those of the submission:

  • Appendix E: text that will be merged into the main text in the final version, with the additions shown in green. It contains the revised abstract (E.1), a conclusion and limitations section (E.2), and a sentence added to the introduction (E.3).
  • Appendix F: a lower bound of order T1/2−ηT^{1/2-\eta} on the regret of ReMax when two suboptimal arms are tied (Proposition 5).
  • Appendix G: an experiment with Bernoulli rewards (Figure 7 and Table 2).
  • Appendix H: a three-arm toy example of how ReMax explores (Figure 8).
  • Appendix I: an exact solver for the ReMax policy with M≥3M \ge 3.
  • Appendix J: the fixed-instance experiments rerun with exact ReMax for M=2,3,4M=2,3,4 (Figures 9 and 10, Table 3).

Our point-by-point responses are posted under each review.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.