92. Confidence from dependent observations
On this page · Permalink · Source line 3656
Let \(\mathcal F_{t-1}\) contain all information available before observation \(t\), including its already selected action. Let \(\phi_t\in\mathbb R^d\) be measurable with respect to that information. Assume
for every real \(h\), with \(\sigma>0\), and a declared bound \(\|\theta_*\|_2\leq S\). With ridge \(\gamma>0\), set
Proposition 81: Time-uniform regression confidence
For \(0<\delta<1\), with probability at least \(1-\delta\), simultaneously for every finite \(t\),
No independence of successive observations or of the regressors is required. The conditional mean, conditional noise and predictability hypotheses are required. The confidence set remains valid at a stopping time selected from the data.
Read proof · Recorded Lean scope · Visual guide: A confidence set can meet an exact certificate · Permalink · Source line 3675
Proof
Put \(S_t=\sum_{s\leq t}\phi_s\xi_s\). For every fixed \(q\), the conditional moment bound makes
a nonnegative supermartingale. Integrate against the fixed Gaussian law \(q\sim N(0,(\gamma I)^{-1})\). Conditional Tonelli and completing the square give the nonnegative supermartingale
For completeness, stop at the first crossing of \(1/\delta\), then at any deterministic finite horizon. The supermartingale expectation is at most one, so the crossing probability up to that horizon is at most \(\delta\). Increasing the horizon proves the same bound for any finite crossing. Off this event, taking logarithms bounds \(\|S_t\|_{V_t^{-1}}\) by the square-root term. Finally,
The triangle inequality and \(V_t\succeq\gamma I\) bound the ridge term by \(\sqrt\gamma S\). The simultaneous event already covers every selected finite stopping time. \(\square\)
This is the self-normalized mixture argument in [R23], not a new concentration principle. A bounded response in an interval of length \(b-a\) has conditionally sub-Gaussian centered noise with \(\sigma=(b-a)/2\). One direct proof differentiates its tilted log moment-generating function twice. The second derivative is a variance bounded by \((b-a)^2/4\). Integrating from zero gives the stated moment bound.
The determinant term accounts for the observed design, but does not create excitation. If \(\phi_t\) never probes a direction, the set need not shrink in that direction. Regressors extracted after inspecting the same response are not predictable. An estimated hidden state cannot be substituted for \(\phi_t\) while silently retaining the theorem's true conditional-mean equation.