ora-0176

15.8 Approachability as persistent consistency

Blackwell-style approachability asks whether the online value can be kept asymptotically within \(S\). The UODL version asks whether the evolving comparison object admits coherent repairs whose images remain compatible with \(S\) under restriction and transport. This makes vector-valued approachability a test of observers, repair, and persistence simultaneously. A complete theory should recover the classical separating-hyperplane criterion in Euclidean realization and identify its categorical replacement.

The classical realization supplies an exact checkpoint. Let \(g:A\times B\to \mathbb R^d\) be bounded, let \(S\subseteq \mathbb R^d\) be closed and convex, and let \(\bar g_t\) be the average vector payoff. For \(z\notin S\), write \(p=\Pi _S(z)\). The separating normal \(z-p\) defines a scalar observer of the currently violated face.

Theorem 15.8 Euclidean approachability checkpoint

Suppose that for every \(z\notin S\) there is a learner action \(a_z\) such that

\[ \sup _{b\in B} \langle g(a_z,b)-p,z-p\rangle \leq 0, \qquad p=\Pi _S(z). \]

Then the strategy choosing \(a_{\bar g_t}\) makes \(\operatorname {dist}(\bar g_t,S)\to 0\). With \(\lVert g(a,b)\rVert \leq M\), the squared-distance recursion is

\[ \operatorname {dist}(\bar g_{t+1},S)^2 \leq \left(\frac{t}{t+1}\right)^2 \operatorname {dist}(\bar g_t,S)^2 +\frac{4M^2}{(t+1)^2}. \]

Proof ▼

Compare \(\bar g_{t+1}\) with the old projection \(p_t\). Expanding the squared norm produces a cross term proportional to \(\langle g(a_{\bar g_t},b_{t+1})-p_t,\bar g_t-p_t\rangle \), which is nonpositive by the separating condition. Boundedness controls the remaining quadratic term. Iterating the displayed recursion gives distance converging to zero.

Categorically, projection selects a violated-face observer, the learner action is a repair request, and the halfspace inequality certifies that the repair does not move outward through that face. The desired generalization replaces Euclidean projection by a universal nearest-admissible comparison and separating linear functionals by a jointly conservative family of observers. The theorem above is a required recovery result, not the generalization itself.