Research map / Bandits and online learning / Online convex optimization and games
Online Weighted Paging with Unknown Weights
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.
Gives the first online weighted paging algorithm that learns unknown page weights from stochastic cost samples, achieving O(log k)-competitive ratio plus Õ(√(nT)) regret, via an optimistic fractional solver (LCB) and a pessimistic randomized rounding scheme (UCB).
Problem
Online weighted paging where each page's fetching/eviction cost is unknown in advance and only observed through random samples whose mean is the weight.
Approach
A fractional solver uses optimistic lower confidence bounds on page weights to allocate evictions via multiplicative updates, while the randomized rounding scheme uses pessimistic upper confidence bounds and a sampling interface that feeds integral samples to the fractional solver when its eviction mass hits integers.
Key results
- Algorithm achieves E[ON(Q)] ≤ O(log k)·OPT(Q) + Õ(√(nT)) for online weighted paging with unknown weights, matching the optimal O(log k) competitive ratio of known-weight paging up to an additive regret term.
- Lower bounds show both the O(log k) competitive term (paging) and the Ω̃(√(nT)) regret term (MAB) are asymptotically tight since OWP-UW generalizes both.
- The fractional algorithm's cost bound holds with the rounding overhead of 62·ONF + 50n in expectation, and the bad-event probability is at most 1/(nT).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed randomized algorithm with sampled page weights | Online weighted paging with unknown weights · OWP-UW | competitive ratio: O(log k) | Helped |
| Use the proposed randomized algorithm with sampled page weights | Online weighted paging with unknown weights · OWP-UW | additive regret: \tilde{O}(\sqrt{n T}) | Helped |
| Use lower confidence bounds in the fractional solver and upper confidence bounds in randomized rounding | ON · OWP-UW | expected cost bound: O(log k) · OPT(Q) + \tilde{O}(\sqrt{n T}) | Helped |
Surprising findings
- OWP-UW does not admit sublinear regret without a competitive-ratio term: an Ω(T/k) linear regret lower bound holds for pure regret comparison.
Limitations
- Regret term Õ(√(nT)) is additive and depends on number of pages n, which can be large.
- Analysis assumes the good confidence event; bad event handled by a crude O(nT) bound.
- Only theoretical; no empirical evaluation reported.
Experimental setup
Metrics: competitive ratio regret
Builds on: Bansal-Buchbinder-Naor O(log k) weighted paging multiplicative weights fractional caching multi-armed bandit UCB/LCB
Closest papers by meaning
- Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective (ICLR 2026 · similarity 0.84)
- Parameterized Complexity of Caching in Networks (AAAI 2025 · similarity 0.83)
- Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank (NeurIPS 2026 · similarity 0.82)
- A Dynamic Algorithm for Weighted Submodular Cover Problem (ICML 2024 · similarity 0.82)
- Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency (NeurIPS 2025 · similarity 0.82)
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.82)
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.