sec-intrinsic-regret

9.14 Information-structured regret beyond the classical chain

The preceding construction still uses the conventional OCO clock. In fact, ordinary external regret contains a strong but usually implicit information declaration. At round \(t\), the learner acts from a nested information field

\[ \mathcal I_1\subseteq \mathcal I_2\subseteq \cdots \subseteq \mathcal I_T, \]

while the hindsight optimizer is chosen after the entire loss sequence has been revealed. In Witsenhausen’s terminology this is a classical information pattern [ Witsenhausen , 1971 , 1975 ] . The linear order, nested information, and additive accumulation of losses are three distinct assumptions; none belongs to the definition of online UDL.

Let \(A\) be a finite set of decision sites. Fix action objects \(U_\alpha \), local value objects \(V_\alpha \), and an aggregate value object \(V\). An information structure \(\mathcal I=(\mathcal I_\alpha )_{\alpha \in A}\) determines a class \(\Gamma (\mathcal I)\) of information-measurable strategy profiles. A profile \(\gamma \) induces its own closed-loop history \(h^\gamma \), and hence local values

\[ v_\alpha ^\gamma =\ell _\alpha (h^\gamma ,u_\alpha ^\gamma ). \]

Choose an aggregation morphism

\[ \mathsf{Agg}_A:\prod _{\alpha \in A}V_\alpha \longrightarrow V. \]

Addition in \(\mathbb R\) is one possible aggregation law, not the universal meaning of cumulative performance.

Suppose \(\mathcal J\) is a declared comparator information structure on the same decision sites and action types. When \(\mathcal I_\alpha \subseteq \mathcal J_\alpha \) for every \(\alpha \), the comparator has at least the information of the learner, and \(\Gamma (\mathcal I)\subseteq \Gamma (\mathcal J)\). More general comparisons may be expressed by a typed morphism between information structures, but no canonical numerical comparison follows merely from its existence.

Definition 9.20 Information-relative intrinsic regret

For an executed profile \(\pi \in \Gamma (\mathcal I)\), define

\begin{align*} L_{\mathcal M}(\pi ) & =\mathsf{Agg}_A \bigl((v_\alpha ^\pi )_{\alpha \in A}\bigr),\\ L_{\mathcal M}^{\star }(\mathcal J) & =\inf _{\gamma \in \Gamma (\mathcal J)} \mathsf{Agg}_A \bigl((v_\alpha ^\gamma )_{\alpha \in A}\bigr). \end{align*}

Given a comparison observer \(\Omega :V_{\mathrm{on}}\times V_{\mathrm{ref}}\to W\), the information-relative intrinsic regret is

\[ \mathsf{Reg}^{\Omega }_{\mathcal I\to \mathcal J}(\pi ) =\Omega \bigl(L_{\mathcal M}(\pi ), L_{\mathcal M}^{\star }(\mathcal J)\bigr). \]

Every comparator profile is evaluated on its own induced closed-loop history \(h^\gamma \).

The superscript \(\Omega \) is essential. If \(V\) is an ordered abelian group, \(\Omega (a,b)=a-b\) gives numerical regret. In other targets the observer may produce an order proposition, a residual, a vector of local defects, or a homotopy fiber. Varying \(\mathcal J\) produces an information-regret spectrum: performance relative to static, full-information, partially informed, or causally implementable references.

Theorem 9.21 Classical-chain recovery of OCO regret

Let \(A=[T]\), let \(X\) be a convex decision set, and let \(\ell _1,\ldots ,\ell _T:X\to \mathbb R\) be an exogenously fixed sequence of convex losses. Suppose

\(x_t\) is measurable with respect to the nested past-information field generated by \(\ell _1,\ldots ,\ell _{t-1}\);
\(\Gamma (\mathcal J)\) is restricted to constant sections \(\Delta x\) selected with the completed loss sequence;
\(\mathsf{Agg}_{[T]}\) is addition and \(\Omega (a,b)=a-b\).

Then 9.20 is exactly the standard static external regret

\[ \mathsf{Reg}^{\Omega }_{\mathcal I\to \mathcal J}(\pi ) =\sum _{t=1}^T\ell _t(x_t) -\min _{x\in X}\sum _{t=1}^T\ell _t(x). \]

Proof ▼

The first condition identifies the executed profile with an adapted OCO trajectory. By the second condition, optimization over \(\Gamma (\mathcal J)\) is optimization over one action held constant across all rounds; exogeneity makes its loss sequence independent of the learner’s trajectory. Substituting additive aggregation and the difference observer into 9.20 gives the displayed expression.

The theorem locates OCO precisely: it is the constant-comparator corner of intrinsic regret over a classical chain. Other Witsenhausen classes yield different online semantics.

Intrinsic class	Online semantics	Natural reference question
Static	observations do not depend on actions	best decentralized rule on the same exogenous data
Classical	totally ordered, nested histories	best static or dynamic hindsight section
Partially nested	causal sites inherit information along influence paths	best comparator respecting the same inheritance
Nonclassical	an action changes downstream information without transmitting its full basis	best closed-loop policy under a declared information pattern
Nonsequential	events form a partial order or asynchronous dependency shape	best strategy over causal cuts or admissible linearizations
Team	sites share one objective	common team value relative to a comparator information structure
Game	players have distinct objectives	player-indexed regrets or an equilibrium-defect object

Table 9.1 Witsenhausen’s classification generates a family of online-learning problems. The objective axis (team or game) is independent of the information axis (static, classical, partially nested, nonclassical, or nonsequential).

Proposition 9.22 Nonclassical replay obstruction

Suppose \(\beta \leadsto \alpha \): changing \(u_\beta \) may change the observation \(y_\alpha \). If \(\mathcal I_\beta \nsubseteq \mathcal I_\alpha \), then, in general, a counterfactual comparator profile \(\gamma \) cannot be evaluated by replacing the learner’s realized actions while holding its realized observation history fixed. Such a replay need not satisfy the intrinsic closed-loop equations. An intrinsic regret comparison must instead evaluate \(\gamma \) on \(h^\gamma \), unless an additional coupling or invariance assumption is declared.

Proof ▼

Choose profiles \(\pi \) and \(\gamma \) that differ at \(\beta \). By the influence assumption, they may induce \(y_\alpha (h^\pi )\neq y_\alpha (h^\gamma )\). The downstream action under \(\gamma \) must be \(u_\alpha ^\gamma =\gamma _\alpha (y_\alpha (h^\gamma ))\). Evaluating instead at the learner’s realized observation produces \(\gamma _\alpha (y_\alpha (h^\pi ))\), which is generally a different action and belongs to neither declared closed-loop trajectory. The resulting hybrid sequence therefore has no intrinsic-model semantics in general. Evaluating each profile on its own closed-loop solution restores a well-typed comparison.

This obstruction is invisible in standard OCO because losses are exogenous and the past-information fields form a classical chain. Under nonclassical information, the relevant benchmark is policy-level rather than merely action-level: changing a decision may change what can subsequently be known.

Categorically, time should therefore be replaced by an information category \(\mathbb A_{\mathcal I}\) of decision sites and admissible causal dependencies. A classical OCO horizon \([T]\) is the special case whose nerve has one maximal temporal simplex. A partially ordered or nonsequential system generally has several maximal simplices representing compatible executions. The online branch and comparator branch are extensions over this nerve, and intrinsic regret is an observer of their evaluated comparison. This yields the guiding principle

\[ \boxed {\begin{gathered} \text{online learning is indexed by information,}\\ \text{not necessarily by a global clock.} \end{gathered}} \]

The cumulative sum in Hazan’s formulation remains an important observer for the classical-chain case. UODL treats it as one specialization inside a larger theory of information-structured online decision learning.