Introduction
In traditional linear multi-armed bandit (MAB) problems, an agent selects an arm (feature vector) and receives a stochastic reward, aiming to maximize the cumulative return. However, real-world rewards are often "corrupted" by factors that should be ignored, such as sensitive attributes in recommendation systems or confounding medications in clinical trials. This paper introduces a "projection reward" framework where the objective is to maximize the component of the reward projected onto a target subspace $U$, even though this "clean" reward is never directly observed.
The GENTRY Algorithm
To address this challenge, the authors propose GENTRY (Greedy projEc tioN sTRategY). Unlike standard approaches that might simply drop features—potentially introducing bias—GENTRY maintains a full model of the environment and uses projection logic to isolate the desired reward components.
Methodology
GENTRY operates on an $\epsilon$-greedy principle. It employs $L_2$ regularized least squares to estimate the global parameter vector $\theta$ from observed, corrupted returns. Instead of maximizing the total expected return, the algorithm projects the estimate $\hat{\theta}$ onto the target subspace $U$ to calculate an empirical average projection reward for each arm.
The algorithm balances exploration and exploitation using a time-varying parameter $\epsilon_t$. With probability $1-\epsilon_t$, it selects the arm maximizing the estimated projection reward. With probability $\epsilon_t$, it explores by choosing a random arm from a set of linearly independent arms $\mathbb{D}_k$. The authors prove that GENTRY achieves sublinear regret: $O(|D| \log n)$ for finite arm sets and $O(n^{2/3} (\log n)^{1/2})$ for infinite compact sets, potentially reaching $O(d\sqrt{n})$ under smoothness assumptions.
Experimental Evaluation
The researchers evaluated GENTRY against synthetic and real-world datasets.
Synthetic Simulations
In environments with both finite and infinite arm sets, GENTRY significantly outperformed standard strategies like the Uncertainty Ellipsoid (UE) and "Careless" Greedy strategies. While baselines often suffered from linear regret—continuously making suboptimal choices by chasing corrupted rewards—GENTRY demonstrated sublinear regret, converging toward the "oracle" optimal arm. In finite-arm tests, GENTRY identified the true optimal arm in over 80% of trials, compared to less than 40% for competing methods.
Wine Quality Dataset
Using a real-world dataset of white wine characteristics, the authors simulated corruption by adding a "protected" feature and modifying ratings. GENTRY successfully filtered this artificial bias, maintaining significantly lower cumulative regret than methods that either ignored the corruption or failed to account for the projection.
Conclusion and Future Work
GENTRY demonstrates that it is possible to optimize for an unobservable objective by leveraging the global relationship between features and returns. By projecting out known biases rather than deleting features, the algorithm avoids common pitfalls in discrimination-aware machine learning. A current limitation is the requirement that the target subspace $U$ be known a priori. Future research may explore methods for learning this subspace dynamically alongside arm selection.
Summary updated