mlsanityData to 14 Oct 2026

Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret

arXiv 2202.10997 ↗First posted 22 Feb 2022math.OC cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games provided that (a) the standard definition of regret is used but the latent space where the adversary plays is potentially infinite; or (b) the regret introduced by Rustichini (1999) is used and the latent space is finite. Our results are complemented by a number of examples. For any p ∈ [1/2,1] there exists an infinite partial monitoring game for which the minimax regret over n rounds is np up to subpolynomial factors and there exist finite games for which the minimax Rustichini regret is n4/7 up to subpolynomial factors.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 10 of its 24 references that are in the map. First posted on arXiv 22 Feb 2022.

Builds on

10 of 24 references.

References · 10

  1. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  2. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  3. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 42
  4. 2020Mirror Descent and the Information Ratiocited by 40
  5. 2020Asymptotically Optimal Information-Directed Samplingcited by 33
  6. 2021Bilateral Trade: A Regret Minimization Perspectivecited by 29
  7. 2019Connections Between Mirror Descent, Thompson Sampling and the Information Ratiocited by 23
  8. 2019Exploration by Optimisation in Partial Monitoringcited by 21
  9. 2018Cleaning up the neighborhood: A full classification for adversarial partial monitoringcited by 16
  10. 2021A Bit Better? Quantifying Information for Bandit Learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 4; 2025: 1; 2026: 1.

14 papers.

Sort:

  1. 2022On the Complexity of Adversarial Decision Makingcited by 33
  2. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
  3. 2023Repeated Bilateral Trade Against a Smoothed Adversarycited by 15
  4. 2023The Role of Transparency in Repeated First-Price Auctions with Unknown Valuationscited by 15
  5. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  6. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  7. 2024Thompson Sampling in Partially Observable Contextual Banditscited by 5
  8. 2024Stochastic contextual bandits with graph feedback: from independence number to MAS numbercited by 5
  9. 2024Randomized Confidence Bounds for Stochastic Partial Monitoringcited by 3
  10. 2022Worst-case Performance of Greedy Policies in Bandits with Imperfect Context Observationscited by 2
  11. 2024Learning from Snapshots of Discrete and Continuous Data Streamscited by 2
  12. 2025Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoringcited by 1
2 more
  1. 2023On the Minimax Regret in Online Ranking with Top-k Feedbackcited by 0
  2. 2026Efficient contextual partial monitoring with general function approximationcited by 0