Informed Exploration via Generative Modeling

We are glad that the reviewer finds our method intuitive and easy to implement, and that the reviewer appreciates that we tackle the important problem of informed exploration, which is crucial in many important settings. We are also glad that the reviewer appreciates our strong theoretical justification and connections to empirical Bayes, and that the reviewer recognizes that our experiments demonstrate effectiveness in terms of both regret and calibrated confidence intervals.

1. Overlap

As discussed in line 114 in our problem setup, the articles in the historical dataset and the online decision-making phase are assumed to be drawn IID from the same distribution. Note that we use $\mathcal{A}^{\mathrm{hist}}$ throughout to denote the articles observed in the historical dataset, and use $\mathcal{A}^{\mathrm{eval}}$ to denote the articles observed in the online decision-making phase (and in Algorithm 1), which are new articles that are not in $\mathcal{A}^{\mathrm{hist}}$.

2. Multi-arm vs contextual bandit setting

For ease of exposition, the main text of our work focuses on the multi-arm bandit setting, without user context. There, we assume multiple users, but without user attributes. This is equivalent to viewing the problem as one of finding the best article, on average, for a cluster of users with similar interests or attributes.

In Footnote 1 on page 2, we explain that we defer a discussion of the setting with user attributes ("context"), including algorithms, to Appendix B in the Supplementary Materials. We highlight this choice of presentation on line 108 and the footnote at the bottom of page 2 at the beginning of the problem formulation section.

We will emphasize these points in the revision.

3. Computational cost

• For the online decision-making phase, autoregressively generating from the sequence model can be computationally intense, and scales with the number of timesteps. We discuss truncating the generation length in our experiments (see line 443), which we found works well empirically. We find that if we completely remove autoregressive generation, the decision-making algorithm makes lower quality decisions (see Figure 4).
• For both online and offline portions, computational cost for PSAR scales linearly with the number of online and offline actions considered, respectively. This is part is largely unavoidable. We note that the computational scaling of our approach (especially the offline pretraining) is similar to that of training and generating from LLMs. We expect that the cost of sequence modeling (both training and inference) will decrease, as is the current trend for LLMs. We highlight this on line 298, in the paragraph titled "Advantages of the Autoregressive Approach to Thompson Sampling (TS)".
• We think there may be a misunderstanding regarding overlap; see the section of our response regarding overlap.

4. Related work

The paper the reviewer suggested as a related work [1] is not relevant to our work. The suggested paper is on offline policy evaluation, while ours is on online decision-making. Because there is no online data gathering in [1], there is no need to balance exploration and exploitation, and thus the suggested paper has no relation to Bayesian uncertainty. While minor similarities may exist (e.g. modeling potential rewards under different actions, which is conceptually fundamental to all of bandit decision-making), the suggested work is not related.

[1] Doubly Robust Policy Evaluation and Learning. Dudik, Langford, and Li. https://arxiv.org/pdf/1103.4601

We appreciate that the reviewer found our method intuitive, values our theoretical analysis, and values our experiments in both synthetic and real-world settings.

1. Choice of baselines

Deep Bayesian Bandits Showdown [1] evaluates a variety of Bayesian decision-making algorithms when scaled with neural networks. In that work, NeuralLinear and NeuralGreedy were found to outperform a variety of other approaches (e.g. variational inference, Bayes by Backprop, Expectation propagation, dropout). Thus, in our work we chose to compare to neural linear and greedy (see Figure 4) in terms of regret, and also compare to ensembling in terms of uncertainty quantification. For these reasons, we believe the methods we compare to are strong baselines. We will emphasize these points in the revision.

2. Use of foundation models

To clarify definitions, foundation models are models trained on large quantities of data that can be tailored (e.g. via fine-tuning) to more specific downstream tasks [2]. We use BERT, which a foundation model for text, and we fine-tune a sequence model that uses BERT in our setting. We feed text associated with a news article through BERT to get a text representation, which is fed into a sequence model used to predict future rewards; the entire model, including the BERT component, is fine-tuned end-to-end. We find that without (i) the LLM embedding, and (ii) without end-to-end fine tuning that the performance on the downstream decision-making problem goes down. We have described this procedure in the main text (see line 42), where we describe the architecture as "a neural network model with a large language model (LLM) component".

3. What if the sequence models cannot precisely predict outcomes?

Our approach supposes that one is able to pretrain a sequence model to sample from a distribution of missing outcomes appropriately, and we discuss how standard sequence modeling approaches (training via standard loss minimization and gradient descent) can be used for this approach. In other words, techniques used to train sequence models to predict missing/masked out future words, can also be employed to predict missing/masked out future rewards.

Furthermore, in our theory, we characterize a bound on the quality of the decision-making algorithm depending on the loss of the pretrained model; this provides a way to easily evaluate prior to deploying the algorithm, whether PSAR may be a suitable algorithm for the problem (which is a significant advantage that many other decision-making algorithms do not provide).

[1] Riquelme, Carlos et al. “Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling.” ICLR 2018

[2] Wikipedia page for Foundation models https://en.wikipedia.org/wiki/Foundation_model

We appreciate the positive comments about our novel approach to Bayesian uncertainty quantification that we use with decision-making algorithms, in a way that is scalable and effective, is demonstrated on real-world tasks, and is furthermore theoretically grounded.

We thank the reviewer for their suggestions regarding related work on methods for uncertainty quantification. We emphasize that our main contribution is our decision-making algorithm that quantifies uncertainty via sequence modeling, and which is a principled implementation of Thompson sampling. Our contribution furthermore includes the empirical evaluation and theoretical analysis of our method. In the revision, we aim to emphasize the decision-making aspect of our contribution more clearly; see [8] for an overview of this challenge.

We also want to further emphasize how our algorithm PSAR stands out:

• PSAR can power efficient exploration in settings where there are rich unstructured attributes (e.g. text) associated with different actions. Other methods do not take advantage of action attributes.
• Previous efforts to use sequence models to implement Thompson sampling, only sample the next reward, rather than a sequence of next rewards; these do not implement posterior sampling correctly when rewards are noisy and can have bad performance (line 270-275, Figure 4).
• Our theory quantifies rigorously that effective next-token prediction is sufficient for interactive decision-making and exploration, a substantial result missing in all previous work.

Comments and revisions based on suggested related work.

Regarding the papers you listed, several of them are already mentioned in the original draft, while others we plan to add a discussion of:

• Decision Pretrained Transformers [7]: We have already included a discussion of [7]; see line 410.
• Prior Fitted Networks: We have a brief discussion of prior-fitted networks [4] and neural processes on lines 236-238. We plan to expand this discussion, and to include [3,6]. Specifically, we plan to say:
  • While prior fitted networks (PFNs) [3,4,6] develop generative models for Bayesian uncertainty quantification, except for [6], none of these works develop methods for on online decision-making. [6] focuses on a Bayesian optimization setting, while we consider a bandit decision-making setting where actions can have complex attributes (e.g. news article text). Furthermore, while we prove regret bound guarantees for our PSAR algorithm, [6] does not prove any performance guarantees for their approach. In general, we hypothesize that the work on PFNs in developing pretraining and architectural methods is very compatible with our PSAR decision-making algorithm, and believe using PSAR with PFNs is an interesting direction for future research.
• In the revision we plan to discuss [2], which considers a contextual bandit algorithm that utilizes GANs. A primary disadvantage of their approach is that they require taking gradient steps in the generator and discriminator in the online decision-making phase, which is practically difficult in online decision-making problems. In contrast, our approach all the pretraining and gradient steps happen in the pretraining phase.

We do not plan to discuss the following work, as the focus is too tangential to our contribution:

• [1] discusses Bayesian uncertainty for neural networks via dropout, but not generative models for Bayesian uncertainty quantification. Furthermore, [10] which investigated a variety of Bayesian neural network methods with Thompson sampling found that dropout did not perform well. This motivated us to compare to Neural Linear in our simulations, which was among the best performing algorithms in [10].
• [5] is a meta-learning method for fast classification of tabular data, similar to [3]. However, while [3] is (essentially) Bayesian, [5] is not. Thus, [5] is neither about generative models for Bayesian uncertainty quantification, nor online decision-making.

We believe the current proposed revisions balance the need to acknowledge related contributions while preserving the clarity of our main arguments.

Missing outcomes and decision-making

We had some trouble understanding your question on missing outcomes. We do not consider a delayed reward setting, where outcomes are delayed by e.g. weeks or months, as in [9]. Rather, since we are in a bandit decision-making problem, the algorithm only observes rewards for the actions it selects, and the rewards associated with the unselected actions are always missing. The algorithm also generates rewards for future decision times, within the same day.

As detailed in the paper and summarized in Algorithm 1, the imputed missing outcomes (during decision-making) are used to determine the action to take. In the simple multi-arm bandit setting, the arm with the highest (average) imputed missing outcomes is chosen. This is an implementation of Thompson sampling.