← All publications
BETA This research page is an early version. Explanatory text, figure selection, and presentation are still being revised.
UAI 2025

Multi-armed Bandits with Missing Outcomes

Ilia Mahrooghi · Mahshad Moradi · Sina Akbari · Negar Kiyavash
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence · 2025
Paper GitHub UAI / PMLR
Keywords.
multi-armed bandits missing data online learning regret

TL;DR.

Missing rewards can fundamentally change a multi-armed-bandit problem. We analyze regret under missing completely at random, missing at random, and missing not at random mechanisms, show how naive reward estimates can lead to linear regret, and design UCB-style algorithms that explicitly correct for the observation process.

Why this matters.

Real feedback is often selectively missing—in clinical trials, recommendation systems, advertising, and other online decisions. The paper provides a principled way to keep learning when the rewards we fail to observe are not a representative sample of the rewards that actually occurred.

Abstract

While significant progress has been made in designing algorithms that minimize regret in online decision-making, real-world scenarios often introduce additional complexities, with missing outcomes perhaps among the most challenging ones. Overlooking this aspect or simply assuming random missingness invariably leads to biased estimates of the rewards and may result in linear regret. Despite the practical relevance of this challenge, no rigorous methodology currently exists for systematically handling missingness, especially when the missingness mechanism is not random. In this paper, we address this gap in the context of multi-armed bandits (MAB) with missing outcomes by analyzing the impact of different missingness mechanisms on achievable regret bounds. We introduce algorithms that account for missingness under both missing at random (MAR) and missing not at random (MNAR) models. Through both analytical and simulation studies, we demonstrate the drastic improvements in decision-making by accounting for missingness in these settings.

Main message. Missing outcomes are part of the decision problem, not a preprocessing nuisance. Modeling the observation mechanism restores unbiased reward learning and dramatically improves regret.

The paper at a glance

An informal guide to the problem, the idea, and the main results.

multi-armed bandits missing rewards online learning regret analysis

1. The problem

Classical bandit algorithms assume that after pulling an arm, the reward is observed. In many applications that is false: the outcome may be censored, delayed, or selectively missing, and naive bandit updates can then become biased.

2. The key idea

We treat missingness as part of the bandit model. That lets us derive the right regret guarantees under different observation mechanisms and design algorithms that account for the missingness process.

3. Missingness changes regret

Theory

We characterize how different missingness mechanisms alter reward estimation and achievable regret. In particular, ignoring outcome-dependent missingness can bias estimated rewards enough to produce linear regret.

4. Missingness-aware bandit algorithms

Theory + algorithm

We develop UCB-style algorithms for MCAR, MAR, and MNAR settings. The MAR construction uses an observed mediator to recover unbiased reward information, while the MNAR method handles reward-dependent observation through the additional structure developed in the paper.

5. How it works

  1. Formalize how rewards become missing.
  2. Analyze how the observation mechanism changes the information available to the learner.
  3. Design an algorithm that corrects for or adapts to that missingness structure.
  4. Prove regret bounds and compare with naive baselines.

What the simulations show

Main empirical message.

The simulations mirror the theory. In the MAR environment, standard UCB exhibits near-linear cumulative regret because it ignores the biased observation process, while the missingness-aware MAR algorithm achieves much lower regret. The MNAR algorithm also adapts successfully in reward-dependent missingness settings, and additional mediator information improves performance when available.

Where this helps

Good fit

  • You face online decision problems with selectively missing or censored rewards.
  • You want regret guarantees that explicitly account for the observation process.
  • You suspect the missingness pattern itself carries information about arm quality.

Keep in mind

  • The framework covers MCAR, MAR, and MNAR rather than treating all missing feedback as random censoring.
  • The mediator-based formulation gives a concrete way to use auxiliary information to recover useful reward estimates even when missingness depends on the outcome.

Cite this paper

@InProceedings{pmlr-v286-mahrooghi25a,
  title     = {Multi-armed Bandits with Missing Outcomes},
  author    = {Mahrooghi, Ilia and Moradi, Mahshad and Akbari, Sina and Kiyavash, Negar},
  booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence},
  pages     = {2844--2875},
  year      = {2025},
  volume    = {286},
  series    = {Proceedings of Machine Learning Research},
  publisher = {PMLR},
  url       = {https://proceedings.mlr.press/v286/mahrooghi25a.html}
}