Abstract
In many real-world decision-making scenarios, the observed reward is a composite of multiple factors, only some of which are desirable to optimize. Standard linear bandit algorithms typically maximize the total reward, which can lead to biased outcomes in applications like fair recommendation systems or clinical trials. This paper introduces the Greedy Projection Strategy (GPS), a framework designed to maximize the reward derived from a specific feature subspace while remaining invariant to "corruption" from orthogonal dimensions. We demonstrate that GPS achieves sublinear regret and provides a robust mathematical foundation for targeted optimization in the presence of nuisance variables.
Introduction
In the standard linear stochastic bandit problem, a decision-maker selects an action (an "arm") and receives a reward that is a linear function of that action's features. However, this total reward often contains components that are irrelevant or even harmful to the objective. For example, a movie recommendation system might observe high click-through rates driven by historical biases related to a user's protected attributes (e.g., race or gender). If the system optimizes for total clicks, it reinforces these biases.
Ideally, the system should optimize only for the "projection reward"—the portion of the reward attributable to legitimate features like movie genre or quality—while ignoring the "corruption reward" stemming from sensitive attributes. The fundamental challenge is that the projection reward is latent; we only observe the sum of the projection, the corruption, and stochastic noise.
Problem Formulation
We model the reward $r_t$ at time $t$ as a linear function of the decision vector $X_t \in \mathbb{R}^d$ and a hidden parameter $\theta \in \mathbb{R}^d$. The reward is decomposed using an orthogonal projection onto a target subspace $U$:
$$r_t = \langle P_U(X_t), P_U(\theta) \rangle + \langle P_{U^\perp}(X_t), P_{U^\perp}(\theta) \rangle + \eta_t$$
Where:
- $P_U$ is the orthogonal projection onto the desired subspace $U$.
- $P_{U^\perp}$ is the projection onto the "corrupting" orthogonal subspace.
- $\eta_t$ is the observation noise.
The goal is to minimize the cumulative projection regret, which measures the difference between the optimal projection reward and the projection reward obtained by the chosen actions over time.
The Greedy Projection Strategy (GPS)
The authors propose the Greedy Projection Strategy (GPS) to navigate this environment. Unlike standard algorithms that optimize for the total estimated reward, GPS isolates the target subspace during the decision-making phase.
1. Estimation via Full Information
Crucially, GPS does not discard the "corrupting" features during the estimation phase. It uses $L_2$-regularized least squares to estimate the global parameter vector $\theta$ using the full decision vector $X_t$. This ensures the estimate remains unbiased. A common pitfall, termed the "Careless Greedy Strategy" (CGS), involves discarding unwanted features before estimation. The authors prove that CGS leads to biased estimates and linear regret because it fails to account for the mathematical contribution of the ignored features to the total observed reward.
2. Decision Rule
GPS employs an $\epsilon_t$-greedy policy. With probability $1 - \epsilon_t$, the algorithm chooses the arm that maximizes the empirical projection reward: $\hat{r}_t^{proj} = \langle P_U(X_t), P_U(\hat{\theta}_t) \rangle$. With probability $\epsilon_t$, it explores by selecting a random arm from a set of $k$ linearly independent decisions to ensure the parameter space is sufficiently covered.
3. Adaptive Exploration
The exploration rate $\epsilon_t$ is tuned based on the nature of the decision set:
- Finite Arm Sets: $\epsilon_t = O(1/t)$, leading to $O(\log T)$ regret.
- Infinite Compact Sets: $\epsilon_t = O(t^{-1/3})$, leading to $O(T^{2/3})$ regret.
Theoretical and Empirical Results
Regret Bounds
The paper establishes that sublinear regret is achievable even when the target reward is never directly observed. For finite arm sets, GPS achieves $O(\log T)$ cumulative projection regret. For infinite compact sets, the regret is $O(T^{2/3} \sqrt{\log T})$. If the decision set satisfies a specific smoothness condition (SBAR), the performance improves further to $O(\sqrt{T})$.
Simulation Performance
Through synthetic simulations involving general orthogonal projections and discrimination-aware masking, GPS was compared against the Uncertainty Ellipsoid (UE) and the Original Greedy Strategy (OGS).
- Accuracy: GPS identified the optimal projected arm in over 80% of trials, significantly higher than the 30-40% accuracy of standard strategies.
- Regret Growth: While UE and OGS suffered from linear regret growth—as they were consistently "distracted" by the corruption reward—GPS maintained a sublinear curve, effectively isolating the desired reward signal.
Discussion and Limitations
A critical requirement for GPS is the Identifiability Assumption: the target subspace $U$ must be contained within the span of the available decision set. If the available actions do not allow the system to "see" the subspace, optimization is impossible.
While GPS provides a powerful framework, some challenges remain:
- Subspace Knowledge: The algorithm assumes the target subspace $U$ is known a priori. In complex social systems, defining the exact boundaries of "bias" versus "legitimate features" is a non-trivial task.
- Linearity: The model assumes a strictly linear relationship. Future work could explore extending this projection framework to generalized linear models or neural bandits to capture non-linear human behaviors.
Conclusion
Orthogonal projection in linear bandits offers a mathematically rigorous way to handle "corrupted" rewards. By decoupling the estimation of the global parameter from the optimization of the target subspace, the Greedy Projection Strategy allows for decision-making that is both effective and aligned with specific values, such as fairness or clinical specificity.
Summary updated