nucleation

LIT-1524: Cleaning up the neighborhood: A full classification for adversarial partial monitoring

1 min read

Properties7
StatusActive — read 2026-10-25 (NOTE-1162) in full, from the arXiv preprint v1 of 23 May 2018 (arxiv.org/pdf/1805.09247v1, 24 pp.); the ALT 2019 version (PMLR 98:529–556) was fetched and its theorem statements, footnote and contribution list compared, not read in full. Worth reading for the completed classification of finite adversarial partial-monitoring games, degenerate and duplicate actions included (THEORY-963); for how actions that are optimal only on a boundary enter it, through the neighbourhood set and not as neighbours, and for its correction of the lower-bound proof of Bartók et al. (2014) (THEORY-961); for NeighborhoodWatch2, a simpler algorithm with a high-probability √n bound; and for RelExp3 on point-locally observable games (THEORY-950). Read it knowing that the arXiv text says Foster and Rakhlin and Bartók et al. "inadvertently exchanged an expectation and maximum" in their localisation argument and the published text no longer says so, though both abstracts say "correct errors in previous analyses"; that it proves only the two pieces of the classification that were missing or flawed and cites the rest; that its constants are game-dependent and can be large; and that a few small typos survive in the arXiv text.
Version2
Tagslearning-theory, game-theory, anthology-candidate
ExtendsLIT-1528 — Partial Monitoring—Classification, Regret Bounds, and Algorithms
CorrectsLIT-1528 — Partial Monitoring—Classification, Regret Bounds, and Algorithms
Cited as “paper” byNOTE-1162 — Lattimore and Szepesvári — Cleaning up the neighborhood: a full classification for adversarial partial monitoring
Cited as “source” byTHEORY-950 — For a finite partial-monitoring game in which every two actions whose cells meet can estimate their loss difference from their own two signals, RelExp3's expected regret satisfies lim sup E[R_n]/√n ≤ 8√(2K_loc(1+F)(2+F) log K), with K_loc the most actions whose cells share a point and F the number of feedback symbols, and no other game-dependent constant; a two-action game shows that a factor linear in F cannot be avoided in general, THEORY-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-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

Graph View

Lattimore, T. & Szepesvári, C. (2019). Cleaning up the neighborhood: A full classification for adversarial partial monitoring. Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98: 529–556. Preprint: arXiv:1805.09247 (23 May 2018).

Read 2026-10-25 in full (NOTE-1162), from the arXiv preprint; the published text was compared at the level of its statements. The summary was checked against it.

Why this is here

The owner asked on 2026-10-25 for it to be registered and read. The reading of Bartók et al. (LIT-1528, NOTE-1164) left the adversarial classification for non-degenerate games only, and named this paper as the one that completes it and corrects the earlier analyses; THEORY-964’s promotion condition names it. It settles what that reading could not: which games the classification covers, what was wrong in the earlier proofs, and how actions that are optimal only on a boundary count. Its spam game is the check variant of CLAIM-446’s approach–avoid example, with the threshold case that the earlier classification excluded now placed in the easy class.

Backlinks