source/tex/sections/extension.tex

% !TEX root = ../main.tex

\section{Applications}
\label{sec:extension}
In this section, we demonstrate the effectiveness of our methods in more challenging tasks, including dynamic/universal regret minimization and bandit games.

\textbf{\Circled{1} Dynamic Regret.}~~
\label{subsec:dynamic}
In this part, we extend our technique to the dynamic regret setting~\citep{zinkevich2003online} in two-point BCO. Specifically, dynamic regret compares the learner's performance with a sequence of \mbox{time-varying} comparators \smash{$\{\u_t\}_{t=1}^T$} and is defined as follows:
\begin{equation}
    \label{eq:dreg}
    \DReg_T \define \sumT f_t(\x_t) - \sumT f_t(\u_t).
\end{equation}
Ideally, dynamic regret scales with the path length $P_T \triangleq \sum_{t=2}^T \|\u_t - \u_{t-1}\|$, which captures the non-stationarity of the environment and is unknown to the learner. 
In OCO, \citet{zhang2018adaptive} obtained the minimax optimal dynamic regret of \smash{$\O(\sqrt{T (1+P_T)})$}, which can be strengthened to \smash{$\O(\sqrt{(1+V_T+P_T) (1+P_T)})$}~\citep{zhao2024adaptivity} for smooth functions. For two-point BCO, \citet{zhao2021bandit} first established a dynamic regret bound of \smash{$\O(d\sqrt{T(1+P_T)})$}, which was later sharpened to \smash{$\O(\sqrt{dT(1+P_T)})$} by \citet{he2025non}.

We validate the effectiveness of our results by achieving \emph{the first}  gradient-variation dynamic regret with unknown path length in the two-point BCO setting.
We provide an informal theorem below and defer the formal version \pref{thm:dynamic-cvx} and the corresponding proof to \pref{app:dynamic-cvx}.
\begin{Theorem}[Informal]
    \label{thm:dynamic-cvx-informal}  
    Under Assumptions \ref{ass:boundedness}-\ref{ass:Smoothness}, using \pref{alg:dynamic_regret} in \pref{app:dynamic-cvx}, we achieve an $\E[\DReg_T] \le \Ot \big(\sqrt{d^3(1+P_T+ V_T)(1+P_T)}\big)$ dynamic regret for convex functions in two-point BCO, without knowing $P_T$.
\end{Theorem}

\textbf{\Circled{2} Universal Regret.}~~
In this part, we study universal regret~\citep{van2016metagrad} for two-point BCO, where the goal is to match the optimal performance for various function types and curvatures \emph{without} prior knowledge of these properties. 
Specifically, for $\mathcal{F}_{\lin}$ (for linear functions), $\mathcal{F}_{\cvx}$ (for convex functions), and $\mathcal{F}^\lambda_{\scvx}$ (for $\lambda$-strongly convex functions), a universal online learning algorithm $\mathcal{A}$ aims to attain the following universal regret satisfying:
\begin{equation*}
    \label{eq:universal-goal}
    \Reg_T(\A, \{f_t\}_{t=1}^T) \lesssim 
    \begin{cases}
        \Reg_T(\A_\scvx, \F^\lambda_\scvx), \\[1mm]
        \Reg_T(\A_{\cvx}, \F_{\cvx}), \\[1mm]
        \Reg_T(\A_{\lin}, \F_{\lin}),  \\[1mm]
    \end{cases}
\end{equation*}
where \smash{$\A_\scvx$, $\A_{\cvx}$, $\A_{\lin}$} are the (optimal) algorithms designed for $\F^\lambda_\scvx$, $\F_{\cvx}$, and $\F_{\lin}$, respectively. That is, $\A$ is supposed to have comparable regret guarantees with the optimal algorithms designed for the corresponding function classes.

Building on \citet{yan2024simple}, which proposed the optimal universal gradient-variation regret for OCO, we establish \emph{the first} gradient-variation universal regret for linear, convex, and strongly convex functions in two-point BCO by leveraging a new decomposition of the non-consecutive gradient variation. 
We give an informal theorem below and defer the formal version \pref{thm:2point-BCO-Bregman} and its proof to \pref{app:universal}.
\begin{Theorem}[Informal]
    \label{thm:2point-BCO-Bregman-informal}
    Under Assumptions \ref{ass:boundedness}, \ref{ass:Lipschitzness}, \ref{ass:Smoothness++}, Algorithm~\ref{alg:UniGrad-Bregman-1grad} in \pref{app:universal} attains universal regret bounds of \smash{$\O\big(\sqrt{d^3V_T}\big)$}, \smash{$\Ot\big(\sqrt{d^3V_T}+ d^3\big)$}, and \smash{$\O\big(\frac{d}{\lambda}\log(dV_T)\big)$} for linear, convex, $\lambda$-strongly convex functions, respectively. 
\end{Theorem}

\textbf{\Circled{3} Games.}~~
In this part, we extend our results in \mbox{one-point} BLO to bandit bilinear game on hyper-rectangular domains. 
Specifically, we consider a $T$-round zero-sum bilinear game between $\x$-player and $\y$-player with a fixed payoff matrix $A \in \R^{m \times n}$. The action sets for $\x$-player and $\y$-player are denoted as $\X \subseteq \R^m$ and $\Y \subseteq \R^n$, respectively. 
At round $t \in [T]$, the players simultaneously select their actions $\x_t \in \mathcal{X}$ and $\y_t \in \mathcal{Y}$. 
Then, $\x$-player receives loss $f(\x_t,\y_t)=\x_t^\top A \y_t$. Similarly, $\y$-player receives the same reward. 
Finally, $\x$-player submits $\xb\define\frac{1}{T}\sum_{t=1}^T \x_t$ and $\y$-player submits $\yb\define\frac{1}{T}\sum_{t=1}^T \y_t$. 

The performance of the game is evaluated by the duality gap, i.e., the gap to the Nash equilibrium, defined as follows:
\begin{equation*}
    \Dgap(\xb, \yb) \define \max_{\y \in \Y} f(\bar{\x}, \y) - \min_{\x \in \X} f(\x, \bar{\y}).
\end{equation*}
By employing \pref{alg:1p-BLO} as the underlying learning algorithm for both players, we establish an \smash{$\Ot(1/T)$} duality gap guarantee.
We provide an informal theorem below and defer the formal version \pref{thm:game-informal} and its proof to \pref{app:game}.

\begin{Theorem}[Informal]
    \label{thm:game-informal}
    Given hyper-rectangular domains $\X, \Y$ and a bounded payoff matrix $A$, if both players adopt adequate step sizes in \pref{alg:practical}, we achieve an expected duality gap of {$\Ot\big((m^4+n^4)/T\big)$}. 
    Meanwhile, the regret of $\x$-player and $\y$-player are upper-bounded by \smash{$\Ot\big(\sqrt{m^7n^2T}\big)$}.
\end{Theorem}