Regret bound for the adaptive online policy in Algorithm 5

Let $a_t$ be an independent and identically distributed process, and let $r_i$ follow either a linear regression model with white noise or a weighted random-walk model. Let $\pi_5$ denote the online policy specified by Algorithm 5, and let $\Delta_n(\pi_5)$ be its regret over $n$ rounds. Under suitable regularity conditions, Regret-bound conjecture.

$$\Delta_n(\pi_5) \leq O(n\log n).$$

The conjecture proposes a formal regret guarantee for the adaptive algorithm under the stochastic input models considered in the paper; the specific regularity conditions and a proof remain to be established.