Pith. sign in

REVIEW 1 major objections 6 minor 51 references

Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors

T0 review · 1 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 With only one heuristic queried per step, an MTS algorithm can match the best predictor up to an $O(\mathrm{OPT}^{2/3})$ regret term, and the rate is tight.

desk verdict A genuinely new model with a tight regret bound that should go to review; the reader's main worry about Lemma 3.8 does not land, but there is a real, fixable gap in the stated HEDGE bound. read the letter →

arxiv 2506.05479 v1 pith:BPTQKAHX submitted 2025-06-05 cs.LG cs.DS

Matei Gabriel Coşa , Marek Eliáš This is my paper
classification cs.LGcs.DS MSC 68W2768W40
keywords metricaltasksystemslearning-augmentedalgorithmscombiningheuristicsbanditfeedbackregretboundsonlineexpertadviceswitchingcosts
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

The paper studies how to combine $\ell$ heuristics for Metrical Task Systems (MTS) when the algorithm may query only one heuristic per time step and must query a heuristic for $m-1$ consecutive prior steps before its state is revealed, so heuristic costs cannot be observed directly. Its central claim is an algorithm whose expected cost on any input is at most the best heuristic's cost plus $O((D\ell\ln\ell)^{1/3}m^{2/3}\mathrm{OPT}_{\le 0}^{2/3})$, which makes the competitive ratio against the best heuristic converge to 1. The same approach is extended to a hindsight benchmark that switches among heuristics at most $k$ times, with regret $\tilde O(k^{1/3}\mathrm{OPT}_{\le k}^{2/3})$, and a matching lower bound shows the $\mathrm{OPT}^{2/3}$ exponent is unavoidable even with zero bootstrap delay. This matters because deploying many expensive prediction models at every time step may be unnecessary: one query per step plus a short delay preserves near-best-heuristic performance.

What carries the argument

The algorithm maintains a distribution $x_t$ over the $\ell$ heuristics, updated by the full-feedback expert algorithms HEDGE (for the static benchmark) or SHARE (for the switching benchmark). At exploitation steps it follows a heuristic sampled from $x_t$; at exploration steps it spends $m$ time steps bootstrapping a uniformly random heuristic, observes that heuristic's cost, rescales it into a loss vector $g_t$, and feeds it to the expert algorithm. The analysis turns on a stability property, $\|x_{t-1}-x_t\|_1 \le \eta\, g_{t-1}^T x_{t-1}$, together with a rounding procedure that converts distributions over heuristics into actual MTS states whose expected switching cost is controlled by the earth-mover distance. Lemma 3.8 uses these ingredients to compare the real costs $f_t^T x_t$ with the perceived costs $g_t^T x_t$, paying an overhead of order $m\epsilon/(1-\epsilon)^m$; the crucial inequality in that lemma is display (4), which charges near-exploration steps back to earlier exploitation steps.

What would settle it

Work out the smallest non-trivial case of inequality (4), $m=i=2$, with an explicit distribution over the $\beta_t$ coin flips and a nonnegative cost vector $f_t$, and compare the left-hand side $\sum_t \mathbb{E}[f_t^T x_{t-2} E_{t-2}]$ with the right-hand side the proof obtains by factoring out $\mathbb{E}[\beta_{t-i-m}]$ while also keeping that $\beta$ inside the product; a single numerical mismatch would show the proof as printed does not establish the bound, while a corrected derivation that restores the inequality would settle the worry.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1.1, is that $m$-delayed bandit access does not prevent an MTS algorithm from tracking the best of $\ell$ heuristics almost perfectly. With constant $D$, $\ell$, and $m$, the expected cost is $\mathrm{OPT}_{\le 0} + O((D\ell\ln\ell)^{1/3}m^{2/3}\mathrm{OPT}_{\le 0}^{2/3})$, so the competitive ratio is $1+o(1)$ when the best heuristic's cost grows relative to the fixed parameters. The paper also proves Theorem 1.2 for the benchmark that may switch heuristics at most $k$ times, with regret $\tilde O(k^{1/3}\mathrm{OPT}_{\le k}^{2/3})$, and Theorem 1.3, a lower bound of $\tilde\Omega(\mathrm{OPT}_{\le 0}^{2/3})$ that holds even with $m=2$, so the upper bound is tight up to logarithmic factors.

Load-bearing premise

The load-bearing premise is that inequality (4) in Section 3.3 is valid as printed, because that inequality is what lets the proof charge near-exploration costs back to earlier exploitation steps; the printed derivation appears to count the same random coin flip $\beta_{t-i-m}$ twice, so if the inequality fails the $O(\mathrm{OPT}^{2/3})$ regret bound is not formally established.

Editorial extensions

If this is right

  • If the main theorem is correct, a portfolio of $\ell$ prediction models for any MTS can be queried one at a time and still match the best model asymptotically, so heavy models need not all run at every step.
  • Including a classical worst-case $\rho$-competitive MTS algorithm among the heuristics yields a robustified algorithm that is $(1+o(1))\rho$-competitive on adversarial inputs and near-best-heuristic on inputs where a predictor excels.
  • The same machinery gives a regret bound of $O((m\ell\ln\ell)^{1/3}T^{2/3})$ for bandit learning against $m$-memory-bounded adversaries, matching the known $T^{2/3}$ rate for that setting with slightly better dependence on $m$.
  • The lower bound shows that no algorithm in this model can have regret $o(\mathrm{OPT}_{\le 0}^{2/3})$ in the worst case, so the exponent in the upper bound is inherent.
  • If the best heuristic is within a $1+\epsilon$ factor of the offline optimum, the algorithm's expected cost is within $(1+o(1))(1+\epsilon)$ of that optimum.

Reading between the lines

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

  • An editorial worry, not a settled flaw: the printed derivation of inequality (4) appears to use the random variable $\beta_{t-i-m}$ twice in the same expectation, once factored out and once inside a product; if that is a real indexing error, the overhead term $m\epsilon/(1-\epsilon)^m$ would need a corrected charging argument, and the $O(\mathrm{OPT}^{2/3})$ rate might still survive with a modifie
  • The algorithm assumes full online access to the cost functions, so the result does not directly transfer to settings where only the chosen action's cost is revealed; a natural extension is bandit-cost MTS with predictors.
  • The exploration schedule could plausibly be combined with variable bootstrap delays or multiple simultaneous queries, connecting this model to costly state acquisition and sparse predictions.
  • Replacing HEDGE and SHARE with other stable online learners would test whether the stability property alone, rather than the specific exponential weights, is what drives the regret rate.
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

1 major / 6 minor

Summary. The paper introduces a bandit-feedback model for combining heuristics in Metrical Task Systems (MTS): at each time step the algorithm may query one heuristic, and a query returns the heuristic's current state only if the same heuristic was queried in the previous m−1 steps (m-delayed access). The main upper bound (Theorems 1.1 and 3.9) is an algorithm whose expected cost is OPT≤0 + O((Dℓ lnℓ)^{1/3} m^{2/3} OPT_{≤0}^{2/3}) against the best static heuristic, with a matching lower bound (Theorem 1.3) based on the switching-cost construction of Dekel et al. (2013). The algorithm combines an explore/exploit schedule with an internal HEDGE/SHARE expert algorithm on renormalized perceived costs, and uses improper greedy steps during bootstrap periods. Extensions cover k-switching benchmarks (Theorem 1.2) and the memory-bounded bandit setting of Arora et al. (2012).

Significance. If the proof gaps are repaired, this is a solid contribution to learning-augmented online algorithms. The model is natural, the algorithm is conceptually clean, and the lower bound is a convincing reduction that addresses the extra power (lookahead, full input access) of the MTS setting. The paper also includes self-contained proofs of the rounding propositions and a doubling procedure for the unknown OPT≤0. However, the central upper-bound proof as printed relies on a false HEDGE guarantee, so the main theorem is not formally established in the current version.

major comments (1)
  1. [Section 2, Proposition 2.4] Proposition 2.4 is false as written. The standard HEDGE potential analysis for losses in [0,1] yields (1−e^{−η}) Σ_t g_t^T x_t ≤ η Σ_t g_t^T x* + ln ℓ, i.e., the first term on the right must be divided by (1−e^{−η}). For a concrete failure, take ℓ=2, η=0.1, and losses alternating between (1,0) and (0,1) for T steps; then Σ_t g_t^T x_t ≈ T/2 + O(1) while the stated bound gives at most 0.1·(T/2) + O(1). Since this proposition is invoked in the proofs of Theorem 3.9 and Theorem 6.3, the printed upper-bound proofs are not formally valid. The corrected inequality still suffices for the stated rates: for the small γ chosen in Theorem 3.9, η/(1−e^{−η}) = 1 + O(γ), so the extra factor is absorbed in the O(γ OPT) term; nevertheless, the statement and its applications must be revised.
minor comments (6)
  1. [Section 3.3, Lemma 3.8, Eq. (4)] The displayed chain in Eq. (4) is correct: the apparent duplication of β_{t−i−m} is resolved because E[β] and E[∏(1−β)] are factored by independence, and Observation 3.3 gives X_{t−m} ≥ ∏(1−β) X_{t−i−m}; I verified that the indexing is consistent and no factor is duplicated.
  2. [Theorem 5.3] The displayed regret bound in Theorem 5.3 is malformed (it mixes OPT_{≤k}^{2/3} and a fraction OPT_{≤k}^{2/3}/((Dk)^{2/3} m^{4/3}) inside a single O(·) expression). The proof actually establishes a bound of order O((Dℓk)^{1/3} m^{2/3} OPT_{≤k}^{2/3} · (ln Z)^{O(1)}), with Z as in Corollary 5.4; please restate the theorem to match the derivation.
  3. [Section 1.1 and Section 4] The phrase '0 bootstrapping time (m=2)' is a misnomer: in the model, m=2 is the minimal positive delay required to observe a heuristic's cost. Please rephrase to something like 'the smallest possible delay m=2'.
  4. [Theorem 3.9] The condition 'Dℓm ≤ o(OPT_{≤0}^{1/3})' is not used in the proof and is confusing; the proof actually shows E[ALG] ≤ OPT_{≤0} + O(m) + O((Dℓ lnℓ)^{1/3} m^{2/3} OPT_{≤0}^{2/3}), so the bound is meaningful for all OPT. Consider stating the additive O(m) term explicitly and removing the unneeded condition.
  5. [Proof of Theorem 3.9] The proof cites 'Lemma 5.2' before that lemma is stated (it appears in Section 5). Moving Lemma 5.2 to Section 3 or adding a forward reference would improve readability.
  6. [Appendix D] There is a typo 'algortihm' in the first paragraph of Appendix D; it should read 'algorithm'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper and lower bounds rest on external, independently checkable results and on in-paper proofs, not on self-referential reductions.

full rationale

I examined the derivation chain in Sections 3-6 and the appendices. The upper bound uses three external building blocks: the HEDGE/SHARE regret guarantees from Freund-Schapire and Cesa-Bianchi-Lugosi, the stability property from Blum and Burch, and the lower-bound construction of Dekel et al.; none of these are derived from the paper's own claims, and the paper includes its own proofs of the supporting propositions it labels as standard. Lemma 3.8 relates perceived costs to real costs using the definition of the observed loss vector g_t and the exploration indicators, but the relation is not an identity: the factor epsilon/(2D ell), the conditioning on the filtration, and the stability argument are substantive and independently checkable. No parameter is fitted to data and then reported as a prediction; epsilon and gamma are chosen analytically as functions of OPT. The attribution of Proposition A.1 to Antoniadis et al. (2023a) is not load-bearing self-citation because a complete proof is reproduced in Appendix A. I also checked the flagged indexing in inequality (4): the apparent duplication of beta_{t-i-m} is a notational artifact of writing a product of expectations via independence, and the stated bound follows from Observations 3.2 and 3.3 together with independence of X_{t-i-m} from the later beta's. The HEDGE constant issue in Proposition 2.4 is a correctness concern, not a circularity concern, and the proof of Theorem 3.9 would not reduce to its own input even if that constant required correction. The lower bound in Section 4 imports Dekel et al. as an external black box and reduces the MTS instance to it without assuming the target result, so no renaming or definitional equivalence is present. Overall the derivation is self-contained against external benchmarks and no circular step is exhibited.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The paper's guarantees rest on standard expert-learning bounds (HEDGE, SHARE), a black-box lower bound (Dekel et al.), and the oblivious adversary model. No ad hoc entities are introduced. The main tuning parameters epsilon and gamma are analytic optima rather than data-fitted values.

free parameters (3)
  • exploration probability epsilon = (D*ell*ln(ell))^{1/3} m^{-4/3} OPT_{<=0}^{-1/3}
    Chosen by hand to balance exploration overhead against HEDGE regret; the algorithm requires an estimate of OPT_{<=0} (Appendix D provides a doubling routine).
  • HEDGE learning-rate parameter gamma = (D*ell*ln(ell))^{1/3} m^{2/3} OPT_{<=0}^{-1/3}
    Chosen to minimize the final regret expression in Theorem 3.9.
  • SHARE parameters alpha and gamma (k-switch bound) = alpha=(D*ell*k)/(epsilon*OPT_{<=k}), gamma=sqrt(D*ell*k/(epsilon*OPT_{<=k}))
    Chosen in the proof of Theorem 5.3 to balance the SHARE regret bound against the switching penalty.
assumptions (6)
  • standard math HEDGE regret bound (Cesa-Bianchi and Lugosi, Proposition 2.4)
    Used in Theorem 3.9 to bound the cumulative perceived loss; proof referenced.
  • standard math SHARE regret bound (Cesa-Bianchi and Lugosi, Proposition 5.1)
    Used in Theorem 5.3 for the k-switch benchmark.
  • standard math Dekel et al. lower bound for Bandits with Switching Costs (Proposition 4.1)
    Black-box used to construct the MTS lower bound instance.
  • domain assumption Oblivious adversary model
    All guarantees are expected pseudoregret against an adversary fixing input and heuristic solutions before the algorithm's random bits (Section 2).
  • domain assumption Heuristic costs normalized to [0,2D] without loss of generality
    Section 2 argues subtracting the minimum state cost and post-processing predictors makes per-step heuristic cost lie in [0,2D].
  • standard math Existence of a fractional-to-randomized rounding with expected cost bounded by EMD (Propositions 2.1 and 2.2)
    Used to convert distribution updates into actual MTS states with bounded movement cost; proof in Appendix B.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors." pith.science (2026). https://pith.science/paper/BPTQKAHX

@misc{pith2026250605479,
  author       = {Pith},
  title        = {Pith review of: Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BPTQKAHX}},
  note         = {Machine review of arXiv:2506.05479}
}
abstract

We consider the following problem: We are given $\ell$ heuristics for Metrical Task Systems (MTS), where each might be tailored to a different type of input instances. While processing an input instance received online, we are allowed to query the action of only one of the heuristics at each time step. Our goal is to achieve performance comparable to the best of the given heuristics. The main difficulty of our setting comes from the fact that the cost paid by a heuristic at time $t$ cannot be estimated unless the same heuristic was also queried at time $t-1$. This is related to Bandit Learning against memory bounded adversaries (Arora et al., 2012). We show how to achieve regret of $O(\text{OPT}^{2/3})$ and prove a tight lower bound based on the construction of Dekel et al. (2013).

Figures

Figures reproduced from arXiv: 2506.05479 by the authors.

Figure 1
Figure 1. With ℓ = 2, M is the metric closure of this graph. 4 Tight Lower Bound: Proof of Theorem 1.3 In this section, we prove a lower bound matching Theorem 3.9. Our proof is based on the construction of Dekel et al. (2013) for Bandits with Switching Costs, which is a special case of Bandit Learning against a 1-Memory Bounded Adversary. In order to use their construction in our setting, we need to address additional challe… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 42 canonical work pages

  1. [1]

    Online facility location with multiple advice

    Almanza, M., Chierichetti, F., Lattanzi, S., Panconesi, A., and Re, G. Online facility location with multiple advice. In NeurIPS , pp.\ 4661--4673, 2021

    work page 2021

  2. [2]

    Better best of both worlds bounds for bandits with switching costs

    Amir, I., Azov, G., Koren, T., and Livni, R. Better best of both worlds bounds for bandits with switching costs. In Advances in Neural Information Processing Systems, volume 35, pp.\ 15800--15810, 2022

    work page 2022

  3. [3]

    Online algorithms with multiple predictions

    Anand, K., Ge, R., Kumar, A., and Panigrahi, D. Online algorithms with multiple predictions. In ICML , volume 162 of Proceedings of Machine Learning Research, pp.\ 582--598. PMLR , 2022

    work page 2022

  4. [4]

    Learning-augmented dynamic power management with multiple states via new ski rental bounds

    Antoniadis, A., Coester, C., Eli \' a s, M., Polak, A., and Simon, B. Learning-augmented dynamic power management with multiple states via new ski rental bounds. In NeurIPS , 2021

    work page 2021

  5. [5]

    Mixing predictions for online metric algorithms

    Antoniadis, A., Coester, C., Eli \' a s, M., Polak, A., and Simon, B. Mixing predictions for online metric algorithms. CoRR, abs/2304.01781, 2023 a . doi:10.48550/arXiv.2304.01781. URL https://doi.org/10.48550/arXiv.2304.01781

    work page Pith review arXiv doi:10.48550/arxiv.2304.01781 2023

  6. [6]

    Learning-augmented dynamic power management with multiple states via new ski rental bounds

    Antoniadis, A., Coester, C., Eli\' a s , M., Polak, A., and Simon, B. Learning-augmented dynamic power management with multiple states via new ski rental bounds. ACM Trans. Algorithms, 19 0 (2), apr 2023 b . ISSN 1549-6325. doi:10.1145/3582689. URL https://doi.org/10.1145/3582689

    doi:10.1145/3582689 2023

  7. [7]

    Online bandit learning against an adaptive adversary: from regret to policy regret

    Arora, R., Dekel, O., and Tewari, A. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML'12, pp.\ 1747–1754, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851

    work page 2012

  8. [8]

    Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32 0 (1): 0 48--77, 2002. doi:10.1137/S0097539701398375. URL https://doi.org/10.1137/S0097539701398375

    doi:10.1137/s0097539701398375 2002

Show all 51 references
  1. [9]

    Z., and Manasse, M

    Azar, Y., Broder, A. Z., and Manasse, M. S. On-line choice of on-line algorithms. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '93, pp.\ 432–440, USA, 1993. Society for Industrial and Applied Mathematics. ISBN 0898713137

    1993

  2. [10]

    Energy-efficient scheduling with predictions

    Balkanski, E., Perivier, N., Stein, C., and Wei, H.-T. Energy-efficient scheduling with predictions. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc

    2023

  3. [11]

    Learning augmented energy minimization via speed scaling

    Bamas, \' E ., Maggiori, A., Rohwedder, L., and Svensson, O. Learning augmented energy minimization via speed scaling. In NeurIPS , 2020

    2020

  4. [12]

    Ramsey-type theorems for metric spaces with applications to online problems

    Bartal, Y., Bollobás, B., and Mendel, M. Ramsey-type theorems for metric spaces with applications to online problems. Journal of Computer and System Sciences, 72 0 (5): 0 890–921, August 2006. ISSN 0022-0000. doi:10.1016/j.jcss.2005.05.008. URL http://dx.doi.org/10.1016/j.jcss...

    2006 doi

  5. [13]

    and Perchet, V

    Benomar, Z. and Perchet, V. Non-clairvoyant scheduling with partial predictions. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp.\ 3506--3538, 21--27 Jul 2024 a

    2024

  6. [14]

    and Perchet, V

    Benomar, Z. and Perchet, V. Non-clairvoyant scheduling with partial predictions. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of P...

    2024

  7. [15]

    A universal error measure for input predictions applied to online graph problems

    Bernardini, G., Lindermayr, A., Marchetti - Spaccamela, A., Megow, N., Stougie, L., and Sweering, M. A universal error measure for input predictions applied to online graph problems. CoRR, abs/2205.12850, 2022. doi:10.48550/arXiv.2205.12850. URL https://doi.org/10.48550/arXiv....

    2022 doi arXiv

  8. [16]

    Online linear optimization with many hints

    Bhaskara, A., Cutkosky, A., Kumar, R., and Purohit, M. Online linear optimization with many hints. In NeurIPS , 2020

    2020

  9. [17]

    and Burch, C

    Blum, A. and Burch, C. On-line learning and the metrical task system problem. Mach. Learn., 39 0 (1): 0 35--58, 2000. doi:10.1023/A:1007621832648

    2000 doi

  10. [18]

    and Mansour, Y

    Blum, A. and Mansour, Y. Learning, Regret Minimization, and Equilibria, pp.\ 79–102. Cambridge University Press, 2007

    2007

  11. [19]

    Borodin, A., Linial, N., and Saks, M. E. An optimal on-line algorithm for metrical task system. J. ACM , 39 0 (4): 0 745--763, 1992. doi:10.1145/146585.146588

    1992

  12. [20]

    B., Lee, J

    Bubeck, S., Cohen, M. B., Lee, J. R., and Lee, Y. T. Metrical task systems on trees via mirror descent and unfair gluing. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , pp.\ 89--97, 2019. doi:10.1137/1.9781611975482.6. URL https:/...

    2019 doi

  13. [21]

    The randomized k-server conjecture is false! CoRR, abs/2211.05753, 2022 a

    Bubeck, S., Coester, C., and Rabani, Y. The randomized k-server conjecture is false! CoRR, abs/2211.05753, 2022 a . doi:10.48550/arXiv.2211.05753

    2022 doi arXiv

  14. [22]

    Shortest paths without a map, but with an entropic regularizer

    Bubeck, S., Coester, C., and Rabani, Y. Shortest paths without a map, but with an entropic regularizer. In FOCS , pp.\ 1102--1113. IEEE , 2022 b

    2022

  15. [23]

    and Lugosi, G

    Cesa - Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge University Press, 2006. ISBN 978-0-521-84108-5. doi:10.1017/CBO9780511546921. URL https://doi.org/10.1017/CBO9780511546921

    2006 doi

  16. [24]

    Online learning with switching costs and other adaptive adversaries

    Cesa-Bianchi, N., Dekel, O., and Shamir, O. Online learning with switching costs and other adaptive adversaries. ArXiv, abs/1302.4387, 2013

    2013 arXiv

  17. [25]

    Predictive flows for faster ford-fulkerson

    Davies, S., Moseley, B., Vassilvitskii, S., and Wang, Y. Predictive flows for faster ford-fulkerson. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp.\ 7231--7248. PMLR, 23--29 Jul 2023

    2023

  18. [26]

    Bandits with switching costs: T2/3 regret

    Dekel, O., Ding, J., Koren, T., and Peres, Y. Bandits with switching costs: T2/3 regret. Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2013. URL https://api.semanticscholar.org/CorpusID:9425790

    2013

  19. [27]

    Algorithms with prediction portfolios

    Dinitz, M., Im, S., Lavastida, T., Moseley, B., and Vassilvitskii, S. Algorithms with prediction portfolios. In NeurIPS , 2022

    2022

  20. [28]

    Learning-Augmented Streaming Algorithms for Approximating MAX-CUT

    Dong, Y., Peng, P., and Vakilian, A. Learning-Augmented Streaming Algorithms for Approximating MAX-CUT . In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325, pp.\ 44:1--44:24, Dagstuhl, Germany, 2025. Schloss Dagstuhl -- Leibniz-Zentrum f \"u...

    2025 doi

  21. [29]

    G., and Svensson, O

    Drygala, M., Nagarajan, S. G., and Svensson, O. Online algorithms with costly predictions. In Ruiz, F., Dy, J., and van de Meent, J.-W. (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Lear...

    2023

  22. [30]

    o lke, L., and Schl \

    Eberle, F., Lindermayr, A., Megow, N., N \" o lke, L., and Schl \" o ter, J. Robustification of online graph exploration methods. In AAAI , pp.\ 9732--9740. AAAI Press, 2022

    2022

  23. [31]

    Online paging with a vanishing regret

    Emek, Y., Kutten, S., and Shi, Y. Online paging with a vanishing regret. In ITCS , 2021

    2021

  24. [32]

    Competitive k-server algorithms (extended abstract)

    Fiat, A., Rabani, Y., and Ravid, Y. Competitive k-server algorithms (extended abstract). In FOCS , 1990

    1990

  25. [33]

    M., Luby, M., McGeoch, L

    Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., and Young, N. E. Competitive paging algorithms. Journal of Algorithms, 12 0 (4): 0 685--699, 1991. ISSN 0196-6774. doi:https://doi.org/10.1016/0196-6774(91)90041-V. URL https://www.sciencedirect.com/science/artic...

    1991

  26. [34]

    and Schapire, R

    Freund, Y. and Schapire, R. E. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55 0 (1): 0 119--139, 1997. ISSN 0022-0000. doi:https://doi.org/10.1006/jcss.1997.1504. URL https://www.sciencedirect...

    1997

  27. [35]

    and Panigrahi, D

    Gollapudi, S. and Panigrahi, D. Online algorithms for rent-or-buy with expert advice. In ICML , volume 97 of Proceedings of Machine Learning Research, pp.\ 2319--2327. PMLR , 2019

    2019

  28. [36]

    and Warmuth, M

    Herbster, M. and Warmuth, M. K. Tracking the best expert. Machine learning, 32 0 (2): 0 151--178, 1998

    1998

  29. [37]

    Parsimonious learning-augmented caching

    Im, S., Kumar, R., Petety, A., and Purohit, M. Parsimonious learning-augmented caching. In ICML , 2022

    2022

  30. [38]

    and Nguyen, K.-T

    Kevi, E. and Nguyen, K.-T. Online covering with multiple experts, 2023. URL https://arxiv.org/abs/2312.14564

    2023 arXiv

  31. [39]

    Randomized online computation with high probability guarantees

    Komm, D., Kr\' a lovi c , R., Kr\' a lovi c , R., and M\" o mke, T. Randomized online computation with high probability guarantees. Algorithmica, 84 0 (5): 0 1357–1384, May 2022. ISSN 0178-4617. doi:10.1007/s00453-022-00925-z

    2022 doi

  32. [40]

    H., Dean, J., and Polyzotis, N

    Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. The case for learned index structures. In Proceedings of SIGMOD '18 , pp.\ 489--504, 2018. doi:10.1145/3183713.3196909

    2018

  33. [41]

    and Szepesvari, C

    Lattimore, T. and Szepesvari, C. Bandit algorithms. 2017. URL https://tor-lattimore.com/downloads/book/book.pdf

    2017

  34. [42]

    and Megow, N

    Lindermayr, A. and Megow, N. Permutation predictions for non-clairvoyant scheduling. In SPAA , pp.\ 357--368. ACM , 2022

    2022

  35. [43]

    and Megow, N

    Lindermayr, A. and Megow, N. Algorithms with predictions. https://algorithms-with-predictions.github.io, 2023. URL https://algorithms-with-predictions.github.io. Online: accessed 2023-07-12

    2023

  36. [44]

    and Vassilvitskii, S

    Lykouris, T. and Vassilvitskii, S. Competitive caching with machine learned advice. J. ACM , 68 0 (4): 0 24:1--24:25, 2021

    2021

  37. [45]

    and Vassilvitskii, S

    Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Commun. ACM , 65 0 (7): 0 33--35, 2022. doi:10.1145/3528087. URL https://doi.org/10.1145/3528087

    2022 doi

  38. [46]

    Near-optimal bounds for online caching with machine learned advice

    Rohatgi, D. Near-optimal bounds for online caching with machine learned advice. In SODA , 2020

    2020

  39. [47]

    An algorithm for stochastic and adversarial bandits with switching costs

    Rouyer, C., Seldin, Y., and Cesa-Bianchi, N. An algorithm for stochastic and adversarial bandits with switching costs. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Researc...

    2021

  40. [48]

    Sadek, K. A. A. and Eli\'a s , M. Algorithms for caching and MTS with reduced number of predictions. In The Twelfth International Conference on Learning Representations, 2024

    2024

  41. [49]

    Introduction to multi-armed bandits

    Slivkins, A. Introduction to multi-armed bandits. CoRR, abs/1904.07272, 2019. URL http://arxiv.org/abs/1904.07272

    1904 arXiv

  42. [50]

    Online algorithms for multi-shop ski rental with machine learned advice

    Wang, S., Li, J., and Wang, S. Online algorithms for multi-shop ski rental with machine learned advice. In NeurIPS , 2020

    2020

  43. [51]

    Better and simpler learning-augmented online caching

    Wei, A. Better and simpler learning-augmented online caching. In APPROX/RANDOM , 2020

    2020

Pith tools

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