Source
Kwon and Perchet (2017), AISTATS, PMLR 54:604–613, LIT-1526, Theorems 4.1 and 4.3, read in NOTE-1159 with the supplementary material.
What was actually shown
Decisions I, Nature’s actions J, a vector payoff g: I × J → ℝ^d and a signal law s: I × J → Δ(S), all finite and known. The target is C = ℝ^d_−, to which polytopes reduce, and it is assumed approachable. Then:
- General signals (Theorem 4.1). An algorithm that lifts the problem to full-information approachability in a space of flag estimates, and plays each decision with probability at least γ/|I| with γ ∝ T^{−1/3}, guarantees E[d₂(ḡ_T, C)] ≤ 12‖g‖^{1/3}(L_r|I||K||A|)^{2/3}T^{−1/3} + O(T^{−1/2}), against any choices of Nature.
- Outcome-dependent signals (Theorem 4.3). If s(i, j) = s(i′, j), the same construction with no exploration gives O(T
- Optimality. Both rates match lower bounds that already hold for regret minimization: Cesa-Bianchi, Lugosi and Stoltz’s T^{−1/3} for general signals, and the full-information T
What could have failed: the earlier best rates, T^{−1/5} and T^{−1/(I+3)}, might have been the truth for approachability, with its set-valued compatible payoffs. The lifting shows that partial monitoring costs approachability no more than it costs regret, in the worst case.
What this does not say
- Not a rate for every game. “Cannot be improved” is worst case over signal structures. A particular game can do better, as Bartók et al.’s locally observable games do for regret (THEORY-964).
- Not a per-stage or windowed guarantee. The average is compensatory: a coordinate alternating +1 and −1 has average 0 ∈ C and is approached while violated on half the stages. This is CLAIM-357’s caution.
- Not when the target is unapproachable. Approachability is assumed. Perchet’s characterization is cited, not proved or made checkable.
- Not with unknown signal laws, or laws that change.
- Not that the constants are small. They grow with the size of the simplicial subdivision.
Connections
- CLAIM-357. The record’s one-shot target {z : z_i ≤ 0} is this theorem’s C. Its worst residual is a max. The approachability distance is the ℓ₂ norm of the positive part of the average.
- THEORY-964. The same exponents in average form: √T regret is T^{−1/2}, T^{2/3} is T
- THEORY-957. The floor in the general algorithm, and why the outcome-dependent case needs none.