The Incompatibility of Regret and Competitive Ratio

This direction is merged into another direction: dynamic regret minimization (dynamic regret). Its last version stays readable and citable here.

Version 1 of 19 papers17 conceptsfrozen 2026-10-04

In the world of online decision-making, an algorithm must make a sequence of choices without knowing what the future holds. To evaluate how well these algorithms perform, researchers have historically relied on two different "gold standards" from two different communities: Regret (from Machine Learning) and the Competitive Ratio (from Theoretical Computer Science).

While both metrics aim to measure robustness, they represent fundamentally different philosophies. Recent research has revealed that these two goals are often mathematically incompatible, forcing a choice between performing well in stable environments versus volatile ones.

Two Ways to Measure Success

To understand the conflict, we first need to look at what each metric benchmarks against.

  1. Regret (The Static Benchmark): This metric compares your total cost to the cost of the single best fixed action in hindsight. If you had to pick one move and stick with it for the entire duration, how much better would you have done? Achieving "sublinear regret" means that, over time, your average performance becomes as good as that best fixed action.
  2. Competitive Ratio (The Dynamic Benchmark): This metric compares your performance to the best dynamic sequence of actions. It asks: if an omniscient adversary could change their move at every single step to be optimal, how close can you stay to them?

As Niv Buchbinder, Seffi Naor, and their colleagues noted in Unified Algorithms for Online Learning and Competitive Analysis, these two frameworks were developed in isolation. This separation prevented the creation of algorithms that could adaptively balance the need for long-term stability with the need for short-term agility.

The Fundamental Conflict

The intuition for why these metrics clash is simple: Regret rewards settling, while the Competitive Ratio rewards chasing.

If you want to minimize regret, you must eventually converge on a single "best" decision. If you keep switching your strategy back and forth, you will likely incur high costs compared to someone who just picked the best fixed option. However, if you settle on a fixed decision to satisfy the regret metric, a dynamic adversary can easily exploit you. By moving the "optimal" state far away from your chosen fixed point, the adversary ensures your competitive ratio becomes terrible.

This isn't just a practical difficulty; it is a mathematical impossibility. In A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret, Lachlan L. H. Andrew, Adam Wierman, and their co-authors proved that no algorithm can simultaneously achieve sublinear regret and a constant competitive ratio. If you are perfectly optimized for a stable world (low regret), you are vulnerable to volatility. If you are robust against a dynamic adversary (constant competitive ratio), you will never "learn" enough to match the best fixed action in a stable environment.

Bridging the Gap with Randomly Biased Greedy

Since we cannot have both perfectly, the research shifted toward finding the optimal trade-off. Katrina Ligett and Adam Meyerson explored this in their work on the Randomly Biased Greedy (RBG) algorithm.

RBG works by adding a controlled amount of "bias" or "inertia" to a greedy strategy. By tuning this bias, a researcher can move an algorithm along a Pareto frontier:

  • High Bias: The algorithm stays closer to its previous decisions, favoring low regret but risking a poor competitive ratio if the environment shifts drastically.
  • Low Bias: The algorithm reacts quickly to new information, maintaining a good competitive ratio but failing to settle on a single best action, leading to higher regret.

The Reactive Adversary Problem

The conflict becomes even more pronounced when the environment isn't just "dynamic" but "reactive." In many real-world scenarios, like repeated games or high-frequency trading, the adversary observes your moves and changes their strategy specifically to hurt you.

In Policy Regret in Repeated Games, Raman Arora and Mehryar Mohri demonstrate that in these adversarial settings, "external regret" (the standard regret) and "policy regret" (regret against an adversary that reacts to your strategy) are often mutually exclusive.

If you try to minimize external regret, a clever adversary can "lure" you into a specific strategy and then punish you for it. This reinforces the core lesson of this research direction: there is no such thing as a "universally robust" online algorithm. Every choice of metric is a choice about which type of uncertainty—static or dynamic—you are most willing to tolerate.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_incompatibility_of_regret_and_compet_8ecc011e,
  title = {The Incompatibility of Regret and Competitive Ratio},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-incompatibility-of-regret-and-competitive-ratio/rdr_8ecc011e207841df9bb545ecef6ac1eb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_incompatibility_of_regret_and_compet_8ecc011e_v1,
  title = {The Incompatibility of Regret and Competitive Ratio},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-incompatibility-of-regret-and-competitive-ratio/rdr_8ecc011e207841df9bb545ecef6ac1eb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}