Abstract
This paper addresses the challenge of multi-armed bandit (MAB) learning in environments where actions have delayed, long-term impacts on future rewards—a common phenomenon in socially sensitive domains like lending or policing. We introduce a phased-learning algorithm that utilizes forced stabilization to mitigate historical biases. Our approach achieves an order-optimal regret bound of $\tilde{O}(KT^{2/3})$, bridging the gap between sequential decision-making and algorithmic fairness by formalizing how algorithms influence their learning environments.
Introduction
Standard multi-armed bandit algorithms assume that pulling an arm does not fundamentally change its underlying reward distribution. However, in high-stakes, real-world decision-making, this assumption often fails. For instance, if a bank consistently denies loans to a historically disadvantaged group, it restricts their economic mobility, which in turn lowers the group's ability to repay future loans. The algorithm's past actions actively degrade the future "reward" of that group, creating a vicious feedback loop.
Most algorithmic fairness research focuses on static, one-shot decisions. This paper tackles the dynamic, sequential version: designing a learning algorithm that maximizes utility when its own past actions continuously alter the environment's reward structure. The authors prove that ignoring this delayed impact causes standard algorithms like UCB or Thompson Sampling to fail completely, suffering linear regret.
Methodology
To solve this, the authors introduce impact functions into the bandit framework, mathematically encoding how the history of past actions influences current rewards. Their solution follows a two-step approach:
- Action-Dependent Bandits: They first solve a setting where rewards depend only on the current action's probability distribution. By discretizing the continuous action space and using importance weighting, they create a specialized UCB-like algorithm.
- History-Dependent Bandits (The Phased-Learning Template): To handle long-term historical impacts, they introduce a reduction technique that divides the learning horizon into distinct phases.
As illustrated in the figure above, each phase consists of two stages:
- Approaching Stage ($s_a$): The algorithm repeatedly plays the exact same policy (meta-arm). This forces the environment's shifting impact function to stabilize and converge toward the current policy, "washing out" the historical bias of older actions.
- Estimation Stage ($L - s_a$): Once the environment has stabilized, the algorithm collects rewards to estimate the true mean of the action, effectively reducing the complex history-dependent problem back to the simpler action-dependent one.
Key Results
The proposed phased UCB algorithm achieves a sublinear regret bound of $\tilde{O}(KT^{2/3})$, where $K$ is the number of arms and $T$ is the time horizon. The authors prove a matching lower bound of $\Omega(KT^{2/3})$, demonstrating that their algorithm is order-optimal.
Key insights from the study include:
- Standard algorithms are naive: Deploying standard reinforcement learning in socially sensitive domains without accounting for feedback loops mathematically guarantees suboptimal and likely unfair outcomes.
- Forced stabilization: Taming a chaotic, history-dependent environment is possible by holding actions constant for a set period.
- Empirical Performance: In synthetic simulations, the proposed algorithm consistently outperformed state-of-the-art non-stationary bandit baselines (like Discounted UCB and Sliding-Window UCB), especially when the environment was highly sensitive to recent actions.
Limitations and Future Work
The theoretical guarantees rely on the assumption that reward functions are Lipschitz continuous and that the environment's impact function reliably converges when a policy is repeated. Additionally, the algorithm requires an upper-bound estimate of the environment's time-discounting factor.
Future work may extend these techniques to explicitly incorporate hard fairness constraints, such as demographic parity, ensuring algorithms actively repair rather than exploit historical biases.
Summary updated