Concluding, it is worth discussing the inherent difficulties of the problem at hand. Namely, one might argue that we could directly apply the optimistic FTRL result of [1]} (or our equivalent Lemma REF ) both to the primal and to the dual update, and combine the results to bound \(\mathcal {R}_T\)  and \(\mathcal {V}_T\) . The interested reader, however, can verify that this straightforward strategy leads to much worse bounds. Our approach instead is to apply the optimistic FTRL only to the dual update and carefully reconstruct tighter bounds for the Lagrangian, while using a fixed-point iteration to find the exact (minimum) growth rate of \(\Vert \lambda _T\Vert \) . Moreover, unlike prior works such as [2]} or [3]}, we update \(\lbrace x_t\rbrace \)  using \(\lbrace \lambda _t\rbrace \)  (instead of \(\lambda _{t-1}\) ); and then update \(\lbrace \lambda _{t+1}\rbrace \)  using the newly calculated \(\lbrace x_t\rbrace \) . This strategy facilitates the inclusion of predictions as we only need to predict \(x_t\)  and not \(\lambda _t\) . Besides, it is exactly this circular relation between the primal and dual variables which renders the inclusion of predictions in OCO with budget constraints fundamentally different from the respective OCO problem without time-varying constraints.
