Research map / Bandits and online learning / Online convex optimization and games
Barely Random Algorithms and Collective Metrical Task Systems
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 any fully randomized metrical task system algorithm can be converted into one using only 2 log n random bits with a factor-2 loss in competitive ratio, via a discrete (barely fractional) first-order potential-based discretization.
Problem
How many random bits are needed for competitive metrical task systems algorithms on n-point metric spaces; whether randomness must scale with the request sequence length.
Approach
Equivalence between k-barely random algorithms and k-barely fractional strategies (distributions with values in multiples of 1/k) via Birkhoff-von Neumann, plus a proximal-style potential discretization using optimal transport distance that adds hysteresis so the discrete configuration tracks a black-box fractional strategy with only (1+eps) loss in service cost and bounded movement cost.
Key results
- Any fully randomized MTS algorithm that is alpha-competitive yields a k-barely random algorithm that is (1+eps)alpha-competitive for k >= n^2/eps; with eps=1 this gives 2 log n random bits and an O(log^2 n) competitive ratio.
- Any k-barely random MTS algorithm is at least (2n-1)/k-competitive, implying at least log n - O(log log n) random bits are needed for O(log^2 n) competitiveness.
- On uniform metrics, an n-barely random algorithm achieves 2H_n+6 competitiveness, i.e. ceil(log n) random bits suffice for O(log n) competitiveness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| restrict randomness to k>=n^2/epsilon barely random values (discretize fully fractional strategy via Algorithm 1) | fully randomized MTS algorithm · general n-point metrics | competitive ratio: factor (1+epsilon) loss | No clear effect |
| naive rounding of fractional distribution to nearest barely fractional configuration | fractional MTS strategy · general n-point metrics | competitive ratio | Hurt |
| uniform metric: use n random bits with balls-and-urns discretized phase strategy | MTS on uniform metric · uniform metric space | competitive ratio | Helped |
| lower bound: k-barely random algorithms cannot beat (2n-1)/k competitive ratio | barely random MTS · general n-point metrics | competitive ratio | No clear effect |
Surprising findings
- A single deterministic agent is Omega(n)-competitive, yet a team of k >= n^2 deterministic agents can achieve O(log^2 n) competitiveness on average.
- Naive rounding of the fractional strategy to configurations does not preserve competitiveness because the adversary can exploit the discretization.
Limitations
- Requires k >= n^2/eps agents/random values, so whether k=O(n) suffices for optimal ratio remains open on general metrics.
- Lower bound only gives log n - O(log log n) bits, not matching 2 log n exactly.
- Theoretical paper with no empirical evaluation.
Experimental setup
Metrics: competitive ratio
Baselines: naive rounding of fractional strategy deterministic MTS 2n-1 bound uniform metric phase-based algorithm
Builds on: metrical task systems randomized O(log^2 n) algorithm work function algorithm Birkhoff-von Neumann theorem barely random algorithms (list update)
Closest papers by meaning
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.85)
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information (AAAI 2024 · similarity 0.85)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.84)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.83)
- Contextual Decision-Making with Knapsacks Beyond the Worst Case (NeurIPS 2024 · similarity 0.83)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.83)
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.