Effective Dimension in Bandit Problems under Censorship

Gauthier Guinet, Saurabh Amin, Patrick Jaillet

Abstract

In this paper, we study both multi-armed and contextual bandit problems in censored environments. Our goal is to estimate the performance loss due to censorship in the context of classical algorithms designed for uncensored environments. Our main contributions include the introduction of a broad class of censorship models and their analysis in terms of the effective dimension of the problem -- a natural measure of its underlying statistical complexity and main driver of the regret bound. In particular, the effective dimension allows us to maintain the structure of the original problem at first order, while embedding it in a bigger space, and thus naturally leads to results analogous to uncensored settings. Our analysis involves a continuous generalization of the Elliptical Potential Inequality, which we believe is of independent interest. We also discover an interesting property of decision-making under censorship: a transient phase during which initial misspecification of censorship is self-corrected at an extra cost, followed by a stationary phase that reflects the inherent slowdown of learning governed by the effective dimension.

Introduction

In standard multi-armed bandit (MAB) or linear contextual bandit (LCB) problems, the agent typically observes a reward for every action taken. However, real-world applications—ranging from clinical trials to recommendation systems—often involve censored feedback, where rewards are stochastically missing. This censorship creates an endogenous dependency: past actions determine what information is gathered, which in turn dictates future strategy. This paper addresses how censorship reshapes the learning process and quantifies the resulting performance loss using the concept of Effective Dimension ($d_{eff}$).

Methodology

The study focuses on the performance of the Upper Confidence Bound (UCB) class of algorithms in censored environments.

The Generic UCB Framework

The analysis centers on a generic UCB design that relies on regularized reward estimators $\tilde{r}_t^\lambda$. The regularizer is primarily used to prevent artificial cold-start exploratory phases.

Algorithm 1: Generic UCB framework used to analyze regret under censorship.

Censorship Models and Effective Dimension

The authors define a general framework where each action $a$ has a probability $p(a)$ of being observed.

  1. Multi-Armed Bandits: $d_{eff}$ is defined as the sum of the reciprocals of observation probabilities: $\sum 1/p_a$.
  2. Linear Contextual Bandits: The authors introduce a Multi-Threshold (MT) model. Here, censorship depends on the "radial" direction of the action, mimicking scenarios where agents with private valuations decide whether to adopt a recommendation.
Multi-Threshold (MT) censorship model illustrating how observation probability p(a) varies with the action's direction.

A key theoretical innovation is the Continuous Elliptical Potential Inequality. By treating discrete decision steps as a smooth integral, the authors provide a more tractable way to bound information gain under censorship.

Key Theoretical Insights

Censorship as Dimensional Dilation

A primary finding is that censorship does not fundamentally break bandit algorithms; instead, it "dilates" the problem. A $d$-dimensional problem under censorship behaves statistically like a higher-dimensional uncensored problem.

The Transient Phase

The learning process under censorship exhibits two distinct phases:

  • Transient Phase: An initial period where any misspecification of the censorship model is self-corrected by the algorithm at an additional cost.
  • Stationary Phase: A subsequent phase where learning slows down according to the effective dimension $d_{eff}$.

Results: Regret Bounds

The paper provides rigorous regret bounds characterizing the slowdown in learning:

  • Multi-Armed Bandits: Expected regret scales as $\tilde{O}(\sigma \sqrt{d_{eff} T})$, confirming that the cost of censorship is proportional to the square root of the effective dimension.
  • Linear Contextual Bandits: Regret scales as $\tilde{O}(\sigma \sqrt{d \cdot d_{eff} T})$, where $d$ is the original dimension and $d_{eff}$ represents the dilation from multi-threshold censorship.

These results show that if an arm is observed only 10% of the time ($p=0.1$), the effective dimension for that arm effectively increases by a factor of 10, leading to a predictable $\sqrt{10}$ slowdown.

Conclusion and Future Work

This work establishes that classical UCB algorithms can be used in censored environments with predictable performance degradation. While the current analysis assumes data is "Missing Completely at Random" (MCAR) conditional on the action, future research could explore scenarios where rewards themselves influence censorship (e.g., strategic feedback). Extending this framework to Bayesian settings and Markov Decision Processes (MDPs) remains a promising direction for understanding complex human-AI interaction loops.

Summary updated

Abstract

In this paper, we study both multi-armed and contextual bandit problems in censored environments. Our goal is to estimate the performance loss due to censorship in the context of classical algorithms designed for uncensored environments. Our main contributions include the introduction of a broad class of censorship models and their analysis in terms of the effective dimension of the problem -- a natural measure of its underlying statistical complexity and main driver of the regret bound. In particular, the effective dimension allows us to maintain the structure of the original problem at first order, while embedding it in a bigger space, and thus naturally leads to results analogous to uncensored settings. Our analysis involves a continuous generalization of the Elliptical Potential Inequality, which we believe is of independent interest. We also discover an interesting property of decision-making under censorship: a transient phase during which initial misspecification of censorship is self-corrected at an extra cost, followed by a stationary phase that reflects the inherent slowdown of learning governed by the effective dimension. Our results are useful for applications of sequential decision-making models where the feedback received depends on strategic uncertainty (e.g., agents' willingness to follow a recommendation) and/or random uncertainty (e.g., loss or delay in arrival of information).
BibTeX
@inproceedings{guinet2022effective,
  author = {Gauthier Guinet and Saurabh Amin and Patrick Jaillet},
  title = {{Effective Dimension in Bandit Problems under Censorship}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=PNqITXWmOo},
}
Figure