arXiv research

Improved Thompson Sampling for high-dimensional sparse bandits.

VITS improves Thompson Sampling for contextual bandits with efficient approximate inference.

Thompson sampling is an efficient algorithm for sequential decision making, which exploits the posterior uncertainty to address the exploration-exploitation dilemma. There has been significant recent interest in integrating Bayesian neural networks into Thompson sampling. Most of these methods rely on global variable u…

A new framework for structured bandits using influence diagrams and variational Thompson sampling.

Improves content allocation in educational platforms with sparse data.

DTS improves robustness of bandit algorithms in nonstationary environments.

Thompson sampling provides a solution to bandit problems in which new observations are allocated to arms with the posterior probability that an arm is optimal. While sometimes easy to implement and asymptotically optimal, Thompson sampling can be computationally demanding in large scale bandit problems, and its perform…

We design and analyse variations of the classical Thompson sampling (TS) procedure for Bayesian optimisation (BO) in settings where function evaluations are expensive, but can be performed in parallel. Our theoretical analysis shows that a direct application of the sequential Thompson sampling algorithm in either synch…

New algorithm reduces regret in sequential decision-making problems.

Optimizes Thompson sampling policies using policy gradient methods.

New method targets vaccines for new variants using Thompson sampling.

New Thompson sampling algorithm for stochastic partial monitoring achieves logarithmic regret.

Thompson sampling used for linear bandits with normal-gamma priors.

Thompson sampling has impressive empirical performance for many multi-armed bandit problems. But current algorithms for Thompson sampling only work for the case of conjugate priors since these algorithms require to infer the posterior, which is often computationally intractable when the prior is not conjugate. In this …

Improved Thompson Sampling reduces regret in contextual bandits and reinforcement learning.

Improved Thompson Sampling algorithms for bandits with tighter regret bounds.

Thompson sampling, a Bayesian method for balancing exploration and exploitation in bandit problems, has theoretical guarantees and exhibits strong empirical performance in many domains. Traditional Thompson sampling, however, assumes perfect compliance, where an agent's chosen action is treated as the implemented actio…

Paper improves Thompson Sampling for linear contextual bandits.

Thompson sampling is one of the most widely used algorithms for many online decision problems, due to its simplicity in implementation and superior empirical performance over other state-of-the-art methods. Despite its popularity and empirical success, it has remained an open problem whether Thompson sampling can match…

Extends Thompson sampling for RL with fewer episodes.

Thompson Sampling, one of the oldest heuristics for solving multi-armed bandits, has recently been shown to demonstrate state-of-the-art performance. The empirical success has led to great interests in theoretical understanding of this heuristic. In this paper, we approach this problem in a way very different from exis…

Improved statistical inference for adaptive Thompson Sampling.

This paper applies Thompson Sampling to asymmetric $\alpha$-stable bandits for financial and wireless data.

TS-Insight visualizes Thompson Sampling for better debugging and trust.

Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.

TS-UCB improves Thompson Sampling with minimal extra computation.

Recently, it has been shown how sampling actions from the predictive distribution over the optimal action-sometimes called Thompson sampling-can be applied to solve sequential adaptive control problems, when the optimal policy is known for each possible environment. The predictive distribution can then be constructed b…

Distributed Thompson sampling improves regret convergence in constrained communication networks.

In many biomedical, science, and engineering problems, one must sequentially decide which action to take next so as to maximize rewards. One general class of algorithms for optimizing interactions with the world, while simultaneously learning how the world operates, is the multi-armed bandit setting and, in particular,…

Model shows screening for infectious disease is hard but Thompson sampling works well.

ERTS uses Thompson sampling for Gaussian entropic risk bandits, achieving regret bounds.

New Thompson Sampling for partially observed context bandits reduces regret logarithmically with time.

Thompson sampling for multi-armed bandit problems is known to enjoy favorable performance in both theory and practice. However, it suffers from a significant limitation computationally, arising from the need for samples from posterior distributions at every iteration. We propose two Markov Chain Monte Carlo (MCMC) meth…

Improved Thompson Sampling outperforms existing Bayesian optimization methods.

Thompson Sampling provides an efficient technique to introduce prior knowledge in the multi-armed bandit problem, along with providing remarkable empirical performance. In this paper, we revisit the Thompson Sampling algorithm under rewards drawn from symmetric $α$-stable distributions, which are a class of heavy-taile…

Thompson Sampling bounds for contextual bandits with sub-Gaussian rewards.

Ensemble sampling approximates Thompson sampling for complex models.

We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that (1) asymptotically its …

Neural Thompson Sampling uses deep neural networks for contextual bandit problems.

Thompson sampling has emerged as an effective heuristic for a broad range of online decision problems. In its basic form, the algorithm requires computing and sampling from a posterior distribution over models, which is tractable only for simple special cases. This paper develops ensemble sampling, which aims to approx…

Recent advances in deep reinforcement learning have made significant strides in performance on applications such as Go and Atari games. However, developing practical methods to balance exploration and exploitation in complex domains remains largely unsolved. Thompson Sampling and its extension to reinforcement learning…

Predictive sampling improves on Thompson sampling for non-stationary bandit environments.

Batch Thompson Sampling reduces exploration-exploitation trade-off in online decision making.

Thompson Sampling is at most twice as bad as any other policy in Bayesian bandit models.

Multi-armed bandit methods have been used for dynamic experiments particularly in online services. Among the methods, thompson sampling is widely used because it is simple but shows desirable performance. Many thompson sampling methods for binary rewards use logistic model that is written in a specific parameterization…

MetaTS learns to explore better by meta-learning prior from bandit instances.

LMC-TS uses MCMC for efficient posterior sampling in contextual bandits.

Improved sampling for high-dimensional posteriors with underdamped Langevin.