Research map / Learning theory and algorithms / Fairness
Remembering to Be Fair: Non-Markovian Fairness in Sequential Decision Making
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.
Formalizes non-Markovian fairness over decision histories (long-term, periodic, anytime, bounded fairness), shows value-regular status functions can be made Markovian via memory augmentation, and proposes FairQCM, which generates counterfactual memory experiences for Q-learning.
Problem
Fairness in sequential multi-stakeholder decision making depends on the history of decisions and must be assessed at intermediate time points, so it is non-Markovian and standard MDP methods do not directly apply.
Approach
Defines a fairness-scheme formalism (status function, extended aggregation, filter) that expresses long-term, periodic, anytime and bounded fairness; uses memory augmentation to make value-regular status functions Markovian; and generates counterfactual memory experiences (FairQCM) to improve sample efficiency of fair policy learning.
Key results
- In the doughnut allocation simulation, deep FairQCM achieves higher accumulated Nash welfare than Full, Min, RNN and Reset memory baselines across training.
- In simulated lending, FairQCM outperforms the other memory-augmented approaches on accumulated relaxed demographic parity score, and all approaches reach the 10 percent profit margin.
- Tabular FairQCM converges to the optimal Q-function with probability 1 under standard stochastic approximation conditions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FairQCM with counterfactual memory experiences instead of the evaluated memory-augmented RL baselines | DQN-based resource allocation · Resource Allocation | accumulated Nash welfare | Helped |
| use FairQCM with counterfactual memory experiences instead of the evaluated memory-augmented RL baselines | DQN-based resource allocation · Resource Allocation | sample efficiency | Helped |
| use FairQCM with counterfactual memory experiences instead of the evaluated memory-augmented RL baselines | Q-learning resource allocation · Tabular Resource Allocation | accumulated Nash welfare | Helped |
| use FairQCM with counterfactual memory experiences instead of the evaluated memory-augmented RL baselines | Q-learning resource allocation · Tabular Resource Allocation | samples needed to train | Helped |
| use FairQCM with counterfactual memory experiences instead of the evaluated memory-augmented RL baselines | DQN-based simulated lending · Simulated Lending | accumulated Relaxed Demographic Parity score | Helped |
| use FairQCM with counterfactual memory experiences instead of the evaluated memory-augmented RL baselines | DQN-based simulated lending with Gaussian credit score changes · Simulated Lending with Gaussian Credit Score Changes | accumulated Relaxed Demographic Parity score | Helped |
| use a GRU memory instead of some other evaluated memory baselines | DQN-based resource allocation · Resource Allocation | accumulated Nash welfare | Helped |
| use a GRU memory instead of some other evaluated memory baselines | DQN-based simulated lending · Simulated Lending | accumulated Relaxed Demographic Parity score | Helped |
Surprising findings
- The RNN baseline, which has no explicit memory, learns an approximation of history and beats some explicit-memory baselines.
Limitations
- Only a small set of fairness scoring functions was explored.
- Experiments are on simple simulated environments rather than real-world deployments.
- Value-regular status functions are required for Markovian memory augmentation; unbounded returns are not value-regular.
Experimental setup
Datasets: simulated doughnut allocation environment simulated lending environment (adapted from dynamic lending environment)
Benchmarks: simulated doughnut allocation simulated lending
Metrics: accumulated Nash welfare accumulated relaxed demographic parity score number of doughnuts not wasted sample efficiency
Baselines: Full memory DQN Min memory DQN RNN (GRU) DQN Reset Oracle Random
Builds on: Q-learning DQN CRM (counterfactual reward machines) Nash welfare
Closest papers by meaning
- Adapting Static Fairness to Sequential Decision-Making: Bias Mitigation Strategies towards Equal Long-term Benefit Rate (ICML 2024 · similarity 0.91)
- A Causal Lens for Learning Long-term Fair Policies (ICLR 2025 · similarity 0.90)
- Fair Participation via Sequential Policies (AAAI 2024 · similarity 0.89)
- Fair Off-Policy Learning from Observational Data (ICML 2024 · similarity 0.87)
- Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback (ICML 2025 · similarity 0.86)
- FairDICE: Fairness-Driven Offline Multi-Objective Reinforcement Learning (NeurIPS 2025 · similarity 0.85)
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.