Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization

Thanh Nguyen-Tang, Sunil Gupta, A. Tuan Nguyen, Svetha Venkatesh

Abstract

Offline policy learning (OPL) leverages existing data collected a priori for policy optimization without any active exploration. Despite the prevalence and recent interest in this problem, its theoretical and algorithmic foundations in function approximation settings remain under-developed. In this paper, we consider this problem on the axes of distributional shift, optimization, and generalization in offline contextual bandits with neural networks. In particular, we propose a provably efficient offline contextual bandit with neural network function approximation that does not require any functional assumption on the reward. We show that our method provably generalizes over unseen contexts under a milder condition for distributional shift than the existing OPL works. Notably, unlike any other OPL method, our method learns from the offline data in an online manner using stochastic gradient descent, allowing us to leverage the benefits of online learning into an offline setting. Moreover, we show that our method is more computationally efficient and has a better dependence on the effective dimension of the neural network than an online counterpart. Finally, we demonstrate the empirical effectiveness of our method in a range of synthetic and real-world OPL problems.

Introduction

In many high-stakes domains like healthcare or recommendation systems, active exploration is often prohibited due to safety or cost concerns. Instead, we must rely on Offline Policy Learning (OPL), which aims to extract optimal policies from pre-collected "logged" data. However, OPL faces three significant challenges: distributional shift (the logged data may not cover the optimal policy's actions), optimization (neural networks are non-convex and difficult to optimize globally), and generalization (ensuring the policy works on unseen contexts).

Existing theoretical work often relies on simple linear models or assumes access to an unrealistic "optimization oracle." This paper bridges the gap by introducing NeuraLCB, a provably efficient neural OPL method that handles non-linear rewards and distributional shifts more effectively than previous approaches.

Methods: NeuraLCB

NeuraLCB (Neural Lower Confidence Bound) is built on two core principles:

  1. The Pessimism Principle: To combat distributional shift, NeuraLCB calculates a Lower Confidence Bound (LCB) for rewards. By subtracting an uncertainty term from the predicted reward, the agent avoids taking actions in regions where data is sparse, preventing the "overestimation" trap common in offline learners.
  2. Online-style SGD Training: Unlike batch-optimized methods, NeuraLCB processes data in a "streaming" fashion using Stochastic Gradient Descent (SGD). This allows the algorithm to scale linearly ($O(n)$) with the number of samples, making it significantly more computationally efficient than kernel-based methods ($O(n^2)$).

The theoretical framework utilizes the Neural Tangent Kernel (NTK) to prove that overparameterized networks can generalize well because their "effective dimension" is much smaller than their total parameter count.

Key Results and Theoretical Comparison

NeuraLCB provides a stronger theoretical foundation for neural OPL compared to prior work. As shown in the table below, NeuraLCB achieves a competitive sub-optimality bound while requiring a much milder coverage assumption—empirical Single-Policy Concentration (eSPC)—compared to the uniform coverage required by many linear or tabular methods.

Comparison of theoretical results for various OPL methods.

Empirical Performance

The researchers evaluated NeuraLCB against five baselines, including linear (LinLCB) and kernel-based (KernLCB) methods. In synthetic tasks featuring highly non-linear reward functions (quadratic, quadratic-form, and cosine), NeuraLCB consistently achieved the lowest sub-optimality.

Sub-optimality of NeuraLCB vs. baselines across three non-linear synthetic reward functions.

Key empirical insights include:

  • Pessimism is Essential: "NeuralGreedy" (a neural net without the LCB subtraction) performed significantly worse, often "hallucinating" high rewards in unexplored regions.
  • Efficiency via Streaming: Updating the network on single data points per iteration (S-mode) often outperformed batch training on real-world data, suggesting that online-style updates help prevent overfitting to correlated offline data structures.

Conclusion and Future Work

NeuraLCB represents a significant step forward in making neural OPL both theoretically sound and practically viable. It achieves a sub-optimality bound of $\tilde{O}(\kappa \sqrt{\tilde{d}} \cdot n^{-1/2})$, where $\tilde{d}$ is the effective dimension of the neural network. While the current theory relies on the wide-network NTK regime, the algorithm's strong performance on standard-width networks in practice is encouraging. Future work includes extending these neural pessimism principles to multi-step Offline Reinforcement Learning and addressing hyperparameter sensitivity in uncertainty estimation.

Summary updated

Abstract

Offline policy learning (OPL) leverages existing data collected a priori for policy optimization without any active exploration. Despite the prevalence and recent interest in this problem, its theoretical and algorithmic foundations in function approximation settings remain under-developed. In this paper, we consider this problem on the axes of distributional shift, optimization, and generalization in offline contextual bandits with neural networks. In particular, we propose a provably efficient offline contextual bandit with neural network function approximation that does not require any functional assumption on the reward. We show that our method provably generalizes over unseen contexts under a milder condition for distributional shift than the existing OPL works. Notably, unlike any other OPL method, our method learns from the offline data in an online manner using stochastic gradient descent, allowing us to leverage the benefits of online learning into an offline setting. Moreover, we show that our method is more computationally efficient and has a better dependence on the effective dimension of the neural network than an online counterpart. Finally, we demonstrate the empirical effectiveness of our method in a range of synthetic and real-world OPL problems.
BibTeX
@inproceedings{nguyentang2022offline,
  author = {Thanh Nguyen-Tang and Sunil Gupta and A. Tuan Nguyen and Svetha Venkatesh},
  title = {{Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=sPIFuucA3F},
}
Figure