nucleation

LIT-1526: Online Learning and Blackwell Approachability with Partial Monitoring: Optimal Convergence Rates

1 min read

Properties5
StatusActive — read 2026-10-25 (NOTE-1159) in full, from the PMLR copy and its supplementary material; worth reading for the reduction of approachability under partial monitoring to full-information approachability in a lifted space of flags, for the optimal worst-case rates, O(T^-1/3) for general signals and O(T^-1/2) when the signal does not depend on the decision (THEORY-947), and for the exploration floor that decision-dependent signals require (THEORY-957). Read it knowing that approachability is assumed rather than decided, that the guarantees concern the average payoff and so let violations be compensated over time, that optimality is worst case over games, that the constants grow with a simplicial subdivision, and that the proof for outcome-dependent signals is omitted.
Version2
Tagslearning-theory, game-theory, anthology-candidate
Cited as “paper” byNOTE-1159 — Kwon and Perchet — Blackwell approachability with partial monitoring: optimal convergence rates
Cited as “source” byTHEORY-947 — For Blackwell approachability of an approachable polytope under partial monitoring with a known signal law, there are efficient algorithms whose average vector payoff reaches the target at expected distance O(T^-1/3) for general signals and O(T^-1/2) when the signal law does not depend on the decision, the worst-case optimal rates for those two classes, THEORY-957 — When the signal law depends on the decision, Kwon and Perchet's approachability algorithm learns what each decision would reveal only from the stages on which it is played: it keeps every decision's probability at least γ/|I| and estimates the flag by importance weighting, an estimate that is conditionally unbiased with second moment Σ_i 1/P[i_t = i] ≤ |I|²/γ, with the tuned floor γ shrinking as T^-1/3; when the signal law does not depend on the decision, the raw signal is already unbiased for every component and no floor is used

Graph View

Kwon, J. & Perchet, V. (2017). Online learning and Blackwell approachability with partial monitoring: Optimal convergence rates. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54: 604–613. https://proceedings.mlr.press/v54/kwon17a.html.

Read 2026-10-25 in full (NOTE-1159), from the PMLR copy and its supplementary material. The summary was checked against it.

Why this is here

Cited at U29, in reply to the owner’s question about improving the record’s mathematical toolkit, as the work that already joins partial monitoring (Bartók et al., LIT-1528) with approachability for vector-valued objectives, an organization that must meet several demands at once while seeing only partial feedback. U30 used it again for the rate at which such guarantees hold. The record uses approachability only as the engine of Hart and Mas-Colell’s proof (LIT-1521, NOTE-1142); Blackwell’s 1956 paper is not held.

Backlinks