nucleation

LIT-1528: Partial Monitoring—Classification, Regret Bounds, and Algorithms

2 min read

Properties7
StatusActive — read 2026-10-25 (NOTE-1164) in full, from the authors' preprint of March 2013 on Alexander Rakhlin's MIT page; worth reading for the complete classification of finite partial-monitoring games by minimax regret (0, Θ̃(√T), Θ(T^2/3), Θ(T); THEORY-964), for the linear-algebra conditions, global and local observability, that decide the class (THEORY-962), and for the algorithms CBP and NeighborhoodWatch. Read it knowing that the adversarial classification covers non-degenerate games only, that Lattimore and Szepesvári (2019, LIT-1524) completed it to degenerate games, corrected the kernel in its T^2/3 lower-bound proof, and, in their preprint, an exchanged expectation and maximum in NeighborhoodWatch's localisation (THEORY-963, THEORY-961), that the classification concerns the best policy in a fixed, known game, and that the copy read is the preprint, not the journal text.
Version3
Tagslearning-theory, game-theory, anthology-candidate
Extended byLIT-1524 — Cleaning up the neighborhood: A full classification for adversarial partial monitoring
Corrected byLIT-1524 — Cleaning up the neighborhood: A full classification for adversarial partial monitoring
Cited as “paper” byNOTE-1164 — Bartók, Foster, Pál, Rakhlin and Szepesvári — Partial monitoring: classification, regret bounds and algorithms
Cited as “source” byTHEORY-961 — In a finite partial-monitoring game, an action optimal wherever two neighbouring actions tie has a loss vector on the segment between theirs, so a degenerate or duplicate action never creates a neighbouring pair or decides the trivial class, yet its signals count toward the pair's local observability; and the T^2/3 lower bound for a pair that is not locally observable needs the separating direction in the kernel of the signal matrices of all such actions, not only of the two neighbours, THEORY-962 — In a finite partial-monitoring game, the signals of a set D of actions determine the expected loss difference of actions i and j under every outcome distribution iff ℓ_i − ℓ_j lies in the sum of the row spaces of their signal matrices; when it does not, two outcome distributions differing along a vector in the common kernel give every action in D the same signal law and reverse the preference between i and j, so no amount of play restricted to D can learn the comparison, THEORY-963 — The minimax regret of every finite partial-monitoring game against an oblivious adversary, degenerate and duplicate actions included, is 0 when no two actions are neighbours, Θ̃(√n) when every pair of neighbours is locally observable, Θ(n^2/3) when every pair is globally but some pair is not locally observable, and linear otherwise; its lower bounds are proved against stochastic outcomes, so the same four classes hold for them, THEORY-964 — The minimax regret of a finite partial-monitoring game takes one of four rates, decided by its loss and signal matrices: 0 when only one action is non-dominated, Θ̃(√T) when every pair of neighbouring actions is locally observable, Θ(T^2/3) when the game is globally but not locally observable, and Θ(T) when it is not globally observable; against stochastic opponents for every game, against oblivious adversaries for non-degenerate games

Graph View

Bartók, G., Foster, D. P., Pál, D., Rakhlin, A. & Szepesvári, C. (2014). Partial monitoring—classification, regret bounds, and algorithms. Mathematics of Operations Research 39(4): 967–997. doi:10.1287/moor.2014.0663.

Read 2026-10-25 in full (NOTE-1164), from the authors’ preprint of March 2013, not compared with the journal text. The summary was checked against it and narrowed to non-degenerate games for adversarial opponents.

Why this is here

The owner asked at U29 whether the exchange had turned up content that would improve the record’s mathematical toolkit, and the reply put partial monitoring first, as the formal case of an organization whose feedback is informative about some comparisons of its processes and not others. U30 used its global-observability condition for the channels an organization can access, and U31 built experiments on it. The record had no work on partial monitoring. It bears on QUESTION-271 (bandit against full-information evaluation of an organization’s processes) and on CASE-124 (what responses can distinguish). The exchange applied it to CLAIM-446’s avoid/approach example; read as a partial-monitoring game that example is locally observable, so the failure lies in the policy’s not sampling approach, not in the feedback, as the dated note of 2026-10-25 on that claim says. The audited-governance study CASE-158 is the record’s nearest construction.

Backlinks