Empirical analysis of representation learning and exploration in neural kernel bandits

Michal Lisicki, Arash Afkanpour, Graham W. TaylorICLR 2023 · OpenReview

TL;DR

This paper introduces Neural Kernel (NK) bandits, which leverage the efficiency of Gaussian Processes with Neural Kernels (NK-GPs) to achieve state-of-the-art performance on complex, non-linear bandit problems. They also propose a novel framework to disentangle representation learning and exploration, offering deeper insights into bandit algorithm behavior.

What Problem Does This Paper Address?

Sequential decision-making problems, like recommending content or optimizing ad placements, often involve learning from user interactions over time. Contextual bandits are a powerful framework for this, where an agent learns to choose the best action based on observed context and rewards. A key challenge is balancing exploration (trying new actions to discover better strategies) and exploitation (using the current best-known strategy).

Traditional bandit algorithms often struggle with complex, non-linear relationships between context and rewards. While neural networks (NNs) can model these non-linearities, incorporating uncertainty estimation (crucial for exploration) with NNs is computationally expensive or requires approximations. This paper addresses this by exploring Neural Kernels (NKs), which offer a more efficient way to achieve Gaussian Process (GP) like uncertainty estimates, bridging the gap between efficient GPs and powerful NNs.

Methods

The core of this work lies in using Neural Kernel Gaussian Processes (NK-GPs) to power bandit algorithms. NKs are kernels derived from neural networks, allowing for GP-like inference but with the representational power of NNs. The authors leverage two specific NK kernels: the Neural Network Gaussian Process (NNGP) kernel and the Neural Tangent Kernel (NTK).

They propose using these NK-GPs within standard bandit policies like Thompson Sampling (TS) and Upper Confidence Bound (UCB). A key contribution is the development of an empirical framework to separately evaluate two crucial aspects of bandit performance:

  1. Representation Learning: How well the algorithm learns the underlying structure of the data and the relationship between context and reward.
  2. Exploration: How effectively the algorithm balances trying new options to discover potentially better rewards versus sticking with known good options.

They also explore the use of Student's t-process (TP) as a predictive distribution, which can lead to more aggressive exploration due to its heavier tails compared to GPs. Practical considerations like training frequency and model partitioning are also investigated.

Datasets

The authors evaluate their methods on:

  • UCI Datasets: A standard benchmark suite for contextual bandits, including datasets like adult, census, covertype, financial, jester, mushroom, and statlog. These are used to compare against state-of-the-art neural-linear bandits.
  • Noisy Wheel Dataset: An extension of the "wheel dataset" (originally proposed by Riquelme et al., 2018). This dataset is specifically designed to allow for the decoupling of representation learning and exploration. The authors introduce a "noise parameter" ($\epsilon$) to control the complexity of the task, enabling a fine-grained analysis of how algorithms perform under varying levels of exploration need and data complexity.

Key Insights and Ideas

  • NK-GPs as a Sweet Spot: NK-GPs offer a compelling trade-off, providing accurate uncertainty estimates and efficient training, making them well-suited for bandit problems where computational cost is a concern.
  • Deconstructing Bandit Performance: The proposed framework for separating representation learning and exploration is crucial. It moves beyond simply looking at cumulative rewards to understand why certain algorithms perform well or poorly.
  • NTKGP Excels in Exploration: The NTKGP distribution, particularly when paired with Thompson Sampling, demonstrates superior performance in scenarios requiring significant exploration and on complex, non-linear datasets.
  • Student's t-Process for Exploration: The Student's t-process shows promise for enhancing exploration in NK bandits, especially in challenging environments.
  • Practical Considerations Matter: Training frequency and model partitioning can significantly impact performance and computational cost, offering avenues for optimization.

Key Results

  • State-of-the-Art Performance: NK bandits, particularly those using NTKGP, achieve state-of-the-art results on many of the UCI datasets, outperforming neural-linear baselines. This improvement is most pronounced on datasets with high non-linear entanglement and a large number of features.
  • Noisy Wheel Dataset Insights: The analysis on the extended wheel dataset reveals that NTKGP combined with Thompson Sampling is the most robust approach across varying levels of exploration difficulty and data complexity.
  • UCB vs. TS: While both policies are evaluated, Thompson Sampling generally shows better performance, especially when combined with more sophisticated distributions like NTKGP, particularly in exploration-heavy scenarios.
  • Training Frequency Impact: Performance degrades gracefully with less frequent updates, suggesting that NK bandits can be practical even with limited computational resources.

Limitations and Future Work

  • Scalability: Computing Neural Kernels can be computationally intensive, which is acknowledged as a current limitation. The authors suggest kernel approximation methods and distributed computing as potential solutions.
  • Further Exploration-Exploitation Analysis: A more extensive analysis of the exploration parameter ($\eta$) for TS and UCB is suggested.
  • Comparison with Other Bayesian Methods: The authors propose using their framework to analyze other fully Bayesian neural bandit approaches.
  • Limited Memory Approaches: The robustness to less frequent updates suggests potential for developing limited memory NK bandit algorithms.

Summary updated

Abstract

Neural bandits have been shown to provide an efficient solution to practical sequential decision tasks that have nonlinear reward functions. The main contributor to that success is approximate Bayesian inference, which enables neural network (NN) training with uncertainty estimates. However, Bayesian NNs often suffer from a prohibitive computational overhead or operate on a subset of parameters. Alternatively, certain classes of infinite neural networks were shown to directly correspond to Gausian processes (GP) with neural kernels (NK). NK-GPs provide accurate uncertainty estimates and can be trained faster than most Bayesian NNs. We propose to guide common bandit policies with NK distributions and show that NK bandits achieve state-of-the-art performance on nonlinear structured data. Moreover, we propose a framework for measuring independently the ability of a bandit algorithm to learn representations and explore, and use it to analyze the impact of NK distributions w.r.t. those two aspects. We consider policies based on a GP and a Student's t-process (TP). Furthermore, we study practical considerations, such as training frequency and model partitioning. We believe our work will help better understand the impact of utilizing NKs in applied settings.
BibTeX
@inproceedings{lisicki2023empirical,
  author = {Michal Lisicki and Arash Afkanpour and Graham W. Taylor},
  title = {{Empirical analysis of representation learning and exploration in neural kernel bandits}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=e9rdb24Yzqx},
}
Figure