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…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Thompson-Sampling”
Optimizes Thompson sampling policies using policy gradient methods.
problem Improving Thompson sampling in bandit problems.
method Applies policy gradient algorithms to optimize Thompson sampling policies.
result Direct policy search on Thompson sampling improves performance.
MOTS improves Thompson sampling to match minimax bounds for bandit problems.
problem Achieving optimal regret bounds for Thompson sampling in multi-armed bandit problems.
method Proposes MOTS, a variant of Thompson sampling that clips arm sampling.
result Proves MOTS achieves minimax optimal regret bounds .
New method targets vaccines for new variants using Thompson sampling.
problem Deciding how to prioritize vaccines for new variants with delayed feedback.
method Partial likelihood Thompson sampling, updating beliefs with partial likelihood.
result Method effectively prioritizes vaccines based on real-world data.
Improved Thompson Sampling reduces regret in contextual bandits and reinforcement learning.
problem Thompson Sampling's exploration is insufficient in some contexts.
method Developed Feel-Good Thompson Sampling to address exploration issues.
result Feel-Good Thompson Sampling reduces regret compared to standard Thompson Sampling.
New Thompson sampling algorithm for stochastic partial monitoring achieves logarithmic regret.
problem Limited feedback in sequential learning problems.
method Developed a novel Thompson-sampling-based algorithm to sample from the posterior distribution exactly.
result Achieved logarithmic regret bound of O(log T) for a linearized variant of the problem.
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…
Thompson sampling used for linear bandits with normal-gamma priors.
problem Optimizing decisions in uncertain environments with linear dependencies and unknown parameters.
method Bayesian Thompson sampling with multivariate normal-gamma priors.
result Derivation of a Bayesian regret bound for the approach.
Improved Thompson Sampling algorithms for bandits with tighter regret bounds.
problem Efficient and adaptive algorithms for stochastic bandits with bounded rewards.
method Proposed two parameterized Thompson Sampling-based algorithms: TS-MA-α and TS-TD-α.
result Achieved O(Kln^(α+1)(T)/Δ) regret bound, improving scalability and resource allocation.
A new thompson sampling method controls for time-varying effects.
problem Dynamic experiments in online services with time-varying effects.
method Odds-ratio Thompson Sampling
result The proposed method works robust to time-varying effects.
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…
Paper improves Thompson Sampling for linear contextual bandits.
problem Empirical Thompson Sampling does not achieve optimal regret bounds.
method Develops a novel estimator with adaptive data augmentation and coupling.
result Achieves nearly minimax optimal performance.
Improved Thompson sampling for bandits with Langevin algorithms.
problem Thompson sampling's computational inefficiency in generating posterior samples.
method Developed Langevin algorithms for approximate sampling with posterior concentration guarantees.
result Logarithmic regret with constant computational complexity.
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…
Improved statistical inference for adaptive Thompson Sampling.
problem Statistical inference challenges in Thompson Sampling.
method Inflating posterior variance in Thompson Sampling.
result Asymptotically normal estimates of arm means with logarithmic regret increase.
This paper applies Thompson Sampling to asymmetric -stable bandits for financial and wireless data.
problem Optimizing exploration-exploitation in multi-armed bandits with asymmetric -stable distributions.
method Thompson Sampling applied to unknown asymmetric -stable reward distributions.
result Demonstrates effectiveness of Thompson Sampling for asymmetric -stable bandits.
Improved Thompson Sampling for high-dimensional sparse bandits.
problem Stochastic linear contextual bandits with high-dimensional features.
method Thompson Sampling with spike-and-slab priors and variational inference.
result Nearly optimal upper bound on expected cumulative regret.
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 …
TS-Insight visualizes Thompson Sampling for better debugging and trust.
problem Thompson Sampling's black box nature hinders debugging and trust.
method TS-Insight is a visual analytics tool that traces evolving posteriors and evidence counts.
result Visualizations help in verifying, diagnosing, and explaining Thompson Sampling dynamics.
Model shows screening for infectious disease is hard but Thompson sampling works well.
problem Optimal screening policy for infectious diseases is hard to find.
method Stochastic-control model with Thompson sampling for optimal performance.
result Thompson sampling provides optimal performance guarantees in screening for infectious diseases.
ERTS uses Thompson sampling for Gaussian entropic risk bandits, achieving regret bounds.
problem Risk in decision making complicates reward maximization in MAB problems.
method ERTS (Entropic Risk Thompson Sampling) using Thompson sampling with an entropic risk measure.
result Regret bounds for ERTS under entropic risk measure provided.
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.
problem Maximizing a black-box function with multi-agent Bayesian optimization under communication constraints.
method Distributed Thompson sampling using Gaussian processes, with theoretical bounds on regret convergence.
result Theoretical bounds on Bayesian average and simple regret depend on communication graph structure and are applicable in constrained networks.
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.
problem Improving the performance of Thompson Sampling in contextual bandits with sub-Gaussian rewards.
method Proved comprehensive bounds on Thompson Sampling expected cumulative regret based on mutual information and lifted information ratio for sub-Gaussian rewards.
result Explicit regret bounds for various contextual bandit scenarios.
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.
problem Solving contextual multi-armed bandit problems.
method Adapts deep neural networks for exploration and exploitation in a novel posterior distribution.
result Guaranteed cumulative regret of for bounded reward functions.
New Thompson Sampling for partially observed context bandits reduces regret logarithmically with time.
problem Improving Thompson Sampling for partially observed context bandits.
method Proposed a Thompson Sampling algorithm for partially observable contextual multi-armed bandits with theoretical performance guarantees.
result Regret scales logarithmically with time and the number of arms, and linearly with the dimension.
Extends Thompson sampling for RL with fewer episodes.
problem Limited episodes in RL settings.
method Batch Bayesian optimization over episodes to learn action bias terms.
result Significantly outperforms standard Thompson sampling.
TS-UCB improves Thompson Sampling with minimal extra computation.
problem Online decision problems with bandit feedback.
method TS-UCB uses posterior samples and upper confidence bounds to select arms.
result TS-UCB achieves lower regret on various datasets.
Batch Thompson Sampling reduces exploration-exploitation trade-off in online decision making.
problem Balancing exploration and exploitation in online decision making.
method Introducing a batch Thompson Sampling framework for stochastic multi-arm bandit and linear contextual bandit problems.
result Achieves asymptotic regret bound with batch queries, significantly reducing interactions.
Thompson Sampling is at most twice as bad as any other policy in Bayesian bandit models.
problem Optimizing selection of the best arm in Bayesian bandit models with independent latent processes.
method Thompson Sampling approach applied to models with independent latent arm processes.
result Thompson Sampling makes at most twice the expected number of mistakes compared to any other policy.
MetaTS learns to explore better by meta-learning prior from bandit instances.
problem Efficient exploration in bandit problems.
method MetaThompson Sampling (MetaTS) that meta-learns the prior from bandit instances.
result MetaTS quickly adapts to unknown prior and achieves better exploration.
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradoxstat.ML
Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.
problem Finding optimal solutions in combinatorial semi-bandits with suboptimal sampling.
method Proposes Thompson Sampling with polynomial regret for linear combinatorial semi-bandits.
result Demonstrates 'mismatched sampling paradox' where knowing distributions can lead to worse performance.
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…
Thompson Sampling is a well established approach to bandit and reinforcement learning problems. However its use in continuum armed bandit problems has received relatively little attention. We provide the first bounds on the regret of Thompson Sampling for continuum armed bandits under weak conditions on the function cl…
Thompson Sampling fails to perform well in high dimensions.
problem Thompson Sampling's suboptimality in high-dimensional combinatorial semi-bandits.
method Analysis of TS for combinatorial semi-bandits, including non-linear and linear reward functions, with Bernoulli rewards and uniform priors.
result TS's regret scales exponentially in the ambient dimension and minimax regret scales almost linearly in high dimensions.
We study multi-armed bandit problems with graph feedback, in which the decision maker is allowed to observe the neighboring actions of the chosen action, in a setting where the graph may vary over time and is never fully revealed to the decision maker. We show that when the feedback graphs are undirected, the original …
VITS improves Thompson Sampling for contextual bandits with efficient approximate inference.
problem Intractable posterior sampling in traditional Thompson Sampling for contextual bandits.
method VITS uses Gaussian Variational Inference for efficient posterior approximations.
result VITS achieves sub-linear regret bound similar to traditional TS.
Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Banditsstat.ML
New Thompson sampling algorithm reduces regret for exponential family bandits.
problem Minimizing regret in multi-armed bandit problems with exponential family rewards.
method Proposes ExpTS and ExpTS algorithms using novel sampling distributions.
result Minimizes both finite-time and asymptotic regret for exponential family rewards.
Thompson Sampling tackles USS, a sequential selection problem without feedback.
problem Unsupervised Sequential Selection (USS) problem with fixed costs and ordered arms.
method Thompson Sampling algorithm for USS problem.
result Thompson Sampling achieves near optimal regret and better performance than existing algorithms.
The paper extends Thompson Sampling to infinite action spaces using information theory.
problem Addressing the limitation of finite action spaces in Thompson Sampling.
method Information-theoretic analysis, extending rate-distortion theory to infinite action spaces.
result Derives a near-optimal regret bound for bandits with infinite and continuous action spaces.
In this note, we present a version of the Thompson sampling algorithm for the problem of online linear generalization with full information (i.e., the experts setting), studied by Kalai and Vempala, 2005. The algorithm uses a Gaussian prior and time-varying Gaussian likelihoods, and we show that it essentially reduces …
Thompson Sampling with bilateral uncertainty improves performance in Bayesian Optimization.
problem Twin difficulties of modeling and searching complex functions in high dimensions.
method Exploiting conditional independence, Thompson Sampling respecting bilateral uncertainty (BU).
result Thompson Sampling with BU is more effective than the additive approximation in small budgets.
New algorithm reduces regret in multi-armed bandit problems with Gaussian rewards.
problem Optimizing decisions in multi-armed bandit problems with Gaussian rewards.
method Proposed TSCG and UTSCG algorithms using Thompson Sampling with Gaussian prior.
result Achieved lower regret bounds for optimal arm selection.
Ensemble Samplingstat.ML
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…
Optimism stabilizes Thompson Sampling for adaptive inference in multi-armed bandits.
problem Subtle inferential properties of Thompson Sampling under adaptive data collection.
method Introduced optimism as a key mechanism to restore stability and validity of inference.
result Suitably implemented optimism stabilizes Thompson Sampling and enables asymptotically valid Wald inference.
Ensemble sampling approximates Thompson sampling for complex models.
problem Computational intractability of exact posterior distributions.
method Thompson sampling approximation with information-theoretic concepts.
result Established a first rigorous regret bound for ensemble sampling.