Question 1
Here we must first show that:
(1)
\begin{align} \sum_{t = 1}^{T} \log \left(\sum_{m \in \mathcal{M}} w_{m}(t) \exp (- \beta (Y_{t} - \hat{f}_{m}(t))^{2}) \right) = \log \left(\sum_{m \in \mathcal{M}} \pi_{m} \exp \left(- \beta \sum_{t = 1}^{T} (Y_{t} - \hat{f}_{m}(t))^{2}\right)\right) \end{align}
where
(2)
\begin{align} w_{m}(t) &= \frac{\pi_{m} e^{- \beta \hat{r}_{m}(t)}}{\sum_{m \in \mathcal{M}} \pi_{m} e^{- \beta \hat{r}_{m}(t)}} \\ &= \frac{\pi_{m} e^{- \beta \hat{r}_{m}(t)}}{\mathcal{L}_{t}} \end{align}
We use the morphism property of the logarithm and simplify the product:
(3)
\begin{align} (1) &= \sum_{t = 1}^{T} \log \left( \sum_{m \in \mathcal{M}} w_{m}(t) \exp (- \beta (Y_{t} - \hat{f}_{m}(t))^{2}) \right) \\ &= \sum_{t = 1}^{T} \log \left( \sum_{m \in \mathcal{M}} \frac{\pi_{m}}{\mathcal{L}_{t}} \exp (-\beta [\hat{r}_{m}(t) + (Y_{t} - \hat{f}_{m}(t))^{2}]) \right) \\ &= \log \left( \prod_{t = 1}^{T} \sum_{m \in \mathcal{M}} \frac{\pi_{m}}{\mathcal{L}_{t}} \exp (-\beta \hat{r}_{m}(t+1) ) \right) \\ &= \log \left(\prod_{t = 1}^{T}{\mathcal{L}_{t+1}\over \mathcal{L}_{t}} \right)=\log\left({\mathcal{L}_{T+1}\over \mathcal{L}_{1}}\right) \end{align}
We notice that
(4)
\begin{align} \mathcal{L}_{1} &= \sum_{m \in \mathcal{M}} \pi_{m} e^{- \beta \hat{r}_{m}(1)} \\ &= \sum_{m \in \mathcal{M}} \pi_{m} \\ &= 1 \end{align}
since the sum defining $\hat{r}_{m}(1)$ is empty.
Since a sum of non-negative terms is larger than the largest term of the sum
(5)
\begin{align} (1) &= \log(\mathcal{L}_{T+1}) \\ &= \log \left( \sum_{m \in \mathcal{M}} \pi_{m} e^{- \beta r_{m}(T)} \right)\\ & \geq \log \left( \max_{m \in \mathcal{M}} \pi_{m} e^{- \beta r_{m}(T)} \right)\\ &= \max_{m \in \mathcal{M}} ( \log(\pi_{m}) - \beta r_{m}(T) ) \end{align}
Question 2
Let $f : x \rightarrow e^{- x^{2}}$.
To show concavity on the desired interval, we differentiate two times:
(6)
\begin{align} f^{'}(x) &= -2xe^{- x^{2}} \\ f^{''}(x) &= -2e^{- x^{2}} + 4x^{2}e^{-x^{2}} \\ &= 2((\sqrt{2}x)^{2} - 1)e^{- x^{2}} \end{align}
which is non-positive precisely when
(7)
\begin{align} (\sqrt{2}x)^{2} &\leq 1 \\ |x| &\leq \frac{1}{\sqrt{2}} \\ x &\in [-2^{-1/2}; 2^{-1/2}] \end{align}
We recall that $Y_{t} \leq B$ and $\hat{f}_{m}(t) \leq B$,
so that $|Y_{t} - \hat{f}_{m}(t)| \leq 2B$.
We then hypothesize that:
(8)
\begin{align} &\beta \leq \frac{1}{8B^{2}} \\ \iff &4B^{2} \beta \leq \frac{1}{2} \\ \implies &\beta |Y_{t} - \hat{f}_{m}(t)|^{2} \leq \frac{1}{2} \\ \implies &\sqrt{\beta} |Y_{t} - \hat{f}_{m}(t)| \leq 2^{-1/2} \\ \end{align}
By a miraculous coincidence, f is concave at $\sqrt{\beta} |Y_{t} - \hat{f}_{m}(t)|$
under this hypothesis and therefore:
(9)
\begin{align} \sum_{m \in \mathcal{M}} w_{m}(t) e^{- \beta (Y_{t} - \hat{f}_{m}(t))^{2}} &\leq \exp \left(- \left( \sum_{m \in \mathcal{M}} w_{m}(t) \sqrt{\beta} (Y_{t} - \hat{f}_{m}(t)) \right)^{2} \right) \\ &\leq \exp \left(- \beta \left( Y_{t} - \sum_{m \in \mathcal{M}} w_{m}(t) \hat{f}_{m}(t) \right)^{2} \right) \\ &\leq \exp (- \beta (Y_{t} - \hat{f}(t))^{2} ) \end{align}
Question 3
Taking the logarithm of the previous inequality and summing over t, we get:
(10)
\begin{align} \sum_{t = 1}^{T} - \beta (Y_{t} - \hat{f}(t))^{2} &\geq \sum_{t = 1}^{T} \log \left(\sum_{m \in \mathcal{M}} w_{m}(t) e^{- \beta (Y_{t} - \hat{f}_{m}(t))^{2}} \right) \\ &\geq \max_{m \in \mathcal{M}} ( \log(\pi_{m}) - \beta r_{m}(T) ) \end{align}
by the inequality from Question 1.
Therefore:
(11)
\begin{align} \sum_{t = 1}^{T} (Y_{t} - \hat{f}(t))^{2} &\leq - \max_{m \in \mathcal{M}}\left\{ \frac{1}{\beta}\log \pi_{m} - r_{m}(T)\right\} \\ & \leq \min_{m \in \mathcal{M}} \left\{ r_{m}(T) - \frac{1}{\beta} \log \pi_{m} \right\} \\ &\leq \min_{m \in \mathcal{M}} \left\{ \sum_{t = 1}^{T} (Y_{t} - \hat{f}_{m}(t))^{2} + \frac{1}{\beta} \log \frac{1}{\pi_{m}} \right\} \end{align}
Question 4
In this question we shall introduce the notation
$\mathcal{F}_{t} = \sigma ((X_{i},Y_{i})_{i = 1,...,t-1}, X_{t})$
so that $\hat{f}(t)$ and $\hat{f}_{m}(t)$ as well as $f(X_{t})$ are $\mathcal{F}_{t}$ - measurable, and
$\sigma_{t}$ is independent of $\mathcal{F}_{t}$.
Using the deterministic inequality from question 3 with optimal $\beta = 8B^{2}$ and taking expectations yields:
(12)
\begin{align} \frac{1}{T} \sum_{t = 1}^{T} (Y_{t} - \hat{f}(t))^{2} &\leq \min_{m \in \mathcal{M}} \left\{ \frac{1}{T} \sum_{t = 1}^{T} (Y_{t} - \hat{f}_{m}(t))^{2} + \frac{8B^{2}}{T} \log(\frac{1}{\pi_{m}}) \right\} \\ \frac{1}{T} \sum_{t = 1}^{T} \mathbb{E}[(Y_{t} - \hat{f}(t))^{2}] &\leq \mathbb{E} \left[ \min_{m \in \mathcal{M}} \left\{ \frac{1}{T} \sum_{t = 1}^{T} (Y_{t} - \hat{f}_{m}(t))^{2} + \frac{8B^{2}}{T} \log(\frac{1}{\pi_{m}}) \right\} \right] \\ &\leq \min_{m \in \mathcal{M}} \left\{ \frac{1}{T} \sum_{t = 1}^{T} \mathbb{E}[(Y_{t} - \hat{f}_{m}(t))^{2}] + \frac{8B^{2}}{T} \log(\frac{1}{\pi_{m}}) \right\} \end{align}
Now if $g(t)$ is $\mathcal{F}_{t}$ - measurable then:
(13)
\begin{align} \mathbb{E}[(Y_{t} - g(t))^{2}] &= \mathbb{E}[((f(X_{t}) - g(t)) + \varepsilon_{t})^{2}] \\ &= \mathbb{E}[(f(X_{t}) - g(t))^{2}] + 2\mathbb{E}[(f(X_{t}) - g(t))\varepsilon_{t}] + \mathbb{E}[\varepsilon_{t}^{2}] \\ &= \mathbb{E}[(f(X_{t}) - g(t))^{2}] + 2\mathbb{E}[(f(X_{t}) - g(t))\mathbb{E}[\varepsilon_{t}|\mathcal{F}_{t}]] + \sigma_{t}^{2} \\ &= \mathbb{E}[(f(X_{t}) - g(t))^{2}] + \sigma_{t}^{2} \end{align}
So the previous equation can be rewritten as:
(14)
\begin{align} \frac{1}{T} \sum_{t = 1}^{T} \mathbb{E}[(f(X_{t}) - \hat{f}(t))^{2}] + \sigma_{t}^{2} \leq \min_{m \in \mathcal{M}} \left\{ \frac{1}{T} \sum_{t = 1}^{T} \left( \mathbb{E}[(f(X_{t}) - \hat{f}_{m}(t))^{2}] + \sigma_{t}^{2} \right) \ + \ \frac{8B^{2}}{T} \log(\frac{1}{\pi_{m}}) \right\} \end{align}
and the $\sigma_{t}^{2}$ can be simplified out, leaving:
(15)
\begin{align} \frac{1}{T} \sum_{t = 1}^{T} \mathbb{E}[(f(X_{t}) - \hat{f}(t))^{2}]\leq \min_{m \in \mathcal{M}} \left\{ \frac{1}{T} \sum_{t = 1}^{T} \mathbb{E}[(f(X_{t}) - \hat{f}_{m}(t))^{2}]\ + \ \frac{8B^{2}}{T} \log(\frac{1}{\pi_{m}}) \right\} \end{align}
QED.
