In sequential decision-making frameworks like multi-armed bandits and reinforcement learning (RL), an agent faces a classic dilemma: should it exploit its current knowledge by choosing the best-performing option, or explore uncertain options to gather information that might yield higher long-term rewards?
Traditionally, algorithms resolve this by being "optimistic under uncertainty"—intentionally choosing sub-optimal or unknown actions to map out the environment. However, when these choices affect human lives—such as allocating bank loans, displaying job advertisements, or selecting patients for clinical trials—this exploratory behavior runs directly into ethical constraints. Choosing a highly uncertain option means intentionally passing over a known, high-quality option, creating a fundamental conflict with meritocratic fairness, which dictates that a demonstrably worse option should never be preferred over a better one.
The Mathematical Cost of Strict Fairness
When we force a learning agent to be strictly fair at every single step, we strip away its primary tool for gathering information: aggressive, targeted exploration. The mathematical consequences of this restriction are severe.
In a foundational study on classic and contextual bandits, Joseph et al. demonstrated that maintaining individual fairness introduces a massive performance penalty. Because the learner cannot temporarily favor a lower-performing option to gain information, it must wait for statistical confidence to slowly accumulate. This restriction causes a significant increase in the data required to find an optimal policy, often resulting in cubic or even exponential increases in cumulative regret compared to unconstrained algorithms.
This problem compounds dramatically when moving from simple bandits to full reinforcement learning environments, where an agent's actions alter its future states. As Jabbari et al. proved, requiring strict meritocratic fairness at every step forces the learning complexity to become exponential in the number of environment states.
Standard Exploration (Optimistic)
[Known Good Option] < [Unknown Option (High Uncertainty)] --> Agent Explores (Unfair to Known Option)
Fair Exploration (Conservative)
[Known Good Option] > [Unknown Option (Low Confidence)] --> Agent Blocked from Exploring Directly
To prevent this exponential slowdown, the authors introduced Fair-E3, which relaxes strict fairness to an "approximate-action" constraint. Instead of deterministic optimistic exploration, it utilizes random trajectories from unknown states. Because random actions do not systematically favor one choice over another, they satisfy basic fairness requirements while allowing the agent to gather environmental data in polynomial time.
The Externalities of Exploration: Who Pays for Learning?
In a standard utilitarian framework, an algorithm minimizes total system regret without considering who receives the sub-optimal recommendations during the learning phase. This indifference creates severe group-level disparities.
As Raghavan et al. demonstrated, when distinct populations are combined in a shared learning environment, majority data can skew the model's uncertainty estimates. Consequently, minority groups are often subjected to excessive, irrelevant exploration that does not align with their optimal actions—effectively forcing them to subsidize the learning process for the majority.
To distribute this burden equitably, Baek et al. proposed a framework based on Nash axiomatic bargaining. Instead of allowing arbitrary disparities in exploration costs, their approach calculates an ideal distribution of arm pulls based on current reward estimates. It then prioritizes actions for groups that are currently under-explored relative to a fair target, ensuring that the cost of finding the optimal policy is shared equitably across demographic or functional groups with minimal impact on total system performance.
Similarly, in multi-agent cooperative settings, individual agents can be exploited for the collective good. The authors of UCB-TCOM addressed this by designing a mechanism that strategically shares information only about suboptimal arms. This protects the "worst-off" individual agent from bearing the brunt of risky exploration, balancing group efficiency with individual fairness.
The Selective Labels Problem: Why Exploration is Required for Fairness
While exploration can cause short-term unfairness, a complete lack of exploration guarantees long-term discrimination due to selective labels (or censored feedback). In real-world scenarios like lending or hiring, an organization only observes the outcome (e.g., loan repayment) if they grant the opportunity. If a deterministic model decides to reject a subpopulation based on biased historical data, it will never collect the data needed to correct its mistake.
Kilbertus et al. and Wen argue that active exploration is a prerequisite for achieving true long-term fairness. By utilizing stochastic exploring policies to gather data on previously rejected or underrepresented segments, a system can identify profitable opportunities that deterministic models overlook.
To balance the short-term financial or ethical costs of this data collection, Yang et al. introduced a framework called bounded exploration. Instead of completely unconstrained exploration, the algorithm limits how far it deviates from its current optimal policy, recovering unbiased estimates of population characteristics over time while keeping short-term utility losses within acceptable bounds.
Deterministic Policy (No Exploration)
Historical Bias --> Reject Group --> No New Data --> Bias Perpetuated (Downward Spiral)
Stochastic Policy (Bounded Exploration)
Historical Bias --> Explore Group (Accept Some) --> New Data Observed --> Model Corrected (Long-term Fairness)
Relaxing Constraints and Exploiting Mathematical Slack
To bypass the severe regret penalties associated with strict step-by-step fairness, recent literature focuses on relaxing temporal constraints or exploiting the mathematical structure of fairness definitions.
Fairness in Hindsight
Gupta et al. proposed shifting from "fairness-across-time" (which binds the algorithm at every single step) to fairness-in-hindsight. This definition allows decisions to become more conducive over time as the algorithm learns. By permitting the system to adapt its policy retroactively as confidence grows, their algorithm, CaFE, achieves near-optimal regret guarantees while ensuring fairness at the specific moment of decision.
Exploiting Definition Slack
In online fair division problems (where items must be distributed fairly among players with unknown preferences), strict constraints typically degrade the regret rate from $T^{1/2}$ to $T^{2/3}$ because the allocation must remain valid for all potential values within a statistical confidence region. However, Schiffer et al. demonstrated that by exploiting the mathematical slack within specific fairness definitions like proportionality, an algorithm can safely deviate from the perceived optimal allocation for exploration purposes without breaching the minimum utility guarantees required for a fair distribution.
Any-Time Meta-Algorithms
Rather than designing new bandit algorithms from scratch, Patil et al. developed FAIR-LEARN, a meta-algorithm that can wrap around any standard bandit learner. It guarantees that every choice (or arm) is pulled at least a minimum fraction of times at every step, ensuring an "any-time" fairness guarantee while maintaining sub-logarithmic regret relative to an optimal fair policy.
Turning Fairness into an Exploration Driver
Perhaps the most counterintuitive insight in this research area is that fairness constraints do not always hinder performance—they can sometimes replace explicit exploration mechanisms entirely.
In linear contextual bandits, standard algorithms rely on complex geometric calculations (like confidence ellipsoids) to force exploration into unknown feature spaces. Akhavan et al. introduced Group Meritocratic Fairness (GMF), which selects candidates based on their relative rank within their own demographic group rather than their absolute reward score.
Because the highest-ranked individuals are naturally distributed across all groups, enforcing this fairness constraint forces the agent to sample from diverse feature subspaces. The authors proved that this fair-greedy selection naturally ensures sufficient exploration to learn the global reward model, completely eliminating the need for artificial optimism-under-uncertainty mechanisms while achieving optimal sub-linear regret.
Key Foundational Work
Fairness in Reinforcement Learning (2017) — contributed 5 concept elements to this direction.
Fair Learning in Markovian Environments (2016) — contributed 4 concept elements to this direction.
Exploring or Exploiting? Social and Ethical Implications of Autonomous Experimentation in AI (2016) — contributed 3 concept elements to this direction.