Research map / Bandits and online learning / Online convex optimization and games
Robustification of Online Graph Exploration Methods
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use modified rather than basic robustification (ablation) | Learning-augmented Follow the Prediction on Stockholm · Stockholm road network | empirical competitive ratio | Helped |
| Use modified robustification with λ=0.5 instead of the basic scheme (ablation) | Learning-augmented Follow the Prediction on Stockholm · Stockholm road network, large prediction errors | empirical competitive ratio | Hurt |
| Use modified robustification with λ=0.75 instead of the basic scheme (ablation) | Learning-augmented Follow the Prediction on Stockholm · Stockholm road network, large prediction errors | empirical competitive ratio | No clear effect |
| Increase λ when robustifying classical exploration algorithms (ablation) | Nearest Neighbor, Hierarchical Depth First Search, and planar graph exploration · TSPLib instances | empirical competitive ratio | Helped |
| Robustify Follow the Prediction with λ=1 (ablation) | Follow the Prediction · Rosenkrantz graphs | exploration cost | Helped |
| Increase robustification strength to λ=20 (ablation) | Follow the Prediction · Rosenkrantz graphs | exploration cost | Mixed |
| Robustify Hierarchical Depth First Search with λ=1 (ablation) | Hierarchical Depth First Search · Rosenkrantz graphs | competitive ratio | No clear effect |
| Robustify Hierarchical Depth First Search with λ=20 (ablation) | Hierarchical Depth First Search · Rosenkrantz graphs | competitive ratio | Hurt |
| Add robustification to Follow the Prediction for relative prediction errors below 2.5 (ablation) | Follow the Prediction · City road networks | empirical competitive ratio | Helped |
| Add robustification to Follow the Prediction for large prediction errors (ablation) | Follow the Prediction · City road networks | empirical competitive ratio | Helped |
| Use modified robustification instead of basic robustification (ablation) | Input online exploration algorithm · General online graph exploration | worst-case cost bound relative to optimum: (1+\frac{1}{2\lambda})(\lceil\log(n)\rceil+1) -> (1+\frac{1}{\lambda})(\lceil\log(n)\rceil+1) | Hurt |
Closest papers by meaning
- Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions (NeurIPS 2022 · similarity 0.86)
- Robust Offline Active Learning on Graphs (NeurIPS 2024 · similarity 0.86)
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms (NeurIPS 2020 · similarity 0.85)
- Robust Graph Condensation via Classification Complexity Mitigation (NeurIPS 2025 · similarity 0.84)
- Efficient Graph Bandit Learning with Side-Observations and Switching Constraints (AAAI 2025 · similarity 0.84)
- Uncertainty for Active Learning on Graphs (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.