Online Nonparametric Learning, Chaining, and the Role of Partial Feedback

Nicolò Cesa-Bianchi, Pierre Gaillard, Claudio Gentile, Sébastien GerchinovitzarXiv 2017 · OpenReview

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:

  1. 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.
  2. 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.
Example of a loss function in the one-sided feedback model, typical of second-price auctions.

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.

Summary of regret upper bounds across different feedback models and loss function classes.

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

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.
BibTeX
@misc{cesabianchi2017online,
  author = {Nicolò Cesa-Bianchi and Pierre Gaillard and Claudio Gentile and Sébastien Gerchinovitz},
  title = {{Online Nonparametric Learning, Chaining, and the Role of Partial Feedback}},
  year = {2017},
  eprint = {1702.08211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.08211},
}
Figure