Research map / Bandits and online learning / Online convex optimization and games
Online Learning with Bounded Recall
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.
Studies online learning where the learner's output depends only on the last M rewards, showing naive mean-based restarts incur constant regret, proposing AverageRestart achieving O(sqrt(log d / M)) regret, and proving symmetric bounded-recall learners must have constant regret.
Problem
Full-information online learning under a bounded-recall constraint, where the learner's action at round t may depend only on the previous M rewards; the question is what regret is achievable.
Approach
Constructs a stationary bounded-recall learner, AverageRestart, that averages over Hedge runs started at every offset within the last M rounds, achieving optimal Theta(sqrt(log d / M)) per-round regret, while showing mean-based restarts fail (constant regret) and symmetric bounded-recall learners cannot be low-regret.
Key results
- AverageRestart achieves per-round regret at most R(M,d), giving O(sqrt(log d / M)) with Hedge, matching the Omega(sqrt(log d / M)) lower bound.
- Any M-mean-based bounded-recall algorithm incurs per-round regret at least 1/18 - o(1) on a constructed two-action instance.
- Any stationary symmetric bounded-recall algorithm incurs Omega(1) per-round regret on some instance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use average restart over the last M rewards instead of a naive mean-based learner on that window | Stationary M-bounded-recall online learning · Online learning, arbitrary instance | per-round regret: O(\sqrt{(\log d)/M}) vs. 1/18 - o(1) | Helped |
| Run a no-regret algorithm on only the previous M rewards using a mean-based update | M-bounded-recall learning · Online learning, two actions, constructed instance | per-round regret: at least 1/18 - o(1) | Hurt |
| Use periodic restarts with window M rather than unrestricted full-horizon learning | Online learning · Online learning, arbitrary instance | per-round regret: O(\sqrt{(\log d)/M}) | Helped |
| Require the stationary M-bounded-recall learner to be symmetric in its history | Stationary M-bounded-recall learning · Online learning, two actions, constructed instance | per-round regret: \Omega(1) | Hurt |
| Use bounded-recall algorithms rather than classic full-horizon algorithms | Multiplicative Weights-based learners · Periodic drifting rewards | cumulative regret | Helped |
| Use a bounded-recall no-regret algorithm rather than full-horizon Multiplicative Weights | Multiplicative Weights-based learners · Adversarial constructed rewards | cumulative regret | Helped |
Surprising findings
- Natural mean-based restarts over a sliding window (e.g., Hedge over last M rounds) incur constant regret per round despite Hedge being low-regret in the full-horizon setting.
- Any low-regret bounded-recall algorithm must be sensitive to the ordering of the past M losses; symmetric functions of the window cannot achieve low regret.
Limitations
- Stationary bounded-recall algorithms such as AverageRestart are more computationally demanding than standard no-regret algorithms.
- Results are for the experts (simplex) setting; extension to bandit or other full-information settings is not established.
- Simulations are limited to synthetic environments with T=1000 and ten runs.
Experimental setup
Metrics: per-round regret cumulative regret
Baselines: Hedge Multiplicative Weights Follow the Perturbed Leader PeriodicRestart M-mean-based bounded-recall learner
Builds on: Hedge multiplicative weights mean-based learning
Closest papers by meaning
- Online Learning in Unknown Markov Games (ICML 2021 · similarity 0.90)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
- Minimizing Regret on Reflexive Banach Spaces and Nash Equilibria in Continuous Zero-Sum Games (NeurIPS 2016 · similarity 0.88)
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.88)
- Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.86)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 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.