Abstract
We investigate contextual online learning with nonparametric (Lipschitz) comparison classes under different assumptions on losses and feedback information. For full information feedback and Lipschitz losses, we design the first explicit algorithm achieving the minimax regret rate (up to log factors). In a partial feedback model motivated by second-price auctions, we obtain algorithms for Lipschitz and semi-Lipschitz losses with regret bounds improving on the known bounds for standard bandit feedback. Our analysis combines novel results for contextual second-price auctions with a novel algorithmic approach based on chaining. When the context space is Euclidean, our chaining approach is efficient and delivers an even better regret bound.
Introduction
In the realm of online learning, an agent must make a sequence of decisions (actions) based on evolving environments (contexts) to minimize "regret"—the cumulative difference between their realized loss and the loss of the best fixed strategy in hindsight. When the set of possible strategies is "nonparametric" (e.g., the class of all Lipschitz functions), identifying the optimal strategy is a significant challenge.
This research addresses two critical gaps in the existing literature:
- The Constructive Gap: While theoretical minimax regret rates for full-information settings were known to exist, previous proofs were non-constructive. This work introduces the first explicit, computationally efficient algorithm to achieve these rates.
- The Feedback Gap: Most research focuses on either "full information" (observing losses for all actions) or "bandit feedback" (observing only the loss for the chosen action). Real-world scenarios, such as reserve price optimization in digital auctions, often operate in a "one-sided" feedback regime that provides more information than a bandit but less than full information.
Algorithmic Chaining: A Blueprint for Learning
The primary innovation of this work is Algorithmic Chaining. Traditionally, "chaining" is a mathematical technique used to derive bounds on stochastic processes. The authors transform this analytical tool into a structural blueprint for online learning algorithms.
Hierarchical Tree Architecture
Instead of selecting from a flat list of policies, the algorithm organizes the policy space into a hierarchical tree. Each node in the tree represents a "bin" of similar policies.
- Nested Learners: Every internal node hosts its own online learning algorithm (such as Hedge or Exp4), treating its child nodes as experts.
- Local Regret Scaling: As the tree branches out and becomes finer, the "local" loss range at each node decreases. This allows the algorithm to focus on the optimal policy while maintaining tight control over cumulative regret.
- Computational Efficiency: To prevent exponential growth of the tree, the authors employ a wavelet-like dyadic discretization for Euclidean spaces, ensuring the algorithm operates in polynomial time.
The Power of One-Sided Feedback
The authors demonstrate that second-price auctions provide a specific type of structured feedback: if a seller sets a reserve price and the item sells, they can infer the outcome for any higher reserve price. This "one-sided" information is leveraged through chaining to achieve regret bounds that significantly outperform standard bandit algorithms.
Key Results and Regret Bounds
The paper establishes a suite of new regret bounds across various feedback models, where $T$ represents the number of rounds and $d$ is the context dimension.
Key achievements include:
- Full Information: Achieving the minimax rate of $\tilde{O}(T^{(d-1)/d})$ with the explicit HierHedge algorithm.
- One-Sided Feedback: Improving the general regret bound to $\tilde{O}(T^{d/(d+1)})$ and further to $\tilde{O}(T^{(d-1/3)/(d+2/3)})$ for efficient Euclidean versions.
- Second-Price Auctions: Proving a regret bound of $\tilde{O}(T^{(d+1)/(d+2)})$ for seller revenue, even under semi-Lipschitz loss conditions.
Conclusion and Future Work
This research bridges the gap between theoretical existence proofs and practical algorithmic implementation in nonparametric online learning. While the current efficient "wavelet-like" approach is optimized for Euclidean spaces ($[0, 1]^d$), adapting these techniques to more complex metric spaces remains an open challenge. Additionally, while the regret bounds are optimal, they are subject to the "curse of dimensionality," where performance degrades as the dimension $d$ of the context space increases. Future work may explore the application of algorithmic chaining to other structured feedback environments, such as those found in social network interactions.
Note: This is a theoretical research paper focused on mathematical guarantees; no empirical datasets were used for training or evaluation.
Summary updated