# Information Directed Sampling for Linear Partial Monitoring

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

## Built on by (most cited first, 30 of 40)

- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Information Directed Reward Learning for Reinforcement Learning](https://mlsanity.com/paper/2102.12466/) (2021)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [Bandit Phase Retrieval](https://mlsanity.com/paper/2106.01660/) (2021)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Bias-Robust Bayesian Optimization via Dueling Bandits](https://mlsanity.com/paper/2105.11802/) (2021)
- [Near-Optimal Multi-Agent Learning for Safe Coverage Control](https://mlsanity.com/paper/2210.06380/) (2022)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Bandits with Preference Feedback: A Stackelberg Game Perspective](https://mlsanity.com/paper/2406.16745/) (2024)
- [Beyond Optimism: Exploration With Partially Observable Rewards](https://mlsanity.com/paper/2406.13909/) (2024)
- [A Bit Better? Quantifying Information for Bandit Learning](https://mlsanity.com/paper/2102.09488/) (2021)
- [Gaussian Imagination in Bandit Learning](https://mlsanity.com/paper/2201.01902/) (2022)
- [Thompson Sampling in Partially Observable Contextual Bandits](https://mlsanity.com/paper/2402.10289/) (2024)
- [Online Decision Mediation](https://mlsanity.com/paper/2310.18601/) (2023)
- [Robustifying and Boosting Training-Free Neural Architecture Search](https://mlsanity.com/paper/2403.07591/) (2024)
- [Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification](https://mlsanity.com/paper/2109.14412/) (2021)
- [The price of unfairness in linear bandits with biased feedback](https://mlsanity.com/paper/2203.09784/) (2022)
- [Randomized Confidence Bounds for Stochastic Partial Monitoring](https://mlsanity.com/paper/2402.05002/) (2024)
- [Provably Efficient Interactive-Grounded Learning with Personalized Reward](https://mlsanity.com/paper/2405.20677/) (2024)
- [Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints](https://mlsanity.com/paper/2401.11563/) (2024)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)
- [Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits](https://mlsanity.com/paper/2405.15200/) (2024)
- [Non-Stationary Dynamic Pricing Via Actor-Critic Information-Directed Pricing](https://mlsanity.com/paper/2208.09372/) (2022)
- [Neural Active Learning Meets the Partial Monitoring Framework](https://mlsanity.com/paper/2405.08921/) (2024)
- [Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds](https://mlsanity.com/paper/2411.12154/) (2024)

## Abstract (arXiv)

Partial monitoring is a rich framework for sequential decision making under uncertainty that generalizes many well known bandit models, including linear, combinatorial and dueling bandits. We introduce information directed sampling (IDS) for stochastic partial monitoring with a linear reward and observation structure. IDS achieves adaptive worst-case regret rates that depend on precise observability conditions of the game. Moreover, we prove lower bounds that classify the minimax regret of all finite games into four possible regimes. IDS achieves the optimal rate in all cases up to logarithmic factors, without tuning any hyper-parameters. We further extend our results to the contextual and the kernelized setting, which significantly increases the range of possible applications.