Substituting this in the linear equation 15503

Note that here we used that lower triangular504 halves of matrices L and H have the same sparsity patterns, which follows from the fact that banded505 graph is a chordal graph with perfect elimination order {1,2,...,n }. Proof of Theorem 3.1 The proof follows trivially from Theorem 3.1, when b is set to 1.509 A.2 Regret bound analysis510 Proof sketch of Theorem 3.3. We decompose the regret into RT T1+T2+T3 in Lemma .1 and indi-511 vidually bound the terms. This ex-514 plicit expression is later used to bound each entry of (X 1t+1 X 1t)with O(1/ p t)in Appendix A.2.4,515 this gives a O( p T) upperbound on T2. Substituting the above identity in the Equation (19) proves the lemma.527