Research map / Reinforcement learning / MDPs and planning
Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives oracle-efficient game-theoretic algorithms (FTPL, contextual FTPL, fictitious play) for minimax group-fairness RL with exponentially many intersectional group constraints, evaluated on Barabási-Albert graph MDPs.
Problem
Maximizing reward for the worst-off group in RL when groups are arbitrarily intersecting and there may be exponentially many (e.g., all intersections of d attributes) fairness constraints.
Approach
Casts the constrained/minimax group-reward RL problem as a zero-sum game between learner (best response via standard unconstrained RL) and regulator (no-regret updates via optimization oracles over the group class), using follow-the-perturbed-leader (tabular and separator-set cases) or fictitious play (general groups).
Key results
- On the BA graph MDP with alpha/H = 0.04, FairFictRL ensures all groups reach at least 0.04 average reward within a few iterations, while the unconstrained optimum yields at most 0.3 for Group 2 and lower for others.
- Varying alpha traces a Pareto frontier: increasing the minimum group reward equalizes group rewards at the cost of total reward.
- Theory: oracle-efficient reductions give poly-time convergence for tabular MDPs (FTPL) and large MDPs with separator sets (contextual FTPL); fictitious play converges only asymptotically.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| enforce a minimum average group reward of 0.04 using FairFictRL | FairFictRL · Preferential attachment graph MDP | average group reward: 0.04 | Helped |
| increase the minimum average group reward constraint | FairFictRL · Preferential attachment graph MDP | average total reward | Hurt |
| increase the minimum average group reward constraint | FairFictRL · Preferential attachment graph MDP | equality of group rewards | Helped |
Limitations
- Efficiency depends on implementing best-response and optimization oracles efficiently.
- Results rely on boolean group structure; infinite group classes not covered.
- FairFictRL has only asymptotic convergence guarantees and no polynomial-time bound.
Experimental setup
Datasets: synthetic Barabási-Albert preferential attachment graph MDP
Benchmarks: Barabási-Albert graph MDP
Metrics: average reward per group total average reward constraint satisfaction over iterations
Baselines: unconstrained optimal policy
Builds on: Follow the Perturbed Leader contextual FTPL with separator sets fictitious play Sion's minimax theorem Barabási-Albert model
Closest papers by meaning
- FairDICE: Fairness-Driven Offline Multi-Objective Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Fair Cooperation in Mixed-Motive Games via Conflict-Aware Gradient Adjustment (NeurIPS 2025 · similarity 0.86)
- Projection Optimization: A General Framework for Multi-Objective and Multi-Group RLHF (ICML 2025 · similarity 0.86)
- On Generalization Across Environments In Multi-Objective Reinforcement Learning (ICLR 2025 · similarity 0.86)
- Fair Participation via Sequential Policies (AAAI 2024 · similarity 0.86)
- Conflict-Averse Gradient Aggregation for Constrained Multi-Objective Reinforcement Learning (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.