Non-stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling

1, 2, 3. In this response, we address the question from the first three questions from the reviewer. The main advantage of NeuralPES is to offer a practical neural network based non-stationary context bandit algorithm that follows the key insight from PS, which is to only explore for enduring information in the environment. The key differences are:

 a) NeuralPES only requires one-step rollout into the future instead of PS which requires sampling an infinite sequence of future rewards for all actions.
 b) NeuralPES conditions on the one-step rollout of future world parameter prediction with a sequence model instead of sampled rewards, such that we can scale to a large space of contexts and actions.
 c) PS does not support neural networks and assumes a known world dynamics for nonstationarity, but NeuralPES doesn’t require a known world dynamics and can adapt to any type of nonstationarity.

4. The theoretical analysis differs in that (a) we now consider contextual bandits, and (b) generalizes our analysis to linear bandits.

5. Execution/inference time for NeuralPES is 2x of standard neural networks since it requires a prediction of one-step rollout of world parameters. Training-wise, it is approximately 3x to standard ensemble neural networks that carries out Thompson-sampling-like exploration per batch of data given that the model has three stages. However, in production environments, people usually need to completely retrain models to adapt to nonstationarities and hence if we can incrementally train from the current model using NeuralPES, it would actually save a lot of resources.

6. A100 40GB GPU was the only GPU available to us. From our experiment, any GPU with 2 GB is sufficient for the experiment.

7. We refer to both the cumulative regret and the long-run average regret. We will revise those sentences to make it clear.

8. In this particular scenario, the cumulative regret is zero, so the algorithm is optimal.

9. We select M = 10 according to [1] given that a 10-particle ensemble with prior functions is sufficiently enough to approximate the posterior distribution of the reward. Increasing to 100 or even 1000 particles does not significantly improve the performance.

10. Yes the order of recommendations presented within the 12-hour is ignored but as we do not retrain our model within the 12 hours, it would not introduce any bias since we use the same NeuralPES model to address the whole batch of 12-hour data.

11. We are limited by our organization’s policy to not share code. We are in the process of obtaining permission to share open-source code. However, all hyperparameters and datasets are publicly available as listed in the paper.

[1] Osband, Ian, et al. "The neural testbed: Evaluating joint predictions." Advances in Neural Information Processing Systems 35 (2022): 12554-12565.

Thank you for the detailed feedback! We would like to make the following clarifications.

Responding to Weaknesses:

You raised the point that our analysis is “restricted to linear contextual bandits,” which is indeed a fairly large class of problems, and can be a good starting point.

Our algorithm does not rely on any assumptions of how the rewards are generated. Our theoretical results are introduced with the purpose to provide more intuition on how our algorithm works. Our result (Corollary 1) is general, and we establish a result in AR(1) bandit (Corollary 2) only to provide more intuition on this particular example. We will add a discussion/note on theoretical results.

Thank you for your suggestions on improving the presentation of the paper. Algorithm 2 is a submodule of Algorithm 1 and Algorithm 1 makes a call to Algorithm 2. Similarly, Algorithms 3 and 5 are submodules of Algorithm 2.

Responding to Questions: Thank you for bringing this up. We use $\mathbb{I}$ to denote mutual information, and $\mathbb{I}(\theta_2; \theta_1)$ corresponds to the mutual information between $\theta_2$ and $\theta_1$. In Corollary 1, we use $\mathbb{H}(p)$ to denote the entropy of a $\mathrm{Bernoulli}(p)$ random variable. We will include definition of mutual information and entropy in our manuscript. The regret is always non-negative, so when the regret is zero, it implies that the algorithm is optimal. We would like to clarify that the benchmark that the algorithm is compared against is not “the best arm”, i.e., $\arg\max_{a \in \mathcal{A}}\mathbb{E}[R_{t+1, a} | \theta_{t+1}]$, but $\arg\max_{a \in \mathcal{A}}\mathbb{E}[R_{t+1, a} | \theta_t]$ instead.

Therefore, when $\{\theta_t\}$ for ${t \in \mathbb{N}}$ is i.i.d. (an example when changes are frequent), $\mathbb{E}[R_{t+1, a} | \theta_t] = \mathbb{E}[R_{t+1, a}]$ and it makes sense that regret can be zero.

Thank you for acknowledging that this is the first time you see the neural bandit’s work in non-stationary environments. We would like to make the following clarifications.

(1) An Ensemble of neural networks can perform Thompson sampling-like exploration. This is also discussed in literature Lu and Van Roy (2017) [1], Qin et al. (2022) [2] and Osband et al. (2016) [3].

(2) Neural contextual bandit algorithms are very commonly adopted in research that studies scalability [4, 5] and real-world applications [6], and also shown to be very incremental in terms of both training and inference [7]. Since each particle neural network is independent from others in an ensemble, in production systems, ensemble training usually leverages distributed GPU training and hence in general on par with standard deep supervised learning approaches. Since each ensemble particle is identical to a deep supervised learning model, inference cost is identical.

(3) The purpose of our theoretical analysis is to provide supporting evidence on the efficacy of our method, and we believe it achieves its purpose. We leave the analysis involving neural networks to future work.

[1] Lu, Xiuyuan, and Benjamin Van Roy. "Ensemble sampling." Advances in neural information processing systems 30 (2017).

[2] Qin, Chao, et al. "An analysis of ensemble sampling." Advances in Neural Information Processing Systems 35 (2022): 21602-21614.

[3] ​​Osband, Ian, et al. "Deep exploration via bootstrapped DQN." Advances in neural information processing systems 29 (2016).

[4] Xu, Pan, et al. "Neural Contextual Bandits with Deep Representation and Shallow Exploration." International Conference on Learning Representations. 2021.

[5] Riquelme, Carlos, George Tucker, and Jasper Snoek. "Deep bayesian bandits showdown." International conference on learning representations. Vol. 9. 2018.

[6] Lu, Xiuyuan, Zheng Wen, and Branislav Kveton. "Efficient online recommendation via low-rank ensemble sampling." Proceedings of the 12th ACM Conference on Recommender Systems. 2018.

[7] Zhu, Zheqing, and Benjamin Van Roy. "Scalable Neural Contextual Bandit for Recommender Systems." ACM International Conference on Information and Knowledge Management. 2023.