mlsanityData to 7 Oct 2026

An Information-Theoretic Approach to Minimax Regret in Partial Monitoring

arXiv 1902.00470 ↗First posted 1 Feb 2019cs.LG math.OC stat.MLcited by 41

Not on the map. Why?

Abstract (arXiv)

We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine them with the minimax theorem to derive minimax regret bounds for various partial monitoring settings. The highlight is a clean analysis of `non-degenerate easy' and `hard' finite partial monitoring, with new regret bounds that are independent of arbitrarily large game-dependent constants. The power of the generalised machinery is further demonstrated by proving that the minimax regret for k-armed adversarial bandits is at most sqrt{2kn}, improving on existing results by a factor of 2. Finally, we provide a simple analysis of the cops and robbers game, also improving best known constants.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 9; 2023: 12; 2024: 9; 2025: 2.

41 papers.

Sort:

By area:

  1. 2021Reinforcement Learning, Bit by Bitcited by 59
  2. 2022On the Complexity of Adversarial Decision Makingcited by 32
  3. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  4. 2021Deciding What to Learn: A Rate-Distortion Approachcited by 23
  5. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  6. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  7. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  8. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  9. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  10. 2021The Value of Information When Deciding What to Learncited by 15
  11. 2023Repeated Bilateral Trade Against a Smoothed Adversarycited by 15
  12. 2021Weak Signal Asymptotics for Sequentially Randomized Experimentscited by 13
29 more
  1. 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 13
  2. 2023Leveraging Demonstrations to Improve Online Learning: Quality Matterscited by 13
  3. 2022Near-Optimal Multi-Agent Learning for Safe Coverage Controlcited by 11
  4. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
  5. 2024Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learningcited by 10
  6. 2025Formalizing Learning from Language Feedback with Provable Guaranteescited by 10
  7. 2021Interaction-Grounded Learningcited by 9
  8. 2023A Definition of Non-Stationary Banditscited by 9
  9. 2024Monitored Markov Decision Processescited by 9
  10. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  11. 2024Beyond Optimism: Exploration With Partially Observable Rewardscited by 6
  12. 2021A Bit Better? Quantifying Information for Bandit Learningcited by 5
  13. 2022Gaussian Imagination in Bandit Learningcited by 5
  14. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  15. 2023Minimax-Bayes Reinforcement Learningcited by 5
  16. 2023Online Learning with Feedback Graphs: The True Shape of Regretcited by 5
  17. 2023STEERING: Stein Information Directed Exploration for Model-Based Reinforcement Learningcited by 4
  18. 2023Bayesian Reinforcement Learning with Limited Cognitive Loadcited by 4
  19. 2021Minimax Regret for Bandit Convex Optimisation of Ridge Functionscited by 3
  20. 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
  21. 2024On Bits and Bandits: Quantifying the Regret-Information Trade-offcited by 3
  22. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  23. 2021Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classificationcited by 2
  24. 2023Effective Dimension in Bandit Problems under Censorshipcited by 2
  25. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  26. 2024Learning from Snapshots of Discrete and Continuous Data Streamscited by 2
  27. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Dualitycited by 1
  28. 2025Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoringcited by 1
  29. 2023On the Minimax Regret in Online Ranking with Top-k Feedbackcited by 0