Source
Bartók, Foster, Pál, Rakhlin and Szepesvári (2014), LIT-1528, Theorems 1 and 2, assembled in their §7 from Piccolboni and Schindelhauer (2001) for the linear lower bound, Antos et al. (2012) for the √T lower bound, their own Theorem 4 for the T^{2/3} lower bound, FeedExp (Piccolboni and Schindelhauer; Cesa-Bianchi, Lugosi and Stoltz 2006) for the T^{2/3} upper bound, CBP (Corollary 3) and NeighborhoodWatch (Corollary 5) for the √T upper bounds. Read in NOTE-1164.
What was actually shown
For a game G = (L, H) with K non-dominated actions:
| class | condition | stochastic (Thm 1) | adversarial, non-degenerate (Thm 2) |
|---|---|---|---|
| trivial | K = 1 | 0 | 0 |
| easy | K > 1, locally observable | Θ̃(√T) | Θ(√T) |
| hard | globally, not locally observable | Θ(T^{2/3}) | Θ(T^{2/3}) |
| hopeless | not globally observable | Θ(T) | Θ(T) |
The observability conditions are THEORY-962’s span condition, with D equal to all actions (global) or to the neighbourhood action set N⁺_{i,j} (local). The lower bound of Theorem 4 places two outcome distributions p₀ ± εv about the boundary between two neighbours that are not locally observable, with v in the kernel of both signal matrices, and sets ε ∝ T^{−1/3}. Telling them apart needs plays of actions outside the neighbourhood, each costing at least a constant β. Balancing the ε-regret of guessing against the β-cost of looking gives T
In the stochastic easy class the individual regret for a fixed p is logarithmic in T (Corollary 1). A hard game is easy against opponents kept away from its unobservable boundaries, and CBP adapts to that without being told (Theorem 5).
What could have failed: there could have been games with intermediate exponents between 1/2 and 2/3. The paper closes that gap, which was the open part.
What this does not say
- Not about a constrained learner. The class is the minimax regret of the best algorithm, which may play any action. A policy that never plays some action has whatever regret that restriction costs, linear in T if the action is sometimes optimal, whatever the game’s class.
- Not about degenerate games against adversaries. The paper leaves them open. Lattimore and Szepesvári (LIT-1524, read in NOTE-1162) “complete the classification of finite adversarial partial monitoring to include all games” and “correct errors in previous analyses”, by their abstract.
- Not about constants or finite T. The constants depend on the game and can be large.
- Not about learned or changing feedback. L and H are fixed and known. Authority that edits the losses or the signal channels during learning is outside the theorem, as A29 already cautioned (CLAIM-446’s note).
- Not about adaptive adversaries. The adversarial results are for oblivious ones.
Connections
- CLAIM-446. Its approach–avoid example is in the easy class (THEORY-962). Approach with suppressed feedback is hopeless, and information available only from a dominated check is hard.
- Kwon and Perchet (LIT-1526) give the vector-payoff counterpart. For approachability under partial monitoring the worst-case rates are T^{−1/2} with outcome-dependent signals and T^{−1/3} in general, the average-payoff forms of √T and T
- QUESTION-271. The classification says when feedback that depends on the action played costs more than full information, and by how much.
Note of 2026-10-25: the reading of Lattimore and Szepesvári
Lattimore and Szepesvári, “Cleaning up the neighborhood” (LIT-1524), is now read (NOTE-1162). This entry’s promote_when is met by its second disjunct: the paper restates the classification and proves the two pieces that were open or flawed, the √n upper bound for all locally observable games (NeighborhoodWatch2) and the corrected T^{2/3} lower bound, and cites the rest as Bartók et al. did. Its first disjunct is met in substance too, by the re-derivation recorded in THEORY-963.
Two clauses here are mis-stated, so the reading proposes that this entry be Superseded by THEORY-963 rather than promoted:
- The trivial class. It is “no pair of neighbouring actions”, not “only one action is non-dominated”. The latter misplaces games with degenerate or duplicate actions: L = ((0, 0), (0, 1)), or two duplicate actions, have two non-dominated actions, no neighbours and regret 0, yet the wording puts them in the easy class.
- The lower bound’s kernel. The vector v must lie in the kernel of every signal matrix in N_ab, not only of the two neighbours’ signal matrices, as “with v in the kernel of both signal matrices” above has it (THEORY-961). The theorem stands; the slip is harmless for non-degenerate games, where N_ab = {a, b}.
Its adversarial scope, non-degenerate games only, is also narrower than is now known. Whether to supersede or to correct in place and promote is the owner’s decision under ADR-047. The status is unchanged.
Superseded, 2026-10-25
At the owner’s decision under ADR-047, this entry is Superseded by THEORY-963 rather than promoted, for the two mis-stated clauses in the note above. Cite THEORY-963 for the classification and THEORY-961 for the role of degenerate actions and the corrected lower bound.