Research map / Bandits and online learning / Online convex optimization and games
Online Learning in the Random-Order Model
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.
Shows that stochastic online learners can fail under random-order inputs, proposes the SIMULATION template that adapts i.i.d. algorithms to random order, and applies it to delayed feedback, constrained online learning, and bandits with switching costs, plus a VC-dimension characterization for random-order classification.
Problem
Online learning when the adversary fixes the loss sequence but it is presented in uniformly random order; stochastic algorithms can fail due to finite-time non-stationarity, while adversarial algorithms are too pessimistic.
Approach
A general template (SIMULATION) that partitions time into geometrically growing blocks, simulates an i.i.d. distribution from past data, trains a stochastic algorithm on that simulated past, and plays the resulting action frequencies on the next block; sampling without replacement concentrates around the same means, so regret matches the i.i.d. rate.
Key results
- Birthday-Test achieves O(sqrt(T log T)) regret on i.i.d. inputs but suffers Omega(T) regret on a random-order instance.
- SIMULATION for delayed feedback achieves O(sqrt(T log T) + d log T) regret in the random-order model.
- Bandits with switching costs in random order achieve O(sqrt(k T log^3 T)) regret; for classification, ERM in random order has regret at most 8 sqrt(VC T log(T/VC)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Birthday-Test rather than a stochastic no-regret routine alone | Prediction with Experts · stochastic i.i.d. | regret: O(\sqrt{T\log T}) | Helped |
| Use Birthday-Test on a random-order instance with distinct action-1 losses | Prediction with Experts · random order | regret: \Omega(T) | Hurt |
| Apply Simulation with Follow-The-Leader | Prediction with delayed feedback · random order | regret: O(\sqrt{T \log T} + d \log T) | Helped |
| Apply Simulation with a stochastic constrained-learning routine | Online learning with long-term constraints · random order | regret: \widetilde O(\nicefrac{1}{\rho^2}+\nicefrac{\sqrt{T}}\rho) | Helped |
| Apply Simulation with a stochastic constrained-learning routine | Online learning with long-term constraints · random order | constraint violations: zero | Helped |
| Use Simulation-successive-elimination with geometrically increasing blocks | Bandits with switching costs · random order | regret: O(\sqrt{k T \log^3 T}) | Helped |
| Choose the empirical loss minimizer from past examples | Binary classification · random order | regret: 8\sqrt{\VC T\log\left(\frac{T}{\VC}\right)} | Helped |
| Use stochastic algorithms directly without adapting them for random order | Stochastic learning algorithms · random-order inputs | regret | Mixed |
Surprising findings
- A simple algorithm that is no-regret on i.i.d. inputs (Birthday-Test) fails linearly on random-order inputs.
- In random order, online classification learnability is characterized by VC dimension rather than Littlestone dimension.
Limitations
- Bandit feedback is not handled by a black-box reduction; a simplified SSE-based variant is analyzed.
- Constrained setting adds an extra 1/rho^2 term in regret instead of matching the stochastic bound exactly.
- Results are theoretical with no empirical evaluation.
Experimental setup
Metrics: expected regret
Baselines: Follow-the-Leader Birthday-Test adversarial algorithms (Hedge/EXP3-type)
Builds on: Follow-the-Leader successive elimination Bandits with Knapsacks Hoeffding inequality for sampling without replacement
Closest papers by meaning
- Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning (NeurIPS 2016 · similarity 0.90)
- A Theory of Adversary-Directed Online Learning (NeurIPS 2026 · similarity 0.90)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.90)
- Online Convex Optimization in the Random Order Model (ICML 2020 · similarity 0.89)
- Replicable Online Learning (NeurIPS 2025 · similarity 0.88)
- Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs (NeurIPS 2024 · similarity 0.87)
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.