# Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring

arXiv: https://arxiv.org/abs/2006.09668 · HTML: https://mlsanity.com/paper/2006.09668/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

## Built on by (most cited first, 9 of 9)

- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [A Unified Framework for Discovering Discrete Symmetries](https://mlsanity.com/paper/2309.02898/) (2023)
- [Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification](https://mlsanity.com/paper/2109.14412/) (2021)
- [Randomized Confidence Bounds for Stochastic Partial Monitoring](https://mlsanity.com/paper/2402.05002/) (2024)
- [Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring](https://mlsanity.com/paper/2402.08321/) (2024)
- [Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring](https://mlsanity.com/paper/2510.19158/) (2025)
- [On the Minimax Regret in Online Ranking with Top-k Feedback](https://mlsanity.com/paper/2309.02425/) (2023)

## Abstract (arXiv)

We investigate finite stochastic partial monitoring, which is a general model for sequential learning with limited feedback. While Thompson sampling is one of the most promising algorithms on a variety of online decision-making problems, its properties for stochastic partial monitoring have not been theoretically investigated, and the existing algorithm relies on a heuristic approximation of the posterior distribution. To mitigate these problems, we present a novel Thompson-sampling-based algorithm, which enables us to exactly sample the target parameter from the posterior distribution. Besides, we prove that the new algorithm achieves the logarithmic problem-dependent expected pseudo-regret O(log T) for a linearized variant of the problem with local observability. This result is the first regret bound of Thompson sampling for partial monitoring, which also becomes the first logarithmic regret bound of Thompson sampling for linear bandits.