Bandit Learning with Delayed Impact of Actions

Abstract

We consider a stochastic multi-armed bandit (MAB) problem with delayed impact of actions. In our setting, actions taken in the past impact the arm rewards in the subsequent future. This delayed impact of actions is prevalent in the real world. For example, the capability to pay back a loan for people in a certain social group might depend on historically how frequently that group has been approved loan applications. If banks keep rejecting loan applications to people in a disadvantaged group, it could create a feedback loop and further damage the chance of getting loans for people in that group. In this paper, we formulate this delayed and long-term impact of actions within the context of multi-armed bandits. We generalize the bandit setting to encode the dependency of this "bias" due to the action history during learning. The goal is to maximize the collected utilities over time while taking into account the dynamics created by the delayed impacts of historical actions. We propose an algorithm that achieves a regret of $\tilde{\mathcal{O}}(K{T}^{2/3})$ and show a matching regret lower bound of $\Omega (K{T}^{2/3})$, where $K$ is the number of arms and $T$ is the learning horizon. Our results complement the bandit literature by adding techniques to deal with actions with long-term impacts and have implications in designing fair algorithms.

References in corpus (16)

• Contextual Bandits with Similarity Information
• A Short-term Intervention for Long-term Fairness in the Labor Market
• Combinatorial Bandits Revisited
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Asymptotically optimal priority policies for indexable and nonindexable restless bandits
• Online Learning with an Unknown Fairness Metric
• Combinatorial Multi-Armed Bandit with General Reward Functions
• Bandits with Delayed, Aggregated Anonymous Feedback
• Regret Bounds for Restless Markov Bandits
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
• Stochastic Bandit Models for Delayed Conversions
• On the Long-term Impact of Algorithmic Decision Policies: Effort Unfairness and Feature Segregation through Social Learning
• Human Interaction with Recommendation Systems
• Group Retention when Using Machine Learning in Sequential Decision Making: the Interplay between User Dynamics and Fairness
• Stochastic bandits with arm-dependent delays
• Discrepancy-Based Algorithms for Non-Stationary Rested Bandits

Cited by in corpus (2)

• How Do Fair Decisions Fare in Long-term Qualification?
• Unintended Selection: Persistent Qualification Rate Disparities and Interventions