Source-linked AI summary
Fairness in Reinforcement Learning
Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Aaron Roth
TL;DR
Fairness in reinforcement learning must account for actions’ effects on future states and discounted rewards, rather than only immediate outcomes. The paper defines long-term-reward fairness, proves exponential lower bounds for exact and approximate-choice fairness, and presents Fair-E3 under approximate-action fairness. Fair-E3 achieves ϵ-optimality with exponential dependence on 1/(1 −γ), matching the lower bound, while establishing a gap between exact and approximate fairness.
Problem
Existing fairness definitions focus on myopic settings and do not capture how reinforcement-learning actions affect future states and long-term rewards.
Method
The paper defines fairness using optimal discounted action values and develops the Fair-E3 algorithm under approximate-action fairness.
Results
Fair and approximate-choice fair algorithms require exponentially many rounds in the number of states, while Fair-E3’s exponential dependence on 1/(1 −γ) is tight.
Takeaways & Limitations
The results establish an exponential gap between exact and approximate fairness and rigorous trade-offs between fairness and reinforcement-learning performance.
Takeaways & Limitations
The fairness notion permits conditional discrimination and is a necessary rather than sufficient fairness requirement.
Abstract
from arXiv · showhide
We initiate the study of fairness in reinforcement learning, where the actions of a learning algorithm may affect its environment and future rewards. Our fairness constraint requires that an algorithm never prefers one action over another if the long-term (discounted) reward of choosing the latter action is higher. Our first result is negative: despite the fact that fairness is consistent with the optimal policy, any learning algorithm satisfying fairness must take time exponential in the number of states to achieve non-trivial approximation to the optimal policy. We then provide a provably fair polynomial time algorithm under an approximate notion of fairness, thus establishing an exponential gap between exact and approximate fairness
1 Introduction
This paper initiates fairness research in reinforcement learning, where actions affect future states and rewards. It defines fairness through long-term reward and establishes exponential barriers for exact or some approximate notions, alongside a polynomial-time algorithm under approximate-action fairness.
- Motivation: Reinforcement-learning actions can influence the environment and future rewards, unlike the myopic settings emphasized by earlier fair machine-learning work.The paper frames fairness around historical context and long-term consequences of decisions.
- Fairness notion: Fairness requires assigning no greater probability to an action than to another action with higher discounted long-term reward.The definition is weakly meritocratic: better actions need not receive greater probability, but worse actions cannot be favored.
- Relaxation: Approximate-action fairness is a weaker constraint that prevents favoring substantially worse actions and enables the Fair-E3 algorithm.The relaxation preserves a minimal fairness requirement while supporting a polynomial upper bound in the paper’s stated parameters.
- Results: For constant ϵ, fair and approximate-choice fair algorithms require exponentially many rounds in the number of MDP states to achieve ϵ-optimality.This lower bound describes the time needed for near-optimal learning under these fairness constraints.
- Results: For constant ϵ, approximate-action fair algorithms require exponentially many rounds in 1/(1 −γ), and Fair-E3 matches this dependence while achieving ϵ-optimality.The result establishes tightness in the discount-factor dependence.
- Limitations: The fairness model permits conditional discrimination and therefore represents a necessary rather than sufficient fairness requirement.The authors identify this as both a limitation of the notion and a reason their lower bounds are stronger while upper bounds are weaker.
2 Preliminaries
The paper formalizes reinforcement learning in MDPs, discounted value functions, mixing assumptions, and fairness notions based on optimal long-term action values. It shows why immediate-reward fairness is unsuitable and motivates approximate-action fairness as a weaker alternative.
- MDPs and value functions: An MDP is defined by states, actions, transition and reward distributions, a horizon, and discount factor γ.The paper uses an MDP tuple M = (S_M, A_M, P_M, R_M, T, γ), with n states and k actions.
- MDPs and value functions: Policies map histories of observed state, action, and reward triples to action distributions, while V^π and Q^π represent discounted state and state-action values.The optimal policy’s corresponding value functions are denoted V* and Q*.
- Assumptions and performance: The unichain assumption requires every policy’s stationary distribution to be independent of its start state.The paper also uses mixing-time arguments to relate visited-state values to stationary expected values.
- Assumptions and performance: ϵ-optimality requires that, after sufficiently many steps, visited states have values close to those visited by the optimal policy.This is stronger than a notion requiring only termination from a state with near-optimal discounted return.
- Fairness notions: Fairness is defined using Q* because immediate-reward fairness would prohibit short-term sacrifices needed to obtain long-term rewards.The paper therefore evaluates an action’s quality through its true discounted long-term reward.
- Fairness notions: Exact fairness can force uniform randomization until the algorithm has high confidence in Q* values, causing exponential learning time in some cases.This motivates approximate-choice fairness and then approximate-action fairness.
- Fairness notions: Approximate-action fairness prevents substantially worse actions from being chosen over better ones, while preserving that optimal policies and the uniformly random policy satisfy it.The restricted MDP construction retains the original optimum while making every policy approximately-action fair.
3 Lower Bounds
The lower bounds show that exact fairness and approximate-choice fairness can make near-optimal reinforcement learning require exponentially many steps in the number of states. Approximate-action fairness avoids this state-space exponential dependence, although its learning time remains exponentially dependent on 1/(1−γ).
- Lower-bound motivation: Polynomial-time unconstrained reinforcement learning can achieve an ϵ-optimal policy, whereas fairness constraints impose a steep performance cost.The paper contrasts standard polynomial learning rates with its fairness lower bounds.
- Proof idea: The lower-bound construction forces fair algorithms to play actions uniformly until reaching s_n and observing its reward, requiring k^n steps.For k > 2, only one action advances from each state while the others return to s_1.
- Approximate-choice fairness: T = O((k/(1+kα))^n) steps are insufficient for any α-choice fair algorithm to be ϵ-optimal when δ < 1/4, α < 1/4, γ > 1/2, and ϵ < 1/8.The theorem establishes a separate exponential lower bound for approximate-choice fairness.
- Approximate-action fairness: Approximate-action fairness has polynomial dependence on the state-space parameters but still incurs exponential dependence on 1/(1−γ).This dependence is substantially less stringent than the lower bounds for exact fairness and approximate-choice fairness when γ is treated as constant.
4 A Fair and Efficient Learning Algorithm
Fair-E3 is an approximate-action fair learning algorithm that balances exploration and exploitation using estimates from known states. It achieves near-optimality with polynomial dependence on most MDP parameters, while necessarily retaining exponential dependence on 1/(1 −γ).
- Fair-E3 is an α-action fair algorithm that achieves ϵ-optimality after a provable number of steps.The stated guarantee hides poly-logarithmic terms.
- Guarantees and limitations: The running time is polynomial in all MDP parameters except 1/(1 −γ), and this exponential dependence is necessary by the matching lower bound.The paper identifies this dependence as tight for approximate-action fair algorithms.
- Known states: Known states provide sufficiently accurate estimates of rewards, transitions, and optimal action values for Fair-E3’s planning decisions.A state becomes known after enough action observations and random trajectories to estimate these quantities with high probability.
- Planning in Fair-E3: In a known state, Fair-E3 computes an exploration policy and a near-optimal exploitation policy, then explores when the estimated escape probability is sufficiently large and otherwise exploits.From unknown states, it follows a uniformly random trajectory for Hγ_ϵ steps; encounters with unknown states trigger a length-Hγ_ϵ trajectory.
- Planning in Fair-E3: Fair-E3 constructs exploitation and exploration MDPs that respectively reward remaining in known states and reaching unknown states.The exploitation MDP condenses unknown states into an absorbing, unrewarded state, while the exploration MDP rewards escape to that state.
- Analysis of Fair-E3: The Fair-E3 analysis guarantees either a high-reward exploitation policy or an exploration policy that reaches an unknown state quickly, supporting its exploration–exploitation choice.The exploit-or-explore lemma gives an exploration policy whose probability of reaching the absorbing state within 2T*_ϵ steps exceeds β/T.
5 Discussion and Future Work
The paper identifies unresolved trade-offs in fairness-constrained reinforcement learning. It leaves open whether stronger or less frequent fairness guarantees can improve performance without sacrificing nondiscrimination.
- Open questions: Approximate-action fairness has an undesirable exponential dependence on 1/(1−γ), and the paper shows this dependence is unavoidable for that class.Without fairness, near-optimal learning can be polynomial in all underlying MDP parameters.
- Open questions: It remains open whether a meaningful fairness notion can enable reinforcement learning in time polynomial in all MDP parameters.
- Open questions: The fairness definitions may be modulated to bind across time rather than only across actions available at the moment.The paper states that the performance trade-offs of such a strengthening are unclear.
- Open questions: The paper also leaves unclear whether relaxing the every-step guarantee can improve performance while still forbidding discrimination.
A.1 Omitted Proofs for Section 2
This appendix develops technical bounds involving finite-horizon discounted values and state-distribution mixing. The argument uses reward bounds and the fact that the horizon is at least the policy’s mixing time.
- Finite-horizon values: V^π(s,T) denotes expected discounted reward after following policy π from state s for T steps.
- Proof ingredients: The proof identifies the final inequality as following from the reward bound and the discounted-value bound.
- Finite-horizon values: Rewards bounded in [0,1] imply V^π_M(s_i) ≤ 1/(1−γ).
- Mixing argument: When T is at least the ε-mixing time of π, the relevant state-distribution discrepancy is at most ε.
A.2 Omitted Proofs for Section 3
The omitted proofs establish exponential lower bounds for fair learning through MDP constructions that conceal valuable actions behind uniformly random exploration. They extend the bounds across action counts and discount factors.
- Theorem 3: Until reaching s_n, fairness can force a two-action algorithm to choose left and right uniformly, making reaching s_n take exponential time in the number of states.The construction uses coupled MDPs whose observations are identical before s_n.
- Theorems 3–4: For constant ε, fair and approximate-choice-fair algorithms require exponentially many rounds in the number of MDP states to achieve ε-optimality.
- Theorem 3: For k actions, modifying the construction yields lower bounds of Ω(k^n) time steps for fair algorithms satisfying ε-optimality.
- Proof strategy: The proof bounds random-walk reachability of distant states and combines it with discounted-value bounds to show that near-optimality is impossible under the stated parameter ranges.
A.3 Omitted Proofs for Section 4
These omitted proofs analyze Fair-E3 by separating model-estimation and exploration failures. They use approximate MDPs, empirical transition and reward estimates, and repeated exploratory trajectories to establish the algorithm’s guarantees.
- Exploration: An exploration policy is used when a length-2T walk reaches unknown states with probability at least β.
- Policy construction: The exploration policy can be derived by computing an optimal policy in the exploration MDP over unknown states, while exploitation uses the optimal policy in the known-state MDP.
- Model approximation: Empirical transition and reward estimates make the known-state model an O(min{ε,α}^2/4)-approximation with high probability.
- Failure analysis: The proof partitions Fair-E3 failure into poor transition estimates, poor Q-value estimates, unsuccessful exploration, and inaccurate state values.
- Probability control: Failure probabilities are distributed across the listed sources using confidence parameters such as δ/(4n), δ/(4nk), and δ/(4m_exp).
A.4 Relaxing Assumption 2
Fair-E3 can relax the assumption that the optimal policy’s ϵ-mixing time T∗ϵ is known by trying sequential guesses, while retaining polynomial dependence on T∗ϵ.
- Fair-E3 is parameterized by the optimal policy’s ϵ-mixing time T∗ϵ, which Sections 4.3 and 4.4 initially assume is known.
- Sequentially trying T∗ϵ = 1, 2, . . . preserves polynomial running time and sample complexity in T∗ϵ.
- Without knowing T∗ϵ, the new algorithm runs sufficiently long for near-optimal V∗M values to dominate possibly low early-stage values.
B Observations on Optimality and Fairness
The observations establish that fairness is compatible with optimality: an optimal fair policy exists, every optimal policy is approximately-action fair, and uniform randomization is fair.
- For every MDP, there exists an optimal policy π∗ that is fair.
- The policy that uniformly randomizes among actions maximizing Q∗M is both fair and optimal.
- Any optimal policy, including a deterministic one, is approximate-action fair.
- Uniformly randomizing over every available action in every state, regardless of history, is fair.
- A policy in the α-restricted MDP is α-action fair, and an optimal policy in that restricted MDP remains optimal in the original MDP.
C Omitted Details of Fair-E3
The omitted details define exploitation and exploration MDPs on known states, then introduce empirical approximation MDPs using observed transition and reward estimates.
- Exploitation MDP: The exploitation MDP MΓ is defined on known states Γ, with deterministic rewards and an absorbing state s0.
- Exploitation MDP: Transitions between states in Γ are preserved, while transitions from Γ to unknown states are redirected to s0.
- Exploration MDP: The exploration MDP M[n]\Γ shares the exploitation MDP’s structure but assigns zero rewards on known states and reward one at s0.
- Approximation MDPs: Approximation MDPs ˆMΓ and ˆM[n]\Γ use the same state-action sets as their corresponding MDPs.
- Approximation MDPs: For ˆMΓ, empirical transition probabilities are estimated from visits to states, and empirical average rewards are estimated from visits to each known state.