Abstract
We consider the stochastic contextual bandit problem with additional regularization. The motivation comes from problems where the policy of the agent must be close to some baseline policy which is known to perform well on the task. To tackle this problem we use a nonparametric model and propose an algorithm splitting the context space into bins, and solving simultaneously - and independently - regularized multi-armed bandit instances on each bin. We derive slow and fast rates of convergence, depending on the unknown complexity of the problem. We also consider a new relevant margin condition to get problem-independent convergence rates, ending up in intermediate convergence rates interpolating between the aforementioned slow and fast rates.
Introduction
In standard contextual bandit problems, an agent observes a context, selects an action, and receives a reward, with the goal of maximizing cumulative rewards. However, in sensitive domains like medicine or finance, purely exploratory behavior can be risky. This paper introduces a framework for regularized contextual bandits, where the agent's objective is modified to include a convex regularization term (e.g., Entropy or KL-Divergence). This ensures the learned policy remains close to a pre-defined baseline policy—a set of rules known to be safe or effective—while still allowing for performance improvements.
Methodology
The authors propose a nonparametric approach that avoids assuming a linear relationship between contexts and rewards. The strategy relies on three main components:
- Context Binning: The $d$-dimensional context space is partitioned into cubic bins. Within each bin, the problem is treated as a localized multi-armed bandit instance.
- Upper-Confidence Frank-Wolfe (UC-FW): Within each bin, the algorithm employs a projection-free optimization method adapted for bandits. This is particularly effective for handling convex regularization terms.
- Pre-sampling Stage: For regularization functions that exhibit "explosive" gradients at the boundaries (like entropy), a brief initial exploration phase ensures the estimated policy stays within the interior of the decision space where the optimization is well-behaved.
Theoretical Convergence Rates
A core contribution of this work is the derivation of convergence rates that bridge the gap between standard bandit theory and nonparametric estimation. The authors identify two primary regimes:
- Slow Rates: When regularization is weak, the regret bound is $O(T^{-\beta/(2\beta+d)})$, matching standard nonparametric contextual bandit results.
- Fast Rates: Under strong convexity and specific boundary conditions, the algorithm achieves a "fast" rate of $O(T^{-2\beta/(2\beta+d)})$. This matches the minimax rates for nonparametric estimation, which is typically faster than pure optimization rates.
These rates depend on the smoothness parameter $\beta$ of the reward functions and the dimension $d$ of the context space. The authors also introduce a "margin condition" that allows for intermediate rates, interpolating between these two extremes based on how often the optimal policy sits near the decision boundaries.
Empirical Validation
The theoretical exponents were validated through synthetic simulations using various reward distributions (Poisson, Exponential, Bernoulli) and $\beta$-Hölder smooth mean functions. The results confirm that as the smoothness parameter $\beta$ increases, the regret decreases in accordance with the derived formulas.
As shown in the figure above, when the regret $R(T)$ is normalized by the predicted theoretical rate, the curves for different $\beta$ values flatten as $T$ increases, indicating that the empirical performance matches the predicted convergence behavior.
Conclusion and Future Work
This work demonstrates that regularization not only provides safety by adhering to baseline policies but can also accelerate learning by transforming the bandit problem into one that resembles nonparametric estimation. While the current binning approach is effective, it suffers from the "curse of dimensionality" as $d$ increases. Future research may explore adaptive partitioning (like decision trees) to handle high-dimensional context spaces more efficiently and methods to dynamically learn the optimal regularization strength.
Summary updated