Sublinear Regret for Fair Online Learning

This direction is split into other directions: sub-linear fairness regret, fairness-in-hindsight. Its last version stays readable and citable here.

Version 1 of 1101 papers125 conceptsfrozen 2026-10-04

In traditional online learning, an algorithm’s success is measured by its regret: the difference between the total reward it gathered and the reward it could have gathered if it had known the best strategy from the start. Standard algorithms like Upper Confidence Bound (UCB) are designed to be "greedy" for efficiency, often creating a winner-takes-all dynamic. As Lequn Wang and Thorsten Joachims observe in Fairness of Exposure in Stochastic Bandits, this utilitarian focus can leave nearly identical alternatives in the dark, leading to systemic bias in recommendations or resource allocation.

The emerging research direction in "Fair Online Learning" asks a fundamental question: Can we enforce social or ethical constraints—like ensuring every group gets a minimum share of resources—without sacrificing the speed at which the algorithm learns?

The Vanishing Fairness Tax

A central intuition across this field is that fairness and efficiency are asymptotically compatible. In many settings, the "cost" of being fair—often called the fairness tax—effectively vanishes over time.

Researchers like Stephen Gillen and Aaron Roth have shown in Online Learning with an Unknown Fairness Metric that even when the fairness metric is initially unknown, an algorithm can achieve the optimal $O(\sqrt{T})$ regret. This means that as the system matures, the frequency of fairness violations drops to near zero. The learner doesn't just get better at picking winners; it gets better at understanding the boundaries of equity.

From Total Reward to Social Welfare

To make fairness mathematically tractable, researchers have moved beyond simple reward summation toward Social Welfare Functions. Instead of maximizing the sum of rewards, these algorithms optimize for:

  • Nash Social Welfare: Maximizing the product (or geometric mean) of rewards. This naturally balances efficiency with equity, as a zero reward for any one participant would drive the entire objective to zero. Siddharth Barman and Ayush Sawarni demonstrate in Fairness and Welfare Quantification for Regret in Multi-Armed Bandits that a "Nash Confidence Bound" can achieve nearly optimal regret, proving that we can distribute rewards equitably without a fundamental loss in convergence speed.
  • Max-Min (Rawlsian) Fairness: Prioritizing the "weakest link" or the agent receiving the least reward. Arun Kumar Verma and Manjesh K. Hanawal apply this to energy harvesting in Learning and Fairness in Energy Harvesting, ensuring that no single node in a network runs out of power prematurely.

Stepwise vs. Long-Term Constraints

How strictly should fairness be enforced? The research splits into two primary mechanisms:

  1. Stepwise Fairness: Constraints must be met at every single time step. Zhun Deng and Zhiwei Steven Wu explore this in Reinforcement Learning with Stepwise Fairness Constraints, showing that agents can learn to balance long-term rewards with immediate ethical requirements. Similarly, Stephen Pasteris and Vasilios Mavroudis introduce meta-algorithms like FEW and SPEW that wrap around standard learners to guarantee exact statistical parity on every trial.
  2. Long-Term (Amortized) Fairness: Constraints are met on average over time. This is often managed via "virtual queues" that track how much reward a group is "owed." As Abhishek Sinha shows in BanditQ, these queues act as a pressure valve: when a group is underserved, the algorithm's priority shifts until the deficit is cleared.

Why It Works: The Data-Adaptive Exploration

The reason these fair algorithms don't collapse under the weight of their constraints is a shift in how they explore. Traditional UCB explores to find the best arm. Fair algorithms, like those proposed by Dhruv Sarkar and Sayak Ray Chowdhury in Revisiting Social Welfare in Bandits, use a data-adaptive exploration phase.

By spending a small, calculated amount of time exploring all options—or by using "John Ellipsoids" for geometric sampling as in Nash Regret Guarantees for Linear Bandits—the algorithm gains enough information to satisfy fairness constraints early on. Once the "shape" of the reward space is understood, the algorithm can satisfy the fairness requirements (like minimum pull rates) using the most efficient arms possible, leading to the "constant regret" phenomenon described by Vishakha Patil in Achieving Fairness in the Stochastic Multi-Armed Bandit Problem.

Papers in this version

Showing 60 of 101 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sublinear_regret_for_fair_online_learnin_885ac03d,
  title = {Sublinear Regret for Fair Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-regret-for-fair-online-learning/rdr_885ac03dd43a4f78a425c40bc4a4e36c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sublinear_regret_for_fair_online_learnin_885ac03d_v1,
  title = {Sublinear Regret for Fair Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-regret-for-fair-online-learning/rdr_885ac03dd43a4f78a425c40bc4a4e36c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}