Barely Random Algorithms for Metrical Task Systems

Romain Cosson, Laurent MassouliéarXiv 2024 · arXiv · OpenReview

Abstract

We consider metrical task systems (MTS) on general metric spaces with $n$ points and demonstrate that any fully randomized algorithm can be transformed into a randomized algorithm using only $2\log n$ random bits while maintaining the same competitive ratio up to a factor of 2. This result provides the first order-optimal "barely random" algorithms for MTS—algorithms where the number of random bits is independent of the number of requests. We further introduce the concept of collective metrical task systems, where a team of $k$ agents suffers the average cost of its members. Our findings show that such a team can achieve $O(\log^2 n)$-competitiveness with $k \geq n^2$ agents, a significant improvement over the $\Omega(n)$ lower bound for a single deterministic agent. These results have broad implications for distributed systems, advice complexity, and transaction costs in online decision-making.

Introduction

Metrical Task Systems (MTS) serve as a fundamental framework for studying online decision-making under uncertainty. In an MTS, an agent moves within a metric space of $n$ points. At each discrete time step, a task arrives in the form of a cost vector, assigning a service cost to each point. The agent must decide whether to remain at its current location or move to a new one, incurring a movement cost proportional to the distance traveled.

The performance of MTS algorithms is measured by the competitive ratio—the ratio between the algorithm's total cost and the cost of an optimal offline adversary. Historically, a wide gap has existed between deterministic and randomized approaches:

  • Deterministic algorithms are limited to a competitive ratio of $2n-1$.
  • Randomized algorithms can achieve a significantly better ratio of $O(\log^2 n)$.

However, state-of-the-art randomized algorithms typically assume access to an infinite stream of random bits to maintain continuous probability distributions over the metric space. This paper investigates whether such an infinite supply is necessary, or if order-optimal performance can be achieved with a strictly limited amount of randomness.

Methodology

The Collective Viewpoint

The authors bridge the gap between randomness and determinism by establishing a mathematical equivalence between a "barely random" algorithm (using $b$ random bits) and a collective metrical task system consisting of $k = 2^b$ deterministic agents. In this collective model, the total cost is defined as the average cost incurred by the team. This perspective allows the problem of reducing randomness to be reframed as a discretization problem: how can a continuous probability distribution be represented by a finite set of $k$ points?

Discrete First-Order Tracking

To convert a continuous randomized strategy into a discrete one, the authors propose a tracking algorithm based on a proximal operator. The core challenge is to ensure that the discrete configuration of agents accurately follows the ideal continuous distribution without excessive movement.

The authors utilize a potential function $D(x, y)$ based on Optimal Transport (Wasserstein-1 distance) to manage this tracking. A key innovation is the introduction of a "hysteresis" effect. By preventing agents from reacting to infinitesimal shifts in the target distribution, the algorithm avoids "jittering," which would otherwise lead to prohibitive movement costs. To ensure agents can move optimally without needing to be split into fractional parts, the authors apply the Birkhoff-von Neumann Theorem to decompose the required movement into a set of valid permutations.

Key Results

The Conversion Theorem

The central theoretical contribution is a conversion theorem: any $\alpha$-competitive randomized MTS algorithm can be transformed into a $(1+\epsilon)\alpha$-competitive algorithm using $k \ge n^2/\epsilon$ agents. In terms of randomness, this implies that approximately $2 \log n$ bits are sufficient to achieve order-optimal performance.

Performance Bounds

  • General Metric Spaces: The paper proves that for any $n$-point metric, there exists an $O(\log^2 n)$-competitive algorithm using only $\lceil 2 \log n \rceil$ random bits.
  • Uniform Metric Spaces: In the specific case of uniform metrics (where all distances are equal), the requirement is even lower: $\lceil \log n \rceil$ bits are sufficient to achieve $O(\log n)$-competitiveness.
  • Lower Bounds: The authors demonstrate that their upper bound is nearly tight, proving that any $O(\log^2 n)$-competitive algorithm must use at least $\log n - O(\log \log n)$ random bits.

Implications and Discussion

Advice Complexity and Distributed Systems

The results suggest that a very small amount of "advice" about the future—only $2 \log n$ bits total for the entire duration of the process—is enough to break the linear lower bound of deterministic algorithms. Furthermore, the collective model suggests that "intelligence" in multi-agent systems can effectively mimic the benefits of randomness, provided the agents can coordinate their positions.

Transaction Costs

The discretization approach makes MTS more robust to fixed transaction costs. Because the hysteresis mechanism prevents unnecessary movement, the algorithm is naturally suited for environments where every move incurs a baseline fee, a common scenario in financial modeling and asset management.

Conclusion and Future Work

This work establishes that $2 \log n$ random bits are the "magic number" for Metrical Task Systems, providing a bridge between the $O(1)$ bits of deterministic systems and the infinite bits of continuous randomized models. While $n^2$ agents are sufficient for general metrics, future research may investigate if $O(n)$ agents (or $\log n$ bits) suffice for specific metric classes, such as weighted stars. Additionally, exploring "distributed collective MTS," where agents have limited communication or act selfishly, remains a promising avenue for future study.

Summary updated

Abstract

We consider metrical task systems on general metric spaces with $n$ points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only $2\log n$ random bits, and achieves the same competitive ratio up to a factor $2$. This provides the first order-optimal barely random algorithms for metrical task systems, i.e., which use a number of random bits that does not depend on the number of requests addressed to the system. We discuss implications on various aspects of online decision-making such as: distributed systems, advice complexity, and transaction costs, suggesting broad applicability. We put forward an equivalent view that we call collective metrical task systems where $k$ agents in a metrical task system team up, and suffer the average cost paid by each agent. Our results imply that such a team can be $O(\log^2 n)$-competitive as soon as $k\geq n^2$. In comparison, a single agent is always $\Omega(n)$-competitive.
BibTeX
@misc{cosson2024barely,
  author = {Romain Cosson and Laurent Massoulié},
  title = {{Barely Random Algorithms for Metrical Task Systems}},
  year = {2024},
  eprint = {2403.11267},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.11267},
}

Loading related content...

Figure