Online Prediction of Stochastic Sequences with High Probability Regret Bounds

1. Problem Definition

The paper addresses the classical problem of universal prediction of stochastic sequences with a finite, deterministic time horizon $T$.

• Setup: A learner observes a sequence $Z_1, \dots, Z_T$ drawn from an unknown joint probability distribution $P$ over a measurable space $\mathcal{Z}$. At each time step $t$, the learner predicts $B_t$ based on past observations $Z_{1}, \dots, Z_{t-1}$ and incurs a loss $\ell(B_t, Z_t)$.
• Goal: The learner seeks a strategy that is "universal," meaning it does not depend on the specific unknown distribution $P$, yet achieves a regret (the difference between the learner's cumulative loss and the cumulative loss of an optimal strategy that knows $P$) that vanishes as $T \to \infty$.
• Gap in Literature: Existing literature (e.g., Merhav & Feder, 1998; Hutter, 2003) provides bounds on the expected regret ($\mathbb{E}[\Delta]$). However, these do not guarantee that the regret is small with high probability, which is critical for safety-critical applications (e.g., autonomous driving, air traffic control). This paper investigates whether high-probability regret bounds (i.e., $\mathbb{P}(\Delta > \epsilon) \leq \delta$) can be derived for this scenario.

2. Methodology

The authors employ a two-step approach, moving from a simplified technical problem to the general universal setting.

A. The Mismatched Prediction Problem

To derive the bounds, the authors first analyze a "mismatched" scenario where the learner assumes the data follows a known distribution $Q$ (which may differ from the true $P$) and acts optimally with respect to $Q$.

• Regret Definition: The regret $\Delta$ is defined as the average difference between the loss incurred by the learner (using $Q$) and the loss incurred by an oracle (using $P$).
• Similarity Measures: The analysis relies on measuring the divergence between $P$ and $Q$ using:
  • Variational Distance ($V_T$): The expected average total variation distance between the conditional distributions of $P$ and $Q$.
  • Kullback-Leibler (KL) Divergence ($D(P||Q)$): The expected average KL divergence.
• Key Technical Tool: The authors identify a supermartingale structure in the regret process. By applying the Azuma-Hoeffding inequality, they derive a high-probability bound for the mismatched case.

B. Application to Universal Prediction

The results from the mismatched problem are applied to the universal prediction setting by constructing a universal measure $Q_N$.

• Universal Measure: $Q_N$ is typically constructed as a mixture of a parametric family of distributions $\{P_\theta\}_{\theta \in \Theta}$ weighted by a prior $w$:
  $$Q_N = \int_{\Theta} P_\theta w(d\theta)$$
• Convergence Logic: If the true distribution $P$ belongs to the family (i.e., $P = P_{\theta_0}$ for some $\theta_0$ in the support of $w$), the KL divergence $D(P||Q_N)$ grows sublinearly (often logarithmically) with $T$. This ensures the regret vanishes.

3. Key Contributions

1. High-Probability Regret Bounds: The paper provides the first high-probability regret bounds for universal prediction of non-i.i.d. stochastic sequences without expert advice.
2. Impossibility Result: The authors prove that the dependence on the failure probability $\delta$ in their bounds is optimal. Specifically, they show that without additional assumptions, the factor $1/\delta$ (or $1/\sqrt{\delta}$) cannot be replaced by a term that grows significantly slower (e.g., logarithmic) as $\delta \to 0$.
3. Relaxed Assumptions: Unlike previous works that often required finite alphabets, this work handles countable and general measurable spaces with milder technical assumptions.

4. Key Results

Theoretical Bounds

The main result (Theorem 4) states that for any $\delta \in (0, 1]$, with probability at least $1-\delta$:
$$\Delta < 2L \sqrt{\frac{D(P||Q)}{T}} \cdot \frac{1}{\sqrt{\delta}} + \frac{2\sqrt{2}L}{\sqrt{T}} \sqrt{\log \frac{2}{\delta}}$$
Where $L$ is the bound on the loss function.

• Convergence Rate: For a countable alphabet where $D(P||Q)$ is bounded (e.g., in the universal coding setting), the regret converges at a rate of $O(T^{-1/2} \delta^{-1/2})$.
• Comparison to Expectation: This complements the known expectation bound of $O(T^{-1/2})$. The high-probability bound introduces a penalty factor of $\delta^{-1/2}$, which is necessary to guarantee the bound holds with high confidence.

Impossibility Theorem (Theorem 5)

The authors construct a counter-example showing that for any prediction problem, there exists a distribution where the regret is 0 with high probability but close to the maximum loss with probability $\delta$. This proves that the $\delta^{-1/2}$ (or $\delta^{-1}$) scaling in the bound is unavoidable without further assumptions on the tail behavior of the loss.

Summary of Convergence Rates (Table 1)

The paper summarizes convergence rates for different scenarios:

• Countable $Z$ (Universal): $O(T^{-1/2})$ (Expectation) $\to$ $O(T^{-1/2}\delta^{-1/2})$ (High Prob).
• i.i.d. $P_N$: $O((T/\log T)^{-1/2})$ (Expectation) $\to$ $O((T/\log T)^{-1/2}\delta^{-1/2})$ (High Prob).
• Markov Chains: Similar improvements over expectation bounds.

5. Numerical Experiments

The authors validated their theory using a Markov chain with memory $m=3$ and $S=2$ states.

• Setup: The learner used a mixture distribution $Q_N$ over all possible transition parameters.
• Findings:
  • The mean regret converged to 0 as sequence length increased.
  • The observed quantiles (representing the high-probability behavior) also converged to 0, though slower than the mean, consistent with the theoretical $\delta^{-1/2}$ factor.
  • The experiments demonstrated that the framework is computationally feasible for moderate state spaces and memory orders.

6. Significance and Implications

• Practical Reliability: The results are significant for safety-critical systems where "average" performance is insufficient. Knowing that the regret is bounded with probability $1-\delta$ allows for rigorous risk management in applications like medical diagnosis (sepsis prediction) and autonomous navigation.
• Theoretical Rigor: The paper closes a gap in online learning theory by establishing that high-probability bounds for universal prediction are possible but inherently come with a specific cost regarding the confidence parameter $\delta$.
• Optimality: The impossibility result prevents researchers from chasing "logarithmic in $\delta$" bounds for this general setting, redirecting focus toward finding specific structural assumptions that might allow for tighter bounds.

In summary, this paper establishes that while universal prediction can achieve vanishing regret with high probability, the confidence level $\delta$ comes at a polynomial cost in the bound, a trade-off that is proven to be fundamental to the problem structure.