Fairness and Exploration in Sequential Decision Making

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2100 papers163 conceptsfrozen 2026-10-04

In traditional machine learning, fairness is often treated as a static constraint: we have a fixed dataset, and we want to ensure our model doesn't discriminate. But real-world systems—like bank loan approvals, hiring platforms, and dynamic pricing engines—are sequential. They learn from the outcomes of their own past decisions.

This creates a fundamental tension. To learn which decisions are best, an algorithm must explore by trying different options. However, in high-stakes environments, exploration can be inherently unfair. If an algorithm bypasses a highly qualified candidate to "test" a less qualified one for the sake of gathering data, it has violated a basic ethical principle of meritocracy.

The Exploration-Fairness Paradox

In a standard Multi-Armed Bandit (MAB) problem, an agent balances exploration (trying new things) and exploitation (choosing the best known option). Algorithms like Upper Confidence Bound (UCB) or Thompson Sampling are designed to be "optimistic," intentionally over-estimating the potential of unknown options to encourage exploration.

As Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth argue in Fairness in Learning: Classic and Contextual Bandits, this optimism is the root of the fairness problem. They define meritocratic fairness as a simple rule: the algorithm should never prefer a candidate with a lower true probability of success over one with a higher probability.

The paradox is that the algorithm doesn't know the true probabilities—that’s why it’s exploring. If the algorithm is forced to be fair, it cannot take a "risk" on a candidate that looks worse than a known good one.

The Learning Tax: Why Fairness Slows Down Progress

When you impose meritocratic constraints, you pay a "learning tax." In unconstrained learning, regret (the gap between the algorithm's performance and the optimal strategy) usually grows at a rate of $\sqrt{T}$. However, when strict fairness is required, this learning process can slow down dramatically.

In Fairness in Reinforcement Learning, Shahin Jabbari and colleagues demonstrate that enforcing fairness during exploration can lead to an exponential increase in the time required to reach optimality. Intuition suggests why: if the agent cannot use clever heuristics to favor promising actions, it is often forced to act uniformly at random until it achieves near-absolute certainty about every possible choice. This "wait-and-see" approach prevents the agent from quickly narrowing down the best options, trapping it in a state of prolonged ignorance to avoid making a single "unfair" exploratory choice.

The Selective Label Trap

A second major hurdle is the selective label problem, often called the "Bank Loan Problem." In many sequential settings, we only observe the outcome (the "label") if we take a positive action. We know if a person repaid a loan only if we granted it; we never learn if the people we rejected would have been successful.

Niki Kilbertus points out in Fair Decisions Despite Imperfect Predictions that this creates a self-fulfilling prophecy. If a model starts with a slight bias against a group, it will reject members of that group more often, thereby gathering less data about them. This lack of data keeps the model's uncertainty high, which—under certain fairness constraints—leads to even more rejections.

To break this cycle, researchers like Yahav Bechavod and Aaron Roth suggest framing the problem as a contextual semi-bandit. In Individually Fair Learning with One-Sided Feedback, they propose using "stochastic exploring policies." By occasionally making non-deterministic decisions—accepting someone the model is unsure about—the system can gather the labels necessary to correct its own biases over time.

Expanding Fairness to Allocation and Pricing

The research direction has recently expanded from simple "yes/no" decisions to complex resource distribution.

  • Online Fair Division: In problems where items must be distributed among agents with unknown preferences, Ariel D. Procaccia and Benjamin Schiffer show in Honor Among Bandits that fairness requirements shift the regret rate from $T^{1/2}$ to $T^{2/3}$. This shift happens because the allocator must ensure the distribution remains fair for all possible utility values within a statistical confidence region.
  • Doubly Fair Dynamic Pricing: In dynamic pricing, fairness can be procedural (offering the same price to similar people) or substantive (ensuring similar groups actually pay similar amounts). Dan Qiao and Yu-Xiang Wang argue in Doubly Fair Dynamic Pricing that randomized pricing is not just an ethical choice but a mathematical necessity to learn demand curves without violating these dual fairness bounds.

Summary of the Intuition

The core insight of this research area is that fairness is not a free lunch in dynamic systems. If you want to be fair while you learn, you must accept that you will learn more slowly. The "fairness tax" arises because ethical constraints restrict the algorithm's ability to experiment. However, by carefully designing "optimistic" or "stochastic" policies, researchers are finding ways to ensure that the cost of learning is distributed equitably, preventing the feedback loops that turn temporary uncertainty into permanent discrimination.

Papers in this version

Showing 60 of 100 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 61 papers
  2. Version 1 · 2026-10-04 · 100 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_exploration_fairness_tradeoff_84237aed,
  title = {exploration-fairness tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/exploration-fairness-tradeoff/rdr_84237aedbd5f44f99477e20c0bf6e85b},
  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_fairness_and_exploration_in_sequential_d_84237aed_v1,
  title = {Fairness and Exploration in Sequential Decision Making},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-and-exploration-in-sequential-decision-making/rdr_84237aedbd5f44f99477e20c0bf6e85b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}