Extension of Hoeffding-Azuma inequality

Question

I'm trying to solve Exercise 20.7 in Bandit Algorithms by Tor Lattimore and Csaba Szepesv´ari, where it states that if the condition for the original Hoeffding-Azuma inequality is met on an event $A$, i.e. $$ \mathbb{P}\left(\text { exists } t \in[n]: A \text { and } X_t \notin\left[a_t, b_t\right]\right)=0, $$ then for any $\varepsilon>0,$ $$ \mathbb{P}\left(A \cap \sum_{t=1}^n\left(X_t-\mathbb{E}\left[X_t \mid \mathcal{F}_{t-1}\right]\right) \geq \varepsilon\right) \leq \exp \left(-\frac{2 n^2 \varepsilon^2}{\sum_{t=1}^n\left(b_t-a_t\right)^2}\right). $$ I've tried to bound the mgf but falied because the event $A$ breaks the martingale structure and I just don't know how to handle it. I've also read the reference, In Probabilistic methods for algorithmic discrete mathematics, pages 195–248, by C. McDiarmid, where a special event is considered, but I still can't see how to prove it in the general case.

Answer 1

Let $a_t \le b_t$ be fixed numbers. Define $$ \mathcal{E}_t := \{X_t \in [a_t,b_t]\}\\ \mathcal{E}_{\le t}:= \{\forall s \le t, X_t \in [a_t,b_t]\} = \bigcap_{s \le t} \mathcal{E}_{s} \\ \mathcal{E} := \{\forall t, X_t \in [a_t,b_t]\}.$$ Finally let $\mu_t := \mathbb{E}[X_t|\mathscr{F}_{t-1}],$ and $S_t := \sum_{s \le t} X_s - \mu_s$.

Now for any $\lambda, \varepsilon > 0,$ \begin{align} P(\mathcal{E} \cap \{S_n > \varepsilon\}) &= P(\mathcal{E} \cap \{e^{-\lambda \varepsilon + \lambda S_n } \ge 1 \}) \\ &= P(\mathbf{1}_{\mathcal{E}} \cdot e^{-\lambda\varepsilon +\lambda S_n } \ge 1) \\ &\le e^{-\lambda \varepsilon} \mathbb{E}[ \mathbf{1}_\mathcal{E} e^{\lambda S_n}].\end{align}

Now conditioning on $\mathscr{F}_{n-1}$ like in Azuma's inequality, notice that $$ \mathbb{E}[\mathbf{1}_{\mathcal{E}} e^{\lambda S_n}|\mathscr{F}_{n-1}] = \mathbf{1}_{\mathcal{E}_{\le n-1}} e^{\lambda S_{n-1}}\mathbb{E}[ \mathbf{1}_{\mathcal{E}_n}e^{\lambda (S_n - S_{n-1})} |\mathscr{F}_{n-1}].$$ Further, on ${\mathcal{E}_n}, (S_n - S_{n-1}) = X_n - \mu_n \in [a_t-\mu_n, b_t-\mu_n],$ where notice that $\mu_n$ is $\mathscr{F}_{n-1}$-measurable. So the random variable $S_n - S_{n-1}$ has bounded range given $\mathcal{E}_n$ and $\mathscr{F}_{n-1}$, and we can hit this with Hoeffding's lemma to conclude that $$ \mathbb{E}[\mathbf{1}_{\mathcal{E}_n} e^{\lambda (S_n - S_{n-1})} |\mathscr{F}_{n-1}] = \mathbf{E}[ e^{\lambda (S_n - S_{n-1})} | \mathscr{F}_{n-1}, \mathcal{E}_n] P(\mathcal{E}_n|\mathscr{F}_{n-1}) \le e^{\lambda^2 (b_n - a_n)^2/8}.$$

But now we're in business - iterate this argument to conclude tha the MGF is bounded by $e^{\lambda^2 \sum (b_t - a_t)^2/8}$ and conclude as usual. Finally notice that for any event $A$, $ A \cap \mathcal{E}_{\le n } \subset \mathcal{E}_{\le n},$ and so the same result has to hold for $P( A \cap \mathcal{E}_{\le n} \cap \{S_n \ge \varepsilon\}).$