🤖 AI

Past-Discounting is Key for Learning Markovian Fairness with Long Horizons

This paper introduces a past-discounting framework for temporal fairness in multi-agent systems that overcomes the scalability limitations of perfect-recall methods by guaranteeing a bounded, horizon-independent state space, thereby enabling the tractable learning of fair policies over arbitrarily long horizons.

Original authors: Ashwin Kumar, William Yeoh

Published 2026-02-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ashwin Kumar, William Yeoh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Infinite Backpack"

Imagine you are a manager in charge of handing out limited resources (like pizza slices or taxi rides) to a group of people every day. Your goal is to be fair.

For a long time, computer scientists tried to solve this in two ways, both of which had major flaws:

The "Forgetful" Manager (Instantaneous Fairness): This manager only looks at today. "Who needs pizza right now? Give it to them!" They ignore what happened yesterday or last week.
- The Result: Over a year, one person might get 100 slices while another gets none, even though they started with equal needs. The manager is fair today, but creates huge inequality over time.
The "Perfect Memory" Manager (Perfect-Recall Fairness): This manager remembers everything. They keep a running tally of every single slice given to every person since the beginning of time. "Bob got 50 slices last year, so he gets none today to catch Alice up."
- The Result: This sounds fair, but it creates a computational nightmare. As time goes on, the list of numbers the manager has to track gets longer and longer. Eventually, the list becomes so huge that the computer crashes or gets so slow it can't make decisions anymore. It's like trying to carry a backpack that gets heavier every second; eventually, you can't walk at all.

The Solution: The "Fading Memory" Manager

The authors of this paper propose a third way, inspired by how humans actually think. We know that humans naturally forget or devalue things that happened a long time ago. If you were treated unfairly 10 years ago, it matters less to you today than if it happened yesterday.

They introduce Past-Discounting.

Imagine the manager has a "memory dial."

Yesterday's events are remembered clearly (100% weight).
Last week's events are remembered a bit less (maybe 90% weight).
Last year's events are very faint (maybe 10% weight).

This is like a fading photograph. The older the photo, the blurrier it gets. The manager still cares about the past, but the "noise" of ancient history fades away, allowing them to focus on the present and the recent past.

Why This is a Game-Changer

The paper proves two main things about this "Fading Memory" approach:

It Keeps the Backpack Light: Because the old memories fade away, the manager never has to carry an infinite list of numbers. The "backpack" stays a manageable, fixed size, no matter how many years pass. This means computers can actually learn to be fair over very long periods without crashing.
It Learns Better: The authors ran computer simulations (using a method called Reinforcement Learning) to test this.
- The "Perfect Memory" computer worked fine for short games (100 steps) but failed miserably when the game got long (10,000 steps) because it got overwhelmed by data.
- The "Fading Memory" computer succeeded in both short and long games. It learned to balance the scales effectively without getting stuck.

The "Half-Life" Analogy

The paper introduces a concept called Half-Life to help tune this memory. Think of it like a radioactive element that decays.

If you set the "decay" to be fast, you forget the past quickly (good for quick decisions, bad for long-term fairness).
If you set the "decay" to be slow, you remember the past for a long time (good for long-term fairness, but you need to be careful not to get bogged down).

The authors show that there is a "sweet spot" where the memory is long enough to fix past mistakes but short enough to keep the computer running smoothly.

Summary

In short, this paper argues that to be truly fair over a long time, you can't just look at the present (which is too short-sighted), and you can't remember everything perfectly (which breaks the computer). Instead, you should use a smart, fading memory that weighs recent events heavily and lets ancient history fade into the background. This makes it possible for AI systems to learn fair behavior in complex, long-running situations like ride-sharing, vaccine distribution, or aid allocation.

Technical Summary: Past-Discounting for Learning Markovian Fairness with Long Horizons

1. Problem Statement

Dynamic resource allocation in multi-agent systems requires balancing efficiency with fairness over long time horizons. Existing approaches face a fundamental dilemma:

Myopic (Instantaneous) Fairness: Evaluates fairness based solely on the current allocation step. While computationally simple, it ignores historical context, leading to cumulative inequities over time.
Perfect-Recall Fairness: Tracks the complete sum of all past utilities to ensure long-term equity. While theoretically equitable, this approach introduces a critical failure mode: the augmented state space required to track cumulative utilities grows unboundedly with the time horizon. This state explosion renders reinforcement learning (RL) algorithms computationally intractable and prevents convergence on fair policies in long-horizon settings.

The core challenge is to design a memory mechanism that preserves the Markov property (allowing for tractable learning) while maintaining a bounded, horizon-independent state space, without sacrificing the ability to reason about historical inequalities.

2. Methodology

The authors propose Past-Discounted Fairness, a framework inspired by behavioral economics and moral psychology, which posit that human fairness judgments naturally discount distant events. The methodology involves three key components:

A. Discounted-Recall Memory Mechanisms
Instead of summing all past utilities ( $Z_t = \sum u_\tau$ ), the framework applies a tunable discount factor $\gamma_p \in [0, 1]$ to historical utilities. Two specific formulations are defined:

Additive Discounted Recall: The memory state is updated as $Z_t = \gamma_p Z_{t-1} + u_t$ . Here, $\gamma_p=0$ reduces to instantaneous fairness, and $\gamma_p=1$ recovers perfect recall.
Averaged Discounted Recall: Both the accumulated utility and the effective time denominator are discounted, ensuring the memory state remains bounded even when averaging.

B. Theoretical Analysis of State Space
The paper provides rigorous proofs comparing the state space properties of different paradigms:

Perfect Recall (Additive): Theorem 3 proves that the state space grows linearly with the time horizon $t$ per coordinate and exponentially with the number of agents $n$ . This leads to an unbounded state space, making fixed-resolution discretization impossible for long horizons.
Perfect Recall (Averaged): Theorem 5 shows that while the average utility value is bounded, maintaining the Markov property requires carrying the time index $t$ (or an equivalent denominator) as part of the state, which is still unbounded.
Past-Discounted (Additive & Averaged): Theorems 4 and 6 prove that with $\gamma_p < 1$ , the memory state $Z_t$ is uniformly bounded by $u_{max} / (1 - \gamma_p)$ . Crucially, the augmented state space size becomes independent of the time horizon, satisfying the conditions for tractable learning.

C. Control Theory Connection
The authors extend the analysis by modeling fairness memory as a Linear Time-Invariant (LTI) system. They demonstrate that for the memory state to remain bounded, the spectral radius of the memory transition matrix must be less than one ( $\rho(A) < 1$ ). Perfect recall corresponds to an identity matrix ( $\rho=1$ ), which is unstable, whereas past-discounting corresponds to a scaled identity ( $\rho = \gamma_p < 1$ ), guaranteeing stability.

D. Half-Life and Effective Window
To aid practitioners in selecting $\gamma_p$ , the paper introduces the concept of "half-life" ( $t_{1/2}$ ) and "effective window" ( $W_{eff} = 1/(1-\gamma_p)$ ). These metrics quantify how many past steps meaningfully influence the current fairness evaluation, allowing for a principled trade-off between memory depth and computational feasibility.

3. Experimental Results

The authors empirically validate their theory using a Multi-Agent Reinforcement Learning (MARL) setup with a Proximal Policy Optimization (PPO) agent in a dynamic resource allocation environment (10 agents, 2 resources per step).

Setup: Agents were trained over varying horizons ( $T=100$ to $T=10,000$ ) under three memory configurations: Myopic ( $\gamma_p=0$ ), Perfect-Recall ( $\gamma_p=1$ ), and Past-Discounted ( $\gamma_p \in \{0.9, 0.99, 0.999\}$ ).
Findings:
- Myopic Agents: Failed to learn fair policies, resulting in high inequality (high Gini coefficient) due to the lack of historical context.
- Perfect-Recall Agents: Performed well on short horizons ( $T \le 500$ ) but suffered a catastrophic performance collapse as the horizon increased. At $T=10,000$ , their ability to maintain fairness degraded to the level of myopic agents, confirming the theoretical prediction of state-space explosion hindering convergence.
- Past-Discounted Agents: Successfully learned robust fair policies across all horizons. The bounded state representation allowed the PPO algorithm to converge.
- Parameter Sensitivity: The optimal $\gamma_p$ depended on the fairness signal density. For dense signals (Nash Welfare), a shorter memory ( $\gamma_p=0.9$ ) sufficed. For sparse signals (Egalitarian Welfare), a longer memory ( $\gamma_p=0.99$ ) was required to accumulate sufficient information.

4. Key Contributions

Identification of a Failure Mode: The paper formally identifies and proves that perfect-recall fairness causes unbounded state-space growth, rendering long-horizon learning intractable.
Novel Framework: It proposes Past-Discounted Fairness, a behaviorally-grounded framework that interpolates between instantaneous and perfect-recall fairness using a geometrically decaying weight.
Theoretical Guarantees: It provides proofs that past-discounting guarantees a bounded, horizon-independent augmented state space, thereby restoring the Markov property while ensuring computational tractability.
Empirical Validation: It demonstrates that RL agents using past-discounting can learn fair policies over arbitrarily long horizons, whereas agents using perfect recall fail as the horizon extends.

5. Significance and Claims

The paper claims that past-discounting is not merely a heuristic but a practical necessity for building scalable and equitable resource allocation systems. By ensuring the state space remains bounded and horizon-independent, the framework unlocks the ability to learn fair policies tractably in long-horizon settings where traditional perfect-recall methods fail.

The authors position this work as a "third paradigm" that occupies the practical middle ground between the computational simplicity of myopic fairness and the theoretical equity (but computational infeasibility) of perfect recall. The significance lies in providing a principled mechanism to manage the trade-off between immediate outcomes and historical context, grounded in both behavioral insights and rigorous control-theoretic stability conditions.