sec-observer-regret

9.13 Observers and the origin of regret

An online decision and a hindsight comparator inhabit different information semantics. The online branch selects \(x_t\) from the principal past \(\downarrow t\). The comparator branch sees the complete horizon but is restricted to a declared class, such as one action held fixed at every time. Neither branch alone is a regret. A comparison exists only after an observer places their evaluated outcomes in a common value type.

Let \(\mathbb T_T=\{ 1{\lt}\cdots {\lt}T\} \), let \(X\) be an action object, and let \(\pi :\mathbb T_T\to 1\) be the terminal functor. Precomposition gives the constant-diagram functor

\[ \Delta =\pi ^*:\mathcal D\longrightarrow [\mathbb T_T,\mathcal D], \]

with right adjoint

\[ \Delta \dashv \operatorname {Ran}_\pi =\lim _{\mathbb T_T}. \]

Proposition 9.18 Static comparators as right-Kan-consistent sections

Assume \(\mathbb T_T\) is nonempty and connected and the required limits exist. A trajectory object \(c\in [\mathbb T_T,\mathcal D]\) is isomorphic to a constant section precisely when the counit

\[ \varepsilon _c: \Delta \operatorname {Ran}_\pi c\longrightarrow c \]

is an isomorphism. Thus the static comparator declaration is the full subcategory on the right-Kan-consistent trajectories.

Proof ▼

If \(c\cong \Delta u\), connectedness gives \(\operatorname {Ran}_\pi c\cong u\), and the counit is the constant-diagram isomorphism. Conversely, an invertible counit exhibits \(c\cong \Delta \operatorname {Ran}_\pi c\), so \(c\) is isomorphic to a constant section.

For a fixed action carrier \(X\), a comparator trajectory is a natural section \(\Delta 1\to \Delta X\). Connectedness forces all of its temporal components to be the same generalized element \(u:1\to X\). The right Kan condition therefore declares staticness; minimizing cumulative loss over those sections is a subsequent decision readout.

Now let \((V,\oplus ,0,\leq )\) be an ordered commutative value monoid, let \(e_t\) evaluate the revealed information and an action in \(V\), and let \(\sigma _T:V^T\to V\) be the declared accumulation map. The two branches produce

\begin{align} L_T^{\mathrm{on}} & = \sigma _T\bigl(e_1(F_1,x_1),\ldots ,e_T(F_T,x_T)\bigr), \\ L_T^{\mathrm{stat}} & = \inf _{u:\, \Delta u\ \mathrm{static}} \sigma _T\bigl(e_1(F_T,u),\ldots ,e_T(F_T,u)\bigr). \end{align}

The first line is a UODL quantity because each \(x_t\) is adapted to \(F_t\). The second is a UDL quantity computed from the full diagram \(F_T\), with right-Kan consistency restricting the comparator trajectory to a constant section. It is a hindsight semantic object, not an executable online policy.

Definition 9.19 Online comparison observer

An online comparison observer is a declared morphism

\[ \Omega :V_{\mathrm{on}}\times V_{\mathrm{ref}} \longrightarrow W \]

whose two inputs are the cumulative values of an adapted UODL branch and a full-information UDL reference branch. Its output is the observable comparison object.

When \(V\) is an ordered abelian group and \(W=V\), the numerical regret observer is

\[ \Omega (a,b)=a-b, \qquad R_T=\Omega (L_T^{\mathrm{on}},L_T^{\mathrm{stat}}). \]

If \(V\) is only ordered, the observer may return the proposition \(b\leq a\). In a residuated value object it may instead return a residual. Thus subtraction is not supplied by UDL or UODL themselves; it is extra observer structure.

This factorization also separates two uses of “second term.” In the regret difference, \(L_T^{\mathrm{stat}}\) is the full-information UDL term. In the FTRL action objective, by contrast, the regularizer is a mechanism term. It stabilizes the adapted action readout and is not the hindsight comparator. Standard static regret therefore has the typed architecture

\[ \begin{array}{ccccc} \text{prefix evidence}& \longrightarrow & \text{UODL actions} & \longrightarrow & L_T^{\mathrm{on}}\\ \text{full evidence}& \longrightarrow & \text{UDL constant comparator} & \longrightarrow & L_T^{\mathrm{stat}} \end{array} \quad \xrightarrow {\ \Omega \ }\quad R_T. \]

Changing the reference branch changes the observer semantics: allowing a time-varying full-information comparator produces dynamic rather than static regret, even when the online learner is unchanged.