Past exam of the algorithmic foundations of learning course of the University of Oxford / 2025 / 2

Work for an arbitrary realization of the sequence, and set $u_t=X_t^T{V}_{t-1}^{-1}{X}_t$. In the Loewner order,By the spectral theorem for real symmetric matrices, every eigenvalue of $V_{t-1}$ is at least $\lambda$. The matrix inverse therefore has eigenvalues at most ${\lambda }^{-1}$, andFor $0\le u\le 1$, put $g(u)=2\log (1+u)-u$. Since $g(0)=0$ and $g^{\prime }(u)=(1-u)/(1+u)\ge 0$, we have $u\le 2\log (1+u)$. The matrix determinant lemma now givesTaking logarithms and using a telescoping sum,This elliptical potential bound holds for every realization and every $n$, without a probabilistic exceptional event. The condition $\lambda \ge 1$ is what ensures $u_t\le 1$.

Let $a_1,\dots ,a_d>0$ be the eigenvalues of the positive-definite matrix $V_n$. Its trace satisfiesThe arithmetic-geometric mean inequality givesSince $\det V_0={\lambda }^d$, taking the logarithm provesThe determinant is largest, for a fixed trace, when the eigenvalues are equal; this is the geometric content of the estimate.

Use the single eventFix a realization in $\mathcal{E}$. The action space is nonempty and compact, since it is a closed subset of the finite-dimensional unit ball. The Lipschitz continuous reward function is continuous, so there is an optimal action $x_{\star }\in {\mathrm{argmax}}_{x\in \mathcal{X}}\mu (⟨x,{\theta }_{\star }⟩)$. Because the same reward function is used at every time, the pseudoregret is $R_n={\sum }_{t=1}^n{r}_t$, whereThe pair $(x_{\star },{\theta }_{\star })$ is feasible in the optimization defining $(X_t,{\theta }_t)$. This optimism in the face of uncertainty givesFor any positive-definite matrix $V$, the ordinary Cauchy-Schwarz inequality applied to $V^{-1/2}x$ and $V^{1/2}z$ provesBoth ${\theta }_t$ and ${\theta }_{\star }$ belong to the same confidence ellipsoid ${\Theta }_{t-1}$. The triangle inequality for the norm associated with this weighted Euclidean inner product therefore givesand hence $r_t\le 2L{\beta }_{t-1}(\delta )|X_t{|}_{V_{t-1}^{-1}}$. Monotonicity of ${\beta }_t(\delta )$ and another Cauchy-Schwarz inequality now yieldThis reasoning holds on $\mathcal{E}$ for every $n$ simultaneously, proving the asserted probability. In combination with part (a), it also givesOnly the supplied simultaneous confidence set coverage and the optimistic choice are needed here. No claim that the displayed linear estimator is automatically a suitable estimator for a nonlinear link is required: its coverage was an explicit hypothesis.

Let ${\mathcal{G}}_t=\sigma (X_1,\dots ,X_t)$. Under $P_{{\theta }_{\star }}$, the true probability density function is positive and finite at every observation almost surely. Define the sequential likelihood ratioA zero numerator sets the product to zero thereafter. Thus $M_t$ is a well-defined nonnegative process, and $L_t({\theta }_{\star })=\log M_t$, with $\log 0=-\infty$.

The next observation is independent of ${\mathcal{G}}_{s-1}$, while ${\hat{\theta }}_{s-1}$ is measurable with respect to that sigma-algebra. Its conditional expectation is thereforeConsequently $\mathbb{E}(M_s\mid {\mathcal{G}}_{s-1})\le M_{s-1}$; induction also gives $\mathbb{E}{M}_s\le 1$. Thus $(M_t)$ is a nonnegative supermartingale for the filtration $({\mathcal{G}}_t)$. It need not be a martingale: an alternative distribution can put mass outside the support of the true distribution.

The maximal inequality for a nonnegative supermartingale, the corresponding form of the Ville inequality, givesThe strict inequality in the definition of the confidence set correctly becomes a non-strict crossing event.

There is a minor definitional omission in the source: for false candidates $\theta$, the printed sum of log-likelihood ratios can involve $0/0$ or both infinite signs. To define the entire confidence set without a positivity assumption, use the logarithm of the ratio of the two full products, ${\prod }_s{p}_{{\hat{\theta }}_{s-1}}(X_s)$ and ${\prod }_s{p}_{\theta }(X_s)$, taking $0/a=0$ for $a>0$, $a/0=+\infty$ for $a>0$, and, for example, $0/0=1$. This is a measurable extension of the printed formula wherever that formula is defined. The choice at $0/0$ cannot affect coverage of the truth, since its full denominator is positive almost surely. Alternatively, strict positivity of every density on the common support removes the omission.