Posterior Sampling via Autoregressive Generation

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-08-29 00:40:46

Abstract: Real-world decision-making requires grappling with a perpetual lack of data as environments change; intelligent agents must comprehend uncertainty and actively gather information to resolve it. We propose a new framework for learning bandit algorithms from massive historical data, which we demonstrate in a cold-start recommendation problem. First, we use historical data to pretrain an autoregressive model to predict a sequence of repeated feedback/rewards (e.g., click responses to news articles shown to sequences of users). In learning to make accurate predictions, the model implicitly learns an informed prior based on rich action features (e.g., article headlines) and how to sharpen beliefs as more rewards are gathered (e.g., clicks as each article is recommended). At decision-time, we autoregressively sample (impute) an imagined sequence of rewards for each action, and choose the action with the largest average imputed reward. Far from a heuristic, our approach is an implementation of Thompson sampling (with a learned prior), a prominent active exploration algorithm. We prove our pretraining loss directly controls online decision-making performance, and we demonstrate our framework on a news recommendation task where we integrate end-to-end fine-tuning of a pretrained language model to process news article headline text to improve performance.

Main paper: 
 introduction: 
 Real-world decision-making requires grappling with a perpetual lack of data as environments change; intelligent agents must comprehend uncertainty and actively gather information to resolve it. This is especially challenging with tasks involving unstructured inputs such as text and images. This paper offers a fresh perspective, casting the problem of balancing exploration and exploitation in online decision-making as a problem of training and sampling from an autoregressive generative sequence model, an area experiencing rapid innovation [2, 23, 50] .Problem setting. We present our insights by deriving a novel solution to a meta-bandit problem [51, 8, 26, 3] , in which an agent repeatedly encounters new tasks that require exploring to gather useful information. In real applications this meta-learning structure is common, and we illustrate our approach using a news article recommendation setting: Each day a batch of new articles is released, and upon release, the system observes each article's text but is uncertain about how engaging each article will be, as some articles may be surprise hits, or others may be less popular than expected.Models that solely rely on article text will eventually be outperformed by simple alternatives that learn from repeated user feedback. This example highlights the need to use rich features (e.g., article headline) and the need to acquire further information through active exploration.Our Algorithm. Our proposed solution proceeds in two phases. In the pre-training phase, the agent learns to model uncertainty by learning a simulator of user interactions using historical data on previously released articles. The simulator is an autoregressive sequence model that uses an article's attributes (e.g. headline text) to predict sequences of recommendation outcomes across users for Submitted to Workshop on Bayesian Decision-making and Uncertainty, 38th Conference on Neural Information that article. In the online decision-making phase, the agent models its uncertainty by simulating recommendation outcomes for new users with the pretrained sequence model. At each decision time, the agent uses the fitted simulator to autoregressively sample imagined/imputed recommendation outcomes for new users, conditioned on article features and on previously observed outcomes. The agent then takes the action with the greatest imputed average reward.Formal Connections to Thompson Sampling (TS). Far from a heuristic, our approach is a principled implementation of TS (with a learned prior), a prominent bandit algorithm with strong guarantees [49, 45] .implementations of TS, our approach never performs explicit Bayesian inference regarding latent parameters, and instead relies only on predicting and generating observable quantities. This enables standard ML tools for training. The connection between autoregressive sampling and TS rests on a link between exchangeable sequence modeling and Bayesian inference that has been known since de Finetti's seminal work [14] , and has appeared in several different literatures [17, 16, 21, 15, 38, 28] .Theoretical Guarantees and Empirical Evaluations. We provide formal links between interactive decision-making and sequence prediction, including a novel regret bound that scales with the pretraining loss of the sequence model. Furthermore, we demonstrate that our theoretical insights bear out on a news recommendation task that incorporates a language model. 
problem formulation: 
 Online Decision-Making Problem. Each online decision-making phase begins with new articles (actions) A new being released. Each article a ∈ A new is associated with attributes Z (a) ; in our experiments these represent article headlines. Even with rich article headline features Z (a) , the system is uncertain about how engaging articles will be to readers. The system interacts sequentially with distinct users t ∈ {1, 2, . . . , T } and can adapt future recommendations based on initial user feedback. To the t th user, it recommends A t ∈ A new , observes an outcome Y t , and constructs a reward R(Y t ) ∈ [0, 1] by applying a fixed, known function R(•). The vector of outcomes Y t could include a variety of user feedback like whether the user clicked or shared the recommended article.Each action a has T potential outcomes Y if article A t is recommended to the t th user. We assume articles are drawn independently from some fixed article distribution, i.e., {Z (a) , Y (1) Finally, we assume p * is exchangeable, meaning that for any permutation σ over {1, . . . , T }, any z, and any outcomes (y 1 , . . . , y T ), p * (y 1 , . . . , y T | z) = p * (y σ(1) , . . . , y σ(T ) | z).(2) Exchangeability means outcomes from recommendations made to a large subset of m < T users is likely to be representative of outcomes that would have been observed among all T users (Appendix J).Our goal is to develop an adaptive algorithm π for recommending articles that maximizes the expected average reward E p * ,π1 T T t=1 R(Y (At) t) (where the expectation is taken over draws of A new in addition to the randomness in p * and π), or equivalently, minimizes the per-user Bayesian regret, ∆(π; p * ) := E p * ,π maxa∈A new 1 T T t=1 R(Y (a) t ) - 1 T T t=1 R(Y (At) t) .(3)In (3) , we calculate the gap in reward relative to a baseline that always recommends the action with best performance in the (finite) population.Pretraining Phase. The goal of the pre-training phase is to learn a good active exploration algorithm to deploy in the online decision-making phase. We have access to a historical dataset D hist :=EQUATION1:n : a ∈ A hist , with action attributes Z (a) and observed outcomes Y (a)1:n from previous articles (actions) a ∈ A hist , for some n ≤ T . We assume this dataset is drawn from the same data generating distribution as in the online decision-making phase: Across a ∈ A hist , Z (a) i. We view uncertainty about unobserved outcomes as the source of uncertainty for decision-making, avoiding explicit reference to latent parameters/variables. Calibrated generation (imputation) of missing outcomes enables uncertainty quantification and good decisions. 
posterior sampling via autoregressive generation: 
 This work considers unobserved outcome data as the source of a decision-maker's uncertainty (Figure 1 ): for a given article, we only have responses from some users, and there is residual uncertainty in how future users would respond. Inspired by this viewpoint, our method proceeds in two steps:Phase 1: Pretraining an Autoregressive Model. We train an autoregressive sequence model p θ , with parameter θ ∈ Θ, that can predict missing outcomes, conditioned on article (action) attributes, and limited previously observed outcomes. This enables us to generate hypothetical completions of the potential outcome table in Figure 1 . Formally, this model specifies a probability 1:t-1 . We minimize the following loss on the historical dataset D hist :EQUATIONEQUATIONEQUATIONOur approach to pre-training an approximate exchangeable sequence model can also be thought of as empirical Bayes (Appendix C). Our approach also mirrors recent work on neural processes [20, 25, 35, 28] and prior-data fitted networks [33] . Our main contribution is linking this pretrained sequence model to online decision-making, which we present next. EQUATIONFinally, the algorithm selects actionA t = argmax a∈A new μ(a) t . Then the real outcome Y (At) t is observed.The process is repeated at the next decision time. See Algorithm 2 for further details.Through this process, actions that are optimal under some likely generation of the missing outcomes according to p θ , have a chance of a being selected. Once no plausible sample of missing outcomes could result in an action being optimal, it is essentially written off. Good performance of the algorithm relies on the model p θ matching the data generating process closely.We now formalize how the generated/imputed outcomes faithfully represent uncertainty and that PS-AR is akin to Thompson (posterior) sampling, which selects actions proportionally to the probability that actions are optimal. Lemma 1 shows that the imputed mean μ(a) t from PS-AR is a posterior sample of the mean reward µ (a) , and the action A t selected by PS-AR is a posterior sample of the optimal action A * := argmax a∈A new µ (a) whereEQUATIONt ). For simplicity, Lemma 1 is stated under the assumption that PS-AR uses the optimal sequence model p * (see E. P μ(a) t = • | H t-1 = P µ (a) = • | H t-1 and P (A t = a | H t-1 ) = P p θ (A * = a | H t-1+ |A new | 2 ℓ T (p θ ) -ℓ T (p * )Penalty for sub-optimal prediction .Advantages of the Autoregressive Approach. Since our approach focuses on predicting missing outcomes, the learned model only needs to model observable quantities, and can be learned via loss minimization (4) . In contrast, a more standard perspective on TS requires specifying a model for latent variables and performing explicit Bayesian inference; for large scale problems this often involves simplifying modeling assumptions, expensive MCMC, or heuristic posterior approximations.We build a news recommendation task using the MIcrosoft News Dataset (MIND) [53] where we demonstrate how PS-AR easily integrates with pretrained language models. Rewards are binary (click/no-click). We consider three types of sequence models. FLEXIBLE NN (TEXT) and BETA-BERNOULLI NN (TEXT) are neural network models that incorporate article headlines using DistilBERT [46] . FLEXIBLE NN (CATEGORY) uses only category information (e.g. "Sports"). See Appendix F.1 for synthetic experiments, and Appendix G for experiment details. We present pseudo-code for the two phases of our method: pre-training (Algorithm 1) and online decision-making (Algorithm 2). For each a ∈ A, sample outcomes with replacement:Ỹ (a) 1 , Ỹ (a) 2 , . . . Ỹ (a) T | {Z (a) , Y (a) 1:n } i.i.d. ∼ 1 n n i=1 δ Y (a) i Above, 1 n n i=1 δ Y (a) i denotes the empirical distribution of Y (a) 1:n 4:Define bootstrap-resampled minibatch D ← {Z (a) , Ỹ (a) 1:T } a∈A 5:Compute loss ℓ(p θ ; D) as defined in (4)6:Backpropagate and take a gradient step to update θ 7: end while 8: return p θ Practical Considerations for the Pre-Training Step (Algorithm 1)• In Algorithm 1 line 3, instead of bootstrapping sequences of length T , for practical purposes we sometimes bootstrap samples sequences of length T train < T if training to length T is very computationally expensive (we do this for our news recommendation experiments).• While we have been assuming that D hist has sequences all of the same length n, in practice, this may not always be the case. Let n (a) refer to the number of observations for article a ∈ A hist . In this case, we can easily replace n with n (a) in line 3 of Algorithm (2) (we do this for our news recommendation experiments). Autoregressively sample hypothetical outcomes for missing valuesEQUATIONi Form imputed average reward using observed and generated outcomes: i ∈ T (a)μ(a) t ← 1 T τ ∈T (a) obs R Y τ + τ ∈T (a) gen R Ŷ (a) τ 10:end for Autoregressively sample hypothetical outcomes for missing values Ŷ (a)EQUATION1:t ′ -13: end for 4: Form imputed average reward using m generated outcomes Specifically in Figure 4 we compare both versions of PS-AR on a news recommendation setting.EQUATIONIn our experimental setup, use two versions of the pretrained autoregressive sequence model p θ : FLEXIBLE NN (TEXT) and FLEXIBLE NN (CATEGORY) (see Appendix G.3 for more details). We run both versions of PS-AR with each of these two p θ models. We use T = 1000, |A new | = 10, and the truncated version of PS-AR uses m = 500. We follow the procedure described Appendix G.3 in forming the regret plots: we run 500 repetitions of each bandit algorithm and in each repetition we draw a new set of 10 actions/articles from the validation set to represent a "new task". Regret is calculated with respect to µ (a) in Equation ( 6) below:EQUATIONt ) and A * := argmaxEQUATIONAs discussed in Remark 1, the version of the algorithm that performs full imputation averages over both previously observed rewards and hypothetical samples of unobserved rewards when computing the imputed mean (5) . The m-truncated version averages solely over generated rewards. This difference does not have a practically significant impact on performance in Figure 4 .Examining Truncating Generation Length (Figure 5 ) We examine the performance of our PS-AR algorithm for different generation truncation lengths m (Algorithm 2 with lines 4-9 replaced with Algorithm 3). Throughout all our previous experiments we use m = 500. In Figure 5 , we examine the impact of varying m on the regret of the PS-AR with the FLEXIBLE NN (TEXT) sequence model in the news recommendation setting. We follow the procedure described Appendix G.3 in forming the regret plots: we run 500 repetitions of each bandit algorithm and in each repetition we draw a new set of 10 actions/articles from the validation set to represent a "new task". We find that that increasing m reduces the regret of the algorithm; however, when m is sufficiently large, the benefit of increasing m further is negligible. This section discusses the intimate connections between (large) finite-population formulations that were discussed in the main body of the paper and infinite-population formulations that are more common in the Bayesian bandit literature. We do this in the special case of the mixture model of Example 1.We emphasize that from our perspective, the main advantages or disadvantages of the finite population view are conceptual. In terms of advantages: (1) the definitions do not require any explicit assumptions around mixture modeling or latent variables. and (2) The finite nature of the problem lets us visualize the procedure as in Figure 2 , without abstract reference to limits across infinite sequences.B.1 Review of Thompson sampling in infinite populations, with mixture models.Thompson sampling is most often defined for a mixture model as in Example 1. Following that example, we consider in the subsection the canonical example of exchangeable sequences: a mixture model wherein the outcomes are i.i.d conditioned on a latent variable U (a) . That is,p * (Y (a) 1 , . . . , Y (a) T | Z (a) ) = T t=1 P (Y (a) t | Z (a) , U (a) = u)P (U (a) = u)du.The unknown latent variable represents the decision-maker's uncertainty about an action's performance.The literature typically defines the "true arm means" asµ (a) ∞ = R(y)P (y | Z (a) , U (a) )dy.The subscript highlights that this has the interpretation of a long-run average reward across an infinite population of users (or infinite set of rounds). By the law of large numbers (applied conditional on(Z (a) , U (a) ), one has µ (a) ∞ = lim T →∞ 1 T T t=1 R(Y (a) t ).The true best arm is defined asA * ∞ ∈ argmax a∈A new µ (a) ∞ Randomness in the latent parameters (U (a) ) means µ (a)∞ and A * ∞ are random variables whose realizations are uncertain even given the history H t-1 . Thompson sampling selects an action by probability matching on A * ∞ , defined by the propertyEQUATIONPer-period Bayesian regret over T periods is defined asEQUATIONOne can define the true mean of a finite population asµ (a) T = 1 T T t=1 R(Y (a) t ).The true best arm for this finite population is defined asA * T ∈ argmax a∈A new µ (a) TAs in Lemma 1, Thompson sampling selects an action by probability matching on the (finitepopulation) optimal action A * T , defined by the propertyEQUATIONPer-period Bayesian regret over T periods is defined asE 1 T T t=1 R Y (A * T ) t -R Y (At) t (10)It is not hard to show that ( 10) is a more stringent notion of regret than in (8) , since1 T T t=1 R Y (A * T ) t ≥ 1 T T t=1 R Y (A * ∞ ) t by definition of A * T .Both definitions are widely used, with the more stringent finite-population version being more common in the adversarial bandit literature; see [27] .We analyze the gap between the two formulations in the case of a mixture model. Let U new = {U (a) :a ∈ A new } and recall Z new = {Z (a) : a ∈ A new }. By a sub-Gaussian maximal inequality E max a∈A new µ (a) ∞ -µ (a) T = E E max a∈A new µ (a) ∞ -µ (a) T | Z new , U new ≤ 2 log(|A new |) T ,To justify the last inequality, note that since the function R takes values inEQUATION∞ is subgaussian with variance proxy 1, conditional on Z new , U new (by Hoeffing's Lemma). Since it is the average of independent sub-Gaussian random variables, µ∞ -µT is subgaussian with variance proxy 1 T , conditional on Z new , U new . The last step follows then from applying the subgaussian maximal inequality, conditional on Z new , U new .It follows easily that the infinite population optimum A * ∞ is near optimal for finite populations:0 ≤ E max a∈A new µ (a) T -µ (A * ∞ ) T ≤ 2 2 log(|A new |) T .Analogously, the finite population optimum is near-optimal in infinite populations:0 ≤ E max a∈A new µ (a) ∞ -µ (A * T ) ∞ ≤ 2 2 log(|A new |) T .Supported by this theory, we do not focus on the distinction between A * T and A * ∞ in our developments.Some empirical insight can also be gleaned from Figure 4 in Appndix B. The implementation that performs full imputation can be interpreted as Thompson sampling for a finite population. As discussed in Remark 1, averages over both past observed rewards and samples of hypothetical unobserved rewards when sampling hypthetical population means.The implementation that performs forward generation of fixed-length m does not include past observed rewards in the average. For very large m, it is a direct approximation to infinite-horizon Thompson sampling. We can see in Figure 4 the these implementations have very similar performance.Define the The expected analogue of the training loss (4) (and averaged over the draw of news articles) isEQUATIONEQUATIONThe next lemma is a standard result connecting the excess expected loss of a sequence model p θ to its KL divergence from the true sequence model p * . To (nearly) minimize loss, p θ the learner needs to closely approximate the true sequence model.Lemma 2. For any sequence model p θ ,ℓ n (p θ ) = ℓ n (p * ) + E Z (a) ∼P Z D KL p * Y (a) 1 , . . . , Y (a) n | Z (a) p θ Y (a) 1 , . . . , Y (a) n | Z (a).Following the lemma, we provide an example that notes connections to ideas in Bayesian statistics.Example 1 (Exchangeability and mixture models). The canonical example of exchangeable sequences is mixture models, where the outcomes are i.i.d conditioned on a latent variable U (a) . That is,p * (Y (a) 1 , . . . , Y (a) T | Z (a) ) = T t=1 P (Y (a) t | Z (a) , U (a) = u)P (U (a) = u)du.The unknown latent variable represents the decision-maker's uncertainty about an action's performance.Example 2 (Empirical Bayes). Under the mixture model from Example 1, p * is called a posterior predictive distribution in Bayesian statistics. Consider the case where p θ is a posterior predictive induced by prior hyper-parameters θ. For ease of exposition, imagine a setting with no Z's and a conjugate Bayesian model where µ (a) ∼ Beta(α, β) andY (a) 1 , Y (a) 2 , • • • | µ (a) i.i.d. ∼ Bernoulli(µ (a) ).By Bayes rule, the posterior predictive distribution isEQUATION)For this choice of p θ , our training criterion (4) is equivalent to that used in Empirical Bayes (Type-II maximum likelihood) to fit prior distributions to observed data [34, 7, 36] . We empirically observe that training on our sequence loss can recover the true Bayesian prior (Appendix G.5). Our pretraining procedure can be viewed as learning an approximate posterior predictive by gradient descent.We discuss connections between our pretraining procedure and empirical Bayes (12) in Appendix G.5.In this section we discuss a preliminary approach to extend our algorithm to the setting with context features. In the news recommendation setting, the context features would represent user features.Data Generating Process. In this setting, article features Z (a) are drawn independently from P Z over a ∈ A new . Independently of that, user contexts X t are discrete and drawn i.i.d. from an unknown distribution P X , i.e., X 1 , X 2 , . . . , X T i.i.d.EQUATIONMoreover, p * is such that for any z and any permutation σ over {1, . . . , T },EQUATIONσ(1) , . . . , X σ(T ) , YEQUATIONwhere above we use D = to denote equality in distribution.The historical dataset follows the same data generating process. For shorthand, we useEQUATIONn ) to denote sequences of tuples. We denote the training set D hist = Z (a) , X, Y (a) 1:n (for some n ≤ T ). For each a ∈ A hist , we assume (X, Y (a) ) 1:n is a completely at random subset of the tuples (X, Y (a) ) 1:T where X 1 , X 2 , . . . , X T i.i.d.∼ P X and Y (a) 1:T are sampled according to (13) .Phase 1: Pretraining an auto-regressive model. We train a sequence model analogously to Algorithm 1, however replace the training loss (4) with the following loss:EQUATIONIn the contextual case, transformers are a natural choice for the sequence model architecture for p θ . For each a ∈ A, sample outcomes with replacement:( X1 , Ỹ (a) 1 ), ( X2 , Ỹ (a) 2 ), . . . ( XT , Ỹ (a) T ) | {Z (a) , (X, Y (a) ) 1:n } i.i.d. ∼ 1 n n i=1 δ (Xi,Y (a) i ) Above, 1 n n i=1 δ (Xi,Y (a) i) denotes the empirical distribution of (X, Y (a) ) 1:n .Define bootstrap-resampled minibatch D ← {Z (a) , ( X, Ỹ (a) ) 1:T } a∈A 5:Compute loss ℓ(p θ ; D) using ( 14)6:Backpropagate and take a gradient step to update θ 7: end while Autoregressively sample hypothetical outcomes for missing valuesEQUATIONi: i ∈ T (a) gen , X τ = x 8:Update generated set T Form hypothetical average reward using observed and generated (imputed) outcomesμ(a) t ← 1 |T (a) gen | + τ ∈T (a) obs 1 Xτ =x τ ∈T (a) obs R Y (a) τ 1 Xτ =x + τ ∈T (a) gen R Ŷ (a) τ 11:end for Corollary 1 relies on Theorem 1, which is a result that may be of independent interest that bounds the regret of any policy π in terms of the regret of π on the simulated environment and the gap in sequence loss between the simulated environment and the true data generating environment, ℓ T (p θ ) -ℓ T (p * ).Below we use ∆ π; p θ to denote the regret of π when the potential outcomes Y + (|A new |/2) {ℓ T (p θ ) -ℓ T (p * )}Penalty for sub-optimal simulator .Theorem 1, a novel result, states that the regret achieved by any algorithm π under the fitted environment simulator p θ is close to the regret π will achieve when deployed in the true environment p * , so long as the loss achieved by p θ is close to that of p * . Theorem 1 thus characterizes the regret of any algorithm, including TS, that uses a misspecified prior. To see this, pick π to be Thompson sampling with a misspecified prior and pick p θ to be the data generating distribution under the misspecified prior; then ∆ π; p θ will have the typical regret bound for Thompson sampling and the second term on the RHS of (1) characterizes the penalty for having a misspecified prior. Our result can be thought of in some ways as a generalization of [47] , which only applied to a "k-shot" version of Thompson sampling.See proofs in the rest of this section.Proof. By the definition of the expected loss in (11) , and the chain rule of KL divergence: The final equality is the definition of the KL divergence between conditional distributions.EQUATIONProof. At decision time t, suppose in the history H t-1 a particular action a ∈ A new has been shown to usersT (a)obs ⊆ {1, 2, . . . , t -1}. For the function f({y i } T i=1 ) = T -1 T i=1 R(y i ), one has µ (a) = f Y (a) i T i=1and μ(a) i = f Y (a) i : i ∈ T (a) obs ∪ Ŷ (a) i : i ∈ T (a) gen where { Ŷ (a) i : i ∈ T (a)gen } are drawn according to Algorithm 2 applied with sequence model p θ = p * .The result thatP μ(a) t = • | H t-1 = P p θ µ (a) = • | H t-1 follows immediately since {Y (a) i : i ∈ T (a)obs } are non-random conditioned on H i-1 and P ( Ŷ (a) 2 still be correct? The definition below turns out to be the right one.t : i ∈ T (a) gen ) = • | H t-1 = P (Y (a) t : t ∈ T (a) gen ) = • | H t-Definition 1 (Outcome revelation order under non-exchangeable sequence models). A (possibly non-exhangeable) sequence model p θ introduces an alternative data-generating process as follows.First, independently for each arm a ∈ A new , nature samples arm features Z (a) ∼ P Z ; then it samples Y (a) 1:T | Z (a) ∼ p θ (• | Z (a)EQUATIONand for all a ∈ A new ,EQUATION)Proof. We use the notation of Definition 1. Let N Y t ← Y (At) N (A t ) t .For the function f({y i } T i=1 ) = T -1 T i=1 R(y i ), one has µ (a) = f Y (a) i T i=1and μ(a EQUATIONT ) =EQUATIONT ) = • | H t-1 with probability 1. The proof of ( 16) is identical.We continue to use the indexing convention in Definition 1 of Subsection E.3. Formally, any policy π can be expressed a function that maps a history H t-1 and an exogenous random seed ξ to an action asEQUATION)The random seed allows for algorithmic randomness in action selection and is assumed to be independent of the draws of article features and potential outcomes (Z (a) , Y1:T ) a∈A new .The essence of the proof is to recognize that one could write a simulator that first randomly drew the environment "sample path" (Z (a) , Y1:T ) a∈A new and the algorithm seed ξ, and then implemented a completely deterministic sequence of operations to calculate the regret an algorithm incurs with that sample path and seed. Mathematically, the simulator is a function, (written as g(•) in the proof). We can view mis-specification of the sequence model as mis-specifying the distribution of the sample path draws used in the the simulator. We use information-theoretic tools to bound the impact this distributional change on the inputs to the simulator can have on the distribution of outputs of the simulator (e.g. regret).Proof. Since this proof requires analyzes regret under the mis-specified and possibly nonexchangeable model p θ , we must be precise about the order in which potentail outcomes are revealed.See Definition 2 for discussion of our indexing convention.This proof will show that for any policy π,∆ π; p * ≤ ∆ π; p θ + |A new | 2 {ℓ T (p θ ) -ℓ T (p * )}.Note for any policy π, by the triangle inequality,∆ π; p * ≤ |∆(π; p * ) -∆(π; p θ )| + |∆(π; p θ )|The remainder of the proof will focus on bounding the first term above. LetEQUATION1:T :a ∈ A new denote a draw of all article features and potential outcomes.The absolute difference in regret can be written as|∆(π; p θ ) -∆(π; p * )| = E p * ,π max a∈A new 1 T T t=1 R(Y (a) t ) - 1 T T t=1 R(Y t ) -E p θ ,π max a∈A new 1 T T t=1 R(Y (a) t ) - 1 T T t=1 R(Y t ) = E p * g (S new , ξ) -E p θ g (S new , ξ) ,where g is is a function that determines the algorithm's regret as a function of the potential outcomes and the external seed ξ that used to induce randomness in action actions. That is,EQUATION:T a∈A new , ξ := 1 T T t=1 R Y (A * ) t -R Y (At) t .This impliesEQUATION1:T ) = (vi) |A new | 2 • KL P p * (Z (a) ) ∥ P p θ (Z (a) ) =0 +KL P p * (Y (a) 1:T | Z (a) ) ∥ P p θ (Y (a) 1:T | Z (a) ) = (vii) |A new | 2 {ℓ T (p θ ) -ℓ T (p * )} • (i) holds because g is a function that takes values in [-1, 1], so ∥g∥ ∞ ≤ 1.• (ii) holds by Fact 9 in [44] (which uses Pinsker's inequality).• (iii) holds the chain rule for Kullback Liebler Divergence.• (iv) holds because ξ is and S new are independent.• (v) and (vi) hold again because the (Z (a) , Y1:T ) are i.i.d. across a ∈ A new and the chain rule for Kullback Liebler Divergence.• (viii) holds by Lemma 2.This proof is largely review of an information-theoretic analysis of Thompson sampling due to [44] .It was observed by [6, 5] that this analysis applied without modification to analyze regret with respect to the best fixed action (A * ) even in nonstationary environments (e.g. non-exchangeable models p θ as in Definition 1.)Proof. We continue to use the indexing convention in Definition 1. This proof will show that for any sequence model p θ ,∆ π PS-AR (p θ ); p * ≤ |A new | log(|A new |) 2T + |A new | 2 ℓ T (p θ ) -ℓ T (p * ) .By Theorem 1,∆ π PS-AR (p θ ); p * ≤ ∆ π PS-AR (p θ ); p θ + |A new | 2 {ℓ T (p θ ) -ℓ T (p * )}.We bound ∆ π PS-AR (p θ ); p θ by combining the probability matching result of Lemma 1 with Thompson sampling regret bound techniques from Russo and Van Roy [44] . Define the regret for the t th action as∆ t := R Y (A * ) N (A * ) t -R Y (At) N (A t ) t .The notation Y ∆ π PS-AR (p θ ); p θ = E p θ ,πPS-AR(p θ ) 1 T T t=1 ∆ t .By the proof of Proposition 1 of [44] (which is general and applies to all algorithms),E p θ ,πPS-AR(p θ ) 1 T T t=1 ∆ t Z new = z ≤ H p θ A * | Z new = z • Γ T ≤ log(|A new |) • Γ T where H p θ (A * | Z new = z) ≤ log(|A new |) refers to the conditional Shannon entropy of A * given Z new := (Z (a)) a∈A new = z under the data generating process defined by p θ , and Γ is a constant upper bound on the "information ratio" such thatΓ ≥ max t∈[1 : T ] E t ∆ t 2 I t A * ; (A t , Y t ) | w.p. 1.E t [•] = E t [• | H t-1 ]to denote that expectations are conditioned on the history andI t A * ; (A t , Y t )to denote the mutual information between A * and (A t , Y t ) conditional evaluated under a base measure that conditions on H t-1 . (Recall that the history also includes the information in Z new ).The proof of Proposition 5 of [44] shows that one can choose Γ ≤ |A new |/2 w.p. 1. As observed in [6, 5] , this proof relies only on the probability matching property in Lemma 3 and hence applies in our setting.Combining our results impliesE p θ ,πPS-AR(p θ ) 1 T T t=1 ∆ t Z new = z ≤ log(|A new |) • |A new | 2T ,so the result follows by the law of iterated expectations. In this appendix we discuss general implementation techniques in Appendix G. (2) Truncating Generation Lengths. When the population size T is large, generating missing outcomes for the entire population can be costly. To save computation, we implement a slightly modified version of PS-AR that instead generates only m missing outcomes per action and averages those m outcomes to form μ(a) t ; by (24) this is a good approximation when m is relatively large. This is further supported by our simulation results where we vary m (see Figure 5 in Appendix A).Data generating process In this setting, we use article attributes beZ (a) = Z (a) 1 , Z (a) 2 ∈ R 2where Z ∼ Bernoulli(µ(a) ∞ ).Here, µ∞ corresponds to the success rate in the data generating process, in contrast to µ (a) in the main text of the paper, which corresponds to the mean (or success rate) in the finite-sample population of size T . Note that µ (a) converges to µ N (a) t-1 t ′ =1 Y t ′ 1 A t ′ =a , 1 1+N (a), where N (a) := t-1 t ′ =1 1 A t ′ =a . (In practice, we found that repeating the summary tuple input 10 improved performance, so the model took as input vectors in R 22 which consisted of a 2-dimensional Z (a) and 10 copies of the sufficient statistic tuple). Note that this entire p θ could alternatively be implemented as a transformer.The MLP we use has three linear layers, each of width 50. After the first and second linear layers, we apply a ReLU activation. After the last linear layer, we apply a sigmoid function, so that the output is in (0, 1). The models are trained for 1000 epochs with learning rate 0.001, batch size 500, and weight decay 0.01 using the AdamW optimizer.• BETA-BERNOULLI NN. This is a sequential model that is the (closed-form) posterior predictive for a Beta-Bernoulli. The prior parameters for the Beta distribution, α θ (Z (a) ) and β θ (Z (a) ), are each parameterized by separate neural network MLP models that take in Z (a) .The MLPs we use has three linear layers, each of width 50. After the first and second linear layers, we apply ReLU activations. After the last linear layer, we also apply a ReLU activation, so that the final output is in [0, ∞). We initialize weights so that the bias term for both α θ (Z (a) ) and β θ (Z (a) ) to 1, so that we avoid starting with Beta parameters of value 0, as Beta parameters need to be positive. The models are trained for 1000 epochs with learning rate 0.001, batch size 500, and weight decay 0.01 using the AdamW optimizer.Additional details on Figure 6 In our uncertainty quantification plots Figure 6 (right), we evaluate over all 1000 actions in the validation set. We form 250 samples of μ(a) 1 for each action in the validation set using Algorithm 3 with m = 500. To generate posterior samples for BETA-BERNOULLI NN, we use the closed-form posterior (i.e., m = ∞).In our regret plots Figure 6 (left), we run 500 runs. In each run we randomly choose |A new | = 10 actions randomly with replacement from the validation set, and all algorithms are evaluated on these same sampled actions in each run. Regret is calculated relative to µ We now discuss the news data preprocessing process. This dataset is free to download for research purposes at https://msnews.github.io/. It is under a Microsoft Research License at https://github.com/msnews/MIND/blob/master/MSR%20License_Data.pdf, which we comply with.The terms of use are at https://www.microsoft.com/en-us/legal/terms-of-use.Our preprocessing procedure is as follows:1. Collect all articles from the MIND "large" dataset (training split only) [53] .2. Remove any article with fewer than 100 total impressions.3. Normalize the success probabilities to be centered around 0.5 in a way that preserves the ranking of µ (a) . We do this transformation to speed up the learning procedure (since it requires more data to learn small true Bernoulli success probabilities accurately). We leave simulations without this transformation to future work.Our transformation procedures as follows: Let µ with the exception that in place of a two-dimensional Z (a) , the MLP head of the neural network from before is fed as input a DistilBERT [46] embedding of text data Z (a) .Also, the MLP linear layers have width 100 instead of 50, and the sufficient statistics are repated 100 times instead of 10 times. All other architecture details are the same.The model is trained for 500 epochs with learning rate 1e-5 on MLP heads, 1e-8 on the DistilBERT weights, batch size 500, and weight decay 0.01 using the AdamW optimizer.• BETA-BERNOULLI NN (TEXT). This is very similar to the Beta-Bernoulli posterior predictive sequence model in Appendix G.2, with the exception that in place of a two-dimensional Z (a) , the MLP head of the neural network from before is fed as input a DistilBERT [46] embedding of text data Z (a) . On top of the one DistilBERT embedding are two separate MLP heads for α(Z (a) )and β(Z (a) ), which are trained together. Also, the MLP linear layers have width 100 instead of 50, and the sufficient statistics are repated 100 times instead of 10 times. All other architecture details are the same.The model is trained for 500 epochs with learning rate 1e-5 on MLP heads, 1e-8 on the DistilBERT weights, batch size 500, and weight decay 0.01 using the AdamW optimizer.• FLEXIBLE NN (CATEGORY). This is very similar to the flexible neural network model in Appendix G.2, but it uses a one-hot new category vector for Z (a) instead of a two-dimensional Z (a) . The model architecture and training parameters are also the same. In our regret plots Figure 3 (left), we run 500 runs. In each run we randomly choose |A new | = 10 actions randomly with replacement from the validation set, and all algorithms are evaluated on these same sampled actions in each run. Regret is calculated relative to µ (a)∞ as described above.Ensemble We describe the ensembling approach used in the uncertainty quantification plots in DistilBERT embedding; other params the same as before). We include a "randomized prior" variant that initializes each neural network model in the ensemble in a particular way to encourage diversity [37] .We compare our method with several baseline bandit methods.We model success rate µ∞ and potential outcomes Y (a) t using a conjgate Beta-Bernoulli model:EQUATIONEQUATIONWe also use reward mappings R(Y (a)t ) := Y (a)t . In our experiments, we use Beta-Bernoulli with a uniform prior, so α = β = 1. Note that unlike the BETA-BERNOULLI NN, the prior here does not depend on action attributes Z (a) .Online decision-making uses Thompson sampling, as described in in Algorithm 6. Observe outcome Y t from action A t . 9:Update posterior αEQUATIONt-1 otherwise 10: end for PS Neural Linear We implement a variation of "neural linear" as in Riquelme et al. [43] , Snoek et al. [48] . Our problem setting differs from theirs. Their bandit setting has a small, fixed number of actions without features Z (a) , and contexts X t . They also do not have a large historical dataset that can be used for pretraining, and the algorithm must make better decisions solely on the data (rewards) that it gathers through online decision-making.We create an adapted version of "neural linear" for our setting. First pretrain a (non-sequential) prediction model using D hist that takes as input the text and outputs a prediction for Y (a)t . The architecture of this model is that it takes the input text puts it through a DistilBERT model, and puts the output of DistilBERT through an MLP with (width 100, 3 layers). This model has been trained with learning rate 1e-5, batch size 500, and weight decay 0.01 using the AdamW optimizer. We use Z (a) to refer to the last layer output of article a's headline text.Then we model clicks using a Bayesian linear regression, across actions: for a fixed σ 2 ,EQUATION)EQUATIONEQUATIONwhere 0 768 denotes a vector of 0's of size 768, and I 768 denotes an identity matrix of size 768 × 768.The bandit algorithm consists of 3 rounds of round-robin (choosing each action a ∈ A in sequence) as in Riquelme et al. [43] , and then afterwards, it uses Thompson sampling with the model above, using the posterior of β conditioned on observations across all actions that have been selected. In our experiments we set σ 2 = 0.25. We also try σ 2 = 0.5, 1 (omitted) but this change does not make a meaningful difference in regret.One reason why this version of neural linear does not perform very well compared to other bandit methods in our experiments is that by modeling actions together in this way, it is not possible to estimate the click rate for an action in a way that approaches 0 error as the number of observations for that action increases, unlike other methods (e.g. our PS-AR methods, as well as PS Beta Binomial, UCB, and SquareCB).UCB For UCB we use the multi-arm bandit algorithm described in Section 6 of [1] . We set the failure probability δ = 0.1 and use sub-Gaussian parameter 0.5 (since we have binary rewards).SquareCB In these experiments, we use the flexible neural network p θ with text attributes, but instead of using Thompson sampling, we use SquareCB [18] , which is a bandit algorithm that uses a regression oracle to predict the value of each action. Note that our setting differs from the setting of SquareCB [18] , as SquareCB assumes that the prediction model for action value is being learned online, while our prediction model has been pretrained on historical data and is not learned online.For setting the learning rate γ in SquareCB [18] , we follow Foster et al. [19] and consider a timevarying learning rate γ t = γ 0 t ρ , where γ 0 ∈ {10, 100} (a subset of those suggested in Foster et al. [19] ), and ρ ∈ {0.25, 0.5} are hyperparameters. While some hyperparameter combinations for SquareCB perform almost as well PS-AR FLEXIBLE NN (TEXT), we remark that there is no principled approach to choosing the learning rate provided in existing works (besides grid search by deploying the algorithm many times).Here, we demonstrate in practice an setting where we perform "empirical Bayes" using our pretraining procedure (Algorithm 1). We find that we recover the true prior fairly well.We use a synthetic Beta-Binomial data generating process. We consider onedimensional action features Z (a) i.i.d. ∼ Uniform(0, 1). We then sample µ (a) from a Beta distribution, whereEQUATIONThen, Y (a) | µ (a) , Z (a) ∼ Bernoulli(µ (a) ). We use R(y) := y. We use a training dataset of size 25,000 actions and a validation set of size 10,000 actions; both datasets have observation sequences of length n = 500.Autoregressive model We use p θ which matches the posterior predictive of a Beta-Bernoulli distribution, akin to (12) . To accomodate Z (a) features, we parameterize the prior hyperparameters:α θ (Z (a)), β θ (Z (a) ) (we follow the procedure described in Appendix G.2 for BETA-BERNOULLI NN). The neural network model architecture used in α θ (Z (a) ), β θ (Z (a) ) and the training procedure are also the same as described for BETA-BERNOULLI NN in Appendix G.2 (except that the MLP widths are 100).Recovering the Prior: Figure 9 We show in Figure 9 that through our pretraining procedure Algorithm 1 with our particular choice of p θ model class, that we (approximately) recover the true prior. We show this by comparing means and standard deviations of samples from our learned prior (using p θ ) vs. the true prior (according to the data generating process), for different draws of Z (a) . In the scatter plots, each point corresponds to one Z (a) .Specifically, in these plots we use 100 actions sampled uniformly from the validation set. For each of these 100 actions we form 10, 000 samples of μ(a) 1 using Algorithm 3 using our learned p θ model.We also form 10, 000 samples from the true data generating prior (23) for each of the 100 actions.Then for each action, we compute the mean and standard deviations of the samples on the "prior" samples μ(a) 1 from p θ ; we also compute the mean and standard deviations of the samples from the true prior. We then plot these in a scatter plot; for each action, we have the prior mean according to p θ vs the prior mean according to the data generating process-this forms one point on the scatter plot. A similar procedure is plotted on the right. There, instead of computing the mean of the prior samples, we compute a measure of the spread of the prior samples: let μ(a) We train on a GPU only for text models that fine-tune DistilBERT, which applies to learning sequence models for the MIND news setting (Section 3.2, Appendix G.3). In these cases, each run uses a single NVIDIA A40 GPU, and a single training run of the slowest variant FLEXIBLE NN (TEXT) takes about 16 hours to complete. We ran hyperparameter sweeps and tried several architecture variations, so we estimate the total compute to be an order of magnitude or two larger than that of a single run.EQUATIONNote that we use the CPU cluster for e.g. ensembling, where we freeze the DistilBERT part of the model and train MLP heads with random initializations on bootstrap-resampled subsets of the data.Meta-Learning in Bandits. There are a variety of bandit algorithms for meta-learning problems [51, 8, 26, 3] ; these methods primarily focus on simpler settings (e.g. Gaussian or linear reward models). There are also deep meta-learning methods developed for recommendation systems and the cold-start problem [52, 56, 57] . These works primarily focus on more complex recommendation settings (e.g. tracking the same user over time) and not on uncertainty. In contrast, our goal is to showcase our uncertainty quantification method for decision making in a semi-realistic setting.Reinforcement Learning (RL) with Pre-Trained Autoregressive Models. Many recent works in RL leverage sequence models that are pretrained on a large volume of data collected by an expert policy. [29, 30] relate sampling from a model that predicts the next expert action to Thompson sampling. Other works apply goal-conditioned sampling of expert actions to improve over average expert behavior [54, 24, 9, 12, 13] ; this works well in some settings but is provably sub-optimal others [4, 32] . Our work is different: we use sequence models to imagine plausible trajectories of future rewards, and use this to drive intelligent decision-making without requiring expert demonstrations.Thompson Sampling with Deep Learning Models. Several classes of approaches that have emerged to scale Thompson sampling to modern large scale decision-making problems that utilize neural network. The first class places a Bayesian prior on the weights of the neural network itself.These methods include those that form a Bayesian linear regression model from the last layer of a trained neural network [43, 48] , as well as Bayesian neural networks [55] . A second class of approaches involves forming using an ensemble of neural networks to simulate samples from a posterior distribution [37, 31, 41] . This class also includes algorithms that build on Epinets [40, 58, 39] , which attempt to retain the performance of the ensembling with lower computational cost. Notably, [40] uses sequence prediction loss to evaluate the quality of ("epistemic") uncertainty quantification, inspiring our efforts to construct bandit algorithms using sequence models.We formulate a loss minimization problem that implicitly learns an informed prior using historical data, in order to model the posterior distribution of action rewards for decision-making. This connection enables using modern ML tools to learn rich representations to comprehend uncertainty, in an actionable way. Our formulation introduces a fresh approach to the longstanding challenge of scaling Thompson sampling to incorporate neural networks that incorporate unstructured inputs such as images and text [43] . The main ideas behind our algorithm generalize to contextual settings where user-specific contexts X t can be used to tailor recommendation decisions. We describe generalizing our method to this setting in Appendix D and leave a deeper dive to future work.Limitations. We assume articles are i.i.d. between pretraining and online evaluation, and user outcomes for each action are exchangeable. Such assumptions may not be appropriate in practice, e.g., if user preferences are nonstationary. In conducting this work, we struggled to find publicly available datasets on which to evaluate our method, which led us to build our news recommendation setting. Building public benchmarks for bandit problems that require using complex inputs (e.g. text and/or images) for best performance is an important open direction. A limitation of this work is we do not provide a thorough answer as to the quality of the historical data (e.g., amount of data and/or how data was collected) necessary to ensure learning good sequence models.We elaborate on a comment made in the text. Exchangeability means that outcomes from recommendations made to a large subset of m < T users is likely to be representative of outcomes that would have been observed among all T users.It is not hard to formalize results of this type. For instance, for any permutation σ over {1, . . . , T },EQUATIONThe term 1 -m T is the finite population correction to the standard error of the sample mean [42,K When is an Autoregressive Sequence Model a Valid Posterior Predictive?In Algorithm 1, we learn an autoregressive model to use in place of a posterior predictive in Algorithm 2. We make this connection in Section 3.1 and establish a regret bound for Algorithm 2 that holds whenever p θ has low loss.In this section, we address the following question: When is p θ a valid posterior predictive, for some underlying Bayesian model?In order for an autoregressive generative sequence model to be a valid posterior predictive distribution, the sequence model to be infinitely exchangeable. We say that a sequence model is an infinitely exchangeable sequence model if it generates infinitely exchangeable random variables (Definition 2). Practically, this means that the models we train need to be invariant to the order in which previous outcomes are fed into the model. The key insight behind why infinitely exchangeable sequence models are valid posterior predictives is De Finetti's Representation Theorem (Theorem 2 below).We state this Theorem for binary outcomes for simplicity [10, 22] , but it generalizes to real-valued outcomes [11] .Theorem 2 (De Finetti's Representation Theorem for Binary Outcomes). If a sequence of binary random variables {Y i } i∈N is infinitely exchangeable, then there exists a unique distribution P (µ) on [0, 1] such that for some µ∼ P (µ ∈ • ), Y 1 , Y 2 , Y 3 , • • • | µ i.i.d. ∼ Bernoulli(µ).The implication of Theorem 2 is that any infinitely exchangeable sequence of binary random variables {Y i } i∈N can equivalently be described as being generated by a particular Bayesian model with a Bernoulli likelihood. Above, µ is a latent success probability that is drawn from some prior distribution P (µ ∈ • ).In practice note that our bootstrap training procedure in Algorithm 1 helps ensure our sequence model p θ is approximately exchangeable.Although our contribution is largely conceptual/theoretical, we list some potential positive and negative societal impacts.Positive impacts Our method could potentially enable better decision making in a variety of settings, including areas of clear social good like personalized healthcare. By incorporating historical data, including with complex features (e.g. text or images), in a flexible way, we enable more historical data to be used more effectively.Negative impacts Our method proposes learning recommendation algorithms using historical data.It is possible that historical data contains biases that can be harmful when perpetuated. We urge researchers to be thoughtful when curating and using historical data for this purpose. We also urge researchers to be thoughtful about the rewards R(•) they are aiming to maximize, as e.g. it is not always best for the user to maximize the user's time spent on a recommendation platform.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: See the code included in the supplementary materials.• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We discuss these experimental setting details in Section 3.2 and also Appendix G.• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: In the main experiment plots (e.g. in the main body of the paper), we use error bars to denote ±1 standard error of the mean, and we note this in the appropriate captions.We do not include error bars in Figure 7 in Appendix G.3, which is just for exploratory data visualization of click probabilities in a dataset.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We discuss the compute we used in Appendix G.6.• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss broader impacts in Appendix L.• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not release data, and we do not consider our models to have a high risk for misuse.• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification:The only assets we use are the MIND dataset [53] and DistilBERT [46] . For both we ensure we follow their license agreements (see Appendix G.3 for more information on their URLs, usage, and licenses).• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.Processing Systems (BDU at NeurIPS 2024). Do not distribute. 
 
 Appendix:  



Reviews: review: title: title: Review for "Posterior Sampling via Autoregressive Generation"
main_review: main_review: 1. Summary of the Paper:
This paper presents a novel approach to bandit algorithms, particularly focusing on Thompson sampling, by leveraging autoregressive generative models. The authors propose a framework that uses historical data to pretrain an autoregressive model for predicting sequences of rewards. This model is then used to implement Thompson sampling by generating imagined reward sequences for each action. The work is applied to a cold-start recommendation problem, specifically in news article recommendation.

2. Strengths:
a) Novelty: The integration of autoregressive generative models with Thompson sampling is an innovative approach to bandit algorithms. This bridges the gap between modern machine learning techniques and classical decision-making strategies.

b) Theoretical Grounding: The authors provide a theoretical analysis linking their pretraining loss to online decision-making performance, which adds rigor to their approach.

c) Practical Application: The framework is demonstrated on a real-world problem (news recommendation), showing its potential for practical impact.

d) Scalability: The method's ability to leverage large historical datasets for pretraining suggests good scalability to large-scale problems.

3. Weaknesses:
a) Empirical Evaluation: The paper would benefit from a more comprehensive empirical evaluation, including comparisons with a wider range of baseline methods and experiments on diverse datasets.

b) Computational Complexity: There's limited discussion on the computational demands of the approach, particularly for large-scale applications. This is crucial for understanding its practical feasibility.

c) Exchangeability Assumption: The assumption of exchangeability might limit the applicability of the method in some real-world scenarios where context significantly changes over time.

4. Detailed Comments:
- The theoretical analysis (Theorem 1 and Corollary 1) is a strong point, but it would be helpful to provide more intuitive explanations of these results for readers less familiar with the technical details.
- The integration of language models for processing news article headlines is interesting, but more details on this process and its impact would be valuable.
- The paper could benefit from a more in-depth discussion of the limitations of the approach and potential future work to address these limitations.
- A comparison with recent work on approximate Thompson sampling and hypermodels would strengthen the paper's positioning in the current literature.

5. Questions for Authors:
1. How does the computational complexity of your approach compare to traditional Thompson sampling methods, especially for large action spaces?
2. Can you elaborate on how your method might be extended to non-exchangeable settings, such as those with evolving user preferences over time?
3. Have you explored the impact of different architectures for the autoregressive model on the performance of your method?
4. How sensitive is your approach to the quality and quantity of historical data available for pretraining?

6. Recommendation:
This paper presents a novel and potentially impactful approach to bandit algorithms, combining modern machine learning techniques with classical decision-making strategies. While there are areas for improvement, particularly in empirical evaluation and addressing limitations, the theoretical contributions and practical applicability make this work valuable to the field.

The authors should focus on:
1. Expanding the empirical evaluation with more diverse baselines and datasets.
2. Providing a more detailed discussion of computational complexity and scalability.
3. Addressing the limitations of the exchangeability assumption and discussing potential extensions.
4. Enhancing the comparison with recent related work in approximate Thompson sampling and hypermodels/hyperagent.

With these revisions, this paper could make a significant contribution to the field of online decision-making and recommendation systems.
title: title: Review
main_review: main_review: **Overview:**
The paper presents a novel framework for learning bandit algorithms from historical data, specifically applied to a cold-start recommendation problem. The authors propose using an autoregressive model to predict sequences of feedback/rewards, which implicitly learns an informed prior. This approach is framed as an implementation of Thompson Sampling with a learned prior. The paper provides theoretical guarantees and demonstrates the framework on a news recommendation task.

**Strength:**
The use of autoregressive models for posterior sampling in bandit problems is a novel approach. There are solid theoretical results including a novel regret bound that scales with the pre-training loss of the sequence model, which highlights the connection between pre-training loss and online decision-making performance. Emperical results seem strong, outperforming other approaches in terms of cumulative regret.

**Weekness:**
Comparison to other state-of-the-art methods and the tasks chosen for expeirments are limited. The performance will be more convincing if comparison with e.g., "Learning to Optimize Via Posterior Sampling, Daniel Russo" and "TS-UCB: Improving on Thompson Sampling, Jackie Baek" are made. These important citations are also missing. Experiments on other standard bandit/decision making datasets should also be beneficial. Finally, the complexity of training and deploying autoregressive models might be a concern for large-scale applications.

Nonetheless, for a workshop paper, the idea it presents is interesting enough.