PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits
We address the problem of regret minimization in logistic contextual bandits, where a learner decides among sequential actions or arms given their respective contexts to maximize binary rewards. Using a fast inference procedure with Pólya-Gamma distributed augmentation variables, we propose an improved version of Thompson Sampling, a Bayesian formulation of contextual bandits with near-optimal performance. Our approach, Pólya-Gamma augmented Thompson Sampling (PG-TS), achieves state-of-the-art performance on simulated and real data. PG-TS explores the action space efficiently and exploits high-reward arms, quickly converging to solutions of low regret. Its explicit estimation of the posterior distribution of the context feature covariance leads to substantial empirical gains over approximate approaches. PG-TS is the first approach to demonstrate the benefits of Pólya-Gamma augmentation in bandits and to propose an efficient Gibbs sampler for approximating the analytically unsolvable integral of logistic contextual bandits.
This submission tries to propose Polya-gamma augmented Thompson sampling from a frequentist-derived algorithm whose likelihood is a mixture of Gaussian and PG mixing distribution when the reward is the logistic model with binary observation in contextual bandits to improve the Laplace approximation based Bayesian sampling. Experiments are demonstrated on the real world data including the public benchmark Yahoo data.  Detailed comments:  Like you admitted the logistic reward is pragmatic, that's why so far very few have been researched on this topic, which makes it difficult to get adopted by the community.   As you stated the example in the news recommendation setting case in the click or not over the item problem, which is the same or similar to recent advances that took over the contextual bandit, see below.  You adopted the traditional Gibbs sampler, where you sample from the PG distribution with M = 100 burn-in steps, for the experiment is fine, but lack of regret bounds to support, that you may want to study more, e.g., see [1]'s section or appendix about TS.  Laplace-TS's batch update is a good pro but did not fully explored at the moment.  Gibbs step M is too tiny and does not well theoretically motivated.  Laplace approximations are sensitive to multimodality is a con.  The sample complexity or size etc would be clearly stated and analyzed.  You played with a toy dataset on Forest Cover Type from UCI where you only reported the result over 100 runs with 1000 trials, I suggest adjusting the performance towards at least, say, 50k or 100k etc. There is no way to adopt some wrong results as illustrated in Figure 4, it may take a while for you to conquer though.  Your major issue is lack of theoretical guarantee or regret (either upper or lower) bound for the proposed algorithm, as it's standard in this field.  The regret gain is not significant from Figure 5 through the experimental report presented, and the benefit of arm's frequency is not conniving as far as I can tell.  You partitioned the UCI dataset to k = 32 clusters by the traditional k-means clustering where you set the reward of each arm to be the average reward in the corresponding cluster, where you might want to change k's values to see the difference.  Missing references: [1] ICML 2017 On Context-Dependent Clustering of Bandits [2] SIGIR 2016 Collaborative Filtering Bandits [3] ICML 2016 Distributed Clustering of Linear Bandits in Peer to Peer Networks  Where the exactly same Yahoo today module benchmark data is employed, in this sense that your proposed solutions should be able to compare with the state-of-the-art overtook traditional contextual bandit[1-3], which I am curious to see the empirical comparison at least with either one of [1-3].  Since there is no regret bound provided in this manuscript, the empirical result as described and in Figure 4 which showed that your result is wrong or inconsistent on your implementation for conducting the experiment on Yahoo, see more details on how to do legitimate experiments therein in [2,3] to observe the correct performance behavior you should achieve.  The discussion is not really a discussion part, and the real conclusion is missing. Please differentiate these two sections and wrote them separately.  Last but not least, this manuscript should be written in a more professional English writing including to fix typos and grammar errors etc, e.g., "Motivated by our results" and so forth. You should carefully address these concerns to increase the quality of this submission.  %Update after rebuttal% I read their rebuttal, and they did a good job on the clarifications. I have increased my score, and I have no problem to accept this submission.