Online Paging with a Vanishing Regret
summary
Online paging with cache size K and universe N over T rounds becomes achievable with predictions: a simulation algorithm SIM algorithm replaces true next-arrival times with online predictions and guarantees regret O(eta + K) where eta is the cumulative prediction-error (so if one predictor has sublinear eta the regret/T → 0). Multiple predictors use parallel SIM runs plus Blum and Burch style switching under full information, and a banded access model solution uses chasing with restarts and omitted initial requests to supply stateless feedback, yielding vanishing regret in practice.
AI-written summary · about
chapters (6)
- 0:00Start
- 2:55Machine Leamed Predictions
- 10:56Related Work
- 13:28Algorithm for Single Predictor Case
- 19:36Reduction to Troublemaker Counting Sec. II. Technic
- 26:28Multiple Predictors
related talks
44mParsimonious Learning-Augmented Algorithms
58mMemory-Regret Tradeoff for Online Learning
48mA Simple Condition for Constant Regret in Online Decision-Making
30mConsensus-Based Distributed Online Prediction and Optimization
40mA Bayesian Approach to Online Resource Allocation
01h 17mOnline Reinforcement Learning and Regret
01h 04mCompetitive Analysis of Online Algorithms (Part 2)
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives