Pith. sign in

REVIEW 2 major objections 6 minor 22 references

Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that Follow-the-Perturbed-Leader with Pareto perturbations attains the optimal $O(\sqrt{mdT})$ regret in adversarial size-invariant combinatorial semi-bandit problems, and that a conditional resampling variant reaches…

desk verdict The main theorem is a genuine advance and looks correct, but the advertised CGR complexity saving is not supported by the algorithm as written. read the letter →

arxiv 2506.12490 v2 pith:I5OJEVL7 submitted 2025-06-14 cs.LG stat.ML

Botao Chen , Junya Honda This is my paper · ORCID
classification cs.LGstat.ML MSC 68Q3262L05
keywords Follow-the-Perturbed-Leadercombinatorialsemi-banditssize-invariantactionsetsgeometricresamplingconditionalFréchetdistributionParetominimaxregret
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Follow-the-Perturbed-Leader (FTPL) plays the action that minimizes cumulative estimated loss plus a random perturbation, and it computes actions without solving an optimization problem for selection probabilities. The paper proves that in adversarial size-invariant combinatorial semi-bandits — every action picks exactly $m$ of $d$ base arms and only the chosen arms' losses are revealed — FTPL with Pareto perturbations incurs $O(\sqrt{mdT})$ pseudo-regret, matching the known lower bound, and with Fréchet perturbations incurs $O(\sqrt{m^2 d^{1/\alpha}T}+\sqrt{mdT})$. This matters because prior FTPL analyses for standard multi-armed bandits did not extend cleanly to combinatorial action sets, and a recent attempt at this extension contains a flawed stability argument. The paper further adapts Conditional Geometric Resampling, cutting per-round complexity from $O(d^2)$ to $O(md(\log(d/m)+1))$ without changing the regret rate. If the proof is right, FTPL is an optimization-free policy with minimax-optimal adversarial regret for this problem class.

What carries the argument

The load-bearing object is the ratio $J_i(\lambda;D)/\phi_i(\lambda;D)$: the derivative of base-arm $i$'s selection probability with respect to its own cumulative loss, divided by the probability itself. Lemma 3 bounds this ratio by a maximum over subsets $B_{i,w}$ of the simpler ratios $J_{i,\theta}(\lambda^*;D,B_{i,w})/\phi_{i,\theta}(\lambda^*;D,B_{i,w})$, and the reduction is powered by Lemma 11, which asserts that for the Fréchet and Pareto CDFs the ratio $\int \psi(z)F(z+\lambda_j)/(z+\lambda_i)\,dz \big/ \int \psi(z)F(z+\lambda_j)\,dz$ is monotonically increasing in $\lambda_j$. That monotonicity lets Lemmas 12–14 drop base arms one at a time, converting a high-dimensional stability problem into one-dimensional integral ratios. For the complexity result, the mechanism is Conditional Geometric Resampling: for an arm with $\sigma_i>m$, sample perturbations conditioned on the event that its perturbation ranks among the top $m$ among the $\sigma_i$ arms with no larger cumulative loss, implemented by a uniform random swap, obtaining an unbiased estimator $(\sigma_i/m\vee 1)M_{t,i}$ and expected resampling count $m+m\log(d/m)$.

What would settle it

Numerically evaluate the derivative of that integral ratio with respect to $\lambda_j$ on a dense grid (for example $\lambda_i,\lambda_j\in[0,10]$, $\alpha\in(1,5]$, $\psi\equiv 1$) for both the Fréchet and Pareto CDFs; a single negative derivative would falsify Lemma 11 and collapse the proof chain to Theorem 1. Alternatively, symbolically verify the key bracket in the proof, which for the Pareto case reduces to the monotonicity of $x^{\alpha+1}-x$ on $[1,\infty)$, and check that no integration domain violates that condition.

Watch

Extended reading notes

Core claim

On its own terms, the paper's claim is Theorem 1: in the adversarial size-invariant semi-bandit setting, FTPL with geometric resampling and Fréchet perturbations of shape $\alpha>1$ achieves $R(T)=O(\sqrt{m^2 d^{1/\alpha}T}+\sqrt{mdT})$, and with Pareto perturbations it achieves $R(T)=O(\sqrt{mdT})$, matching the $\Omega(\sqrt{mdT})$ minimax lower bound. The proof decomposes the pseudo-regret into a penalty term and a stability term, and bounds the stability term by showing that the derivative-to-probability ratio $J_i(\lambda;D)/\phi_i(\lambda;D)$ is dominated by a maximum over subsets of base arms (Lemma 3), which then reduces to explicit distribution-dependent constants (Lemma 4). The same section extends Conditional Geometric Resampling to size-invariant semi-bandits, claiming unbiased inverse-probability estimators with expected resampling count $m+m\log(d/m)$ and per-round cost $O(md(\log(d/m)+1))$, with no loss in the regret order. The paper also reconstructs a missing step in a recent competing FTPL analysis for this problem, argues that the step is not established by analogy, and provides a numerical counterexample to the claimed monotonicity.

Load-bearing premise

The load-bearing premise is Lemma 11, the claim that for Fréchet and Pareto perturbation distributions the integral ratio $\int \psi(z)F(z+\lambda_j)/(z+\lambda_i)\,dz \big/ \int \psi(z)F(z+\lambda_j)\,dz$ increases monotonically in $\lambda_j$; if that monotonicity fails for either distribution, the subset-reduction bound in Lemma 3, the stability bounds in Lemmas 4–6, and Theorem 1 all lose their support.

Editorial extensions

If this is right

  • With Pareto perturbations, FTPL's $O(\sqrt{mdT})$ regret matches the $\Omega(\sqrt{mdT})$ lower bound, so an optimization-free policy is minimax optimal in adversarial size-invariant semi-bandits.
  • With Fréchet perturbations the regret is $O(\sqrt{m^2 d^{1/\alpha}T}+\sqrt{mdT})$; as $\alpha$ grows the extra factor $d^{1/(2\alpha)}$ approaches $1$, so the bound tracks the optimal rate closely for large shape parameters.
  • Conditional Geometric Resampling lowers per-round resampling cost from $O(d^2)$ to $O(md(\log(d/m)+1))$ with the same regret order, and its estimator has no larger variance than the original geometric resampling estimator.
  • A recent competing proof of FTPL regret for this problem is invalid as written; the paper's numerical counterexample shows the specific monotonicity claim it relies on does not hold, so that result needs either a new proof or a modified argument.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the CGR estimator has variance no larger than GR's and the paper's regret proof tracks only the estimator's first and second moments, a formal regret bound for FTPL with CGR should follow by the same lemmas; an implementation benchmark on large $d$ would test the predicted speedup.
  • Lemma 11 is a pure property of the perturbation CDF, not of the regret, so if the same monotonicity holds for other heavy-tailed families (with suitable shapes), the subset-reduction argument would extend near-optimal FTPL regret to those families; this is an extrapolation the paper does not make.
  • The paper restricts attention to the adversarial regime and to actions of fixed size $m$; a natural next question, left implicit, is whether the same perturbation-and-resampling machinery yields best-of-both-worlds guarantees in stochastic combinatorial semi-bandits, as it does for multi-armed bandits.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper studies Follow-the-Perturbed-Leader (FTPL) with geometric resampling in size-invariant combinatorial semi-bandit problems with adversarial losses. In Section 3 it claims a regret bound of O(sqrt(m^2 d^{1/alpha} T) + sqrt(mdT)) for Frechet perturbations with shape alpha > 1 and O(sqrt(mdT)) for Pareto perturbations, the latter matching the Omega(sqrt(mdT)) lower bound. The proof rests on Lemmas 3-6, which bound the stability term through rank-based ratio inequalities, and on the regret decomposition in Lemma 2. Section 5 proposes Conditional Geometric Resampling (CGR), claiming per-round complexity O(md(log(d/m)+1)) without changing the regret guarantee. Section 9 argues that a competing proof by Zhan et al. is flawed and provides a numerical counterexample.

Significance. If the regret bounds are correct, the paper makes a substantive contribution: it supplies the first proof of near-optimal FTPL regret in adversarial combinatorial semi-bandits with heavy-tailed perturbations, including a Pareto case matching the lower bound, and it provides an optimization-free alternative to FTRL-based algorithms. The proof chain I examined is largely coherent: Lemma 11's monotonicity, which the reader identified as the weakest assumption, is a correct calculation for both the Frechet and Pareto CDFs, and the summations in Lemma 6 are consistent with the stated rates. The paper also does a useful service by isolating a concrete flaw in Zhan et al. (2025). However, the CGR contribution is not established at the claimed level of rigor: the algorithm lacks a specified data structure for the required order-statistic queries, and the formal statement of the conditioning event in Lemma 8 is incorrect as written. The complexity claim is therefore a liability in an otherwise strong theoretical paper.

major comments (2)
  1. [Section 5, Algorithm 3 and Eq. (17)-(18)] The claimed complexity C_resampling = O(d) is unsupported. For every i in U, Lines 13-15 require finding the theta-th largest element of the prefix set {r'_{t,j} : sigma_j <= sigma_i} in each resampling step. A literal scan costs O(sigma_i) per i, i.e. O(md) per resampling in the worst case, and even a standard persistent order-statistics tree would cost Omega(d log d + |U| log d) per resampling unless additional structure is specified. The text's assertion that the value-swapping operation 'does not change the order of the resampling cost' is therefore not justified, and the advertised complexity O(md(log(d/m)+1)) in the Abstract and Section 5 is not established. This does not invalidate Theorem 1, but it is a load-bearing claim for the CGR half of the paper.
  2. [Section 5, Lemma 8] The displayed conditioning event E_{t,i} = { |{j : r''_{t,j} <= r''_{t,i}, sigma_j <= sigma_i}| <= m } is not equivalent to saying that r''_{t,i} lies among the top-m largest elements of the prefix, and it is not a necessary condition for arm i to be selected. If i is selected, at most m-1 prefix arms can have r''_{t,j} > r''_{t,i}, since each such arm also outranks i in the perturbed objective; hence |{j : r''_{t,j} <= r''_{t,i}, sigma_j <= sigma_i}| >= sigma_i - m + 1, which can exceed m. The proof of Lemma 8 actually works with E_{t,i} = {Rank_{i,i} in [m]}, and Algorithm 3's Lines 13-15 implement that rank event. The lemma statement should be corrected to the rank event or the equivalent lower-bound inequality.
minor comments (6)
  1. [Section 4.1 and Lemmas 13-14] The symbol 'em' is used throughout the proof of Lemma 3 and in Lemmas 13-14, but it is never defined; it appears to denote a candidate number of selected arms distinct from the fixed m. Please introduce and define this notation explicitly.
  2. [Section 7.3, proof of Lemma 5] The two events Omega and Omega are introduced with nearly identical symbols, and the set-inclusion argument is difficult to follow. Please use visually distinct notation and state explicitly which cumulative-loss vector is used in each event.
  3. [Section 6, proof of Lemma 9] The definition of the set Delta_d is garbled: the text reads 'Delta_d = {p in [0,1]^d : P_{i in [d]} 1 <= p_i <= m}'. For the equality E[u_t | L_hat_t] = w_t to hold, Delta_d should be the convex hull of the action set, i.e. {p in [0,1]^d : sum_i p_i = m}. Please correct the display.
  4. [Section 7.1, Lemma 15] The exponent is called n in parts of the proof but p in the statement, and the displayed calculation contains 'n' where 'p' is intended. Please make the notation uniform.
  5. [Section 5, Lemma 8 and Eq. (9)] The quantity M_t is used ambiguously: in the proof it is first written as a maximum over low-rank arms plus a sum over high-rank arms, while the surrounding text and Eq. (9) treat M_t as the total number of resampling iterations. Please define M_t once and relate the two expressions explicitly.
  6. [Section 9, Figure 1] The axis labels in Figure 1 are garbled in the manuscript text and the plot is hard to interpret. Please provide a legible figure with labeled axes and a caption giving the exact parameter values used in the numerical counterexample.

Circularity Check

0 steps flagged · score 2.0 of 10

No material circularity: the FTPL regret bound is derived from first principles in the paper; self-citations are not load-bearing. The CGR complexity claim has an implementation gap, but that gap is not circular.

full rationale

The central regret bound is self-contained. Lemma 11 proves the needed monotonicity by direct differentiation of the ratio for Frechet and Pareto CDFs, checking the sign of the symmetrized integrand in the paper. Lemmas 3, 4, 5, and 6 then bound the stability term in terms of subset/rank maxima and integrate the result, and Theorem 1 combines this with the regret decomposition of Lemma 2. No parameter is fitted to the target regret, and the lower bound cited (Audibert et al., 2014) is external. The only potentially load-bearing citations are to the same authors' earlier work: Honda et al. (2023), Lee et al. (2024), and Chen et al. (2025). In each case, however, the manuscript reproduces the needed argument: Lemma 9 and Lemma 5 are proved in Sections 6 and 7.3, and the CGR correctness is proved in Lemmas 7-8 rather than assumed from Chen et al. (2025). Thus these self-citations are methodological, not logical inputs. Separately, Section 5's claim that the theta-th-largest swap 'does not change the order of the resampling cost, which remains C_resampling = O(d)' is not supported by a specified data structure; a literal implementation costs O(sigma_i) per i, i.e., O(md) per resampling. This is a complexity-correctness gap in a headline contribution, but it is not circular: it does not feed back into the proof of Theorem 1. Overall there is no self-definitional, fitted-input, or self-citation-load-bearing step; the derivation chain is independent.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No constants are fitted to data. The learning rate eta is chosen explicitly in Theorem 1 to balance the penalty and stability terms; it is a policy hyperparameter, not a hidden degree of freedom. The central claim rests on the size-invariant action set, the Frechet/Pareto perturbation families, and the standard analytic inequalities listed above. No new entities such as particles, forces, conserved quantities, or dimensions are introduced.

assumptions (5)
  • domain assumption Action set is size-invariant: A = {a in {0,1}^d : ||a||_1 = m}.
    The base-arm probability formula (1)-(2) and the rank-based stability analysis in Lemmas 3-6 assume every action has exactly m base arms; general or matroid constraints are not covered.
  • domain assumption Perturbations are i.i.d. from a Frechet or Pareto distribution with shape alpha > 1, using the exact CDFs given in Section 2.1.
    Lemma 11's monotonicity and Lemma 4's explicit ratio bounds use the algebraic form of these CDFs and their hazard derivatives; the regret bounds are not claimed for other perturbation families.
  • standard math Gautschi's inequality (Lemma 16) and Malik's exact order-statistic moments for Pareto (Lemma 17) are correct.
    Lemma 10 uses these standard results to bound the one-step penalty term E[r^T a_1].
  • domain assumption Loss vectors are bounded in [0,1]^d and chosen adversarially; pseudo-regret is defined against the best fixed action.
    The regret decomposition and estimator arguments use the boundedness of losses and the fixed-hindsight benchmark.
  • standard math The CDF domination G(x) >= F(x-1) between Frechet and shifted Pareto used in Lemma 19 holds on the relevant support.
    This is proved in Lemma 19 via e^(-1/x^alpha) >= 1 - x^(-alpha); it is used to transfer Pareto order-statistic bounds to Frechet.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems." pith.science (2026). https://pith.science/paper/I5OJEVL7

@misc{pith2026250612490,
  author       = {Pith},
  title        = {Pith review of: Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I5OJEVL7}},
  note         = {Machine review of arXiv:2506.12490}
}
abstract

This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in size-invariant combinatorial semi-bandit problems. Recently, Honda et al. (2023) and Lee et al. (2024) showed that FTPL achieves Best-of-Both-Worlds (BOBW) optimality in standard multi-armed bandit problems with Fr\'{e}chet-type distributions. However, the optimality of FTPL in combinatorial semi-bandit problems remains unclear. In this paper, we consider the regret bound of FTPL with geometric resampling (GR) in size-invariant semi-bandit setting, showing that FTPL respectively achieves $O\left(\sqrt{m^2 d^\frac{1}{\alpha}T}+\sqrt{mdT}\right)$ regret with Fr\'{e}chet distributions, and the best possible regret bound of $O\left(\sqrt{mdT}\right)$ with Pareto distributions in adversarial setting. Furthermore, we extend the conditional geometric resampling (CGR) to size-invariant semi-bandit setting, which reduces the computational complexity from $O(d^2)$ of original GR to $O\left(md\left(\log(d/m)+1\right)\right)$ without sacrificing the regret performance of FTPL.

Figures

Figures reproduced from arXiv: 2506.12490 by the authors.

Figure 1
Figure 1. The ratio Ji,4,I(λ)/Ji,3,I(λ) as a function of λq0 for q0 ∈ I \ {i}. Acknowledgements We thank Dr. Jongyeong Lee for pointing out the error in the proof of Lemma 10 in the previous version. References Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with a new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015. Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Reg… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 19 canonical work pages

  1. [1]

    Fighting bandits with a new kind of smoothness

    Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with a new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015

    work page 2015

  2. [2]

    Regret in online combinatorial optimization

    Jean-Yves Audibert, S \'e bastien Bubeck, and G \'a bor Lugosi. Regret in online combinatorial optimization. Mathematics of Operations Research, 39 0 (1): 0 31--45, 2014

    work page 2014

  3. [3]

    Geometric resampling in nearly linear time for follow-the-perturbed-leader with best-of-both-worlds guarantee in bandit problems

    Botao Chen, Jongyeong Lee, and Junya Honda. Geometric resampling in nearly linear time for follow-the-perturbed-leader with best-of-both-worlds guarantee in bandit problems. In International conference on machine learning. PMLR, 2025. In press

    work page 2025

  4. [4]

    Combinatorial multi-armed bandit: General framework and applications

    Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages 151--159. PMLR, 2013

    work page 2013

  5. [5]

    Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations

    Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking, 20 0 (5): 0 1466--1478, 2012

    work page 2012

  6. [6]

    Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems

    Junya Honda, Shinji Ito, and Taira Tsuchiya. Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems . In Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of PMLR, pages 726--754. PMLR, 20 Feb--23 Feb 2023

    work page 2023

  7. [7]

    Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits

    Shinji Ito. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits. Advances in Neural Information Processing Systems, 34: 0 2654--2667, 2021

    work page 2021

  8. [8]

    Matroid bandits: fast combinatorial optimization with learning

    Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. Matroid bandits: fast combinatorial optimization with learning. In Uncertainty in Artificial Intelligence, pages 420--429, 2014

    work page 2014

Show all 22 references
  1. [9]

    Tight regret bounds for stochastic combinatorial semi-bandits

    Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535--543. PMLR, 2015

    2015

  2. [10]

    Follow-the-perturbed-leader with fréchet-type tail distributions: Optimality in adversarial bandits and best-of-both-worlds

    Jongyeong Lee, Junya Honda, Shinji Ito, and Min-hwan Oh. Follow-the-perturbed-leader with fréchet-type tail distributions: Optimality in adversarial bandits and best-of-both-worlds. In Conference on Learning Theory, pages 3375--3430. PMLR, 2024

    2024

  3. [11]

    Exact moments of order statistics from the pareto distribution

    Henrick John Malik. Exact moments of order statistics from the pareto distribution. Scandinavian Actuarial Journal, 1966 0 (3-4): 0 144--157, 1966

    1966

  4. [12]

    First-order regret bounds for combinatorial semi-bandits

    Gergely Neu. First-order regret bounds for combinatorial semi-bandits. In Conference on Learning Theory, pages 1360--1375. PMLR, 2015

    2015

  5. [13]

    Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits

    Gergely Neu and G \'a bor Bart \'o k. Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits. Journal of Machine Learning Research, 17 0 (154): 0 1--21, 2016

    2016

  6. [14]

    Online joint bid/daily budget optimization of internet advertising campaigns

    Alessandro Nuara, Francesco Trov \`o , Nicola Gatti, and Marcello Restelli. Online joint bid/daily budget optimization of internet advertising campaigns. Artificial Intelligence, 305: 0 103663, 2022

    2022

  7. [15]

    Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits

    Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits. In International Conference on Artificial Intelligence and Statistics, pages 8117--8144. PMLR, 2023

    2023

  8. [16]

    Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning

    Umair ul Hassan and Edward Curry. Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning. Expert Systems with Applications, 58: 0 36--56, 2016

    2016

  9. [17]

    Thompson sampling for combinatorial semi-bandits

    Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pages 5114--5122. PMLR, 2018

    2018

  10. [18]

    Efficient ordered combinatorial semi-bandits for whole-page recommendation

    Yingfei Wang, Hua Ouyang, Chu Wang, Jianhui Chen, Tsvetan Asamov, and Yi Chang. Efficient ordered combinatorial semi-bandits for whole-page recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017

    2017

  11. [19]

    More adaptive algorithms for adversarial bandits

    Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263--1291. PMLR, 2018

    2018

  12. [20]

    Follow-the-perturbed-leader approaches best-of-both-worlds for the m-set semi-bandit problems

    Jingxin Zhan, Yuchen Xin, and Zhihua Zhang. Follow-the-perturbed-leader approaches best-of-both-worlds for the m-set semi-bandit problems. arXiv preprint arXiv:2504.07307v2, 2025

    2025 arXiv

  13. [21]

    Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits

    Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22 0 (28): 0 1--49, 2021

    2021

  14. [22]

    Beating stochastic and adversarial semi-bandits optimally and simultaneously

    Julian Zimmert, Haipeng Luo, and Chen-Yu Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In International Conference on Machine Learning, pages 7683--7692. PMLR, 2019

    2019

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.