Non-Deterministic Behavior of Thompson Sampling with Linear Payoffs and How to Avoid It
Authors: Doruk Kilitcioglu
Serdar Kadioglu
Venue: Accepted by TMLR ()

Abstract: Thompson Sampling with Linear Payoffs (LinTS) is popular contextual bandit algorithm for solving sequential decision making problem. While LinTS has been studied extensively in the academic literature, surprisingly, its behavior in terms of reproducibility did not receive the same attention. In this paper, we show that a standard and seemingly correct LinTS implementation leads to non-deterministic behavior. This might go unnoticed easily, yet impact results adversely. This calls the reproducibility of papers that use LinTS into question. Further, it forbids using this particular implementation in any industrial application where reproducibility is critical not only for debugging purposes but also for the trustworthiness of machine learning models. We first study the root cause of the non-deterministic behavior. We then conduct experiments on recommendation system benchmarks to demonstrate the impact of non-deterministic behavior in terms of reproducibility and downstream metrics. Finally, as a remedy, we show how to avoid the issue to ensure reproducible results and share general advice for practitioners. 


Published in Transactions on Machine Learning Research (07/2022)
Non-Deterministic Behavior of Thompson Sampling with Linear Payoffs and How to Avoid It
Doruk Kiliiçioğll Pidelity Investments 245 Summer St Boston MA 02210
doruk. doruk..ilttciogllu@@ff..com
Serdar Kadıoğlu Pidelity Investments 245 Summer St Boston MA 02210
serdar, waaoorkkkooo@uff.no.o...mm com
Reviewed on OpenReview:
https: openreview. net/ formm id= fXtd3gfttt
Abstract
Thompson Sampling with Linear Payoffs (LinTS) is popular contextual bandit algorithm for solving sequential decision making problems. While LinTSS has been studied extensively in the academic literature, surprisingly, its behavior terms of reproducibility did not receive the same attention. In this paper, show that standard and seemingly correct LinTS implementation loads to non-deterministic behavior. This might go unnoticed casily, yet im- pact results adversely. This calls the reproducibility of papers that use LinTS into question. Further, it forbids using this particular implementation in any industrial application where reproducibility is critical not only for debugging purposes but also for the trustworthiness of machine learning models. We first study the root cause of the non-deterministic behavior. We then conduct experiments on recommendation system benchmarks to demonstrate the impact of non-deterministic behavior in terms of reproducibility and downstream metrics. Finally, as remedy, we show how to avoid the issue to ensure reproducible results and share general advice for practitioners.
1 Introduction
Contextual multi-armed bandit (MAB) algorithms are powerful solutions for online decision making problems in many areas of Information Retricval (IR) including online advertisement (Schwartz et al. (017) and personalized recommendation systems (Li et al. 2010). J. In this setting, an agent makes sequential decisions under uncertainty. In contextual bandits, the agent also observes feature vector (contezt) associated with each decision. Given the contextual information, the agent selects an arm and receives reward. The mechanism that determines the reward is unknown to the agent, and the reward of the chosen arm only be observed at runtime. The agent should carefully balance exploration and exploitation to maximize cunulative reward (Auer et al. 2002).
The main methods that target the ioploration-exploitttiin trade-off fall into two familics with several vari- anis: upper confidence bound (UCB) (Li al.) 2010 and Thompson Sampling (TS) (Thompson 1933 While the former selects the arm with the highest UCB, the latter Bayesian approach that maintains posterior distribution.
Among the bandit policies, Thompson Sampling with linear payoffs (LinTT)) has attracted significant atten- tion in the bandit literature. The original LinTS paper (Agrawal & Goyal 2013) from 2013 has more than 600 citations including many from the IR and recommender systems literalure (Abeille & Lazaric 2017

---

Published in Transactions on Machine Learning Research (07/2022)
Garcelon et al. 2020:
Dimakopoulou et al.
2019 Gutowski et al. 2019 2021 Moreover, LinTS is imple-
mented in several machine learning libraries including the STRIATUM Python library from National Taiwan University (Lin et al., 2016 STREAMING
REST service from Nth Iteration Labs
(Kuijswijk et al,
2016), the CONTEXTUAL R package from Tilburg University, DEEP BAYESIAN BANDITS Tensorflow- Python library from Google Brain with a variation that uses Bayesian Linear Regression (Riquelme et al.
2018), and finally, as part of MABWISER (Strong et al. 2021 2019), our own Python library for contextual multi-armed bandits from Fidelity Investment:
The LinT'S algorithm is popular for its Bayesian approach to exploration and empirical gains in performance over other contextual bandit algorithms (Li et al. 2010). The original LinTS paper from Microsoft Rescarch by Agrawal & Goyal (2013) provides an elegant proof for the non-trivial regret bound of the algorithm using martingale- based analysis. Unfortunately, the paper does not provide an implementation or any computational results to demonstrate algorithm performance. As such, the reproducibility of this work remained unknown to date. In this paper, we put LinTS to test.
Python is one of the most popular programming languages in machine learning research and data science practice. When implementing the Lin'TS algorithm in Python as part of our personalization efforts at Fidelity, we discovered that standard and seemingly correct implementation leads to subtle non-determinism. Such behavior might easily go unnoticed, yet it affects the predictions ad adversely and alters conclusions drawn. Non- deterministic behavior has several undesirable consequences. First, it casts a shadow on the reproducibility of papers and applications where this implementation is used. Second, it cannot be part of any industrial application where reproducibility is critical not only for reproducing recommendation results and debugging, but also for potential external audits required by law and trustworthiness of algorithms.
In this paper, we first show that the main issue behind the non-delerministic behavior stems from the multivariate normal distribution functionality in NUMPY (Harris et al. 2020). The NUMPY package is fun- damental in numeric computation, hence, is reasonable to assume that LinTS implementations will depend on NUMPY. In fact, this non-deterministic multivariate normal distribution functionality is used in existing LinTS implementations found STRIATUM STreAMINGBANDDr and DEEP BAYESIAN BANDETS as can seen in their Github repositories. We find the underlying cause to be prevalent across the open source community This casts shadow the reproducibility of any work relying on these librarics, and on any research that relies on NUMPY's multivariate normal sampling.
Unfortunately, such non-deterministic behavior is not documented. The issue is neither discussed online nor in previous literature. Despite the popularity of LinTS and its applications, the susceptibility of its Python implementation to undesired non-delerministic behavior not widely known. A general user who sets a specific sced for the pscudo-random generator, might expect deterministic results when no there are no inherent parallelism or asynchronous behavior. This user would remain oblivious to the fact that their work cannot be replicated across different environments. This is exactly what would like to raise awareness for and address in this paper.
1.1 Our Contributions
First, we would like to bring attention to the non-detorministic behavior of LinTS which is not discussed in the original paper. This issue concerned with LinTS implementation in Python. Therefore, is not within the immediate scope of the original work. Our main contribution is to track down the root cause of non-determinism to Singular Value Decomposition (SVD) (Golub & Reinsch 1970) of the covariance matrix when generating samples from the multivariate normal distribution.
As remedy, we show that the issue can be avoided using Cholesky Decomposition (Gentle 1998 instead of SVD, given that Cholesky's assumptions hold. We prove that using the Cholesky method is sound in the LinTS setting and then verify this numerically with extensive experiments across multiple environments
5 https////ehhab.ccm//eeeorotooo htt.///ooooooooe/////oe 6 hhttps///gthhubaa httpp:///ghhubbcoo//fflllltttttt httpa////wwnnnaie/////////////// reprodduciiilyyy
http////eeeaeaaee//eeeeeeeee ( contextual bandits
2

---

Published in Transactions on Machine Learning Research (07 (2022)
We also demonstrate that the DEEP BAYESIAN BANDITS paper [Riquelme et al., 2018]: which proposes new benchmark for bandits, suffer from the same reproducibility issue Based on our proposed approach, for reference, we contribute an open-source deterministic LinTS implementation in Python as part of our MABWISER library [Srong et al. 2021 2019 Finally, we stress that using Cholesky decomposition is not the default setting any NUMPY version when sampling from the multivariate normal distribution, and for best practice, we point out where special attention required. This extends our contribution to other works beyond LinTS into broader recommender systems and IR community.
1.2 Organization of the Paper
We start with brief background on bandits and LinTS in Section 2 Readers familiar with it can skip S where we explain the non-deterministic behavior and its rool cause. We then demonstrate the issue with a minimum example in Section 3.2 While non-determinism is a scrious concern, thankfully, it is easy to address prove in Section 4 Finally, computational results in Section [
quantify the impact of this issue on well-known recommendation benchmarks in terms of both raw scores and downstream evaluation metrics.
2 Background
In multi-armed bandits, an agent makes a sequence of decisions at time points t t= .,,,, whereby, at each time t, the agent chooses an arm a, from a set of K arms. A single-arm is selected in the default case, while & arms can be selected in lop-k/slate recommendation setting (Swaminathan et al. 2017). After choosing one or more arms, reward r; R is observed for each selected arm from an unknown model of stochastic or deterministic outcomes. The rewards for other arms remain unknown. In contextual bandits, the agent also observes side information corresponding the state of the environment at time t. This side information is referred to as contert and is defined as Ia E Rdd The arm with the highest expected reward E[re|as] differs depending on this context. The uncertainty of the expected reward may differ based on context, which can impact decisions the exploration strategy leverages that information.
In the Regret Minimization approach to optimizing bandit algorithms, the performance of a bandit algorithm is evaluated the cumulative reward given by Ei=1 Tt: or equivalently, on the cumulative regret incurred by the learning policy. If define reward rf the reward if the optimal action is chosen at time I, an optimal policy will generate a cumulative reward of r" = rf: and the expected cumulative regret can be represented as: B[r*] E[r]. Overall, the objective of both context- and contextual bandits is to maximize the cumulative reward, and equivalently, minimize the cumulative regret, which is the primary objective of the Regret Minimization task.
There exist a variety of learning policies that address the exploration strategies include frequentist (c-Greedy (Sutton & Barto 2018), SoftMax (Sutton & Barto 2018). UCB (Auer et al. 2002 and Bayes-basee (TS) approaches {Russo et al. 2018). In context-free bandits, the TS learning policy observes the number of successes and failures, generates beta distribution for each arm, and samples from the beta select the next arm. In contextual bandits, LinUCB (Li al. 2010 and LinTS (Agrawal & Goyal 2013) the popular choices.
trade-off. The different
2.1 LinTS
The LinTS algorithm (Agrawal& & Goyal 2013) is the Bayes-based competitor of LinUCB. The main principle behind the LinTS approach is that the parameters used in ridge regression sampled from multivariate normal distribution. This follows the Bayesian assumption that model parameters are not fixed and have prior distributions that can be revised upon obscrvations. Algorithm 1 presents the details of Thompson Sampling with linear payofTs.
The LinTS algorithm starts by initializing a ridge regression for each arm. Notice that this uses the same A_ (XTX, + Ma)- from LinUCB, with X, again, as the regularization strength. In the initialization
We plan open issues relevant repositories share and rectify the problem.
3

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Algorithm 1: Thompson Sampling with Linear Payoffs (LinTS)
Initialization for each
Ag ATa, X a 0", ANaa 0d
for t = 1, 2, ..., T do 1. For each arm sample Sto from distribution Nupuas a²
2. Select arm, = argmara(Z
3. Observe reward Fz
4. Update the selected arm:
Ag f Aa + +27 It
X ra t X ra xf
Buo- t A 2
step, there exist no Xa observation, making the starting value of Aa equal to Xla. The other components of the ridge regression, X and 3 are initialized with zeroes.
At each time point f, multivariate normal distribution is generated for each arm with the mean as the current 3 parameter of the arm, denoted by 3pa- For the covariance matrix, M a² A² is used, where is the exploration factor. A sampled Bto vector is drawn from this distribution. The non-deterministic behavior addressed in this paper occurs in this step (Step 1).
Next, the sampled values are used in the standard ridge regression calculation 2r,re to generate the expectation of the arm. The arm with the maximum expectation selected (Step 2), and a reward v, is obsorved (Step 3). Basod on the reward of the select arm, A and Bpa are updated accordingly (Step 4). At time / + 1, and so on, the 3 samples can be generated from revised multivariate normal distributions, and the algorithm proceeds.
3 Non-Deterministic Behavior of LinTS in Python
At inference time with a new context vector Tt, based on the trained parameters Sp and A, the LinTS scoring procedure for each arm as follows:
1. Find the inverse A of the trained model parameter A.
2. Scale A-1 with the exploration parameter a² to find the covariance matrix M a²A-1.
Sample d-dimensional vector from the multivariate normal distribution defined by the mean B,. from the training and the covariance matrix M.
Find the dot product of the context vector of with the sampled parameters 3 generate the likelihood.
In Python, a standard and straightforward implementation this procedure uses the multivariate normal distribution functionality from the NUMPY package. Figure outlines the corresponding implementation, which can be used to retrieve the score of specific arm given the context vector o, (x) and the parameters 8pm (beta_mp mu) and A (A_ (A_inv). The figure shows both the RandomState class usage (Option 1), which has been deprecated in July 2019 with version 1.18, and the new Generator class usage (Option 2). The multivariate normal distribution function provided in the RandomState generator uses SVD (Golub & Reinsch 1970) to decompose the covariance matrix, which leads to non-determinism. Similarly, the new Generator class exclusively used SVD until the version 1.19 release in December 2019, which means that any implementation to that date has inherited the issuc. To date, SVD remains the default option as the underlying decomposition technique in the multivariate normal distribution for both Option and Option 2. In other words, any implementation similar to Figure T is problematic.
4

---

Published in Transactions on Machine Learning Research (07/2022)
Option 1) Randon number generator Legacy, Deprecated
rug up randon. RandomState (seed=42)
Option 2) Randon number generator - New Generator class rng np randon.... default_xng (42)
# Scoring function def get_acore_of_arate beta_mu, A_inv, alpha=1):
Scaling with the exploration parameter
M (quare(alpha) + A_inv
Multivariate sampling beta_ sampled mng.uultivariate..nnr (beta_mu,
Score the arm
return up dot (x, beta_sampled)
Figure 1: Python implementation the LinTS scoring function for each arm in the multi-armed bandit. 3.1 The Root Cause Behind Non-Detene non-Determinism
We narrow down the root cause of the issue to multivariate sampling. While it is not acknowledged in the
NUMPy documentation, there exist few thread discussions in GitHub issues (#243: # #13597 # m and # #1335: that point to this underlying cause: the NUMPY multivariate sampling implementation guarantees the distribution of the samples but not the values of the samples.
Specifically, given the mean vector of dimension d and the covariance vector M of dimension d x d, the aativariite_normat function generates new samples as follows:
Decompose the covariance matrix M into matrix L.
Randomly sample values from the standard normal distribution b.
3. Add the mean vector m to the dot product of the randomly sampled vector and the decomposed covariance matrix to give the final vector 8.
How the matrix L generated in the first step of the algorithm depends on the underlying decomposition method. As mentioned in Section both the deprecated RandomState and the newer Generator classes use SVD.
The root cause of the non-determinism is, unfortunately, in the NUMPY's implementation of SVD. When singular values equal, they returned in non-deterministic order. This subtle side effect is reported least early as 2012 in issue #2435. To make it worse, the issue is marked as "wont-fix" as the scope of this SVD implementation does not provide any guarantee on the values but only on the resulting distribution. As stated in issue # 13358,, the ordering of singular values is left to be determined by the underlying linear algebra library. Consequently, even when the seed value fixed, sampling from a multivariate distribution with repeated singular values the covariance matrix can lead to different. results depending on the linear algebra library in the backend.
To confirm this behavior, show that with the exact same seed and NUMPY versions, the sampled values are in fact different depending on whether NUMPy is installed with Linear Algebra Package (LAPPACK) (An-
derson et al. 1999), Basic Lincar Algebra Subprograms (BLAS) Blackford et al. 2002). Open Source Basic Linear Algebra Subprograms (OpenBLAS) (Xianyi 2011 or Intel Math Kernel Library (MKL) [Intel 2003
Not only that, but due to numeric instability, there no guarantee that results will remain reproducible even on the same machine with the same lincar algebra backend.
/isuuup///ssus///// /2435
httpp/////ghaaabb//////////uu/// 133997

---

presents toy Published in Transactions on Machine Learning Research (07 (022))
In the context of LinTS, the issue manifests itself with the mean vector f Ap the covariance matrix M <- a² A- and the output 3. When the random sampling from the multivariate normal distribution is not guaranteed to be deterministic, then the inference made by Lin'SS is not reproducible. Notice that repeated singular values in the covariance matrix can naturally occur depending on the data.
Within the broader context of contextual bandits, that may be affected by the same issue. In general, UCB-based algorithms such as LinUCB (Li al 2010)) and UCB-based Generalized Linear Bandits [Li et al. 2017 Kveton et al 2020 which compute the optimal action without stochastic component, hand, TS-based contextual bandits such as PG-TS (Dumitrascu et al. 2018). and TS-based Generalized Linear Bandits such as GLM-TSL (Kveton et al. 2020) and SGD-TS (Ding et al. 2021) may be susceptible to non-determinism issues, as they inchude components that randomly sample from multivariate normal distribution.
important be on the lookout for other algorithms
not susceptible to this -etermmmeinn issue. On the other
In Section 5 our experimental analysis demonstrale that when the matrix of context vectors used in the training data is not linearly independent different scores generated depending on the compute environ- ment.
3.2 Minimal Example to Reproduce the Error
Let us finish this section with a minimal example to make the issue more concrete. Figure 2 training and test data sets with three arms.
# Three arms [1, 3]
Training data
decisions np array ([1,
2, 2, 3, 3, 3, 3, 31)
rewards array ([O,
1, 0,
0
0, 0,
1, 1, 11)
contexts arra ([[O,
1, 2, 3,
61
[1,
1, 1, 1, 11
[0, 0, 1, 0,
0]
[0,
2,
2, 3,
[1, 3, 1, 1,
11
[0,
0,
0,
0, 0]
[0, 1, 4, 3, 5].
[0,
1,
2,
4, 5]
[1, 2, 1, 1, 31, [0, 2,
1, 0, 0]1)
# Test data teat_context = array ([O, 1. 2, 3, 5))
# Output
>> (1, **2*8, 3, 3, 3) (with MKL NumPy v1 18)
# >> [1, $*1*8, 3, 3, 3) (with OpenBLAS NumPy v1.18 18)
Figure 2: Example to reproduce non-determinittic LinTS.
We run this example using the LinTS implementation given in Figure 1 on the same operating system (Mac OS) with the same Python and NUMPY versions, and the same seed value for the random number generator. As can be seen in the result: [3 the LinTS algorithm generates different results for the same context vector in the test data depending on the linear algebra packages MKL and OpenBLAS. Ancedotally, we encountered different results even with the same linear algebra package between two runs on the same machine. With larger number of arms, higher dimensional context vectors, and larger training and test data sets, we expect to greater frequency of such discrepancics. We demonstrate this effect further in Computational Results section.
/hhttps//gthhhub.cm//feellll additional ceciiiima___epppemeettttesse minimal

---

Published in Transactions on Machine Learning Research (07/2022)
4 How to Guarantee Deterministic Thompson Sampling
The SVD implementation in NUMPY package returns singular values in sorted order. This suffers from insta- bility when there are equal values. As a remody, we need a technique that bypasses instability from pivoting or sorling operations and returns unique results. The Cholesky decomposition one such method (Gentle 1998). In the sections below, we show why Cholesky decomposition is an appropriate alternative SVD within the context of the LinTS algorithm 14
4.1 Cholesky Decomposition
The Cholesky decomposition operates over Hermitian positive definite matrix and docomposes it into lower triangular matrix and its conjugale transpose. It does not involve singular values eigenvalues, follows predictable set of steps with no pivoting or branching operation, and avoids the sorting problem. This yiclds deterministic behavior, up to numerical rounding errors, across different linear algebra packages. When reproducibility is of concern, Cholesky decomposition is one of the most recommended alternatives to SVD for multivariate normal sampling, see e-g. NUMPy GitHub issues # #13558 and #13597.
The main requirement of Cholesky decomposition is its reliance on Hermitian positive definite matrices. In LinTS, the decomposition is applied to the covariance matrix M A for which we need to guarantee positive definiteness.
LEMMA 4.1. In LinTS, the covariance matrix M = === is positive definite.
We observe that before any training, the matrix is initialized as Ala, which is a real symmetric diagonal matrix, and therefore positive definite. During the training process, as shown in Al- gorithm [ the matrix A is updated using 2ąait' where x, is a real-valued columnar vector, which leads to 2,22 being real symmetric positive semidefinite matrix. This addition of A and 2,27 has been shown to generate positive definite matrix (Hoerl & Kennard] 1970), that is, the matrix A remains positive definite during training. Since the inverse of positive definite matrix is also positive definite (Horn & Johnson, 2012 the mairix A-1 is also positive definite. The covariance matrix M thus remains positive definite, making Cholesky decomposition appropriate for use during LinTS implementation.
PROOF.
Fortunately, in its recent versions, NUMPY introduced the option to select the decomposition method used for the multivariate normal sampling. The new Generator class provides this option in release 1.19 with Cholesky being one of the alternatives. We note that SVD remains to be the default option.
To ensure deterministic implementation of LinTS in Python, we recommend the following:
The multivariate normal function the legacy RandomState number generator (Option 1) should not be used in LinTS implementations since it uses SVD exclusively. If RandomState must be used, e.g., for backwards compatibility, recommend custom implementation of the sampling function.
2.
The new Generator (Option 2) is suitable for LinTS. The important distinction is that instead the default SVD option, Cholesky should be selected when sampling from the multivariate normal distribution.
Make sure to select Cholesky decomposition beta_ sampled rng.mul www.amtvrratteeorreeeeaa (heta_mu, M, method=' 'choled"choleskky
Figure 3: Cholesky decomposition for deterministic multivariate normal sampling.
Our running implementation illustrated in Figure I can be modified to adhere to these guidelines in Figure 3 With this minor update, the minimal example in Figure 3.2 now returns identical results. The adverse impact of not following these suggestions is demonstrated next.
We would also like acknowledge our action editor Lihong Li's suggestion of adding small noise to the initialization of the matrix A. Our initial empirical findings confirm that an appropriately sized noise deterministically applied the diagonal of the matrix the time of initizlization can be another potential salution.
7

---

Published in Transactions on Machine Learning Research (07/2022)
OPERATING SYSTEM (OS)
OS VERSION
NUMPy LA BACKEND
Windows
10.10
OpenBLAS
Red Hat Linux
3.10
OpenBLAS
MacOS Darwin
10.15 (19.6)
OpenBLAS
MacOS Darwin
10.15 (19.5)
MKL
Amazon AWS Limux
4.14
LAPACK
Table 1: Environments considered in our experiments with varying operating systems and linear algebra backend.
5 Computational Results
In the previous soctions, we explored non-determinism in LinTS, revealed the root cause behind the problem, and proposed simple solution with easy-to-follow best practices. What remains to be is computa- tional study to quantify the impact of the non-deterministic behavior and understand the extent it impacts downstream tasks and metries. In particular, the goal of our experiments is to answer two main questions:
[Q1] What the similarity between the results produced by a non-deterministic implementation of the LinTS algorithm under different environment setups? Does a deterministic implementation resolve this dissimilarity?
[Q2] Does the issue manifest itself in standard benchmarks and existing Python libraries, and what is its impact on relevant evaluation metrics?
To answer these questions, we consider Recommendation System as our application domain, where LinTS is commonly used, and conduct experiments on the well-known MovieLens data set (Harper & Konstan 2016). As negative result, observe that when using SVD, the recommendations exhibit considerable discrepancies in both generated item scores and recommendation metrics. Practitioners might attribute such performance differences incorrectly to algorithmic improvements while it is solely due to non-determinism.
As a positive result, we find that using Cholesky yiclds identical results across all environments, independent of the OS and the linear algebra backend. This confirms our proof experimentally and verifies the effectiveness of our proposed solution. Finally, we focus on Google Brain's DEEP BAYESIAN BANDITS library (Riquelme) et al. 2018 to test 3rd party implementation, confirming it also suffers in terms of reprodueibility.
5.1
Environment Setup
Table ! provides the list of environments considered in our experiments. We target mainstream operating systems Windows, Linux, and Mac OS. We also include Amazon AWS Linux as an example of cloud service provider. In parallel, we consider three different linear algebra backends: Open Source Basic Linear Algebra Subprograms (OpenBLAS) (Xianyi 2011h, Linear Algebra Package (LAPACK) (Anderson et al. 1999 and
Intel Math Kernel Library (MKL) [Itel 2003). Note that even with the same underlying linear algebra package, there can be differences between operating systems.
5.2 Numerical Results MovieLens Data
We use the well-known 100K MovieLens data set (Harper & Konstan 2016) with 100K ratings from 943 users for 1682 movies. For TS, we binarize the data set for each uscr-movic pair with positive reward if the user rated the movie and zero otherwise. This gives us 1.58M observations with 100K positive responses. We divide it into 70%-30% train and test splits. The user context includes age, gender (boolean), occupation (onc-hot), and the ZIP code (ordinal). We augment this context with a column representing an unknown occupation (none or other). This minor feature engineering creates linear dependence in the data and duplicate singular values in A-1 matrix.
8

---

Published in Transactions on Machine Learning Research (07 (0222
ENY
COMPARISON
RED HAT LINUX
Score
0%
Prediction
32.64%
Score
0.00021%
4.2e-4%
MACOS MKL
Prediction
43.87%
67.36%
MACOS OPENBLAS
Score
0%
100%
0.00042%
Prediction
32.64%
100%
67.36%
AWS LINUX
Score
0%
100%
0.00042%
100%
Prediction
64%6
100%
67.36%
100%
RED HAT
MACOS
WINDOWS
MAc MKL
LINUX
OPENBLAS
Table 2: Numerical Results on MovieLens: Comparison of the percenlage of matching raw user-item scores and matching predictions on whether to recommend the item across environment pairs when using SVD- based LinT'S implementation. A reproducible result should match 476,006 (100%) times as shown in bold. Any other result is a discrepancy due to non-deterministic behavior.
NDCG
PRECISION
RECALL
ENVIRONMENT
CR
@5
@10
@25
@5
@10
@25
@5
@10
@25
Windows
37
0.0166
0.0244
0.0399
0.1251
0.1208
0.1102
0.0064
0.0118
0.0265
Red Hat
54
0.0201
0.0286
0.0457
0.1399
0.1300
0.1175
0.0070
0.0132
0.0297
MacOS MKT.
40
0.0181
0.0270
0.0418
0.1336
0.1265
0.1124
0.0071
0.0132
0.0271
Mac OpenBLAS
54
0.0201
0.0286
0.0457
0.1399
0.1300
0.1175
0.0070
0.0132
0.0297
AWS Linux
54
0.0201
0.0286
0.0457
0.1399
0.1300
0.1175
0.0070
0.0132
0.0297
Cholesky (for all)
31
0.0131
0.0190
0.0312
0.0926
0.0905
0.0858
0.0048
0.0090
0.0203
Table 3: Numerical Results on MovieLens Data: Comparison evaluation metrics at different top-k set- tings across different environments when using SVD-based LinTS implementation, The last row shows the Cholesky implementation that is identical for all environments.
Table presents results that compare all pairs of environments the MovieLens data using the SVD- based LinTS implementation. The table contains the matching percentages for the raw user-item scores generated by LinTS, and whether both environments made the same prediction on recommending the item to the user. Ideally, we expect 476,006 matches, as shown in bold. We find that this is the case for three pairs of environments, which match 100%, while the others have an low percentage of predictions match and very few matches in scores. Let us note, compared to our variant. of the Movielens dataset studied here, real-world datascts might capture richer structure that could Icad to even worse discrepancies.
Table 3 presents the results for recommendation metrics for different top-k recommendations from 5 to 25, and the cumulative reward (CR) when only single arm is selected. The cumulative reward is calculated as the sum of rewards across the rocommendations of the model, and recommendation metrics follow their standard definit (Sun et al. 2020). As can be seen, the failure of matching scores propagates rean and causes significant differences in the evaluation metrics. The NDCG@5 difference between Windows and MacOS OPenBLAS cnvironments enough to change the outcome of an experiment, leading to incorrect conclusions. When using Cholesky decomposition instead, as we expect from the theory, all environments return the scores 100% of the time, leading to identical metrics.

---

Published in Transactions on Machine Learning Research (07/2022)
OS
BACKEND
RS
SVD
CHOLESKY
MacOS Big Sur
MKL
4135
3575
4140
MacOS Big Sur
OpenBLAS
3720
3830
4140
Ubuntu 18.04
MKL
3475
3540
4140
Ubuntu 18.04
OpenBLAS
4075
3875
4140
Table 4: Numerical Results with the DEEP BAYESIAN BANDIT Library: Comparison of the cumulative reward across different environments when using the SVD-based and Cholesky-based Lin implementation. The identical reward are shown in bold. Any other result is a discrepancy due to non-deterministic behavior.
5.2.1 Additional Experiments:
We conducted further experiments on other recommendation benchmarks such as the GoodReads data set. (Wan & McAuley 2018) with review-based user features generated by TEXTWISER (Kiliteioglu & Ka- dioglu 2021), MovieLens with parameter tuning, and on synthetic dataset. All of these additional experiments lead to the same conclusion and are omitted here.
5.3
Numerical Results with the Deep Bayesian Bandits Library
As our final experiment, we turn our attention an existing library and test an implementation aside from our own, focusing the DEEP BAYESIAN BANDITS library from Google Brain (Riquelme et al. 2018
This library contains the LS algorithm to account for its baseline approach. The LinTS implementatior of the paper (Riquelme et al.
2018 makes a sampling call to the multivariate, poattte__ammlll function as we warned against in Son 3 Crucially, the LinTS algorithm shows the best cumulative regret for the UCI mushroom data set euta & Graff 2017 in this paper (Riquelme et al. 2018), which calls for verification.
Many thanks to our authors who provided example code to reproduce their table, we were able to run their code to test whether this LinTS algorithm is prone to reproducibility issues We the UCT mushroom data set & Graff, 2017) in bandit task (Blundell et al., 2015).. taking sample of 2000 to fully mimic the example. We then compare the reproducibility across three different approaches:
RandomState (RS): The legacy option from Figure which uses SVD. The DEEP BAYESIAN BANDITS library implements this option. We plan to reach out to the contributors this library to share our findings.
SVD: The newer Generator class for random number generator that uses the default SVD decompo- sition, as shown in Section 3
The newer Generator class that explicitly specifies the Cholesky docomposition (Fig- ure 3) This the suggested method of our paper.
Cholesky:
To measure the difference, use the cumulative reward generated by the LinTS policy, which is used to select the best performing policy when comparing bandit algorithms. It is therefore critical that the rewards are reproducible.
Table 4 presents the results which show that the cumulative reward differs considerably across different environments for SVD-based implementations. Once again, we show that using the Cholesky dccomposition alleviates the problem completely, producing the same reward across all environments. Note that in contrast to the recommendation metrics in the previous example, Cholesky leads to better performance in this task.
additiiona www.:////t/o/o/////oo/o /wtps//foww//o/d////bbbaoaaaee
cttpccoccrrreepppppccoottttttl contextual banditsstlbbbaii///aoa//
_flll_ootterirr______1 banddss/algorrthms/lleezs full posterior p_t_pprioorsamplllgnnnnpp hamplinggpy#41.90
17 "htttss//gthhub.cmmfffii hwttitt///mmbweeeeeeeeeeeeeeeeee /ttp://lll//iitaaaaeaettttiiiiie
10

---

Published in Transactions on Machine Learning Research (07/2022)
This also calls the existing results into question. Our findings indicate that the previous results will not be reproducible even if we were to use their exact implementation. We reiterate our recommendation for using the Cholesky decomposition to ensure deterministic LinTSS behavior, which also applies to Google's DEEP BAYESIAN BANDITS [Riquelme et al. 2018 library as well as any academic or industrial work that depends on it.
6 Conclusion
Almost ten years after the impactful LinT'S paper (Agrawal & Goyal 2013), we presented a detailed treat- ment of the subtle non-deterministic behavior that jeopardizes its implementations in Python. LinTS offers great versatility in quantifying uncertainty and provides a principled mechanism for exploration. However, attention is required to guarantee deterministic behavior as we advocated in this paper.
We identified the root cause of the issue, discussed potential sources of instability that can lead to unwanted behavior, provided a minimal example and multiple experiments reproduce the error, and studied it in details. Our experiments demonstrated that the issuc manifests itself in well-known recommendation bench- marks, impacts existing libraries and any work that utilizes NUMPY's multivariate sampling implementation, and can be detrimental to computational results and conclusions drawn. Finally, and most importantly, we described a simple fix based on Cholesky decomposition to rectify the issuc within the context the LinTS algorithm. We proved the soundness of the technique and shared general advice with practitioners and researchers.
Our open-source contextual multi-armed bandit library, MABWISER (Strong al. 2021 2019 is released with this deterministic LinTS implementation reference. Overall, our findings take step toward reproducible AT research and hopefully motivate others not to overlook such important issues forgotten implementation details that might influence scientific conclusions.
Acknowledgments
We would like to thank Anshuman Pradhan and Pramod R for bringing this issue to our attention, and to Emily Strong for providing the initial implementation in MABWISER (Strong al.) 2021 2019). We would also like to Chank our anonymous reviewers and our action editor Lihong Li for their reviews and feedback which has helped improve this work.
References
Mare Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. Electronic Journal of Statistics, 11(2):5165 5197, 2017. doi: 10.1214/17-E/S144155 URL
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Inter- national Conference on Machine Learning, pp. 127-135, Atlanta, GA, USA, 2013. PMLR, JMLR.org.
E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Ham- marling, A. McKenney, and D. Sorensen. LAPACK Users' Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA, third edition, 1999. ISBN 0-89871-447-8 (paperback).
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 27(2-3):235-225) 2002.
L Susan Blackford, Antoine Petitet, Roldan Pozo, Karin Remington, R Clint Whaley, James Demmel, Jack Dongarra, Tain Duff, Sven Hammarling, Greg Henry, et al. An updated set of basic linear algebra subprograms (blas). ACM Trans. Math. Softw., 28(2):135 151, June 2002. ISSN 0098-3500, doi: 10.1145/ 567806.567807. URL https://doi. http://to..ogg//// 10e. 11t.11111/666666555558 567807
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference
11

---

Published in Transactions on Machine Learning Research (07/2022)
Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. Lille, France, 07-09 Jul 2015. PMLR. URL http://proceedings.mt wtt.m..pppee.e../..e/ee//ee
html
Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Balanced linear contextual bandits. Proceedings of the AAAI Conference Artificial Intelligence, 33(01):3445 3411)33345-343,, 2019.
Qin Ding, Cho-Jui Hsich, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics, pp. 1585 1593. PMLR, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.ice. edi. m1
Bianca Dumitrascu, Karen Feng, and Barbara Engelhardt. Pg-ts: Improved thompson sampling for logistic contextual bandits. Advances in neural information processing systems, 31, 2018.
Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouricch, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks on linear contextual bandits. Advances in Neural Information Processing Systems, 33, 2020.
James E. Gentle. Solution of Linear Systems, pp. 87-121. Springer New York, New York, NY, 1998. ISBN 978-1-4612-0623-1. doi: 10.1007/978-1-441226622 3. URL. https::/bbd..org/11110000 org/10..0077 978-1-4612-0623-11
Gene H Golub and Christian Reinsch. Singular value decomposition and least squares solutions. Numerische mathematik, 14(5):403 420, 1970.
Nicolas Gutowski, Tassadit Amghar, Olivier Camp, and Fabien Chhel. Gorthaur: : A portfolio approach for dynamic selection of multi-armed bandit algorithms for recommendation. In 2019 IEEE 31st International Conference on Tools with Arlificial Intelligence (ICTAI), pp. 1164 1171, Portland, OR, USA, 11 2019. IEEE. doi: 10.1109/ICTAA.2019.0000
Nicolas Gutowski, Tassadit Amghar, Olivier Camp, and Fabien Chhel. Gorthaur-exp3: Bandit-based selec- tion from a portfolio of recommendation algorithms balancing the accuracy-diversity dilemma. Informa- tion Sciences, 546:378 396, 2021. ISSN 0020-0255. doi: https:///ooi.org/11000 hns com wttp://e....ceccccc////errrtteae htt.://cwc.....aac..c.....aaaaaa
URL
bttts:///ww..cciencehe
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):19, 2016.
Charles R. Harris, K. Jarrod Millman, St'efan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fern'andez del R'1o, Mark Wiebe, Pearu Peterson, Pierre G' G'erard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Wockesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, URL https:///oi. http:/://ooooor//o...oo.. 1038/
585(7825):357-3306 September 2020. doi: 00003//441880-00022200 1115866-0002649-2
Arthur E Hoerl and Robert W Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55-67, 1970.
Roger A Horn and Charles R Johnson. Matrir analysis. Cambridge university press, USA, 2012.
Intel. MKL: Intel Math Kernel Library Source Basic Linear Algebra Subprograms, 2003. URL. https:
//docs. aaaconda.com//iitn anacoonn..cco//lllooottaaaaaaaae htm
Doruk Kilitcioglu and Serdar Kadioglu. Representing the unification of text featurization using a context-
free grammar. In The Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, The Thirty- Third Innovative Applications of Artificial Intelligence Conference, IAAI 2021. AAAI Press, 2021. URL
12

---

Published in Transactions on Machine Learning Research (07/2022)
Jules Kruijswijk, Robin van Emden, Petri Parvinen, and Maurits Kaptein. Streamingbandit; experi- menting with bandit policies. arXiv preprint arXiv: 06700, 2016. URL. attps://github..co
Wth-iteration www.ooaaaaststtainnnnnnna..
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Conference on Arti- ficial Intelligence and Statistics, pp. 2066 2076. PMLR, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandlt approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661 670, Raleigh, NC, USA, 2010. ACM, ACM Press.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Y. A. Lin, Dept. of Computer Science Y. Y. Yang. Computational Learning Lab, and National Taiwan Uni- versity Information Engineering. Striatum. https://giithb..co htt.://w...oomtttcaaa////ttteeee
2016.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown. In International Conference on Learning Representations, Vancouver, Canada, 2018.
Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Tan Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and TrendsI in Machine Learning, 11(1):1 96, 2018.
Eric M. Schwartz, Eric T. Bradlow, and Peter S. Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Mark. Sci., 36(4):500-52) 2017. doi: 10.1287 111287/ksc.2016..1 10233. URL
https://doi. org/ 10. 1287 2228/mksc... 1016610230
Emily Strong, Bernard Kleynhans, and Serdar Kadioglu. Mabwiser: A parallelizable contextual multi- armed bandit library for python. In 2019 IEFE 31st International Conference on Tools with Artificial Intelligence (ICTAI 2019), pp. 885 890, Portland, OR, USA, 2019. IEEE, IEEE. URL https://gs thub.
com//iidelity/mabwiie.
Emily Strong, Bernard Kleynhans, and Serdar Kadiogl. MABWiser: parallelizable contextual multi-armed bandits. Int. J. Artif. Intell. Tools, (014))215002111121500022 2021. doi: 10.1122/1122222/3221500111
URL https://doi.coo htt///i..org/g/// org/10. /111/1/0222221112502222222
Zhu Sun, Di Yu, Hui Fang, Jie Yang, Xinghna Qu, Jie Zhang, and Cong Geng, Are We Evaluating Rigorously? Benchmarking Recommendation for Reproducible Evaluation and Fair Comparison, pp. 23 32. Association for Computing Machinery. New York, NY, USA, 2020. ISBN 9781450375832. URL httpps://oll org/
10. 111111133//111... 3383333333331398999 3412489
Richard S Sutton and Andrew G Barto. Reinforcement learning:: An introduction. MIT press, 2018
Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford, Damien Jose, and Imed Zitouni. Off-policy evaluation for slate recommendation. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnetl (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL ltttps://proceedinggg wtwpoeeedddinn...u.iiiseeeseeepp neurips meurips.cc/papeess cc/paper/ Paper. .dff
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285 294, 12 1933. ISSN 0006-3444. doi: 10. 10.1093/biomet/ 25.3-4.285. URL httph:::// http::///oooooo/11...oo 10.
3-4.2/85
Mengting Wan and Julian J. McAuley. Item recommendation on monotonic behavior chains. In Sole Pera, Michael D. Ekstrand, Xavier Amatriain, and John O'Donovan (ods.), Proceedings of the 12th ACM Conference on Recommender Systems, ReeSys 2018, Vancouver, BC, Canada, Oclober 2-7, 2018, pp. 86 94. ACM, 2018. doi: 00.1145/3240323..
URL httpp:://oii. wttp.....1.//3/20022...... 324036
Zhang Xianyi. OpenBLAS: Open Source Basic Linear Algebra Subprograms, 2011. URL https://wwa openblas.ned .nt//
13


Reviews:
[{"review_id": "3z3MQPREDs", "reviewer": "Reviewer_bVwk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nIt is exciting and inspiring to find a bug that is wide and common. This paper can help prevent reproducibility issues and reduce the engineer efforts for tuning models/parameters, and may have helped some. I personally have seen some similar reproducibility problems in some industry machine learning systems and people were struggling finding a solution. I appreciate the authors to point out this bug and provides a solution.\n\nWeakness\n1. It is unclear how severe this bug is. The authors do not provide enough evidence to show the severity. For the experiments, it is not clear how this non-deterministic issue caused more severe problems than other possible randomness. For instance, in some distributed machine learning algorithms (eg EASGD, an asynchronized optimization algorithm), the completion order of CPUs/GPUs/nodes is random and may also lead to non-deterministic behaviors of the trained models. The authors should be more clear on this point.\n2. This paper needs to justify whether and why Cholesky Decomposition is a better solution compared to making a deterministic implementation of SVD. The content of this paper does not convince me that we should use Cholesky to replace a widely-used and supported algorithm SVD. \n3. Maybe an adversarial example that escalates this bug may help strengthen this paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper points out a reproducibility issue/bug of many popular and widely used implementations of the LinTS (Thompson Sampling with Linear Payoffs) that are based on MumPy's  implementation of SVD (singular value decomposition). LinTS is a fundamental and widely used machine learning algorithm for solving the contextual bandit problems, and has found applications in various areas such as recommender systems and ranking. This but is that: in some implementations of LinTS, multiple experiments with the same random seed, the same Python codes, and the same datasets could return different results, which may cause the results of previous experiments unable to reproduce. The authors also did experiments on real-world movie datasets to show this bug. The root cause of the bug comes from NumPy's implementation of SVD that many LinTS implementations base on. In NumPy's implementation of SVD, when the matrix has two or more equal singular values, then there order in the return results of SVD are not deterministic and may be affected by the devices/systems. Therefore, the LinTS implementations based on it will also be non-deterministic. Then, the authors introduced Cholesky Decomposition for replacing the SVD, which does not have such bug. The authors also provide a LinTS implementation based on it, The authors show that this new implementation always returns the same result in different systems/devices, and thus, fixed this bug. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Resolve the weakness 1 and 2. Resolving weakness 3 is optional but can well strengthen this paper.\n\nFor the current version, I will vote a major revision and want to see weakness 1 and 2 addressed.", "broader_impact_concerns": "This paper does not have ethical concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VKTTPJY8MB", "reviewer": "Reviewer_5XTG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The writing is clear and well organized. The technical problem is explained in a clear way and is supported properly. I don't have clear suggestions for improving this work.\n\nThat said, I consider that the brought contribute might be of benefit for researchers in the bandit area. Hence, as both the technical part seems correct and well supported, and there is a contribute given by this work I am satisfied with it.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work investigates the usage of the well-known Linear Thompson Sampling algorithm in practice. The focus is in evaluating its reproducibility due to its randomness. Authors showed that the original algorithm is actually characterized by a non-deterministic behavior preventing its usage for industrial applications.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I do not have specific changes to request.", "broader_impact_concerns": "I did not find any ethical concern with this work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WrBrfc6EwM", "reviewer": "Reviewer_Sa2S", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work explores how Python will implement the Lin-TS algorithm in great detail and also provide extensive experiment results. This topic is interesting and worth to explore as it will help scholars to develop a better understanding about the implication of TS algorithms.\n1. It is well-organized and generally easy to read.\n\nWeaknesses:\n1. Section 2 \n   1. The first paragraph mentions `top-k recommendation', which seems to relate to the best arm identification/pure exploration (BAI) in multi-armed bandits. However, the second paragraph simply suggests that 'The performance of a bandit algorithm is evaluated on the cumulative reward'. (Regret Minimization/RM)   \n   1. In general, BAI and RM are two common targets in the field of multi-armed bandits. I think this section should describe and distinct these two targets and provide more references to relating works.\n   1. I understand this work is mainly about the experiments of LinTS (a RM algorithm), but a clear description on the context is still appreciated. A clear introduction of multi-armed bandits can be found in many existing works such as the book ['Bandit Algorithms'](https://banditalgs.com/).\n   1. Besides, the notation $E[r|a]$ is used in the first paragraph but the definition of neither 'r' nor 'a' is clearly explained.\n1. Section 5\n   1. I can understand the claim of the authors from the paragraphs, but the results look confusing to me since I don't quite understand how the comparison is done. Is the cumulative regret applied to evaluate the performance of the algorithm?\n   1. How many times have the same setup been simulated?\n   1. What is the meaning of 'Score', 'Probability', and 'Prediction' in Table 2?\n   1. May you provide more explanations on the evaluation metrics and environment setups in Table 3? What do 5, 10, and 25 stand for?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focuses on the non-deterministic behavior of the Lin-TS algorithm, which is claimed to be caused by the SVD calculation in the application of Lin-TS (the step involving multivariate normal distribution function in particular). It studies this topic by exploring how the general tool, Python, implements each step of the algorithm and suggests that this issue may be addressed by replacing SVD with Cholesky decomposition.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "In general, I believe this work is interesting and worth attention. However, I suggest some changes to convince me the claims are reasonable as detailed in the 'Strengths And Weaknesses' part:\n1. In Section 2, a more detailed introduction of the background is appreciated, which will also help the readers to understand how the performance of LinTS is evaluated in the experiment section (LinTS was originally proposed for regret minimization as I know).\n1. In Section 5, more explanation on the results may help understanding. I do believe the conclusions are reasonably drawn from the experiment results, but currently it is a bit difficult for me to understand the tables now.", "broader_impact_concerns": "No concerns on the ethical implications of the work in my view.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies a reproducibility issue in popular implementation of LinTS based on NumPy's SVD implementation. Given wide application of LinTS and popularity of NumPy, reviewers find the problem and solution to be relevant and useful to the community. They also agree that the solution is technically sound and well supported, and that the writing is of good quality. The responses also answered some of the questions in initial reviews. All reviewers are positive about this work, so I'd like to recommend Accept with Minor Revision.

In addition to what reviewers have pointed out, I'd like to add two suggestions, and look forward to responses in the revision:

First, nondeterminism happens when two singular values are the same. Would it be an easier fix to add a small, deterministic perturbation to diagonal elements when initializing matrix A (first line of Algorithm 1)? If the perturbation is different in element, and the magnitude is small, we will get almost identical performance as unperturbed LinTS, and the chances of seeing non-deterministic results are essentially 0.

Second, while the paper focuses on LinTS, can the authors have a discussion of whether nondeterminism happens in other similar algorithms, such as LinUCB, and TS with generalized linear models, etc.? While the answers may be straightforward in some cases, it'll still be helpful to make them explicit.
Decision: Accept (poster)