Introduction
In contextual multi-arm bandit (MAB) problems, a decision-maker observes a context (e.g., user demographics) and selects an action or "arm" (e.g., a product recommendation) to maximize a reward. When the action space is massive, learning the reward for every single arm independently becomes impossibly slow. To circumvent this, researchers typically assume an underlying structure: if two arms are "close" within a predefined metric space, their expected rewards should be similar.
However, in real-world applications, the "true" metric governing these similarities is rarely known. Is a user who likes sci-fi movies "closer" to a horror fan or a documentary buff? If an algorithm relies on an incorrect metric, its performance degrades significantly. This paper tackles the challenge of nonparametric contextual bandits in an unknown metric space, introducing Approx-Zooming—a novel algorithm that learns hidden relationships between arms on the fly from reward data alone.
The Approx-Zooming Algorithm
The authors propose Approx-Zooming, which builds upon the classic "Zooming" algorithm by introducing a data-driven similarity estimation layer. The algorithm operates through several key mechanisms:
- Adaptive Partitioning: The algorithm divides the context-arm space into "balls." It begins with a coarse view and adaptively "zooms in" (partitions the space into smaller balls) on regions that yield high rewards.
- Flagging Rule: A partition is "flagged" when the algorithm has collected enough samples such that the statistical variance is smaller than the potential bias introduced by the ball's size.
- Data-Driven Similarity: Once flagged, the algorithm enters a dedicated phase to estimate distances between arms within that specific context interval. It utilizes a $k$-nearest neighbor (k-NN) estimator to approximate the $L_2$ distance between the reward functions of different arms.
- Clustering: Based on these estimated distances, Approx-Zooming clusters similar arms together. This allows the algorithm to share data across arms that behave similarly, effectively reducing the problem's dimensionality.
- UCB Selection: Finally, it employs an Upper Confidence Bound (UCB) approach to balance exploration of new arms and exploitation of known high-reward arms.
Experimental Setup and Key Results
The Zigzag Reward Experiment
The paper evaluates the algorithm using synthetic simulations, specifically testing with 50, 100, and 200 arms. The reward function is designed as a periodic "zigzag." This is a deliberate and clever choice: it creates a scenario where arms that are "far apart" in a simple linear index are actually highly similar in their reward behavior.
As the heatmaps demonstrate, Approx-Zooming successfully learns this complex underlying structure over time, progressively narrowing its selections to the optimal zigzag path across the context intervals.
Simulation Performance
The algorithm's performance was benchmarked against an Oracle with the true reward function, an Oracle with the true similarity metric, and a naive baseline that learns every arm independently.
The results reveal a fascinating trade-off regarding the "cost of learning." Learning the metric requires extra exploration samples upfront, causing a slightly slower start. However, this investment pays massive dividends in the long run. In the 200-arm simulation, Approx-Zooming significantly outperformed the naive independent learner. More importantly, it even surpassed an oracle given a standard metric ($|\theta_a - \theta_{a'}|$). The standard metric failed to account for the periodic nature of the rewards, whereas Approx-Zooming discovered this periodicity purely through data.
Theoretical Guarantees
Beyond empirical success, the authors prove an upper bound on the algorithm's regret. If the "mass" of nearly-optimal arms decreases linearly, Approx-Zooming achieves a regret of $O(\sqrt{KT})$, where $K$ is the number of arms and $T$ is the time horizon. Furthermore, because the algorithm learns distances directly from reward observations, it is entirely metric-agnostic; permuting arm IDs or applying complex transformations to their features does not impact performance.
Limitations and Future Work
While Approx-Zooming presents a significant step forward, it has limitations. The primary analysis and simulations focus on 1D context spaces. In very high dimensions, the number of samples required for the k-NN estimator could become prohibitive. Additionally, the algorithm currently requires knowing or estimating the Lipschitz constant $L$; without it, the partitioning logic becomes difficult to manage.
Future research directions suggested by the authors include generalizing the approach to Hölder continuous functions (a broader class than Lipschitz) and exploring connections to Gaussian Process bandits, where one might empirically estimate a covariance matrix instead of a distance metric.
Summary updated