source/tex/sections/one-point.tex

% !TEX root = ../main.tex

\section{One-Point Bandit Linear Optimization}
\label{sec:1point}
In this section, beyond the two-point setup, we demonstrate the versatility of our technique in the \emph{one-point} Bandit Linear Optimization (BLO) setting. 
Specifically, one-point BLO only allows the learner to query one point $\x_t \in \X$ and observe value of \smash{$f_t(\x_t)\define\inner{\ellb_t}{\x_t}$}, at each round $t \in [T]$. 

For one-point BLO, there are partial results that combine optimistic online learning and variance-reduced gradient estimators to derive \emph{gradient-variance} regret~\citep{hazan2009stochastic,hazan2011betterBCO}. 
Specifically, their methods update a sequence $\{\w_t\}_{t=1}^T$ and query \smash{$\x_t=\w_t+\epsilon_t \lambda_{t,i_t}^{-\frac12}\u_{t,i_t}$}. 
Here, $i_t$ is drawn uniformly from $[d]$, and $\epsilon_t$ is sampled uniformly from \smash{$\{-1,+1\}$}. $\lambda_{t,i_t}$ and $\u_{t,i_t}$ denote the $i_t$-th eigenvalue and eigenvector of the Hessian $\nabla^2 \mathcal{R}(\w_t)$ for a barrier function $\mathcal{R}(\cdot)$. The gradient estimator then takes the form of:
\begin{equation}
    \label{eq:1pvariance}
    \smash{\g_t=d\inner{\ellb_t-\tgb_t}{\x_t},\epsilon_t\lambda_{t,i_t}^{\frac12}\u_{t,i_t}+\tgb_t,}
\end{equation}
where $\tgb_t$ denotes a reservoir-based estimate of the gradient mean.
While effective for the variance bound, extending their method to gradient-variation regret remains a highly non-trivial open challenge. 

Inspired by the construction in \pref{eq:chiangestimator}, we design a novel gradient estimator and establish the \emph{first} gradient-variation regret bound for one-point BLO over the hyper-rectangular domains, which is formally defined below.
\begin{Assumption}
    \label{ass:hyper-rectangle}
The domain $\X \subset \R^d$ is a hyper-rectangle of the form \smash{$\X = \prod_{i=1}^d [a_i, b_i]$}, where $ a_i < b_i$ for all $i \in [d]$.
\end{Assumption}
The novel gradient estimator is constructed as follows:
\begin{equation}
    \label{eq:chiangestimator1p}
    \begin{gathered}
        \tgb_t = {}  \frac{1}{2}\sum_{i=1}^d \lambda_{t,i}^{\frac{1}{2}} \sbr{r^{(+1)}_i-r^{(-1)}_i} \eb_{i_t},\\
        \g_t = {}  d(\inner{\ellb_t}{\x_t} -  z_t)\epsilon_t\lambda_{t,i_t}^{\frac{1}{2}}\eb_{i_t} + \tgb_t,
    \end{gathered}
\end{equation}
where $i_t,\epsilon_t$ share the same definition as in \pref{eq:1pvariance}. 
We maintain buffers \smash{$\mathbf{r}^{(\pm 1)} \in \mathbb{R}^d$} to store historical gradient estimation values. 
In this case, we define $\alpha_t$ as the largest integer such that \smash{$0 \leq \alpha_t < t$, $i_{\alpha_t} = i_t$}, and \smash{$\epsilon_{\alpha_t} = \epsilon_t$}. 
Then \smash{$z_t \define r_{i_t}^{(\epsilon_t)}=\inner{\ellb_{\alpha_t}}{\x_{\alpha_t}}$} represents the function value when \smash{$(i_t, \epsilon_t)$} was last sampled. 
$\lambda_{t,i}$ denotes the $i$-th eigenvalue of the Hessian $\nabla^2 \mathcal{R}(\w_t)$, where $\mathcal{R}(\cdot)$ is the log-barrier function defined as \smash{$\mathcal{R}(\w) = -\sum_{i=1}^d \sbr{\log(w_i - a_i) + \log(b_i - w_i)}$}.

\begin{algorithm}[t]
    \caption{Gradient-Variation One-Point BLO}
    \label{alg:1p-BLO}
    \begin{algorithmic}[1]
        \Require Step size $\eta>0$
        \State \textbf{Initialization:} $\w_1=\mathbf{0}$, \smash{$\tgb_1 = \mathbf{0}$}, \smash{$G_0=\mathbf{0}$} and buffer vectors \smash{$\r^{(+1)} = \r^{(-1)} =\mathbf{0}\in \R^{d}$}
        \For{round $t \in [T]$}
            \State Compute $\tgb_t$ as in \eqref{eq:chiangestimator1p}
            \State Choose $i_t$ uniformly from $[d]$ and $\epsilon_t$ uniformly from \smash{$\{-1,+1\}$} and fetch \smash{$z_t=r^{(\epsilon_t)}_{i_t}$}
            \State Play action $\x_t = \w_t + \epsilon_t \lambda_{t,i_t}^{-1/2}\eb_{i_t}$
            \State Observe $v_t=\inner{\ellb_t}{\x_t}$ and compute $\g_t$ as in \eqref{eq:chiangestimator1p}
            \State Update buffer vector \smash{$r^{(\epsilon_t)}_{i_t}=v_t$}
            \State Calculate \smash{$G_t=G_{t-1}+\g_t$} and update
            \begin{equation*}
               \smash{\w_{t+1} = \argmin_{\w \in \X}\bbr{\eta \left\langle G_t+\tgb_{t+1},\w\right\rangle+\mathcal{R}(\w)}}
            \end{equation*}
        \EndFor
    \end{algorithmic}
\end{algorithm}
Using \pref{eq:chiangestimator1p}, we propose \pref{alg:1p-BLO} with its regret guarantee in \pref{thm:1p-BLO}. The proof is deferred to \pref{app:1point}.
\begin{Theorem}
    \label{thm:1p-BLO}    
    Under Assumptions~\ref{ass:boundedness}-\ref{ass:Smoothness}, \ref{ass:hyper-rectangle}, choosing $\eta=\frac{1}{8RGd^2\sqrt{V_T\ln T}}$, with \smash{$V_T\define\sumTT\|\ellb_t-\ellb_{t-1}\|^2$}, \pref{alg:1p-BLO} satisfies:
    \begin{equation*}
        \E[\Reg_T]\le \O \Big(d^{\frac{7}{2}}\sqrt{V_T\log^3 T}\Big).
    \end{equation*}   
\end{Theorem}
To the best of our knowledge, this is the \emph{first} gradient-variation regret bound for one-point BLO, albeit with the assumption of a hyper-rectangular feasible domain.
\begin{Remark}
    We adopt \pref{ass:hyper-rectangle} mainly due to technical reasons. 
    Specifically, since the Hessian of $\mathcal{R}(\cdot)$ remains diagonal for hyper-rectangular domains, its eigenvectors coincide with the standard basis vectors, which enables the optimistic term $\tgb_t$ to store historical data component-wise, making our analysis in \pref{sec:cvx-base} implementable.
\end{Remark}
\begin{Remark}
Note that \pref{alg:1p-BLO} is not directly implementable due to a causality issue: the estimator $\tgb_{t}$ depends on $\w_t$, which is in turn determined by $\tgb_{t}$. 
However, we can determine $\tgb_{t}$ and $\w_t$ by solving $d$ independent equations involving strictly monotonic functions. 
Consequently, $\w_t$ can be efficiently approximated via binary search to a precision of $1/T$ within $\O(\log T)$ iterations, incurring only a negligible additive $\O(1)$ term in the final regret. 
We refer readers to \pref{app:practical-1p-BLO} for a practical algorithm.
\end{Remark}
Finally, we stress that establishing \mbox{gradient-variation} regret for one-point BLO is pretty challenging, as it reduces to the open problem of obtaining squared \mbox{path-length} in multi-armed bandits~\citep{wei2018more}. 
As a first step, we demonstrate the versatility of our approach on \mbox{hyper-rectangular} domains, deferring the general case to future research.