Abstract
We study contextual bandit learning for any competitor policy class and continuous action space. We obtain two qualitatively different regret bounds: one competes with a smoothed version of the policy class under no continuity assumptions, while the other requires standard Lipschitz assumptions. Both bounds exhibit data-dependent “zooming" behavior and, with no tuning, yield improved guarantees for benign problems. We also study adapting to unknown smoothness parameters, establishing a price-of-adaptivity and deriving optimal adaptive algorithms that require no additional information.
Introduction
Contextual bandit learning is a fundamental framework for sequential decision-making where an agent observes a context, selects an action, and receives a loss. While discrete action spaces are well-studied, many real-world applications—such as dynamic pricing or robotic control—involve continuous action spaces. Traditional approaches to continuous actions often rely on global Lipschitz assumptions, which assume that similar actions yield similar losses. However, these assumptions frequently fail in practice where loss functions can be discontinuous or highly irregular.
The Smoothing Paradigm
This paper introduces a robust framework that shifts the focus from competing with the single best action to competing with "smoothed" distributions of actions. By mapping every action $a$ to a distribution (e.g., a uniform distribution over a small interval $[a-h, a+h]$), the learner interacts with a smoothed version of the environment. This approach provides several advantages:
- Robustness to Discontinuity: The loss function effectively becomes well-behaved even if the underlying raw losses are jagged.
- Policy-Based Scaling: Unlike prior methods that struggle with high-dimensional contexts, this framework scales with the complexity of the policy class ($\log |\Pi|$), allowing for the use of sophisticated models like neural networks.
Zooming and Adaptivity
The proposed algorithms exhibit "zooming" behavior, adaptively focusing samples on regions of the action space that yield lower losses without requiring pre-discretization. A significant contribution of this work is the development of algorithms that adapt to unknown smoothness parameters ($h$ or $L$). The authors identify a fundamental "price of adaptivity"—a necessary increase in regret when the smoothness constant is unknown—and provide algorithms that achieve optimal adaptive rates.
Key Results
The theoretical guarantees of the proposed framework are summarized in terms of regret bounds across various settings, ranging from worst-case scenarios to data-dependent instances.
As shown in the table above, for a fixed bandwidth $h$, the algorithms achieve a smoothed regret bound of $\Theta(\sqrt{T/h})$ without any continuity assumptions. In the Lipschitz setting with an unknown parameter $L$, the adaptive regret is $\Theta(T^{2/3}\sqrt{L})$. Furthermore, the algorithms are instance-optimal, providing improved "data-dependent" bounds for easier problems where optimal actions are clearly separated.
Conclusion and Future Work
While this work establishes strong statistical limits and provides a unified algorithmic approach, practical implementation for very large policy classes remains a computational challenge. Future research may explore extending the smoothing intuition to more complex, high-dimensional action spaces and addressing scenarios with delayed or partially masked feedback.
Summary updated