Research map / Bandits and online learning / Online convex optimization and games
Replicable Online Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines adversarial and iid replicability for online learning under time-varying input distributions and gives replicable low-regret algorithms for online linear optimization and experts, a general conversion framework, and regret lower bounds.
Problem
Designing online learning algorithms that produce the exact same action sequence with high probability on two independent input sequences drawn from time-varying (possibly adversarial) distributions, while keeping low regret.
Approach
Extends algorithmic replicability to online settings with oblivious time-varying input distributions; uses block updates (changing actions only at block endpoints) combined with randomly offset grid rounding of cumulative costs (from Follow the Lazy Leader) and geometric noise for experts, so two runs with shared randomness pick identical actions with high probability.
Key results
- Adversarially rho-replicable FLLB for online linear optimization achieves regret roughly O~(D T^{5/6} n^{1/6} rho^{-1/3}).
- Adversarially replicable FTPLB* for experts achieves regret O~(T^{5/6} ln^{5/6}(n) rho^{-1/3}).
- An iid rho-replicable experts algorithm achieves worst-case regret O~(sqrt(T) log(n)/rho), matching lower bound Omega(sqrt(T)/rho) up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add block updates and random-grid rounding of cumulative costs | Online linear optimization · Adversarial input distributions | regret: \widetilde{\calO}(D T^{5/6}n^{1/6}\rho^{-1/3}) | Helped |
| Add block updates and geometric noise to expert costs | Experts · Adversarial input distributions | regret: \widetilde{\calO}(T^{5/6}\ln^{5/6}(n)\rho^{-1/3}) | Helped |
| Convert FTPL using block updates and randomized rounding | Online linear optimization · Adversarial input distributions | regret: \widetilde{\calO}(DT^{7/8} n^{3/8} \rho^{-1/4}) | Helped |
| Convert FTPL using block updates and randomized rounding | Experts · Adversarial input distributions | regret: \widetilde{\calO}(T^{7/8} n^{1/8} \rho^{-1/4}) | Helped |
| Use growing block lengths, varying geometric noise, and a regret-triggered switch to FTPL | Experts · IID input distributions | worst-case regret: \calO\left( \frac{1}{\rho} \times (\log\log(T))^2 \times \log\left(\frac{ n\log\log(T)}{\rho}\right) \times \sqrt{T} \ri | Helped |
| Use the standard FTPL algorithm without block updates | Online linear optimization · Adversarial input distributions | replicability | Hurt |
| Use FLL without block updates | Online linear optimization · Adversarial input distributions | replicability | Hurt |
| Use the general conversion framework instead of a setting-specific algorithm | Online linear optimization and experts · Adversarial input distributions | regret: \widetilde{\calO}(DT^{7/8} n^{3/8} \rho^{-1/4}); \widetilde{\calO}(T^{7/8} n^{1/8} \rho^{-1/4}) | Hurt |
Surprising findings
- Standard Follow the Lazy Leader and Follow the Perturbed Leader are not adversarially replicable, even though they achieve low regret.
Limitations
- Gap between upper bound (T^{5/6} or T^{7/8} regret) and lower bound (sqrt(T)) for adversarial replicability in experts and OLO.
- Analysis restricted to full-information setting; bandit feedback left open.
- Replicability parameter rho scaling worsens regret polynomially (rho^{-1/3} or rho^{-1/4}).
Experimental setup
Metrics: regret replicability probability
Baselines: Follow the Perturbed Leader Follow the Lazy Leader
Builds on: Follow the Lazy Leader Follow the Perturbed Leader replicable algorithms (Impagliazzo et al. 2022)
Closest papers by meaning
- Replicable Constrained Bandits (NeurIPS 2026 · similarity 0.89)
- Replicable Reinforcement Learning (NeurIPS 2023 · similarity 0.88)
- On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.88)
- Online Learning in the Random-Order Model (ICML 2025 · similarity 0.88)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.87)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.86)
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.